Beregning af mønters pålydende værdi (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.

Edit: Oprindeligt havde jeg kildekoden til Matlab-løsningen med på siden, men efter en flytning af website, så er det på forunderlig vis gået tabt i kopieringen. Jeg håber at beskrivelsen kan stå alene hvis nogle har læst med her.

Jeg vil i denne tekst vise en metode til at beregne værdien af en mængde mønter, udelukkende baseret på et billede af dem. Jeg vil anvende Matlab til analysen, men vil ikke komme nærmere ind på brugen af Matlab, da det drejer sig om billedbehandlingen og ikke værktøjet.

Der er en række skridt jeg vil tage for at udføre beregningen. Disse er
  • Billedtagning af mønterne
  • Analyse af histogram for billedet
  • Konvertering til støjsvagt billede baseret på tærskelværdier fundet via. histogrammet
  • Ekstra støjfiltrering
  • Opdeling af billede i forbundne flader - objekter
  • Beregning af egenskaber for objekterne
  • Analyse af histogram for objekternes arealer
  • Valg af tæskelværdier for mønttyperne baseret på histogrammet
  • Beregning af værdi
  • Billedtagning af mønterne

    Dette kan virke som den letteste del af opgaven, men i praksis er den nok den sværeste. Et billede skal ikke have for meget støj, der skal være en meget ensartet belysning, og man bør tage billedet sådan at en mønts størelse ikke afhænger af dens position i billedet, men kun af mønten selv.
    I praksis er det svært at opfylde. Jeg forsøgte i længere tid at få nogle fornuftige billeder med mit gamle digitalkamera, men uden held. Enten var der for meget highligt fra de mest blanke mønter, eller de blev alle underbelyst. Selv underlaget var svært at få tilstrækkelig støjfrit. Den ensartede belysning gik slet ikke.
    Jeg endte derfor med at låne et billede fra et projekt på DIKU. Samme projekt som inspirerede mig til at forsøge netop denne opgave. Bemærk den dejligt ensfarvede baggrund og den jævne belysning. Billedet er optaget i en almindelig scanner, som netop er god på det område. Der er anbragt lidt revet papir i det ene hjørne for at skabe kraftig støj.

    Analyse af histogram for billedet

    For at kunne se hvad der er baggrundsstøj og hvad der er mønter, så opbygger jeg et histogram over lysværdier i billedet. Dette viser mig at der grundlæggende set er to områder: under og over 120 i intensitet. Da mønterne er mørkere end den hvide baggrund konkluderer jeg at de må ligge i den lave del af området.

    Jeg indlæser billedet fra disk og beregner histogram



    Konvertering til støjsvagt billede baseret på tærskelværdier fundet via. histogrammet

    Fra histogrammet ved vi at mønterne ligger i området under 120 i intensitet. Det er derfor simpelt at beregne et binært billede som kun finde mønterne ved at kun medtage værdier under 120. I praksis er mønterne ikke alene under de 120; der vil også være støj. Tilsvarende er det ikke kun baggrunden som ligger over 120; lyse områder af mønterne vil også være der. Den slags spredning skal man helst forholde sig til allerede ved billedtagningen.

    Jeg beregner det binære billede som pixels under 120 i intensitet, og viser billedet som et to-farvers gråtone billede.



    Hvis man vælger en forkert tærskelværdi, så fjerner man enten for meget eller for lidt og det virker derfor ikke. Histogrammet tjener til at finde den optimale tærskel for en simpel objektisolering som denne, der kun tager sig af lysintensitet. Herunder to eksempler på binære billeder som er beregnet med for høj og for lav tærskelværdi. For lav medfører at mønterne ikke kommer ordentligt med. For høj lader støjen slippe med.


    Ekstra støjfiltrering

    Efter grænseværdien er sat, og et binært billede beregnet, er der stadig lidt støj. Jeg fjerner det værste med erorde. Erode eroderer billedet. Det vil kort fortalt sige at fladerne bliver ædt fra kanterne. For store flader sker der det at de bliver mindre. For små flader vil errosionen medføre at de helt fjernes. Støjen er netop meget små flader, mens mønterne er store. Mønterne bliver altså også ædt Det er dog rimelig ensartet, og hvis man bare gør det konsekvent, så kan man stadig kalibrere billederne.



    Man ser her at støjen er helt væk. Mønterne er dog også blevt ædt lidt, så det kompenserer jeg delvist for ved en dilate, som i praksis er det modsatte af en erosion.



    Opdeling af billede i forbundne flader - objekter

    Nu er der kun mønter. Forbundne områder skal så navngives. Hvert ubrudt forbundet område af værdier forskellige fra nul vil få sin egen pixelværdi. Sagt på en anden måde... fra en 2D matrise af 0 og 1 konverteres til en 2D matrise af 0..n, hvor n er antallet af ikke-forbundne objekter. I det binære billede er der nu 20 selvstændige øer af pixels. Hver sådan ø skal have sin egen "label", som er et tal. Man kan betragte det som at hver mønt bliver farvelagt med et forskeligt tal. Det kan sagtens visualiseres så det er mere klart.Jeg beregner labels for det binære billede og viser resultatet


    Labelfunktionen navngiver områder med pixels forskellige fra nul som selvstændige objekter. Derfor er det vigtigt at mønterne ikke overlapper. To overlappende mønter i det binære billede ville give een label som dækker en irregulært formet mønt, der er kombinationen af de to. En Hough transformation vil kunne se de enkelte mønters cirkelform selv med overlapning, men den anvender jeg ikke her.

    Beregning af egenskaber for objekterne

    Jeg beregner herefter de enkelte objekters egenskaber og filtrerer dem baseret derpå. Den egenskab jeg er intereseret i er objektets konvekse areal. Det er arealet af objektets konvekse skrog. Man kunne mene at det reele pixelareal var en mere logisk ting at kigge efter, men på grund af ikke-perfekt belysning og erode-trinnet tidligere, kan der være større eller mindre huller i mønterne. Det konvekse skrog påvirkes dog ikke af den slags, bare kanten ikke er for skadet. Man mister ganske vist informationen om hullet i nogle af mønterne, men det er ok i dette tilfælde. Valget af arealet som afgørende faktor skyldes at det er konstant. Mønter kan være mere eller mindre blanke eller slidte, men de ændrer normalt ikke størelse.
    Til sidst i teksten viser jeg hvordan man kan finde frem til de pixels i det oprindelige billede som præcis udgører ens mønt. Dermed kan man lave mere komplekse sammenligninger. Man kan se på farve og evt. frekvensindehold.

    Jeg beregner en vektor af størelsen på de konvekse arealer. Derefter laver jeg et histogram over arealerne for at se om det virkelig er nok til at skelne mellem mønterne.



    Hvis man tæller efter kan man se at der er præcis 20 elementer. Det ser dog ud som om de er opdelt i 9 forskellige arealgrupper, hvilket antyder at der er 9 forskellige mønttyper. Der er i virkeligheden kun syv, så nogle af elementerne må være samem mønttype med lidt forskelligt konvekst areal. Disse skal naturligvis ikke opfattes som forskellige objekter, men regnes for ens. Derfor skal elementer med meget ens areal gruperes. I histogrammet kan man se at der faktisk er 7 adskilte arealer. Disse repræsenterer mønternes arealer. Man sætter derfor en grænse på 2199 (midten mellem to områder), som adskilder første og anden gruppe. Hvis ens billedmateriale er af en højere kvalitet, så ville man som udgangspunkt have arealerne koncenteret i mindre områder, og man kunne derfor lave ganske smalle områder for arealerne hvor man genkender de enkelte mønter, og alle udenfor disse bånd ville være defineret som ukendte mønttyper.

    Da jeg ikke formåede at tage et ordentligt billede med mit digitale kamera har jeg kun dette ene eksempel. Det egner sig dårligt som kaliberringsbillede, da man skal gætte lidt på hvilke arealer der passer til hvilke mønter. Man kunne istedet have lavet kalibreringsbilleder til hver type. Billedet ville eksempelvis være 10 tyvekroner, det næste ville være 10 tikroner etc. Baseret derpå kunne man beregne et nøjagtigt areal for hver type. Alternativt kunen man have eet billede med 1 tyvekrone, 2 tikroner, tre femkroner etc. Dermed kan man også regne ud hvad der er hvad.

    Ser jeg på billedet, så ser jeg at der er 2*20, 1*10, 1*5, 2*2, 4*1, 3*0.5, 7*0.25. Tokronerne og tyverene samt tierne og femmerne er der lige mange af, og der skal jeg være mere kreativ.
    Jeg kan med det samme se at første grupering i histogramet må være 25ører, da der er syv. Næste gruppe må være enkroner, da der er 4. Tredje gruppe må være 50ører, da der er 3. Fjerde gruppe har een mønt. Det kan så være en tier eller en femmer. Da femmere har større konvekse arealer end tiere, så må denne gruppe være tierne, da arealet er mindst her. De næste to grupper har begge to mønter hver og kan være tyvere eller tokroner. Arealet er også mere ens, men igen viser en sammenligning at den ene er størst. Tyverene har størst areal, så femte gruppe må være tokroner, sjete gruppe er så tyverene, og til sidst har vi femmerne.

    Denne metode virker fint, og man kan teste sine grænser for at sikre at man har valgt rigtigt, men det er naturligvis at foretrække med et ordentligt kalibreringsbillede!

    De definerede grænser er nu: 20kr = 4000-4600 10kr = 3200-3500 5kr = 4600-5000 2kr = 3500-4000 1kr = 2250-2600 0.50kr = 2600-3200 0.25kr = 1500-2250 Herefter skal man egentlig bare tælle antallet af mønter i hvert interval. Jeg gør dette ved at definere top og bund for intervallet og en mønt er indenfor hvis arealet er over eller ligmed bund og mindre end top. For at lette denne sammenligning laver jeg en 2d array med min-, max- og værdi-informationen.

    Jeg beregnede tidligere samtlige konvekse arealer for mine labels. Disse arealer kan jeg nu søge i efter værdier som passer til mine mønter.

    Når jeg kører denne kode på mit billede, så får jeg 66.25kr som værdi. Hvis jeg selv tæller i billedet, så får jeg samme værdi. Det siger imidlertid ikke så meget, da jeg kun regner på det billede, som jeg reelt har konstrueret koden til at kigge på. For at lave en ordentlig test, skal jeg beregne værdien af andre billeder. Jeg har som sagt problemer med at konstruere brugbare billeder (en scanner kunne gøre det), så jeg klippeklistrer lidt i kalibreringsbilledet for at lave et nyt. Det er lidt snyd, men bestemt ikke i alvorlig grad. Jeg ender så ud med følgende billede.


    Programmet siger denne gang at der er 91.5kr og det siger en manuel eftertælling også. Programmet er altså nu i stand til, alene baseret på arealet af mønterne, at beregne deres pålydende værdi.

    Yderligere test for meget ensartede mønter 

    Jeg lovede tidligere at vise hvordan man finder de oprindelige pixels som udgjorde ens objekt. Det skal jeg hermed gøre.

    Man kan for de labels, man beregner, få en bounding box, som angiver mindste akse-orienterede rektangle som objektet kan være inde i. Dette egner sig fint til at finde de pixels som er objektet. Man kan altså finde den mindste rektangulære gruppe af pixels i det oprindelige billede, som repræsenterer objektet.


       
     


    Dette giver imidlertid alle pixels i objektets bounding box. Det er ikke hvad man ønsker. Kun objektets egne pixels skal bruges - resten skal væk. Der er en binær property mere som hedder Image. Den er et bitmask som viser hvilke pixels i ens bounding box som faktisk er en del af objektet. Hvis man ganger den på alle pixels i bounding box, så vil pixels udenfor objektet blive nulstillede, så det gør jeg.

     
     

    Det man nu ser, er at dele af mønten faktisk bliver klippet af. Det er beklageligt, men skyldes at disse dele ikke er belyst sådan at de klarede sig igennem støjfiltreringen i starten. Skal man lave lysberegninger for sine mønter, så bør det derfor være relative værdier. Genemsnitlig lysstyrke pr pixel eksempelvis.