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_P(\mathcal{L}) = c - ax - by$ its {\it shift} to point $P(x,y)$,
$h_0(\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$, 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 of
arithmetical width $\nu = \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 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.}
  \label{fig:bs}
\end{figure}

The control of the assigned width $\varepsilon$ is ensured on the
following way.
At the beginning, a large width $\varepsilon_0$ is assigned to the
recognition problem to allow the detection of large blurred segments.
Then, when no more aumentation of the minimal width is observed as the
segment grows ($\mu_{i+\lambda} = \mu_i$), the assigned width is set at
a near value to the observed minimal width in order to avoid the
incorporation of spurious outliers in further parts of the segment.

\subsection{Directional scan}

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$ orthogonal to $\mathcal{D}$.
\begin{equation}
DS = \left\{ S_i = \mathcal{D} \cap \mathcal{N}_i \cap \mathcal{I} |
\delta(\mathcal{N}_i) = - \delta^{-1}(\mathcal{D})
\cap h_0(\mathcal{N}_i) = h_0(\mathcal{N}_{i-1}) + p(\mathcal{D}) \right\}
%S_i = \mathcal{D} \cap \mathcal{N}_i, \mathcal{N}_i \perp \mathcal{D}
\end{equation}
In this expression, 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$.

\begin{figure}[h]
\center
  \input{Fig_notions/fig}
  \caption{Example of directional scan.}
  \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$,
the scan strip is defined by :
\begin{equation}
\mathcal{D}(A,B) = \mathcal{L}(\delta_x, \delta_y, min (c1,c2), 1 + |c_1-c_2|)
\end{equation}
\noindent
where $\delta_x = x_B - x_A, \delta_y = y_B - y_A,
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{N}_i$ is then defined by :
\begin{equation}
\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{equation}
where $\nu_{AB} = max (|\delta_x|, |\delta_y|)$

%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$. The scan strip is :
\begin{equation}
\mathcal{D}(C,\vec{D},w)
= \mathcal{L}(y_D, -x_D, x_C\cdot y_D - y_C\cdot x_D - w / 2, w)
\end{equation}

\noindent
and the scan line $\mathcal{N}_i(C,\vec{D},w)$ :
\begin{equation}
\mathcal{N}_i(C,\vec{D},w) = \mathcal{L}(x_D, y_D,
     x_D\cdot x_C + y_D\cdot y_C - w / 2 + i\cdot w, max (|x_D|,|y_D|)
\end{equation}

\subsection{Adaptive directional scan}

The blurred segment is searched within a directional scan which position
and orientation are given by the user, or defined in arbitrary direction in
unsupervised mode.
Most of the times, the detection stops where the segment escapes sideways
froms the scan strip (\RefFig{fig:escape}).
Therefore a second search is run again using a second directional scan aligned
on the detected segment.
But only a quantized estimation of this blurred segment direction is given,
and the longer the real segment, the higher the probability to fail again
on a blurred segment escape from the directional scan.

\begin{figure}[h]
\center
  \begin{tabular}{c}
    \includegraphics[width=0.49\textwidth]{Fig_notions/escapeFirst_zoom.png}
  \end{tabular}
  \caption{Example of early detection failures
           on side escapes from the directional scan.}
  \label{fig:escape}
\end{figure}

%Even in ideal situation where the detected segment is a perfect line,
%its width is never null as a result of the discretization process.
%The estimated direction accuracy is mostly constrained by the length of
%the detected segment.
%To avoid these side escapes, the scan should not be a linear strip but
%rather a conic shape to take into account the blurred segment preimage.
%This side shift is amplified in situations where the blurred segment is
%left free to get thicker in order to capture possible noisy features.
%The assigned width is then still greater than the detected minimal width,
%so that the segment can move within the directional scan.
%Knowing the detected blurred segment shape and the image size, it is
%possible to define a conic scan area, but this solution is computationaly
%expensive because it leads to useless exploration of large image areas.
%
%\begin{figure}[h]
%\center
%  %\begin{picture}(300,40)
%  %\end{picture}
%  \input{Fig_notions/bscone}
%  \caption{Possible extension area based
%           on the detected blurred segment preimage.}
%  \label{fig:cone}
%\end{figure}

In the former work, an additional refinement step was run,
but doing so, the problem was just delayed further.
%The solution implemented in the former work was to let some arbitrary
%margin between the scan strip width and the assigned width to the detection,
%and to perform two fine detection steps, using for each of them the direction
%found at the former step.
This process could be itered as long as the blurred segment escapes from
the directional scanner using as any fine detection steps as necessary.
But the multiple detection of the same segment start points produces
a useless computational coast.

Here the proposed solution is to dynamically adapt the scan direction on
the detection result.
At each position $i+1$, the scan strip is updated using the direction
of the blurred segment computed at the former position $i$.
The adaptive directional scan $ADS$ is then defined by :
\begin{equation}
%S_i = \mathcal{D}_{i-1} \cap \mathcal{N}_i
ADS = \left\{ S_i = \mathcal{D}_i \cap \mathcal{N}_i \cap \mathcal{I} |
\delta(\mathcal{N}_i) = - \delta^{-1}(\mathcal{D}_0)
\cap h_0(\mathcal{N}_i) = h_0(\mathcal{N}_{i-1}) + p(\mathcal{D})
\cap \mathcal{D}_{i+1} = d (\mathcal{B}_i,\varepsilon) \right\}
\end{equation}
The last clause expresses the update of the scan bounds at step $i+1$.
Compared to static directional scans, the scan strip moves while
scan lines remain fixed.
An example of adaptive directional scan is given in \RefFig{fig:adaption}.

\begin{figure}[h]
\center
  \begin{tabular}{c@{\hspace{0.2cm}}c}
    \includegraphics[width=0.49\textwidth]{Fig_notions/adaptionBounds_zoom.png} &
    \includegraphics[width=0.49\textwidth]{Fig_notions/adaptionLines_zoom.png}
  \end{tabular}
  \caption{Example of blurred segment detection
           using an adaptive directional scan.
           On the right picture, the scan bounds are displayed in red, the
           detected blurred segment in blue, and its bounding lines in green.
           The left picture displays the successive scans.
           Adaption is quite sensible when crossing the tile joins.}
  \label{fig:adaption}
\end{figure}