fundamentos.tex

\chapter{Fundamentos teóricos}

Este capítulo descreve os principais elementos teóricos utilizados no
desenvolvimento desta pesquisa. As seções \ref{sec:red_neu} e \ref{sec:red_tip}
resumem os principais conceitos sobre redes neurais, assim como as principais
técnicas utilizadas nesta área. A seção \ref{sec:red_khn} é dedicada
especificamente as redes de Kohonen, descrevendo sua estrutura conceitual e seu
algorítimo de treinamento, esta categoria de rede neural é o núcleo da técnica
de \textit{clustering} de imagens proposta neste trabalho, assunto abordado no
próximo capítulo. Uma breve formalização dos descritores de Hu é feita na seção
\ref{sec:desc_hu}. E por fim, alguns conceitos chave sobre imagens digitais são
apresentados na seção \ref{sec:img_dig}.

\section{Redes neurais artificiais}\label{sec:red_neu}

Dentro da Inteligência artificial, mais especificamente no contexto do
aprendizado de máquina, as redes neurais artificiais são sistemas computacionais
inspirados na estrutura do cérebro, em particular dos neurônios, que adquirem
conhecimento através da experiência.

As redes neurais se assemelham a grafos direcionados, onde os nós são os
neurônios, ou unidades de processamento, que possuem uma quantidade indefinida
de conexões de entrada e saída. As conexões são o equivalente às arestas do
grafo, e são responsáveis por transmitir informações entre os neurônios, podendo
amplificar ou reduzir a acuidade destas informações.

\begin{figure}[H]
\centering
\input{./graficos/neuronio}
\caption{Texto da figura}
\end{figure}

Sinais de entrada provenientes de fora da rede chegam por meio de conexões
originadas do mundo externo, de modo semelhante, saídas da rede para o mundo
externo são conexões que deixam a rede.

A configuração da rede, ou seja, os peso atual das conexões, determina como os
dados de entrada irão ativar os diferentes neurônios e gerar um determinado
resultado. Para grande maioria dos tipos de redes neurais, uma configuração
particular é obtida através de um algoritmo de treinamento. O treinamento em
geral busca reforçar as conexões que geram bons resultados e penalizar as que
não geram.

Estre as tarefas para as quais uma rede neural é adequada se
incluem: classificação, reconhecimento de padrões, predições, otimização
e filtragem de ruído.

\section{Principais tipos de redes neurais}\label{sec:red_tip}

Dentre a grande variedade de tipos de redes neurais artificiais, as mais
importantes, seja por sua contribuição teórica ou pela praticidade, são:

\subsection{Rede perceptron multicamada}

A perceptron multicamada é (a) uma rede direta, isto é, o sinal passa da entrada
até a saída sem ciclos; (b) possui camadas intermediárias de neurônios entre as
camadas de entrada e saída, ditas camadas ocultas; (c) utiliza funções de
ativação não lineares, comumente a função sigmoide e (d) os neurônios são
altamente conectados, em geral cada neurônio é conectado a todos os neurônios
da camada anterior e da camada seguinte.

\begin{figure}[H]
\centering
\input{./graficos/perceptron_mult}
\caption{Texto da figura}
\end{figure}

A presença de múltiplas camadas permite a este tipo de rede resolver uma enorme
variedade de problemas, ou em outros termos, reconhecer uma vasta variedade de
padrões. As redes multicamadas são computacionalmente completas, ou seja, são
equivalentes à classe das máquinas de Turing.

A retropropagação é o algoritmo de treinamento mais utilizado para esta variante
de rede neural. Cada iteração deste algoritmo é dividido em dois passos, no
primeiro a rede é alimentada com um dos exemplos, o resultado é capturado e
comparado com o valor esperado, com isso o erro geral da rede é calculado;
segue-se então ao segundo passo, que atualiza os pesos sinápticos penalizando
cada neurônio segundo sua influência no erro geral, essa etapa é feita da camada
de saída para a de entrada, retroativamente.

\subsection{Rede de Hopfield}

A rede de Hofield é (a) uma forma de rede neural recorrente, isto é,
determinadas conexões realimentam alguns neurônios, formando ciclos na rede; (b)
apresenta um atraso temporal, ou seja, a propagação dos sinais não é instantânea
e (c) a saída é um estado de convergência, isto é, após se apresentar uma entrada
a rede opera em ciclos até que a saída não mude mais, situação onde se diz que a
rede alcançou o equilíbrio.

ESQUEMA DE UMA REDE DE HOPFIELD AQUI

A rede de Hopfield funciona como uma memória endereçada por conteúdo, ou memória
associativa, por exemplo, muitas vezes lembramos de fatos inteiros apenas com uma
pequena lembrança do acontecimento. Uma memória associativa é, deste modo, um
conjunto de padrões armazenados de tal modo que, quando se apresenta um novo padrão,
a resposta será o padrão armazenado que seja mais parecido a este que foi apresentado.

Geralmente as redes de Hopfield não possuiem um método de aprendizado associado,
os pesos sinápticos são calculados por métodos matemáticos provenientes de sua
definição formal. A definição formal garante que a rede sempre irá convergir,
contudo, em algumas situações esta convergência pode não ocorrer para o padrão
mais próximo da entrada, e ainda não existe um método conhecido que resolva
este problema.

\subsection{Redes de Kohonen}

As redes de Kohonen apresentam apenas duas camadas de neurônios, a camada de
entrada e a de saída. A camada de saída é uma espécie de malha de neurônios não
conectados entre si, mas amplamente conectados com os neurônios da camada de
entrada. Esta malha funciona como um mapa, onde para cada padrão de entrada
apenas um neurônio é ativado, padrões semelhantes ativam neurônios dentro de
uma mesma região da malha.

ESQUEMA DE UMA REDE DE KOHONEN AQUI

As redes de Kohonen possuem um algoritmo próprio de treinamento, dividido em
três etapas; na primeira, chamado de processo competitivo, uma determinada entrada
ativa apenas um neurônio da malha; na segunda, chamado de processo cooperativo,
o neurônio escolhido estabelece uma vizinhança de neurônios que serão ajustados
para, junto com ele, identificar padrões semelhantes ao que foi apresentado; e
por fim, na terceira etapa, chamada de processo adaptativo, os pesos são
atualizados com base no neurônio vencedor e na vizinhança topológica. Este
algoritmo de treinamento é dito não supervisionado, pois não depende de um
par \textit{(entrada, saída esperada)}, já que a própria rede estabelece como
será a configuração dos resultados.

\section{Redes neurais de Kohonen}\label{sec:red_khn}

Esta seção irá apresentar mais detalhadamente como é a configuração de uma rede
de Kohonen, seu algoritmo de treinamento e os usos comuns deste tipo de rede.

\subsection{Topologia de uma rede de Kohonen}

Como dito anteriormente, a rede de Kohonen apresenta apenas duas camadas de
neurônios, a camada de entrada e a camada de saída. A camada de entrada deve
possuir tantos neurônios quanto forem à quantidade de elementos do padrão de
entrada. A camada de saída é uma grade de geometria livre, geralmente
retangular, de neurônios que não estão ligados entre si, mas estão, cada um,
ligados a todos os neurônios da camada de entrada. As conexões apresentam pesos
para escalar o sinal enviado.

ESQUEMA DE UMA CONEXÃO DA REDE DE KOHONEN AQUI

\subsection{Treinamento da rede}

O treinamento requer que os pesos sinápticos sejam iniciados com valores bem
pequenos, para que a rede não apresente inicialmente nenhuma configuração. Três
processos são executados para cada entrada do conjunto de treinamento, o
processo competitivo, o processo cooperativo e o processo adaptativo.

\subsubsection{Processo competitivo}

Quando uma entrada $ x = \left[x_1, x_2, ..., x_n\right]^T $ é apresentado à
rede, o neurônio da grade que melhor responder a este padrão será ativado, este
neurônio é dito vencedor, e será recompensado ajustando-se seus componentes
para mais próximo do vetor de entrada.

O critério escolhido para determinar o neurônio vencedor é a distância
euclidiana entre o vetor de entradas e o vetor de pesos das sinapses do
neurônio, como indicado na equação \ref{eq:dit_ecl}:

\begin{equation}\label{eq:dit_ecl}
d_i(t) = \sqrt{\sum_{j = 1}^N \left( x_j(t) - w_{ij}(t) \right)^2}
\end{equation}

Onde:

\begin{itemize}
\item $ d_i(t) $ é a distância euclidiana entre o vetor de pesos do
neurônio $ i $ e o vetor de entradas na iteração $ t $;
\item $ i $ é o índice do neurônio da grade;
\item $ j $ é o índice do neurônio de entrada;
\item $ N $ é o número de entradas;
\item $ x_j(t) $ é o sinal de entrada na entrada $ j $ na iteração $ t $;
\item $ w_{ij}(t) $ é o valor do peso sináptico entre o neurônio de
entrada $ j $ e o neurônio da grade $ i $ na iteração $ t $.
\end{itemize}

\subsubsection{Processo cooperativo}

Estudos biológicos indicam que ao ser excitado, um neurônio estimula seus
vizinhos topológicos, de forma que quanto mais próximo um neurônio está do
neurônio ativo, mais excitado pelo estímulo do neurônio ativo ele é. O processo
cooperativo busca simular este mecanismo biológico.

Em termos matemáticos, o que se deseja é um parâmetro $ h_{ik} $ , dito
\textit{vizinhança topológica}, que indica o gral de cooperação entre o
neurônio vencedor $ i $ e o seu vizinho $ k $, que deve ser simétrico em relação
ao neurônio $ k $ e deve decrescer constantemente com o aumento da
distância $ l_{ik} $ , até que $ \lim\limits_{ l_{ik} \to \infty } h_{ik} = 0 $ .
A função gaussiana \ref{eq:gauss} atende a estas duas exigências:

\begin{equation}\label{eq:gauss}
h_{ik} = e^{ \left( \frac{ l_{ik}^2 }{ 2 \sigma^2 } \right) }
\end{equation}

O parâmetro $ \sigma $ é denominado \textit{largura efetiva da vizinhança},
e deve diminuir a cada iteração, indicando uma tendência de especialização da
rede. Neste trabalho o parâmetro $ \sigma $ é a equação \ref{eq:leg_eft}:

\begin{equation}\label{eq:leg_eft}
\sigma(t) = \sigma_0 e^{ t / \tau_l }
\end{equation}

Onde:

\begin{itemize}
\item $ \sigma_0 $ é o valor inicial de $ \sigma $;
\item $ t $ é a iteração atual;
\item $ \tau_l $ é uma constante de tempo.
\end{itemize}

\subsubsection{Processo adaptativo}

O processo adaptativo atualiza os pesos sinápticos a cada iteração, levando em
consideração o neurônio vencedor e a vizinhança topológica. O ajuste dos pesos
deve decrescer com o tempo, para evitar que novos dados comprometam seriamente
o conhecimento já adquirido, substituindo padrões já estabelecidos por novos.
Algo semelhante ocorre com o cérebro humano, ao decorrer do envelhecimento o
aprendizado vai se tornando mais difícil.

O ajuste $ \Delta w_{ij} $ que a sinapse entre o neurônio de entrada $ i $ e
um neurônio da malha $ j $ deve sofrer é expresso pela equação \ref{eq:ajus}:

\begin{equation}\label{eq:ajus}
\Delta w_{ij} = \eta(t) h_{ik}(t) (x_j - w_{ij})
\end{equation}

Onde $ h_{ik}(t) $ é o parâmetro vizinhança topológica na iteração $ t $ ,
referente ao neurônio vencedor $ k $ . O
parâmetro \textit{taxa de aprendizagem} $ \eta(t) $ é definido pela
expressão \ref{eq:tx_aprd}:

\begin{equation}\label{eq:tx_aprd}
\eta(t) = \eta_0 e^{ t / \tau_l }, \eta_0 \in [0, 1]
\end{equation}

Onde $ \tau_l $ é uma constante de tempo.

\subsubsection{Algoritmo geral de treinamento}

O algoritmo \ref{alg:trei_khn} resume as três etapas anteriores e descreve
todo o processo de treinamento de uma rede de Kohonen:
%\clearpage

\begin{algorithm}[H]
\caption{Treinamento de uma rede de Kohonen}\label{alg:trei_khn}
\SetAlgoRefName{alg:trei_khn}
\Entrada{$ \sigma_0 $ , $ \tau_l $ , $ \eta_0 $ e o valor do \textit{erro} }
\Inicio{
  \Repita{distâncias auclidianas $ \le $ erro}{
    Calcular a \textit{largura efetiva} $ \sigma(t) $\;
    Calcular a \textit{vizinhança topológica} $ h $\;
    Calcular a \textit{taxa de aprendizado} $ \eta(t) $\;
    \ParaCada{conexão}{
      Calcular $ \Delta w $\;
      Ajustar o arco\;
    }
  }
}
\end{algorithm}

\section{Descritores de Hu}\label{sec:desc_hu}

Os descritores de Hu são um conjunto de sete momentos invariantes a rotação,
translação e escala.

O momento bidimensional de ordem $ (p+q) $ é dado pela
equação \ref{eq:mm_bid_cont}:

\begin{equation}\label{eq:mm_bid_cont}
m_{pq} = \iint x^p y^q f(x, y) \mathrm{d}x \mathrm{d}y, p, q \in
\end{equation}

A equação num domínio discreto, pode ser reescrita na forma:

\begin{equation}\label{eq:mm_bid_disc}
m_{pq} = \sum_{x, y} x^p y^q f(x, y), p, q \in
\end{equation}

A massa total da função $ f(x, y) $ é determinado pelo
momento $ m_{00} $, conforme a equação \ref{eq:mm_bid_m00}:

\begin{equation}\label{eq:mm_bid_m00}
m_{pq} = \sum_{x, y} f(x, y), p, q \in
\end{equation}

Existe um ponto no qual a aplicação pontual da massa total gera o mesmo momento
que a massa distribuída, este ponto é dito centroide de $ f(x, y) $ e suas
coordenadas $ x $ e $ y $ são dadas pela equação \ref{eq:ct_xy}:

\begin{subequations}\label{eq:ct_xy}
\begin{align}
    \bar{x} = \frac{1}{ m_{00} } \sum x f(x, y) = \frac{ m_{10} }{ m_{00} } \\
    \bar{y} = \frac{1}{ m_{00} } \sum y f(x, y) = \frac{ m_{01} }{ m_{00} }
\end{align}
\end{subequations}

O momento central é obtido se deslocando a imagem para o centroide,
da seguinte forma:

\begin{equation}\label{eq:mm_ctr}
\mu_{pq} = \sum_{x, y} (x - \bar{x})^p (y - \bar{y})^q f(x, y)
\end{equation}

Ainda é necessário normalizar o momento para que os valores resultantes não sejam
extremos a ponto de serem ignorados pelo sistema de reconhecimento de padrões. O
momento central de ordem $ (p+q) $ normalizado é obtido dividindo o momento
central de $ y $ mesma ordem por um fator definido por $ \mu_{00}^\gamma $ ,
conforme indicado pela equação \ref{eq:mm_norm}:

\begin{subequations}\label{eq:mm_norm}
\begin{align}
    \gamma = 1 + \frac{ p + q }{2} \\
    \eta_{pq} = \frac{ \mu_{pq} }{ \mu_{00}^\gamma }
\end{align}
\end{subequations}

A partir dessas equações são estabelecidos sete momentos invariantes à translação,
 rotação e escala, chamados de momentos de Hu, ou descritores de Hu. São eles:

\begin{subequations}\label{eq:mmt}
\begin{align}
  \varphi_1 = \eta_{20} + \eta_{02} \\
  \varphi_2 = (\eta_{20} - \eta_{02})^2 + 4\eta_{11}^2 \\
  \varphi_3 = (\eta_{30} - 3\eta_{12})^2 + (3\eta_{21} - \eta_{03})^2 \\
  \varphi_4 = (\eta_{30} + \eta_{12})^2 + (3\eta_{21} + \eta_{03})^2 \\
%
  \varphi_5 = (\eta_{30} - 3\eta_{12})(\eta_{30} + \eta_{12})
               \left[ (\eta_{30} + \eta_{12})^2 - 3(\eta_{21} + \eta_{03})^2 \right] \\
              + (3\eta_{21} - \eta_{03})(\eta_{21} + \eta_{03})
               \left[ 3(\eta_{30} + \eta_{12})^2 - (\eta_{21} + \eta_{03})^2 \right] \\
%
  \varphi_6 = (\eta_{20} - \eta_{02})
               \left[ (\eta_{30} + \eta_{12})^2 - (\eta_{21} + \eta_{03})^2 \right] \\
              + 4\eta_{11}(\eta_{30} - \eta_{12})(\eta_{21} + \eta_{03}) \\
%
  \varphi_7 = (3\eta_{21} - \eta_{30})(\eta_{30} + \eta_{12})
               \left[ (\eta_{30} + \eta_{12})^2 - 3(\eta_{21} + \eta_{03})^2 \right] \\
              + (3\eta_{12} - \eta_{03})(\eta_{21} + \eta_{03})
               \left[ 3(\eta_{30} + \eta_{12})^2 - (\eta_{21} + \eta_{03})^2 \right]
\end{align}
\end{subequations}

\section{Imagens digitais}\label{sec:img_dig}

Imagens digitais são representações computacionais de imagens bidimensionais,
codificadas de modo a permitir seu armazenamento, exibição e manipulação por
dispositivos eletrônicos. Há dois tipos fundamentais de imagens digitais,
os mapas de bits (\textit{bitmaps}) e as imagens vetoriais.

\subsection{Mapas de bits}

Mapa de bists é a representação matricial de uma imagem, onde cada posição,
chamada de \textit{pixel}, armazena uma cor. Normalmente os \textit{pixels} são
codificados no padrão RGB (\textit{Red}, \textit{Green},\textit{Blue}), que
utiliza três \textit{bytes} para armazenar um inteiro para as cores vermelha,
verde e azul, respectivamente. Em mídias impressas é comum que as imagens
\textit{bitmaps} utilizem o padrão
CMYK (\textit{Cian}, \textit{Magenta}, \textit{Yelow}, \textit{Black}) ao invés
do RGB.

Embora uma imagem bitmap seja armazenada na RAM com todos os \textit{pixels}, é
comum, por uma questão de economia de memória e tempo de transmissão, a compressão
destes arquivos. Entre os principais formatos de compressão estão
o GIF (\textit{Graphics Interchange Format}), o JPEG
(\textit{Joint Photographic Experts Group}) e o PNG (\textit{Portable Network Graphics}).

\subsection{Imagens vetoriais}

As imagens vetoriais são formadas pela descrição geométrica de objetos.
Por serem compostas de vetores, este tipo de imagem ocupa menos espaço na
memória comparado com as bitmaps, e não perdem a qualidade quando
aplicado transformações de escala e rotação sobre elas.