\documentclass[a4paper,ruledheader]{abnt}
\usepackage {amssymb}
\input epsf.tex
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[dvipdfm]{hyperref}
\usepackage[dvips]{graphicx}      % uso do includegraphics
%\usepackage[alf]{abntcite}
\usepackage{abnt-alf}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hypersetup{colorlinks=true, linkcolor=blue, citecolor=red}
\hypersetup{
           pdftitle = {Classificador de imagens},
           pdfsubject = {Proposta de projeto},
           pdfkeywords = {classificador, fotos, figuras, gif, jpg, jpeg}
           pdfauthor = {Francisco J\´{u}nior, Marinas Dantas, Patrícia Maforte}
           }
%%%%% CABECALHO %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titulo{ImageSelector: um classificador de imagens}
\autor{ Francisco do Nascimento J\'{u}nior \par 
        Marinas Carrasco de Ribamar Dantas \par
        Patrícia Maforte dos Santos}
\orientador{Alejandro Frery}
\instituicao{Uiversidade Federal de Pernambuco \par Centro de Informática}
\local{Recife}
\data{Janeiro, 2003}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\folhaderosto
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\listoffigures
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sumario
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Resumo}
O objetivo deste projeto \'e o desenvolvimento de um classificador
que permita separar imagens coletadas em um banco de dados em duas classes
sem\^anticas: imagens fotogr\'aficas e imagens gr\'aficas. Imagens
fotogr\'aficas incluem cenas naturais, como pessoas, faces, animais, flores,
paisagens e cidades. Imagens gr\'aficas s\~ao logotipos, desenhos, ícones,
mapas e panos de fundo, geralmente gerados utilizando o computador. \\
Na maioria das vezes, n\~ao h\'a problema para n\'os decidirmos se uma imagem
\'e gr\'afica (Figura 1) ou fotogr\'afica (Figura 2). Baseado
nisso, o
sistema tentar\'a classificar da mesma maneira que os humanos fariam.
No entanto, \`as vezes n\~ao fica claro que categoria pode ser aplicada:
\'e o caso de imagens mistas ou de fotografias de desenhos.
Figuras nestes casos n\~ao ser\~ao utilizadas no treinamento, nem na fase de testes. \citeauthoronline{athitsos97distinguishing} \\

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.6]{seriadas.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem gr\'afica}
  \label{seriadas}
\end{figure}

\begin{figure}[!hp]
  \centering
  \includegraphics{bebe.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem fotogr\'afica}
  \label{bebe}
\end{figure}

Os classificadores podem ser utilizados em ferramentas comerciais de
recupera\c{c}\~ao de imagens com base no conte\'udo. Meios diferentes
podem ser utilizados para coletar as imagens a serem classificadas. Apesar de
utilizarmos uma base de dados, uma forma muito interessante e que iremos
usar como motiva\c{c}\~ao de projeto \'e a classifica\c{c}\~ao
de imagens da web. \\

\chapter{Objetivo}
O objetivo do classificador envolve as seguintes atividades:
\begin {itemize}
\item leitura da base de imagens do banco de dados;

\item prepara\c{c}\~ao das amostras de treinamento;

\item estudo, defini\c{c}\~ao, implementa\c{c}\~ao e aplica\c{c}\~ao de
 m\'etricas (n\'umero de cores, cor predominante, vizinho mais distante,
 satura\c{c}\~ao, histograma de cor, histograma do vizinho mais distante,
 raz\~ao de dimens\~ao, dimens\~ao menor) baseadas nas diferen\c{c}as
 entre as duas classes em quest\~ao;

\item disponibiliza\c{c}\~ao dos valores resultantes das m\'etricas em tuplas de
 a\-tri\-bu\-tos com valores normalizados e utiliza\c{c}\~ao destas tuplas da amostra
 de treinamento na constru\c{c}\~ao do classificador utilizando m\'etodo supervisionado
 ID3 (Itemized Dichotomizer 3). \citeauthoronline{Camillo}

\end {itemize}

Ap\'os a execu\c{c}\~ao desses procedimentos, ser\'a criada uma
\'arvore de decis\~ao geradora de regras para a classifica\c{c}\~ao.}

Ao final da separa\c{c}\~ao das imagens, o sistema permitir\'a a visualiza\c{c}\~ao
gr\'afica das m\'etricas para as figuras classificadas e ainda gr\'aficos que exibir\~ao
os resultados obtidos (taxas de classifica\c{c}\~ao e erros, desvio padr\~ao, n\'umero
m\'edio de itera\c{c}\~oes).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Motivação}
A Web \'{e} uma complexa e vasta fonte de informa\c{c}\~{a}o multim\'{i}dia.
A cada dia, mais imagens digitais s\~{a}o acrescentadas e retiradas da web,
tornando a necessidade de encontrar um determinado grupo de imagens uma tarefa
cada vez mais dif\'{i}cil. Desta forma, para se fazer uso dessas
informa\c{c}\~{o}es de forma eficiente \'{e} necess\'{a}rio que estas estejam
organizadas, de forma a permitir a pesquisa e a recupera\c{c}\~{a}o.} \citeauthoronline{frankel96webseer}

A recupera\c{c}\~{a}o de imagens representa uma \'{a}rea muito ativa
desde a d\'{e}cada de 1970. Existem duas linhas de pesquisa que estudam a
recupera\c{c}\~{a}o de imagens, que s\~{a}o o gerenciamento de banco de dados
e a vis\~{a}o computacional. Estas duas \'{a}reas estudam a recupera\c{c}\~{a}o
de imagens sob dois \^{a}ngulos diferentes, um baseado em texto e outro
baseado no conte\'{u}do visual das imagens. A recupera\c{c}\~{a}o de imagens
baseada em textos primeiro descreve as imagens de forma textual e depois
utiliza um SGBD (Sistema de Gerenciamento de Banco de Dados) baseado em textos
para a recupera\c{c}\~{a}o das imagens. Por\'{e}m, existem algumas dificuldades
neste tipo de recupera\c{c}\~{a}o. A primeira delas seria a quantidade de
trabalho requerida na anota\c{c}\~{a}o manual das imagens. A segunda e mais
importante seria o aspecto da subjetividade relacionada com a an\'{a}lise do
conte\'{u}do das imagens. Ou seja, para uma mesma imagem pessoas diferentes
t\^{e}m percep\c{c}\~{o}es diferentes, que o\-ca\-si\-o\-na\-ri\-am
anota\c{c}\~{o}es diferentes, podendo levar a erros irrecuper\'{a}veis
no processo de recupera\c{c}\~{a}o.

Neste cen\'{a}rio, a organiza\c{c}\~{a}o e recupera\c{c}\~{a}o de imagens
baseada no conte\'{u}do tornou-se uma \'{a}rea muito importante da vis\~{a}o
computacional e da multim\'{i}dia. A necessidade de se encontrar uma imagem
dentro de um conjunto de informa\c{c}\~{o}es digitais \'{e} importante para
diversos grupos de usu\'{a}rios, como jornalistas, engenheiros, historiadores,
designers, professores, artistas e ag\^{e}ncias de propagandas, entre outros.
A tecnologia que permite o acesso a essas informa\c{c}\~{o}es vem mudando
rapidamente, assim como a forma como as pessoas interagem com a informação visual.

O desenvolvimento de ferramentas que permitam o agrupamento de imagens
em grupos semanticamente significativos tornou-se algo de extrema import\^{a}ncia,
representando uma solu\c{c}\~{a}o para o desafio da recupera\c{c}\~{a}o de
imagens baseada no conte\'{u}do. Estas ferramentas tornar\~{a}o poss\'{i}vel
a busca eficiente de imagens espec\'{i}ficas em um grande banco de dados, pois
estas imagens estar\~{a}o esquematicamente categorizadas.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Cronograma}
\begin {enumerate}

\item 11/11/02 \--- 25/11/02: Obten\c{c}\~ao da Base de dados; \\
      \hspace * {1.56 in} Estudo e defini\c{c}\~ao das m\'etricas de classifica\c{c}\~ao; \\
      \hspace * {1.56 in} Busca do algoritmo ID3 (Itemized Dichotomizer 3).
\item 26/11/02 \--- 30/11/02: Estrutura\c{c}\~ao da implementa\c{c}\~ao.
\item 01/12/02 \--- 20/12/02: Implementa\c{c}\~ao l\'ogica.
\item 21/12/02 \--- 01/01/03: Recesso Acad\^emico.
\item 02/01/03 \--- 15/01/03: Implementa\c{c}\~ao l\'ogica.
\item 16/01/03 \--- 08/02/03: Implementa\c{c}\~ao gr\'afica.
\item 09/02/03 \--- 11/02/03: Prepara\c{c}\~ao da documenta\c{c}\~ao e apresenta\c{c}\~ao do projeto.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Histórico}
Segue abaixo a descrição das etapas de desenvolvimento do nosso projeto, seguindo uma ordem cronológica:
\section{Obtenção da base de dados}
Tentamos entrar em contato com o autor do artigo no qual estamos nos baseando
[\citeauthoronline{Camillo}], mas não obtivemos resposta. Então, procuramos na web uma base de imagens já anteriormente utilizada
com a mesma finalidade (classificação), porém não também não obtivemos êxito. A solução encontrada foi criar uma base,
a partir de CDs de imagens gráficas (fotos e clipart's), totalizando 400 imagens, entre as quais 200 são gráficas e
200 são fotográficas. \\

\section{Estudo da linguagem R}
Foi feito um estudo da linguagem e do ambiente R focalizando as funcionalidades oferecidas por
esta linguagem para o desenvolvimento do nosso projeto. A linguagem R é bastante eficaz na manipulação de dados,
fornecendo técnicas gráficas e estatísticas. O ambiente R fornece facilidades gráficas para a análise e visualização de
dados em manipulação. \citeauthoronline{introR}\\
Para o desenvolvimento do nosso projeto, inicialmente encontramos a biblioteca "pixmap", que foi utilizada
na leitura e manipulação das imagens. Esta biblioteca possui métodos que retornam as matrizes de cores (R, G e B) para
uma determinada imagem, informações que são utilizadas na implementação das métricas. Porém, para que as imagens
pudessem ser lidas, foi necessária a conversão das mesmas para o formato .ppm, que foi obtida através do uso do software
ImageMagick, recomendado por um membro da lista de discussão do R. O ImageMagick é um conjunto de ferramentas e
bibliotecas, utlizado para leitura, escrita e manipulação de imagens em diversos formatos. \\
Na etapa de categorização das imagens lidas na base de dados iremos utlizar a biblioteca "cluster", que possui funções
que implementam os algoritmos de clustering do livro de \citeauthoronline{kaufman} para agrupamento de objetos. \\
Um ponto negativo da linguagem: performance. O ambiente está custando para devolver respostas de extração das métricas às
figuras. Há duas coisas que podem está contribuindo para isso, ou até a combinação delas: o tamanho da figura e o algoritmo
da métrica, que na maioria das vezes, é composto por laços aninhados varrendo as três matrizes de R, G e B da figura.

\section{Estudo das métricas}
As métricas são parâmetros utilizados para diferenciar os dois tipos de imagens que foram
propostos para classifficação: imagens gráficas e imagens fotográficas. As imagens fotográficas são geralmente
representadas por cenas reais como paisagens, animais, flores e pessoas. As principais caracterizadas apresentadas
pelas imagens fotográficas, que podem ser comprovadas através da fig. 3, são:
\begin{itemize}
\item Ausência de regiões com cores constantes
\item Tendem a apresentar uma pequena diferença na razão altura x largura
\item Maior número de cores utilizadas
\end{itemize}
\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.6]{elefante.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem fotogr\'afica para verificação de características}
\end{figure}
As imagens gráficas são geralmente representadas por logotipos, botões, ícones, mapas, que, em sua grande maioria, são
geradas pelo computador. As principais caracterizadas apresentadas pelas imagens gráficas, que podem ser comprovadas
através da fig. 4, são:
\begin{itemize}
\item Grandes regiões com a mesma cor
\item Menor número de cores utilizadas
\item Tendem a apresentar uma grande diferença na razão largura x altura
\end{itemize}
\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.6]{logo.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem gr\'afica para verificação de características}
\end{figure}

\section{Estudo dos algoritmos de clustering}
No livro de \citeauthoronline{kaufman}, foi visto duas classes de algoritmos de clustering:
\begin{itemize}
\item{por partição} - É construído k grupos, onde cada grupo contém no mínimo um elemento e cada objeto do
conjunto pertence a exatamente um grupo. Ele é aplicado quando se quer classificar objetos em k grupos, onde k é fixo
(embora sua escolha possa ser automatizada). \\
Dentro desta classe, cita-se os algoritmos:
\subitem{Partitioning Around Medoids (PAM)}: Utiliza uma matriz de dissimilaridades entre os objetos do conjunto para identificar os
grupos. A idéia do algoritmo é a seguinte: seleciona-se k objetos para representarem os k grupos (esses objetos levarão a um melhor resultado
se forem centralmente localizados); a seguir, cada elemento do conjunto será atribuído ao grupo do objeto representativo
mais próximo a ele. Essa medida de proximidade é dada através da distância média ou dissimilaridade média. \\
Um bom resultado é notado quando a distância média do objeto representativo a todos os demais do seu grupo é mínima, quando isso acontece, chamamos esse objeto ótimo de medóide. \\
Este algoritmo poderia ser usado para o nosso problema, pois o número de grupos é definido e ele é tido como algoritmo de classificação mesmo.
\subitem{Clustering Large Applications (CLARA)}: Este algoritmo é uma extensão do anterior para conjuntos de entrada grandes, diferenciando apenas no fato de que ele não utiliza
a matriz de dissimilaridades entre os objetos, por ser uma matriz nxn,
o que custaria muito quando n crescer. \\
A idéia do CLARA é capturar randomicamente uma amostra do conjunto, buscar os objetos representativos dessa amostra, em seguida, utilizar o PAM para
agrupar os objetos.\\
Este algoritmo será utilizado no nosso projeto, pois utilizamos um conjunto razoavelmente grande de objetos.
\subitem{Fuzzy Analysis (FANNY)}: Este algoritmo utiliza o princípio da lógica fuzzy, que evita decisões diretas, ou seja, ao invés de dizer "o objeto A pertence ao grupo 1", ele poderia
dizer "o objeto A pertence por 80\% ao conjunto 1 e por 20\% ao conjunto 2", significando que provavelmente A pertence ao grupo 1. \\
Infelizmente a computação dele é complexa, não tão óbvia nem intuitiva. Uma outra desvantagem é que retorna uma matriz nxk, de n objetos e k grupos, com os coeficientes de pertinência a cada grupo. \\
\item{hierárquicos} - Esta classe não constrói uma única partição com k grupos, mas os objetos se distribuem para todos os valores de k ao mesmo tempo. Poderia se pensar que este seria melhor do que
os algoritmos de partição, pois ele encontra todas as partições possíveis de uma única vez e depois seria só escolher uma delas. Porém devemos levar em consideração que o método de partição almeja selecionar o melhor
agrupamento de k grupos, o que não é possível com o hierárquico, pois este não pode reparar uma operação feita anteriormente, impedindo reparos no agrupamento. \\
Há dois tipos de técnicas hierárquicas: aglomerativa e divisiva.
Na aglomerativa, de uma iteração de k = r para k = r + 1 dois grupos se unem e formam um só. Na divisiva, indo de uma iteração com k = r para k = r - 1, um grupo se divide em dois. \\
Este tipo de algoritmo não se adequa ao nosso problema, pois ele foca problemas que se assemelham com árvores evolucionárias, muito encontrado na biologia, para classificação de plantas, animais.
\end{itemize}
\subsection {Algoritmo escolhido: Clustering Large Applications}
\begin{enumerate}
\item Seleciona-se cinco ou mais amostras randômicas de objetos de tamanho igual a 40 + 2*K, motivado pelo objetivo de ter uma probabilidade razoável de objetos encontrados para todos os grupos em pelo menos uma amostra. \\
\item A amostra é agrupada em k clusters usando o algoritmo do PAM que consistem em duas partes:
\begin{itemize}
\item{BUILD} - Nesta fase são escolhidos sucessivos objetos representativos afim de obter um objeto com a distância média menor possível entre um objeto da amostra e seu objeto representativo mais similar.
Isso é feito até se encontrar k objetos representativos.\\
\item{SWAP} - Agora, o foco é dado na melhoria dos objetos representativos e do agrupamento resultante da escolha deles.
Para isso, é feito a troca de um objeto não-representativo por um representativo e calculado um fator de agrupamento representando a contribuição daquele objeto no agrupamento caso ele se torne representativo.
\end{itemize}
\item Após os objetos representativos serem finalmente escolhidos, casa um elemento do conjunto será atribuído a um grupo de acordo com sua proximidade do objeto representativo do grupo.\\
\item É calculado um fator de qualidade do agrupamento usando a distância média de cada objeto ao representativo do seu grupo.
\item Faz-se os passos 2, 3 e 4 para cada amostra, comparando os seus fatores de qualidade e ressaltando o melhor resultado.
\end{enumerate}
\bibliographystyle{abnt-alf}
\bibliography{is}

\end{document}