-
even authored3d4de8fe
notionsV2.tex 7.51 KiB
\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 \textbf{digital straight 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 $\vec{V}(\mathcal{L}) = (a,b)$ the director vector
of digital line $\mathcal{L}$, $w(\mathcal{L}) = \nu$ its arithmetical width,
$h(\mathcal{L}) = c$ its 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 {\it naive line}.
The {\it thickness} $\mu = \frac{\nu}{max(|a|,|b|)}$ of
% the digital straight line
$\mathcal{L}(a,b,c,\nu)$ is the minimum of the vertical and horizontal
distances between lines $ax + by = c$ and $ax + by = c + \nu$.
\begin{definition}
A \textbf{blurred segment} $\mathcal{B}$ of assigned thickness $\varepsilon$
is a set of points in $\mathbb{Z}^2$ that all belong to a covering digital
straight line $\mathcal{L}$ of thickness $\mu = \varepsilon$.
The \textbf{optimal line} of the blurred segment is the covering
line with minimal thickness.
The \textbf{thickness} of the blurred segment is the thickness of its
optimal line.
\end{definition}
A linear-time algorithm to recognize a blurred segment of assigned thickness
$\varepsilon$ \cite{DebledAl05} is used in this 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 thickness
$\varepsilon$ and thickness $\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 thickness
augments from $\mu_{i-1}$ to $\mu_i$; if the new thickness $\mu_i$ exceeds
the assigned thickness $\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
is an important point of the proposed method.
\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
\textbf{scan strip}, into scans $S_i$, each of them being a segment of a
naive line $\mathcal{N}_i$, called a \textbf{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}
\vec{V}(\mathcal{N}_i) \cdot \vec{V}(\mathcal{D}) = 0 \\
\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
$\vec{V}(\mathcal{N}_i) \cdot \vec{V}(\mathcal{D}) = 0$
expresses the orthogonality 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 traversed 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 iteratively 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
$p_{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 p_{AB},~ p_{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 a central point $C(x_C,y_C)$,
a direction $\vec{D}(X_D,Y_D)$ and a minimal thickness $w$.
If we note
$p_{\vec{D}} = max (|X_D|,|Y_D|)$,
$\nu_{\vec{D}} = \lceil w\cdot p_{\vec{D}} \rceil$,
$c_3 = x_C\cdot Y_D - y_C\cdot X_D - \frac{\nu_{\vec{D}}}{2}$,
and $c_4 = x_C\cdot X_D + y_C\cdot Y_D - \frac{p_{\vec{D}}}{2}$,
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,~ \nu_{\vec{D}}) \\
\mathcal{N}_i^{C,\vec{D},w} = \mathcal{L}(X_D,~ Y_D,~
c_4 + i\cdot p_{\vec{D}},~ p_{\vec{D}})
\end{array} \right.
\end{equation}