DE69029594T2

DE69029594T2 - Ermittlung von Linienabschnitten und von vorbestimmten Mustern in einem optisch abgetasteten Dokument

Info

Publication number: DE69029594T2
Application number: DE69029594T
Authority: DE
Inventors: Keiko Abe
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1989-03-25
Filing date: 1990-03-23
Publication date: 1997-04-24
Anticipated expiration: 2010-03-24
Also published as: US5129012A; EP0389988A2; DE69029594D1; KR910017331A; EP0389988A3; EP0389988B1

Description

Diese Erfindung bezieht sich auf ein Verfahren und eine Vorrichtung zur Erfassung von Liniensegmenten und speziellen Mustern, die in einem Dokument vorhanden sein können, und insbesondere auf solch ein Verfahren und eine Vorrichtung mit einer besonderen Nützlichkeit bei der optischen Zeichenerkennung, wobei ein Dokument aus Linien- und Zeichenindices gebildet wird und wobei Linienindices von Zeichenindices zur Erleichterung der Zeichen-Interpretation unterschieden (diskriminiert) werden.
Optische Zeichenerkennung wird seit langem zum maschinellen Lesen von Information auf einem gedruckten Dokument verwendet, um solch eine Information in elektronische Form umsetzen zu können. Typischerweise wird ein Dokument mit alphanumerischen Zeichenindices, Punktuationsindices und Linienindices versehen, wobei letzteres ein unterstrichenes Wort oder eine unterstrichene Passage sind. Um die Zeichenerkennung zu erleichtern ist es allgemein nützlich, gedruckte Linien aus dem Dokument, wie beispielsweise die zuvor genannte Unterstreichung zu beseitigen. Natürlich können solche Linien im allgemeinen nach dem Druck eines Dokumentes nicht ignoriert werden.
Es wurden verschiedene Techniken vorgeschlagen, um alphanumerische Zeichen sowie andere Zeichen zu erkennen, die normalerweise zur Übertragung von Information mittels eines gedruckten Dokumentes verwendet werden. Einige dieser Techniken sind in den japanischen Patentveröffentlichungen Nr. 62-74181, 62-74182, 62-74183 und 62-74184 beschrieben. Weitere Beispiele von Techniken, die zur Erkennung von gedruckten Zeichen verwendet werden, sind beispielsweise beschrieben in "Segmentation Methods for Recognition of Machine-Printed Characters" Hoffman and McCullough, IBM Journal of Research and Development, März 1971, Seiten 153-165; "Block Segmentation and Text Extraction in Mixed Text/Image Documents", Wahl, Wong and Casey, Computer Graphics and Image Processing, Band 20 (1982), Seiten 375-390; und "Approach to Smart Document Reader System" Masuda, Hagita, Akiyama, Takahashi and Naito, Proceedings ICTP 1985, Seiten 550-557. Das Vorhandensein von Linien in dem gedruckten Dokument kann die erfolgreiche Erkennung von gedruckten Zeichen verhindern, wenn es in Abtast-Bilddaten umgesetzt wird. Beispielsweise kann eine einfache Unterstreichung verwischt, unterbrochen oder mit uneinheitlicher Dicke gedruckt sein. Eine Linie dieses Typs kann fehlerhaft als angehängtes Element interpretiert werden, wodurch die erfolgreiche Erkennung eines in der Nähe befindlichen Zeichens verhindert wird.
Das Problem der Unterscheidung zwischen Linien und Zeichen erhöht sich, wenn die Linie auf dem Dokument leicht gewinkelt oder schrägliegend ist. Darüberhinaus werden Linien oft in speziellen Mustern gedruckt oder gezeichnet, von denen einige zu erkennende Zeichen enthalten und andere Graphikinformation wie Zeichnungen, Photos und dergleichen enthalten, die nicht durch die Maschine interpretiert werden müssen. Beispielsweise können Linien in einem Gitter gedruckt werden, um eine Tabelle zu schaffen, in der alphanumerische Zeichen vorgesehen werden. Als weiteres Beispiel können die Linien als rechteckiger Kasten oder Block gebildet werden, in dem alphanumerische Zeichen oder die genannten Graphikdaten vorgesehen werden können. Im letzteren Fall ist es wünschenswert, den Block zu identifizieren, der als eine Grenze für die Graphikdaten dient und die Zeichenerkennung so zu programmieren, daß alle Verzeichnisse innerhalb des Blocks nicht berücksichtigt werden. Für Dokumente mit einer Tabelle, die aus Linien wie beispielsweise horizontalen und vertikalen Linien gebildet werden, ist es wünschenswert, die Tabellenanordnung bestehend aus diesen Linien ganz einfach nicht zu berücksichtigen, wodurch zur Erkennung nur die darin befindlichen alphanumerischen Zeichen verbleiben. Wie beschrieben wird solch eine Linien-, Block- und Tabellen-Beseitigung elektronisch mit den Bilddaten ausgeführt, die aus der Abtastung des Dokuments erhalten werden.
Typischerweise sind Bilddaten in der Form von Pixelinformation, die dann in eine bitlörmige Darstellung des abgetasteten Dokuments übersetzt wird. Beispielsweise kann ein optischer Scanner eine Auflösung in der Größenordnung von 300 Punkten pro Inch aufweisen, so daß ein typisches Liniensegment eine Fläche der Bit-Abbildung entsprechend einer Breite von ungefähr vier Punkten und einer Länge aufweist, die durch die tatsächliche Länge der Linie festgelegt wird (beispielsweise belegt eine ein Inch lange Linie einen Bereich der Größenordnung von ungefähr 4 x 300 Punkten). Vor kurzem vorgeschlagene Linien-Erfassungstechniken umfassen das sogenannte Fünf-Linien- Verfahren, das Konturvektor-Paarmitten-Erfassungsverfahren, das richtungsweise Schwarzlauf-Kurzmitten-Erfassungsverfahren, das Bogenverfolgungs-Verfahren, das Randverteilungs-Erfassungsverfahren und das Liniendichten-Erfassungsverfahren. Viele dieser Techniken erfordern die Erfassung der Koordinaten der Start- und Endpunkte der Linien, und solche Koordinaten können leicht aus der bitweisen Darstellung erhalten werden. Indessen macht die uneinheitliche Dicke der Linie, die verschiedene Punktdichten ergibt, die genaue Erfassung der Linie durch die zuvor genannten Verfahren schwierig, wenn nicht sogar unmöglich. Beispielsweise kann die Linie an manchen Positionen eine Breite von nur einem Punkt aufweisen, an anderen Positionen kann die Linie eine Breite von zwei Punkten aufweisen, an noch weiteren Positionen kann die Linie eine Breite von drei Punkten aufweisen, usw. Daher kann die Linie elektronisch nicht korrekt gelöscht werden, was wiederum wesentliche Fehler bei der Zeichenerkennung ergibt.
Vor kurzem erfolgte Vorschläge zur Mustererfassung, wie beispielsweise dem Gitter einer Tabelle oder dem Umriß eines Blocks, wurden im wesentlichen auf Dokumente angewendet, bei denen Graphikinformation, wie beispielsweise Zeichnungen oder Photographien innerhalb der Tabelle oder des Blocks enthalten sind. Solche Vorschläge, unter die das sogenannte Randverteilungs-Verfahren und das sogenannte vergrößerte Kontraktions-Verfahren fallen, hatten wenig Erfolg, wenn sie auf solche Dokumente angewendet wurden, bei denen alphanumerische Zeichen innerhalb der Tabelle oder des Blocks eingeschlossen waren.
Aus der EP-A-0 177 823 ist ein Verfahren zur Auswahl von horizontalen und/oder vertikalen Linien in digitalisierten Bildern bekannt, wobei horizontale und vertikale Bit- Folgen (strings) erfaßt werden, die einen vorbestimmten Schwellenwert überschreiten. Für jeden von diesem erfaßten Bit-String zu untersuchenden Bildpunkt wird ein Muster gewonnen. Ein Bitmuster wird aus diesem Muster ermittelt.
Daher ist es Aufgabe der vorliegenden Erfindung, eine verbesserte Technik (Verfahren und Vorrichtung) zur Erfassung von Linien in einem abgetasteten Dokument zu schaffen, die die Nachteile, Mängel und Unzulänglichkeiten der bekannten Vorschläge beseitigt.
Es ist ein weiterer Gegenstand dieser Erfindung, eine verbesserte Technik zur Erfassung von Liniensegmenten in gespeicherten Bilddaten zu schaffen, auch wenn solche Liniendaten geneigt und von uneinheitlicher Dicke sind.
Es ist ein noch weiterer Gegenstand dieser Erfindung, eine verbesserte Technik zur Erfassung und Bestimmung der Größe und Position von jeder Tabelle, Block oder Linienmuster zu schaffen, die in gespeicherten Bilddaten vorhanden sein können, die aus einem optisch abgetasteten Dokument erhalten wurden.
Ein noch weiterer Gegenstand dieser Erfindung ist es, eine Technik zu schaffen, die die Zeichenerkennung verbessert und erhöht.
Gemäß dieser Erfindung werden wie durch die Ansprüche festgelegt Liniensegmentdaten aus Bilddaten erfaßt, die Linien- und Zeichenindices darstellen, die von einem optisch abgetasteten Dokument erhalten wurden. Linienelemente werden aus den Bilddaten erfaßt und die Länge eines Linienelementes wird mit einer Schwellenlänge lth verglichen. Der Bezug zwischen einem Linienelement, das größer als die Länge lth ist, mit einem weiteren Linienelement, das eine Länge größer als lth aufweist, wird bestimmt, und ein Liniensegment wird gemäß der bestimmten Beziehung identifiziert.
Wenn zwei Linienelemente vertikal um weniger als einen vorbestimmten Wert δV getrennt sind, wird identifiziert, daß diese beiden Linienelemente in einem Liniensegment enthalten sind.
Die horizontale Beziehung zwischen diesen Linienelementen, die vertikal um weniger als δV getrennt sind, wird bestimmt. Genauer gesagt, wenn die horizontale Position des Startpunktes von einem Linienelement an oder zwischen den horizontalen Positionen des Start- und Endpunktes eines angrenzenden Linienelementes angeordnet ist, wird angenommen, daß beide Linienelemente Teil eines gemeinsamen Liniensegmentes sind.
Gemäß einem Aspekt dieser Erfindung wird die Trennung zwischen angrenzenden Linienelementen, wenn vorhanden, bestimmt, und wenn diese Trennung weniger als einen vorbestimmten Wert δd beträgt, werden die getrennten Linienelemente zur Bildung eines erfaßten Linienelementes verbunden.
Gemäß einem weiteren Aspekt dieser Erfindung wird der durch das identifizierte Liniensegment belegte Bereich durch Erweiterung der horizontalen Positionierung des Startpunktes von einem Linienelement vergrößert, so daß er im wesentlichen gleich der horizontalen Position des Startpunktes eines weiteren Linienelementes ist, sowie durch Erweiterung der horizontalen Positionierung des Endpunktes des weiteren Linienelementes, so daß es im wesentlichen gleich der horizontalen Position des Endpunktes des zuerst genannten Linienelementes ist. Das Liniensegment, das den somit vergrößerten Bereich belegt, kann dann elektronisch aus den gespeicherten Bilddaten beseitigt werden, wodurch im wesentlichen nur die zu erkennenden Zeichenindices zurückbleiben.
Gemäß einem weiteren Merkmal dieser Erfindung werden die gespeicherten Bilddaten effektiv um ungefähr 90º gedreht und dann werden die Linienelemente aus den gedrehten Bilddaten erfaßt. Die Länge von jedem solchen Linienelement wird festgelegt, und wenn diese Länge größer als lth ist, wird die Verbindungsbeziehung von einem Linienelement mit der Länge größer als lth zu einem weiteren Linienelement der Länge größer als lth bestimmt. Dann wird ein Liniensegment entsprechend der Verbindungsbeziehung dieser Linienelemente identifiziert. Als Ergebnis werden horizontale und vertikale Liniensegmente identifiziert.
Gemäß einem Aspekt dieses Merkmals wird die angrenzende Beziehung zwischen horizontalen und vertikalen Liniensegmenten festgelegt, und das aus solchen Liniensegmenten gebildete spezielle Muster wird abhängig von der Angrenzungsbeziehung identifiziert.
Gemäß einem Aspekt dieses Merkmals wird die Angrenzungsbeziehung durch die Effassung festgelegt, ob horizontale und vertikale Liniensegmente sich kreuzen, zusammenlaufen oder einen Winkel zueinander bilden. Das aus diesen Liniensegmenten gebildete Muster wird als Tabellenmuster identifiziert, wenn sich die Segmente kreuzen oder zusammenlaufen, als Blockmuster, wenn die Segmente eine Ecke bilden und als Linienmuster, wenn sich die Segmente nicht verbinden.
Gemäß einem weiteren Aspekt dieser Erfindung wird die Angrenzungsbeziehung von mehreren horizontalen und vertikalen Liniensegmenten bestimmt, und abhängig von den speziellen Segmenten, die sich kreuzen, zusammenlaufen oder Ecken bilden, wird die Größe und die Position von jedem Tabellen-, Block- und Linienmuster in dem abgetasteten Dokument bestimmt.
Gemäß einem bevorzugten Ausführungsbeispiel dieser Erfindung wird ein Prozessor, wie beispielsweise eine CPU, ein Mikroprozessor oder dergleichen, zur Ausführung dieser oben genannten Funktionen programmiert.
Wenn bezugnehmend auf Linienelemente, Liniensegmente oder Richtung die Ausdrücke "horizontal" und "vertikal" verwendet werden, sollten sie im weiten Sinne interpretiert werden und mussen nicht nur auf Richtungen parallel bzw. senkrecht zu dem Horizont beschränkt werden. Horizontal und vertikal sind so zu verstehen, daß sie sich auf zwei orthogonale Achsen beziehen. Dennoch werden der Einfachheit halber und zum besseren Verständnis der vorliegenden Erfindung die Bezeichnungen "horizontal" und "vertikal" durchgehend verwendet, um dem Leser eine schnelle Erfassung von Richtungen in einem abgetasteten Dokument zu ermöglichen.
Die folgende detaillierte und beispielsweise Beschreibung, die nicht zur Beschränkung der vorliegenden Erfindung gedacht ist, wird am besten in Verbindung mit den begleitenden Zeichnungen ersichtlich. Es zeigen:
Fig. 1A bis 1C zusammen ein Flußdiagramm, das darstellt, wie Liniensegmente gemäß der vorliegenden Erfindung zur Erleichterung von Zeichenerkennung erfaßt und verarbeitet werden;
Fig. 2 eine schematische Darstellung von verschiedenen Anordnungen von Linienelementen, wie sie durch einen optischen Abtastkopf (Scanner) erfaßt werden können;
Fig. 3 eine schematische Darstellung der horizontalen Verbindungsbeziehung von Linienelementen, die ein Liniensegment bilden können;
Fig. 4 eine schematische Darstellung der vertikalen Verbindungsbeziehung von Linienelementen, die ein Liniensegment bilden können;
Fig. 5A bis 5G schematische Darstellungen von verschiedenen Verbindungsbeziehungen von Linienelementen, die dennoch ein Liniensegment bilden;
Fig. 6 eine schematische Darstellung, wie der durch Linienelemente, die in einem gemeinsamen Liniensegment eingeschlossen sind, festgelegte Bereich zur Vorbereitung expandiert wird, um aus Bilddaten entfernt zu werden, um die Zeichenerkennung zu erleichtern;
Fig. 7A und 7B schematische Darstellungen, wie der durch ein Vielfachelement- Liniensegment besetzte Bereich trotz einer Neigung nach rechts oder links des Segmentes expandiert wird;
Fig. 8A bis 8C schematisch die Angrenzungsbeziehung von horizontalen und vertikalen Liniensegmenten, die in vorbestimmten Mustern angeordnet sind; und
Fig. 9A bis 9C die Muster, die abhängig von den in Fig. 8A bis 8C dargestellten Angrenzungsbeziehungen erfaßt werden.
Wie oben genannt findet die vorliegende Erfindung ihre Anwendung bei Zeichenerkennungssystemen. Der Zweck der Erfindung liegt in der Erfassung von Linien, wie beispielsweise einer Unterstreichung von Zeichen, dem Netzwerk einer Tabelle oder des Umrisses eines Blockes, und dann in der wirksamen Entfernung dieser Linien zur Erleichterung der genauen Zeichenerkennung. Die genaue Technik oder der Algorithmus, der für die Zeichenerkennung verwendet wird, stellt keinen Teil der vorliegenden Erfindung als solcher dar. Genauso ist die Weise, in der Bilddaten, die Linien- und Zeichenindices wiedergeben, von einem Dokument ermittelt werden, bekannt. Somit können optische Abtasttechniken, die für den Fachmann bekannt sind, zur Abtastung eines Dokuments, Erzeugung von Bilddaten, die dieses Dokument wiedergeben, und zur Speicherung dieser Bilddaten zur Liniensegment-Erfassung, Linienlöschung und Zeichenerkennung verwendet werden. Verzeichnisse, die aus dem abgetasteten Dokument erfaßt werden, sind beispielsweise als Pixel dargestellt, und eine geeignete Speichervorrichtung, wie beispielsweise ein RAM, dient als Bitplan-Speicher entsprechend solchen Pixel-Bilddaten.
Bekannte Abtastvorrichtungen werden zur Abtastung eines Dokuments verwendet, und gemäß einem Ausführungsbeispiel weist der Scanner eine Auflösung in der Größenordnung von ungefähr 300 Punkten pro Inch (dpi) auf. Diese Abtastpunkte bilden die Pixel, die wiederum in eine Bitplan-Wiedergabe des abgetasteten Dokuments umgesetzt werden. Ein geeigneter programmierbarer Prozessor (oder eine CPU), wie beispielsweise ein Mikroprozessor, wie beispielsweise ein herkömmlicher Mikroprozessor von Intel Corp., Motorola Corp., Hitachi, NEC oder dergleichen, verarbeitet die Bilddaten zur Erfassung von Linienelementen, Liniensegmenten, Tabellen- oder Blockmustern, und zur Erkennung von Zeichen, die durch die Bilddaten wiedergegeben werden. Da die Abtastung und Speicherung der Bilddaten, die von dem optisch abgetasteten Dokument erhalten werden, bekannt ist, erfolgt keine weitere Beschreibung und Darstellung der Vorrichtungen, die zur Erhaltung und Speicherung dieser Bilddaten verwendet werden.
Dementsprechend zielt die Beschreibung der vorliegenden Erfindung genauer gesagt auf den Vorgang des Prozessors, der die durch die Flußdiagramme von Fig. 1A, 1B und 1C dargestellten Abläufe (Routinen) mit den gespeicherten Bilddaten ausführt. Bezugnehmend auf Fig. 1A beginnt der Ablauf mit der Anweisung 202, durch die die gespeicherten Bilddaten so verarbeitet werden, daß die horizontalen und vertikalen Koordinatenpositionen von jedem Pixel identifiziert werden. Die Ausdrücke "horizontal" und "vertikal" sollen die oben genannte weit gefaßte Bedeutung haben. Somit sind die horizontalen und vertikalen Koordinatenpositionen die Koordinatenwerte, die den jeweiligen Pixeln in der Bitplan-Darstellung des abgetasteten Dokuments zugeordnet sind. Unter der Annahme, daß das Dokument aus einem dunklen Verzeichnis auf einem hellen Hintergrund besteht, stellt die Binärzahl "1" das dunkle Verzeichnis an einer Bitplan- Position dar und eine Binärzahl "0" gibt den Hintergrund wieder.
Nach der Verarbeitung der gespeicherten Bilddaten geht der Ablauf zur Anweisung 204 zur Erfassung und Identifizierung von einzelnen Linienelementen. Beispielsweise weisen mehrere angrenzende Pixel, die im wesentlichen in der horizontalen Richtung angeordnet sind, ein Linienelement auf Fig. 3 stellt Linienelemente B5, B6, B7, B8 und B9 dar. Es ist ersichtlich, daß jedes dieser Linienelemente aus mehreren kontinuierlichen Pixeln gebildet ist. Als weiteres Beispiel kann jedes soche Linienelement eine Breite oder Dicke von nur einem Punkt aufweisen (es wird daran erinnert, daß gemäß einem Ausführungsbeispiel der optische Scanner, der zur Abtastung des Dokuments verwendet wird, eine Auflösung in der Größenordnung von 300 dpi ermöglicht). Dementsprechend dient die Anweisung 204 zur Erfassung und Identifizierung von Linienelementen B5 bis B9 wie in Fig. 3 gezeigt.
Der dargestellte Ablauf geht dann zur Anweisung 206, so daß der Prozessor zu dem nächsten Linienelement weitergeht. Bei dem vorliegenden Beispiel ist angenommen, daß die Pixel, die das Linienelement B5 bilden, untersucht werden, und dann geht der Prozessor zu dem nächsten Linienelement B6. Die Abfrage 208 erfolgt dann, um festzulegen, ob die Trennung Δd&sub1; zwischen diesen angrenzenden Linienelementen B5 und B6 weniger als einen vorbestimmten Wert δd beträgt. Wenn diese Abfrage bestätigend beantwortet wird, wie es der Fall ist, wenn die Trennung (Abstand) zwischen den Elementen B5 und B6 weniger als δd beträgt, geht der Ablauf zur Anweisung 210 zur Verbindung dieser Elemente. Somit wird der Raum zwischen den Linienelementen B5 und B6 in dem Bitplan "ausgefüllt".
Danach erfolgt die Abftage 211, um zu bestimmen, ob weitere Linienelemente in dieser horizontalen Achse untersucht werden sollen. Wenn dies der Fall ist, geht der Ablauf zur Anweisung 206 zurück und die zuvor genannten Vorgänge, die durch die Abftage 208, die Anweisung 210 und die Abftage 211 dargestellt sind, werden wiederholt. Als Ergebnis dieser Schleife werden die Linienelemente B5, B6, B7 und B8 verbunden, da angenommen wird, daß die Trennung Δd&sub1;, Δd&sub2; und Δd&sub3; zwischen diesen Linienelementen jeweils weniger als δd beträgt. Die verbundenen Elemente B5 bis B8 bilden ein Linienelement L&sub1; mit einer Länge l&sub1;.
Nachdem wie zuvor gesagt zu dem Element B8 weitergegangen wurde und das Element B8 mit dem Element B7 zur Bildung der Linie L&sub1; verbunden wurde, erfolgt nochmals die Abfrage 211. Aus Fig. 3 ist zu sehen, daß noch ein weiteres Element B9 auf seine Untersuchung wartet. Daher wird nach der Verbindung des Elementes B8 mit dem Element B7 die Abfrage 211 bestätigend beantwortet und der Ablauf geht zur Anweisung 206 zurück und schreitet zu dem nächsten Element B9 weiter. Es ist ersichtlich, daß das Element B9 von dem Element B8 um den Abstand Δd&sub4; getrennt ist. Die Abfrage 208 erfolgt, um festzulegen, ob dieser Abstand Δd&sub4; weniger als δd beträgt. Es sei angenommen, daß der vorbestimmte Wert δd acht Punkten der Scanner-Auflösung entspricht. In dem in Fig. 3 dargestellten Beispiel ist die Trennung Δd&sub4; größer als acht Punkte. Dementsprechend wird die Abfrage 208 bei der Abfrage des Elements B9 negativ beantwortet. Der Ablauf geht dann zur Abfrage bei 211 weiter, ob noch weitere Linienelemente auf dieser horizontalen Achse zur Untersuchung verbleiben. In dem in Fig. 3 dargestellten Beispiel wird angenommen, daß die Abftage 211 negativ beantwortet wird.
In diesem Stadium des beschriebenen Ablaufs wird ein Linienelement L&sub1; mit einer Länge l&sub1; gebildet, sowie ein Linienelement L&sub2; mit einer Länge l&sub2;. Der Ablauf geht dann zur Abfrage 212, um festzulegen, ob die Länge von jedem dieser Linienelemente größer als ein Schwellenwert lth ist. Somit wird die Länge l&sub1; mit der Schwellenwertlänge lth verglichen und die Länge l&sub2; wird mit der Schwellenwertlänge lth verglichen. Gemäß einem Ausführungsbeispiel ist die Schwellenwertlänge lth gleich ungefähr 90 Punkten der Scanner-Auflösung, was somit die Unterscheidung einer Unterstreichung von einem Gedankenstrich "-" gestattet. Wenn die Länge eines Linienelementes L größer als die Schwellenwertlänge lth ist, wird dieses Linienelement weiterhin als ein Linienelement identifiziert. Wenn indessen die Länge des Linienelementes L nicht größer als die Schwellenwertlänge lth ist, wird dieses Element nicht mehr als Linienelement identifiziert.
Wenn die Abfrage 212 negativ beantwortet wird, d.h. wenn die Länge 1 des Linienelementes L weniger als der Schwellenwert lth beträgt, wird das Linienelement L deklassifiziert, d.h. es wird nicht länger als Linienelement erkannt, und der Ablauf geht zur Anweisung 206 zurück. Wenn indessen die Abflage 212 bestätigend beantwortet wird, wird das Linienelement L weiterhin als Linienelement klassifiziert. Der Prozessor geht dann zur Abfrage bei 214, ob ein weiteres Element ähnlich den zuvor genannten Elementen B5, B6, usw., in der "Nähe" eines klassifizierten Linienelements L vorliegt. Beispielsweise bezugnehmend auf Fig. 2, wenn ein Linienelement B1 erfaßt wurde, legt die Abfrage 214 fest, ob ein weiteres Linienelement, wie beispielsweise ein Linienelement B2 vorliegt, das von dem Linienelement B1 in der Nähe von diesem, aber mit Abstand, vorliegt. Wenn die Abfrage 214 negativ beantwortet wird, d.h. wenn keine weiteren Linienelemente in der Nähe des festgelegten Linienelements B1 vorliegen, geht der Ablauf zur Anweisung 216 weiter, um dieses festgelegte Linienelement B1 als Liniensegment zu bezeichnen. Der Ablauf geht dann zur Anweisung 206 zurück und der vorhergehende Vorgang wird wiederholt.
Wenn die Abfrage 214 bestätigend beantwortet wird, wie es der Fall sein wird, wenn ein Linienelement B2 erfaßt wird, nachdem das Linienelement B1 erfaßt wurde, geht der Prozessor zur Abfrage bei 218, ob die vertikale Trennung ΔV zwischen diesen Linienelementen B1 und B2 weniger als einen vorgewählten Wert δV beträgt. Beispielsweise bezugnehmend auf Fig. 4, wenn ein Linienelement L&sub4; in der Nähe des gerade bestimmten Linienelements L&sub3; vorliegt, aber diese beiden Linienelemente zwar nahe einander, aber nicht angrenzend liegen (d.h. sie liegen nahe beieinander, aber "berühren" sich nicht), dann wird die vertikale Trennung ΔV erfaßt. Es ist ersichtlich, daß Linienelemente L&sub3; und L&sub4; vertikal getrennt sein können, da die Linienelemente verschmiert sein können oder aufgrund spezieller Merkmale des Scanners. Dennoch, wenn diese beiden Linienelemente L&sub3; und L&sub4; ausreichend nahe zueinander liegen, sind diese Linienelemente Teil des gleichen Liniensegments. Wenn beispielsweise ΔV< 2 Punkte ist, dann können die beiden Liniensegmente L&sub3; und L&sub4; als in dem gleichen Liniensegment eingeschlossen angesehen werden.
Fig. 4 stellt die Weise dar, wie die Länge 1 eines Liniensegments gemessen werden kann. Nach der Verbindung von Liniensegmenten, die getrennt sein können, wie bei der Verbindung der Liniensegmente B5 und bis B8 zur Bildung eines Linienelements L&sub1;, oder nach der Bestimmung, daß ein getrenntes Element nicht verbunden werden soll, wie das Linienelement L&sub2;, kann die Länge von jedem Linienelement durch Erfassung der horizontalen Koordinatenposition seines Startpunktes und der horizontalen Koordinatenposition eines Endpunktes gemessen werden. Beispielsweise ist angenommen, daß das Linienelement L&sub3; eine horizontale Linie mit horizontaler bzw. vertikaler Koordinatenposition X3st und Y&sub3; zur Festlegung seines Startpunktes und mit einer horizontalen bzw. vertikalen Koordinatenposition X3ed und Y&sub3; zur Festlegung seines Endpunktes ist. Die Differenz zwischen diesen Koordinaten und insbesondere die Differenz zwischen der horizontalen Koordinate X3st des Startpunktes und der horizontalen Koordinate X3ed des Endpunktes kann leicht bestimmt werden. Somit wird die Länge des Linienelementes L&sub3; gemessen.
Wenn die vertikale Trennung ΔV zwischen Linienelementen L&sub3; und L&sub4; weniger als δV beträgt, wird die Abftage 218 bestätigend beantwortet und der Ablauf geht zur Abftage 220 weiter. Wenn indessen die Abfrage 218 negativ beantwortet wird, d.h. wenn die vertikale Trennung ΔV zwischen Linienelementen L&sub3; und L&sub4; den vorbestimmten Wert δV überschreitet, geht der Ablauf zur Anweisung 216 und das Linienelement L&sub3; wird als Liniensegment bezeichnet. Dann geht der Ablauf zur Anweisung 206 zurück, so daß ein Linienelement L&sub4; als nächstes untersucht und in der oben beschriebenen Weise verarbeitet wird.
Wenn indessen die Abfrage 218 bestätigend beantwortet wird, wie es der Fall ist, wenn die vertikale Trennung zwischen Linienelementen L&sub3; und L&sub4; weniger als δV beträgt, geht der Ablauf zur Abfrage bei 220 weiter, ob diese Elemente eines der in Fig. 5A bis 5G gezeigten Verbindungsmuster aufweisen. Diese Verbindungsmuster stellen die verschiedenen Verbindungsbeziehungen von einem Linienelement mit einem weiteren dar (es sei angenommen, daß natürlich jedes der Linienelemente eine Länge größer als den Schwellenwert lth aufweist). Es ist ersichtlich, daß diese Verbindungsbeziehungen die Möglichkeit berücksichtigen, daß ein Linienelement in der Nachbarschaft eines weiteren länger als das andere Linienelement sein kann, bezüglich diesem nach links oder nach rechts verschoben sein kann. Auch wenn Fig. 5A bis 5G die Verbindungsbeziehung zwischen zwei angrenzenden Linienelementen darstellen, ist ersichtlich, daß die Verbindungsbeziehung von mehreren Elementen, die ein gemeinsames Liniensegment bilden, in der gleichen Weise wie die Verbindungsbeziehung nur zwischen zwei Linienelementen bestimmt werden kann. Beispielsweise können vier Linienelemente B1 bis B4 in Fig. 2A, 2B oder 2C dargestellten Verbindungsbeziehungen aufweisen, aber dennoch weist die Verbindungsbeziehung von einem Linienelement mit dem nächsten eine der in Fig. 5A bis 5G gezeigten Möglichkeiten auf. Das heißt vier separate Linienelemente B1 bis B4 können die in Fig. 2A gezeigte "aufeinanderliegende" vertikale Beziehung aufweisen, wobei einige Elemente länger als andere sind. Alternativ können die vertikal angeordneten Linienelemente B1 bis B4 eine "Neigung" nach rechts aufweisen, wie in Fig. 2B gezeigt ist, oder eine "Neigung" nach links, wie in Fig. 2C gezeigt ist. Ein Liniensegment, das aus mehreren Linienelementen besteht, weist eine Neigung auf, wenn diese Linienelemente nicht genau längs der horizontalen Abtastachse ausgerichtet sind. Es wird dann erwartet, daß in vielen Anwendungen eine Neigung dieser Linienelemente erfaßt werden wird.
Durch einen Vergleich der Figuren 2A bis 2C mit den Figuren 5A bis 5G ist zu sehen, daß aufeinanderliegende ungleiche Linienelemente des in Fig. 2A gezeigten Typs der Anordnung von Linienelementen entsprechen, die in Fig. 5C und 5F dargestellt sind, die Neigung der Linienelemente nach rechts entspricht wie in Fig. 2B gezeigt der Anordnung, die in Fig. 5A und 5B gezeigt ist, und die Neigung nach links, die in Fig. 2C gezeigt ist, entspricht Fig. 5D und 5E.
Eine Abfrage 220 wird durch Erfassen ausgeführt, ob die horizontale Koordinate des Startpunktes von einem Linienelement an oder zwischen den horizontalen Koordinaten des Start- und des Endpunktes eines vertikal angrenzenden Linienelementes liegt. Somit und bezüglich der horizontalen Koordinaten davon stellt Fig. 5A den Startpunkt eines Linienelements L&sub6; dar, das zwischen dem Start- und dem Endpunkt eines Linienelementes L&sub5; vorgesehen ist. Dies ist ähnlich der Beziehung zwischen Linienelementen B1 und B2 in Fig. 2A und 2B. Fig. 5B zeigt den Startpunkt eines Linienelements L&sub1;&sub0;, das an dem Endpunkt eines Linienelements L&sub9; angeordnet ist. Fig. 5B zeigt den Startpunkt eines Linienelements L&sub7;, das zwischen dem Startpunkt und Endpunkt eines Linienelements L&sub8; angeordnet ist. Dies gleicht der Beziehung zwischen Linienelementen B2 und B3 in Fig. 2A sowie der Beziehung zwischen Linienelementen B 1 und B2 oder zwischen B2 und B3 oder zwischen B3 und B4 in Fig. 2C. Fig. 5E zeigt den Startpunkt eines Linienelements L&sub1;&sub1;, der an dem Endpunkt eines Linienelements L&sub1;&sub2; angeordnet ist.
Fig. 5C zeigt den Startpunkt eines Linienelements L&sub1;&sub4;, der zwischen dem Start- und dem Endpunkt eines Linienelements L&sub1;&sub3; liegt. In gleicher Weise zeigt Fig. 5F den Startpunkt eines Linienelements L&sub1;&sub5;, der zwischen Start- und Endpunkt eines Linienelements L&sub1;&sub6; liegt. Die Beziehung zwischen Linienelementen B3 und B4 in Fig. 2A ist ähnlich zu sehen wie die Verbindungsbeziehung zwischen Linienelementen L&sub1;&sub3; und L&sub1;&sub4; in Fig. 5C.
Schließlich stellt Fig. 5G eine zusammengesetzte Verbindungsbeziehung zwischen Linienelementen L&sub1;&sub7;, L&sub1;&sub8; und L&sub1;&sub9; dar. Es sei angenommen, daß jedes dieser Linienelemente eine Länge größer als den Schwellenwert Lth aufweist und daß die vertikale Trennung zwischen dem Linienelement L&sub1;&sub7; und jedem der Linienelemente L&sub1;&sub8; und L&sub1;&sub9; weniger als δV beträgt, wobei ersichtlich ist, daß Elemente L&sub1;&sub7; und L&sub1;&sub8; in dem gleichen Liniensegment enthalten sind, da der Startpunkt des Elementes L&sub1;&sub8; zwischen dem Startpunkt und dem Endpunkt des Linienelements L&sub1;&sub7; liegt. In gleicher Weise sind Elemente L&sub1;&sub7; und L&sub1;&sub9; in dem gleichen Segment enthalten, da der Startpunkt des Elementes L&sub1;&sub9; zwischen dem Start- und dem Endpunkt des Elementes L&sub1;&sub7; liegt. Gemäß einem Ausführungsbeispiel, auch wenn die Trennung Δd zwischen Elementen L&sub1;&sub8; und L&sub1;&sub9; größer als δd sein kann, werden diese Elemente dennoch zu einem gemeinsamen Segment verbunden aufgrund der Beziehung von jedem zu dem Element L&sub1;&sub7;.
Wenn vertikal beabstandete Linienelemente keinem der in Fig. 5 gezeigten Verbindungsmuster entsprechen, wird die Abfrage 220 negativ beantwortet und der Ablauf geht zur Anweisung 216 zurück. Somit werden die vertikal beabstandeten Elemente separat als einzelne Liniensegmente bezeichnet. Wenn aber die Abfrage 220 bestätigend beantwortet wird, wird das Liniensegment bestehend aus diesen einzelnen Linienelementen, wie beispielsweise das Liniensegment 10 von Fig. 2A, das Liniensegment 11 von Fig. 2B, das Liniensegment 12 von Fig. 2C oder jegliches andere der Liniensegmente, die durch die Linienelemente dargestellt werden, die die Verbindungsmuster aufweisen, die in Fig. 5A bis 5G gezeigt sind, als ein Liniensegment bezeichnet, wie es durch die Anweisung 222 wiedergegeben wird.
Danach geht der Ablauf zur Abfrage 224 weiter, um zu bestimmen, ob weitere Linienelemente in den Bildplan-Bilddaten zu untersuchen sind. Wenn dies der Fall ist, geht der Ablauf zur Anweisung 206 zurück und der vorhergehende Vorgang wird wiederholt. Wenn indessen sämtliche Linienelemente untersucht wurden, geht der Prozessor zu dem in Fig. 1B dargestellten Ablauf weiter.
Bevor mit einer Erläuterung des in Fig. 1B dargestellten Flußdiagrammes fortgefahren wird, erfolgt eine weitere Erläuterung hinsichtlich der Bezeichnung von Liniensegmenten. Wie oben genannt identifiziert der Prozessor die individuellen Linienelemente, die zusammen ein Liniensegment bilden. Beispiele von solchen Liniensegmenten sind in Fig. 2A bis 2C gezeigt. Vorzugsweise werden die vertikal angeordneten Linienelemente, die in einem gemeinsamen Liniensegment enthalten sind, durch ihre jeweilige Abtast-Zeilenzahl, die auch ihren vertikalen Koordinaten Yi entspricht, zusammen mit den Startpunkt- und Endpunkt-Koordinaten von jedem Liniensegment identifiziert, wie beispielsweise den horizontalen Koordinaten Xst bzw. Xed. Wenn die Bitplan-Darstellung der Bilddaten aus Spalten und Zeilen aufgebaut gedacht ist, dann können die jeweiligen X- und Y- Koordinaten von den Elementen, die ein Liniensegment bilden, in einer Segmenttabelle wie folgt gespeichert werden:
Nachdem die jeweiligen Liniensegmente identifiziert, bezeichnet und beispielsweise in einer Durchsichtstabelle gespeichert sind, wird der Bereich, der durch jedes Liniensegment belegt wird, expandiert, um Rauschanteile einzufassen, die oft in der Nähe von verschiedenen der erfaßten Linienelemente vorliegen und die als Artefakte, wie beispielsweise fehlerhafte Bits erscheinen, die als dunkle Bereiche wiedergegeben werden. Es wird daran erinnert, daß die Liniensegmente gemäß der vorliegenden Erfindung identifiziert werden, um sie aus der Bitplan-Darstellung des abgetasteten Dokuments zu löschen, um somit die Zeichenerkennung zu erleichtern. Durch Erweiterung des tatsächlich durch jedes bezeichnete Liniensegment belegten Bereichs können die genannten Artefakte oder "das Rauschen" wirksam beseitigt werden.
Bezugnehmend nun auf das in Fig. 1B gezeigte Flußdiagramm wird nun erläutert, in welcher Weise der durch ein identifiziertes Liniensegment belegte Bereich vergrößert wird. Die Anweisung 226 wird ausgeführt, um die Grenze von jedem Linienelement, das in dem Segment enthalten ist, zu expandieren, um ein vergrößertes Liniensegment zu bilden. Fig. 6 zeigt schematisch, wie die Grenzen der jeweiligen Linienelemente expandiert werden. Es sei angenommen, daß Linienelemente L&sub1;, L&sub2;, L&sub3;, L&sub4; und L&sub5; ein Liniensegment bilden. Es sei weiterhin angenommen, daß Artefakte oder Rauschen N angrenzend an verschiedenen dieser Linienelemente auftritt. Die Grenzerweiterung der jeweiligen Linienelemente wird wie folgt ausgeführt:
Die horizontale Position des Startpunktes des Linienelementes L&sub2; wird erweitert, so daß sie im wesentlichen gleich der horizontalen Position des Startpunktes des Linienelementes L&sub1; ist, wie durch die unterbrochene Linie angrenzend an den Startpunkt des Elementes L&sub2; dargestellt ist. Zusätzlich wird die horizontale Position des Endpunktes des Linienelementes L&sub1; expandiert, so daß sie im wesentlichen gleich der horizontalen Position des Endpunktes des Linienelementes L&sub2; ist. Dies ist ebenfalls durch die unterbrochene Linie in der Nähe des Endpunktes des Elementes L&sub1; dargestellt.
In einer ahnlichen Weise wird die horizontale Position des Startpunktes des Linienelementes L&sub3; erweitert, so daß sie im wesentlichen gleich der horizontalen Position des Startpunktes des Linienelementes L&sub2; ist, und die horizontale Position des Endpunktes des Linienelementes L&sub2; wird erweitert, so daß sie im wesentlichen gleich der horizontalen Position des Endpunktes des Linienelementes L&sub3; ist. Dieser Vorgang wird für jedes der Linienelemente wiederholt, wodurch der Bereich, der tatsächlich durch das Liniensegment belegt wird, erweitert wird, so daß er die Artefakte oder das Rauschen N einschließt. Wenn daher das flächenerweiterte Liniensegment aus der gespeicherten Bitplan- Anordnung des abgetasteten Dokuments beseitigt wird, verbleiben die Artefakte N nicht.
Wenn erwunscht können die oberen und unteren vertikalen Grenzen der tatsächlich durch das Liniensegment belegten Fläche beispielsweise um eine Abtastzeile erweitert werden. Somit und wie in Fig. 6 gezeigt kann die Abtastlinie oberhalb des Linienelementes L&sub1;, die als leer angenommen sei, in der Bitplan-Anordnung dunkel dargestellt werden, und in gleicher Weise kann die Abtastlinie unterhalb des Linienelementes L&sub5;, die ebenfalls als leer angenommen sei, in gleicher Weise dunkel dargestellt werden. Als Ergebnis werden die obere und untere Grenze des durch das expandierte Segment belegten Bereichs vergrößert, wie durch die unterbrochenen Linien dargestellt ist.
Fig. 7A und 7B sind vereinfachte Darstellungen, wie der Bereich eines Liniensegments mit einer Neigung nach rechts oder einer Neigung nach links, der aus drei Linienelementen L&sub1; bis L&sub3; gebildet wird, expandiert wird. Das mittlere Linienelement L&sub2; wird erweitert, so daß sein Startpunkt mit dem Startpunkt des oberen Linienelementes L&sub1; ausgerichtet ist und sein Endpunkt mit dem Endpunkt des unteren Linienelementes L&sub3; ausgerichtet ist. Der Endpunkt des oberen Linienelementes L&sub1; wird erweitert, so daß er mit dem Endpunkt des mittleren Linienelementes L&sub2; ausgerichtet ist, und der Startpunkt des unteren Linienelementes L&sub3; wird erweitert, so daß er mit dem Startpunkt des mittleren Linienelementes L&sub2; ausgerichtet ist.
Nach der Expandierung des Bereichs, der durch das Liniensegment belegt ist, geht der Prozessor zur Anweisung 228 weiter, wodurch der erweiterte Bereich von jedem Liniensegment aus der gespeicherten Bitplan-Anordnung gelöscht wird. Somit können Unterstreichungen und Artefakte in der Nähe von Unterstreichungen gelöscht werden, um die Erkennung der in den Bilddaten verbleibenden Zeichen zu erleichtern. Selbst wenn die Unterstreichung eine Neigung wie in Fig. 2B und 2C, 6 und 7 dargestellt aufweist, können solche geneigten Liniensegmente dennoch wirksam gelöscht werden. Bei Bedarf und abhängig von der Verwendung und den Funktionen des Systems, in dem der vorher beschriebene Prozessor verwendet wird, kann jedes identifizierte Liniensegment von einer Position des Dokuments zu einer weiteren bewegt werden, oder es kann neu orientiert, vergrößert oder verkleinert werden.
Das oben in Verbindung mit Fig. 1A erläuterte Flußdiagramm dient zur Identifizierung von horizontalen Liniensegmenten. Vertikale Liniensegmente können unter Verwendung des gleichen Algorithmus verwendet werden, indem nur die gespeicherten Bilddaten effektiv um 90º gedreht werden. Solch eine Datenrotation ist eine Funktion, die leicht durch einen bekannten Algorithmus ausgeführt wird. Somit können sowohl horizontale wie auch vertikale Liniensegmente erfaßt werden. Zur Erfassung solcher vertikalen Liniensegmente wird der in Fig. 1A dargestellte Ablauf durch den Prozessor wiederholt, beispielsweise nachdem die Abftage 224 (Fig. 1A) negativ beantwortet ist, und dies ist in Fig. 1C dargestellt.
Wie in Fig. 1C dargestellt wird die Anweisung 326 ausgeführt, wobei die abgetasteten Bilddaten um 90º gedreht werden und dann wird der in Fig. 1A dargestellte Ablauf wiederholt, um die jeweiligen vertikalen Liniensegmente zu identifizieren und zu bezeichnen, die in dem Dokument vorliegen können. Es ist ersichtlich, daß eine Durchsichtstabelle ähnlich der vorher genannten Segmenttabelle zur Identifizierung von jedem vertikalen Liniensegment erzeugt werden kann. In solch einer vertikalen Segmenttabelle entspricht die Abtast-Zeilenzahl der x-Koordinate und die Start- und Endpunkte von jeder vertikalen Linie entsprechen jeweils y-Koordinaten.
Der Zweck des in Fig. 1 C gezeigten Flußdiagramms ist die Erfassung von speziellen Mustern, die aus den horizontalen und vertikalen Liniensegmenten gebildet werden können. In dem beschriebenen Ausführungsbeispiel sind diese erfaßten Muster bekannt als "Tabellenmuster", die aus einem Gitter von horizontalen und vertikalen Liniensegmenten gebildet werden, als "Blockmuster", das aus dem Umriß aus horizontalen und vertikalen Liniensegmenten gebildet wird, und als "Linienmuster", das ganz einfach aus einem horizontalen oder vertikalen Liniensegment gebildet wird (d.h., eines, das kein orthogonales Liniensegment berührt).
Nach Identifizierung der jeweiligen horizontalen und vertikalen Liniensegmente geht der Prozessor zur Anweisung 328 weiter, um das nächste horizontale Liniensegment zu untersuchen, das identifiziert wurde (oder in der Segmenttabelle gespeichert wurde). Zuerst wird natürlich das erste identifizierte Liniensegment untersucht. Dann wird die Anfrage 330 ausgeführt, um zu bestimmen, ob dieses horizontale Liniensegment ein vertikales Liniensegment kreuzt. Genauer gesagt wird die Angrenzungsbeziehung zwischen diesem horizontalen Liniensegment und einem vertikalen Liniensegment untersucht, um zu bestimmen, ob es von dem in Fig. 8 gezeigten Typ ist. Es wird daran erinnert, daß jedes Liniensegment als Funktion seiner horizontalen und vertikalen Koordinaten identifiziert und bezeichnet werden kann, wie sie in der obigen Segmenttabelle wiedergegeben sind. Dementsprechend werden zur Bestimmung, ob ein horizontales Liniensegment ein vertikales Liniensegment kreuzt, die Koordinaten des Start- und des Endpunktes von diesen Liniensegmenten untersucht. Beispielsweise sei angenommen, daß das horizontale Liniensegment durch L1h mit Startpunkt-Koordinaten (x1hst, y1hst) und Endpunkt-Koordinaten (x1hed, y1hed) wiedergegeben wird. Es sei weiterhin angenommen, daß das vertikale Liniensegment, dessen Angrenzungsbeziehung untersucht wird, durch L1v mit Startpunkt-Koordinaten (x1vst, y1vst) und Endpunkt-Koordinaten (x1ved, y1ved) wiedergegeben wird.
Wenn nun die horizontalen und vertikalen Koordinaten des Startpunktes der vertikalen Linie L1v größer als die horizontalen und vertikalen Koordinaten des horizontalen Liniensegments L1h sind, und wenn die horizontalen und vertikalen Koordinaten des Endpunktes des horizontalen Liniensegments L1h größer als die horizontalen und vertikalen Koordinaten des Endpunktes des vertikalen Liniensegments L1v sind, dann schneiden sich diese Liniensegmente. Genauer gesagt bilden die folgenden Gleichungen eine Angrenzungsbeziehung, die aus sich schneidenden Liniensegmenten gebildet werden:
x1hst< x1vst und y1hst< y1vst und x1ved< x1hed und y1ved< y1hed.
Wenn die vorhergehenden Bedingungen erfüllt sind, wird die Anfrage 330 bestätigend beantwortet und der Ablauf geht zur Anweisung 336 weiter, um diese beiden Liniensegmente L1h und L1v als Teil eines Gitters zu identifizieren, das eine Tabelle bildet.
Wenn indessen die Anfrage 330 negativ beantwortet wird, erfolgt die Anfrage 332, um zu bestimmen, ob das horizontale Liniensegment, das untersucht wird, mit einem vertikalen Liniensegment verbunden ist. Fig. 8C zeigt zwei Verbindungspunkte, die aus einem vertikalen Liniensegment L4v gebildet werden, das an ein horizontales Liniensegment L4h angrenzt und das weiterhin an ein horizontales Liniensegment L5h angrenzt. Ein Vergleich von Fig. 8A und 8C ergibt, daß ein Verbindungspunkt sich von einem Schnittpunkt darin unterscheidet, daß sich die horizontalen und vertikalen Liniensegmente, die einen Verbindungspunkt bilden, nicht schneiden.
Ein Verbindungspunkt wird bestimmt durch Erfassung, ob der Startpunkt von beispielsweise dem vertikalen Liniensegment L4v auf dem horizontalen Liniensegment L4h liegt, oder ob der Endpunkt des Liniensegments L4v auf dem horizontalen Liniensegment L5h liegt.
Es sei angeommen, daß das horizontale Liniensegment L4h aus den Startpunkt- Koordinaten (x4hst, y4hst) und den Endpunkt-Koordinaten (x4hed, y4hed) gebildet wird. In gleicher Weise sei angenommen, daß das horizontale Liniensegment L5h aus den Startpunkt-Koordinaten (x5hst, y5hst) und den Endpunkt-Koordinaten (x5hed, y5hed) gebildet wird. Schließlich sei angenommen, daß das vertikale Liniensegment L4v aus den Startpunkt-Koordinaten (x4vst, y4vst) und den Endpunkt-Koordinaten (x4ved, y4ved) gebildet wird. Ein Verbindungspunkt zwischen horizontalen und vertikalen Liniensegmenten wird durch die folgenden Bedingungen bestimmt:
4hst< x4vst< x4hed und y4hst=y4vst=y4hed
oder
x5hst< x4ved< x5hed und y5hst=y4ved=y5hed
Wenn die Abfrage 332 bestätigend beantwortet wird, geht der Ablauf zur Anweisung 336 und die Verbindungs-Liniensegmente werden als Teil des Gitters einer Tabelle identifiziert. Wenn indessen diese Abfrage negativ beantwortet wird, geht der Ablauf zur Abfrage 334 weiter.
Die Anfrage 334 legt fest, ob die Angrenzungsbeziehung zwischen einem horizontalen Liniensegment und einem vertikalen Liniensegment einen Eckpunkt bildet. Wie in Fig. 8B dargestellt bildet ein horizontales Liniensegment L2h einen Eckpunkt mit einem vertikalen Liniensegment L2v und weiterhin mit einem vertikalen Liniensegment L3v. In gleicher Weise bildet ein horizontales Liniensegment L3h einen Eckpunkt mit jedem der vertikalen Liniensegmente L2v und L3h. Das horizontale Liniensegment L2h wird durch Startpunkt- Koordinaten (x2hst, y2hst) und Endpunkt-Koordinaten (x2hed, y2hed) festgelegt. Das horizontale Liniensegment L3h wird aus den Startpunkt-Koordinaten (x3hst, Y3hst) und den Endpunkt-Koordinaten (x3hed, y3hed) festgelegt. In gleicher Weise wird das vertikale Liniensegment L2v aus den Startpunkt-Koordinaten (x2vst, y2vst) und den Endpunkt- Koordinaten (x2ved, y2ved) festgelegt. Schließlich wird das vertikale Liniensegment L3v aus den Startpunkt-Koordinaten (X3vst, y3vst) und den Endpunkt-Koordinaten (x3ved, y3ved) festgelegt. Wie aus Fig. 8B ersichtlich wird ein Eckpunkt durch eine der folgenden Bedingungen gebildet:
Wenn eine dieser Bedingungen erfüllt ist, wird die Anfrage 334 bestätigend beantwortet und der Ablauf geht zur Anweisung 338 weiter, um die angrenzenden horizontalen und vertikalen Liniensegmente als Teil eines Blockmusters zu identifizieren. Wenn indessen die Anfrage 334 negativ beantwortet wird, wird angenommen, daß weder ein Schnittpunkt noch ein Verbindungspunkt noch ein Eckpunkt vorliegt. Daher geht der Ablauf zur Anweisung 340 zur Identifizierung des untersuchten Liniensegments ganz einfach als eine Linie.
Durch die Abfragen 330 bis 334 und die Anweisungen 336 bis 340 kann das spezielle Muster, in dem das Liniensegment, das gerade untersucht wird, enthalten ist, bestimmt werden. Fig. 9 zeigt diese Muster als eine Tabelle, die als ein Netzwerk gezeigt ist, für den Fall, daß die Anweisung 336 ausgeführt wird, einen Block, der ganz einfach aus einem Umriß bestehend aus horizontalen und vertikalen Liniensegmenten gebildet wird, wenn die Anweisung 338 ausgeführt wird, und eine einfache Linie für den Fall, daß die Anweisung 340 ausgeführt wird. Es ist ersichtlich, daß die Umrißgrenzen der in Fig. 9B gezeigten Tabelle vorliegen, wenn die Anfrage 332 bestätigend beantwortet wird, und wenn diese Anfrage negativ beantwortet wird, dann enthält die Tabelle keine solche Außengrenze.
Nach der Ausführung der Anweisung 336 oder der Anweisung 338 oder der Anweisung 340 geht der Ablauf zur Abfrage bei 342 weiter, ob weitere Liniensegmente auf eine Untersuchung warten. Wenn dies der Fall ist, geht der Ablauf zur Anweisung 328 zurück, und der vorhergehende Vorgang wird wiederholt.
Wenn somit der Ablauf durch die Schleife von der Anweisung 328 zu der Abfrage 342 und dann zurück zu der Anweisung 328 geht, werden die Angrenzungsbeziehungen von jeweiligen horizontalen und vertikalen Liniensegmenten festgelegt. Daher werden jede Linie, jede Tabelle und jeder Block, der in dem Dokument vorliegen kann, identifiziert, und die jeweiligen Koordinatenpositionen von ihren Gesamtbestandteilen werden identifiziert.
Nachdem alle der zuvor identifizierten horizontalen und vertikalen Liniensegmente untersucht sind, wird die Anfrage 342 negativ beantwortet, und der Ablauf geht zur Anweisung 344 weiter, um die Größe und die Position von jeder Linie, Block und Tabelle zu bestimmen, die identifiziert wurden. Dadurch kann jedes solche Muster gelöscht werden, was die Erfassung von Zeichen erleichtert, die innerhalb oder angrenzend an die identifizierten Muster vorliegen können. Weiterhin können durch Identifizierung, Positionsbestimmung und Festlegung der Größe von jedem solchen Muster das Muster selbst separat verarbeitet werden, so daß es wiedergegeben, vergrößert oder verkleinert werden kann. Darüberhinaus kann für den Fall, daß das Zeichenerkennungsgerät, mit dem die vorliegende Erfindung verwendet wird, nicht zur Erkennung von Graphikfiguren, wie beispielsweise Photos verwendet werden kann, der Muster-Identifizierungsalgorithmus, der oben beschrieben ist, ganz einfach zur Vermeidung eines Versuchs zur Erkennung von Bilddaten verwendet werden, die in einem identifizierten Block oder Tabelle enthalten sind.
Auch wenn die obige Erfindung insbesondere bezugnehmend auf bevorzugte Ausführungsbeispiele gezeigt und beschrieben wurde, ist für den Fachmann ersichtlich, daß verschiedenartige Änderungen und Modifikationen ausgeführt werden können, ohne den Bereich der Erfindung zu verlassen. Beispielsweise wird bei den beschriebenen Ausführungsbeispielen nach der Untersuchung von einem Linienelement seine Nachbarschaft auf angrenzende Linienelemente untersucht, deren Verbindungsbeziehung bestimmt wird. Alternativ kann jede Abtastzeile, d.h. jede der Bitplan-Bilddaten, die im wesentlichen längs der horizontalen Achse angeordnet sind, untersucht werden, um zu bestimmen, ob die Abtastzeile ein oder mehrere Linienelemente enthält. Nachdem alle Abtastzeilen untersucht wurden, kann dann die vertikale Trennung und Verbindungsbeziehung zwischen Abtastzeilen festgelegt werden.
Es ist weiterhin ersichtlich, daß die in Fig. 1A bis 1C gezeigten Flußdiagramme zur allgemeinen Erläuterung dienen, wie der Prozessor arbeitet. Die speziellen Abfragen und Anweisungen, die in diesen Flußdiagrammen dargelegt sind, können verändert werden, ihre spezielle Reihenfolge oder Sequenz kann modifiziert werden und verschiedene Anfragen oder Anweisungen können weggelassen oder hinzugefügt werden. Beispielsweise kann in Fig. 1C die Anweisung 332 weggelassen werden.

Claims

1. Vorrichtung zur Erfassung von Liniensegmenten in gespeicherten Bilddaten, die Linien- und Zeichenindices wiedergeben, die aus einem optisch abgetasteten Dokument erhalten wurden, wobei die optische Abtasteinrichtung das Dokument abtastet und Bilddaten entsprechend dem Dokument erstellt, eine Speichereinrichtung, die Buildaten speichert und ein Prozessor Liniensegmente identifiziert, die sich vertikal in den gespeicherten Bilddaten erstrecken können, dadurch gekennzeichnet, daß der Prozessor so programmiert ist, daß er (a) Linienelemente, d.h. verbundene Pixel in einer horizontalen Linie aus den Bilddaten (202, 204, 206) erfaßt; (b) bestimmt, ob die Länge von einem Linienelement größer als eine Schwellenwert-Linie lth (212) ist; (c) eine Verbindungsbeziehung von einem Linienelement, das größer als die Schwellenwertlänge ist, mit einem weiteren Linienelement bestimmt, das größer als die Schwellenwertlänge (218, 220) ist; und (d) ein Liniensegment entsprechend der Verbindungsbeziehung der Linienelemente (216, 222) identifiziert, wobei der Prozessor eine Verbindungsbeziehung durch Bestimmung festlegt, ob eine vertikale Beziehung zwischen einem und weiteren Linienelementen weniger als einen vorbestimmten Wert δV (218) beträgt, und wenn dies der Fall ist und wenn eine vorbestimmte horizontale Beziehung zwischen diesen Linienelementen vorliegt, das Liniensegment als aus dem einen und weiteren Linienelementen (220, 222) bestehend identifiziert, wobei jedes Linienelement einen Start- und einen Endpunkt mit Koordinatenpositionen aufweist und der Prozessor die vorbestimmte horizontale Beziehung zwischen Linienelementen durch Festlegung bestimmt, ob die horizontalen Koordinatenposition des Startpunktes von einem Linienelement mit oder zwischen den Koordinatenpositionen des Start- und Endpunktes des weiteren Linienelementes (Fig. 5) liegt.

2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß der Prozessor Linienelemente durch die Bestimmung erfaßt, ob horizontal angrenzende Linienelemente voneinander getrennt sind, und wenn das der Fall ist, bestimmt, ob die Trennung weniger als einen vorbestimmten Wert δd (208) beträgt, und die Linienelemente, die um weniger als δd getrennt sind, zur Bildung eines erfaßten Linienelementes (210) verbindet.

3. Vorrichtung nach Anspruch 1 oder 2, bei der das identifizierte Liniensegment einen Bereich der gespeicherten Bilddaten belegt, dadurch gekennzeichnet, daß der Prozessor weiterhin so programmiert ist, daß er den Bereich durch Erweiterung der horizontalen Koordinatenposition des Startpunktes des einen Linienelementes, so daß er im wesentlichen gleich der horizontalen Koordinatenposition des weiteren Linienelementes ist, und durch Erweiterung der horizontalen Koordinatenposition des Endpunktes des weiteren Linienelementes erweitert, so daß er im wesentlichen gleich der horizontalen Koordinatenposition des Endpunktes des einen Linienelementes ist (226; Fig. 6 und 7).

4. Vorrichtung nach Anspruch 3, dadurch gekennzeichnet, daß der Prozessor weiterhin so programmiert ist, daß er aus den gespeicherten Bilddaten die Daten entsprechend dem vergrößerten Bereich des Liniensegmentes (228) entfernt.

5. Vorrichtung nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß der Prozessor weiterhin so programmiert ist, daß er die gespeicherten Bilddaten effektiv um ungefähr 90º (326) dreht und die Vorgänge (a) bis (d) wiederholt, wodurch er wenigstens ein horizontales Liniensegment und wenigstens ein vertikales Liniensegment identifiziert.

6. Vorrichtung nach Anspruch 5, dadurch gekennzeichnet, daß der Prozessor weiterhin so programmiert ist, daß eine Angrenzungsbeziehung zwischen den horizontalen und vertikalen Liniensegmenten, wenn vorhanden, bestimmt (328-334), und ein spezielles Muster von Liniensegmenten als Funktion der Angrenzungsbeziehung (326-340) identifiziert.

7. Vorrichtung nach Anspruch 6, dadurch gekennzeichnet, daß der Prozessor eine Angrenzungsbeziehung dadurch bestimmt, daß er bestimmt, ob die horizontalen und vertikalen Liniensegmente sich kreuzen (330) oder verbinden (332) oder eine Ecke (334) bilden und das spezielle Muster als Teil eines Tabellenmusters identifiziert, wenn sich die Liniensegmente kreuzen (336) als Teil eines Tabellenmusters, wenn sich die Liniensegmente verbinden (336) und als Teil eines Blockmusters, wenn die Liniensegmente eine Ecke (338) bilden.

8. Vorrichtung nach Anspruch 7, dadurch gekennzeichnet, daß der Prozessor eines der horizontalen und vertikalen Linensegmente als ein Liniensegment identifiziert, wenn es kein weiteres Liniensegment (334, 340) kreuzt, sich nicht mit diesem verbindet oder mit ihm keine Ecke bildet.

9. Verfahren zur Erfassung von Liniensegmenten, die sich vertikal in gespeicherten Bilddaten erstrecken können, die Linien- und Zeichenindices darstellen, die aus einem optisch abgetasteten Dokument erhalten werden, gekennzeichnet durch (a) Erfassung von Liniensegmenten, d.h. verbundenen Pixeln in einer horizontalen Linie, aus den Bilddaten (202, 204, 206); (b) Bestimmung, ob die Länge von einem Linienelement größer als eine Schwellenwert-Länge lth (212) ist; (c) Bestimmung einer Verbindungsbeziehung von einem Linienelement, das größer als die Schwellenwertlänge ist, mit einem weiteren Linienelement, das größer als die Schwellenwertlänge ist (218, 220); und (d) Identifizierung eines Liniensegmentes entsprechend der Verbindungsbeziehung der Linienelemente (216, 222), wobei eine Verbindungsbeziehung festgelegt wird durch Bestimmung, ob eine vertikale Trennung zwischen dem einen und weiteren Linienelementen kleiner als ein vorbestimmter Wert δV (218) ist, und wenn dem der Fall ist und eine vorbestimmte horizontale Beziehung zwischen diesen Linienelementen vorliegt, Identifizierung des Liniensegmentes als aus einem oder weiteren Linienelementen (220, 222) bestehend, wobei jedes Linienelement einen Start- und einen Endpunkt mit horizontalen und vertikalen Positionen aufweist und die vorbestimmte horizontale Beziehung durch die horizontale Position des Startpunktes von einem Linienelement bestimmt wird, das an einem oder zwischen den horizontalen Positionen des Start- und Endpunktes des anderen Linienelementes (Fig. 5) liegt.

10. Verfahren nach Anspruch 9, dadurch gekennzeichnet, daß die Linienelemente durch die Bestimmung erfaßt werden, ob horizontal angrenzende Linienelemente getrennt sind, und wenn dem der Fall ist, durch Bestimmung, ob die Trennung als ein vorbestimmter Wert δd (208) ist, und Verbindung der Linienelemente, die um weniger als δd getrennt sind, zur Bildung eines erfaßten Linienelementes (210).

11. Verfahren nach einem der Ansprüche 9 oder 10, gekennzeichnet durch eine Vergrößerung des identifizierten Liniensegmentes durch Erweiterung der horizontalen Position des Startpunktes des einen Linienelementes, so daß er im wesentlichen gleich der horizontalen Position des Startpunktes des weiteren Linienelementes ist, und durch Erweiterung der horizontalen Position des Endpunktes des weiteren Linienelementes, so daß er im wesentlichen gleich der horizontalen Position des Endpunktes des einen Linienelementes (Fig. 6 und 7) ist.

12. Verfahren nach Anspruch 11, gekennzeichnet durch eine Entfernung der Daten entsprechend dem vergrößerten Liniensegment (218) aus den gespeicherten Bilddaten.

13. Verfahren nach einem der Anspruche 9 bis 12, gekennzeichnet durch ein effektives Drehen der gespeicherten Bilddaten um ungefähr 90º, und durch Wiederholung der Schritte (a) bis (d), wodurch wenigstens ein horizontales Liniensegment und wenigstens ein vertikales Liniensegment (326) identifiziert werden.

14. Verfahren nach Anspruch 13, gekennzeichnet durch eine Bestimmung einer Angrenzungsbeziehung zwischen horizontalen und vertikalen Liniensegmenten (330-334), falls vorhanden, und Identifizierung eines speziellen Musters von Liniensegmenten abhängig von der Angrenzungsbeziehung (336-340).

15. Verfahren nach Anspruch 14, dadurch gekennzeichnet, daß eine Angrenzungsbeziehung dadurch festgelegt wird, daß bestimmt wird, ob die horizontalen und vertikalen Liniensegmente sich kreuzen (330) oder verbinden (332) oder eine Ecke (334) bilden, und bei dem das spezielle Muster als eine Tabelle erkannt wird, wenn die Liniensegmente sich kreuzen oder verbinden (336), oder als ein Blockmuster, wenn die Liniensegmente eine Ecke (338) bilden.