DE10308014B4

DE10308014B4 - System und Verfahren zum Lokalisieren eines nichttextlichen Bereichs eines elektronischen Dokumentes oder Bildes, der mit einer benutzerdefinierten Beschreibung des Bereichs übereinstimmt

Info

Publication number: DE10308014B4
Application number: DE10308014A
Authority: DE
Inventors: Steven John Fort Collins Simske; David Eugene St. Greeley Auter
Original assignee: Hewlett Packard Development Co LP
Current assignee: Hewlett Packard Development Co LP
Priority date: 2002-05-29
Filing date: 2003-02-25
Publication date: 2006-02-23
Anticipated expiration: 2023-02-26
Also published as: GB0311680D0; DE10308014A1; US7050630B2; GB2389209A; US20030223637A1

Abstract

Verfahren zum Lokalisieren eines nichttextlichen Bereichs eines elektronischen Dokuments oder Bildes (103), der mit einer benutzerdefinierten Beschreibung (104) des Bereichs übereinstimmt, wobei das Verfahren folgende Schritte aufweist:
Segmentieren jedes Dokuments eines Korpus von elektronischen Dokumenten in textliche und nichttextliche Bereiche;
Erzeugen der benutzerdefinierten Beschreibung (104) unter Verwendung geometrischer Parameter, die durch eine Benutzerschnittstelle eingegeben werden;
Vergleichen (106) der nichttextlichen Bereiche von jedem Dokument des Korpus von elektronischen Dokumenten (103) mit der benutzerdefinierten Beschreibung (104);
Identifizieren (107) von nichttextlichen Bereichen der elektronischen Dokumente (103), die mit der benutzerdefinierten Beschreibung (104) gemäß vorbestimmten Kriterien übereinstimmen; und
Wiedergewinnen von Dokumenten von dem Korpus, die mit der benutzerdefinierten Beschreibung übereinstimmen, und Identifizieren der wiedergewonnenen Dokumente für einen Benutzer.

Description

Die vorliegende Erfindung bezieht sich allgemein auf den Bereich der digitalen Dokumentverarbeitung. Spezieller bezieht sich die vorliegende Erfindung auf ein System und ein Verfahren zum Lokalisieren eines nichttextlichen Bereichs eines elektronischen Dokuments oder Bildes, der mit einer benutzerdefinierten Beschreibung des Bereichs übereinstimmt.

Mit dem Aufkommen einer erschwinglichen, großvolumigen Medienspeicherung tendieren viele Menschen und Organisationen zu einer umfangreichen digitalen Archivierung von Bildern und Dokumenten. Diese Tendenz reicht von einfachen Privatphotosammlungen zu extrem anspruchsvollen Datenbanken, die durch internationale Firmen verwendet werden, die digitale Bilder und Dokumente umfassen, die einen Text mit Bildern oder Graphiken kombinieren können. Leider ist ein Suchen nach und Wiedergewinnen von Bildern und Dokumenten aus diesen Datenbanken keine leichte Aufgabe.

Ein Digitalisieren und Scannen von Dokumenten, um elektronische Versionen zu erzeugen, ein Speichern der elektronischen Version in einer bestimmten Form eines elektronischen Speicherungsmediums und ein anschließendes Suchen nach diesen Dokumenten ist keine neue Technologie. Tatsächlich gibt es zahlreiche, im Handel und anderweitig erhältliche Systeme, die in den letzten Jahren entwickelt worden sind, um sich dieser Aufgabe zu widmen. Einer der größten Vorteile von einem solchen durchsuchbaren Dokumentsystem ist die Fähigkeit, große Mengen von Daten nach einem sehr kleinen Prozentsatz eines „Ziel"-Materials schnell und effizient zu durchsuchen.

Aktuelle Dokumentverwaltungssysteme erbringen bei der Arbeit mit Dokumenten, die vorwiegend aus Textinformationen bestehen, eine angemessen gute Leistung. Die wichtigsten Verfahren zum Durchsuchen einer Bilddatenbank sind textbasiert, wobei eine Indexierung, Dateinamen, thematische Etiketten usw., verwendet werden. Viele Techniken sind zum Analysieren von Bildern und Extrahieren der Textinformationen aus diesen Bildern und zum Umwandeln des Textes in eine Form entwickelt worden, die dann durch den Computer verarbeitet werden kann. Diese Technik ist allgemein als OCR (OCR = Optical Character Recognition = optische Schriftzeichenerkennung) bekannt. Die OCR kann verwendet werden, um einen Text aus einem Dokument zu erfassen, um einen Index für eine durchsuchbare Datenbank zu bilden. Der Text kann nach Bedarf auch in andere Anwendungen exportiert werden. Relativ gesprochen, steckt die OCR noch immer in ihren Kinderschuhen, und von keinem Paket kann behauptet werden, daß es zu 100 genau ist. Daher erfordert die OCR, die zu Indexierungszwecken verwendet wird, obwohl sie sehr nützlich ist, immer noch ein gewisses Maß an manueller Verifizierung, speziell wenn sie zum Tasten primärer Bereiche verwendet wird.

Bei der Automatisierung des Dokumentbilderzeugungs- und Durchsuchungsprozesses für Dokumente, die vorwiegend aus Text bestehen, hat die OCR-Technologie hat einen bedeutsamen Schritt gemacht. OCR-Prozesse und computerautomatisierte Prozesse sind jedoch bei der Handhabung von nichttextlichen Daten, speziell im Vergleich zu menschlichen Fähigkeiten, extrem beschränkt. Das visuelle Wahrnehmungssystem des Menschen ist bei der Hochgeschwindigkeitsanalyse von Bildern und bei der Identifizierung von Objekten in derselben hervorragend. Tatsächlich können Menschen von einem Bild Informationen viel schneller als von einer Textdarstellung der gleichen Daten erhalten.

Aus der DE 100 00 935 A1 ist ein Verfahren zum Verarbeiten von Dokumentenbildern bekannt, die beispielsweise durch Scannen erfasst worden sind und noch nicht vollständig verarbeitet sind. Die Bedienungsperson kann die zu verarbeitenden Dokumentenelemente spezifizieren, indem beispielsweise eine Textauswahlbox markiert wird. Wenn diese Box nicht markiert ist, wird das entsprechende Dokumentenelement beim Scannen des Dokuments nicht verarbeitet. Demzufolge kann die Bedienungsperson die gewünschten Dokumentenelemente verarbeiten lassen, ohne dass sie auf das Verarbeiten aller anderen Arten von Elementen warten muss.

Der vorliegenden Erfindung liegt die Aufgabe zugrunde, ein Verfahren und ein System zu schaffen, mit denen eine Identifikation eines Dokuments in einer Datenbank aufgrund von nicht-textlichen Suchkriterien, die durch die Bedienungsperson eingegeben werden können, ermöglicht wird.

Diese Aufgabe wird durch ein Verfahren gemäß Anspruch 1 und durch ein System gemäß Anspruch 7 gelöst.

Der in den Ansprüchen und den nachfolgenden Beschreibungsunterlagen verwendete Begriff „Korpus" bezieht sich auf eine Gruppe aus einem oder mehreren elektronischen Dokumenten.

Die vorliegende Erfindung sieht unter anderem ein Verfahren zum Lokalisieren eines nichttextlichen Bereichs eines elektronischen Dokumentes oder Bildes vor, der mit einer benutzerdefinierten Beschreibung des Bereichs übereinstimmt, wobei das Verfahren ein Vergleichen von nichttextlichen Bereichen von jeweils einem Korpus von elektronischen Dokumenten mit der benutzerdefinierten Beschreibung und ein Identifizieren von nichttextlichen Bereichen der elektronischen Dokumente, die mit der benutzerdefinierten Beschreibung gemäß den vorbestimmten Kriterien übereinstimmen, aufweist.

Die vorliegende Erfindung sieht auch ein System zum Lokalisieren eines nichttextlichen Bereichs eines elektronischen Dokumentes oder Bildes basierend auf einer benutzerdefinierten Beschreibung des Bereichs vor, wobei das System eine Benutzerschnittstelle zur Erzeugung der benutzerdefinierten Beschreibung des Bereichs und eine Zoneneinteilungsmaschine zum Segmentieren des elektronischen Dokuments in Bereiche, die nichttextlicher Bereiche umfassen, ein Vergleichen der nichttextlichen Bereiche mit der benutzerdefinierten Beschreibung und ein Identifizieren von nichttextlichen Bereichen, die mit der benutzerdefinierten Beschreibung gemäß dem vorbestimmten Kriterium übereinstimmen, aufweist.

Die vorliegende Erfindung sieht auch computerlesbare Anweisungen vor, die auf einem Medium zum Speichern von compu terlesbaren Anweisungen gespeichert sind, wobei die Anweisungen bewirken, daß ein Computer oder Prozessor jeweils einen Korpus von elektronischen Dokumenten in textliche und nichttextliche Bereiche segmentiert, die nichttextlichen Bereiche von jedem der elektronischen Dokumente mit einer benutzerdefinierten Beschreibung eines Zielbereichs vergleicht und nichttextliche Bereiche der elektronischen Dokumente, die mit der benutzerdefinierten Beschreibung des Zielbereichs gemäß dem vorbestimmten Kriterium übereinstimmen, identifiziert.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend, Bezug nehmend auf die beiliegenden Zeichnungen näher erläutert. Es zeigen:
1 ist ein Prozeßflußdiagramm eines Systems zum Übereinstimmen von nichttextlichen Bereichen eines elektronischen Dokuments oder Bildes mit benutzerdefinierten Parametern gemäß einem Ausführungsbeispiel der vorliegenden Erfindung,
1a einen Scanner und Allzweckcomputer, die beim Praktizieren der vorliegenden Erfindung verwendet werden können,
2 ein Prozeßflußdiagramm eines Systems zum Übereinstimmen von nichttextlichen Bereichen eines elektronischen Dokuments oder Bildes mit benutzerdefinierten Parametern und zum Extrahieren von Metadaten aus denselben gemäß einem anderen Ausführungsbeispiel der vorliegenden Erfindung,
3 eine geometrische Beschreibung, die benutzerdefinierte Parameter verkorpust, mit denen nichttextliche Bereiche von eingegebenen Dokumenten gemäß einem Ausführungsbeispiel der vorliegenden Erfindung übereinstimmt werden,
4 ein ausführliches Flußdiagramm des Betriebs eines Ausführungsbeispiels einer Zoneneinteilungsmaschine der vorliegenden Erfindung,
5 ein Beispiel eines Ausführungsbeispiels eines Metadatenextraktionsregel-Dokuments gemäß der vorliegenden Erfindung.
In den Zeichnungen bezeichnen identische Bezugszeichen bezeichnen ähnliche, jedoch nicht notwendigerweise identische Elemente in den Zeichnungen.
Die vorliegenden Erfindung sieht unter anderem eine Einrichtung und ein Verfahren zum Identifizieren von benutzerdefinierten nichttextlichen Bereichen von spezifizierten digitalen Bildern oder elektronischen Dokumenten und nach Bedarf ein Extrahieren von spezifischen deskriptiven Daten aus diesen Bereichen vor. Der hierin und in den beigefügten Ansprüchen verwendete Begriff „Dokument" ist als ein beliebiges Dokument, das eine Kombination aus Text, Untertiteln, Überschriften, Photos, Aufnahmen, Bildern, Graphiken, etc. enthält, zu verstehen. Ein Dokument kann ein Photo, eine Aufnahme oder ein Bild mit oder ohne Text oder eine beliebige Kombination aus diesen Elementen sein.
1 ist ein Prozeßflußdiagramm, das ein Ausführungsbeispiel der Erfindung darstellt. Bei diesem Prozeß bereitet 100 der Benutzer die Bilder und/oder Dokumente 103 zur Verarbeitung vor. Dies kann einfach ein Liefern oder Übertragen eines elektronischen Bildes oder von Dokumentdateien an das System beinhalten. Wenn die Bilder oder die Dokumente, die verarbeitet werden sollen, in Druckkopieform vorliegen, wird dieser Schritt 100 wahrscheinlich ein Betreiben eines Scanners oder eines anderen Bilderzeugungssystems beinhalten, um eine elektronische Version der Dokumente, die verarbeitet werden sollen, zu erzeugen. Die Dokumente, die in das System 100 eingegeben werden, können in einem beliebigen Format vorliegen, einschließlich, jedoch nicht beschränkt auf ein TIFF (TIFF = Tagged Image File Format = etikettiertes Bilddateiformat), BMP (BMP = Bitmap), GIF (GIF = Graphics Interchange Format = Grafikaustauschformat), JPG (JPG = Joint Pictures Expert Group Format = Vereinte-Bildexpertengruppe-Format), PDF (PDF = Portable Document Format = tragbares Dokumentformat) und PostScript-Format.
Auch erzeugt der Benutzer eine Beschreibung 101, die als GD (GD = Geometric Description = geometrische Beschreibung) 104 bekannt ist, die die ins Ziel gefaßten Bereiche des Dokuments beschreibt. In anderen Worten definiert die GD 104 den nichttextlichen Bereich oder die Bereiche, bezüglich derer der Benutzer wünscht, daß das System dieselben in den Bildern oder Dokumenten, die an das System bei 100, wie vorstehend beschrieben, geliefert wurden, identifiziert. Die GD wird in einem standardisierten Format, das als GDF (GDF = Geometric Description Format = geometrisches Beschreibungsformat) bezeichnet wird, aufbereitet. Die GD 104 und das GDF werden nachstehend ausführlicher erörtert. Das System vergleicht alle nichttextlichen Bereiche der eingegebenen Dokumente 100 mit der GD, die durch den Benutzer 104 erzeugt wurde. Es wird darauf hingewiesen, daß Schritt 100, Vorbereiten eines Dokuments zur Verarbeitung, und Schritt 101, erzeugen einer GD für einen Zielbereich in diesem Dokument, in einer beliebigen Reihenfolge ausgeführt werden können.
Sobald der Benutzer die vorangegangenen Schritte 100, 101 ausgeführt hat, beginnt das automatisierte System mit der Verarbeitung der elektronischen Bilder und/oder Dokumente 103. Die GD 104 und ein Dokument 103 werden zu einer ZAE (ZAE = Zoning Analysis Engine = Zoneneinteilungsmaschine) 106 gesendet. Die ZAE 106 identifiziert alle nichttextlichen Bereiche im Dokument 103. Dafür können die OCR-Techniken verwendet werden. Es ist jedoch keine volle OCR erforderlich, da die textlichen Bereiche, sobald dieselben einmal identifiziert worden sind, vorzugsweise aussortiert werden und nicht in einen editierbaren Text umgewandelt werden müssen. PRECISION SCAN und PRECISION SCAN PRO von der Firma Hewlett Packard sind Beispiele einer Scan-Software mit der notwendigen Funktionalität, um textliche und nichttextliche Bereiche in einem Dokument zu identifizieren. Nach dem Identifizieren von nichttextlichen Bereichen vergleicht die ZAE 106 dann die Spezifikationen der GD 104 mit jedem nichttextlichen Bereich in dem Dokument 103. Die ZAE 106 kann auch das eingehende Bild oder Dokument 100 in ein Standardformat, z. B. ein Bitmap-Format, umwandeln, um den Vergleich mit der GD 104 zu vereinfachen.
Wenn zwischen den Spezifikationen der GD 104 und den nichttextlichen Bereichen des Dokuments 103 keine Übereinstimmung 107 vorliegt, endet die Verarbeitung für dieses spezielle Dokument. Das System kehrt dann zur Verarbeitung eines weiteren Dokuments zurück, wenn ein solches vorhanden ist, 109.
Wenn eine Übereinstimmung vorgefunden worden ist, kann das Dokument etikettiert 114 werden. Zusätzlich oder alternativ kann das Dokument dem Benutzer 115 präsentiert oder für denselben identifizieren werden. Der Benutzer kann dann die Option haben, das Dokument zu etikettieren oder es zur späteren Verwendung auf beiseite zu legen. Nach der Handhabung der identifizierten Übereinstimmung kehrt das System dann zur Verarbeitung eines weiteren Dokumentes zurück, falls ein solches vorhanden ist 109.
Dieses Verfahren wiederholt sich solange, bis alle Bilder und Dokumente 103, die an das System 100 geliefert oder für diese spezielle Suche benannt wurden, verarbeitet worden sind. Der Betrieb des Dokuments endet dann 113. Der Benutzer kann einen Teilsatz des Korpuss von verfügbaren elektronischen Dokumenten, in denen die Suche nach einer Übereinstimmung mit der definierten GD durchzuführen ist, spezifizieren 104.
Wenn ein Bereich, der mit der GD übereinstimmt 104, in einem Dokument identifiziert worden ist, kann eine Aufzeichnung von dieser Übereinstimmung erzeugt und gespeichert werden 114. Dies ist besonders nützlich, wenn der Benutzer das identifizierte Dokument zum gegenwärtigen Zeitpunkt nicht betrachten oder weiter mit demselben arbeiten oder dasselbe verarbeiten möchte. Die Aufzeichnung der Übereinstimmung ist vorzugsweise in einer XML-Datei oder – datenbank (XML = Extensible Markup Language = erweiterbare Markierungssprache) gespeichert. Zum Beispiel,
Die „relativen" xmin, xmax, ymin und ymax werden verwendet, so daß die x- und y-Achsen normiert sind, um von 0 bis 100 der vollen Skala zu gehen, so daß die Zielposition unabhängig von Pixel/Zoll (ppi) spezifiziert ist. Auf diese Weise kann der Bereich lokalisiert werden, ungeachtet dessen, wie die Daten für die Analyse skaliert sind, z. B. werden einige Bereiche bei einem spezifischen ppi ausgewertet, andere Bereiche werden bei anderen ppis ausgewertet, und Quelldateien von einem unterschiedlichen ppi sind immer noch vergleichbar. Wenn ein Bereich beispielsweise das mittlere Viertel einer Seite abdeckt, beträgt sein relativer xmin 0,25, sein relativer xmax 0,75, sein relativer ymin 0,25 und sein relativer ymax 0,75. Wenn die Seite bei 300 ppi angelangt ist und 11 × 8,5 Zoll beträgt, dann werden die absoluten Werte ganz einfach so berechnet: xmin = 8,5 × 300 × 0,25 = 637,5 Pixel xmax = 8,5 × 300 × 0,75 = 1.912,5 Pixel ymin = 11 × 300 × 0,25 = 825 Pixel ymax = 11 × 300 × 0,75 = 2.475 Pixel
Der in 1 dargestellte Prozeß mit Ausnahme der Schritte, die durch den Benutzer ausgeführt werden, ist vorzugsweise in einer Softwareanwendung verkorpust, die auf einem Allzweckcomputer 121, der in 1a dargestellt ist, betrieben werden kann. 1a stellt einen Scanner 120, der mit dem Computer 121 verbunden ist, dar. Der Scanner 120 kann verwendet werden, um die Druckkopiedokumente oder Bilder zu digitalisieren. Ein digitales Bild kann eine Probe sein, die die Basis für eine GD bildet, oder ein Zusatz für den Korpus von Dokumenten sein, mit dem die GD verglichen wird, um einen übereinstimmenden nichttextlichen Bereich zu finden. Der Scanner 120, der dargestellt ist, ist ein einfacher Flachbettscanner. Es könnte jedoch ein beliebiger Typ von Scanner beim Praktizieren der vorliegenden Erfindung verwendet werden.
2 zeigt ein anderes Ausführungsbeispiel der vorliegenden Erfindung, wo der Benutzer nicht nur am Lokalisieren von Dokumenten, die einen textlichen Bereich aufweisen, der mit der GD 104 übereinstimmt, interessiert ist, sondern auch Daten aus diesen Bereichen 108 extrahieren möchte. Diese extrahierten Daten können als Metadaten über den Bereich, aus dem sie extrahiert wurden, beschreiben werden. Die Metadaten sind Daten, die andere zugrundeliegende Daten, d. h. Daten über Daten, beschreiben.
Bei diesem Ausführungsbeispiel führt der Benutzer drei vorhergehende Schritte aus. Die Schritte eins 100 und zwei 101 sind mit dem vorherigen Beispiels identisch. Bei Schritt drei 102 ist der Benutzer für das Vorbereiten der MER (MER = Metadata Extraction Rules = Metadatenextrahierungsregeln) 105 verantwortlich, welche Regeln, z. B. spezifische Algorithmen, sind, die beim Extrahieren der spezifischen Daten verwendet werden, die vom Benutzer aus Bereichen benötigt werden, die als mit der GD 104 übereinstimmend identifiziert worden sind. Die MER 105 wird nachstehend ausführlicher erörtert.
Der Prozeßfluß in 2 ist im wesentlichen mit dem vorherigen Prozeß bis zu dem Punkt identisch, wo eine Übereinstimmung 107 durch die ZAE 106 gefunden worden ist 107. Sobald der Benutzer die vorangegangenen Schritte 100, 101, 102 ausgeführt hat, beginnt das automatisierte System mit der Verarbeitung der elektronischen Bilder und/oder Dokumente 103. Die GD 104 und ein Dokument 103 werden an die ZAE 106 gesendet. Die ZAE 106 identifiziert alle nichttextlichen Bereiche in dem Dokument 103. Die ZAE 106 vergleicht dann die Spezifikationen der GD 106 mit jedem nichttextlichen Bereich in dem Dokument 103.
Wenn zwischen den Spezifikationen der GD 104 und den nichttextlichen Bereichen des Dokuments 103 keine Übereinstimmung 107 vorhanden ist, endet die Verarbeitung für dieses spezielle Dokument. Das System kehrt dann zur Verarbeitung eines anderen Dokuments zurück, wenn ein solches vorhanden ist 109.
Sobald jedoch ein Dokument, das einen nichttextlichen Bereich enthält, der mit der GD 104 übereinstimmt, lokalisiert worden ist, werden die Metadaten aus dem übereinstimmenden nichttextlichen Bereich dieses Dokuments 103 gemäß den Bestimmungen der MER 105 extrahiert 110. Wenn die Metadaten extrahiert worden sind, werden die Informationen vorzugsweise in einer Datenbank gespeichert 111. Zusätzlich oder alternativ können die extrahierten Metadaten dem Benutzer zur Überprüfung vorgelegt werden 112.
Nachdem jedes Dokument auf nichttextliche Bereiche, die mit der GD 104 übereinstimmen, überprüft worden ist 107, kehrt das System zur Verarbeitung eines weiteren Bildes zurück, wenn ein solches vorhanden ist 109. Dies gilt je nachdem, ob ein übereinstimmender nichttextlicher Bereich in dem vorhergehenden Dokument entdeckt worden ist. Sobald alle Bilddokumente 103 verarbeitet worden sind, endet der Systembetrieb 113.
3 ist eine Darstellung einer GD 104 gemäß der vorliegenden Erfindung. Die GD 104 ist vorzugsweise ein elektronisches Dokument der XML oder einer anderen standardisierten Sprache. Die verwendete Sprache ist nicht besonders von Bedeutung, jedoch eignet sich XML an sich ziemlich gut für diese Art von Anwendung.
Die GD 104 wird in einem standardisierten Format, das hierin als das GDF (GDF = Geometric Description Format = geometrisches Beschreibungsformat) bezeichnet wird, aufbereitet. Die exakten Spezifikationen und Einzelheiten dieses Formats sind nicht notwendigerweise von Bedeutung, um die Erfindung zu praktizieren. Solche Spezifikationen und Einzelheiten können ausgewählt und definiert werden, wie es für eine spezielle Anwendung angebracht ist. Die ZAE empfängt vorzugsweise die GD 104 in einem erwarteten und standardisierten Format, so daß der Vergleich mit den nichttextlichen Bereichen des Dokuments, das verarbeitet wird, vereinfacht werden kann.
Bei einem bevorzugten Beispiel, das in XML vorliegt, kann das GDF die nachstehenden Informationen in der nachstehenden Organisation umfassen:
Der Benutzer muß die XML-Syntax und Formatierung jedoch nicht kennen, um eine solche GD zu erzeugen. Vielmehr kann die GD in einer ordnungsgemäßen XML automatisch von einem einfacheren Dateneingabeform, die dem Benutzer geboten wird, oder selbst aus einer Serie von spezifisch angeordneten Benutzerschnittstellensteuerungen, wie z. B. Knöpfen, Wahlknöpfen, Listenfeldern, Combofeldern, Textfeldern, Schiebern, etc., erzeugt werden.
Die GD 104 kann durch den Benutzer auf zahlreiche Weisen erzeugt werden. Ein Beispiel ist die Verwendung der Dateneintragsform oder der soeben beschriebenen Benutzerschnittstelle. Der einfachste Weg aus der Perspektive des Benutzers ist, einen ordnungsgemäß programmierten Computer dazu zu bringen, eine Probe des Bereichs oder der Bereiche zu analysieren, die der Benutzer identifizieren möchte, und eine GD 104 anhand dieser Analyse automatisch zu erzeugen. Die Programmierung für einen Computer, um eine GD anhand einer Probe zu erzeugen, hängt von den Spezifikationen und Einzelheiten des GD-Schemas ab, das bei einer spezifischen Anwendung übernommen wurde, und gehört zu den Fähigkeiten eines durchschnittlich qualifizierten Fachmanns, der sich den Inhalt dieser Offenbarung dabei zunutze macht. Die verwendete Probe kann eine elektronische Datei oder eine Druckkopieprobe sein, die dann gescannt wird, um eine elektronische Version zu erzeugen. In beiden Fällen kann das System dann die elektronisch aufbereitete Probe verwenden und eine GD 104 gemäß der Probe erzeugen. In einem solchen Fall erkennt das System eine Fehlertoleranz für die Parameter, die durch Analysieren der Probe erhalten wurden. Vorzugsweise beträgt diese Fehlertoleranz beispielsweise 5%. Alternativ, wenn mehrere Proben gescannt werden, können als Fehlertoleranz drei Standardabweichungen anstelle von 5% verwendet werden. Dies ist eine typische und einfache statistische Heuristik zum Bestimmen von Ausreißern und ermöglicht, daß eine „automatische, adaptive" Fehlertoleranz erhalten wird, wenn dem Benutzer mehrere Proben vorliegen.
Alternativ kann der Benutzer die Parameter der GD 104 unter Verwendung einer Benutzerschnittstelle spezifizieren. Dies könnte ein Auswählen eines Probebereichs aus einem größeren Bild oder Dokument unter Verwendung von beispielsweise einer graphischen Benutzerschnittstelle, wie z. B. einem Scannervorschaufenster oder einer PDF-Betrachtungseinrichtung, wie z. B. Adobe ACROBAT, umfassen.
In jedem dieser Fälle ist der Benutzer vorzugsweise in der Lage, einen beliebigen Parameter der GD 104, der durch eine automatische Analyse einer Probe erzeugt wurde, aufzuheben. Dies könnte beispielsweise durch ein Rechts-Klick-Menü, ein Pull-Down-Menü oder eine Benutzerschnittstelle, die speziell für die Erzeugung einer GD 104 von einer Probe oder von anderen benutzerspezifizierten Parametern konzipiert ist, geschehen. Die Art und Weise der Erzeugung der GD 104 ist nicht von Bedeutung, solange die GD 104 den nichttextlichen Bereich eines Dokuments, den der Benutzer finden möchte, beschreibt.
Wie in 3 gezeigt ist, besteht die GD 104 vorzugsweise aus zwei Abschnitten. Abschnitt Eins 104a, der auch als die Anforderungen erster Ordnung bekannt ist, besteht aus einer Beschreibung des Zielbereichs. Diese Beschreibung enthält typischerweise die Höhe und Breite des Zielbereichs, die Exzentrizität und/oder ein Histogramm des Zielbereichs und/oder die Anzahl von Zielbereichen und eine Bereich-zu- Bereich-Ausrichtung, wenn mehrere Bereiche spezifiziert sind. Abschnitt eins kann ferner beliebige andere nützliche und einschlägige deskriptive Daten umfassen. Die Daten für Abschnitt eins können von einem Bitmap-Bild von einer Probe, die gescannt wird, genommen werden, oder können durch eine direkte Benutzereingabe spezifiziert werden.
In vielen Fällen sind die Daten in Abschnitt eins ausreichend, ohne zudem die Zielbereiche zu identifizieren, nach denen der Benutzer im Korpus der elektronischen Dokumente, die durchsucht werden sollen, sucht. Dies ist speziell der Fall, wenn eine hochqualitative Probe verwendet wird, um die Daten von Abschnitt eins 104a der GD 104 zu erzeugen.
Die Daten im Abschnitt eins können jedoch mit den Daten von Abschnitt zwei 104b ergänzt werden, um besser sicherstellen zu können, daß das System der vorliegenden Erfindung die Bereiche, die durch den Benutzer gewünscht werden, in den Dokumenten, die durchsucht werden, identifiziert oder korrekt identifiziert. Die zwei Abschnitte 104a, 104b der fertiggestellten GD 104 können an verschiedenen Punkten während der Untersuchung durch die ZAE 106 verwendet werden, wie nachstehend ausführlicher beschrieben wird. Abschnitt zwei 104b ist auch als die SVG-Beschreibung (SVG = Scalable Vector Graphics = skalierbare Vektorgraphik) des Zielbereichs bekannt. Die SVG-Beschreibung 104b der GD 104 enthält eine SVG-Beschreibung der Zielbereiche oder der Zielbereiche, die der Benutzer in den Dokumenten, die durchsucht werden, identifizieren möchte. Der SVG-Standard ist eine offene XML-Spezifikation zur Beschreibung von Vektorgraphiken, die ermöglicht, daß die beschriebenen Graphiken skaliert, rotiert und anderweitig elektronisch manipuliert werden können. Ein SVG-Standard ist durch das W3C (W3C = World Wide Web Consortium = World-Wide-Web-Konsortium) bekannt gemacht worden und ist unter http://www.w3.org/TR/SVG/ verfügbar. Dieser SVG-Standard kann mit der vorliegenden Erfindung verwendet werden und wird dies vorzugsweise auch. In anderen Worten erfüllt die SVG-Beschreibung des Zielbereichs in Abschnitt zwei 104b vorzugsweise den W3C-SVG-Standard.
Bei der vorliegenden Erfindung wird die Probe gescannt und schließlich in einer Bitmap-Form aufbereitet, wenn der Benutzer die GD 104 mit einer Probe erzeugt. Das Bitmap kann dann in eine Vektorform umgewandelt und unter Verwendung des SVG-Standards beschrieben werden.
4 ist ein ausführlicheres Prozeßflußdiagramm des Betriebs der ZAE 106. Die GD 104 und das Bilddokument 103 werden an die ZAE 106 gesendet. Der erste Schritt in der ZAE 106 ist, das Bilddokument nach Bedarf zu entzerren und dann das Bild in seine Komponentenbereiche zu segmentieren 118. Die Komponentenbereiche werden dann durch Precision Scan, OCR oder eine ähnliche Technologie analysiert, um zu bestimmen, ob es textliche oder nichttextliche Bereiche 119 sind. Es werden beliebige textliche Bereiche ignoriert 120. Die verbleibenden Bereiche werden anschließend mit Abschnitt eins 104a der GD verglichen, um zu bestimmen, ob sie die Anforderungen der ersten Ordnung 121 erfüllen. Beliebige Bereiche, die die Anforderungen der ersten Ordnung nicht erfüllen, stimmen nicht mit dem Bereich überein, den der Benutzer sucht, wie durch die GD 104 definiert ist, und werden ignoriert 120.
Die Bereiche, die die Anforderungen des Abschnitts 104a erfüllen, können als mit der GD 104 übereinstimmend betrachtet werden und werden als die Bereiche identifiziert, nach denen der Benutzer sucht. Dies würde ein grobes Suchergebnis ergeben, das in einigen Fällen vollkommen adäquat sein kann.
Alternativ werden die Bereiche, die die Anforderungen des Abschnitts eins 104a; 3 erfüllen, zu Kandidatenbereichen, die einem weiteren Vergleichen mit den Daten von Abschnitt zwei 104b, 3 der GD 104 unterzogen werden. Um diesen weiteren Vergleich auszuführen, werden die Kandi datenbereiche binarisiert und in SVG-kompatible Vektorgraphiken 122 umgewandelt. Diese Umwandlung wird mit einer Binär-zu-Vektor-Umwandlungssoftware ausgeführt, die ein Teil der ZAE 106 ist oder von derselben aufgerufen wird.
Die SVG-Beschreibung des Kandidatenbereichs wird dann mit dem Abschnitt zwei der GD 104b verglichen, die die SVG-kompatible Beschreibung des Bereichs ist, nach dem der Benutzer sucht. Die Übereinstimmung basiert auf der Ähnlichkeit der zwei Bilder. Der Prozentsatz des gemeinsamen verwendeten Bereichs (der separat von der SVG-Spezifikation berechnet wurde) ist eine gute Möglichkeit zum Korrelieren der zwei SVG-Beschreibungen. Bereiche, die um mehr als 95% überlappen, gelten beispielsweise allgemein als „übereinstimmend" 123. Die Kriterien zum Übereinstimmen mehrerer Bereiche können in gewisser Weise gelockert werden (wenn das Ziel, das im GDF beschrieben ist, zwei oder mehr Bereiche auf der Seite aufweist), weil ein Ermöglichen einer höheren „Falsch-Positiv"-Rate für einen Bereich (z. B. 10% Nichtüberlappung) durch die niedrige Fehlerrate für doppelte Übereinstimmungen versetzt wird, wenn die Bereichssätze tatsächlich unterschiedlich sind. Die 10%-Nichtüberlappung bedeutet einfach, daß eine 5%-Toleranz für zwei Bereiche hinzugefügt wird. Eine exaktere Skalierung auf zwei Bereiche (statistisch gesprochen) könnte 1-(95%)(95%)=9,75, sein, jedoch sind 10% üblicherweise ausreichend.
Die Ausrichtungsunterschiede zwischen der Schablone und den Kandidatenbereichen werden ohne weiteres durch Rotieren eines Bildes um 90, 180 oder 270 Grad bezüglich des anderen gehandhabt, bevor sie entweder von dem Kandidatensatz oder dem finalen „übereinstimmenden" Satz eliminiert werden.
Wenn mehr Bereiche analysiert werden sollen 124, kehrt der Prozeß zu dem Texttest 119 in der ZAE 106 zurück. Nachdem alle Bereiche analysiert worden sind, werden die übereinstimmten Bilder, falls welche vorhanden sind, weiterverarbeitet. Wie zuvor erwähnt wurde, könnte eine Weiterverar beitung einfach bedeuten, dass die Dokumente mit einem Flag versehen werden und/oder die übereinstimmenden Bereiche dem Benutzer gezeigt werden, oder sie könnte einen umfangreicheren Prozeß des Analysierens, Extrahierens und Speichern von Metadaten von den speziellen Bereichen bedeuten.
Beim Extrahieren von Metadaten aus den Bereichen wird die Prozedur zum Extrahieren der Daten in einem Satz von MERs (MER = metadate extraction rule = Metadatenextrahierungsregel) 105 spezifiziert. Die MER, wie die GD, wird vorzugsweise in einem XML-Dokument aufgezeichnet, kann jedoch auch andere Formen annehmen. Die MER muß durch den Benutzer nicht in einer XML-Syntax und einem XML-Format eingegeben werden. Vielmehr kann die MER, wie die vorstehend beschriebene GD, durch ein Eintrittsformular oder eine Benutzerschnittstelle mit einer Standardeingabevorrichtung, wie z. B. Knöpfe, Wahlknöpfe etc., eingegeben werden. Die MER kann dann als eine XML-Datei basierend auf der Benutzereingabe automatisch erzeugt werden.
Die MER-Regeln umfassen typischerweise eine Vielfalt an Algorithmen, die entweder eingebaut oder durch den Benutzer bereitgestellt werden, die ausgeführt werden, um eine nützliche Analyse des identifizierten Bereichs zu liefern. Ein beliebiger Algorithmus zum Analysieren eines nichttextlichen Bereichs eines elektronischen Bildes oder Dokuments könnte verwendet werden und würde sich innerhalb des Schutzbereichs der vorliegenden Erfindung bewegen. Einige Beispiele sind Operationen auf den Reihen und Spalten von Pixeln (Profektionsprofile), Histogrammanalysen (die Anzahl von Spitzen, Prozentsatz von schwarzen gegenüber weißen Pixeln etc.), Bestimmen von Hauptfarben (Palettenerzeugung) etc.
Wenn der identifizierte Bereich beispielsweise ein Balkendiagramm oder ein Tortendiagramm oder dergleichen ist, könnten die extrahierten Daten das Ergebnis eines Vergleichs der Größe von Elementen in dem Balkendiagramm oder, bei einer Farbunterscheidung, in dem Tortendiagramm sein. Daher könnte eine Annäherung der Rohdaten, die verwendet werden, um das Diagramm zu erzeugen, als Metadaten aus dieser Analyse der elektronischen Version des Diagramms extrahiert werden.
In vielen Fällen weisen nur ein Dokument oder wenige Dokumente in einem großen Satz von Dokumenten Bereiche auf, die mit der GD 104 übereinstimmen, die der Benutzer spezifiziert hat. Eine spezielle Anwendung der vorliegenden Erfindung, auf die dies zutrifft, wird in der Qualitätskontrolle zum Scannen von Büchern verwendet. Um ein Buch in elektronischer Form aufzubereiten, wird jede Seite des Buchs gescannt. Typischerweise ist an jeder einzelnen Seite des Buchs, das gescannt wird, ein MTF-Ziel (MTF = Modulation Transfer Function = Modulationsübertragungsfunktion) angebracht. Die MTF ist ein Symbol, das aus vertikalen und horizontalen Linien besteht, die durch unterschiedliche Räume getrennt sind. Ihre Funktion ist es, zu ermöglichen, daß die Qualität des Scannens des Buchs bewertet werden kann.
In bezug auf die vorliegende Erfindung könnte die Definition des MTF-Ziels oder der MTF-Ziele in der GD 104 umfaßt sein. Die relative Positionierung der MTF-Ziele auf der Seite würde in Abschnitt eins 104a beschrieben sein, und die tatsächliche Geometrie der MTF-Ziele (die horizontalen und vertikalen Linien und entsprechenden Räume) würden durch Abschnitt zwei 104b beschrieben sein. Nach der Datei oder den Dateien, die durch das Scannen des Buchs erzeugt werden, wird durch ein Ausführungsbeispiel der vorliegenden Erfindung für das gescannte Bild des MTF-Ziels gesucht. Wenn das gescannte Bild des MTF-Ziels lokalisiert worden ist, wird es gemäß bekannter Techniken verwendet, um die Scanqualität der Seiten, die aus dem Buch gescannt wurden, zu bewerten.
5 gibt einen groben Überblick über einen Probe-MER-Satz 105, der zum Analysieren eines solchen MTF-Ziels verwendet werden könnte. In dem Beispiel ist ein grober Überblick über die Grundschritte der Algorithmen gegeben 124, und die entsprechenden primitiven Algorithmen sind gezeigt 125. Die Schritte des Algorithmus umfassen: (1) Erzeugen eines Histogramms für jeden der vier Zielbereiche, (2) Finden von Pixeln für x% des Histogramms, wobei x = 5 & 95, (3) Finden eines Bereichs für x = 95% – x = 5% und (4) Berechnen des MTFs in beide Richtungen durch Verwendung der entsprechenden zwei Zielbereiche. Die primitiven Algorithmen können folgendes umfassen: (1) ComputeHistogramm(), (2) ComputeHistogrammPctPoint(x), wobei x = 5, 95, (3) Subtraktion und (4) Division. Diese Algorithmen können beispielsweise mit den zusätzlichen primitiven Algorithmen 126 ergänzt werden, die dargestellt sind, z. B. (1) ComputeProjectionProfile(d), wobei Richtung d = x,y; (2) FindProjectionProfilePeaks(); (3) Multiplikation und (4) Addition.
Es ist klar, daß es sich dabei nicht um eine erschöpfende Liste handelt. Es gibt eine unendliche Anzahl von Algorithmen, die entwickelt und verwendet werden könnten, um Daten von einem nichttextlichen Bereich eines elektronischen Dokuments zu extrahieren. Jedoch selbst bei den aufgelisteten acht einfachen Algorithmen werden mehrere weitere Anwendungen für die vorliegende Erfindung ohne weiteres offenbar.

Claims

Verfahren zum Lokalisieren eines nichttextlichen Bereichs eines elektronischen Dokuments oder Bildes (103), der mit einer benutzerdefinierten Beschreibung (104) des Bereichs übereinstimmt, wobei das Verfahren folgende Schritte aufweist: Segmentieren jedes Dokuments eines Korpus von elektronischen Dokumenten in textliche und nichttextliche Bereiche; Erzeugen der benutzerdefinierten Beschreibung (104) unter Verwendung geometrischer Parameter, die durch eine Benutzerschnittstelle eingegeben werden; Vergleichen (106) der nichttextlichen Bereiche von jedem Dokument des Korpus von elektronischen Dokumenten (103) mit der benutzerdefinierten Beschreibung (104); Identifizieren (107) von nichttextlichen Bereichen der elektronischen Dokumente (103), die mit der benutzerdefinierten Beschreibung (104) gemäß vorbestimmten Kriterien übereinstimmen; und Wiedergewinnen von Dokumenten von dem Korpus, die mit der benutzerdefinierten Beschreibung übereinstimmen, und Identifizieren der wiedergewonnenen Dokumente für einen Benutzer.
Verfahren gemäß Anspruch 1, bei dem die benutzerdefinierte Beschreibung eine Beschreibung gemäß dem Skalierbare-Vektorgrafik-Standard eines nichttextlichen Bereichs umfasst, den der Benutzer innerhalb des Korpus von Dokumenten lokalisieren möchte.
Verfahren gemäß Anspruch 1 oder 2, bei dem die benutzerdefinierte Beschreibung eine relative maximale und minimale Abmessung eines nichttextlichen Bereichs umfasst.
Verfahren gemäß einem der Ansprüche 1 bis 3, bei dem die benutzerdefinierte Beschreibung Spezifizierungen von Exzentrizität, Histogramm oder Intra-Bereichs-Abhängigkeit eines nichttextlichen Bereichs umfasst, den der Benutzer innerhalb des Korpus von Dokumenten lokalisieren möchte.
Verfahren gemäß einem der Ansprüche 1 bis 4, das ferner ein Definieren eines Satzes von Algorithmen (105), die auf dem nichttextlichen Bereich ausgeführt werden, der als mit der benutzerdefinierten Beschreibung (104) übereinstimmend identifiziert ist, aufweist, um Daten von dem nichttextlichen Bereich zu extrahieren.
Verfahren gemäß einem der Ansprüche 1 bis 5, bei dem die benutzerdefinierte Beschreibung in erweiterbarer Markierungssprache wiedergegeben wird und das Verfahren ferner ein automatisches Umwandeln der Benutzereingabe in einem anderen Format in die benutzerdefinierte Beschreibung in erweiterbarer Markierungssprache aufweist.
System zum Lokalisieren eines nichttextlichen Bereichs eines elektronischen Dokuments oder Bildes (103) basierend auf einer benutzerdefinierten Beschreibung (104) des Bereichs, wobei das System folgende Merkmale aufweist: eine Benutzerschnittstelle zur Erzeugung (104) der benutzerdefinierten Beschreibung des Bereichs (104) basierend auf geometrischen Parametern, die durch die Benutzerschnittstelle eingegeben werden; und eine Zoneneinteilungsmaschine (106) zum Segmentieren (118) des elektronischen Dokuments (103) in Bereiche, die textliche und nichttextliche Bereiche umfassen, zum Vergleichen der nichttextlichen Bereiche mit der benutzerdefinierten Beschreibung (104) und zum Identifizieren (114) von nichttextlichen Bereichen, die mit der benutzerdefinierten Beschreibung (104) gemäß vorbestimmten Kriterien übereinstimmen.
System gemäß Anspruch 7, das ferner einen Allzweckcomputer (121) aufweist, wobei die Benutzerschnittstelle (101) und die Zoneneinteilungsmaschine (106) durch eine Anwendung, die auf dem Allzweckcomputer (121) arbeitet, bereitgestellt werden.
System gemäß Anspruch 8, bei dem die benutzerdefinierte Beschreibung eine Beschreibung gemäß dem Skalierbare-Vektorgraphik-Standard eines nichttextlichen Bereichs umfasst, den der Benutzer innerhalb des Korpus von Dokumenten lokalisieren möchte.
System gemäß Anspruch 8 oder 9, bei dem die benutzerdefinierte Beschreibung in erweiterbarer Markierugssprache wiedergegeben ist und das Verfahren ferner ein automatisches Umwandeln der Benutzereingabe in einem anderen Format in die benutzerdefinierte Beschreibung in erweiterbarer Markierungssprache aufweist.