\documentclass[dvipdfm,a4paper,ruledheader]{abnt}
\usepackage {amssymb}
\input epsf.tex
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{graphicx}	  % uso do includegraphics
%\usepackage[alf]{abntcite}
\usepackage{latexsym}
\usepackage{abnt-alf}
%%%%% 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{2002}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\folhaderosto
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\listoffigures
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\listoftables
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sumario
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Resumo}
O objetivo deste projeto \'e o desenvolvimento de um classificador
que permita classificar 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, com 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. \cite{athitsos97distinguishing} \\

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

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=0.5]{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.
\newpage
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{Objetivos}
Serão necessárias as seguintes atividades para o desenvolvimento do classificador:
\begin {itemize}
\item leitura da base de imagens do banco de dados;

\item estudo da linguagem R, que será utilizada na implementação do classificador;

\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 uma tabela de
 a\-tri\-bu\-tos com valores normalizados e utiliza\c{c}\~ao desta tabela
 para a classificação das imagens, utilizando o algoritmo Clustering Large Aplications. \cite{kaufman}

\item validação do clasificador, utilizando grupos de $5\%$ de cada categoria para análise de resultados
em uma tabela de confusão.
\end {itemize}

Após o agrupamento das imagens nas categorias desejadas, o sistema permitir\'a a visualiza\c{c}\~ao
das m\'etricas para as figuras classificadas através de gráficos.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Motivação}
A Web \'{e} uma complexa e vasta fonte de informa\c{c}\~{a}o multimí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í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. \cite{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ível
a busca eficiente de imagens especí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} Estudo do algoritmo de clustering.
\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}
Agora, iremos detalhar melhor como foram atingidas as etapas de desenvolvimento, 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
\cite{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 também não obtivemos êxito. A solução encontrada foi criar uma base,
a partir de CDs de imagens (fotos e clipart's), totalizando 200 imagens, entre as quais 100 são gráficas e
100 são fotográficas. As imagens utilizadas estão em apenas um dos dois formatos, GIF ou JPG.\\

\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. \cite{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
a imagem lida, 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 representa imagens coloridas
da classe de imagens pixmap.
Para a conversão das imagens foi utilizado o 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 iremos utlizar a biblioteca "cluster", que possui funções
que implementam os algoritmos de clustering do livro \cite{kaufman} para agrupamento de objetos. \\

\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 principais características 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.0]{elefante.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem fotogr\'afica para verificação de características}
\end{figure}
As principais características 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}
\newpage
\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.0]{logo.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem gr\'afica para verificação de características}
\end{figure}
Sendo assim, as métricas implementadas no projeto foram: vizinho mais distante, razão de dimensão,
dimensão menor, saturação, número de cores, porcentagem da cor predominante, histograma de cor e
histograma de vizinho mais distante.

\subsection{Vizinho Mais Distante}
A métrica do vizinho mais distante baseia-se na transição de cores que aparece 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 mais visíveis. Desde que o intervalo de cores varie de 0 até 255,
o intervalo para a distância de cor varia de 0 até 765. \\
A distância de cores para dois pontos $p1(r_{1},g_{1},b_{1})$ e $p2(r_{2},g_{2},b_{2})$ é definida como:
%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation}
d = \mid(r_{1} - r_{2})\mid + \mid(g_{1} - g_{2})\mid + \mid(b_{1} - b_{2})\mid.
\end{equation}
Cada pixel da imagem possui vizinhos à esquerda, à direita, acima e abaixo, exceto os pixels das brodas da imagem.
O vizinho $p2$ mais distante de $p1$ é aquele em que a distância de cor entre $p2$ e $p1$ maior ou igual do que
a distancia entre p1 e qualquer um de seus outros vizinhos. \\
Um parâmetro utilizado nesta métrica é o valor de transição, definido como a distância entre $p1$n e o seu vizinho
mais distante. Outro parâmetro utilizado é o parâmetro $P$, que pode variar entre 0 e 765. Assim, a métrica do
vizinho mais distante para uma imagem é definida como o número de pixels que tem valor de transição maior ou igual a P.
\cite{athitsos97distinguishing} \\
Como as imagens gráficas possuem grandes regiões com a mesma cor, elas possuem muitos pixels cujo valor de transição
é zero. Desta forma, se escolhermos o valor de $P$ como sendo igual a 1, é esperado que imagens fotográficas possuam
um valor maior do que imagens gráficas para esta métrica. \\

\subsection{Histograma de Vizinho Mais Distante}
O histograma do vizinho mais distante é um histograma unidimensional
com 766 bins. O i-ésimo bin, a partir do zero, contém o número de pixels que possui
valor de transição igual à i . \\
Para calcular esta métrica, cria-se um histograma $F_{g}$ e $F_{f}$, de uma imagem gráfica e de uma imagem fotográfica,
respectivamente, pela média dos histogramas do vizinho mais distante de todas as imagens gráficas e fotográficas da base. \\
O próximo passo é a definição da correlação entre os histogramas A e B como:
\begin{equation}
D(A,B)= \sum_{i=0}^{765} A_i B_i
\end{equation}
onde $A_{i}$ e $B_{i}$ são, respectivamente, os i-ésimos bins de A e B .

Para o cálculo do histograma do vizinho mais distante de uma imagem é necessário criar o histograma $F_{g}$ de uma imagem
gráfica, a partir da média dos histogramas do vizinho mais distante de todas as imagens gráficas da base.
De maneira similar, é criado o histograma $F_{f}$ de uma imagem fotográfica a partir do conjunto de
imagens fotográficas da base.

O valor calculado s de uma imagem nesta métrica é dado por
\begin{equation}
s = \frac{b}{a+b}
\end{equation}

onde a e b são a correlação entre os histogramas $F_{i}$ e $F_{g}$ para a e $F_{i}$ e $F_{f}$ para b, com $F_{i}$ sendo
o histograma do do vizinho mais distante para a imagem.
Espera-se que imagens fotográficas possuam um valor calculado para esta métrica maior do que o das imagens gráficas.

\subsection{Número de Cores}
O valor utilizado para esta métrica é o número de cores diferentes que aparecem na imagem levando-se em consideração o
RGB, ou seja, todos os canais (Red, Green, Blue) juntos.
Normalmente, imagens gráficas possuem menor número de cores utilizadas do que imagens fotográficas.

\subsection{Histograma de Cor}
Um histograma de cor é uma tabela tridimensional de tamanho 16x16x16, no qual cada cor (r,g,b) corresponde ao bin
indexado por $\left( \lfloor \frac{r}{16} \rfloor, \lfloor \frac{g}{16} \rfloor \lfloor \frac{b}{16} \rfloor \right)$.
Este histograma contém em cada bin o número de pixels na imagem que possuem a cor representada por aquele bin.
Para o cálculo desta métrica, é utlizada a correlação C(A,B) entre dois histogramas A e B, que é definida como
\begin{equation}
C(A,B)= \sum_{i=0}^{16} \sum_{j=0}^{16} \sum_{k=0}^{16} A_{i,j,k} B_{i,j,k},
\end{equation}
Da mesma forma que na métrica do histograma do vizinho mais distante, para o cálculo do histograma de cores de uma imagem
é necessário criar o histograma de cor das imagens gráficas $H_{g}$, a partir da média dos histogramas de cores de todas
as imagens gráficas da base. De maneira similar, é criado o histograma das imagens fotográficas $H_{f}$ a partir do
conjunto de imagens fotográficas da base.
O valor calculado para a imagem I na métrica do histograma de cor é definido como
\begin{equation}
s = \frac{b}{a+b}
\end{equation}
onde a e b são a correlação entre os histogramas $H_{i}$ e $H_{g}$ para a e $H_{i}$ e $H_{f}$ para b.
Espera-se que os valores calculados sejam maiores para imagens fotográficas do que para as imagens gráficas.

\subsection{Porcentagem da Cor Predominante}
O valor calculado para esta métrica é o número de pixels da cor predominante, a cor que aparece em maior quantidade
nos pixels da imagem, expresso em porcentagem. \\
Como as imagens gráficas possuem grandes regiões com a mesma cor, o valor calculado para estas imagens é maior do que
para imagens fotográficas.

\subsection{Saturação}
O grau de saturação de uma cor é determinado pela quantidade de luz branca nela existente. Quanto maior a quantidade
de branco, menor a saturação da cor. \\
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$, o $g$ e o $b$.
O nível de saturação de p é definido por $\mid m - n \mid $.
Para o cálculo desta métrica é necessário espeecificar um parâmetro $P$, e, o valor calculado é o número de pixels com
nível de saturação maior ou igual a $P$. para  valores altos de $P$, é esperado que os avlores calculados sejam maiores
para as imagens gráficas.

\subsection{Razão de Dimensão}
A métrica da razão de dimensão especifica a razão entre a menor dimensão e maior dimensão da imagem.
As dimensões devem ser dadas em pixels. \\
Espera-se que as imagem fotográficas possuam um valor calculado maior que das
imagens gráficas.

\subsection{Dimensão Menor}
O valor calculado para uma imagem é o valor de sua menor dimensão em pixels, seja ela largura ou altura.
Em geral, as imagens gráficas têm valores calculados menores do que as imagens fotográficas. \\

Todas as métricas foram normalizadas após o cálculo de seus valores, dividindo-se cada valor obtido por
$(largura \times altura)$, que são as dimensões das imagens em pixels.

\section{Estudo dos algoritmos de clustering}
Para secolha do algoritmo de clustering mais adequado ao nosso projeto, foram analisados dois métodos,
por particionamento e hierárquico, ambos contidos no livro de \citeauthoronline{kaufman}:
\subsection{Método por particionamento}
Neste método, são construídos $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 deseja classificar objetos em $k$ grupos, onde $k$ é
fixo (embora sua escolha possa ser automatizada). \\
Este método pode ser aplicado através de dois programas: o Partitioning Around Medoids (PAM), o Clustering Large
Applications (CLARA) e o Fuzzy Analysis (FANNY). \\
\subsubsection{Partitioning Around Medoids (PAM)}
Este programa utiliza uma matriz de dissimilaridades entre os objetos do conjunto para identificar os
grupos. A idéia do algoritmo é a seguinte:
\begin {itemize}
\item selecionam-se $k$ objetos para representar os $k$ grupos (esses objetos levarão a um melhor resultado
se forem centralmente localizados);
\item 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.
\end {itemize}
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 é bem definido. Porém, o limite de
objetos a serem categorizados é igual a 100, tornando inviável a construção da matriz de dissimilaridades $nxn$ caso $n$
ultrapasse esse limite.

\subsubsection{Clustering Large Applications (CLARA)}
Este algoritmo é uma extensão do PAM para conjuntos de entrada grandes, diferenciando apenas no fato de que ele não utiliza
a matriz de dissimilaridades entre os objetos. \\
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.
\subsubsection{Fuzzy Analysis (FANNY)}
Este algoritmo utiliza o princípio da lógica fuzzy, que evita decisões diretas, ou seja, ao invés de afirmar "o objeto A
pertence ao grupo 1", ele poderia afirmar "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 deste algoritmo é complexa, não tão óbvia nem intuitiva. Uma outra desvantagem é que ele retorna
uma matriz $n \times k$, de n objetos e $k$ grupos, com os coeficientes de pertinência a cada grupo. \\
\subsection{Método hierárquico}
Esta classe não constrói uma única particionamento com $k$ grupos, mas os objetos se distribuem entre todos os valores
de $k$ em uma mesma execução. A princípio, este algoritmo parece ser melhor do que os algoritmos de particionamento, pois ele
encontra todas as partições possíveis de uma única vez, restando apenas a escolha de uma delas. Porém devemos levar
em consideração que o método de particionamento almeja selecionar o melhor agrupamento de $k$ grupos, o que não é
possível com o hierárquico, pois este não pode corrigir uma operação feita anteriormente, impedindo modificaçõres nos
agrupamentos. \\
Há dois tipos de métodos hierárquicos: o aglomerativo e o divisivo.
No método aglomerativo, partindo de uma iteração de ${k = r}$ para ${k = r + 1}$ dois grupos se unem, formando um único grupo.
No método divisivo, partindo de uma iteração com ${k = r}$ para ${k = r - 1}$, um grupo se divide em dois outros grupos. \\
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, entre outros.

\subsection {Algoritmo escolhido: Clustering Large Applications}
Este algortimo consiste na seguinte sequência de passos:
\begin{enumerate}
\item Selecionam-se cinco ou mais amostras randômicas de objetos de tamanho igual a ${40 + 2*K}$, motivado pelo objetivo
de se ter uma probabilidade razoável de objetos encontrados para todos os grupos em pelo menos uma amostra. \\
\item A amostra é agrupada em $k$ categorias usando o algoritmo PAM, que consiste 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 do conjunto de objetos representativos e, consequentemente, na tentativa
de melhorar os agrupamentos gerados por este conjunto.
Para isto, é feita 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 a escolha final dos objetos representativos, cada elemento do conjunto será atribuído a um grupo de acordo com
sua proximidade em relação ao objeto representativo do grupo.\\
\item Calcula-se 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}

\section{Validação do clasificador}
A validação dos dados obtidos na etapa de categorização foi realizada com conjuntos de $5\%$ dos dados de cada conjunto
que será classificado. Os resultados obtidos para estes conjuntos serão avaliados através da construção de uma matriz
de confusão.
Uma matriz de confusão contém informações sobre as classificações reais e previstas feitas por
um sistema de classificação. O desempenho de tais sistemas geralmente é avaliado utilizando-se os dados da matriz.
A tabela seguinte mostra a matriz de confusão para um classificador de duas classes. As entradas da matriz de confusão
têm o seguinte significado no contexto de nosso estudo:
\begin{itemize}
\item a é o número de imagens previstas como gráficas e classificadas como gráficas
\item b é o número de imagens previstas como gráficas e classificadas como fotográficas
\item c é o número de imagens gráficas que foram não foram classificadas
\item d é o número de imagens previstas como fotográficas e classificadas como gráficas
\item e é o número de imagens previstas como fotográficas e classificadas como fotográficas
\item f é o número de imagens fotográficas que foram não foram classificadas
\end{itemize}

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|c|r|}	\hline
{\em Previstos $\diagdown$ Reais}	& {\em Gráfica} & {\em Fotográfica} & {\em Não-clasificadas}
\\ \hline
Gráfica 			&	a	&      b	    &	    c
\\
Fotográfica			&	d	&      e	    &	   f
\\ \hline
\end{tabular}
\end{center}
\caption{Matriz de confusão}
\end{table}

\chapter{Resultados experimentais}

\section{Manipulação das imagens}
Inicialmente, buscamos imagens que demonstrassem as mais variadas
características de cada classe. Por exemplo, das fotos, buscamos
paisagens, pessoas, plantas, objetos; e dentre as gráficas,
ícones, cartoons, setas, logotipos, etc. Porém, um outro fator
ficou sendo preponderante na escolha das imagens para o estudo: o
tamanho. A conversão das imagens para o formato PPM aumenta
consideravelmente o tamanho da figura, gerando conseqüências no armazenamento e na leitura das mesmas. \\
O ambiente R gerou alguns erros na leitura de imagens
relativamente grandes (acima de 1Mb no formato PPM), então
tornamos público este erro na lista de discussão do R-project
e um dos pesquisadores da linguagem nos enviou uma versão corrigida da biblioteca Pixmap que contém as funções de manipulação de imagens. \\
Em suma, resultamos em 178 imagens, divididas da seguinte forma: \\
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|c|r|}	\hline
{\em }	     & {\em GIF} & {\em JPG} & {\em TOTAL}
\\ \hline
Gráficas      &       50       &      39	    &	89
\\
Fotográficas  &       50       &      39	    &	89
\\ \hline
\end{tabular}
\end{center}
\caption{Base de imagens}
\end{table}

\section{Cálculo das métricas}
Após a separação visual das imagens em dois conjuntos, foram aplicadas as métricas descritas
na seção 5.3 a cada um desses conjuntos. Nesta seção, iremos apresentar alguns resultados
representativos para cada um desses conjuntos de imagens, diferenciando as imagems gráficas
das imagens fotográficas. \\
Apesar de os valores das métricas terem sido normalizados (como citado na observação da seção 5.3),
eles são apresentados abaixo como obtidos antes da normalização, para que possam ser analizados
de maneira mais representativa.
Foram aplicadas ao conjunto das imagens GIF todas as métricas descritas na seção 5.3. Porém,
ao conjunto das imagens JPG a métricas cor predominante não pôde ser calculada, devido a problemas
encontrados com a linguagem de implentação do sistema. Como as imagens JPG possuem uma
quantidade de cores muito maior do as imagens GIF, a métrica número de cores só pôde ser
calculada através da utilização de alguns artifícios de implentação que impedissem que a quantidade
de memória utilizada pela estrutura que armazenava as cores dos pixels já lidos pudesse
ultrapassar o limite máximo de memória do tipo de dado desta estrutura. Com isso, não foi possível
determinar a cor predominate, pois só foi possível determinar a quantidade de cores diferentes,
mas não a frequência total de cada cor.
Desta forma, a ordem em que os resultados das métricas são apresentados para as imagens GIF são:
vizinho mais distante, razão de dimensão, saturação, número de cores, cor predominante,
histograma do vizinho mais distante e histograma de cores. Já para as imagens JPG a ordem é a
seguinte: vizinho mais distante, razão de dimensão, saturação, número de cores,
histograma do vizinho mais distante e histograma de cores. \\
É notório que as imagens JPG causaram grande impacto no cronograma de desenvolvimento do sistema, pois a etapa de processamento das métricas é a mais custosa e qualquer erro em seu andamento, prejudicará os passos seguintes. Por causa disso, foi necessário não arriscar quanto a tentativas de buscar soluções mágicas para uma eficiência no cálculo do número de cores (a âncora do atraso), e então formamos um pequeno conjunto de imagens com 21 elementos (11 fotos e 9 gráficas) para vermos o efeito na classifica da ausência das métricas número de cores e cor predominante; o resultado verermos na seção posterior.

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=0.5]{anim003.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem gráfica GIF}
\end{figure}
Métricas = (6542, 26244, 15797, 8, 207072, 17692, 28576, 162)

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.0]{foto006.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem fotográfica GIF}
\end{figure}
Métricas = (37229, 39998, 38790, 25, 1759, 23565, 35773, 200)

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.0]{esc018.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem gráfica JPG}
\end{figure}
Métricas = (16886, 15375, 14341, 12865, 14485, 21755, 124)

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.0]{foto005.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem gráfica JPG}
\end{figure}
Métricas = (43044, 28255, 42412, 31415, 36478, 35724, 168)

\section{Classficação}
Nesta etapa, foi utilizado o algoritmo descrito na seção 5.4.3 para realizar a categorização das imagens nas duas classes desejadas. Não houveram problemas na sua utilização, que, por sinal, mostrou-se ter boa performance. \\
A saida do método que implementa o algoritmo citado contém algumas informações bem expressivas a
respeito do processo realizado pelo algoritmo, como a melhor amostra, os medoides, se os dados foram normalizados, etc. \\
Abaixo veremos os resultados anotados da classificação em três conjuntos distintos de imagens:
\begin{enumerate}
\item{Imagens GIF}
\item{Imagens JPG com número de cores}
\item{Imagens JPG sem número de cores}
\end{enumerate}

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|c|}      \hline
{\em Algoritmo $\diagdown$ Real }	& {\em Gráfica} & {\em Fotográfica}
\\ \hline
Gráfica      &	     44       &      02
\\
Fotográfica  &	     06       &      48
\\ \hline
Total	     &	     50       &      50
\\ \hline
\end{tabular}
\end{center}
\caption{Classificação de imagens GIF}
\end{table}
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|c|}      \hline
{\em Algoritmo $\diagdown$ Real }	& {\em Gráfica} & {\em Fotográfica}
\\ \hline
Gráfica      &	     29       &      01
\\
Fotográfica  &	     01       &      26
\\ \hline
Total	     &	     30       &      27
\\ \hline
\end{tabular}
\end{center}
\caption{Classificação de imagens JPG utilizando número de cores}
\end{table}

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|c|}      \hline
{\em Algoritmo $\diagdown$ Real }	& {\em Gráfica} & {\em Fotográfica}
\\ \hline
Gráfica      &	     09       &      02
\\
Fotográfica  &	     00       &      10
\\ \hline
Total	     &	     09       &      12
\\ \hline
\end{tabular}
\end{center}
\caption{Classificação de imagens JPG sem número de cores}
\end{table}
\section{Validação}
Na etapa de validação, foi observado que a qualidade do classificador, associada ao algoritmo
de clssificação escolhido, foi bastante satisfatória. A validação da classificação obtida para
o conjunto de imagens GIF pode ser observada atrvés da seguinte matriz de confusão:

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|c|r|}	\hline
{\em Previstos $\diagdown$ Reais}	& {\em Gráfica} & {\em Fotográfica} & {\em Não-clasificadas}
\\ \hline
Gráfica 			&	100\%	&      0\%	      &       0
\\
Fotográfica			&	80\%	    &	   20\% 	   &	  0
\\ \hline
\end{tabular}
\end{center}
\caption{Matriz de confusão para imagens GIF}
\end{table}

Os resultados apresentados nesta tabela mostram que a classificação para as imagens gráficas
possui um indíce de acerto maior, devido à complexidade das imagens gráficas ser menor,
levando a valores mais similares para as métricas. Podemos observar na Figura 9 um exemplo de
uma imagem fotográfica GIF que foi classificada errada, por apersentar uma pequena
quantidade de cores pequena e grandes áreas com a mesma cor.
\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.5]{foto002.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo de imagem GIF com classificação errada}
  \label{seriadas}
\end{figure}

Para imagens JPG, os resultados obtidos da validação foram semelhantes. Porém, como o tamanho do conjunto de validação
para as imagens JPG é menor em relaçao ao conjunto das imagens GIF, a matriz de confusão apresenta-se da seguinte
forma:
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|c|r|}	\hline
{\em Previstos $\diagdown$ Reais}	& {\em Gráfica} & {\em Fotográfica} & {\em Não-clasificadas}
\\ \hline
Gráfica 			&	100\%	&      0\%	      &       0
\\
Fotográfica			&	80\%	    &	   20\% 	   &	  0
\\ \hline
\end{tabular}
\end{center}
\caption{Matriz de confusão para imagens GIF}
\end{table}


\chapter{Antecedentes}
\section{Webseer: um motor de busca de imagens para a www}
O Webseer é um sistema para localização de imagens na web. Este sistema utliza uma indexação das imagens tanto por texto quanto pelo seu conteúdo, pois a
análise do conteúdo das imagens acrescenta as informações obtidas através da indexação por texto.
Esta informaçõa adicional é utilizada para informar o contexto no qual a imagem está inserida,
para facilitar as informações que serão utilizadas pelo algoritmo de classsificação.

\section{Distinguindo imagens gráficas e fotográficas na  www}
Este sistema foi usado como parte do Webseer, utilizando a análise das iamgeens pelo seu conteúdo.
As imagens a serem classificadas são submetidas a alguns testes, e os resulatdos são repassados
para um classificador.

\chapter{Conclusão}
Este trabalho contém a definição, desenvolvimento e resultados do problema proposto: a classificação de imagens com base no conteúdo. A justificativa da importância do problema e o motivo de escolha foram comentados já anteriormente no capítulo 3, onde descrevemos a motivação do trabalho. Porém, esta motivação ganha um brilho peculiar após o desenvolvimento e a obtenção dos resultados, pois, foi notável a dificuldade de se trabalhar com imagens e a grande quantidade de dados adquiridos destas. \\
O classificador obteve bons resultados, categorizando corretamente grande parte das imagens submetidas (ver Tabela de resultados), tendo como principal responsável a atuação do algoritmo de classificação CLARA descrito na seção 5.4.1.2. O que surpreendeu durante a sua execução foi o tempo de processamento para capturar os dados das imagens, porém é simplesmente justificado por se tratar de manipulação de grandes matrizes de dados, além das limitações do ambiente computacional.\\
Dentre as dificuldades encontradas, pode ser destacada a utilização do ambiente R, não que seja uma linguagem de baixo nível ou limitada, mas pelo fato de ser uma linguagem em desenvolvimento, cujos colaboradores estão sempre atentos às falhas e sugestões indicadas pelos usuários. Com isso, sempre nos deparamos com o conflito de possibilidades do R versus a necessidade na implementação. No entanto, a documentação e a lista de discussão foram pontos importantes para o melhor andamento da implementação. \\
A longo do trabalho, já foram discutidos os processos, seus resultados e seus problemas, ficando de principal ponto de discussão deste trabalho a variação das escolhas realizadas neste, tais como: métricas, algoritmos de classificação, formatos de figuras, além da indispensável determinação de um ambiente computacional adequado.

\apendice
\chapter{Gráficos das métricas}
Nesta seção iremos mostrar os resultados obtidos a partir das métricas que foram descritas ne Sessão 5.3.
Os gráficos abaixo irão mostrar a relação entre a quantidade de imagens gráficas e fotográficas cujos valores
das métricas foram inferiores a aos dos limiares 0.1, 0.2, ..., até 0.9. Os resultados para cada uma das métricas
estão colocados em forma de gráficos, que são apresentados nas Figura 10 a 13. Nas Figuras 10 e 12 são apesentados os resultados para as métricas vizinho mais distante, razão de dimensão,
saturação e número de cores. Já nas Figuras 13 e 14, são apresentadas as métricas as métricas restantes, que são cor predominate,
histograma do vizinho mais distante e histograma de cores. Estas figuras são telas que foram obtidas como saída do
ImageSelector.

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=0.6]{hist1.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Gráficos das métricas para imagens GIF - Tela1}
\end{figure}

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=0.6]{hist2.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Gráficos das métricas para imagens GIF - Tela2}
\end{figure}

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=0.6]{histJPG1.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Gráficos das métricas para imagens JPG - Tela1}
\end{figure}

\begin{figure}[!hp]
  \centering
  \includegraphics[scale=0.6]{hist2JPG.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Gráficos das métricas para imagens JPG - Tela2}
\end{figure}

\chapter{GIF versus JPG}
\section{Formato GIF (Graphics Interchange Format)}
O GIF é diferente dos demais arquivos bitmap comuns pois é baseado em stream.
Ele consiste de uma série de pacotes de dados, chamado blocos, que armazenam informação adicional do protocolo.
Devido a essa organização, arquivos GIF devem ser lidos como se eles fossem arquivos contínuos de stream de dados.

\subsection{Visão Geral}
Nome: GIF \\
Também Conhecido Como: Graphics Interchange Format \\
Tipo: Bitmap \\
Cores: 1 a 8 bit \\
Compressão: LZW \\
Tamanho Máximo Da Imagem: 64Kb X 64Kb pixels \\
Múltiplas Imagens Por Arquivo: Sim \\
Formato Numérico: Little-Endian \\
Originado Por: CompuServe Inc. \\
Plataforma: MS-DOS, Macintosh, UNIX, Amiga, outros \\
Applicações Que Suportam: Muitas \\

\subsection{Principais Características}
\subsubsection{Número de Cores}
A grande maioria dos arquivos GIF contém imagens com qualidade de 16-cores ou 256-cores.
Imagens em tons de cinza, tais como as produzidas por scanners são muitas vezes armazenadas usando GIF,
embora gráficos monocromáticos, tais como clip art e imagens documento, raramente são. Essas cores são indexadas,
por isso esse formato funcionará melhor com imagens de cores sólidas, sem gradientes (degradês).

\subsubsection{Controle de Compressão}
O dado imagem armazenado em um arquivo GIF é sempre comprimido no formato LZW.
Esse algoritmo reduz strings de valores de bytes idênticos em uma palavra de código único e é
capaz de reduzir o tamanho de um dado típico de 8-bit pixel em 40\% ou mais. Seu tamanho pode ser
reduzido diminuindo-se o número de cores utilizadas para criar uma imagem.

\subsection{Qualidades}
\subsubsection{Transparência}
A forma de uma imagem GIF é sempre retangular, entretanto este formato permite determinar
que uma ou mais cores sejam transparentes e portanto não apareçam na tela do browser.
Esse recurso transmite a impressão de que a imagem possui, por exemplo, uma forma arredondada.
Ao se exportar uma imagem para esse formato tem-se de determinar que a cor de fundo seja transparente.
\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.0]{transparencia.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Exemplo do uso da transparência}
\end{figure}

Nesse exemplo há três botões: Diving, Charters e Cruises. Os botões Diving e Cruises são GIF's com o fundo transparente
e o botão Charters é um JPG que não permite transparência.

\section{Formato JPEG (Joint Photographic Experts Group)}
\subsection{Visão Geral}
Nome: JPEG File Interchange Format \\
Também Conhecido Como: JFIF, JFI, JPG, JPEG \\
Tipo: Bitmap \\
Cores: Acima de 24-bit \\
Compressão: JPEG \\
Tamanho Máximo Da Imagem: 64Kx64K pixels \\
Formato Numérico: Big-endian \\
Múltiplas Imagens Por Arquivo: Não \\
Originado Por: C-Clube Microsystems \\
Plataforma: Todas \\
Aplicações Que Suportam: Muitas \\

\subsection{Principais Características}
\subsubsection{Número de Cores}
Arquivos JPG possuem milhões de cores, Truecolor. Por isso funcionarão muito bem para
imagens com gradientes (degrades). O JPEG deve ser o formato preferido se você estiver
trabalhando com imagens fotográficas que tenham muitas cores tênues e informação tonal.
Como você não precisa reduzir as cores de 24 bits para apenas 8 bits de dados (ou 256 cores),
você tem uma possibilidade muito maior de reproduções fiéis de imagens com o JPEG.
\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.0]{degradees1.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Comparação entre GIF e JPG}
\end{figure}
A imagem ilustra uma fotografia salva no formato JPG (acima), com qualidade muito superior ao formato GIF (abaixo)
com grande perda de qualidade.

\subsubsection{Controle de Compressão}
A compressão de um arquivo JPG pode ser controlada dosando-se a qualidade da foto versus
tamanho do arquivo. Tonar arquivos menores é um grande ganho para transmiti-los entre redes e
para o armazenamento de bibliotecas de imagens. Quando se é possível comprimir um arquivo colorido
de 2 Mbyte para um de 100 Kbytes ou menos faz grande diferença no espaço em disco e no tempo de transmissão.
(Se compararmos GIF e JPEG, a taxa é de quatro para um). 
\begin{figure}[!hp]
  \centering
  \includegraphics[scale=1.0]{qualidadejpg.jpg}
  \setlength{\abovecaptionskip}{3pt}
  \caption{Comparação da qualidade de uma imagem JPG}
\end{figure}
No exemplo a mesma imagem é mostrada com duas diferentes definições de qualidade.
A imagem acima está com qualidade máxima (100) e ficaria com 24,43 Kb. A imagem abaixo foi
definida para ser exportada com qualidade baixíssima (5) e ficaria com 1,59 Kb.

\subsection{Qualidades}
\subsubsection{Transparência}
Não possui.

\chapter{GIF Versus JPEG}
Mesmo para os aplicativos que suportam JPEG, gasta-se muito mais tempo para decodificar e
visualizar uma imagem JPEG do que para uma imagem mais simples como GIF. Assim, usar JPEG é
essencialmente um compromisso tempo/espaço: você abre mão do tempo para ganhar no armazenamento
e transmissão de uma imagem de forma mais barata.
Além de ser o melhor formato para fotografias e imagens com nuances de cor, JPG é perfeito
para quem precisa dosar a qualidade e o tamanho (em Kb) da imagem.

\chapter{Formato PPM}
O PPM (Portable Pixmap) é um formato simples para imagens a cores. Um ficheiro de imagem em formato PPM-RAWBITS (Portable Pixmap RAWBITS) começa sempre com um cabeçalho: \\
\begin{itemize}
\item{a sequência de caracteres P6 e um ou mais caracteres brancos}
\item{a largura l da imagem em pixels e um ou mais caracteres brancos}
\item{a altura h da imagem em pixels e um ou mais caracteres brancos}
\item{o valor máximo de cada componente RGB (que é sempre igual a 255) e um carcter branco}
\item{linhas começadas por \# são comentários (ignorados até ao fim da linha)}
\end{itemize}
Após o cabeçalho seguem-se $3 \times l \times h$ bytes de informação correspondentes aos valores das componentes de cor de cada um dos pixels da imagem (onde $l$ e $h$ são as dimensões da imagem). \\

Os valores dos pixels são ordenados desde o canto superior esquerdo da imagem até ao canto inferior direito; para cada pixel os valores das componentes são dados pela ordem R,G,B. \\

\bibliographystyle{abnt-alf}
\bibliography{is6,abnt-options}
\citeoption{abnt-emphasize=bf}

\end{document}