Classificação de imagens de fotografias históricas usando detecção de linhas e paralelogramos pela presença de edifícios

Neste trabalho é realizado o estudo de uma metodologia para classificar imagens de fotografias históricas baseada na detecção de edifícios. A metodologia envolve a detecção de bordas pelo algoritmo de Canny e a detecção de linhas e de paralelogramos usando a Transformada de Hough. Devido às características das imagens, são testados também alguns filtros para melhorar a qualidade com redução de ruído e ajuste de contraste. Resultados preliminares mostraram que os atributos usados na classificação possibilitam 62% de acerto, separando razoavelmente as classes edifícios da não-edifícios.

Os autores de [8] definem edifícios como objetos construídos pelo homem com contornos bem definidos e bordas retas. Essas estruturas contêm, na maioria das vezes, portas e janelas, formando um conjunto de paralelogramos alinhados. Ao passo que linhas extraídas de imagens de não-edifícios são geralmente distribuídas aleatoriamente. A detecção de fotografias que possuem fachadas de edifícios e de outras construções (igrejas, por exemplo), com o auxílio de técnicas de Recuperação de Imagens com Base no Conteúdo Visual (RIBC), pode ser usada na classificação de áreas entre urbanas ou rurais e na diferenciação entre ambientes externos e internos, colaborando com a indexação e recuperação dessas imagens.

As técnicas de RIBC são geralmente baseadas na análise de cores, formas e texturas das imagens. Tipicamente, a construção de um sistema RIBC compreende duas etapas: a representação das imagens e a comparação entre as representações das imagens da base com a imagem-consulta, para computação de um ranking de similaridade [15].

Segundo [9], as técnicas de representação mais usuais podem ser divididas em duas grandes categorias: abordagens baseadas em visão e abordagens baseadas em modelos. As abordagens baseadas em visão, aspectos puramente quantitativos da imagem são computados, sendo os mais comuns os histogramas de cores e técnicas de análise de texturas. Por exemplo, as técnicas descritas em [3] e [12], que realizam a classificação de imagens de exteriores. Entretanto, conforme observado em [16], a classificação de imagens que contém estruturas construídas pelo homem não é satisfatória nestes trabalhos pois cor e textura não são informativas para esta classe.

Já as técnicas baseadas em modelos buscam a extração de modelos 3D dos objetos de interesse. Essas técnicas, oriundas principalmente dos trabalhos de visão computacional, requerem um conhecimento a priori da forma dos objetos. As técnicas baseadas em modelos são pouco aplicáveis a domínios amplos, pela imprevisibilidade do que pode ser encontrado em cada imagem, não só em termos de conteúdo, mas em termos de escala, ângulo de visão, etc. Em [8], por exemplo, é proposta a aplicação de princípios de agrupamento perceptivo, oriundos da psicologia Gestalt, para extração de elementos de nível intermediário que possam ser vistos como sugestões do conteúdo da imagem. Essa técnica começa pela extração de pequenos segmentos de reta que são, então, agrupados em retas maiores, junções em L, junções em U, grupos paralelos, grupos paralelos significativos e finalmente polígonos. As relações semânticas entre essas estruturas são usadas para detectar a presença de objetos construídos pelo homem, tais como edifícios, torres e pontes.

No trabalho em [6], visão computacional é utilizada para compreender cenas que em geral possuem grande diversidade de objetos, como cenas naturais contendo estradas, prédios, árvores, etc. O algoritmo proposto é baseado na detecção de ângulos e retas. Em testes anteriores executados com o detector de quinas de Harris (figuras a seguir), nota-se que, em construções, os ângulos de janelas e portas são corretamente marcados, denotanto certa organização geométrica, o que não ocorre nas imagens de paisagens naturais e plantações. Aliadas a esses resultados, informações de linhas e paralelogramos contidos nas imagens podem determinar a localização das portas e janelas nas imagens.

(As quinas detectadas são marcadas em vermelho.)

O algoritmo de detecção de paralelogramos descrito por [10] é capaz de detectar paralelogramos de tamanhos e orientações variadas mesmo em imagens ruidosas. Nesse trabalho, os autores fazem uso da Transformada de Hough para detectar paralelogramos. Além disso, esse método tem a vantagem de dividir a imagem em partições menores, formando uma grade retangular. Dessa forma, calcular a Transformada de Hough sobre cada partição da imagem reduz a complexidade computacional comparada à Transformada de Hough global. Um algoritmo semelhante é também utilizado por [11] para detectar retângulos.

Com base nessas informações, a metodologia proposta neste trabalho será composta pela detecção de linhas utilizando a Transformada de Hough e detecção de paralelogramos usando o algoritmo de [10]. Adicionalmente, serão utilizados filtros para melhorar a qualidade das imagens, que possuem características bem distintas das imagens utilizadas pelos autores citados anteriormente. Nesses trabalhos, imagens sintéticas e fotografias recentes são usadas.

A primeira etapa do trabalho é a seleção de imagens para os experimentos e sua separação em três classes: edifícios, intermediárias e não-edifícios. Essa separação foi sugerida em [8] e contém as seguintes características, adaptadas para esse trabalho:

• Edifícios: maior parte da imagem ocupada por fachada de edifício (parte externa). Pode conter pessoas, árvores, esculturas, carros e outros objetos ocupando pequena parte da imagem.
• Intermediárias: imagem contém alguma parte mínima de fachada, ou edifício distante. Pode conter vários objetos e pessoas ocupando maior porção da imagem.
• Não-edifícios: nenhuma parte da imagem contém edifícios.

O trabalho será realizado utilizando-se um subconjunto do acervo fotográfico digitalizado do APM de diversos temas (construções, paisagens, pessoas, carros, etc) e condições (iluminação, conservação, suporte fotográfico, ângulos, distância da cena, orientação, etc) contendo 90 imagens, 30 de cada classe. As fotografias têm aproximadamente 800×600 pixels em RGB com 24 bits (8 bits para o canal vermelho, 8 bits para o canal verde, 8 bits para azul) para a cor e formato JPEG.

A segunda etapa do trabalho é a detecção de bordas, realizada pelo algoritmo de Canny [1]. A Transformada de Hough será aplicada na imagem das bordas, e usada para a detecção de linhas e paralelogramos (o código-fonte do detector de paralelogramos foi fornecido pelos autores). No espaço de Hough, um ponto representa uma linha do plano da imagem e o valor do pico nesse ponto indica o tamanho da linha. O algoritmo de detecção de paralelogramos [10] parte da observação de [7] de que, no espaço de Hough, um paralelogramo é representado por quatro picos que guardam entre si algumas relações geométricas características:

• Esses picos aparecem aos pares, onde cada par tem o mesmo valor de θ, ou seja, tem o mesmo ângulo de inclinação;
• As intensidades dos dois picos são as mesmas, pois representam lados opostos do paralelogramo e têm portanto o mesmo tamanho;
• Os pares são separados no eixo θ do espaço de Hough por uma valor α, onde α é um dos ângulos internos do paralelogramo.
• As distâncias verticais entre os picos no eixo ρ do espaço de Hough são as distâncias entre os lados do paralelogramo.

A terceira etapa do trabalho é a realização de testes preliminares com um conjunto de amostras para determinar parâmetros e limiares. Esse conjunto contém um total de 9 imagens, 3 para cada classe. As métricas escolhidas para os experimentos são:

1. Número total de linhas.
2. Número de linhas maiores ou igual a um limiar.
3. Razão entre as métricas 2 e 1, para efeito de normalização.
4. Número de paralelogramos.

O objetivo inicial é utilizar as métricas 3 e 4 para fazer a separação em classes.

A quarta etapa é a execução do experimento, com os parâmetros e limiares escolhidos na etapa anterior, no conjunto de 90 imagens. Inicialmente, a classificação das imagens será baseada nos limiares escolhidos pela análise dos resultados preliminares. Os resultados serão apresentados por meio de uma matriz de confusão, em que cada linha e cada coluna representam uma classe, cada elemento da matriz contém o número de imagens da classe dada pela linha classificadas como a classe dada pela coluna. A diagonal da matriz de confusão reflete o resultado da classificação para as classes existentes. O esquema das etapas de trabalho é mostrado na figura seguinte:

Para um teste inicial, foram selecionadas duas imagens: uma da classe edifícios, outra da classe não-edifícios. Esse primeiro teste foi apenas para ter uma idéia dos valores dos parâmetros. Os parâmetros selecionados para variarem foram:

* tamanho da partição (tile): 10×10, 15×15, 30×30 e alt/2 x larg/2 (alt e larg são a altura e a largura da imagem de entrada, respectivamente). * lado mínimo do paralelogramo (RMin): 5 e 10. * ângulo interno do paralelogramo: 90°ou genérico (no algoritmo de [10], existe a possibilidade de não fornecer esse parâmetro, sendo que neste caso procura-se por todos os paralelogramos, independente do ângulo interno).

Como resultado desse teste, observou-se que não foi detectado nenhum paralelogramo de ângulo interno 90° em testes com essas imagens para RMin = 5 e RMin = 10 e tiles 10×10 e 15×15. Nos testes realizados com tiles 10×10, 15×15 e 30×30 e RMin = 5 e RMin = 10 não foram detectados paralelogramos correspondentes às janelas do edifício, mas vários outros que não coincidem com as bordas detectadas. As imagens utilizadas são mostradas na figura a seguir e os resultados para tile = alt/2 x larg/2 e RMin = 5 estão na tabela a seguir. Para as imagens testadas, os números de paralelogramos detectados diferem em uma ordem de grandeza.

Os resultados da subseção anterior mostraram a necessidade de realizar experimentos com imagens ideais, sintéticas, com ruído mínimo, pois apenas no teste com tile = alt/2 x larg/2 e RMin = 5 alguns dos paralelogramos detectados estavam de acordo com as bordas oriundas das linhas formadas por portas, janelas e contornos do edifício, sugerindo uma melhor validação do detector para essa função.

Duas imagens sintéticas foram usadas para testar a influência dos parâmetros tamanho da partição (tile) e lado mínimo do paralelogramo (RMin). Os resultados mostraram que tiles próximos do tamanho das janelas da imagem sintética (aproximadamente 16×20 pixels) melhoram a detecção e que o RMin deve ser entre 5 ou 10 para essa imagem. Os testes foram realizados com o detector de paralelogramos configurado para encontrar paralelogramos genéricos. A tabela a seguir mostra os resultados. Pode-se concluir que os parâmetros que melhor diferenciam as imagens são tile 20×20 e RMin = 10. As imagens sintéticas e exemplos de resultados são encontrados nas próximas figuras:

Imagens sintéticas

Resultados com tile 20×20 e RMin = 10. Em cinza os paralelogramos detectados.

Resultados com tile 30×30 e RMin = 5.

Devido às características das imagens, foram testados dois filtros para melhorar a qualidade, o filtro gaussiano para redução de ruído e ajuste de contraste, ambos 3×3. O filtro gaussiano foi usado com σ = 0,5 e o filtro de ajuste de contraste com α = 0,2, e correspondem aos filtros gaussian e unsharp do programa Matlab:

Também foram testadas uma redução de cor para aproximar a fotografia da imagem ideal, com poucos detalhes, uma redução no tamanho das imagens para que o tempo de execução (por volta de 10 minutos por imagem) fosse menor, e a retirada das molduras que introduzem paralelogramos por causa de suas linhas e detalhes, por exemplo:

Em [14] é proposta uma metodologia para a remoção automática de molduras da base de imagens do APM, que de fato afetam os resultados da recuperação e indexação de imagens com base no conteúdo.

O objetivo com estes novos testes é verificar o comportamento do detector de linhas e paralelogramos nas imagens com diferentes configurações e visualizar um possível limiar. Nesse experimento foram utilizadas 9 imagens de fotografias, 3 de cada classe. As configurações usadas foram:

1. Imagem original.
2. Imagem original reduzida em 50% do tamanho.
3. Imagem original reduzida em 50% sem a moldura (retirada manualmente).
4. Imagem original reduzida em 50% sem a moldura com apenas 3 níveis de cinza.
5. Imagem original reduzida em 50% sem a moldura com melhora do contraste e suavização.

Exemplo das configurações:

* Imagem original da classe edifícios

* Imagem original reduzida em 50%

* Imagem original reduzida em 50% sem a moldura

* Imagem original reduzida em 50% sem a moldura com apenas 3 níveis de cinza

* Imagem original reduzida em 50% sem a moldura com melhora do contraste e suavização

A tabela a seguir mostra os resultados para tile 20×20 e RMin = 10:

Os dados da tabela são o número de imagens resultante da comparação. A configuração 2 foi comparada com a imagem original (configuração 1). A configuração 3 foi comparada com a 2. As outras configurações foram comparadas com os valores da configuração 3. Nota-se que as configurações 2 e 4 reduzem em 100% dos casos as linhas, e em 89% e 78% o número de paralelogramos detectados. A configuração 5 aumenta em 89% das imagens o número de linhas e em 67% os paralelogramos. A configuração 3 em geral reduz o número de linhas detectadas, devido à retirada da moldura.

Resultados separados por classe:

As mesmas amostras nas 5 configurações, processadas com tiles 20×20 e RMin = 10, foram analisadas para a obtenção de um limiar para as métricas 3 e 4. Os resultados estão na tabela abaixo. Na numeração da primeira coluna, o primeiro algarismo indica a configuração e o segundo, a classe da imagem. Para os limiares 50, 60, 70, 90 e 100 os resultados foram iguais ou próximos de zero e por isso não foram listados.

As cores (exceto amarelo) indicam possibilidade de determinar um limiar.

As imagens estão distribuídas da seguinte forma:

• Edifícios:

AB-05-3-012.jpg
AB-05-3-015.jpg
AB-05-3-033.jpg

• Intermediárias:

TG-2-031.jpg
TG-1-050.jpg
SI-61(30).jpg

• Não-edifícios:

AB-06-1-027.jpg
JP-11-2-043.jpg
AB-08-012(04).jpg

A partir desses resultados, foram estabelecidos limiares para as configurações:

Os limiares encontrados na seção anterior foram usados para os testes com dois grupos de imagens: imagem original reduzida em 50% sem a moldura (3) e imagem original reduzida em 50% sem a moldura com melhora do contraste e suavização (5).

Para o conjunto de teste foram selecionadas aleatoriamente 90 imagens, 30 de cada classe. As imagens sofreram redução de resolução em 50% e as molduras presentes foram retiradas manualmente.

Os resultados são apresentados nas tabelas a seguir:

Matriz de confusão para a configuração 3: Classe 1 = edifícios, Classe 2 = intermediárias, Classe 3 = não-edifícios e Classe 4 = não foi possível classificar.

Matriz de confusão para a configuração 5.

Na matriz da configuração 3, os resultados foram 13%, 57% e 0% para as classes edifícios, intermediárias e não-edifícios, respectivamente, e na configuração 5, os resultados foram 1%, 83% e 0%.

Embora o algoritmo de detecção de paralelogramos seja capaz de detectar paralelogramos de tamanhos e orientações variadas mesmo em imagens ruidosas, o número de paralelogramos mostrou-se incapaz de diferenciar as imagens com estruturas construídas pelo homem das imagens com estruturas naturais. Um ajuste melhor dos parâmetros tile e RMin poderia levar a resultados mais satisfatórios nessas imagens, levando-se em conta uma média do tamanho das janelas, por exemplo.

Aparentemente, os atributos usados na classificação possibilitam distinguir uma das classes, a intermediária, das outras duas, edifícios e não-edifícios. Entretanto, uma análise da matriz de confusão revela que há uma concentração de valores na coluna da classe intermediária, o que significa que a maior parte das imagens foi classificada como intermediária e baixa concentração na diagonal, ou seja, a maioria das imagens não foi classificada corretamente. Isso indica que os atributos escolhidos tem valores próximos para todas as classes.

Como trabalhos futuros, tem-se o objetivo de:

• utilizar um conjunto de imagens maior para o treinamento e testes;
• selecionar novos atributos e ajustar melhor os parâmetros utilizados;
• uso de métodos quantitativos e estatística para projetar e comparar os experimentos, de forma mais objetiva;
• realizar a classicação com Support Vector Machines (SVM) [2];
• fazer a detecção de bordas com o algoritmo de [13]. Esse algoritmo faz a detecção de bordas de Canny com as alterações propostas por [4], e as imagens resultantes são menos ruidosas do que o filtro de Canny implementado no Matlab, como mostram as imagens testadas:

Imagem original, filtro canny do Matlab, filtro canny alterado.

Em nenhum dos testes foram detectados paralelogramos. Obs: as bordas da imagem não tem largura de 1 pixel, como no canny tradicional. http://www.csse.uwa.edu.au/~pk/Research/MatlabFns/

Obs: novamente não foram detectados paralelogramos quando o ângulo é configurado para 90°.

Utilizando a interface da LIBSVM para Matlab: (LIBSVM : a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm)

• Treino: 15, 5 de cada classe
• Teste: 90, 30 de cada classe
• Kernel: radial basis function, SVM: C-SVC
• Para vários valores de C e gamma testados, o melhor resultado foi (C = 130 e gamma = 0,00002):

Accuracy = 45.5556% (41/90) (classification)

accuracy =

 45.5556
  1.1778
  0.1117

(accuracy is a vector including accuracy (for classification), mean squared error, and squared correlation coefficient (for regression).)

• Treino: 45, 15 de cada classe
• Teste: 45, 15 de cada classe
• Kernel: radial basis function, SVM: C-SVC
• Para vários valores de C e gamma testados, o melhor resultado foi (C = 360 e gamma = 0,05):

Accuracy = 62.2222% (28/45) (classification)

accuracy =

 62.2222
  0.5778
  0.2732

[1] J. Canny. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986.

[2] C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software disponível em http://www.csie.ntu.edu.tw/~cjlin/libsvm.

[3] X. Feng, C. K. I. Williams, and S. N. Felderhof. Combining belief networks and neural networks for scene segmentation. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 24, pages 467–483, 2002.

[4] M. M. Fleck. Some defects in finite-difference edge finders. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(3):337–345, 1992.

[5] T. Gevers and A. W. M. Smeulders. Content-Based Image Retrieval: An Overview, chapter 8. IMSC Press Multimedia Series. Prentice Hall, 1st edition, July 2004.

[6] C. Harris and M. Stephens. A combined corner and edge detector. In Proceedings of The Fourth Alvey Vision Conference, pages 147–151, 1988.

[7] D. Ioannou and E. Dugan. Parallelogram detection in a digital image with the use of the hough transform. In Proceedings of the IEEE Computer Society International Conference on Pattern Recognition, volume II, pages 532–536. IEEE Computer Society, 1996.

[8] Q. Iqbal and J. Aggarwal. Retrieval by classification of images containing large manmade objects using perceptual grouping. Pattern Recognition, 35(7):1463–1479, July 2002.

[9] Q. Iqbal and J. K. Aggarwal. Feature integration, multiimage queries and relevance feedback in image retrieval. In Proceedings of 6th International Conference on Visual Information Systems, pages 467–474, Sep. 24-26 2003.

[10] C. Jung and S. Rosito. Parallelogramdetection using the tiled hough transform. In Proceedings of 13th International Conference on Systems, Signals and Image Processing, volume I, pages 177–180, 2006.

[11] C. R. Jung and R. Schramm. Rectangle detection based on a windowed hough transform. In Proceedings of XVII Brazilian Symposium on Computer Graphics and Image Processing, pages 113–120. IEEE Computer Society, 2004.

[12] S. Konishi and A. L. Yuille. Statistical cues for domain specific image segmentation with performance analysis. In Proceedings of the 2000 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, volume I, pages 135–132, 2000.

[13] P. D. Kovesi. MATLAB and Octave functions for computer vision and image processing. School of Computer Science & Software Engineering, The University of Western Australia. Disponível em http://www.csse.uwa.edu.au/~pk/research/matlabfns/.

[14] A. P. B. Lopes, D. L. Flam, N. C. Batista, S. E. F. de Avila, J.M. Almeida, and A. de A. Araújo. Frame detection in historical photographs using tiled hough transform. 2008. Submetido para publicação.

[15] N. Sebe, Q. Tian, E. Loupias, M. Lew, and T. Huang. Evaluation of salient point techniques. Image and Vision Computing, 21(13-14):1087–1095, December 2003.

[16] A. Vailaya, A. K. Jain, and H. J. Zhang. On image classification: City images vs. landscapes. Pattern Recognition, 31:1921–1936, 1998.

Artigo última versão (inclui novos testes): :cursos:visao:2008-1:grupo08:artigo_natalia3.pdf

Artigo corrigido: :cursos:visao:2008-1:grupo08:artigo_natalia2.pdf

Artigo (primeira versão): :cursos:visao:2008-1:grupo08:artigo_natalia.pdf

Referências (.bib): :cursos:visao:2008-1:grupo08:ref_natalia.zip

Apresentação: :cursos:visao:2008-1:grupo08:apresentacao.ppt