\documentclass{CNMAC-TEMA}

\usepackage[brazil]{babel}      % para texto em Portugu\^{e}s
%\usepackage[english]{babel}    % para texto em Ingl\^{e}s

\usepackage[latin1]{inputenc}   % para acentua\c{c}\~{a}o em Portugu\^{e}s
%\input{P-margin.inf}

\usepackage[]{cite,amssymb,fontsmpl,epsfig,subfigure,verbatim}
\usepackage[]{enumerate,subfigure,multirow,amsfonts}
\usepackage[]{psfrag}
\usepackage[]{amsmath}
\usepackage[]{multirow}
\usepackage[]{times}
\usepackage[]{pifont,bm}
\usepackage{colortbl}
\usepackage{xcolor}
\usepackage{booktabs}

\newcommand\mf[1]{\text{\boldmath$#1$}}
\newcommand{\N}{\mbox{I${\!}$N}}
\newcommand{\R}{\mbox{I${\!}$R}}
\newcommand{\Z}{\mbox{Z${\!\!}$Z}}
\newcommand{\Q}{\mbox{I${\!\!\!}$Q}}
\newcommand{\compl}{\mbox{I${\!\!\!}$C}}

%============DESENVOLVIMENTOS
\newtheorem{prop}{Proposi\c c\~ao}[section]
\newtheorem{pro}{Problema}[section]
\newtheorem{alg}{Algoritmo}[section]
\newtheorem{lem}{Lema}[section]
\newtheorem{deft}{Defini\c c\~ao}[section]
\newtheorem{teo}{Teorema}[section]
\newtheorem{cor}{Corol\'{a}rio}[section]
\newtheorem{conj}{Conjectura}[section]
\newtheorem{nota}{Nota}[section]

\begin{document}

\title{Uma Alternativa de Acelera\c{c}\~{a}o do Algoritmo \emph{Fuzzy} $K$-\emph{Means} Aplicado \`{a} Quantiza\c{c}\~{a}o Vetorial}

%\author
%    {
%    F. MADEIRO%
%	  \thanks{madeiro@poli.br}\,,
%     Escola Polit\'{e}cnica de Pernambuco, Universidade de Pernambuco, 50720-001, Recife, PE, Brasil.
%     \\ \\
%    R. R. A. GALV\~{A}O%
%     \thanks{rodrigoregisag@gmail.com.}\,,
%     Escola Polit\'{e}cnica de Pernambuco, Universidade de Pernambuco, 50720-001, Recife, PE, Brasil.
%    \\ \\
%    F. A. B. S. FERREIRA%
%     \thanks{felipebsferreira@gmail.com}\,,
%     Instituto de Estudos Avan\c{c}ados em Comunica\c{c}\~{o}es, 58429-900, Campina Grande, PB, Brasil.
%    \\ \\
%	 D. C. CUNHA%
%     \thanks{dcunha@cin.ufpe.br}\,,
%     Centro de Inform\'{a}tica, Universidade Federal de Pernambuco, 50740-560, Recife, PE, Brasil.
%     }

%\maketitle
\criartitulo

%\runningheads {Madeiro, Galv\~{a}o, Ferreira e Cunha}{\small Uma Alternativa de Acelera\c{c}\~{a}o do Algoritmo \emph{Fuzzy} $K$-\emph{Means} Aplicado \`{a} Quantiza\c{c}\~{a}o Vetorial}

\begin{abstract}
{\bf Resumo}. Compress\~{a}o de sinais, marca dī\'{a}gua digital e reconhecimento de padr\~{o}es s\~{a}o exemplos de aplica\c{c}\~{o}es de quantiza\c{c}\~{a}o vetorial (QV). Um problema relevante em QV \'{e} o projeto de dicion\'{a}rios. Neste trabalho, \'{e} apresentada uma alternativa de acelera\c{c}\~{a}o do algoritmo \emph{fuzzy} $K$-\emph{Means} aplicado ao projeto de dicion\'{a}rios. Resultados de simula\c{c}\~{o}es envolvendo QV de imagens e de sinais com distribui\c{c}\~{a}o de Gauss-Markov mostram que o m\'{e}todo proposto leva a um aumento da velocidade de converg\^{e}ncia (redu\c{c}\~{a}o do n\'{u}mero de itera\c{c}\~{o}es) do algoritmo \emph{fuzzy} $K$-\emph{Means} sem comprometimento da qualidade dos dicion\'{a}rios projetados.


{\bf Palavras-chave}. Quantiza\c{c}\~{a}o vetorial, \emph{Fuzzy} $K$-\emph{Means},
Codifica\c{c}\~{a}o de imagens.
\end{abstract}

\section{Introdu\c{c}\~{a}o}
A quantiza\c{c}\~{a}o \'{e} uma t\'{e}cnica relevante em sistemas de compress\~{a}o de sinais~\cite{madeiro_tutor_revista_iecom,gersho3}. Seu alvo \'{e} a digitaliza\c{c}\~{a}o (discretiza\c{c}\~{a}o) dos valores de amostras de um sinal. H\'{a} duas classes gerais de quantiza\c{c}\~{a}o: escalar e vetorial. A primeira consiste em um mapeamento $Q:\mathbb{R} \rightarrow C$, em que $C$ \'{e} um subconjunto do espa\c{c}o Euclidiano unidimensional $\mathbb{R}$. O n\'{u}mero de elementos de $C$ \'{e} denominado n\'{u}mero de n\'{\i}veis do quantizador, denotado por $L$. Ao final do processo de quantiza\c{c}\~{a}o, cada amostra poder\'{a} ser codificada, por exemplo, em uma palavra-bin\'{a}ria de $l=\log_2 L$ bits. A quantiza\c{c}\~{a}o vetorial (QV), por sua vez, consiste em um mapeamento $Q:\mathbb{R}^{N} \rightarrow W$, em que $W=\{{\vec w}_i;\ i=1, \ 2, \ \ldots, \ K \} \subset \mathbb{R}^{N}$ \'{e} denominado dicion\'{a}rio, $N$ \'{e} a dimens\~{a}o do quantizador vetorial e $K$ \'{e} o tamanho do dicion\'{a}rio (n\'{u}mero de vetores-c\'{o}digo). A taxa de codifica\c{c}\~{a}o da quantiza\c{c}\~{a}o vetorial \'{e} dada por $\frac{1}{N}\log_2 K$, expressa em bits por amostra em codifica\c{c}\~{a}o de forma de onda de voz e em bits por \emph{pixel} (bpp) em codifica\c{c}\~{a}o de imagem.

A Figura~\ref{fig:func_qv_ima} ilustra a QV de imagem, realizada no dom\'{\i}nio dos \emph{pixels} (dom\'{\i}nio original, isto \'{e}, sem uso de transformadas). Observa-se que a imagem \'{e} dividida em blocos de \emph{pixels}. No exemplo, s\~{a}o usados blocos de $4 \times 4$ \emph{pixels} (dimens\~{a}o $N=16$) e um dicion\'{a}rio de tamanho $K=32$. O processo de quantiza\c{c}\~{a}o consiste em substituir cada bloco de \emph{pixels} da imagem original pelo vetor-c\'{o}digo (bloco de \emph{pixel}) mais pr\'{o}ximo (segundo um crit\'{e}rio de dist\^{a}ncia) dentre os $32$ vetores-c\'{o}digo do dicion\'{a}rio. A qualidade da imagem quantizada depende do dicion\'{a}rio utilizado. Em outras palavras, dados dois dicion\'{a}rios de mesmo tamanho e mesma dimens\~{a}o, diz-se que um deles tem melhor qualidade quando leva \`{a} imagem quantizada com qualidade superior (segundo um crit\'{e}rio de distor\c{c}\~{a}o) \`{a} obtida com uso do outro dicion\'{a}rio.

\begin{figure}[htbp]
\centerline{\epsfig{figure=funcionamento_qv_imagem.ps,width=5.0cm}}
\caption{Exemplo de QV de imagem.\label{fig:func_qv_ima}}
\end{figure}

Dentre os desafios existentes em QV, podem ser citados: o projeto de dicion\'{a}rios~\cite{madeiro_lncs_renato_2008}, a complexidade computacional~\cite{waslon.cbrn03.meio} e a sensibilidade da t\'{e}cnica aos erros de transmiss\~{a}o~\cite{madeiro_tema_lima_2009}.
Ressalte-se que, al\'{e}m da compress\~{a}o de sinais, h\'{a} um amplo espectro de aplica\c{c}\~{o}es para QV, como, por exemplo, esteganografia~\cite{Chang2012, chang2009reversible}, marca d'\'{a}gua digital \cite{chen2009fuzzy, lin2009adaptive}, identifica\c{c}\~{a}o vocal \cite{Srinivasan2012} e classifica\c{c}\~{a}o de sinais de voz com patologias~\cite{trabalho_silvana_2012}.

Como t\'{e}cnicas para projeto de dicion\'{a}rios, podem ser citadas: algoritmo LBG (Linde-Buzo-Gray)~\cite{lbg}; algoritmos {\it fuzzy}~\cite{Tsekouras_2005} e algoritmos de aprendizagem competitiva~\cite{waslon.tema.2010} e algoritmos mem\'{e}ticos~\cite{waslon.capitulo.nicso.2009}. Em se tratando de QV de imagem, o alvo das t\'{e}cnicas \'{e} minimizar a distor\c{c}\~{a}o introduzida no processo de substitui\c{c}\~{a}o dos blocos de pixels originais pelos respectivos vetores-c\'{o}digo. No que diz respeito \`{a} QV de sinais unidimensionais, como \'{e} o caso dos sinais de voz, o alvo \'{e} minimizar a distor\c{c}\~{a}o introduzida ao se substitu\'{\i}rem os blocos de amostras originais pelos respectivos vetores-c\'{o}digo.

Neste trabalho, \'{e} apresentada uma t\'{e}cnica de acelera\c{c}\~{a}o do algoritmo \emph{fuzzy} $K$-\emph{Means} aplicado ao projeto de dicion\'{a}rios. Resultados de simula\c{c}\~{a}o concernentes \`{a} QV de imagens e de sinais com distribui\c{c}\~{a}o de Gauss-Markov mostram que a t\'{e}cnica apresentada leva a uma redu\c{c}\~{a}o do n\'{u}mero de itera\c{c}\~{o}es realizadas no projeto de dicion\'{a}rios, sem que haja comprometimento da qualidade dos dicion\'{a}rios obtidos. Conv\'{e}m mencionar que na literatura podem ser encontrados diversos trabalhos envolvendo l\'{o}gica nebulosa ({\it fuzzy}) no \^{a}mbito de QV, e.g.~\cite{Chang_2007, Filippi_2007, Gkalelis_2008, Phanprasit_2009, Pan_2011}.


\section{Algoritmo $K$-\emph{Means}}
O projeto de dicion\'{a}rios possui grande import\^{a}ncia para o bom desempenho de sistemas de compress\~{a}o de sinais baseados em QV. De uma maneira geral, o projeto de dicion\'{a}rios \'{e} um processo de agrupamento de dados (ou \emph{clus\-te\-ri\-za\-\c{c}\~{a}o})\cite{Duda_2001}. Tal processo consiste em agrupar um conjunto de dados ($M$ blocos ou vetores de amostras extra\'{\i}dos do conjunto de treino) em grupos ou \emph{clusters} ($K$ c\'{e}lulas de quantiza\c{c}\~{a}o, tal que $K<M$), de maneira que vetores do mesmo grupo apresentem alta similaridade entre si e possuam pouca similaridade com vetores de outros grupos.

Existem muitas t\'{e}cnicas para agrupamento de dados na literatura. Em \cite{Xu_2005}, elas s\~{a}o classificadas como m\'{e}todos hier\'{a}rquicos e m\'{e}todos de parti\c{c}\~{a}o. Os m\'{e}todos de parti\c{c}\~{a}o s\~{a}o subdivididos em m\'{e}todos de \emph{clus\-te\-ri\-za\-\c{c}\~{a}o} abrupta (\emph{hard}) e \emph{clusteriza\c{c}\~{a}o} \emph{fuzzy}. No primeiro caso, podemos citar o algoritmo $K$-\emph{Means} \cite{gersho3}, em que cada vetor de treino (bloco de amostras do conjunto de dados original) pertence a uma e apenas uma c\'{e}lula de quantiza\c{c}\~{a}o. J\'{a} no caso da t\'{e}cnica baseada em \emph{clusteriza\c{c}\~{a}o fuzzy}, na qual se enquadra, por exemplo, o algoritmo \emph{fuzzy} $K$-\emph{Means} \cite{karayiannis1}, cada vetor de treino pode estar associado a v\'{a}rias c\'{e}lulas de quantiza\c{c}\~{a}o, com um certo grau de pertin\^{e}ncia a cada c\'{e}lula.

O algoritmo $K$-\emph{Means} \'{e} brevemente apresentado a seguir.

Seja $X=\{{\vec x}_{j}\},j=1,2,...,M$,  um conjunto de treino composto por $M$ vetores $N$-dimensionais, com $M \gg K$. O algoritmo $K$-\emph{Means} particiona o espa\c{c}o vetorial
${\cal R}^N$ atribuindo cada vetor de treino a um \'{u}nico {\it cluster} atrav\'{e}s da busca do vizinho mais pr\'{o}ximo (VMP). Precisamente, ${\vec x}_{j}$ pertencer\'{a} ao {\it cluster} (ou regi\~{a}o de Voronoi ou c\'{e}lula de quantiza\c{c}\~{a}o) $V({\vec w}_i)$ se $d({\vec x}_{j},{\vec w}_{i}) < d({\vec x}_{j},{\vec w}_{a}), \forall a \neq i$, em que $d({\vec x}_{j},{\vec w}_{i})$ denota a dist\^{a}ncia Euclidiana quadr\'{a}tica entre ${\vec x}_j$ e ${\vec w}_i$. Neste caso, diz-se que ${\vec w}_i$ \'{e} o VMP de ${\vec x}_j$. Pode-se associar a busca do VMP a uma fun\c{c}\~{a}o de pertin\^{e}ncia, definida por

\begin{equation}
\mu_{i}\left({\vec x}_{j}\right)=\left\{ \begin{matrix}1,\; se\; {\vec w}_{i}={\rm VMP}({\vec x}_{j})\\
\hspace{-7pt}0,\; \mbox{ caso contr\'{a}rio}\;\;\;\;
\end{matrix}\right.~.
\end{equation}

Dessa forma, a distor\c{c}\~{a}o obtida ao se representarem todos os vetores do conjunto de treino pelos respectivos VMPs \'{e} dada por

\begin{equation}
J_{1}=\sum_{i=1}^{K}\sum_{j=1}^{M}\mu_{i}({\vec x}_{j})d({\vec x}_{j},{\vec w}_{i}).
\end{equation}

Para minimizar $J_1$, os vetores ${\vec w}_{i}$ s\~{a}o atualizados como segue:

\begin{equation}\label{eq:centroide}
{\vec w}_{i}=\frac{\sum_{j=1}^{M}\mu_{i}({\vec x}_{j}){\vec x}_{j}}{\sum_{j=1}^{M}\mu_{i}({\vec x}_{j})},~i=1,2,...,K.
\end{equation}

Depois de inicializado o conjunto de vetores ${\vec w}_{i}, i=1,2,...,K$, o algoritmo $K$-\emph{Means} aplicado ao projeto de dicion\'{a}rios (quantizadores vetoriais) pode ser assim resumido:

\begin{enumerate}
\item Particionamento -- o conjunto de treino \'{e} particionado em $K$ {\it clusters} de acordo com a regra do VMP.
\item Atualiza\c{c}\~{a}o do dicion\'{a}rio -- os novos vetores-c\'{o}digo s\~{a}o os centr\'{o}ides dos {\it clusters}, calculados de acordo com a Equa\c{c}\~{a}o~(\ref{eq:centroide}).
\item Teste de converg\^{e}ncia -- crit\'{e}rio de parada do algoritmo.
\end{enumerate}

As etapas de particionamento e atualiza\c{c}\~{a}o s\~{a}o realizadas at\'{e} que o crit\'{e}rio de parada seja satisfeito. Precisamente, o algoritmo p\'{a}ra ao final da $t$-\'{e}sima itera\c{c}\~{a}o se
\begin{equation}
\frac{J_{1}(t-1)-J_{1}(t)}{J_{1}(t)}\leq\epsilon,
\end{equation}
em que $\epsilon$ \'{e} um par\^{a}metro do algoritmo, denominado limiar de distor\c{c}\~{a}o, e $J_{1}(t)$ denota a distor\c{c}\~{a}o obtida no particionamento da $t$-\'{e}sima itera\c{c}\~{a}o.


\section{Algoritmo \emph{Fuzzy} $K$-\emph{Means}}

O algoritmo \emph{fuzzy} $K$-\emph{Means} tem por objetivo minimizar a distor\c{c}\~{a}o entre os vetores de treinamento ${\vec x}_j$ e os vetores-c\'{o}digo ${\vec w}_i$ que comp\~{o}em o dicion\'{a}rio. A medida de distor\c{c}\~{a}o \'{e} definida em \cite{Bezdek_1981} e dada por
\begin{equation}\label{eq:jm}
J_m = \sum\limits_{i=1}^K {\sum\limits_{j=1}^M {{\mu_i}\left({{\vec x}_j} \right)^m}} \,d\left({{\vec x}_j,{\vec w}_i} \right)~,1<m<\infty
\end{equation}
em que $\mu_i({\vec x}_j)$ \'{e} uma fun\c{c}\~{a}o que representa o grau de pertin\^{e}ncia do vetor ${\vec x}_j$ \`{a} $i$-\'{e}sima c\'{e}lula de quantiza\c{c}\~{a}o e $m$ \'{e} o par\^{a}metro que controla a nebulosidade da \emph{clusteriza\c{c}\~{a}o}. Para um determinado dicion\'{a}rio e considerando que $\mu_i({\vec x}_j) \in [0,1], i=1,\ldots, K$; $0 < \sum\limits_{j=1}^M {{\mu_i}\left({{\vec x}_j} \right)} < M$ e $\sum\limits_{i=1}^K {{\mu_i}\left({{\vec x}_j} \right)}=1$, a minimiza\c{c}\~{a}o da fun\c{c}\~{a}o $J_m$ resulta em
\begin{equation}
{\mu _i}\left( {{\vec x}_j} \right) = \frac{1}{{\sum\limits_{k=1}^K { \left({\frac{{d \left( {{\vec x}_j,{\vec w}_i} \right)}}{{d\left( {{\vec x}_j,{\vec w}_k} \right)}}}\right)^{\frac{1}{m-1}}} }}~.
\end{equation}
Para um dado conjunto de fun\c{c}\~{o}es de grau de pertin\^{e}ncia, os vetores-c\'{o}digo do dicion\'{a}rio podem ser obtidos por meio da minimiza\c{c}\~{a}o de $J_m({\vec w}_i)$, tal que
\begin{equation}
{\vec w}_i = \frac{{\sum\limits_{j=1}^M {{\mu_i}{{\left( {{\vec x}_j} \right)}^m}{\vec x}_j} }}{{\sum\limits_{j = 1}^M {{\mu_i}{{\left( {{\vec x}_j} \right)}^m}} }}~,i=1,2,\ldots, K.
\end{equation}

\subsection{Algoritmo \emph{Fuzzy} $K$-\emph{Means} Acelerado}
Um dos desafios em se tratando de m\'{e}todos de \emph{clusteriza\c{c}\~{a}o} \'{e} o aumento da velocidade de converg\^{e}ncia (re\-du\-\c{c}\-\~{a}o do n\'{u}mero de itera\c{c}\~{o}es). No \^{a}mbito da quantiza\c{c}\~{a}o vetorial, algumas alternativas foram propostas para acelerar o algoritmo $K$-\emph{Means}, tais como as t\'{e}cnicas de Lee {\it et al}. \cite{Lee_1997} e de Paliwal-Ramasubramanian \cite{Paliwal_2000}.

Em ambas as t\'{e}cnicas, ao final de cada itera\c{c}\~{a}o, os vetores-c\'{o}digo do dicion\'{a}rio s\~{a}o recalculados de acordo com a express\~{a}o
\begin{equation}
{{\vec w}_i^{~t}} = {{\vec w}_i^{~t-1}} + s\left( \mathcal{C} \left( V \left( {{\vec w}_i^{~t-1}} \right) \right) - {{\vec w}_i^{~t-1}} \right)~, \label{Eq:Atualiz}
\end{equation}
em que ${{\vec w}_i^{~t}}$ \'{e} o vetor-c\'{o}digo ${{\vec w}_i}$ na $t$-\'{e}sima itera\c{c}\~{a}o, $s$ \'{e} um fator de escala e $\mathcal{C} \left( V \left( {{\vec w}_i^{~t-1}} \right) \right)$ \'{e} o centr\'{o}ide da parti\c{c}\~{a}o $V \left( {{\vec w}_i^{~t-1}} \right)$. A diferen\c{c}a entre as t\'{e}cnicas de acelera\c{c}\~{a}o do algoritmo $K$-\emph{Means} est\'{a} no fator de escala $s$. Enquanto em \cite{Lee_1997} $s$ assume um valor fixo, na t\'{e}cnica de Paliwal-Ramasubramanian o fator de escala \'{e} fun\c{c}\~{a}o da itera\c{c}\~{a}o $t$, o que leva a uma maior velocidade de converg\^{e}ncia. Neste caso, o fator de escala $s$ \'{e} dado pela equa\c{c}\~{a}o
\begin{equation}
s = 1 + \frac{x}{(x+t)}~, \label{Eq:FEscala}
\end{equation}
em que $x>0$.

Assim, para as vers\~{o}es aceleradas do algoritmo $K$-\emph{Means}, cada novo vetor-c\'odigo n\~ao \'e mais determinado como o centr\'oide de sua classe, mas sim por um dos pontos na linha que conecta o vetor-c\'odigo atual com seu ponto refletido, passando pelo novo centr\'oide da classe, conforme ilustra a Figura~\ref{fig:lee_baek_sung}. O algoritmo $K$-\emph{Means} determina o ponto 2, correspondente ao novo centr\'oide da classe, como o novo vetor-c\'odigo. A proposta de Lee {\it et al}., ao utilizar uma abordagem do tipo {\it look ahead}, escolhe como novo vetor-c\'odigo um ponto entre os pontos 2 e 4, visando acelerar a converg\^encia do algoritmo $K$-\emph{Means}. Em suma, o novo vetor-c\'odigo \'e determinado da seguinte forma: {\it novo vetor-c\'odigo = vetor-c\'odigo atual + escala $\times$ (novo centr\'oide -- vetor-c\'odigo atual)}.

\begin{figure}[htb]
\centerline{\psfig{figure=fig_lee_baek.eps, width=7.5cm}}
\caption{Atualiza\c{c}\~ao do dicion\'ario pelo m\'etodo de Lee {\it et al}.\label{fig:lee_baek_sung}}
\end{figure}

Uma inspe\c{c}\~{a}o da Equa\c{c}\~{a}o~(\ref{Eq:Atualiz}) revela que a proposta de redu\c{c}\~{a}o do n\'{u}mero de itera\c{c}\~{o}es tem como pressuposto uma tend\^{e}ncia de deslocamento dos vetores-c\'{o}digo segundo uma trajet\'{o}ria aproximadamente retil\'{\i}nea. Simula\c{c}\~{o}es realizadas com projeto de dicion\'{a}rios para QV de sinais unidimensionais, realizadas pelos autores deste trabalho, mostraram que o pressuposto \'{e} satisfeito pelo algoritmo $K$-\emph{Means} bem como pelo \emph{fuzzy} $K$-\emph{Means}.

A t\'{e}cnica apresentada em \cite{Paliwal_2000}, utilizada para acelerar o algoritmo $K$-\emph{Means}, \'{e} aplicada neste trabalho para acelerar o algoritmo \emph{fuzzy} $K$-\emph{Means}.
Pela inspe\c{c}\~{a}o da Equa\c{c}\~{a}o (\ref{Eq:FEscala}), percebe-se que o fator de escala $s$ varia lenta e inversamente com a itera\c{c}\~{a}o $t$. A raz\~{a}o de se utilizar um fator de escala vari\'{a}vel se justifica pelo fato de que as atualiza\c{c}\~{o}es devem ser progressivamente menos acentuadas. Com isso, nas itera\c{c}\~{o}es pr\'{o}ximas \`{a} converg\^{e}ncia, n\~{a}o \'{e} interessante o uso de um fator de escala alto, sob o risco de haver uma perturba\c{c}\~{a}o indesejada no dicion\'{a}rio. Por fim, o fator $s$ deve satisfazer a duas condi\c{c}\~{o}es: (1) $s>1$, para assegurar uma converg\^{e}ncia mais r\'{a}pida que a do algoritmo \emph{fuzzy} $K$-\emph{Means}; (2) $s<2$, para evitar que o algoritmo tenha uma converg\^{e}ncia muito lenta ou n\~{a}o convirja.

Neste trabalho, portanto, a vers\~{a}o acelerada do algoritmo \emph{fuzzy} $K$-\emph{Means} consiste em recalcular os vetores-c\'{o}digo do algoritmo \emph{fuzzy} $K$-\emph{Means} convencional por meio das Equa\c{c}\~{o}es~(\ref{Eq:Atualiz}) e (\ref{Eq:FEscala}).

\section{Resultados}
Nesta se\c{c}\~{a}o, s\~{a}o apresentados resultados obtidos para projeto de dicion\'{a}rios usando como conjunto de treino (i) sinais com distribui\c{c}\~{a}o de Gauss-Markov e (ii) imagens digitais. Os algoritmos \emph{fuzzy} $K$-\emph{Means} (denotado por FKM) e \emph{fuzzy} $K$-\emph{Means} acelerado (denotado por AFKM) param ao final da $t$-\'{e}sima itera\c{c}\~{a}o, se
\begin{equation}
\frac{J_{m}(t-1)-J_{m}(t)}{J_{m}(t)}\leq\epsilon,
\end{equation}
com $J_m$ dado na Equa\c{c}\~{a}o~ (\ref{eq:jm}), com $m=5$, em conformidade com as recomenda\c{c}\~{o}es de~\cite{karayiannis1}, e $\epsilon=10^{-3}$ em todas as simula\c{c}\~{o}es realizadas.

Antes, entretanto, \'{e} importante mostrar que, a cada itera\c{c}\~{a}o, os vetores-c\'{o}digo no algoritmo FKM tendem a se deslocar segundo uma trajet\'{o}ria aproximadamente retil\'{\i}nea, conforme mostra a Figura~\ref{fig:vetores}, na qual as cores e os pontos indicados representam, respectivamente, regi\~{o}es de Voronoi e seus centr\'{o}ides. Desta forma, a Figura~\ref{fig:vetores} justifica a proposta de acelera\c{c}\~{a}o do presente artigo.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
  \hline
  {\epsfig{figure=iteracao_2.eps,width=5.5cm}} &
  {\epsfig{figure=iteracao_3.eps,width=5.5cm}} \\
  {\small (a) 2 itera\c{c}\~{o}es.} & {\small (b) 3 itera\c{c}\~{o}es.}\\
  {\epsfig{figure=iteracao_4.eps,width=5.5cm}} &
  {\epsfig{figure=iteracao_5.eps,width=5.5cm}} \\
  {\small (c) 4 itera\c{c}\~{o}es.} & {\small (d) 5 itera\c{c}\~{o}es.}\\ \hline
\end{tabular}
\caption{Trajet\'{o}ria de deslocamento retil\'{\i}nea dos vetores-c\'{o}digo no algoritmo FKM.\label{fig:vetores}}
\end{center}
\end{figure}

\subsection{Fonte de Gauss-Markov}
A fonte de Gauss-Markov de $1^{a}.$ ordem \'{e} tamb\'{e}m conhecida como fonte de Markov de $1^{a}.$ ordem ou fonte AR(1) \cite{gray1}. Para efeito de simplicidade, essa fonte ser\'{a} referenciada como fonte de Gauss-Markov ao longo de todo o texto.

O processo discreto de Gauss-Markov $\{X(n)\}$ \'{e} definido pela equa\c{c}\~{a}o

\begin{equation}\label{gauss1}
x(n)=ax(n-1)+w(n), \hspace{0.5em} \forall n
\end{equation}
em que $\{w(n)\}$ \'{e} uma sequ\^encia de vari\'aveis aleat\'orias Gaussianas independentes e identicamente distribu\'{\i}das com m\'{e}dia zero e $a$ \'{e} um par\^{a}metro denominado coeficiente de correla\c{c}\~{a}o, que determina o grau de correla\c{c}\~{a}o entre $x(n)$ e $x(n-1)$.

Em todas as simula\c{c}\~{o}es realizadas com sinais com distribui\c{c}\~{a}o de Gauss-Markov, utilizou-se conjunto de treinamento com 150.000 amostras. Foram projetados dicion\'{a}rios para QV com taxa de 1,0 bit por amostra. Essa taxa \'{e} obtida para diversas combina\c{c}\~{o}es de dimens\~{a}o $N$ e n\'{u}mero de n\'{\i}veis $K$, como, por exemplo, $N=6$ e $K=64$; $N=8$ e $K=256$. Para cada combina\c{c}\~{a}o, foram utilizadas 40 inicializa\c{c}\~{o}es aleat\'{o}rias diferentes de cada algoritmo. A qualidade dos dicion\'{a}rios projetados foi avaliada por meio da rela\c{c}\~{a}o sinal-ru\'{\i}do (SNR, {\it signal-to-noise ratio}), assim definida:
\begin{equation}
{\rm SNR}=10\log _{10}\left(\frac{\sum\limits_nx^2(n)}{%
\sum\limits_n[x(n)-y(n)]^2}\right),
\end{equation}
em que $x(n)$ e $y(n)$ representam, respectivamente, o sinal original e o sinal quantizado no instante de tempo $n$.

S\~{a}o apresentados resultados para valores m\'{e}dios de SNR dos sinais reconstru\'{\i}dos e n\'{u}mero m\'{e}dio de itera\c{c}\~{o}es para os dois algoritmos (FKM e AFKM), assim como o n\'{u}mero de casos em que o algoritmo AFKM realizou um n\'{u}mero menor de itera\c{c}\~{o}es (ou seja, teve maior velocidade de converg\^{e}ncia) que o algoritmo FKM e o n\'{u}mero de casos em que o algoritmo AFKM resultou em sinais reconstru\'{\i}dos com um valor maior de SNR m\'{e}dia.

Os resultados mencionados anteriormente est\~{a}o organizados nas Tabelas~\ref{tab:gauss} e \ref{tab:gauss2}, referentes a distribui\c{c}\~{o}es de Gauss-Markov com coeficientes de correla\c{c}\~{a}o $a=0,0$ e $a=0,9$, respectivamente. Observa-se na Tabela~\ref{tab:gauss}, por exemplo, para $K=64$, que o n\'{u}mero m\'{e}dio de itera\c{c}\~{o}es realizadas pelo algoritmo AFKM \'{e} igual a 20,15, ao passo que o n\'{u}mero correspondente para o algoritmo FKM \'{e} 24,30. Observa-se, ainda, que, dentre as 40 inicializa\c{c}\~{o}es, em 30 o algoritmo AFKM foi mais r\'{a}pido (realizou um menor n\'{u}mero de itera\c{c}\~{o}es) que o FKM; dentre essas 30, em 22 inicializa\c{c}\~{o}es o algoritmo AFKM levou a sinais reconstru\'{\i}dos com SNR superior \`{a} obtida com uso de dicion\'{a}rio FKM. De uma forma geral, a inspe\c{c}\~{a}o da Tabela~\ref{tab:gauss} revela que o algoritmo AFKM converge mais rapidamente que o algoritmo FKM (realiza um menor n\'{u}mero de itera\c{c}\~{o}es), sem que haja comprometimento dos dicion\'{a}rios projetados -- de fato, os valores m\'{e}dios de SNR obtidos com dicion\'{a}rios AFKM s\~{a}o, em geral, iguais ou ligeiramente superiores aos obtidos com dicion\'{a}rios FKM. Esse comportamento \'{e} tamb\'{e}m observado na Tabela~\ref{tab:gauss2}.

\begin{table}[htb]
\begin{center}
\caption{\label{tab:gauss}
Resultados obtidos para sinais com distribui\c{c}\~{a}o de Gauss-Markov com coeficiente de correla\c{c}\~{a}o $a=0,0$.}
\vspace{0.1cm}
\begin{tabular}{ccccccc}
\hline
  \multirow{2}{*}{\footnotesize $K$} & \multicolumn{2}{c}{\footnotesize SNR M\'{e}dia} & \multicolumn{2}{c}{\footnotesize N$^{o.}$ M\'{e}dio de Itera\c c\~{o}es} & {\scriptsize N$^{o.}$ de casos em que} & {\scriptsize N$^{o.}$ de casos em que} \\
  \cline{2-5}
  & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\scriptsize  AFKM teve menos itera\c c\~{o}es} & {\scriptsize  AFKM levou a maiores SNRs} \\
  \cline{1-7}
  {\footnotesize 4} & {\footnotesize 4,36} & {\footnotesize \textbf{4,38}} & {\footnotesize 8,75} & {\footnotesize \textbf{8,25}} & {\footnotesize 22} & {\footnotesize 16} \\
  \cline{1-7}
  {\footnotesize 8} & {\footnotesize 4,44} & {\footnotesize \textbf{4,45}} & {\footnotesize 12,12} & {\footnotesize \textbf{9,97}} & {\footnotesize 30} & {\footnotesize 18} \\
  \cline{1-7}
  {\footnotesize 16} & {\footnotesize 4,60} & {\footnotesize \textbf{4,62}} & {\footnotesize  17,46} & {\footnotesize  \textbf{14,76}} & {\footnotesize  28} & {\footnotesize  24} \\
  \cline{1-7}
  {\footnotesize 32} & {\footnotesize  4,76} & {\footnotesize  \textbf{4,79}} & {\footnotesize  21,43} & {\footnotesize  \textbf{18,72}} & {\footnotesize  32} & {\footnotesize  24} \\
  \cline{1-7}
  {\footnotesize 64} & {\footnotesize  4,95} & {\footnotesize  \textbf{4,96}} & {\footnotesize  24,30} & {\footnotesize  \textbf{20,15}} & {\footnotesize  30} & {\footnotesize  22} \\
  \cline{1-7}
  {\footnotesize 128} & {\footnotesize  5,33} & {\footnotesize  \textbf{5,35}} & {\footnotesize  25,60} & {\footnotesize  \textbf{21,56}} & {\footnotesize  28} & {\footnotesize  25} \\
  \cline{1-7}
  {\footnotesize 256} & {\footnotesize  5,63} & {\footnotesize  \textbf{5,63}} & {\footnotesize  26,78} & {\footnotesize  \textbf{20,18}} & {\footnotesize  30} & {\footnotesize  24} \\
\hline
\end{tabular}
\end{center}
%\end{table}


%%%%% Gauss-Markov 0.9
%\begin{table}[htb]
\begin{center}
\caption{\label{tab:gauss2}
 Resultados obtidos para sinais com distribui\c{c}\~{a}o de Gauss-Markov com coeficiente de correla\c{c}\~{a}o $a=0,9$.}
 \vspace{0.1cm}
\begin{tabular}{ccccccc}
\hline
  \multirow{2}{*}{\footnotesize $K$} & \multicolumn{2}{c}{\footnotesize SNR M\'{e}dia} & \multicolumn{2}{c}{\footnotesize N$^{o.}$ M\'{e}dio de Itera\c c\~{o}es} & {\scriptsize N$^{o.}$ de casos em que} & {\scriptsize N$^{o.}$ de casos em que} \\
  \cline{2-5}
  & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\scriptsize  AFKM teve menos itera\c c\~{o}es} & {\scriptsize  AFKM levou a maiores SNRs} \\
  \cline{1-7}
  {\footnotesize 4} & {\footnotesize 7,96} & {\footnotesize \textbf{7,96}} & {\footnotesize 12,32} & {\footnotesize \textbf{9,17}} & {\footnotesize 31} & {\footnotesize 25} \\
  \cline{1-7}
  {\footnotesize 8} & {\footnotesize 9,36} & {\footnotesize \textbf{9,38}} & {\footnotesize 18,95} & {\footnotesize \textbf{14,62}} & {\footnotesize 25} & {\footnotesize 20} \\
  \cline{1-7}
  {\footnotesize 16} & {\footnotesize 10,19} & {\footnotesize \textbf{10,20}} & {\footnotesize  26,52} & {\footnotesize  \textbf{25,45}} & {\footnotesize  22} & {\footnotesize  15} \\
  \cline{1-7}
  {\footnotesize 32} & {\footnotesize  10,70} & {\footnotesize \textbf{10,71}} & {\footnotesize  21,43} & {\footnotesize  \textbf{17,15}} & {\footnotesize  30} & {\footnotesize  29} \\
  \cline{1-7}
  {\footnotesize 64} & {\footnotesize  11,05} & {\footnotesize \textbf{11,06}} & {\footnotesize  24,30} & {\footnotesize  \textbf{19,25}} & {\footnotesize  34} & {\footnotesize  31} \\
  \cline{1-7}
  {\footnotesize 128} & {\footnotesize  11,33} & {\footnotesize \textbf{11,34}} & {\footnotesize  20,58} & {\footnotesize  \textbf{18,66}} & {\footnotesize  31} & {\footnotesize  27} \\
  \cline{1-7}
  {\footnotesize 256} & {\footnotesize  11,91} & {\footnotesize \textbf{11,92}} & {\footnotesize  24,15} & {\footnotesize  \textbf{19,92}} & {\footnotesize  30} & {\footnotesize  25} \\
\hline
\end{tabular}
\end{center}
\end{table}


\subsection{Imagens}
Os resultados apresentados nesta subse\c{c}\~{a}o foram obtidos considerando as imagens Elaine, Goldhill, Clock e Lena, todas com $256 \times 256$ pixels, $256$ n\'{\i}veis de cinza e ilustradas na Figura~\ref{fig:imagens}. Foi considerada QV com dimens\~{a}o $N=16$, o que corresponde a blocos de $4 \times 4$ \emph{pixels}, e dicion\'{a}rios projetados com $K=32$, $64$, $128$, $256$ e $512$ vetores-c\'{o}digo. Para cada tamanho de dicion\'{a}rio considerado, foram utilizadas 40 inicializa\c{c}\~{o}es aleat\'{o}rias diferentes de cada algoritmo. A qualidade dos dicion\'{a}rios projetados foi avaliada por meio da rela\c{c}\~{a}o sinal-ru\'{\i}do de pico (PSNR, \emph{peak signal-to-noise ratio}), assim definida para imagens $256 \times 256$ originalmente codificadas a $8,0$~bpp:
\begin{equation}
{\rm PSNR\,\,(dB)}= 10\log _{10}\left[ \frac{V_p^2}{{\rm
MSE}}\right],
\end{equation}
em que $F(i,j)$ e $\widehat F(i,j)$ representam, respectivamente, os valores de \emph{pixels} da $i$-\'{e}sima linha e $j$-\'{e}sima coluna das imagens original e reconstru\'{\i}da (quantizada), MSE ({\it mean square error}) denota o erro m\'{e}dio quadr\'{a}tico entre essas imagens e $V_p$ denota o maior valor de n\'{\i}vel de cinza (para o caso de imagens originais 8,0~bpp, tem-se $V_p=255$).

S\~{a}o apresentados resultados para os mesmos par\^{a}metros considerados na subse\c{c}\~{a}o referente a sinais com distribui\c{c}\~{a}o de Gauss-Markov. Tais resultados encontram-se organizados nas Tabelas~\ref{tab:imag_elaine} e \ref{tab:imag_goldhill}, referentes \`{a}s imagens Elaine e Goldhill, respectivamente, e na Figura \ref{fig:psnr_versus_iter_clock}, referente \`{a} imagem Clock, e devem ser entendidos como segue.

Considere, por exemplo, a Tabela~\ref{tab:imag_elaine}. Para o conjunto de treino correspondente \`{a} imagem Elaine e assumindo dicion\'{a}rios de tamanho $K=512$, o valor m\'{e}dio da PSNR das imagens reconstru\'{\i}das com dicion\'{a}rios obtidos pelo algoritmo FKM foi de $33,12$~dB, enquanto o correspondente valor m\'{e}dio obtido pelos dicion\'{a}rios AFKM foi de $33,18$~dB. Cabe ressaltar que os valores m\'{e}dios de PSNR calculados levam em considera\c{c}\~{a}o o uso de 40 inicializa\c{c}\~{o}es de dicion\'{a}rio distintas, conforme mencionado no in\'{\i}cio desta subse\c{c}\~{a}o. Ainda com rela\c{c}\~{a}o \`{a} Tabela~\ref{tab:imag_elaine} e considerando $K=512$, o n\'{u}mero m\'{e}dio de itera\c{c}\~{o}es do algoritmo FKM foi $47,07$, ao passo que o algoritmo AFKM teve uma maior velocidade m\'{e}dia de converg\^{e}ncia -- de fato, o n\'{u}mero m\'{e}dio de itera\c{c}\~{o}es para o algoritmo AFKM foi $32,06$. Para $K=512$, a Tabela~\ref{tab:imag_elaine} revela ainda que, das $40$ inicializa\c{c}\~{o}es consideradas, em $36$ delas o algoritmo AFKM realizou um menor n\'{u}mero de itera\c{c}\~{o}es. Por fim, dentre as $36$, em $28$ os dicion\'{a}rios AFKM levaram a imagens Elaine reconstru\'{\i}das com valores de PSNR superiores aos obtidos com os dicion\'{a}rios FKM.

Considere agora a Tabela~\ref{tab:imag_goldhill}. Para $K=512$, a t\'{e}cnica proposta no presente trabalho contribuiu para reduzir em cerca de $26\%$ o n\'{u}mero de itera\c{c}\~{o}es do algoritmo \emph{fuzzy} $K$-\emph{Means}. De fato, o algoritmo FKM tem um n\'{u}mero m\'{e}dio de itera\c{c}\~{o}es igual a $46,40$, enquanto o AFKM tem um n\'{u}mero m\'{e}dio de itera\c{c}\~{o}es igual a $34,24$. Para $K=512$, os valores m\'{e}dios de PSNR das imagens reconstru\'{\i}das foram bem pr\'{o}ximos com o uso de dicion\'{a}rios FKM e AFKM, sendo $30,76$~dB no primeiro caso e $30,82$~dB no segundo.

As Tabelas~\ref{tab:imag_elaine} e \ref{tab:imag_goldhill} mostram que, para cada imagem considerada nas simula\c{c}\~{o}es e os diversos valores de $K$ considerados, o algoritmo AFKM possui, em geral, uma maior velocidade de converg\^{e}ncia do que aquela apresentada pelo algoritmo FKM. Em outras palavras, para a maioria das $40$ inicializa\c{c}\~{o}es consideradas para cada valor de $K$, o algoritmo AFKM realiza um menor n\'{u}mero de itera\c{c}\~{o}es comparado ao algoritmo FKM. Adicionalmente, as tabelas revelam que o aumento de velocidade de converg\^{e}ncia n\~{a}o ocorre \`{a} custa de um comprometimento de qualidade dos dicion\'{a}rios projetados. Na realidade, o algoritmo AFKM produz, em geral, com um menor n\'{u}mero de itera\c{c}\~{o}es, dicion\'{a}rios de qualidade similiar ou levemente superior (valores de PSNR praticamente iguais ou ligeiramente superiores) \`{a}quela apresentada pelos dicion\'{a}rios FKM.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccccc}
  \hline
  {\epsfig{figure=elaine.ps,width=1.6cm}} &
  {\epsfig{figure=goldhill.ps,width=1.6cm}}&
  {\epsfig{figure=clock.ps,width=1.6cm}} &
  {\epsfig{figure=lena.ps,width=1.6cm}} \\
  {\small (a) Elaine.} & {\small (b) Goldhill.} & {\small (c) Clock.} & {\small (d) Lena.}\\ \hline
\end{tabular}
\caption{Imagens $256 \times 256$ usadas nas simula\c{c}\~{o}es.\label{fig:imagens}}
\end{center}
\end{figure}


\begin{table}[h]
\begin{center}
\caption{\label{tab:imag_elaine}
 Resultados obtidos para a imagem Elaine.}
 \vspace{0.1cm}
\begin{tabular}{ccccccc}
\hline
  \multirow{2}{*}{\footnotesize $K$} & \multicolumn{2}{c}{\footnotesize PSNR M\'{e}dia} & \multicolumn{2}{c}{\footnotesize N$^{o.}$ M\'{e}dio de Itera\c c\~{o}es} & {\scriptsize N$^{o.}$ de casos em que} & {\scriptsize N$^{o.}$ de casos em que} \\
  \cline{2-5}
  & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\scriptsize  AFKM teve menos itera\c c\~{o}es} & {\scriptsize  AFKM levou a maiores PSNRs} \\
  \cline{1-7}
  {\footnotesize 32} & {\footnotesize 27,61} & {\footnotesize \textbf{27,63}} & {\footnotesize 29,22} & {\footnotesize \textbf{25,35}} & {\footnotesize 28} & {\footnotesize 20} \\
  \cline{1-7}
  {\footnotesize 64} & {\footnotesize 29,01} & {\footnotesize \textbf{29,02}} & {\footnotesize 31,60} & {\footnotesize \textbf{25,05}} & {\footnotesize 29} & {\footnotesize 23} \\
  \cline{1-7}
  {\footnotesize 128} & {\footnotesize 30,34} & {\footnotesize \textbf{30,35}} & {\footnotesize 35,35} & {\footnotesize \textbf{26,80}} & {\footnotesize 32} & {\footnotesize 16} \\
  \cline{1-7}
  {\footnotesize 256} & {\footnotesize 31,71} & {\footnotesize \textbf{31,76}} & {\footnotesize 38,42} & {\footnotesize \textbf{31,36}} & {\footnotesize 33} & {\footnotesize 24} \\
  \cline{1-7}
  {\footnotesize 512} & {\footnotesize 33,12} & {\footnotesize \textbf{33,18}} & {\footnotesize 47,07} & {\footnotesize \textbf{32,06}} & {\footnotesize 36} & {\footnotesize 28} \\
\hline
\end{tabular}
\end{center}
%\end{table}


%Goldhill
%\begin{table}[htb]
\begin{center}
\caption{\label{tab:imag_goldhill}
 Resultados obtidos para a imagem Goldhill.}
 \vspace{0.1cm}
\begin{tabular}{ccccccc}
\hline
  \multirow{2}{*}{\footnotesize $K$} & \multicolumn{2}{c}{\footnotesize PSNR M\'{e}dia} & \multicolumn{2}{c}{\footnotesize N$^{o.}$ M\'{e}dio de Itera\c c\~{o}es} & {\scriptsize N$^{o.}$ de casos em que} & {\scriptsize N$^{o.}$ de casos em que} \\
  \cline{2-5}
  & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\scriptsize  AFKM teve menos itera\c c\~{o}es} & {\scriptsize  AFKM levou a maiores PSNRs} \\
  \cline{1-7}
  {\footnotesize 32} & {\footnotesize 26,49} & {\footnotesize \textbf{26,55}} & {\footnotesize 30,62} & {\footnotesize \textbf{25,03}} & {\footnotesize 25} & {\footnotesize 20} \\
  \cline{1-7}
  {\footnotesize 64} & {\footnotesize 27,53} & {\footnotesize \textbf{27,52}} & {\footnotesize 28,80} & {\footnotesize \textbf{21,55}} & {\footnotesize 30} & {\footnotesize 25} \\
  \cline{1-7}
  {\footnotesize 128} & {\footnotesize 28,45} & {\footnotesize \textbf{28,45}} & {\footnotesize 30,75} & {\footnotesize \textbf{24,85}} & {\footnotesize 32} & {\footnotesize 25} \\
  \cline{1-7}
  {\footnotesize 256} & {\footnotesize 29,54} & {\footnotesize \textbf{29,52}} & {\footnotesize 37,02} & {\footnotesize \textbf{27,33}} & {\footnotesize 34} & {\footnotesize 19} \\
  \cline{1-7}
  {\footnotesize 512} & {\footnotesize 30,76} & {\footnotesize \textbf{30,82}} & {\footnotesize 46,40} & {\footnotesize \textbf{34,24}} & {\footnotesize 37} & {\footnotesize 27} \\
\hline
\end{tabular}
\end{center}
\end{table}



Conforme se observa na Figura~\ref{fig:psnr_versus_iter_clock}, o algoritmo AFKM converge mais rapidamente que o FKM. De fato, o primeiro realiza um menor n\'{u}mero de itera\c{c}\~{o}es para projetar o dicion\'{a}rio. Al\'{e}m disso, a Figura~\ref{fig:psnr_versus_iter_clock} revela que, fixada uma itera\c{c}\~{a}o, o dicion\'{a}rio AFKM tem qualidade superior \`{a} do dicion\'{a}rio FKM, levando a uma imagem reconstru\'{\i}da com maior valor de PSNR. A Figura~\ref{fig:psnr_versus_iter_clock} tamb\'{e}m permite observar que uma determinada qualidade de imagem reconstru\'{\i}da (ou, de forma equivalente, uma dada qualidade de dicion\'{a}rio projetado) \'{e} obtida mais prematuramente (em um menor n\'{u}mero de itera\c{c}\~{o}es) pelo algoritmo AFKM.

\begin{figure}[htb]
\centerline{\epsfig{figure=clock_32_2_PSNR_versus_ITER.eps,width=8.3cm}}
\caption{PSNR da imagem Clock reconstru\'{\i}da ao final de cada itera\c{c}\~{a}o dos algoritmos FKM e AFKM, considerando a mesma inicializa\c{c}\~{a}o para ambos os algoritmos.\label{fig:psnr_versus_iter_clock}}
\end{figure}

Finalmente, \'{e} v\'{a}lido mencionar que abordagens evolutivas, e.g.~\cite{waslon.acivs2008.lncs}, podem levar a dicion\'{a}rios de melhor qualidade quando comparados aos obtidos pelo algoritmo AFKM. No entanto, tal superioridade \'{e} obtida \`{a}s custas de elevada complexidade computacional (opera\c{c}\~{o}es l\'{o}gicas e aritm\'{e}ticas, aplica\c{c}\~{a}o de operadores gen\'{e}ticos). Para a imagem Lena, por exemplo, para dicion\'{a}rios de tamanhos 32 e 64, h\'{a} um ganho de 0,25~dB e de 0,28~dB respectivamente ao serem usados dicion\'{a}rios projetados com o algoritmo~\cite{waslon.acivs2008.lncs} em substitui\c{c}\~{a}o aos dicion\'{a}rios AFKM.


\section{Conclus\~{a}o}
Neste trabalho, foi apresentada uma t\'{e}cnica para aumentar a velocidade de converg\^{e}ncia do algoritmo \emph{fuzzy} $K$-\emph{Means} aplicado ao projeto de dicion\'{a}rios para compress\~{a}o de sinais baseada em quantiza\c{c}\~{a}o vetorial. A t\'{e}cnica consiste, essencialmente, em recalcular os vetores-c\'{o}digo ao final de cada itera\c{c}\~{a}o do algoritmo, por meio de um procedimento que tem como pressuposto o deslocamento dos vetores-c\'{o}digo segundo trajet\'{o}rias aproximadamente retil\'{\i}neas ao longo das itera\c{c}\~{o}es do algoritmo. Por meio de simula\c{c}\~{o}es envolvendo o projeto de dicion\'{a}rios para quantiza\c{c}\~{a}o vetorial de sinais com distribui\c{c}\~{a}o de Gauss-Markov e imagens digitais, observou-se que a t\'{e}cnica proposta contribui para reduzir o n\'{u}mero de itera\c{c}\~{o}es realizadas pelo algoritmo \emph{fuzzy} $K$-\emph{Means}. Os resultados de simula\c{c}\~{o}es mostraram que o aumento da velocidade de converg\^{e}ncia do algoritmo n\~{a}o ocorre \`{a} custa de preju\'{\i}zo de qualidade dos dicion\'{a}rios projetados. Em outras palavras, a rela\c{c}\~{a}o sinal-ru\'{\i}do de pico (PSNR) das imagens reconstru\'{\i}das com o uso de dicion\'{a}rios projetados pela t\'{e}cnica proposta \'{e} praticamente a mesma ou ligeiramente superior \`{a} PSNR das imagens reconstru\'{\i}das com o uso de dicion\'{a}rios projetados pelo vers\~{a}o original do algoritmo \emph{fuzzy} $K$-\emph{Means}. Em projetos de dicion\'{a}rios com taxa de 1,0 bit por amostra, tendo como conjunto de treino uma fonte de Gauss-Markov de $1^{a}.$ ordem, a t\'{e}cnica apresentada neste trabalho levou a redu\c{c}\~{o}es de at\'{e} cerca de $25\%$ no n\'{u}mero m\'{e}dio de itera\c{c}\~{o}es.


\section*{Abstract}
Signal compression, digital watermarking and pattern recognition are examples of applications of vector quantization (VQ). A relevant problem concerning
VQ is codebook design. In this paper, an alternative is presented for accelerating the fuzzy $K$-Means algorithm applied to codebook design.
Simulation results involving VQ of images and Gauss-Markov signals show that the proposed method leads to an increase of convergence speed (reduction of the number of iterations) of the fuzzy $K$-Means algorithm without sacrificing the quality of the designed codebooks.

\bibliographystyle{waslon}
\bibliography{a_new2}
\end{document}


%Tifany
\begin{table}[!h]
\begin{center}
\caption{\label{tab:imag_tiffany}
 Resultados obtidos para a imagem Tiffany.}
 \vspace{0.1cm}
\begin{tabular}{ccccccc}
\hline
  \multirow{2}{*}{\footnotesize $K$} & \multicolumn{2}{c}{\footnotesize PSNR M\'{e}dia} & \multicolumn{2}{c}{\footnotesize N$^{o.}$ M\'{e}dio de Itera\c c\~{o}es} & {\scriptsize N$^{o.}$ de casos em que} & {\scriptsize N$^{o.}$ de casos em que} \\
  \cline{2-5}
  & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\footnotesize FKM} & {\footnotesize \textbf{AFKM}} & {\scriptsize  AFKM teve menos itera\c c\~{o}es} & {\scriptsize  AFKM levou a maiores PSNRs} \\
  \cline{1-7}
  {\footnotesize 32} & {\footnotesize 29,45} & {\footnotesize \textbf{29,47}} & {\footnotesize 28,40} & {\footnotesize \textbf{23,55}} & {\footnotesize 32} & {\footnotesize 25} \\
  \cline{1-7}
  {\footnotesize 64} & {\footnotesize 30,51} & {\footnotesize \textbf{30,52}} & {\footnotesize 30,52} & {\footnotesize \textbf{25,20}} & {\footnotesize 30} & {\footnotesize 21} \\
  \cline{1-7}
  {\footnotesize 128} & {\footnotesize 31,60} & {\footnotesize \textbf{31,61}} & {\footnotesize 34,72} & {\footnotesize \textbf{29,02}} & {\footnotesize 35} & {\footnotesize 24} \\
  \cline{1-7}
  {\footnotesize 256} & {\footnotesize 32,81} & {\footnotesize \textbf{32,88}} & {\footnotesize 40,70} & {\footnotesize \textbf{33,10}} & {\footnotesize 37} & {\footnotesize 31} \\
  \cline{1-7}
  {\footnotesize 512} & {\footnotesize 34,34} & {\footnotesize \textbf{34,42}} & {\footnotesize 47,25} & {\footnotesize \textbf{38,65}} & {\footnotesize 35} & {\footnotesize 30} \\
\hline
\end{tabular}
\end{center}
\end{table}