Der JND-Algorithmus

Einleitung

Wie wir gesehen haben, sind bisher verschiedene Verfahren entwickelt worden, um die Qualität eines Bildes im Vergleich zu einem Referenzbild zu messen und gleichzeitig ein Mass zu finden, das gut mit dem der menschlichen Wahrnehmung übereinstimmt. Momentan werden viele Versuche unternommen, ein rechnergestütztes objektives Bildqualitätsverfahren zu erstellen und die Mehrzahl stützt sich auf das Lubin-JND Modell.

Auswahl des Verfahrens

In der vorangegangen Semesterarbeit entschied man sich deshalb für das Lubin-JND Modell und hat es in einer vereinfachten Form in einem C++-Algorithmus implementiert.

Aus diesem Grund und weil aufgrund meiner Recherchen dieses Modell eindeutig für die geforderten Zwecke am besten geeignet ist, habe ich mich entschlossen, es ebenfalls zu verwenden.

Es geht nun darum, den Algorithmus zu verbessern, da die bisherigen Ergebnisse noch nicht befriedigend waren. Ausserdem muss überprüft werden, inwiefern diese Version des Algorithmus Werte liefert, die besser mit der subjektiven Bewertung korreliert als der vorige.

Nachfolgend erkläre ich zuerst, welche Veränderungen am Modell im Vergleich zur vorangegangen Semesterarbeit vorgenommen wurden. Danach erfolgt eine Beschreibung der Arbeitsweise des Modells und zum Schluss wird die Implementation in den C++-Algorithmus erläutert.

Veränderungen des Algorithmus

In der vorhergegangen Semesterarbeit [37] wurde das oben beschriebene Modell von Lubin in einer vereinfachten Form ohne Orientierungsfilter implementiert, es wurde jedoch noch keine Normierung oder eine Verifizierung der Ergebnisse vorgenommen. Ich habe im Rahmen der vorliegenden Diplomarbeit unter anderem den Algorithmus um die Funktionen der Orientierungsfilter wie folgt ergänzt:

• Es wurden drei gaussförmige Richtungsfilter ausgewählt. Jeweils ein Filter bevorzugt Strukturen in horizontaler, vertikaler und diagonaler Richtung. Die Implementierung erfolgte als 3 x 3-Matrix im Ortsbereich, wobei das richtungsgefilterte Ergebnis durch eine Faltungsoperation mit dem zu bearbeitenden Kontrastbild zustande kommt.

• Im Unterschied zum Modell von Lubin, das als Richtungsfilter phasenunabhängige Filter für vier Orientierungen verwendet (jeweils Transformierte von Hilbertpaaren), habe ich wegen der kürzeren Rechenzeit erstens nur drei Filter verwendet und zweitens die Phase nicht berücksichtigt (bei einem Vergleich von Bildern in PAL-Auflösung dauert die Berechnung nach dieser Implementation knapp 150 Sekunden, die Berechnung ohne Richtungsfilter ist nach rund 42 Sekunden abgeschlossen). Ansonsten wurde das Modell komplett übernommen. Da jedoch davon ausgegangen wurde, dass die Bilder immer ohne seitliche Abweichung zur Normalen beurteilt werden, wurde auf die Möglichkeit verzichtet, den Betrachtungswinkel zu berücksichtigen. Diese Einschränkung beeinträchtigt jedoch nicht die Qualität des Ergebnisses.

• Es sind einige Korrekturen und Verbesserungen vorgenommen worden, so ist es zum Beispiel jetzt möglich, die Bilder beim Starten des Programms mit Namen zu übergeben, was bei einem Vergleich von mehreren hundert Bildern sehr von Vorteil ist (siehe [37]).

• Auf Wunsch ist auch eine Reduzierung der zu erzeugenden Pyramidenstufen möglich, was die Rechenzeit verkürzt, aber auch die Genauigkeit der Werte vermindert. Ebenso können die Differenzbilder abgespeichert werden, wenn genug Speicherplatz vorhanden ist.

In Abschnitt 7.2.2 werden die einzelnen Verarbeitungsschritte des von mir implementierten JND-Modells im einzelnen erklärt (Bild 7.1). Der dazugehörende Quellcode ist im Anhang A abgedruckt.

Beschreibung der einzelnen Schritte im Modell

1.
Die beiden zu vergleichenden Bilder müssen in digitaler Form (im PPM-Format) vorliegen und sie müssen beide die gleiche Grösse besitzen (z. B. 768 x 576 Pixel für Fernsehbilder).

2.
Beide Bilder werden zuerst entsprechend dem Betrachtungsabstand und der Augenoptik tiefpassgefiltert. Zusätzlich sollte an dieser Stelle die Pupillenweite berücksichtigt werden, die sich anhand der durchschnittlichen Bildhelligkeit abschätzen lässt. Dieser Verarbeitungsschritt wurde aber nicht implementiert.

3.
Die Bilder werden neu abgetastet, um die Abtastung durch die Zapfen auf der Netzhaut zu simulieren. Für Bilder, die ohne seitliche Verschiebung zur Normalen betrachtet werden (wie bei uns der Fall), kann ein quadratisches Abtastraster von 120 Pixel pro Grad verwendet werden, was einem Netzhautbild von 512 x 512 Pixeln entspricht. Mit diesen Werten deckt man ein Gesichtsfeld von 4.25 Grad ab, was ungefähr dem Bereich der höchsten Sehschärfe in der Fovea centralis entspricht.

4.
Aus den drei Farbwertanteilen R, G und B werden mit der Gleichung (7.1) die Luminanzwerte Y für jeden Bildpunkt der beiden Bilder errechnet, da das Modell nur Helligkeitswerte berücksichtigt.

Anschliessend werden sieben lokale Kontrastbilder für die Bereiche von 32 Schwingungen pro Grad bis 0.5 Schwingungen pro Grad erzeugt. In jedem Bereich entspricht der so ermittelte lokale Kontrast ungefähr dem Weberkontrast (7.2).

Für Details bei der Berechnung der Kontrastbilder mit Laplacepyramiden verweise ich auf [37] und [36]

5.
Jedes der 7 Kontrastbilder (entsprechend einem der 7 Pyramidenlevel) wird mit drei Richtunsfiltern gefaltet (Filter X für Strukturen in horizontaler Richtung, Filter Y für Strukturen in vertikaler Richtung und Filter Z für diagonale Strukturen). Danach wird für jeden Punkt i ein lokales Energiemass ei berechnet, wobei sich der Index i auf die Position im Bild, das Pyramidenniveau und die Orientierung bezieht.

6.
Das lokale Energiemass ei wird mit der Wahrnehmungsgrenze [Barten] für diese Position und diese Pyramidenstufe normiert.

bezeichnet die Mittenfrequenz des jeweiligen Pyramidenniveaus, L die lokale Helligkeit (7.2) und die Bildbreite in Grad. Als Ergebnis erhält man das normierte Energiemass . Dieses wird für die Berechnung einer Nichtlinearität verwendet (7.4).

7. Variante a
Jetzt besitzt man 21 Matrizen (7 Pyramidenstufen zu 3 Orientierungen), zwischen denen die Abstände wie folgt ermittelt werden: Zuerst werden die kleineren Pyramidenstufen auf die volle Grösse hochinterpoliert, dann berechnet man Dj aus Gleichung (7.5).

Die Indizes j und k beziehen sich auf den Ort beziehungsweise das Pyramidenniveau und die Orientierung. S1 und S2 bezeichnen die beiden Eingangsbilder und T ist der Ausgang der Nichtlinearität. Das Ergebnis dieser Operation ist eine Matrix mit den Abmessungen der Eingangsbilder, die an jeder Stelle einen Abstandswert enthält.

7. Variante b
Alternativ habe ich die Möglichkeit getestet, die Fehlervektoren der 7 Bilder der 3 verschiedenen Orientierungen getrennt voneinander auszuwerten und noch eine Gewichtung vorzunehmen, die die horizontalen und vertikalen Orientierungn stärker bewertet als die diagonalen, da das menschliche Auge diese Strukturen besser wahrnehmen kann.

Jeder errechnete Abstandswert repräsentiert die Wahrscheinlichkeit, dass ein Betrachter an diesem Ort in den Bildern einen Unterschied feststellt. In dieser Stufe werden die Umrechnungen vorgenommen, die im Modell in Form einer Zuordnungstabelle integriert sind. Das Maximum der Werte steht für die Wahrscheinlichkeit, dass ein Beobachter irgendeinen Unterschied an irgendeiner Stelle in den Bildern feststellt. Falls es gewünscht wird, kann auch je nach Bereich die gesamte Matrix ausgewertet werden.

Die zwei Varianten der JND-Berechnungen

Wie schon erwähnt habe ich den Algorithmus im wesentlichen um die Orientierungsfilter erweiter. Dabei habe ich zusätzlich noch zwei Varianten unterschieden.

Eine erste Variante berechnet zuerst alle Differenzenvektoren aller 21 Bildern (7 Bandpassbilder zu je 3 Orientierungen) und errechnet einen gesamten JND-Wert. Die zweite Variante berechnet die Fehlervektoren der drei verschiedenen Orientierungen getrennt und nimmt hinterher zuerst noch eine Gewichtung vor, um den Umstand zu berücksichtigen, dass die menschliche visuelle Wahrnehmung empfindlicher auf horizontale und vertikale Strukturen reagiert als auf diagonale. Erst dann wird der JND-Wert berechnet.

Bei beiden Algorithmen werden die erhaltenen Werte zum Schluss in eine sechswertige Notenskala umgewandelt.

Das gesamte C++-Programm gliedert sich wie folgt:

Übersicht über die Module

• Das Hauptprogramm ist in der Datei main.cc implementiert und steuert den gesamten Ablauf der Berechnungen. Diese Datei importiert die Hilfsdateien laplace.h, bild.h, matrix.h und vektor.h.

• Die Klasse Laplacepyramide, die in der Datei laplace.h definiert und in laplace.cc implementiert ist ist zuständig für die Erstellung der verschiedenen Kontrastbilder mit Hilfe einer Zerlegung in eine 7-stufige Laplace-Pyramide. Die Klasse ist abhängig von den Dateien bild.h, matrix.h, und vektor.h. Die Laplacepyramide besteht aus zwei Arrays von Bildern, je einer für die Gaussbilder und einer für die Laplacebilder. Zusätzlich sind die verschiedenen Zugriffsfunktionen wie laden und speichern definiert.

• In der Klasse Bild, die in der Datei bild.h definiert und in bild.cc implementiert ist und die die Dateien matrix.h und vektor.h benötigt, sind Routinen für das Einlesen, Abspeichern, Über- / Unterabtasten und das Filtern von Bildern definiert.

• Die Klasse Matrix ist eine Hilfsklasse, die in der Datei matrix.h sowohl definiert als auch als Template implementiert ist. Die Matrix ist als ein Array von Vektoren definiert. Für die Matrizen sind die Operationen Subtraktion, Addition und Zuweisung definiert.

• Die Klasse Vektor ist ebenfalls eine Hilfsklasse, die als Template in der Datei vektor.h definiert und implementiert ist. Der Vektor ist ein Array von Werten mit einem sicheren Zugriffsoperator.

Starten des Programmes

Das Programm wird unter UNIX im Verzeichnis, in dem es sich befindet, mit dem Befehl ./jnd aufgerufen. Die zu bewertenden Bilder können irgendwo in der Verzeichnisstruktur abgelegt sein. Sie müssen die gleichen Pixelabmessungen besitzen und im Portable Pix Map-Format (.ppm) vorliegen. Während der Berechnungen wird der Benutzer über die gerade ausgeführten Operationen auf dem Laufenden gehalten. Nach Abschluss aller Berechnungen werden der RMS-Wert (zu Vergleichszwecken, resp. um sich überzeugen zu können, dass dieser nur sehr bedingt mit dem subjektiven Qualitätseindruck übereinstimmt) und der JND-Wert ausgegeben. Zusätzlich werden die Qualitätsstufen in eine sechsstufige Notenskala umgerechnet und angezeigt.

Hauptalgorithmus für die JND-Berechnung

In der Hauptroutine main.cc wird der JND-Wert und zum Vergleich auch der RMS-Wert der beiden Bilder berechnet und ausgegeben.

Die Berechnung des JND-Wertes besteht aus den Schritten Kontrastbildberechnung, Aufteilung in die drei Orientierungen, Normalisierung und Multiplikation mit der nichtliearen Kennlinie T (Gleichung 7.4) und anschliessend Differenzenvektorberechnung.

Um Rechnerleistung zu sparen, werden die Laplacebilder vor der Differenzberechnung nicht überabgetastet. Es wird iterativ beim tiefsten Pyramidenniveau startend ein lokales Differenzbild berechnet. Anschliessend wird es überabgetastet und zum Differenzbild der nächsthöheren Stufe hinzuaddiert.

Bei Variante a wird der globale JND-Wert als Maximum des Differenzbildes sofort ausgegeben und in die Notenskala von 1 (schlechtester Wert) bis 6 (bester Wert) umgerechnet, bei Variante b erfolgt vor diesem Schritt noch eine orientierungsabhängige Gewichtung.