DE69027616T2

DE69027616T2 - Gerät und Verfahren zum Bestimmen von Konturen und Linien

Info

Publication number: DE69027616T2
Application number: DE69027616T
Authority: DE
Inventors: Robert H Dr Meyer; Kevin K Tong
Original assignee: Hughes Aircraft Co
Current assignee: Raytheon Co
Priority date: 1989-03-27
Filing date: 1990-03-22
Publication date: 1996-10-31
Anticipated expiration: 2010-03-23
Also published as: EP0389968A2; JPH02285475A; IL93533A0; US5081689A; ES2088913T3; EP0389968A3; EP0389968B1; JP2642215B2; DE69027616D1

Description

Diese Erfindung betrifft Bildprozessoren und insbesondere eine Vorrichtung und ein Verfahren zur Bildverstärkung zur Erfassung von Rändern und Linien.
Die riesige Menge von Daten, die in der Form von Luft-, Satelliten- und anderen Typen eines Bildes verfügbar sind, überschreiten bei weitem die Verarbeitungskapazität von gegenwärtigen Computerumgebungen. Folglich besteht ein Bedarf nach Systemen, die schnell und automatisch Objekte erfassen, die große Mengen eines Bildes ergeben, das unvorhersagbare Szenen und Objekte darstellt.
Die Aufgaben von Computervisualisierungssystemen zerfallen im allgemeinen in drei Gruppen: eine untere Stufe, eine mittlere Stufe und eine obere Stufe. Die Analyse der unteren Stufe bringt ein Zerlegen des Ursprungsbildes in leicht manipulierbare visuelle Grundelemente, wie zum Beispiel Bereiche und Linien, und ihrer Attribute, wie zum Beispiel Farbe, Textur, Größe, Form, Ausrichtung, Länge, usw., mit sich. Das Verfahren der mittleren Stufe betrifft ein Analysieren der Linien und Bereiche, die in dem Verfahren der unteren Stufe festgestellt worden sind, und ein Finden von zum Beispiel bestimmten geometrischen Formen und Mustern. Die Analyse der oberen Stufe arbeitet auf den ausgedehnten geometrischen Merkmalen, um eine Erkennung und eine Beschreibung der Objekte in der Szene zu erzielen.
Die vorliegende Erfindung betrifft hauptsächlich Verbesserungen der Bildverarbeitung der unteren Stufe. Das Ursprungsbildeingangssignal für eine Verarbeitung der unteren Stufe weist typischerweise Intensitätsänderungen in einem Bild auf, die teilweise infolge eines Reflexionsvermögens, einer Tiefe, einer Ausrichtung und Beleuchtungsunstetigkeiten bestehen. Die Gliederung von bedeutsamen lokalen Intensitätsänderungen (Rändern) in kohärentere globale Ereignisse (Linien oder Grenzen) ist ein früher aber wichtiger Schritt bei der Transformation des visuellen Signals in nützliche Zwischenkonstrukte für interpretierende Verfahren der mittleren und oberen Stufe. Über die letzten zwanzig Jahre ist eine Anzahl von Verfahren zur Randerfassung entwickelt worden. Diese beinhalten:
1) eine einfache einer Schwellwertbildung unterzogene Faltung (z.B., Sobel-Operator, Roberts- Kreuzoperator) innerhalb eines fest bemessenen zweidimensionalen Fensters, worauf eine "Ausdünn"-Operation der sich ergebenden Daten folgt;
2) einen Laplace-Operator innerhalb eines zweidimensionalen Verarbeitungsfensters, der mit einem Algorithmus zum Erfassen von "Nullübergängen" gekoppelt ist;
3) den Haralick-Flächenmodellalgorithmus; und
4) den Nevatia-Babu-Algorithmus.
Ein Algorithmus zum Erzeugen verbundener Randgrenzen zwischen angrenzenden Bereichen von verschiedenen Graustufen ist in einem Artikel mit der Überschrift "Contextual Boundary Formation by One-Dimensional Edge Detection and Scan Line Matching", von Ehrich et al., in COMPUTER GRAPHICS AND IMAGE PROCESSING, Bd. 16, Nr. 2 (Juni 1981), offenbart. Eine Randerfassungseinrichtung erzeugt Datenstrukturen, die alternative Interpretationen von Randquerschnitten darstellen. Die Randannahmen werden auf der Grundlage des Grads der Übereinstimmungen zwischen den Randannahmen miteinander verbunden, um globale Ränder auszubilden. Im Detail werden relationale Bäume bezüglich angenommenen Randpunkten entlang einer Abtastzeile ausgebildet. Der verwendete Gleichheitsprüfungsalgorithmus ist ein Parallelbaumgleichheitsprüfungsalgorithmus, der die relationalen Bäume der Ränder in angrenzenden Abtastzeilen auf Gleichheit prüft. Das Verbinden wird durch ein Untersuchen mehrerer Verbindungsmöglichkeiten und ein Verwenden eines Verfahrens erzielt, das die optimale Verbindungsanordnung auf der Grundlage des Grads der Übereinstimmungen zwischen den verschiedenen angenommenen Randpunkten bestimmt.
Auch mit diesen und anderen gegenwärtigen Verfahren ist die Erzeugung von Liniensegmenten ein schwieriges Problem geblieben, das zeitaufwendige Randverkettungs- und Liniensegmentierungsalgorithmen erfordert. Somit würde es wünschenswert sein, ein Verfahren zum Erzeugen von Rändern und Liniensegmenten zu schaffen, das schneller und genauer als frühere Verfahren ist.
Neben Langsamkeit weisen die vorhergehenden Verfahren zur Randerfassung eine Anzahl von anderen Nachteilen auf. zum Beispiel sind Bilder, die eine Mehrzahl von Auflösungen und Kontrasten aufweisen, aufgrund der Verwendung eines festen zweidimensionalen Fensters oder Teilfläche schwierig handzuhaben. Es gibt zwei probleme, die sich aus der Verwendung eines festen Fensters ergeben: 1) Wenn ein Rand größer als das Fenster ist, erhält man entweder keinen Rand oder mehrere Ränder; und 2) wenn ein Fenster zu groß ist, verwischt es durch eine Mittelwertbildung von Daten innerhalb des Fensters Details. Obgleich ein Verwenden mehrerer Fenstergrößen ein Lösungsweg dieses Problems ist, hat die Komplexität eines Aussortierens der sich ergebenden Daten aus den verschiedenen Fenstergrößen die Nützlichkeit dieses Verfahrens beschränkt. Als Ergebnis würde es wünschenswert sein, einen Bildprozessor zu schaffen, der die Bildmerkmale von vielen verschiedenen Auflösungen gleich gut mit weniger verschwommenen oder fehlenden Rändern handhaben kann.
Ein in Beziehung stehendes problem, das durch eine feste zweidimensionale Fenstergröße verursacht wird, ist die sich ergebende Empfindlichkeit gegenüber Schwellwerten.
Wenn eine Fenstergröße zu klein ist, wird lediglich ein Teil eines Randes gemessen. Die Faltung ergibt dann einen Meßwert lediglich eines Teils der Intensitätsänderung und ein Schwellwert, der eingestellt ist, um die Intensitätsänderung eines gesamten Randes zu erfassen, würde zu hoch sein und würde den Rand ignorieren. Ein Verringern des Schwellwerts würde mehrere Ränder ergeben, wo lediglich ein einziger Rand existiert. Folglich würde es wünschenswert sein, einen Bildprozessor zu schaffen, der geeignet zwischen Bildmerkmalen eines hohen und niedrigen Kontrasts unterscheiden kann, ohne zu empfindlich gegenüber der Schwellwerteinstellung zu sein.
Die vorliegende Erfindung, wie sie in den Ansprüchen 1 und 9 dargelegt ist, schafft eine Vorrichtung und ein Verfahren zur Bildverstärkung, die die Ränder und geraden Liniensegmente von Bilddaten schnell und genau erfassen. Die Erfindung führt anstelle einer zweidimensionalen eine eindimensionale Analyse von Bilddaten durch, und dies ergibt anstelle einer statischen eine effektiv dynamische Fenstergröße, um sicherzustellen, daß der gesamte Rand eingefangen wird. Dies wird durch die Verwendung einer Reihe von horizontalen und/oder vertikalen Abtastzeilen durchgeführt, um eindimensionale Randsignaturen in den Intensitätsdaten einer Abtastzeile zu suchen. Randkrümmungspunkte in den Intensitätsdaten der Abtastzeile werden analysiert, um zu bestimmen, ob sie bestimmte Merkmalscharakteristiken von Rändem aufweisen. Wenn sie einmal identifiziert worden sind, werden Paare von diesen Krümmungspunkten, welche Randgrenzen darstellen, dann verwendet, um Randstellen eines einzigen Punktes zu bestimmen. Dies kann durch ein Finden des mittleren Intensitätspegels zwischen den Paaren von Krümmungspunkten und ein Bezeichnen dieses Punktes als die Randstelle durchgeführt werden. Dieses Verfahren stellt in der Tat die Fenstergröße dynamisch ein und ermöglicht es, daß Ränder von vielen verschiedenen Auflösungen und Kontrasten analysiert werden.
Nachdem eine Randstelle eines Punktes bestimmt ist, können Randstellen des Punktes auf aufeinanderfolgenden Abtastzeilen verfolgt werden, um gerade Liniensegmente auszubilden. Dies wird durch ein Einstellen eines Bereichs für eine mögliche Liniensegmentrichtung von einem ersten Punkt und ein Bestimmen durchgeführt, ob sich eine Randstelle des Punktes in der nächsten Abtastzeile innerhalb dieses Bereichs befindet. Wenn sie es ist, wird ein Liniensegment zwischen den ersten und zweiten Punkten gezogen und der zulässige Bereich für jeden Randpunkt in aufeinanderfolgenden Abtastzeilen wird verschmälert, bis ein Randpunkt nicht länger in den zulässigen Bereich paßt. Ränder, die außerhalb eine gegebenen Liniensegmentrichtung fallen, können dann verwendet werden, um neue Liniensegmente zu beginnen.
Dieses gesamte Verfahren erfordert lediglich einen oder zwei Durchläufe durch die Buddaten. Zwei Durchläufe können mit einer Parallelverarbeitungsarchitektur gleichzeitig durchgeführt werden. Das Ergebnis ist, daß das Extrahieren von Randpunkten und Liniensegmenten aus digitalisierten Bilddaten viel schneller als bei früheren vergleichbaren Verfahren ist.
Die Erfindung handhabt Bildmerkmale von vielen verschiedenen Auflösungen gleich gut. Ebenso werden Rand- und Liniensegmentdaten "deutlicher" extrahiert, so daß Linien mit weniger verschwommenen oder fehlenden Rändern weniger fragmentiert sind. Bei vielen Bildern ist der Randschwellwertparameter weniger kritisch als bei früheren Verfahren und unterscheidet geeignet zwischen Bildmerkmalen eines hohen und niedrigen Kontrasts. Die Erfindung könnte ebenso verwendet werden, um andere Intensitätsmerkmale neben Rändem, wie zum Beispiel bestimmte Merkmale, die Charakten stikkombinationen von Rändern aufweisen, wie zum Beispiel Küstenlinien, Straßen oder Fahrzeuge, zu erfassen und zu verfolgen. Ebenso könnte die Erfindung verwendet werden, um Merkmale zu erfassen, die bestimmte definierte Spektralcharakteristiken aufweisen.
Die verschiedenen Merkmale der vorliegenden Erfindung werden für einen Fachmann durch ein Lesen der folgenden Beschreibung und durch Bezugnahme auf die folgende Zeichnung ersichtlich, in welcher:
FIG. 1 eine perspektivische Ansicht einer Reihe von Bildelementintensitätskurven entlang aufeinanderfolgender Abtastzeilen von typischen Bilddaten darstellt;
FIG. 2 einen Graph einer einzigen Bildelementintensitätskurve für aufeinanderfolgende Bildelemente entlang einer einzigen Abtastzeile gemäß der vorliegenden Erfindung darstellt;
FIG. 3 einen die Ableitung eines Randpunktes aus zwei Krümmungsextrema zeigenden Graph eines Abschnitts der in FIG. 2 gezeigten Bildelementintensitätskurve darstellt;
FIG. 4 eine Darstellung des Verfahrens eines Ausbildens der Liniensegmente durch ein Verfolgen von Randpunkten gemäß der vorliegenden Erfindung zeigt; und
FIG. 5 eine Darstellung eines Bildverarbeitungssystems gemäß der vorliegenden Erfindung zeigt.
FIG. 1 stellt ein zweidimensionales Signal (d.h., ein Bild) dar. Die x- und y-Achsen sind die horizontalen und vertikalen Achsen des Bildes, während die dritte Achse die Intensität (Helligkeit) des digitalisierten Bildes an jedem Punkt (Bildelement) darstellt. Die Quelle des Bildes kann Licht oder andere Bereiche des elektromagnetischen Spektrums sein; oder es könnte ein akustisches Bild oder irgendein anderes wünschenswertes zweidimensionales Signal sein. Als ein bestimmtes Beispiel könnte das digitalisierte Bild aus einem CCD-Sensor erzielt werden, der an eine Bildfangschaltung angeschlossen ist, die das CCD-Ausgangssignal digitalisiert und eine Matrix von 512 x 512 von Bildelementintensitätswerten erzeugt. Diese Werte würden automatisch in einem Computerspeicher gespeichert. Es ist anzumerken, daß FIG. 2 zur Klarheit lediglich 32 Bildelementintensitätspunkte zeigt. Wenn jedoch ein CCD-Sensor für 512 x 512 Elemente verwendet wird, würde eine gegebene Abtastzeile tatsächlich 512 Bildelementintensitätspunkte aufweisen.
Gemäß der vorliegenden Erfindung ist der Intensitätswert jedes Bildelements auf der Bildelementintensitätskurve 10 durch Intensitätspunkte 12 dargestellt. Es ist zu erkennen, daß die Intensitätsdaten in den Figuren 1 und 2 als eine veranschaulichende Hilfe bildlich aufgetragen sind. In der Praxis können die Verfahren der vorliegenden Erfindung durch ein Durchführen verschiedener Berechnungen an den Daten ausgeführt werden, ohne tatsächlich die Daten aufzutragen. Auf eine ähnliche Weise wird der Ausdruck "Abtasten" verwendet, um eine Analyse von Daten entlang einer einzelnen vertikalen oder horizontalen Zeile anzuzeigen, und schließt in sich nicht notwendigerweise irgendeine mechanische Abtastungsbewegung über dem Bild ein.
Die vorliegende Erfindung bringt ein zweiteiliges Verfahren mit sich, um Liniensegmente aus Bilddaten zu erzielen. Der erste Teil bringt die Erfassung von Randpunkten mit sich. Der zweite Teil bringt das Verfolgen der erfaßten Randpunkte mit sich, um gerade Linien auszubilden. Es ist zu erkennen, daß, wenn die Randpunkte einmal erfaßt worden sind, die Randpunkte eine Information liefern werden, die auf viele Weisen verwendet werden kann. In dem bevorzugten Ausführungsbeispiel ist es jedoch bevorzugt, daß die Randpunkte, die von dem ersten Teil der Erfindung bestimmt werden, dann verwendet werden, um gemäß dem zweiten Teil der Erfindung Liniensegmente zu erzielen.
In dem ersten Teil der vorliegenden Erfindung wird die Erfassung von Randpunkten als ein eindimensionales Verfahren ausgeführt. Zu Beginn werden die Intensitätsdaten, wie zum Beispiel jene, die in FIG. 2 gezeigt sind, auf Intensitätssignaturen analysiert, die Charakteristiken von Rändern sind. Dies kann durch eine erste Verarbeitung der Daten mit einem Gleitdifferenzoperator durchgeführt werden, um lokale "Steigungen" an jedem Punkt 12 entlang der Abtastzeilenintensitätskurve 10 zu erzielen. Insbesondere wird für einen gegebenen Punkt 14 auf der Intensitätskurve 10 die Steigung der Linie, die den Punkt 14 mit dem vorhergehenden Punkt 16 verbindet, bestimmt. Auf eine ähnliche Weise wird für einen nachfolgenden Punkt 18 die Steigung einer Linie, die diesen Punkt 18 mit dem vorhergehenden Punkt 14 verbindet, bestimmt. Die Steigungen der ersten Ableitung werden dann zu Winkeln oder "Winkelsteigungen" gewandelt, wobei die Funktion verwendet wird:
Winkel = tan&supmin;¹ (c x Steigung)
wobei c eine Konstante (weniger als 1), wie zum Beispiel .75, ist. Der für c gewählte Wert ist nicht besonders kritisch. Er wirkt als eine vertikale Erhöhung oder Verstärkung der Bildelementintensitäten und wird eingestellt, um eine zweckdienliche ganzzahlige tabellarische Darstellung der Winkelfunktion zu ermöglichen.
Eine Gleitdifferenz von Winkelsteigungen kann dann genommen werden, um eine Steigungskrümmung an jedem Punkt entlang der Abtastzeile zu erzielen. Zum Beispiel wird die Steigungskrümmung an einem ersten Punkt 14 gleich der Winkelsteigung an dem zweiten Punkt 18 minus der Winkelsteigung an dem ersten Punkt 14.
Als nächstes werden Krümmungsextrema lokalisiert. Krümmungsextrema stellen Punkte auf der Intensitätskurve 10 dar, welche maximale positive oder negative lokale Steigungskrümmungen aufweisen. In FIG. 2 sind Krümmungsextrema durch die umkreisten Punkte 20 dargestellt. Die Bestimmung, welche Krümmungen Extrema sind, wird durch ein Vergleichen der Beträge einer aufeinanderfolgenden Folge von Krümmungen durchgeführt, die das gleiche Vorzeichen besitzen. Es ist durch eine Überprüfung in FIG. 2 zu sehen, daß Krümmungsextremapunkte 20 Punkte darstellen, an denen es relativ große Änderungen der Steigung zwischen den Krümmungsextremapunkten 20 und den vorhergehenden und nachfolgenden Punkten gibt. Anders ausgedrückt, Krümmungsextrema sind Stellen, an denen Tendenzen einer Intensitätsänderung einen größeren Wechsel erfahren. Es ist dieser schnelle Wechsel von Intensitäts-(oder Schattierungs-)-Tendenzen, der die zwei Seiten von Randgrenzen in Bilddaten kennzeichnet. Dies ist in FIG. 3 gezeigt.
Es ist anzumerken, daß in einigen Systemen Rauschen aus dem Sensor oder anderen Quellen Spitzen oder Zacken einbringen kann, die nichts mit dem zu analysierenden Bild zu tun haben. Unglücklicherweise werden solche Rauschzacken möglicherweise als Krümmungsextrema interpretiert. Um ein solches Rauschen effektiv auszufiltern, können alle Krümmungsextrema überprüft werden, um zu sehen, ob sie einen Rauschschwellwert überschreiten. Dieser Rauschschwellwert kann als proportional zu den Steigungen der Abtastzeilenintensitätskurve an den Punkten, an denen die Extrema lokalisiert werden, gewählt werden. xrümmungsextrema, welche den Schwellwert überschreiten, können dann ignoriert werden, da sie wahrscheinlich Rauschen darstellen. Es ist zu erkennen, daß der Schwellwert von vielen Charakteristiken des Systems und von den eingebrachten Bilddaten abhängen wird, und in Systemen, die nicht empfindlich gegenüber unzulässigen Rauschpegeln sind, kann der Schritt eines Vergleichens der Krümmungsextrema mit dem Rauschschwellwert vollständig weggelassen werden.
Der nächste Schritt besteht darin, die Existenz eines Randes aus den Krümmungsextremapunkten 20 zu bestätigen. Da die Krümmungsextremapunkte 20 durch die Daten selbst bestimmt werden, stellt die Erfindung in der Tat eine dynamische Fenstergröße ein, aus welcher Ränder zu finden sind. Aus FIG. 2 ist zu sehen, daß die Intensitätsdifferenz zwischen dem ersten Krümmungsextrema 20 an der äußersten linken Seite und dem zweiten Krümmungsextrema 20 ziemlich klein ist; während die Differenz der Intensität zwischen dem zweiten Krümmungsextrema 20 und dem dritten viel größer ist. Man kann dies so interpretieren, daß es bedeutet, daß ein Rand irgendwo zwischen dem zweiten und dritten Krümmungsextrema 20 existiert, aber eine Oberfläche einer relativ gleichmäßigen Intensität (und daher kein Rand) zwischen dem ersten und zweiten Krümmungsextrema 20 existiert. Demgemäß wird der Intensitätspegel an jedem Krümmungsextrema 20 mit dem an dem benachbarten Krümmungsextrema 20 verglichen, um Ränder zu erfassen. Wo die Differenz einen vorbestimmten Schwellwert überschreitet, wird ein Rand bestätigt.
Dieses Verfahren ist detaillierter in FIG. 3 dargestellt. Darin ist ein Abschnitt der Intensitätskurve 10 gezeigt, der zwei Krümmungsextrema 20 aufweist. Der Intensitätspegel an dem ersten Krümmungsextrema 20 ist mit I&sub1; bezeichnet. Die Intensität an dem zweiten ist I&sub2;. Ein Rand wird bestätigt, wenn die Änderung der Intensität, I&sub2; - I&sub1; einen vorbestimmten Schwellwert überschreitet. In einigen Fällen ist es möglich, daß die Differenz zwischen dem Intensitätspegel den Schwellwert auch dort überschreitet, wo es keinen Rand gibt. Dies kann zum Beispiel in dem Fall eines ausgedehnten Bereichs einer feinen Schattierung auftreten, an dem die gesamte Änderung des Intensitätspegels von der einen Seite der Bereichs zu der anderen ziemlich groß ist, aber kein Rand zwischen den zwei Extrema existiert. Um zu verhindern, daß ein Rand in einem Bereich einer feinen Schattierung festgestellt wird, wenn festgestellt wird, daß die Intensitätsdifferenz zwischen zwei benachbarten Krümmungsextrema den vorbestimmten Schwellwert überschreitet, kann die mittlere Intensitätsänderung pro Bildelement überprüft werden. Wenn die mittlere Intensitätsänderung pro Bildelement weniger als ein vorbestimmter Betrag, zum Beispiel eine Intensitätseinheit ist, dann kann darauf geschlossen werden, daß der Bereich keinen Rand enthält, sondem stattdessen ein Bereich einer allmählichen Intensitätsänderung ist. In solchen Fällen wird kein Rand zwischen solchen Krümmungsextrema festgestellt.
Wenn die Existenz eines Randes zwischen zwei Krümmungsextrema 20 einmal bestätigt worden ist, kann dann die Randstelle des Punktes bestimmt werden. Dies kann durch ein Finden des mittleren Intensitätspegels zwischen den zwei Krümmungsextrema 20 durchgeführt werden. Das heißt, der Intensitätspegel gleich (I&sub1; + I&sub2;)/2 wird festgestellt. Das Bildelement, das dem mittleren Intensitätspegel auf der Intensitätskurve 10 entspricht, wird dann bestimmt. Die Stelle dieses Bildelements entlang der Abtastzeile wird dann als ein Randpunkt bezeichnet. Das vorhergehende Verfahren wird für jeden Krümmungsextrempunkt 20 durch die gesamte Intensitätskurve 10 hindurch für eine gegebene Abtastzeile wiederholt.
Um ein Ausbilden von Liniensegmenten gemäß dem zweiten Teil der vorliegenden Erfindung zu beginnen, wird das gesamte zuvor beschriebene Verfahren für eine zweite Abtastzeile wiederholt. Wenn einmal Randpunkte in der zweiten Abtastzeile festgestellt worden sind, können sie mit Randpunkten in der vorhergehenden Abtastzeile verglichen werden, um zu bestimmen, ob ein Liniensegment zwischen Randpunkten in der ersten und der zweiten Abtastzeile unter Verwendung des nachfolgend beschriebenen Verfahrens gezogen werden kann. Das Linienausbildungsverfahren wird dann für alle nachfolgenden parallelen Abtastzeilen wiederholt.
Genauer gesagt werden gemäß der vorliegenden Erfindung, wenn jede Abtastzeile verarbeitet ist und in einem Satz von ausgewählten Randpunkten verbleibt, die Randpunkte so verfolgt, wie wenn sie Ziele einer gleichmäßigen Geschwindigkeit gewesen wären. Die aus einer gegebenen Abtastzeile extrahierten Randpunkte sind Randpunkten zugehörig, die gemäß den folgenden drei Regeln in vorhergehenden Abtastzeilen erfaßt worden sind:
1) Wenn ein erfaßter Randpunkt innerhalb "n" Bildelementen eines Randpunktes auf der vorhergehenden Abtastzeile liegt, wo der Punkt auf der vorhergehenden Zeile nicht bereits einem geraden Linienelement zugehörig ist, werden die zwei erfaßten Randpunkte verwendet, um ein gerades Liniensegment zu beginnen.
2) Wenn ein erfaßter Randpunkt nicht innerhalb "n" Bildelementen eines Randpunktes auf der vorhergehenden Abtastzeile liegt und er ebenso keinem existierenden geraden Linienelement zugeordnet werden kann, wird die Stelle des erfaßten Randes für den Startpunkt eines neuen Linienelements gespeichert.
3) Wenn ein erfaßter Randpunkt innerhalb "n" Bildelementen einer vorhergesagten Randpunktstelle liegt (wo die Vorhersage unter Verwendung einer Kenntnis der Liniensegmente durchgeführt worden ist, die momentan verfolgt werden), wird versucht, den neuen Randpunkt auf die nachstehend beschriebene Weise dem zweckmäßigen Liniensegment hinzuzufügen.
Die Auswahl von "n" ist nicht kritisch und wird so betrachtet, daß die genaue Anzahl durch Versuch-und-Fehler optimiert werden kann. Zum Beispiel kann "n" in einigen Gestaltungen als 1 oder 2 Bildelemente gewählt werden.
Es wird nun Bezug auf FIG. 4 genommen, in der das Verfahren zum Hinzufügen zu einem existierenden Liniensegment dargestellt ist. Aus Regel 1 zuvor ist zu sehen, daß die ersten zwei Randpunkte verwendet werden können, um ein gerades Liniensegment zu beginnen. Aus diesen zwei Punkten wird eine anfängliche geplante Liniensegmentrichtung berechnet. Diese ist in FIG. 4 mit "erste Schätzung einer Liniensegmentrichtung" bezeichnet. Ein "Fehlerbalken" einer vorbestimmten Anzahl von Bildelementen (typischerweise 1 oder 2 Bildelemente) ist ebenso dem zweiten Punkt zugewiesen. Dieser Balken wird verwendet, um den Bereich zu bestimmen, innerhalb welchem die Liniensegmentrichtung eingestellt werden kann, wenn spätere Punkte dem Liniensegment hinzugefügt werden. Die Idee besteht darin, einige Schwankungen der tatsächlichen Position der Randpunkte entlang des Liniensegments, zu welchem sie gehören, zuzulassen. Andererseits darf es nicht zulässig sein, daß die Punkte leicht von der anfänglichen Liniensegmentrichtung abweichen, was anstelle einer geraden Linie zu einem Bogen führt.
FIG. 4 zeigt ebenso einen dritten Punkt, der dem Liniensegment hinzugefügt wird. Da der dritte Punkt in den zulässigen Liniensegmentbereich fällt (er befindet sich zwischen der ersten oberen Grenze und der ersten unteren Grenze einer Liniensegmentrichtung), erfüllt er das Kritenum, welches bestimmt, daß er ein Teil des Liniensegments und nicht der Beginn einer neuen Linie ist. Die dem dritten Punkt zugewiesenen Fehlerbalken werden verwendet, um einen neuen und festeren Bereich zu bilden, in welchem die Liniensegmentrichtung eingestellt werden kann. Dieser Bereich ist in FIG. 4 als durch die Linien, die mit "zweite obere Grenze auf Liniensegmentrichtung" und "zweite untere Grenze auf Liniensegmentrichtung" bezeichnet sind, definiert. Es ist anzumerken, daß die zweite untere Grenze auf Liniensegmentrichtung mit der ersten unteren Grenze auf Liniensegmentrichtung übereinstimmt, womit die neuen Grenzen auf die Liniensegmentrichtung effektiv verschmälert werden. Die zweite Schätzung der Liniensegmentrichtung wird so durchgeführt, daß sie von dem ersten Punkt zu dem dritten und neuesten Punkt führt.
Schließlich wird ein vierter Punkt betrachtet. Wie es in FIG. 4 dargestellt ist, fällt der vierte Punkt außerhalb des Bereichs der zweiten oberen und unteren Grenzen auf die Liniensegmentrichtung. Somit kann der vierte Punkt nicht dem Liniensegment hinzugefügt werden. Das Verfolgen des Liniensegments ist an dem dritten Punkt beendet und die Stelle des vierten wird als die mögliche Startstelle eines neuen Liniensegments gespeichert.
Es ist beachtenswert, daß sowohl der erste Teil der Erfindung (Randerfassung) als auch der zweite Teil (Liniensegmentausbildung) auf jeder Abtastzeile vor einem Fortschreiten zu nachfolgenden Abtastzeilen durchgeführt werden kann. Als Ergebnis ist lediglich ein Durchlauf durch die vertikalen Abtastzeilen und ein Durchlauf durch die horizontalen Abtastzeilen notwendig. Da desweiteren die vertikalen und horizontalen Abtastverfahren vollkommen entkoppelt sind, könnten die zwei Durchläufe durch die Daten gleichzeitig, zum Beispiel mit einer Parallelverarbeitungsarchitektur, durchgeführt werden. In solchen Fällen müssen die normalen Schritte, die für parallele Algorithmen notwendig sind, aufgrund der Tatsache nicht durchgeführt werden, daß die vertikalen und horizontalen Abtastungen inhärent trennbar sind. Diese Merkmale tragen zu der erhöhten Geschwindigkeit einer Verarbeitung der vorliegenden Erfindung bei.
Es gibt viele Weisen, die jeweiligen Rollen der vertikalen und horizontalen Abtastzeilen zu trennen, um einen Redundanz zu vermeiden und die Geschwindigkeit und Genauigkeit der Erfindung weiter zu erhöhen. In dieser Hinsicht ist es anzumerken, daß sowohl vertikale als auch horizontale Abtastungen wünschenswert sind, aber beide nicht absolut notwendig sind. Eine nützliche Liniensegmentinformation kann aus jedem Satz von Abtastungen abgeleitet werden. Jedoch ist es wünschenswert, beide zu haben, da eine vertikale Zeilenabtastung keine vertikale Bildzeile verarbeiten kann und eine horizontale Abtastung keine horizontale Bildzeile handhaben kann. Folglich ist es bevorzugt, daß die Rollen der vertikalen und horizontalen Abtastungen so geteilt werden, daß jede ihr entsprechendes "Einflußgebiet" aufweist. Zum Beispiel kann jeder Satz von Abtastungen Liniensegmente handhaben, die einen Bereich von plus oder minus 45º aufweisen. Insbesondere können horizontale Abtastungen Liniensegmente in einer vertikalen Richtung und 45º auf jeder Seite einer Vertikalen handhaben; vertikale Abtastungen können Liniensegemente entlang einer horizontalen Richtung und ebenso 45º auf jeder Seite einer Horizontalen handhaben. Als Ergebnis wird die Verarbeitung keine Liniensegmente außerhalb des zulässigen Bereichs verfolgen, auch wenn sie in der Lage sein würde, dies zu tun.
Eine zweitrangige Betrachtung ist, daß es bei genau 45º 25 einige Zweideutigkeiten gibt und die Möglichkeit besteht, daß beide Sätze von Abtastungen das Liniensegment von 45º als dem anderen Satz von Abtastzeilen zugehörig ignorieren würden. Folglich ist es bevorzugt, auch mit dem Risiko eines zufälligen doppelten Zählens einer Linie, daß sich die horizontalen und vertikalen Zuständigkeiten leicht überlappen.
Es ist zu erkennen, daß die erzeugten Daten aus Koordinaten von Liniensegmentpunkten von vertikalen und horizontalen Abtastungen bestehen werden. Diese können unabhängig oder kombiniert verwendet werden. Die Liniensegmentdaten können zur visuellen Untersuchung aufgetragen werden oder sie können direkt in einer nachfolgenden Bildanalyse einer mittleren oder oberen Stufe verwendet werden.
Es wird nun Bezug auf FIG. 5 genommen, in der eine vereinfachte Darstellung eines Bildverarbeitungssystems 22 gemäß einem Ausführungsbeispiel der vorliegenden Erfindung gezeigt ist. Ein Sensor 24, welcher eine CCD-Matrix sein kann, empfängt Signale sich ändernder Intensität von einem Bild. Der Sensor wandelt das Ursprungssignal in ein elektrisches Signal, welches zu einem Präprozessor 26 gesendet wird. Dieser Präprozessor 26 kann solche Funktionen, wie zum Beispiel ein Bildfangen und -digitalisieren, durchführen. Das digitalisierte Bild wird dann zu einem Prozessor 28 gesendet, welcher eine EA-Einheit 30, eine CPU 32 und einen Speicher 34 aufweist. Wenn die Bilddaten einmal empfangen und in dem Speicher 34 gespeichert sind, kann der Prozessor 28 dann die notwendigen Berechnungen an den Daten durchführen, um die Rand- und Linienstellen unter Verwendung der vorhergehend dargelegten Verfahren zu erzielen. Schließlich können die Koordinatenstellen des Randes und der Liniensegmente von dem Prozessor 28 zu einer Anzeigeeinheit 36 gesendet werden, bei der sie in der erwünschten Weise verwendet werden.
Es ist zu erkennen, daß die vorliegende Erfindung sehr zugänglich gegenüber Hardwareausführungen ist. Wie es vorhergehend erwähnt worden ist, macht die entkoppelte Art der vertikalen und horizontalen Abtastungen ein Parallelisieren der zwei Aufgaben sehr einfach. Da ebenso die Verarbeitung als ein Problem eines eindimensionalen Signals angenähert wird, könnte sie ebenso einfach von einem Fließbandprozessor mit digitalen Signalverarbeitungschips gehandhabt werden. Als Ergebnis kann eine bekannte einfach verfügbare billige Hardware verwendet werden, um die vorliegende Erfindung auszuführen.
Vorbereitende Tests sind unter Verwendung von Bildern, die von 512 x 512 Bildelementen bis zu 200 x 200 Bildelementen im Quadrat reichen, ausgeführt worden. Jedes Bildelement der Bilder wies eine Intensität auf, die von 0 bis 255 Einheiten reicht. Die Bilder beinhalten sowohl sichtbare als auch infrarote Daten. Testbildszenen beinhalteten ein stark ungeordnetes Bild mit Merkmalen, die 2 bis 3 Bildelemente entfernt sind; Merkmale eines sehr niedrigen und sehr hohen Kontrasts mit Intensitätsänderungen, die von 6 bis zu 130 Einheiten reichen; gemischte Merkmalsauflösungen mit Merkmalsgrenzen, die von 4 scharfen Bildelementen bis zu 25 verschwommenen Bildelementen reichen; und kleine und große Merkmale, die von unter 4 Bildelementen entlang der größten Ausdehnung bis zu über 300 Bildelementen ent lang der größten Ausdehnung reichen. Sowohl zeitliche Tests als auch Linienqualitätstests wurden an der Erfindung durchgeführt, welche auf einem Computer Microvax II ausgeführt worden ist. Die Erfindung benötigte 60 Sekunden, um Ränder aus einem Bild 512 x 512 einer Getränkedose zu extrahieren und weitere 30 Sekunden, um die geraden Liniensegmente zu erzielen. Durch Vergleich benötigte ein Randextrahierungsalgorithmus (der Nevatia-Babu-Algorithmus) im Stand der Technik 24 Minuten, um Ränder des gleichen Testbildes der Getränkedose zu extrahieren. Die Erfindung wurde so gezeigt, daß sie verschwommene Linien sehr gut handhabt. Ein Vergleich mit anderen Algorithmen im Stand der Technik hat gezeigt, daß sie schlechterdings in ihrer Fähigkeit versagen, verschwommene Linien handzuhaben.

Claims

1. Vorrichtung zum Verstärken eines Bildes, das Merkmale enthält, wobei das Bild durch Bildelementdaten dargestellt ist, die Bildelementdaten sowohl von Merkmalen als auch von Nichtmerkmalen beinhalten, wobei die Verstärkung ohne vorhergehende Kenntnis der Merkmale erzeugt wird, wobei die Vorrichtung aufweist:

eine Sensoreinheit (24), die Lichtenergie von diskreten Bildelementen in dem Bild in elektrische Signale wandelt, wobei die Bildelemente definierte Stellen in der X-Y-Ebene aufweisen;

eine Präprozessoreinheit (26), die die Signale digitalisiert;

eine Einrichtung (28), die Krümmungsextrema als solche Punkte auf einer Abtastzeile identifiziert, an denen die Intensität relativ große Änderungen bezüglich vorhergehenden und nachfolgenden Bildelementen erfährt;

eine Einrichtung (28), die die Differenz der Intensität zwischen Paaren von Krümmungsextrema mißt und solche Paare von Krümmungsextrema identifiziert, für welche die Differenz einen vorbestimmten Schwellwert überschreitet;

eine Einrichtung (28), die einzelne Randpunkte als einen Punkt entlang der Abtastzeile zwischen den identifizierten Paaren für Krümmungsextrema identifiziert,

eine Einrichtung (28), die Randpunkte entlang benach barten Abtastzeilen identifiziert, wobei erste und zweite Randpunkte auf ersten und zweiten benachbarten Abtastzeilen liegen;

eine Einrichtung (28), die ein Liniensegment zwischen dem ersten Randpunkt und dem zweiten Randpunkt extrapoliert, wenn die Bildelementstellendifferenz zwischen dem ersten Randpunkt auf der ersten Abtastzeile und dem zweiten Randpunkt auf der zweiten Abtastzeile weniger als n Bildelemente beträgt, wobei n eine Ganzzahl ist;

eine Einrichtung (28), die durch ein Extrapolieren einer Linie von dem ersten Randpunkt zu einem Punkt, der X Bildelemente größer als der zweite Punkt ist, wobei X eine Ganzzahl ist, und durch ein Extrapolieren einer Linie von dem ersten Randpunkt zu einem Punkt, der X Bildelemente kleiner als der zweite Punkt ist, obere und untere Linienrichtungsgrenzen berechnet;

eine Einrichtung (28), die ein neues Liniensegment zwischen dem ersten Randpunkt und einem dritten Randpunkt auf einer benachbarten dritten Abtastzeile extrapoliert, wenn dieser dritte Randpunkt innerhalb der oberen und unteren Linienrichtungsgrenzen liegt; und

eine Anzeigeeinheit (36), die ein verstärktes Bild erzeugt, das lediglich die identifizierten Randpunkte und Liniensegmente enthält, bei der das verstärkte Bild vorwiegend Randpunkte und Linien enthält, die die Merkmale darstellen, und relativ frei von Bildelementen von Nichtmerkmalen ist.

2. Vorrichtung nach Anspruch 1, bei der die Abtastzeilen sowohl vertikale als auch horizontale Abtastzeilen sind.

3. Vorrichtung nach Anspruch 1 oder 2, die desweiteren eine Einrichtung (28), die die Krümmungsextrema für jeden Punkt mit einem zweiten vorbestimmten Schwellwert vergleicht, der proportional zu der Steigungskrümmung für diesen Punkt ist, und eine Einrichtung aufweist, die solche Krümmungsextrema, welche den zweiten Schwellwert überschreiten, ignoriert, wodurch Rauschen in den Bildelementdaten ignoriert wird.

4. Vorrichtung nach Anspruch 1, 2 oder 3, die desweiteren eine Einrichtung (26) aufweist, die die mittlere Intensitätsänderung pro Bildelement zwischen benachbarten Krümmungsextrema vergleicht und diesen Wert mit einem dritten Schwellwert vergleicht, bei der, wenn dieser dritte Schwellwert nicht überschritten wird, kein Randpunkt zwischen diesen Krümmungsextrema identifiziert wird.

5. Vorrichtung nach einem der vorhergehenden Ansprüche, die eine Speichereinheit (34), die die digitalisierten Signale speichert, und eine an die Speichereinheit gekoppelte Einrichtung (32) aufweist, die die Intensität der Signale an diskreten Bildelementen entlang einer Mehrzahl von Abtastzeilen durch das Bild hindurch erfaßt und mißt, wobei die Intensitätswerte eine Intensitätskurve entlang der Abtastzeilen erzeugen.

6. Vorrichtung nach einem der vorhergehenden Ansprüche, die eine Einrichtung (28), die den Wert des elektrischen Signals für jedes Bildelement jeder definierten Stelle zuweist, und eine Einrichtung (28) aufweist, die eine lineare Abtastzeile der Bildelemente in der X-Y- Ebene auswählt.

7. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Einrichtung (24), die die Lichtenergie wandelt, ein CCD-Bildsensor ist.

8. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Präprozessoreinheit (26) ein Bildfangpräprozessor ist.

9. Verfahren zum Verstärken eines Bildes, das Merkmale enthält, wobei das Bild durch Bildelementdaten dargestellt ist, die Bildelementdaten sowohl von Merkmalen als auch von Nichtmerkmalen beinhalten, wobei die Verstärkung ohne vorhergehende Kenntnis der Merkmale erzeugt wird, wobei das Verfahren die folgenden Schritte aufweist;

a) Wandeln von Lichtenergie von einem Bild in elektrische Signale, die der Intensität der Lichtenergie in diskreten Bildelementen in dem Bild entsprechen, wobei die Bildelemente alle eine definierte Stelle in der X-Y- Ebene aufweisen;

b) Identifizieren von Krümmungsextrema in einer Abtastzeile durch Bestimmen solcher Bildelemente, für welche sich die Werte des elektrischen Signals bezüglich den Werten für benachbarte Bildelemente entlang der Abtastzeile am schnellsten ändern;

c) Messen der Differenz des Betrags des Werts des elektrischen Signals zwischen allen Paaren von Krümmungsextrema entlang der Abtastzeile;

d) Bestimmen ausgewählter Paare von Krümmungsextrema, für welche die Differenz einen vorbestimmten Schwellwert überschreitet;

e) Identifizieren eines Bildelements entlang der Abtastzeile, das einen Wert des elektrischen Signals zwischen dem Wert für das identifizierte Paar aufweist, als einen Randpunkt, wobei das Bildelement zwischen dem identifizierten Paar entlang der Abtastzeile liegt; und Anzeigen der X-Y-Stelle des Randpunktes;

f) Identifizieren von Randpunkten entlang benachbarter Abtastzeilen, wobei erste und zweite Randpunkte entlang erster und zweiter benachbarter Abtastzeilen liegen;

g) Extrapolieren eines Liniensegments zwischen dem ersten Randpunkt und dem zweiten Punkt, wenn die Bildelementstellendifferenz zwischen dem ersten Randpunkt auf der ersten Abtastzeile und dem zweiten Randpunkt auf der zweiten Abtastzeile weniger als n Bildelemente beträgt, wobei n eine Ganzzahl ist;

h) Berechnen oberer und unterer Linienrichtungsgrenzen durch ein Extrapolieren einer Linie von dem ersten Randpunkt zu einem Punkt, der X Bildelemente größer als der zweite Punkt ist, wobei X eine Ganzzahl ist, und durch ein Extrapolieren einer Linie von dem ersten Randpunkt zu einem Punkt, der X Bildelemente kleiner als der zweite Punkte ist; und

i) Extrapolieren eines neuen Liniensegments zwischen dem ersten Randpunkt und einem dritten Randpunkt auf einer benachbarten dritten Abtastzeile, wenn dieser dritte Randpunkt innerhalb der oberen und unteren Linienrichtungsgrenzen liegt.

10. Verfahren nach Anspruch 9, bei dem der Schritt eines Wandelns von Lichtenergie desweiteren den Schritt eines Vorsehens eines CCD-Sensors (24) aufweist, der die Lichtenergie wandelt.

11. Verfahren nach Anspruch 9 oder 10, das desweiteren die Schritte eines Digitalisierens des elektrischen Signals in ein digitales Signal für jeden Bildelementwert aufweist.

12. Verfahren nach Anspruch 11, das desweiteren den Schritt eines Sendens der digitalisierten Signale zu einem programmierbaren Prozessor (26) und eines Speicherns der Intensitätswerte in Speicherstellen aufweist, die den Bildelementkoordinaten in dem Bild entsprechen.

13. Verfahren nach einem der Ansprüche 9 bis 12, bei dem der Schritt b) desweiteren den Schritt eines Bestimmens jener Punkte aufweist, an denen die Ableitung der Intensitätskurve einen zweiten Schwellwert überschreitet.

14. Verfahren nach einem der Ansprüche 9 bis 13, bei dem der Schritt e) desweiteren den Schritt eines Bestimmens des Punktes aufweist, der einen Intensitätswert aufweist, der gleich der mittleren Intensität des identifizierten Paares von Krümmungsextrema ist.

15. Verfahren nach einem der Ansprüche 9 bis 14, das desweiteren einen Schritt (j) eines Berechnens einer neuen oberen oder unteren Linienrichtungsgrenze durch ein Extrapolieren einer Linie von dem ersten Punkt zu einem Punkt, der X Bildelemente größer als der dritte Randpunkt ist, und durch ein Extrapolieren einer Linie von dem ersten Punkt zu einem Punkt, der X Bildelemente kleiner als der dritte Randpunkt ist, und eines Verwendens lediglich jener Richtungsgrenzen aufweist, welche einen schmäleren Bereich von Linienrichtungsgrenzen erzeugen.

16. Verfahren nach Anspruch 15, das desweiteren die folgenden Schritte aufweist:

(k) Wiederholen der Schritte (g) - (j) für einen vierten und alle nachfolgenden Randpunkte in jeder nachfolgenden Abtastzeile, bis kein Randpunkt innerhalb der momentanen oberen und unteren Richtungsgrenzen festgestellt wird; und

(1) Wiederholen der Schritte (f) - (k) für Randpunkte, die außerhalb von oberen und unteren Grenzen fallen, um neue Liniensegmente zu erzeugen.