Verfahren und Vorrichtung zur Bildverarbeitung

Beschreibung

Die Erfindung betrifft allgemein Vorrichtungen und Verfahren zur Bildverarbeitung. Insbesondere betrifft die Erfindung ein Verfahren und eine Vorrichtung zur Bildverarbeitung, bei welcher aus den Bilddaten

Konturpunkte ermittelt und anhand der Konturpunkte eine Segmentierung vorgenommen wird, bei welcher zusammengehörende Konturpunkte für die Weiterverarbeitung zu Objekten zusammengefasst werden.

Für verschiedenste technische Anwendungen werden heutzutage Bildverarbeitungssysteme eingesetzt, um eine automatische Objekterkennung zu realisieren. Beispielsweise orientieren sich Industrieroboter vielfach anhand von verarbeiteten Bilddaten, welche es einem Roboter ermöglichen, ein Objekt und dessen Lage und Position zu erkennen. Um eine zuverlässige Erkennung von Objekten zu gewährleisten, wird jedoch bisher eine große Menge an "a priori"-Wissen über die zu erkennenden Objekte benötigt. Damit geht auch oft einher, daß für das jeweilige technische Einsatzgebiet speziell zugeschnittene Software-Lösungen erstellt werden. Es ist offensichtlich, daß eine derartige Herangehensweise sehr aufwendig und entsprechend teuer ist. Vielfach schließen sich dabei auch an eine technische Umsetzung auch noch langwierige Lernprozesse an, mit welchen das System für die Erkennung ausgewählter Objekte trainiert wird.

Noch ein weiteres Manko ist, daß für die Bilderkennung speicherintensive und komplizierte Berechnungen erforderlich sind. Eine Echtzeit-Erkennung ist auf diese Weise daher kaum zu realisieren.

Der Erfindung liegt daher die Aufgabe zugrunde, eine technische Lösung bereitzustellen, mit der eine Bilderkennung in Echtzeit erfolgen kann und die mit nur sehr wenig oder sogar keinerlei a-priori-Information in der Lage ist, eine zutreffende und zuverlässige Erkennung von Objekten durchzuführen. Diese Aufgabe wird bereits in höchst überraschend einfacher Weise durch eine Vorrichtung und ein Verfahren, wie sie in den unabhängigen Ansprüchen angegeben sind, gelöst. Vorteilhafte Ausgestaltungen und Weiterbildungen der Erfindung sind in den jeweiligen abhängigen Ansprüchen angegeben.

Dazu ist eine Bildverarbeitungsvorrichtung mit einer in Form von Hardware integrierter Einrichtung zur Segmentierung von Bilddaten und einer ebenfalls in Form von Hardware integrierter Einrichtung zur Bestimmung und Verarbeitung von Konturpunkten, dadurch gekennzeichnet, daß die Einrichtung zur Segmentierung von Bilddaten eine Einrichtung zur Bestimmung von Eckpunkten von Konturen aus von der Einrichtung zur Bestimmung und Verarbeitung von Konturpunkten bereitgestellten Listendaten mit Konturpunkten umfasst, wobei die Einrichtung zur Bestimmung von Eckpunkten von Konturen eine Einrichtung zur Durchführung des folgenden Algorithmus umfasst: -zu jedem Punkt p einer Menge aufeinanderfolgender

Konturpunkte einer Kontur werden Tripel mit Punkten (p ^~ , p, P ⁺ ) gebildet, wobei die Punkte p ^" , p ⁺ Konturpunkte darstellen, die in beiden Richtungen entlang der Kontur vom Punkt p beabstandet sind, -zu diesen Punkten wird getestet, ob die Bedingungen

: i ) d ² _min < I p-P ⁺ I ² ≤ d ²

( ü ) d min < I p-P ^" I ² < d ² und

( üi ) α < Cmax erfüllt sind, wobei d ² _min , d ² _max und α _max gesetzte vorbestimmte Parameter sind, und wobei für den öffnungswinkel α gilt:

wobei a den Abstand der Punkte p und p ⁺ , b den Abstand der Punkte p und p ^~ , und c den Abstand der Punkte p ⁺ und p ^~ bezeichnen, und wobei die Bedingungen (i), (ii) und (iii) für eine Reihe von zu p beiderseits benachbarten Punkten getestet werden,

-der kleinste öffnungswinkel α oder eine daraus abgeleitete Größe aus der Menge der getesteten Tripel mit Punkten (p ^~ , p, p ⁺ ), welche alle Bedingungen (i) , (ii) und (iii) erfüllen, wird ausgewählt und dem Punkt p zugeordnet, -ein Punkt p wird aussortiert, wenn zu diesem dieser ein benachbarter Punkt p' existiert, für welchen die Bedingungen (i), (ii) und (iii) erfüllt sind und einen kleineren öffnungswinkel α aufweist.

Unter einem benachbarten Punkt p' wird dabei ein Punkt verstanden, welcher innerhalb einer vorbestimmten Umgebung um den Punkt p entlang der Kontur angeordnet ist. Beispielsweise kann als Bedingung gesetzt werden

!p ² -p' ² !< d^ax-

Durch Setzen des Parameters d ² _max wird vermieden, daß vermeintlich kleine öffnungswinkel zwischen weit entfernten Punkten bei stark gekrümmten Konturen zugeordnet werden. Der Parameter d ² _min gibt die Auflösung an, mit welcher die Kontur, beziehungsweise die Konturpunkte abgetastet wird.

Ein günstiger zulässiger Bereich für |p-p ⁺ | ² zur Erzielung einer effektiven Abtastung wird weiterhin erreicht, wenn dmax ≥ d _min + 1, etwa zum Beispiel d _max = d _min + 2 gesetzt wird. Die Parameter d _max , d,m _n und α _ma χ müssen nicht fest durch die Hardware vorgegeben sein, vielmehr kann die

Bildverarbeitungsvorrichtung auch dazu ausgebildet sein, wenigstens einen dieser Parameter wählbar oder variierbar zu setzen.

Es hat sich gezeigt, daß der erfindungsgemäße Algorithmus besonders einfach und effektiv in Hardware, vorzugsweise in FPGA- oder ASIC-Bausteine implementiert werden kann. Insbesondere ist auch der benötigte Speicher vergleichsweise klein. Dies zusammengenommen führt zu einer sehr schnellen Erkennung von Eckpunkten von Objekten zwischen geradlinigen Segmenten und einer unter Verwendung dieser Punkte möglichen weitergehenden Segmentierung. Insbesondere können dann auch schnell Verbindungen zwischen den Eckpunkten gebildet und weiterverarbeitet werden.

Für die Auswahl der Tripel, beziehungsweise der Punkte p ⁺ , p ^" können verschiedene Auswahlvorschriften eingesetzt werden. Besonders effektiv, insbesondere auch hinsichtlich der Anzahl der benötigten Addierer und Multiplexer ist es jedoch, wenn Tripel (p, p ⁺ , p ^~ ) nacheinander mit

Konturpunkten p ⁺ , p ^" gebildet und auf Erfüllung der Bedingungen (i), (ii), und (iii) getestet werden, die entlang der Kontur fortschreitend weiter vom Konturpunkt p entfernt sind. Dabei ist es weiterhin günstig für die Rechengeschwindigkeit bei ausreichender Genauigkeit der Bestimmung von Eckpunkten, wenn der Test der Bedingungen (i) , (ii) , und (iii) für einen gegebenen Konturpunkt p abgebrochen wird, sobald eine der Bedingungen (i), (ii),

und (iii) für ein Tripel (p, p ⁺ , p ^~ ) nicht mehr erfüllt ist.

Als vorteilhaft für eine fehlerarme Segmentierung für eine Vielzahl von Bedingungen hinsichtlich der Bildauflösung und des Bildkontrasts hat es sich weiterhin erwiesen, wenn in der Einrichtung zur Bestimmung von Eckpunkten von Konturen der Parameter d^ _n auf einen Wert von d^ _n ≥ 4 gesetzt ist. Für den Parameter α _max sind weiterhin Werte von α _max < 160° günstig.

Wenn die Bedingungen (i) bis (iii) für eine große Anzahl benachbarter Konturpunkte erfüllt bleibt, steigt der Rechenaufwand zur Bestimmung des minimalen öffnungswinkel für den Konturpunkt p. Es ist daher von Vorteil für den Rechenaufwand und die Geschwindigkeit der Analyse der Eckpunkte, wenn die Einrichtung zur Bestimmung von Eckpunkten von Konturen ausgebildet ist, für einen gegebenen Konturpunkt p zu jeder Seite entlang einer Kontur höchstens 7 Konturpunkte für die Tests der Bedingungen (i), (ii) und (iii) einzubeziehen. Mit anderen Worten wird der Test abgebrochen, wenn die Konturpunkte p+, p- jeweils sieben Konturpunkte vom Punkt p entfernt sind.

Unabhängig von der Objektsegmentierung sieht die Erfindung eine vorzugsweise integrierte Bildverarbeitungsvorrichtung mit einem oder mehreren Bildspeichern und zumindest einer integrierten Hardwareeinheit vor, die eingerichtet ist, die im Bildspeicher abgelegten Daten eines Digitalbildes abzutasten und Konturpunkte mit Subpixel-Genauigkeit zu ermitteln und als fortlaufende Listendaten in einem Speicher abzulegen. Die Bildverarbeitungsvorrichtung weist weiterhin eine Recheneinheit auf, welche eingerichtet ist, aus den im Speicher abgelegten Listendaten mithilfe eines

Rechenwerks die Verbindungswahrscheinlichkeiten zwischen jeweils zwei Konturpunkten unter Berücksichtigung des Abstands der Punkte zueinander zu ermitteln. Außerdem ist zumindest eine Recheneinheit, die nachfolgend als Klassifikator bezeichnet wird, vorgesehen, welche aus Mengen von berechneten Verbindungswahrscheinlichkeiten Teilmengen mit zumindest drei

Verbindungswahrscheinlichkeiten für mögliche Verbindungen zwischen zumindest drei benachbarten Konturpunkten, wovon einer ein zuvor bestimmter zentraler Konturpunkt ist, auswählt und für jede Teilmenge denjenigen zum zentralen Konturpunkt, beziehungsweise Zentralpunkt benachbarten Konturpunkt aussortiert, der eine mögliche Verbindung mit der geringsten Verbindungswahrscheinlichkeit zu einem benachbarten Konturpunkt aufweist, sofern die Verbindung nicht zwei zum Zentralpunkt benachbarte Punkte verbindet und im Anschluß daran in eine Konturpunktliste die nicht aussortierten Konturpunkte mit Konnektoren einträgt, welche die verbleibenden Verbindungen zum Zentralpunkt kennzeichnen.

Die Erfindung sieht außerdem ein Verfahren zur Ermittlung zusammenhängender Konturen in Bilddaten vor, welches insbesondere in einer wie vorstehend beschriebenen Bildverarbeitungsvorrichtung durchführbar ist, bei welchem aus den Bilddaten Konturpunkte ermittelt und die Verbindungswahrscheinlichkeiten möglicher Verbindungen von Konturpunkten zu benachbarten Konturpunkten errechnet werden, und wobei aus einer Menge von solchen Verbindungswahrscheinlichkeiten ein oder mehrere Teilmengen mit zumindest drei Verbindungswahrscheinlichkeiten für mögliche Verbindungen zwischen zumindest zwei Konturpunkten und einem benachbarten ausgewählten zentralen Konturpunkt analysiert und jeweils derjenige der zentralen Konturpunkt benachbarten Konturpunkte aussortiert wird, der eine

mögliche Verbindung mit der geringsten

Verbindungswahrscheinlichkeit zu einem der anderen Punkte aufweist, sofern die Verbindung nicht zwei zum Zentralpunkt benachbarte Punkte verbindet, und nach Abschluß dieser Analyse der Teilmengen in eine Liste in einem elektronischen Speicher Konturpunktdaten einträgt, welche Konnektoren umfassen, die zu einer Kontur gehörende Verbindungen zum Zentralpunkt kennzeichnen. Diese Konnektoren können dann weiterverarbeitet werden, indem anhand der Konnektoren die Konturpunkte zu Kontursegmenten zusammengefasst werden, die für die Objektverarbeitung und Objekterkennung dienen.

Unter benachbarten Konturpunkten werden im Sinne der Erfindung nicht etwa Konturpunkte zu direkt aneinandergrenzenden Pixeln verstanden, sondern vielmehr alle Konturpunkte innerhalb einer vorgegebenen Umgebung um den Zentralpunkt. Beispielsweise kann dies eine 5 x 5- Umgebung mit dem jeweiligen betrachteten Zentralpunkt in dessen Zentrum sein. Diese Menge an Konturpunkten wird dann auch als Nachbarschaft bezeichnet.

Die Ermittlung der Lage von Konturpunkten mit Subpixel- Genauigkeit zu einem Bildpunkt erfolgt dabei durch Berechnung aus der Lage des Bildpunktes und weiterer umgebender Bildpunkte.

Der erfindungsgemäße Auswahlvorgang, bei welchem jeweils Konturpunkte aus einer Menge aussortiert werden, welche die geringste Verbindungswahrscheinlichkeit zum Zentralpunkt aufweisen, bietet den Vorteil, sehr wenig Speicher zu benötigen. Insbesondere kann die Verarbeitung anhand von fortlaufenden Listendaten erfolgen. Der hierfür benötigte geringe Speicherbedarf ermöglicht mit geringem Aufwand an einzusetzender Hardware sogar eine Verarbeitung in

Echtzeit. Zudem lassen sich die oben beschriebenen Prozesse aufgrund ihrer Einfachheit leicht in Hardware-Bausteinen ohne aufwendige Software und periphere Beschaltung implementieren. Die erfindungsgemäße Vorrichtung kann daher sehr einfach als sehr kompakte integrierte Hardware- Bildverarbeitungsvorrichtung ausgeführt werden. Um den benötigten Speicher zu reduzieren, ist insbesondere auch die Weiterverarbeitung der Konturpunkte in Form von fortlaufenden Listendaten besonders vorteilhaft. Diese Listendaten enthalten vorzugsweise nur die

Bildpunktkoordinaten von relevanten Konturpunkten sowie Attributen der Umgebung und somit lediglich die für die Konturerkennung relevanten Daten. Demgemäß wird die Datenmenge auf diese Weise gegenüber den Originaldaten des Bildes auf ein Minimum reduziert. Das Aussortieren hat das Ziel, diejenigen Konturpunkte zu ermitteln, die zusammen mit dem jeweils betrachteten Zentralpunkt zur gleichen Kontur gehören.

Der Schritt des Auswählens von Konturpunkten für die

Weiterverarbeitung durch Aussortieren von Konturpunkten mit der geringsten Verbindungswahrscheinlichkeit zum Zentralpunkt kann auch folgendermassen veranschaulicht werden: Die Menge der um einen Zentralpunkt gruppierten Konturpunkte (=Nachbarschaftskandidaten) kann in einer Ebene bildhaft veranschaulicht werden, indem die Verbindungswahrscheinlichkeiten zwischen Konturpunkten durch Strecken dargestellt werden, wobei die Länge einer Strecke indirekt proportional zur Verbindungswahrscheinlichkeit ist. Es werden nun Polygone gebildet, welche als Eckpunkte den Zentralpunkt und zumindest zwei zum Zentralpunkt benachbarte weitere Konturpunkte enthalten. Anschließend wird derjenige der zum Zentralpunkt benachbarten Punkte entfernt, von welchem die längste Verbindung zu einem weiteren Punkt des Polygons

ausgeht. Dieses Verfahren kann dann je nach Anzahl der benachbarten Konturpunkte für alle zum Zentralpunkt benachbarten Konturpunkte wiederholt werden, bis eine gewisse Anzahl von Konturpunkten, je nach Anordnung der Punkte unter Umständen auch nur zwei Punkte inklusive des Zentralpunkts übrigbleibt und es sich keine Polygone mehr bilden lassen, in denen weitere Streichungen von Elementen stattfinden .

Dieser Auswahlvorgang des Klassifikators läßt sich besonders effektiv mit wenigen Rechenoperationen und geringem Aufwand an Hardware durchführen, wenn aus der Menge der Konturpunkte der Nachbarschaft des Zentralpunkts, beziehungsweise der zum Zentralpunkt benachbarten Konturpunkte jeweils eine Teilmenge als Tripel mit dem Zentralpunkt und zwei weiteren Konturpunkten mit den zugeordneten Verbindungswahrscheinlichkeiten gebildet wird und vorzugsweise von drei Komparatoren für die Verbindungswahrscheinlichkeiten die geringste Wahrscheinlichkeit ermittelt und jeweils der zum

Zentralpunkt benachbarte Konturpunkt, von welchem die Verbindung mit der geringsten Verbindungswahrscheinlichkeit innerhalb des Tripels ausgeht, aus einer Nachbarschaftsmenge der zum Zentralpunkt benachbarten Konturpunkte aussortiert wird, sofern die zugehörige

Verbindung nicht zwei zum zentralen Konturpunkt benachbarte Konturpunkte verbindet.

Die Konnektoren, die der Klassifikator nach dem Aussortieren in der Nachbarschaft belässt, werden in eine Konturpunktliste eingetragen und können dann die Indizes benachbarter Konturpunkte und die Verbindungswahrscheinlichkeiten zu benachbarten Konturpunkten sowie weitere Nachbarschaftsinformationen (Richtung DIR, Kontrast cont, Farbe) enthalten.

Werden die Konturpunkte wieder als auf einer Ebene mit durch die Verbindungswahrscheinlichkeiten modifizierten Koordinaten angeordnet betrachtet, so entspricht diese Vorgehensweise dem Bilden von Tripeln von Konturpunkten, deren Verbindungen dementsprechend ein Dreieck bilden. Es wird in diesem Dreieck nun die längste Seite bestimmt und derjenige zum Zentralpunkt benachbarte Konturpunkt gestrichen, von welchem die längste Seite ausgeht.

Der Vorgang des Aussortierens, beziehungsweise des Auswählens der verbleibenden Konturpunkte wird vorzugsweise zumindest einmal für die Menge der nicht aussortierten Konturpunkte wiederholt. Die Bildverarbeitungsvorrichtung, insbesondere der Klassifikator, der aus zumindest drei

Elementen für Verbindungen von zumindest zwei Konturpunkten zu einem ausgewählten zentralen Konturpunkt jeweils die Verbindung mit der geringsten Verbindungswahrscheinlichkeit aussortiert, kann insbesondere dazu eingerichtet sein, den Auswahl-Vorgang, bei welchem Konturpunkte mit möglichen Verbindungen mit der geringsten

Verbindungswahrscheinlichkeit aussortiert werden für jeden ausgewählten zentralen Konturpunkt zu wiederholen, bis keine weiteren zum zentralen Konturpunkt benachbarten Konturpunkte gestrichen, beziehungsweise aussortiert werden können.

Werden, wie es besonders bevorzugt ist, jeweils Tripel von Konturpunkten, beziehungsweise zugehörigen Verbindungswahrscheinlichkeiten für mögliche Verbindungen gebildet und eine geeignete Auslesereihenfolge der Konturpunkte beachtet, bei welcher die Teilmengen so gebildet werden, daß nur nächste Nachbarn von Konturpunkten, beziehungsweise die Verbindungswahrscheinlichkeiten zwischen diesen Punkten

enthalten sind, hat es sich im übrigen gezeigt, daß genau eine einmalige Wiederholung des Aussortierens für alle Tripel von Verbindungswahrscheinlichkeiten für mögliche Verbindungen zwischen nächst benachbarten Konturpunkten ausreicht, um zumindest in den allermeisten Fällen alle diejenigen Konturpunkte auszusortieren, die nicht zur selben Kontur wie der jeweils betrachtete Zentralpunkt gehören .

Beim Auswählen von Konturpunkten durch Aussortieren von Konturpunkten mit geringer Verbindungswahrscheinlichkeit können sich unter Umständen Mehrdeutigkeiten ergeben, die dazu führen, daß beispielsweise bei einem Tripel von Konturpunkten, der Klassifikator für die Verbindungswahrscheinlichkeiten keinen Konturpunkt aussortiert, obwohl die jeweils längsten Verbindungen, beziehungsweise die geringsten

Verbindungswahrscheinlichkeiten jeweils für Verbindungen zum Zentralpunkt bestehen. Dies ist insbesondere dann der Fall, wenn die Punkte mit durch die

Verbindungswahrscheinlichkeiten modifizierten Koordinaten ein gleichschenkliges Dreieck oder sogar ein gleichseitiges Dreieck bilden. Hier könnten zwar alle Konturpunkte übernommen werden, allerdings hat sich überraschend gezeigt, daß eine wesentlich bessere, um Artefakte verminderte Nachbarschaftsdefinition erfolgt, wenn eine Modulation auf die Verbindungswahrscheinlichkeit aufgeprägt wird, die einer Positionsverschiebung von Konturpunkten entspricht, die kleiner als der Pixelabstand ist.

Zwar werden hier die Daten für die

Verbindungswahrscheinlichkeiten verändert, was auch zu falschen Pfadentscheidungen über tatsächlich zu einer zusammenhängenden Kontur gehörenden Konturpunkten führen kann, allerdings hat es sich gezeigt, daß dies unschädlich

ist, da sich mögliche falsche Entscheidungen im Mittel neutralisieren. Eine einfache, bevorzugte Realisierung einer Modulation ist dabei die Veränderung der Pixel- Koordinaten von Konturpunkten. Ebenso möglich wäre es aber auch, innerhalb des Klassifikators die

Verbindungswahrscheinlichkeiten zu berechnen und dann diesen Verbindungswahrscheinlichkeiten eine Modulation aufzuprägen.

Im einfachsten Fall können Verbindungswahrscheinlichkeiten von Konturpunkten anhand des Abstands dieser Punkte zueinander ermittelt werden. Je weiter zwei Konturpunkte voneinander entfernt sind, desto geringer ist ihre Verbindungswahrscheinlichkeit. Es wird aber bevorzugt, weitere Attribute der Konturpunkte zu erfassen und in die

Berechnung der Verbindungswahrscheinlichkeit mit einfließen zu lassen.

Als günstig hat es sich dabei insbesondere erwiesen, wenn das Rechenwerk für die Verbindungswahrscheinlichkeiten zwischen Konturpunkten anhand des Abstands zwischen den

Konturpunkten und zumindest einem der Attribute Kontrast, Farbe und Richtung errechnet werden. Dazu ist gemäß einer Weiterbildung der Erfindung vorgesehen, daß die Recheneinheit, die eingerichtet ist, aus den im Speicher abgelegten Listendaten die Verbindungswahrscheinlichkeiten zwischen Konturpunkten zu ermitteln, die Verbindungswahrscheinlichkeiten zwischen Konturpunkten anhand des Abstands zwischen den Konturpunkten und zumindest einem der Attribute Kontrast, Farbe und Richtung errechnet. Eine Möglichkeit ist beispielsweise, anhand eines oder mehrerer Attribute den Wert einer Funktion der Werte dieses Attribute zu errechnen und eine Verbindungswahrscheinlichkeit nur dann zu berechnen, wenn der Wert der Funktion einen Schwellwert je nach Art der Funktion über- oder unterschreitet.

Ein Attribut kann dabei beispielsweise die mittlere Punktrichtung, die vom Konturpunktprozessor ausgegeben wird (der maximale Grauwertkontrats liegt in einer Antastrichtung), sein. Die mittlere Punktrichtung ist als Summe der Richtungsvektoren beider zu einem Konnektor gehörenden Konturpunkte definiert und steht in der Regel in guter Näherung senkrecht zur Richtung des Konnektors selbst. Weisen zwei Konturpunkte eine ähnliche Richtung der Kontur auf, steigt entsprechend die

Verbindungswahrscheinlichkeit, also die Wahrscheinlichkeit, daß die beiden Punkte tatsächlich zu einer gemeinsamen Kontur gehören. Ein weiteres Merkmal ist der Winkel zwischen der mittleren Punktrichtung und der Richtung des Konnektors. Dieser Winkel kann in besonders einfacher Weise über das Skalarprodukt der beiden Vektoren berechnet und in die Verbindungswahrscheinlichkeit einbezogen werden.

Der Kontrast kann insbesondere der Helligkeitsunterschied von zum Konturpunkt benachbarten Bereichen sein, die durch die Konturlinie getrennt sind. Weisen zwei Konturpunkte einen solchen ähnlichen Kontrast auf, steigt entsprechend die Wahrscheinlichkeit, daß die beiden Konturpunkte auf einer gemeinsamen Konturlinie liegen. Ist der Kontrast invers, dann handelt es sich zumeist um eine dünne Linie, deren in der Regel parallel in geringem Abstand laufende Konturen nicht verbunden werden dürfen, d.h. dass in diesem Fall die Verbindungswahrscheinlichkeit auf null gesetzt wird.

Gemäß dieser Ausführungsform der Erfindung kann daher die integrierte Recheneinheit, die eingerichtet ist, die im Bildspeicher abgelegten Daten eines Digitalbildes abzutasten und Konturpunkte mit Subpixel-Genauigkeit zu ermitteln und als fortlaufende Listendaten in einem

Speicher abzulegen, dazu eingerichtet sein, neben der Position eines Konturpunktes zumindest ein weiteres Attribut des Konturpunktes zu berechnen und in den fortlaufenden Listendaten abzuspeichern. Vorzugsweise wird mittels der integrierten Recheneinheit für einen

Konturpunkt einen Attribut-Vektor mit zumindest 24 Bit Länge, vorzugsweise zumindest 36 Bit Länge erzeugt und in den fortlaufenden Listendaten abgespeichert. Die Recheneinheit, die dazu eingerichtet ist, aus den im Speicher abgelegten Listendaten

Verbindungswahrscheinlichkeiten zwischen Konturpunkten zu ermitteln, kann dann Verbindungswahrscheinlichkeiten zwischen Konturpunkten anhand des Abstands zwischen den Konturpunkten und zumindest einem weiteren Attribut errechnen.

Um die Bilddaten schnell mit nur wenig benötigtem Speicher verarbeiten zu können, insbesondere um aus den Bilddaten Konturpunkte und Konnektoren zu ermitteln, ist weiterhin bevorzugt, daß die Bilddaten in mehreren Streifen ausgelesen werden, die jeweils eine Breite von mehr als 1 Pixel, vorzugsweise zumindest 16 Pixel, besonders bevorzugt 26 oder 32 Pixel aufweisen. Vorzugsweise werden dabei die Bilddaten nacheinander in Streifen ausgelesen, die um mehr als einen Pixel, vorzugsweise um zumindest 4 Pixel, besonders bevorzugt um zumindest 8 Pixel überlappen. Aufgrund dieses überlapps werden zwar unter Umständen Konnektoren im überlappbereich doppelt berechnet, dieser zusätzliche Mehraufwand wird aber dadurch überkompensiert, daß sich die einzelnen ermittelten Konturen leichter und fehlerfreier wieder zusammensetzen lassen.

Die Bildverarbeitungsvorrichtung ist weiterhin bevorzugt für eine Echtzeit-Bildverarbeitung eingerichtet. Dies bedeutet, daß innerhalb des Bildtransfers eine vollständige

Ermittlung von Objekten, welche die Konturen beschreiben, erfolgt. Diese Echtzeit-Verarbeitung wird insbesondere auch durch die sehr einfache Berechnung der Konnektoren für die Konturpunkte ermöglicht.

Um eine solche Echtzeit-Verarbeitung zu ermöglichen, ist es weiterhin besonders bevorzugt, daß die Vorrichtung Dual- Port-RAM-Speicher und eine Einrichtung zum gleichzeitigen Ablegen und Auslesen von Listendaten aus dem Dual-Port-RAM- Speicher aufweist. Dieser Speicher ermöglicht nicht nur sehr kurze Zugriffszeiten, insbesondere können die verschiedenen Prozesse zur Bildverarbeitung auch gleichzeitig auf die Daten im selben Speicher zugreifen. Während ein erster Prozess Listendaten in den Speicher schreibt, kann bereits ein anderer Prozess Listendaten gleichzeitig wieder aus dem Speicher entnehmen. Allerdings sind solche Speicher, beispielsweise auf einem FPGA im allgemeinen sehr klein. Typischerweise stehen Speicher im Bereich von 4 kByte zur Verfügung. Erst die Verarbeitung von Listendaten anstelle der Abbildung ganzer Bilder oder Bildbereiche im Speicher ermöglicht dabei auch die Beschränkung auf derartige kleine Speicher.

Als ein der Bildung von Listendaten mit den Konnektoren nachgeschalteter Prozess ist vorzugsweise ein

Morphologiefilter vorgesehen. Der Begriff Morphologiefilter wird in diesem Zusammenhang zur Kennzeichnung der glättenden Wirkung der Filteroperation verwendet, obwohl in diesem Grenzbereich auch topoiogische Eigenschaften ausgenutzt werden.

So weist gemäß dieser Ausführungsform der Erfindung die Bildverarbeitungsvorrichtung eine Morphologiefilter- Recheneinrichtung auf, welche dazu eingerichtet ist, die Konturpunktliste mit Konnektoren hinsichtlich zumindest

einer der Eigenschaften zu filtern:

-Konturpunkte zu Ketten von höchstens drei Konturpunkten werden gelöscht,

-Konturpunkte, welche nur zu einer einseitig mit einer längeren Kette verbundenen Kette mit höchstens drei Konturpunkten gehören, werden gelöscht, -Konturpunkte, welche Start- und Endpunkte von Ketten zusammengehörender Konturpunkte bilden, werden in der Konturpunktliste gekennzeichnet, -Konturpunkte, welche Verzweigungspunkte zumindest zweier Ketten bilden, werden in der Konturpunktliste gekennzeichnet .

Um die Verkettung der Konnektoren zu Objektsegmenten zu erleichtern, ist gemäß noch einer Weiterbildung der Erfindung außerdem eine Einrichtung zum Erzeugen von Rangvektoren für Konturpunkte vorgesehen, welche die Konturpunktliste mit Konnektorstruktur ausliest und jeweils ausgehend von einem Zentralpunkt über die Konnektoren die Konnektorstruktur sämtlicher Nachbarpunkte einliest und einen Rangvektor erzeugt, der die Anzahl der Verzweigungen der Nachbarpunkte und des Zentralpunkts selbst beinhaltet. Dabei wird die Konnektorstruktur in zeitlicher Verzögerung zum Eintragen von Konnektoren in die Konturpunktliste abgetastet. Die zeitliche Verzögerung ist vorgesehen, damit bereits Daten im betreffenden Dual-Port-RAM vorhanden sind, in welchen sowohl die Listendaten mit den Konnektoren eingetragen, als auch zur Bildung von Rangvektoren ausgelesen werden. Anschließend kann der Rangvektor über eine Tabelle oder Boolesche Funktionen auf eine vorzugsweise skalare Potentialfunktion abgebildet und Artefakte mittels der Potentialfunktion aussortiert werden. Um die spätere Segmentierung zu erleichtern, kann eine Einrichtung zum Auslesen der Konturpunktliste in geordneter Reihenfolge als geordnete Reihe von Konturpunkten

vorgesehen sein, wobei aufeinanderfolgende Listeneinträge zu aufeinanderfolgenden Konturpunkten entlang einer Kontur gehören. Diese Einrichtung kann zusammengehörende Konturpunkte insbesondere anhand der jeweiligen in der Konturpunktliste abgespeicherten Konnektoren ermitteln.

Eine solche geordnete Liste von Konturpunkten wird im Sinne der Erfindung auch als „Chain" bezeichnet. Die im Segmentierungsprozess erzeugten Chains stellen somit eine Folge geordneter Konturpunkte dar, die von einem Startpunkt ausgehend einen Endpunkt erreichen. Jedem der Konturpunkte können dabei wie gesagt durch einen vorgeschalteten Prozess Attribute, darunter die Abtastrichtung sowie der Kontrast entlang der Abtastrichtung zugewiesen werden.

Für die Bewertung der Relevanz eines Chains ist es dabei sinnvoll, den Kontrastbelag der Chain, beziehungsweise allgemeiner der Menge der zu einer Kontur gehörenden Konturpunkte zu berechnen. Als relevant werden Chains bewertet, wenn der Betrag des Kontrastbelages über einer gegebenen Schwelle liegt. Insbesondere kann die Weiterverarbeitung von Chains oder Mengen von zu einer Kontur gehörenden Konturpunkten in Abhängigkeit dieser Bewertung erfolgen. Ist eine Chain oder Menge als relevant bewertet, wird diese weiter verwendet, anderenfalls, unter anderem bei zu geringem Kontrastbelag wird die Chain oder Konturpunktmenge fallengelassen. Mit anderen Worten werden Chains mit zu geringem Kontrastbelag mittels einer entsprechenden Einrichtung der erfindungsgemäßen Vorrichtung aussortiert. Dieses Aussortieren muß nicht sofort erfolgen. Jedenfalls ist es besonders vorteilhaft, auch den Kontrastbelag als Attribut einer Chain, beziehungsweise einer Menge von zu einer gemeinsamen Kontur gehörenden Konturpunkten zu speichern.

Die Berechnung des Kontrastbelags kann besonders vorteilhaft erfolgen, indem für die Konturpunkt jeweils eine Abtastrichtung errechnet wird. Diese Abtastrichtung ist unabhängig vom Vorzeichen des Kontrastes diejenige Richtung entlang derer in der Bildumgebung lokal der maximale Kontrast auftritt. Die Abtastrichtungen müssen ferner nicht die exakten Richtungen des maximalen Kontrastwechsels in der Umgebung um den Konturpunkt sein. Vielmehr kann die jeweilige Abtastrichtung aus einer eng begrenzten Anzahl möglicher Richtungen ausgewählt werden, um den Rechenaufwand zu begrenzen. Beispielsweise können höchstens 16, bevorzugt 8 oder sogar besonders bevorzugt nur 4 mögliche Richtungen verwendet werden, die demgemäß mit entsprechend wenigen Bits darstellbar sind. Zur

Berechung des Kontrastbelags einer Kontur, beziehungsweise der zugeordneten Chain oder Menge von Konturpunkten können dann die Kontrastwerte der einzelnen Konturpunkte entsprechend ihrer Zählrichtung akkumuliert werden. Die Zählrichtung wird in Abhängigkeit der Abtastrichtung und dem Richtungsvektor der Kontur am Konturpunkt ermittelt und gibt an, ob der zum Konturpunkt gehörende, seinerseits vorzeichenbehaftete Kontrastwert beim Akkumulieren addiert oder subtrahiert wird.

Auch der Richtungsvektor kann ebenso wie die Abtastrichtung vorteilhaft auf wenige Richtungen, beziehungsweise wenige Möglichkeiten beschränkt werden. Ebenso wie bei der Abtastrichtung können höchstens 16, etwa 8 oder auch nur 4 verschiedene mögliche Richtungen für den Richtungsvektor zur Berechnung der Zählrichtung verwendet werden.

Das Aussortieren kontrastarmer Chains erfolgt in Weiterbildung der Erfindung mit einer im folgenden auch als „Chainfilter" bezeichneten Datenfiltereinrichtung. Diese

sortiert Mengen von zu einer gemeinsamen Kontur gehörenden Konturpunkten aus, wenn die Menge der Konturpunkte wenigstens eine der nachfolgenden Bedingungen erfüllt: a) die Länge der Kontur ist kleiner als ein vorgegebener Wert, vorzugsweise 10 Pixel, und sowohl der Start-, als auch der Endpunkt der Kontur weisen den Grad 1 auf, sind also nicht Bestandteil einer weiteren Kontur, b) die Länge der Kontur ist kleiner als ein vorgegebener Wert, vorzugsweise 10 Pixel, und entweder der Start-, als auch der Endpunkt der Kontur weisen einen Grad >2 auf, c) Start- und Endpunkt sind identisch und die Länge der Kontur ist kleiner als ein vorgegebener Wert, vorzugsweise 10 Pixel, d) der Betrag des Kontrastbelags ist kleiner als ein vorgegebener Wert.

Eine Filterung erfolgt demgemäß nicht nur anhand des akkumulierten Kontrasts, sondern auch anhand weiterer Kriterien, wie insbesondere der Strukturgröße.

Mittels dieses Chainfilters sollen Chains oder Chain- Segmente aussortiert werden, die zu Konturen gehören, welche durch Artefakte, etwa durch Rauschen entstanden sind und keine sinnvollen Strukturen beschreiben. Der Chainfilter ergänzt die durch den oben beschriebenen Morphologiefilter beschriebene Filterung.

Es hat sich gezeigt, daß eine artefaktarme Ermittlung von Verbindungen zwischen Konturpunkten bereits mit einer kleinen Umgebung eines ausgewählten zentralen Konturpunkts funktioniert. So kann eine zuverlässige Ermittlung von Verbindungen zwischen Konturpunkten erfolgen, wenn Verbindungswahrscheinlichkeiten für mögliche Verbindungen von Konturpunkten jeweils nur zu solchen weiteren Konturpunkten einschließlich des zentralen Konturpunkts errechnet werden, die maximal 2 bis 2,5 Pixel bezogen auf

das Raster des Digitalbildes von einem Konturpunkt entfernt sind.

Für die Berechnung der Konnektoren sind fast ausschließlich nur die jeweils nächst benachbarten Konturpunkte relevant. Daher können Rechenschritte gespart werden, wenn bereits die Bildung der Mengen von Konturpunkten, insbesondere von Tripeln für das Aussortieren geschickt vorgenommen wird. Dazu ist gemäß einer Weiterbildung der Erfindung eine der Recheneinheit zur Berechnung von

Verbindungswahrscheinlichkeiten für mögliche Verbindungen zwischen Konturpunkten vorgeschaltete Sortiereinrichtung vorgesehen, welche Listendaten von zu einem ausgewählten zentralen Konturpunkt benachbarten Konturpunkten jeweils entsprechend einer Reihenfolge ausgibt, die beim Abtasten einer Umgebung des zentralen Konturpunkts erhalten wird, indem sukzessive ausschließlich benachbarte Punkte der Umgebung ausgelesen werden. Dies ist beispielsweise ein Unterschied zu Bilddaten in üblichen Bildformaten. Hier sind die Daten zeilenweise geordnet. Innerhalb einer Zeile gehören zwar aufeinanderfolgende Daten der Bilddatei dann zwar zu aufeinanderfolgenden, also auch benachbarten Bildpunkten, dies gilt jedoch nicht mehr am Zeilenende. Hier erfolgt ein Sprung vom letzen Punkt der Zeile zum ersten, weit entfernten Punkt der nächsten Zeile.

Auf den ersten Blick erscheint die eingesetzte Ermittlung von Konturpunkten mit Subpixel-Genauigkeit , beziehungsweise das eingesetzte Subpixel-Raster redundante oder überflüssige Information zu enthalten und damit die nachfolgenden Berechnungen zu verlangsamen oder komplizierter zu machen. Allerdings werden nicht etwa zusätzliche Punkte berechnet, sondern es wird vielmehr vorzugsweise für jeden Konturpunkt im Raster der Bilddaten

höchstens einen Konturpunkt mit Subpixel-Genauigkeit ermittelt .

Wie bereits oben diskutiert, ermöglicht die Erfindung einen äußerst sparsamen Speichereinsatz. Gemäß einem weiteren Aspekt der Erfindung kann daher eine erfindungsgemäße Vorrichtung auch als integrierte

Bildverarbeitungsvorrichtung realisiert werden, welche einen oder mehrere Bildspeicher und zumindest eine integrierten Hardwareeinheit zur Ermittlung von Konturpunkten aus Bilddaten, einer der integrierten Hardwareeinheit zur Ermittlung von Konturpunkten nachgeschalteten Hardwareeinheit zur Ermittlung von zu einer Kontur gehörenden Verbindungen zwischen Konturpunkten, einen der Hardwareeinheit zur Ermittlung von Verbindungen nachgeschalteten Morphologieprozessor zur Bestimmung der Anzahl der von Konturpunkten ausgehenden Verbindungen von Konturen zu benachbarten Konturpunkten, sowie eine Einrichtung zur Segmentierung aufweist, mittels welcher aus den Daten über die Konturpunkte und deren Verbindungen zu weiteren Konturpunkten Objekte erstellt werden, welche die Konturen der Bilddaten beschreiben, wobei der Hardwareeinheit zur Ermittlung von zu einer Kontur gehörenden Verbindungen zwischen Konturpunkten ein Speicher oder Speicherbereich zugeordnet ist, dessen Größe höchstens 20 Prozent des gesamten Speichers für die Verarbeitung der Bilddaten zu die Konturen beschreibenden Objekten ausgenommen des oder der Bildspeicher beträgt.

Die Erfindung wird nachfolgend anhand von Ausführungsbeispielen und unter Bezugnahme auf die beigeschlossenen Zeichnungen näher erläutert. Dabei verweisen gleiche Bezugszeichen auf gleiche oder ähnliche Teile.

Es zeigen

Fig. 1 die Architektur eines integrierten Echtzeitbildverarbeitungssystems (IEBVS) ,

Fig. 2 eine grafische Darstellung der Konturpunktliste,

Fig. 3 schematisch ein Bereich einer Kontur mit Konturpunkten, Konnektoren und Punktrichtungen,

Fig. 4 ein Ordnungsprinzip für das Auslesen der Konturpunkte,

Fig. 5 ein Schaltbild einer Sortiereinrichtung,

Fig. 6 eine beispielhafte Verteilung von Konturpunkten in einer 5 x 5 - Umgebung eines Konturpunkts,

Fig. 7, 8, 9A bis 9C ein Berechnungsbeispiel, wobei Fig. 7 eine Anordnung von benachbarten Konturpunkten im Subpixel- Raster, Fig. 8 die Lage der Konturpunkte im Originalraster, und die Fig. 9A bis 9C Tabellen mit Koordinatenwerten und Abständen von Konturpunkten zeigen,

Fig. 10 eine Darstellung eines SNNC ("Statistical Nearest Neighbourhood Classifier") zur Ermittlung von Konnektoren,

Fig. 11 eine weitere Anordnung von benachbarten Konturpunkten im Subpixel-Raster,

Fig. 12 eine Darstellung eines größeren Bildausschnitts mit Konturpunkten und durch Aussortieren ermittelten Verbindungen,

Fig. 13 die Datenstruktur der vom SNNC für die Weiterverarbeitung gespeicherten Daten.

Fig. 14 ein Blockschaltbild einer Einrichtung eines morphologischen Filters zur Erzeugung von Rangvektoren,

Fig. 15 ein Beispiel einer Datenstruktur einer Konturpunktliste nach einer morphologischen Filterung,

Fig. 16 ein Beispiel einer Datenstruktur einer Konturpunktliste zur Speicherung der Daten singulärer Punkte mit einem Rang größer gleich 3,

Fig. 17 eine Einrichtung zum Auslesen einer

Konturpunktliste in geordneter Reihenfolge als geordnete Reihe von Konturpunkten,

Fig. 18 Konturpunkte einer Chain mit eingezeichneten Abtastrichtungen zur Ermittlung des Kontrastbelags einer Kontur,

Fig. 19 ein Beispiel einer Menge möglicher Abtastrichtungen,

Fig. 20 ein Ausführungsbeispiel für einen Kontrastakkumulator,

Fig. 21 die Phasenlage und den Speicherbedarf der Prozesse zur Bildverarbeitung,

Fig. 22 und 23 Ausschnitte einer Kontur mit Konturpunkten, sowie Parametern zur Bestimmung von Eckpunkten.

Fig. 1 zeigt die Struktur oder Architektur einer erfindungsgemäßen Vorrichtung 1 in Form eines integrierten EchtZeitbildverarbeitungssystems IEBVS. Dieses IEBVS umfasst ein Bildinterface, an das eine oder mehrere Bildquellen 3, z.B. CCD- Kameras, angeschlossen werden können und das die Bilddaten als Digitalbild in einem Bildspeicher 4 ablegt. Auf diesen Bildspeicher 4 greift ein Konturpunktprozessor 5 in Form einer integrierten Hardwareeinheit zu, die eingerichtet ist, die im Bildspeicher 4 abgelegten Daten eines Digitalbildes abzutasten und Konturpunkte mit Subpixel-Genauigkeit zu ermitteln und als fortlaufende Listendaten in einem Speicher abzulegen. Der Konturpunktprozessor 5 liefert die Koordinaten und ausgewählte Merkmale von Konturpunkten in Listenform. Merkmale sind z.B. Grauwerte oder Farben der angrenzenden Regionen, Kontraste oder Richtungen.

Die Koordinaten werden subpixelgenau innerhalb von "Regions of Interest", z.B. von waagerecht angeordneten Streifen ausgegeben. Um allgemeingültig. Bilder zu verarbeiten, ist vorzugsweise zunächst die Segmentierung, d.h. die Aufteilung des Bildes in Regionen mit homogenen Merkmalen vorteilhaft, anschließend die Interpretation dieser Merkmale .

Fig. 2 zeigt eine grafische Darstellung der Konturpunktliste. Neben klaren Konturen, im Beispiel die eines gestörten Datamatrixcodes, finden sich viele Punkte mit meist geringem Kontrast, die aufgrund verschiedener Oberflächenstörungen oder infolge Rauschen entstehen können. Aufgabe der nachfolgenden Verarbeitungseinheiten ist es nun, die Struktur der zwischen den einzelnen Regionen liegenden Konturen in geordneter Reihenfolge als verkettete Folge von Punkten durch Hardware in Echtzeit zu beschreiben, um diese in einem weiteren Schritt mit Hilfe

von Software oder weiterer Hardware durch digitale geometrische Objekte, insbesondere Strecken, Kreise, Polynome etc., zu approximieren und dann zu erkennen.

Die Aufgabe der Erfindung wird nun insbesondere dadurch gelöst, dass zunächst die Nachbarschaft von Konturpunkten in einem Statistical Nearest Neighbourhood Classifier 7 (SNNC) festgestellt wird. Dieser SNNC 7 umfasst eine Recheneinheit, welche aus den im Speicher abgelegten Listendaten mithilfe eines Rechenwerks die

Verbindungswahrscheinlichkeiten zwischen Konturpunkten unter Berücksichtigung des Abstands der Punkte zueinander ermittelt, und einen Klassifikator, welcher aus Mengen von berechneten Verbindungswahrscheinlichkeiten Teilmengen mit zumindest drei Verbindungswahrscheinlichkeiten für mögliche Verbindungen zwischen zumindest drei benachbarten Konturpunkten, wovon einer ein zuvor bestimmter zentraler Konturpunkt ist, auswählt und für jede Teilmenge denjenigen zum zentralen Konturpunkt benachbarten Konturpunkt aussortiert, der eine mögliche Verbindung mit der geringsten Verbindungswahrscheinlichkeit zu einem benachbarten Konturpunkt aufweist, sofern die Verbindung nicht zwei zum Zentralpunkt benachbarte Punkte verbindet, und im Anschluß daran in eine Konturpunktliste die nicht aussortierten Konturpunkte mit Konnektoren einträgt, welche die verbleibenden Verbindungen zum Zentralpunkt kennzeichnen Diese Daten werden dann in einen Speicher 9 eingetragen. Dieser Speicher 9 ist besonders bevorzugt ein Dual-Port-RAM.

Anschließend erfolgt mit einem morphologischen Filter 11, welcher den Speicher 9 ausliest, die Auswahl der relevanten Konturen und die Unterdrückung nicht relevanter Störungen. In einem dritten Schritt werden die Konturen in geordneter Reihenfolge als verkettete Objekte oder "Chains"

ausgelesen. Anhand dieser Ketten wird dann von einer weiteren Hardwareeinheit eine Segmentierung vorgenommen. Mittels eines MikroControllers 15 wird der Prozeßablauf in der Vorrichtung 1 gesteuert.

Um eine derart komplexe Struktur unter Echtzeitbedingungen in einen Schaltkreis zu integrieren, ist vorzugsweise eine strenge Pipelineverarbeitung vorgesehen. Im Gegensatz zu bekannten Softwarelösungen, die auf Hardwareplattformen mit ausreichender L2- Cache- Unterstützung arbeiten und zeitnah Zugriffe auf unterschiedliche Datenstrukturen ausführen können, ist es vorteilhaft, bei einer komplexen Integration Beschränkungen hinsichtlich der Speichergröße in Kauf zu nehmen, da andererseits auf diese Weise kleine schnelle SRAM- Bereiche, beispielsweise in Form von DualPortRAMs, wie dem in Fig. 1 gezeigten Speicher 1 verwendet werden können. Ferner bestehen dann erweiterte Anforderungen an die Verafbeitungsqualität der einzelnen Teilschritte, da das Pipelinekonzept Beschränkungen bei aufwendigen Such- und Ordnungs- oder Korrekturprozessen auferlegt. Eine typische Speichergröße von schnellen internen SRAM' s liegt vorzugsweise bei 4 bis 16 kByte.

Der erreichbare Integrationsgrad wird ferner insbesondere von der Verlustleistung bestimmt, die wiederum von der

Anzahl der zu realisierenden Verarbeitungsschritte abhängt. Eine besonders günstige Lösung mit einem minimalen Datenstrom im jeweiligen Prozeß ergibt sich dann, wenn ein kompaktes Listenformat für die Darstellung von Konturpunkten verwendet wird, da für die hierarchisch aufgebaute Signalverarbeitung jeweils nur streng determinierte Zugriffe auf Teilstrukturen erforderlich sind, so dass aufwendige Zugriffe auf Bildarrays mit Grauwert- oder Farbdaten vermieden werden können.

Aufgabe des Statistical Nearest Neighbourhood Processor 7 (SNNC) ist die Verbindung von Konturpunkten zu Konturen. Um die Nachbarschaft von Punkten P[j] bezüglich eines Zentralpunkts P[i] festzustellen, wird zunächst die Verbindungswahrscheinlichkeit P _C onn[i,j] der Punktmenge berechnet und dann klassifiziert.

Ein einfacher und bewährter Klassifikator ist der Abstand

Ein Punkt gehört zur Nachbarschaft NBD, wenn p _Con n[i» j] einen Schwellwert überschreitet. Weitere Nachbarschaftsmaße können gebildet werden, indem Pconnfi/j] mit aus den Abtastrichtungen DIR und/oder Kontrasten cont gebildeten

Maßen ergänzt werden. Dadurch können z.B. zutreffend weiter entfernt liegende Punkte mit der gleichen Richtung verbunden werden, senkrecht stehende Rauschpunkte jedoch nicht.

Da durch einen vorgeschalteten Konturpunktprozessor weitere Informationen, darunter der lokale Kontrast cont, als auch eine Richtungsinformation DIR bereitstehen, kann die Entscheidung deutlich verbessert werden, indem der Schwellwert für die Verbindungsentscheidung P als Funktion dieser Parameter ausgeprägt und als Tabelle und/oder ALU gemäß der nachstehenden Funktion ausgeführt wird:

r _/ n- _f ( ^Aχ y ^p iR - ^A y ^χ Dm

^ 1 A Axx ²² ++ AAyy ²²

In der oben angegebenen Beziehung bezeichnen δx, δy die Komponenten der Vektordarstellung einer Verbindung und X _DIR ,

YDI _R - die Komponenten der mittleren Punktrichtung. Das Argument der Funktion f wird dann maximal, wenn der Winkel α 90° beträgt.

Fig. 3 zeigt zur Verdeutlichung einen Bereich einer Kontur 16, auf der Konturpunkte 26 liegen. Die Verbindungen 24 zwischen nächst benachbarten Konturpunkten 26 sind als gestrichelte Linien eingezeichnet. Die mittleren Punktrichtungen 22 der Konturpunkte 26 sind als Pfeile dargestellt. Die mittleren Punktrichtungen können beispielsweise durch die an den Pfeilen angegebenen Ziffern charakterisiert werden. Bei dem in Fig. 3 gezeigten Beispiel weisen die Konturpunkte 26 drei der hier verwendeten acht möglichen Punktrichtungen, entsprechend den Ziffern 0 bis 7 auf. Wie anhand von Fig. 3 ersichtlich ist, ist der Winkel α jeweils der zwischen der mittleren Punktrichtung 22 und der Verbindung 24 zwischen zwei Konturpunkten 26 eingeschlossene Winkel.

Wenn die so berechnete Wahrscheinlichkeit P _C onn[i/j] größer als ein Schwellwert "Threshold" ist, wird eine Verbindung hergestellt .

In einer fortlaufenden Kontur hat jeder Zentralpunkt in der Regel nur einen Vorgänger und einen Nachfolger mit einem

Abstandsmaß, das sich aus dem Pitch des verwendeten Rasters ergibt. Diese relativ enge Definition führt in Praxis jedoch dazu, dass Konturen aufreißen und als getrennte Objekte gespeichert werden und somit einen nicht unerheblichen Aufwand bei der nachfolgenden Verarbeitung erzeugen. Deshalb besteht die Aufgabe des SNNC u.a. auch darin, Konturpunkte zu verbinden, die ein Abstandsmaß ausweisen, das größer als der Bildpunktabstand des Abtastrasters ist.

Das optimale Maß ist abhängig von den konkreten Bedingungen, es hat sich jedoch erwiesen, dass ein Wert von 2 bis 2.5 des Pixelabstands eine erhebliche Verbesserung der Konturqualität ergibt. Der Preis hierfür ist allerdings ein Ansteigen der Anzahl der möglichen Kandidaten für eine Nachbarschaft, die in Echtzeit verarbeitet werden.

Der SNNC 7 hat nun die Aufgabe, innerhalb der Nachbarschaft NBD die topologisch relevanten Nachbarn zu ermitteln.

Erfindungsgemäß wird diese Aufgabe nun dadurch gelöst, dass aus der Menge NBD Tripel bestehend aus dem Zentralpunkt Pi und einer beliebigen Kombination von zwei weiteren Punkten Pji und Pj ₂ aus NBD gebildet werden und dass die VerbindungsWahrscheinlichkeiten,

Ptripiet = i Paonni i' J ¹ ] ' P _∞ nnlJ ¹ ' J ² ] ' Pconnli J ² I)

berechnet werden. Das oben angegebene Tripel oder Triplett stellt also einen Vektor mit den

Verbindungswahrscheinlichkeiten zwischen allen Verbindungen zwischen einem ausgewählten zentralen Konturpunkt und jeweils zwei benachbarten Punkten dar, wobei als benachbarte Punkte alle Punkte innerhalb eines höchstens 2 bis 2.5-fachen Pixelabstands in Betracht kommen.

Wenn festgestellt wird, dass die

Verbindungswahrscheinlichkeit oberhalb einer vorgegebenen Schwelle "Threshold" liegt, dann wird das Tripel analysiert und die Verbindung mit der kleinsten Wahrscheinlichkeit gestrichen. Die Hardwarerealisierung sieht außerdem eine effiziente Sortiermaschine vor, die zunächst Dreiecke ermittelt. Wegen der Testbedingung sind jedoch nur die Dreiecke mit den jeweils kürzesten Abständen

auf dem äußeren Polygon, beziehungsweise die nächsten Nachbarn der Konturpunkte relevant. Deshalb können durch Anwendung von Ordnungsprinzipien Operationen gespart werden.

Fig. 4 zeigt ein Schema, wie mittels einer geeigneten Sortiereinrichtung Listendaten von zu einem ausgewählten zentralen Konturpunkt benachbarten Konturpunkten ausgelesen werden. Der momentan ausgewählte zentrale Konturpunkt ist mit "CP" bezeichnet. Die Konturpunkte sind mit

Subpixelgenauigkeit abgelegt, es existiert pro Bildpunkt maximal ein Eintrag. Deshalb können die oben beschriebenen Dreiecke durch kontinuierliche Abtastung der Nachbarpunkte, beispielsweise im Uhrzeigersinn erzeugt werden. Die Zahlen 1 bis 24 geben die Reihenfolge des Auslesens von

Konturpunkten innerhalb einer 5x5 Umgebung mit Listendaten wider. Die Konturpunkte, beziehungsweise deren Listendaten werden also in der Reihenfolge aus dem Bildbereich einer Umgebung mit maximal 2 Pixeln Abstand zum Zentralpunkt ausgelesen, wie sie durch die Zahlen, die in den Pixeln angegeben sind und Listendaten von Konturpunkten werden entsprechend dieser Reihenfolge ausgegeben. Demensprechend wird zunächst der mit "1" bezeichnete Pixel ausgelesen, dann der mit "2" bezeichnete Pixel, und so weiter, bis zum letzten Pixel "24" dieser Umgebung. Es werden also sukzessive ausschließlich benachbarte Punkte der Umgebung des Zentralpunkts ausgelesen.

Eine Ausgestaltung einer solchen Sortiereinrichtung 17 ist in Fig. 5 dargestellt. Zur Adressierung wird z.B. ein

Schieberegister für die Indizes (Adressen) der Konturpunkte in einem DualportRAM verwendet. Immer dann, wenn für ein Pixel eine positive Entscheidung als Konturpunkt vergeben wird, erhält dieser Konturpunkt die nächstfolgende Adresse im DualportRAM, die wiederum als Index (Teil der Adresse )

in ein Schieberegister eingeschoben wird. Falls der nächstfolgende Bildpunkt kein Konturpunkt ist, wird eine Null im Schieberegister eingetragen. Dieses Schieberegister mit einer Länge von n x m z.B. 5x24 kann damit 120 Indizes speichern. Dadurch, dass Konturpunkte selten sind, genügen wenige Bit, z.B. 6-8 bit Wortbreite.

Ein Beispiel für eine Verteilung von Konturpunkten in der 5 x 5-Umgebung eines zentralen Konturpunkts zeigt Fig. 6. Die Einträge mit der Bezeichnung "Index" zeigen an, daß der betreffende Pixel ein Konturpunkt ist. Eine lokale 5x5 Umgebung wird in bekannter Weise durch Abgriffe an den entsprechenden Registern hergestellt. Diese Register werden nun über Eingänge 20 eines geeignet angeschlossenen Multiplexers 19 so ausgelesen, dass die in Fig. 4 dargestellte Reihenfolge am Ausgang des Registers 23 entsteht. Dieser Prozeß wird genau dann gestartet, wenn der Zentralpunkt CP ungleich null ist, d.h. wenn eine zu analysierende Nachbarschaft im Registersatz dargestellt wird und der Punkt CP ein Konturpunkt ist.

Immer dann, wenn der Ausgangswert des Multiplexers 19 ungleich null ist, wird der Index in ein Ausgangsregister 23 geschoben, das direkt Daten aus dem DualportRAM adressiert. Ob der Ausgangswert des Multiplexers 19 ungleich null ist, wird mittels eines auf das Ausgangsregister 23 wirkenden Komparators 21 ermittelt.

Zur Entkopplung der Sortierprozesse vom kontinuierlich laufenden Konturdetektionsprozeß können weitere FIFO-Puffer oder Register, typisch für 8 bis 12 Konturpunkte in den Ausgangsdatenstrom eingefügt werden, die dann die zu einer Nachbarschaft gehörenden Konturpunkte auch mehrfach repetitierend auslesen können, so dass sämtliche für den Sortierprozeß benötigten Konturpunktkombinationen

bereitgestellt werden können. Es ist weiterhin grundsätzlich möglich, diesen Sortierprozeß durch Parallelisierung zu beschleunigen, beispielsweise indem zwei oder mehr Multiplexer parallel geschaltet werden.

Die im Beispiel der Fig. 6 dargestellte Belegung mit Indizes entspricht den Umgebungen des nachfolgend anhand der Fig. 7, 8, 9A bis 9C beschriebenen Berechnungsbeispiels zur Berechnung von Konnektoren zwischen zu einer gemeinsamen Kontur gehörenden Konturpunkten.

In Fig. 7 ist zunächst die Lage eines zentralen Konturpunkt 25 und benachbarter Konturpunkte 26 mit möglichen Verbindungen 27 einer Kontur im Subpixel-Raster dargestellt. An den Achsen des Diagramms sind dabei die Indizes der Bildpunkte aufgetragen. Fig. 8 zeigt die gleichen Punkte im Originalraster der Bilddaten. Anhand der Fig. 8 wird deutlich, .daß sich die relevanten, gemeinsam mit dem Zentralpunkt zu einer Kontur gehörenden benachbarten Konturpunkte im Originalraster deutlich schlechter erkennen und Graphen bilden lassen.

Im Beispiel wurden die Konnektoren mit einer Subpixelgenauigkeit von 1/4 Pixel berechnet. Dieses Beispiel wird aus Gründen der Einfachheit mit Abständen als Maß für die reziproke Verbindungswahrscheinlichkeit veranschaulicht. In der linken Tabelle (Fig. 9A) sind die Subpixelkoordinaten (Spalten X, Y) der im oberen Teil gezeigten Konturpunktanordnung dargestellt. Die Tabelle beginnt mit dem Zentralpunkt CP. In der mit "Field" bezeichneten Spalte sind die Subpixel-Koordinaten der Konturpunkte eingetragen, wie ■ sie sich aus der Abtastung gemäß Fig. 4 für die in Fig. 6 gezeigte Umgebung ergeben. Im DualPort RAM wird im Beispiel also folgende Konturpunktreihenfolge adressiert: CP, 7, 9, 13, 18, 19,

22, 24, 7. Zusätzlich eingezeichnet sind die Hauptrichtung 29 aller Konturpunkte der Umgebung des Zentralpuhkts, sowie die Punktrichtungen 30.

Aus den Subpixelkoordinaten werden die relativen Abstände [Xrel,Yrel] zum Zentralpunkt berechnet, wie sie in der Tabellen der Fig. 9B aufgelistet sind. Daraus wird wiederum der Abstand p zum Zentralpunkt. Die Pixel mit den Indizes 7, 9, 13, 18, 19, 22, 24, 7 bilden ein Polygon, in dessen Mitte der Zentralpunkt CP steht. Die Seiten des Polygons [X_Poly, Y_Poly] bilden mit den Verbindungen zum Zentralpunkt Dreiecke, so z.B. das Dreieck <CP,, "Field" 7, "Field" 9>. In diesem Dreieck ist die längste Seite 8,602 Subpixel lang und damit länger als die beiden anderen Seiten mit Längen 5,385 und 3,606, so daß diese längste

Seite die niedrigste Verbindungswahrscheinlichkeit zwischen den drei Konturpunkten repräsentiert. Damit wird die längste Seite aus der Liste der zu verbindenden Konturpunkte gestrichen. Diese Operation wird für sämtliche Dreiecke ausgeführt. Dabei werden zwei weitere, also insgesamt drei Punkte gestrichen. Von diesem Aussortierprozeß sind speziell die Konturpunkte mit den Indizes 9, 18 und 24 betroffen. Es verbleiben vier nicht aussortierte Konnektoren, wobei ein Konnektor Anfang und Ende des Polygons verbindet. Die verbleibenden Konturpunkte sind in der Tabelle der Fig. 9C aufgelistet. Der Aussortier-Vorgang wird für die verbleibenden Konnektoren oder Konturpunkte nun wiederholt. Beim wiederholten Aussortieren entfällt außerdem noch der Konturpunkt mit dem Index 12, beziehungsweise der erste in der Tabelle der Fig. 9C aufgelistete Konturpunkt.

Dieser Konnektor ist am Ende der Analyse zu untersuchen, hierbei entfällt ein weiterer Konnektor. Es verbleiben dann

die drei Konnektoren 28 in Fig. 7, die in den Listendaten gespeichert werden. Demgemäß ergibt sich als Ergebnis der Berechnung in diesem Beispiel, daß die Konnektoren vom Zentralpunkt als Konturpunkt zu den drei weiteren übriggebliebenen Punkten die eine oder mehreren Konturen repräsentieren, zu denen der Zentralpunkt gehört. Der SNNC 7 verfügt demgemäß nach Durchlaufen dieses oben anhand der Fig. 7, 9A bis 9C beschriebenen Filters, beziehungsweise Aussortier-Vorgangs über die Information, welche Konturpunkte aus der Konturpunktliste mit dem Zentralpunkt verbunden sind.

Bei dem in den Fig. 7, 9A bis 9C gezeigten Beispiel wurde das Verfahren des Aussortierens anhand eines sehr einfachen Klassifikators für die Verbindungswahrscheinlichkeit, nämlich ein Klassifikator, der lediglich vom Abstand der Konturpunkte zueinander abhängt, beschrieben. Die Erkennung der relevanten Verbindungen zwischen Konturpunkten kann aber noch wesentlich verbessert werden, wenn für die Berechnung der Klassifikatoren zusätzliche Attribute der

Konturpunkte eingesetzt werden. Insbesondere ist hier daran gedacht, die Richtung und/oder den Kontrast der Konturpunkte zu verwenden. Die Richtung kann beispielsweise ein Richtungsvektor sein, welcher senkrecht zur Kante in den Bilddaten, dessen Kontur zu bestimmen ist, liegt.

Vereinfacht kann dabei auch eine Richtungsinformation mit einer reduzierten Anzahl möglicher Richtungen, beispielsweise 8 mögliche Richtungen als Attribut vom Konturpunktprozessor 5 ermittelt und abgespeichert werden. Die Richtung eines Konnektors ergibt sich dann aus dem Verbindungsvektor zwischen dem

Zentralpunkt i und einem der äußeren Punkte j der Nachbarschaft. Anhand dieser beiden Richtungsangaben kann dann der Winkel α zwischen der abgespeicherten mittleren

Punktrichtung und dem Konnektor ermittelt werden. Als Klassifikator für die Verbindungswahrscheinlichkeit kann dann beispielsweise eine Funktion des Winkels α ,z.B. dessen sinus oder cosinus, und des Abstands der Punkte angesetzt werden.

Die Verbindungswahrscheinlichkeit kann ferner mit einem

Kontrastmaß verknüpft werden, um kontrastreiche

Konturen gegenüber kontrastarmen zu bevorzugen, indem z.B. eine Multiplikation mit dem Betrag des mittleren Punktkontrasts des Verbindungselements zur Klassifikation der Verbindungswahrscheinlichkeit verwendet wird. Dies ist besonders bei insgesamt kontrastarmen Szenen oder dünnen Linien von Vorteil.

Fig. 10 zeigt ein Schaltbild eines SNNC 7 zur Ermittlung von Konnektoren. Anhand dieser Figur kann die Funktionsweise des SNNC 7 näher erläutert werden. Durch die Sortiereinrichtung können die Konturpunkte in der benötigten Reihenfolge adressiert werden. Am Dateneingang 71 des SNNC liegt die Information über die Koordinaten, einen Kontrast sowie die Punktrichtung [x, y, cont , DIR] vor, die Daten werden in Register 72, 73, 74 mit 32 bit Wortbreite eingelesen.

Eine weiter unten noch genauer beschriebene Recheneinheit 75, die im folgenden als "CaIc Pconn" bezeichnet wird, berechnet nun die Verbindungswahrscheinlichkeit zwischen den drei Konturpunkten eines Dreiecks. Hierzu wird ein Zentralpunkt durch Adressdecodierung ausgewählt. Bei dem in Fig. 10 gezeigten Beispiel sind die Daten des Zentralpunkts in das Register 74 geladen. Neu einlaufende Konturpunkte werden in die beiden Register 72 und 73 eingelesen. Die drei möglichen Kombinationen der

Verbindungswahrscheinlichkeiten werden mittels der Komparatoren 761, 762, 763 und des nachgeschalteten Decoders 77 analysiert. Wenn die geringste

Verbindungswahrscheinlichkeit zwischen dem Zentralpunkt und einem der beiden Punkte auf dem Polygon liegt, beziehungsweise keine Verbindung zum Zentralpunkt ist, so wird die betreffende Verbindung gelöscht, indem je nachdem, von welchem der beiden zum Zentralpunkt benachbarten Konturpunkten entweder das Bit EN_CLK_RG1 oder das Bit EN_CLK_RG2 an den Ausgängen 78, beziehungsweise 79 gesetzt wird. Die Indizes der betrachteten drei Punkte werden parallel zu den Daten gespeichert. Der Index des nicht gelöschten Punktes wird in ein Schieberegister übertragen, hierzu wird die Indexdifferenz zum Zentralpunkt berechnet und mit dem nächstfolgenden Takt gespeichert.

Die Recheneinheiten CaIc Pconn 751, 752, 753 erhalten die Folge der mit dem Registerausgang 23 Fig. 5 adressierten Konturpunkte mit ihren Attributen und berechnen die Verbindungswahrscheinlichkeiten und vergleichen diese untereinander in Verbindung mit den Komparatoren 761, 762, 763 und entscheiden im Decoder 77 für jedes analysierte Tripel die zu streichenden Verbindungen. Am Ausgang werden die Signale EN CLK RGl und EN CLK RG2 für die Konturpunkte Pl und P2 geliefert, die das Streichen von Verbindungen steuern. Anschließend werden weitere Tripel analysiert. Nach einer ausreichenden Zahl von verarbeiteten Tripeln verbleiben nicht markierte Verbindungen, die als Ergebnis Konnektoren, welche die Indizes benachbarter Konturpunkte und die Verbindungswahrscheinlichkeit des Konturpunkts i mit dem Zentralpunkt CP sowie mit dem nächstfolgenden Nachbarn i+1 enthalten.

Bei der Berechnung der Verbindungswahrscheinlichkeiten kann es allerdings zu Mehrdeutigkeiten kommen, die durch

gleichschenklige bzw. gleichseitige Dreiecke zum Ausdruck kommen. Um Morphologiestörungen ohne komplizierte Logik zu vermeiden (z.B. kleine Dreiecke in den Konturen) kann vorteilhaft eine Recheneinrichtung zum Aufprägen einer Modulation auf die Komparatoren des Klassifikators, beispielsweise einer Modulation in Form eines pseudostochastischen geometrischen Rauschens addiert werden, das den Eindruck eines nicht ganz regulären Rasters erzeugt. Hierzu addiert man über eine Tabelle einen marginalen Rauschanteil, z.B. mit 10% des Pixelabstands zur Koordinatendifferenz für die relativen Abstände δx und/oder δy zum Zentralpunkt.

Fig. 11 zeigt eine weitere Anordnung von benachbarten Konturpunkten im Subpixel-Raster, welche von Bilddaten einer anderen Stelle des Digitalbilds gewonnen wurden. Bei diesem Beispiel wurden im Unterschied zu der in Fig. 7 gezeigten Umgebung nur zwei relevante Konnektoren 28 durch Aussortieren aus den möglichen Verbindungen 27 ermittelt.

Fig. 12 zeigt eine Darstellung mit Konturpunkten und durch Aussortieren ermittelten Verbindungen, die einen größeren Bildausschnitt repräsentiert. Zur übersichtlichkeit sind nur die Verbindungen 28 dargestellt. Wie anhand dieser Figur ersichtlich wird, ergeben die aneinandergereihten

Konnektoren 28 den Verlauf von Konturen im Digitalbild. In Fig. 12 sind zwei Ausschnitte 31, 32 mit Kreisen markiert. Der Ausschnitt 31 kennzeichnet die drei aus der in Fig. 7 gezeigten Umgebung ermittelten Konnektoren 28 mit einer vom Zentralpunkt ausgehenden Verzweigung. Der Ausschnitt 32 kennzeichnet die Konnektoren 28 der in Fig. 11 gezeigten Umgebung. Der gestrichelte Kreis zeigt den Bereich mit der Umgebung aller in Fig. 7 eingezeichneten Konturpunkte an. Anhand von Fig. 12 wird dabei deutlich, daß der in Fig.

11 gezeigte Fall einer durchlaufenden Kontur häufiger ist, als das Auftreten einer Verzweigung.

Anhand von Fig. 12 wird außerdem deutlich, daß dieses einfache Verfahren des Aussortierens zu einer Erkennung von Konturlinien mit nur wenigen Artefakten führt. Ansonsten würde man beispielsweise zusätzlich noch kurze Linien erwarten, die isoliert sind oder von den Konturlinien ausgehen. Im in Fig. 12 gezeigten Bild ist lediglich eine solche kurze Linie 33 zu erkennen.

Fig. 13 zeigt die Daten-Struktur der vom SNNC 7 für die Weiterverarbeitung vorzugsweise in einem weiteren DualPort- RAM gespeicherten Daten mit Konnektoren, beziehungsweise Informationen über die Verbindungen des jeweiligen Punks zu weiteren Konturpunkten. Die Information über die Verbindungen mit Nachbarpunkten wird im folgenden auch als "Linkinfo" bezeichnet.

Der Index des Zentralpunkts i bildet die Adresse unter der die Linkinfo in einem DualPort RAM gespeichert wird (siehe weiter unten) . Jeder erlaubte Konturpunkt (EN=I) liefert einen weiteren Index j (Pointer), die Differenz

LINK[n] = J _n - i

wird als LINK bezeichnet. Unter Kenntnis der LINKs können von einem Zentralpunkt aus sämtliche Nachbarn in der Konturpunktliste adressiert werden. Aufgrund der Struktur des SNNC können maximal 4 LINKs pro Zentralpunkt entstehen, fünf und mehr Nachbarn werden in mehrere Nachbarschaften aufgelöst. Die Maske MASK gibt an, ob der betreffende LINK gesetzt ist oder nicht. Parallel dazu wurden im gleichen Speicher die Attribute durch den Konturpunktprozessor

gespeichert, so dass die Koordinaten sowie Grauwert und bei Bedarf Farbinformationen bereit stehen.

Nachfolgend wird der in Fig. 1 schematisch dargestellte morphologische Filter 11 genauer beschrieben.

Die so eindeutig verbundenen Konturpunkte können noch nicht als Objekte ausgelesen werden, weil zwei Voraussetzungen fehlen. Erstens sind Anfangs- und Endpunkte der Konturen noch nicht definiert, zweitens existieren noch eine Vielzahl von Artefakten, die Ressourcen für die Objektsegmentierung unnötig belasten würden. Deshalb wird die Morphologie von benachbarten Punkten mittels des morphologischen Filters 11 untersucht, bevor die Punkte anhand der Konnektoren zu Objekten vereinigt werden. Der morphologische Filter 11 ist nun dazu eingerichtet, die Konturpunktliste mit Konnektoren hinsichtlich zumindest einer der Eigenschaften zu filtern: -Konturpunkte zu Ketten von höchstens drei Konturpunkten werden gelöscht,

-Konturpunkte, welche nur zu einer einseitig mit einer längeren Kette verbundenen Kette mit höchstens drei Konturpunkten gehören, werden gelöscht, -Konturpunkte, welche Start- und Endpunkte von Ketten zusammengehörender Konturpunkte bilden, werden in der Konturpunktliste gekennzeichnet,

-Konturpunkte, welche Verzweigungspunkte zumindest zweier Ketten bilden, werden in der Konturpunktliste gekennzeichnet , -Koinzidenzen werden korrigiert, und

-es wird eine doppelte Verlinkung durchgeführt.

Zur Ausführung dieser Funktionen wird zunächst eine im Filter 11 implementierte, nachfolgend als "RankFilter" bezeichnete Funktion eingesetzt. Mittels dieser Funktion

werden Rangvektoren für Konturpunkte gebildet. Dazu wird die Konturpunktliste der in Fig. 13 gezeigten Datenstruktur mit Konnektorstruktur ausgelesen und jeweils ausgehend von einem Zentralpunkt über die Konnektoren die Konnektorstruktur sämtlicher Nachbarpunkte eingelesen und einen Rangvektor erzeugt, der die Anzahl der Verzweigungen der Nachbarpunkte und des Zentralpunkts selbst beinhaltet. Der RankFilter bestimmt also die Anzahl der von einem Konturpunkt ausgehenden Verbindungen, hier durch Bildung der Summe der gesetzten Bits der Maske MASK. Eine vierfache Verzweigung hätte damit den Rang 4, MASK=IlIlB, ein Kettenelement, wie etwa der in Fig. 11 gezeigte Zentralpunkt Rang 2 und in der Regel MASK=OOIlB.

Das RankFilter adressiert die benachbarten über MASK zugelassenen LINKs und bestimmt damit für jeden Konturpunkt der Nachbarschaft den Rang. Aus den so ermittelten Rängen wird ein Rangvektor gebildet, der die Strukturinformation über die Anzahl der Verzweigungen der Nachbarpunkte enthält.

Da die Verkettung der Punkte aus allen Richtungen aufgerufen werden kann, ist eine doppelte Verlinkung mit einer Markierung für bereits gelesene Punkte sinnvoll. Deshalb wird eine Linkadresse LinkAdr generiert, die angibt, auf welcher der vier möglichen Positionen des adressierten Nachbarpunkts der inverse Link auf den Ausgangspunkt gespeichert ist. Die LinkAdr wird nach Ausführung der morphologischen Filterung gespeichert.

Da die sequentielle Abfolge eines Links auf einen Nachbarpunkt und des inversen Links auf den Zentralpunkt zurück immer die Pointerdifferenz Null ergibt, kann relativ einfach über Komparatoren diese Adresse gefunden werden. Im Ergebnis erhält man eine Struktur, die es mit nur einem

Zugriff gestattet, den Index des benachbarten, verbundenen Konturpunkts zu finden und verkettete Konturpunkte mit hoher Geschwindigkeit auszulesen.

Eine besonders vorteilhafte Realisierung eines Rangfilters 35, vorzugsweise als Bestandteil des morphologischen Filters 11 ist in Fig. 14 dargestellt. Vom Rangfilter 35 wird aus der Datenstruktur 37 aus dem DualportRAM 9 , wie sie auch in Fig. 13 gezeigt ist, zunächst die Linkinfo des Zentralpunkts mit der Adresse Ptr[0] im DualportRAM in das Eingangsregister des Rangfilters gelesen. Anschließend werden die LINKs 1-4 über einen Multiplexer 39 adressiert, die Adressen Ptr[1..4] durch Addition berechnet und der Reihe nach aufgerufen. Nicht benötigte LINKs, gekennzeichnet durch eine Null auf dem zugeordneten Bit der Maske MASK können übersprungen werden. Zu den relativ abgespeicherten LINKs wird die Pointeradresse des Zentralpunkts mittels des Addierers 45 addiert, anschließend kann direkt die Liste adressiert werden. Auf diese Weise werden die Linkinfos eingelesen. Die angeschlossenen Komparatoren 40, 41, 42, 43 des morphologischen Filters 11, beziehungsweise des implementierten Rangfilters 35 vergleichen die LINKs des mit Ptr[i] adressierten Konturpunkts mit dem LINK[i] des Zentralpunkts. Vier (3) Komparatoren vergleichen die betreffenden LINK' s. Wenn eines der Paare komplementär zueinander ist, generiert der betreffende Komparator 40, 41, 42, 43 ein Signal CMP_LINK [1..4] , so dass hieraus mittels des Decoders 44 die LinkAdr decodiert werden kann.

Im gleichen Prozeß kann auch der Rang RANK[I..4] ermittelt und zu einem Rangvektor <RANK[1], RANK[2], RANK[3], RANK[4]> zusammengestellt werden, indem die Maskenbits mittels des Addierers 46 addiert werden. Der Rangvektor wird innerhalb des morphologischen Filter zu einer binären

Entscheidung über die weitere Zulassung einer bisher als gültig erklärten Verbindung verarbeitet und im der Struktur MASK gespeichert.

Außerdem werden mit dem morphologischen Filter Störungen in den wie oben beschrieben verbundenen Konturen beseitigt, die insbesondere bei hoher Auflösung und/oder Empfindlichkeit zu einer Reihe von kleinen Artefakten führen, die aufgrund ihrer Anordnung zu Objekten segmentiert würden. Dies ist für die Effizienz der nachfolgenden Verarbeitungsschritte nachteilig. Mit dem morphologischen Filter werden daher bereits vor der Objektsegmentierung kleinere Störungen beseitigt.

Nachfolgend soll die Arbeitsweise einer Funktion des morphologischen Filters 11 beschrieben werden. Diese Funktion wird im folgenden als "MorphFilter" bezeichnet. Nachdem Rang und LinkAdr berechnet wurden, kann ein einfaches Filter realisiert werden. Hierzu werden zunächst störende kleine Strukturen, "Appendices" mit 1 bis 2 Konturpunkten gelöscht. Ein solcher Appendix ist beispielsweise die kurze Linie 33 in Fig. 12. Man erkennt derartige Strukturen an der Anzahl der Verzweigungen ihrer Nachbarn (in Klammern), z.B. an folgendem Rangvektor: <l,3,0,0>. Der Konturpunkt mit diesem Rangvektor ist mit der Hauptkontur über einen singulären Punkt vom Rang 3 verbunden. Der Punkt soll gelöscht, die Singularität der Hauptkontur, beziehungsweise die Verzweigungsstelle auf den Rang 2 zurückgestellt werden. Die Operation kann mit folgendem Maple-Programmcode veranschaulicht werden:

if RankVector=[l, 3, 0, 0] then

MASK [Ptr [1] , LinkAdr [Ptr[0] ,1] ] :=0: MASK[Ptr[0] ,1] :=0:

MASK [ Ptr [0] ,2] :=0: end:

Der Zentralpunkt hat den Rang 1 und steht im RankVector an erster Stelle. LINK[I] des Zentralpunkts verweist auf einen Konturpunkt mit dem Rang 3. Die LinkAdr [Ptr [0] , 1] gibt in diesem Fall an, wo auf dem Konturpunkt mit dem Rang 3 der inverse LINK auf den Zentralpunkts zu finden ist. Ptr[l] adressiert den Konturpunkt mit dem Rang 3, also löscht die Operation

MASK [Ptr [1] , LinkAdr [Ptr [0] , 1] ] :=0:

den LINK auf den einzelnen Konturpunkt, der Rang wird von 3 auf 2 reduziert. Deshalb verhält sich der singulärer Punkt anschließend wie ein normaler Bestandteil einer verketten Liste, d.h. es tritt keine Verzweigung auf. Für die nachfolgende Verarbeitung werden zwei Objekte weniger generiert, die Vereinigung von zwei gültigen längeren Objekten zu einem Objekt entfällt.

Ein weiteres Beispiel ist ein Konturpunkt mit einem

Rangvektor <2,3,l,0>. Dieser ist ein Appendix mit zwei Konturpunkten. Die beiden Konturpunkte sind mit der Hauptkontur über eine Verbindung vom Rang 2 und einen singulären Punkt, beziehungsweise einer Verzweigung des Rangs 3 verbunden. Ein solcher Appendix kann mit einem

Filter gelöscht werden, der eine zum nachstehenden Maple- Code analoge Funktion ausführt.

if RankVector=[2, 3, 1,0] then if LinkAdr [Ptr [2] , I]=I then L:=2 eise L:=l: end:

MASK [Ptr [1] , LinkAdr [Ptr [0] ,L] ] : =0 : MASK [Ptr [0] ,1] : =0 :

MASK [ Ptr [0] ,2] : =0 :MASK [Ptr [2] ,1] :=0: end:

Der Randpunkt mit dem Rang 1 steht auf LINK [2], LinkAdr [Ptr [2] , 1] zeigt auf den inversen LINK auf Ptr[O] ( dies ist vom Rand gesehen der nächste Punkt). Da Ptr[0] den Rang 2 hat, muß der andere LINK (L) auf den singulären Punkt Ptr[l] der Hauptkontur mit dem Rang 3 zeigen. Folglich löscht die Funktion

MASK [Ptr [1] , LinkAdr [Ptr [0] ,L] ] : =0 : den LINK von Ptr[l] auf Ptr[0] und reduziert den Rang von 3 auf 2, die Verbindung ist gelöscht.

Analog kann auch die Vertauschung <2,l,3,0> gefiltert werden.

Die Funktion "MorphFilter" kann durch Analyse des Rangvektors noch weitere für die Segmentierung wichtige Informationen liefern:

- Klassifikation von Start- und Endpunkten von Chains

- Klassifikation von verbundenen singulären Punkten,

- Klassifikation von singulären Punkten des Rangs 3 und höher.

Hierzu wird der Rangvektor über eine Tabelle oder Boolesche Logik auf die Zielfunktion abgebildet. In der Linkinfo der Konturpunktliste wird dies durch Setzen entsprechender Bits markiert. Besonders vorteilhaft hat sich hierbei die in

Fig. 15 dargestellte Datenstruktur für Konnektoren nach der Filterung durch MorphFilter erwiesen. Für Konturpunkte vom Rang 2 werden maximal 3 LINKs benötigt, da das Abtrennen von Appendizes nur für Punkte vom Rang 3 zugelassen ist.

Die gegenüber der in Fig. 13 enthaltenen zusätzlichen Bits bedeuten:

C: continue (1 Bit zur Segmentierung),

S : Start/Endpunkt (1 Bit),

MASKl: entspricht den Bits 0 bis 2 von MASK,

LinkAdr: entspricht der oben beschriebenen LinkAdr[0 - 2], die vierte wird nicht benötigt

Beim späteren Lesen der Information wird durch Dekodierung des Rangs von MASK (Rang gleich 2) das in Fig. 15 gezeigte Format erkannt.

Singuläre Punkte mit einem Rang größer gleich 3 können mit der in Fig. 16 dargestellten Datenstruktur codiert werden. Hierbei bezeichnet der Eintrag CONN33 eine Konnektormatrix für die Verbindung von singulären Punkten des Rangs 3 oder 4. Beim späteren Lesen der Information wird durch Dekodierung des Rangs von MASK (Rang größer 2) das in Fig. 16 dargestellte Format erkannt.

Die zusätzlichen Information werden zum Zeitpunkt der Segmentierung verwendet. Deshalb speichert MorphFilter die Struktur in einem RAM ab.

Die so vorbereiteten Informationen der Konturpunktliste können direkt aus dem Speicher in geordneter Reihenfolge als geordnete Reihe von Konturpunkten, die nachfolgend auch als "Chain" bezeichnet wird, ausgelesen werden, so daß aufeinanderfolgende Listeneinträge zu aufeinanderfolgenden Konturpunkten entlang einer Kontur gehören.

Die Chains werden dabei mithilfe einer nachfolgend als GetNextCP bezeichneten Struktur ermittelt. GetNextCP liest die Linkinfo des Zentralpunkts in einem zum MorphFilter verzögerten Prozeß. Die Verzögerung beträgt typisch 8 Spalten, kann aber bei größeren Speichern auch größer gewählt werden. ChainReadOut scannt die einlaufenden Konturpunkte auf Start- und Endpunkte. Diese weisen bei der

in Fig. 15 gezeigten Datenstruktur die Merkmale Rang (MASK) =2 und S=I auf.

Wenn ein solcher Punkt entdeckt wurde, wird die Linkinfo der beiden Nachbarpunkte ausgewertet, es wird nach dem singulären Punkt gesucht (Rang 1 oder 3,4). Wenn nur ein Nachbar mit S=I gefunden wird, dann wird dieser als Startpunkt erklärt. Er bildet den ersten Vertreter einer Chain. Ferner wird der Link auf den nächsten Punkt generiert. Sämtliche Elemente der Chain erhalten eine neue Segmentnummer, die auch an sämtliche weitere Vertreter der verbundenen Punktmenge vererbt wird. Falls zwei singuläre Punkte benachbart sind, wird der erste gefundene verwendet, der Rest ergibt sich automatisch. Falls das "Continue" - Bit gesetzt wurde, wird der Aufbau von Chains fortgesetzt.

GetNextCP ermittelt zunächst anhand von MASK die Zutändigkeit, die nach einer in einem Decoder hinterlegten Tabelle definiert ist. Die Tabelle liefert die Anzahl der Nachbarn sowie die Positionen, auf die zugegriffen werden kann. Aus der Linkinfo in der Konturpunktliste werden die Pointer auf die Nachbarn und die Adressen der beiden LINKs berechnet .

Ein möglicher Aufbau der GetNextCP-Struktur 50 ist in Fig. 17 dargestellt. Die Datenstruktur 51 mit den Einträgen MASK, C, MASKl, S und LinkAdr, entsprechend der genauer in Fig. 15 dargestellten Datenstruktur, steuert die Verlinkung zu Chains. Im Decoder 52 ist die oben genannte Tabelle hinterlegt.

Wenn ein Startpunkt (S=I) adressiert wurde, so hat dieser den Rang 2 und somit zwei Nachbarn. In diesem Fall wählt der Decoder 52 beide mögliche Links aus, decodiert den Link mit einem nicht dem Rang 2 entsprechenden Nachbarn und

setzt den Startpunkt eines Chains auf diesen Konturpunkt, indem der Wert PTR_Start generiert wird. Der andere Link wird über den Multiplexer 53 und den Addierer 54 als neuer Pointer PTR_new weitergegeben.

Wenn S=O gefunden wird, d.h. wenn der Konturpunkt kein Start- oder Endpunkt ist, wird nur ein Link ausgewählt. Die Auswahl wird über die Maskenbits MASKl gesteuert. Indem ein neuer Pointer PTR_new generiert wird, wird automatisch das zugehörige Maskenbit rückgesetzt, sodaß eine wiederholte Adressierung desselben Konturpunkts ausgeschlossen wird. Verlinkten Konturpunkten wird eine Segmentnummer zugewiesen. Da ab diesem Zustand keine Linkinfo mehr benötigt wird, kann hierzu der Low-Teil des Datenworts verwendet werden.

Während des Prozesses werden die Pointeradressen ständig überwacht. Wenn ein Signal out_of_range kommt, d.h. wenn der zulässige Index die vorgegebene untere oder obere Grenze verläßt, wird der Prozeß abgebrochen. Auf dem entsprechenden Konturpunkt wird das C-bit (continue) gesetzt und die Segmentnummer gespeichert. Wenn bei wiederholtem Auslesen der Pointer innerhalb des erlaubten Bereichs liegt, kann der Prozeß fortgesetzt werden. Am Ausgang des Prozesses entsteht eine für jedes Segment geordnete Folge von Pointern. Da die entsprechenden Konturpunktattribute zu diesen Pointern korreliert gespeichert wurden, können die Attribute direkt ausgelesen werden .

Bei der Verarbeitung der Chains können außerdem folgende Ausnahmefälle auftreten:

1. beide Startpunkte eines Chains werden verarbeitet, so dass zwei verschieden indizierte Segmente aufeinander stoßen (Koinzidenz)

2. keiner der Startpunkte wird verarbeitet, weil entweder das Objekt keine hat (etwa bei einem Kreis oder einer geschlossenen Kontur) oder weil die Startpunkte weit vor der aktuellen Abtastposition liegen, so dass sie nicht erfasst werden können,

3. Die Kontur schneidet die Bildbegrenzung (Randpunkte).

Im ersten Fall treffen die Chains mit zwei verschiedenen Segmentnummern aufeinander, sie laufen jedoch nicht ineinander, weil die Maskenbits dies verhindern. Durch den Test, dass ein Abbruch bei einem Rang ungleich 2 entsteht, kann die Vorrichtung erkennen, dass es sich um eine sogenannte Koinzidenz handelt. Der betreffende Rang 2 des Koinzidenzpunkts wird wie ein singulärer Punkt behandelt, der Segmente miteinander verbindet, nur hier mit dem Unterschied, dass nur ein Objekt vorhanden ist.

Im zweiten Fall wird nach dem Auslesen der Chains ein weiterer Test durchgeführt, der bisher nicht verarbeitete Nachbarschaften des Typs <2,2,2,x> analysiert und dann einen Startpunkt generiert. Die weitere Verarbeitung erfolgt wie oben beschrieben.

Randpunkte, die zwischen aufeinanderfolgenden Streifen auftreten können, werden wie Koinzidenzpunkte mit Rang 2 behandelt und anschließend aufeinander referenziert .

Der Konturpunktprozessor liefert über einen ersten Port einen laufenden Datenstrom von attributierten Konturpunkten, im schlechtesten Fall sind bei sehr fein aufgelösten Grauwertbildern ca. 20 bis 25% der Pixel als Konturpunkte abgespeichert.

Nachfolgend soll eine Realisierung für einen üblicherweise kleinen DualPortRAM von Ik x 36 bit beschrieben werden, welche auch eine solche Menge an Konturpunkten verarbeiten kann. Mit diesem DualPortRAM kann ein Bildauszug mit 512 Konturpunkten inklusive der Zusatzinformation und Attribute zwischengespeichert werden, dies entspricht im Beispiel einem minimalen Pixelblock der Größe 70 x 26 Pixel. Der Konturpunktprozessor liest die Bilddaten in mehreren Streifen aus, die jeweils eine Breite von mehr als 1 Pixel, vorzugsweise zumindest 16 Pixel, besonders bevorzugt 26 oder 32 Pixel aufweisen. Beim nachfolgenden Beispiel werden Streifen von 26 Pixel Höhe mäanderförmig über die gesamte Bildbreite ausgelesen, anschließend folgt der nächste Streifen. Die Daten werden als Liste gespeichert, im Attribut werden die Koordinaten gehalten.

Der Konturpunktprozessor 5 beginnt mit dem Speichern der Konturpunkte. Nachdem 5 Spalten eingelaufen sind, kann der SNNC 7 beginnen zu arbeiten, der Konturpunktprozessor 5 läuft währenddessen weiter.

Die maximale Pointeradresse kann exakt berechnet werden. Hierzu wird bei jedem Spaltensprung der Adressindex gespeichert und um 5 Spalten verzögert ausgelesen, praktisch genügt auch ein konstanter Offset, z.B. -32 , da der Speicher genügend groß ist. Der SNNC 7 liest aus dem DualPortRAM zunächst 5x5 Nachbarschaften aus, und speichert Attribute der betreffenden Konturpunkte in einem Registersatz ab.

Der Prozeß MorphFilter des morphologischen Filters 11 benötigt fertig abgespeicherte und gefilterte Links, deshalb wird ein Sicherheitsabstand von 3 Spalten zur Verarbeitung der Daten durch den SNNC 7 eingehalten.

Der Segmentierungsprozeß hingegen benötigt einen noch größeren Abstand. Grund hierfür ist das rechenintensivere Konturfolgeverfahren. Um ein umständliches Zusammensetzen von Konturen zu vermeiden, sollte die Konturen auf einer möglichst großen Länge ungestört verfolgt werden können. Ein typischer Wert hierfür beträgt 8 Spalten. Immer dann wenn ein Startpunkt oder ein gesetztes Continue-bit aus einer vorangegangenen Operation gefunden wurde, wird die GetNextCP-Struktur 50 angestoßen.

Die Steuerung hierfür wird man zweckmäßig nicht über den DualPortRAM sondern eine getrennte einfache Schieberegisterstruktur realisieren, um Speicherbandbreite zu sparen.

Der SNNC ist nach der Verarbeitung von ca. 3 Spalten nachdem der Konturpunktprozessor 5 abgespeichert hat, mit seinem Prozeß fertig. Folglich steht die für MorphFilter benötigte Information ca. nach der Verarbeitung von 6

Spalten durch den Konturpunktprozessor 5 zur Verfügung.

Die so vorverarbeiteten Konturdaten können in den Hauptspeicher des IEBVS 1 zurückgeschrieben werden und anschließend vom Mikrocontroller formatiert und für die nachfolgenden Verarbeitungsprozesse übernommen werden.

Im folgenden wird die weitere Filterung der Chains beschrieben, mit welcher Artefakte, die beispielsweise durch Rauschen in den Bilddaten entstehen können, erkannt und entsprechende Chains ausgefiltert werden.

Die Chains haben dazu die Form einer Folge geordneter Konturpunkte, die von einem Startpunkt ausgehend einen Endpunkt erreichen, wobei durch einen vorgeschalteten

Prozess Attribute zugewiesen sind. Neben dem Kontrast wird auch die Abtastrichtung als Attribut gespeichert.

Für die Bewertung der Relevanz eines Chains ist es sinnvoll, den Kontrastbelag zu berechnen. Als relevant werden Chains bewertet, wenn der Betrag des Kontrastbelages über einer gegebenen Schwelle liegt. Hierzu werden die Kontrastwerte der einzelnen Konturpunkte entsprechend ihrer Zählrichtung akkumuliert. Fig. 18 zeigt ein Chainsegment mit den Punkten PO bis P8, deren Abtastrichtungen durch Pfeile gekennzeichnet sind.

Jedem Konturpunkt ist eine der vier in Fig. 19 dargestellten Abtastrichtungen DirO, Dirl, Dir2, Dir3 zugeordnet. Entlang der jeweiligen Abtastrichtungen tritt lokal der maximale Kontrast auf. Die nachstehende Tabelle 1 listet die Konturpunkte und ihre Abtastrichtungen auf, die weiteren Spalten werden im folgenden erklärt .

Tabelle 1:

In Tabelle 2 werden die Differenzwinkel zwischen den Abtastrichtungen DirO bis Dir3 der Konturpunkte und dem

Richtungsvektor [δx, δy] des Chains ausgewertet.

Tabelle 2

Für das hier verwendete Koordinatensystem mit dem Koordinatenursprung links oben, wie in Fig. 18 dargestellt, ergeben sich die Abtastrichtungen DirO bis Dir3 als:

DirO = [ 1, 0],

Dirl = [ 1, -i],

Dir2 = [ 0, -1],

Dir3 = [ -1, -1] -

Die Spalte „Zählrichtung" in Tabelle 2 beschreibt die zu erfüllende Bedingung für eine positive Zählrichtung des Kontrastbeitrages des aktuellen Konturpunktes. Bei der Formatierung der Chains wird der Kontrastbelag durch Hardware akkumuliert, indem zunächst das Vorzeichen aus der Richtung Dir und dem Vektor [δx , δy ] = [Pi ₊ i -Pi] berechnet wird. Man bestimmt für jeden Konturpunkt die Vorzeichen von δx , δy, δx + δy sowie δx -δy und verknüpft diese mit den Bedingungen gemäß Tabelle 2. Für das Chainsegment gemäß Fig. 18 sind in Tabelle 1 δx, δy und die ermittelte Zählrichtung eingetragen. Für den letzten Punkt P8 ist der Richtungsvektor [δx , δy ] nicht definiert, deshalb wird der Richtungsvektor von P7 verwendet.

Fig. 20 zeigt die Hardwarerealisierung eines Kontrastakkumulators 80 zur Bestimmung des Kontrastbelags

einer Kontur, beziehungsweise der zugehörigen Chain. Eine erste Stufe bestehend aus zwei Komparatoren 81, 82 und zwei Addern 83, 84 bestimmt die Vorzeichen der Terme δx, δy, δx + δy sowie δx - δy. Eine kleiner lokaler Speicher 85 (LUT) oder eine äquivalente Logikschaltung dekodiert das relevante Vorzeichen entsprechend der Richtung DirO,..., Dir3 des aktuellen Konturpunkts. Anschließend werden die Kontrastwerte Conti in einem Akkumulator 86 vorzeichenrichtig addiert, so dass am Endpunkt der Kontur der Kontrastbelag σ _CO n _t als Summe der einzelnen Kontrastwerte vom Akkumulator 86 entnommen und als Attribut der Kontur gespeichert werden kann. Der Kontrastbelag σ _CO n _t stellt damit eine gute Näherung für das Integral der Differenzen der von der Kontur aus gesehen linken und rechten Grau- und/oder Farbwerte dar und beschreibt damit die Signifikanz eines Konturelements.

Die Kontrastbelegung wird anschließend in einem Chainfilter für die Filterung von Artefakten verwendet. In diesem Filter wird außerdem der durch die Chainverarbeitung bereits bekannte Grad des Start- und Endpunkts, sowie die Anzahl der Konturpunkte auf einem Chain verwendet. Diese Merkmale werden als Chainattribute bezeichnet und klassifiziert. Ein Klassifikator des Chainfilters hat die Aufgabe, anhand der genannten Merkmale zu entschieden, ob es sich bei dem aktuellen Chainsegment um eine sinnvolle Struktur handelt oder aber ein etwa auf Grund von Rauschen entstandenes Artefakt. Dieses, beziehungsweise die zugehöroge Chain wird anschließend gelöscht, um das Datenvolumen in den weiteren Verarbeitungsschritten zu reduzieren .

Die Tabelle 3 listet Bedingungen eines einfachen

Klassifikator, um rauschbehaftete Chains zu unterdrücken.

Alle Chainsegmente, die die hier aufgeführten Bedingungen erfüllen, werden als Störung klassifiziert und gelöscht.

Für die mit summarischer Kontrast bezeichneten Kombinationen wird jeweils eine Funktion aus Länge und Kontrastbelag berechnet und dann so quantisiert, dass die jeweilige Chain in einem topologischen Filter weiter verarbeitet werden kann.

Tabelle 3:

Mit der ersten Bedingung werden Chains aussortiert, bei welchen die Länge der Kontur kleiner als ein vorgegebener Wert, hier speziell kleiner als 10 Pixel ist, wobei sowohl der Start-, als auch der Endpunkt der Kontur den Grad 1 auf weisen. Demgemäß liegt hier eine sehr kurze, isolierte Kontur vor.

Bei den Bedingungen gemäß der zweiten und dritten Zeile werden ebenfalls kleine Konturen herausgefiltert, wobei hier ein Ende der Kontur mit einer weiteren Kontur

verbunden ist. Demgemäß handelt es sich hier um kurze Abzweige an anderen Konturen.

Sind Start- und Endpunkt der Chain identisch, so repräsentiert die Chain eine in sich geschlossene Kurve, wie etwa einen Kreis. Ist eine solche Kurve zu klein, wird sie gemäß der 4. Bedingung der Tabelle ausgefiltert, wobei im Speziellen wiederum Chains von Konturen mit einer Ausdehnung von höchstens 10 Pixeln gelöscht werden.

Die letzten vier Bedingungen betreffen Konturen, deren Konturpunkte eine Kontrastbelegung mit einem summierten absoluten Kontrastwert kleiner als 320 aufweisen. An diesem Beispiel zeigt sich, daß bei der Bewertung der Relevanz des Kontrastes vorteilhaft auch die Länge der Kontur mit einbezogen werden kann. Ist eine Kontur mit schwachem Kontrast vergleichsweise lang, so kann der akkumulierte Betrag des Kontrastes den Schwellwert dennoch überschreiten und die Kontur, beziehungsweise die zugeordnete Chain wird als relevant bewertet und nicht aussortiert.

Fig. 21 zeigt die Phasenlage und den Speicherbedarf der vorstehend beschriebenen Prozesse zur Bildverarbeitung bis zur Segmentierung der Bilddaten. Der Gesamtspeicher 60 ist aufgeteilt in einen Speicherbereich 61 für die Ermittlung von Konturpunkten, einen Speicherbereich 62, welcher vom SNNC 7 verwendet wird, einen Speicherbereich 63 für den morphologischen Filter 11 und einen deutlich größeren Speicherbereich 64 für die Segmentierung. Dem SNNC 7 als Hardwareeinheit zur Ermittlung von zu einer Kontur gehörenden Verbindungen zwischen Konturpunkten ist dabei ein Speicher oder Speicherbereich zugeordnet, dessen Grosse höchstens 20 Prozent des gesamten Speichers für die Verarbeitung der Bilddaten zu die Konturen beschreibenden Objekten ausgenommen des oder der Bildspeicher beträgt.

Anhand der Fig. 22 und 23, die Ausschnitte einer Kontur mit Konturpunkten zeigen, wird nachfolgend beschrieben, wie anhand der ermittelten Konturpunktdaten als Bestandteil der Objektsegmentierung Eckpunkte der Konturen bestimmt werden. Dargestellt ist ein Ausschnitt einer Kontur 26 mit Konturpunkten 26. Das von der Segmentierungseinheit 13 der in Fig. 1 dargestellten Kgrundkonfiguration durchgeführte Verfahren zur Bestimmung von Krümmungen, insbesondere von Eckpunkten von Konturen 16 basiert darauf, daß zu einem Punkt p der Konturpunkte 26 einer Kontur 16 Tripel mit Punkten (p ^~ , p, p ⁺ ) gebildet werden, wobei die Punkte p ^~ , p ⁺ Konturpunkte darstellen, die in beiden Richtungen entlang der Kontur vom Punkt p beabstandet sind.

Bei einer gekrümmt verlaufenden Kontur 16, wie bei dem in Fig. 22 gezeigten Beispiel bilden diese Punkte (p ^~ , p, p ⁺ ) dann ein Dreieck mit Seiten der Längen a, b, c.

Zu diesen Punkten wird getestet, ob die Bedingungen (i) d ² _min < Ip-P ⁺ I ² < d ² _max ,

( ii ) d ² _min < I p-p ^' l ² < d ² _max , und

( iii ) α < α _m a _x erfüllt sind, mit d ² _m i _n , d ² _ma χ und α _max als vorgegebenen Parametern. Der öffnungswinkel α ist gegeben durch:

a wobei a den Abstand der Punkte p und p ⁺ , b den Abstand der Punkte p und p ^~ , und c den Abstand der Punkte p ⁺ und p ^~ bezeichnen. Anhand der Fig. 22 wird klar, daß bei einem sehr großen Winkel α, der sich an 180° annähert, eher nicht zu erwarten ist, daß es sich bei Punkt p um einen Eckpunkt

zwischen zwei geradlinigen Segmenten handelt. Um zu vermeiden, daß bereits sehr kleine Krümmungen an einer Kontur als Ecken intepretiert werden, kann dazu der Winkel ot _max entsprechend gewählt werden. In der Praxis eignen sich oft Winkel kleiner 160°, beispielsweise α _max = 150°.

Die Bedingungen (i) bis (iii) nacheinander für die nächsten Nachbarn des Punkts p, dann die übernächsten Nachbarn des Punkts p, usw. getestet. Wird eine der Bedingungen (i) , (ii)/ (iü) dabei für ein Tripel der Punkte (p ^~ , p, p ⁺ ) nicht erfüllt, wird der Test abgebrochen. Von den öffnungswinkeln α der Tripel mit Konturpunkt p, welche die Bedingungen (i) - (iii) erfüllen, wird der kleinste öffnungswinkel ausgewählt und dem Punkt p zugeordnet.

Wird der Test der Bedingungen (i) - (iii) abgebrochen, so wird der nächste Konturpunkt entlang der Kontur 16 als Punkt p ausgewählt und das Verfahren wiederholt. Der Abbruch kann einerseits erfolgen, wenn die Bedingungen (i) - (iii) für ein Tripel nicht erfüllt sind, oder, wenn eine vorbestimmte Anzahl von benachbarten Konturpunkten 26 untersucht wurde. Vorzugsweise wird im letzteren Fall der Test abgebrochen, nachdem Tripel mit sieben Punkten 26 beiderseits des Punkts p untersucht wurden. Je nach Anforderung kann auch eine geringere Anzahl maximal zu untersuchender Tripel festgelegt sein.

Kann für einen gegebenen Konturpunkt p kein Tripel ermittelt werden, welches die Bedingungen (i) bis (iii) erfüllt, so wird dieser Punkt von vorneherein aussortiert und nicht mehr bei der Bestimmung eines Eckpunkts berücksichtigt .

In einem zweiten Durchlauf erfolgt eine weitere Aussortierung, wenn zu einem Punkt p ein benachbarter Punkt p' existiert, für welchen die Bedingungen (i) , (ii) und (iii) erfüllt sind und der einen kleineren öffnungswinkel α ¹ aufweist. Dies ist in Fig. 23 gezeigt. Bei dem gezeigten Beispiel ist im speziellen der öffnungswinkel α' des Tripels mit Punkt p' kleiner als der öffnungswinkel α des Tripels mit Punkt p. Mit diesem zweiten Durchlauf wird vermieden, daß einem stark gekrümmten Konturbereich, der eine Ecke eines Objekts wiedergibt, mehrere eng benachbarte Eckpunkte ermittelt werden.

Die Erfindung wie vorstehend beschrieben, kann beispielsweise in einer kompakten Vorrichtung implementiert werden, um die Erkennung vom Mustern zu realisieren. Unter anderem können auf diese Weise Raster oder Formularfelder in Bilddaten unabhängig von Deformationen erkannt und zugeordnet werden. Dies ermöglicht eine schnelle Erkennung und Auswertung von Formularen, wie etwa von ausgefüllten Lotteriescheinen mit einer handlichen Vorrichtung. Die

Erkennung gelingt so auch selbst wenn das Formular Knicke oder Wölbungen aufweist, auch wenn das Bild, etwa mittels eines Handscanners unter einem Winkel aufgenommen und entsprechend verzerrt ist. Die Erkennung von ausgefüllten Formularen ist besonders für die Erfindung geeignet, da die Formulardaten an vorgegebenen Stellen eingetragen werden, so daß eine einfache Erkennung, sogar ohne aufwendige, softwaregestützte Auswertung erfolgen kann. Die ansonsten sehr komplexe Zuordnung und Identifizierung von Mustern, wie etwa dem einem Raster auf einem Lotterieschein kann hier vollständig in Form von Hardware mittels einer Pipeline-Verarbeitung und Objektsegmentierung realisiert werden .

Es ist dem Fachmann ersichtlich, daß die Erfindung nicht auf die vorstehend beschriebenen Ausführungsbeispiele beschränkt ist, sondern vielmehr in vielfältiger Weise variiert werden kann. Insbesondere können die Merkmale der Ausführungsbeispiele auch miteinander kombiniert werden.