PatentDe  


Dokumentenidentifikation DE102005045812A1 16.05.2007
Titel Verfahren zur cache-optimierten Bearbeitung eines digitalen Bilddatensatzes
Anmelder Siemens AG, 80333 München, DE
Erfinder John, Matthias, Dr., 90429 Nürnberg, DE
DE-Anmeldedatum 27.09.2005
DE-Aktenzeichen 102005045812
Offenlegungstag 16.05.2007
Veröffentlichungstag im Patentblatt 16.05.2007
IPC-Hauptklasse G06T 1/60(2006.01)A, F, I, 20050927, B, H, DE
IPC-Nebenklasse G06F 17/10(2006.01)A, L, I, 20050927, B, H, DE   G06F 7/00(2006.01)A, L, I, 20050927, B, H, DE   
Zusammenfassung Für eine cache-optimierte Verarbeitung eines Bilddatensatzes (B) wird vorgeschlagen, im Rahmen eines Bildbearbeitungsalgorithmus zumindest auf einen Teil der Bildpunkte (bij) des Bilddatensatzes (B) nach Maßgabe ihrer Bildkoordinaten (i, j) in einer durch eine raumfüllende Kurve bestimmten Zugriffsreihenfolge (Z) zuzugreifen.

Beschreibung[de]

Die Erfindung bezieht sich auf ein Verfahren zur cache-optimierten Bearbeitung eines digitalen Bilddatensatzes, insbesondere zur Anwendung im Rahmen eines medizinischen Bildgebungssystems.

Im Zuge digitaler medizinischer Bildgebungsverfahren wie z.B. der Computertomographie sind umfangreiche digitale Bilddatensätze mit Mitteln der elektronischen Bildverarbeitung zu bearbeiten. Derartige Bearbeitungsschritte umfassen die Anwendung von Farb-, Kontrast- oder Glättungsfiltern, Koordinatentransformationen wie Translation, Rotation, Skalierung oder Spiegelung, etc.

Diese Bearbeitungsschritte werden üblicherweise mittels numerischer Algorithmen durchgeführt, die auf Computeranlagen mit einer herkömmlichen Mikroprozessorarchitektur implementiert sind. Angesichts der großen Datenmengen, die bei der Bearbeitung medizinischer Bilddatensätze üblicherweise zu handhaben sind, laufen diese Algorithmen auf herkömmlichen Computeranlagen oft vergleichsweise langsam ab, und nehmen hierdurch mitunter einen signifikanten Anteil der Gesamtlaufzeit bildgebender Anwendungen ein. Dies kann wiederum zu einer merklichen Beeinträchtigung der Arbeitsabläufe führen, im Zuge derer diese Anwendungen eingesetzt werden. Konkret kann beispielsweise die Effizienz der medizinischen Befundung eines digitalen Röntgenbilds oder CT-Bilddatensatzes erheblich darunter leiden, wenn bei jedem Bildbearbeitungsschritt des zu befundenden Bilddatensatzes infolge der Laufzeit eines oder mehrerer Bildverarbeitungsalgorithmen minutenlang auf den Neuaufbau des Bildes auf dem Bildschirm gewartet werden muss.

Moderne Computersysteme weisen in der Regel eine vergleichsweise schnelle arithmetische Datenverarbeitung, aber einen im Vergleich dazu nur langsamen Speicherzugriff auf. Der langsame Speicherzugriff wirkt hierdurch unter gegebenen Randbedingungen als "Flaschenhals", der die Ablaufgeschwindigkeit eines auf dem Computersystem ausgeführten Programms maßgeblich begrenzt. Diese Beschränkung betrifft in besonderem Maße Bildbearbeitungsalgorithmen, zumal bei diesen Prozessen mit der arithmetischen Rechenleistung ein besonders hoher Datendurchsatz und hierdurch wiederum ein vergleichsweise intensiver Speicherzugriff einhergeht.

Zur Beschleunigung der Arbeitsgeschwindigkeit weisen moderne Computersysteme in der Regel einen als "Cache" bezeichneten Zwischenspeicher, oder sogar eine Hierarchy solcher Caches auf. Ein Cache ist ein Speicher mit einem vergleichsweise kleinen Speicherumfang, der einen wesentlich schnelleren Datenzugriff erlaubt als der Hauptspeicher, und in den Daten, die für einen Programmablauf aktuell benötigt werden, für einen schnellen Zugriff temporär abgelegt werden können.

Gewöhnlich ist die Arbeitsteilung von Cache und Hauptspeicher für den Programmierer von Anwendungssoftware nicht direkt beeinflussbar. Vielmehr ist im Rahmen gängiger Softwareentwicklungsumgebungen nur eine standardisierte Zugriffsform auf den Speicherinhalt vorgesehen. Während der Ausführung einer Anwendungssoftware wird dementsprechend die Cacheverwaltung nicht direkt durch die Anwendungssoftware, sondern durch interne Strukturen des Computersystems vorgenommen. Ob Dateninhalt für eine Anwendungssoftware aus dem Cache oder direkt aus dem Hauptspeicher bezogen wird, hängt dabei von dem aktuellen Speicherinhalt des Caches ab. Auf Datenanforderung durch den Mikroprozessor wird zunächst überprüft, ob die angeforderten Daten im Cache vorliegen. Wenn nicht, wird üblicherweise ein diese Daten enthaltender Datenblock in den Cache geladen.

Eine Datenanfrage, die aus dem Cache bedient werden kann, wird als Cache-Treffer (Cache Hit) bezeichnet. Eine Datenanfrage, für die mangels entsprechender Daten im Cache auf den Hautspeicher zurückgegriffen werden muss, wird demgegenüber als Cache-Fehltreffer (Cache Miss) bezeichnet. Ein Cache-Fehltreffer beansprucht bei einem herkömmlichen Computersystem um bis zu einem Faktor 50 mehr Zeit als ein Cache-Treffer. Die Optimierung des Cache-Inhalts bei der Programmausführung, und damit die Verringerung der Anzahl der Cache-Fehltreffer birgt somit ein erhebliches Verbesserungspotential bei der Implementierung von Anwendungssoftware, insbesondere auf dem Gebiet der elektronischen Bildbearbeitung.

Eine besonders hohe Rate von Cache-Fehltreffern wird üblicherweise bei affinen Koordinatentransformationen von Bildern wie Drehungen, Spiegelungen, Translationen oder Skalierungen erzeugt, weshalb derartige Transformation vergleichsweise zeitintensiv sind.

Eine Optimierung der Cache-Leistung für Bildbearbeitungsprozesse wird bisher einerseits durch Entwicklung spezieller Hardwarekonfigurationen mit einer komplexen Cache-Architektur oder speziellen Cache-Zugriffsfunktionen versucht. Dies bedingt aber den Einsatz nicht-standardgemäßer Hardware, und hiermit wiederum zwangsläufig hohe Kosten.

Andererseits werden bisweilen spezielle Layouts für die Abspeicherung von Bilddaten vorgeschlagen, die von den gängigen Bilddatenformaten abweichen. Der Einsatz solcher Speicherlayouts bedingt aber nachteiligerweise vor dem eigentlichen Bearbeitungsschritt eine Umwandlung der zu bearbeitenden Bilddaten in das gewünschte Speicherlayout sowie eine Rückumwandlung des Bildes nach erfolgter Bearbeitung. Durch diese Umwandlungsschritte wird der durch ein spezielles Speicherlayout erzielbare Effizienzgewinn zumindest teilweise wieder kompensiert. Zudem hängt die Effizienz eines solchen Speicherlayouts stark von dem Algorithmus ab, mit welchem das Layout eingesetzt wird. Mit anderen Worten bedürfen verschiedene Algorithmen in der Regel verschiedener angepasster Speicherlayouts. Ein Einsatz angepasster Speicherlayouts erschwert somit die Kombinierbarkeit verschiedener Bildbearbeitungsalgorithmen.

Wiederum alternativ hierzu wird versucht, eine cache-optimierte Implementierung von Bildbearbeitungsalgorithmen zu erreichen, indem die Zugriffsreihenfolge des Algorithmus auf die Bilddaten durch Vertauschung von Bearbeitungsschleifen (Loops) oder blockorientierte Bearbeitung (loop blocking) geändert wird. In ersterem Fall werden je nach Bedarf innere und äußere Schleifen des Algorithmus vertauscht, was aber nur bei einer begrenzten Anzahl von Bildbearbeitungsalgorithmen überhaupt möglich ist. In letzterem Fall werden die Bilddaten des zu bearbeitenden Bilddatensatzes in Form von Koordinatenblöcken (und nicht wie üblich zeilenweise) eingelesen und bearbeitet. Blockorientierte Bearbeitung ist aber nur dann effektiv, wenn die Blockgröße an die Größe des Caches angepasst ist, und diese insbesondere nicht überschreitet. Dies ist in Hinblick auf die Kompatibilität von Anwendungssoftware nachteilig, zumal die Cachegröße von Computersystem zu Computersystem verschieden ist.

Der Erfindung liegt die Aufgabe zugrunde, ein effektives Verfahren zur Bearbeitung eines Bilddatensatzes anzugeben, das kompatibel und mit einfachen Mitteln einsetzbar ist. Das Verfahren soll insbesondere auf gängigen Computersystemen einen schnellen Ablauf von Bildbearbeitungsalgorithmen, insbesondere von affinen Koordinatentransformationen, sicherstellen.

Diese Aufgabe wird erfindungsgemäß gelöst durch die Merkmale des Anspruchs 1. Danach ist vorgesehen, im Zuge der Ausführung eines Bildbearbeitungsalgorithmus auf zumindest einen Teil der Bildpunkte eines zu bearbeitenden Bilddatensatzes hinsichtlich ihrer Bildkoordinaten in einer durch eine raumfüllende Kurve bestimmten Zugriffsreihenfolge zuzugreifen.

Als Bilddatensatz (nachfolgend kurz Bild) wird hierbei eine Datei verstanden, die ein Feld (Array) von Bildpunkten umfasst. Jedem Bildpunkt ist ein Farb- oder Helligkeitswert sowie ein n-dimensionaler (n = 2,3, ...) Satz von (Bild-)Koordinaten zugeordnet, der die Position eines jeden Bildpunktes bezüglich der anderen Bildpunkte kennzeichnet.

Als Speicherreihenfolge wird die Reihenfolge bezeichnet, in der die Bildpunkte des Bilddatensatzes originär in dem Hauptspeicher hinterlegt sind.

Als Bildbearbeitungsalgorithmus (oder kurz Algorithmus) ist eine Sequenz mathematischer Anweisungen zur Modifikation der Bildpunkte bezeichnet, insbesondere eine Koordinatentransformation wie z.B. eine Translation, Rotation, Skalierung oder Spiegelung. Die Bezeichnung Algorithmus wird insbesondere auch für einzelne Bestandteile eines übergeordneten Algorithmus verwendet.

Als Implementierung eines Algorithmus wird eine Formulierung eines Algorithmus in computergerechten Anweisungen, insbesondere in Form einer Programmiersprache, eines Flussdiagramms, etc. bezeichnet.

Der Begriff "raumfüllende Kurve" wird im Sinne der mathematischen Definition dieses Begriffes verwendet. Allgemein wird damit eine stetig zusammenhängende Kurve bezeichnet, die eine mathematische Abbildung eines eindimensionalen reellen Raumes auf einen mehrdimensionalen reellen Raum ermöglicht und dabei den mehrdimensionalen reellen Raum komplett überdeckt. Außerdem wird mit dem Begriff "raumfüllende Kurve" eine Diskretisierung dieser reellen Abbildung bezeichnet, die eine endliche Zahl aufeinanderfolgender Punkte (hier durch die Zugriffsreihenfolge gegeben) auf eine beliebig feine Diskretisierung eines mehrdimensionalen Quaders (hier durch das Bild oder Teilbild gegeben) abbildet, wobei jeder Punkt der Diskretisierung des Quaders (bzw. Bildes oder Teilbildes) einmal, zumindest aber mindestens einmal, durchlaufen wird. Derartige raumfüllende Kurven und deren Diskretisierungen sind an sich bekannt und beispielsweise in H.Sagan, "Space-Filling Curves", Springer Verlag, 1994 beschrieben.

Die Erfindung geht von der Erkenntnis aus, dass einerseits die Bildpunkte eines Bilddatensatzes in aller Regel in einer linearen Speicherreihenfolge, d.h. sukzessive nacheinander in Zeilenrichtung (x-Richtung), Zeile für Zeile, sowie (im Falle von 3D-Daten) xy-Ebene für xy-Ebene, etc., hinterlegt sind, und dass aufgrund dieser Speicherreihenfolge Bildpunkte, die in y- oder z-Richtung eng benachbart sind, im Hauptspeicher an vergleichsweise weit entfernten Positionen abgelegt sind.

Bilddaten werden weiterhin üblicherweise blockweise in der linearen Speicherreihenfolge in den Cache übernommen, was erkanntermaßen dazu führt, dass mit vergleichsweise hoher Wahrscheinlichkeit zwar die Zeilennachbarn eines angeforderten Bildpunktes im Cache vorhanden sind, nicht aber diejenigen Bildpunkte, die zu diesem Bildpunkt in y-Richtung oder z-Richtung benachbart sind. Erkanntermaßen führt dies wiederum dazu, dass herkömmlich implementierte Algorithmen dann eine besonders hohe Anzahl von Cache-Fehltreffern verursachen, wenn sie nicht in Zeilenrichtung, sondern entlang der Spalten (y-Richtung) oder gegebenenfalls Stapel (z-Richtung) des Bildes operieren. In diesem Fall muss nämlich die benötigte Information "stückchenweise" aus entfernten Positionen des Hauptspeichers zusammengesucht werden. Die Cache-Verwaltung eines herkömmlichen Computersystems erzeugt in diesem Fall erkanntermaßen größtenteils Blindleistung, d.h. füllt den Cache mit Bilddaten, die größtenteils nicht oder erst zu einem späteren Zeitpunkt von dem Algorithmus verarbeitet werden.

Mit der Erfindung wird, ausgehend von den vorstehend beschriebenen Erkenntnissen, die Zielrichtung verfolgt, Bildpunkte gebündelt nach Maßgabe ihres Nachbarschaftsverhältnisses im Koordinatensystem des Bildes einzulesen. Mit anderen Worten sollen Bildpunkte, die im Bild eng benachbart sind, auch hinsichtlich ihrer Position in der Zugriffsreihenfolge eng benachbart sein. Diese Eigenschaft der Zugriffsreihenfolge ist nachfolgend als Lokalitätskriterium bezeichnet. Unter Beachtung des Lokalitätskriteriums wird besonders häufig auf Bildpunkte zugriffen, deren Zeilennachbarn bereits kurz zuvor eingelesen wurden. Solche Bildpunkte befinden sich erkanntermaßen mit sehr hoher Wahrscheinlichkeit im Cache. Ein Algorithmus, dessen Zugriffsreihenfolge nach dem Lokalitätskriterium ausgerichtet ist, erzeugt deshalb nur wenige Cache-Fehltreffer und arbeitet hierdurch sehr effektiv. Erkanntermaßen wird nun durch den Zugriff auf die Bildpunkte entlang einer raumfüllenden Kurve das Lokalitätskriterium auf einfache Weise in hohem Maße erfüllt.

Das Verfahren ist dabei vorteilhaft bei allen Computersystemen einsetzbar, die über einen Cache verfügen und eine Cacheverwaltung aufweisen, die die im Hauptspeicher abgelegten Daten stets blockweise in sukzessiver Speicherreihenfolge in den Cache lädt. Diese Anforderung ist bei den meisten modernen Computersystemen erfüllt, so dass das Verfahren kompatibel auf standardgemäßen Computeranlagen einsetzbar ist. Insbesondere zumal raumfüllende Kurven in der Regel in Form rekursiver Konstruktionsregeln formuliert oder formulierbar sind, setzt die Anwendung des Verfahrens keine Kenntnis der Cachegröße voraus. Das Verfahren ist vielmehr flexibel und ohne das Erfordernis einer individuellen Anpassung mit Caches unterschiedlicher Größe oder einer Hierarchie mehrerer Caches einsetzbar.

Im Hinblick auf die Kompatibilität des Verfahrens ist schließlich vorteilhaft, dass das Verfahren nicht direkt die Cacheverwaltung beeinflusst, insbesondere keine speziellen Zugriffsmechanismen auf den Cache, benötigt. Vielmehr schafft das Verfahren lediglich günstige Rahmenbedingungen, unter denen bereits eine gewöhnliche Cacheverwaltung besonders effektiv arbeitet.

In einer Variante des Verfahrens ist vorgesehen, alle Bildpunkte des Bildes entlang einer einzigen raumfüllenden Kurve einzulesen. Insbesondere wenn das Bildformat des zu bearbeitenden Bildes mit der Struktur der raumfüllenden Kurve nicht übereinstimmt, hat es sich alternativ als besonders vorteilhaft erwiesen, das Bild zunächst in mehrere Teilbilder zu untergliedern, und auf die Bildpunkte mindestens eines dieser Teilbilder anschließend entlang einer raumfüllenden Kurve zuzugreifen. Die Bildpunkte der anderen Teilbilder werden entweder herkömmlich oder entlang einer eigenen raumfüllenden Kurve abgearbeitet. Diese Teilbilder können sich auch überlappen, d.h. gemeinsame Bildpunkte enthalten. Auf solche gemeinsamen Bildpunkte wird bevorzugt nur einmal zugegriffen. Bei jeder weiteren Zählung, d.h. jedem weiteren Vorkommen, in der Zugriffsreihenfolge werden diese Bildpunkte einfach übersprungen.

In einer bevorzugten Ausführung des Verfahrens erfolgt die Bestimmung der Zugriffsreihenfolge auf Basis einer selbstähnlichen raumfüllenden Kurve, zumal bei solchen Kurven das oben beschriebene Lokalitätskriterium besonders gut erfüllt ist. Als selbstähnlich wird eine Kurve bezeichnet, wenn sie auf verschiedenen Größenskalen eine stets ähnliche Struktur aufweist. Selbstähnliche raumfüllende Kurven, die als mathematisches Phänomen an sich bekannt sind, werden in der Regel rekursiv durch Aneinanderreihung einer Wiederholsequenz in identischer, gedrehter oder gespiegelter Form generiert und lassen sich auf diese Weise beliebig in alle Richtungen des von den Bildpunkten eingenommenen Koordinatensystems erweitern. Als selbstähnliche raumfüllende Kurven werden insbesondere die sogenannte Hilbert-Kurve oder die sogenannte Peano-Kurve für das Verfahren herangezogen.

Das Verfahren ist besonders vorteilhaft einsetzbar auf eine affine Transformation von Bilddaten, d.h. eine Translation, Drehung, Spiegelung, Skalierung (d.h. Vergrößerung oder Verkleinerung) oder Scherung der Bilddaten oder eine beliebige Linearkombination der vorstehend genannte Transformationsarten.

Gegenstand der Erfindung ist gemäß Anspruch 7 ferner ein Computerprogrammprodukt, insbesondere als Bestandteil der Anwendungssoftware einer medizinischen Bildgebungsanlage, das zur Durchführung des vorstehend beschriebenen Verfahrens ausgebildet ist.

Nachfolgend werden Ausführungsbeispiele der Erfindung anhand einer Zeichnung näher erläutert. Darin zeigen:

1 bis 4 eine anhand der Hilbert-Kurve in ihrer ersten bis vierten Rekursionsstufe bestimmte Zugriffsreihenfolge zum Einlesen eines Bilddatensatzes mit 2 × 2, 4 × 4, 8 × 8 bzw. 16 × 16 Bildpunkten, und

5 bis 7 eine anhand der Peano-Kurve in ihrer ersten bis dritten Rekursionsstufe bestimmte Zugriffsreihenfolge zum Einlesen eines Bilddatensatzes mit 3 × 3, 9 × 9 bzw. 27 × 27 Bildpunkten,

8 eine Zugriffsreihenfolge zum Einlesen eines 17 × 17 Bildpunkte umfassenden Bilddatensatzes in zwei Teilbildern, wobei die Zugriffsreihenfolge bezüglich des ersten Teilbilds anhand der Hilbert-Kurve bestimmt ist, und

9 eine Zugriffsreihenfolge zum Einlesen eines 19 × 16 Bildpunkte umfassenden Bilddatensatzes in fünf Teilbildern, wobei die Zugriffsreihenfolge bezüglich aller fünf Teilbilder anhand der Hilbert-Kurve bestimmt ist.

Einander entsprechende Größen sind in den Figuren mit gleichen Bezugszeichen versehen.

Die 1 bis 9 zeigen in schematischer Darstellung jeweils einen zweidimensionalen Bilddatensatz (oder kurz Bild B). Das Bild B umfasst allgemein eine Anzahl von N × M (N,M = 2,3, ...) Bildpunkten bij. Jeder Bildpunkt bij enthält einen Farb- oder Helligkeitswert. Jedem Bildpunkt bij ist weiterhin ein Set von Koordinaten i (i = 1,2, ..., N) und j (j = 1,2, ..., M) zugeordnet, die die Stellung eines jeden Bildpunktes bij im Bild B kennzeichnen. Die Bildpunkte bij sind in Form einer orthogonalen Matrix im Bild B angeordnet. Die Koordinate i unterscheidet als Zeilenindex Bildpunkte bij innerhalb einer Spalte j. Die Koordinate j unterscheidet als Spaltenindex Bildpunkte bij innerhalb eine Zeile i.

In den 1 bis 7 ist in Form einer die Bildpunkte bij verbindenden Linie weiterhin eine Zugriffsreihenfolge Z dargestellt, mittels welcher im Zuge des erfindungsgemäßen Verfahrens ein Bildbearbeitungsalgorithmus auf die Bildpunkte bij zugreift.

Die 3 und 4 sowie 7 sind aus Gründen der besseren Übersichtlichkeit vereinfacht dargestellt, indem dort die Bildpunkte bij lediglich durch die Ecken sowie den Anfangs- und Endpunkt der Zugriffsreihenfolge Z angedeutet sind.

In den 1 bis 4 ist die Zugriffsreihenfolge Z durch die sogenannte Hilbert-Kurve bestimmt, die im Verlauf der 1 bis 4, angepasst an eine unterschiedliche Größe des jeweiligen Bildes B, in aufeinanderfolgenden Rekursionsstufen dargestellt ist. 1 zeigt die Grundform der Hilbert-Kurve (auch als Generator bezeichnet). Aus der Darstellung ist erkennbar, dass die Grundform der Hilbert-Kurve vier in einer 2 × 2-Matrix angeordnete Felder (oder Quadranten) umfasst, die in einer U-förmigen Fortschrittsrichtung abgearbeitet werden. In der ersten Rekursionsstufe gemäß 1 beinhaltet jedes Feld nur einen einzigen Bildpunkt bij, so dass dortige 2 × 2 Bildpunkte bij fassende Bild B in der Zugriffsreihenfolge Z = b11, b21, b22, b12 abgearbeitet wird.

Wie die Abfolge der 1 bis 4 zeigt, ist die durch die Hilbert-Kurve bestimmte Zugriffsreihenfolge Z beliebig rekursiv erweiterbar. Zum Übergang von einer Ausgangsstufe in die nächsthöhere Rekursionsstufe wird der von den abzutastenden Bildpunkten bij aufgespannte Koordinatenraum in Richtung beider Koordinaten i und j verdoppelt, wobei die Ausgangsstufe als erster Quadrant des vergrößerten Koordinatenraums übernommen wird. Für die übrigen Quadranten wird die Ausgangsstufe in gedrehter oder gespiegelter Form ergänzt, so dass die solchermaßen erweiterte Zugriffreihenfolge Z alle Bildpunkte bij des vergrößerten Koordinatenraums stetig und genau einmal durchläuft, und so dass die Zugriffsreihenfolge Z die Quadranten des vergrößerten Koordinatenraums wiederum entlang einer U-förmigen (zu der Grundform der Hilbert-Kurve selbstähnlichen) Fortschrittsrichtung nacheinander abarbeitet.

In der zweiten Rekursionsstufe gemäß 2 erfasst die durch die Hilbert-Kurve bestimmte Zugriffsreihenfolge Z 4 × 4 Bildpunkte bij, in der dritten (3) und vierten (4) Rekursionsstufe 8 × 8 bzw. 16 × 16 Bildpunkte bij.

Die 5 bis 7 zeigen in unterschiedlichen Rekursionsstufen eine auf der sogenannten Peano-Kurve basierenden Zugriffsreihenfolge Z. Bei der Peano-Kurve handelt es sich wie bei der Hilbert-Kurve um eine selbstähnliche, raumfüllende Kurve, die analog zu der vorstehend beschriebenen Vorgehensweise rekursiv beliebig erweiterbar ist.

5 zeigt wiederum die Grundform (oder den Generator) der Peano-Kurve, die neun in einer 3 × 3-Matrix angeordnete Felder umfasst, die entlang einer S-förmigen Fortschrittsrichtung abgearbeitet werden.

Sowohl die Hilbert-Kurve als auch die Peano-Kurve sind ohne Verlust ihrer mathematischen Eigenschaften auf höherdimensionale Koordinatenräume ausdehnbar. Die höherdimensionalen Varianten der Hilbert- bzw. Peano-Kurve werden bei Bedarf zur Bestimmung einer Zugriffsreihenfolge für Bilddaten von N-dimensionalen Bildern (N = 3, 4, ...) eingesetzt.

Die vorstehend beschriebene Verfahrensvariante, bei der alle Bildpunkte bij des Bildes B entlang einer einzigen raumfüllenden Kurve eingelesen werden, ist insbesondere dann vorteilhaft einsetzbar, wenn das Bild B nicht zu groß ist und hinsichtlich seines Bildformats mit der Struktur der zugrundegelegten raumfüllenden Kurve übereinstimmt. Als Struktur der raumfüllenden Kurve wird hierbei die Form des von der raumfüllenden Kurve in ihrer k-ten (k = 1,2, ...) Rekursionsstufe erfassten Punktmusters bezeichnet. Die Hilbert-Kurve hat demnach, wie den 1 bis 4 zu entnehmen ist, eine Struktur von 2k × 2k Bildpunkten bij, die Peano-Kurve, wie den 5 bis 7 zu entnehmen ist, eine Struktur von 3k × 3k Bildpunkten bij.

Umfasst das Bild B dagegen sehr viele Bildpunkte bij oder entspricht das Bildformat nicht der Struktur der Hilbert-Kurve oder der Peano-Kurve, so wird das Bild B zunächst in eine Anzahl von Teilbildern Tj (j = 2,3,4, ...) gegliedert, von denen mindestens eines entlang der Hilbert-Kurve oder Peano-Kurve eingelesen wird.

8 zeigt beispielhaft eine solchermaßen entwickelte Zugriffsreihenfolge Z zum Einlesen eines Bilds B mit 17 × 17 Bildpunkten bij. Das Bild B ist in ein erstes Teilbild T1 und ein zweites Teilbild T2 gegliedert. Das Teilbild T1 umfasst dabei die Bildpunkte b11 bis b16,16 und ist somit insbesondere derart gewählt, dass es der Struktur der Hilbert-Kurve in ihrer vierten Rekursionsstufe entspricht. Das Teilbild T2 umfasst die restlichen Bildpunkte b1,17 bis b17,17 sowie b17,16 bis b17,1. Die Zugriffsreihenfolge Z enthält die Bildpunkte bij des ersten Teilbilds T1 entsprechend in der durch 4 vorgegebenen Reihenfolge. Die Bildpunkte bij des zweiten Teilbildes T2 werden anschließend linear in Spalten- bzw. Zeilenrichtung eingelesen.

9 zeigt beispielhaft eine Zugriffsreihenfolge Z zum Einlesen eines Bildes B mit 19 × 16 Bildpunkten bij. Das Bild B ist hierbei in jeweils quadratische Teilbilder T1 bis T5 gegliedert, von denen das Teilbild T1 wiederum die Bildpunkte b11 bis b16,16 umfasst. Der verbleibende rechte Rand des Bildes B wird durch die Teilbilder T2 bis T5 abgedeckt, wobei jedes dieser Teilbilder T2 bis T5 mit dem Teilbild T1 in einer Bildpunktspalte überlappt. Innerhalb jedes der Teilbilder T1 bis T5 wird auf die jeweils darin enthaltenen Bildpunkte bij entlang einer Hilbert-Kurve entsprechender Rekursionsstufe zugegriffen. Auf die in der Zugriffsreihenfolge Z doppelt enthaltenen Bildpunkte bij der 16. Bildspalte wird nur bei der Abarbeitung des ersten Teilbilds T1 zugegriffen. Bei der Abarbeitung der Teilbilder T2 bis T5 werden diese Bildpunkte bij übersprungen.

Prinzipiell ist auch denkbar, in verschiedenen Teilbildern die Zugriffsreihenfolge Z anhand unterschiedlicher raumfüllender Kurven zu bestimmen.

Um Laufzeit für die Berechnung der Zugriffsreihenfolge einzusparen, sind im Rahmen eines nach dem erfindungsgemäßen Verfahren implementierten Computerprogramms die Hilbert-Kurve und/oder die Peano-Kurve vorzugsweise in einer oder mehreren Rekursionsstufen als Koordinatenfolgen vorgegeben.

Alternativ kann die Zugriffsfolge auch während der Laufzeit durch ein rekursives Konstruktionsverfahren für die Hilbert-Kurve bzw. die Peano-Kurve berechnet werden. Für die Hilbert-Kurve ist ein geeignetes rekursives Konstruktionsverfahren beispielsweise aus G. Breinhold, Ch. Schierz, "Algorithm 781: generating Hilbert's space-filling curve by recursion", ACM Trans. of Math. Software (TOMS), 24(2), 1998, S. 184-189 bekannt.

Experimenteller Vergleich:

Das erfindungsgemäße Verfahren wurde anhand eines vereinfachten Testprogramms getestet, welches im Rahmen eines Algorithmus für eine Bildrotation um 90° bzw. um 45° den zu verarbeitenden Bilddatensatz in jeweils 64 × 64 Bildpunkte umfassende Teilbilder gliedert und auf die Bildpunkte eines jeden Teilbildes in der durch die Hilbert-Kurve (6. Rekursionsstufe) vorgegebenen Reihenfolge zugreift.

Das Testprogramm (nachfolgend kurz mit "Hilbert" bezeichnet) wurde zum einen mit einem ersten Vergleichsprogramm (nachfolgend kurz als "Standard" bezeichnet) verglichen, bei welchem der Rotationsalgorithmus herkömmlich implementiert ist, indem auf die Bildpunkte des Bildes zeilenweise zugegriffen wird.

Das Testprogramm wurde zum anderen mit einem zweiten Vergleichsprogramm verglichen, welches bei der Ausführung des Rotationsalgorithmus in Form rechteckiger Blöcke, innerhalb jedes Blockes aber wiederum zeilenweise auf die Bildpunkte zugreift. Dieses Vergleichsprogramm wurde mit einer auf das verwendete Computersystem optimierten Blockgröße von 16 × 16 (nachfolgend "Block 16") sowie 32 × 32 (nachfolgend "Block 32") Bildpunkten getestet.

Das Testprogramm sowie beide Vergleichsprogramme wurden auf einem Computersystem mit einer Mikroprozessorarchitektur des Typs Intel Pentium 4 CPU, 2GHz mit 1GB RAM, 8KB L1 Cache und 512 KB L2 Cache getestet.

Das Testprogramm sowie beide Vergleichsprogramme wurden in C++ kodiert und mit dem GNU C++-Compiler (g++) in der Optimierungsstufe -O compiliert.

Die Algorithmen wurden an 2D-Bildern verschiedener Größe (1024 × 1024, 2048 × 2048, ...) getestet.

In TAB 1 sind die Ergebnisse der Testreihen aufgeführt. Aus der Tabelle geht hervor, dass der erfindungsgemäß implementierte Rotationsalgorithmus (Hilbert) für beide Drehungen sowohl gegenüber dem zeilenorientierten Rotationsalgorithmus (Standard) als auch gegenüber dem blockorientierten Rotationsalgorithmus (Block 16/Block 32) einen signifikanten Laufzeitvorteil aufweist, der sich mit zunehmender Bildgröße zunehmend ausprägt.

  • TAB 1: Laufzeitvergleich eines erfindungsgemäß implementierten Rotationsalgorithmus (Hilbert) mit Vergleichsprogrammen (Standard, Block 16, Block 32) an 2D-Bildern unterschiedlicher Bildgröße (1024 × 1024, ...) für eine 90°-Drehung sowie eine 45°-Drehung

Bei dem Vergleich des erfindungsgemäß implementierten Rotationsalgorithmus mit dem blockorientierten Rotationsalgorithmus ist zu berücksichtigen, dass die vergleichsweise gute Performance des letzteren nur durch vorausgehende Optimierung der Blockgröße an das verwendete Computersystem erreicht wurde, während der erfindungsgemäße Rotationsalgorithmus keiner individuellen Anpassung an das Computersystem bedarf.


Anspruch[de]
Verfahren zur cache-optimierten Verarbeitung eines Bilddatensatzes (B), bei welchem im Rahmen eines Bildbearbeitungsalgorithmus zumindest auf einen Teil der Bildpunkte (bij) des Bilddatensatzes (B) nach Maßgabe ihrer Bildkoordinaten (i, j) in einer durch eine raumfüllende Kurve bestimmten Zugriffsreihenfolge (Z) zugegriffen wird. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der Bildbearbeitungsalgorithmus eine affine Bildtransformation ist. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass der Bildbearbeitungsalgorithmus eine Drehung oder Spiegelung ist. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass die Zugriffsreihenfolge (Z) durch die Hilbert-Kurve oder die Peano-Kurve bestimmt wird. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass der Bilddatensatz (B) in mehrere Teilbilder (Tj) gegliedert wird, wobei auf die Bildpunkte (bij) mindestens eines Teilbilds (Tj) nach Maßgabe ihrer Bildkoordinaten (i, j) in einer durch eine raumfüllende Kurve bestimmten Zugriffsreihenfolge (Z) zugegriffen wird. Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass mindestens zwei Teilbilder (Tj) einander überlappen, wobei mehrfach in der Zugriffsreihenfolge (Z) enthaltene Bildpunkte (bij) bei der zweiten und jeder weiteren Zählung in der Zugriffsreihenfolge (Z) übersprungen werden. Computerprogrammprodukt, umfassend eine Implementierung eines Bildbearbeitungsalgorithmus, die zur Durchführung des Verfahrens nach einem der Ansprüche 1 bis 6 ausgebildet ist.






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