-
Die
Erfindung betrifft ein Verfahren gemäß dem Oberbegriff des Anspruches
1.
-
Bei
einer Vielzahl von Gegenständen,
die mittels einem bildgebenden Verfahren abgebildet werden, stellt
sich das Problem, die Oberfläche
des Gegenstandes bildpunktweise bzw. im Hinblick auf eine Vielzahl
von einzelnen Bildpunkten überprüfen zu müssen. Eine Überprüfung der
aufgenommenen Bilder erfordert einen ausgesprochen umfangreichen Rechenaufwand,
insbesondere wenn eine Mehrzahl von Merkmalen jedes aufgenommenen
Bildpunktes überprüft werden
muss bzw. die Anzahl der zu überprüfenden Gegenstände pro
Zeiteinheit groß ist.
Des weiteren soll ein derartiges Prüfverfahren eine möglichst
sichere Aussage über
jeden geprüften
Bildpunkt liefern. Eine solche Aussage wird entweder für eine weitere
Beurteilung des aufgenommenen Gegenstandes herangezogen oder für sich selbst
als Bewertung des Gegenstandes angesehen.
-
Erfindungsgemäß werden
diese Aufgaben mit den im Kennzeichen des Patentanspruches 1 angeführten Merkmalen
gelöst.
-
Mit
dieser Vorgangsweise wird ein mit einfacher Hardware rasch erhaltenes
zuverlässiges
Prüfungsergebnis
erstellt, das eine Auswertung oder Beurteilung einem Mehrzahl von
Merkmalen der einzelnen Bildpunkte zulässt und die Möglichkeit
bietet, eine Vielzahl von Gegenständen innerhalb kürzester Zeit
zu bewerten. Das Prüfergebnis
stützt
sich dabei auf die für
die Bildpunkte des zu prüfenden
Objektes ermittelten Merkmalsvektoren und den Vergleich dieser Merkmalsvektoren
mit einem Sollbereich. Die Erstellung des Sollbereiches kann vor
Durchführung der
Prüfung
mit entsprechend hoher Genauigkeit vorgenommen werden; die Überprüfung der
Bildpunkte des zu prüfenden
Gegenstandes kann sehr rasch vorgenommen werden, da der rechnerische
Teil der Überprüfung, ob
ein Merkmalsvektor eines Bildpunktes des Gegenstandes in den Sollbereich
fällt,
mit einfacher Hardware rasch durchgeführt werden kann.
-
Bei
der erfindungsgemäßen Vorgangsweise wird
ein Sollbereich erstellt. Dieser Sollbereich wird durch ein einen
Körper,
d.h. eine Ellipse, eine Ellipsoid oder eine Hyperellipsoid bestimmt.
Ein Ellipsoid ist durch einen Mittelwertvektor und eine Kovarianzmatrix
beschrieben: Der Mittelwertvektor gibt die Lage des Mittelpunktes
im Merkmalsraum an; die Kovarianzmatrix beschreibt die Orientierung
und Ausdehnung.
-
Üblicherweise
werden den einzelnen Bildpunkten drei Parameterwerte, z.B. zu mischende Farbwerte,
wie z.B. Rot, Grün
und Blau, zugeordnet. In diesem Fall wird der Sollbereich durch
das von einem Ellipsoid eingeschlossene Volumen bestimmt. Im einfachsten
Fall liegt dieses Ellipsoid vollständig im gültigen Wertebereich der Merkmale
und der Sollbereich entspricht dem Ellipsoid. Das Ellipsoid kann jedoch
auch aus dem Wertebereich der Merkmale hinausragen, z.B. in den
Bereich negativer Rot-, Grün- oder
Blauwerte. In diesen Fällen
ist der Sollbereich beschrieben durch ein Ellipsoid welches mit
der/den entsprechenden Grundebenen geschnitten wird.
-
Zu
Beginn der erfindungsgemäßen Vorgangsweise
wird eine vorgegebene Anzahl von Muster- bzw. Sollwertgegenständen mit
einer Bildverarbeitungseinheit aufgenommen bzw. werden digitale Bilder
der Mustergegenstände
erstellt. Für
eine vorgegebene Anzahl von Bildpunkten aller von den Muster- bzw.
Sollwertgegenständen
aufgenommenen Bilder wird jeweils ein Merkmalsvektor erstellt. Dazu wird
derart vorgegangen, dass auf einer vorgegebenen Anzahl von Mustergegenständen ein
und derselbe Bildpunkt bzw. ein Bildpunkt mit gleicher Adresse bzw.
gleichen Koordinaten auf allen Mustergegenständen ausgewählt wird. Für diesen festgelegten Bildpunkt
werden für
jeden Mustergegenstand die Merkmale ermittelt und zu einem Merkmalsvektor
zusammengestellt. Dies bedeutet, dass eine Vielzahl von Merkmalsvektoren
erstellt wird, die der Anzahl der aufgenommenen Mustergegenstände entspricht. Da
die Merkmalsvektoren ein und desselben Bildpunktes auf den einzelnen
Mustergegenständen
voneinander mehr oder weniger abweichen bzw. unterschiedliche Ausprägungen besitzen,
ergibt sich eine Punktwolke bzw. eine Menge an Merkmalsvektoren mit
mehr oder weniger großen
Merkmalsunterschieden im Merkmalsraum, dessen Dimension durch die Anzahl
der Merkmale definiert ist. Dieser Bildpunkt, der auf den Mustergegenständen festgelegt
wird, entspricht einem Bildpunkt auf dem zu prüfenden Gegenstand bzw. der
Bildpunkt am Gegenstand besitzt ein Pendant mit gleicher Adresse
bzw. gleichen Koordinaten auf dem Mustergegenstand.
-
Für jeden
Bildpunkt des zu prüfenden
Gegenstandes wird im dreidimensionalen Raum ein Ellipsoid im Merkmalsraum
festgelegt. Im zweidimensionalen Raum ergibt sich eine Ellipse;
im höher
dimensionierten Raum ein Hyperellipsoid. Dabei kann für jeden
Bildpunkt ein eigenes Ellipsoid, beschrieben durch den Parametersatz
aus Mittelwertvektor und Kovarianzmatrix, oder für eine Anzahl von Bildpunkten
durch ein repräsentatives
Ellipsoid oder aber auch durch eine Teilmenge des Parametersatzes festgelegt
werden. Zwei Teilmengen des Parametersatzes können demnach die mit dem Mittelwertvektor verbunden
Parameter und die in der Kovarianzmatrix enthaltenen Parameter sein;
in diesem Fall wird jeder Bildpunkt durch einen eigenen Mittelwertvektor
charakterisiert und mehrere Bildpunkte teilen sich die Parameter
ein und derselben Kovarianzmatrix.
-
In 1 ist
eine Anzahl von sogenannten "Trainingspixel" eingezeichnet, d.h.
eine Anzahl von zu einem Bildpunkt des Gegenstandes gehörenden Merkmalsvektoren,
die von den zugeordneten Bildpunkten auf den einzelnen Mustergegenständen ermittelt
wurden. Diese Trainingspunkte stammen somit von einer Anzahl von
Muster- bzw. Sollwertgegenständen
und besitzen in der Regel unterschiedliche Merkmalswerte. Die dargestellte
Punktwolke gibt somit die zulässige
Variation der Merkmalswerte für einen
Bildpunkt wieder. Im vorliegenden Fall wurde ein und derselbe Bildpunkt
von 95 Muster- bzw. Sollwertgegenständen aufgenommen.
-
Das
dargestellte Diagramm ist zur Erläuterung auf zwei Dimensionen
reduziert und betrifft als Merkmale nur die Farbwerte Grün (G) und
Rot (R). Der Sollbereich wird in der Abbildung durch die Schwellwerte
Gh und Gl für
den Grünwert
und Rl und Rh für
den Rotwert beschrieben. Die Punkte bzw. Merkmalsvektoren der Merkmalswolke,
die maximale und minimale Werte in R bzw. G annehmen definieren
die Schwellwerte Rl und Rh bzw. Gl und Gh. Der durch Paare von Geraden,
bzw. Paaren von Ebenen, begrenzte zweidimensionale Körper, d.h.
Fläche, stellt
den Sollbereich dar.
-
In 1 entspricht
jeder dargestellte Punkt einem Rot-Grün-Wertepaar
bzw. Merkmalsvektor, das bzw. der in einer Aufnahme des Bildpunktes
am Muster- bzw. Sollwertgegenstand gemessen wurde. Alle von den
Muster- bzw. Sollwertgegenständen
aufgenommenen Bildpunkte werden zur Ermittlung der Merkmalsvektoren
zweckmäßigerweise
an denselben Bildpunkten des Aufnahmesensors abgebildet. Der Sollbereich,
in dem Rot-Grün-Wertpaare
bzw. die Merkmalsvektoren als ordnungsgemäß angesehen werden, wird aus
der Wolke der Trainingspunkte bzw. der Merkmalsvektoren gebildet
und wenn man, wie zuvor ausgeführt,
annimmt, dass alle Rot-Werte zwischen dem minimalen und maximalen
Rotwert und alle Grün-Werte
zwischen dem minimalen und maximalen Grünwert erlaubt sind, ergibt
sich ein rechteckiger Bereich, der in 1 eingezeichnet
ist.
-
Allerdings
beschreibt dieser rechteckige, durch achsparallele Geraden begrenzte
Bereich die Wolke der Trainingspunkte bzw. den Sollbereich nicht
sonderlich gut bzw. ist zu groß bzw.
zu permissiv. Insbesondere Bereiche in der linken oberen und rechten
unteren Ecke des Rechtecks wären
erlaubt, sind aber von den erhaltenen Trainingspunkten bzw. Merkmalsvektoren
relativ weit entfernt und würden daher
für einen
Betrachter des Gegenstandes als fehlerhaft bewertet werden.
-
Aus
diesem Grund ist es sinnvoll, den erlaubten Sollbereich enger einzugrenzen,
wozu insbesondere eine Vorgabe der Anzahl und Richtung der Achsvektoren
zielführend
ist, welche der tatsächlichen
Erstreckung der Punktewolke besser gerecht wird. Aus 2 erkennt
man, dass das einschließende
Polygon der Punktwolke besser gerecht wird. Das einschließende Polygon
entspricht der konvexen Hülle
der Punktwolke. Zur Berechnung der konvexen Hülle kann der Quickhull Algorithmus
herangezogen werden (Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm
for convex hulls," ACM Trans.
on Mathematical Software, 22(4): 469–483, Dec 1996). Der Nachteil
bei der Verwendung einer konvexen Hülle ist der nicht vorhersehbare
Aufwand bei der Prüfung
eines Bildpunktes. Im schlimmsten Fall muss, wenn n die Anzahl Trainingspixel
ist, mit n-1 den Sollbereich begrenzenden, nicht achsparallelen,
Geraden verglichen werden.
-
3 zeigt,
dass durch eine Verwendung einer Ellipse im gezeigten zweidimensionalen
Fall, eine bessere Nachbildung des Verlaufs der Punktewolke als
in 1 erfolgen kann. Die Berechnung der Parameter
der Ellipse, d.h. die Bestimmung der Parameterwerte für Mittelwertvektor
und Kovarianzmatrix kann durch direkte Berechnung aus der Stichprobe,
d.h. der Menge der Trainingspixel erfolgen, wozu vorgesehen ist,
dass zur Ermittlung des Sollbereiches der Mittelpunktvektor und/oder
die Kovarianzmatrix rechnerisch ermittelt oder durch eine statistische
Schätzung
ermittelt werden. Die Parameterermittlung kann auch durch Anwendung
des Minimax Algorithmus geschehen (M.I. Schlesinger and V. Hlavac.
Ten lectures on statistical and structural pattern recognition.
Kluwer Academic Publishers, 2002). Dazu ist vorgesehen, dass zur
Ermittlung des Mittelpunktvektors und der Kovarianzmatrix eine Gewichtung
der einzelnen Merkmalsvektoren erfolgt, wobei den im Randbereich
des Sollbereichs liegenden Punkten weniger Gewicht zugemessen wird.
-
Es
wird nochmals bemerkt, dass die 1, 2 und 3 eine
Reduktion der erfindungsgemäßen Vorgangsweise
auf den zweidimensionalen Raum darstellen. Sofern im drei- bzw.
n-dimensionalen
Raum vorgegangen wird, ergeben sich drei- bzw. n-dimensionale Merkmalsvektoren
und ein Ellipsoid bzw. Hyperellipsoide.
-
Eine
Verbesserung der Schätzung
des Sollbereichs wird durch gleichzeitige Elimination von Ausreißern erreicht.
In diesem Fall wird angenommen, die Stichprobe der Trainingspixel
ist nicht zur Gänze
repräsentativ.
Ein Verfahren dazu ist das Volumen des Sollbereichs, bzw. die Fläche im zweidimensionalen
Fall, auf einen Bruchteil des Gesamtvolumens zu reduzieren. Ein
sinnvoller Wert ist z.B. eine Reduktion des Sollbereiches auf 95%
des ursprünglichen
Volumens. 4 zeigt ein Beispiel für eine Reduktion
des Sollbereiches auf 95% des Volumens.
-
Eine
weitere Möglichkeit
besteht in der Verwendung eines Mehrschrittverfahrens, wobei im
ersten Schritt ein Sollbereich ermittelt wird, in einem zweiten
Schritt jene Trainingspixel am Rand des Sollbereiches entfernt werden,
und im letzten Schritt aus den verbleibenden Trainingspixel eine neuer
Sollbereich ermittelt wird. Als Randpixel wird hier ein Bruchteil
r der Stichprobe angesehen und aus den verbleibenden Bruchteil von
1-r Trainingspixel wird der Sollbereich des letzten Schrittes bestimmt.
Ein sinnvoller Wert für
die zur Schätzung
des endgültigen
Sollbereiches herangezogenen Pixel ist 95% der Stichprobe. 5 zeigt
ein Beispiel für
eine Reduktion des Sollbereiches auf 95% der Stichprobe.
-
Die
Prüfung
eines Bildpunktes besteht in der Ermittlung ob der mit diesem Punkt
verbundene Merkmalsvektor innerhalb des Sollbereiches liegt. Ist der
Sollbereich durch eine Ellipse, ein Ellipsoid oder ein Hyperellipsoid
beschrieben, so genügt
es zur Feststellung der Distanz die Mahalanobisdistanz für diesen
Bildpunkt zu berechnen und mit der Mahalanobisdistanz des Umfanges
der Ellipse bzw. der Hülle
des Ellipsoids bzw. Hyperellipsoids zu vergleichen. Die Mahalanobisdistanz
beinhaltet alle Parameter des Sollbereiches, d.h. den Mittelwertvektor μ und die
Kovarianzmatrix Σ.
Die Mahalanobisdistanz d für
einen Merkmalsvektor x → ist definiert als d = (x → – μ)Σ(x → – μ) und wird verglichen mit der
Mahalonisdistanz D für
den Rand des Sollbereiches, d.h. die Mahalanobisdistanz für die Hülle des
Ellipsoids. Ein Punkt wird als in den Sollbereich fallend klassifiziert, d.h.
er hat dann die Prüfung
bestanden, wenn d ≤ D. Merkmalsvektoren,
die auf der Hüllkurve
bzw. -fläche liegen,
können
als zum Sollwertbereich gehörend klassifiziert
werden.
-
Die
Ermittlung der Mahalonisdistanz wird erläutert in P.C. Mahalanobis, "On the generalized
distance in statistics",
Proceedings of National Institute of Sciences of India, Vol. 2,
pages 49–55,
oder J.D. Jobson "Applied
Multivariate Data Analysis",
Volume II, Categorical and Multivariate Methods, Chapter 7.1.3:
Geometric Interpretation of Data Matrices, pages 140–144, Springer,
1994, oder Luc Devroye, Laszio Györfi, Gabor Lugosi "A Probabilistic Theory of Pattern
Recognition", Chapter
3.8, The Mahalanobis Distance, pages 30–31, Springer, 1996.
-
Mit
der erfindungsgemäßen Vorgangsweise kann
der Anforderung entsprochen werden, dass eine Überprüfung eines Gegenstandes extrem schnell
vorgenommen werden muss. Es wird dabei mit einer dezidierten Hardware
gearbeitet, auf der jedoch der Speicherbedarf sehr begrenzt ist,
sodass nur wenige Parameterwerte für die einzelnen Bildpunkte
vorgegeben werden können.
-
Eine
Approximation des Sollbereiches durch einen Körper bzw. eine Hüllkurve
bzw. -fläche,
der bzw. die die Wolke der Merkmalsvektoren möglichst eng umschließt bzw.
diese Punktwolke zur Gänze enthält und mit
wenigen Parameterwerten beschreibbar ist, ist vorteilhaft. Ein konvexer
Körper
ist dazu gut geeignet. Weiters ist die Idee der Darstellung eines
Sollbereiches durch ein umschließendes Ellipsoid äquivalent
zu der Sichtweise der Repräsentation einer
Stichprobe durch eine multivariate Normalverteilung. Die Normalverteilungsannahme
ist in der Regel eine gute Vorgangsweise für die Prüfung von Gegenständen die
durch Merkmale gekennzeichnet welche eine Streuung um einen Sollwert
aufweisen.
-
Die
Bildprüfung
erfolgt in einer an die Bildaufnahmeeinheit bzw. deren Bildsensor
angeschlossenen Recheneinheit, vorzugsweise realisiert durch für die Aufgabe
optimierte elektronische Schaltkreise. Dabei spielt der für die Bildprüfung benötigte Speicherplatz
eine wesentliche Rolle. Es ist vorteilhaft, eine suboptimale Lösung für die Prüfung der
Farbbildpunkte zu akzeptieren und dafür Speicherplatz zu sparen,
indem dieselben Parameter für
verschiedene Bildpunkte mit gleichen oder ähnlichen Parametersätzen verwendet
werden. Besonders vorteilhaft ist es, die Orientierung und Streuung,
d.h. die Kovarianzmatrix, für
eine Gruppe von Bildpunkten gemeinsam vorzugeben und nur den Mittelwertvektor
für jeden
Bildpunkt individuell zu speichern.
-
Im
dreidimensionalen Merkmalsraum sind bei Verwendung eines Ellipsoids
10 Parameter pro zu prüfenden
Bildpunkt nötig.
Diese Parameter sind die 3 Einträge
des Mittelwertvektors μ,
6 Werte die sich aus der symmetrischen 3 × 3 Kovarianzmatrix Σ ergeben
und ein skalarer Wert der die Mahalonobisdistanz der Ellipsoidhülle D angibt.
-
Es
hat sich als vorteilhaft erwiesen, eine Gruppe von Bildpunkten zusammenzufassen
und für diese
Gruppe einen gemeinsamen Satz der 6 Parameter der Kovarianzmatrix Σ zu speichern
und für
jeden Bildpunkt in der Gruppe einen individuellen Satz von 4 Parametern
zur Festlegung des Mittelwertvektors μ und der Mahalanobisdistanz
der Ellipsoidhülle D
vorzusehen.
-
Der
Rechenaufwand zur Prüfung
selbst, d.h. die Berechnung der Mahalanobisdistanz d und Vergleich
dieser mit dem Wert der Mahalanobisdistanz für den Rand des Sollbereiches
D, setzt sich pro Bildpunkt aus den folgenden Operationen zusammen:
3 Subtraktionen, 5 Additionen, 10 Multiplikationen und eine Vergleichsoperation.
-
Soll
die Prüfung
mit einer gewissen Toleranz versehen werden, so wird dies vorzugsweise
dadurch erreicht, dass der Parameter D derart verändert wird,
dass das Ellipsoid bezüglich
des Volumens vergrößert wird.
Hier kann, ähnlich
der Einschränkung
des Sollbereichs auf Volumensanteile kleiner 100%, eine Vergrößerung des
Toleranzbereiches proportional dem Volumen größer als 100% angegeben werden.
-
Die
Zusammenfassung von Bildpunkten des zu prüfenden Gegenstandes zu Gruppen
mit teilweise oder gänzlich
gleichen Parametern kann nach unterschiedlichen Gesichtspunkten
erfolgen:
- 1) Die Punkte können nach Bildregionen, z.B. nach
bestimmten Bildmotiven zusammengefasst werden. Das hat den Vorteil,
dass sich vorgegebene Toleranzen (siehe oben) jeweils auf eine Gruppe
von Bildpunkten beziehen, denen ein Betrachter eine gemeinsame Bedeutung
zuordnet.
- 2) Die Bildpunkte können
nach einer verfahrenstechnischen Gemeinsamkeit zusammengefasst werden
(bei Banknoten z.B. Tiefdruck, Offsetdruck, OVI-Druck usw.)
- 3) Die Bildpunkte können
nach farblichen Ähnlichkeiten
zusammengefasst werden.
- 4) Die Bildpunkte können
nach ähnlichen
Orientierungen und Streuungen zusammengefasst werden.
-
Ferner
sind Kombinationen aus obigen Gesichtspunkten, besonders einer der
Punkte 1 bis 3 mit 4, vorteilhaft.
-
Die
Erfindung betrifft ferner ein Softwareprodukt entsprechend den Merkmalen
des Anspruches 9.