
\documentclass[10pt,twocolumn]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{epsfig}

%TCIDATA{OutputFilter=Latex.dll}
%TCIDATA{LastRevised=Fri Apr 01 18:03:04 2005}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{CSTFile=article.cst}

\input{tcilatex}

\begin{document}

\title{My \LaTeX paper}
\author{G. A. Borges}
\maketitle

\section{Introduction}

Environment maps are extensively used in mobile robots navigation systems
for tasks like map-based positioning or global path planning. When the robot
moves on a flat ground, a 2-D map is sufficient to solve these problems. For
indoor environments, a such map can be extracted from a set of range data
provided by a rotating laser range finder. Planar surfaces that often occur
in structured environments are modeled by line segments. The process of line
extraction from range data must be executed on line while the robot is
moving, and it must provide an accurate polygonal model of the environment.
Classical algorithms initially used for this task \cite
{book:duda:73,article:siadat:97,article:vandorpe:96} are issued from the
edge segmentation methods developed for video image processing. These
algorithms are generally very sensitive to changes on some parameters. More
sophisticated methods like prototype-based fuzzy clustering algorithms \cite
{book:bezdek:81,article:frigui:99} are more robust but they are generally
more time expensive. In order to avoid some drawbacks of these solutions,
this paper proposes a split-and-merge segmentation algorithm based on the
fuzzy clustering approach.

In this paper, Section \ref{SectionFC} discuss about fuzzy clustering.
\[
\zeta =\left[ 
\begin{array}{cccc}
1 & 0 & \cdots  & 0 \\ 
0 & 1 &  &  \\ 
\vdots  &  & \ddots  &  \\ 
0 &  &  & 1
\end{array}
\right] 
\]

\section{Prototype-based fuzzy clustering algorithm}

\label{SectionFC}

The main objective of prototype-based fuzzy clustering algorithms is to
reduce iteratively a cost function $J$. Most \ algorithms use a cost
function given by 
\begin{equation}
J(\beta ,{\small U},\mathcal{Z})=\sum_{i=1}^{C}%
\sum_{j=1}^{N}u_{ij}^{m}d^{2}(x_{j},y_{j},\beta _{i}).  \label{EqJ}
\end{equation}

In eq. (\ref{EqJ}), $\beta _{i}$ represents the parameters of the \emph{i-th}
prototype and $u_{ij}^{m}$ is the grade of membership of the \emph{j-th}
point $(x_{j},y_{j})$ to the prototype $\beta _{i}$. $d(x_{j},y_{j},\beta
_{i})$ is a distance function between the point $(x_{j},y_{j})$ and the
prototype $\beta _{i}$ and $m$ is a constant. The fuzzy clustering algorithm
also imposes the following constraints: 
\begin{equation}
u_{ij}\in \lbrack 0,1],\quad 0<\sum_{j=1}^{N}u_{ij}<N,
\end{equation}
\begin{equation}
\sum_{i=1}^{C}u_{ij}=1,  \label{EqFCMConstraint}
\end{equation}

For the purposes of straight lines extraction, there exist different
representations for the prototypes $\beta _{i}$ based on the cluster
covariance matrix \cite{book:bezdek:81,article:frigui:99}. However, the new
approach proposed in this paper uses a more compact representation. This
representation is given by $\beta =\{(\rho _{i},\alpha _{i})\ |\ i=1,\ldots
,C\}$, where $\beta _{i}=(\rho _{i},\alpha _{i})$ are the polar parameters
of the \emph{i-th} straight line. From the polar representation of a line $%
\rho =x\cos (\alpha )+y\sin (\alpha )$ \cite{book:young:86}, a suitable
choice for the distance function $d$ is 
\begin{equation}
d^{2}(x_{j},y_{j},\beta _{i})=f^{2}(x_{j},y_{j},\beta
_{i})+g^{2}(x_{j},y_{j},\beta _{i}),  \label{Eqd2}
\end{equation}
where $f^{2}(x_{j},y_{j},\beta _{i})=(\rho _{i}-x_{j}\cos (\alpha
_{i})-y_{j}\sin (\alpha _{i}))^{2},$ and $g^{2}(x_{j},y_{j},\beta _{i})$ is
a penalty function for points that are very far from the cluster center.

Partitioning the data set $\mathcal{Z}$ into $C$ prototypes $\beta $ is
accomplished by minimizing the objective function \ $J$ (eq. (\ref{EqJ})).
In order to consider the constraints (\ref{EqFCMConstraint}), the Lagrange
multipliers method is used and the problem becomes to minimize 
\begin{equation}
V(\beta ,\mathcal{U},\mathcal{Z})=J(\beta ,\mathcal{U},\mathcal{Z}%
)+\sum_{j=1}^{N}\lambda _{j}\left( 1-\sum_{i=1}^{C}u_{ij}\right) ,
\end{equation}
where the $\lambda _{j}$'$s$ are the Lagrange's multipliers. $V$ is
minimized by using the alternating optimization method. Therefore, by
considering $\beta $ as constant, $u_{ij}$ is determined as the one that
satisfies $\partial V(\beta ,\mathcal{U},\mathcal{Z})/\partial u_{ij}=0$ and 
$\partial V(\beta ,\mathcal{U},\mathcal{Z})/\partial \lambda _{j}=0.$ Thus, $%
u_{ij}$ is given by 
\begin{equation}
u_{ij}=\frac{1}{\sum_{k=1}^{C}\left[ \frac{d^{2}(x_{j},y_{j},\beta _{i})}{%
d^{2}(x_{j},y_{j},\beta _{k})}\right] ^{\frac{1}{m-1}}}.  \label{EqU}
\end{equation}

In order to determine the parameters of the prototype $\beta _{i}$, the
membership measures $u_{ij}$ are considered as constants and the following
equations set is solved: $\partial J(\beta ,\mathcal{U},\mathcal{Z}%
)/\partial \beta _{i}=\mathbf{0}.$ Therefore, using eqs. (\ref{EqJ}) and (%
\ref{Eqd2}), it can be shown that $\rho _{i}$ and $\alpha _{i}$ are given by 
\begin{eqnarray}
\rho _{i} &=&\tilde{x}_{i}\cos (\alpha _{i})+\tilde{y}_{i}\sin (\alpha _{i}),
\label{EqRo} \\
\alpha _{i} &=&\frac{1}{2}\arctan \left( \frac{-2\tilde{S}_{xy_{i}}}{\tilde{S%
}_{yy_{i}}-\tilde{S}_{xx_{i}}}\right) ,  \label{EqAlfa}
\end{eqnarray}
where 
\begin{eqnarray}
\tilde{x}_{i} &=&\frac{\sum_{j=1}^{N}u_{ij}^{m}x_{j}}{%
\sum_{j=1}^{N}u_{ij}^{m}},\quad \tilde{y}_{i}=\frac{%
\sum_{j=1}^{N}u_{ij}^{m}y_{j}}{\sum_{j=1}^{N}u_{ij}^{m}},  \label{EqWCOG} \\
\tilde{S}_{xx_{i}} &=&\sum_{j=1}^{N}u_{ij}^{m}(x_{j}-\tilde{x}%
_{i})^{2},\quad \tilde{S}_{yy_{i}}=\sum_{j=1}^{N}u_{ij}^{m}(y_{j}-\tilde{y}%
_{i})^{2},  \nonumber \\
\tilde{S}_{xy_{i}} &=&\sum_{j=1}^{N}u_{ij}^{m}(x_{j}-\tilde{x}_{i})(y_{j}-%
\tilde{y}_{i}).  \nonumber
\end{eqnarray}

In the above development, the penalty function $g$ was kept as constant and
given by 
\begin{equation}
g^{2}(x_{j},y_{j},\beta _{i})=(x_{j}-\tilde{x}_{i})^{2}+(y_{j}-\tilde{y}%
_{i})^{2},
\end{equation}
where $\tilde{x}_{i}$ and $\tilde{y}_{i}$ are the weighted center of gravity
coordinates of the \emph{i-th} prototype from the last iteration (eq. (\ref
{EqWCOG})).

The prototype-based fuzzy line extraction algorithm is summarized as follows:

The main drawbacks of this algorithm are its sensitivity to initialization
(e.g. the initial prototypes), to local minima of $J$, to noise and outliers
and the difficulty to determine \emph{a priori} the number of lines $C$.
There exist other approaches to deal with these drawbacks as shown in \cite
{article:dave:97}.

\begin{figure}[t]
\centering
\setlength{\epsfxsize}{7.5cm}\centerline{\epsffile{angelrsx.eps}} %
\setlength{\epsfxsize}{7.5cm}\centerline{\epsffile{angellsz.eps}}
\caption{Simulation environment.}
\label{FigScenario}
\end{figure}

\bibliographystyle{unsrt}
\bibliography{exemplo2}

\end{document}
