Die vorliegende Erfindung betrifft ein Verfahren zur Erstellung eines Histogramms eines Bildes mit mindestens einem Farbkanal, bei dem die in einem Eingabebild pro Farbkanal auftretenden Pixelwerte in N Werteintervalle kategorisiert werden, das Eingabebild in M Pixel zerlegt wird und jedem Pixel ein Werteintervall zugeordnet wird. Innerhalb der Programmarchitektur einer Graphikkarte eines Rechners werden die Werteintervalle der Pixel des Eingabebildes in diskrete Tiefenwerte kodiert. Dabei entspricht die Anzahl der möglichen Tiefenwerte der Anzahl der Werteintervalle N. Jedem Tiefenwert ist eine Ebene zugeordnet, in der Pixel mit einem diesem Tiefenwert zugeordneten Pixelwert eingezeichnet werden und beginnend mit der tiefsten Ebene werden die Pixel kumulativ gezählt, die in dieser Ebene oder allen vorhergehenden Ebenen gezeichnet wurden und die Summen für jede Ebene als kumulatives Histogramm ausgegeben.
Beschreibung[de]
Die vorliegende Erfindung betrifft ein Verfahren zur Erstellung eines
Histogramms eines Bildes nach dem Oberbegriff des Patentanspruchs 1.
Im Kontext der Bildverarbeitung ist man oft an einem Histogramm eines
Bildes interessiert.
Mit Hilfe eines Histogramms kann man eine Aussage über die im
Bild vorkommenden Grauwerte machen, sowie über den Kontrastumfang und die Helligkeit
des Bildes. Man kann ein Histogramm außerdem dazu verwenden, um eine Histogramm-Equalisierung
durchzuführen. Ferner sind Histogramme die Grundlage histogramm-basierter Abstandsmaße
wie Mutual Information (siehe dazu F. Maes, A. Collignon, D. Vandermeulen, G. Marchal
and P. Suetens, „Multimodality Image Registration by Maximization of Mutual
Information", In IEEE Trans. on Medical Imaging, vol. 16, No 2, pages 187-198.,
April 1997) oder Verbundentropie (wie in dem Artikel von D. Hill, C. Studholme und
D. Hawkes, „Voxel similarity measures for autmated image registration", In
Visualization in Biomedical Computing 1994, volume 2359, pages 205-216. The International
Society for Optical Engeneering, SPIE Proceedings, 1994, beschrieben).
Histogramme findet man häufig im Bereich der digitalen Fotografie.
Viele digitale Fotoapparate zeigen auf dem Display während der Motivsuche als
Hilfe für ein ausgewogeneres Bild in Echtzeit oder für bereits gespeicherte
Aufnahmen ein Histogramm an. Das Betrachten eines Histogramms erlaubt es dem Fotografen,
das Ergebnis oder das geplante Foto genauer zu kontrollieren, als es das Kameradisplay
erlaubt. Zum Beispiel kann man typische Fehler wie Unter- und Überbelichtung
erkennen.
Bei einem Graubild soll abhängig von seinen Bildinhalt automatisch
Kontrast und Helligkeit optimal angepasst werden. Eine Lösung dafür ist
die so genannte Histogramm-Equalisierung. Die betrachtet das Histogramm des Eingabebildes
und transformiert dieses Eingabebild so, dass das Ergebnisbild ein gleichverteiltes
Histogramm aufweist. Viele Bild- und Photobearbeitungsprogramme bieten diese Funktionalität
an. In der automatischen Objekterkennung kommen Histogramme zum Einsatz. Ein Computer
soll in einem aufgenommenen Farbbild automatisch die darin sichtbaren Objekte identifizieren.
Bei der Analyse des Bildes werden Objekte aus einer Bilddatenbank mit Hilfe von
Histogramm-Vergleichen in der aufgenommen Szene lokalisiert und identifiziert.
Unter einem Histogramm versteht man eine Funktion, die einem Grauwert
im Bild seine relative oder absolute Häufigkeit zuweist. Damit kann man eine
Aussage darüber treffen, mit welcher Wahrscheinlichkeit ein Grauwert im Bild
vorkommt.
Bei einem Grauwertbild mit beispielsweise 256 Grauwerten weist das
nicht kumulative Histogramm mit relativen Häufigkeiten jedem Grauwert zwischen
0 und 255 eine relative Häufigkeit
zu.
Für andere Anzahlen von Grauwerten ändert sich die Formel
entsprechend.
Um ein Histogramm für ein Farbbild (oder ein anderes Bild mit
mehr als einem Kanal) zu berechnen, sind verschiedene Möglichkeiten der Histogrammberechnung
denkbar. Es ist beispielsweise möglich, den Farbraum in kleinere Subräume
zu unterteilen und diese Unterteilung für die Histogrammberechnung zu benutzen,
d.h. man zählt Auftretenshäufigkeiten von Farben innerhalb des Subraums.
Ferner kann ein Farbbild auch in einen anderen Farbraum konvertiert werden, der
sich besser zur Berechnung eines Farbhistogramms eignet: So kann man das Farbbild
aus dem RGB-Farbraum in den YUV-Farbraum umrechnen und dort nur den Y-Kanal (Luminanz-Kanal)
für die Histogrammberechnung auswerten. Eine weitere Möglichkeit der Histogrammberechnung
wäre, das Histogramm für jeden Kanal im Farbbild separat zu berechnen.
Neben einem differenzierten Histogramm gibt es auch ein kumulatives
Histogramm, das angibt, wie oft ein Grauwert kleiner oder gleich einem bestimmten
Wert vorkommt.
Für das obige Beispiel eines Grauwertbildes mit 256 Grauwerten
weist das kumulative Histogramm mit relativen Häufigkeiten hi jedem
Grauwert zwischen 0 und 225 eine kumulierte relative Häufigkeit Hi
zwischen 0 und 1 zu, die aussagt, wie häufig dieser Grauwert oder kleinere
Grauwerte vorkommen:
Bisher wurden Histogramme meistens auf der CPU (Central Processing
Unit bzw. Hauptprozessor) oder einer ähnlich flexiblen Prozessorarchitektur
(z.B. DSP – digitaler Signalprozessor) berechnet.
Um das Histogramm eines Grauwertbildes auf der CPU zu berechnen, muss
man in zwei verschachtelten Schleifen über das Bild laufen und dabei zählen,
wie oft ein bestimmter Grauwert vorkommt. Als Ergebnis erhält man die absolute
Anzahl jedes Grauwertes. Um aus den absoluten Werten die relative Häufigkeit
zu berechnen, muss man dann den jeweiligen Absolutwert durch die Gesamtanzahl der
Pixel dividieren. Im Prinzip also ein sehr einfacher Algorithmus.
Pseudocode zur Histogrammberechnung:
Für jede Zeile i des Bildes
Für jede Spalte j des Bildes
Lies den Grauwert des Pixels an der Position (i, j) Inkrementiere die Variable,
die die Anzahl des jeweiligen Grauwertes zählt
Abschließend:
Relative Häufigkeit eines Grauwertes ist Anzahl seines Auftretens geteilt
durch Anzahl der Pixel im Bild.
Neue Ansätze wie beschrieben in Y. Deuerling-Zheng, „Fast
2D Non-rigid Image Registration for Digital Subtraction Angiography using Graphics
Hardware", Friedrich-Alexander-Universität Erlangen-Nürnberg, Lehrstuhl
für Mustererkennung, 2005, versuchen aber, Histogramme auf der Grafikkarte
und dessen Spezial-Prozessor (GPU – Graphics Processing Unit) zu berechnen,
sind dabei aber langsamer als eine Implementierung auf der CPU. Auch Verfahren,
die auf den ersten Blick die Grafikkarten zur Histogrammberechnung einsetzen führen
die Berechnung wieder auf der CPU aus.
Wie erwähnt, sind frühere Ansätze wie bei Y. Deuerling-Zheng
beschrieben, die versucht haben, das Histogramm auf der Grafikkarte zu berechnen,
stets wesentlich langsamer als die Berechnung des Histogramms auf der CPU. Um dies
zu erklären, sind in den folgenden Absätzen die Probleme beschrieben,
die man bei der Implementierung des Histogramms auf der Grafikkarte hat.
Es ist nicht unmittelbar möglich, das Konzept der iterativen
Berechnung des Histogramms auf der Grafikkarte auszuführen. Zwar ist es auch
hier möglich, ein Programm in einer C-ähnlichen Syntax zu schreiben, das
auf der Grafikkarte aufgerufen wird, doch treten dabei mehrere Probleme auf: In
einem Programm auf der Grafikkarte ist es zum einen sehr ineffizient, in zwei verschachtelten
Schleifen innerhalb dieses Programms über das Bild zu laufen (vgl. Pseudocode
von oben), zum anderen ist dies für größere Bilder aufgrund der Begrenzung
heutiger Hardware nicht möglich.
Um dieses Problem der ineffizienten Implementierung von verschachtelten
Schleifen auf der Grafikkarte zu umgehen, kann das Programm auf der Grafikkarte
für jeden Pixel einmal aufgerufen werden, so wie es in dem Artikel, Simon Green,
„Image Processing Tricks in OpenGL", NVIDIA Corporation, GameDevelopers Conference,
zu beziehen unter http://download.nvidia.com/developer/presentations/2005/GDC/O
penGL_Day/OpenGL_Image_Processing_Tricks.pdf,2005, vorgeschlagen wird: Dort wurde
für jeden möglichen Grauwert ein Programmdurchlauf ausgeführt, bei
dem nur die Pixel gezeichnet wurden, die diesen Grauwert besaßen. Nach jedem
Programmdurchlauf waren die gezeichneten Pixel zu zählen, wofür Occlusion-Queries
(eine in der Grafikhardware implementierte Möglichkeit, die Anzahl gezeichneter
Pixel zu zählen) eingesetzt wurden.
Ein weiteres Problem besteht darin, dass es in einem Programm auf
der Grafikkarte nicht effizient möglich ist, abhängig vom Grauwert eine
bestimmte Variable zu inkrementieren. Dies liegt nach R. Chisu, „Techniques
for Accelerating Intensitybased Rigid Image Registration", Technische Universität
München, Fakultät für Informatik, 2005, vor allem daran, dass es
nicht möglich ist, wahlfrei in einen Ausgabespeicher zu schreiben. Ferner ist
die Anzahl der möglichen Ausgaben sehr begrenzt.
Der vorliegenden Erfindung liegt die Aufgabe zugrunde, ein Verfahren
zur Erstellung eines Histogramms eines Bildes anzugeben, das schnell und effizient
ist und die CPU eines Rechners nicht belastet.
Diese Aufgabe wird mit dem Verfahren gemäß Patentanspruch
1 gelöst.
In den Unteransprüchen sind Merkmale bevorzugter Ausführungsformen
der Erfindung gekennzeichnet.
Um das Histogramm effizient und schnell zu berechnen, wird erfindungsgemäß
ein Verfahren angewandt, das auf der Grafikkarte ausgeführt wird und dem das
zu analysierende Grauwertbild als Eingabe übergeben wird.
In einem ersten Schritt wird jeder Pixel des Bildes (im Folgenden
als Eingabebild bezeichnet), für das ein Histogramm zu berechnen ist, in einen
Tiefenwert überführt. Tiefenwerte werden im Allgemeinen eingesetzt, um
bei der Darstellung einer dreidimensionalen Szene zu entscheiden, welcher Teil dieser
dreidimensionalen Szene vorne ist (und damit sichtbar), und welcher Teil hinten
ist (und damit verdeckt und nicht sichtbar). Dieser Vergleich der Verdeckung wird
mit Hilfe des Tiefenwerts bestimmt und gibt dadurch an, welche Pixel zu zeichnen
sind und welche nicht. Die Menge der Tiefenwerte bildet den Tiefenpuffer (Z-Buffer)
der Grafikkarte.
Diese Tiefenwerte werden benutzt, um den Grauwert des Pixels in eine
Tiefeninformation eindeutig umzukodieren. Dabei wird für jeden Pixel im Eingabebild
ein Farbpunkt gezeichnet, dem abhängig von seinem Grauwert ein kleinerer oder
größerer Tiefenwert zugewiesen wird. Das bedeutet, dass aus einem Grauwertbild
ein Tiefenbild mit gleicher Auflösung erzeugt wird.
Im Folgenden wird die Erfindung anhand der Beschreibung eines Ausführungsbeispiels
unter Bezugnahme auf die Zeichnung näher erläutert. Darin zeigen:
1: die Umwandlung der Grauwerte eines Bildes mit 3
Grauwerten in einen Tiefenpuffer mit 3 Tiefenstufen;
2: das Setzen der Datenebene hinter t3 und anschließende
Projektion unter Berücksichtigung des Tiefenpuffers;
3: das Setzen der Datenebene zwischen t2 und t3 und
anschließende Projektion unter Berücksichtigung des Tiefenpuffers;
4: das Setzen der Datenebene zwischen t1 und t2 und
anschließende Projektion unter Berücksichtigung des Tiefenpuffers;
5: das Setzen der Datenebene vor t1 und anschließende
Projektion unter Berücksichtigung des Tiefenpuffers;
6: das sich ergebene kumulative relative Histogramm
und das differenzierte relative Histogramm für das Eingabebild gemäß
1, und
7: ein Flussdiagramm zur Erläuterung des Ablaufs
des erfindungsgemäßen Verfahrens.
Die Berechnung von Histogrammen auf Grafikkarten bringt eine ganze
Reihe von Vorteilen mit sich.
Es ist heute schon so, dass einige Bildverarbeitungs-Algorithmen bevorzugt
auf der Grafikkarte implementiert werden, da sich die Architektur der Grafikkarte
aufgrund ihrer massiv parallelen Verarbeitung für diese Art von Problemstellungen
besonders eignet. Wurden in einem derartigen Kontext bisher Histogramme benötigt,
so war der Nutzen einer Implementierung auf der Grafikkarte fraglich, da keine effiziente
Histogrammberechnung zur Verfügung stand und diese häufig auf der CPU
des PCs durchgeführt werden musste. Damit mussten die Daten von der Grafikkarte
geholt, auf dem Hauptprozessor gerechnet und die Ergebnisse wieder auf die Grafikkarte
hochgeladen werden. Durch dieses umständliche und zeitaufwändige Kopieren
der Daten zwischen Grafikkarte und Hauptprozessor war der Zeitvorteil, den die eigentliche
Implementierung des Bildverarbeitungsalgorithmus auf der GPU besitzt, zunichte gemacht.
Durch unser Verfahren zur schnellen Histogrammberechnung auf Grafikkarten
wird die Implementierung einer ganzen Reihe von Algorithmen auf der Grafikkarte
sehr attraktiv. Besonders alle Algorithmen, die auf einem statistischen Ansatz aufbauen,
gewinnen enorm, da diese faktisch immer ein Histogramm der Grauwerte benötigen.
Zu dieser Gruppe gehören z.B. 2-D/3-D und 3-D/3-D Registrierungsalgorithmen.
Auch viele Algorithmen, die zur 2-D-Bildverbeserung von z.B. Fluoroskopie-Aufnahmen
eingesetzt werden benötigen Histogramme. Nachdem der Trend auch hier dazu geht,
diese Algorithmen auf Grafikkarten zu implementieren, ist der vorgestellte Ansatz
zur Histogrammberechnung von Bedeutung.
Ganz prinzipiell ist der Vorteil der Implementierung von Algorithmen
auf der Grafikkarte darin zu sehen, dass in der Zeit, in der die Grafikkarte einen
Algorithmus abarbeitet, die CPU des PCs für andere Aufgaben frei ist. Durch
die vorgestellte Histogrammberechnung ist eine ganze Gruppe von Algorithmen jetzt
für die Implementierung auf Grafikkarten geeignet.
Obwohl wir hier den Ansatz nur für Grauwertbilder diskutiert
haben, lässt er sich direkt wie oben beschrieben auf Farbbilder anwenden.
1 zeigt die Umwandlung der Grauwerte eines Eingabebildes
mit drei Grauwerten (t1 = hellgrau, t2 = dunkelgrau, t3 = schwarz) in einen Tiefenpuffer
mit drei Tiefenstufen t1, t2, t3. In 1 ist oben stark
vereinfachtes Eingabebild mit nur neun Pixeln gezeigt, welches Pixel mit verschiedenen
Grauwerten, nämlich hellgrau, dunkelgrau und schwarz aufweist. Dieses Grauwertbild
wird erfindungsgemäß in einer Grafikkarte in einen Tiefenpuffer (Z-Buffer)
konvertiert. In 1 unten ist ein solcher Z-Buffer schematisch
dargestellt. Legt man das 2-dimenionale Eingabebild in eine XY-Ebene, so weist der
Tiefenpuffer eine vorbestimmte Anzahl von zur XY-Ebene parallelen Ebenen auf, die
entlang der Z-Achse aufgereiht ist. Die einzelnen Ebenen im Z-Buffer sind für
das dargestellte Beispiel t1, t2 und t3. Dabei bezeichnet t3 die „hinterste
Ebene" und t1 die „vorderste Ebene". Die dunkelsten Pixel, in diesem Fall
schwarz liegen in der Ebene auf der Höhe t3, die dunkelgrauen Pixel liegen
in der Ebene t2 und die hellgrauen Pixel in der Ebene t1.
Die Umkodierung der Grauwerte in Tiefenwerte kann z.B. effizient mit
Hilfe eines Fragmentprogramms, beispielsweise eines Pixel-Shaders bzw. Fragment-Shaders,
auf der GPU der Grafikkarte ausgeführt werden. Auf heutigen Grafikkarten nimmt
der Tiefenwert einen Wert zwischen 0 und 1 an, sodass man bei der Ausgabe des Fragmentprogramms
auf diese Normierung achten muss.
Bei einem Bild mit beispielsweise 256 Grauwerten gibt das Programm
auf der Grafikkarte für den Grauwert 0 einen Tiefenwert von 1 aus, für
den Grauwert 255 einen Tiefenwert von 0 aus und für einen Grauwert zwischen
0 und 255 einen absteigenden Tiefenwert zwischen 1 und 0 in Schritten von
1256
.
Nach der Ausführung des Programms auf der Grafikkarte werden
nun nacheinander von hinten nach vorne so viele Ebenen gezeichnet, wie es zu unterscheidende
Grauwerte gibt, also genau so viele wie es der erwünschten Auflösung des
Histogramms entspricht. Da die Ebenen „von hinten nach vorne" gezeichnet
werden, verdeckt eine neu gezeichnete Ebene immer die Ebene, die im vorherigen Schritt
gezeichnet wurde. Dementsprechend enthält auch der Tiefenpuffer der Grafikkarten
nach jeder Ebene neue Werte für die Stellen, an denen ein Pixel gezeichnet
wurde. Das Zeichnen der Ebenen in bestimmten Tiefen ist nötig, um Pixel in
der entsprechenden Tiefe einzusammeln.
2 zeigt die Projektion der Datenebene „hinter
t3" unter Berücksichtigung des Tiefenpuffers. Unten links in 2
ist das Ergebnis angezeigt, d.h. es werden keine Pixel im Ausgabebild gezeichnet.
Im kumulativen Histogramm heißt das, dass es keine Werte größer als
t3 gibt. Somit ist
in Gleichung 2.
Den nächsten Schritt zeigt 3, nämlich
die Projektion der Datenebene „zwischen" t2 und t3 unter Berücksichtigung
des Tiefenpuffers. Unten links ist das Ergebnis gezeigt: Es werden vier Pixel im
Ausgabebild gezeichnet. Das heißt im kumulativen Histogramm gibt es insgesamt
vier Werte größer oder gleich als t3.
Somit ist in 2:
4 zeigt die Projektion der Datenebene zwischen t1 und
t2 unter Berücksichtigung des Tiefenpuffers. Hier werden im links unten dargestellten
Ausgabebild sieben Pixel gezeichnet, d.h. im kumulativen Histogramm gibt es insgesamt
sieben Werte größer oder gleich als t2. Somit ist
in Gleichung 2.
Die Grafikkarte überprüft nun mit Hilfe des Tiefenpuffers,
welche Pixel jeder neuen Ebene überhaupt gezeichnet werden dürfen. Es
können nämlich nur diese Pixel gezeichnet werden, die den gleichen oder
kleineren Wert haben als der Wert, der an der entsprechenden Pixelposition schon
im Tiefenpuffer eingetragen ist. Geht man von einer in der Praxis realistischen
Auflösung aus, d.h. wenn das Eingabebild z.B. aus 256 Grauwerten besteht und
das gewünschte Histogramm diese Auflösung bieten soll, dann müssen
256 Ebenen eingezeichnet werden, die sich in immer geringerer Tiefe befinden. Die
erste Ebene wird in einer solchen Tiefe gezeichnet, dass ihr ein Tiefenwert 1 im
Tiefenpuffer zugewiesen wird. Jede weitere Ebene (bei 256 zu unterscheidenden Grauwerten)
wird so gezeichnet, dass sie um
1256
tel weniger tief ist, also vor der davor gezeichneten Ebene liegt. Die letzte Ebene
hat schließlich einen Tiefenwert von Null und befindet sich damit vor allen
anderen Ebenen und allen Farbpunkten, die vom Programm der Grafikkarte im ersten
Schritt gezeichnet wurden.
5 zeigt die Projektion der Datenebene „vor t1„
unter Berücksichtigung des Tiefenpuffers. Hier werden im gezeigten Beispiel
neun Pixel im Ausgabebild links unten gezeichnet, d.h. im kumulativen Histogramm
gibt es insgesamt neun Werte größer oder gleich t1. Dies ist auch genau
das Ergebnis, das man von einem kumulativen Histogramm erwartet, d.h. es muss die
Gesamtanzahl der vorhandenen Pixel herauskommen. Somit ist in Gleichung 2:
Um die Anzahl der gezeichneten Pixel zu zählen, welches die Pixel
mit einem gleich großen oder kleineren Wert wie im Tiefenpuffer sind, werden
so genannte Occlusion-Queries eingesetzt. Occlusion-Queries sind die in der Grafik-Hardware
implementierte Möglichkeit, die Anzahl gezeichneter Pixel effizient zu zählen.
Diese bieten die Möglichkeit zu bestimmen, wie viele Pixel in einem Zeichenschritt
tatsächlich gezeichnet worden sind. Da aber nur diese Pixel gezeichnet werden,
die den Tiefenwert der Ebene oder kleiner haben, wird als Ergebnis nach jedem Zeichen/Zählschritt
ein Wert des kumulativen Histogramms mit absoluten Häufigkeiten ausgegeben.
Aus diesem kumulativen Histogramm mit absoluten Häufigkeiten
muss nun noch das nicht kumulative Histogramm mit relativen Häufigkeiten berechnet
werden. Dafür wird zunächst das nicht kumulative Histogramm mit absoluten
Häufigkeiten berechnet, indem die Differenz zwischen zwei benachbarten Werten
für benachbarte Ebenen des kumulativen Histogramms berechnet wird. Danach wird
das nicht kumulative Histogramm mit relativen Häufigkeiten berechnet, indem
der Absolutwert der gezählten Pixel durch die Gesamtanzahl der Pixel dividiert
wird.
6 zeigt oben das resultierende kumulative relative
Histogramm für das Eingabebild mit drei Grauwerten gemäß
1 bis 5 und unten ist
das aus dem kumulativen Histogramm berechnete relative Histogramm dargestellt. Dabei
den die Werte
bis
berechnet als
und
und
Als weitere Option ist es möglich, die Quantisierung des Histogramms
in größeren Einheiten durchzuführen. So kann es z.B. ausreichend
sein für eine bestimmte Anwendung, aus einem Grauwertbild mit 256 möglichen
Grauwerten ein Histogramm mit 64 oder 128 Auflösungsstufen zu berechnen. Dabei
wird aus einem Bereich von Werten eine Gruppe gebildet, die von da an als gemeinsame
Einheit im Histogramm betrachtet werden soll. Dies geschieht erfindungsgemäß
auf der Grafikkarte, indem weniger Ebenen gezeichnet werden. Es werden also nicht
256 Ebenen im Abstand von 0 bis 1 mit einer
1256
gezeichnet sondern z.B. 64 oder 128 mit einer Schrittweite von
164
bzw.
1128
.
In 7 ist der Ablauf der einzelnen Verfahrensschritte
in der Grafikkarte eines Rechners noch einmal zusammengefasst.
Durch das erfindungsgemäße Verfahren zur schnellen Histogrammberechnung
auf Grafikkarten wird die Implementierung einer ganzen Reihe von Algorithmen auf
der Grafikkarte sehr attraktiv. Besonders alle Algorithmen, die auf einem statistischen
Ansatz aufbauen, gewinnen enorm, da diese faktisch immer ein Histogramm der Grauwerte
benötigen. Zu dieser Gruppe gehören z.B. 2-D/3-D und 3-D/3-D Registrierungs-Algorithmen.
Auch viele Algorithmen, die zur 2-D-Bildverbesserung von z.B. Fluoroskopie-Aufnahmen
eingesetzt werden, benötigen Histogramme. Nachdem der Trend auch hier dazu
geht, diese Algorithmen auf Grafikkarten zu implementieren, ist der vorgestellte
Ansatz zur Histogrammberechnung von Bedeutung.
Es ist zwar heute schon so, dass einige Bildverarbeitungs-Algorithmen
bevorzugt auf der Grafikkarte implementiert werden, da sich die Architektur einer
Grafikkarte aufgrund ihrer massiv parallelen Verarbeitung für diese Art von
Problemstellungen besonders eignet. Wurden in einem derartigen Kontext bisher Histogramme
benötigt, so war der Nutzen einer Implementierung auf der Grafikkarte jedoch
fraglich, da keine effiziente Histogrammberechnung zur Verfügung stand und
diese häufig dann doch wieder auf der CPU des PCs durchgeführt werden
musste. Dabei mussten die Daten von der Grafikkarte geholt, auf dem Hauptprozessor
gerechnet und die Ergebnisse wieder auf die Grafikkarte hochgeladen werden. Durch
dieses umständliche und zeitaufwendige Kopieren der Daten zwischen Grafikkarte
und Hauptprozessor war der Zeitvorteil, den die eigentliche Implementierung des
Bildverarbeitungsalgorithmus auf der GPU besitzt, zunichte gemacht.
Ganz prinzipiell ist bei dem erfindungsgemäßen Verfahren
der Vorteil der Implementierung von Algorithmen auf der Grafikkarte darin zu sehen,
dass in der Zeit, in der die Grafikkarte einen Algorithmus abarbeitet, die CPU des
PCs für andere Aufgaben frei ist.
Die oben stehende Beschreibung eines Ausführungsbeispiels der
vorliegenden Erfindung bezieht sich auf Grauwertbilder. Wie jedoch bereits in der
Beschreibungseinleitung erwähnt, lässt sich das beschriebene Konzept ohne
weiteres auch auf Farbbilder anwenden.
Anspruch[de]
Verfahren zur Erstellung eines Histogramms eines Bildes mit mindestens
einem Farbkanal,
bei dem die in einem Eingabebild pro Farbkanal auftretenden Pixelwerte in N Werteintervalle
kategorisiert werden,
das Eingabebild in M Pixel zerlegt wird und jedem Pixel ein Werteintervall zugeordnet
wird,
dadurch gekennzeichnet, dass
innerhalb der Programmarchitektur einer Graphikkarte eines Rechners die Werteintervalle
der Pixel des Eingabebildes in diskrete Tiefenwerte kodiert werden, wobei die Anzahl
der möglichen Tiefenwerte der Anzahl der Werteintervalle N entspricht, jedem
Tiefenwert eine Ebene zugeordnet ist, in der Pixel mit einem diesem Tiefenwert zugeordneten
Pixelwert eingezeichnet werden und beginnend mit der tiefsten Ebene die Pixel kumulativ
gezählt werden, die in dieser Ebene oder allen vorhergehenden Ebenen gezeichnet
wurden und die Summen für jede Ebene als kumulatives Histogramm ausgegeben
werden.Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass das kumulative
Histogramm in ein differenziertes Histogramm überführt wird, indem jeweils
der vorhergehende ausgegebene Summenwert von dem aktuellen Summenwert einer Ebene
abgezogen wird und die Differenzwerte ausgegeben werden.Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die Zählung
der gezeichneten Pixel mittels Occlusions-Queries erfolgt.Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet,
dass die Anzahl der in jeder Ebene gezählten Pixel durch die Gesamtanzahl der
Pixel dividiert wird, um die relativen Häufigkeiten der Pixel in den einzelnen
Ebenen oder den bis dahin gezählten Ebenen zu bestimmen.Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet,
dass die Summenwerte des Histogramms für jeweils eine Untergruppe von Ebenen
erstellt wird, um die Auflösung zu reduzieren.Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet,
dass das Eingabebild ein Schwarz-Weiß-Bild ist und die Pixelwerte Grauwerten
entsprechen.Verfahren nach einem der Ansprüche 1-5, dadurch gekennzeichnet,
dass das Eingabebild ein Farbbild oder ein Bild mit mehreren Kanälen ist, wobei
jeweils für die einzelnen Farbkanäle Histogramme erstellt werden.Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass vor der Erstellung
eines Histogramms der Farbraum eines Eingabebildes in einen anderen Farbraum konvertiert
wird.Verfahren nach Anspruch 8, dadurch gekennzeichnet, dass das Eingabebild
aus dem RGB-Farbraum in den YUV-Farbraum konvertiert wird und dort nur der Y-Kanal,
d.h. der Lumineszenzkanal, für die Histogrammberechnung ausgewertet wird.Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet,
dass die Umkodierung der Pixelwerte in Tiefenwerte auf der GPU der Graphikkarte
mit einem Pixel-Shader- oder Fragment-Shader-Programm erfolgt.