Carlos Alexandre Barros de Mello

Filtragem, Compressão e Síntese

de Imagens de Documentos Históricos

Tese apresentada ao Centro de Informática da Universidade Federal de Pernambuco, como requisito parcial para a obtenção do grau de Doutor em Ciência da Computação sob a orientação do Prof. Dr. Rafael Dueire Lins.

Recife

27 de Maio de 2002

ii

Resumo

Este trabalho apresenta novos aspectos quanto ao processamento de imagens de documentos históricos. Um novo algoritmo para segmentação de imagens baseado em Entropia é proposto e analisado e comparado com diversos outros métodos, com a finalidade de gerar imagens monocromáticas de alta qualidade para inspeção visual, impressão e para inserção em ferramentas de Reconhecimento Óptico de Caracteres. Com a aplicação desse novo algoritmo, um sistema de síntese de imagens de documentos históricos é proposto, onde a textura do papel é criada automaticamente a partir de informações estatísticas da textura original. À essa textura é adicionada a imagem de textual, também sintetizada, apresentando a imagem final do documento com características perceptualmente similares à imagem original e com diferenças estatisticamente não-significantes.

iii

Abstract

This Thesis presents news features on historical documents image processing. A new entropy-based segmentation algorithm is proposed and analysed, comparing it with similar techniques, generating high-quality monochromatic images for visual inspection, printing and for better response of Optical Character Recognition tools. With the development of this new algorithm, a system for automatic generation of images of historical documents is proposed, where the paper texture is fully created from statistical information of the original texture. To this texture, the textual image, also automatically generated, is added and the final image is presented with features which are perceptually similar to the original one and with differences statistically not significant.

iv

Sumário

Índice de Figuras v

Índice de Tabelas vii

Tabela de Símbolos e Siglas viii

Introdução 10

1 Reconhecimento Óptico de Caracteres: Técnicas e Ferramentas 19 1.1 Um Ambiente para Processamento Automático de Imagens de Documentos 19 1.2 Algoritmos para Reconhecimento Óptico de Caracteres 27

1.2.1 Redes Neurais 28 1.3 Um Estudo Comparativo entre Ferramentas Comerciais de OCR 33

1.3.1 Descrição dos Experimentos 36 1.3.2 Transcrição de Documentos Históricos 39 1.3.3 Análise de Erros 39

1.4 Conclusão 40

2 Segmentação de Documentos 42 2.1 Algoritmos Clássicos de Segmentação 44

2.1.1 Algoritmo de Pun 46 2.1.2 Algoritmo de Kapur-Sahho-Wong 47 2.1.3 Algoritmo de Johannsen e Bille 48

2.2 Um Novo Algoritmo para Segmentação Baseado em Entropia 50 2.2.1 O Novo Algoritmo de Segmentação Aplicado a Imagens Coloridas 60

2.3 Algoritmos de Segmentação e Reconhecimento Óptico de Caracteres 67 2.4 Conclusão 67

3 Análise de Texturas 69 3.1 Geração de Texturas 1: Preenchendo e Colorindo 70

3.1.1 Método Baseado em Assimetria 73 3.1.2 Método Baseado em Curtose 74 3.1.3 Algoritmo de Coloração da Textura por Matiz 74

3.2 Geração de Texturas 2: Geração Automática de Texturas Coloridas 77 3.2.1 Análise das Texturas Sintéticas 80

3.3 Conclusão 84

4 Geração Automática de Imagens de Documentos Históricos 85 4.1 Geração por Composição de Imagens 86 4.2 Geração Completa 88

4.2.1 Caracterização da Base de Imagens da Fonte 88 4.2.2 Processo de Geração da Imagem 90

4.3 Conclusão 93

Conclusões e Trabalhos Futuros 95

v

Índice de Figuras

Figura 1. Exemplo de um documento do acervo de Joaquim Nabuco. 13 Figura 2. Sistema de geração por composição de imagens aplicado a documentos manuscritos ou datilografados.

16

Figura 3. Sistema de geração completa da imagem da tinta e do papel aplicado apenas a documentos datilografados.

17

Figura 4. Esquema do processo completo para reconhecimento de caracteres 20 Figura 5. Ruído em imagens monocromáticas 22 Figura 6. Exemplo de filtragem por vizinhança usando máscaras de bits 3x3, apresentando um pixel branco cercado por 8 pretos e um pixel preto cercado por 8 brancos

22

Figura 7. “Sombra” que surge na borda dos caracteres, provocando, em alguns casos, a união de duas ou mais letras.

22

Figura 8. Exemplo de aplicação da operação morfológica de erosão 23 Figura 9. Simulação de uma segmentação de documento 24 Figura 10. Exemplo de Segmentação de uma imagem 26 Figura 11. Exemplos de letras usadas como amostras de documentos históricos 30 Figura 12. Gráfico do Erro Médio Quadrático da rede até sua convergência 33 Figura 13. Deslocamento do Histograma do tom azul com o aumento do brilho de uma imagem.

35

Figura 14. Brilho versus Precisão para o TextBridge e o Corel OCR Trace 38 Figura 15. Brilho versus Precisão para o Omnipage e o Wordlinx 38 Figura 16. Detalhes da degradação na digitalização 38 Figura 17. Exemplo de recorte de cor usando o software Photoshop 43 Figura 18. Algoritmos de segmentação baseados em médias 44 Figura 19. Algoritmo de segmentação de Otsu. 45 Figura 20. Algoritmos de segmentação aplicados à imagem da Figura 17.a 49 Figura 21. Exemplos de documentos pertencentes a cada classe definida 51 Figura 22. Simulação da disposição de duas diferentes classes em um documento e a separação destas classes dada por um parâmetro qualquer como Entropia, por exemplo

52

Figura 23. Projeções de H em duas componentes de Hw e Hb 52 Figura 24. Modificação do recorte nas cores definido para a classe de imagens com

vi

H≤0,25 53 Figura 25. Modificação do recorte nas cores definido para a classe de imagens com 0,25 < H < 0,30

53

Figura 26. Novo algoritmo aplicado à imagem da Figura 17.a 55 Figura 27. Aplicação do novo algoritmo de segmentação e outros algoritmos em cartões postais em tons de cinza

56

Figura 28. Exemplo de documento onde o algoritmo mostrou-se ineficiente 57 Figura 29. Pré-processamento no documento anterior para corrigir segmentação 57 Figura 30. Exemplo de carta com Hw = 0 58 Figura 31. Aplicação do algoritmo em grupos de linhas 59 Figura 32. Exemplo de segmentação de um documento datilografado 60 Figura 33. Aplicação do novo algoritmo a imagens coloridas de documentos Datilografados

62

Figura 34. Segmentação do documento da Figura 1. 63 Figura 35. Aplicação do novo algoritmo a imagens com interferência frente-verso 65 Figura 36. Aplicação do algoritmo a imagens coloridas de cartões postais 66 Figura 37. Exemplo de filtragem eliminando apenas os pixels classificados como Tinta

69

Figura 38. Distribuições com terceiros e quartos momentos significativamente diferentes de uma distribuição Gaussiana.

72

Figura 39. Exemplo de preenchimento usando o algoritmo de Assimetria. 73 Figura 40. Exemplo de preenchimento usando o algoritmo de Curtose 74 Figura 41.Gaussiana modificada com uso da Variância ao invés do Desvio Padrão. 79 Figura 42. Texturas consideradas com ruído em experimento com ANOVA. 81 Figura 43. Amostras de letras u retiradas de diferentes cartas entre 1882 e 1888. 85 Figura 44. Configuração para geração automática de documentos utilizando a imagem da parte referente a tinta adicionada a textura gerada.

86

Figura 45. Exemplos de imagens de caracteres extraídos dos documentos para gerar Fonte

89

Figura 46. Parte da base de caracteres usada na geração automática da imagem Textual

90

Figura 47. Processo de geração da imagem de um documento histórico. Primeira Fase: Criação dos arquivos de dados e do arquivo de texto com o conteúdo da carta.

91

Figura 48.Processo de geração da imagem de um documento histórico. Segunda

Fase: Geração da imagem a partir dos arquivos de dados e de texto

91

Figura 49. Geração automática da imagem do documento da Figura 1. 92 Figura 50. Documento usado como entrada de diversos OCR’s. 103 Figura 51. Exemplo de Rotação de um documento. 111 Figura 52. Aplicação da transformada de Radon para determinar o ângulo de rotação de uma imagem.

112

vii

Índice de Tabelas

Tabela 1. Iteração e respectivo Erro Médio Quadrático para Rede Neural usada no reconhecimento de caracteres

32

Tabela 2. Principais características de algumas ferramentas de OCR 34

Tabela 3. Taxa de acerto média para diferentes resoluções em imagens monocromáticas 36

Tabela 4. Taxa de acerto média para diferentes resoluções de imagens em tons de cinza 36

Tabela 5. Taxa de acerto média para diferentes graus de rotação para uma imagem com 250 dpi

37

Tabela 6. Melhores valores de brilho para maior taxa de acerto no reconhecimento 38

Tabela 7. Taxa de acerto para documentos históricos datilografados 39

Tabela 8. Taxa de acerto do Corel OCR Trace para documentos históricos datilografados filtrados por algoritmos baseados em entropia

67

Tabela 9. Taxa de acerto do OmniPage para documentos históricos datilografados filtrados por algoritmos baseados em entropia

67

Tabela 10. PSNR (em dB) entre a imagens originais e as versões coloridas apresentadas nas Lâminas 14, 15 e 16

76

Tabela 11. Matizes mais freqüentes em amostras de texturas 77

Tabela 12. Entropia da distribuição das matizes em amostras de texturas 78

Tabela 13. Valor médio da Relação Sinal-Ruído de Pico (PSNR) e do Erro Médio Quadrático (EMQ) para um conjunto de 200 texturas geradas automaticamente

80

viii

Tabela de Símbolos e Siglas

(Dispostos por ordem de aparição no texto) dpi – dots per inch (pontos por polegada) OCR – Optical Character Recognition (Reconhecimento Óptico de Caracteres) r – Componente Vermelha de uma cor g – Componente Verde de uma cor b – Componente Azul de uma cor C – Tom de Cinza EMQ – Erro Médio Quadrático p(i) – Probabilidade do elemento i t – Valor de Corte H – Entropia Hw – Entropia das cores acima de um determinado ponto Hb - Entropia das cores abaixo de um determinado ponto mw – Constante multiplicativa associada com Hw mb – Constante multiplicativa associada com Hb cor[i] – Cor do Pixel i Hr – H para o tom de Vermelho Hwr - Hw para o tom de Vermelho Hbr - Hb para o tom de Vermelho Hg – H para o tom de Verde Hwg - Hw para o tom de Verde Hbg - Hb para o tom de Verde Hb – H para o tom de Azul Hwb - Hw para o tom de Azul Hbb - Hb para o tom de Azul N – Número de elementos (em uma imagem, número de pixels) x - Média σ - Desvio Padrão

nM - Momento Central de Ordem n Sk – Assimetria (Skewness) Kurt – Excesso de Curtose (Kurtosis) max – Cor mais freqüente d - Número de linhas de uma imagem matiz – Valor de Matiz matiz_max – Matiz mais freqüente h_hue – Entropia das matizes paleta[i] – Entrada i da paleta de cores da imagem PSNR – Razão Sinal-Ruído de Pico (Peak Signal-to-Noise Ratio) dB – Unidade Decibel ANOVA – Análise de Variância NS – Diferenças Estatisticamente Não-Significativas S – Diferenças Estatisticamente Significativas GLCM – Matriz de Co-Ocorrência de Tons de Cinza (Grey Level Co-Occurrence Matrix)

ix

Agradecimentos

Gostaria de agradecer a todos que tornaram esta Tese possível, em particular: • À Deus por tudo e por todos que pôs no meu caminho, me dando as oportunidades às quais

tentei aproveitar o máximo possível. • À Banca que avaliou esta Tese composta pelos professores Alejandro Frery, Ana Lúcia

Candeias, Flávio Bortolozzi, Judith Kelner e Valdemar Cardoso, pela disposição em ler atentamente o trabalho por, pelo menos, duas vezes e tecer comentários, sempre buscando o seu crescimento.

• A todos os meus amigos pelo apoio durante todo este longo período de doutorado. Não tenho como citar o nome de todos, mas não posso deixar de mencionar os nomes de Hermes e Unilton, pelos três últimos anos de convivência quase diária.

• Ao amigo e mestre prof. Dr. Valdemar Cardoso da Rocha Júnior pelo exemplo de profissionalismo como professor e pesquisador.

• Ao CNPq pelo apoio financeiro ao projeto. • À minha família: Aos meus pais por todo o esforço de uma vida inteira de dedicação única aos

filhos – seremos sempre gratos por tudo; À minha irmã, Cláudia, exemplo de força, dedicação e coragem, fonte de uma sabedoria sem limites Ao meu filho, João Vittor, minha alegria, pelo sorriso de todas as manhãs, dando forças para continuar esse trabalho e sendo ele o responsável pelos meus poucos momentos de descanso e lazer.

• Ao meu orientador, prof. Dr. Rafael Dueire Lins. Sem dúvida, já parte de minha família, a quem eu não posso enumerar a quantidade de coisas que tenho para agradecê-lo, desde a insistência em minha vinda ao doutorado, à força em momentos difíceis da vida, crença em minha capacidade, responsável pelo meu preparo para as mais diversas situações dentro da vida acadêmica, etc, etc, etc. Sem dúvida, a melhor expressão para a palavra “Educador”.

10

Introdução

O papel, inventado no Egito por volta de 4.000 a.C., pela sua praticidade, portabilidade e custo, representou uma das maiores revoluções tecnológicas da humanidade. Ele substituiu todas as formas de armazenamento de informações anteriores (entalhamento em pedra ou madeira, impressão em tijolos de argila, gravações em couro de animais, etc.), sendo, ainda hoje, o meio mais usado para armazenamento e difusão de informação. Isto não o torna, porém, o mais eficiente. Além da fragilidade inerente, a rápida ocupação de grandes espaços físicos e a dificuldade na busca por dados específicos são as principais desvantagens dessa forma de armazenamento de informações. Nos dias atuais, o uso dos recursos computacionais apresenta-se como alternativa viável e vantajosa para a solução de tais problemas.

A criação de dispositivos digitalizadores (scanners e câmeras digitais) tornou possível a transposição de documentos para computadores na forma de imagens. Dessa forma, é possível o armazenamento de imagens de documentos, visando uma proteção mais eficiente ao desgaste provocado pelo tempo. Armazenados em dispositivos de memória secundária, sejam ópticos, como DVD’s ou CD-ROM’s, ou magnéticos como discos rígidos, fitas, discos Zip, Jaz drives, etc., é inteiramente viável a cópia de acervos completos de documentos para outro dispositivo de armazenamento sem nenhuma perda de dados, posterior à digitalização.

Talvez o ponto crítico dessa tecnologia esteja na grande quantidade de espaço necessário para armazenar as imagens. Por exemplo, uma página em papel A4 digitalizada, utilizando uma resolução para digitalização de 200 dpi1 e 256 tons de cinza, gera uma imagem de cerca de 1.700x2.400 pixels que ocupa 4.113 Kbytes, se armazenada no formato padrão do sistema Windows, o BMP. Isso torna a prática extremamente onerosa. Se a imagem for relativa a um texto, chamada algumas vezes de imagem textual, a informação contida nela pode ser armazenada em um formato de texto ocupando menos de 100 Kbytes.

A transposição de imagens para o formato de texto surge como uma solução a este problema. Uma transposição não automática é inaceitável devido aos custos envolvidos, a baixa velocidade e a baixa confiabilidade do processo. Um sistema automático deve reconhecer os caracteres presentes no documento, diferenciando-os de imagens ou outros dados que possam estar presentes, e transpô-los para caracteres ASCII (American Standard Code for Information Interchange – padrão computacional de caracteres). Este processo é chamado de Reconhecimento Óptico de Caracteres (OCR - Optical Character Recognition). O espaço ocupado por um arquivo de texto é centenas de vezes menor que o ocupado por uma imagem, além de possibilitar a execução de mecanismos de busca por palavras-chave. As dificuldades estão, basicamente, em dois pontos: a escolha do melhor método para realizar a transposição e os melhores ajustes de parâmetros para digitalização já que ajustes inadequados de resolução, brilho, contraste, número de cores, etc., podem provocar uma atuação ineficiente dos algoritmos de reconhecimento e podem requerer uma nova digitalização ou um processamento específico da imagem. O objetivo do Reconhecimento Óptico de Caracteres é o mesmo tanto para documentos manuscritos ou datilografados. No entanto, devido à grande quantidade de características distintas inerentes à escrita de cada pessoa, o reconhecimento de textos manuscritos ainda é um ponto em estudo. Ainda não foi definido um algoritmo eficiente para um perfeito sistema para reconhecimento de

1 dots per inch – pontos por polegada: medida da densidade de resolução de imagens em computadores

11

caracteres manuscritos independente do usuário. Para documentos datilografados, dependendo da qualidade do papel e da tinta, o problema já está praticamente resolvido com altas taxas de acerto [50].

Além do uso de OCR’s para diminuição do espaço de armazenamento, a criação de livros digitais surge hoje como uma área em grande expansão. Embora o ser humano esteja mais acostumado com o uso de papel e ainda o considere o melhor método para leitura [60], os livros digitais têm evoluído bastante em termos de interface ao longo dos anos. Novos livros podem ser gerados diretamente no computador, mas a transposição para o universo digital da literatura já existente necessita do uso de ferramentas eficientes para reconhecimento automático de caracteres.

Nosso objetivo neste trabalho é o desenvolvimento de técnicas que possam ser utilizadas na criação de um banco de dados de imagens de documentos históricos. Este tipo de acervo, de extrema valia cultural e social, possui uma grande diversidade de características. Mesmo assim, estudos em imagens de documentos históricos ainda são escassos tornando ainda mais relevantes as informações aqui dispostas. É apresentada, ao longo desta tese, uma descrição detalhada de uma série de fatores fundamentais no estudo de tais imagens.

Esta tese está inserida no Projeto Nabuco [38][101] que foi desenvolvido visando a atender às necessidades da Fundação Joaquim Nabuco em preservar documentos históricos e tornar mais fácil o acesso a esses. A Fundação Joaquim Nabuco (FUNDAJ), um instituto de pesquisa social, situada em Recife, Pernambuco, possui rico acervo, com centenas de milhares de documentos pertencentes a figuras de destaque da história nacional, destacando dentre elas, seu patrono Joaquim Nabuco.

Joaquim Nabuco (1849-1910), escritor, estadista e diplomata, teve um papel fundamental na campanha de libertação dos escravos no Brasil. Dentre os documentos pertencentes a seu acervo existem diversas cartas (manuscritas e datilografadas), cartões postais, etc. Particular destaque merece seu acervo de cartas com cerca de 6.500 documentos, perfazendo um total de aproximadamente 30.000 páginas.

Esse projeto visa ao desenvolvimento de um ambiente, fornecendo um conjunto de ferramentas para executar o processo de aquisição, processamento, armazenamento e gerenciamento de imagens de documentos históricos, tendo sido o acervo de documentos de Joaquim Nabuco priorizado face sua importância histórica, grande demanda de consulta e também devido a degradação sofrida pelo papel pela alta alcalinidade empregada no processo químico de sua formação no final do século XIX e início do século XX. O ambiente computacional Nabuco deve ser capaz de processar um grande número de documentos, sendo operado por pessoas não-especializadas em informática, trabalhando em dois níveis:

• O primeiro objetivo consiste em preservar o valor iconográfico do documento, substituindo de forma mais vantajosa as técnicas de fotografias e microfilmagens amplamente utilizadas hoje em dia para preservação desse tipo de documento. Para isso, imagens coloridas de alta definição são geradas.

• O segundo objetivo consiste em tornar as informações desses documentos facilmente acessíveis a pesquisadores. Nesse caso, imagens em preto e branco de boa definição são geradas [14][15].

Alcançar o primeiro objetivo não é difícil. Por outro lado, obter boa qualidade em imagens preto e branco não é uma tarefa trivial. Em alguns documentos a tinta está esmaecida; em outros casos a tinta está transpassando de uma face para outra do papel, o que se torna uma grande dificuldade quando o documento está escrito dos dois lados. Neste caso, o algoritmo padrão de conversão de imagens coloridas para imagens preto e branco através de limiarização com um valor fixo [18], gera imagens de qualidade inaceitável, como mostraremos adiante. Para prover o acesso fácil às informações, as imagens devem ser comprimidas e armazenadas em um formato conveniente. Esses arquivos de imagens serão parte de um banco de dados multimídia, também desenvolvido no projeto [101].

12

O nível de compressão da imagem sem degradação da sua qualidade é também um dos itens relevantes dessa pesquisa. Para tanto, novos algoritmos foram desenvolvidos [43][51][52], buscando aumentar a taxa de compressão das imagens através de características inerentes às próprias imagens de documentos.

A aquisição das imagens das cartas consiste de três fases básicas que são : • Digitalização das imagens através de scanners • Filtragem da imagem digitalizada • Compressão dos documentos.

Logo após essas fases, as imagens estarão prontas e disponíveis para o sistema de pesquisa e consulta.

No ambiente Nabuco, o processo de digitalização das cartas é feito com a utilização de um scanner de mesa. Scanner é um dispositivo que efetua uma varredura mecânica com uma linha de sensores sobre a imagem a ser digitalizada. A digitalização forma uma codificação que pode ser gravada em arquivos.

No início do Projeto Nabuco, foi utilizado um scanner de mesa EPSON ES-300C. Esse modelo tinha as seguintes características:

Scanner Resolução Óptica Resolução de Cor Máxima Área de Leitura Epson ES-300C 300 dpi 24 bits/pixel A4 ou Carta

Posteriormente, utilizou-se outro scanner de mesa HP modelo ScanJet 4c com as seguintes características:

Scanner Resolução Óptica Resolução de Cor Máxima Área de Leitura HP Scanjet 4c 600 dpi 24 bits/pixel 8.5" x 14" (Legal) Experimentos efetuados conjuntamente com os especialistas em documentos históricos da

Fundação Joaquim Nabuco definiram um bom ponto de equilíbrio entre resolução de digitalização, tempo de digitalização, espaço para armazenamento e tempo de transmissão de documentos via rede. Para tanto, documentos representando os diversos tipos de papel, escrita, degradação, etc. existentes no acervo foram digitalizados com diferentes resoluções e analisados pelos especialistas quanto à visualização em tela de vídeo e re-impressão em impressoras jato de tinta coloridas. O valor de resolução de 200 dpi apresentou resultados satisfatórios, observando também o espaço necessário para armazenamento de tais imagens.

Dessa forma, os documentos do acervo foram digitalizados em 16 milhões de cores (formato computacional chamado de true colour). Tais experimentos também apontaram para a conveniência e adequação do formato de armazenamento JPEG [72] com uma taxa de perda de cerca de 1%. Nesse formato, as imagens serão armazenadas em CD-Rom’s com finalidades de preservação. Observamos que a luz proveniente do scanner para fins de digitalização não apresentou níveis representativos de degradação nos documentos, segundo os especialistas da FUNDAJ.

As ferramentas de filtragem de imagens existentes atualmente nos softwares comerciais (como PhotoShop, PaintShop Pro, PhotoImpact, etc) para processamento de imagens são lentas para o tamanho das imagens do Projeto Nabuco, requerem usuários especializados para aquisição e filtragem da imagem e não são completamente adequadas para nossa aplicação. Por esses motivos, surgiu a necessidade de se desenvolver um algoritmo próprio dentro do ambiente.

Dois algoritmos distintos são usados no ambiente Nabuco para a filtragem dos documentos, de acordo com a natureza do documento. São considerados os seguintes aspectos:

• O documento não apresenta interferência do verso na parte da frente. Este caso, já implementado anteriormente [14], é o mais simples.

• Há interferência da tinta do verso no anverso face à translucidez do papel. Neste caso, algumas técnicas foram desenvolvidas e serão aqui apresentadas.

13

Um exemplo de uma carta pertencente ao acervo da Fundação Joaquim Nabuco pode ser visto na Figura 1 a seguir.

Figura 1. Exemplo de um documento do acervo de Joaquim Nabuco.

Mais exemplos de documentos pertencentes ao acervo podem ser vistos nas lâminas de 1

a 5, no final desta tese. Esses documentos foram impressos em uma impressora/copiadora Xerox DocuColor 40 com resolução de 600 dpi em cores e em tons de cinza.

Como o Projeto Nabuco é anterior a esta tese, é mister aclarar qual a contribuição desta dissertação. A idéia original do projeto global é do prof. Dr. Rafael Lins e foi descrita no artigo [38]. Três dissertações de mestrado foram desenvolvidas dentro do Projeto Nabuco, merecendo serem destacadas as suas contribuições:

14

• Luciano Galdino Rosa Neto [71] tratou aspectos da base de dados do Projeto Nabuco, modificando o software de bibliotecas Micro-Isis para incluir imagens e também desenvolveu módulos para o Gais, possibilitando o acesso aos documentos via Internet.

• O autor desta tese, durante sua dissertação de Mestrado [43], cuidou da compressão das imagens monocromáticas do acervo, criando o algoritmo chamado de Run-Length Modificado.

• Leopoldo Rodrigues França Neto, na sua dissertação de Mestrado [24], definiu os principais aspectos do Ambiente Nabuco, desenvolvendo um sistema semi-automático para binarização das imagens do acervo e apresentando uma variação no algoritmo de Run-Length Modificado. Ficam assim caracterizadas as contribuições mais significativas ao Projeto Nabuco não

constantes da presente tese. Desta maneira, toda e qualquer referência ao Projeto Nabuco que não seja devidamente atribuída a outrem ou ao próprio autor durante a dissertação de Mestrado, é original e faz parte exclusiva da presente tese, sendo o mesmo, sob a orientação do seu supervisor, os únicos responsáveis pelas idéias, algoritmos e programas aqui apresentados.

Outros exemplos de sistemas para disponibilização de versões digitais de acervos de documentos históricos podem ser encontrados. Dentre esses, destacamos: • Projeto Gutenberg: Desenvolvido pela Universidade de Keio, Tóquio, dentro do Projeto

HUMI (Humanities Media Interface Project). Apresenta a versão digital da Bíblia impressa originalmente por Gutenberg, composta por dois volumes, com mais de 1.300 páginas. As páginas foram digitalizadas com uma resolução de fac-símile e applets Java são utilizados para apresentar as imagens na janela do Navegador. O site possui ainda outras obras digitalizadas. Maiores informações em: http://www.humi.keio.ac.jp.

• Livro de Emblemas: Projeto para criação de uma acervo digital de emblemas franceses, desenvolvido pela Universidade de Glasgow. Maiores informações podem ser encontradas em: http://www.emblems.arts.gla.ac.uk.

• Projeto ARTFL (American and French Research onthe Treasure of the French Language): Desenvolvido pela Universidade de Chicago, EUA. Possui diversas coleções de textos e enciclopédias francesas do século XVI. Algumas obras têm mais de 17 volumes, totalizando mais de 18.000 páginas. Maiores informações: http://www.lib.uchicago.edu/efts/ATFL.

• Koninklijke Bibliotheek: Uma seleção de objetos, manuscritos, livros, gravuras e pinturas da Idade Média até o século XX publicados na forma de livro e apresentados de forma digital. Todo o material apresentado refere-se aos Países Baixos. Maiores informações sobre o projeto em: http://www.konbib.nl/index-en.html.

• The Digital Scriptorium: O projeto apresenta o desenvolvimento de uma base de dados digital de manuscritos medievais e da renascença, sendo desenvolvido por diversas bibliotecas filiadas às universidades de Berkeley e Columbia nos Estados Unidos da América. O acervo possui mais de 8.500 imagens coloridas apresentadas em diversos formatos para visualização em tela, inclusive, formatos em alta resolução com 300 dpi de resolução. Muitas imagens, porém, ainda não estão disponíveis no site: http://sunsite.berkeley.edu/Scriptorium.

• Cervantes Digital Library: Site dedicado as obras de Miguel de Cervantes, contendo sua bibliografia e uma coleção de arquivos digitais de algumas de suas obras, notadamente, Dom Quixote, a qual aparece tanto como imagens digitalizadas quanto como texto em inglês e espanhol. O projeto é fruto da colaboração de diversas universidades e do Centre de Estudios Cervantinos na Espanha. O acervo digital possui imagens armazenadas em 2 cores no formato GIF com baixa resolução. Ao todo, 6 obras são apresentadas das quais 5 já estão completas. Site: http://www.csdl.tamu.edu/cervantes/english/index.html.

• Projeto DEBORA (Digital AccEss to BOoks of the RenAissance). O principal objetivo desse projeto Europeu é o desenvolvimento de um conjunto de ferramentas para acesso remoto a livros do século XVI digitalizados, sem a necessidade de contato com as bibliotecas onde os livros originais estão localizados. A parte técnica do projeto vem sendo desenvolvida em

15

conjunto por universidades da França, Grã-Bretanha e Portugal. Diversas bibliotecas na Itália, Portugal e França associam-se às universidades fornecendo parte do material digitalizado. Mais informações em : http://debora.enssib.fr.

Nesta tese, apresentamos as bases de um novo sistema de compressão de imagens de

documentos baseado na sua transcrição. Várias etapas são definidas nesse sistema. O seu primeiro passo depende fortemente da resposta de ferramentas de OCR. Assim, concentramo-nos, de início, em buscar uma melhora na resposta de tais ferramentas quando aplicadas a imagens de documentos históricos datilografados. Esta melhora foi alcançada com o desenvolvimento de um novo algoritmo para segmentação de imagens coloridas e em tons de cinza. Com esse algoritmo, conseguimos criar uma imagem eliminando os pixels denotados aqui como papel, restando apenas o que denotamos por tinta. Este pré-processamento conseguiu aumentar significativamente a taxa de acerto dos OCR’s comerciais em cerca de 10%.

É importante salientar alguns aspectos fundamentais da restrição a textos datilografados. Por um lado, a utilização de material datilografado facilita o estudo, pois, em geral, os sistemas de reconhecimento possuem uma taxa de acerto maior nesses casos. Deve-se considerar também que as cartas são do final do século passado, quando, devido às características tecnológicas e sociais da época, os escritores possuíam suas próprias máquinas de datilografar e delas se utilizavam para escrever mesmo quando em viagem. Dessa maneira, há uma uniformidade tipográfica diferentemente de outros períodos históricos, tal como na década de 1970, onde a tecnologia permitia a troca do conjunto de esferas ou margaridas, possibilitando o uso de vários conjuntos de fontes, inclusive, em um mesmo documento. Em contrapartida à facilidade da uniformidade tipográfica, surgem como fatores de degradação a sujeira dos tipos ocasionada pelo uso e as cópias carbono (alguns documentos não são originais, mas 2a ou 3a via em carbono). Além disso, o fato de estarmos trabalhando com documentos antigos nos traz uma série de fatores bastante particulares inerentes ao acervo, dificultando bastante o trabalho. O próprio papel usado surge como um fator primordial já que seu envelhecimento, ocasionando escurecimento, fungos, manchas, dobras, amassados, etc., influencia bastante o desempenho dos algoritmos de reconhecimento das ferramentas de OCR.

A restrição a documentos datilografados aplica-se apenas às etapas onde ferramentas de OCR são usadas. Os processos de filtragem são utilizados em quaisquer imagens do acervo, incluindo documentos manuscritos e cartões postais.

Uma melhoria relevante na taxa de acerto das ferramentas de OCR permite-nos a criação de um sistema para geração de imagens, cuja maior justificativa está na alta taxa de compressão associada. Para acessar pela Internet um documento datilografado, um pesquisador ou qualquer outra pessoa não necessitará visualizar a imagem original do documento (em geral, com centenas de Kbytes); bastará copiar: o código executável do sistema de geração uma única vez, arquivos texto com cerca de 2 Kb, contendo o conteúdo da carta, e mais algumas informações armazenadas em arquivos com menos que 1 Kb que serão usadas para gerar uma imagem similar à original. A base para todo esse sistema estará sendo aqui descrita. Foi observado em [88] que o acesso pela Internet a documentos convertidos para imagem através da digitalização é bastante oneroso e traz uma série de problemas.

O sistema de geração funciona em dois níveis. O primeiro, mais rápido e gerando resultados mais próximos do original, é feito através de composição de imagens, utilizando a imagem textual gerada pela segmentação da imagem do documento original e uma textura sintética do papel da carta, conforme pode ser visto de forma resumida na Figura 2.

Em um segundo nível, o sistema gera sinteticamente não só a textura do papel, mas também a imagem textual, usando uma base de imagens de caracteres extraída dos próprios documentos. Nesse caso, o sistema utiliza uma ferramenta de OCR como apoio para geração do arquivo de texto referente ao conteúdo da carta e, por esse motivo, foi aplicado apenas a documentos datilografados.

16

Figura 2. Sistema de geração por composição de imagens aplicado

a documentos manuscritos ou datilografados.

A Figura 3 apresenta esquematicamente esse segundo aspecto do sistema. O arquivo de texto gerado pelo OCR é convertido para imagem à qual é colorida, utilizando informações da imagem textual original. Em seguida, a textura é sintetizada e adicionada ao fundo da imagem textual, formando o papel do documento.

Maiores detalhes sobre o processo de síntese proposto são vistos no Capítulo 4 desta tese. Assim, o trabalho apresentado nesta tese envolve diversos fatores de processamento de

imagens desde a criação de algoritmos para filtragem, geração automática de texturas e de documentos, até a compressão final de documentos históricos datilografados. Enquanto não existe uma definição formal para uma textura, este conceito tem particular importância em computação gráfica [85] onde é usado para dar mais naturalidade a modelos artificiais. Podemos entender por textura como um padrão que se repete, uniformemente ou não, sobre uma superfície. No nosso caso, a textura está associada às características físicas do papel do documento.

A seguir, tem-se a descrição de cada capítulo que compõe esta tese, além do presente capítulo de Introdução.

O primeiro capítulo explica como funciona, basicamente, um ambiente para processamento de documentos, algumas das principais técnicas de OCR e apresenta os tipos de problemas que podem ser encontrados em um documento digitalizado. As dificuldades inerentes ao processo de digitalização são transferidas imediatamente para a qualidade da imagem gerada. Algumas ferramentas comerciais de OCR atualmente disponíveis são analisadas e testadas quanto ao percentual de acerto face à variação de diversos parâmetros de entrada (ajuste do scanner, tonalidade do papel, textura, sensibilidade à rotação do documento, etc.), simulando diferentes graus de conhecimento de um usuário padrão. Um OCR primitivo baseado em redes neurais é desenvolvido e apresentado. Tal OCR será base para um sistema de transcrição múltipla de documentos o qual utilizará diversas ferramentas de OCR, buscando a melhor resposta entre elas em cada parte transcrita do texto.

No segundo capítulo, serão analisados alguns algoritmos de segmentação de imagens existentes. O objetivo é gerar uma imagem onde as componentes do papel possam ser eliminadas, deixando apenas a tinta. Para tanto, diversos algoritmos encontrados na literatura são testados e analisados seus comportamentos com as imagens do acervo Nabuco. Destaca-se um novo algoritmo de segmentação baseado em entropia desenvolvido no projeto, comparando-o com

17

outros similares. Em especial, será observado o problema da interferência frente-verso dos documentos (no caso de documentos escritos nos dois lados).

a)

b)

Figura 3. Representação esquemática de entrada e saída do algoritmo desenvolvido para documentos datilografados. a) Entrada: Imagem textual e textura e b) Saída: Geração da

imagem sintética

O terceiro capítulo apresenta uma análise das texturas do papel dos documentos digitalizados. Através de diversos parâmetros inerentes às texturas, é apresentado um algoritmo para criação automática de texturas coloridas dos documentos. Essa textura artificial sintetizada é semelhante à original sob diversos aspectos, principalmente, do ponto de vista de percepção do olho humano.

À imagem gerada da textura é acrescida a componente texto. No caso de documentos manuscritos, a imagem de texto gerada pelo algoritmo de segmentação é acrescida à textura. Documentos datilografados podem ser completamente sintetizados, utilizando um arquivo texto com informações contidas no documento original. O texto transcrito pelas ferramentas comerciais de OCR serve como entrada para uma ferramenta primitiva que é responsável pela segmentação do texto caractere-a-caractere de tal forma a estabelecer um conjunto de fontes tipográficas. À imagem textual gerada é adicionada a textura artificial do papel. Esse esquema de compressão é descrito no capítulo quatro.

18

Por fim, nas conclusões, é feita uma análise das contribuições dadas por este trabalho e linhas para desenvolvimentos futuros.

19

1

Reconhecimento Óptico de Caracteres: Técnicas e Ferramentas

Antes de serem iniciados os procedimentos de reconhecimento de caracteres, alguns fatores devem ser levados em consideração. A maioria dos algoritmos de reconhecimento perde grande quantidade de informação se alguma degradação for imposta à imagem. Existem problemas inerentes ao próprio documento a ser digitalizado e há ruídos adicionados no próprio processo de digitalização. Por exemplo, um certo grau de rotação adicionado ao documento pode gerar uma imagem de baixa qualidade para mecanismos de reconhecimento de caracteres. Dessa forma, é preciso pré-processar a imagem antes de prosseguir com a sua transcrição para texto. Os principais requisitos de um sistema de OCR foram descritos em [11] por Cushman-Ojha-Daniels e em [12] por Dengel-Bleisenger-Hoch-Fein-Hönes.

Uma ferramenta primitiva de OCR para documentos datilografados foi desenvolvida no âmbito desta tese com o propósito de gerar uma ferramenta ajustada especificamente ao Projeto Nabuco. No entanto, as ferramentas comerciais atualmente disponíveis estão desenvolvidas com um tão alto grau de complexidade que seria extremamente difícil, durante o período desta tese, projetar e implementar um sistema similar aos existentes. Por esse motivo, resolvemos pesquisar, dentre os mais usados softwares da área, qual o de melhor resultado. Nesse sentido, os softwares foram testados em imagens de documentos históricos manuscritos e datilografados. Para textos manuscritos, porém, as taxas de acerto foram insignificantes (próximas a 0 % em todos os casos). Em documentos datilografados, a taxa de acerto foi de 30% em alguns casos, como será analisado posteriormente.

A seguir, analisaremos, como é organizado um ambiente para processamento de documentos e alguns algoritmos para reconhecimento óptico de caracteres, destacando o uso de redes neurais. Concluiremos o capítulo com um estudo comparativo entre as principais ferramentas de OCR disponíveis comercialmente no mercado.

1.1 Um Ambiente para Processamento Automático de Imagens de Documentos

O objetivo da análise de imagens de documentos é identificar os componentes da imagem e extrair informação como um ser humano faria [55]. Uma visão geral de sistemas de processamento de documentos pode ser vista em [6] (início do desenvolvimento do antigo OCR

Capítulo

20

Wordscan da Calera Inc.), [23] (onde sugere-se o uso de restrições sintáticas em um sistema para reconhecimento de palavras, usando um modelo de Markov e uma variação no algoritmo de Viterbi), [54] (incluindo uma revisão histórica sobre o tema), [73] e [79].

Basicamente, dois tipos de componentes podem ser encontrados em documentos: texto e figuras. É importante proceder com essa identificação para que a ferramenta de OCR não perca tempo tentando processar áreas do documento compostas apenas por elementos gráficos (figuras, fotos, diagramas, etc.).

Quatro passos devem ser seguidos na imagem antes do reconhecimento final dos caracteres da imagem de um documento:

1. Captura dos dados: feita no papel do documento através de um digitalizador (tal como um scanner).

2. Processamento da imagem: análise de rotação, redução de ruídos inerentes ao papel ou inseridos pelo processo de digitalização, detecção de junção de caracteres, segmentação da imagem, etc.

3. Análise de características: após o processamento da imagem, características intermediárias devem ser encontradas para facilitar o posterior processo de reconhecimento como, por exemplo, o tamanho das fontes do documento e análise de diagramação.

4. Análise e reconhecimento de texto e gráficos: nesta fase, o documento final é gerado com grupos de pixels transcritos para títulos, sub-títulos, corpo de texto, etc. Os gráficos podem ser inseridos no documento final como imagem, dependendo do formato de saída suportar tais elementos, como XML (eXtensible Markup Language) [68], por exemplo.

Este processo pode ser visualizado de forma resumida na Figura 4 abaixo.

Figura 4. Esquema do processo completo para reconhecimento de caracteres

O primeiro e principal passo em qualquer sistema de processamento de imagens de

documentos é a aquisição das imagens. Esse ainda é o mais delicado e dependente do usuário. Além disso, os efeitos do processo de digitalização serão sentidos em todas as etapas seguintes, podendo, inclusive, gerar uma melhor ou pior resposta de uma ferramenta de OCR [19]. Diversos problemas de digitalização podem afetar o formato de um caractere, podendo, inclusive, perder pixels, deixando “buracos” o que pode dificultar o reconhecimento. Os tipos de possíveis problemas refletidos nos caracteres e provocados por problemas de digitalização (como rotação, variações na largura e altura, borramento, etc.) são modelados por Baird em [3] e utilizados para definir um sistema de geração aleatória de caracteres com tais erros.

Realizada no digitalizador (geralmente, um scanner), a determinação da resolução utilizada na digitalização é essencial para um perfeito processo de reconhecimento. Embora não haja regra definida quanto ao melhor valor de resolução para um documento, 150 a 250 dpi foi considerada, pelos técnicos em documentação histórica da Fundação Joaquim Nabuco, uma taxa adequada por gerar imagens de boa qualidade para visualização em tela de terminal de vídeo ou para re-impressão em dimensões iguais às do documento original. Um aumento na resolução implica em um aumento do número de pixels na imagem e, conseqüentemente, um aumento na quantidade de informação necessária para processar e armazenar. Qualquer alteração necessária

21

na resolução da imagem deve ser feita através de uma nova digitalização. Dessa forma, é essencial a escolha de um valor adequado, levando em consideração o tamanho do arquivo resultante, a maneira como tais imagens serão visualizadas, a velocidade de digitalização, a velocidade de transmissão via rede, o custo dos dispositivos de digitalização, transmissão, armazenamento, visualização, etc. Levando todos esses fatores em consideração, a equipe do Projeto Nabuco optou por digitalizar o acervo em 200 dpi, inclusive porque tal resolução é compatível com o padrão adotado para a transmissão/impressão de documentos via dispositivos de fac-símile. Como não seria possível a digitalização e o armazenamento de imagens em diversas resoluções diferentes, a resolução definida para o armazenamento (200 dpi) também será usada para as aplicações em Reconhecimento de Caracteres. De fato, em experimentos posteriores, apresentados na seção 1.3 desta tese, foi comprovada que uma resolução de 200 a 250 dpi apresenta as melhores taxas de acerto de ferramentas de OCR.

Observações também devem ser feitas quanto a dimensão da paleta de cores (número máximo de cores) escolhida para digitalização. Mesmo para imagens com poucas cores (como documentos, onde, geralmente, as cores predominantes são as da tinta e do papel), sugere-se uma digitalização em true colour ou em tons de cinza, permitindo a captação de nuances de tonalidade nos documentos. Isso garante uma melhor qualidade na imagem final a ser processada.

Após a digitalização, algoritmos de processamento de imagens devem ser aplicados antes do reconhecimento de caracteres, procurando corrigir defeitos na imagem ou extrair dados não só inúteis para o reconhecimento, mas que podem também dificultar o processo. As fases iniciais do processamento devem lidar com a eliminação de ruídos em uma imagem e a identificação de possíveis erros oriundos de rotação durante o processo de digitalização.

Caso o documento tenha sido mal-posicionado sobre a mesa de digitalização, a imagem gerada poderá sofrer uma inclinação a qual pode vir a gerar falhas na etapa final de reconhecimento. A rotação da imagem de um documento pode ser tratada principalmente pelo uso da Transformada de Hough [18][66]. Outros métodos, porém, também apresentam bons resultados como pode ser visto em [4], onde um sistema de detecção de grau de rotação é proposto baseado no cálculo do máximo de uma função de energia de um conjunto de projeções de caracteres. O Apêndice B desta tese apresenta as principais características da Transformada de Hough e mostra uma simulação de sua aplicação feita no software MatLab [97], usando a Transformada de Radon [25][40][70].

Corrigidos eventuais problemas de rotação, o sistema deve tentar eliminar possíveis ruídos na imagem. Definimos como ruído a presença de pixels na imagem que não correspondem à informação original (obtidos algumas vezes, através da digitalização) ou que não contém informação relevante ao processo em estudo. No caso da digitalização a partir de papéis, o ruído pode vir do próprio papel (tais como, rugosidade devido a dobras ou amassados, fungos, manchas de umidade, manchas de manuseio, respingos da tinta utilizada na escrita ou na impressão, etc.), não sendo acrescentado pelo scanner. Outros tipos de ruídos, no entanto, são devidos ao próprio processo de digitalização da imagem real, como a junção de caracteres. A Figura 5 mostra um exemplo de uma imagem sob a presença de ruídos.

Imagens digitalizadas a partir de documentos escritos estão suscetíveis à presença de ruídos na forma de pixels indesejados. Em imagens monocromáticas, por exemplo, esses ruídos podem ser identificados como pixels pretos em áreas onde deveriam haver apenas pixels brancos e vice-versa. No caso de imagens monocromáticas, esse problema pode ser parcialmente resolvido através do uso de uma filtragem por vizinhança [15][57]. Através do uso de uma máscara de bits, diversas regras podem ser aplicadas, visando a eliminação do ruído. Por exemplo, com uma máscara 3x3, um pixel preto cercado por oito pixels brancos pode ser considerado um ruído e transformado em um pixel branco. A mesma inversão pode ser realizada em um pixel branco cercado por oito pixels pretos. Um exemplo de tais máscaras pode ser visto na Figura 6.

22

a) b)

Figura 5. Ruído em imagens monocromáticas a) Exemplo de ruído e b) aproximação da imagem

Figura 6. Exemplo de filtragem por vizinhança usando máscaras 3x3, apresentando um pixel

branco cercado por 8 pretos e um pixel preto cercado por 8 brancos.

A presença de ruídos, no entanto, torna-se uma questão mais complexa quando tratamos imagens com mais cores, como imagens com 256 tons de cinza (padrão com 256 cores, variando as tonalidades do preto absoluto ao branco), por exemplo. O aumento no número de cores acarreta um aumento na quantidade de informações em uma imagem. Isso torna mais difícil a determinação do que é letra, o que é papel e o que é ruído. É importante saber usar essa quantidade maior de informação de forma a trazer melhores resultados.

Uma situação grave e difícil de ser solucionada acontece quando dois caracteres aparecem próximos em um documento e, ao serem digitalizados, são unidos na imagem. Esta união, decorrente do processo de digitalização, pode ser vista como uma “sombra” ao redor do caractere. A Figura 7 apresenta uma imagem digitalizada e, em maior escala, a presença da “sombra” como uma borda que cerca toda a letra nos pontos onde há a fronteira entre a letra e o papel (cor de frente e cor de fundo na imagem). A imagem apresentada foi digitalizada com 256 tons de cinza e uma resolução de 250 dpi.

a) b)

Figura 7. “Sombra” que surge na borda dos caracteres, provocando, em alguns casos, a união de duas ou mais letras.

a) Exemplo da “sombra” e b) aproximação da imagem na área de junção das letras.

23

Nessa mesma figura, podemos observar a junção da letra t com a letra h na parte superior das letras. Nesse caso, a imagem já apresentava uma grande proximidade entre as duas letras e a digitalização as aproximou ainda mais. Embora o olho humano consiga distinguir sintaticamente no documento original os caracteres mesmo com uma tênue fronteira entre eles e o papel, o mesmo ainda não é possível para o computador, algumas vezes. O ser humano também faz uso da semântica do documento, possibilitando a segmentação correta, mesmo se houvesse a sobreposição parcial (concatenação direta) das duas letras. A máquina, restrita a padrões sintáticos, não vislumbra tal horizonte.

Diversos algoritmos usados para reconhecimento de caracteres necessitam de uma separação perfeita dos símbolos. Dentre eles, citamos o casamento de padrões e os algoritmos estatísticos. Várias ferramentas podem provocar uma separação nas letras, incluindo processos de Morfologia Matemática [64] entre outros [37]. Uma operação morfológica de erosão [64] pode ser aplicada a imagem a fim de aumentar a separação entre os caracteres.

A Morfologia Matemática é uma forma de descrever e analisar a forma de um objeto digital, considerando que uma imagem consiste de um conjunto de elementos (pixels) que se unem em grupos em uma estrutura bi-dimensional (forma). Certas operações matemáticas em conjuntos podem ser usadas para intensificar aspectos específicos das imagens. Uma das operações mais elementares da Morfologia é a erosão. Para conjuntos A e B em Z², a erosão de A por B, denotada por AΘB, é definida como:

})(|{ ABxBA x ⊆=Θ

Ou seja, a erosão de A por B é o conjunto de todos os pontos x tal que B, transladado por x, está contido em A. Em imagens binarizadas de documentos, a operação pode causar um estreitamento nos caracteres, provocando o afastamento de caracteres conectados pelo processo de digitalização como apresentado na Figura 7 anterior.

Um exemplo do resultado de tal operação pode ser visto nas imagens da Figura 8 a seguir.

a)

b)

Figura 8. Exemplo de aplicação da operação morfológica de erosão. a) Imagem original e b) imagem erodida.

24

Devidamente tratados os problemas de rotação e ruídos, o próximo passo é a realização de

uma segmentação na imagem. A segmentação [18][64] visa a identificar regiões dentro de uma imagem. Pode ser aplicada de formas diferentes em um documento: a segmentação pode gerar a classificação entre pixels representando tinta e papel, separando-os; ou pode ser usada para classificar em uma imagem os elementos gráficos e de texto. Analisaremos esses dois aspectos a seguir. O primeiro deles é visto em destaque no Capítulo 2 desta tese.

A imagem de um documento pode conter mais do que apenas caracteres; pode ter fotos ou gravuras as quais não deverão ser tratadas pelo algoritmo para reconhecimento de caracteres. Assim, uma segmentação da imagem é necessária antes do processo de reconhecimento óptico de caracteres. De fato, nesse sentido, o processo de segmentação ocorre em duas fases: primeiro há uma segmentação do documento, determinando as áreas que possuem caracteres a serem reconhecidos e as áreas que não os possuem, como pode-se ver na Figura 9. Em seguida, é feita uma segmentação de texto, buscando a definição dos caracteres. Como dito, o objetivo da segmentação é identificar imagens, textos, etc., localizando conjuntos de elementos com características similares: uma página de documento pode ter caracteres escritos com diferentes famílias de fontes em diferentes estilos. Cada área classificada como texto é analisada quanto ao tamanho de fonte antes de proceder com a segmentação de texto, onde serão delimitados os caracteres de uma área, como explicado a seguir.

a) b)

Figura 9. Simulação de uma segmentação de documento. a) Análise feita na estrutura física do documento com a identificação de diferentes regiões

e b) resultado, gerando uma estrutura lógica com as classificações como texto ou figura. A segmentação de documentos, buscando a identificação das regiões de texto e de figuras,

começa com uma análise da diagramação do mesmo. Cada região da imagem é delimitada por um bloco e será classificada como texto, imagem ou não importa (contendo elementos que não conseguiram ser classificados de nenhuma das duas formas; é possível, no entanto, que essa terceira classe não exista e tudo que não seja classificado como texto seja considerado imagem). Após isso, as regiões classificadas como texto passarão por um processo de segmentação de texto que, de fato, é o mesmo processo de segmentação do documento, mas definido em uma região menor e resultando em caracteres. As linhas de texto são definidas e, dentro dessas linhas, cada caractere é encontrado e classificado.

25

Áreas de cabeçalho e rodapé também podem ser identificadas, dependendo do tamanho da fonte utilizada e da resolução de digitalização.

Variações quanto ao uso de segmentação podem ser encontradas na literatura, onde é tratado o problema de localização de informações em tipos específicos de documentos, tais como endereços em postais, em [62], e dados em um formulário, em [10][76].

A segmentação de documentos pode ser feita de diversas formas como exposto em [55], onde um analisador sintático é utilizado como ferramenta de auxílio a um OCR. Na referência [58], um sistema de descrição de diagramação (layout) de página é definido, localizando linhas e blocos de texto. Fletcher e Kasturi [13] tratam da segmentação de texto, onde é proposto um método para localização de caracteres sem se preocupar com a sua identificação. O algoritmo usa a transformada de Hough para localizar linhas conectadas. A segmentação de documentos é foco principal da referência [65], onde é feita uma classificação das áreas de um documento em texto e gráficos usando cálculo de densidade média de pontos em uma região. Mais detalhes sobre a transformada de Hough podem ser visto no Apêndice B desta dissertação.

A transformada de Hough é novamente utilizada em [21] para determinar o tamanho do espaço entre as linhas de um documento. O algoritmo de Run-Length [18] é utilizado para diminuir a complexidade de cálculos da transformada. O Run-Length é usado para diminuir a quantidade de pixels pretos da imagem binária original, criando uma nova imagem em tons de cinza. Essa nova imagem é gerada, substituindo colunas de pixels pretos adjacentes pela quantidade de tais pixels. Esse valor corresponderá a um tom de cinza na nova imagem. Sobre essa nova imagem é que deverá ser aplicada a transformada de Hough.

Algoritmos para detecção de bordas ou aproximação de curvas digitalizadas por polígonos podem ser encontrados em [42], [59], [84] e [90]. A referência [66] mostra uma visão geral sobre o assunto, analisando algoritmos que examinam a borda apenas ou toda a área interna do objeto.

Definidas as áreas de texto e, dentro delas, os caracteres, uma normalização é feita em cada caractere a fim de proceder com seu reconhecimento. Algoritmos de reconhecimento mais modernos identificam diversas características de fontes como tipo (arial, times new roman, courier, etc.), estilo (negrito, itálico, sublinhado) e tamanho. Determinadas as características da fonte, procede-se com seu reconhecimento utilizando-se técnicas de classificação como veremos em maiores detalhes posteriormente.

Outra aplicação do processo de segmentação de grande importância em nosso trabalho é a classificação das cores que correspondem à tinta da escrita, das cores do papel, podendo gerar duas imagens distintas, como pode-se ver um exemplo na Figura 10. A imagem original é apresentada na Figura 10a; a Figura 10b mostra a imagem da tinta em fundo branco. A Figura 10c, salienta a textura do papel, ficando a parte escrita vazada. Tal forma de segmentação é tratada em destaque em [32] para segmentação de imagens de textos datilografados e cheques. A referência [78] faz uma abordagem sobre segmentação baseada em momentos, onde, um sistema de recorte de cor é definido tal que o valor de corte varia dependendo da imagem de forma a manter inalterados os momentos da imagem de entrada e da imagem de saída. Um algoritmo semelhante, utilizando momentos, analisado posteriormente, foi testado nessa tese sem obter resultados satisfatórios. Detalhes dos algoritmos desenvolvidos no âmbito desta dissertação relativos a este tipo de segmentação serão tratados no Capítulo 2.

Aplicações do processo de segmentação também são encontradas no processamento de imagens de cheques bancários. No processamento desse tipo de imagem, diferentes algoritmos de segmentação podem ser encontrados em três etapas: 1) separação do fundo do cheque (padrão para cada banco) da parte referente à tinta, 2) identificação das áreas escritas em classes (nome do correntista, valor do cheque, data, etc.) e 3) segmentação do texto para reconhecimento dos caracteres. Quanto à eliminação do padrão do papel do banco (fundo do cheque), Yoshimura-Yoshimura [91] sugerem a subtração da imagem do cheque e de uma imagem do padrão do banco. Tal prática é bastante simples de ser implementada e pode obter resultados satisfatórios já que os padrões, geralmente, são poucos em um mesmo banco. Assim, é necessário saber a que instituição o padrão do cheque pertence e, possivelmente, qual o tipo de cheque (já que uma

26

mesma instituição pode ter padrões diferentes para tipos de contas diferentes). Diversos outros métodos trabalham com a extração de informações textuais do cheque como pode ser visto em [35], onde são usadas informações a priori sobre a formatação do cheque a fim de classificar as áreas de texto ou em [82], onde o uso de uma análise de cores é aplicado à extração da assinatura nos cheques.

a) b)

c)

Figura 10. Exemplo de Segmentação de uma imagem. a) Imagem original e imagem segmentada com a parte referente b) à tinta e c) ao papel.

Em termos de OCR, enfocaremos, ao longo desta tese, principalmente a sua aplicação em

documentos datilografados. Referências sobre aplicação de técnicas de OCR em textos manuscritos podem ser encontradas em [8] e [56]. Na primeira referência, uma série de técnicas

27

são apresentadas e testadas para o reconhecimento de texto manuscrito baseadas na procura por mínimos locais em áreas da palavra a ser reconhecida. O sistema foi apresentado apenas com a inserção de imagens de palavras já isoladas como entrada sem considerar sua segmentação na imagem completa do texto. Em [56], é feita uma análise de sistemas para reconhecimento de textos manuscritos e testes são feitos em um sistema comercial voltado a este propósito. Um survey completo sobre o assunto pode ser visto na referência [77]. Maiores avanços sobre as técnicas de reconhecimento de caracteres manuscritos podem também ser encontradas em [16] (onde são analisadas e classificadas características da imagem de caracteres manuscritos a fim de facilitar seu reconhecimento), [22] (apresentando uma estratégia para isolamento de caracteres manuscritos) e [63] (uma análise de texto manuscrito em cheques franceses).

Outra aplicação para reconhecimento de caracteres em documentos datilografados é no desenvolvimento de bancos de dados. Um exemplo de tal utilização de OCR’s pode ser visto em [67] onde há uma descrição completa de uma plataforma para banco de documentos.

1.2 Algoritmos para Reconhecimento Óptico de Caracteres

Muitas são as formas de proceder ao reconhecimento de caracteres de uma imagem. De fato, independente da técnica usada, quando falamos em reconhecimento de caracteres, estamos falando em técnicas de classificação de padrões. Um padrão é definido como um conjunto de elementos ordenados, de forma que, se algum elemento é alterado, obtém-se um novo padrão. No caso de reconhecimento óptico de caracteres, considera-se como padrão uma pequena porção de toda a imagem. Para imagens de documentos, a imagem é separada em suas linhas de texto e, por sua vez, as linhas têm seus caracteres separados. Cada caractere é observado dentro de uma janela a fim de determinar sua classe. Enquanto essa observação é feita, todo o resto da imagem é esquecido. Da observação dos dados na janela, toma-se a decisão da classificação do padrão, geralmente, através do uso de técnicas estatísticas ou redes neurais. Uma classe de reconhecimento é um conjunto de padrões que deve gerar uma mesma saída em um sistema de classificação. Variações não significativas em alguns pixels que formam uma letra não devem permitir que a letra seja classificada como outro símbolo qualquer.

Alguns algoritmos são bastante antigos e têm uma idéia básica muito simples, como é o caso do casamento de padrões (pattern matching). Nesses algoritmos, uma base de imagens é gerada com os caracteres de uma dada fonte de letras. Esta base é usada na realização de comparações com elementos colhidos da imagem textual. Cada elemento é comparado com a base e classificado de acordo com o melhor casamento possível. Com o objetivo de conseguir resultados satisfatórios, os programas baseados neste algoritmo devem ser treinados com diversos tipos diferentes de bases vindas de diferentes tipos de fontes. Dessa forma, aumentam as probabilidades de um dado de entrada gerar uma saída correta. O uso de um maior número de bases embora, por um lado, possa aumentar a eficiência do algoritmo, provoca também um aumento em sua complexidade (tendo que executar mais comparações por entrada) e aumenta ainda o espaço necessário para armazenar a base. Observa-se que uma tolerância deve ser permitida em relação à entrada. Essa tolerância visa a identificação do caractere mesmo que não aconteça um casamento perfeito. Um artifício usado para melhorar a qualidade da resposta é a utilização de um dicionário de palavras características da língua da qual se faz o reconhecimento. Assim, é possível sugerir a transcrição correta de certas palavras comparando-as com os termos armazenados no dicionário. O uso de dicionários não se restringe a nenhum algoritmo específico. De fato, essa técnica é utilizada pela grande maioria dos programas que realizam reconhecimento de caracteres, não importando o algoritmo utilizado para o processo.

28

Outra técnica busca propriedades características das letras e faz o casamento através da estrutura do caractere. Um classificador estrutural depende da seleção de tais características e na precisão de suas medições. Mais de um tipo de característica pode ser medida em uma imagem e alocada em um vetor. Uma classificação eficiente depende da escolha adequada das características da imagem e de uma medição acurada. Tais características podem ser circularidade (razão do quadrado do perímetro pela área para um círculo circunscrevendo a letra), retangularidade (razão entre a área da região ocupada pela letra pela área da caixa limitante que a circunda), análise de buracos (regiões fechadas com a cor do papel, circundadas por pixels com cor da tinta) momentos de qualquer ordem, etc [62]. Todas essas características podem ser extraídas de uma imagem, armazenadas em um vetor e classificadas em um espaço de vetores característicos utilizando, por exemplo, distância Euclidiana. Com o advento das redes neurais [2][20], um grande leque em estudos foi aberto e o reconhecimento de caracteres ganhou mais uma ferramenta em busca da transposição perfeita de imagem para texto. Como os outros algoritmos já usados, as redes neurais não produzem respostas absolutamente corretas, mas, até então, têm alcançado os melhores resultados. Faremos, a seguir, uma análise de um experimento feito usando redes neurais no reconhecimento de caracteres de documentos históricos. Tal experimento servirá como base para etapas futuras do Projeto, onde múltiplas ferramentas de OCR poderão trabalhar em conjunto em uma mesma imagem a fim de gerar uma melhor taxa de acerto. Nesse sistema, um OCR primitivo com parâmetros definidos para os documentos do Projeto Nabuco, como o que será mostrado a seguir, será utilizado para ajudar na escolha da resposta correta entre os múltiplos OCR’s, quando necessário.

1.2.1 Redes Neurais O estudo sobre computação neural começou em 1943 com a publicação do trabalho de Warren McCulloch e Walter Pitts. O primeiro, neurofisiologista, e o segundo, lógico, foram os pioneiros na definição do Neurônio. Ainda hoje, grande parte dos estudos em redes neurais usa o modelo desenvolvido por eles. Não menos importante foi a contribuição de Donald Hebb, em 1949, o qual afirmou que os neurônios poderiam produzir diferentes respostas a diferentes padrões de acordo com a experiência de cada um. Por definição [2], computação neural é o estudo de redes com nós adaptativos os quais, através de um processo de aprendizado, armazenam conhecimento e são capazes de usar esse conhecimento. As principais características das redes neurais estão exatamente em sua capacidade de aprendizado e na possibilidade de generalização. O termo e a analogia com os neurônios humanos vêm exatamente de nossa capacidade de aprender com a experiência. Um ser humano pode registrar as imagens de uma cadeira e uma poltrona e identificar que as duas servem para os mesmos fins. Para um computador, no entanto, essa não é uma tarefa fácil, envolvendo um sem-número de variáveis. Diversos problemas relativos a computação neural ainda não estão resolvidos, mas muito já foi estabelecido em muitas áreas diferentes, mostrando a grande potencialidade do assunto. Desde o trabalho de McCulloch-Pitts, muitos tipos de redes neurais surgiram. Diversas são as arquiteturas possíveis e os algoritmos para aprendizado. Não nos deteremos aqui na explicação desses métodos e algoritmos, mas, sim, na utilização desses algoritmos em um problema prático: o reconhecimento óptico de caracteres. Para maiores informações sobre o assunto, sugerimos a referência [20].

Com seu potencial de aprendizagem, as redes neurais surgiram como uma opção lógica dentro do problema do reconhecimento de caracteres. Atualmente, como já mencionado anteriormente, os softwares que apresentam os melhores resultados no reconhecimento de padrões em imagens textuais são os que se utilizam de redes neurais em sua implementação.

O reconhecimento óptico de caracteres realiza a tradução de uma imagem textual para o formato de texto simples. Através do uso de redes neurais, é possível identificar a imagem de

29

entrada, definindo o caractere que ela representa. Para tanto, a rede deve ser treinada com diversas amostras de caracteres com a finalidade de dar-lhe precedentes para definir a que caractere uma imagem está associada. Trata-se, portanto, de um problema de classificação. Dentro da etapa de treinamento e de uso da rede, propriamente dita, sua entrada será composta por imagens de possíveis caracteres. Nesse caso, diversas imagens de cada caractere são extraídas de diversas imagens da base e utilizadas no aprendizado da rede. No uso, no entanto, podem surgir caracteres desconhecidos à rede: caracteres não usados no treinamento ou símbolos formados pela junção de dois ou mais caracteres na imagem os quais não foram devidamente isolados no pré-processamento, como mostrado anteriormente. Nesse caso, a rede não terá como transpor a imagem para texto, mas poderá usar artifícios para tentar fazer a correta tradução desses caracteres, como através do uso de dicionários. Não abordaremos aqui esse problema, já que, no nosso caso, o uso de documentos históricos requer a criação de um dicionário específico. Tal problema será tratado em trabalhos futuros. Um pré-processamento na imagem é necessário para que a probabilidade de um perfeito reconhecimento do caractere seja maior. Neste estudo da atuação de redes neurais no reconhecimento de caracteres, não analisaremos os processos que ajustam as imagens de entrada por fugirem aos nossos objetivos. Consideraremos que a entrada da rede já estará pré-processada quanto a diversos fatores, como possibilidade de rotação, por exemplo.

Visando diretamente ao Projeto Nabuco, as letras do alfabeto português foram extraídas diretamente de imagens de cartas datilografadas pertencentes ao acervo de Joaquim Nabuco. Trabalhamos com cartas e documentos datilografados, fazendo uma transposição desses documentos para o formato de texto a fim de torná-los mais acessíveis a pesquisadores. Em tais documentos, será possível disponibilizar uma série de recursos como a busca por palavras-chaves, extremamente difícil quando tratamos com imagens. As imagens coloridas são transpostas para imagens com 256 tons de cinza, calculando a luminância de cada pixel pelo algoritmo padrão [17] definido pela CIE (Comission Internationale l’Eclairage - Comissão Internacional de Iluminação) :

bgbC .11,0.59,0.3,0 ++=

onde C é o tom de cinza resultante e r, g e b (tanto C, quanto r, g e b estão definidos entre 0 e 255) são os respectivos tons de vermelho, verde e azul. Computacionalmente, o valor de C deve ser truncado para ser apresentado como um valor inteiro.

Diferente da maioria dos softwares comerciais para reconhecimento, os testes feitos são aplicados a imagens em tons de cinza. Normalmente, a imagem é binarizada a fim de proceder ao reconhecimento. Com isso, forneceremos mais informações à rede para que esta possa identificar os caracteres com maior precisão. Para extração de caracteres, algumas imagens base foram escolhidas dentro do acervo, de acordo com os objetivos do projeto. O número de caracteres extraídos varia dependendo da freqüência da letra na língua portuguesa da época como será explanado a seguir.

Os caracteres foram extraídos com dimensões de 16x27 pixels, totalizando 432 pixels por caractere. Buscando reduzir a quantidade de informações de entrada a fim de diminuir a complexidade da arquitetura da rede, um processamento foi executado nas amostras tal que suas dimensões foram reduzidas para a metade por um algoritmo de redimensionamento, ou seja, 8x13 pixels (104 pixels no total). Essa redução provoca uma perda nos dados de entrada e será utilizada apenas para análise da potencialidade das redes neurais, não devendo estar presente em futuras utilizações deste projeto a fim de gerar respostas mais precisas. Os caracteres estão representados em imagens com 256 tons de cinza. A Figura 11 mostra exemplos ampliados de alguns caracteres. Ressaltamos que as amostras são retiradas de documentos históricos e, na figura, não foi segmentada a parte referente ao papel.

30

Figura 11. Exemplos de letras usadas como amostras de documentos históricos.

A fim de analisar a potencialidade das redes neurais no reconhecimento de caracteres,

limitaremos nosso espaço amostral apenas às letras minúsculas do alfabeto. Dentre os diversos algoritmos existentes, utilizando os conceitos de redes neurais,

optamos aqui pelo uso de um Multilayer Perceptron (MLP) [20]. O algoritmo de aprendizado usado é o Back-Propagation [20].

Um MLP caracteriza-se por possuir uma camada de entrada com um conjunto de unidades sensoras, uma ou mais camadas escondidas e uma camada de saída. O sinal de entrada se propaga pela rede camada-a-camada. O algoritmo de Back-Propagation consiste de dois passos através das diferentes camadas da rede: um da camada de entrada para de saída e outro de volta no caminho inverso. No primeiro passo, um padrão de ativação é aplicado a entrada e os seus efeitos se propagam pela rede. Um conjunto de saídas é produzido segundo a atual configuração da rede. Logo após, os dados se propagam de volta às entradas, corrigindo os pesos adotados de acordo com alguma regra de correção de erros. O processo repete-se até que a resposta encontrada seja tão próxima da esperada quanto seja desejado.

A arquitetura utilizada, com neurônios completamente conectados, será disposta da seguinte forma:

1. 104 neurônios de entrada (um para cada pixel da imagem das letras); 2. Uma camada escondida com 50 neurônios; 3. 26 neurônios na camada de saída (um para cada letra minúscula do alfabeto); 4. Taxa de aprendizagem: 0,01; 5. Momentum = 0,01.

Onde a Taxa de Aprendizagem da rede serve como medida de quanto os pesos adotados na rede podem variar entre cada iteração e o Momentum é usado como uma medida para aumentar esta taxa sem provocar instabilidade no sistema.

O número de 50 neurônios na camada escondida foi resultado de testes feitos na rede, variando essa configuração, partindo de experimentos com 20 até 70 neurônios de 10 em 10. A configuração proposta gerou resultados melhores em comparação a outras arquiteturas com menos neurônios ou, em alguns casos, resultados bastante similares a outras configurações com mais neurônios. Outras imagens do mesmo acervo de Joaquim Nabuco e com características similares às imagens base (ou seja, imagens em 256 tons de cinza e datilografadas) serão tomadas na fase de teste e validação da rede. Ressalta-se que, nesta fase, serão usados apenas conjuntos de imagens independentes do conjunto de treinamento, como especificado na teoria da computação neural [20].

As condições iniciais da rede são caracterizadas por pesos pseudo-aleatórios segundo uma distribuição uniforme com valores entre –1 e +1; os valores do limiar estão dispostos entre –0,1 e +0,1.

Para desenvolvimento dos testes, foi usado como base o código de um Multilayer Perceptron existente em [64]. Esse código, no entanto, possui erros tanto conceituais quanto de implementação os quais tiveram que ser corrigidos. A implementação do código traz ainda a vantagem de podermos incorporá-lo em ferramentas associadas ao Projeto Nabuco o que não seria possível com os softwares comerciais para redes neurais como o SNNS ou o NeuroSolutions. Para o desenvolvimento da ferramenta, foi usado o C++ Builder� 1.0 da Inprise (antiga Borland). O código desenvolvido pode ser encontrado no Apêndice C desta tese.

31

Experimentos Diversos experimentos foram feitos com a rede a fim de buscar a melhor configuração possível. Apresentaremos aqui alguns destes experimentos, variando apenas o número de letras testadas e o erro médio quadrático máximo permitido (critério de parada das iterações). Em algumas aplicações, é preciso comparar uma imagem com outra sem uso de qualquer característica do processamento visual humano. A comparação é feita pixel-a-pixel entre os padrões de luminância da imagem original e da imagem em análise. Uma medida largamente utilizada é o Erro Médio Quadrático (EMQ). Para uma imagem original I e uma imagem em análise I’, ambas com dimensões NxM, o EMQ entre as imagens é calculado como:

��= =

−=N

i

M

j

jiIjiINM

IIEMQ1 1

2)],(),('[)1

()',(

onde I(i,j) e I´(i,j) representam a luminância da imagem original e da imagem em análise, respectivamente. O EMQ é uma medida para diferenças entre as imagens apenas e não pode ser usado para predizer qual das duas imagens é a melhor.

Foram feitos testes com erro máximo de 10% e de 3%. Primeiro Experimento

Como primeira etapa, quatro letras foram usadas para treino e teste da rede: a, b, c e d. Doze amostras de cada letra foram extraídas das imagens base e 27 foram usadas na fase de teste. Embora o número de caracteres possa ser considerado pequeno, lembramos que não há grandes variações entre eles já que, na maioria dos casos, trata-se da mesma máquina de datilografar que os gera. Além disso, nosso objetivo, no momento, é o de analisar a potencialidade de um sistema de reconhecimento baseado em Redes Neurais. O uso do sistema aqui descrito para trabalhos futuros irá requerer um número maior de amostras para compor a base de treinamento. Com 10% de erro máximo, foram necessárias 39 iterações para a rede convergir. Nesse caso, 27 caracteres foram usados como teste e houve falha no reconhecimento em 11,11% dos casos. Para 3% de erro, 80 iterações foram usadas na rede e houve uma taxa de falha igual a anterior, ou seja, 11,11%.

Segundo Experimento

Numa segunda fase, mais duas letras foram inseridas na base. Agora, trabalhamos com as letras a, b, c, d, e e f. Com 10% de erro, 39 iterações levaram a uma taxa de 44,74% de erro nos caracteres testados. Para 3% de erro, foram necessárias 45 iterações e, dos caracteres testados, apenas 18,42% foram reconhecidos de forma errada pela rede.

Terceiro Experimento

Mais três letras foram acrescentadas a base de letras: g, h e i. O critério de parada de 10% fez com que a rede realizasse 49 iterações e cometeu erros em 18,36% das imagens testadas. Para 3% de erro, 77 iterações foram realizadas pela rede e uma taxa 12,24% de erro foi encontrada nas imagens de teste.

Quarto Experimento

As letras do alfabeto de a a q foram usadas neste experimento, totalizando 17 letras. Para 10% de erro foram feitas 55 iterações e houve um mal reconhecimento em 32% dos casos. Para 3%, essa taxa caiu para 24,52% com 75 iterações.

Quinto Experimento

Nesse último experimento, vinte e duas letras do alfabeto foram utilizadas. Foram deixadas de fora apenas as letras k, w, x e y por não serem comuns na língua portuguesa e por não

32

estarem presentes em quase nenhuma carta das digitalizadas do acervo, dificultando a coleta de amostras nos documentos. Nesse experimento, consideramos apenas uma taxa de erro de 3%. No caso, 283 iterações foram necessárias para que a rede convergisse. Com os pesos encontrados pela rede, 167 imagens foram testadas e 87,43 % foram reconhecidas corretamente. Curiosamente, observamos que, de todas as letras testadas, apenas a letra s não foi reconhecida em nenhuma das amostras de teste. Mesmo assim, a rede obteve resultados expressivos. Esses resultados, no entanto, ainda podem ser melhorados através da apresentação de mais caracteres para treinamento da rede e da mudança da configuração da rede, testando o uso de mais camadas escondidas. Os valores da Função de Erro Médio Quadrático podem ser vistos na Tabela 1 e na Figura 12. Nessa tabela, cada coluna apresenta, no lado direito, a iteração e, no lado esquerdo, o valor do Erro Médio Quadrático.

Outros experimentos, não relatados aqui, puderam ser feitos até chegarmos à configuração

final da rede apresentada no quinto experimento acima descrito. Nesse sentido, pudemos testar o comportamento da rede nas seguintes situações: aplicação de uma função linear na camada escondida e na camada de saída; ausência do fator de limiar; ausência de momentum na rede, etc. Estes testes provocaram respostas diversas, desde a não convergência da rede até uma convergência falsa rápida em até uma única iteração.

Tabela 1. Iteração e respectivo Erro Médio Quadrático para Rede Neural usada no

reconhecimento de caracteres. 1 0.560522 2 0.543305 3 0.538135 4 0.534696 5 0.531425 6 0.528061 7 0.524610 8 0.521128 9 0.517697 10 0.514370 11 0.511146 12 0.508011 13 0.504974 14 0.502058 15 0.499282 16 0.496642 17 0.494117 18 0.491678 19 0.489300 20 0.486968 21 0.484675 22 0.482417 23 0.480193 24 0.478001 25 0.475836 26 0.473699 27 0.471589 28 0.469510 29 0.467466 30 0.465462 31 0.463501 32 0.461587 33 0.459723 34 0.457909 35 0.456145 36 0.454430 37 0.452760 38 0.451130 39 0.449533 40 0.447960

41 0.446400 42 0.444844 43 0.443284 44 0.441717 45 0.440147 46 0.438581 47 0.437032 48 0.435513 49 0.434033 50 0.432599 51 0.431212 52 0.429872 53 0.428575 54 0.427318 55 0.426095 56 0.424901 57 0.423731 58 0.422579 59 0.421442 60 0.420314 61 0.419192 62 0.418072 63 0.416950 64 0.415824 65 0.414691 66 0.413550 67 0.412398 68 0.411234 69 0.410057 70 0.408867 71 0.407662 72 0.406444 73 0.405211 74 0.403963 75 0.402700 76 0.401422 77 0.400126 78 0.398813 79 0.397479 80 0.396122

81 0.394740 82 0.393329 83 0.391886 84 0.390408 85 0.388892 86 0.387333 87 0.385730 88 0.384080 89 0.382381 90 0.380630 91 0.378828 92 0.376973 93 0.375063 94 0.373101 95 0.371084 96 0.369015 97 0.366894 98 0.364720 99 0.362496 100 0.360222 101 0.357901 102 0.355533 103 0.353119 104 0.350663 105 0.348165 106 0.345628 107 0.343052 108 0.340441 109 0.337795 110 0.335116 111 0.332406 112 0.329666 113 0.326896 114 0.324099 115 0.321275 116 0.318424 117 0.315548 118 0.312646 119 0.309719 120 0.306767

121 0.303792 122 0.300793 123 0.297771 124 0.294727 125 0.291661 126 0.288576 127 0.285471 128 0.282348 129 0.279209 130 0.276054 131 0.272886 132 0.269706 133 0.266516 134 0.263317 135 0.260112 136 0.256902 137 0.253689 138 0.250476 139 0.247265 140 0.244056 141 0.240852 142 0.237655 143 0.234467 144 0.231290 145 0.228126 146 0.224976 147 0.221842 148 0.218725 149 0.215628 150 0.212552 151 0.209499 152 0.206469 153 0.203465 154 0.200487 155 0.197537 156 0.194616 157 0.191725 158 0.188864 159 0.186036 160 0.183241

161 0.180478 162 0.177750 163 0.175056 164 0.172397 165 0.169774 166 0.167186 167 0.164634 168 0.162118 169 0.159639 170 0.157195 171 0.154787 172 0.152416 173 0.150080 174 0.147779 175 0.145512 176 0.143281 177 0.141084 178 0.138920 179 0.136791 180 0.134694 181 0.132629 182 0.130596 183 0.128595 184 0.126624 185 0.124683 186 0.122773 187 0.120892 188 0.119039 189 0.117215 190 0.115419 191 0.113650 192 0.111909 193 0.110193 194 0.108505 195 0.106841 196 0.105203 197 0.103590 198 0.102002 199 0.100438 200 0.098898

201 0.097383 202 0.095890 203 0.094420 204 0.092974 205 0.091550 206 0.090148 207 0.088768 208 0.087410 209 0.086073 210 0.084758 211 0.083463 212 0.082189 213 0.080936 214 0.079702 215 0.078489 216 0.077295 217 0.076121 218 0.074966 219 0.073829 220 0.072712 221 0.071613 222 0.070532 223 0.069468 224 0.068423 225 0.067394 226 0.066383 227 0.065389 228 0.064412 229 0.063451 230 0.062506 231 0.061577 232 0.060663 233 0.059765 234 0.058883 235 0.058015 236 0.057162 237 0.056323 238 0.055499 239 0.054689 240 0.053892

241 0.053109 242 0.052340 243 0.051583 244 0.050840 245 0.050109 246 0.049390 247 0.048684 248 0.047990 249 0.047308 250 0.046637 251 0.045977 252 0.045329 253 0.044692 254 0.044066 255 0.043450 256 0.042845 257 0.042250 258 0.041665 259 0.041090 260 0.040525 261 0.039969 262 0.039423 263 0.038886 264 0.038357 265 0.037838 266 0.037327 267 0.036825 268 0.036331 269 0.035846 270 0.035368 271 0.034898 272 0.034436 273 0.033982 274 0.033536 275 0.033096 276 0.032664 277 0.032239 278 0.031821 279 0.031410 280 0.031005

281 0.030607 282 0.030215 283 0.029830

Acima de tudo, destacamos os bons resultados obtidos no teste com 22 letras do alfabeto,

onde cerca de 88% das 167 amostras testadas foram reconhecidas com sucesso.

33

Em sua configuração final, resultados satisfatórios foram conseguidos nos cinco experimentos, destacando-se as respostas conseguidas com um critério de parada de 3% no erro médio quadrático. Para aumento da eficiência da rede, um número maior de amostras de cada letra deverá ser extraída das imagens base e novas configurações na rede deverão ser experimentadas. A rede, no entanto, encontrou respostas satisfatórias nas imagens teste na maioria dos casos.

Figura 12. Gráfico do Erro Médio Quadrático da rede até sua convergência.

1.3 Um Estudo Comparativo entre Ferramentas Comerciais de OCR

Como um dos objetivos finais desta tese envolve a geração automática de documentos a partir de um arquivo texto gerado de uma imagem digitalizada do documento, deve-se determinar qual a melhor forma de obter tais arquivos de texto. Para tanto, podemos desenvolver uma ferramenta de OCR própria para o Projeto ou então utilizar alguma ferramenta comercial.

Na Seção anterior, apresentaram-se os resultados iniciais de uma ferramenta primitiva desenvolvida que, embora bastante satisfatórios, foram obtidos em situações ideais. No Capítulo 2, a seguir, descrevem-se todas as etapas que um sistema para processamento de documentos deve executar até a geração final de um arquivo em texto. Essas etapas são essenciais para uma taxa de acerto maior possível e devem estar presentes em qualquer sistema criado para tais fins. A implementação de todas essas etapas anteriores ao reconhecimento da imagem e, em seguida, o desenvolvimento e treinamento de um algoritmo para a classificação dos caracteres, em si, seria uma prática extremamente onerosa. Além disso, correr-se-ia o risco de obter sistemas com taxas de acerto inferiores ou iguais aos sistemas existentes. Por esses motivos, ferramentas comerciais foram testadas a fim de verificar suas taxas de acerto e os pontos falhos que poderiam ser explorados e melhorados. O trabalho foi concentrado então na fase de pré-processamento das imagens, gerando imagens de melhor qualidade para a entrada do OCR.

Apresentam-se, aqui, os estudos desenvolvidos para determinar a melhor ferramenta de OCR a ser utilizada no Projeto, observando sua resposta a situações adversas.

Existem diversas ferramentas comerciais disponíveis para reconhecimento óptico de caracteres. Vamos analisar aqui o comportamento de seis das mais amplamente difundidas ferramentas comerciais de OCR e, através dele, tentar discorrer sobre os erros de reconhecimento. As ferramentas são :

• Omnipage 8.0 (Caere Corporation) [93] • Corel OCR Trace (Corel Corporation) [95]

34

• SmartPage (Recognita Corporation) [99] • Wordlinx (OCRON Inc.) [98] • TextBridge Pro 98 (Scansoft Inc.) [100] • TypeReader Professional 4.0 (Expervision) [96]

Todas essas ferramentas apresentavam versões demonstrativas para cópia em 1998, época em que foram feitos os testes aqui relatados.

Este estudo foi aceito para apresentação e publicação nos Anais de Vision Interface 99, em Quebéc, Canadá, no artigo A Comparative Study on OCR Tools, Carlos A.B. Mello e Rafael D. Lins, maio/1999 [50].

A tabela 2, a seguir, resume algumas importantes características desses softwares. Foram analisados os tipos de imagens (quanto a quantidade de cores) com as quais os softwares trabalham; capacidade de correção de problemas de rotação nas imagens; presença de dicionários e permissão de alterações nesses; qual a resolução máxima permitida (fixando, no caso, um máximo de 250 dpi, por validar as características do Projeto Nabuco); tipos de arquivos de entrada; quais as técnicas de reconhecimento implementadas; consegue-se reconhecer diferentes fontes de caracteres (quanto a tipo, tamanho, estilo); e, por último, se o sistema consegue reconhecer páginas com diferentes diagramações.

Tabela 2. Principais características de algumas ferramentas de OCR

Omnipage

Corel Smartpage Wordlinx TextBridge TypeReader

Tipos de Imagens (cores)

Tons de Cinza

Tons de cinza

Preto-e- Branco

Preto-e- Branco

Preto-e- Branco

Preto-e- Branco

Imagens Rotacionadas

Sim Sim Não Não Sim Não

Dicionário

Sim Sim Não Sim Sim Sim

Mudanças no Dicionário

Sim Não Não Sim Sim Sim

Resoluções

250 dpi 250 dpi 150 dpi 250 dpi 250 dpi 250 dpi

Arquivos de Entrada

Vários Vários Apenas TIFF Vários Vários Apenas TIFF

Técnica de OCR

Redes Neurais

Sem Informações

Sem Informações

Sem Informações

Redes Neurais

Sem Informações

Diferentes Fontes

Não

Sim Não Não Não Sim

Diferentes Diagramações

Sim Sim Não Não Sim Sim

Entre os softwares testados apenas o Omnipage e o Corel OCR Trace trabalham com

imagens em tons de cinza. Ambos, no entanto, convertem a imagem para monocromática antes de executarem o reconhecimento. Essa conversão é feita através de um filtro de corte [18] centrado em 127, sendo que o Omnipage aplica, primeiro, um aumento no brilho da imagem de cerca de 15 unidades.

Por aumento do brilho em 15 unidades, entenda-se um deslocamento de cada ponto dos histogramas2 dos tons RGB para a direita (direção do branco 255) de 15 pontos. Assim, uma cor

2 O Histograma de uma imagem digital com tons entre 0 e L-1 é uma função discreta inif =)( , onde i é o

i-ésimo tom e in é o número de pixels na imagem que possuem o tom i, onde i=0, 1, 2, ..., L-1. No caso, L = 256.

35

125 no histograma de qualquer tom, passará a posição 140 após o aumento no brilho, conforme a Figura 13 a seguir.

Figura 13. Deslocamento do Histograma do tom azul com o aumento do brilho de uma imagem.

Observamos que não há mudança na forma do histograma, apenas há um

deslocamento para a direita, considerando que houve um aumento no brilho. Algumas vezes, a variação no valor do brilho pode ser definida em porcentagem. Nesse caso, o valor do tom deve ser multiplicado pelo valor da porcentagem, tendo sua variação definida por esse produto.

Para os experimentos seguintes, foram usados cinco textos em inglês e português de assuntos diversos, extraídos da Internet, com fundo branco, fonte de cor preta com tamanhos e tipos variados, impressos em impressora Hewlett-Packard Laserjet 5L com 300 dpi de resolução em papel branco Chamex [94] A4 com 210x297mm de dimensões e 75g/m² de gramatura. Os documentos têm, em média, 3.714 caracteres em cerca de 624 palavras.

A variação no Brilho utilizada pelos digitalizadores é feita através de software. Ou seja, os documentos são digitalizados com um valor de brilho fixo (proveniente do aparelho de digitalização) e, em seguida, o programa que realizou a digitalização oferece a opção de alterar os valores de brilho e contraste. Com a mudança desses valores, no entanto, as imagens não são novamente digitalizadas. A aplicação dos novos parâmetros é feita na imagem previamente digitalizada, indicando que o processo é feito via software. No scanner utilizado, o aumento (ou diminuição) do valor de brilho corresponde a um deslocamento linear de X unidades no histograma da imagem. O ponto de 100 para brilho e contraste na digitalização é considerado como o valor inicial da digitalização (ou seja, se ajustarmos a escala de brilho e contraste para o ponto 100, não há deslocamento no histograma).

Os textos foram digitalizados com um scanner Scanjet 4C da Hewlett-Packard, possuindo resolução máxima de 720 dpi. Os valores de brilho e contraste na digitalização foram ajustados para 123 e 133, respectivamente. Tais valores de brilho e contraste são definidos dentro do software de digitalização do scanner. Os valores de 123 para brilho e 133 para contraste foram definidos por serem os valores utilizados na digitalização do acervo de Joaquim Nabuco. Para digitalização, foi usado o software HP Deskscan II. Com esses ajustes, para uma imagem em tons de cinza, a tonalidade média de fundo (a cor do papel) para as imagens foi de 235 e a tonalidade média de frente (cor da tinta) encontrada foi 5. Os documentos foram digitalizados da esquerda para a direita e de cima para baixo, conforme o procedimento padrão dos digitalizadores.

A comparação entre os arquivos gerados pelas ferramentas de OCR e os arquivos corretos (originais) foi realizada mediante algumas restrições. Devido à saída do OCR ser composta por muitos ruídos (caracteres provenientes de sujeiras na imagem), um pré-processamento foi feito em todos os arquivos a fim de facilitar um sistema de comparação automática entre os textos. Nesse pré-processamento, foi eliminada parte dos ruídos inseridos nos arquivos de texto em algumas situações; caracteres especiais foram inseridos, marcando linhas retiradas pela ferramenta de OCR; e, por último, o texto gerado foi formatado para adquirir uma formatação próxima a do documento original. Essas restrições foram utilizadas nos experimentos relatados na

36

próximas seções. No Apêndice A, apresentamos um exemplo de saída dos OCR's para um dos textos analisados.

1.3.1 Descrição dos Experimentos Os experimentos realizados, descritos a seguir, são necessários para tentarmos analisar os

principais pontos de falha dos softwares de OCR e possibilitar a escolha criteriosa de qual OCR atende aos requisitos do Projeto Nabuco. Procederemos, a seguir, com uma descrição de cada experimento. Sensibilidade à Digitalização O ajuste da resolução para digitalização de documentos influencia bastante a capacidade de reconhecimento das ferramentas de OCR. Um alto valor de resolução implica num aumento proporcional do espaço de armazenamento, mas não garante um aumento na taxa de reconhecimento do texto.

Os cinco documentos usados como teste foram digitalizados com diferentes resoluções em tons de cinza e em preto-e-branco para verificar a sensibilidade dos seis softwares. Seja a taxa de acerto o número percentual de símbolos corretamente transcritos de imagem para texto. A tabela 3 mostra essa taxa, em relação aos seis softwares.

Tabela 3. Taxa de acerto média para diferentes resoluções em imagens monocromáticas

dpi Omnipage Corel SmartPage Wordlinx Textbridge Typereader 75 5,32 % 0,000 % 0,000 % 10,26 % 9,07 % 0,000 %

100 42,70 % 87,1 % 62,22 % 58,31 % 89,5 % 89,98 % 150 98,99 % 96,94 % 88,23 % 68,52 % 99,21 % 99,09 % 200 99,53 % 99,32 % - 66,17 % 99,41 % 99,38 % 250 99,52 % 99,05 % - 70,53 % 99,47 % 99,59 %

O Smartpage não trabalha com imagens digitalizadas com resolução maior que 150 dpi. Nota-se também uma degradação na taxa de acerto com resoluções de 200 a 250 dpi no Corel OCR Trace e no Omnipage. Isso pode ser explicado devido ao aumento da presença de ruídos (advindos do próprio papel) quando se aumenta a resolução da imagem, aumentando também a quantidade de detalhes. Wordlinx apresentou a pior taxa de acerto entre todos os softwares testados. Mesmo com altas resoluções, seus melhores resultados foram abaixo do aceitável com taxas de erro acima de 30%.

Alguns softwares permitem o auxílio de dicionários para decisão das palavras reconhecidas. No entanto, optamos pela não utilização deste recurso por dois motivos. Primeiro, nem todos os softwares testados possuem dicionários acoplados, o que dificultaria a comparação. Em segundo lugar, procuramos analisar a informação vinda diretamente da ferramenta. Lembramos que nosso objetivo maior é a aplicação a imagens de cartas e documentos do começo do século. Os textos dessa época possuem uma ortografia distinta da atualmente em vigor, não conseguindo ser corrigida pelos programas de hoje.

Como visto na tabela 2, apenas o Omnipage e o Corel OCR Trace trabalham com imagens em tons de cinza. Sua precisão para este tipo de imagem com diferentes resoluções pode ser vista na tabela 4.

Tabela 4. Taxa de acerto média para diferentes resoluções de imagens em tons de cinza.

dpi Omnipage Corel OCR Trace 75 23,71 % 20,8 %

100 48,51 % 33,24 % 150 97,76 % 60,27 % 200 98,63 % 97,31 % 250 99,67 % 99,21 %

37

Ambos os softwares tiveram respostas similares para altas resoluções. No entanto, o

Omnipage convergiu para melhores resultados mais rápido que o Corel OCR Trace, como pôde ser visto na Tabela 4, e também apresentou melhores taxas para baixas resoluções. Sensibilidade à Rotação do Documento Como já mencionado, o processo de OCR é sensível à rotação do documento. A taxa de acerto das ferramentas de OCR varia com o grau de rotação da imagem. Enquanto alguns softwares tratam essa rotação com pequena perda de informação, outros não trabalham tão apropriadamente. Após a digitalização, o software de OCR deve verificar se a imagem foi rotacionada durante a digitalização. Para isso, um processo de detecção de bordas deve ser realizado a fim de determinar graus de rotação. Tal processo é necessário porque algumas técnicas usadas para reconhecimento de caracteres requerem que as entradas estejam corretamente alinhadas. O detector de bordas pode determinar o ângulo de rotação e, em seguida, usar essa informação para re-orientar a imagem e alinhá-la. Como já vimos, uma maneira de proceder com a detecção de rotação é através do uso da transformada de Hough (maiores detalhes no Apêndice B desta tese), procedendo com uma rotação no sentido inverso a fim de alinhar a imagem. Rotação é tratada apenas pelo Omnipage, Corel OCR Trace e TextBridge Pro. Apenas uma das imagens foi usada como teste, sendo rotacionada no sentido horário em diferentes graus. A taxa média de acerto desses softwares na imagens testada pode ser vista na tabela 5. Tabela 5. Taxa de acerto média para diferentes graus de rotação para uma imagem com 250dpi.

Rotação Omnipage Corel OCR Trace TextBridge 1 grau 98,63 % 99,25 % 99,25 % 2 graus 98,63 % 96,77 % 99,13 % 3 graus 98,51 % 33,24 % 99,01 % 12 graus 97,72 % 0 % 0 %

O Omnipage trabalhou com imagens com mais de 12 graus de rotação com uma pequena diferença na taxa de erro (menos de 1%). O mesmo não aconteceu com os outros softwares que apresentaram uma alta taxa de degradação trabalhando com imagens com mais de 3 graus (no caso do Corel) ou 10 graus (no caso do TextBridge). Sensibilidade ao Brilho O próximo experimento tem como objetivo determinar o melhor valor de ajuste de brilho na digitalização a fim de obter os melhores resultados para cada software. Para tanto, trabalhamos com imagens monocromáticas com 200 dpi. Dois softwares não foram usados neste experimento: o Smartpage devido à sua limitação de resolução a 150 dpi e TypeReader o qual, em sua versão demonstrativa não permite o armazenamento dos arquivos texto gerados. Os documentos serão então digitalizados com diferentes variações no aumento do brilho de 1 a 255 unidades, variando de 5 em 5, totalizando 50 imagens para cada texto (algumas imagens foram excluídas por estarem completamente escuras devido ao valor de brilho ser muito baixo). Essas imagens foram então usadas como entrada para as ferramentas de OCR. Suas respostas foram comparadas com os arquivos originais e a taxa média de erro percentual foi desenhada como pode ser visto na Figura 14 e na Figura 15.

Alguns pontos de degradação podem ser notados nos gráficos das Figuras 14 e 15. Essa degradação pode ser notada como descontinuidades (na forma de pequenos "vales") nos gráficos acima. Para o Textbridge, por exemplo, uma degradação foi observada com valores de brilho entre 95 e 100. A Figura 16, abaixo, apresenta um exemplo de tal problema. A palavra mostrada na figura seria corretamente transposta como “History”. A imagem digitalizada com 95% de brilho (Figura 16.a) gerou a tradução correta com o TextBridge. O mesmo software, no entanto,

38

traduziu a palavra “History” como “Histwy” com uma imagem digitalizada com valor de brilho de 100% (Figura 16.b). O mesmo ocorreu com alguns outros softwares com outras imagens produzindo o decréscimo na curva de precisão.

Figura 14. Brilho versus Precisão para o TextBridge e o Corel OCR Trace

Figura 15. Brilho versus Precisão para o Omnipage e o Wordlinx

A média de brilho que produziram os melhores desempenhos são mostrados na tabela 6.

O valor médio de brilho que gerou taxas de acerto ótimas nos quatro softwares testados foi de 103,75 que é menor que o valor médio definido pelos digitalizadores, em geral (que vão de 0 a 255). Ou seja, a precisão dos softwares de OCR foi melhor em baixos valores de brilho (imagens mais escuras) do que em altos valores (imagens mais claras). A taxa de erro alcançada nesses valores é diferente para cada software.

a) b)

Figura 16. Detalhes da degradação na digitalização. a) Digitalização com brilho ajustado para 95 e (b) digitalização com brilho de 100

Tabela 6. Melhores valores de brilho para maior taxa de acerto no reconhecimento

Software Melhor valor de brilho Textbridge 90

Corel OCR Trace 115 Omnipage 105 Wordlinx 105

39

1.3.2 Transcrição de Documentos Históricos Para a segunda fase dos experimentos, escolhemos quatro imagens de cartas

datilografadas do acervo de Joaquim Nabuco. Essas imagens são representativas desse tipo de documento do acervo da Fundação Joaquim Nabuco que possui mais de 6.500 documentos. Todos eles são do final do século dezenove e foram digitalizados com 200 dpi de resolução e em tons de cinza. Ressalta-se que apenas o Corel OCR Trace e o Omnipage trabalham com imagens em tons de cinza e, por esse motivo, estes foram os únicos softwares testados a seguir. A tabela 7 mostra a taxa de acerto média para as quatro imagens testadas.

Tabela 7. Taxa de acerto para documentos históricos datilografados Imagem Corel OCR Trace Omnipage D0023 85,70 % 80,31 % D0064 89,58 % 84,45 % D0077 85,14 % 80,07 % D0097 85,51 % 75,43 %

O Corel OCR Trace alcançou os melhores resultados, obtendo, no melhor caso, uma taxa de acerto de mais de 98%. Entretanto, com um espaço amostral maior com cerca de 20 cartas com características diversas (variações no grau de degradação do papel e da tinta, diferentes texturas, etc) a taxa de erro deste software foi de cerca de 30% o que foi considerado inaceitável para os propósitos do projeto. Nesse espaço amostral maior, o OmniPage obteve um melhor comportamento.

1.3.3 Análise de Erros É importante observarmos que a comparação entre a resposta do OCR e o texto original

não é uma tarefa simples. Nos experimentos com diferentes valores de brilho, por exemplo, diversos tipos de erros foram encontrados na saída do OCR. Um processo não-automático para comparação dos textos é inaceitável devido ao custo e a baixa taxa de confiabilidade. Um sistema totalmente automático, entretanto, terá que lidar com todo tipo de erro para gerar uma resposta correta. Antes de analisarmos os erros no arquivos de texto, é preciso que um pré-processamento seja aplicado. Devido a grande variedade de diferentes tipos de erros, os arquivos de texto são formatados a fim de facilitarem o reconhecimento automático de erros. A contagem de erros é feita por comparações com o arquivo de texto original. Problemas para esse processo automático ocorrem em diversas situações. A mais crítica, por exemplo, acontece quando uma linha inteira de texto é reconhecida erroneamente. A ferramenta de OCR pode reconhecer errado todos os caracteres ou não reconhecer a linha e pulá-la, passando para o reconhecimento da próxima linha. Nesse último caso, um sistema de contagem de erros faria a comparação de linhas diferentes do texto original e consideraria que a linha inteira foi reconhecida errada, prosseguindo com a comparação entre linhas diferentes do texto, difundido o erro. No caso, uma única linha não reconhecida poderia provocar uma grande taxa de erro no texto, podendo não representar o valor correto. Assim, o pré-processamento trata desse e de outros problemas que ocorrem no reconhecimento de uma imagem textual por uma ferramenta de OCR, evitando erros na taxa de acerto calculada. Por exemplo, quando uma linha não é reconhecida, uma caractere especial (“-”) é colocado em seu lugar no texto.

Nas imagens testadas, detectamos as seguintes classes de erros nos textos de saída (considerando o pré-processamento feito no texto, explicado anteriormente):

• Substituição de um caractere por outro (“e” por “c”) • Substituição de um caractere por mais de um (como em “m” por “rn”) • Substituição de mais de um caractere por apenas um (como em “rn” por “m”) • Perda de caracteres (supressão)

40

• Junção de palavras sem perda de caracteres (supressão de espaços em branco) • Junção de palavras com perda de caracteres • Perda completa de linhas de texto • Inserção de caracteres • Inserção de ruído

O primeiro item acima é o mais fácil de ser tratado. Este problema não causa nenhuma

mudança no comprimento da palavra original; apenas a substituição de um caractere diferente de espaço. Devemos observar que não estamos interessados, no momento, na correção das palavras feita com o auxílio de um dicionário. Nosso interesse está enfocado apenas na detecção de erros. Quando o valor de brilho é ajustado próximo aos valores ótimos dos OCR’s (tabela 5), a substituição de um caractere por outro é o erro mais comum, seguido pela inclusão de caracteres, geralmente, devido a ruídos no documento original. Smartpage e Wordlinx foram os softwares que tiveram as maiores taxas de troca de caracteres (cerca de 60% de seus erros). Os outros softwares apresentaram uma divisão mais distribuída dos seus erros entre todas as classes, observando o crescimento da taxa de inclusão de caracteres em altos valores de brilho. O pior caso para detectar é quando uma ou mais linhas completas são apagadas. O sistema deve decidir se houve mesmo uma exclusão ou se a linha foi reconhecida inteiramente errada. Embora esta seja a classe mais difícil de detectar é também a mais rara, sendo detectada apenas em altos e baixos valores de brilho. A junção de duas palavras com ou sem perda de algum caractere é também um erro comum encontrado em altos e baixos valores de brilho. Entre essas duas classes, o erro mais freqüente é a união de duas palavras sem a perda de qualquer caractere. Como mencionado anteriormente, estamos interessados apenas na detecção de erros gerados pelas ferramentas de OCR para comparação entre sua saída e o arquivo original. Nenhuma tentativa de correção de erros foi feita. Em altas resoluções, o tipo de erro mais comum é causado por um reconhecimento errado de algum caractere. Esse tipo de erro pode ser corrigido, se um dicionário for usado em conjunto com o OCR. Em baixas resoluções, todas as classes de erro estão presentes no texto de saída e é praticamente impossível utilizar apenas uma técnica para corrigi-los.

1.4 Conclusão Neste Capítulo, analisamos as principais características de um ambiente para processamento de documentos e os fatores que afetam a taxa de acerto de ferramentas de OCR. Alguns desses fatores advém do processo de digitalização e podem prejudicar sensivelmente os algoritmos de reconhecimento de padrões. Em busca de uma ferramenta de OCR para atender às necessidades do Projeto Nabuco testamos diversos softwares comerciais e, inclusive, desenvolvemos uma ferramenta primitiva. Concluímos que a criação de um software próprio não traria muitas vantagens em termos de custo e benefício, se utilizado como único recurso de OCR. Submetendo os programas comerciais a diversas condições extremas, consideramos o Omnipage como a ferramenta mais adequada ao projeto. O OCR primitivo desenvolvido ainda será analisado posteriormente em próximas etapas do Projeto, onde um sistema de OCR’s múltiplos será desenvolvido. As respostas dos OCR’s serão analisadas e o sistema deverá determinar qual a melhor resposta a cada palavra reconhecida. Nesse caso, um aprimoramento na ferramenta primitiva desenvolvida, ajustada especificamente para os documentos de Joaquim Nabuco, poderá servir como um ponto de partida para a decisão a ser tomada automaticamente. Um dos primeiros passos no processo de transcrição de uma imagem textual para um arquivo editável de texto é a segmentação, como foi apresentado neste Capítulo. Uma segmentação eficiente pode levar o sistema a altas taxas de acerto quanto ao reconhecimento.

41

Documentos históricos apresentam o agravante de possuírem uma textura característica no papel com propriedades as mais adversas por causa da degradação provocada por diversos fatores. Dessa forma, um algoritmo de segmentação eficiente é fundamental quando falamos em reconhecimento automático de caracteres da digitalização de tais documentos. Por esse motivo, abordaremos no próximo Capítulo alguns dos principais algoritmos para segmentação de imagens, incluindo um novo algoritmo desenvolvido no âmbito desta tese.

42

2

Segmentação de Documentos

O processo de delimitação de áreas em imagens é denominado Segmentação. A

segmentação de uma imagem pode ser útil em diversas aplicações [24]: no reconhecimento óptico de caracteres ela separa as letras reconhecidas e traduzidas para texto, por exemplo. O presente capítulo trata da aplicação da segmentação como um classificador de objetos em uma imagem, visando a separação do objeto considerado como fundo da imagem do objeto considerado como frente. Nesse caso, a segmentação é usada para separar partes da imagem (como a tinta e o papel).

O problema maior na implementação desse processo nas imagens dos documentos do acervo de Joaquim Nabuco está na semelhança entre alguns tons de tinta e de papel. Isso torna o processo de separação entre ambos mais complicado. Basicamente, em um documento, encontramos duas classes de cores: as da tinta e as do papel. Seus histogramas, no entanto, não são tão claramente distintos. Uma imagem digitalizada de um documento escrito sobre papel branco apresenta um histograma com um pico na cor branca (R=G=B=255), observando que, em geral, a maior parte das cores de um documento corresponde ao papel. Nesse caso, pode-se considerar que as outras cores são da tinta ou são ruídos. Para esse tipo de documento, esse comportamento pode se repetir para um grande número de amostras com pequenas variações. No Projeto Nabuco, no entanto, essa separação não é tão constante, variando o ponto de separação entre as duas classes freqüentemente. Piores ainda são os casos onde uma nova classe se apresenta com cores da tinta transpassada de um lado para outro do papel.

Podemos ver na Figura 17 o resultado da aplicação de um algoritmo de recorte para redução de cores de uma imagem baseado na cor mais próxima: dado um valor de corte, as cores acima desse valor serão transformadas para branco e as cores abaixo, para preto. Para tanto, foi usado o software Photoshop� da Adobe Systems [92] que possui tal algoritmo implementado, utilizando um valor de corte igual a 127 (um valor médio na escala de níveis de cinza, padrão em alguns softwares). Diversos tipos de algoritmos de segmentação podem ser encontrados em [26] (apresentando um algoritmo baseado em filtros de Gabor), [39] (com uma análise de texturas feita usando Wavelets) e [81] (com um algoritmo baseado em momentos estatísticos).

Os algoritmos para segmentação de imagens podem ser divididos em: globais e locais. Os métodos globais utilizam um único valor de corte para segmentar toda a imagem. O segundo tipo possui um valor inicial de corte e esse valor pode ser alterado à medida que a imagem vai sendo varrida. Deteremo-nos ao estudo de algoritmos globais de segmentação por questões de eficiência.

Analisaremos aqui, primeiramente, três algoritmos clássicos de recorte de cor (threshold) e, em seguida, três dos principais algoritmos baseados em entropia [1] para segmentação de imagens encontrados na literatura: o algoritmo de Pun [64][68], o de Kapur-Sahoo-Wong

Capítulo

43

[33][64] e o de Johannsen e Bille [27][64], além do algoritmo de Otsu [61], um dos mais usados em termos de segmentação de imagens, principalmente imagens médicas. Tais algoritmos são descritos de forma sucinta, aplicando-os às imagens do acervo. Nessa primeira análise, apenas imagens em tons de cinza serão trabalhadas. Os algoritmos foram aplicados a um conjunto de 200 imagens representativas do acervo de Joaquim Nabuco. Observamos que não serão analisados algoritmos de dithering [17], pois, embora seus resultados sejam extremamente satisfatórios quanto à redução de cores (como através do algoritmo de Difusão de Erro, por exemplo), eles não são apropriados para um de nossos principais propósitos que é a eliminação do fundo da imagem para melhor resposta de ferramentas de OCR.

a) b)

Figura 17. Exemplo de recorte de cor usando o software Photoshop. (a) Imagem original em 256 tons de cinza e

(b) sua versão filtrada em 2 cores pelo software Photoshop com valor de corte de 127 No final deste Capítulo, um novo algoritmo para segmentação baseado em entropia será

descrito. O material constante neste capítulo foi anteriormente publicado em [46][47][49]: • A New Segmentation Algorithm for True Colour Images of Historical Documents, XVIII

Simpósio Brasileiro de Telecomunicações, setembro de 2000, Gramado, RS, Brasil, apresentando o novo algoritmo para segmentação aplicado a imagens coloridas.

• Image Segmentation of Historical Documents, Visual 2000, agosto, 2000, Cidade do México, México, descrevendo uma variação na versão original do algoritmo de segmentação, onde foram definidas alguma mudanças nos parâmetros de segmentação.

• Segmentação de Imagens de Documentos Históricos, XVII Simpósio Brasileiro de Telecomunicações, setembro, 1999, Vila Velha, ES, Brasil, apresentando o novo algoritmo de segmentação desenvolvido.

44

2.1 Algoritmos Clássicos de Segmentação Trataremos primeiro com imagens em tons de cinza, onde as cores são definidas por um

valor apenas, igual para as três componentes RGB do espaço de cores (R=G=B). Para tais imagens, o mais comum dos algoritmos de recorte de cor define um valor fixo de limiar (ou valor de corte ou ainda valor de threshold) e os tons acima desse valor são convertidos para branco e os tons abaixo tornam-se preto, a fim de gerar uma imagem monocromática. Esse é o mais simples algoritmo de segmentação e é aplicado na maioria das ferramentas comerciais para edição de imagens, como Photoshop [92], por exemplo, conforme mencionado anteriormente. O resultado de sua aplicação em uma imagem do acervo de Joaquim Nabuco pôde ser visto na Figura 17. Algumas variações nesse algoritmo são possíveis, utilizando um valor de corte variável definido, por exemplo, pela cor mais comum na imagem. Um segundo algoritmo bastante utilizado é o de seleção iterativa [64]. Neste método, um valor inicial de limiar é definido e refinado ao longo de iterações. O valor inicial é definido como o ponto médio dos tons presentes no histograma da imagem. Esse valor é usado então para calcular duas novas médias: a média das cores abaixo deste ponto inicial, chamada Tb, e a média das cores acima do ponto inicial, Tw. Uma nova estimativa de limiar é calculada com valor

2/)( TwTb + . O processo é então repetido até que Tb = Tw ou Tb > Tw. Uma variação nesse algoritmo pode ser conseguida com a utilização de uma média ponderada para o cálculo do valor inicial de corte e os valores de Tb e Tw. Os resultados da aplicação destes dois algoritmos podem ser vistos na Figura 18.

a) b) c)

Figura 18. Algoritmos de segmentação baseados em médias. a) Imagem original em tons de cinza e sua segmentação por seleção iterativa usando b) a média e c) a média ponderada.

Os resultados gerados pelo algoritmo de seleção iterativa não foram satisfatórios tanto em

termos de qualidade quanto de resposta eficiente de ferramentas de OCR (no caso de documentos datilografados), principalmente, quando aplicado a imagens com interferência frente-verso, como pode ser visto na Figura 17 anterior.

Um maior destaque deve ser dado a um dos algoritmos mais usados em termos de segmentação: o algoritmo de Otsu [61]. O algoritmo tem como base a análise de discriminante. Os pixels da imagem são classificados entre cor de frente (tinta) ou cor de fundo (papel). A segmentação é feita usando as médias das classes ( bµ e wµ , para os pixels classificados como

tinta e papel, respectivamente), das variâncias intra-classes 2bσ , inter-classes 2

wσ e total 2Tσ ,

definidas como:

)()(

0 twtt

b

µµ = e )(1)(

0 twttt

w −−

=µµµ

2

102 ])[()( wbb twtw µµσ −= �

=−=

255

0

22 )()(i

tt ipi µσ 222 )( btw t σσσ −=

45

onde

�=

=t

i

iptw0

0 )()( e �+=

−==255

101 )(1)()(

ti

twiptw

�=

=t

it ipit

0

)(.)(µ e �+=

=255

1

)(.ti

T ipiµ

Nicor

ip)(

)( = , N = número total de pixels e cor(i) é o número de vezes que a cor aparece

no histograma da imagem Otsu demonstrou que o valor ótimo do limiar t* pode ser encontrado pela maximização da

função 2

2 )()(

T

b tt

σση = , ou seja, a variância entre-classes dividida pela variância total. O algoritmo

de Otsu foi aplicado a um conjunto de cerca de 200 imagens, conseguindo bons resultados em muitos casos. No entanto, quando aplicado a imagens apresentando interferência frente-verso, o algoritmo gerou imagens monocromáticas com perceptível presença de pixels do verso do documento, não conseguindo filtrar a maioria deles. Um exemplo da aplicação do algoritmo em uma tal imagem, conforme apresentado anteriormente, na Figura 18 pode ser visto na Figura 19.

a) b)

Figura 19. Algoritmo de segmentação de Otsu. a) Imagem original em tons de cinza com interferência frente e verso e b) sua segmentação pelo algoritmo de Otsu.

Alguns algoritmos para segmentação utilizam-se do conceito de Entropia. Definida por

Claude Shannon em 1948 [74][75], a Entropia é uma medida de informação. A Teoria da Informação, desenvolvida por Shannon, visa a modelar o conceito de informação, definida como segue. Seja E um evento que ocorre com probabilidade p(E). Assim, se E ocorreu, diz-se que foram recebidas

))(

1log(

EpI = unidades de informação

Esse conceito de informação tem um caráter intuitivo. Dado um evento com probabilidade 1 de ocorrer, ou seja, existe a “certeza”, a informação associada a este evento é nula, pois ele não nos traz nenhuma surpresa. No entanto, quanto menor a probabilidade de ocorrer um determinado evento, maior a surpresa quando da sua ocorrência, conseqüentemente, mais informação será obtida com a sua ocorrência. Suponha que existem n possíveis símbolos x e que o símbolo i ocorre com probabilidade

)( ixp . Então, a entropia associada com a fonte X dos símbolos é:

�=

−=n

iii xpxpH

1

)](log[)(

46

onde a entropia é medida em bits/símbolo para uma fonte binária. A seguir, apresentaremos de forma sucinta três algoritmos de segmentação baseados no

conceito de entropia.

2.1.1 Algoritmo de Pun Pelo algoritmo de Pun [69], a entropia associada aos pixels pretos, Hb, e a entropia

associada aos pixels brancos, Hw, são delimitadas pelo valor de corte t. O algoritmo sugere que t seja tal que maximize a função H = Hb + Hw. Onde, Hb e Hw são determinados por:

�−=t

ipipHb0

])[log(][ (1)

e

�+

−=255

1

])[log(][t

ipipHw (2)

Onde ][ip é a probabilidade do pixel i de cor ][icor na imagem, dada pela razão entre o número de aparições da ][icor pelo número total de pixels na imagem e o logaritmo é tomado com base 256, considerando que tratamos com imagens em um universo de 256 possíveis níveis para cada tom. Isso não afeta o conceito de entropia, já que, como afirmado em [36], a base dos logaritmos provê apenas uma unidade de medida.

Considere-se, como exemplo, a aplicação do algoritmo de Pun à imagem da Figura 17.a. Primeiro, calculam-se as distribuições de probabilidade dos tons de cinza (de 0 a 255). Abaixo, apresentam-se os dez valores com maior probabilidade dessa distribuição:

Nível de Cinza Probabilidade (%)

.... ... 143 2,3303 144 2,4777 145 2,595 146 2,704 147 2,8061 148 2,7842 149 2,7756 150 2,7247 151 2,5998 152 2,4432 .... ...

De início, o valor de corte, t, é igual a zero. Calcula-se HbHw + , onde Hw e Hb são

definidos segundo as equações 1 e 2. O valor da soma é armazenado, t é incrementado e, novamente, HbHwH += é calculado para o novo valor de t. Procede-se assim, buscando que valor de t levou a soma de Hw e Hb ao máximo e este será o ponto de corte das cores da imagem na segmentação. Pun demonstrou que a maximização da entropia H é conseguida maximizando a função F(t) definida como:

)),...,,(log()1log(

]1[)),...,,(log(

)log()(

2552110 pppMaxP

HwHb

pppMaxP

HwHb

tFtt

t

t

t

++

−−+=

47

Onde �=

=t

iit pP

0

é a probabilidade acumulada até o tom de corte t.

Na imagem em teste, foram encontrados os seguintes valores para t e para a função a ser maximizada F(t) :

t F(t) 0 0,000005 1 0,000013 2 0,000020 3 0,000047 4 0,000101 5 0,000190 6 0,000333 … …

135 0,179273 136 0,180587 137 0,181558 138 0,182617 139 0,183128 140 0,183861 141 0,183978

O máximo sendo alcançado para t = 141, resultando em : Hw = 1,958532, Hb = 2,648481 Hw + Hb = 4,607013 t = 141 A imagem segmentada pelo algoritmo pode ser vista na Figura 20.a. Embora a Entropia

tenha alcançado seu valor máximo em t = 141, a imagem resultante não apresentou resultados satisfatórios. O ponto de corte encontrado foi acima do necessário, permitindo que a maioria das cores ficassem abaixo dele. Assim, a imagem gerada apresenta poucas cores removidas pelo processo de segmentação.

2.1.2 Algoritmo de Kapur-Sahho-Wong Assim como no algoritmo de Pun, Kapur-Sahoo-Wong [33] definem o valor de corte t

através da maximização da função H = Hb + Hw. No entanto, as probabilidades agora são definidas através de uma distribuição de probabilidade A para a tinta e uma distribuição B para o fundo da imagem (o papel), tal que:

t

t

tt Pp

Pp

Pp

A ,...,, 10=

e

)1(,...,

)1(,

)1(25521

tt

t

t

t

Pp

Pp

Pp

B−−−

= ++

Onde cada ip corresponde a probabilidade da cor i e tP é a probabilidade acumulada até o valor de corte t.

As entropias Hw e Hb são calculadas através das equações 1 e 2, com ][ip agora de acordo com as distribuições A e B, ou seja:

48

�−=t

tt Pip

Pip

Hb0

)][

log(][

e

�+ −−

−=255

1

)1

][log(

1][

t tt Pip

Pip

Hw

Novamente, a maximização da função, F(t) = HbHw + é analisada para definir o valor de corte t, calculando F(t) para cada valor de t de 0 a 255, definindo seu máximo.

Aplicado a imagem do documento apresentando na Figura 17.a, o algoritmo apresentou os seguintes resultados (observando-se que a distribuição de probabilidade é a mesma apresentada anteriormente) :

t F 0 4,606999 1 5,243487 2 5,661869 3 5,725614 4 5,779921 5 5,886212

… … 97 8,541615 98 8,544100 99 8,545389 100 8,546646 101 8,547775 102 8,548019 103 8,545033

Hw = 4,076193, Hb = 4,468840 Hw + Hb = 8,545033 t = 103 A imagem segmentada segundo esses parâmetros pode ser vista na Figura 20.b. Apesar da

imagem gerada ser de melhor qualidade que a gerada pelo algoritmo anterior, o ponto de corte ainda não foi o ideal já que é possível identificar ainda elementos gerados pela interferência da tinta do outro lado do papel.

2.1.3 Algoritmo de Johannsen e Bille Uma outra variação de algoritmo de segmentação baseado em entropia é proposta por

Johannsen e Bille. [27][64], buscando minimizar a função )()( tStS wb + , onde:

)]()()[/1()log()(1

000���

−

===

++=t

iit

t

ii

t

iib pEpEpptS

e

)]()()[/1()log()(255

1

255255

���+===

++=ti

itti

iti

iw pEpEpptS

sendo )log(.)( xxxE −= e, novamente, t é o valor de corte. Utilizando a Figura 17.a como exemplo, encontramos os seguintes resultados como

pontos de mínimo da função )()( tStS wb + , definida acima,: Sw = 0,008981, Sb = 0,000377

em

49

t = 208 quem geram 009358,0)()( =+ tStS wb e a imagem segmentada é mostrada na Figura 20.c.

a) b)

c) d)

Figura 20. Algoritmos de segmentação aplicados à imagem da Figura 17.a a) Pun, b) Kapur-Sahoo-Wong, c) Johannsen e Bille e d) Otsu.

Como podemos comparar pelas imagens da Figura 20, os três algoritmos não geraram

resultados satisfatórios (principalmente o de Johannsen e Bille), deixando ainda bastante nítidas

50

áreas onde o fundo do documento é bastante visível (o papel). Maiores informações foram procuradas a respeito do algoritmo de Johannsen e Bille, mas não foram encontradas em nenhum repositório de artigos pela Internet. Apenas a referência [64] descreve algo sobre o algoritmo, mas sem apresentar detalhes.

No interesse de eliminar a interferência da tinta de um dos lados no outro, esses algoritmos não alcançaram os níveis desejados. Assim, um novo algoritmo foi desenvolvido e aplicado à nossa base de imagens de documentos históricos. Este novo algoritmo será analisado na próxima seção.

2.2 Um Novo Algoritmo para Segmentação Baseado em Entropia

Devido a baixa qualidade das imagens geradas pelos algoritmos de recorte de cor testados, vimos a necessidade do desenvolvimento de um novo algoritmo de segmentação. Baseado nos estudos feitos nos algoritmos de Pun, Kapur-Sahoo-Wong e Johannsen, um novo algoritmo é proposto também baseado na entropia do histograma da imagem.

Tentamos, a princípio, usar a entropia do histograma das imagens completas como limite para o recorte de cor, mas os resultados foram insatisfatórios. Como as texturas da tinta e do papel apresentam características distintas, dividimos a entropia da imagem em dois grupos. A cor mais freqüente na imagem é utilizada como separador dessas duas entropias. É razoável supor que essa cor faça parte do papel da imagem já que, em geral, apenas um pequena parte do documento é composta por tinta. A longa experiência acumulada pela Xerox para documentos monocromáticos, analisando o número de cópias efetuadas e consumo de toner, mostra que apenas 5% da área de um documento é composto por tinta.

Assim, no primeiro passo do algoritmo, uma varredura é feita na imagem a fim de determinar a cor que aparece mais vezes. Essa cor mais freqüente, t, será usada como valor de corte inicial para determinarmos a entropia dos valores maiores e menores que t no histograma [17] da imagem. Por convenção, a entropia das freqüências acima desse valor de corte será chamada de Hw e Hb será a entropia das freqüências abaixo de t. Como antes, Hw e Hb serão dadas pelas equações 1 e 2. Aqui, porém, a entropia será calculada usando uma base logarítmica igual ao produto das dimensões da imagem. Ou seja, se uma imagem tem dimensões X versus Y, a base do logaritmo será YX × . Novamente, ressaltamos que isso não altera o conceito dado a entropia, como afirmado em [36]. Foi observado, numa base de mais de 500 imagens, que todo os valores de entropia dos histogramas mantiveram-se sempre dentro do intervalo de 0,2 a 0,4. Dessa forma, os documentos foram classificados e separados por inspeção visual de acordo com os seguintes critérios: documentos com interferência frente-verso, documentos claros, documentos com grandes áreas em preto e, por último, uma classe com os documentos que não se enquadram segundo os critérios anteriores (os mais comuns do acervo). As entropias dos histogramas de cada imagem pertencente às classes foram então calculadas. Os valores encontrados de entropia serviram para criar três classes de documentos (alguma interseção entres as classes é possível), unificando algumas das anteriores: • Tipo 1: 25,0≤H

Documentos muito claros e/ou com pouco texto • Tipo 2: 30,025,0 << H

Documentos mais comuns. • Tipo 3: 30,0≥H

Documentos escuros, com grandes quantidades de pixels pretos (como bordas ao redor da carta) e/ou documentos com interferência do verso na frente.

51

Podemos ver exemplos dessas três classes na Figura 21.

a) b)

c)

Figura 21. Exemplos de documentos pertencentes a cada classe definida. a) H=0,22, b) H=0,27 e c) H = 0,32

Consideremos, na Figura 22, a entropia como fator classificador entre pixels com cores

pertencentes ao papel e a tinta. Existe uma grande possibilidade de haver interseção entre as duas classes de objetos (papel e tinta). Para resolver esse problema, vamos decompor a entropia H em

52

duas componentes Hw e Hb, como descrito anteriormente. A Figura 23 apresenta apenas as projeções Hw e Hb a fim de ilustrar o conceito graficamente.

Figura 22. Simulação da disposição de duas diferentes classes em um documento e a separação

destas classes dada por um parâmetro qualquer como Entropia, por exemplo.

Figura 23. Projeções de H em duas componentes de Hw e Hb.

Podemos considerar, assim, Hw e Hb como projeções de H. Buscando uma melhor classificação dos pixels pertencentes ao papel e a tinta, iremos variar os valores de Hw e Hb de forma a aumentar ou diminuir a inclinação da reta referente a H. Esta variação será feita através do produto de Hw e Hb por constantes multiplicativas, chamadas de mw e mb. As três classes de documentos serão definidas a seguir.

Tipo 1: 25,0≤H Neste caso, as cores dos pixels do papel e da tinta podem se confundir, ou pode haver uma quantidade muito pequena de pixels com cor de tinta. A entropia H não pode ser tomada como valor de corte, pois eliminará em alguns casos tanto o papel quanto a tinta. O corte deve ser aumentado para forçar uma maior separação. Para tanto, aumentamos a componente Hw de H, multiplicando-a por um fator mw = 2, mas aumentamos também a componente da tinta, Hb, por um fator ainda maior mb = 3, a definição de tais valores de mb e mw para esta classe de documentos e para as próximas será analisada posteriormente. Um novo valor de corte será dado por:

HbHwHbmbHwmw 32.. +=+ HbHbHw ++= 22 HbHbHw ++= )(2 HbH += 2

Ou seja, o dobro do valor anterior de H acrescido de Hb. Graficamente, podemos analisar a diferença do novo corte feito em relação ao anterior, observando a Figura 24.

53

Figura 24. Modificação do recorte nas cores definido para a classe de imagens com 25,0≤H

Tipo 2: 30,025,0 << H

Para os documentos mais comuns, já há uma separação natural entre o papel e a tinta. Para reduzir as interseções, multiplicamos Hb por um fator de 2,6 (mb) e Hw permanece inalterado (mw = 1). O valor de corte será agora:

HbHwHbmbHwmw 6,2.1.. +=+ HbHbHw 6,1++=

HbH 6,1+= Assim, foi necessário acrescentar a H mais 1,6Hb. Figura 25, mostra o resultado dessa mudança graficamente.

Figura 25. Modificação do recorte nas cores definido para a classe de imagens com

30,025,0 << H Tipo 3: 30,0≥H

Nesse tipo de documento, observamos que a entropia serve como fator de corte, não havendo necessidade de modificação do seu valor. Ou seja, aqui o corte será definido por mw = mb = 1 e:

54

HHbHwHmbHwmw =+=+ ..

Em resumo, a entropia, H, serve de base para definição de dois fatores multiplicativos, mw

e mb, de acordo com as seguintes regras: • Se 25,0≤H , então 2=mw e 3=mb • Se 30,025,0 << H , então 1=mw e 6,2=mb • Se 30,0≥H , então 1=mw e 1=mb

Os valores dos fatores mw e mb foram encontrados através de experimentos, observando a qualidade da imagem final, principalmente, em relação aos documentos com interferência frente-verso, e a melhora na taxa de acerto de ferramentas de OCR aplicadas a documentos datilografados. Nesse sentido, os valores foram alterados e ajustados, aplicando o algoritmo no conjunto de 200 imagens selecionadas, analisando os resultados encontrados no conjunto.

A imagem em tons de cinza é varrida novamente e um novo recorte é feito. Dessa vez, o pixel i é convertido para branco, se:

)..()256/][( HbmbHwmwicor +≥ (3) Caso contrário, sua cor é mantida, gerando uma nova imagem em tons de cinza, ou convertida para preto, dando origem a uma imagem monocromática. Podemos também inverter esse recorte, gerando uma imagem onde a tinta da frente é eliminada, restando apenas o fundo do documento. Isso pode ser feito se o pixel i for convertido para branco se:

)..()256/][( HbmbHwmwicor +≤ (4) em oposição ao que foi feito anteriormente. O novo algoritmo de segmentação aqui proposto foi utilizado diretamente na geração de imagens para dois tipos de aplicações: 1) armazenamento de imagens monocromáticas de alta qualidade dos documentos e 2) a busca por melhores taxas de acerto de ferramentas comerciais de OCR quando aplicadas a documentos datilografados (observa-se que esse caso restringe-se a documentos datilografados porque as atuais ferramentas de OCR não respondem satisfatoriamente a documentos manuscritos). A utilização do algoritmo no documento apresentado na Figura 17.a pode ser vista na Figura 26. Mais exemplos podem ser encontrados nas lâminas encontradas em anexo a esta tese.

Seções anteriores apresentaram outros métodos de binarização por entropia que foram implementados e analisados dentro do projeto. A comparação das Figuras 15 e 18 mostra que esses algoritmos não alcançaram resultados eficientes nem na redução da interferência do verso na frente do papel e nem na melhoria da taxa de acerto de ferramentas de OCR’s. Além de não conseguirem obter os resultados desejados para nossas aplicações, esses métodos apresentaram um tempo de processamento maior que o algoritmo proposto neste trabalho devido ao alto custo nos processos de maximização e minimização de funções que neles existem.

A Figura 27 mostra o novo algoritmo aplicado a imagens de cartões postais. Mesmo não tendo sido desenvolvido para esse fim, o algoritmo apresentou resultados qualitativos satisfatórios em comparação com outros métodos, demonstrando também sua versatilidade. Na mesma figura, apresentamos os resultados de outros métodos de segmentação aplicados ao mesmo cartão postal, sendo o pior resultado o gerado pelo algoritmo de Johannsen.

55

Figura 26. Novo algoritmo aplicado à imagem da Figura 17.a.

A filtragem por entropia aqui descrita foi aplicada em 200 imagens de cartas e cartões

postais do acervo de Joaquim Nabuco. Apenas 5 casos resultaram em imagens de qualidade insatisfatória, necessitando um tratamento especial para maior eliminação das cores classificadas como papel. Podemos ver uma ampliação de uma dessas imagens e a resposta do algoritmo na Figura 28. O documento apresenta a tinta bastante degradada tendo sido quase que totalmente absorvida pelo papel. Nesse documento foi possível obter uma melhor resposta do algoritmo utilizando filtros de variação nos valores de brilho e contraste da imagem. Foi aplicado um filtro que reduziu o brilho da imagem em 55% e aumentou seu contraste em 50%. Nessa nova imagem, o novo algoritmo foi aplicado novamente. Seus resultados podem ser vistos na Figura 29.

Das 200 imagens testadas, 32% delas são do tipo 1, acima definido; 28% do tipo 2 e 40% do tipo 3. Foi observada a presença de imagens com entropia dos pixels acima do valor de corte t, Hw, com valor nulo em 4% dos casos. Tais casos representam imagens com bordas pretas ao redor da carta como pode ser visto um exemplo na Figura 30, onde a cor mais freqüente é o preto (tom 255).

56

a) b)

c) d)

e) f)

Figura 27. Aplicação do novo algoritmo de segmentação e outros algoritmos em cartões postais em tons de cinza.

(a) Imagem original em tons de cinza de um cartão postal do acervo de Joaquim Nabuco (b) algoritmo de corte do Photoshop, (c) algoritmo de Pun, (d) algoritmo de Kapur-Sahoo-Wong,

(e) algoritmo de Johannsen e Bille e (f) novo algoritmo proposto.

57

a) b)

c)

Figura 28. Exemplo de documento onde o algoritmo mostrou-se ineficiente. (a) Imagem original com a tinta bastante degradada, (b) seu histograma e

(c) o resultado após a filtragem pelo novo algoritmo.

a) b)

c)

Figura 29. Pré-processamento no documento anterior para corrigir segmentação. (a) Imagem da figura 26.a com parâmetros de brilho e contraste alterados e

(b) sua nova segmentação pelo algoritmo proposto.

58

a) b)

Figura 30. Exemplo de carta com Hw = 0. a) Documento original e b) sua segmentação. Uma outra forma de utilizar o algoritmo é aplicá-lo a grupos de linhas. Criam-se sub-

imagens onde o algoritmo será executado. Toda a segmentação é feita agora em cada sub-imagem, considerando que linhas mais próximas apresentam características mais semelhantes melhorando o processo de segmentação. Algumas imagens que geraram respostas insatisfatórias anteriormente, obtiveram melhores resultados com a aplicação em sub-imagens como pode ser visto na Figura 31. Com a aplicação do algoritmo a grupos de linhas, o algoritmo consegue encontrar os melhores valores de corte para pequenas partes da imagem. Dessa forma, é possível ter ajustes mais precisos em imagens onde haja pouca diferença entre as cores da tinta e do papel, como no caso de documentos com tonalidades escuras para o papel. Nesses casos, o melhor valor encontrado para o número de linhas em cada grupo é 10. Não foi encontrado nenhum critério específico que defina esse número de linhas em relação a algum parâmetro. De fato, o uso do algoritmo em grupos de linhas só mostrou-se mais eficiente que o original aplicado a toda a imagem em alguns casos, sem, no entanto, podermos classificar tais casos.

O algoritmo foi aplicado também a imagens de textos datilografados pertencentes ao acervo do Projeto Nabuco. Nosso interesse aqui também está na melhora da resposta de ferramentas de OCR. Através da aplicação direta da filtragem por entropia o ruído proveniente do papel em imagens datilografadas pode ser eliminado ou reduzido, gerando imagens de melhor qualidade.

59

a)

b)

c)

Figura 31. Aplicação do algoritmo em grupos de linhas. a) Imagem original, b) imagem segmentada com o algoritmo aplicado a toda a imagem e

c) imagem segmentada com o algoritmo aplicado a grupos de 10 em 10 linhas.

60

Este sistema de geração de imagens, apresentado em capítulos posteriores, depende fortemente da utilização de imagens de boa qualidade para que a taxa de erro do OCR seja a menor possível. Conforme apresentado no Capítulo anterior, o Omnipage [91] é a ferramenta de OCR que apresenta as melhores taxas de acerto nas mais diversas situações [48], chegando a cerca de 99% de acerto em alguns casos. Não é isso que acontece, porém, quando trabalhamos com imagens de documentos históricos como os que fazem parte do acervo de Joaquim Nabuco. Para esse tipo de imagem, a taxa de erro alcança valores inaceitáveis para o projeto. Procurando obter melhores taxas, aplicamos a filtragem por entropia para gerarmos imagens em tons de cinza para serem usadas como entrada no Omnipage. Podemos ver na Figura 32 uma ampliação de parte de um desses documentos antes e após a aplicação do algoritmo.

A Figura 32.c mostra outra aplicação do algoritmo, como mencionado anteriormente, onde temos eliminadas as cores consideradas como tinta, restando apenas o papel do documento. Essa imagem de fundo será usada na geração de uma base de texturas de papéis da época para fins de sintetização de imagens.

a) b)

c)

Figura 32. Exemplo de segmentação de um documento datilografado. a) Imagem original em detalhes, (b) imagem filtrada retirando as componentes

classificadas como papel e (c) sua versão complementar.

2.2.1 O Novo Algoritmo de Segmentação Aplicado a Imagens Coloridas Uma variação do algoritmo apresentado na seção 2.2 foi desenvolvida para trabalhar com

imagens de cartas e documentos coloridos (em true colour - 16 milhões de cores) com espaço de cromaticidade definido no sistema RGB. Nesse formato, cada cor da imagem é formada por 24 bits, onde cada tom de vermelho, verde e azul é representado em 8 bits (dentro do padrão RGB – Red, Green e Blue). Nessa variação do algoritmo apresentado na seção anterior, todos os cálculos feitos na versão para tons de cinza são aplicados a cada freqüência de r, g e b que forma a cor. Consideramos que não há correlação espectral entre os tons. Assim, onde antes tínhamos apenas

61

H, Hw e Hb, agora, temos, Hr, Hwr, Hbr (para as freqüências de vermelho), Hg, Hwg, Hbg (para as componentes de verde), Hb, Hwb e Hbb (para as freqüências de azul). Da mesma forma, os fatores multiplicativos i e mb estão explicitados para cada freqüência (mwr, mbr, mwg, mbg, mwb e mbb) segundo as mesmas regras definidas anteriormente. Para o cálculo de cada Hwf e Hbf (onde f = r, g ou b) usaremos as equações 1 e 2, onde uma freqüência de corte diferente será tomada para r, g e b. Uma mudança no algoritmo original é feita quanto à classificação do pixel como papel ou tinta. Na versão para tons de cinza, essa classificação é feita baseada apenas no resultado da condição de segmentação. Como, com imagens coloridas, trabalhamos com três tons diferentes para formar a cor do pixel, a mesma inequação será calculada para cada freqüência (r, g e b): )..()256/][( HbfmbfHwfmwfif +≥ (5) com f = r, g ou b, referente a cada uma das freqüências que compõem a cor do pixel. O pixel será considerado como papel apenas se, em pelo menos um caso, a condição for verdadeira. Se a condição for falsa para os valores de r, g e b do pixel, a cor permanece inalterada na imagem resultante. Um exemplo da utilização desse algoritmo em uma imagem do acervo de Joaquim Nabuco pode ser vista na Figura 33. Como na versão para imagens em tons de cinza, uma inversão no sinal da desigualdade acima gera uma imagem apenas com as componentes classificadas como papel, como pode ser visto na Figura 33.c. A Figura 34 apresenta o resultado da aplicação do algoritmo a imagem do documento apresentado na Figura 1. Como dito anteriormente, para fins de segmentação, três tipos de imagens foram definidos, tomando a entropia como base: para o Tipo 1, temos imagens com entropia do histograma (H) 30,025,0 << H ; Tipo 2, 25,0≤H ; Tipo 3, 30,0≥H . Separando cada uma das 200 imagens coloridas testadas em três imagens cada qual composta apenas por um dos tons R,G ou B, obtivemos, para as imagens com tons de vermelho, 7% do tipo 1, 23% do tipo 2 e 70% do tipo 3. Porcentagens semelhantes foram encontradas para as imagens em tons de verde. As imagens em tons de azul apresentaram 9% do tipo 1, 28% do tipo 2 e 63% do tipo 3.

Nota-se aqui também a presença de valores nulos para a entropia dos pixels abaixo do tom mais freqüente t, (Hw), para cada tom. Para o vermelho houve a presença de 18% de valores nulos para Hwr, o mesmo aconteceu em 7% para Hwg e 2,7% para Hwb. Há interseções em alguns casos. 4% das imagens testadas apresentam Hwr e Hwg com valor nulo ao mesmo tempo, representando, em geral, imagens com muitas manchas no papel. Em, aproximadamente, 3% dos casos, tanto Hwr, quanto Hwg e Hwb possuem valor nulo, sendo esses representados por documentos com bordas escuras. Todas as imagens que possuem Hw=0 quando em tons de cinza, também apresentam o mesmo valor para alguma freqüência de RGB quando coloridas.

Na Figura 35, podemos ver a aplicação do algoritmo em uma imagem manuscrita colorida com interferência do verso na frente. Também quando aplicado a cartões postais coloridos, o algoritmo apresentou resultados satisfatórios como pode ser visto na Figura 36. Mais detalhes da aplicação do novo algoritmo de segmentação aplicado a imagens coloridas podem ser vistos nas Lâminas de 6 a 8, onde o algoritmo foi aplicado às imagens apresentadas nas lâminas 1, 3 e 5. O uso do algoritmo no documento da lâmina 4 não apresentou resultados satisfatórios, como mostrado na Figura 28, e, por isso, não é apresentada nas lâminas.

A segmentação do documento apresentado na Figura 1 pode ser vista na Figura 34.

62

a)

b)

c)

Figura 33. Aplicação do novo algoritmo a imagens coloridas de documentos datilografados. (a) Imagem original colorida, (b) sua segmentação sem o papel e

(c) a segmentação sem a tinta.

63

Figura 34. Segmentação do documento da Figura 1.

64

a)

65

Figura 35. Aplicação do novo algoritmo a imagem com interferência frente-verso.

a) Imagem original e b) Segmentação apresentando apenas os pixels classificados como tinta.

66

a)

b)

Figura 36. Aplicação do algoritmo a imagens coloridas de cartões postais. a) Imagem original e b) Imagem segmentada.

67

2.3 Algoritmos de Segmentação e Reconhecimento Óptico de Caracteres

O algoritmo apresentado na seção anterior foi aplicado ao conjunto de imagens do acervo de Joaquim Nabuco testadas no Capítulo 1. As mesmas imagens testadas na seção 1.3.2 foram filtradas pelos algoritmos de segmentação baseados em entropia apresentados e as novas imagens geradas foram submetidas ao reconhecimento dos softwares Corel OCR Trace e OmniPage. Seus resultados podem ser vistos nas tabelas 8 e 9 (a segunda coluna de cada tabela refere-se aos dados apresentados na tabela 7).

Tabela 8. Taxa de acerto do Corel OCR Trace para documentos históricos datilografados filtrados por algoritmos baseados em entropia

Imagem Corel OCR Trace Johannsen Pun Kapur-Sahoo-Wong Novo D0023 85,70 % 85,62 % 83,48 % 85,36 % 85,62 % D0064 89,58 % 89,30 % 88,67 % 90,01 % 89,37 % D0077 85,14 % 85,25 % 85,25 % 85,25 % 85,37 % D0097 85,51 % 84,55 % 83,79 % 83,79 % 83,71 %

Tabela 9. Taxa de acerto do OmniPage para documentos históricos datilografados filtrados por

algoritmos baseados em entropia Imagem OmniPage Johannsen Pun Kapur-Sahoo-Wong Novo D0023 80,31 % 78,25 % 43,32 % 91,69 % 91,44 % D0064 84,45 % 84,52 % 63,76 % 85,23 % 80,07 % D0077 80,07 % 80,07 % 71,89 % 77,30 % 92,40 % D0097 75,43 % 5,15 % 69,57 % 73,42 % 88,03 %

Pode-se observar uma pequena perda na taxa de acerto do algoritmo aqui proposto para o

algoritmo utilizado pelos próprios softwares em alguns casos. Essa perda pode ser justificada por uma possível eliminação de parte de alguns caracteres no processo de segmentação pelo novo algoritmo proposto, provocando erro no reconhecimento do documento.

Os outros algoritmos apresentados anteriormente para segmentação (baseados em entropia ou não) foram testados a fim de obter melhores respostas das ferramentas de OCR, mas, como as imagens binarizadas geradas por esses algoritmos eram de pior qualidade, como já mostrado, os resultados obtidos com o novo algoritmo aqui apresentado foram superiores a todos. Ressaltamos que este é um passo essencial para uma alta taxa de acerto dos algoritmos para reconhecimento de caracteres.

2.4 Conclusão Foi apresentado nessa seção, um estudo sobre alguns dos principais algoritmos para segmentação, destacando-se as técnicas baseadas na entropia do histograma. Devido à baixa qualidade das imagens geradas, um novo algoritmo foi desenvolvido, também baseado na entropia do histograma das imagens. Tal algoritmo é aplicado tanto a imagens em tons de cinza quanto coloridas. O objetivo é gerar uma imagem do documento, apenas com os pixels classificados como tinta, eliminando o máximo possível, as cores do papel. Particularmente, o algoritmo obteve excelentes resultados quando aplicado a imagens de documentos do acervo escritos nos dois lados do papel. Tais documentos apresentam uma interferência de um lado no outro quando digitalizados. Em geral, essa interferência é o principal problema encontrado pelos algoritmos de segmentação.

68

O novo algoritmo foi aplicado a imagens de documentos datilografados para fins de melhora da resposta de ferramentas de OCR, obtendo resultados bastante satisfatórios, aumentando a taxa de acerto em até mais de 10%. As imagens segmentadas apresentando as cores classificadas como papel podem ser utilizadas para estudos sobre textura. Assim, pode-se tentar desenvolver um método para geração automática da textura do papel para uma posterior composição com a imagem textual. No próximo Capítulo, analisaremos os principais aspectos das texturas das imagens das cartas e documentos históricos do acervo de Joaquim Nabuco.

69

3

Análise de Texturas

Tendo como base o algoritmo apresentado no Capítulo 2, neste Capítulo apresentamos o

desenvolvimento de um ambiente para geração das texturas dos papéis dos documentos do acervo de Joaquim Nabuco. Consideraremos aqui uma textura como um padrão que se repete em uma superfície. Especificamente, será o padrão que define a superfície do papel do documento.

Como dito anteriormente, não existem conceito universal para o termo textura. Podemos analisar uma textura como um padrão envolvendo uma superfície. O termo é bastante comum em Computação Gráfica, onde os modelos de objetos são “encobertos” por uma textura a fim de dar naturalidade à cena. Diversas definições para o termo podem ser encontradas em [85], assim como exemplos de aplicações.

Procuraremos desenvolver aqui um método automático para criação do espaço de cores onde a textura é formada. Não nos preocuparemos com a distribuição espacial da textura, considerando-a com um comportamento uniforme o que não minimiza a complexidade do trabalho, nem os resultados encontrados.

Como vimos, através do novo algoritmo de filtragem por entropia apresentado, uma inversão na condição de segmentação cria uma imagem do documento com a eliminação da parte referente à tinta. Dessa forma, apenas o que for considerado papel estará presente na imagem final, sendo a tinta substituída pela cor branca, conforme pode ser visto na Figura 37.

a) b)

Figura 37. Exemplo de filtragem eliminando apenas os pixels classificados como tinta. (a) Imagem Original e (b) sua filtragem com a eliminação da tinta

Uma forma de gerar uma textura de papel “limpo”, ou seja, sem referências a qualquer

presença de caracteres, seria a pintura das áreas em branco (ou “buracos”) por um padrão específico. A Lâmina 9 apresenta um detalhamento ainda maior da imagem filtrada apresentada na Figura 37.b. Foi escolhida para análise uma parte da imagem próxima de onde antes havia uma

Capítulo

70

letra no documento original. Algumas observações devem ser feitas com essa imagem. Como já discutido, devido ao processo de digitalização, uma “borda” cerca todas as letras dos documentos. Se tentarmos inserir cores nos buracos sem um tratamento adequado a este problema, o resultado será insatisfatório. Podemos observar em detalhes, como exemplo, na Lâmina 10, o resultado de uma simples substituição da cor branca da Figura 37.b pela média do histograma da imagem. É possível perceber a presença de uma borda ao redor dos locais onde haviam caracteres antes. Assim, a necessidade de aplicar, neste processo de coloração, um tratamento prévio a estas áreas fica justificado. Mesmo em tamanho normal (sem fator de ampliação) esta borda é perceptível. A geração automática da textura é usada no projeto para fins de geração automática de todo o documento original. À textura é acrescentada a imagem textual ou o texto é completamente gerado através de um conjunto de fontes, como será descrito no próximo Capítulo.

Existem diversos métodos para gerar padrões de textura como descrito em [83]. Novamente, Tuceryan e Jain [80] fazem uma descrição de outros métodos para geração e um algoritmo para repetição de um padrão pequeno em uma imagem maior pode ser visto em [7].

Desenvolvemos, aqui, dois processos para geração da texturas. O primeiro, mais simples, trata do preenchimento dos buracos na imagem por um padrão gerado através de informações estatísticas do próprio documento. O segundo método sintetiza completamente a textura, partindo de um arquivo de dados sobre a imagem. Estes dois processos são analisados a seguir.

3.1 Geração de Texturas 1: Preenchendo e Colorindo Antes de proceder com o preenchimento das áreas em branco (buracos), o efeito da “sombra”

observada na borda de caracteres deve ser reduzido, tornando essa área mais próxima a textura real do papel. Após a redução (ou eliminação) dessa borda, vamos prosseguir com a geração das texturas dos papéis. Ressaltamos que nosso objetivo é a geração de imagens a partir de arquivos texto. O algoritmo aqui descrito foi apresentado no trabalho [48]:

• Generating Paper Texture Using Statistical Moments, Carlos A.B.Mello e Rafael D.Lins, Silver Jubilee IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP 2000, Istanbul, Turquia, junho/2000. Busca-se o preenchimento dos espaços em brancos gerados pelo novo algoritmo de

segmentação quando usado para eliminar as freqüências classificadas como tinta nos documentos. Para tanto, um padrão deve ser construído automaticamente, casando com a textura original do papel. O problema da “sombra” gerada pela digitalização, como descrito anteriormente e exposto na Lâmina 9, deve ser tratado antes da geração da textura. Essa filtragem pode ser feita de duas formas: a primeira através de um ajuste dos parâmetros de segmentação do algoritmo; a segunda, através da filtragem das freqüências durante o processo de geração da textura. O primeiro processo não se mostrou eficiente por eliminar cores pertencentes ao papel mesmo. O segundo tipo de tratamento será descrito a seguir.

Todo o processo apresentado nesta seção é realizado em imagens em tons de cinza as quais são coloridas conforme será descrito posteriormente. A conversão da imagem em true colour para tons de cinza é feita baseada na equação padrão [17] para tal conversão:

bgrC .11,059,0.3,0 ++= (6) onde C é a nova cor de cinza gerada truncada para um valor inteiro e r, g e são as componentes da cor original.

71

A geração desses padrões de textura tem como objetivo principal a compressão de imagens. Para fins de coloração foram usadas medidas estatísticas baseadas no conceito de momentos estatísticos. A média, definida por

�=i

ixNx )/1(

refere-se ao primeiro momento, sendo o segundo momento relativo ao desvio padrão, estabelecido pela equação:

� −=i

i xxN 2)()/1(σ

Em geral, um momento central de ordem n pode ser definido como:

� −=i

nin xxNM )()/1( (7)

onde N é o número de dados, n é a ordem do momento e x é a média. Outros momentos também podem ser usados para caracterizar áreas de textura. Momentos de terceira e quarta ordem definem duas outras medidas: a assimetria (Skewness - Sk) e a curtose (Kurtosis - Kurt) [64]. A assimetria caracteriza o grau de assimetria de uma distribuição ao redor de sua média. Enquanto a média e desvio padrão são quantidades dimensionais, a assimetria é adimensional, sendo um valor que apenas caracteriza a forma de uma distribuição. Um valor positivo de assimetria indica uma distribuição com uma “cauda” de assimetria mais para o lado positivo do eixo X; um valor negativo indica uma cauda extendida para o lado negativo do eixo. Um exemplo de duas distribuições com assimetria positiva ou negativa é apresentado na Figura 38.a. Se a distribuição é simétrica, como uma distribuição Normal, o valor de assimetria é zero. A curtose mede o quão achatada uma distribuição é em relação a uma distribuição Normal. Seu valor também é adimensional. Uma distribuição com curtose positiva é chamada leptocúrtica e uma distribuição com curtose negativa é chamada platicúrtica. A Figura 38.b apresenta distribuições com as duas características de curtose.

Estes dois momentos são expressos como:

( )� −==i

i xxNMSk33

3 /)()/1(/ σσ (8)

e

( ) 3/)()/1(3/44

4 −−=−= �i

i xxNMKurt σσ (9)

Onde, como antes, x é a média e σ é o desvio padrão calculados sobre todos os pixels diferentes de branco na região. A equação 9 acima é definida, atualmente, como excesso de curtose. Essas medidas estatísticas serão usadas para gerar uma textura de papel tão próxima possível do papel original. A lâmina 10 mostra a substituição dos pixels brancos pela média do histograma da imagem, não gerando uma textura de boa qualidade.

72

a) b)

Figura 38. Distribuições com terceiros e quartos momentos significativamente diferentes de uma distribuição Gaussiana. a) Assimetria (terceiro momento). b) Curtose (quarto momento). Apresentamos aqui um algoritmo para geração de texturas com duas variações no

processo de preenchimento dos pixels brancos baseado na imagem gerada pelo novo algoritmo de segmentação com a condição de segmentação invertida. As medidas estatísticas podem ser tomadas para a imagem completa ou para partes da imagem, repetindo o cálculo para cada número d de linhas, 1 ≤ d ≤ y, onde y é a altura da imagem. Chamaremos de região a parte da imagem em estudo. Assim, uma região pode englobar toda a imagem ou apenas um conjunto de d linhas. Os algoritmos serão aplicados às imagens em tons de cinza como exposto. Trataremos depois do processo de conversão da imagem para colorido. Em um primeiro passo, a distribuição de freqüência do histograma da imagem é calculada. Em uma imagem de dimensões XxY , essa distribuição é considerada uniforme e é calculada pela definição clássica de probabilidade:

nnip i /][ = onde ][ip é a probabilidade da presença de uma cor i no histograma da imagem (0 ≤ i ≤ 255), in é o número de pixels com cor i e n é o número total de pixels. Deve ser observado que n é igual ao número total de pixels da região analisada (definida por d, tornando, assim, Xxdn = , onde X é a largura da imagem) decrescido do número de pixels brancos encontrados na região. Em todos os 200 documentos históricos testados (manuscritos ou datilografados, com interferência ou não) não foi percebida a presença de pixels com cor branca nem na tinta, nem no papel. Tal cor só aparece nas bordas da imagem devido ao processo de digitalização, não sendo considerada, assim, componente do documento original. Assim, todos os pixels brancos encontrados na imagem do documento foram gerados pelo processo de segmentação (pixels classificados como tinta na imagem original). A seguir, a média e o desvio padrão da região são calculados. No histograma de uma região, seja x o valor médio das cores dos pixels; σ , o desvio padrão e max a cor mais freqüente. Ainda, para a região, seja ][icor a cor do pixel i. Quando um pixel branco é encontrado, o sistema lê os três pixels anteriores e procede com um ajuste nas suas freqüências supondo que elas foram afetadas pelo processo de digitalização, criando uma “sombra”ao redor dos caracteres, como descrito no Capítulo 1. Esse ajuste não é feito em qualquer pixel com cor branca. Foi observado que as cores que compõem o papel da carta (trabalhando-se com as imagens compostas apenas pelas componentes classificadas como papel geradas pelo algoritmo proposto no Capítulo 2) diferem bastante das cores que formam as bordas. Ou seja, as freqüências presentes nas fronteiras entre as letras e o papel são encontradas apenas em pequenas partes do papel. O ajuste feito segue as seguintes regras: • Se )(max][ sicor +< ou )(max][ σ−>icor então ][.2,0][][ icoricoricor += • Senão:

73

− Se i=0, então )2

(][σ±= xicor

− Se i ≠ 0, então ]1[][ −= icoricor O número de vizinhos, assim como o fator multiplicativo de 0,2 na primeira regra acima, foram encontrados experimentalmente tendo gerado as melhores repostas. Na segunda regra, o sinal de + ou – é escolhido aleatoriamente. Um exemplo do uso dessa técnica pode ser visto na Lâmina 11. Feito esse ajuste, segue a substituição dos pixels brancos pelo padrão que mantenha a textura concisa. Dois métodos foram testados e serão analisados a seguir, tomando os ajustes feitos até agora.

3.1.1 Método Baseado em Assimetria A expressão (9) é usada para o cálculo da Assimetria (Sk) de uma região. Quando a

varredura detecta um pixel branco, o sistema calcula o novo valor do pixel tal que ele não altere o valor de assimetria da região. Ou seja, o pixel i terá uma cor C determinada por:

xNSkC += σ*)*( 3/1 Se C=255 (branco), seu valor será substituído pela média do histograma na região. Após a definição da nova cor do pixel, um novo valor para o desvio padrão é calculado adicionando agora o novo pixel com cor C.

A Figura 39 apresenta a aplicação do algoritmo em uma imagem com três diferentes definições de regiões.

a) b)

c) d)

Figura 39. Exemplo de preenchimento usando o algoritmo de assimetria. a) Imagem original e preenchimento com (b) d = y (toda a imagem), (c) d = 1 e (d) d = 10.

74

3.1.2 Método Baseado em Curtose Este método é similar ao anterior, usando agora a medida da curtose. Aqui, o pixel branco

receberá uma cor C tal que:

xNkurtC ++= σ*]*)3[( 4/1 A mesma restrição quanto ao valor de C igual a branco deve ser considerada aqui. Um novo cálculo do valor do desvio padrão também deve ser feito considerando a nova cor de pixel. O uso desse método em uma imagem teste com diversos valores de região pode ser visto na Figura 40.

a) b)

c) d)

Figura 40. Exemplo de preenchimento usando o algoritmo de curtose. a) Imagem original e preenchimento com (b) d = y (toda a imagem), (c) d = 1 e (d) d = 10.

3.1.3 Algoritmo de Coloração da Textura por Matiz O algoritmo aqui apresentado foi publicado em [45]:

• Colourising Paper Texture of Grayscale Historical Documents, Carlos A.B.Mello e Rafael D.Lins, I Congresso de Informática da Amazônia, Manaus, Brasil, abril/2001.

A textura do papel foi gerada nesta seção em tons de cinza. A imagem original

segmentada em true colour tem sua paleta de cores reduzida a 256 tons de cinza e só então procede-se com o preenchimento dos buracos relativos ao corte das freqüências de tinta. Após a geração da textura em tons de cinza, ela deve ser colorida para gerar um papel semelhante ao original. Para tanto, algumas informações da imagem original colorida são armazenadas em um arquivo binário e utilizadas. Testes foram feitos aplicando os mesmos algoritmos em imagens coloridas com resultados insatisfatórios Da imagem original do documento, calculamos a média e o desvio padrão de cada tom r, g, b. Essa informação nos fornecerá o espaço de cada cor primária que será usada para criar a

75

versão colorida da imagem. Para cada tom, a princípio, o espaço de cores permitido será dado pelos valores entre x – σ e x + σ . Foi observado que, entre diversas diferentes características, a matiz apresentou um comportamento bastante singular: a maioria dos pixels na textura possuem o mesmo valor de matiz, chamado matiz_max. Nossa estratégia então é selecionar as cores com matiz igual a matiz_max do conjunto de cores formado no espaço R,G,B permitido. O valor de matiz de cada tom é calculado [5] segundo a equação:

)(*)()(/)2/))()cos((( 2 bgbrgrbrgramatiz −−+−−+−= (10) onde, se b > g, então matiz = 2*π – matiz. As variáveis r, g, e b são os valores das cores primárias. A Lâmina 12 mostra uma amostra de uma textura e o conjunto de cores formadas pelos valores RGB que formam matiz_max para essa textura em particular. Essas combinações serão usadas para colorir a imagem. Para a textura da Lâmina 12.a, a matiz mais freqüente tem valor 31 e é encontrada em 64% dos pixels da imagem. Não sendo o único valor de matiz presente, encontramos uma variação entre 28 e 34. O espaço de cores primárias formado para essa imagem gera um conjunto de 1.001 cores com matiz igual a 31. Nos cálculos da matiz e do espaço de cor desprezamos os pixels com cor branca já que estes antes eram ocupados por texto. Diversas outras imagens foram analisadas e apresentaram um comportamento similar.

Como definido anteriormente, da imagem colorida original armazenamos informações de média, desvio padrão de cada tom e a matiz mais freqüente a fim de colorir a versão em tons de cinza. A essas informações é adicionado o valor da entropia das matizes dos pixels (chamada h_hue) da imagem original, a qual também é armazenada em um arquivo de dados. De agora em diante, apenas esse arquivo e a imagem em tons de cinza são necessários para gerar a textura sintética. Devido a presença de outras matizes na imagem, o espaço de cores RGB será alterado tendo seus valores máximos e mínimos calculados para cada tom como: • tom_max = x + fator1*σ + fator2 e • tom_min = x - fator1*σ - fator2

onde x e σ são a media aritmética e o desvio padrão dos tons (r, g ou b) na imagem original e fator1 e fator2 são duas constantes definidas de acordo com as regras: • se h_hue > 1, então fator1 = 1, fator2 = 0 e delta = 0 • senão fator1 = 2, fator2 = 1 e delta = 2. As constantes fator1 e fator2 podem expandir o espaço de cor, enquanto delta permite uma variação no valor de matiz_max de forma que o espaço de matiz permitido encontra-se agora entre os valores de matiz_max ± delta. Definidos os valores máximo e mínimo de RGB, procede-se com a determinação das cores que geram matiz_max, as quais são armazenadas em uma paleta, paleta1. O valor de delta aumenta o espaço de matizes permitidas pelo sistema. Seu valor é determinado pela entropia das matizes da imagem original (h_hue) como definido anteriormente. Selecionadas as cores a serem usadas na imagem final, uma nova paleta é criada, chamada paleta2, e será usada como a paleta final de cores da imagem. Cada entrada na paleta1 terá seu correspondente tom de cinza calculado. Como a diferença entre cores adjacentes na paleta1 é pequena, haverá poucos tons de cinza diferentes. A paleta original da imagem será então substituída por esta nova versão com os tons de cinza substituídos por cores da paleta1.

76

Essa técnica altera apenas uma parte da paleta de tons de cinza completa. A fim de criar uma paleta de cores mais uniforme, os outros tons de cinza que não foram modificados serão agora definidos tomando como base o maior valor da paleta1 que foi inserido na nova paleta de acordo com o seguinte algoritmo: Sejam pos_min e pos_max a posição mínima e máxima da paleta de tons de cinza que foi alterada por entradas da paleta1 e count1 e count2 dois contadores inicializados com os valores zero e pos_min, respectivamente: • Se i < pos_min, então paleta[i] = paleta[pos_max] – count2 e count2 = count2 – 1; • Se i > pos_max, então paleta[i] = paleta[pos_max] + count1 e count1 = count1 + 1.

De fato, como apenas os valores da paleta de tons de cinza são alterados, a estrutura da imagem em si não é modificada, aumentando a eficiência do sistema.

Além do mais, como a redução a tons de cinza diminui o número de cores na imagem para, no máximo, 256, o processo de coloração mantém esse número máximo de cores. Na prática, o número de cores é reduzido com pequena diferença perceptual entre as imagens original e colorida.

A Lâmina 13 e a Lâmina 14 apresentam dois exemplos do uso desta técnica na coloração de imagens em tons de cinza. As paletas originais e as novas são também apresentadas. No primeiro caso da Lâmina 13, a imagem original tinha 247 cores e a colorida apenas 37. No segundo caso, Lâmina 14, a redução é de 1.594 cores para apenas 61

A Lâmina 15 apresenta outros exemplos de execução do algoritmo. Todas as imagens mostradas nas Lâminas 13, 14 e 15 são texturas extraídas de documentos em true colour. Para esses experimentos, as texturas são partes não escritas de documentos selecionadas em uma janela com tamanho de 30-50% da imagem original.

A Relação Sinal-Ruído de Pico, PSNR (Peak Signal-to-Noise Ratio), entre a imagem original e a colorida é calculada pela equação 11 como:

)/255(log10 2

10 EMQPSNR = [dB] (11) onde EMQ é o Erro Médio Quadrático entre as imagens. PSNR é medido em dB (decibel), expressando, em uma escala logarítmica, diferenças de níveis de energia. Outros métodos de avaliação foram propostos, mas não implementados como, por exemplo, o PQS (Picture Quality Scale) [53]. O valor de PSNR das imagens das Lâminas 13, 14 e 15 pode ser encontrado na Tabela 10. Dessa forma, podemos fazer uma avaliação quantitativa do algoritmo.

Tabela 10. PSNR (em dB) entre a imagens originais e as versões coloridas apresentadas nas Lâminas 13, 14 e 15.

Imagens PSNR (dB) (Vermelho)

PSNR (dB) (Verde)

PSNR (dB) (Azul)

d0934-3 30 42 39 d0838 41 45 39 d0775-3 27 43 37 d0778-3 32 44 39 d0798-7 28 41 39

A técnica introduzida aqui foi testada em um conjunto de 20 diferentes classes de texturas apresentando um desempenho satisfatório tanto em nível perceptual quanto em termos quantitativos através de uma análise de PSNR. Apenas um caso foi considerado insatisfatório em uma textura com um grande número de diferentes matizes e cores. Nesse caso, quatro valores

77

diferentes de matizes se destacam, cada um aparecendo em aproximadamente 20% da imagem. Podemos observar essa textura específica na primeira linha de imagens da Lâmina 15.

Ressaltamos que o algoritmo não é aplicado à imagem em si; apenas a paleta da imagem indexada é colorida. Esse algoritmo permite que uma imagem seja armazenada em tons de cinza e apresentada ao usuário como uma imagem colorida após o processo. Uma variação dele representa um papel fundamental na próxima etapa do Projeto apresentada na próxima seção.

3.2 Geração de Texturas 2: Geração Automática de Texturas Coloridas Após a segmentação do documento, a imagem contendo apenas os pixels classificados

como papel são analisados e deles são extraídas a média e o desvio padrão dos tons vermelho, verde e azul na imagem, excluindo os pixels de cor branca. A média e o desvio padrão são utilizados na definição do espaço de cores da imagem gerada. Lembramos que, durante a segmentação, os pixels classificados como tinta são pintados de branco para gerarem a imagem só com o papel. O espaço RGB é definido, a princípio, pelos tons entre x – σ e x + σ , onde x é a média e σ é o desvio padrão. Com o objetivo de reconstruir uma versão aproximada da imagem da textura do papel é necessário encontrar um fator que decida que cores podem fazer parte da imagem ou não, dentro do espaço RGB encontrado. A solução para este problema foi encontrada observando nas texturas dos diversos tipos de papéis que um valor de matiz sempre aparece um número de vezes muito maior do que os outros valores. Esse mesmo fato foi usado anteriormente para colorir as imagens no algoritmo descrito na última seção. Chamamos esse valor de matiz de matiz_max e podemos visualizar alguns exemplos nas imagens da tabela 11. Em um conjunto de 200 texturas amostradas do acervo de Joaquim Nabuco, cada textura apresenta um valor mais freqüente de matiz que aparece, em média, em 41% dos pixels da imagem. Esse valor alcançou um mínimo de 17% e um máximo de 90%. Ou seja, há casos onde um único valor de matiz é encontrado em 90% dos pixels da imagem. A matiz, então, é a grandeza usada para definir que tons de RGB serão usados dentro do espaço possível. Resta definir o quanto cada tom deverá estar presente na imagem.

Tabela 11. Matizes mais freqüentes em amostras de texturas. Imagem Matiz_Max Freqüência testebak2 30 37,75 % teste4bak2 33 26,51 % teste5bak2 48 19,76 % teste6bak2 31 41,62 % teste7bak2 35 42,34 %

A Lâmina 16 apresenta um exemplo de um pedaço da textura de um papel através da imagem teste6bak2.bmp e as cores que podem ser formadas através de sua média, variância e o valor mais comum de matiz.

O histograma das imagens mostra que suas funções possuem características quase-gaussianas como pode ser visto na Lâmina 17. A aproximação das funções a gaussianas pode ser medida através da entropia da imagem. Quanto menor a entropia, mais a função se aproxima de uma distribuição normal [34]. Podemos calcular a entropia dos histogramas de cada tom RGB na imagem original da textura, a fim de analisarmos suas aproximações a funções normais. Calculamos também a entropia das matizes presentes na imagem, chamada h_hue. Dessa forma, teremos apenas um valor de entropia relacionado com as três componentes RGB. A tabela 12 a

78

seguir apresenta o valor de entropia encontrado para cada uma das imagens da tabela anterior. Novamente, a entropia é calculada utilizando como base logarítmica o produto das dimensões da imagem.

Tabela 12. Entropia da distribuição das matizes em amostras de texturas Imagem Entropia (h_hue) testebak2 0,169175

Teste4bak2 0,160451 Teste5bak2 0,180805 Teste6bak2 0,164334 Teste7bak2 0,113249

O valor da entropia indica o quão próxima uma distribuição está de uma função gaussiana. Se este valor for igual a zero, teremos uma distribuição normal completamente definida pela média e desvio padrão. Através da entropia, definimos uma possibilidade de aumento no valor calculado da matiz mais freqüente. São permitidos valores entre matiz_max - delta e matiz_max + delta, onde:

• Se h_hue > 0,17, então delta = 10 e

• Senão, delta = 1.

Menores entropias indicam funções mais próximas de gaussianas, tendo, assim, menor variação. O valor limitante de 0,17 foi encontrado através de experimentos, observando as entropias das imagens e as variações de matizes encontradas nas mesmas. Criamos aqui um espaço de matizes permitidas na imagem final a ser reconstruída.

Em seguida, procedemos com a criação de funções quase-gaussianas para os histogramas dos tons RGB dadas suas médias e desvios-padrão. As funções criadas devem ser ajustadas posteriormente para que possam cobrir toda a imagem, afinal, a soma total das amplitudes do histograma deve ser igual ao número de pixels da imagem. Limitada a média e o desvio-padrão, a gaussiana criada pode gerar um diferente número de pixels. A fim de ajustar melhor os histogramas, permitimos uma variação no espaço RGB criado que agora passa a conter os tons

entre os valores x ± fator*|variância|, onde |variância| corresponde ao valor adimensional da variância. A variável fator é calculada através de um processo iterativo definida para cada tom quando a soma das amplitudes do histograma do tom for maior ou igual ao número de pixels na imagem ou se aproximar a até 20% deste valor. Neste último caso, uma correção é feita posteriormente no histograma acrescentando o número de pixels que faltam. Um valor de fator é determinado para cada tom RGB, podendo ser diferente para cada um. fator é limitada por três vezes o desvio padrão, impedindo, assim, que a variável cresça indefinidamente.

A definição do espaço de cores agora é determinada pelo valor da variância e não mais pelo desvio padrão. Como as funções dos histogramas não são gaussianas exatas, o uso da variância criou gráficos mais aproximados do original, tendo como resultado imediato uma gaussiana com uma elevação na amplitude do ponto médio, “esticando” o centro da gaussiana, como pode ser exemplificado na Figura 41.

79

Figura 41. Gaussiana modificada com uso da Variância ao invés do Desvio Padrão. Construídos os histogramas, obtém-se a quantidade de cada tom RGB que estará presente

na imagem e como combiná-los nas cores formadoras do espaço de matizes. A entropia das matizes também é usada para definir quantas vezes acessaremos o espaço

de matiz definido para colher tons RGB para a imagem. Uma análise das tabelas 11 e 12 anteriores sugere uma relação entre a entropia e o número de vezes que a entropia mais freqüente aparece em uma imagem. Uma função de primeira ordem foi então ajustada para definir um valor aproximado para o número de vezes que usaremos as cores definido pelo espaço de matizes:

0089.16_*64.152__ += huehcoresdenúmero

Funções de graus maiores foram testadas sem alcançar melhores resultados. O restante da imagem é preenchido com combinações dos tons do espaço RGB definido, mesmo não gerando matiz_max. Por fim, definimos as cores dos pixels da imagem fazendo buscas pseudo-aleatórias no espaço de matriz e, posteriormente, no espaço RGB, seguido de um embaralhamento na imagem. A imagem final é gerada através dos valores de média e desvio-padrão dos tons RGB, a matiz mais freqüente e a entropia das matizes da imagem original. Armazenadas em um arquivo binário, essas informações ocupam apenas 40 bytes, ressaltando-se que é preciso armazenar também as dimensões da imagem original. Pode-se ver, a seguir, nas Lâminas 18, 19, 20, 21 e 22, alguns exemplos do resultado da aplicação do algoritmo gerando texturas.

Em [9], Campisi, Hatzinakos e Neri sugerem um método para síntese de texturas em tons de cinza usando um sistema de excitação linear com Transformada de Wavelet Binária em cascata com um equalizador de histograma. A criação automática de uma textura é uma técnica mais complicada que a coloração. No momento, concentramo-nos na definição do espaço de cores onde a textura está inserida.

O algoritmo definido foi implementado e testado em um conjunto de 200 texturas como analisado a seguir.

80

3.2.1 Análise das Texturas Sintéticas As 200 texturas geradas foram analisadas e comparadas com as texturas originais por

inspeção visual e alcançaram resultados satisfatórios. Além disso, dois métodos de análise quantitativos foram aplicados: o cálculo da Razão Sinal-Ruído de Pico (PSNR, definida na equação 15) e o método estatístico de Análise de Variância (ANOVA - Analisys of Variance) [41]. A PSNR e o Erro Médio Quadrático (EMQ) foram calculados para cada tom RGB no conjunto de 200 texturas sintéticas geradas. As texturas foram extraídas de um conjunto de 200 imagens representativas do Acervo de Joaquim Nabuco.

Os valores médios para o PSNR e EMQ para cada tom RGB pode ser visto na tabela 13 a seguir.

Tabela 13. Valor médio da Relação Sinal-Ruído de Pico (PSNR) e do Erro Médio

Quadrático (EMQ) para um conjunto de 200 texturas geradas automaticamente. PSNR (dB) EMQ

Vermelho 42,18 4,65 Verde 40,90 5,59 Azul 41 5,45

A Análise de Variância (ANOVA) foi introduzida por R.A.Fisher [41] como um

procedimento para controlar a taxa de erro Tipo I (incorreta rejeição de uma hipótese nula quando ela é verdadeira) sempre que aplicado a comparação de dois ou mais grupos em experimentos. A hipótese nula sugere que as variâncias dos dois grupos testados são iguais; uma hipótese alternativa (hipótese 1, por exemplo) define que as variâncias são diferentes. Assim, a ANOVA é utilizada para avaliar se grupos são diferentes baseando-se em alguma medida característica. A estatística F (F de Fisher) é usada para implementar um teste de hipótese para definir se a hipótese nula é verdadeira. A ANOVA retorna o valor-p para esse teste, através de uma consulta a uma tabela da distribuição F.

Uma Análise de Variância foi aplicada com média, desvio padrão, assimetria, curtose e entropia de cada componente RGB como variáveis dependentes, tipo de imagem como variável independente e p < 0,05. Nesse contexto, tipo de imagem, refere-se à origem da amostra da imagem: da textura original ou da sintética. O valor de p < 0,05 diz que o valor calculado da estatística F para a ANOVA supera o valor crítico de F com p = 0,05, indicando que uma rejeição da hipótese nula é associada com um erro de probabilidade de Tipo I menor que 0,05. O valor da variável p é escolhido pelo usuário, sendo normalmente igual a 0,05 ou 0,01. A Análise de Variância foi executada pelos softwares StatView e MatLab, apresentando os mesmos resultados em ambos.

Assim, se o valor do teste F, encontrado na tabela da distribuição, for menor que p, temos diferenças significativas entre as amostras. No caso em análise, a hipótese nula corresponde à imagem original ser estatisticamente igual à imagem sintética e a hipótese 1, contrária, refere-se às duas imagens serem estatisticamente diferentes.

Testes post hoc revelaram que a média e a entropia dos dois tipos de imagens não apresentam diferenças estatisticamente significantes. Uma análise do desvio padrão apresentou diferenças significativas porque os ruídos de alta-freqüência da imagem original não estão presentes na imagem gerada.

Os testes de Análise de Variância descritos foram divididos em dois experimentos. Na primeira, as texturas foram separadas em duas classes, tomando como base a imagem original: texturas com muito ou pouco ruído. Considera-se, no caso, ruído a presença de grandes concentrações de pixels com matiz diferente de matiz_max espalhados por toda a imagem. Podemos ver alguns exemplos de texturas com ruídos na Figura 42 a seguir. Nesse experimento, foram utilizadas 23 texturas com ruído e 177 sem ruído. A segunda fase, a ANOVA foi aplicada

81

ao conjunto total de texturas sem distinção. Os resultados da ANOVA podem ser vistos a seguir. Observa-se que a notação F(X) indica com quantos X graus de liberdade determina-se a forma da função de Fisher . Para a ANOVA, conclui-se que as imagens em análise possuem diferenças estatisticamente Não-Significativas (NS) ou Significativas (S). Apresentam-se,a seguir, os resultados em cada experimento, conseguidos utilizando o software StatView.

Figura 42. Texturas consideradas com ruído em experimento com ANOVA.

Primeiro Experimento: Texturas divididas em dois grupos: com ou sem ruído.

ANOVA para Entropia

Tom Tipo de Imagem F(X) p Conclusão Com Ruído F(1) = 0,286 0,5954 NS Vermelho Sem Ruído F(1) = 2,361 0,1254 NS Com Ruído F(1) = 1,188 0,2820 NS Verde Sem Ruído F(1) = 2,599 0,1080 NS Com Ruído F(1,44) = 3,759 0,059 NS Azul Sem Ruído F(1,298) = 3,101 0,0739 NS

ANOVA para Média

Tom Tipo de Imagem F(X) p Conclusão Com Ruído F(1) = 0,005 0,9436 NS Vermelho Sem Ruído F(1) = 0,027 0,8702 NS Com Ruído F(1) = 0,063 0,8031 NS Verde Sem Ruído F(1) = 21,957 <0,0001 S Com Ruído F(1) = 0,01 0,9212 NS Azul Sem Ruído F(1) = 0,023 0,8783 NS

ANOVA para Desvio Padrão

Tom Tipo de Imagem F(X) p Conclusão Com Ruído F(1) = 0,313 0,5789 NS Vermelho Sem Ruído F(1) = 4573 0,0333 S Com Ruído F(1) = 0,02 0,8871 NS Verde Sem Ruído F(1) = 0,045 0,8316 NS Com Ruído F(1) = 0,544 0,4647 NS Azul Sem Ruído F(1) = 2,418 0,1210 NS

82

Segundo Experimento: Um só conjunto de texturas sem separar as com ruído.

Resultados da ANOVA Medição Tom F(X) p Conclusão

Vermelho F(1) = 76,15 <0,0001 S Verde F(1) = 324,268 <0,0001 S

Entropia

Azul F(1) = 328,928 <0,0001 S Vermelho F(1) = 0,034 0,8535 NS

Verde F(1) = 0,025 0,8742 NS

Média Azul F(1) = 0,054 0,8168 NS

Vermelho F(1) = 116,051 <0,0001 S Verde F(1) = 5,6967 0,0175 NS

Desvio Padrão

Azul F(1) = 4,6775 0,0312 NS

Observa-se que, se analisarmos um grupo só sem separar as imagens com ruído, existem diferenças significantes em muitas das variáveis medidas (apenas a média não apresenta tal comportamento). Este fato é esperado já que o ruído na textura original não aparece na textura sintética o que provoca muitas variações locais, afetando bastante o desvio padrão.

Além do primeiro e segundo momentos (média e variância, respectivamente), já analisados, aplicamos uma ANOVA a assimetria e a curtose, já que esses momentos também são medidas comuns para analisar texturas [64][80]. Foram encontradas diferenças estatisticamente significativas apenas para a Assimetria dos histogramas dos tons Verde e Azul, considerando, novamente, dois grupos de imagens (com ou sem ruído). As medidas para os outros histogramas, segundo a ANOVA, não apresentam diferenças significativas.

Novamente, dois experimentos foram feitos: um com duas classes de imagens (com ou sem ruído) e outro com toda a base.

Primeiro Experimento: Texturas divididas em dois grupos: com ou sem ruído.

ANOVA para Assimetria Tom Tipo de Imagem F(X) p Conclusão

Com Ruído F(1) = 0,0810 0,7768 NS Vermelho Sem Ruído F(1) = 5,2609 0,0225 NS Com Ruído F(1) = 28,9604 8,32e-7 S Verde Sem Ruído F(1) = 0,215 0,6432 NS Com Ruído F(1) = 29,9607 5,75e-7 S Azul Sem Ruído F(1) = 46,7943 4,34e-11 S

ANOVA para Curtose

Tom Tipo de Imagem F(X) p Conclusão Com Ruído F(1) = 1,1742 0,2821 NS Vermelho Sem Ruído F(1) = 4,9346 0,0271 NS Com Ruído F(1) = 0,2273 0,6349 NS Verde Sem Ruído F(1) = 0,0577 0,8103 NS Com Ruído F(1) = 0,7505 0,3891 NS Azul Sem Ruído F(1) = 3,3962 0,0663 NS

83

Segundo Experimento: Considerando todo o conjunto de texturas

Resultados da ANOVA Medição Tom F(X) P Conclusão

Vermelho F(1) = 5,2375 0,0227 NS Verde F(1) = 0,201 0,6545 NS

Assimetria

Azul F(1) = 52,8704 3,21e-6 S Vermelho F(1) = 4,9143 0,0273 NS

Verde F(1) = 0,0675 0,7952 NS

Curtose Azul F(1) = 4,139 4,1139 NS

Outra análise dos resultados foi feita utilizando Matriz de Co-Ocorrência de Tons de Cinza (Grey Level Co-Occurrence Matrix - GLCM) [64]. Uma GLCM contém informações sobre a posição dos pixels com tons de cinza semelhantes. No nosso caso, utilizamos a técnica para cada componente RGB da imagem. Como temos 256 diferentes variações possíveis para cada tom, formaremos uma família de matrizes de 256x256 elementos, onde, cada posição (i,j) da matriz indica quantas vezes a cor i e a cor j apareceram separadas de uma distância d em uma direção definida (horizontal, vertical ou diagonal). Por exemplo, seja M a matriz GLCM, a posição M(i,j) contém o número de pixels P1 e P2 na Imagem, no qual P1 tem cor i e P2 tem cor j, e P1 e P2 estão separados de uma distância d em alguma direção. Os índices para a matriz M correspondem a níveis de um dado tom, não linhas ou colunas da imagem. Assim, o conceito de GLCM foi adaptado para ser aplicado a cada tom RGB nas imagens das texturas originais e sintéticas. Calculadas as matrizes, fazendo uma leitura horizontal e utilizando uma distância igual a 2 (explicado posteriormente), aplicamos novamente a ANOVA para as propriedades desvio padrão, curtose, assimetria, energia, contraste e homogeneidade. Em relação à GLCM, outros três parâmetros comuns no estudo de texturas [28][29][30][31] foram calculados nas imagens geradas: energia, contraste e homogeneidade:

��=i j

jiglcmEnergia ),(2

�� −=i j

jiglcmjiContraste ),(.)( 2

�� −+=

i j jijiglcm

adeHomogeneid||1),(

onde glcm(i,j) corresponde ao valor da GLCM na posição (i,j). O Contraste como calculado quantiza o valor esperado da diferença entre 2 pixels. A homogeneidade mede o quão próximo da diagonal principal estão os maiores valores de cor.

Os resultados estão apresentados abaixo, calculados usando o software MatLab:

Resultados da ANOVA Medição Tom F(X) p Conclusão

Vermelho F(1) = 28,32 1,804e-7 S Verde F(1) = 2,57 0,1096 NS

Desvio Padrão

Azul F(1) = 4,57 0,0332 NS Vermelho F(1) = 6,14 0,013 NS

Verde F(1) = 1,91 0,168 NS

Assimetria Azul F(1) = 2,15 0,143 NS

Vermelho F(1) = 10,9 0,001 NS Verde F(1) = 3,79 0,052 NS

Curtose

Azul F(1) = 4,44 0,036 NS

84

Vermelho F(1) = 24,70 0,000001 S Verde F(1) = 0,00011 0,9915 NS

Energia

Azul F(1) = 2,56 0,1105 NS Vermelho F(1) = 18,25 0,000025 S

Verde F(1) = 78,18 0 S

Contraste Azul F(1) = 69,49 1,665e-15 S

Vermelho F(1) = 0,18 0,6736 NS Verde F(1) = 129,36 0 S

Homogeneidade

Azul F(1) = 149,4 0 S

O desvio padrão e energia histograma do tom de vermelho, assim como o contraste do histograma dos três tons e a homogeneidade dos histogramas dos tons verde e azul apresentaram diferenças significativas. A distância de 2 foi escolhida por representar um valor razoável de similaridade entre os pixels. O mesmo teste foi executado fazendo uma varredura vertical na imagem para gerar a GLCM para distância de 2, apresentando diferenças significativas para os parâmetros de contraste e homogeneidade para os histogramas dos três tons RGB.

Foram geradas também as GLCM’s para as distâncias de 3 e 5 com varredura horizontal e vertical. Resumidamente, novamente as maiores diferenças foram encontradas quanto ao contraste e homogeneidade dos histogramas das três componentes Vermelho, Verde e Azul, assim como para o desvio padrão do histograma do tom vermelho.

Os resultados do algoritmo apresentados nesta seção superaram o da seção anterior (onde é feita a coloração da textura em tons de cinza). Além dos resultados serem melhores (quantitativamente), o processo automático reduz mais ainda a quantidade de informação necessária para gerar a textura. Antes, era preciso ter a imagem original em tons de cinza e um arquivo em binário com dados sobre a coloração. Agora, somente um arquivo binário de 40 bytes é necessário.

3.3 Conclusão Foi apresentada, nesse capítulo, uma análise das texturas das imagens de papéis de cartas e documentos históricos. Através dessa análise novos algoritmos para geração automática de texturas foram propostos e analisados. Os primeiros algoritmos tratam do preenchimento dos “buracos” da imagem gerados pelo algoritmo de segmentação apresentado no capítulo anterior. Tais algoritmos trabalham com imagens em tons de cinza e usam informações sobre matiz para colorir tal imagem, resultando em uma imagem colorida perceptualmente similar à original. Um algoritmo para completa geração automática da textura também é apresentado onde informações estatísticas e de matiz da imagem original são armazenadas em um arquivo para binário. O algoritmo foi aplicado em um conjunto de 200 imagens e os resultados finais foram analisados qualitativamente, segundo inspeção visual, e quantitativamente, segundo o cálculo de PSNR e testes de ANOVA. A criação automática de texturas é parte fundamental de um sistema para síntese das imagens de documentos históricos. Dentro dos principais objetivos do Projeto Nabuco, lembramos que está a divulgação do acervo de cartas e documentos. Uma forma de difundir o acervo é a diminuição da quantidade de bytes necessários para sua transmissão via Internet. Como a síntese da textura pode ser feita com um arquivo binário de apenas 40 bytes, vamos analisar a seguir a composição dessa textura com a parte textual do documento.

85

4

Geração Automática de Imagens de Documentos Históricos

Como já mencionamos, as cartas e documentos do acervo de Joaquim Nabuco possuem características bastante peculiares, em particular, as cartas datilografadas. A grande maioria das cartas foi escrita em uma mesma máquina. As condições sociais da época faziam disso uma situação normal. As pessoas dispunham de uma única máquina de escrever e transportavam-na consigo em suas viagens. Isso pôde ser constatado através de informações de historiadores e também através da análise dos documentos de Joaquim Nabuco. A Figura 43 abaixo, por exemplo, apresenta quatro extrações da letra u de quatro cartas escritas em épocas diferentes entre 1882 e 1888. Podemos notar uma falha no lado superior direito da letra presente em todas as amostras das quatro cartas. Isto confirma, com grande probabilidade, nossa informação de que a máquina usada foi a mesma em todo esse período na maioria das cartas escritas por Joaquim Nabuco.

Figura 43. Amostras de letras u retiradas de diferentes cartas entre 1882 e 1888.

A fim de proceder com a geração da imagem do documento, definimos dois possíveis

caminhos. Ambos os processos utilizam a textura sintética gerada como definido no Capítulo anterior. A diferença entre os métodos está na imagem textual utilizada. O primeiro método usa a imagem textual resultante do novo algoritmo de segmentação descrito no Capítulo 2 em composição com a textura sintética e pode ser aplicado tanto a imagens de documentos manuscritos quanto para documentos datilografados. Em um segundo método, um arquivo de texto é gerado por uma ferramenta de OCR a partir de imagens de documentos datilografados. Informações da carta são inseridas no arquivo texto que, junto com os dados da textura serão utilizadas para sintetizar o documento completo automaticamente. Neste caso, restringimo-nos ao uso de documentos datilografados apenas e um conjunto base de imagens de caracteres é usado para re-construir a imagem textual do documento a partir do arquivo de texto. Analisaremos, a seguir, cada um desses processos.

Capítulo

86

4.1 Geração por Composição de Imagens Parte final deste projeto e junção de todas as outras, o sistema de geração automática de

imagens busca alcançar altas taxas de compressão com perda para a divulgação do acervo de Joaquim Nabuco. O sistema trabalha em dois níveis: primeiro, a reconstrução de um documento através da criação automática da textura e de uma posterior adição da imagem do texto gerada pelo algoritmo de segmentação apresentado no capítulo anterior. Como descrito, este processo pode ser implementado tanto em imagens de documentos manuscritos quanto em textos datilografados.

A Figura 44 mostra a configuração completa do sistema para geração de imagens coloridas de cartas e documentos datilografados ou manuscritos a partir da imagem textual. Como primeiro passo, a imagem digitalizada do documento é segmentada através do algoritmo de segmentação apresentado no Capítulo 3 a fim de separar as imagens do papel e da tinta. As imagens geradas do texto e do papel são usadas então na formação de dois arquivos de dados: o primeiro, referente à imagem do papel, será usado na geração da textura sintética; o segundo, referente à imagem textual, será usado posteriormente na sua coloração. Tais conjuntos de dados foram descritos nas seções 3.1.3 e 3.2 e correspondem a média e desvio padrão dos histogramas dos tons RGB, o valor de matiz mais freqüente na imagem, a entropia das matizes e as dimensões da imagem, perfazendo um total de 40 bytes.

Figura 44. Configuração para geração automática de documentos utilizando

a imagem da parte referente a tinta adicionada a textura gerada. Como a imagem textual gerada pela segmentação possui grandes áreas com uma única cor

(o branco – presente onde antes havia a textura do papel) é razoável utilizarmos algum formato de armazenamento que se valha de tal característica. Além disso, não há grande variação nos tons de vermelho, verde e azul presentes (comprovado pelo valor do desvio padrão das imagens textuais sempre próximo de zero). Assim, o algoritmo Lempel-Ziv-Welch [86] presente no formato GIF é escolhido para armazenar as imagens textuais. Como esse formato é restrito ao armazenamento de imagens com 256 cores, converteremos a imagem textual original para tons de cinza antes de procedermos com a conversão para o novo formato.

Quanto à textura, como apresentado no Capítulo 3, apenas o arquivo binário de dados precisa ser armazenado a fim de gerar a imagem da textura. Na geração da imagem do documento, a imagem da textura do papel é criada em dimensões menores que a carta original

87

por questões de eficiência, sendo então repetida para criar a imagem com as dimensões da imagem textual correspondente. Utilizando o algoritmo de coloração por matiz descrito na seção 3.1.3, a imagem textual é colorida e a textura sintética é adicionada, criando a imagem final gerada com 16 milhões de cores.

Uma pequena variação se faz necessária quanto ao algoritmo de coloração apresentado anteriormente quando aplicado às imagens textuais. No caso dos caracteres de texto, pouca diferença existe nas cores de seus pixels. Assim, em todos os casos testados, o desvio padrão apresentou valor igual ou próximo a zero. Se aplicado da forma previamente apresentada, o algoritmo de coloração não provocará mudanças na nova paleta de cores gerada. Por esse motivo, o valor do desvio padrão é acrescido de 5. O valor mínimo de desvio padrão 5 foi considerado ótimo em testes realizados nos quais foram avaliados o tempo de processamento e a qualidade final da imagem. Valores maiores provocaram aumentos significativos no tempo de execução do algoritmo sem, no entanto, aumentar proporcionalmente a qualidade da imagem colorida. Com o valor definido, permitimos mudanças na paleta sem alterar muito a característica da imagem de não apresentar grandes variações entre as cores da tinta.

A lâmina 23 apresenta em detalhes todo este processo, mostrando as imagens geradas passo-a-passo. A mesma imagem apresentada nessa lâmina é vista em destaque na lâmina 24.

Tal algoritmo foi testado em um conjunto de 200 imagens de documentos datilografados e os histogramas dos tons RGB foram analisados pelo método de Análise de Variância (ANOVA), descrito no Capítulo anterior, quanto a média, desvio padrão, curtose e assimetria. Os resultados, gerados pelo software MatLab, podem ser vistos abaixo:

Resultados da ANOVA

Medição Tom F(X) p Conclusão Vermelho F(1) = 0,5376 0,4666 NS

Verde F(1) = 0,0961 0,7577 NS

Média Azul F(1) = 0,000073 0,9786 NS

Vermelho F(1) = 0,0631 0,8026 NS Verde F(1) = 0,3676 0,5469 NS

Desvio Padrão

Azul F(1) = 6,7206 0,0122 NS Vermelho F(1) = 1,1976 0,2787 NS

Verde F(1) = 4,8836 0,0314 NS

Assimetria Azul F(1) = 6,9787 0,0108 NS

Vermelho F(1) = 1,4943 0,2269 NS Verde F(1) = 2,5205 0,1182 NS

Curtose

Azul F(1) = 2,3709 0,1259 NS Como antes, F(X) é a função de Fisher, NS indica diferenças estatisticamente não-significativas e S indica que houve diferenças estatisticamente significativas. Assim, diferenças estatisticamente significantes não foram encontradas em nenhum dos parâmetros analisados. Quanto a taxa de compressão, como dito na Introdução desta tese, as imagens originais dos documentos são armazenadas no formato JPG com 1% de perda, conforme testes e avaliação da razão perda/qualidade realizados por especialistas em documentos.

A imagem segmentada contendo a parte referente ao texto, porém, é armazenada no formato GIF, como definido anteriormente. Como justificado, a escolha do formato GIF deve-se ao fato dele implementar em seu núcleo o algoritmo de Lempel-Ziv-Welch que alcança melhores resultados em imagens com grandes áreas com uma só cor. Para as imagens textuais, o formato JPG apresentou resultados piores do que o GIF, justificando, assim, a troca de formato para o uso do algoritmo aqui descrito. Mesmo adicionando os tamanhos dos arquivos binários necessários para coloração e geração da textura sintética (40 bytes cada), o uso da imagem GIF gera uma

88

maior taxa de compressão. As imagens originais armazenadas em formato JPG com 1% de perda ocupam, em média, 378 Kbytes; já as imagens textuais em formato GIF mais os arquivos de dados ocupam, em média, 175 Kbytes. Isso denota uma melhora de cerca de 46%, em média. Convidamos o leitor a observar nas lâminas 24, 25 e 26 alguns dos resultados obtidos pelo método descrito nesta seção.

4.2 Geração Completa Para a completa geração do documento, incluindo a imagem textual e a textura, criamos

uma base de caracteres extraídos das imagens dos documentos. Nessa fase, dependemos de uma resposta eficiente das ferramentas de OCR e, por isso, restringiremos o método a documentos datilografados. Como analisado no Capítulo 1, estaremos usando o OmniPage como ferramenta de apoio.

O conteúdo dessa seção foi aceito para publicação em anais no artigo [44]: • Generation of Images of Historical Documents by Composition, Carlos A.B.Mello e

Rafael D.Lins, Vision Interface 2002, Calgary, Canadá, maio/2002.

4.2.1 Caracterização da Base de Imagens da Fonte Um conjunto de imagens de caracteres foi extraído das imagens segmentadas,

constituindo um conjunto fonte. Esse foi determinado tomando por base amostras de imagens de cada caractere (incluindo, letras, números, acentos, pontuação, símbolos, etc.). O número de amostras variou conforme o caractere. Existem caracteres que não são tão freqüentes na língua corrente nos documentos e, por isso, são mais difíceis de encontrar grandes números de amostras com diferenças significativas. Podemos facilmente exemplificar esse fato com o símbolo “%” encontrado em apenas uma carta.

Foram colhidas diversas amostras de cada caractere (um número variável de amostras para cada um, como explicado anteriormente) a partir da imagem textual em tons de cinza gerada pelo novo algoritmo de segmentação. Essas amostras, com dimensões, iguais foram usadas para gerar um elemento gráfico único para cada caractere. É feita uma análise pixel-a-pixel de cada amostra. Se os pixels têm a mesma cor, ela é repetida no novo elemento. Se as cores são diferentes, observa-se se há a predominância de alguma cor. Se houver, esta será a cor utilizada no elemento único; caso contrário, uma média das cores é calculada.

Cada amostra foi padronizada segundo as seguintes características: • As letras (maiúsculas e minúsculas), números e símbolos de pontuação são enquadrados

em molduras de 22x31 pixels. Alguns símbolos especiais ocupam uma área maior (como “%”, “(“ e “)”).

• Os caracteres são armazenados em 256 tons de cinza para permitir uma posterior coloração;

• As letras minúsculas são separadas em três grupos: largas (m e w), baixas (g, p, q, y e ç) e as normais (as demais letras). De acordo com essa classificação, as letras normais possuem um espaçamento de três pixels na lateral esquerda e seis pixels abaixo; as letras largas não possuem espaçamento nas laterais, ocupando todos os 22 pixels de largura da caixa; e o espaçamento inferior nas letras baixas é de apenas um pixels.

• Optamos por armazenar os caracteres acentuados ao invés de armazenar os acentos e plotar a acentuação em cima da letra (como uma máquina de escrever) por questões de eficiência;

• Caso seja encontrado algum símbolo que não esteja no fonte, a imagem de um “*” será colocada no lugar e um arquivo de erro é gerado com o símbolo desconhecido. Exemplos de alguns símbolos podem ser vistos em destaque na Figura 45. Uma amostra

da maioria dos símbolos da base é encontrada na Figura 46.

89

Figura 45. Exemplos de imagens de caracteres extraídos dos documentos para gerar fonte.

Primeira linha: Caracteres normais (minúsculos e maiúsculos); Segunda linha: Caracteres largos (m e w) e Símbolo Especial (%); Terceira linha: Caracteres baixos (p e q) e Símbolo

‘*’ usado para indicar um caractere desconhecido para a fonte.

90

Figura 46. Parte da base de caracteres usada na geração automática da imagem textual.

Quanto aos documentos, alguns parâmetros foram definidos e tomados por padrão:

• Margem esquerda = 150 pixels; • Margem superior = 75 pixels; • Espaço em branco = 24 pixels; • Espaçamento entre linhas = 70 pixels; • Tabulação = 4 espaços em branco.

Como o espaçamento entre linhas varia em alguns casos, utilizamos como critério de

variação o número de caracteres da carta. Cartas longas (arquivos de texto com mais de 1.000 caracteres), em geral, possuem um espaçamento menor entre as linhas. Nesses casos, esse espaçamento passa a ser de 40 pixels. Por segurança, analisamos também se o tamanho da linha gerada ultrapassa as dimensões da imagem. Isso é possível, pois variações podem surgir nos parâmetros acima definidos. Nesses casos, os espaços em branco diminuem para 20 pixels.

Esses parâmetros foram aplicados em um conjunto de 30 imagens geradas, apresentando resultados satisfatórios.

4.2.2 Processo de Geração da Imagem O processo de geração automática da imagem do documento pode ser dividido em duas

fases: a primeira, referente à geração dos dados da imagem e a segunda, à sua reconstrução. Nesse momento, faz-se necessário re-apresentar nas Figuras 47 e 48 os esquemas mostrados anteriormente na Figura 3 com as duas fases necessárias à geração da imagem sintética do documento.

91

Figura 47. Processo de geração da imagem de um documento histórico.

Primeira Fase: Criação dos arquivos de dados e do arquivo de texto com o conteúdo da carta.

b)

Figura 48. Processo de geração da imagem de um documento histórico. Segunda Fase: Geração da imagem a partir dos arquivos de dados e de texto.

Na primeira fase, a fim de que os dados necessários à geração da imagem sejam criados é

preciso primeiro segmentá-la de acordo com o novo algoritmo apresentado no Capítulo 2. Como na seção anterior, são extraídos das imagens do papel e do texto dois arquivos binários de dados, descritos nas seções 3.2 e 3.1.3. Os dados da imagem do papel são usados para gerar a textura sintética e os dados da imagem textual são usados para colorir a imagem de texto gerada. Diferentemente da seção anterior, no entanto, o texto também será gerado automaticamente.

A imagem textual do documento segmentado é inserida em uma ferramenta de OCR. O arquivo texto gerado é então armazenado juntamente com os arquivos binários de dados da textura e da tinta. São esses os arquivos necessários para o sistema de criação da imagem do documento.

Na segunda etapa do sistema, uma imagem em branco é criada com as dimensões da carta armazenadas no arquivo de dados da imagem textual. Em seguida, os parâmetros de margem e espaçamentos são definidos como descrito anteriormente formando uma moldura onde serão colocadas as imagens dos caracteres. Cada caractere do arquivo texto é lido, convertido para

92

imagem através da fonte definida e posicionado na imagem em branco, observando espaçamento e quebras de linha. Construída toda a imagem do texto, o sistema prossegue com a coloração da paleta, usando o arquivo binário da imagem textual original (gerada após a segmentação) e a variação quanto ao desvio padrão apresentada na seção anterior.

Definida a imagem textual, o sistema cria a textura sintética conforme demonstrado na seção 3.2 e distribui essa textura, repetindo seu padrão pela parte branca da imagem textual gerada. O processo corresponderia a transformar a cor branca de fundo da imagem textual em uma cor transparente e sobrepô-la à imagem ao papel gerado. Toda a área branca é substituída pela textura do papel.

O resultado da síntese completa do documento apresentado na Figura 1 pode ser visto na Figura 49 a seguir.

Figura 49. Geração automática da imagem do documento da Figura 1.

93

A lâmina 27 apresenta os arquivos gerados em cada passo desse processo, partindo da imagem do documento D0765 original até a imagem final gerada. A lâmina 28 apresenta as imagens do mesmo documento em detalhes. Outros exemplos da aplicação do algoritmo podem ser vistas nas lâminas 29, 30, 31 e 32.

Novamente, um conjunto de 30 imagens foi testado e teve seus histogramas analisados segundo o método de Análise de Variância:

Resultados da ANOVA Parâmetro Tom F(X) p Conclusão

Vermelho F(1) = 0,28 0,5989 NS Verde F(1) = 0,0261 0,8722 NS

Média

Azul F(1) = 0,091 0,7641 NS Vermelho F(1) = 0,0415 0,8393 NS

Verde F(1) = 0,0649 0,8 NS

Desvio Padrão Azul F(1) = 0,2065 0,6514 NS

Vermelho F(1) = 1,694 0,1988 NS Verde F(1) = 11,6766 0,0012 S

Assimetria

Azul F(1) = 28,0239 2e-7 S Vermelho F(1) = 0,6853 0,4116 NS

Verde F(1) = 8,6822 0,0048 S

Curtose Azul F(1) = 14,7128 0,000034 S

Assim, foram detectadas diferenças estatisticamente significativas apenas quanto a curtose

e assimetria dos histogramas dos tons verde e azul. Para as outras medidas analisadas, as diferenças são consideradas estatisticamente não-significativas.

Não aplicaremos aqui o método de PSNR (Razão Sinal-Ruído de Pico) por este ser um algoritmo de análise pixel-a-pixel. A imagem gerada apresenta diferenças na posição do texto em relação a imagem do documento original o que provocaria resultados quantitativamente insatisfatórios da PSNR sem, no entanto, poder gerar uma avaliação qualitativa precisa.

Em termos de taxas de compressão, o sistema descrito nesta seção apresenta resultados altamente satisfatórios já que apenas o arquivo texto com o conteúdo da imagem do documento e os dois arquivos binários de dados são necessários para a geração da imagem. Os arquivos de texto têm cerca de 1 Kbyte, mesmo tamanho, aproximadamente, dos dois arquivos binários (40 bytes cada). Assim, 2 Kbytes apenas são necessários para geração completa de uma versão aproximada da imagem do documento. Todo o sistema e a base de fontes pode ser transferido uma única vez pela Internet para o usuário. A partir de sua instalação, bastaria apenas o usuário transferir os arquivos de texto e os arquivos binários de dados.

Como uma aplicação prática, podemos citar a apresentação dos documentos do acervo de Joaquim Nabuco na Internet. Um pesquisador pode acessar o documento datilografado de duas formas: através do arquivo texto gerado pelo OCR (podendo, assim, ler todo o conteúdo da carta) ou através da imagem reconstituída da carta. Nesse segundo caso, é possível apresentar a carta em monocromático, em tons de cinza ou colorida, com ou sem o fundo referente ao papel.

4.3 Conclusão Foi apresentado neste Capítulo um sistema para geração automática com perdas da

imagem de documentos do acervo de Joaquim Nabuco. Duas formas de geração são possíveis. Na primeira, usa-se a imagem textual gerada pelo novo algoritmo de segmentação apresentado no Capítulo 2. Tal imagem, armazenada no formato GIF e em tons de cinza, é colorida segundo uma variação no algoritmo proposto na seção 3.1.3 e tem sua textura sintetizada conforme descrito na

94

seção 3.2 e adicionada a imagem textual. Em relação ao formato JPG com 1% de perda utilizado hoje em dia no projeto, a nova técnica apresentada usando composição de imagens traz um ganho de mais de 50% na taxa de compressão, gerando imagens com diferenças estatisticamente não-significantes quanto a diversos parâmetros de medições.

A segunda técnica, busca a geração total da imagem, incluindo a parte referente ao texto. Para tanto, uma base de imagens de caracteres foi criada e armazenada em tons de cinza. Uma ferramenta de OCR converte a imagem do documento datilografado original em texto o qual tem cada caractere convertido para imagem segundo essa base. Tal imagem é colorida e tem sua textura sintética criada e adicionada ao fundo do papel. Mais eficiente em termos de taxa de compressão que o método apresentado anteriormente, tal técnica precisa apenas de 2 Kbytes para cada documento do acervo a fim de re-criar uma versão aproximada da imagem original. Novamente, a técnica de ANOVA não apresentou diferenças estatisticamente significantes entre as imagens geradas e as imagens originais.

Em termos de inspeção visual, as imagens geradas pelas duas técnicas são nitidamente diferentes. A imagem sintética ainda não consegue representar ruídos presentes e comuns nas imagens originais. No entanto, com o intuito de prover um sistema que permita uma fácil divulgação de qualquer acervo de documentos, os métodos aqui apresentados conseguem alcançar resultados bastante satisfatórios.

Testes foram feitos utilizando uma base de caracteres armazenadas em apenas duas cores, mas os resultados não foram satisfatórios, apresentando diferenças significativas estatisticamente. Nesse caso, após a imagem textual ser adicionada à textura, um filtro passa-baixa é aplicado a fim de suavizar as fronteiras entre a tinta e o papel.

Nos dois algoritmos apresentados, o tempo de processamento não foi analisado. Em ambos, o fator determinante é a geração da textura cujo tempo de execução é função do valor do desvio padrão dos tons RGB. Na maioria dos casos, dadas as características das cores mais freqüentes no papel das cartas, o desvio padrão do azul apresenta um valor mais baixo em relação ao dos outros componentes. Nos dois casos, ainda é feita a coloração da imagem textual, mas tal algoritmo, por ser aplicado apenas à paleta de cores da imagem, não tem grande influência no tempo total do processamento. No algoritmo de geração completa, é necessário a criação da imagem textual, processo ao qual também não tem grande parcela no tempo de processamento do algoritmo. A maior influência no tempo total para geração da imagem sintética é a criação da textura como dito anteriormente.

95

Conclusões e Trabalhos Futuros

Destacamos aqui a originalidade do trabalho apresentado e seu potencial com inúmeras possibilidades de aplicações em diversas áreas diferentes do processamento de imagens como: segmentação, reconhecimento de caracteres, compressão e geração de imagens. Além disso, destacamos também o caráter social do projeto, tendo sempre como grande incentivo a preservação de imagens de documentos históricos e a ampla divulgação de seu conteúdo para pesquisadores e estudiosos ou apenas pessoas interessadas. Nesse sentido, contribuímos com avanços no estudo de processamento de imagens de documentos históricos, uma área com grande valor social, mas com poucos trabalhos realizados.

Diversos dos objetivos iniciais do Projeto Nabuco foram alcançados nesta tese. Destacamos como principais contribuições para o Projeto:

• A criação de um algoritmo eficiente e automático para segmentação das imagens dos documentos, gerando imagens monocromáticas de boa qualidade;

• Criação de métodos de coloração de imagens; • Criação de algoritmos para geração automática de texturas de papéis de documentos

históricos; • Desenvolvimento e análise de técnicas para geração automática de imagens sintéticas de

documentos históricos; • Utilização do processo de síntese em um sistema eficiente de compressão das imagens de

documentos. • Definição e criação de um OCR primitivo baseado em Redes Neurais para futuras etapas

do Projeto Nabuco. A maioria dos algoritmos desenvolvidos ao longo da tese foram utilizados na etapa final

de síntese, justificando cada passo dado. Os documentos do acervo de Joaquim Nabuco podem ser difundidos através de arquivos que totalizam apenas 2 Kbytes os quais são usados para gerar uma imagem estatisticamente semelhante a imagem original do documento.

A tese gerou diversos artigos nacionais ([45][46]) e internacionais ([44][47][48][49][50]) e os espaços abertos por ela para desenvolvimento de novas técnicas ainda irão gerar muitos outros, dando continuidade ao importante projeto de preservação e divulgação da história.

Prosseguindo com os trabalhos desenvolvidos nesta tese, continuaremos com a busca de um algoritmo eficiente para geração automática de texturas coloridas. Algumas classes de texturas foram identificadas nos documentos e esta informação pode ser usada para gerar imagens mais próximas da original. Tais classes podem ser exemplificadas por papéis com texturas apresentando listras ou pontos escuros. Tais informações quanto ao tipo de papel (sem considerar cor) podem ser inseridas no arquivo binário de dados e serem acrescidas na geração da imagem sintética final. Ainda quanto a geração automática da textura, uma análise do algoritmo ainda deve ser feita, buscando uma diminuição de sua complexidade computacional. A geração das texturas gasta um tempo computacionalmente alto e pode ser reduzido implementando técnicas de otimização de código.

Um segundo ponto a ser abordado é o desenvolvimento de técnicas que melhorem as respostas de ferramentas de OCR para documentos manuscritos. Pode-se observar nas cartas de Joaquim Nabuco que sua caligrafia possui um certo grau de inclinação. Além da aleatoriedade

96

inerente a qualquer escrita, tal inclinação pode dificultar a resposta de OCR's. A implementação de algoritmos como a transformada de Hough ou a de Radon podem detectar graus de inclinação os quais seriam corrigidos. Aplicadas às letras do documento, estas transformadas podem gerar um novo conjunto de fontes a serem reconhecidas pela ferramenta de OCR. Os erros de transcrição podem ser diminuídos com metodologias de treinamento eficientes para a nova fonte.

Os arquivos texto gerados pelas ferramentas de OCR serão usados para buscas por palavras-chaves e também para indexação automática do acervo [87]. Os documentos datilografados podem ser usados para indexação de forma quase direta. Os maiores problemas ocorrem com documentos manuscritos. Com o desenvolvimento de técnicas para o reconhecimento de caracteres manuscritos, índices podem ser gerados também para tais documentos. Mesmo que o reconhecimento como um todo não seja perfeito, uma palavra, se importante para o texto, pode gerar uma classificação. Por exemplo, se for identificado um certo número de palavras da língua inglesa, pode-se colocar o documento em uma classe de correspondências estrangeiras. As palavras podem, inclusive, serem procuradas na própria imagem, criando, assim, um sistema de busca por padrões na imagem sem precisar de sua completa transcrição para texto [89].

Ao longo do trabalho de doutoramento, observou-se que diferentes OCR's geram diferentes respostas quando submetidos a um mesmo documento. Essas diferenças nem sempre representam erros. No geral, o Omnipage foi considerado o melhor software comercial para tais aplicações. Em diversos casos, no entanto, houve caracteres ou palavras não identificados por ele, mas reconhecidas por outras ferramentas. Tentaremos, assim, o desenvolvimento de um sistema de transcrição múltipla, utilizando mais de uma ferramenta de OCR e analisando suas diversas respostas. Devido a diversidade dos erros possíveis de serem gerados, tal sistema é não-trivial. Um dicionário deverá estar associado e algoritmos eficientes de busca no dicionário devem ser implementados. Tal dicionário deve ser adaptado para a grafia da época dos documentos com o auxílio de especialistas em lingüística.

A geração automática do texto também pode ser melhorada, acrescentando informações nos arquivos binários quanto a margens e espaçamentos de cada documento em particular. Isso não provocaria mudanças nos resultados dos testes estatísticos, mas, sim, quanto à inspeção visual do documento. Ainda mais, o arquivo de texto gerado pelo OCR pode ser utilizado com mais eficiência, inserindo num sistema funções de análise sintática desse arquivo a fim de gerar informações adicionais sobre a carta para sua geração. Por exemplo, uma carta inicializada por uma data possui uma margem superior menor.

Por último, uma interface gráfica amigável precisa ser desenvolvida para a implantação do sistema na Fundação Joaquim Nabuco ou em qualquer outra instituição que disponha de acervos semelhantes.

97

Bibliografia

[1] N.Abramson. Information Theory and Coding. McGraw-Hill Book Company, 1963. [2] I.Aleksander e H. Morton. An Introduction to Neural Computing. International Thomson

Computer Press, 1995. [3] H.S.Baird. Document Image Defect Models. Structured Document Image Analysis, pp.

546-556, 1992. [4] H.S.Baird. The Skew Angle of Printed Documents. Proceedings on Conference of the

Society of Photographic Scientists and Engineers, Rochester on Hybrids Imaging Systems, pp. 14-21, 1987.

[5] D.H.Ballard e C.M. Brown. Computer Vision. Prentice-Hall, 1982. [6] M.Bokser. Omnidocument Technologies. Proccedings on IEEE, pp.1066-1078, Julho,

1992. [7] J.S.DeBonet. Multiresolution Sampling Procedure for Analysis and Synthesis of Texture

Image, Computer Graphics (SIGGRAPH '97 Proceedings), pp. 361-368, 1997 [8] R.M.Bozinovic abd S.N.Srihari. Off-Line Cursive Script Recognition. IEEE Transactions

on Pattern Analysis and Machine Intelligence, pp. 68-83, Janeiro, 1989. [9] P.Campisi, D.Hatzinakos e A.Neri. A Perceptually Lossless, Model-Based, Texture

Compression Technique. IEEE Trans. on Image Processing, vol. 9, no. 8, pp. 1325-1336, 2000.

[10] R.Casey, D.Ferguson, K.Mohiuddin e E.Walach. Intelligent Forms Processing Systems. Machine Vision and Applications, Vol. 5, pp. 143-155, 1992.

[11] W.H.Cushman, P.S.Ojha e C.M.Daniels. Usable OCR: What Are The Minimum Performance Requirements ?. Conference Proceedings on Empowering people: Human factors in computing system: special issue of the SIGCHI Bulletin, pp. 145-152, Abril, 1990, Seattle, WA USA.

[12] A.Dengel, R.Bleisenger, R.Hoch, F.Fein e F.Hönes. From Paper to Office Document Standard Representation. Computer, pp. 63-67, Julho, 1992.

[13] L.A.Fletcher and R.Kasturi. A Robust Algorithm for Text String Separation from Mixed Text/Graphics Images. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 910-918, Novembro, 1988.

[14] L.R. França Neto, Projeto Nabuco: Um Ambiente para Processamento de Grandes Acervos de Imagens, Dissertação de Mestrado, Departamento de Informática, UFPE, Outubro, 1998

[15] L.R.França Neto, C.A.B. Mello e R.D. Lins. Técnicas de Filtragem para Imagens Digitais de Documentos Históricos. XV Simpósio da Sociedade Brasileira de Telecomunicações, Recife, Brasil, Setembro, 1997.

[16] T.Frêche e N.Vincent. Some New Global Parameters to Qualify the Handwriting. Vision Interface ’99, Québec, Canadá, Maio, 1999.

[17] J.Gomes e L. Velho. Computação Gráfica: Imagem. Sociedade Brasileira de Matemática, 1994.

[18] R.Gonzalez e P. Wintz. Digital Image Processing. Addison Wesley Publishing Co., 1995.

98

[19] R.T.Hartley and K.Crumpton. Quality of OCR for Degraded Text Images. Proceedings of the Fourth ACM Conference on Digital Libraries, pp. 228-229, Agosto, 1999, Berkeley, CA USA.

[20] S.Haykin. Neural Networks A Comprehensive Foundation. IEEE Press, 1994. [21] S.C.Hins, J.L.Fisher e D.P.D’Amato. A Documnet Skew Detection Method Using Run-

Length Encoding and the Hough Transform. Proceedings on 10th. International Conference on Pattern Recognition, pp. 464-468, 1990.

[22] J.F. Hébert, M.Parizeau e N.Ghazzali, Learning to Segment Cursive Words Using Isolated Characters, Vision Interface ’99, Québec, Canadá, Maio, 1999.

[23] J.J.Hull. Incorporation of a Markov Model of Language Syntax in a Text Recognition Algorithm. Proceedings of Symposium of Document Analysis and Information Retrieval, pp. 174-185, 1992.

[24] A.K.Jain e C.Dorai, Practicing Vision: Integration, Evaluation and Applications, Pattern Recognition, vol. 30, no.2, pp. 183-196, 1997.

[25] A.K.Jain. Fundamentals of Digital Image Processing. Prentice Hall, Inc., 1989. [26] A.K.Jain e S.Bhattachrjee. Text Segmentation using Gabor Filters for Automatic

Document Processing. Machine Vision and Applications, Vol. 5, pp. 169-184, 1992. [27] G. Johannsen e J. Bille, A Threshold Selection Method Using Information Measures, Proc.

Sixth International Conference on Pattern Recognition, pp. 140-143, Munique, Alemanha, 1982.

[28] B.Julesz, Nonlinear and Cooperative Processes in Texture Perception, In Theoretical Approaches in Neurobiology, T.P. Werner, E. Reichardt, (Editors). MIT Press, Cambridge, MA, pp. 93-108, 1981.

[29] B.Julesz, Textons, the Elements of Texture Perception, and Their Interactions, Nature, 290, pp. 91-97, 1981.

[30] B.Julesz, A Theory of Preattentive Texture Discrimination Based on First-Order Statistics of Textons, Biological Cybernetics, 41, pp. 131-138, 1981.

[31] B.Julesz, Experiments in the Visual Perception of Texture, Scientific American, 232, pp.34-43, 1975.

[32] M.Kamel e A.Zhao. Extraction of Binary Character/Graphics Images from Grayscale Document Images. CVGIP: Graphical Models and Image Processing. Vol. 55, No. 3, pp.203-217, 1993.

[33] J.N.Kapur, P.K. Sahoo e A.K.C.Wong. A New Method for Gray-Level Picture Thresholding using the Entropy of the Histogram, Computer Vision, Graphics and Image Processing, 29(3), Março, 1985.

[34] J. N. Kapur, Measures of Information and their Applications, John Wiley and Sons, 1994. [35] A.Koerich e L.Ling. A System for Automatic Extraction of the User-Entered Data from

Banckchecks. Proceedings of Sibgrapi’98, pp. 270-277, outubro, 1998, RJ, Brasil. [36] S.Kullbak. Information Theory and Statistics. Dover Publications, Inc.1997. [37] L.Lam, S-W. Lee e C.Y.Suen. Thinning Methodologies – A Comprehensive Survey. IEEE

Transactions on Pattern Analysis and Machine Intelligence, pp. 377-393, 1985. [38] R.D.Lins, M.S. Guimarães Neto, L.R. França Neto e L.G. Rosa. An Environment for

Processing Images of Historical Documents. Microprocessing & Microprogramming, pp. 111-121, North-Holland, January, 1995.

[39] S.Livens, P.Scheunders, G.Van de Wouwer, D.Van Dyck, Wavelets for Texture Analysis, http://www.ruca.ua.ac.be/ ~ VisionLab/WTA.html, 1997.

[40] D.Ludwig. The Radon Transform of Euclidian Space. Communication Pure and Applied Mathematics, 19, pp.49-81, 1966.

[41] R.E.McGrath. Understanding Statistics – A Research Perspective. Addison-Wesley Educational Publishers, 1997.

[42] G.Medioni e Y.Yasumoto. Corner Detection and Curve Representation Using Cubic B-Splines. Computer Vision, Graphics and Image Processing, Vol. 39, pp. 267-278,1987.

99

[43] C.A.B.Mello. Algoritmos e Técnicas para Compressão de Grandes Acervos de Imagens Estáticas. Dissertação de Mestrado, Departamento de Informática, Agosto, 1996. Disponível para cópia em http://www.di.ufpe.br/~cabm.

[44] C.A.B.Mello e R.D.Lins, Generation of Images of Historical Documents by Composition, Vision Interface 2002, Calgary, Canadá, maio, 2002.

[45] Carlos A.B.Mello e Rafael D.Lins, Colourising Paper texture of Grayscale Historical Documents, I Congresso de Informática da Amazônia, Manaus, Brasil, abril, 2001

[46] C.A.B.Mello e R.D. Lins. A New Segmentation Algorithm for True Colour Images of Historical Documents, XVIII Simpósio Brasileiro de Telecomunicações, Gramado, RS, Brasil, setembro, 2000.

[47] C.A.B.Mello e R.D. Lins. Image Segmentation of Historical Documents, Visual 2000, Cidade do México, México, agosto, 2000.

[48] C.A.B.Mello e R.D. Lins. Generating Paper Texture Using Statistical Moments, IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP 2000, Istanbul, Turquia, junho, 2000.

[49] C.A.B.Mello e R.D. Lins, Segmentação de Imagens de Documentos Históricos, XVII Simpósio Brasileiro de Telecomunicações, Vila Velha, ES, Brasil, setembro, 1999.

[50] C.A.B.Mello e R.D. Lins. A Comparative Study on Commercial OCR Tools. Proceedings of Vision Interface’99. Québec, Canadá, Maio, 1999.

[51] C.A.B.Mello, L.R.França Neto e R.D.Lins. Uma Nova Técnica para Compressão de Imagens Estáticas. Anais do XVI Congresso da Sociedade Brasileira de Computação, Brasil, Agosto, 1996.

[52] C.A.B.Mello, L.R.França Neto e R.D.Lins. A New Algorithm for Monochromatic Image Compression. Proceedings of 23rd Euromicro Conference, Budapest, Hungria, 1997.

[53] M.Miyahara, K.Kotani e V.R.Algazi. Objective Picture Quality Scale (PQS) for Image Coding. IEEE Trans. on Communications, Vol. 46, no. 9, pp. 1215-1226, 1998.

[54] S.Mori, C.Y.Suen e K.Yamamoto. Historical Review of OCR Research and Development. Proceedings of IEEE, pp. 1029-1058, 1992.

[55] G.Nagy, S.Seth e M.Viswanathan. A Prototype Document Image Analysis System for Technical Journals. Computer, pp. 10-22, Julho, 1992.

[56] F.Nouboud e R.Plamondon. On-Line Recognition of Handprinted Characters: Surveys and Beta Tests. Pattern Recognition, Vol. 23, No. 9, pp. 1031-1044, 1990.

[57] L.O’Gorman and R.Kasturi. Document Image Analysis. IEEE Computer Society Press. 1995.

[58] L.O’Gorman. The Document Spectrum for Page Layouts Analysis. IEEE Transactions on Pattern Analysis and Machine Inteligence, pp. 1162-1173, Novembro, 1993.

[59] L.O’Gorman. Curvilinear Feature Detection from Curvature Estimation. Proceedings of (th International Conference on Pattern Recognition, pp. 1116-1119, 1988.

[60] K.O’Hara e A.Sellen. A Comparison of Reading Paper and On-Line Documents. Conference Proceedings on Human factors in computing systems, pp. 335-342, Março, 1997, Atlanta, GA USA.

[61] N.Otsu, A Threshold Selection Method from Gray-level Histograms, IEEE Transactions on Systems, Man and Cybernetics, v. SMC 9, no 1, pp.62-66, 1979.

[62] P.W.Palumbo, S.Srihari, J.Soh, R.Sridhar e V.Demjanenko. Postal Address Block Location in Real Time. Computer, pp. 10-22, Julho, 1992.

[63] T.Paquet, M.Avila e C.Olivier. Word Modeling for Handwritten Word Recognition, Vision Interface ’99, Quebéc, Canadá, Maio, 1999.

[64] J.R.Parker. Algorithms for Image Processing and Computer Vision. John Wiley and Sons, 1997.

[65] T.Pavlidis e J.Zhou. Page Segmentation and Classification. CVGIP: Graphical Models and Image Processing. Vol. 54, No. 6, pp. 484-496, 1992.

100

[66] T.Pavlidis. A Review of Algorithms for Shape Analysis. Computer and Image Processing, Vol. 7, pp. 243-258,1978.

[67] I.T.Phillips, S.Chen e R.M.Haralick. CD-Rom Document Database Standard. Proceedings on International Conference on Document Analysis and Recognition, pp. 478-483, 1993.

[68] N. Pitts-Moultis e C. Kirk. XML: Black Book, Makron Books, 2000. [69] T.Pun. Entropic Thresholding, A New Approach, Computer Graphics and Image

Processing, 16(3), Julho 1981. [70] J.Radon. On the Determination of Functions from their Integrals Along Vertain

Manifolds. Bertichte Saechsiche Akad. Wissenschaften (Leipzig). Math. Phys. Klass 69, pp.262-277, 1917.

[71] L.G. Rosa Neto. Nabuco: Uma Base de Dados Para Documentos Historicos. Dissertação de Mestrado, Departamento de Informática, 1994.

[72] K.Sayood. Introduction to Data Compression. Morgan Kaufmann Publishers, Inc. 1996. [73] J.Schürmann, N.Bartneck,T.Bayer, J.Franke, E.Mandler e M.Oberländer . Document

Analysis – From Pixels to Contents. Proceedings IEEE, pp. 1101-1119, Julho, 1992. [74] C.Shannon. A Mathematical Theory of Communication. Bell System Technology Journal,

vol. 27, pp. 370-423, 623-656, 1948. [75] C.Shannon e W.Weaver. The Mathematical Theory of Communication. The University of

Illinois Press, Urbana, Illinois. 1949. [76] S.L.Taylor, R.Fritzson e J.A.Pastor. Extraction of Data from Preprinted Forms. Machine

Vision and Applications, Vol. 5, pp. 211-222, 1992. [77] O.D.Trier, A.K.Jain and T.Taxt, Feature Extraction Methods for Character Recognition -

A Survey, Pattern Recognition 29, pp. 641-662, 1996. [78] W-H.Tsai. Moment-Preserving Thresholding: A New Approach. Computer Vision,

Graphics and Image Processing, Vol. 29, pp. 377-393, 1985. [79] S.Tsujimoto e H.Asada. Major Components of a Complete Text Reading System.

Proceedings of IEEE, pp. 1133-1149, Julho, 1992. [80] M.Tuceryan e A.K.Jain. Texture Analysis, The Handbook of Pattern Recognition and

Computer Vision (2nd Edition), by C. H. Chen, L. F. Pau, P. S. P. Wang (editores), pp. 207-248, World Scientific Publishing Co., 1998.

[81] M.Tuceryan, Moment Based Texture Segmentation, Pattern Recognition Letters, vol.15, pp. 659-668, 1994.

[82] K. Ueda. Extraction of Signature and Seal Imprint from Bankchecks by Using Color Information. Proceedings of 3rd International Conference on Document Analysis and Recognition, pp. 665-668, Montreal, Canada, 1995.

[83] J.R.Ullmann. Pattern Recognition Techniques. Butterworth & Co., 1973. [84] K.Wall e P.E.Danielsson. A Fast Sequential Method for Polygonal Approximation of

Digitized Curves. Computer Vision, Graphics and Image processing, Vol. 28, pp. 220-227, 1984.

[85] A.Watt. 3D Computer Graphics. Addison-Wesley Publishing Co., 1993. [86] T.A.Welch. A Technique for High-Performance Data Compression. IEEE Transactions on

Information Theory, No. 3, Vol IT-23, pp 337-343, Maio, 1977. [87] I.H.Witten, A.Moffat e T.C. Bell. Managing Gigabytes - Compressing and Indexing

Documents and Images. Van Nostrand Reinhold, 1994. [88] M.Worring e A.W.M.Smeulders. Internet Access to Scanned Paper Documents.

Proceedings of the third ACM Conference on Digital Libraries, pp. 313-314, Junho, 1998, Pittsburgh, PA USA.

[89] V.Wu, R.Manmatha e E.M.Riseman. Finding Text in Images. Proceedings of the 2nd ACM International Conference on Digital Libraries, pp. 3-12, Julho, 1997, Philadelphia, PA USA.

101

[90] W-Y.Wu e M-J.J.Wang. Detecting the Dominant Points by the Curvature-Based Polyginal Approximation. CVGIP: Graphical Models and Image Processing. Vol. 55, No. 2, pp.79-88, 1993.

[91] I.Yoshimura e M.Yoshimura. Off-Line Verification of Japanese Signatures after Elimination of Background. International Journal of Pattern Recognition and Artificial Inteligence, no. 8, pp. 693-708, 1994.

[92] Adobe Systems Inc. URL: http://www.adobe.com. Visitado em 15/12/01. [93] Caere Corporation. URL: http://www.caere.com. Visitado em 15/12/01. [94] Chamex. URL: http://www.chamex.com.br. Visitado em 15/12/01. [95] Corel Corp. URL: http://www.corel.com. Visitado em 15/12/01. [96] Expervision. URL: http://www.expervision.com. Visitado em 15/10/99. [97] MatLab. URL: http://www.mathworks.com. Visitado em 01/08/01. [98] OCRON Inc. URL: http://www.newsoftinc.com. Visitado em 15/10/99. [99] Recognita Corp. URL: http://www.recognita.com. Visitado em 15/10/99. [100] Xerox. URL: http://www.xerox.com. Vsitado em 07/01/02. [101] Projeto Nabuco: http://www.cin.ufpe.br/~nabuco. Visitado em 08/01/02.

102

Exemplo da Aplicação de Diferentes Ferramentas de OCR’s a um Texto Digitalizado

Apresentaremos aqui o resultado da aplicação de algumas ferramentas de OCR à imagem do documento apresentado na Figura 50.

A imagem do documento apresentado na Figura 50 foi dada como entrada para algumas das ferramentas de OCR testadas no capítulo 1. A seguir, apresentamos os documentos em texto gerados, observando que nenhuma alteração foi feita nestes, sendo preservada toda a formatação fornecida por eles e demais características. O documento original foi extraído da Internet, impresso em uma impressora preto-e-branco HP Lasejet com 300 dpi de resolução e digitalizado em um scanner HP Scanjet 4c.

Apêndice A

103

Figura 50. Documento usado como entrada de diversos OCR’s.

104

Texto Original (formatado de acordo com a imagem original, excluindo a figura) Titanic - Communications http://www.titanicmovie.com/past/hist_brief_index.html A Brief History Of Titanic The Royal Mail Ship TITANIC was the last grand dream of the Gilded Age. It was designed to be the greatest achievement of an era of prosperity, confidence and propriety. Although no one knew it, the world was about to change drastically. Radio had been invented in 1901. The Wright Brothers' first successful flight was in 1903. The old presumptions about class, morals, and gender-roles were about to be shattered. If the concept of Titanic was the climax of the age, then perhaps its sinking was the curtain that marked the end of the old drama, and the start of a new one. THE PLAN. The intensely competitive transatlantic steamship business had seen recent major advances in ship design, size and speed. White Star Line, one of the leaders, determined the focus on size and elegance rather than pure speed. In 1907, White Star Line's managing director J. Bruce Ismay and Lord James Pirrie, a partner in Harland & Wolff (White Star Line's ship-builder since its founding in 1869) conceived of three magnificent steam ships which would set a new standard for comfort, elegance, and safety. The first two were to be named Olympic and Titanic, the latter name chosen by Ismay to convey a sense of overwhelming size and strength. It took a year to design the two ships. Construction of Olympic started in December, 1908, followed by Titanic in March 1909. The Belfast shipyards of Harland & Wolff had to be re-designed to accommodate the immense projects while White Star's pier in New York had to be lengthened to enable the ships to dock. During the two years it took to complete Titanic's hull, the press was primed with publicity about the ship's magnificence, making Titanic virtually a legend before her launch. The "launch" of the completed steel in May, 1911, was a heavily publicized spectable. Tickets were sold to benefit a local children's hospital. She was then taken for "fitting out" which involved the construction of the ship's many facilities and systems, her elaborate woodwork and fine decor. As the date of her maiden voyage approached, the completed Olympic suffered a collision and required extensive repairs, increasing the workload at Harland & Wolff, which was already struggling to complete Titanic on schedule. Titanic's maiden voyage was delayed from March 20 to April 10. THE SHIP Titanic was 883 feet long (1/6 of a mile), 92 feet wide and weighed 46,328 tons. She was 104 feet tall from keel to bridge, almost 35 feet of which were below the waterline... even so, she stood taller above the water than most urban buildings of the time. There were three real smoke-stacks; a fourth, dummy stack was added largely to increase the impression of her gargantuan size and power and to vent smoke from her numerous kitchens and galleys. She was the largest movable object ever made by man. The ship's immense size and complexity is illustrated by an incident recalled by Second Officer Lightoller. There was a gangway door on the starboard site aft "large enough 1 of 4 19/05/98 18:48

105

Texto gerado pelo Omnipage 9.0 Titwic - Co=mications http://~.titmicmovic.com/past/hist-brief-index.html A Brief History Of _fitaffic The Royal Mail Ship TITANIC was the last grand dream of the Gilded Age. It was designed to be the greatest achievement of an era of prosperity, confidence and propriety. Although no one knew it, the world was about to change drastically. Radio had been invented in 1901. The Wright Brothers' first successful flight was in 1903. The old presumptions about class, morals, and gender-roles were about to be shattered. If the concept of Titanic was the climax of the age, then perhaps its sinking was the curtain that marked the end of the old drama, and the start of a new one. THE PIAN The intensely competitive transatlantic steamship business had seen recent major advances in ship design, size and speed. White Star Line, one of the leaders, determined to focus on size and elegance rather than pure speed. In 1907, White Star Line's managing director J. Bruce Ismay and Lord James Pirrie, a partner in Harland & Wolff (White Star Line's ship-builder since its founding in 1869) conceived of three magnificent steam ships which would set a new standard for comfort, elegance, and safety. The first two were to be named Olympic and Titanic, the latter name chosen by Ismay to convey a sense of overwhelming size and strength. It took a year to design the two ships. Construction of Olympic started in December, 1908, followed by Titanic in March 1909. The Belfast shipyards of Harland & Wolff had to be re-designed to accommodate the immense projects while White Star's pier in New York had to be lengthened to enable the ships to dock. During the two years it took to complete Titanic's hull, the press was primed with publicity about the ship's magnificence, making Titanic virtually a legend before her launch. The "launch" of the completed steel in May, 1911, was a heavily publicized spectacle. Tickets were sold to benefit a local children's hospital. She was then taken for "fitting ouC which involved the construction of the ship's many facilities and systems, her elaborate woodwork and fine decor. As the date of her inaiden voyage approached, the completed Olympic suffered a collision and required extensive repairs, increasing the workload at Harland & Wolff, which was already struggling to complete Titanic on schedule. Titanic's maiden voyage was delayed from March 20 to April 10. THE SHIP Titanic was 883 feet long (l/6 of a mile), 92 feet wide and weighed 46,328 tons, She was 104 feet tall from keel to bridge, almost 35 feet of which were below the waterline... even so, she stood taller above the water than most urban buildings of the time. There were three real smoke-stacks; a fourth, dummy stack was added largely to increase the impression of her gargantuan size and power and to vent smoke from her numerous kitchens and galleys. She was the largest movable object ever made by man. The ship's immense size and complexity is illustrated by an incident recalled by Second Officer Lightoller. There was a gangway door on the starboard side aft 9arge enough 1 of 4 19/05/98 18:48

106

Texto gerado pelo Corel OCR Trace 8.0 Titanic Communications http://www.titanicmovie.com/past/hist brief index.html A• Brief History Qf Titanic So thli is the s1ifp thep say Is umlnkab1e.dblquote The Royal Mail Ship TITANIC was the last grand dream of the Gilded Age. It was designed to be the greatest achievement of an era of prosperity, confidence and propriety. Although no one knew it, the world was about to change drastically. Radio had been invented in 1901. The Wright Brothersquote first successful flight was in 1903. The old presumptions about class, morals, and gender-roles were about to be shattered. If the concept of Titanic was the climax of the age, then perhaps its sinking was the curtain that marked the end of the old drama, and the start of a new one. THE• PLAM The intensely competitive transatlantic steamship business had seen recent major advances in ship design, size and speed. White Star Line, one of the leaders, determined to focus on size and elegance rather than pure speed. In 1907, White Star Linequote s managing director J. Bruce Ismay and Lord James Pirrie, a partner in Harland & Wolff (White Star Linequote s ship-builder since its founding in 1869) conceived of three magnificent steam ships which would set a new standard for comfort, elegance, and safety. The first two were to be named Olympic and Titanic, the latter name chosen by Ismay to convey a sense of overwhelming size and strength. It took a year to design the two ships. Construction of Olympic started in December, 1908, followed by Titanic in March 1909. The Belfast shipyards of Harland & Wolff had to be re-designed to accommodate the immense projects while White Starquote s pier in New York had to be lengthened to enable the ships to dock. During the two years it took to complete Titanicquote s hull, the press was primed with publicity about the shipquote s magnificence, making Titanic virtually a legend before her launch. The dblquote launchdblquote of the completed steel in May, 1911, was a heavily publicized spectacle. Tickets were sold to benefit a local childrenquote s hospital. She was then taken for dblquote fitting outdblquote which involved the construction of the shipquote s many facilities and systems, her elaborate woodwork and fine decor. As the date ofher maiden voyage approached, the completed Olympic suffered a collision and required extensive repairs, increasing the workload at Harland & Wolff, which was already struggling to complete Titanic on schedule. Titanicquote s maiden voyage was delayed &om March 20 to April 10. THE SHIP Titanic was 883 feet long (1/6 of a mile), 92 feet wide and weighed 46,328 tons. She was 104 feet tall from keel to bridge, almost 35 feet of which were below the waterline... even so, she stood taller above the water than most urban buildings of the time. There were three real smoke-stacks; a fourth, dummy stack was added largely to increase the impression ofher gargantuan size and power and to vent smoke from her numerous kitchens and galleys. She was the largest movable object ever made by man. The shipquote s immense size and complexity is illustrated by an incident recalled by Second Officer Lightoller. There was a gangway door on the starboard side aft dblquote large enough 1 of4 19/05/98 18:48

107

Texto gerado pelo Textbridge Titanic - Communications http://www.titanicmovie coiripast’1-i ist brief index.html A Brief History Of Titanic The Royal Mail Ship TITANIC was the last grand dream of the Gilded Age. It was designed to be the greatest achievement of an era of prosperity, confidence and propriety. Although no one knew it, the world was about to change drastically. Radio had been invented in 1901. The Wright Brothers first successful flight was in 1903. The old presumptions about class, morals, and gender-roles were about to be shattered. If the concept of Titanic was the climax of the age, then perhaps its sinking was the curtain that marked the end of the old drama, and the start of a new one. ThE PLAN The intensely competitive transatlantic steamship business had seen recent major advances in ship design, size and speed. White Star Line, one of the leaders, detennined to focus on size and elegance rather than pure speed. In 1907, White Star Line s managing director J. Bruce Ismay and Lord James Pirrie, a partner in Harland & Wolff (White Star Line’s ship-builder since its founding in 1869) conceived of three magnificent steam ships which would set a new standard for comfort, elegance, and safety. The first two were to be named Olympic and Titanic, the latter name chosen by Ismay to convey a sense of overwhelming size and strength. It took a year to design the two ships. Construction of Olympic started in December, 1908, followed by Titanic in March 1909. The Belfast shipyards of Harland & Wolff had to be re-designed to accommodate the immense projects while White Star’s pier in New York had to be lengthened to enable the ships to dock. During the two years it took to complete Titanic’s hull, the press was primed with publicity about the ship’s magnificence, making Tilanic virtually a legend before her launch. The “launch” of the completed steel in May, 1911, was a heavily publicized spectacle. Tickets were sold to benefit a local children’s hospital. She was then taken for “fitting out” which involved the construction of the ship’s many facilities and systems, her elaborate woodwork and fine decor. As the date of her maiden voyage approached, the completed Olympic suffered a collision and required extensive repairs, increasing the workload at Harland & Wolff, which was already struggling to complete Titanic on schedule. Titanic’s maiden voyage was delayed from March20 to April 10. THE SHIP Titanic was 883 feet long (1/6 of a mile), 92 feet wide and weighed 46,328 tons. She was 104 feet tall from keel to bridge, almost 35 feet of which were below the waterline.., even so, she stood taller above the water than most urban buildings of the time. There were three real smoke-stacks; a fourth, dummy stack was added largely to increase the impression of her gargantuan size and power and to vent smoke from her numerous kitchens and galleys. She was the largest movable object ever made by man. The ship’s immense size and complexity is illustrated by an incident recalled by Second Officer Lightoller. There was a gangway door on the starboard side aft “large enough

108

Texto gerado pelo Wordlinx Titanic- Communications htrp:llu?Yw.titanicmovie.comipastihistbr inden.html A Brief History Of Titanic The Royal Mail Ship TITANIC was the last grand dream ofthe Gilded Age. It was designed to be the greatest achievement ofan era ofprosperity, confidence and propriety. Although no one knew it, the world was about to change drastically. Radio had been invented in 1901. The Wright Brothers' first successful flight was in 1903. The old presumptions about class, morals, and gender-roles were about to be shattered. If the concept of Titanic was the climax ofthe age, then perhaps its sinking was the curtain that marked the end ofthe old drama, and the start ofa new one. MEPLAN The intensely competitive transatlantic steamship business had seen recent major advances in ship design, size and speed. White Star Line, one ofthe leaders, determined to focus on size and elegance rather than pure speed. In 1907, White Star Line's managing director J. Bruce Ismay and Lord James Pirrie, a partner in Harland & Wolff(White Star Line's ship-builder since its founding in 1869) conceived of three magnificent steam ships which would set a new standard for comfort, elegance, and safety. The first two were to be named Olympic and Titanic, the latter name chosen by Ismay to convey a sense ofoverwhelming size and strength. It took a year to design the two ships. Construction of Olympic started in December, 1908, followed by Titanic in March 1909. The Belfast shipyards of Harland & Wolff had to be re-designed to accommodate the immense projects while White Star's pier in New York had to be lengthened to enable the ships to dock. During the two years it took to complete Titanic's hull, the press was primed with publicity about the ship's magnificence, making Titanic virtually a legend before her launch. The "launch ofthe completed steel in May, 1911, was a heavily publicized spectacle. Tickets were sold to benefit a local children's hospital. She was then taken for "fitting out" which involved the construction ofthe ship's many facilities and systems, her elaborate woodwork and fine decor. As the date of her maiden voyage approached, the completed Olympic suffered a collision and required extensive repairs, increasing the workload at Harland & Wolff, which was already struggling to complete Titanic on schedule. Titanic's maiden voyage was delayed from March 20 to April 10. TtIE SHIP Titanic was 883 feet long (1/6 of a mile), 92 feet wide and weighed 46,328 tons. She was 104 feet tall from keel to bridge, almost 35 feet ofwhich were below the waterline... even so, she stood taller above the water than most urban buildings ofthe time. There were three real smoke-stacks; a fourth, dummy stack was added largely to increase the Impression ofher gargantuan size and power and to vent smoke from her numerous kitchens and galleys. She was the largest movable object ever made by man. The ship's immense size and complexity is illustrated by an incident recalled by Second Officer Lightoller. There was a gangway dooron the starboard side aft "large enough

109

B

Análise de Rotação – A Transformada de Hough

Antes de proceder com a análise do reconhecimento, é preciso primeiro determinar se o documento digitalizado está rotacionado em relação ao eixo da escrita do documento original. A disposição do papel sobre a mesa do scanner pode estar sujeita a uma rotação, por ser este um processo manual na maioria dos casos. Já existem aparelhos digitalizadores que tratam grandes quantidades de documentos de forma automática, diminuindo a possibilidade de rotação nas imagens. Estes aparelhos, no entanto, não são adequados ao uso em documentos históricos face a sua importância (um dispositivo mecânico pode por falha rasgar, amassar, até mesmo destruir o documento) e falta de padronização (cada documento possui característica de espessura, dimensões, etc).

Para tratar problemas de rotação da imagem a transformada de Hough é o método mais utilizado. Com ela, o espaço de coordenadas cartesianas XY é convertido para um novo espaço, chamado espaço de Hough, onde cada pixel da imagem corresponde a um conjunto de retas. Se N retas, correspondendo a N pixels, se encontram em um ponto, estes N pixels estão alinhados na imagem. Assim, cada reta que pode passar por um dado pixel em uma imagem pode ser completamente descrita pela equação:

bXaY += . (12) Onde X e Y são as coordenadas do pixel na imagem, a é o grau de inclinação da reta e b é a ordenada onde a reta encontra o eixo Y. Esta mesma equação pode ser escrita de outra forma apenas trocando a ordem das variáveis:

Yxab i +−= . (13) que corresponde à equação da reta no plano (a, b) (o espaço de Hough). Considere um ponto (xi, yi) e a equação geral

bxay ii += . (14)

Existe um número infinito de retas que passam por ),( ii yx , todas elas satisfazendo a equação 14

para valores diferentes de a e b. Tomando a expressão 13 do espaço de Hough para o ponto ),( ii yx , temos, para o par fixo ix e iy , apenas uma única reta no espaço de Hough. Tomemos,

agora, outro ponto ),( ii yx da imagem. Novamente, infinitas retas passam por esse ponto no

espaço XY e teremos uma reta no espaço de Hough associada a esse novo ponto. Essa nova reta

interceptará (se ii yx ≠ ) a reta definida pelo ponto ),( ii yx em uma coordenada ),( '' ba , onde a'

é a inclinação e b' é a interseção da reta contendo os dois pontos no plano XY. Assim, todos os

Apêndice

110

pontos contidos na reta bXaY += . terão retas no plano de Hough que se interceptarão em

),( '' ba .

Ao espaço de Hough está associado um acumulador. O espaço é subdividido em células acumuladoras, limitadas por valores máximos e mínimos de a e b. A célula com coordenada

),( ji possui um valor de acumulador ),( jiA , correspondendo à célula associada com a

coordenada ),( ji ba no plano ),( ba . Inicialmente, ),( jiA é igual a zero, para todo i e j. Para cada

ponto da imagem, fixamos o parâmetro a para cada célula e resolvemos a equação 2 para acharmos o valor de b. O valor encontrado é arredondado de modo a pertencer a uma célula no espaço. Por exemplo, se a escolha do valor ap resulta em um valor bq, o valor acumulado na célula ),( qp é incrementado de um, ou seja: 1),(),( += qpAqpA . Ao final, um valor K no

acumulador ),( ji indica a presença de K pontos no plano XY pertencendo à reta ji bxay += . . O

número de subdivisões feitas no espaço de Hough, definindo as células, garante a confiabilidade da resposta do procedimento.

A equação 1, no entanto, apresenta seu maior problema à medida que a reta inclina-se na vertical (formando um ângulo de 90° com o eixo X). Nessa inclinação, o valor de b (ponto de encontro da reta com o eixo Y) tende a infinito. Este problema, no entanto, pode ser facilmente resolvido representando a equação da reta em outra forma, como a forma normal, por exemplo:

)sen(.)cos(. wywxr += (15)

onde r é a distância perpendicular da origem do plano à reta e w é o ângulo desta linha perpendicular ao eixo X. O processo para uso de acumuladores continua o mesmo. O valor de w, no entanto, varia entre ±90°.

Através desta transformada, é possível determinar o grau de rotação da imagem digitalizada e, assim, proceder a uma rotação no sentido reverso. No caso de imagens textuais, a base de todas as letras que não têm prolongamentos abaixo da linha de escrita (letras que não sejam j, q, p, g ou y) devem ser colineares para que o texto não apresente nenhuma rotação. Assim, para se determinar o grau de rotação de uma imagem textual, cada símbolo é envolto por uma caixa (chamada glyph) e os pontos médios de cada uma dessas caixas é usado como base para a transformada de Hough. A determinação da caixa limitante do símbolo pode ser feita através da identificação de regiões conectadas na imagem. No caso de imagens monocromáticas, essas regiões são compostas por pixels pretos. Para imagens em tons de cinza, pode-se usar um valor de corte para definir as regiões de pixels pretos e brancos.

Podemos implementar a transformada de Hough no software MatLab [97] através da transformada de Radon [25][40][71]. Abaixo, podemos ver uma tal aplicação da transformada de Radon em uma simulação de uma rotação aplicada a um documento digitalizado. Suponha que foi inserida uma rotação de 10o no sentido anti-horário durante o processo de digitalização conforme pode ser visto na Figura 51. A transformada deve determinar este ângulo de rotação e, em seguida, uma rotação de mesmo valor e sentido contrário será imposta na imagem. Toda a aplicação a seguir foi feita com auxílio do software MatLab versão 6.0.

111

a)

b)

Figura 51. Exemplo de rotação de um documento. a) Documento original e b) Documento rotacionado em 10o

À imagem rotacionada foi aplicada a função abaixo, desenvolvida no MatLab, utilizando a

transformada de Radon para determinar o ângulo de rotação : function y=posrot(x) % desenha o grafico da transformada de Radon para % determinar rotacao de uma imagem e localiza a posicao % onde o maximo ocorre % posj indica o angulo de rotacao % A entrada x deve ser uma imagem greyscale BW=edge(x); theta=0:179; [R,xp]=radon(double(BW),theta); imagesc(theta,xp,R); colormap(hot); xlabel('\theta (degrees)');ylabel('x'''); colorbar; maxr = max(max(R)); tam=size(R); for i=1:tam(1) for j=1:tam(2) if (R(i,j)==maxr) posi=i; posj=j; end end end y=90-posj;

112

O resultado da transformada pode ser visto no gráfico da Figura 52.a e o resultado final da função foi o ângulo de rotação de –11o (erros de aproximação podem ter sido inseridos pelo programa), indicando uma rotação de 11o no sentido horário, como pode ser visto na Figura 52.b.

a)

b)

Figura 52. Aplicação da transformada de Radon para determinar o ângulo de rotação de uma imagem.

a) Resultado gráfico da transformada de Radon aplicada à imagem rotacionada da Figura 51.b. b) Imagem final rotacionada segundo o ângulo definido pela função

113

Código Fonte de Rede Neural para Reconhecimento de Caracteres

Apresenta-se a seguir o código fonte para um sistema de reconhecimento de caracteres, utilziando Redeus Neurais e o algoritmo de Back-Propagation. O código foi implementado no C++ Builder 1.0 da Inprise. #include <vcl\condefs.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <malloc.h> #include <iostream.h> #include <conio.h> #include <sys/types.h> #pragma hdrstop USERES("bprop3.res"); int NO_OF_INPUTS = 104; int NO_OF_HIDDEN = 50; int NO_OF_OUTPUTS = 26; float *inputs; // Valores de Entrada da primeira camada (escondida) float **hweights; // Pesos na Camada Escondida float *hidden; // Saída da Camada Escondida float *vhidden; float *err_hidden; // Erros nos neurônios da camada escondida float **old_hweights; // Pesos da Camada Escondida em t-1 float **delta_hweights; // Variação dos Pesos entre t e (t-1) float **oweights; // Pesos na camada de saída float *outputs; // Saída final float *voutputs; float *err_out; // Erros na camada de saída float **old_oweights; // Pesos da Camada de Saida em t-1 float **delta_oweights; // Variação dos Pesos entre t e (t-1) float *teta; // Threshold float *should; // Valor desejado na saída float learning_rate = 0.01; float momentum = 0.01; FILE *input_data; // Arquivo para Treinamento FILE *test_data; // Arquivo para Teste FILE *iptr; // Um dos dois acima FILE *file_error; // Arquivo de Erro FILE *wptr; // Arquivo de Pesos para Uso int actual; // Saída atual time_t start, end; long etime; void compute_hidden (int node); void compute_output (int node); float output_function (float x); void compute_all_hidden (); void compute_all_outputs ();

Apêndice C

114

float weight_init (void); float threshold_init (void); void initialize_all_weights (); void initialize_threshold(); float compute_output_error (); float compute_hidden_node_error (int node); void compute_hidden_error (); void update_output (); void update_hidden (void); float * fvector (int n); float **fmatrix (int n, int m); void setup (void); int get_inputs (float *x); void save_weights(); void compute_training_outputs(); float compute_error_term(); void print_outputs(); int dset = 1; int operacao = 0; // Tipo de operação da rede: Treino (1) ou Uso (2) int camada = 0; // Indica camada ((1) escondida; (2) saida) int count = 0; int main(int argc, char *argv[]) {

int k, i, j, intera; float x; bool flag; char filename[255]; FILE *thresh; /* Dados de entrada do programa */ if (argc < 2) { cout << "Uso: bprop -<option> \n"; cout << "option:\n\t t (treinamento) ou u (uso)\n\n"; exit(1); } if (argv[1][1] == 't') { cout << "Entre com o nome do arquivo de treino :\n"; operacao = 1; } if (argv[1][1] == 'u') { cout << "Entre com o nome do arquivo de uso :\n"; operacao = 2; } if ((argv[1][1] != 't') && (argv[1][1] != 'u')) { cout << "Uso: bprop -<option> \n"; cout << "option:\n\t t (treinamento) ou u (uso)\n\n"; exit(1); } cin >> filename; if ((input_data = fopen (filename, "r")) == NULL) {cout << "Nao posso abrir o arquivo " << filename << "\n"; exit(2);} iptr = input_data; /* Inicialização */ setup (); initialize_all_weights(); // Inicializa Pesos initialize_threshold(); // Inicializa Threshold intera = 1; flag = true; // Condição de Fim das Iterações /* Treino */ if (argv[1][1] == 't') { while (flag) // Condição de repetição do treinamento { k = get_inputs (inputs); while (k) { cout << "Treinando no Conjunto " << dset << "\n"; compute_all_hidden(); compute_all_outputs();

115

/* Propagação dos erros nos pesos backward */ compute_training_outputs(); compute_output_error(); compute_hidden_error(); update_output(); update_hidden(); x = compute_error_term(); printf ("Set %d error term is %f\n", dset, x); k = get_inputs(inputs); dset++; } // Fim do While (k) x = compute_error_term(); if (operacao == 1) // Salva erros { if ((file_error = fopen ("error.dat", "a+")) == NULL) {cout << "Nao posso abrir o arquivo de Erros!!\n"; exit(2);} fprintf (file_error, "%d %f\n", intera, x); fclose (file_error); } if (x > 0.1) { fseek (iptr, 0L, SEEK_SET); intera++; } else flag = false; } // Fim do while (flag) } // Fim do if (argv[1][1]... /* Teste */ // Aplicando a NN em uma entrada if (argv[1][1] == 'u') { k = get_inputs(inputs); while (k) { if ((wptr = fopen ("weights2.dat", "rb")) == NULL) {cout << "Nao posso abrir arquivo de Pesos!\n";exit(2);} if ((thresh = fopen (“thresh.dat”, “rb”)) == NULL) {cout << "Nao posso abrir arquivo de Limiar!\n";exit(2);} for (i=0; i<NO_OF_INPUTS; i++) for (j=0; j<NO_OF_HIDDEN; j++) fread (&hweights[j][i], sizeof (float), 1, wptr); for (i=0; i<NO_OF_HIDDEN; i++) for (j=0; j<NO_OF_OUTPUTS; j++) fread (&oweights[j][i], sizeof (float), 1, wptr); for (i=0; i<NO_OF_OUTPUTS; i++) fread (&teta[i], sizeof(float), 1, thresh); compute_all_hidden(); compute_all_outputs(); print_outputs(); k = get_inputs(inputs); } // Fim do While (k) } // Fim do if (argv[1][1] ... fclose (input_data); input_data = NULL; iptr = NULL; save_weights(); fclose (wptr); fclose (thresh); } void save_weights () { FILE *f; FILE *f2; int i,j,k; if ((f = fopen ("weights.dat", "w+")) == NULL) {cout << "Nao posso abrir arquivo de Pesos!\n"; exit(1);} if ((f2 = fopen ("weights2.dat", "wb")) == NULL)

{cout << "Nao posso abrir arquivo de Pesos 2!\n"; exit(1);} fprintf (f, "Numero de Entradas: %d\nNumero de Neuronios na Camada Escondida: %d\nNumero de Saidas: %d\n", NO_OF_INPUTS, NO_OF_HIDDEN, NO_OF_OUTPUTS);

fprintf (f, "Learning Rate = %f\nMomentum = %f\n\n", learning_rate, momentum); k=0; fprintf (f, "Pesos na Camada Escondida\n\n"); for (i=0; i<NO_OF_INPUTS; i++) for (j=0; j<NO_OF_HIDDEN; j++) { fprintf (f, "%f ", hweights[j][i]); fwrite (&hweights[j][i], sizeof (float), 1, f2); k++; if (k > 5)

116

{fprintf (f, "\n"); k=0;} } fprintf (f, "\nPesos na Camada de Saída\n\n"); k = 0; for (i=0; i<NO_OF_HIDDEN; i++) for (j=0; j<NO_OF_OUTPUTS; j++) { fprintf (f, "%f ", oweights[j][i]); fwrite (&oweights[j][i], sizeof (float), 1, f2); k++; if (k>5) {fprintf (f, "\n"); k=0;} } fprintf (f, "\n"); fclose (f); } /* Computa a saída da Camada Escondida */ void compute_hidden (int node) { float x = 0; int i; for (i=0; i<NO_OF_INPUTS; i++) x += inputs[i]*hweights[node][i]; camada = 1; hidden[node] = output_function (x); vhidden[node] = x; } /* Computa a saída da Camada de Saída */ void compute_output (int node) { int i; float x = 0; for (i=0; i<NO_OF_HIDDEN; i++) x += hidden[i]*oweights[node][i]; x += teta[node]; camada = 2; outputs[node] = output_function (x); voutputs[node] = x; } /* Função de Ativação */ float output_function (float x) { return 1.0/(1.0 + exp((double)(-x))); } /* Derivada da Função de Ativação */ float of_derivative (float x) {

float a; a = output_function(x); if (camada == 2) return 1.0; /* Linear - na Camada de Saida*/ if (camada == 1) return a*(1 - a); /* Sigmoid - na Camada Escondida*/ } /* Calcula todos os nós da camada escondida */ void compute_all_hidden () { int i; for (i=0; i<NO_OF_HIDDEN; i++) compute_hidden (i); } /* Calcula os nós na camada de saída */ void compute_all_outputs () { int i; for (i=0; i<NO_OF_OUTPUTS; i++) compute_output (i); } /* Inicializa o peso */ float weight_init (void) { float aux, aux2; aux2 = 0; while (aux2 == 0) // Não permite Peso Zero!

117

{ aux = ((float) rand())/100000; aux2 = fabs(aux - 0.5); } return (aux2); } /* Inicializa todos os pesos */ void initialize_all_weights () { int i , j, aleat, sign; FILE *f5; randomize(); if ((f5 = fopen("weights0.dat", "w+")) == NULL) {cout << "Nao posso abrir arquivo de Pesos Iniciais!\n";exit(1);} fprintf (f5, "Pesos Iniciais na Camada Escondida:\n\n"); for (i=0; i<NO_OF_INPUTS; i++) for (j=0; j<NO_OF_HIDDEN; j++) { hweights[j][i] = weight_init(); aleat = rand() % 100; if (aleat >= 50) sign = 1; else sign = -1; // So para escolher aleatoriamente valores negativos e positivos parao Peso hweights[j][i] = hweights[j][i]*sign; fprintf (f5, "[%d][%d] = %f \n", j, i, hweights[j][i]); } fprintf (f5, "\nPesos Iniciais na Camada de Saida:\n\n"); for (i=0; i<NO_OF_HIDDEN; i++) for (j=0; j<NO_OF_OUTPUTS; j++) { oweights[j][i] = weight_init (); aleat = rand() % 100; if (aleat >= 50) sign = 1; else sign = -1; // Idem que o de antes oweights[j][i] = oweights[j][i]*sign; fprintf (f5, "[%d][%d] = %f \n", j, i, oweights[j][i]); } fclose (f5); } float threshold_init (void) { float aux, aux2; int sign; aux = 1; while ((aux > 0.1) || (aux < -0.1) || (aux == 0)) // Threshold entre -0.1 e 0.1 e diferente de /Zero { aux = (((float) rand())/100000); aux2 = rand() % 10; if (aux2 >= 5) sign = 1; else sign = -1; aux = aux*sign; // Escolhe um sinal aleatoriamente } return (aux); } /* Inicializa o Threshold */ void initialize_threshold () { int i; FILE *thresh, *thresh2; randomize(); if ((thresh = fopen("thresh0.dat", "w+")) == NULL) {cout << "Nao posso abrir arquivo de Threshold Iniciais!\n";exit(1);} if ((thresh2 = fopen("thresh.dat", "w+")) == NULL) {cout << "Nao posso abrir arquivo de Threshold!\n";exit(1);} fprintf (thresh, "Valores de Threshold:\n\n"); for (i=0; i<NO_OF_OUTPUTS; i++) { teta[i] = threshold_init(); fprintf (thresh, "[%d] = %f \n", i, teta[i]); fwrite (&teta[i], sizeof (float), 1, thresh2); } fclose (thresh); fclose (thresh2); }

118

/* Calcula o erro da camada de saída */ float compute_output_error () { int i; float x = 0.0;

for (i=0; i<NO_OF_OUTPUTS; i++) { camada = 2; err_out[i] = (should[i]-outputs[i]) * of_derivative(voutputs[i]); x += err_out[i]; } return x; } /* valor desejado */ void compute_training_outputs() { int i; cout << "A saída deve ser:\n"; cout << " A B C D E F G H I J K L M N O P Q R S T W X Y Z \n"; for (i=0; i<NO_OF_OUTPUTS; i++) { if (i==actual) should[i] = 1.0; else should[i] = 0.0; printf ("%5.1f ", should[i]); } cout << "\n"; } /* Calcula o erro do nó NODE da camada escondida */ float compute_hidden_node_error (int node) { int i; float x = 0.0, aux; for (i=0; i<NO_OF_OUTPUTS; i++) x += err_out[i]*oweights[i][node];

camada = 1; aux = of_derivative(vhidden[node]) * x; return (aux); } /* Calcula todos os termos de erros da camada escondida */ void compute_hidden_error () { int i; for (i=0; i<NO_OF_HIDDEN; i++) err_hidden[i] = compute_hidden_node_error(i); } /* Atualiza os pesos da camada de saída */ void update_output () { int i, j; for (i=0; i<NO_OF_OUTPUTS; i++) for (j=0; j<NO_OF_HIDDEN; j++) { old_oweights[i][j] = oweights[i][j]; oweights[i][j] += learning_rate*err_out[i]*hidden[j]; delta_oweights[i][j] = old_oweights[i][j] - oweights[i][j]; oweights[i][j] += delta_oweights[i][j]*momentum; } } /* Atualiza os pesos da camada escondida */ void update_hidden (void) { int i, j; for (i=0; i<NO_OF_HIDDEN; i++) for (j=0; j<NO_OF_INPUTS; j++) { old_hweights[i][j] = hweights[i][j]; hweights[i][j] += learning_rate*err_hidden[i]*inputs[j]; delta_hweights[i][j] = old_hweights[i][j] - hweights[i][j]; hweights[i][j] += delta_hweights[i][j]*momentum; } }

119

float compute_error_term () { int i; float x = 0.0; for (i=0; i<NO_OF_OUTPUTS; i++) x += (err_out[i]*err_out[i]); return x/2.0; } float * fvector (int n) { return (float *)malloc(sizeof(float)*n); } float **fmatrix (int n, int m) { int i; float *x, **y; y = (float **)malloc (sizeof(float)*n); x = (float *)malloc (sizeof(float)*n*m); for (i=0; i<n; i++) y[i] = &(x[i*m]); return y; } void setup (void) { inputs = fvector (NO_OF_INPUTS); hweights = fmatrix (NO_OF_HIDDEN, NO_OF_INPUTS); old_hweights = fmatrix (NO_OF_HIDDEN, NO_OF_INPUTS); delta_hweights = fmatrix (NO_OF_HIDDEN, NO_OF_INPUTS); hidden = fvector (NO_OF_HIDDEN); vhidden = fvector (NO_OF_HIDDEN); err_hidden = fvector (NO_OF_HIDDEN); oweights = fmatrix (NO_OF_OUTPUTS, NO_OF_HIDDEN); old_oweights = fmatrix (NO_OF_OUTPUTS, NO_OF_HIDDEN); delta_oweights = fmatrix (NO_OF_OUTPUTS, NO_OF_HIDDEN); outputs = fvector (NO_OF_OUTPUTS); voutputs = fvector (NO_OF_OUTPUTS); err_out = fvector (NO_OF_OUTPUTS); teta = fvector (NO_OF_OUTPUTS); should = fvector (NO_OF_OUTPUTS); } int get_inputs (float *x) {

int i, k, letra; unsigned char dado; for (i=0; i<NO_OF_INPUTS; i++) { fread (&dado, sizeof (unsigned char), 1, iptr); k = (int) dado; x[i] = k; if (k<1) return 0; x[i]/= 255; } if (operacao == 1) // Se for Treino { for (i=0; i<NO_OF_OUTPUTS; i++) { fread (&dado, sizeof(unsigned char), 1, iptr); letra = (int) dado; if (letra == 1) actual = i; } } return 1; } void print_outputs () { int i, j; j = 0; for (i=0; i<NO_OF_OUTPUTS; i++) { printf ("%6.3f ", outputs[i]); if (outputs[i] > outputs[j]) j = i; } printf ("Atual NN classificada como %d\n", j); }