Pós-Graduação em Ciência da Computação
SAULO CADETE SANTOS MACHADO
SEGMENTAÇÃO DE TEXTO EM IMAGENS DE MAPAS E
PLANTAS BAIXAS ANTIGOS
Dissertação de Mestrado
Universidade Federal de Pernambuco
[email protected]
www.cin.ufpe.br/~posgraduacao
Recife
2014
UNIVERSIDADE FEDERAL DE PERNAMBUCO
CENTRO DE INFORMÁTICA
PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
SAULO CADETE SANTOS MACHADO
SEGMENTAÇÃO DE TEXTO EM IMAGENS DE MAPAS E PLANTAS BAIXAS
ANTIGOS
ESTE TRABALHO FOI APRESENTADO À PÓS-GRADUAÇÃO
EM CIÊNCIA DA COMPUTAÇÃO DO CENTRO DE
INFORMÁTICA
DA
UNIVERSIDADE
PERNAMBUCO
COMO
REQUISITO
FEDERAL
PARCIAL
DE
PARA
OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIA DA
COMPUTAÇÃO.
ORIENTADOR:
PROF.
DR.
ALEXANDRE BARROS DE MELLO
Recife
2014
CARLOS
Dissertação de Mestrado apresentada por Saulo Cadete Santos Machado à Pós-Graduação em
Ciência da Computação do Centro de Informática da Universidade Federal de Pernambuco, sob
o título SEGMENTAÇÃO DE TEXTO EM IMAGENS DE MAPAS E PLANTAS
BAIXAS ANTIGOS orientada pelo Prof. Carlos Alexandre Barros de Mello e aprovada pela
Banca Examinadora formada pelos professores:
______________________________________________
Prof. Cleber Zanchettin
Centro de Informática/UFPE
______________________________________________
Prof. Byron Leite Dantas Bezerra
Escola Politécnica de Pernambuco/UPE
______________________________________________
Prof. Carlos Alexandre Barros de Mello
Centro de Informática/UFPE
Visto e permitida a impressão.
Recife, 28 de agosto de 2014.
___________________________________________________
Profa. Edna Natividade da Silva Barros
Coordenadora da Pós-Graduação em Ciência da Computação do
Centro de Informática da Universidade Federal de Pernambuco.
Agradecimentos
Agradeço a Deus pela oportunidade de concluir mais esta etapa de minha formação.
À minha família pelo constante incentivo. O apoio e compreensão de meus pais
foram essenciais para que eu pudesse superar as dificuldades que encontrei. Agradeço ao
meu pai por me motivar a continuar estudando. Em especial, agradeço à minha mãe por
sempre ter me ajudado a superar os maiores desafios.
Ao meu orientador, Prof. Dr. Carlos Alexandre Barros de Mello, por ter acreditado
em minha capacidade de desempenhar o trabalho. Foi um privilégio trabalhar novamente
sob sua orientação.
Aos meus colegas de trabalho que sempre estimularam a formação acadêmica e
valorizaram a pesquisa científica. É um prazer trabalhar em um lugar em que o pensamento
inovador e criativo é tão valorizado.
A todos que participaram de minha vida nos últimos anos e colaboraram de alguma
maneira com a conclusão dessa etapa.
Resumo
Documentos
antigos
podem
conter
informações
importantes
para
o
desenvolvimento de trabalhos atuais. Mapas e plantas baixas históricos podem representar a
cultura artística e tecnológica do momento em que foram criados. A qualidade e quantidade
de suas informações justificam esforços para mantê-los e garantir a disponibilidade desses
documentos. O primeiro passo para alcançar isso é a digitalização. Mas é necessário um
processamento automático para que o documento seja pesquisável sem a custosa indexação
manual. Ferramentas comuns de reconhecimento automático de caracteres têm dificuldade
em reconhecer o texto de imagens de mapas e plantas baixas. Além do desgaste do papel
provocado pelo tempo e manuseio, esses documentos possuem muitos elementos gráficos,
como desenhos de rios e paredes, que ocupam a maior parte da imagem e podem até colidir
com componentes textuais. Esse texto pode ser de diferentes estilos, tamanhos e orientações.
Para facilitar a o reconhecimento de texto pelas ferramentas de reconhecimento automático,
é importante remover os componentes gráficos da imagem antes de submetê-la ao processo
de reconhecimento. Trabalhos recentes sobre segmentação de texto em imagens de mapas e
plantas baixas usam regras definidas especialmente para as características das imagens que
esperam. Esta dissertação apresenta uma nova abordagem para segmentar texto em imagens
de mapas e plantas baixas. O método é divido em três etapas. A primeira é o préprocessamento em que o plano de fundo e alguns componentes gráficos são removidos. A
segunda etapa é a de classificação em que são utilizados classificadores baseados em
Máquinas de Vetores de Suporte treinados para identificar caracteres e sequências de
caracteres. Por fim, é realizado um pós-processamento para evitar erros de classificação e
recuperar componentes a partir de sua similaridade com os que foram classificados como
texto. Os resultados comprovaram a eficácia do método proposto que alcançou taxas de erro
inferiores a 10% para a segmentação de texto em imagens de mapas e plantas baixas.
Palavras-chave: Processamento de imagens. Segmentação. Detecção de texto. Máquinas de
vetor de suporte.
Abstract
Ancient documents may contain useful information for more recent works. Maps
and floor plans may represent the artistic and technological culture of the time they were
created. The quality and quantity of their contents justify efforts to preserve and guarantee
the availability of these documents. The first step to achieve this is through digitizing. But
an automatic processing is required for the document to be searchable without expensive
manual indexing. Common character recognition tools have problems for recognizing text
in images of maps and floor plans. Besides damage caused by time and handling, these
documents have many graphical components, like drawings of rivers and walls, which
occupies most part of the image and may even collide with text components. The text itself
can be of different styles, sizes and orientations. To make it easier for character recognition
software to recognize the text of these images, it is important to remove graphical
components from the image, before submitting it to the recognition process. The most recent
works for text segmentation in images of maps or floor plans use rules defined specially for
characteristics of the images they expect. This work presents a new approach for text
segmentation in images of maps and floor plans. The method is divided into three steps. First
is the pre-processing when the background and some graphical components of the image
are removed. The second step is the classification where are used classifiers based on
Support Vector Machines trained to detect characters and sequences of characters. Finally
a post-processing is done to avoid classification errors and recover components based on
their similarity to those classified as text. The results confirmed the efficiency of the proposed
method that achieved error rates below 10% for text segmentation in images of maps and
floor plans.
Keywords: Image processing. Segmentation. Text detection. Support vector machines.
Lista de Figuras
Figura 1.1: Exemplos dos desafios para detecção de texto em (a) mapas e (b) plantas baixas.
.............................................................................................................................................. 19
Figura 2.1: Visualização do sistema de cores aditivo. ......................................................... 22
Figura 2.2: Adjacência entre pixels. .................................................................................... 25
Figura 2.3: Exemplo da influência da quantidade de coeficientes usados no descritor de
Fourier. ................................................................................................................................. 26
Figura 2.4: Exemplos de operações morfológicas. .............................................................. 29
Figura 2.5: Visualização do HOG. ....................................................................................... 31
Figura 2.6: O treinamento de uma SVM consiste em encontrar o hiperplano que produza a
máxima separação entre as classes. ..................................................................................... 33
Figura 3.1: Exemplo de processo de digitalização de documentos. .................................... 37
Figura 3.2: (a-c) Detecção de focos em níveis diferentes. (d) Grid para extração de
características criado a partir dos focos. .............................................................................. 46
Figura 3.3: Funções de peso para as células do HOG.......................................................... 47
Figura 3.4: Aplicação do algoritmo de Mello e Machado a algumas imagens de mapas a
plantas baixas. ...................................................................................................................... 52
Figura 4.1: Diagrama da visão geral do processo de execução do método proposto. ......... 56
Figura 4.2: Diagrama do subprocesso de pré-processamento. ............................................. 57
Figura 4.3: Resultado da transformação para tons de cinza e redimensionamento de uma
imagem. ................................................................................................................................ 58
Figura 4.4: Resultados das operações de pré-processamento. ............................................. 59
Figura 4.5: Eliminação de componentes de acordo com a área. .......................................... 61
Figura 4.6: Resultado da remoção de componentes de acordo com a espessura do traçado.
.............................................................................................................................................. 62
Figura 4.7: Subprocesso de detecção de texto ..................................................................... 62
Figura 4.8: Pontos de canto para uma imagem. ................................................................... 64
Figura 4.9: Ilustração da projeção de fatores de normalização (linhas) e orientações (colunas)
para o método de Felzenszwalb et al.. ................................................................................. 65
Figura 4.10: Exemplo da superfície de descrição sem outliers à esquerda e com um outlier à
direita. .................................................................................................................................. 67
Figura 4.11: Variação da superfície de descrição de acordo com o parâmetro σ de uma função
de núcleo gaussiana e o parâmetro C do descritor. .............................................................. 68
Figura 4.12: Subprocesso reutilizável de recuperação. ........................................................ 69
Figura 4.13: Áreas de proximidade consideradas na recuperação. ...................................... 71
Figura 5.1: Exemplo de Matriz de Confusão ....................................................................... 77
Figura 5.2: Resultados obtidos para os exemplos de mapas. ............................................... 79
Figura 5.3: Resultados obtidos para imagens de plantas baixas. ......................................... 90
Lista de Tabelas
Tabela 5.1: Valores de parâmetros para SVDD avaliados em repetição de holdout. .......... 75
Tabela 5.2: Média e desvio padrão dos indicadores para imagens de mapas. ..................... 78
Tabela 5.3: Média e desvio padrão de indicadores obtidos para imagens de plantas baixas.
.............................................................................................................................................. 89
Tabela 5.4: Comparação de resultados. O valor de cada indicador é a média obtida para as
imagens de avaliação. ........................................................................................................ 100
Lista de Abreviações
CBIF
Corner Based Interpolated Feature
CCM
Coeficiente de Correlação de Matthews
HOG
Histogram of Oriented Gradients (Histograma de Gradientes Orientados)
OCR
Optical Characters Recognition (Reconhecimento Ótico de Caracteres)
RGB
Red, Green and Blue (Vermelho, Verde e Azul)
ROC
Receiver Operating Characteristic (Característica de Operação do
Receptor)
SVDD
Support Vector Data Descriptor (Máquina de Vetores de Descrição de
Dados)
SVM
Support Vector Machine (Máquina de Vetores de Suporte)
Sumário
1
Introdução ................................................................................................................ 14
1.1
Processamento Digital de Imagens .......................................................................... 15
1.2
Reconhecimento de Texto ........................................................................................ 16
1.3
Documentos Antigos ................................................................................................ 18
1.3.1 Mapas e Plantas Baixas ............................................................................................ 19
1.4
Motivação e Problema.............................................................................................. 20
1.5
Objetivos .................................................................................................................. 21
1.6
Estrutura da Dissertação ........................................................................................... 21
2
Conceitos Básicos .................................................................................................... 22
2.1
Processamento Digital de Imagens .......................................................................... 22
2.1.1 Limiarização ............................................................................................................. 23
2.1.2 Componentes Conexos ............................................................................................. 24
2.1.3 Descritores de Fourier .............................................................................................. 25
2.1.4 Morfologia Matemática ............................................................................................ 26
2.1.5 Histograma de Gradientes Orientados ..................................................................... 29
2.2
Reconhecimento de Padrões .................................................................................... 32
2.2.1 Máquinas de Vetores de Suporte.............................................................................. 32
2.2.2 Sistemas de Reconhecimento Óptico de Caracteres ................................................ 35
3
Detecção de Texto em Imagens de Mapas e Plantas Baixas .................................... 37
3.1
Mapas e Plantas Baixas ............................................................................................ 37
3.2
Segmentação de Gráficos ......................................................................................... 38
3.2.1 De las Heras et al. .................................................................................................... 38
3.2.2 Miao et al. ................................................................................................................ 38
3.2.3 Leyk e Boesch .......................................................................................................... 39
3.3
Detecção, Segmentação e Recuperação de Texto .................................................... 40
3.3.1 Karaoglu, Fernando e Tremeau ................................................................................ 40
3.3.2 Weinman .................................................................................................................. 41
3.3.3 Dovgalecs et al. ........................................................................................................ 41
3.3.4 Vassilieva e Fomina ................................................................................................. 42
3.3.5 Tombre et al. ............................................................................................................ 42
3.3.6 Ahmed et al. ............................................................................................................. 43
3.3.7 Tarafdar et al. ........................................................................................................... 44
3.3.8 Almazán, Fornes e Valveny ..................................................................................... 45
3.3.9 Minetto et al. ............................................................................................................ 47
3.3.10 Biswas e Das ............................................................................................................ 48
3.3.11 Shi et al. ................................................................................................................... 48
3.3.12 Pratim Roy et al. ...................................................................................................... 50
3.3.13 Mello e Machado...................................................................................................... 51
4
Método Proposto ...................................................................................................... 56
4.1
Pré-processamento ................................................................................................... 57
4.2
Detecção de Texto .................................................................................................... 62
4.2.1 Caracteres ................................................................................................................. 62
4.2.2 Sequências de caracteres .......................................................................................... 64
4.2.3 Classificação ............................................................................................................ 66
4.3
Separação de Pequenos Componentes Alongados ................................................... 68
4.4
Recuperação ............................................................................................................. 69
5
Experimentos e Resultados ...................................................................................... 72
5.1
Bases de Dados ........................................................................................................ 72
5.2
Experimentos............................................................................................................ 73
5.2.1 Parâmetros do Pré-processamento ........................................................................... 74
5.2.2 Parâmetros da Detecção de Texto ............................................................................ 74
5.3
Implementações........................................................................................................ 75
5.4
Método de Avaliação ............................................................................................... 76
5.5
Resultados e Análise ................................................................................................ 77
5.5.1 Mapas ....................................................................................................................... 78
5.5.2 Plantas Baixas .......................................................................................................... 89
5.5.3 Comparação de Resultados .................................................................................... 100
5.5.4 Considerações Gerais ............................................................................................. 100
6
Conclusões e Trabalhos Futuros ............................................................................ 101
6.1
Trabalhos Futuros .................................................................................................. 101
Referências ............................................................................................................. 103
14
1 Introdução
Os meios de comunicação evoluíram ao longo da história motivados pela economia,
política e tecnologia. Depois da fala, a escrita foi o meio responsável pela maior mudança na
história da comunicação humana. O papel está entre os mais antigos dos materiais de escrita e,
apesar dos avanços tecnológicos e do surgimento de novas formas de armazenamento de
informação, a escrita em papel ainda é um dos meios de comunicação mais usados no mundo.
Para aproveitar melhor as informações que existem já em papel é importante combinar suas
qualidades às vantagens do uso de novas tecnologias.
A escrita é uma forma de comunicação que consiste em expressar uma linguagem
através de símbolos. Muitos historiadores concordam que a ela foi inventada de forma
independente em duas regiões do mundo, na Mesopotâmia por volta de 3200 a.C. e na
Mesoamérica por volta de 600 a.C. (HOUSTON, 2004). Além do conteúdo representado,
materiais e instrumentos de escrita também evoluíram. Dentre os vários materiais usados ao
longo da história destacam-se as placas de pedra, argila ou madeira, couro animal, tecido, folhas
largas, papiro e papel. Os instrumentos também assumiram diversas formas como instrumentos
cuneiformes, penas, canetas-tinteiro, pincéis, lápis e canetas. A escrita foi muito disseminada
com o papiro. Inventado no Egito e produzido a partir de uma planta comum no delta do rio
Nilo, o papiro era semelhante ao papel contemporâneo. Ele era barato e facilmente produzido,
mas era frágil e possuía superfície irregular, o que dificultava a escrita. Apesar do enorme uso
de superfícies como papiro, elas dependiam de materiais específicos que tinham um estoque
limitado e precisavam de um processo de confecção cuidadoso para que tivessem qualidade
aceitável.
O papel como é conhecido atualmente foi inventado na China no século II a.C.. Criado
com materiais como madeira e restos de pano, ele podia ser produzido em qualquer lugar. Ainda
é muito utilizado e com diversas finalidades como superfície de registro informações, pacotes
e envelopes para transporte de produtos e higiene pessoal (MELLO; OLIVEIRA; SANTOS,
2012). Segundo o último relatório global da Associação Alemã de Papel e Celulose
(“Statistiken,” 2014), em 2011 e 2012 o consumo de papel no mundo se manteve estável em
mais de quatrocentos milhões de toneladas por ano, o que equivale a um consumo anual de
cinquenta e sete quilos de papel por pessoa. Da quantidade de papel produzida no mundo em
2012, foram utilizados 53,24% para pacotes e 34,53% para impressão. Dados da Indústria
Brasileira de Árvores (“Cenários,” 2014) mostram que entre 2012 e 2013 o consumo de papel
no Brasil subiu 0,7%, chegando a 9.852.000 toneladas de papel. Ainda segundo o órgão
brasileiro, o consumo de papel no Brasil segue em crescimento há dez anos. Em relação a 2012,
15
2013 apresentou pequenas quedas, 0,5% no consumo para papéis para impressão e escrita e
2,3% no consumo de papel para imprensa. O primeiro trimestre de 2014, comparado ao mesmo
período de 2013, teve crescimento de 5,4% do consumo doméstico para impressão e escrita e
queda de 13,2% no consumo de papel para imprensa.
A estabilização e queda no consumo de papel são motivadas pela adoção de novas
tecnologias e pela adoção de políticas de sustentabilidade. O papel é leve e barato, mas sofre
desgastes com o tempo, depende de meios de transporte convencionais e ocupam espaço de
armazenamento. Computadores pessoais são instrumento de trabalho cada vez mais comuns.
Melhoria de infraestrutura, maior capacidade de processamento e programas cada vez mais
fáceis de operar são alguns dos fatores que contribuem para que a informação seja criada e
propagada em meio digital. Políticas de preservação do meio ambiente também contribuem
para a redução do consumo de papel. Mesmo com regulamentações existentes, o uso
descontrolado de papel pode ter um impacto negativo sobre o meio ambiente. Por isso existem
esforços para reduzir o uso de papel e promover a reciclagem, evitando desmatamento.
O uso de computadores traz grandes vantagens, mas ainda não é possível substituir o
papel. Facilidade de encontrar documentos, economia no espaço de armazenamento físico,
facilidade de criar cópias idênticas e rápida transmissão de documentos são algumas vantagens
obtidas com o uso do meio digital. Mas a enorme utilização do papel e seu baixo custo fazem
com que os novos meios de registro de informação não tentem substituir o papel, mas
transformar seu conteúdo para que seja possível utilizá-lo em computadores.
A digitalização de documentos, isto é, sua transformação do meio físico para formato
digital, é a primeira etapa para usufruir das possibilidades de processamento modernas.
Problemas inerentes ao uso do papel, como a ocupação de grande volume de armazenamento e
o desgaste causado pelo tempo e pelo manuseio são resolvidos com o uso da imagem digital.
Ela facilita a cópia e a publicação do documento, mas possui um problema comum ao
documento físico, a dificuldade de encontrá-lo através de seu conteúdo. Para tornar possível
busca pelo conteúdo do documento digitalizado é necessário transcrevê-lo para texto
processável. Essa é uma tarefa custosa para ser realizada manualmente, mas com o auxílio de
ferramentas computacionais pode ser substituída por um processo automático.
1.1 Processamento Digital de Imagens
Processamento Digital de Imagens é o conjunto de processos cujas entradas e saídas
são imagens (GONZALEZ; WOODS, 2007). A conversão do documento físico em texto
editável envolve vários desses processos.
16
A aquisição é primeira etapa em um sistema de processamento de imagens. Ela
compreende a obtenção da imagem que pode já existir em formato digital ou ser capturada
através de sensores. Escâneres e câmeras são exemplos de dispositivos de digitalização
baseados em sensores. A imagem obtida é um arquivo digital que pode ser copiado, publicado
e armazenado com facilidade. O documento digitalizado pode ser preservado em mídias como
CDs (Compact Disks), DVDs (Digital Versatile Disk) ou discos rígidos ou publicado em
serviços de armazenamento em nuvem. A transmissão desse documento através da Internet
permite que ele seja acessado de qualquer lugar do mundo em poucos segundos. A aquisição é
uma etapa crítica porque é responsável por criar o conteúdo que irá ser usado em todo o
processamento. Problemas nesta etapa podem causar o fracasso de todo o processamento.
A imagem digital obtida pode ser subdividida em partes que a compõem através de
processos de segmentação. De forma simples, os componentes de imagens de documentos
podem ser divididos em dois grupos: texto e elementos gráficos (como desenhos). Processos de
segmentação podem separar objetos de interesse do plano de fundo da imagem, isolando o texto
do papel e suas imperfeições. Eles também podem criar separação entre componentes. O nível
de detalhamento dos processos de segmentação pode variar de acordo com a aplicação, mas sua
precisão é fundamental para que a aplicação alcance o resultado esperado (GONZALEZ;
WOODS, 2007).
Antes que os componentes sejam submetidos ao reconhecimento automático em tais
aplicações, eles precisam ser descritos a partir das características que serão utilizadas para
definir seus rótulos. Processos de descrição podem utilizar diferentes tipos de informação do
componente. A escolha correta do processo de descrição é fundamental para que o processo de
reconhecimento tenha bons resultados. Como resultado do reconhecimento tem-se os rótulos
para cada componente, identificando a qual classe pertencem. Em sistemas de reconhecimento
de caracteres, por exemplo, a descrição de um componente é usada para rotular ele como um
caractere ou como gráfico.
1.2 Reconhecimento de Texto
A capacidade de reconhecimento de texto de um computador ainda é bem inferior à
dos humanos. A maioria dos leitores é capaz de ler em texto em diferentes orientações, com
letras em estilos variados e cercado por figuras e outras decorações. Mesmo com parte do texto
distorcida, omitida ou obstruída, as pessoas ainda são capazes de utilizar a experiência e o
contexto para reconhecer o texto (CHERIET et al., 2007). O Reconhecimento Óptico de
Caracteres (Optical Characters Recognition, OCR) é uma tecnologia capaz de transformar
imagens de texto em texto processável e armazenável por computadores. Os primeiros sistemas
17
de OCR utilizavam técnicas e características simples. Elas eram lentas e não garantiam robustez
a variações na forma dos caracteres. Com o avanço da tecnologia os computadores estão cada
vez mais poderosos o que permitiu o desenvolvimento de técnicas mais robustas.
As primeiras propostas de reconhecimento automático de texto surgiram na década de
vinte e no início da década de trinta. Em 1929, na Alemanha, Tauschek propôs um dispositivo
mecânico que usava um mecanismo giratório com máscaras e um fotodetector para reconhecer
caracteres e números através de um processo de casamento de padrão. A luz passava por
diferentes máscaras e chegava ao fotodetector. Quando a luz não o alcançava, significava que
a máscara e o caractere possuíam o mesmo padrão (MELLO; OLIVEIRA; SANTOS, 2012).
As primeiras técnicas de OCR, com origem na década de cinquenta, também eram baseadas em
casamento de padrão. Cada caractere de entrada era comparado com um conjunto de modelos
de cada classe possível. A classe usada para rotular o caractere era escolhida de acordo com
medidas de similaridade entre ele e os modelos.
Mori, Suen e Yamamoto (MORI; SUEN; YAMAMOTO, 1995) dividiram os sistemas
de OCR para uso comercial em três gerações. Os da primeira geração surgiram no início década
de sessenta. Eles eram limitados ao reconhecimento de caracteres de fontes específicas,
desenvolvidas para facilitar o processo de reconhecimento. Entre a década de sessenta e a
década de setenta surgiram os sistemas da segunda geração. Estes eram capazes de reconhecer
alguns caracteres impressos com fontes comuns e um conjunto restrito de numerais
manuscritos. A partir da metade da década de setenta, a tecnologia de integração em larga escala
possibilitou que milhares de transistores fossem integrados em um único chip. A terceira
geração de sistemas de OCR foi marcada por esse aumento na capacidade de integração.
Problemas mais complexos puderam ser resolvidos devido ao aumento do poder
computacional. (MELLO; OLIVEIRA; SANTOS, 2012)
Os sistemas modernos de OCR são muito mais baratos que as soluções das primeiras
gerações. No início, esse tipo de sistema custava milhares de dólares e hoje pode ser obtido por
menos de cem dólares. Algumas soluções são fornecidas gratuitamente em conjunto com
dispositivos de digitalização, inclusive dispositivos para uso doméstico. Seguindo tendências
de desenvolvimento de sistemas com código aberto, também existem sistemas de OCR gratuitos
e mantidos por comunidades de desenvolvedores.
O menor custo de desenvolvimento e a evolução dos dispositivos móveis fez com que
também surgissem soluções para esse tipo de plataforma. O maior desafio neste caso é a
qualidade da imagem capturada. As câmeras desses dispositivos, por melhores que sejam, não
conseguem garantir uma boa qualidade de digitalização. São comuns os problemas como
18
diferença de iluminação e de perspectiva. Mesmo com essas dificuldades já existem soluções
de reconhecimento automático para dispositivos móveis que prometem bons resultados
(“ABBYY Solutions for Mobile Capture,” 2014).
A velocidade e a capacidade de reconhecimento aumentaram muito desde os primeiros
sistemas de OCR. Os primeiros demoravam cerca de um minuto para reconhecer um caractere.
Hoje essa velocidade chega a centenas de caracteres por segundo. As soluções também se
tornaram capazes de reconhecer texto impresso em diversas fontes, com algumas soluções
alcançando precisão de 99% no reconhecimento de texto impresso em imagens de boa
qualidade. (MELLO; OLIVEIRA; SANTOS, 2012)
1.3 Documentos Antigos
Mesmo com os avanços das técnicas de OCR nos últimos anos, a maioria delas não
consegue reconhecer texto em documentos que sofreram alguma degradação. O papel é uma
superfície mais resistente que seus antecessores, mas ainda assim é considerado frágil.
Documentos antigos podem apresentar manchas no papel como resultado da degradação do
tempo ou manuseio. Em alguns casos, seja por impossibilidade de transporte ou tamanho
inadequado do papel, a digitalização desses documentos não é feita usando escâneres
convencionais. Mesmo construindo estruturas específicas para a tarefa, é comum que surjam
diferenças de iluminação na imagem obtida. Outro problema comum a documentos antigos é
absorção de tinta pelo papel. Nesse caso o conteúdo de um lado da folha pode sobrepor o de
outro. Esses fatores dificultam a utilização de OCR porque se não forem corretamente tratados
na etapa de pré-processamento podem arruinar o resultado final.
Documentos antigos podem ser úteis para aplicações modernas. Em alguns casos, sua
importância pode ir além do que está impresso, mas ter um caráter histórico. Apesar de a
computação já estar estabelecida há décadas, somente no fim do século XX surgiram as
primeiras legislações sobre o uso legal de documentos eletrônicos. Hoje, essas legislações ainda
estão se estabelecendo, mas a possibilidade de substituir documentos em papel por documentos
digitais, mantendo o valor legal, é um dos principais motivos para os esforços de digitalização
de acervos antigos. Geralmente, a digitalização de acervos antigos é seguida por um esforço de
indexação, tarefa de associar índices ao documento digital. Esses índices podem conter
informações sobre o próprio documento, metadados, que podem ajudar a identificá-lo. Alguns
exemplos são a data de criação, o autor e o título do documento. Mas para que se possa pesquisar
pelo conteúdo do documento ele precisa ser reconhecido.
Existem muitas soluções de OCR de propósito geral bem estabelecidas atualmente.
Dificilmente, uma alternativa criada para resolver um problema específico teria resultados de
19
reconhecimento semelhante a essas soluções. Ao invés de criar uma técnica específica é mais
viável realizar um pré-processamento e submeter a imagem resultante a um OCR de propósito
geral. Esse pré-processamento trataria os problemas específicos. No caso de documentos
antigos, por exemplo, podem ser aplicadas técnicas para a segmentação do plano de fundo que
tratem as diferenças de intensidade causadas pelo desgaste e ou pela diferença de iluminação
na digitalização.
1.3.1 Mapas e Plantas Baixas
Mapas e plantas baixas são tipos de documentos que possuem características que
dificultam ainda mais o reconhecimento automático. Os objetos presentes nesses documentos
atravessam gerações e suas informações podem ser úteis para trabalhos atuais nas áreas de
conhecimento envolvidas como cartografia, construção civil e arquitetura. Devido ao caráter
histórico, esses documentos também são uma expressão artística que retratam a cultura, a
filosofia e a tecnologia do tempo em que foram criados (MASINI et al., 2004). Mas o
reconhecimento automático do texto para esses documentos é dificultado pela grande
quantidade de componentes gráficos que possuem.
Representações de rios, paredes ou outros elementos dividem o espaço com o conteúdo
textual. Em alguns casos os gráficos chegam a sobrepor partes do texto. Mapas e plantas baixas
de locais e épocas diferentes possuem componentes gráficos diferentes, o que dificulta a escolha
de características que possam distingui-los de componentes textuais. Para obter bons resultados
de reconhecimento é essencial que a segmentação de texto desses documentos seja tratada de
maneira especial. Na Figura 1.1 é possível perceber alguns desses problemas.
Figura 1.1: Exemplos dos desafios para detecção de texto em (a) mapas e (b) plantas
baixas.
(a)
(b)
Fonte: produção própria.
20
Os métodos atuais para segmentação de texto nesses tipos de documento são baseados
em regras definidas por observação e por isso possuem algumas limitações. As regras, criadas
a partir de um conjunto de imagens, podem não estar preparadas para outros exemplos que os
autores não tenham encontrado. Por serem criadas a partir da observação humana, as regras
precisam ser baseadas em características interpretáveis. A maioria das soluções utiliza
heurísticas que decidem se os componentes são de texto ou gráfico a partir de características
geométricas.
1.4 Motivação e Problema
O processamento automático de mapas e plantas baixas antigos traz benefícios às áreas
que interagem com esses documentos. A conversão para o texto processável permite que
soluções existentes sejam melhoradas e que surjam novas aplicações para esses tipos de
documento.
Ambos os tipos de documento podem possuir valor histórico. O conteúdo do
documento pode possuir várias informações importantes para o entendimento da cultura,
filosofia e tecnologia de quando foi criado. Pesquisas manuais em acervos podem se tornar
pesquisas pelo conteúdo desejado, resolvidas em frações de segundo e que poderiam ser
realizadas em qualquer lugar do mundo. Quando não for necessário, o usuário sequer terá acesso
ao documento físico, o que contribui para sua preservação.
Uma das principais aplicações para mapas antigos são Sistemas de Informação
Geográfica (SIG). Esse tipo de sistema tem como propósito capturar, armazenar, analisar e
apresentar todo tipo de informação geográfica de uma localização. Uma das principais fontes
de informação para esses sistemas são mapas (alguns antigos). É através deles que é possível
entender o que aconteceu e tentar prever o que irá acontecer em uma localização. Com a
facilidade de pesquisar pelo conteúdo do mapa seria muito mais fácil associá-lo a uma
determinada região. Feito de forma automática, esse processo teria utilidade para historiadores,
geógrafos e pesquisadores de ciência da informação.
Plantas baixas antigas podem conter informações importantes para aplicações de
disciplinas relacionadas. Para realizar uma reforma ou restauração em um local é importante
conhecer a estrutura original. Mais uma vez a disponibilidade do acervo em formato digital
permite que os documentos sejam facilmente encontrados através de pesquisas sobre seu
conteúdo. Nome da construção, endereço e responsáveis são algumas das informações que
podem ser usadas para encontrar as plantas baixas, além de informações de escala.
21
1.5 Objetivos
O principal objetivo deste trabalho é criar uma técnica de segmentação de texto capaz
de lidar com imagens de mapas e plantas baixas, evitando o uso de condições e limiares
definidos empiricamente e cuja imagem com componentes de texto produza melhores
resultados ao ser submetida a soluções convencionais de OCR.
Os objetos específicos são:

Contribuir para o estado da arte de um problema ainda sem solução ótima;

Experimentar a utilização de características de problemas de domínios diferentes do
analisado;

Experimentação de uma Máquina de Vetor de Suporte como classificador de uma
classe, capaz de identificar texto;

Contribuir para a disseminação e pesquisas sobre processamento de imagens de
documentos antigos, visando a preservação da informação.
1.6 Estrutura da Dissertação
Este trabalho está dividido em seis capítulos. No primeiro é apresentada uma visão
geral sobre processamento digital de imagens e da segmentação de texto, motivações e desafios
para processar imagens de mapas e plantas baixas antigos, e os objetivos da pesquisa. O
Capítulo 2 contém o conhecimento básico relacionado à solução proposta na pesquisa. O
Capítulo 3 apresenta mais detalhes sobre segmentação de texto e o estado da arte para
processamento de imagens de mapas e plantas baixas. No Capítulo 4, está descrito o método
desenvolvido na pesquisa. Os experimentos e resultados obtidos estão no Capítulo 5. No
Capítulo 6 são apresentadas as conclusões, contribuições e sugestões de trabalhos futuros.
22
2 Conceitos Básicos
Este capítulo apresenta conceitos necessários para a compreensão do trabalho. Neste
estão reunidos conhecimentos das áreas de Processamento Digital de Imagens e Aprendizagem
de Máquina. É importante destacar que o objetivo deste capítulo não é servir como fonte de
conhecimento dessas áreas, mas apenas destacar os conceitos relevantes envolvidos no trabalho.
2.1 Processamento Digital de Imagens
Uma imagem digital pode ser interpretada como uma matriz em que cada célula (pixel)
armazena uma parte da informação da imagem original. O pixel é definido pelas coordenadas
em que se encontra na matriz e seu valor. Esse valor é interpretado como a intensidade ou cor
do pixel (MELLO; OLIVEIRA; SANTOS, 2012).
Duas características da imagem digital são definidas no momento da digitalização. A
resolução espacial, que indica a quantidade de pontos que são necessários para representar uma
polegada na imagem original e a resolução de cor, que é a quantidade de cores disponíveis para
cada pixel assumir (MELLO; OLIVEIRA; SANTOS, 2012).
O sistema de cores mais comum é formado pelas cores primárias vermelho, verde e
azul (Red, Green and Blue, RGB). Nesse sistema cada cor é codificada em uma sequência de
24 bits, 8 bits para cada cor primária. Cada uma delas é definida por um inteiro com valor de 0
a 255 e a tripla (R, G, B) define a cor do pixel. Por ser um sistema de cores aditivo (Figura 2.1),
a tripla (0,0,0) representa o preto absoluto e a tripla (255,255,255) representa o branco absoluto.
Figura 2.1: Visualização do sistema de cores aditivo.
Fora dos círculos o valor dos pixels é (0,0,0). Cada círculo equivale a uma fonte de luz com
valor máximo para seu componente (255,0,0), (0,255,0) e (0,0,255). A intersecção entre dois
círculos produz cores secundárias, resultado da soma de dois componentes. No centro da
figura está uma região branca produzida pela adição dos três componentes. Fonte: produção
própria.
As imagens coloridas podem ser representadas através de sua luminância (MELLO;
OLIVEIRA; SANTOS, 2012). Nesse caso, apenas níveis de cinza são representadas na imagem
que passa a ser chamada de imagem em tons de cinza. Usando as triplas do sistema RGB esses
23
tons são obtidos quando as três componentes possuem o mesmo valor, como os valores já
mencionados para preto e branco. Logo, esse tipo de representação precisa de uma
representação de apenas 8 bits para seus valores. Para obter o valor de luminância 𝐿 ,
convertendo uma imagem colorida para tons de cinza, pode ser usada a equação a seguir.
𝐿 = 0.299𝑅 + 0.587𝐺 + 0.114𝐵
(1)
As imagens podem ter uma representação ainda mais restrita que a de tons de cinza.
Com apenas duas cores, as chamadas imagens bitonais ou imagens binarizadas podem ser
representadas com apenas 1 bit para cada pixel. O processo de transformação para se obter esse
tipo de imagem é descrito a seguir.
2.1.1 Limiarização
A limiarização é o processo de conversão de uma imagem para uma representação
bitonal, a imagem binarizada. É esperado que nesse processo os objetos de interesse assumam
uma cor e o plano de fundo outra (em geral, as cores usadas são preto e branco). Por produzir
uma separação entre partes da imagem esse processo pode ser entendido como uma técnica de
segmentação. A dificuldade é decidir como transformar os valores para que a separação ocorra
como esperado. Uma forma simples é escolher um limiar, ou ponto de corte. Se esse ponto de
corte estiver relacionado às cores, todos os pixels com valores abaixo desse ponto serão
transformados em preto, e os demais em branco.
Existem várias técnicas de limiarização. Elas podem ser classificadas de acordo com
a aplicação do limiar encontrado ou com o algoritmo utilizado. Algoritmos globais aplicam o
mesmo limiar a toda a imagem. Já algoritmos locais dividem a imagem para que cada região
tenha um limiar correspondente. Segundo (MELLO; OLIVEIRA; SANTOS, 2012), os
algoritmos de limiarização podem ser divididos em: (i) algoritmos baseados em histograma1,
que utilizam características estatísticas da distribuição de cores ou o formato do histograma da
imagem para decidir o limiar; (ii) métodos iterativos, que partem de uma suposição inicial de
limiar e buscam a solução ótima executando várias iterações do algoritmo até que um critério
de parada seja satisfeito; (iii) algoritmos baseados em entropia2, que utilizam essa medida para
calcular o ponto de corte; (iv) e algoritmos difusos (fuzzy), que baseados no conceito da lógica
difusa, levam em consideração a probabilidade de que cada pixel possa ser objeto de interesse
ou plano de fundo.
1
Histograma é uma representação da distribuição dos dados. Para uma imagem o histograma representa a
distribuição de cores.
2
Entropia é a quantidade média de informação que uma fonte produz.
24
Além desses, existem algoritmos que utilizam novas abordagens para limiarização
como os baseados em conceitos de percepção visual. Mello (MELLO, 2010) apresentou uma
técnica de limiarização para imagens com plano de fundo complexo, capaz de lidar com marcas
disformes de tinta e degradação. O algoritmo é baseado em conceitos de percepção visual, como
o de percepção de objetos à distância. Segundo esse conceito, quanto mais distante o observador
estiver do objeto, menos detalhes poderão ser distintos; apenas as características mais marcantes
vão permanecer evidentes. Para aplicar os efeitos do distanciamento de um objeto à imagem
digital, o autor usou uma operação morfológica, que simula a perda de detalhes e
arredondamento de quinas, e uma redução no tamanho da imagem, que reproduz a ilusão de
que os objetos se tornam menores com a distância. A redução de tamanho faz com que a maioria
dos componentes pequenos, como o conteúdo impresso na imagem, desapareça. Essa imagem
é restaurada ao tamanho inicial e subtraída da imagem original. Como resultado a maior parte
do plano de fundo é removida. A limiarização final pode ser realizada com outro método de uso
geral já que a complexidade do plano de fundo foi removida.
2.1.2 Componentes Conexos
Além da intensidade dos pixels, a conectividade entre eles também pode ser usada para
separá-los. Um pixel (𝑝) de uma imagem pode possuir até oito vizinhos, dois horizontais (ℎ𝑖 ),
dois verticais (𝑣𝑖 ) e quatro diagonais (𝑑𝑖 ), como mostra a Figura 2.2. A adjacência entre pixels
pode ser tratada como (i) Adjacência-4, quando dois pixels são considerados vizinhos se
possuírem o mesmo valor e estiverem nas posições de vizinhos horizontais ou verticais; (ii)
Adjacência-8, quando são considerados vizinhos os pixels com mesmo valor e que estejam nas
posições de vizinhos horizontais, verticais ou diagonais e Adjacência-m (mista), quando pixels
de mesmo valor são considerados vizinhos nas posições horizontais e verticais e, se não
estiverem nessas posições, são avaliados como vizinhos diagonais.
De acordo com o critério de adjacência utilizado, é possível definir se existe um
caminho digital entre dois pixels da imagem. Um caminho é uma sequência de pixels distintos
em que cada pixel é adjacente ao anterior. Seja 𝑆 um subconjunto de pixels da imagem, se
existir um caminho entre dois pixels da imagem, 𝑝 e 𝑞, formado inteiramente de pixels de 𝑆,
esses dois pixels são considerados conexos. Para qualquer pixel 𝑝 em 𝑆, o conjunto de pixels
em 𝑆 conectados a ele é chamado de componente conexo (GONZALEZ; WOODS, 2007).
25
Figura 2.2: Adjacência entre pixels.
O pixel central p pode possuir até oito vizinhos, sendo dois horizontais, dois verticais e quatro
diagonais. Fonte: produção própria.
Várias características podem ser obtidas com a análise de componentes conexos. Além
de características mais simples, como as geométricas, também podem ser analisados detalhes
da forma do componente. Existem técnicas, como Descritores de Fourier, vistos em detalhes a
seguir, que criam uma representação mais genérica do componente, facilitando um
reconhecimento posterior (MELLO; OLIVEIRA; SANTOS, 2012).
2.1.3 Descritores de Fourier
Descritores de Fourier são um dos mais populares e eficientes métodos de
representação de forma existentes. Entre as vantagens que esse método apresenta estão, grande
capacidade de discriminação, baixa sensibilidade a ruídos, fácil normalização e preservação da
informação (CHERIET et al., 2007). Este método utiliza a assinatura da forma para descrever
os componentes no domínio da frequência.
Uma das maneiras de construir a assinatura de forma é usando coordenadas complexas.
Cada coordenada (𝑥(𝑡), 𝑦(𝑡)) de uma fronteira digital formada por L pixels, em que 𝑡 =
0,1, . . . , 𝐿 − 1 , pode ser expressa em termos de coordenadas complexas usando a relação
estatística descrita a seguir.
𝑠(𝑡) = [𝑥(𝑡) − 𝑥𝑐 ] + 𝑗[𝑦(𝑡) + 𝑦𝑐 ],
(2)
em que 𝑗 = √−1 e (𝑥𝑐 , 𝑦𝑐 ) é o centroide da forma calculado definido por:
1
𝑥𝑐 = 𝐿 ∑𝐿−1
𝑡=0 𝑥(𝑡) e
1
𝑦𝑐 = 𝐿 ∑𝐿−1
𝑡=0 𝑦(𝑡).
(3)
Apesar de não ser necessário, o ajuste da coordenada pelo centroide permite que a nova
representação seja invariante a translação (CHERIET et al., 2007).
Os descritores de Fourier para uma assinatura de forma 𝑠(𝑡) com 𝐿 pixels, onde 𝑡 =
0,1, . . . , 𝐿 − 1, são obtidos através da Transformada Discreta de Fourier:
26
𝐿−1
−𝑗2𝜋𝑛𝑡
1
𝑎𝑛 = ∑ 𝑠(𝑡)𝑒 ( 𝐿 )
𝐿
(4)
𝑡=0
onde 𝑛 = 0,1,2, . . . , 𝐿 − 1.
No domínio da frequência, os componentes de mais alta frequência são responsáveis
por detalhes finos, e os de mais baixa frequência determinam a forma global da imagem. Esse
comportamento pode ser usado para simplificar mais ainda a nova representação da assinatura
de forma. Se apenas os primeiros 𝑃 coeficientes forem utilizados após a transformação,
detalhes da fronteira serão perdidos. Esse comportamento é ilustrado na Figura 2.3. Isso
equivale a considerar 𝑎(𝑢) = 0 para 𝑢 > 𝑃 − 1. Nesse caso, a reconstrução da fronteira
através da transformada inversa seria dado por:
𝑃−1
𝑗2𝜋𝑛𝑘
1
𝑠̂ (𝑡) = ∑ 𝑎𝑛 𝑒 ( 𝑃 )
𝑃
(5)
𝑛=0
As vantagens dos descritores de Fourier estão ligadas às vantagens da análise de
Fourier. Os descritores são robustos a mudanças de tamanho e podem se tornar robustos a
translação e rotação através de uma normalização (MELLO; OLIVEIRA; SANTOS, 2012).
Esta normalização faz com que a escolha de outro ponto de início para a assinatura de forma
não influencie a representação dos descritores. O fator de normalização escolhido é o
componente 𝑎0 porque ele armazena a energia média do sinal e geralmente possui o maior
coeficiente, o que mantém os demais componentes no intervalo [0,1] (ZHANG; LU, 2005).
Figura 2.3: Exemplo da influência da quantidade de coeficientes usados no descritor de
Fourier.
Na figura, (a) é a imagem original e (b-f) são as formas recuperadas (transformada inversa) a
partir de descritores de Fourier com 70, 30, 15, 7 e 3 coeficientes, respectivamente. Fonte:
(“Fourier Descriptors,” 2014).
2.1.4 Morfologia Matemática
A morfologia, ou estudo da forma, é comumente relacionada à biologia. Nessa área de
conhecimento, a morfologia estuda a forma e estrutura de animais e plantas. Na computação, a
morfologia tem como objeto de estudo os componentes de uma imagem digital. Sua linguagem
27
é baseada em conceitos matemáticos da Teoria dos Conjuntos e por isso é chamada de
morfologia matemática.
A morfologia matemática utiliza ferramentas de álgebra não-linear e opera com
conjuntos de pontos, sua conectividade e forma. Suas operações podem simplificar a imagem e
quantificar e preservar as principais características da forma dos objetos. Essas operações são
predominantemente utilizadas para pré-processamento (remoção de ruídos e simplificação de
forma), melhoria estrutural de objetos (afinamento, engrossamento, envoltória convexa),
segmentação e descrição quantitativa de objetos (área, perímetro, projeções) (SONKA;
HLAVAC; BOYLE, 2014).
Normalmente, os pixels com maior intensidade são usados para representar os objetos.
Em imagens binarizadas, pixels brancos pertencem aos objetos e pixels pretos ao plano de
fundo. Isso pode exigir que seja calculada a imagem inversa ou negativa antes de aplicar uma
operação de morfologia matemática.
Essas operações, as transformações morfológicas, são obtidas através de uma relação
entre a imagem e um pequeno conjunto de pontos chamado de elemento estruturante (SONKA;
HLAVAC; BOYLE, 2014). Um elemento estruturante é posicionado de acordo com um ponto
de origem. Embora usar o centro de gravidade do elemento estruturante como origem seja
comum, a escolha da origem geralmente depende da aplicação (GONZALEZ; WOODS, 2007).
Uma transformação é aplicada movendo sistematicamente o elemento estruturante pela
imagem. Considerando que o elemento estruturante esteja sobreposto à imagem, o pixel da
imagem posicionado abaixo da origem do elemento estruturante é o pixel atual que será
modificado de acordo com o resultado da relação da imagem com o elemento estruturante.
Para compreender as operações de morfologia matemática é preciso conhecer dois
conceitos bastante utilizados nelas. A reflexão de um conjunto 𝐵, indicada por 𝐵̂, é definida a
seguir:
𝐵̂ = {𝑤|𝑤 = −𝑏, 𝑝𝑎𝑟𝑎 𝑏 ∈ 𝐵}
(6)
Se 𝐵 é um objeto de uma imagem, 𝐵̂ é formado pela inversão das coordenadas de 𝐵.
Como resultado tem-se o reflexo do objeto em relação à origem do sistema de coordenadas. Por
exemplo, o ponto (𝑥, 𝑦) de 𝐵 será substituído por (−𝑥, −𝑦) em 𝐵̂.
A translação de um conjunto 𝐵 no ponto 𝑧 = (𝑧1 , 𝑧2 ) é representada como (𝐵)𝑧 . Seu
resultado é o conjunto de pontos em B cujas coordenadas (𝑥, 𝑦) foram substituídas por (𝑥 +
𝑧1 , 𝑦 + 𝑧2 ) . Essa operação, definida pela equação a seguir, é responsável por deslocar o
elemento estruturante de acordo com sua origem.
28
(𝐵)𝑧 = {𝑐|𝑐 = 𝑏 + 𝑧, 𝑝𝑎𝑟𝑎 𝑏 ∈ 𝐵}
(7)
A erosão e a dilatação são duas operações fundamentais para o processamento
morfológico. A erosão de uma imagem 𝐴 por um elemento estruturante 𝐵, indicada por 𝐴 ⊝
𝐵, é o conjunto de pontos 𝑧 de forma que 𝐵, transladado por 𝑧, está contido em 𝐴. A equação
dessa operação é definida a seguir.
𝐴 ⊝ 𝐵 = {𝑧|(𝐵)𝑧 ⊆ 𝐴}
(8)
O resultado da erosão para uma imagem binarizada é a eliminação dos pixels brancos
que não atenderam à condição estabelecida. A estrutura do objeto é simplificada e ele pode ser
decomposto em outros mais simples (SONKA; HLAVAC; BOYLE, 2014). Por exemplo, a
erosão da Figura 2.4a pelo elemento estruturante Figura 2.4b tem como resultado a Figura 2.4c.
A dilatação de uma imagem 𝐴 por um elemento estruturante 𝐵, identificada por 𝐴⨁𝐵,
pode ser definida como o conjunto de todos os deslocamentos, 𝑧, de forma que 𝐵̂ e 𝐴 tenham
ao menos um ponto em comum. Essa operação pode ser usada para preencher buracos e
aberturas nos objetos e como consequência aumenta o tamanho original do objeto (SONKA;
HLAVAC; BOYLE, 2014). Um exemplo de resultado de dilatação pode ser observado na
Figura 2.4d. Essa operação é definida pela equação a seguir.
𝐴⨁𝐵 = {𝑧|(𝐵̂ )𝑧 ⋂ 𝐴 ≠ ∅}
(9)
Erosão e dilatação não são transformações inversas e as combinações delas em ordens
diferentes produzem resultados diferentes. A erosão seguida da dilatação, usando o mesmo
elemento estruturante, é chamada de abertura. Um exemplo desta operação é ilustrado na Figura
2.4e. Identificada por 𝐴 ∘ 𝐵 , a abertura de uma imagem 𝐴 por um elemento estruturante
simétrico 𝐵 é definida pela equação a seguir.
𝐴 ∘ 𝐵 = (𝐴 ⊝ 𝐵) ⊕ 𝐵
(10)
O fechamento é uma operação composta por uma dilatação seguida por uma erosão,
mantendo o mesmo elemento estruturante. Com isso, vales e aberturas podem ser preenchidos.
A Figura 2.4f ilustra esse resultado. O fechamento de uma imagem 𝐴 por um elemento
estruturante simétrico 𝐵, é identificado por 𝐴 • 𝐵 e definido pela equação:
𝐴 • 𝐵 = (𝐴 ⊕ 𝐵) ⊝ 𝐵
(11)
A abertura e fechamento podem ser usados para eliminar quaisquer detalhes da imagem
que sejam menores que o elemento estruturante, sem distorcer a forma geral dos objetos. Essa
característica faz com que sejam boas ferramentas para a eliminação de ruídos das imagens. Na
Figura 2.4, os itens (g) e (h) ilustram a aplicação em sequência da abertura e fechamento.
29
Figura 2.4: Exemplos de operações morfológicas.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
Dada a imagem (a) e o elemeto estruturante (b), são apresentados os resultados das operações
morfológicas de (c) erosão, (d) dilatação, (e) abertura, (f) fechamento, (g) abertura seguida de
fechamento e (h) fechamento seguido de abertura. Fonte: produção própria.
2.1.5 Histograma de Gradientes Orientados
A orientação do traçado em uma imagem tem um papel importante na diferenciação
entre vários objetos. Histograma de Gradientes Orientados (Histogram of Oriented Gradients,
30
HOG) é um método de extração de características baseado em histogramas de orientação
calculados para várias regiões da imagem.
Histogramas de orientação representam a distribuição de diferentes orientações na área
observada. A direção do gradiente é uma das abordagens mais usadas para determinar a
orientação local de um traçado. Isso se deve principalmente à sua simplicidade de
implementação e a uma certa invariância à largura do traçado (CHERIET et al., 2007).
O gradiente é a ferramenta ideal para encontrar a intensidade e a direção de um ponto
da borda de uma imagem. Seu cálculo, baseado em derivadas de primeira ordem, é capaz de
detectar a direção e a magnitude da variação de intensidade presente na imagem original. Para
uma imagem 𝑓, o gradiente é o vetor ∇𝑓 definido a seguir.
𝜕𝑓
𝑔𝑥
𝜕𝑥
∇𝑓 = [𝑔 ] = 𝜕𝑓
𝑦
[𝜕𝑦]
(12)
A norma ‖∇𝑓‖ do vetor gradiente representa a taxa de variação na direção 𝛼(𝑥, 𝑦)
desse vetor. Por representar a variação de intensidade, o vetor gradiente para um ponto possui
uma direção ortogonal à direção da borda no mesmo ponto. Essas propriedades são definidas
pelas equações a seguir:
‖∇𝑓‖ = √𝑔𝑥2 + 𝑔𝑦2
(13)
𝑔𝑥
𝛼(𝑥, 𝑦) = tan−1 ( )
𝑔𝑦
(14)
Em 2005, Dalal e Triggs (DALAL; TRIGGS, 2005) propuseram o HOG como método
de descrição de imagens. Esse método de descrição tem como princípio o cálculo de
histogramas de orientação para cada pixel da imagem. Esses histogramas são quantizados em
um pequeno número de partições 𝑝 com a qual cada pixel contribui proporcionalmente à
magnitude do gradiente naquela direção. Quando o ângulo do gradiente não estiver centralizado
em uma partição, o valor de sua contribuição deve ser dividido linearmente entre as partições
vizinhas.
A Figura 2.5 ilustra os descritores HOG obtidos para quatro imagens de caracteres
diferentes. Neste exemplo os histogramas foram quantizados em dezesseis partições, cada uma
com uma largura de 2𝜋/16 radianos e centralizada em 2𝑘𝜋/16 para 𝑘 = 0,1,2, … ,15 . É
possível notar a representação dos caracteres no descritor correspondente. Para o caractere ‘O’,
o HOG é quase uniforme em todos os ângulos. Para o ‘I’ é possível perceber uma grande
31
concentração de gradiente em sentido horizontal, causado pela maior quantidade de pixels com
variação de intensidade horizontal (MINETTO et al., 2013).
Figura 2.5: Visualização do HOG.
Colunas da esquerda para a direita: imagens de componentes isolados de imagem
representando caracteres, representação da magnitude do gradiente para cada pixel,
representação da orientação do gradiente para cada pixel e descritores HOG correspondente a
cada imagem. Fonte: (MINETTO et al., 2013).
Imagens, geralmente, possuem mais de um padrão de distribuição de pixels. Com a
intenção de representar melhor essas imagens as características dos pixels são agregadas em
células. A agregação pode ser feita através de uma simples média da contribuição de todos os
pixels na célula, mas Dalal e Triggs consideraram também a influência dos pixels nas células
vizinhas, usando uma técnica de interpolação bilinear. O uso de vetores de características por
célula provê robustez a pequenas deformações e reduz o final do vetor de características. Mas
para tornar as características robustas às diferenças de contribuição das células é necessário
realizar uma normalização.
Os autores propuseram o uso de quatro fatores de normalização para cada vetor de
características de célula. Esses fatores podem ser representados por 𝑁𝛿,𝛾 (𝑖, 𝑗) em que 𝑖 e 𝑗 são
os índices da posição da célula na imagem e 𝛿, 𝛾 ∈ {−1,1} são os deslocamentos para analisar
as células vizinhas. A equação a seguir é usada para obter os fatores de normalização para uma
célula 𝐶(𝑖, 𝑗). (FELZENSZWALB et al., 2010)
32
𝑁𝛿,𝛾 (𝑖, 𝑗) = √‖𝐶(𝑖, 𝑗)‖2 + ‖𝐶(𝑖 + 𝛿, 𝑗)‖2 + ‖𝐶(𝑖, 𝑗 + 𝛾)‖2 + ‖𝐶(𝑖 + 𝛿, 𝑗 + 𝛾)‖2
(15)
Cada fator representa a energia do gradiente para um bloco de quatro células, inclusive
𝐶(𝑖, 𝑗). O descritor HOG final para uma célula é formado pela concatenação dos vetores obtidos
com os quatro fatores de normalização. Sendo assim, considerando o uso de 9 partições, são
obtidos vetores de 36 dimensões por célula.
2.2 Reconhecimento de Padrões
O passo final para o reconhecimento de objetos é utilizar os descritores obtidos para
ele em um sistema de reconhecimento automático. Reconhecimento de padrões é uma área de
pesquisa científica cujo objetivo é encontrar funções que possam mapear objetos em um número
de possíveis classes, categorias ou rótulos (MELLO; OLIVEIRA; SANTOS, 2012). A seguir,
será descrita uma importante técnica utilizada em aplicações de reconhecimento de padrões.
2.2.1 Máquinas de Vetores de Suporte
Máquinas de Vetores de Suporte (Support Vector Machines, SVM) (CORTES;
VAPNIK, 1995) são máquinas de decisão que definem hiperplanos que levam à separação
ótima entre duas classes, provendo assim maior proteção contra erros (DAVIES, 2005). Parte
de uma nova geração de sistemas baseados em avanços na teoria de aprendizagem estatística,
as SVM estão entre os métodos mais sofisticados de aprendizagem supervisionada (MELLO;
OLIVEIRA; SANTOS, 2012). Seu conceito básico é que se os padrões não são separáveis em
sua dimensionalidade original, eles podem ser mapeados para uma dimensão suficientemente
maior em que serão separáveis. Os hiperplanos capazes de produzir essa separação são
definidos por pontos extraídos do conjunto de treinamento chamados de vetores de suporte. A
Figura 2.6 ilustra esse conceito.
Os conceitos básicos de SVM podem ser compreendidos mais facilmente quando
analisando problemas linearmente separáveis. Para um problema de classificação binária, em
que 𝑁 padrões de entrada 𝒙𝑖 são rotulados como 𝑑𝑖 ∈ {+1, −1}, a função de decisão pode ser
definida como 𝑔(𝑥) = 𝒘𝑇 𝒙 + 𝑏. Nesta, 𝒘 é um vetor de pesos ajustáveis e 𝒃 é um valor de
tendenciosidade (bias). Vários hiperplanos de separação podem existir para solucionar o
problema, mas a SVM tem como objetivo encontrar o hiperplano que possua a maior distância
(𝑟) para os padrões apresentados no treinamento. Essa distância é maximizada até que se
encontre a superfície de decisão chamada de hiperplano ótimo.
33
Figura 2.6: O treinamento de uma SVM consiste em encontrar o hiperplano que
produza a máxima separação entre as classes.
Os vetores de suporte são os pontos mais próximos do hiperplano, a uma distância r. Na
figura estão representados como círculos e quadrado preenchidos. Fonte: Adaptado de
(DUDA; HART; STORK, 2000).
Para a superfície de separação produzida pelo hiperplano ótimo, a função
discriminante pode ser definida como 𝑔(𝑥) = 𝒘𝑇𝑂 𝒙 + 𝑏𝑂 . Essa função pode ser usada para
medir a distância do ponto 𝒙 para o hiperplano ótimo (DUDA; HART; STORK, 2000). Para
um vetor de suporte 𝒙(𝑠) cujo rótulo é 𝑑 (𝑠) , a margem de separação para o hiperplano é obtida
conforme a equação a seguir.
1
𝑠𝑒 𝑑 (𝑠) = +1
𝑔(𝒙 )
‖𝒘𝑂 ‖
𝑟=
=
1
‖𝒘𝑂 ‖
−
𝑠𝑒 𝑑 (𝑠) = −1
{ ‖𝒘𝑂 ‖
(𝑠)
(16)
A distância entre vetores de suporte de classes distintas deve ser o dobro desse valor,
2/‖𝒘𝑂 ‖. Portanto, para encontrar a representação canônica do hiperplano, os valores de 𝒘 e 𝑏
são ajustados até que os sejam encontrados vetores de suporte que satisfaçam à condição
|𝒘𝑇 𝒙 + 𝑏| = 1 . Então para todos os vetores de entrada 𝒙𝑖 o resultado da classificação
correspondente 𝑧𝑖 será 𝑧𝑖 (𝒘𝑇 𝒙𝒊 + 𝑏) ≥ 1 (CHERIET et al., 2007).
Outra importante característica da SVM é o uso de funções de transformação do espaço
de características 𝜙(). Com essa transformação é possível que os dados se tornem linearmente
separáveis na nova dimensionalidade. Usando essa função 𝜙(), a de classificação passa a ser
𝑧𝑖 (𝒘𝑇 𝜙(𝒙𝒊 ) + 𝑏) ≥ 1 . Para encontrar a melhor margem de separação ainda é necessário
34
maximizar ‖𝒘‖−1 ou minimizar ‖𝒘‖2 . O problema de otimização pode ser resolvido através
da equação a seguir (BISHOP, 2006)b:
1
arg min ‖𝒘‖2
2
𝒘,𝑏
(17)
O problema de minimização dessa função dadas as restrições de desigualdade lineares
apresentadas anteriormente é um exemplo de programação quadrática. Apesar do valor de
tendenciosidade não estar presente na função a ser otimizada, ele participa implicitamente
através das restrições lineares. Utilizando multiplicadores de Lagrange (BISHOP, 2006) é
possível obter a representação dual do problema em que maximiza-se a equação:
𝑁
𝑁
𝑁
1
∑ 𝛼𝑖 − ∑ ∑ 𝛼𝑖 𝛼𝑗 𝑧𝑖 𝑧𝑗 𝑘(𝑥𝑖 , 𝑥𝑗 )
2
𝑖=1
(18)
𝑖=1 𝑗=1
com respeito às restrições:
𝛼𝑖 ≥ 0,
𝑖 = 1, … , 𝑁,
𝑁
∑ 𝛼𝑖 𝑧𝑖 = 0.
(19)
𝑖=1
Nessas equações os multiplicadores de Lagrange 𝛼 são obtidos resolvendo o problema
quadrático e 𝑘(𝒙, 𝒙′) é a função de núcleo que define implicitamente o novo espaço de
características 𝜙(𝒙) ∙ 𝜙(𝒙′) . Já o valor de tendenciosidade é determinado com base em
condições complementares descritas como:
𝛼𝑖 ≥ 0
𝑧𝑖 𝑔(𝑥𝑖 ) − 1 ≥ 0
(20)
𝛼𝑖 {𝑧𝑖 𝑔(𝑥𝑖 ) − 1} = 0
O artifício de mapeamento para uma maior dimensionalidade pode reduzir ou até
eliminar a capacidade de generalização de uma SVM. Mesmo com o uso de transformações
não-lineares, que podem evitar esse impacto sobre a qualidade da SVM, é importante levar em
consideração as restrições da separabilidade linear. Para diminuir a rigidez das margens de
separação, melhorando a capacidade de generalização, é possível incluir conceitos de variáveis
de relaxamento 𝜉. Elas representam o quanto que a restrição de separação pode ser violada.
(DAVIES, 2005) A partir dessa modificação as restrições lineares da classificação passam a ser
𝑧𝑖 (𝒘𝑇 𝜙(𝒙𝒊 ) + 𝑏) ≥ 1 − 𝜉𝑖 , em que 𝜉𝑖 ≥ 0. Como resultado as restrições do problema dual
também são modificadas e são descritas nas equações a seguir em que a constante 𝐶 funciona
como limite superior para os multiplicadores e controla a tolerância a erros de classificação
durante o aprendizado (CHERIET et al., 2007).
35
0 ≤ 𝑎𝑖 ≤ 𝐶,
𝑖 = 1, … , 𝑁,
𝑁
∑ 𝑎𝑖 𝑧𝑖 = 0.
(21)
𝑖=1
O uso de SVM pode trazer vários benefícios. Sua solução baseada em programação
quadrática garante que sejam encontrados ótimos globais, ao contrário de outras abordagens de
que podem ficar presas em ótimos locais. Além disso, o uso de uma função de núcleo para
transformar o espaço dos padrões pode resolver problemas não linearmente separáveis e os
vetores de suporte se adaptam de acordo com a dificuldade de separação para os padrões de
treinamento.
2.2.2 Sistemas de Reconhecimento Óptico de Caracteres
Sistemas de OCR combinam conhecimentos de processamento de imagens e
reconhecimento de padrões para reconhecer o texto de uma imagem. Em geral, esses sistemas
realizam um processamento off-line3 composto por três estágios: pré-processamento, extração
de características e classificação. O pré-processamento tem a finalidade de melhorar a qualidade
da imagem e segmentar os elementos que serão processados nas etapas seguintes. Tipos
diferentes de pré-processamento podem ser necessários de acordo com a aplicação. (i)
Processos de suavização e remoção de ruídos podem ser utilizados para consertar pequenas
imperfeições nos traçados dos caracteres e remover detalhes indesejados e ruídos como sal e
pimenta. (ii) Para tratar problemas de distorção (dewarp) que podem ter surgido na captura são
utilizados processos de detecção e correção de distorções. As distorções podem fazer com que
linhas que eram horizontais ou verticais no documento original sejam transformadas em linhas
inclinadas após a digitalização. (iii) Além da inclinação da página causada por distorções, os
caracteres também podem estar inclinados. Essa característica é comum em textos manuscritos
e pode ser corrigida através de processos de detecção e correção de inclinação. (iv) Um dos
processos mais importantes para preparar a imagem do caractere para descrição e classificação
é o de normalização de caracteres. Cada caractere passa a ser representado em um plano
normalizado que é utilizado por todos os outros. (v) Processos de traçado e análise de contorno
são usados para extrair as bordas ou fronteiras dos componentes. (vi) Processos de afinamento
permitem calcular uma versão afinada do componente. A aplicação iterativa de afinamento,
processo chamado de esqueletização, produz uma representação em linhas chamada de
3
O processamento off-line atua sobre o conteúdo estático, isto é, a imagem resultante após o texto ter sido escrito.
Opõe-se ao modo on-line em que, além da imagem resultante, tem-se informações obtidas durante a escrita, como
pressão, velocidade e direção.
36
esqueleto. Ele pode ser útil para analisar quantidade de traçados, ramificações e pontos de
intersecção. (CHERIET et al., 2007)
Na etapa de extração de características são utilizados processos de descrição para
representar os componentes através de atributos que sejam adequados para a etapa de
classificação. Um dos maiores desafios relacionados a esta etapa é identificar quais
características são mais significativas para o tipo de imagem tratado na aplicação. A seleção de
características é realizada visando maximizar a precisão da classificação, a eficiência do
processo ou ambos, sem interferir diretamente na etapa de classificação. Além de extrair ou
selecionar características, também existem métodos para criar novas características para
descrever os componentes. A criação geralmente é feita a partir de combinações de
características mais simples. O número de estudos sobre criação de características está
crescendo devido ao aumento do poder computacional. Isso possibilita que técnicas mais
complexas sejam utilizadas, como as que permitem que as características sejam criadas e
adaptadas automaticamente. (CHERIET et al., 2007)
A classificação utiliza processos de reconhecimento para rotular os componentes a
partir das características que os descrevem. Para o OCR, os componentes são caracteres e os
rótulos são números ou letras do alfabeto. Um classificador precisa passar por um processo de
treinamento para que seja capaz de reconhecer diferentes padrões. Durante o treinamento são
apresentados exemplos das classes do universo de interesse a ele. Ele deve ter a habilidade de
generalizar o conhecimento adquirido durante esse processo, isto é, deve ser capaz de classificar
corretamente padrões que não foram apresentados durante o treinamento.
O treinamento pode ser realizado utilizando diferentes processos de aprendizado. Os
principais paradigmas são o aprendizado supervisionado e o aprendizado não-supervisionado.
Em sistemas reconhecimento de caracteres é comum utilizar métodos que aprendam a rotular a
partir de exemplos cujos rótulos são conhecidos e utilizados no treinamento. Neste paradigma,
chamado de aprendizado supervisionado, conjuntos de exemplos de entrada são apresentados
gradualmente e um supervisor fornece as respectivas respostas para cada um deles. Na prática
não existe um supervisor. Os algoritmos de aprendizado supervisionado ajustam parâmetros
internos do método de acordo com um sinal de erro obtido ao fim da classificação. O processo
continua iterativamente até que um critério de parada predefinido seja alcançado. Esse critério
de parada pode estar relacionado à quantidade de iterações ou à taxa de erro. No aprendizado
não-supervisionado, o aprendizado acontece a partir dos próprios dados de entrada, sem
conhecimento prévio das classes a que pertencem. Esse paradigma é útil para inferir a
distribuição dos dados de entrada.
37
3 Detecção de Texto em Imagens de Mapas e Plantas Baixas
Este capítulo apresenta os principais conceitos e desafios relacionados à detecção de
texto em imagens de mapas e plantas baixas. Muitos trabalhos tratam individualmente partes
do problema, mas poucos propõem soluções automáticas para segmentar texto em imagens de
mapas e plantas baixas por completo.
3.1 Mapas e Plantas Baixas
Mapas e plantas baixas contêm informações que podem ser úteis para diversas áreas
de conhecimento. A conversão desses documentos para formato digital facilita a recuperação
de suas informações, mas suas características tornam a aquisição mais difícil. Dimensões que
fogem aos padrões, degradação e sensibilidade do material são algumas das dificuldades
enfrentadas neste processo.
A principal utilidade de analisar o conteúdo de uma imagem é permitir que o
documento possa ser recuperado a partir de uma pesquisa por um elemento que ele contenha.
O item pesquisado pode ter formato gráfico ou textual. Para procurar por um texto nesses
documentos a imagem precisa passar por etapas que vão da aquisição até o reconhecimento de
caracteres. Existem trabalhos que analisam a aquisição para documentos como mapas e plantas
baixas. Daniil et al. (DANIIL et al., 2003), por exemplo, analisaram qual a melhor forma de
aquisição de imagens de mapas antigos. Os autores tiveram como objetivo mitigar o impacto
das possíveis deformações geométricas que podem ocorrer durante a digitalização. A Figura
3.1 contém um exemplo de processo de digitalização baseado no que foi proposto pelos autores
e que poderia ser aplicado a imagens de mapas e plantas baixas.
Figura 3.1: Exemplo de processo de digitalização de documentos.
Fonte: produção própria.
O processo prevê diferentes situações de digitalização para o documento. Ele tem
início com uma análise das características do documento físico que fornece as informações
necessárias para decidir se o documento pode ser digitalizado usando escâner ou não. Se o
documento puder ser digitalizado em escâner, o processo encerra após uma tarefa de
digitalização. Caso contrário, é necessário usar técnicas de fotogrametria para obter a imagem
38
do documento. Se for utilizada uma câmera analógica, é necessário digitalizar o filme para obter
as imagens em formato digital. Por fim a imagem é submetida a um processo de retificação para
corrigir possíveis distorções.
Alguns trabalhos tratam de recuperar informações contidas em gráficos da imagem.
Eles utilizam conceitos relacionados que são úteis para a compreensão das características que
definem gráficos. A próxima seção apresenta trabalhos que tiveram esta finalidade.
3.2 Segmentação de Gráficos
A maioria das aplicações com foco em segmentação de gráficos envolve a associação
de documentos históricos com versões modernas. Esses trabalhos são importantes porque
tratam de componentes presentes nas imagens que são alvo deste trabalho, os gráficos.
3.2.1 De las Heras et al.
De las Heras et al. apresentaram um sistema para detecção de paredes em imagens de
plantas baixas. As paredes descrevem a estrutura da construção e contém informação de outros
elementos como quartos, janelas e portas (DE LAS HERAS et al., 2013). O sistema é capaz de
detectar paredes descritas com diferentes notações e de maneira não supervisionada.
Os autores propuseram algumas premissas para a identificação de paredes que são a
base para a segmentação usada no sistema. Para identificar se as paredes de uma planta atendem
a essas premissas a imagem é submetida a uma análise de histograma. Quando a imagem não
atende as premissas é aplicada uma etapa adicional de pré-processamento, a transformação em
imagem de bordas usando o detector de bordas de Canny (CANNY, 1986). Essa padronização
é essencial para o suporte às diferentes notações sem a necessidade de intervenção do usuário.
Apesar de depender das premissas definidas sobre a notação das paredes, o sistema
proposto obteve bons resultados de acordo com as medidas consideradas pelos autores. O
sistema foi capaz de identificar paredes com outros padrões de definição, alcançando taxas
melhores que as de outros trabalhos relacionados.
3.2.2 Miao et al.
Miao et al. propuseram um método para segmentação de linhas em imagens de mapas
topográficos (MIAO et al., 2013). Mapas topográficos descrevem o relevo de uma região. As
principais notações usadas para diferenciar os elementos nesse tipo de mapa são linhas ou cores.
Em alguns casos as cores não são suficientes para diferenciar a informação no mapa e as linhas
são facilmente confundidas com o plano de fundo. O método apresentado utiliza a densidade
de energia das linhas e plano de fundo para a segmentação.
39
O conceito de densidade de energia representa o grau de concentração de energia. Para
uma imagem negativa 𝑓(𝑖, 𝑗), a densidade de energia (𝐸𝑑 ) é a média da energia em sua área
(𝑀 × 𝑁). A fórmula a seguir detalha esse conceito.
2
𝑁
∑𝑀
𝑖=1 ∑𝑗=1(𝑓(𝑖, 𝑗))
(22)
𝐸𝑑 =
𝑀×𝑁
O método tem como princípio que as linhas possuem densidade de energia maior que
o plano de fundo. Mas a análise de densidade é realizada usando janelas verticais e horizontais,
desfavorecendo a detecção de linhas em direções diferentes. Para contornar essa limitação os
autores utilizaram a transformação de cisalhamento (EASLEY; LABATE; LIM, 2008). Ela é
uma transformação afim, semelhante à transformação de rotação, mas que ao contrário desta, é
capaz de transformar a direção da imagem mantendo sua estrutura e características lineares.
Isso permite que as linhas sejam detectadas em diferentes direções criadas a partir da
transformação e o resultado final é obtido através da união das detecções anteriores.
3.2.3 Leyk e Boesch
O método proposto por Leyk e Boesch também realiza a segmentação de mapas
topográficos antigos, mas tem como base a distribuição de cores (LEYK; BOESCH, 2009).
Processar automaticamente esse tipo de documento é desafiador devido à baixa qualidade das
imagens adquiridas, resultado de envelhecimento e manuseio inapropriado. O método proposto
realiza a segmentação de imagens coloridas com base em um agrupamento iterativo e não
supervisionado que identifica as camadas de cor do mapa topográfico.
Enquanto os autores do artigo referenciado na seção anterior utilizaram as linhas, estes
utilizaram as cores dos mapas topográficos para identificar as informações de relevo que elas
representam. A segmentação é o resultado de quatro etapas.
1) Agrupamento baseado na homogeneidade das cores dos pixels. Esta etapa define os
pixels que representam cada camada de cor.
2) Definição dos pixels que representam as sementes para o crescimento de região. A partir
do agrupamento na etapa anterior, alguns pixels são definidos como semente de acordo
com as suas distâncias dos protótipos.
3) Crescimento de região a partir das sementes definidas.
4) Pós-processamento a partir de filtros e testes de vizinhança para melhorar a
homogeneidade. Nesta etapa são examinados os pixels que não foram inclusos no
crescimento de região.
Outros trabalhos apresentam soluções que têm como objetivo recuperar informações
em formato textual contidas na imagem. Na seção a seguir são descritos alguns deles.
40
3.3 Detecção, Segmentação e Recuperação de Texto
A recuperação da informação de texto em uma imagem é abordada de diferentes
formas. Existem métodos para detectar o texto com base em classificador, segmentar o texto
usando características da imagem e recuperar na imagem um conteúdo de texto fornecido pelo
usuário. A seguir estão alguns trabalhos que utilizam esses métodos.
3.3.1 Karaoglu, Fernando e Tremeau
Os autores (KARAOGLU; FERNANDO; TREMEAU, 2010) propuseram um método
de detecção e localização de texto em fotos de ambientes abertos ou fechados. O método, que
localiza e extrai texto automaticamente, é robusto a diferenças de tamanho de fonte, estilo,
diferenças de iluminação, sombras, imagens com baixo contraste e outras distorções. Suas
etapas são:
1) Limiarização – Algoritmo de limiarização que utiliza informações globais e locais, bem
como características complexas da imagem para encontrar o limiar adequado. É robusto
ao tamanho e tipo da fonte de texto. As regiões da imagem resultante são consideradas
candidatos a texto e classificadas nas etapas seguintes.
2) Extração de características – Algumas características das regiões obtidas são calculadas
para que um classificador possa decidir se ela representa um texto ou não. As
características utilizadas dividem-se entre geométricas ou de regularidade de forma.
Além dessas também é utilizada uma característica proposta pelos autores, a Corner
Based Interpolated Feature, CBIF. Esta é capaz de recuperar informações de formas a
partir dos pontos de canto, muito útil para quando as formas tenham sofrido
deformações ou apresentem ruídos.
3) Classificação – As características são usadas em um classificador para decidir se a
região é de texto. Os autores escolheram um classificador supervisionado, o Random
Forest (BREIMAN, 2001).
4) Formação de palavras – Os caracteres classificados como texto na etapa anterior são
agrupados para formar palavras. Este processo é baseado na distância entre as regiões
dos caracteres.
O método obteve bons resultados. As características proporcionaram robustez a
sombras, iluminação não uniforme, reflexos, tipos de fonte, e outros fatores. Mesmo assim, por
não ter sido criado para segmentação de texto em imagens ricas em gráficos, as características
desses documentos inviabilizariam a aplicação direta desse método nesse tipo de imagem.
41
3.3.2 Weinman
Weinman propôs um método para reconhecer nomes de lugares de mapas digitalizados
(WEINMAN, 2013). O autor assume que as posições das palavras no mapa já são conhecidas
e as compara com um índice de topônimos para identificar a região que o mapa representa.
O método é representado por uma rede bayesiana. A entrada é a imagem de uma
palavra. Essa imagem é transformada em texto a partir de um sistema de reconhecimento de
texto. O texto é transformado em topônimo levando em consideração a probabilidade de que
ela represente um texto geográfico. A partir do topônimo encontrado, seu posicionamento no
mapa digitalizado e o alinhamento global do mapa, é calculada a coordenada final da imagem.
Como última etapa as hipóteses de topônimos são atualizadas levando em consideração as
coordenadas definidas para o mapa.
O uso do índice de topônimos e da referência de posicionamento para decidir os
topônimos diminuíram os erros de OCR. Segundo o autor, apesar de um terço das palavras dos
mapas não possuírem referência geográfica, os erros de reconhecimento foram reduzidos em
19%.
Apesar de estar relacionado ao tipo de imagens abordado neste trabalho, o método de
Weinman não leva em consideração a segmentação do texto. O posicionamento desses
componentes é considerado já conhecido.
3.3.3 Dovgalecs et al.
O sistema proposto por Dovgalecs et al. é capaz de encontrar uma palavra ou padrão
a partir de uma pesquisa realizada pelo usuário (DOVGALECS et al., 2013). O método, que é
independente de segmentação, é dividido em duas etapas. Na primeira é realizada uma extração
de características da imagem e na segunda é realizada a busca pelo conteúdo fornecido.
Para a extração de características off-line foram usadas características SIFT (LOWE,
1999). As características são agrupadas de maneira não supervisionada para formar as
representações visuais de palavra. Para aumentar a velocidade de comparação com o conteúdo
pesquisado os autores propuseram pré-compilar representações de Bag of Visual Words
(BoVW) segundo a configuração proposta em (RUSIÑOL et al., 2011).
A pesquisa online pelo conteúdo, iniciada quando o usuário marca uma região a ser
pesquisada, é dividida em duas etapas. A primeira é a detecção de zonas candidatas e a segunda
é o filtro de falsos positivos usando propriedades da imagem. As zonas restantes são submetidas
a uma comparação para encontrar a que mais se adequa ao conteúdo pesquisado.
O método foi aplicado a imagens de documentos históricos, mas sua abordagem de
detecção de palavra pesquisada não contribui para a segmentação de texto nessas imagens. O
42
método é independente de segmentação e utiliza características específicas para a pesquisa de
palavras.
3.3.4 Vassilieva e Fomina
As autoras propuseram um algoritmo para detecção de texto em imagens de gráficos
(VASSILIEVA; FOMINA, 2013). O texto em gráficos tem características únicas. Ele não é
como texto em documentos nem em imagens de cenários naturais. Nos gráficos os textos
geralmente possuem alto contraste e plano de fundo uniforme, como em imagens de
documentos, mas são textos pequenos como em imagens de cenários naturais. Por isso as
autoras propuseram um algoritmo para detectar localização, orientação e tamanho de todas as
regiões de texto em uma imagem de gráfico.
O algoritmo é dividido em três passos.
1) Detecção de caracteres – Os caracteres são detectados a partir de análise de
componentes conectados. São usadas características como tamanho, posição na
imagem, densidade de pixels, área e razão de aspecto.
2) Detecção de linhas de texto – É aplicada a Transformada de Hough (DUDA; HART,
1972) à imagem com os potenciais caracteres detectados no passo anterior. As linhas
são consideradas como elementos que contêm três ou mais pontos e filtradas a partir de
regras baseadas nas propriedades de uma linha, densidade de pontos sobre a linha,
número de linhas paralelas e ortogonais para um ponto e a quantidade de pontos
compartilhados com outras linhas.
3) Agrupamento de caracteres – Os pontos detectados sobre as linhas são analisados para
que sejam agrupados em palavras e frases.
Segundo os experimentos realizados pelas autoras o uso do algoritmo para criar a
entrada do reconhecimento de caracteres produziu uma melhoria de até 20 vezes no
reconhecimento. O maior ganho de reconhecimento foi para textos não horizontais, já que o
algoritmo detecta, além da posição, a orientação do texto.
Apesar de serem ricas em componentes gráficos, o tipo de imagem alvo do método
proposto é diferente de mapas e plantas baixas. Para este último, além da irregularidade dos
componentes gráficos, o próprio texto surge em diferentes formatos e orientações. A
simplicidade das características e algumas premissas adotadas inviabilizam a aplicação deste
método para imagens de mapas e plantas baixas.
3.3.5 Tombre et al.
Tombre et al. propuseram um método para segmentação de texto e gráfico com foco
em imagens ricas em gráficos. O método também possui um pós-processamento para recuperar
43
componentes de texto que colidiram com gráficos (TOMBRE et al., 2002). A segmentação
texto/gráfico é realizada através de análise dos componentes conectados. Durante o
processamento são criadas três camadas de conteúdo, textos, gráficos e pequenos componentes
alongados. Essa última armazena componentes a serem tratados posteriormente para detecção
de linhas tracejadas ou extração de caracteres.
As regras usadas para segmentação são baseadas em propriedades espaciais dos
componentes. Área, razão de aspecto e as dimensões dos componentes são usados para
classifica-los como texto. Os componentes classificados como texto são avaliados novamente
sobre sua densidade e alongamento para reclassificá-los como pequenos componentes
alongados. Os demais componentes são considerados gráficos. Os limiares usados nas
classificações são definidos empiricamente, de acordo com as respectivas propriedades.
Os componentes da camada de texto são agrupados para formar palavras. Esse
agrupamento é realizado de acordo com o alinhamento e a distância entre componentes de texto.
Uma palavra é formada se os componentes possuírem o mesmo alinhamento e a distância for
menor que um limiar relativo à altura média das palavras no alinhamento.
Por fim é realizado um pós-processamento para recuperar caracteres que colidiram
com gráficos. Para isso os autores assumiram que o texto a ser recuperado está em forma de
palavras, e não de caracteres isolados. Também consideraram que as palavras não colidem por
completo com gráficos, alguns caracteres da palavra devem ter sido encontrados na
segmentação realizada anteriormente.
A recuperação desses caracteres é feita em duas etapas. Na primeira é estimada a região
de busca, levando em consideração a direção do texto usado como base. Se o texto for formado
por apenas um componente, a região de busca é um círculo ao redor dele. Se algum componente
da camada de pequenos componentes alongados estiver na região de busca de uma palavra, esse
componente é restaurado e adicionado à palavra. Os componentes da camada de gráficos são
restaurados a partir de uma análise de esqueleto e de suas conexões.
O método tem a grande vantagem de considerar a recuperação de elementos que
colidiram com gráficos. Mas a segmentação considera características espaciais simples e com
limiares de classificação definidos empiricamente. Essas escolhas limitaram a capacidade de
generalização do método.
3.3.6 Ahmed et al.
Ahmed et al. propuseram um método para a segmentação de texto e gráficos de
imagens de plantas baixas (AHMED et al., 2011). Com base no método de Tombre et al.
(TOMBRE et al., 2002), os autores propuseram um método especializado para o cenário
44
escolhido. Ahmed et al. trataram componentes específicos de plantas baixas, como paredes
externas e linhas finas, para reduzir o erro na segmentação do texto.
As paredes externas são removidas antes da segmentação para evitar que elas sejam
classificadas incorretamente como texto. As plantas baixas também podem possuir linhas finas
que colidem com o texto dificultando o reconhecimento. Esses elementos são removidos a partir
de operações morfológicas com parâmetros definidos empiricamente.
A imagem pré-processada é submetida a uma análise de componentes conectados para
realizar a segmentação texto/gráfico. Ela é realizada utilizando a informação de área dos
componentes. Limiares definidos sobre essa propriedade são usados para definir a classificação
como texto ou gráfico.
Alguns elementos gráficos são classificados incorretamente e considerados texto.
Esses elementos pequenos são removidos levando em consideração sua área, altura, largura e
densidade. Os elementos gráficos maiores são removidos levando em consideração a altura e
largura dos elementos restantes.
A recuperação é realizada para o título da planta baixa e para caracteres que tenham
sido removidos por colidirem com elementos gráficos. A recuperação do título é feita usando
uma operação de espalhamento na imagem das paredes externas, removidas inicialmente. Os
elementos que possuírem densidade e largura dentro de limites estabelecidos empiricamente
são considerados título e recuperados para a imagem de texto. A recuperação de caracteres que
colidiram também é realizada com espalhamento. A imagem de texto é duplicada e são
executados separadamente o espalhamento vertical e horizontal. A imagem resultante da união
das imagens de espalhamento é submetida a uma análise de componentes conectados e os
elementos da imagem original que estiverem dentro da caixa de contorno dos componentes
encontrados são recuperados.
Os valores para a maioria dos parâmetros de segmentação foram definidos
experimentalmente pelos autores. As premissas usadas sobre plantas baixas e a definição
empírica dos limiares para classificação dos componentes dificultam a generalização do
método. Além disso o processamento é extremamente custoso o que pode inviabilizar o uso do
método em algumas aplicações.
3.3.7 Tarafdar et al.
Tarafdar et al. apresentaram uma abordagem para encontrar palavras pesquisadas em
imagens de documentos gráficos (TARAFDAR et al., 2013). A abordagem é dividida em duas
etapas. Na primeira, componentes isolados são detectados usando características invariantes a
rotação e comparados aos caracteres pesquisados. Devido à sobreposição de caracteres com
45
elementos gráficos, alguns caracteres não são encontrados na pesquisa inicial. A segunda etapa
encontra esses caracteres possivelmente removidos a partir de informações estimadas nas
regiões candidatas a resultado da pesquisa. Por fim o resultado do reconhecimento é validado
com base na posição, tamanho, orientação e distância entre caracteres.
Para reduzir o erro da pesquisa e facilitar a recuperação de texto não reconhecido,
linhas longas são removidas da imagem no início do processamento. As linhas longas são
identificadas após a esqueletização e vetorização da imagem. Linhas longas sem pontos de
junção são consideradas elementos gráficos removidas da imagem na qual será realizada a
pesquisa. Os pontos de junção são mantidos porque podem conter caracteres sobrepostos que
serão recuperados em etapas posteriores do método.
O reconhecimento de caracteres é realizado a partir de características invariantes a
rotação, translação e escala. Os autores observaram resultados superiores ao usar FourierMellin (ADAM et al., 2000) para descrever as formas. Essas características foram usadas para
reconhecimento usando SVM.
Os caracteres não reconhecidos da pesquisa são detectados usando SIFT (Scaleinvariant Feature Transform) (LOWE, 1999). O caractere não encontrado é procurado apenas
em uma região candidata, estimada a partir do posicionamento dos demais caracteres
encontrados.
Por fim é feita uma validação do resultado. O resultado é considerado válido se for
verificada a compatibilidade entre os caracteres encontrados. Essa verificação considera a
posição, tamanho e orientação dos caracteres presentes no resultado.
Por ser uma abordagem para encontrar texto pesquisado ela pouco contribui para uma
segmentação de texto genérica. O pré-processamento para remoção do gráfico é simples e a
recuperação de caracteres com colisão utiliza o conhecimento da palavra pesquisada. O tipo de
descritor utilizado é adequado para o reconhecimento de padrões mais controlados, mas não
seria adequado para discriminar texto e gráficos em imagens de mapas e plantas baixas. Nessas
imagens existe muita variedade de dentro das próprias classes.
3.3.8 Almazán, Fornes e Valveny
Almazán, Fornes e Valveny propuseram um método de extração de características que
se adapta à forma descrita (ALMAZAN; FORNES; VALVENY, 2013). Esse método é capaz
de realizar tarefas de reconhecimento de formas manuscritas. Os autores propuseram uma
adaptação da extração de características baseada HOG que foca a descrição nas regiões mais
discriminantes da forma.
46
O HOG utiliza a informação de gradiente dos pixels como base para a extração de
características. São calculadas a orientação e a magnitude do gradiente de intensidade para cada
pixel e, em seguida, a imagem é dividida em uma grade uniforme de células. Para cada uma
delas é calculado um histograma de gradientes. Os histogramas são transformados em vetores
de características que podem ser usados para classificar a imagem.
Os autores propuseram uma nova abordagem para a extração de características HOG.
Ao invés de uma grade rígida, a extração é feita sobre um conjunto de pontos da forma que
deve ser descrita, chamados focos. Os focos são definidos a partir da subdivisão da imagem de
acordo com o centro geométrico do nível anterior. No primeiro nível, o foco é o centro
geométrico do componente. Esse centro é usado para dividir o componente em quatro subregiões. O centro geométrico dessas sub-regiões são os focos do segundo nível. Assim segue a
subdivisão e definição de focos até o nível determinado. As características são extraídas de
subimagens definidas para cada ponto de foco. O tamanho dessas subimagens depende da
quantidade e do tamanho das células de extração HOG. A figura a seguir ilustra esses conceitos.
Figura 3.2: (a-c) Detecção de focos em níveis diferentes. (d) Grid para extração de
características criado a partir dos focos.
Fonte: (ALMAZAN; FORNES; VALVENY, 2013).
O novo descritor HOG melhorou o desempenho de classificação de formas. O uso dos
focos também permitiu que o descritor não sofresse com diferenças de razão de aspecto da
imagem. Isto é, ele é capaz de comparar formas em imagens com razões de aspecto diferentes.
Mas grandes diferenças de tamanho têm impacto negativo sobre o método. Seu uso para
imagens muito pequenas, como caracteres isolados, produz um número muito grande de
características sem representatividade. Para imagens maiores pode ser necessário usar um
número maior de focos, aumentando o número de características e, consequentemente, a
complexidade para usá-las como descritores.
47
3.3.9 Minetto et al.
Minetto et al. propuseram o uso de uma versão modificada de HOG como descritor
para melhorar o reconhecimento de texto em imagens de ambientes externos (MINETTO et al.,
2013). O descritor possibilitou melhorias nos resultados de detecção e reconhecimento de texto
quando usado como filtro de pós-processamento para reduzir erros de classificação entre texto
e gráfico.
O T-HOG tem como primeira etapa a normalização de tamanho e contraste. A
subimagem de entrada é redimensionada para que tenha uma altura definida empiricamente,
mantendo a razão de aspecto. Essa redução de tamanho deve remover ruídos e outros detalhes
desnecessários enquanto o texto continua legível. Os autores consideram que apenas a
informação de brilho é necessária para reconhecer os caracteres, por isso as subimagens também
são convertidas para tons de cinza. Para reduzir a influência de diferenças de iluminação,
sombras e reflexos, ainda é realizada uma normalização de contraste.
O descritor proposto tem como princípio que imagens de objetos complexos
geralmente possuem diferentes distribuições de gradiente em diferentes regiões da imagem. A
grade de células do algoritmo tradicional é substituída por uma divisão horizontal da imagem
no T-HOG. Essa abordagem de divisão simples proporciona maior capacidade discriminativa
para os elementos que os autores consideraram (linhas de texto horizontais).
Os autores também consideraram o limite entre as células. Se rígidos, quaisquer
alterações no posicionamento do texto dentro das subimagens iriam causar grandes distorções,
já que partes das letras saltariam de uma célula para outra. Para reduzir esse problema as células
são definidas por funções suaves de peso. A Figura 3.3 ilustra essas funções.
Figura 3.3: Funções de peso para as células do HOG.
Fonte: (MINETTO et al., 2013).
O T-HOG não é eficiente como detector de texto, mas é um bom filtro pósprocessamento. Por depender de um tamanho fixo de subimagem para análise, o uso do T-HOG
como detector exigiria várias tentativas de detecção, percorrendo várias versões
redimensionadas da imagem original. O uso no pós-processamento possibilitou a redução de
48
falsos positivos na detecção e reconhecimento automático de texto. Mesmo com os bons
resultados de pós-processamento esse descritor não é adequado para problemas de detecção de
texto em imagens de mapas e plantas baixas já que esse tipo de documento pode possuir texto
em diferentes orientações e até mesmo escrita cursiva.
3.3.10 Biswas e Das
Biswas e Das apresentaram dois métodos pra extração de texto de imagens de mapas
digitalizados (BISWAS; DAS, 2012). O primeiro utiliza operações de morfologia matemática
para agrupar símbolos e desvio padrão para classificar os componentes em texto ou não texto.
O segundo método realiza a extração de texto a partir de análise de intensidade.
Os métodos diferem desde o pré-processamento. Para o método baseado em operações
de morfologia matemática (método-1) é usada a imagem binarizada, criada a partir de uma
limiarização global. O método baseado na análise de intensidade (método-2) recebe como
entrada a imagem transformada para tons de cinza.
A partir da imagem binarizada o método-1 aplica operações morfológicas para
segmentar elementos textuais. Linhas são removidas pelas operações e símbolos menores são
removidos a partir de limiares empíricos baseados na média e no desvio padrão das medidas
dos componentes. O método considera o comportamento do texto apenas na vertical e
horizontal e os elementos estruturantes utilizados seguem esse princípio.
O método-2 utiliza a imagem em tons de cinza para detectar o texto a partir da análise
de intensidade. Para isso a imagem é dividida em blocos de tamanho fixo que são submetidos
à análise. O princípio dessa análise é que os valores de intensidade variam mais em regiões de
texto que em outras regiões do mapa. Os blocos são analisados e de acordo com a diferença de
intensidade são encontradas as linhas que possuem texto.
Apesar de terem sido capaz de segmentar boa parte do texto nos experimentos
apresentados pelos autores, os métodos possuem algumas deficiências. Ambos falham quando
o tamanho do texto é muito grande e não compacto o suficiente para que sejam observadas as
características que os métodos esperam. Além disso, o método-1 é limitado à extração de texto
horizontal ou vertical, e o método-2 apenas horizontal. Não é raro que em imagens de mapas
ou plantas baixas os textos sejam apresentados em inclinações menos regulares.
3.3.11 Shi et al.
Shi et al. propuseram uma abordagem para detecção de texto que utiliza um grafo de
Regiões de Extremos com Estabilidade Máxima (Maximally Stable Extremal Regions, MSER)
(SHI et al., 2013). Após a detecção das MSERs da imagem original é construído um grafo,
usando as MSERs como vértices, para classifica-los como textuais ou não textuais.
49
MSER é um detector de região robusto a mudanças de perspectiva, escala e iluminação
(MATAS et al., 2004). Como o texto geralmente tem um contraste diferente do plano de fundo
e geralmente possui a mesma cor, MSER torna-se adequado para detecção de texto. Mas as
MSERs resultantes de uma imagem não são apenas de texto, por isso os autores propuseram
uma abordagem para detectar se as regiões contêm ou não texto.
Um modelo em grafo foi construído para integrar diferentes informações usadas para
classificar as MSERs. Para a construção do grafo cada MSER é considerado um vértice e os
vértices estão interligados por arestas não direcionadas se as MSERs satisfizerem critérios que
levam em consideração a localização espacial, a cor o tamanho das regiões.
O grafo é usado para decidir se as MSERs são de texto ou não a partir da minimização
da função de custo. A função de custo do grafo é resultado de duas outras funções, a função de
custo unitário, que leva em consideração características de um vértice, e a função de custo de
pares, que analisa diferenças entre vértices vizinhos. O custo unitário representa a penalidade
de classificar um vértice como texto ou não texto e é calculado com base no resultado dessa
classificação.
Os autores utilizaram treze características para representar as MSER e treinar um
classificador supervisionado para estimar a possibilidade dela ser uma região de texto. Dentre
elas estão características de gradiente, obtidas usando HOG. As demais características são
regularidade, que descreve se a forma possui muitas curvas e quinas; uniformidade da largura
do traço, que descreve se o traço tem a mesma largura ao longo da forma; e ocupação, que
descreve o quão preenchida é a região.
A função de custo de pares visa reduzir erros da classificação isolada dos MSERs. Ela
representa uma penalidade pela descontinuidade entre componentes vizinhos do grafo. Com
esta função, se as características de dois nós vizinhos são similares, a penalidade por classificalos de maneira diferente deve ser grande. Por outro lado, se as características são diferentes, a
penalidade deve ser pequena. Para esta função as características observadas são as distâncias
geométrica e de cor das MSERs.
A classificação final das MSERs é realizada utilizando o grafo construído.
Considerando que existem dois vértices fixos representando as classes texto e não texto, todos
os vértices de MSERs estariam ligados a eles com arestas cujos pesos são inversamente
proporcionais ao respectivo custo. Isto é, se o custo unitário de classificar um vértice como
texto é pequeno, o peso da aresta que liga ele ao vértice da classe texto é grande. Uma relação
semelhante pode ser observada para as arestas que ligam MSERs vizinhos. Se o custo de pares
50
para dois vértices vizinhos é pequeno, o peso da aresta que os une é grande. Utilizando o grafo,
a minimização das funções de custo pode ser resolvida encontrando o corte mínimo.
Após a detecção do texto ainda são realizadas algumas tarefas de pós-processamento.
Elementos de texto próximos ou em colisão são agrupados e posteriormente divididos em
palavras. Para reduzir a ocorrência de falsos positivos, as palavras formadas têm sua altura
normalizada e são submetidas a uma classificação para confirmar se realmente são compostas
por texto. Um classificador supervisionado é usado para analisar janelas da palavra intercaladas
por um passo de tamanho definido.
A abordagem proposta teve bons resultados, principalmente em precisão. Segundo os
autores, alguns elementos de texto não foram detectados pelo MSER devido à instabilidade da
cor causada pela diferença de iluminação em algumas imagens. Mas o uso do grafo para integrar
as informações de componentes isolados e de seu contexto, bem como a minimização do custo
utilizando corte mínimo, facilitou a remoção de elementos não textuais. Apesar dos resultados,
a dependência de informações de cor e rigidez do modelo de classificação escolhido dificultam
a generalização dessa abordagem para imagens como mapas e plantas baixas, em que a maioria
de texto e gráfico possuem a mesma cor e existe uma grande variedade no formato do texto.
3.3.12 Pratim Roy et al.
Pratim Roy et al. propuseram um método capaz de segmentar caracteres com colisão
de diferentes orientações e tamanhos (PRATIM ROY et al., 2012). Alguns documentos gráficos
como mapas e plantas baixas possuem texto com diferente orientação, espaçamento interno e
até mesmo com alguma curvatura. Essas características dificultam o reconhecimento
automático. Além disso quando ocorrem colisões a segmentação do texto é mais complexa que
quando existe apenas texto horizontal. Os autores propuseram uma abordagem de segmentação
direcionada a esse tipo de imagem.
O reconhecimento de caracteres é uma etapa essencial ao modelo proposto. Já que o
reconhecimento deve ser independente de orientação, as características usadas para descrever
os componentes devem ser invariantes a rotação. Os autores utilizaram uma técnica de zoning,
baseada na envoltória convexa, e a informação angular dos pixels de contorno para tornar as
características invariantes a rotação. Uma SVM foi utilizada como classificador para estimar a
probabilidade de um componente ser um caractere conhecido.
A primeira etapa do método é a detecção de componentes com colisão. A partir da
imagem de uma palavra são identificados os componentes conectados para que seja detectada
a colisão. Cada componente é submetido ao reconhecimento automático e, de acordo com a
51
probabilidade obtida, o componente pode ser segmentado diretamente ou seguir para o processo
de segmentação do método.
As grandes lacunas deixadas no plano de fundo ao segmentar caracteres com colisão
são utilizadas para detectar as zonas de segmentação. Para lidar com a possibilidade de texto
em diferentes orientações são utilizadas propriedades do casco convexo. Essas propriedades
são utilizadas para encontrar os pontos de segmentação iniciais. Os pontos de segmentação
iniciais são candidatos a criar linhas de segmentação que dividem o componente com colisão
em componentes primitivos.
Os componentes primitivos podem ser caracteres ou partes de um caractere. Para
melhorar o resultado final da segmentação esses primitivos são mesclados com a aplicação de
um algoritmo de programação dinâmica. Esse algoritmo utiliza diversas hipóteses de
segmentação e a taxa de reconhecimento para os segmentos primitivos para encontrar a melhor
segmentação.
Apesar de considerar a possibilidade de diferentes orientações e a colisão com
gráficos, algumas premissas adotadas dificultam sua aplicação a problemas de segmentação de
texto em mapas e plantas baixas antigas. Depender de reconhecimento para detectar colisão
pode atrapalhar quando existirem fontes de estilo diferente ou texto em escrita cursiva. Apesar
de ter sido aplicado a problemas de imagens de gráficos, o método utiliza apenas características
do texto para a segmentação.
3.3.13 Mello e Machado
Mello e Machado propuseram um algoritmo para segmentação de texto em mapas e
plantas baixa (MELLO; MACHADO, 2014). O algoritmo é composto por quatro passos. O
primeiro, mais simples, apenas detecta se o papel usado é texturizado ou não. Como um papel
texturizado indica uma variação de tons, foi analisado o desvio padrão dos tons do histograma
(em imagens em tons de cinza). Se o desvio padrão dos tons mais claros (com valores acima de
130) for menor que 10, o papel é considerado texturizado. Nesse caso, a imagem passa por um
processo de remoção de plano de fundo. Essa remoção é feita através do método de
segmentação baseado na percepção de objetos à distância (MELLO, 2010), binarizando a
imagem final. No passo seguinte, segmentação do texto, elementos muito grandes ou muito
pequenos são removidos, seguido da remoção de margens e aplicação de morfologia
matemática para remoção da maior parte das figuras. O terceiro passo é a remoção de linhas
para evitar a presença desses objetos na imagem. O quarto e último passo cuida da restauração
de elementos de texto erroneamente eliminados. Exemplos da aplicação desse algoritmo podem
ser vistos na Figura 3.4.
52
Apesar de ter sido desenvolvido com parte da pesquisa realizada para esta dissertação,
o algoritmo de (MELLO; MACHADO, 2014) é uma abordagem diferente do sistema proposto
neste trabalho. As regras predefinidas foram substituídas por um método que envolve
aprendizagem de máquina para realizar a segmentação
Figura 3.4: Aplicação do algoritmo de Mello e Machado a algumas imagens de mapas a
plantas baixas.
(a)
53
(b)
54
(c)
55
(d)
(a) e (c) são as imagens em tons de cinza e (b) e (d) os resultados obtidos. É possível perceber
que boa parte dos elementos de texto foram mantidos. Fonte: (MELLO; MACHADO, 2014).
56
4 Método Proposto
Neste capítulo será apresentada a solução proposta para segmentação de texto de
imagens de mapas e plantas baixas. Cada etapa do método desenvolvido durante a pesquisa será
detalhada e justificada.
Analisando o estado da arte, apresentado no Capítulo 3, foi possível perceber que
poucos autores trataram de segmentação de texto para mapas e plantas baixas como é o objetivo
deste trabalho. Os métodos baseados em pesquisa de palavras (DOVGALECS et al., 2013;
TARAFDAR et al., 2013) não servem para indexar o conteúdo desses documentos para
pesquisas futuras e pouco contribuem para a segmentação de texto. Quando utilizam alguma
segmentação, é baseada em características simples, já que o maior esforço é direcionado às
características usadas para reconhecer o conteúdo pesquisado na imagem. Até mesmo os
trabalhos que propuseram métodos de segmentação de texto (AHMED et al., 2011; BISWAS;
DAS, 2012; PRATIM ROY et al., 2012; TOMBRE et al., 2002) apresentaram algumas
limitações relacionadas à escolha de características e ao método de classificação.
Neste trabalho, objetivou-se a criação de um método de segmentação de texto para
imagens de documentos ricos em gráficos, como mapas e plantas baixas. Decidiu-se também
que o novo método não deveria depender de regras definidas específicas para as imagens
observadas. Para o desenvolvimento, foram usadas diferentes técnicas de processamento de
imagens e reconhecimento de padrões. Essas técnicas foram aplicadas em quatro etapas
distintas, pré-processamento, detecção de caracteres, detecção de sequências e recuperação.
Na Figura 4.1, está representado o processo de execução da técnica proposta. No préprocessamento é aplicada uma técnica de limiarização e alguns componentes cujas
características não poderiam ser observadas em componentes textuais, são removidos. Os
restantes são submetidos a duas abordagens de reconhecimento de padrões. A primeira usa as
características dos componentes para detectar caracteres. A segunda utiliza outro conjunto de
características para detectar texto em formato de sequências de caracteres. Por fim, são
recuperados os componentes que estiverem próximos aos que tiverem sido classificados como
textuais.
Figura 4.1: Diagrama da visão geral do processo de execução do método proposto.
Fonte: produção própria.
57
4.1 Pré-processamento
O pré-processamento é o primeiro subprocesso que modifica a imagem. Nele são
removidas partes indesejadas da imagem e é feita a divisão em componentes conectados que
são usados nos subprocessos seguintes. A Figura 4.2 contém o diagrama do pré-processamento.
Figura 4.2: Diagrama do subprocesso de pré-processamento.
Fonte: produção própria.
As primeiras operações sobre a imagem de entrada são para ajustá-la ao padrão
esperado pelo algoritmo. Primeiro, é avaliado o tamanho da imagem. Se ela possuir alguma
dimensão maior que 5000 pixels, ela é redimensionada, com respeito à sua razão de aspecto
original, para que a maior dimensão respeite esse limite. A redução no tamanho é necessária
porque muitas imagens possuem dimensões muito maiores que podem inviabilizar
computacionalmente a aplicação do método. O limite foi definido por observação, de forma
que todo o texto na imagem ainda fosse legível. A dimensão de cores também é avaliada. A
maioria dos mapas e plantas baixas antigos possui pouca informação em cores, optou-se por
utilizar imagens em tons de cinza, convertendo as que não estiverem nesse formato. A Figura
4.3 ilustra esses ajustes para uma imagem de mapa possuía largura de 8192 pixels.
A limiarização proposta em (MELLO, 2010) é aplicada na imagem em tons de cinza
para remover o plano de fundo irregular dos documentos antigos. Como descrito na Seção 2.1.1,
esse método tem como princípio o efeito que a distância de um objeto tem sobre a percepção
de suas características. Inicialmente, é realizada uma transformação na distribuição de
intensidade da imagem para que os valores ocupem toda a faixa possível, de 0 a 255. Esse
ajuste, cujo resultado pode ser observado na Figura 4.4a, é chamado equalização de histograma
e aumenta o contraste e permite uma melhor visualização dos detalhes da imagem.
Essa imagem é então submetida a operações morfológicas de fechamento para simular
a perda de detalhes provocada pela distância. A Figura 4.4b ilustra o resultado da operação de
fechamento. A simulação do efeito da distância complementada com a redução do tamanho da
imagem. Componentes pequenos como textos ou linhas impressos desaparecem após essas
operações, restando apenas detalhes de mais alto nível como diferenças no plano de fundo. Essa
imagem é restaurada ao tamanho original (Figura 4.4c) e é calculada a diferença entre a imagem
original e ela. O resultado é uma imagem em que as diferenças de intensidade que existiam no
plano de fundo foram eliminadas ou reduzidas, como pode ser observado na Figura 4.4d.
58
Um limiar é definido para que toda diferença menor que ele seja considerada como
plano de fundo. Todo pixel que não for branco, isto é, não foi confirmado como plano de fundo,
tem seu valor complementado e avaliado em relação a esse limiar. Quando a diferença é menor
que o limiar, o pixel é transformado em branco. Por fim, todas as diferenças restantes têm seu
valor complementado novamente para que voltem ao valor anterior. A imagem produzida ainda
é em tons de cinza, mas a maior parte do plano de fundo foi transformada em branco. Com mais
uma equalização de histograma, a limiarização pode ser realizada por outro algoritmo mais
simples, já que boa parte da complexidade associada ao plano de fundo terá sido removida. O
resultado dessa operação pode ser vista na Figura 4.4e. Neste caso foi aplicada uma limiarização
baseada em histograma. O resultado da limiarização da Figura 4.3 pode ser observado na Figura
4.4f.
Figura 4.3: Resultado da transformação para tons de cinza e redimensionamento de
uma imagem.
(a)
(b)
Em (b), recorte em tamanho real da imagem (a), é possível perceber que o texto continua
legível. Fonte: produção própria.
59
Figura 4.4: Resultados das operações de pré-processamento.
(a)
(b)
(c)
60
(d)
(e)
(f)
Operações: (a) equalização de histograma; (b) fechamento; (c) redução do tamanho e
restauração ao tamanho original; (d) diferença entre as variações do plano de fundo e a
imagem equalizada; (e) confirmação de valores de plano de fundo; e (f) limiarização. Fonte:
produção própria.
A partir da imagem binarizada são eliminadas regiões que não possuem texto. No préprocessamento são utilizadas características simples, mas que permitem eliminar componentes
cujas características não poderiam ser encontradas em componentes de texto. A área é uma das
características avaliada. Foram escolhidos um limite superior relativo à área total da imagem
61
após a redução de tamanho, e um limite inferior fixo. Apesar de terem sido obtidos a partir de
observação, esses limiares servem para remover componentes cujas áreas são muito grandes ou
muito pequenas para texto, poupando o uso do classificador para esses casos. A Figura 4.5
ilustra a eliminação dos componentes da Figura 4.4f cujas áreas não estão dentro dos limites.
Figura 4.5: Eliminação de componentes de acordo com a área.
Fonte: produção própria.
Outra característica usada para eliminar componentes é a espessura do traçado dos
componentes. A partir dos experimentos realizados em um conjunto de imagens isolado, ficou
evidente que alguns traçados finos que permaneciam na imagem ou eram parte de um
componente gráfico ou eram ruído não eliminado nas etapas anteriores de pré-processamento.
Visando reduzir a quantidade de componentes processados na etapa de detecção de texto foram
utilizadas operações morfológicas de abertura e fechamento. Traçados finos são removidos
usando um elemento estruturante de pequenas dimensões em forma de disco. Para evitar que
esse processo afete os componentes que ainda permanecerem, apenas os componentes conexos
com Adjacência-8 que forem completamente removidos são desconsiderados, todos os outros
são recuperados da imagem anterior às operações morfológicas. A Figura 4.6, formada pelos
componentes conexos restantes, é produto final do pré-processamento para Figura 4.3a.
62
Figura 4.6: Resultado da remoção de componentes de acordo com a espessura do
traçado.
Fonte: produção própria.
4.2 Detecção de Texto
Os componentes obtidos no pré-processamento são submetidos ao subprocesso de
detecção de texto. Nesta etapa, foi considerada a possibilidade de existir dois tipos de
componentes de texto: caracteres isolados ou sequências de caracteres. Para adequar a técnica,
foram usados dois classificadores baseados em conjuntos de características diferentes, um para
caracteres e outro para sequências. O resultado da classificação são conjuntos de componentes
de texto, de gráfico e de pequenos componentes alongados. O diagrama deste subprocesso,
reutilizável para caracteres e sequências, está ilustrado na Figura 4.7.
Figura 4.7: Subprocesso de detecção de texto
Este subprocesso é reutilizável e aplicado às duas formas de texto consideradas, caracteres e
sequências. Fonte: produção própria.
4.2.1 Caracteres
As características utilizadas para a detecção de caracteres foram baseadas no trabalho
de Karaoglu, Fernando e Tremeau (KARAOGLU; FERNANDO; TREMEAU, 2010).
Conforme explicado na Seção 3.3.1, os autores utilizaram um conjunto de características
composto por características geométricas e de regularidade de forma associados a descritores
de forma robustos a distorções nos componentes.
As características geométricas consideram propriedades básicas dos componentes.
Para um componente conexo 𝑐, a área 𝐴 representa a quantidade de pixels presente em 𝑐. O
perímetro 𝑃 representa a quantidade de pixels que compõem a borda do componente. Também
63
são considerados os tamanhos dos eixos maior 𝐸𝑚𝑎𝑖𝑜𝑟 e menor 𝐸𝑚𝑒𝑛𝑜𝑟 . Essas medidas são
obtidas analisando os eixos de uma elipse com o mesmo tamanho e orientação do componente.
A partir do tamanho dos eixos, é obtida a última característica geométrica utilizada, a razão de
aspecto 𝑅𝐴 :
𝑅𝐴 (𝑐) =
𝐸𝑚𝑒𝑛𝑜𝑟 (𝑐)
𝐸𝑚𝑎𝑖𝑜𝑟 (𝑐)
(23)
A partir dessas características, é possível ainda descrever outras propriedades do
componente relacionadas à regularidade de sua forma. A razão de ocupação 𝑅𝑂 é definida pela
relação entre a área do componente e a área total de sua bounding box4.
𝑅𝑂 (𝑐) =
𝐴(𝑐)
𝐵𝑜𝑢𝑛𝑑𝑖𝑛𝑔𝐵𝑜𝑥𝐴𝑟𝑒𝑎(𝑐)
(24)
O número de buracos 𝑁𝐵 é obtido usando operações morfológicas. A partir da imagem
𝐼 do componente é obtida a imagem com os buracos preenchidos 𝐼𝑝 . A quantidade de buracos
pode ser interpretada como a quantidade de componentes conexos 𝑛 em uma imagem criada
pela diferença da imagem preenchida pela imagem original.
𝑁𝐵 = 𝑛(𝐼𝑝 − 𝐼)
(25)
As duas últimas características de regularidade são as medidas de compacidade e
regularidade da forma. A compacidade 𝐶 é obtida pela divisão da área do componente pelo
quadrado de seu perímetro. A regularidade 𝐿, medida usada em (SHI et al., 2013), representa a
complexidade do componente como uma relação entre a área de seu esqueleto e seu perímetro.
As equações a seguir definem esses conceitos.
𝐴
(26)
𝑃2
𝐴(𝑒𝑠𝑞𝑢𝑒𝑙𝑒𝑡𝑜(𝑐))
(27)
𝐿=
𝑃
No algoritmo proposto, foram utilizadas apenas as características que não fossem
𝐶=
influenciadas por diferenças de tamanho do componente.
A partir das apresentadas
anteriormente, as escolhidas para compor o vetor de descrição foram: razão de aspecto, razão
de ocupação, número de buracos, compacidade e regularidade.
Além dessas características foram utilizados descritores de forma baseados nos cantos
do componente como proposto em (KARAOGLU; FERNANDO; TREMEAU, 2010). Por usar
4
Bounding box é uma caixa ou retângulo na imagem que envolve os pixels do componente em questão. Diferente
do retângulo mínimo, a bounding box não é ajustada para a orientação dos componentes, os lados do retângulo são
sempre paralelos aos da imagem original.
64
apenas as posições de canto para descrever o objeto, o método CBIF é robusto a pequenas
distorções que ocorram em outros trechos do objeto. Os descritores CBIF são uma variação dos
descritores de Fourier em que ao invés de descrever o componente usando todos os pontos de
sua borda, são usados apenas os pontos de canto.
A técnica de He e Yung (HE; YUNG, 2004) foi utilizada para detectar os pontos de
canto usados para construir o descritor. Essa técnica percorre a borda da imagem preenchendo
pequenos buracos e encontrando pontos de junção. A curvatura é analisada ao longo da borda
e os pontos de máximo locais são considerados candidatos a pontos de canto. Os pontos de
canto finais são escolhidos de acordo com limiares de curvatura definidos localmente, e com o
ângulo do possível canto. Se um ponto de canto estiver muito próximo a um ponto de junção,
ele é descartado para que seja usado o ponto de junção como ponto de canto final. Na Figura
4.8, por exemplo, a forma pode ser representada apenas pelos pontos de canto ao invés de usar
todo seu contorno.
Figura 4.8: Pontos de canto para uma imagem.
Os pontos coloridos exemplificam possíveis cantos de acordo com a intensidade da curvatura
que os definem. Os verdes são pontos com curvaturas mais suaves, amarelos um pouco mais
intensas e vermelhos com curvaturas mais acentuadas. Fonte: produção própria.
O CBIF é obtido através do cálculo dos descritores de Fourier para os pontos de cantos
finais. Os dez coeficientes mais significativos são incorporados ao descritor usado para detectar
caracteres, produzindo um vetor de características com quinze elementos que será usado para
classificar o componente.
4.2.2 Sequências de caracteres
Em imagens de mapas e plantas baixas de grandes dimensões, textos menores podem
apresentar colisão entre os caracteres. Nesse caso os componentes conexos não representam
apenas um, mas uma sequência de caracteres. Diferentemente de caracteres isolados, as
sequências não possuem propriedades de forma em comum. Por isso, os descritores usados para
caracteres não seriam adequados. A alternativa escolhida foi usar descritores baseados em HOG
adaptativo, como proposto em (ALMAZAN; FORNES; VALVENY, 2013).
65
Nesta abordagem, ao invés de calcular o HOG para toda a imagem com uma grade
predefinida, o descritor é calculado para as regiões mais representativas da imagem. Conforme
discutido na Seção 3.3.8, essas regiões são janelas centralizadas nos centros geométricos
obtidos através de divisões sucessivas da imagem de acordo com eles. Esses centros
geométricos, chamados de focos, são calculados e usados para dividir cada nível até que seja
alcançado um nível limite pré-estabelecido ℎ. A quantidade total de focos para um nível 𝑘 =
1,2, … , ℎ pode ser obtida com a equação:
ℎ
𝑛 = ∑ 4𝑘
(28)
𝑘=0
Cada foco é usado para centralizar uma janela de cálculo de HOG. Essas janelas são
divididas em células para que seja descrita através de HOG. Mas o método de HOG usado difere
do original apresentado na Seção 2.1.5. Felzenszwalb et al. (FELZENSZWALB et al., 2010)
propuseram uma variação do método de Dalal e Triggs. A partir de uma Análise de
Componentes Principais (DUDA; HART; STORK, 2000), os autores identificaram que a
capacidade de descrição do vetor de 36 dimensões do HOG original era equivalente à de um
vetor de 11 dimensões formado por componentes principais.
Para reduzir a dimensionalidade evitando o custo de calcular novamente os
componentes principais, os autores propuseram uma aproximação baseada na projeção dos
vetores em relação a nove partições e aos fatores de normalização. Os valores obtidos para as
normalizações e orientações são somados para formar um vetor de 4 características relativas à
energia (fatores de normalização) e 9 à orientação. Assim, a representação de 36 dimensões
(4 × 9) é transformada em uma de 13 dimensões (4 + 9) como mostra a Figura 4.9.
Figura 4.9: Ilustração da projeção de fatores de normalização (linhas) e orientações
(colunas) para o método de Felzenszwalb et al..
Fonte: produção própria.
Também foi proposto em (FELZENSZWALB et al., 2010) que fossem usadas
características de orientação sensíveis ao contraste. As 9 características obtidas pela análise do
método de Dalal e Triggs são invariantes ao contraste, isto é, não levam em consideração o
66
sentido do vetor gradiente, apenas sua direção. Para complementar foram calculadas as
características para 18 partições de orientação sensíveis a contraste. O conjunto de
características foi normalizado com quatro fatores de normalização conforme o método
original, produzindo um vetor de 4 × (9 + 18) = 108 características. A projeção foi aplicada
novamente para reduzir a dimensionalidade, produzindo um vetor de 31 dimensões. Essa
representação do HOG é formada por 27 componentes relativos à orientação (9 independentes
de contraste e 18 sensíveis a contraste) e 4 componentes que armazenam a energia geral do
gradiente nas células do bloco analisado. (FELZENSZWALB et al., 2010)
Considerando que cada janela centralizada nos focos são divididas em uma grade de
𝑐 × 𝑐 células, a dimensão do vetor de características para uma imagem é dada por:
ℎ
2
𝑛𝐻𝑂𝐺 = 31𝑐 ∑ 4𝑘
(29)
𝑘=0
Os valores adotados para 𝑐 e ℎ são apresentados no Capítulo 5.
4.2.3 Classificação
A classificação de componentes em texto ou gráfico pode ser interpretado como um
problema de classificação de apenas uma classe. Os componentes de gráfico não possuem um
padrão definido, eles podem ser desde pequenos traçados até marcações de rios ou paredes nos
formatos mais variados. Para lidar com esse cenário foi escolhido um classificador baseado em
SVM que é construído para problemas de uma classe, ideal para a detecção de outliers.
As Máquinas de Vetores de Descrição de Dados (Support Vector Data Descriptor,
SVDD) (TAX; DUIN, 2004) foram treinadas para classificar texto enquanto identificam
qualquer objeto que não siga o padrão de características identificado. Usando SVM é possível
de produzir a melhor superfície de separação para duas classes, mesmo quando há poucos
exemplos. O SVDD permite que essa superfície seja construída mesmo quando apenas
exemplos de uma classe são conhecidos.
A principal diferença entre SVDD e SVM é o formato da superfície de separação.
Enquanto para uma SVM a superfície é um hiperplano, para um SVDD a superfície é uma
hiperesfera. Esse formato permite a melhor adequação aos exemplos da classe alvo. Para
encontrar a hiperesfera de separação máxima é proposta uma abordagem análoga à de SVM
(Seção 2.2.1). O objetivo é encontrar o menor volume da hiperesfera de raio 𝑅 > 0 e centro 𝒂
através da minimização de 𝑅 2 considerando um conjunto de 𝑁 padrões 𝒙𝑖 em que i= 1,2, … , 𝑁.
Para garantir que os exemplos do treinamento 𝒙𝑖 estejam dentro da hiperesfera é usada a
restrição ‖𝒙𝑖 − 𝒂‖2 ≤ 𝑅 2 + 𝜉𝑖 , em que 𝜉𝑖 ≥ 0 são variáveis de relaxamento introduzidas para
67
flexibilizar a superfície de separação. Seja 𝐶 > 0 um parâmetro de usuário que controla a
relação entre o volume da hiperesfera e o erro de classificação, o problema de otimização é
dado por:
𝑁
2
arg min 𝑅 + 𝐶 ∑ 𝜉𝑖
𝑅,𝒂,𝝃
(30)
𝑖
É possível considerar que a hiperesfera é flexível e se ajusta aos dados usando uma
função de núcleo 𝜙(). A restrição do problema passa a ser dada por ‖𝜙(𝒙𝑖 ) − 𝒂‖2 ≤ 𝑅 2 + 𝜉𝑖 .
A otimização é resolvida através de um problema dual com métodos semelhantes aos usados
em SVM. Dado que o problema foi resolvido, um exemplo de teste é considerado um outlier
quando ‖𝜙(𝒙𝑖 ) − 𝒂‖2 > 𝑅 2.
Três características do treinamento podem influenciar na qualidade da superfície de
descrição escolhida. Uma delas é a utilização de exemplos de outliers no treinamento. Apesar
de ser possível realizar o treinamento apenas com exemplos da classe alvo, a qualidade da
descrição dos exemplos alvo é melhor quando são apresentados exemplos de outliers. A Figura
4.10 ilustra a diferença de superfícies obtidas com e sem o uso de outliers. É possível perceber
que o outlier utilizado estaria dentro da hiperesfera se a superfície não fosse recalculada.
Quando ele foi usado para a escolha da nova superfície, foi escolhido como vetor de suporte e
a superfície foi deformada de modo que ele não fosse mais incluso dentro dela. Como resultado
a hiperesfera deixou de envolver precisamente os exemplos de alvo.
Figura 4.10: Exemplo da superfície de descrição sem outliers à esquerda e com um
outlier à direita.
Os exemplos usados como vetor de suporte são ilustrados como círculos. A seta na figura da
direita indica o vetor de suporte criado a partir do outlier apresentado no treinamento. Os tons
de cinza indicam a distância para o centro da hiperesfera, quanto mais escuro, menor a
distância. Fonte: (TAX; DUIN, 2004).
O uso da função de núcleo permite que a superfície do descritor se adeque para
representar melhor os exemplos. Uma função de núcleo gaussiana, por exemplo, permite que
68
com a variação da largura desta função, a superfície represente os dados com maior precisão.
Esse comportamento pode ser observado na Figura 4.11 em que a largura da função de núcleo
gaussiana é alterada através do parâmetro 𝜎. Quanto menor esse valor, mais complexa será a
superfície e por isso serão usados mais vetores de suporte.
O parâmetro de ajuste 𝐶 também influencia no volume e no ajuste da hiperesfera aos
dados de treinamento. Para valores maiores a superfície de descrição se aproxima à forma rígida
definida pelos dados de exemplo. Já valores menores de 𝐶 produzem hiperesferas de menor
volume, uma aproximação da forma definida pelos dados de exemplo. Quanto menor o valor
de 𝐶, mais vetores de suporte serão necessários para definir a superfície.
Figura 4.11: Variação da superfície de descrição de acordo com o parâmetro σ de uma
função de núcleo gaussiana e o parâmetro C do descritor.
Nestas imagens os círculos representam os vetores de suporte. Fonte: (TAX; DUIN, 2004).
A capacidade deste método de descrever os dados de uma classe em relação a poucos
exemplos negativos foi a principal motivação para escolhê-lo para decidir se os componentes
da imagem são texto. Usando exemplos de texto e um pequeno número de exemplos de gráficos,
foram criados dois SVDDs: um capaz de detectar caracteres, outro capaz de detectar sequências.
A classificação realizada por esses modelos é a última etapa da detecção do texto e produz como
resultado um rótulo de texto ou gráfico para cada componente.
4.3 Separação de Pequenos Componentes Alongados
As imagens de mapas e plantas baixas possuem muitos tracejados que, quando
analisados individualmente, podem ser confundido com letras. Para evitar essa confusão foi
69
utilizada uma abordagem semelhante à de Tombre et. al. (TOMBRE et al., 2002). A separação
é realizada após a detecção de caracteres, e não em um pré-processamento. Isso permite que o
conhecimento obtido com a classificação seja usado para detectar os componentes alongados.
Os componentes são analisados de acordo com sua densidade e alongamento para
decidir se devem ser considerados pequenos componentes alongados. A densidade é semelhante
à razão de ocupação usada no pré-processamento, mas ao invés do bounding box é utilizado o
menor retângulo que circunscreve o componente. O alongamento é a relação do maior eixo com
o menor eixo, ou o inverso da razão de aspecto. Essas medidas são avaliadas contra limiares
pré-definidos para decidir se o objeto é um pequeno componente alongado. Os valores
sugeridos em (TOMBRE et al., 2002) foram 0.5 para o limite de densidade e 2 para o limite de
alongamento.
A detecção de componentes alongados no conjunto de componentes classificados
como gráfico é submetida a uma terceira restrição. Características dos componentes textuais já
conhecidos são usadas para evitar erros na recuperação dos componentes alongados. Foi então
definido que a área de um componente alongado recuperado dos gráficos não deve ser maior
que um limiar relativo à média das áreas dos componentes textuais.
4.4 Recuperação
A última etapa do método é recuperar possíveis componentes classificados
incorretamente. Características dos componentes textuais são usadas para procurar possíveis
componentes de texto nos conjuntos de pequenos componentes alongados e de gráficos. O
diagrama da Figura 4.12 representa este subprocesso.
Figura 4.12: Subprocesso reutilizável de recuperação.
Fonte: produção própria.
A primeira etapa é identificar, a partir dos componentes de texto, um limite máximo
para a área dos componentes que serão recuperados. Esse limite é uma maneira simples de
evitar que componentes sejam recuperados incorretamente. A área dos componentes é calculada
como apresentado na Seção 4.2.1 e o limite para 𝑁 componentes 𝑐𝑖 , onde 𝑖 = 1,2, … , 𝑁, é
definido pela equação a seguir.
70
max 𝑚𝐴(𝑐𝑖 )
(31)
onde 𝑚 > 0 é um parâmetro usado para ajustar o limite de acordo com a área máxima
encontrada entre os componentes.
Essa restrição é inicialmente usada para texto do conjunto de pequenos componentes
alongados. É esperado que esse conjunto possua muitos traços e linhas, mas também letras e
números alongados. Com os componentes recuperados desse conjunto, são analisados os
componentes do conjunto de gráficos.
A recuperação é um processo baseado no posicionamento dos componentes. Quando
um componente avaliado está próximo a um componente de texto, dado um limiar definido
baseado nas dimensões do componente de texto, o componente avaliado é recuperado para o
conjunto de texto. Para cada componente de texto 𝑐𝑡 usado como âncora para recuperar um
componente analisado 𝑐𝑎 são definidos os limiares horizontal 𝐿ℎ e vertical 𝐿𝑣 :
𝐿ℎ = l(𝑐𝑡 ) ∗ 𝐾ℎ
(32)
𝐿𝑣 = a(𝑐𝑡 ) ∗ 𝐾𝑣
(33)
onde l() e a() são funções que calculam a largura e a altura do componente,
respectivamente. As constantes 𝐾ℎ = 0.6 e 𝐾𝑣 = 1.1 foram obtidas experimentalmente para
criar os limites de distância a partir das medidas do componente 𝑐𝑡 .
Para cada componente de texto 𝑐𝑡 , cada componente analisado 𝑐𝑎 passa por uma
verificação para decidir se este deve ser recuperado. Para os componentes de texto e analisado,
respectivamente, são considerados 𝑥𝑒𝑠𝑞𝑡 e 𝑥𝑒𝑠𝑞𝑎 as coordenadas horizontais mais à esquerda;
𝑥𝑑𝑖𝑟𝑡 e 𝑥𝑑𝑖𝑟𝑎 as coordenadas horizontais mais à direita; 𝑦𝑡𝑜𝑝𝑡 e 𝑦𝑡𝑜𝑝𝑎 as coordenadas verticais
mais ao topo; e 𝑦𝑏𝑎𝑖𝑡 e 𝑦𝑏𝑎𝑖𝑎 as coordenadas verticais mais abaixo. A partir dessas
considerações, um componente analisado é recuperado quando uma das condições a seguir é
satisfeita.
Proximidade vertical:
|𝑥𝑒𝑠𝑞𝑡 − 𝑥𝑒𝑠𝑞𝑎 | < 𝐿ℎ e
|𝑥𝑑𝑖𝑟𝑡 − 𝑥𝑑𝑖𝑟𝑎 | < 𝐿ℎ e
(34)
{|𝑦𝑡𝑜𝑝𝑡 − 𝑦𝑏𝑎𝑖𝑎 | < 𝐿𝑣 ou |𝑦𝑏𝑎𝑖𝑡 − 𝑦𝑡𝑜𝑝𝑎 | < 𝐿𝑣 }
Proximidade horizontal:
|𝑦𝑡𝑜𝑝𝑡 − 𝑦𝑡𝑜𝑝𝑎 | < 𝐿𝑣 e
|𝑦𝑏𝑎𝑖𝑡 − 𝑦𝑏𝑎𝑖𝑎 | < 𝐿𝑣 e
{|𝑥𝑒𝑠𝑞𝑡 − 𝑥𝑑𝑖𝑟𝑎 | < 𝐿ℎ 𝑜𝑢 |𝑥𝑑𝑖𝑟𝑡 − 𝑥𝑒𝑠𝑞𝑎 | < 𝐿ℎ }
(35)
71
Proximidade diagonal:
{|𝑥𝑒𝑠𝑞𝑡 − 𝑥𝑑𝑖𝑟𝑎 | < 𝐿ℎ ou |𝑥𝑑𝑖𝑟𝑡 − 𝑥𝑒𝑠𝑞𝑎 | < 𝐿ℎ } e
{|𝑦𝑡𝑜𝑝𝑡 − 𝑦𝑏𝑎𝑖𝑎 | < 𝐿𝑣 ou |𝑦𝑏𝑎𝑖𝑡 − 𝑦𝑡𝑜𝑝𝑎 | < 𝐿𝑣 }
(36)
A Figura 4.13 ilustra cada uma das áreas de recuperação obtidas com as condições
anteriores. Em vermelho estão as áreas de proximidade vertical, em verde estão as de
proximidade horizontal e em amarelo estão as de proximidade diagonal.
Figura 4.13: Áreas de proximidade consideradas na recuperação.
Fonte: produção própria.
É importante destacar que a recuperação não é executada iterativamente. Primeiro são
recuperados componentes do conjunto de pequenos componentes alongados. Com o novo
conjunto de texto, são recuperados componentes do conjunto de gráficos.
72
5 Experimentos e Resultados
Neste capítulo são apresentados os experimentos, metodologias e resultados
relacionados ao algoritmo proposto. Para verificar a capacidade de segmentação de texto do
algoritmo aplicado a problemas reais, foram usadas imagens de mapas e plantas baixas
históricos. Durante os experimentos foram avaliadas diferentes parametrizações até alcançar
resultados satisfatórios avaliados sobre um conjunto de observação isolado.
5.1 Bases de Dados
Para verificar a eficácia do método foram usadas imagens de mapas e plantas baixas
reais. A maioria dessas imagens fazem parte do acervo do projeto ProHist (MELLO, 2014).
Outros mapas usados nos experimentos foram obtidos no portal OldMapsOnline (“Old Maps
Online,” 2014). Dentre essas imagens foram escolhidas duas de mapas e duas de plantas baixas
para compor um conjunto de observação e ajustes de parâmetros.
Uma base criada artificialmente foi usada para o treinamento dos classificadores. A
dificuldade de encontrar uma base de dados gratuita com imagens de caracteres impressos
motivou a elaboração de uma base própria. Foi criado um gerador de imagens de caracteres e
sequências para serem utilizadas para treinamento dos classificadores. A ferramenta de código
aberto ImageMagick (“ImageMagick: Convert, Edit, and Compose Bitmap Images,” 2014) foi
usada para construir esse gerador parametrizado de imagens de caracteres ou sequências usando
diferentes tamanhos e estilos de fonte.
Os estilos e tamanhos foram escolhidos a partir de observação. Para imagens de
caracteres, foram usados todos os estilos suportados pelo ImageMagick, exceto os que
produziram caracteres com traçados muito finos, eles não poderiam representar um caractere
impresso após digitalizado. Os 30 estilos escolhidos são formados por variações de
‘AvantGarde’, ‘Bookman’, ‘Courier’, ‘Helvetica’, ‘NewCenturySchlbk’, ‘Palatino’ e ‘Times’.
Esses estilos são combinados a 4 tamanhos de fonte diferentes (19, 38, 76 e 152) para construir
os exemplos de caracteres. No total foram criadas 7.440 imagens de caracteres.
Os exemplos de sequência foram criados com apenas oito estilos e um tamanho de
fonte. Foram escolhidos por observação apenas os estilos que produziam resultados distintos e
que eram mais propícios a produzir colisões entre caracteres, evitando os não representativos.
Os estilos escolhidos foram ‘AvantGarde-Demi’, ‘Bookman-Demi’, ‘Courier-Bold’,
‘Helvetica-BoldOblique’, ‘NewCenturySchlbk-BoldItalic’, ‘Palatino-BoldItalic’, ‘TimesRoman’, ‘Times-BoldItalic’. Como as colisões que formam componentes de sequência tendem
a ocorrer apenas em tamanhos menores de fonte, foi usado apenas o tamanho 16. Para simular
palavras reais, o texto de entrada para o gerador foi obtido a partir uma base de palavras do
73
dicionário brasileiro. No total foram selecionadas 600 palavras, de 5 ou mais caracteres, que
combinadas com os estilos produziram 4.800 imagens de sequências.
Essas imagens de caracteres e sequências foram criadas já binarizadas. Considerando
que as imagens seriam avaliadas como componentes conexos, elas foram criadas com plano de
fundo preto e letras brancas e o limiar de binarização usado no ImageMagick foi definido por
observação como 35.
Exemplos reais de outliers, obtidos a partir das imagens de observação, foram usados
para produzir os vetores de suporte dos SVDD. Noventa e duas imagens de componentes não
textuais foram escolhidas e foram suficientes para que os SVDD criassem superfícies de
separação representativas apesar da quantidade muito inferior à de componentes de texto.
5.2 Experimentos
As imagens de observação foram usadas para avaliar a qualidade de classificação do
SVDD e definir seus parâmetros. O treinamento tem início com a normalização dos dados que
posteriormente são divididos em conjuntos de treinamento e de testes para cada classe. A
avaliação dos resultados foi feita para diversas configurações do algoritmo, alterando desde
componentes de extração de características até parâmetros do classificador. As configurações
finais foram escolhidas observando a qualidade do classificador produzido através de curvas de
Características de Operação do Receptor (Receiver Operating Characteristic, ROC) (DUDA;
HART; STORK, 2000).
A normalização foi realizada em respeito aos mínimos e faixas de variação de cada
dimensão dos vetores de características. Para cada dimensão foram calculados os valores
mínimos e a variação máxima. Considerando um valor de característica 𝑣𝑘 , onde 𝑘 = 1,2, … , 𝐾
é o índice entre as 𝐾 características de um vetor de descrição, a normalização do valor 𝑣𝑘 norm
pode ser obtida com as operações a seguir.
𝑣𝑘 min = min 𝑣𝑘 ∀ 𝑘 = 1,2, … , 𝐾
(37)
𝑣𝑘 var = max 𝑣𝑘 − 𝑣𝑘 min
(38)
𝑣𝑘 norm =
𝑣𝑘 − 𝑣𝑘 min
𝑣𝑘 var + 𝛼
(39)
onde 𝛼 = 0,0001 é uma constante usada para evitar que hajam divisões por zero,
𝑣𝑘 min é o valor mínimo e 𝑣𝑘 var é a variação máxima. Os valores obtidos para essas variáveis
são associados ao classificador para que seja aplicada a mesma normalização durante os testes
e a execução.
74
As imagens foram divididas em treinamento e testes usando a técnica de holdout
(DUDA; HART; STORK, 2000). A divisão das imagens para treinamento e teste é feita
aleatoriamente, mas respeitando uma relação pré-estabelecida. Para cada classe foram
escolhidos 80% dos exemplos para treinamento e 20% para testes. Para evitar que uma
determinada divisão aleatória pudesse impactar nos resultados, a técnica foi repetida dez vezes
para cada configuração.
5.2.1 Parâmetros do Pré-processamento
Os parâmetros para a etapa de pré-processamento foram escolhidos observando o
resultado produzido por ela. Para a limiarização baseada em percepção visual, foram usados os
elementos estruturantes em formato de disco com tamanhos 3 e 5, aplicados nessa ordem. Isso
produziu o resultado da perda de detalhes da imagem. Na redução aplicada posteriormente, a
imagem foi reduzida a 0,8% de sua dimensão original. O primeiro limiar, que transforma em
branco pixels com valores próximos ao de plano de fundo foi definido como 30, enquanto o
valor usado para o limiar fixo que produz a imagem binária final foi 120.
Os limites para a área do componente também foram definidos por observação. Para
evitar a remoção de componentes importantes, esses limites são valores que, nos testes
realizados, removeram apenas componentes com áreas absurdamente grandes ou pequenas. O
limite superior definido foi de 0,2% da área total da imagem e o inferior, 13 pixels. Qualquer
componente fora dessa faixa foi considerado gráfico. Foi possível perceber que a maioria dos
componentes removidos eram ruídos representados por regiões muito pequenas, ou desenhos,
como rios, marcações de parede ou grades de escala que ocupavam boa parte da imagem. Outra
operação que resultou na remoção de ruídos foi a eliminação de componentes com traçados
finos. Para esta operação foi usado um elemento estruturante em formato de disco de tamanho
1. É importante ressaltar que se ao menos um pixel do componente permanecer na imagem após
a operação, ele é restaurado para evitar perda de informações.
5.2.2 Parâmetros da Detecção de Texto
Entre os descritores utilizados na detecção, o CBIF e o HOG adaptativo são
parametrizados. Para a detecção dos cantos do CBIF são usados os parâmetros propostos em
(HE; YUNG, 2004). A única alteração foi no parâmetro de largura da função gaussiana usada
para calcular a curvatura. Neste trabalho observou-se que, devido ao reduzido tamanho das
letras de imagens de mapas e plantas baixas, o uso de um valor menor para a gaussiana produziu
melhores resultados. Esse valor foi definido experimentalmente como 𝜎 = 0.2. Para o HOG
adaptativo foram utilizados os parâmetros descritos em (ALMAZAN; FORNES; VALVENY,
2013). Com nível ℎ = 2 resultou em 5.859 características para cada componente.
75
Os parâmetros dos classificadores foram escolhidos a partir da análise de resultados
de classificação para várias repetições de holdout. Com base nos experimentos usando
diferentes valores para os parâmetros (descritos na Tabela 5.1), foram escolhidos os valores
𝐶 = 0.1 e 𝜎 = 8 para o SVDD.
Tabela 5.1: Valores de parâmetros para SVDD avaliados em repetição de holdout.
Parâmetro
𝐶
Valores
0,1; 0,2; 0,3
3; 5; 8
𝜎
A decisão dos valores finais foi realizada a partir da análise das curvas ROC
produzidas por classificadores criados com diferentes combinações desses parâmetros. Para um
problema de classificação binária, o gráfico da curva ROC representa a taxa de verdadeiro
positivo (TPR) no eixo das ordenadas, e a taxa de falso positivo (FPR) no eixo das abcissas.
Essas taxas indicam, respectivamente, quantos elementos de uma classe alvo foram
classificados corretamente em relação ao número total de exemplos dessa classe; e quantos
elementos da classe negativa foram classificados como alvo em relação ao número de exemplos
da classe negativa. Dessa forma é possível perceber que um classificador ótimo possuiria a
maior área sob a curva ROC, com alta TPR e baixa FPR. Essa informação foi utilizada para
analisar os classificadores criados e escolher o que produzisse melhor resultado.
5.3 Implementações
Todo o algoritmo foi desenvolvido sobre a ferramenta MATLAB (“MATLAB: The
Language of Technical Computing,” 2014). A escolha dessa ferramenta deu-se pela facilidade
de manipular estruturas de dados e pela existência de um conjunto de funções para
processamento de imagens e reconhecimento de padrões. Também foram usadas bibliotecas de
terceiros e uma aplicação externa descritas a seguir.
A aplicação externa integrada foi o ImageMagick, usado para a criação das imagens
de caracteres e sequências para treinamento dos SVDDs. A utilização completa dos recursos de
renderização de texto requer outra ferramenta, também de código aberto, o Ghostscript
(“Ghostscript Download Page,” 2014). É ele quem provê as fontes utilizadas nos experimentos.
A integração com o comando do ImageMagick de criação das imagens foi realizada através de
chamadas de processo em um código MATLAB.
A implementação de detectores de canto disponibilizada por He, um dos autores de
(HE; YUNG, 2004), foi usada para criar os descritores CBIF. Disponível em (HE; YUNG,
2008), a detecção dos cantos foi parametrizada conforme descrito na Seção 5.2.2 e
76
complementada com a técnica de descritores de Fourier para obter o vetor de características
CBIF.
Os descritores HOG adaptativos foram implementados usando a biblioteca VLFeat
(“VLFeat,” 2014). Essa biblioteca provê várias funcionalidades relacionadas a processamento
de imagens e visão computacional. Entre os descritores de características implementados estão
o HOG proposto em (FELZENSZWALB et al., 2010). A função existente foi integrada à
computação dos focos para produzir o descritor HOG adaptativo.
O classificador não foi implementado neste trabalho, mas foi utilizada a biblioteca
DDTools (TAX, 2014). Publicada por Tax, um dos autores de (TAX; DUIN, 2004), a biblioteca
contém uma implementação do SVDD que segue o artigo original. Essa biblioteca é construída
como uma extensão da PRTools (“PRTools: A Matlab toolbox For Pattern Recognition,” 2014)
que contém vários recursos para lidar com problemas de reconhecimento de padrões, desde préprocessamento até ferramentas de comparação de classificadores. O uso dessas bibliotecas
também facilitou a comparação de resultados por prover ferramentas para a análise da curva
ROC.
5.4 Método de Avaliação
A avaliação do algoritmo foi realizada através da comparação entre a imagem
resultante e sua correspondente, criada por um operador manual. Foram produzidas 10 imagens
de resultado esperado para a comparação (ground truth), sendo metade de plantas baixas e
metade de mapas. Os operadores produziram o ground truth a partir da imagem binarizada.
Eles foram instruídos a tornar branca toda região da imagem que não possuísse texto.
Dada a imagem binarizada original, os pixels pretos de uma são considerados
pertencentes à classe positiva (P) e os pixels brancos à classe negativa (N). Os pixels pretos na
imagem obtida pelo algoritmo e pretos na imagem ground truth são considerados os
verdadeiramente positivos (TP). De maneira análoga, os pixels brancos da imagem do algoritmo
que também são brancos na imagem ground truth são considerados verdadeiramente negativos
(TN). Quando um pixel da imagem do algoritmo é preto, mas deveria ser branco, segundo a
imagem ground truth, ele é considerado falso positivo (FP). Já quando um pixel é branco na
imagem obtida pelo algoritmo e preto na imagem ground truth, é considerado falso negativo
(FN). Esses indicadores compõem a matriz de confusão, ilustrada na Figura 5.1.
Outros indicadores podem ser calculados a partir dos descritos anteriormente. Cinco
outros indicadores derivados foram calculados neste trabalho. A taxa de verdadeiramente
positivos ou sensibilidade (TPR), a taxa de verdadeiramente negativos ou especificidade
77
(TNR), a precisão (Pre), a acurácia (Acc) e o Coeficiente de Correlação de Matthews (CCM)
(BALDI; BRUNAK; CHAUVIN, 2000).
Figura 5.1: Exemplo de Matriz de Confusão
Resultado Esperado
Resultado
Obtido
Positivo
Negativo
Positivo
TP
FP
Negativo
FN
TN
Fonte: produção própria.
TP
P
TN
TNR =
N
TP
Pre =
TP + FP
TP + TN
Acc =
P+N
TP × TN − FP × FN
TPR =
CCM =
√(TP + FN)(TP + FP)(TN + FP)(TN + FN)
(40)
(41)
(42)
(43)
(44)
Com exceção do CCM, os indicadores apresentados podem ser facilmente
interpretados através de suas fórmulas. A sensibilidade e a especificidade indicam as taxas de
acerto em relação às classes positiva e negativa, respectivamente. A precisão indica o quanto
foi corretamente previsto como positivo pelo algoritmo. A acurácia representa a taxa de acerto
total do algoritmo. O CCM é uma solução de agregação da matriz de confusão em um único
valor. Esse coeficiente assume valores entre [−1, +1] que indicam a qualidade do classificador
binário avaliado. O extremo −1 indica que o classificador está em total desacordo com o que
era esperado, produzindo o máximo de erros de classificação. Um valor 0 (zero) indica que o
classificador tem o mesmo resultado que uma escolha aleatória entre as classes, 50% de
probabilidade de acerto. O extremo +1 indicam que o classificador foi capaz classificar
perfeitamente todos os exemplos de teste.
5.5 Resultados e Análise
Nesta seção, são apresentados os resultados obtidos com a aplicação do algoritmo
proposto e suas interpretações. Detalhes sobre os experimentos com mapas estão na Seção 5.5.1
78
e plantas baixas na Seção 5.5.2. Também serão discutidos pontos em comum aos dois tipos de
imagem na Seção 5.5.3.
5.5.1 Mapas
Nestes experimentos, o algoritmo foi aplicado às cinco imagens de mapas que foram
consideradas para comparação. Os resultados foram analisados a partir dos indicadores
descritos na Seção 5.4. Foram calculadas as médias e desvios padrão para cada indicador, o que
permitiu a comprovação da eficácia do algoritmo.
Para essas imagens foram alcançados valores de CCM de até 0.70. A Tabela 5.2
apresenta os resultados considerando a média e o desvio padrão de cada indicador.
Tabela 5.2: Média e desvio padrão dos indicadores para imagens de mapas.
Indicador
Média
Desvio Padrão
TPR
78,12%
8,11%
TNR
89,50%
7,43%
Pre
73,71%
10,92%
Acc
86,25%
5,79%
CCM 0,6473
0,0490
Foi possível perceber que o método produziu bons resultados mesmo para imagens
com muitos componentes gráficos. As imagens e seus respectivos resultados são apresentados
na Figura 5.2. É possível destacar alguns desses resultados, para o mapa da Figura 5.2a o
método alcançou 78,33% de sensibilidade, 88,24% de especificidade, 74,60% de precisão,
85,21% de acurácia e CCM de 0,6570. Na Figura 5.2c é possível perceber uma grande
densidade de texto em meio a traçados de rios e grades do mapa. A maioria desses artefatos
foram removidos corretamente (Figura 5.2d), mas componentes de texto que colidiam com eles
não foram recuperados. Como consequência foi alcançada uma precisão de 90,20%, mas a
sensibilidade foi de apenas 67,39%. É interessante destacar o resultado da Figura 5.2f em que
a limiarização conseguiu segmentar os objetos de interesse, pouco visíveis na imagem original,
chegando à sensibilidade de 80,59%. A Figura 5.2h foi a que alcançou maior CCM. Neste mapa
existem muitos componentes gráficos que foram, em sua maior parte, removidos durante o
processamento. Os elementos textuais, presentes em diversas orientações, foram recuperados
pelo algoritmo que atingiu uma acurácia de 95,27%. Para o mapa da Figura 5.2i, que possui
plano de fundo bastante irregular e muitos artefatos próximos a textos, o resultado (Figura 5.2j)
alcançou sensibilidade de 80,45% e acurácia de 86,89%.
79
Figura 5.2: Resultados obtidos para os exemplos de mapas.
(a)
80
(b)
81
(c)
82
(d)
83
(e)
84
(f)
85
(g)
86
(h)
87
(i)
88
(j)
Fonte: produção própria..
89
5.5.2 Plantas Baixas
A mesma metodologia foi aplicada às imagens de plantas baixas. Entre os exemplos
obteve-se o valor de 0,8707 para o CCM. Na Tabela 5.3 estão as médias e desvios padrão de
todos os indicadores analisados.
Tabela 5.3: Média e desvio padrão de indicadores obtidos para imagens de plantas
baixas.
Indicador
Média
Desvio Padrão
TPR
64,62%
24,31%
TNR
96,46%
1,96%
Pre
82,88%
14,83%
Acc
87,70%
8,82%
CCM 0,6547
0,1735
Na Figura 5.3 são apresentados os resultados da segmentação obtidos com a aplicação
do método proposto às imagens de plantas baixas consideradas para comparação. A Figura 5.3b
foi o resultado de maior CCM. É possível perceber que o algoritmo produziu novamente o
resultado esperado, componentes gráficos da imagem foram removidos preservando o texto da
imagem. Essa imagem também obteve bons índices para sensibilidade (92,44%), especificidade
(95,44%), precisão (89,47%) e acurácia (94,56%). Para a Figura 5.3d, apesar de ter recuperado
corretamente boa parte do texto, alcançando precisão de 93,81%, o resultado de sensibilidade
foi de apenas 37,13%. Isso ocorreu porque a solução não leva em consideração o texto cursivo
presente na imagem original. O resultado da Figura 5.3f sofreu, não apenas com presença de
texto cursivo, mas também com a confusão de pequenos elementos gráficos que, quando
observados isoladamente, são difíceis de serem distinguidos. Apesar disso a acurácia foi de
94,10%. Com pouco conteúdo textual, a Figura 5.3h alcançou precisão de 92,31%. É possível
perceber que parte do texto foi removido por colidir com margens impressas na imagem, o que
impactou negativamente na sensibilidade de 56,71%. A Figura 5.3i se assemelha à Figura 5.3a
e seu resultado obteve 87,68% de sensibilidade e CCM de 0,7906.
Na maioria das imagens de plantas baixas avaliadas os textos são predominantemente
cursivos. Já que o método proposto não trata esse tipo de texto, houve um impacto negativo nos
resultados. Os resultados são muito melhores para imagens em que essa característica não é
observada.
90
Figura 5.3: Resultados obtidos para imagens de plantas baixas.
(a)
91
(b)
92
(c)
93
(d)
94
(e)
95
(f)
96
(g)
97
(h)
98
(i)
99
(j)
Fonte: produção própria.
100
5.5.3 Comparação de Resultados
Para avaliar o método em relação a outras propostas, foram escolhidas as imagens de
plantas baixas que não possuíam texto cursivo, já que este tipo de escrita não foi tratado neste
trabalho.
Foram escolhidas Figura 5.3a e Figura 5.3i para a avaliação. O método proposto foi
comparado aos algoritmos de Ahmed et al. e Mello e Machado. Os resultados podem ser
observados na Tabela 5.4.
Tabela 5.4: Comparação de resultados. O valor de cada indicador é a média obtida para
as imagens de avaliação.
Método
Ahmed
et al.
Mello e
Machado
Método
Proposto
TPR
TNR
Pre
Acc
CCM
39,72%
97,63%
81,54%
79,08%
0,3987
59,20%
90,86%
72,01%
82,53%
0,5378
90,06%
94,48%
85,20%
93,35%
0,8306
5.5.4 Considerações Gerais
Apesar de os classificadores utilizados terem sido treinados com exemplos criados
artificialmente, o algoritmo foi capaz de detectar corretamente o texto nas imagens de mapas e
plantas baixas reais. Analisando os resultados foi possível observar que a etapa de recuperação
ainda pode ser aprimorada para que sejam recuperados também caracteres que colidirem com
componentes gráficos. Não obstante a deficiência, o algoritmo proposto produziu bons
resultados para a segmentação de texto para os dois tipos de imagem analisados, sem
necessidade de configuração específica. A solução mostrou-se ainda robusta a variações nas
propriedades do texto detectado, como tamanho, estilo e orientação.
O tempo de processamento também foi analisado. O tempo médio de treinamento da
configuração escolhida de SVDD para detecção de caracteres foi de 4 minutos e 8 segundos
para a extração de características e 8 minutos e 13 segundos para a construção do modelo. Para
a detecção de sequências os tempos médios foram de 9 minutos e 54 segundos para extração de
características e 10 minutos e 17 segundos para construção do modelo.
Durante os experimentos constatou-se que a aplicação do método de segmentação
demorou, em média, 8 minutos e 44 segundos. Desse tempo, aproximadamente 5 minutos e 16
segundos foram dedicados à classificação e o restante ao pré-processamento. Os experimentos
foram executados em um computador com processador Intel Core i5 2.6GHz, 8GB de memória
RAM de 1600MHz e armazenamento em disco de estado sólido.
101
6 Conclusões e Trabalhos Futuros
Ao longo da história, muito conhecimento foi produzido em papel. Documentos
históricos podem guardar informações que vão além do seu conteúdo. Dada a importância
desses documentos, é cada vez maior a demanda por soluções de processamento automático
que permitam o usufruto de vantagens associadas ao uso de novas tecnologias. Essa tarefa pode
ser desafiadora devido a características desse tipo de documento. O desgaste causado pelo
tempo ou manuseio, por exemplo, dificultam o uso de técnicas tradicionais.
Alguns documentos, como mapas e plantas baixas, possuem características que os
tornam ainda mais difíceis de serem processados automaticamente. O grande número de
elementos gráficos que se mistura ao texto da imagem dificulta a utilização de ferramentas
convencionais de OCR. Buscando um melhor aproveitamento da informação desses
documentos, surgiram trabalhos que tratam da segmentação do texto para essas imagens. Mas
a complexidade das imagens fez com que a maioria dos métodos usasse informações específicas
de um tipo para segmentar o texto.
Neste trabalho foi apresentado um novo algoritmo de segmentação de texto que utiliza
técnicas de inteligência artificial para detectar o texto. Utilizando uma técnica de limiarização
baseada em percepção visual, o plano de fundo das imagens é removido corretamente, mesmo
quando há uma visível degradação. Os componentes da imagem são descritos utilizando
diferentes características para caracteres e sequências de caracteres. Elas são usadas para treinar
dois SVDDs que se tornam capazes de detectar texto nesses formatos. Visando diminuir o erro
da segmentação, foram utilizadas técnicas de separação dos componentes alongados que
poderiam causar confusão na segmentação final, restaurados nas etapas finais de recuperação.
O método proposto obteve bons resultados, mesmo utilizando imagens de treinamento
para os caracteres criadas artificialmente. A análise de indicadores de classificação binária em
relação a imagens de ground truth produziu resultados como CCM médio de 0,6473 e 0,6547
para mapas e plantas baixas, respectivamente. Outro indicador a ser destacado é a precisão que
teve médias de 73,71% para mapas e de 82,88% para plantas baixas. Quando comparado a
outros métodos, o método proposto obteve valores muito superiores de sensibilidade e CCM.
Parte da pesquisa foi usada para produzir o artigo (MELLO; MACHADO, 2014),
aceito na 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2014),
conferência que acontece em Outubro de 2014 em San Diego, Califórnia, Estados Unidos.
6.1 Trabalhos Futuros
Com a análise dos resultados obtidos foram identificadas possíveis melhorias para o
algoritmo proposto. A seguir, são listados alguns pontos para o desenvolvimento do algoritmo:
102

Avaliar o uso de diferentes classificadores, como técnicas cuja otimização seja mais
simples que as do SVDD, a fim de agilizar o processamento;

Avaliar o uso de outras características para descrever os componentes, utilizando
técnicas de mineração de dados para escolher as que melhor os representarem;

Estudar a inclusão de características e classificadores capazes de detectar texto de escrita
cursiva;

Evoluir a técnica de recuperação de componentes de maneira que seja possível recuperar
partes do texto que colidirem com elementos gráficos.
103
Referências
ABBYY Solutions for Mobile Capture. Disponível em:
<http://www.abbyy.com/solutions/mobile/>. Acesso em: 14 ago. 2014.
ADAM, S. et al. Symbol and character recognition: application to engineering drawings.
International Journal on Document Analysis and Recognition, v. 3, n. 2, p. 89–101, 2000.
AHMED, S. et al. Text/Graphics Segmentation in Architectural Floor Plans. 2011
International Conference on Document Analysis and Recognition, p. 734–738, set. 2011.
ALMAZAN, J.; FORNES, A.; VALVENY, E. Deformable HOG-Based Shape Descriptor.
2013 12th International Conference on Document Analysis and Recognition, p. 1022–
1026, ago. 2013.
BALDI, P.; BRUNAK, S.; CHAUVIN, Y. Assessing the accuracy of prediction algorithms
for classification: an overview. Bioinformatics Review, v. 16, n. 5, p. 412–424, 2000.
BISHOP, C. M. Pattern Recognition and Machine Learning. [s.l.] Springer, 2006.
BISWAS, S.; DAS, A. K. Text extraction from scanned land map images. 2012 International
Conference on Informatics, Electronics & Vision (ICIEV), p. 231–236, maio 2012.
BREIMAN, L. Random Forests. Machine learning, v. 45, n. 1, p. 5–32, 2001.
CANNY, J. A Computational Approach to Edge Detection. IEEE transactions on pattern
analysis and machine intelligence, v. PAMI-8, n. 6, p. 679–698, 1986.
Cenários. Disponível em: <http://www.bracelpa.org.br/web/pt/midia/cenarios.htm>. Acesso
em: 15 ago. 2014.
CHERIET, M. et al. Character Recognition Systems: A Guide for Students and
Practitioners. [s.l.] Wiley-Interscience, 2007.
CORTES, C.; VAPNIK, V. Support-vector networks. Machine Learning, v. 20, n. 3, p. 273–
297, set. 1995.
104
DALAL, N.; TRIGGS, B. Histograms of Oriented Gradients for Human Detection2005
IEEE Computer Society Conference on Computer Vision and Pattern Recognition
(CVPR’05). Anais...San Diego, CA, USA: IEEE, 2005 Disponível em:
<http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1467360>. Acesso em: 9
jul. 2014
DANIIL, M. et al. SCANNING OPTIONS AND CHOICES IN DIGITIZING HISTORIC
MAPS. Proc. of CIPA 2003, p. 3–6, 2003.
DAVIES, E. R. Machine Vision: Theory, Algorithms, Practicalities. 3. ed. San Francisco,
CA: [s.n.].
DE LAS HERAS, L.-P. et al. Unsupervised Wall Detector in Architectural Floor Plans. 2013
12th International Conference on Document Analysis and Recognition, p. 1245–1249,
ago. 2013.
DOVGALECS, V. et al. Spot It! Finding Words and Patterns in Historical Documents. 2013
12th International Conference on Document Analysis and Recognition, p. 1039–1043,
ago. 2013.
DUDA, R. O.; HART, P. E. Use of the Hough transformation to detect lines and curves in
pictures. Communications of the ACM, v. 15, n. 1, p. 11–15, 1 jan. 1972.
DUDA, R. O.; HART, P. E.; STORK, D. G. Pattern Classification. 2nd. ed. [s.l.] WileyInterscience, 2000.
EASLEY, G.; LABATE, D.; LIM, W. Sparse directional image representations using the
discrete shearlet transform. Appl. Comput. Harmon. Anal., v. 25, n. 1, p. 25–46, jul. 2008.
FELZENSZWALB, P. F. et al. Object detection with discriminatively trained part-based
models. IEEE transactions on pattern analysis and machine intelligence, v. 32, n. 9, p.
1627–45, set. 2010.
Fourier Descriptors. Disponível em:
<http://demonstrations.wolfram.com/FourierDescriptors/>. Acesso em: 14 ago. 2014.
105
Ghostscript Download Page. Disponível em:
<http://www.ghostscript.com/download/gsdnld.html>. Acesso em: 11 ago. 2014.
GONZALEZ, R. C.; WOODS, R. E. Digital Image Processing. 3rd. ed. [s.l.] Prentice Hall,
2007.
HE, X. C.; YUNG, N. H. C. Corner detector based on global and local curvature properties.
Optical Engineering, v. 47, n. 5, 1 maio 2008.
HE, X.; YUNG, N. Curvature scale space corner detector with adaptive threshold and
dynamic region of support. … , 2004. ICPR 2004. Proceedings of the 17th …, 2004.
HOUSTON, S. D. The First writing: Script Invention as History and Process. [s.l.]
Cambridge University Press, 2004.
ImageMagick: Convert, Edit, and Compose Bitmap Images. Disponível em:
<http://www.imagemagick.org>. Acesso em: 14 ago. 2014.
KARAOGLU, S.; FERNANDO, B.; TREMEAU, A. A Novel Algorithm for Text Detection
and Localization in Natural Scene Images. 2010 International Conference on Digital Image
Computing: Techniques and Applications, p. 635–642, dez. 2010.
LEYK, S.; BOESCH, R. Colors of the past: color image segmentation in historical
topographic maps based on homogeneity. GeoInformatica, v. 14, n. 1, p. 1–21, 16 jan. 2009.
LOWE, D. G. Object recognition from local scale-invariant features. Proceedings of the
Seventh IEEE International Conference on Computer Vision, p. 1150–1157 vol.2, 1999.
MASINI, N. et al. An algorithm for computing the original units of measure of medieval
architecture. Journal of Cultural Heritage, v. 5, n. 1, p. 7–15, jan. 2004.
MATAS, J. et al. Robust wide-baseline stereo from maximally stable extremal regions. Image
and Vision Computing, v. 22, n. 10, p. 761–767, set. 2004.
MATLAB: The Language of Technical Computing. Disponível em:
<http://www.mathworks.com/products/matlab/>. Acesso em: 11 ago. 2014.
106
MELLO, C. A. B. Segmentation of images of stained papers based on distance
perception2010 IEEE International Conference on Systems, Man and Cybernetics.
Anais...Istambul: IEEE, out. 2010
MELLO, C. A. B. PROHIST Project. Disponível em:
<http://www.cin.ufpe.br/~cabm/prohist/>. Acesso em: 15 ago. 2014.
MELLO, C. A. B.; MACHADO, S. C. S. Text Segmentation in Vintage Floor Plans and
Maps Using Visual PerceptionInternational Conference on Systems, Man and Cybernetics.
Anais...San Diego, CA, USA: 2014
MELLO, C. A. B.; OLIVEIRA, A. L. I.; SANTOS, W. P. Digital Document Analysis and
Processing. New York, New York, USA: Nova Science Publishers, 2012.
MIAO, Q. et al. Linear feature separation from topographic maps using energy density and
the shear transform. IEEE transactions on image processing : a publication of the IEEE
Signal Processing Society, v. 22, n. 4, p. 1548–58, abr. 2013.
MINETTO, R. et al. T-HOG: An effective gradient-based descriptor for single line text
regions. Pattern Recognition, v. 46, n. 3, p. 1078–1090, mar. 2013.
MORI, S.; SUEN, C. Y.; YAMAMOTO, K. Historical review of OCR research and
development. In: O’GORMAN, LAWRENCE AND KASTURI, R. (Ed.). . Document Image
Analysis. Los Alamitos, CA, USA: IEEE Computer Society Press, 1995. p. 244–273.
Old Maps Online. Disponível em: <http://www.oldmapsonline.org/>. Acesso em: 10 ago.
2014.
PRATIM ROY, P. et al. Multi-oriented touching text character segmentation in graphical
documents using dynamic programming. Pattern Recognition, v. 45, n. 5, p. 1972–1983,
maio 2012.
PRTools: A Matlab toolbox For Pattern Recognition. Disponível em: <http://prtools.org/>.
Acesso em: 11 ago. 2014.
RUSIÑOL, M. et al. Browsing Heterogeneous Document Collections by a SegmentationFree Word Spotting MethodICDAR’11. Anais...2011
107
SHI, C. et al. Scene text detection using graph model built upon maximally stable extremal
regions. Pattern Recognition Letters, v. 34, n. 2, p. 107–116, jan. 2013.
SONKA, M.; HLAVAC, V.; BOYLE, R. Image processing, analysis, and machine vision.
4th. ed. [s.l.] Cengage Learning, 2014.
Statistiken. Disponível em: <https://www.vdp-online.de/en/papierindustrie/statistik.html>.
Acesso em: 14 ago. 2014.
TARAFDAR, A. et al. A Two-Stage Approach for Word Spotting in Graphical Documents.
2013 12th International Conference on Document Analysis and Recognition, p. 319–323,
ago. 2013.
TAX, D. M. J. Dd_tools Pattern Recognition Laboratory. Disponível em:
<http://prlab.tudelft.nl/david-tax/dd_tools.html>. Acesso em: 11 ago. 2014.
TAX, D. M. J.; DUIN, R. P. W. Support vector data description. Machine learning, p. 45–
66, 2004.
TOMBRE, K. et al. Text/Graphics Separation RevisitedProceedings of the 5th International
Workshop on Document Analysis Systems V. Anais...2002Disponível em:
<http://link.springer.com/chapter/10.1007/3-540-45869-7_24>. Acesso em: 8 ago. 2014
VASSILIEVA, N.; FOMINA, Y. Text detection in chart images. Pattern Recognition and
Image Analysis, v. 23, n. 1, p. 139–144, 26 mar. 2013.
VLFeat. Disponível em: <http://www.vlfeat.org/>. Acesso em: 11 ago. 2014.
WEINMAN, J. Toponym Recognition in Historical Maps by Gazetteer Alignment. 2013 12th
International Conference on Document Analysis and Recognition, p. 1044–1048, ago.
2013.
ZHANG, D.; LU, G. Study and evaluation of different Fourier methods for image retrieval.
Image and Vision Computing, v. 23, n. 1, p. 33–49, jan. 2005.