Detección de "río" en el texto

En el intercambio de pila de TeX, hemos estado discutiendo cómo detectar "ríos" en los párrafos de esta pregunta .

En este contexto, los ríos son bandas de espacios en blanco que resultan de la alineación accidental de espacios entre palabras en el texto. Dado que esto puede distraer bastante al lector, los ríos malos se consideran un síntoma de una tipografía pobre. Un ejemplo de texto con ríos es este, donde hay dos ríos que fluyen en diagonal.

Hay interés en detectar estos ríos automáticamente, de modo que puedan evitarse (probablemente mediante la edición manual del texto). Raphink está progresando en el nivel de TeX (que solo conoce las posiciones de los glifos y los cuadros delimitadores), pero estoy seguro de que la mejor manera de detectar ríos es con algo de procesamiento de imágenes (ya que las formas de los glifos son muy importantes y no están disponibles para TeX) . He intentado varias formas de extraer los ríos de la imagen de arriba, pero mi simple idea de aplicar una pequeña cantidad de desenfoque elipsoidal no parece ser lo suficientemente buena. También probé un poco de radónHough transformado basado en filtrado, pero tampoco llegué a ninguna parte con esos. Los ríos son muy visibles para los circuitos de detección de características del ojo humano / retina / cerebro y de alguna manera pensaría que esto podría traducirse en algún tipo de operación de filtrado, pero no puedo hacer que funcione. ¿Algunas ideas?

Para ser específicos, estoy buscando alguna operación que detecte los 2 ríos en la imagen de arriba, pero no tenga demasiadas detecciones de falsos positivos.

EDITAR: endolith preguntó por qué estoy buscando un enfoque basado en el procesamiento de imágenes dado que en TeX tenemos acceso a las posiciones de glifos, espacios, etc., y podría ser mucho más rápido y más confiable usar un algoritmo que examine el texto real. Mi razón para hacer las cosas al revés es que la formade los glifos puede afectar cuán notable es un río, y a nivel de texto es muy difícil considerar esta forma (que depende de la fuente, la ligadura, etc.). Para ver un ejemplo de cómo la forma de los glifos puede ser importante, considere los siguientes dos ejemplos, donde la diferencia entre ellos es que he reemplazado algunos glifos por otros de casi el mismo ancho, de modo que un análisis basado en texto consideraría ellos igualmente buenos / malos. Tenga en cuenta, sin embargo, que los ríos en el primer ejemplo son mucho peores que en el segundo.

He pensado en esto un poco más y creo que lo siguiente debería ser bastante estable. Tenga en cuenta que me he limitado a las operaciones morfológicas, porque estas deberían estar disponibles en cualquier biblioteca estándar de procesamiento de imágenes.

(1) Imagen abierta con una máscara nPix-by-1, donde nPix es aproximadamente la distancia vertical entre letras

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

(2) Abra la imagen con una máscara de 1 por mPix para eliminar lo que sea demasiado estrecho para ser un río.

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

(3) Elimine los "ríos y lagos" horizontales que se deben al espacio entre párrafos o sangría. Para esto, eliminamos todas las filas que son todas verdaderas y las abrimos con la máscara nPix-by-1 que sabemos que no afectará a los ríos que hemos encontrado anteriormente.

Para eliminar los lagos, podemos usar una máscara de apertura que sea un poco más grande que nPix-by-nPix.

En este paso, también podemos tirar todo lo que es demasiado pequeño para ser un río real, es decir, todo lo que cubre menos área que (nPix + 2) * (mPix + 2) * 4 (que nos dará ~ 3 líneas). El +2 está ahí porque sabemos que todos los objetos tienen al menos nPix de altura y mPix de ancho, y queremos ir un poco por encima de eso.

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

(4) Si estamos interesados ​​no solo en la longitud, sino también en el ancho del río, podemos combinar la transformación de distancia con el esqueleto.

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

   riversWithWidth = dt.*sk;

(los colores corresponden al ancho del río (aunque la barra de color está desactivada por un factor de 2)

Ahora puede obtener la longitud aproximada de los ríos contando el número de píxeles en cada componente conectado y el ancho promedio promediando sus valores de píxeles.

Aquí está el mismo análisis exacto aplicado a la segunda imagen "sin río":

En Mathematica, usando la erosión y la transformación 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}]

Editar Respondiendo el comentario del Sr. Wizard

Si quiere deshacerse de las líneas horizontales, simplemente haga algo como esto (probablemente alguien podría simplificarlo):

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

Hmmm ... supongo que la transformación de radón no es tan fácil de extraer. (La transformación de radón básicamente gira la imagen mientras "mira a través de ella" de borde. Es el principio detrás de los escáneres CAT.) La transformación de su imagen produce este sinograma, con los "ríos" formando picos brillantes, que están encerrados en un círculo:

El que tiene una rotación de 70 grados se puede ver con bastante claridad como el pico a la izquierda de esta gráfica de un corte a lo largo del eje horizontal:

Especialmente si el texto era gaussiano borroso primero:

Pero no estoy seguro de cómo extraer de manera confiable estos picos del resto del ruido. Los extremos superior e inferior brillantes del sinograma representan los "ríos" entre las líneas horizontales de texto, que obviamente no le importan. ¿Quizás una función de ponderación vs ángulo que enfatiza más líneas verticales y minimiza las horizontales?

Una función de ponderación de coseno simple funciona bien en esta imagen:

encontrar el río vertical a 90 grados, que es el máximo global en el sinograma:

y en esta imagen, encontrar el que está a 104 grados, aunque el desenfoque primero lo hace más preciso:

(La radon()función de SciPy es un poco tonta , o mapearía este pico de nuevo en la imagen original como una línea que atraviesa el medio del río).

Pero no encuentra ninguno de los dos picos principales en el sinograma para su imagen, después de difuminar y ponderar:

Están allí, pero están abrumados por las cosas cerca del pico medio de la función de ponderación. Con la ponderación y los ajustes correctos, este método probablemente podría funcionar, pero no estoy seguro de cuáles son los ajustes correctos. Probablemente también depende de las propiedades de los escaneos de la página. Tal vez la ponderación debe derivarse de la energía general en el segmento o algo así, como una normalización.

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'

Entrené un clasificador discriminativo en los píxeles usando características derivadas (hasta el segundo orden) en diferentes escalas.

Mis etiquetas:

Predicción sobre la imagen de entrenamiento:

Predicción sobre las otras dos imágenes:

Supongo que esto parece prometedor y podría arrojar resultados utilizables dada la mayor cantidad de datos de capacitación y quizás características más inteligentes. Por otro lado, me tomó solo unos minutos obtener estos resultados. Puede reproducir los resultados usted mismo utilizando el software de código abierto ilastik . [Descargo de responsabilidad: soy uno de los principales desarrolladores.]

(Lo siento, esta publicación no viene con demostraciones increíbles).

Si desea trabajar con la información que TeX ya tiene (letras y posiciones), puede clasificar manualmente las letras y los pares de letras como "inclinadas" en una dirección u otra. Por ejemplo, "w" tiene pendientes de esquina SW y SE, el combo "al" tiene una pendiente de esquina NW, "k" tiene una pendiente de esquina NE. (No olvide la puntuación: una cita seguida de una letra que llena la mitad inferior del cuadro de glifos establece una pendiente agradable; la cita seguida de q es particularmente fuerte).

Luego, busque las ocurrencias de las pendientes correspondientes en lados opuestos de un espacio: "w al" para un río de SW a NE o "k T" para un río de NO a SE. Cuando encuentre uno en una línea, vea si ocurre uno similar, debidamente desplazado hacia la izquierda o hacia la derecha, en las líneas arriba / abajo; cuando encuentres una serie de estos, probablemente haya un río.

Además, obviamente, solo busque espacios apilados casi verticalmente, para los ríos verticales lisos.

Puede ser un poco más sofisticado midiendo la "fuerza" de la pendiente: cuánto de la casilla de avance está "vacía" debido a la pendiente y, por lo tanto, contribuye al ancho del río. "w" es bastante pequeño, ya que solo tiene una pequeña esquina de su casilla de avance para contribuir al río, pero "V" es muy fuerte. "b" es ligeramente más fuerte que "k"; la curva más suave da un borde de río más visualmente continuo, haciéndolo más fuerte y visualmente más ancho.