PatentDe  


Dokumentenidentifikation DE102006028941A1 27.12.2007
Titel Verfahren zur Erstellung eines Histogramms eines Bildes
Anmelder Siemens AG, 80333 München, DE
Erfinder Deinzer, Frank, 90552 Röthenbach, DE;
Kubias, Alexander, 56412 Boden, DE
DE-Anmeldedatum 23.06.2006
DE-Aktenzeichen 102006028941
Offenlegungstag 27.12.2007
Veröffentlichungstag im Patentblatt 27.12.2007
IPC-Hauptklasse H04N 1/407(2006.01)A, F, I, 20060623, B, H, DE
IPC-Nebenklasse H04N 1/56(2006.01)A, L, I, 20060623, B, H, DE   G06T 7/00(2006.01)A, L, I, 20060623, B, H, DE   
Zusammenfassung 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.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com