http://rubinghsoftware.de/projects/alfavision_comp/

Page contents Kurzbeschreibung Aufgabe Algorithmus Quellcode     Interne dependency-Struktur     Listing der source files     Build     Run Siehe auch Appendix (on separate page) Ausführliche Algorithmusbeschreibung

Kurzbeschreibung

Diese Seite enthält einen Programmiertest den ich gemacht habe für eine Bewerbung in 2011 bei einer kleinen Firma die sich befasst mit optischer 3D-Vermessung und der dazugehörenden Bildverarbeitung.[1] 

Die Aufgabe war, Pixelanzahl, bounding box, und Schwerpunkt zu bestimmen für jede der 4-connected components in einem Binärbild. 

Die Aufgabe und meine Lösung (mit Quellcode) sind hier aufgenommen mit freundlicher Genehmigung der Firma Alfavision (www.alfavision.de). 

Aufgabe

 Gegeben: Bilddatentyp wie folgt:
 
 typedef struct image_ {
   int size_x;                   /* Bildgröße in x-Richtung */
   int size_y;                   /* Bildgröße in y-Richtung */
   unsigned char *data;          /* Zeiger auf die Bilddaten */
 } image_t;
 
 Die Bildgröße beträgt size_x mal size_y Bildpunkte (Pixel) der Größe
 1 Byte.
 
 Die Bilddaten sind zeilenweise, beginnend mit der linken, oberen
 Ecke abgelegt (auf das letzte Pixel der ersten Zeile folgt im Speicher
 unmittelbar das erste Pixel der zweiten Zeile). Der Zeiger data zeigt
 auf das linke, obere Pixel. size_x mal size_y Bytes/Bildpunkte sind
 zugreifbar.
 
 
 Gegeben: Zusammenhangskomponenten-Datenstruktur wie folgt:
   
 typedef struct comp_ {
   int min_x;                    /* Kleinste vorkommende x-Koordinate */
   int min_y;                    /* Kleinste vorkommende y-Koordinate */
   int max_x;                    /* Größte vorkommende x-Koordinate */
   int max_y;                    /* Größte vorkommende y-Koordinate */
   int pixels;                   /* Anzahl der Bildpunkte in der Komponente */
   double bary_x;                /* Schwerpunkt, x-Koordinate */
   double bary_y;                /* Schwerpunkt, y-Koordinate */
 } comp_t;
 
 min_x, min_y, max_x und max_y sind die Koordinaten eines umschreibenden
 Rechtecks (Bounding Box) um die Zusammenhangskomponente, die pixels
 Bildpunkte enthält. Der geometrische Schwerpunkt der Komponente liegt an
 der Position bary_x, bary_y.
 
 
 
 Aufgabe:
 
 Entwerfen Sie eine Algorithmik in ANSI-C, die aus einem vorgegebenen
 Binärbild (die Bildpunkte haben entweder Grauwert 0 oder Grauwert 255).
 alle Zusammenhangskomponenten extrahiert. Eine Zusammenhangskomponente
 umfasst alle Pixel mit Grauwert 255, die von einem beliebigen Pixel der
 Komponente aus über den linken, rechten, oberen oder unteren Nachbarn
 erreichbar sind.
 
 Die zu entwerfende Interface-Routine sollte als Eingabeparameter
 einen Zeiger auf ein Binärbild enthalten.
 
 Für jede Komponente soll die Anzahl der enthaltenen Bildpunkte,
 das umschreibende Rechteck und der Schwerpunkt erfasst werden.
 Die Ausgabe der Komponenten kann als Liste, Vektor, Array, Iterator
 oder in sonstiger geeigneter Art und Weise erfolgen. Entsprechende
 Parameter oder Rückgabewerte sind in der Interface-Routine vorzusehen.
 
 Die Routine(n) sollten zumindest kurz kommentiert sein. Der Gedankengang
 der Lösung sollte aus der Kommentierung ersichtlich werden.
 Hilfsdatenstrukturen und Hilfsroutinen nach Bedarf.

Algorithmus

Vorher hatte ich schon einen Algorithmus gekannt fürs Erkennen der 4-connected components in einem Binärbild, nämlich das sogenannte Connected Components Labeling, und diesen Algorithmus habe ich als Ausgangspunkt genommen.  Der Connected Components Labeling Algorithmus macht mehrere Durchgänge (passes) durchs image, was notwendig ist damit die labels vollständig gesetzt werden können. 
    Jedoch, in dieser Programmieraufgabe ist das vollständige label image nicht als output notwendig; und ist es möglich gewesen, die unterliegende Idee aus dem Connected Components Labeling Algorithmus so einzusetzen dass die für diese Aufgabe benötigte Information aus dem image extrahiert werden kann in nur einem Durchgang (one pass) durch das image. 

Meinen Algorithmus habe ich einigermaßen ausgiebig optimiert; an erster Stelle in Laufzeit, und an zweiter Stelle in Speicherbenutzung.  Solche algorithmische Optimierung zu engineeren und feinzuschleifen ist eine der Arten von Aufgaben die mich generell stark motiviert, und eine meiner Stärken. 

Meinen Algorithmus habe ich ausführlich beschrieben (auf Englisch) in einem großen comment block in einer der source files in der von mir eingesandten Quellcode.  Diese Algorithmusbeschreibung aus dem Quellcode, zur besseren lesbarkeit umformattiert von plain ASCII text nach HTML aber sonst ungeändert gelasssen, habe ich zusätzlich hier auf einer separaten Seite hingestellt. 

Quellcode

Die Sourcen sind, wie in der Aufgabe verlangt, reines ANSI C.  Es ist ein stand-alone Programm, das als seine einzigen externen Abhängigkeiten nur die standard C libraries benutzt die geinterfaced werden durch die header files assert.h, stdlib.h (für malloc() und free()), stdio.h, limits.h, und stdarg.h.

Interne dependency-Struktur

(Abb. 1)   Dependency diagram.  A block uses only those other blocks that are located strictly vertically below it.

Listing der source files

Die Links in der linken Spalte der obigen Tabelle führen zu Darstellungen der source files in der Form von HTML-Seiten.  (So gemacht um viewing der sourcen im internet browser möglich zu machen.) 
    Ein gzip-Archiv das alle source files in origineller Form enthält (und mit den originellen Dateinamen) ist hier.  Entpacken: gunzip countcomponents.tar.gz, dann tar -xvf countcomponents.tar

Build

Mit dem GNU gcc compiler wird aus den Sourcen der Executable countcomponents wie folgt erzeugt:

	gcc -ggdb -Wall -ansi -DDEBUG \
		lineacc.c      \
		lmap.c         \
		debug.c        \
		processimage.c \
		testdata.c     \
		main.c         \
		-o countcomponents

Run

Das Programm wird auf der Kommandzeile wie folgt aufgerufen (unter UNIX/Linux):

	./countcomponents TESTNR 

	./countcomponents TESTNR  | grep OutComp 

Das required argument TESTNR, eine integer Zahl in [1,9], spezifiziert welcher der eingebauten Testcases ausgeführt werden sollte. 

Das Programm loggt nach stdout mehr oder weniger "alles" das während Programmlauf passiert.  Sobald eine Komponente (4-connected component) fertig gefunden ist, werden die Daten dieser Komponente vom Programm ausgedruckt auf einer Zeile die Anfangt mit dem Kennwort "OutComp".  In der zweiten Kommandozeile oben werden nur diese Outputzeilen durchgelassen, wodurch übrig bleibt eine schlichte Auflistung aller gefundenen Komponenten (mit deren Pixelzahl, bounding box, und Schwerpunkt).

Siehe auch

Testaufgaben über 3D-Sehen aus der gleichen Bewerbung.