DE19722439A1

DE19722439A1 - Verfahren und Vorrichtung zur Auffindung und Dekodierung maschinenlesbarer Symbole einschließlich Datenmatrixsymbolen

Info

Publication number: DE19722439A1
Application number: DE19722439A
Authority: DE
Inventors: Lingnan Liu
Original assignee: Intermec Corp
Current assignee: Intermec Technologies Corp
Priority date: 1996-05-29
Filing date: 1997-05-28
Publication date: 1997-12-04
Also published as: US5742041A; JPH1063772A

Description

Die vorliegende Erfindung betrifft Verfahren und Vorrichtungen zum Auffinden und Dekodieren maschinenlesbarer Symbole oder Bilder, einschließlich von Symbolen, die zumindest zwei feste Grenzen aufweisen.

Strichcodeleser (bar code-Leser) finden typische Strichcodes aus linearen Symboliken auf und dekodieren diese. "Lineare Symboliken" sind derartige Symboliken, bei welchen Daten als parallele Anordnung abwechselnder Streifen unterschiedlicher Breite und Leerräume kodiert sind (beispielsweise U.P.C., Code 39, Code 93, usw.). Lineare Symboliken kodieren, ebenso wie andere Symboliken, "Datenzeichen" (also von Menschen lesbare Zeichen) in Form von "Symbolzeichen", die typischerweise durch abwechselnde Streifen und Leerräume gebildet werden.

Strichcodeleser wandeln normalerweise Symbolzeichen in Daten zeichen dadurch um, daß ein Bereich abgetastet oder abgebildet wird, um ein Reflexionssignal zu erzeugen, welches üblicher weise ein Analogsignal ist, und das modulierte Licht wieder gibt, welches von Bereichen mit hohem Reflexionsvermögen oder "Leerräumen" reflektiert wird, und durch Bereiche mit niedri gem Reflexionsvermögen oder "Striche" absorbiert wird. Daher repräsentiert das Signal das Muster aus Strichen und Leerräu men in dem Symbol.

Strichcodeleser finden normalerweise Strichcodeinformation aus anderen visuellen Rauschen, welches in dem Signal enthal ten ist, dadurch auf, daß sie in dem Signal eine ungestörte Zone oder Ruhezone auffinden. Eine "Ruhezone" ist ein heller Zwischenraum, der keine dunklen Markierungen enthält, und der einem Symbol vorgeht oder nachfolgt, häufig in der Nähe eines Start- oder Stoppzeichens. Typischerweise weist eine Ruhezone Abmessungen auf, die etwa zehnmal so groß sind wie Striche, welche der Ruhezone vorausgehen oder nachfolgen.

Neuere Datensammelsymboliken haben sich von den typischen linearen Symboliken entfernt, um gestapelte Symboliken oder Bereichssymboliken zu erzeugen, um die "Informationsdichte" zu erhöhen, also die Menge an Information, die in einem vor gegebenen Bereich kodiert ist. "Gestapelte Symboliken" oder Mehrfachzeilensymboliken verwenden benachbarte Zeilen aus Strichen mit verschiedenen Breiten und Leerräumen (beispiels weise Code 49, PDF417, usw.). "Bereichssymboliken" oder zwei dimensionale Matrix-Symboliken verwenden Anordnungen von Datenzellen in Form regelmäßiger Vielecke, bei welchen die Entfernung von einem Zentrum zum Zentrum der benachbarten Datenzelle gleich ist (beispielsweise Datenmatrix, Maxi Code, Code One, Aztec Code, usw.).

Während Standardalgorithmen für das Auffinden und Dekodie ren für lineare Symboliken verwendet werden können, und für einige gestapelte Symboliken, sind derartige Algorithmen für Bereichssymboliken ungeeignet. Bereichssymboliken verwenden typischerweise "Findermuster", welche eindeutige Muster dar stellen, die von Geräten und Algorithmen für die automatisier te Bilderkennung erkannt werden können. Beispielsweise verwen det die Datenmatrix-Symbolik eine zweidimensionale Matrix be nachbarter quadratischer Module mit einem Findermuster, wel ches feste Kanten oder Ränder entlang der Unterseite und der linken Seite enthält, sowie zwei gestrichelte oder unterbro chene Ränder entlang der Oberseite und der rechten Seite, die aus abwechselnden schwarzen und weißen Quadraten bestehen.

Die Datenmatrix-Symbolik verwendet ein Verfahren zum Auffin den und Dekodieren eines Symbols innerhalb eines gespeicher ten Bildes. Das Standardverfahren umfaßt folgende Schritte: (1) Suchen nach einem Ort des Symbols innerhalb des gespei cherten Bildes; (2) Auffinden der beiden festen oder durchge zogenen Ränder des Findermusters; (3) Auffinden des Außenran des der gestrichelten Ränder; (4) Abschneiden irgendwelcher weißer "Halbinseln" an dem Außenrand der beiden festen Rän der; (5) Auffinden der beiden gestrichelten Ränder; (6) Be rechnung der lokalen mittleren Modulbreite C unter Verwendung der beiden gestrichelten Ränder; (7) Bestimmung der Zentren der schwarzen und weißen quadratischen Module auf den gestri chelten Rändern; und (8) Bestimmung der Zentren der Daten module für kleine Symbole (also ohne interne Findermuster), und Dekodieren des Symbols. Die Schritte werden hintereinander durchgeführt, wobei die gesamten durchgezogenen und gestri chelten Ränder zuerst aufgefunden werden, und dann zusätzli che Suchschritte durchgeführt werden. Für größere Symbole, die interne Findermuster aufweisen, umfaßt das Verfahren wei terhin folgende Schritte: (1) Auffinden der Zentrumspunkte der gestrichelten Ränder für die internen Findermuster; (2) Bestimmung der Zentren der Datenmodule; (3) Feststellung, ob die Anzahl an Datenmodulen gerade ist, und falls ja, Dekodie ren des Symbols unter Verwendung eines ECC 200-Dekodierver fahrens; und (4) Feststellung, ob die Anzahl an Datenmodulen ungerade ist, und falls ja, Dekodieren des Symbols unter Ver wendung eines ECC 000-140-Dekodierverfahrens. Weitere Einzel heiten in bezug auf dieses Verfahren finden sich in der "Data Matrix AIM Uniform Symbology Specification".

Das voranstehend geschilderte Verfahren erfordert ein be trächtliches Ausmaß an Speicherkapazität während des Auffin dungsvorgangs für ein bestimmtes Symbol, und erfordert ein beträchtliches Ausmaß an Verarbeitungs-Overhead, wobei häufig ein schneller Mikroprozessor erforderlich ist. Schnelle Mikro prozessoren sind normalerweise teuerer als ihre langsameren Gegenstücke, und daher sind Lesegeräte teuer, die zum Auffin den und Dekodieren von Datenmatrixsymbolen ausgelegt sind. Es ist möglicherweise noch wesentlicher, daß der Standard-Auffindungsalgorithmus nicht immer das Findermuster auffinden kann, da das Findermuster nur auf zwei Seiten der Matrix aus Datenzellen angeordnet ist, neben der Ruhezone, und relativ eng ist. Datenmatrixsymbole lassen sich noch schwieriger auf finden, wenn das Symbol verzerrt oder beschädigt ist. Wenn bei dem gespeicherten Bild eine Perspektivwinkelverzerrung vorhanden ist (beispielsweise wenn das Bild so erzeugt wird, daß das Lesegerät nicht senkrecht zum Symbol ausgerichtet ist), oder das Etikett entlang seiner Findermusterränder be schädigt ist, ist das Standardverfahren zum Dekodieren von Datenmatrixsymbolen unzureichend.

Die vorliegende Erfindung besteht in einem Verfahren und einer Vorrichtung zum Auffinden und Dekodieren maschinenles barer Symbole, einschließlich Datenmatrixsymbole, durch Iden tifizieren von Abschnitten des Findermusters und nachfolgen de Konstruktion eines Randes für das gespeicherte Bild des Symbols. Die vorliegende Erfindung stellt ein robustes Verfah ren zum Auffinden von Bildern von Symbolen unter Verwendung redundanter Information in dem Findermuster zur Verfügung, beispielsweise das relativ große Findermuster in bezug auf die Abmessungen des Symbols in der Datenmatrix-Symbolik. Die vorliegende Erfindung kann den Ort eines Datenmatrixsymbols nur mit der folgenden Information auffinden und festlegen: (1) zwei gegenüberliegende Ecken; (2) drei komplette Ränder oder Seiten des Findermusters; (3) vier Teilränder; (4) drei Teilränder und eine Ecke des fehlenden Randes; oder (5) eine Ecke und zwei Teilränder, welche der einen Ecke gegenüberlie gen. Auf der Grundlage nur eines dieser fünf Fälle identifi zierter Information kann die vorliegende Erfindung exakt den Rand des Symbols bestimmen, und daher das Symbol schnell de kodieren.

Zusätzlich kann die vorliegende Erfindung die Version des Symbols bestimmen. Die erforderliche Information zum Auffin den der Version des Datenmatrixsymbols ist entweder eine voll ständige Zeitspur oder eine vollständige Ecke, an welcher sich die gestrichelten Ränder treffen. Zwei teilweise ge strichelte Ränder können dazu hilfreich sein, die Version zu bestimmen, wobei die Genauigkeit dieser Bestimmung davon ab hängt, inwieweit sämtliche Findermuster des Symbols bekannt sind.

Die vorliegende Erfindung stellt einen wirksamen Ausgleich zwischen der Geschwindigkeit des Auffindens und der Dekodie rung eines Symbols gegenüber der Komplexizität zur Verfügung. Während ein kompliziertes Programm dazu geschaffen werden kann, sehr stark verzerrte oder beschädigte Symbole aufzufin den, und zu dekodieren zu versuchen, wäre eine derartiges Ver fahren sehr zeitaufwendig. Kunden wünschen Hochgeschwindig keitssymbolleser, so daß eine große Menge an Symbolen schnell abgebildet und dekodiert werden kann. Daher sind zeitaufwen dige Dekodierverfahren unerwünscht.

Wie auch in den nachstehenden Patentansprüchen angegeben ist, stellt die vorliegende Erfindung im weiteren Sinne ein Ver fahren zum Auffinden eines vorbestimmten Bildes innerhalb eines gespeicherten Bildes zur Verfügung, wobei das vorbe stimmte Bild erste und zweite lineare Merkmale und erste und zweite gestrichelte lineare Merkmale neben den ersten und zweiten linearen Merkmalen aufweist. Das Verfahren umfaßt folgende Schritte: (a) Auffinden eines Randpunktes eines der ersten und zweiten linearen Merkmale, (b) Auffinden zumindest eines Abschnitts eines der ersten und zweiten linearen Merk male auf der Grundlage des aufgefundenen Randpunktes, (c) Auffinden zumindest eines Abschnitts eines anderes der ersten und zweiten linearen Merkmale, (d) Auffinden zumindest eines Abschnitts des ersten gestrichelten Merkmals auf der Grund lage des aufgefundenen Abschnitts des ersten oder zweiten linearen Merkmals; (e) Auffinden des zweiten gestrichelten Merkmals auf der Grundlage des aufgefundenen Abschnitts des ersten gestrichelten Merkmals oder der ersten linearen Merk mals; und (f) Auffinden einer Position des vorbestimmten Bil des in dem gespeicherten Bild auf der Grundlage der aufge fundenen Abschnitte der ersten und zweiten linearen und ge strichelten Merkmale.

Die vorliegende Erfindung stellt weiterhin ein Verfahren zum Auffinden eines Bildes eines maschinenlesbaren Symbols inner halb eines gespeicherten Bildes zur Verfügung, wobei das Sym bol ein vorbestimmtes Muster am Umfang des Symbols aufweist. Das vorbestimmte Muster weist erste und zweite durchgezogene lineare Merkmale auf, die sich an einer gemeinsamen durchge zogenen Ecke treffen, sowie erste und zweite gestrichelte linieare Merkmale, die von den freien Enden der ersten und zweiten durchgezogenen Merkmale ausgehen, und sich in einer gemeinsamen gestrichelten Ecke treffen. Das Verfahren umfaßt folgende Schritte: (a) Auffinden eines Randpunktes des vorbe stimmten Musters, (b) Untersuchung zumindest eines Abschnitts des Umfangs des Symbols, (c) Auffinden, auf der Grundlage des Untersuchungsschrittes, von zumindest Abschnitten des vorbe stimmten Musters, wobei die vorbestimmten Abschnitte entweder sind: (i) durchgezogene und gestrichelte Ecken, (ii) zumin dest ein Abschnitt der ersten und zweiten durchgezogenen und gestrichelten Merkmale, (iii) zumindest ein Abschnitt der er sten und zweiten gestrichelten Merkmale und der durchgezoge nen Ecke, (iv) zumindest ein Abschnitt der ersten und zweiten durchgezogenen Merkmale und der gestrichelten Ecke, und (v) zumindest vollständige Orte von dreien der vier Merkmale, und (d) Bestimmung einer Position des Symbols in dem gespeicher ten Bild auf der Grundlage der aufgefundenen Abschnitte des vorbestimmten Musters.

Die Erfindung wird nachstehend anhand zeichnerisch dargestell ter Ausführungsbeispiele näher erläutert, aus welchen weitere Vorteile und Merkmale hervorgehen. Es zeigt:

Fig. 1 ein Blockschaltbild eines beispielhaften Datensammel symboliklesegeräts gemäß der vorliegenden Erfindung mit einer Aufsicht auf ein Datenmatrixsymbol;

Fig. 2A und 2B zusammen ein Flußdiagramm eines beispielhaften Verfahrens zum Auffinden und Dekodieren von Daten sammelsymbolen, insbesondere des Datenmatrixsymbols von Fig. 1;

Fig. 3 eine vergrößerte Ansicht des Datenmatrixsymbols von Fig. 1;

Fig. 4 eine schematische Ansicht eines optisch verzerrten Datenmatrixsymbols;

Fig. 5 ein Flußdiagramm eines Unterprogramms zum Auffinden einer Linie an gegenüberliegenden Seiten eines Start punkts;

Fig. 6 ein Flußdiagramm eines Unterprogramms zum Auffinden eines Liniensegments von einer Seite eines Start punkts aus;

Fig. 7 eine vergrößerte Ansicht verzerrter und/oder beschä digter durchgezogener Ränder für das Findermuster eines Datenmatrixsymbols;

Fig. 8 ein Flußdiagramm eines Unterprogramms zum Überqueren eines Elements;

Fig. 9 ein Flußdiagramm eines Unterprogramms zum Auffinden einer durchgezogenen Ecke für ein Findermuster eines Datenmatrixsymbols;

Fig. 10 eine schematische Darstellung eines Datenmatrixsym bols, welches eine falsche durchgezogene Ecke auf weist;

Fig. 11 ein Flußdiagramm eines Unterprogramms zum Auffinden gestrichelter Ränder für ein Findermuster eines Datenmatrixsymbols; und

Fig. 12 eine schematische Darstellung eines großen Daten matrixsymbols, welches mehrere, benachbarte Finder muster aufweist.

Wie in Fig. 1 gezeigt ist, weist ein Datensammelsymboliklese gerät 50 gemäß der vorliegenden Erfindung eine Lichtquelle 52 auf, welches eine Ansammlung von Daten oder ein anderes Symbol beleuchtet, beispielsweise ein Datenmatrixsymbol 53. Der hier verwendete Begriff "Datensammelsymbol" bezeichnet ein Symbol aus irgendeiner linearen, gestapelten Bereichs symbolik oder einer anderen maschinenlesbaren Symbolik. Ein mit einer Lichtöffnung 61 versehener Sensor 54 empfängt von dem Symbol 53 reflektiertes Licht und wandelt das empfangene Licht in ein elektrisches Signal oder Profil um. Die Licht quelle 52 kann beispielsweise eine LED sein, eine Blitzlampe, eine Infrarotlichtquelle, ein Rasterabtastlaser, oder ein anderes, lichtaussendendes Element, während der Sensor 54 eine ein- oder zweidimensionale CCD sein kann, ein Halblei terarray, ein Photodetektor, ein Vidicon, oder eine andere Flächenabbildungsvorrichtung, welche empfangenes Licht in elektrische Signale umwandeln kann.

Ein Empfänger oder Wandler 56 empfängt das elektrische Sig nal von dem Sensor 54 und wandelt es in ein Signal um, wel ches von einem programmierten Computer oder Prozessor 60 ver arbeitet werden soll. Typischerweise erzeugt der Sensor 54 dein analoges Profilsignal, welches das modulierte Licht wie dergibt, welches von den Elementen in dem Symbol 53 reflek tiert wird. Wenn der Prozessor 60 ein digitaler Computer ist, dann wandelt der Wandler 56 jeden Pixel (Bildpunkt) in dem Bild des Symbols 53 aus dem von dem Sensor 54 erzeugten Ana logsignal in ein Digitalsignal mit mehreren Pegeln um, wel ches numerisch die verschiedenen Amplituden des Analogsignals wiedergibt. Der Wandler 56 und/oder Prozessor 60 ist bzw. sind mit einem Speicher 57 gekoppelt, um die Profile in digi taler Form zu speichern. Der Wandler 56, der Speicher 57 und der Prozessor 60 können eine monolithisch integrierte Schal tung sein.

Der Sensor 54 kann eine ladungsgekoppelte Vorrichtung ("CCD") oder eine entsprechende Flächenabbildungsvorrichtung sein, die eine aktive Oberfläche aufweist, beispielsweise eine recht eckige Oberfläche aus M mal N Pixelelementen, beispielsweise 582 mal 752 Pixelelemente. Bekanntlich gibt jedes Pixelelement in dem CCD-Array des Sensors typischerweise ein Graupegel signal aus, also ein Analogsignal, welches die Menge oder In tensität des Lichts bestimmt, welches auf das entsprechende Pixelelement einfällt, ähnlich wie bei einem Videodatensignal. Der Wandler 56 wandelt vorzugsweise die Graupegelsignale in ein Digitalsignal um, welches beispielsweise 16 Graupegel zur Verwendung bei dem Prozessor 60 aufweist. Der Speicher 57 speichert die Digitalsignale, und umfaßt vorzugsweise sowohl flüchtigen als auch nicht-flüchtigen Speicher (beispielsweise einen Speicher mit wahlfreiem Zugriff und einen elektrisch löschbaren Nur-Lese-Speicher). Daher kann durch den Leser 50 ein Objekt oder Bild innerhalb des Gesichtsfeldes des Sensors 54 in elektrische Signale umgewandelt werden, die digitali siert werden, und als gespeichertes Bild in dem Speicherab schnitt 57 mit wahlfreiem Zugriff gespeichert werden, um von dem Prozessor 60 zurückgeholt und verarbeitet zu werden, un ter Steuerung durch ein Programm 100, welches in dem Speicher gespeichert ist (wie voranstehend erwähnt). Nach der Verarbei tung des gespeicherten Bildes kann der Prozessor 60 die Er gebnisse einer derartigen Verarbeitung an ein Peripherigerät oder einen Computer (nicht gezeigt) ausgeben.

In den Fig. 2A und 2B (zusammen Fig. 2) führt ein beispiel haftes Programm 100, welches von der Lesevorrichtung 50 ge mäß der vorliegenden Erfindung durchgeführt wird, zuerst ein Auffinden des Bildes des Symbols 53 innerhalb eines gespei cherten Bildes durch, und dekodiert dann das Symbol. Der hier verwendete Begriff "gespeichertes Bild" betrifft allgemein das Gesamtbild im Gesichtsfeld, welches in dem Speicher 57 gespeichert ist, welches von dem Sensor 54 und dem Prozessor 60 erzeugt wurde, und welches das Symbol 53 oder andere Sym bole enthält, die dekodiert werden sollen. Für einen entspre chenden Verarbeitungswirkungsgrad enthält, wenn die CCD in dem Sensor 54 ein Feld oder Array von 582 mal 752 Pixeln auf weist, der Speicher 57 einen Array von 582 mal 752 Speicher orten, die von dem Prozessor 60 adressiert werden, und dem Array der Pixel entsprechen. Das gespeicherte Bild in dem Speicher 57 wird vorzugsweise in bezug auf ein kartesisches Koordinatensystem dargestellt, so daß der Ort jedes Pixels durch ein Zahlenpaar dargestellt wird, welches die horizon tale bzw. vertikale Position des Pixels in dem gespeicherten Bild angibt. Beispielsweise werden dem ersten Pixel in der oberen linken Ecke des gespeicherten Bildes die kartesischen Koordinaten (0, 0) zugeordnet, während dem untersten, ganz rechts gelegenen Pixel die Koordinaten (752, 582) zugeordnet sind. Objekte innerhalb des gespeicherten Bildes, also Grup pen von Pixeln, können daher arithmetisch aufgesucht werden, unter Verwendung geometrischer und trigonometrischer Eigen schaften auf der Grundlage des Koordinatensystems (beispiels weise Gleichungen für Linien, Kreise oder andere geometrische oder trigonometrische Gleichungen, die zur Darstellung ebener Objekte verwendet werden, wie nachstehend noch genauer erläu tert wird). Der hier verwendete Begriff "Auffinden" betrifft allgemein die Bestimmung sowohl der Position als auch der Orientierung des Bildes eines Gegenstands oder Objekts inner halb des gespeicherten Bildes.

Das Programm 100 beginnt im Schritt 102, in welchem die Lese vorrichtung ein Bild des Symbols 53 abtastet oder speichert. Die Lesevorrichtung 50 kann beispielsweise ein von Hand gehal tener Gegenstand sein, und einen Triggerschalter (nicht ge zeigt) aufweisen, der mit dem Prozessor 60 gekoppelt ist, und die Lichtquelle 52 zur Beleuchtung des Symbols 53 veranlaßt, und den Sensor 54, den Wandler 56 und den Prozessor 60 ein Bild des Symbols in dem Speicher 57 nach Betätigung des Schal ters speichern läßt. Die spezifische Vorrichtung und das spe zifische Verfahren zum Speichern eines Bildes eines Symbols durch die Lesevorrichtung 50 sind konventionell, und werden von Fachleuten auf diesem Gebiet verstanden, ohne daß hier eine nähere Beschreibung erforderlich ist.

Im Schritt 102 beginnt der Prozessor 60 auch damit, das Sym bol 53 innerhalb des gespeicherten Bildes aufzufinden. Wie in Fig. 1 und deutlicher in Fig. 3 gezeigt ist, weist das Datenmatrixsymbol 53 ein Findermuster auf, welches aus zwei durchgezogenen Rändern 70 und 72 und zwei gestrichelten oder unterbrochenen Rändern 74 und 76 besteht, also einen zentra len Datenbereich. Die beiden durchgezogenen Ränder 70 und 72 sind idealerweise im Winkel von 90° zueinander angeordnet, und treffen sich in einer Schnittecke 80. Wie nachstehend noch genauer erläutert wird, rufen jedoch optische Verzerrun gen oder Fehler unterschiedliche Winkel für die durchgezogene Ecke 80 hervor, wie durch ein Symbol 90 in Fig. 4 angedeutet ist. Der erste Rand 70 hat ein freies Ende oder eine freie Ecke 82, während der zweite Rand 72 eine freie Ecke 84 auf weist.

Die beiden gestrichelten Ränder 74 und 76 treffen sich in ei ner Ecke 86. Wenn in der Ecke 86 kein schwarzes Quadrat vor handen ist, dann ist das Datenmatrixsymbol 53 ein Symbol der Version ECC 200; andernfalls ist das Symbol ein Datenmatrix symbol der Version ECC 140. Der erste gestrichelte Rand 74 trifft das freie Ende des zweiten Randes 72 in der Ecke 84, wogegen der zweite gestrichelte Rand 76 den ersten Rand 70 in der Ecke 82 trifft.

Das endgültige Ziel der vorliegenden Erfindung besteht in der Bestimmung der Orte der beiden durchgezogenen Ränder 70 und 72 und der beiden gestrichelten Ränder 74 und 76, um hierdurch einen Begrenzungskasten oder eine Außenkontur für das Symbol 53 zu bestimmen. Durch Bestimmung der Außenkontur für das Symbol 53 kann die Lesevorrichtung 50 leichter jede der Datenzellen innerhalb des Symbols auffinden, und hier durch das Symbol schnell dekodieren. Die Begriffe "Punkt" und "Pixel" werden hier austauschbar verwendet.

Im Schritt 102 beginnt der Prozessor 60 mit dem Auffinden des Symbols 53 innerhalb des gespeicherten Bildes, beispielswei se durch Untersuchung eines oder mehrerer virtueller Abtast- oder Scan-Pfade, die durch das gespeicherte Bild verlaufen, um einen Randpunkt zwischen der Ruhezone und einer der durch gezogenen Ränder 70 und 72 aufzufinden. Der Prozessor 60 fin det einen Randpunkt (X, Y) in dem kartesischen Koordinaten system auf, wie auf diesem Gebiet wohlbekannt ist, und bei spielsweise beschrieben ist in A. Rosenfeld, Digital Picture Processing, Academic Press, Bd. 1 und 2, 1982. Der Prozessor 60 kann beispielsweise mehrere Abtastpfade durch das gespei cherte Bild untersuchen, beispielsweise einen horizontalen Pfad durch das Bild, einen vertikalen Pfad in einer Orientie rung von 90° zum horizontalen Pfad, sowie Pfade in einem Win kel von 26°, 45° bzw. 71° gegenüber dem horizontalen Pfad.

Es können auch andere bekannte Abtaststrategien für ein ge speichertes Bild eingesetzt werden.

Die ursprünglichen Abtastpfade oder Pixellinien, die von dem Prozessor 60 im Schritt 102 untersucht werden, verlaufen vor zugsweise vertikal, um so einen Randpunkt für einen Rand auf zufinden, der von links nach rechts in bezug auf das kartesi sche Koordinatensystem verläuft. Der Prozessor 60 nimmt am Anfang an, daß ein Benutzer, welcher die Lesevorrichtung 50 verwendet, den Sensor 50 aufrecht in bezug auf das Symbol 53 ausgerichtet hat, so daß das Bild des Symbols 53, wie in Fig. 3 gezeigt, korrekt orientiert ist. Allerdings kann das Bild des Symbols auch in verschiedenen anderen Orientierungen inner halb des gespeicherten Bildes orientiert sein, beispielsweise wie das invertierte Symbol 90, das in Fig. 4 gezeigt ist. Der Randpunkt (X, Y), der von dem Prozessor 60 im Schritt 102 auf gefunden wird, liegt daher wahrscheinlich entlang dem zweiten durchgezogenen Rand 72 für das Symbol 90, statt entlang dem ersten durchgezogenen Rand 70 für das Symbol 53 (Fig. 3).

Im Schritt 104 ruft der Prozessor ein Unterprogramm 200 auf, welches ein Liniensegment definiert oder auffindet, welches entlang dem aufgefundenen Rand verläuft, und welches den Rand punkt (X, Y) enthält. In Fig. 5 beginnt ein beispielhaftes Liniensegment-Auffindungsverfahren 200 im Schritt 202 mit der Eingabe des Randpunktes (X, Y) und eines Gradienten oder einer Randrichtung θ. Der Gradient oder die Randrichtung betrifft die Entfernung der größten Änderung der Pixelintensität von einem vorgegebenen Pixel in bezug auf die Randrichtung an die sem Pixel oder Punkt. Bei der vorliegenden Erfindung ist der Randrichtungswinkel θ an einem vorgegebenen Punkt im all gemeinen senkrecht zum Rand einer Grenze oder eines anderen Merkmals in dem Symbol 53 an diesem Punkt angeordnet. Im Schritt 204 setzt der Prozessor 60 eine Richtungsmarke auf einen Wert "links" in bezug auf das kartesische Koordinaten system.

Im Schritt 206 ruft der Prozessor 60 ein Unterprogramm 250 auf, welches ein Liniensegment auffindet, welches an dem Randpunkt (X, Y) beginnt, und entlang dem Rand nach links verläuft. In Fig. 6 beginnt das Randauffindungsprogramm 250 im Schritt 252 damit, daß ein Startpunkt (der Randpunkt (X, Y)) eingegeben wird, die Randrichtung θ, und der Wert der Richtungsmarke. Im Schritt 254 stellt der Prozessor eine Anfangspunktvariable (X′, Y′) zu dem Randpunkt (X, Y) ein, sowie eine Anfangsrichtungsvariable θ′ zur Randrichtung θ. Im Schritt 254 stellt der Prozessor 60 darüber hinaus eine Variable N auf 0 ein, und eine mittlere Randrichtung θ_AVE auf den Wert von θ. Schließlich stellt im Schritt 254 der Prozessor 60 eine Rückkehrmarke auf einen Fehlerwert ein.

Im Schritt 256 stellt der Prozessor 60 fest, ob die Richtungs marke einen Wert "links" aufweist. Ist dies der Fall, dann findet im Schritt 258 der Prozessor 60 einen Randpunkt in der Nähe links von dem Punkt (X′, Y′), um einen neuen Randpunkt (X′′, Y′′) aufzusuchen, und eine neue Randrichtung θ′′ für den neuen Randpunkt. Der Begriff "in der Nähe" bedeutet einen Klaster oder eine Gruppe von Pixeln, beispielsweise eine qua dratische Gruppe von 3 × 3 Pixeln.

Wenn im Schritt 256 der Prozessor 60 feststellt, daß die Rich tungsmarke nicht auf den Wert "links" eingestellt ist, dann findet alternativ im Schritt 260 der Prozessor 60 einen Punkt in der Nähe rechts von dem Punkt (X′, Y′) als neuen Randpunkt (X′′, Y′′), und eine neue Richtungsorientierung θ′′. Nach dem Schritt 258 oder 260 bestimmt der Prozessor 60 im Schritt 262, ob ein Randpunkt aufgefunden wurde. Ist dies der Fall, dann stellt im Schritt 264 der Prozessor 60 den Anfangspunkt (X′ Y′) auf den neu aufgefundenen Randpunkt (X′′, Y′′) ein. Zusätz lich stellt der Prozessor 60 im Schritt 264 die Anfangsrich tungsvariable θ′ auf die neue Randrichtung θ′′ an dem neuen Randpunkt ein, und inkrementiert den Wert N um 1.

Im Schritt 266 stellt der Prozessor 60 fest, ob der Absolut wert der Differenz zwischen der Richtungsvariable θ′ und dem mittleren Richtungswert θ_AVE größer als ein Schwellen richtungswert θ_THRESHOLD ist. Ist dies nicht der Fall, so aktualisiert im Schritt 268 der Prozessor 60 den mittleren Richtungswert θ_AVE dadurch, daß er sämtliche vorherigen Richtungswerte θ′ addiert, und die Summe durch den Momentan wert für die Variable N dividiert. Dann verzweigt das Programm 250 zurück zum Schritt 256. In den Schritten 258 (oder 260), 262, 264, 266 und 268 untersucht der Prozessor 60 das gespei cherte Bild und bewegt sich entlang einer der durchgezogenen Grenzen 70 oder 72, oder entlang eines Abschnitts der Grenze, indem im wesentlichen Pixel nach Pixel des gespeicherten Bilds in der Richtung θ′ für einen Randpunkt der Grenze abgetastet wird, die neben der Ruhezone liegt.

Das Symbol 53 kann beschädigte Grenzen aufweisen, beispiels weise die in Fig. 7 gezeigten, beschädigten durchgezogenen Grenzen 70′ und 72′ Wie in Fig. 7 gezeigt, kann das Finder muster Druck- oder Abbildungsfehler enthalten, welche dazu führen, daß eine oder mehrere Grenzen einen Abschnitt 91 mit einer größeren Breite als der mittleren Breite aufweisen. Be kanntlich weisen die durchgezogenen Grenzen, ebenso wie ein zelne Datenzellen, eine Breite gleich der X-Ausdehnung auf. Die X-Ausdehnung stellt typischerweise die kleinste Breite (oder Höhe) der Striche, Zwischenräume, Datenzellen oder an derer Merkmale in einer vorbestimmten Symbolik dar. Das Sym bol 53 kann auch andere Beschädigungen oder Fehler enthalten, beispielsweise Leerstellen 92, welche dazu führen, daß die durchgezogenen Grenzen 70′ oder 72′ eine Breite aufweisen, die geringer ist als die X-Ausdehnung. Darüber hinaus können die Grenzen auch Spalte 93 enthalten, so daß die Grenzen nicht durchgehend sind, und fragmentarisch vorhanden sind. Schließ lich kann das Symbol 53 fehlende Ecken enthalten, beispiels weise eine Leerstelle 92′. Die Programme gemäß der vorlie genden Erfindung suchen vorzugsweise die durchgezogenen und gestrichelten Grenzen des Findermusters für das Symbol 53 auf, trotz derartiger Fehler, Leerstellen und Spalte in den Gren zen. Im Schritt 266 stellt daher der Prozessor 60 fest, ob die Differenz zwischen der neuen Richtungsvariablen θ′ und dem mittleren Richtungswert θ_AVE so groß ist, daß die Schwellenrichtung θ_THRESHOLD überschritten wird, was an zeigt, daß entweder eine Ecke erreicht wurde (beispielsweise die Ecken 80, 82 oder 84), oder daß die Grenze nicht durch gehend ist, und infolge irgendeines Spaltes 93 geendet hat. Die Konstante θ_THRESHOLD weist vorzugsweise einen Wert von zwischen 5° und 15° auf.

Wenn der momentane Richtungswert θ′ sich von dem Mittelwert unterscheidet, so daß er größer als die Schwellenrichtung θ_THRESHOLD im Schritt 266 ist, oder wenn der Randpunkt im Schritt 262 nicht aufgefunden wurde, dann stellt im Schritt 270 der Prozessor 60 fest, ob die Konstante N größer als ein Schwellenwert N_THRESHOLD ist. Die Konstante N_THRESHOLD stellt die minimale Anzahl an Malen dar, welche ein Prozessor 60 die Schritte 258 (oder 260), 262, 264, 266 oder 268 durch läuft, bevor festgestellt wird, daß ein Liniensegment exakt aufgefunden wurde. Die Konstante N_THRESHOLD kann eine der artig kleine Zahl wie 3 bis 5 darstellen, wodurch angegeben wird, daß ein Liniensegment von 3 bis 5 Pixeln dazu erforder lich ist, ein Liniensegment zu identifizieren. Allerdings verwendet die vorliegende Erfindung vorzugsweise einen Wert von N in dem Unterprogramm 250 von zwischen 6 und 15, abhän gig von derartigen Faktoren wie der Auflösung der Lesevor richtung 60, der Größe des abgebildeten Symbols 53, usw.

Wenn der Prozessor 60 die Schritte 258 (oder 260), 262, 264, 266 oder 268 für eine Anzahl an Iterationen durchgeführt hat, die kleiner ist als der Wert von N_THRESHOLD, dann aktuali siert im Schritt 272 der Prozessor 60 einen gespeicherten Wert für eine ermittelte X-Ausdehnung oder Breite W. Darauf hin kehrt der Prozessor 60 mit einer Rücksprungmarke zurück, die immer noch auf dem Fehlerwert eingestellt ist, der im Schritt 254 eingestellt wurde, und zwar zu dem Programm oder Unterprogramm, welches das Unterprogramm 250 aufgerufen hat (kehrt also zum Unterprogramm 200 von Fig. 5 zurück). Wenn der Prozessor jedoch in ausreichender Weise die Folge von Schrit ten in dem Programm 250 durchgeführt hat, so daß der Wert von N größer als der Konstantwert für N_THRESHOLD 270 ist, dann speichert im Schritt 274 der Prozessor 60 den Momentanwert von N oder gibt diesen aus, stellt einen Endpunkt (X_END, Y_END) so ein, daß er gleich dem momentanen Punkt ist, der bei den Schritten von 250 aufgefunden wurde, also (X′, Y′). Zusätz lich stellt der Prozessor 60 im Schritt 274 einen Endrich tungswert θ_END so ein, daß dieser gleich dem momentanen Richtungswert θ′ ist. Schließlich speichert der Prozessor im Schritt 274 den momentanen mittleren Richtungswert θ_AVE oder stellt diesen zur Verfügung, und ändert die Rücksprung marke auf einen Erfolgswert. Daraufhin aktualisiert im Schritt 272 der Prozessor 60 den gespeicherten Wert für W, und kehrt dann zu dem Programm oder Unterprogramm zurück, welches das Unterprogramm 200 aufgerufen hatte (kehrt also zum Unterpro gramm 200 zurück).

Im Schritt 272 ruft der Prozessor 60 ein Elementenkreuzungs-Unterprogramm 300 auf, um die X-Ausdehnung W zu bestimmen. Bei dem Unterprogramm 300 wird im wesentlichen der Endpunkt (X_END, Y_END) in der Gradientenrichtung θ abgetastet, um die Breite der Grenze oder des Randes an diesem Punkt zu be stimmen. Wie in Fig. 3 gezeigt, weisen nur an den Eckpunkten 82 und 84 die durchgezogenen Grenzen 70 und 72 eine Breite von einer X-Abmessung auf. An anderen Punkten entlang den durchge zogenen Grenzen 70 und 72 können eine oder mehrere Datenzellen der Grenze benachbart angeordnet sein, so daß die Breite in der Gradientenrichtung das Zweifache oder mehr der X-Ausdeh nung betragen kann.

In Fig. 8 im Schritt 302 des Elementenkreuzungs-Unterprogramms 300 setzt der Prozessor 60 am Anfang einen Wert k auf Eins, wobei k die Anzahl an Abtastungen darstellt. Der Prozessor 60 ruft im Schritt 304 die Gradientenrichtung θ und die er mittelte X-Ausdehnung W aus dem Speicher ab, ebenso wie einen Startpunkt (X, Y), der für das beispielhafte Symbol 53 in Fig. 3 der Eckpunkt 82 ist. Liegt der Startpunkt am Ende ei ner durchgezogenen Grenze, dann wählt der Prozessor 60 einen Startpunkt aus, der die Hälfte der X-Ausdehnung (1/2W) rück wärts entlang der Grenze darstellt (also nach links). Darauf hin erfaßt im Schritt 306 der Prozessor 60 eine Intensitäts ablesung I_k(X,Y) am momentanen Punkt (X, Y) und speichert diese, und führt im Schritt 308 einen Vergleich von I_k(X,Y) mit einem Schwellenintensitätswert I_THRESHOLD durch. Wenn die momentane Intensitätsablesung I_k(X,Y) nicht die Schwel lenwertintensität überschreitet, dann stellt der Prozessor 60 fest, daß das Element noch nicht überquert wurde und geht zum Schritt 310 über. Wenn beispielsweise die Pixelintensi tätswerte in einem Bereich von 1 bis 16 liegen, wobei die niedrigen Werte ein schwarzes Element bezeichnen, dann stellt der Prozessor 60 im Schritt 308 fest, ob der momentane Inten sitätswert für den momentanen Pixel kleiner als etwa in der Mitte des Wertebereiches liegt, beispielsweise kleiner als ein Wert von 8 ist.

Im Schritt 310 stellt der Prozessor 60 einen neuen Punkt ein, der neue X- und Y-Achsenkoordinaten aufweist, nämlich als X_NEW = X + cos θ und Y_NEW = Y + sin θ. Dann stellt im Schritt 312 der Prozessor 60 den Wert X = X_NEW ein, den Wert Y = Y_NEW, und inkrementiert k um Eins. Der Prozessor 60 springt zurück zum Schritt 360, bewegt sich zum neuen Ab tastpunkt I_k(X,Y), und macht weiter. Auf diese Weise bewegt sich der Prozessor 60 durch einen Endabschnitt der ersten durchgezogenen Grenze 70.

Wenn jedoch im Schritt 380 der Prozessor 60 feststellt, daß die Intensitätsablesung I_k(X,Y) die Schwellenwertintensität überschreitet, und daß die Möglichkeit besteht, daß der Ele ment überquert wurde, dann geht der Prozessor zum Schritt 314 über. Im Schritt 314 überprüft der Prozessor 60 Intensitäts pegel an zwei vorher gespeicherten Punkten und an zwei Punk ten hinter der momentanen Intensität I_k(X,Y), und vergleicht diese Werte mit der Hälfte der Schwellenwertintensität auf folgende Weise:

½|(I _k-1+I_k-2)-(I_k+1+I_k+2)|<.5 · I_THRESHOLD (1)

Dieser zusätzliche Schritt unterstützt die Ermittlung, ob das Element tatsächlich überquert wurde, oder ob irgendeine Anomalie aufgetreten ist. Wenn die Differenz der Intensitä ten vor und nach dem momentanen Punkt nicht die Hälfte der Schwellenwertintensität überschreitet, dann stellt der betref fende Punkt nur eine Anomalie infolge einer Reflexion dar, eine Beschädigung des Symbols 53, einen Druckfehler, usw. Der Prozessor 60 berechnet dann Koordinaten X_NEW und Y_NEW und inkrementiert wie voranstehend geschildert den Wert für k im Schritt 312, und kehrt zum Schritt 306 in dem Unterprogramm 300 zurück.

Wenn jedoch die Differenz der Intensitäten größer als die Hälfte der Schwellenwertintensität ist, dann ist es wahr scheinlich, daß die durchgezogene Grenze 70 überquert wurde. Daher geht der Prozessor 60 zum Schritt 316 über, um die Ent fernung des Kreuzungspunkts von dem ursprünglichen Start punkt unter Verwendung folgender Entfernungsformel zu bestim men:

Schließlich geht der Prozessor 60 zum Schritt 318 über, in welchem er die berechnete Entfernung (dist) mit der ermittel ten X-Ausdehnung des Symbols W vergleicht. Ist die Entfernung entweder kleiner als 50% der ermittelten X-Ausdehnung oder größer als 150% der ermittelten X-Ausdehnung, dann stellt der Prozessor 60 fest, daß die berechnete Abmessung der durch gezogenen Grenze 70 zu klein oder zu groß ist, um korrekt zu sein, und geht zum Schritt 320 über, in welchem er zu dem Programm oder Unterprogramm zurückkehrt, welches das momentane Unterprogramm 300 aufrief, und anzeigt, daß der Versuch, das Element zu überqueren, fehlgeschlagen ist. Liegt jedoch die Entfernung zwischen 50% und 150% der ermittelten X-Ausdeh nung, dann geht der Prozessor 60 zum Schritt 322 über, und kehrt zu dem Programm 200 oder dem Unterprogramm zurück, wel ches das Unterprogramm 300 aufgerufen hat. Zusätzlich gibt der Prozessor 60 im Schritt 322 den neuen Wert für W zurück, auf der Grundlage der neu ermittelten Entfernung dist.

Unter Rückkehr zum Schritt 272 in Fig. 6 aktualisiert der Prozessor 60 den gespeicherten Wert der ermittelten X-Ausdeh nung W durch den neu empfangenen Wert für W. Der Prozessor 60 kann beispielsweise den Momentanwert der ermittelten X-Ausdehnung W durch die Entfernung dist mitteln, um eine exak tere Bestimmung der X-Ausdehnung zur Verfügung zu stellen. Dies führt dazu, daß der Prozessor 60 die X-Ausdehnung für das Symbol 53 feststellen kann, trotz Verzerrungen, beispiels weise den optischen Verzerrungen, die in Fig. 4 gezeigt sind, wobei die X-Ausdehnung in der Ecke 82 erheblich größer ist als die X-Ausdehnung in der Ecke 84. Der Prozessor 60 kann auch andere Verfahren zur Ermittlung der X-Ausdehnung des Sym bols 53 einsetzen, die zur Verwendung bei der vorliegenden Erfindung auf geeignete Weise modifiziert wurden, beispiels weise gemäß der gleichzeitig anhängigen Anmeldung des vorlie genden Erfinders, Orientation Independent Method for Robust Computing of X-Dimensions in Code 1 Symbols, Anmeldung Nr. 08/524 368, eingereicht am 6. September 1995.

Wiederum in Fig. 5 stellt im Schritt 208 der Prozessor 280 die Richtungsmarke auf einen Wert "rechts" ein. Daraufhin findet im Schritt 210 der Prozessor 60 ein Liniensegment auf der rechten Seite des Startpunktes (X, Y). Der Prozessor 60 ruft erneut das Randauffindungs-Unterprogramm 250 von Fig. 6 auf, abgesehen davon, daß die im Schritt 252 eingegebene Richtungs marke den Wert "rechts" aufweist. Unter erneuter Durchführung des Unterprogramms 250 beendet der Prozessor 60 das Unterpro gramm 200 und kehrt zum Hauptprogramm 100 von Fig. 2 zurück.

Im Schritt 106 ermittelt der Prozessor 60 in dem Hauptprogramm 100, ob eine der Grenzen, oder ein Abschnitt der Grenzen 70 oder 72, in dem Unterprogramm 200 aufgefunden wurde, durch Untersuchung der Daten, die zum Hauptprogramm zurückbefördert wurden, beispielsweise des Wertes der Rücksprungmarke des Liniensegment-Auffindungsunterprogramms 250 (Fig. 6). Wurde kein Liniensegment aufgefunden, dann endet das Programm 100. Die Lesevorrichtung 50 sorgt für eine hörbare und/oder sicht bare Fehleranzeige für den Benutzer, wodurch dem Benutzer an gezeigt wird, daß er das Symbol 53 erneut abbilden muß. Nach der erneuten Abbildung des Symbols 53 führt der Prozessor 60 das Programm 100 erneut durch, als zweiten Versuch zum Deko dieren des Symbols. Alternativ hierzu könnte, wie hier be schrieben, das Programm 100 versuchen, das Bild des Symbols 53 innerhalb des gespeicherten Bildes dadurch aufzufinden, daß es durch darauffolgende Schritte in dem Programm durch läuft, und versucht, andere wesentliche Merkmale des Finder musters aufzufinden, beispielsweise gegenüberliegende Ecken, teilweise oder vollständige gestrichelte Grenzen 74 oder 76, usw., und hierdurch die Außengrenzen des Symbols ermittelt. Um jedoch einen Ausgleich zwischen Auffindungs- und Dekodier geschwindigkeit und der Komplexizität des Auffindungsalgo rithmus zu erreichen, nimmt der Prozessor 60 im Schritt 106 an, daß das Symbol 53 zu stark beschädigt ist, als daß schnell eine exakte Ermittlung der Grenzen des Symbols erreicht wer den könnte. Daher endet das Programm 100 im Schritt 106, wenn keine Teilgrenze aufgefunden wird.

Wenn der Prozessor 60 im Schritt 106 feststellt, daß eine der Grenzen 70 oder 72 aufgefunden wurde, dann versucht der Pro zessor 60 im Schritt 108, die durchgezogene Ecke 80 am lin ken Ende der aufgefundenen Linie zu finden. Daher ruft im Schritt 108 der Prozessor 60 ein Eckenauffindungs-Unterpro gramm 150 auf. Wie aus Fig. 9 hervorgeht, beginnt das Ecken auffindungs-Unterprogramm 350 im Schritt 352 damit, daß ein Startpunkt (X, Y) eingegeben wird, die Randrichtung θ, ein Wert für die Endemarke, und die ermittelte X-Ausdehnung oder Breite W. Der Startpunkt (X, Y) ist der Endpunkt, der vorher am linken Ende der aufgefundenen Linie im Schritt 206 (Fig. 5) aufgefunden wurde, wogegen die Randrichtung θ die Gra dientenrichtungen entsprechend diesem Endpunkt ist. Die End marke wird auf den Wert "links" im Schritt 108 (Fig. 2) ein gestellt, wogegen die Breite W im Schritt 272 (Fig. 6) ermit telt wurde.

Im Schritt 354 stellt der Prozessor 60 fest, ob die Endmarke den Wert "links" aufweist. Ist dies der Fall, dann wird im Schritt 356 eine Richtungsvariable Θ₁ auf einen Wert der Randrichtung θ plus 90° oder π/2 eingestellt. Alternativ, wenn die Richtungsmarke nicht auf den Wert "links" eingestellt ist (also auf rechts), dann stellt im Schritt 358 der Prozes sor 60 die Richtungsvariable Θ₁ auf einen Wert von minus 90° oder π/2 ein. Im Schritt 360 stellt der Prozessor 60 ei nen Zählerwert N auf einen Wert von 1 ein. Der Prozessor 60 untersucht darüber hinaus das gespeicherte Bild und bewegt sich oder "springt" um einen Breitenwert W nach links und zwei Breitenwert W nach oben von dem Startpunkt aus. Anders ausgedrückt führt der Prozessor 60 am Anfang einen Sprung nach links zu einem Punkt (X₀, Y₀) aus, welcher folgenden Wert aufweist:

X₀ = X+Wcosθ₁, and (3)

Y₀ = Y + W sin θ₁ (4)

Daraufhin führt der Prozessor 60 einen Sprung um eine Entfer nung des Zweifachen der Breite W zu einem Punkt (X₁, Y₁) durch, der folgenden Wert aufweist:

X₁ = X₀ + 2W cos θ, and (5)

Y₁ =Y₀ + 2Wsinθ. (6)

Im Schritt 362 führt dann der Prozessor 60 eine Bewegung oder einen Sprung um eine Entfernung gleich M nach rechts zu einem neuen Punkt (X₁, Y₁) durch, der folgenden Wert aufweist:
X₁ = X₁ + Wcos(θ₁ + π), and (7)
Y₁ = Y₁ + Wsin(θ₁ + π). (8)

Im Schritt 364 findet der Prozessor 60 einen Randpunkt in der Nachbarschaft des neuen Punkts (X₁, Y₁), um einen neuen Randpunkt (X₁, Y₁)_EDGE aufzufinden. Wie hier erläutert untersucht der Prozessor vorzugsweise einen quadratischen Be reich von 3 Pixeln × 3 Pixeln, um einen Übergang von schwar zen auf weiße Pixel innerhalb dieser Nachbarschaft aufzufin den.

Im Schritt 366 stellt der Prozessor fest, ob ein Randpunkt aufgefunden wurde. Ist dies nicht der Fall, dann stellt im Schritt 368 der Prozessor 60 fest, ob der Zählerwert N größer als ein Schwellenwert N_THR ist. Ist der Zählerwert N nicht größer als der Schwellenwert N_THR, dann inkrementiert im Schritt 370 der Prozessor 60 den Wert für N um 1, und richtet einen neuen Punkt ein, der einige Pixel oberhalb des oberen Punkts (X₁, Y₁) liegt, der im Schritt 360 eingerichtet wurde. Anders ausgedrückt springt der Prozessor 60 im Schritt 370 zu einem neuen oberen Punkt (X₁, Y₁), der folgenden Wert aufweist:

X₁ = X₀ + (2+N)*Wcosθ, and (9)

Y₁ = Y₀ + (2+N)*Wsinθ. (10)

Auf diese Weise richtet, wenn die Ecke 80 beschädigt ist, wie durch die beschädigte Ecke 92′ in Fig. 7 angedeutet, der Prozessor 60 einen neuen Punkt oberhalb im Schritt 372 ein, in dem Versuch, sich über die beschädigte Ecke hinaus zu ei nem Punkt am Ende der zweiten durchgezogenen Grenze 72 zu bewegen. Daraufhin wiederholt der Prozessor 60 die Schritte 362, 364, 366, 368 und 372, wenn sich der Prozessor schritt weise nach oben bewegt, bis entweder im Schritt 366 ein Rand gefunden wird, oder der Zählerwert N größer als der Schwel lenwert N_THR ist.

Der Wert N_THR gibt die Anzahl an Malen an, welche der Pro zessor 60 durch die Schritte 362, 364, 366, 368 und 372 hin durchgelaufen ist. Nach einer festgelegten Anzahl an Itera tionen dieser Schritte, beispielsweise N_THR = 5, ist dann während der sechsten Iteration der Wert N größer als der Schwellenwert N_THR, was anzeigt, daß die Ecke 80 zu stark beschädigt ist, oder daß der Prozessor 60 ein Bild in dem gespeicherten Bild untersucht, welches dem Symbol 53 ähnlich ist, jedoch dieses nicht darstellt. Daher schickt im Schritt 372 der Prozessor 60 einen Fehlerwert zum Hauptprogramm 100 zurück, und endet das Eckenauffindungs-Unterprogramm 350.

Nimmt man an, daß im Schritt 366 ein Randpunkt aufgefunden wurde, dann findet im Schritt 374 der Prozessor 60 eine Linie, die vom Randpunkt (X₁, Y₁)_EDGE an beiden Seiten aus geht, und findet die Endpunkte der aufgefundenen Linie auf. Dann ruft der Prozessor 60 im Schritt 374 das Linienauffin dungs-Unterprogramm 200 von Fig. 5 auf. Nach Auffinden der Linie und der Endpunkte im Unterprogramm 200 bestimmt der Prozessor 60 im Schritt 376, ob der Endpunkt (X_END, Y_END), der an der rechten Seite der im Schritt 374 aufgefundenen Linie liegt, nahe am Startpunkt (X, Y) liegt, welcher der End punkt ist, der an der linken Seite der Linie liegt, die im Schritt 104 (Fig. 2) bestimmt wurde. Im Schritt 376 bestimmt der Prozessor 60 die Entfernung entsprechend Gleichung (2) zwischen dem Endpunkt (X_END, Y_END) und dem Startpunkt (X, Y), und stellt dann fest, ob die Entfernung kleiner als ein Schwellenwert ist. Der Schwellenwert kann innerhalb der Hälf te bis zum Zweifacher der ermittelten X-Ausdehnung liegen, und kann ein Wert wie beispielsweise einmal der Wert von W sein. Wenn die ermittelte Entfernung nicht kleiner als die Schwelle ist, dann schickt im Schritt 378 der Prozessor 60 einen Fehlerwert an das Hauptprogramm 100 zurück, der anzeigt, daß die Ecke 80 nicht gefunden wurde. Ist jedoch die ermit telte Entfernung kleiner als die Schwelle, dann schickt im Schritt 380 der Prozessor 60 einen Erfolgswert zurück, sowie die Endpunkte der Linie, die im Schritt 374 bestimmt wurden.

Wiederum in Fig. 2 stellt im Schritt 110 der Prozessor 60 fest, ob eine Ecke in dem Eckensuchprogramm 350 von Fig. 9 aufgefunden wurde. Ist dies nicht der Fall, dann stellt der Prozessor 60 im Schritt 112 die Richtungsmarke auf den Wert "rechts" ein, und versucht, die durchgezogene Ecke 80 am rechten Ende der im Schritt 106 festgestellten Linie aufzu finden. Beispielsweise könnte das Symbol 53 von Fig. 3 um 90° im Gegenuhrzeigersinn in dem gespeicherten Bild gedreht sein (wie in Fig. 10 gezeigt), so daß die im Schritt 104 ermittel te Linie die durchgezogene Grenze 72 darstellt (statt die durchgezogene Grenze 70). Daher ist die durchgezogene Ecke 80 rechts von der aufgefundenen Grenze 72 vorhanden. Nach Durch führung des Eckensuchunterprogramms 350 von Fig. 9 kehrt das Unterprogramm zum Hauptprogramm 100 in Fig. 2 zurück, und der Prozessor 60 stellt im Schritt 114 fest, ob die Ecke 80 auf gefunden wurde. Ist dies nicht der Fall, dann springt das Programm 100 zu einem Schritt 132, um die gestrichelten Gren zen 74 und 76 aufzufinden, wobei die durchgezogene Ecke 80 ignoriert wird, wie nachstehend noch genauer erläutert wird. Wie voranstehend jedoch geschildert wurde, kann das Programm 100 auch alternativ mit den übrigen Schritten des Programms weiter machen, in dem Versuch, immer noch die Grenzen eines stark beschädigten oder verzerrten Symbols zu bestimmen.

Wenn der Prozessor 60 im Schritt 110 oder im Schritt 114 feststellt, daß die Ecke 80 aufgefunden wurde, dann versucht im Schritt 116 der Prozessor 60, die durchgezogene Grenze neben der aufgefundenen Ecke aufzufinden. Wenn beispielswei se die erste durchgezogene Grenze 70 am Anfang im Schritt 104 aufgefunden wurde, dann versucht im Schritt 116 der Prozes sor 60, die durchgezogene Grenze 72 aufzufinden. Daher ruft im Schritt 116 der Prozessor das Liniensegment-Auffindungs unterprogramm 250 von Fig. 6 auf, mit einem Startpunkt, wel cher der Eckpunkt ist, der früher aufgefunden wurde, und ei ner auf einen Wert "aufwärts" eingestellten Richtungsmarke, wenn man annimmt, daß das Symbol 53 wie in Fig. 3 gezeigt ausgerichtet ist. Das Unterprogramm 50 wird entsprechend abgeändert, um die neue Richtung zu berücksichtigen, was Fachleute auf diesem Gebiet sofort verstehen werden.

Nach dem Versuch, die zweite Grenze in dem Unterprogramm 250 aufzufinden, stellt der Prozessor 60 im Schritt 118 von Fig. 2 fest, ob die zweite durchgezogene Grenze 72 gefunden wurde. Falls nicht, dann ruft im Schritt 120 der Prozessor 60 das Eckenauffindungsunterprogramm 350 auf, im Versuch, die durch gezogene Ecke 80 am entgegengesetzten Ende der Linie aufzu finden, die im Schritt 104 bestimmt wurde. In Fig. 10 ist ein Symbol 92 gezeigt, welches gleich dem Symbol 53 von Fig. 3 ist, mit der Ausnahme, daß es um 90° im Gegenuhrzeigersinn gedreht ist. Zusätzlich verursacht ein Druckfehler an der Ecke 84 ein Ende der gestrichelten Grenze 74, daß sie mit dem Endpunkt der zweiten durchgezogenen Grenze 72 verschmilzt und mit diesem verbunden ist, so daß eine unechte durchgezogene Ecke 84′ ausgebildet wird. Daher kann die falsche Ecke 84′ im Schritt 108 fehlerhaft als die durchgezogene Ecke 80 fest gestellt werden. Allerdings findet der Prozessor die zweite durchgezogene Grenze im Schritt 116 nicht auf. Wenn der Pro zessor im Schritt 118 feststellt, daß die zweite Grenze nicht vorhanden ist, dann versucht daher im Schritt 120 der Prozes sor 60, die durchgezogene Ecke am entgegengesetzten Ende der Linie aufzufinden, die ursprünglich im Schritt 104 aufgefun den wurde.

Daher ruft im Schritt 120 der Prozessor 60 das Eckenauffin dungs-Unterprogramm 350 von Fig. 9 auf, um zu versuchen, die durchgezogene Ecke 80 am entgegengesetzten Ende der Linie 72 für das Symbol 92 von Fig. 10 aufzufinden. Im Schritt 122 stellt der Prozessor 60 fest, ob die durchgezogene Ecke 80 aufgefunden wurde. Ist dies nicht der Fall, dann endet das Programm. Alternativ könnte, wie voranstehend bereits er wähnt, das Programm 100 dennoch weitergehen und versuchen, die Grenzen des Symbols aufzufinden. Wenn der Prozessor 60 im Schritt 122 feststellt, daß die Ecke 80 aufgefunden wurde, dann versucht im Schritt 124 der Prozessor, die zweite durch gezogene Grenze (also die Grenze 70) aufzufinden, die von der aufgefundenen, durchgezogenen Ecke 80 ausgeht, durch Auf rufen des Liniensegment-Auffindungsunterprogramms 250 von Fig. 6. Daraufhin stellt im Schritt 126 von Fig. 2 der Prozessor 60 fest, ob die zweite durchgezogene Grenze im Schritt 124 aufgefunden wurde, und wenn dies nicht der Fall ist, endet das Programm 100. Wurde die zweite durchgezogene Grenze im Schritt 126 oder 118 aufgefunden, so versucht der Prozessor 60 im Schritt 128, eine erste gestrichelte Grenze aufzufinden, die vom freien Ende der zweiten durchgezogenen Grenze aus aus geht (von der Ecke gegenüberliegend der durchgezogenen Ecke 80 ausgeht).

In Fig. 11 beginnt der Prozessor 60 in einem Auffindungsunter programm 400 für eine gestrichelte Linie im Schritt 402 mit der Eingabe eines Startpunkts (X, Y), einer Richtung θ, ei ner Breite W, und stellt einen Zählerwert N auf 0 ein. Der Startpunkt (X, Y) ist der Endpunkt der durchgezogenen Grenze, beispielsweise der Endpunkt 84 der zweiten durchgezogenen Grenze 72. Die Richtung θ ist die Gradientenrichtung, bei spielsweise die, die senkrecht zur Richtung der durchgezoge nen Grenze 72 verläuft, und sollte parallel zur Richtung der gestrichelten Linie 74 liegen. Im Schritt 404 bewegt sich der Prozessor 60 nach innen auf der durchgezogenen Grenze in be zug auf den Startpunkt (X, Y). Wenn beispielsweise der Start punkt (X, Y) der Eckpunkt 84 der zweiten durchgezogenen Gren ze 72 ist, dann bewegt sich der Prozessor 60 im Schritt 404 um eine Entfernung nach unten, die gleich der Hälfte der X-Abmessung oder 1/2W ist. Daraufhin kreuzt im Schritt 406 der Prozessor 60 die durchgezogene Grenze 72 in der Richtung θ, und berechnet einen neuen Wert für die Breite W in dem Elementenüberkreuzungs-Unterprogramm 300 von Fig. 8, das vor anstehend erläutert wurde.

Im Schritt 408 stellt der Prozessor 60 fest, ob das Ende der durchgezogenen Grenze (oder ein schwarzes Element bei späte ren Iterationsschritten) aufgefunden wurde. Der Prozessor 60 vergleicht die Entfernung dist, die im Schritt 316 des Unter programms 300 ermittelt wurde, mit einem Paar von Entfernungs schwellen. Eine erste Entfernungsschwelle kann das doppelte einer ermittelten X-Abmessung W für Elemente (also 2 _* W₁) betragen, während die zweite Entfernungsschwelle die Hälfte der ermittelten Blockabmessung in X-Richtung W betragen kann. Bekanntlich kann infolge von Druckfehlern, optischen Verzer rungen und dergleichen die X-Abmessung schwarzer oder dunkler Elemente in einem vorgegebenen Symbol größer oder kleiner als die X-Abmessung weißer oder heller Elemente in demselben Sym bol sein, obwohl diese idealerweise gleich sein sollten. Der Prozessor 60 stellt im Schritt 408 fest, ob die ermittelte Entfernung dist zwischen der ersten und zweiten Entfernungs schwelle liegt, auf der Grundlage-der folgenden Beziehung:

½ _* W₁ < W 2 _* W₁ (11)

Wenn der Prozessor im Schritt 408 feststellt, daß die ermit telte Entfernung dist größer als die erste Schwelle 2 _* W ist, was entweder einen starken Druckfehler oder eine Abtastung in den Datenzellen für das Symbol 53 anzeigt, oder kleiner ist als die zweite Schwelle 1/2 _* W, dann endet das Unterprogramm 400. Wenn jedoch die ermittelte Entfernung dist zwischen den Schwellenwerten liegt, dann kreuzt im Schritt 410 der Prozes sor 60 das weiße Element neben der durchgezogenen Grenze 72. Der Prozessor 60 ruft im Schritt 410 erneut das Elementenüber kreuzungs-Unterprogramm 300 von Fig. 8 auf. Das Unterprogramm 300 von Fig. 8 wird jedoch geringfügig abgeändert, um eine Kompensation für das Überkreuzen eines weißen statt eines schwarzen Elements zur Verfügung zu stellen, wie Fachleuten auf diesem Gebiet sofort auffallen wird. Beispielsweise be stimmt der Prozessor 60 im Schritt 308, ob die momentane Pixelintensitätsschwelle kleiner als die Schwellenintensität I_THRESHOLD ist.

Daraufhin stellt im Schritt 412 von Fig. 11 der Prozessor 60 fest, ob das Ende des weißen Elements aufgefunden wurde. Der Prozessor 60 vergleicht die Entfernung dist des weißen Ele ments, die in dem Unterprogramm 300 festgestellt wurde, mit einem entsprechenden Paar von Schwellenwerten. Wenn die er mittelte Entfernung der Breite W größer als die Hälfte der ermittelten X-Abmessung W₂ ist, jedoch kleiner als das Dop pelte der ermittelten weißen X-Abmessung W₂, dann bestimmt der Prozessor 60 auf der Grundlage der nachstehenden Bezie hung, daß das weiße Element ordnungsgemäß überquert wurde:

½ _* W₂ < W 2 _* W₂ (12)

Daher geht der Prozessor 60 zum Schritt 414 über, in welchem er den Wert N um 1 inkrementiert. Andernfalls, wenn die ermit telte Entfernung außerhalb der Schwellenwerte liegt, schickt der Prozessor 60 einen Fehlerwert zurück, und beendet das Unterprogramm 400.

Nach dem Schritt 414 mittelt der Prozessor 60 im Schritt 416 die festgestellten schwarzen und weißen X-Abmessungen W₁ und W₂ entsprechend folgender Gleichungen:

Die gemittelten, festgestellten schwarzen und weißen X-Abmes sungen W₁ und W₂ werden dann später in darauffolgenden Iterationen der Schritte 406, 408, 410, 412 und 414 verwen det, wie nachstehend noch genauer erläutert wird.

Daraufhin stellt im Schritt 418 der Prozessor 60 fest, ob der Zählerwert N größer als ein Schwellenwert N_THRE ist. Der Schwellenwert N_THRE weist vorzugsweise einen Wert von 72 auf, der eine Maximalanzahl an Iterationen durch die Schrit te 406, 408, 410, 412, 414 und 416 angibt. In Fig. 12 zeigt ein Symbol 94 ein größeres Datenmatrixsymbol, welches im we sentlichen aus vier Symbolen entsprechend dem Symbol 53 von Fig. 3 besteht. In der Datenmatrixsymbolik können mehrere Symbole nebeneinander in einer quadratischen Matrix angeord net sein, wie in Fig. 12 gezeigt, um ein einzelnes, größeres Symbol zur Verfügung zu stellen. Momentan verwendet die maxi male Symbolabmessung eine einzige, kombinierte gestrichelte Grenze, die 72 weiße Datenzellen (oder 72 schwarze Datenzel len) aufweist. Wenn daher im Schritt 418 der Prozessor 60 feststellt, daß der Zählerwert N größer als 72 ist, dann untersucht der Prozessor ein beschädigtes Symbol oder unter sucht kein Datenmatrixsymbol, sondern irgendeine andere Infor mation in dem gespeicherten Bild. Wenn jedoch der Zählerwert N kleiner als der Schwellenwert N_THR E ist, dann springt das Programm zurück und führt die Schritte 406, 408, 410, 412, 414 und 416 durch. Diese Schritte werden kontinuierlich durch geführt, bis der Prozessor 60 im Schritt 408 oder 412 kein schwarzes oder weißes Element mehr findet, oder der Schwel lenwert im Schritt 418 überschritten wird.

Wenn der Prozessor 60, wiederum in Fig. 2, die erste gestri chelte Grenze im Schritt 128 aufgefunden hat, beispielsweise die gestrichelte Grenze 74, dann ermittelt der Prozessor 60 im Schritt 130, ob die gestrichelte Grenze aufgefunden wurde. Ist dies nicht der Fall, dann könnte das Symbol eine beschä digte Ecke 84 (oder Ecke 82) aufweisen, wodurch verhindert wird, daß der Prozessor die gestrichelte Grenze in dem Unter programm 400 auffindet. Daher findet im Schritt 132 der Pro zessor 60 das entgegengesetzte Ende der ersten durchgezogenen Grenze auf, die vorher im Schritt 104 ermittelt wurde, bei spielsweise der Grenze 72. Alternativ, wenn der Prozessor 60 im Schritt 114 festgestellt hat, daß die durchgezogene Ecke 80 nicht aufgefunden wurde, geht das Programm 100 dann zum Schritt 132 über.

Daraufhin versucht im Schritt 134 der Prozessor 60, die ande re gestrichelte Grenze aufzufinden, die mit dem aufgefunde nen, entgegengesetzten Ende der durchgezogenen Grenze verbun den ist, unter Einsatz des Auffindungsunterprogramms 400 für eine gestrichelte Grenze gemäß Fig. 11. Wenn beispielsweise die Ecke 84 stark beschädigt ist, dann verwendet der Prozes sor 60 das Unterprogramm 400, um die gestrichelte Grenze 76 aufzufinden, die von der Ecke 82 der durchgezogenen Grenze 70 für das Symbol 53 (Fig. 3) ausgeht. Im Schritt 136 stellt der Prozessor 60 dann fest, ob das Unterprogramm 400 die ge strichelte Grenze aufgefunden hat (beispielsweise die gestri chelte Grenze 76). Ist dies nicht der Fall, so endet das Pro gramm 100. Wenn jedoch das Programm 400 eine der gestrichel ten Grenzen im Schritt 136 oder im Schritt 130 aufgefunden hat, dann findet der Prozessor 60 die andere gestrichelte Grenze.

Zuerst ruft der Prozessor 60 im Schritt 138 das Unterprogramm 400 auf, und versucht, die gestrichelte Grenze aufzufinden, die senkrecht von der ersten aufgefundenen gestrichelten Grenze ausgeht, und findet beispielsweise die gestrichelte Grenze 76, wenn die gestrichelte Grenze 74 vorher im Schritt 128 für das Symbol 53 aufgefunden wurde (Fig. 3). Der Prozes sor 60 beginnt in der Ecke 86, und bewegt sich nach links zur Ecke 84 im Unterprogramm 400, wenn er die gestrichelte Gren ze 74 auffindet. Im Schritt 140 stellt der Prozessor 60 fest, ob die zweite gestrichelte Grenze aufgefunden wurde. Ist dies nicht der Fall, dann findet im Schritt 142 der Prozessor 60 das entgegengesetzte Ende der ersten durchgezogenen Grenze auf, wenn der Prozessor im Schritt 128 die erste gestrichel te Grenze aufgefunden hatte. Beispielsweise kann die Ecke 86, in welcher sich die gestrichelten Grenzen 74 und 76 treffen, stark beschädigt oder verzerrt sein, so daß der Prozessor 60 nicht die gestrichelte Grenze auffinden kann, die senkrecht von der ersten aufgefundenen gestrichelten Grenze ausgeht. Da her versucht im Schritt 144 der Prozessor 60, die gestrichel te Grenze aufzufinden, die mit dem aufgefundenen gegenüber liegenden Endpunkt verbunden ist, in dem Auffindungsunterpro gramm 400 für eine gestrichelte Grenze. Wenn beispielsweise der Prozessor 60 eine erste gestrichelte Grenze 74 im Schritt 128 aufgefunden hat, jedoch nicht die gestrichelte Grenze 76 auffinden konnte, die senkrecht von dieser ausgeht, im Schritt 138, so versucht der Prozessor 60, die gestrichelte Grenze 76 dadurch aufzufinden, daß er in der Ecke 82 beginnt, und sich von dort aus nach oben entlang der gestrichelten Grenze 76 bewegt, im Unterprogramm 400. Im Schritt 146 stellt der Pro zessor 60 fest, ob das Unterprogramm 400 die zweite gestri chelte Grenze aufgefunden hat. Ist dies nicht der Fall, so endet das Programm 100.

Wenn das Programm 200 die zweite gestrichelte Grenze im Schritt 146 oder im Schritt 140 aufgefunden hat, stellt der Prozessor 60 im Schritt 147 fest, ob es der Prozessor nicht geschafft hat, die durchgezogene Ecke 80 im Schritt 114 auf zufinden. Ist dies der Fall, dann findet im Schritt 147 der Prozessor 60 die zweite durchgezogene Grenze auf. Der Prozes sor 60 führt im wesentlichen das Unterprogramm 250 durch, beginnend an dem Endpunkt der zweiten aufgefundenen gestri chelten Grenze, um die noch nicht aufgefundene, durchgezoge ne Grenze aufzufinden. Wenn beispielsweise der Prozessor 60 es nicht geschafft hat, die Ecke 80 aufzufinden, jedoch die durchgezogene Grenze 70 und die gestrichelten Grenzen 76 und 74 aufgefunden hat, so würde der Prozessor 60 im Schritt 147 das Unterprogramm 250 einsetzen, beginnend an der Ecke 84, um die durchgezogene Grenze 72 aufzufinden.

Daraufhin untersucht im Schritt 148 der Prozessor 60 die Ecke 86, an welcher sich die gestrichelten Grenzen 74 und 76 tref fen, um eine Version für das Symbol zu bestimmen. Der Prozes sor 60 stellt fest, ob die gestrichelten Grenzen 74 und 76 annähernd bei denselben kartesischen Koordinaten enden, oder innerhalb einer ermittelten X-Abmessung W der Koordinaten. Wenn die gestrichelten Grenzen annähernd an demselben Eck punkt enden, also an einem schwarzen Element, dann weiß der Prozessor 60, daß das Symbol ein Symbol der Version ECC 140 ist (beispielsweise wie das Symbol 90 von Fig. 4). Wenn je doch die Entfernung zwischen den beiden Eckpunkten annähernd die Quadratwurzel des Doppelten der ermittelten X-Abmessung ist, dann stellt der Prozessor 60 fest, daß die erste und zweite gestrichelte Grenze 74 und 76 an einem weißen Element enden, wie in Fig. 3 gezeigt ist. Ist dies der Fall, dann stellt der Prozessor 60 fest, daß das Symbol 53 ein Symbol der Version ECC 200-Datenmatrix ist. Falls der Prozessor 60 feststellt, daß die Ecke 86 beschädigt ist (beispielsweise dadurch, daß er im Schritt 138 die zweite gestrichelte Grenze nicht auffinden kann), dann untersucht der Prozessor die bei den gestrichelten Grenzen 74 und 76, um die Version des Sym bols zu bestimmen.

Im Schritt 150 wählt der Prozessor 60 das geeignete Dekodier programm aus, und dekodiert das aufgefundene Bild des Symbols 53. Da der Prozessor 60 die Version des Datenmatrixsymbols aus dem vorherigen Schritt 148 kennt, kann der Prozessor 60 das geeignete Dekodierprogramm auswählen. Die Dekodierprogramme sind auf diesem Gebiet wohlbekannt. Falls erforderlich, kann der Prozessor 60 im Schritt 150 bekannte lineare Anpassungs programme durchführen, um Linien durch die aufgefundenen Ab schnitte der durchgezogenen Grenzen 70 und 72 anzupassen, und die gestrichelten Grenzen 74 und 76, und/oder die Eckpunkte 80, 82, 84 und 86, um einen Umfangs- oder Begrenzungskasten für das Symbol 53 festzulegen. Wenn eine Ecke oder ein Ab schnitt einer Grenze fehlen würde, könnten die linearen An passungsverfahren exakt die Außengrenzen des Symbols bestim men, um das Auffinden der Datenzellen innerhalb des Symbols zu erleichtern. Lineare Anpassungsverfahren sind auf diesem Gebiet bekannt, und wären besonders vorteilhaft bei einem stark verzerrten Symbol, beispielsweise dem Symbol 90 von Fig. 4. Die vorliegende Erfindung kann auf der Grundlage der hier erfolgten, detaillierten Beschreibung so angepaßt werden, daß sie bekannte lineare Anpassungsverfahren und Grenzkasten ermittlungsverfahren verwendet, wie sie beispielsweise in den gleichzeitig anhängigen Anmeldungen des vorliegenden Er finders beschrieben sind, die nachstehend angegeben sind: "Method and Apparatus for Locating Data Regions in Stored Images of Symbols", Anmeldung Nr. 08/571 257, eingereicht am 11. Dezember 1995, und "Method and Apparatus for Accurately Locating Data Regions in Stored Images of Symbols", Anmeldung Nr. 08/607 100, eingereicht am 26. Februar 1996. Sämtliche genannten U.S.-Patente und -Anmeldungen werden in die vor liegende Anmeldung durch Bezugnahme eingeschlossen, als Teil der vorliegenden Anmeldung.

Obwohl zur Erläuterung bestimmter Ausführungsformen der vor liegenden Erfindung und Beispiele für diese beschrieben wur den, lassen sich verschiedene Abänderungen vornehmen, ohne vom Wesen und Umfang der Erfindung abzuweichen, wie Fachleu ten auf diesem Gebiet bekannt ist. Die hier vorgestellte Lehre gemäß der vorliegenden Erfindung kann bei anderen Maschinen ansichtssystemen eingesetzt werden, nicht nur unbedingt bei Lesevorrichtungen für maschinenlesbare Symbole. Zwar wurde beispielsweise die vorliegende Erfindung voranstehend allge mein so beschrieben, daß sie das zentrale Findermuster eines Datenmatrixsymbols auffindet, jedoch läßt sich die vorliegen de Erfindung auch bei Maschinenvisionssystemen einsetzen, die ein Auffinden entsprechender linearer, gestrichelter und "L-förmiger" Muster erfordern. Die vorliegende Erfindung läßt sich einfach bei Computersystemen mit Roboterarmen zum Auf finden der Ränder quadratischer, rechteckiger oder anderer polygonförmiger Gegenstände in verschiedenen Umgebungen ein setzen, beispielsweise im Zusammenhang mit einer automati sierten Montage.

Während das Programm 100 endet, nachdem es nicht erreicht wurde, bestimmte Abschnitte des Findermusters aufzufinden, beispielsweise Abschnitte bestimmter Grenzen, kann darüber hinaus das Programm dennoch fortgesetzt werden, nachdem das entsprechende Merkmal nicht aufgefunden wurde, obwohl ein derartiges Programm komplizierter und daher langsamer werden kann als jenes Programm, welches hier allgemein beschrieben wurde. Diese und weitere Änderungen können bei der Erfindung angesichts der voranstehenden, detaillierten Beschreibung vorgenommen werden. Allgemein ausgedrückt sollten in den nach folgenden Patentansprüchen die verwendeten Begriffe nicht so verstanden werden, daß sie die Erfindung auf die spezifische Ausführungsform beschränken, die in der Beschreibung und den Patentansprüchen geschildert wird, sondern die Begriffe soll ten so verstanden werden, daß sie jedes Auffindungsprogramm umfassen, welches entsprechend den Patentansprüchen arbeitet, um Merkmale oder Symbole aufzufinden, beispielsweise Daten matrixsymbole. Begriffe wie beispielsweise das Auffinden ei nes Merkmals sollten allgemein so verstanden werden, daß sie jedes Verfahren oder jede Struktur umfassen, die zur automa tischen Erkennung eines unterscheidbaren Merkmals dienen, beispielsweise einer Linie einer Grenze, die auf ein Objekt aufgedruckt ist, oder eine Linie, welche ein erkennbares Teil des Gegenstandes bildet. Wesen und Umfang der vorliegenden Erfindung ergeben sich daher aus der Gesamtheit der vorliegen den Anmeldeunterlagen und sollen von den beigefügten Patent ansprüchen umfaßt sein.

Claims

1. Verfahren zum Auffinden eines vorbestimmten Bildes inner halb eines gespeicherten Bildes, wobei das vorbestimmte Bild erste und zweite lineare Merkmale und erste und zwei te gestrichelte lineare Merkmale neben den ersten und zweiten linearen Merkmalen aufweist, mit folgenden Schrit ten:
Auffinden eines Randpunktes eines der ersten und zweiten linearen Merkmale;
Auffinden zumindest eines Abschnitts eines der ersten und zweiten linearen Merkmale auf der Grundlage des aufgefun denen Randpunktes;
Auffinden zumindest eines Abschnitts eines anderen der ersten und zweiten linearen Merkmale;
Auffinden zumindest eines Abschnitts des ersten gestrichel ten Merkmals auf der Grundlage des aufgefundenen Abschnitts des ersten oder zweiten linearen Merkmals;
Auffinden des zweiten gestrichelten Merkmals auf der Grund lage des aufgefundenen Abschnitts des ersten gestrichelten Merkmals oder des ersten durchgezogenen Merkmals; und
Auffinden einer Position des vorbestimmten Bildes in dem gespeicherten Bild auf der Grundlage der aufgefundenen Ab schnitte der ersten und zweiten linearen und gestrichel ten Merkmale.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß der Schritt des Auffindens zumindest eines Abschnitts eines der ersten und zweiten linearen Merkmale folgende Schritte umfaßt:

Auffinden eines neuen Randpunkts des ersten durchgezoge nen Merkmals, der von einer ersten Seite des aufgefundenen Randpunkts ausgeht;
Ermitteln, ob eine Randrichtung an dem neuen Randpunkt eine vorbestimmte Beziehung zu einem Schwellenrichtungswert aufweist; und
Wiederholung der Schritte des Auffindens eines neuen Rand punktes und Ermittlung, bis die Randrichtung die vorbe stimmte Beziehung zu dem Schwellenrichtungswert aufweist.

3. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß der Schritt des Auffindens zumindest eines Abschnitts eines der ersten und zweiten linearen Merkmale einen Rand des ersten durchgezogenen Merkmals auffindet, der von gegen überliegenden Seiten des aufgefundenen Randpunkts ausgeht.

4. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß sich das erste und zweite lineare Merkmal in einer gemein samen Ecke treffen, und daß das Verfahren weiterhin fol gende Schritte aufweist:
Auffinden eines ersten Endpunkts des ersten durchgezoge nen Merkmals;
Bewegung zu einem Ort in dem gespeicherten Bild, der eine vorbestimmte Entfernung von dem Endpunkt weg liegt Auffinden eines neuen Randpunkts des zweiten durchgezogenen Merkmals in der Nähe des Ortes;
Feststellung einer Linie, die von dem neuen Randpunkt aus geht und entlang dem zweiten durchgezogenen Merkmal ver läuft, wobei die Linie einen zweiten Endpunkt in der Nähe des ersten Endpunkts aufweist;
Ermittlung, ob eine Entfernung zwischen dem ersten Endpunkt und dem zweiten Endpunkt eine vorbestimmte Beziehung zu einem Schwellenwert aufweist; und
Bestimmung der gemeinsamen Ecke auf der Grundlage des ersten und zweiten Endpunkts.

5. Verfahren nach Anspruch 4, gekennzeichnet durch den Schritt des Auffindens der gemeinsamen Ecke, auf der Grundlage des aufgefundenen Abschnitts des ersten durchgezogenen Merk mals, wobei der Schritt der Auffindung zumindest eines Ab schnitts eines anderen Abschnitts einen Abschnitt des zwei ten durchgezogenen Merkmals auf der Grundlage der aufgefun denen gemeinsamen Ecke auffindet.

6. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die ersten und zweiten gestrichelten Merkmale dunkle und helle abwechselnde Elemente enthalten, wobei die Schritte zum Auffinden der ersten und zweiten gestrichelten Merkmale folgende Schritte umfassen:

(a) Beginn an einem freien Ende des ersten durchgezogenen Merkmals;
(b) Überqueren eines dunklen Elements;
(c) Bestimmung einer Breite des dunklen Elements;
(d) Ermittlung, ob die Breite des dunklen Elements akzep tierbar ist, auf der Grundlage eines Werts für die Breite des dunklen Elements;
(e) Überqueren eines hellen Elements;
(f) Bestimmung einer Breite des hellen Elements;
(g) Ermittlung, ob die Breite des hellen Elements akzep tierbar ist, auf der Grundlage eines Werts für die Breite des hellen Elements;
(h) Aktualisierung der Werte für die Breite des dunklen und hellen Elements auf der Grundlage der festgestell ten Breiten der dunklen und hellen Elemente; und
(i) Wiederholung der Schritte (b) bis (h), bis das erste gestrichelte Merkmal aufgefunden wurde.

7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß der Schritt des Auffindens des zweiten gestrichelten Merkmals folgende Schritte umfaßt:
Beginn an einem freien Ende des ersten gestrichelten Merk mals; und
Wiederholung der Schritte (b) bis (h) in einer Richtung zum freien Ende des zweiten oder ersten linearen Merkmals hin, bis das zweite gestrichelte Merkmal aufgefunden wur de.

8. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß der Schritt des Auffindens des zweiten gestrichelten Merkmals folgende Schritte umfaßt:
Beginn an einem freien Ende des zweiten oder ersten linea ren Merkmals; und
Wiederholung der Schritte (b) bis (h), bis das zweite ge strichelte Merkmale aufgefunden wurde.

9. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß der Schritt der Überquerung des dunklen Elements folgende Schritte umfaßt:
Durchführung einer Ablesung einer Intensität an einer momentanen Position;
Vergleichen der Intensität mit einer Schwellenwertinten sität;
inkrementaler Vorschub der Position entlang einer Über querungsrichtung, bis eine Intensität an einem momentanen Abschnitt die Schwellenwertintensität überschreitet; und
Festlegung des momentanen Abschnitts, an welchem die Schwellenwertintensität überschritten wurde, als Ende des dunklen Elements.

10. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das erste gestrichelte Merkmal mehrere linear angeordnete dunkle Elemente umfaßt, wobei die Schritte des Auffindens des ersten gestrichelten Merkmals folgende Schritte um faßt:

(a) Beginn an einem freien Ende des ersten durchgezogenen Merkmals
(b) Überqueren eines dunklen Elements;
(c) Bewegung zum Beginn eines nächsten dunklen Elements in den mehreren, linear angeordneten dunklen Elemen ten; und
(d) Wiederholung der Schritte (b) und (c), bis das erste gestrichelte Merkmal aufgefunden wurde.

11. Verfahren zum Auffinden eines Bildes eines maschinenles baren Symbols innerhalb eines gespeicherten Bildes, wobei das Symbol ein vorbestimmtes Muster am Umfang des Symbols aufweist, das vorbestimmte Muster erste und zweite durch gezogene lineare Merkmale aufweist, die sich in einer gemeinsamen durchgezogenen Ecke treffen, und erste und zweite gestrichelte lineare Merkmale aufweist, die von freien Enden der ersten und zweiten durchgezogenen Merk male ausgehen, und sich in einer gemeinsamen gestrichel ten Ecke treffen, mit folgenden Schritten:
Auffinden eines Randpunktes des vorbestimmten Musters;
Untersuchung zumindest eines Abschnitts des Umfangs des Symbols;
Auffinden, auf der Grundlage des Untersuchungsschritts, zumindest von Abschnitten des vorbestimmten Musters, wo bei die aufgefundenen Abschnitte entweder (a) durchge zogene und gestrichelte Ecken sind, oder (b) zumindest ein Abschnitt der ersten und zweiten durchgezogenen und gestrichelten Merkmale, oder (c) zumindest ein Abschnitt der ersten und zweiten gestrichelten Merkmale und der durchgezogenen Ecke, oder (d) zumindest ein Abschnitt der ersten und zweiten durchgezogenen Merkmale und die gestrichelte Ecke, oder (e) zumindest vollständige Orte von dreien der vier Merkmale; und
Bestimmung einer Position des Symbols in dem gespeicher ten Bild auf der Grundlage der aufgefundenen Abschnitte des vorbestimmten Musters.

12. Verfahren nach Anspruch 11, dadurch gekennzeichnet, daß der Auffindungsschritt folgende Schritte umfaßt:
Auffinden eines neuen Randpunktes des ersten durchgezoge nen Merkmals, welches von einer ersten Seite des aufge fundenen Randpunkts ausgeht;
Ermittlung, ob eine Randrichtung an dem neuen Randpunkt eine vorbestimmte Beziehung zu einem Schwellenrichtungs wert aufweist; und
Wiederholung der Schritte des Auffindens eines neuen Rand punkts und Ermittlung, bis die Randrichtung die vorbe stimmte Beziehung zum Schwellenrichtungswert aufweist.

13. Verfahren nach Anspruch 11, dadurch gekennzeichnet, daß der Schritt des Auffindens einen Rand des ersten durch gezogenen Merkmals auffindet, der von entgegengesetzten Seiten des aufgefundenen Randpunktes ausgeht, und die durchgezogene Ecke an einem Ende des aufgefundenen Randes des ersten durchgezogenen Merkmals auffindet.

14. Verfahren nach Anspruch 11, dadurch gekennzeichnet, daß der Auffindungsschritt folgende Schritte umfaßt:
Auffinden eines ersten Endpunktes des ersten durchgezoge nen Merkmals;
Bewegung zu einem Ort in dem gespeicherten Bild, der eine vorbestimmte Entfernung von dem Endpunkt aufweist;
Auffinden eines neuen Randpunktes des zweiten durchgezoge nen Merkmals in der Nähe des Ortes;
Bestimmung einer Linie, die von dem neuen Randpunkt aus geht und entlang dem zweiten durchgezogenen Merkmal ver läuft, wobei die Linie einen zweiten Endpunkt in der Nähe des ersten Endpunkts aufweist;
Ermittlung, ob eine Entfernung zwischen dem ersten und zweiten Endpunkt eine vorbestimmte Beziehung zu einem Schwellenwert aufweist; und
Auffinden des Punktes der durchgezogenen Ecke als zwei ter Endpunkt, wenn die Entfernung zwischen dem ersten und zweiten Endpunkt die vorbestimmte Beziehung zu dem Schwellenwert aufweist.

15. Verfahren nach Anspruch 11, dadurch gekennzeichnet, daß das erste gestrichelte Merkmal mehrere linear angeordnete dunkle Elemente enthält, wobei die Schritte des Auffin dens folgende Schritte umfassen:

(a) Beginn am freien Ende des ersten durchgezogenen Merk mals;
(b) Überqueren eines dunklen Elements;
(c) Bewegung zum Beginn eines nächsten dunklen Elements bei den mehreren linear angeordneten dunklen Elemen ten; und
(d) Wiederholung der Schritte (b) und (c), bis das erste gestrichelte Merkmal aufgefunden wurde.

16. Verfahren nach Anspruch 11, dadurch gekennzeichnet, daß das maschinenlesbare Symbol ein Datenmatrixsymbol ist, wobei der Schritte des Auffindens entweder die gestrichel te Ecke oder das erste und zweite gestrichelte Merkmal insgesamt auffindet, wobei das Verfahren weiterhin fol gende Schritte umfaßt:
Ermittlung einer Version des Datenmatrixsymbols auf der Grundlage der aufgefundenen gestrichelten Ecke oder der ersten und zweiten gestrichelten Merkmale; und
Dekodieren des Datenmatrixsymbols auf der Grundlage der ermittelten Version.

17. Vorrichtung zum Auffinden eines Bildes eines vorbestimm ten Musters innerhalb eines gespeicherten Bildes, wobei das vorbestimmte Muster erste und zweite durchgezogene lineare Merkmale aufweist, die sich in einer gemeinsamen Ecke treffen, und erste und zweite gestrichelte lineare Merkmale aufweist, die von freien Enden der ersten und zweiten durchgezogenen Merkmale ausgehen, wobei die Vor richtung aufweist:
einen Sensor, der von dem vorbestimmten Muster reflek tiertes Licht empfängt, und hieraus ein Ausgangssignal erzeugt;
einen Empfänger, der das Ausgangssignal empfängt und ein Datensignal erzeugt, welches zumindest Abschnitte des vorbestimmten Musters anzeigt;
einen Speicher zum Speichern des Datensignals, welches zumindest Abschnitte des vorbestimmten Musters darstellt; und
einen Prozessor zum Auffinden des vorbestimmten Musters in dem Speicher, wobei der Prozessor so programmiert ist, daß er (a) einen Randpunkt eines der ersten und zweiten durchgezogenen Merkmale auffindet, (b) zumindest einen Abschnitt eines der ersten und zweiten durchgezogenen Merkmale auffindet, auf der Grundlage des aufgefundenen Randpunkts, (c) zumindest einen Abschnitt eines anderen der ersten und zweiten durchgezogenen Merkmale auffin det, (d) die ersten und zweiten gestrichelten Merkmale auffindet, auf der Grundlage der aufgefundenen ersten oder zweiten durchgezogenen Merkmale; und (e) eine Posi tion des vorbestimmten Bildes in dem Speicher auffindet, auf der Grundlage der aufgefundenen ersten und zweiten durchgezogenen und gestrichelten Merkmale.

18. Vorrichtung nach Anspruch 17, dadurch gekennzeichnet, daß der Prozessor zumindest einen Abschnitt eines der ersten und zweiten durchgezogenen Merkmale dadurch auffindet, daß er einen Rand des ersten durchgezogenen Merkmals auffindet, der von entgegengesetzten Seiten des aufgefun denen Randpunkts innerhalb des Speichers ausgeht.

19. Vorrichtung nach Anspruch 17, dadurch gekennzeichnet, daß der Prozessor den gemeinsamen Eckpunkt dadurch auffindet, daß er (a) einen ersten Endpunkt des ersten durchgezoge nen Merkmals auffindet, (b) sich zu einem Ort in dem ge speicherten Bild bewegt, der eine vorbestimmte Entfernung von dem Endpunkt aufweist, (c) einen neuen Randpunkt des zweiten durchgezogenen Merkmals in der Nähe des Ortes auf findet, (d) eine Linie bestimmt, die von dem neuen Rand punkt ausgeht und entlang dem zweiten durchgezogenen Merk mal verläuft, wobei die Linie einen zweiten Endpunkt ent hält, der in der Nähe des ersten Endpunkts liegt, und (e) feststellt, ob eine Entfernung zwischen dem ersten und zweiten Endpunkt eine vorbestimmte Beziehung zu einem Schwellenwert aufweist.

20. Vorrichtung nach Anspruch 17, dadurch gekennzeichnet, daß das erste gestrichelte Merkmale mehrere linear angeordne te dunkle Elemente enthält, wobei der Prozessor das erste gestrichelte Merkmal dadurch auffindet, daß er (a) an ei nem freien Ende des ersten durchgezogenen Merkmals be ginnt, (b) ein dunkles Element überquert, (c) zum Beginn eines nächsten dunklen Elements in den mehreren linear angeordneten dunklen Elementen hin geht, und (d) die Schritte (b) und (c) wiederholt, bis das erste gestrichel te Merkmal aufgefunden wurde.