AT503279B1 - Verfahren zur erkennung von kanten in bildern - Google Patents

Description

2 AT 503 279 B1

Die Erfindung betrifft ein Verfahren gemäß dem Oberbegriff des Patentanspruches 1.

Das menschliche Auge ist sensitiv auf in Bildern dargestellte Kanten und die Erkennung bzw. Erkennbarmachung von Kanten in einem Bild ist eine wesentliche Aufgabe für die Bildverarbeitung.

Es ist bekannt für die Bildverarbeitung Filter einzusetzen, mit denen in der von einem Bild gewonnenen Werte- bzw. Bildpunktmatrix, insbesondere Intensitätsmatrix, für jedes einzelne dieser Pixel festgestellt werden kann, ob es auf einer Kante liegt. Es ist von Interesse, die Ausprägung bzw. Intensität dieses Kantenpixels bzw. der Kante zu überprüfen, deren Berechnung mittels einer Matrix von Gewichtungsfaktoren durchgeführt wird. Diese speziell aufgebaute Matrix wird als Kantenfilter bezeichnet. Aus dem Stand der Technik sind unterschiedliche Kantenfilter bekannt, so z.B. Sobel-Filter bzw. Prewitt-Filter und Roberts-Filter. Mit derartigen Filtern erfolgt eine Faltung für das jeweilige Pixel der Pixelmatrix und dessen Umgebungsbereich. Bei der Faltung wird somit der das Pixel umgebende Bereich in einer durch den Kantenfilter vorgegebenen Größe mitberücksichtigt. Üblich sind vor allem 3x3-Filter, d.h. Filter, die einen Bereich von 9 Pixel berücksichtigen, von denen das interessierende bzw. untersuchte Pixel das in der Mitte dieses Bereichs liegende Pixel ist. Diesem Pixel wird das Resultat des Filtervorganges zugeordnet. Jedes Pixel der Pixelmatrix wird demselben Filtervorgang unterzogen.

Es ergibt sich daraus, dass ein Filter für Randreihen der Pixelmatrix nicht gut eingesetzt werden kann, da dort der außerhalb des Randes der Matrix liegende Umgebungsbereich keine Pixel zur Verfügung stellen kann. Entweder werden derartige Randpixelreihen bei der Faltung außer Betracht gelassen oder es werden fixe Werte für die nicht vorhandenen Pixel vorgegeben, um den Umgebungsbereich zu vervollständigen.

Diese Filter enthalten üblicherweise 3x3 Werte, die mit dem betrachteten 3x3 Pixel umfassenden Bereich gefaltet werden. Ein derartiger Filter umfasst zur Unterscheidung von horizontalen und vertikalen Kanten bzw. von Kanten, die orthogonal zueinander verlaufen, jeweils zwei Filtermatrizes, die jeweils mit dem 3x3 Pixel umfassenden Bereich gefaltet werden. Die erhaltenen beiden Resultate werden miteinander verknüpft; beispielsweise werden die Absolutbeträge dieser beiden Resultate addiert.

Der für das jeweils betrachtete Pixel erhaltene Verknüpfungswert dieser beiden Resultate wird in eine Kantenmatrix eingetragen und liefert eine Aussage, inwieweit das Pixel auf einer Kante liegt oder nicht. Zweckmäßig wird die gesamte erhaltene Matrix dieser Verknüpfungswerte ebenso wie einzelne Pixel einer weiteren Auswertung, z.B. einem Vergleich mit Schwellwerten, unterworfen.

Die Anwendung bekannter Filter bzw. die erforderlichen Faltungsberechnungen erfordern jedoch einen beträchtlichen Rechenaufwand, sodass der Bedarf nach einem effizienten und trotzdem exakte und verwertbare Ergebnisse liefernden Filter besteht bzw. Bedarf an einem effizienten Verfahren zur Erkennung von Kanten besteht. Erfindungsgemäß ist ein derartiges Verfahren der eingangs genannten Art durch die im Kennzeichen des Anspruchs 1 angeführten Merkmale charakterisiert.

Der eingesetzte Filter ist ausgesprochen einfach aufgebaut und bietet aufgrund der Vielzahl der in ihm enthaltenen Nullen eine außergewöhnlich große Effizienz, da Multiplikationen mit Null nicht durchgeführt werden müssen. Damit sinkt die Rechendauer bei der Auswertung von Bildern bzw. Bildpixelmatrizen im Hinblick auf vorhandene oder nicht vorhandene Kanten. Der erfindungsgemäße Filter ist ausreichend resistent gegen Rauschen. Des weiteren besitzt dieser Filter keine Vorzugsrichtung, sodass senkrecht zueinander verlaufende Kanten exakt detektiert werden können. Schließlich sind das Kantenbild und die mit den erhaltenen Verknüpfungswerten gebildete Pixelmatrix nicht gegeneinander verschoben, sondern die Pixel in dem auszuwertenden Bild und in der Matrix der Verknüpfungswerte entsprechen einander lagemäßig. 3 AT 503 279 B1

Unter dem Umgebungsbereich des jeweils ausgewerteten bzw. betrachteten Pixels werden die an das Pixel seitlich, oben und unten sowie in diagonaler Richtung angrenzenden Pixel verstanden.

Von Vorteil ist es, wenn die Verknüpfung der beiden durch die Anwendung der beiden Filtermatrizes des Filters erhaltenen Resultate zur Ermittlung des Verknüpfungswertes G mit folgenden Verknüpfungsgleichungen erfolgt: G = max (Η, V) G = max (Η, V) + A * min (Η, V) G = max (Η, V) + B * min (Η, V)2 / max (Η, V) oder G = (Η + V) / 2 + max (Η, V), H ist der Absolutbetrag des einen und V der Absolutbetrag des anderen Resultates beim Einsatz der beiden unterschiedlichen Filtermatrices.

Die letzte Berechnungsart bzw. Verknüpfungsgleichung erweist sich als besonders günstig, da viele moderne Prozessoren den Average-Operator als SIMD-Befehl unterstützen.

Es zeigte sich, dass es von Vorteil ist, wenn für den Faktor A ein Wert zwischen 0,25 und 0,50, vorzugsweise zwischen 0,30 und 0,40, gewählt wird. Für den Faktor B wird ein Wert zwischen 0,30 und 0,55, vorzugsweise zwischen 0,35 und 0,50, gewählt.

Von besonderen Vorteilen ist es, wenn auf die durch die Verknüpfungswerte G gebildete Wertematrix ein Maximumoperator angewendet wird. Soferne dieser Maximumoperator auf jeweils 2x2 Pixel angewandt wird und eine Reduktion von Zeilen und Spalten jeweils auf 50 % vornimmt, so ergibt sich der Vorteil, dass zur Berechnung jedes Pixel der sich nach Anwendung dieses Maximumoperators ergebenden Pixelmatrix alle 16 Pixel seiner 4x4-Umgebung der ursprünglichen Bildmatrix genau einmal herangezogen wurden.

Als Beispiel wird unter Bezugnahme auf die Abbildungen 1 bis 5 auf eine erstellte Pixelmatrix eines aufgenommenen Bildes 2 1 2 10 5 2 10 6 2 10 6 1 8 8 2 7 .............................. und zwar auf das zweite Pixel der zweiten Spalte ein erfindungsgemäßer Filter angewendet. Betrachtet man dieses Pixel und seinen Umgebungsbereich, so ergibt sich folgende Faltungs- 4 AT 503 279 B1

Operation für die erste Filtermatrix: 1x1 + 0x2 + 0x1 + 0x1 + 0x10 + 0x5 + 0x1 + 0x10 + (-1) x 6 = -5

Wie in Fig. 1 dargestellt, berechnet die erste Filtermatrix die Differenz der beiden dem betrachteten zweiten Pixel in der zweiten Spalte diagonal links oben und rechts unten benachbarten Pixel. Nach Errechnung der Differenz wird der Absolutbetrag der Differenz gebildet. Für die zweite Filtermatrix ergibt sich für dieses Pixel folgende Faltungsoperation: 0x1 + 0x2 + (-1) x 1 +0x1 + 0x10 + 0x5 + 1x1 + 0x10 + 0x6 = 0

Wie in Fig. 2 dargestellt, berechnet die zweite Filtermatrix die Differenz der beiden dem betrachteten zweiten Pixel in der zweiten Spalte diagonal rechts oben und links unten benachbarten Pixel. Nach Errechnung der Differenz wird der Absolutbetrag der Differenz gebildet.

Es ergibt sich für den Wert H = -5 der Absolutwert 5 und für den Wert V ergibt sich der Absolutwert 0. Wie in Fig. 3 dargestellt, werden diese beiden Werte mit einer der angeführten Verknüpfungsgleichungen verknüpft und man erhält einen Verknüpfungswert G für das interessierende Pixel.

Bei Verwendung der Verknüpfungsgleichung G = (H+V) 12 + max (Η, V) ergibt sich der Verknüpfungswert G=7,5 für das Pixel in der zweiten Spalte der zweiten Zeile. Dieser Verknüpfungswert G ist der Kantenwert des interessierenden Pixels und wird zur Beurteilung des Pixels herangezogen.

Auf eine mit den Verknüpfungswerten G für die einzelnen Pixel erstellte Matrix der Verknüpfungswerte kann sodann vorteilhafterweise ein Maximumoperator angewendet werden, mit dem aus einem Pixelquadrat von 2x2 Pixeln das Maximum ermittelt wird. Diese ermittelten Maxima werden sodann zu einer neuen Pixelmatrix zusammengesetzt. Sofern ein Maximumoperator auf einen Pixelbereich von 2x2 Pixel angewendet wird, ergibt sich eine Reduktion der Pixel sowohl in den Spalten als auch in den Zeilen auf die Hälfte. Fig. 4 zeigt eine Reduzierung der Matrix der für die Pixelmatrix erhaltenen Kantenwerte auf die Hälfte der Zeilen und Spalten. Dabei werden die Kantenwerte von vier benachbarten Pixel durch einen vorgegebenen Operator, vorzugsweise den Maximumoperator, verknüpft. Die vier Pixel werden durch ein Pixel ersetzt, das allerdings im Zentrum der vier Pixel gelegen ist, d.h. um einen halben Pixelwert gegenüber jedem ursprünglichen Pixel diagonal verschoben ist.

Bei einer derartigen Verknüpfung des erfindungsgemäß vorgesehenen neuen Filters mit einem 2x2 Maximumoperator wird der Wert jedes zugehörigen Pixels des 4x4-Umgebungsbereiches in der aufgenommenen Bildmatrix genau einmal zur Berechnung des jeweiligen Pixelwertes der sich ergebenden Wertematrix eingesetzt, die sich nach Anwendung des Maximumoperators ergibt. Damit wird ein Verlust an Informationen vermieden. Sofern man mit dem erfindungsgemäßen eine erste und eine zweite Filtermatrix umfassenden Kantenfilter eine Berechnung der Kantenwerte vornimmt, so zeigt Fig. 5, dass bei Anwendung des Filters auf das zweite und das dritte Pixel der zweiten Zeile und auf das zweite und dritte Pixel der dritten Zeile für jedes dieser Pixel die jeweils diagonal liegenden vier Nachbarpixel berücksichtigt werden. D.h., dass 16 Pixel für die Berechnung der Kantenwerte der vier Pixel herangezogen werden. Der erfindungsgemäße Kantenfilter ermöglicht, dass jeweils für jedes der vier betrachteten Pixel jeweils vier unterschiedliche Nachbarpixel berücksichtigt werden, sodass jedes Pixel des betrachteten Pixelbereiches von 4x4 Pixel nur ein einziges Mal in die Berechnung eingeht. Wird auf die resultierenden vier Kantenwerte ein Maximumoperator angewendet, so erfolgt eine Reduktion auf ein Pixel gemäß Fig. 4, wobei sämtliche Werte von den 16 betrachteten Pixel zur Berechnung des Kantenwertes des resultierenden Pixel verwendet wurden, jedoch jedes Pixel mit seinem Wert nur ein einziges Mal für diese Berechnung herangezogen wurde.

Claims (8)

1. 5 AT 503 279 B1 Patentansprüche: 1. Verfahren zur Erkennung von Kanten in Bildern, wobei auf die Wertematrix, insbesondere Intensitätsmatrix, der von den aufgenommenen Bildern abgeleiteten Bildpixel zumindest ein Kantenfilter angewendet wird, dadurch gekennzeichnet, - dass die der Filterung unterworfenen Pixel und deren Umgebungsbereich mit einem Filter gefaltet werden, der eine erste Filtermatrix 1 0 0 0 0 0 0 0-1 und eine zweite Filtermatrix 0 0-1 0 0 0 1 0 0 umfasst, - dass das jeweilige Pixel und der dazugehörige Umgebungsbereich jeweils mit jeder dieser Filtermatrizes gefaltet wird, - dass die beiden Resultate mit einer Rechenoperation verknüpft werden und - dass der erhaltene Verknüpfungswert (G) als Maß für den Betrag des Kantenwerts des jeweiligen Pixels und/oder die Zugehörigkeit des Pixels zu einer Kante angesehen bzw. beurteilt wird.
2. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Verknüpfung der beiden Resultate dadurch erfolgt, dass die Absolutbeträge dieser Resultate ermittelt und der Verknüpfungswert dieser beiden Absolutbeträge mit einer der folgenden Gleichungen berech- net wird: a) G = max (Η, V) oder b) G = max (Η, V) + A * min (Η, V) oder c) G = max (Η, V) + B * min (Η, V)2 / max (Η, V) oder d) G = (Η + V) / 2 + max (Η, V), wobei H und V die Absolutbeträge der Resultate und G den erhaltenen Verknüpfungswert darstellen und der Faktor A zwischen 0,25 und 0,50, vorzugsweise zwischen 0,30 und 0,40, und der Faktor B zwischen 0,30 und 0,55, vorzugsweise zwischen 0,35 und 0,50, liegt.
3. 3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass der Filter auf jedes Pixel der Wertematrix und dessen Umgebungsbereich einmal angewendet wird.
4. 4. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass auf an den Rändern der Pixelmatrix gelegene Pixel eine Anwendung des Filters unterbleibt oder für Pixel an den Rändern für die im Umgebungsbereich fehlenden Pixel Werte vorgegeben werden.
5. 5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass die für die einzelnen Pixel erhaltenen Verknüpfungswerte (G) in einer Matrix angeordnet werden und mit einem Maximumoperator, vorzugsweise einem 2x2-Maximumoperator, gefaltet werden.
6. 6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass gleichzeitig mit der Faltung mit dem Maximumoperator eine Reduktion von Spalten und/oder Zeilen der Matrix, insbesondere eine Reduktion der Spalten und Zeilen jeweils um 50 %, erfolgt.
7. 7. Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass vor der An- 6 AT 503 279 B1 Wendung des Kantenfilters ein Gauß-Filter zur Glättung des Bildes angewandt wird.
8. 8. Computerprogrammprodukt mit Programmcode-Mitteln, die auf einem computerlesbaren Datenträger gespeichert sind, um das Verfahren nach jedem beliebigen der Ansprüche 1 bis 7 durchzuführen, wenn das Programmprodukt auf einem Computer ausgeführt wird. Hiezu 1 Blatt Zeichnungen