-
Die
Erfindung betrifft ein Verfahren gemäß dem Oberbegriff des Anspruchs
1 zur Lokalisierung von Bildelementen, welche wenigstens zwei rechtwinklige
Eckelemente aufweisen.
-
Ein
derartiges Verfahren wird insbesondere beim automatischen Lesen
von QR-Codes angewandt. Denn um QR-Codes automatisch lesen zu können, müssen die
Lesesysteme den Code genau lokalisieren können.
-
QR-Codes
sind zweidimensionale, quadratische Bildelemente, welche eine große Menge
an Informationen enthalten können.
QR-Codes sind von einer so genannten Ruhezone, welche keine Bildbestandteile
enthält,
umrandet. Zur Lokalisierung von QR-Codes enthalten diese an vorgegebenen
Positionen definierte rechtwinklige Eckelemente.
-
Beim
Lokalisieren von QR-Codes stellen Störungen im Grenzbereich der
Ruhezone ein großes
Problem dar. Des Weiteren ist es wegen der großen Anzahl von Objekten innerhalb
eines QR-Codes sehr
zeitaufwendig, einen QR-Code zu lokalisieren.
-
Aus
der
DE 197 22 439
A1 ist ein Verfahren bekannt, bei welchem aus zusammenhängenden Bildpunkten
Geraden ermittelt und die Schnittpunkte zweier sich im rechten Winkel
schneidender Geraden ermittelt werden.
-
Bei
dem bekannten Verfahren wird zunächst nach
einem Punkt gesucht, der auf einer möglichen Geraden liegen könnte. Ausgehend
von diesem Punkt werden dann in zwei Richtungen die Ecken gesucht,
die diese Gerade mit anderen möglichen
Geraden bildet.
-
Nachdem
eine Ecke gefunden wurde, wird auf dieselbe Weise eine zweite Gerade
gesucht, die diese Ecke mit der ursprünglichen Geraden bilden könnte.
-
Des
Weiteren ist aus der
US
6,863,218 B2 ein Verfahren bekannt, bei dem ein Bild in
verschiedene Richtungen durchgescannt und bei jeder Scan-Linie eine
Anzahl von weißen
beziehungsweise schwarzen Pixeln, die unmittelbar benachbart sind, gezählt wird.
Die schwarzen und weißen
Scan-Liniensegmente werden anschließend mit dem Muster eines so
genannten „Finder-Pattern" eines QR-Codes verglichen.
Auf diese Weise kann man die grobe Position von drei Finder-Pattern
bestimmen und deren Mittelpunkte berechnen, die dann die Grundlage für eine Drehlagenberechnung
bilden.
-
Anschließend wird
nach den Außenpunkten der
Finder-Pattern beziehungsweise des Codes mit Hilfe von Scan-Linien
gesucht, die in den jeweiligen Mittelpunkten anfangen und in verschiedene
Richtungen verlaufen. Zur Erhöhung
der Sicherheit wird anschließend
nach so genannten „Timing
Pattern" des QR-Codes
und nach so genannten „Alignment Pattern" gesucht. Um die „Alignment
Pattern" zu finden,
wird zunächst
ein Schnittpunkt ermittelt, wo sich zwei Geraden kreuzen, die parallel
zu zwei Geraden, die die Mittelpunkte verbinden, verlaufen.
-
Darüber hinaus
ist aus der US 2005/0121520 A1 ein Verfahren bekannt, bei dem zunächst nach
einem Startpunkt gesucht wird, der innerhalb eines Codes liegt.
Dann werden alle Richtungen gescannt und eine Gerade gesucht, die
zwei Punkte eines Kreises verbindet und komplett aus weißen Punkten
besteht sowie eine andere gerade Linie kreuzt, die auch vollständig aus
weißen
Punkten besteht und im Zentrum des Kreises liegt. Diese Gerade wird
dann als ein Rand des Codes bestimmt. Werden auf diese Weise vier
Ränder
bestimmt, kann die Drehlage und genaue Position des Codes bestimmt
werden.
-
Es
ist Aufgabe der vorliegenden Erfindung, ein Verfahren an- zugeben,
mittels welchem Bildelemente in relativ kurzer Zeit lokalisiert
werden können.
-
Die
Lösung
dieser Aufgabe ergibt sich aus den Merkmalen des kennzeichnenden
Teils des Anspruchs 1. Vorteilhafte Weiterbildungen der Erfindung
ergeben sich aus den Unteransprüchen.
-
Gemäß der Erfindung
ist ein Verfahren zur Lokalisierung von Bildelementen, welche wenigstens zwei
definierte rechtwinklige Eckelemente aufweisen, dadurch gekennzeichnet,
dass jeweils aus zusammenhängenden
Bildpunkten ein Objekt gebildet wird, die äußere Kontur der Objekte durch
Geraden angenähert dargestellt
wird, von im rechten Winkel zueinander verlaufenden Geraden die
Schnittpunkte bestimmt werden und festgestellt wird, ob einer Geraden
zwei Schnittpunkte zugeordnet werden können, die in einem Mindestabstand
zueinander liegen.
-
Mittels
des erfindungsgemäßen Verfahrens wird
im Wesentlichen die Position der definierten rechtwinkligen Eckelemente
bestimmt, wodurch das Bildelement lokalisiert werden kann. Die Erfindung macht
sich den Umstand zunutze, dass die definierten rechtwinkligen Eckelemente
sich in einer bestimmten Position in dem Bildelement befinden, wie dies
insbesondere bei QR-Codes der Fall ist. Bei QR-Codes sind immer
drei rechtwinklige Eckelemente vorhanden, welche sich an bestimmten
Stellen des QR-Codes befinden.
-
Mittels
des erfindungsgemäßen Verfahrens lässt sich
die Position der definierten rechtwinkligen Eckelemente in zuverlässiger Weise
und kurzer Zeit bestimmen.
-
Dadurch,
dass jeweils aus zusammenhängenden
Bildpunkten ein Objekt gebildet wird, wird im Wesentlichen sichergestellt,
dass die definierten rechtwinkligen Eckelemente auch dann erkannt
werden, wenn die Eckelemente von anderen Bildelementen oder Störlinien
ganz oder teilweise umschlossen sind. Dies wirkt sich erheblich
auf die Zuverlässigkeit
des Verfahrens aus.
-
Denn
erfindungsgemäß soll die äußere Kontur
der Objekte durch Geraden angenähert
dargestellt werden. Durch die Bildung von separaten Objekten kann
auch dann die äußere Kontur
der definierten rechtwinkligen Eckelemente auf einfache Weise dargestellt
werden, wenn sich die Eckelemente innerhalb eines ein eigenes Objekt
darstellenden Bildelements befinden bzw. von der Kontur eines anderen
Objektes abgeschirmt werden.
-
Durch
Bestimmung der Schnittpunkte der im rechten Winkel zueinander verlaufenden
Geraden werden alle rechtwinkligen Ecken der Konturen ermittelt.
D. h., es bleiben solche Ecken bzw. Schnittpunkte unberücksichtigt,
welche nicht zu einem rechtwinkligen Eckelement gehören. Es
werden somit nur solche Schnittpunkte berücksichtigt, welche zu den definierten
rechtwinkligen Eckelementen gehören
könnten.
-
Durch
die Bestimmung einer Geraden, welche von zwei anderen Geraden rechtwinklig
geschnitten wird, und durch die Überprüfung, ob
die Schnittpunkte in einem Mindestabstand zueinander liegen, werden
die zur Lokalisierung des betreffenden Bildelements erforderlichen
definierten Eckelemente ermittelt. Denn der Mindestabstand der Ecken der
definierten rechtwinkligen Eckelemente ist insbesondere bei QR-Codes
festgelegt. Ist der Abstand der Schnittpunkte größer als der festgelegte Mindestabstand
der Ecken der rechtwinkligen Eckelemente, bilden die Schnittpunkte
die Ecken eines definierten rechtwinkligen Eckelements. Es lassen
sich somit solche rechtwinkligen Eckelemente ausblenden, welche
nicht zu den definierten rechtwinkligen Eckelementen gehören.
-
In
vorteilhafter weise kann nach dem Bilden der Objekte die Größe der Objekte
festgestellt und die Größe der Objekte
mit einer vorbestimmten Größe verglichen
werden, so dass Objekte, deren Größe kleiner als die vorbestimmte
Größe ist,
aussortiert werden können.
Hierdurch reduziert sich die zu verarbeitende Datenmenge erheblich,
was sich sehr vorteilhaft auf die Geschwindigkeit des Verfahrens auswirkt.
Sehr vorteilhaft ist insbesondere, dass durch das Aussortieren der
kleinen Objekte die Genauigkeit bzw. Zuverlässigkeit des Verfahrens nicht beeinträchtigt wird.
-
Bei
einer weiteren besonderen Ausführungsform
der Erfindung ist vorgesehen, dass die Objekte von ein Rechteck
bildenden Seitenlinien umrahmt werden, den Seitenlinien des Rechtecks
am nächsten
kommende Bildpunkte erfasst werden und den erfassten Bildpunkten
eine Gerade zugeordnet wird. Hierdurch wird die einer jeweiligen
Seitenlinie zugeordnete äußere Kontur
eines Objekts durch eine oder mehrere Geraden näherungsweise dargestellt.
-
Handelt
es sich bei einer derart gebildeten Geraden um die Seite eines definierten
rechtwinkligen Eckelements, so fällt
diese Gerade mit der entsprechenden Geraden eines anderen definierten rechtwinkligen
Eckelements zusammen. Diese Gerade wird von den anderen Geraden,
die die beiden definierten rechtwinkligen Eckelemente bilden, geschnitten.
Da der Abstand der Schnittpunkte größer ist als der festgelegte
Mindestabstand, in dem sich die definierten rechtwinkligen Eckelemente
befinden müssen,
steht fest, dass die Schnittpunkte die Ecken der definierten rechtwinkligen
Eckelemente darstellen.
-
Als
sehr vorteilhaft hat es sich herausgestellt, die Objekte von den
Seitenlinien des Rechtecks abzutasten und jeweils aus einem Bereich
von drei bis zehn, insbesondere vier bis sieben, vorzugsweise fünf zusammenhängenden
Bildpunkten einen solchen Bildpunkt zu markieren, der der betreffenden Seitenlinie
am nächsten
kommt, wobei die Gerade dann aus den markierten Bildpunkten gebildet
wird. Hierdurch wird die zu verarbeitende Datenmenge stark reduziert,
was sich sehr vorteilhaft auf die Geschwindigkeit des erfindungsgemäßen Verfahrens auswirkt.
Es hat sich herausgestellt, dass genannte Datenreduktionen die Genauigkeit
bzw. Zuverlässigkeit
des erfindungsgemäßen Verfahrens
nahezu nicht beeinträchtigen.
-
Sehr
vorteilhaft ist auch eine Ausführungsform
der Erfindung, bei der aus den markierten Bildpunkten jeweils ein
die Gerade bildender Gesamtvektor gebildet wird, derart, dass (n)
aus einem ersten markierten Bildpunkt und einem zweiten markierten
Bildpunkt ein erster Untervektor gebildet wird, (o) durch die Hinzunahme
eines weiteren markierten Bildpunkts ein wei terer Untervektor gebildet
wird, (p) der Winkel zwischen dem ersten Untervektor und dem weiteren
Untervektor bestimmt wird, (q) festgestellt wird, ob der bestimmte
Winkel kleiner als ein Grenzwinkel ist, und (r) für den Fall,
dass der bestimmte Winkel kleiner als der Grenzwinkel ist, die Schritte
(o) bis (q) wiederholt werden, wobei dann im Schritt (p) jeweils
der Winkel zwischen einem dann jeweils vorhergehenden gebildeten
Untervektor und einem dann jeweils zusätzlichen Untervektor bestimmt
wird, bzw. (s) für
den Fall, dass der bestimmte Winkel gleich oder größer als
der Grenzwinkel ist, der Gesamtvektor durch die Verbindungslinie
vom ersten Bildpunkt zum vorletzten hinzugenommenen Bildpunkt bestimmt
wird.
-
Eine
derartige Bildung der Geraden zeichnet sich dadurch aus, dass bei
einem vertretbaren Rechenaufwand eine hohe Genauigkeit erreicht
wird. D. h., die derart gebildete Gerade ist sehr gut an die markierten
Bildpunkte angenähert.
-
Dadurch,
dass ein weiterer Bildpunkt hinzugenommen wird, lässt sich
ein weiterer Untervektor bestimmen. In vorteilhafter Weise ist der
weitere Bildpunkt zum zweiten Bildpunkt direkt benachbart bzw. ist
jeweils der zusätzlich
hinzugenommene Bildpunkt zum vorhergehenden Bildpunkt direkt benachbart. Hierdurch
wird eine sehr große
Genauigkeit erreicht.
-
Des
Weiteren ist es vorteilhaft, wenn der weitere bzw. jeweils der zusätzliche
Untervektor durch die Verbindungslinie zwischen dem zweiten Bildpunkt
und dem weiteren Bildpunkt gebildet wird, wie dies bei einer besonderen
Ausführungsform
der Erfindung vorgesehen ist. D. h., der weitere Vektor hat zunächst seinen
Ausgangspunkt im zweiten Bildpunkt und endet im dritten Bildpunkt
bzw. der zusätzliche
Vektor hat seinen Ausgangspunkt im vorletzten hinzugenommenen Bildpunkt
und endet im zuletzt hinzugenommenen Bildpunkt.
-
Nachdem
der weitere Untervektor gebildet wurde, wird der Winkel zwischen
dem ersten Untervektor, der beispielsweise seinen Ausgangspunkt
im ersten Bildpunkt hat und im zweiten Bildpunkt endet, und dem
weiteren Untervektor, d. h. hier zunächst dem zweiten Untervektor,
der gemäß einer
besonderen Ausführungsform
der Erfindung zwischen den beiden zuletzt hinzugenommenen Bildpunkten
angeordnet ist, d. h. hier zunächst
seinen Ausgangspunkt im zweiten Bildpunkt hat und im dritten Bildpunkt
endet, bestimmt.
-
Der
zwischen den beiden Vektoren gebildete Winkel wird dann mit einem
Grenzwinkel verglichen. Ist der bestimmte Winkel kleiner als der
Grenzwinkel, wird ein zusätzlicher
Bildpunkt, d. h. hier zunächst
ein vierter Bildpunkt, hinzugenommen und die vorstehend beschriebene
Vorgehensweise wiederholt.
-
D.
h., es wird ein zusätzlicher
Vektor gebildet, d. h. hier zunächst
ein dritter Vektor, der zwischen dem dritten Bildpunkt und dem vierten
Bildpunkt angeordnet ist, d. h. der im dritten Bildpunkt seinen
Ausgangspunkt hat und im vierten Bildpunkt endet. Zwischen dem zusätzlichen
Vektor und dem hier zunächst
aus dem zweiten Bildpunkt und dem dritten Bildpunkt gebildeten vorhergehenden
Vektor, d. h. hier zunächst
dem zweiten Vektor, wird der Winkel bestimmt und mit dem Grenzwinkel
verglichen.
-
Ist
der bestimmte Winkel kleiner als der Grenzwinkel, wiederholt sich
das Verfahren erneut, und zwar so lange, bis der zwischen den beiden
zuletzt gebildeten Vektoren bestimmte Winkel größer ist als der Grenzwinkel.
In dem Fall wird der Ausgangspunkt des zuletzt gebildeten Vektors,
d. h. der vorletzte hinzugenommene Bildpunkt und der erste Bildpunkt,
zur Bildung eines Gesamtvektors genommen, der vom ersten Bildpunkt
ausgeht und im vorletzten hinzugenommenen Bildpunkt endet.
-
Statt
dass der weitere bzw. zusätzliche
Untervektor durch die Verbindungslinie zwischen den beiden zuletzt
hinzugenommenen Bildpunkten gebildet wird, kann der weitere bzw.
zusätzliche
Untervektor durch einen durch die Verbindungslinie zwischen dem
ersten Bildpunkt und dem zuletzt hinzugenommenen Bildpunkt gebildeten
Gesamtsummenvektor gebildet werden, wie dies bei einer weiteren
besonderen Ausführungsform
der Erfindung vorgesehen ist.
-
D.
h., der Winkel wird nicht zwischen den beiden zuletzt gebildeten,
jeweils zwischen zwei benachbarten Bildpunkten angeordneten Vektoren
gebildet, sondern es wird stets zwischen dem ersten Bildpunkt und
dem letzten hinzugenommenen Bildpunkt ein Gesamtsummenvektor gebildet,
der seinen Ausgangspunkt im ersten Bildpunkt hat und im letzten
hinzugenommenen Bildpunkt endet, mit dem dann ein zuvor gebildeter
Untervektor, beispielsweise ein aus dem letzten hinzugenommenen
Bildpunkt und dem vorletzten hinzugenommenen Bildpunkt gebildeter
Untervektor, der im vorletzten hinzugenommenen Bildpunkt seinen
Ausgangspunkt hat und im letzten hinzugenommenen Bildpunkt endet,
den zu bestimmenden Winkel bildet.
-
Ist
der Winkel zwischen diesen beiden Vektoren kleiner als der Grenzwinkel,
wird ein weiterer Bildpunkt hinzugenommen, mit dem dann ein neuer Gesamtsummenvektor
gebildet wird, der seinen Ausgangspunkt im ersten Bildpunkt hat
und im weiteren hinzugenommenen Bildpunkt endet, und der vorstehende
Vorgang wiederholt sich.
-
Der
Vorgang wiederholt sich so lange, bis der aus dem jeweiligen Gesamtsummenvektor
und dem aus den beiden zuletzt hinzugenommenen Bildpunkten gebildeten
Untervektor gebildete Winkel größer als
der Grenzwinkel ist. Ist der Winkel größer als der Grenzwinkel, wird
der zuletzt gebildete Gesamtsummenvektor zum Gesamtvektor.
-
Des
Weiteren kann statt, dass der vorhergehende Untervektor durch die
Verbindungslinie zwischen dem als drittletzten hinzugenommenen Bildpunkt
und dem als vorletzten hinzugenommenen Bildpunkt gebildet wird,
der vorhergehende Untervektor durch einen durch die Verbindungslinie
zwischen dem ersten Bildpunkt und dem als vorletzten hinzugenommenen
Bildpunkt gebildeten Teilsummenvektor gebildet werden, wie dies
bei einer weiteren besonderen Ausführungsform der Erfindung vorgesehen
ist.
-
D.
h., der Winkel wird nicht von dem entweder aus den beiden letzten
hinzugenommenen Bildpunkten gebildeten Untervektor oder aus dem
aus dem ersten Bildpunkt und dem zuletzt hinzugenommenen Bildpunkt
gebildeten Gesamtsummenvektor und dem aus dem drittletzten hinzugenommenen Bildpunkt
und dem vorletzten hinzugenommenen Bildpunkt gebildeten Untervektor
gebildet, sondern entweder aus dem aus den beiden letzten hinzugenommenen
Bildpunkten gebildeten Untervektor oder aus dem ersten Bildpunkt
und dem letzten hinzugenommenen Bildpunkt gebildeten Gesamtsummenvektor
und dem aus dem ersten Bildpunkt und dem vorletzten hinzugenommenen
Bildpunkt gebildeten Teilsummenvektor.
-
Bei
der vorstehend beschriebenen Ausführungsform des erfindungsgemäßen Verfahrens
werden somit im Prinzip aus beispielsweise benachbarten Bildpunkten
Vektoren gebildet. Diese Vektoren werden ausgehend von einem ersten
Vektor so lange miteinander verknüpft, bis sich die Richtungen
der Vektoren um einen nicht mehr tolerierbaren Betrag unterscheiden.
-
D.
h., es wird jeweils unter Berücksichtigung eines
neu hinzugenommenen Bildpunkts ein neuer Vektor gebildet, dessen
Richtung mit der Richtung eines jeweils unter Berücksichtigung
der vorher vorhandenen Bildpunkte gebildeten Vektors verglichen wird,
und zwar so lange, bis sich die Richtungen um einen vorbestimmten
Wert unterscheiden. Aus den bis dahin miteinander verknüpften Vektoren
wird dann ein Gesamtvektor gebildet.
-
Die
Länge des
Gesamtvektors hängt
davon ab, wie viel Einzelvektoren miteinander verknüpft werden.
Die Verknüpfung
der Einzelvektoren wiederum erfolgt so lange, bis die Richtung eines
Einzelvektors eine zu große Änderung
aufweist. Ist die Richtungsänderung
eines Einzelvektors zu groß,
wird dieser Einzelvektor nicht mehr zur Bildung des Gesamtvektors
hinzugenommen und der Gesamtvektor aus den bisher miteinander verknüpften Einzelvektoren gebildet.
-
Bei
einer weiteren besonderen Ausführungsform
der Erfindung ist vorgesehen, dass für den Fall, dass der bestimmte
Winkel größer als
der Grenzwinkel ist, aus dem vorletzten hinzugenommenen Bildpunkt
und dem letzten hinzugenommenen Bildpunkt eine neue erste Richtung
bestimmt wird, wobei der neue erste Bildpunkt dem vorletzten hinzugenommenen
Bildpunkt entspricht und der neue zweite Bildpunkt dem letzten hinzugenommenen
Bildpunkt. D. h., das Verfahren beginnt zur Bildung eines neuen Gesamtvektors
von vorne.
-
Hierdurch
kann in vorteilhafter Weise die vollständige Kontur eines Objektes
durch Vektoren dargestellt werden. Die Bildung einer geschlossenen Kontur
ist dann abgeschlossen, wenn der letzte gebildete Gesamtvektor im
ersten Bildpunkt, d. h. in dem Bildpunkt, von dem der erste gebildete
Gesamtvektor ausgeht, endet.
-
Weitere
Einzelheiten, Merkmale und Vorteile der vorliegenden Erfindung ergeben
sich aus der nachfolgenden Beschreibung eines besonderen Ausführungsbeispiels
unter Bezugnahme auf die Zeichnung.
-
Es
zeigen:
-
1 eine
schematische Darstellung eines Störungen aufweisenden QR-Codes,
-
2 den
in 1 dargestellten QR-Code als Binärbild,
-
3 die
in 2 enthaltenen, aus zusammenhängenden Punkten bestehenden
Objekte,
-
4 die
nach einem Größenvergleich
verbleibenden Objekte,
-
5 ein
in 3 enthaltenes, einzelnes Objekt,
-
6 das
in 5 dargestellte Objekt, von Seitenlinien umrandet
und mit hervorgehobener äußerer Kontur,
-
7 eine
Grobstruktur der in 6 dargestellten äußeren Kontur,
-
8 die
durch angenäherte
Geraden dargestellte Grobstruktur der 6,
-
9 eine
Darstellung der rechtwinkligen Ecken aller in 3 dargestellten
Objekte, die durch die äußere Kontur
der Objekte beschreibenden Geraden gebildet werden, die sich im
rechten Winkel schneiden,
-
10 die
Ecken aus 9, die sich in einem vorgegebenen
Mindestabstand zueinander befinden und auf einer gemeinsamen Geraden
liegen,
-
11 eine
durch markante Bildpunkte dargestellte äußere Kontur eines weiteren
Objektes,
-
12 zwischen
zwei benachbarten markanten Bildpunkten der in 11 dargestellten
Kontur angeordnete Vektoren,
-
13 die
Bestimmung von Winkeln jeweils zwischen zwei zuletzt gebildeten
Untervektoren,
-
14 die
Beschreibung der in 11 dargestellten Kontur mittels
mehrerer aus den in 13 dargestellten Untervektoren
gebildeter Gesamtvektoren,
-
15 eine
zweite Ausführungsform
zur Bildung eines Untervektors,
-
16 eine
dritte Ausführungsform
zur Bildung eines Untervektors und
-
17 eine
weitere Ausführungsform
zur Bestimmung des Winkels zwischen zwei Untervektoren.
-
Wie 1 entnommen
werden kann, weist ein QR-Code drei rechtwinklige Eckelemente 1a, 1b, 1c auf,
die sich in definierten Positionen der Abbildung des QR-Codes befinden.
Der Abstand der rechtwinkligen Eckelemente 1a, 1b, 1c ist
gleich oder größer als
ein festgelegter Mindestabstand. Durch die rechtwinkligen Eckelemente 1a, 1b, 1c lässt sich der
QR-Code lokalisieren, da die Bildelemente des QR-Codes eine definierte
Lage zu den rechtwinkligen Eckelementen 1a, 1b, 1c haben.
-
Die
Bildelemente des QR-Codes sind von einer so genannten Ruhezone 2 umrahmt,
welche vollständig
frei von Bildbestandteilen ist. Der QR-Code kann, wie in 1 dargestellt,
durch Kratzer oder entsprechende Farblinien 3a, 3b gestört sein.
-
Um
den QR-Code lesen zu können,
muss ein betreffendes Lesesystem den Code genau lokalisieren können. Dies
kann dadurch geschehen, dass die Positionen der rechtwinkligen Eckelemente 1a, 1b, 1c festgestellt
werden. Hierzu wird die in 1 dargestellte
Abbildung zunächst
in ein Binärbild
umgewandelt. Das entsprechende Binärbild ist in 2 dargestellt.
-
Wie 2 entnommen
werden kann, entspricht das Binärbild
zwar im Wesentlichen dem QR-Code, jedoch sind die Störungen 3a, 3b mit
den übrigen
Elementen des QR-Codes zu einem Gesamtbild verschmolzen.
-
Zur
Lokalisierung der rechtwinkligen Eckelemente 1a, 1b, 1c werden
die zusammenhängenden Bildpunkte
des Binärbildes
zu einzelnen Objekten zusammengefasst. Dies ist aus der so genannten
Blobanalyse bekannt. Die einzelnen Objekte sind in 3 mit
den Bezugszeichen 4 bis 16 bezeichnet.
-
Im
nächsten
Schritt wird die Größe der Objekte
mit einer vorgegebenen Größe verglichen
und solche Objekte ausgesondert, deren Größe kleiner als die vorgegebene
Größe ist.
Hierbei handelt es sich um die Objekte 5, 8, 9, 10, 11, 14, 15, 16.
Dem weiteren Verfahren werden somit nur noch die verbleibenden Elemente 4, 6, 7, 12, 13 zugrunde
gelegt. Die verbleibenden Elemente 4, 6, 7, 12, 13 sind
in 4 dargestellt.
-
Das
weitere Verfahren wird im Folgenden anhand des in 5 dargestellten
Objektes 4 beschrieben.
-
Wie 6 entnommen
werden kann, wird das Objekt 4 von ein Rechteck bildenden
Seitenlinien 26, 27, 28, 29 umrahmt.
Ausgehend von jeder Seitenlinie wird das Objekt 4 dann
abgetastet. Beginnend am Anfang einer Seitenlinie wird das Objekt 4 dann Bildpunkt
für Bildpunkt
abgetastet. Hierbei wird der jeweils einer Seitenlinie am nächsten kommende Bildpunkt erfasst.
Durch das Abtasten des Objektes 4 von allen vier Seitenlinien 26, 27, 28, 29 entsteht die
in 6 dargestellte äußere Kontur 4a.
-
Zur
Reduktion von Daten wird aus einem Bereich von fünf nebeneinander liegenden
Bildpunkten jeweils der Bildpunkt ausgewählt (markiert), der dem das
Objekt umschließenden
Viereck am nächsten kommt.
Eine so entstehende Grobstruktur der Kontur des Objektes 4 ist
in 7 dargestellt.
-
Den
markierten Bildpunkten wird dann eine Gerade zugeordnet, die den
Verlauf der Bildpunkte angenähert
wiedergibt. Die Geraden sind in 8 mit den
Bezugszeichen 17 bis 25 versehen. Die Bildung
der Geraden 17 bis 25 wird später noch im Einzelnen erläutert.
-
Von
den Geraden 17 bis 25 werden dann die Geraden 17, 18, 23, 24 ausgewählt, die
sich unter einem rechten Winkel kreuzen.
-
Die
anhand des Objektes 4 vorstehend dargestellte Vorgehensweise
wird für
jedes verbliebene Objekt 4, 6, 7, 12, 13,
dessen Größe gleich
oder größer als
die vorgegebene Größe ist (vergleiche 4),
durchgeführt.
Die so insgesamt erhaltenen Schnittpunkte bzw. Ecken sind in 8 dargestellt.
-
Danach
werden die Geraden ermittelt, welche von wenigstens zwei anderen
Geraden unter einem rechten Winkel geschnitten werden, und der Abstand
der Schnittpunkte mit einem vorgegebenen Abstand verglichen. Ist
der Abstand der Schnittpunkte gleich oder größer als der vorgegebene Abstand,
bilden die Schnittpunkte die Ecken eines definierten rechtwinkligen
Eckelements 1a, 1b, 1c. Dies ist in 10 dargestellt.
-
Als
weiteres Kriterium kann noch hinzugenommen werden, dass die Länge der
Geraden durch die jeweils äußeren der
die jeweils betreffende Gerade bildenden Bildpunkte begrenzt wird und
sich die zwei anderen Geraden auf derselben Seite der Geraden befinden,
die sie schneiden bzw. auf der sie enden.
-
Nachdem
die Ecken der definierten Eckelemente 1a, 1b, 1c bekannt
sind, lässt
sich das Bildelement lokalisieren.
-
Im
Folgenden wird die Zuordnung der Geraden zu den markierten Bildpunkten
anhand der 11 bis 17 beschrieben.
-
In 11 ist
die äußere Kontur
eines Objektes durch entsprechende Bildpunkte 31, 32 dargestellt.
Zur Reduzierung des Rechenaufwands wird die Darstellung der Kontur
auf markante Bildpunkte 31 beschränkt. Die Bildpunkte 32,
die einen geringeren Informationsgehalt haben, werden im weiteren Verfahren
nicht berücksichtigt.
Zur Darstellung der Kontur mittels der markanten Bildpunkte 31 wird
die Kontur von einem Rechteck umschlossen und von jeder Seitenlinie
des Rechtecks abgetastet. Die Abtastung beginnt jeweils in einem
Eckpunkt des Rechtecks und verläuft
kontinuierlich in einem Abstand von einem Bildpunkt längs der
betreffenden Seitenlinie bis zum nächsten Eckpunkt des Rechtecks.
Bei der Abtastung werden Bereiche von beispielsweise fünf Bildpunkten
gebildet und es wird jeweils der Bildpunkt markiert, der der betreffenden
Seitenlinie des Rechtecks am nächsten
kommt. Durch Abtasten der Kontur von allen vier Seiten des Rechtecks
erhält man
die markanten Bildpunkte 31.
-
Wie 12 entnommen
werden kann, stellen die markanten Bildpunkte 31 die Kontur
in einem Raster dar. Zwischen zwei benachbarten markanten Bildpunkten 1 sind
jeweils Untervektoren 33 angeordnet.
-
Wie 13 entnommen
werden kann, werden jeweils zwischen zwei aufeinander folgenden Untervektoren 33a', 33a bis 33e Winkel α1 bis α5 gebildet.
Die zwischen zwei Untervektoren 33a', 33a bis 33e bestehenden
Winkel α1
bis α5 werden
jeweils mit einem Grenzwinkel verglichen. Ist der Winkel α2 bis α4 zwischen
zwei Untervektoren 33a bis 33d kleiner als der
Grenzwinkel, wird der zuletzt gebildete Untervektor 33c in
die Bildung eines Gesamtvektors 34a einbezogen und ein
weiterer an den zuletzt gebildeten Untervektor 33c angrenzender
Untervektor 33d zum Vergleich mit dem vorhergehenden Untervektor 33c hinzugenommen.
Ergibt der Vergleich des zwischen den beiden letzten Untervektoren 33c, 33d gebildeten
Winkels α4
mit dem Grenzwinkel, dass der zwischen den beiden Untervektoren 33 gebildete Winkel α4 kleiner
als der Grenzwinkel ist, wird der zuletzt hinzugenommene Vektor 33d zur
Bildung des Gesamtvektors 34a hinzugenommen.
-
Ergibt
der Vergleich, dass der zwischen den beiden zuletzt gebildeten Untervektoren 33d, 33e gebildete
Winkel α5
größer als
der Grenzwinkel ist, wird der zuletzt hinzugenommene Untervektor
nicht zur Bildung des Gesamtvektors 34a hinzugenommen und
der Gesamtvektor 34a aus den bisher gebildeten Untervektoren
gebildet. Dies ist in 14 dargestellt.
-
Wie 14 in
Verbindung mit 13 entnommen werden kann, ist
der Winkel α1
zwischen dem Untervektor 33a und dem vorhergehenden Untervektor 33a' größer als
der Grenzwinkel, weshalb ab dem Bildpunkt 32a ein neuer
Gesamtvektor 34a gebildet wird. Des Weiteren kann 14 in
Verbindung mit 13 entnommen werden, dass der
Winkel α2
zwischen dem Untervektor 33a und dem Untervektor 33b,
der Winkel α3
zwischen dem Untervektor 33b und dem Untervektor 33c und
der Winkel α4
zwischen dem Untervektor 33c und dem Untervektor 33d jeweils
kleiner als der Grenzwinkel ist. Der Winkel α5 zwischen dem Untervektor 33e und
dem Untervektor 33d hingegen ist wieder größer als
der Grenzwinkel, so dass der Untervektor 33e nicht mehr zur
Bildung eines Gesamtvektors 34a hinzugenommen wird. Somit
wird ein Gesamtvektor 34a gebildet, der vom ersten Bildpunkt 32a ausgeht
und im letzten hinzugenommenen Bildpunkt 32e endet.
-
Der
letzte Bildpunkt 32e bildet einen neuen ersten Bildpunkt,
von dem der Untervektor 33e ausgeht. Ein Vergleich des
Untervektors 33f mit dem Untervektor 33e sowie
ein Vergleich des Untervektors 33g mit dem Untervektor 33f hat
jeweils ergeben, dass der zwischen diesen Vektoren gebildete Winkel α kleiner
als der Grenzwinkel ist, so dass die Untervektoren 33e, 33f, 33g zur
Bildung eines weiteren Gesamtvektors 34b verwendet werden.
-
Auf
die vorstehend beschriebene Weise werden aus allen verbleibenden
Bildpunkten der Kontur weitere Gesamtvektoren 34c, 34d und 34e gebildet, wobei
der letzte Untervektor 33a' unmittelbar
einen Gesamtvektor bildet.
-
Statt,
wie zuvor beschrieben, aufeinander folgende Untervektoren miteinander
verglichen werden, können
aus den vorhandenen Bildpunkten bzw. Untervektoren Summenvektoren
gebildet werden, welche einem Vergleich zugrunde gelegt werden können. So
lässt sich 15 entnehmen,
dass bei der Hinzunahme des Bildpunkts 32d ein vom ersten Bildpunkt 32a ausgehender
und im zuletzt hinzugenommenen Bildpunkt 32d endender Gesamtsummenvektor 35d gebildet
wird. Der Gesamtsummenvektor 35d wird mit dem vom vorletzten
hinzugenommenen Bildpunkt 32c ausgehenden und im letzten hinzugenommenen
Bildpunkt 32d endenden Untervektor 33c verglichen.
D. h., es wird geprüft,
ob der zwischen dem Untervektor 33c und dem Gesamtsummenvektor 35d bestehende
Winkel α6
größer als ein
vorgegebener Grenzwinkel ist. Ist dies nicht der Fall, wird ein
weiterer Bildpunkt 32e hinzugenommen und der Vorgang wiederholt
sich, und zwar so lange, bis der zwischen dem betreffenden jeweiligen
Untervektor und dem jeweiligen Gesamtsummenvektor bestehende Winkel
größer als
der vorgegebene Grenzwinkel ist.
-
Wie 16 entnommen
werden kann, kann der vorhergehende Vektor als ein aus vorhergehenden
gebildeten Untervektoren gebildeter Teilsummenvektor gebildet werden.
Der Teilsummenvektor 36c geht vom ersten Bildpunkt 32a aus
und endet im vorletzten hinzugenommenen Bildpunkt 32c.
Der zwischen dem Teilsummenvektor 36c und dem vom vorletzten
hinzugenommenen Bildpunkt 32c ausgehenden und im letzten
hinzugenommenen Bildpunkt 32d endenden Untervektor 33c bestehende
Winkel α7
wird mit einem vorgegebenen Grenzwinkel verglichen. Ist der Winkel α7 größer als
der Grenzwinkel, wird ein weiterer Bildpunkt 32e hinzugenommen
und ein neuer Teilsummenvektor, der vom ersten Bildpunkt 32a ausgeht
und im dann vorletzten Bildpunkt 32d endet, gebildet und
dem dann erneut stattfindenden Vergleich mit dem vom vorletzten
hinzugenommenen Bildpunkt 32d ausgehenden und im letzten hinzugenommenen
Bildpunkt endenden Untervektor 33d zugrunde gelegt. Ist
der dann gebildete Winkel größer als
der Grenzwinkel, wird der zuletzt gebildete Teilsummenvektor zum
Gesamtvektor.
-
Wie 17 entnommen
werden kann, kann auch der zwischen einem Gesamtsummenvektor 37d und
einem Teilsummenvektor 37c gebildete Winkel α8 zum Vergleich
mit einem vorgegebenen Grenzwinkel genommen werden. Ist der Winkel α8 kleiner
als der Grenzwinkel, wird ein weiterer Bildpunkt 32e hinzugenommen
und ein neuer Gesamtsummenvektor sowie ein neuer Teilsummenvektor gebildet
und der zwischen den beiden Vektoren bestehende Winkel zum erneuten
Vergleich mit dem Grenzwinkel verwendet.