Bildesammenligning i PHP? Mulig?

[haavis]

Hei.

Jeg har utviklet en helt greit bildedatabase på nettet til personlig
bruk. Så begynte jeg å eksperimentere med tanken om et spesielt søk,
nemlig å søke etter bilder som ligner ett annet bilde!

Altså, at man faktisk ser at det bildet forestiller ligner på et annet
bilde!

Jeg vet jo at det finnes mange programmer som kan gjøre dette med
bilder på harddisken, men er dette mulig å implementere i PHP?

En metode som så ut til å være grei er at alle bilder får sin egen
Fourier-rekke generert. Dermed kan man sammenligne begynnelsen av
denne med andre bilder for å se om de ligner.

Men jeg har ingen anelse om hvordan man gjør dette med bilder, og enda mindre å gjøre det i PHP!

Finnes det en enklere metode? Noen nevnte å bruke GD for å lese inn
fargeverdien til en del (mange?) piksler i et bilde og sammenligne
disse med neste bilde med en feilmargin på f.eks. 3%.

Men dette høres tidkrevende ut.

Er det andre måter å lagre unike signaturer for et bilde som kan
sammenlignes med andre?

Tusen takk for svar og forslag. Kom med hva som helst!

PS: Jeg har nå laget en slag implementasjon av dette, som gjør følgende:

Oppretting / Signatur:
- Lager en thumbnail med størrelse 15x15
- Lager et array med fargeinformasjon for hvert piksel
- Lagrer arrayet i databasen

- Sammenligning
- For hvert bilde som skal sammenlignes leses fargearrayet inn
- Hvert piksel blir så sammenlignet
--- Har det røde i pikslene et forhold innenfor en viss grense gis pikslen verdien 1
--- Dette gjøres for grønt og blått
--- Får verdi 1, får hele pikselet verdi 1
- "Pikselverdiene" legges sammen og deles på 225 (15 x 15)
- Er denne verdien større enn .80 antas det at bildet er likt.

Dette fungerer overraskene bra noen ganger, men dårlig andre ganger. For bilder der det er himmel øverst og gress nederst finner den en del like bilder. Men det kan ikke være stor forskjell på bildene. De kan ikke ha annen vinkel eller motivene kan ikke ha stor innbyrdes forskjell.

Jeg tenkte da videre på å kanskje ta "midten" av referansebildet (x * x antall piksler) og sammenligne denne "boksen" på alle steder i de andre bildene, kanskje det gir bedre resultat.

Uansett - vil gjerne ha kommentarer og forslag her! Hva som helst, og jeg blir kjempeglad!

[petterg]

Du kan bruke imagemagick til å konvertere til et ukomprimert bildeformat som er lettere å jobbe med, og dermed lese denne inn i et array byte for byte. Og så gjøre de matematiske beregningene du vil på dette arrayet.

 

Sansynligvis vil du være bedre tjent (ytelsesmessig) med å gjøre dette i C elns, men metoden å gjøre det på er i prinsipp den samme.

 

(Har bare gjort dette med MatLab, og der finnes det funksjoner for å lesse diverse bildeformater direkte til array, så jeg slapp å tenke på dekoding.)

[El Nino]

15x15 pixler er litt snaut når man skal sammenligne bilder. Her burde den økes til minst 50x50 pixler. Men det er min mening.

 

En tanke jeg kom på var å legge hver pixelverdi til sammen i hel en streng, slik at man hadde en lang streng som inneholdt hver eneste pixelverdi. Deretter kjørt denne funksjonen http://no.php.net/similar_text for å sjekke bildene opp mot hverandre..

 

Var bare en tanke..

 

El Nino

[petterg]

Den similar_text saken vil bli veldig følsom for lys endringer. Tror nok man bør jobbe i frekvensplanet.

Evt prøve på wavelet.

 

Man kan også bruke folding for å detektere kanter.

Prof. Manjunath ved UCSB (ucsb.edu) hadde et slik prosjekt for noen år siden. Har ikke tid til å finne fram til det nå, men søk litt, så kanskje du finner....

[haavis]

Takk for raske svar.

 

Har også lyst til å jobbe i frekvensplanet som nevnt, siden man da meget enkelt kan gjøre sammenlignigner og siden det også tar mindre plass. Dessuten blir sammenligningene mye bedre.

 

Nå har jeg ikke prøvd å satt meg inn i matten bak f.eks. wavelets, men matematikken bak Fourier-rekker kjenner jeg til. Jeg vet at det skal være mulig å omgjøre et bilde til en Fourier-rekke med såkalt Fast Fourier Transform, og så samemnligne de x første leddene for å finne rimelig like bilder. Og en slik sammenligning vil ikke være så følsom som små endringer i farger, lys og annet småpjusk

 

Lurer på om det er noen som har prøvd på dette tidligere i PHP, eller om jeg er virkelig den eneste?

 

Når det gjelder direkte fargesammenligning er denne ganske grov. Jeg ser at det kan forbedres noe, men det er begrenset hvor mye. Hvis man økte pikslene til 50 x 50 ville det føre til 2500 piksler for hvert bilde. I en bildedatabase av en viss størrelse ville det føre til uhorvelige mengder data som skal sammenlignes, og det uten at resultatet blir noe kjempebra heller.

 

Det hadde vært veldig spennende å få til noe der man regnet ut frekvensområdet til bildet, ala Fourier eller Wavelets. Ser for meg at kanskje fourier rekker er noe jeg vil satse på siden det både brukes i bildesammenligning og det er matematikk jeg kjenner til!

 

Igjen - takk for god respons

[Nervetattoo]

Jeg har sett en stor diskusjon på et annet forum rundt dette hvor noe lignende ble laget.

Jeg prøvde å finne det igjen men kunne ikke helt huske hvor jeg hadde lest det så det ble desverre med forsøket.

 

Jeg har tenkt å gjøre dette selv en gang i fremtiden, men per nå er bilder og php ikke min sterke side så jeg kan ikke hjelpe deg.

 

Men det er et veldig kult område, så jeg vil bare støtte deg i dette, stå på

[haavis]

Heisann : )

 

Ja, har blitt hektet på dette nå og føler at jeg ikke kommer til å gi meg før jeg får det skikkelig til. Synes det hadde vært utrolig morsomt hvis jeg hadde klart å implementere noe slikt. Skal lete litt videre, og eventuelt henvende meg til noen engelske fora for å henvende meg til et enda bredere publikum

 

Og jeg kommer selvfølgelig tilbake og poster eventuelle resultat senere

 

Tusen takk for støtte

[petterg]

Snakker om å forminske bildet.... NEI!

Kom deg i frekvensplanet, og kutt heller ut noen frekvenser.

 

For at dette skal virke kan du ikke lage en fourier-rekke. Du må lage et fourier-plan. Altså ta fourier transformasjonen i 2D. Du ender da opp med en matrise. (Slik fourier er det som er basis jpeg-kompresjon.)

Deretter kan du kutte ut første rad og første kolonne. (Disse inneholder nesten bare info om lysstyrke, og det er du absolutt ikke intresert i. Hvis du setter alle disse til middelverdien av resten av tallene i matrisen, gjøre en omvendt fourier og normaliserer, vil du ende opp med orginalbildet, hvor bare lysstyrken er føkka. (Hvis du bruker fargebilder, vil også fargene være føkka.)

 

Så må du se på hva slags info du har interesse av. Sansynligvis er det mye form og lite farge. Altså bør du ta utgangspunkt i svarthvit bilde for info, og evt legge på et grovt farge skjema. Dette gjøres ved først å konvertere fra RGB til Intencity-Hue-Saturation, før du tar fourier. (Lurer på hva resultatet hadde blitt om man hadde gjort om slik etter fourier.)

På hue og saturation kan du gjøre om til å bruke 4 bit pr pixel, slik at disse to kan slås sammen i en matrise med 8 bpp.

Hvis man kaller bitene for H4,H3,H2,H1 og S4,S3,S2,S1. For hver pixel setter du da f.x. sammen til S4,H4,H3,S3,S2,H2,H1,S1.

Da har du redusert til kun to matriser å ta fourier på: Intensity og hue-sat. Du har beholdt alle detaljer ang. form, men redusert med tanke på farge.

 

Så, i frekvensplanet, som sagt første rad og kolonne kan ryke å reise ang Intensity. Litt usikker på om man kan gjøre det sammen med Hue-Sat. Uansett, du kan nå, alt ettersom hvor mye detaljer du vil ta vare på, klippe bort X antall kolonner og rader i matrisa. De siste kolonnene/radene er de som har mest detaljer, så klipp bakfra. (den siste kolonnen/raden vil ofte bestå av nuller uansett.)

 

I frekvensplanet vil du stå igjen med tall med masse desimaler. Disse må du finne en egnet måte å sample til så mange bit du ønsker å ta vare på. (Ingen sa det var fornuftig å runde av til heltall!)

 

Her kan du finne mye intresant på fagfeltet:

http://www-iplab.ece.ucsb.edu/publications....htm#managingDB

Fant ikke tilbake til bildedatabase-søke-motoren som Manjunath jobbet på i 2001/2002, men den finnes sikkert fortsatt. Der tok man f.x. bilde av en sko, og ba systemet finne fram til de bildene som lignet mest... det kom endel sko, men også apelsiner og palmetrær blandet seg inn.

 

Jeg tror du vil tjene på å komme fram til hvordan det skal gjøres før du starter med å gjøre det i php. MatLab med imageprocessing toolbox er et veldig godt verktøy for slik eksprimentering.

[haavis]

Igjen takk for interessant svar. Tror også det å bruke frekvenser er den riktige veien å gå, siden piksel sammenligning - som nevnt tidligere - blir for grovt.

 

Har forstått fra andre kilder at man ender opp med et fourier-plan og ikke rekke.

 

Skal prøve å lese meg litt opp på det, og få det til på andre måte før jeg prøver å få det til i PHP. Du har gitt meg et godt utgangspunkt! Tror det kan bli spennende hvis man får dette til.

 

Selvfølgelig er dette et enormt fagfelt, og jeg har ikke tenkt å lage den mest avanserte gjenkjennelsesrutinen, men noe som fungerer bedre enn det jeg har nå i alle fall. Skal også se om jeg finner noe på skolebiblioteket her - det gjør det nok sikkert.

 

Interessant tema dette

[petterg]

Mange har prøvd dette ved bruk av fourier før. Ingen har fått det til ordentlig.

Hvis jeg skulle starta på no slikt nå ville jeg sett mer i retning av wavelet. Etter wavelet transform får du et bilde (high pass) som stort sett består av konturer. Altså man ser objektene, formene, men all info som farge og lysstyrke er borte.

Hvis man lager noe som følger sammenhengende linjer blandt disse konturene vil man muligens være i stand til å plukke ut objekter fra bildet.

Da kan oppgaven din bestå i å finne ut hvordan man skal kunne sammenligne objektene, i steden for å forsøke å sammenligne hele bilder, slik du må ved fourier. Du kan evt bruke fourier på objektene for å sammenligne dem.

Du sitter fortsatt igjen med for mye informasjon. Hadde man funnet en eller annen måte å beskrive / transformere objektene som fjernet informasjon om skalering og retning.....

 

Wavelet er mye enklere å implementere enn fourier, og krever mye mindre prosessor kraft.

 

Har du planer å gjøre dette til en skoleoppgave?

[haavis]

For å svare på det siste først: Nei, jeg gjør dette på fritiden. Så vill er jeg

 

Hadde man funnet en eller annen måte å beskrive / transformere objektene som fjernet informasjon om skalering og retning.....

 

Da er vi vel inne på segmentering av bildene, og det tror jeg er virkelig vanskelig å få til, i alle fall i den sammenhengen jeg holder på med det. Jeg har litt lyst til å se hva jeg får til med disse Fourier-greiene : )

 

Meeeen ... du sier:

Wavelet er mye enklere å implementere enn fourier, og krever mye mindre prosessor kraft.

 

Hvis det er tilfellet så er det kanskje bedre å prøve det? Kan du fortelle litt mer om wavelets?

 

Skulle forresten spørre om:

 

 

På hue og saturation kan du gjøre om til å bruke 4 bit pr pixel ...

 

Nå er ikke så veldig inne på bildebehandling generelt, men jeg splitta bildet vha av Paint Shop Pro, bare for å kikke hvordan det så ut. Det så ut til at saturation kom ut i fire bit (16 farger) og hue i 8 bit (256). Mener du da bare å redusere palettene?

 

Det som i såfall skal brukes til Fourier-beregningen, er det da bare palettverdiene?

 

Fortsatt takk for svar

[Torbjørn]

frekvenser bør ikke bare fjernes fra frekvensrommet (som jeg foretrekker å kalle det)

 

legg heller på en utflatning. brå stopp i frekvenser vil gi rippel når du transformerer tilbake.

[Torbjørn]

Enda et alternativ er å se på "Scale space"

 

Tenk deg at du gradvis jevner ut bildet, først vil detaljene forsvinne, siden vil konturer smelte sammen, og til slutt sitter du igjen med bare en feit topp i midten.

 

hvis du lagrer alle mellomtrinnene, og reverserer prosessen, vil du se konturene komme til syne etter hvert som du panorerer bakover i tid.

 

Da vil du få et pent bilde av hvor markante topper viser seg først, og hvor flere og flere detaljer etter hvert kommer til syne.

 

Det vil være hensiktsmessig å stopppe før du kommer helt ned på laveste nivå hvor antall konturer (ekstremalpunkter) eksploderer.

 

For hvert stillbilde må du finne alle topper, alle bunner og alle sadelpunkt. For det finnes det mange fremgansmåter. En angrepsvinkel er å følge den deriverte, en annen er å tråkle gjennom samtlige punkter du finner og analysere naboene, men her er det opptil flere feller å gå i.

 

Trenger jeg si at php er totalt uegnet til dette.

 

Se på octave, det er laget for slik matematikk og bildebehandling.

[petterg]

For å svare på det siste først: Nei, jeg gjør dette på fritiden. Så vill er jeg 

 

Jeg har vurdert å gjøre noe slikt for skoleoppgave.

 

Hadde man funnet en eller annen måte å beskrive / transformere objektene som fjernet informasjon om skalering og retning.....

 

Da er vi vel inne på segmentering av bildene, og det tror jeg er virkelig vanskelig å få til, i alle fall i den sammenhengen jeg holder på med det. Jeg har litt lyst til å se hva jeg får til med disse Fourier-greiene : )

Ja, selv om det er vanskelig tror jeg det er veien å gå. F.x sleit man før med å skille objekter i et bilde, men etter at en smarting fant ut av wavelet ble det hele mye enklere. Og når man ser på hvor enkelt wavelet er, er det rart ingen har tenkt på det før.

 

Meeeen ... du sier:

Wavelet er mye enklere å implementere enn fourier, og krever mye mindre prosessor kraft.

 

Hvis det er tilfellet så er det kanskje bedre å prøve det? Kan du fortelle litt mer om wavelets?

Ta et google søk. wavelet og jpeg2000.

Fant mye fint på emnet den gang jeg skulle implementere wavelet i hardware. (Et prosjekt som desverre ble avbrutt p.g.a problemer kvantifisering.)

 

Skulle forresten spørre om:

På hue og saturation kan du gjøre om til å bruke 4 bit pr pixel ...

 

Nå er ikke så veldig inne på bildebehandling generelt, men jeg splitta bildet vha av Paint Shop Pro, bare for å kikke hvordan det så ut. Det så ut til at saturation kom ut i fire bit (16 farger) og hue i 8 bit (256). Mener du da bare å redusere palettene?

hmm. I teorien skal begge komme som 8bit. Da har vel den ene allerede blitt redusert. Husker ikke helt hvordan det der hang sammen. - Ingen av dem brukte hele registeret fra 0-255 (8bit). Mente å huske at den ene hadde en range fra ca 10-140 (nesten mulig på 7bit) og den andre brukte 20 - 180, og krever dermed mer enn 7 bit. Uansett... unøyaktigheter i disse planene gir ikke store utslaget i det sammensatte bildet. Så du må bare prøve deg fram hva som virker mest fornuftig å kutte bort.

Reverser prosessen så ofte du kan, så ser du lett om du har gjort noe som gir dårlig resultat.

 

Det som i såfall skal brukes til Fourier-beregningen, er det da bare palettverdiene?

Om du velger å ha tallene i matrisa i forhold til en palett, eller om du kjører raw-data er vel litt optil deg. Jeg ville kjørt raw-data, da det ikke blir avhengig av noen palett som kan være forskjellig fra bilde til bilde. Tror det blir enklere å forholde seg til når du skal sammenligne.

 

Edit: quotefeil

Endret 9. november 2004 av petterg

[CronoMan]

Du kan hente data fra bildet og ta et gjennomsnitt av pixlene

[stiber]

Litt sent innligg, men sjekk ut følgende linker.

http://www.gnu.org/software/gift/gift.html

http://www.mrml.net

http://viper.unige.ch/

Jeg vurderer å bruke noe av dette selv til mitt neste bildearkiv prosjekt.

[haavis]

Hmmm ... Interessante greier. Jeg prosjektet litt på is grunnet mye skolearbeid, men dette ser jo fint ut ,) Tusen takk, skal undersøke dette nærmere ...

[ChrZZ]

Bare sånn kjapt.... Hvilke programmer kan gjøre dette med bilder på harddisken?

[Torbjørn]

ingen som jeg vet om. teoriene som er lagt fram er det opp til den aktive forumleser å implementere

[ChrZZ]

Jeg vet jo at det finnes mange programmer som kan gjøre dette med

bilder på harddisken, men er dette mulig å implementere i PHP?

Det er den delen her jeg refererte til, Torbjørn.