Hardware/Software Codesign with SystemC: Practicum Opdracht 1

© Harry Broeders.

Deze pagina is bestemd voor studenten van de Haagse Hogeschool - Faculteit Technologie, Innovatie & Samenleving groep E-EMSYS.

Het is de bedoeling dat je 2 weken met deze opdracht bezig bent, 4 uur op het practicum en 4 uur daarbuiten.

Opdracht 1a

We gaan eerst kennismaken met SystemC aan de hand van deze handleiding. We beginnen met een voorbeeld op een laag abstractieniveau (het gate-level abstractie niveau) omdat dit eenvoudig te begrijpen is. Bedenk wel dat de "kracht" van SystemC juist het modelleren op een hoog abstractieniveau is! Maak ook de oefening die in de handleiding staat.

Inleiding

Bij deze practicumopdracht gaan we een beeldbewerking algorithme onderzoeken en implementeren. Bij veel beeldbewerking applicaties is het nodig bepaalde objecten in een beeld te herkennen. Een voorbeeld van zo'n applicatie is OCR (Optical Character Recognition) wat bijvoorbeeld gebruikt wordt om ingescande documenten om te zetten naar text bestanden of om numberborden te herkennen. Een basisbewerking voor beeldbewerking algoritmen die objecten in een beeld herkennen (zoals OCR) is "binarization", ook wel "thresholding" genoemd. Een binarization algoritme zet een grijswaarde plaatje met 256 mogelijke grijswaarden (0..255) om in een zwart/wit plaatje met maar 2 waarden: zwart (0) en wit (1 of 255). In dit plaatje kunnen dan vervolgens objecten zoals lijnen en letters relatief eenvoudig herkend worden. Een van de meest gebruikte binarization algorithmen is Otsu's method. Bij deze methode wordt een zogenoemde global threshold bepaald door de "within-class variance" te minimaliseren of door de "across-class variance" te maximaliseren. Deze methode is eenvoudig om te implemeneteren, werkt erg snel (vergeleken met andere methoden) en werkt goed als er een gelijkmatige belichting is, zoals bij "flatbed scanners".

Otsu's methode werkt in 3 stappen:

1. Van de afbeelding wordt een histogram gemaakt. Dit histogram geeft weer met welke waarschijnlijkheid elke grijswaarde voorkomt. Dit is eenvoudig te bepalen door te tellen hoe vaak elke waarde voorkomt (de frequentie van elke grijswaarde) en vervolgens deze frequentie te delen door het totale aantal pixels.
2. Met behulp van dit histogram wordt er een threshold waarde (grenswaarde) berekend waarbij de "within-class variance" minimaal is (dan is de "across-class variance" maximaal).
3. Elke pixel uit de afbeelding wordt vervolgens vergeleken met deze threshold waarde en als de grijswaarde lager is dan de threshold dan wordt de pixel zwart (0) gemaakt, anders wordt de pixel wit (1 of 255) gemaakt.

Op wikipedia kun je meer informatie vinden:

• http://en.wikipedia.org/wiki/Thresholding_%28image_processing%29 .
• http://en.wikipedia.org/wiki/Otsu%27s_Method .

De volgende presentatie geeft een goede beschrijving van Otsu's methode:

• http://liama.ia.ac.cn/wiki/_media/projects:pal:image_binarization_using_otsu_method_20090420_.pdf . Deze link is dood (6-12-2012) maar ik had nog een kopietje: ppsx/image_binarization_using_otsu_method_20090420.ppsx .

Om het binarization algoritme te kunnen implementeren in C++ moeten we grijswaarden plaatjes kunnen inlezen en wegschrijven. Het is handig om daarbij gebruik te maken van een eenvoudig formaat wat dan indien gewenst naar een complexer formaat (zoals .jpg of .png) omgezet kan worden. Ik heb gekozen om plaatjes te gebruiken die zijn opgeslagen in het portable graymap (.pgm) formaat. In dit formaat is het mogelijk om de informatie als ASCII karakters op te slaan. Dit maakt het heel eenvoudig om plaatjes in dit formaat in te lezen en weg te schrijven. Ook kunnen deze plaatjes eenvoudig via een seriële verbinding verstuurd worden.

Je kunt .pgm files inlezen en wegschrijven vanuit C++ met de door mij geschreven class PGM_Image. Deze class is geïmplementeerd met behulp van functies die zijn geschreven door John Burkardt. Het gebruik van deze class wijst hopelijk zichzelf. Omdat bij Otsu's method de lengte en breedte van het plaatje niet van belang zijn heb ik daar geen vraag-memberfuncties voor gemaakt. Je kunt de class declaratie vinden in pgma_io.h  en de implementatie in pgma_io.cpp . De class PGM_Image beschikt over een random access iterator interface waardoor objecten van deze class bewerkt kunnen worden met de algorithmen uit de C++ standaard.

Test plaatjes

Om het SystemC model te testen hebben we test plaatjes nodig. In de onderstaande tabel staan enkele testplaatjes en de bijbehorende waarde van de threshold die met de Otsu methode bepaald is.

De threshold values zijn bepaald met het volgende MATLAB programma:

for i=1:7;
    image = imread(strcat('input', int2str(i), '.pgm'));
    level(i) = graythresh(image);
    imageBW = im2bw(image,level(i));
    figure, imshow(imageBW)
end
threshold = ceil(level*256)

Je ziet dat je in MATLAB op een heel hoog abstractieniveau kunt werken. Otsu's method is aanwezig in de Image Processing Toolbox van MATLAB.

SystemC model

Op het internet heb ik 4 verschillende implementaties gevonden van Otsu's methode. Deze implementaties heb ik geïmplementeerd in het volgende SystemC model: main.cpp . 2 van de 4 gevonden implementaties blijken niet de goede threshold waarde te bepalen! Wat maar weer eens bewijst dat je niet alles moet geloven wat je op internet vindt ;-)

Opdracht 1b

Maak een tekening van het door mij gemaakte SystemC model. Teken de verschillende subsystemen met hun poorten en de verbindingen daartussen. Geef duidelijk aan of een poort een input of output poort is. Geef ook het type van de data die over de verbinding "loopt" weer in je tekening.

Opdracht 1c

In de implementatie IMPL4 die je kunt vinden op http://www.labbookpages.co.uk/software/imgProc/otsuThreshold.html  wordt gebruik gemaakt van een frequentiehistogram in plaats van een probabilityhistogram. Verifier met behulp van het SystemC model dat IMPL3 en IMPL4 beide correct werken met een frequentiehistogram. Delen door size in de module Histogram_maker is dus overbodig.

Verwijder de twee niet werkende implementaties uit het model en pas het model aan zodat op de verbinding tussen de Histogram_maker en de Threshold_finder een histogram met integers in plaats van een histogram met floating point getallen wordt doorgegeven.

Opdracht 1d

Bepaal welk van de twee implementaties je wil gaan implementeren (bij opdracht 2) op het DE2-70 bord. Kies als criteria de conversiesnelheid/pixel. Bedenk zelf hoe je kunt bepalen welk van de 2 implementaties van het algoritme de snelste implementatie op het bord oplevert. Bedenk dat het in hardware mogelijk is om dingen parallel te doen! Onderbouw je keuze door te meten aan het model! Om executietijd te meten kun je gebruik maken van de class StopWatch zie stop-watch.h  en stop-watch.cpp . Een voorbeeld van het gebruik kun je hier vinden: stop-watch-test.cpp . Bedenk wel dat je nu meet op een PC terwijl de applicatie uiteindelijk op het DE2-70 bord moet gaan draaien.

Opdracht 1e

Als we de conversie zo snel mogelijk willen maken moeten we zeker geen floating-point getallen gebruiken. In plaats daarvan moeten we fixed-point getallen gebruiken. Zie http://en.wikipedia.org/wiki/Fixed-point_arithmetic. Het probleem bij het gebruik van fixed-point is dat we het aantal bits voor en na de decimale punt zodanig moeten kiezen dat er geen overflow optreed en dat de nauwkeurigheid nog voldoende is. Ik eis dat de threshold die met de fixed-point versie van het model berekend wordt exact hetzelfde ia als de waarde die gegeven is in de bovenstaande tabel voor alle in die tabel gegeven test plaatjes.

Je mag mag echter wel van de volgende veronderstellingen uitgaan: een plaatje wat met dit algoritme bewerkt moet worden

• bestaat uit pixels waarbij elke pixel een grijswaarde weergeeft. De minimale grijswaarde is 0 (zwart) en de maximale grijswaarde is 255 (wit).
• bestaat uit maximaal 2¹⁶ pixels.
• bestaat uit pixels die niet allemaal dezelfde waarde hebben. (Er is dus altijd een voor- en een achtergrond in het plaatje te herkennen).

De SystemC library bevat diverse fixed-point datatypes waarmee je relatief eenvoudig kunt experimenteren en het benodigde aantal bits (voor en na de decimale punt) kunt bepalen. In het SystemC boek worden de fixed-point datatypes behandeld in paragraaf 4.5. Je kunt ook deze presentatie bekijken: http://wwwhome.ewi.utwente.nl/~gerezsh/sendfile/sendfile.php/idsp-fixed.pdf?sendfile=idsp-fixed.pdf .

Zet de bij opdracht 1c gekozen implementatie om naar fixed-point waarbij het aantal bits voor en na de decimale punt van elke fixed-point variable minimaal is zodanig dat geen overflow optreed en dat de gewenste nauwkeurigheid gehaald wordt.