SPEZIELLE MUSTERANALYSESYSTEME Schrift

Transcrição

Schriftdaten
Anwendungsszenarien
SPEZIELLE MUSTERANALYSESYSTEME
Schrift- und Spracherkennung mit
Hidden-Markov-Modellen
Explizit segmentierend
Implizit segmentierend
Teil IX
Maschinelle Schrifterkennung
Vorlesung im Wintersemester 2016
Prof. E.G. Schukat-Talamazzini
Stand: 5. September 2016
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Hardware zur digitalen Schriftdatenerfassung I
Schriftdaten
Maschinelle Schriftdatenerfassung
Schriftdatenvariabilität
Segmentierung von Wörtern in Zeichen
y
Der SCANNER
wandelt eine Papiervorlage in eine
Bildmatrix
Anwendungsszenarien
[f (x, y )]x=1..N;y =1..M
Explizit segmentierende Systeme
Vorteile „off-line“
Implizit segmentierende Systeme
x
Verarbeitung bestehender
Dokumente
hohe Lesegeschwindigkeit
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Hardware zur digitalen Schriftdatenerfassung II
Der Bilddatenscanner
y
Der DIGITIZER
wandelt die Schreibstiftbewegung
in eine Koordinatenpaarfolge
[(xi , yi )]i=1..L
Zeilenweise Abtastung der Vorlage
durch Flachbett-, Papiereinzugs- oder Handscanner
Digitale Umsetzung der Helligkeitswerte
durch Vektor oder Matrix von Photozellen
heute CCD (charge-coupled device)
Vorteile „on-line“
x
Dynamik- & Sequenzinformation
geringeres Datenvolumen
konstante Strichdicke
Binärbildmatrix vs. Grauwertmatrix
binär: f (x, y ) ∈ {0, 1}
b-bit Grauwerte: f (x, y ) ∈ 0, 1, 2, . . . , 2b − 1
Auflösung & Verarbeitungsgeschwindigkeit
Ortsauflösung 300–1200 ppi (pixel/inch) · 256 Graustufen (8 bit) · bis zu 1000 Zeichen/sek
Schriftdaten
Anwendungsszenarien
Schriftdaten
ift
St
Sic
htli
nie
Das graphische Tablett
Warum ist Schrifterkennung schwierig?
Variabilität
Die Handschriftausprägung ist abhängig von
· Stil, Bildungsgrad, Anatomie, Gesundheitszustand sowie
· Schreibgerät, Schreibfläche und Aufnahmeapparatur.
perzipierte Position
Displayebene
Digitizerebene
Anwendungsszenarien
digitalisierte Position
Resonanztechnologie
Kontinuität
Signal von Grafiktablett an Stiftspitze · Impuls an Rechner zur Bestimmung der x/y -Position
Die Einzelschriftzeichen kursiv geschriebener Texte
sind in Bildmatrix/Punktfolge i.a. nicht segmentiertbar.
Folge der Abtastpositionen (xi , yi )
Ambiguität
Schreibtempo und -beschleunigung · pen-up/pen-down-Signal
Orientierung und Reihenfolge der Striche (strokes)
O
I
Σ
Visuelle Rückkopplung
Komplexität
Display zeigt x/y -Spur an (electrinic ink)
Parallaxe zwischen digitalisiertem & perzipiertem Aufsetzpunkt
Segmentierungsalternativen
Zeichensätze
alphanum. 62 + ε · mathem. (250) · Kanji (6500) · chines. (50 000)
Wortschätze
Scheckbetrag (10..50) · Postadressen (100..1000) · Texterfassung (10 000+)
Syntaxmodell
lexikalisch · grammatisch · PLZ+Ortsname · Formularaufbau
Auflösung & Verarbeitungsgeschwindigkeit
Ortsauflösung 200–600 ppi (pixel/inch) · Zeitauflösung 100 pps (pixel/sek) · Echtzeiterfassung
kleines/großes ’O’, Null, Einkreisung, Kommandogeste ?
kleines ’L’, Ziffer ’1’, senkrechter Balken, Apostroph ?
großes Sigma, Summenzeichen ?
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Erfassungsbedingte Variabilität
Statische Variabilität
Geometrische Transformationen
Größe, Form, Neigung, Rotation, Liniendicke
Störungen
Topologische Kategorien
Papierunreinheiten
Stempel
Hilfslinien
Zeichenboxen
Kontinuum
Spitze
Schlinge
Deformationen durch Scanner
Löcher
Unterbrechungen
isolierte Punkte
Segmentale Kategorien
Deformationen durch Digitizer
Kontinuum
Spitze
Buckel
Strichanfangdefekt (pen-up)
Häkchen am Strichende (pen-up)
Schriftdaten
Anwendungsszenarien
Dynamische Variabilität
• Strichfolge
• Strichzahl
• Schreibtempo
• Nachspurung
Fragestellung
In welchem Verarbeitungsschritt wird das jeweilige Phänomen behandelt?
(Merkmalgewinnung, Segmentierung, Matching, Modellierung)
Schriftdaten
Anwendungsszenarien
Beispiel: Ziffernrealisierungen
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Schreiberverfassung
Blockschrift gesperrt
Selbst Ziffern zu segmentieren ist aussichtslos!
Kursivschrift
jedes Einzelwort ist zusammenhängend
topologisch getrennt
Kursivschrift durchbrochen
Blockschrift verklebt
Block- und Kursivschrift
Berührung; Überlappung
Anwendungsszenarien
Darbietungsform
Blockschrift in Zeichenboxen
Schriftdaten
Schriftdaten
gemischt
Anwendungsszenarien
Zeichensegmentierung
Die Segmentierung von ’on-line’-Schriftdaten ist einfacher?
Mehrstrichhaltige Zeichen
d = c+l
Verzögerte Ligaturen & Diakritika
Überschneidung von Ziffernbestandteilen
Überlappung von Ziffernaufenthaltsbereichen
Übergreifende Unterstreichungen & Dekorierungen
Geteilte Strichverantwortung
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Arabische Schriftzeichen
Arabisches Alphabet
Besonderheiten arabischer Schrift
·
·
·
·
·
·
·
·
·
·
keine Majuskel/Minuskel-Unterscheidung
Punkte oben/unten/mittig (≤ 3) als Unterscheidungsmerkmal
Diakritische Ergänzungen: alif, madda, hamza, ta’marbuta
Schreibrichtung rechts→links
PAW (pieces of arabic words) wegen Basisligatur & Ausnahmen
4 positionsabhängige Buchstabenausprägungen
Überlappungen auf der Horizontalen
Ungewöhnliche Größenunterschiede (Breite und Höhe)
Vokale optional & als Diakritika realisiert
Buchstabenverdopplung mittels chadda
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Segmentierung, Umschreibung, Typographie ?
Schriftdaten
Anwendungsszenarien
Handschrift
Handschrift und Druckschrift
Druckschrift
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungen optischer Schriftzeichenerfassung - OCR
Anwendungsszenarien
Elektronische Tinte auf intelligentem Papier
PEN-Computer, Notepad
Postanschriftenleser
Papier-und-Bleistift Kommunikation
Automatische Poststücksortierung
Adreßfeld = PLZ, Ort, Straße, (Bundesstaat)
Kleinstrechner in Notizblockgröße
Dateneingabe per Stift auf PAD
(pen-and-display)
keine Tastatur
Bank-, Zoll- und Versicherungsformulare
Kooperativer Schreiber
Ziffern
(eigenes Erfolgsinteresse)
· schreibt sorgfältig (Normschrift?)
· benutzt Hilfslinien & Zeichenboxen
· Datenerfassung in mobilen
Einsatzbereichen
· wenn eine Tastatur zu groß/laut wäre
· zur hybrid textuell-graphischen Eingabe
· zur Textkorrektur und -annotation
· für die Zugangskontrolle
Teilautomatisierung
menschliche Schreibgeschwindigkeit
(partieller Rationalisierungsgewinn)
· deutliche Rückweisungsrate
· sehr niedrige Fehlerrate
Intelligente Wandtafeln
1.5–2.5 Zeichen/sek
(alphanumerisch, Blockschrift)
(alphanumerisch, Kursivschrift)
(chinesisch)
Anschrieb von CCD-Kamera erfaßt
· Protokollierung von Vorträgen
· Transliteration (LATEX)
· On-line Grafikeinblendung
· On-line Grafikerstellung
· On-line Formelauswertung
Formularleser
Block
Kursiv
— Geldbetrag, Konto, BLZ, Datum, KFZ
— Vor/Zuname, Institut, Warenkennung, ...
— Betragstext, Unterschrift
Texterfassungssysteme
Schriftdaten
Anwendungsszenarien
U.S. Postal Service
Kuvertaufdruck überschrieben
Umrandungsbox verlassen
Poststempel überlagert
Hilfslinien berührt &
Bildrotation
Hilfslinien überschrieben
Briefmarke & Poststempel
Schriftdaten
Anwendungsszenarien
PenRight! / PalmPrint
multilingual ohne Wörterbuch
benutzerdefinierte Zeichen
Unterschrift statt Paßwort
Buchstaben, Ziffern und (Zeige-)Gesten
lernfähig, mit Gastmodus
Weltläufige Kameras
Liest und übersetzt Dokumente
Liest und verortet Straßenschilder
Überweisungsbelege
Schriftdaten
Anwendungsszenarien
Schriftdaten
Kontonummern auf Überweisungsbelegen
Schriftdaten
Anwendungsszenarien
Anwendungsszenarien
Verkehrsüberwachung — Gefahrgüter
Schriftdaten
Anwendungsszenarien
Kraftfahrzeug-Kennzeichen
Schriftdaten
Anwendungsszenarien
Wortvereinzelung
Segmentierung & Merkmalgewinnung
Matching & Fehlernachbearbeitung
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Sequentielle OCR-Architektur
Layout-Analyse
Schriftdateneingabe
Zerlegung
Störunterdrückung
BLOCKSCHRIFT
eines Dokuments in seine logischen
Bestandteile
Unterschrift
Bankinstitut
BLZ
Konto−Nr.
KURSIVSCHRIFT
(Layoutanalyse)
Datum
Empfänger
Betrag
Verwendungszweck
noch Verwendungszweck
Segmentierung
Normierung
Normierung
Segmentierung
Kontoinhaber
Konto−Nr.
explizite
Segmentierung
in
Einzelzeichen
Merkmalgewinnung
Post−
wert−
zeichen
implizite
Segmentierung:
Strichsegmente,
Linienelemente
Klassifikation
BLZ
Absender
Überweisungsbeleg
Adressatenname
Straße & Hausnummer
PLZ
Ortsname
Briefkuvert
kontextuelle
Nachbearbeitung
Schriftdaten
Anwendungsszenarien
Schriftdaten
Wiederholte Bildprojektion
y
Anwendungsszenarien
Normierung
(Elimination von Variabilitäten im Vorfeld der Klassifikation)
y
Rotation
der Vorlage oder der Schriftzeile um einen Winkel α
x
x
Neigung
der vertikalen Schriftkomponenten um einen
Winkel α
Iteriertes Auswerten vertikaler & horizontaler Bildprojektionen
Größe
·
·
·
·
relative Ausdehnung rx , ry von Zeichen/Wörtern in
x- und y -Richtung
Spalten
Textblöcke
Zeilen
Wörter
Liniendicke
des gescannten Shriftbildes übersteigt i.a. einen
Pixel
Schriftdaten
Anwendungsszenarien
Schriftdaten
Koordinatentransformation
Anwendungsszenarien
Schriftaufrichtung
1. Bestimmung der Normierungsfaktoren α, β, rx , ry
2. Transformation der Bildebenenkoordinaten T : (x, y ) 7→ (x 0 , y 0 )
Originalbild mit geneigter
Schrift
α
β
Akkumulatorebene mit den
Punktdichten (x, α)
Rotation
Neigung
Größe
Vertikale
Scherungsoperation
0 x
x
=
y0
y − x · tan α
Horizontale
Scherungsoperation
0 x
x − y · cot β
=
y0
y
Anisotrope
Skalierungsoperation
0 x
x/rx
=
y0
y /ry
Schriftdaten
Anwendungsszenarien
Typographische Begrenzung
aufgerichtetes Schriftbild
Schriftdaten
Anwendungsszenarien
Linienverdünnung
(auf die Breite eines Pixels)
Vertikale Schriftbereiche:
• Oberlängenbereich
• Schriftkorpus oder -basis
• Unterlängenbereich
Sind die vier Begrenzungslinien parallele
Geraden, so genügt zur Detektion eine
Vertikalprojektion.
Projektion
Oberlinie
Mittellinie
Grundlinie
Unterlinie
Skelettierung mit Gaborfiltertechnik
Die Filterausgabe ergibt eine Bewertung
aller Bildpunkte hinsichtlich ihrer
Mittelachseneigenschaft.
Schwellwertbildung liefert schon fast ein
Linienmuster.
Schriftdaten
Anwendungsszenarien
Schriftdaten
Segmentierung in Einzelzeichen — Blockschrift
Anwendungsszenarien
Segmentierung in Einzelzeichen — Kursivschrift
Blockschrift
· Nullstellen der vertikalen Bildprojektion
· Analyse zusammenhängender Gebiete
Probleme
· Untere Ligaturen sind zur Zeichensegmentierung unzureichend!
· Striche überspannen Buchstabenfolgen!
· Striche unterteilen Einzelzeichen!
Berührende oder überlappende Blockschrift
· relative Minima der vertikalen Projektion
· Verbinden der lokalen Extrema der oberen & unteren Wortkontur
· objektrandgesteuerter Abstieg von lokalen Minima der oberen
Wortkontur
’o’, ’v’ und ’r’ bilden obere Ligaturen
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Segmentierungstechniken I
Geometrische Segmentierung in Striche
·
·
·
·
lokale x- und y -Extrema
Steigungsdiskontinuitäten
Wendepunkte
Krümmungsmaxima
’u’ und ’w’ beinhalten untere Ligaturen
Segmentierungstechniken II
Topologisch orientierte Liniensegmentierung
Anzahl Nachbarpixel:
1 = Linienende
2 = Linieninneres
3 = Gabelung
4 = Kreuzung
2
3
Segmentierung in Formelemente
reguläre/singuläre Ereignisse · PDL (picture description language)
3
1
4
1
1
4
1
1
Dynamische Strichsegmentierung
· kleinste motorische Einheiten
· Zyklus „Beschleunigung–Tempogipfel–Verlangsamung“
Schriftdaten
Anwendungsszenarien
Schriftdaten
Einzelzeichenmerkmale
Anwendungsszenarien
Polare und spektrale Merkmale
Repräsentation des Schriftzeichens durch einen Merkmalvektor
• Betragsspektrum der Konturpunktfolge ∈ CT
x = (x1 , . . . , xD )> ∈ IRD
• Polarkoordinaten der Konturpunkte bzgl. Objektschwerpunkt
Beispiele für Merkmale:
f (x, y ) selbst · 2D-FFT · PCA · zentrale Momente · (siehe )
Winkelschnittanalyse
Schriftdaten
Ring−
Projektion
zonenbezogene Punktdichte
Anwendungsszenarien
Segmentbezogene Merkmale
• Länge —
Analytische
Methode
zwischen x-Achse und Sehne oder Regressionsgerade
• Mittlere Krümmung
2
2 2
2
• Typographische Position
Schriftzeichen explizit segmentiert
ein zeichenbezogener Merkmalvektor
numerische Klassifikation
2 2
Eingabemuster
mittleres Schreibtempo und max. Beschleunigung
bzgl. Grund-, Mittel-, Unter- und Oberlinie
Referenzmuster
grobe Quantisierung der möglichen Referenzwinkel
OL
3
2
Einzelzeichenvergleich
0
5
GL
6
UL
typographische Position
Kettencode
elastischer Mustervergleich
1
4
ML
Richtungswinkel
|κ(t)| = (d / dt ) + (d y / dt )
• Dynamische Merkmale —
• Kettencode —
2
Anwendungsszenarien
Zeichen- und Wortklassifikation
Anzahl der Segmentbildpunkte
• Referenzwinkel
Schriftdaten
7
Syntaktische
Methode
Kette, Baum oder Graph von Segmenten
(Zeichenebene)
Kette, Baum oder Graph von Segmenten
(Wortebene)
Zeichenmatching
Wortmatching
Schriftdaten
Anwendungsszenarien
Schriftdaten
Anwendungsszenarien
Elastischer Mustervergleich
b2
Zeichenprototyp
Eingabemuster
a4
b4
b5
a3
Vergleich einer parametrisierten
Strichsegmentfolge mit einem
Zeichen- oder Wortprototypen:
Motivation
b3
e
ndierend
korrespo
te
Segmen
a2
·
·
·
·
·
·
Leicht verwechselbare Zeichen
Distribution von Majuskeln/Minuskeln und Buchstaben/Ziffern
Buchstabenfolgen ergeben korrekte Wörter !
Wortfolgen ergeben domänenspezifisch sinnvolle Ausdrücke
Testpassagen sind syntaktisch & semantisch wohlgeformt
mittlere Worthäufigkeiten
K1as
se
St
gu
Au
b2
b3
b4
b1
b2
b3
b4
b1
b2
b3
b1
b4
a1
1
4
5
8
a1
1
5
10
18
a1
a1
a2
4
3
2
7
a2
5
4
6
13
a2
a2
7
4
9
0
12
8
13
6
a3
a3
lokale Distanzen
Schriftdaten
a3
kumulative Distanzen
Anwendungsszenarien
b2
b3
b4
A u g
u S
en
rlang
8E
9705
A u g u S t
H v p v s f
n
i
Zeichenselektion
t
A u g u s t
Zeichenkorektur
lokale Transitionen
DM 2S0.−
Nachverarbeitung
a3
Rückwärtszeiger
Dien
slag
−78T3
Tel.: 85
DTW-Algorithmus zur dynamischen Skalenverzerrung
b1
Kontextuelle Nachverarbeitung
b1
a1
Schriftdaten
Anwendungsszenarien
Fundamentalformel der (Hand-)Schrifterkennung
Schriftdaten
Anwendungsszenarien
Bayesregel & Systemarchitektur
Serialisierung in ein Longitudinalmuster
Hidden-Markov- und andere Wahrscheinlichkeitsmodelle
LINGUISTIK
Text−
erzeugung
P(w)
HANDSCHRIFTPRODUKTION
w
Schreiber
Scanner
Digitizer
P(X | w)
w∗
X
Merkmale
Dekodierung
P(X, w)
Schriftdaten
Anwendungsszenarien
Schriftdaten
Architektur eines HSE-Systems
Anwendungsszenarien
Serialisierung des Schriftbildes
Markovmodelle
für Wörter
und Einzelzeichen
Repräsentation des Schriftzuges als Vektorsequenz
a) Überlappende Zerlegung in schmale Bildspalten
b) Mäandernde 2D-Traversierung des Schriftbildes
Normierung
Segmentierung
Maximum
a posteriori
Dekodierung
Merkmal−
gewinnung
c) Geometrie- oder produktionsorientierte Schriftkonturverfolgung
Grammatik
Lexikalisches Modell
Satzsyntax / Textsyntax
Schriftdaten
Anwendungsszenarien
Überlappende Abtastung des Schriftzuges
Schriftdaten
Anwendungsszenarien
Problematik der Fensterbildung
Vertikalausrichtung
Zeichenkorpus, Oberlänge oder Unterlänge befinden sich außerhalb
ihrer korrekten typographischen Region
• Fensterbreite
Größenordnung einer durchschnittlichen Zeichenbreite
• Fortschaltung
etwa 2–5 Fenster/Zeichen
Horizontalausrichtung
Komponenten benachbarter Zeichen teilen sich dieselbe Bildspalte
(Schriftneigung)
Schriftdaten
Anwendungsszenarien
Nichtlineare Modelle für Basislinien
Schriftdaten
Anwendungsszenarien
Hidden Markov Modelle für Zeichen und Wörter
elementarer
HMM−Zustand
für Liniensegmente
einfaches Zeichenmodell
aus Segmentmodellen
’d’ (Block)
komplexes Zeichenmodell
’d’ (Kursiv)
• Konische obere/untere Basis- und Begrenzungslinien
’U’
’n’
’i’
’x’
• Wellenförmige typographische Begrenzungen
’L[o’
Schriftdaten
Anwendungsszenarien
Dekodierung von Ort und Postleitzahl
’0’
’1’
’2’
’9’
Einzelziffern−
erkennung
5−stellige Postleitzahlen
91058
bel. Ziffernfolge
ERLANGEN
Postleitzahl−Ortsname−Kongruenz
Schriftdaten
’L]o[s’
’o]s’
Anwendungsszenarien
Wortmodell
aus Zeichenmodellen
Wortmodell aus
kontextabhängigen
Zeichenmodellen
Implizite vs. explizite Segmentierung
Schriftdaten
Anwendungsszenarien
Eindimensionale & zweidimensionale Zufallsprozesse
Schriftdaten
Anwendungsszenarien
MRF — Markov Random Fields
1D-HMM
HMM
Zustandsfolge
Zustand
Bildspalte
MRF Abhängigkeitstopologien
2D-HMM
HMM
Schriftdaten
Zustandsmatrix
Anwendungsszenarien
Zustand
Pseudo 2D Hidden Markov Modelle
HMM
Metazustand
Zustand
Metazustandsfolge
Zustandsfolge
Bildpunkt
Bildpunkt
• Kausales MRF
P(qxy = si | Q Φxy ) = P(qxy = si | Q Θxy )
• Markov Mesh
P(qxy = si | Q Υxy ) = P(qxy = si | Q Θxy )
• Unilaterales MRF P(qxy = si | Q Σxy ) = P(qxy = si | Q Θxy )

SPEZIELLE MUSTERANALYSESYSTEME Schrift

Transcrição

Documentos relacionados

NoSta-D Chat - Institut für deutsche Sprache und Linguistik

Digitalisierung der Industrie – Die plattform Industrie 4.0

Automatische Segmentierung der Gewebegrenzen - CEUR

Grammatische Kategorien und sprachliche Diversität - UK

Antrag auf Auskunft aus dem Verkehrszentralregister (Flensburg)

MAGISTRAT DER STADT WIEN - Bewerbungs

Pörtschach am Wörthersee - HOLIDAY LAND Reisebüro Werner

- Zahweh.ch

AUFNAHMEANTRAG Jugendfeuerwehr

PlagiarismFinder 2.0 - Friedrich-Schiller