Détection de «rivière» dans le texte

175

Au cours de l'échange de piles TeX, nous avons discuté de la façon de détecter les "rivières" dans les paragraphes de cette question .

Dans ce contexte, les rivières sont des bandes d'espaces blancs résultant d'un alignement accidentel d'espaces inter-mots dans le texte. Comme cela peut être assez dérangeant pour un lecteur, les mauvaises rivières sont considérées comme un symptôme d'une mauvaise typographie. Celui-ci est un exemple de texte avec des rivières, où deux rivières coulent en diagonale.

entrez la description de l'image ici

Il est intéressant de détecter ces rivières automatiquement, afin de les éviter (probablement par édition manuelle du texte). Raphink fait quelques progrès au niveau de TeX (qui ne connaît que les positions des glyphes et les cadres de sélection), mais je suis convaincu que le meilleur moyen de détecter les rivières est de traiter certaines images (les formes de glyphes étant très importantes et non disponibles pour TeX) . J'ai essayé diverses méthodes pour extraire les rivières de l'image ci-dessus, mais ma simple idée d'appliquer une petite quantité de flou ellipsoïdal ne semble pas suffisante. J'ai aussi essayé du radonLe filtrage basé sur la transformation de Hough, mais je n’ai rien obtenu non plus. Les rivières sont très visibles pour les circuits de détection des caractéristiques de l'œil humain / de la rétine / du cerveau et je penserais que cela pourrait se traduire par une sorte d'opération de filtrage, mais je ne parviens pas à le faire fonctionner. Des idées?

Pour être précis, je recherche une opération qui détectera les 2 rivières dans l’image ci-dessus, mais n’aura pas trop d’autres détections de faux positifs.

EDIT: endolith m'a demandé pourquoi je poursuivais une approche basée sur le traitement d'images, étant donné que dans TeX, nous avons accès aux positions des glyphes, aux espacements, etc. Ma raison de faire les choses dans l'autre sens est que la formedes glyphes peut avoir une incidence sur la perception d’une rivière et, au niveau du texte, il est très difficile d’envisager cette forme (qui dépend de la police, de la ligature, etc.). Pour un exemple de l'importance de la forme des glyphes, considérons les deux exemples suivants. La différence est que j'ai remplacé quelques glyphes par d'autres de la même largeur, de sorte qu'une analyse basée sur le texte prendrait en compte: eux aussi bien / mauvais. Notez cependant que les rivières dans le premier exemple sont bien pires que dans le second.

entrez la description de l'image ici

entrez la description de l'image ici

Lev Bishop
la source
5
+1 J'aime cette question. Ma première pensée est une transformation de Hough , mais elle nécessiterait probablement un traitement préalable. Peut-être un filtre de dilatation en premier.
datageist
Je suis surpris que la transformation de Radon n'ait pas fonctionné, en fait. Comment avez-vous fait?
endolith
@endolith: Rien de sophistiqué. Je me suis servi ImageLines[]de Mathematica, avec et sans prétraitement. J'imagine qu'il s'agit techniquement d'une transformation de Hough plutôt que de radon. Cela ne me surprendra pas si le prétraitement approprié (je n'ai pas essayé le filtre de dilatation suggéré par le datagraphe) et / ou les réglages de paramètres peuvent réussir ce travail.
Lev Bishop
Google Image Search pour les rivières montre également des rivières "sinueuses". Voulez-vous les trouver? cdn.ilovetypography.com/img/text-river1.gif
endolithe
@endolith J'imagine que je souhaite finalement reproduire le traitement du système visuel humain qui rend certaines configurations d'espaces distrayantes. Etant donné que cela peut se produire également dans les méandres des rivières, j'aimerais alors les attraper, bien que les lignes droites semblent poser plus de problèmes en général. Encore mieux serait un moyen de quantifier le «mal» des rivières d’une manière qui corresponde à leur degré de visibilité lors de la lecture du texte. Mais tout cela est très subjectif et difficile à quantifier. En premier lieu, capturer toutes les mauvaises rivières sans trop de faux positifs suffira.
Lev Bishop

Réponses:

135

J'y ai réfléchi un peu plus et je pense que ce qui suit devrait être assez stable. Notez que je me suis limité aux opérations morphologiques, car celles-ci devraient être disponibles dans toutes les bibliothèques de traitement d'image standard.

(1) Ouvrir une image avec un masque nPix par 1, nPix correspondant à la distance verticale entre les lettres.

#% 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));

entrez la description de l'image ici

(2) Ouvrez l’image avec un masque 1-sur-mPix pour éliminer tout ce qui est trop étroit pour être une rivière.

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

entrez la description de l'image ici

(3) Supprimez les "rivières et les lacs" horizontaux dus à l'espace entre les paragraphes ou à l'indentation. Pour cela, nous supprimons toutes les lignes qui sont toutes vraies et les ouvrons avec le masque nPix par 1 qui, à notre connaissance, n’affectera pas les rivières que nous avons trouvées précédemment.

Pour supprimer les lacs, nous pouvons utiliser un masque d’ouverture légèrement plus grand que nPix-by-nPix.

À ce stade, nous pouvons également éliminer tout ce qui est trop petit pour être une véritable rivière, c’est-à-dire tout ce qui couvre moins de surface que (nPix + 2) * (mPix + 2) * 4 (cela nous donnera environ 3 lignes). Le +2 est là parce que nous savons que tous les objets ont au moins nPix en hauteur et mPix en largeur, et nous voulons aller un peu au-dessus de cela.

%# 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);

entrez la description de l'image ici

(4) Si nous nous intéressons non seulement à la longueur, mais également à la largeur de la rivière, nous pouvons combiner la transformation de la distance avec le squelette.

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

   riversWithWidth = dt.*sk;

entrez la description de l'image ici (les couleurs correspondent à la largeur de la rivière (bien que la barre de couleur soit un facteur 2)

Vous pouvez maintenant obtenir la longueur approximative des rivières en comptant le nombre de pixels de chaque composant connecté et la largeur moyenne en faisant la moyenne de leurs valeurs de pixels.


Voici la même analyse appliquée à la deuxième image "pas de rivière":

entrez la description de l'image ici

Jonas
la source
Merci. J'ai Matlab donc je vais essayer ceci sur d'autres textes pour voir à quel point il sera robuste.
Lev Bishop
Le réintégrer dans TeX pourrait être un autre problème, à moins que nous ne puissions le transférer vers Lua.
ℝaphink
@ LevBishop: Je pense que je comprends un peu mieux la question. La nouvelle solution devrait être assez robuste.
Jonas
@levBishop: Une dernière mise à jour.
Jonas
1
@ LevBishop: Je viens de remarquer la deuxième image. Il s'avère que l'analyse basée sur la morphologie fait son travail.
Jonas
56

Dans Mathematica, en utilisant l'érosion et la transformation de Hough:

(*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}]

entrez la description de l'image ici

Editer répondre au commentaire de l'assistant

Si vous voulez vous débarrasser des lignes horizontales, faites plutôt quelque chose comme ceci (probablement quelqu'un pourrait le rendre plus simple):

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

entrez la description de l'image ici

Dr. belisarius
la source
1
Pourquoi ne pas se débarrasser de toutes les lignes horizontales? (+1)
Mr.Wizard
@Monsieur. Juste pour montrer que toutes les lignes sont détectées ...
Dr. belisarius
1
Cela ne fait pas partie du problème cependant, n'est-ce pas?
Mr.Wizard
@Monsieur. Edité à la demande
Dr. belisarius
4
@belisarius Le système de coordonnées utilisé dans la transformation de Hough a été modifié après la version 8.0.0 pour correspondre à celui de la transformation de Radon. Cela a changé le comportement d'ImageLines. Globalement, il s'agit d'une amélioration, bien que dans ce cas, on préfère le comportement précédent. Si vous ne voulez pas expérimenter avec des pics détections, vous pouvez changer le rapport d'aspect de l'image d'entrée pour être plus proche de 1 et d' obtenir un résultat similaire à 8.0.0: lines = ImageLines[ImageResize[#, {300, 300}], .6, "Segmented" -> True] & /@ i1;. Cela dit, pour ce problème, une approche morphologique semble plus robuste.
Matthias Odisio
29

Hmmm ... Je suppose que la transformation de Radon n'est pas si facile à extraire. (La transformation du radon fait essentiellement pivoter l'image tout en "regardant à travers". C'est le principe qui sous-tend les balayages CAT.) La transformation de votre image produit ce sinogramme, les "rivières" formant des pics lumineux encerclés:

entrez la description de l'image ici

Celui à une rotation de 70 degrés peut être vu assez clairement comme le pic à gauche de cette représentation d'une coupe sur l'axe horizontal:

entrez la description de l'image ici

Surtout si le texte était d'abord gaussien flou:

entrez la description de l'image ici

Mais je ne sais pas comment extraire de manière fiable ces pics du reste du bruit. Les extrémités supérieure et inférieure lumineuses du sinogramme représentent les "rivières" situées entre des lignes de texte horizontales, qui ne vous intéressent évidemment pas. Peut-être qu'une fonction de pondération par rapport à un angle accentue davantage les lignes verticales et minimise les lignes horizontales?

Une simple fonction de pondération en cosinus fonctionne bien sur cette image:

entrez la description de l'image ici

trouver le fleuve vertical à 90 degrés, ce qui correspond aux maxima globaux du sinogramme:

entrez la description de l'image ici

et sur cette image, trouver celle à 104 degrés, bien que le flou le rende plus précis:

entrez la description de l'image ici entrez la description de l'image ici

(La radon()fonction de SciPy est plutôt idiote , ou je mapperais ce sommet sur l'image d'origine sous la forme d'une ligne traversant le milieu de la rivière.)

Mais il ne trouve aucun des deux pics principaux dans le sinogramme pour votre image, après avoir brouillé et pondéré:

entrez la description de l'image ici

Ils sont là, mais ils sont dépassés par les éléments proches du sommet de la fonction de pondération. Avec une pondération et des ajustements appropriés, cette méthode pourrait probablement fonctionner, mais je ne suis pas sûre de ce que sont les ajustements appropriés. Cela dépend probablement aussi des propriétés des scans de la page. Peut-être que la pondération doit être dérivée de l'énergie globale de la tranche ou de quelque chose comme une normalisation.

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'
endolithe
la source
Et si vous deviez flouter d'abord avec une gaussienne asymétrique? Ie étroit dans la direction horizontale, large dans la direction verticale.
Jonas
@ Jonas: Cela aiderait probablement. Le problème principal est de sélectionner automatiquement les sommets de l'arrière-plan lorsque l'arrière-plan varie énormément avec la rotation. Un flou asymétrique pourrait lisser les bandes horizontales d'une ligne à l'autre.
endolith
Cela fonctionne bien pour détecter la rotation des lignes dans le texte, au moins: gist.github.com/endolith/334196bac1cac45a4893
endolith
16

J'ai formé un classifieur discriminant sur les pixels à l'aide de fonctions dérivées (jusqu'au 2e ordre) à différentes échelles.

Mes étiquettes:

Étiquetage

Prédiction sur l'image d'entraînement:

entrez la description de l'image ici

Prédiction sur les deux autres images:

entrez la description de l'image ici

entrez la description de l'image ici

Je suppose que cela semble prometteur et pourrait donner des résultats utilisables avec davantage de données de formation et peut-être des fonctionnalités plus intelligentes. Par contre, il ne m'a fallu que quelques minutes pour obtenir ces résultats. Vous pouvez reproduire les résultats vous-même à l'aide du logiciel open source ilastik . [Avertissement: je suis l'un des principaux développeurs.]

Bernhard Kausler
la source
2

(Désolé, cet article ne vient pas avec des démonstrations géniales.)

Si vous souhaitez utiliser les informations que TeX possède déjà (lettres et positions), vous pouvez classer manuellement les lettres et les paires de lettres comme "en pente" dans un sens ou dans un autre. Par exemple, "w" a des pentes de coin SW et SE, le combo "al" a une pente de coin NO, "k" a une pente de coin NE. (N'oubliez pas la ponctuation - une citation suivie d'une lettre qui remplit la moitié inférieure de la boîte à glyphes établit une belle pente; la citation suivie de q est particulièrement forte.)

Ensuite, recherchez les occurrences de pentes correspondantes sur les côtés opposés d'un espace - "w al" pour une rivière d'ouest en nord-est ou "k T" pour une rivière d'ouest en nord-est. Lorsque vous en trouvez un sur une ligne, voyez si un événement similaire se produit, décalé de manière appropriée vers la gauche ou la droite, sur les lignes ci-dessus / ci-dessous; quand vous en trouvez une course, il y a probablement une rivière.

Aussi, évidemment, il suffit de chercher des espaces empilés presque verticalement, pour les rivières verticales de plaine.

Vous pouvez obtenir un peu plus sophistiqué en mesurant la "force" de la pente: quelle part de la zone d’avancée est "vide" en raison de la pente et contribue ainsi à la largeur de la rivière. "w" est assez petit, car il ne dispose que d'un petit coin de sa boîte d'avance pour contribuer à la rivière, mais "V" est très fort. "b" est légèrement plus fort que "k"; la courbe plus douce donne un bord de rivière plus visuellement continu, ce qui le rend plus fort et plus large visuellement.

Xanthir
la source