Algoritam za minimum funkcije dvije varijable (Programiranje) @ Bug.hr Forum

DigiMagic

17 godina

neaktivan

offline

pon 12.12.2011 19:18

Odgovori Citiraj

Algoritam za minimum funkcije dvije varijable

Prilično sam googlao, ali ne mogu nikako pronaći...

Imam dva polja koja sadrže mjerenja sa senzora, recimo da se zovu a[256] i b[256]. Želim naći takve x i y, da je za njih funkcija (a[x] , b[y]) najbliže zadanoj vrijednosti c. U idealnom slučaju dakle funkcija ( a[x], b[y] ) = c, međutim prihvatljiva je i određena greška jer su x i y cijeli brojevi, a funkcija() izračunava floate.

Najgluplja varijanta da provjerim svih 256*256 mogućnosti mi nije ok jer će se stvar vjerojatno kasnije morati izvoditi na mikrokontroleru ili sličnom slabom procesoru.

Kako mogu najbrže naći x i y? Generalno ću imati dosta dobre početne vrijednosti i funkcija() bi se trebala ponašati ok (glatko, bez čudnovatih skokova i sl.).

Google čini se da preporuča Newton-Raphson metodu, međutim za nju bih trebao poznavati derivaciju funkcije, a to nemam... Mislio sam probati nekakvo binarno približavanje, da postavim x i y na 128, pa probam +64 i -64 i uzmem najbolji rezultat, pa od toga -32 i +32 i uzmem najbolji rezultat, itd, ali nisam siguran je li to najoptimalnije...

Moj PC

trajni link

0 0 hvala 0

workload

15 godina

neaktivan

offline

sri 14.12.2011 23:09

Odgovori Citiraj

Re: Algoritam za minimum funkcije dvije varijable

Ovaj tvoj alogoritam opet će dovesti do n*n(iako ga nisam potpuno skužio, mislim da znam što si htio postići).

Uglavnom da bi ostvario nešto slično oba polja moraju biti sortirana.

I onda krećeš npr. od a[0] i b[255], ako je vrijednost prevelika uzimaš a[0] i b[254] ako je premala onda [a1] i b[255] i tako dalje uspoređuješ i odlučuješ da li ćeš ići s desna ili lijeva. Na ovaj način ćeš n*n provjera dostići samo u najgoroj situaciji, kada je rezultat a[255], b[0]. (možda se još netko javi sa boljom idejom).

Ali da li ćeš ovo moći implementirati zavisi o ponašanju funkcije.

Znači bitno je da li povećanjem vrijednosti varijabli vrijednost f(x,y) povećava ili smanjuje.

f(x,y)>f(x,y+1) ili je f(x,y)<f(x,y+1) - to isto i za x.

Ali je jako bitno koliko utjecaja na rezulta funkcije ima varijabla x, a koliko y.

Npr. za funkciju tipa f(x,y)=x^4 + sqrt(y)

Ili je možda funkcija ciklička, npr. f(x,y)= (x*y)%255

trajni link nadporuka

0 0 hvala 0

DigiMagic

17 godina

neaktivan

offline

pet 16.12.2011 18:50

Odgovori Citiraj

Algoritam za minimum funkcije dvije varijable

Nisam razumio, u kom smislu bi polja trebala biti sortirana? Tvoj algoritam mi izgleda ok, za neke slučajeve sam siguran da je brži od mog, moram još promisliti...

Radi se o jednoj specifičnoj vrsti spektrofotometra, ono što proračunavam su zapravo (korekcije grešaka za) boje u xyY sustavu.

Moj PC

trajni link

0 0 hvala 0

workload

15 godina

neaktivan

offline

sub 17.12.2011 13:35

Odgovori Citiraj

Re: Algoritam za minimum funkcije dvije varijable

Pa trebalo bi ta polja soritirati prije pretrage( po ulaznim ili silaznim vrijednostima, svejedno), jer inače nema algoritma koji bi mogao upotrijebiti a da nije uspopoređivanje svakog člana sa svakim.

Odnosno ako polje nije sortirano (npr. a1=1, a2=2, a3=8, a4=4, a5=3, a6=9, a7=5....) kod pretrage nikada nećeš znati da li je sljedeći član veči ili manji pa češ morati proči cijelo pollje.

trajni link nadporuka

0 0 hvala 0

bed

16 godina

neaktivan

offline

sub 17.12.2011 14:41

Odgovori Citiraj

Re: Algoritam za minimum funkcije dvije varijable

Što ti senzori mjere?

Dobio sam dojam da tražiš kromu koju uspoređuješ s xyY skalom? Što su x i y, 256 mogućnosti - 8bit šta? Daj malo proširi priču, možda postoji kakvo jednostavno rješenje..

bedsoft.net

trajni link nadporuka

0 0 hvala 0

DigiMagic

17 godina

neaktivan

offline

sub 17.12.2011 19:41

Odgovori Citiraj

Re: Algoritam za minimum funkcije dvije varijable

bed kaže...

Što ti senzori mjere?

Dobio sam dojam da tražiš kromu koju uspoređuješ s xyY skalom? Što su x i y, 256 mogućnosti - 8bit šta? Daj malo proširi priču, možda postoji kakvo jednostavno rješenje..

Senzori mjere Y za poznate x i y (prema CIE 1931). Imam više poznatih boja x,y (postoji posebna elektronika i filteri koji brinu o tome), te za svaku vektor Y pod različitim početnim uvjetima. Sve skupa služi za kalibriranje projektora, međutim kako točno, to ne bih smio reći - radi se o proizvodu koji je u razvoju.

@workload: u pravu si za sortirana polja. Ne bi smio biti problem, sva su monotono rastuća.

Moj PC

trajni link nadporuka

0 0 hvala 0

bed

16 godina

neaktivan

offline

sub 17.12.2011 22:29

Odgovori Citiraj

Re: Algoritam za minimum funkcije dvije varijable

Provalio sam te, ode ideja dođavola.. :o)

Ti mjeriš osvjetljenje kojeg uspoređuješ s zadanim parametrom s ciljem kalibracije / pronalaska odstupanja od zadanog, ako sam dobro shvatio? A problem se sastoji u tome da imaš samo informaciju o osvjetljenju Y sa senzora, a fali ti x i y informacije - kroma do kojih želiš doći nekom aproksimacijom? Ako je tako, nisam siguran u točnost te aproksimacije. Nemaš poznat odnos x i y, što će rezultirati (barem mi se ovako napamet čini, možda sam u krivu) s više mogućih rješenja x i y koji zadovoljavaju uvjet.

Enivej, nemam neku pametnu ideju kako to rješiti tu usporedbu osim prevrtiti sve mogućnosti, tim više što ne znaš odnos x i y, pa u slučaju nekakvog 'binarnog djelila' ne znaš u kojoj polovici je tvoje rješenje. Btw nevezano za temu, imaš neki projektor i server na 'stolu' za isprobavanje? Može li se kako (za pivu) isprobati funkcionalnost DCP-a?

bedsoft.net

trajni link nadporuka

0 0 hvala 0

DigiMagic

17 godina

neaktivan

offline

ned 18.12.2011 1:57

Odgovori Citiraj

Re: Algoritam za minimum funkcije dvije varijable

bed kaže...

Provalio sam te, ode ideja dođavola.. :o)

Ti mjeriš osvjetljenje kojeg uspoređuješ s zadanim parametrom s ciljem kalibracije / pronalaska odstupanja od zadanog, ako sam dobro shvatio? A problem se sastoji u tome da imaš samo informaciju o osvjetljenju Y sa senzora, a fali ti x i y informacije - kroma do kojih želiš doći nekom aproksimacijom? Ako je tako, nisam siguran u točnost te aproksimacije. Nemaš poznat odnos x i y, što će rezultirati (barem mi se ovako napamet čini, možda sam u krivu) s više mogućih rješenja x i y koji zadovoljavaju uvjet.

Enivej, nemam neku pametnu ideju kako to rješiti tu usporedbu osim prevrtiti sve mogućnosti, tim više što ne znaš odnos x i y, pa u slučaju nekakvog 'binarnog djelila' ne znaš u kojoj polovici je tvoje rješenje. Btw nevezano za temu, imaš neki projektor i server na 'stolu' za isprobavanje? Može li se kako (za pivu) isprobati funkcionalnost DCP-a?

Može kad/ako nabavim nešto te vrste - zasad sve radimo s consumer opremom. Ali planiramo imati i consumer i profi verzije pa ćemo vjerojatno morati posuditi nešto za testiranje...

x i y imam poznate... da ne kompliciram, otprilike se radi o ovome http://www.cinetal.com/products/dolby3D.asp, ali drukčija, preciznija izvedba. Nezgodacija je što ne postoje direktna mjerenja ili formule nego ove greške koje moram ukloniti ili prikriti, moram iterativno naći vrijednosti za kompenziranje... uglavnom mislim da znam sad što trebam računati.

Moj PC

trajni link nadporuka

0 0 hvala 0