Digital Snow Prints

Theoretical Background
Methods
Results
Practical Applications
Possible Extensions
Subdivision of Tasks


Theoretical Background:

The technique of animal tracking using snowprints dates as far back as primitive hunter/gatherer societies. Early man needed to be able to correctly recognize an animal's tracks and deduce information to ensure its swift capture for the purposes of consumption. (The deer, bobcat, and human have distinctive prints) Since then, the science of animal tracking has been improved enormously. Naturalists have set up bait stations for the express purpose of monitoring the prints of the animals they attract. This technique has proved useful in studying species that are widely dispersed over a geographical region. Furthermore, biological study of animal behavior and perambulation has revealed the wealth of data an expert tracker can deduce from a set of animal prints. Specifically, careful observation of tracks can indicate the animal's speed of travel and its physical condition.

Animal gait is a function of the animal's morphology and its speed of travel. Every animal has a distinctive pattern of prints which is characterized by three measurements: stride, straddle, and intergroup. The stride is the longitudinal distance between footprints made by the same apendage. The intergroup is the longitudinal distance between footprints of the anterior or posterior. The straddle is the lateral distance between the footprints of anterior or posterior.

Today, animal tracking has been further improved by the use of the helicopter as a means of locomotion for the tracker. This technique is used frequently in Alaska and Canada to monitor animal populations that reside in open habitats. Helicopter tracking allows the tracker to cover far more ground than on foot, but it increases the likelihood of misidentifying tracks or losing the trail altogether.

It is to this enormous wealth of knowledge that the Digital Snow Prints Group adds yet another innovation: automated animal tracking using signal processing techniques. This development will merge the intuition and experience of expert animal trackers with the computational speed of current computers. The results of this new technology are promising.

Beyond the science of animal tracking, this project also employs the signal processing techniques of convolution and time-domain analysis. Each animal print is converted to a matrix representation in Matlab. These are compared against images located in the detection area. The snow scene is analyzed using a matched filter. A flipped, conjugated version of each print matrix is shifted and convolved repeatedly across the scene. This results in a correlation value that measures the similarity between the two signals. According to the Cauchy-Schwarz theorem, this correlation value will be maximized when the correlated areas are identical. A threshold value is defined for the matched filter. When the correlation value is above this threshold, a match is found. Otherwise, there is no match.




Methods Employed:

There are 3 different techniques employed in this project to detect the animal prints: straight convolution, convolution with whitespace elimination, and convolution with known gait optimization. Each technique varies in terms of its complexity and computational efficiency. The various algorithmic tradeoffs are analyzed below.

The straight convolution algorithm uses a brute force detection and scanning. A small window sweeps over the detection area searching for prints. The current window is compared to the possible permuations of prints. Each image is compared against all stored animal prints and all possible rotations of those prints. The correlation values are checked against a set threshold. Images above the threshold are marked as a positive match for that particular animal. Each match is indicated by an 'x' in the graphical interface. An interpolation algorithm is used to connect these points and plot the projected path of the animal. This algorithm is relatively simple, but extremely slow. It requires searching the entire detection area and matching the images against empty space. This method is extemely wasteful which contributes to the the slow processing speed of the algorithm.

The second method of convolution with whitespace elimination requires a slight modification in the initial stages of the algorithm. Instead of checking the entire detection area against the print images, this method pre-scans the area for white space. Each print is outlined with a fitted box that marks off its area. Then, the detection area is multiplied by a whitespace remover to ignore the extraneous space. The original correlation algorithm is then run on the remaining portions of the detection area. The search is much more efficient because it only spends computational time on areas that contain prints. Since most of the detection area is composed of white space, this method is much more efficient. This technique is much more effective in vast snowscapes with few prints.

The third method of print matching exploits properties of gaits . The algorithm begins by eliminating all whitespace as in the previous algorithm. Then it scans for a single instance of an animal print. Once the print is identified using convolution, the locations of the rest of the prints are predicted using gait information stored in a lookup table. (The data in the lookup table assumes a walking gait for each animal.) This method is far more computationally efficient than the previous two because it requires less image matching. Reading data out of a lookup table is significantly faster than comparing each print separately. Moreover, this method enables the snowprint tracker to detect animals travelling at specific speeds. If additional gait information were loaded into the lookup table, animal prints could be selected not only by their type, but also by their speed of travel.


Results:

The data show that naive convolution requires approximately 11 times more flops and 15 times more CPU time than convolution with gait optimization. Convolution with white space removal requires about 4 times more flops and 7 times more CPU time than convolution with gait optimization. The snow print detection method that uses gait information is clearly the most efficient; however, it has limitations. The procedure assumes the animals are walking at a constant speed; therefore, it is extremely inefficient at tracking animals moving at any other pace. Using convolution with white space elimination is preferable over gait optimization in the case of varying gaits.


Practical Applications:

Animal trackers can take digital pictures of animal prints they observe while tracking on foot or from the air. These images can be converted to an image matrix and analyzed by the snowprint tracker at a later time. The data can be used to confirm or refute the initial conclusions of the tracker. This can help add credibility to new discoveries regarding animal population sizes or migratory patterns that are often controversial and difficult to substantiate. Environmental groups attempting to estimate the population sizes of certain species will find this program especially helpful in their legal battles to classisfy a species as endangered.

In addition, the snowprint tracker can be used as a sort of "assistant" to the tracker in the field. Portable computing technology allows bringing this program into the field and using it as the primary tool for tracking. This could be very beneficial to amateur trackers with little experience, or for helping expert trackers searching for hard to track species. Moreover, this program will prove extremely efficient for analyzing areas of heavy animal traffic. An aerial view of hundreds of prints can be analyzed in a matter of minutes with tremendous accuracy. This task could take a tracker hours or even days to complete. Computer analysis can pick specific animals or specific gaits from a much larger collection of prints. Thus, a tracker can determine the fraction of bobcats that are chasing prey rather than walking leisurly through the forest.

Beyond the obvious benefit to trackers and naturalists, this program could also have military applications. Aerial satellite surveillance can capture digital images of soldier footprints for large armies. These images can be analyzed to determine the size of the advancing army, the speed and direction of their travel, and the possible threats they pose to enemy territory. This intelligence data could all be generated automatically by sophisticated computers and relayed to local commanders on a constant basis. The future possiblities of snowprint analysis are tremendous.


Possible Extensions:

The project capabilities could be expanded through the addition of more detailed gait information for each animal. Such information would improve the convolution performance as well as determine the speed at which the animal is moving. Initial investigations indicate that frequency analysis of the snow scene could reveal the necessary gait information. Wavelets could be used to improve the white space removal function because of their edge-detection abilities.


Subdivision of Tasks:

Zachary wrote the Matlab code and implemented all of the algorithms. He designed and executed the described enhancements to the original brute force convolution method.

Harris wrote the text for the final report, project description, and progress report. He researched the use of wavelets in our project, though those techniques investigated were not implemented.

Hilary put forth the snow print idea! She designed the project print images in XFIG. Also, she designed the poster and helped with algorithm descriptions. She edited most of the text on this webpage.

Alexa designed and coded the webpage, integrating the project information and keeping it current. She contributed to the Matlab coding by writing the method comparison section. She constructed the poster with Hilary.