Flusserkennung im Text

175

Während des TeX-Stack-Austauschs haben wir diskutiert, wie "Flüsse" in Absätzen in dieser Frage erkannt werden können .

In diesem Zusammenhang sind Flüsse Leerräume, die sich aus der zufälligen Ausrichtung von Zwischenwörtern im Text ergeben. Da dies für einen Leser ziemlich ablenkend sein kann, werden schlechte Flüsse als Symptom für eine schlechte Typografie angesehen. Ein Beispiel für einen Text mit Flüssen ist dieser, bei dem zwei Flüsse diagonal fließen.

Bildbeschreibung hier eingeben

Es besteht ein Interesse daran, diese Flüsse automatisch zu erkennen, damit sie vermieden werden können (wahrscheinlich durch manuelle Bearbeitung des Textes). Raphink macht einige Fortschritte auf der TeX-Ebene (die nur Glyphenpositionen und Begrenzungsrahmen kennt), aber ich bin zuversichtlich, dass der beste Weg zum Erkennen von Flüssen eine Bildverarbeitung ist (da Glyphenformen sehr wichtig sind und TeX nicht zur Verfügung stehen). . Ich habe verschiedene Methoden ausprobiert, um die Flüsse aus dem obigen Bild zu extrahieren, aber meine einfache Idee, ein kleines Maß an ellipsoidaler Unschärfe anzuwenden, scheint nicht gut genug zu sein. Ich habe auch Radon probiertObwohl auf Transformationen basierendes Filtern, kam ich damit auch nicht weiter. Die Flüsse sind für die Funktionserkennungskreise des menschlichen Auges / der Netzhaut / des Gehirns sehr gut sichtbar, und irgendwie würde ich denken, dass dies in eine Art Filteroperation übersetzt werden könnte, aber ich bin nicht in der Lage, es zum Laufen zu bringen. Irgendwelche Ideen?

Um genau zu sein, suche ich nach einer Operation, die die beiden Flüsse im obigen Bild erkennt, aber nicht zu viele andere falsch positive Erkennungen aufweist.

BEARBEITEN: Endolith fragte, warum ich einen bildverarbeitungsbasierten Ansatz verfolge, da wir in TeX Zugriff auf die Glyphenpositionen, Abstände usw. haben und es möglicherweise viel schneller und zuverlässiger ist, einen Algorithmus zu verwenden, der den tatsächlichen Text untersucht. Mein Grund, Dinge anders zu machen, ist die FormDie Anzahl der Glyphen kann sich auf die Wahrnehmbarkeit eines Flusses auswirken. Auf Textebene ist es sehr schwierig, diese Form zu berücksichtigen (abhängig von der Schriftart, der Ligatur usw.). Betrachten Sie als Beispiel, wie wichtig die Form der Glyphen sein kann, die folgenden zwei Beispiele, bei denen der Unterschied darin besteht, dass ich einige Glyphen durch andere mit fast der gleichen Breite ersetzt habe, sodass eine textbasierte Analyse dies berücksichtigen würde sie gleich gut / schlecht. Beachten Sie jedoch, dass die Flüsse im ersten Beispiel viel schlechter sind als im zweiten.

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

Lev Bischof
quelle
5
+1 Ich mag diese Frage. Mein erster Gedanke ist eine Hough-Transformation , aber sie müsste wahrscheinlich vorverarbeitet werden. Vielleicht zuerst einen Dilatationsfilter .
Datageist
Ich bin überrascht, dass die Radon-Transformation nicht funktioniert hat. Wie hast du es gemacht?
Endolith
@ Endolith: Nichts anspruchsvolles. Ich habe ImageLines[]Mathematica mit und ohne Vorverarbeitung verwendet. Ich denke, dies ist technisch eher eine Hough-Transformation als eine Radon-Transformation. Es wird mich nicht wundern, wenn die ordnungsgemäße Vorverarbeitung (ich habe den vom Datageist vorgeschlagenen Dilatationsfilter nicht ausprobiert) und / oder Parametereinstellungen dazu beitragen, dass dies funktioniert.
Lev Bishop
Google Image Search für Flüsse zeigt auch "gewundene" Flüsse. Möchtest du die finden? cdn.ilovetypography.com/img/text-river1.gif
endolith
@endolith Ich denke, ich möchte letztendlich die Verarbeitung des menschlichen visuellen Systems replizieren, die bestimmte Konfigurationen von Räumen ablenkt. Da dies auch bei mäandrierenden Flüssen vorkommen kann, möchte ich diese gerne fangen, obwohl die geraden im Allgemeinen eher ein Problem zu sein scheinen. Noch besser wäre es, die "Schlechtigkeit" von Flüssen auf eine Weise zu quantifizieren, die der Sichtbarkeit beim Lesen des Textes entspricht. Aber das ist alles sehr subjektiv und schwer zu quantifizieren. Zuallererst reicht es aus, wirklich alle schlechten Flüsse zu fangen, ohne zu viele Fehlalarme.
Lev Bishop

Antworten:

135

Ich habe darüber noch etwas nachgedacht und denke, dass das Folgende ziemlich stabil sein sollte. Beachten Sie, dass ich mich auf morphologische Operationen beschränkt habe, da diese in jeder Standard-Bildverarbeitungsbibliothek verfügbar sein sollten.

(1) Öffnen Sie das Bild mit einer nPix-by-1-Maske, wobei nPix der vertikale Abstand zwischen Buchstaben ist

#% read image
img = rgb2gray('http://i.stack.imgur.com/4ShOW.png');

%# threshold and open with a rectangle
%# that is roughly letter sized
bwImg = img > 200; %# threshold of 200 is better than 128

opImg = imopen(bwImg,ones(13,1));

Bildbeschreibung hier eingeben

(2) Öffnen Sie das Bild mit einer 1-mal-mPix-Maske, um alles zu entfernen, was zu schmal ist, um ein Fluss zu sein.

opImg = imopen(opImg,ones(1,5));

Bildbeschreibung hier eingeben

(3) Entfernen Sie horizontale "Flüsse und Seen", die durch Abstände zwischen Absätzen oder Einrückungen entstehen. Dazu entfernen wir alle Zeilen, die alle wahr sind, und öffnen sie mit der nPix-by-1-Maske, von der wir wissen, dass sie die zuvor gefundenen Flüsse nicht beeinflusst.

Zum Entfernen von Seen können wir eine Öffnungsmaske verwenden, die etwas größer als nPix-by-nPix ist.

In diesem Schritt können wir auch alles wegwerfen, was zu klein ist, um ein echter Fluss zu sein, dh alles, was weniger Fläche als (nPix + 2) * (mPix + 2) * 4 abdeckt (das ergibt ~ 3 Linien). Die +2 ist da, weil wir wissen, dass alle Objekte mindestens nPix in der Höhe und mPix in der Breite haben, und wir wollen ein wenig darüber hinausgehen.

%# horizontal river: just look for rows that are all true
opImg(all(opImg,2),:) = false;
%# open with line spacing (nPix)
opImg = imopen(opImg,ones(13,1));

%# remove lakes with nPix+2
opImg = opImg & ~imopen(opImg,ones(15,15)); 

%# remove small fry
opImg = bwareaopen(opImg,7*15*4);

Bildbeschreibung hier eingeben

(4) Wenn wir nicht nur an der Länge, sondern auch an der Breite des Flusses interessiert sind, können wir Distanztransformation mit Skelett kombinieren.

   dt = bwdist(~opImg);
   sk = bwmorph(opImg,'skel',inf);
   %# prune the skeleton a bit to remove branches
   sk = bwmorph(sk,'spur',7);

   riversWithWidth = dt.*sk;

Bildbeschreibung hier eingeben (Farben entsprechen der Breite des Flusses (obwohl der Farbbalken um den Faktor 2 abweicht)

Jetzt können Sie die ungefähre Länge der Flüsse ermitteln, indem Sie die Anzahl der Pixel in jeder verbundenen Komponente und die durchschnittliche Breite durch Mitteln der Pixelwerte berechnen.


Hier ist genau die gleiche Analyse, die auf das zweite "No-River" -Bild angewendet wurde:

Bildbeschreibung hier eingeben

Jonas
quelle
Vielen Dank. Ich habe Matlab, also werde ich es an einigen anderen Texten ausprobieren, um zu sehen, wie robust es sein wird.
Lev Bishop
Es könnte ein weiteres Problem sein, es wieder in TeX zu integrieren, es sei denn, wir können das irgendwie nach Lua portieren.
ℝaphink
@ LevBishop: Ich denke, ich verstehe das Problem ein bisschen besser. Die neue Lösung sollte ziemlich robust sein.
Jonas
@levBishop: Noch ein Update.
Jonas
1
@LevBishop: Hab gerade das zweite Bild gesehen. Es stellt sich heraus, dass die morphologiebasierte Analyse ihre Aufgabe erfüllt.
Jonas
56

In Mathematica mit Erosion und Hough-Transformation:

(*Get Your Images*)
i = Import /@ {"http://i.stack.imgur.com/4ShOW.png", 
               "http://i.stack.imgur.com/5UQwb.png"};

(*Erode and binarize*)
i1 = Binarize /@ (Erosion[#, 2] & /@ i);

(*Hough transform*)
lines = ImageLines[#, .5, "Segmented" -> True] & /@ i1;

(*Ready, show them*)
Show[#[[1]],Graphics[{Thick,Orange, Line /@ #[[2]]}]] & /@ Transpose[{i, lines}]

Bildbeschreibung hier eingeben

Bearbeiten Sie den Kommentar von Beantwortung von Mr. Wizard

Wenn Sie die horizontalen Linien loswerden möchten, gehen Sie stattdessen wie folgt vor (wahrscheinlich könnte es jemand einfacher machen):

Show[#[[1]], Graphics[{Thick, Orange, Line /@ #[[2]]}]] & /@ 
 Transpose[{i, Select[Flatten[#, 1], Chop@Last@(Subtract @@ #) != 0 &] & /@ lines}]

Bildbeschreibung hier eingeben

Dr. belisarius
quelle
1
Warum nicht alle horizontalen Linien loswerden? (+1)
Mr.Wizard
@Herr. Nur um zu zeigen, dass alle Linien erkannt werden ...
Dr. Belisarius
1
Das ist jedoch nicht Teil des Problems, oder?
Mr.Wizard
@Herr. Bearbeitet wie gewünscht
Dr. belisarius
4
@belisarius Das in der Hough-Transformation verwendete Koordinatensystem hat sich nach 8.0.0 geändert und stimmt mit dem der Radon-Transformation überein. Dies hat wiederum das Verhalten von ImageLines geändert. Insgesamt ist dies eine Verbesserung, obwohl man in diesem Fall das vorherige Verhalten vorziehen würde. Wenn Sie nicht mit Spitzenerfassungen experimentieren möchten, können Sie das Seitenverhältnis des Eingangsbildes ändern zu 1 näher zu sein und ein ähnliches Ergebnis wie 8.0.0 erhalten: lines = ImageLines[ImageResize[#, {300, 300}], .6, "Segmented" -> True] & /@ i1;. Trotzdem scheint ein morphologischer Ansatz für dieses Problem robuster zu sein.
Matthias Odisio
29

Hmmm ... Ich denke, Radon-Transformation ist nicht so einfach zu extrahieren. (Die Radon-Transformation dreht das Bild im Grunde genommen, während Sie es von der Kante aus "durchschauen". Dies ist das Prinzip von CAT-Scans.) Die Transformation Ihres Bildes erzeugt dieses Sinogramm, wobei die "Flüsse" helle Spitzen bilden, die eingekreist sind:

Bildbeschreibung hier eingeben

Die bei einer Drehung um 70 Grad ist ziemlich deutlich als die Spitze auf der linken Seite dieses Diagramms eines Schnitts entlang der horizontalen Achse zu sehen:

Bildbeschreibung hier eingeben

Vor allem, wenn der Text zuerst nach Gauß verschwommen war:

Bildbeschreibung hier eingeben

Ich bin mir jedoch nicht sicher, wie ich diese Peaks zuverlässig aus dem Rest des Rauschens extrahieren kann. Die hellen oberen und unteren Enden des Sinogramms stellen die "Flüsse" zwischen horizontalen Textzeilen dar, die Sie offensichtlich nicht interessieren. Vielleicht eine Gewichtungsfunktion gegen den Winkel, die mehr vertikale Linien betont und die horizontalen minimiert?

Eine einfache Cosinus-Gewichtungsfunktion funktioniert für dieses Bild gut:

Bildbeschreibung hier eingeben

Finden des vertikalen Flusses bei 90 Grad, welches das globale Maximum im Sinogramm ist:

Bildbeschreibung hier eingeben

und auf diesem Bild ist es genauer, wenn man das Bild bei 104 Grad findet, obwohl es zuerst verwischt wird:

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

(SciPys radon()Funktion ist irgendwie dumm , oder ich würde diesen Peak wieder als Linie durch die Mitte des Flusses auf das Originalbild abbilden.)

Nach dem Verwischen und Gewichten wird jedoch keiner der beiden Hauptpeaks im Sinogramm für Ihr Bild gefunden:

Bildbeschreibung hier eingeben

Sie sind da, aber sie sind überwältigt von dem Zeug in der Nähe der mittleren Spitze der Wichtungsfunktion. Mit der richtigen Gewichtung und Tweaking wahrscheinlich diese Methode könnte funktionieren, aber ich bin nicht sicher , was die richtigen Kniffe sind. Dies hängt wahrscheinlich auch von den Eigenschaften der Scans der Seite ab. Vielleicht muss die Gewichtung von der Gesamtenergie in der Scheibe oder so etwas wie einer Normalisierung abgeleitet werden.

from pylab import *
from scipy.misc import radon
import Image

filename = 'rivers.png'
I = asarray(Image.open(filename).convert('L').rotate(90))

# Do the radon transform and display the result
a = radon(I, theta = mgrid[0:180])

# Remove offset
a = a - min(a.flat)

# Weight it to emphasize vertical lines
b = arange(shape(a)[1]) #
d = (0.5-0.5*cos(b*pi/90))*a

figure()
imshow(d.T)
gray()
show()

# Find the global maximum, plot it, print it
peak_x, peak_y = unravel_index(argmax(d),shape(d))
plot(peak_x, peak_y,'ro')
print len(d)- peak_x, 'pixels', peak_y, 'degrees'
Endolith
quelle
Was wäre, wenn Sie zuerst mit einem asymmetrischen Gaußschen verwischen würden? Dh schmal in horizontaler Richtung, breit in vertikaler Richtung.
Jonas
@Jonas: Das würde wahrscheinlich helfen. Das Hauptproblem besteht darin, die Peaks automatisch aus dem Hintergrund zu ziehen, wenn sich der Hintergrund mit der Drehung so stark ändert. Durch asymmetrisches Verwischen können die horizontalen Streifen von Linie zu Linie geglättet werden.
Endolith
Dies funktioniert gut, um die Drehung von Linien im Text zu erkennen, zumindest: gist.github.com/endolith/334196bac1cac45a4893
Endolith
16

Ich habe einen Unterscheidungsklassifizierer für die Pixel unter Verwendung von abgeleiteten Merkmalen (bis zur 2. Ordnung) auf verschiedenen Skalen trainiert.

Meine Labels:

Beschriftung

Vorhersage zum Trainingsbild:

Bildbeschreibung hier eingeben

Vorhersage auf den beiden anderen Bildern:

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

Ich denke, dies sieht vielversprechend aus und könnte bei mehr Trainingsdaten und vielleicht intelligenteren Funktionen zu brauchbaren Ergebnissen führen. Andererseits habe ich nur wenige Minuten gebraucht, um diese Ergebnisse zu erzielen. Sie können die Ergebnisse selbst reproduzieren, indem Sie die Open-Source-Software ilastik verwenden . [Haftungsausschluss: Ich bin einer der Hauptentwickler.]

Bernhard Kausler
quelle
2

(Dieser Beitrag enthält leider keine großartigen Demonstrationen.)

Wenn Sie mit Informationen arbeiten möchten, die TeX bereits hat (Buchstaben und Positionen), können Sie Buchstaben und Buchstabenpaare manuell als in die eine oder andere Richtung geneigt klassifizieren. Beispielsweise hat "w" SW- und SE-Eckneigungen, die "al" -Kombination hat eine NW-Eckneigung, "k" hat eine NE-Eckneigung. (Interpunktion nicht vergessen - ein Zitat, gefolgt von einem Buchstaben, der die untere Hälfte des Glyphenfelds ausfüllt, erzeugt eine schöne Steigung; Zitat gefolgt von q ist besonders stark.)

Suchen Sie dann nach Vorkommen entsprechender Steigungen auf gegenüberliegenden Seiten eines Raums - "w al" für einen Fluss von SW nach NE oder "k T" für einen Fluss von NW nach SE. Wenn Sie einen in einer Zeile finden, prüfen Sie, ob ein ähnlicher Fehler auftritt, der in den Zeilen darüber / darunter entsprechend nach links oder rechts verschoben ist. Wenn Sie einen Lauf von diesen finden, gibt es wahrscheinlich einen Fluss.

Achten Sie auch einfach auf fast senkrecht gestapelte Stellen, auf die senkrechten Flüsse.

Wenn Sie die "Stärke" des Abhangs messen, können Sie ein wenig differenzierter werden: Wie viel des Vorauskastens ist aufgrund des Abhangs "leer" und trägt somit zur Breite des Flusses bei. "w" ist ziemlich klein, da es nur eine kleine Ecke seines Vorschubkastens hat, um zum Fluss beizutragen, aber "V" ist sehr stark. "b" ist etwas stärker als "k"; Die sanftere Kurve sorgt für einen optisch kontinuierlichen Flussrand, der stärker und optisch breiter wird.

Xanthir
quelle