Poison; Open Source Image Processor

Poison; Open Source Image Processor

Ruud van Baar

0222445 [email protected] Juni 2005 Onder begeleiding van: R. van den Boomgaard


Abstract Er zijn vele wiskundige programma’s beschikbaar, zoals Matlab en Mathematica, welke zeer geschikt zijn voor uiteenlopende taken. Een nadeel van deze programma’s is dat ze te duur zijn voor studenten om thuis te gebruiken. Gezien de vooruitgang van verschillende Open Source talen, zoals bijvoorbeeld Python, wordt in deze paper uiteengezet hoe een programma in deze taal kan worden gebruikt voor een inleidende cursus Beeldbewerken zoals dat gegeven wordt aan de Universiteit van Amsterdam. Daarnaast wordt er gekeken naar de Gaussische convolutie, welke een belangrijke rol speelt in de hedendaagse beeldbewerking. Verschillende mogelijkheden van benadering en berekening van deze convolutie worden bekeken en een aantal hiervan worden geïmplementeerd en vergeleken.

2


1. Inleiding ...................................................................................................................... 5 2. Python ......................................................................................................................... 7 2.1 Inleiding ................................................................................................................ 7 2.2 Basis Python ......................................................................................................... 7 2.2 Gebruikte Modules................................................................................................ 8 2.2.1 Numarray ....................................................................................................... 8 2.2.2 Matplotlib..................................................................................................... 10 2.2.3 Python Image Library .................................................................................. 10 3. Poison........................................................................................................................ 11 3.1 Ontwerpcriteria ................................................................................................... 11 3.2 Keuzes................................................................................................................. 11 3.3 Graphical User Interface ..................................................................................... 13 3.3.1 Tekstvelden .................................................................................................. 13 3.3.2 Menu’s ......................................................................................................... 14 3.3.3 Afbeeldingen................................................................................................ 14 3.3.4 Implementatie .............................................................................................. 14 3.3.5 Poisonobject................................................................................................. 15 3.3.6 Poisonfunctions............................................................................................ 15 3.4 Werking............................................................................................................... 17 4. Evaluatie Poison........................................................................................................ 21 4.1 Practicum 1 ......................................................................................................... 21 4.2 Practicum 2 ......................................................................................................... 22 4.3 Practicum 3 ......................................................................................................... 22 4.4 Practicum 4 ......................................................................................................... 24 4.5 Practicum 5 ......................................................................................................... 24 5. Gaussische bibliotheek.............................................................................................. 27 5.1 Inleiding .............................................................................................................. 27 5.2 Straight Forward ................................................................................................. 27 5.3 Interpolatie .......................................................................................................... 28 5.4 Recursief ............................................................................................................. 28 5.5 Fourier................................................................................................................. 29 5.6 Implementatie ..................................................................................................... 30 5.6.1 Straightforward ............................................................................................ 30 5.6.2 Recursief ...................................................................................................... 31 5.7 Resultaten............................................................................................................ 31 6. Conclusie................................................................................................................... 35 7. Referenties ................................................................................................................ 39 Appendix A................................................................................................................... 40 Appendix B ................................................................................................................... 41 Appendix C ................................................................................................................... 44

3


4


1. Inleiding In het derde jaar van het Bachelor-programma Informatica aan de Universiteit van Amsterdam wordt het vak Beeldbewerken gegeven door Rein van den Boomgaard. Voor de practica van dit vak wordt gebruik gemaakt van het programma Matlab, ontwikkeld door The MathWorks. Matlab is een “hogere programmeertaal en interactieve omgeving voor het ontwikkelen van algoritmes, datavisualisatie, data-analyse en numerieke berekeningen” aldus de website [1]. De practica van dit vakken lopen uiteen van een kleinste kwadraten schatter tot een implementatie van een Gaussische Convolutie. De opdracht voor dit Bachelor project is het schrijven van een programma met eenzelfde functionaliteit, echter nu Open Source en in Python. Open Source wil zeggen dat de code van het programma door iedereen is in te zien en vrij aan te passen. Bovendien is het gratis. Een aantal van deze modules zijn bruikbaar voor de implementatie van het programma. Als basis zal de module numArray dienen, een object dat gebruikt wordt om arrays te representeren in Python. Een tweede gedeelte van de opdracht is tijdens de bespreking met de projectbegeleider naar voren gekomen. Aanvankelijk waren er twee mogelijke uitbreidingen van de opdracht: - Dynamisch programmeren: Een programma bepaalt runtime wat voor type variabelen zijn er in een functie worden gebruikt. Afhankelijk van dit type zal een functie bijvoorbeeld een ander algoritme gebruiken of op een andere wijze gebruik maken van de cache. - Gaussische bibliotheek: De Gaussische convolutie is een veelgebruikte functie in beeldbewerking. Om deze functie effectief te implementeren zijn veel algoritmes ontwikkeld, zoals bijvoorbeeld een recursieve vorm of de standaard gediscretiseerde vorm. De tweede opdracht zou een implementatie van deze verschillende algoritmes betreffen. De keuze is uiteindelijk gevallen op de tweede mogelijkheid, de Gaussische bibliotheek. Op de CD-Rom is de sourcecode van Poison te vinden. Daarnaast staan de gebruikte papers, de opdrachten van Beeldbewerken en Python 2.4 met de modules er op. Voor installatie en gebruik is er een readme.txt.

5


6


2. Python 2.1 Inleiding De gebruikte taal voor het programma is Python. Deze taal is een geïnterpreteerde, interactieve en object georiënteerde programmeertaal. Python is ontwikkeld aan het CWI, het Centrum voor Wiskunde en Informatica, in Amsterdam. De ontwikkeling is begonnen in 1990 en is nog steeds in volle gang. Er komen steeds meer modules voor diverse toepassingen en ook wordt Python in belangrijke projecten gebruikt, waarvan de bekendste wel Google is [2]. In dit hoofdstuk volgt een korte introductie van Python, met uitleg over basisprincipes van de taal.

2.2 Basis Python In een taal als C is het niet belangrijk op wat voor manier de code is uitgelijnd, als er maar een semicolon (;) aan het eind van een regel staat en blokken bij elkaar worden gegroepeerd met behulp van gekrulde haken ({ en }). Dit is direct een van de grootste verschillen met Python. Bij Python is de indentie bepalend voor de groepering van expressies. Een ander groot verschil is dat variabelen niet expliciet gedefinieerd hoeven te worden, maar krijgen ze het juiste type door de interpreter toegewezen. Zo is bijvoorbeeld de volgende C-code: int a = 1; if(a == 1){ printf(“Hello World\n”); a = a + 1; }

gelijk aan de volgende Python code: a = 1 if (a==1): print “Hello World” a = a + 1

Als de laatste regel in de Python code een stuk naar voren zou staan, zodat het uitgelijnd is met de if-statement, zou deze code anders zijn dan de C-code. In dit specifieke voorbeeld zou het uiteindelijke resultaat gelijk zijn, echter bij een andere waarde van a zou in C deze waarde niet worden opgehoogd en in Python wel. Python is een van de weinige talen die op deze manier gebruik maakt van indentie. Andere talen zijn bijvoorbeeld Haskell en Occam. Het voordeel van deze manier van programmeren is de manier waarop programmeurs gedwongen worden om nette code te schrijven, zodat in een keer te zien is welke operaties bij welke vertakking behoren. De meeste Python-code die wordt geschreven is vrij eenvoudig te begrijpen, ook voor mensen die niet zoveel programmeerervaring hebben. Veelal leest het als pseudo-code, wat omgekeerd ook in het voordeel van Python spreekt; als je pseudo-code hebt, is dit vrij eenvoudig te implementeren. Om de taal zo eenvoudig mogelijk te houden, zijn er maar een tweetal type loops, de For- en While-loop, en is branching alleen mogelijk met behulp van een If statement. De taal bevat namelijk geen switch of goto statements. Een belangrijke manier van opslaan van gegevens in Python zijn dictionaries. Dit zijn ongeordende lijsten waarbij objecten worden aangeroepen met behulp van een sleutel. Het is een soort van array, echter zijn de sleutels niet de standaard integers, maar kan dit 7

Poison; Open Source Image Processor ook bijvoorbeeld een woord zijn. Vandaar de naam dictionary, een van de toepassingen is het opslaan van een woord met een bijbehorend woord in een andere taal. Een programmeur kan commentaar geven in de code op twee verschillende manieren. De eerste is met behulp van het hash karakter (#). Dit is gelijk aan de dubbele slash zoals die in C wordt gebruikt (//) en kan alleen voor één regel commentaar worden gebruikt. Voor een uitgebreidere uitleg kan gebruik worden gemaakt van de documentation strings. Dit zijn drie quotes, single dan wel dubbel (’’’ of ”””). Dit commentaar wordt afgesloten door dezelfde sequentie van karakters [15].

2.2 Gebruikte Modules Naast de standaard aangeboden bibliotheken is het gebruikelijk om ook een aantal andere bibliotheken te gebruiken. Voor Poison, het programma, zijn er drie extra bibliotheken gebruikt. Bij de ontwikkeling ging dit om de volgende versies: - Numarray 1.2.3 voor Python 2.4 - Matplotlib 0.74 voor Python 2.4 - Python Imaging Library (PIL 1.1.5) voor Python 2.4 Poison is later getest op een systeem waarop de volgende versies stonden geïnstalleerd: - Numarray 1.3.2 voor Python 2.4 - Matplotlib 0.81 voor Python 2.4 - Python Imaging Library (PIL 1.1.5) voor Python 2.4

2.2.1 Numarray Numarray [3] zal de basis vormen voor Poison. De afbeeldingen waarmee gewerkt wordt, worden opgeslagen als een array. Afhankelijk van het type afbeelding zal dit een twee- of driedimensionaal array zijn. Als het een grijze afbeelding is zal het een tweedimensionaal array zijn. Dit kan bijvoorbeeld het volgende zijn: [[ 0.47450981 [ 0.47450981 [ 0.44705883 ..., [ 0.61176473 [ 0.62745100 [ 0.61176473

0.49411765 0.49411765 0.51764709

0.50980395 ..., 0.50980395 ..., 0.48235294 ...,

0.52156866 0.52156866 0.52941179

0.50980395 0.50980395 0.53725493

0.44313726] 0.44313726] 0.44705883]

0.62352943 0.60392159 0.62352943

0.61960787 ..., 0.61568630 ..., 0.61960787 ...,

0.59215689 0.60392159 0.59215689

0.59607846 0.60784316 0.59607846

0.59607846] 0.60000002] 0.59607846]]

Dit is de Numarray representatie voor de volgende afbeelding:

Het eerste punt in het array, 0.47450981, is de grijswaarde van het punt helemaal linksonder in de afbeelding. Deze waarde is altijd tussen 0 en 1, en bepaalt de intensiteit

8

Poison; Open Source Image Processor van dat punt. Bij nieuwere versies van Numarray en Matplotlib worden zwart-wit afbeeldingen ingelezen als een kleurenafbeelding waarbij de drie kleurkanalen gelijk worden gesteld. Bij een kleurafbeelding is het iets anders, hier wordt gebruik gemaakt van een driedimensionaal array. In de derde dimensie worden de RGB-waardes opgeslagen. Dit ziet er bijvoorbeeld als volgt uit: [[[ 0.66274512 [ 0.56470591 [ 0.59215689 ..., [ 0.60784316 [ 0.67058825 [ 0.96470588 ..., [ 0.60784316 [ 0.53725493 [ 0.60784316

0.41568628 0.40784314 0.36470589

0.28627452 0.31764707 0.22352941

1. ] 1. ] 1. ]

0.60000002 0.65882355 0.81960785

0.63137257 0.69411767 0.70588237

1. ] 1. ] 1. ]]

0.60000002 0.53333336 0.60000002

0.63137257 0.57647061 0.63137257

1. ] 1. ] 1. ]]]

Deze representatie stelt de volgende afbeelding voor:

Hierbij worden punten in de afbeelding niet weergegeven door één waarde, maar door drie. Dit zijn natuurlijk de RGB-waardes, waarbij de R in dit geval 0.66274512 is, G 0.41568628 en de B 0.28627452. Een belangrijk verschil tussen Matlab en Poison is de manier waarop afbeeldingen worden gerepresenteerd. In Matlab bevindt de oorsprong van de afbeelding zich linksboven, terwijl die in Poison zich linksonder bevindt. Hierdoor worden de assenstelsel anders opgebouwd zoals later wordt uitgelegd. Numarray is enorm uitgebreid, daarom wordt niet alles geïmporteerd, echter alleen de gebruikte modules. Van Numarray zijn dat, naast natuurlijk de hoofdmodule voor de standaard array operaties, de volgende: - random_array: Bij het genereren van ruis is het prettig als dit zo natuurlijk mogelijk gebeurt. Dit houdt in dat een compleet array willekeurig moet worden gegenereerd. Als dit punt voor punt zou gebeuren is dat erg inefficiënt. Numarray biedt de functie random aan, waarbij in de functieaanroep een formaat kan worden meegegeven van een array dat moet worden gemaakt. - mlab: Deze submodule bevat veel operaties zoals die in Matlab ook worden gebruikt. Deze module bevat bijvoorbeeld functies voor het vinden van het

9


-

-

minimum van een array en het optellen van de verschillende elementen in een array. linear_algebra: In de huidige implementatie van Poison wordt alleen de functie inverse gebruikt van deze module. Deze functie inverteert een array zoals dat bij een matrix gebruikelijk is. Uiteraard bevat deze module veel meer handige functies, zoals het vinden van eigenwaarden van een matrix, de singuliere waarde ontbinding en het bepalen van de determinant. nd_image.filters: Deze module bevat de functie convolve, welke gebruikt wordt voor de Gaussische bibliotheek.

2.2.2 Matplotlib Een tweede belangrijke module voor Poison is Matplotlib [4]. Deze module wordt gebruikt voor bijvoorbeeld het weergeven van de afbeeldingen en het maken van plotjes. Helaas heeft Matplotlib standaard alleen ondersteuning voor het inlezen van het Portable Network Graphics (PNG) formaat. Daarom wordt er in Poison een derde module gebruikt, welke verderop wordt besproken. Om Matplotlib gebruik te laten maken Numarray in plaats van Numerics, waar standaard afbeeldingen in worden opgeslagen, moet in het bestand .matplotlibrc in de directory share/matplotlib de verwijzing naar Numerics worden aangepast naar Numarray. Van Matplotlib worden de volgende twee modules gebruikt: - image: Deze module bevat de functie waarmee een Image-object om wordt gezet in een Numarray object. - pylab: Hierin zitten veel nuttige functies. Zo zit hier bijvoorbeeld een goede functie in voor het weergeven van afbeeldingen en een functie voor het maken van plots.

2.2.3 Python Image Library De Python Image Library (PIL) [5] wordt gebruikt voor het inlezen van de verschillende afbeeldingstypen. Omdat Matplotlib standaard alleen met het PNG-formaat overweg kan, wordt PIL gebruikt voor ondersteuning van onder andere de formaten JPEG, BMP en TIFF. Afbeeldingen worden met behulp van PIL ingelezen in een Image-object. Dit formaat is echter erg PIL-specifiek en kan alleen worden gemanipuleerd met de door PIL aangeboden functies. Hoewel deze functies wel uitgebreid zijn, zijn ze niet compleet. Daarnaast bevat PIL geen goede functie voor het weergeven van de afbeeldingen. Daarom wordt het Image-object omgezet naar een Numarray-object met behulp van een ingebouwde functie van Matplotlib.

10


3. Poison De doelstelling van het project was het ontwikkelen van een Open Source Image Processor die gebruikt kan worden voor de cursus Beeldbewerken [6] zoals dat gegeven wordt in het Bachelorprogramma van Informatica. Voor de practica van dit vak wordt momenteel het programma Matlab gebruikt. Dit programma is hiervoor uitstekend geschikt, echter is het te duur voor studenten om thuis te gebruiken. Het zou dan ook gemakkelijk zijn indien er een gratis variant was van het programma waarmee de studenten de opdrachten zouden kunnen maken. Het schrijven van een programma met deze functionaliteit is de opdracht van dit project.

3.1 Ontwerpcriteria Het ideale programma zou minimaal aan de volgende eisen moeten voldoen: 1) De opdrachten van het vak Beeldbewerken kunnen er in worden uitgevoerd. 2) Het is gemakkelijk uit te breiden met nieuwe functies en modules. 3) De code is duidelijk en overzichtelijk. Het moet belangrijk zijn dat ook mensen die niet zoveel programmeerervaring hebben, begrijpen wat er ongeveer gebeurt. 4) Functies moeten zo universeel mogelijk zijn en niet bijvoorbeeld als eis stellen dat invoer 2D moet zijn. 5) Gebruikte variabelen in het programma zijn gemakkelijk in te zien en aan te passen. Criterium 1 is uiteindelijk het criterium waarmee getest kan worden of de functionaliteit van het programma inderdaad is wat verwacht werd. Dit zal gebeuren in de evaluatie van het programma.

3.2 Keuzes De belangrijkste keuze is natuurlijk de taal geweest waarin het programma zou worden geschreven. In de opdracht was al een suggestie gedaan, namelijk Python. Andere mogelijkheden waren bijvoorbeeld Perl en Ruby, echter bleek Python zeer geschikt vanwege een aantal bibliotheken die geschikt waren voor de implementatie. Als algemene referentie voor Python is [7] en [8] gebruikt. Een va de gemaakte keuze is de naam van het programma. De keuze hiervan is gevallen op Poison, wat een anagram is van de eerste letters van Open Source Image Processor met de toevoeging van de letters ‘on’. Een volgende keuze die gemaakt moest worden, was de keuze van de modules die gebruikt zouden worden. Omdat Python zelf geen goede manier heeft om met (grote) arrays overweg te kunnen, is hiervoor een aparte module nodig. Hiervoor zijn twee goede mogelijkheden: - Numerics - Numarray Numarray is de officieuze opvolger van Numerics en is ontwikkeld om beter overweg te kunnen gaan met grote arrays, i.e. arrays met meer dan 20.000 elementen. Aangezien beelden vrij snel meer dan 20.000 elementen bevatten, is de keuze gevallen op Numarray.

11

Poison; Open Source Image Processor Omdat Numarray zelf geen mogelijkheid heeft om beelden in te lezen en weer te geven, is hiervoor een tweede module nodig. Deze module heet Matplotlib en kan gebruikt worden voor het inlezen en weergeven van bijvoorbeeld afbeeldingen en lijnplots. Een nadeel van deze module is dat het standaard alleen overweg kan met het Portable Network Graphics (PNG) formaat, wat de functionaliteit erg zou beperken en er van de gebruiker verwacht zou worden dat hij zelf eerst de afbeeldingen omzet naar een ander formaat. Om toch ondersteuning te kunnen bieden voor andere formaten als TIFF en JPEG, wordt gebruik gemaakt van de module Python Image Library (PIL). Omdat de combinatie van deze twee laatste modules een veelgebruikte is, is er standaard een functie aanwezig in Matplotlib om de ingelezen afbeeldingen van PIL om te kunnen zetten naar een Numarray, waarna er operaties op kunnen worden toegepast. Python is een object georiënteerde taal en bij het werken met beelden is het dan ook logisch om gebruik te maken van objecten om deze beelden te representeren. Hiervoor zijn een aantal mogelijke modellen: - Singleton: Dit object staat op zichzelf en bevat alle functies die gebruikt worden in combinatie met dit object. - Proxy: Dit is een object dat een ander object beschrijft en eventueel uitbreidt. Het is een overkoepeld object dat de functionaliteit uitbreidt door bijvoorbeeld functies toe te voegen en informatie over het beschreven object opslaat. - Chain of Responsibilities: Dit is een ketting van objecten, waarbij standaard het onderste object wordt gebruikt voor operaties. Indien een uit te voeren functie niet in dit onderste object van de keten aanwezig is, zal naar het object worden gekeken wat boven dit object in de keten staat. Op deze manier kan een object met vele andere objecten worden uitgebreid. De keuze voor Singleton leek al vrij snel af te vallen, aangezien het belangrijkste object dat gebruikt wordt Numarray is. Omdat het meestal niet aan te raden is aanpassingen te maken in dit soort objecten, in verband met bijvoorbeeld nieuwe versies en het altijd aan moeten leveren van de complete module, en er wel uitbreidingen van dit object moesten worden gedaan, moest de keuze gebeuren tussen het Proxy-model en het Chain of Responsibilities model. Het Proxy-model heeft als grootste nadeel dat alle functies zoals die zich in het basisobject bevinden opnieuw moeten worden beschreven in het proxy-object. Dit levert veel functies op die maar uit één regel code bestaan, namelijk het aanroepen van de functie die zich in het basisobject bevinden. Een voordeel hiervan is dat de programmeur kan bepalen welke functies een gebruiker kan gebruiken. Aanvankelijk was de keuze gevallen op het Proxy-model. Tijdens de implementatie bleek echter dat de Numarray van zichzelf al zo volledig was, dat er weinig extra functies aan het object zelf hoefden te worden toegevoegd. Hierdoor is er uiteindelijk een bibliotheek ontstaan van functies die in de aanroep van de functie het array/beeld meekrijgen. Het Singleton model is dan ook uiteindelijk het gebruikte model voor het programma. Omdat er veel interactie met een gebruiker moet plaatsvinden, zal er een interface moeten zijn. Deze User Interface (UI) kan een simpele commandoregel zijn waar een gebruiker zijn opdrachten ingeeft, of dit kan een grafische omgeving (Graphical User Interface,

12

Poison; Open Source Image Processor oftewel GUI) zijn. Hoewel het programma vrij eenvoudig kan worden gedraaid vanaf de standaard Pythonshell (IDLE), is er toch gekozen voor een grafische interface om het geheel meer houvast te geven.

3.3 Graphical User Interface De grafische interface van Poison verzorgt de interactie met de gebruiker en zorgt er voor de ingegeven commando’s worden uitgevoerd. Deze interface wordt opgebouwd met behulp van Tk, een standaard bibliotheek die in Python zit. Tk bevat onder andere modules voor tekstvelden, menu’s en knoppen en biedt de mogelijkheid om de verschillende onderdelen te koppelen. De GUI wordt beschreven in de module poisonGUI.py. In afbeelding 1 staat een screenshot van de GUI met uitleg over de verschillende onderdelen van de GUI.

3.3.1 Tekstvelden

Afbeelding 1: De GUI van Poison

Het grootste gedeelte van de interface wordt ingenomen door een drietal tekstvelden. Dit zijn de drie volgende: 1) Command window: Dit tekstveld is het enige veld waarbij gebruikers iets kunnen intypen. Hier kunnen ze opdrachten geven die het programma moet uitvoeren. 2) History window: Hier staan de meest recente opdrachten van de gebruiker. 3) Object window: Dit venster geeft de array objecten weer die de gebruiker heeft ingelezen. De velden zijn ScrolledText widgets. Dit zijn normale Text-widgets, echter dan met de uitbreiding dat er automatisch scrollbalken worden aangemaakt.

13

Poison; Open Source Image Processor Bij het opdrachtscherm zit een koppeling met de entertoets. Dit wil zeggen dat als er op de enter wordt gedrukt, er een event optreedt. Dit event zorgt er voor dat er een functie wordt aangeroepen. De functie die wordt aangeroepen, readcmd, zorgt er voor dat de laatste regel ingegeven tekst wordt uitgelezen en uitgevoerd door de Pythoninterpreter met behulp van het commando exec. Het nadeel van deze functie is dat de uitvoer naar de Shell wordt geprint. Aangezien het de bedoeling is deze uitvoer in Poison te krijgen, wordt de buffer waarnaar uitvoer wordt weggeschreven aangepast naar een andere buffer, welke later gebruikt wordt om de uitvoer naar het opdrachtscherm te printen. Voordat de functie readcmd wordt aangeroepen, wordt er eerst een lijst gemaakt met daarin de variabelen zoals die op dit moment aanwezig zijn. Nadat de functie is uitgevoerd, wordt er wederom een lijst met deze variabelen aangemaakt. Indien deze lijsten verschillen, betekent dit dat er een nieuwe variabele is toegevoegd door de opdracht van de gebruiker. Als dit een Numarray object betreft, wordt hier een Poisonobject van gemaakt en wordt hij toegevoegd aan de lijst van objecten die geprint moeten worden in het objectvenster en indien het commando whos wordt uitgevoerd. Bij elk tekstveld bevindt zich een label om duidelijk te maken wat er in het veld staat.

3.3.2 Menu’s Poison heeft, net als vrijwel elk programma met een GUI, bovenaan in het venster een aantal menu’s staan. Dit zijn de menu’s File, Edit en Help. Deze menu’s worden gemaakt met behulp van de Menu widget welke aangeboden wordt door Tk. De commando’s in de menu’s roepen verschillende functies aan, behorende bij de acties die verwacht wordt. Zo zal copy de geselecteerde tekst kopiëren naar het klembord en zal find een zoekvenster weergeven waarmee een string kan worden gevonden in de opgegeven commando’s en resultaten.

3.3.3 Afbeeldingen Net als in Matlab worden afbeeldingen in een nieuwe venster geopend. Er was een mogelijkheid tot intergratie in de rest van de GUI, echter is dit bijna een project op zichzelf. Op deze manier is het een standaardfunctie van Matplotlib, terwijl bij intergratie in de rest van het programma deze complete code moet worden aangepast.

3.3.4 Implementatie De GUI wordt aangemaakt door in het programma een Poisonmenu-object aan te maken. Op deze manier worden de benodigde variabelen automatisch geïnitialiseerd. Er zijn 3 belangrijke globale variabelen: - poison_dict: Dit is een dictionary van een aantal lokale omgevingsvariabelen en de variabelen zoals deze door de gebruiker worden ingegeven. Deze dictionary wordt aan het begin gelijk gesteld met de locale variabelen, zodat de bibliotheken die worden geïmporteerd ook worden gebruikt voor het uitvoeren van de functies. - clipboard: Clipboard is een variabele waar een String in kan worden opgeslagen door gegevens te kopiëren/knippen. Deze kan vervolgens op een andere plek weer in het programma worden gezet. 14

Poison; Open Source Image Processor -

menu: Dit is een referentie naar het menu zelf. Op deze manier is het voor externe functies mogelijk om bijvoorbeeld tekst naar het menu te schrijven.

Naast deze globale variabelen zijn er ook een aantal instance variabelen, welke bij het menu zelf behoren. Dit zijn de volgende: - objects: Omdat poison_dict ook een hoop extra gegevens bevat, zoals de geïmporteerde bibliotheken, wordt er een extra lijst aangemaakt. Deze lijst bevat alleen maar objecten van het type Poisonobject. Dit is het object dat wordt gebruikt voor de administratie en bevat de gegevens van de verschillende numArrays die er in het geheugen staan. - lastfind: Deze variabele wordt gebruikt om de vorige string op te slaan die werd gebruikt in de Find-functie. Als de gebruiker een zoekopdracht uitvoert, zal deze worden opgeslagen in deze string zodat als de gebruiker de functie Find Again uitvoert, deze de vorige gezochte string nogmaals gaat zoeken. Nadat deze variabelen zijn aangemaakt, vindt er een initialisatie plaats van Tk. Dit object vormt de basis voor alle grafische objecten die eerder zijn beschreven, zoals de tekstvelden en de menu’s. Alle onderdelen worden hieraan bevestigd om ze onderling met elkaar te kunnen combineren. In dit programma wordt gebruik gemaakt van een frame, omdat de opbouw niet standaard te implementeren is. Als de tekstvelden aan een frame worden vastgemaakt, kunnen deze frames onderling weer worden gecombineerd. Zo heeft Poison een frame aan de rechterkant om de twee tekstvelden aan die kant onder elkaar te zetten. Als dit frame vervolgens aan de root (basis) wordt bevestigd, kan deze worden gecombineerd met het linker tekstvlak. Bij elk tekstframe behoort ook een label om aan te geven wat er in dat tekstvlak gebeurt.

3.3.5 Poisonobject Aanvankelijk was het de bedoeling om een compleet eigen object te schrijven en hiermee verder te gaan werken. Dit was vooral omdat Matlab een mogelijkheid had om via het commando ‘whos’ alle variabelen die op dat moment door de gebruiker gedefinieerd waren weer te geven. Zoals reeds beschreven in het hoofdstuk 3.2 Keuzes, waren er drie mogelijke ideeën voor het object. Gaandeweg het project is dit object een administratief object geworden en is Numarray zelf een object geworden naar het Singletonmodel. Het Poisonobject bevat een aantal gegevens over het object dat beschreven wordt. Dit is bijvoorbeeld de naam van het object en de afmetingen van het array dat beschreven wordt. Het object is vrij eenvoudig uit te breiden met meer gegevens, bijvoorbeeld of een afbeelding een kleurenbeeld is.

3.3.6 Poisonfunctions Dit is de primaire bibliotheek voor veel functies van Poison. Vrij weinig functies zoals die aangeboden worden door de extra bibliotheken zijn direct overgenomen. Dit zou namelijk heel veel problemen geven, omdat er dubbele definities van functies kunnen optreden. Zo is bijvoorbeeld de functie imread reeds geïmplementeerd in Matplotlib. Het probleem met deze functie is dat hij alleen overweg kan met het PNG formaat. Deze functie wordt daarom overschreven met een andere implementatie, die gebruik maakt van de mogelijkheid van PIL om afbeeldingen in te lezen, waarna een functie van Matplotlib

15

Poison; Open Source Image Processor deze afbeelding omzet naar een Numarray. Dit wordt gedaan door de module matplotlib.pylab te importen als pyl. Hierdoor dient de functie aangeroepen te worden als pyl.imread. Eenzelfde probleem zou kunnen ontstaan als er bijvoorbeeld functies zijn met veel voorkomende namen. Zo is een functie Random vrij vaak voorkomend. Door alleen functies toe te staan op een beheersbare manier, is te bepalen hoe een bepaalde functie moet worden afgehandeld. Dit kan een oneliner zijn, zoals bijvoorbeeld de functie randn: def randn(x): return pyl.randn(x)

Maar het kan ook bijvoorbeeld een functie zijn met wat extra functionaliteit, zoals imshow: def imshow(image, **kwargs): if (len(image.shape) == 2): pyl.gray() else: pyl.jet() pyl.imshow(image, origin='lower', aspect='preserve', *kwargs) pyl.show()

Hiebij is er functionaliteit toegevoegd doordat grijze afbeeldingen met een andere colormap worden weergegeven dan kleurafbeeldingen. Dit was omdat bij een oudere versie van Numarray en Matplotlib kleurafbeeldingen een andere opbouw hadden die hiermee werd opgevangen. In nieuwere versies is deze controle niet meer nodig en worden zowel kleur- als zwart-witafbeeldingen zonder problemen weergegeven. Naast deze controle voor de aanpassing van de kleurmap wordt de afbeelding op een andere manier weergegeven dan standaard is. De oorsprong staat onder in plaats van boven en de verhouding tussen horizontaal en verticaal wordt bewaard. Dan zijn er nog een aantal functies die niet standaard worden aangeboden door een van de gebruikte bibliotheken. Dit is bijvoorbeeld de functie im2gray, welke kleurafbeeldingen omzet in zwart-wit afbeeldingen: def im2gray(image): if (len(image.shape) == 2): menuwrite("Error: Already a gray valued image\n", '#d53b0b') return r = image[:,:,0] g = image[:,:,1] b = image[:,:,2] grey = zeros([image.shape[0],image.shape[1]]) grey = grey.astype(Float32) grey[:,:] = 0.299 * r + 0.587 * g + 0.114 * b return grey

Ook hiervoor geldt dat in de nieuwe versies van de verschillende modules de functionaliteit gelijk blijft, alleen dient hij nu ook op zwart-wit afbeeldingen te worden toegepast om later met deze afbeeldingen te kunnen werken.

16


3.4 Werking Na het opstarten van het programma kan de gebruiker commando’s ingeven. Deze commando’s lijken in veel gevallen op de commando’s zoals ze ook in Matlab worden gebruikt. Hier volgt een inventarisatie van de verschillende functies zoals deze gebruikt zijn in het practicum beeldbewerken. Practicum 1 Matlab functie Imread Whos Imshow

Poison voorbeeld a = imread(‘kids.tif’) Whos() imshow(a)

Min

min(a)

Max Im2double

max(a) Im2double

Rgb2gray

im2gray(a)

Axis on Bij ingave variabelenaam waarde direct printen

axis(‘on’), axis(‘off’) Print variabele

1:10

arange(1,11)

Plot

plot(d)

17

Opmerkingen

a mag zowel een variabele als een filename zijn Afhankelijk van de input geeft deze functie een waarde of een array terug. Om de minimale waarde van een twee dimensionaal array te krijgen, gebruik je dan ook min(min(a)) Afhankelijk van de gebruikte versies van de verschillende modules, worden afbeeldingen als Floats of Integers ingelezen. Bij oudere versies worden de afbeeldingen als floats ingelezen. De functie zet afbeeldingen om naar floats, de naam van de functie is alleen zo gekozen vanwege de vergelijkbare functie in Matlab. Bij de oudere modules werden grijze afbeeldingen ingelezen als een tweedimensionaal array. In nieuwere versies worden zowel kleur als zwart-wit ingelezen als een driedimensionaal array. Om zowel zwart-wit als kleurafbeeldingen te kunnen gebruiken in bepaalde functies moeten ze eerst met deze functie worden omgezet naar een 2D array. Default on Print is een algemeen gebruikt commando. In tegenstelling tot Matlab wordt uitvoer pas weergegeven als daar expliciet om wordt gevraagd. De tweede waarde is een tot-waarde is, in tegenstelling tot Matlab waar het een toten-met-waarde is. Een belangrijk verschil tussen Matlab en Poison is dat Matlab begint te tellen bij 1

Poison; Open Source Image Processor en Poison bij 0. Dit verschil is te merken bij deze functie. Practicum 2 Sum Randn

sum(a); sum(sum(a)) randn(1)

Inv Ones

inverse(a) ones(10)

For

For a in range(10)

Reshape

Reshape

De input is het aantal random getallen dat moet worden gekozen Input is het aantal enen. Dit kan ook een lijst zijn, zodat de output een array wordt met de waarde van de input als waardes voor de lengtes van de assen. Zeros werkt op eenzelfde manier. For kan alleen gebruikt worden in zelfgedefinieerde functies, niet in Poison zelf

Practicum 3 Length

Length

Floor Ceil linspace

floor(a) Ceil(a) Linspace

Practicum 4 Round round(a) Feval Imfilter Imfilter Imnoise imnoise Exp

Rond af naar dichtst bij zijnde integer

Niet alle ruismogelijkheden van Matlab zijn aanwezig. Momenteel zijn alleen Salt & Pepper en Gaussian beschikbaar.

exp(a)

Practicum 5 Ndgrid ndgrid Sin Cos Quiver Tic/toc

Geeft de grootste waarde van de lengtes van de assen van een afbeelding terug.

Momenteel is de functie alleen beschikbaar waarbij een 2D array wordt gebruikt.

Sin(a) Cos(a) quiver Tic()/toc()

Het is mogelijk om, net als in Matlab, eigen functies en modules te schrijven. Deze functie kan worden geschreven met IDLE, de standaard editor van Python. De bestanden dienen in de directory user te worden gezet, waarna ze kunnen worden ingeladen met behulp van de knop Reload Modules in het menu File. Ook als er een nieuw bestand in de 18

Poison; Open Source Image Processor directory wordt gezet kan deze worden ingeladen met deze menuoptie. Eigen geschreven functies dienen te worden aangeroepen met behulp van <modulenaam>.. Als er bijvoorbeeld een bestand zou zijn met de naam affine.py en deze bevat de functie pv wordt deze uitgevoerd met behulp van affine.pv(). Om in deze modules gebruik te maken van bovenstaande functies is het belangrijk dat er bovenaan in de nieuwe module de volgende regel code staat: from poisonfunctions import *

Er zijn twee belangrijke verschillen tussen Matlab en Poison die zeker bij beeldbewerken voor veel verwarring kunnen zorgen. De eerste is dat in Matlab het eerste element van een array op de indexwaarde 1 staat, waar de eerste waarde in Poison op de indexwaarde 0 staat. Het tweede verschil is dat de assenstelsel omgekeerd staan. De oorsprong van de afbeeldingen in Matlab bevindt zich linksboven, terwijl hij in Poison linksonder staat. Dit levert de volgende assenstelsels op: y

x

x

y Assenstelsel van Matlab

Assenstelsel van Poison

19


20


4. Evaluatie Poison De opdrachten van het vak Beeldbewerken zullen worden gebruikt om de werking van het programma te evalueren. Dit zijn 6 verschillende practica met een uiteenlopende opdracht. Om te evalueren worden in dit hoofdstuk alle practica beschreven en van een aantal practica de commando’s en resultaten van Matlab en Poison naast elkaar gezet.

4.1 Practicum 1 In het eerste practicum werd er kennis gemaakt met Matlab. De verschillende opdrachten bestonden uit het inlezen en weergeven van afbeeldingen. Verder moesten er eenvoudige operaties worden uitgevoerd op de afbeeldingen, zoals het omzetten van afbeeldingen van integer naar dubbel en van kleur naar grijs. Het tweede gedeelte van de opdracht betrof het maken van plots, het werken met arrays en het schrijven van eigen functies. De code voor het practicum is te vinden in Appendix A. De belangrijkste resultaten met verschillen en overeenkomsten worden hieronder besproken. In afbeelding 2 is te zien hoe Matlab het plaatje ‘kids.tif’ weergeeft. Dit is een donker plaatje en lijkt ook niet te kloppen met hoe het plaatje er uit ziet als de afbeelding in een fotobewerkingsprogramma geopend wordt. In afbeelding 3 staat weergegeven hoe de zelfde afbeelding wordt weergegeven in Poison. Hier kloppen de kleuren met wat verwacht wordt. Door dit verschil zullen de antwoorden van Poison en Matlab niet met elkaar overeenkomen.

Afbeelding 2

Afbeelding 3

21


Een van de opdrachten was om van een afbeelding een dwarsdoorsnede te nemen. Omdat in Poison afbeeldingen anders worden opgeslagen, is het belangrijk dat bij het nemen van de doorsnedelijn er een andere offset wordt gebruikt. Dit zal in dit geval de breedte van de afbeelding zijn, minus de plek waar de doorsnede gemaakt moet worden. De resultaten van deze opdracht zijn te zien in afbeeldingen 4 en 5.

Afbeelding 4: Doorsnede van flowers.tif in Matlab

Afbeelding 5: Doorsnede van flowers.tif in Poison

4.2 Practicum 2 In dit practicum werd de kleinste kwadraten methode behandeld. Hierbij wordt een aantal punten willekeurig gegeneerd, waar vervolgens een lijn doorheen moest worden getrokken. Deze lijn werd bepaald met behulp van de kleinste kwadraten methode. Naast het fitten van een rechte lijn moest ook een sinus/cosinus functie benaderd worden.

4.3 Practicum 3 Dit practicum draaide om interpolatie en geometrische operaties die werden toegepast op afbeeldingen. We moesten een functie schrijven die een affine transformatie uitvoert. Dit is een transformatie waarbij punten die op een lijn liggen op dezelfde lijn blijven liggen en het middelpunt van een lijn blijft na de transformatie het middelpunt van de lijn. In dit geval was het de bedoeling om een functie te maken die een rotatie uitvoerde en hierbij de ‘ontbrekende’ punten bepaalde met behulp van interpolatie. De code voor de functies is te vinden in Appendix B. Vanwege de eerder genoemde verschillen tussen de assenstelsels en arrays van Matlab en Poison zijn de resultaten van dezelfde input verschillend.

22


Afbeelding 6: Profiel van cameraman.tif in Matlab

Afbeelding 7: Profiel van cameraman.tif in Poison

In afbeeldingen 6 en 7 zijn de resultaten van de functie Profile te zien. Dit profiel is genomen op de volgende manier: Matlab: hold on; plot(profile(a,156,180,136,200,200,'nearest'),'b') plot(profile(a,156,180,136,200,200,'linear'),'g') hold off;

Poison: plot(affine.profile(a,100,180,120,200,200,'nearest')) plot(affine.profile(a,100,180,120,200,200,'linear'))

Er is in beide afbeeldingen een duidelijk verschil te zien tussen de blauwe lijn, de nearest neighbour intepolatie, en de groene lijn, de bilineaire intepolatie. De affine transformatie heeft ongeveer een zelfde implementatie. Echter bij het uitvoeren van de functie is er een groot verschil zichtbaar vanwege de verschillen tussen de assenstelsels van de twee programma’s, zoals te zien is in tabel 8. Matlab: im=myaffine(a,-50,128,128,-50,128,306,200,200,'linear');

Poison: im=affine.myaffine(a,-50,128,128,-53,128,306,200,200,'linear');

23

Poison; Open Source Image Processor Matlab

Poison

Tabel 8: Uitvoeren van de Affine transformatie levert verschillende resultaten op

4.4 Practicum 4 Deze week moest er een algoritme geïmplementeerd worden dat isodata thresholding op een afbeelding toepaste. Hierbij wordt gekeken naar de waarde van een pixel. Als deze boven een bepaalde waarde (threshold) is, krijgt de pixel de waarde 1, anders 0. Op deze manier vormt zich een binaire afbeelding waarbij bepaalde objecten er uitspringen. Omdat niet elke afbeelding in maar 2 groepen is op te splitsen, was de volgende opdracht om een functie te schrijven die de afbeelding in meerdere groepen kan clusteren. Dit heet k-Means clustering. Ten slotte was er een opdracht waarbij verschillende soorten filters moesten worden beschreven en deze moesten getest worden op verschillende soorten ruis.

4.5 Practicum 5 Practicum 5 omvat de Gaussische functie. Met behulp van de standaard implementatie van de Gaussische functie moesten een aantal Gauassische afgeleiden worden bepaald en toegepast op een afbeelding. De code van een aantal functies zoals die gebruikt worden in dit practicum is te vinden in Appendix C.

24


Afbeelding 9: Matlab uitvoer van functie 11

Afbeelding 10: Matlab uitvoer van functie 11

In afbeeldingen 9 en 10 wordt de volgende functie weergegeven: f(x, y) = A sin(Vx) + B cos(Wy)

(11)

Deze afbeeldingen worden gemaakt met behulp van de volgende regels code. Poison y=arange(-100,101) x=arange(-100,101) [X,Y]=ndgrid(x,y) A=1;B=2;V=6*pi/201;W=4*pi/201; F=A*sin(V*X)+B*cos(W*Y) imshow(F)

Matlab x = -100:100; y = -100:100; [X,Y] = ndgrid (x,y); A=1; B=2; V = 6* pi /201; W = 4* pi /201; F = A * sin ( V * X ) + B * cos ( W * Y ); imshow (x,y,F ,[]);

Hierin zijn een aantal verschillen te zien, zoals de manier waarop een array van optellende waardes wordt gemaakt. Ook zijn er overkomsten te zien, zoals de mogelijkheid van functies om meerdere waardes terug te geven. De Fx en Fy zijn als volgt gedefinieerd: fx = A cos (Vx) V fy = -B sin (Wy) W Helaas is het in Poison (nog) niet mogelijk om Meshplots te maken. Een 2D variant is te vinden onder contour of de functie die de contouren invult: contourf. In afbeelding 12 is een voorbeeld te zien hiervan, in dit geval gegenereerd met behulp van de volgende functie: p = zeros([64,64]) p[32,32] = 1 p = p.astype(Float32) w=gD(p,3,1,0) contourf(w)

Wat hierbij opvalt ten opzichte van de code van Matlab is dat het array is moet worden omgezet naar een Float32 array. Dit is omdat de Floatwaardes die gD terug hoort te geven worden afgekapt naar Integers.

25


Afbeelding 12: Een contourplot van een pulsfunctie geconvolueerd met de eerste afgeleide van de Gaussfunctie in Poison Het resultaat van de gD functie toegepast op de afbeelding cameraman.tif is in afbeelding 13 en 14 te zien, voor respectievelijk Matlab en Poison. Dit betreft de eerste orde afgeleide van de Gauss in de y-richting.

Afbeelding 13: Eerste orde afgeleide in de y-richting in Matlab

Afbeelding 14: Eerste orde afgeleide in de y-richting in Poison

26


5. Gaussische bibliotheek 5.1 Inleiding De Gaussische convolutie wordt gebruikt om ruis in afbeeldingen te verwijderen door deze te blurren. Dit is vergelijkbaar met het mean filter, welke net als de Gaussische convolutie gebruik maakt van de omliggende pixels om een aangepaste waarde voor een pixel te berekenen. Het grootste verschil tussen de twee zijn de gewichten die pixels krijgen toegewezen. Door gebruik te maken van de omgevingspixels van een punt, is het de bedoeling dat waardes die door ruis een abnormale waarde hebben gekregen, worden weg geëffend. Een tweede toepassing van de Gaussische functie zijn de afgeleiden van deze functie. Vanwege de speciale eigenschappen van de functie is een convolutie van een Gaussische afgeleide toegepast op een afbeelding een benadering van de afgeleide van de afbeelding. Door de afgeleide te bepalen, worden er karakteristieke eigenschappen van een afbeeldingen zichtbaar gemaakt. Zo is een van de toepassingen van deze convolutie het zoeken van randen (edge detection).

5.2 Straight Forward De meest standaard manier van de Gaussische convolutie wordt in dit hoofdstuk besproken [9]. De Gaussische kernel is gedefinieerd als: G ( x) =

1

G ( x) = G ( x1 ,..., x d ) =

1

s

x

−

2 2

e 2s ( s 2π ) d Een van de belangrijke eigenschappen van deze functie is dat hij kan worden herschreven op de volgende manier: s

s

−

e

x12 2s

2

...

−

1

e

x12 2s2

= G1s ( x1 )...G1s ( x d )

( s 2π ) ( s 2π ) In plaats van de functie op alle dimensies tegelijk toe te passen, wordt de functies gesplitst over de verschillende dimensies en later gecombineerd. Deze eigenschap geldt ook voor de afgeleide van de functie en zorgt er voor dat er alleen een eendimensionale functie hoeft te worden geïmplementeerd om de convolutie uit te kunnen voeren. d

d

De afgeleiden van de functie kunnen natuurlijk worden bepaald zoals elke afgeleide wordt berekend. Echter kan voor de afgeleide de Hermite polynoom gebruikt worden. Deze wordt berekend met behulp van een recursief algoritme: H 0 ( x) = 1 H 1 ( x) = 2 x H n +1 ( x) = 2 xH n ( x) − 2(n − 1) H n −1 ( x) Gecombineerd met de Gaussische kernel ontstaat de volgende functie: n

⎛ −1 ⎞ ⎛ x ⎞ s (∂ G )( x) = ⎜ ⎟ Hn⎜ ⎟G ( x) ⎝s 2⎠ ⎝s 2⎠ n

s

27


5.3 Interpolatie Beelden f in een computersysteem alleen kunnen worden gerepresenteerd als een discrete verzameling pixels F. De kernel functie W wordt meestal gerepresenteerd als een gesamplede versie van de analytisch bekende kernel functie w. Vervolgens wordt de convolutie van de twee berekend met behulp van F*W. Dit is echter niet altijd de best mogelijke benadering voor alle mogelijke w. Om een betere benadering te krijgen, is het mogelijk om de afbeelding te interpoleren en hier vervolgens de convolutie op toe te passen [10].

5.4 Recursief Omdat de Gaussische convolutie zoveel gebruikt wordt in het gebied van beeldbewerken, zijn er naast de Straightforward aanpak nog een aantal manieren. Een hiervan is het recursieve algoritme. Zowel door Deriche [11] als Young en Van Vliet [12][13] is hier over geschreven. Het grote voordeel van deze functie is dat hij snel is. Het nadeel van deze implementatie is dat het een benadering is. Het idee van dit algoritme is dat er door de afbeelding wordt heengelopen met bepaalde constanten als input. Deze waarden worden teruggeschreven naar dit array, waardoor ze als invoer voor een volgende waarde worden gebruikt. Op deze manier wordt er vier keer door het array heengelopen, een keer heen en terug over de y-as en een keer heen en terug over de x-as. De functie van Van Vliet is gebaseerd op de volgende benadering van de Gauss uit [14]: −t 1 1 g (t ) = e2 = + ε (t ) 2 a0 + a2 t + a4 t 4 + a6 t 6 2π met a 0 = 2.490895 a 2 = 1.466003 a 4 = −0.024393 a 6 = 0.178257 en de fout ε (t ) < 2.7 × 10 −3 . Bij de maximale waarde van g(t) (bij t = 0) is deze fout kleiner dan 0,68%. Er is ook een 10e orde polynomiale benadering beschikbaar, echter bleek dat deze polynoom voldoende was. Na een herschrijving met behulp van de Fourier transformatie wordt de functie geschreven als volgt: Gq ( s) = G L ( s )G R ( s)

Hierin wordt de functie gesplitst in twee gedeeltes. De ene helft stelt de polen voor in het linker gedeelte van het vlak en de andere helft de polen in de rechterhelft van het vlak. Deze kunnen worden geschreven als: A1 GL (s) = (1.1668 + qs )(3.20373 + 2.21567qs + q 2 s 2 ) A1 G R ( s) = (1.1668 − qs )(3.20373 − 2.21567qs + q 2 s 2 )

28

Poison; Open Source Image Processor De differential equation kan worden herschreven naar een difference equation met behulp van een bilineaire transformatie. Het probleem met deze transformatie is dat er nullen ontstaan in nieuwe vergelijkingen. Daarom wordt de transformatie uitgevoerd met de backward difference techniek. Deze techniek geeft de volgende functies: A2 H L ( z) = −1 b0 − b1 z − b2 z − 2 − b3 z −3 H R ( z) =

A2 b0 − b1 z − b2 z 2 − b3 z 3 1

met b0 = 1.57825 + 2.44413q + 1.4281q 2 + 0.422205q 3 b1 = 2.44413q + 2.85619q 2 + 1.26661q 3

(

b2 = − 1.4281q 2 + 1.26661q 3

)

b3 = 0.422205q 3 Hierbij is HL(z) de voorwaartse filterfunctie en HR(z) de achterwaartse filterfunctie, welke op de volgende manier geïmplementeerd kunnen worden: forward : w[n] = Bin[n] + (b1 w[n − 1] + b2 w[n − 2] + b3 w[n − 3]) / b0

backward : out[n] = Bw[n] + (b1out[n + 1] + b2 out[n + 2] + b3 out[n + 3]) / b0 Hierin is B een normalisatiefactor welke als volgt gedefinieerd is: b + b2 + b3 B = 1− 1 b0 Voor de eerste orde afgeleide wordt de forward functie vervangen door de volgende functie: forward: w[n] = ( B / 2)(in[n + 1] − in[n − 1]) + (b1 w[n − 1] + b2 w[n − 2] + b3 w[n − 3]) / b0 Voor de tweede orde afgeleide worden de forward en backward functies vervangen door de volgende functies: forward: w[n] = B(in[n] − in[n − 1]) + (b1 w[n − 1] + b2 w[n − 2] + b3 w[n − 3]) / b0 backward: out[n] = B ( w[n + 1] − w[n]) + (b1out[n + 1] + b2 out[n + 2] + b3 out[n + 3]) / b0

5.5 Fourier Een ander algoritme dat kan worden gebruikt, wordt uitgevoerd met behulp van de Fourier Transformatie [9]. Het voordeel van deze transformatie is dat hij voor kleine schaal erg nauwkeurig is en voor grote schaal erg snel. Het nadeel is dat bij kleine schaal het algoritme niet erg snel is en bij grote schaal niet erg nauwkeurig. Het principe van het algoritme is dat we van een discrete afbeelding L de discrete Fourier Transformatie berekenen. Het antwoord noemen we Lˆ . Dit doen we ook voor de 29

Poison; Open Source Image Processor convolution kernel W die we gebruiken, wat ons Wˆ oplevert. Als we deze twee vervolgens puntsgewijs vermenigvuldigen, komen we op het benodigde resultaat. In een schema is dit als volgt: R = L *W M M M DFT M M M Rˆ = Lˆ * Wˆ

5.6 Implementatie In dit project zijn twee implementaties gedaan van Gaussische functies. Dit zijn de Straightforward Gauss en de Recursieve Gauss van Van Vliet.

5.6.1 Straightforward De implementatie van de Straightforward Gauss bestaat uit 3 functies en is te vinden in GaussianDerivatives.py: gD

Deze functie wordt standaard aangeroepen als er een Gaussische convolutie op een afbeelding wordt toegepast. Vanuit deze functie wordt de GaussianDerivativeFunction aangeroepen om de Gauss te berekenen. De input is de afbeelding, een lijst van schalen (voor elke as 1) en een lijst van ordes van afgeleiden. Als optie kan er een aangepaste vermenigvuldigingsfactor voor de schaal worden meegegeven, waardoor het aantal omgevingspixels dat wordt gebruikt voor de berekening van een pixel, wordt vergroot. Een tweede optie is de manier waarop er met het borderprobleem wordt omgegaan. Door de Gauss gebruik maakt van de omgevingspixels zit je bij de rand met een probleem. Hier heb je namelijk geen pixels aan een van de zijkanten. Hiervoor zijn 4 mogelijke oplossingen: •

Gebruik maken van een constante: De onbekende pixels krijgen een constante waarde, bijvoorbeeld 0.

•

Herhaling van de buitenste pixel (‘nearest’): De onbekende pixels krijgen de waarde van de randpixel waar ze het dichtst bij liggen.

•

Reflectie: De afbeelding wordt bij de randen gespiegeld. Oftewel, verder bij de rand naar buiten gaan is hetzelfde als vanaf de rand verder naar binnen gaan.

•

Wrapping: De afbeelding wordt bij de randen herhaald. Als je aan de bovenkant van een afbeelding de waarde van de pixel wilt weten, krijg je de waarde van de pixel aan de onderkant van de afbeelding terug.

HermiteH

Deze functie implementeert het Hermite algoritme zoals deze eerder werd beschreven.

30

Poison; Open Source Image Processor GaussianDerivativeFunction

Deze functie implementeert de volgende functie: n

⎛ −1 ⎞ ⎛ x ⎞ s (∂ G )( x) = ⎜ ⎟ Hn⎜ ⎟G ( x) ⎝s 2⎠ ⎝s 2⎠ n

s

Zoals eerder beschreven in het hoofdstuk Straightforward.

5.6.2 Recursief Het recursieve algoritme van Van Vliet is geïmplementeerd in recursivevanvliet.py. Momenteel is de functie alleen beschikbaar voor een tweedimensionale afbeelding. De functie begint met het initialiseren van de waardes q, q2 en q3. Hierna krijgen vervolgens de b0, b1, b2 en b3 de correcte waardes toegewezen, waarna tenslotte B kan worden geïnitialiseerd. Er worden een aantal tijdelijk arrays aangemaakt ter grootte van de afbeelding. Hierna worden de eerste 3 punten berekend. Dit gebeurt apart van de rest, omdat anders eerdergenoemd probleem met de randen optreedt. De manier waarop dit probleem wordt aangepakt is op de ‘nearest’ manier, oftewel de waarde van de buitenste pixel wordt gebruikt als een punt buiten de het array valt. Hierna wordt er twee keer door het array heengelopen terwijl de filterfuncties worden toegepast. Dit gebeurt ook op de x-as. Afhankelijk van de orde welke berekend moet worden, worden de arrays op een andere manier berekend.

5.7 Resultaten We willen twee dingen testen: 1) Is de benadering van het recursieve algoritme goed genoeg ten opzichte van de standaard implementatie. 2) Welk algoritme werkt sneller. Om het eerste punt te testen, plotten we voor verschillende schaal de Gauss voor beide algoritmes. Deze resultaten zijn te zien in afbeeldingen 15 tot en met 17.

Afbeelding 15: De blauwe lijn is de recursieve Gauss, welke een benadering is van de groene Straightforward Gauss

31


Afbeelding 16: Eerste orde afgeleide van de Gauss. De blauwe lijn is de recursieve functie, de groene de straightforward.

Afbeelding 17: Tweede orde afgeleide van de Gauss. De blauwe lijn is de recursieve functie, de groene de straightforward.

De resultaten zijn gegenereerd met een schaal van 15 en genormaliseerd naar 1.

32

Poison; Open Source Image Processor Voor het meten van de snelheid van de functies, wordt er door een loop heen gelopen die telkens een hogere schaal gebruikt voor het berekenen van de Gauss functie. Hierbij maakt het niet zoveel uit welke invoerwaarde gebruikt wordt. Van elke berekening wordt er een tijdmeting gedaan, wat aan het eind uitgezet wordt in een grafiek. Deze grafiek is te zien in afbeelding 18.

Afbeelding 18: Tijdmetingen van de verschillende methodes van Gaussberekening. De groene lijn is het recursieve algoritme, de blauwe de straightforward aanpak. Zoals te zien is, wordt het recursieve algoritme op den duur sneller dan de Straighforward implementatie. In de grafiek zijn schalen gebruikt die in de praktijk nooit zullen worden gebruikt, maar in dit geval was het om aan te tonen dat het recursieve algoritme een complexiteit heeft van O(1) terwijl het straighforward algoritme een complexiteit heeft van O(N). Indien het recursieve algoritme geoptimaliseerd zou worden, door het bijvoorbeeld in een taal te schrijven die sneller is, zoals Pyrex of C, zal het algoritme bij een kleinere schaal al sneller zijn.

33


34


6. Conclusie Poison doet grotendeels wat het moet doen, echter kunnen er natuurlijk nog een aantal dingen aan verbeterd worden. Om een paar punten te noemen: - Numarray objecten die worden ingelezen, komen in de objectlijst te staan. Als er vervolgens een aanpassing aan dit object komt, zoals een ander type of formaat, wordt dit niet doorgevoerd. - Bepaalde functies hebben in hun standaard implementatie veel mogelijkheden tot instellen. Door de tussenlaag die Poison aanbrengt gaan een aantal van deze opties verloren. - Veel functies zijn geschreven voor het practicum. Dit maakt ze erg taakspecifiek en zal bij andere input wellicht niet teruggeven wat verwacht wordt. Zo is de ndgrid functie gedefinieerd als zijnde een functie die een grid van elke dimensie kan teruggeven, terwijl de functie in Poison alleen maar 2D aan kan. - Bibliotheken die door gebruikers zelf worden gedefinieerd in de directory user moeten worden aangeroepen met behulp van de modulenaam en bij wijzigingen in deze bestanden moeten ze door de gebruiker zelf opnieuw worden geladen. In Matlab wordt dit automatisch gedaan. - Er missen veel menufuncties, zoals Opslaan en Ongedaan Maken. De keuze was gemaakt om eerst de aandacht te richting op de opdracht en later eventueel wat uitbreidingen hier aan te doen. Vanwege de uitgebreide extra opdracht is dit er echter niet van gekomen. - De imshow-functie werkt niet naar behoren. Zo worden er grote stukken wit zichtbaar indien een afbeelding niet volledig in het standaardformaat van het canvas past en kloppen de assen naast de afbeeldingen soms niet met de waardes zoals deze in het array staan. Dit ligt niet aan de implementatie van Poison, maar het zou natuurlijk wel prettig zijn indien dit correct werkt. - Conversies tussen verschillende typen moeten expliciet gebeuren, waar dit in Matlab impliciet gebeurt. Zo zal het toewijzen van een Float aan een array van Integers resulteren in een afkapping van de Float. Ondanks deze punten van verbetering, is de doelstelling van het project geslaagd, namelijk een Open Source Image Processor te maken. Ook als gekeken wordt naar het ideaalbeeld van de opdracht, zoals deze beschreven werd in hoofdstuk 3.1, lijken veel van deze punten gehaald te zijn: 1) De opdrachten van het vak Beeldbewerken kunnen er in worden uitgevoerd. Dit blijkt geen enkel probleem, de opdrachten kunnen worden uitgevoerd, waarbij veel van de code is terug te vinden in de appendices. 2) Het is gemakkelijk uit te breiden met nieuwe functies en modules. Door een mogelijkheid aan te bieden voor gebruikers om in een aparte directory nieuwe modules te zetten, is het gebruiken van eigen functies zeer eenvoudig. 3) De code is duidelijk en overzichtelijk. Het moet belangrijk zijn dat ook mensen die niet zoveel programmeerervaring hebben, begrijpen wat er ongeveer gebeurt.

35

Poison; Open Source Image Processor Deze eis werd al bijna afgedwongen door de keuze van de taal. Python kan niet werken zonder goede indentie, waardoor de code vanzelf overzichtelijk wordt. Bovendien schrijft de code bijna als pseudocode, wat ook voor mensen die niet dagelijks programmeren begrijpelijk is. 4) Functies moeten zo universeel mogelijk zijn en niet bijvoorbeeld als eis stellen dat invoer 2D moet zijn. Deze eis wordt niet volledig bereikt, doordat een aantal functies specifiek zijn voor het practicum beeldbewerken. 5) Gebruikte variabelen in het programma zijn gemakkelijk in te zien en aan te passen. Ondanks de poging om variabelen die worden ingelezen weer te geven in een eigen tekstveld, gaat het nut een beetje verloren doordat bij het aanpassen van de data dit niet wordt geüpdate. Wellicht kan dit in een volgende versie worden aangepast door de variabelen voor en na het uitvoeren van een functie met elkaar te vergelijken, om te kijken welke gewijzigd zijn. Een nieuwere versie van Python zou kunnen worden geschreven met behulp van Pyrex om het geheel sneller te maken. Met Pyrex kunnen bestanden op een C-manier worden gecompileerd. Een van de grootste verschillen tussen beide programma’s is natuurlijk de andere assenstelsels. Er kan wel geprobeerd worden om de assenstelsels van Matlab te emuleren, echter is het wellicht slimmer om de andere conventies van Matlab te laten voor wat het is en uit te gaan van het assenstelsel van Poison. Er is nog veel werk te doen bij de Gaussische bibliotheek. Bij de reeds geïmplementeerde Straightforward methode is weinig meer aan te passen. Bij het recursieve algoritme kan echter nog functionaliteit worden toegevoegd. Op dit moment is het borderprobleem in deze functie opgelost door de buitenste pixelwaarde te nemen, de nearest aanpak. Er zou gebruik kunnen worden gemaakt van padding om bij de randen bijvoorbeeld reflectie of wrapping toe te passen. De resultaten van het recursieve functie blijken in de praktijk goed te werken, de resultaten van de Gauss toegepast op een afbeelding geeft eenzelfde resultaat als de Straightforward Gauss. Als we echter gaan kijken hoe de Gaussfuncties zich naast elkaar verhouden, lijken ze, zeker in de tweede orde afgeleide, niet op veel punten overeen te komen. Voor dit probleem is verder onderzoek noodzakelijk. Wellicht komt het door een fout in de implementatie van het algoritme, of door een fout in de claim van Van Vliet en Young dat de foutmarge kleiner is dan 0,68%. Ondanks dat de snelheid van het recursieve algoritme erg laag is, is hij wel constant met een grotere schaal. Dit is natuurlijk een groot voordeel ten opzichte van het Straightforward algoritme, welke bij een grotere schaal langzamer wordt. In dit geval wordt de recursieve Gauss pas bij een schaal van 1500 sneller, wat in de praktijk niet

36

Poison; Open Source Image Processor gebruikt zal worden. Als we echter een snellere taal zouden gebruiken zal dit al bij een kleinere schaal het geval zijn.

37


38


7. Referenties 1) http://www.mathworks.com/products/matlab/ Bezocht op 31 mei 2005. 2) http://www.python.org/Quotes.html 3) http://www.stsci.edu/resources/software_hardware/numarray Bezocht op 20 juni 2005 4) http://matplotlib.sourceforge.net/ Bezocht op 20 juni 2005 5) http://www.pythonware.com/products/pil/ Bezocht op 20 juni 2005 6) http://staff.science.uva.nl/~rein/WebWiki/UvA-MachineVision/WelcomePage.html Bezocht op 20 juni 2005 7) Mark Lutz, Programming Python, 2nd Edition, ISBN: 0-596-00085-5, O'Reilly & Associates Inc. 8) http://www.python.org Bezocht op 20 juni 2005 9) R. van den Boomgaard, Algorithms for Linear Scale Space, januari 2004, http://staff.science.uva.nl/~rein/production/Educational/GaussConvolutions4.pdf Bezocht op 20 juni 2005. 10) Rein van den Boomgaard, Rik van der Weij. Gaussian Convolutions; Numerical Approximations based on Interpolation. In Scale-Space 2001. 2001. 11) Rachid Deriche, Recursively Implementing the Gaussian and its Derivatives, Proceedings Second Internation Conference on Image Processing, 1993 12) Lucas van Vliet, Ian Young, Piet Verbeek. Recursive Gaussian Derivative Filters, in the Proceedings of the 14th International Conference on Pattern Recognition, Volume 1, pagina 509, 1998. 13) I.T. Young, L. van Vliet, Recursive Implementation of the Gaussian Filter, Signal Processing 44, 1995, pagina 139-151 14) M. Abramowitz, I.A. Stegun, Handbook of Mathematical Functions, Dover, New York, 1965 15) http://en.wikipedia.org/wiki/Python_programming_language Bezocht op 21 juni 2005

39


Appendix A a = imread('kids.tif') whos imshow(a) b = im2gray(a) minval = min(min(b)) maxval = max(max(b)) c = 1/maxval * b # Overbodige operatie, verdeling is reeds correct a=imread('flowers.tif') a=im2gray(a) imshow(a) print a[300,300] # Vanwege het verschil met de assen een a[300,300] = 1 # andere waarde imshow(a) v = array([8,5,1,9]) x = [1,3] # Beide aanroepen kunnen print v[x] # Andere output. Bij x = [0,2] zou dit wel gelijk zijn v[x]=[11,34] print v print arange(1,10) # Tot in plaats van tot en met print arange(100,10,-15) print a[arange(299,302),arange(299,302)] # In numarray wordt op deze manier een diagonaal geprint. Oftewel a[299,299], # a[300,300], etc.

40


Appendix B from poisonfunctions import * """ inImage is used in practicum 3 """ def inImage(size, x, y): if (x - 1 > size[0] or x < 0): return 0; if (y - 1> size[1] or y < 0): return 0; return 1 """ pixel value at real coordinates """ def pv (image, x ,y ,method ): if (len(image.shape) != 2): menuwrite("Error: Invalid image. Use im2gray function to convert color" + "images to grayvalued images\n") # Check to see if the coordinates are within the borders of the image if (inImage( image.shape , x, y)): # If so, do the interpolation """ If the method is nearest, we have to find the nearest neighbour. We do this by rounding the x and y values and return the value of this pixel """ if(method == 'nearest'): try: x = int(round(x)) y = int(round(y)) return image[x,y] except: return 0.0 """ If the method is lineair, we have to give a calculated value for the pixel at that position. """ if(method == 'linear'): """ First we get the floor-value and ceiling-value for the desired coordinates. This way we get integers and can retrieve the values of the corresponding coordinates """ x1 = int(floor(x)) x2 = int(ceil(x)) y1 = int(floor(y)) y2 = int(ceil(y)) """ If the floor and ceil-value are the same, it must mean we already had an integer and we don't have to interpolate """ if(x1 == x2):

41

Poison; Open Source Image Processor try: interpolx1 = image[x1,y1] interpolx2 = image[x1,y2] except: return 0.0 else: """ Else we get the values for the neighbours of the point we're looking for. We first do this for the y1 and next for the y2, and then interpolate between those values """ try: temp1 = image[x1,y1] temp2 = image[x2,y1] """ We apply the interpolation-function """ interpolx1 = (x-x1)*temp2 + (x2-x)*temp1 """ We do the same for y2 """ temp1 = image[x1,y2] temp2 = image[x2,y2] interpolx2 = (x-x1)*temp2 + (x2-x)*temp1 """ If y1 and y2 are the same, then so are interpolx1 and interpolx2. So we don't have to interpolate """ except: return 0.0 if(y1 == y2): return interpolx1; """ Else we apply the interpolation-function """ else: return (y-y1)*interpolx2 + (y2-y)*interpolx1 else: # We return a constant if the point is out of range return 0.0 """ Profile of an image along a straight line in N Points """ def profile(image, x0, y0, x1, y1, N, method): x = linspace(x0, x1, N); y = linspace(y0, y1, N); line = zeros(len(x)).astype(Float32) for i in range(len(x)): line[i] = pv(image, x[i], y[i], method) return line # im=myaffine(a,-50,128,128,-50,128,306,200,200,'lineair'); def myaffine(image, x0, y0, x1, y1, x2, y2, M, N, method): r = zeros([M, N]).astype(Float32); # allocate new image of correct size #calculate A,..,F X = array([[1,1,1],[M,1,1],[1,N,1]]);

42

Poison; Open Source Image Processor x = transpose([[x0,x1,x2]]) # Unfortunately Numarray does not support the Matrix Left Division temp = matrixmultiply(transpose(X),X) temp = matrixmultiply(inverse(temp),transpose(X)) ABC = matrixmultiply(temp,x) A = ABC[0][0]; B = ABC[1][0]; C = ABC[2][0]; y = transpose([[y0, y1, y2]]) DEF = matrixmultiply(temp,y) D = DEF[0][0]; E = DEF[1][0]; F = DEF[2][0]; for xa in range(M): for ya in range(N): # calculate x and y x = A*float(xa)+B*float(ya)+C; y = D*float(xa)+E*float(ya)+F; r[xa, ya] = pv(image, x, y, method); return r def plotParallellogram(x0, y0, x1, y1, x2, y2): y3 = y1+y2-y0; x3 = x1+x2-x0; pyl.plot ( [ y0 , y1 , y3 , y2 , y0 ] , [x0 , x1 , x3 , x2 , x0 ], color='y',linewidth=2)

43


Appendix C from numarray import * from poisonobject import * from poisonGUI import *

""" gauss1d calculates the gaussian for a one dimensional array according to a given scale """ def gauss1D(s): """ scale """ if s <= 0: menuwrite("ERROR: Scale has to be bigger than 0\n", '#d53b0b') return M = ceil(2.5 * s) """ Get the length and width """ x = arange(-M,M + 1) """ Execute the gaussian function """ t = exp(-power(x,2)/(2*power(s,2))) """ Normalize """ t = t / sum(sum(t[:])) return(t)

def gauss(s): """ scale """ if s <= 0: menuwrite("ERROR: Scale has to be bigger than 0\n", '#d53b0b') return M = 2.5 * s; N = 2.5 * s; """ Get the length and width """ x = arange(-M,M + 1) y = arange(-N,N + 1) """ Create the grid """ [X,Y] = ndgrid(x,y);

44


""" Convert to float, else we get strange results """ X = X.astype(Float32) Y = Y.astype(Float32) """ Execute the gaussian function """ t = exp(-(power(X,2)+power(Y,2))/(2*pow(s,2))) """ Normalize """ t = t / sum(sum(t[:])) """ Convert the 2d array to an image in greyscale """ return(t)

""" gD is the basic gaussian function, with a possibily to define a way to handle borders """ def gD(image, sigma, iorder, jorder, mode='nearest'): """ iorder is the i-order derivative in the y direction jorder is the j-order derivative in the x direction """ if (not(len(image.shape) == 2)): menuwrite("Error: Only works on gray valued image.\nUse the" + " im2gray() function to convert.\n", '#d53b0b') return """ Choose N according to the scale """ N = ceil(2.5 * sigma) x = arange(-N , N + 1) y = arange(-N , N + 1) """ Check the value of the order """ """ 0-order means we don't have the multiply the result with a certain value """ if iorder == 0: multi = gauss1D(sigma) """ With a 1st order derivative we have to multiply the result with the value -x/sigma^2 """ elif iorder == 1: multi = -x/(power(sigma,2)) multi = multi * gauss1D(sigma) """ With a 2nd order derivatie we have to multiply the result with the value x^2/sigma^4)-1/sigma^2 """

45

Poison; Open Source Image Processor elif(iorder == 2): multi = ((power(x,2)/power(sigma,4))-(1/power(sigma,2))) * gauss1D(sigma) else: """ A not supported derivative value """ menuwrite("Error, derivatives higher than 2nd order are not supported", color='#d53b0b'); return -1 """ We do the same for the jorder """ if(jorder == 0): multj = gauss1D(sigma) elif(jorder == 1): multj = -y/(power(sigma,2)) * gauss1D(sigma) elif(jorder == 2): multj = ((power(y,2)/power(sigma,4))-(1/power(sigma,2))) * gauss1D(sigma) else: menuwrite("Error, derivatives higher than 2nd order are not supported", color='#d53b0b'); return -1; """ Now we convolve the result """ H = zeros([image.shape[0], image.shape[1]]) H = H.astype(Float32) H2 = zeros([image.shape[0], image.shape[1]]) H2 = H2.astype(Float32) for i in range(image.shape[1]): H[:,i] = imfilter(image[:,i], multj, bordertype=mode) for i in range(image.shape[0]): H2[i,:] = imfilter(H[i,:], multi, bordertype=mode) return H2

46

Poison; Open Source Image Processor

Recommend Documents