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(\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 $\mathcal{L}$
of arithmetical width $w(\mathcal{L}) = \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}.
The enclosing digital segment $E(\mathcal{B})$ is the section of this
optimal digital straight line bounded by the end points of $\mathcal{B}$.
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
and $\mathcal{B}_i = \mathcal{B}_{i-1}$.}
  \label{fig:bs}
\end{figure}

Associated to this primitive, the following definition of a directional scan
also based on digital straight lines is also used in this work.

\subsection{Directional scan}

\begin{definition}
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$, called a {\it scan line}, orthogonal to $\mathcal{D}$.
\end{definition}

\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(\mathcal{N}_i) = h(\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 definition, 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 parsed 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(-88,13.5){$A$}
     \put(-185,111.5){$B$}
     \put(-20,98){$\mathcal{D}$}
     \put(-137,64){\color{blue}{$S_0$}}
     \put(-77,94){\color{red}{$S_8$}}
     \put(-183,64){\color{dgreen}{$S_{-5}$}}
     \put(-123,8){\color{blue}{$\mathcal{N}_0$}}
     \put(-60,30){\color{red}{$\mathcal{N}_8$}}
     \put(-169,8){\color{dgreen}{$\mathcal{N}_{-5}$}}
     \end{picture}
  \caption{A directional scan.
           The start scan $S_0$ is drawn in blue, odd scans in green,
           even scans in red, the bounds of scan lines $\mathcal{N}_i$
           with plain lines and the bounds of scan strip $\mathcal{D}$
           with 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$,
and if we note $\delta_x = x_B - x_A$, $\delta_y = y_B - y_A$,
$c_1 = \delta_x\cdot x_A + \delta_y\cdot y_A$,
$c_2 = \delta_x\cdot x_B + \delta_y\cdot y_B$ and
$\nu_{AB} = max (|\delta_x|, |\delta_y|)$, it is then defined by
the following scan strip $\mathcal{D}^{A,B}$ and scan lines
$\mathcal{N}_i^{A,B}$:
\begin{equation}
\left\{ \begin{array}{l}
\mathcal{D}^{A,B} =
\mathcal{L}(\delta_x,~ \delta_y,~ min (c1,c2),~ 1 + |c_1-c_2|) \\
\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{array} \right.
\end{equation}

%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$. If we note
$c_3 = x_C\cdot Y_D - y_C\cdot X_D$,
$c_4 = X_D\cdot x_C + Y_D\cdot y_C$,
$\nu_{\vec{D}} = max (|X_D|,|Y_D|)$,
it is then defined by
the following scan strip $\mathcal{D}^{C,\vec{D},w}$ and scan lines
$\mathcal{N}_i^{C,\vec{D},w}$:
\begin{equation}
\left\{ \begin{array}{l}
\mathcal{D}^{C,\vec{D},w}
= \mathcal{L}(Y_D,~ -X_D,~ c_3 - w / 2,~ w) \\
\mathcal{N}_i^{C,\vec{D},w} = \mathcal{L}(X_D,~ Y_D,~
               c_4 - w / 2 + i\cdot w,~ \nu_{\vec{D}}
\end{array} \right.
\end{equation}