DE69504069T2

DE69504069T2 - Verfahren und gerät zu dekodierung von zweidimensionalen zeichen im raumbereich

Info

Publication number: DE69504069T2
Application number: DE69504069T
Authority: DE
Inventors: Ming Danbury Ct 06811 Lei; Joe Brookfield Ct 06804 Zheng
Original assignee: United Parcel Service of America Inc; United Parcel Service Inc
Current assignee: United Parcel Service of America Inc; United Parcel Service Inc
Priority date: 1994-06-07
Filing date: 1995-06-01
Publication date: 1998-12-10
Anticipated expiration: 2015-06-02
Also published as: CA2187209A1; ES2122656T3; EP0764307A1; DE69504069D1; DK0766191T3; JP2771899B2; JPH10501082A; CA2187209C; DE69515481T2; PT766191E; ES2144185T3; US6094509A; ATE169754T1; ATE190415T1; EP0766191B1; DE69515481D1; EP0764307B1; EP0766191A3; EP0766191A2; GR3033330T3

Description

ERFINDUNGS GEBIET

Die vorliegende Erfindung betrifft optisch codierte Symboliken und insbesondere das Codieren eines zweidimensionalen optischen Symbols im räumlichen Bereich.

STAND DER BETREFFENDEN TECHNIK

Optische Symbolik betrifft ein informationsmäßig codiertes Symbol, das sich nur von einem optischen Erkennungsmechanismus über einen Decodierprozeß lesen läßt. Seit Jahren ist für den Strichcode als maschinenlesbare Symbolik geworben worden. Ein Strichcode ist ein eindimensionales Symbol, das eine eindeutige Seriennummer enthält, die in schwarzen und weißen Strichen codiert ist. Strichcodes sind weitverbreitet als Indizes, um physische Objekte größeren Datenbanken, die ausführlichere Informationen enthalten, zuzuordnen.
Ein Beispiel für ein System zum Verarbeiten eines Bildes mit einem Strichcode wird in EP-A-0 449 634 gezeigt, daß das Bestimmen der Feinausrichtung eines Strichcodes durch Unterteilen der Bildfläche in vertikale Zellen 52, von denen einige einem Teil eines Strichcodeetiketts überlagert sein können, offenlegt. Für jede Abtastzeile innerhalb der Zelle wird ein der Graustufe der Bildelemente entlang dieser Abtastzeile in der Zelle entsprechendessignal erhalten (Figur 8c) sowie der Versatz zwischen den von unterschiedlichen Abtastzeilen erzeugten Signalen (Figur 8d). Eine Kreuzkorrelationsfunktion (Figur 9) der ersten Abtastzeile der Zelle mit jeder der aufeinanderfolgenden Abtastzeilen wird verwendet, um die Ausrichtung der Striche des Strichcodes bezüglich der Abtastzeilen zu bestimmen.
Bei dem steigenden Bedarf nach auf Informationen basierenden Technologien besteht beträchtliches Interesse an der Beseitigung der zugeordneten Datenbank und dem Speichern von mehr Dateninformationen in dem Strichcode selber. Bei der gegenwärtigen Technologie wird durch das Codieren zusätzlicher Informationen ein eindimensionaler Strichcode unrealistisch lang. Eine Anzahl zweidimensionaler Symboliken, entweder in Form eines gestapelten Strichcodes oder vom Matrixtyp, ist eingeführt worden, um diesen Bedarf zu berücksichtigen.
Ein zweidimensionales Symbol besteht aus einem zweidimensionalen Array von Elementen, die Informationszellen umfassen. Die Größe des Arrays bzw. die Größe eines Symbols wird dann durch die Codiervorgänge und die zu codierenden Informationen bestimmt. Die Zellen in dem Symbol weisen im allgemeinen eine polygonale Form auf und erscheinen entweder weiß oder schwarz. Ein Symbol basiert somit auf der geometrischen Form der Zellen und der Strukturen. Alle Elemente in einem Symbol, sowohl die weißen wie auch die schwarzen, weisen gleiche Größe und gleiche Form auf.
Die primäre Aufgabe bei der Verwendung einer zweidimensionalen Symbolik besteht darin, die zugeordnete Datenbank, wie sie bei Anwendungen mit Strichcodes Verwendung findet, zu beseitigen. Das Symbol wird somit zu einem tragbaren Informationsträger, der datenbankunabhängig ist. Das Merkmal, ein Informationsträger zu sein, ist besonders in den Industriezweigen Transport und Verteilung wichtig, in denen Briefe, Pakete, Behälter und andere entsprechende Artikel, die versandt oder transportiert werden, allgemein nach Ursprung, Flugnummer, Ziel, Name, Preis, Teilenummer und anderen Informationen identifiziert werden. Die Informationen werden in einem Etikett codiert, das entlang des Verteilungsweges gelesen wird. Andere Anwendungen für diese Etiketten sind beispielsweise die automatische Lenkung und Sortierung von Post, Paketen und Gepäck.
Eine der zweidimensionalen Symboliken, die öffentlich als Maxicode-Symbolik bekannt ist, ist in EP-A-0 573 129 in den US-Patenten Nr. 4,874,936 und 4,896,029 an Chandler et al. offengelegt. Das offengelegte Symbol ist ein Beispiel, bei dem die Zellen eine hexagonale Form und einen Durchmesser von etwa 30 tausendstel Zoll aufweisen. Um ein derartiges Symbol zu decodieren, muß an jedem Element die Rückstrahlstärke bestimmt werden. Um die Graustufenstärke jedes hexagonalen Elements richtig zu bestimmen, müssen zuerst die Position und Ausrichtung des Symbols gefunden und die Stelle der Mitte jedes Elements identifiziert werden.
In EP-A-0 573 129 wird eine allgemeine Methodik unter Verwendung einer Fourier-Transformation bei dem Decodierprozeß beschrieben. Das Prinzip besteht darin, ein im räumlichen Bereich dargestelltes Bild, das das Symbol enthält, in einen Spektralbereich umzuwandeln, wo die Strukturinformationen des Symbols für die spätere Bestimmung der Zellstärke gewonnen wird. Das in EP-A-0 573 129 beschriebene, auf einem Sechseck basierende Symbol ist eins, bei dem die eindeutige Struktur und Darstellung der codierenden Elemente in dem räumlichen Bereich ein Array aus sechs stark konzentrierten Energiepunkten in dem Spektralbereich bildet, die als die hellen Punkte bekannt sind. Sie sind gleichmäßig um 60 Grad voneinander beabstandet, wenn das ursprüngliche Etikett keine Verzerrung aufweist. Es folgt eine Suche, um die Position der primären Menge zu lokalisieren, um auf die Ausrichtung des Etiketts im räumlichen Bereich Rückschlüsse zu ziehen. Das offengelegte Verfahren wird im Feld als das Spektralbereichsverfahren bezeichnet. Von dem Verfahren ist aber auch durchaus bekannt, daß es auf Grund der Beteiligung der Fourier-Transformationsberechnungen eines der rechnerisch am aufwendigsten Verfahren ist. Für Echtzeitanwendungen muß teure Technik verwendet werden, um die erforderliche Verarbeitungsgeschwindigkeit zu erreichen. Dieses Verfahren ist bei automatischen Sortieranwendungen eingesetzt worden, bei denen hochliegende Lesegeräte eingesetzt werden. Bei derartigen Anwendungen sind die Kosten für die Rechnerhardware im Vergleich mit den Kosten der ganzen Sortiersysteme akzeptabel.
Abgesehen davon, daß es eine teure Umsetzung hinsichtlich Hardware erfordert, hat das Spektralverfahren in der Praxis andere Probleme gezeigt. So zum Beispiel können die verrauschten Informationen, wie beispielsweise die Graustufenschwankungen außerhalb des Symbols innerhalb des Bilds, ungünstig zu dem Spektrum beitragen und es ermöglichen, daß der Decodierprozeß versagt. Diese Graustufenschwankung kann durch gedruckte Zeichen, andere Zeichen, Schmutz oder Material mit ungleichmäßigem Reflexionsgrad um das Symbol herum verursacht werden. Bei vielen anderen Anwendungen wie zum Beispiel handgehaltenen Lesegeräten besteht ein großer Bedarf an kostenwirksamen Lesesystemen, ein Ziel, das schnelle Decodierung, aber viel weniger Hardware erfordert. Weiterhin besteht in der Technik ein Bedarf nach einem System mit verringerter rechnerischer Komplexität zum Decodieren von Symbolen, das gleichzeitig wirksamer und zuverlässiger ist. Außerdem besteht ein Bedarf an einem System, das das Symbol bei veränderlichem Abstand wirksam decodieren kann.
EP-A-0 573 129 legt auch ein Erfassungsziel offen, das aus mehreren konzentrischen Ringen mit kontrastierenden Reflexionsgraden gebildet wird, die bei linerarem Abtasten ein periodisches Videosignal ergeben. Ein Verfahren zum Auffinden des Erfassungsziels verwendet analoge Filtermittel, wobei das Signal direkt mit einer vorbestimmten Frequenz verglichen wird, was das Anpassen der Frequenzen gestattet. Ungeachtet dieses Verfahrens besteht in der Technik weiterhin ein Bedarf an einem System mit verringerter rechnerischer Komplexität zum Lokalisieren zweidimensionaler Erfassungsziele, das gleichzeitig wirksamer und zuverlässiger ist. Es besteht außerdem ein Bedarf an einem derartigen System, das ein Erfassungsziel unabhängig von seiner Größe wirksam lokalisieren kann.

KURZE DARSTELLUNG DER ERFINDUNG

Die vorliegende Erfindung ist unter Berücksichtigung der oben beschriebenen Probleme gemacht worden. Die vorliegende Erfindung stellt ein verbessertes System zum Bestimmen der Ausrichtung eines abgebildeten Symbols im räumlichen Bereich durch Berechnen des Korrelationskoeffizienten zwischen radial benachbarten Signalen und Lokalisieren jedes einzelnen informationsmäßig codierten Elements durch Verwendung mehrerer Segmente und Justieren, für jedes Segment, seiner Position und Elementgröße für die weitere Bestimmung der Stelle aller Elemente zum Decodieren bereit.
Allgemein beschrieben stellt die vorliegende Erfindung ein Verfahren zum Bearbeiten eines Bildes bereit, was folgendes einschließt: Entwickeln einer Abtastschablone mit einer Reihe von Punktepaaren, die entlang zweier paralleler Linien beabstandet sind, die geringen Abstand voneinander haben, wobei jedes Paar einen ersten Punkt aufweist, der auf einer der parallelen Linien gegenüber einem zweiten Punkt des Paares auf der anderen parallelen Linie positioniert ist; Positionieren der Schablone auf den Bilddaten; und Vergleichen von Graustufenstärken der ersten Punkte des Paares mit Graustufenstärken jeweiliger zweiter Punkte des Paares, um zwischen den ersten Punkten und den zweiten Punkten einen Korrelationsfaktor zu bestimmen; gekennzeichnet durch folgende Schritte: Bewegen der Abtastschablone in verschiedene Ausrichtungen bezüglich des Bildes und Bestimmen des Korrelationsfaktors für jede Position der Schablone; und Identifizieren von einer oder mehreren Mengen kollinearer Elemente in dem Bild durch Auffinden einer oder mehrerer Schablonenpositionen, die charakteristischen Werten des Korrelationsfaktors zugeordnet sind.
Die Erfindung betrifft auch ein Bildverarbeitungssystem, wie es in Anspruch 20 definiert ist.
Das Raumbereichsverfahren verläßt sich allein auf die Signalverarbeitung im räumlichen Bereich. Bei der Bestimmung der Ausrichtung beispielsweise eines abgebildeten Maxicode-Symbols dreht sich eine Schablone, die aus um 60 Grad beabstandeten Spindeln besteht, innerhalb eines 60-Grad-Bereichs um die Mitte des Symbols. Zwei parallele Signale entlang jeder Spindel werden bei einem wachsenden Winkel gewonnen, und ihr Korrelationskoeffizient wird berechnet. Eine gewisse Anzahl der Korrelationskoeffizienten mit den höchsten Werten erhalten Priorität, um die mögliche Ausrichtung des Symbols zu schätzen. Auf der Grundlage des geschätzten Ausrichtungswinkels werden in dem Symbol sechs Segmente bildende sechs Achsen definiert. Jede Achse sowie die Sechseckgröße entlang ihrer axialen Position kann fein justiert werden, um die genaue Ausrichtung und Sechseckgröße für jedes Segment unter Verwendung der Graustufenwerte der benachbarten Sechsecke entlang der Achse zu erhalten. Innerhalb jedes Segments wird dann unter Verwendung der justierten Parameter die Mitte jedes Sechsecks aus der bekannten Geometrie des Symbols lokalisiert. Eine das Symbol darstellende Tabelle wird erhalten, indem der Graustufenwert des die Mitte jedes Sechsecks darstellenden Bildelements identifiziert wird.
Wie aus der folgenden Beschreibung deutlich wird, beginnen alle Signalverarbeitungsvorgänge in der Mitte des Symbols. Daraus resultiert der Widerstand der vorliegenden Erfindung gegenüber Störung von unerwünschten Signalen, wie beispielsweise gedruckten Zeichen, Grafiken oder Schmutz um das Symbol herum. Die Wirksamkeit der Verarbeitungsvorgänge bei der vorliegenden Erfindung ist verständlich, da lediglich ein Teil eines das Symbol enthaltenden Signals verarbeitet wird.
Bei einer bevorzugten Ausführungsform wird ein zweidimensionales Erfassungsziel lokalisiert durch Auffinden seines Schlüsselements, eines geometrisch symmetrischen, begrenzten Elements eines ersten Reflexionsgrades, das von einem geometrisch symmetrischen Grenzbereich mit einem zweiten Reflexionsgrad umgeben ist. Das Schlüsselelement wird lokalisiert durch Abtasten des gespeicherten Bildes entlang einer ersten Abtastrichtung, Erfassen eines in Frage kommenden begrenzten Elements und zugeordneten Grenzbereichs, die entlang der ersten Abtastrichtung Symmetrie zeigen, und Bestimmen, ob das in Frage kommende begrenzte Element und der zugeordnete Grenzbereich entlang einer von der ersten Richtung verschiedenen zweiten Richtung symmetrisch sind. Der Vorteil bei der Verwendung von Symmetrieprüfungen besteht darin, daß sie gegenüber Verzerrung des Bildes des Erfassungsziels aufgrund eines Neigungswinkels zwischen dem Ziel und dem Erkennungsmechanismus invariant sind, da die Symmetrieeigenschaft des Erfassungsziels in dem verzerrten Bild beibehalten wird. Das System und das Verfahren beinhalten vorzugsweise auch das Bestimmen von Durchmessern des in Frage kommenden begrenzten Elements und seines zugeordneten Grenzbereichs in jeder der Richtungen, in der sie Symmetrie zeigen; und Bestimmen, ob die Durchmesser innerhalb einer vorbestimmten Toleranz voneinander liegen. Der Schritt des Erfassens von Symmetrie entlang der Abtastrichtung umfaßt vorzugsweise auch eine Lauflängencodierung der Zeilen des Bildes und Untersuchung der Läufe auf Symmetrie.
Die vorliegende. Erfindung strebt deshalb an, eine Lösung bereitzustellen, um eine oder mehrere Mengen kollinearer Elemente in einem Bild zu identifizieren.
Weitere Aufgaben, Merkmale und Vorteile der vorliegenden Erfindung gehen aus einer Untersuchung der nachfolgenden Beschreibung der bevorzugten Ausführungsform der Erfindung im Zusammenhang mit den beiliegenden Zeichnungen und den angefügten Ansprüchen hervor.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Figur 1 ist eine Draufsicht auf ein zweidimensionales Symbol mit angezeigten sechs Achsen.
Figur 2 zeigt das Systemflußdiagramm, das die Decodierung des Symbols im räumlichen Bereich umreißt.
Figur 3 ist ein Systemblockschaltbild zur Bilderzeugung eines zweidimensionalen Erfassungsziels bzw. Symbols, bei dem der Prozessor gemäß der vorliegenden Erfindung konfiguriert ist.
Figur 4 zeigt die Achsen, mit denen die Symmetriemerkmale des Erfassungsziels bei der bevorzugten Ausführungsform der Erfindung geprüft werden.
Figuren 5A und 5B zeigen ein Systemflußdiagramm, das die Schritte der Technik zum Lokalisieren eines Erfassungsziels umreißt.
Figur 6 zeigt schematisch einen Vorgang der Feinabstimmung zum Bestimmen der Mitte eines Schlüsselelements.
Figur 7 ist eine Draufsicht auf das Symbol mit einer willkürlichen Ausrichtung innerhalb eines Bildrahmens.
Figur 8 zeigt ein Verfahren zum Wählen der vier Schwellwerte aus einem Histogramm.
Figur 9 ist eine Draufsicht auf den Bereich innerhalb des Symbols, der zum Erzeugen des Histogramms verwendet wird.
Figur 10 ist eine Draufsicht auf die zum Erzeugen des eindimensionalen Ausrichtungssignals bei der bevorzugten Ausführungsform der Erfindung entworf ene Schablone.
Figur 11 ist eine Draufsicht auf ein Maxicode- Symbol willkürlicher Ausrichtung mit achtzehn Synchron-Sechsecken, die angezeigt sind, und bezeichneten sechs Achspaaren.
Figur 12A ist eine graphische Darstellung eines eindimensionalen Ausrichtungssignals.
Figur 12B ist eine graphische Darstellung des eindimensionalen Ausrichtungssignals von Figur 12A nach Filterung.
Figur 13A zeigt eine Auswahl von verwendeten Versuchsstrahlen, und Figuren 138, 13C und 13D zeigen schematisch die Ergebnisse korrekter Bestimmung der Achsrichtung und der Größe der Sechsecke entlang der Achse, der inkorrekten Bestimmung der Sechseckgröße bzw. der inkorrekten Bestimmung der Achsrichtung.
Figur 14 zeigt ein Flußdiagramm, das die Bestimmung des richtigen Paars von Versuchsparametern bei der Feinjustierung der Maxicode-Symbolachsen umreißt.
Figuren 15A und 15B sind schematische Ansichten von Clustern von benachbarten Rechtecken, die Bildpunkte darstellen, deren Farben durch W (weiß) und B (schwarz = black) markiert sind, wobei mit den Clustern bestimmt wird, ob ein Bildelement die Mitte eines Sechsecks ist.
Figur 16 ist eine Draufsicht auf den Vorgang des Lokalisierens der Mitte jedes einzelnen Sechsecks des Symbols.

AUSFUHRLICHE BESCHREIBUNG DER ERFINDUNG

Nunmehr unter Bezugnahme auf die Zeichnungen, in denen gleiche Bezugszeichen sich auf gleiche Teile in den verschiedenen Ansichten beziehen, zeigt Figur 1 ein als Maxicode bekanntes zweidimensionales Symbol 10 nach dem Stand der Technik, das auf einem Etikett, Paket oder dergleichen positioniert sein kann. Die Maxicode-Symbolik enthält eine Matrix aus sechseckigen informationscodierenden Elementen 12, die in einem Quadrat angeordnet sind, und in ihrer Mitte ein Erfassungsziel 100, das aus sechs konzentrischen Ringen mit abwechselnd hellem und dunklem Reflexionsgrad besteht. Figur 2 ist ein Flußdiagramm, das den Gesamtprozeß der vorliegenden Erfindung zeigt, um ein Bild des Symbols zu erhalten, das Scheibenzentrum seines Erfassungsziels zu erkennen, die Größe von Sechsecken zu schätzen, Schwellwerte zur Unterscheidung schwarzer Sechsecke von weißen Sechsecken zu bestimmen, die Ausrichtung von innerhalb des Maxicode-Symbols enthaltenen Symbolachsen zu bestimmen, Werte für Achsrichtung und Sechseckgröße fein abzustimmen und die Mitten einzelner Sechsecke zum Decodieren der innerhalb des Symbols enthaltenen Informationen zu lokalisieren. Auf dieses Gesamtflußdiagramm wird Bezug genommen werden, wenn die Unterkomponenten des Prozesses ausführlich beschrieben werden.

Lesegerät

Unter Bezugnahme auf Figur 3 werden die Bauelemente eines Erkennungsmechanismus 20 schematisch gezeigt. Der Erkennungsmechanismus 20 hat den Zweck, ein Bild von Angaben auf einer Oberfläche wie beispielsweise einem Etikett 14 zu erfassen. Dieser Mechanismus führt die Schritte 202, 204 und 206 aus, wie in Figur 2 gezeigt. Der Erkennungsmechanismus 20 enthält eine CCD-Videokamera 30 (CCD = charge-coupled device), wie beispielsweise eine Pulnix 7-CN, hergestellt von Pulnix America, Inc. in Sunnyvale, Kalifornien 94086. Das Ziel wird von einer Lichtquelle wie beispielsweise einer oder mehreren LEDs 22 beleuchtet, und das reflektierte Licht vom Symbol 10 auf dem Etikett 14 wird von einer Optik 24 auf den Detektor der Kamera 30 fokussiert. Eine derartige Kamera enthält eine Matrix aus Bildelementen, die durch Liefern eines Ausgangssignals, das zu der auf das Bildelement fallenden Menge an Licht in Beziehung steht, ein Bild bildet. Diese Ausgangssignale werden herkömmlicherweise zu einem Analog-Digital-Umsetzer 32 ausgelesen, um ein Array aus Bilddaten zu erzeugen, die beispielsweise im Bereich von 0 (Schwarz) bis 255 (Weiß) liegen können, und um derartige Daten, gesteuert von einem Mikroprozessor 36, in einem Rechnerspeicher 34 zu speichern. Der Prozeß, derartige Bilddaten im Rechnerspeicher zu erhalten, wird in den US-Patenten Nr. 4,874,936 und 4,896,029 beschrieben.
Die vorliegende Erfindung wird vorzugsweise von der Software her in der Sprache C umgesetzt, die auf einem Personal Computer wie beispielsweise einem Compaq Deskpro 50M mit einer Bildfangkarte darin läuft. Die Bildfangkarte liefert eine Schnittstelle zwischen der CCD-Kamera und dem Rechner. Bei der bei der vorliegenden Erfindung verwendeten Bildfangkarte handelt es sich um einen von Dipix Technologies of Canada vermarkteten Powergrabber. Der Prozessor 36 im Rechner kann von einem Durchschnittsfachmann programmiert werden, um die folgenden Operationen an den in dem Speicher 34 gespeicherten Bilddaten durchzuführen. Außerdem ist zu verstehen, daß die Funktionen der Erfindung in festverdrahteten Logikschaltungen oder in anwendungsspezifischen integrierten Schaltungen (ASIC = application specific integrated circuit) umgesetzt werden kann.
Um auf ein beliebiges Bildelement in dem Rechnerspeicher 34 zuzugreifen, werden zwei Parameter, wobei x die Spalte und y die Zeile darstellen, das heißt die Koordinaten (x, y), als Adresse für ein Bildelement verwendet. Das digitalisierte Videosignal kann aus diesem Grund als zweidimensionales Bild betrachtet werden. Die x-Achse, wie in Figur 1 gezeigt, verläuft parallel zu den Zeilen von Bildelementen des CCD-Detektors der Kamera, aber die Kamera kann das Symbol 10 unter jedem beliebigen Winkel relativ zu der x-Achse erfassen. Die Kamera kann auch relativ zu der Ebene des Symbols gekippt sein, was zu einer gewissen Verzerrung des Bildes führt.

Erkennung des Erfassungsziels

Von den sechs Ringen, die das Maxicode- Erfassungsziel umfassen, sind drei Ringe dunkel Ringe 101, 103 und 105, und drei Ringe sind helle Ringe 102, 104 und 106, wie in Figur 4 gezeigt. Der innere helle Kern 102 wird als einer der drei hellen konzentrischen Ringe betrachtet. Der innere Kern 102 bildet ein Schlüsselelement, und die anderen Ringe liefern Randelemente, mit denen allen das Ziel auf eine unten beschriebene Weise lokalisiert werden kann.
In dem gespeicherten mehrzeiligen Bild von Symbol weisen die hellen Ringe darstellende Daten aufgrund des hohen Reflexionsgrades der hellen Ringe hohe Zahlenwerte auf, und diejenigen Daten, die die dunklen Ringe darstellen, weisen aufgrund des niedrigen Reflexionsgrades der dunklen Ringe niedrige Zahlenwerte auf.
Gemäß der vorliegenden Ausführungsform erfolgt das Lokalisieren eines Erfassungsziels nicht durch Abstimmen einer synthetischen Schablone. Vielmehr wird der (in Schritt 208 von Figur 2 dargestellte) Lokahsierungsprozeß innerhalb der Bilddaten selber durch Verwendung der Symmetrieeigenschaft des Erfassungsziels ausgeführt. Figur 4 zeigt das gleiche Erfassungsziel 100 m{t vier durch Winkel von 45 Grad getrennten Achsen. Eine Achse 300 weist nach Osten bzw. in horizontaler Richtung, eine Achse 302 weist nach Norden bzw. in vertikaler Richtung, und Achsen 304 und 306 weisen nach Nordost bzw. Nordwest. Achse 300 ist diegleiche wie die in Figur 1 gezeigte x-Achse und wird dadurch definiert, daß sie parallel zu den Zeilen von Bildelementen verläuft. Bei der gezeigten bevorzugten Ausführungsform ist das Erfassungsziel zu einer beliebigen dieser Achsen symmetrisch. Die Symmetrie ist tatsächlich aber nicht auf diese Achsen in dem bevorzugten Erfassungsziel beschränkt, dessen konzentrische kreisförmige Ringe in allen Richtungen symmetrisch sind. Wenn im vorliegenden Text auf Richtung Bezug genommen wird wie beispielsweise "Nord" oder "vertikal", so soll damit lediglich ein relativer Bezugsrahmen gebildet werden.
Nunmehr unter Bezugnahme auf Figuren 5A und 5B wird der Prozeß von Schritt 208 von Figur 2 zum Lokalisieren der Mitte des Erfassungsziels schematisch und ausführlicher unter Bezugnahme auf entsprechende Verarbeitungsvorrichtungen gezeigt. Außerdem wird der Durchmesser des Ziels gewonnen, um Informationen für eine mögliche Schätzung der Bildauflösung zu liefern.
Im Block 254 wird eine Startzeilenzahl im Bild gewählt. Auf diese Weise wird eine Zeile von Bildelementwerten adressiert. Ein Schwellwert zum Unterscheiden weißer Bildelemente von schwarzen Bildelementen wird aus der Menge von Werten für die aktuelle Zeile bestimmt. Mit dem Schwellwert werden Ubergänge zwischen schwarzen und weißen Gebieten des gespeicherten Bilds aufgefunden. Es existieren viele Verfahren zum Bestimmen des Schwellwerts, die dem Fachmann bekannt sind, wie z.B. das in US- Patent Nr. 4,874,936 beschriebene Histogrammverfahren. Vorzugsweise wird als Schwellwert ein Mittelwert gewählt, der als 1/2 (Pmax + Pmin) berechnet ist, wobei Pmax und Pmin der kleinste und größte Bildelementwert in der aktuellen Zeile sind. Alternativ dazu kann für das gesamte Bild ein Schwellwert auf die gleiche Weise berechnet werden, für den Prozeß des Lokalisierens der Mitte des Erfassungsziels wird aber bevorzugt, für jede Zeile einen eigenen Schwellwert zu bilden. Ein anderes Verfahren zum Bestimmen des Schwellwerts wird unten im Zusammenhang mit der Bestimmung der Ausrichtung des Symbols offengelegt.
Auf der Grundlage des kalkulierten Schwellwerts können die Daten lauflängencodiert werden. Folgendes ist ein Beispiel:
Diejenigen Bildelementwerte unter dem Schwellwert sind mit dem Buchstaben B (d.h. Black = Schwarz) gekennzeichnet, und diejenigen über dem Schwellwert sind mit dem Buchstaben W (d.h. Weiß) gekennzeichnet. Die entsprechende lauf längencodierte Sequenz ist:
78355454.
Der Zahlenwert, der angibt, wie oft der gleiche Buchstabe in der unmittelbaren Gruppe zusammenhängend auftritt, wird als ein "Lauf" bezeichnet. Die Gesamtanzahl an Läufen in dem Beispiel beträgt 8. Es ist zu beachten, daß die Codierung immer mit dem ersten schwarzen Bildelement in der Abtastrichtung begonnen wird. Wenn somit die codierte Sequenz mit 1, 2, 3, ... indexiert wird, dann stehen die durch gerade Zahlen indexierten Läufe für weiße Läufe.
Um numerisch die Möglichkeit zu erfassen, daß eine durch die Mitte des Erfassungsziels gehende Zeile aktuell codiert worden ist, wird die Anzahl an Läufen mit der Anzahl an Ringen bei Block 255 verglichen. Entlang der Achse 300 des Ziels 100, die die fünf benachbarten Ringe 101, 103, 104, 105, 106 zweimal durchquert und den mittleren Ring 102 einmal, befinden sich mindestens 12 übergänge "W zu B" oder "B zu W". Fur eine durch den mittleren weißen Ring 102 des gegebenen Ziels 100 verlau fende Zeile muß die Anzahl an Läufen deshalb größer als 13 sein. Wenn die Anzahl an Läufen unter einer vorbestimmten Zahl (vorzugsweise 13) liegt, braucht das Ziel 100 entlang dieser Zeile nicht weiter hinsichtlich Symmetrie geprüft zu werden. In diesem Fall schreitet das Progamm zu Block 259 weiter und prüft, um zu bestimmen, ob die aktuelle Zeile die letzte Zeile im Bild ist. Falls ja, wird im Block 261 eine Nachricht erzeugt, daß in dem Bild kein Ziel gefunden wurde. Wenn nein, kehrt das Programm zu Block 254 zurück, um die nächste Zeile zu untersuchen. Es versteht sich, daß die vordefinierte kleinste Anzahl von Läufen von der Anzahl kozizentrischer Ringe abhängt, die das Ziel ausmachen.
Wenn die Anzahl an Läufen größer ist als die vordefinierte Anzahl, untersucht das Programm abwechselnd jeden weißen Lauf in der aktuellen Zeile. Aufgrund des Musters dieses Erfassungsziels können die ersten beiden weißen Läufe und die letzten beiden weißen Läufe nicht der mittlere weiße Lauf sein. Die Suche kann somit auf die weißen Läufe begrenzt werden, die jeweils um eine gewisse Zahl (z.B. 2) zu dem ersten und letzten weißen Lauf der codierten Sequenz versetzt sind. Bei Block 256 sind wird der erste weiße Lauf gewählt. Bei Block 258 wird der Lauf geprüft, um zu bestimmen, ob er bereits am Ende der aktuellen Zeile ist. Falls ja, so schreitet das Programm für die oben beschriebene Prüfung zu Block 259 weiter. Falls nein, prüft das Programm bei Blöcken 262 und 264, um zu bestimmen, ob der weiße Lauf den inneren Ring 102 darstellt. Bei einem Bild fester Größe kann das Erfassungsziel nicht willkürlich groß sein. Eine gewisse größte Länge (z.B. 6 Bildelemente) kann der Länge des inneren weißen Laufs auferlegt werden, um den Lokalisierungsprozeß zu beschleunigen. Wenn der weiße Lauf bei Prüfung bei Block 262 länger als dieser Toleranzwert ist, dann ist es nicht erforderlich, diesen Lauf auf Symmetrie hin zu prüfen, und das Programm kehrt zu Block 256 zurück. Wenn das Prüfungsergebnis zeigt, daß der weiße Lauf innerhalb des Toleranzwerts liegt, wird bei Block 264 eine weitere Prüfung durchgeführt, um den weißen Lauf mit den vorausgegangenen beiden weißen Läufen und den folgenden beiden weißen Läufen zu vergleichen. Es ist zu beachten, daß, wenn die drei hellen Ringe nach Auslegung die gleiche Breite aufweisen, wie dies bei dem in Figur 4 gezeigten bevorzugten Ziel der Fall ist, die Breite ihrer entsprechenden Läufe sich möglicherweise als Ergebnis des Schwellwertbildungsprozesses oder unzureichender Bildauflösung voneinander um ein oder höchstens zwei Bildelemente unterscheidet.
Es existieren unterschiedliche Wege, um die Ähnlichkeit zwischen dem aktuellen weißen Lauf und den benachbarten weißen Läufen zu vergleichen. Bei der bevorzugten Ausführungsform besteht eine Ähnlichkeitsprüfung darin, ob der mittlere weiße Lauf plus ein Bildelement mindestens so lang ist wie jeder seiner vier benachbarten weißen Läufe. Es sollte klar sein, daß diese Prüfung für irgendwelche Schwankung beim Schwellwert für schwarze oder weiße Bildelemente nicht empfindlich ist (d.h., die Wahl des Schwellwerts ist nicht kritisch). Wenn der mittlere weiße Lauf plus ein Bildelement kürzer ist als irgendeine seiner vier benachbarten weißen Läufe, dann kann er nicht der Repräsentant des inneren Rings 102 sein, und das Programm kehrt zu Block 256 zurück.
Wenn der aktuelle Lauf der Prüfung des Blocks 264 genügt, wird bei Block 268 die folgende Symmetrieprüfung bei einem gegebenen Erfassungsziel 100, das aus 6 konzentrischen, ursprünglich mit etwa gleicher Breite gedruckten Ringen gebildet wird, durchgeführt:
(1) Es sei 1 die Länge des aktuellen weißen Laufs. Es seien w&sub1;, w&sub2;, w&sub3;, w&sub4; die beiden vorausgegangenen und die beiden folgenden weißen Läufe, und es seien b&sub1;&sub1; h&sub2;, h&sub3;, b&sub4; die beiden vorausgegangenen und die beiden folgenden schwarzen Läufe, jeweils der aktuellen Zeile. Die durchschnittlichen Längen von weißen Läufen und schwarzen Läufen werden mit w bzw. b bezeichnet. Dann gilt
w=w&sub1;+w&sub2;+w&sub3;+w&sub4;/4;und
b=b&sub1;+b&sub2;+b&sub3;+b&sub4;/4.
Die Symmetrieprüfung ist erfüllt, wenn die beiden folgenden Bedingungen erfüllt sind:
b-w < 2
wj-w < 2und bj-b < 2 für j=1,2,3,4
wobei 2 die Toleranz darstellt (2 Bildelemente), die für Schwankungen beim Toner des Etikettendruckers und einen ungenauen Bildschwellwertpegel zugelassen ist. Man beachte, daß der äußere dunkle Ring 105 bei der Prüfung nicht verwendet wird, da seine Breite möglicherweise manchmal von ihm benachbarten verrauschten Komponenten (z.B. dunkle Symbolkomponenten - im Fall der Maxicode- Symbolik Sechsecke) beeinflußt werden kann. Wenn die vorausgegangene erste Symmetrieprüfung nicht bestanden wird, kehrt das Programm zu Block 256 zurück. Nach dem Bestehen der Symmetrieprüfung entlang der Achse 300 wird bei Block 272 eine in Frage kommende Mittenkoordinate (x&sub1;, y&sub1;) des Erfassungsziels festgelegt, und der geschätzte Durchmesser des gesamten Ziels entlang der Achse 300 (immer noch unter Ausschluß des äußeren dunklen Rings 105) wird wie folgt geschätzt:
Auf der Grundlage der in Frage kommenden Mitte (x&sub1;, y&sub1;) werden bei Blöcken 274 bis 282 weitere Symmetrieprüfungen durchgeführt, um zu verifizieren, daß die Koordinaten (x&sub1;, y&sub1;) innerhalb der Mitte des Erfassungsziels liegen. Eine neue Richtung zur Symmetrieprüfung wird bei Block 274 gewählt. Ausgehend vom Bildelement (x&sub1;, y&sub1;) und unter Einsatz des gleichen Schwellwerts, wie er in der aktuellen horizontalen Richtung verwendet wird, wird entlang der Achse 304 eine Lauflängencodierung sowohl nach unten als auch nach oben durchgeführt, bis in jeder Richtung insgesamt fünf übergänge "W zu B" oder "B zu W" erhalten werden. Dies führt zu vier weißen Läufen und vier schwarzen Läufen, deren Mitte bei dem weißen Lauf der in Frage kommenden Mitte liegt. Die vorausgegangene Symmetrieprüfung wird auf diese Läufe bei Block 276 angewendet, und der Durchmesser des Erfassungsziels entlang dieser Achse wird bei Block 278 berechnet und gespeichert.
Der Fachmann versteht, daß dieser diagonale Durchmesser entlang der Achse 304, nämlich die Anzahl von Bildelementen multipliziert mit einem Faktor von 2, in enger Beziehung zu dem einen zuvor entlang der Achse 300 berechneten stehen sollte. Die Differenz zwischen diesen beiden Durchmessern ist direkt proportional zu dem Neigungswinkel, der die Bildverzerrung hervorruft. Gemäß dem bei dem Bilderzeugungsprozeß zugelassenen maximalen Neigungswinkel kann ein Toleranzwert festgelegt werden. Eine Toleranz von 4 Bildelementen beispielsweise funktioniert für einen Neigungswinkel bis zu 30 Grad. Wenn bei Prüfung bei Block 280 die Differenz größer ist als die gewählte Toleranz, dann wird die vermutete Mitte (x&sub1; y&sub1;) verworfen, und das Programm kehrt zu Block 256 zurück, um einen neuen Lauf zu adressieren und schließlich, falls erforderlich, eine neue Zeile von Daten zur Lauflängencodierung, um die oben beschriebenen Prüfungen zu wiederholen. Andernfalls kehrt das Programm zu Block 274 zurück und die Symmetrieprüfung und die Durchmesserkontrolle werden entlang der Achsen 306 bzw. 302 fortgeführt. Wenn schließlich die vertikal codierten Daten entlang Achse 302, die durch die in Frage kommende Mitte (x&sub1;, y&sub1;) verläuft, die Symmetrieprüfung und die Durchmesserkontrolle bestehen, wird bei Block 284 die vermutete Mitte (x&sub1;, y&sub1;) bestätigt. Bei der gezeigten Ausführungsform wird jedes Scheitern das Programm zu Block 256 zurückführen. Um allerdings in dem Bild des Erfassungsziels Verzerrung oder Fehistellen zu berücksichtigen, kann ein Scheitern gestattet werden, bevor aus dem in Frage kommenden Lauf ausgestiegen wird. Beispielsweise kann ein Scheitern entlang einer der diagonalen Achsen toleriert werden, wenn die andere diagonale Achse und die vertikale Achse die Symmetrieund Durchmesserprüfungen bestehen.
Der Fachmann versteht, daß die in Frage kommende Mitte (x&sub1;, y&sub1;) nun innerhalb des inneren hellen Rings 102 liegen muß, doch befindet sie sich möglicherweise nicht in der wahren Mitte des Erfassungsziels. Auf der Grundlage der Startkoordinaten (x&sub1;, y&sub1;) wird bei Blöcken 286 und 288 eine Feinabstimmungsprozedur durchgeführt. Figur 6 zeigt schematisch die Abstimmungsprozedur. Die Koordinaten (x&sub1;, y&sub1;) liegen innerhalb des inneren Rings 102 und vermutlich bei Bildelement 402. Bei gegebenem y&sub1; wird ein Abstimmfenster definiert. Die Größe des Fensters ist durch die Größe des inneren weißen Rings 102 definiert. Die Längen von mindestens 2 Zeilen von Daten (die Länge des weißen Laufs) innerhalb des inneren Rings 102 unmittelbar über und unter y&sub1; werden gezählt, wie beispielsweise Zeile y&sub0;, y&sub2; und y&sub3;. Es werden dann Zahlenwerte, die die entsprechenden Längen darstellen, gewonnen, beispielsweise die Länge von Zeile y&sub0; kann 5 Bildelemente betragen, und die Länge von Zeile Y&sub2; kann 7 Bildelemente betragen. Die neue vertikale Koordinate wird in der längsten Zeile gewählt, d.h. in der Zeile, die die größte Breite des inneren Rings 102 mißt. Auf diese Weise wird eine neue in Frage kommende Mitte 404 festgelegt (die bei dem gezeigten Beispiel bei Koordinaten (x&sub1;, y&sub2;) liegt).
Auf der Grundlage der Koordinaten (x&sub1;, y&sub2;) wird dann wieder die gleiche Art von Messung entlang der Spalten durchgeführt, um die längste Spalte innerhalb des inneren Rings 102 zu finden (was sich bei dem in Figur 6 gezeigten Beispiel als x&sub2; herausstellt). Der Schnittpunkt der längsten Zeile und der längsten Spalte bei Koordinaten (x&sub2;&sub1; y&sub2;) ergibt die endgültigen bzw. wahren Mittenkoordinaten des Erfassungsziels.
Wenn zwei oder mehr Spalten- oder Zeilenlängenwerte vorliegen, die zufälligerweise gleich sind, werden bei Block 288 von Figur 5 die Bildelementstärkewerte für jede der gleichen Zeilen oder Spalten akkumuliert. Die endy;iltige Mittenkoordinate wird in einem derartigen Fall so gewählt, daß sie in der Zeile oder Spalte mit dem größten summierten Stärkewert liegt.
Zwischen der gesamten Maxicode-Symbolik, den Ringen des Erfassungsziels und den einzelnen Sechsecken besteht ein festgelegtes Größenverhältnis. Es ist aus diesem Grund verständlich, daß bei Bestimmung einer Schätzung der Größe des Erfassungsziels wie oben beschrieben die durchschnittliche Größe der einzelnen Sechsecke im Bild berechnet werden kann. Dies kann als der durchschnittliche Sechseckdurchmesser ausgedrückt werden, bei dem es sich um den Abstand zwischen entgegengesetzten flachen Seiten eines Sechsecks handelt. Bei der Maxicode-Symbolik, wo die Sechsecke zusammengepackt sind, ist der Sechseckdurchmesser gleich dem Abstand zwischen den Mitten benachbarter Sechsecke. Wenn in der folgenden Beschreibung auf die Sechseckgröße Bezug genommen wird, kann somit darunter auch die Sechseckbeabstandung verstanden werden. Dies würde nicht unbedingt auch für alle zweidimensionalen Symboliken gelten.

Eigenschaften der Maxicode-Svmbolik und des CCD-Bildes

Wie oben erwähnt enthält das in Figur 1 gezeigte Symbol 10 eine Matrix aus sechseckigen informationscodierenden Elementen 12, die in einem Quadrat angeordnet sind, und in seiner Mitte das Scheibenzentrum 100, das aus sechs konzentrischen Ringen mit abwechselndem dunklen und hellen Reflexionsgrad besteht. Die Struktur der gepackten sechseckigen Elemente bzw. Zellen diktiert eine bestimmte Beziehung der Zellen zu der Mitte. Figur 7 zeigt schematisch ein Maxicode-Symbol. Wie gezeigt gehen durch die Mitte des Scheibenzentrums nur sechs Symbolachsen 0, 1, 2, 3, 4, 5, die zu einer Menge von Sechsecken, deren Mitten kollinear sind, ausgerichtet sind. Jede Symbolachse muß um 60 Grad beabstandet sein. Der Fachmann versteht, daß die folgenden Techniken zur Verwendung mit zweidimensionalen Symboliken mit mehr oder weniger als sechs derartiger Achsen modifiziert werden können. Beispielsweise würde eine Matrix aus in Zeilen und Spalten angeordneten quadratischen Elementen acht Achsen aufweisen, die sich von einer bezeichneten Mitte der Symbolik durch Mengen von Quadraten, deren Mitten kollinear sind, radial erstrecken. Derartige Achsen würden um 45 Grad auseinanderliegen. Die Ausrichtung der Symbolik könnte unter Verwendung von lediglich vier dieser Achsen bestimmt werden, da der Unterschied bei der Elementbeabstandung zwischen quadratischen Elementen, die sich mit ihren Seiten berühren, und anderen, die sich an ihren Ecken berühren, berücksichtigt werden müßte, um alle acht Achsen zu finden.
Weiterhin sind um das Scheibenzentrum herum sechs Mengen eindeutiger Kombinationen aus hellen und dunklen Sechsecken 16 beabstandet, wobei jede Menge drei Sechsecke umfaßt, wie in Figur 7 deutlicher gezeigt. Diese achtzehn Sechsecke werden als Synchron-Sechsecke bezeichnet. In jeder Menge von Synchron-Sechsecken liegen zwei der drei Synchron-Sechsecke auf einer der sechs Symbolachsen nebeneinander. Die Synchron-Sechsecke im Symbol sind somit eindeutig positioniert, 60 daß jede der sechs Symbolachsen durch zwei Synchron-Sechsecke in einer Zeile in jeder Menge laufen muß. Das Muster der sechs Mengen von Synchron-Sechsecken verändert sich nicht mit den im Symbol codierten Informationen. Wie aus einer weiteren Beschreibung der vorliegenden Erfindung zu verstehen sein wird, wird diese eingebettete Struktur verwendet, um die Etikettausrichtung eindeutig zu bestimmen und die Position jeder Symbolachse zu justieren.
Wie oben erwähnt werden die Koordinaten (x, y) als Adresse für ein Bildelement verwendet. Die x-Achse, wie in Figur 7 gezeigt, liegt horizontal (parallel zu den Zeilen von Bildelementen), und die y-Achse liegt vertikal (parallel zu den Spalten von Bildelementen). Der Anfangspunkt des Koordinatensystems liegt in der Mitte des Scheibenzentrums, die auch die Mitte des Bildes ist. Winkel im Koordinatensystem werden von der x-Achse aus im Uhrzeigersinn gemessen. Somit ist in Figur 7 ein Hauptwinkel 54 definiert, der den Winkel zwischen der Symbolachse 0 und der horizontalen Achse x darstellt. Der Hauptwinkel definiert die wahre Ausrichtung des Symbols in einem Bild. Wenn beispielsweise der Hauptwinkel einen Wert von 180 Grad aufweist, so bedeutet dies, daß das abgebildete Symbol im Bild ohne Drehung positioniert ist; alle anderen Werte bedeuten, daß das abgebildete Symbol im Bild gedreht worden ist. Unter den Symbolachsen 0, 1, 2, 3, 4, 5 existiert immer eine und nur eine Symbolachse, die einen Winkel von der x-Achse unterstützt, der zwischen 0 und weniger als 60 Grad liegen muß. Dieser Winkel wird als der Ausrichtungswinkel 56 bezeichnet.

Wählen eines Bildbereichs zur Bestimmung der Ausrichtung des Symbols

Auf der Grundlage der Mitte des Scheibenzentrums, nach Bestimmung unter Verwendung des obigen Verfahrens, kann aus dem in dem Rechnerspeicher gespeicherten ursprünglichen Bild ein kleinerer quadratischer Bildrahmen 50 fester Größe, der das Maxicode-Symbol enthält, gewonnen werden. Dies wird schematisch in Figur 7 dargestellt. Die Mitte des Maxicode-Symbols liegt nun in der Mitte des kleineren Bildes.
Bei einer typischen Anwendung kann die Größe des kleineren Bildes 50 aus den folgenden Gründen so gewählt werden, daß sie 128 Bildelemente mal 128 Bildelemente beträgt. Die Größe des oben beschriebenen Maxicode- Symbols beträgt bei typischem Druck ein Zoll im Quadrat. Bei Verwendung einer CCD- Kamera wie oben beschrieben, die in einem zweckmäßigen Abstand von einem das Symbol enthaltenden Etikett eingesetzt wird, liegt die Auflösung des Bildes in der Regel bei etwa 90 Punkten pro Zoll (dpi), das heißt die Darstellung eines einen Zoll langen Randes des Symbols im Bild ist 90 Bildelemente lang. Das Maxicode-Symbol paßt deshalb üblicherweise in einen 128 Bildelemente mal 128 Bildelemente großen quadratischen Bereich des Bildes, unabhängig von der Ausrichtung des Symbols. Es ist anzumerken, daß die Auflösung je nach dem Abstand zwischen dem Etikett und der Kamera variieren kann. In der Praxis hat sich gezeigt, daß die Auflösung zwischen etwa 70 und etwa 130 dpi variiert.

Bestimmen von Schwellwertpegeln zur Verwendung beim Auffinden der Ausrichtung des Symbols

Nunmehr unter Bezugnahme auf Schritt 210 von Figur 2 und ausführlicher auf Figuren 8 und 9 wird ein Verfahren zum Bestimmen zweier, bei der Erfindung verwendeter Schwellwertpegel gezeigt. Zunächst wird aus einem Teil des Bildes, das als Teilbild 51 bezeichnet wird und dessen Mitte beim Scheibenzentrum 100 liegt, ein Histo gramm erzeugt. Zum Erzeugen des Histogramms wird ein kleines Teilbildgebiet gewählt, um die Möglichkeit des Schrägverzerrens des Histogramms durch die Einbeziehung weißer Bereiche des Bildes außerhalb des Symbols zu vermeiden. Figur 9 zeigt, daß das Teilbild 51 als das größte quadratische Bild innerhalb des Symbols 10 einer gegebenen Größe gewählt ist. Bei dem oben erörterten kleineren Vollbild 50 mit einer Größe von 128 mal 128 Bildelementen wird bei der Auflösung des Maxicode-Symbols mit 90 dpi die Größe des Teilbildes 51 als 90/ 2 berechnet, was etwa 64 mal 64 Bildelemente ist. Dann wird ein Histogramm wie in Figur 8 gezeigt aufgetragen, das die Anzahl von Bildelementen innerhalb des Teilbildes 51 zeigt, die jeden der möglichen Graustufenstärkewerte (0 bis 255) aufweisen.
Wenn das Bild aus schwarzen und weißen Bereichen besteht, wird das Histogramm normalerweise zwei Spitzenwerte und ein Tal in der Mitte der Spitzenwerte aufweisen. Die beiden, den beiden Spitzenwerten entsprechenden Graustufenwerte sind mit L01 und HI1 bezeichnet. Der dem Tal entsprechende Graustufenwert ist mit MID bezeichnet. In der Mitte von LO1 und HI1 zu MID liegen zwei Grauwerte, die jeweils mit LO2 und HI2 bezeichnet sind. Diese Positionen entlang der Intensitätsskala des Histogramms werden auf unterschiedliche Weise verwendet, um die Farbe von Teilen des Bildes zu bestimmen.
Beim Bestimmen der Farbe des Abtastarrays der Synchron-Sechsecke wird der Graustärkenwert, wenn er größer als HI2 ist, zu +1 (weiß) umgewandelt. Wenn der Graustufenwert unter LO2 liegt, wird er zu -1 (schwarz) umgewandelt. Der Rest der Graustufenwerte wird zu (Grau) umgewandelt, was möglicherweise anzeigt, daß ein Bildelement an der Grenze zwischen einem schwarzen Sechseck und einem weißen Sechseck liegt.

Bestimmung der Symbolausrichtung

Um ein Maxicode-Symbolbild zu decodieren, muß der Ort der Mitten der Sechsecke sowie deren entsprechende Intensität bekannt sein. Die Ausrichtung des Symbols innerhalb des Vollbildes 50 muß bestimmt werden und zusammen mit der zuvor bestimmten Mitte 102 des Symbols zur Berechnung des Ortes der Sechsecke verwendet werden. Die Schritte 212 bis 218 von Figur 2 beziehen sich auf den Prozeß des Auffindens der Ausrichtung des Symbols.
Zusammengefaßt verwendet der Prozeß eine Korrelationstechnik, um die Position der Symbolachsen aufzufinden. Zunächst wird eine in der Mitte des Scheibenzentrums zentrierte Schablone mit sich radial erstreckenden Armen oder Spindeln über dem Symbol gedreht, und Graustufenwerte unter den Spindeln werden wie unten beschrieben verglichen, um eine Sequenz von Korrelationskoeffizienten zu gewinnen, die hier als "Ausrichtungsssignaln bezeichnet werden. Diese Korrelationskoeffizienten sind von der Bildstärke unabhängig. Diese Sequenz wird gefiltert und analysiert, um den Ausrichtungswinkel zu bestimmen, wobei es sich um den Winkel zwischen der x-Achse des Bildes und der zuerst angetroffenen Symbolachse handelt. Die Symbolachsen liegen unter dem Ausrichtungswinkel und bei sechs radialen Positionen, die sich von dem Ausrichtungswinkel um Mehrfache von 60 Grad unterscheiden. Mit den Synchron- Sechsecken wird bestimmt, bei welcher dieser Positionen die Hauptsymbolachse liegt. Um Bildverzerrung und begrenzte Bildauflösung zu berücksichtigen, werden die Richtung jeder Symbolachse und die Größe von Sechsecken entlang jeder Achse fein abgestimmt.

1. Eine Schablone erstellen.

Nunmehr unter Bezugnahme auf Figur 10 wird eine Schablone 70 gezeigt, die aus sechs Paaren von Spindeln 74 besteht, die um 60 Grad voneinander beabstandet sind. Jedes Paar von Spindeln ist auf einer mit gepunkteten Linien gezeigten radialen Spindelachse 73 zentriert und weist zwei gleichmäßig beabstandete parallele Linien 72 auf, eine auf jeder Seite der Spindelachse 73. Die Linien 72 sind unter einem ausgewählten Abstand von der Spindelachse positioniert, nämlich einem Bruchteil des oben bestimmten geschätzten durchschnittlichen Sechseckdurchmessers. Dabei kann sich ein Abstand zwischen den parallelen Linien 72 von etwa 1,0 Bildelemente bei einer Auflösung von etwa 70 dpi bis etwa 2,0 Bildelemente bei einer Auflösung von etwa 130 dpi ergeben. Die gewählte Beabstandung kann innerhalb dieses Bereichs von Werten auf der Grundlage der gemessenen Auflösung eines bestimmten Bildes bestimmt werden. Entlang der parallelen Linien werden besondere Datenerfassungsstellen aufge tragen, die einander paarweise gegenüberliegend angeordnet sind. Der Abstand zwischen den parallelen Linien 72 wird so gewählt, daß bei Ausrichtung einer Spindelachse zu einer Symbolachse die beiden Datenerfassungsstellen jedes Paars innerhalb des gleichen Sechsecks des Bildes liegen.
Die besonderen Datenerfassungsstellen werden entlang den Linien 72 wie folgt aufgetragen. Wenn die Schablone über dem Bild des Symbols positioniert ist, werden für diese Stellen Graustufenbildelementwerte aufgezeichnet. Diese Stellen werden bei einer Spindel mit p1, p2, p3, p4, p5, p6 bzw. q1, q2, q3, q4, q5, q6 bezeichnet. Um sicherzustellen, daß diese Punkte außerhalb des Bereichs des Scheibenzentrums liegen, beginnen sie unter einem Abstand von 6 Sechseckdurchmessern von der Mitte der Schablone aus entlang der parallelen Linien 72. Die Stellen p1...p6 sind voneinander um einen Abstand eines Sechseckdurchmessers gleichmäßig beabstandet, und die Stellen q1...q6 sind auf die gleiche Weise direkt auf der anderen Seite von p1...p6 entlang der gegenüberliegenden Linie 72 positioniert. Insgesamt liegen sechs Paare von Linien 72 vor, die jeweils 2 Mengen von 6 Datenerfassungsstellen liefern. Dementsprechend werden aus den p- und q-Stellen aller sechs Spindeln zwei erweiterte Sequenzen derartiger Stellen für insgesamt 36 p-Stellen und 36 q-Stellen gebildet. Um alle die Werte zu verketten, werden die Bildelementwerte jeder Sequenz auf der in Figur 10 gezeigten Schablone mit p1, p2, p36 und q1, q2, ... q36 bezeichnet. Wie unten erläutert, wird das Ausrichtungssignal aus einem Vergleich zweier Sequenzen von Graustufenwerten entsprechend diesen beiden Sequenzen von Datenerfassungsstellen berechnet.
Von dem Prozessor 36 wird für jedes von dem CCD-Detektor erfaßte Bild eine neue Schablone 70 erstellt. Die oben beschriebene Scheibenzentrumerfassungsprozedur liefert einen in Bildelementen gemessenen, geschätzten durchschnittlichen Sechseckdurchmesser, der mit der Auflösung des Bildes variiert. Vorzugsweise liegt anfänglich eine der Spindelachsen 73 entlang der x-Achse des Bildes. Es ware moglich, auf der Grundlage der Auflösung des Bildes viele im voraus erstellte Schablonen zur Wahl zu speichern, dies würde aber beträchtlichen Speicherplatz erfordern, und die Berechnung einer Schablone 70 erfolgt sehr schnell.
Nunmehr unter Bezugnahme auf Figur 11 wird weiterhin der Prozeß des Anwendens der Schablone 70 zum Erstellen des eindimensionalen Ausrichtungssignals gezeigtf aus dem die Etikettausrichtung geschätzt werden kann. Durch überlagern der Schablone 70 auf das Maxicode-Symbol 10, wobei jeweilige Mitten zusammenfallen, können die Graustufenwerte an Bildelementstellen, die unter den Punkten p1, p2, ..., p36 liegen, als eine Sequenz aus sechsunddreißig Elementen erhalten werden. Ebenso bilden die Graustufenwerte an Bildelementorten, die unter den Punkten q1, q2, ..., q36 liegen, eine weitere Sequenz aus sechsunddreißig Elementen. Der Korrelationskoeffizient p der beiden Sequenzen kann dann berechnet werden. Einfach ausgedrückt ist der Korrelationskoeffizient zweier Sequenzen ein Maß für die paarweise Differenz beim Graustufenwert zwischen den beiden Sequenzen. Je größer der Korrelationskoeffizient, umso geringer ist die Differenz zwischen den beiden Sequenzen. Der Wert des Korrelationskoeffizienten liegt immer im Bereich von null bis einschließlich eins. Ein Korrela tionskoeffizient zwischen den beiden Sequenzen kann durch folgende Gleichung berechnet werden:
(where = wobei)
und g(pi) und g(qi) stehen für die Graustufenwerte von Bildelementen an den Stellen pi bzw. qi.

2. Erzeugung eines eindimensionalen Ausrichtungssignals

Die Schablone 70 wird über den Bilddaten mit der Mitte der Schablone in der Mitte des Scheibenzentrums "errichtet", und die Koordinaten der Datenstellenorte werden notiert. Die anfängliche Ausrichtung der Schablone ist derart&sub1; daß die einer Menge von parallelen Linien 72 zugeordnete Spindelachse 73 zu der x-Achse des Bildelementkoordinatensystems ausgerichtet ist und einem Winkel von 0 Grad entspricht. Es versteht sich allerdings, daß die anfängliche Platzierung der Schablone nicht so beschränkt ist, da die Schablone symmetrisch ist und beliebig platziert werden kann, solange wie die Mitte mit der Mitte des Symbols zusammenfällt. Die beiden Sequenzen von Graustufenwerten werden aufgezeichnet, und für die anfängliche Position der Schablone wird ein Korrelationskoeffizient 1 berechnet und gespeichert. Die Schablone wird dann vorzugsweise entgegen dem Uhrzeigersinn durch ein festes Winkelinkrement gedreht. Von der Schablone unter dem neuen Winkel werden Graustufenwerte bei den neuen Datenstellenpositionen gewonnen, und ein neuer Korrelationskoeffizient 2 wird erhalten und im Speicher dem neuen Winkel zugeordnet.
Die gleiche Prozedur wird mit dem festen Winkelinkrement solange wiederholt, bis die Gesamtdrehung der Schablone 60 Grad erreicht. Durch die Wahl des Winkelinkrements wird die Genauigkeit beim Lokalisieren der Ausrichtung des Maxicode-Symbols beeinflußt. Ein zu großes Inkrement kann zu einem ungenauen Ausrichtungswinkel führen, während ein zu kleines Inkrement zusätzliche Rechenleistung bedeutet, ohne die Genauigkeit signifikant zu verbessern. Bei der bevorzugten Ausführungsform der Erfindung wird als das Inkrement 0,5 Grad verwendet.
Der Fachmann wird verstehen, daß bei Drehung der Schablone von null bis sechszig Grad in 0,5-Grad- Inkrementen der innere Teil des gesamten Maxicode-Symbols von den sechs Paaren der parallelen Linien 72 Ilabgetastetn wird. Somit wird eine Sequenz von 120 Korrelationskoeffizienten 1... 120 gewonnen und gespeichert, die jedem der 120 Winkelinkremente entsprechen. Diese Sequenz bzw. dieses eindimensionale Array wird als das eindimensionale Ausrichtungssignal bezeichnet.
Die Schablone 70 ist so ausgelegt, daß der größte Korrelationskoeffizient erhalten wird, wenn die Spindelachsen entlang der Mitten der die Symbolachsen bildenden Sechsecke liegen. Dies gilt, da beim Ausrichtungswinkel 56 für jeden Datenerfassungspunkt auf einer parallelen Linie 72 der Schablone der entsprechende Punkt auf der anderen parallelen Linie 72 zum gleichen Sechseck gehört, weshalb die beiden Punkte die gleichen Graustufenwerte aufweisen sollten. Die so gewonnenen beiden Sequenzen entsprechen unter den 120 Koeffizienten dem größten Korrelationskoeffizient. Der Ausrichtungswinkel 56 kann deshalb durch Merken eines Winkels, der einer bestimmten Eigenschaft des Ausrichtungssignals entspricht, vorzugsweise des größten, in dem eindimensionalen Ausrichtungssignal gespeicherten Korrelationskoeffizienten, geschätzt werden.
An dieser Stelle ist es wert, nochmals anzumerken, daß die Beabstandung zwischen den beiden parallelen Linien der Schablone 70 bei der Erzeugung des eindimensionalen Ausrichtungssignals wichtig ist. Die Beabstan dung sollte die Größe des Maxicode-Symbols 10 widerspiegeln. Bei Maxicode-Symboletiketten festgelegter Bildauflösung ist die Beabstandung eine feste Größe. Sie sollte klein genug sein, damit die sechs Paare paralleler Linien der Schablone mit dem Ausrichtungswinkel entlang der Symbolachsen 0, 1, 2, 3, 4, 5 in die Sechsecke passen können. Dies wird wichtiger, wenn das Bild des Maxicode-Symbols Verzerrungen enthält. Die Achsen eines verzerrten Maxicode-Symbolbildes sind nicht länger voneinander um präzise 60 Grad beabstandet. Durch Verringerung der Beabstandung zwischen den zwei parallelen Linien der Schablone 70 besteht eine gute Möglichkeit, daß die parallelen Linien 72 bei der richtigen Ausrichtung immer noch entlang aller sechs Symbolachsen in die Sechsecke passen. Andererseits kann die Beabstandung nicht zu klein sein, so daß die Schablone 70 bei irgendeiner falschen Ausrichtung, die nicht dem Ausrichtungswinkel entspricht, ebenfalls einen großen Korrelationskoeffizienten ergibt. Die Beabstandung ist aus diesem Grund zu der Größe der Sechsecke direkt proportional. Bei der bevorzugten Ausführungsform der vorliegenden Erfindung variiert die Beabstandung zwischen 1,0 und 2,0 Bildelementen, was der Bildauflösung im Bereich von 70 dpi bis 130 dpi entspricht.

3. Eindimensionale Ausrichtungssignal filterung

Es wird nun der Prozeß der Wahl des hchsten Korrelationskoeffizienten des eindimensionalen Ausrichtungssignals beschrieben. Das eindimensionale Ausrichtungssignal kann aufgetragen werden, wie schematisch in Figur 12A gezeigt, die den Wert des Korrelationskoeffizienten über die Winkelposition der Schablone 70 zwischen 0 und 59,5 Grad aufgetragen zeigt. Das eindimensionale Ausrichtungssignal enthält gewöhnlicherweise aufgrund von Bildverzerrung und Rauschen, was durch Etikettendruck, Bilderzeugung und Digitalisierung erzeugt wird, viele steile Spitzen. Der Filterungsschritt 214 von Figur 2 ist deshalb erforderlich, um diese falschen Spitzen zu entfernen. Die Wirkung des Filterungsschritts liegt im Glätten der Kurve und der Verringerung der Plötzlichkeit jeder abrupten Veränderung. Allgemein werden steile Spitzen zu niedrigeren, breiteren Spitzenwerten reduziert, während die Höhe breiter Spitzenwerte relativ unverändert bleibt. Figur 12B zeigt das Signal von Figur 12A nach Filterung auffolgende Weise.
Da das Ausrichtungssignal eine Funktion von Winkeln zwischen 0 und 59,5 Grad mit einem Inkrement von einem halben Grad ist, wird das Ausrichtungssignal sich wiederholen, wenn der Winkel 60 Grad erreicht und darüber hinausgeht. Das Ausrichtungssignal kann somit vollständig als eine Kurve dargestellt werden, die sich mit den von bis 59,5 Grad reichenden Winkelinkrementen verändert, wie in Figur 12A gezeigt. Um die Filterungsprozedur zu erleichtern, wird die Kurve gewickelt, nämlich 0 und 59,5 Grad werden verkettet. Ebenfalls in gestrichelten Linien ist ein sich bewegendes Fenster WIN gezeigt, das eine bestimmte Anzahl von Winkeln überdeckt und an die Kurve angelegt wird. Die Koeffizienten bei Winkeln innerhalb des Fensters werden gemittelt, und der Mittelwert ersetzt den Wert- in der Mitte des Fensters. Auf diese Weise werden die Spitzen im Signal nach unten gemittelt. Um den Ausrichtungswinkel am besten beizubehalten und um zu verhindern, daß sich der Ausrichtungswinkel verschiebt, enthält das in der bevorzugten Ausführungsform verwendete Fenster WIN lediglich drei benachbarte inkrementale Winkelpositionen der Schablone. Bei jedem Winkel wird der gefilterte Korrelationskoeffizient als der Mittelwert der drei Korrelationskoeffizienten, die dem betrachteten Winkel und seinem linken und rechten benachbarten Winkel entsprechen, berechnet.
Möglicherweise werden bei einem Durchgang einer derartigen Tiefpaßfilterung nicht notwendigerweise alle unerwünschten Spitzen entfernt. Bei der bevorzugten Ausführungsform werden drei Durchgnge angewendet. Nach drei Durchgängen der Filterung besteht eine große Möglichkeit, daß der Ausrichtungswinkel 56 dem höchsten Spitzenwert in dem geglätteten Ausrichtungssignal entspricht. Um in der Praxis einen Fall zu verhindern, bei dem der höchste Spitzenwert nicht den wahren Ausrichtungswinkel angibt, wird die wahre Ausrichtung aus dem Ausrichtungssignal mit einer vorbestimmten Anzahl von Spitzenwerten, beispielsweise den fünf höchsten Spitzenwerten bestimmt. Vorzugsweise findet der Prozessor den höchsten verbleibenden Spitzenwert und wählt ihn als einen der in Frage kommenden Spitzenwerte aus. Dann werden die Daten für zwei Winkelpositionen auf jeder Seite dieses Spitzenwerts verworfen, indem sie auf Null gesetzt werden. Danach wird in den verbleibenden Daten der nächsthöhere Korrelationskoeffizient gefunden, und sein Winkel wird als ein Kandidat gewählt, und die Daten für zwei Winkelpositionen auf jeder Seite dieses Spitzenwerts werden verworfen. Dies wird solange wiederholt, bis fünf in Frage kommende Winkel identifiziert worden sind.

4. Wählen des richtigen Ausrichtungswinkels

Unter den fünf als Ausrichtungswinkel in Frage kommenden Winkeln wird eine Wahl getroffen, indem bestimmt wird, welcher Kandidat am besten einer Ausrichtung des Symbols entspricht, bei der die Synchron- Sechsecke richtig positioniert sind. Eine der Symbolachsen 0, 1, 2, 3, 4, 5 ist von der x-Achse des Bilds um den Ausrichtungswinkel entfernt. Um allerdings die Symbolausrichtung zu finden, muß der Hauptwinkel 54 bestimmt werden. Wie in Figur 7 veranschaulicht, stehen der Hauptwinkel und der Ausrichtungswinkel durch folgende Gleichung in Beziehung:
Hauptwinkel = Ausrichtungswinkel + (r x 60º),
wobei die beiden Winkel in Gradeinheiten angegeben sind und r eine ganze Zahl ist, die einen Wert von 0, 1, 2, 3, 4 und 5 annimmt. Bei dem in Figur 7 gezeigten Beispiel eines Maxicode-Symbols hat r den Wert 3.
Der Ausrichtungswinkel und die ganze Zahl r können durch Verwendung der in der Maxicode-Symbolik eingebetteten Synchron-Sechsecke bestimmt werden. Es wurde bereits erläutert, daß die achtzehn Synchron- Sechsecke ein eindeutiges Muster bilden. Das Muster kann durch ein eindimensionales Array aus achtzehn Elementen dargestellt werden, deren Werte entweder +1 oder -1 betragen, je nach dem, ob die vorbestimmte Farbe der Sechsecke weiß der schwarz ist. Sechs derartige eindimensionale Arrays können erzeugt werden, indem jedesmal mit einer anderen Symbolachse begonnen wird. Wie oben beschrieben, verläuft jede Symbolachse durch zwei Synchron-Sechsecke. Fur jede Achse wird das eindimensionale Synchron-Array durch Gruppieren der Farbe der Synchron-Sechsecke, die durch entweder +1 oder -1 dargestellt wird, im Uhrzeigersinn, bei der Achse beginnend, erzeugt. Wie angemerkt, gibt es deshalb sechs eindimensionale Synchron-Arrays, die jeweils einer der sechs Achsen der Maxicode-Symbolik entsprechen. Die sechs eindimensionalen Arrays können gruppiert werden, um eine Synchron-Nachschlagetabelle oder ein zweidimensionales Array derart zu erstellen, daß jede Achse durch ein ordnungsgemäß geordnetes Synchron-Array, das eine Zeile der Tabelle darstellt, identifiziert werden kann. Eine derartige Nachschlagetabelle ist in Tabelle I gezeigt, und die angegebenen Werte entsprechen den Synchron-Sechsecken des in Figur 7 gezeigten Symbols. TABELLE I
Zeile 0 der Nachschlagetabelle enthält vorzugsweise das eindimensionale Synchron-Array, das mit den Werten der Synchron-Sechsecke auf der Hauptachse (Symbolachse 0) beginnt, und Zeile 1 beginnt mit den Synchron- Sechseckwerten der Symbolachse 1, usw.
Zum Vergleich auf der Grundlage jedes in Frage kommenden Ausrichtungswinkels nacheinander werden die Grauwerte an den Stellen, wo sich die Mitten der 18 Synchron-Sechsecke befinden sollten, berechnet, um ein eindimensionales Abtastarray aus Synchron-Sechsecken in Graustufenwerten zu erzeugen. Ein besonderes, unten beschriebenes Schwellwertbildungsverfahren, das das Histogramm von Figur 8 verwendet, wird angewendet, um das Abtastarray in ein Array aus Elementen umzuwandeln, die entweder schwarz, weiß oder grau sind, wobei den weißen Sechsecken +1 zugeordnet wird, den schwarzen Sechsecken -1 zugeordnet wird und der grauen Farbe 0 zugeordnet wird. Die Abweichung zwischen dem Array der Synchron-Sechsecke und ihrem Abtastarray muß bei dem richtigen Ausrichtungswinkel ein Minimum sein.
Insbesondere können auf der Grundlage des in Frage kommenden Ausrichtungswinkels und der mittleren Größe der Sechsecke, die zuvor gewonnen wurden, die vorgeschlagenen mittleren Bildelementstellen der achtzehn Synchron-Sechsecke bestimmt werden. Die Graustufenwerte bei diesen Bildelementstellen werden gewonnen und dann entweder in +1, -1 oder 0 umgewandelt. Diese Zahlen werden in dem eindimensionalen Abtastarray gemäß der gleichen, bei der Erstellung des eindimensionalen Synchron-Arrays der Nachschlagetabelle verwendeten Reihenfolge angeordnet. Das Abtastarray wird dann mit jedem der sechs Synchron-Arrays in der Synchron- Nachschlagetabelle verglichen, um das Synchron-Array zu finden, bei dem die geringste Summe an Synchron- Differenzen an jedem Elementvergleich erhalten wird. Das heißt, die entsprechenden Elemente des Nachschlagetabellenarrays und des Abtastarrays werden subtrahiert, und die Absolutwerte dieser Differenzen werden summiert. Wenn, wie oben vorgeschlagen, die Zeilenzahlen der Nachschlagetabelle den Achsenzahlen des Symbols entsprechen, dann liefert die Zeilenzahl (Achse des Maxicode-Symbols), die dem am besten angepaßten Synchron-Array zugeordnet ist, die ganze Zahl r zur Bestimmung des Hauptwinkels 54. Das Ergebnis dieses Prozesses ist eine vorgeschlagene Ausrichtung des Symbols, wenn dieser in Frage kommende Winkel der richtige Ausrichtungswinkel ist.
Der Fachmann wird verstehen, daß durch richtige Ordnung der sechs Synchron-Arrays, wie oben beschrieben, die ganze Zahl r als der Schleifenindex für das Synchron-Array bestimmt werden kann, das die geringste Summe an Synchron-Differenzen von dem geprüften Abtastarray aufweist. Dies kann in der Synchron- Nachschlagetabelle erreicht werden, indem das der Achse 0 zugeordnete Synchron-Array als das Synchron-Array markiert wird, das der Achse 1 zugeordnete Synchron-Array als Synchron-Array 1 markiert wird, usw. Der Schleifenindex geht von 0 bis 5.
Um zu bestimmen, welcher der in Frage kommenden Spitzenwerte der fünf höchsten Spitzenwerte des eindimensionalen Ausrichtungssignals der richtige Ausrichtungswinkel ist, kann die obige Prozedur für jeden in Frage kommenden Winkel und die geringste Summe von aufgezeichneten Synchron-Differenzen erfolgen. Unter allen in Frage kommenden Ausrichtungwinkeln ist der Kandidat, der die geringste Summe an Synchron-Differenzen ergibt, -der Ausrichtungswinkel. Die Achse, die dem Synchron-Array zugeordnet ist, das die geringste Summe von Synchron-Differenzen von dem von diesem Kandidat erzeugten Abtastarray aufweist, ergibt die richtige ganze Zahl r.
Es wird nun das besondere Schwellwertbildungsverfahren beschrieben, das beim Prüfen der in Frage kommenden Spitzenwerte verwendet wird. Beim Erzeugen des Abtastarrays für jeden Kandidaten für den Ausrichtungs winkel werden zwei Schwellwertpegel, LO2 und HI2, im Histogramm von Figur 8 verwendet. Ein Bildelement mit einem Graustufenwert größer oder gleich HI2 wird als weiß festgelegt und es erhält einen Wert 1 zugeordnet. Ein Bildelement mit einem Graustufenwert kleiner gleich LO2 wird als schwarz festgelegt, und ihm wird ein Wert -1 zugeordnet. Ein Bildelement mit einem Graustufenwert zwischen HI2 und LO2 wird als grau festgelegt, und ihn wird ein Wert von 0 zugeordnet. Dieses Verfahren stellt im wesentlichen sicher, daß die kleinste Summe der Synchron-Differenz immer dem Ausrichtungswinkel und der richtigen Achse entspricht. Der Hauptwinkel kann dann als die Summe der Ausrichtungswinkel plus r Mehrfache von sechszig Grad berechnet werden.

5. Feinabstimmung der Richtungen der Symbolachsen und der Sechseckgroßen.

Von dem Hauptwinkel aus, der der Achse 0 entspricht, können die anderen fünf Symbolachsen durch Addieren von unterschiedlichen Mehrfachen von 60 Grad lokalisiert werden. Da in einigen Fällen eine Bildverzerrung vorliegt (hauptsächlich aufgrund von Etiketten, die nicht in einer Ebene senkrecht zur Kameraoptik liegen), und aufgrund von begrenzter Bildauflösung weichen die anfänglich berechneten Winkelpositionen der Symbolachsen gewöhnlicherweise um einen kleinen Offset von ihren tatsächlichen Positionen ab. Außerdem nehmen möglicherweise nicht alle Sechsecke im Bild die gleiche Größe an. Aus diesem Grund sollten diese beiden Parameter, nämlich die Richtung jeder Achse und die Sechseckgröße entlang der Achse, justiert werden&sub1; bevor sie bei der Bestimmung der Mitten einzelner Sechsecke verwendet werden können. Dies geschieht bei Schritt 218 von Figur 2.
Die beiden Parameter weisen möglicherweise keinen Fehler auf, das heißt die berechnete Achse verläuft genau durch die Mitte jedes Sechsecks auf der Achse, und die Größe von Sechsecken entlang dieser Achse ist die gleiche und ist bekannt. Die Mittenkoordinaten jedes Sechsecks entlang der Achse, beginnend bei der Mitte des Scheibenzentrums, können dann unter Verwendung des Winkels der Achse und der bekannten Größe der Sechsecke berechnet werden. Wenn allerdings einer der beiden Parameter, die die Richtung der Achse oder die Größe von Sechsecken entlang der Achse darstellen, nicht genau ist, dann wird mindestens ein Teil der berechneten Mitten nicht mit den tatsächlichen Mitten der Sechsecke entlang der Achse zusammenfallen. Um die Genauigkeit der beiden Parameter zu prüfen, wird eine im Flußdiagramm von Figur 14 (und ausführlich unten beschriebene) Prozedur durchgeführt, um zu bestimmen, wieviele tatsächliche Sechseckmitten durch verschiedene Kombinationen der beiden Parameter, Achsrichtung und Sechseckgröße genau vorausgesagt werden. Die Prozedur zum Vergleichen verschiedener Kombinationen der Parameter wird schematisch in Figur 13 gezeigt, und die Prozedur zum Bestimmen, ob ein Punkt im Bild in der Mitte eines Sechsecks liegt, wird schematisch teilweise in Figur 15 gezeigt. Diese Prozeduren werden auch ausführlich unten beschrieben. Für jedes Paar von Parametern wird ein ganzzahliger Zählwert aufgezeichnet und aktuahsiert, um die Anzahl berechneter Mitten anzugeben, bei denen es sich wirklich um die eigentlichen Mitten handelt. Wenn die beiden Parameter keine Fehler aufweisen, sollten die berechneten Mitten der Sechsecke entlang der Achse mit den eigentlichen Mitten zusammenfallen, und der ganzzahlige Zählwert der genauen Mitten ist hoch. Wenn die Parameter nicht genau sind, sollte der den beiden Parametern zugeordnete ganzzahlige Zählwert der genauen Mitten kleiner sein als der den richtigen Parametern zugeordnete.
Nunmehr ausführlicher auf Figur 13A Bezug nehmend, können die aus dem Hauptwinkel berechneten sechs Achsen durch das folgende Verfahren justiert werden. Beispielsweise bei einer der Achsen 61 beginnend werden einige wenige Strahlen 61a, 61b, 61c und 61d, die von der Mitte des Scheibenzentrums ausgehen und der Achse 61 benachbart sind, derart gewählt, daß jeder Strahl die Achse um ein Mehrfaches von 0,5 Grad versetzt. Diese Strahlen sowie die Achse 61 werden die Kandidaten für die richtige Achse des Maxicode-Symbols. Analog dazu werden verschiedene Zahlen, die geringfügig größer und kleiner sind als die mittlere Größe von Sechsecken (geschätzt wie oben beschrieben) gewählt und als die Kandidaten für die richtige Größe von Sechsecken entlang der richtigen Achse verwendet. Die Schrittgröße bei der Suche nach der richtigen Größe von Sechsecken wird so gewählt, daß sie 0,05 Bildelemente beträgt. Die korrekte Größe der Sechsecke kann somit lediglich die durchschnittliche Sechseckgröße plus oder minus ein Mehrfaches von 0,05 sein.
Figur 13B veranschaulicht ein Paar Parameter ohne Fehler. Der vorgeschlagene Strahl 61 verläuft direkt durch alle Sechseckmitten 62 entlang der Achse, und alle Mitten werden von der vorgeschlagenen Sechseckgröße richtig vorhergesagt. Figur 13C zeigt ein Paar Parameter einschließlich einer richtigen Achsenrichtung, aber einer falschen Sechseckgröße. Es werden somit nur einige richtige Sechseckmitten 62 vorhergesagt, während andere vorhergesagte Mitten 63 tatsächlich nicht die Mitten von Sechecken im Bild sind. Figur 13D zeigt einen Fehler sowohl bei der Richtung als auch bei der Rechteckgröße. Es wird noch zu sehen sein, daß der ganzzahlige Zählwert für das in Figur 138 veranschaulichte Paar von Parametern größer ist als der Zählwert für Figur 13C, der größer Bein wird als der Zählwert für Figur 13D.
Jede Kombination aus den Achsenrichtungskandidaten und den Größenkandidaten wird als Paar Versuchsparameter zum Erzeugen eines ganzzahligen Zählwerts verwen det, der anzeigt, wieviele berechnete Koordinaten tatsächlich die Mitten der Sechsecke darstellen. Vorzugsweise werden Sechsecke 12a entlang der in Frage kommenden Achse und Sechsecke 12n neben beiden Seiten der Sechsecke entlang der in Frage kommenden Achse geprüft. Das Paar von Versuchsparametern, das den größten ganzzahligen Zählwert erzeugt, wird als die richtige Achse und die Größe von Sechsecken entlang der Achse verwendet.
Der jedem Satz von Versuchsparametern zugeordnete ganzzahlige Zählwert wird gemäß des in Figur 14 gezeigten Algorithmus erzeugt. Es wird anfänglich bei Schritt 308 ein Paar Versuchsparameter gewählt. Bei Schritt 309 kann mit den Synchron-Sechsecken die Anzahl der Iterationen der Prozedur von Figur 14 begrenzt werden, indem schnell einige ungenaue Paare von Parametern eliminiert werden. Es ist beschrieben worden, daß die richtigen geometrischen Stellen der 18 Synchron-Sechsecke unter Verwendung der richtigen Richtung jeder Achse und der richtigen Größe der Sechsecke entlang der Achse berechnet werden können. Wenn bei der Berechnung dieser Stellen die falsche Größe von Sechsecken und die falsche Richtung einer Achse benutzt werden, können die Bildelementwerte für Sechsecke bei diesen berechneten Stellen nicht zu einer zufriedenstellenden übereinstimmung der bekannten Farben des Synchron-Musters führen. Nur diejenigen Paare von Parametern, die eine gute übereinstimmung mit den Synchron-Sechsecken liefern, brauchen bei der folgenden Prozedur von Figur 14 verwendet zu werden.
Für jedes Paar von Versuchsparametern muß die Farbe von Bildelementen an den berechneten Stellen der drei Synchron-Sechsecke mit der Farbe der wahren Synchron-Sechsecke um die betreffende Achse herum übereinstimmen. Die Farbe von Bildpunkten kann bestimmt werden, indem nur der Schwellwertpegel MID des Histogramms von Figur 8 verwendet wird, um schwarz von weiß zu unterscheiden. Der Schwellwertpegel MID ist der Talpunkt im Histogramm. Um den Wert zu bestimmen, gibt es viele alternative Wege, die dem Fachmann bekannt sind. Unter Einsatz von MID kann entweder schwarz oder weiß bestimmt werden, je nach dem, ob die Graustufenwerte der Bildelemente entweder kleiner oder nicht kleiner als MID sind. Falls es einem Paar von Versuchsparametern nicht gelingt, das richtige Synchron-Muster zu erzeugen, dann besteht keine Notwendigkeit, weiterzugehen, um den dem Paar von Versuchsparametern, die verworfen werden können, zugeordneten ganzzahligen Zählwert zu berechnen.
Für ein bei Schritt 308 gewhltes Paar von Versuchsparametern, die die Richtung eines Strahls und die Sechseckgröße entlang des Strahls darstellen, wird nach Bestehen der vorangegangenen Synchron-Musterprüfung vom Schritt 309 der zugeordnete ganzzahlige Zhlwert bei Schritt 310 auf null initialisiert. Eine vorbestimmte Anzahl von Sechseckmitten entlang des Strahls, die durch Bildkoordinaten (x, y) dargestellt werden, sowie denjenigen entlang des Strahls benachbarte Mitten von Sechsecken werden bei Schritt 312 berechnet. Aus Gründen der Genauigkeit sollen die Zahlen x und y in Gleitkommadarstellung sein. Für jede der sechs Maxicode-Symbolachsen kann die vorbestimmte Anzahl entlang des Strahls als die Anzahl von Sechsecken entlang der Achse gewählt werden. Beispielsweise können für die Achsen 0, 1, 2, 3, 4, 5 die Zahlen 9, 11, 11, 10, 11, 11 verwendet werden.
Bei Schritt 314 wird eine der berechneten Sechseckmitten (x, y) gewählt. Die Koordinaten (x, y) werden bei Schritt 316 unter Verwendung von Zeile = (int) (y+0,5), Spalte = (int) (x+0,5) in ganzzahlige Werte umgewandelt, wobei int bedeutet, daß nur der ganzzahlige Teil der Zahl genommen wird. Auf diese Weise soll sichergestellt worden, daß die Gleitkommakoordinaten in die ganz zahligen Koordinaten desjenigen Bildelements umgewandelt werden, dessen Mitte den Gleitkommawerten am nächsten liegt. Das Bildelement an der Stelle (Zeile, Spalte) wird dann daraufhin geprüft, ob es schwarz, weiß oder keines von beidem ist. Die hier eingesetzte Graustufenschwellwertprüfung basiert auf den Pegeln LO1 und HI1 des Histogramms von Figur 8. Wenn der Wert des Bildelements weder größer als HI1 noch kleiner als LO1 ist, dann kann das Bildelement nicht die Mitte eines Sechsecks sein, und für das Bildelement ist keine weitere überprüfung erforderlich. Wenn der Graustufenwert kleiner als LO1 ist, dann wird festgestellt, daß das Bildelement schwarz ist, und es wird mit B bezeichnet. Wenn der Graustufenwert größer als HI1 ist, dann wird festgestellt, daß das Bildelement weiß ist, und es wird mit W bezeichnet. In beiden Fällen werden die Stellen von vier benachbarten Bildelementen des betrachteten Bildelements bei Schritt 320 unter Verwendung eines unten beschriebenen Verfahrens erhalten. Eine weitere überprü fung der vier benachbarten Bildelemente geschieht bei Schritt 322. Keiner der Graustufenwerte der vier benachbarten Bildelemente eines schwarzen Bildelements B sollte größer als der Histogrammpegel LO2 sein, wohingegen keiner der Graustufenwerte der vier benachbarten Bildele mente eines weißen Bildelements W kleiner als HI2 sein sollte. Erst nach dem Bestehen dieser Prüfungen ist bestätigt, daß das Bildelement die Mitte eines Sechsecks ist, und der dem geprüften Paar von Parametern zugeordnete ganzzahlige Zählwert wird bei Schritt 324 erhöht.
Der Prozeß kehrt zu Schritt 314 zurück und wird wiederholt, um zu kontrollieren, ob die Koordinaten der nächsten berechneten Sechseckmitte tatsächlich in der Mitte eines Sechsecks im Bild liegen. Nach der Prüfung der vorherbestimmten Anzahl berechneter Mitten wird der dem Paar von Versuchsparametern zugeordnete ganzzahlige Zählwert schließlich bei Schritt 328 bestimmt, und der Prozeß kehrt zur Wahl eines weiteren Paars von Parametern zu Schritt 308 zurück. Nachdem alle der vorbestimmten Anzahl von Paaren von Versuchsparametern auf diese Weise geprüft worden sind&sub1; wird der Achse eine Richtung und eine Sechseckgröße zugeordnet, die gleich denen des Paars von Versuchsparametern mit dem höchsten ganzzahligen Zählwert sind, das die höchste Anzahl berechneter Koordinaten darstellt, die tatsächlich die Mitten von Sechsecken darstellen.
In Block 320 werden andere Verfahren verwendet, um die vier, dem Bildelement in einer berechneten Mitte benachbarten Bildelemente zu gewinnen. Unter Bezugnahme auf Figur 15A werden fur ein schwarzes Bildelement B&sub1; seine vier benachbarten Bildelemente direkt darüber, darunter und auf seinen Seiten, die mit B1, B2, B3 und B4 bezeichnet sind, verwendet. Für ein weißes Bildelement W wird ein Block aus vier Bildelementen einschließlich W verwendet, wie in Figur 15B gezeigt. Das heißt, es werden die vier nächsten benachbarten Bildpunkte mit Koordianten (x, y), die durch W1, W2, W3 und W4 bezeichnet sind, verwendet, und je nach dem Wert nach dem Dezimalkomma bei x und y kann W jeden beliebigen der Werte W1, W2, W3 und W4 annehmen.
Die Verwendung verschiedener Verfahren beim Verifizieren der Mitte eines schwarzen oder eines weißen Sechsecks basiert auf der Überlegung, daß ein weißes Sechseck, das von schwarzen Sechsecken umgeben ist, möglicherweise bezüglich der Anzahl von Bildelementen eine kleinere Größe aufweist. Dies trifft insbesondere dann zu, wenn die Beleuchtung für das CCD-Sensorarray relativ schwach ist. Das Verfahren zum Gewinnen der vier benachbarten Bildelemente eines schwarzen Bildelements kann aber auch durch das Verfahren ersetzt werden, das für ein weißes Bildelement verwendet wird.
Es ist anzumerken, daß das obige Verfahren zum Verifizieren der Mitte eines Sechsecks für Bilder von unterschiedlichem Dynamikbereich verwendet werden kann. Beim richtigen Bestimmen der richtigen Achsen und ihrer entsprechenden Größen von Sechsecken sind die folgenden Uberlegungen wichtig. Für einen Strahl in der Nachbarschaft einer nichtigen Achse werden die Koordinaten (x, y) in dem Strahl aus dem Paar der Versuchsparameter berechnet. Weiterhin können die Koordinaten, die die Mitten der benachbarten Sechsecke 12n relativ zu denjeingen berechneten Mitten entlang des Strahls darstellen, aus dem gleichen Paar von Versuchsparametern analog berechnet werden. Mit allen diesen Koordinaten kann der ganzzahlige Zählwert erzeugt werden. Bei der Realisierung der vorliegenden Erfindung werden die Mittenkoordinaten des Sechsecks 12a entlang jedes Strahls sowie diejenigen der beiden benachbarten radialen "Zeilen" von Sechsecken 12n, wie in Figur 13A gezeigt, berechnet. Der Strahl und die beiden "Zeilen" von Sechsecken verlaufen parallel zueinander. Durch dieses Verfahren wird die Suchgenauigkeit verbessert, wenn entlang einiger der sechs Achsen Blöcke aus schwarzen und/oder weißen Sechsecken vorliegen.
Während jede der sechs Symbolachsen unabhangig voneinander auf die gleiche Weise wie oben beschrieben justiert werden kann, führt ein bevorzugtes Suchverfahren, nachdem eine Achse erst einmal justiert worden ist, die Suche nach einer neuen Achse auf der Grundlage der Suchergebnisse durch, die von der bereits justierten Achse (bzw. den bereits justierten Achsen) erhalten wurden. Bei der bevorzugten Ausführungsform der Erfindung sollte zur Suche nach dem Paar von Versuchsparametern, die die Richtung jeder wahren Achse und die Größe der Sechsecke entlang der Achse am besten beschreiben, deshalb ungeachtet eines Grads von Verzerrung eine besondere Reihenfolge eingehalten werden. Die Suche wird zuerst durchgeführt, um die wahre Achse 0 und die Größe der Sechsecke entlang der Achse 0 zu bestimmen. Der Suchraum besteht aus fünf Größen von Sechsecken mit der durchschnittlichen Sechseckgröße in der Mitte und fünf Strahlen mit der berechneten Achse 0 in der Mitte, gemäß dem in Figur 13A gezeigten Modell. Die Achse in der Mitte, die in diesem Fall die berechnete Achse Q ist, wird als die Startachse bezeichnet. Ein Vektor in der Richtung der Achse 0, dessen Richtung durch den Suchprozeß korrigiert wird und dessen Länge gleich der Größe der Sechsecke ist, kann berechnet werden. In Figur 16 ist der Vektor durch v&sub0; dargestellt. Analog dazu kann ein durch v&sub3; bezeichneter Vektor in Richtung der Achse 3 erhalten werden.
Um auf die beste Weise einen Suchraum für jede der wahren Symbolachsen 1, 2, 4 und 5 zu erstellen, sollten die von den Achsen 0 und 3 erhaltenen Suchergebnisse folgendermaßen verwendet werden. Wenn die Länge von v&sub0; die gleiche ist wie die durchschnittliche Sechseckgröße, dann wird die berechnete Symbolachse 1 als die Startachse zum Beginnen der Suche verwendet. Wenn die Länge von v&sub0; (was die Sechseckgröße darstellt) von der durchschnittlichen Sechseckgröße um ein positives (oder negatives) Vielfaches der Versuchsparameterschrittgröße 0,05 abweicht, dann sollte, anstatt die berechnete Achse 1 als Startachse zu verwenden, die Suche nach der Symbolachse 1 mit der berechneten Achse 1 plus (oder minus) dem gleichen Vielfachen des Winkelschrittintervalls (0,5 Grad) beginnen. Bei der Suche, wie sie oben beschrieben ist, werden dennoch insgesamt fünf Strahlen verwendet. Die Suche wird dann durchgeführt und führt zu einem Vektor v&sub1; in Richtung der wahren Symbolachse 1. Analog dazu sollte die Suche nach der Symbolachse 5 mit der berechneten Achse 5 minus (oder plus) dem gleichen Vielfachen von 0,5 Grad beginnen. Aus dem Suchprozeß kann ein Vektor v&sub5; erhalten werden.
Entsprechend der Länge von v&sub3; können die berechneten Achsen 2 und 4 auf die gleiche Weise justiert werden, um die Startachse für den Suchprozeß zu lokalisieren. Die Suche führt zu zwei Vektoren v&sub2; und v&sub4; in den Richtungen der Achsen 2 bzw. 4.

Lokalisieren von Mitten aller Sechsecke des Svmbols

Nunmehr unter Bezugnahme auf Figur 16 wird ein systematischer Weg veranschaulicht, die Mitten von Sechsecken des Maxicode-Symbolbildes zu lokalisieren. Mit den Vektoren v&sub0;, v&sub1;, ..., v&sub5;, die eine für jede Symbolachse individuell bestimmte justierte Sechseckgröße verkörpern, können die Mitten der Sechsecke entlang der sechs Symbolachsen bestimmt werden. Die Mitten der Sechsecke innerhalb des von der Achse 0 und Achse 1 begrenzten Bereichs können dann mit dem Vektor v&sub0; lokalisiert werden. Das heißt, die Mitte jedes Sechsecks in jeder teilweisen Zeile von Sechsecken, die sich links von der Achse 1 erstreckt, kann gefunden werden, indem Mehrfache von Vektor v&sub0; zu den Koordinaten eines Sechsecks entlang der Achse 1 hinzuaddiert werden. So wird beispielsweise die Mitte des Sechsecks 69 in Figur 16 bestimmt, indem ein Mehrfaches von v&sub0; (6 × v&sub0;) zu der Position von Sechseck 68, das auf der Achse 1 liegt, hinzuaddiert wird. Bei der Mitte 102 des Symbolbildes beginnend, kann die Position von Sechseck 69 durch die Vektorgleichung 14v&sub1; + 6v&sub0; dargestellt werden. Mit dem gleichen Prozeß werden diejenigen Mitten innerhalb des von der Achse 0 und Achse 5 begrenzten Bereichs bestimmt, indem Mehrfache von Vektor v&sub0; zu den Koordinaten von Sechsecken entlang Achse 5 hinzuaddiert werden.
Analog dazu können die Mitten der Sechsecke in dem von Achsen 2 und 4 begrenzten Bereich lokalisiert werden, indem Mehrfache von Vektor v&sub3; zu den Koordinaten von Sechsecken entlang der Symbolachsen 2 und 4 hinzuaddiert werden. Für die Sechsecke innerhalb des Bereichs zwischen Achsen 1 und 2 werden Mehrfache des Vektors (v&sub2; - v&sub1;) zu den Koordinaten von Sechsecken entlang Achse 1 hinzuaddiert. Für die Sechsecke innerhalb des Bereichszwischenachsen4undswerdenmehrfachedes Vektors (v&sub4; - v&sub5;) zu den Koordinaten von Sechsecken entlang Achse 5 hinzuaddiert.
Wenn eine Verzerrung vorliegt, wird die Fehleran häufung auf ein Minimum reduziert, wenn die sechs Segmente des Symbols einzeln auf die obige Weise behandelt werden.
Die Graustufenwerte in den Mitten der Sechsecke bilden eine Matrix von Zahlen und können bei dem nachfol genden Decodierprozeß verwendet werden. Ein Decodierprozeß wird in den US-Patenten Nr. 4,874,936 und 4,896,029 beschrieben.
Die vorliegende Erfindung ist hinsichtlich besonderer Ausführungsformen beschrieben worden, die in jeder Hinsicht beispielhaft und nicht begrenzend sein sollen. Alternative Ausführungen werden für den Fachmann auf dem Gebiet, auf das sich die vorliegende Erfindung bezieht, offensichtlich, ohne vom Schutzumfang der vorliegenden Erfindung abzuweichen, die durch die beigefügten Ansprüche anstatt durch die vorausgegangene Beschreibung definiert wird.

Claims

1. Verfahren zum Bearbeiten eines Bildes, was folgendes einschließt: Entwickeln (212) einer Abtastschablone (70) mit einer Reihe von Punktepaaren (pi, qi), die entlang zweier paralleler Linien (72) beabstandet sind, die geringen Abstand voneinander haben, wobei jedes Paar einen ersten Punkt (Pi) aufweist, der auf einer der parallelen Linien gegenuber einem zweiten Punkt (qi) des Paares auf der anderen parallelen Linie positioniert ist; Positionieren der Schablone auf den Bilddaten; und Vergleichen von Graustufenstärken der ersten Punkte des Paares mit Graustufenstärken jeweiliger zweiter Punkte des Paares, um zwischen den ersten Punkten und den zweiten Punkten einen Korrelationsfaktor zu bestimmen; gekennzeichnet durch folgende Schritte:

Bewegen der Abtastschablone (70) in verschiedene Ausrichtungen bezüglich des Bildes und Bestimmen des Korrelationsfaktors für jede Position der Schablone; und

Identifizieren von einer oder mehreren Mengen kollinearer Elemente (12) in dem Bild durch Auffinden einer oder mehrerer Schablonenpositionen, die charakteristischen Werten des Korrelationsfaktors zugeordnet sind.

2. Verfahren nach Anspruch 1, wobei die Reihen von Punktepaaren radial von einem Schablonenmittelpunkt ausgehen; wobei der Schritt des Positionierens der Schablone das Positionieren des Schablonenmittelpunkts an einem Mittelpunkt des Bildes umfaßt; und wobei der Schritt des Bewegens der Schablone das Drehen der Schab lone um den Schablonenmittelpunkt umfaßt.

3. Verfahren nach Anspruch 1 oder 2, bei dem die kollinearen Elemente (12) Teil einer zweidimensionalen Symbolik (10) sind.

4. Verfahren nach Anspruch 3, bei dem die kollinearen Elemente (12) mindestens eine radiale Menge benachbarter Elemente umfassen, deren Mitten entlang einer durch einen Anfangspunkt des Symbols gehenden Linie (0-3, 1-4, 2-5) liegen.

5. Verfahren nach Anspruch 1, bei dem das Bild eine mehrzeilige Bildelementmatrix mit einem zweidimensionalen, optisch lesbaren Symbol (10) der Art, das Elemente mit mindestens zwei verschiedenen Reflexionsgraden aufweist, und mindestens eine radiale Menge benachbarter Elemente umfaßt, deren Mitten entlang einer durch einen Anfangspunkt des Symbols gehenden Linie (0-3, 1-4, 2-5) liegen, und wobei die Schritte für die Bearbeitung des Bildes folgendes umfassen:

Entwickeln einer Abtastschablone (70) mit einer Reihe von Punktepaaren (Pji qi), die entlang zweier Linien (72) beabstandet sind, die parallel zu einem Radius durch den Anfangspunkt sind, wobei die Punkte jedes Paares den gleichen Abstand von dem Anfangspunkt aufweisen, einer auf jeder der Linien;

Vergleichen von Graustufenstärken der ersten Punkte des Paares mit Graustufenstärken der zweiten Punkte des Paares, um einen Korrelationsfaktor zwischen ihnen zu bestimmen;

stufenweises Drehen der Abtastschablone um den Anfangspunkt und wiederholtes Bestimmen des Korrelationsfaktors für jede Drehposition der Schablone; und

Identifizieren der radialen Menge benachbarter Elemente durch Auffinden der Drehposition, die charakteristischen Werten des Korrelationsfaktors zugeordnet ist.

6. Verfahren nach Anspruch 5, bei dem der Schritt des Identifizierens der radialen Menge benachbarter Elemente weiterhin das Bilden eines eindimensionalen Signals durch Auftragen des Korrelationsfaktors über der Drehposition und Filtern des Signais umfaßt.

7. Verfahren nach Anspruch 5 oder 6, das weiterhin umfaßt, den Anfangspunkt des Symbols durch folgende Schritte zu lokalisieren:

Lokalisieren eines begrenzten Elements (102), das entlang mindestens zweier Richtungen Symmetrie zeigt; und Bestimmen einer Mitte des begrenzten Elements.

8. Verfahren nach einem der Ansprüche 5 bis 7, bei dem das Symbol (10) mehrere in einer Matrix angeordnete polygonale, Informationen codierende Elemente (12) umfaßt.

9. Verfahren nach einem der Ansprüche 5 bis 8, bei dem der Schritt des Auffindens der charakteristischen Korrelationsfaktorwerten zugeordneten Position umfaßt, ein Ausrichtungssignal zu bilden, das für jede Position der Schablone (70) eine Folge der Korrelationsfaktoren umfaßt, und die Höhe der Spitzenwerte des Signals zu vergleichen, um den höchsten Spitzenwert zu finden.

10. Verfahren nach Anspruch 9, das weiterhin den Schritt der Tiefpaßfilterung (214) der Spitzenwerte des Ausrichtungssignals umfaßt.

11. Verfahren nach Anspruch 5, bei dem das zweidimensionale, optisch lesbare Symbol (10) mehrere radiale Mengen benachbarter Elemente (12) aufweist, deren Mitten entlang Achsen (Achsen 0 - 5) liegen, die durch den Anfangspunkt des Symbols gehen und um den Anfangspunkt herum gleichmäßig beabstandet sind, wobei die Elemente eines von mindestens zwei verschiedenen Reflexionsgraden aufweisen, wobei:

in der Abtastschablone (70) die Anzahl und die Beabstandung der Reihen von Punktepaaren gleich der Anzahl und Beabstandung der Achsen ist;

für jede der mehreren Reihen von Punktepaaren ein Korrelationsfaktor bestimmt wird; und

die Position der Achsen von radialen Mengen benachbarter Elemente durch Auffinden der dem höchsten Korrelationsfaktor zugeordneten Drehposition der Schablone identifiziert wird.

12. Verfahren nach Anspruch 11, bei dem das Symbol (10) mehrere in einer Matrix angeordnete polygonale, Informationen codierende Elemente (12) umfaßt.

13. Verfahren nach Anspruch 11 oder 12, bei dem jeder Achse des Symbols ein eindeutiges Muster von Ausrichtungselementen (16) zugeordnet ist und das weiterhin das Identifizieren (216) jeder der Achsen. durch Bestimmen, welches Muster von Ausrichtungselementen der Achse zugeordnet ist, umfaßt.

14. Verfahren nach einem der Ansprüche 11 bis 13, weiterhin mit einem Verfahren zum individuellen Justieren (218) der Positionen der Achsen, was folgende Schritte umfaßt:

Auswählen (308) mehrerer Kombinationen von Achsenrichtungen (61) und Elementgrößen als Versuchsparameter;

für jedes Paar von Versuchsparametern wiederum das Bestimmen der Orte in dem Bild, an denen die Mitten (63) der Elemente (12) entlang der Achse auftreten würden;

Bestimmen, ob die Mitten der Elemente tatsächlich an den Orten auftreten; und

Auswählen des Paares von Versuchsparametern, die tatsächliche Sechseckmitten (62) am besten lokalisieren.

15. Verfahren nach Anspruch 14, bei dem der Schritt des Bestimmens der Orte in dem Bild, an denen die Mitten der Elemente entlang der Achse auftreten würden, das das Bestimmen der Orte enthält, an denen die Mitten der Elemente neben der Achse auftreten würden.

16. Verfahren nach Anspruch 14 oder 15, bei dem das Verfahren des individuellen Justierens der Positionen der Achsen weiterhin das Bestimmen umfaßt, ob jedes Paar von Versuchsparametern die Farben des eindeutigen Musters von Ausrichtungselementen voraussagt.

17. Verfahren nach Anspruch 16, weiterhin mit dem Schritt des Berechnens der Positionen der Mitten der Elemente in einem Bereich neben jeder der Achsen unter Verwendung der für jede der Achsen individuell justierten Elementgröße.

18. Verfahren nach einem der Ansprüche 14 bis 17, bei dem der Schritt des Bestimmens (322), ob die Mitten der Elemente tatsächlich an den Orten auftreten, umfaßt, für jeden der Orte zu bestimmen, ob benachbarte Bildelemente (B1 - B4, W1 - W4) des Bildes die Farbe aufweisen, die der Farbe an dem Ort gleicht.

19. Verfahren nach Anspruch 5, bei dem das zweidimensionale Symbol ein Schlüsselelement (102) aufweist, wobei das Schlüsselelement ein geometrisch symmetrisches, begrenztes Element mit einem ersten Reflexionsgrad ist, das von einem Gebiet (101) mit einem zweiten Reflexionsgrad vollständig umgeben ist, weiterhin mit folgenden Schritten:

Lokalisieren (208) des Schlüsselelements durch:

Abtasten (254 - 268) des gespeicherten Bildes entlang einer ersten Abtastrichtung, um ein in Frage kommendes begrenztes Element zu erfassen, das entlang der ersten Abtastrichtung Symmetrie zeigt; und

Bestimmen (276), ob das in Frage kommende begrenzte Element entlang einer von der ersten Richtung verschiedenen zweiten Richtung symmetrisch ist;

Lokalisieren (286, 288) eines Anfangspunktes durch Untersuchen von Graustufenstärken innerhalb des Schlüsselelements, um eine Mitte des Schlüsselelements zu lokalisieren;

Bestimmen der ungefähren Größe der Elemente des Symbols durch Mittelung mehrerer verschiedener Durchmesser des Schlüsselelements.

20. Bildverarbeitungssystem, das folgendes umfaßt: eine auf dem Bild positionierte Abtastschablone (70) mit einer Reihe von Punktepaaren (Pi, qi), die entlang zweier paralleler Linien (72) beabstandet sind, die geringen Abstand voneinander haben, wobei jedes Paar einen ersten Punkt (pi) aufweist, der auf einer der parallelen Linien gegenüber. einem zweiten Punkt (qi) des Paares auf der anderen parallelen Linie positioniert ist; und einen Vergleicher (36) zum Vergleichen von Graustufenstärken der ersten Punkte des Paares mit Graustufenstärken jeweiliger zweiter Punkte des Paares, um zwischen den ersten Punkten und den zweiten Punkten einen Korre lationsfaktor zu bestimmen; gekennzeichnet durch:

einen Positionierer (36) zum Bewegen der Abtastschablone in verschiedene Ausrichtungen bezüglich des Bildes, wobei der Vergleicher den Korrelationsfaktor für jede Position der Schablone bestimmt; und

einen Finder (36) zum Identifizieren von einer oder mehreren Mengen kollinearer Elemente (12) in dem Bild durch Auffinden einer oder mehrerer Schablonenpositionen, die charakteristischen Werten des Korrelationsfaktors zugeordnet sind.

21. Bildverarbeitungssystem nach Anspruch 20, bei dem die Reihen von Punktepaaren radial von einem Schablonenmittelpunkt ausgehen; und wobei der Positionierer (36) den Schablonenmittelpunkt an einen Mittelpunkt des Bildes bewegt und die Schablone durch Drehen der Schablone um den Schablonenmittelpunkt bewegt.

22. Bildverarbeitungssystem nach Anspruch 20 oder 21, bei dem das Bildverarbeitungssystem ein System zum Bestimmen der Ausrichtung eines optisch lesbaren, zweidimensionalen Symbols (10) der Art, die Elemente (12) mit mindestens zwei verschiedenen Reflexionsgraden aufweist, und mehrere radiale Mengen benachbarter Elemente umfaßt, deren Mitten entlang von durch einen Anfangspunkt des Symbols gehenden Achsen (0-3, 1-4, 2-5) liegen und gleichmäßig um den Anfangspunkt herum beabstandet sind, umfassend:

eine Lichtquelle (22);

einen Detektor (30) mit einem Array von Bildelementen, die so positioniert sind, daß sie Licht von der Lichtquelle, das von dem Symbol reflektiert wurde, empfangen;

eine Ausleseschaltung (32), die so angeschlossen ist, daß sie Datensignale von den Bildelementen erhält und in einer Speichervorrichtung (34) ein das Symbol enthaltendes Bild bildet; und

einen Prozessor (36), der ausgebildet ist, die Position der Achsen der radialen Mengen benachbarter Elemente zu lokalisieren, durch:

Entwickeln einer Abtastschablone (70) mit mehreren Reihen von Punktepaaren (Pi, qi), die entlang zweier Linien (72) beabstandet sind, die parallel zu einem Radius durch den Anfangspunkt verlaufen, wobei die Punkte jedes Paares den gleichen Abstand von dem Anfangspunkt aufweisen, einer auf jeder der Linien, wobei die Anzahl und die Beabstandung der Reihen gleich der Anzahl und Beabstandung der Achsen ist;

Vergleichen von Graustufenstärken der ersten Punkte des Paares mit Graustufenstärken der zweiten Punkte des Paares, um für alle Reihen einen Korrelationsfaktor zwischen ihnen zu bestimmen;

stufenweises Drehen der Abtastschablone um den Anfangspunkt und wiederholtes Bestimmen des Korrelationsfaktors für jede Position der Schablone; und

Auffinden der Position der Schablone, die dem höchsten Korrelationsfaktor zugeordnet ist.

23. Bildverarbeitungssystem nach Anspruch 22, bei dem das zweidimensionale Symbol ein Schlüsselelement (102) aufweist, wobei das Schlüsselelement ein geometrisch symmetrisches, begrenztes Element mit einem ersten Reflexionsgrad ist, das von einem Gebiet (101) mit einem zweiten Reflexionsgrad vollständig umgeben ist, und wobei:

der Prozessor (36) ausgelegt ist, das Schlüsselelement zu lokalisieren, durch:

Lokalisieren (286, 288) des Anfangspunktes durch Untersuchen von Graustufenstärken innerhalb des Schlüsselelements, um eine Mitte des Schlüsselelements zu lokalisieren;