Billedsegmentering (old 2003)

This page is, evidently, in danish. It was part of an exercise for a university course some time back. I have not translated it into English, since I have no reason to believe there is a demand for it. If I am wrong, feel free to contact me and let me know.

Denne side er en html-udgave af en opgaveløsning for et kursus i mønstergenkeldelse og billedbehandling.

Jeg har tidligere beskrevet hvordan et objekts egenskaber kan ses som koordinater i et vektorrum. Et objekt med tre egenskaber (som RGB-farver) er da punkter i et 3D rum.

Jeg vil her forsøge at vise hvordan man kan anvende denne tolkning til at segmentere farvebilleder.

Segmentering 

Begrebet segmentering dækker over at sortere en række elementer ind i en af flere mulige klasser. For farver kan man eksempelvis sortere dem i en mest blållig klasse, en mest rødlig klasse og meget mørk klasse. Givet en farve skal man nu anbringe den i den mest passende klasse. Det mest rimelige er at anbringe farven i den klasse som er nærmest. Spørgsmålet er så bare hvad der er nærmest. Hvordan beregner man afstanden?

Euclidsk afstand

Den mest simple afstandsberegning i et 3D rum er Euclids afstand. Givet to punkter (x1,y1,z1) og (x2,y2,z2) er afstanden kvadratroden af (x1-x2)^2 + (y1-y2)^2 + (y1-y2)^2. For et højere rum med flere dimensioner tilføjes blot flere led for de ekstre akser.
Man kan dermed nemt beregne en afstand mellem to farver. For to farver er Euclids metode den korrekte. Det bliver dog kompliceret når man taler om afstanden mellem en farve og en klasse af farver. Med denne metode må man beregne den gennemsnitlige farve for ens klasse og derefter beregne afstanden fra den uklasificerede farve til klassens centrum. Metoden kan bruges, men den har svagheder. Den tager for det første ikke hensyn til fordelingen af farver i klassen.

Mahalanobis afstand

En mere kompleks måde at beregne afstanden fra en uklasificeret farve til en klasse er Mahalanobis afstand. I dette afstandsmål tages der hensyn til hvordan farverne i klassen er spredt i rummet. På tegningen herunder er der en rød og en blå klasse samt et grønt uklasificeret punkt. Farverne er ikke udtryk for egentlige RGB-værdier, men er der for at skelne mellem objekterne på figuren. Man ser at det grønne punkt ligger nogenlunde midt mellem de to klasser. Faktisk er den en smule tættere på det røde center end det er på det blå. Et Euclidsk afstandsmål ville derfor klasificere punktet som tilhørende den røde klasse.

Med Mahalanobis afstandsmål vil punktet derimod tilhøre den blå klasse. Det virker ved første øjekast forkert, men giver god mening ved nærtere eftertanke. Forestiller man sig at begge klasser langsomt pustest op som en ballon indtil den ene opsluger det grønne punkt. Så er det den blå klasse som først når punktet. Det skyldes at "den aflange ende" af den blå klasse peger mod punktet, mens det er "den flade ende" af den røde klasse som går ud mod punktet.

Man behøver nu ikke at forestille sig balloner, men skal istedet se ovennævnte som udtryk for spredningen af farverne i de enkelte klasser. Sagt med få og simple ord, så viser formen af den røde klasse at elementerne i klassen spreder sig op og ned. Hvis man har et punkt i klassen, så er det mere sansynligt at punktet er over eller under centrum, end at det er til højre eller venstre for centrum. På billedet ser man at øvre og nedre fjerdedel indeholder flere punkter end højre og venstre fjerdedele.


Denne spredning betyder at har man to punkter som er lige langt fra centrum, men hvor det ene punkt er ved siden af klassen mens det andet er over eller under, så er det mere sansynligt at punktet faktisk tilhører klassen hvis det er over eller under end ved siden af.
Dette kan illustreres ved at definere at ellipsen omkring klassen er i afstand 1 fra centrum i enhver retning. Et punkts afstand fra klassen er dermed målt ved hvor meget længere punktet er fra klassens centrum end ellipsen er i den retningn. Samme klasser som før, nu med afstand=1 markeret for begge.
Afstanden fra en blå klasse til punktet er den blå/grå linie og afstanden fra den røde klasse er den blå/pink linie. Længden af den blå linie er for begge klasser 1. Derved er afstanden fra den røde klasse lidt over 2 mens afstanden fra den blå klasse er omkring 1.5.


Man skal altså tage hensyn til et punkts orientering i forhold til klassen, og klassens form, når man skal definere et rimeligt afstandsmål. Med klassens form menes også dens udstrækning. Er den meget koncentreret med næsten identiske farver, eller indeholder den meget spredte farver? Et eksempel på segmentering af et billede i to klasser, hvor størelsen er indlysende relevant, kan være følgende:

Billedet består af en blok som er rent rød (1,0,0) og en anden blok som er en blanding af primært grønlige farver. Den røde klasse er størst når man ser på antallet af pixels, men den grønne er størst hvis man ser på antallet af forskellige farver og spredningen i farverummet. Givet en pixel som ikke rigtig er rød og ikke rigtig grøn, da er det langt mere sansynligt at den hører til i den grønne klasse. Den røde er jo kendetegnet ved så lille spredning at det virker usansynligt at en pixel, som skiller sig så meget ud, hører til der. Den grønne klasse er derimod så spredt at snart sagt hvad som helst kan høre til i den, hvis bare det er lidt grønt.


Viser man klasserne som de ligger i farverummet, så ser man direkte størelsen af den grønne og røde klasse.
Første billede viser distributionen af farver for hele billedet. Andet billede viser den grønne klasse som lyssegrønne punkter. Den grønne klasse indeholder i dette tilfælde ikke alle grønne punkter, da den er defineret som et udsnit af det grønne område. Den røde klasse sidder hele ned i højre hjørne og fylder kun eet punkt.


Dette var en forklaring på hvorfor Euclids afstand ikke er tilstrækkelig. Som sagt bør et punkt mellem den grønne og røde klasse tilfalde den grønne og ikke den røde, da det er overvejende sansynligt at punktet hører til der.

Beregning med Mahalanobi

Før man kan udføre nogen afstandsberegning skal der mere til end billeder af balloner og intuitive fornemmelser for størelser og farver. Man skal beregne variansen for klassen og dermed et koordinatsystem som beskriver klassen bedst muligt.

Har man en række farver som hører til i ens klasse, så beregner man kovarians-matrisen for alle farverne. Derefter beregner man egenvektorene og egenværdierne for denne matrise for at få (i dette tilfælde) de tre akser som udgører koordinatsystemet for klassen. Nedenstående matlab funktion returnerer et 4*4 koordinatsystem baseret på de pixels det modtager. At systemet er 4*4 for 3D farver skyldes at koordinatsystemets nulpunkt skal medtages i systemet. Dette betyder en translation og dermed skal matrisen være 4*4.

function principal=principalSystemFromPixels(pixels)
%calculates the principal system from the covariance matrix's eigen vectors
%and eigen values AND the center of all given pixels

%calculate the length and orientation of the axis
c=cov(pixels);
[v l]=eig(c);
%kludge to remove singular matrix
kludge=rand(3,3)/1000;
l=l+kludge;
v=v*sqrt(l);

%calculate the translation of the center og the pixels
center=mean(pixels);
principal=eye(4,4);
principal(1:3,1:3)=v(1:3,1:3);
principal(1:3,4)=center';
% principal=inv(principal);
end

Koordinatsystemet for tre klasser i et billede er indtegnet i en punktsky herunder sammen med det oprindelige billede.


De tre klasser er defineret som de pixels der er inde i de rektangulære områder, der er markeret i billedet. Klassens farve er vist som rektanglets farve for senere reference. For hver klasse er dets pixels markeret i punktskyen med klassens farve. Man ser at den brune klasse ligger i et snævert område nær den hvide farve, mens den mørkegrønne og den lysegrønne klasse er mørkere og rimeligt ens.
For hver klasse er det principale koordinatsystem beregnet og indtegnet i det sidste billede. Det kan være svært at se, men de er der. Liniernes længde viser hvor stor spredning klasserne har og i hvilken retningn spredningen er størst. Hvert system er tegnet med tre linier som angiver hver af de tre akser. Aksernes længde er defineret som 1 - ligesom ellipsen tidligere.

For at anskueliggøre koordinatsystemet bedre er det her tegnet i 2D for en række punktsamlinger. Bemærk hvordan systemets akser orienterer sig efter punktmængdens form.


Når man beregner et punkts afstand til en klasse, så gør man det altså i klassens eget koordinatsystem. Er en akse lang, så vil en afstand langs aksen være mindre end hvis aksen er kort. Det er simpel 3D-regning som kendes fra geometriske transformationer.
Afstanden beregnes ved at transformere punktet (her en 3D farve) over i klassens koordinatsysten og i dette koordinatsystem beregne den euklidske afstand fra det transformerede punkt til systemets centrum.

Segmentering med Mahalanobis afstand indebærer følgende skridt:

  • Definitation af klasser ud fra en punktmængde
  • Transformering af alle uklasificerede punkter til hver af klassernes koordinatsystemer
  • Beregning af afstand fra transformerede koordinat til klasses centrum
  • Valg af klasse med korteste beregnede afstand
  • Konkrete segmenteringer

    I stedet for at tærske mere langhalm, vil jeg nu vise segmentering af nogle faktiske billeder. 

    Billede 1 - simple afgrænsede former

    Billedet består af 6 unikke farver incl. baggrunden. Denne meget lille farvespredning ser man tydeligt i figurene her. Koordinatsystemerne er imidlertid ikke nemme at se. Det skyldes at alle seks klasser har en farvespredning på nul - de består hverisør af kun een farve. Når der ingen variation er, så er der reelt heller intet koordinatsystem.

    Segmenteringen gik som den skulle. Hver klasse er for sig. Hvad ville der ske hvis ikke der var defineret en klasse for hver farve, men istedet kun tre klasser? Så skal alle pixels falde i en af de tre. Resultatet ses herunder.


    Den blå, den lilla og den grønne falder i en klasse. Den røde er for sig selv og den hvide baggrund er for sig selv.
    Man vil generelt mene at den lila burde komme is amme klasse som den røde da afstanden til denne klasse er mindre end til den blå. Denne fejl skyldes sansynligvis at da hver klasse er een farve, så er der ingen spredning i klassens data, og dermed er akserne i systemet alle af længden nu. Jeg kan ikke regne fornuftigt med nul-matriser i min afstandsberegning, da de ikke kan inverteres. Af den grund lægger jeg en meget lille tilfældig værdi til alle matriserne for at forhindre nulmatriser. Det betyder desværre at for en række klasser som alle reelt har nulmatriser, da er deres system nu udelukkende beskrevet ved de meget små tilfældige værdier. Hvis den ene klasse får en lidt større tilfældig værdi lagt til en nulakse, så vil denne klasse tilsyneladende have større spredning end de andre, og være mere tilbøjelig til at få uklasificerede punkter tildelt. Denne fejl opstår dog kun for nulmatriser, hvilket vil sige klasser som er beskrevet ved een farve.

    Billede 2 - kompleks form

    Dette billede viser en blå bil på en ganske kompleks baggrund. Det segmenteres med Mahalanobis og Euclids afstand for sammenligning.

    Det lykkedes faktisk at isolere bilens karosseri ganske glimrende. Græsset og muren er også genkendt, men generelt kan man ikke sige at billedet er godt segmenteret. Det er også en særdeles kompleks opsætning.
    Sammenligner man Mahalanobi og Euclid, så er der ikke den store forskel, men man kan dog se at Euclid er mere støjfyldt. Det skyldes afstandsberegningen, som ikke tager hensyn til spredning. Eksempelvis græsset har stor spredning.

    For dette mere realistiske billede, hvor klasserne har en vis spredning, kan man godt se koordinatsystemerne i farverummet. De er ikke markante, men dog synlige. Klassernes spredning er nemmere at se ved at tegne dem ind i farverummet som herunder.

     


    Billede 3 - kompleks form

    Dette billede en hvid bil på en sort bane omgivet af gult græs. Det virker nemmere at segmentere.

    Jeg sammenligner igen Mahalanobis afstand med Euclids som segmenteringsmål.


    Det er denne gang tydeligt af Euclids metode ikke drager fordel af den farvespredning to af klasserne har. Mahalanobis afstand er et langt bedre mål i dette billede. Det ses dog at begge faktisk får et acceptabelt resultat ud af segmenteringen, og hvis man arbejder videre med disse segmenterede billeder, så kan de måske anvendes til... noget.

    Igen viser jeg billedet som det er defineret i farverummet, klasserne i rummet og koordinatakserne. Bemærk særligt den hvide farveklasse (tegnet med brunt her). Den er naturligvis placeret i det hvide område, men den er også langt mere koncentreret end græsset og banen er. Den strækker sig en smule ned i det mørke område, men holder sig på linien hvor gråtonerne ligger. Igen noget man selv kan se i billedet.


    Billede 4 - kompleks form

    Et gråtonebillede er konverteret til RGB for at kunne anvende samme program. Billedet forestiller nogle mønter på en lys baggrund. Mønterne varierer i lysstyrke, hvilket derfor er eneste kriterium for segmenteringen.

    Det første der er værd at bemærke er farvefordelingen i rummet. Da det egentlig er et gråtonebillede ligger samtlige farver på linien hvor R, G og B er ens.


    En anden ting som skal bemærkes er at klasserne overlaper ganske meget, hvilket man kan se på næste figur. Hvis to klasser overlapper, så betyder det at farverne i det rum, hvor begge klasser er, tilhører begge klasser. Der er altså et helt område som egentlig er klasificeret som tilhørende begge klasser. Punkter i det rum kan naturligvis derfor ikke altås sendes til rette klasse, hvilket giver dårlig klasificering.


    Jeg har dog forsøgt en klasificering alligevel.


    Hvilken er så bedst? Tja. De er ikke særligt gode nogen af dem. Det er i hvert fald tydeligt nok at en segmentering med disse to metoder ikke er tilstrækkeligt til at skelne mellem mønterne. Det er imidlertid stadig anvendeligt i samarbejde med andre metoder. Man ser at de mest lyse reflekser i mønterne er lyssegrønne, baggrunden er forholdsvis ensartet mørkegrøn (den oprindelige var ikke ensfarvet) og de mørke mønter er brune. Med hensyn til papirstykket i hjørnet, så fik Mahalanobi det med som et hele, mens Euclid hakkede det lidt i stykker mod baggrunden. I dette tilfælde er det faktisk en fordel af objektet er blevet forminsket, selvom det strengt taget er forkert.

    Konklusion

    Disse segmenteringsmetoder er anvendelige til meget, men har deres begrænsninger. Man skal ikke være overoptimistisk med hensyn til segmentering af komplekse billeder. At fjerne baggrunden fra billederne med biler og lade bilen stå uskadt tilbage, det virker som en umulig opgave.
    Det vil imidlertid forbedre metoden, hvis klasserne ikke angives som rektangulære former i billedet. Ofte vil det være ønskværdigt at kunne vælge et større sammenhængende irregulært formet område. Begge biler er eksempelvis klasificeret ud fra et lille udsnit på karosseriet. Med bedre klasser vil man måske have en reel chance for at fjerne baggrund. Uden anden klasseudvælgelse tror jeg ikke på det.