Finding ships lost at sea using tracking algorithms

SOS…SOS…Shipwrecked crew members aboard a dinghy send out distress signals. Hovering overhead, a helicopter searches for the dinghy using an infra-red camera or synthetic aperture radar (SAR). But the helicopter is unable to locate the dinghy because the images are inaccurate, distorted, or incomplete.

The odds of being rescued in this scenario have been greatly improved by computerized prediction and tracking methods developed by scientists working on the project Prediction in INTeracting Systems (PINTS). This is one of 23 projects now being carried out by MITACS, one of the federal government's network of excellence.

The mandate of PINTS is to conduct mathematical research into the filtering theory behind computer-based tracking and image processing systems. The project is headed by Dr. Michael Kouritzin, an associate professor of mathematical sciences at the University of Alberta. The first results were presented at the AeroSense-2000 Conference in Orlando, FL, (April 2000), by graduate student, David Ballantyne. He presented Dr. Kouritzins's method of locating a dinghy-lost-at-sea from distorted, corrupted, partial observations of its signal by using filtering theory.

The dinghy-lost-at-sea simulation presents an example of seven-dimensional tracking based on two-dimensional observations that has applications in search and rescue. In this project a computer simulates observations of a boat on the ocean surface that are corrupted and distorted by background noise. From these observations researchers attempt to determine the location and motions of the dinghy in order to rescue the occupants. But because of the altitude of the helicopter, the images obtained are so obscured by noise that the position of the boat cannot be determined by a single picture. However, knowledge of the likely motions of this type of boat along with a sequence of images taken at several times enables researchers to locate the boat in all but the noisiest conditions.

The novel method of filtering used to detect the dinghy is called the "Branching Particle Method for Tracking." The filter tracks the target by simulating a large number of independent particles that move with the same types of motion and variables affecting the movement of the dinghy. When an observation is available, the filter branches (duplicates) some particles that are likely to be tracking the dinghy and removes some that are unlikely to be tracking it.

The result of filtering is, after each observation, an approximation to the probability that the dinghy is in any region of space given all observation images so far. Simply put, with a branching particle filter the dinghy is more likely to be in areas where there are more particles.

According to Dr. Kouritzin, the mathematical modelling and prediction techniques that can be used for search and rescue missions can also be applied to a broader range of complex systems, such as communication networks and financial markets. The ability to classify and track targets such as boats, aircraft, submarines and other objects based upon distorted, corrupted sensor information is a basic requirement for air traffic management, search and rescue, surveillance, narcotic smuggling prevention and military industries.

Currently, Dr. Kouritzin is working with VisionSmart, an engineering firm in Edmonton, to design scanning algorithms for lumber mills that will help assure quality in the production of oriented strand boards (OSB), a standard building material.

According to Daniel Kenway, President of VisionSmart the OSB industry provided VisionSmart with an opportunity to apply high-speed processing to physical property inspection. OSB mills require detection of corner and edge defects and stains, as well as graders which are capable of sorting boards at assembly line speeds. For mechanical vision systems to be beneficial under such high output production, they must be not only as fast as a human quality controller, but also as discriminating.

Infrared cameras can be used to detect density variations and resin spots in the boards through thermographic (heat pattern) imaging as the boards are cooling. However, these data are heavily corrupted and distorted by uneven cooling resulting from board motion, by debris on the boards, and by required positioning of the cameras. But by using filtering techniques scanners can better locate imperfections and weaknesses in the OSB boards.

At the Université du Québec à Trois Rivières, Dr. Bruno Rémillard, a member of the PINTS team has been developing mathematical filters for classifying and tracking aircraft for Lockheed Martin Canada. Dr. Rémillard is working on new filters that are faster than existing filters because they require fewer calculations, yet are equally accurate. The military applications are not related to directing missiles but rather to improving the ability of computers to distinguish between military and civilian aircraft, and thereby reducing the potential for civilian casualties during conflicts.

According to Dr. Kouritzin, MITACS has sped up research at PINTS. "Being a member of a network of centres of excellence has made it easier to find corporate sponsors," Dr. Kouritzin explains. "Most mathematicians do not have much experience in approaching or dealing with corporations, and MITACS provides the necessary structure."

For more information please visit the MITACS Web site.

by Michael Rappaport