Lokale Gitteroptimierung für einen objektbasierten Bewegtbildcodec

Diplomarbeit von Holger Hornig

Einleitung:

In der heutigen Zeit ist die Mobilität und ständige Erreichbarkeit zu einem wichtigen Teil unserer Lebensqualität geworden.

Gerade im Bereich der Bildtelefonie müssen große Datenmengen bewältigt werden. Um vielen Nutzern diesen Dienst anbieten zu können, ist eine schmalbandige Übertragung notwendig. Die objektbasierte Bildcodierung nutzt logisch zusammenhängende Bildbereiche aus, um diese optimiert zu kodieren und zu übertragen. Dazu werden markante Punkte im Objekt gesucht, deren Position sich im folgenden Bild leicht wiederfinden lassen. Aus diesen Punkten wird ein Dreieckgitter gebildet, deren Inhalt einzelne Bildbereiche darstellen.

Unter der Voraussetzung, dass sich die Punkte zwischen zwei Bildern nur wenig bewegen, kann das darauf folgende Bild mittels Analyse der Bewegungsvektoren und Morphing approximiert werden.

In dieser Arbeit wird die Suche solcher markanten Punkte erläutert. Ferner werden zwei Verfahren und deren Optimierung zur vollständigen Triangulierung der Objekte gegenübergestellt und verglichen. Ein weiterer Bestandteil ist die optimierte Approximation von bekannten Konturen anhand von mehreren Fehlerkriterien.

Inhaltsverzeichnis:

1.	Einleitung	1
2.	Beschreibung der Algorithmen	3
2.1	Definitionen	3
2.2	Aufbau der Datenstruktur	6
2.3	Suchen eines Objektes	7
2.4	Bestimmung der Konturpunkte	8
2.4.1	Hilfsalgorithmen	9
2.5	Bestimmung äußerer Triangulierungspunkte	10
2.5.1	Intervallmethode	10
2.5.2	Methode der besten Eckpunkte	11
2.6	Approximation der Konturkante	12
2.7	Berechnung innerer Triangulierungspunkte	15
2.7.1	Intervallmethode	15
2.7.2	Suche nach dem globalen Maximum	16
2.7.3	Eleminierung von ungültigen Punkten	17
3.	Triangulierungsalgorithmen	19
3.1	Äußere Triangulierung mit Kurvendreiecken	19
3.2	Äußere Triangulierung mit regulären Dreiecken	22
3.3	Keine äußere Triangulierung	22
3.4	Greedy-Algorithmus	23
3.4.1	Optimiertes Greedy-Verfahren	24
3.5	Delaunay-Algorithmus	25
3.5.1	Voronoi-Zonen	25
3.6	Vervollständigung der Kanten zu Dreiecken	27
3.7	Optimierung der Dreiecke	28
3.8	Bearbeitung von degenerierten Dreiecken	32
4.	Codierverfahren	34
4.1	Intra-Gittercodierung	35
4.1.1	Ein einfaches Intra-Codierverfahren	35
4.1.2	Ein besseres Intra-Codierverfahren	37
4.1.3	Fast optimale Intra-Codierung	38
4.1.4	Die Inter-Codierung	39
4.1.5	Intra-Codierung mit Inter-Datenrate	40
5.	Hilfsroutinen	41
5.1	WATCHDOGS	1
5.1.1	Complete triangulation	41
5.1.2	Valid triangles	42
5.1.3	Intersect triangles	44
5.1.4	Complete contour	47
5.1.5	Same grids	47
5.1.6	Grid syntax	47
5.2	Auswertungsroutinen	49
5.2.1	make statistic	49
6.	Relationen von Pixeln und Geraden	50
6.1	Lage eines Punktes zu einer Kante	50
6.2	Schnitt von zwei Kanten	51
6.3	Lage eines Punktes zu einem Polygonzug	52
6.3.1	Graphische Hilfsroutinen	52
6.3.2	Mathematische Hilfsmodule	52
6.3.3	Flood-fill Algorithmus (G)	53
6.3.4	Scanlinie Algorithmus (GM)	54
6.3.5	Even odd oder scanline Methode (GM)	54
6.3.6	Winding-number Algorithmus (GM)	58
6.3.7	Winkelsummen Test (GM)	58
6.4	Lage einer Kante zu einem Polygon	61
6.4.1	Ein trivialer Ansatz	61
6.4.2	Mittelpunkt und Kreuzungsfreiheit	61
7.	Simulationsergebnisse	63
7.1	Suche nach den äußeren und inneren Triangulierungspunkten	63
7.2	Approximation der Konturkante	65
7.3	Vergleich der Triangulierungsalgorithmen	71
7.3.1	Güte des minimalen Winkels	71
7.3.2	Minimale Fläche des Dreiecks	73
7.3.3	Ordnung der Verfahren	74
7.4	Bewertung der Intra-Codierverfahren	75
8.	Zusammenfassung	77
A.	Beschreibung der Parameter	79
B.	Struktur der Delaunay Files	81