PatentDe  


Dokumentenidentifikation DE102006053116A1 31.05.2007
Titel Verfahren und System zur Histrogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit
Anmelder Siemens Medical Solutions USA, Inc., Malvern, Pa., US
Erfinder Fluck, Oliver, Plainsboro, N.J., US;
Aharon, Shmuel, West Windsor, N.J., US;
Rousson, Mikael, Trenton, N.J., US;
Cremers, Daniel, 53117 Bonn, DE
Vertreter KRAMER - BARSKE - SCHMIDTCHEN, 81245 München
DE-Anmeldedatum 10.11.2006
DE-Aktenzeichen 102006053116
Offenlegungstag 31.05.2007
Veröffentlichungstag im Patentblatt 31.05.2007
IPC-Hauptklasse G06T 1/20(2006.01)A, F, I, 20070212, B, H, DE
IPC-Nebenklasse G06T 5/40(2006.01)A, L, I, 20070212, B, H, DE   
Zusammenfassung Ein Verfahren zur Histogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU) enthält das Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet; das Unterteilen des Gebietes in unabhängige Gebiete oder Flächen; das parallele Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche; und das parallele Aufsummieren in der GPU von den Flächenhistogrammen, so dass ein abschließendes Bildhistogramm abgeleitet wird.

Beschreibung[de]

Die vorliegende Erfindung bezieht sich auf das Gebiet der Bildbearbeitung und insbesondere auf das Gebiet der Histogrammberechnung.

Aufgrund der immensen Berechnungsleistung von Grafikprozessoren (GPU) der heutigen Zeit wurde die Berechnung auf GPU's für allgemeine Zwecke ein sehr aktives Gebiet der Forschung und Entwicklung. Die Leistung von Algorithmen, die auf GPU's laufen, hängt sehr stark davon ab, wie gut sie angeordnet werden können, dass sie zu der Single Instruction Multiple Data (SIMD) Architektur des Prozessors passen und diese ausnützen. Viele Aufgaben, die als einfach angesehen werden zum Durchführen auf einer Central Prozessing Unit (CPU), wie z.B. das Gruppieren und Zählen von Werten eines Gebiets für statistische Zwecke, stellen merkliche Herausforderungen zur Implementierung auf einer GPU dar. Siehe Kevin Bjorke: Color Controls, GPU Gems, Addison-Wesley, 2004, Kapitel 22 und 24.

Ein Algorithmus entsprechend der vorliegenden Erfindung ermöglicht das Berechnen von Histogrammen auf Grafikarten. Histogramme sind ein Schlüsselfaktur für das Verständnis, die Interpretation und die Verarbeitung von digitalen Bildern. Sie werden für verschiedene Zwecke verwendet, einschließlich der Analyse des Bereichs und der Verteilung von Werten in einem Bild. Während GPU's gegenwärtig weit verbreitet sind zum Verarbeiten und Visualisieren von Bildern bei interaktiven Raten und Bildverarbeitungsalgorithmen zur Farbkorrektur und Filterung erfolgreich auf GPU's implementiert worden sind, scheint ein praktischer Weg zum Berechnen eines Histogramm vollständig auf einer GPU schwer fassbar geblieben zu sein.

Entsprechend muss ein Histogramm im Allgemeinen auf der CPU berechnet werden und an die GPU übertragen werden. Aufgrund der begrenzten Transferbandbreite, die typischerweise verfügbar ist, ist das Übertragen von Daten zwischen der GPU und der CPU ein kostenintensiver Vorgang. Im Allgemeinen ziehen Anwendungen nur Nutzen von der GPU-Leistung, wenn sie vollständig auf Grafikhardware laufen können.

Entsprechend einem Aspekt der Erfindung enthält ein Verfahren zur Histogrammberechnung unter Verwendung einer Graphikverarbeitungseinheit (GPU): Das Speichern von Bilddaten in einem zweidimensionalen (2D) Strukturgebiet; Aufteilen des Gebiets in unabhängige Gebiete oder Flächen; paralleles Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche; und paralleles Aufsummieren der Flächenhistogramme in der GPU, so dass ein abschließendes Bildhistogramm abgeleitet wird.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Unterteilens des Gebiets das Unterteilen des Gebiets in gleich große und voneinander unabhängige Gebiete.

Entsprechend einem anderen Aspekt der Erfindung enthält der Schritt des Berechnens einer Mehrzahl von Flächenhistogrammen: Zählen der Intensität in einem Texel, die durch Texeltexturkoordinaten bestimmt wird, die Anzahl der Histogrammkästen und die Größe der Bilddaten.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Berechnens einer Mehrzahl von Flächenhistogrammen: Bestimmen für jeden Texel einen entsprechenden Kasten unter Verwendung von Texturkoordinaten.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Berechnens einer Mehrzahl von Flächenhistogrammen: Zählen für jeden Texel das Auftreten von Werten im Inneren von seiner zugehörigen Fläche für den entsprechenden Histogrammkasten.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Bestimmens eines entsprechenden Kastens für jeden Texel durch Texturkoordinaten: Bestimmen des gleichen entsprechenden Kastens für jeden Texel, der die gleiche gegebene Position in seiner jeweiligen zugehörigen Fläche hat.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des parallelen Aufsummierens: Anwenden eines flächenweisen Texturverringerungsvorgangs.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Anwendens eines Texturverringerungsvorgangs das Durchführen eines Renderdurchlaufs zum Halbieren der Texturgröße.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Ausführens eines Renderdurchlaufs zum Halbieren der Texturgröße das Aufsummieren des i-ten Texels eines gegebenen Histogramms mit dem i-ten Texel der drei Flächen, die in einer positiven Texturkoordinatenrichtung angrenzend sind.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Speicherns von Bilddaten das Verwenden von zumindest einer aus einer RGB und RGBA Textur.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Speicherns von Bilddaten das Verwenden von zumindest einem aus Leuchtkraft (c=1), RGB (c=3) und RGBA (c=4) Textur, so dass ein Histogramm von n Kästen in einer quadratischen Flächengröße von sqrt(n/c) × sqrt(n/c) Texeln entsteht, wobei c die Anzahl der Kanäle pro Texel ist.

Gemäß einem anderen Aspekt der Erfindung enthält ein Verfahren zur Histogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU) das Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet; das Unterteilen des Gebiets in unabhängige Gebiete oder Flächen durch Unterteilen des Gebiets in gleichmäßig große und unabhängige Flächen; das parallele Berechnen in einer GPU einer Mehrzahl von Flächenhistogrammen, eines für jede Fläche, und Bestimmen für jeden Texel einen entsprechenden Kasten unter Verwendung von Texturkoordinaten durch Zählen des Auftretens von Werten im Inneren von seiner zugehörigen Fläche für jeden Texel für den entsprechenden Histogrammkasten; das parallele Aufsummieren der Flächenhistogramme in der GPU, so dass ein abschließendes Bildhistogramm abgeleitet wird, indem ein Texturreduktionsvorgang angewendet wird, indem ein Renderdurchlauf zum Halbieren der Texturgröße ausgeführt wird, indem der i-te Texel eines gegebenen Histogramms mit dem i-ten Texel der drei Flächen angrenzend in einer positiven Texturkoordinatenrichtung aufsummiert wird.

Gemäß einem anderen Aspekt der Erfindung enthält ein Verfahren zur Histogrammberechnung, das eine Grafikverarbeitungseinheit (GPU) enthält: Speichern von eingegebenen Daten in einem zweidimensionalen (2D) Texturgebiet; Unterteilen des Gebiets in gleichmäßig bemessene Abschnitte; parallel Ableiten in der GPU einen Satz von Histogrammen, der ein Histogramm für jeden der Abschnitte enthält; und Summieren des Satzes der Histogramme zum Ableiten eines abschließenden Histogramms.

Gemäß einem anderen Aspekt der Erfindung enthält ein Verfahren zur Bildhistogrammberechnung, das eine Grafikverarbeitungseinheit (GPU) enthält: Speichern von eingegebenen Bilddaten in einem zweidimensionalen (2D) Texturgebiet; Unterteilen des Gebiets in gleichmäßig große Abschnitte; parallel in der GPU Ableiten eines Satzes von Bildhistogrammen, der ein Histogramm für jeden der Abschnitte enthält; und Summieren des Satzes von Bildhistogrammen zum Ableiten eines abschließenden Histogramms.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Ableitens eines Satzes von Bildhistogrammen: Bestimmen eines entsprechenden Kastens für jeden Texel.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Ableitens eines Satzes von Bildhistogrammen: Bestimmen eines entsprechenden Kastens unter Verwendung von Texturkoordinaten für jeden Texel.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Anwendens eines Texturverringerungsvorgangs: Ausführen eines Renderdurchlaufs zum Halbieren der Texturgröße.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Ausführens eines Renderdurchlaufs zum Halbieren der Texturgröße: Aufsummieren des i-ten Texels eines gegebenen Histogramms mit dem i-ten Texel der drei Flächen angrenzend in einer positiven Texturkoordinatenrichtung.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Ableitens eines Satzes von Histogrammen: Anwenden eines Texturreduktionsvorgangs.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Anwendens eines Texturreduktionsvorgangs: Summieren in jedem Texel einer zugehörigen Fläche alle Zähler innerhalb der zugehörigen Fläche, die dem entsprechenden Kasten entsprechen, der für das jeweilige Texel bestimmt ist, so dass ein kombiniertes Bildhistogramm erhalten wird.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Anwendens eines Texturreduktionsvorgangs: Wiederholen der Schritte des Texturreduktionsvorgangs, so dass ein abschließendes Bildhistogramm erhalten wird.

Gemäß einem anderen Aspekt der Erfindung enthält der Schritt des Anwendens eines Texturreduktionsvorgangs: Summieren in jedem Texel einer zugehörigen Fläche aller Zähler innerhalb der zugehörigen Fläche, die dem entsprechenden Kasten entsprechen, der für das jeweilige Texel bestimmt ist; und Summieren des Satzes von Histogrammen zum Ableiten eines abschließenden Bildhistogramms.

Gemäß einem anderen Aspekt der Erfindung enthält ein System zur Histogrammberechnung, das eine Grafikverarbeitungseinheit (GPU) verwendet: Eine Speichereinrichtung zum Speichern eines Programms und anderer Daten; und eine Prozessoreinrichtung in Kommunikationsverbindung mit der Speichereinrichtung, wobei der Prozessor arbeitet mit dem Programm zum Ausführen von: Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet; Unterteilen des Gebiets in unabhängige Gebiete oder Flächen; paralleles Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche; und paralleles Aufsummieren in der GPU der Flächenhistogramme, so dass ein abschließendes Bildhistogramm abgeleitet wird.

Gemäß einem anderen Aspekt der Erfindung arbeitet der Prozessor mit dem Programm zum Ausführen von: Unterteilen des Gebiets in gleichgroße und unabhängige Gebiete.

Gemäß einem anderen Aspekt der Erfindung arbeitet der Prozessor mit dem Programm zum Ausführen von: Zählen der Intensität in einem Texel, die durch Texeltexturkoordinaten bestimmt ist, die Anzahl der Histogrammkästen und die Größe der Bilddaten.

Gemäß einem anderen Aspekt der Erfindung enthält ein Computerprogrammprodukt ein von einem Computer verwendbares Medium, das eine Computerprogrammlogik darauf aufgezeichnet hat für einen Programmcode zur Histogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU), durch: Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet; Unterteilen des Gebiets in unabhängige Gebiete oder Flächen; paralleles Berechnen einer Mehrzahl von Flächenhistogrammen, eines für jede Fläche, in einer GPU; und paralleles Aufsummieren in der GPU der Flächenhistogramme, so dass ein abschließendes Bildhistogramm abgeleitet wird.

Gemäß einem anderen Aspekt der Erfindung enthält ein Verfahren zur Histogrammberechnung, das eine Grafikverarbeitungseinheit (GPU) verwendet, das Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet; das Unterteilen des Gebiets in unabhängige Gebiete oder Flächen; das parallele Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche; und das parallele Aufsummieren der Flächenhistogramme in der GPU, so dass ein abschließendes Bildhistogramm abgeleitet wird.

Die Erfindung ist vollständiger zu verstehen aus der detaillierten Beschreibung, die folgt, in Verbindung mit der Zeichnung, in denen:

1 in diagrammartiger Weise Schritte gemäß den Prinzipien der Erfindung zeigt;

2 in diagrammartiger Weise zugeordnete Schritte gemäß den Prinzipien der vorliegenden Erfindung zeigt; und

3 in grundlegender schematischer Form einen digitalen Prozessor zeigt, der zur Zweiwegedatenverbindung mit einer Eingabeeinrichtung, mit einer Ausgabeeinrichtung, einer GPU und einer Speichereinrichtung zum Speichern eines Programms und anderer Daten, wie sie typischerweise in einer Ausführungsform der vorliegenden Erfindung verwendet werden, verbunden ist.

Gemäß den Prinzipien der vorliegenden Erfindung wird hier ein Verfahren zum Berechnen von Histogrammen in Shader-Programmen, typischerweise in einer GPU, offenbart, wie es anschließend durch beispielhafte Ausführungsformen beschrieben wird.

Ein Bildhistogramm ist eine Darstellung der Bildintensitätenverteilung durch Rechtecke, auch als Kästen bezeichnet, wovon die Breiten Klassenintervalle darstellen und deren Flächen proportional zu den entsprechenden Bildintensitätsfrequenzen sind.

Das Histogramm wird typischerweise durch Zählen von ausgeprägten Bildintensitäten in jeweilige Kästen erzeugt. Während dies eine verhältnismäßig triviale Aufgabe zur Implementierung auf einer CPU ist, macht die Streaming-Architektur der gegenwärtigen Grafikverarbeitungseinheiten dies zu einer schwierigen Aufgabe. Ein Grund dafür ist, dass die GPU es einem nicht erlaubt, in Speicherorte zu schreiben, die durch deren Eingabewert bestimmt werden. Das bedeutet, dass es nicht möglich ist, die Bildintensität bei einem gegebenen Pixel zu prüfen, den Kasten zu bestimmen, dem sie zugefügt werden sollte, und dann sie diesem Kasten zuzufügen. Zusätzlich ist es aufgrund von Performancegründen nicht möglich, die eingegebenen Werte auf die entsprechende Anzahl von Kästen zu minimieren und das Gesamtbild für jeden Kasten in dem Fragmentshader in der GPU abzutasten.

In der Grafik wird ein Fragmentshader typischerweise verwendet, um die Farbwerte von Pixeln eines Bildes durch Berechnen der Farbe (rot, grün, blau), der Transparenz (Alpha) und (in 3D-Grafiken) der Tiefenwerte der Fragmente zu bestimmen.

Prinzipien für eine Ausführungsform gemäß der vorliegenden Erfindung enthalten das Folgende: Die eingegebenen Daten werden in einer 2D-Textur mit der Leistung von zwei Dimensionen gespeichert, und das Gebiet wird in gleichgroße und unabhängige Gebiete aufgeteilt (die auch als Abschnitte oder „Flächen" bezeichnet werden). Die Flächengröße hängt von der Granularität des Histogramms ab. Unter Verwendung von typischen Werten von Leuchtkraft (c=1), RGB (c=3) oder RGBA (c=4) Textur führt ein Histogramm von n-Kästen zu einer Quadratflächengröße von sqrt(n/c) × sqrt(n/c) Texturelementen oder „Texeln", wobei c die Anzahl von Kanälen pro Texel ist. Die Anzahl von Flächen entspricht der eingegebenen Texturgröße geteilt durch die Größe der Flächen. Ein Histogramm wird für jeden Abschnitt erzeugt und dann werden die Abschnittshistogramme alle in ein abschließendes Bildhistogramm aufsummiert. Die Intensität oder Intensitäten, die in einem Texel gezählt wird/werden, wird/werden durch seine Texturkoordinaten und die Anzahl der Histogrammkästen bestimmt.

Unter Verwendung von diesem Schema werden eine Mehrzahl von lokalen Histogrammen parallel berechnet. Jeder Texel von einer Fläche zählt das Auftreten von Werten im Inneren von seiner zugehörigen Fläche für ein spezielles Histogrammintervall oder Kasten. Der entsprechende Kasten wird unter Verwendung von Texturkoordinaten bestimmt. Somit stellt nach einem einzigen Durchlauf von n/4 Texturabrufen pro Texel jede Fläche eine lokale Verteilung von Werten in ihrem Gebiet dar. Zum Erhalten einer globalen Verteilung von Werten innerhalb eines Gebiets werden alle Flächen in ein einziges globales Histogramm kombiniert. Flächen werden durch Anwenden eines Texturreduktionsvorgangs auf eine Weise ähnlich zu demjenigen, der in Jens Krüger und Rüdiger Westermann: Linear Algebra Operators for GPU Implementation of Numerical Algorithms ACM SIGGRAPH, 2003, beschrieben ist, dessen Offenbarung hier in dem Maß durch Bezugnahme eingeschlossen ist, in dem sie nicht inkompatibel zu der vorliegenden Erfindung ist, aufsummiert.

1 zeigt einen geeigneten Texturreduktionsvorgang, wobei die Pfeile die Richtung des Findens eines Werts eines speziellen Histogrammintervalls oder Kastens zeigen.

2 zeigt eine schematische Darstellung von Schritten eines geeigneten Texturreduktionsvorgangs von Textur 10 auf Textur 12. Das Auftreten eines Werts im Inneren einer Fläche wird gezählt und als eine eingekreiste Zahl in einem speziellen Texel von jeder Fläche gezeigt. Die Farben in den Kreisen identifizieren Texel, die zu einem gemeinsamen Wert des Histogrammintervalls gehören. Die Flächen werden zu einem globalen Histogramm durch Anwenden eines Texturreduktionsvorgangs aufsummiert. Beispielsweise in 2 wird der Zähler in dem oberen linken Texel von jeder Fläche über alle vier Flächen in der Gruppierung 10 aufsummiert, was 0 + 2 + 1 + 2 = 5 ergibt. Der Zähler von 5 wird dann in die obere linke Texel-Position der Fläche der nächsten Stufe 12 platziert, und so wird weiter für jeden der verbleibenden drei Texel von jeder verbleibenden Fläche vorgegangen. Im nächsten Schritt wird eine Fläche erzielt. Die Boxfarben in 2 sind nur zum Symbolisieren, dass die Texel verschiedene Werte haben.

Während jedes Renderdurchlaufs wird die Texturgröße in jeder Dimension halbiert. Der i-te Texel eines lokalen Histogramms wird mit dem i-ten Texel der drei Flächen angrenzend in einer positiven Texturkoordinatenrichtung aufsummiert. Auf diese Weise werden alle m × m Flächen eines Gebiets in ein abschließendes Histogramm nach log(m) Durchläufen kombiniert. Die Anzahl der kostenintensiven Bildlookups pro eingegebenem Wert wird somit minimiert.

Die Tabelle 1 zeigt anwendbare Definitionen für eine beispielhafte Ausführungsform in Einklang mit Prinzipien der vorliegenden Erfindung.

Unter Verwendung dieser Definitionen ergibt sich:

Die Intensität, die in einem Texel/Kanal gezählt wird, wird durch seine Texturkoordinaten (x, y) bestimmt: I = (floor(y/h)·h + floor(x/h))·bx

Zum Durchführen des Zählens wird jeder Texel in einer Fläche oder Abschnitt während jeder Fragmentprogrammausführung in Inneren des Abschnitts abgetastet. Die Position relativ zu dem Ursprung eines Abschnitts wird durch Texturkoordinaten bestimmt: Ox = floor (x/h)·h Oy = floor (y/h)·h

Nachdem die m × m Histogramme in einem Puffer der Größe s × s erzeugt sind, werden sie in eine einzige Histogrammtextur der Größe h × h aufsummiert. Wie oben angemerkt wird das Aufsummieren durch Durchführen eines so genannten Reduktionsvorgangs realisiert, wie es grafisch und schematisch in 1 und 2 gezeigt ist. Der Reduktionsvorgang wird auf eine flächenweise Art durchgeführt, vergleichbar zu dem texelweisen Reduktionsvorgang, der in der vorher erwähnten Veröffentlichung von Krüger und Westermann vorgestellt ist.

Bei einer beispielhaften Ausführungsform gemäß den Prinzipien der vorliegenden Erfindung wird die gesamte Berechnung auf der GPU durchgeführt, wobei entweder die DirectX oder OpenGL API's (Application Programming Interface) verwendet werden. Die Bilddaten und das Histogramm werden auf der GPU unter Verwendung von Texturen gespeichert. Die Berechnungen werden dann durchgeführt, indem ein Quadrat primitiv in die Ergebnistextur gerendert wird und die Berechnung in einem Fragmentprogramm durchgeführt wird. Der Fluss der Berechnung kann unter Verwendung unterschiedlicher Texturen als Eingabe/Ausgabe und durch Laden unterschiedlicher Fragmentprogramme kontrolliert werden.

Wie offensichtlich ist, ist die vorliegende Erfindung am besten unter Verwendung einer Anwendung einer Bildquellenausrüstung in Verbindung mit einem programmierten digitalen Computer zu implementieren. 3 zeigt in grundlegender schematischer Form einen Digitalprozessor, der zur Zweiwegedatenkommunikation mit einer Eingabeeinrichtung, einer Ausgabeeinrichtung, einer Grafikkarte und einer Speichereinrichtung zum Speichern eines Programms und anderen Daten verbunden ist. Die Eingabeeinrichtung ist weit ausgedrückt als eine Einrichtung zum Vorsehen eines geeigneten Bilds oder Bildern zum Verarbeiten gemäß der vorliegenden Erfindung gestaltet.

Beispielsweise kann die Eingabe direkt angewendet werden oder durch Speicherung aus einer Bildeinrichtung, wie z.B. einer Kamera, einer in einem CATSCAN beinhalteten Einrichtung, einer X-ray-Maschine, einem MRI oder einer anderen Einrichtung, oder als ein gespeichertes Bild oder durch Kommunikation mit anderen Computern oder Einrichtungen durch direkte Verbindung, einen modulierten Infrarotstrahl, Funk, Landleitung, Telefax oder Satellit, wie z.B. durch das World Wide Web oder Internet, oder jede andere geeignete Quelle solcher Daten.

Die Ausgabeeinrichtung kann eine computerartige Displayeinrichtung unter Verwendung von irgendeiner geeigneten Vorrichtung, wie z.B. einem Kathodenstrahl-Kineskoprohr, einem Plasmadisplay, einem Liquid Crystal Display usw. enthalten, oder sie kann eine Einrichtung zum Rendern eines Bild enthalten oder nicht und kann eine Speichereinrichtung oder einen Teil der Speichereinrichtung aus 3 zum Speichern eines Bilds zur weiteren Bearbeitung oder zur Betrachtung oder Untersuchung, wie es günstig ist, enthalten, oder sie kann eine Verbindung oder einen Anschluss verwenden, einschließlich solcher, wie sie oben in Verbindung mit der Eingabeeinrichtung erwähnt sind. Der Prozessor ist mit einem Programm betreibbar, das entsprechend der vorliegenden Erfindung festgesetzt ist zum Implementieren der Schritte der Erfindung. Ein solcher programmierter Computer kann unmittelbar durch Kommunikationsmedien, wie z.B. eine Landleitung, Funk, das Internet, usw. zur Bilddatenermittlung und -übertragung eine Schnittstelle haben.

Die Erfindung kann zumindest teilweise unmittelbar in einer Softwarespeichereinrichtung implementiert sein und in dieser Form als Softwareprodukt verpackt sein. Dies kann in der Gestalt eines Computerprogrammprodukts sein, das ein durch einen Computer verwendbares Medium enthält, das eine Computerprogrammlogik darauf aufgezeichnet hat, für einen Programmcode zum Durchführen des Verfahrens der vorliegenden Erfindung.

Die Erfindung wurde auch zum Teil durch Beispiele erklärt, wobei veranschaulichende beispielhafte Ausführungsformen verwendet werden. Es ist zu verstehen, dass die Beschreibung durch beispielhafte Ausführungsform nicht beschränkend sein soll, und dass, während die Erfindung in breitem Sinn anwendbar ist, es hilfreich ist, auch ihre Prinzipien ohne den Verlust der Generalität durch beispielhafte Ausführungsformen darzustellen. Es ist beispielsweise anzumerken, dass sich die Anwendung der vorliegenden Erfindung auch auf die Verarbeitung von Datensätzen ohne Bild erstreckt.

Es ist auch zu verstehen, dass verschiedene Änderungen und Ersetzungen, die hier nicht unbedingt explizit beschrieben sind, durch einen Fachmann, auf dessen Fachgebiet sie sich beziehen, durchgeführt werden können. Solche Veränderungen und Ersetzungen können vorgenommen werden, ohne vom Rahmen der Erfindung abzuweichen, wie er durch die folgenden Ansprüche definiert ist.


Anspruch[de]
Verfahren zur Histogrammberechnung unter Verwendung einer grafischen Verarbeitungseinheit (GPU), enthaltend:

Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet;

Unterteilen des Gebiets in unabhängige Gebiete oder Flächen;

paralleles Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche; und

paralleles Aufsummieren der Flächenhistogramme in der GPU, so dass ein abschließendes Bildhistogramm abgeleitet wird.
Verfahren zur Histogrammberechnung nach Anspruch 1, wobei der Schritt des Unterteilens des Gebiets das Unterteilen des Gebiets in gleichgroße und unabhängige Gebiete enthält. Verfahren zur Histogrammberechnung nach Anspruch 1 oder 2, wobei der Schritt des Berechnens einer Mehrzahl von Flächenhistogrammen enthält:

Zählen der Intensität in einem Texel, die durch Texeltexturkoordinaten, die Anzahl der Histogrammkästen und die Größe der Bilddaten bestimmt ist.
Verfahren zur Histogrammberechnung nach einem der Ansprüche 1 bis 3, wobei der Schritt des Berechnens einer Mehrzahl von Flächenhistogrammen enthält:

Bestimmen für jeden Texel einen entsprechenden Kasten unter Verwendung von Texturkoordinaten.
Verfahren zur Histogrammberechnung nach einem der Ansprüche 1 bis 4, wobei der Schritt des Berechnens einer Mehrzahl von Flächenhistogrammen enthält:

Zählen für jeden Texel das Auftreten von Werten im Inneren seiner zugehörigen Fläche für den entsprechenden Histogrammkasten.
Verfahren zur Histogrammberechnung nach Anspruch 4, wobei der Schritt des Bestimmens eines entsprechenden Kastens unter Verwendung von Texturkoordinaten für jeden Texel enthält:

Bestimmen des gleichen entsprechenden Kastens für jeden Texel, der die gleiche gegebene Position in seiner jeweiligen zugehörigen Fläche hat.
Verfahren zur Histogrammberechnung nach einem der Ansprüche 1 bis 6, wobei der Schritt des parallelen Aufsummierens enthält:

Anwenden eines flächenweisen Texturreduktionsvorgangs.
Verfahren zur Histogrammberechnung nach Anspruch 7, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Ausführen eines Renderdurchlaufs zum Halbieren der Texturgröße.
Verfahren zur Histogrammberechnung nach Anspruch 8, wobei der Schritt des Ausführens eines Renderdurchlaufs zum Halbieren der Texturgröße enthält:

Aufsummieren des i-ten Texels eines gegebenen Histogramms mit dem i-ten Texel der drei Flächen angrenzend in einer positiven Texturkoordinatenrichtung.
Verfahren zur Histogrammberechnung nach einem der Ansprüche 1 bis 9, wobei der Schritt des Speicherns von Bilddaten die Verwendung von zumindest einer aus RGB und RGBA Texturen enthält. Verfahren zur Histogrammberechnung nach einem der Ansprüche 1 bis 10, wobei der Schritt des Speicherns von Bilddaten das Verwenden von zumindest einer aus Leuchtkraft (c=1), RGB (c=3) oder RGBA (c=4) Textur enthält, so dass ein Histogramm von n-Kästen in einer quadratischen Flächengröße von sqrt(n/c) × sqrt(n/c) Texeln resultiert, wobei c die Anzahl von Kanälen pro Texel ist. Verfahren zur Histogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU), enthaltend:

Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet;

Unterteilen des Gebiets in unabhängige Gebiete oder Flächen durch Unterteilen des Gebiets in gleichmäßig große und unabhängige Flächen;

paralleles Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche, und Bestimmen für jeden Texel einen entsprechenden Kasten unter Verwendung von Texturkoordinaten durch Zählen des Auftretens von Werten im Inneren seiner zugehörigen Fläche für den entsprechenden Histogrammkasten für jeden Texel; und

paralleles Aufsummieren der Flächenhistogramme in der GPU, so dass ein abschließendes Bildhistogramm abgeleitet wird, durch Anwenden eines Texturreduktionsvorgangs durch Ausführen eines Renderdurchlaufs zum Halbieren der Texturgröße durch Summieren des i-ten Texels eines gegebenene Histogramms mit dem i-ten Texel der drei Flächen angrenzend in einer positiven Texturkoordinatenrichtung.
Verfahren zur Histogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU), enthaltend:

Speichern von eingegebenen Daten in einem zweidimensionalen (2D) Texturgebiet;

Unterteilen des Gebiets in gleichgroße Abschnitte;

paralleles Ableiten in der GPU eines Satzes von Histogrammen, einschließlich eines Histogramms für jeden der Abschnitte; und

Aufsummieren des Satzes von Histogrammen zum Ableiten eines abschließenden Histogramms.
Verfahren zur Histogrammberechnung nach Anspruch 13, wobei der Schritt des Ableitens eines Satzes von Histogrammen enthält:

Bestimmen eines entsprechenden Kastens für jeden Texel.
Verfahren zur Histogrammberechnung nach Anspruch 13, wobei der Schritt des Ableitens eines Satzes von Histogrammen enthält:

Bestimmen eines entsprechenden Kastens durch Verwendung von Texturkoordinaten für jeden Texel.
Verfahren zur Histogrammberechnung nach Anspruch 13, wobei der Schritt des Ableitens eines Satzes von Histogrammen enthält:

Anwenden eines Texturreduktionsvorgangs.
Verfahren zur Histogrammberechnung nach Anspruch 16, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Aufsummieren in jedem Texel einer zugehörigen Fläche aller Zähler innerhalb der zugehörigen Fläche, die dem entsprechenden Kasten entsprechen, der für jedes Texel bestimmt ist, so dass ein kombiniertes Histogramm erhalten wird.
Verfahren zur Histogrammberechnung nach Anspruch 16 oder 17, wobei der Schritt des Anwendens eins Texturreduktionsvorgangs enthält:

Wiederholen der Schritte des Texturreduktionsvorgangs, so dass ein abschließendes Histogramm erhalten wird.
Verfahren zur Histogrammberechnung nach einem der Ansprüche 16 bis 18, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Summieren in jedem Texel einer zugehörigen Fläche aller Zähler innerhalb der zugehörigen Fläche, die dem entsprechenden Kasten entsprechen, der für jedes Texel bestimmt ist;

und

Summieren des Satzes von Histogrammen zum Ableiten eines abschließenden Histogramms.
Verfahren zur Histogrammberechnung nach einem der Ansprüche 16 bis 19, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Ausführen eines Renderdurchlaufs zum Halbieren der Texturgröße.
Verfahren zur Histogrammberechnung nach Anspruch 20, wobei der Schritt des Ausführens eines Renderdurchlaufs zum Halbieren der Texturgröße enthält:

Summieren des i-ten Texels eines gegebenen Histogramms mit dem i-ten Texel der drei Flächen angrenzend in einer positiven Texturkoordinatenrichtung.
Verfahren zur Bildhistogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU), enthaltend:

Speichern von Bildeingangsdaten in einem zweidimensionalen (2D) Texturgebiet;

Unterteilen des Gebiets in gleichgroße Abschnitte;

paralleles Ableiten in der GPU eines Satzes von Bildhistogrammen, der ein Histogramm für jeden der Abschnitte enthält; und

Summieren des Satzes von Bildhistogrammen zum Ableiten eines abschließenden Histogramms.
Verfahren zur Bildhistogrammberechnung nach Anspruch 22, wobei der Schritt des Ableitens eines Satzes von Bildhistogrammen enthält:

Bestimmen eines entsprechenden Kastens für jeden Texel.
Verfahren zur Bildhistogrammberechnung nach Anspruch 22, wobei der Schritt des Ableitens eines Satzes von Bildhistogrammen enthält:

Bestimmen eines entsprechenden Kastens für jeden Texel unter Verwendung von Texturkoordinaten.
Verfahren zur Bildhistogrammberechnung nach einem der Ansprüche 22 bis 24, wobei der Schritt des Ableitens eines Satzes von Histogrammen enthält:

Anwenden eines Texturreduktionsvorgangs.
Verfahren zur Bildhistogrammberechnung nach Anspruch 25, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Ausführen eines Renderdurchlaufs zum Halbieren der Texturgröße.
Verfahren zur Bildhistogrammberechnung nach Anspruch 26, wobei der Schritt des Ausführens eines Renderdurchlaufs zum Halbieren der Texturgröße enthält:

Aufsummieren des i-ten Texels eines gegebenen Histogramms mit dem i-ten Texel der drei Flächen angrenzend in einer positiven Texturkoordinatenrichtung.
Verfahren zur Bildhistogrammberechnung nach einem der Ansprüche 25 bis 27, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Summieren in jedem Texel von einer zugehörigen Fläche aller Zähler innerhalb der zugehörigen Fläche, die dem entsprechenden Kasten entsprechen, der für jeden Texel bestimmt wird, so dass ein kombiniertes Bildhistogramm erhalten wird.
Verfahren zur Bildhistogrammberechnung nach einem der Ansprüche 25 bis 28, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Wiederholen von Schritten des Texturreduktionsvorgangs, so dass ein abschließendes Bildhistogramm erhalten wird.
Verfahren zur Bildhistogrammberechnung nach einem der Ansprüche 25 bis 29, wobei der Schritt des Anwendens eines Texturreduktionsvorgangs enthält:

Summieren in jedem Texel einer zugehörigen Fläche aller Zähler innerhalb der zugehörigen Fläche, die dem entsprechenden Kasten entsprechen, der für jedes Texel bestimmt ist;

und

Summieren des Satzes von Histogrammen zum Ableiten eines abschließenden Bildhistogramms.
System zur Histogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU), enthaltend:

Speichermittel zum Speichern eines Programms und anderer Daten; und

Prozessormittel in Verbindung mit der Speichereinrichtung, wobei der Prozessor mit dem Programm betreibbar ist zum Ausführen von:

Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet;

Unterteilen des Gebiets in unabhängige Gebiete oder Flächen;

paralleles Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche; und

paralleles Aufsummieren der Flächenhistogramme in der GPU zum Ableiten eines abschließenden Bildhistogramms.
System zur Histogrammberechnung nach Anspruch 31, wobei der Prozessor mit dem Programm betreibbar ist zum Ausführen von;

Unterteilen des Gebiets in gleichgroße und unabhängige Gebiete.
System zur Histogrammberechnung nach Anspruch 31 oder 32, wobei der Prozessor betreibbar ist mit dem Programm zum Ausführen von:

Zählen der Intensität in einem Texel, die durch Texeltexturkoordinaten, die Anzahl der Histogrammkästen und die Größe der Bilddaten bestimmt ist.
Computerprogrammprodukt, enthaltend ein durch einen Computer verwendbares Medium, das auf ihm eine Computerprogrammlogik aufgezeichnet hat für Programmcode zur Histogrammberechnung unter Verwendung einer Grafikverarbeitungseinheit (GPU), durch:

Speichern von Bilddaten in einem zweidimensionalen (2D) Texturgebiet;

Unterteilen des Gebiets in unabhängige Gebiete oder Flächen;

paralleles Berechnen einer Mehrzahl von Flächenhistogrammen in einer GPU, eines für jede Fläche; und

paralleles Aufsummieren der Flächenhistogramme in der GPU, so dass ein abschließendes Bildhistogramm abgeleitet wird.
Computerprogrammprodukt nach Anspruch 34, wobei:

der Schritt des Unterteilens des Gebiets das Unterteilen des Gebiets in gleichgroße und unabhängige Gebiete enthält.
Computerprogrammprodukt nach Anspruch 34 oder 35, wobei:

der Schritt des Berechnens einer Mehrzahl von Flächenhistogrammen enthält:

Zählen der Intensität in einem Texel, die durch Texeltexturkoordinaten, die Anzahl der Histogrammkästen und die Größe der Bilddaten bestimmt wird.






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