PatentDe  


Dokumentenidentifikation DE60217748T2 31.10.2007
EP-Veröffentlichungsnummer 0001246124
Titel Verfahren und Gerät zur Anzeige eines Bildraumes
Anmelder Ricoh Co., Ltd., Tokyo, JP
Erfinder Iwasaki, Masajiro, Yokohama-shi, Kanagawa, JP
Vertreter Schwabe, Sandmair, Marx, 81677 München
DE-Aktenzeichen 60217748
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 18.03.2002
EP-Aktenzeichen 022519342
EP-Offenlegungsdatum 02.10.2002
EP date of grant 24.01.2007
Veröffentlichungstag im Patentblatt 31.10.2007
IPC-Hauptklasse G06K 9/62(2006.01)A, F, I, 20051017, B, H, EP
IPC-Nebenklasse G06T 11/20(2006.01)A, L, I, 20051017, B, H, EP   G06F 17/30(2006.01)A, L, I, 20051017, B, H, EP   

Beschreibung[de]

Die vorliegende Erfindung bezieht sich im Allgemeinen auf ein Verfahren zum Anzeigen eines Bildraums und insbesondere auf ein Bildraum-Anzeigeverfahren und eine Bildraum-Anzeigevorrichtung zum räumlichen Anzeigen von Merkmalen eines Bildes.

Hinsichtlich eines solchen Verfahrens zum Anzeigen eines Bildraums gibt es die folgenden Verfahren:

  • 1) "A User Interface Visualizing feature Space for Content-Based Image Retrieval", Technical Report of IEICE, IE98-204; und
  • 2) "Visual Interaction for Exploration in Information Space of Documents", Journal of JSSST, Band 13.

Das vorstehend erwähnte bekannte Verfahren 1) ist ein Verfahren zur Abbildung von Bildmerkmalen auf einem Anzeigeraum in 2 Dimensionen durch Verringern der Anzahl von Dimensionen eines mehrdimensionalen Raums gemäß der Hauptkomponentenanalyse. Das vorstehend erwähnte bekannte Verfahren 2) führt eine Idee der dynamischen Aktualisierung von visualisierten Ergebnissen in einem visuellen Klassifizierungsverfahren ein, wobei die Aktualisierung in Reaktion auf eine Benutzeroperation durchgeführt wird und die visuelle Klassifizierung durch Anordnen einer großen Anzahl von Dokumenten und Schlüsselwörtern auf der Basis ihrer gegenseitigen Beziehungen gegeben wird.

Das bekannte Verfahren 1) hat jedoch insofern ein Problem, als die Hauptkomponentenanalyse nicht ausgeführt werden kann, wenn Bildmerkmale nicht durch Vektordaten dargestellt werden können oder wenn eine Bildähnlichkeit zwischen Bildern nicht durch eine lineare Funktion dargestellt werden kann. Das bekannte Verfahren 2) hat insofern einen Nachteil, als die Anzahl von Schlüsselwörtern auf Grund einer großen Menge an Berechnung groß wird, was eine Verarbeitungszeit lang macht, wodurch es für eine interaktive Darstellung ungeeignet gemacht wird.

Wenn andererseits mehrere Merkmale aus einem Bild extrahiert werden, um dessen Merkmalsraum in 3 Dimensionen oder einem 3-dimensionalen Anzeigeraum anzuzeigen, kann ein Benutzer den Merkmalsraum leicht erfassen, wenn die Merkmale den jeweiligen Dimensionsachsen zugewiesen werden, um jeder Dimensionsachse Sinn zu geben.

US 6 121 969 offenbart eine auf Ähnlichkeit basierende Datenbank von Bildern, in der die Bilder entsprechend einer biologischen unbewussten Ähnlichkeit geordnet und korreliert sind.

Der Artikel "Applications of Quadtree, Octree and Binary Tree Decomposition Techniques to Shape Analysis and Pattern Recognition" von BB Chaudhuri, IEEE Transactions on Pattern Analysis and Machine Intelligence, Band PAMI-7 Nr. 6, Dezember 1985, S. 652–661, beschreibt, dass eine n-dimensionale Binärbaumzerlegung des Merkmalsraums für eine effiziente Musterklassifiziererkonstruktion verwendet werden kann.

Es ist eine allgemeine Aufgabe der vorliegenden Erfindung, ein verbessertes und nützliches Bildraum-Anzeigeverfahren und eine verbesserte und nützliche Bildraum-Anzeigevorrichtung zu schaffen, bei denen die vorstehend erwähnten Probleme beseitigt sind.

Eine speziellere Aufgabe der vorliegenden Erfindung besteht darin, ein Bildraum-Anzeigeverfahren und eine Bildraum-Anzeigevorrichtung zu schaffen, die einem Benutzer erleichtern, einen Merkmalsraum zu erfassen, indem jedes Merkmal einer jeweiligen von Dimensionsachsen eines Anzeigeraums zugewiesen wird.

Um die vorstehend erwähnten Aufgaben zu erreichen, werden gemäß der vorliegenden Erfindung ein Bildraum-Anzeigeverfahren und eine Bildraum-Anzeigevorrichtung, wie in den beigefügten Ansprüchen definiert, geschaffen.

Gemäß der vorliegenden Erfindung wird, wenn mehrere Merkmale verwendet werden, die Baumstruktur für jedes der Merkmale erzeugt und jede Baumstruktur wird in einer Dimension hinsichtlich Dimensionsdaten entsprechend der Anzahl der Merkmale abgebildet. Die Dimensionsdaten werden als Anzeige-Koordinatenachsendaten verwendet, um die Merkmale in den Dimensionen des Anzeigeraums abzubilden. Folglich ermöglicht der durch das Verfahren der vorliegenden Erfindung angezeigte Bildraum einem Benutzer, den Merkmalsraum leicht zu erfassen.

In dem Bildraum-Anzeigeverfahren gemäß der vorliegenden Erfindung kann das Unterteilen des Anzeigeraums den Schritt umfassen: Erhalten von Abständen zwischen jedem Punkt der Merkmale und Mittelpunkten von zwei Anhäufungen in Bezug auf jeden Punkt; Sortieren aller Punkte gemäß einer Differenz zwischen den erhaltenen Abständen; und Unterteilen des Anzeigeraums in zwei Anhäufungen durch Festlegen einer Grenze der Anhäufungen gemäß einer Sortierreihenfolge.

Die Grenze der Anhäufungen kann zwischen Punkten festgelegt werden, von welchen eine Differenz von Abständen, die Punkten vorangehen und nachfolgen, in der Sortierreihenfolge am größten ist. Ein Bereich, der einer der Dimensionen des Anzeigeraums entspricht, kann gemäß den Abständen zu Mittelpunkten der zwei Anhäufungen und einem Verhältnis von Differenzen der Differenzabstände an der Grenze der Anhäufungen unterteilt werden. Die Grenze der Anhäufungen kann einem Punkt in der Mitte in der Sortierreihenfolge entsprechen. Die Merkmale können dreidimensionale Daten sein, die der Form, Textur und Farbe der Bilder entsprechen, und die Merkmale werden unter Verwendung der dreidimensionalen Daten als Anzeige-Koordinatenachsendaten angezeigt.

Weitere Aufgaben, Merkmale und Vorteile der vorliegenden Erfindung werden aus der folgenden ausführlichen Beschreibung besser ersichtlich, wenn sie in Verbindung mit den begleitenden Zeichnungen gelesen wird.

1 ist ein Blockdiagramm einer Bildanzeigevorrichtung gemäß einer ersten Ausführungsform der vorliegenden Erfindung;

2 ist ein Blockdiagramm eines Teils der Bildanzeigevorrichtung, die einen Bildanzeigeprozess durchführt;

3 ist eine Darstellung einer Baumstruktur, die vom Bildanzeigeprozess erzeugt wird;

4 ist eine Darstellung einer 1-dimensionalen Abbildung der in 3 gezeigten Baumstruktur;

5 ist eine Darstellung, die eine Beziehung zwischen dem 3-dimensionalen Anzeigeraum und Merkmalen (Form, Textur, Farbe), die von einem Bild extrahiert werden, zeigt;

6 ist ein Ablaufplan eines Merkmalsachsen-Anzeigeraum-Erzeugungsprozesses gemäß der ersten Ausführungsform der vorliegenden Erfindung;

7 ist ein Ablaufplan eines Anzeigeraum-Erzeugungsprozesses I gemäß der ersten Ausführungsform der vorliegenden Erfindung;

8 ist ein Ablaufplan eines Binärbaum-Erzeugungsprozesses gemäß der ersten Ausführungsform der vorliegenden Erfindung;

9 ist ein Ablaufplan eines Anzeigeraum-Erzeugungsprozesses II gemäß der ersten Ausführungsform der vorliegenden Erfindung; und

10 ist ein Ablaufplan eines Anhäufungsprozesses gemäß der ersten Ausführungsform der vorliegenden Erfindung.

ERSTE AUSFÜHRUNGSFORM

Nun wird eine Beschreibung einer ersten Ausführungsform der vorliegenden Erfindung gegeben. 1 ist ein Blockdiagramm einer Bildanzeigevorrichtung gemäß einer ersten Ausführungsform der vorliegenden Erfindung. 2 ist ein Blockdiagramm eines Teils der Bildanzeigevorrichtung, die einen Bildanzeigeprozess durchführt.

In 1 umfasst die Bildanzeigevorrichtung: eine Zentraleinheit (CPU) 1, die einen gesamten Betrieb der Bildanzeigevorrichtung steuert; einen Festwertspeicher (ROM) 2, der Programme speichert, die von der CPU 1 ausgeführt werden; einen Direktzugriffsspeicher (RAM), der dynamische Daten zur Ausführung der im ROM 2 gespeicherten Programme speichert und als Arbeitsbereich dient, wenn die Programme ausgeführt werden; eine Tastatur 4 und eine Maus 5 als Eingabevorrichtungen; einen Monitor 6 als Anzeigevorrichtung; eine Bildanzeigeeinheit 8, die eine Bildanwendung 7 ausführt; eine periphere Schnittstelle (I/F) 9, die als Schnittstelle mit einer Peripherievorrichtung 1 wie z. B. einer Digitalkamera oder einem Scanner fungiert; und eine Netz-I/F 10, die als Schnittstelle mit einem Netz 12 fungiert. Diese Komponenten sind über einen Bus 13 miteinander verbunden, so dass sie durch die CPU 1 so gesteuert werden können, dass diese Komponenten zusammen als Computer dienen, um verschiedene Funktionen der vorliegenden Erfindung auszuführen.

Außerdem ist eine Speichermedien-Ansteuereinheit 15 wie z. B. eine CD-ROM-Ansteuereinheit mit dem Bus 13 verbunden. Die Speichermedien-Ansteuereinheit 15 liest Programmcodes von einem Speichermedium wie z. B. einem CD-ROM, um die im Speichermedium gespeicherten Programmcodes auf den Computer zu laden, so dass der Computer verschiedene später erwähnte Funktionen der vorliegenden Erfindung ausführt.

Der Bildanzeigeteil 8 umfasst, wie in 2 gezeigt, eine Merkmalsextraktionseinheit 81, eine Anhäufungseinheit 82, eine Baumstruktur-Erzeugungseinheit 83, eine Anzeigeraum-Erzeugungseinheit 84 und eine Anzeigebildschirm-Erzeugungseinheit 85. Die Einheiten 8185 führen einen Merkmalsextraktionsprozess, einen Anhäufungsprozess, einen Baumstruktur-Erzeugungsprozess, einen Anzeigeraum-Erzeugungsprozess bzw. einen Anzeigebildschirm-Erzeugungsprozess gemäß der Bildanwendung 7 durch.

Nun wird eine Beschreibung von Prozessen gegeben, die vom Bildanzeigeteil 8 mit der vorstehend erwähnten Struktur durchgeführt werden. Die Prozesse umfassen 1) einen Merkmalsextraktionsprozess, 2) einen Merkmalsraum-Baumstruktur-Extraktionsprozess und 3) einen Bildanzeigebildschirm-Erzeugungsprozess.

1) Merkmalsextraktionsprozess:

Als Merkmal eines Bildes gibt es verschiedene Merkmale, wie z. B. ein Histogrammmerkmal, ein Kantenmerkmal oder ein Texturmerkmal.

Die vorliegende Erfindung ist auf beliebige Merkmale anwendbar. Die vorliegende Anmeldung ist natürlich auf Merkmale anwendbar, die aus anderen Daten als Bilddaten extrahiert werden. Die vorliegende Erfindung ist beispielsweise auf Merkmale anwendbar, die aus Textdaten extrahiert werden. Hier wird eine Beschreibung eines Extraktionsprozesses eines allgemeinen Histogrammmerkmals gegeben. Als Bilddaten, aus denen Merkmale extrahiert werden, liegen Bilddaten vor, die von den peripheren Vorrichtungen 11 wie z. B. einer Digitalkamera oder einem Scanner geliefert werden, oder Bilddaten, die vom Web heruntergeladen werden. Es besteht keine Begrenzung in Bezug auf das Eingabeverfahren.

Zuerst wird ein geeigneter Farbraum (beispielsweise Lab, Luv, HSV usw.) ausgewählt und der ausgewählte Farbraum wird in mehrere Bereiche unterteilt. Dann wird eine Untersuchung hinsichtlich dessen durchgeführt, welches Pixel des Bildes welchem Bereich des Farbraums entspricht. Nach dem Zählen der Anzahl von Pixeln für jeden Bereich wird werden die Pixelanzahldaten auf der Basis der Anzahl von ganzen Pixeln normiert. Die normierten Daten der Anzahl von Pixeln für jeden Bereich entspricht dem Histogrammmerkmal. Das Merkmal eines Histogramms dient als Punkt des Merkmalsraums des Histogramms. Als Abstand zwischen zwei Merkmalen im Merkmalsraum eines Histogramms wird eine Gesamtsumme von Differenzen der Anzahlen von Pixeln für jeden entsprechenden Bereich der zwei Merkmale oder ein Euklid-Abstand im Allgemeinen verwendet. In dieser Weise kann der Abstand zwischen Merkmalen erhalten werden.

2) Merkmalsraum-Baumstruktur-Extraktionsprozess:

Ein Merkmalsraum ist ein Raum einer Dimension hoher Ordnung und kann nicht einfach in 2 Dimensionen auf einem Bildschirm angezeigt werden. Folglich wird die Struktur eines Merkmalsraums zuerst durch eine Baumstruktur ausgedrückt. Dann kann der Merkmalsraum virtuell auf einem Bildschirm ausgedrückt werden, indem die Baumstruktur auf den Raum des Bildschirms abgebildet wird.

Um den Merkmalsraum durch eine Baumstruktur auszudrücken, wird der Merkmalsraum angehäuft und wird in mehrere Unterräume unterteilt, um Knoten der Baumstruktur zu bilden. Ferner wird jeder Unterraum (Knoten) angehäuft und wird in Unterräume unterteilt, um Knoten zu bilden. Die Baumstruktur des Merkmalsraums kann durch rekursives Durchführen der vorstehend erwähnten Operation erzeugt werden. Das heißt, alle Merkmale werden in den untersten Knoten jeweils auf einer Einzelknotenbasis angeordnet. 3 zeigt ein Beispiel der so gebildeten Baumstruktur. Obwohl die Anzahl von Knoten, die den Raum unterteilen, eine beliebige Zahl gleich oder größer als 2 sein kann, ist die Anzahl von Knoten hier der Bequemlichkeit halber auf 2 gesetzt. In dieser Baumstruktur werden ähnliche Merkmale nahe beieinander angeordnet und eine Positionsbeziehung von Bildern im Bildraum wird durch die Baumstruktur ausgedrückt.

Hinsichtlich eines Anhäufungsverfahrens kann das allgemeine Verfahren der nächsten Nachbarn, das K-Mittelwert-Algorithmusverfahren usw. verwendet werden. Obwohl ähnliche Bilder nahe beieinander in dieser Baumstruktur angeordnet werden, hängen andere Genauigkeiten von der Genauigkeit der Anhäufung ab. Folglich kann ein Verfahren zum Verbessern der Genauigkeit der Anhäufung, eine Anhäufung gemäß den folgenden Prozeduren verwendet werden. Es sollte beachtet werden, dass die Unterteilungszahl in diesem Verfahren auf 2 gesetzt ist.

  • (i) Erfassung des Mittelpunkts der Anhäufung:
  • a) Auswählen eines beliebigen Punkts A in einem Raum.
  • b) Festlegen des weitesten Punkts vom ausgewählten Punkt A als Mittelpunkt C1 der ersten Anhäufung; und
  • c) Festlegen des weitesten Punkts vom Punkt C1 als Mittelpunkt C2 der zweiten Anhäufung.
  • (ii) Sortieren von Punkten:
  • a) Auswählen eines beliebigen Punkts P in einem Raum.
  • b) Berechnen von Abständen zwischen dem ausgewählten Punkt P und jedem der Mittelpunkte C1 und C2 von zwei Anhäufungen, und Erhalten einer Differenz zwischen den berechneten Abständen als Differenzabstand;

    Differenzabstand = |C1 – P| – |C2 – P|
  • c) Wiederholen von a) und b), um den Differenzabstand für alle Punkte zu erhalten; und
  • d) Sortieren aller Punkte gemäß der aufsteigenden Reihenfolge der Differenzabstände.
  • (iii) Unterteilung von Punkt:

    Eine Differenz zwischen Differenzabständen von entgegengesetzten Seiten des gemäß dem Differenzabstand sortierten Punkts wird erhalten, um eine Grenze von Anhäufungen zwischen Punkten festzulegen, deren Abstand am größten ist. Die Seite, deren Differenzabstand kleiner ist als ein Abstand zur Grenze der Anhäufung, gehört zu C1, und die Seite, deren Differenzabstand größer ist als ein Abstand zur Grenze der Anhäufung, gehört zu C2. Überdies sollte die Baumstruktur gut ausgeglichen sein. Das heißt, wenn es erwünscht ist, Bilder in einem gleichen Intervall auf einem endgültigen Anzeigbildschirm zu verteilen, kann die Trennung in der Mitte der Anzahl von Bildern durchgeführt werden. Die so erhaltenen zwei Anhäufungen werden als Knoten eines Baums festgelegt, um dieselben Prozesse (1), (2) und (3) für jeden Knoten rekursiv durchzuführen. Ein Baum wird durch diese Operation erzeugt und schließlich gehört jedes Bild zu einem Blattknoten.

Mit dem herkömmlichen Verfahren wird ein Bildschirm aus der so erzeugten einen Baumstruktur erzeugt. In der vorliegenden Erfindung wird jedoch eine Baumstruktur mit einer sinnvollen Merkmalseinheit erzeugt und eine Baumstruktur in der Binärbaumform wird für jedes Merkmal erzeugt. Die Merkmale mit einer solchen Bedeutung sind Farbe, Form oder Textur und eine Achse eines durch den folgenden Bildschirmerzeugungsprozess erzeugten Bildschirms entspricht jedem Merkmal.

3) Bildanzeigebildschirm-Erzeugungsprozess:

Nach dem Erzeugen der Baumstruktur wird jede Baumstruktur in 1 Dimension abgebildet. Der Anzeigebereich auf einem Bildschirm ist ein Datenbereich für die Abbildung in 1 Dimension.

Die Baumstruktur wird von einer Wurzel derselben nachgeführt und

  • a) der Datenbereich wird zweigeteilt, so dass die zwei Kindknoten in den jeweiligen Bereichen angeordnet werden. Der Bereich kann gleich unterteilt werden. Um die Anzeigegenauigkeit zu verbessern, können die Unterteilungspunkte im Verhältnis zur Anzahl von Knoten, die zu einem Kindknoten gehören, oder im Verhältnis zu einem Abstand zwischen einem Unterteilungspunkt zur Zeit der Anhäufung und jedem Mittelpunkt bestimmt werden. Auch unter Berücksichtigung des Abstandes eines Spalts zwischen Anhäufungen kann ein Bereich, der dem Raum des Spalts entspricht, ferner festgelegt werden und der Raum ist nicht mit einem Kindknoten versehen. Gemäß einem solchen Verfahren kann der Anzeigebildschirm eine weitere genaue Ähnlichkeit ausdrücken.
  • b) Durchführen des vorstehend erwähnten 1) Merkmalsextraktionsprozesses und 2) Merkmalsraum-Baumstruktur-Extraktionsprozesses in Bezug auf jeden Kindknoten.

Durch rekursive Verarbeitung werden folglich alle Baumstrukturen in 1 Dimension abgebildet. 4 ist ein Beispiel der Abbildung einer Baumstruktur, die in 3 gezeigt ist. In diesem Beispiel ist der Bereich gleich unterteilt, während die Baumstruktur verfolgt wird.

Durch Durchführen des vorstehend erwähnten Prozesses in Bezug auf alle Baumstrukturen können mehrdimensionale Daten, die der Anzahl von Baumstrukturen entsprechen, erhalten werden. Hinsichtlich einer Bildschirmanzeige sind, da es schwierig ist, in mehr als drei Dimensionen auszudrücken, die Daten vorzugsweise bis zu drei Dimensionen. Wenn beispielsweise eine Baumstruktur auf der Basis der Merkmale von Farbe, Form und Textur erzeugt wird, kann der 3-dimensionale Anzeigeraum mit Achsen, die dem Farb-, Form- bzw. Texturstamm entsprechen, erzeugt werden.

5 zeigt ein Beispiel einer endgültigen räumlichen Bildschirmanzeige. Jeder in 5 gezeigte Punkt ist eine Stelle des Merkmals, das aus einem Bild gemäß den Parametern von Form, Textur und Farbe extrahiert wird, und das Bild kann an dieser Stelle als solches angezeigt werden. Es sollte beachtet werden, dass, obwohl Form, Textur und Farbe, die aus einem Bild extrahiert werden, in der vorliegenden Ausführungsform als Merkmale wiedergegeben werden, die vorliegende Erfindung nicht auf ein solches Merkmal begrenzt ist und auf beliebige Merkmale wie z. B. ein aus Textdaten extrahiertes Merkmal angewendet werden kann.

Nun wird eine Beschreibung in Bezug auf 6 bis 10 eines Bildraum-Anzeigeprozesses gemäß der ersten Ausführungsform der vorliegenden Erfindung gegeben. Der Bildraum Anzeigeprozess wird durch Ausführen von im ROM 2 gespeicherten Programmen durchgeführt, während die CPU 1 den RAM 3 als Arbeitsbereich verwendet. In dem Bildraum-Anzeigeprozess gemäß der vorliegenden Ausführungsform wird ein Merkmal jeder Anzeigedimensionsachse zugewiesen.

6 ist ein Ablaufplan eines Prozesses zum Erzeugen eines Merkmalsachsen-Anzeigeraums. In diesem Prozess wird zuerst ein Merkmal A ausgewählt und ein Aufruf wird für einen Anzeigeraum-Erzeugungsprozess I durchgeführt, um einen 1-dimensionalen Anzeigeraum zu erzeugen (Schritt S101). Anschließend werden die Koordinaten des 1-dimensionalen Anzeigeraums des Merkmals A erfasst (Schritt S102) und die erfassen Koordinaten werden als Koordinaten einer Anzeigeachse X festgelegt (Schritt S103). Außerdem wird ein Merkmal B ausgewählt und ein Aufruf an den Anzeigeraum-Erzeugungsprozess I wird durchgeführt, um einen 1-dimensionalen Anzeigeraum zu erzeugen (Schritt S104). Dann werden die Koordinaten des 1-dimensionalen Anzeigeraums des Merkmals B erfasst (Schritt S105) und die erfassten Koordinaten werden als Koordinaten einer Anzeigeachse Y festgelegt (Schritt S106). Ferner wird ein Merkmal C ausgewählt und ein Aufruf wird an den Anzeigeraum-Erzeugungsprozess I durchgeführt, um einen 1-dimensionalen Anzeigeraum zu erzeugen (Schritt S107). Dann werden die Koordinaten des 1-dimensionalen Anzeigeraums des Merkmals B erfasst (Schritt S108) und die erfassten Koordinaten werden als Koordinaten einer Anzeigeachse Z festgelegt (Schritt S109). Schließlich wird ein 3-dimensionaler Anzeigebildschirm auf der Basis der Koordinatenwerte der Anzeigeachsen, die im Prozess der Schritte S103, S106 und S109 erfasst wurden, erzeugt. Es sollte beachtet werden, dass in diesem Prozess der Prozess der Schritte S101–S103 veranlasst, dass das Merkmal A der Koordinatenachse X entspricht, der Prozess der Schritte S104–S106 veranlasst, dass das Merkmal B der Koordinatenachse Y entspricht, und der Prozess der Schritte S107–S109 veranlasst, dass das Merkmal C der Koordinatenachse Z entspricht.

7 ist ein Ablaufplan des vorstehend erwähnten Anzeigeraum-Erzeugungsprozesses I. In diesem Prozess wird, wenn Bilddaten eingegeben werden, das Bildmerkmal bis zum letzten Bild extrahiert (Schritte S201 und S202), um einen Satz von Merkmalen (Merkmalsraum) zu erhalten (Schritt S203).

Anschließend wird ein Binärbaum-Erzeugungsprozess, der in 8 gezeigt ist, aufgerufen (Schritt S204) und der Binärbaum-Erzeugungsprozess wird in Bezug auf den Satz der Merkmale durchgeführt (Schritt S205). Dann wird ein Anzeigeraum-Erzeugungsprozess II, der in 9 gezeigt ist, auf der Basis von Wurzelsätzen (Knoten) des Binärbaums und eines Anzeigeraums als Eingaben aufgerufen (S206) und der Anzeigeraum wird durch Durchführen des Anzeigeraum-Erzeugungsprozesses II erzeugt (Schritt S207).

Die zur Zeit der Ausführung des in 18 gezeigten Anzeigeraum-Erzeugungsprozesses I durchgeführte Routine ist in 8 bis 10 gezeigt. 8 ist ein Ablaufplan eines Binärbaum-Erzeugungsprozesses, der in Schritt S204 aufgerufen wird und in Schritt S205 durchgeführt wird. In diesem Prozess wird ein Aufruf an den in 10 gezeigten Anhäufungsprozess durchgeführt, um zwei Teilmengen (Anhäufungen) A und B zu erzeugen, indem ein Merkmalssatzaufruf halbiert wird (Schritt S301). Der Anhäufungsprozess wurde in der Beschreibung von 2) Merkmalsraum-Baumstruktur-Extraktionsprozess beschrieben. Wenn die Teilmengen A und B erzeugt werden, wird jede der Teilmengen A und B als Kindsatz (Kindknoten) des Merkmalssatzes festgelegt (Schritt S302). Dann wird festgestellt, ob das Merkmalselement der Teilmenge A1 ist oder nicht (Schritt S303). Wenn das Merkmalselement der Teilmenge A1 ist, wird festgestellt, ob das Merkmalselement der Teilmenge B1 ist oder nicht (Schritt S304). Wenn das Merkmalselement der Teilmenge A in Schritt S303 nicht 1 ist, wird überdies der Binärbaum-Erzeugungsprozess aufgerufen, um den Prozess nach Schritt S301 durchzuführen, indem die Teilmenge A als Satz betrachtet wird, und auch den Prozess von Schritt S304 durchzuführen. Dieser Prozess wird beendet, wenn das Merkmalselement der Teilmenge B in Schritt S304 1 ist. Wenn das Merkmalselement der Teilmenge B nicht 1 ist, wird der Binärbaum-Erzeugungsprozess in Schritt S305 aufgerufen (Schritt S306), um den Prozess nach Schritt S301 durchzuführen, indem die Teilmenge B als Satz betrachtet wird, und der Prozess wird beendet.

9 ist ein Ablaufplan des Anzeigeraum-Erzeugungsprozesses II, der in Schritt S206 aufgerufen wird und in Schritt S207 durchgeführt wird. In diesem Prozess wird beurteilt, ob alle Merkmale Sätze (Blattsätze), die zu den jeweiligen untersten Knoten gehören, sind oder nicht (Schritt S401). Wenn sie Blattsätze sind, wird das Bild im Anzeigeraum angeordnet (Schritt S402) und der Prozess wird beendet. Wenn andererseits in Schritt S401 beurteilt wird, dass die Merkmale nicht Blattsätze sind, wird der Anzeigeraum in Teilmengen A und B unterteilt (Schritt S403). Dann wird jede der Teilmengen A und B entsprechend Kindern des Binärbaums einem jeweiligen der Unterräume A und B zugewiesen (Schritt S404. Dann wird der Anzeigeraum-Erzeugungsprozess II rekursiv aufgerufen, indem die Teilmenge A als Satz und der Unterraum A als Anzeigeraum betrachtet wird (Schritt S405). Dann wird der Anzeigeraum-Erzeugungsprozess II rekursiv aufgerufen, indem die Teilmenge B als Satz und der Unterraum B als Anzeigeraum betrachtet wird (Schritt S406). Der Prozess der Schritte S403, S404 und S405 wird wiederholt, bis ein Blattsatz gebildet ist, und das Bild wird im Anzeigeraum angeordnet, nachdem der Blattsatz festgelegt ist (Schritt S402).

10 ist ein Ablaufplan des Anhäufungsprozesses, der in Schritt S301 durchgeführt wird. Wie im Merkmalsraum-Baumstruktur-Extraktionsprozess beschrieben, wird zuerst ein beliebiger Punkt A ausgewählt (Schritt S501) und ein Punkt, der am weitesten vom ausgewählten Punkt A liegt, wird als Punkt C1 festgelegt (Schritt S502). Dann wird ein Punkt, der am weitesten vom Punkt C1 liegt, als Punkt C2 festgelegt (Schritt S503) und ein beliebiger Punkt P, der nicht verarbeitet wurde, wird ausgewählt (Schritt S504). Als nächstes werden Differenzabstände zwischen dem Punkt P und jedem der Punkte C1 und C2 berechnet (Schritt S505). Dann wird der ausgewählte Punkt P als Punkt wiedergegeben, der verarbeitet wurde (Schritt S506). Der Prozess der Schritte S504 bis S506 wird wiederholt, bis unverarbeitete Punkte beseitigt sind (Schritt S507). Nachdem alle Punkte verarbeitet wurden, werden alle Punkte gemäß einer aufsteigenden Reihenfolge der Differenzabstände sortiert (Schritt S508). Dann wird eine Differenz zwischen Differenzabständen, die jedem Punkt vorangehen und nachfolgen, für alle sortierten Punkte berechnet (Schritt S509) und der Satz von Punkten wird an einer Anhäufungsgrenze unterteilt, wo die Differenz zwischen Differenzabständen maximal ist (Schritt S510). Es sollte beachtet werden, dass, obwohl die Merkmale in der vorliegenden Ausführungsform den Anzeigeraum-Dimensionsachsen zugewiesen werden, wie in 6 gezeigt, der vorstehend erwähnte Anzeigeraum-Erzeugungsprozess I aufgerufen werden kann, wenn die Merkmale nicht den Anzeigedimensionsachsen zugewiesen werden.

Die vorliegende Erfindung ist nicht auf die speziell offenbarten Ausführungsformen begrenzt und Veränderungen und Modifikationen können vorgenommen werden, ohne vom Schutzbereich der vorliegenden Erfindung, wie durch die beigefügten Ansprüche definiert, abzuweichen.


Anspruch[de]
Bildraum-Anzeigeverfahren, das umfasst:

a) Extrahieren (S201) von Merkmalen aus Bildern;

b) Erzeugen (S301–S306) einer Baumstruktur für jedes der Merkmale, die für jedes Bild in einem Blattknoten endet;

c) Erzeugen von Dimensionsdaten, die der Anzahl der Merkmale entsprechen;

d) Anzeigen der Dimensionsdaten über die bzw. auf den entsprechenden unterteilten Anzeigeräume als Anzeigekoordinatenachsen-Daten;

e) Unterteilen (S206) des Anzeigeraums entsprechend der Baumstruktur durch Abbilden jeder Baumstruktur auf eine Dimension; und

f) Anzeigen des Merkmalsraums durch Anzeigen der Bilder in entsprechenden Unterteilungen (S207) des unterteilten Anzeigeraums.
Bildraum-Anzeigeverfahren nach Anspruch 1, dadurch gekennzeichnet, dass das Unterteilen des Anzeigeraums die folgenden Schritte umfasst:

Erhalten von Abständen (S505) zwischen jedem Punkt der Merkmale und Mittelpunkten zweier Anhäufungen in Bezug auf jeden Punkt;

Sortieren (S508) aller Punkte entsprechend einer Differenz zwischen den erhaltenen Abständen; und

Unterteilen (S501) des Bildraums in zwei Anhäufungen bzw. Kluster durch Setzen einer Grenze der Anhäufungen bzw. Kluster entsprechend einer Sortierreihenfolge.
Bildraum-Anzeigeverfahren nach Anspruch 2, dadurch gekennzeichnet, dass die Grenze der Anhäufungen zwischen Punkten gesetzt wird, für die eine Differenz zwischen Abständen, die Punkten vorhergehen und nachfolgen, in der Sortierreihenfolge am größten ist. Bildraum-Anzeigeverfahren nach Anspruch 3, dadurch gekennzeichnet, dass ein Bereich, der einer der Dimensionen des Anzeigeraums entspricht, entsprechend den Abständen zu Mittelpunkten von zwei Anhäufungen und entsprechend einem Verhältnis von Differenzen der Differenzabstände an der Grenze der Anhäufungen unterteilt wird. Bildraum-Anzeigeverfahren nach Anspruch 2, dadurch gekennzeichnet, dass die Grenze der Anhäufungen einem Punkt in der Mitte in der Sortierreihenfolge entspricht. Bildraum-Anzeigeverfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Merkmale dreidimensionale Daten sind, die der Form, der Textur und der Farbe der Bilder entsprechen, und die Merkmale unter Verwendung der dreidimensionalen Daten als Anzeigekoordinatenachsen-Daten angezeigt werden. Bildraum-Anzeigevorrichtung zum Extrahieren von Merkmalen aus Bildern, die Mittel zum Ausführen aller Schritte nach einem der Ansprüche 1 bis 6 umfasst. Computerprogramm, das Programmcodemittel umfasst, die, wenn sie auf einem Computer ausgeführt werden, den Computer anweisen, das Verfahren nach einem der Ansprüche 1 bis 6 auszuführen.






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