\documentclass[a4paper,twoside]{article}
\usepackage[english]{babel}
\usepackage[cp1250]{inputenc}
\usepackage{a4wide}
% for using hyper references, e.g. web links in bibliography
\usepackage{hyperref}
% umoznuje nastavit margins
\usepackage[hmargin=2cm,vmargin=2.5cm]{geometry}
% for multicolumn environmnet
\usepackage{multicol}
% compressed versions of listings, e.g. begin{itemize*} instead of \begin{itemize}
\usepackage{mdwlist}
% this changes labeling of second level lists
% \renewcommand{\labelenumii}{\arabic{enumii} $\models$ }
% other counters: \alph, \Alph, \roman
%Veci pro matiku
\usepackage{amsmath, amsthm, amssymb}
%Vkladani obrazku atd.
\usepackage{graphicx}
%Vypisy pseudokodu
\usepackage{algorithmic}
% pygmentize: beautiful source code listings
\include{pygmentize}
\author{Štěpán~Šindelář}
\title{Image Processing Assignment}
\begin{document}
\section{Introduction}
This document describes edge detection in computer vision in
general and also simultaneiously our implementation of
the canny edge detector, which was developed in Matlab.
\section{Edge Detection in Computer Vision}
Edges help humans to recognize familiar shapes, which is a first step in
recognizig whole objects and assigning them some meaning.
There is a lot of information in our world that has not been
digitalized, yet we would like our computers to understand it
and carry out some tasks according to what they have understood.
For example, in an ideal worl all the road signs would contain
a chip that would provide digital information for unmanned vehicles,
but in practice this is not possible and if we ever want to construct
unmanned vehicle, we must incorporate some road signs recognition
algorithm. Such algorithm gets an image from digital camera as an input
and it should recognize the road signs that appear in the picture.
As for humans, first step for such computer algorithm is to recognize edges.
Formally, we say that edge is a connected set of points at which the image
brightness changes sharply. Ideally, the detected edges form the
boundary of objects and therefore provide us valuable information for
further processing and recognition.
Edge detection is not only useful for unmanned vehicles, but in other
areas including
\begin{itemize*}
\item recognition of car plates \cite{lee1994automatic},
\item digitalization of books \cite{liu2005text},
\item aid for human pilots and drivers, for example,
\begin{itemize*}
\item recognizing speed limit road signs and displaying current
speed limit,
\item making sure that landing aeroplane has right direction with
respect to landing strip,
\end{itemize*}
\item conversion of raster images to vector images.
\end{itemize*}
There are several approaches to edge detection. In this report, we
concentrate on Canny edge detector, which deals with gray scale images.
Marr-Hilderth edge detector also expectes gray scale images. Moreover,
there are approaches for edge detection in coloured images,
for instance \cite{huntsberger1985color}. The application of edge
detection for conversion of raster images to vector images was
the main motivation behind relatively new edge detection
algorithm, which uses so called contour dots and
curves \cite{outliner:Online}.
\textit{Note: in the following text we assume only gray scale images.}
\section{Basic Image Processing}
\subsection{Gaussian Filters}
It is inevitable that an image produced by digital camera will contain
some noise. We can look at such image as a discreete signal which can be seen
as a function from the domain of image coordinates to rational numbers
in interval $[0,1]$. It is known that Gaussian probability distribution
natuarally appears in practice \cite{casella2001statistical}.
So it is resonable to "smooth" the signal so it is closer to
normal distribution. For this, we use a dicreete aproximation of the
2 dimensional normal function as a convolution matrix.
This way the new value of pixel is calculated as a weighted average
of its neightbours, where the pixel itself gets the highest weight
because of the shape of normal function and the closer a neighbour is
the higher weight it gets. Figure \ref{gaus} shows the 2 dimensional Gaussian
function and an example of Gaussian filter convolution matrix.
\begin{figure}[h]
\centering
\begin{tabular}{ l | l }
\Large
$
g(x,y) = \frac{1}{2\pi \sigma^2} e^{-\frac{x^2 + y^2}{2 \sigma^2}}
$
\normalsize
&
$
\left( \begin{array}{ccc}
a & b & c \\
d & e & f \\
g & h & i \end{array}
\right)
$
\\
\end{tabular}
\caption{Gaussian function and example convolution matrix \label{gaus}}
\end{figure}
In our implementation, we use standard Matlab function $fspecial$
to obtain a convolution matrix of Gaussian filter with specified mean
and then function $imfilter$ to apply the filter to an image.
The $imfilter$ function supports various approaches to handle the
boundary of the image, we use a replication of boundary.
%pygmentize_begin matlab
%
% G = fspecial('gaussian', [5,5], Sigma);
% Ig = imfilter(I, 'replicate', TODO);
%pygmentize_end
\subsection{Sobel Masks}
Our aim in edge detection is to recognize pixels at which the image
brightness changes. If we look at particular pixel in 2D image,
there are 4 lines that cross this pixel, two neighbours lay on
each of them, let us denote them $u$ and $v$.
If we want to calculate some number that
would tell us how much the brightness changes in given direction
at out pixel, it is natural to subtract the brightness these two neighbours.
However, to make the method even more robust, it might be helpful to
also consider the neighbours of $u$ and $v$, but in direction that
is perpendicular to the original direction. Figure \ref{sobel} ilustrates
the situation, red pixel is the pixel for which we want to calculate the
brightness change in south-north direction, green pixels are pixels
that we take into account when calculating it.
\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{sobel.png}
\caption{Pixels that we should consider when calculating brightness change in south-north direction.}
\label{sobel}
\end{figure}
The only question is what weight should we give to each of the
green pixels. Sobel mask, which is the mask that we use in our
implementation, gives twice more weight to $u$ and $v$, so the final
matrices whith which we calculate the brightness change in horizontal
and vertical directions are depicted in figure \ref{sobel}.
This type of mask is called Sobel mask.
\begin{figure}[h]
\centering
\begin{tabular}{ l | l }
$
\left( \begin{array}{ccc}
1 & 2 & 1 \\
0 & 0 & 0 \\
-1 & -2 & -1 \end{array}
\right)
$
&
$
\left( \begin{array}{ccc}
-1 & 0 & 1 \\
-2 & 0 & 2 \\
-1 & 0 & 1 \end{array}
\right)
$
\\
\end{tabular}
\caption{Sobel masks: first with high responses on horizontal edges,
second one with high responses on vertical edges. \label{sobel}}
\end{figure}
In practical implementation, we again take advantage of function
$imfilter$. We construct a Matlab matrices representing the sobel masks
and then use them as an argument for $imfilter$ as in the following
demonstration
%pygmentize_begin matlab
%
% SobelH = [1 2 1; 0 0 0; -1 -2 1];
% SobelV = [1 2 1; 0 0 0; -1 -2 1];
% TODO;
%pygmentize_end
\subsection{Gradient}
Because, for every pixel, we can express brightness changes in
vertical and horizontal directions as a number using sobel masks.
We can think of these two numbers as vectors and we can combine
them into a single vector -- gradient, as depicted in the figure
\ref{mag}. Gradient is important because it should be prependicular
to the actual edge which comes from the fact that we calculate gradient
from the brightness change in horizontal and vertical directions.
For further processing, it is convenient to calculate
gradient length, called magnitude, and the angle between
gradient and horizontal axis.
The length (in eucledian metric) can be calculated using pythagoras
theorem as follows $|g| = \sqrt{|u|^2 + |v|^2}$. Sometimes
different metrics, such as Manhattan metric $|g| = \left| |u| + |v| \right|$,
are used to improve the performance.
The angle can be calculated using tangens function:
$\alpha = tan^{-1}\left( \frac{u}{v} \right)$.
\begin{figure}[h]
\centering
\includegraphics[scale=0.8]{magnitude.png}
\caption{Gradient.}
\label{mag}
\end{figure}
\section{Canny Edge Detector}
\subsection{Non-maxima Suppression}
\subsection{Double Tresholding}
\section{Results}
\nocite{*} % to get all the entries from bibliography \nocite{xyz} only includes xyz
\bibliographystyle{ieeetr}
\bibliography{image-proc}
\end{document}
%pygmentize_begin matlab
%
% for i=1:100
% for j=1:100
% if i == j
% A(i,j) = 0;
% end
% end
% end
%pygmentize_end