Hauptseite

Fugenschnitzer-Programmbibliothek 0.8 beta 2
Programmiererhandbuch

Fugenschnitzer – Seam Carving für jedermann.
Copyright © 2008/9 David Eckardt
http://fugenschnitzer.sourceforge.net

Inhalt

Funktionsindex

Bilddaten

Datenformat

Das Bild muß als Datenpuffer/1D-Feld vorliegen. Der Elementardatentyp ist comp_t. Dies ist ein 32-Bit-Integertyp ohne Vorzeichen. Jedes Element entspricht einem Bildpixel im Farbmodell RGB mit 8 Bit pro Kanal. Für 1 Byte = 8 Bit entspricht das unterste Byte dem R-Kanal, das zweitunterste G und das drittunterste B.
Da die Elemente des Bildes 32 Bit Breite besitzen, bieten sie Platz für vier Kanäle @ 8 Bit. Der frei bleibende Kanal wird für die Fugensuche ignoriert, bei der Größenänderung aber mit verarbeitet.

Speicherplatz

Falls das Bild nur verkleinert wird, braucht das aufrufende Programm keinen weiteren Speicherplatz anzufordern als den, den das Bild von Anfang an einnimmt. Wird das Bild jedoch vergrößert, muß das aufrufende Programm zusätzlichen Speicherplatz anfordern, bevor es das bearbeitete Bild zurücknehmen kann. Die Funktion sc_prepare gibt über die Ausgabewerte width und height Auskunft darüber, wie viel Speicher das Bild höchstens beanspruchen wird. Nach Aufruf von sc_prepare beträgt die Bildgröße höchstens
width * height * sizeof(comp_t) .

Funktionen

Grundfunktionen

Die Funktionen zur einfachen Bildgrößenänderung sind im Folgenden in der Reihenfolge aufgeführt, in der sie aufgerufen werden.

void sc_init(void)
Initialisiert alles. Diese Funktion muß genau einmal aufgerufen werden, und zwar vor allen anderen, und danach nie wieder.
bool sc_load(
const comp_t *image,
long int *width, long int *height,
int zoom
)
Lädt das Bild.
int sc_prepare(
const bool vertical,
const long int extend,
const bool interpol,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Bereitet die Fugensuche und Bildgrößenänderung vor. Dabei wird vor allem die Änderungsrichtung festgelegt.
bool sc_seam(long int last)
Ermittelt last Fugen.
long int sc_carve(
long int nom,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Ändert die Bildgröße so, daß sie sich um nom Pixel von der Originalgröße unterscheidet. Damit das Bild kleiner ist als im Original, muß nom negativ sein und positiv, damit es größer wird. Die Bildgrößenänderung erfolgt um maximal so viele Pixel, wie bisher Fugen ermittelt wurden. Falls das Bild größer werden soll als das Original, also nom > 0, erfolgt die Vergrößerung höchstens um so viele Pixel, wie zuvor der Funktion sc_prepare durch den Parameter extend angegeben wurden.
bool sc_fix(
const bool restore,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Fixiert das Bild. Dabei wird es auf seinen momentanen Zustand festgelegt, die ermittelten Fugen verworfen und die Bildgrößenänderungsrichtung wieder freigegeben.
void sc_eject(comp_t *image)
Gibt das Bild aus.
void sc_close(void)
Schließt alles.

Zusatzfunktionen

Vorschaubild

Es ist möglich, ein skaliertes (proportional verkleinertes) Vorschaubild des gerade verarbeiteten Bildes abzurufen. Das ist für den Fall gedacht, wenn ein Bild angezeigt werden soll, dessen Maße die Bildschirmgröße übersteigen.
Um das Vorschaubild zu erzeugen, muß beim Aufruf von sc_load mit dem Parameter zoom ein Skalierungsfaktor z > 1 angegeben werden. Mit sc_preview wird dann das Vorschaubild abgerufen. Das Vorschaubild entspricht dem verarbeiteten Bild in seinem momentanen Zustand, allerdings in Breite und Höhe durch z geteilt.
Für den Speicherplatz des skalierten Vorschaubildes gilt dasselbe wie für das Originalbild. Wird das Bild über seine Originalgröße hinaus vergrößert, muß für das Vorschaubild zusätzlicher Speicherplatz angefordert werden. sc_prepare gibt über die Parameter pwidth und pheight Auskunft darüber, wie viel Speicher für das Vorschaubild angefordert werden muß, analog zu width und height. sc_carve und sc_fix geben über diese Parameter an, wie groß das Vorschaubild momentan ist.

void sc_preview(comp_t *image)
Gibt das Vorschaubild aus.

Nachträgliche Erweiterung

Die maximale Bildgröße, die beim Aufruf von sc_prepare durch den Parameter extend angegeben wurde, kann während der Bildverarbeitung erweitert werden. Hierzu dient die Funktion sc_extend. Sie verhält sich in bezug auf ihre Parameter und ihren Rückgabewert genau wie sc_prepare. Nach Aufruf von sc_extend muß wie bei sc_prepare ggf. mehr Bildspeicher angefordert werden.

int sc_extend(
const long int extend,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Erweitert das Bild nachträglich so, daß seine maximale Größe seine Originalgröße um extend Pixel übersteigen kann. Für die Bedeutung der Parameter siehe sc_prepare.

Programmablauf

Voraussetzungen

Zunächst muß das Bild geladen werden. Wie gesagt, ist das erforderliche Bilddatenformat RGB mit 8 Bit/1 Byte pro Kanal und 32 Bit/4 Kanälen pro Pixel. Das unterste Byte entspricht dem R-Kanal. Falls das Bild als 1D-Feld von Bytes im RGBA- oder RGB32-Format vorliegt, kann es einfach per C-Cast nach comp_t* konvertiert werden. Dabei ist allerdings die Bytereihenfolge/Endianness der Maschine zu beachten.
Für die Bildmaße, Breite und Höhe, in Pixeln, muß jeweils eine Variable vom Typ long int vorhanden sein, in denen die Größe des Ausgangsbildes gespeichert ist. Den Bibliotheksfunktionen werden dann Zeiger auf diese Variablen übergeben.

Einfacher Ablauf: Laden – Größe ändern – ausgeben

Angenommen, das Bild liegt als 1D-Feld comp_t *image vor, und seine Größe ist in den Variablen long int x (Breite) und long int y (Höhe) gespeichert. Wir möchten das Bild um 50 Pixel in horizontaler Richtung vergrößern und dabei die einzufügenden Pixel interpolieren.

Fertig! image enthält das geänderte Bild und x und y die neuen Bildmaße. Das Bild kann jetzt gespeichert werden.

Interaktion – Größe mehrmals ändern

Zwischen den Aufrufen von sc_prepare und sc_fix können sc_seam, sc_carve und sc_eject mehrmals beliebig oft aufgerufen werden. sc_seam erweitert dabei jeweils den Bereich, innerhalb dessen die Bildgröße mit sc_carve geändert werden kann. Damit ist es möglich, eine Benutzerinteraktion zu realisieren, in der der Benutzer die Bildgröße nach Belieben ändern kann, bevor das Bild auf eine bestimmte Größe festgelegt wird.
sc_eject gibt dabei das Bild stets in der maximalen Größe aus, das ist die Originalgröße plus der Anzahl Pixel in Größenänderungsrichtung, die sc_prepare mit dem Parameter extend übergeben wurde. Die überzähligen Pixel in jeder Bildzeile bzw. -spalte müssen vom aufrufenden Programm ignoriert und bei Anzeige des Bildes ausgeblendet werden.
Hier die Erweiterungen zum Beispiel von oben:

Nebenläufige Ausführung und parallelisiertes Rechnen

Fugenschnitzer ist für nebenläufige (multi-threaded) Programmausführung und parallelisierte Ausführung von Rechenoperationen ausgelegt. Die Initiation und Synchronisation der laufenden Threads müssen dabei vom aufrufenden Programm aus gesteuert werden.
Die hierfür verwendeten Funktionen sind von sich aus nicht threadsicher (thread safe), d.h., sie verhinderm nicht von alleine vollautomatisch das Auftreten von möglichen Konflikten, die auftreten können, wenn eintrittsinvariante Funktionen beliebig oft, zu beliebiger Zeit und in beliebiger Reihenfolge aufgerufen werden. Stattdessen ist es erforderlich, daß das aufrufende Programm im Dialog mit den Bibliotheksfunktionen arbeitet. Der hierfür erforderliche Aufwand ist allerdings gering und allemal sowohl wesentlich geringer als auch weniger fehleranfällig und flexibler, als es ein komplettes Threadverwaltungssystem wäre.

Fortschrittsabfrage und Anhalten der Fugensuche

long int sc_seam_progress(void)
Fragt den Fortschritt ab, während sc_seam läuft.

Hinweis: Diese Funktion darf jederzeit aufgerufen werden.

long int sc_seam_cancel(void)
Hält sc_seam nach Abschluß der momentan berechneten Fuge an. Den Fortschritt bis dahin liefert sc_seam_progress.

Hinweis: Diese Funktion darf jederzeit aufgerufen werden.

Parallelisierte Fugensuche

Die Rechenvorgänge bei der Fugensuche können parallelisiert werden. Dabei betrifft die Parallelisierung den Suchvorgang für eine einzelne Fuge. Erst wenn die aktuelle Fuge ermittelt und verarbeitet wurde, kann der Suchvorgang der nächsten Fuge beginnen. Das Parallelisieren der Fugensuche erfolgt durch Entkoppeln von voneinander unabhängigen Operationen in drei Stufen:

  1. gleichzeitiges Differenzieren mehrerer Bildausschnitte
  2. akkumulieren bereits differenzierter Bildzeilen bei gleichzeitigem Differenzieren der folgenden
  3. gleichzeitige Anwendung der ermittelten Fuge auf mehrere Bildteile

Paralles Differenzieren und Akkumulieren

Damit der Akkumulierungsvorgang bereits beginnen kann, wenn die Differenzierung noch läuft, wird das Bild in mehrere Teile (parts) aufgeteilt. Jeder Teil enthält eine bestimmte Anzahl Bildzeilen. Das aufrufende Programm gibt dabei an, wie viele Pixel in einem Teil mindestens enthalten sein sollen; der Vorgabewert ist 65536.
Zum Steuern des parallel laufenden Differenzier- und Akkumuliervorgangs stehen die Funktionen

  1. sc_seam_paral_diff,
  2. sc_seam_paral_accu und
  3. sc_seam_paral_seam

zur Verfügung.

Parallelisiertes Differenzieren

Der Differenziervorgang selbst läßt sich parallelisieren, indem mehrere Bildausschnitte gleichzeitig differenziert werden. Zusammen mit einem gleichzeitig laufenden Akkumuliervorgang bedeutet daß, daß jeder Bildteil wieder in mehrere Abschnitte aufgeteilt wird. Für jeden dieser Abschnitte ist ein Differenzierthread zuständig. Das aufrufende Programm gibt hierbei zuvor an, wie viele Threads es geben soll; Fugenschnitzer teilt dann die Bildbreite durch die gewünschte Threadanzahl.

Ablaufschema und Vorbereitung/Abschluß

Wie anfangs angekündigt, erfolgt die Fugensuche unter Verwendung der parallelisierten Funktionen immer nur für eine Fuge (im Unterschied zu sc_seam). Das aufrufende Programm muß also eine Fugenzählschleife enthalten. Vor Beginn und nach Abschluß der Suche muß die Funktion sc_seam_paral_init bzw. sc_seam_paral_close aufgerufen werden. Damit ergibt sich folgendes Schema:

  1. sc_seam_paral_init
  2. (Zählschleife für Fugensuche)
  3. sc_seam_paral_close.

Die Suche nach einer Fuge enthält selbst wiederum zwei Schleifen: Eine Differenzier- und eine Akkumulierschleife. Diese beiden Schleifen laufen gleichzeitig; die Akkumulierschleife muß dabei in Abhängigkeit von der Differenzierschleife synchronisiert sein.
Vor Beginn dieser Schleifen wird die Funktion sc_seam_paral_start aufgerufen. Nachdem die Schleifen beendet sind, wird sc_seam_paral_seam_init aufgerufen, gefolgt von sc_seam_paral_seam. Schließlich wird durch Aufruf von sc_seam_paral_finish die Verarbeitung dieser Fuge beendet.
Damit sieht der Ablauf innerhalb eines einzelnen Schleifendurchlaufs der Fugensuche so aus:

  1. sc_seam_paral_start
  2. (Differenzierschleife, mehrere Differenzierthreads) → synchronisiert → (Akkumulierschleife)
  3. sc_seam_paral_seam_init
  4. sc_seam_paral_seam (läuft in mehreren Threads gleichzeitig)
  5. sc_seam_paral_finish

Starten von Threads und Synchronisierung

Wie angekündigt, muß das aufrufende Programm das Starten von Threads bewerkstelligen sowie für die korrekte Synchronisierung der Differenzier- und Akkumulierschleife sorgen. Da diese beiden Schleifen parallel arbeiten, muß jede von ihnen in einem eigenen Thread laufen. Die Funktionsanforderungen an das aufrufende Programm sind:

  1. Einen Thread starten,
  2. auf Beendigung eines oder mehrerer Threads warten,
  3. eine Nachricht in Form eines Integerwerts von einem Thread zum anderen senden,
  4. auf Eintreffen einer Nachricht warten und den Inhalt weitergeben.

Diese Funktionen lassen sich mit dem Basisumfang einer Multi-Threading-Bibliothek wie z.B. pthreads implementieren.

Funktionen

Hier die Funktionen der parallelisierten Fugensuche in der Reihenfolge, in der sie aufgerufen werden:

void sc_seam_paral_init(void)
Initiiert die Fugensuche.
int sc_seam_paral_start(
long int samples,
int threads
)
Startet den parallelisierten Suchvorgang für eine Fuge.
void sc_seam_paral_diff(
const int part,
const int thread
)
Differenzierfunktion für parallelisierte Fugensuche.
bool sc_seam_paral_accu(const int part)
Akkumulierfunktion für parallelisierte Fugensuche.
void sc_seam_paral_seam_init(const int threads)
Initialisiert die Verarbeitung der ermittelten Fuge.
void sc_seam_paral_seam(const int thread)
Verarbeitungsfunktion für die ermittelte Fuge.
long int sc_seam_paral_finish(void)
Schließt den parallelisierten Suchvorgang für eine Fuge ab.
void sc_seam_paral_close(void)
Schließt die Fugensuche ab.

Codebeispiel

compute_seams ist die Hauptfunktion und imitiert sc_seam. diff_loop und accu_loop repräsentieren die Differenzier- und Akkumulierschleife. Das Starten der Threads und das Warten auf deren Beendigung übernehmen die Pseudofunktionen start_thread und join_thread, die mit dem Pseudodatentyp thread_t arbeiten. Eine entsprechende Funktionalität bietet z.B. die pthreads-Bibliothek.
Für die Synchronisierung zwischen Differenzier- und Akkumulierschleife sind die Pseudofunktionen send_message und wait_for_message zuständig, die die Funktion einer Nachrichtenwarteschlage (message queue) erfüllen. Der wesentliche Punkt ist, daß sc_seam_paral_accu einen Bildteil erst dann bearbeiten darf, wenn sc_seam_paral_diff seine Bearbeitung abgeschlossen hat.

Die Bibliotheksfunktionen sind fett geschrieben, die Variablenbezeichner im Vraiablenstil und Pseudofunktionen kursiv.

Parallelisierte Bildgrößenänderung

Ablaufschema

Die Bildgrößenänderung läßt sich ebenfalls parallelisieren. Das geschieht nach folgendem Schema:

  1. Parallelisierte Größenänderung initialisieren mit sc_carve_paral_init. Dabei übergibt das aufrufende Programm die Anzahl threads an gewünschten Instanzen (bzw. Threads, wenn jede Instanz in einem eigenen Thread läuft).
  2. Größenänderung durchführen mit sc_carve_paral. Diese Funktion muß threads mal aufgerufen werden (threads wie an sc_carve_paral_init übergeben). Die verschiedenen Instanzen von sc_carve_paral dürfen gleichzeitig laufen.
  3. Nachdem alle Instanzen von sc_carve_paral fertig sind, Vorgang abschließen mit sc_carve_paral_finish.

Fortschrittsabfrage

Während sc_carve_paral läuft – ggf. in mehreren Instanzen gleichzeitig –, kann das aufrufende Programm den Fortschrittm mit sc_carve_paral_progress abfragen.

Funktionen

long int sc_carve_paral_init(
long int nom,
int threads
)
Initialisiert die parallelisierte Bildgrößenänderung.
void sc_carve_paral(const int thread)
Parallelisierte Bildgrößenänderungsfunktion.
long int sc_carve_paral_finish(
long int *width, long int *height,
long int *pwidth, long int *pheight,
)
Schließt die parallelisierte Bildgrößenänderung ab.
long int sc_carve_paral_progress(void)
Fragt den Fortschritt der parallelisierten Bildgrößenänderung ab.

Codebeispiel

Die Funktion resize_image imitiert sc_carve, jedoch auf T = 4 Threads verteilt. Das Starten der Threads und Abwarten von deren Beendigung übernehmen wieder die Pseudofunktionen start_thread und join_thread, die mit dem Pseudodatendyp thread_t arbeiten. Eine entsprechende Funktionalität bietet z.B. die pthreads-Bibliothek.

Hinweise zum Kompilieren & Linken

Include-Header für die Bibliotheksfunktionen

Der Include-Header ist "seamcarv.h".

C99 und bool

Die Bibliotheksfunktionen sind in C99 geschrieben und verwenden den Datentyp bool. Dieser ist über den C99-Include-Header <stdbool.h> erhältlich. Beim Kompilieren mit GCC muß evtl. der Kommandozeilenparameter -std=c99 angegeben werden. Falls im Quelltext gleichzeitig Nicht-stdlib-Funktionen verwendet werden, muß evtl. mit dem zusätzlichen GCC-Kommandozeilenparameter -U__STRICT_ANSI__ das Präprozessormakro __STRICT_ANSI__ gelöscht werden.

Verlinken mit der Bibliothek

Hinweis: Siehe hierzu unbedingt das GCC-Handbuch.
Zum dynamischen Verlinken des Programms, das die Fugenschnitzer-Programmbibliothek verwendet, durch GCC muß folgendes erfüllt sein:

  1. Die Bibliothek muß im Bibliothekssuchpfad oder selben Verzeichnis wie der Quell-/Objektcode liegen. Die Bibliothek ist eine Datei mit folgendem Namen:
    Plattform Bibliotheksdateiname
    Windows seamcarv.dll
    Darwin/OS X libseamcarv.dylib
    Linux libseamcarv.so
  2. Der Bibliotheksname und ggf. das aktuelle Verzeichnis müssen als weiterer Linkzeit-Bibliothekssuchpfad angegeben werden:
    -lseamcarv -L.
  3. Unter Linux muß der Laufzeit-Bibliothekssuchpfad um das aktuelle Verzeichnis erweitert werden:
    -Wl,-R.

Die komplette Kommandozeile für Linux ist also (zuzüglich etwaige weitere verwendete Bibliotheken):
> gcc beispiel.c -std=c99 -U__STRICT_ANSI__ -lseamcarv -L. -Wl,-R. -o beispiel
Hinweis: Falls GCC die Bibliothek angeblich nicht findet, obwohl sie offensichtlich da ist, ist dem GCC-Handbuch, Abschnitt Options For Linking, zu entnehmen, nach welchem System GCC nach der Bibliothek sucht, nach welchem Schema die Bibliotheksdatei benannt sein muß und wie zusätzliche Bibliothekssuchpfade für Link- und Laufzeit anzugeben sind. Weitere Informationen hierzu und noch viel mehr stehen auch im Handbuch für ld, dem GNU-Linker, der beim Linken von GCC aufgerufen wird.