Refine
Year of publication
- 2007 (2) (remove)
Document Type
- Diploma Thesis (1)
- Doctoral Thesis (1)
Language
- German (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Approximability (1)
- Approximierbarkeit (1)
- Berechnungskomplexität (1)
- Formale Sprache (1)
- Maschinelles Lernen (1)
- Regular Languages (1)
- Reguläre Sprachen (1)
Institute
- Informatik (2)
Manipulierte Bilder werden zu einem immer gröÿeren Problem in der aktuellen Berichterstattung und sie verursachen in vielen Fällen Empörung unter den Lesern.
In dieser Diplomarbeit werden verschiedene Ansätze aus der aktuellen Forschung aufgezeigt, die zur Erkennung von manipulierten digitalen Bildern benutzt werden können. Hierbei liegt der Schwerpunkt besonders auf verschiedenen statistischen Ansätzen von Farid, Johnson und Popescu. Ein Abriss über die wichtigsten inhaltsbasierten Algorithmen wird ebenfalls gegeben.
Weiterhin wird für die Algorithmen, die im Hinblick auf technische Realisierbarkeit, Laufzeit und ein breites Spektrum von möglichen Szenarien vielversprechend wirken, eine Automatisierung entwickelt, die die Analyse ohne weitere Benutzereingaben durchführt. Das Augenmerk liegt hier besonders darauf, dass die zu analysierenden Bilder möglichst wenige Vorraussetzungen erfüllen müssen, damit es eine Möglichkeit der korrekten Erkennung gibt.
Diese Automatisierungen werden implementiert, wenn möglich verbessert und auf einer Menge von Bildern getestet. Enthalten sind sowohl zufallsgenerierte Bilder, als auch aus geometrischen Formen synthetisierte und natürliche Bilder. Die Erkennung der auf die Bilder angewandten Fälschungstechniken beschäftigt sich vor allem mit Duplikationen, Einfügen und Interpolation von Bereichen.
Der Test dieser Implementierung konzentriert sich auf die absolute Effektivität und Effiienz gegen die gegebene Testmenge, betrachtet jedoch auch die spezifischen Vor- und Nachteile der ursprünglichen Algorithmen und der entwickelten Verbesserung. Ihre Ergebnisse, die sie auf den Testbildern erbringen, legen die Grundlage für eine Beurteilung der Algorithmen bezüglich Laufzeit und Effiienz.
Aufbauend auf diesen Analysen wird eine Bewertung der Algotihmen vorgenommen, die auch einen Ausblick auf mögliche Szenarien in der digitalen Bildbearbeitung und der Erkennung von Fälschungen für die nächsten Jahre geben soll.
Im Gegensatz zur Minimierung von DFAs ist die exakte Minimierung von NFAs oder regulären Ausdrücken nachweislich schwierig, im allgemeinen Fall PSpace-schwer. Wir zeigen, dass selbst schwache Approximationen zur Minimierung von NFAs und regulären Ausdrücken wahrscheinlich nicht effizient möglich sind. Falls als Eingabe ein NFA oder regulärer Ausdruck der Größe n gegeben ist, löst ein Approximationsalgorithmus für das Minimierungsproblem mit Approximationsfaktor o(n) bereits ein PSpace-vollständiges Problem. Wenn wir uns auf NFAs oder reguläre Ausdrücke über einem unären - also einelementigen - Alphabet beschränken, so ist das Problem der exakten Minimierung NP-vollständig. Wir weisen nach, dass effiziente Approximationen für das unäre Minimierungsproblem mit Approximationsfaktor n^(1-delta) für jedes delta>0 nicht möglich sind, sofern P != NP gilt. Liegt die Eingabe als DFA mit n Zuständen vor, kann sie exponentiell größer sein als ein äquivalenter NFA oder regulärer Ausdruck. Dennoch bleibt das Minimierungsproblem PSpace-schwer, wenn die Anzahl der Übergänge oder Zustände in einem äquivalenten NFA oder die Länge eines äquivalenten regulären Ausdrucks zu bestimmen ist. Wir zeigen, dass auch hierfür keine guten Approximationen zu erwarten sind. Unter der Annahme der Existenz von Pseudozufallsfunktionen, die wiederum auf der Annahme basiert, dass Faktorisierung schwierig ist, zeigen wir, dass kein effizienter Algorithmus einen Approximationsfaktor n/(poly(log n)) für die Zahl der Übergänge im NFA oder die Länge des regulären Ausdrucks garantieren kann. Für die Zahl der Zustände im NFA weisen wir nach, dass effiziente Approximationen mit Approximationsfaktor (n^(1/2))/(poly(log n)) ausgeschlossen sind. Wir betrachten dann Lernprobleme für reguläre Sprachen als Konzeptklasse. Mit den entwickelten Methoden, die auf der Annahme der Existenz von Pseudozufallsfunktionen beruhen, zeigen wir auch, dass es für das Problem des minimalen konsistenten DFAs keine effizienten Approximationen mit Approximationsfaktor n/(poly(log n)) gibt. Für den unären Fall hingegen weisen wir nach, dass es einen effizienten Algorithmus gibt, der einen minimalen konsistenten DFA konstruiert und erhalten somit auch einen effizienten PAC-Algorithmus für unäre reguläre Sprachen, die von DFAs mit n Zuständen akzeptiert werden. Für unäre Beispielmengen weisen wir außerdem nach, dass es keine effizienten Algorithmen gibt, die minimale konsistente NFAs konstruieren, falls NP-vollständige Probleme nicht in Zeit (n^(O(log n)) gelöst werden können. Andererseits geben wir einen effizienten Algorithmus an, der zu unären Beispielmengen einen konsistenten NFA mit höchstens O(opt^2) Zuständen konstruiert, wenn ein minimaler konsistenter NFA opt Zustände hat. Abschließend betrachten wir das Lernen von DFAs durch Äquivalenzfragen. Für den nicht-unären Fall ist bekannt, dass exponentiell viele Fragen für DFAs mit n Zuständen benötigt werden. Für unäre zyklische DFAs mit primer Zykluslänge und höchstens n Zuständen zeigen wir, dass Theta((n^2)/(ln n)) Äquivalenzfragen hinreichend und notwendig sind. Erlauben wir größere zyklische DFAs als Hypothesen, kommen wir mit weniger Fragen aus: Um zyklische DFAs mit höchstens n Zuständen durch Äquivalenzfragen mit zyklischen DFAs mit höchstens n^d Zuständen für d <= n als Hypothesen zu lernen, sind O((n^2)/d) Fragen hinreichend und Omega((n^2 ln d)/(d (ln n)^2)) Fragen nötig.