notions.tex

\section{Base notions}

\subsection{Blurred segment}

Our work relies on the notion of digital straight line
as classically defined in the digital geometry literature \cite{debled}.
Only the 2-dimensional case is considered here.

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

The parameter $\nu$ is the width of the digital line.
If $\nu = max (|a|, |b|)$, $\cal D$ is the narrowest 8-connected line
and is called a naive line.

\begin{definition}
A blurred segment of width $\nu$ is a set ${\cal S}_\nu$ of points in
$\mathbb{Z}^2$ that all belong to a digital line of width $\nu$.
\end{definition}

\begin{picture}(300,20)
\framebox(300,20){Exemple de segment flou ? (\c ca va finir par lasser)}
\end{picture}

To construct a blurred segment we use a liner time algorithm based on the
incremental growth of the convex hull of the input points using Melkman
algorithm \cite{Melkman87}. Points are added while the convex hull width
is less than the blurred segment assigned width.

\subsection{Directional scan}

A directional scan is a partition of a digital straight line ${\cal S}$,
called the {\it scan strip}, into naive straight line segments ${\cal L}_i$,
that are orthogonal to ${\cal S}$. The segments, called {\it scan lines}, are
developed on each side of a central scan line ${\cal S}_0$, and labelled
with their manhattan distance ($d_1 = |d_x| + |d_y|$) to ${\cal L}_0$ and
a positive (resp.  negative) sign if their are on the left (resp. right)
of ${\cal L}_0$.

\begin{picture}(300,20)
\framebox(300,20){Exemple de directional scan}
\end{picture}

The directional scan can be defined by its central scan line ${\cal L}_0$.
If $A(x_A,y_A)$ and $B(x_B,y_B)$ are the end points of this scan line,
the scan strip is defined by :

\centerline{
${\cal S}(A,B) = {\cal D}(a, b, c, \nu)$, with
$\left\{ \begin{array}{l}
a = x_B - x_A \\
b = y_B - y_A \\
\nu = 1 + |c_2 - c_1| \\
c = min (c_1, c_2)
\end{array} \right.$
}
\noindent
where $c_1 = a\cdot x_A + b\cdot y_A$ and $c_2 = a\cdot x_B + b\cdot y_B$.

The scan line ${\cal L}_i(A,B)$ is then defined by :

\centerline{
${\cal L}_i(A,B) = {\cal S}(A,B) \cap {\cal D}(a', b', c', \nu')$, with
$\left\{ \begin{array}{l}
a' = y_B - y_A \\
b' = x_A - x_B \\
\nu' = max (|a'|,|b'|) \\
c' = a'\cdot x_A + b'\cdot y_A + i \cdot \nu'
\end{array} \right.$
}

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.

The 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$ :

\centerline{
${\cal S}(C,\vec{D},w) = {\cal D}(a, b, c, \nu)$, with
$\left\{ \begin{array}{l}
a = y_D \\
b = -x_D \\
\nu = w \\
c = a\cdot x_C + b\cdot y_C - w / 2
\end{array} \right.$
}

and the scan line ${\cal L}_i(A,B)$ by :

\centerline{
${\cal L}_i(C,\vec{D},w) =
{\cal S}(C,\vec{D},w) \cap {\cal D}(a', b', c', \nu')$, with
$\left\{ \begin{array}{l}
a' = x_D \\
b' = y_D \\
\nu' = max (|a'|,|b'|) \\
c' = a'\cdot x_C + b'\cdot y_C - w / 2 + i\cdot w
\end{array} \right.$
}

\subsection{Adaptive directional scan}

Notions \`a d\'evelopper :
\begin{itemize}
\item Direction de scan
\item Epaisseur de consigne du SF
\item Largeur optimale du SF
\end{itemize}

Poser le pb : la direction est incompl\`etement estim\'ee, d'o\`u un risque
de sortie de scan.
\begin{picture}(300,20)
\framebox(300,20){Illustration d'une sortie de scan avec les diff\'erentes
\'epaisseurs en jeu}
\end{picture}

La direction du segment ne peut \^etre connue qu'a posteriori.

La direction d'une droite discr\`ete s'affine au fur et \`a mesure de
son d\'eveloppement. 
Ainsi en va t-il des segments flous (a fortiori).

Il faut donc r\'eactualiser la direction du scan.

$N$ scans reste limit\'e.

D'o\`u le scan adaptatif $\rightarrow$ r\'eorientation de $\cal S$.