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

175

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.

ingrese la descripción de la imagen aquí

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.

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Lev Bishop
fuente
55
+1 Me gusta esta pregunta. Mi primer pensamiento es una Transformación Hough , pero probablemente necesitaría algo de preprocesamiento. Tal vez un filtro de dilatación primero.
Datageist
Me sorprende que Radon transform no haya funcionado, en realidad. ¿Cómo lo hiciste?
Endolith
@endolith: Nada sofisticado. Utilicé ImageLines[]desde Mathematica, con y sin preprocesamiento. Supongo que esto técnicamente está usando una transformación Hough en lugar de Radon. No me sorprenderá si el preprocesamiento adecuado (no probé el filtro de dilatación sugerido de datageist) y / o la configuración de parámetros pueden hacer que esto funcione.
Lev Bishop
La Búsqueda de imágenes de Google para ríos también muestra ríos "sinuosos". ¿Quieres encontrar esos? cdn.ilovetypography.com/img/text-river1.gif
endolith
@endolith Supongo que, en última instancia, quiero replicar el procesamiento del sistema visual humano que distrae ciertas configuraciones de espacios. Como esto puede suceder también para los ríos serpenteantes, me gustaría atraparlos, aunque los rectos parecen ser más problemáticos en general. Aún mejor sería una forma de cuantificar la "maldad" de los ríos de una manera que corresponda a cuán fuertemente visibles son al leer el texto. Pero todo eso es muy subjetivo y difícil de cuantificar. En primer lugar, basta con atrapar realmente todos los ríos malos sin demasiados falsos positivos.
Lev Bishop

Respuestas:

135

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

ingrese la descripción de la imagen aquí

(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));

ingrese la descripción de la imagen aquí

(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);

ingrese la descripción de la imagen aquí

(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;

ingrese la descripción de la imagen aquí (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":

ingrese la descripción de la imagen aquí

Jonas
fuente
Gracias. Tengo Matlab, así que probaré esto en algunos otros textos para ver qué tan robusto será.
Lev Bishop
Integrarlo nuevamente en TeX podría ser otro problema, a menos que podamos trasladar eso a Lua de alguna manera.
phaphink
@LevBishop: Creo que entiendo el tema un poco mejor. La nueva solución debería ser bastante robusta.
Jonas
@levBishop: una actualización más.
Jonas
1
@LevBishop: Acabo de notar la segunda imagen. Resulta que el análisis basado en la morfología hace su trabajo.
Jonas
56

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

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí

Dr. belisario
fuente
1
¿Por qué no deshacerse de todas las líneas horizontales? (+1)
Mr.Wizard
@Señor. Solo para mostrar que se están detectando todas las líneas ...
Dr. belisarius
1
Sin embargo, eso no es parte del problema, ¿verdad?
Mr.Wizard
@Señor. Editado según lo solicitado
Dr. belisarius
44
@belisarius El sistema de coordenadas utilizado en la transformación de Hough cambió después de 8.0.0 para coincidir con el de la transformación de Radón. Esto a su vez ha cambiado el comportamiento de ImageLines. En general, esto es una mejora, aunque en este caso uno preferiría el comportamiento anterior. Si no desea experimentar con detecciones pico, se puede cambiar la relación de aspecto de la imagen de entrada para estar más cerca de 1 y obtener un resultado similar al 8.0.0: lines = ImageLines[ImageResize[#, {300, 300}], .6, "Segmented" -> True] & /@ i1;. Dicho todo esto, para este problema, un enfoque morfológico parece más robusto.
Matthias Odisio
29

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:

ingrese la descripción de la imagen aquí

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:

ingrese la descripción de la imagen aquí

Especialmente si el texto era gaussiano borroso primero:

ingrese la descripción de la imagen aquí

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:

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

(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:

ingrese la descripción de la imagen aquí

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'
endolito
fuente
¿Qué pasaría si primero se empañara con un Gaussiano asimétrico? Es decir, estrecho en dirección horizontal, ancho en dirección vertical.
Jonas
@Jonas: Eso probablemente ayudaría. El principal problema es seleccionar automáticamente los picos del fondo cuando el fondo varía mucho con la rotación. El desenfoque asimétrico podría suavizar las franjas horizontales de línea a línea.
endolito el
Esto funciona bien para detectar la rotación de líneas en el texto, al menos: gist.github.com/endolith/334196bac1cac45a4893
endolith
16

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

Mis etiquetas:

Etiquetado

Predicción sobre la imagen de entrenamiento:

ingrese la descripción de la imagen aquí

Predicción sobre las otras dos imágenes:

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

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.]

Bernhard Kausler
fuente
2

(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.

Xanthir
fuente