next up previous contents
Next: Tests Up: Detection of High Curvature Previous: Beus and Tiu BT87

The new algorithm

The proposed two-pass algorithm defines a corner in a simple and intuitively appealing way, as a location where a triangle of specified size and opening angle can be inscribed in a curve. A curve is represented by a sequence of points $\ipt{i}$ in the image plane. The ordered points are densely sampled along the curve, but, contrary to the other four algorithms, no regular spacing between them is assumed. A chain-coded curve can also be handled if converted to a sequence of grid points. In the first pass the algorithm scans the sequence and selects candidate corner points. The second pass is post-processing to remove superfluous candidates.

First pass. In each curve point $\cpt$ the detector tries to inscribe in the curve a variable triangle $(\bpt ,\cpt ,\fpt )$ constrained by a set of simple rules:
 \begin{align}\dmin^2 &\leq \vert \cpt - \fpt \vert^2 \leq \dmax^2 \nonumber \\
... \bpt \vert^2 \leq \dmax^2
\calpha &\leq \ialpha{max}, \nonumber
where $\vert \cpt - \fpt \vert = \vert\fvc \vert = \fln $ is the distance between $\cpt$and $\fpt$ , $\vert \cpt - \bpt \vert = \vert\bvc \vert = \bln $ the distance between $\cpt$and $\bpt$ , and $\calpha \in [-\pi , \pi]$ the opening angle of the triangle. (See figure 1a.) The latter is computed as

\begin{displaymath}\calpha = \arccos{\frac{\fln^2+\bln^2-\cln^2}{2\fln\bln}}

Figure: Detecting high curvature points. (a) Determining if $\cpt$ is a candidate point. (b) Testing $\cpt$ for sharpness non-maxima suppression.
\end{center} \end{figure}

Variations of the triangle that satisfy the conditions (7) are called admissible. Search for the admissible variations starts from $\cpt$ outwards and stops if any of the conditions (7) is violated. (That is, a limited number of neighboring points is only considered.) Among the admissible variations, the least opening angle $\palpha{\cpt}$ is selected. $\pi - \vert\palpha{\cpt}\vert$ is assigned to $\cpt$ as the sharpness of the candidate. If no admissible triangle can be inscribed, $\cpt$ is rejected and no sharpness is assigned.

Considering the vector product of $\bvc=(\bln_x,\bln_y)$ and $\cvc=(\cln_x,\cln_y)$, it is easy to see that the corner is convex if $\bln_x\cln_y-\bln_y\cln_x \geq 0$, otherwise it is concave.

Second pass. The sharpness based non-maxima suppression procedure is illustrated in figure 1b. A corner detector can respond to the same corner in a few consecutive points. Similarly to edge detection, a post-processing step is needed to select the strongest response by discarding the non-maxima points.

A candidate point $\cpt$ is discarded if it has a sharper valid neighbor $\ipt{v}$: $\palpha{\cpt} > \palpha{\ipt{v}}$. In the current implementation, a candidate point $\ipt{v}$ is a valid neighbor of $\cpt$ if $\vert \cpt - \ipt{v} \vert^2 \leq \dmax^2$. As alternative definitions, one can use $\vert \cpt - \ipt{v} \vert^2 \leq \dmin^2$ or the points adjacent to $\cpt$.

Parameters. $\dmin$, $\dmax$ and $\ialpha{max}$ are the parameters of the algorithm. $\dmin$ sets the scale (resolution), with small values responding to fine corners. The upper limit $\dmax$ is necessary to avoid false sharp triangles formed by distant points in highly varying curves. $\ialpha{max}$ is the angle limit that determines the minimum sharpness accepted as high curvature. In practice, we often set $\dmax = \dmin + 2$ and tune the remaining two parameters, $\dmin$ and $\ialpha{max}$. The default values are $\dmin = 7$ and $\ialpha{max} = 150^\circ $.

next up previous contents
Next: Tests Up: Detection of High Curvature Previous: Beus and Tiu BT87
Dmitry Chetverikov