\chapter{Software Specification and Design}\label{softwareDesign}

In this chapter, the features of this project are presented as a
list of functional and nonfunctional requirements, as well as a
diagram showing the use cases that are expected to occur in the
process of tree detection.  An explanation of the requirements
and use cases is provided to clarify the process of using this
project.

This chapter also presents the structure of this project both
in terms of the classes used and in terms of the subsystems
from which it is composed.  The purpose of each class and each
subsystem is explained, and information is provided regarding
the ways in which each subsystem accomplishes its task.

\section{Requirements}\label{sec:requirements}

	The purpose of this project is to find the locations of trees
	in an image.  Given that there are no constraints on the type,
	resolution, or geographic area of the image, the system relies
	heavily on the judgment of the user to overcome tree-detection
	difficulties that cannot be anticipated or resolved within
	the algorithm.	For this reason, this project uses an 
	interactive detection procedure in which the user must be able
	to see what the system is doing in order to effectively guide
	the process.  A significant portion of the program is devoted
	to the task of letting the user see the current status of the
	operation and what needs to be done next.  In addition, a large
	portion of the program is devoted to allowing the user to control
	the way that tree detection occurs in order to minimize errors.
	Table~\ref{tab:funcreq} shows the functional requirements.

\begin{table}
\begin{center}
\begin{tabular}{|ll|} \hline

	F01 & The utility shall allow the user to load a photographic \\
	    & image of a geographic area. \\
	F02 & The utility shall allow the user to display the photographic image.\\
	F03 & The utility shall allow the user to zoom and scroll the image.\\
	F04 & The utility shall load vegetation cover, vegetation type, \\
	    & and vegetation height maps if available.\\
	F05 & The utility shall display vegetation map information for\\
	    & user-specified locations.\\
	F06 & The utility shall allow the user to display one of the vegetation maps.\\
	F07 & The utility shall allow the user to display one of the\\
	    & vegetation maps on top of the image.\\
	F08 & The utility shall allow the user to select image regions\\
	    & to use as tree templates.\\
	F09 & The utility shall allow the user to select one template\\
	    & as the active template.\\
	F10 & The utility shall allow the user to edit the active template.\\
	F11 & The utility shall allow the user to associate a name,\\
	    & type, hight, and width for each template.\\
	F12 & The utility shall allow the user to place templates into groups.\\
	F13 & The utility shall allow the user to adjust tuning parameters for\\
		& tree detection.\\
	F14 & The utility shall allow the user to filter the image to\\
	    & produce a correlation image.\\
	F15 & The utility shall allow the user to display the correlation image.\\
	F16 & The utility shall search the correlation image for trees.\\
	F17 & The utility shall search only within the region currently in view.\\
	F18 & The utility shall place a mark at each location where a tree is detected.\\
	F19 & The utility shall allow the user to place a tree mark in any location\\
	F20 & The utility shall allow the user to mark any location as\\
	    & the location of an artificial structure.\\
	F21 & The utility shall allow the user to delete any mark from any location.\\
	F22 & The utility shall allow the user to save all data in a project folder.\\
	F23 & The utility shall allow the user to load a project from\\
	    & an existing project folder.\\
	F24 & The utility shall allow the user to output all item\\
	    & locations to a file usable by VFIRE.\\
	F25 & The utility shall allow the user to create rough tree\\
	    & placements based only on vegetation maps.\\
	F26 & The utility shall mark tree placements made based on veg map data.\\
	F27 & The utility shall allow the user to output map-based tree\\
	    & placements to a file usable by VFIRE.\\
\hline
\end{tabular} 
\end{center}
\caption{Functional Requirements.}
\label{tab:funcreq}
\end{table}


	The nonfunctional requirements are shown in Table~\ref{tab:nonfuncreq}.
	These features reflect some of the goals and constraints of
	the project, such as the use of C++ for optimum speed and the
	direct implementation of graphics display functions to maintain
	total control over memory consumption, which is of concern when viewing very
	large images.

\begin{table}
\begin{center}
\begin{tabular}{|ll|} \hline

	NF01 & The utility shall directly implement graphics to create and\\
		 & manage templates. \\
	NF02 & The utility shall directly implement graphics to display, scroll,\\
		 & and zoom image. \\
	NF03 & The utility shall use bilinear interpolation to zoom into and out of\\
		 & the image. \\
	NF04 & The utility shall swap correlation images to and from disk to match\\
		 & currently active template. \\
	NF05 & The utility shall use the brightness component of the image for\\
		 & tree detection. \\
	NF06 & The utility shall perform contrast stretching on the correlation image. \\
	NF07 & The utility shall be implemented on the Linux platform. \\
	NF08 & The utility shall be written in C++. \\
	NF09 & The utility shall use GDAL to read image files. \\
	NF10 & The utility shall use FLTK for its GUI. \\
\hline
\end{tabular} 
\end{center}
\caption{Nonfunctional Requirements.}
\label{tab:nonfuncreq}
\end{table}

\section{Use Cases}\label{sec:useCases}

	The operations commonly used in the tree-detection process are shown
	in Figure~\ref{fig:useCases}.	The use cases show that the user is given the
	flexibility to decide at runtime which geographic images to
	analyze, which combination of images to view at any moment, and
	which image to use as the source for any tree placements that
	are made.  The user creates a template by drawing a highlighting mark over a particular tree.
	Each template is given
	a name, as well as a nominal height and width.	These data are
	eventually placed in the output file for every tree detected using
	that template.	The user can determine the approximate height and
	width either by visual inspection of the photographic image or
	by clicking on the image at the location of the template to view
	data from the vegetation maps.	Multiple templates can be created
	for a single project, and the user can click on any existing
	template to select it as the active template.  Subsequently, the user can filter the
	image using the active template to produce a correlation image.
	The system then scans the correlation image for bright spots, corresponding to likely trees.
	Finally, the system places a mark at the location of each
	tree detected.	The user may then choose to have the current set
	of tree marks placed in an output file and stop the process or make
	changes to improve the accuracy and repeat the process.

	\begin{figure}
		\begin{center}
			\includegraphics[width=123mm]{images/useCases.png}
		\end{center}
		\caption{Use Cases.}
		\label{fig:useCases}
	\end{figure}

	\section{Classes}\label{sec:classes}

	Although the goal of this project is complex from an image analysis perspective, most of the data
	types used are fairly simple arrays of numbers.  Therefore,
	only six classes are needed, and the classes are completely
	independent with no inheritance.  Figure~\ref{fig:classHierarchy} shows the classes
	used in this project.

	\begin{figure}[h]
		\begin{center}
			\includegraphics[width=12cm]{images/classHierarchy.png}
		\end{center}
		\caption{Classes Used by Utility.}
		\label{fig:classHierarchy}
	\end{figure}


	An instance of the Image class is used to store the main image
	used in a tree-detection project. This is generally expected to be
	a photographic image of the area of interest, though other types
	of images can be used as long as they possess the same metadata.
	In addition, the system also uses three other instances of
	the Image class.  The first of these is used to allow viewing of
	a vegetation map (if any), the second of these is used to allow viewing
	of the vegetation map simultaneously with the photographic image,
	and the third of these is used as a work space to hold temporary
	image data.  Image class objects contain the raster data for
	the image as well as the georeferencing data that associates
	each location in the image with its corresponding location on the
	Earth's surface.  The Image class also contains the information to
	let the display system know how to display the image, such as the
	current scroll position, zoom level, and whether the display buffer
	needs to be refreshed.

	Instances of the Attribute class are used to store the vegetation
	maps for the system.  Each vegetation map is stored as a raster
	of vegetation codes.  The meaning of each code is stored in data
	tables contained in each instance of the class.  For each possible
	vegetation code, the data tables give the associated display
	color.	In addition, data tables also translate vegetation codes
	into information such as dominant vegetation type, percentage
	of vegetation cover, or vegetation height, depending on which
	vegetation map file the Attribute instance is being used to store.
	The display system is not designed to use objects of the Attribute
	class.	Therefore, vegetation maps are not displayed directly.
	Instead, the pattern of display colors associated with the raster
	of vegetation codes is scaled and copied to an object of the Image
	class, which is then displayed.  The vegetation map can be copied
	onto a blank Image object or it be can mixed with photographic
	data already present in the Image object to produce an overlay
	of the vegetation map over the photographic image.

	The Point class is used to keep track of individual pixels in
	an image.  Each instance of the Point class stores the horizontal
	and vertical location of a single pixel, as well as its three
	color components.  Multiple instances of the Point class are
	used to form templates.

	Each instance of the ItemRef class is used to store an image
	template.  ItemRef is a container class for objects of the Point
	class.	Such collections of Point objects constitute the image
	templates that are used as filter masks to produce correlation
	images which are then scanned for bright spots corresponding
	to tree locations.  ItemRef also contains the tuning parameters
	that govern which bright spots in the correlation image qualify
	as trees.  These parameters determine how bright the spot must
	be, how wide it must be, and how much brighter it must be than
	the surrounding image.	ItemRef also stores information about
	the area covered by each template.  When the user chooses to
	filter an image, only the portion of the image currently in view
	is filtered, allowing the user to quickly test the accuracy of a
	newly created or newly altered template without waiting for the
	entire image to be processed.  Finally, ItemRef stores a name,
	nominal height, and nominal width to be associated with any tree
	detected using that particular template.

	ItemGroup is a container class for objects of the ItemRef class.
	The purpose of ItemGroup is to allow templates to be placed into
	separate groups, of which only one group is visible at a time.
	This allows the user to decide which templates and corresponding
	tree marks will be visible simultaneously with others and which
	ones will not.	If the user wants a particular template and
	its associated tree marks to be seen only by itself, without
	any others on the screen at the same time, then this template
	should be placed into its own separate instance of ItemGroup.

	ObjectIO is the class used to read and write the binary
	tree-location files used by VFIRE.  Instances of the ObjectIO class are
	used to write the geographic coordinates of each tree along with
	its height, width, and type.  All the information is written in
	binary form to save disk space.  ObjectIO can also be used to
	read these data from VFIRE.

	\section{Program Subsystems}\label{sec:programSubsystems}

	This project consists largely of global functions rather than
	class methods.	The functions that display images could have been
	included with the Image class, but the current configuration
	is very intuitive.  A large collection of global functions,
	together, constitute the graphics display subsystem, and the
	graphics display subsystem accepts data from a small, fixed
	number of Image objects.  The process of displaying images is
	straightforward and predictable in terms of which operations
	will be performed on which class objects.  Figure~\ref{fig:systemStructure} shows the
	arrangement of subsystems.

	\begin{figure}
		\begin{center}
			\includegraphics[width=12cm]{images/systemStructure.png}
		\end{center}
		\caption{System Structure}
		\label{fig:systemStructure}
	\end{figure}

	The File I/O subsystem consists of several functions that read
	and write the files used by the system.  Vegetation map files and
	GeoTIFF image files are read by the system but never written.
	Tree-location files are written by the system but never read.
	Project data files and correlation image files are read and
	written by the system.	GeoTIFF files are usually photographic
	images, and the File I/O subsystem relies on GDAL to read these
	files.	GDAL has the ability to read and write other types of
	files, but this project currently uses it only for GeoTIFF files.

	The Template subsystem is a set of functions that allow the
	user to create, edit, and manage the templates used for tree
	detection.  The user creates templates by using the mouse pointer
	to draw highlighting marks on the desired portion of the image.
	The Template subsystem keeps track of which pixels have been
	highlighted, which template the pixel belongs to, and which group
	the template belongs to.  As shown in Figure~\ref{fig:systemStructure}, the template
	subsystem relies on the graphics subsystem to draw the marks.
	The template subsystem also keeps the data in the active template
	current as the zoom level or other view conditions change.

	The Graphics subsystem includes all the functions that
	display images on screen.  The Graphics subsystem can only
	process objects of the Image class, and to avoid running out of
	memory, this project uses only four instances of the this class.
	The first instance stores the original image.  The second stores
	the original image mixed with the color pattern of one of the
	vegetation maps.  The third stores the color pattern of the
	vegetation map by itself, and the third is a work space used
	for temporary storage of correlation images and to show tree
	placements made using vegetation map data alone.  The graphics
	subsystem is always set to display one of these Image objects.
	The object being displayed at any particular time depends on the
	current view settings selected by the user.  The need to display
	highlighting marks for the templates adds complexity to the
	display subsystem, and the need to display, at times, very large
	images adds further complexity.  However, the graphics subsystem
	always displays one of the four Image objects listed above.

	The functions in the Algorithm subsystem use the available
	templates and user-controlled tuning parameters to detect the
	locations of trees within the image.  This is done by filtering the
	image with the active template to produce a correlation
	image in which the brightness at any location varies directly
	as the similarity between the pixels in the template and the pixels in
	the corresponding neighborhood in the image.  There are many ways to 
	calculate the correlation values, but
	in this implementation, each pixel in the correlation
	image is calculated by taking the average difference between
	the two sets of pixels and subtracting this value from 255.  Once the 
	correlation image is produced, it is scanned for bright spots and
	they are marked as likely trees according to the current settings
	of the tuning parameters

