PatentDe  


Dokumentenidentifikation DE69229468T2 28.10.1999
EP-Veröffentlichungsnummer 0544430
Titel Verfahren und Gerät zur Bestimmung der Wortfrequenz in einem Dokument ohne Dokumentbilddekodierung
Anmelder Xerox Corp., Rochester, N.Y., US
Erfinder Cass, Todd A., Cambridge, Massachusetts 02138, US;
Huttenlocher, Daniel P., Ithaca, New York 14580, US;
Halvorsen, Per-Kristian, Los Altos, California 94022, US;
Withgott, M. Margaret, Los Altos, California 94022, US;
Kaplan, Ronald M., Palo Alto, California 94306, US;
Rao, Ramana B., San Francisco, California 94112, US
Vertreter Grünecker, Kinkeldey, Stockmair & Schwanhäusser, Anwaltssozietät, 80538 München
DE-Aktenzeichen 69229468
Vertragsstaaten DE, FR, GB
Sprache des Dokument En
EP-Anmeldetag 16.11.1992
EP-Aktenzeichen 923104319
EP-Offenlegungsdatum 02.06.1993
EP date of grant 23.06.1999
Veröffentlichungstag im Patentblatt 28.10.1999
IPC-Hauptklasse G06K 9/00

Beschreibung[de]

Die vorliegende Erfindung betrifft Verbesserungen für Verfahren und Vorrichtungen für die Dokumentbildverarbeitung und insbesondere Verbesserungen für das Erkennen und Bestimmen der Frequenz von Wörtern oder Bildern in einem Dokument, ohne zuerst die Wörter oder Bilder zu decodieren oder auf eine externe lexikalische Referenz Bezug zu nehmen.

Bei der computergestützten elektronischen Dokumentverarbeitung ist eine der Eigenschaften des Dokuments/der Dokumente, die der Bediener häufig zu kennen wünscht, die Frequenz (Häufigkeit) mit der einige oder alle der Wörter auftreten. Zum Beispiel geben Salton & McGill Introduction to Modern Information Retrieval, Chapter 2, pp. 30, 36 McGraw-Hill Inc., 1983 an, daß die Verwendungsfrequenz eines bestimmten Begriffs in einem Kontext der Informationswiedergewinnung mit der Wichtigkeit dieses Begriffs relativ zum Informationsinhalt des Dokuments korrelieren kann. Die Information zur Wortfrequenz kann also für die automatische Dokumentzusammenfassung und/oder -kommentierung nützlich sein. Die Information zur Wortfrequenz kann auch zum Lokalisieren, Indizieren, Archivieren, Sortieren oder Abrufen von Dokumenten verwendet werden.

Eine andere Verwendung der Wortfrequenzinformation ist in der Textverarbeitung gegeben. So wurde zum Beispiel eine Textverarbeitungseinrichtung vorgeschlagen, um die häufige Verwendung gleicher Wörter in einem Text zu verhindern, wobei die häufig auftretenden Wörter im Dokument kategorisiert und angezeigt werden. Eine Liste der ausgewählten Wörter und der Häufigkeit des Auftretens wird für jedes Wort innerhalb eines bestimmten Teils des Textes erstellt, wobei das angegebene Wort und seine Position auf einer CRT angezeigt wird.

Derartige Wortfrequenzbestimmungen werden bisher auf elektronischen Texten durchgeführt, deren Inhalt zuvor in eine maschinenlesbare Form umgewandelt wird, etwa unter Verwendung einer optischen Zeichenerkennung (OCR), bei der Bitmap-Worteinheitenbilder oder in einigen Fällen eine Anzahl von Zeichen in den Worteinheitenbildern entziffert und mit Bezug auf eine externe Zeichenbibliothek in codierte Wiedergaben der Bilder umgewandelt werden. Die decodierten Wörter oder Zeichenketten werden dann mit Wörterbuchbegriffen in einem assoziierten Wörterbuch verglichen. Eine derartige optische Zeichenerkennung weist den Nachteil auf, daß der Zwischenschritt für die optische Zeichenerkennung eine größere Möglichkeit eines Berechnungsfehlers einführt. Außerdem erfordert die Verarbeitung eine beträchtliche Zeitdauer, wodurch der gesamte Prozeß zur Identifikation der Worteinheiten verlangsamt wird.

Die europäische Patentanmeldung 0-402-064 (Sakai et al.) beschreibt eine Textverarbeitungseinrichtung in einem Computersystem, die das Auftreten von Wörtern in einem Text zählt und eine Liste sich wiederholender Wörter auf einer CRT anzeigt. Die Liste gibt die ausgewählten Wörter zusammen mit der Anzahl ihres Auftretens und ihren Positionen im Text an. Wenn eine Wortwiederholung nicht erwünscht ist, kann ein Bediener diese durch Synonyme ersetzen oder in anderer Weise den Text mit Hilfe von Aktionen zum Suchen, Anzeigen und Bearbeiten von Text ändern.

Die europäische Patentanmeldung EP-A-0-364-179 (Hawley) beschreibt ein Verfahren und eine Vorrichtung zum Extrahieren von Schlüsselwörtern aus Text, der in einem maschinenlesbaren Format gespeichert ist. Die Frequenz des Auftretens jedes Wortes in einer Datei wird im Vergleich zu der Frequenz des Auftretens von anderen Wörtern in der Datei berechnet. Wenn die berechnete Frequenz die Frequenz desselben Wortes in einer dem Text entsprechenden Referenzdomäne um einen vorbestimmten Schwellwert übersteigt, dann wird dieses Wort als Schlüsselwort für die Datei ausgewählt.

Die europäische Patentanmeldung EP-A-0-364-180 (Hawley) beschreibt ein Verfahren und eine Vorrichtung zum automatischen Indizieren und Abrufen von Dateien in einem sehr großen Computerdateisystem. Schlüsselwörter werden automatisch aus zu indizierenden Dateien extrahiert und als Einträge in einer Indexdatei verwendet. Jede Datei, die einen der Indexeinträge als Schlüsselwort aufweist, wird in dem Index mit diesem Schlüsselwort assoziiert. Wenn eine Datei abgerufen werden soll und ihr Inhalt, nicht aber ihr Name oder ihre Lokation bekannt ist, können ihre Schlüsselwörter eingegeben werden, um entsprechend ihre Identifikationsinformation (zusammen mit den Identifkationsinformationen zu anderen Dateien mit denselben Schlüsselwörtern) anzuzeigen, wodurch das Wiederauffinden erleichtert wird.

In FIRST INTERNATIONAL CONFERENCE ON DOCUMENT ANALYSIS AND RECOGNITION IDCAR 91, 30 September - 2 October 1991, San Malo gibt D. S. Bloomberg auf den Seiten 963-971 in "Multiresolution morphological approach to document image analysis" morphologische Operationen zum Durchführen einer Dokumentbildanalyse an. Es werden zum Beispiel Techniken zum Identifizieren von kursiven und fetten Wörtern im Text unter Verwendung einer Extraktion auf der Wortebene bei einer reduzierten Auflösung angegeben.

In PROCEEDINGS 7TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION, Vol. 2, 30 July - 2 August 1984, Montreal, CA, geben Casey et al. in "Unsupervised construction of decision networks for pattern classification" einen Klassifikationseinrichtung zum Codieren von Dokumenten unter Verwendung eines Mustervergleichs an. Es wird eine Klassifikation des Zeichenmuster durch Mustervergleich angegeben, nachdem ein Entscheidungsnetz als Vorklassifikationseinrichtung verwendet wird, um eine Prototypklasse auszuwählen.

In Übereinstimmung mit einem Aspekt der vorliegenden Erfindung ist ein Verfahren zum Bestimmen der Frequenz von Wortbildeinheiten in einem elektronischen Dokument, das ein oder mehrere Bilder umfaßt, angegeben, wobei das Verfahren durch folgende Schritte gekennzeichnet ist:

(A) Segmentieren des einen bzw. der mehreren Bilder in Wortbildeinheiten, ohne den Bildinhalt zu decodieren,

(B) Bestimmen von wenigstens einer Formeigenschaft für jede aus dem Satz von Wortbildeinheiten in dem einen bzw. den mehreren Bildern, ohne die Wortbildeinheiten zu decodieren,

(C) Identifizieren von Äquivalenzklassen in dem Satz von Wortbildeinheiten durch das Clustern von Wortbildeinheiten mit ähnlichen Formeigenschaften, und

(D) Bestimmen der Anzahl von Wortbildeinheiten in jeder Äquivalenzklasse.

In Übereinstimmung mit einem anderen Aspekt der vorliegenden Erfindung ist eine Vorrichtung zum Bestimmen der Frequenz der Wortbildeinheiten in einem elektronischen Dokument, das eines oder mehrere Bilder umfaßt, angegeben, wobei die Vorrichtung gekennzeichnet ist durch

eine Segmentierungseinrichtung zum Segmentieren des einen bzw. der mehreren Bilder in Wortbildeinheiten, ohne den Bildinhalt zu decodieren,

eine Bestimmungseinrichtung zum Bestimmen von wenigstens einer Formeigenschaft für jede aus einem Satz von Wortbildeinheiten in dem einen bzw. den mehreren Bildern, ohne die Wortbildeinheiten zu decodieren,

eine Identifikationseinrichtung zum Identifizieren von Äquivalenzklassen des Satzes von Wortbildeinheiten durch das Clustern von Wortbildeinheiten mit ähnlichen Formeigenschaften, und

eine Bestimmungseinrichtung zum Bestimmen der Anzahl von Wortbildeinheiten in jeder Äquivalenzklasse.

Es ist eine Aufgabe der vorliegenden Erfindung, ein Verfahren und eine Vorrichtung zum Bestimmen der Frequenz des Auftretens von Wortbildeinheiten in einem Dokument nur auf der Basis der visuellen Eigenschaften des gescannten Dokuments und ohne Bezugnahme auf eine externe lexikalische Referenz anzugeben.

Andere Aufgaben der vorliegenden Erfindung bezwecken, ein Verfahren und eine Vorrichtung des beschriebenen Typs anzugeben, wobei die Wörter oder die Wortbildeinheiten selbst nicht bestimmt oder decodiert werden müssen, wobei zuvor keine Umwandlung des Dokuments zu optischen Zeichencodes oder ASCII-Codes vorgenommen werden muß wobei das Verfahren und die Vorrichtung verwendet werden können, um eine Schlüsselworterkennung zu unterstützen.

In Übereinstimmung mit einem Aspekt der vorliegenden Erfindung sind ein Verfahren und eine Vorrichtung zum Bestimmen der Frequenz von Wortbildeinheiten in einem Dokument angegeben, wobei die Wortbildeinheiten im Dokument nicht zuerst decodiert werden müssen oder das Dokument zu optischen Zeichencodes umgewandelt werden muß. Die vorliegende Erfindung verwendet eine nicht auf dem Inhalt basierende Bildeinheitenerkennung, die auf den Bildformeigenschaften wie etwa der Länge, Höhe oder einer anderen Eigenschaften der Bildeinheit basiert. Genauso gut können andere Systeme wie eine Bitmap-Workstation (d. h. eine Workstation mit einer Bitmap-Anzeige) oder ein System, das ein Bitmapping oder Scannen verwendet, für die Implementierung des hier beschriebenen Verfahrens und der Vorrichtung verwendet werden.

In Übereinstimmung mit einer Ausführungsform des Verfahrens der vorliegenden Erfindung wird das Dokument zuerst eingegeben und in Bildeinheiten segmentiert. Es wird wenigstens eine signifikante Bildformeigenschaft der Bildeinheit bestimmt, wobei Äquivalenzklassen der Bildeinheiten identifiziert werden, in die Bildeinheiten mit ähnlichen Bildformeigenschaften geclustert werden. Die Anzahl der Bildeinheiten in den Äquivalenzklassen bestimmt die Frequenz des Auftretens der Bildeinheit.

Die Bildeinheiten können Worteinheiten in einem Textdokument sein, wobei eine Worteinheit vorzugsweise durch das Erhalten einer Wortformwiedergabe der Worteinheit bewertet wird, die wenigstens ein eindimensionales Signal, das die Form der Worteinheit kennzeichnet, oder eine Bildfunktion ist, die eine die Worteinheit umschließende Grenze definiert, wobei die Bildfunktion erweitert wird, so daß eine Kantenfunktion, welche die Kanten der innerhalb der Grenzen festgestellten Zeichenkette wiedergibt, über die gesamte Domäne durch eine unabhängige Variable innerhalb der geschlossenen Grenzen definiert wird, ohne daß das oder die Zeichen der Worteinheit individuell festgestellt und/oder identifiziert werden.

Insbesondere sind ein Verfahren und eine Vorrichtung zum Bestimmen der Frequenz von Wortbildeinheiten in einem Dokument direkt aus dem gespeicherten Bitmapbild des Dokuments heraus angegeben, ohne daß die Worteinheiten zuerst decodiert werden, indem etwa die Wortbildeinheiten im Dokumentbild zu Zeichencodewiedergabe wie ASCII oder einen anderen codierten Text umgewandelt werden. Die Technik ist deshalb unabhängig von der Sprache, wobei tatsächlich graphische Muster, codierte und sinnlose Wörter einfach miteinbezogen und verarbeitet werden können, wobei die mögliche Einführung von unnötigen Fehlern durch Zwischeninterpretationsprozesse wie etwa einer optischen Zeichenerkennung (OCR) beseitigt werden können. Das Verfahren kann also in vorteilhafter Weise die natürlich segmentierbare Natur der Worteinheitenbilder verwenden, die in dem gedruckten Text verwendet werden.

Die Äquivalenzklassen werden durch das Vergleichen ausgewählter Bildformeigenschaften, Eigenschaftskombinationen oder abgeleiteter Wiedergaben der Bildeinheitenformen miteinander bestimmt. Die Bildformeigenschaften können die Länge, die Breite, den Font, den Schriftschnitt, die Querschnitteigenschaften, die Anzahl der Oberlängen, die Anzahl der Unterlängen oder ähnliches umfassen. Die Bildeinheiten in jeder Äquivalenzklasse werden miteinander verknüpft und gemappt, um das Bestimmen der Frequenz derselben zu ermöglichen.

Das Verfahren kann das Durchführen einer Datenverarbeitung in einem Datenverarbeitungssystem umfassen, welches eine Verarbeitungseinrichtung zum Durchführen von Funktionen durch das Ausführen von Programmbefehlen in einer vorbestimmten Weise sowie eine Speichereinrichtung umfaßt, die eine Vielzahl von Verarbeitungsprogrammodulen umfaßt. Das Verfahren umfaßt das Identifizieren von Worteinheiten in den Textbildern und das Bestimmen von wenigstens einer Bildformeigenschaft der Worteinheiten. Worteinheiten mit ähnlichen Bildformeigenschaften werden dann geclustert, wobei die geclusterten Worteinheiten quantifiziert werden.

Die Vorrichtung kann ein programmierter digitaler Computer sein.

Die vorliegende Erfindung wird im folgenden beispielhaft mit Bezug auf die beigefügten Zeichnungen beschrieben. Es zeigen:

Fig. 1 ein Flußdiagramm eines Verfahrens in Übereinstimmung mit einer bevorzugten Ausführungsform der vorliegenden Erfindung zum Bestimmen der Frequenzen von Wortbildeinheiten in einem Dokument, ohne das Dokument zuerst zu Zeichencodes umzuwandeln, und

Fig. 2 eine Vorrichtung in Übereinstimmung mit einer bevorzugten Ausführungsform der vorliegenden Erfindung zum Bestimmen der Frequenzen von Wortbildeinheiten in einem Dokument, ohne zuerst die Wortbildeinheiten zu decodieren oder die Wortbildeinheiten im Dokument zu Zeichencodes umzuwandeln.

Eine bevorzugte Ausführungsform des Verfahrens der vorliegenden Erfindung ist in dem Flußdiagramm von Fig. 1 dargestellt, und die Vorrichtung zum Durchführen des Verfahrens von Fig. 1 ist in Fig. 2 dargestellt. Der deutlicheren Darstellung halber wird die vorliegende Erfindung mit Bezug auf die Verarbeitung eines einzelnen Dokuments beschriebenen. Es ist jedoch zu beachten, daß die vorliegende Erfindung auf die Verarbeitung eines Dokumentcorpus angewendet werden kann, das eine Vielzahl von Dokumenten umfaßt.

Wie in Fig. 2 gezeigt, wird das Verfahren auf einem elektronischen Bild eines Originaldokuments 5 durchgeführt, das Textzeilen 7, Titel, Zeichnungen, Fig. 8 oder ähnliches enthalten kann, wobei das Dokument auf einem oder mehreren Blättern oder Seiten 8 aus Papier oder in anderer greifbarer Form vorliegt. Das zu verarbeitende elektronische Dokumentbild wird auf herkömmliche Weise durch zum Beispiel eine Eingabeeinrichtung wie den gezeigten optischen Scanner 12 und den Sensor 13, einen Kopiergerät-Scanner, einen Braille-Lesegerät-Scanner, eine Bitmap-Workstation oder ähnliches erzeugt. Derartige Eingabeeinrichtungen sind aus dem Stand der Technik bekannt, weshalb hier auf eine Beschreibung derselben verzichtet wird. Eine zum Beispiel von einem Scanner-Sensor 13 erhaltene Ausgabe wird digitalisiert, um Bitmap-Bilddaten zu erhalten, die das Dokumentbild für jede Seite des Dokuments wiedergeben, wobei die Daten zum Beispiel in einem Speicher 15 eines Spezial- oder Universalcomputers 16 gespeichert werden. Der digitale Computer 16 kann von dem Typ sein, der eine Datenverarbeitung in einem Datenverarbeitungssystem durchführt, das eine Verarbeitungseinrichtung zum Durchführen von Funktionen durch das Ausführen von Programmbefehlen in einer vorbestimmten Weise umfaßt. Derartige Computer sind aus dem Stand der Technik bekannt. Die Ausgabe aus dem Computer 16 wird zu einer Ausgabeeinrichtung wie zum Beispiel einem Speicher oder einer anderen Form von Speichereinheit oder wie dargestellt zu einer Ausgabeanzeige 17 gegeben, die zum Beispiel ein Photokopiergerät, eine CRT-Anzeige, ein Drucker, ein Faxgerät oder ähnliches sein kann.

Wie in Fig. 1 gezeigt, umfaßt die erste Phase der Bildverarbeitungstechnik der vorliegenden Erfindung eine Dokumentbildanalyse auf einer niedrigen Ebene, wobei das Dokumentbild unter Verwendung von herkömmlichen Bildanalysetechniken oder im Fall von Textdokumenten unter Verwendung eines Begrenzungsboxverfahrens seitenweise in nicht decodierte Information, welche die Bildeinheiten enthält, segmentiert wird.

Ein anderes Verfahren zum Finden von Wortboxen besteht darin, das Bild mit einem horizontalen Strukturelement (SE), das Zeichen aber nicht Wörter miteinander verbindet, zu schließen, worauf eine Operation folgt, welche die Begrenzungsboxen der verbundenen Bildkomponenten (in diesem Fall Wörter) etikettiert. Der Prozeß kann beträchtlich beschleunigt werden, indem eine oder mehrere Schwellwertverkleinerungen (mit dem Schwellwert 1) verwendet werden, wodurch das Bild verkleinert wird und der Abstand zwischen den Zeichen geschlossen wird. Auf die Schwellwertverkleinerung(en) folgt typischerweise ein Schließen mit einem kleinen horizontalen SE. Die Operation zum Etikettieren verbundener Komponenten wird auch mit der Verkleinerung vorgenommen, wobei dann die Ergebnisse zu voller Größe vergrößert werden. Der Nachteil des Arbeitens mit einer Verkleinerung besteht darin, daß die Wortbegrenzungsboxen ungenau sind; für viele Anwendungen reicht diese Genauigkeit jedoch aus. Das beschriebene Verfahren weist bei arbiträren Textfonts zufriedenstellende Ergebnisse auf, wobei jedoch in extremen Fällen, wie etwa bei großen Fonts mit festgelegten Breiten und großen Zeichenabständen oder bei kleinen Fonts mit variablen Breiten und kleinen Wortabständen Fehler auftreten können. Das robusteste Verfahren wählt ein SE zum Schließen auf der Basis einer Messung von spezifischen Bildeigenschaften aus. Dazu sind die folgenden zwei zusätzlichen Schritte erforderlich:

(1) Ordnen der Bildkomponenten in dem originalen oder verkleinerten (aber nicht geschlossenen) Bild nach Zeilen von links nach rechts und von oben nach unten,

(2) Erstellen eines Histogramms des horizontalen Komponentenabstands. Dieses Histogramm sollte natürlich die kleinen Zeichenabstände von den größeren Wortabständen unterscheiden. Dann wird das Tal zwischen diesen Gipfeln verwendet, um die Größe der SE für die Verwendung beim Schließen des Bildes zu bestimmen, so daß Zeichen aber nicht Wörter miteinander verbunden werden.

Nachdem die Begrenzungsboxen oder die Wortboxen bestimmt wurden, werden die Positionen der Worteinheiten und die Raumbeziehungen zwischen den Worteinheiten auf einer Seite bestimmt (Schritt 25). Zum Beispiel kann ein Dokumentbild in englischer Sprache auf der Basis des relativen Unterschieds zwischen dem Abstand zwischen Zeichen innerhalb eines Wortes und dem Abstand zwischen Wörtern in Wortbildeinheiten segmentiert werden. Die Satz- und Absatzgrenzen können in ähnlicher Weise festgestellt werden. Außerdem kann eine zusätzliche Bereichssegmentierungsanalyse durchgeführt werden, um eine Beschreibung des physikalischen Dokumentaufbaus zu erzeugen, welche die Seitenbilder in etikettierte Bereiche unterteilt, die zusätzlichen Dokumentelementen wie Figuren, Tabellen, Fußnoten oder ähnlichem entsprechen. Zum Beispiel können Figurbereiche von Textbereichen durch den relativen Mangel von in Zeilen angeordneten Bildeinheiten innerhalb des Bereichs unterschieden werden. Unter Verwendung dieser Segmentierung kann auch Information über die Anordnung der verarbeiteten Dokumente sowie optional andere Eingabeinformation wie der Dokumentstil oder die "Lesereihenfolge" für die Wortbilder erzeugt werden. Der Begriff "Bildeinheit" wird also hier verwendet, um ein identifizierbares Segment eines Bildes wie etwa eine Zahl, ein Zeichen, einen Glypen, ein Symbol, ein Wort, eine Phrase oder eine andere Einheit zu bezeichnen, die verläßlich extrahiert werden kann. Um das Dokument zu betrachten und zu bewerten, wird das Dokumentbild in vorteilhafter Weise in Sätze von Zeichen, Symbolen oder anderen Elementen wie Wörtern segmentiert, die zusammen eine einzelne Verständniseinheit bilden. Derartige einzelne Verständniseinheiten sind allgemein in einem Bild dadurch gekennzeichnet, daß sie durch einen größeren Abstand voneinander getrennt werden als die Elemente einer Einheit, wobei sie auch durch eine vorbestimmte graphische Hervorhebung wie etwa eine Begrenzungsbox oder eine andere graphische Trennungsangabe getrennt werden können, die eine oder mehrere Bildeinheiten von anderen Bildeinheiten im Dokumentbild unterscheidet. Derartige Bildeinheiten, die einzelne Verständniseinheiten darstellen, werden im folgenden als "Worteinheiten" bezeichnet.

In vorteilhafter Weise wird als nächstes ein Unterscheidungsschritt 30 durchgeführt, um die Bildeinheiten zu identifizieren, die einen ausreichenden Informationsinhalt aufweisen, um für die Bewertung des Dokumentinhalts verarbeitet werden zu können. Eine bevorzugte Ausführungsform zum Feststellen der Funktion oder von Stoppwörtern ist ein morphologisches Verfahren. In diesem Verfahren wird zuerst die Länge und Höhe jeder Bildeinheit im Bild bestimmt, wobei Bildeinheiten von nicht mehr als einer vorbestimmten Anzahl von Zeichen als kurze Bildeinheiten bestimmt werden, die vorzugsweise drei Zeichen oder weniger aufweisen. Als nächstes werden die Bildeinheiten, die keine kurzen Bildeinheiten sind, aus dem Bild gelöscht. Dann wird das Bild in der horizontalen Richtung unscharf gemacht, wobei die Bildeinheiten jedoch nicht ineinander verwischt werden. Dies kann zum Beispiel durch das SCHLIESSEN des Bildes mit einem horizontalen Strukturelement mit zum Beispiel einer Länge von 5 Pixeln vorgenommen werden. Die Länge des horizontalen Strukturelements, das zum Unscharfmachen der Zeichen mit der Höhe x verwendet wird, ist von der Breite des verwendeten Zeichentyps abhängig. Weiterhin können andere Konfigurationen von Strukturelementen in der SCHLIESSEN-Operation verwendet werden, um denselben Verwischungseffekt zu erhalten. Die effektivste Möglichkeit zum Verwischen von Zeichen mit der Höhe x besteht jedoch darin, wie oben beschrieben ein horizontales Strukturelement zu verwenden.

Eine VEREINIGUNG von Erosionen wird dann unter Verwendung eines Satzes von Oberlängen entsprechenden Strukturelementen und eines Satzes von Unterlängen entsprechenden Strukturelementen vorgenommen. Die VEREINIGUNG sieht eine optionale Rauschbeseitigungsfilterung vor, wobei die VEREINIGUNG einen Startpunkt vorsieht, von dem aus kurze Bildeinheitenmasken in einer darauffolgenden Startpunktfülloperation wie einer fillClip- Operation gefüllt werden können. Die VEREINIGUNG arbeitet auf allen im Bild verbleibenden Bildeinheiten (d. h. in diesem Fall nur auf den kurzen Bildeinheiten). Da die VEREINIGUNG der Erosionen unter Verwendung eines Satzes von Oberlängen entsprechenden Strukturelementen und eines Satzes von Unterlängen entsprechenden Strukturelementen vorgenommen wird, umfassen die gefüllten Bildeinheiten Oberlängen und/oder Unterlängen, d. h. es handelt sich um Funktionswörter. Die Funktionswörter werden dann als diejenigen Bildeinheiten identifiziert, die gefüllte kurze Bildeinheitenmasken sind.

Als nächstes werden in Schritt 40 ausgewählte Bildeinheiten, z. B. die nicht in Schritt 30 unterschiedenen Bildeinheiten, ohne Decodierung der klassifizierten Bildeinheiten oder Bezugnahme auf decodierte Bilddaten auf der Basis einer Bewertung von vorbestimmten Bildformeigenschaften der Bildeinheiten bewertet. Die Bewertung umfaßt eine Bestimmung (Schritt 41) der Bildformeigenschaften und einen Vergleich (Schritt 42) der bestimmten Bildformeigenschaften für jede Bildeinheit mit den bestimmten Bildformeigenschaften der anderen Bildeinheiten.

In einer bevorzugten Ausführungsform wird wenigstens ein eindimensionales Signal abgeleitet, das die Form einer Worteinheit kennzeichnet, oder es wird eine Bildfunktion abgeleitet, die eine die Worteinheit einschließende Grenze definiert, wobei die Bildfunktion erweitert wird, so daß eine Kantenfunktion, welche die Kanten der innerhalb der Grenze festgestellten Zeichenkette wiedergibt, über die gesamte Domäne durch eine einzige unabhängige Variable innerhalb der geschlossenen Grenze definiert wird, ohne daß das Zeichen oder die Zeichen der Worteinheit einzeln festgestellt und/oder identifiziert werden.

Die abgeleitete Bildeinheitformwiedergaben der ausgewählten Bildeinheiten werden wie oben bemerkt mit den abgeleiteten Bildeinheitformwiedergaben der anderen ausgewählten Bildeinheiten verglichen (Schritt 41), um Äquivalenzklassen der Bildeinheiten zu identifizieren (Schritt 50), so daß jede Äquivalenzklasse die meisten oder alle Instanzen eines bestimmten Wortes im Dokument enthält. Die Äquivalenzklassen werden auf diese Weise durch das Clustern der Bildeinheiten im Dokument auf der Basis der Ähnlichkeit der Bildeinheitenklassifikatoren gebildet, ohne tatsächlich die Inhalte der Bildeinheiten zu decodieren, wie etwa durch die Umwandlung der Wortbilder zu Zeichencodes oder zu einer anderen Interpretation auf einer höheren Ebene. Es können auch andere Vergleichsverfahren verwendet werden. Eine Technik, die zum Beispiel verwendet werden kann, besteht darin, die Rasterbilder der extrahierten Bildeinheiten unter Verwendung von Entscheidungsnetzen zu korrelieren. Eine derartige Technik ist für Zeichen in einem Forschungsbericht mit dem Titel "Unsupervised Construction of Decision Networks for Pattern Classification" von Casey et al. in IBM Research Report, 1984 beschrieben, der hier unter Bezugnahme eingeschlossen ist.

Je nach der besonderen Anwendung und der relativen Wichtigkeit der Verarbeitungsgeschwindigkeit gegenüber der Genauigkeit können Vergleiche mit verschiedenen Präzisionsgraden durchgeführt werden. Zum Beispiel können nützliche Vergleiche auf der Länge, der Breite oder einer anderen Meßdimension der Bildeinheit (oder auf einer abgeleiteten Bildeinheitformwiedergabe von zum Beispiel der größten Figur in einem Dokumentbild), dem Font, dem Schriftschnitt, dem Querschnitt (ein Querschnitt ist eine Sequenz von Pixeln mit einem ähnlichen Zustand in einer Bildeinheit), der Anzahl der Oberlängen, der Anzahl der Unterlängen, der durchschnittlichen Pixeldichte, der Länge einer oberen Linienkontur einschließlich von Gipfeln und Tälern, der Länge einer Basiskontur einschließlich von Gipfeln und Tälern sowie auf einer Kombination derartiger Klassifikatoren basieren.

Wenn Dokumente mit mehreren Seiten verarbeitet werden, wird jede Seite verarbeitet und werden die Daten wie oben genannt im Speicher 15 (siehe Fig. 1) gespeichert. Dann kann die Gesamtheit der Daten verarbeitet werden.

Eine Möglichkeit zum bequemen Vergleichen und Klassifizieren der Bildeinheiten in Äquivalenzklassen besteht darin, jede Bildeinheit oder Bildeinheitformwiedergabe bei der Bildung mit den zuvor verarbeiteten Bildeinheiten/Formwiedergaben zu vergleichen, wobei bei einer Übereinstimmung die assoziierte Bildeinheit mit der entsprechenden Äquvialenzklasse identifiziert wird. Dies kann zum Beispiel vorgenommen werden, indem ein Signal vorgesehen wird, das eine Übereinstimmung angibt, und indem ein Zähler oder ein mit der übereinstim menden Äquivalenzklasse assoziiertes Register inkrementiert wird. Wenn die aktuelle Bildeinheit mit keiner zuvor verarbeiteten Bildeinheit übereinstimmt, wird eine neue Äquivalenzklasse für die aktuelle Bildeinheit erzeugt.

Alternativ dazu können die Bildeinheiten wie gezeigt (Schritt 50) in jeder Äquivalenzklasse miteinander verknüpft werden und auf ein Äquivalenzklassen-Etikett gemappt werden, das für jede Äquivalenzklasse bestimmt wird. Die Anzahl der Einträge für jede Äquivalenzklasse kann dann einfach gezählt werden.

Nachdem auf diese Weise das gesamte Dokumentbild oder ein interessanter Teil derselben verarbeitet wird, wird eine Anzahl von Äquivalenzklassen mit jeweils einer assoziierten Zahl identifiziert, welche die Häufigkeit angibt, mit der eine Bildeinheit mit ähnlichen Formeigenschaften oder Klassifikatoren identifiziert wurde, wodurch die Bildeinheitfrequenz bestimmt wird.

Ein durch die Technik der vorliegenden Erfindung vorgesehenes wichtiges Merkmal ist die Verarbeitung, die Identifikation, der Vergleich oder die Manipulation von Bildeinheiten ohne daß dafür der Inhalt der Bildeinheiten decodiert werden muß. Eine Decodierung ist auch für die Ausgabe nicht erforderlich. Insbesondere werden Bildeinheiten ohne Decodierung bestimmt, verarbeitet und für die Ausgabe ausgegeben, so daß im Grunde der tatsächliche Inhalt der Bildeinheiten zu keinem Zeitpunkt bestimmt zu werden braucht. Bei Anwendungen wie Kopiergeräten oder elektronischen Druckern, die Bilder direkt von einem Dokument auf ein anderes drucken oder reproduzieren können, ohne ASCII oder andere Codierungs- /Decodierungsanforderungen zu berücksichtigen, können auf diese Weise Bildeinheiten identifiziert und unter Verwendung von einer oder mehreren morphologischen Eigenschaften der Bildeinheit verarbeitet werden. Bei dem beschriebenen Vergleichsprozeß wird zum Beispiel jede Bildeinheit mit nicht bestimmten Inhalt im Bereich des interessanten Dokumentbildes mit anderen Bildeinheiten mit ebenfalls nicht bestimmten Inhalt im Dokument verglichen. Ausgewählte Bildeinheiten mit immer noch nicht bestimmten Inhalt können dann optisch oder elektronisch für die Ausgabe zum Beispiel zu einer Bildreproduktionsvorrichtung eines Kopiergerätes, zu einem elektronischen Speicher, einer visuellen Anzeige oder ähnlichem ausgegeben werden, um zum Beispiel eine Liste von signifikanten "Wörtern" oder Bildeinheiten in der Reihenfolge der Frequenz ihres Auftretens im Dokumentbild zu erzeugen.

Die oben beschriebene Technik kann verwendet werden, um die Signifikanz der Bildeinheiten eines Dokuments auf der Basis der Frequenz des Auftretens einer bestimmten Bild einheit zu bestimmen. Auf diese Weise kann zum Beispiel die Häufigkeit des Auftretens einer Bildeinheit in seiner entsprechenden Äquivalenzklasse verwendet werden, um eine Hierarchie von Wörtern zu erstellen, wobei eine derartige Hierarchie in vielfältigerweise nützlich sein kann, wie zum Beispiel um Dokumentzusammenfassungen und -kommentierungen zu erstellen. Dabei ist jedoch zu beachten, daß die Klassifikatoren bestimmt werden, ohne daß dafür der Inhalt der Bildeinheit decodiert wird; nur die ausgewählten Klassifikatoren der Bildeinheit selbst werden verwendet. Dieses Verfahren kann natürlich in ähnlicher Weise wie oben beschrieben auf Dokumente mit einer Länge von mehreren Seiten angewendet werden.

Die vorliegende Erfindung wurde in Bezug auf bestimmte Anwendungen beschrieben, wobei jedoch zu beachten ist, daß die vorliegende Beschreibung nur beispielhaft ist und daß zahlreiche Änderungen in der Kombination und der Anordnung der Teile durch den Fachmann vorgenommen werden können, ohne daß dadurch von dem im folgenden definierten Erfindungsumfang abgewichen wird.


Anspruch[de]

1. Verfahren zum Bestimmen der Frequenz von Wortbildeinheiten in einem elektronischen Dokument, das ein oder mehrere Bilder umfaßt, wobei das Verfahren durch folgende Schritte gekennzeichnet ist:

(A) Segmentieren des einen bzw. der mehreren Bilder in Wortbildeinheiten, ohne den Bildinhalt zu decodieren,

(B) Bestimmen von wenigstens einer Formeigenschaft für jeden aus dem Satz von Wortbildeinheiten in dem einen bzw. den mehreren Bildern, ohne die Wortbildeinheiten zu decodieren,

(C) Identifizieren von Äquivalenzklassen in dem Satz von Wortbildeinheiten durch das Clustern von Wortbildeinheiten mit ähnlichen Formeigenschaften, und

(D) Bestimmen der Anzahl von Wortbildeinheiten in jeder Äquivalenzklasse.

2. Verfahren nach Anspruch 1, wobei (C) das Korrelieren von Wortbildeinheit-Formeigenschaften unter Verwendung eines Entscheidungsnetzes umfaßt.

3. Verfahren nach Anspruch 1 oder 2, wobei (C) das Vergleichen von Wortbildeinheit- Formeigenschaften umfaßt.

4. Verfahren nach wenigstens einem der vorstehenden Ansprüche, wobei (A) das Ableiten einer Begrenzungsbox, die eine Wortbildeinheit einschließt, umfaßt, ohne das Zeichen bzw. die Zeichen der Wortbildeinheit individuell festzustellen und/oder zu identifizieren.

5. Verfahren nach wenigstens einem der vorstehenden Ansprüche, wobei (D) die folgenden Schritte umfaßt:

Verknüpfen der Wortbildeinheiten in jeder Äquivalenzklasse miteinander, und

Zählen der Anzahl der verknüpften Wortbildeinheiten für jede Äquivalenzklasse.

6. Verfahren nach Anspruch 5, wobei der Schritt zum Verknüpfen der Wortbildeinheiten miteinander umfaßt:

Bestimmen eines Äquivalenzklassen-Etiketts für jede Wortbildeinheit, und Mappen jeder Wortbildeinheit auf das bestimmte Äquivalenzklassen-Etikett.

7. Verfahren nach wenigstens einem der vorstehenden Ansprüche, wobei die Formeigenschaften wenigstens die Abmessungen der Bildeinheit, die Anzahl der Oberlängen, die Anzahl der Unterlängen und/oder die Kontureigenschaften der Wortbildeinheit umfassen.

8. Verfahren nach wenigstens einem der vorstehenden Ansprüche, wobei (A), (B), (C) und (D) durch das Betreiben eines programmierten digitalen Computers durchgeführt werden.

9. Vorrichtung zum Bestimmen der Frequenz von Wortbildeinheiten in einem elektronischen Dokument, das ein oder mehrere Bilder umfaßt, gekennzeichnet durch:

eine Segmentierungseinrichtung (16, 20) zum Segmentieren des einen oder der mehreren Bilder in Wortbildeinheiten, ohne den Inhalt zu decodieren,

eine Bestimmungseinrichtung (16, 41) zum Bestimmen von wenigstens einer Formeigenschaft für jede aus dem Satz von Wortbildeinheiten in dem einen oder den mehreren Bildern, ohne die Wortbildeinheiten zu decodieren,

eine Identifikationseinrichtung (16, 50) zum Identifizieren von Äquivalenzklassen in dem Satz von Wortbildeinheiten durch das Clustern von Wortbildeinheiten mit ähnlichen Formeigenschaften, und

eine Bestimmungseinrichtung (16) zum Bestimmen der Anzahl der Wortbildeinheiten in jeder Äquivalenzklasse.

10. Vorrichtung nach Anspruch 9, wobei die Bestimmungseinrichtung (16) eine Frequenz für jede Äquivalenzklasse bestimmt, wobei die Vorrichtung weiterhin eine Ausgabeeinrich tung (17) zum Erzeugen einer Ausgabe in Antwort auf die Frequenzen der Äquivalenzklassen umfaßt.







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

  Patente PDF

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