Camillo Jorge Santos Oliveira
Classificação de Imagens Coletadas na Web
Dissertação apresentada ao Curso de
Mestrado do Departamento da Ciência da
Computação do Instituto de Ciências
Exatas da Universidade Federal de Minas
Gerais, como requisito parcial à obtenção
do título de Mestre em Ciência da
Computação.
Universidade Federal de Minas Gerais
Belo Horizonte, 20 de Agosto de 2001
© 2001
Camillo J. S. Oliveira
Todos os Direitos Reservados
Oliveira, Camillo Jorge Santos.
519.6
Classificação de imagens coletadas na Web/Camillo Jorge Santos Oliveira. –
O48c Belo Horizonte: DCC/ICEx/UFMG, 2001
73p.: il.
Dissertação (Mestrado) – Universidade Federal de Minas Gerais. Curso de Pós
Graduação em Ciência da Computação. Orientador: Arnaldo de Albuquerque
Araújo.
1. Processamento digital de imagens. 2. Inteligência Artificial. 3. World Wide
Web (Sistemas de recuperação da informação). I. Araújo, Arnaldo de
Albuquerque. II. Universidade Federal de Minas Gerais, Departamento de
Ciência da Computação. III. Título.
iii
À minha esposa LINNYER
DEDICO
iv
Agradecimentos
A Deus.
À minha esposa, Linnyer Beatrys pelo incentivo, confiança, orgulho e dedicação, de todos
os dias.
Ao Prof. Dr. Arnaldo Albuquerque pela determinação ao orientar este trabalho.
Aos professores e funcionários do Programa de Pós-Graduação do Departamento de
Ciência da Computação da UFMG, aqui representados pelo coordenador do curso Prof.
Henrique Pacca, pela secretária Renata Viana Moraes e pelo funcionário da biblioteca
Helvécio, agradecendo pela oportunidade e atenção dispensada ao longo do curso.
Aos meus colegas Silvio (Magnânimo) e Paulo (Marinheiro) pelas contribuições positivas
ao meu trabalho e ao meu estresse através de discussões, comentários e sugestões.
Aos colegas do Núcleo de Processamento Digital de Imagens, em especial ao Carlos
(kapaoc) pela cooperação e atenção dispensada às minha mais diversas solicitações e ao
Daniel (Patrullero) por sua participação.
Aos amigos Flávio Bortolozzi e Hélio Olímpio da Rocha que apoiaram-me de maneira
crucial ao longo da minha vida acadêmica.
Aos casais Vera e Artur, Léia e Josuel pelas palavras de apoio e motivação e por suas
orações que foram fundamentais para esta empreitada.
v
Sumário
INTRODUÇÃO...............................................................................................................................................................11
1.1 M OTIVAÇÃO ............................................................................................................................................................ 12
1.2 P ROBLEMA A BORDADO ......................................................................................................................................... 15
1.3 ESTRUTURA DA DISSERTAÇÃO ............................................................................................................................. 18
REVISÃO BIBLIOGRÁFICA....................................................................................................................................19
2.1 P ROCESSO DE COLETA DAS IMAGENS.................................................................................................................. 19
2.2 M ÉTRICAS ................................................................................................................................................................ 21
2.3 CLASSIFICAÇÃO ...................................................................................................................................................... 26
2.4 O M ÉTODO ID3....................................................................................................................................................... 27
2.5 CONSIDERAÇÕES FINAIS........................................................................................................................................ 34
MATERIAIS E MÉTODOS.........................................................................................................................................35
3.1 DADOS DA COLETA DE IMAGENS.......................................................................................................................... 36
3.2 P REPARAÇÃO DAS A MOSTRAS DE TREINAMENTO ............................................................................................. 36
3.3 A PLICAÇÃO DAS M ÉTRICAS .................................................................................................................................. 37
3.4 UTILIZAÇÃO DO ID3 ............................................................................................................................................... 38
3.5 M ÉTODOS PARA VALIDAR O MODELO ................................................................................................................ 40
3.6 ESCOLHA DO M ÉTODO PARA VALIDAÇÃO DO M ODELO................................................................................... 46
3.7 VALIDAÇÃO DO CLASSIFICADOR.......................................................................................................................... 47
3.8 CONSIDERAÇÕES FINAIS........................................................................................................................................ 49
RESULTADOS EXPERIMENTAIS .........................................................................................................................50
4.1 RESULTADOS UTILIZANDO O MÉTODO DE VALIDAÇÃO CRUZADA COM K-DOBRAS ................................... 50
4.2 RESULTADOS EXPERIMENTAIS UTILIZANDO IMAGENS INÉDITAS ................................................................... 55
4.2 EXCEÇÕES NAS A MOSTRAS DE TREINAMENTO .................................................................................................. 57
4.3 CONSIDERAÇÕES FINAIS........................................................................................................................................ 57
CONCLUSÃO..................................................................................................................................................................59
5.1 CONTRIBUIÇÕES...................................................................................................................................................... 59
5.2 TRABALHOS FUTUROS ........................................................................................................................................... 61
REFERÊNCIAS BIBLIOGRÁFICAS ......................................................................................................................62
APÊNDICE A...................................................................................................................................................................65
APÊNDICE B ...................................................................................................................................................................69
APÊNDICE C...................................................................................................................................................................72
6
Lista de Figuras
Pag
1.1 – Exemplo de imagem fotográfica no formato JPEG e seu respectivo histograma de cores. 16
1.2 – Exemplo de imagem fotográfica no formato GIF e seu respectivo histograma de cores.
16
1.3 – Exemplo de imagem gráfica no formato JPEG e seu respectivo histograma de cores.
17
1.4 – Exemplo de imagem gráfica no formato GIF e seu respectivo histograma de cores.
17
2.1 – (a) Imagem gráfica no formato GIF. (b) Histograma de cores.
21
2.2 – (a) Imagem gráfica no formato GIF. (b) Histograma de cores.
22
2.3 – Exemplo de uma árvore de decisão.
32
3.1 – Coleta de imagens na WWW.
36
3.2 – Processo de separação visual das imagens, da base de imagens, formando as amostras 37
de treinamento.
3.3 – Quatro imagens e suas respectivas tuplas obtidas depois da aplicação das métricas.
39
3.4 – Esboço do método de validação com divisão em duas partes.
41
3.5 – Esboço do método de validação cruzada com subamostragem aleatória..
43
3.6 – Esquema mostrando o exemplo do método de validação cruzada com 4-dobras.
44
3.7 – Esquema mostrando o exemplo do método de validação cruzadas com “um de fora”.
45
4.1 – Taxas de erro obtidas para amostras de imagens que possuem o formato GIF.
51
4.2 – Desvio padrão das taxas de erro para amostras de imagens que possuem o formato GIF. 52
4.3 – Taxas de erro obtidas para amostras de imagens que possuem o formato JPEG.
53
4.4 – Desvio padrão das taxas de erro para amostras de imagens que possuem o formato 53
JPEG.
4.5 – Número médio de iterações para imagens no formato GIF.
54
4.6 – Número médio de iterações para imagens no formato JPEG.
55
4.7 – Taxas de classificação para imagens no formato GIF, onde obteve-se uma média de 56
92,3% de imagens classificadas corretamente.
4.8 – Taxas de classificação para imagens no formato JPEG, onde obteve-se uma média de 56
89,5% de imagens classificadas corretamente.
4.9 – Alguns exemplos de imagens que não foram classificadas corretamente
57
B1 – Gráficos obtidos da avaliação das amostras de treinamento formadas por imagens GIF.
70
B2 – Gráficos obtidos da avaliação das amostras de treinamento formadas por imagens JPEG. 71
C1 – Exemplos de imagens gráficas coletadas na WWW
72
C2 – Exemplos de imagens gráficas coletadas na WWW
72
C3 – Exemplos de imagens gráficas coletadas na WWW
73
7
Lista de Tabelas
Pag
A1 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 200.
65
A2 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 400.
65
A3 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 800.
65
A4 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 1000.
66
A5 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 1200.
66
A6 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 200.
66
A7 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 400.
67
A8 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 800.
67
A9 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 1000.
67
A10 – Valores das taxas de erro obtidas para o método de validação cruzada com kdobras, para k = 2, 4, 5, 8 e 10, em amostras de tamanho igual a 1200.
67
A11 – Resultados da classificação de imagens que possuem o formato GIF e JPEG
que não foram utilizadas na obtenção da árvore de decisão (treinamento).
68
8
Lista de Abreviaturas
CLS
Concept Learning System
GIF
Graphics Interchange Format
HTML
Hypertext Markup Language
ID3
Itemized Dichotomizer 3
JPEG
Joint Photographics Experts Group
NPDI
Núcleo de Processamento Digital de Imagens
RAM
Random Access Memory
RGB
Red Green Blue
SGBD
Sistema Gerenciador de Banco de Dados
TDIDT
Top-Down Induction Decision Tree
UFMG
Universidade Federal de Minas Gerais
URL
Universal Resource Locator
VoD
Video on Demand
WWW
World Wide Web
9
Resumo
O objetivo deste trabalho é o desenvolvimento de um classificador que permita separar
imagens coletadas na WWW (World Wide Web) em duas classes semânticas: imagens
fotográficas e imagens gráficas. Imagens fotográficas incluem cenas naturais, como
pessoas, faces, animais, flores, paisagens e cidades. Imagens gráficas são logotipos,
desenhos, ícones, mapas e panos de fundo, geralmente gerados utilizando o computador.
O desenvolvimento do classificador envolve as seguintes atividades: coleta das
imagens na WWW realizada através do uso de um robô; preparação das amostras de
treinamento; estudo, definição, implementação e aplicação de métricas (número de cores,
cor predominante, vizinho mais distante, saturação, histograma de cor, histograma do
vizinho mais distante, razão de dimensão, dimensão menor) baseadas nas diferenças entre
as duas classes em questão; disponibilização dos valores resultantes das métricas em tuplas
de atributos com valores normalizados e utilização destas tuplas da amostra de treinamento
na construção do classificador utilizando método supervisionado ID3 (Itemized
Dichotomizer 3). O resultado deste desenvolvimento é o classificador que inclui uma
árvore de decisão geradora de regras para a classificação.
Um esquema de validação do classificador é utilizado. Este esquema é implementado
através de dois procedimentos. O primeiro utiliza o método de validação cruzada com kdobras nas amostras de treinamento já disponíveis e seus resultados demonstraram a
estabilidade do aprendizado do classificador, com taxa média de erro de 9,2% quando
aplicado o método de validação cruzada com 10-dobras. O segundo procedimento de
validação consiste em utilizar o classificador com imagens inéditas (imagens não utilizadas
para construir o classificador) e verificar-se a precisão da classificação. Obteve-se uma
média de 91% de imagens classificadas corretamente. O desenvolvimento deste trabalho
demonstra a viabilidade de se construir classificadores que possam ser utilizados em
ferramentas de recuperação de imagens com base no conteúdo.
10
Abstract
The purpose of this work is the development of a classifier that allows to separate images
collected from the WWW (World Wide Web) into two semantic classes: photographs and
graphics. Photographs images include natural scenes such as people, faces, animals,
flowers, landscapes and cities. Graphics images are logotypes, drawings, icons, maps and
backgrounds walls, generally created by a computer.
The development of the classifier includes the following steps: image collecting on the
WWW using a robot; preparation of training samples; study, definition, implementation,
and application of the metrics (the number of colors, the percentage of the prevalent color,
the farthest neighbor, the saturation, the color histogram, the farthest neighbor histogram,
the dimension ratio, the smallest dimension) based on the differences between the two
classes mentioned; availability of the metrics output in tuples of attributes with normalized
values and utilization of these training sample tuples in the construction of the classifier
using the supervisioned method ID3 (Itemized Dichotomizer 3). The result of this
development is the classifier that includes a decision tree which is responsible for
generating the rules for classification.
A classifier validation schema is used. This schema is implemented by two
procedures. The first uses k-fold cross-validation method on the training samples already
available and its results demonstrated the stability of the classifier learning, reaching an
average tax error of 9,2% when the cross-validation method is applied with ten-folds. The
second validation procedure consists in utilize the classifier with unseen images (images
that were not used to construct the classifier) and verify the precision of classification. We
obtained an average of 91% of images classified correctly. The development of this work
demonstrates the viability in constructing classifiers that can be used in image retrieval
based on content tools.
11
Capítulo 1
Introdução
Esta dissertação apresenta uma proposta de classificação de imagens coletadas na WWW
(World Wide Web). A classificação agrupa as imagens em duas classes semânticas de
grande importância e abrangência, que são, imagens fotográficas e imagens gráficas.
Com a expansão da WWW tem-se a inclusão de uma imensa quantidade de
informações que são colocadas à disposição do usuário da rede, como: vídeos, documentos
texto e imagens. Além disso, um outro fator de grande importância é a velocidade com que
estas imagens, são adicionada à rede.
Assim, faz-se necessário a utilização de ferramentas capazes de recuperar imagens
deste ilimitado ambiente que é a WWW. Em 1970, foram iniciadas pesquisas na área de
recuperação de imagens. Nesta época, tais pesquisas eram desenvolvidas por pesquisadores
da área de banco de dados e que tratavam de fazer a recuperação das imagens baseada em
texto. As características das imagens eram anotadas na forma de texto e depois utilizava-se
um SGBD (Sistema Gerenciador de Banco de Dados) para tratar da recuperação das
informações. Em 1990, surgiu uma nova abordagem que permitiu de fato, trabalhar com
imagens. Imagens estas que aumentaram em larga escala na WWW. A idéia principal desta
abordagem é realizar a recuperação das informações baseada nos conteúdos das imagens,
tais como cor, forma e textura. Desta maneira, muitas técnicas têm sido desenvolvidas com
base nesta linha de pesquisa e muitos sistemas de recuperação baseados no conteúdo foram
construídos. Alguns, citados em Bimbo (1999), são: QBIC, Virage, Visual Retrievalware,
Macs-Hermes, Chabot, IRIS, Picasso, ICARS, Photobook, CANDID, VisualSeek,
FIBSSR, CORE e NeTra. Uma área que contribui de forma relevante para esta abordagem
é a visão computacional.
12
Até o momento, não existem algoritmos genéricos para processar todos os tipos de
imagens e a diversidade destes tipos, bem como o tamanho ocupado por estas imagens. A
etapa de classificação das imagens torna-se importantíssima para o desenvolvimento de
uma ferramenta de recuperação de imagens para a WWW. As imagens podem pertencer a
classes semânticas diferentes, tais como fotografias, gráficos, mapas, caricaturas, retratos
de pessoas, cartões, faces, imagens coloridas e etc. Após a classificação, pode-se então
realizar a pesquisa por classes.
Esta dissertação tem por objetivo apresentar a viabilidade de classificação de imagens
coletadas na WWW em duas classes semânticas: imagens fotográficas e imagens gráficas.
1.1 M OTIVAÇÃO
Recentemente, tem-se visto um rápido crescimento no tamanho das coleções de imagens
digitais. Todos os dias, equipamentos militares e civis geram gigabytes de imagens. Gupta
(1997) relata que o sistema de observação da terra, desenvolvido e operado pela NASA,
deverá gerar um terabyte de dados de imagens por dia quando em total operação. Em
conseqüência, não se pode acessar ou fazer uso da informação sem que esta esteja
organizada, permitindo uma navegação, pesquisa e recuperação. A recuperação de imagens
representa uma área de pesquisa muito ativa desde o início da década de 1970 e tem
recebido a contribuição de duas grandes linhas de pesquisas que seriam o gerenciamento
de banco de dados e a visão computacional. Estas duas linhas de pesquisas estudam a
recuperação de imagens sob dois ângulos diferentes, um sendo baseado em textos e o outro
baseado no conteúdo visual (Rui, 1999).
Como visto, a recuperação de imagens baseada em texto era uma maneira muito
popular de se recuperar a imagem, primeiro descrevendo a imagem de texto e então usando
sistemas de gerenciamento de banco de dados baseados em textos para executar a
recuperação da imagem. Muitos avanços, tais como modelagem de dados, indexação
multidimensional e avaliação de consultas, tem sido realizados ao longo das pesquisas.
Contudo, Rui (1999) afirma que existem duas grandes dificuldades, especialmente, quanto
ao tamanho das coleções de imagens que são grandiosas. A primeira dificuldade é a vasta
quantidade de trabalho requerido na anotação manual das imagens. A segunda dificuldade,
que é mais essencial, resulta do rico conteúdo das imagens e a subjetividade humana de
percepção. Isto é, para um mesmo conteúdo de imagem, diferentes pessoas possuem
13
percepções diferentes. Para Rui (1999), a subjetividade da percepção e anotações
imprecisas podem causar, mais tarde, perdas irrecuperáveis no processo de recuperação.
Do ano de 1990 em diante, por causa da emergência em larga escala das coleções de
imagens, as dificuldades encontradas pela anotação manual tornaram-se mais agudas. A
fim de superar estas dificuldades, foi proposta a recuperação de imagens baseada no
conteúdo. Ou seja, em vez de serem anotadas manualmente por chaves baseadas em texto,
as imagens são indexadas pelo seu próprio conteúdo visual, tal como, cor, forma e textura.
Para Gupta (1997), a recuperação de imagens emergiu como uma área de pesquisa
importante com muitas aplicações em vários campos, como banco de dados de imagens,
multimídia e bibliotecas digitais.
Segundo Vailaya (1998), a organização e a recuperação de imagens baseada no
conteúdo emergiu como uma área importante da visão computacional e da multimídia,
devido ao desenvolvimento rápido das imagens digitais, do armazenamento e da tecnologia
das redes.
A expansão da WWW é fato. Para Abbadeni (1999), a WWW é hipermídia grande,
distribuída e um sistema de informação não estruturado. A cada dia, novos documentos,
entre os quais muitas imagens, são adicionados na Web. Para melhor organizar e recuperar
esta quase ilimitada informação, máquinas de busca na Web são altamente desejadas (Rui,
1999).
A Web é uma complexa e grande fonte de informação multimídia. É estimado que
existam 180 milhões de imagens públicas na Web e que ocupem aproximadamente três
terabytes. Cada vez mais imagens digitais são adicionadas e retiradas na Web todos os dias.
A necessidade de encontrar uma imagem dentro de uma coleção digital específica na Web
é importante para muitos grupos de usuários, incluindo jornalistas, engenheiros,
historiadores, designers, professores, artistas e agências de propagandas, entre outros. A
tecnologia de acesso às imagens vem mudando rapidamente e a forma como as pessoas
interagem com a informação visual ultrapassa nossa compreensão (Goodrum, 2001).
Segundo Goodrum (2001), mais e mais pessoas e organizações carregam imagens para
a Web, desta forma, a pesquisa e recuperação de imagens tem se tornado o maior desafio
para os pesquisadores e desenvolvedores.
O desenvolvimento de ferramentas que permitam agrupar imagens em categorias
semanticamente significativas, que utilizam características visuais de baixo nível, tornou-
14
se fundamental dentro do cenário apresentado. Este desenvolvimento representa uma
solução para o desafio da recuperação de imagens baseada no conteúdo.
Ferramentas tornarão possíveis as buscas de imagens específicas em um banco de
dados grande e de utilidade inquestionável e darão à WWW todo seu potencial (Abbadeni,
1999).
Para Abbadeni (1999), a busca por imagens no contexto da WWW é uma tarefa
extremamente difícil e se apresenta como um novo desafio. Três características são
relevantes em se tratando de imagens na WWW:
•
o tamanho inacreditavelmente grande de todas estas imagens (espaço ocupado
em disco);
•
a diversidade extraordinária de tipos de imagens que podem ser encontrados na
WWW;
•
no campo do processamento de imagens e visão computacional, não existe um
algoritmo de uso geral capaz de processar todos os tipos de imagens.
Diante destas características, uma etapa de classificação é fundamental antes do
desenvolvimento de uma ferramenta de recuperação de imagens para a WWW, isto porque,
tais imagens podem pertencer a classes semânticas diferentes, como fotografias, gráficos,
mapas, caricaturas, retratos de pessoas, cartões, faces, imagens coloridas, etc. Após a
classificação, pode-se então fazer a pesquisa por classes semânticas. Desta forma,
Abbadeni (1999) afirma que surgem duas vantagens imediatas:
•
uma melhoria efetiva, onde os ruídos são reduzidos, pois a pesquisa é feita em
uma classe específica e não em todo o banco de dados;
•
podem ser aplicados algoritmos apropriados a cada classe de imagens, uma vez
que não existem algoritmos genéricos (de uso comum) para todas as classes.
A classificação semântica das imagens pode ser realizada de diversas maneiras. Um
exemplo é mostrado por Vailaya (1998), que separa fotografias de paisagens e fotografias
de cidades (construções), ou ainda, como mostram Guérin-Dungué (2000) e Szumer
(1998), a classificação de imagens fotográficas com cenas de ambientes internos e
externos.
Para Guérin-Dungué (2000) a classificação de cenas do mundo real em categorias
semânticas é um desafio aberto na análise de imagens. Com o aumento da viabilidade de
15
base de dados de imagens e vídeos, há uma necessidade crucial por métodos automáticos
de indexação baseado no conteúdo.
1.2 P ROBLEMA ABORDADO
Para realizar a classificação semântica das imagens coletadas na WWW, objetivo deste
trabalho, é necessária a especificação de métricas capazes de diferenciar os dois tipos de
imagens em questão. As métricas são procedimentos que aplicados a uma imagem,
retornam um valor numérico capaz de permitir a classificação destas imagens. Estas
métricas estão baseadas nas diferenças entre imagens fotográficas e imagens gráficas.
A coleta das imagens, que serão submetidas à classificação, é realizada por um robô.
O robô recebe como entrada uma lista contendo a URL (Universal Resource Locator) de
vários servidores. Para cada servidor, é analisado o seu arquivo HTML (Hypertext Markup
Language) e extraídas as ligações (links) para outras páginas HTML e os endereços de
todas as imagens de extensão JPEG (Joint Photographics Experts Group) e GIF (Graphics
Interchange Format) encontradas no arquivo HTML, realizando assim a recuperação das
imagens e gravando-as em disco local.
A partir da base de imagens coletada através do robô, aplicam-se métricas para
distinguir as duas classes de imagens, que seriam as imagens fotográficas (Figura 1.1(a) e
Figura 1.2(a)) e as imagens gráficas (Figura 1.3(a) e Figura 1.4(a)). Imagens fotográficas
são as imagens que incluem cenas naturais, como pessoas, faces, flores, animais, paisagens
e cidades (Abbadeni, 1999; Athitsos, 1998; Frankel, 1996).
Algumas características apresentadas pelas imagens fotográficas, podem ser
comprovadas observando a Figura 1.1 e a Figura 1.2, são:
•
Descrevem objetos do mundo real;
•
Ausência de regiões com cores constantes, isto é, os objetos tendem a possuir
textura;
•
Tendem a ser imagens quadradas, com pouca diferença na razão de aspecto
(altura x largura);
•
Pouca incidência de regiões com altas saturações de cores;
•
Possuem um maior número de cores utilizadas.
16
Tanto a Figura 1.1 como a Figura 1.2 mostra uma imagem fotográfica e seu respectivo
histograma de cores no modelo de formação da cor RGB (Red, Green e Blue), onde cada
pixel possui uma certa quantidade de cor em cada canal (Vermelho, Verde e Azul). Cada
canal varia dentro do intervalo de [ 0, 255] (256 cores para cada canal). Analisando o
histograma de cores (cor x probabilidade que ocorre a cor (p(cor)), pode-se observar o
número de cores, a cor que mais predomina, cores que não existem e inclusive podemos
(de maneira qualitativa) observar a transição entre os pixels da imagem (mais acentuados
ou menos acentuados).
Figura 1.1 – Exemplo de imagem fotográfica no formato JPEG e seu respectivo
histograma de cores.
Figura 1.2 – Exemplo de imagem fotográfica no formato GIF e seu respectivo histograma
de cores.
As imagens gráficas seriam logotipos, desenhos, mapas, botões e ícones, geralmente
gerados pelo computador (Abbadeni, 1999; Athitsos, 1998; Frankel, 1996).
17
Algumas características apresentadas pelas imagens gráficas, que podem ser
comprovadas observando a Figura 1.3 e a Figura 1.4, são:
•
Tendem a possuir grandes regiões cobertas pela mesma cor;
•
Possuem menor número de cores utilizadas;
•
As bordas dos objetos tendem a ser mais aguçadas (bem definidas);
•
Tendem a ser imagens com grande diferença na razão de aspecto (altura x
largura);
•
Tendem a possuir um tamanho menor que as imagens fotográficas;
•
Geralmente, possuem regiões cobertas com cores saturadas.
Figura 1.3 – Exemplo de imagem gráfica no formato JPEG e seu respectivo histograma de
cores.
Figura 1.4 – Exemplo de imagem gráfica no formato GIF e seu respectivo histograma de
cores.
18
As métricas elaboradas, implementadas e aplicadas nas imagens coletadas apresentam
como resultado deste processo, um vetor de características extraídas para cada imagem, a
este vetor, chama-se tupla. Após a obtenção das tuplas resultantes das métricas, faz-se a
normalização dos valores dos atributos e obtém-se as amostras de treinamento. O problema
a ser abordado a partir das amostras refere-se ao processo de desenvolvimento de um
classificador para os tipos de imagens envolvidas e a determinação de processos de
validação para o classificador proposto.
1.3 ESTRUTURA DA DISSERTAÇÃO
Nas seções anteriores pode-se notar a importância, nos dias atuais, da separação das
imagens em classes semânticas visando a recuperação das imagens na Web. Nos demais
capítulos desta dissertação encontram-se todos os aspectos relacionados com a proposta de
classificação em imagens fotográficas e as imagens gráficas.
No Capítulo 2, tem-se uma revisão bibliográfica, onde são feitas as descrições do robô
utilizado para a coleta das imagens, a descrição das métricas utilizadas para distinguir os
dois tipos de classes de imagens (fotográficas e gráficas). Por fim, a descrição da
classificação empregando o método de classificação supervisionado ID3.
O Capítulo 3 apresenta os materiais e métodos utilizados nas etapas de
desenvolvimento quais sejam, coleta de imagens, preparação das amostras de treinamento,
aplicação das métricas, obtenção do classificador e validação do método de classificação
proposto.
No Capítulo 4, estão dispostos os resultados dos experimentos. Através da observação
dos dados dispostos na forma de gráficos, pode-se observar a viabilidade de utilização do
classificador.
O Capítulo 5 conclui o trabalho apresentando as contribuições e propostas para
trabalhos futuros.
19
Capítulo 2
Revisão Bibliográfica
Aplicações recentes em sistemas multimídia têm gerado a necessidade da utilização de
ferramentas para a recuperação de imagens na WWW. Conforme apresentado no Capítulo
1, nota-se o problema relacionado com a quantidade de imagens incluídas diariamente na
WWW e a necessidade de uma classificação destas imagens em grupos semânticos, o que
pode ser realizado utilizando a abordagem que utiliza informações baseadas no conteúdo
visual das imagens como: cor, forma e textura.
Este Capítulo provê um estudo prospectivo sobre os principais conceitos envolvidos
no desenvolvimento do classificador proposto. Neste estudo, estão incluídos a descrição da
coleta das imagens, a descrição das métricas e a descrição do método supervisionado de
classificação ID3.
A Seção 2.1 apresenta a descrição do processo de coleta das imagens na WWW
utilizando um robô. A Seção 2.2 reúne as considerações sobre as métricas e os conceitos
fundamentais envolvidos com o processo de caracterização das diferenças entre imagens
fotográficas e imagens gráficas. A Seção 2.3 tece comentários sobre a classificação e
finalmente a Seção 2.4 descreve o método de classificação supervisionado ID3 utilizado
neste trabalho.
2.1 P ROCESSO DE COLETA DAS IMAGENS
A coleta das imagens na WWW é realizada utilizando-se um robô. Desenvolvido
inicialmente no Laboratório de Vídeo sob Demanda (VoD - Video on Demand) do
Departamento de Ciência da UFMG (Universidade Federal de Minas Gerais). Trata-se de
20
um programa capaz de recuperar imagens disponíveis na WWW, que possuem o formato
JPEG e GIF. Basicamente o programa tem como entrada um arquivo texto contendo uma
lista de URL´s da Internet, recuperando os arquivos HTML dos servidores indicados pela
URL. O robô extrai as ligações (links) para outras páginas HTML, extrai as localizações das
imagens, recupera as imagens e grava as mesmas em disco.
Para organizar a recuperação dos arquivos, o robô implementa uma árvore binária.
Cada nodo da árvore binária representa um servidor a ser pesquisado. Para cada servidor
pesquisado, existe uma outra árvore binária que armazena as URL´s pertencentes a um
servidor da lista de servidores de entrada do programa robô. Cada nodo das árvores possui
uma variável de estado, indicando se a URL já está sendo coletada ou não.
Para cada servidor, o programa robô cria um diretório local no disco com o mesmo
nome da URL. Arquivos recuperados de um servidor são salvos neste diretório, sob o
mesmo nome do diretório de sua localização usada no servidor remoto. Assim, tem-se uma
árvore de diretórios exatamente igual à analisada no servidor remoto.
O robô foi implementado utilizando threads o que caracteriza um sistema concorrente.
Threads são disparadas pelo programa robô durante a sua execução, sendo responsáveis
pela recuperação dos arquivos. A execução utilizando threads é importante pois se a
execução fosse seqüencial, o programa robô seria muito lento, sob dois aspectos:
•
o robô faz freqüentemente requisições de entrada e saída e isto é sempre um
procedimento instável sobre o ponto de vista de tempo;
•
existem muitas regras a serem respeitadas e seguidas pelos robôs na Internet.
Uma delas é crítica, onde o robô não pode fazer mais que uma requisição de
arquivo no mesmo servidor em um período de 60 segundos, assim o robô deve
esperar 60 segundos depois de cada arquivo recuperado de um servidor.
Cada thread disparada trabalha da seguinte maneira: inicialmente pesquisa um
servidor que não está sendo utilizado por outra thread, isto é, somente uma thread pode
coletar imagens de um servidor por vez. A thread faz a pesquisa da URL na árvore de
URL´s e recupera esta. Toda vez que a thread recupera um arquivo texto (extensão .html),
o seu conteúdo é analisado para verificação das ligações para outras páginas. Neste
momento, a árvore binária de servidores URL pode crescer – cada nova ligação de servidor
ou arquivos HTML são inseridos na árvore binária de URL´s. Da mesma forma, se um
21
novo servidor é encontrado, este é inserido na árvore binária de servidores. Após cada
recuperação, a thread é forçada a parar por 60 segundos.
2.2 M ÉTRICAS
Na construção de um classificador de imagens, são necessários procedimentos, que quando
aplicados sobre as imagens informem a classe (imagens fotográficas ou imagens gráficas) à
qual pertencem. Estes testes (procedimentos) são construídos a partir de métricas que são
baseadas nas diferenças entre as duas classes em questão. Imagens fotográficas e imagens
gráficas tendem a possuir diferentes faixas de valores obtidas com as métricas, com isto
consegue-se distinguir os dois tipos de imagens. As métricas, que serão descritas na
seqüência, foram obtidas de Athitsos (1998).
Número de Cores
O valor utilizado para esta métrica é o número de cores distintas que aparecem na imagem.
Leva-se em consideração o RGB, ou seja, todos os canais (Red, Green, Blue) junto.
Imagens gráficas possuem menor número de cores utilizadas, como pode ser
observado, comparando-se os histogramas apresentados, na Figura 2.1(b) e na Figura
2.2(b), fica bem evidente que a imagem da Figura 2.1(a) possui um menor número de cores
utilizadas que a imagem da Figura 2.2(a).
A normalização é feita dividindo-se o valor obtido por ( L arg ura × Altura) , que são as
dimensões da imagem em pixels.
Figura 2.1 – (a) Imagem gráfica no formato GIF. (b) Histograma de cores.
22
Figura 2.2 – (a) Imagem fotográfica no formato GIF. (b) Histograma de cores.
Porcentagem da Cor Predominante
Esta métrica consiste em encontrar a porcentagem da cor mais freqüente na imagem. O
valor calculado é o número de pixels da cor predominante expresso em porcentagem.
Imagens gráficas possuem um número pequeno de cores e grandes regiões com a mesma
cor. Imagens gráficas possuem um valor calculado maior que o das imagens fotográficas.
Comparando os histogramas apresentados, na Figura 2.1(b) e na Figura 2.2(b) observa-se a
porcentagem da cor que mais ocorre. Note que a imagem gráfica da Figura 2.1(a) possui
uma cor que aparece em 57% dos seus pixels. Já na imagem fotográfica da Figura 2.2(a)
possui uma cor que aparece em 10% dos pixels da imagem.
A normalização é feita dividindo-se o valor obtido por ( L arg ura × Altura) , que são as
dimensões da imagem em pixels.
Vizinho Mais Distante
A métrica do vizinho mais distante baseia-se na transição de cores que aparecem tanto em
imagens gráficas como em imagens fotográficas. Imagens gráficas possuem regiões com
cores constantes e possuem transições de cores bem pronunciadas (visíveis).
Para dois pontos
p1 e
p 2 , com vetor de cores ( r1 , g 1 , b1 )
respectivamente, define-se distância de cor d como:
d = r1 − r2 + g1 − g 2 + b1 − b2 .
e ( r2 , g 2 , b2 )
23
Desde que o intervalo de cores varie de 0 até 255, o intervalo para a distância de cor
varia de 0 até 765.
Cada pixel p1 (exceto os das bordas da imagem) possui vizinhos acima, abaixo, à
direita e à esquerda. Um vizinho p 2 de p1 é considerado o vizinho mais distante de p1 se
a distância de cor entre p1 e p 2 for maior ou igual que a distância entre p1 e qualquer um
dos seus vizinhos. Define-se valor de transição de p1 , como a distância entre p1 e seu
vizinho mais distante.
Nesta métrica, deve-se especificar o parâmetro P que varia entre 0 e 765. O valor
obtido para a imagem é o número de pixels que tem um valor de transição maior ou igual a
P (Athitsos, 1998).
Desde que imagens gráficas possuam grandes regiões com a mesma cor, elas possuem
muitos pixels cujo valor de transição é zero. Conseqüentemente, se P for igual a 1 (um),
espera-se, como regra, valores calculados maiores para imagens fotográficas que imagens
gráficas.
A normalização é feita dividindo-se o valor obtido por ( L arg ura × Altura) , que são as
dimensões da imagem em pixels.
Existe uma segunda versão desta mesma métrica para acentuar as diferenças dos
valores calculados, entre imagens gráficas e imagens fotográficas, que gera valores altos de
P . Nesta segunda versão, o valor calculado em uma imagem é o número f 1 de pixels com
valor de transição maior ou igual a P , dividido pelo número f 2 de pixels com valor de
transição maior que 0 (zero). Desde que f 2 tenda a ser grande para imagens fotográficas,
imagens gráficas têm valores calculados maiores em relação às imagens fotográficas.
Saturação
Esta métrica é baseada na saturação das cores. Cores altamente saturadas são mais comuns
em imagens gráficas do que em imagens fotográficas.
Para um pixel p com vetor de cor ( r , g , b) , seja m o máximo e n o mínimo entre o
r, g e b . O nível de saturação de p é definido por m − n .
É especificado um parâmetro P . O valor calculado de uma imagem é o número de
pixels com nível de saturação maior ou igual à P . Para valores altos de P , esperam-se
24
valores calculados maiores para as imagens gráficas, desde que as cores saturadas ocorram
mais freqüentemente em imagens gráficas.
A normalização é feita dividindo-se o valor obtido por ( L arg ura × Altura) , que são as
dimensões da imagem em pixels.
Histograma de Cor
A métrica do histograma de cor está baseada no fato que certas cores ocorrem mais
freqüentemente em imagens gráficas do que em imagens fotográficas. Consiste na simples
coleta estatística de um grande número de imagens gráficas e fotográficas e na construção
de histogramas que mostram qual a freqüência de ocorrência de cada cor para cada tipo de
imagem. O valor calculado para uma imagem depende da correlação de seu histograma de
cor com o histograma das imagens gráficas e o histograma das imagens fotográficas.
Um histograma de cor é uma tabela tridimensional de tamanho 16 x16x16 . Cada cor
 r   g   b 
( r , g , b) corresponde ao bin indexado por   ,   ,    na tabela. O histograma de
 16  16  16  
cor de uma imagem contém cada bin o número de pixels naquela imagem cujas cores
correspondem para aquele bin.
A correlação C ( A, B) entre dois histogramas A e B é definido como
16
16
16
C ( A, B ) = ∑∑∑ ( Ai , j , k Bi , j ,k ) ,
i =0 j = 0 k = 0
onde Ai , j , k e Bi , j , k são respectivamente os bins (pacotes) em A e B indexados por
(i , j , k ) .
Cria-se o histograma de cor das imagens gráficas H g apanhando centenas ou milhares
de imagens gráficas e calculando a média de seus histogramas de cor. Similarmente cria-se
o histograma de cor das imagens fotográficas H f , usando um conjunto grande de imagens
fotográficas.
Suponha que uma imagem I
tenha o histograma de cor
H i e considere
a = C ( H i , H g ) e b = C( H i , H f ) . O valor calculado para a imagem I na métrica do
histograma de cor é definido como s =
b
. Quando C ( H i , H f ) aumenta, s também
a+b
25
aumenta. Quando C ( H i , H g ) aumenta, s diminui. Espera-se que os valores sejam
calculados maiores para imagens fotográficas.
Histograma do Vizinho Mais Distante
Esta métrica está baseada nos mesmos princípios utilizados na métrica do vizinho mais
distante.
Nesta métrica, o histograma do vizinho mais distante é um histograma unidimensional
com 766 bins. O i − ésimo bin (começando com zero) contém o número de pixels com
valor de transição igual à i . Cria-se um histograma Fg , de uma imagem gráfica, pela
média dos histogramas do vizinho mais distante de centenas ou milhares de imagens
gráficas. Cria-se um histograma F f , de uma imagem fotográfica, na mesma maneira como
foi feito para as imagens gráficas, utilizando um grande número de imagens fotográficas.
Define-se a correlação D( A, B) entre os histogramas A e B como
765
D( A, B) = ∑ Ai Bi ,
0
onde Ai e Bi são, respectivamente, os i − ésimos bins de A e B .
Seja Fi o histograma do vizinho mais distante de uma imagem,
a = D( Fi , Fg ) e b = D( Fi , F f ) .
O valor calculado s de uma imagem nesta métrica é dado por
s=
b
.
a+b
Como na métrica do histograma de cores, espera-se que imagens fotográficas possuam um
valor calculado maior que das imagens gráficas.
Razão de Dimensão
As razões de dimensões são dadas por:
•
w é a variável referente à largura da imagem em pixels;
•
h é a variável referente à altura da imagem em pixels;
26
•
m receberá o maior valor entre w e h , ou seja, se w tiver um valor maior, m
receberá o valor de w , caso contrário, se h for maior que w , então m receberá
o valor de h .
•
l receberá o menor valor entre w e h , ou seja, se w tiver um valor menor, m
receberá o valor de w , caso contrário, se h for menor que w , então m
receberá o valor de h .
O valor calculado para a Razão de Dimensão seria a razão entre l e m .
Espera-se que as imagem fotográficas possuam um valor calculado maior que das
imagens gráficas.
Dimensão Menor
O valor calculado para uma imagem é o tamanho de sua menor dimensão em pixels, ou
seja, se a altura é menor, então o valor calculado para a imagem será a altura. Se a largura
for menor, então o valor calculado para a imagem será a largura. Em geral, as imagens
gráficas têm valores calculados menores do que para as imagens fotográficas.
2.3 C LASSIFICAÇÃO
Han (1996) afirma que classificar consiste em separar conjuntos distintos de objetos ou
observações, alocando novos objetos ou observações em grupos previamente definidos.
Para realizar a classificação, é necessário um algoritmo para separar e alocar objetos ou
observações. Este algoritmo é chamado técnica de classificação. O objetivo final de um
método de classificação é prover resultados relevantes ou replicar o julgamento
especialista. A performance relativa de diferentes técnicas de classificação pode depender
das condições dos dados.
Wu (1999) afirma que a aquisição de conhecimento em bases de dados tem sido
trabalhada por pesquisadores em várias disciplinas, incluindo a inteligência artificial, há
mais de vinte anos. Embora muito trabalho tenha sido feito e alguns pacotes de
aprendizagem comerciais já estejam disponíveis, o trabalho existente concentra-se nos
quatro aspectos seguintes:
•
construção de bases de conhecimento para sistemas especialistas;
27
•
projeto de vários algoritmos de aprendizado;
•
adição de uma máquina de indução para um sistema de banco de dados existentes
em modo ad hoc para implementar regras de indução do banco de dados; e
•
projeto de uma máquina específica para aprender de um conjunto de dados de
domínio específico. Junto com o reconhecimento da limitação do problema do
conhecimento em transformar conhecimento de especialistas humanos para
sistema baseados em máquinas que aprende e sistemas baseados no conhecimento
e ainda é uma fronteira de pesquisa importante para ambos, máquina de
aprendizado e tecnologia de banco de dados.
Neste trabalho, utiliza-se um método de classificação não paramétrico supervisionado
chamado ID3 (Itemized Dichotomizer 3) desenvolvido por Quinlan (1986). Trata-se de um
algoritmo que usa lógica e matemática para processar, organizar e simplificar um grande
conjunto grande de dados. Sua habilidade para operar dados não numéricos é facilmente
aplicável para muitas situações. Este método é capaz de gerar regras através da indução de
atributos, gerando uma árvore de decisão. Han (1996) afirma ser o método mais utilizado
em aplicação de aprendizado indutivo. Para Pao (1989), o ID3 é facilmente automatizado.
O aprendizado indutivo utiliza um conjunto de exemplos (amostra de treinamento) e
determina uma relação entre estes exemplos via inferência indutiva. Regras de indução
podem ser utilizadas para predizer (prever) as saídas ou para replicar o julgamento. A
técnica do aprendizado indutivo é diferente da técnica estatística em muitos aspectos (Han
1996; Mak, 1996; Pal, 1997). Uma diferença é que os métodos estatísticos utilizam funções
discriminantes, enquanto o método ID3 (não numérico, categórico) desenvolve uma árvore
discriminante, resultado da indução utilizando amostras de treinamento. O método ID3
assume atributos nominais enquanto os métodos estatísticos assumem atributos numéricos.
2.4 O MÉTODO ID3
Origens
Em 1966, foi publicado um modelo de formação de conceito. Este modelo está baseado na
idéia de que para formar conceitos discretos do “novo” (desconhecido), do desorganizado
ou de dados não estruturados, as mentes humanas dividem os itens e conceitos em
28
subconjuntos com características comuns. Aqui está um esboço da estratégia da formação
do conceito (Hunt, 1966):
1. Estabelecer critérios que possam ser úteis, de acordo com alguma heurística,
para separar um conjunto em subconjuntos. Um exemplo em nosso contexto
seria dado pelas características antagônicas que permitam separar imagens
gráficas de imagem fotográficas (situações antagônicas). Outros exemplos
seriam os critérios estabelecidos para separar humano de animal, macho de
fêmea.
2. Dividir (separar) o conjunto de acordo com um critério selecionado.
3. Retornar ao item 1, escolher um novo critério até que uma única definição de
dados “novos” (desconhecidos) seja alcançada.
Hunt (1966) chamou este algoritmo de CLS (Concept Learning System). Muitos
afirmam que este método é baseado no conceito do dividir para conquistar. De fato, alguns
cientistas da computação explicam seus projetos de algoritmos de dividir para conquistar
como sendo intuitivos.
CLS é um método algorítmico para resolver tarefas de aprendizados de conceitos
simples usando conceitos de aprendizados para classificar informação nova. Devido à
natureza do CLS, este requer um número pequeno de valores discretos possíveis para o
vetor de características (esta é uma falha que foi superada com o ID3). O ID3 usa o CLS
como parte de sua implementação.
Desenvolvimento
Quinlan (1986) utilizando o modelo da formação do conceito, desenvolveu o método ID3,
que trata de um método supervisionado de aprendizado, capaz de gerar regras através da
construção de uma árvore de decisão. A construção desta árvore é função do valor da
entropia dos atributos da amostra de treinamento. A entropia mede o grau de desordem
entre os atributos. Deste modo, consegue-se induzir a construção de uma árvore, levandose em conta uma hierarquia de importância entre os atributos. Trata-se do método TDIDT
(Top-Down Induction Decision Tree) (Quinlan, 1986; McSherry, 1999; Wu, 1999).
Quinlan (1986) usou a estratégia do dividir para conquistar combinada à lógica, isto é, ao
critério de classificação para separar em grupos menores. O resultado deste experimento
foi impressionante com pequeno tempo de processamento.
29
Implementações
Antes que o algoritmo possa ser implementado, algumas terminologias devem ser
definidas. Faz-se referência a um conjunto de treinamento I . Cada subconjunto de I ,
incluindo o mesmo I na primeira iteração, será chamado de “janela”.
Segue um esboço do algoritmo ID3:
1. Selecionar aleatoriamente uma “janela” (subconjunto) de I .
2. Usar o CLS para formar uma regra, considerando-se a estrutura de árvore de
decisão produzida pela “janela”.
3. Realizar iterações em todo conjunto I , encontrando os elementos que não
foram classificados pelas regras geradas no item 2.
4. Formar uma nova “janela” adicionando para a “janela” corrente os elementos
que não foram classificados no item 3.
5. Repetir o item 2 até não existirem mais elementos não classificados no conjunto
I.
Entropia
Uma definição matemática do ID3 é que este determina algoritmicamente o maior ganho
em conteúdo de informação, enquanto o sistema decrementa a entropia (TDIDT). A
entropia e o conceito de conteúdo de informação recorrem a muitos aspectos da ciência da
computação, incluindo teoria da informação, algoritmos e compressão de dados.
Sucintamente, conteúdo da informação é a quantidade de dados existente em cada unidade
de representação (usualmente bits) e entropia é a menor unidade de representação
necessária para comunicar um certo conjunto de dados.
Por exemplo, seja M o conjunto {1, 2}. Obviamente, um bit será necessário para
representar um elemento de M , o conteúdo da informação de cada bit é um item de M .
A entropia pode ser definida matematicamente. Sendo W um subconjunto (“janela”)
de uma amostra de treinamento, m é o número de elementos da “janela” W e n a o
número de instâncias do elemento a em W . Conseqüentemente, a probabilidade p a de
encontrar a em W é definida como:
30
pa =
na
m
(1)
Para um sistema simples com classes c i , i = 1, 2, Κ , C , a entropia do sistema podem
ser definidas como:
C
Entropia = ∑ − pi log 2 pi
(2)
i =1
Por exemplo, em um conjunto de dados com dois valores disjuntos (como o conjunto
M mostrado anteriormente), onde existe uma probabilidade igual de encontrar cada um
dos valores, a entropia pode ser calculada como:
Entropia( M ) = −0,5 log 2 0,5 − 0,5 log 2 0,5 = 1
(3)
Caso Geral
Nesta seção, é dado uma interpretação matemática do ID3. A complexidade das equações
pode tornar o método ID3 inteiramente difícil de ser analisado devido ao grande número de
variáveis.
Seja N o número de elementos (padrões conhecidos) separados em conjuntos de
padrões de classes c i , i = 1, 2, Κ , C e o número de elementos na janela c i é N i .
Assumindo que todos os atributos têm J valores, para cada padrão K atributos e cada
atributo tem J k valores.
O objetivo matemático final do ID3 é reorganizar os dados de modo a criar uma árvore
de decisão. Isto é feito seguindo as etapas abaixo:
1. Calcule a entropia inicial do conjunto de treinamento T utilizando a Equação (2).
2. (a) Um atributo deve ser selecionado para ser o nodo raiz da árvore de decisão.
Isto é feito particionando o conjunto de treinamento T em K subconjuntos
de treinamento: para cada atributo Ak , k = 1, 2, Κ , K , onde a k é um valor
possível de Ak , particionando T de acordo com os valores a kj dos J valores
do atributo Ak . O número de atributos no ramo a kj é n kj . Note que estas sub
árvores particionadas não têm nenhuma relação inerente ao critério do grupo
final.
31
(b) O número de padrões pertencendo à classe c i em qualquer ramo da
população n kj é definido como n kj (i ) . A entropia de cada ramo n kj é avaliada
por:
C
Entropia(T , Ak , j ) = ∑ −
i =1
nkj (i )
nkj
log 2
nkj (i )
nkj
(4)
(c) A entropia de cada subconjunto é um resultado parcial – o ID3 necessita
considerar a entropia total do sistema. Esta é calculada como:
J 
n ij 
Entropia(T , Ak ) = ∑ 
Entropia (T , Ak , j )


j =1 ∑ j nij


(5)
(d) A árvore de decisão com a menor entropia é então selecionada pelo ID3
seleciona. A redução na entropia pode ser facilmente calculada através de:
Entropia(T ) − Entropia(T , Ak ) = ∆Entropia( k )
(e) Encontre o atributo
Ak0
(6)
que dê o maior decréscimo na entropia.
Matematicamente, encontre Ak0 tal que ∆Entropia ( k 0 ) > ∆Entropia( k ) para
todo k = 1, 2, Κ , K e k ≠ k 0 .
(f) O nodo Ak0 torna-se o nodo raiz da árvore de decisão.
3. Sintetize o próximo nível da árvore de decisão encontrando o atributo Ak que,
depois de testar todos os ramos, produz o maior decréscimo na entropia do
sistema. Forme subconjuntos de um nível prévio separando T de acordo com o
valor de Ak . É importante observar que o mesmo atributo é testado ao longo da
largura de cada nível de profundidade da árvore.
4. Repita este algoritmo até todos os elementos do subconjunto sejam do mesmo
tipo ou a entropia do sistema todo seja zero.
A Figura 2.3 mostra um exemplo de árvore de decisão, onde cada nodo não folha é um
atributo e cada nodo folha uma classe (um padrão conhecido).
32
Figura 2.3 – Exemplo de uma árvore de decisão.
A árvore de decisão construída tem-se uma estrutura que agrupa as regras aprendidas
durante o treinamento. Uma regra nada mais é que uma expressão lógica capaz de produzir
como resultado a classe a qual o objeto possui. Um exemplo de expressão lógica
sintetizada
a
partir
de
uma
árvore
de
decisão
pode
ser:
A1 (a11 ) ∧ A4 ( a43 ) ∧ A2 (a 22 ) → C ( N 4 ) , que representa o caminho destacado na Figura 2.3.
Para o atributo A1 aplicando um limiar resulta o subconjunto a11 e para o atributo A4
aplicando um limiar resulta o subconjunto a 43 e para o atributo A2 aplicando um limiar
resulta no subconjunto a 22 que resultaria no nodo folha N 4 que seria a classe, resultante da
classificação. Esta expressão pode ser representada utilizando estruturas de seleção
condicional se-então, que seria equivalente à:
Se o valor do atributo A1 = a11 , e
o valor do atributo A4 = a43 , e
o valor do atributo A2 = a22 .
Então todas as classificações c i ∈ N 4 podem ser assumidas.
O conjunto N 4 ⊆ C é o conjunto de uma ou mais conclusões, c i ∈ C , que ocorre
neste nodo. A expressão C ( N 4 ) indica que todas as classificações c i ∈ N 4 podem ser
afirmadas. O ideal seria que cada caminho na árvore terminasse com um nodo folha
33
contendo uma conclusão única ( N i = 1 para todo i ). Cada árvore de classificação poderia
ser capaz de diferenciar cada um dos exemplos que aprendeu da amostra de treinamento
T.
Complexidade
Segundo Quinlan (1986) a cada nodo não folha da árvore de decisão, o ganho de cada
atributo não testado F deve ser determinado. Este ganho depende do valor p a para cada
valor Fi de F , assim todo objeto em C deve ser examinado para determinar a sua classe e
seu valor F . Conseqüentemente, a complexidade computacional do procedimento a cada
nodo é O(C ⋅ F ) , onde F é o número de atributos acima. O gasto computacional total do
ID3 requerido por iteração é assim proporcional ao produto do tamanho do conjunto de
treinamento, o número de atributos e o número de nodos não folhas na árvore de decisão.
A mesma relação aparece ao se estender para todo processo de indução, até mesmo quando
várias iterações são executadas. Nenhum crescimento exponencial em tempo e espaço tem
sido observado quando as dimensões do trabalho de indução crescem, desta forma, a
técnica poderá ser aplicada para trabalhos maiores.
Vantagens e Desvantagens
Uma das grandes vantagens do ID3 é a sua simplicidade, quando comparado com outros
algoritmos de aprendizado: ID3 é muito mais direto na sua aproximação. Sua modelagem
baseada na cognição torna relativamente simples a compreensão de seu funcionamento
pelos humanos. Lamentavelmente, a árvore de decisão produzida pelo ID3, quando
utilizado para grandes processos ou conjuntos de dados com ruídos, tende a ser confusa
para a percepção humana.
ID3 executa muito bem quando os conjuntos dados são complexos e grandes – muito
melhor que o seu predecessor o CLS. Uma das maneiras pela qual o ID3 realiza isto é
encontrando o dado escondido e seus relacionamentos. Isto deve-se a problemas usando a
técnica simples do dividir e conquistar.
Outra vantagem do ID3 é seu uso conservativo dos recursos do sistema. O tempo
computacional envolvido no ID3 é linear e pode ser calculado como o produto do número
de objetos de treinamento, o número de possíveis atributos que descrevem cada objeto, e a
34
complexidade do critério final de seleção (medido como o número de nodos na árvore de
decisão).
A maior desvantagem do ID3 é que a árvore de decisão produzida é essencialmente
imutável – não se pode eficientemente trocar a árvore de decisão sem reconstruí-la. Usando
um método de atualização, a árvore tende a produzir um árvore de decisão que está longe
da árvore de decisão ótima, refutando assim a idéia original de formar a árvore de decisão
do ID3.
2.5 CONSIDERAÇÕES FINAIS
Nas seções deste capítulo pode-se observar a utilização de métricas na obtenção de valores,
parâmetros que permitem caracterizar os diferentes tipos de imagens, neste caso, imagens
fotográficas e imagens gráficas.
Estes valores resultantes das métricas serão organizados em tuplas contendo os
atributos valorados para cada imagem coletada.
O método é capaz de construir uma árvore de decisão em função do valor da entropia
dos atributos destas tuplas das amostras de imagens de treinamento.
Verifica-se que o método ID3 de classificação supervisionada apresenta características
importantes e adequadas ao desenvolvimento deste trabalho.
No próximo capítulo, estão descritos os procedimentos relacionados à utilização do
ID3, e também são apresentados os materiais e métodos empregados nas etapas de coleta
das imagens na WWW, separação das amostras de treinamento, aplicação das métrica para
obtenção de tuplas contendo as características das imagens, a utilização do método de
classificação supervisionado ID3 e também são discutidos os materiais e métodos
utilizados no processo de validação do modelo de classificação.
35
Capítulo 3
Materiais e Métodos
Nos capítulos anteriores, observa-se a importância dos classificadores para a recuperação
de imagens no ambiente da WWW. Também, foram descritas as principais métricas
envolvidas no processo de classificação e o método ID3 utilizado na construção do
classificador.
Este capítulo é dedicado à descrição dos materiais e métodos utilizados no
desenvolvimento e validação do classificador de imagens propostos.
Estimar a precisão de um classificador que utiliza um algoritmo de aprendizado
supervisionado é importante não somente para prever a sua exatidão de cálculos e
regularidade na execução, mas também se estabelecer critérios de escolha do classificador
em um conjunto de classificadores (seleção do modelo) ou combinando classificadores
(Wolpert, 1992).
O capítulo está organizado em seções que representam cada uma das etapas de
desenvolvimento do classificador de imagens. A Seção 3.1 apresenta os resultados
referentes à execução do robô de coleta de imagens. A Seção 3.2 descreve o processo
inicial de preparação das amostras de treinamento. A Seção 3.3 descreve os resultados
obtidos com aplicação das métricas. A Seção 3.4 descreve a utilização do método ID3 na
obtenção do classificador. A Seção 3.5 descreve os métodos que podem ser utilizados para
validação do classificador. A Seção 3.6 analisa a escolha do método para validar o modelo
e finalmente a Seção 3.7 faz a descrição dos experimentos para a validação do classificador
utilizando o método de validação cruzada com k-dobras.
36
3.1 D ADOS DA COLETA DE IMAGENS
No processo de coleta das imagens na WWW, ilustrado na Figura 3.1, utiliza-se um
programa robô descrito na Seção 2.1. Foram coletadas aproximadamente 10 gigabytes de
imagens no formato GIF e JPEG em vários domínios. Estas imagens foram armazenadas
em disco rígido do computador onde o robô esteve em execução por aproximadamente 8
dias.
3.2 P REPARAÇÃO DAS AMOSTRAS DE TREINAMENTO
Após o processo de coleta e armazenamento das imagens, realiza-se a separação das
amostras que serão utilizadas no treinamento. Esta etapa consiste em separar as imagens
em quatro grupos, que estão enumerados abaixo:
1. Imagens gráficas no formato GIF;
2. Imagens fotográficas no formato GIF;
3. Imagens gráficas no formato JPEG;
4. Imagens fotográficas no formato JPEG.
Figura 3.1 – Coleta de imagens na WWW.
Todo o processo de separação das amostras de treinamento é realizado por inspeção
visual. Isto torna o trabalho um pouco cansativo. A figura 3.2 ilustra a separação visual das
amostras de treinamento.
37
A separação destas em um dos grupos acima mencionados é realizada de forma
manual. Na execução desta etapa foram separadas 1350 imagens fotográficas GIF, 3058
imagens gráficas GIF, 4763 imagens fotográficas JPEG e 1434 imagens gráficas JPEG.
Figura 3.2 – Processo de separação visual das imagens, da base de imagens, formando as
amostras de treinamento.
3.3 APLICAÇÃO DAS MÉTRICAS
O processo de separação visual das imagens resulta em quatro conjuntos distintos (ver
Seção 3.2). Sobre cada um destes conjuntos aplicam-se as métricas descritas na Seção 2.2,
quais sejam número de cores, cor predominante, vizinho mais distante (as duas versões
descritas anteriormente), saturação, histograma de cor, histograma do vizinho mais
distante, razão de dimensão e dimensão menor.
Nesta seção, são mostrados os resultados indicativos para cada métrica. Foram
submetidos às métricas 1350 imagens fotográficas GIF, 2967 imagens gráficas GIF, 4742
imagens fotográficas JPEG e 1434 imagens gráficas JPEG. Como os valores calculados
pelas métricas possuem intervalos e grandezas diferentes, para cada tipo de imagem, estes
valores devem ser normalizados (na Seção 2.2, na descrição das métrica, é citada a
normalização), colocando-os no intervalo fechado de [0,1]. Desta forma, qualquer que seja
38
o valor resultante de cada métrica, estará normalizado, não existindo valores fora do
intervalo de [ 0,1] .
Os valores obtidos para cada imagem são colocados em um vetor, constituindo assim
uma tupla, para cada imagem. Uma tupla é descrita da seguinte forma:
t i = ( a1 , a2 ,Κ , a j , ck )
Onde: t i - tupla da i-ésima imagem; a j - j-ésima métrica (número de cores, porcentagem
da cor predominante, vizinho mais distante 1, vizinho mais distante 2, saturação,
histograma de cor, histograma do vizinho mais distante, razão de dimensão) e ck - k-ésima
classe (neste trabalho tem-se apenas duas classes: 1 – imagens fotográficas e 0 – imagens
gráficas).
A Figura 3.3 mostra exemplos de imagens e suas respectivas tuplas obtidas após a
aplicação das métricas.
Como resultado desta etapa, tem-se 1350 tuplas de imagens fotográficas GIF, 2967
tuplas de imagens gráficas GIF, 4742 tuplas de imagens fotográficas JPEG e 1434 tuplas
de imagens gráficas JPEG.
3.4 U TILIZAÇÃO DO ID3
O método supervisionado de aprendizado ID3 é capaz de gerar regras através da
construção de uma árvore de decisão.
Na construção do classificador, utilizam-se as tuplas resultantes da aplicação das
métricas nas amostras de treinamento. Não se deve esquecer que estes valores foram
normalizados.
Para cada atributo contido nas tuplas, calcula-se a entropia, Seção 2.4. O atributo de
maior entropia passa a ser o nodo raiz da árvore de decisão.
Com os valores existente para o atributo de maior entropia, busca-se um limiar, que
seria o valor que melhor consegue separar o conjunto de treinamento em questão. Levando
somente em consideração, para a separação, os valores do atributo de maior entropia.
Aplicando um limiar, utilizando o nodo raiz, ou seja o atributo de maior entropia,
realiza-se a classificação das tuplas, gerando dois novos subconjuntos de tuplas onde o
39
atributo utilizado como critério não participa dos dois novos subconjuntos. O algoritmo é
descrito no Capítulo 2, Seção 2.4.
t = (0,000364; 0,003; 1,000; 0,087; 0,211; 0,623; 0,017; 0,733; 1)
(a)
t = (0,000013; 0,132; 0,870; 0,119; 0,072; 0, 208; 0,000 0,927; 1)
(b)
t = (0,000986; 0,413; 0,626; 0,113; 0,061; 0,181; 0,192; 0, 249 ;
(c)
0)
t = (0,000008; 0,825; 0,210; 0,629; 0,061 0,157; 0,144; 0,294; 0 )
(d)
Figura 3.3 – Quatro imagens e suas respectivas tuplas obtidas depois da aplicação das
métricas. (a) imagem fotográfica no formato JPEG, (b) imagem fotográfica no formato
GIF, (c) imagem gráfica no formato JPEG e (d) imagem gráfica no formato GIF. A ordem
dos atributos da tupla são: número de cores, porcentagem da cor predominante, vizinho
mais distante 1, vizinho mais distante 2, saturação, histograma de cor, histograma do
vizinho mais distante, razão de dimensão e classe (1 – imagem fotográfica ou 0 – imagem
gráfica).
40
Com a árvore de decisão construída, tem-se uma estrutura que agrupa as regras
aprendidas. Neste momento, o classificador, ou seja, o modelo para classificação está
construído.
Desta forma, tem-se um modelo de classificação que utiliza o ID3 para disponibilizar
uma árvore de decisão. Uma árvore para imagens JPEG e outra para imagens GIF.
3.5 M ÉTODOS PARA V ALIDAR O MODELO
Esta seção é dedicada à descrição de alguns métodos capazes de verificar a estabilidade do
modelo de classificação obtido.
Um classificador é uma função de mapeamento de uma instância desconhecida (sem
tipo, rótulo, sem classificação), tornando-a conhecida (com tipo, rótulo, classificada)
usando para isto uma estrutura de dados interna.
O método ID3, descrito na Seção 3.4, constrói, a partir de um conjunto de dados
conhecidos, uma árvore de decisão através da abordagem TDIDT.
Para validar o classificador, faz-se necessário a utilização de algumas definições
matemáticas.
Seja V o espaço de instâncias desconhecidas, Y o conjunto classes possíveis,
X = V × Y o espaço de instâncias conhecidas e D = { x1 , x 2 , Κ , x n } um conjunto de dados
consistindo de N instâncias conhecidas, onde x i v i ∈ V , y i ∈ Y . Um classificador C faz
o mapeamento de uma instância desconhecida v ∈ V para uma instância conhecida y ∈ Y
e um indutor I faz o mapeamento de um conjunto de dados D em um classificador C . A
notação I ( D, v) significa atribuir um tipo para a instância v pelo classificador construído
pela indução I no conjunto de dados D , isto é, I ( D, v ) = ( I ( D))( v) . Assume-se que exista
uma distribuição no conjunto de instâncias conhecidas e que o conjunto de dados sejam
consistidos de uma distribuição independente e uniforme.
A precisão do classificador C é a probabilidade de classificar corretamente uma
instância selecionada de maneira aleatória, isto é, precisão = Pr[C (v ) = y ] para uma
instância selecionada de maneira aleatória v, y ∈ X , onde a distribuição de probabilidade
sobre o espaço das instâncias é o mesmo da distribuição que foi usada para selecionar as
41
instâncias para o conjunto de treinamento do indutor. Normalmente, ao utilizar uma única
forma de estimar a precisão não faz sentido pois não apresenta um intervalo de confiança.
Assim deve-se considerar como aproximar um intervalo quando possível. Para identificar
fraquezas, também tenta-se identificar casos onde a estimativa falha.
Existem vários métodos capazes de testarem a estabilidade de um modelo. Entre eles
temos: validação com divisão em duas partes (holdout validation), validação cruzada com
subamostragem aleatória (random subsampling cross-validation), validação cruzada com
k-dobras (k-fold cross-validation), validação cruzada com “um de fora” (leave-one-out
cross-validation) e bootstrap validation.
Validação com divisão em duas partes
O método de validação com divisão em duas partes (holdout validation) (Kohavi, 1995;
Blum, 1999) é um dos métodos mais comuns para estimar a generalização de erro. Este
método, também chamado de teste de estimativa simples, particiona o conjunto de dados
em dois subconjuntos mutuamente excludentes chamados de conjunto de treinamento e
conjunto de teste. É comum designar 2 3 do conjunto de dados para o conjunto de
treinamento e 1 3 para o conjunto de teste. A Figura 3.4 mostra um esboço da partição do
conjunto de dados para o método de validação com divisão em duas partes.
Figura 3.4 – Esboço do método de validação com divisão em duas partes.
De posse do conjunto de dados particionado, realiza-se o treinamento com o conjunto
de dados destinado para este fim e aplica-se a árvore gerada na etapa de treinamento na
etapa de classificação dos dados do conjunto de teste, calculando-se então a precisão da
classificação.
O método de validação com divisão em duas partes é uma estimativa pessimista
porque somente uma parte dos dados é utilizada para o treinamento. Quanto maior o
42
número de instâncias deixadas para teste maior será o erro, porém um pequeno conjunto de
teste conduz a um intervalo de confiança muito grande. Como verifica-se a seguir.
Em estatística, uma sucessão de eventos independentes é chamado processo de
Bernoulli. Seja S o número de classificações corretas em um conjunto de teste, então S é
uma distribuição binomial (soma de Bernoulli). Para um conjunto de teste razoavelmente
grande, a distribuição
S N , onde
N
é o tamanho do conjunto de teste, é
aproximadamente uma distribuição normal com média p e variância p (1 − p ) N . Assim,
o valor transformado para f = S N (a taxa de acerto do classificador) é dado subtraindose a média e dividindo-se pelo desvio padrão:
f −p
p (1 − p )
N
Pelo teorema do limite de De Moivre-Laplace, tem-se:


Pr − z ≤





f −p
≤ + z = c

p(1 − p)

N

Onde z é o (1 − c) 2 − th ponto quantil de uma distribuição normal padrão e c é o
intervalo de confiança. Com 100c porcento de intervalo de confiança, este determina z e
inverte as desigualdades. Inverter as desigualdades conduz para uma equação quadrática
em p , onde as raízes são os pontos inferior e superior do intervalo de confiança.

z2
f
f2
z2
p = f +
±z
−
+

2N
N N 4N 2





 z2 
1 + 
N

O maior problema do método de validação com divisão em duas partes ocorre quando
o conjunto de dados estiver distribuído de forma esparsa e as amostragens não forem
representativas. Este método faz uso ineficiente dos dados (Kohavi, 1995).
Weiss (1991) afirma que a desvantagem do método de validação com divisão em duas
partes está na redução da quantidade de dados disponíveis para treinamento e validação,
quando do particionamento do conjunto de dados.
43
Validação cruzada com subamostragem aleatória
O método validação cruzada com subamostragem aleatória (random subsampling crossvalidation) (Kohavi, 1995) separa um número fixo de elementos exemplos aleatórios do
conjunto de dados D . No segundo experimento, separa o mesmo número de exemplos,
porém em posições excludentes (diferentes do experimentos anteriores). Repete-se esta
separação em todos os demais experimentos que possam existir. A Figura 3.5 mostra um
esboço do método de validação cruzada com subamostragem aleatória, onde a parte
destacada é um exemplo dos elementos separados de forma aleatória em cada experimento.
A estimativa do Erro seria dada por:
Erro =
1 k
∑ Ei
k i =1
Onde Ei é 1 se classificou corretamente ou 0 se classificou erroneamente e k é o número
de elementos separados de forma aleatória de um conjunto de dados D .
Figura 3.5 – Esboço do método de validação cruzada com subamostragem aleatória
Validação cruzada com k-dobras
No método de validação cruzada com k-dobras (k-fold cross-validation) (Kohavi, 1995;
Anthony, 1998; Blum, 1999) o conjunto D , de tamanho N , é dividido em k subconjuntos
(dobras) mutuamente excludentes de tamanhos aproximadamente iguais. Onde 1 < k ≤ N .
O treinamento e o teste são realizados k vezes. Sempre utilizando k − 1 subconjuntos para
treinamento e o subconjunto que restou para teste.
44
A principal vantagem do método de validação cruzada com k-dobras é que todos os
exemplos do conjunto de dados são eventualmente usados para treinamento e teste. A
Figura 3.6 mostra um esquema ilustrando o método de validação cruzada com k-dobras,
mais precisamente uma validação cruzada com 4-dobras.
A estimativa de Erro seria dada por:
Erro =
1 k
∑ Ei
k i =1
Onde é 0 ≤ Ei ≤ 1 e representa taxa de erro para o dobra e k é o número de dobras.
Figura 3.6 – Esquema mostrando o exemplo do método de validação cruzada com 4dobras.
Validação cruzada com “um de fora”
O método de validação cruzada com “um de fora” (leave-one-out cross-validation)
(Kearns, 1997) é o caso degenerado do método de validação cruzada com k-dobras, onde o
número de dobras ( k ) é igual ao número de elementos do conjunto D . Para um conjunto
de dados com N exemplos, executar N experimentos. Para cada experimento usar N − 1
exemplos para treinamento e um único exemplo para teste. A Figura 3.7 mostra um esboço
do método de validação cruzada com “um de fora”, onde a parte destacada é um único
elemento a ser testado. Treinam-se todos os outros elementos e testa apenas um.
A estimativa do Erro seria dada por:
45
Erro =
1 k
∑ Ei
k i =1
Onde Ei é 1 se classificou corretamente ou 0 se classificou erroneamente e k é o número
de dobras, que neste caso é igual ao número de elementos do conjunto de dados.
Figura 3.7 – Esquema mostrando o exemplo do método de validação cruzadas com “um de
fora”.
0,249
Bootstrap
O método bootstrap foi descrito por Efron (1983). Dado um conjunto de dados de tamanho
N , uma amostra bootstrap é criada da reamostragem de N instâncias do conjunto de
dados (com sobreposição) para criar a amostra de treinamento. Desde que o conjunto de
dados seja amostrado com sobreposição, a probabilidade de uma dada instância qualquer
não seja escolhida depois de N amostras é (1 − 1 N ) N ≈ e −1 ≈ 0,368 . O número esperado
de instâncias distintas que aparecem do conjunto original de dados é 0,632 N . A estimativa
de precisão eteste nos dados de teste será muito pessimista ( ~ 63% das instâncias), porém
este número é combinado com o erro de substituição etreino sendo menor que o eteste . Assim
o Erro seria:
Erro = 0,632 ⋅ e teste + 0,368 ⋅ etreino
46
O processo é repetido para vários experimentos com diferentes sobreposições e os
resultados são obtidos através da média dos valores de Erro para todos os experimentos:
Ebootstrap =
1 b
∑ (0,632 ⋅ eteste + 0,368 ⋅ etreino )
b i =1
O método bootstrap é a melhor maneira de estimar performance para conjuntos de
dados muito pequenos.
3.6 ESCOLHA DO MÉTODO PARA V ALIDAÇÃO DO MODELO
Dos métodos descritos na seção anterior, o método de validação com divisão em duas
partes é um dos mais simples, porém, não conduz a uma boa validação do modelo. O
método bootstrap para pequenas amostras pode fazer uma boa validação do modelo mas
existem algumas situações onde o método falha, por exemplo, quando não se tem alteração
no conjunto de treinamento com etreino = 0% de substituição eteste = 50% . A estimativa
para o classificador é Ebootstrap = 0,632 ⋅ 50% + 0,368 ⋅ 0% = 31,6% , um valor calculado
inteiramente inconsistente, sendo o erro esperado de 50%.
Os métodos que realizam a divisão do conjunto de dados em dobras (validação
cruzada com subamostragem aleatória, validação cruzada com k-dobras e validação
cruzada com “um de fora”) são intensamente utilizados em Kohavi (1995), Kearns (1997),
Anthony (1998) e Blum (1999). Para validação do modelo proposto neste trabalho, utilizase o método de validação cruzada com k-dobras em virtude deste método possuir a
vantagem sobre o método da validação cruzada com subamostragem aleatória, no que diz
respeito da utilização de todo o conjunto de dados tanto para treinamento como para teste e
possuir menor gasto computacional, isto em relação ao método de validação cruzada com
“um de fora”, visto que o método de validação cruzada com “um de fora”, que seria o caso
degenerado do método de validação cruzada com k-dobras, com custo computacional
muito alto, inviável neste trabalho.
Ao optar pelo método de validação cruzada com k-dobras, deve-se pensar em quantas
dobras devem ser utilizados para a realização da validação. Algumas ponderações extraídas
da literatura, sobre o assunto, dizem respeito às seguintes opções:
•
Utilizar um grande número de dobras.
47
+ A taxa de erro será menor (a estimativa será mais precisa).
− O tempo computacional gasto será muito grande (muitos experimentos).
•
Com um pequeno número de dobras.
+ O número de experimentos e consequentemente tempo de computacional gasto
serão menores.
− A taxa de erro será maior.
Na prática, a escolha do número de dobras depende do tamanho do conjunto de dados,
da distribuição do conjunto de dados e dos recursos computacionais disponíveis. Para
conjuntos de dados esparsos, deve-se utilizar o método de validação cruzada com “um de
fora” de modo a treinar o máximo de exemplos (elementos) possíveis. Kohavi (1995)
afirma que o método de validação cruzada com 10-dobras repetido para 10 experimentos é
uma boa maneira para obter uma estimativa do erro.
3.7 V ALIDAÇÃO DO C LASSIFICADOR
Na Seção 3.2, descreve-se o processo de preparação das amostras de treinamento que são
utilizadas na construção do classificador (árvores de decisão para imagens nos formatos
JPEG e GIF). Estas amostras de treinamento são agora utilizadas com o método de
validação cruzada com k-dobras.
Nesta seção, descrevem-se dois procedimentos para validação do classificador obtido
na Seção 3.5. O primeiro procedimento utiliza imagens conhecidas, isto é imagens da
amostra de treinamento. Sobre estas amostras de treinamento, aplica-se o método de
validação cruzada com k-dobras.
O segundo procedimento de validação utiliza imagens inéditas a todo o processo, isto
é, imagens separadas para teste e mantidas fora do processo de treinamento. Serão
submetidas ao classificador de forma a se verificar a precisão do classificador.
Aplicação do método de validação cruzada com k-dobras
De posse das amostras de treinamento (tuplas), realiza-se uma reamostragem para a
construção de subconjuntos de imagens, isto é, seleciona-se de forma aleatória dentro do
conjunto de amostras de treinamento, imagens que irão participar de novos conjuntos.
48
Os novos conjuntos terão tamanhos diferentes. Eles serão compostos de 200, 400, 800,
1000 e 1200 imagens (representadas através de tuplas). Estes novos conjuntos serão
formados para imagens nos formatos GIF e JPEG. O motivo de se ter conjuntos para os
tipos de imagens (GIF e JPEG) deve-se a forma em que estes trabalham com o conjunto de
pixels da imagem (Miano, 1999).
Ao final desta etapa, tem-se, para cada conjunto de amostras GIF e JPEG de tamanhos
200, 400, 800, 1000 e 1200, as tuplas resultantes da aplicação das métricas sobre as
imagens destas amostras.
Para cada amostra de 200, 400, 800, 1000 e 1200, utiliza-se o método ID3 para a
geração de uma árvore de decisão e realiza-se a validação cruzada utilizando o método de
validação cruzada com k-dobras para k = 2, 4, 5, 8 e 10.
Para realizar o treinamento das k − 1 dobras na validação, utiliza-se inicialmente uma
“janela” de tamanho igual à 50. Monta-se a árvore de decisão com estas 50 tuplas e
classifica as tuplas que ficaram de fora da “janela”. Caso se tenha 100% de classificação, a
árvore de decisão foi encontrada e para-se. Caso contrário, incluir na “janela” as tuplas que
não foram classificadas corretamente e construir uma nova árvore. Repetir o processo
quantas vezes forem necessários até que a árvore gerada pela janela classifique
corretamente a amostra de treinamento toda. Segundo Quinlan (1986), este método
converge com poucas iterações.
Após a realização da validação do modelo, de posse das árvores geradas para imagens
GIF e JPEG que deram as menores taxas de erro utiliza-se estas duas árvores para
classificar imagens desconhecidas. Para isto, deve-se montar amostras obtidas do banco de
dados de imagens coletadas pelo programa robô (Seção 3.2).
De posse das árvores de decisão dos experimentos que geraram as menores taxas de
erro. Uma árvore para classificar imagens no formato GIF e outra árvore para o formato
JPEG. Realiza-se uma nova reamostragem de imagens desconhecidas (não utilizadas para
o treinamento), obtidas de maneira totalmente aleatória junto a base de imagens coletadas
pelo robô (Seção 3). A taxa de classificação é obtida da seguinte maneira:
 número _ classifica ções _ corretas 
%C = 
 × 100
 tamanho _ amostra _ testada 
Esta nova reamostragem gera as seguintes amostras: 10 amostras com 250 imagens
cada, com imagens fotográficas no formato GIF; 10 amostras de 250 imagens cada, com
49
imagens gráficas no formato GIF; 10 amostras de 250 imagens cada, com imagens
fotográficas no formato JPEG e 10 amostras de 150 imagens cada, com de imagens
gráficas no formato JPEG.
3.8 CONSIDERAÇÕES FINAIS
Este capítulo apresentou os procedimentos realizados em cada etapa de desenvolvimento
do classificador. Da mesma forma, discutiu a escolha de uma técnica para validação do
classificador obtido a partir das amostras de treinamento. O processo de separação destas
amostras de treinamento também foi tema deste capítulo.
Os materiais e métodos envolvidos a cada etapa quais sejam, coleta de imagens,
preparação das amostras de treinamento, aplicação das métricas, obtenção do classificador
foram realizadas em ambiente computacional do NPDI (Núcleo de Processamento Digital
de Imagens, do Departamento de Ciência da Computação, do Instituto de Ciências Exatas
da UFMG).
Entre as dificuldades comuns a qualquer processo de desenvolvimento cita-se como o
de maior relevância, as restrições dos recursos computacionais disponíveis para o
desenvolvimento. Toda implementação foi realizada sobre processador Pentium II,
utilizando 20 gigabytes de disco e 192 megabytes de memória RAM (Random Access
Memory). Os resultados experimentais obtidos neste ambiente estarão disponíveis no
próximo capítulo.
50
Capítulo 4
Resultados Experimentais
Este capítulo tem como objetivo mostrar os resultados experimentais obtidos na execução
dos procedimentos do classificador (obtido na Seção 3.4). Estes procedimentos foram
propostos na Seção 3.6. Como visto, estão envolvidos com a validação dois procedimentos.
O primeiro procedimento envolve as mesmas amostras de treinamento utilizadas na
construção do classificador e aplica-se sobre elas o método de validação cruzada com kdobras. O segundo procedimento de validação utiliza imagens inéditas a todo processo e
submete estas imagens ao classificador. A Seção 4.1 mostra os resultados experimentais,
para imagens no formato GIF e imagens no formato JPEG, das taxas de erro e do desvio
padrão das taxas de erro quando da utilização do método de validação cruzada com kdobras. A Seção 4.2 apresenta os resultados das taxas de classificações aplicando o
procedimento para validação em imagens que não foram utilizadas para o treinamento.
Este procedimento é feito tanto para imagens no formato GIF como para imagens no
formato JPEG.
Na Seção 4.3, são exemplificadas as condições de execução na construção das
amostras de treinamento utilizadas no desenvolvimento do classificador e no procedimento
de validação usando a validação cruzada com k-dobras.
4.1 R ESULTADOS U TILIZANDO O MÉTODO DE V ALIDAÇÃO
C RUZADA COM K-D OBRAS
A Figura 4.1 apresenta o gráfico das taxas de erro, em porcentagem, obtidas para as
amostras de imagens no formato GIF, cada amostra contendo 200, 400, 800, 1000 e 1200
51
imagens, utilizando-se o método de validação cruzada com k-dobras, com k = 2, 4, 5, 8 e
10. Percebe-se que as amostras que possuem os tamanhos de 800, 1000 e 1200 foram as
que obtiveram menores taxas de erro.
Figura 4.1 – Taxas de erro obtidas para amostras de imagens que possuem o formato GIF.
A Figura 4.2 apresenta o desvio padrão das taxas de erro apresentadas na Figura 4.1.
Como conseqüência dos resultados do gráfico da Figura 4.1, percebe-se que as amostras
que possuem os tamanhos de 800, 1000 e 1200 foram as que obtiveram os menores valores
para o desvio padrão.
Ainda na Figura 4.2, para as amostras de tamanhos iguais à 800, 1000 e 1200, que
apresentam os menores desvios padrão, vê-se que estas possuem uma tendência de
aumento do desvio padrão em função do aumento do número de dobras.
Se o algoritmo de indução, neste caso a árvore de decisão gerada, é estável para um
conjunto de dados, o desvio padrão do método de validação aplicado deve ser
aproximadamente o mesmo, independente do número de dobras (kohavi, 1995). Isto é
visível na Figura 4.2 onde a variância quase não é alterada para as várias dobras, para as
amostras de 800, 1000 e 1200. Com base nestes resultados, verifica-se a estabilidade do
classificador proposto.
52
Apresentados os resultados para imagens no formato GIF, mostra-se agora os
resultados para as amostras de treinamento JPEG.
A Figura 4.3 apresenta o gráfico das taxas de erro, em porcentagem, obtida para as
amostras de imagens no formato JPEG, cada amostra contendo 200, 400, 800, 1000 e 1200
imagens. Utiliza-se o método de validação cruzada com k-dobras, com k = 2, 4, 5, 8 e 10.
Da mesma forma que ocorreu com as imagens no formato GIF, percebe-se que as amostras
que possuem os tamanhos de 800, 1000 e 1200 foram as que obtiveram menores taxas de
erro.
A Figura 4.4 mostra o gráfico do desvio padrão das taxas de erro, obtidas para as
amostras de imagens no formato JPEG, cada amostra contendo 200, 400, 800, 1000 e 1200
imagens. Utiliza-se o método de validação cruzada com k-dobras, com k = 2, 4, 5, 8 e 10.
As amostras que possuem os tamanhos de 800, 1000 e 1200 foram as que obtiveram os
menores desvio padrões.
Ainda na Figura 4.4, as amostras de tamanhos iguais à 800, 1000 e 1200, apresentam
uma tendência de aumento do desvio padrão em função do aumento do número de dobras.
Figura 4.2 – Desvio padrão das taxas de erro para amostras de imagens que possuem o
formato GIF.
53
Figura 4.3 – Taxas de erros obtidas para amostras de imagens que possuem o formato
JPEG.
Figura 4.4 – Desvio padrão das taxas de erro para amostras de imagens que possuem o
formato JPEG.
Uma iteração consiste em gerar a árvore de decisão para as imagens que estão dentro
da “janela” (inicialmente tamanho igual a 50) e classificando o que está fora da janela.
Caso não se tenha sucesso em classificar corretamente todas as imagens, inclui-se na
54
“janela” as imagens que tiveram classificação errada e inicia-se uma outra iteração. Assim,
sucessivamente, até que todos os elementos da amostras de treinamento sejam classificados
corretamente.
Observa-se, além do número de iterações, que em todos os procedimentos de
treinamento ocorridos houve a convergência do algoritmo, conseguindo sempre classificar
100% da amostra de treinamento.
As Figuras 4.5 e 4.6 mostram, para imagens no formato GIF e imagens no formato
JPEG respectivamente, o número médio de iterações para cada validação cruzada com kdobras, com k = 2, 4, 5, 8 e 10 e amostras de tamanhos iguais à 200, 400, 800, 1000 e
1200. Percebemos que o número de iterações não cresce na mesma proporção que cresce o
número de dobras. Também não cresce na mesma proporção o número de iterações em
relação ao tamanho da amostra e não existe diferença significativa entre o número de
iterações para imagens no formato GIF ou no formato JPEG.
Figura 4.5 – Número médio de iterações para imagens no formato GIF.
55
Figura 4.6 Número médio de iterações para imagens no formato JPEG.
4.2 R ESULTADOS E XPERIMENTAIS U TILIZANDO IMAGENS INÉDITAS
A Figura 4.7 mostra os resultados obtidos quando da utilização de imagens inéditas, isto é,
imagens que não fizeram parte do treinamento ao processo de classificação. Como
resultados apresentados em forma de gráficos, vê-se a porcentagem de imagens
classificadas corretamente em amostras de imagens que possuem o formato GIF. Foram
utilizados 10 conjuntos (amostras) de 250 imagens inéditas. Obteve-se uma porcentagem
média de 92,3% de acerto, com desvio padrão igual a 2,1.
A Figura 4.8 mostra a porcentagem de imagens classificadas corretamente em
amostras de imagens inéditas submetidas ao classificador obtido e que possuem o formato
JPEG. Foram utilizados 10 conjuntos (amostras) de 250 imagens inéditas. Obteve-se uma
porcentagem média de 89,5% de acerto, com desvio padrão igual a 3,0.
56
Figura 4.7 – Taxas de classificação para imagens no formato GIF, onde obteve-se uma
média de 92,3% de imagens classificadas corretamente.
Figura 4.8 – Taxas de classificação para imagens no formato JPEG, onde obteve-se uma
média de 89,5% de imagens classificadas corretamente.
57
4.2 E XCEÇÕES NAS AMOSTRAS DE TREINAMENTO
Algumas imagens foram problemáticas para a classificação devido a sua aparência não ter
coerência com os valores retornados pelas métricas. É o caso das imagens apresentadas na
Figura 4.9. Por isso é importante criar mais métricas, que realmente expressem as
diferenças entre imagens gráficas e imagens fotográficas.
A Figura 4.9 mostra alguns exemplos que não foram classificados corretamente. A
Figura 4.9(a) é uma imagem gráfica no formato JPEG que apresenta características de uma
imagem fotográfica (muitas cores, transição entre as cores dos pixels suave, forma
quadrada). A imagem da Figura 4.9(b) é uma imagem fotográfica no formato GIF, que
apresenta características de uma imagem gráfica (grandes regiões com a mesma cor, altas
saturações de cores e transições abruptas). A Figura 4.9(c) é outro exemplo de uma
imagem no formato JPEG, que é uma imagem gráfica, mas se comporta como se fosse
uma imagem fotográfica.
(a)
(b)
(c)
Figura 4.9 – Alguns exemplos de imagens que não foram classificadas corretamente.
4.3 CONSIDERAÇÕES FINAIS
Avaliando os resultados obtidos para a taxa de erro e o desvio padrão da taxa de erro
percebe-se que a árvore de decisão gerada e utilizada para o experimento mostrou-se
estável. Isto pode ser observado quando nota-se que a variância praticamente não variou
com o aumento do número de dobras e que as amostras de tamanhos iguais a 800, 1000 e
1200 foram as amostras mais representativas. Isto vale tanto para imagens no formato GIF
e imagens no formato JPEG.
58
Foram mostradas a taxa de classificação para as imagens no formato GIF e imagens no
formato JPEG. Para este experimento foram utilizadas 10 amostras de 250 imagens para
cada um dos tipos de imagens. Percebe-se que a taxa de classificação para as imagens no
formato GIF é um pouco mais alta que a taxa de classificação para imagens no formato
JPEG e que as imagens no formato JPEG possuem um maior desvio padrão.
Mostrou-se o número de iterações para cada validação cruzada com k-dobras realizado
e percebe-se que o número de iterações não cresce na mesma proporção do número de
dobras e tão pouco com o aumento do tamanho da amostra.
Por fim, foram mostrados alguns exemplos de imagens problemáticas para a
classificação, que possuem aparências questionadas pelas métricas.
59
Capítulo 5
Conclusão
Esta dissertação apresentou as etapas necessárias para realizar a classificação de imagens
coletadas na WWW, que são: a utilização de um robô para a coleta das imagens; preparação
de amostras de treinamento; aplicação de procedimentos (métricas) sobre as imagens
obtendo valores capazes de discriminar os dois tipos de imagens em questão; utilização de
um método supervisionado simbólico capaz de induzir uma árvore de decisão, utilizando
para isto uma abordagem TDIDT. Este método chama-se ID3. Após a obtenção do
classificador, foram descritos métodos capazes de avaliar a estabilidade do modelo de
classificação, na realidade avaliar a estabilidade da árvore de decisão gerada pelo ID3. Em
seguida realizou-se a avaliação do classificador utilizando imagens inéditas, ou seja,
imagens que não fizeram parte do treinamento, calculando a taxa de classificação para cada
um dos tipos de imagens envolvidas neste trabalho (GIF e JPEG). Obteve-se uma taxa de
classificação de 92,3% para imagens no formato GIF e 89,5% para imagens no formato
JPEG.
5.1 CONTRIBUIÇÕES
Com a expansão e a popularização da WWW, as coleções de imagens digitais crescem
rapidamente. Uma imensa quantidade de informações são incluídas diariamente na Web.
Grande parte destas informações estão disponíveis na forma de imagens. Porém, o acesso,
ou seja, a recuperação destas imagens é uma tarefa que ainda apresenta grandes desafios.
60
O desenvolvimento deste trabalho demonstra a viabilidade de construir classificadores
que possam ser utilizados em ferramentas de recuperação de imagens com base no
conteúdo.
O grande volume das coleções de imagens e a complexidade de processamento dos
métodos utilizados, além das limitações do ambiente computacional disponível para o
desenvolvimento, representaram um importante desafio. Várias dificuldades menores
tiveram de ser superadas e entre elas, quer-se citar: a imaturidade desta área de pesquisa, a
ausência de documentação relevante a respeito da utilização do ID3, as restrições impostas
pelos equipamentos. No entanto, pode-se assegurar que este trabalho corresponde a uma
importante contribuição para a área de recuperação da informação, processamento de
imagens e visão computacional.
A disponibilização do classificador foi realizada a partir da utilização de imagens
coletadas na WWW. O Capítulo 2 apresentou este processo de coleta. Neste capítulo,
realizou-se a revisão bibliográfica que envolveu a descrição das métricas utilizadas na
obtenção de atributos que foram utilizados pelo método de classificação supervisionado
ID3. Ainda neste capítulo, apresentaram-se as origens e os algoritmos relacionados com o
desenvolvimento e implementação deste método para obtenção do classificador.
O Capítulo 3 tratou dos materiais e métodos envolvidos no desenvolvimento de cada
etapa deste trabalho. Nota-se que nas seções deste capítulo estão informações a respeito da
preparação das amostras de treinamento, da construção do classificador e da validação
deste classificador. Foram propostas duas formas de validação. A primeira proposta
envolve a aplicação do método de validação cruzada com k-dobras sobre as mesmas
amostras de treinamento que foram utilizadas pelo método ID3. A segunda proposta utiliza
imagens inéditas que são submetidas ao classificador.
O Capítulo 4 apresentou os resultados experimentais obtidos no processo de validação.
Vê-se que as duas propostas de validação foram realizadas. A Seção 4.1 apresentou
gráficos dos resultados experimentais aplicando-se o método de validação cruzada com kdobras sobre as amostras de treinamento. A Seção 4.2 foi dedicada aos resultados
experimentais do procedimento de validação que submete imagens inéditas ao
classificador. Pode-se constatar a viabilidade dos resultados e a estabilidade do
classificador.
61
Constata-se que o processo de construção de um classificador não é trivial. Muitas
técnicas e métodos devem ser considerados. Uma heterogeneidade de conhecimentos é
absorvida para que se possa realizar com sucesso cada uma das etapas. Durante todo o
trabalho os resultados e dificuldades encontradas foram discutidos e comentados. O que se
pode ressaltar é que um ambiente computacional arrojado e estável é fundamental para o
desenvolvimento deste tipo de aplicação.
5.2 TRABALHOS F UTUROS
Seguindo a mesma linha desta dissertação, podem ser indicados os seguintes caminhos
para trabalhos futuros:
•
Utilização de outros modelos para classificação como: Redes Neurais, CN2 e
CN4.5-rules estes dois últimos filhos do ID3.
•
Viabilizar a associação com outros modelos de classificadores. Por exemplo,
utilizar Redes Neurais nas imagens que não foram classificadas ou vice-versa.
•
Pesquisar mais métricas como por exemplo: as imagens gráficas possuem em
geral algumas similaridades.
•
Criar uma etapa capaz de encontrar e retirar a moldura que muitas vezes ocorre
nas imagens e estas afetam o resultados das métricas.
•
Buscar separar as duas classes, objeto deste trabalho, em subclasses (Vailaya,
1998; Guérin-Dungué, 2000). Exemplos de subclasses para a classe de imagens
fotográficas seriam: imagens de paisagens, imagens de ambientes internos,
imagens de ambientes externos, imagem de rostos e etc. Exemplos de subclasses
para a classe de imagens gráficas seriam: logotipos, mapas, ícones, botões,
desenhos.
•
Muitas imagens fotográficas, tanto no formato GIF como no JPEG, possuem
algum texto, que retirado, tem-se a imagem limpa. Criar uma etapa que realize
este trabalho. Uma proposta para isto pode ser encontrada em Guimarães (2000).
62
Referências Bibliográficas
[Abbadeni, 1999]
Abbadeni N., Ziou, D., Wang, S., Image classification and
retrieval on the www, Proceedings of the 4th ACM Conference
on Digital Libraries, 1999, Berkeley, CA USA, p. 208-209,
August.
[Anthony, 1998]
Anthony, M., Holden, S. B., Cross-validation for binary
classification by real-valued functions: theorical analysis,
Proceedings of the 11th Annual Conference on Computational
Learning Theory, 1998, Madison, WI USA, p. 218-229, July.
[Athitsos, 1998]
Athitsos, V., Swain, M. J., Frankel, C., Distinguishing
photographs and graphics on the www, Proceeding of IEEE
Workshop on Content-Based Access of Image and Video
Libraries, 1998, Puerto Rico, June.
[Bimbo, 1999]
Bimbo, A. D., Visual information retrieval, Morgan Kaufmann,
270p., 1999.
[Blum, 1999]
Blum, A., Kalai, A., Langford, J., Beating the hold-out: bounds
for k-fold and progressive cross-validation, Proceedings of the
twelfth Annual Conference on Computational learning theory,
1999, Santa Cruz, CA USA, July.
[Efron, 1983]
Efron, B., Estimating the error rate of a prediction rule:
improvement on cross-validation, Jounal of the American
Statistical Association, 78:316-331.
[Frankel, 1996]
Frankel, C., Swain, M. J., Athitsos, V., WebSeer: an image
search engine for the www, University of Chicago, Technical
Report 9614, 1996, Computer Science Departament, 1100 East
58th Street, Chicago, Illinois 60637, August.
[Goodrum, 2001]
Goodrum, A., Spink, A., Image searching on the excite web
search engine, Information Processing and Management, 2001,
v. 37, p. 295 – 311.
[Guérin-Dungué, 2000] Guérin-Dungué, A., Oliva, A., Classification of scene
photopgraphs from local orientations features, Pattern
Recognition Letters, 2000, v. 21, p. 1135 – 1140.
[Guimarães, 2000]
Guimarães, S. J. F., Leite, N. J., Image decomposition in
morphological residues: an approach for image filtering and
segmentation, 13th Brazilian Symposium on Computer Graphics
63
and Image Processing (SIBGRAPI), Gramado-RS, 2000, 276283, October.
[Gupta, 1997]
Gupta, A., Jain, R., Visual information retrieval,
Communications of the ACM, 1997, 40(5):71-79, May.
[Han, 1996]
Han, I., Chandler, J. S., Liang, T. -Peng. The impact of
meansurement scale and correlation structure on classification
performance of inductive learning and statistical methods,
Expert Systems With Applications, Elsevier Ltd, 1996,
10(2):209-221.
[Hunt, 1966]
Hunt, E. B., Experiments in Induction, Academic Press, New
York, NY, 1966.
[Kearns, 1997]
Kearns, M., Ron, D., Algorithmic stability and sanity-check
bounds for leave-one-out cross-validation, Proceedings of the
tenth Annual Conference on Computational Learning Theory,
1997, Nashville, TN USA, July.
[Kohavi, 1995]
Kohavi, R. A study of cross-validation and bootstrap for
accuracy estimation and model selection, International Joint
Conference on Artificial Intelligence (IJCAI), 1995.
[Quinlan, 1986]
Quinlan, J. R., Induction of decision tress, Machine learning,
1986, v. 1, p. 81 – 106.
[Mak, 1996]
Mak, B., Bui, Tung, Blanning, R., Aggregating and updating
experts´ knowledge: na experimental evaluation of five
classification techniques, Expert Systems with Applications,
Elsevier, 1996, 10(2):233-241.
[McSherry, 1999]
McSherry, D., Strategic induction of decision tree, KnowledgeBased Systems, Elsevier, 1999, 12:269-275.
[Miano, 1999]
Miano, J., Compressed image file formats: jpeg, png, gif, xbm,
bmp, Addison Wesley Longman, Inc, 1999, 264p.
[Pal, 1997]
Pal, N. R., Chakraborty, S., Bagchi, A., RID3: an id3-like
algorithm for real data. Information Science 96, Elsevier, 1997,
p 271-290.
[Pao, 1989]
Pao, Y., Adaptive pattern recognition and neural networks,
Addison Wesley, Reading, MA, 1989.
[Rui, 1999]
Rui, Y., Huang, T. S., Chang. S., -F., Image retrieval: current
techiniques, promising directions, and open issue, Journal of
Visual Communications and Image Representation, 1999, v. 10,
p. 39 – 62.
64
[Szumer, 1998]
Szumer, M., Picard, R. W. Indoor – outdoor image classification,
Proceedings of IEEE International Workshop on Content-Based
Access of Image and Vídeo Database, in conj. ICCV´98,1998,
Bombay, January.
[Vailaya, 1998]
Vailaya, A., Jain, A., Zhang, H. J., On image classification: city
vs. landscape, Proceeding of IEEE Workshop on Content-Based
Access of Image and Video Libraries, 1998, Santa Barbara,
California, June.
[Weiss, 1991]
Weiss, S. M., Kulikowski, C. A., Computer systems that learn,
1991, Morgan Kaufmann.
[Wolpert, 1992]
Wolpert, D. H., Stacked generalization, Neural Networks, 1992,
5:241-259.
[Wu, 1999]
Wu, X., Induction by attribute elimination, IEEE Transactions on
Knowledge and Data Engineering, September/October, 1999,
11(5):805-812.
65
Apêndice A
As tabelas que seguem mostram os resultados das taxas de erro do método de validação
cruzada com k-dobras para imagens no formato GIF, para amostras de imagens de
tamanhos iguais a 200, 400, 800, 1000 e 1200.
N = 200
k
Média Var. D.p.
2 4,0 13,0
8,5 40,5 6,4
4 8,0 6,0 18,0 8,0
10,0 29,3 5,4
5 10,0 7,5 5,0 7,5 5,0
7,0
4,4 2,1
8 12,0 12,0 4,0 0,0 8,0 16,0 8,0 8,0
8,5 24,9 5,0
10 0,0 10,0 0,0 5,0 5,0 10,0 10,0 10,0 0,0 15,0 6,5 28,1 5,3
Tabela A1 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 200.
N = 400
k
Média Var. D.p.
2 9,0 12,5
10,8 6,1 2,5
4 6,0 10,0 11,0 22,0
12,3 46,9 6,8
5 5,0 16,3 6,3 6,3 6,3
8,0 21,6 4,6
8 10,0 8,0 8,0 12,0 12,0 8,0 18,0 2,0
9,8 21,1 4,6
10 7,5 7,5 15,0 22,5 7,5 10,0 15,0 10,0 2,5 2,5 10,0 37,5 6,1
Tabela A2 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 400.
N = 800
k
Média Var. D.p.
2 5,5 7,8
6,6
2,5 1,6
4 8,0 6,0 7,5 5,0
6,6
1,9 1,4
5 5,6 8,8 6,3 6,3 5,0
6,4
2,0 1,4
8 4,0 5,0 5,0 8,0 6,0 6,0 7,0 8,0
6,1
2,1 1,5
10 3,8 7,8 10,0 3,8 7,5 5,0 5,0 6,3 7,5 6,3
6,3
3,9 2,0
Tabela A3 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 800.
Obs. Var. significa variância e D. p. significa desvio padrão.
66
N = 1000
k
Média Var. D.p.
2 6,6 6,8
6,7
0,0 0,1
4 5,6 7,6 7,6 4,4
6,3
2,5 1,6
5 5,0 6,0 7,5 7,0 6,0
6,3
1,0 1,0
8 3,2 5,6 5,6 6,4 6,4 9,6 5,6 6,4
6,1
3,1 1,8
10 2,0 4,0 8,0 7,0 6,0 6,0 8,0 9,0 5,0 3,0
5,8
5,3 2,3
Tabela A4 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 1000.
N = 1200
k
Média Var. D.p.
2 8,2 9,5
8,8
0,9 0,9
4 7,0 9,0 6,0 8,0
7,5
1,7 1,3
5 9,2 7,5 8,3 6,3 10,0
8,3
2,1 1,5
8 6,0 6,0 7,3 8,7 9,3 8,0 4,7 10,7
7,6
3,9 2,0
10 5,8 8,3 7,5 3,3 10,0 6,7 6,7 5,8 7,5 8,3
7,0
3,9 2,0
Tabela A5 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 1200.
As tabelas que seguem mostram os resultados das taxas de erro do método de
validação cruzada com k-dobras para imagens no formato JPEG, para amostras de imagens
de tamanhos iguais a 200, 400, 800, 1000 e 1200.
N = 200
K
Média Var. D.p.
2 23,0 18,0
20,5 12,5 3,5
4 20,0 22,0 10,0 16,0
17,0 28,0 5,3
5 17,5 32,5 5,0 0,0 25,0
16,0 183 13,5
8 24,0 4,0 28,0 16,0 8,0 8,0 24,0 24,0
17,0 85,7 9,3
10 35,0 20,0 25,0 15,0 15,0 10,0 20,0 15,0 15,0 25,0 19,5 52,5 7,2
Tabela A6 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 200.
Obs. Var. significa variância e D. p. significa desvio padrão.
67
N = 400
K
Média Var. D.p.
2 11,0 17,5
14,3 21,1 4,6
4 15,0 14,0 17,0 24,0
17,5 20,3 4,5
5 16,3 10,0 13,0 23,8 18,8
16,4 28,0 5,3
8 20,0 10,0 14,0 18,0 16,0 22,0 16,0 16,0
16,5 13,4 3,7
10 17,5 12,5 7,5 10,0 20,0 17,5 10,0 22,5 12,5 15,0 14,5 23,3 4,8
Tabela A7 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 400.
N = 800
k
Média Var. D.p.
2 15,5 21,0
18,3 15,1 3,9
4 14,5 19,0 16,5 15,7
16,4 3,6 1,9
5 10,6 16,3 13,1 15,0 14,4
13,9 4,6 2,1
8 8,0 14,0 18,0 16,0 13,0 11,0 14,0 15,0
13,6 9,4 3,1
10 17,5 12,5 15,0 13,8 16,3 16,3 16,3 11,3 12,5 13,8 14,5 4,2 2,1
Tabela A8 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 800.
N = 1000
k
Média Var. D.p.
2 16,0 15,6
15,8 0,1 0,3
4 14,4 15,6 14,0 14,8
14,7 0,5 0,7
5 12,0 17,0 14,0 13,0 17,0
14,6 5,3 2,3
8 8,8 12,8 9,6 13,6 13,6 13,6 14,4 14,9
12,7 5,0 2,2
10 11,0 13,0 16,0 11,0 11,0 11,0 11,0 18,0 11,0 15,0 12,8 6,8 2,6
Tabela A9 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 1000.
N = 1200
k
Média Var. D.p.
2 15,5 14,0
14,8 1,1 1,1
4 14,3 17,7 13,3 13,0
14,6 4,5 2,1
5 13,8 15,4 14,2 12,9 13,8
14,0 0,8 0,9
8 15,3 19,3 15,3 18,7 15,0 14,9 13,5 13,3
15,7 4,9 2,2
10 15,0 16,0 15,0 13,6 13,6 14,4 11,0 13,0 16,0 13,3 14,1 2,4 1,5
Tabela A10 – Valores das taxas de erro obtidas para o método de validação cruzada
com k-dobras, para k = 2, 4, 5, 8 e 10 em uma amostra de tamanho igual a 1200.
Obs. Var. significa variância e D. p. significa desvio padrão.
68
Percentual de imagens classificadas corretamente nos conjuntos de amostras de
imagens, utilizados para testes e formado por imagens GIF e JPEG que não fizeram parte
do treinamento da árvore de decisão.
1
2
3
4
5
6
7
8
9
10 Média Var. D. p.
GIF 95,8 90,6 95,7 93,1 90,3 92,4 93,0 91,4 89,8 91,1 92,3 4,5 2,1
JEPG 88,1 86,5 91,4 90,6 93,0 84,5 87,2 89,6 94,3 89,8 89,5 9,1 3,0
Tabela A12 – Resultado da classificação de imagens que possuem o formato GIF e JPEG
que não foram utilizadas na obtenção da árvore de decisão (do treinamento).
Obs. Var. significa variância e D. p. significa desvio padrão.
69
Apêndice B
As métricas descritas na Seção 2.2 foram submetidas a experimentos e nesta seção são
mostrados alguns resultados indicativos para cada métrica. Foram utilizadas para os testes
1350 imagens fotográficas GIF, 2967 imagens gráficas GIF, 4742 imagens fotográficas
JPEG e 1434 imagens gráficas JPEG. Como os valores retornados pelas métricas possuem
intervalos e grandezas diferentes, estes valores devem ser normalizados, colocando-os no
intervalo fechado de [ 0,1] . Realizadas as normalizações, calculam-se as porcentagens de
imagens gráficas e imagens fotográficas cujos valores foram inferiores aos dos limiares
0,1; 0,2; 0,3; 0,4; 0,5; 0,6; 0,7; 0,8; e 0,9. Este procedimento foi feito para o conjunto de
imagens GIF e JPEG, e os resultados estão colocados em forma de gráficos e são
apresentados na Figura B1 e na Figura B2. Estes gráficos mostram que, dependendo do
limiar, obtêm-se uma porcentagem de imagens, dependendo do tipo da imagem
(fotográfica ou gráfica). Isto fica bem ilustrado observando a Figura B1 e a Figura B2, que
mostram os gráficos gerados para cada métrica. Pode-se concluir que estas métricas são
viáveis para serem utilizadas como características utilizadas na discriminação dos dois
tipos de imagens.-
70
Figura B1 – Gráficos obtidos da avaliação das amostras de treinamento formadas por
imagens GIF.
71
Figura B2 – Gráficos obtidos da avaliação das amostras de treinamento formada por
imagens JPEG.
72
Apêndice C
Neste apêndice, são mostrados (Figura C1, Figura C2 e Figura C3) mais alguns exemplos
de imagens gráficas que podem ser coletadas na WWW.
Figura C1 – Exemplos de imagens gráficas coletadas na WWW
Figura C2 – Exemplos de imagens gráficas coletadas na WWW
73
Figura C3 – Exemplos de imagens gráficas coletadas na WWW