Najpre, zdravo zemljace!

Kao drugo, zaboravi na primenu svojih nepravilnih poligona u video nadzoru, osim ako dobro znas sta radis, jer je ovo sto te muci najmanji od problema.

Ali da krenemo redom.

Efikasno resenje problema koje na zalost ne mogu da ti prekucam jer je dugacko nalazi se u knjizi: Udi Manber, "Algorithms: a Creative Approach"

Tvoj problem nije bas dobro definisan. Naime kazes da su sve tacke u poligonu crne. Zar nije onda dovoljno da proveris da li je tacka koja te zanima obojena u crno? Ali, pretpostavicu da si se toga vec setio i idem dalje.

Sto se trougla, odnosno svih _konveksnih_ poligona tice, stvar je prilicno jednostavna. Uslov koji te zanima je sledeci:

Tacka je unutar poligona ako se nalazi na istoj strani svake od stranica kao i teziste poligona.

Kako to ispitati?

Pa, pronadjes prvo jednacinu svake od stranica. Ako su tacke na stranici (x1,y1) i (x2, y2), resis sistem jednacina:

a x1 + b y1 + c = 0
a x2 + b y2 + c = 0

pri cemu posto imas 2 jednacine i 3 nepoznate (koeficijente prave a, b, c), usvojis jednu od vrednosti, recimo c = 1 i dalje resavas.

Kada si nasao a, b, c, onda gledas ovako: samo na samoj pravoj ova jednacina vazi. Za sve tacke (x,y) koje su van prave je vrednost izraza

a x + b y + c

ili manja ili veca od nule. Pri tome za sve tacke sa jedne strane prave vrednost je veca od nule, a za tacke sa druge strane vrednost je manja od nule.

Za konveksan poligon teziste se nalazi u tacki cija je svaka koordinata aritmeticka sredina koordinata odgovarajucih temena. Dakle:

za svaku tacku (x, y) koju zelis da ispitas proveris da li ako se zameni u svaku od gornjih jednacina za svaku stranicu daje broj koji je istog znaka kao kada se u odgovarajucu jednacinu ubaci teziste poligona. Ako je odgovor da, onda si utvrdio da je tacka u poligonu.

Za nekonveksan poligon stvari se doooosta komplikuju, tu vec treba da radi knjiga.

Ideja je da se iz tacke koja se ispituje povuce poluprava i izbroji broj preseka sa stranicama poligona. Ako je broj preseka neparan, tacka je unutar poligona. Ako je paran, tacka je van poligona. Poligon moze i da ima stranice koje se samopresecaju i uopste da bude vrlo komplikovan. Cika Udi Manber to resava vrlo efikasno u svojoj knjizi.

poz.

Zdravo i tebi Filipe !

Bas volim kad neko detaljno odgovori, a bogami dobru si mi ideju dao. Pocinjem da je sprovodim u delo ...

Ono sa bojom pixela - ponavljam da imam za ulaz samo temena poligona, a pixeli za koje se odredi da su unatar njega fuuncija treba da ih oboji u crno (crni na slici su znaci samo pixeli koji odrejuju temena a ja treba da filujem u crno ostale pixele unutar poligona)

Mada to imam vec razradjeno (manje vise radi na gurku), pa sam hteo da vidim jel neko zna jos neku efikasniju foru, u stvari matematicku.

A i ti izgleda ceprkas po video nadzoru. Jel pises neki softver za to kad kazes da je ovo najmanji deo u celom problemu ?
Jel si koristio VideoForWindows mozda?
Ja sam skoro sve vec uoblicio, sada samo da dodam te 'nepravilne regione' - do sada su bili samo pravougaonici.

Imao sam i problema sa brzinom uporedjivanja frejmova, ali mi to resise Dragi Tata i Ivan Dimkovic, pa bas sada ceprkam po nekom dll-u koji mi uporedjuje i xor-uje fejmove, ali mi nesto bas i ne ide sa ovim VC++, posto sam za njega bas pocetnik.

Ajde ako mozes kazi barem jel ima negde da se downloaduje ta knjizica, ili neki deo od nje - mora da je mnogo dobra (kopao sam po netu i video ko je cika prof. dr. Udi Manber)

Pozdrav

Ono sto tebi treba je Matematika 1 za bilo koji tehnicki fakultet, pa onda okrenes poglavlje Analiticka geometrija i utvrdis da je znanje matematike ipak potrebno za programiranje...

Ja bih samo dodao da je postavka problema MNOGO idealizovana... :( U praksi nikada neces imati samo "nule i jedini", u praksi su slike ditherovane, rasurene blablabla, i trebace mnogo vise problema da se resi nego problemi sa konveksnim i nekonveksnim poligonima...

Jedna od ideja kako da izbegnes razne varijante algoritama za plotanje linija po bitmapama, itd... Jedno od resenja je da

- Za crtanje geometrijskih figura kostistis Win32 GDI funkcije
- To ces raditi na 1-bitnoj ravni

A onda ces tu ravan jednostavno koristiti za proveru da li je tacka u nekom trouglu/n-touglu ili ne tako sto ces ispitati da li je ona 0 ili 1

Samo jedna "prečica". Postoji GDI funkcija

PtInRegion

Koja proverava da li je tačka unutar poligona (konveksnog ili nekonveksnog, svejedno) ili ne. A za solidan tutorijal o algoritmima u kompjuterskoj geometriji, pogledaj

http://geometryalgorithms.com/

Posto je tema izgleda intersantna, resih da detaljno opisem problem.

Detaljan opis i pitanja zakacena su uz poruku.

Dakle ovako.

Vec si primetio da tvoje slike 'pate' od suma. To se ne moze izbeci,
naprosto priroda radi protiv tebe. Sumovi su neodvojivi deo svakog
merenja, pocev od jednostavnog merenja duzine stola pa do
komplikovanijeg merenja tipa analize slike sa kamere.

Ako vec ne mozemo da ga se oslobodimo, mozemo bar da probamo da ga
procenimo pa da ga onda 'ubijemo' sa slike. Najveci problem je
napraviti detekciju pokreta koja ce da bude robusna, tj. da se ne
zbuni usled nekih nepredvidjenih ulaza, trzaja kamere, vetra, promene
uslova osvetljenja i sta ti ja znam.

Jedna od metoda za otklanjanje suma poziva u pomoc statistiku. Za sada
posmatramo samo jedan piksel na slici. Posto je slika u tvom primeru
stacionarna (srednja vrednost piksela je ista tokom dugog vremena, jer
posmatras scenu koja ne bi trebalo da se promeni), a sum na jednom
pikselu je stacionaran slucajan proces. Ovo je neophodna pretpostavka,
u opstem slucaju ne mora da bude tako, na primer televizijska slika
na kojoj se stalno nesto menja i te kako _nije_ stacionaran proces!

Napominjem da iako model RGB za boje nije ortogonalan, ovaj metod moze
da se dosta dobro primeni.

Prema centralnoj granicnoj teoremi, srednja vrednost jednog piksela
u vremenu konvergira ka stvarnoj, a varijansa, tj. odstupanje od prave
vrednosti usled suma smanjuje se sa kvadradnim korenom broja piksela
koji su ucestvovali u usrednjavanju. Tako na primer, ako je x[k]
intenzitet piksela u vremenskom trenutku k, tada u trenutku N vrednost

$$ xs[N] = 1/N \sum _i=0^{N-1} x[N-i] $$

tj. srednja vrednost poslednjih N vrednosti piksela u trenucima
semplovanja ima sum koji je $\sqrt N$ puta manji po snazi nego sum u
svakom pojedinacnom trenutku. U teoriji, ako bismo semplovali
beskonacno mnogo slika i izracunali gornju sumu, dobili bismo tacnu
procenu prave vrednosti datog piksela. U praksi, dovoljno je sabrati
onoliko clanova koliko je dovoljno da snaga suma padne ispod nekog
nivoa, recimo nivoa LSB-a u broju x[k]. Ako usvojis odsecanje vise
bita, onda mozes da postavis veci prag za odbacivanje suma i da
skratis gornju sumu pa samim tim ubrzas racunanje. U praksi se ovo
izvodi tako sto procenu $\hat x[k]$ za svaki piksel racunas prema
formulici:

$$ \hat x[k] = 1/N (x[k] - x[k-N]) $$

sto ce ti biti procena za piksel $x[N]$ u trenutku $N$, a u cemu ce
oni koji znaju prepoznati filter propusnik niskih
ucestanosti. Pretpostavka je naime da je sum uglavnom sadrzan u VF
spektru signala. To je prakticno ispunjeno samo ako mozemo da snimamo
veliki broj slika u sekundi ('veliki broj' zavisi od primene!) jer
inace sum na slici ostaje pa ostaje.

Problem sa ovim je sto se sa porastom N povecavaju zahtevi za
memorijom. To je problem kod svih filtara ovog tipa (tzv. FIR filtri)
ali je cena koja mora da se plati za neizoblicen signal procene,
apsolutnu stabilnost filtra i imunost na sum.

Druga varijanta je tzv. IIR filtar koji se koristi slicnom idejom, ali
koji postepeno 'zaboravlja' frejmove koji su se desili davno:

$$ \hat x[k] = - \alpha \hat x[k] + \alpha x[k] $

gde je $\alpha \in (0, 1)$ koeficijent 'zaboravljanja'.

Treca varijanta je koriscenje tzv. Kalmanovog regulatora, sklopa koji
eliminise sum u signalu tako sto pravi procenu njegove vrednosti koja
je 'optimalna prema srednjekvadratnoj gresci' iz cega se ne moze
zakljuciti mnogo osim da volim da se gadjam terminima. :)

Zaozbiljno, probaj da na netu potrazis kljucne reci 'Kalman
regulator', teorija je prilicno za*ebana ali bi trebalo da ponegde na
kraju clanka izvuces formulicu ili recept kako se to tacno radi. Da
se ne zavlacim u objasnjenja, to je verovatno ono sto ti je potrebno,
odnosno ono sto se izmedju ostalog koristi u profesionalnim sistemima
za nadzor.

U medjuvremenu ce ti filtriranje slike odraditi i FIR ili IIR filtri.

Kada to resis, sledeci problem koji treba napasti je prostorno
filtriranje slike, tj. ubijanje suma usled razlika susednih piksela i
'jittera'.

Uzgred, vec se opasno priblizavamo racunu koji hardver opste namene
nece stici da uradi u realnom vremenu. Oprez.

poz.

filimil:
Tacka je unutar poligona ako se nalazi na istoj strani svake od stranica kao i teziste poligona

Dakle matematicki deo, tacka x, je unutar konveksnog poligona P(p1,...,pn)
ako se moze dobiti kada se temena poligona opterete pozitivnim tezinama
(l1,...ln ) cija je suma 1 = l1+l2+ ... + ln.
Ako ih opteretimo jednakim tezinama dobicemo teziste l1=l2=...=ln

Dakle akko:
x=l1*p1 + l2*p2 +.... ln*pn, l1+l2+...+ln=1// sistem jednacina (2,3)

bar teziste mozes lako dobiti:
t=1/n*p1+1/n*p2+ ... +1/n*pn

Sto se tezista tice, stvar je OK.

Medjutim, mislim da je sa ovim postupkom problem bar to sto je$ O(n^3)$, jer ukljucuje resavanje sistema linearnih jednacina (kojih ima manje nego promenljivih, uzgred, s obzirom da su $x$ i $p_i$ poznate velicine a $l_i$ nepoznate). Ne znam da li postoji precica.

poz.

Evo REKURZIJE:
1.Ako je dim(Poligon)=3 ispitujemo da li se tacka nalazi u njemu
2.Ako je dim(Poligon)>3 uzimamo jednu tacku i ispitujemo da li se
tacka nalazi u trouglu oko nje, ako se ne nalazi
onda iz Poligona izbacujemo datu tacku i
vracamo se na slucaj 1.

A evo i koda:

class Tacka {
public:
int x;
int y;
Tacka operator+(const Tacka&);
Tacka operator-(const Tacka&);
};

bool inPoly(Tacka x,Tacka* p, int n) // proverava da li se
// tacka x nalazi u poligonu p od
// n tacaka
{
if (n<3) return false;
if (n==3) {
Tacka p2=p[1]-p[0];// transliramo trougao u
Tacka p3=p[2]-p[0];// koordinatni pocetak
//resavamo sistem
float s=(x.y-(p1.y/p1.x)*x.x)/(p2.y-(p1.y/p1.x)*p2.x);
float v = (x.x - s*p2.x)/p1.x;
//uslov da se tacka nalazi unutar trougla
if(s<0||v<0||s+v>1) return false;
else return true;
}
if (inPoly(x,p,3)) return true;
p[1] =p[0]; // izbacujemo srednju tacku a ne ivicnu
return inPoly(x,p+1,n-1);
}

AAAAAuh !

Filipe, bas mi je, moram da priznam zastao dah, dok sam citao tvoj odgovor !
Inace za sada ne znam sta da ti kazem, osim HVALA !

Malo ce duze da prodje dok ukapiram sve ove terorijske postavke koje si izneo, a jos duze dok ih implementiram.

Ali pricacemo jos, sigurno ...

mali dodatak,
kod predhodne funkcije poligon ce bit unisten posle poziva
funkcije tako da je neophodno uraditi jedno od sledecih
1.iskopirati poligon pre poziva f-je
2.u svakom pozivu praviti novu kopiju poligona
3.pri kraju koda dodati
int temp = p[1];
p[1]=p[0];
p[0]=p[1];
4* Napraviti klasu poligon sa odgovarajucim copy konstruktorom

Ono sto sam zapravo hteo da kazem jeste da problem koji si napao nije nesto sto se moze resiti za jedno vece programiranja u VB-u. Potrebno je preturiti i malo knjiga jer je dosta veoma pametnih ljudi oborilo dosta drveta za hartiju da bi dosli do zakljucaka koje sam ti onako knjiski nabrojao.

Inace ovo sto sam ti napisao je sam pocetak, koji je dovoljno razumljiv da moze da se pokaze studentima. Metode za stvarno robusnu detekciju koriste 'crnomagijske' metode koje stvarno nisam u stanju da razumem. Neki tipovi sa Caltecha cak umeju da prepoznaju i prebroje ljude na kadru. Imaju i sajt (potrazicu ga kasnije, ako je jos tu, dobijate link) sa radovima. Za mene je bio zaista previse, ali mozda se posetioci foruma ne predaju tako lako.

poz.

I ja sam nasao na netu dosta implementacija Kalmanove terorije, ali toliko toga ima da ni sam ne znam odakle da pocnem. Najgore je to sto prosta implementacija izgleda ne postoji, pa cu morati prvo da konsultujem neke drugare sa PMF-a...

Nesto najasnije, sto sam do sada nasao je zakaceno uz poruku.
Koga zanima, nek pogleda.

Link:

http://www.vision.caltech.edu/html-files/overview.html

Dobar ti onaj sajt ...