Newer
Older
This work relies on the notion of digital straight line as classically
defined in the digital geometry literature \cite{KletteRosenfeld04}.
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$.
In the following, we note $\delta(\mathcal{L}) = b/a$ the slope of
digital line $\mathcal{L}$, $w(\mathcal{L}) = \nu$ its arithmetical width,
$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.
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$.
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
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$.
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}$.}
Associated to this primitive, the following definition of a directional scan
also based on digital straight lines is also used in this work.
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}$.
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})
%S_i = \mathcal{D} \cap \mathcal{N}_i, \mathcal{N}_i \perp \mathcal{D}
$\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)
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.
% \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(-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}$}}
\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.}
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}$:
\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})
%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}$:
\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,~