Matematicki problem - nalazenje najduzeg kontinualnog niza

[mikikg]

Za potrebe nekog programa koji pisem potrebno je da uradim "filtriranje" nekih izmerenih tacaka rastojanja dobijenih preko Lidara (rotacioni laserski daljinomer).

Konretan problem se svodi na to da preko Lidara dobijam tacke izmerenog objekta koje mi u sustini trebaju ali se desi iz raznih razloga da mi u taj skup uleti i neke tacke koje nisu deo objekta koji se prati vec neke "fleke" tj slucajne tacke koje se dobiju refleksijom od pozadine i koje mi prave probleme - trebam da filtriram te tacke.

Da uprostim pricu, recimo da imam ovakva dva niza koja su dobijena iz nekog predhodnog koraka procesiranja.
Prvi niz su izmerene daljine, drugi niz je ugaoni index tacke. Ugaoni index se racuna u opsegu 0-180' sa korakom od 0.25' - tehnicki gledano nebitno je da li izrazeno kao index ili kao ugao, formula je Ugao=Index/4.

Primer (C/C++)

Code:

int daljine[1000];
int ugao[1000];
int broj_tacaka = 4;

daljine[0] = 1500; //mm
daljine[1] = 1800; //mm
daljine[2] = 1400; //mm
daljine[3] = 900; //mm

ugao[0] = 22;
ugao[1] = 23;
ugao[2] = 24;
ugao[3] = 71;

//ocekivani rezultat procesiranja treba da bude 1400mm na ugaonom indexu 24.

U ovom primeru imamo 4 tacke, prve tri su jedna-za-drugom (spojene = deo jednog detektovanog objekta) dok je 4. tacka smetnja-fleka koju trebam da ignorisem.
Algoritam MORA da nadje najblizu tacku objekta koji ima najvecu "sirinu" (najvise uzastopnih tacaka).
Moj trenutni code radi tako sto nadje minimum iz ovog skupa ali u ovom konkretnom slucaju je ocigledno ta 4. tacka smetnja i nije dobro, ocekivani rezultat je 3. tacka (pod idexom [2]) tj 1400mm na 24. ugaonom indexu.

---

Da li moze neko da mi pomogne sa ovim, tj kako bi izgledao algoritam ili konkretno parce code-a koji bi radio ispravno trazenu funkciju?
Code mora da bude veoma veoma optimizovan i brz jer mi je time-frame za procesiranje vrlo uzak i nemam mnogo procesorske snage na raspolaganju.

[rane_nbg]

Prvo sto mi pada na pamet a da je prosto je da, kada vec imas dve informacije X-daljinu i Y-ugao, da dodas jos jednu IF petlju u kojoj nakon trazenja minimuma iz array-a X postavis novi uslov, koristeci elemente iz array-a Y.

Prvo nadjes index minimalnog elmenta iz array-a X. Onda, pitas da li je za taj index element iz array-a Y veci od srednje vrednosti svih elemenata Y. Dodatno, mozes da ubacis neki zadati treshold i da pitas da li je razlika po apsolutnoj vrednosti izmedju tog elementa i srednje vrednosti veca od tresholda, ako jeste, tacka se odbacuje, ako nije uzimas je. U primeru koji si naveo, nece biti tesko da pronadjes tacku koja ima toliko razliciti ugao, od svih ostalih. Ne znam koliko su tacke koje zelis da odbacis bliske i to moze da postane jako tesko za filtiranje ovom procedurom. 

Pravilan nacin da se uradi kako treba u slucaju da imas mnogo elemenata je statisticki, sto naravno zahteva veliko procesorsko vreme. Npr. fitovanje podataka sa gausovom raspodelom ili pravljenjem histogramima od podataka.

Ako mozes posalji malo vise tacaka koje dobijas merenjem i sta ti konkretno znaci mali time frejm za procesiranje i slaba procesorka snaga. Koliko brzo mora to sve da se obavi?

[mikikg]

Ako mozes posalji malo vise tacaka koje dobijas merenjem i sta ti konkretno znaci mali time frejm za procesiranje i slaba procesorka snaga. Koliko brzo mora to sve da se obavi?

Posto je to neki kontinualni sistem, stalno mi stizu ti podaci i program mora da obavi sav racun u pauzi izmedju dva frejma, frejmovi dolaze na svakih 20ms (50Hz) i odprilike sam potrosio nekih 10ms za dosadasnji racun, ima tu vec dosta posla, prvo mora da dekodira vrlo glomazan paket koji je stigao sa Lidara, zatim radi konverziju u planarnu projekciju (floating-point math, to mi je najtezi racun, koristio sam koeficijente umesto sin() i cos() funkcija da bi ubrzao) i onda mora da prvrti sve tacke (trenutno imam 720 ugaonih pozicija) i da nadje one koje su u nekoj definisanoj zoni pa posle toga ide logika trazenja "najblizih tacaka".

U pitanju je RPi 3 koji preko LAN dobija te podatke, taj deo obrade radi samo jedan poseban thread, nemam tu za sad multy-thread (niti znam kako bi ga izveo zbog sinhronizacije).

Taj program (drajver da ga nazovem) radi u pozadini i koristi /dev/shm (shared memory) kanale da komunicira sa drugom GUI APP koja iscrtava to sve, to je manje-vise nebitno, srz logike je tu u tom "drajveru".

[Braca]

Miki, pokušaj da pratiš razliku između uzastopnih tačaka, jer su tada iskakanja iz niza uočljivija.
To podrazumeva da imaš neki kriterijum za razlikovanje "dobre" od "loše" razlike.

Nisam kod kuće i trenutno imam neke obaveze, pa ne mogu da se detaljnije pozabavim problemom.

Pozdrav

[veselinovic]

Miki,
ko da mi se nesto javlja da smo u mjerenjima radili neku devijaciju, pa sto izlazi iz nekog opsega se odbaci.
Ima i gausova kriva ( sjecamo se sa novcanice od 10 DEM).
Mozda, da se napravi aritmeticka sredina svih mjerenja.
Onda se odredi odstupanje svakog mjerenja od aritm. sredine, i odbace rezultati koji odstupaju vise od...
E onda od preostalih rezultata nadjes ait sredinu i eto.
U konkretnom slucaju bi bilo da je Xsr1=1400mm ( slucajno se pogodilo)
sad imas greske:
1. 100
2. 400
3. 0
4. -500
Odbacis 2 i 4 kao suvise pogresne i ostane
1400 i 1500
srednja vrijednost je 1450




Ako mi jos sta padne na pamet javljam se.

[Ubledeli]

@mikikg
e interesantan problem, imam par predloga, slicnih sto ces i videti
prva varijanta je da primenis 1D konvolucioni kernel sto otpada iz razloga nemanja pytorcha ili neke adekvatne biblioteke
druga varijanta je da rucno emuliras kernel i da ga nateras da radi bas ono sto ti hoces
dakle:
sliding window od 2n+1 tacaka recimo 5, gledas trenutnu tacku, dve prethodne i dve sledece
uzmes njihov mean(aritmeticku sredinu jer je tako najjeftinije), i onda poredis, da li je trenutna(srednja od tih 5) tacka u threshold okolini mean-a
ako jeste koristis je, ako nije odbacujes
sa ovom metodom imas dva parametra koja mozes da stelujes, a to su sirina prozora i threshold sta se smatra prihvatljivim a sta ne
obe stvari mogu biti asimetricne, npr uzmes 6 starih tacaka i 2 nove mada je ista susttina, takodje + depth i - depth thresholdi ne ,moraju biti isti
sto se optimizacije toga tice ako nije dovoljno brzo racnanje mean-a nadji neku rekurzivnu (mozda cak decaying?) varijantu
nadam se da sam uspeo da razjasnim, ako isam pisi, daj primere tackica, pa da nakuckam kod

[gorankg]

Ako se sećaš pričao sam ti da sam imao problem sa pronalaženjem kružnica na fotografiji. Moj je hardver bio još siromašniji i nisam mogao čak ni jedan frejm u RAM da gurnem nego onako kako dolaze linije sa kamere radim detekciju. Dok nismo angažovali i platili nekog lika da nam napravi algoritam i softver to nikako nije davalo 100% dobar rezultat. Bio je OK moj algoritam ali pošto je rezolucija bila jadna dešavalo se da omane. Njegov softver nikad! Kad sam kopao po njegovom kodu i literaturi shvatio sam da je čovek primenio neki od klasičnih algoritama koji se inače primenjuju u Computer Vision. 
E sad, tebi na RPI može da radi OpenCV pa što ne probaš sa njim. Kamera ili Lidar mislim da je skoro svejedno odnosno OpenCV bi trebao da radi i sa lidarom. Možda eventualno budeš kratak sa vremenom obrade to nisam siguran.

[mikikg]

Evo kako to izgleda u GUI u 2D projekciji, na primer ovde su samo dve tacke detektovane (tik jedna uz drugu) u zelenoj zoni i to je minimum koji treba da podrzi masina, ove sporne "noise" tacke se pojave bilo kad bilo gde i to samo jedna i ako je ne filtriram a pojave se u zelenoj zoni napravi povecu pometnju jer je to signal za PID koji vozi nekih 30+kW motor : )

[Braca]

Miki, problem prepoznavanja anomalnih vrednosti uopšte nije jednostavan, tako da ne postoje univerzalna rešenja.
Pre svega, neophodno je prikupiti determinističke, tzv. a-priori, informacije o procesu merenja, tj. podatke koji se od jednog do drugog prolaza relativno malo menjaju, tako da se mogu upotrebiti kao fiksni deo modela.
Procena očekivane vrednosti sledećeg mernog rezultata u nizu se onda vrši na osnovu odstupanja od modela, i to je najjednostavniji slučaj.

Ako se procena validnosti vrednosti merenja s indeksom (i) zasniva na nekom modelu iz prethodnih podataka (i=0:i-1), onda srednja vrednost uzastopnih razlika prethodnih merenja predstavlja dosta dobar estimator. U primeru koji si naveo, uzastopne vrednosti razlike izmerene daljine y(i) - y(i-1) će biti +300 i -400 (pišem "y" umesto "daljina"), što daje srednju vrednost od -100, koja onda predstavlja očekivanu vrednost razlike y(3)-y(2). Ta razlika je 900-1400=-500, i ona u odnosu na -100 očigledno predstavlja anomaliju.

Ovo gore je samo primer jednog jednostavnog estimatora i naveo sam ga kao ilustraciju načina razmišljanja.

Ako mi pošalješ par setova izmerenih rezultata možda ću biti u stanju da uradim nešto više.

Pozdrav

[mikikg]

Braco, dostavicu ti par setova malo kasnije, mada realno nisu toliko reprezentativni. Kao sto vidis u screenshot tu ima dosta tacaka ali su bitne samo one koje su u zelenoj zoni interesa, samo me te tacke interesuju a one pak su malobrojne, zadesi se tu da ima do recimo 15-ak tacaka.

Poenta celog ovog procesiranja je da mi da kao rezultat finalno rastojanje objekta po Y osi, dakle sve je sublimirano u jedan broj koji se salje dalje PLC-u.
U PLC-u postoji neka vrsta filtriranja tako sto prati delta-rastojanje izmedju tacaka i ako mnogo odstupa ta vrednost se ignorise i uzima se predhodna koja je bila, to sprecava trzanje/cimanje motora.

---

Hajde malo da zakomplikujem vec komplikovanu situaciju

Generalno lidar vraca vise informacija o pojedinacnim tackama, pored rastojanja dobije se jos nekoliko parametra, na primer drugi je rastojanje koji se racuna na prvom echo-u, pa tu ima i RSSI nivo (jacina signala) za prvu i drugu izmerenu razdaljinu.
Ja u ovom trenutku uzimam samo prvu izmerenu daljinu i ostale podatke o tackama ignorisem.
Ne znam da li po tom pitanju moze nesto da se uradi, da li tu pomazu ovi dodatni podaci.

Konkretan senzor je Sick LMS500 Pro, papreno skup senzor, kosta odprilike kao dobar polovan Saab + dobar polovan Volvo + jedno 3 Jugica
PDF za taj senzor ima ovde:
https://www.sick.com/media/docs/4/14/514...037514.PDF

[mikikg]

Hmm, ovaj matetmaticki problem je ustvari pitanje na konkursu za programere kod Amazon-a : )

Find length of the largest region in Boolean Matrix

Consider a matrix with rows and columns, where each cell contains either a ‘0’ or a ‘1’ and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. If one or more filled cells are also connected, they form a region. find the length of the largest region.

https://www.geeksforgeeks.org/find-lengt...an-matrix/

Examples:

Input : M[][5] = {
                  0 0 1 1 0
                  1 0 1 1 0
                  0 1 0 0 0
                  0 0 0 0 1 }
Output : 6
In the following example, there are
2 regions one with length 1 and the
other as 6. So largest region: 6

Input : M[][5] = {
                  0 0 1 1 0
                  0 0 1 1 0
                  0 0 0 0 0
                  0 0 0 0 1 }
Output: 6
In the following example, there are
2 regions one with length 1 and the
other as 4. So largest region: 4

Koliko razumem isti je problem samo je kod mene drugacija projekcija tacaka (koju sam odradio) i treba mi 1 x N matrica umesto M x N
Ovo nalazi najveci region i onda znam da mi je to objekat koji se prati, sve ostalo su smetnje.

[mikikg]

Code:

#include <stdio.h>

int main() {
    char string[100] = "Hello Kurnool";
    int i, start = 0, longest = 0, longest_pos = 0;

    for (i = 0; string[i] != '\0'; i++) {
        if (string[i] == ' ') {
            start = i + 1;
        } else {
            if (i - start > longest) {
                longest = i - start;
                longest_pos = start;
            }
        }
    }   
    printf("longest word: %d letters, '%.*s'\n",
           longest, longest, string + longest_pos);

    return 0;
}

Hmm, mozda je ovo resenje!
Ovo trazi najduzu reč u stringu, stim sto cu ja umesto stringova i mojih tacaka samo da kazem na primer "T" gde mi je tacka i da stavim " " gde mi je praznina i tako da nadjem najduzi niz, njegovu pocetnu poziciju i njegovu duzinu, onda te rezultate uzmem u dosadasnji racun za trazenje minimuma i to bi bilo odprilike to!

[mikikg]

Radi tako, prepravio sam 5 linija mog coda-a

Evo konkretno, tri vrlo bliske grupe tacaka ali ova koju je markirao je ipak najšira i ispravno je izabrao bas taj skup.

[rane_nbg]

Svaka cast

Sve dokle u okolini lidara ne bude nekih malih predmeta ili ostrih ivica, trebalo bi da radi. Ravni i veliki predmeti se lako prepoznaju, dok manji mogu mozda biti problem.

Cisto radoznalosti radi, gde ce se postavljati taj lidar, tj. sta mu je okruzenje i sta 30kW motor pokrece? Self driving car?

[Khadgar2007]

Kada dobiješ kaznu za prebrzu vožnju onda ćeš saznati di se nalazi i čemu služi. 

[mikikg]

Heh, nije autonomno vozilo mada je ovaj Lidar predvidjen i za takve stvari.
U pitanju je fizicki simulator "necega", ne mogu vise detalja da dam u ovom trenutku, kada bude sve proradilo bice slika i video zapisa sta i kako radi ...

[Braca]

Miki, raduje me da si na dobrom putu.
Na žalost, ja zbog porodičnih obaveza ovih dana kod kuće samo spavam, tako da nije bilo šanse da se dalje pozabavim ovom stvari.

[mikikg]

Zanimljivo, sve ovo sto smo pricali oko procesiranja sa Lidara je stalo u nekih 20-ak linija C++ code-a.
Ova "data." struktura je ustvari shared-memory instanca, postoji samo jedna u programu tj sistemu, to je najbrzi nacin za inter-proces komunikaciju i razmenu podataka na *nix. Drugi programi mogu da citaju i pisu u tu data strukturu isto tako, sve sto treba je da se samo upotrebi zajednicki header fajl koji definise strukturu i to se zakaci na /dev/shm pod nekim predefinisanim indexom, to radi bas dobro!
Takodje posto postoji samo jedna instanca tog memoriskog objekta, to je prakticno i najefikasnije resenje po pitanju zauzeza RAM-a, dakle nema drugih kopija, sve se radi preko pointera koji ukazuje na tacnu memorisku lokaciju.
U mom slucaju je ta data struktura velika oko 30kB sto je zanemarljivo malo na *nix koji imaju obicno >1GB RAM, nema "curenja memorije" i ostalih problema. Dodatno cela struktura moze da se smatra kao fajl i da se u taku procita ili kopira u na primer backup fajl i da se kasnije vrati.

Vise o tome ovde:
POSIX Shared Memory in Linux
https://www.softprayog.in/programming/in...y-in-linux