\chapter{Implementation and Results}\label{ch5}

In this chapter, the software implementation of this project is
presented.  Examples are provided, demonstrating the use of the currently
implemented features, and an explanation is given of the major design
and implementation issues.  Possible methods to optimize tree-detection
accuracy are considered, and several examples of tree-detection results
are provided.  An exact, quantitative analysis of tree-detection
accuracy is not provided because such results vary greatly among images
and may vary significantly even within a single image.  Instead of
numeric detection results, screen shots are provided, showing the
detection results obtained for portions of the panchromatic image of
Kyle Canyon, Nevada.  The screen shots are categorized to exemplify the
good, adequate, and poor accuracy regions of the image.  Good results
were obtained in about fifteen percent of the image, adequate results
were obtained in about seventy percent of the image, and poor results
were obtained in the remaining fifteen percent.  These screen shots
are intended to indicate the level of accuracy that can be expected
for images of similar resolution depicting scenes similarly suited for
tree detection.

	\section{Detecting Trees}\label{sec:detectingTrees}

	After loading a photographic image of the area of interest, the
	user identifies a group of similar-looking trees and selects
	one of them to serve as the template for the rest.  The user
	then uses the mouse to draw a highlighting mark over that
	particular tree, covering all pixels intended for inclusion in
	the template.  The tree to be selected as the template is shown
	in Figure~\ref{fig:treeZoomedIn}.  The image is zoomed in so that
	the individual tree can be easily seen.  The tree, itself, is the
	light-colored blob in the center of the image.	The shadow of the
	tree is also visible.  It is the dark, elongated shape pointing
	upward and to the left from the tree.  It is often helpful to
	include, in the template, portions of the ground surrounding the
	tree or, as shown in Figure~\ref{fig:treeZoomedInHighlighted},
	the shadow of the tree.

	\begin{figure}[h]
		\begin{center}
			\includegraphics[width=140mm]{images/treeZoomedIn.png}
		\end{center}
		\caption{Enlarged View of Tree Centered in Window.}
		\label{fig:treeZoomedIn}
	\end{figure}

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/treeZoomedInHighlighted.png}
		\end{center}
		\caption{Enlarged View of Tree Highlighted by User.}
		\label{fig:treeZoomedInHighlighted}
	\end{figure}

	Figure~\ref{fig:treeZoomedOutHighlighted} shows the image zoomed
	out to allow more of the area to be seen.  The template can still
	be seen, highlighted in green.	It is intended that the system
	will search for similar-looking trees and mark their locations.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/treeHighlightedZoomedOut.png}
		\end{center}
		\caption{Tree Used As Template and Surrounding Area.}
		\label{fig:treeZoomedOutHighlighted}
	\end{figure}

	Once the template has been defined, the user activates the filtering
	process.  The result of the filtering process is a correlation image, as
	shown in Figure~\ref{fig:correlation}.  The image looks red because the
	correlation image is monochrome and the data for it is stored in the first
	available array in the Image object being used as a temporary workspace.
	The second and third arrays (green and blue) are used for intermediate
	processing of the correlation image.  The display function could have been
	modified to show only the red array of the workspace image, displaying
	it in grayscale.  However, there are cases where it is desirable to see
	the other arrays as well, to verify that the processing algorithms are
	working properly.  The bright spots in the correlation image of Figure~\ref{fig:correlation} correspond
	to locations in the original image that look similar to the template tree.
	Filtering the original image to produce the correlation image is generally
	the most time consuming step in the tree-detection process.  For this
	reason, the system filters only the portion of the image in view at
	the time of filtering.  This way, the user can test the effectiveness of
	a template without waiting for the entire image to be filtered, and it
	can be determined quickly whether the current template is adequate.
	When it comes time to filter the entire image, the user clicks the
	``fit'' button, which will fit the entire image into the window.
	With the entire image in view, any subsequent filter command will be
	applied to the entire image.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/correlation.png}
		\end{center}
		\caption{Monochrome Correlation Image Contained in Red Buffer of Workspace Image.}
		\label{fig:correlation}
	\end{figure}

	After creating the correlation image, the system begins searching for
	bright spots.  It places tree markers in the locations of certain
	bright spots according to a set of user-adjusted tuning parameters.
	Figure~\ref{fig:resultsOneTemplate} shows the placement of tree markers
	in the portion of the original image near the template.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsOneTemplate.png}
		\end{center}
		\caption{Likely Trees Marked After Processing.}
		\label{fig:resultsOneTemplate}
	\end{figure}

	The tuning parameters tell the system which bright spots qualify as trees
	and which ones do not.  The controls are shown in Figure~\ref{fig:tuning}.
	Bright spots are initially found by identifying local maxima.  Each
	pixel in the correlation image is surrounded by eight other pixels.
	If the center pixel is brighter than six of the surrounding pixels,
	then it is a peak in six directions, and if it is dimmer than two of
	the surrounding pixels, then it is a dip in two directions.  Using the
	parameters of Figure~\ref{fig:tuning}, such a pixel would meet the first
	two criteria for inclusion as a likely tree.  However, if it had more
	than two dip directions or fewer than six peak directions, it would fail.
	Since each pixel in the correlation image is a linear combination of
	other values, the word {\em moment} is used to refer to the pixel value itself.
	Figure~\ref{fig:tuning} shows that each local maximum pixel must have a value of
	at least 190 on a scale of 0 to 253.  The maximum value for any pixel
	is 253 because the values 255 and 254 are reserved for manually placed
	or manually deleted items, respectively.  Bright spots corresponding
	to valid trees are often surrounded by dark-colored perimeters.
	Figure~\ref{fig:tuning} shows that a bright spot must be surrounded
	by a perimeter at least 18 units darker than the brightest pixel in
	order to qualify as a likely tree location.  The distance between the
	perimeter and the brightest pixel usually falls within certain bounds.
	In the case shown in Figure~\ref{fig:tuning}, the perimeter must
	lie anywhere from one to thirteen pixels from the brightest pixel in
	the bright spot.  In addition, the perimeter may be partial or it may
	completely enclose  the bright spot.  Estimating the extent of enclosure
	is done by scanning in eight  directions from the brightest pixel.
	In the case of Figure~\ref{fig:tuning}, the perimeter must be detected
	in all eight directions for a given bright spot to qualify as a likely
	tree.  It is possible for one tree to produce a bright spot with more
	than one local maximum.  Therefore, a minimum distance between tree
	markers is set by the user.  Tree markers occurring closer than the
	minimum distance from any other marker will be culled from the image.
	Finally, the user may wish culling to occur on a per-template basis,
	in which case the tree markers for one template are culled without
	regard to their distances to the tree markers from other templates.
	On the other hand, the user may consider all the tree markers to refer to
	the same type of tree, in which case the tree markers from one template
	should not be allowed to exist too close to marks from another template.
	In the case of Figure~\ref{fig:tuning}, the markers must be at least
	four meters apart and the markers for the active template are culled
	without regard to the markers of other templates.

	\begin{figure}
		\begin{center}
			\includegraphics[width=8cm]{images/tuning.png}
		\end{center}
		\caption{Tuning Parameter Controls.}
		\label{fig:tuning}
	\end{figure}

	As mentioned above, the user has the ability to manually place markers.
	The great majority of markers are used to represent trees, but they
	can be used to represent artificial structures as well, depending on
	the associated item code.    In addition, the user can manually delete
	any marker of any type.  The locations of manually placed or deleted
	items are stored in the correlation image itself.  When a user places
	an item manually, the value 255 is placed in that particular location
	in the correlation image.  This value is interpreted as a valid tree
	or artificial structure, and the automatic system cannot override such
	placements even if its rules would not otherwise have placed an item
	in that location.  Similarly, when the user manually deletes an item, the value
	254 is placed in that particular location in the correlation image.
	This value is automatically interpreted to contain nothing, and the
	automatic system cannot override such deletions even if its rules
	would otherwise have placed an item in that location.

	In the process of tree detection, large amounts of data may
	be produced.  To allow the user to interrupt the process and
	resume it at a later time, the system allows the user to save
	the  data in a project directory and reload it when needed.
	A project directory contains one project file, along with
	one correlation image file for each template in the project.
	The project file is a text file that contains the current values
	of the tuning parameters for each template as well as all other
	data associated with the templates.  The correlation image files
	contain the raster data for each correlation image.

	Once the tree-detection process is satisfactorily completed,
	the user outputs all tree and artificial structure locations to a
	binary file that can be used as input for the VFIRE application.
	To save space within the file and reduce the time it takes VFIRE
	to read the file, tree types are expressed using an item code,
	as shown in Figure~\ref{fig:placementFile}.  The reference list
	of item codes is shown above the list of existing templates
	so that the user can place the correct code for each template
	before generating the placement file.  The user also has the 
	option of letting the tree type be selected by the vegetation type vegetation map.
	For example, if the user selects item code 14 in Figure~\ref{fig:placementFile}, 
	then, for each tree, code 14 will be replaced by whatever code matches the tree 
	type in the vegetation map at the location of that particular tree.
	Each template is called a reference because the system refers
	to the data in the template to determine what to search for.

	\begin{figure}[h]
		\begin{center}
			\includegraphics[width=140mm]{images/placementFile.png}
		\end{center}
		\caption{Placement File Information.}
		\label{fig:placementFile}
	\end{figure}

	\section{Using Vegetation Maps}\label{sec:usingVegMaps}

	In addition to the photographic imagery of the area of interest,
	the user can also view vegetation maps of the area.  This project
	is currently able to handle three different vegetation maps.
	The first of these is the map showing vegetation cover.  Each $5m \times 5m$
	surface cell has a code that determines what percentage of the
	land in that cell is covered by vegetation.  The second type of
	vegetation map is the vegetation type map.  Each $5m \times 5m$ cell has a
	code specifying the dominant vegetation species within that cell.
	The third type of vegetation map is the vegetation height map.
	Each $5m \times 5m$ cell has a code specifying the range of tree heights
	within the cell.  Each of these maps can be displayed by itself
	or as an overlay onto the photographic image of the area.
	Figure~\ref{fig:tifAlone} shows the panchromatic image of
	Kyle Canyon, zoomed out far enough to show the entire image all
	at once.  Figure~\ref{fig:vegMapAlone} shows the vegetation type
	vegetation map for the same area, and Figure~\ref{fig:mixed}
	shows the vegetation map as an overlay on the panchromatic image.

	\begin{figure}[h]
		\begin{center}
			\includegraphics[width=140mm]{images/tifAlone.png}
		\end{center}
		\caption{Photographic Image Alone.}
		\label{fig:tifAlone}
	\end{figure}

	\begin{figure}[h]
		\begin{center}
			\includegraphics[width=140mm]{images/vegMapAlone.png}
		\end{center}
		\caption{Vegetation Map Alone.}
		\label{fig:vegMapAlone}
	\end{figure}

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/mixed.png}
		\end{center}
		\caption{Photographic Image and Vegetation Map Together.}
		\label{fig:mixed}
	\end{figure}

	The image overlay is intended to help the user to determine
	tree types.  Similar-looking trees found to exist on uniformly
	colored regions are probably the same type of tree.  The tree
	type itself can be determined by clicking anywhere in the region.
	Figure~\ref{fig:textOutput} shows the text output that results from clicking
	on the image.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/textOutput.png}
		\end{center}
		\caption{Terminal Text Output Produced When User Clicks on the Image.}
		\label{fig:textOutput}
	\end{figure}

	Vegetation maps can be used to make tree placements even when
	no photographic image is available.  Figure~\ref{fig:randomPlacement} shows how this
	project can make tree placements based on the vegetation cover
	vegetation map.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/randomPlacement.png}
		\end{center}
		\caption{Tree Placements Made According to Vegetation Map Tree Densities.}
		\label{fig:randomPlacement}
	\end{figure}

	The system draws a circle for every location where a tree is placed.
	This allows the user to see the results of the current settings and make
	adjustments if necessary.  The density of tree placements in any cell
	is governed by the designated vegetation cover percentage of that cell.
	The vegetation type vegetation map may be used to determine tree types
	or the types may be generated randomly according to user-specified relative
	proportions as shown in Figure~\ref{fig:randomPlacementFile}.

	\begin{figure}
		\begin{center}
			\includegraphics[width=10cm]{images/randomPlacementFile.png}
		\end{center}
		\caption{Random Placement File Information.}
		\label{fig:randomPlacementFile}
	\end{figure}

	\section{Tree Detection Accuracy}\label{sec:treeDetectionAccuracy}

	When the system fails to mark the location of a tree, it
	is considered a false negative result, and when it marks a
	location where no tree actually exists, it is considered a false
	positive result.  Ideally, the tuning parameters should be
	adjusted to balance each type of error so that both are kept
	below the maximum acceptable limit.  In practice, however,
	it may not be possible to keep both types of errors within
	acceptable limits at the same time.  A more generally applicable
	procedure, therefore, is to adjust the tuning parameters to
	put the number of false positives within acceptable limits
	and then create a new template to deal with the remaining
	false negatives.  Figure~\ref{fig:resultsTwoTemplates} shows
	the same region depicted in Figure~\ref{fig:resultsOneTemplate}
	after the inclusion of a second template.  As shown in the image,
	adding the second template reduces the number of false negatives.
	The tree markers associated with the second template are shown in
	a slightly brighter red to indicated that they are associated with
	the currently active template.	This image depicts the adequate,
	though not exceptional, level of accuracy found in about seventy
	percent of the image.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsTwoTemplates.png}
		\end{center}
		\caption{Likely Trees Marked After Processing with Two Templates.}
		\label{fig:resultsTwoTemplates}
	\end{figure}

	The second template takes advantage of the fact of being surrounded by
	shadow on all sides, unlike the first template, which has shadow only on
	two sides.  The trees themselves both look like light-gray blobs.  It is
	the nearby shadows that distinguish them from each other.  The second
	template will more easily detect trees that are similarly surrounded by shadow.
	This is the reason why some portion of the area surrounding a tree is
	often included in the template.  Including in the template some portion of
	the immediate area around a tree often produces darker perimeters around
	bright spots corresponding to trees in the correlation image.  As the
	template approaches the edge of a tree during the filtering process, the
	shadow in the template overlaps the tree in the image and the shadow in
	the image overlaps the tree in the template.  This situation produces a
	low correlation value, and it occurs mostly when the template is at the
	edge of a tree, resulting in a dark perimeter around the bright spot.
	As the template approaches the center of the tree, the similar regions
	tend to coincide more, which produces the bright spot in the center.
	If the shadow or otherwise dissimilar area surrounding a tree is not
	included in the template, the bright spot will still be produced in the
	correlation image, but it is less likely to be enclosed by an extra
	dark perimeter.  The darker perimeter is helpful because it makes
	the bright spot easier for the system to recognize as a likely tree.
	Still, there does remain some advantage in the practice of excluding any
	surrounding area from the template and including only the tree itself.
	The advantage is in reducing the false negatives caused by differences in
	nearby shadows.  However, the disadvantage of doing this is in increasing
	the number of very conspicuous false positives, where there is nothing
	in the vicinity that could possibly be a tree.  In general, both methods
	should be tried, keeping in mind the strengths and weaknesses of each.
	The templates shown in Figure~\ref{fig:resultsTwoTemplates} were chosen to
	produce satisfactory tree detection results in most portions of the image.
	In about fifteen percent of the image, however, false positives were
	found to be excessively high.  Figure~\ref{fig:resultsBurntTrees} shows
	an area where the straight-line shadows of burnt trees were mistaken
	for living trees.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsBurntTrees.png}
		\end{center}
		\caption{False Positives Produced by Burnt Trees.}
		\label{fig:resultsBurntTrees}
	\end{figure}

	Figure~\ref{fig:resultsSmallTrees} shows an area where what appear to be
	large shrubs or small trees are commonly mistaken for the medium-sized
	trees being sought.  About ten percent of the image is covered by this
	type of vegetation.  These areas account for most of the false positives
	produced for this image.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsSmallTrees.png}
		\end{center}
		\caption{False Positives Produced by Small Trees and Shrubs.}
		\label{fig:resultsSmallTrees}
	\end{figure}

	In some areas, even a small number of false positives is unacceptable.
	Figure~\ref{fig:resultsBuiltUp} and Figure~\ref{fig:resultsBuiltUp2}
	show two such areas.  These are the two regions with a significant
	concentration of artificial structures.  Clearly, a false positive
	occurring directly on top of a house or in the middle of a road would be
	unacceptable.  Therefore, the system allows the user to manually remove
	each such error from the current project.  This is not a lengthy process
	because these regions are so small.  Manual correction would not be practical,
	however, if these regions were significantly larger.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsBuiltUp.png}
		\end{center}
		\caption{False Positives On Houses.}
		\label{fig:resultsBuiltUp}
	\end{figure}


	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsBuiltUp2.png}
		\end{center}
		\caption{False Positives On Roads.}
		\label{fig:resultsBuiltUp2}
	\end{figure}

	In the remaining fifteen percent of the image, detection
	results were relatively good.  Figure~\ref{fig:resultsGood1} and
	Figure~\ref{fig:resultsGood2} show two of the areas where the trees
	are spaced far enough from one another to show a single light gray blob
	coupled with a clearly defined shadow.  This is the best situation for
	tree detection.  When the trees are too close together, the blobs and
	shadows interfere with one another and confuse the system.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsGood1.png}
		\end{center}
		\caption{Good Results in Area with Few Items to Produce False Positives.}
		\label{fig:resultsGood1}
	\end{figure}

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsGood2.png}
		\end{center}
		\caption{Good Results in Another Area with Few Items to Produce False Positives.}
		\label{fig:resultsGood2}
	\end{figure}

	There are areas of the image where tree detection accuracy
	is unknown.  These are the regions entirely covered in shadow.
	Figure~\ref{fig:shadow1} and Figure~\ref{fig:shadow1} show some of the
	regions bordering the dark areas where tree detection is not possible.

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsShadow1.png}
		\end{center}
		\caption{Portions of Image Obscured by Shadow.}
		\label{fig:shadow1}
	\end{figure}

	\begin{figure}
		\begin{center}
			\includegraphics[width=140mm]{images/resultsShadow2.png}
		\end{center}
		\caption{Additional Area Obscured by Shadow.}
		\label{fig:shadow2}
	\end{figure}




