Auszüge aus der Diplomarbeit
Ausgewählte Abschnitte aus der Diplomarbeit Automatische Lokalisierung von Textelementen in visuellen Medien ...
1 Einleitung
Text als Medium ist eines der häufigst verwendeten Mittel um Information zu übertragen, auszutauschen und zu archivieren. In vielen Bereichen des alltäglichen Lebens spielt das Lesen und Verstehen von textuellen Nachrichten eine essentielle Rolle. Im Gegensatz zum Menschen können Computer Text nur "lesen", wenn dieser nach einer Zeichentabelle, wie zum Beispiel ASCII1, kodiert ist. Ein Großteil der heute vorhandenen schriftlichen Information liegt jedoch in Form von Papier, von Bildern und von Videos vor [28], weshalb sie von Computerprogrammen nicht auf inhaltlicher Ebene erfasst werden kann.
Die Entwicklung von Programmen und Algorithmen, die textuell vorhandenen Inhalt aus Medien wie den oben genannten extrahieren können, ist daher erstrebenswert und wird seit einiger Zeit vorangetrieben [14]. Die Anwendungen für solche Algorithmen sind vielfältig.
Das kontinuierliche Wachstum digitaler Videoarchive verursacht Bedarf an sogenannten content based indexing and retrieval systems [15, 29], also Systemen, die Videomaterial anhand ihres textuellen Inhalts indizieren können. Bisher wurde Filmmaterial per Hand durch Redakteure katalogisiert, archiviert und bei Bedarf anhand von manuell erstellten Listen aus dem Archiv geholt. Ein automatisches System könnte die Arbeit des Katalogisierens schneller und ausführlicher durchführen sowie beim Suchen nach Stichworten - einen effektiven Suchalgorithmus vorausgesetzt - bessere, präzisere Ergebnisse liefern als die bisher verwendete Methodik. Eine nicht zu untersch ätzende Zeitersparnis würde als nützlicher Nebeneffekt auftreten.
Bilder spielen im World Wide Web eine entscheidende Rolle. Kaum eine Website kommt ohne Bilder aus und viele davon enthalten Text [10]. Für Suchmaschinenbetreiber wäre es erstrebenswert den textuellen Inhalt der Bilder interpretieren zu können um so in der Lage zu sein, Websites noch besser indizieren und einordnen zu können um dadurch die Treffergenauigkeit bei Suchanfragen erhöhen. 2003 litten in Österreich 5.7 Prozent der Bevölkerung an einer Beeinträchtigung des Sehvermögens2. Diese Menschen benutzen oft Browser, die Inhalte von Websites mittels einer Text-to-Speech Engine vorlesen. Die HTML-Spezifikation sieht zwar das alt-Attribut, das eine computerlesbare ASCII-Version des Bildinhalts beinhalten sollte, für im Web verwendete Bilder vor, allerdings halten sich nicht alle Programmierer an diese Konvention. Ein robuster Texterkennungsalogrithmus für Bilder würde das Websiteangebot für Sehbehinderte um ein Vielfaches vergrößern und damit einen Beitrag zur Integration dieser Bevölkerungsgruppe leisten.
Hinweistafeln können viele Inhalte haben (Werbung, Information, Gefahrenhinweise, etc.) und sind überall anzutreffen [12, 13]. Sie erleichtern das Leben, können aber Probleme oder gar Gefahr verursachen, wenn sie missinterpretiert oder nicht verstanden werden. Dies kann zum Beispiel der Fall sein, wenn der Hinweis in einem für Europäer unbekannten Zeichensatz wie asiatisch verfasst ist. Ein PDA3 mit einer Kamera und einem Texterkennungsprogramm könnte in Kombination mit einem Übersetzungsmodul Hinweistafeln übersetzen und so die dargestellte Information für den Benutzer verständlich aufbereiten.
Die Liste der Szenarien, die auf Textverstehenden Algorithmen basieren, ließe sich nahezu beliebig fortsetzen. Als Basis für diese Szenarien wurden in den letzten Jahren eine Vielzahl von Algorithmen entwickelt und veröffentlicht, die verschiedene Arten von Text in Bildern [10, 23, 31, 28, 25, 26] und Bildsequenzen [1, 16, 17, 3] lokalisieren und extrahieren.
1.1 Zielsetzung
Die Probleme und Herausforderungen beim Entwickeln von Algorithmen im Bereich der automatischen Textlokalisierung und -extrahierung sind vielfältig. Eine große Anzahl von Faktoren trägt dazu bei, dass die Erkennung keine triviale Aufgabe ist. Zu diesen Faktoren zählen unter anderen die perspektivische Verzerrung des Texts, teilweise Verdeckung von Textelementen, die optische Auflösung des Ausgangsmaterials, exotische Schriftarten sowie schwacher Kontrast zwischen Text und Hintergrund.
Die verschiedenen publizierten Algorithmen lassen sich anhand der verwendeten Methodik einteilen und zusammenfassen. Diese Diplomarbeit bietet eine detaillierte Übersicht über die in repräsentativen Publikationen vorgestellten Techniken und zeigt deren Gemeinsamkeiten, wichtige Unterschiede sowie Vor- und Nachteile der verwendeten Algorithmen auf. Der praktische Teil stellt eine neue Methode zur Identifizierung von Text in Bildern vor und beschreibt die dazu verwendeten Methoden und die damit erreichten Ergebnisse ausführlich.
...
1 American Standard Code for Information Interchange
2 Studie: Barrierefreies Internet in Österreich 2003, http://www.icosmedias.com/studie
3 Personal Digital Assistant
2.1 Ausgangsmaterial
Digitale Kameras sind nichts Neues im Bereich der digitalen Bildverarbeitung und in Kombination mit OCR bereits seit längerer Zeit im Einsatz 5]. So werden zum Beispiel hoch auflösende Digitalkameras verwendet, um empfindliche Dokumente zu digitalisieren, die bei der Verwendung von herkömmlichen Scannern erheblichen Schaden davontragen würden. Bei diesen Kameras handelt es sich um professionelle, für diesen Einsatzzweck entwickelte Geräte, die in Kombination mit perfekten Lichtbedingungen optimale Resultate erzielen. Dazu wird das zu digitalisierende Objekt flach positioniert und die optische Achse der Kameralinse so eingerichtet, dass sie rechtwinkelig auf das zu scannende Dokument steht.
Die in der Einleitung beschriebenen Beispielanwendungen für TIE-Systeme sollen jedoch mit gewöhnlichen, auf dem Markt einfach erhältlichen Linsensystemen, wie sie zum Beispiel in PDAs, Mobiltelefonen und digitalen Kompaktkameras verbaut sind, arbeiten. Diese Geräte sind nicht für die Aufnahme von Dokumenten geschaffen, wodurch die Voraussetzungen für eine direkte Anwendung von OCR-Software nicht optimal sind.
...
2.2 Nachweis
In der Nachweisphase prüft ein TIE-Algorithmus, ob im Eingabebild Text vorhanden ist. Beim Verarbeiten von Standbildern, wie zum Beispiel Aufnahmen von Hinweistafeln [12, 30], Nummernschildern [24] oder Adressen auf Postsendungen [8], ist dies oft per Definition der Fall und viele veröffentlichte Algorithmen gehen implizit davon aus, dass Text im Ausgangsmaterial vorhanden ist. In diesen Publikationen wird daher oft auf diesen Teil der TIE-Struktur verzichtet.
Falls es sich bei dem Ausgangsmaterial um Videosequenzen handelt [29, 10] beinhaltet es mit hoher Wahrscheinlichkeiten mehr Frames ohne Text als Frames mit Text. Eine Anwendung der Lokalisierungsstufe auf sämtliche Frames wäre daher sinnlos und würde die Laufzeit erhöhen.
Eine Möglichkeit das Vorhandensein von Text in Videomaterial zu erkennen ist auf das Erscheinen von Text zu achten. Da Text oft abrupt auftaucht, kann man über die Differenz zwischen zwei aufeinander folgenden Frames Rückschlüsse auf das Auftauchen von Text schließen. Die Rückschlüsse können im Frequenzbereich, wo das Vorhandensein von Text durch eine erhöhte Frequenz indiziert wird, im Bildbereich und anhand der Anzahl der intrakodierten Blocks der P- und B-Frames in MPEG Videomaterial vorgenommen werden. Im Bildbereich wird primär auf Intensitätsunterschiede zwischen zwei Frames geachtet, da man davon ausgeht, dass Text eine höhere Intensität als der Hintergrund hat. Dazu werden alle Pixel, die einen gewissen Helligkeitswert überschreiten und deren Nachbarpixel signifikant dunkler sind, addiert und aus dem Ergebnis geschlossen, ob es sich um einen Textframe handelt oder nicht. Probleme treten bei dieser Methode bei so genanntem reversed text, also hellem Text auf dunklem Hintergrund auf. Keine der drei auf Frameunterschieden beruhenden Methoden kann Texte, die langsam einoder ausgeblendet werden, erkennen [5].
Eine einfache Lösung des Nachweisproblems für Ausgangsmaterial in Videoform ist jeden Frame als potentiellen Textframe zu behandeln und der Lokalisierungsphase zu übergeben. Als Nachteile ergeben sich zwangsläufig eine Verschwendung von Rechenzeit auf Frames ohne Text und viele falsche Alarme. Es kann allerdings davon ausgegangen werden, dass Text eine gewisse Zeit sichtbar sein muss um vom Betrachter wahrgenommen werden zu können. Basierend auf dieser Annahme wird um Rechenzeit zu sparen nicht jeder Frame an die Lokalisierungsphase weitergegeben sondern nur Frames in einem konstanten Intervall [5].
Für die Nachweisphase werden meist globale Features herangezogen und diese mit Schwellwerten verglichen. In Videomaterial wird oft ausgenutzt, dass einzelne Frames zeitliche Vorgänger und Nachfolger haben und die Unterschiede zwischen diesen und dem aktuellen Frame anhand von Differenzbildern ermittelt. Wird in der Nachweisphase festgestellt, dass Text im Ausgangsmaterial vorhanden ist, wird dieses an den Lokalisierungsteil weitergegeben.
...
2.7 Evaluierung
In beinahe allen Teilbereichen von Computer Vision and Pattern Recognition (CVPR) gibt es Schwierigkeiten bezüglich der Performanceevaluierung. Die empirische Evaluierung ist ein wichtiges Mittel um festzustellen, ob und wie gut ein Algorithmus ein definiertes Set von Vorgaben erfüllt. Obwohl bereits viele Studien zum Thema objektive Performanceevaluierung in CVPR durchgeführt wurden, haben sich relativ wenige davon mit dem Subbereich TIE-Systemevaluierung beschäftigt.
Nachdem ein typisches TIE-System aus fünf Phasen besteht, kann jede einzelne Phase separat evaluiert werden. Die Ergebnisse der Nachweisphase einzelner TIE-Systeme können ohne Probleme miteinander verglichen werden indem die so genannte detection rate ermittelt wird. Diese ergibt sich aus dem Verhältnis der Anzahl von richtig identifizierten Textframes zur Anzahl aller im Ausgangsmaterial vorhandenen Textframes.
Die Ermittlung der Performance der Lokalisierungs- und Extraktionsphase ist ungleich schwieriger und bisher ist kein System verfügbar, das die verschiedenen Extraktionsalgorithmen auf objektive Art miteinander vergleichen kann. Im Folgenden werden die Gründe dafür und damit die Schwierigkeiten, die sich beim Vergleich von TIE-Systemen ergeben, erläutert [14].
Unter ground truth data versteht man die Vergleichsgrundlage, mit der die Ergebnisse entsprechender TIE-Systemphasen miteinander verglichen werden können. Im Gegensatz zur Evaluierung von Algorithmen anderer Videoerkennungssysteme wie der automatischen Erkennung von Szenenwechseln, Fahrzeugen oder Gesichtern, lässt sich die Erkennungsgenauigkeit für TIE-Systeme nur schwierig definieren. Die Vergleichsgrundlagen für Textlokalisierung sind üblicherweise begrenzende Rechtecke, die Buchstaben, Wörter und Textzeilen beinhalten. Falls ein TIE-Algorithmus sehr genau arbeitet und Text auf Buchstabenebene erkennt, wird er die Lücken zwischen zwei Buchstaben nicht als Text erfassen und die in der Vergleichsgrundlage definierten Textzeilen daher nicht komplett erkennen, wodurch sich eine (scheinbar) schlechte Performance ergibt.
Nach der Definition der Vergleichsgrundlage muss definiert werden, welche Maße verwendet werden um die Ergebnisse der Lokalisierung des TIE-Systems mit jenen der Vergleichsgrundlage zu vergleichen. Dazu werden üblicherweise die so genannte recall rate und precision rate verwendet. Zusätzlich muss definiert werden welche Elemente verglichen werden sollen. Hier kommen in der Praxis Pixel-zu-Pixel, Buchstabe-zu-Buchstabe und Rechteckzu- Rechteck Vergleiche zum Einsatz.
Durch die Vielzahl der Ziele der unterschiedlichen TIE-Systeme spielt die Anwendungsabhängigkeit eine entscheidende Rolle bei der Evaluierung. Es muss zwischen Algorithmen, die sämtlichen im Ausgangsmaterial vorkommenden Text erkennen sollen, wie es bei Videoindizierung notwendig ist, und solchen, die nur für die Autoren maßgeblichen Text wie zum Beispiel Sportspielstände oder Newsticker identifizieren sollen, unterschieden werden. Auch die Optimierung eines TIE-Systems auf entweder Geschwindigkeit oder Genauigkeit und die damit verbundenen dementsprechend gesetzten Gewichtungsfaktoren für falsche Alarme und falsche Nicht-Alarme sorgen dafür, dass der Vergleich von TIE-Systemen zu einer nicht trivialen Aufgabe wird.
Obwohl von vielen Autoren der Vergleich des eigenen Systems mit anderen Systemen erwünscht ist, gibt es keine domainspezifischen oder allgemeinen, umfangreichen Vergleichsdatenbanken mit Bildern oder Videos, die textuelle Information beinhalten. Aus diesem Grund verwenden die Entwickler von TIE-Systemen meist von ihnen selbst erstellte Datenbanken um die eigenen Algorithmen zu evaluieren [25, 13, 12, 15, 18, 4]. Diese Datenbanken enthalten oft Bilder, die spezifische, an den jeweiligen Algorithmus angepasste Annahmen beinhalten, wodurch es schwierig wird die Inhalte solcher Datenbanken für einen objektiven Vergleich heranzuziehen.
TIE-Systeme lassen sich anhand der unterschiedlichen Ausgabeformate unterscheiden, wodurch sich wieder das Problem der Vergleichbarkeit ergibt. So repräsentieren einige Algorithmen die Ergebnisse anhand von Bounding- Boxes ohne auf die Verzerrung oder Schräglage von Text zu achten, während andere nur die Textpixel ohne Hintergrund als Resultat darstellen.
...
3 Text-Spotting Agent
In diesem Kapitel wird ein neues Konzept zur Lokalisierung von Text in Standbildern vorgestellt. Der Text-Spotting Agent ist ein Algorithmus, der sich in Form der Lokalisierungsphase in jedes beliebige TIE-System integrieren lässt. Er erkennt arbiträr rotierte Buchstaben in Textelementen des Ausgangsbilds durch Vergleiche mit in einer Bibliothek vorhandenen Signaturen. Dazu wird das Bild in Regionen aufgeteilt und die Richtungen der am stärksten ausgeprägten Kanten jeder Region ermittelt. Die aus diesen Richtungen entstehende Signatur wird mit den Signaturen der Bibliothek verglichen und bei einer annähernden Übereinstimmung in einer Datenstruktur als Text markiert. Als zusätzliches Feature wird anhand der Signaturen der Bibliothek die Textrichtung jeder als Text markierten Region erkannt, wodurch örtlich nahe Regionen mit ähnlicher Textrichtung zu größeren Textbl öcken zusammengefasst werden können. Der Text-Spotting Agent liefert als Ergebnis eine Datenstruktur, die von der nächsten Phase eines TIE-Systems - Textextraktion und Verbesserung - weiterverarbeitet werden kann.
...
4 Zusammenfassung und Ausblick
Das Ziel dieser Diplomarbeit war es, einen neuen Ansatz zur Texterkennung zu entwickeln und vorzustellen sowie den aktuellen Stand der Technik im Bereich der automatischen Erkennung von Text in Stand- und Bewegtbildern darzustellen und zu diskutieren. Dazu wurden repräsentative Publikationen dieses Bereichs der automatischen Bildverarbeitung analysiert und die darin vorgestellten Algorithmen nach Herangehensweise und Methodik eingeteilt. Das Ergebnis der Analyse ist ein fünfstufiges Schema nach dem sich die meisten TIE-Systeme einteilen lassen.
In der ersten Phase, der Nachweisphase, wird das zu untersuchende Ausgangsmaterial analysiert und festgestellt, ob es wahrscheinlich ist, dass Text in diesem vorhanden ist. Dies ist vor allem bei Videoframes von großer Bedeutung, da eine typische Videosequenz mehr Einzelbilder ohne Text als mit Text beinhaltet und eine Anwendung der Lokalisierungsphase auf jeden Frame eine Verschwendung von Ressourcen darstellen würde.
Die Lokalisierungsphase ist jene Phase, in der die Positionen von Textelementen im Ausgangsbild festgestellt wird. Ein großer Teil dieser Diplomarbeit ist dieser essentiellen Phase gewidmet, da hier eine Vielzahl unterschiedlicherMethoden und Strategien publiziert wurde. Je nach verwendeten Features zur Texterkennung lassen diese sich in Bottom-Up und Top-Down Ansätze einteilen. Erstere gehen dabei von Elementen wie Kanten oder zusammenh ängenden Komponenten im Ausgangsbild aus - man spricht daher auch von "data driven" Ansätzen - und erstellen durch das bedingte Zusammenf ühren dieser Elemente Bounding-Boxes, die mit hoher Wahrscheinlichkeit Text beinhalten. Top-Down Ansätze sind "model-driven" und identifizieren Textelemente anhand von Texturen oder Pattern im Frequenzbereich. Zu den dazu eingesetzten Methoden gehören Garbor-Filter, Wavelet- Transformationen und neuronale Netzwerke.
Der praktische Teil der Diplomarbeit stellt eine neue Methode zur Identifizierung von Textelementen im Rahmen der Lokalisierungsphase eines TIESystems vor. Der Text-Spotting Agent analysiert die Kanteninformationen des Ausgangsbilds und basiert auf der Theorie, dass sich Textelemente anhand der Richtungsunterschiede der vorkommenden Kantenrichtungen erfassen lassen ("model-driven"). Zur Definition der Richtungsunterschiede dient eine Bibliothek, deren Elemente ("Signaturen") im Zuge der Ausführung des Text-Spotting Agent mit den unbekannten im Ausgangsbild gefundenen Signaturen verglichen werden. Bei einem positiven Vergleich wird aus der Bibliothek die Textrichtung der entsprechenden Signatur ausgelesen und diese zusammen mit der Stärke derselben und einer daraus berechneten Textwahrscheinlichkeit an den nächsten Schritt des TIE-Systems übergeben. Durch die Verwendung der rotations- und skalierungsinvarianten Signaturen als Features wird der Vergleich von zwei Featurewerten vereinfacht. Die prototypische Java Implementierung des Text-Spotting Agent ist in der Lage einen Großteil der Versalien des lateinischen Alphabets anhand von nur acht verschiedenen Signaturen zu identifizieren.
Die nächste Phase - Tracking - wird nur für videoverarbeitende TIESysteme benötigt und hat die Aufgabe die Berechnung redundanter Informationen zu vermeiden: Sich bewegende Textblöcke sollen durch die Lokalisierungsphase nur ein Mal erkannt werden und anschließend über die folgenden Frames verfolgt werden, wodurch eine erneute Lokalisierung verhindert wird.
In der Phase der Textextraktion und Verbesserung werden die lokalisierten Textblöcke für eine Weiterleitung an Standard OCR-Software vorbereitet. Die dazu nötigen Operationen hängen stark vom Anwendungsgebiet und damit dem Ausgangsmaterial des jeweiligen TIE-Systems ab. Vor allem bei Algorithmen zur Erkennung von Szenetext kann in dieser Phase eine Vielzahl von Prozeduren wie zum Beispiel der Korrektur von perspektivischen Verzerrungen oder von unregelmäßiger Beleuchtung notwendig sein. Bei Ausgangsmaterial in Form von Bewegtbildern wird meist eine künstliche Erhöhung der Auflösung und eine Schärfung der Kanten durchgeführt. Danach wird mittels eines dynamisch zu berechnenden Schwellwerts jeder Textblock binarisiert und an die letzte Phase des TIE-Systems, die Erkennung, weitergegeben. Diese setzt mittels eines "off-the-shelf" OCR-Softwarepakets die übergebenen Textelemente in maschinenlesbaren ASCII-Text um.
Ein bekanntes Problem im Bereich der automatischen Erkennung von Text ist die Evaluierung von TIE-Systemen. Es existiert bis dato keine unabh ängige Bild- oder Videodatenbank mit definierten zu identifizierenden Textinhalten, die zu objektiven Vergleichen herangezogen werden könnte. Vor allem auf Grund der beschriebenen Unterschiede in den Anforderungen an die TIE-Systeme wird es auch in Zukunft schwierig bleiben solche objektiven Gegenüberstellungen durchzuführen.
4.1 Diskussion der Ergebnisse und Ausblick
Die prototypische Implementierung des Text-Spotting Agent ist theoretisch in der Lage 20 Großbuchstaben des lateinischen Alphabets zu identifizieren. Die restlichen sechs Versalien enthalten nicht genügend durchgehende Kanten um mit diesem Verfahren als Signatur erfasst werden zu können. Hier könnte die Verwendung eines zweiten, parallel arbeitenden, auf die Features runder Buchstaben reagierenden Algorithmus Abhilfe schaffen. Alternativ kann in der Textextrahierungs- und Verbesserungsphase versucht werden, die nicht identifizierten Buchstaben anhand ihrer erkannten Nachbarbuchstaben in Textblöcke zu integrieren.
Der Prototyp des Text-Spotting Agent liefert in vielen Fällen falschen Alarm. Vor allem architektonische und natürliche Strukturen werden vom Algorithmus oft fälschlicherweise als Text eingestuft. Textregionen in natürlichen Formationen wie den Ästen von Bäumen lassen sich relativ problemlos in der Textextraktions- und Verbesserungsphase des TIE-Systems während dem bedingten Zusammenführen von Textregionen mit gleichen oder ähnlichen Textrichtungen eliminieren. Die Textidentifikation von Strukturen in Architektur lässt sich nur schwierig korrigieren, da Fenster, Säulen und Fassadenelemente im Kantenbild genau jene Eigenschaften aufweisen, auf die der Text-Spotting Agent anspricht.
Obwohl der Text-Spotting Agent auf eine unkomplizierte Erweiterung der verwendeten Signaturen ausgelegt wurde, ist es möglich, dass - ähnlich wie bei der Einbindung des Buchstaben Y - die Erweiterung der Signaturdatenbank zu einer niedrigeren durchschnittlichen Erkennungsrate führt. Der Grund hierfür ist in der gegenseitigen Beeinflussung der Signaturen zu suchen, die mit der Anzahl der unterschiedlichen Signaturen in der Bibliothek exponentiell ansteigt.
Der Text-Spotting Agent reiht sich in eine Vielzahl von in den letzten Jahren entwickelten Algorithmen und Methoden zur automatischen Texterkennung ein. Der Bedarf an solchen robusten TIE-Systemen wird in den kommenden Jahren weiter zunehmen, da textuelle Informationen verschiedenster Ausprägungen in Bildern und Videos in vielen Bereichen des Alltags eine immer größere Rolle spielen. Die Weiterentwicklung und Verbesserung der Erkennungs- und Lokalisierungsalgorithmen wird daher weiterhin ein sich rasant entwickelnder und bedeutender Bereich der Computer Vision und der automatischen Bildverarbeitung bleiben.
Die vollständige Diplomarbeit ist unter Ressourcen zum Download bereitgestellt.