\chapter{Detector}		\label{sec:detector}
\thispagestyle{empty}
  
Detection is the first stage of a recognition system. Given an input image with a lot of particles, it aims to find key points,
which have at least a little probability to be a corpuscle of interest. Once that one of these points is detected, a patch is centered on
it and then, it is passed to the classifier in the next stage. It is extremely important to detect almost all the objects of interest when they
are rarely found in images and their number is low, as it typically happens in pollen detection. 

In our research, we need to detect points only in pollen database. This database was labelled by human experts and a reference list has been
built with information about genus and position of pollen particles sampled from air and now in images.\\
Thus, we evaluate performance by measuring how well our automatic detector agrees with the set of reference labels. A \emph{detection} 
occurs if the algorithm indicates the presence of an object at a location where a pollen exists according to the reference list. 
Similarly, a \emph{false alarm} occurs if the algorithm indicates the presence of an object at a location where no pollen exists 
according to the reference list \cite{paper:Burl}. \\
The overall performance can be evaluated computing:

\begin{flushleft}
\begin{equation}
\mbox{perc. of detection} = \frac{ \mbox{nr. of detected interest particles} }{ \mbox{ nr. of particles of interest} } * 100
\end{equation}
\begin{equation}
\mbox{perc. of false alarms} = \frac{ \mbox{nr. of detected particles which are not of interest} }{ \mbox{ nr. of particles of
interest} } *100
\end{equation}
\end{flushleft}

More precisely, we consider a box centered on the detected interest point. We say that there is a matching between this box and the expert's
one, if 

\begin{equation} \label{eq:overlapbox}
\sqrt{(x_{c1}-x_{c2})^2 + (y_{c1}-y_{c2})^2} \leq \alpha \sqrt{ \frac{A_1 + A_2}{2}}
\end{equation}

where $x_{ci},y_{ci}$ are the coordinates of the box centroid, $A_i$ is the area of the box and $\alpha$ is a parameter to be chosen. In our
experiment, we chose $\alpha$ equal to $1/\sqrt{2}$. This value and parameter are the same ones we used in the software we developed 
to label pollen grains. In that situation,  eq. 
(\ref{eq:overlapbox}) is used to establish when two expert's boxes overlap and if this condition is satisfied then, the software
removes the old box because there is too much overlap and we interpret the old box as a mistake. Analogously for the detector, if the 
same condition holds, we say that there is a
matching between the automatically detected box and the expert's one. 

Typically, a detection system has some parameter to tune. When one parameter is varied then, also the false alarm and detection
percentages change. Thus, by varying at each time a threshold, we can compute a sequence of percentages. The resulting curve is
known as receiver operating characteristic (ROC) curve. 

In the following sections, we will describe two detectors and we will assess their performance thanks to ROC curves.

\section{Detector based on difference of Gaussians} \label{sec:DetDoG}

This detector is based on a filtering approach \cite{paper:Lowe} \cite{draft:Lowe}.\\
The outline of this system is shown in \figref{schemaDoG}; an example of the involved computations using an image of pollen database is shown in \figref{outlineDoG2b}.

\begin{figure}[htbp]
\centering
\includegraphics[width=1\textwidth]{./figure/outlineDoGa.eps}
\caption{Outline of detector based on DoG computation.}
\label{figure:schemaDoG}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[width=1\textwidth,height=.2\textwidth]{./figure/outlineDoG2b.eps}
\caption{Example of computations done by DoG detector for an image of pollen database.}
\label{figure:outlineDoG2b}
\end{figure}


The input image is converted in gray level values and sampled with a sample frequency $F_s$. Then, it is filtered two times with a Gaussian
kernel with a certain standard deviation $\sigma$ to produce images $A$ and $B$. Finally, we extract interest points looking for the maxima and minima in the
image $A-B$.

In \figref{esempiokernelDoG}, we show the plots of Gaussian kernel and difference of Gaussian (DoG) kernel and their DFT in the 1-D case.\\
The goal of the sampling stage is to make the smallest pollen appear a little blob of few pixels. This automatically removes dust particles smaller than pollen grains and reduces the amount of computation. With a proper choice of the variance of the Gaussian kernel $\sigma$, the output image will have a peak in correspondence of round shaped objects with a certain size. \figref{esempiokernelDoGScala} shows a synthetic example in which two filters with DoG kernels having different $\sigma$ are applied to an image. When $\sigma$ is low, the output image has a narrow peak in correspondence of the little blob of the input image. When $\sigma$ is high, the peak is in correspondence of the largest blob. The variance of the Gaussian kernel allows to select the size of the interest objects.\\
In order to detect how good a point of extremum is in the output image, we fit around it a paraboloid. The
vertex of this paraboloid gives the exact position of the interest point and its curvature is a measure of its quality. If this value is too
low then, it is likely that this extremum is generated by a strip shaped object or by an object that is smaller than the one we are looking for. If this value is high then the object in that position is round and it has a size that fits the size of our target.


\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth,height=0.5\textwidth]{./figure/esempiokernelDoG.eps}
\caption{First row: basic kernels, namely Gaussian kernel and the equivalent kernel of the whole system. Second row: DFT of previous kernels.}
\label{figure:esempiokernelDoG}
\end{figure}


\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth,height=0.4\textwidth]{./figure/esempiokernelDoGScala.eps}
\caption{This example shows how the choice of scale $\sigma$ is related with the dimension of objects of interest. The first image has a little blob of 1 pixel in the upper left corner and a larger one of 10 pixel diameter in the lower right corner. The second image shows a good peak in the position of the smaller blob, $\sigma$ was chosen equal to 1. The third image shows a good peak in the position of the larger blob, $\sigma$ was chosen equal to $8\sqrt{2}$.}
\label{figure:esempiokernelDoGScala}
\end{figure}

We run experiments on database of pollen particles captured by air sampler machine. The ROC curves are shown in \figref{ROCDoG}. Each ROC is
drawn for many values of the sample frequency. Because we are considering a set of values also for $\sigma$ we have a family of curves.
For example, with sample frequency equal to 12 and $\sigma$ equal to 8 we are able to detected nearly 90\% of pollen grains  with 1000\% 
of false alarms.


\begin{figure}[htbp]
\centering
\includegraphics[width=1\textwidth]{./figure/ROCDoG2.eps}
\caption{ROC curves for detector using DoG.}
\label{figure:ROCDoG}
\end{figure}


We observe that the previous evaluation is quite optimistic because in these experiments we kept the size of patches constant. The
classifier needs patches tightly centered on the object because around it there are other particles that can change the values of our features. This
was confirmed when we tried to classify these detected patches because we achieved poor results. Thus, we should take into account
additional errors for the necessary operation of box to object adaptation. \\
Moreover, in the previous experiment we used a square box of side 200
pixels because the biggest pollen, namely pine, has these dimensions. On the other hand, most of pollen grains can be bounded by a box of side 50
pixels. Then, it is likely that we had some matches by chance. Because our boxes are quite big and we admit some overlap between them, these
patches may give a match even if the interest point is not on a pollen but in some point near it.



\section{Morphological detector}	\label{sec:DetMor}

This detector is based on morphological operations on the gray level image like: edge detection, dilation, erosion, opening, closing. The need to adapt the size
of the boxes around objects, (see previous section), encouraged us to try this new method.

We now describe the main operations involved. Given an image we make a conversion to normalized\footnote{After the normalization the
background mean is equal to 0 and the minimum value is -1.} gray level values and then,

\begin{enumerate}
\item we compute the edges applying ``canny'' edge detector and we get a binary image
\item we make 4 dilation with a disk of radius 1 pixel
\item we fill the holes
\item we label the regions and compute a mask: a region is kept if the following conditions are satisfied
\begin{itemize}
\item its area is bigger than a threshold, \emph{ThresAm}
\item the ratio between major and minor axis of ellipse fitting the region is less than a threshold, \emph{ThresAx}
\item the mean of gray values that in the original image fall inside the region is between two thresholds, \emph{ThresMeanL} and
\emph{ThresMeanH}
\end{itemize}
\item we make 2 closing with a disk of radius 1
\item we make 1 dilation with a disk of radius 1
\item we compute a new mask applying the same tests of point 4
\item we make 2 closings and 1 opening with the same disk of radius 1
\item we fill the holes
\item we compute a new mask based on the previous one taking only the regions that satisfy the following tests:
\begin{itemize}
\item area must be between thresholds, \emph{ThresAm} and \emph{ThresAM}
\item the ratio between major and minor axis of ellipse fitting the region is less than a threshold, \emph{ThresAx}
\item the mean of gray values that in the original image fall inside the region is between two thresholds, \emph{ThresMeanL} and
\emph{ThresMeanH}
\item the ratio between the area of the region and its bounding box must be grater than threshold \emph{ThresExt}
\end{itemize}
\end{enumerate}

These series of operations were found experimentally. However we can find some justifications for the tests done to select good regions. No
pollen is too dark or too bright (see thresholds \emph{ThresMeanL} and \emph{ThresMeanH}), is too big or too small (see thresholds
\emph{ThresAm} and \emph{ThresAM}), is too elongated (threshold \emph{ThresAx}) or U-shaped (threshold \emph{ThresExt}).

In \figref{esempioMask1}, \figref{esempioMask2} and \figref{esempioMask3}, you can see the operations involved in the mask computation, 
the regions found and the patches that will be sent to the
classifier.

\begin{figure}[htbp]
\centering
\includegraphics[width=1\textwidth,height=0.65\textwidth]{./figure/esempioMask1.eps}
\caption{Masks and morphological operations computed by morphological detector.}
\label{figure:esempioMask1}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\textwidth]{./figure/esempioMask2.eps}
\caption{Original image with mask superimposed.}
\label{figure:esempioMask2}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth,height=0.6\textwidth]{./figure/esempioMask3.eps}
\caption{Original image with boxes automatically detected by our algorithm (green) and by the expert (red).}
\label{figure:esempioMask3}
\end{figure}


We show in \figref{ROCMorpDetTP2} ROC curves drawn varying one threshold each time and keeping to default values the other parameters. These
curves are computed taking more than 70 images with 236 pollen grains.

\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth,height=0.65\textwidth]{./figure/ROCMorpDetTP2.eps}
\caption{ROC curves of morphological detector.}
\label{figure:ROCMorpDetTP2}
\end{figure}

We run a last experiment with a choice for these thresholds inspired by the previous ROC curves, see \tabref{performanceDetMor1}, 
and we achieved the result in \tabref{performanceDetMor2}. 
The performance is quite good and promising. The worsening when considering the full data set may be caused by a
different kind of preparation of slides (the collection of images in our database took 4 months and some adjustment was done) and to the
average smaller number of pollen particles per image in the other part of database.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{4cm}|c||}
\hline
\emph{parameter}	& \emph{value}	\\
\hline
\hline
ThresAream	& $3*17^2$ \\
\hline
ThresAreaM	& $3*80^2$ \\
\hline
ThresExt	& $0.4$ \\
\hline
ThresAx		& $2.2 $ \\
\hline
ThresMeanL	& $-0.3$ \\
\hline
ThresMeanH	& $-0.025$ \\
\hline
\hline
\end{tabular}
\end{center}
\caption{Final choice of parameters in morphological detector.}
\label{tab:performanceDetMor1}
\end{table}


\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{4cm}|{c}|{c}||}
\hline
\emph{performance}	& \emph{71 images / 236 pollens}	& \emph{299 images / 562 pollens}	\\
\hline
\hline
perc. detection	& 93\%	& 87\% \\
\hline
perc. false alarms	& 956\%	& 1400\% \\
\hline
\hline
\end{tabular}
\end{center}
\caption{Performance of morphological detector}
\label{tab:performanceDetMor2}
\end{table}


This detector is able to find pollen particles with a very high probability and to do a good segmention of these particles (see chapter 8).
Its main disadvantages are:
\begin{itemize}
\item slowness because all morphological operations are made on the image with the original resolution
\item high customization, this detector is likely not suitable to detect other  kinds of particles
\end{itemize} 

  
  
\clearemptydoublepage
