%% 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}