\documentclass{crorr} %%%%% journal info -- DO NOT CHANGE %%%%%%%%% \setcounter{page}{15} \renewcommand\thisnumber{1} \renewcommand\thisyear {2014} \renewcommand\thismonth{xxx} \renewcommand\thisvolume{5} % \newtheorem{prop}{Proposition} % \newtheorem{exa}{Example} % \theoremstyle{remark} % \newtheorem{rem}{Remark} % \newtheorem{alg}{Algorithm} \newcommand\argmin{\mathop{\mathrm{argmin}}\nolimits} \newcommand{\R}{\mathbb{R}} %% ZA TABLICE % \usepackage{booktabs} % \usepackage{xcolor} %%%%% end %%%%%%%%% %%%%%%%%% already loaded packages -- DO NOT RELOAD %%%%% % \usepackage{amssymb} % \usepackage{amsmath,amsthm} % \usepackage{latexsym} % \usepackage{amsfonts} % \usepackage{amsbsyt} % \usepackage{graphicx} %%%%%% end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage[displaymath,mathlines,pagewise]{lineno} \begin{document} %\begin{linenumbers} \markboth{Tomislav Maro\v{s}evi\'c}{DATA CLUSTERING FOR CIRCLE DETECTION} \title[DATA CLUSTERING FOR CIRCLE DETECTION]{DATA CLUSTERING FOR CIRCLE DETECTION} \author[Tomislav Maro\v{s}evi\'c]{\bf Tomislav Maro\v{s}evi\'c\affil{1}\comma\corrauth} \address{\affilnum{1}\ Department of Mathematics, Josip Juraj Strossmayer University of Osijek\\ Trg Lj.\,Gaja 6, HR-31\,000 Osijek, Croatia\\ E-mail: $\langle$tmarosev@mathos.hr$\rangle$} \begin{abstract} This paper considers a multiple-circle detection problem on the basis of given data. The problem is solved by application of the center-based clustering method. For the purpose of searching for a locally optimal partition modeled on the well-known $k$-means algorithm, the $k$-closest circles algorithm has been constructed. The method has been illustrated by several numerical examples. \end{abstract} \keywords{data clustering, circle detection, $k$-means, locally optimal partition} \maketitle \section{Introduction} Grouping a data set into clusters is an important problem in many applications (e.g.\ facility location problem, pattern recognition, text classification, business, etc.) (see \cite{Gan, Kogan, Teboulle}). In this paper we consider a multiple-circle detection problem based on given data. This problem appears in several areas, such as pattern recognition, earthquake investigations, image analysis, machining of round parts, etc. (see e.g. \cite{DreznerBri, Qiao, ScitS, Song, Teboulle}). In solving the problem we apply a center-based clustering method. The points are grouped around circles such that the sum of distances from data points and appropriate closest circles is minimized. Let $\R^2$ denote the set of all points in the plane and $\R_+$ the set of nonnegative real numbers. A partition of the data-points set $\mathcal{A}=\{A_i=(x_i,y_i)\in\R^2\colon i=1,\dots,m\}\subset \R^2$ into $k$ disjoint subsets $\pi_1,\dots,\pi_k$, $1\leq k\leq m$, such that \begin{eqnarray*} \bigcup\limits_{i=1}^k \pi_i=\mathcal{A},\quad \pi_r\cap \pi_s=\emptyset,\quad r\neq s,\quad |\pi_j|\geq 1,\quad j=1,\dots,k, \end{eqnarray*} will be denoted by $\Pi(\mathcal{A})=\{\pi_1,\dots,\pi_k\}$, and the elements $\pi_1,\dots,\pi_k$ of such partition are called {\em clusters} in $\R^2$. Let us assume that all data from the set $\mathcal{A}$ come from some circles that should be reconstructed or detected. To each cluster $\pi_j\in\Pi$ we associate a corresponding circle-representative $C_j(p_j,$ $q_j,r_j)$ with centre $S_j=(p_j,q_j)$ and radius $r_j$ such that \begin{equation}\label{f3} (p^\star_j,q^\star_j,r^\star_j)=\argmin\limits_{p,q,r\in\R}\Phi_j(p,q,r),\quad \Phi_j(p,q,r)=\sum\limits_{A_i\in\pi_j}D(C(p,q,r),A_i), \end{equation} where $D(C(p,q,r),A_i)$ represents the distance from the point $A_i$ to the circle $C$. There is a number of recent literature focused on this problem \cite{Ahn, Chernov, Drezner, Gander}. If in \eqref{f3} we consider that the measure of the distance from the circle $C$ to the point has the form \begin{equation}\label{f4} D(C,A_i)=|\sqrt{(x_i-p)^2+(y_i-q)^2}-r |^2, \end{equation} then we talk about the \emph{total least squares} (TLS) optimality criterion. If we consider that the distance from the circle to the point is euclidean distance \begin{equation}\label{f5} D(C,A_i)=|\sqrt{(x_i-p)^2+(y_i-q)^2}-r|, \end{equation} then we apply the \emph{least absolute deviations} (LAD) optimality criterion (\cite{VazlerSS}). If we take that \begin{equation}\label{f6} D(C_j,A_i)=| (x_i-p)^2+(y_i-q)^2-r^2|^2, \end{equation} then we have the so-called algebraic fitting criterion. If we define an objective function $\mathcal{F}\colon\mathcal{P}(\mathcal{A},k)\to \R_{+}$ on the set of all partitions $\mathcal{P}(\mathcal{A},k)$ of the set $\mathcal{A}$ containing $k$ clusters in the sense of closest circles $C_1,\ldots,C_k$ by \begin{eqnarray}\label{f1} \mathcal{F}(\Pi)=\sum\limits_{j=1}^k\sum\limits_{A_i\in \pi_j} D(C_j,A_i), \end{eqnarray} then an optimal partition $\Pi^\star$ is a partition at which function $\mathcal{F}$ attains its minimum, i.e.\, $\Pi^\star=\argmin\limits_{\Pi\in \mathcal{P}(\mathcal{A},k)}\mathcal{F}(\Pi)$. Conversely, for a given set of circles $C_1,\dots,C_k$, applying the minimal distance principle, we can define the partition $\Pi=\{\pi_1,\dots,\pi_k\}$ of the set $\mathcal{A}$ in the following way: \begin{eqnarray*} \pi_j=\{A\in \mathcal{A}\colon D(C_j,A)< D(C_s,A),\,\forall s=1,\dots,k,\;s\neq j\},\quad j=1,\dots,k. \end{eqnarray*} Therefore, problem (\ref{f1}) of finding an optimal partition of the set $\mathcal{A}$ can be reduced to the following optimization problem \begin{equation}\label{f2} \argmin\limits_{C_1,\dots,C_k\subset{\R^2}}F(C_1,\dots,C_k),\quad F(C_1,\dots,C_k)=\sum\limits_{i=1}^m\min\limits_{j=1,\dots,k}D(C_j,A_i). \end{equation} In general, the functional $F$ is not differentiable and it may have several local and global minima. In \emph{Section~\ref{FIT}}, we look at the problem of fitting the circle, i.e.\ finding the optimal parameters of the circle on the basis of given data. With regard to the problem of data clustering by circles, in \emph{Section~\ref{ALG}} we give an algorithm for searching for a locally optimal partition by means of $k$-closest circles. In \emph{Section~\ref{EXA}}, several illustrative examples are mentioned. \section{Geometric and algebraic circle fits} \label{FIT} For problem (\ref{f3}) of locating a circle on the basis of the given set of $n$ fixed points $P_i=(x_i,y_i),\;i=1,\ldots,n$ in the plane, there exists a number of algorithms and methods. These methods are based on different measures and various criteria for defining a "closest" circle (see \cite{Brimberg, Chernov, Drezner, Nievergelt-mid}). Let $C(p,q,r)$ be a circle in the plane with center $S=(p,q)$ and radius $r$. If we apply criterion \eqref{f4}, then we have the following optimization problem \begin{equation} \label{f7} \argmin\limits_{p,q,r\in\R} G_2(p,q,r), \quad G_2(p,q,r)=\sum_{i=1}^{n} |\sqrt{(x_i-p)^2+(y_i-q)^2}-r |^2, \end{equation} which is based on minimizing the sum of squared distances from the fitting circle to data points. This is the \emph{(total) least squares} circle fitting (\cite{ChernovLes, Gander}). For solving optimization problem \eqref{f7}, one can use various iterative algorithms which are successful (e.g.\ the Levenberg-Marquardt, Landau algoritm, Sp\"ath algorithm \cite{ChernovLes}). In addition, one can apply criterion \eqref{f5} and then deal with the following optimization problem \begin{equation} \label{f8} \argmin\limits_{p,q,r\in\R} G_1(p,q,r), \quad G_1(p,q,r)=\sum_{i=1}^{n} |\sqrt{(x_i-p)^2+(y_i-q)^2}-r |, \end{equation} which is based on minimizing the sum of euclidean distances from the fitting circle to data points. This problem has also been analysed in literature (\cite{Brimberg, Nievergelt}) and an exact procedure exists for this problem. However, a heuristic approach (three points method) has also been suggested because it runs much faster than exact procedures. On the other hand, one can apply algebraic circle fitting wherein criterion (\ref{f6}) is taken into account. Then we get the following optimization problem \begin{equation} \label{f9} \argmin\limits_{p,q,r\in\R} G(p,q,r),\quad G(p,q,r)=\sum_{i=1}^{n} |(x_i-p)^2+(y_i-q)^2-r^2 |^2. \end{equation} Algebraic circle fitting refers to noniterative procedures that give good results in many applications. There exists simple algebraic fitting - K\"asa method and several modifications such as Chernov-Oroskov modification and Pratt circle fitting (\cite{Chernov}). One can also use another criterion of closeness of a circle to data, the so-called minimax criterion, where one deals with the optimization problem \[ \argmin\limits_{p,q,r} g(p,q,r),\quad g(p,q,r)=\max_{i=1,\ldots,n} \{ |\sqrt{(x_i-p)^2+(y_i-q)^2}-r | \}. \] There are algorithms for solving this problem, too (\cite{BrimbergJS, Nievergelt-mid}). The above mentioned methods for estimation and for searching for optimal parameters have certain properties and advantages, but also disadvantages (\cite{Chernov, Drezner, Nievergelt}). Particular problems frequently determine the choice of an appropriate criterion and specific methods for circle fitting. \section{$K$ closest circles algorithm} \label{ALG} As we have mentioned in the Introduction, the problem of finding an optimal partition of the set of points in the plane, $\mathcal{A}=\{A_i=(x_i,y_i)\in\R^2\colon i=1,\dots,m\}\subset \R^2$, into $k$ disjoint subsets grouped around circles $C_j(S_j(p_j,q_j),r_j)$, $j=1,\ldots,k,$ can be reduced to the following optimization problem (see (\ref{f1}), (\ref{f2})) \[ \argmin\limits_{C_1,\dots,C_k\subset{\R}^2} F(C_1,\dots,C_k), \] where \begin{equation} \label{f11} F(C_1,\dots,C_k)=\sum\limits_{i=1}^m\min\limits_{j=1,\dots,k}D(C_j,A_i) . %= \sum\limits_{j=1}^k\sum\limits_{A_i\in\pi_j}D(C_j,A_i) \end{equation} Function $\mathcal{F}$ given by \eqref{f1} and function $F$ given by \eqref{f11} coincide at optimal partition (\cite{Spaeth}). In general, optimization problem (\ref{f11}) is a nonconvex and nonsmooth optimization problem and it could have several local minima. So, one deals with the complex problem of finding an optimal solution. One of the most popular clustering algorithms for searching for a locally optimal partition is the $k$-means algorithm (\cite{Jain, Kogan}). Analogously to the $k$-means algorithm, we construct the \emph{$k$-closest circles algorithm}. \begin{algorithm} [$k$-closest circles (KCC) algorithm] \label{Alg2} $\,$ {\setlength{\leftmargini}{3.5em} \begin{itemize} \item[Step~0:] Input $1\leq k\leq m,\;$ $\mathcal{A}=\{A_i=(x_i,y_i)\in\R^2\colon i=1,\dots,m\}$. Choose an initial partition $\Pi^{(0)}=\{\pi_1^{(0)},\ldots,\pi_k^{(0)}\}$ and set $\mu=0$; \item[Step~1:] Solve the optimization problem\\ $ (p^{(\mu)}_j,q^{(\mu)}_j,r^{(\mu)}_j)=\argmin\limits_{p,q,r\in\R}\Phi_j(p,q,r),$ $\quad j=1,\ldots,k,$ \\ $ \Phi_j(p,q,r)=\sum\limits_{A_i\in\pi_j^{(\mu)}}D(C(p,q,r),A_i)$, \ \ and set $C_j^{(\mu)}=(p_j^{(\mu)},q_j^{(\mu)},r_j^{(\mu)})$; \item[Step~2:] (Assignment step) Determine a new partition (new clusters) \\ $\Pi^{(\mu+1)}=\{\pi_1^{(\mu+1)},\ldots,\pi_k^{(\mu+1)}\}$ according to the minimal distance principle {\small \begin{eqnarray*} \pi_1^{(\mu+1)} &=& \{A_i\in \mathcal{A}\colon D(C_1^{(\mu)},A_i)< D(C_l^{(\mu)},A_i),\,\forall l=2,\dots,k\},\\ \pi_j^{(\mu+1)} &=& \{A_i\in \mathcal{A}\setminus\cup_{s=1}^{j-1}\pi_s^{(\mu+1)}\colon D(C_j^{(\mu)},A_i)< D(C_l^{(\mu)},A_i),\,\\ && \forall l=j+1,\dots,k\}, \qquad j=2,\ldots,k-1, \\ \pi_k^{(\mu+1)} &=& \mathcal{A}\setminus\cup_{s=1}^{k-1}\pi_s^{(\mu+1)}\,. \end{eqnarray*} } \item[Step~3:] If $\Pi^{(\mu+1)}=\Pi^{(\mu)}$, STOP. Otherwise, set $\mu=\mu+1$ and go to Step~1. \end{itemize} } \end{algorithm} In \emph{Step~0}, the input data have been introduced and the initial partition has been chosen. In \emph{Step~1}, by solving the corresponding optimization problem, the corresponding circle-representative has been determined for each cluster. In \emph{Step~2}, in order to establish new clusters grouped around these circle-representatives, \emph{the minimal distance principle} has been applied. The following proposition shows that the proposed algorithm has a decreasing property. It enables us to apply the algorithm as a method for obtaining a (locally) optimal partition. \\ \begin{proposition} The $K$-closest circles algorithm does not increase the value of the objective function $\mathcal{F}$ defined by (\ref{f1}). \end{proposition} \begin{proof} From the proposed Algorithm 1 we obtain clusters $(\pi_1^{(\mu)},\ldots,\pi_k^{(\mu)})$ and the corresponding circles $(C_1^{(\mu)},\ldots,C_k^{(\mu)})$. It follows that \begin{eqnarray*} \mathcal{F}(C_1^{(\mu)},\ldots,C_k^{(\mu)}) &= & \sum\limits_{j=1}^k\sum\limits_{A_i\in \pi_j^{(\mu)}} D(C_j^{(\mu)},A_i) \\ (Step\; 2) \quad &\geq & \sum\limits_{j=1}^k\sum\limits_{A_i\in \pi_j^{(\mu+1)}} D(C_j^{(\mu)},A_i) \\ (Step\; 1) \quad &\geq & \sum\limits_{j=1}^k\sum\limits_{A_i\in \pi_j^{(\mu+1)}} D(C_j^{(\mu+1)},A_i)= \mathcal{F}(C_1^{(\mu+1)}, \ldots,C_k^{(\mu+1)})\,. \end{eqnarray*} \end{proof} \section{Examples} \label{EXA} In this section we give a few illustrative examples with various synthetic and empirical data. We suppose that the number of clusters $k$ is given in advance in all examples. Calculations were done by \emph{Mathematica} \cite{wolfram}. %%%%%%%%%%%%%%%% Fig.~1 %%%%%%%%%%%%%%%%%% \begin{figure}[ht] \centering \includegraphics[width=3.5cm]{Fig1a.eps} \put(-105,105){\small (a) Data } \qquad \includegraphics[width=3.5cm]{Fig1b.eps} \put(-120,105){\small (b) Initial circles: $F=99.6864$ } \caption{\it Initializations for the $k$-closest circles algorithm ($k=3$) } \label{Fig1} \end{figure} \begin{example}\label{Exa1} On the basis of three circles given in parametric form $K_i=S_i+r_i(\cos t,\sin t)$, $t\in[0,2\pi]$, $i=1,2,3,$ the set $\mathcal{A}$ of $85$ random points is generated by using binormal random additive errors with mean vector $0\in\R^2$ and the covariance matrix $\sigma^2I$, $\sigma^2=0.1$ (see Fig.~\ref{Fig1}a). The sum of orthogonal distances (LAD criterion) from these points to corresponding circles $K_1,K_2,K_3$ is $F=5.94991$. Circles should be reconstructed on the basis of the data-points set $\mathcal{A}$. By using the chosen circles shown in Fig.~\ref{Fig1}b, the initial partition has been determined according to the minimal distance principle. In Fig.~\ref{Fig2}, the first, the third, the fifth, the seventh, and finally the ninth iteration with the corresponding objective function value are shown. In the end, objective function value $F^\star=5.66076$ and circles are obtained, for which it can be said that they represent a good reconstruction of original circles. \end{example} %%%%%%%%%%%%%%%% Fig.~2 %%%%%%%%%%%%%%%%%% \begin{figure}[ht] \centering \includegraphics[width=3cm]{Fig2a.eps} \put(-85,90){\footnotesize (a) It~1: $F=16.72$ } \qquad \includegraphics[width=3cm]{Fig2b.eps} \put(-85,90){\footnotesize (b) It~3: $F=13.23$ } \qquad \includegraphics[width=3cm]{Fig2c.eps} \put(-85,90){\footnotesize (c) It~5: $F=5.78$ } \\[2ex] \includegraphics[width=3cm]{Fig2d.eps} \put(-85,90){\footnotesize (d) It~7: $F=5.77$ } \qquad \includegraphics[width=3cm]{Fig2e.eps} \put(-85,90){\footnotesize (e) It~9: $F=5.66$ } \caption{\it A few steps of the $k$-closest circles algorithm ($k=3$)} \label{Fig2} \end{figure} %%%%%%%%%%%%%%%% Table 1 %%%%%%%%%%%%%%%%%% \begin{table}[ht!] \begin{center} {\footnotesize \begin{tabular}{cclll}\\ \hline \multicolumn{2}{c}{Original 4 circles}& Algebraic fitting criterion & LAD criterion & TLS criterion \\ Center & Radius & Center \;\; Radius & Center \;\; Radius & Center \;\; Radius \\ \hline $(3,2)$ & $3$ & $(2.65,\,1.66) $ $\;\;\;\;$ $ 2.94$ & $(2.65,\,1.37) $ $\;\;\;\;$ $ 3.20$ & $(2.66,\,1.68) $ $\;\;\;\;\;$ $ 2.92$ \\ $(-0.5,0) $ & $ 1$ & $(-0.57,\,0.09) $ $\;\;$ $ 1.01$ & $(-0.48,\,0.12) $ $\;\;$ $ 0.98$ & $(-0.52,\,0.19) $ $\;\;\;$ $ 0.95$\\ $(0,-3) $ & $ 2$ & $(0.10,\,-2.81) $ $\;\;$ $ 1.92$ & $(0.05,\,-2.81) $ $\;\;$ $ 1.95$ & $(-0.10,\,-2.77) $ $\;\;$ $ 1.91$\\ $(2,-2) $ & $ 1.5$ & $(2.01,\,-1.65) $ $\;\;$ $ 1.51$ & $(3.43,\,0.90) $ $\;\;\;\;$ $ 1.95$ & $(1.68,\,-1.66) $ $\;\;\;$ $ 1.83$\\ \hline \end{tabular}} \caption{\it Centers and radii of circles} \label{Tab1} \end{center} \end{table} \begin{example}\label{Exa2} On the basis of four circles, the set $\mathcal{A}$ of $100$ pseudorandom points is generated by adding uniformly distributed pseudorandom errors in interval $[0,0.2]$ (see Fig.~\ref{Fig3}a). After that, an initial partition with $k=4$ clusters is obtained by Mathematica function FindClusters that uses the Euclidean distance and clusters the data based on proximity (see Fig.~\ref{Fig3}a). By using the KCC-algorithm with algebraic circle fitting - criterion \eqref{f6} (see Fig.~\ref{Fig3}b), with orthogonal distances - LAD criterion \eqref{f5} (see Fig.~\ref{Fig3}c) and with TLS criterion \eqref{f4}, we obtained corresponding circles. {\em Table 1} shows centers and radii of original four circles and of circles obtained by the KCC-algorithm for three criteria. We can say that the obtained circles-centers represent a good reconstruction of original circles and given data (with an exception of the fourth circle of the LAD criterion). \end{example} %%%%%%%%%%%%%%%% Fig.~3 %%%%%%%%%%%%%%%%%% \begin{figure}[ht] \centering \includegraphics[width=3.5cm]{Fig3a.eps} \put(-100,138){\small (a) Initial partition } \qquad \includegraphics[width=3.5cm]{Fig3b.eps} \put(-100,138){\small (b) Algebraic criterion } \qquad \includegraphics[width=3.9cm]{Fig3c.eps} \put(-100,138){\small (c) LAD criterion } \caption{\it Circles reconstruction} \label{Fig3} \end{figure} \begin{example}\label{Exa3} Similarly to Example~\ref{Exa1}, synthetic data are generated by four circles with the same center and different radii. With the initial partition shown in Fig.~\ref{Fig4}a the same KCC-locally optimal partition is obtained by using algebraic circle fitting - criterion \eqref{f6} (see Fig.~\ref{Fig4}b), by using orthogonal distances - LAD criterion \eqref{f5} and by using TLS criterion \eqref{f4}. The reconstructed circles by all three criteria \eqref{f4}, \eqref{f5} and \eqref{f6} are almost the same in this case. It can be seen that the obtained circles-centers of this partition represent a good reconstruction of the original circles. \end{example} %%%%%%%%%%%%%%%% Fig.~4 %%%%%%%%%%%%%%%%%% \begin{figure}[ht] \centering \includegraphics[width=5cm]{Fig4a.eps} \put(-140,155){\small (a) Data and initial partition} \qquad \includegraphics[width=5cm]{Fig4b.eps} \put(-140,155){\small (b) Algebraic criterion} \caption{\it Circles reconstruction} \label{Fig4} \end{figure} \begin{example}\label{Exa4} Similarly to Example~\ref{Exa1}, synthetic data are generated by ten circles with different centers and the same radius. With the initial partition shown in Fig.~\ref{Fig5}a, the KCC-locally optimal partition is obtained by using algebraic circle fitting - criterion \eqref{f6} (see Fig.~\ref{Fig5}b) and orthogonal distances - LAD criterion \eqref{f5} (see Fig.~\ref{Fig5}c). In this case, TLS criterion \eqref{f4} has given similar results as the LAD criterion. We can say that circles-centers obtained by using algebraic circle fitting represent a reconstruction of original circles well enough, which cannot be said for circles-centers obtained by using the LAD criterion. \end{example} %%%%%%%%%%%%%%%% Fig.~5 %%%%%%%%%%%%%%%%%% \begin{figure}[ht] \centering \includegraphics[width=3.9cm]{Fig5a.eps} \put(-125,120){\small (a) Data and initial partition} \quad \includegraphics[width=3.9cm]{Fig5b.eps} \put(-110,120){\small (b) Algebraic criterion } \quad \includegraphics[width=3.9cm]{Fig5c.eps} \put(-110,120){\small (c) LAD criterion } \caption{\it Circles reconstruction} \label{Fig5} \end{figure} \begin{remark} In the case of synthetic data constructed as in previous examples, one could determine a measure of quality of some partition by using Hausdorff distance between the set of original circles and the set of reconstructed circles (see e.g.\ \cite{ScitS}). \end{remark} \begin{example}\label{Exa5} In paper \cite{ScitS}, seismic activity data from a wider area of the Republic of Croatia has been considered in order to locate the most intense seismic activity in the observed area. It has been shown that the optimal partition with $k=13$ clusters points out at $13$ locations in which the most intense seismic activity in the observed area can be expected. For the purpose of analyzing the geometric position of circles at which some cluster centers are situated, it is interesting to find out that position (nine points-centers have been taken into account, \cite{ScitS}). %%%%%%%%%%%%%%%% Fig.~6 %%%%%%%%%%%%%%%%%% \begin{figure}[ht] \centering \includegraphics[width=4cm]{Fig6a.eps} \put(-110,135){\small (a) Algebraic criterion } \qquad \includegraphics[width=4.75cm]{Fig6b.eps} \put(-130,135){\small (b) LAD criterion } \caption{\it Circles reconstruction} \label{Fig6} \end{figure} Two corresponding circles have been obtained by using the KCC-algorithm: with algebraic circle fitting - criterion \eqref{f6} (see Fig.~\ref{Fig6}a), and with orthogonal distances - LAD criterion \eqref{f5} (see Fig.~\ref{Fig6}b). In this case, TLS criterion \eqref{f4} has also given two circles that are by the location of centers and radii between the results of criteria \eqref{f6} and \eqref{f5}. \end{example} \section{Conclusions} This paper considers the multiple-circle detection problem on the basis of given data-points set which comes from several circles in the plane. In solving the problem, a center-based clustering method has been applied. Let us note that numerical experiments show that the proposed KCC-algorithm has similar properties as the $k$-means algorithm and it can mainly give a locally optimal partition. If we have a good initial approximation, the KCC-algorithm can provide an acceptable solution. In the case we do not have a good initial approximation, the algorithm should be restarted with various random initializations, as proposed by \cite{Leisch2006}. It is assumed that the number of clusters is given in advance. The problem of determining the appropriate number of clusters in a partition is a specific problem that has not been considered in this paper. By applying the proposed KCC-algorithm, one can see a certain dependence of results of circles reconstruction on different criteria implemented for fitting of circles. It seems that algebraic criterion \eqref{f6} has a certain advantage since it includes both the smallest and the largest distance of the point from the circle $((d^2-r^2)^2=~(d-r)^2\cdot (d+r)^2)$; however, a more extensive investigation should be done with respect to this matter. %%%% Acknowledgment %%%%%%%% \section*{Acknowledgement} The author would like to thank Prof. Scitovski (University of Osijek, Croatia) for his support, helpful comments and useful suggestions. %%%% Bibliography %%%%%%%%%% \begin{thebibliography}{99} \bibitem{Ahn} Ahn, S.\,J., Rauh, W., and Warnecke, H.J. (2001). Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola. Pattern Recognition, 34, 2283-2303. \bibitem{Brimberg} Brimberg, J., Juel, H., and Sch\"obel, A. (2009). Locating a minisum circle in the plane. Discrete Applied Mathematics, 157, 901-912. \bibitem{BrimbergJS} Brimberg, J., Juel, H., and Sch\"obel, A. (2006). Locating a circle on the plane using the minimax criterion. IMM Technical Report, No. 1-2006. \bibitem{Chernov} Chernov, N. (2010). Circular and linear regression: Fitting circles and lines by least squares. Chapman\&Hall/CRC. \bibitem{ChernovLes} Chernov, N., and Lesort, C. (2005). Least Squares Fitting of Circles. Journal of Mathematical Imaging and Vision, 23, 239-252. \bibitem{Cupec} Cupec, R., Grbi\'c, R., Sabo, K., and Scitovski, R. (2009). Three points method for searching the best least absolute deviations plane. Applied Mathematics and Computation, 215, 983-994. \bibitem{DreznerBri} Drezner, Z., and Brimberg, J. (2013). Fitting concentric circles to measurements. Mathematical Methods of Operations Research, DOI 10.1007/s00186-013-0455-4, Springer, Published online. \bibitem{Drezner} Drezner, Z., Steiner, S., and Wesolowsky, G.O. (2002). On the circle closest to a set of points. Computers\&Operations Research, 29, 637-650. \bibitem{Gan} Gan, G., Ma, C, and Wu, J. (2007). Data Clustering: Theory, Algorithms, and Applications. Philadelphia: SIAM. \bibitem{Gander} Gander, W., Strebel, R., and Golub, G.H. (1995). Fitting of circles and ellipses least squares solution. SVD and Signal Processing III, 349-356. \bibitem{Jain} Jain, J. (2010). Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 31, 651-666. \bibitem{Kogan} Kogan, J. (2007). Introduction to Clustering Large and High-Dimensional Data. Cambridge: Cambridge University Press. \bibitem{Kogan2006b} Kogan, J., and Teboulle, M. (2006). Scaling clustering algorithms with Bregman distances. In: Berry, M.W., and Castellanos, M. (Eds.). Proceedings of the Workshop on Text Mining at the Sixth SIAM International Conference on Data Mining. \bibitem{Leisch2006} Leisch, F. (2006). A toolbox for k-centroids cluster analysis. Computational Statistics \& Data Analysis, 51, 526-544. \bibitem{Nievergelt} Nievergelt, Y. (2010). Median spheres: theory, algorithms, applications. Numerische Mathematik, 114, 573-606. \bibitem{Nievergelt-mid} Nievergelt, Y. (2002). A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres. Numerische Mathematik, 91, 257-303. \bibitem{Qiao} Qiao, Y., and Ong, S.H. (2004). Connectivity-based multiple-circle fitting. Pattern Recognition, 37, 755-765. \bibitem{SaboS} Sabo, K., and Scitovski, R. (2008). The best least absolute deviations line -- properties and two efficient methods. ANZIAM Journal, 50, 185-198. \bibitem{ScitS} Scitovski, R., and Scitovski, S. (2013). A fast partitioning algorithm and its application to earthquake investigation. Computers and Geosciences, 59, 124-131. \bibitem{Song} Song, Q., Yang, X., Soh, Y.C., and Wang, Z.M. (2010). An information-theoretic fuzzy C-spherical shells clustering algorithm. Fuzzy Sets and Systems, 161, 1755-1773. \bibitem{Spaeth} Sp\"{a}th, H. (1983). Cluster-Formation und Analyse. R.\ Oldenburg Verlag, M\"{u}nchen. \bibitem{Teboulle} Teboulle, M. (2007). A unified continuous optimization framework for center-based clustering methods. Journal of Machine Learning Research, 8, 65-102. \bibitem{VazlerSS} Vazler, I., Sabo, K., and Scitovski, R. (2012). Weighted median of the data in solving least absolute deviations problems. Communications in Statistics - Theory and Methods, 41, 1455-1465. \bibitem{wolfram} Wolfram, S. (1991). Mathematica - A System for Doing Mathematics by Computer. Addison-Wesley. \end{thebibliography} %\end{linenumbers} \end{document}