notions.tex

\section{Theoretical background}

\label{sec:notions}

\subsection{Blurred segment}

This work relies on the notion of digital straight line as classically
defined in the digital geometry literature \cite{KletteRosenfeld04}.
Only the 2D case is considered here.

\begin{definition}
A digital line $\mathcal{L}(a,b,c,\nu)$, with $(a,b,c,\nu) \in \mathbb{Z}^4$,
is the set of points $P(x,y)$ of $\mathbb{Z}^2$ that satisfy :
$0 \leq ax + by - c < \nu$.
\end{definition}

In the following, we note $\delta(\mathcal{L}) = b/a$ the slope of
digital line $\mathcal{L}$, $w(\mathcal{L}) = \nu$ its arithmetical width,
$h_P(\mathcal{L}) = c - ax - by$ its {\it shift} to point $P(x,y)$,
$h_0(\mathcal{L}) = c$ its {\it shift} to origin, and
$p(\mathcal{L}) = max(|a|,|b|)$ its period (i.e. the length of its
periodic pattern).
When $\nu = p(\mathcal{L})$, then $\mathcal{L}$ is the narrowest 8-connected
line and is called a naive line.

\begin{definition}
A blurred segment $\mathcal{B}$ of assigned width $\varepsilon$ is a set
of points in $\mathbb{Z}^2$ that all belong to a digital line of
arithmetical width $\nu = \varepsilon$.
\end{definition}

A linear-time algorithm to recognize a blurred segment of assigned width
$\varepsilon$ \cite{DebledAl05} is used in the work.
It is based on an incremental growth of the convex hull of the blurred
segment when adding each point $P_i$ successively.
The minimal width $\mu$ of the blurred segment $\mathcal{B}$ is the
arithmetical width of the narrowest digital straight line that contains
$\mathcal{B}$.
It is also the minimal width of the convex hull of $\mathcal{B}$,
that can be computed by Melkman's algorithm \cite{Melkman87}.
As depicted on \RefFig{fig:bs},
the extension of the blurred segment $\mathcal{B}_{i-1}$ of assigned width
$\varepsilon$ and minimal width $\mu_{i-1}$ at step $i-1$ with a new input
point $P_i$ is thus controlled by the recognition test $\mu_i < \varepsilon$.

\begin{figure}[h]
\center
  \input{Fig_notions/bswidth}
  \caption{A growing blurred segment $\mathcal{B}_i$ :
when adding the new point $P_i$, the blurred segment minimal width
augments from $\mu_{i-1}$ to $\mu_i$; if the new width $\mu_i$ exceeds
the assigned width $\varepsilon$, then the new input point is rejected.}
  \label{fig:bs}
\end{figure}

\subsection{Directional scan}

A directional scan $DS$ is an ordered partition restricted to the image
domain $\mathcal{I}$ of a digital straight line $\mathcal{D}$,
called the {\it scan strip}, into scans $S_i$, each of them being a segment
of a naive line $\mathcal{N}_i$ orthogonal to $\mathcal{D}$.
\begin{equation}
DS = \left\{ S_i = \mathcal{D} \cap \mathcal{N}_i \cap \mathcal{I}
\left| \begin{array}{l}
\delta(\mathcal{N}_i) = - \delta^{-1}(\mathcal{D}) \\
\wedge~ h_0(\mathcal{N}_i) = h_0(\mathcal{N}_{i-1}) + p(\mathcal{D})
\end{array} \right. \right\}
%S_i = \mathcal{D} \cap \mathcal{N}_i, \mathcal{N}_i \perp \mathcal{D}
\end{equation}
In this expression, the clause
$\delta(\mathcal{N}_i) = - \delta^{-1}(\mathcal{D})$
expresses the othogonality constraint between the scan lines $\mathcal{N}_i$
and the scan strip $\mathcal{D}$.
Then the shift of the period $p(\mathcal{D})$ between successive scans
guarantees that all points of the scan strip are travelled one and only one
time.

The scans $S_i$ are developed on each side of a start scan $S_0$,
and ordered by their distance to the start line $\mathcal{N}_0$ with
a positive (resp. negative) sign if they are on the left (resp. right)
side of $\mathcal{N}_0$ (\RefFig{fig:ds}).
The directional scan is iterately processed from the start scan to both ends.
At each iteration $i$, the scans $S_i$ and $S_{-i}$ are successively processed.

\begin{figure}[h]
\center
%  \input{Fig_notions/fig}
  \includegraphics[width=0.8\textwidth]{Fig_notions/scanstrip.eps}
     \begin{picture}(1,1)(0,0)
     \thicklines
     \put(-176,112){\vector(2,-1){30}}
     \put(-90,19){\vector(-2,1){30}}
     {\color{dwhite}{
       \put(-181,114.5){\circle*{10}}
       \put(-84,16.5){\circle*{10}}
       \put(-16,102.5){\circle*{10}}
       \put(-132,66.5){\circle*{12}}
       \put(-72,96.5){\circle*{12}}
       \put(-175.5,65.5){\circle*{20}}
       \put(-117,10.5){\circle*{14}}
       \put(-54,32.5){\circle*{14}}
       \put(-161,10.5){\circle*{20}}
     }}
     \put(-185,112){$A$}
     \put(-88,14){$B$}
     \put(-20,98){$\mathcal{D}$}
     \put(-137,64){$S_0$}
     \put(-77,94){$S_8$}
     \put(-183,64){$S_{-5}$}
     \put(-123,8){$\mathcal{N}_0$}
     \put(-60,30){$\mathcal{N}_8$}
     \put(-169,8){$\mathcal{N}_{-5}$}
     \end{picture}
  \caption{A directional scan: the start scan $S_0$ in blue, odd scans in
           green, even scans in red, scan lines bounds $\mathcal{N}_i$ in
           plain lines and scan strip bounds $\mathcal{D}$ in dotted lines.}
  \label{fig:ds}
\end{figure}

A directional scan can be defined by its start scan $S_0$.
If $A(x_A,y_A)$ and $B(x_B,y_B)$ are the end points of $S_0$,
the scan strip is defined by :
\begin{equation}
\mathcal{D}(A,B) =
\mathcal{L}(\delta_x,~ \delta_y,~ min (c1,c2),~ 1 + |c_1-c_2|)
\end{equation}
\noindent
where $\delta_x = x_B - x_A$, $\delta_y = y_B - y_A$,
$c_1 = \delta_x\cdot x_A + \delta_y\cdot y_A$ and
$c_2 = \delta_x\cdot x_B + \delta_y\cdot y_B$.
The scan line $\mathcal{N}_i$ is then defined by :
\begin{equation}
\mathcal{N}_i(A,B) = \mathcal{L}(\delta_y,~ -\delta_x,~
\delta_y\cdot x_A - \delta_x\cdot y_A + i\cdot \nu_{AB},~ \nu_{AB})
\end{equation}
where $\nu_{AB} = max (|\delta_x|, |\delta_y|)$

%The scan lines length is $d_\infty(AB)$ or $d_\infty(AB)-1$, where $d_\infty$
%is the chessboard distance ($d_\infty = max (|d_x|,|d_y|)$).
%In practice, this difference of length between scan lines is not a drawback,
%as the image bounds should also be processed anyway.

A directional scan can also be defined by its central point $C(x_C,y_C)$,
its direction $\vec{D}(X_D,Y_D)$ and its width $w$. The scan strip is :
\begin{equation}
\mathcal{D}(C,\vec{D},w)
= \mathcal{L}(Y_D,~ -X_D,~ x_C\cdot Y_D - y_C\cdot X_D - w / 2,~ w)
\end{equation}

\noindent
and the scan line $\mathcal{N}_i(C,\vec{D},w)$ :
\begin{equation}
\mathcal{N}_i(C,\vec{D},w) = \mathcal{L}(X_D,~ Y_D,~
     X_D\cdot x_C + Y_D\cdot y_C - w / 2 + i\cdot w,~ max (|X_D|,|Y_D|)
\end{equation}