summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/sciposter/sciposterexample/sciposter-example.tex
blob: 93b7c4169687610553685b434b5bafcdf086648e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
\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}