Die Erfindung betrifft ein Verfahren und eine Vorrichtung zum Zusam- menfügen von mehreren digitalen Einzelbildern zu einem Gesamtbild.

Endoskop Systeme werden zum Inspizieren schwer zugänglicher Hohlräume im industriellen und medizinischen Bereich eingesetzt. Das eingeschränkte Blickfeld von Endoskop Systemen erschwert die Orientierung sowie die Koordination beim Inspizieren der Hohlräume, wodurch der gesamte Inspiziervorgang deutlich komplexer und zeitaufwändiger wird. Um das Blickfeld von Endoskop Systemen zu erweitern, wurden Verfahren entwickelt, die aus einer Folge von endoskopisch aufgenommenen, digitalen Einzelbildern ein Gesamtbild erzeugen. Das Zusammenfügen wird auch als Stitching oder Mosaicking bezeichnet. Durch das zusammengefügte Gesamtbild, das auch als Bildmosaik bezeichnet wird, wird das Blickfeld des Endoskopsystems künstlich erweitert.

Aus dem Fachartikel„Real-Time Image Mosaic for Endoscopic Video Se- quences" von Konen et al., veröffentlicht in„Bildverarbeitung für die Medizin", 2007, ist ein echtzeitfähiges Verfahren zum Zusammenfügen von endoskopisch aufgenommenen Einzelbildern zu einem Bildmosaik bekannt, das auf einer Berechnung des optischen Flusses basiert. Als optischer Fluss wird ein Vektorfeld bezeichnet, das zwischen je zwei Einzel- bildern für jedes Pixel die Bewegungsrichtung und -geschwindigkeit angibt. Hierbei wird angenommen, dass sich zwischen den Einzelbildern die Pixelwerte nicht verändern, sondern lediglich verschieben. Nachteilig bei diesem Verfahren ist, dass die Berechnung des optischen Flusses aufwändig ist. Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren zum Zusammenfügen von mehreren digitalen Einzelbildern zu einem Gesamtbild zu schaffen, das schnell, insbesondere echtzeitfähig, und genau ist.

Diese Aufgabe wird durch ein Verfahren mit den Merkmalen des Anspruchs 1 gelöst. Das erfindungsgemäße Verfahren basiert auf einem merkmalsbasierten Algorithmus, mit dem in dem ersten Einzelbild mehrere Merkmale bestimmt und diese Merkmale in dem zweiten Einzelbild erneut bestimmt bzw. verfolgt werden. Das Verfolgen der in dem ersten Einzelbild bestimmten Merkmale wird auch als Tracking bezeichnet. Als merkmalsbasierter Algorithmus können beispielsweise der KLT-Algorithmus, der Harris-Corner-Detektor, der Monotonie-Operator, der SIFT- Algorithmus (Scale Invariant Feature Transform) oder der SURF- Algorithmus (Speeded Up Robust Features) dienen.

Aus den bestimmten und verfolgten Merkmalen wird eine Transformationsmatrix berechnet, die zum Zusammenfügen der Einzelbilder zu dem Gesamtbild dient. Die Transformationsmatrix weist mindestens sechs Frei- heitsgrade auf und ist beispielsweise eine affine Transformationsmatrix mit genau sechs Freiheitsgraden oder eine projektive Transformationsmatrix mit genau acht Freiheitsgraden. Aus der Menge der bestimmten Merkmalskorrespondenzen, also den ersten und zugehörigen zweiten Merkmalskoordinaten zu den Merkmalen M ₁ bis M _n wird die Transformationsmatrix be- rechnet, die die beiden Einzelbilder ineinander überführt. Die Gesamtmenge der Merkmalskorrespondenzen wird mit

A = {{ _P :y _ι ),{pi _P ^b ₂ ),...,{p:y _n )} o) bezeichnet, wobei

P: die ersten Merkmalskoordinaten des Merkmals M _n und

_P : die zugehörigen zweiten Merkmalskoordinaten des

Merkmals M _n sind.

Wenn die zu Grunde liegende Transformation die perspektivische Transformation ist, gilt

P ^a = H _b , _a p ^b (2) wobei H b,a eine Transformationsmatrix mit acht Freiheitsgraden ist, die die Punkte p ^a = (x ^a , y ^a , l) ^τ und p ^b = (x ^b , y ^b , l) ^τ miteinander verbindet.

Ausschreiben der Elemente der Matrix H ergibt

und die Koordinaten berechnen sich als - A - und

Einfaches Umformen dieser Gleichungen führt zu hi ix ^b + h ₁₂ y ^b + h ₁₃ - h ₃ ixV - h ₃₂ y ^b x ^a - h ₃₃ x ^a = 0 (6) und h _2i x ^b + h ₂₂ y ^b + h ₂₃ - h ₃₁ x ^b y ^a - h ₃₂ y ^b y ^a - h ₃₃ y ^a = 0 (7)

Jede Merkmalskorrespondenz liefert zwei homogene Gleichungen dieser Art, um die neun Parameter H ₁₁ ... h ₃₃ zu bestimmen. Allerdings ist die Mat- rix H _b>a nur bis auf einen beliebigen Skalierungsfaktor eindeutig definiert, weshalb sie acht Freiheitsgrade besitzt. Wenn die homogenen Gleichungen durch das Element h ₃₃ geteilt werden, bleiben acht Unbekannte, da sich dieses Element herauskürzt. Aus diesem Grund ist eine Menge von vier Merkmalskorrespondenzen ausreichend, um die Transformationsmatrix zwischen zwei Einzelbildern zu bestimmen.

Die Berechnung der Transformationsmatrix kann mittels einer Singulär- wertzerlegung durchgeführt werden. Aus den Vektoren h = (h _π , h ₁₂ , h ₁₃ , h ₂₁ , h ₂₂ , h ₂₃ , h ₃₁ , h ₃₂ , h ₃₃ ) ^τ (8)

(X ₁ = (jcf ,y ^b , 1,0,0,0 -xχ ^b -yχ ^b -x _t ^a ) ^τ (9) P ₁ = (O ₉ O ₉ O ₉ Xf ₉ Yf , l. -xfy.Vy bf _y_. aV ,y _τ ,a" \)1 (10) können die homogenen Gleichungen als α^h = 0 (H) geschrieben werden. Aus den n Merkmalskorrespondenzen mit n > 4 kann nun die Systemmatrix Q für die Singulärwertzerlegung konstruiert werden

und die homogenen Gleichungen aus Gleichung (11) lassen sich schreiben als

Q h = O (14)

Die Lösung dieses Gleichungssystems ist der Nullraum von Q. Die Lösung ist eindeutig, wenn in der Menge vier oder mehr Merkmalskorresponden- zen enthalten sind, die nicht kolinear sind. Existieren mehr als vier solcher Korrespondenzen, kann ebenfalls an Hand der Singulärwertzerlegimg die Lösung mit den kleinsten Fehlerquadraten berechnet werden. Die Singu- lärwertzerlegung faktorisiert Q in drei Matrizen Q = U J V . Die Diago- nalmatrix∑ enthält die absteigend sortierten Singulärwerte σi ... σ ₉ . Im Fall einer perfekten Lösung gilt σ _{9 =} 0 und G ₁ ≠ 0 für 1 < i < 8. Im Fall eines überbestimmten Gleichungssystems gilt σ ₉ ~ 0. In beiden Fällen ist der korrespondierende letzte Spaltenvektor von V der Lösungsvektor. Dieser Vektor enthält neun Elemente, die die gesuchte Transformationsmatrix erge- ben, wenn diese zeilenweise mit den Elementen aufgefüllt wird.

Für das affine Transformationsmodell kann auf entsprechende Weise die Transformationsmatrix bestimmt werden. Da diese Transformationsmatrix nur sechs Freiheitsgrade hat, reicht hier eine Menge von mindestens drei nicht kolinearen Merkmalskorrespondenzen. Es gilt σ$ = 0 und σ ₉ = 0 und die korrespondierenden rechtssingulären Vektoren sind die achten bzw. neunten Einheitsvektoren. Im Fall einer perfekten Lösung gilt σ ₇ = 0 und im Fall einer Lösung mit geringsten Fehlerquadraten σ ₇ ~ 0. Die Lösung ist hier der siebte Spaltenvektor aus V.

Da der merkmalsbasierte Algorithmus aufgrund seiner Einfachheit, insbesondere bei endoskopisch aufgenommenen Einzelbildern, aufgrund deren schlechter Bildqualität, zu Fehlzuordnungen bei den Merkmalskorrespondenzen, also zu falsch verfolgten Merkmalen, führt, ist eine robuste Be- rechnung der Transformationsmatrix erforderlich. Hierzu wird der sogenannte RANSAC-Algorithmus (RANdom SAmple Consensus) verwendet, mit dem falsch zugeordnete Merkmalskorrespondenzen bei der Berechnung der Transformationsmatrix unberücksichtigt bleiben. Zunächst wird anhand einer ersten Teilmenge, beispielsweise einer minimalen Teilmenge von erforderlichen Merkmalskorrespondenzen, eine Test- Transformationsmatrix berechnet. Für diese Test-Transformationsmatrix wird nun ein Gütewert, der sogenannte Support, bestimmt. Das bedeutet, es wird ermittelt, ob die Test-Transformationsmatrix für eine zweite Teilmen- ge der Merkmale, beispielsweise für die restlichen Merkmale, einem vorgegebenen Gütekriterium genügt. Es wird beispielsweise ermittelt, welche Anzahl der Merkmale der zweiten Teilmenge dem Gütekriterium genügt. Die dem Gütekriterium genügenden Merkmale werden als sogenannte In- lier bezeichnet, die anderen Merkmale werden entsprechend als Outlier bezeichnet. Für eine Test-Transformationsmatrix wird eine Merkmalskorrespondenz beispielsweise als Inlier klassifiziert, wenn gilt

|p; - hpf | <;, (15) wobei ||...| den euklidischen Abstand bezeichnet.

Dieser Vorgang wird solange wiederholt, bis eine Test- Transformationsmatrix mit einem ausreichend hohen Support gefunden oder eine maximale Anzahl an Iterationen durchlaufen wurde. Die endgültige Transformationsmatrix ist dann beispielsweise die beste Test- Transformationsmatrix. Alternativ kann aus den zu der besten Test- Transformationsmatrix vorliegenden Inliern die Transformationsmatrix berechnet werden.

Der merkmalsbasierte Algorithmus ermöglicht somit die Erstellung endo- skopischer Bildmosaike bzw. eines endoskopischen Gesamtbilds aus Einzelbildern, wobei durch den RANSAC-Algorithmus eine Ausreißer- Erkennung für falsch verfolgte bzw. getrackte Merkmale bereitgestellt wird. Das erfindungsgemäße Verfahren gewährleistet somit aufgrund des merkmalsbasierten Algorithmus ein schnelles und aufgrund des RANSAC- Algorithmus ein genaues Zusammenfügen der Einzelbilder, auch wenn diese nur eine geringe Bildqualität aufweisen, wie dies bei endoskopisch aufgenommenen Einzelbildern der Fall ist. Das erfindungsgemäße Verfah- ren ist insbesondere echtzeitfähig, wobei unter Echtzeitfähigkeit mindestens zehn zusammengefügte Einzelbilder pro Sekunde bei Verwendung eines handelsüblichen PC verstanden wird.

Ein Verfahren nach Anspruch 2 ermöglicht ein Bestimmen der Merkmals- koordinaten bei verhältnismäßig großen Verschiebungen zwischen den Einzelbildern. Ausgehend von einer niedrigsten Auflösungsstufe wird ein Merkmal, beispielsweise subpixelgenau, lokalisiert und verfolgt. Das Ergebnis wird in die nächste Auslösungsstufe projiziert, wo das Merkmal erneut bestimmt und verfolgt wird. Die Verschiebungen in Pixeln sind so- mit pro Auflösungsstufe auf ein bestimmtes Maß begrenzt.

Ein Verfahren nach Anspruch 3 bietet einen guten Kompromiss zwischen Schnelligkeit und Genauigkeit. Bei diesem merkmalsbasierten Algorithmus, der auch als KLT-Algorithmus bezeichnet wird, ist das Bestimmen und Verfolgen der Merkmale optimal aufeinander abgestimmt, da ein Pixelfenster bzw. Merkmalsfenster nur dann als Merkmal charakterisiert wird, wenn das für das Verfolgen des Merkmals zu lösende lineare Gleichungssystem stabil lösbar ist. Hierzu wird aus den Gradienten zu den Pixeln des Pixelfensters in dem ersten Einzelbild eine Matrix gebildet und deren Eigenwerte berechnet. Die Matrix hat den Rang 2. Sofern beide Eigenwerte einen vordefinierten Schwellwert überschreiten, wird das Pixelfenster als Merkmal charakterisiert, dem erste Merkmalskoordinaten zugeordnet werden. Da die Merkmale auch als Merkmalspunkte bezeichnet werden, werden die Merkmalskoordinaten auch entsprechend als Punktko- ordinaten bezeichnet. Diese Merkmalskoordinaten können die Pixelkoordinaten eines der im Pixelfenster liegenden Pixels sein. Die Matrix wird anschließend zum Verfolgen bzw. zum Bestimmen des Merkmals in dem zweiten Einzelbild verwendet. Hierzu wird aus der Matrix und einem Feh- lervektor ein Verschiebungsvektor durch Lösen eines linearen Gleichungssystems berechnet. Der Verschiebungsvektor beschreibt die Verschiebung des Pixelfensters bzw. Merkmals in dem zweiten Einzelbild und gilt für alle Pixel des Pixelfensters. Der merkmalsbasierte Algorithmus ist in dem Fachartikel„Detection and Tracking of Point Features" von Carlo Tomasi und Takeo Kanade (Technical Report CMU-CS-91-132, Carnegie Mellon University, 1991) im Detail beschrieben, auf den hiermit verwiesen wird. Der Algorithmus ist auch als KLT (Kanade-Lukas-Tomasi)-Tracking- Algorithmus oder als KLT- Tracker bzw. KLT -Algorithmus bekannt. Der KLT-Algorithmus basiert auf dem linearen Gleichungssystem

G - d = e (16) wobei

G eine symmetrische Matrix mit Rang 2,

d ein Verschiebungsvektor (dx, dy) und

e ein Fehlervektor ist.

Für jeweils zwei aufeinander folgende Einzelbilder I (nachfolgend auch I _a ) und J (nachfolgend auch I _b ) kann die Matrix G durch Ermittlung der Gradienten g aus dem ersten Einzelbild wie folgt berechnet werden: wobei g ein Gradientenvektor zu einem Pixel des Pixelfensters

W,

w eine Gewichtungsfunktion zur Gewichtung der Pixel des Pixelfensters W und

dA = dx ^• dy das Integrationsdifferenzial des Doppelintegrals ist.

Der zweidimensionale Fehlervektor e wird aus den berechneten Gradienten g und den Differenzen der Pixelwerte der Einzelbilder im Pixelfenster W wie folgt berechnet: e = J (/(x) - J(x))• gwdA ( 18)

wobei

I(x) der Pixelwert des ersten Einzelbilds im Pixel x, J(x) der Pixelwert des zweiten Einzelbilds im Pixel x, g der Gradientenvektor zu einem Pixel des Pixelfensters

W,

w eine Gewichtungsfunktion zur Gewichtung der Pixel des Pixelfensters W und

dA = dx ^• dy das Integrationsdifferenzial des Doppelintegrals ist. Für diskrete Pixel sind die Doppelintegrale in den Gleichungen (16) bis (18) durch Doppelsummen in der x- und y-Richtung der Bildebene zu ersetzen. Bei der Berechnung der Eigenwerte deuten zwei kleine Eigenwerte auf homogene Bildbereiche hin, während ein großer und ein kleiner Eigenwert für unidirektionale Merkmale, wie beispielsweise Kanten, stehen. Zwei große Eigenwerte deuten auf Ecken oder hochfrequente Texturen hin, welche gut zu verfolgende Merkmale sind. Da der größere Eigenwert nach oben durch die maximalen Pixelwerte bzw. Intensitätswerte begrenzt ist, ist es ausreichend, dass der kleinere der beiden Eigenwerte über einem bestimmten Schwellwert liegt. Folglich wird bei der Merkmalsauswahl ein Pixelfenster dann akzeptiert, wenn für deren Eigenwerte X ₁ und X ₂ gilt, dass wobei λ _t ein vordefinierter Schwellwert ist.

Ein Verfahren nach Anspruch 4 erhöht die Genauigkeit bei der Berechnung der Verschiebungsvektoren. Bei der Lösung des linearen Gleichungssystems (16) wird der Verschiebungsvektor d(i) einen Restfehler aufweisen, da die Taylor- Approximation durch den linearen Term, also durch den Gradientenvektor g, nur dann eine präzise Lösung darstellt, wenn die Pixelwerte linear von x und y abhängen. Dies ist vor allem in Pixelbereichen mit hohen Frequenzen, die sich gut zum Verfolgen bzw. Tracken eignen, nicht der Fall. Die näherungsweise Lösung für den Verschiebungsvektor d(i) kann jedoch als Ausgangspunkt für weitere Iterationsschritte dienen, in denen das Gleichungssystem (1) erneut gelöst und ein neuer Verschiebungsvektor d(i+l) berechnet wird. Um zu prüfen, ob dies nötig ist, wird zunächst das jeweilige Pixelfenster um den bestimmten Verschiebungsvektor in einem der Einzelbilder verschoben. Da diese Position in der Regel zwischen diskreten Pixelkoordinaten liegt, werden mittels bilinearer Interpolation neue Pixelwerte für das Pixelfenster berechnet und hieraus anschließend der Fehler, also die Summe der quadratischen Differenzen der Pixelwerte bzw. Bildintensitäten, bestimmt. Übersteigt dieser Fehler einen vordefinierten Toleranzwert, werden ausgehend von dem aktuellen Ver- schiebungsvektor d weitere Iterationsschritte durchgeführt, bis der Fehler den Toleranzwert unterschreitet oder eine maximale Anzahl an Iterationsschritten erreicht ist. Typischerweise werden weniger als fünf Iterationsschritte benötigt, um das gesuchte Merkmal präzise zu lokalisieren. Da nach jedem Iterationsschritt durch lineare Interpolation die Pixelwerte bzw. Intensitätswerte neu bestimmt werden, kann der Verschiebungsvektor d mit Subpixelgenauigkeit berechnet werden.

Ein Verfahren nach Anspruch 5 ermöglicht eine Berechnung der Verschiebungsvektoren bei verhältnismäßig großen Verschiebungen zwischen den Einzelbildern. Der merkmalsbasierte Algorithmus ist aufgrund des ihm zugrunde liegenden linearen Ansatzes nur in der Lage, verhältnismäßig kleine Verschiebungen zu bestimmen. Durch einen pyramidenbasierten Ansatz, in dem die Einzelbilder in mehreren Auflösungsstufen j vorliegen, können auch größere Verschiebungen bestimmt werden. Ausgehend von einer niedrigsten Auflösungsstufe wird ein Merkmal, beispielsweise subpi- xelgenau, lokalisiert und die durch den Verschiebungsvektor d(j) errechnete Position auf die nächste Auflösungsstufe projiziert, wo sie als Ausgangspunkt für die weitere Berechnung des Verschiebungsvektors d(j+l) dient. Somit nähert sich der Algorithmus einer exakten Lösung für den Verschiebungsvektor d mit jeder Auflösungsstufe an, wobei die zu bestimmenden Verschiebungen pro Auflösungsstufe ausreichend klein sind. Der Algorithmus ist beispielsweise mit einem vorgebbaren Suchradius r steuerbar, welcher angibt, wie groß die Verschiebungen sein dürfen, die vom Algorithmus zu erkennen sind. Anhand des Suchradius berechnet der Algorithmus automatisch die Anzahl der Auflösungsstufen sowie den Faktor des Subsamplings zwischen zwei Auflösungsstufen. Gleichzeitig wird ein Grenzbereich in x- und y-Richtung definiert, der von dem Algorithmus bei der weiteren Berechnung ignoriert wird. Dies ist darin begründet, dass durch den Gauss-Filter, der auf jeder Auflösungsstufe angewandt wird, Randbereiche entstehen, die Undefiniert sind.

Ein Verfahren nach Anspruch 6 gewährleistet, dass die zu verfolgenden Merkmale möglichst homogen über den Einzelbildern verteilt sind. Hier- durch können Verschiebungen in unterschiedlichste Richtungen einfach verfolgt werden.

Ein Verfahren nach Anspruch 7 gewährleistet eine hohe Bildqualität des Gesamtbilds. Die projektive Transformation wird auch als perspektivische Transformation oder Homografie bezeichnet. Mittels der projektiven

Transformation kann die freie Bewegung eines bildgebenden Sensors über einem flachen Objekt modelliert oder eine beliebige Szene, bei der die Bewegung des bildgebenden Sensors auf die Rotation um seine eigene Achse eingeschränkt ist.

Ein Verfahren nach Anspruch 8 erhöht die numerische Stabilität bei der Berechnung der Transformationsmatrix. Ein Verfahren nach Anspruch 9 gewährleistet eine hohe numerische Stabilität in Verbindung mit einer hohen Bildqualität des Gesamtbilds. Zunächst wird aus den Merkmalen der einzelnen Bilder j jeweils der Schwerpunkt berechnet. Der Schwerpunkt c = (c _x ,c _y ) berechnet sich als

1 "

(20)

Weiterhin kann für jedes Bild j der mittlere Abstand d zum Schwerpunkt berechnet werden:

Ziel ist es, den Koordinatenursprung der berechneten Merkmale aus jedem Einzelbild in den Schwerpunkt zu verschieben und die Merkmale so zu skalieren, dass der Abstand zum Ursprung im Durchschnitt V2 beträgt. Dies geschieht durch Multiplikation mit den Normalisierungsmatrizen N _j , die sich wie folgt berechnen:

An Hand der normalisierten Merkmalskoordinaten p^ wird nun die normalisierte Transformationsmatrix H berechnet, so dass gilt P.≡Hp; (23)

Die nicht-normalisierte Transformationsmatrix H kann nun aus H berechnet werden. Es gilt:

H = N ₃ ^"1 H N _b . (24)

Ein Verfahren nach Anspruch 10 gewährleistet eine robuste und genaue Berechnung der Transformationsmatrix. Durch die abschließende Berechnung der Transformationsmatrix aus allen Inliern der besten Test- Transformationsmatrix wird eine optimale Genauigkeit der Transformationsmatrix erreicht. Ein Verfahren nach Anspruch 11 gewährleistet ein einfaches und effizientes Zusammenfügen der Einzelbilder zu dem Gesamtbild, was insbesondere für die Echtzeitfähigkeit von Bedeutung ist.

Ein Verfahren nach Anspruch 12 gewährleistet eine einfache Visualisie- rung des Gesamtbilds in Echtzeit. Das Gesamtbild ist eine hybride Darstellung aus einem statischen und einem dynamischen Anteil. Der statische Anteil sind zeitlich zurückliegende Einzelbilder, die von dem aktuellen Einzelbild als dynamischen Anteil überlagert sind. Vorzugsweise wird das aktuelle Einzelbild jeweils in der Monitormitte eines Monitors angezeigt. Das Bildmosaik wird somit immer auf die aktuellste Ansicht zentriert. Ein Verfahren nach Anspruch 13 gewährleistet ein schnelles und rechenoptimiertes Zusammenfügen der Einzelbilder. Dies ist insbesondere für das Zusammenfügen in Echtzeit von Bedeutung. Ein Verfahren nach Anspruch 14 gewährleistet ein schnelles und genaues Zusammenfügen zu einem Gesamtbild, auch wenn die Einzelbilder eine schlechte Bildqualität aufweisen. Mit einem Endoskop System aufgenommene Einzelbilder sind durch die eingesetzten Weitwinkellinsen in der Regel verzerrt. Zusätzlich wird die Bildqualität durch die Bewegung des bild- gebenden Sensors sowie durch Glanzlichteffekte beeinträchtigt.

Ein Verfahren nach Anspruch 15 verbessert die Bildqualität des Gesamtbilds. Bildgebende Systeme mit Linsen, insbesondere Weitwinkellinsen, verursachen in den Einzelbildern Verzerrungen. Dies ist auch bei Endo- skopsystemen der Fall. Die Entzerrung erfolgt mittels eines inversen Ver- zerr-Modells. Hinsichtlich der Entzerrung wird auf den Fachartikel„Preci- se Radial Un-distortion of Images" von John Mallon und Paul F. Whelan, veröffentlicht in„Proceedings of 17th International Conference on Pattern Recognition", 2004, verwiesen.

Ein Verfahren nach Anspruch 16 vermeidet das Bestimmen und Verfolgen von falschen Merkmalen. Endoskopisch aufgenommene Einzelbilder weisen regelmäßig einen hohen Anteil an Glanzlicht in Folge der zu inspizierenden glatten und/oder feuchten Oberflächen auf. Glanzlicht entsteht dort, wo das vom Endoskop System ausgestrahlte Licht senkrecht auf die Objektoberfläche auftrifft und von dort reflektiert wird. Da diese Glanzlichter hohe Pixelwerte bzw. Intensitätswerte haben, sind an den Grenzen der Glanzlichter oftmals die stärksten Kontraste zu finden, sodass der merkmalsbasierte Algorithmus hier die vermeintlich besten Merkmale findet. Diese Merkmale gehören jedoch nicht zur Szene, sondern werden bei der Aufnahme der Einzelbilder erzeugt und sind dementsprechend in ihrer Bewegung von der Bewegung des bildgebenden Sensors abhängig. Da sich das Glanzlicht von Einzelbild zu Einzelbild nur geringfügig verändert, können die zugehörigen Merkmale gut verfolgt werden, wobei auch der RANSAC- Algoritmus nicht in der Lage ist, sie ausreichend zu eliminieren. Dies führt letztendlich zu einer schlechten Transformationsmatrix. Da sich Glanzlichter in ihren Pixelwerten deutlich von dem Rest des Einzelbilds abheben, können diese relativ einfach durch einen Schwellwerttest und anschließen- der Erosion erkannt werden. Für jedes Einzelbild werden alle Pixelwerte mit einem Glanzlichtschwellwert verglichen. Die Pixel, deren Pixelwert den Glanzlichtschwellwert überschreiten, werden einer Glanzlichtmaske zugeordnet. Die so entstehende Glanzlichtmaske wird durch Erosion ausgeweitet. Diese entspricht einer morphologischen Dilation mit einem run- den Strukturelement. Anhand der binären Glanzlichtmaske werden Merkmale in deren Bereich ausgeschlossen. Hierzu werden im Bereich der Glanzlichtmaske keine Merkmale bestimmt oder darin bestimmte Merkmale nicht verfolgt bzw. nicht zur Berechnung der Transformationsmatrix herangezogen.

Der Erfindung liegt ferner die Aufgabe zugrunde, eine Vorrichtung zum Zusammenfügen von mehreren digitalen Einzelbildern zu einem Gesamtbild zu schaffen, die schnell, insbesondere echtzeitfähig, und genau ist. Diese Aufgabe wird durch eine Vorrichtung mit den Merkmalen des Anspruchs 17 gelöst. Die Vorteile der erfindungsgemäßen Vorrichtung entsprechen den bereits beschriebenen Vorteilen des erfindungsgemäßen Verfahrens. Insbesondere kann die Vorrichtung auch entsprechend den Ansprüchen 2 bis 16 weitergebildet werden. Eine Vorrichtung nach Anspruch 18 erhöht die Genauigkeit beim Zusammenfügen der Einzelbilder zu dem Gesamtbild, insbesondere wenn die Einzelbilder mittels eines Endoskop Systems aufgenommen sind.

Eine Vorrichtung nach Anspruch 19 erhöht die Genauigkeit beim Zusammenfügen der Einzelbilder, wenn diese Glanzlichter enthalten.

Ein Endoskop System nach Anspruch 20 weist ein virtuell erweitertes Blick- feld auf. Das Endoskop System kann in der Technik zur Analyse und Prüfung von Bauteilen sowie zur Dokumentation von Fehlstellen eingesetzt werden. Darüber hinaus kann das Endoskop System in der Medizin zur Untersuchung von Hohlorganen und zur Dokumentation von Läsionen sowie in der minimalinvasiven Chirurgie eingesetzt werden.

Weitere Merkmale, Vorteile und Einzelheiten der Erfindung ergeben sich aus der nachfolgenden Beschreibung eines Ausführungsbeispiels. Es zeigen: Fig. 1 eine schematische Ansicht eines Endoskop Systems mit einer Vorrichtung zum Zusammenfügen von digitalen Einzelbildern zu einem Gesamtbild,

Fig. 2 eine schematische Ansicht von zwei aufeinanderfolgend aufgenommenen Einzelbildern,

Fig. 3 eine schematische Ansicht eines aus den Einzelbildern in

Fig. 2 zusammengefügten Gesamtbilds, Fig. 4 einen schematischen Ablaufplan des Verfahrens zum Zusammenfügen der Einzelbilder zu dem Gesamtbild, und

Fig. 5 einen schematischen Ablaufplan des merkmalsbasierten

Algorithmus zum Bestimmen und Verfolgen von Merkmalen in den Einzelbildern.

Ein Endoskopsystem 1 weist einen Schaft 2 auf, an dem an einem ersten Ende 3 ein Griff 4 und an einem zweiten Ende 5 ein bildgebendes System 6 angeordnet ist. Der Schaft 2 ist flexibel ausgebildet. Alternativ kann dieser auch starr sein.

Das optische System 6 umfasst eine Strahlungsquelle 7, eine Weitwinkellinse 8 und einen bildgebenden Kamera- Sensor 9. Die Strahlungsquelle 7 sowie der Kamera-Sensor 9 können über den Griff 4 gesteuert werden. Der bildgebende Sensor 9 ist beispielsweise als miniaturisierter Videosensor in Tip-Chip-Technologie ausgebildet.

Die von dem Sensor 9 aufgenommenen Einzelbilder I _a ,I _b werden über eine Signalleitung 10 von dem Sensor 9 zu einer Vorrichtung 11 übertragen, die zum Zusammenfügen der digitalen Einzelbilder I _a ,I _b zu einem Gesamtbild G dient. Die Signalleitung 10 ist beispielsweise als elektrische Bildübertragungsleitung ausgebildet. Die Vorrichtung 11 ist als Personalcomputer ausgebildet, auf dem eine Eingabeeinheit 12, eine Entzerreinheit 13, eine Glanzlichteinheit 14, eine Auswahleinheit 15, eine Verfolgungseinheit 16, eine Transformationseinheit 17 und eine Ausgabeeinheit 18 implementiert sind. Zur Speicherung von Daten weist die Vorrichtung zusätzlich eine Speichereinheit 19 auf. Zur Visualisierung des Gesamtbilds G ist die Vorrichtung 11 an einen Monitor 20 angeschlossen.

Mit dem Kamera-Sensor 9 werden zunächst in einem zeitlichen Abstand Δt ein erstes Einzelbild I _a sowie ein zeitlich nachfolgendes zweites Einzelbild I _b aufgenommen. Zwischen der Aufnahme der Einzelbilder I _a und I _b wurde der Kamera-Sensor 9 verschoben, sodass die vor dem Kamera-Sensor 9 liegende Szene aus unterschiedlichen Positionen aufgenommen wurde. Das Einzelbild I _a wird zunächst im Schritt Si in die Eingabeeinheit 12 eingelesen und anschließend in der Entzerreinheit 13 im Schritt S ₂ mittels eines inversen Verzerr-Modells entzerrt. Das entzerrte Einzelbild I _a wird im Schritt S ₃ in der Speichereinheit 19 abgelegt. Anschließend wird das entzerrte Einzelbild I _a der Glanzlichteinheit 14 übergeben, die im Schritt S ₄ eine Glanzlichtmaske L _a erstellt, die im Schritt S ₅ in der Speichereinheit 19 abgelegt wird. Zum Erstellen der Glanzlichtmaske L _a werden die Pixelwe- ret p _a (x,y) mit einem Glanzlichtschwellwert I ₁ verglichen und diejenigen Pixel der Glanzlichtmaske L _a zugeordnet, deren Pixelwert p _a (x,y) den Glanzlichtschwellwert I ₁ überschreiten. Anschließend wird dieser Pixelbe- reich bzw. diese Pixelbereiche durch morphologische Dilation mit einem runden Strukturelement erweitert und so die Glanzlichtmaske L _a gebildet.

Anschließend wird das Einzelbild I _a im Schritt S ₆ der Auswahleinheit 15 und der Verfolgungseinheit 16 zugeführt, in denen der merkmalsbasierte Algorithmus, beispielsweise der KLT- Algorithmus, implementiert ist. Die genaue Funktionsweise des KLT-Algorithmus wird nachfolgend noch genauer erläutert. Die Auswahleinheit 15 gibt im Schritt S ₇ n Merkmale M ₁ bis M _n aus, die in dem Einzelbild I _a bestimmt wurden. Die Merkmale M ₁ bis M _n sind durch zugehörige Merkmalskoordinaten p " bis p " charakterisiert, die in der

Speichereinheit 19 abgelegt werden. Das Einzelbild I _a wird im Schritt Sg der Ausgabeeinheit 18 zugeführt, mit der dieses im Schritt S ₉ in einer pla- naren Projektionsfläche dargestellt wird. Für das erste Einzelbild I _a erfolgt noch kein Zusammenfügen, da kein weiteres Einzelbild vorliegt. Der Ursprung des ersten Einzelbildes I _a kann in Schritt S ₉ neu festgelegt werden. Hierzu wird aus der Speichereinheit 19 im Schritt S _1O eine Ursprungs- Transformationsmatrix H _a;0 ausgelesen werden. Anschließend wird im

Schritt S ₁₁ zu Schritt S ₁ zurückgegangen, wo das nachfolgende zweite Einzelbild I _b im Schritt S ₁ eingelesen wird. Anschließend werden die Schritte S ₂ bis S ₇ für das Einzelbild I _b wiederholt. Anschließend werden die in dem ersten Einzelbild I _a bestimmten Merkmale M ₁ bis M _n in dem zweiten Einzelbild I _b bestimmt. Dieser Vorgang wird auch als Tracken bzw. Verfolgen bezeichnet. Im Schritt S ₁₂ werden die Merkmale M ₁ bis M _n sowie Parameter für den KLT-Algorithmus, wie beispielsweise einem Suchradius r, aus der Speichereinheit 19 in die Verfol- gungseinheit 16 eingelesen. Die Funktionsweise der Verfolgungseinheit 16 wird nachfolgend noch im Detail beschrieben.

Das Ergebnis des KLT-Algorithmus, das von der Verfolgungseinheit 16 ausgegeben wird, sind Merkmalskorrespondenzen, die für jedes der Merk- male M ₁ bis M _n aus den ersten Merkmalskoordinaten p " bis p " sowie zugehörigen zweiten Merkmalskoordinaten p * bis p * bestehen. Die Merkmalskorrespondenzen sind dementsprechend (p " , pf ) bis (p " , p* ). Die Merkmalskorrespondenzen werden im Schritt S ₁₃ gebildet, wobei im Schritt Si ₄ die Glanzlichtmasken L _a und L _b einfließen, sodass keine Merkmale M zugelassen werden, die innerhalb einer der Glanzlichtmasken L _a oder L _b liegen. Im Schritt Si ₅ wird in der Transformationseinheit 17 die Transformationsmatrix H _{b a} berechnet. Die Berechnung erfolgt entsprechend den Gleichungen (1) bis (24) mittels des RANS AC- Algorithmus, wozu in Schritt S ₁₆ Parameter für den RANSAC-Algorithmus, wie beispielsweise die Größe der ersten Teilmenge Ti und der zweiten Teilmenge T ₂ von Merkmalen M ₁ sowie die Anzahl N der Iterationen eingelesen wird. Für nachfolgende Einzelbilder kann in Schritt Si ₆ zusätzlich noch eine Merkmalshistorie eingelesen werden. Die Merkmalshistorie enthält alle Koordinaten und Werte eines Merkmals über die Zeit und kann von Nutzen sein, wenn Merkmale verloren gehen. Mit der Merkmalshistorie können zusätzliche Merkmals- korrespondenzen zwischen vergangenen Einzelbildern und dem aktuellen Einzelbild generiert werden, um das Gesamtbild bzw. dessen Entstehungs- prozess zu stabilisieren. Die Merkmalskoordinaten des verlorenen Merkmals werden mittels der Transformationsmatrix bzw. über mehrere aufeinanderfolgende Einzelbilder hinweg mittels mehrerer Transformationsmatri- zen weitertransformiert. Dadurch können diese Merkmale in der Liste der Merkmalskorrespondenzen weitergeführt werden.

Zur Berechnung der Transformationsmatrix H _{b a} werden die Merkmalsko- ordinaten zunächst normalisiert und anschließend die Transformationsmatrix H _b>a mittels des RANSAC-Algorithmus berechnet. Hierzu wird aus der Gesamtmenge der Merkmale Mi bis M _n eine erste Teilmenge Ti ausgewählt. Im Falle einer projektiven Transformationsmatrix sind acht Unbekannte zu bestimmen, sodass mindestens vier Merkmalskoordinaten aus- gewählt werden müssen, um die Transformationsmatrix H _b;3 eindeutig zu berechnen. Der RANSAC-Algorithmus führt N-Iterationsschritte durch, wobei in jedem Iterationsschritt eine erste Teilmenge T ₁ zufällig ausgewählt und eine Test-Transformationsmatrix T berechnet wird. Anschlie- ßend wird die berechnete Test-Transformationsmatrix T mit einer zweiten Teilmenge T ₂ von Merkmalen M ₁ überprüft, wobei sich die Teilmengen T ₁ und T ₂ nicht überschneiden. Als Gütewert für die jeweilige Test- Transformationsmatrix T wird die Anzahl Ni der sogenannten Inlier herangezogen. Ein Merkmal M ₁ der zweiten Teilmenge T ₂ ist dann ein Inlier, wenn dieses innerhalb einer vordefinierten Genauigkeit durch das berechnete Test-Transformationsmodell abgebildet werden kann. Hierzu wird mit der Test-Transformationsmatrix T der euklidische Abstand berechnet. Die Test-Transformationsmatrix T mit der höchsten Anzahl Ni an Inliern wird als Ausgangspunkt verwendet, um mit allen als Inlier gekennzeichneten Merkmalen M ₁ der zweiten Teilmenge T ₂ die Transformationsmatrix H _b;3 zu berechnen.

Wird keine Transformationsmatrix gefunden, so wird das Einzelbild I _b im Schritt S ₁₇ verworfen und im Schritt S ₁₁ ein weiteres Einzelbild eingelesen. Liegt kein weiteres Einzelbild vor, so endet das Verfahren im Schritt S ₁₈ . Wird eine Transformationsmatrix H _{b a} gefunden, so wird diese im Schritt S ₁₉ an die Ausgabeeinheit 18 übergeben, in der die Einzelbilder I _a und I _b zu dem Gesamtbild G zusammengefügt werden. Das Gesamtbild G wird durch den Monitor 20 visualisiert, wobei vorzugsweise das aktuelle Ein- zelbild I _b dem bzw. den vorangehenden Einzelbildern I _a überlagert wird. Das aktuellste Einzelbild I _b wird vorzugsweise mittig auf dem Monitor 20 dargestellt. Die Transformationsmatrix H _{b a} wird im Schritt S ₂₀ in der Speichereinheit 19 abgelegt. Liegt kein weiteres Einzelbild vor, endet das Verfahren im Schritt S ₁₈ . Nachfolgend wird unter Bezugnahme auf Fig. 5 die Funktionsweise der Auswahleinheit 15 und der Verfolgungseinheit 16 genauer beschrieben. Im Schritt S ₆ wird das Einzelbild I _a zunächst eingelesen. Das Einzelbild I _a wird dann im Schritt S ₆₁ mit einem Glättungsfüter geglättet und anschließend im Schritt S ₆₂ eine Auflösungspyramide aus mehreren Auflö sungs stufen j er- stellt. Die Anzahl der Auflö sungs stufen j wird beispielsweise aus einem vorgegebenen Suchradius r berechnet.

Anschließend werden aus dem Einzelbild I _a n Merkmale M ₁ bis M _n entsprechend den Gleichungen (16) bis (19) bestimmt bzw. extrahiert. Die Merkmale M ₁ bis M _n werden in allen Auflösungsstufen j berechnet, damit diese im darauffolgenden Einzelbild I _b auch bei großen Verschiebungen verfolgt werden können. Der Verschiebungsvektor wird zunächst in der niedrigsten Auflösungsstufe bestimmt und anschließend in die nächsthöhere Auflö sungs stufe projiziert. Die Verschiebung in Pixeln kann somit in jeder Auflösungsstufe auf ein gewünschtes Maß begrenzt werden.

Im Schritt S ₆₃ wird ein Pixelfenster W mit einer vordefinierten Breite b in x-Richtung und einer vordefinierten Höhe h in y-Richtung über das Einzelbild I _a verschoben, wobei in jeder bzw. einer Vielzahl von Positionen des Pixelfenster W eine Matrix G entsprechend Gleichung (17) berechnet wird. Die Matrix G ergibt sich aus der Summe der Produkte gg ^τ über alle Pixel des Pixelfensters W, wobei g der Gradientenvektor zu einem bestimmten Pixel des Pixelfensters W ist. In Fig. 2 ist beispielhaft das Pixelfenster W des Merkmals M ₁ mit einem Gradientenvektor g eingezeichnet. Zusätzlich kann eine Gewichtungsfunktion w berücksichtigt werden. Ist dies nicht gewünscht, kann w = 1 gewählt werden. Zu jedem Pixelfenster W werden die Eigenwerte X ₁ und λ ₂ der Matrix G berechnet und anhand von Gleichung (19) entschieden, ob das Pixelfenster W ein Merkmal M charakteri- siert. Zusätzlich muss ein neu hinzukommendes Merkmal M einen Minimalabstand ΔM zu den bereits bestimmten Merkmalen M einhalten. In Schritt S ₆₄ wird eine Speicherung der bestimmten Merkmale M ₁ bis M _n eingeleitet, sodass diese im Schritt S ₇ an die Speichereinheit 19 übermittelt werden. Anschließend wird im Schritt S ₆₅ wieder zu Schritt S ₆₁ zurückge- gangen, wo das zweite Einzelbild I _b eingelesen und geglättet sowie in Schritt S ₆₂ eine Auflösungspyramide hierzu erstellt wird.

Für das Verfolgen bzw. Tracken der Merkmale M ₁ bis M _n in der Verfolgungseinheit 16 werden diese der Reihe nach in Schritt S ₆₆ ausgewählt. Zunächst werden für das erste Merkmal M ₁ die Einzelbilder I _a und I _b in der niedrigsten Auflösungsstufe j = 1 in Schritt S ₆₇ ausgewählt. Anschließend wird für diese Auflösungsstufe das Gleichungssystem (16) gelöst. Die Lösung des Gleichungssystems (16) ist der Verschiebungsvektor d für das erste Merkmal M ₁ . Die Matrix G ist für Schritt S ₆₈ bereits bekannt. Der Fehlervektor e wird in Schritt S ₆₈ nach Gleichung (18) berechnet, wobei das Pixelfenster W in einem ersten Iterationsschritt i = 1 in dem zweiten Einzelbild I _b an einer dem ersten Einzelbild I _a entsprechenden Stelle angenommen wird. Der in dem ersten Iterationsschritt ermittelte Verschiebungsvektor d(i, j) ist noch fehlerbehaftet. Für einen zweiten Iterations- schritt i = 2 wird das Pixelfenster P in dem zweiten Einzelbild I _b an einer um den im ersten Iterationsschritt ermittelten Verschiebungsvektor d verschobenen Stelle angenommen. Das Gleichungssystem (16) wird mit einem neu berechneten Fehlervektor e erneut gelöst, wobei der im zweiten Iterationsschritt ermittelte zweite Verschiebungsvektor d eine verbesserte Lösung des Gleichungssystems (16) darstellt. Der beschriebene Iterationsschritt S ₆₉ wird solange wiederholt, bis die Lösung für den Verschiebungsvektor d konvergiert und das Merkmal M ₁ in dem zweiten Einzelbild I _b im Schritt

5 ₇₀ bestimmt ist. Das Lösen des Gleichungssystems (16) kann beispiels- weise mittels des Ne wton-Raphson- Algorithmus erfolgen. Wird nach einer Höchstzahl von Iterationen keine konvergierende Lösung für den Verschiebungsvektor d gefunden, wird das zugehörige Merkmal M ₁ im Schritt

5 ₇₁ verworfen und im Schritt S ₇₂ zu Schritt S ₆₆ zurückgegangen, wo das nächste Merkmal M ₂ ausgewählt wird.

Ist das Merkmal M ₁ im Schritt S ₇ o bestimmt, so wird im Schritt S ₇₃ zu Schritt S ₆₇ zurückgegangen, wo die nächsthöhere Auflösungs stufe j = 2 der Einzelbilder I _a und I _b ausgewählt wird. Anschließend werden die Schritte S ₆₈ , S ₆₉ und S ₇ o für diese Auflösungs stufe unter Berücksichtigung des in der vorangegangenen Auflösungsstufe ermittelten Verschiebungsvektors d wiederholt. Wurde diese Schleife für alle Auflösungsstufen j durchlaufen, so wird im Schritt S ₇₄ überprüft, ob weitere zu bestimmende Merkmale M vorliegen. Ist dies der Fall, wird Schritt S ₇₂ wiederholt. Wurden alle Merkmale M im Einzelbild I _b bestimmt, so werden im Schritt S ₇₅ verlorene Merkmale M ersetzt. Ein Merkmal M kann verloren werden, wenn dieses in dem Einzelbild I _b aufgrund der Verschiebung des Sensors 9 nicht mehr enthalten ist oder es im Schritt S ₇₁ als unbrauchbar verworfen wurde. In Schritt S ₇₅ werden verloren gegangene Merkmale M derart ersetzt, dass die Anzahl der Merkmal M wieder n beträgt. Das Ersetzen der Merkmale M im Schritt S ₇₅ erfolgt entsprechend dem Schritt S ₆₃ . Für die neu hinzugekommenen Merkmale M wird in Schritt S ₆₇ ein Speichervorgang initiiert. Sofern weitere Einzelbilder vorliegen, wird Schritt S ₆₅ wiederholt. Liegen keine weiteren Einzelbilder I vor, wird der KLT-Algorithmus im Schritt S ₇₆ verlassen und zu Schritt S ₁₃ übergegangen. Zum Zusammenfügen der Einzelbilder I _a und I _b werden die x- und y- Koordinaten der Pixel des verschobenen Einzelbildes I _b auf den nächsten ganzzahligen Wert gerundet. Dieses Verfahren wird auch als„nearest neighbour"- Verfahren bezeichnet. Die nachfolgenden Einzelbilder können durch Multiplikation der aktuellen Transformationsmatrix H _11-1 mit der vorangegangenen Transformationsmatrix Hj _{-1 0} wie folgt berechnet werden:

H _1; o ⁼ H _1-1; o " H _1;1-1 (25)

Mit dem erfindungsgemäßen Verfahren und der entsprechenden Vorrichtung 11 können 6 bis 25 Bilder pro Sekunde auf einem PC vom Typ Intel Core 2 6420 mit 2,13 GHz und 2 GB RAM erzielt werden.