PatentDe  


Dokumentenidentifikation DE69229537T2 25.11.1999
EP-Veröffentlichungsnummer 0544432
Titel Verfahren und Gerät zur Dokumentverarbeitung
Anmelder Xerox Corp., Rochester, N.Y., US
Erfinder Withgott, Margaret M., Los Altos, California 94022, US;
Huttenlocher, Daniel P., Ithaca, New York 14850, US;
Bagley, Steven C., Palo Alto, California 94301, US;
Halvorsen, Per Kristian, Los Altos, California 94022, US;
Bloomberg, Dan S., Palo Alto, California 94306, US;
Kaplan, Ronald M., Palo Alto, California 94306, US;
Cass, Todd A., Cambridge, Massachusetts 02138, US;
Rao, Ramana R., San Francisco, California 94112, US
Vertreter Grünecker, Kinkeldey, Stockmair & Schwanhäusser, Anwaltssozietät, 80538 München
DE-Aktenzeichen 69229537
Vertragsstaaten DE, FR, GB
Sprache des Dokument En
EP-Anmeldetag 16.11.1992
EP-Aktenzeichen 923104335
EP-Offenlegungsdatum 02.06.1993
EP date of grant 07.07.1999
Veröffentlichungstag im Patentblatt 25.11.1999
IPC-Hauptklasse G06K 9/00

Beschreibung[de]

Die vorliegende Erfindung betrifft Verfahren und Vorrichtungen zur automatischen Dokumentverarbeitung und insbesondere Verbesserungen von Verfahren und Vorrichtungen zum Erkennen von semantisch signifikanten Wortbildeinheiten in einem Dokumentbild ohne vorhergehendes Decodieren des Dokumentbildes sowie zum automatischen Erzeugen einer Zusammenfassung des Dokumentinhalts.

Es ist seit langem ein Ziel der computerunterstützten elektronischen Dokumentverarbeitung, einfach und verläßlich auf Information in elektronisch decodierten Daten, die Dokumente wiedergeben, zugreifen und dieselbe extrahieren zu können. Weiterhin ist es ein Ziel der computerunterstützten Dokumentverarbeitung, die in einem gespeicherten Dokument oder einem gespeicherten Dokumentencorpus enthaltene Information zusammenzufassen und zu charakterisieren. Um zum Beispiel das Durchsehen und Bewerten des Informationsinhalts eines Dokuments oder eines Dokumentcorpus zu vereinfachen, um die Relevanz desselben mit Bezug auf die Bedürfnisse eines bestimmten Benutzers zu bestimmen, wäre es vorteilhaft, wenn man den Informationsinhalt der semantisch signifikantesten Teile eines Dokuments identifizieren könnte. Es wäre auch vorteilhaft, den Informationsinhalt dieser Teile derart darstellen zu können, daß der Benutzer die Informationsinhalte erkennen und bewerten kann. Das Problem des Identifizierens der signifikanten Teile in einem Dokument ist größer, wenn es sich um Bilder der Dokumente (Bitmap-Bilddaten) handelt als wenn es sich um Codewiedergaben derselben (z. B. Codewiedergaben von Text, wie etwa ASCII) handelt. Im Gegensatz zu ASCII-Textdateien, bei denen der Benutzer Operationen wie Boolesche Stichwortsuchen vornehmen kann, um interessanten Text aufzufinden, sind elektronische Dokumente, die durch das Scannen eines Originals ohne Decodierung für die Erzeugung von Dokumentbildern erstellt wurden, schwierig zu bewerten, ohne daß jedes Dokumentbild eigens betrachtet wird oder ohne daß eine per Hand erstellte Zusammenfassung des Dokumentes erstellt wird. Natürlich erfordert das Durchsehen des Dokuments oder das Erstellen einer Zusammenfassung für das Dokument extensive menschliche Arbeit.

Andererseits umfassen gegenwärtige Bilderkennungsverfahren, insbesondere bei Textmaterial, allgemein das Aufteilen eines Bildsegments, damit es in einzelne Zeichen analysiert werden kann, die dann entziffert oder decodiert und mit Zeichen in einer Zeichenbibliothek verglichen werden. Eine Klasse von derartigen Verfahren umfaßt optische Zeichenerkennungs-(OCR)-Techniken. Typischerweise können OCR-Techniken ein Wort erst dann erkennen, wenn alle einzelnen Zeichen des Wortes decodiert wurden und ein entsprechendes Wortbild aus einer Bibliothek abgerufen wurde.

Weiterhin erfordern die Decodierungsoperationen der optischen Zeichenerkennung allgemein extensive Berechnungsarbeit, wobei allgemein ein nicht unbeträchtlicher Anteil von Erkennungsfehlern erzeugt wird und wobei die Bildverarbeitung häufig einen beträchtlichen Zeitaufwand erfordert, insbesondere bei der Wortverarbeitung. Jede Bitmap eines Zeichens muß von ihren Nachbarn unterschieden werden; dann muß das Aussehen des Zeichens analysiert werden und in einem Entscheidungsprozeß als ein bestimmtes Zeichen in einem vorbestimmten Satz von Zeichen identifiziert werden. Weiterhin tragen die Bildqualität des Originaldokuments und das in der Erzeugung eines gescannten Bildes inhärente Rauschen zu der Unsicherheit bezüglich des tatsächlichen Aussehens der Bitmap für ein Zeichen bei. Die meisten Zeichenerkennungsprozesse nehmen an, daß ein Zeichen ein unabhängiger Satz von zusammenhängenden Pixeln ist. Wenn diese Annahme wegen der Qualität des Bildes nicht zutrifft, ist keine Erkennung möglich.

EP-A-0-361-464 beschreibt ein Verfahren und eine Vorrichtung zum Erzeugen einer Zusammenfassung eines Dokuments, wobei der korrekte Bedeutungsinhalt des Dokumentes präzise angegeben wird. Das Verfahren umfaßt das Auflisten von Hinweiswörtern, d. h. von vorbestimmten Wörtern, die das Vorhandensein von signifikanten Phrasen angeben, die über den Inhalt des Dokuments Aufschluß geben können, wobei alle Hinweiswörter im Dokument gesucht werden und wobei Sätze des Dokumentes extrahiert werden, in denen eines der aufgelisteten Hinweiswörter durch die Suche gefunden wurde. Weiterhin kann eine Zusammenfassung des Dokuments durch die Aneinanderreihung der extrahierten Sätze erstellt werden. Wenn die Anzahl der Hinweiswörter ein langes Exzerpt erzeugt, wird eine morphologische Sprachanalyse der Sätze in der Zusammenfassung vorgenommen, um unnötige Phrasen zu beseitigen und nur die Phrasen zu extrahieren, die die Hinweiswörter in der richtigen Wortart verwenden, wobei auf ein die Hinweiswörter enthaltendes Wörterbuch Bezug genommen wird.

Luhn beschreibt in "A Business Intelligence System", IBM Journal, October 1958 ein System, das ein Dokument teilweise automatisch zusammenfaßt, indem es die am häufigsten auftretenden (die signifikanten) Wörter feststellt und alle Sätze im Text analysiert, die diese Wörter enthalten. Ein Relativwert der Satzsignifikanz wird dann durch eine Formel erstellt, die die Anzahl der in einem Satz enthaltenen signifikanten Wörter und die Nähe der Wörter zueinander im Satz wiedergibt. Dann werden mehrere der Sätze mit den höchsten Signifikanzgraden aus dem Text extrahiert, um automatisch eine Zusammenfassung zu erstellen.

D. S. Bloomberg gibt in "Multiresolution morphological approach to document image analysis" in FIRST INTERNATIONAL CONFERENCE ON DOCUMENT ANALYSIS AND RECOGNITON IDCAR 91, 30 September-2 October 1991, San Malo, FR, pp. 963-971 morphologische Operationen zum Durchführen einer Dokumentbildanalyse an. Es werden zum Beispiel Techniken zum Identifizieren von kursiv und fett dargestellten Wörtern in einem Text unter Verwendung eines Extrahierens auf der Wortebene mit reduzierter Auflösung angegeben.

M. Hase et al. geben in "A method for extracting marked regions from document images" in SYSTEMS & COMPUTERS IN JAPAN, vol. 18, no. 8, 1987, NEW YORK, US, pp. 77-87 Techniken zum Extrahieren von markierten Bereichen aus Originaldokumenten an. Der Benutzer kann einen Bereich unter Verwendung eines Filzstiftes mit einer farbigen Markierung oder mit einer Kreismarkierung angeben.

PATENT ABSTRACTS OF JAPAN, vol. 014, no. 298 (P-1068), 27 June 1990 beschreibt JP- A-02 093 866 und gibt eine Technik zum Extrahieren eines Satzes, der ein Stichwort enthält, und zum Erzeugen eines zusammenfassenden Satzes an. Der Satz wird aus den Dokumentdaten extrahiert.

FR-A-2 453 451 gibt ein Lesegerät für Blinde an. Das Gerät umfaßt eine optoelektronische Kamera, eine Logikeinheit und eine Ausgabeeinheit, die ASCII zu Braille umwandelt. Die Kamera weist eine Öffnung und zwei Walzen in der Nähe der Öffnung auf, um eine regelmäßige geradlinige manuelle Bewegung über ein Papier mit einem zu lesenden Text zu ermöglichen.

In Übereinstimmung mit einem Aspekt der vorliegenden Erfindung ist ein Verfahren zum elektronischen Verarbeiten eines elektronischen Dokumentbildes angegeben, wobei das Verfahren folgende Schritte umfaßt:

(A) Segmentieren des Dokumentbildes in Wortbildeinheiten, ohne das Dokumentbild zu decodieren, und

(B) Identifizieren eines Satzes von Wortbildeinheiten für die weitere Verarbeitung auf der Basis von Bildeinheit-Eigenschaften, ohne die Wortbildeinheiten zu decodieren,

dadurch gekennzeichnet, daß

die Bildeinheit-Eigenschaften eine Formwiedergabe einer Bildeinheit sind,

wobei (B) umfaßt:

(B1) Vergleichen der Bildeinheit-Formwiedergaben der aus dem Dokumentbild segmentierten Wortbildeinheiten miteinander oder mit vorbestimmten oder benutzerbestimmten Auswahlkriterien, um den Satz von Wortbildeinheiten zu identifizieren.

In Übereinstimmung mit einem anderen Aspekt der vorliegenden Erfindung ist eine Vorrichtung zum elektronischen Verarbeiten eines elektronischen Dokumentbildes angegeben, wobei die Vorrichtung umfaßt:

eine Segmentierungseinrichtung zum Segmentieren des Dokumentbildes in Wortbildeinheiten, ohne das Dokumentbild zu decodieren, und

eine Identifizierungseinrichtung zum Identifizieren eines Satzes von Wortbildeinheiten für die weitere Verarbeitung auf der Basis von Bildeinheit-Eigenschaften, ohne die Wortbildeinheiten zu decodieren,

dadurch gekennzeichnet, daß

die Bildeinheit-Eigenschaften die Formwiedergabe einer Bildeinheit sind,

wobei die Identifizierungseinrichtung umfaßt:

eine Vergleichseinrichtung zum Vergleichen der Bildeinheit-Formwiedergaben der aus dem Dokumentbild segmentierten Wortbildeinheiten miteinander oder mit vorbestimmten oder benutzerbestimmten Auswahlkriterien, um den Satz von Wortbildeinheiten zu identifizieren.

Die durch Ausführungsformen der vorliegenden Erfindung ermöglichten Vorteile umfassen ein Verfahren und eine Vorrichtung zum automatischen Erzeugen von Hilfsdokumentbildern, die den Inhalt eines gesamten Primärdokumentbildes angeben, ein Verfahren und eine Vorrichtung des oben beschriebenen Typs zum automatischen Extrahieren von Zusammenfassungen von Material und zum Vorsehen von Verknüpfungen von der Zusammenfassung zurück zum Originaldokument, sowie ein Verfahren und eine Vorrichtung des oben beschrie benen Typs zum Erzeugen von Zusammenfassungen eines Dokuments in Braille oder von sprachsynthetisierten Zusammenfassungen eines Dokuments.

Weitere durch Ausführungsformen der vorliegenden Erfindung ermöglichte Vorteile umfassen ein Verfahren und eine Vorrichtung des oben beschriebenen Typs, die durch das Vorsehen von Bildextrakten ein Durchsehen des Dokuments oder durch die Verwendung von lexikalischen Extrakten eine Kategorisierung des Dokuments erlauben, sowie ein Verfahren und eine Vorrichtung des oben beschriebenen Typs, die nicht von statistischen Eigenschaften großer, voranalysierter Dokumentcorpora abhängig sind.

Im folgenden wird eine bevorzugte Ausführungsform der vorliegenden Erfindung mit Bezug auf die beigefügten Zeichnungen beschrieben. Es zeigen:

Fig. 1 ein Flußdiagramm des Verfahrens der vorliegenden Erfindung, und

Fig. 2 ein Blockdiagramm einer Vorrichtung in Übereinstimmung mit der vorliegenden Erfindung zum Ausführen des Verfahrens von Fig. 1.

Im Gegensatz zu Techniken aus dem Stand der Technik wie den oben beschriebenen, beruht die vorliegende Erfindung auf der Erkenntnis, daß sich gescannte Bilddateien und Zeichencodedateien wesentlich in bezug auf die Bildverarbeitung und insbesondere die Datenwiedergewinnung unterscheiden. Das Verfahren einer bevorzugten Ausführungsform der vorliegenden Erfindung nutzt die sichtbaren Eigenschaften von in Papierdokumenten enthaltenem Text, etwa das Vorhandensein oder die Häufigkeit von linguistischen Einheiten (etwa von Wörtern, die Signifikanz angeben, wie zum z. B. "wichtig", "ausschlaggebend" oder ähnlichen), die durch den Autor verwendet werden, um auf eine bestimmte Phrase oder einen bestimmten Teil des Textes aufmerksam zu machen. Eine bevorzugte Ausführungsform des Verfahrens ist in dem Flußdiagramm von Fig. 1 gezeigt, und eine Vorrichtung zum Ausführen des Verfahrens ist in Fig. 2 gezeigt. Der Einfachheit halber wird die vorliegende Erfindung in bezug auf die Verarbeitung eines einzelnen Dokuments beschrieben. Es ist jedoch zu beachten, daß die vorliegende Erfindung für die Verarbeitung eines Dokumentencorpus mit einer Vielzahl von Dokumenten verwendet werden kann. Insbesondere sieht die vorliegende Erfindung ein Verfahren und eine Vorrichtung zum automatischen Exzerpieren von semantisch signifikanter Information aus den Daten oder dem Text eines Dokuments auf der Basis bestimmter Bildformeigenschaften von Bildeinheiten vor, die im Dokumentbild enthaltenen Inhaltseinheiten entsprechen. Die exzerpierte Information kann unter anderem zum automatischen Erzeugen eines Dokumentindex oder einer Zusammenfassung verwendet werden. Die Auswahl der Bildeinheiten für die Zusammenfassung kann in Abhängigkeit von der bestimmten Anwendung des Verfahrens und der Vorrichtung der vorliegenden Erfindung auf der Basis der Häufigkeit des Auftretens oder auf der Basis von vorbestimmten oder benutzerbestimmten Auswahlkriterien vorgenommen werden.

Die vorliegende Erfindung ist nicht auf Systeme beschränkt, die ein Dokumentscannen verwenden. Ebenso gut können andere Systeme wie eine Bitmap-Workstation (d. h. eine Workstation mit einer Bitmap-Anzeige) oder ein System, das sowohl ein Bitmapping wie ein Scannen verwendet, für die Implementierung der hier beschriebenen Verfahren und Vorrichtungen verwendet werden.

Im folgenden wird auf Fig. 2 Bezug genommen. Das Verfahren wird auf einem elektronischen Bild eines Originaldokuments durchgeführt, das Textzeilen, Titel, Zeichnungen, Figuren oder ähnliches auf einer oder mehreren Papierseiten 10 oder in anderer greifbarer Form enthalten kann. Das zu verarbeitende elektronische Dokumentbild wird auf herkömmliche Weise zum Beispiel durch eine herkömmliche Scaneinrichtung 12, wie sie in einem Dokumentkopiergerät, einem Faxgerät oder einem Braille-Lesegerät enthalten ist, oder aber durch einen elektronischen Strahlscanner oder ähnliches erzeugt. Eine derartige Scaneinrichtung ist aus dem Stand der Technik bekannt und wird deshalb hier nicht beschrieben. Eine durch das Scannen erhaltene Ausgabe wird digitalisiert, um nicht decodierte Bitmap- Bilddaten zu erzeugen, die das Dokumentbild für jede Seite des Dokuments wiedergeben, wobei die Daten zum Beispiel in einem Speicher 15 eines speziellen oder allgemeinen digitalen Computer-Datenverarbeitungssystems 13 gespeichert werden. Das Datenverarbeitungssystem 13 kann ein durch Daten betriebenes Verarbeitungssystem sein, das eine sequentielle Verarbeitungseinrichtung 16 zum Durchführen von Funktionen von Ausführungsprogrammbefehlen in einer vorbestimmten Sequenz umfaßt, die in einem Speicher wie dem Speicher 15 gespeichert sind. Die Ausgabe aus dem Datenverarbeitungssystem 13 wird zu einem Ausgabegerät 17 wie zum Beispiel zu einem Speicher oder einer andersartigen Speichereinheit, zu einer Ausgabeanzeige 17A, die wie gezeigt zum Beispiel eine CRT-Anzeige sein kann, zu einer Druckereinrichtung 17B, die in einem Dokumentkopiergerät oder in einem Braille-Standardformdrucker enthalten sein kann, zu einem Faxgerät, zu einem Sprachsynthesizer oder zu einer ähnlichen Einrichtung gegeben.

Unter Verwendung der in Fig. 2 gezeigten Ausstattung werden die identifizierten Worteinheiten auf der Basis der in den Bildeinheiten inhärenten signifikanten Bildformeigenschaften festgestellt, ohne daß das gescannte Dokumentbild zuerst zu Zeichencodes umgewandelt wird.

Das Verfahren zum Durchführen einer derartigen Bildeinheit-Identifizierung wird im folgenden mit Bezug auf Fig. 1 beschrieben. Die erste Phase der Bildverarbeitungstechnik der vorliegenden Erfindung umfaßt eine Dokumentbildanalyse der niedrigeren Ebene, in der das Dokumentbild für jede Seite unter Verwendung von herkömmlichen Bildanalysetechniken oder bei Textdokumenten vorzugsweise unter Verwendung des Begrenzungsbox-Verfahrens in nicht decodierte Information segmentiert wird, die Bildeinheiten enthält (Schritt 20). Dann werden die Positionen und die räumlichen Beziehungen zwischen den Bildeinheiten auf einer Seite bestimmt (Schritt 25). Zum Beispiel kann ein englischsprachiges Dokumentbild auf der Basis der relativen Differenz zwischen den Abständen zwischen Zeichen in einem Wort und den Abständen zwischen Wörtern in Wortbildeinheiten segmentiert werden. Satz- und Absatzgrenzen können auf ähnliche Weise bestimmt werden. Eine zusätzliche Bereichsegmentierung-Bildanalyse kann durchgeführt werden, um eine physikalische Strukturbeschreibung zu erzeugen, die Seitenbilder in etikettierte Bereiche unterteilt, die Hilfsdokumentelementen wie Zeichnungen, Tabellen, Fußnoten und ähnlichem entsprechen. Zeichnungsbereiche können von Textbereichen zum Beispiel auf der Basis der relativen Fehlens von in einer Zeile angeordneten Bildeinheiten im Bereich bestimmt werden. Unter Verwendung dieser Segmentierung kann Wissen über die Anordnung der verarbeiteten Dokumente gesammelt werden (zum Beispiel links-rechts, oben-unten), wobei optional auch andere eingegebene Information wie der Dokumentstil und eine "Lesereihenfolge" für die Wortbilder erzeugt werden kann. Der Ausdruck "Bildeinheit" wird hier verwendet, um ein identifizierbares Segment eines Bildes wie eine Zahl, einen Buchstaben, einen Glyphen, ein Symbol, ein Wort, eine Phrase oder eine andere Einheit zu bezeichnen, das verläßlich extrahiert werden kann. Für das Durchsehen und Bewerten des Dokuments wird das Dokumentbild in Sätze von Zeichen, Symbolen oder anderen Elementen wie Wörtern unterteilt, die zusammen eine einzelne Inhaltseinheit bilden. Derartige einzelne Inhaltseinheiten sind in einem Bild allgemein durch einen Abstand voneinander getrennt, der größer ist als der Abstand, der die Elemente innerhalb einer Einheit voneinander trennt. Es kann aber auch eine vorbestimmte graphische Hervorhebung wie etwa eine Umgebungsbox oder ein anderes graphisches Trennelement verwendet werden, das eine oder mehrere Bildeinheiten von anderen Bildeinheiten in dem gescannten Dokumentbild unterscheidet. Derartige Bildeinheiten stellen einzelne Inhaltseinheiten dar, die im folgenden als "Worteinheiten" bezeichnet werden.

In vorteilhafter Weise wird als nächstes ein Unterscheidungsschritt 30 durchgeführt, um die Bildeinheiten zu identifizieren, die einen Informationsinhalt aufweisen, der nicht ausreicht, um für die Bewertung des Inhalts des verarbeiteten Dokuments nützlich zu sein. Ein be vorzugtes Verfahren besteht darin, eine morphologische Funktion oder Stoppwort-Feststellungstechniken zu verwenden. In diesem Verfahren werden zuerst die Länge und Höhe der Bildeinheiten im Bild bestimmt, wobei Bildeinheiten als kurze Bildeinheiten identifiziert werden, wenn sie nicht mehr als eine vorbestimmte Anzahl von Zeichen umfassen, vorzugsweise drei Zeichen oder weniger. 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 oder verwischt, wobei die Bildeinheiten jedoch nicht ineinander gewischt werden. Dies kann zum Beispiel durch das Schließen 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 einer Höhe x im Bild verwendet wird, ist von der Breite der verwendeten Schriftart abhängig. Es können auch andere Konfigurationen von Strukturelementen in der Schließen-Operation verwendet werden, um denselben Verwischungseffekt zu erreichen. Die effizienteste und einfachste Möglichkeit zum Verwischen von Zeichen mit einer Höhe x besteht jedoch in der oben angegebenen Verwendung eines horizontalen Strukturelements.

Eine Vereinigung von Erosionen wird dann im Bild vorgenommen, wobei ein Satz von Strukturelementen für die Oberlängen und ein Satz von Strukturelementen für die Unterlängen verwendet wird. Die Vereinigung sieht ein optionales Rauschbeseitigungs-Filtern vor, wobei die Vereinigung einen Startpunkt vorsieht, von dem aus die kurzen Bildeinheiten- Masken in einer darauffolgenden Fülloperation wie etwa einer fillClip-Operation gefüllt werden. Die Vereinigung operiert auf allen im Bild verbleibenden Bildeinheiten (d. h. in diesem Fall nur auf den kurzen Bildeinheiten). Weil die Vereinigung der Erosionen unter Verwendung eines Satzes von Strukturelementen für die Oberlängen und eines Satzes von Strukturelementen für die Unterlängen durchgeführt wurde, sind die Bildeinheiten, die gefüllt werden, diejenigen Bildeinheiten, die Zeichen mit Oberlängen und/oder Unterlängen umfassen, d. h. Funktionswörter. Als Funktionswörter werden diejenigen Bildeinheiten identifiziert, die gefüllte kurze Bildeinheit-Masken sind.

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

Ein bevorzugtes Verfahren zum Definieren der zu bewertenden Bildeinheit-Formeigenschaften besteht darin, Wortform-Ableitungstechniken zu verwenden. Dabei wird wenigstens ein eindimensionales Signal erhalten, das die Form einer Worteinheit kennzeichnet. Alternativ dazu kann eine Bildfunktion erhalten werden, die eine die Worteinheit umgebende Grenze definiert. Die Bildfunktion wird erweitert, um eine Bildfunktion zu bestimmen, die Kanten der innerhalb der Grenze festgestellten Zeichenkette wiedergibt. Die Kantenfunktion wird insgesamt durch eine einzige unabhängige Variable definiert, die die Bildeinheit-Formwiedergabe darstellt. Dadurch können Bildeinheiten festgestellt werden, ohne daß das Zeichen oder die Zeichen einer Worteinheit festgestellt und/oder identifiziert werden.

Die abgeleiteten Bildeinheit-Formwiedergaben jeder ausgewählten Bildeinheit werden wie oben genannt verglichen (Schritt 42), wobei sie entweder mit den abgeleiteten Bildeinheit- Formwiedergaben der anderen ausgewählten Bildeinheiten verglichen werden (Schritt 42A) oder mit vorbestimmten/benutzerbestimmten Bildformeigenschaften verglichen werden, um spezifische Typen von Bildeinheiten zu lokalisieren (Schritt 42B). Die bestimmten Bildformeigenschaften der ausgewählten Bildeinheiten werden in vorteilhafter Weise miteinander verglichen, um Äquivalenzklassen von Bildeinheiten zu definieren, so daß jede Äquivalenzklasse die meisten oder alle Instanzen einer bestimmten Bildeinheit im Dokument enthält, wobei die relative Häufigkeit des Auftretens jeder Bildeinheit im Dokument bestimmt werden kann. Die Bildeinheiten können dann in Übereinstimmung mit der Häufigkeit ihres Auftretens sowie in Übereinstimmung mit anderen Eigenschaften der Bildeinheiten wie etwa ihrer Länge als signifikant klassifiziert oder identifiziert werden. Es hat sich zum Beispiel herausgestellt, daß eine nützliche Kombination von Auswahlkriterien bei Geschäftskorrespondenz in Englisch darin besteht, die Worteinheiten mit mittlerer Frequenz auszuwählen.

Es ist zu beachten, daß der Auswahlprozeß auf Phrasen, die identifizierte signifikante Bildeinheiten umfassen, und auf benachbarte Bildeinheiten, die in einer Lesereihenfolge miteinander verknüpft sind, erweitert werden kann. Die Häufigkeit des Auftretens derartiger Phrasen kann auch derart bestimmt werden, daß die Teile des Quellendokuments, die für die Zusammenfassung ausgewählt werden, Phrasen sind, die einen vorbestimmten Häufigkeitsschwellwert von zum Beispiel fünf überschreiten.

Es ist zu beachten, daß die Spezifikation der Bildformeigenschaften für Titel, Überschriften, Bildbeschriftungen, linguistische Kriterien oder andere eine Signifikanz angebende Merkmale eines Dokumentbildes vorbestimmt und durch den Benutzer ausgewählt werden können, um die Auswahlkriterien zu bestimmen, die eine "signifikante" Bildeinheit definieren. Zum Beispiel sind Titel typischerweise mit einer größeren Schriftgröße dargestellt als der Haupttext. Das Vergleichen der Bildformeigenschaften der ausgewählten Bildeinheiten des Dokumentbildes, um Übereinstimmungen mit den Bildeigenschaften der Auswahlkriterien zu finden, oder das andersartige Erkennen der Bildeinheiten mit den spezifizierten Bildformeigenschaften ermöglicht es, die signifikanten Bildeinheiten einfach zu identifizieren, ohne das Dokument zu decodieren.

Es können verschiedene Techniken zum Vergleichen der Wortformen verwendet werden.

Je nach der besonderen Anwendung und der relativen Wichtigkeit der Verarbeitungsgeschwindigkeit gegenüber der Genauigkeit können zum Beispiel Vergleiche mit unterschiedlichem Genauigkeitsgrad durchgeführt werden. Nützliche Vergleiche können zum Beispiel auf der Basis der Länge, der Breite oder eines anderen Maßes der Bildeinheit (oder der abgeleiteten Bildeinheit-Formwiedergabe, z. B. der größten Zeichnung in einem Dokumentbild), der Anzahl der Oberlängen, der Anzahl der Unterlängen, der Länge der oberen Linienkontur, einschließlich von Gipfeln und Tälern, der Länge der Basiskontur, einschließlich von Gipfeln und Tälern, sowie auf der Basis einer Kombination der vorstehend genannten Klassifikatoren durchgeführt werden.

Ein wichtiges Merkmal des Verfahrens der vorliegenden Erfindung besteht darin, daß die anfängliche Verarbeitung und Identifikation von signifikanten Bildeinheiten bewerkstelligt wird, ohne daß der Inhalt der Bildeinheiten decodiert wird oder daß der Informationsinhalt des Dokumentbildes in anderer Weise bekannt sein muß. Insbesondere muß der tatsächliche Inhalt der Worteinheiten in dieser Phase des Verfahrens nicht bestimmt werden. Bei Anwendungen wie Kopiergeräten oder elektronischen Druckern, die Bilder direkt von einem Dokument ohne Verwendung von ASCII oder anderen Codierungs-/Decodierungsanforderungen drucken oder reproduzieren können, können deshalb Bildeinheiten auf der Basis von einer oder mehreren Bildformeigenschaften der Bildeinheiten identifiziert und bearbeitet werden. Die Bildeinheiten mit unbekanntem Inhalt können dann weiter optisch oder elektronisch verarbeitet werden. Einer der Vorteile einer Verarbeitung von Bildeinheiten ohne Decodierung der Inhalte der Bildeinheiten in dieser Phase des Verfahrens besteht darin, daß die Gesamtgeschwindigkeit der Bildhandhabung wesentlich erhöht werden kann.

Die zweite Phase der Dokumentanalyse der vorliegenden Erfindung beinhaltet die Verarbeitung (Schritt 50) der identifizierten signifikanten Bildeinheiten, um ein zusätzliches Hilfs dokument zu erzeugen, das den Inhalt des Quellendokumentbildes angibt. Es ist zu beachten, daß das Format, in dem die identifizierten signifikanten Bildeinheiten dargestellt werden, variieren kann. Die identifizierten signifikanten Bildeinheiten können in der Lesereihenfolge, um eine oder mehrere Phrasen wiederzugeben, oder in einer Listenreihenfolge der relativen Häufigkeit ihres Auftretens präsentiert werden. Entsprechend muß das Hilfsdokumentbild nicht ausschließlich auf die identifizierten signifikanten Bildeinheiten beschränkt sein. Wenn gewünscht, können die identifizierten signifikanten Bildeinheiten in der Form von Phrasen dargestellt werden, wobei benachbarte Bildeinheiten in der Lesereihenfolge dargestellt werden, die durch die während der oben beschriebenen Schritte 20 und 25 zur Segmentierung des Dokuments und zur Bestimmung der Struktur erhaltene Dokument-Positionsinformation angegeben wird. Alternativ dazu kann eine wie oben beschriebene Analyse der Häufigkeit von Phrasen durchgeführt werden, um die dargestellten Phrasen auf die am häufigsten vorkommenden zu beschränken.

Die vorliegende Erfindung ist weiterhin nicht bezüglich der Form des Hilfsdokumentbildes beschränkt. Die Technik zur Informationswiedergewinnung der vorliegenden Erfindung ist besonders gut für die Verwendung in Lesegeräten für Blinde geeignet. Eine Ausführungsform unterstützt die Angabe von Stichwörtern durch einen Benutzer, zum Beispiel in einer Stichwortliste, um wahrscheinliche Interessenpunkte in einem Dokument anzugeben. Unter Verwendung der angegebenen Stichwörter kann das Auftreten des Wortes in dem interessanten Dokument gefunden werden, wobei Textbereiche vor und hinter dem Stichwort abgerufen und unter Verwendung der oben beschriebenen Techniken verarbeitet werden können. Die signifikanten Stichwörter können jedoch auch automatisch in Übereinstimmung mit vorgeschriebenen Kriterien wie etwa der Häufigkeit ihres Auftretens oder ähnlichen Kriterien ausgewählt werden, wobei die oben beschriebenen morphologischen Bilderkennungstechniken verwendet werden; außerdem kann automatisch eine Zusammenfassung des Dokumentes unter Verwendung der bestimmten Wörter erstellt werden.

Eine andere Ausführungsform unterstützt das automatische Auffinden von signifikanten Segmenten eines Dokuments in Übereinstimmung mit anderen vordefinierten Kriterien, zum Beispiel von Dokumentsegmenten, die einen wahrscheinlich hohen Informationswert aufweisen, wie etwa Titel oder linguistisch betonte Phrasen. Das Auffinden der signifikanten Wörter oder Segmente eines Dokuments kann unter Verwendung der oben beschriebenen Bildform- Erkennungstechniken bewerkstelligt werden. Die auf diese Weise als signifikant identifizierten Wörter oder Worteinheiten können unter Verwendung von optischen Zeichenerkennungstechniken decodiert werden, um zum Beispiel für einen blinden Benutzer in Braille oder in einer anderen für denselben verständlichen Form ausgegeben zu werden. Zum Beispiel können die durch die oben beschrieben Techniken identifizierten oder ausgewählten Wörter entweder durch einen geeigneten Braille-Format-Drucker, etwa durch einen Drucker, der auf Kunststoff basierende Tinte verwendet, in Braille gedruckt oder durch eine Sprachsynthesizer-Ausgabeeinrichtung in der Form von gesprochener Sprache ausgegeben werden.

Wenn ein verdichtetes Dokument ausgegeben wird, kann der Benutzer zu der Originalquelle zurückkehren wollen, um diese auszudrucken oder eine Wiedergabe des gesamten Textes zu hören. Dies kann auf verschiedene Weise bewerkstelligt werden. Ein Verfahren besteht darin, daß der assoziierte Synthesizer oder Braille-Drucker etwa eine Quelleninformation der folgenden Form vorsieht: "oben auf Seite 2 befindet sich ein Artikel mit dem Titel ..." Der Benutzer kann dann auf diese interessante Stelle zugreifen.

Zwei Klassen von Vorrichtungen können diese Fähigkeit erweitern, indem sie eine Möglichkeit der Benutzerinteraktion währen der Ausgabe des verdichteten Dokuments vorsehen. Eine Vorrichtung ist ein einfacher Indexmarkierer. Dabei kann es sich zum Beispiel um eine in der Hand gehaltene Einrichtung mit einer Taste handeln, die der Benutzer drückt, wenn er oder sie einen interessanten Titel hört, wobei die Einrichtung ein N-Wege-Bewegungsdetektor in einer Maus 19 (Fig. 2) sein kann, der viele verschiedene Befehle annimmt. Das Lesegerät zeichnet die Interessemarkierungen auf und kehrt nach der Ausgabe der vollständigen Zusammenfassung zu dem Originalartikel zurück.

Ein anderer Typ von Vorrichtung verwendet die Berührungsbildschirm-Technologie. Eine derartige Vorrichtung fordert den Benutzer auf, ein Blatt 41 mit einer Braille-Zusammenfassung auf eine horizontale Anzeige zu legen. Der Benutzer berührt dann den interessanten Bereich auf dem Bildschirm 42, um entweder einen vollständigen Ausdruck oder eine sprachsynthetisierte Lesung anzufordern. Der Benutzer gibt dem Monitor an, wann eine neue Seite verarbeitet werden soll.

Dabei ist zu beachten, daß bei Verwendung des Verfahrens der vorliegenden Erfindung für ein Lesegerät für Blinde eine Reduktion der dem Benutzer für die Bewertung vorgelegten Materialmenge erreicht werden kann, so daß viele Probleme beseitigt werden können, die der gegenwärtigen Lesetechnologie für Blinde und andere Personen inhärent sind: so ist etwa ein effizientes Durchsehen eines Dokumentcorpus unter Verwendung von synthetisierter Sprache problematisch, sind das Volumen und die Kosten von Übertragungen auf Braille-Papier problematisch und ist der zum Lesen derartiger Kopien erforderliche Zeitaufwand problematisch.

Die vorliegende Erfindung ist nützlich, um gekürzte Dokumentbilder (Bildextrakte) für das Durchsehen vorzusehen. Eine reduzierte Wiedergabe eines Dokuments wird unter Verwendung eines Bitmap-Bildes mit wichtigen Elementen im Dokument erzeugt. Dies ermöglicht es dem Leser, schnell eine gescannte Dokumentbibliothek entweder elektronisch zu durchsuchen oder aber manuell zu durchsuchen, wenn Zusammenfassungskarten auf einem Medium wie Papier ausgedruckt werden. Die vorliegende Erfindung kann auch für die Kategorisierung eines Dokuments nützlich sein (lexikalisches Extrakt). Dabei können Stichwörter automatisch mit einem Dokument assoziiert werden. Der Benutzer kann dann die Stichwörter durchsehen, wobei die Stichwörter jedoch auch weiter verarbeitet werden können, etwa indem sie unter Verwendung einer optischen Zeichenerkennung decodiert werden.

Die vorliegende Erfindung wird hier in bezug auf besondere Anwendungen beschrieben und dargestellt, wobei jedoch zu beachten ist, daß die vorliegende Beschreibung lediglich beispielhaft ist und daß zahlreiche Änderungen in der Kombination und der Anordnung der Teile durch den Fachmann vorgenommen werden können, ohne daß dadurch der Schutzumfang der durch die beigefügten Ansprüche definierten vorliegenden Erfindung verlassen wird.


Anspruch[de]

1. Verfahren zum elektronischen Verarbeiten eines elektronischen Dokumentbildes, wobei das Verfahren folgende Schritte umfaßt:

(A) Segmentieren des Dokumentbildes in Wortbildeinheiten, ohne das Dokumentbild zu decodieren, und

(B) Identifizieren eines Satzes von Wortbildeinheiten für die weitere Verarbeitung auf der Basis von Bildeinheit-Eigenschaften, ohne die Wortbildeinheiten zu decodieren,

dadurch gekennzeichnet, daß

die Bildeinheit-Eigenschaften eine Formwiedergabe einer Bildeinheit sind,

wobei (B) umfaßt:

(B1) Vergleichen der Bildeinheit-Formwiedergaben der aus dem Dokumentbild segmentierten Wortbildeinheiten miteinander oder mit vorbestimmten oder benutzerbestimmten Auswahlkriterien, um den Satz von Wortbildeinheiten zu identifizieren.

2. Verfahren nach Anspruch 1, wobei (B) weiterhin das Klassifizieren der Wortbildeinheiten in Übereinstimmung mit der Häufigkeit ihres Auftretens umfaßt.

3. Verfahren nach Anspruch 1 oder 2, wobei die Bildeinheit-Formwiedergabe wenigstens die Bildeinheit-Abmessungen, die Anzahl der Oberlängen, die Anzahl der Unterlängen und/oder eine Kontureigenschaft der Bildeinheiten umfaßt.

4. Verfahren nach wenigstens einem der vorstehenden Ansprüche, das weiterhin den folgenden Schritt umfaßt:

(C) Erzeugen eines gekürzten Dokumentbildes auf der Basis des identifizierten Satzes von Wortbildeinheiten.

5. Verfahren nach wenigstens einem der Ansprüche 1 bis 3, das weiterhin wenigstens einen der folgenden Schritte umfaßt:

(D) Erzeugen eines Dokumentindex auf der Basis von ausgewählten Wortbildeinheiten aus dem identifizierten Satz von Wortbildeinheiten,

(E) Erzeugen einer sprachsynthetisierten Ausgabe von ausgewählten Wortbildeinheiten aus dem identifizierten Satz von Wortbildeinheiten,

(F) Erzeugen eines gedruckten Braille-Formats von ausgewählten Wortbildeinheiten aus dem identifizierten Satz von Wortbildeinheiten, und

(G) Erzeugen einer Dokumentzusammenfassung aus ausgewählten Wortbildeinheiten aus dem identifizierten Satz von Wortbildeinheiten.

6. Verfahren nach wenigstens einem der Ansprüche 1 bis 3, das weiterhin folgende Schritte umfaßt:

(H) Bilden von Phrasenbildeinheiten auf der Basis von ausgewählten Wortbildeinheiten aus dem identifizierten Satz von Wortbildeinheiten, wobei die Phrasenbildeinheiten jeweils eine Wortbildeinheit aus dem identifizierten Satz von Wortbildeinheiten sowie mit derselben in der Lesereihenfolge verknüpfte benachbarte Wortbildeinheiten umfassen, und

(I) Ausgeben der Phrasenbildeinheiten.

7. Vorrichtung zum elektronischen Verarbeiten eines elektronischen Dokumentbildes, mit:

einer Segmentierungseinrichtung (13, 20) zum Segmentieren des Dokumentbildes in Wortbildeinheiten, ohne das Dokumentbild zu decodieren, und

einer Identifizierungseinrichtung (13, 40) zum Identifizieren eines Satzes von Wortbildeinheiten für die weitere Verarbeitung auf der Basis von Bildeinheit-Eigenschaften, ohne die Wortbildeinheiten zu decodieren,

dadurch gekennzeichnet, daß

die Bildeinheit-Eigenschaften die Formwiedergabe einer Bildeinheit sind,

wobei die Identifizierungseinrichtung (13, 40) umfaßt:

eine Vergleichseinrichtung (13, 32) zum Vergleichen der Bildeinheit-Formwiedergaben der aus dem Dokumentbild segmentierten Wortbildeinheiten miteinander oder mit vorbestimmten oder benutzerbestimmten Auswahlkriterien, um den Satz von Wortbildeinheiten zu identifizieren.

8. Vorrichtung nach Anspruch 7, welche weiterhin umfaßt: eine Erzeugungseinrichtung (13, 50) zum Erzeugen eines Hilfsdokumentbildes auf der Basis des identifizierten Satzes von Wortbildeinheiten.

9. Vorrichtung nach Anspruch 8, welche weiterhin umfaßt:

eine Scaneinrichtung (12) zum Scannen eines Originalbildes, um das Dokumentbild zu erzeugen, wobei die Scaneinrichtung (12) in einem Dokumentkopiergerät, das gedruckte Dokumentkopien erzeugt, oder in einem Lesegerät für Blinde integriert ist, das eine Kommunikationseinrichtung zum Kommunizieren von Daten an den Benutzer umfaßt, und

eine Steuereinrichtung zum Steuern des Dokumentkopiergerätes, um eine gedruckte Dokumentkopie des Hilfsdokumentbildes zu erzeugen, oder zum Steuern der Kommunikationseinrichtung des Lesegerätes, um den Inhalt des Hilfsdokumentbildes zu kommunizieren.

10. Vorrichtung nach Anspruch 9, wobei die Kommunikationseinrichtung einen Drucker (17B) zum Erzeugen von Dokumentkopien im Braille-Format umfaßt oder wobei die Kommunikationseinrichtung einen Sprachsynthesizer zum Erzeugen einer sprachsynthetisierten Ausgabe in Übereinstimmung mit dem Hilfsdokumentbild umfaßt.

11. Vorrichtung nach Anspruch 9, wobei das Lesegerät eine durch den Benutzer bedienbare Einrichtung zum Angeben des gescannten Dokuments oder eines ausgewählten Teils desselben in Übereinstimmung mit dem Hilfsdokumentbild nach der Kommunikation des Hilfsdokumentbildes an den Benutzer 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

Patent Zeichnungen (PDF)

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