108
Pós-Graduação em Ciência da Computação Universidade Federal de Pernambuco [email protected] www.cin.ufpe.br/~posgraduacao Recife 2014 SAULO CADETE SANTOS MACHADO SEGMENTAÇÃO DE TEXTO EM IMAGENS DE MAPAS E PLANTAS BAIXAS ANTIGOS Dissertação de Mestrado

SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

  • Upload
    others

  • View
    15

  • Download
    0

Embed Size (px)

Citation preview

Page 1: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · 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

Universidade Federal de Pernambuco

[email protected]

www.cin.ufpe.br/~posgraduacao

Recife

2014

SAULO CADETE SANTOS MACHADO

SEGMENTAÇÃO DE TEXTO EM IMAGENS DE MAPAS E

PLANTAS BAIXAS ANTIGOS

Dissertação de Mestrado

Page 2: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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 FEDERAL DE

PERNAMBUCO COMO REQUISITO PARCIAL PARA

OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIA DA

COMPUTAÇÃO.

ORIENTADOR: PROF. DR. CARLOS

ALEXANDRE BARROS DE MELLO

Recife

2014

Page 3: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado
Page 4: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 5: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 6: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 7: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 8: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 9: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 10: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 11: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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)

Page 12: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 13: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 14: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 15: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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,

Page 16: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 17: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 18: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 19: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 20: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 21: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 22: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 23: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 24: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 25: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 26: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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:

Page 27: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

26

𝑎𝑛 =1

𝐿∑𝑠(𝑡)𝑒(

−𝑗2𝜋𝑛𝑡𝐿

)

𝐿−1

𝑡=0

(4)

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

𝑛=0

(5)

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

Page 28: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 29: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 30: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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,

Page 31: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 32: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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)

Page 33: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 34: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 35: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

34

maximizar ‖𝒘‖−1 ou minimizar ‖𝒘‖2. O problema de otimização pode ser resolvido através

da equação a seguir (BISHOP, 2006)b:

arg min

𝒘,𝑏

1

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

−1

2∑∑𝛼𝑖𝛼𝑗𝑧𝑖𝑧𝑗𝑘(𝑥𝑖 , 𝑥𝑗)

𝑁

𝑗=1

𝑁

𝑖=1

(18)

com respeito às restrições:

𝛼𝑖 ≥ 0, 𝑖 = 1,… , 𝑁,

∑𝛼𝑖𝑧𝑖

𝑁

𝑖=1

= 0. (19)

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

𝛼𝑖{𝑧𝑖𝑔(𝑥𝑖) − 1} = 0

(20)

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

Page 36: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

35

0 ≤ 𝑎𝑖 ≤ 𝐶, 𝑖 = 1, … ,𝑁,

∑𝑎𝑖𝑧𝑖

𝑁

𝑖=1

= 0. (21)

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.

Page 37: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 38: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 39: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 40: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 41: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 42: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 43: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 44: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 45: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 46: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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 Fourier-

Mellin (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 (Scale-

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

Page 47: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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 sub-

regiõ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.

Page 48: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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ós-

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

Page 49: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 50: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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 classifica-

los 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

Page 51: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 52: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 53: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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)

Page 54: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

53

(b)

Page 55: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

54

(c)

Page 56: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 57: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 58: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 59: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 60: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

59

Figura 4.4: Resultados das operações de pré-processamento.

(a)

(b)

(c)

Page 61: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 62: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 63: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 64: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

𝐶 =

𝐴

𝑃2 (26)

𝐿 =

𝐴(𝑒𝑠𝑞𝑢𝑒𝑙𝑒𝑡𝑜(𝑐))

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

Page 65: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 66: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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𝑘ℎ

𝑘=0

(28)

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

Page 67: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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:

𝑛𝐻𝑂𝐺 = 31𝑐2∑4𝑘ℎ

𝑘=0

(29)

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

Page 68: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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:

arg min𝑅,𝒂,𝝃

𝑅2 + 𝐶∑𝜉𝑖

𝑁

𝑖

(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

Page 69: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 70: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 71: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

{|𝑦𝑡𝑜𝑝𝑡 − 𝑦𝑏𝑎𝑖𝑎| < 𝐿𝑣 ou |𝑦𝑏𝑎𝑖𝑡 − 𝑦𝑡𝑜𝑝𝑎| < 𝐿𝑣}

(34)

Proximidade horizontal:

|𝑦𝑡𝑜𝑝𝑡 − 𝑦𝑡𝑜𝑝𝑎| < 𝐿𝑣 e

|𝑦𝑏𝑎𝑖𝑡 − 𝑦𝑏𝑎𝑖𝑎| < 𝐿𝑣 e

{|𝑥𝑒𝑠𝑞𝑡 − 𝑥𝑑𝑖𝑟𝑎| < 𝐿ℎ 𝑜𝑢 |𝑥𝑑𝑖𝑟𝑡 − 𝑥𝑒𝑠𝑞𝑎| < 𝐿ℎ}

(35)

Page 72: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 73: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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’, ‘Times-

Roman’, ‘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

Page 74: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 75: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 76: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 77: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 78: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Positivo Negativo

Resultado

Obtido

Positivo TP FP

Negativo FN TN

Fonte: produção própria.

TPR =

TP

P (40)

TNR =

TN

N (41)

Pre =

TP

TP + FP (42)

Acc =

TP + TN

P + N (43)

CCM =

TP × TN − FP × FN

√(TP + FN)(TP + FP)(TN + FP)(TN + FN) (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

Page 79: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Page 80: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

79

Figura 5.2: Resultados obtidos para os exemplos de mapas.

(a)

Page 81: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

80

(b)

Page 82: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

81

(c)

Page 83: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

82

(d)

Page 84: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

83

(e)

Page 85: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

84

(f)

Page 86: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

85

(g)

Page 87: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

86

(h)

Page 88: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

87

(i)

Page 89: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

88

(j)

Fonte: produção própria..

Page 90: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 91: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

90

Figura 5.3: Resultados obtidos para imagens de plantas baixas.

(a)

Page 92: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

91

(b)

Page 93: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

92

(c)

Page 94: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

93

(d)

Page 95: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

94

(e)

Page 96: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

95

(f)

Page 97: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

96

(g)

Page 98: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

97

(h)

Page 99: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

98

(i)

Page 100: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

99

(j)

Fonte: produção própria.

Page 101: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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 TPR TNR Pre Acc CCM

Ahmed

et al. 39,72% 97,63% 81,54% 79,08% 0,3987

Mello e

Machado 59,20% 90,86% 72,01% 82,53% 0,5378

Método

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

Page 102: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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:

Page 103: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 104: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 105: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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

Interscience, 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.

Page 106: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.

Page 107: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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 Segmentation-

Free Word Spotting MethodICDAR’11. Anais...2011

Page 108: SAULO CADETE SANTOS MACHADO - repositorio.ufpe.br‡… · saulo cadete santos machado segmentaÇÃo de texto em imagens de mapas e plantas baixas antigos este trabalho foi apresentado

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.