\documentclass{sciposter} \usepackage{epsfig} \usepackage{amsmath} \usepackage{amssymb} \usepackage{multicol} %\usepackage{fancybullets} \newtheorem{Def}{Definition} %\definecolor{BoxCol}{rgb}{0.9,0.9,0.9} % uncomment for grey background to \section boxes % for use with default option boxedsections %\definecolor{BoxCol}{rgb}{0.9,0.9,1} % uncomment for light blue background to \section boxes % for use with default option boxedsections %\definecolor{SectionCol}{rgb}{0,0,0.5} % uncomment for dark blue \section text \title{Generalized Pattern Spectra Sensitive to Spatial Information} % Note: only give author names, not institute \author{Michael H. F. Wilkinson} % insert correct institute name \institute{Institute for Mathematics and Computing Science,\\ University of Groningen\\} \email{michael@cs.rug.nl} % shows author email address below institute %\date is unused by the current \maketitle % The following commands can be used to alter the default logo settings %\leftlogo[0.9]{logoWenI}{ % defines logo to left of title (with scale factor) %\rightlogo[0.52]{RuGlogo} % same but on right % NOTE: This will require presence of files logoWenI.eps and RuGlogo.eps, % or other supported format in the current directory %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Begin of Document \begin{document} %define conference poster is presented at (appears as footer) \conference{{\bf ICPR 2002}, 16th International Conference on Pattern Recognition, 11-15 August 2002, Qu\'ebec City, Canada} %\LEFTSIDEfootlogo % Uncomment to put footer logo on left side, and % conference name on right side of footer % Some examples of caption control (remove % to check result) %\renewcommand{\algorithmname}{Algoritme} % for Dutch %\renewcommand{\mastercapstartstyle}[1]{\textit{\textbf{#1}}} %\renewcommand{\algcapstartstyle}[1]{\textsc{\textbf{#1}}} %\renewcommand{\algcapbodystyle}{\bfseries} %\renewcommand{\thealgorithm}{\Roman{algorithm}} \maketitle %%% Begin of Multicols-Enviroment \begin{multicols}{3} %%% Abstract \begin{abstract} Morphological pattern spectra computed from granulometries are frequently used to classify the size classes of details in textures and images. An extension of this technique, which retains information on the spatial distribution of the details in each size class is developed. Algorithms for computation of these spatial pattern spectra for a large number of granulometries on binary images are presented. \end{abstract} %%% Introduction \section{Introduction} \PARstart{G}{ranulometries} are ordered sets of morphological openings or closings, each of which removes image details below a certain size. These can be used for texture analysis through the use of \emph{pattern spectra}, which show how the number of foreground pixels in the image changes as a function of the size parameter \cite{maragos89:_patter}. A drawback of the classical definition of pattern spectra is that spatial information is not included in a pattern spectrum as shown below. In this paper, \emph{spatial pattern spectra} are developed which retain information on the distribution of these details at different scales. \newcommand{\imsize}{0.45\columnwidth} \begin{figure} \begin{center} \begin{tabular}{c c} {\resizebox{\imsize}{!}{\includegraphics{blocks1}}} & {\resizebox{\imsize}{!}{\includegraphics{blocks2}}}\\ (a) & (b) \\ {\resizebox{\imsize}{!}{\includegraphics{blocks3}}} & {\resizebox{\imsize}{!}{\includegraphics{blocks1a}}}\\ (c) & (d) \\ \end{tabular} \end{center} \caption{ Parts (a) through (c) show three images consisting of squares of different sizes; (d) shows the pattern spectra, denoting the number of foreground pixels removed by openings by reconstruction by $\lambda \times \lambda$ squares. No granulometry is capable of separating the patterns, because the only differences between the images lie in the distributions of the connected components. }\label{fig:blocks} \end{figure} \section{Theory} Let binary images $X$ and $Y$ be defined as a subset of the image domain ${\mathbf M}\subset {\mathbb Z}^n$ or ${\mathbb R}^n$ (usually $n=2$). \begin{Def} A binary granulometry is a set of operators $\{\alpha_r\}$ with $r$ from some ordered set $\Lambda$ (usually $\Lambda \subset {\mathbb R}$ or ${\mathbb Z}$), with the following three properties \begin{align} \alpha_r(X) & \subset X \label{eq:antiext} \\ X \subset Y & \Rightarrow \alpha_r(X) \subset \alpha_r(Y) \label{eq:increasing} \\ \alpha_r(\alpha_s(X)) & = \alpha_{\max(r,s)}(X) \label{eq:idempot}, \end{align} for all $r,s \in \Lambda$. \end{Def} \begin{Def} The pattern spectrum $s_{\alpha}(X)$ obtained by applying granulometry $\{\alpha_r\}$ to a binary image $X$ is defined as \begin{equation} (s_{\alpha}(X))(u) = - \frac{\partial A(\alpha_r(X))}{\partial r}\bigg{\vert}_{r=u} \end{equation} in which $A(X)$ is a function denoting the Lebesgue measure in ${\mathbb R}^n$. \end{Def} In the case of discrete images, and with $r \in \Lambda \subset {\mathbb Z}$, this differentiation reduces to \begin{align} (s_{\alpha}(X))(r) & = \#(\alpha_{r}(X) \setminus \alpha_{r^+}(X)) \\ & = \#(\alpha_{r}(X)) - \#(\alpha_{r^+}(X)), \end{align} with $r^+ = \min\{ r' \in \Lambda \vert r' > r \}$, and $\#(X)$ the numnber of elements of $X$. The opening transform \cite{Nacken:thesis} $\Omega_X$ of a binary image $X$ for a granulometry ${\alpha_r}$ is \begin{equation} \Omega_X(x) = \max\{ r \in \Lambda \vert x \in \alpha_r(X) \} \end{equation} The pattern spectrum of a binary image $X$ using granulometry $\{\alpha_r\}$ is the histogram of $\Omega_X$ obtained with the same size distribution \cite{Nacken:thesis}, disregarding the bin for grey level 0. \begin{figure} \begin{center} {\resizebox{\imsize}{!}{\includegraphics{blocks3}}} {\resizebox{\imsize}{!}{\includegraphics{blocks3rec}}} \end{center} \caption{ \label{fig:opentransf} Opening transform with $\{\alpha_r\}$ as in Fig. \ref{fig:blocks}: (left) original image; (right) opening transform (contrast stretched for clarity). } \end{figure} \section{Spatial pattern spectra} Pattern spectra only retain the amount of detail present at scale $r$. This can be amended by computing some parameterization of the spatial distribution in an image $\alpha_r(X) \setminus \alpha_{r+}(X)$ as a function of $r$. \begin{Def} Let ${M}(X)$ be some parameterization of the spatial distribution of detail in the image $X$. The spatial pattern spectrum ${S}_{{M},\alpha}$ is then defined as \begin{equation} ({S}_{{M},\alpha}(X))(r) = {M}(\alpha_r(X) \setminus \alpha_{r+}(X)). \end{equation} \end{Def} An obvious parameterization of the spatial distribution is through the use of moments. Focusing on the case of 2-D binary images, the moment $m_{ij}$ of order $ij$ of an image $X$ is given by \begin{equation} m_{ij}(X) = \sum_{(x,y) \in \mathbf X} x^i y^j. \end{equation} The spatial moment spectrum $S_{m_{ij},\alpha}$ of order $ij$ is \begin{equation} (S_{m_{ij},\alpha}(X))(r) = m_{i,j}(\alpha_r(X) \setminus \alpha_{r^+}(X)). \end{equation} For $i=0$ and $j=0$ we obtain the standard pattern spectrum. For each $r$, $(S_{m_{ij},\alpha}(X))(r)$ is just the moment of an image, therefore, derived parameters such as coordinates of the centre of mass, (co-)variances, skewness and kurtosis of the distribution of details at each scale can be computed easily. We can then define pattern mean spectra, pattern (co-)variance spectra, pattern kurtosis spectra, etc. The pattern mean-$x$ and variance-$x$ spectra ($S_{\bar x,\alpha}$ and $S_{\sigma(x),\alpha}$) are defined as: \begin{align} S_{\bar x,\alpha} & = \frac{S_{m_{10},\alpha}} {S_{m_{00},\alpha}} \\ \intertext{and} S_{\sigma(x),\alpha} & = \sqrt{\frac{S_{m_{20},\alpha}} {S_{m_{00},\alpha}} - S_{\bar x, \alpha}}. \end{align} These two are shown in Figures \ref{fig:tauspect} and \ref{fig:binspect}. Note that these definitions hold only where $(S_{m_{00},\alpha}(f))(r) \neq 0$. For all other values of $r$ they will be defined as zero. Further post-processing can be done to compute central moments and moment invariant from pattern moment spectra \cite{Flusser:Suk:93,Hu:62}. \section{An Algorithm} Nacken \cite{Nacken:thesis} derived an algorithm for computation of pattern spectra for granulometries based on openings by discs of increasing radius for various metrics, using the opening transform. After the opening transform has been computed, it is straightforward to compute the pattern spectrum: \begin{itemize} \item Set all elements of array {\tt S} to zero \item For all $x \in X$ increment {\tt S}[$\Omega_X(x)$] by one. \end{itemize} To compute the pattern \emph{moment} spectrum, the only thing that needs to be changed is the way {\tt S}[$\Omega_X(x)$] is incremented. As shown in Algorithm \ref{alg:spect}. \begin{algorithm} \begin{itemize} \item Set all elements of array {\tt S} to zero \item For all $(x,y) \in X$ increment {\tt S}[$\Omega_X(x,y)$] by $x^iy^j$. \end{itemize} \caption{ Algorithm for computation of pattern moment spectrum of order $ij$. \label{alg:spect}} \end{algorithm} This algorithm can readily be adapted to other granulometries, simply by computing the appropriate opening transform. \begin{figure} \begin{center} \begin{tabular}{c c} {\resizebox{\imsize}{!}{\includegraphics{blocks3op}}} & {\resizebox{\imsize}{!}{\includegraphics{blocksopen3a}}}\\ (a) & (b)\\ {\resizebox{\imsize}{!}{\includegraphics{blocksopen3vx}}}& {\resizebox{\imsize}{!}{\includegraphics{blocksopen3vy}}}\\ (c) & (d) \\ \end{tabular} \end{center} \caption{ \label{fig:tauspect} The opening transform using city-block metric: (a) opening transform of Fig. 1(c); (b) pattern spectrum; (c) pattern variance-$x$; (d) variance-$y$ spectra.} \end{figure} \renewcommand{\imsize}{0.3\columnwidth} \begin{figure} \begin{center} {\resizebox{\imsize}{!}{\includegraphics{blocks1mx}}} {\resizebox{\imsize}{!}{\includegraphics{blocks2mx}}} {\resizebox{\imsize}{!}{\includegraphics{blocks3mx}}}\\ {\resizebox{\imsize}{!}{\includegraphics{blocks1vx}}} {\resizebox{\imsize}{!}{\includegraphics{blocks1vx}}} {\resizebox{\imsize}{!}{\includegraphics{blocks3vx}}} \end{center} \caption{ \label{fig:binspect} Pattern mean-$x$ (top) and variance-$x$ (bottom) spectra: the three collumns show spectra for Fig. 1(a), (b) and (c) from left to right respectively. Unlike the standard pattern spectra, these spatial pattern spectra can distinguish the three images.} \end{figure} \section{Discussion} Spatial pattern spectra form a useful supplement to ordinary pattern spectra, because of their ability to retain spatial information. Pattern moment spectra, in particular, are easily computed concurrently with computation of the standard pattern spectrum. Post-processing of these pattern moment spectra can be done to yield a number of easily interpreted spectra, such as pattern mean, variance, skew, and kurtosis spectra, which have reduced covariance compared to the ``raw'' pattern moment spectra. Invariance to rotation, translation or scale change can also be achieved by post-processing \cite{Flusser:Suk:93,Hu:62}. In the future grey scale versions of these spatial pattern spectra will be developed. I expect that the efficient grey level algorithms for area and attribute pattern spectra \cite{Meijster:Wilkinson:PAMI} can be adapted to spatial pattern spectra as well. %%% References %% Note: use of BibTeX als works!! \bibliographystyle{plain} \begin{thebibliography}{1} \bibitem{Flusser:Suk:93} J.~Flusser and T.~Suk. \newblock Pattern recognition by affine moment invariants. \newblock {\em Pattern Recognition}, 26:167--174, 1993. \bibitem{Hu:62} M.~K. Hu. \newblock Visual pattern recognition by moment invariants. \newblock {\em IRE Transactions on Information Theory}, IT-8:179--187, 1962. \bibitem{maragos89:_patter} P.~Maragos. \newblock Pattern spectrum and multiscale shape representation. \newblock {\em IEEE Trans. Patt. Anal. Mach. Intell.}, 11:701--715, 1989. \bibitem{Meijster:Wilkinson:PAMI} A.~Meijster and M.~H.~F. Wilkinson. \newblock A comparison of algorithms for connected set openings and closings. \newblock {\em IEEE Trans. Patt. Anal. Mach. Intell.}, 24(4):484--494, 2002. \bibitem{Nacken:thesis} P.~F.~M. Nacken. \newblock {\em Image Analysis Methods Based on Hierarchies of Graphs and Multi-Scale Mathematical Morphology}. \newblock PhD thesis, University of Amsterdam, Amsterdam, The Netherlands, 1994. \end{thebibliography} \end{multicols} \end{document}