Die
Erfindung betrifft im allgemeinen eine verbesserte Vorrichtung zum
Auffinden und Lesen innerhalb einer Abbildung gedruckter, zweidimensionaler
Strichcodes.The
This invention relates generally to an improved apparatus for
Find and read within a printed, two-dimensional image
Barcodes.
Im
Gegensatz zu den häufigen
Voraussagen, daß wir
eines Tages in einer "papierlosen
Gesellschaft" leben
werden, spielen Papier und andere bedruckte Medien eine zunehmend
wichtige Rolle als ein billiges, effektives und zweckmäßiges Kommunikationsmittel.
Eine grundlegende Einschränkung
bei Papier ist jedoch, daß es
vom Standpunkt des Computers aus gegenwärtig ein Format allein zur
Ausgabe ist. Während
Papier das bevorzugte Medium zur Anzeige von Information für den Gebrauch
durch den Menschen sein kann, ist es schwierig, wenn nicht unmöglich, daß ein Computer
zuverlässig
Daten wiederfinden kann, sobald sie gedruckt worden sind. Die optische
Zeichenerkennung (optical character recognition oder OCR) versucht,
dieses Problem auf einem relativ einfachen Gebiet, wie Text, der
unter Verwendung von Standardfonts ausgedrückt ist, zu lösen, hat
dies aber bisher nur mit begrenztem Erfolg erreicht. Während Genauigkeitsraten
von neunundneunzig (99 %) Prozent vielleicht erzielbar sind und
eindrucksvoll erscheinen mögen,
wird eine Seite mit 3000 Zeichen noch im Durchschritt dreißig (30)
OCR-Fehler aufweisen und somit eine teure und zeitraubende Nachbearbeitung
von Hand benötigen.in the
Unlike the frequent ones
Predict that we
one day in a "paperless
Society "live
paper and other printed media are increasingly playing
important role as a cheap, effective and appropriate means of communication.
A basic limitation
with paper, however, that is it
From the standpoint of the computer currently a format alone for
Edition is. While
Paper is the preferred medium for displaying information for use
It can be difficult, if not impossible, for a computer
reliable
Can find data once they have been printed. The optical
Character recognition (optical character recognition or OCR) attempts to
this problem in a relatively simple area, like text, the
using standard fonts
but so far only achieved with limited success. While accuracy rates
of ninety-nine (99%) percent may be achievable and
like to appear impressive
a page with 3000 characters is still in step thirty (30)
OCR errors and thus an expensive and time-consuming post-processing
Need by hand.
Ein
anderer Ansatz verwendet computerlesbare Strichcodes, die direkt
auf Papier (oder einem anderen bedruckten Medium, wie Mikrofilm)
enthalten sein können.
Sobald sie codiert worden sind, können derartige Strichcodes
von dem Computer verwendet werden, um Information wiederzufinden,
die für
den menschlichen Leser offenbar, aber für einen Computer schwierig
zu erkennen ist (z.B. gedruckter Text), Information, die zur Schaffung
der Seite einbegriffen, jedoch für
den menschlichen Leser im wesentlichen unsichtbar ist (z.B. Tabellenkalkulationsformulare),
oder irgendwelche andere gewünschte
Information, ob von dem tatsächlichen Zeichentext
auf dem Papier abhängig
oder nicht.One
another approach uses computer-readable barcodes directly
on paper (or other printed medium, such as microfilm)
may be included.
Once encoded, such barcodes may
used by the computer to retrieve information,
the for
the human reader obviously, but difficult for a computer
(e.g., printed text), information to be created
the page included, however for
is essentially invisible to the human reader (e.g., spreadsheet forms),
or any other desired
Information, whether from the actual character text
dependent on the paper
or not.
Computerlesbare
Strichcodes, in denen digitale Daten direkt auf Papier aufgezeichnet
sind, sind bekannt und sind dafür
verwendet worden, eine Dokument- oder Produktkennzeichnung bereitzustellen,
wobei ein fester Satz von Werten unter Verwendung einfacher numerischer
Codierungs- und
Lesetechniken gegeben ist. Dokument- oder Produktkennzeichnungssysteme,
die in der Vergangenheit angewandt worden sind, umfassen Strichcodemarkierer
und -lesegeräte,
die in einem weiten Bereich von Schauplätzen Verwendung gefunden haben.
Mit Bezug auf Papierdokumente sind spezielle Markierungen oder Muster
in dem Papier dazu verwendet worden, Information über ein
in Beziehung stehendes Ausrüstungsstück bereitzustellen,
beispielsweise das Auftragssteuerungsblatt zur Bildverarbeitung,
wie es von Hikawa in dem US-Patent Nr. 5 051 779 gelehrt wird. Ähnlich sind
Kennzeichnungsmarkierungen, die codierte Information umfassen, auf
die Fläche vorgedruckter
Formulare gedruckt worden, wie es in dem US-Patent Nr. 5 060 980
von Johnson et al beschrieben worden ist. Das System von Johnson
et al schreibt vor, daß ein
Benutzer handgeschriebene Information in die Felder einer Papierkopie des
Formulars eingibt und dann das Formular abtastet, liest oder scannt,
um Einträge
in die Felder in dem Duplikatformular zu schaffen, das elektronisch
in dem Computer gespeichert ist. Ein weiteres System ist in dem
US-Patent Nr. 5 091 966 von Bloomberg et al beschrieben, das das
Decodieren von skulpturförmigen
Codes lehrt, die digital codierte Daten auf Papier sind. Die Kennzeichnungscodes
können
von einem Computer gelesen werden und vereinfachen dadurch die Computerhandhabung
des Dokuments, wie die Kennzeichnung, das Wiederfinden und das Übertragen
eines solchen Dokuments.computer readable
Barcodes in which digital data is recorded directly on paper
are known and are for
been used to provide a document or product identifier,
where a fixed set of values using simple numeric
Coding and
Reading techniques is given. Document or product labeling systems,
which have been used in the past include bar code markers
and readers,
which have found use in a wide range of venues.
With regard to paper documents are special markers or patterns
in the paper has been used for information about
to provide related equipment,
for example, the job control sheet for image processing,
as taught by Hikawa in U.S. Patent No. 5,051,779. Are similar
Identification marks comprising encoded information
the area preprinted
Forms have been printed as disclosed in U.S. Patent No. 5,060,980
has been described by Johnson et al. The system of Johnson
et al
User handwritten information in the fields of a paper copy of the
Type form and then scan, read or scan the form
around entries
to create the fields in the duplicate form that electronically
is stored in the computer. Another system is in the
U.S. Patent No. 5,091,966 to Bloomberg et al
Decode sculptural
Codes teaches that are digitally coded data on paper. The identification codes
can
be read by a computer, thereby simplifying computer handling
of the document, such as marking, retrieving and transmitting
such a document.
Neben
den oben beschriebenen, verschieden geformten Strichcodes sind zweidimensionale
Strichcodes, die "Datenstreifen" genannt werden,
mit mehreren Reihen aus "Datenlinien", die auf bedruckte
Medien digital codierte Information darstellen, in der Technik ebenfalls
bekannt. Jede Datenlinienreihe besteht aus einer Reihe aus schwarzen
und weißen
Pixeln oder Bildpunkten, die jeweils eine binäre "0" bzw. "1" darstellen. Die Orientierung oder Ordnung
der Bits in jeder Reihe bestimmt die darin gespeicherten digitalen
Daten. Die in der Gesamtheit der Reihen gespeicherten Daten definieren
die Daten, die in dem zweidimensionalen Strichcode enthalten sind.
Um den Strichcode zu lesen, führt
der Benutzer normalerweise ein Handlesegerät (Handscanner), das gleichzeitig
die Information in jeder Datenlinienreihe liest, vertikal entlang
der Länge
des Strichcodes, um alle Datenlinienreihen zu lesen.Next
The differently shaped bar codes described above are two-dimensional
Barcodes called "data strips"
with multiple rows of "data lines" printed on it
Media digitally encoded information, in the art as well
known. Each data line series consists of a series of black ones
and white
Pixels or pixels, each representing a binary "0" or "1". The orientation or order
The bits in each row determine the digital data stored therein
Dates. Define the data stored in the entirety of the rows
the data contained in the two-dimensional bar code.
To read the barcode leads
The user usually uses a handheld reader (handheld scanner) at the same time
the information in each data line reads vertically
the length
of the bar code to read all data line rows.
Ein
Beispiel eines Systems nach dem Stand der Technik, das einen zweidimensionalen
Datenstreifenstrichcode mit Reihen aus Datenlinien mit Papiermedien
verwendet, wird in den US-Patenten Nr. 4 692 603, 4 754 127 und
4 782 221 von Brass et al gefunden. Bei diesem System bestehen zweidimensionale
Strichcodes aus Datenlinienreihen, die dazu verwendet werden, Computerprogramme
und Daten auf Papier zu codieren, und unter Verwendung eines Handlesegerätes eingelesen
oder gescannt werden. Zusätzlich
zum Codieren der Computerprogramme und Daten enthalten diese Datenlinien
auch Folge- und Synchronisationsbits, die nachstehend als "Taktbits" bezeichnet werden.
Die Anforderung zur Verwendung zahlreicher Taktbits direkt innerhalb
jeder Datenlinienreihe reduziert die Menge von digitalen Daten wesentlich,
die innerhalb jeder Reihe gespeichert werden kann. Wenn Datenlinienreihen
mit Taktbits beschädigt
sind, was üblich
ist, wenn derartige Strichcodes fotokapiert oder durch Faksimilesysteme übertragen
werden, würden
ferner derartige Taktbits verlorengehen, was es schwierig, wenn
nicht unmöglich,
macht, die in dem Strichcode codierte Information zu decodieren.
Andere Beispiele von zweidimensionalen Strichcodes umfassen: (1)
US-Patent Nr.An example of a prior art system that uses a two-dimensional data stripe bar code with rows of data lines with paper media is found in U.S. Patent Nos. 4,692,603, 4,754,127 and 4,782,221 to Brass et al. In this system, two-dimensional bar codes consist of data line rows that are used to encode computer programs and data on paper, and read or scanned using a hand-held reader. In addition to encoding the computer programs and data, these data lines also include follow-up and synchronization bits hereinafter referred to as "clock bits". The requirement to use many clock bits directly within each data line row substantially reduces the amount of digital data that can be stored within each row. Furthermore, if data lines of clock bits are corrupted, which is common when such bar codes are photocopied or transmitted by facsimile systems, such clock bits would be lost, making it difficult, if not impossible, to decode the information encoded in the bar code. Other examples of two-dimensional bar codes include: (1) US Pat.
5
083 214 von Knowles; das ein zweidimensionales Strichcodesystem
beschreibt, das innerhalb der codierten Daten selbst eingebettete
Taktbits erfordert, und (2) US-Patent Nr. 4 924 078 von Sant'Anselmo et al, das
ein zweidimensionales Strichcodesystem beschreibt, bei dem ein Orientierungs-
und/oder Zeitgebungszellenrand innerhalb des Körpers des Strichcodes selbst
enthalten ist.5
083 214 from Knowles; this is a two-dimensional bar code system
describes that embedded within the encoded data itself
Clock bits, and (2) U.S. Patent No. 4,924,078 to Sant'Anselmo et al
describes a two-dimensional bar code system in which an orientation
and / or timing cell edge within the body of the bar code itself
is included.
In
der anhängigen
Patentanmeldung "A
Clock-Free Two-Dimensional Barcode and Method for Printing and Reading
the Same", (Serial
Nr. 08/569 280, am 8. Dezember 1995 eingereicht) ("die '280-Anmeldung"), deren Offenbarungsgehalt
hierin durch Bezugnahme explizit enthalten ist, ist ein taktloser,
zweidimensionaler Strichcode mit einem Rand auf mindestens einer
der vier Seiten des Strichcodes beschrieben, wobei der Rand außerhalb
der Umgrenzungen des Strichcodes selbst angeordnet ist. Die zweidimensionalen
Strichcodes werden manchmal "PanaMarks"® genannt.
Wie es in 1A hierin abgebildet ist, ist
ein zweidimensionaler Strichcode 10 an der unteren rechten
Ecke einer bedruckten Seite 11 gedruckt, obwohl diese Position
völlig
beliebig ist. Bei der in 1A abgebildeten
Ausführungsform
ist der restliche Teil der bedruckten Seite 11 von gedrucktem
Text 12 eingenommen. Jedoch wird ein Fachmann feststellen,
daß irgendeine
Art eines computererzeugten, bedruckten Materials, beispielsweise
ein Tabellenkalkulationsblatt oder Graphiken, den gedruckten Text 12 ersetzen
kann. Der zweidimensionale Strichcode 10, der hierin in 1B abgebildet
ist, umfaßt
einen Rand 13, der an all seinen vier Seiten vorhanden
ist. Wie es in der '280-Anmeldung
vollständig
beschrieben ist, ist der Rand 13, obwohl er nur auf einer
der vier Seiten des zweidimensionalen Strichcodes 10 notwendig
ist, aus ästhetischen
Gründen
typischerweise auf allen vier Seiten enthalten.In co-pending patent application "A Clock-Free Two-Dimensional Barcode and Method for Printing and Reading the Same", (Serial No. 08 / 569,280, filed December 8, 1995) ("the '280 application"), the Disclosed herein, by reference, is a tactless, two-dimensional bar code having an edge on at least one of the four sides of the bar code, the margin being located outside the boundaries of the bar code itself. The two-dimensional barcodes are sometimes called "PanaMarks" ® . As it is in 1A Shown herein is a two-dimensional bar code 10 at the lower right corner of a printed page 11 printed, although this position is completely arbitrary. At the in 1A Illustrated embodiment is the remaining part of the printed page 11 of printed text 12 ingested. However, one of ordinary skill in the art will recognize that some type of computer-generated printed matter, such as a spreadsheet or graphics, will print the printed text 12 can replace. The two-dimensional barcode 10 that is in here 1B is imaged, includes an edge 13 which is present on all its four sides. As fully described in the '280 application, the edge is 13 although he only on one of the four sides of the two-dimensional barcode 10 necessary, for aesthetic reasons typically included on all four pages.
In
der anhängigen
Patentanmeldung "A
Borderless Clock-Free Two-Dimensional
Barcode and Method for Printing and Reading the Same", (Serial Nr. 09/088
189, am 1: Juni 1998 eingereicht) ("die ' 189-Anmeldung"), deren Offenbarungsgehalt
hierin durch Bezugnahme explizit enthalten ist, ist ein taktloser,
zweidimensionaler Strichcode ohne eine Rand (hierin in 2 gezeigt)
zusammen mit Verfahren zum Drucken und Lesen desselben beschrieben.
In der '189-Anmeldung
sind zwei alternative Symbologien für den Strichcode dargestellt,
und zwar eine erste Symbologie, die erfordert, daß die vier
Eckenbits 21 schwarz sind (wenn auf einen weißen Hintergrund
gedruckt wird), und eine zweite Symbologie, in der keine schwarzen
Eckenbits 21 erforderlich sind. Als solche sind zwei alternative
Verfahren zum Lesen des Strichcodes von 2 in der '189-Anmeldung beschrieben,
und zwar ein erstes Verfahren, das den Strich code verarbeitet, der
keine Eckenbits erfordert, wie es durch das Flußdiagramm in 8A darin
und der damit in Beziehung stehenden Beschreibung beschrieben ist,
und ein zweites Verfahren; das den Strichcode verarbeitet, der Eckenbits
benötigt,
wie es durch das Flußdiagramm
in 8B darin und die damit in Beziehung
stehende Beschreibung beschrieben ist. Obwohl die beiden Verfahren
zum Lesen des Strichcodes, die in der '189-Anmeldung beschrieben sind, befriedigende
Ergebnisse liefern, wurde es herausgefunden, daß, wenn der Strichcode auf
eine Seite mit einem komplexen Hintergrund gedruckt war, die durch
den Auffindungsschritt 70 der 8A und 8B der '189-Anmeldung,
die darin in Verbindung mit den 9A und 9B beschrieben
ist, gelieferten Ergebnisse weniger als optimal waren, insbesondere
bei der Anwesenheit von Einzellinienrauschzuständen (d.h., eine beliebige
Linie über
den Strichcode hinweg mit einer Breite, die kleiner oder gleich
der Breite eines Bitblocks innerhalb des Strichcodes ist, was oft
bei gefaxten Dokumenten und durch schlecht gewartete Drucker gedruckten
Dokumenten auftreten kann). Zusätzlich
wurde herausgefunden, daß Änderungen
bei dem Schritt der Abschätzung des
Schrägstellungwinkels über Hough-Transformation 71 der 8A und 8B der '189-Anmeldung vorgenommen
werden könnten,
um die Verarbeitungsgeschwindigkeit zu erhöhen. Wegen der zunehmenden
Verarbeitungsgeschwindigkeit des Schrittes der Abschätzung des
Schrägstellungwinkels über Hough-Transformation der
vorliegenden Erfindung ist auch der Schritt der Abschätzung des
Schrägstellungswinkels
zur Vorlagenanpassung 71 der 8B der '189-Anmeldung nicht
länger
erforderlich, der es erfordert, daß der Strichcode Eckenbits
umfaßt,
wodurch die Zahl von Bits verkleinert wird, die innerhalb des Strichcodes
gespeichert werden kann, und eine weniger als optimale Verarbeitungsgeschwindigkeit
aufweist.In the pending patent application "A Borderless Clock - Two-Dimensional Barcode and Method for Printing and Reading the Same", (Serial No. 09 / 088,189, filed June 1, 1998) ("the '189 application"), the disclosure of which is expressly incorporated herein by reference, is a tactless, two-dimensional bar code without an edge (herein incorporated by reference) 2 shown) along with methods of printing and reading the same. In the '189 application, there are two alternative symbologies for the bar code, a first symbology that requires the four corner bits 21 are black (when printed on a white background), and a second symbology in which there are no black corner bits 21 required are. As such, two alternative methods of reading the bar code are 2 in the '189 application, a first method that processes the barcode that does not require corner bits, as shown by the flowchart in FIG 8A therein and the related description, and a second method; which processes the barcode that requires corner bits as indicated by the flowchart in FIG 8B therein and the related description is described. Although the two methods of reading the bar code described in the '189 application provide satisfactory results, it has been found that when the bar code was printed on a page with a complex background, that was determined by the retrieval step 70 of the 8A and 8B the '189 application incorporated herein in connection with the 9A and 9B provided results were less than optimal, especially in the presence of single line noise conditions (ie, any line across the bar code with a width that is less than or equal to the width of a bit block within the bar code, which is often the case for faxed documents and through poorly maintained printer printed documents may occur). In addition, it has been found that changes in the skew angle estimation step are via Hough transform 71 of the 8A and 8B The 189 application could be made to increase the processing speed. Also, because of the increasing processing speed of the step of estimating the skew angle via Hough transform of the present invention, the step of estimating the skew angle is for template matching 71 of the 8B The 189 application no longer requires that the bar code include corner bits, thereby reducing the number of bits that can be stored within the bar code and having a less than optimal processing speed.
Es
ist deshalb ein Ziel der vorliegenden Erfindung, eine Vorrichtung
zum Decodieren von Information zu schaffen, die digital in der Form
eines randlosen, taktfreien, zweidimensionalen Strichcodes codiert
ist, der auf ein bedrucktes Medium gedruckt ist, das bei Anwesenheit
komplexer Hintergründe
arbeiten kann.It
It is therefore an object of the present invention to provide a device
to decode information that is digital in shape
encoded a borderless, tact-free, two-dimensional barcode
which is printed on a printed medium in the presence
complex backgrounds
can work.
Es
ist ein zusätzliches
Ziel dieser Erfindung, eine Vorrichtung zum Decodieren von Information
zu schaffen, die digital in der Form eines randlosen, taktfreien,
zweidimensionalen Strichcodes codiert ist, der auf ein bedrucktes
Medium gedruckt ist, das eine verbesserte Verarbeitungsgeschwindigkeit
aufweist.It is an additional object of this invention to provide an apparatus for decoding information which is encoded digitally in the form of a borderless, tact-free, two-dimensional bar code printed on a printed medium having an improved processing speed.
Es
ist außerdem
ein weiteres Ziel dieser Erfindung, eine Vorrichtung zum Decodieren
von Information zu schaffen, die digital in der Form eines randlosen,
taktfreien, zweidimensionalen Strichcodes codiert ist, der auf ein
bedrucktes Medium gedruckt ist und keine Eckenbits umfaßt.It
is also
Another object of this invention is an apparatus for decoding
to create information that is digital in the form of a borderless,
clock-free, two-dimensional bar codes coded on a
printed medium is printed and does not include corner bits.
Es
ist ein anderes Ziel dieser Erfindung, eine Vorrichtung zum Decodieren
von Information zu schaffen, die digital in der Form eines zweidimensionalen
Strichcodes codiert ist, der auf ein bedrucktes Medium gedruckt
ist, und der einen Rand umfassen kann oder auch nicht umfassen kann.It
Another object of this invention is an apparatus for decoding
to create information that is digital in the form of a two-dimensional
Barcodes coded on a printed medium
is, and may or may not include an edge.
Verschiedene
andere Ziele, Vorteile und Merkmale der vorliegenden Erfindung werden
leicht aus der folgenden detaillierten Beschreibung ersichtlich
werden, und die neuartigen Merkmale werden in den beigefügten Ansprüchen besonders
herausgestellt.Various
Other objects, advantages and features of the present invention will become apparent
readily apparent from the following detailed description
and the novel features are particularly pointed out in the appended claims
exposed.
Diese
und andere Ziele werden durch eine Vorrichtung zum Decodieren stochastisierter
Information erreicht, die auf ein von einem Menschen lesbares Medium
in der Form eines Pixel- oder Bitmusters (Bitmaps) aus Reihen und
Spalten aus Datenpixeln gedruckt ist, die codierte Datenbits darstellen.
Jedes Datenpixel weist entweder eine erste oder eine zweite Farbe
auf. Das Bitmuster weist eine vorherbestimmte Größe auf und ist von einem Außernbereich
aus Pixeln mit einer vorherbestimmten, im wesentlichen gleichmäßigen Farbe
umgeben. Ein Rand aus einer kontrastbildenden Farbe kann innerhalb
des Außenbereichs
vorhanden sein. Das vom Menschen lesbare Medium wird zuerst abgetastet
oder gescannt, um das Bitmuster zu digitalisieren, und dann zu einer
Grauskalendarstellung auf einer Pixelbasis formatiert. Die Grauskalendarstellung
auf Pixelbasis wird in eine Binärdarstellung
auf Pixelbasis umgewandelt, indem ein Schwellenwertintensitätspegel
auf der Grundlage der Grauskalendarstellung festgelegt wird, und
Pixel, die größer oder
gleich dem Schwellenwert sind, auf einen ersten Pegel, z.B. "0", umgewandelt werden,und Pixel, die
kleiner als der Schwellenwert sind, auf einen zweiten Pegel, z.B. "1", umgewandelt werden. Die Reihen- und
Spaltenumgrenzungen des digitalisierten Bitmusters werden aufgefunden
oder lokalisiert, indem ein Fenster schrittweise in einem vorherbestimmten
Muster über
die Binärdarstellung
auf Pixelbasis bewegt wird. Bei jedem Schritt wird der Teil der
Darstellung, der von dem Fenster umgeben ist, geprüft, um zu
bestimmen, ob der Teil zu einem Charakteristikum oder mehreren Charakteristiken
des Bitmusters paßt,
und die Umgrenzungen des digitalisierten Bitmusters werden als die
Umgrenzungen des Fensters festgelegt, wenn der Teil zu der einen
Charakteristik oder den mehreren Charakteristiken des Bitmusters
paßt.
Der Schrägstellungswinkel
des digitalisierten Bitmusters wird bestimmt, und die Schrägstellung
des digitalisierten Bitmusters wird gegebenenfalls be seitigt, so
daß der Schrägstellungswinkel
auf im wesentlichen Null verringert wird. Das digitalisierte Bitmuster
wird danach gestutzt oder zugeschnitten, und die Binärdaten werden
aus dem digitalisierten Bitmuster ausgelesen, wodurch ein eindimensionales
Feld oder Array aus digitalen Daten erzeugt wird. Schließlich wird
das eindimensionale Array entstochastisiert, und es wird eine Fehlerkorrektur
angewandt, um eine im wesentlichen fehlerfreie digitale Darstellung
der codierten Information zu erzeugen.These
and other objects are stochastized by an apparatus for decoding
Information reaches onto a human-readable medium
in the form of a pixel or bit pattern (bitmap) of rows and
Columns of data pixels representing coded data bits.
Each data pixel has either a first or a second color
on. The bit pattern has a predetermined size and is from an out-of-range area
of pixels of a predetermined, substantially uniform color
surround. An edge of a contrasting color may be inside
of the outdoor area
to be available. The human-readable medium is scanned first
or scanned to digitize the bit pattern, and then to a
Gray scale rendering formatted on a pixel basis. The gray scale representation
on a pixel basis will be in a binary representation
converted to pixel-based by a threshold intensity level
is determined on the basis of the gray scale representation, and
Pixels that are larger or
equal to the threshold, to a first level, e.g. "0", and pixels that are converted
are less than the threshold, to a second level, e.g. "1", to be converted. The series and
Column boundaries of the digitized bit pattern are found
or localized by stepping a window in a predetermined one
Pattern over
the binary representation
is moved on a pixel basis. At each step, the part of the
Appearance surrounded by the window checked to
determine if the part becomes one or more characteristics
the bit pattern fits,
and the boundaries of the digitized bit pattern are called the
Boundaries of the window set when the part to the one
Characteristic or the multiple characteristics of the bit pattern
fits.
The skew angle
the digitized bit pattern is determined, and the skew
the digitized bit pattern is optionally rectified, then
that the skew angle
is reduced to substantially zero. The digitized bit pattern
is trimmed or cropped afterwards, and the binary data becomes
read from the digitized bit pattern, creating a one-dimensional
Field or array of digital data is generated. Finally will
the one-dimensional array is de-stochastized, and it becomes an error correction
applied to a substantially error-free digital representation
to generate the coded information.
Bei
einer Ausführungsform
umfaßt
das Fenster, das bei dem Auffindungs- oder Lokalisierungsschritt verwendet
wird, einen Kernbereich, der der vorherbestimmten Größe des Bitmusters
entspricht, und einen Ruhebereich, der dem Außenbereich entspricht. Das
Prüfen
umfaßt
das getrennte Prüfen
von Teilen der Darstellung, die von dem Kernbereich und dem Ruhebereich
umgeben sind, um zu bestimmen, ob die Teile zu einem Charakteristikum
oder mehreren Charakteristiken des Bitmusters bzw. des Außenbereichs
passen. Vorzugsweise wird die Pixelverteilung jedes Bereichs geprüft, um zu
bestimmen, ob sie in vorherbestimmte Bereiche fällt, um zu bestätigen, daß das Bitmuster
in der Abbildung vorhanden ist, d.h., das Bitmuster im Kernbereich wird
eine annähernd
gleichmäßige Pixelverteilung
aufweisen, und der Außenbereich
wird eine Pixelverteilung aufweisen, die Pixel nahe bei 100 % mit
entweder "0" oder " 1" besitzt. Wenn die
Teile der Darstellung, die von dem Kernbereich und dem Ruhebereich
umgeben sind, zu dem einen Charakteristikum oder den mehreren Charakteristiken
des Bitmusters passen, werden die Umgrenzungen eines Kandidatbereichs
für das
digitalisierte Bitmuster auf die Umgrenzungen des Kernbereichs festgelegt.
Wenn zusätzlich
herausgefunden wird, daß die
Teile der Darstellung, die von dem Fenster umgeben sind, die vorher gehende
Prüfung
bestehen, kann der Teil, der vom Kernbereich umgeben ist, auch zugeschnitten
werden, um die äußeren Umgrenzungen
des Kandidatbitmusters darin zu bestimmen, wenn die äußeren Umgrenzungen
mit den vorherbestimmten Abmessungen des Bitmusters verglichen werden,
um weiter zu bestätigen,
daß ein
Bitmuster innerhalb des Fensters vorhanden ist.at
an embodiment
comprises
the window used in the locating or locating step
is a core area of the predetermined size of the bit pattern
corresponds, and a relaxation area, which corresponds to the outdoor area. The
Check
comprises
the separate testing
of parts of the representation, of the core area and the resting area
are surrounded to determine if the parts become a characteristic
or more characteristics of the bit pattern or the outside area
fit. Preferably, the pixel distribution of each area is checked to
determine if it falls within predetermined ranges to confirm that the bit pattern
in the figure, that is, the bit pattern becomes the core area
an approximate
even pixel distribution
and the outdoor area
will have a pixel distribution, the pixels close to 100% with
has either "0" or "1". If the
Parts of the representation of the core area and the resting area
to which one or more characteristics
of the bit pattern become the bounds of a candidate area
for the
digitized bit patterns are set to the boundaries of the core area.
If additional
it is found out that the
Parts of the representation that are surrounded by the window, the previous ones
exam
The part surrounded by the core area can also be cropped
become the outer boundaries
of the candidate bit pattern therein, if the outer boundaries
be compared with the predetermined dimensions of the bit pattern,
to further confirm
the existence
Bit pattern exists within the window.
Bei
einer anderen Ausführungsform
der vorliegenden Erfindung wird der Schrägstellungswinkel bestimmt,
indem zuerst alle horizontalen oder vertikalen Kanten innerhalb
des aufgefundenen Kandidatbereichs vorzugsweise unter Verwendung
eines Erkenners endlicher Zustände
aufgefunden werden. Die Koordinaten einer horizontalen oder vertikalen
Linie innerhalb des aufgefundenen Kandidatbereichs, die die horizontalen oder
vertikalen Kanten darstellen, werden dann unter Verwendung der Hough-Transformation berechnet. Schließlich wird
der Schrägstellungswinkel
als der Winkel zwischen den Koordinaten der horizontalen oder vertikalen
Linie innerhalb des Kandidatbereichs und einer horizontalen Linie,
die eine Reihe aus Pixeln innerhalb der Darstellung darstellt, oder
einer vertikalen Linie, die eine Spalte aus Pixeln innerhalb des
Kandidatbereichs darstellt, berechnet. Wahlweise können sowohl
die horizontalen als auch vertikalen Kanten aufgefunden werden,
und der Schrägstellungswinkel
kann unter Verwendung sowohl der horizontalen als auch vertikalen Kanten
berechnet werden.In another embodiment of the present invention, the skew angle is determined by first looking at all horizontal or vertical edges within the found candidate area preferably be found using a recognizer finite states. The coordinates of a horizontal or vertical line within the found candidate area representing the horizontal or vertical edges are then calculated using the Hough transform. Finally, the skew angle is calculated as the angle between the coordinates of the horizontal or vertical line within the candidate area and a horizontal line representing a row of pixels within the display or a vertical line representing a column of pixels within the candidate area. Optionally, both the horizontal and vertical edges can be found, and the skew angle can be calculated using both the horizontal and vertical edges.
Bei
einer anderen Ausführungsform
wird der Kandidatbereich in mehrere horizontale und/oder vertikale
Bereiche unterteilt. Für
jeden horizontalen und/oder vertikalen Bereich werden vorläufige Schrägstellungswinkel
berechnet, und der Schrägstellungswinkel
wird durch ein Wahlschema aus den vorläufigen Schrägstellungswinkeln ausgewählt, beispielsweise
wird der Medianwert ausgewählt.at
another embodiment
the candidate area is divided into several horizontal and / or vertical
Divided areas. For
each horizontal and / or vertical area becomes preliminary skew angles
calculated, and the skew angle
is selected by a selection scheme from the provisional skew angles, for example
the median value is selected.
Die
Erfindung wird im folgenden beispielhaft anhand der Zeichnung beschrieben,
in dieser ist bzw. sind:The
Invention is described below by way of example with reference to the drawing,
in this is or are:
1A ein
Diagramm, das schematisch den zweidimensionalen Strichcode der '280-Anmeldung veranschaulicht,
der auf eine Seite aus gedrucktem Text gedruckt ist, und 1B ein
Beispiel des zweidimensionalen Strichcodes der '280-Anmeldung, 1A a diagram schematically illustrating the two-dimensional bar code of the '280 application printed on a page of printed text, and 1B an example of the two-dimensional bar code of the '280 application,
2 ein
Beispiel eines zweidimensionalen Strichcodes gemäß der vorliegenden Erfindung, 2 an example of a two-dimensional bar code according to the present invention,
3 ein
Flußdiagramm,
das die Schritte zum Codieren und Decodieren von Information auf
einem bedruckten Medium gemäß der vorliegenden
Erfindung zeigt, 3 a flow chart showing the steps for encoding and decoding information on a printed medium according to the present invention,
4 ein
zweidimensionaler Strichcode, der auf ein bedrucktes Medium mit
einem komplexen Hintergrund gedruckt ist, wobei eine Ruhezone um
den Strichcode herum vorgesehen ist, 4 a two-dimensional bar code printed on a printed medium with a complex background, with a quiet zone around the bar code;
5 ein
Flußdiagramm,
das beschreibt, wie der zweidimensionale Strichcode gemäß der vorliegenden
Erfindung zu lesen ist, 5 a flow chart describing how to read the two-dimensional bar code according to the present invention,
6 die
Auslegung des Schiebefensters, das als Teil des Auffindungsverfahrens
der vorliegenden Erfindung verwendet wird, 6 the design of the sliding window used as part of the discovery method of the present invention,
7A, 7B und 7C drei
alternative Ausführungsformen
von Suchmustern, die als Teil des Auffindungsverfahrens der vorliegenden
Erfindung verwendet werden, 7A . 7B and 7C three alternative embodiments of search patterns used as part of the discovery method of the present invention,
8 ein
Schaubild des Erkenners endlicher Zustände, der dazu verwendet wird,
Kantenpixel bei dem Verfahren zur Schrägstellungsabschätzung der
vorliegenden Erfindung zu detektieren, 8th 12 is a diagram of the finite state recognizer used to detect edge pixels in the skew estimation method of the present invention;
9A ist
ein Diagramm eines Verfahrens zur Schrägstellungswinkelabschätzung nach
dem Stand der Technik auf der Grundlage der Verwendung einer einzigen
Linie innerhalb der Kantenabbildung, und 9B ist
ein Diagramm des Wahlschemaverfahrens, das als Teil des Verfahrens
zur Schrägstellungswinkelabschätzung der
vorliegenden Erfindung verwendet wird. 9A FIG. 12 is a diagram of a prior art skew angle estimation method based on the use of a single line within the edge map, and FIG 9B Figure 4 is a diagram of the voting scheme method used as part of the skew angle estimation method of the present invention.
Wie
es in den US-Patenten Nr. 5 625 721 und Nr. 5 703 972 von Lopresti
et al, die beide mit "Certifiable Optical
Character Recognition" betitelt
sind, und in US-Patent Nr. 5 748 807, das mit "A Method and Means For Enhancing Optical
Character Recognition of Printed Documents" betitelt ist, deren Offenbarungsgehalte alle
hierin explizit durch Bezugnahme eingeschlossen sind, beschrieben
ist, kann Information über
Inhalte, Layout, Erzeugung und Wiederauffindung eines Dokuments
durch einen Compu ter codiert werden, wenn das Dokument zu Beginn
erzeugt wird oder bei einer anschließenden Computerverarbeitung
desselben. Die codierte Dokumentinformation kann dann über einen
zweidimensionalen Strichcode bereitgestellt werden, der auf der
Fläche
einer gedruckten Version des Dokuments erzeugt ist. Fortschrittliche
Codier- und Druckauflösungsfähigkeiten,
die gegenwärtig
verfügbar
sind, können
bis zu 30 000 Bits Information auf dem Raum von einem einzigen Quadratzoll
(645,16 mm2) aufnehmen. Deshalb kann man,
wie es durch die oben genannten Anmeldungen gelehrt wird, theoretisch
die gesamten Dokumentinhalte codieren, wobei dies nur durch die Menge
an Raum auf der Dokumentfläche
begrenzt ist, die man dem zweidimensionalen Strichcode zu opfern gewillt
ist. Ein Strichcodelesegerät
in Verbindung mit einem optischen Seitenscanner oder Seitenlesegerät oder vollständig getrennt
von diesem, kann den zweidimensionalen Strichcode abtasten und die
Information einem zugehörigen
System liefern, das mit der geeigneten Erkennungs- und Decodier-Software
ausgestattet ist. Die decodierte Information kann dann von dem Abtastsystem
dazu verwendet werden, eine neue Version des Dokuments zu schaffen
oder die Erkennung, Wiedergabe und Fehlerkorrektur für das gescannte
oder abgetastete Dokument zu verbessern. Um den zweidimensionalen
Strichcode zu decodieren, ist es nicht erforderlich, daß ein derartiges
Strichcodelesegerät-
und -abtastsystem die Druckauflösung
des zweidimensionalen Strichcodes kennt, vorausgesetzt, daß die Abtastauflösung des
Lesegeräts
in der Lage ist, mindestens eine 3 × 3-Pixelmatrix für jedes logische Bit des zweidimensionalen
Strichcodes für
die bevorzugte Ausführungsform des
unten in bezug auf 8 diskutierten Erkenners endlicher
Zustände
herzustellen.As described in U.S. Patent Nos. 5,625,721 and 5,703,972 to Lopresti et al, both of which are entitled "Certifiable Optical Character Recognition", and in U.S. Patent No. 5,748,807, which is entitled "A Method and Means for Enhanced Optical Character Recognition of Printed Documents, the disclosures of which are all expressly incorporated herein by reference, information about content, layout, creation and retrieval of a document may be encoded by a computer when the document is generated at the beginning or in a subsequent computer processing of the same. The encoded document information may then be provided via a two-dimensional bar code generated on the face of a printed version of the document. Advanced encoding and print resolution capabilities that are currently available can accommodate up to 30,000 bits of information in the space of a single square inch (645.16 mm 2 ). Therefore, as taught by the above-referenced applications, theoretically one can encode the entire document contents, limited only by the amount of space on the document surface that one is willing to sacrifice to the two-dimensional bar code. A barcode reader in conjunction with an optical page scanner or page reader or completely separate from it, can scan the two-dimensional bar code and provide the information to an associated system equipped with the appropriate recognition and decoding software. The decoded information may then be used by the scanning system to provide a new version of the document or to improve recognition, playback and error correction for the scanned or scanned document. In order to decode the two-dimensional bar code, such a bar code reader and scanner system is not required to know the print resolution of the two-dimensional bar code provided that the scan resolution of the reader is capable of having at least one 3x3 pixel matrix for each logical bit of the two-dimensional bar code for the preferred embodiment of FIG 8th discussed recognizer of finite states.
Die
in der Form eines zweidimensionalen Strichcodes codierte Information
kann dazu verwendet werden, die Software-Werkzeuge zu verbessern,
die bereits dazu verwendet werden,. Papierdokumente zu schaffen.
Beispiele umfassen Textverarbeitungs-, Tabellenkalkulations-, objektorientierte
Graphik- und Multimediaanwendungen, wie Sprachaufzeichnung und fotografische
Bildgebung.The
information coded in the form of a two-dimensional bar code
can be used to improve the software tools,
that are already being used. To create paper documents.
Examples include word processing, spreadsheet, object oriented
Graphic and multimedia applications, such as voice recording and photographic
Imaging.
Der
Rand 13, der bei dem zweidimensionalen Strichcode 10 von 1 verwendet
wird, war kein kritisches Merkmal der Erfindung, die in der '280-Anmeldung offenbart
ist, da der größte Teil
der darin beschriebenen Schlüsselverfahrensschritte
funktioniert, ob ein Rand vorhanden ist oder nicht. Jedoch wurde
der Rand 10 bei der '280-Anmeldung
von den Schritten der Schrägstellungsabschätzung und
der Schrägstellungsbeseitigung
verwendet.The edge 13 that with the two-dimensional barcode 10 from 1 was not a critical feature of the invention disclosed in the '280 application, since most of the key process steps described therein work whether or not there is an edge. However, the edge became 10 used in the '280 application of the steps of skew estimation and skew elimination.
2 veranschaulicht
ein Beispiel der zweidimensionalen Strichcodesymbologie, die bei
der '189-Anmeldung
eingeführt
wurde. Ein zweidimensionaler Strichcode 20 umfaßt einen
codierten Satz aus Datenbits in einem zweidimensionalen Gitter.
Typischerweise wird jedes Datenbit, das codiert ist, als eine Matrix
aus schwarzen oder weißen
Pixeln 23 gedruckt. Eine Pixelmatrix, die ein Datenbit
darstellt, ist quadratisch und kann so klein wie eine 1 × 1-Mätrix bis
so groß wie
eine 6 × 6-Matrix
oder größer sein.
Es können
auch nichtquadratische Matrizen verwendet werden. Es sind keine
Takte oder Ränder
bei der Symbologie für
den zweidimensionalen Strichcode 20 notwendig oder erforderlich.
Bei der bevorzugten Ausführungsform
ist der zweidimensionale Strichcode 20 ein 20 × 20-Array
aus Datenbits, wobei jedes Bit in einer 9 × 9-Pixelmatrix gespeichert
ist, obwohl festgestellt werden kann, daß die Größe flexibel ist, und daß die ein zige
Anforderung an die Größe ist,
daß der
Leseprozeß die
Größe des codierten
Arrays kennt. 2 Figure 3 illustrates an example of the two-dimensional bar code symbology introduced in the '189 application. A two-dimensional barcode 20 comprises a coded set of data bits in a two-dimensional grid. Typically, each data bit that is encoded will be considered a matrix of black or white pixels 23 printed. A pixel matrix representing a data bit is square and may be as small as a 1x1 maze to as large as a sixx6 matrix or larger. Non-square matrices may also be used. There are no bars or borders in the symbology for the two-dimensional barcode 20 necessary or necessary. In the preferred embodiment, the two-dimensional bar code is 20 a 20x20 array of data bits, each bit being stored in a 9x9 pixel matrix, although it can be determined that the size is flexible, and that the only requirement for size is that the read process be the size of the knows encoded arrays.
In
der '189-Anmeldung
sind zwei unterschiedliche Ausführungsformen
der Strichcode-Symbologie beschrieben. Bei der ersten Ausführungsform
sind die vier Eckenbits 21 immer schwarz (wenn auf einen
weißen Hintergrund
gedruckt wird). Die vier Eckenbits 21 bei der ersten Ausführungsform
werden "Ankerbits" genannt. Die restlichen
Datenbits bei der ersten Ausführungsform
der '189-Anmeldung
sind pseudo-stochastisiert (pseudorandomized) und können irgendeine
Kombination gewünschter
Information und Fehlerkorrekturbits enthalten. Die Symbologie der
ersten Ausführungsform
sorgt für
eine gute Schrägstellungsabschätzung, wenn die
Schrägstellung
klein ist und der zweidimensionale Strichcode 20 frei von
irgendeiner Beschädigung
ist. Jedoch macht die Plazierung der Ankerbits 21 in der
Ecke diese gegenüber
Beschädigung
anfällig.
Somit gibt es bei der in der '189-Anmeldung
beschriebenen zweiten Ausführungsform
keine Forderung nach Ankerbits 21, und der zweidimensionale
Strichcode 20 ist einfach ein N × M-Array aus Datenbits, vorzugsweise
mit N = M = 20, wobei in diesem Fall für die Speicherung von bis zu
50 Bytes (400 Bits) Information gesorgt wird. Bei der zweiten Ausführungsform
sind alle Datenbits pseudo-stochastisiert und können irgendeine Kombination
gewünschter
Informations- und Fehlerkorrekturbits enthalten. Vorzugsweise wird
ein herkömmlicher
(7, 4) Hamming-Code als der Fehlerkorrekturcode verwendet, um statistisches
Rauschen zu detektieren und zu korrigieren, wobei in diesem Fall
der zweidimensionale Strichcode bis zu 28 Bytes (224 Bits) Information
festhalten kann.The '189 application describes two different embodiments of bar code symbology. In the first embodiment, the four corner bits 21 always black (when printing on a white background). The four corner bits 21 in the first embodiment, "anchor bits" are called. The remaining data bits in the first embodiment of the '189 application are pseudorandomized and may contain some combination of desired information and error correction bits. The symbology of the first embodiment provides for good skew estimation when the skew is small and the two-dimensional bar code 20 is free of any damage. However, the placement of the anchor bits does 21 in the corner these vulnerable to damage. Thus, in the second embodiment described in the '189 application, there is no requirement for anchor bits 21 , and the two-dimensional barcode 20 is simply an N × M array of data bits, preferably with N = M = 20, in which case storage of up to 50 bytes (400 bits) of information is provided. In the second embodiment, all data bits are pseudo-stochastized and may contain any combination of desired information and error correction bits. Preferably, a conventional (7, 4) Hamming code is used as the error correction code to detect and correct statistical noise, in which case the two-dimensional bar code can hold up to 28 bytes (224 bits) of information.
3 veranschaulicht
die Schritte, die in dem Codier/Decodier-Prozeß enthalten sind. Mit der Ausnahme,
wie es hierin in bezug auf die Verfahren der vorliegenden Erfindung
beschrieben ist, ist jeder Schritt ausführlicher in der '280-Anmeldung und/oder
in der '189-Anmeldung
beschrieben. Während
des Codierprozesses werden zunächst
Eingangsdaten in der Form eines eindimensionalen, linearen Bitstroms
verarbeitet, um bei Schritt 30 einen normalen, auf Blöcken beruhenden
Fehlerkorrekturcode ("ECC") zu addieren, bei Schritt 31 stochastisiert,
bei Schritt 32 von einem eindimensionalen Bitstrom auf
eine zweidimensionale Darstellung, d.h., den zweidimensionalen Strichcode,
abgebildet, und der zweidimensionale Strichcode wird schließlich bei
Schritt 33 gedruckt. Der Decodierprozeß wiederholt diese Schritte
in umgekehrter Reihenfolge, wobei der gedruckte, zweidimensionale
Strichcode bei Schritt 34 gelesen wird, bei Schritt 35 aus
einer zweidimensionalen auf eine eindimensionale Darstellung abgebildet
wird, bei Schritt 36 entstochastisiert wird, und schließlich bei
Schritt 37 der ECC angewandt wird, um den "rohen" linearen Bitstrom
wiederherzustellen. Insbesondere werden die Verfahren der vorliegenden
Erfindung bei dem Leseschritt 34 verwendet. 3 illustrates the steps included in the encode / decode process. Except as described herein with respect to the methods of the present invention, each step is described in more detail in the '280 application and / or' 189 application. During the encoding process, input data is first processed in the form of a one-dimensional linear bit stream to be used at step 30 to add a normal block-based error correction code ("ECC") at step 31 stochastized, at step 32 from a one-dimensional bit stream to a two-dimensional representation, ie, the two-dimensional bar code, and the two-dimensional bar code finally becomes at step 33 printed. The decoding process repeats these steps in reverse order, with the printed two-dimensional barcode at step 34 is read at step 35 from a two-dimensional to a one-dimensional representation, at step 36 de-stochastized, and finally at step 37 the ECC is applied to restore the "raw" linear bit stream. in the special are the methods of the present invention in the reading step 34 used.
5 veranschaulicht
die Schritte bei dem Leseverfahrensschritt der vorliegenden Erfindung.
Zuerst wird die gescannte oder abgetastete Grauskalenabbildung durch
den Schwellenwertbildungsschritt 100 in schwarz und weiß umgewandelt,
wobei ein bestimmter Intensitätspegel
dynamisch ausgewählt
wird (z.B. der mittlere oder Medianwert-Pixelwert) und Pixel mit
einem Pegel gleich oder über
dem ausgewählten
Intensitätspegel
werden als schwarz (oder weiß)
angesehen, und Pixel mit einem Intensitätspegel, der kleiner als der ausgewählte Intensitätspegel
ist, werden als weiß (oder
schwarz) angesehen. Um den Prozeß zu beschleunigen, wird als nächstes wahlweise
die Auflösung
der gescannten oder abgetasteten Eingangsabbildung bei Schritt 102 reduziert,
wie es unten weiter diskutiert wird. Danach wird bei Schritt 104 durch
das Schiebefensterverfahren der vorliegenden Erfindung ein zweidimensionaler
Kandidatstrichcodebereich lokalisiert oder aufgefunden und aus der
Eingangsabbildung herausgezogen, wie es unten in bezug auf die 4, 6 und 7 weiter
diskutiert wird. Wenn bestimmt wird, daß ein Kandidatbereich einen
zweidimensionalen Strichcode umfaßt, wird der Kandidatbereich
bei Schritt 104 aus der ursprünglichen Abbildung herausgezogen
(mit der ursprünglichen
Auflösung).
Dann wird bei Schritt 106 der Schrägstellungswinkel des zweidimensionalen Strichcodes
innerhalb des Kandidatbereichs durch das Verfahren der vorliegenden
Erfindung abgeschätzt,
wie es mit Bezug auf die 8 und 9 hierin
weiter beschrieben wird. 5 illustrates the steps in the reading process step of the present invention. First, the scanned or scanned gray scale image is formed by the thresholding step 100 converted into black and white, with a certain intensity level being dynamically selected (eg, the median or median pixel value) and pixels having a level equal to or above the selected intensity level are considered black (or white) and pixels having an intensity level that is smaller when the selected intensity level is considered to be white (or black). To speed up the process, optionally, the resolution of the scanned or scanned input image is next step 102 reduced, as discussed further below. After that, at step 104 by the sliding window method of the present invention, a two-dimensional candidate bar code area is located or found and extracted from the input image as described below with respect to FIGS 4 . 6 and 7 will be discussed further. When it is determined that a candidate area includes a two-dimensional bar code, the candidate area at step 104 pulled out of the original image (with the original resolution). Then at step 106 the skew angle of the two-dimensional bar code within the candidate area is estimated by the method of the present invention as described with reference to FIGS 8th and 9 further described herein.
Sobald
der Schrägstellungswinkel
bekannt ist, wird er bei Schritt 108 wie notwendig korrigiert,
wie es in der '189-Anmeldung
ausführlicher
beschrieben ist. Wenn der Schrägstellungswinkel ϕ größer als
ein minimaler Schwellenwert α ist, über welchen
der Leseschritt 112 nicht länger in der Lage ist, den Strichcode
zuverlässig
zu lesen, jedoch unter einem zweiten Schwellenwert β, wird ein
einfaches Schrägstellungsbeseitigungsverfahren
angewandt. Wenn der Schrägstellungswinkel ϕ größer als
der zweite Schwellenwert β ist,
der typischerweise auf sieben Grad Schrägstellung festgelegt ist, wird
ein trigonometrischer Schrägstellungsbeseitigungsprozeß angewandt,
der mehr Verarbeitungszeit als das einfache Schrägstellungsbeseitigungsverfahren benötigt. Das
einfache Schrägstellungsbeseitigungsverfahren
wendet das Scher-Dreh-Verfahren an, und ist vollständig in
der '189-Anmeldung
in bezug auf die 16A, 16B und 16C darin offenbart. Das trigonometrische
Schrägstellungsbeseitigungsverfahren
ist auch vollständig
in der '189-Anmeldung
in bezug auf 17 darin beschrieben.Once the skew angle is known, it will be at step 108 corrected as necessary, as more fully described in the '189 application. If the skew angle φ is greater than a minimum threshold α over which the read step 112 is no longer able to reliably read the bar code, but below a second threshold β, a simple skew cancellation method is used. If the skew angle φ is greater than the second threshold β, which is typically set at seven degrees skew, then a trigonometric skew removal process is employed that requires more processing time than the simple skew sweep method. The simple skew-removal method uses the shear-twist method, and is fully described in the '189 application with respect to Figs 16A . 16B and 16C disclosed therein. The trigonometric skew-removal method is also fully described in the '189 application 17 described therein.
Der
Kandidatbereich wird wahlweise bei Schritt 110 zugeschnitten,
um eine enge Umgrenzung um den zweidimensionalen Strichcode herum
zu schaffen, wie es unten weiter beschrieben ist. Schließlich wird
die Information, die in dem zweidimensionalen Strichcode codiert
ist, bei Schritt 112 aus dem Kandidatbereich gelesen, wie
es in den '280-
und '189-Anmeldungen vollständig beschrieben
ist. Der Kandidatbereich kann sowohl bei dem Zuschneideschritt 110 als
auch dem Leseschritt 112 geprüft werden, um sicherzustellen,
daß er bestimmte
Charakteristiken des zweidimensionalen Strichcodes enthält, und
in dem Fall, daß der
Kandidatbereich derartige Charakteristiken nicht enthält, kann
die Verarbeitung zu dem Auffindungsschritt 104 zurückkommen,
um die Suche nach einem Kandidatbereich wiederaufzunehmen.The candidate area is optionally at step 110 tailored to provide a narrow boundary around the two-dimensional bar code, as further described below. Finally, the information encoded in the two-dimensional bar code is incremented 112 from the candidate area as fully described in the '280 and' 189 applications. The candidate area may be at both the trim step 110 as well as the reading step 112 to ensure that it contains certain characteristics of the two-dimensional bar code, and in the event that the candidate area does not contain such characteristics, the processing may proceed to the locating step 104 come back to resume the search for a candidate area.
Der
erste Schritt 102 des Leseprozesses verringert die Auflösung der
Abbildung um einen Faktor von vorzugsweise vier, um den Auffindungsschritt 104 zu
beschleunigen, obwohl ein Fachmann feststellen kann, daß die Auflösung der
Abbildung um andere Faktoren verringert werden kann, und, wenn die
Verarbeitungsgeschwindigkeit kein Thema ist, muß dieser Schritt überhaupt
nicht ausgeführt
werden. Die Eingangsabbildung wird vorzugsweise einfach unterabgetastet,
um eine Abbildung mit niedrigerer Auflösung zu schaffen. Die folgende
Gleichung beschreibt, wie eine Abbildung mit verringerter Auflösung aus
der ursprünglichen
Eingangsabbildung erzeugt werden kann: R (I,
J) = O (Reihe_Sprung * I, Spalte Sprung * J) (1) für: 0 ≤ I < Reihe_m/Reihe_Sprung 0 ≤ J < Spalte_m/Spalte_Sprungwobei
O(x, y) die ursprüngliche
Eingangsabbildung darstellt, R(x, y) die reduzierte Abbildung darstellt,
Reihe in und Spalte m jeweils die vertikale bzw. horizontale Größe des Eingangsabbildungs-Arrays
darstellen, und Reihe Sprung und Spalte Sprung jeweils Abtastfaktoren
in den vertikalen bzw. horizontalen Richtungen sind. Vorzugsweise
sind Reihe Sprung und Spalte Sprung beide gleich 4. Wie der Fachmann
feststellen kann, können
andere Verfahren zur Verringerung der Auflösung der Eingangsabbildung
das durch Gleichung (1) beschriebene, bevorzugte Verfahren ersetzen.The first step 102 of the reading process reduces the resolution of the image by a factor of preferably four, by the retrieval step 104 although one skilled in the art may find that resolution of the map can be reduced by other factors, and if processing speed is not an issue, this step need not be performed at all. The input image is preferably simply subsampled to provide a lower resolution image. The following equation describes how a reduced resolution map can be generated from the original input map: R (I, J) = O (row_step * I, column jump * J) (1) For: 0 ≤ I <row_m / row_step 0 ≤ J <column_m / column_step where O (x, y) represents the original input image, R (x, y) represents the reduced map, row in and column m respectively represent the vertical and horizontal sizes of the input mapping array, and row jump and column jump respectively sample factors into vertical or horizontal directions. Preferably, the series jump and column jump are both equal to 4. As those skilled in the art will appreciate, other methods for reducing the resolution of the input image may be as described by equation (1) written, replace preferred method.
Der
Auffindungsschritt 104 bestimmt den Ort des zweidimensionalen
Strichcodes innerhalb einer gegebenen Dokumentabbildung. Verfahren
nach dem Stand der Technik zur Auffindung umfassen ein einfaches Auffindungsschema
auf der Grundlage der Verteilung eines Histogramms der horizontalen
und vertikalen Projektion von Abbildungspixeln, wie es in der '28O-Anmeldung beschrieben
ist, und ein mathematisches, auf Morphologie beruhendes Schema,
das in der anhängigen
Patentanmeldung "Method
of Locating a Machine Readable Two Dimensional Barcode Within an
Image (amended)",
(Serial Nr. 08/822 347, am 17. März
1997 eingereicht) ("die '347-Anmeldung") beschrieben ist.
Das einfache Auffindungsschema der '280-Anmeldung ist ungeachtet des Ortes
des zweidimensionalen Strichcodes innerhalb einer Abbildung relativ
schnell, liefert jedoch keine optimalen Ergebnisse, wenn der zweidimensionale
Strichcode auf einen komplexen Hintergrund gedruckt ist, Einzellinienrauschen
umfaßt
oder einen Schrägstellungswinkel
aufweist, der größer als
fünf Grad ist.
Das auf Morphologie beruhende Auffindungsschema der '347-Anmeldung kann
mit Dokumenthintergründen
wie gedrucktem Text umgehen, kann jedoch nicht mit komplexen Hintergründen, wie
dem dunklen Hintergrund 220 von 4 umgehen
und ist im Hinblick auf die Verarbeitungsgeschwindigkeit nicht so
effektiv. Das unten beschriebene Verfahren der vorliegenden Erfindung
hat die günstigen
Eigenschaften der beiden Verfahren nach dem Stand der Technik und
ist in der Lage, den zweidimensionalen Strichcode aufzufinden, wenn
er auf ein Dokument gedruckt ist, das einen komplexen Hintergrund,
wie den dunklen Hintergrund 220 von 4, umfaßt.The discovery step 104 determines the location of the two-dimensional bar code within a given document image. Prior art methods of detection include a simple locating scheme based on the distribution of a histogram of horizontal and vertical projection of imaging pixels, as described in the '28O application, and a mathematical, morphological-based scheme described in U.S. Patent No. 5,308,347 in the copending patent application "Method of Locating a Machine Readable Two Dimensional Barcode Within an Image (amended)" (Serial No. 08 / 822,347 filed Mar. 17, 1997) ("the '347 application"). The simple discovery scheme of the '280 application is relatively fast regardless of the location of the two-dimensional bar code within an image, but does not provide optimal results if the two-dimensional bar code is printed on a complex background, includes single-line noise, or has a skew angle greater than five degrees is. The morphology-based retrieval scheme of the '347 application can handle document backgrounds such as printed text but can not handle complex backgrounds such as the dark background 220 from 4 handle and is not as effective in terms of processing speed. The method of the present invention described below has the favorable characteristics of the two prior art methods and is capable of finding the two-dimensional bar code when printed on a document having a complex background such as the dark background 220 from 4 , includes.
Nach 4 wird
nun beim Drucken eine Ruhezone 200 aus weißem Raum
explizit um den zweidimensionalen Strichcode 210 herum
geschaffen, um die Genauigkeit des Auffindungsprozesses zu verbessern, wenn
der zweidimensionale Strichcode 210 in einem bedruckten
Medium eingeschlossen ist, das komplexe Hintergründe, wie Hintergrund 220,
enthält.
Die Ruhezone 200 verbessert auch die Genauigkeit des Auffindungsprozesses
bei der Anwesenheit von Linienrauschen und Schrägstellung des zweidimensionalen
Strichcodes. Wie es in 1A gezeigt ist, ist, wenn der
zweidimensionale Strichcode in einer Ecke eines Dokuments außerhalb
der Grenzen angeordnet ist, in denen die Dokumentinhalte, wie Text
oder Graphiken, liegen, von Natur aus eine Fläche aus weißem Raum vorhanden. Jedoch
zeigt sich eine viel schwierigere Situation, wenn ein Dokument keine
derartigen Grenzen oder anderen Flächen aus weißem Raum
umfaßt.
Somit kann dadurch, daß explizit
die Anwesenheit einer Ruhezone 200 um den zweidimensionalen
Strichcode 210 herum erforderlich ist, der zweidimensionale
Strichcode 210 überall
auf einem Dokument mit einem komplexen Hintergrund plaziert sein,
wie es allgemein in 4 gezeigt ist, und dennoch durch
das Verfahren der vorliegenden Erfindung gelesen werden.To 4 will now be a quiet zone when printing 200 from white space explicitly around the two-dimensional barcode 210 created around to improve the accuracy of the retrieval process when the two-dimensional barcode 210 enclosed in a printed medium that has complex backgrounds, such as background 220 , contains. The quiet zone 200 also improves the accuracy of the detection process in the presence of line noise and skew of the two-dimensional bar code. As it is in 1A is shown, when the two-dimensional bar code is located in a corner of a document outside the boundaries in which the document contents, such as text or graphics lie, is inherently an area of white space. However, a much more difficult situation arises when a document does not include such boundaries or other areas of white space. Thus, by explicitly indicating the presence of a quiet zone 200 around the two-dimensional barcode 210 around, the two-dimensional barcode 210 be placed anywhere on a document with a complex background, as it is generally in 4 and yet be read by the method of the present invention.
Der
Auffindungsschritt 120 von 5 zieht
Nutzen aus der Tatsache, daß der
zweidimensionale Strichcode in der Mitte einer Ruhezone (weißer Bereich)
angeordnet ist, wobei die Kombination auf jede Art von Dokumenthintergrund
gedruckt werden kann. Deshalb ist der zweidimensionale Strichcode
von einem weißen
Randbereich umgeben, wie es in 4 gezeigt
ist. Wie ein Fachmann feststellen wird, erfordert die Ruhezone,
daß im
wesentlichen alle Pixel darin die gleiche Farbe aufweisen, jedoch
kann die besondere Farbe schwarz oder weiß sein (oder eine andere Farbe
im Fall eines Farbdokuments, die in dem Schwellenwertschritt 100 in
schwarz oder weiß umgewandelt
wird). Der Auffindungsschritt 120 muß ein gewisses Niveau an "Speckle"-Rauschen und Linienrauschen
gestatten; das in die Ruhezone beispielsweise während des Druckens oder Abtastens
bzw. Scannens eingeleitet wird. Der Auffindungsschritt 120 verwendet
das in 6 veranschaulichte Schiebefenster 300,
um einen zweidimensionalen Strichcode in der Eingangsabbildung aufzufinden.
Insbesondere wird das Schiebefenster 300 über die
Eingangsabbildung hinweg bewegt und wird an ausgewählten Positionen
dazu verwendet, den Teil der Abbildung innerhalb der Umgrenzungen
des Schiebefensters 300 herauszuziehen. Der herausgezogene
Teil der Abbildung wird dann geprüft, um zu bestimmen, ob ein
zweidimensionaler Strichcodekandidatbereich darin vorhanden ist,
wie es unten weiter diskutiert wird. Das Schiebefenster 300 weist
zwei Bereiche auf: (1) einen Kernbereich 310 und (2) einen
Ruhebereich 320. Der Kernbereich 310 entspricht
dem zweidimensionalen Strich code selbst, und der Ruhebereich 320 entspricht
der Ruhezone des zweidimensionalen Strichcodes. Die Größe der beiden
Bereiche ist hauptsächlich
durch die Spezifikation des zweidimensionalen Strichcodes, d.h.,
die Größe des zweidimensionalen
Strichcodes 210 und der Ruhezone 200, die in 4 gezeigt
sind; bestimmt. Da jedoch die Größe des rechteckigen
Fensters, die notwendig ist, um den zweidimensionalen Strichcode
zu enthalten, zunimmt, wenn der zweidimensionale Strichcode schräggestellt
ist, wie dies durch den schräggestellten,
zweidimensionalen Strichcode 330 in 6 gezeigt
ist, ist die Größe des Kernbereichs
des Schiebefensters 300 geringfügig größer als die erwartete Größe des zweidimensionalen
Strichcodes, um sich an Umstände
anzupassen, bei denen ein zweidimensionaler Strichcode bis zu einer
bestimmten maximalen Größe schräggestellt
ist. Zusätzlich
gestattet diese Eigenschaft auch, daß der zweidimensionale Strichcode
während
des Druck- und/oder Scanprozesses geringfügig vergrößert und dennoch durch das
Verfahren der vorliegenden Erfindung aufgefunden werden kann.The discovery step 120 from 5 takes advantage of the fact that the two-dimensional bar code is located in the center of a quiet zone (white area), which combination can be printed on any type of document background. Therefore, the two-dimensional bar code is surrounded by a white border area, as in 4 is shown. As one of ordinary skill in the art will appreciate, the quiet zone requires that substantially all pixels therein have the same color, however, the particular color may be black or white (or another color in the case of a color document that is in the threshold step 100 is converted into black or white). The discovery step 120 must allow a certain level of "speckle" noise and line noise; which is introduced into the quiet zone, for example during printing or scanning. The discovery step 120 uses that in 6 illustrated sliding windows 300 to find a two-dimensional bar code in the input image. In particular, the sliding window 300 moves past the input image and is used at selected positions to the part of the image within the boundaries of the sliding window 300 pull it out. The extracted portion of the image is then examined to determine if there is a two-dimensional bar code candidate area therein, as further discussed below. The sliding window 300 has two areas: (1) a core area 310 and (2) a rest area 320 , The core area 310 corresponds to the two-dimensional bar code itself, and the rest area 320 corresponds to the quiet zone of the two-dimensional barcode. The size of the two areas is mainly due to the specification of the two-dimensional bar code, ie, the size of the two-dimensional bar code 210 and the rest area 200 , in the 4 are shown; certainly. However, since the size of the rectangular window necessary to contain the two-dimensional bar code increases when the two-dimensional bar code is skewed, as by the skewed two-dimensional bar code 330 in 6 is the size of the core area of the sliding window 300 slightly larger than the expected size of the two-dimensional bar code to accommodate circumstances where a two-dimensional bar code is skewed to a certain maximum size. In addition, this feature also allows the two-dimensional bar code to be slightly increased during the printing and / or scanning process and yet be found by the method of the present invention.
Es
können
verschiedene Suchmuster für
das Schiebefenster 300 verwendet werden. Der Einfachheit halber
kann das Suchmuster von der oberen linken Ecke der Abbildung starten
und Reihe um Reihe von links nach rechts für jede Reihe abtasten, wie
es in 7A gezeigt ist, was leicht durchzuführen ist,
jedoch keinerlei a priori Wissen um den Ort des zweidimensionalen
Strichcodes innerhalb einer gegebenen Abbildung verwendet und deshalb
nicht das effektivste Suchverfahren sein kann.There can be different search patterns for the sliding window 300 be used. For simplicity, the search pattern may start from the top left corner of the image and scan row by row from left to right for each row, as shown in FIG 7A what is easy to do but does not use any a priori knowledge about the location of the two-dimensional bar code within a given map and therefore may not be the most effective search method.
In
der Praxis wird der zweidimensionale Strichcode gewöhnlich an
einen vordefinierten Ort innerhalb einer Seite gedruckt. Wenn decodiert
wird, braucht somit nur ein kleiner Teil der gesamten Dokumentabbildung durch
das Schiebefenster 300 abgetastet werden. Dieser kleine
Bereich wird gewöhnlich
durch die Abtastvorrichtung gemäß dem erwarteten
Ort des zweidimensionalen Strichcodes, z.B. in jeder Ecke des Dokuments, erhalten.
Sobald der kleine Bereich (oder Bereiche) herausgezogen sind, ist
es wahrscheinlicher, daß sich
der zweidimensionale Strichcode näher an der Mitte des herausgezogenen
kleinen Bereichs als an der Umgrenzung befinden wird. Das bevorzugte
Suchmuster startet von der Mitte des herausgezogenen kleinen Bereichs und
dehnt sich in einem spiralähnlichen
Muster nach außen
aus, wie es in 7B gezeigt ist, was es gestattet, daß der zweidimensionale
Strichcodekandidatbereich viel schneller aufgefunden wird, als durch
das einfache Verfahren, das in bezug auf 7A diskutiert
wurde. Jedoch kann die Implementierung dieses Suchverfahrens komplizierter
sein. Deshalb kann alternativ ein Suchmuster, das weniger kompliziert
als das Suchmuster von 7B durchzuführen jedoch schneller als das
Suchmuster von 7A ist, unter Verwendung eines Sprungreihensuchmusters
durchgeführt
werden, wie es in 7C veranschaulicht ist, das
reihenweise in dem herausgezogenen kleinen Bereich sucht. Wie es
in 7C gezeigt ist, startet das Sprungreihensuchmuster das
Suchen in der mittleren Reihe, springt dann von der mittleren Reihe
eine Reihe nach oben und eine Reihe nach unten, dann von der mittleren
Reihe zwei Reihen nach oben und zwei Reihen nach unten, wobei jede Reihe
durchsucht wird, bis ein zweidimensionaler Kandidatstrichcodebereich
gefunden wird oder das obere Ende und das untere Ende des herausgezogenen
kleinen Bereichs erreicht sind. Für jede Reihe sucht das Sprungreihensuchmuster
von links nach rechts. Obwohl es nicht so effektiv wie das spiralähnliche
Muster von 7B ist, ist es leichter durchzuführen.In practice, the two-dimensional bar code is usually printed to a predefined location within a page. Thus, when decoding, only a small portion of the entire document image needs to pass through the sliding window 300 be scanned. This small area is usually obtained by the scanning device according to the expected location of the two-dimensional bar code, eg in each corner of the document. Once the small area (or areas) are pulled out, it is more likely that the two-dimensional bar code will be closer to the center of the extracted small area than to the perimeter. The preferred search pattern starts from the center of the extracted small area and expands outward in a spiral-like pattern as shown in FIG 7B which allows the two-dimensional bar code candidate area to be found much faster than by the simple method described with respect to FIG 7A was discussed. However, the implementation of this search method can be more complicated. Therefore, alternatively, a search pattern that is less complicated than the search pattern of 7B however, perform faster than the search pattern of 7A is to be performed using a jump series search pattern as it is in 7C which searches in rows in the extracted small area. As it is in 7C 2, the jump row search pattern starts searching in the middle row, then jumps one row up and one row down from the middle row, then down two rows from the middle row and two rows down, searching each row, until a two-dimensional candidate bar code area is found or the top and bottom of the extracted small area are reached. For each row, the jump row search pattern searches from left to right. Although not as effective as the spiral-like pattern of 7B is, it is easier to perform.
Wenn
eine verbesserte Effektivität
notwendig ist, kann ferner jedes hierin diskutierte Suchmuster derart
modifiziert werden, daß es
durch Überspringen
einiger Abtastwege sucht, so daß nur
entlang der geradzahligen Wege gesucht wird, wie es in den 7A–7C gezeigt
ist.Further, if improved effectiveness is required, any search pattern discussed herein may be modified to seek by skipping some scan paths so that only the even-numbered paths are searched for, as shown in FIGS 7A - 7C is shown.
Wenn
das Schiebefenster jeden Ort passiert, wird der Abbildungsbereich
innerhalb des Schiebefensters 300 geprüft, um zu sehen, ob er bestimmte
Charakteristiken des zweidimensionalen Strichcodes enthält. Wie
es oben angedeutet wurde, sind die Bits in dem zweidimensionalen
Strichcode stochastisiert und enthalten eine gleichmäßige Verteilung
von Bits. Zusätzlich
ist die annähernde
Größe des zweidimensionalen
Strichcodes bekannt, und der zweidimensionale Strichcode ist von
einer Ruhezone aus weißem
Raum umgeben. Das Auffindungsverfahren der vorliegenden Erfindung
prüft den
Abbildungsbereich bei jedem Schritt, um zu bestimmen, ob er diese
Merkmale enthält,
und somit zu bestimmen, ob der Abbildungsbereich als ein zweidimensionaler
Strichcodekandidatbereich ausgewählt
werden sollte.When the sliding window passes each location, the imaging area becomes within the sliding window 300 checked to see if it contains certain characteristics of the two-dimensional bar code. As indicated above, the bits in the two-dimensional bar code are stochastized and contain a uniform distribution of bits. In addition, the approximate size of the two-dimensional bar code is known, and the two-dimensional bar code is surrounded by a quiet zone of white space. The retrieval method of the present invention examines the mapping area at each step to determine if it contains those features, and thus to determine whether the mapping area should be selected as a two-dimensional bar code candidate area.
Als
eine erste Prüfung
an jeder Position wird der Kernbereichsdichtewert der Abbildung
innerhalb des Kernbereichs 310 des Schiebefensters 300 geprüft, um zu
bestimmen, ob er in einen vorbestimmten Bereich fällt. Weil
die Bits innerhalb des zweidimensionalen Strichcodes wegen des Stochastisierungsprozesses
(randomization process) in einem gleichmäßigen Muster verteilt sind,
wird insbesondere ein perfekt gleichmäßiger, zweidimensionaler Strichcode
eine gleiche Anzahl von schwarzen Pixeln und weißen Pixeln aufweisen. Die "Kernbereichsdichte" ist als das Verhältnis der
Anzahl von schwarzen Pixeln zur Gesamtzahl von Pixeln innerhalb
des Kernbereichs 310 des Abtastfensters 300 definiert.
Weil der oben disku tierte Binärisierungsprozeß (binarisation
process) der Abtastvorrichtung oder des Schwellenwertschrittes 100 bewirken
kann, daß der zweidimensionale
Strichcodebereich zu dunkel oder zu hell ist, kann die Kernbereichsdichte
geringfügig
auf einem Niveau schwanken, das etwas niedriger oder höher als
0,5 ist. Deshalb kann der Kernbereichsdichtewert in einem vorherbestimmten
Bereich um 0,5 herum liegen. Wenn der zu decodierende, zweidimensionale Strichcode
einen Rand umfaßt,
müssen
zusätzlich
der Schwellenwert und der Bereich der Kernbereichsdichte entsprechend
eingestellt werden, um den zusätzlichen
schwarzen Pixeln Rechnung zu tragen, die aufgrund des schwarzen
Randes vorhanden sind (falls z.B. der Schwellenwert 0,5 beträgt und der
Bereich 0,45 bis 0,55 beträgt,
wenn kein schwarzer Rand vorhanden ist, kann der Schwellenwert 0,55
betragen und der Bereich ist 0,50 bis 0,60, wenn ein schwarzer Rand
vorhanden ist). Wenn herausgefunden wird, daß der Kernbereich eine Kernbereichsdichte
aufweist, die die Anwesenheit eines zweidimensionalen Strichcodes
anzeigt, fährt
die Prüfung
fort, sonst wird das Schiebefenster in seine nächste Position bewegt, um die
Kernbereichsdichte zu bewerten.As a first check at each position, the core area density value of the map becomes within the core area 310 of the sliding window 300 checked to determine if it falls within a predetermined range. In particular, because the bits within the two-dimensional bar code are distributed in a uniform pattern because of the stochastization process, a perfectly uniform, two-dimensional bar code will have an equal number of black pixels and white pixels. The "core area density" is defined as the ratio of the number of black pixels to the total number of pixels within the core area 310 of the sampling window 300 Are defined. Because the above-discussed binaryization process (binarization process) of the scanner or threshold step 100 can cause the two-dimensional bar code area to be too dark or too bright, the core area density may slightly fluctuate to a level slightly lower or higher than 0.5. Therefore, the core area density value may be in a predetermined range around 0.5. In addition, if the two-dimensional bar code to be decoded comprises an edge, then the threshold and range of core area density must be adjusted accordingly to account for the extra black pixels present due to the black border (eg, if the threshold is 0.5 and the range is 0.45 to 0.55, if there is no black border, the threshold may be 0.55 and the area is 0.50 to 0.60 if there is a black border). If it is found that the core area has a core area density indicating the presence of a two-dimensional bar code, the test continues, otherwise the sliding window is moved to its next position to evaluate the core area density.
Als
eine zweite Prüfung
an jeder Position wird die Ruhebereichsdichte des Bereichs innerhalb
des Ruhebereichs 320 des Schiebefensters 300 bewertet,
um zu bestimmen, ob sie in einen vorherbestimmten Bereich fällt. Die
Ruhebereichsdichte ist als das Verhältnis der Anzahl von schwarzen
Pixeln zur Gesamtzahl von Pixeln innerhalb des Ruhebereichs 320 des
Schiebefensters 300 definiert. Wie es in 4 gezeigt
ist, enthält die
Ruhezone 200 idealerweise keine schwarzen Pixel, und somit
würde ein
perfekt abgetasteter, zweidimensionaler Strichcode ohne irgendein
Rauschen (d.h, schwarze Pixel) innerhalb der Ruhezone 200 einen
Ruhebereichsdichtewert von Null ergeben. Um etwas Speckle-Rauschen
oder Rauschen einer einzelnen gezogenen Linie Rechnung zu tragen,
wird im voraus ein Maximaldichtewert, der etwas größer als
Null ist, als ein annehmbarer Wert ausgewählt. Der Ruhebereichsdichtewert
für den
Teil der Abbildung in der Ruhezone 320 des Schiebefensters 300 wird
bewertet, und wenn herausgefunden wird, daß er kleiner oder gleich dem
im voraus ausgewählten
Wert ist, fährt
die Prüfung
fort, sonst wird das Schiebefenster in seine nächste Position bewegt, um die
Kernbereichsdichte zu bewerten.As a second test at each position, the quiet area density of the area becomes within the rest area 320 of the sliding window 300 to determine if it falls within a predetermined range. The quiet area density is defined as the ratio of the number of black pixels to the total number of pixels within the quiet area 320 of the sliding window 300 Are defined. As it is in 4 shown contains the rest zone 200 ideally no black pixels, and thus a perfectly scanned, two-dimensional bar code would be without any noise (ie, black pixels) within the quiet zone 200 give a quiescent density value of zero. To account for some speckle noise or noise of a single drawn line, a maximum density value slightly greater than zero is selected in advance as an acceptable value. The resting area density value for the part of the picture in the quiet zone 320 of the sliding window 300 is evaluated, and if it is found to be less than or equal to the preselected value, the test continues, otherwise the sliding window is moved to its next position to evaluate the core area density.
Als
eine abschließende
Prüfung
wird ferner eine Zusehneideprüfung
durchgeführt,
wenn ein Abbildungsbereich innerhalb eines Abtastfensters in die
annehmbaren Bereiche für
sowohl die Kernbereichsdichte als auch die Ruhebereichsdichte fällt, um
die Gültigkeit
jedes Bereichs zu prüfen.
Der Zuschneideschritt der vorliegenden Erfindung beruht auf der
Tatsache, daß die
Bits in dem zweidimensionalen Strichcode gleichmäßig verteilt sind. Somit wird
in einem Array aus 20 × 20
Bits keine Reihe oder Spalte in dem Kandidatbereich vorhanden sein,
die nicht irgendwelche schwarzen Bits enthält. Das Zuschneiden wird von
der Mitte zur Außenseite
hin vorgenommen. Von der Mitte des Kandidatbereichs ausgehend wird
jede Abbildungsreihe fortlaufend von der Mitte zum oberen Ende des
Kandidatbereichs abgetastet, bis eine Reihe erreicht ist, die keine schwarzen
Pixel enthält,
wobei man annimmt, daß dies
dort ist, wo die obere Kante des zweidimensionalen Strichcodes liegt.
Der Abtastprozeß wird
weitere drei Male wiederholt, wobei die Reihenabtastung von der
Mitte nach unten zum unteren Ende des Kandidatbereichs und die Spaltenabtastung
dann von der Mitte zu der am weitesten links liegenden Spalte des
Kandidatbereichs und schließlich
von der Mitte zu der am weitesten rechts liegenden Spalte des Kandidatbereichs
fortschreitet. Anstelle daß eine
einzige Reihe die Kante des zweidimensionalen Strichcodes kenn zeichnet,
können
die jeweiligen Umgrenzungen des zweidimensionalen Strichcodes durch
die Anwesenheit einer vorherbestimmten, aufeinanderfolgenden Anzahl
von Reihen oder Spalten gekennzeichnet sein, die kein Schwarz enthalten,
um Abtastzeilenrauschen von dem Abtastprozeß oder einer zu hellen Abbildung
Rechnung zu tragen.When
a final one
exam
will also be a visual inspection
carried out,
if an imaging area within a sampling window in the
acceptable areas for
both the core area density and the quiescent area density fall to
the validity
every area to test.
The trimming step of the present invention is based on
Fact that the
Bits are evenly distributed in the two-dimensional bar code. Thus, will
in an array of 20 × 20
Bits no row or column will be present in the candidate area
that does not contain any black bits. The cropping is done by
the middle to the outside
made. Starting from the middle of the candidate area
each series of images running continuously from the middle to the upper end of the
Scanned candidate range until a number is reached that no black
Contains pixels,
assuming that this
where is the top edge of the two-dimensional barcode.
The scanning process becomes
repeated three more times, the serial scan of the
Center down to the bottom of the candidate area and the column scan
then from the middle to the leftmost column of the
Candidate area and finally
from the center to the rightmost column of the candidate area
progresses. Instead of one
single row marks the edge of the two-dimensional bar code,
can
the respective boundaries of the two-dimensional bar code
the presence of a predetermined, consecutive number
be marked by rows or columns that do not contain black,
scan line noise from the scan process or too bright a picture
Take into account.
Nachdem
der Kandidatbereich zugeschnitten worden ist, wird die Größe des neuen
Bereichs gegen die erwartete Größe des zweidimensionalen
Strichcodes geprüft.
Wenn eine wesentlich unterschiedliche Größe gefunden wird, kennzeichnet
dies, daß der
Kandidatbereich kein zweidimensionaler Strichcodebereich ist, und
das Schiebefenster wird in seine nächste Position bewegt, um die
Kernbereichsdichte zu bewerten. Das Prüfen der Größe nach dem Zuschneideprozeß bewirkt
die Beseitigung gewisser Bereiche, die von den ersten beiden Prüfungen falsch
detektiert worden sein können.
Beispielsweise kann ein Textbereich die Dichteprüfung bestehen, wenn er einen
Font mit einer Größe umfaßt, die
der Größe jedes
Bits innerhalb des zweidimensionalen Strichcodes ähnlich ist
und einen bestimmten Zeilenabstand und Zeichenabstand aufweist.
Jedoch wird ein Zuschneiden eines Textbereichs gewöhnlich mit
einem einzigen Bereich eines verbundenen Bestandteils, z.B. einem
Zeichen, enden, der eine Größe aufweisen
wird, die sich wesentlich von derjenigen unterscheidet, die für den zweidimensionalen
Strichcode erwartet wird.After this
The candidate area has been tailored to the size of the new one
Area against the expected size of the two-dimensional
Barcodes checked.
If a significantly different size is found, marks
this, that the
Candidate area is not a two-dimensional bar code area, and
the sliding window is moved to its next position to the
To assess core area density. Checking the size after the trimming process causes
the elimination of certain areas wrong from the first two exams
may have been detected.
For example, a text area may pass the density check if it has a
Font with a size that includes
the size of each
Bits within the two-dimensional barcode is similar
and has a certain line spacing and character spacing.
However, cropping a text area is usually done with
a single area of a connected component, e.g. one
Characters ending with a size
which differs materially from that which for the two-dimensional
Bar code is expected.
Sobald
herausgefunden wird, daß ein
Kandidatbereich alle drei Prüfungen
erfüllt,
wird er als ein gültiger
Kandidatbereich angesehen. Der gegenwärtige Ort innerhalb der Abbildung
des Schiebefensters wird aufgezeichnet und auf die Abbildung mit
voller Auflösung
abgebildet, und der entsprechende Bereich wird als ein Kandidatbereich
zur weiteren Verarbeitung herausgezogen. Wenn ein zweidimensionaler
Strichcode innerhalb des Schiebefensters einen relativ großen Schrägstellungswinkel
aufweist, können
dessen Ecken außerhalb der
Umgrenzungen des Kernbereichs 310 des Schiebefensters 300 verblieben
sein. Die Ecken können
wiedergefunden werden, indem die Größe des Kernbereichs 310 geringfügig ausgedehnt
wird, wenn der Kandidatbereich aus der Abbildung mit voller Auflösung herausgezogen
wird, um sicherzustellen, daß der
gesamte zweidimensionale Strichcode herausgezogen ist. Jegliches
Rauschen, das in dem herausgezogenen Bereich wegen der Ausdehnung
der Fenstergröße geschaffen
wird, kann bei dem Zuschneideschritt 110 beseitigt werden,
der die gleiche Zuschneideverfahrensweise von innen nach außen verwendet,
die oben in bezug auf den Auffindungsschritt 104 beschrieben
wurde.Once a candidate area is found to satisfy all three exams, it is considered a valid candidate area. The current location within the map of the sliding window is recorded and mapped to the full resolution map, and the corresponding area is extracted as a candidate area for further processing. When a two-dimensional bar code within the sliding window has a relatively large skew angle, its corners may be outside the boundaries of the core area 310 of the sliding window 300 be left. The corners can be recovered by changing the size of the core area 310 is slightly extended when the candidate area is extracted from the full resolution map to ensure that the entire two-dimensional bar code is extracted. Any noise created in the extracted area due to the expansion of the window size may occur during the trimming step 110 which uses the same inside-out trimming procedure above with respect to the retrieval step 104 has been described.
Ungleich
den Auffindungsverfahren, die in den '280- und '189-Anmeldungen beschrieben sind, schneidet
das Verfahren der vorliegenden Erfindung den aufgefundenen Kandidatbereich
vor der Schrägstellungsbeseitigung
nicht zu, weil das Zuschneiden eines schräggestellten, zweidimensionalen
Strichcodes leicht seine Ecken beschädigen kann, wohingegen das
Zuschneiden eines zweidimensionalen Strichcodes, dessen Schrägstellung
richtig beseitigt ist, seine Ecken bewahren wird.Unlike the retrieval methods described in the '280 and' 189 applications, the method of the present invention does not intersect the found candidate area prior to skew elimination, because cropping a skewed two-dimensional bar code can easily damage its corners, whereas cropping a two-dimensional barcode whose Tilting is properly eliminated, its corners will be preserved.
Das
Verfahren zur Schrägstellungsabschätzung der '280-Anmeldung beruht
auf der Auffindung von zwei Ankerbits an der oberen linken und der
unteren linken Ecke des zweidimensionalen Strichcodes, um den Schrägstellungswinkel
zu berechnen. Wie es darin weiter diskutiert wird, werden Vorlagen
dazu verwendet, die Ecken aufzufinden, und dieses Verfahren versagt,
wenn der Schrägstellungswinkel
relativ groß,
wie größer als annähernd fünf Grad
Schrägstellung
ist. Zusätzlich
sind die Ecken des zwei dimensionalen Strichcodes oft durch Rauschen
verformt, was zu einem ungenauen Wert für den durch das Verfahren der '280-Anmeldung abgeschätzten Schrägstellungswinkel
führt.The
Pitch estimation method of the '280 application
on the finding of two anchor bits on the upper left and the
bottom left corner of the two-dimensional bar code to the skew angle
to calculate. As will be discussed further in this, become templates
used to find the corners, and this method fails
if the skew angle
relatively large,
how larger than approximately five degrees
inclination
is. additionally
The corners of the two dimensional bar code are often noise
deformed, resulting in an inaccurate value for the skew angle estimated by the method of the '280 application
leads.
Um
diese Mängel
zu beheben, offenbart die '189-Anmeldung
eine Schrägstellungsabschätztechnik
auf der Grundlage einer Hough-Transformation. Die Hough-Transformation
ist eine parametrische Transformation, die dazu verwendet werden
kann, geometrische Merkmale, wie gerade Linien, innerhalb einer
Abbildung zu detektieren. Das Verfahren der '189-Anmeldung zieht alle horizontalen
Kantenpixel unter Verwendung einer vertikalen Schwarz- und Weiß-Maske über die
gesamte Abbildung hinweg heraus. Dann wird die Hough-Transformation
mit allen identifizierten horizontalen Kantenpixeln durchgeführt, um
den Winkel der längsten
Kantenlinie zu berechnen, der den Schrägstellungswinkel des zweidimensionalen
Strichcodes darstellt. Dieses Verfahren erfordert eine bedeutende
Verarbeitungszeitdauer, weil eine Bewegen einer vertikalen Maske über die
gesamte Abbildung hinweg, um jedes Kantenpixel zu detektieren, umfaßt, daß auf jedes
Abbildungspixel mehrere Male zugegriffen wird (die tatsächliche
Anzahl von Zugriffen hängt
von der Größe der Maske
ab), und weil das Hough-Transformationsverfahren eine breite Vielfalt
von möglichen
Winkeln in 0,5-Grad-Inkrementen für alle Kantenpixel prüft, um den
Winkel der längsten
Kantenlinie zu bestimmen. Weil der durch die Hough-Transformation bestimmte
Winkel dem Winkel der Linie entspricht, die die größte Anzahl von
Pixeln enthält,
wird zusätzlich
der Schrägstellungswinkel
nicht genau bestimmt, wenn Rauschen einer gezogenen Linie über den
zweidimensionalen Strichcode hinweg vorhanden ist. Dies ist der
Fall, weil die Rauschlinie die dominante Linie unter allen Kantenlinien
sein wird, was bewirkt, daß der
Verfahrensschritt zu Schrägstellungsabschätzung den
Winkel gemäß dem Linienrauschen
berechnet. Die Auswirkung einer gezogenen Linie ist in 9A veranschaulicht,
wobei Linie 400 entlang des unteren Endes des zweidimensionalen Strichcodes 410 gezogen
ist. Weil die dominante Linie 430 in der horizontalen Kantenabbildung 420 die
dominante Linie ist, wird das Verfahren zur Schrägstellungswinkelabschätzung der '189-Anmeldung den
Schrägstellungswinkel
falsch als 0,5 Grad berechnen.To remedy these deficiencies, the '189 application discloses a skew estimation technique based on a Hough transform. The Hough transform is a parametric transformation that can be used to detect geometric features, such as straight lines, within an image. The method of the '189 application extracts all horizontal edge pixels across the entire image using a vertical black and white mask. Then, the Hough transform is performed with all the identified horizontal edge pixels to calculate the angle of the longest edge line representing the skew angle of the two-dimensional bar code. This method requires significant processing time since moving a vertical mask across the entire image to detect each edge pixel involves accessing each imaging pixel several times (the actual number of accesses depends on the size of the mask), and because the Hough transform method examines a wide variety of possible angles in 0.5 degree increments for all edge pixels to determine the angle of the longest edge line. In addition, because the angle determined by the Hough transform corresponds to the angle of the line containing the largest number of pixels, the skew angle is not accurately determined when there is noise of a ruled line across the two-dimensional bar code. This is because the noise line will be the dominant line under all edge lines, causing the skew estimation step to calculate the angle according to the line noise. The effect of a drawn line is in 9A illustrates where line 400 along the lower end of the two-dimensional bar code 410 is drawn. Because the dominant line 430 in the horizontal edge illustration 420 is the dominant line, the skew angle estimation method of the '189 application will incorrectly calculate the skew angle as 0.5 degrees.
Das
Verfahren zur Schrägstellungsabschätzung der
vorliegenden Erfindung beruht auch auf dem Hough-Transformationsverfahren
mit zwei wesentlichen Änderungen,
um das Verfahren praktischer und zuverlässiger zu gestalten. Zuerst
wird ein Erkenner endlicher Zustände
dazu verwendet, die Kantenpixel des zweidimensionalen Strichcodes
in einem einzigen Durchgang zu detektieren, anstelle der vertikalen
Maske, die bei der '189-Anmeldung verwendet
wird. Da die Schwarz-Weiß-
und Weiß-Schwarz-Übergänge innerhalb des Kandidatbereichs
Kanten in den logischen Reihen und Spalten zugeordnet sind, wird
ein gültiger Übergang
durch eine spezifizierte Anzahl von aufeinanderfolgenden schwarzen
Pixeln gefolgt durch eine spezifizierte Anzahl von aufeinanderfolgenden
weißen
Pixeln (oder umgekehrt) durch einen zusätzlichen Erkenner endlicher
Zustände
bestimmt, der in 8 in Diagrammform gezeigt ist.
Dieses Verfahren ist effizienter, weil es nur einmal auf jedes Abbildungspixel
zugreift, und kann dazu verwendet werden, entweder horizontale oder vertikale
Kanten oder beide zu detektieren. Zusätzlich erfordert der Erkenner
endlicher Zustände
nicht, daß der
zweidimensionale Strichcode überhaupt
irgendwelche Ankerbits umfaßt,
was das Verfahren zur Schrägstellungsabschätzung der
vorliegenden Erfindung bei der Anwesenheit einer geringfügigen Verformung
irgendeiner Ecke des abgetasteten, zweidimensionalen Strichcodes
robuster macht.The skew estimation method of the present invention is also based on the Hough transform method with two major changes to make the method more practical and reliable. First, a finite state recognizer is used to detect the edge pixels of the two-dimensional bar code in a single pass, rather than the vertical mask used in the '189 application. Since the black and white and white and black transitions within the candidate area are assigned edges in the logical rows and columns, a valid transition is made by a specified number of consecutive black pixels followed by a specified number of consecutive white pixels (or vice versa). determined by an additional recognizer of finite states, which in 8th shown in diagram form. This method is more efficient because it accesses each imaging pixel only once, and can be used to detect either horizontal or vertical edges, or both. In addition, the finite state recognizer does not require the two-dimensional bar code to include any anchor bits at all, making the skew estimation method of the present invention more robust in the presence of slight deformation of any corner of the scanned two-dimensional bar code.
Insbesondere überprüft der Erkenner
endlicher Zustände
nacheinander jedes Pixel in jeder Reihe (oder Spalte), um vertikale
(oder horizontale) Kanten zu finden. Ein Kantentransistor oder -übergang
ist als eine erste Abfolge von mindestens N Pixeln in einer ersten
Farbe gefolgt durch eine zweite Abfolge von mindestens N Pixeln
in der entgegengesetzten Farbe definiert. Die Position des schwarzen
Pixels, die den Kantenübergang
bewirkt, wird als der Ort der Kante verwendet. In einer Reihe, die
beispielsweise aus vier aufeinanderfolgenden weißen Pixeln gefolgt von vier
aufeinanderfolgenden schwarzen Pixeln und weiter gefolgt von drei
aufeinanderfolgenden weißen
Pixeln besteht, werden somit nur die fünf Pixel in der Reihe als ein
Kantenübergang
bezeichnet, wenn N = 4. Wenn jedoch in dem gleichen Beispiel N =
3, werden die fünften
und die achten Pixel als Kantenübergänge (Kanten)
bezeichnet.In particular, the recognizer checks
finite states
successively each pixel in each row (or column) to vertical
(or horizontal) edges to find. An edge transistor or junction
is a first sequence of at least N pixels in a first
Color followed by a second sequence of at least N pixels
defined in the opposite color. The position of the black one
Pixels representing the edge transition
is used as the location of the edge. In a row, the
for example, four consecutive white pixels followed by four
consecutive black pixels and further followed by three
successive white
Pixels, only the five pixels in the row become one
Edge transition
when N = 4. However, in the same example, if N =
3, become the fifth
and the eighth pixels as edge transitions (edges)
designated.
Im
Zustandsdiagramm von 8 ist ein Erkenner endlicher
Zustände,
der eine Maschine für
bedingte Zustände
ist, gezeigt, der für
N gleich oder größer als
3 arbeitet. In 8 beziehen sich die Bezeichnungen "B" und "W" auf
die Farbe (d.h., schwarz oder weiß) des Pixels an der besonderen
Position innerhalb der verarbeiteten Reihe oder Spalte. Somit geht
in einem Anfangszustand 500, wenn die Farbe des ersten
Pixels schwarz ist, der Prozeß von
Zustand 500 zu Zustand 501 über. Wenn die Farbe des ersten
Pixels weiß ist,
geht statt dessen der Prozeß von
Zustand 500 zu Zustand 502 über. Die Verarbeitung fährt durch
die Zustandsmaschine weiter fort, wie es weiter unten diskutiert
wird, bis ein spezielles Zeichen erreicht ist, das das Ende der besonderen
verarbeiteten Reihe oder Spalte angibt, an welchem Punkt die nächste Reihe
oder Spalte vom Anfangszustand 500 verarbeitet wird. Bei
jedem Zustand über
Zustand 500 hinaus, wird ein Positionsindex I inkrementiert,
um die Position des Pixels zu verfolgen, das innerhalb der besonderen
Reihe oder Spalte untersucht wird. Zusätzlich werden bestimmte andere
Arbeitsgänge
bei verschiedenen Zuständen
durchgeführt,
wie dies in Tabelle 1 angegeben und unten weiter beschrieben ist.In the state diagram of 8th is a finite state recognizer, which is a conditional state machine, which operates for N equal to or greater than 3. In 8th The terms "B" and "W" refer to the color (ie, black or white) of the pixel at the particular position within the ver worked row or column. Thus, in an initial state 500 if the color of the first pixel is black, the process of state 500 to state 501 above. If the color of the first pixel is white, then the process goes from state to state 500 to state 502 above. Processing continues through the state machine, as will be discussed below, until a special character is reached indicating the end of the particular processed row or column, at which point the next row or column is from the initial state 500 is processed. At every state about condition 500 In addition, a position index I is incremented to keep track of the position of the pixel being examined within the particular row or column. In addition, certain other operations are performed at different states as indicated in Table 1 and further described below.
Tabelle
1 Table 1
Wenn
bei Zustand 501 die Farbe des nächsten Pixels schwarz ist,
geht die Verarbeitung zu Zustand 503 über, wohingegen, wenn die Farbe
des nächsten
Pixels weiß ist,
die Verarbeitung zu Zustand 502 übergeht. Wenn ebenso bei Zustand 502 die
Farbe des nächsten
Pixels weiß ist,
geht die Verarbeitung zu Zustand 504 über, wohingegen, wenn die Farbe
des nächsten
Pixels schwarz ist, die Verarbeitung zu Zustand 501 übergeht.If at state 501 the color of the next pixel is black, the processing goes to state 503 whereas, when the color of the next pixel is white, the processing becomes state 502 passes. If also at state 502 the color of the next pixel is white, the processing goes to state 504 whereas, when the color of the next pixel is black, the processing becomes state 501 passes.
Wie
es in Tabelle 1 angegeben ist, ist bei den Zuständen 501 und 502 die
Anzahl von aufeinanderfolgenden Pixeln, denen begegnet wird, auf
2 festgesetzt (für
zwei aufeinanderfolgende schwarze Pixel bei Zustand 501 und
zwei aufeinanderfolgende weiße
Pixel bei Zustand 502). Vom Zustand 501 aus geht
die Verarbeitung zu Zustand 503 über, wenn das nächste Pixel
schwarz ist, und zu Zustand 502, wenn das nächste Pixel weiß ist. Bei
Zustand 503 fährt
die Verarbeitung bei Zustand 503 fort, solange jedes folgende
Pixel, dem begegnet wird, schwarz ist und die Anzahl der Pixel kleiner
als N bleibt. Jedesmal, wenn Zustand 503 durchlaufen wird,
wird der Pixelzählwert,
d.h., #Pixel in Tabelle 1, inkrementiert. Wenn das N-te aufeinanderfolgende schwarze
Pixel erreicht wird, geht die Verarbeitung zu Zustand 505 über. Wenn
einem weißen
Pixel vor N aufeinanderfolgenden schwarzen Pixeln begegnet wird,
geht die Verarbeitung zu Zustand 502 über. Die Verarbeitung durchläuft die
Zustände 502, 504 und 506 auf
analoge Weise, wenn zuerst einer Reihe von weißen Pixeln begegnet wird, wobei
die Pixelfarben umgekehrt sind. As indicated in Table 1, the states are 501 and 502 the number of consecutive pixels encountered is set to 2 (for two consecutive black pixels at state 501 and two consecutive white pixels at state 502 ). From the state 501 off the processing goes to state 503 over if the next pixel is black and to state 502 if the next pixel is white. At state 503 the processing continues with state 503 as long as each successive pixel encountered is black and the number of pixels remains smaller than N. Every time when condition 503 is traversed, the pixel count, ie, #Pixel in Table 1, is incremented. When the Nth consecutive black pixel is reached, the processing goes to state 505 above. When a white pixel is encountered in front of N consecutive black pixels, the processing goes to state 502 above. The processing goes through the states 502 . 504 and 506 in an analogous way, when first encounters a series of white pixels, with the pixel colors reversed.
Bei
Zustand 505 fährt
die Verarbeitung bei Zustand 505 für jedes folgende schwarze Pixel
fort, wobei der Pixelzählwert
für jeden
Durchlauf inkrementiert wird und tatsächlich nach dem letzten schwarzen
Pixel in der gegenwärtigen
Abfolge gesucht wird. Wenn bei Zustand 505 einem weißen Pixel
begegnet wird, geht die Verarbeitung zu Zustand 507 über, wo
der Pixelzählwert
auf 2 gesetzt wird und der Index des letzten schwarzen Pixels als
ein "Kanten Kandidat" gesetzt wird. Der
Kanten Kandidat ist das letzte schwarze Pixel in einer Abfolge von
N oder mehr aufeinanderfolgenden schwarzen Pixeln. Bei Zustand 507 wird
der Pixelzählwert
auf 2 zurückgesetzt.
Wenn das Pixel, dem bei Schritt 507 begegnet wird, schwarz
ist, geht die Verarbeitung zurück zu
Zustand 501, um ein Zählen
von schwarzen Pixeln zu beginnen, wobei tatsächlich der Kanten Kandidat
verworfen wird, weil die notwendige Bedingung, d.h. mindestens N
aufeinanderfolgende schwarze Pixel gefolgt von mindestens N aufeinanderfolgenden
weißen
Pixeln, nicht erfüllt
worden ist. Wenn das Pixel, dem bei Zustand 507 begegnet
wird, weiß ist,
geht die Verarbeitung zu Zustand 509 über, wo der Pixelzählwert inkrementiert
wird. Die Verarbeitung fährt
bei Zustand 509 fort, solange weißen Pixeln begegnet wird und
der Pixelzählwert
kleiner als N bleibt. Wenn einem schwarzen Pixel zu irgendeiner
Zeit, bevor das N-te weiße
Pixel erreicht ist, begegnet wird, kehrt die Verarbeitung zu Zustand 501 zurück, wobei
der Kanten Kandidat verworfen wird, weil die notwendige Bedingung
von mindestens N aufeinanderfolgenden weißen Pixeln nicht erfüllt ist.
Wenn das N-te aufeinanderfolgende weiße Pixel erreicht ist, geht
die Verarbeitung zu Zustand 511 über, bei dem der Kantenkandidat
gespeichert wird, und der Pixelzählwert
wird inkrementiert. Wie es oben mit Bezug auf die Zustände 502, 506 und 506 festgestellt
wurde, ist die Verarbeitung durch die Zustände 508, 510 und 512 analog zu
derjenigen, die oben mit Bezug auf die Zustände 507, 509 und 511 diskutiert
wurde, wobei die Pixelfarben umgekehrt sind. Die einzige Ausnahme
ist, daß der
Kanten Kandidat bei Zustand 508 auf den Index des gegenwärtigen Pixels
gesetzt ist, während
der Kanten Kandidat bei Zustand 507 auf den Index des vorhergehenden
Pixels gesetzt ist, wie es in Tabelle 1 angegeben ist, da nur schwarze
Pixel als Kanten bezeichnet werden können.At state 505 the processing continues with state 505 for each successive black pixel, incrementing the pixel count for each pass and actually searching for the last black pixel in the current sequence. If at state 505 encountered a white pixel, the processing goes to state 507 where the pixel count is set to 2 and the index of the last black pixel is set as a "candidate edge". The edge candidate is the last black pixel in a sequence of N or more consecutive black pixels. At state 507 the pixel count is reset to 2. If the pixel that is at step 507 is encountered, is black, processing goes back to state 501 to start counting black pixels, actually discarding the edge candidate because the necessary condition, ie, at least N consecutive black pixels followed by at least N consecutive white pixels, has not been satisfied. If the pixel at the was standing 507 is white, is the processing goes to state 509 over where the pixel count is incremented. Processing continues at state 509 as long as white pixels are encountered and the pixel count remains smaller than N. When a black pixel is encountered at any time before the Nth white pixel is reached, the processing returns to the state 501 back, where the edge candidate is discarded because the necessary condition of at least N consecutive white pixels is not met. When the Nth consecutive white pixel is reached, the processing goes to state 511 where the edge candidate is stored and the pixel count is incremented. As above with regard to the states 502 . 506 and 506 has been determined, is the processing by the states 508 . 510 and 512 analogous to the one above with respect to the states 507 . 509 and 511 was discussed with the pixel colors reversed. The only exception is that the edges candidate at state 508 is set to the index of the current pixel, while the edge is candidate at state 507 is set to the index of the previous pixel, as indicated in Table 1, since only black pixels can be referred to as edges.
Wenn
als nächstes
bei Zustand 511 einem schwarzen Pixel begegnet wird, geht
die Verarbeitung zu Zustand 508 über und dieses schwarze Pixel
wird als ein Kanten Kandidat festgelegt, da mindestens N aufeinanderfolgenden
weißen
Pixeln begegnet worden ist (nur schwarze Pixel können Kanten sein). Nach Zustand 508 fährt die
Verarbeitung durch die Zustände 510 und 512 fort,
auf eine ähnliche
Weise wie die Verarbeitung, die bei den Zuständen 509 und 511 auftrat,
um zu bestimmen, ob es N aufeinanderfolgende schwarze Pixel gibt,
die mindestens N aufeinanderfolgenden weißen Pixeln folgen, und wenn
dies der Fall ist, wird der Kanten Kandidat als eine Kante bei Schritt 512 gespeichert.
Wenn bei Zustand 511 einem weißen Pixel begegnet wird, geht
die Verarbeitung zu Zustand 506 über, um das letzte weiße Pixel
in der gegenwärtigen
Abfolge zu suchen, und geht dann zu Zustand 508 über, sobald
das letzte weiße
Pixel aufgefunden wurde, um zu bestimmen, ob eine Abfolge von mindestens
N schwarzen Pixeln folgt: Analoge Schritte treten mit Bezug auf
die Verarbeitung von Zustand 512 durch die Zustände 505, 507, 509 und 511 auf.If next at state 511 a black pixel is encountered, the processing goes to state 508 over and this black pixel is set as an edge candidate since at least N consecutive white pixels have been encountered (only black pixels can be edges). After state 508 the processing moves through the states 510 and 512 in a similar way as the processing used in the states 509 and 511 occurred to determine if there are N consecutive black pixels following at least N consecutive white pixels, and if so, the edge candidate becomes as an edge at step 512 saved. If at state 511 encountered a white pixel, the processing goes to state 506 to search for the last white pixel in the current sequence, and then go to state 508 over, as soon as the last white pixel is found, to determine if a sequence of at least N black pixels follows: Analogous steps occur with respect to the processing of state 512 through the states 505 . 507 . 509 and 511 on.
Der
Kantendetektionsprozeß fährt durch
die Reihe oder Spalte aus Pixeln fort, wobei nach N aufeinanderfolgenden
schwarzen (oder weißen)
Pixeln und dann nach N aufeinanderfolgenden weißen (oder schwarzen) Pixeln
einer zweiten Farbe gesucht wird, bis das spezielle Zeichen erreicht
ist, das das Ende der Reihe oder Spalte bezeichnet. An jedem Punkt,
an dem N aufeinanderfolgende schwarze (oder weiße) Pixel gefunden werden,
dem N aufeinanderfolgende weiße
(oder schwarze) Pixel folgen, wird das schwarze Pixel an der Grenze
zwischen den beiden Abfolgen als eine Kante festgelegt.Of the
Edge detection process goes through
the row or column of pixels, where after N consecutive
black (or white)
Pixels and then N consecutive white (or black) pixels
a second color is searched until the special character is reached
is, which denotes the end of the row or column. At every point,
where N consecutive black (or white) pixels are found
the N consecutive white
(or black) pixels follow, the black pixel becomes the border
between the two sequences as an edge.
Sobald
die Kantenpixel (entweder horizontal, vertikal oder sowohl horizontal
als auch vertikal) durch den Erkenner endlicher Zustände detektiert
werden, werden sie in den Hough-Bereich unter Verwendung des gleichen
Prozesses, der in der '189-Anmeldung
beschrieben ist, abgebildet.As soon as
the edge pixels (either horizontal, vertical, or both horizontal
as well as vertically) detected by the recognizer of finite states
They will be in the Hough area using the same
Process in the '189 application
is described.
Der
Erkenner endlicher Zustände
verbessert die Verarbeitungsgeschwindigkeit des Schrittes zur Schrägstellungsabschätzung, beeinflußt jedoch
nicht die Auswirkung von Linienrauschen. Wenn, wie es in 9A gezeigt
ist, eine Linie 400 gezogen wird, die durch einen Strichcode 410 hindurch
verläuft,
wird sie die dominante Kantenlinie 430 innerhalb der Kantenabbildung 420 werden
und wird ein falsches Ergebnis für
den Schrägstellungswinkel
erzeugen, wenn die Linie nicht parallel zur horizontalen (oder vertikalen,
wenn vertikale Kanten detektiert werden) Achse des Strichcodes selbst
gezogen ist. Die Linie 430 in 9A bewirkt,
daß der Schrägstellungswinkel
falsch als 0,5 Grad abgeschätzt
wird. Um den Einfluß einer
derartigen beliebig gezogenen Linie beim Abschätzen des Schrägstellungswinkels
des zweidimensionalen Strichcodes zu verringern, unterteilt das
Verfahren der vorliegenden Erfindung die horizontale Kantenabbildung,
die von dem Erkenner endlicher Zustände geschaffen wird, in eine
Anzahl von Bereichen. Der Schrägstellungswinkel
wird für
jeden Bereich bestimmt, und es wird ein Wahlschema dazu verwendet,
den Schrägstellungswinkel
zu bestimmen, der am wahrscheinlichsten die tatsächliche Schrägstellung
repräsentiert.
Bei dem bevorzugten Verfahren wird die horizontale Kantenabbildung
in drei Bereiche unterteilt, wie einen oberen Bereich 440,
einen mittleren Bereich 450 und einen unteren Bereich 460 der
horizontalen Kantenabbildung 420 von 9B.
Der Schrägstellungswinkel
wird für
jeden Bereich bestimmt, d.h., fünf
Grad für
den oberen Bereich 440 und den mittleren Bereich 450 und
0,5 Grad für
den unteren Bereich (aufgrund der Kantenlinie 430, die
durch die gezogene Linie 400 hervorgerufen wird), und der
Medianwert, d.h., vorzugsweise fünf
Grad, wird als die tatsächliche
Schrägstellungswinkelabschätzung gewählt. Wie
der Fachmann feststellen wird, gibt es viele Möglichkeiten, das Wahlschema
zu implementieren. Bei der vorliegenden Erfindung wird der Me dianwert
verwendet, weil er den geringsten Overhead im Hinblick auf die Verarbeitungsgeschwindigkeit
liefert. Andere Verfahren zum Bestimmen des Schrägstellungswinkels umfassenden
am häufigsten
auftretenden Schrägstellungswinkel
(d.h., Majoritätswahl)
oder komplexere Gewichtungstechniken (d.h. gewichtete Wahl). Dieses
Mehrbereichs-Schrägstellungsabschätzschema
ist robuster gegenüber
beliebigem Linienrauschen als Verfahren nach dem Stand der Technik,
weil, wenn Linienrauschen vorhanden ist, das die Schrägstellungsabschätzung beeinflussen
wird, es wahrscheinlich ist, daß nur
ein einziger Bereich beeinflußt
wird, wie es durch die Linie 400 in 9B veranschaulicht
ist. Wenn Linienrauschen vorhanden ist, das mehr als einen Bereich überquert,
muß es
unter einem relativ großen
Winkel in bezug auf die Kantenpixel in der horizontalen Kantenabbildung
sein und wird somit keine dominante Linie sein, die die Schrägstellungswinkelabschätzung beeinflußt. Wie
der Fachmann feststellen wird, kann auf der Grundlage der Detektion
von sowohl horizontalen als auch vertikalen Kanten die Kantenabbildung
in sowohl horizontale als auch vertikale Bereiche zur Prüfung durch
eines der Wahlschemata unterteilt sein.The finite state recognizer improves the processing speed of the skew estimation step, but does not affect the effect of line noise. If, as it is in 9A shown is a line 400 being pulled by a barcode 410 passes through, it becomes the dominant edge line 430 within the edge map 420 and will produce an incorrect result for the skew angle if the line is not drawn parallel to the horizontal (or vertical if vertical edges are detected) axis of the bar code itself. The line 430 in 9A causes the skew angle to be misjudged as 0.5 degrees. In order to reduce the influence of such arbitrarily drawn line in estimating the skew angle of the two-dimensional bar code, the method of the present invention divides the horizontal edge map provided by the finite state recognizer into a number of regions. The skew angle is determined for each area, and a voting scheme is used to determine the skew angle that most likely represents the actual skew. In the preferred method, the horizontal edge map is divided into three areas, such as an upper area 440 , a middle area 450 and a lower area 460 the horizontal edge illustration 420 from 9B , The skew angle is determined for each area, ie, five degrees for the upper area 440 and the middle area 450 and 0.5 degrees for the lower area (due to the edge line 430 passing through the drawn line 400 is generated), and the median value, ie, preferably five degrees, is chosen as the actual skew angle estimate. As those skilled in the art will recognize, there are many ways to implement the voting scheme. In the present invention, the median value is used because it provides the least overhead in terms of processing speed. Other methods of determining the skew angle include most commonly occurring skew angle (ie, majority choice) or more complex weighting techniques (ie, weighted choice). This multi-range skew estimation scheme is more robust to any line noise than prior art methods nik, because if there is line noise that will affect the skew estimate, it is likely that only a single area will be affected, as by the line 400 in 9B is illustrated. If there is line noise traversing more than one region, it must be at a relatively large angle with respect to the edge pixels in the horizontal edge map and thus will not be a dominant line that affects skew angle estimation. As one of ordinary skill in the art will appreciate, based on the detection of both horizontal and vertical edges, the edge map may be divided into both horizontal and vertical regions for review by one of the voting schemes.
Wie
es oben diskutiert wurde, gestattet die Verwendung eines Erkenners
endlicher Zustände,
um die Kantenpixel aufzufinden, gefolgt durch den Schrägstellungsabschätzschritt
auf der Grundlage der Hough-Transformation, daß das Verfahren der vorliegenden
Erfindung die Notwendigkeit für
Ankerbits in dem zweidimensionalen Strichcode beseitigt, was die
Auswirkung von Eckenverformung des zweidimensionalen Strichcodes
verringert. Zusätzlich
erhöht
das Mehrbereichs-Wahlschema die Immunität des Verfahrens zur Schrägstellungsabschätzung der
vorliegenden Er findung gegenüber
Hintergrundrauschen, insbesondere gezogene Linien, weiter.As
as discussed above, allows the use of a recognizer
finite states,
to find the edge pixels, followed by the skew estimation step
on the basis of Hough transformation, that the method of the present
Invention the need for
Ankerbits in the two-dimensional barcode eliminates what the
Impact of corner deformation of two-dimensional bar code
reduced. additionally
elevated
the multirange voting scheme the immunity of the skew estimation method of the
present invention
Background noise, especially drawn lines, continue.
Sobald
der Schrägstellungswinkel
abgeschätzt
worden ist, wird die Schrägstellung
des Kandidatbereichs beseitigt, wie es oben mit Bezug auf Schritt 108 von 5 diskutiert
ist, und in der '189-Anmeldung
ausführlicher
beschrieben ist, unter Verwendung eines Scher-Dreh-Verfahrens für kleinere
Schrägstellungsniveaus
und alternativ unter Verwendung eines trigonometrischen Verfahrens
für größere Schrägstellungsniveaus.Once the skew angle has been estimated, the skew of the candidate area is eliminated, as described above with respect to step 108 from 5 and is described in more detail in the '189 application using a shear-twisting method for smaller skew levels and, alternatively, using a trigonometric method for larger skew levels.
Nach
dem Korrigieren des Schrägstellungswinkels
wird die Umgrenzung des zweidimensionalen Strichcodes wahlweise
durch den Zuschneideschritt 110 von 5 bestimmt,
der das gleiche Verfahren von innen nach außen verwendet, das oben mit
Bezug auf den Auffindungsschritt 104 beschrieben ist, obwohl
ein engerer Schwellenwert dazu verwendet wird, die Gültigkeit
des Kandidatbereichs des zweidimensionalen Strichcodes zu prüfen, da
die Beseitigung der Schrägstellung
bereits aufgetreten ist und es unwahrscheinlich ist, daß irgendwelche
gültigen
Bits weggeschnitten sind. Sobald der Kandidatbereich zugeschnitten
ist, werden dessen Abmessungen mit den erwarteten Abmessungen des
zweidimensionalen Strichcodes verglichen. Wenn sich die Abmessungen
stark unterscheiden, ist kein zweidimensionaler Strichcode in dem
Kandidatbereich vorhanden, und die Verarbeitung geht zurück zu dem
Auffindungsschritt 104, wie es in 5 gezeigt
ist. Wenn die Abmessungen in einen Bereich fallen, der nahe bei
der Größe des zweidimensionalen
Strichcodes ist, geht die Verarbeitung zum Leseschritt 112 über.After correcting the skew angle, the boundary of the two-dimensional bar code is optionally selected by the cropping step 110 from 5 determined using the same procedure from the inside out, the above with respect to the finding step 104 although a narrower threshold is used to check the validity of the candidate area of the two-dimensional bar code, since the elimination of skew has already occurred and it is unlikely that any valid bits are cut away. Once the candidate area is cropped, its dimensions are compared to the expected dimensions of the two-dimensional bar code. If the dimensions differ greatly, there is no two-dimensional bar code in the candidate area, and processing goes back to the locating step 104 as it is in 5 is shown. If the dimensions fall within a range close to the size of the two-dimensional bar code, the processing goes to the reading step 112 above.
An
diesem Punkt ist der abgetastete, zweidimensionale Strichcode aufgefunden,
dessen Schrägstellung
beseitigt und er eng zugeschnitten worden. Der nächste Schritt ist es, die Datenbits
auszulesen, was den zweidimensionalen Strichcode aus dem Abbildungsbereich,
in dem jedes Bit als eine Ansammlung schwarzer oder weißer Pixel
dargestellt ist, bei der bevorzugten Ausführungsform in ein 20 × 20-Bit-Array
aus logischen Werten transformiert. Es ist anzumerken, daß, da die
zweidimensionale Strichcodesymbologie taktfrei ist, es keine. vorherbestimmten
Referenzmuster gibt, um zu helfen, den Leseprozeß zu orientieren. Jedoch ist
die logische Größe des zweidimensionalen
Strichcodes im voraus bekannt, beispielsweise ein Quadrat, das bei
der bevorzugten Ausführungsform 20 Bits
auf jeder Seite mißt.
Weil diese Bits in der Markierung während des Codierprozesses pseudo-stochastisiert
werden, wird außerdem
irgendeine besondere Reihe oder Spalte aus Pixeln eine stärkere Verteilung
von Schwarz-Weiß-
und Weiß-Schwarz-Übergängen in
der Nähe
der Kanten in den logischen Reihen und Spalten und eine geringere
Verteilung in der Nähe
der Mitten aufweisen. Dieser Prozeß ist vollständig in
der '280-Anmeldung
beschrieben. Sobald horizontale und vertikale Mittellinien durch
den in der '280-Anmeldung
beschriebenen Prozeß hergestellt
sind, werden die Bits aus dem zweidimensionalen Strichcode ausgelesen,
indem der Pixelwert aufgezeichnet wird; der an der Schnittstelle
jeder horizontalen und vertikalen Mittellinie liegt (wobei beispielsweise
jeder "weiße" Pixelwert = "0" und jeder "schwarze" Pixelwert = " 1" gesetzt
wird). Die '189-Anmeldung
beschreibt mit Bezug auf die 18A–18D ein verbessertes Taktungsverfahren
zum Auslesen der Bits aus dem zweidimensionalen Strichcode, das
die Fehlerrate reduziert, indem die Bits in jeder der vier möglichen
Richtungen gelesen werden, wodurch vier unterschiedliche Arrays
geschaffen werden, die Daten darstellen, und das Array zur Ausgabe
ausgewählt wird,
bei dem der ECC-Schritt 37 von 3 zeigt,
daß es
die geringste Anzahl von Fehlern aufweist. Wenn der Leseschritt
versagt, wie es beispielsweise von dem ECC bestimmt wird, kann die
Verarbeitung hier wieder zurück
zu dem Auffindungsschritt 104 übergehen, wie es in 5 gezeigt
ist.At this point, the scanned, two-dimensional bar code has been found, its skew removed and it has been cut to size. The next step is to read the data bits, which transforms the two-dimensional bar code from the mapping area, where each bit is represented as a collection of black or white pixels, in the preferred embodiment into a 20x20 bit array of logical values. It should be noted that since the two-dimensional bar code symbology is clock-free, it is not. predetermined reference pattern to help orient the reading process. However, the logical size of the two-dimensional bar code is known in advance, for example a square, in the preferred embodiment 20 Measuring bits on each side. In addition, because these bits in the tag are pseudo-stochastized during the encoding process, any particular row or column of pixels will have a greater distribution of black-and-white and white-black transitions in the vicinity of the edges in the logical rows and columns and one have less distribution near the centers. This process is fully described in the '280 application. Once horizontal and vertical centerlines are established by the process described in the '280 application, the bits are read from the two-dimensional bar code by recording the pixel value; which is at the intersection of each horizontal and vertical centerline (for example, setting each "white" pixel value = "0" and each "black" pixel value = "1"). The '189 application describes with reference to FIGS 18A - 18D an improved timing method for reading out the bits from the two-dimensional bar code, which reduces the error rate by reading the bits in each of the four possible directions, thereby creating four different arrays representing data and selecting the array for output, in which the ECC step 37 from 3 shows that it has the least number of errors. If the read step fails, as determined, for example, by the ECC, then processing can go back to the discovery step 104 pass over, as is in 5 is shown.
Zusammengefaßt sind
zweidimensionale Strichcodes, die von einer Ruhezone aus weißem Raum
umgeben sind, die einen Rand umfassen oder nicht umfassen kann,
wobei jeder Strichcode codierte, digitale Information in einem Bitmuster
aufweist, das vorzugsweise stochastisierte, codierte Datenbits darstellt,
auf ein bedrucktes Medium gedruckt. Um die codierte, digitale Information
aus dem bedruckten Medium herauszuziehen, wird das bedruckte Medium
abgetastet, dann wird das Bitmuster innerhalb des bedruckten Mediums
aufgefunden, indem ein Fenster schrittweise in einem vorherbestimmten
Muster über
das bedruckte Medium hinweg bewegt wird. Bei jedem Schritt wird
der Teil des bedruckten Mediums, der von dem Fenster umgeben ist, geprüft, um zu
bestimmen, ob er zu einem Charakteristikum oder mehreren Charakteristiken
des Bitmusters paßt.
Die Schrägstellung
des Bitmusters, falls eine vorhanden ist, wird bestimmt, indem ein
Erkenner endlicher Zustände
in Kombination mit einer Hough-Transformationsberechnung verwendet
wird. Bei einer Ausführungsform
wird der Kandidatbereich in mehrere horizontale Bereiche unterteilt,
vorläufige
Schrägstellungswinkel
werden für
jeden Bereich berechnet, und der tatsächliche Schrägstellungswinkel
wird unter Verwendung eines Wahlschemas ausgewählt. Sobald der Schrägstellungswinkel
berechnet worden ist, wird die Schrägstellung des Bitmusters, falls
notwendig, beseitigt, das Bitmuster wird zugeschnitten und die stochastisierte,
digitale Information wird aus dem Bitmuster ausgelesen. Schließ lich werden
in dem Prozeß,
der jegliche entdeckte Fehler korrigiert und/oder aufzeichnet, die
digitalen Informationen entstochastisiert und jegliche Fehlerkorrekturcodes
entfernt, wodurch die ursprüngliche,
codierte, digitale Information reproduziert wird.Summarized are two-dimensional barcodes surrounded by a quiet zone of white space that may or may not include an edge, each barcode encoded, digital In Formation in a bit pattern, which preferably represents stochastisierte coded data bits, printed on a printed medium. In order to extract the encoded digital information from the printed medium, the printed medium is scanned, then the bit pattern is found within the printed medium by moving a window stepwise in a predetermined pattern across the printed medium. At each step, the portion of the printed media surrounded by the window is examined to determine if it matches one or more characteristics of the bit pattern. The skew of the bit pattern, if any, is determined by using a finite state recognizer in combination with a Hough transform computation. In one embodiment, the candidate area is divided into a plurality of horizontal areas, tentative skew angles are calculated for each area, and the actual skew angle is selected using a selection scheme. Once the skew angle has been calculated, the skew of the bit pattern is eliminated if necessary, the bit pattern is cropped, and the stochasticized digital information is read from the bit pattern. Finally, in the process that corrects and / or records any detected errors, the digital information is de-stochastized and any error correction codes are removed, thereby reproducing the original encoded digital information.