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