TranslationK-d træer
K-d træer
Hej jeg vil gerne bruge et K-D træ til at find billeder der ligner et bestemt billede. Men jeg ikke rigtigt greje hvilke dimensioner af et billede der vil give mening i et K-D træ, skal det f.eks være gennemsnits farver? has værdier?. Giver en "range-search" egentlig mening?
Re: K-d træer
Umiddelbart bør du nok kigge på måde hvorpå du kan udtrække nogle features fra dine billeder, selvfølgelig kan en gennemsnits farve godt være en feature, men den alene vil nok ikke være et særligt godt grundlag at finde ens billeder ud fra. (Med mindre det er noget meget særligt billede materiale du har). En efterhånden godt brugt teknik er principal component analyse (PCA) det kræver dog du har mod på lidt matematik, selvom du sikkert godt kan finde nogle færdige implementationer hvor du ikke behøver at sætte dig ind i så meget. (her er en primer om PCA: http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf)
Helt generelt om feature extraction kan du jo starte her på wikipedia: http://en.wikipedia.org/wiki/Feature_extraction
Helt generelt om feature extraction kan du jo starte her på wikipedia: http://en.wikipedia.org/wiki/Feature_extraction
Re: K-d træer
Jeg tror du blander to ting sammen her:
Først er der repræsentationen af dine billeder hvordan du kan sammenligne dem. Dernæst kan du finde ud af hvilke datastrukturer som passer til at lave søgninger på netop dit problem. Selvfølgelig hænger de ting sammen, men konceptuelt er de adskilte.
KD-træer bliver som hovedregel brugt til at finde de nærmeste n naboer til et punkt. De kan f.eks være i en stokastisk raytracer, som f.eks en photon mapper, hvor du vil indsamle de n nærmeste fotoner omkring det punkt hvor din stråle ramte..
Så mit råd er, tænk først over:
1. Hvordan er dit billede data præsenteret?
2. Hvordan kan to billede nemt og hurtigt sammenlignes?
3. Hvis 2 ikke finder en god løsning, gå til 1
Hvis løsningen til 2 ikke inkluderer en god søgestrukturer, kan det være du kan måske optimere hastigheden ved at inkludere en?
Først er der repræsentationen af dine billeder hvordan du kan sammenligne dem. Dernæst kan du finde ud af hvilke datastrukturer som passer til at lave søgninger på netop dit problem. Selvfølgelig hænger de ting sammen, men konceptuelt er de adskilte.
KD-træer bliver som hovedregel brugt til at finde de nærmeste n naboer til et punkt. De kan f.eks være i en stokastisk raytracer, som f.eks en photon mapper, hvor du vil indsamle de n nærmeste fotoner omkring det punkt hvor din stråle ramte..
Så mit råd er, tænk først over:
1. Hvordan er dit billede data præsenteret?
2. Hvordan kan to billede nemt og hurtigt sammenlignes?
3. Hvis 2 ikke finder en god løsning, gå til 1
Hvis løsningen til 2 ikke inkluderer en god søgestrukturer, kan det være du kan måske optimere hastigheden ved at inkludere en?
Re: K-d træer
nøøj tak Gorm, meget pædagogisk men det hjalp mig ikke ud over at være en liiiile bitte smule irriterende
Anyway med til historien hører self. at jeg blevet anbefalet at sammenligne mine billeder via f.eks 8X8 subimages, hvor jeg fandt gennemsnitsfarven og derefter organiserede dem i et K-d træ, herved undgik jeg at skulle sammenligne n gange og ja n er meget stort og jeg har rigtig mange sammenligninger. Det skal siges at mine billeder er meget små, og der er rigtig mange af dem.
Jeg begyndte at lege med algoritmen men kunne ikke rigtig få ind i mit hoved hvordan jeg skulle definere range search for gennemsnitsfarver. Derfor håbede jeg at der nogen der havde erfaring lige præcis med k-d træer og billeder,. Derudover har gennemsnitsfarven den fejl at to firkanter i forskellige farver vil opfattes som ens, men algoritmen vil ikke fange det.
Jeg har siden da kigget lidt videre på det og anden og bedre måde er repræsentere billeder på er via wavelets, nogen der har erfaringer i den retning?
Anyway med til historien hører self. at jeg blevet anbefalet at sammenligne mine billeder via f.eks 8X8 subimages, hvor jeg fandt gennemsnitsfarven og derefter organiserede dem i et K-d træ, herved undgik jeg at skulle sammenligne n gange og ja n er meget stort og jeg har rigtig mange sammenligninger. Det skal siges at mine billeder er meget små, og der er rigtig mange af dem.
Jeg begyndte at lege med algoritmen men kunne ikke rigtig få ind i mit hoved hvordan jeg skulle definere range search for gennemsnitsfarver. Derfor håbede jeg at der nogen der havde erfaring lige præcis med k-d træer og billeder,. Derudover har gennemsnitsfarven den fejl at to firkanter i forskellige farver vil opfattes som ens, men algoritmen vil ikke fange det.
Jeg har siden da kigget lidt videre på det og anden og bedre måde er repræsentere billeder på er via wavelets, nogen der har erfaringer i den retning?
Re: K-d træer
Beklager hvis mit svar var for pedantisk, men nu du har givet mere information tror jeg fik en idé til en løsning som bruger gennemsnitsværdierne (som måske virker en smule, men som har den fejl du snakkede om).
For at bygge sit træ:
1. For hver 8x8 subimage A laver man et kd-træ.
2. Så tager man alle billeder og smider deres gennemsnitsværdi i A ned i kd-træet. Sammen med gennemsnitsværdien er det vigtigt at gemme, hvilket billede værdien hører til.
Jeg går ud fra at siden det er blevet forslået at bruge et kd-træ, er det fordi at pixelværdierne er på på 3 eller 4 dimensioner (alt om du har alpha med).
Når man så søger efter sammenligninger og ranges i kd-træet, er det blot at lave en 'forskellighedstolerance' som man bruger til at søge med. En forspørgsel kan f.eks være: giv mig alle de billeder, som ligger indenfor 2 pixelværdier i gennemsnit i forhold til den referenceværdi jeg spørger med (dvs. man bliver altid nød til at have et referencebillede, som man bruger til at stille spørgsmålet: Hvilke billeder ligner det billede jeg nu har i hånden).
Den efterspørgsel bruger man så for hvert eneste 8x8 subimage. Hvis et billede går igen i alle efterspørgslerne er det 'cirka ens med referencebilledet'.
Personligt tror jeg en eller anden form for vægtet gennemsnit (f.eks et gaussfilter el. lign af hvert subimage) vil virke fint til at sammenligne billeder, især hvis man lader hvert subimage overlappe en lille smule med naboerne..
Var det bedre?
For at bygge sit træ:
1. For hver 8x8 subimage A laver man et kd-træ.
2. Så tager man alle billeder og smider deres gennemsnitsværdi i A ned i kd-træet. Sammen med gennemsnitsværdien er det vigtigt at gemme, hvilket billede værdien hører til.
Jeg går ud fra at siden det er blevet forslået at bruge et kd-træ, er det fordi at pixelværdierne er på på 3 eller 4 dimensioner (alt om du har alpha med).
Når man så søger efter sammenligninger og ranges i kd-træet, er det blot at lave en 'forskellighedstolerance' som man bruger til at søge med. En forspørgsel kan f.eks være: giv mig alle de billeder, som ligger indenfor 2 pixelværdier i gennemsnit i forhold til den referenceværdi jeg spørger med (dvs. man bliver altid nød til at have et referencebillede, som man bruger til at stille spørgsmålet: Hvilke billeder ligner det billede jeg nu har i hånden).
Den efterspørgsel bruger man så for hvert eneste 8x8 subimage. Hvis et billede går igen i alle efterspørgslerne er det 'cirka ens med referencebilledet'.
Personligt tror jeg en eller anden form for vægtet gennemsnit (f.eks et gaussfilter el. lign af hvert subimage) vil virke fint til at sammenligne billeder, især hvis man lader hvert subimage overlappe en lille smule med naboerne..
Var det bedre?
Last edited by Gorm on 18 Jul 2009, 13:10, edited 1 time in total.
Re: K-d træer
Med fare for blot at være pædagogisk og irriterende vil jeg lige poste et link til VLFeat:
- Rune
Udeover selve implementeringen er der også nogle mini-tutorials om de forskellige algoritmer. SIFT -- scale-invariant feature transform -- er generelt meget populær, og en hurtig google-søgning finder både det oprindelige paper samt diverse implementeringer og beskrivelser heraf."The VLFeat open source library implements popular computer vision algorithms including SIFT, MSER, k-means, hierarchical k-means, agglomerative information bottleneck, and quick shift. It is written in C for efficiency and compatibility, with interfaces in MATLAB for ease of use, and detailed documentation throughout. It supports Windows, Mac OS X, and Linux."
- Rune
Re: K-d træer
Hej Gorm
Ja der var meget bedre
Jeg havde opfattet det som et K-D træ hvor hver 8x8 billede var en enkelt heltals dimension, men det krævede en enkelt værdi for all 64 pixels, hvilket ikke gave megen mening.
Jeg fandt en god beskrivelse af den "dumme" sammenlignings algoritme her.
http://www.lac.inpe.br/~rafael.santos/J ... eyareequal
echo^fdg jeg havde håbet ikke at skulle ud i mønster genkendelse :shock: Nu skulle jeg måske prøve og se hvordan den naive implementation virker
Ja der var meget bedre
Jeg havde opfattet det som et K-D træ hvor hver 8x8 billede var en enkelt heltals dimension, men det krævede en enkelt værdi for all 64 pixels, hvilket ikke gave megen mening.Jeg fandt en god beskrivelse af den "dumme" sammenlignings algoritme her.
http://www.lac.inpe.br/~rafael.santos/J ... eyareequal
echo^fdg jeg havde håbet ikke at skulle ud i mønster genkendelse :shock: Nu skulle jeg måske prøve og se hvordan den naive implementation virker