%% 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 | %% +-------------+ %\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\\ 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} \Index{Mathematical morphology}, \Index{Image processing}, \Index{Image analysis}, \Index{Interpolation}, \Index{Mosaic}, \Index{Median set}. \end{Keywords} %% +----------+ %% | SECTIONS | %% +----------+ \vspace*{-0.5cm} \section{Introduction} \label{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{Serra82,Serra88,Soille2003,DougLotu:03} techniques have been used to design several interpolation methods~\cites{Beucher1998,Bors2002,Chatzis2000,Guo1995,Iwanowski2000a,Iwanowski2000b,Lee2000,Meyer1994,Meyer1996,Serra1994,Iwanowski2001,Iwanowski2005,Iwanowski2002b,Vizireanu2003,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~\cite{Iwanowski2001,Iwanowski2005,Iwanowski2002b,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{VidCreMao2005a,VidCreMao2005b,VidCreMao2006}. % These basic principles are two: an inclusion property and the utilization of the median set as interpolator~\cite{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{sec:summary} presents a brief summary of the previously presented interpolation technique. Section~\ref{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{sec:mosaicImagesInterpolation}. Some experimental results are provided in Section~\ref{sec:experimentalResults}. Conclusions are commented in Section~\ref{sec:commentariesAndConclusions}. %---------------------------------------- \vspace*{-0.4cm} \section{A Brief Summary of an Interpolation Technique for Binary Images} \label{sec:summary} \vspace*{-0.2cm} The technique reported in this paper is based on a previous work of ours applied to binary images ~\cites{VidCreMao2005a,VidCreMao2005b,VidCreMao2006}. It will be briefly described in this section. \vspace*{-0.4cm} \subsection{Inclusion Property} \label{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{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{fig:inclusionProperty} illustrates inclusion property: Fig.\ref{fig:inclusionProperty}(b) is equal to Fig.\ref{fig:inclusionProperty}(e) minus Fig.\ref{fig:inclusionProperty}(h). \begin{figure}[t!] \centering \begin{tabular}{ccc} \includegraphics[width=1.25cm]{./images/i1g.pdf}& \includegraphics[width=1.25cm]{./Images/i1h.pdf}& \includegraphics[width=1.25cm]{./Images/i1i.pdf}\\ \LET{a}{Input set 1} & \LET{b}{Interpolated set} & \LET{c}{Input set 2} \\ \includegraphics[width=1.25cm]{./Images/i1a.pdf}& \includegraphics[width=1.25cm]{./Images/i1b.pdf}& \includegraphics[width=1.25cm]{./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]{./Images/i1d.pdf}& \includegraphics[width=1.25cm]{./Images/i1e.pdf}& \includegraphics[width=1.25cm]{./Images/i1f.pdf}\\ \LET{g}{Hole~1} & \LET{h}{Interpolated hole} & \LET{i}{Hole~2} \\ \end{tabular} % \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{fig:inclusionProperty} \end{figure} \vspace*{-0.3cm} \subsection{Binary Image Interpolation Algorithm} \label{sec:binaryTechniqueAlgorithm} \vspace*{-0.1cm} In the algorithm for interpolating binary images~\cites{VidCreMao2005a,VidCreMao2005b,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{VidCreMao2005a}. \vspace*{-0.4cm} %\section{The Problem of Border Regions in Mosaic Images} \section{Treatment of Border Regions in Mosaic Images} \label{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 \cite{VidCreMao2005a,VidCreMao2005b,VidCreMao2006}). \vspace*{-0.3cm} \subsection{Classification of Border Images} \label{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$). % \begin{wrapfigure}[7]{r}[0.05\width]{0cm} \centering \begin{tabular}{cccc} \borderFigure{1.25}{./images/testImage1.pdf}& \borderFigure{1.25}{./images/testImage2.pdf}& \borderFigure{1.25}{./images/testImage3.pdf}& \borderFigure{1.25}{./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} \caption{Border test images.} %\vspace*{-0.5cm} % \label{fig:testImages} \end{wrapfigure} % 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{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} \centering \fbox{\parbox{2\linewidth}{ {\scriptsize \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} % \caption{Classification function.} \label{fig:borderTypeAlgorithm} \end{wrapfigure} % 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 Fig.\ref{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 Fig.\ref{fig:borderTypeAlgorithm}. It consists in intersecting the border and test images. % In the classification function in Fig.\ref{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 Fig.\ref{fig:borderTypeCC}. Note that \emph{Type} 3 and \emph{Type} 5 are not possible. Also, note that \emph{Type} 0 (not illustrated in Fig.\ref{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 \begin{tabular}{cccccc} \borderFigure{1.0}{./images/borde07.pdf}& \borderFigure{1.0}{./images/borde06.pdf}& \borderFigure{1.0}{./images/borde08.pdf}& \borderFigure{1.0}{./images/borde09.pdf}& \borderFigure{1.0}{./images/borde10.pdf}& \borderFigure{1.0}{./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{fig:borderTypeCC} \end{figure} \vspace*{-0.9cm} \subsection{Interpolation of Border Images} \label{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{fig:twoIntersectedBorderImages} illustrates an example of this situation. Input images are the first and the last one. \begin{figure}[h!] \centering \begin{tabular}{ccccccc} \borderFigure{1.0}{./images/Border01ToBorder02_000.pdf}& \borderFigure{1.0}{./images/Border01ToBorder02_025.pdf}& \borderFigure{1.0}{./images/Border01ToBorder02_050.pdf}& \borderFigure{1.0}{./images/Border01ToBorder02_062.pdf}& \borderFigure{1.0}{./images/Border01ToBorder02_075.pdf}& \borderFigure{1.0}{./images/Border01ToBorder02_087.pdf}& \borderFigure{1.0}{./images/Border01ToBorder02_100.pdf}\\ \end{tabular} % \caption{Interpolation between border images with non-empty intersection} % \vspace*{-0.6cm} \label{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 Fig.\ref{fig:intersectedBorderImages2} is illustrated an example of this situation. \begin{figure}[h!] \centering \begin{tabular}{ccccccc} \borderFigure{1.0}{./images/Border03ToBorder04_000.pdf}& \borderFigure{1.0}{./images/Border03ToBorder04_025.pdf}& \borderFigure{1.0}{./images/Border03ToBorder04_050.pdf}& \borderFigure{1.0}{./images/Border03ToBorder04_075.pdf}& \borderFigure{1.0}{./images/Border03ToBorder04_092.pdf}& \borderFigure{1.0}{./images/Border03ToBorder04_096.pdf}& \borderFigure{1.0}{./images/Border03ToBorder04_100.pdf}\\ \end{tabular} % \caption{Interpolation between a border image and non-border image with non-empty intersection} % \vspace*{-0.6cm} \label{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{sec:matchingInterpolation}--- and are considered a matched pair), then interpolate $X_1$ and $X_2$ normally. \autoref{fig:intersectedBorderImages3} illustrates an example of this case. \begin{figure}[h!] \centering \begin{tabular}{ccccccc} \borderFigure{1.0}{./images/Border05ToBorder06_000.pdf}& \borderFigure{1.0}{./images/Border05ToBorder06_012.pdf}& \borderFigure{1.0}{./images/Border05ToBorder06_037.pdf}& \borderFigure{1.0}{./images/Border05ToBorder06_050.pdf}& \borderFigure{1.0}{./images/Border05ToBorder06_075.pdf}& \borderFigure{1.0}{./images/Border05ToBorder06_087.pdf}& \borderFigure{1.0}{./images/Border05ToBorder06_100.pdf}\\ \end{tabular} % \caption{Interpolation between a border image and non border image with empty intersection} % \vspace*{-0.6cm} \label{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{VidCreMao2005a,VidCreMao2005b,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{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{sec:classificationBorderImages} is employed.) For example, in Fig.\ref{fig:artificialCCs}, the Type~2 case uses as artificial \CC~ a point (Fig.\ref{fig:artificialCCs}(b)), and the Type~1 case employs a line at the bottom (Fig.\ref{fig:artificialCCs}(a)). \end{enumerate} %\vspace*{-0.5cm} \begin{figure}[!ht] \centering \begin{tabular}{cc} \borderFigure{1.25}{./images/borde07.pdf} \borderFigure{1.25}{./images/borde07art.pdf} \borderFigure{1.25}{./images/borde07int.pdf}& \borderFigure{1.25}{./images/borde06.pdf} \borderFigure{1.25}{./images/borde06art.pdf} \borderFigure{1.25}{./images/borde06int.pdf}\\ \LET{a}{Type 1}&\LET{b}{Type 2}\\ \borderFigure{1.25}{./images/borde08.pdf} \borderFigure{1.25}{./images/borde08art.pdf} \borderFigure{1.25}{./images/borde08int.pdf}& \borderFigure{1.25}{./images/borde09.pdf} \borderFigure{1.25}{./images/borde09art.pdf} \borderFigure{1.25}{./images/borde09int.pdf}\\ \LET{c}{Type 4}&\LET{d}{Type 6}\\ \borderFigure{1.25}{./images/borde10.pdf} \borderFigure{1.25}{./images/borde10art.pdf} \borderFigure{1.25}{./images/borde10int.pdf}& \borderFigure{1.25}{./images/borde11.pdf} \borderFigure{1.25}{./images/borde11art.pdf} \borderFigure{1.25}{./images/borde11int.pdf}\\ \LET{e}{Type 7}&\LET{f}{Type 8} \end{tabular} % \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{fig:artificialCCs} % \end{figure} \vspace*{-0.6cm} \section{Interpolation of Mosaic Images} \label{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{Vizireanu2003} to interpolate shapes of regions. % On the other hand, \cite{Iwanowski2002b,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 Fig.\ref{fig:generalRegionBasedAlgorithm}. %,~\ref{fig:regionBasedAlgorithm2} and~\ref{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{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{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 Fig.\ref{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 Fig.\ref{fig:separationRegions}. \autoref{fig:separationRegions}(a) is the input mosaic, Figs.~\ref{fig:separationRegions}(d) and~\ref{fig:separationRegions}(e) are two regions with gray-level value equal to 27, and Figs.~\ref{fig:separationRegions}(f) to~\ref{fig:separationRegions}(h) are regions with gray-level values equal to 193, 130 and 93, respectively. Figures ~\ref{fig:separationRegions}(b) and ~\ref{fig:separationRegions}(c) illustrate the structure of the mosaic and the hierarchical region-based tree of the input image~\cite{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 Fig.\ref{fig:artificialCCs})}\\ %\> \mbox{// depend on the location of regions (see Fig.\ref{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}}}} % \caption{General region-based interpolation algorithm.} \vspace*{-0.4cm}\label{fig:generalRegionBasedAlgorithm} \end{figure} \begin{comment} \begin{figure}[!h] {\scriptsize \begin{tabbing} \quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad \kill \usrv {INTERPOLATOR} ($Current\_S_1$:\usrv{Slice},$Current\_S_2$:\usrv{Slice}):\usrv{Slice} \{\\ \> \mbox{// (1) Detection and separation of regions in each slice}\\ \> $RS1$ = \usrv{extractRegions}($Current\_S_1$); \mbox{// Regions in slice 1 are stored in a vector} \\ \> $RS2$ = \usrv{extractRegions}($Current\_S_2$); \mbox{// Regions in slice 2 are stored in a vector} \\ \> ...\\ \} \end{tabbing}} % \vspace*{-0.3cm} \caption{General region-based interpolation algorithm (Separation of regions).} \label{fig:regionBasedAlgorithm1} \end{figure} \end{comment} \begin{figure}[!ht] \centering \begin{tabular}{ccc} \includegraphics[width=1.5cm]{./images/mosaico01.pdf}& \includegraphics[height=1.5cm]{./images/mosaico02.pdf}& \includegraphics[width=1.5cm]{./images/HRBI.pdf}\\ \LET{a}{Input mosaic} & \LET{b}{Structure}&\LET{c}{Region-based tree}\\ \end{tabular} \begin{tabular}{ccccc} \borderFigure{1.0}{./images/mosaico01A1.pdf}& \borderFigure{1.0}{./images/mosaico01A2.pdf}& \borderFigure{1.0}{./images/mosaico01B.pdf}& \borderFigure{1.0}{./images/mosaico01C.pdf}& \borderFigure{1.0}{./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{fig:separationRegions} \end{figure} \vspace*{-0.3cm} \subsection{Matching and Interpolation} \label{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 Fig.\ref{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{Soille2003}, i.e., its skeleton is reduced by pruning until a final point is reached. For a filled \CC~definition see Section~\ref{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). \begin{comment} \begin{figure}[!h] {\scriptsize \begin{tabbing} \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{// Matching and interpolated region are processed by hierarchical level}\\ \> \usrv{P}=0; \mbox{// Interpolated regions (counter)}\\ \> \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\ \> \> \keyw{FOR} \usrv{j} := 1 \keyw{TO} $n_k$ \\ \> \> \> \mbox{// Only regions with the same gray-level and hierarchical level k are processed}\\ \> \> \> \keyw{IF} \usrv{graylevel}($RS1_i^k$) = \usrv{graylevel}($RS2_j^k$)\\ \> \> \> \> \mbox{// Proximity test computation:}\\ \> \> \> \> \mbox{// if both regions pass the test the distance between them is stored}\\ \> \> \> \> \keyw{IF} ($\delta_{\lambda_1}(RS1_i^k) \cap RS2_j^k \ne \emptyset$) \keyw{OR} ($RS1_i^k \cap \delta_{\lambda_2}(RS2_j^k) \ne \emptyset$)\\ \> \> \> \> \> $D_{i,j}^k$ = \usrv{distance}($MSP_{RS1_i^k},MSP_{RS2_j^k}$); \\ \> \mbox{// If region i from slice 1 does not match any region in slice 2 or}\\ \> \mbox{// if region j from slice 2 does not match any region in slice 1,}\\ \> \mbox{// the next level is searched}\\ \> \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\ \> \> \keyw{IF} $D_{i,j}^k = \infty, \forall j=1,n_k$ \\ \> \> \> \keyw{FOR} \usrv{j} := 1 \keyw{TO} $n_k$ \\ \> \> \> \> \keyw{IF} \usrv{graylevel}($RS1_i^k$) = \usrv{graylevel}($RS1_j^{k+1}$)\\ \> \> \> \> \> \keyw{IF} ($\delta_{\lambda_1}(RS1_i)\cap RS2_j^{k+1} \ne \emptyset$) \keyw{OR} ($RS1_i \cap \delta_{\lambda_2}(RS2_j^{k+1}) \ne \emptyset$)\\ \> \> \> \> \> \> $D_{i,j}^k$ = \usrv{distance}($MSP_{RS1_i^k},MSP_{RS2_j^{k+1}}$); \\ \> \> \keyw{IF} $D_{j,i} = \infty, \forall j = 1,n_k$ \\ \> \> \> \keyw{FOR} \usrv{j} := 1 \keyw{TO} $n_k$ \\ \> \> \> \> \keyw{IF} \usrv{graylevel}($RS1_j^{k+1}$) = \usrv{graylevel}($RS1_i$)\\ \> \> \> \> \> \keyw{IF} ($\delta_{\lambda_1}(RS1_j^{k+1})\cap RS2_i^k \ne \emptyset$) \keyw{OR} ($RS1_j^{k+1} \cap \delta_{\lambda_2}(RS2_i^k) \ne \emptyset$)\\ \> \> \> \> \> \> $D_{i,j}^k$ = \usrv{distance}($MSP_{RS1_j^{k+1}},MSP_{RS2_i^k}$); \\ \> ...\\ \} \end{tabbing}} %} % \vspace*{-0.4cm} \caption{General region-based interpolation algorithm (Proximity test computation part).} \label{fig:regionBasedAlgorithm2} \end{figure} %(NOTA: EN FIG 12 (parte 1), AÑADIDO part EN CAPTION...) % \end{comment} 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, $Y_k = \mathop{min}_{1 \le i \le n} \{Y_i,\mathop{MSP\_distance}(X,Y_i)\}$, where $\mathop{MSP\_distance}$ represent the Euclidean distance between the MSP points of each input region. The rest of matched regions are rejected. \begin{comment} To solve this situation we choose the minimal distance in each row (or column) with multiplicities; the rest of entries in a row (or column) would be converted to infinity. \begin{figure}[!ht] \ContinuedFloat {\scriptsize \begin{tabbing} \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{// If there exists multiple matching, just the regions with minimal distance}\\ \> \mbox{// between them are kept}\\ \> \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\ \> \> \keyw{IF} ($D_{i,j} \ne \infty, \forall j = 1,n_k$) > 1 \\ \> \> \> $D_{i,j}^k=\min \{D_{i,l}^k, l = 1,n_k\}$; \\ \> \> \keyw{IF} ($D_{j,i} \ne \infty, \forall j = 1,n_k$) > 1 \\ \> \> \> $D_{j,i}^k=\min \{D_{j,l}^k, l = 1,n_k\}$; \\ \> \mbox{// Interpolation between matched regions is performed computing median sets.}\\ %\> \mbox{// It is computed using median set}\\ \> \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\ \> \> \keyw{FOR} \usrv{j} := 1 \keyw{TO} $n_k$ \\ \> \> \> \keyw{IF} $D_{i,j}^k \ne \infty$ \\ \> \> \> \> \usrv{P} = \usrv{P} + 1; \\ \> \> \> \> $RI_P$ = \usrv{medianSet}($RS1_i^k$,$RS2_j^k$); \\ \> \mbox{// Isolated regions are interpolated with artificial regions that}\\ \> \mbox{// depend on the location of regions (see Fig.\ref{fig:artificialCCs})}\\ \> \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\ \> \> \keyw{IF} ($D_{i,j}^k = \infty, \forall j = 1,n_k$) \\ \> \> \> \usrv{P} = \usrv{P} + 1; \\ \> \> \> $RI_P$ = \usrv{medianSet}($RS1_i^k$,\usrv{artificial}($RS1_i^k$)); \\ \> \> \keyw{IF} ($D_{j,i}^k = \infty, \forall j = 1,n_k$) \\ \> \> \> \usrv{P} = \usrv{P} + 1; \\ \> \> \> $RI_P$ = \usrv{medianSet}($RS2_j^k$,\usrv{artificial}($RS2_j^k$)); \\ \> ...\\ \} \end{tabbing}} % \vspace*{-0.4cm} \caption{(Cont.) General region-based interpolation algorithm (Multiple matching, interpolation, and isolated region treatment part).} \end{figure} % %(NOTA: EN FIG12 (parte 2), AÑADIDO part EN CAPTION...) \end{comment} These criteria and procedures were already used in the interpolation method for binary images ~\cite{VidCreMao2005a,VidCreMao2005b,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{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 Fig.\ref{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{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{fig:regionBasedAlgorithm2} %\end{figure} \vspace*{-0.3cm} \subsection{Final Adjustment} \label{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{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{VidCreMao2005a,VidCreMao2005b,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 Fig.\ref{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. \begin{comment} \begin{figure}[!h] %\fbox{ \parbox{0.5\linewidth} {\scriptsize \begin{tabbing} \quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad \kill \usrv {INTERPOLATOR} ($Current\_S_1$:\usrv{Slice},$Current\_S_2$:\usrv{Slice}):\usrv{Slice} \{\\ \> ...\\ \> \mbox{// (3) Final adjustment} \\ %\> \mbox{// *****************************************************}\\ \> \mbox{// Overlapped interpolated regions are eliminated from interpolated regions}\\ \> \usrv{Z} = $\bigcup_{i=1,P-1}\bigcup_{j=i+1,P}(RI_i \cap RI_j)$\\ \> \keyw{FOR} \usrv{k} := 1 \keyw{TO} \usrv{P} \\ \> \> $RI_k$=$RI_k \setminus$ \usrv{Z};\\ \> \mbox{// Empty pixels of $RI_k$ are flooded by watershed procedure}\\ \> \usrv{M} = $\varepsilon_1 (\bigcup_{i=1, P} RI_k)$ \mbox{// Image to be flooded}; \\ \> \usrv{FLOODING}(\usrv{M}$^C$);\\ \> ... \\ \> \mbox{// Final mosaic image is composed}\\ \> \usrv{S} = $\emptyset$;\\ \> \keyw{FOR} \usrv{k} := 1 \keyw{TO} \usrv{P} \\ \> \> \usrv{S} = \usrv{S} $\cup ~((RI_k \cup RW_k) \cdot$\usrv{GL}$_k$);\\ \> \mbox{// \usrv{GL}$_k$ denotes the gray-level value of interpolated region k} \\ \> \keyw{RETURN}(\usrv{S}); \\ \} \end{tabbing}}%} % \vspace*{-0.4cm} \caption{General region-based interpolation algorithm (Adjustment part).} \label{fig:regionBasedAlgorithm3} \end{figure} \end{comment} %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 %Fig.\ref{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{fig:floodingAlgorithm} %\end{figure} \vspace*{-0.3cm} \section{Experimental Results} \label{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{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]{./images/gris001Togris002_000.pdf}& \includegraphics[width=1.25cm]{./images/gris001Togris002_012.pdf}& \includegraphics[width=1.25cm]{./images/gris001Togris002_025.pdf}& %\includegraphics[width=1.25cm]{./images/gris001Togris002_037.pdf}\\ \includegraphics[width=1.25cm]{./images/gris001Togris002_050.pdf}& %\includegraphics[width=1.25cm]{./images/gris001Togris002_062.pdf}& \includegraphics[width=1.25cm]{./images/gris001Togris002_075.pdf}& %\includegraphics[width=1.25cm]{./images/gris001Togris002_087.pdf}& \includegraphics[width=1.25cm]{./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{fig:example1} \end{figure} The example in Fig.\ref{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]{./images/gris025Togris026_100.pdf}& \includegraphics[width=2.0cm]{./images/gris025Togris026_087.pdf}& \includegraphics[width=2.0cm]{./images/gris025Togris026_062.pdf}& \includegraphics[width=2.0cm]{./images/gris025Togris026_050.pdf}\\ %\LET{a}{} & \LET{b}{} & \LET{c}{} & \LET{d}{}\\ %\end{tabular} %\begin{tabular}{ccccc} \includegraphics[width=2.0cm]{./images/gris025Togris026_037.pdf}& \includegraphics[width=2.0cm]{./images/gris025Togris026_025.pdf}& %\includegraphics[width=2.0cm]{./images/gris025Togris026_075.pdf}& \includegraphics[width=2.0cm]{./images/gris025Togris026_012.pdf}& \includegraphics[width=2.0cm]{./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{fig:example2} \end{figure} %\section{Commentaries and Conclusions} %\vspace*{-0.6cm} \section{Conclusions} \label{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 represent 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} \bibliography{vidal} \begin{comment} \section*{Appendix} \begin{figure}[!h] {\scriptsize \begin{tabbing} \quad \= \quad \= \quad \= \quad \= \quad \= \quad \= \quad \kill \usrv {INTERPOLATOR} ($Current\_S_1$:\usrv{Slice},$Current\_S_2$:\usrv{Slice}):\usrv{Slice} \{\\ \> \mbox{// (1) Detection and separation of regions in each slice}\\ \> $RS1$ = \usrv{extractRegions}($Current\_S_1$); \mbox{// Regions in slice 1 are stored in a vector} \\ \> $RS2$ = \usrv{extractRegions}($Current\_S_2$); \mbox{// Regions in slice 2 are stored in a vector} \\ \> \mbox{// (2) Matching and Interpolation} \\ \> \mbox{// Matching and interpolated region are processed by hierarchical level}\\ \> \usrv{P}=0; \mbox{// Interpolated regions (counter)}\\ \> \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\ \> \> \keyw{FOR} \usrv{j} := 1 \keyw{TO} $n_k$ \\ \> \> \> \mbox{// Only regions with the same gray-level and hierarchical level k are processed}\\ \> \> \> \keyw{IF} \usrv{graylevel}($RS1_i^k$) = \usrv{graylevel}($RS2_j^k$)\\ \> \> \> \> \mbox{// Proximity test computation:}\\ \> \> \> \> \mbox{// if both regions pass the test the distance between them is stored}\\ \> \> \> \> \keyw{IF} ($\delta_{\lambda_1}(RS1_i^k) \cap RS2_j^k \ne \emptyset$) \keyw{OR} ($RS1_i^k \cap \delta_{\lambda_2}(RS2_j^k) \ne \emptyset$)\\ \> \> \> \> \> $D_{i,j}^k$ = \usrv{distance}($MSP_{RS1_i^k},MSP_{RS2_j^k}$); \\ \> \mbox{// If region i from slice 1 does not match any region in slice 2 or}\\ \> \mbox{// if region j from slice 2 does not match any region in slice 1,}\\ \> \mbox{// the next level is searched}\\ \> \keyw{FOR} \usrv{i} := 1 \keyw{TO} $n_k$ \\ \> \> \keyw{IF} $D_{i,j}^k = \infty, \forall j=1,n_k$ \\ \> \> \> \keyw{FOR} \usrv{j} := 1 \keyw{TO} $n_k$ \\ \> \> \> \> \keyw{IF} \usrv{graylevel}($RS1_i^k$) = \usrv{graylevel}($RS1_j^{k+1}$)\\ \> \> \> \> \> \keyw{IF} ($\delta_{\lambda_1}(RS1_i)\cap RS2_j^{k+1} \ne \emptyset$) \keyw{OR} ($RS1_i \cap \delta_{\lambda_2}(RS2_j^{k+1}) \ne \emptyset$)\\ \> \> \> \> \> \> $D_{i,j}^k$ = \usrv{distance}($MSP_{RS1_i^k},MSP_{RS2_j^{k+1}}$); \\ \> \> \keyw{IF} $D_{j,i} = \infty, \forall j = 1,n_k$ \\ \> \> \> \keyw{FOR} \usrv{j} := 1 \keyw{TO} $n_k$ \\ \> \> \> \> \keyw{IF} \usrv{graylevel}($RS1_j^{k+1}$) = \usrv{graylevel}($RS1_i$)\\ \> \> \> \> \> \keyw{IF} ($\delta_{\lambda_1}(RS1_j^{k+1})\cap RS2_i^k \ne \emptyset$) \keyw{OR} ($RS1_j^{k+1} \cap \delta_{\lambda_2}(RS2_i^k) \ne \emptyset$)\\ \> \> \> \> \> \> $D_{i,j}^k$ = \usrv{distance}($MSP_{RS1_j^{k+1}},MSP_{RS2_i^k}$); \\ \> \mbox{// (3) Final adjustment} \\ %\> \mbox{// *****************************************************}\\ \> \mbox{// Overlapped interpolated regions are eliminated from interpolated regions}\\ \> \usrv{Z} = $\bigcup_{i=1,P-1}\bigcup_{j=i+1,P}(RI_i \cap RI_j)$\\ \> \keyw{FOR} \usrv{k} := 1 \keyw{TO} \usrv{P} \\ \> \> $RI_k$=$RI_k \setminus$ \usrv{Z};\\ \> \mbox{// Empty pixels of $RI_k$ are flooded by watershed procedure}\\ \> \usrv{M} = $\varepsilon_1 (\bigcup_{i=1, P} RI_k)$ \mbox{// Image to be flooded}; \\ \> \usrv{FLOODING}(\usrv{M}$^C$);\\ \> ... \\ \> \mbox{// Final mosaic image is composed}\\ \> \usrv{S} = $\emptyset$;\\ \> \keyw{FOR} \usrv{k} := 1 \keyw{TO} \usrv{P} \\ \> \> \usrv{S} = \usrv{S} $\cup ~((RI_k \cup RW_k) \cdot$\usrv{GL}$_k$);\\ \> \mbox{// \usrv{GL}$_k$ denotes the gray-level value of interpolated region k} \\ \> \keyw{RETURN}(\usrv{S}); \\ \} \end{tabbing}}%} % \caption{General region-based interpolation algorithm.} \label{fig:regionBasedAlgorithm} \end{figure} % % BIBLIOGRAPHY % for details, see ftp://ftp.ams.org/pub/tex/amsrefs/amsrdoc.pdf % \begin{bibsection} \begin{biblist}[\resetbiblist{9}] \bib{Banon:Banon:2000:NeInDi}{article}{ author={Banon, Gerald J. F.}, title={New insight on digital topology}, booktitle={Mathematical Morphology and its Applications to Image and Signal Processing}, address={Boston}, publisher={Kluwer Academic Publishers}, book={ editor={Goutsias, John}, editor={Vincent, Luc}, editor={Bloomberg, Dan S.}, publisher={Kluwer Academic Publishers}, address={Boston}, date={2000}, }, conference={ title={International Symposium on Mathematical Morphology, 5}, date={2000-06-{26--28}}, address={Palo Alto, USA}, }, pages={138--148} } \bib{Banon:BanonBarr:1998:BaMoM}{report}{ author={Banon, Gerald J. F.}, author={Barrera, Junior}, date={1998}, title={Bases da morfologia matemática para a análise de imagens binárias}, organization={INPE}, address={São José dos Campos}, edition={2}, note={Available from: <\url{http://bibdigital.sid.inpe.br/rep/dpi.inpe.br/banon/1998/06.30.17.56}>. Access in: 2003-04-17. rep: dpi.inpe.br/banon/1998/06.30.17.56} } \bib{Banon:Heijmans:1994:MoImOp}{book}{ author={Heijmans, Henk J. A. M.}, date={1994}, title={Morphological image operators}, address={Boston}, publisher={Academic} } \bib{Banon:Serra:1982:ImAnMa}{book}{ author={Serra, Jean}, date={1982}, title={Image analysis and mathematical morphology}, address={London}, publisher={Academic} } \bib{Banon:RosenfeldPfal:1968:DiFuDi}{article}{ author={Rosenfeld, Azriel}, author={Pfaltz, John L.}, date={1968}, title={Digital functions on digital pictures}, journal={Pattern Recognition}, volume={1}, number={1}, pages={33--61} } \end{biblist} \end{bibsection} \end{comment}