Detecção de "rio" em texto


175

Na troca de pilha TeX, discutimos como detectar "rios" nos parágrafos desta pergunta .

Nesse contexto, rios são faixas de espaço em branco que resultam do alinhamento acidental de espaços entre palavras no texto. Como isso pode ser bastante perturbador para um leitor, rios ruins são considerados um sintoma de tipografia ruim. Um exemplo de texto com rios é este, onde existem dois rios fluindo na diagonal.

insira a descrição da imagem aqui

Há interesse em detectar esses rios automaticamente, para que possam ser evitados (provavelmente pela edição manual do texto). O Raphink está fazendo algum progresso no nível TeX (que apenas conhece as posições dos glifos e as caixas delimitadoras), mas sinto-me confiante de que a melhor maneira de detectar rios é com algum processamento de imagem (já que as formas dos glifos são muito importantes e não estão disponíveis para o TeX) . Eu tentei várias maneiras de extrair os rios da imagem acima, mas minha ideia simples de aplicar uma pequena quantidade de desfoque elipsoidal não parece ser boa o suficiente. Eu também tentei alguns RadonFiltragem baseada em transformação, mas também não cheguei a lugar nenhum. Os rios são muito visíveis aos circuitos de detecção de características do olho humano / retina / cérebro e, de alguma forma, acho que isso poderia ser traduzido para algum tipo de operação de filtragem, mas não consigo fazê-lo funcionar. Alguma ideia?

Para ser específico, estou procurando alguma operação que detecte os 2 rios na imagem acima, mas não tenha muitas outras detecções de falsos positivos.

EDIT: endolith perguntou por que estou adotando uma abordagem baseada no processamento de imagens, uma vez que no TeX temos acesso às posições de glifos, espaçamentos etc., e pode ser muito mais rápido e confiável usar um algoritmo que examina o texto real. Minha razão para fazer as coisas de outra maneira é que a formaUm dos glifos pode afetar o grau de visibilidade de um rio e, no nível do texto, é muito difícil considerar essa forma (que depende da fonte, da ligadura etc.). Para um exemplo de como a forma dos glifos pode ser importante, considere os dois exemplos a seguir, onde a diferença entre eles é que substituí alguns glifos por outros quase da mesma largura, para que uma análise baseada em texto considere eles igualmente bons / ruins. Note, no entanto, que os rios no primeiro exemplo são muito piores que no segundo.

insira a descrição da imagem aqui

insira a descrição da imagem aqui


5
+1 Gostei desta pergunta. Meu primeiro pensamento é uma transformação Hough , mas provavelmente precisaria de algum pré-processamento. Talvez um filtro de dilatação primeiro.
datageist

Estou surpreso que a transformação Radon não tenha funcionado, na verdade. Como você fez isso?
endolith

@ endolith: Nada sofisticado. Eu usei ImageLines[]no Mathematica, com e sem algum pré-processamento. Eu acho que isso é tecnicamente usando uma transformação Hough ao invés de Radon. Não ficarei surpreso se o pré-processamento adequado (não tentei o filtro de dilatação sugerido pelo datagrama) e / ou as configurações de parâmetros puderem fazer esse trabalho.
Lev Bishop

A Pesquisa de imagens do Google por rios também mostra rios "sinuosos". Você quer encontrar isso? cdn.ilovetypography.com/img/text-river1.gif
endolith

@ endolith Acho que, em última análise, quero replicar o processamento do sistema visual humano que faz com que certas configurações de espaços sejam perturbadoras. Como isso também pode acontecer nos rios sinuosos, eu gostaria de pegá-los, embora os mais retos pareçam ser mais um problema em geral. Melhor ainda, seria uma maneira de quantificar a "maldade" dos rios de uma maneira que corresponda ao quão fortemente visíveis eles são ao ler o texto. Mas tudo isso é muito subjetivo e difícil de quantificar. Em primeiro lugar, basta pegar realmente todos os rios ruins sem muitos falsos positivos.
Lev Bishop

Respostas:


135

Pensei um pouco mais sobre isso e acho que o seguinte deve ser bastante estável. Observe que me limitei às operações morfológicas, porque elas devem estar disponíveis em qualquer biblioteca de processamento de imagens padrão.

(1) Abra a imagem com uma máscara nPix por 1, em que nPix é a distância vertical entre as 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));

insira a descrição da imagem aqui

(2) Abra a imagem com uma máscara de 1 por mPix para eliminar o que for muito estreito para ser um rio.

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

insira a descrição da imagem aqui

(3) Remova os "rios e lagos" horizontais que são devidos ao espaço entre parágrafos ou recuo. Para isso, removemos todas as linhas verdadeiras e abrimos com a máscara nPix por 1 que sabemos que não afetará os rios que encontramos anteriormente.

Para remover lagos, podemos usar uma máscara de abertura um pouco maior que nPix por nPix.

Nesta etapa, também podemos jogar fora tudo que é pequeno demais para ser um rio real, ou seja, tudo que cobre menos área que (nPix + 2) * (mPix + 2) * 4 (que nos dará ~ 3 linhas). O +2 está lá porque sabemos que todos os objetos têm pelo menos nPix de altura e mPix de largura, e queremos ir um pouco acima disso.

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

insira a descrição da imagem aqui

(4) Se estivermos interessados ​​não apenas no comprimento, mas também na largura do rio, podemos combinar a transformação de distância com o 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;

insira a descrição da imagem aqui (as cores correspondem à largura do rio (embora a barra de cores esteja desativada por um fator de 2)

Agora você pode obter o comprimento aproximado dos rios contando o número de pixels em cada componente conectado e a largura média calculando a média dos valores de pixels.


Aqui está exatamente a mesma análise aplicada à segunda imagem "no-river":

insira a descrição da imagem aqui


Obrigado. Eu tenho o Matlab, então tentarei isso em outros textos para ver o quão robusto será.
Lev Bishop

Integrá-lo de volta ao TeX pode ser outro problema, a menos que possamos portá-lo para Lua de alguma forma.
precisa saber é o seguinte

@ Levevishop: Acho que entendi um pouco melhor a questão. A nova solução deve ser bastante robusta.
Jonas

@levBishop: Mais uma atualização.
Jonas #

1
@ Levevishop: Acabei de notar a segunda imagem. Acontece que a análise baseada em morfologia faz seu trabalho.
Jonas

56

No Mathematica, usando erosão e transformada 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}]

insira a descrição da imagem aqui

Editar Respondendo ao comentário do Sr. Wizard

Se você quiser se livrar das linhas horizontais, faça algo assim (provavelmente alguém poderia simplificá-lo):

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

insira a descrição da imagem aqui


1
Por que não se livrar de todas as linhas horizontais? (+1)
Mr.Wizard

@Sr. Só para mostrar todas as linhas estão sendo detectados ...
Dr. belisarius

1
Isso não faz parte do problema, não é?
Mr.Wizard

@Sr. Editado como solicitado
Dr. belisarius

4
@belisarius O sistema de coordenadas usado na transformação Hough foi alterado após 8.0.0 para corresponder ao sistema da transformação Radon. Por sua vez, isso mudou o comportamento do ImageLines. No geral, isso é uma melhoria, embora, neste caso, alguém prefira o comportamento anterior. Se você não quiser experimentar com detecções de pico, você pode alterar a razão da imagem de entrada para estar mais perto de 1 e obter um resultado semelhante ao 8.0.0: lines = ImageLines[ImageResize[#, {300, 300}], .6, "Segmented" -> True] & /@ i1;. Tudo dito, para esse problema, uma abordagem morfológica parece mais robusta.
Matthias Odisio

29

Hummm ... acho que a transformação de radônio não é tão fácil de extrair. (A transformação de radônio basicamente gira a imagem enquanto "olha através dela" de ponta a ponta. É o princípio por trás das tomografias.) A transformação de sua imagem produz esse sinograma, com os "rios" formando picos brilhantes, que são circulados:

insira a descrição da imagem aqui

Aquele com rotação de 70 graus pode ser visto claramente como o pico à esquerda deste gráfico de uma fatia ao longo do eixo horizontal:

insira a descrição da imagem aqui

Especialmente se o texto fosse gaussiano borrado primeiro:

insira a descrição da imagem aqui

Mas não sei como extrair esses picos de maneira confiável do resto do barulho. As extremidades superior e inferior brilhantes do sinograma representam os "rios" entre as linhas horizontais do texto, das quais você obviamente não se importa. Talvez uma função de ponderação versus ângulo que enfatize mais linhas verticais e minimize as horizontais?

Uma função simples de ponderação de cosseno funciona bem nesta imagem:

insira a descrição da imagem aqui

encontrar o rio vertical a 90 graus, que é o máximo global no sinograma:

insira a descrição da imagem aqui

e nesta imagem, encontrando a de 104 graus, embora o desfoque primeiro a torne mais precisa:

insira a descrição da imagem aqui insira a descrição da imagem aqui

(A radon()função SciPy é meio idiota , ou eu mapeia esse pico de volta para a imagem original como uma linha que atravessa o meio do rio.)

Mas ele não encontra nenhum dos dois picos principais no sinograma da sua imagem, depois de desfocar e ponderar:

insira a descrição da imagem aqui

Eles estão lá, mas estão sobrecarregados com as coisas próximas ao pico médio da função de ponderação. Com a ponderação e os ajustes corretos, esse método provavelmente pode funcionar, mas não tenho certeza de quais são os ajustes corretos. Provavelmente também depende das propriedades das digitalizações da página. Talvez a ponderação precise ser derivada da energia geral na fatia ou algo assim, como uma normalização.

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'

E se você fosse desfocar com um gaussiano assimétrico primeiro? Ou seja, estreito na direção horizontal, largo na direção vertical.
Jonas

@Jonas: Isso provavelmente ajudaria. O principal problema é escolher automaticamente os picos do plano de fundo quando o plano de fundo varia muito com a rotação. O desfoque assimétrico pode suavizar as faixas horizontais de linha para linha.
endolith 11/10

Isso funciona bem para detectar a rotação de linhas no texto, pelo menos: gist.github.com/endolith/334196bac1cac45a4893
endolith

16

Treinei um classificador discriminativo nos pixels usando recursos derivados (até a 2ª ordem) em diferentes escalas.

Meus marcadores:

Marcação

Previsão na imagem do treinamento:

insira a descrição da imagem aqui

Previsão nas outras duas imagens:

insira a descrição da imagem aqui

insira a descrição da imagem aqui

Acho que isso parece promissor e pode gerar resultados úteis, com mais dados de treinamento e recursos talvez mais inteligentes. Por outro lado, levei apenas alguns minutos para obter esses resultados. Você pode reproduzir os resultados usando o software de código aberto ilastik . [Aviso: sou um dos principais desenvolvedores.]


2

(Desculpe, este post não vem com demonstrações impressionantes.)

Se você deseja trabalhar com as informações que o TeX já possui (letras e posições), pode classificar manualmente as letras e os pares de letras como "inclinados" em uma direção ou outra. Por exemplo, "w" tem inclinações de canto SW e SE, o combo "al" tem uma inclinação de canto noroeste, "k" tem uma inclinação de canto NE. (Não se esqueça da pontuação - uma citação seguida de uma letra que preenche a metade inferior da caixa de glifos estabelece uma inclinação agradável; a citação seguida de q é particularmente forte.)

Em seguida, procure por ocorrências de declives correspondentes em lados opostos de um espaço - "w al" para um rio SW-para-NE ou "k T" para um rio NW-SE. Quando você encontrar um em uma linha, veja se um semelhante ocorre, movido adequadamente para a esquerda ou direita, nas linhas acima / abaixo; quando você encontra uma corrida dessas, provavelmente há um rio.

Além disso, obviamente, basta procurar espaços empilhados quase na vertical, para os rios verticais simples.

Você pode ficar um pouco mais sofisticado medindo a "força" da inclinação: quanto da caixa de avanço está "vazia" devido à inclinação e, assim, contribuindo para a largura do rio. "w" é bastante pequeno, pois possui apenas um pequeno canto de sua caixa de avanço para contribuir com o rio, mas "V" é muito forte. "b" é um pouco mais forte que "k"; a curva mais suave fornece uma margem do rio mais visualmente contínua, tornando-a mais forte e visualmente mais larga.

Ao utilizar nosso site, você reconhece que leu e compreendeu nossa Política de Cookies e nossa Política de Privacidade.
Licensed under cc by-sa 3.0 with attribution required.