DE69724755T2

DE69724755T2 - Auffinden von Titeln und Photos in abgetasteten Dokumentbildern

Info

Publication number: DE69724755T2
Application number: DE69724755T
Authority: DE
Inventors: Jiangying Plainsboro Zhou; Daniel P. Hopewell Lopresti
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1997-01-21
Filing date: 1997-12-16
Publication date: 2004-07-01
Anticipated expiration: 2017-12-17
Also published as: DE69724755D1; EP0854433A3; JPH10260993A; US5892843A; EP0854433B1; EP0854433A2

Description

Hintergrund und Zusammenfassung der Erfindung
Die vorliegende Erfindung bezieht sich im Allgemeinen auf computerisierten Informationszugriff. Insbesondere bezieht sich die Erfindung auf ein computerisiertes System zum Auffinden von Titeln oder Photos (einschließlich Titeln) oder anderen Text- oder Nichttextregionen in Punktrasterbildern, wie beispielsweise in abgetasteten Dokumenten. Der aufgefundene Titeltext oder Kopfzeilentext kann auf mehrere Art verwendet werden, einschließlich Schlüsselwortsuche oder Indexierung von Punktrasterbild-Datenbanken, während die aufgefundenen Photos für grafische Schnellsuche benutzt werden können.
Die Welt wird rapide zu einer Informationsgesellschaft. Digitaltechnologie hat die Erstellung riesiger Datenbanken ermöglicht, die eine Fülle von Informationen enthalten. Die kürzliche Explosion in der Popularität von bildorientierten Systemen wird erwartungsgemäß zur Schaffung enormer Datenbanken führen, die enorme Herausforderungen in Bezug auf Datenbankzugriff darstellen werden. In dieser Hinsicht ist die Explosion in der Popularität des World Wide Web bloß ein Beispiel davon wie sich Informationstechnologie rapide in Richtung eines bildorientierten Paradigmas entwickelt.
Bildorientierte Systeme stellen eine große Herausforderung hinsichtlich Wiederauffinden von Information dar. Während Informations-Wiederauffindungstechnologie in codierten, zeichenorientierten Systemen ziemlich gut fortgeschritten ist, funktionieren diese Wiederauffindungstechniken nicht in
bildorientierten Systemen. Das beruht darauf, dass bildorientierte Systeme Information als Rasterdaten speichern, die dem Aussehen der gedruckten Seite und nicht dem Inhalt der Information auf jener Seite entsprechen. Traditionelle Techniken erfordern die Umwandlung von Rastedaten in Textdaten, durch optische Zeichenerkennungssoftware (OCR), bevor sich Informations-Wiederauffindungssysteme ranhalten können.
Leider ist die optische Zeichenerkennungssoftware rechenbetont teuer, und der Erkennungsprozess ist ziemlich langsam. Außerdem können typische Photos ohne Text nicht sinnvoll mit OCR-Technologie verarbeitet werden. Beim Umgang mit großen Mengen bildorientierter Daten ist es nicht praktisch optische Zeichenerkennung der ganzen Datenbank durchzuführen. Überdies, selbst wo Zeit und rechenbetonte Ressourcen die massenhafte OCR-Umwandlung von Bilddaten in Textdaten zulässt, ist das Ergebnis nach wie vor eine große, unstrukturierte Datenbank, ohne eine kurze Liste nützlicher Schlüsselworte, die gestatten könnten ein Dokument von Interesse wiederaufzufinden und zu überprüfen. Durchsuchen der ganzen Datenbank nach selektierten Schlüsselwörtern, mag vielleicht nicht die optimale Antwort sein, da volle Schlüsselwortsuchen häufig viel zu viele Hits bzw. Treffer generieren, um von Nutzen zu sein.
Das Paper nach dem Stand der Technik „a document segmentation, classification and recognition system" von Shih et al, Proceedings of the International Conference on Systems Integration, 15. Juni 1992 Seiten 258–267, offenbart ein System für Dokumentsegmentierung, Klassifizierung und Erkennung, das ähnliche Blöcke gruppiert, sich Statistiken über geometrische Attribute wie beispielsweise, einer „Bounding Box", der Blöcke zu Nutze macht, und die geometrischen Attribute nach Gruppierungsregeln klassifiziert.
Die vorliegende Erfindung geht frisch an das Problem heran. Die Erfindung erkennt an, dass es große Mengen von Daten geben wird, die Raster- oder Bildformat haben, und dass Benutzer diese Information suchen möchten, genauso wie sie jetzt textorientierte Systeme durchsuchen. Anstatt das ganze Dokument von Bildformat in Textformat umzuwandeln, analysiert die vorliegende Erfindung die Punktrasterdaten in ihrem systemeigenen Format, um Regionen innerhalb der Bilddaten aufzufinden, die höchst wahrscheinlich Kandidaten für Dokumenttitel, Kopfzeilen oder anderen Kennzeichnern entsprechen, oder Regionen aufzufinden, die Photos entsprechen. Das System findet diese Dokumenttitel, Kopfzeilen oder andere Bezeichner und Photos in Punktrasterbilddaten auf, was das weitere Manipulieren der aufgefundenen Regionen auf verschiedene Art zulässt. Die aufgefundenen Titel, Kopfzeilen oder Photos können seriell in einer Liste angezeigt werden, auf die der Benutzer Zugriff hat, um ein Dokument von Interesse zu selektieren. Falls erwünscht, können die aufgefundenen Titel oder Kopfzeilen durch optische Zeichenerkennung in Textdaten umgewandelt werden, auf die dann – unter Verwendung codierter, zeichenorientierter Informations-Wiederauffindungssysteme – weiterer Zugriff möglich ist bzw. die dann damit weiter manipuliert werden können.
Als Alternative, selbst wenn die ganze Seite mittels optischer Zeichenerkennung umgewandelt wird, kann es immer noch nützlich sein, verschiedene Titel und andere Text- oder Nichttextregionen mit Hilfe des abgetasteten Bilds ausfindig zu machen. Die Erfindung wird diese Funktion ebenso ausführen.
Die Erfindung ist mehrsprachig. Somit kann sie Titel oder Kopfzeilen in Punktrasterdaten, wie beispielsweise in abgetasteten Dokumenten und in Dokumenten auffinden, die in einer Reihe verschiedener Sprachen geschrieben sind. Die Titelauffindungstechnologie der Erfindung ist außerdem unabhängig vom Schreibsystem. Sie ist fähig Titel in Dokumentbildern aufzufinden, ohne Rücksicht darauf nehmen zu müssen welcher Zeichensatz oder welches Alphabet oder selbst welche Schriftart verwendet worden ist.
Außerdem benötigt das System keinerlei vorherige Kenntnis über die Orientierung des Texts. Es ist fähig mit Dokument-Layouts zurechtzukommen, die gemischte Orientierungen aufweisen, die sowohl vertikale Orientierung als auch horizontale Orientierung einschließen. Die Erfindung beruht auf gewissen angemessenen „Regeln", die für viele, wenn nicht alle, Sprachen gelten. Diese Regeln erklären die Beobachtung, dass Titeltext oder Kopfzeilentext gewöhnlich auf eine Art gedruckt ist, die ihn von anderem Text unterscheiden soll (z.B. größere Schriftart, Fettdruck, mittig am oberen Ende einer Spalte). Diese Regeln erklären außerdem die Beobachtung, dass der Abstand zwischen Zeichen auf einer Textzeile im Allgemeinen enger ist als der Abstand zwischen Zeilen, und dass Textzeilen typisch entweder horizontal oder vertikal sind.
Die Erfindung findet Titel, Kopfzeilen und Photos in Dokumentbildern mit Hilfe von Dokumentanalyse- und rechenbetonten Geometrietechniken auf. Das Bild wird in einem Punktrasterpuffer gespeichert, der dann mittels verbundener Komponentenanalyse analysiert wird, um gewisse geometrische Daten, die mit den verbundenen Komponenten in Bezug stehen, oder Tintenkleckse aufzufinden, die auf der Bildseite erscheinen. Diese geometrischen Daten oder verbundenen Komponentendaten werden in einer Datenstruktur gespeichert, die dann durch einen Klassifizierungsprozess analysiert wird, der die Daten darauf beruhend etikettiert oder sortiert, ob jede verbundene Komponente die geometrischen Eigenschaften eines Zeichens oder die geometrischen Eigenschaften eines Teils von einem Bild, wie beispielsweise einer Punktrasterwiedergabe eines Photos hat.
Nach der Klassifizierung führt dann das System eine „Nearest Neighbour" (Nahesten Nachbarn) Analyse der verbundenen Komponentendaten ins Feld, um „Nearest Neighbour" Graphe zu generieren. Diese werden in einer „Nearest Neighbour" Graphdatenstruktur gespeichert, die eine Liste verbundener Listen repräsentiert, die den „Nearest Neighbour" jeder verbundenen Komponente entsprechen. Die „Nearest Neighbour" Graphe definieren „Bounding Boxes" um jene verbundenen Datenkomponenten herum, die, beispielsweise, einer Textzeile in einer Kopfzeile bzw. Überschrift entsprechen. Die „Nearest Neighbour" Graphe werden danach als horizontal oder vertikal, abhängig davon klassifiziert ob die Verbindungen, die die „Bounding Box" Zentren von „Nearest Neighbours" verbinden, vorherrschend horizontal oder vertikal sind.
Als Nächstes analysiert ein Filtermodul die Daten, um die durchschnittliche Schriftarthöhe aller horizontalen Daten und eine separate durchschnittliche Schriftarthöhe aller vertikalen Daten zu bestimmen. Danach wird jede Kette horizontaler Daten mit dem Durchschnitt verglichen; und jede Kette vertikaler Daten wird mit dem Durchschnitt verglichen, um jene Ketten, die über der Durchschnittshöhe liegen oder jene Ketten deren Höhe einen vorbestimmten Schwellwert überschreitet, zu selektieren. Diese werden als aufzufindende Titelkandidaten selektiert. Falls erwünscht, lässt sich weitere Verfeinerung der Analyse mit Hilfe anderer geometrischer Merkmale durchführen, wie beispielsweise ob die Schriftarten Fettdruck sind oder durch Identifizieren welche Daten Ketten repräsentieren, die auf der Seite zentriert sind.
Nach dem die Titelkandidaten selektiert worden sind, werden die Kandidaten auf die ursprünglichen Punktrasterdaten zurückverwiesen. Im Wesentlichen werden die „Bounding Boxes" der verbundenen Komponenten zu einer einzelnen „Bounding Box" vermischt, die mit dem aufgefundenen Titel assoziiert ist, und jene einzelne „Bounding Box" wird dann zu den Punktrasterdaten zurückverwiesen, so dass die in der "Bounding Box" erscheinenden Punktrasterdaten als ein aufgefundener Titel selektiert werden können. Falls erwünscht, lässt sich der aufgefundene Titel mit Hilfe optischer Zeichenerkennungssoftware weiter verarbeiten, um die Titelabbildung in Titeltext umzuwandeln.
Ebenso, nach dem die Photokandidaten selektiert worden sind, werden die Kandidaten auf die ursprünglichen Punktrasterdaten zurückverwiesen. Die „Bounding Boxes" der Photokandidaten, die einander überlappen, werden in eine einzelne „Bounding Box" vermischt, so dass Punktraster, die innerhalb der „Bounding Box" erscheinen, selektiert und als Teil des Photos aufgefunden werden können. Falls erwünscht, kann mit einer Photoregion assoziierter Kopfzeilentext mit Hilfe optischer Zeichenerkennungssoftware identifiziert und verarbeitet werden. Der Kopfzeilentext kann dann als ein Etikett zum Identifizieren des Photoinhalts oder für spätere Suche verwendet werden.
Um die Erfindung, ihre Ziele und Vorteile vollkommener zu verstehen, kann auf die folgende Spezifikation und auf die zugehörigen Zeichnungen Bezug genommen werden.
Kurzbeschreibung der Zeichnungen
1 ist ein Software-Blockdiagramm des gegenwärtig bevorzugten Ausführungsbeispiels der Erfindung;
2 ist eine Muster-/Probeseite von Punktrasterdaten, die sowohl horizontalen als auch vertikalen Text illustriert;
3a ist eine vergrößerte Ansicht eines Beispiels einer verbundenen Textkomponente;
3b ist eine Vergrößerung eines Beispiels einer verbundenen Nichttextkomponente;
4 ist ein Diagramm der verbundenen Komponentendatenstruktur, die vom gegenwärtig bevorzugten Ausführungsbeispiel verwendet wird;
5a und 5b illustrieren „Bounding Boxes", die um ein Textzeichen (5a) und um ein Nichttextelement (5b) gezogen sind;
6 ist eine Beschreibung der „Nearest Neighbour" Graphdatenstruktur der gegenwärtig bevorzugten Implementierung;
7 ist ein Diagramm, das zum Verständnis der „Bounding Box" Techniken nützlich ist, die vom gegenwärtigen Ausführungsbeispiel verwendet werden;
8 ist ein Beispiel einer gemischten „Bounding Box", die die Beziehung der „Bounding Box" zum ursprünglichen Punktraster der 2 zeigt;
9a–9d illustriert verschiedene „Nearest Neighbour" Graphe, die zum Verständnis nützlich sind wie horizontale und vertikale Klassifizierung durchgeführt wird;
10a und 10b sind beispielhafte Textzeichen "0" und "M", die verschiedene Merkmale zeigen, die vom gegenwärtigen System erfasst werden;
11 illustriert wie die Erfindung möglicherweise auf Etikettierregionen auf einer Seite mit zugehörigen statistischen Sicherheitsfaktoren angewandt werden kann;
12 ist eine Tabelle, die beispielhafte verbundene Komponenten von Text und Nichttext mit den entsprechenden Werten verschiedener geometrischer Komponenten zeigt, die zur Klassifizierung der Komponenten benutzt werden können.
Beschreibung des bevorzugten Ausführungsbeispiels
Bezugnehmend auf 1, wird die gegenwärtig bevorzugte Implementierung der Titelauffindungstechnologie illustriert. Das bevorzugte Ausführungsbeispiel ist ein computerimplementiertes System. 1 ist ein Softwareblockdiagramm des Systems. Die Softwarekomponente wird in den Speicher eines geeigneten Computersystems, wie beispielsweise ein Mikrocomputersystem geladen. Die in der 1 illustrierten Funktionsblöcke sind somit im Prozessor des Computersystems enthalten und werden durch diesen betrieben.
Bezugnehmend auf die 1, wurde eine beispielhafte Seite Abbildungsdaten, wie z. B. eine Seite 20 von einem Magazinartikel illustriert. Obwohl die visuelle Abbildung der Seite 20 hier illustriert ist, wird klargestellt, dass die Seite eigentlich Bilddaten, wie beispielsweise Punktrasterbilddaten umfasst, in denen individuelle schwarze oder weiße Pixels des Bilds als Binärzahlen gespeichert sind. Die Punktrasterbilddaten können von einer breiten Palette verschiedener Quellen stammen, die optische Scanner, Faxmaschinen, Kopierer, Graphiksoftware, Videodaten, „World Wide Web" Seiten und dergleichen einschließen.
Der Prozessor des Computersystems, auf dem die Erfindung implementiert ist, unterhält einen Punktrasterpuffer 22 im Direktzugriffsspeicher (RAM) des Computersystems. Der Punktrasterpuffer 22 ist vorzugsweise einer ausreichenden Größe, um alle der mit einer gegebenen Seite oder Abbildung assoziierten Punktrasterdaten zu halten. Falls erwünscht, lässt sich der Punktrasterpuffer 22 größer machen, um mehrfache Seiten zu halten. Im Allgemeinen wird die Größe des Punktrasterpuffers 22 von der Auflösung des Bilds abhängen. Jedes individuelle Bildelement bzw. Pixel wird innerhalb des Puffers 22 an einer separaten Speicherstelle gespeichert. Bei einigen Anwendungen kann, um Systemgeschwindigkeit zu erhöhen, eine mit einer Auflösung (z. B. 300 Punke je Zoll) für Archivierungszwecke gescannte Seite auf eine niedrigere Auflösung (z. B. 150 Punkte je Zoll) umgewandelt werden, und die Version niedrigerer Auflösung wird dann im Punktrasterpufter 22 für weitere Verarbeitung, wie hierin erläutert, gespeichert. Reduzieren der Auflösung bedeutet, dass weniger Daten verarbeitet werden müssen, und dies wird Berechnung beschleunigen. Beachten Sie bitte, dass das Reduzieren der Bildauflösung im Punktrasterpuffer 22 nicht bedeutet, dass das Archivbild notwendigerweise degradiert wird. Sobald die Titelregionen von Interesse mit Hilfe der Erfindung aufgefunden worden sind, lässt sich die Stelle dieser Regionen leicht wieder auf das Bild höherer Auflösung platzieren.
Was die Punktrasterdaten anbelangt, wird die vorliegende Beschreibung die Erfindung im Kontext von Schwarzweißbilddaten beschreiben. Mit anderen Worten umfassen die Punktrasterdaten, für den Zweck dieser Beschreibung, einfache Binärdaten, die schwarze und weiße Punkte bzw. Pixels repräsentieren, die das Gesamtbild ausmachen. Natürlich lassen sich die hierin beschriebenen Techniken leicht auf andere Formen von Bilddaten, einschließlich Mehrbit-Grautondaten und Mehrbit-Farbdaten ausdehnen. Hier werden binäre Schwarzweißdaten verwendet, um die Erläuterung zu vereinfachen, und um eine mögliche Konfiguration zu illustrieren.
Das computerimplementierte Softwaresystem benutzt eine Gruppe von Verarbeitungsmodulen, wobei jedes konzipiert ist verschiedene Datenmanipulationsfunktionen auszuführen. Diese Verarbeitungsmodule sind in der 1, in Rechtecke eingeschlossen, illustriert. Diese Module arbeiten mit Daten, die im Speicher, gemäß festgelegten Datenstrukturen, gespeichert sind, die nachstehend ausführlicher beschrieben werden. In der 1 sind die Datenstrukturen oder Datenspeicher mittels Rechtecken mit offenem Ende illustriert, um sie von den Verarbeitungsmodulen zu unterscheiden. Außerdem wurden, zum besseren Verständnis der Erfindung, die Verarbeitungsmodule der Erfindung in der 1 in einer Top-Down-Reihenfolge angeordnet, und zeigen die Sequenz in der die verschiedenen Module im Betrieb geschaltet werden.
Zunächst wird vom Modul 24 ein Prozess zum Auffinden verbundener Komponenten mit den Daten im Punktrasterpuffer 22 durchgeführt. Dieser Prozess zum Auffinden verbundener Komponenten bestückt die Datenstruktur 26 der verbundenen Komponenten, die zum Speichern eines großen Teils der mit dem Punktrasterbild assoziierten geometrischen Daten benutzt wird. Eine verbundene Komponente in einem binären Bild ist ein maximaler Satz von sich berührenden schwarzen Pixels. Das Modul 24 lässt sich konfigurieren, um eine Analyse verbundener Komponenten durchzuführen. Im Wesentlichen beginnt der Auffindungsprozess verbundener Komponenten mit einem gegebenen Datenelement innerhalb des Punktrasterpuffers 22 und analysiert die benachbarten Datenelemente, um zu bestimmen ob sie einen Teil einer verbundenen Komponente umfassen, da die schwarzen, den Druckbuchstaben "e" ausmachenden , Punkte alle miteinander verbunden sind. Beziehen Sie sich für ein Beispiel auf die 3a. Beachten Sie, dass der Buchstabe "e" im Beispiel aus einer Ansammlung verbundener schwarzer Punkte besteht. Beginnend am unteren Schwanz des Buchstaben "e" mit offenem Ende, kann man den ganzen Buchstaben nachziehen, indem man von schwarzem Punkt zu schwarzem Punkt traversiert, so wie man eine Halbinsel oder Landenge traversiert ohne Wasser überqueren zu müssen.
Im bevorzugten Ausführungsbeispiel wird die Analyse der verbundenen Komponenten auf eine Art Rasterpunktabfühlung durchgeführt, womit zusammenhängende schwarze Pixel, die auf der selben horizontalen Linie liegen, als eine Einzeleinheit, Segment genannt, behandelt werden. Die verbundene Komponente besteht ihrerseits aus einem oder mehreren Segmenten und kann deshalb als eine verbundene Liste von Segmenten ausgedrückt werden.
Natürlich werden, in einem verallgemeinerten Punktrasterbild, nicht alle der Daten Zeichen repräsentieren. Zur Illustration, siehe hierzu 2, eine Muster-/Probeseite von Daten, die sowohl horizontalen Text als auch vertikalen Text sowie Nichttext- oder Bilddaten, insbesondere ein Photo, aufweist. Die 3b zeigt einen beispielhaften Teil eines Nichttextbereichs. Beachten Sie, dass individuell verbundene Komponenten für die Nichttextdaten definiert werden können, obwohl diese verbundenen Komponenten viel unregelmäßiger sind und in der Größe viel mehr variieren.
Im gegenwärtig bevorzugten Ausführungsbeispiel werden verbundene, Text repräsentierende, Komponenten durch das Modul 28 klassifiziert, wie nachstehend ausführlicher beschrieben werden wird; verbundene, photographische Regionen repräsentierende, Komponenten werden durch das Photoklassifizierungsmodul 29, wie nachstehend besprochen, klassifiziert. Nach jedem dieser beiden Klassifizierungsprozesse, gibt es weitere regionspezifische Prozessprozeduren (z. B., Zeilenorientierungsbestimmung bei Text, oder „Bounding-Box-Mischen" bei Photos). Diese Klassifizierungen und nachfolgenden Verarbeitungsschritte für Textdaten und photographische Daten können in der einen oder anderen Reihenfolge, oder parallel ausgeführt werden Für die Zwecke der gegenwärtigen Erläuterung wird angenommen, dass die Textverarbeitung zuerst durchgeführt wird und danach die Photoverarbeitung mit jenen verbundenen Komponenten durchgeführt wird, die vom Textprozess als „Nichttext" etikettiert wurden. Daher wird, am Ende der Klassifizierungsprozesse, jeder verbundenen Komponente eine von drei möglichen Etiketten zugeordnet worden sein: „Text," „Photo," „Andere."
Das Auffindungsmodul für verbundene Komponenten identifiziert individuelle, verbundene Komponenten oder Kleckse und identifiziert und findet verschiedene geometrische Merkmale auf, die später in diesem Programm von anderen Modulen benutzt werden. Die 4 zeigt grafisch die Konfiguration der Datenstruktur verbundener Komponenten 26; der Leser möchte vielleicht außerdem auf den Anhang Bezug nehmen, in dem eine C Sprachüberschrifts-Dateiauflistung davon und die „Nearest Neighbour" Graphdatenstruktur angegeben sind. Bezugnehmend auf die 4, unterhält die Datenstruktur verbundener Komponenten eine Aufzeichnung einer Reihe geometrischer Merkmale für jede verbundene Komponente. Diese Merkmale schließen ein: die Größe, Breite und Höhe der „Bounding Box", die die verbundene Komponente definiert, die Zahl der Löcher in der verbundenen Komponente, einen Hinweis auf das erste Element in der verbundenen Komponente und verschiedene andere Daten, die die Zahl und den Typ von Bogen beschreiben, die zum Formen der Komponenten benutzt wurden. Diese letzteren, in den 10a und 10b illustrierten, Daten sind nützlich, um Zeichen von Nichtzeichen zu unterscheiden. Die bevorzugte Implementierung zeichnet außerdem auf wie viele Enden die verbundene Komponente hat. Beispielsweise hat der in der 10a gezeigte Buchstabe "O" , einen Aufwärtsbogen 50 und einen Abwärssbogen 52; ein Aufwärtsende 54 und ein Abwärtsende 56; und ein Loch 60. Ein Loch ist eine Region weißen Raums, die gänzlich von schwarzem Raum umgeben ist. Der Buchstabe "M" hat zwei Aufwärtsenden 54 und drei Abwärtsenden 56 und zwei Abwärtsbögen 52 und einen Aufwärtsbogen 50. Wenn Text von Nichttext zu unterscheiden ist, werden diese Merkmale sowie andere von diesen abgeleitete Merkmale dazu verwendet die Unterscheidung auszuführen. Die 12 illustriert einige Probekomponentenzeichen (zwei Englisch und zwei Kanji), und eine Region von einem Photo. In dieser Phase der Analyse, wird kein Versuch unternommen zwischen Text, Photos und anderen Komponenten zu unterscheiden. Das Klassifizierungsmodul 28 ist für die Unterscheidung zwischen Textkomponenten, Photokomponenten und anderen Komponenten verantwortlich. Die Tabelle gibt die tatsächlichen für die Komponenten berechneten Werte an. Beachten Sie beim Vergleichen der tatsächlichen Werte, dass die Nichttextkomponente eine viel größere Zahl von Löchern sowie eine viel größere Zahl von Aufwärts- und Abwärtsbögen aufweist.
Die Datenstruktur verbundener Komponenten ist im Wesentlichen als eine Liste konfiguriert, wobei jede verbundene Komponente als ein separates Element in der List repräsentiert wird. In dieser Phase der Analyse, wird kein Versuch unternommen zwischen Text- und Nichttextkomponenten zu unterscheiden. Jede verbundene Komponente (ob Text oder Nichttext) wird entsprechend der in 4 gezeigten Datenstruktur in die Liste eingetragen.
Nach dem die Datenstruktur 26 durch den Auffindungsprozess verbundener Komponenten 24 bestückt worden ist, wird der Klassifizierungsprozess oder das Modul 28 dann aufgefordert mit den Daten in der Datenstruktur 26 zu arbeiten. Das Klassifizierungsmodul ist für die Unterscheidung zwischen Textkomponenten und Nichttextkomponenten verantwortlich. Englische Textzeichen können von verbundenen Nichttextkomponenten gewöhnlich auf der Basis der in jeder Komponente vorgefundnen Zahl von Löchern unterschieden werden. Ein englisches Zeichen hat höchstens ein oder zwei Löcher. Natürlich muss, um kompliziertere Zeichen, wie beispielsweise chinesische Zeichen, der Schwellwert für die Zahl der Löcher geringfügig höher sein. Ebenso neigen die Zahl der Enden sowie der Typ und die Zahl der Kurven für Textzeichen dazu kleiner als Nichttextzeichen zu sein. Wiederum werden kompliziertere Zeichen, wie beispielsweise chinesische Zeichen, eine höhere Zahl dieser Attribute haben.
Das gegenwärtig bevorzugte Ausführungsbeispiel klassifiziert eine verbundene Komponente oder einen Klecks als Text, wenn sie bzw. er die Kriterien im folgenden Pseudocode erfüllt:
Für jede verbundene Komponente:
WENN Größe der „Bounding Box" < vorbestimmte Größe
DANN ist die Komponente Nichttext, Ausstiegroutine.
SONST WENN Zahl der schwarzen Pixels < vorbestimmte Zahl
DANN ist die Komponente Nichttext, Ausstiegroutine.
SOINST WENN Breite oder Höhe > vorbestimmte Größe
DANN ist die Komponente Nichttext, Ausstiegroutine.
SONST WENN durchschnittliche Strichstärke (Pixels/Segment) > vorbestimmte Stärke
DANN ist die Komponente Nichttext, Ausstiegroutine.
SONST WENN Stärke/Höhe-Verhältnis, oder Höhe/Stärke-Verhältnis > vorbestimmtes Verhältnis
DANN ist die Komponente Nichttext, Ausstiegroutine.
SONST WENN Zahl der Löcher >= vorbestimmte Zahl
DANN ist die Komponente Nichttext, Ausstiegroutine.
SONST WENN Zahl der Aufwärtsenden und Abwärtsenden > vorbestimmte Zahl
DANN ist die Komponente Nichttext, Ausstiegroutine.
SONST WENN Verhältnis von (Zahler schwarzer Pixels in Bounding Box)/(Größe der Bounding Box) < vorbestimmte Zahl
DANN ist die Komponente Nichttext, Ausstiegroutine.
SONST ist die Komponente Text, Ausstiegroutine.
Auf ähnliche Weise klassifiziert das Photoklassifizierungsmodul 29 die Daten der verbundenen Komponenten als „Photo" oder „Nichtphoto". Wie oben festgestellt, können die Textklassifizierung und Photoklassifizierung in der einen oder anderen Reihenfolge oder parallel implementiert werden.
Das gegenwärtig bevorzugte Ausführungsbeispiel klassifiziert eine verbundene Komponente als eine Region innerhalb eines Photos, falls sie die Kriterien im folgenden Pseudocode erfüllt:
WENN Größe der Bounding Box < vorbestimmte Größe
DANN ist die Komponente kein Photo, Ausstiegroutine.
WENN # der schwarzen Pixels < vorbestimmte #
DANN ist die Komponente kein Photo, Ausstiegroutine.
WENN (Breite/Höhe) ODER (Höhe/Breite) > vorbestimmtes Verhältnis
DANN ist die Komponente kein Photo, Ausstiegroutine.
WENN (# der schwarzen Pixels/Größe der Bounding Box) < vorbestimmtes Verhältnis
DANN ist die Komponente kein Photo, Ausstiegroutine.
WENN (Breite > vorbestimmte Größe) UND (Höhe > vorbestimmte Größe)
DANN ist die Komponente ein Photo, Ausstiegroutine.
WENN durchschnittliche Strichstärke (Pixels/Segment) > vorbestimmtes Verhältnis
DANN ist die Komponente ein Photo, Ausstiegroutine.
WENN # der Löcher > vorbestimmte #
DANN ist die Komponente ein Photo, Ausstiegroutine.
WENN # der Aufwärtsenden und Auwärtsenden > vorbestimmte #
DANN ist die Komponente ein Photo, Ausstiegroutine.
ANDERNGFALLS ist die Komponente kein Photo, Ausstiegroutine.
Das Vermögen des Systems zwischen Text, Photos und anderen Bilddaten zu unterscheiden, funktioniert, indem verschiedenen geometrischen Merkmalen, die allgemein in diesen jeweiligen Abbildungstypen zu finden sind, Attribute zugeordnet werden. Zeichen umfassen im Allgemeinen massive schwarze Striche, die eine relativ einheitliche Größe und ein relativ einheitliches Seitenverhältnis aufweisen. Zeichen haben außerdem im Allgemeinen eine relativ einheitliche durchschnittliche Strichstärke/-breite. Andererseits neigen photographische Regionen dazu unregelmäßig bemessen zu sein und unregelmäßige Seitenverhältnisse zu haben. Außerdem haben photographische Regionen eine höhere Zahl von Löchern in einer gegebenen Region oder verbundenen Komponente. Diese Löcher tragen zum Grautonaussehen bei, das vom Auge wahrgenommen wird, wenn man die Region aus einiger Entfernung betrachtet. Diese Merkmale lassen sich daher verwenden, um bei der Unterscheidung zwischen Text- und Photoregionen zu helfen. Natürlich gibt es hierbei einige Überlappung. Einige Photoregionen können Attribute haben, die jenen von Text ähneln und einiger Text kann Attribute aufweisen, die Photoregionen ähnlich sind. Um dies zu berücksichtigen, mischt das System „Bounding Boxes" verbundener Komponenten deren „Bounding Boxes" sich überlappen. Solches Überlappen ist in photographischen Regionen häufig anzutreffen. Auf diese Weise können verbundene Komponenten, die sonst als Text gekennzeichnet werden würden, als photographisch klassifiziert werden, wenn sich die „Bounding Box" der Komponente mit „Bounding Boxes" anderer photographischer Regionen überlappt. Gleichermaßen können verbundene Komponenten, die andernfalls als photographisch klassifiziert werden würden, als Text klassifiziert werden, wenn die benachbarten verbundenen Komponenten Text sind und keine „Bounding Box" Überlappung vorliegt. Ein Beispiel der letzteren Situation würde, beispielsweise, auftreten, wenn eine ornate Schriftart zu Beginn einer Zeile Text verwendet wird.
Sobald Text und andere Komponenten identifiziert worden sind, kann die Datenstruktur der verbundenen Komponenten dazu benutzt werden einen Hinweis zu speichern wie die jeweilige Komponente klassifiziert wurde. Beachten Sie bitte, dass an dieser Stelle der Analyse gewisse Daten als textartige Kennzeichen aufweisend selektiert worden sind. Zu diesem Zeitpunkt wird keine optische Zeichenerkennung ausgeführt, daher arbeitet das System immer noch mit Bilddaten und geometrischen Attributen jener Bilddaten.
Bis zu diesem Punkt umfasst jede verbundene Komponente ein individuelles Zeichen (oder einen Teil davon) oder eine individuelle Form oder einen individuellen Klecks. Der nächste Schritt ist, mit dem Gruppieren von Zeichen zu beginnen, um zu identifizieren welche Regionen vielleicht Zeilen oder Ketten von Text repräsentieren. Um das zu erreichen, wird eine „Nearest Neighbour" Analyse durchgeführt. Das bevorzugte Ausführungsbeispiel verwendet Delaunay-Triangulierung, um ein „Nearest Neighbour" Graph zu konstruieren. Für Hintergrundinformationen über Delaunay-Triangulierung, siehe "A Sweepline Algorithm for Voronoi Diagrams," Algorithmica, 2: 153–174, 1987. Die „Nearest Neighbour" Analyse nutzt die früher erwähnten Annahmen aus, dass Abstand auf einer Zeile im Allgemeinen enger als Abstand zwischen Zeilen ist. Dies ist eine angemessen zu stellende Vermutung, und wird sich wahrscheinlich (aber nicht garantiert) über verschiedene Sprachen und Zeichensätze hinweg bestätigen. Die „Nearest Neighbour" Analyse wird vom Modul 30 durchgeführt. Es greift auf die Daten in der Datenstruktur 26 für verbundene Komponenten zu und generiert ein „Nearest Neighbour" Graph, das in der Graphdatenstruktur 32 für „Nearest Neighbour" Graphe gespeichert ist. Die 6 zeigt diagrammatisch die Konfiguration der gegenwärtig bevorzugten Datenstruktur zum Speichern von „Nearest Neighbour" Graphen. Die „Nearest Neighbour" Analyse vergleicht im Wesentlichen jede vorher identifizierte Zeichenkomponente mit den anderen Zeichenkomponenten, um zu identifizieren welche einander am nächsten sind. Im bevorzugten Ausführungsbeispiel geschieht dies durch geometrische Berechnung des Abstands zwischen den Mittelpunkten der Zeichenkomponenten. Die Mittelpunkte der Zeichenkomponenten werden ihrerseits geometrisch durch die rechteckigen „Bounding Boxes" erstellt, die für jedes Zeichen, während der Auffindung verbundener Komponenten, erstellt wurden. Erinnern Sie sich daran, dass die „Bounding Box" Daten, das heißt, die maximalen und minimalen X und Y Werte für jede Komponente durch das Modul 24 in der Datenstruktur 26 für verbundene Komponenten gespeichert worden sind.
Zur Illustration der „Nearest Neighbour" Analyse beziehen Sie sich bitte auf die 5a und 5b und die 7. Die 5a und 5b illustrieren wie der Auffindungsprozess für verbundene Komponenten, „Bounding Boxes" um eine aufgefundene Komponente definiert. Insbesondere zeigt die 5a die „Bounding Box" um eine Textkomponente; 5b zeigt die „Bounding Box" um eine Nichttext-Zeichenkomponente. 7 zeigt wie die „Nearest Neighbour" Analyse bestimmt, dass gewisse Textzeichen näher zueinander und deshalb wahrscheinlich Teil einer Einzelzeile oder einer Textkette sind. Der Grund dafür ist, dass in den meisten Druckkonventionen, Zeichen in derselben Textzeile gewöhnlich näher aneinander als Zeichen über Textzeilen hinweg platziert sind. Deshalb stammt der „Nearest Neighbour" einer Textkomponente wahrscheinlich aus der selben Textzeile. In der Tat ist, in einer Mehrheit von Fällen, der „Nearest Neighbour" eines Zeichens einfach das nächste Zeichen im Satz. Auf diese Weise werden eine Kette von Zeichen aus der selben Textzeile miteinander verbunden. Normalerweise werden Zeichen in einer Textzeile in mehrere „Nearest Neighbour" Graphe gruppiert. Die Analyse wird geometrisch ausgeführt, und sucht jene Komponenten, die einander am Nächsten sind. In den meisten Fällen wird eine verbundene Komponente nur einen „Nearest Neighbour" haben. Jedoch kann eine verbundene Komponente manchmal mehr als einen „Neighbour" (Nachbarn) haben, wobei jeder den selben minimalen Abstand hat. In solchen Fällen werden alle solcher „Neighbours" (Nachbarn) als die „Nearest Neighbours" der Komponente betrachtet. Um dies zu berücksichtigen, repräsentiert die Datenstruktur jede Komponente durch eine verbundene Liste. Beispielsweise illustriert die 9a die Situation in der die Komponente "A" zwei „Nearest Neighbours" hat, Komponente "B" und Komponente "C". Der Abstand zwischen „Neighbours" (Nachbarn) wird durch eine Linie gemessen, die die Mittelpunkte der jeweiligen „Bounding Boxes" verbindet. Die „Nearest Neighbour" Analyse konstruiert eine verbundene Liste aller Komponenten, die sich auf einer festgestellten minimalen Distanz vom „Neighbour" (Nachbarn) der Komponente befinden.
Wie die 9a illustriert, können „Nearest Neighbour" Komponenten in beliebiger Orientierung (einschließlich horizontalen und vertikalen Orientierungen) angeordnet sein. Das gegenwärtig bevorzugte Ausführungsbeispiel identifiziert Linien zwischen verbundenen „Nearest Neighbour" Komponenten als entweder horizontal oder vertikal. In der 9a ist die Verbindung zwischen Komponenten "A" und "B" eine horizontale Verbindung, wogegen die Verbindung zwischen Komponenten "A" und "C" eine vertikale Verbindung ist. Im Allgemeinen wird einer Verbindung zwischen einer verbundenen Komponente und jedem ihrer „Nearest Neighbours" eine Orientierung gegeben. Zum Beispiel, wenn die Komponente "B" der „Nearest Neighbour" von Komponente "A" ist, dann ist die Verbindung horizontal, wenn die Linie, die die Mittelpunkte der „Bounding Boxes" von "A" und "B" verbinden, unter einer 45° Diagonallinie ist, und vertikal, wenn anders. Die 9b illustriert eine horizontale Verbindung gemäß dieser Definition. Verbundene Komponenten, die gegenseitig „Nearest Neighbours" sind, formen eine verbundene Einheit, die ein „Nearest Neighbour" Graph genannt wird. Beispielsweise, bezugnehmend auf die 9c, wenn die Komponente "B" der „Nearest Neighbour" von Komponente "A" ist, und die Komponente "C" der „Nearest Neighbour" der Komponente "B" ist, dann sind "A," "B" und "C" alle Teil des selben „Nearest Neighbour" Graphs. Die Datenstruktur für den „Nearest Neighbour" Graph schließt ein Datenelement ein, das mit jedem Eintrag in die verbundene Liste zur Speicherung der Orientierung der Verbindung assoziiert ist.
Das Modul 34 untersucht die geometrische Orientierung jedes „Nearest Neighbour" Graphs, um zu bestimmen, ob die Zeile oder Kette von Zeichen, die durch ein Graph verbunden ist, vertikal oder horizontal angeordnet ist. Im gegenwärtigen bevorzugten Ausführungsbeispiel wird jeder „Nearest Neighbour" Graph, abhängig von der vorherrschenden Orientierung seiner Verbindungen, als horizontal oder vertikal klassifiziert. Wenn die Mehrheit der Verbindungen horizontal sind, dann ist der „Nearest Neighbour" Graph horizontal; andernfalls ist er vertikal. Die 9d illustriert ein Beispiel, dass ein Graph als horizontal klassifiziert ist, weil er zwei horizontale Verbindungen und eine vertikale Verbindung hat. Sobald die Orientierung eines „Nearest Neighbour" Graphs bestimmt worden ist, werden dann jene Verbindungen im Graph, deren Orientierungen nicht der bestimmten Orientierung entsprechen, entfernt. In der 9d, wird das vertikale Glied, das die Buchstaben "A" und "D" verbindet, entfernt nach dem der Graph als horizontal angeordnet identifiziert worden ist. Das Modul 36 überprüft dann die Schriftgröße von Textkomponenten in jeder Orientierung und erkennt Kandidatentitelkomponenten in jeder Orientierung separat.
Während ein Schwellwert von 45°bei der gegenwärtigen Implementierung zum Bestimmen der Orientierung einer Verbindung benutzt wird, muss das System vielleicht Seiten berücksichtigen, die schräg verlaufen, daher können vielleicht verschiedene horizontale und vertikale Schwellwerte geeignet sein. Überdies, obwohl horizontal und vertikal die einzig möglichen Orientierungen des in der gegenwärtigen Implementierung in Betracht gezogenen Texts sind, kann Text anderer Orientierungen, falls erwünscht, in Erwägung gezogen werden. Insbesondere kann das System veranlasst werden Textzeilen zu identifizieren, die schräg gedruckt sind. Andererseits, kann es für ein System, das nur zur Handhabung von englischem Text eingesetzt wird, möglich sein das vorgenannte Design zu vereinfachen, indem separate Verarbeitung für vertikale Textzeilen eliminiert wird.
Wenn weitere Unterscheidung erforderlich ist, kann die Schwellwertentscheidung hinsichtlich der Schriftartgröße auf einer lokalen Basis getroffen werden, d. h. nicht auf der Basis der Seite als Ganzes. Während durchschnittliche Schriftartgröße in vielen Fällen ein gutes Attribut zur Unterscheidung bereitstellt, können Systeme gebaut werden, die andere Unterscheidungsattribute als Schriftgröße einsetzen. Solch andere Attribute lassen sich außerdem zusammen mit der Schriftartgröße verwenden, um verfeinerte oder zusätzliche Unterscheidungsebenen zu erzielen. Beispielsweise kann die geometrische Mitte der Textkette mit der Vertikallinienmitte der Seite oder mit der Vertikallinienmitte von Textspalten verglichen werden, um als mögliche Titelkandidaten jene zu selektieren, die um „prominente" Positionen auf der Seite zentriert sind. Als Alternative, oder zusätzlich, kann die Strichbreite oder -stärke der das Zeichen bildenden Linien zur Identifizierung von Titelkandidaten verwendet werden. In dieser Hinsicht wäre eine Fettdrucktype mit einer fetteren Strichbreite ein wahrscheinlicherer Kandidat für eine Kopfzeile. Jedoch, wie oben erwähnt, erzielt das gegenwärtige Ausführungsbeispiel, unter Verwendung der Buchstabengröße oder zusammen mit der Schriftartgröße als das unterscheidende Merkmal, ziemlich erfolgreiche Ergebnisse.
Während das gegenwärtig bevorzugte Ausführungsbeispiel Schriftartgröße zur Klassifizierung verbundener Komponenten verwendet, können andere geometrische Attribute, wie jene, die hierin beschrieben sind, zur Verstärkung des Klassifizierungsprozesses verwendet werden. Ein Weg dies zu erzielen, ist ein sequentieller oder verschachtelter Programmschleifenansatz, wo eine Entscheidung erster Ebene getroffen wird (Verwendung der Schriftartgröße, beispielsweise), gefolgt von einer zweiten Ebene, die den Schritt weiter verfeinert (Verwendung einiger anderer Attribute), und so weiter. Für irgendeinen der Klassifizierungsschritte (z. B., Identifizieren verbundener Komponenten als entweder Text oder Photo; oder Titel/Nichttitel-Klassifizierung von Textkomponenten), können multiple Attribute gleichzeitig in Betracht gezogen werden. Ein Weg dies zu erreichen, wäre für jede verbundene Komponente Vektoren zu konstruieren, wo jedes Vektorelement eins der selektierten Attribute ist. Dann kann Klassifizierung durch Vergleichen der Vektordaten mit vorbestimmten Vektorschwellwerten durchgeführt werden. Neuronale Netzanalyse ist eine weitere Alternative für gleichzeitiges Analysieren multipler Attribute.
Um Schriftartgrößen zu unterscheiden, berechnet das Filtrationsmodul 36 zuerst die durchschnittliche Schriftartgröße aller auf der Seite identifizierten vertikalen Zeichen, und berechnet ebenso die durchschnittliche Schriftartgröße aller auf der Seite erscheinenden horizontalen Zeichen. Das Modul 36 führt dies leicht durch, indem es auf die „Nearest Neighbour" Graphdatenstruktur 32 zugreift, um die vertikalen (oder horizontalen) Ketten zu isolieren und sich dann durch Hinweis auf die Datenstruktur verbundener Komponenten zurückzubeziehen, um die Höhe der entsprechenden „Bounding Box" für jenes Zeichen zu ermitteln. Sobald die horizontalen und vertikalen Durchschnitte berechnet worden sind, wird jede Kette mit jenem Durchschnitt verglichen. Ketten, die Zeichen umfassen, die größer als ein vorbestimmter Schriftartschwellwert sind, werden als Titelkandidaten selektiert.
Danach wird eine „Bounding Box" für jeden der selektierten horizontalen und vertikalen Kandidaten konstruiert. Das Modul 38 konstruiert diese „Bounding Boxes" im Wesentlichen durch Mischen der individuellen „Bounding Boxes" der Komponentenzeichnen, Selektieren der geeigneten Größe, so dass alle Zeichen innerhalb einer selektierten Textzeile von der „Bounding Box" umrandet sind. Wie bereits festgestellt, wird eine Textzeile gewöhnlich in mehrere „Nearest Neighbour" Graphe zerteilt. Daher involviert der Mischprozess im Modul 38 das Mischen von „Bounding Boxes" jener „Nearest Neighbour" Graphe zu einer einzelnen „Bounding Box", um eine Titeltextzeile zu formen. Diese „Bounding Boxes" werden dann bei 40 auf geeignete Weise gespeichert. Bei 40 gespeicherte „Bounding Box" Daten beschreiben im Wesentlichen die (X,Y) Positionen der oberen linken und unteren rechten Ecken jeder „Bounding Box". Die Positionen sind auf die (X,Y) Stellen auf dem ursprünglichen Punktrasterbild 20 bezogen. Somit können diese „Bounding Box" Koordinaten dafür verwendet werden „Bounding Boxes" auf dem Originaldokument zu umreißen, und damit die Titelkandidaten zu selektieren. Wenn erwünscht können die selektierten Kandidaten dann vom Originaldokument weg angezeigt werden, wie beispielsweise in einer Liste von Titeln, wobei jeder auf das Originaldokument zurückbezogen ist. Als Alternative können die Titel durch optische Zeichenerkennung verarbeitet werden, um sie in Zeichendaten umzuwandeln.
Für jene verbundenen Komponenten, die als Photokomponenten identifiziert wurden, mischt sie das Modul 39, um Photoregionen zu formen. Der Mischprozess prüft die „Bounding Boxes" aller Photokomponenten; jene, deren „Bounding Boxes" miteinander überlappen, werden zu einer einzigen Region vermischt. Eine neue „Bounding Box", die die gemischte Region umschließt, wird dann konstruiert. Diese „Bounding Boxes" werden dann bei 41 auf geeignete Weise gespeichert. Diese „Bounding Boxes" beschreiben im Wesentlichen die (X,Y) Koordinaten der oberen linken und unteren rechten Ecken jeder Photoregion. Die Positionen sind Referenzen auf die (X,Y) Stellen auf dem ursprünglichen Punktrasterbild 20. Somit können diese „Bounding Box" Koordinaten dafür verwendet werden „Bounding Boxes" auf dem Originaldokument zu umreißen, und damit die Photoregionen zu selektieren.
Wenn erwünscht, kann Text, der die mit jeder Photoregion assoziierte Kopfzeile repräsentiert, außerdem als Teil des Prozesses identifiziert werden. Für jede Photoregion wird ein schmaler Streifen des Rechteckrahmens, der die „Bounding Box" des Photos umgibt, in Betracht gezogen. Text, der innerhalb der vier Seiten des schmalen Streifens liegt, wird untersucht und eine Kandidaten-Kopfzeilentextregion selektiert. Der Selektionsprozess kann wie folgt voranschreiten:
WENN horizontaler Text im unteren Streifen vorhanden ist
DANN ist es die Kopfzeile, Ausstiegroutine.
WENN horizontaler Text im oberen Streifen vorhanden ist
DANN ist es die Kopfzeile, Ausstiegroutine.
WENN vertikaler Text im linken Streifen vorhanden ist
DANN ist es die Kopfzeile, Ausstiegroutine.
WENN vertikaler Text im rechten Streifen vorhanden ist
DANN ist es die Kopfzeile, Ausstiegroutine.
ANDERNFALLS es wird keine Kopfzeile gefunden, Ausstiegroutine.
Obwohl die Erfindung im Zusammenhang mit einem Ausführungsbeispiel beschrieben wurde, das Kopfzeilen, Titel und Photos auffindet, wird die Erfindung ebenso grundlegende Textregionen (ob Titel oder nicht) sowie andere Nichttextregionen, wie beispielsweise Graphe, Linienzeichnungen und dergleichen identifizieren. Überdies ist es möglich zwischen verschiedenen „Levels" (Ebenen) von Text, auf der Basis von Schriftartgröße, relativer Platzierung und so weiter, zu unterscheiden. Demzufolge kann, mittels der hierin beschriebenen Technologie, eine, bei 80 in der 11 gezeigte, Seitenabbildung verwendet werden, um Ausgabe 82 zu produzieren, die verschiedene unterschiedlich etikettierte Regionen identifiziert. Der Mechanismus zum Unterscheiden zwischen Text und Nichttext ist oben beschrieben worden. Mit Hilfe dieses Mechanismus kann die Bildregion 84, die Photo 86 entspricht, identifiziert und etikettiert werden. Im illustrierten Ausführungsbeispiel schließt das Etikett einen Vertrauenswert (z. B. 0,74) ein, der anzeigt wie sicher das System hinsichtlich der Validität eines gegebenen Etiketts ist. Ebenso können alle Textregionen etikettiert werden, um die Funktion der Textregion anzuzeigen (z. B. Level 1[L1] Titel, Level 2[L2] Titel, Textkörper, und so weiter). Wie bei der Bildregion kann jede Textregion ebenso einen Vertrauenswert einschließen.
Anhang

Claims

Ein computerimplementiertes Verfahren der Identifizierung von Titeln in Dokumentenbilddaten, dadurch gekennzeichnet, dass es folgende Schritte umfasst: Speichern der Bilddaten (20) in einem Puffer (22); Durchführen der Auffindung (24) verbundener Komponenten an den gespeicherten Bilddaten, um eine Vielheit verbundener Komponenten zu identifizieren und eine erste Datenstruktur (26) zum Speichern von Datenobjekten zu generieren, die besagten verbundenen Komponenten entsprechen; für jedes in besagter ersten Datenstruktur gespeichertes Datenobjekt, das Identifizieren wenigstens eines ersten Attributs, das die Form der entsprechenden verbundenen Komponente widerspiegelt und eines zweiten Attributs, das eine geometrische Eigenschaft der entsprechenden verbundenen Komponente widerspiegelt und Speichern besagter ersten und zweiten Attribute in Verbindung mit besagter ersten Datenstruktur: Analysieren (28) wenigstens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Bilddaten entsprechen, die Text repräsentieren; Durchführen einer "Nearest-Neighbour" Analyse (30) an besagten Objekten, um wenigstens ein "Nearest-Neighbour" Diagramm (32) zu konstruieren, das Bilddaten entspricht, die wenigstens einen Teil von wenigstens einer Zeile Text repräsentieren; Analysieren (34) besagter zweiten Attribute, um eine durchschnittliche geometrische Eigenschaft der verbundenen Komponenten zu bestimmen, die Text repräsentierenden Bilddaten entsprechen: für jedes "Nearest-Neighbour" Diagramm, das Bilddaten entspricht, die wenigstens eine Zeile Text repräsentieren, Vergleichen der gespeicherten zweiten Attribute der jedem Diagramm zugehörigen Datenobjekte mit besagter durchschnittlichen geometrischen Eigenschaft; Auswählen (36) als Titelkandidaten jener "Nearest-Neighbour" Diagramme, in denen die Komponentendatenobjekte zweite Attribute aufweisen, die wesentlich anders als besagte durchschnittliche geometrische Eigenschaft sind; Definieren einer "Bounding Box" für jeden der besagten Titelkandidaten und Mischen (38) besagter "Bounding Boxes" von Titelkandidaten, die wenigstens einer Zeile Text entsprechen, um wenigstens eine gemischte "Bounding Box" (40) zu bestimmen ; und Verbinden besagter gemischten "Bounding Box" (40) mit besagten gespeicherten Bilddaten, wodurch besagte gemischte "Bounding Box" Teile besagter gespeicherter Bilddaten zeichnet, die Titel repräsentieren.
Verfahren des Anspruchs 1, wobei besagte geometrische Eigenschaft Größe ist.
Verfahren des Anspruchs 1, das weiter Analysieren besagter "Nearest-Neighbour" Diagramme umfasst, die Bilddaten entsprechen, die wenigstens eine Zeile Text repräsentieren, um räumliche Orientierung zu bestimmen.
Verfahren des Anspruchs 1, das weiter Designieren besagter "Nearest-Neighbour" Diagramme umfasst, die Bilddaten entsprechen, die wenigstens eine Zeile Text als entweder allgemein horizontal orientierten Text oder allgemein vertikal orientierten Text repräsentieren.
Verfahren des Anspruchs 4, wobei besagtes Designieren durch Vergleichen besagter "Nearest-Neighbour" Diagramme durchgeführt wird, die Bilddaten entsprechen, die wenigstens eine Zeile Text nach festgelegten Daten repräsentieren, die einen Neigungswinkel von fünfundvierzig (45) Grad repräsentieren.
Verfahren des Anspruchs 4, das weiter separate Bestimmung von folgendem umfasst: (a) der horizontalen durchschnittlichen Schrifthöhe verbundener Komponenten, die Bilddaten entsprechen, die allgemein horizontal orientierten Text repräsentieren und (b) der vertikalen durchschnittlichen Schrifthöhe verbundener Komponenten, die Bilddaten entsprechen, die allgemein vertikal orientierten Text repräsentieren und Verwenden besagter separat bestimmter durchschnittlichen Schrifthöhen, zum Auswählen als Titelkandidaten: (a) jene "Nearest-Neighbour" Diagramme, die Bilddaten entsprechen, die allgemein horizontal orientierte Zeilen von Text repräsentieren, in denen die Komponentendatenobjekte größere Größenattribute als besagte horizontale durchschnittliche Schrifthöhe aufweisen; und (b) jene "Nearest-Neighbour" Diagramme, die Bilddaten entsprechen, die allgemein vertikal orientierte Zeilen von Text repräsentieren, in denen die Komponentendatenobjekte größere Größenattribute als besagte vertikale durchschnittliche Schrifthöhe aufweisen.
Verfahren des Anspruchs 1, wobei besagte Bilddaten Einbitdaten sind, die Schwarzweißwerte repräsentieren.
Verfahren des Anspruchs 1, wobei besagte Bilddaten Mehrbitdaten sind, die Grauwerte repräsentieren.
Verfahren des Anspruchs 1, wobei besagte Bilddaten Mehrbitdaten sind, die Farbwerte repräsentieren.
Verfahren des Anspruchs 1, wobei besagtes erste geometrische Attribut aus der Gruppe ausgewählt wird, die aus folgendem besteht: Anzahl von schwarzen Bildpunkten, Anzahl von weißen Bildpunkten, Anzahl von Löchern, Anzahl von Strichenden, Anzahl von nach oben gerichteter Strichbogen, Anzahl nach unten gerichteter Strichbogen.
Verfahren des Anspruchs 1, wobei besagtes zweite Attribut eine "Bounding Box" um die verbundene Komponente definiert.
Verfahren des Anspruchs 1, wobei das zweite Attribut eine rechteckige "Bounding Box" um die verbundene Komponente definiert, der durch obere, untere, linke und rechte Begrenzungslinien gekennzeichnet ist.
Verfahren des Anspruchs 1, das weiter Analysieren besagter ersten und zweiten Attribute umfasst, um zu identifizieren, welche Datenobjekte Text repräsentierenden Bilddaten entsprechen.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut der Bildpunktzahl einer festgelegten Farbe entspricht, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vergleichen des ersten Attributs mit einem vorbestimmten Schwellwert durchgeführt wird.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut der Anzahl schwarzer Bildpunkte entspricht, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn das erste Attribut unter einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut einer "Bounding Box" entspricht, welche die verbundene, eine Höhe und Breite aufweisende, Komponente umschließt, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vergleichen von wenigstens einer besagten Höhe und Breite mit einem vorbestimmten Schwellwert durchgeführt wird.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut einer "Bounding Box" entspricht, welche die verbundene, eine Höhe und Breite aufweisende, Komponente umschließt, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn wenigstens eine besagte Höhe und Breite über einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut einer durchschnittlichen Strichbreite entspricht, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn besagtes erste Attribut über einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 18, wobei die Auffindung besagter verbundener Komponente durch Segmentieren besagter gespeicherter Daten in Segmente durchgeführt wird, die schwarze Bildpunkte enthalten und wobei besagte durchschnittliche Strichbreite als das Verhältnis der Anzahl schwarzer Bildpunkte zur Anzahl schwarzer Segmente berechnet wird.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut einer "Bounding Box" entspricht, welche die verbundene, eine Höhe und Breite aufweisende, Komponente umschließt, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn das Verhältnis von Breite zu Höhe über einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut einer "Bounding Box" entspricht, der die verbundene, eine Höhe und Breite aufweisende, Komponente umschließt, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn das Verhältnis Höhe zu Breite über einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut der Anzahl Bildlöcher in der verbundenen Komponente entspricht, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn das erste Attribut über einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut der Anzahl von Strichenden in der verbundenen Komponente entspricht, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn das erste Attribut über einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 1, wobei besagtes erste Attribut einer "Bounding Box" entspricht, welche die verbundene Komponente umschließt, die eine durch die Höhe und Breite definierte Größe aufweist, und weiter der Anzahl schwarzer Bildpunkte innerhalb der verbundene Komponente entspricht, und wobei besagter Schritt des Analysierens besagter ersten Attribute, um zu identifizieren welche Datenobjekte Text repräsentierenden Bilddaten entsprechen, durch Vereinbaren durchgeführt wird, dass die Bilddaten keinen Text repräsentieren, wenn das Verhältnis der Anzahl schwarzer Bildpunkte zur Größe der besagten "Bounding Box" unter einem vorbestimmten Schwellwert liegt.
Verfahren des Anspruchs 1, das weiter die Auffindung eines Titels aus besagten Bilddaten durch Kopieren einer Teilmenge besagter gespeicherten, durch besagte "Bounding Box" gezeichneten, Bilddaten in einen Speicherpuffer umfasst.
Verfahren des Anspruchs 1, das weiter die Auffindung eines Titels aus besagten Bilddaten durch Durchführen optischer Zeichenerkennung (OCR) an einer Teilmenge besagter gespeicherten, durch besagte "Bounding Box" gezeichneter Bilddaten umfasst, um Textdaten zu generieren, die dem gezeichneten Titel entsprechen.
Verfahren des Anspruchs 1, das weiter die Verwendung besagter "Bounding Box" zum Generieren von Textdaten, die dem gezeichneten Titel entsprechen und das Verwenden besagter Textdaten als einen besagten Bilddaten zugehörigen Index umfasst.
Verfahren des Anspruchs 1, das weiter Verwenden besagter "Bounding Box", zum Generieren von Textdaten, die dem gezeichneten Titel entsprechen und Verwenden besagter Textdaten als ein computersuchbares, besagten Bilddaten zugehöriges Schlüsselwort umfasst.
Verfahren des Anspruchs 1, das weiter für jedes in besagter ersten Datenstruktur gespeicherte Datenobjekt das Identifizieren einer Vielheit zweiter Attribute umfasst, wobei jedes eine andere geometrische Eigenschaft der entsprechenden verbundene Komponente umfasst.
Verfahren des Anspruchs 29, das weiter das Analysieren besagter zweiten Attribute in einer vorbestimmten sequentiellen Reihenfolge umfasst, um als Titelkandidaten jene "Nearest-Neighbour" Diagramme auszuwählen, in denen die Komponentendatenobjekte Attribute aufweisen, die festgelegten Charakteristiken entsprechen.
Verfahren des Anspruchs 29, das weiter das Analysieren besagter zweiten Attribute im wesentlichen gleichzeitig umfasst, um als Titelkandidaten jene "Nearest-Neighbour" Diagramme auszuwählen, in denen die Komponentendatenobjekte Attribute aufweisen, die festgelegten Charakteristiken entsprechen.
Verfahren des Anspruchs 1, das weiter das Identifizieren fotografischer Bereiche innerhalb Dokumentenbilddaten durch Durchführen folgender Schritte umfasst: für jedes in besagter ersten Datenstruktur gespeicherte Datenobjekt, das Identifizieren wenigstens eines dritten Attributs, das eine geometrische Eigenschaft der entsprechenden verbundenen Komponente widerspiegelt und Speichern besagten dritten Attributs in Verbindung mit besagter Datenstruktur; Analysieren (29) wenigstens besagten dritten Attributs, das eine geometrische Eigenschaft widerspiegelt, um zu identifizieren welche Datenobjekte Bilddaten entsprechen, die mögliche fotografische Bereiche repräsentieren, durch Festlegen einer "Bounding Box" für jede besagter verbundener Komponenten und Auswählen als fotografische Bereichskandidaten jener verbundenen Komponenten, die "Bounding Boxes" aufweisen, die größer als eine erste vorbestimmte Schwellwertgröße sind; weiteres Analysieren besagten dritten Attributs, das eine geometrische Eigenschaft besagter fotografischer Bereichskandidaten aufweist, um als fotografische Bereiche jene Kandidaten auszuwählen, die besagte Attribute haben, die eine geometrische Eigenschaft widerspiegeln, die eine erste Beziehung mit einem zweiten vorbestimmten Schwellwert hat; Mischen (39) besagter "Bounding Boxes" besagter ausgewählten fotografischen Bereiche, deren entsprechende "Bounding Boxes" sich überlappen, um wenigstens eine gemischte "Bounding Box" (41) zu definieren; und Verbinden besagter gemischten "Bounding Box" mit besagten gespeicherten Bilddaten, wodurch besagte gemischte "Bounding Box" Teile besagter gespeicherter Bilddaten zeichnet, die besagte fotografische Bereiche repräsentieren.
Verfahren des Anspruchs 32, wobei besagtes Attribut eine geometrische Eigenschaft widerspiegelt, die die Zahl schwarzer Bildpunkte in besagter verbundenen Komponente repräsentiert.
Verfahren des Anspruchs 32, wobei besagtes Attribut, das eine geometrische Eigenschaft widerspiegelt, das Höhe-Breite-Verhältnis der "Bounding Box" besagter verbundenen Komponente repräsentiert.
Verfahren des Anspruchs 32, wobei besagtes Attribut, das eine geometrische Eigenschaft widerspiegelt, das Verhältnis der Anzahl schwarzer Bildpunkte zur Größe der "Bounding Box" besagter verbundenen Komponente repräsentiert.
Verfahren des Anspruchs 32, wobei besagtes Attribut, das eine geometrische Eigenschaft widerspiegelt, die Anzahl von Löchern in besagter verbundenen Komponente repräsentiert.
Verfahren des Anspruchs 32, wobei besagtes Attribut, das eine geometrische Eigenschaft widerspiegelt, die Anzahl von nach oben und unten gerichteten Enden schwarzer Bildpunkte in besagter verbundenen Komponente repräsentiert.