-
1. Technisches
Gebiet
-
Die vorliegende Erfindung bezieht
sich auf eine Linienrichtungsbestimmungsvorrichtung, eine Bildschrägeerfassungsvorrichtung
und eine Bildschrägekorrekturvorrichtung,
wobei diese alle angepasst sind, bei einer Verarbeitungsvorrichtung
für ein gedrucktes
Bild und einer Zeichenerkennungsvorrichtung verwendet zu werden.
-
2. Beschreibung des Stands
der Technik
-
Bei der Verarbeitung eines Bildes
eines gedruckten Originals ist es insbesondere zum Erkennen von
Zeichen darin sehr bedeutsam, die Richtung von Linien von Zeichen
darauf zu bestimmen, d.h., ob Zeichen in vertikalen Zeilen oder
horizontalen Zeilen gedruckt sind. Dies ist so, da die Zeichenextraktionsverarbeitung
in vielen Fällen
von der Richtung von Zeichenlinien abhängt.
-
Viele herkömmliche Verfahren zum Bestimmen
einer Linienrichtung verwenden die Randverteilung in vertikalen
und horizontalen Richtungen eines Eingabebildes. Ein typisches Verfahren
wird in Technical Reports of IEICE, Nr. PRL80-70, beschrieben, die
von The Institute of Electronics, Information and Communication
Engineer, herausgegeben werden.
-
Dieses Verfahren verwendet Leerlinien,
die von der Randverteilung extrahiert werden, die von einer vertikalen
Zeichenlinie und einer horizontalen Zeichenlinie abhängen.
-
Ein Linienrichtungsbestimmungsverfahren, das
die Randverteilung nicht verwendet, wurde ebenfalls beispielsweise
in der japanischen offengelegten Patentveröffentlichung Nr. 4-90082 vorgeschlagen. Dieses
Verfahren erstellt ein Histogramm einer Lauflänge von weißen Pixeln (Leerzeichen) in
vertikalen und horizontalen Richtungen und unterscheidet die Richtung
von Linien durch Vergleichen eines Peaks von weißen Pixeln in der vertikalen
Richtung mit einem Peak von weißen
Pixeln in der horizontalen Richtung. Das Verfahren basiert auf der
Tatsache, dass in horizontalen Zeilen getippte Zeichen eine kleinere
horizontale als vertikale Beabstandung aufweisen, während in
vertikalen Zeilen getippte Zeichen eine kleinere vertikale als horizontale
Beabstandung aufweisen.
-
In dem Artikel "A method of detecting the orientation
of aligned components" von
A. Hashizume u.a., Pattern Recognition Letters, NL, North-Holland Publ.
Amsterdam, Band 4, Nr. 2, 1. April 1986, Seiten 125 – 132 wird
ein Verfahren zum Erfassen der Linienrichtung eines Satzes von Komponenten
angegeben. Paare von nächsten
Komponenten werden mittels eines sogenannten Näherungsbaums bestimmt, und
Vektoren, die von einer Komponente zu dem nächsten Nachbarn zeigen, werden
hergeleitet. Als nächstes
wird ein Histogramm der Richtungen der Vektoren berechnet. Um den
Peak des Richtungshistogramms zu erfassen, wird ein Glättungsoperator mit
einer bestimmten Winkelmaskengröße auf das ursprüngliche
Richtungshistogramm angewendet.
-
In dem Artikel "The Skew Angle of Printed Documents" von Henry S. Baird,
SPSE Symposium on Hybrid Imaging Systems, Annual Conference, 1987,
Seiten 21 – 24
wird ein neuer Algorithmus zum Bestimmen des Winkels der Schiefe
von Zeilen von Text in einem Bild einer gedruckten Seite dargestellt. Jede
Stelle eines Zeichens wird durch den Mittelpunkt des Bodens seines
begrenzenden Kästchens definiert.
Für einen
gegebenen Winkel Q werden die Zahlen von Zeichen an gegebenen Projektionsabschnitten
akkumuliert, und die Quadrate dieser Zahlen werden addiert, um die "Energieausrichtungsfunktionen" A(Q) zu erhalten
(vgl. Zeilen 18 – 23
auf Seite 22). Diese Funktion A(Q) zeigt ein globales Maximum an
dem schrägen
Winkel des Dokuments.
-
In der europäischen Patentanmeldung
EP 0 434 415 A2 wird
das in dem Artikel von Henry S. Baird beschriebene Verfahren als
eine Referenz des Stands der Technik angeführt, und das Verfahren wird
in den
1A bis
1C dargestellt.
-
Die oben beschriebenen herkömmlichen
Linienrichtungsbestimmungsverfahren und Vorrichtungen beinhalten
jedoch die folgenden Probleme: Das erste Problem besteht darin,
dass das die Randverteilung verwendende Verfahren manchmal versagt, eine
korrekte Unterscheidung einer Zeichenlinienrichtung auf einem gedruckten
Bild mit einem komplizierten Layout der Zeichen darin zu erhalten.
Dies ist so, da die Randverteilung des gesamten Bereichs nicht immer
Leerzeichen um jeweilige Zeichenketten an einem Originalbild erfassen
kann, das einem komplizierten Layout von Zeichen darin aufweist.
-
Das zweite Problem besteht darin,
dass das die Lauflänge
von Leerzeichen verwendende Verfahren Information auf Läufen von
Leerzeichen aus einem weiten Bereich eines Eingabebildes extrahiert, was
nur für
die Linienrichtungsbestimmungsprozess nützlich ist und bei vielen Fällen für andere
Arten von Verarbeitung, z.B. der Zeichenerkennungsverarbeitung,
nicht verwendet werden kann. Mit anderen Worten müssen viel
Zeit und viele Betriebsressourcen zum Erhalten von Information verbraucht
werden, die nur zum Extrahieren der Richtung von Linien nützlich ist.
Dies verringert den Wirkungsgrad des Betriebs der Vorrichtung.
-
Das dritte Problem besteht darin,
dass das die Lauflänge
von Leerzeichen verwendende Verfahren auf erfassbare Linienrichtungen
begrenzt ist, wie es in 1 gezeigt
ist. Das heißt,
dass das Verfahren keine andere Richtung als die vertikalen 20 und
horizontalen 21 Richtungen und die einen Winkel von einem Mehrfachen
von 45° aufweisenden
Richtungen 22 und 23 unterscheiden kann, in denen Lauflängen natürlicherweise
bestimmt werden können.
Dies bedeutet, dass ein von einem gedruckten Blatt eingegebenes
Bild mit einem großen
Winkel der Schräge nicht
korrekt verarbeitet werden kann, ohne dass es vorher auf seine Schräge korrigiert
wird. Das Verfahren kann eine Schwierigkeit mit Bildern beinhalten, die
von einem handbetriebenen Scanner oder einer Kamera eingegeben werden,
die dazu tendieren, ohne weiteres schräg zu sein. Zum Unterscheiden der
Richtung mit einem Winkel eines Mehrfachen von 45° ist es notwendig,
auf das Bildspeichermittel (Bildspeicher) zum Berechnen einer Lauflänge in dieser Richtung
verglichen mit der Unterscheidung der horizontalen oder vertikalen
Richtung übermäßig zuzugreifen.
Das Abtasten des Bildspeichers bei einer Schräge führt zu einem weiteren Anstieg
der Verarbeitungszeit auf Grund des Zugreifens auf diskrete Adressen
darin durch Berechnen dieser Adressen. Natürlich kann das die vertikale
und horizontale Randverteilung verwendende Verfahren nicht jede Richtung
verschieden von der vertikalen und horizontalen Richtungen unterscheiden.
-
Das vierte Problem besteht darin,
dass sowohl die Verfahren, die die Randverteilung, als auch die,
die die Lauflänge
von Leerzeichen verwenden, auf erfassbare Linienrichtungen begrenzt
sind, und daher können
Verarbeitungsergebnisse, die von einem eingegebenen Bild durch diese
Verfahren erhalten werden, nicht zum Erfassen und/oder Korrigieren der
Schräge
des Bildes verwendet werden. Folglich muss die herkömmliche
Linienrichtungsbestimmungsvorrichtung mit einer getrennten Bildschrägeerfassungsvorrichtung
und einer getrennten Bildschrägekorrekturvorrichtung
ausgestattet sein. Dies macht das System groß und sehr kostspielig.
-
Demgemäß ist die vorliegende Erfindung
auf eine Linienrichtungsbestimmungsvorrichtung gerichtet, wie es
in Anspruch 1 definiert ist. Weitere Ausführungsformen sind in den abhängigen Ansprüchen definiert.
-
Im folgenden entspricht das, was "erste Ausführungsform" genannt wird, ungefähr der Abstandserfassung,
die in dem Dokument von Hashizume offenbart ist, d.h., dass es keine
Ausführungsform
der Erfindung ist. Auf ähnliche
Weise bilden die sogenannten "dritten" und "vierten" "Ausführungsformen" keinen Teil der
vorliegenden Erfindung.
-
KURZBESCHREIBUNG
DER ZEICHNUNGEN
-
In den Zeichnungen zeigt/zeigen:
-
1 eine
Ansicht zum Erläutern,
dass es nur in eingeschränkten
Richtungen möglich
ist, Lauflängen
natürlicher
zu definieren;
-
2 ein
Blockdiagramm, das einen Aufbau einer Vorrichtung zum Ausführen einer
ersten, zweiten und dritten Ausführungsform
der vorliegenden Erfindung zeigt;
-
3 ein
Ablaufdiagramm, das eine Verarbeitungsprozedur für die ersten, zweiten und dritten Ausführungsformen
der vorliegenden Erfindung zeigt;
-
4 einen
beispielhaften Aufbau eines Zeichenelement-Puffers, der bei der ersten Ausführungsform
der vorliegenden Erfindung verwendet wird;
-
5A, 5B, 5C und 5D Ansichten
zum Erläutern
eines Abstands zwischen Zeichenelementen bei der ersten Ausführungsform
der vorliegenden Erfindung;
-
6 einen
beispielhaften Aufbau eines Puffers für Zeichenelement-Abstandsdaten,
die bei der ersten Ausführungsform
der vorliegenden Erfindung verwendet werden;
-
7 zeigt
ein Beispiel einer Zahl-Richtungs-Tabelle, die bei der ersten Ausführungsform der
vorliegenden Erfindung verwendet wird;
-
8A, 8B, 8C und 8D Ansichten
zum Erläutern
eines Abstands zwischen Zeichenelementen bei der zweiten Ausführungsform
der vorliegenden Erfindung;
-
9 einen
beispielhaften Aufbau eines Puffers für Zeichenelement-Abstandsdaten,
die bei der zweiten Ausführungsform
der vorliegenden Erfindung verwendet werden;
-
10A, 10B und 10C Ansichten zum Erläutern eines Vorteils eines
Abstands zwischen Zeichenelementen bei der zweiten Ausführungsform
der vorliegenden Erfindung;
-
11A, 11B und 11C und 11D eines
beispielhaften Unterteilens des Umfangs eines Kreises in gleiche
Winkelteile bei der dritten Ausführungsform der
vorliegenden Erfindung;
-
12 einen
beispielhaften Aufbau eines Puffers für Zeichenelement-Abstandsdaten,
die bei der dritten Ausführungsform
der vorliegenden Erfindung verwendet werden;
-
13 ein
Beispiel einer Tabelle zum Speichern von Zahl-Richtungs-Daten, die bei der dritten Ausführungsform
der vorliegenden Erfindung verwendet werden;
-
14 ein
Blockdiagramm, das einen Aufbau einer Vorrichtung zum Ausführen einer
vierten Ausführungsform
der vorliegenden Erfindung zeigt;
-
15 ein
Ablaufdiagramm, das eine Verarbeitungsprozedur für die vierte Ausführungsform
der vorliegenden Erfindung zeigt;
-
16A und 16B Ansichten zum Erläutern mittels
Beispiel der Definition von Zeichenelement-Dichten in jeweiligen
Richtungen für
die vierte Ausführungsform
der vorliegenden Erfindung;
-
17 einen
beispielhaften Aufbau eines Zeichenelement-Dichtepuffers, der bei der vierten Ausführungsform
der vorliegenden Erfindung verwendet wird;
-
18 ein
Blockdiagramm, das einen Aufbau einer Vorrichtung zum Ausführen einer
fünften Ausführungsform
der vorliegenden Erfindung zeigt; und
-
19 ein
Ablaufdiagramm, das die Schritte zur Verarbeitung eines Bildes bei
der fünften
Ausführungsform
der vorliegenden Erfindung zeigt.
-
AUSFÜHRLICHE
BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORM
-
2 ist
ein Blockdiagramm einer Linienrichtungsbestimmungsvorrichtung, die
eine erste Ausführungsform
der vorliegenden Erfindung ist. 3 ist
ein Ablaufdiagramm, die Schritte der Verarbeitung eines eingegebenen
Bildes durch die erste Ausführungsform
der vorliegenden Erfindung zeigt.
-
Mit Bezug auf 2 und 3 wird
die erste Ausführungsform
der vorliegenden Erfindung nachstehend ausführlich beschrieben.
-
Eine auf einem Blatt von Papier gedruckte Bildinformation,
die darauf gedruckt ist, wird durch einen Bildeingabeabschnitt 1,
der aus einem Scanner oder einer Kamera aufgebaut ist, eingegeben
und in einem Bildspeicher 2 gespeichert (Schritt 301).
Der Inhalt des Bildspeichers 2 wird an eine Anzeigeeinheit 4 übertragen
(Schritt 302), die dann die empfangene Bilddaten auf einer
Anzeige 5 darstellt (Schritt 303).
-
Jeder Punkt auf dem eingegebenen
Bild wird hier nachstehend, falls notwendig, durch seine senkrechten
Abstände
(x, y) von den beiden Achsen eines pixelbasierten Koordinatensystems
lokalisiert, dessen Ursprung (0, 0) beispielsweise an dem obersten linken
Punkt des Bildes ist. Zeichenlinien auf dem Bild werden "horizontal" genannt, wenn die
Zeichen in horizontalen Zeilen geschrieben sind, und "vertikal" genannt, wenn die
Zeichen in vertikalen Zeilen geschrieben sind.
-
Ein Benutzer kennzeichnet einen verarbeitbaren
Bereich auf dem eingegebenen Bild durch Verwenden einer Tastatur 6 oder
einer Maus 7. Die spezifizierten Bereichsdaten werden in
der CPU 3 gespeichert (Schritt 304). In diesem
Fall sei angenommen, dass der verarbeitbare Bereich keine unterschiedlich
gerichteten Zeichenlinien umfasst. Dieser Bereich soll vorzugsweise
keine anderen Bereiche von z.B. eines Fotobildes oder eines mit
Linien gezeichneten Bildes enthalten. Der verarbeitbare Bildbereich
kann als ein Rechteck gekennzeichnet sein, das durch ein Paar von
Koordinaten (X0, Y0) seines obersten linken Punktes mit Koordinaten
(X1, Y1) eines untersten rechten Punktes spezifiziert ist. Dieser
Bereich kann ebenfalls durch Verwenden eines weiteren komplizierteren
Verfahrens gekennzeichnet sein. In diesem Fall wird die Bereichskennzeichnung
manuell durch den Benutzer durchgeführt, wobei sie jedoch automatisch
durch Anwenden irgendeiner der herkömmlichen automatischen Bereichsaufteilungsverfahren
durchgeführt
werden kann. Ein typisches Verfahren ist in der japanischen offengelegten
Patentveröffentlichung
Nr. 5-225378 beschrieben.
-
Die CPU 3 überträgt Positionsdaten
des spezifizierten verarbeitbaren Bildbereichs an einen Zeichenelement-Extraktionsabschnitt 8,
der seinerseits Zeichenelemente extrahiert, die sich auf den Inhalt des
Bildspeichers 2 beziehen, und die extrahierten Daten in
einem Zeichenelement-Puffer 9 speichert (Schritt 305).
Bei dieser Beschreibung wird die Zeichenelement-Extraktion für sogenannte
schwarze Pixel mit vorbestimmten Werten in der Praxis durchgeführt.
-
Der Zweck des Extrahierens von Zeichenelementen
besteht darin, zu prüfen,
in welcher Richtung Zeichen am dichtesten verteilt sind. Demgemäß ist die
Extraktion eines Zeichens selbst am besten, was jedoch schwierig
ist, da nicht vor der Zeichenerkennungsverarbeitung herausgefunden
werden kann, welches Teil eines Bildbereichs ein Zeichen zusammensetzt.
Daher werden Bildelemente, die als ein Zeichen aufbauende Teile
betrachtet werden, als Alternativen verwendet. Repräsentativ
ist ein bildverbindender Bereich, der durch ein Verfahren extrahiert werden
kann, das von Nagao in einem Buch, Image Recognition Theory, herausgegeben
von Colona Co., 1983, auf Seite 85 offenbart wird. Andere bekannte Verfahren
können
ebenfalls angewendet werden. Gemäß der vorliegenden
Erfindung ist es möglich, die
Richtung von Linien von Zeichen, alphanumerischen Zeichen und Symbolen
bei einem eingegebenen Bild zu bestimmen, ohne vorher eine Zeichenerkennungsverarbeitung
durchzuführen.
-
Ein Verfahren zum Erhalten eines
begrenzenden Rechtecks einer verbindenden Komponente, das von dem
vorliegenden Anmelder in der japanischen offengelegten Patentveröffentlichung
Nr. 5-51474 vorgeschlagen
wurde, kann angewendet werden, wenn es ausreichend ist, nur ein
begrenzendes Rechteck eines verbindenden Bereichs an einem eingegebenen
Bild zu kennen. Der Zeichenelement-Extraktionsbereich 8 extrahiert
ein begrenzendes Rechteck des verbindenden Bereichs durch Spezifizieren
eines Paars von Koordinaten seines obersten linken Punktes (sy,
sy) und untersten rechten Punktes (ex, ey) und speichert die gepaarten
Koordinaten in einem Zeichenelement-Puffer 9. Das begrenzende
Rechteck kann nicht auf den obigen Ausdruck beschränkt und
kann anders spezifiziert sein.
-
4 zeigt
ein Beispiel eines Aufbaus des Zeichenelement-Puffers 9, bei dem die Daten
zweidimensional gespeichert sind. D.h., dass vertikal angeordnete
Datensätze
jeweiligen Zeichenelementen und horizontal angeordnete Datensätze jeweiligen
x- und y-Koordinaten des obersten linken Endes und x- und y-Koordinaten
des untersten rechten Endes des begrenzenden Rechtecks des Zeichenelements
entsprechen. In 4 ist
ein begrenzendes Rechteck eines i-ten Zeichenelements (i = 0, 1,
..., N-1, wobei N die Zahl von Zeichenelementen ist) durch seine
Koordinaten des obersten linken Punktes von sx[i]) und sy[y]) und
die Koordinaten des untersten rechten Punktes von ex[i] und ey[i])
definiert.
-
Es ist natürlich, dass die Darstellung
des Zeichenelementes nicht auf das begrenzende Rechteck des verbindenden
Bereichs beschränkt
ist. Beispielsweise kann das Zeichenelement durch Koordinaten seines
Mittelpunktes oder Schwerpunkts anstatt der Koordinaten des begrenzenden
Rechtecks dargestellt werden. Außerdem ist es ebenfalls möglich, ein Zeichenelement
zu verwenden, das nicht auf die verbindende Komponente oder ein
begrenzendes Rechteck der Zeichenkomponente basiert, wie es durch
den vorliegenden Anmelder bei der japanischen offengelegten Patentanmeldung
Nr. 02-277185 offenbart ist. Es ist natürlich möglich, ein Zeichen selbst als
eine Zeichenkomponente zu verwenden, wenn das Zeichen von der getrennten
Vorrichtung extrahiert wurde. In diesem Fall kann der Zeichenelement-Extraktionsabschnitt 9 aus
dem Strukturblockdiagramm (2)
der Linienrichtungsbestimmungsvorrichtung weggelassen werden.
-
Ein Zeichenelement-Abstandsberechnungsabschnitt 10 berechnet
Abstände
jedes Zeichenelements von seinem Nachbarn in unterschiedlichen Richtungen
und speichert den kleinsten der berechneten Abstandswerte in einem
Zeichenelement-Abstandspuffer 11 (Schritt 306).
-
Es kann gesagt werden, dass je kleiner
der Abstand zwischen Zeichenelementen ist, desto dichter die Zeichenelemente
verteilt sind. Der Abstandswert ist in einer umgekehrten Beziehung
zu dem Zeichenelement-Dichtewert, wobei jedoch beide in der Substanz
gleich sind. Ein Zeichenelement-Abstand kann auf verschiedene Arten
definiert sein. Mit anderen Worten, es ist nicht immer notwendig,
einen Abstand zwischen zwei Zeichenelementen im Unterschied zu normalen
Abstandsmessungen zu definieren. Mit Bezug auf
5A bis
5D werden
Zeichenelementabstände
beispielsweise für
Zeichen
51 und
52 bestimmt.
Das Zeichenelement
51 wird durch
sx[0] sy[0], ex[0], ey[0] und das Zeichenelement
52 wird durch
sx[1], sy[1], ex[1], ey[1] dargestellt. Nur wenn die x-Koordinaten
Bereiche von zwei begrenzenden Rechtecke der Zeichenelemente überlappen,
wird ein Paar von nächsten
y-Koordinatenwerte
der nächsten
horizontalen Seiten beider Rechtecke ausgewählt, und eine Differenz zwischen diesen
y-Koordinatenwerten
wird als ein vertikaler Abstand zwischen den Zeichenelementen definiert.
5A zeigt einen derart definierten
Abstand, und
5B zeigt
einen nicht derart definierten Fall. Nur wenn die y-Koordinatenwertbereiche
der zwei begrenzenden Rechtecke der Zeichenelemente
51 und
52 überlappen
(in dem Fall von
5C), wird
ein Paar der nächsten
x-Koordinatenwerten der nächsten
vertikalen Seiten beider begrenzenden Rechtecke ausgewählt, und
eine Differenz zwischen diesen x-Koordinatenwerten wird als ein
horizontaler Abstand (sx[1]-ex[0]) zwischen den Zeichenelementen
definiert.
5C zeigt
einen derart definierten Abstand, und
5D zeigt
einen nicht derart definierten Fall. Nur wenn die x-Koordinatenbereiche
der zwei begrenzenden Rechtecke der Zeichenelemente überlappen
(in dem Fall von
5A),
wird ein Paar von nächsten
x-Koordinatenwerten
der nächsten
horizontalen Seiten beider Rechtecke ausgewählt, und eine Differenz zwischen
den x-Koordinatenwerten wird
als ein vertikaler Abstand (sy[1]-ey[0]) zwischen den Zeichenelementen
definiert.
-
Bei den oben erwähnten Fällen werden die Zeichenlinien
in eine von zwei Richtungen – horizontal
und vertikal – gebracht.
Obgleich Ausführungsformen
ebenfalls beschrieben werden, um zu unterscheiden, ob Zeichenlinien
horizontal oder vertikal sind, kann die Definition eines Abstands
zwischen zwei Zeichenelementen auf das obige begrenzt sein, und
andere Linienrichtungen als die vertikalen und horizontalen Richtungen
können
ebenfalls abhängig von
der unterschiedlichen Definition von Zeichenelementabständen unterschieden
werden.
-
6 zeigt
einen beispielhaften Aufbau des Zeichenelement-Abstandpuffers 11, der angepasst ist,
um die Abstandsdaten von 5A bis 5D zu speichern. Der Puffer 11 speichert
die Daten zweidimensional. D.h., dass vertikal angeordnete Datensätze jeweiligen
Zeichenelementen und horizontal angeordnete Datensätze den
kürzesten
horizontalen und vertikalen Abständen
eines Zeichenelements zu seinen Nachbarn in den jeweiligen Richtungen
entsprechen. Bei dem Puffer 11 wird ein i-tes Zeichenelement
(i = 0, 1, ..., N-1, wobei N die Anzahl von Zeichenelementen ist)
durch den kürzesten
horizontalen Abstand D(i)(0) zu einem Nachbarn in der horizontalen
Richtung und den kürzesten
vertikalen Abstand D[i][1] zu einem Nachbarn in der vertikalen Richtung festlegt.
-
Der Zeichenelement-Abstandsberechnungsabschnitt 10 berechnet
Abstände
jedes Zeichenelements von Nachbarn in jeweiligen Richtungen mit
Bezug auf den Inhalt des Zeichenelementspuffers 9 und speichert
den kleinsten der berechneten Abstandswerte in einem Zeichenelement-Abstandspuffer 11 gemäß der folgenden
Prozedur:
- (1) Jedes Element D[i][j] (i = 0,
1, ... N-1, J = 0) wird mit einem Wert UD initialisiert, der gleich max(1x,
1y) ist, wobei 1x eine horizontale Breite und 1y eine vertikale
Höhe eines
verarbeitbaren Bereichs ist.
- (2) i = 0
- (3) J = 0
- (4) k = 0
- (5) Ein Abstand zwischen einem i-ten Zeichenelement und einem
j-ten Zeichenelement wird in der Richtung k (k = 0 ist eine horizontale
Richtung und k = 1 ist eine vertikale Richtung) berechnet.
- (6) Wenn ein Wert D definiert wurde, wird D[i][k] = min (D[i][k],
d) bestimmt. D.h., dass D[i][k] um d aktualisiert wird, wenn d kleiner
als das aktuelle D[i][k] ist.
- (7) k = k + 1
- (8) Der Prozess kehrt zu Schritt (5) zurück, wenn k kleiner als 2 ist.
- (9) j = j + 1
- (10) j+ = 1, wenn j= = 1.
- (11) Der Prozess kehrt zu Schritt (4) zurück, wenn j kleiner als N ist.
- (12) i = i + 1
- (13) Der Prozess kehrt zu Schritt (3) zurück, wenn i kleiner als N ist.
-
In Unterschied zu normalen Abstandsmessungen
wird der Zeichenelement-Abstand nicht zwischen zwei optionalen Zeichenelementen
definiert, wie es oben beschrieben ist, und es ist möglich, dass nicht
jeder Abstand zwischen benachbarten Zeichenelementen in bestimmten
Richtungen definiert sein kann. Daher kann es einen derartigen Fall
geben, dass kein Abstand zwischen nächsten Nachbarn definiert ist.
In diesem Fall kann ein Wert, der sich offensichtlich von allen
definierten Abständen
unterscheidet, als undefinierte Abstandsdaten für ein entsprechendes Element
D[i][j] gespeichert werden. Bei der Ausführungsform der vorliegenden
Erfindung verwendet der Zeichenelement-Abstandsberechnungsabschnitt 10 UD
= max(1x, 1y) (wobei 1x eine verarbeitbare Bereichsbreite in der
horizontalen Richtung und 1y eine verarbeitbare Bereichshöhe in der
vertikalen Richtung ist), um undefinierte horizontale und vertikale
Abstände
gemeinsam darzustellen, wie es vorhergehend in der Prozedur des
Abschnitts 10 beschrieben wurde. Die Verwendung eines derartigen außergewöhnlichen
Werts gemeinsam für
undefinierte horizontale und vertikale Abstände ermöglicht, dass alle gespeicherten
Werte ohne Unterschied behandelt werden, wenn die kürzesten
Abstände
in unterschiedlichen Richtungen durch Vergleichen der gespeicherten
Daten bestimmt werden. Jeder Wert ist verwendbar, um einen undefinierten
Abstand darzustellen, wenn es ein praktisch unmöglicher Abstand ist. Es ist
ebenfalls möglich,
alle Abstandsdaten mit einem Flag zu versehen, das definiert oder undefiniert
angibt. Ein Flag entspricht einen Datensatz in dem Zeichenelement-Puffer 9 oder
dem Zeichenelement-Abstandspuffer 11.
-
Jeder UD-Wert (undefined distance
value = undefinierter Abstandswert) kann die gleiche Wirkung aufweisen,
wie es oben beschrieben ist, wenn er größer als ein möglicher
Abstandswert ist und gemeinsam für
undefinierte horizontale und vertikale Abstände verwendet wird.
-
Da sehr kleine oder sehr große Zeichenelemente
zum Unterscheiden eines Abstands zwischen Zeichen nicht erwünscht sind,
speichert der Zeichenelement-Abstandsberechnungsabschnitt 10 den UD-Wert
in D[i][0] und D[i][1] für
derartige unerwünschte
Zeichenelemente und ignoriert die unerwünschten Zeichenelemente, wenn
ein nächstes
Zeichenelement von einem normalen Zeichenelement gesucht wird.
-
In dem Fall, wenn die zum Unterscheiden
der Richtung von Linien extrahierten Zeichenelementen nicht in einer
Nachverarbeitungsstufe verwendet werden, ist es möglich, die
unerwünschten
Zeichenelemente vorher aus dem Zeichenelement-Puffer 9 zu entfernen. Ein
Kriterium zum Unterscheiden der unerwünschten Zeichenelemente kann
eine geeignete Schwelle oder eine bestimmte Differenz von dem Mittelwert
sein. Es ist ebenfalls möglich,
eine Form oder ein anderes geeignetes Kriterium als die obigen Größenbegriffe
zu verwenden.
-
Ein Linienrichtungs-Bestimmungsabschnitt 12 prüft die Häufigkeit
von kurzen Abständen
zwischen Zeichenelementen in horizontalen und vertikalen Richtungen
mit Bezug auf den Inhalt des Zeichenelement-Abstandspuffers 11 und
entscheidet durch Mehrheit, dass die horizontale oder vertikale
Richtung dichter mit Zeichenelementen ist (Schritt 307).
-
D.h., dass der Linienrichtungsabschnitt 12 zuerst
die Zahl M[0] und die Zahl M[1] für jedes i (i = 0, 1, ..., N-1,
wobei N die Zahl von Zeichenelementen ist) zählt, dessen Abstandswerte die
Bedingungen erfüllen: D[i][0] < D[i][1]
und D[i][0] > D[i][1].
-
M[0] und M[1] können anders als oben definiert
sein. Beispielsweise ist es ebenfalls möglich, das Zählen von
M[0] und M[1] für
ein Zeichenelement i wegzulassen, das keine bestimmte oder größere Differenz
zwischen D[i][0] und D[i][1] aufweisen kann.
-
Als nächstes bestimmt der Abschnitt 12 einen
Wert j0, bei dem M[j0] = max (M[0], M[1]) erhalten wird . Dies dient
dazu, die Richtung zu suchen, in der die höchste Häufigkeit der kurzen Abstände von Zeichenelementen
erhalten wird. Wenn es mehrere j0 gibt, betrachtet der Abschnitt 12 diese
Bestimmung als unmöglich
und setzt j0 gleich der Anzahl möglicher
Richtungen (2 in diesem Fall).
-
Die Korrelation zwischen einem Wert
M[] und einer Linienrichtung kann anders als oben definiert sein.
Beispielsweise kann der Abschnitt 12 immer anstatt der
Beurteilung "Bestimmung
ist unmöglich" einen numerischen
Code ausgeben, der eine der beiden Richtungen angibt, und. eine
Differenz zwischen der Häufigkeit
der beiden Richtungen getrennt ausgeben, um die Wahrscheinlichkeit
der Richtung der höchsten
Häufigkeit
mit Bezug auf die Richtung der zweiten Häufigkeit anzugeben.
-
Schließlich wandelt der Linienrichtungs-Bestimmungsabschnitt 12 den
Wert j0, der die Richtung der höchsten
Häufigkeit
angibt, oder eine andere Information (z.B., dass die Bestimmung
unmöglich
ist) in einen Winkel der Linienrichtung oder anderen Informationscode
mit Bezug auf die Zahl-Richtungs-Tabelle 13 um
und gibt den umgewandelten Wert aus (Schritt 308). Die
Zahl-Richtungs-Tabelle 13 wird beispielsweise in 7 gezeigt. Die Ausgabe des
Linienrichtungs-Bestimmungsabschnitts 12 wird an eine Anzeigeeinheit 4 übertragen,
wie es in 2 gezeigt ist.
Natürlich
kann die Ausgabe der Linienrichtungs-Bestimmungsvorrichtung durch eine geeignete getrennte
Schnittstelle an jede andere Vorrichtung, wie beispielsweise eine
Zeichenerkennungsvorrichtung, die die Information benötigt, übertragen
werden.
-
<Zweite Betriebsart zum Ausführen der
Erfindung>
-
Bei einer anderen (zweiten) Ausführungsform
der vorliegenden Erfindung wird die Definition eines Abstands zwischen
Zeichenelementen, die bei der ersten Ausführungsform verwendet wird,
so modifiziert, dass die Bestimmung der Linienrichtung eine höhere Genauigkeit
erlangen kann. Mit gemeinsamen Bezug auf 2 und 3 wird
die Differenz der zweiten Ausführungsform
von der ersten Ausführungsform
nachstehend beschrieben. Andere Abschnitte der Ausführungsform
sind denjenigen der ersten Ausführungsform ähnlich.
-
Ein Zeichenelement-Abstandsberechnungsabschnitt 10 berechnet
Abstände
jedes Zeichenelements von seinen Nachbarn in unterschiedlichen Richtungen
mit Bezug auf den Inhalt des Zeichenelement-Puffers 9 und
speichert den kleinsten der berechneten Abstandswerte in einem Zeichenelement-Abstandspuffer 11 (Schritt 306).
Bei diesem Schritt machte die erste Ausführungsform keinen Unterschied
in der Position des nächsten
Nachbars bezüglich
des Zeichenelements (hier nachstehend "Zeichenelement I" genannt), beispielsweise rechts oder links
von dem Zeichenelement I in der horizontalen Richtung oder über oder
unter in der vertikalen Richtung. Im Gegensatz dazu unterscheidet
die zweite Ausführungsform
die relative Position (Orientierung) des Nachbars in den Richtungen.
Mit anderen Worten wählt
die erste Ausführungsform
für jedes
Zeichenelement I die nächsten
Nachbarn aus, einen in der horizontalen Richtung und einen in der
vertikalen Richtung, und vergleicht die Abstände, die von den nächsten Nachbarn
in den jeweiligen Richtungen bestimmt wurden. Im Gegensatz dazu
berechnet die zweite Ausführungsform
Abstände
von dem Element I zu dem nächsten
Nachbarn, die über
und unter (in entgegengesetzter Richtung) in der vertikalen Richtung
und links und rechts (in jeder entgegengesetzten Richtung) in der
horizontalen Richtung angeordnet sind, und verwendet einen größeren der
beiden Abstände
(in jeder entgegengesetzten Richtung), die in jeweiligen (den vertikalen
und horizontalen) Richtungen als die vertikalen und horizontalen
Abstandswerte gemessen wurde, anstatt der durch die erste Ausführungsform
definierten vertikalen und horizontalen Abstandswerte.
-
Mit Bezug auf 8A bis 8D wird
ein Verfahren zum Bestimmen eines Abstands von einem Zeichenelement
(I), der als ein Bezug zu den über,
unter, links bzw. rechts positionierten Zeichenelementen II dient,
wie folgt beschrieben:
- (1) Nur in dem Fall,
wenn zwei Zeichenelemente I und II eine Überlappung ihrer x-Koordinatenbereiche
jedoch keine Überlappung
ihrer y-Koordinatenbereiche aufweisen, und der y-Koordinatenwert jedes in dem Element
II enthaltenen Punkts kleiner als der y-Koordinatenwert jedes in
dem Element I enthaltenen Punkts ist (d.h., dass das Element II über dem
Element I existiert), wird ein Abstand nach oben von dem Element
I zu dem Element II als eine Differenz zwischen dem y-Koordinatenwert
der oberen Seite eines begrenzenden Rechtecks des Elements I und
dem y-Koordinatenwert der unteren Seite eines begrenzenden Rechtecks
des Elements II definiert (wie es in 8A gezeigt
ist).
- (2) Nur in dem Fall, wenn zwei Zeichenelemente I und II eine Überlappung
ihrer x-Koordinatenbereiche jedoch keine Überlappung ihrer y-Koordinatenbereiche
aufweisen, und der y-Koordinatenwert
jedes in dem Element II enthaltenen Punktes größer als der y-Koordinatenwert
jedes in dem Element I enthaltenen Punktes ist (d.h., dass das Element
II unter dem Element I existiert), wird ein Abstand nach unten von
dem Element I zu dem Element II als eine Differenz zwischen dem
y-Koordinatenwert der unteren Seite eines begrenzenden Rechtecks
des Elements I und des y-Koordinatenwerts der oberen Seite eines
begrenzenden Rechtecks des Elements II definiert (wie es in 8B gezeigt ist).
- (3) Nur in dem Fall, wenn zwei Zeichenelemente I und II eine Überlappung
ihrer y-Koordinatenbereiche, jedoch keine Überlappung ihrer x-Koordinatenbereiche
aufweisen, und der x-Koordinatenwert
jedes in dem Element II enthaltenen Punktes kleiner als der x-Koordinatenwert
jedes in dem Element I enthaltenen Punktes ist (d.h., dass das Element
II an der linken Seite des Elements I existiert), wird ein Abstand
nach links von dem Element I zu dem linken Element II als eine Differenz zwischen
dem y-Koordinatenwert der linken Seite eines begrenzenden Rechtecks
des Elements I und des y-Koordinatenwerts
der rechten Seite eines begrenzenden Rechtecks des Elements II definiert
(wie es in 8C gezeigt
ist).
- (4) Nur in dem Fall, wenn zwei Zeichenelemente I und II eine Überlappung
ihrer y-Koordinatenbereiche, jedoch keine Überlappung ihrer x-Koordinatenbereiche
aufweisen, und der x-Koordinatenwert
jedes in dem Element II enthaltenen Punktes größer als der x-Koordinatenwert
jedes in dem Element I enthaltenen Punktes ist (d.h., dass das Element
II an der rechten Seite des Elements I existiert), wird ein Abstand nach
links von dem Element I zu dem linken Element II als eine Differenz
zwischen dem y-Koordinatenwert der rechten Seite eines begrenzenden
Rechtecks des Elements I und des y-Koordinatenwerts der linken Seite eines
begrenzenden Rechtecks des Elements II definiert (wie es in 8D gezeigt ist).
-
9 zeigt
einen beispielhaften Aufbau eines Zeichenelement-Abstandspuffers 11,
der angepasst ist, um die Abstandsdaten von 8A bis 8D zu
speichern. Auf ähnliche
Weise zu dem bei der ersten Ausführungsform
verwendeten Puffer speichert der Puffer 11 die Daten zweidimensional,
d.h., dass vertikal angeordnete Datensätze jeweiligen Zeichenelementen
und horizontal angeordnete Datensätze den kürzesten Abständen eines
Zeichenelements zu seinem nächsten
Nachbarn nach links, Nachbarn nach rechts, Nachbarn nach oben bzw.
Nachbarn nach unten entsprechen. Bei dem Zeichenelement-Abstandspuffer 11,
wie es in 9 gezeigt
ist, wird ein i-tes Zeichenelement (i = 0, 1, ..., N-1, wobei N die Anzahl
von Zeichenelementen ist) als ein Abstand D[i][0] zu dem nächsten Element
nach links, ein Abstand D[i][1] zu dem nächsten Element nach rechts,
ein Abstand D[i][2] zu dem nächsten
Element nach oben und ein Abstand D[i][3] zu dem nächsten Element
nach unten definiert. Bei der weiteren Beschreibung werden Abstände in den
obigen Begriffen ausgedrückt.
-
Ein Beispiel der Arbeitsprozedur
eines Zeichenelement-Abstandsberechnungsabschnitts 10 ist wie
folgt:
Diese Prozedur unterscheidet sich von derjenigen, die
bei der ersten Ausführungsform
beschrieben wurde, nur durch die Anzahl von Richtungen, d.h. vier Richtungen
bei dieser Ausführungsform,
jedoch zwei Richtungen bei der ersten Ausführungsform.
- (1)
Jedes Datenelement D[i][j] (i = 0, 1, .. N-1, J = 0) wird mit einem
Wert UD initialisiert, der gleich max(1x, 1y) ist, wobei 1x eine
horizontale Breite und 1y eine vertikale Höhe des verarbeitbaren Bereichs
ist.
- (2) J = 0
- (3) k = 0
- (4) Ein Abstand zwischen dem i-ten Zeichenelement und einem
j-ten Zeichenelement wird in der Richtung k (k = 0 ist eine Richtung
nach links, k = 1 ist eine Richtung nach rechts, k = 2 ist eine
Richtung nach oben und k = 3 ist eine Richtung nach unten) berechnet.
- (5) Wenn ein Wert D definiert wurde, wird D[i][k] = min (D[i][k],
d) bestimmt. D.h., dass D[i][k] um d aktualisiert wird, wenn d kleiner
als das aktuelle D[i][k] ist. Nichts wird getan, wenn d undefiniert
ist.
- (6) k = 1 + 1
- (7) Der Prozess kehrt zu Schritt (5) zurück, wenn k kleiner als 2 ist.
- (8) j = j + 1
- (9) j+ = 1, falls j = =1.
- (10) Der Prozess kehrt zu Schritt (4) zurück, wenn j kleiner als N ist.
- (11) i = i + 1
- (12) Der Prozess kehrt zu Schritt (3) zurück, wenn i kleiner als N ist.
-
Ein Linienrichtungsbestimmungsabschnitt 12 prüft die Häufigkeit
von kurzen Abständen
zwischen Zeichenelementen in horizontalen und vertikalen Richtungen
mit Bezug auf den Inhalt des Zeichenelement-Abstandspuffers 11 (Schritt 307)
wie folgt:
D.h., dass der Linienrichtungsabschnitt 12 zuerst
die Zahl M[0] und die Zahl M[1] für jedes i (i = 0, 1, ..., N-1,
wobei N die Zahl von Zeichenelementen ist) zählt, dessen Abstandswerte die
Bedingungen erfüllt:
max
(D[i][0], D[i][1]) < max(D[i][2],
D[i][3]) (für
M[0]) und
max (D[i][0], D[i][1]) > max(D[i][2], D[i][3]) (für M[1]).
-
Bei dieser Ausführungsform wird der Wert UD
an D[i][] gegeben, wenn D[i][] undefiniert ist. Dies beseitigt die
Notwendigkeit für
eine besondere Behandlung des Falls, der ein undefiniertes D[i][]
aufweist, jedoch nicht die notwendige Bedingung darstellt, wie es
für die
erste Ausführungsform
beschrieben ist. Der Wert UD ist nicht auf den gezeigten Wert begrenzt.
-
Als nächstes entscheidet der Abschnitt 12, dass
die Linie horizontal ist, wenn M[0] > = M[1], und die Linie vertikal ist, wenn
M[0] < M[1] ist
(Schritt 303). Die Werte von M[0] und M[1] können anders
definiert und die Korrelation zwischen den Werten und der Linienrichtung
kann ebenfalls modifiziert sein. Diese Ausführungsform kann ein anderes
Ausgangssignal aufweisen, das "die
Linienrichtung kann nicht bestimmt werden" angibt, wie es bei der ersten Ausführungsform
beschrieben ist.
-
Mit Bezug auf 10A bis 10C werden
Vorteile des Anwendens der oben beschriebenen Definitionen der Abstände nachstehend
beschrieben.
-
Mit Ketten von Zeichen, die in vertikalen
Zeilen geschrieben sind, wie es in 10A gezeigt
ist, kann sowohl die erste als auch die zweite Ausführungsform
die Zeichenelemente gemeinsam nutzen, da sie einen verbundenen (kontinuierlichen)
Teils jedes Zeichens als das Zeichenelement erkennen.
-
In 10B und 10C stellen Pfeile Zeichenelemente
dar, die zur Prüfung
der Abstände
in den entsprechenden Bereichen des Zeichenelement-Abstandspuffers 11 zu
speichern sind. 10B zeigt die
Zeichenelemente, die zum Definieren von Abständen zwischen ihnen von der
ersten Ausführungsform
zu verwenden sind, und 10C zeigt
die Zeichenelemente, die zum Definieren von Abständen zwischen ihnen von der
zweiten Ausführungsform
zu verwenden sind.
-
Wie es in 10B gezeigt ist, erkennt das Abstandsdefinitionsverfahren
der ersten Ausführungsform,
dass ein Zeichenelement 102 einen nächsten Nachbarn 103,
ein Zeichenelement 103 einen nächsten Nachbarn 102 und
ein Zeichenelement 104 einen nächsten Nachbarn 103 in
der horizontalen Richtung aufweist. In diesem Fall werden Abstandswerte,
die kleiner als eine gewöhnliche
Beabstandung zwischen Zeichen sind, in dem Zeichenelement-Abstandspuffer 11 gespeichert.
Ein Auftreten eines derartigen Falls kann reduziert werden, indem vorher
zu kleine Elemente von dem Umfang der Prüfung weggelassen werden, und
es kann kein Problem in der Praxis entstehen, da die Richtung der Zeichenlinien
auf der Grundlage der Daten aller Zeichenelemente in einem gesamten
Bereich definiert ist.
-
Um die Möglichkeit des Auftretens des
oben beschriebenen Falls zu minimieren, extrahiert die zweite Ausführungsform
die nächsten
linken und rechten Nachbarn jedes Zielzeichenelements in der horizontalen
Richtung und wählt
das entferntere als ein nächstes
Zeichenelement für
das Zielzeichenelement aus. Sie extrahiert ebenfalls die nächsten Nachbarn
nach oben und nach unten jedes Zielzeichenelements in der vertikalen
Richtung und wählt
das entferntere als ein nächstes
Zeichenelement für
das Zielzeichenelement aus. Wie es in 10C gezeigt ist,
weist ein Zeichen 102 einen nächsten Nachbarn 101 und
ein Zeichenelement 104 einen nächsten Nachbarn 105 in
der horizontalen Richtung auf, womit der Problemfall verglichen
mit der ersten Ausführungsform
reduziert ist. D.h., dass die zweite Ausführungsform bestimmt ist, die
Richtung von Zeichenlinien mit erhöhter Genauigkeit zu definieren.
-
<Dritte Betriebsart zum Ausführen der
Erfindung>
-
Bei einer weiteren (dritten) Ausführungsform der
Erfindung wird die Definition eines Abstands zwischen Zeichenelementen,
die bei der ersten Ausführungsform
verwendet werden, so modifiziert, um andere Richtungen zusätzlich zu
den horizontalen und vertikalen Richtungen zu berücksichtigen.
Mit gemeinsamen Bezug auf die 2 und 3 wird der Unterschied der
dritten Ausführungsform
zu der ersten Ausführungsform
nachstehend beschrieben. Weitere Abschnitte der Ausführungsform
sind in der Funktion denjenigen der ersten Ausführungsform ähnlich.
-
Ein Zeichenelement-Abstandsberechnungsabschnitt 10 berechnet
Abstände
jedes Zeichenelements von seinen Nachbarn in unterschiedlichen Richtungen,
wobei auf den Inhalt eines Zeichenelementspuffers 9 Bezug
genommen wird, und speichert den kleinsten der für jedes Zeichenelement berechneten
Abstandswerte in einem Zeichenelement-Abstandspuffer 11 (Schritt 306).
Bei diesem Schritt definiert die dritte Ausführungsform Abstände in jeweiligen
Richtungen wie folgt:
Zuerst bestimmt der Abschnitt 10 einen
repräsentativen
Punkt an jedem Zeichenelement, der beispielsweise ein Schwerpunkt
des Elements oder eine Mitte eines begrenzenden Rechtecks des Elements
sein kann. Die Mitte des begrenzenden Rechtecks weist einen Ausdruck
((sx + ex)/2, (sy + ey)/2) auf, wenn dem Rechteck Koordinaten (sx,
sy) seines obersten linken Punktes und Koordinaten (ex, ey) seines
untersten rechten Punkts gegeben wird. Der repräsentative Punkt jedes Zeichenelements
ist jedoch nicht auf die oben beschriebenen Punkte begrenzt.
-
Das folgende Beispiel wird mit Zeichenelementen
beschrieben, die jeweils durch eine Mitte eines begrenzenden Rechtecks
dargestellt werden.
-
Abstände von einem Zeichenelement
zu Nachbarn in jeweiligen unterschiedlichen Richtungen werden wie
folgt definiert: Ein Kreis (360°)
mit der Mitte an einer Rechteckmitte wird in einer Mehrzahl von
Unterteilungen unterteilt. 11A stellt
einen in 12 Unterteilungen mit 30° Intervallen
unterteilten Kreis dar, die über
15° Intervallen
sind. Dieser unterteilte Kreis wird bei der weiteren Beschreibung
verwendet. Ein Kreis kann jedoch in eine unterschiedliche Anzahl
von Winkeln unterteilt sein, die gleich oder nicht gleich sein können. Es
ist jedoch vorzuziehen, dass jede Trennlinie durch die Mitte des
Kreises läuft
und den Umfang bei zwei Punkten daran schneidet.
-
Dies ist so, da sich voneinander
um 180° unterscheidende
Winkel als die gleiche Richtung betrachtet werden. Eine Richtung
jeder Unterteilung wird durch einen Zentriwinkel jeder Unterteilung
definiert, wenn der Winkel kleiner als 180° ist. Wenn der Zentriwinkel
eine Unterteilung 180° überschreitet, wird
die Richtung der Unterteilung durch Subtrahieren von 180° von dem
Winkel definiert. Beispielsweise können die Zeichen von 11A bis 11D in Unterteilungen (Richtungen) mit
Trennwinkeln von 0, 30, ..., 150, 0, 30, ... 150 Grad unterteilt
sein, wie es in 11B gezeigt
ist.
-
Nun sei angenommen, dass die horizontale Richtung
0° und die
vertikale Richtung 90° ist.
Ein Abstand von einem repräsentativem
Punkt eines Zielzeichenelements I bis zu einem repräsentativen Punkt
jedes Zeichenelements II kann gemessen werden. Ein Abstand d zwischen
zwei Punkten wird als eine Länge
eines Segments definiert, das diese beiden Punkte verbindet. Ein
Quadrat der Segmente kann ebenfalls bei der gleichen Logik verwendet
werden. Weitere Abstandsmaße,
z.B. ein Stadtblockabstand (eine Summe einer Differenz zwischen
x-Koordinatenwerten
und einer Differenz zwischen zwei y-Koordinatenwerten) kann ebenfalls angewendet werden,
wie es der Anlass erfordert.
-
Das zwei Punkte verbindende Segment
wird in eine der Unterteilungen des Kreises mit der Mitte an dem
jeweiligen Punkt des Zeichenelements I aufgenommen, wie es in 11C gezeigt ist. In diesem Fall
sei angenommen, dass die Richtung der Zeichenelemente I und II eine
Richtung ist, die durch die Unterteilung angegeben wird, in der
das eingeschlossene Segment (d.h. ein Zentriwinkel der Unterteilung)
und der Abstand zwischen den Zeichenelementen I und II gleich "d" ist. In diesem Fall wird ein Abstand
zwischen den Elementen I und II in keiner anderen Richtung definiert.
-
Winkeln der Unterteilungen werden
Nummern gegeben, wie es in 11D gezeigt
ist. Diese Nummern werden für
entsprechende Winkel an jeweiligen Anordnungen verwendet. Dieses
Beispiel kann durch irgendein anderes Verfahren zum Korrelieren
der Winkel und Anordnungen geändert
werden. Ein Abstand zwischen einem i-ten Zeichenelement (i = 0,
1, ..., N-1, wobei N die Anzahl von Zeichenelementen ist) bis zu
einem j-ten Zeichenelement (j = 0, 1, ..., 5), das der nächste Nachbar
ist, wird als D[i][j] dargestellt.
-
12 zeigt
einen beispielhaften Aufbau des Zeichenelement-Abstandspuffers 11,
der angepasst ist, um die Abstandsdaten zu speichern. Der Puffer 11 speichert
die Daten zweidimensional, d.h., dass vertikal angeordnete Datensätze jeweiligen
Zeichenelementen und horizontal angeordnete Datensätze Abständen von
jedem Zeichenelement zu seinen Nachbarn in jeweiligen Richtungen
entsprechen. Da der gezeigte Fall sechs nummerierte Richtungen liefert,
weist der Puffer 11 sechs Bereiche in der horizontalen
Richtung auf.
-
Der Betrieb des Zeichenelement-Abstandsberechnungsabschnitts 10 ist
beispielsweise wie folgt:
Im Unterschied zu der ersten Ausführungsform
definiert die dritte Ausführungsform
Abstände
zwischen zwei Zeichenelementen in einer von verschiedenen Richtungen.
D.h., dass der Abstand zwischen zwei optionalen Zeichenelementen
I und II immer in einer Richtung definiert wird. Die Prozedur kann
somit vereinfacht werden.
- (1) Jedes Element
D[i][j] (i = 0, 1, ..., N-1, J = 0) wird mit einem Wert UD initialisiert,
der gleich dem max(1x, 1y) ist, wobei 1x eine horizontale Breite und
ein 1y eine vertikale Höhe
eines verarbeitbaren Bereichs ist.
- (2) i = 0
- (3) J = 0
- (4) Ein Abstand zwischen einem i-ten Zeichenelement und einem
j-ten Zeichenelement wird in einer Richtung k (k = 0, 1, ..., 11)
berechnet.
- (5) Wenn ein Wert d definiert wurde, wird D[i][k] = min (D[i][k],
d) bestimmt. D.h., dass D[i][k] um d aktualisiert wird, wenn d kleiner
als das aktuelle D[i][k] ist.
- (6) j = j + 1
- (7) j+ = 1, falls j= = 1.
- (8) Der Prozess kehrt zu Schritt (4) zurück, wenn j kleiner als N ist.
- (9) i = i + 1
- (10) Der Prozess kehrt zu Schritt (3) zurück, wenn i kleiner als N ist.
-
Bei dieser Ausführungsform wird D[i][] der Wert
UD gegeben, wenn D[i][] undefiniert ist. Dies beseitigt die Notwendigkeit
für eine
besondere Behandlung des Falls, der ein undefiniertes D[i][] aufweist, wobei
es jedoch nicht die notwendige Bedingung darstellt, wie es für die erste Ausführungsform
beschrieben ist. Der Wert UD ist nicht auf den gezeigten Wert begrenzt.
-
Ein Linienrichtungsbestimmungsabschnitt 12 prüft die Häufigkeit
von kurzen Abständen
zwischen Zeichenelementen in jeweiligen Richtungen mit Bezug auf
den Inhalt des Zeichenelement-Abstandspuffers 11 und entscheidet
die Richtung, in der die Zeichenelemente an den kürzesten
Abständen
angeordnet sind (Schritt 307).
-
D.h., dass der Linienrichtungsabschnitt 12 die
Anzahl von Zeichenelementen i für
jedes Zielzeichenelement i zählt.
Genauer gesagt, zählt
er: Die Anzahl M[0] von Zeichenelementen i (i = 0, 1, ..., N-1, wobei
N die Anzahl von Zeichenelementen ist), deren Abstandswerte von
dem Zielzeichenelement die Bedingung D[i][0] = min (D[i][0],
D[i][1],
..., D[i][5]) erfüllen;
M[1]
von i, dessen Abstandswerte die Bedingung D[i][1] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
M[2]
von i, dessen Abstandswerte die Bedingung D[i][2] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
M[3]
von i, dessen Abstandswerte die Bedingung D[i][3] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
M[4]
von i, dessen Abstandswerte die Bedingung D[i][4] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
und
M[5] von i, dessen Abstandswerte die Bedingung D[i][5]
= min
(D[i][0], D[i][1], ..., D[i][5]) erfüllen.
-
Als nächstes bestimmt der Abschnitt 12 einen
Wert j0, bei dem M[j0] = max(M[0], M[1]) erhalten wird, und definiert
den Wert j0 als einen Zahlencode der Richtung der Linien. Wenn es
mehrere j0 gibt, betrachtet der Abschnitt 12 eine Bestimmung als
unmöglich
und stellt j0 ein, um gleich der Anzahl von möglichen Richtungen (6 in diesem
Fall) zu sein.
-
Die Definition von M[] und die Korrelation zwischen
M[] und den Linienrichtungen sind nicht auf das obige begrenzt und
könnten
anders modifiziert, als es hier vorstehend für die erste Ausführungsform beschrieben
wurde.
-
Die Extraktion von Linienrichtungen
durch das oben beschriebene Verfahren basiert auf der experimentellen
Tatsache, dass jedes Dokument dichte Zeilen in der Richtung von
Zeichenlinien enthält.
Dieses Merkmal zum Erfassen von Linien in Richtungen verschieden
von den horizontalen und vertikalen Richtungen kann nicht nur für Seiten
verwendet werden, die darauf die original gedruckte Linien aufweisen,
sondern ebenfalls für
ein Bild mit geneigten Zeichenlinien, die durch eine Kamera oder
einen Handy-Scanner eingegeben wurden.
-
Schließlich wandelt ein Linienrichtungsbestimmungsabschnitt 12 den
Wert j0, der die Richtung der höchsten
Häufigkeit
angibt, oder eine andere Information (z.B. dass die Bestimmung unmöglich ist) in
einen Winkel der Linienrichtung oder anderen Informations-Code mit
Bezug auf eine Zahl-Richtungs-Tabelle 13 um
und gibt den umgewandelten Wert aus (Schritt 308). Die
Zahl-Richtungs-Tabelle 13 wird mittels Beispiel in 13 gezeigt. Die Ausgabe des
Linienrichtungsbestimmungsabschnitts 12 wird an eine Anzeigeeinheit 4 übertragen,
wie es in 2 gezeigt
ist. Natürlich
kann die Ausgabe der Linienrichtungsbestimmungsvorrichtung durch
eine geeignete getrennte Schnittstelle an jede andere Vorrichtung,
wie beispielsweise eine Zeichenerkennungsvorrichtung, die die Information
benötigt,
wie es für die
erste Ausführungsform
beschrieben wurde, übertragen
werden.
-
<Vierte Betriebsart zum Ausführen der
Erfindung>
-
Anstatt Abstände von jedem Zeichen zu seinen
Nachbarn zu berechnen, wie es in der dritten Ausführungsform
durchgeführt
wurde, berechnet eine weitere (vierte) Ausführungsform die Dichte von Zeichenelementen
in der Nachbarschaft jedes Zeichenelements in einem verarbeitbaren
Bereich, wählt Richtungen
der Häufigkeiten
der Peaks für
jeweiligen Zeichenelemente aus und definiert die Richtung, in der
die höchste
Häufigkeit,
die die höchste
Dichte von Zeichenelementen in dem Bereich angibt, als die Richtung
der Zeichenlinien in dem Bereich aus.
-
14 ist
ein Blockdiagramm der vierten Ausführungsform der vorliegenden
Erfindung. Die Ziffer 1410 kennzeichnet einen Zeichenelement-Dichte-Berechnungsabschnitt
und die Ziffer 1411 kennzeichnet einen Zeichenelement-Dichtepuffer.
Die anderen Abschnitte sind in der Funktion denjenigen ähnlich,
die in 2 gezeigt sind.
-
15 ist
ein Ablaufdiagramm, das die Verarbeitungsprozedur der vierten Ausführungsform
der vorliegenden Erfindung darstellt. Die Prozedur ist mit Ausnahme
der Schritte 1506 und 1507 die gleiche wie diejenige,
die in 2 gezeigt ist.
-
Der Unterschied der vierten Ausführungsform
zu der dritten Ausführungsform
ist wie folgt: Der Zeichenelement-Dichte-Berechnungsabschnitt 1410 berechnet
Dichten von Zeichenelementen in der Nachbarschaft jeder von jeweiligen
Elementen in jeder von jeweiligen Richtungen in einem verarbeitbaren
Bereich und speichert erhaltene Dichtewerte in dem Zeichenelement-Dichtepuffer 1411.
Die weitere Erläuterung
wird mit einem Beispiel von bei der dritten Ausführungsform verwendeten Zeichenelementen
durchgeführt.
Es ist natürlich
möglich,
andere Zeichen mit anders definierten repräsentativen Punkten zu verwenden.
-
Die Dichte von Zeichenelementen in
der Nachbarschaft eines Zeichenelements wird mittels Beispiel wie
folgt definiert: Wie es in den 16A und 16B gezeigt ist, wird ein
Kreis mit einem Radius R mit der Mitte an einem repräsentativen
Punkt des Zeichenelements gezeichnet und in Unterteilungen mit einem
Intervall eines spezifizierten Winkels (30°) unterteilt. Die Anzahl repräsentativer
Punkte von umgebenden Zeichenelementen in einer Unterteilung wird
als die Dichte der Zeichenelemente in der der Richtung der Unterteilung
entsprechenden Richtung bestimmt. In 16A und 16B wird eine Mehrzahl von
Zeichenelementen gezeigt, die in der Nachbarschaft des Zeichenelements
an der Mitte des Kreises verteilt sind.
-
Winkelunterteilungen des Kreises
werden durchgeführt,
wie es beispielsweise in 11A gezeigt
ist, und Richtungen der jeweiligen Unterteilungen werden nummeriert,
wie es beispielsweise in 11B gezeigt
ist. Es ist natürlich
möglich,
einen anders unterteilten Kreis und anders nummerierte Unterteilungen
zu verwenden, wie es bei der dritten Ausführungsform beschrieben ist.
-
16B zeigt
die Verteilung von repräsentativen
Punkten von umgebenden Zeichenelementen innerhalb des gleichen Kreises
von 16A. Die repräsentativen
Punkte der Zeichenelemente außerhalb
des Radius des Kreises werden weggelassen. Wie es in 16B gezeigt ist, ist die
größte Anzahl von
repräsentativen
Punkten in Unterteilungen aufgenommen, die einem Winkel von 30° an der Mitte des
Kreises entsprechen. D.h., dass, verglichen mit Zählwerten
in allen anderen gepaarten Unterteilungen, eine Summe von Punkten,
die in zwei Unterteilungen enthalten sind, die durch einen Winkel
von 30° in 16B dargestellt sind, am
größten ist.
Es ist offensichtlich, dass Zeichenelemente in dieser Winkelrichtung
am dichtesten verteilt sind.
-
Die Verarbeitungsprozedur bei Schritt 1506 wird
nachstehend mittels der numerischen Darstellung von Unterteilungsrichtungen
beschrieben, wie es in 11D gezeigt
ist. In diesem Fall wird die Dichte von Zeichenelementen, die ein
i-tes Zeichenelement (i = 0, 1, ..., N-1, wobei N die Zahl von Zeichenelementen
ist) in einer Richtung zu einem j-ten Zeichenelement hin umgeben,
als D[i][j] ausgedrückt.
- (1) Jedes Element D[i][j] (i = 0, 1, ..., N-1,
J = 0, 1, ..., 5) wird durch Null initialisiert.
- (2) i = 0
- (3) J = 0
- (4) Die Anzahl von in einer Winkelunterteilung in einer Richtung
von dem i-ten Zeichenelement zu dem j-ten Zeichenelement enthaltenen
repräsentativen
Punkten wird gezählt
und in D[i][j] gespeichert.
- (5) j = j + 1
- (6) Der Prozess kehrt zu Schritt 4 zurück, wenn j kleiner als 6 ist.
- (7) i = i + 1
- (8) Der Prozess kehrt zu Schritt 3 zurück, wenn i kleiner als N ist.
-
Mit Bezug auf den Inhalt des Zeichenelement-Dichtepuffers 1411 prüft der Linienrichtungsbestimmungsabschnitt 1412,
in welcher Richtung die umgebenden Zeichen für jedes Zeichenelement dichter
verteilt sind (Schritt 1507).
-
D.h., dass der Linienrichtungsabschnitt 1412 zählt: Die
Anzahl M[i] von Zeichenelementen i (i = 0, 1, .., N-1, wobei N die
Anzahl von Zeichenelementen ist), deren Abstände von jedem Zielzeichenelement
i die Bedingung D[i][0] = min
(D[i][0], D[i][1], ..., D[i][5])
erfüllen;
M[1]
von i, dessen Abstandswerte die Bedingung D[i][1] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
M[2]
von i, dessen Abstandswerte die Bedingung D[i][2] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
M[3]
von i, dessen Abstandswerte die Bedingung D[i][3] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
M[4]
von i, dessen Abstandswerte die Bedingung D[i][4] = min
(D[i][0],
D[i][1], ..., D[i][5]) erfüllen;
und
M[5] von i, dessen Abstandswerte die Bedingung D[i][5]
= min
(D[i][0], D[i][1], ..., D[i][5]) erfüllen.
-
Als nächstes bestimmt der Abschnitt 1412 einen
Wert j0, bei dem M[j0] = max(M[0], M[1]) erhalten wird, und definiert
den Wert j0 als die Zahl, die die Richtung von Linien angibt.
-
Wenn es mehrere j0 gibt, betrachtet
der Abschnitt 12 eine Bestimmung als unmöglich und
setzt j0 gleich der Anzahl von möglichen
Richtungen (6 in diesem Fall).
-
Die Definition von M[] und die Korrelation zwischen
M[] und der Linienrichtung sind nicht auf das obige begrenzt und
können
anders modifiziert werden, als es vorher für die dritte Ausführungsform beschrieben
ist.
-
<Fünfte
Betriebsart zum Ausführen
der Erfindung>
-
Eine weitere (fünfte) Ausführungsform der vorliegenden
Erfindung ist eine Bildschrägekorrekturvorrichtung,
die eine Richtung von Zeichenlinien verschieden von den horizontalen
und vertikalen Zeilen eines eingegebenen Textbildes durch Verwenden
der Funktionen der dritten Ausführungsform
extrahiert, die Schräge
des Bildes durch Vergleichen der Richtung der extrahierten Zeichenlinien
mit einer bekannten Richtung der Linien auf dem Original bestimmt und
das Bild gemäß der erfassten
Schräge
korrigiert.
-
18 ist
ein Blockdiagramm der Bildschrägekorrekturvorrichtung,
die die fünfte
Ausführungsform
der vorliegenden Erfindung ist. 19 ist
ein Ablaufdiagramm, das den Verarbeitungsvorgang der fünften Ausführungsform
der vorliegenden Erfindung darstellt. Der Betrieb der Ausführungsform
wird nachstehend mit Bezug die 18 und 19 beschrieben.
-
Bei der fünften Ausführungsform bestimmt ein Linienrichtungsbestimmungsabschnitt 1813 einen
Wert j0, der die Richtung der höchsten
Häufigkeit von
Zeichenelementen oder die Unmöglichkeit
der Beurteilung darstellt, und wandelt den Wert j0 in einen Winkel
der Linienrichtung oder ein anderes geeignetes Signal um, wobei
Bezug auf eine Zahl-Richtungs-Tabelle
genommen wird, und gibt das umgewandelte Signal aus (Schritt 1908).
Die Prozedur bei dem Schritt 1908 ist die gleiche wie diejenige
der dritten Ausführungsform
mit Ausnahme der folgenden Vorgänge:
Beim
Kennzeichnen eines zu verarbeitenden Bereichs an einem eingegebenen
Bild durch Verwenden einer Tastatur 1807 oder einer Maus 1808 (Schritt 1904),
gibt der Benutzer ebenfalls die korrekte Richtung der Linien innerhalb
des verarbeitbaren Bereichs ein, deren Daten in einem Bezugslinienrichtungsspeicher
unter der Steuerung einer CPU 1803 gespeichert werden.
Der Benutzer kann die Bezugsdaten auf verschiedene Arten eingeben.
In diesem Fall gibt der Benutzer Ziffern eines Winkels durch die Tastatur 1807 in
die CPU 1803 ein.
-
Der Linienrichtungsbestimmungsabschnitt 1812 kann
ebenfalls entweder eine vertikale (90°) oder horizontale (0°) Richtung
als eine korrekte Linienrichtung auswählen, die nahe an ihrem Ausgangswinkel
ist. Dieses Verfahren ist nützlich,
wenn die folgenden zwei Voraussetzungen erfüllt sind. In diesem Fall kann
der Bezugslinienrichtungseingabespeicher 1814 weggelassen
werden.
- (1) Die Richtung von Linien ist entweder
vertikal oder horizontal.
- (2) Die Schräge
eines Originals ist ausreichend kleiner als 90°.
-
In diesem Fall wird der Benutzer
nicht aufgefordert, einen Winkel der korrekten Linienrichtung einzugeben.
Dies kann dem Betrieb der Vorrichtung weiter vereinfachen.
-
Bei Schritt 1908 empfängt ein
Bildschrägeberechnungsabschnitt 1815 ein
von dem Linienrichtungsbestimmungsabschnitt 1812 ausgegebenes
Signal und berechnet einen Winkel der Schräge des Bildes durch Vergleichen
des empfangenen Ausgangssignals mit den in dem Bezugslinienrichtungsspeicher 1814 (bei
Schritt 1904) gespeicherten Bezugsdaten, mit Ausnahme des
Falls, wenn das empfangene Ausgangssignal keinen Winkel der Linienrichtung
sondern die Unmöglichkeit
der Beurteilung (Schritt 1909) angibt. Wenn die Linienrichtung
beispielsweise 30° an
dem Ausgang des Linienrichtungsbestimmungsabschnitts 1812 und
die Bezugslinienrichtung 30° ist,
wird die Schräge
des Bildes als 0° erfasst.
Wenn die Linienrichtung beispielsweise 0° an dem Ausgang des Linienrichtungsbestimmungsabschnitts 1812 und
die Bezugslinienrichtung 30° ist, wird
die Schräge
des Bildes als –30° erfasst.
Das Verarbeitungsergebnis wird an einen Bildschrägekorrekturabschnitt 1816 übertragen
(Schritt 1910).
-
Der Bildschrägekorrekturabschnitt 1816 addiert
einen umgekehrten Drehwinkel entsprechend dem berechneten Winkel
der Schräge
des Bildes zu den in dem Bildspeicher 1802 gespeicherten
Bilddaten, um die Wirkung der geschätzten Schräge des Bildes auszulöschen (Schritt 1911).
Der Bildschrägekorrekturabschnitt 1816 kann
das Bild unter Verwendung einer geeigneten bekannten Technik drehen, wie
beispielsweise in der offengelegten japanischen Patentveröffentlichung
Nr. 63-191192 offenbart ist.
-
Die Linienrichtungsbestimmungsvorrichtung gemäß der vorliegenden
Erfindung kann die Richtung von Linien von Zeichen durch Verwenden
der lokalen Dichte von Elementen bestimmen, die jeweilige Zeichen
aufbauen, ohne durch die Merkmale eines großen Bereichs eines Bildes mit
kompliziertem Layout beeinflusst zu werden.
-
Die Linienrichtungsbestimmungsvorrichtung gemäß der vorliegenden
Erfindung kann die Richtung von Linien von Zeichen durch Verarbeitung
von Zeichen-aufbauenden Elementen bestimmen und daher Zeichenelemente,
die bereits für
irgendeinen anderen Zweck extrahiert wurden, verwenden wie sie sind.
Die Vorrichtung kann ebenfalls Zeichenelemente durch sich selbst
extrahieren, die nicht nur zum Bestimmen der Linienrichtung sondern
ebenfalls zum weiteren Gebrauch bei der Zeichenerkennungsvorrichtung
verwendet werden.
-
Die Linienrichtungsbestimmungsvorrichtung gemäß der vorliegenden
Erfindung kann jede Richtung verschieden von den horizontalen und
vertikalen Linienrichtungen unterscheiden, wenn sich die Richtung
von den vertikalen und horizontalen Richtungen um einen spezifizierten
Winkel oder mehr unterscheidet. Daher kann die Vorrichtung mit Eingangssignalen
von weitverbreiteten Arten von Eingabevorrichtungen, z.B. einem
Handy-Scanner und einer Kamera, verwendet werden. Die Linienrichtungsbestimmungsvorrichtung
kann diagonale Linienrichtungen ohne häufiges Zugreifen auf den Bildspeicher bestimmen,
da der Linienrichtungsbestimmungsprozess nicht die Stufe des Extrahierens
von Zeichenelementen betrifft.
-
Die Bildschrägeerfassungsvorrichtung und die
Bildschrägekorrekturvorrichtung
gemäß der vorliegenden
Erfindung werden durch Verwenden der oben beschriebenen Merkmale
der Linienrichtungsbestimmungsvorrichtung gemäß der vorliegenden Erfindung
und durch Hinzufügen
einer kleinen Menge von Verarbeitung verwirklicht. Demgemäß können diese
Vorrichtungen einen sehr hohen Wirkungsgrad der Leistung aufweisen,
wenn sie in Kombination mit der Linienrichtungsbestimmungsvorrichtung
der vorliegenden Erfindung verwendet werden.
