%% sample.tex VERSION 2 (February 9th, 2007 - revised February 12th, 2007)
%% sampledocument.tex VERSION 3 (April 27th, 2007)

%% A sample full paper template you modify and save as fullpaperdocument.tex
%% to produce your camera-ready full paper

%% +-------------+
%% | PAPER TITLE |
%% +-------------+

\renewcommand{\shorttitle}{A region-based interpolation method for mosaics}
%\title[ short-title ]{ full-title }
\title%
%    [A Region-Based Interpolation Method for Mosaics]% short title (maximum of 50 characters)
    {A region-based interpolation method for mosaic images}% full title

%\RunningHead{Vidal, Crespo and Maojo}{A Region-Based Interpolation
%Method for Mosaic Images}

%% +---------+
%% | AUTHORS |
%% +---------+
\begin{Authors}
    \Author
        {Javier Vidal}
        \Affil[AILFIUPM]{GIB - LIA,    %Artificial Intelligence Laboratory\\
               Facultad de Informática, Universidad Politécnica de Madrid, Spain
%              28660 Boadilla del Monte (Madrid), SPAIN\\
               \email{\{jvidal,jcrespo,vmaojo\}@infomed.dia.fi.upm.es}}
        \Affil{Departamento Ingeniería Informática y Ciencias de la Computación, Facultad de Ingeniería, Universidad de Concepcion, Chile\\
               \email{jvidal@udec.cl}}
    \Author
        {Jose Crespo}
        \Affilref[AILFIUPM]
    \Author
        {Víctor Maojo}
        \Affilref[AILFIUPM]
\end{Authors}


%% +-----------------------+
%% | ABSTRACT and KEYWORDS |
%% +-----------------------+
%% Abstract and keywords are written inside two environments,
%% the "Abstract" amd the "Keywords" environments, respectively.
%% Note the uppercase "A" and "K".
%% Keywords are separated with comma. The last keyword ends
%% with a period.

\begin{Abstract}
Image interpolation is an important operation in some image analysis
and processing applications. This paper describes a region-based
interpolation method for mosaic images. It is an extension of a
previously presented interpolation technique based on morphological
operations for binary images. Even though the principles used in
this method are similar to those used in the technique for binary
images, there are some substantial differences, pointed out in this
paper, due the nature of images treated. Some experimental results
are provided.
\end{Abstract}

\begin{Keywords}
    mathematical morphology,
    \Index{image processing},
    \Index{image analysis},
    \Index{interpolation},
    \Index{mosaic},
    \Index{median set}.
\end{Keywords}

%% +----------+
%% | SECTIONS |
%% +----------+
%\renewcommand{\baselinestretch}{0.99}

\vspace*{-0.5cm}
\section{Introduction}
\label{\fullpaperid:sec:Introduction}
%\vspace*{-0.cm}

Image interpolation is necessary in some image processing
applications. Methods for image interpolation construct new images
from a set of known ones, and they permit to increase the practical
resolution of data. However, it should be stated that the
interpolated images are obtained from the input images and depend
completely on them.

Mathematical morphology~\cites{Vidal:Serra82,Vidal:Serra88,Vidal:Soille2003,Vidal:DougLotu:03} techniques have been
used to design several interpolation
methods~\cites{Vidal:Beucher1998,Vidal:Bors2002,Vidal:Chatzis2000,Vidal:Guo1995,Vidal:Iwanowski2000a,Vidal:Iwanowski2000b,Vidal:Lee2000,Vidal:Meyer1994,Vidal:Meyer1996,Vidal:Serra1994,Vidal:Iwanowski2001,Vidal:Iwanowski2005,Vidal:Iwanowski2002b,Vidal:Vizireanu2003,Vidal:Beucher1994}
that deal with the shapes of the objects to be interpolated.
%
In this paper, we are especially interested in morphological
interpolation for mosaic
images~\cites{Vidal:Iwanowski2001,Vidal:Iwanowski2005,Vidal:Iwanowski2002b,Vidal:Vizireanu2003}.

The interpolation method for mosaics described in this paper is
morphological as well. The principles used are similar to those used
in an interpolation technique for binary images presented
in~\cites{Vidal:VidCreMao2005a,Vidal:VidCreMao2005b,Vidal:VidCreMao2006}.
%
These basic principles are two: an inclusion property and the
utilization of the median set as interpolator~\cite{Vidal:Soille1991}.
%
Despite such similarities, the nature of the treated images make it
necessary to treat some additional aspects, which are pointed out in
the paper.

The proposed method is region-based. In this work, the input images
are 2D mosaic images, i.e., 2D gray-level segmented images that are
composed of piecewise-constant regions.

This paper is organized as follows. Section~\ref{\fullpaperid:sec:summary}
presents a brief summary of the previously presented interpolation
technique. Section~\ref{\fullpaperid:sec:binaryImages2Mosaics} presents an
extension of this technique in order to treat the so-called border
images. Characteristics and technical details of this region-based
interpolation method are described in
Section~\ref{\fullpaperid:sec:mosaicImagesInterpolation}. Some experimental
results are provided in Section~\ref{\fullpaperid:sec:experimentalResults}.
Conclusions are commented in
Section~\ref{\fullpaperid:sec:commentariesAndConclusions}.

%----------------------------------------
%\vspace*{-0.4cm}
\section{A brief summary of an interpolation technique for binary images}
\label{\fullpaperid:sec:summary}
%\vspace*{-0.2cm}

The technique reported in this paper is based on a previous work of
ours applied to binary images~\cites{Vidal:VidCreMao2005a,Vidal:VidCreMao2005b,Vidal:VidCreMao2006}. It will be
briefly described in this section.

%\vspace*{-0.4cm}
\subsection{Inclusion property}
\label{\fullpaperid:sec:inclusionProperty}
%\vspace*{-0.2cm}

Our technique is based on an inclusion property that establishes a
relationship which we think can greatly facilitate and improve the
results of interpolation methods for binary images. It establishes
% a constraint in how
the recursive interpolation of shapes with internal structures
(pores and grains).
% are interpolated.

Formally, if $A_i$ and $B_i$ are two sets of input slice 1, such
that $B_i \subset A_i$, and $A_j$ and $B_j$ are two sets of input
slice 2, such that $B_j \subset A_j$, and we want to interpolate
$A_i$ with $A_j$, and $B_i$ with $B_j$, then the following condition
should be satisfied:

\vspace*{-0.5cm}
\begin{equation}
\INT (A_i \setminus B_i, A_j \setminus B_j) = \INT (A_i, A_j)
\setminus \INT (B_i, B_j),
%
\label{\fullpaperid:eq:inclusionProperty}
\end{equation}
\vspace*{-0.6cm}

\noindent ``$\INT$'' corresponds to the interpolation computation.
The arguments of $\INT$ are the two images to be interpolated and
its result is the interpolated one. \autoref{\fullpaperid:fig:inclusionProperty}
illustrates inclusion property: Figure \ref{\fullpaperid:fig:inclusionProperty}(b)
is equal to Figure \ref{\fullpaperid:fig:inclusionProperty}(e) minus
Figure \ref{\fullpaperid:fig:inclusionProperty}(h).


\begin{figure}[t!]
\centering
\begin{tabular}{ccc}
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1g.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1h.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1i.pdf}\\
\LET{a}{Input set 1} & \LET{b}{Interpolated set} & \LET{c}{Input set 2} \\ \\
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1a.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1b.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1c.pdf}\\
%\LET{d}{Filled \CC~1} & \LET{e}{Interpolated filled \CC} & \LET{f}{Filled \CC~2} \\
\LET{d}{Filled grain~1} & \LET{e}{Interpolated filled grain} & \LET{f}{Filled grain~2} \\ \\
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1d.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1e.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/i1f.pdf}\\
\LET{g}{Hole~1} & \LET{h}{Interpolated hole} & \LET{i}{Hole~2} \\
\end{tabular}
%
%\vspace*{-0.3cm}
\caption{Inclusion property example. Part~(d) is the filled grain of
part~(a). Similarly, part~(f) is the filled grain of part~(c).
Parts~(g) and~(i) are the holes of, respectively, parts~(a)
and~(c).} \vspace*{-0.5cm} \label{\fullpaperid:fig:inclusionProperty}
\vspace{2mm}
\end{figure}

%\vspace*{-0.3cm}
\subsection{Binary image interpolation algorithm}
\label{\fullpaperid:sec:binaryTechniqueAlgorithm}
%\vspace*{-0.1cm}

In the algorithm for interpolating binary
images~\cites{Vidal:VidCreMao2005a,Vidal:VidCreMao2005b,Vidal:VidCreMao2006}, we can
distinguish three main sections: (1) separation of outer \CCs~from
each slice, (2) matching of \CCs~(one from input slice 1 and another
from input slice 2), and (3) interpolation of matched \CCs. Note
that in this technique \CC~refers to a connected component, and it
can denote a grain or a hole.

In the first step, the outer filled \CCs~of the input slices are
identified and separated. The outer filled \CCs~are the filled
\CCs\ surrounded by the background pixels that touch the border of the
image. Then, in the matching step, the method establishes correspondences
between \CCs~from the different slices. Those \CCs~that match will
be aligned in order to overlap them and, after that, interpolated
using a median set computation.

A detailed description of the algorithm pseudo-code for
interpolating binary images can be found in~\cite{Vidal:VidCreMao2005a}.

\vspace*{-0.4cm}
%\section{The Problem of Border Regions in Mosaic Images}
\section{Treatment of border regions in mosaic images}
\label{\fullpaperid:sec:binaryImages2Mosaics}
%\vspace*{-0.2cm}

%Although the principles used in the presented method for mosaic
%images are similar to those used in the technique for binary images
%summarized in the previous section, there are some considerations to
%be made that are related to the nature of the input images (mosaic
%images).

In the first step of the mosaic interpolation method, regions of
connected pixels with the same gray-level are extracted from the
pair of input slices
%
and are converted to binary images.
%
Some of the extracted regions touch the border of the images. These
regions pose a distinctive problem that must be treated and
satisfactorily solved. Next section describes how our technique
deals with it. It should pointed out that this
%problem
issue was
%practically non-existent in binary images (and it was
not treated in \cites{Vidal:VidCreMao2005a,Vidal:VidCreMao2005b,Vidal:VidCreMao2006}).

\vspace*{-0.4cm}
\subsection{Classification of border images}
\label{\fullpaperid:sec:classificationBorderImages}
%\vspace*{-0.2cm}

A ``binary border image'' is an image that has a \CC~that touches
its border. In formal terms, let $I$ and $X$ represent,
respectively, a binary image and a connected component (clearly, $X
\subseteq I$).
%
\vspace*{2mm}
%\begin{wrapfigure}[7]{r}[0.05\width]{0cm}
\begin{figure}[h!]
\centering
\renewcommand{\baselinestretch}{0.5}% for tabular environment
\small
\begin{tabular}{cccc}
\setlength{\fboxrule}{1.3pt}\setlength{\fboxsep}{3.5pt}
\fbox{\includegraphics[trim = 6 6 6 6,width=1.25cm]{\fullpaperpdirectory/images/testImage1.pdf}}&
\setlength{\fboxrule}{1.3pt}\setlength{\fboxsep}{3.5pt}
\fbox{\includegraphics[trim = 6 6 6 6,width=1.25cm]{\fullpaperpdirectory/images/testImage2.pdf}}&
\setlength{\fboxrule}{1.3pt}\setlength{\fboxsep}{3.5pt}
\fbox{\includegraphics[trim = 6 6 6 6,width=1.25cm]{\fullpaperpdirectory/images/testImage3.pdf}}&
\setlength{\fboxrule}{1.3pt}\setlength{\fboxsep}{3.5pt}
\fbox{\includegraphics[trim = 6 6 6 6,width=1.25cm]{\fullpaperpdirectory/images/testImage4.pdf}}\\
&&&\\
%\borderFigure{1.25}{\fullpaperpdirectory/images/testImage1.pdf}&
%\borderFigure{1.25}{\fullpaperpdirectory/images/testImage2.pdf}&
%\borderFigure{1.25}{\fullpaperpdirectory/images/testImage3.pdf}&
%\borderFigure{1.25}{\fullpaperpdirectory/images/testImage4.pdf}\\
\LET{a}{$\partial A_1$} & \LET{b}{$\partial A_2$} & \LET{c}{$\partial A_3$} & \LET{d}{$\partial A_4$}\\
\end{tabular}
%\vspace*{-0.3cm}
\caption{Border test images.}
%\vspace*{-0.5cm}

%
\label{\fullpaperid:fig:testImages}
%\end{wrapfigure}
\end{figure}
%
If $\partial I$ denotes the set of border points of image $I$ (i.e.,
if the image is $N \times M$, its border pixels are those located at
row 0, row $(N-1)$, column 0 and column $(M-1)$), then $I$ is a
binary border image if $\partial I \cap X \ne \emptyset$.
%
\autoref{\fullpaperid:fig:borderTypeCC} illustrates several examples of such
images\footnote{Images are surrounded by a gray-frame in order to
distinguish the boundaries of the border \CCs. Sets and \CCs~appear
in white in this paper.}.

%\begin{wrapfigure}[13]{l}[0.05\width]{0cm}
\begin{figure}[h!]
\centering 
%\fbox{\parbox{2\linewidth}{ {
\framebox[6.6cm]{\parbox{6.6cm}{ {
\footnotesize
\begin{tabbing}
\quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad  \kill
\usrv {BORDERCLASS} ($X$:\usrv{Slice}):\keyw{integer} \{\\
\>  \usrv{type} = 0;\\
\>  \keyw{IF} \usrv{numberOfCC}($X^C$) > 1 \\
\>  \>  \usrv{type} = 8; \\
\>  \keyw{ELSE} \\
\>  \>  \keyw{FOR} \usrv{i} = 1 \keyw{TO} 4 \\
\>  \>  \>  \keyw{IF} $\mid \partial A_i \cap X \mid = \mid \partial A_i \mid$\\
\>  \>  \>  \>  \usrv{type} = \usrv{type} + 2;\\
\>  \>  \>  \keyw{ELSEIF} $\mid \partial A_i \cap X \mid \ne 0$\\
\>  \>  \>  \>  \usrv{type} = \usrv{type} + 1;\\
\>  \keyw{RETURN} (\usrv{type}); \\
\}
\end{tabbing}
}}}
%
%\vspace*{-0.5cm}
%\vspace*{3mm}
%
\caption{Classification function.} \label{\fullpaperid:fig:borderTypeAlgorithm}
%\end{wrapfigure}
%\vspace*{-8mm}
\end{figure}

%
Border \CCs~are detected and processed by defining four test
images, called $\partial A_1$, $\partial A_2$, $\partial A_3$ and
$\partial A_4$.
%
These images are illustrated in Figure \ref{\fullpaperid:fig:testImages}, and they
are composed of a line located at one of the four image borders (up,
right, down or left).

The classification of border images is performed by a function
described in Figure \ref{\fullpaperid:fig:borderTypeAlgorithm}. It consists in
intersecting the border and test images.
%
In the classification function in Figure \ref{\fullpaperid:fig:borderTypeAlgorithm},
the notation $\mid Y \mid$ denotes the cardinal of $Y$, i.e., the
number of pixels of set $Y$. If $X$ touches all the border $\partial
A_i$, the ``type'' variable is incremented by 2; if $X$ touches
partially the border $\partial A_i$, ``type'' is incremented by 1.
This is computed for each border.
%
All types of border images are displayed in
Figure \ref{\fullpaperid:fig:borderTypeCC}. Note that \emph{Type} 3 and \emph{Type}
5 are not possible. Also, note that \emph{Type} 0 (not illustrated
in Figure \ref{\fullpaperid:fig:borderTypeCC}) is a non-border image. We have
arbitrarily defined as \emph{Type} 8 the case in which a border \CC~touches more than one of the border test images $\partial A_i$ and
has an intersection with $\cup_i (\partial A_i \cap X)$, $i\in \{1,
..., 4\}$, that is not a connected set.


\begin{figure}[h!]
\centering
\renewcommand{\baselinestretch}{0.5}% for tabular environment
\small
\begin{tabular}{cccccc}
\borderFigure{1.0}{\fullpaperpdirectory/images/borde07.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/borde06.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/borde08.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/borde09.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/borde10.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/borde04.pdf}\\
&&&&&\\
\LET{a}{Type 1} & \LET{b}{Type 2} & \LET{c}{Type 4} & \LET{d}{Type
6} & \LET{e}{Type 7} & \LET{f}{Type 8}\\
\end{tabular}
%
\caption[Border images classification]{Border images
classification.}
%
%\vspace*{-0.9cm}
\label{\fullpaperid:fig:borderTypeCC}
\end{figure}

%\vspace*{-0.9cm}
\subsection{Interpolation of border images}
\label{\fullpaperid:sec:borderImagesInterpolation}
%\vspace*{-0.2cm}

Border \CCs~detected according to the procedure described in the
last section should be interpolated.
%
The interpolation of border \CCs~is described in the following.
Several cases are distinguished. (Note: the region border type is
used in case~4.) Let $X_1$ and $X_2$ be \CCs~in two different
slices:

\begin{enumerate}
%\vspace{-0.2cm}
\item If $X_1$  and $X_2$ are border \CCs, such that $X_1 \cap
X_2 \ne \emptyset$ then interpolate with $X_1$ and $X_2$ in their
original location (without alignment).
\autoref{\fullpaperid:fig:twoIntersectedBorderImages} illustrates an example of
this situation. Input images are the first and the last one.

\vspace{4mm}
\begin{figure}[h!]
\centering
\begin{tabular}{ccccccc}
\borderFigure{1.0}{\fullpaperpdirectory/images/Border01ToBorder02_000.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border01ToBorder02_025.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border01ToBorder02_050.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border01ToBorder02_062.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border01ToBorder02_075.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border01ToBorder02_087.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border01ToBorder02_100.pdf}\\
\end{tabular}
%
%\vspace{2mm}
\caption{Interpolation between border images with non-empty
intersection.}
%
%\vspace*{-0.6cm}
%\vspace{-6mm}
\label{\fullpaperid:fig:twoIntersectedBorderImages}
\end{figure}

\item If just $X_1$ or $X_2$ is a border \CC~and if $X_1 \cap
X_2 \ne \emptyset$ then interpolate with $X_1$ and $X_2$ in their
original location. In Figure \ref{\fullpaperid:fig:intersectedBorderImages2} is
illustrated an example of this situation.
\vspace{4mm}

\begin{figure}[h!]
\centering
\begin{tabular}{ccccccc}
\borderFigure{1.0}{\fullpaperpdirectory/images/Border03ToBorder04_000.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border03ToBorder04_025.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border03ToBorder04_050.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border03ToBorder04_075.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border03ToBorder04_092.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border03ToBorder04_096.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border03ToBorder04_100.pdf}\\
\end{tabular}
%
%\vspace{2mm}
\caption{Interpolation between a border image and non-border image
with non-empty intersection.}
%
%\vspace*{-0.6cm}
%\vspace{-6mm}
\label{\fullpaperid:fig:intersectedBorderImages2}
\end{figure}

\item If either $X_1$ or $X_2$ is a border \CC~and $X_1 \capº
X_2 = \emptyset$ but $\delta_{\lambda_1}(X_1) \cap X_2 \ne
\emptyset$ or $X_1 \cap \delta_{\lambda_2}(X_2) \ne \emptyset$
(i.e., these \CCs~satisfies a proximity test (see later
Section~\ref{\fullpaperid:sec:matchingInterpolation}) and are considered a
matched pair), then interpolate $X_1$ and $X_2$ normally.
\autoref{\fullpaperid:fig:intersectedBorderImages3} illustrates an example of
this case.
\vspace{4mm}

\begin{figure}[h!]
\centering
\begin{tabular}{ccccccc}
\borderFigure{1.0}{\fullpaperpdirectory/images/Border05ToBorder06_000.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border05ToBorder06_012.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border05ToBorder06_037.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border05ToBorder06_050.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border05ToBorder06_075.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border05ToBorder06_087.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/Border05ToBorder06_100.pdf}\\
\end{tabular}
%
%\vspace{2mm}
\caption{Interpolation between a border image and non border image
with empty intersection.}
%
%\vspace*{-0.6cm}
\label{\fullpaperid:fig:intersectedBorderImages3}
\end{figure}

\item
In this case, either $X_1$ or $X_2$ is the empty set (i.e., it is
non-existent). Let us suppose that $X_2$ is the empty set, so that
$X_1$ vanishes from slide 1 to slide 2. This is dealt
in~\cites{Vidal:VidCreMao2005a,Vidal:VidCreMao2005b,Vidal:VidCreMao2006} with the
so-called ``artificial'' \CCs, so that an interpolation is performed
between $X_1$ and an artificial point or line in slide~2.
\autoref{\fullpaperid:fig:artificialCCs} displays several cases of artificial
\CCs~for different types of border \CCs. (That is, in this case,
the border region classification described in
Section~\ref{\fullpaperid:sec:classificationBorderImages} is employed.) For
example, in Figure \ref{\fullpaperid:fig:artificialCCs}, the Type~2 case uses as
artificial \CC~a point (Figure \ref{\fullpaperid:fig:artificialCCs}(b)), and the
Type~1 case employs a line at the bottom
(Figure \ref{\fullpaperid:fig:artificialCCs}(a)).
\end{enumerate}

%\vspace*{-0.5cm}
\begin{figure}[!ht]
\centering
\begin{tabular}{cc}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde07.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde07art.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde07int.pdf}&
\borderFigure{1.25}{\fullpaperpdirectory/images/borde06.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde06art.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde06int.pdf}\\
\LET{a}{Type 1}&\LET{b}{Type 2}\\ \\
\borderFigure{1.25}{\fullpaperpdirectory/images/borde08.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde08art.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde08int.pdf}&
\borderFigure{1.25}{\fullpaperpdirectory/images/borde09.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde09art.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde09int.pdf}\\
\LET{c}{Type 4}&\LET{d}{Type 6}\\ \\
\borderFigure{1.25}{\fullpaperpdirectory/images/borde10.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde10art.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde10int.pdf}&
\borderFigure{1.25}{\fullpaperpdirectory/images/borde11.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde11art.pdf}
\borderFigure{1.25}{\fullpaperpdirectory/images/borde11int.pdf}\\
\LET{e}{Type 7}&\LET{f}{Type 8}
\end{tabular}
%
%\vspace{2mm}
\caption{Artificial \CCs~to interpolate isolated border \CCs: (a) $X
\cap (\bigcup_{k=1}^4 \partial A_k)$, (b) $X \cap ((\partial A_1
\cap
\partial A_2) \cup (\partial A_2 \cap \partial A_3) \cup (\partial
A_3 \cap \partial A_4) \cup (\partial A_4 \cap \partial A_1))$, (c),
(d) and (e) $\bigcup_{k=1}^4{X \cap \partial A_k, \mbox{ if } X \cap
\partial A_k = \partial A_k}$, (f) $\mathop{Thinning}(A)$. In
each case, the left image is $X_1$, the middle image is the
artificial \CC, and the right image is the interpolated result.}
%
%\vspace*{-0.5cm}
\label{\fullpaperid:fig:artificialCCs}
%
\end{figure}

%\vspace*{-0.6cm}
\section{Interpolation of mosaic images}
\label{\fullpaperid:sec:mosaicImagesInterpolation}
%\vspace*{-0.2cm}

Mosaics are the gray-level images better suited to be treated by a
region-based interpolation technique.
%
Morphological interpolation for mosaic images is a recent subject.
In the literature, the treatment of shapes in region-based
interpolation problems have been frequently involved a conversion to
binary images as strategy to treat shapes.
%
In particular, binary morphological skeletons are used in~\cite{Vidal:Vizireanu2003} to interpolate shapes of regions.
%
On the other hand, \cites{Vidal:Iwanowski2002b,Vidal:Iwanowski2005} describes a
morphological mosaic interpolation based on the distance function
calculation. This technique incorporates affine transformations in
order to align matched regions (distance functions should be applied
to non-empty intersected regions).

The general algorithm of ours region-based interpolation method is
displayed in Figure \ref{\fullpaperid:fig:generalRegionBasedAlgorithm}.
%,~\ref{\fullpaperid:fig:regionBasedAlgorithm2} and~\ref{\fullpaperid:fig:regionBasedAlgorithm3},
%corresponding to its
The algorithm is divided in 3 main parts: (1)~detection and
separation of regions in each slice, (2)~matching and interpolation
between regions, and (3)~final adjustment.
%More detailed description
%at low level pseudo-code can be found in the Appendix.
%
Note that these three steps are not exactly identical to the three
steps of the binary image interpolation outlined in
Section~\ref{\fullpaperid:sec:summary}; the matching and interpolation stages
have been integrated, and the final adjustment step is new (it was
not necessary for the binary image case). The next sections describe
these parts of the algorithm.

%\vspace*{-0.3cm}
\subsection{Region separation}
\label{\fullpaperid:sec:regionSeparation}
%\vspace*{-0.2cm}

In mosaics, a region corresponds to a set of connected pixels with
the same gray-value.
%
In the first step of our algorithm, step (1) in
Figure \ref{\fullpaperid:fig:generalRegionBasedAlgorithm}, regions are extracted and
stored as binary images.
%
The gray-level value for each region is also stored, as well as the
hierarchical level that corresponds to the region in a tree
structure that is built.
%
A simple mosaic and its regions structure is displayed in
Figure \ref{\fullpaperid:fig:separationRegions}. \autoref{\fullpaperid:fig:separationRegions}(a)
is the input mosaic, Figures~\ref{\fullpaperid:fig:separationRegions}(d)
and~\ref{\fullpaperid:fig:separationRegions}(e) are two regions with gray-level
value equal to 27, and Figures~\ref{\fullpaperid:fig:separationRegions}(f)
to~\ref{\fullpaperid:fig:separationRegions}(h) are regions with gray-level values
equal to 193, 130 and 93, respectively. Figures
~\ref{\fullpaperid:fig:separationRegions}(b) and~\ref{\fullpaperid:fig:separationRegions}(c)
illustrate the structure of the mosaic and the hierarchical
region-based tree of the input image~\cite{Vidal:Garrido2002}.

The first level is composed by all the regions which are directly or
indirectly adjacent to the border of the image; the next level
includes regions that belong to the internal structures of the
regions in the first level in such a way that they are directly or
indirectly adjacent to these regions, and so on.

This tree-based information was not necessary in binary images,
because the only structure inside a \CC\ that could exist would be a
hole or grain inside (and not many regions).

\begin{figure}[!t]
\fbox{\parbox{2\linewidth}{ {\scriptsize
\begin{tabbing}
\quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad
\= \quad \kill
\usrv {INTERPOLATOR} ($S_1, S_2$:\usrv{Slice}):\usrv{Slice} \{\\
\>  \mbox{// (1) Detection and separation of regions in each slice}\\
\>  \keyw{For} each slice $S_i$\\
\>  \>  \keyw{Store} region $j$ from slice $S_i$ into vector element
$\mathop{RS}_i^j$\\
\>  \>  Compute and store the hierarchical level of $\mathop{RS}_i^j$\\
\>  \mbox{// (2) Matching and Interpolation (Regions are processed by hierarchical level)} \\
\>  \keyw{For} each level $k$ of the hierarchical region tree\\
\>  \>  \keyw{For} each region $i$ in slice $S_1$\\
\>  \>  \>  \keyw{For} each region $j$ in slice $S_2$\\
\>  \>  \>  \>  \keyw{If} hierarchical levels of $\mathop{RS}_1^i$ and $\mathop{RS}_2^j$ are $k$\\
\>  \>  \>  \>  \>  \mbox{// Only regions with the same gray-level are processed}\\
\>  \>  \>  \>  \>  \keyw{If} graylevel of both $\mathop{RS}_1^i$
and $\mathop{RS}_2^j$ are equal\\
\>  \>  \>  \> \>  \>  \keyw{If} $\mathop{RS}_1^i$ and $\mathop{RS}_2^j$ pass the proximity test\\
\>  \>  \>  \> \>  \>  \>   \>  Establish matching between region
$i$ and region $j$\\
\>  \>  \mbox{// If region i from slice 1 does not match any region in slice 2 or if region j from}\\
\>  \>  \mbox{// slice 2 does not match any region in slice 1, the next level is searched}\\
\>  \>  \keyw{For} each region $i$ in slice $S_1$\\
\>  \>  \>  \keyw{For} each region $j$ in slice $S_2$\\
\>  \>  \>  \>  \keyw{If} hierarchical level of $\mathop{RS}_1^i =
k$ \keyw{and} hierarchical level of $\mathop{RS}_2^j=k+1$\\
\>  \>  \>  \>      \keyw{or} hierarchical level of $\mathop{RS}_1^i = k+1$ \keyw{and} hierarchical level of $\mathop{RS}_2^j=k$\\
%\>  \>  \>  \>  \>  \mbox{// Only regions with the same gray-level are processed}\\
\>  \>  \>  \>  \>  \keyw{If} graylevel of both $\mathop{RS}_1^i$
and $\mathop{RS}_2^j$ are equal\\
\>  \>  \>  \> \>  \>  \keyw{If} $\mathop{RS}_1^i$ and $\mathop{RS}_2^j$ pass the proximity test\\
\>  \>  \>  \> \>  \>  \>   \>  Establish matching between region
$i$ and region $j$\\
\>  \mbox{// If there exists multiple matching, only regions with minimal distance}\\
\>  \mbox{// between them are kept}\\
\>  \keyw{For} each region $i$ in slice $S_1$\\
\>  \>  \keyw{If} multiple matching is detected for region $i$\\
\>  \>  \>  Choose to match region $k$ from slice $S_2$ with minimal MSP-distance from region $i$\\
\>  \keyw{For} each region $j$ in slice $S_2$\\
\>  \>  \keyw{If} multiple matching is detected for region $j$\\
\>  \>  \>  Choose to match region $k$ from slice $S_1$ with minimal MSP-distance from region $j$\\
\>  \mbox{// Interpolation between matched regions is performed computing median sets.}\\
\>  \keyw{For} each region $i$ in slice $S_1$\\
\>  \>  \keyw{For} each region $j$ in slice $S_2$\\
\>  \>  \>  \keyw{If} region $\mathop{RS}_1^i$ match with region $\mathop{RS}_2^j$\\
\>  \>  \>  \>  Compute the interpolated region $S_p$ between $\mathop{RS}_1^i$ and $\mathop{RS}_2^j$ using median set\\
\>  \mbox{// Isolated regions are interpolated with artificial regions (see Figure \ref{\fullpaperid:fig:artificialCCs})}\\
%\>  \mbox{// depend on the location of regions (see Figure \ref{\fullpaperid:fig:artificialCCs})}\\
\>  \keyw{For} each region $i$ in slice $S_1$\\
\>  \>  \keyw{If} region $\mathop{RS}_1^i$ is isolated\\
\>  \>  \>  Choose to match corresponding artificial region for region $\mathop{RS}_1^i$\\
\>  \>  \>  Calculate interpolated region $S_p$ between $\mathop{RS}_1^i$ and its artificial region\\
\>  \keyw{For} each region $j$ in slice $S_2$\\
\>  \>  \keyw{If} region $\mathop{RS}_2^j$ is isolated\\
\>  \>  \>  Choose to match corresponding artificial region for region $\mathop{RS}_2^j$\\
\>  \>  \>  Calculate interpolated region $S_p$ between $\mathop{RS}_2^j$ and its artificial region\\
\>  \mbox{// (3) Final adjustment} \\
\>  Compute overlapped regions $\cup_{i=1,p-1} \cup_{j=i+1,p} (S_i \cap S_j)$ and empty regions $[\cup_{i=1,p}S_i]^C$\\
%\>  Compute empty regions as $[\cup_{i=1,p}S_i]^C$\\
\>  Flood overlapped and empty regions %$\cup_{i=1,p-1} \cup_{j=i+1,p} (S_i \cap S_j) \bigcup [\cup_{i=1,p}S_i]^C$
    with a watershed procedure\\
\}
\end{tabbing}}}}
%
%\vspace*{3mm}
\caption{General region-based interpolation algorithm.}
%\vspace*{-0.4cm}
\label{\fullpaperid:fig:generalRegionBasedAlgorithm}
\end{figure}


\begin{figure}[!ht]
\centering
\begin{tabular}{ccc}
\includegraphics[width=1.5cm]{\fullpaperpdirectory/images/mosaico01.pdf}&
\includegraphics[height=1.5cm]{\fullpaperpdirectory/images/mosaico02.pdf}&
\includegraphics[width=1.5cm]{\fullpaperpdirectory/images/HRBI.pdf}\\
\LET{a}{Input mosaic} & \LET{b}{Structure}&\LET{c}{Region-based tree}
\vspace{4mm}
\end{tabular}
\begin{tabular}{ccccc}
\borderFigure{1.0}{\fullpaperpdirectory/images/mosaico01A1.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/mosaico01A2.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/mosaico01B.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/mosaico01C.pdf}&
\borderFigure{1.0}{\fullpaperpdirectory/images/mosaico01D.pdf}\\
\LET{d}{Region A} & \LET{e}{Region A} & \LET{f}{Region B} & \LET{g}{Region C} & \LET{h}{Region D}
\end{tabular}
%
\caption{A mosaic divided in regions.}
%\vspace*{-0.5cm}
\label{\fullpaperid:fig:separationRegions}
\end{figure}


%\vspace*{-0.3cm}
\subsection{Matching and interpolation}
\label{\fullpaperid:sec:matchingInterpolation}
%\vspace*{-0.2cm}

The objective of the matching step is to establish correspondences
between (a)~each region in slice~1 and (b)~zero or more regions in
slice~2. Such a number can be zero if no correspondence occurs.
Regions to be matched must have an identical gray-level value as a
prerequisite. The matching step corresponds to step~(2) in the
region-based interpolation algorithm
%and it is
shown in Figure \ref{\fullpaperid:fig:generalRegionBasedAlgorithm}.

The criteria used in the matching step are the proximity test and
the minimal distances between their MSP\footnote{A filled \CC,
representing a filled region is reduced to a point using the Minimal
Skeleton by Pruning \cite{Vidal:Soille2003}, i.e., its skeleton is reduced
by pruning until a final point is reached. For a filled
\CC~definition see Section~\ref{\fullpaperid:sec:binaryTechniqueAlgorithm}.}
points. The proximity test consists in the computation of the
\emph{proximity zone}. The proximity zone of $X$ is a dilation of
$X$ with a disk-shaped structuring element of radius $\lambda_X$.
$X$'s radius is computed as $\lambda_X = \min \{\alpha:X \subseteq
\delta_\alpha (MSP_X)\}$, where $\mathop{MSP}_X$ is the MSP of $X$.

If two regions $X$ and $Y$ from different slices match, i.e.,
$\delta_{\lambda_X}(X) \cap Y \ne \emptyset$ or $X \cap
\delta_{\lambda_Y}(Y) \ne \emptyset$, the distance between $MSP_X$
and $MSP_Y$ is stored.
% in a matrix (named $D$ in the algorithm).

Multiple matching can happen, that is, some regions can match with
more than one region of the other slice.
%
%This situation is reflected in the matrix $D$ with more than one
%entry different from $\infty$ in one or more rows and/or columns.
%
Sometimes, this kind of situations produces a merged region.
%
This situation is solved in the following manner: let $X$ be a
region from slice 1 that match with $n$ regions $Y_1, Y_2, ..., Y_n$
from slice 2. We must choose $Y_k$, such that, 
\begin{equation*}
Y_k = \mathop{min}_{1 \le i \le n} \{Y_i,\mathop{MSP\_distance}(X,Y_i)\},
\end{equation*}
where $\mathop{MSP\_distance}$ represent the Euclidean distance
between the MSP points of each input region. The rest of matched
regions are rejected.



These criteria and procedures were already used in the interpolation
method for binary images~\cites{Vidal:VidCreMao2005a,Vidal:VidCreMao2005b,Vidal:VidCreMao2006} but, in the case
of mosaics, we consider also the hierarchical level of the regions.
Particularly, two regions can match if the difference between their
hierarchical level is at most one level.
%
This condition is verified before the proximity test in the matching
step.
%
The hierarchical level is also used to compute the median sets,
i.e., when all the regions at a certain hierarchical level are
matched, the median sets between them are computed. After that,
correspondences between regions at the next level are analyzed and
so on.

%\begin{figure}[!h]
%\ContinuedFloat
%\fbox{ \parbox{0.5\linewidth}{\scriptsize
%\begin{tabbing}
%\quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad
%\= \quad \kill
%\usrv {INTERPOLATOR} ($Current\_S_1$:\usrv{Slice},$Current\_S_2$:\usrv{Slice}):\usrv{Slice} \{\\
%\>  ...\\
%\>  \mbox{// (2) Matching and Interpolation} \\
%\>  \mbox{// *****************************************************}\\
%\>  ...\\
%\>  \mbox{// Interpolation between matched regions is performed.}\\
%\>  \mbox{// It is computed using median set}\\
%\>  \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\
%\>  \>  \keyw{FOR} \usrv{j} := 1 \keyw{TO} $m_k$ \\
%\>  \>  \>  \keyw{IF} $D_{i,j}^k \ne \infty$ \\
%\>  \>  \>  \>  \usrv{P} = \usrv{P} + 1; \\
%\>  \>  \>  \>  $RI_P$ = \usrv{medianSet}($RS1_i^k$,$RS2_j^k$); \\
%\>  ...\\
%\}
%\end{tabbing}}}
%
%\caption{(cont.) Matching and interpolation part of general
%region-based interpolation algorithm (Interpolation part).}
%%\label{\fullpaperid:fig:regionBasedAlgorithm2-3}
%\end{figure}
%
%(NOTA: EN FIG 12 (parte 3), AÑADIDO part EN CAPTION...)
%

Finally, isolated regions
%(as isolated \CCs~in binary images)
are treated. They correspond to regions that do not match and are
therefore interpolated with an artificial region whose shape (a
point or a line) depends on the position of the region (see examples
in Figure \ref{\fullpaperid:fig:artificialCCs}).

%\begin{figure}[!h]
%\ContinuedFloat
%\fbox{ \parbox{0.5\linewidth}{\scriptsize
%\begin{tabbing}
%\quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad
%\= \quad \kill
%\usrv {INTERPOLATOR} ($Current\_S_1$:\usrv{Slice},$Current\_S_2$:\usrv{Slice}):\usrv{Slice} \{\\
%\>  ...\\
%\>  \mbox{// (2) Matching and Interpolation} \\
%\>  \mbox{// *****************************************************}\\
%\>  ...\\
%\>  \mbox{// Isolated regions are interpolated with artificial regions which}\\
%\>  \mbox{// depend on the location of regions (see Table~\ref{\fullpaperid:tab:artificialCCs})}\\
%\>  \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\
%\>  \>  \keyw{IF} ($D_{i,j}^k = \infty, \forall j = 1,m_k$) \\
%\>  \>  \>  \usrv{P} = \usrv{P} + 1; \\
%\>  \>  \>  $RI_P$ = \usrv{medianSet}($RS1_i^k$,\usrv{artificial}($RS1_i^k$)); \\
%\>  \keyw{FOR} \usrv{j} := 1 \keyw{TO} $m_k$ \\
%\>  \>  \keyw{IF} ($D_{i,j}^k = \infty, \forall i = 1,n_k$) \\
%\>  \>  \>  \usrv{P} = \usrv{P} + 1; \\
%\>  \>  \>  $RI_P$ = \usrv{medianSet}($RS2_j^k$,\usrv{artificial}($RS2_j^k$)); \\
%\>  ...\\
%\}
%\end{tabbing}}}
%
%\caption{(cont.) Matching and interpolation part of general
%region-based interpolation algorithm (Treatment of isolated
%regions).}
%\label{\fullpaperid:fig:regionBasedAlgorithm2}
%\end{figure}

%\vspace*{-0.3cm}
\subsection{Final adjustment}
\label{\fullpaperid:sec:finalAdjustment}
%\vspace*{-0.2cm}

%The last part of our method allows to eliminate empty pixels (where
%no regions cover these pixels) and overlapped pixels (where more
%than one region cover these pixels.
%
%Both situation are produced by translations and/or interpolation
%computations of particular regions. %%
%\autoref{\fullpaperid:fig:regionBasedAlgorithm3} illustrate this section of the
%algorithm.
%(NO ESTÁ MUY CLARO)
%
%$(DECIR ALGO DE QUE ESTO NO ES NECESARIO EN EL BINARY CASE ??)
%
%(¿QUÉ TAL PONER UNA IMAGEN MUY SENCILLA EN LA QUE SE VEAN LOS DOS
%TIPOS DE SITUACIONES, PÍXELES SIN PINTAR Y PÍXELES SOLAPADOS ??)
%
%\end{comment}


This stage is necessary for mosaic image interpolation but not for
the binary image case (in fact, this stage was not present in our
previous binary image interpolation technique
\cites{Vidal:VidCreMao2005a,Vidal:VidCreMao2005b,Vidal:VidCreMao2006}).
%
In mosaics, after the previous steps we have a set of interpolated
regions $\{ R_i \}$ that pose two problems: (a)~$\cup_i R_i$ does
not necessarily cover the whole image support (i.e., there are empty
spaces that do not belong to any $R_i$); and~(b) in general,
interpolated regions can overlap (i.e., pixels can belong to more
than one interpolated region).



%During the process described above, the input regions must be
%translated to compute interpolated regions. On the other hand, there
%exists adjacency restriction between regions, i.e., adjacent regions
%in input slices would produce adjacent interpolated regions as
%results. Both condition not always are satisfied  directly by our
%method, producing spaces (empty pixels) that  are no covered  by any
%interpolated regions and spaces (overlapped pixels) where  more than
%one interpolated region use these space.

These problems %must be solved.
are solved at step (3) of the general region-based interpolation
algorithm shown in Figure \ref{\fullpaperid:fig:generalRegionBasedAlgorithm}.
 Pixels that belong to empty spaces or
to overlapped spaces must be assigned to \emph{one} region. This is
performed by using a simple watershed procedure in this last part of
the algorithm. Particularly, the image to be flooded is the
complement of the image constituted by the interior of $\cup_i R_i$
minus the overlapping regions. Note also that appropriate gray-level
values must be used to label the interpolated regions.

%Finally, interpolated mosaic is composed from interpolated regions
%and information about gray-level value of these regions.

%In this section of the technique, empty pixels and overlapped pixels
%are reassigned to regions by flooding using a simple watershed
%procedure.
%
%The algorithm pseudo-code is illustrated in
%Figure \ref{\fullpaperid:fig:floodingAlgorithm}. It receives a set of interpolated
%regions, then iteratively dilate them until there is no more empty
%pixels in the image.
%
%\begin{figure}[h]
%\centering
%
%\fbox{ \parbox{0.98 \linewidth}{\scriptsize
%\begin{tabbing}
%\quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad  \kill
%\usrv {FLOODING} ($R$:\usrv{vectorOfRegions},\usrv{N}:\keyw{Integer}):\usrv{vectorOfRegions} \{ \\
%\>  \mbox{// R stored interpolated regions, N is the number of regions}\\
%\>  \usrv{k} = 1;\\
%\>  \usrv{emptyPixels} = $\mid (\bigcup_{i=1,N} R_i)^C \mid$; \mbox{// Compute the number of empty pixels.} \\
%\>  \keyw{WHILE} \usrv{emptyPixels} $\ne 0$ \{ \\
%\>  \>  $R_k = \delta (R_k)$;\\
%\>  \>  $R_k = R_k \cap (\bigcup_{i=1,N-1}\bigcup_{j=i+1,N}(R_i \cap R_j))^C$;\\
%\>  \>  \usrv{emptyPixels} = $\mid (\bigcup_{i=1,N}R_i)^C\mid$;\\
%\>  \>  \usrv{k} = \usrv{k}+1;\\
%\>  \>  \keyw{IF} \usrv{k} > \usrv{N} \\
%\>  \>  \>  \usrv{k} = 1;\\
%\>  \} \\
%\>  \keyw{RETURN}(\usrv{R});\\
%\}
%\end{tabbing}
%}}
%%
%\caption{Flooding algorithm.} \label{\fullpaperid:fig:floodingAlgorithm}
%\end{figure}

%\vspace*{-0.3cm}
\section{Experimental results}
\label{\fullpaperid:sec:experimentalResults}
%\vspace*{-0.2cm}

This section discusses some experimental results of our method. We
have used synthetic images
%which provides the possibility of emphasize some aspect of functioning of method.
that permit to emphasize some relevant aspects of our method.

\autoref{\fullpaperid:fig:example1} illustrates a simple case with a human-like
mosaic. Input slices are the first and the last one. The body and
the two background regions of the images are treated as border
%\CCs.
regions. Note that the body is Type 8, the big background is Type 6
and the small background is Type 2.
%
The face, eyes and mouth regions are treated as \CCs~with inclusion
relationships using the hierarchical region-based tree.

\begin{figure}[!h]
\centering
\begin{tabular}{cccccc}
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_000.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_012.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_025.pdf}&
%\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_037.pdf}\\
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_050.pdf}&
%\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_062.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_075.pdf}&
%\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_087.pdf}&
\includegraphics[width=1.25cm]{\fullpaperpdirectory/images/gris001Togris002_100.pdf}\\
%\LET{a}{} & \LET{b}{} & \LET{c}{} & \LET{d}{} &  \LET{e}{} & \LET{f}{} \\%& \LET{g}{} & \LET{h}{} & \LET{i}{}\\
\end{tabular}
%
\caption{Example of mosaic interpolation.}
%\vspace*{-0.4cm}
\label{\fullpaperid:fig:example1}
\end{figure}

The example in Figure \ref{\fullpaperid:fig:example2} shows a situation where there
exist an isolated region, e.g., the dark region  situated at the
bottom right of the image, which vanishes through from the first to
the last input image. A border region (the white one at the upper
left) that moves to the upper-left corner of the image is also
displayed in this sequence.

\begin{figure}[!h]
\centering
\begin{tabular}{cccc}
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_100.pdf}&
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_087.pdf}&
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_062.pdf}&
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_050.pdf}\\ \\
%\LET{a}{} & \LET{b}{} & \LET{c}{} & \LET{d}{}\\
%\end{tabular}
%\begin{tabular}{ccccc}
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_037.pdf}&
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_025.pdf}&
%\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_075.pdf}&
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_012.pdf}&
\includegraphics[width=2.0cm]{\fullpaperpdirectory/images/gris025Togris026_000.pdf}
%\LET{e}{} & \LET{f}{} & \LET{g}{} & \LET{h}{} \\%& \LET{i}{}\\
\end{tabular}
%
\caption{Example of mosaic interpolation.}
%\vspace*{-0.4cm}
\label{\fullpaperid:fig:example2}
\end{figure}


%\section{Commentaries and Conclusions}
%\vspace*{-0.6cm}
\section{Conclusions}
\label{\fullpaperid:sec:commentariesAndConclusions} %\vspace*{-0.2cm}

In this paper, we have presented a region-based interpolation method
for mosaic images. It is based on a previous interpolation technique
of ours for binary images. As is shown in the paper, even though the
basic principles in both techniques are similar, there exist some
substantial differences between both cases. For example, the
matching and interpolation operations are performed level by level
of the hierarchical region-based tree that represents the region
structure of the image. The overall interpolation is achieved when
all levels have been processed.

Another important difference is that it is necessary a new final
adjustment step for mosaic interpolation. After regions have been
interpolated, there are generally pixels in the interpolated slice
that do not belong to any region. In addition, there can be
overlapping between interpolated regions.
%
The last step of our interpolation algorithm for mosaics solve these
problems.


%On the other hand, it is necessary to consider the concept of
%adjacency because in mosaics the domain of each image is covered by
%regions (in binary images \CCs just cover a portion of the image,
%the rest is background). This is the function of the last step of
%our general interpolation algorithm.

%\vspace*{-0.4cm}
\section*{Acknowledgments}
%\vspace*{-0.2cm}
This work has been supported in part by the
University of Concepción (Chile), by the MECESUP programme of the
Education Ministry of Chile, by the Artificial Intelligence
Laboratory of School of Computer Science of ``Universidad
Politécnica de Madrid'', and by the collaboration programme of Banco
Santander-Central Hispano and Universidad Politécnica de Madrid for
doctoral studies.

%\bibliographystyle{plain}
%\begin{bibsection}
%	\bibliography{vidal}
%\end{bibsection}

\begin{bibsection}
	\begin{biblist}

\bib{Vidal:Beucher1994}{techreport}{
      author={Beucher, Serge},
       title={Interpolations d'ensembles, de partitions et de fonctions},
 institution={Centre de Morphologie Math\'{e}matique},
        date={1994},
      number={N-18/94/MM},
}

\bib{Vidal:Beucher1998}{incollection}{
      author={Beucher, Serge},
       title={Interpolation of sets, of partitions and functions},
        date={1998},
   booktitle={Mathematical morphology ant its applications to image and signal
  processing},
      editor={Heijmans, Henk~J. A. M.},
      editor={Roerdink, Jos B. T.~M.},
   publisher={Kluwer Academics Publishers},
       pages={119\ndash 126},
}

\bib{Vidal:Bors2002}{article}{
      author={Bors, Adrian~G.},
      author={Kechagias, Lefteris},
      author={Pitas, Ioannis},
       title={Binary morphological shape-based interpolation applied to
  \mbox{3D} tooth reconstruction},
        date={2002},
     journal={IEEE Transaction on Medical Imaging},
      volume={21},
      number={2},
}

\bib{Vidal:Chatzis2000}{article}{
      author={Chatzis, Vassilios},
      author={Pitas, Ioannis},
       title={Interpolation of 3{D} binary images based on morphological
  skeletonizations},
        date={2000},
     journal={IEEE Transaction on Medical Imaging},
      volume={19},
      number={7},
}

\bib{Vidal:DougLotu:03}{book}{
      author={Dougherty, Edward~R.},
      author={Lotufo, Roberto~A.},
       title={Hands-on morphological image processing},
   publisher={SPIE Press},
     address={Bellingham, WA},
        date={2003},
        ISBN={0-8194-4720-X},
  url={http://bookstore.spie.org/index.cfm?fuseaction=DetailVolume\&productid=%
501104},
}

\bib{Vidal:Garrido2002}{thesis}{
      author={Garrido, Luis},
       title={Hierarchical region-based processing of images and video
  sequences: Application to filtering, segmentation and information retrieval},
        type={Ph.D. Thesis},
     address={Department of Signal Theory and Communications - Universitat
  Politècnica de Catalunya},
        date={2002},
}

\bib{Vidal:Guo1995}{article}{
      author={Guo, Jun-Feng},
      author={Cai, Yuan-Long},
      author={Wang, Yu-Ping},
       title={Morphology-based interpolation for 3{D} medical image
  reconstruction},
        date={1995},
     journal={Computarized Medical Imaging and Graphics},
      volume={19},
      number={3},
       pages={267\ndash 279},
}

\bib{Vidal:Iwanowski2000b}{incollection}{
      author={Iwanowski, Marcin},
      author={Serra, Jean},
       title={The morphological - affine object deformation},
        date={2000},
   booktitle={International {S}ymposium on {M}athematical {M}orphology
  ({ISMM}), palo alto, \mbox{CA}},
      editor={John~Goutsias, Luc~Vincent},
      editor={Bloomberg, Dan~S.},
   publisher={Kluwer Academics Publishers},
       pages={445},
}

\bib{Vidal:Iwanowski2000a}{thesis}{
      author={Iwanowski, Marcin},
       title={Application of mathematical morphology to image interpolation},
        type={Ph.D. Thesis},
     address={School of Mines of Paris - Warsaw University of Technology},
        date={2000},
}

\bib{Vidal:Iwanowski2001}{incollection}{
      author={Iwanowski, Marcin},
       title={Generalized morphological mosaic interpolation and its
  application to computer-aided animations},
        date={2001},
   booktitle={Computer analysis of images and patterns},
      editor={Verlag, W.Skarbek;~Springer},
      volume={LNCS series (Lecture Notes on Computer Science) no.2124},
       pages={494\ndash 501},
        note={Proceedings of 9th International Conference CAIP 2001, Sept. 5-7,
  2001, Warsaw, Poland},
}

\bib{Vidal:Iwanowski2002b}{inproceedings}{
      author={Iwanowski, Marcin},
       title={Image morphing based on morphological interpolation combined with
  linear filtering},
organization={University of West Bohemia},
        date={2002},
   booktitle={International journal of \mbox{WSCG}},
      volume={1},
       pages={233\ndash 239},
        note={Proceedings of the 10th International Conference in Central
  Europe on Computer Graphics, Visualization and Computer Vision, Pilzen, Czech
  Republic},
}

\bib{Vidal:Iwanowski2005}{proceedings}{
      author={Iwanowski, Marcin},
      editor={Society, IEEE Signal~Processing},
       title={Universal morphological interpolator},
        date={2005},
      volume={II},
        ISBN={0-7803-9135-7},
        note={Proceedings of International Conference on Image Processing
  {ICIP’05}, Genova, Italy},
}

\bib{Vidal:Lee2000}{article}{
      author={Lee, Tong-Yee},
      author={Wang, Wen-Hsiu},
       title={Morphology-based three-dimensional interpolation},
        date={2000},
     journal={IEEE Transactions on Medical Imaging},
      volume={19},
      number={7},
       pages={711\ndash 721},
}

\bib{Vidal:Meyer1994}{techreport}{
      author={Meyer, Fernand},
       title={Interpolations},
 institution={Centre de Morphologie Math\'{e}matique},
        date={1994},
      number={N-16/94/MM},
}

\bib{Vidal:Meyer1996}{incollection}{
      author={Meyer, Fernand},
       title={A morphological interpolation method for mosaic images},
        date={1996},
   booktitle={Mathematical morphology and its applications to image and signal
  processing},
   publisher={Kluwer Academics Publishers},
}

\bib{Vidal:Serra82}{book}{
      author={Serra, Jean},
       title={Mathematical morphology. {V}olume {I}},
   publisher={London: Academic Press},
        date={1982},
}

\bib{Vidal:Serra88}{book}{
      editor={Serra, Jean},
       title={Mathematical morphology. {V}olume {II}: {T}heoretical advances},
   publisher={London: Academic Press},
        date={1988},
}

\bib{Vidal:Serra1994}{techreport}{
      author={Serra, Jean},
       title={Interpolations et distances of {H}ausdorff},
 institution={Centre de Morphologie Math\'{e}matique},
        date={1994},
      number={N-15/94/MM},
}

\bib{Vidal:Soille1991}{article}{
      author={Soille, Pierre},
       title={Spatial distributions from contour lines: an efficient
  methodology based on distance transformations},
        date={1991},
     journal={Journal of Visual Communication and Image Representation},
      volume={2},
      number={2},
       pages={138\ndash 150},
}

\bib{Vidal:Soille2003}{book}{
      author={Soille, Pierre},
       title={Morphological image analysis: Principles and applications},
     edition={2},
   publisher={Springer-Verlag},
        date={2003},
        ISBN={3540429883},
}

\bib{Vidal:VidCreMao2005b}{incollection}{
      author={Vidal, Javier},
      author={Crespo, Jose},
      author={Maojo, V\'{i}ctor},
       title={Inclusion relationships and homotopy issues in shape
  interpolation for binary images},
        date={2005},
   booktitle={Lecture {N}otes in {C}omputer {S}cience, \mbox{LNCS 3429}},
      editor={Andres, E.},
      editor={Damiand, G.},
      editor={Lienhardt, P.},
      volume={LNCS3429},
   publisher={Springer-Verlag},
     address={Berlin Heidelberg},
       pages={206\ndash 215},
}

\bib{Vidal:VidCreMao2005a}{incollection}{
      author={Vidal, Javier},
      author={Crespo, Jose},
      author={Maojo, V\'{i}ctor},
       title={Recursive interpolation technique for binary images based on
  morphological median sets},
        date={2005},
   booktitle={Computational {I}maging and {V}ision {J}ournal},
      editor={Ronse, C.},
      editor={Najman, L.},
      editor={Decenciere, E.},
      volume={30},
   publisher={Springer-Verlag},
     address={Dordrecht},
       pages={53\ndash 62},
}

\bib{Vidal:VidCreMao2006}{article}{
      author={Vidal, Javier},
      author={Crespo, Jose},
      author={Maojo, V\'{i}ctor},
       title={A shape interpolation technique based on inclusion relationships
  and median sets},
        date={2007},
     journal={Accepted in ``Image and Vision Computing Journal''},
}

\bib{Vidal:Vizireanu2003}{inproceedings}{
      author={D. N. Vizireanu},
      author={Halunga, Simona},
      author={Fratu, Octavian},
       title={A grayscale image interpolation method using new morphological
  skeleton},
        date={2003},
   booktitle={Proceeding of 6th {I}nternational {C}onference on
  {T}elecommunication in {M}odern {S}atellite, {C}able and {B}roadcasting
  {S}ervices},
       pages={519\ndash 521},
}

	\end{biblist}
\end{bibsection}
%\renewcommand{\baselinestretch}{1}
