\chapter{Overview on related work}
\thispagestyle{empty}

The aim is to build a system for automatic recognition of particle categories. Furthermore, we are interested in a general approach enabling us to work 
with several kinds of corpuscles which are found in microscopic analysis. In this way, it is easy to add new classes 
to the already considered set and, no new customized reprogramming is required.

Generally, input images of a such system have resolution of nearly 1024x1024 pixels, while the objects to which we are interested on have
square bounding box with side between 30 and 200 pixels. The average side is around 60 pixels, then, the system has to handle objects with low
resolution. Its output is the number of detected particles in each category.

The automated analysis proceeds in two parts: \emph{detection} and \emph{classification}, an outline is shown in \figref{outlinerecognition}. \\

\begin{figure}[tbp]
\centering
\includegraphics[width=1\textwidth]{./figure/outlinerecognition.eps}
\caption{Outline of recognition system. Detector finds interesting points in the input image and gives back to the classifier a certain number of patches. For each patch, the classifier establishes the class to which the object in foreground belongs.}
\label{figure:outlinerecognition}
\end{figure}

\begin{figure}[tbp]
\centering
\includegraphics[width=1\textwidth]{./figure/toyClass.eps}
\caption{Outline of classifier: the system extracts from the input patch a set of features. In the training period, the system learns how to divide the feature space. In the test phase, the system assigns a class to the input image looking at the region where the test feature falls.}
\label{figure:toyClass}
\end{figure}

In the detection stage the system will select those parts 
of the image which are likely to contain a particle of interest, for example a pollen. 
This process is akin to visual attention in humans: most of the computation 
is devoted to the most promising areas of the image. \\
The second stage, that is classification, consists of taking image portions which contain a 
visual event associable to a particle of interest, and attributing such event either to one out of a number of known species 
or, to an ``unknown object'' grab-bag category.

In urinalysis detection is not a problem, because in the pictures of stream (see next section for a detailed description) all particles have
to be analyzed. Once that overlap among cells is avoided, all objects in the image will be classified. Moreover because of the tipical low
concentration of particles in the fluid, particles are quite well distributed on the original image. Detection for urinalysis is not a
great task. For this reason, our urine database is a collection of patches with particles already well centered; whereas in pollen recognition, detection is still crucial, because the input images of the system are pictures of sticky tape.\\
A given section of tape has accumulated airborne 
particles for many hours. Such an image contains hundreds of particles like: pollen grains, dust, insect parts, etc. 
 The detection process should quickly flag the location of those particles that have at 
least a small chance of being pollen particles. At this stage the number of false rejects, i.e. pollen particles that are not selected, must be 
extremely low because some species can have low counts and we have to take into account also classifier mistakes. 

Classification of both urine particle patches and pollen patches has to establish if the particle is of interest, in which case the class will be
also identified, otherwise, it has to be discarded.\\
 This is a visual \emph{pattern recognition} problem, whose solution is conceptually simple. Given a signal $s$ belonging to a class $k$,
 $k=1,\cdots,K$, the main stages of classification are:
 
 \begin{enumerate}
 \item
 a number of features are extracted from the original signal to form the \emph{feature vector} $x \in \Bbb{R}^D$, that is the image
 transformed into a \emph{pattern}.
 \item 
 a decision function must be determined:
 
 \begin{eqnarray}
  r: \Bbb{R}^D \rightarrow {1,\cdots,K} \nonumber \\
 x \mapsto r(x)
  \end{eqnarray}
 
In many cases, a discriminant function $g(x,k)$ is used:

\begin{equation}
 r: x \mapsto \max_{k\in{1,\cdots,K}} g(x,k) \nonumber \\
 \end{equation}

 This can be regarded as a \emph{trained pattern classifier}, an outline of a classification system is shown in \figref{toyClass}.
 \end{enumerate}

It is well-known, that in the pattern recognition the 
 crucial step is designing informative features: if our features do capture the peculiarities of the appearance of our objects, 
 then, almost any classifier will perform a competent job (Duda and Hart, \cite{libro:Duda}). 

The task of classification even if conceptually simple, is practically a hard challenge. The classifier has to handle images with very low
resolution and often poor contrast.\\
In addition, pollen identification is difficult because \cite{libro:pollini}:
\begin{itemize}
\item there is a large number of look-alike categories
\item each genus of plant has many species (strictly speaking, we are classifying among genera) 
\item high winds may carry unusual kinds of pollen
\item pollen shape and texture can be corrupted by previous impacts
\item pollen shape depends on its orientation on slide; most frequently are seen in the equatorial position, in which they all appear as ovoid
\item ``apparently trees do not read literature and insist upon producing pollen grains with the same number of sides as some of other
pollen kinds'' \cite{libro:pollini}
\end{itemize}

Urine particle classification is difficult because:
\begin{itemize}
\item some cells are semi-transparent, i.e. casts and mucus
\item almost all categories have high variability in shape, texture and size; for example, there is no defined shape and size for clumps,
crystals can be square, rectangular or hexagonal, white cells can have a nucleus or a uniform texture
\item there is a smooth transition between particles belonging to different categories and even human experts do not agree in the 
classification of some casts or blood cells; for example, a ``big'' red blood cell is completely not distinguishable from a
``small'' white blood cell. 
\end{itemize}

To summarize, the system for automatic visual recognition of particles is composed by a detector and a classifier. The detector is simply
achieved in urinalysis, because all objects in foreground are objects of interest while in pollen recognition the detector has to deal with a
lot of non-pollen particles. The detector must have an extremely low missed-detection rate. The classification of patches passed by the detector,
is similar in both cases. In both situations in fact, the classifier handles images with poor resolution and contrast, and there is a strong
variability \emph{between} classes, but sometimes just a little variability \emph{within} some categories.\\

In the next sections, we will present approaches developed by other research groups in the field of visual recognition of particles or, more
generally, visual recognition of small objects in images with low contrast and resolution.\\
We will start describing IRIS urine analysis system that is somewhat our reference point for the urine project, 
then, we will see another approach due
to Dahmen et al. \cite{paper:Dahmen}; for this last method, we had enough details to make a program based on that research and so 
we can make a direct comparison between this technique and our method. 
Finally, we will focus on the detection problem and we will present the work of Burl et al.
 \cite{paper:Burl} about the identification of volcanoes in Venus surface, and we conclude introducing a technique 
 for pollen recognition \cite{progetto:Germania} and another technique for its identification, \cite{paper:pollenid}. \\



\section{IRIS urine analysis system} \label{sec:IRIS}

Thanks to the courtesy of IRIS, we will refer to \cite{depliant:IRIS} and to many discussions with scientists from IRIS to describe their
system. However, we have available only few information about the machine they are selling and we will be able to show only an outline of
their technique.

The \emph{iQ200 Automated Urinalysis System} is a bench-top analyzer able to perform chemical and microscopic analysis. The former one is
focused on the determination of color, gravity and composition of urine. The latter one is used to analyze the sediment, this is useful in
the diagnosis of renal and urinary tract diseases. Each kind of analysis is performed by two different but connected modules. The goal of the
module for particle recognition is to overcome the limitations of manual microscopy: lack of standardization and precision, risk of biohazard, slow processing
and high costs because it requires highly trained technologists. This analyzer is able to classify and quantify 12 particle categories (the
same ones of our urine database) based on a visual recognition system. 

In \figref{depliantIRIS}, you can see an outline of this module. They take from a given specimen 2$\mu L$ of centrifugated urine, they make a
very thin flow through a channel and then, they take 24 pictures per second with a CCD digital camera coupled with a microscope. In this way,
they get around 500 images with resolution 1024x1280 and 0.68 $\mu m/pix$. Given a frame, they are able to detect patches centered on
particles by morphological operations or simply by the application of a threshold. Note that they mechanically avoid the overlap among
particles by regulating the thickness of the flow. Then, they extract from each patch features that take into
account: the image size, the contrast of particle in foreground with respect to the background mean, the shape of the cell and its texture. 
Given these features from each patch, they train a neural network to make a decision in test. They claim that on our database their system
has a very good performance with an error rate\footnote{The error rate is the ratio between the number of not correctly classified test images
and the total number of tested images; its value allows to assess the performance of a classifier.} of nearly 5\%. In the every day use of
their system with the data of their customers, they state the classifier has an error rate of about 10\%. A specimen is processed in nearly 
1 minute and their system allows a continuous load with a maximum of 55 samples.\\
They claim that the hard tasks for this system are:
\begin{itemize}
\item to handle low contrast particles because they perform masking operations to determine some features like shape and size; 
for this reason, the most not correctly classified classes are Mucus and Casts
\item to handle unknown particles
\end{itemize}
This last point requires a special comment. In urine, there are corpuscules of unknown origin which have never been studied and which are not
of interest in the actual analysis. All these particles should be collected in an artifact class which collects also images out of focus or
not well segmented. However, they state that this class fills all the feature space and makes classification quite
difficult. For this reason, they have chosen the ``abstention'' rule: when the outcome of the system has a low confidence they discard the image and
put it on the artifact class. In this way, they show to the user images with high confidence and reliability for the twelve categories of
interest with possibility to check mistakes (the patches are stored in the memory of two computers positioned under the bench). There is
still the problem that the artifact class captures also a lot of particles belonging to other categories. In our database, we have not 
available patches belonging to the artifact class.

We observe that a segmentation-free approach could solve the problem of misclassification among low contrast categories and boost the
performance of the system. To take into account features based on shape, interest points can be extracted from a given patch. Our method is
based on the first principle and achieves a very low error rate in these categories, is much simpler, is more easily updated with new
classes even if it has a slightly higher global error rate.

\begin{figure}[htbp]
\centering
\includegraphics[width=1\textwidth]{./figure/BrochureIRIS.eps}
\caption{Outline of IRIS system for visual recognition of particles in urine (courtesy of IRIS), see par. \ref{sec:IRIS}.}
\label{figure:depliantIRIS}
\end{figure}

\newpage

\section{Fourier Mellin Transform} \label{sec:TFM}

The approach formulated by Dahmen et al. \cite{paper:Dahmen} is general and segmentation free like the system we are describing in this thesis. Their idea to extract features that are invariant with respect to shift, rotation and scale is powerful because it allows to obtain the same measurement from cells that are found in different positions, orientations and scales. \\
They aim to classify three different kinds of red blood cells (namely,
\emph{stomatocyte, echinocyte, discocyte}) in a database of grayscale images with resolution 128x128 pixels. Given an image, they extract 
Fourier Mellin based features that are invariant with respect to 2D rotation, scale and translation. Then, they model the distribution of the
observed training data using Gaussian mixture densities. Using these models in a Bayesian framework they are able to perform the test and to
achieve an error rate of about 15\%.

Let be $f[x,y]\in\Bbb{R}^{N\times N}$ a 2D discrete image, its discrete Fourier Transform is defined as

\begin{equation} \label{eq:TFM1}
F(u,v) = \frac{1}{N} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} f[j,k] e^{- \frac{2 \pi i (uj + vk)}{N}}
\end{equation}

with $i = \sqrt{-1}$ and $u,v=0,1,...,N-1$. It can be easily shown that the amplitude spectrum $A$ of $F(u,v)$ is invariant with respect to
translation, inverse invariant with respect to scaling and variant with respect to rotation. By transforming the rectangular coordinates
$(u,v)$ of $A(u,v)$ to polar coordinates $(r,\theta)$ and by using logarithmic scale for the radial axis, image scales and rotations become
shifts in the log-polar representation $\hat{A}$ of $A$. If you compute the amplitude spectrum $B$ of the Fourier Transform of $\hat{A}$, you
can extract features which are invariant with respect to rotation, scale and translation. Moreover, $\hat{A}$ is real valued, thus $B$ is
symmetric and you can consider the values that fall in window of size for example 25x12 pixels (the origin will fall in the middle of 
a longer side of this window). 
They reduce the dimensionality of the space to $d$ using a linear discriminant analysis (we suppose they apply and we applied
in our implementation Fisher's discriminants, \cite{libro:Bishop} \cite{paper:fld}). \\
For example, in our implementation of their system using our urine database we sampled the images to a common resolution of 90x90 pixels\footnote{Note that when an image has a
resolution smaller than 90x90 pixels we add a frame with values equal to the estimated background mean.}.
So, reshaping the image in a column vector we decrease the feature space dimension from 8100 to 300 thanks to the symmetry of Fourier Mellin
transform and to the windowing operation, then we achieve a further reduction projecting the data along directions given by Fisher 
linear discriminants and thus, we work in a final 11 dimensional feature space.\\
In \figref{EsempioTFM}, we show the Fourier Mellin Transform of a bacterium image. Note that in order to change the coordinates from
rectangular to log-polar you have to apply the inverse mapping and interpolate the values. If $(x,y)$ and $(r,\theta)$ are the coordinates
in the cartesian system and in the polar one respectively, then

\begin{eqnarray}
\left\{ \begin{array}{c}
r = \sqrt{x^2 + y^2} \\
\theta = \arctan y/x
\end{array} \right. 
\left\{ \begin{array}{c}
x = r \cos \theta \\
y = r \sin \theta
\end{array} \right.
\end{eqnarray}

Given a grid of $(r,\theta)$ values, the correspondences in $(x,y)$ are computed and the values in these points are taken (generally with 
interpolation).\\ 
With reference to \figref{EsempioTFM}, the plot on the upper left corner is obtained
automatically by Matlab command \emph{cart2pol}, instead the plot on the upper right corner is a mesh of the data computed by inverse
mapping. You can also notice the symmetry of the Fourier Mellin Transform in the lower right corner; the box superimposed shows the window of features that will be
extracted.


\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth,height=0.7\textwidth]{./figure/EsempioTFM.eps}
\caption{Operations involved in the computation of Fourier Mellin Transform: example taken from a bacterium image. Upper left corner: mesh of
``cart2pol'' command to Fourier Transform of the image; upper right corner: mesh obtained by inverse mapping; lower left corner: magnitude of
Fourier Transform in log-polar coordinates; lower right corner: Fourier Mellin Transform.}
\label{figure:EsempioTFM}
\end{figure}

Once a Gaussian mixture model is estimated for each class, to classify an observation $x\in \Bbb{R}^d$ the Bayesian decision rule is applied
\begin{equation} \label{eq:maxlikTFM}
x \mapsto r(x) = argmax_k {p(k)p(x\mid k)}
\end{equation}
where $p(k)$ is the \emph{a priori} probability of class $k$, $p(x \mid k)$ is the \emph{class conditional} probability for the observation
$x$ given class $k$ and $r(x)$ is the classifier decision.

The results of this technique on our database are quite good with an error rate of about 21\%
for the classification of the 12 categories of urine database, see \figref{CMTFM}. \\
This performance is consistent with the one achieved by the authors 
on their database, error rate of 15\% on three classes. Using the same data, our technique is able to halve this error rate (see par. \ref{sec:classFinExp}).\\

\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\textwidth]{./figure/CMTFM.eps}
\caption{Confusion matrix of the classifier using features derived by Fourier Mellin Transform. This result has been achieved thanks to our implementation of the method described by Dahmen et al. \cite{paper:Dahmen}, see par. \ref{sec:TFM}.
Each row indicates how a given class of corpuscles was classified. The training is done taking 500 images in each category.}
\label{figure:CMTFM}
\end{figure}

This method is particularly interesting because it is able to achieve a good performance with quite simple features and it does not require
any segmentation. On the other hand, the performance is still not acceptable for any real application and not comparable with commercial 
systems. 


\section{Detection of small objects}

In this section we will refer to the research of Burl et al. \cite{paper:Burl} about the identification of volcanoes in Venus surface. A
tipical image, of their database is shown in \figref{vulcaniVenus}. Their database had many thousands of 1024x1024 images derived from
the successful Magellan mission to Venus of NASA-JPL (1989). Their task was to identify in this large database the volcanoes by an automatic
vision system. We are referring to this work because the detection of these small objects in such a big image is similar to the detection of
pollen grains in a picture of sticky tape piece.

As we did to build the pollen database, through a graphical user interface they labeled examples in a certain number of images. Applying a
suitable matched filter and looking for the maximum values in the cross-correlation image they find interest points. Given an interest point,
they consider a patch of $k \times k$ pixels centered on it and they use principal component analysis (or discrete Karhunen-Loeve transform
\cite{libro:pca}) to reduce the space dimension.
Finally, the classification is achieved using the quadratic classifier, that is they model the two classes (volcano and not-volcano) with
gaussian densities and then, in test they apply Bayes' rule

\begin{equation} \label{bayes:burl}
p(\omega_i \mid y) = \frac{p(y \mid \omega_i)p(\omega_i)}{p(y \mid \omega_1)p(\omega_1)p(y \mid \omega_2)p(\omega_2)}
\end{equation}

where $y$ is the observed feature vector and $\omega_i$ is the i-th class.


\begin{figure}[htbp]
\centering
\includegraphics[width=0.7\textwidth]{./figure/vulcaniVenus.eps}
\caption{This image shows a 30Km$\times$30Km region on Venus containing a number of small volcanoes.}
\label{figure:vulcaniVenus}
\end{figure}
 
The main common aspects between this research and our research are:
\begin{itemize}
\item
method to build the database (we are referring to the pollen database)
\item
the philosophy of the detector for which we allow a high number of false alarms to get an high detection rate
\item
the classifier philosophy because there is a modeling of training data and then a decision based on Bayes' rule
\end{itemize}
On the other hand, the main differences are:
\begin{itemize}
\item
their classifier works in a binary case (only two classes)
\item
their detector handles images with a lot of gaussian noise, instead our (pollen database) images have only much more variability in the
background
\item
our categories can have less variability in size but generally, have more variability in shape and texture
\end{itemize}




\section{Using SEM and 3D data for pollen recognition}

We describe here a research developed mainly by Ronneberger \cite{progetto:Germania} at Freiburg University in collaboration with the weather
service of Germany and Swiss.\\
In their work, they highlight that by using fluorescence microscopy instead of the common translucent one it is easy to discriminate between
biological and non-biological material. Moreover, they observe that an expert has to analyze a pollen grain on different planes to be sure of
his classification. For these reasons, they take with the highest available quality 3D data of pollen grains by a laser scanning microscope.\\
Given a database in which each pollen is represented by a stack of images (one image for each scanned plane), they compute some
gray-scale invariants to avoid object-specific programming. These invariants are kernels (i.e. multiplication of two gray values belonging
to pixel at a certain distance) evaluated and summed over all angles or over all the shifts. Finally, they use support vector machines to
classify.\\
Their database has a collection of 26 species of ``pure'' pollen particles for a total of 385 corpuscules. They assessed the performance with the
the technique ``leave-one-out'', that is, they performed 385 tests on each pollen taking for training the rest of images in the database. They achieved
an error rate of 8\%.

The main weak points of this work are:
\begin{itemize}
\item
it is not feasible, a laser scanning microscope is very expensive and not suitable for a real-time and low-cost instrument
\item
the method is cumbersome because it requires a 3D analysis
\item
their database is very small and so their performance is not reliable
\item
``pure'' pollen grains are much less variable in appearance and size than pollen particles captured by air sampler machine (see chapter 8 for
an experimental prove).
\end{itemize}

\section{Pollen identification with Paradise network}

In \cite{paper:pollenid}, the authors describe two methods of pollen identification in images taken by optical microscope.\\
This work is one of the first attempts to automate the process of pollen identification using optical microscope. Indeed, 
several researches were done using scanning electron microscope (SEM) and good results were achieved, \cite{paper:pollidSEM1}
\cite{paper:pollidSEM2} \cite{paper:pollidSEM3} \cite{paper:pollidSEM4}. But, SEM is expensive, slow and
absolutely not suitable for a real-time application. 
 
Their first method is a model based approach and it assumes that pollen grains have a ``double edge'' in the exine. Thus, a ``snake'' (a proper spline)
 is used to detect the presence of this edge. Since not all pollen grains show the double edge property and since the achieved performance is not
 so good we do not go in further details.

 The second approach uses the so-called ``Paradise Network''. Several small templates which are able to identify important features in the
 object, are generated and then linked together to form a certain number of patterns. This scomposition is repeated in test and the system
 looks for the best matching between the pollen and non-pollen patterns. The network is able to recognize nearly 80\% of pollen as pollen and
 misclassify 4\% of the debris as pollen.
 
This work is interesting, because they use images acquired with the common equipment, namely volumetric spore trap and the optical
microscope. On the other hand, their performance is still not acceptable for any practical application and is referred to a system 
that receives as input already segmented images of pollen or junk particles. Moreover, they limit their study only to pollen particles 
with a double edge in the exine. 


\section{Conclusion}

In the previous chapter we explained the need for an automatic system for particle recognition as opposed to the manual analysis done by 
highly trained experts. \\
In this chapter, an overview was given on researches focused on automation of microscopic analysis.

In the urinalysis case, even if there is already a good system for automatic particle recognition, it can be still improved using 
segmentation free approach and trying to build a more flexible system able to extend the classification to new categories. 

Pollen recognition is still manually done. The attempts to use SEM give good but useless results because no cheap, portable and real-time
instrument can adopt this technology. On the other hand, no research was able to find good performance in detection and classification using
optical microscope images of sticky tape pictures.

All these considerations justify our interest and research in automatic visual recognition of biological particles.  

  
\clearemptydoublepage

