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{KletteRosenfeld04}.
Only the 2-dimensional case is considered here.

\begin{definition}
A digital line $\mathcal{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 arithmetic width of the digital line.
When $\nu = max (|a|, |b|)$, $\mathcal{D}$ 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
$\mathcal{S}_\varepsilon$ of points in $\mathbb{Z}^2$ that all belong
to a digital line of arithmetical width $\varepsilon$.
\end{definition}

Linear time algorithms have been developed to recognize a blurred segment
of assigned width $\varepsilon$ \cite{DebledAl05,Buzer07}.
They are based on an incremental growth of the convex hull of the blurred
segment when adding each point 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, that is computed by
Melkman's algorithm \cite{Melkman87}.
The extension of the blurred segment with a new input point is thus
controlled by the recognition test $\mu < \varepsilon$.

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

At the beginning, a large width $\varepsilon_{ini}$ is assigned to the
recognition problem to allow the detection of large blurred segments.
Then, when extending the blurred segment, this assigned width is
gradually decremented to reach the detected blurred segment minimal width.

\subsection{Directional scan}

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

\begin{figure}[h]
\center
  %\begin{picture}(300,40)
  %\end{picture}
  \input{Fig_notions/fig}
  \caption{Example of directional scan.}
  \label{fig:ds}
\end{figure}

The directional scan can be defined by its central scan line $\mathcal{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{
$\mathcal{S}(A,B) = \mathcal{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 $\mathcal{L}_i(A,B)$ is then defined by :

\centerline{
$\mathcal{L}_i(A,B) = \mathcal{S}(A,B) \cap \mathcal{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{
$\mathcal{S}(C,\vec{D},w) = \mathcal{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 $\mathcal{L}_i(A,B)$ by :

\centerline{
$\mathcal{L}_i(C,\vec{D},w) =
\mathcal{S}(C,\vec{D},w) \cap \mathcal{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 $\mathcal{S}$.