Contents and Figures for Adaptive Algorithms for Over-the-Horizon Radar-Data Processing

by Allen Klinger

Sections Page

A. 2

Title, Period of Performance, Cost of Effort, Name of Company

B. 2

Task Objective

C 2

Technical Summary 2

Historic Information 3

Bayesian Learning 4

Selective Adaptation 5

Operator Alerts 5

Data Collection 8

Facility 8

Personnel 8

Bibliography and References 9

Resume of Allen Klinger 10

Figures Page

Figure 1. Outgoing Radar Beam Path Via Ionosphere (NOAA) 6

Figure 2. Range Azimuth Radar Bins 7

Section A:

Title Adaptive Algorithms for Over-the-Horizon Radar-Data Processing

Period of Performance 1 November 1997 to 31 October 1998

Cost of Effort $ 75,000

Name of Company Space Computer Corporation

Section B:

Task Objective A Training Set for Over-the-Horizon Radar Data

Section C:

Technical Summary

This paper describes dealing with irregular radar-returns from over-the-horizon radar used in imaging sea-surface regions. The computer data processing described here adapts proven research tools into effective ways to to detect and track small boats smuggling illicit drugs into the United States. The basis of that effort is to combine algorithms for clutter-suppression and tracking with novel approaches that utilize adaptation to current data, incorporate recent history, and enable application of operator judgement to guide computing.

The data processing uses generalized Bayesian learning algorithms. That approach enables developing a model to describe the current-sea clutter-map in combination with recent radar returns from boat targets. The model is used to create updates: maps to best include a radar energy return with the past information. These computations are probability-based. They employ prior off-line computations thus enabling high-speed real-time operational decisions. Following processing to convert received radar returns to correspond to two-dimensional range/azimuth bins, we produce a probability field from the Bayesian-learning model. Algorithmic analysis of the probability field characteristics leads to options relevant to tracking and clutter-see-through that afford new capabilities to a human operator.

Where past outcomes show that human operators have successfully judged a multitude of clues to determine a future target track or to distinguish a boat-return from clutter we will process the information to enable a parallel system to be trained to learn from examples. That is, we will develop a learning database for future development of neural network algorithms and other methods that employ parallel computing. We will investigate a wide range of the time and space features. We will

undertake computations that update Bayesian learning algorithms. These computations will be

coupled to algorithms that address both the features and the current probability field characteristics. These algorithms will highlight domains where there is a substantial probability of a boat target. When the operator confirms the presence of a target the actual values of the members of the large feature set will be recorded. Thus actual probability field data will be recorded with the most-significant feature elements that locate ocean-going targets.

Whether an algorithm is imperative or adaptive, whether it is stand-alone or interactive, and whether it relies on neural network or genetic models, we believe that the key to successful interdiction using over-the-horizon radar data is to allow operator input regarding the most-likely track locations. The following sections, Historic Information, Bayesian Learning, Selective Adaptation, and Operator Alerts describe ways to aid an operator, or to allow a computer, to focus directly, or by learning algorithms, on key regions. These sections describe fundamental aspects of the overall program of applying adaptive algorithms. Our goal is enhancement of the value of over-the-horizon radar data through the task objective, creating a training set to enable adaptive algorithms to thoroughly use the received radar information.

Historic Information

We begin with the assumption that the usual state sensed by raw radar data (returns) is a cluttered-image with or without an actual target. Sea clutter and ionospheric-propagation-path variability generate an ongoing need for a maintenance-level data analysis activity. When a boat is located, prediction and tracking depend on effective use of previous knowledge. When no target is found, processing must focus on suspect regions to ensure that penetration has not occurred. This is best done by operator control guiding the parallel computations.

The two forms of data are the ambient or general-background level and returns containing detected targets. The former involves long term averages for regions being illuminated by over-the-horizon radar. The situation is complicated by the propagation variations, essentially the tendency for change in the radar outward-bound and returning-information paths to differ due to ionosphere height fluctuations: see illustration in Figure 1 [9] as well as Figure 24.1 of [1, 2] . These variations mean that there may be many target situations. Hence operator action [3] (i.e.,

narrowing a field of interest, focus on one feature), and general clustering [4], will associate groups of confirmed targets within the data processed in this project.

Data collection and creation of a historic record is an initial task that will support future algorithmic processes we will undertake. That effort consists of developing a reliable time-dependent database of radar returns. For ease of focus on the algorithms this is shown via range-azimuth bins, but there are a wide range of possibilities. From [1, pp. 1.11-1.13] these include: range, radial velocity, angular direction, size, shape, and other target measurements (temporal doppler frequency shift leading to radial velocity, spatial doppler frequency shift producing tangential or cross-range velocity). The result is that we will be equally-able to consider signal-oriented historical data, whether characterized by yielding range or doppler values. In either instance data processing deals with something more akin to the actual radar return: see e.g., Figs. 24.27 a-c on pp. 24.36-24.37 of [1, 2].

We expect to construct display tools that utilize contemporary computer algorithms and enable thoughtful analysis of the historic data in support of the goal of estimating the probability field. A direct way to display multiple-measures by parallel coordinates - see [3] - was the basis of IBM reports to the FAA. This is one of several approaches to display of complex data that are investigated in the statistical research literature. Likewise research in pattern analysis involving clustering of features in two-alternative situations (target/no-target) [4] will be the basis of new algorithms for over-the-horizon radar data. The project has the central goal of establishing a dataset to use to train adaptive algorithms.

Bayesian Learning

This section describes how utilization of historic data for computations involving probability can begin with off-line analysis. The approach is due to Bayes, sometimes known as Bayes' Theorem, and is a central topic in pattern analysis/recognition decision-making, where it yields Bayes' Decision Rule. The method is also at the heart of several advanced areas of computer research. These include efforts that led to commercial products: computer programs devised to learn medical-drug efficacy, and others that took geologists' general information about locating mineral resources and combined them with satellite imagery to locate valuable deposits. The same technology has been the basis of successful computer-products that screen loan applicants at banks, examine credit card histories, and find relative risk for insurance companies. The past success at transfer of theoretic research to practical product leads us to examine the application of Bayes' Rule to radar data.

The radar approach employs as a central idea Bayesian learning: application of Bayes' Theorem and spatial relationships between data elements. The purpose is to update past radar data that has been transformed into sequences of range-azimuth images to obtain a current probability-field indicating likelihood a boat target will soon appear in different locations. Figure 2 shows a radar data range-azimuth display. This corresponds to a form of image information that for computations involves a data structure stored as a two-dimensional array R with rows indexed by i and columns indexed by j. Rows correspond to the range-bins; columns to angle/azimuth intervals.

We will convert each R-array element R[ i, j ] into a probability that a boat appears at the corresponding physical location. We will assume it possible to calculate this probability by comparing several related factors. They include: 1) the pattern of reflected radar energy in the immediate neighbors of the range-azimuth cell being considered; 2) radar reflection pattern prototypes of small boats; 3) sea clutter patterns. The methods for evaluating these R-array elements use straightforward computational processes based on Bayes' Rule and local topology.

While this phase is purely development, it is based both on cooperation with operational personnel and on application of well-established pattern recognition theory. The following describes how these items are applied to our task objective..

Over time the radar produces a sequence of images. The corresponding array data will be snapshots of the probability field that governs whether a certain range-azimuth intensity value corresponds to electromagnetic energy from a boat target or not. If i and j are the row and column indices, at time

t the Rt [ i, j] will give rise to pij( x, t) , the probability of an observed radar return signal x at

time t being an indicator of a boat target at location i, j . As a new radar return is received it can be taken as an instantaneously-accurate portrait of reality or one member of the image sequence. Bayesian learning assumes that the second is the proper interpretation: it gives weight to prior values. This is the preferable mode since the over-the-horizon radar return generally reflects off the ionosphere twice, and since variability in its height introduces inaccuracies in individual data streams as implied by Figure 1.

We will allow operator control to input prior boat paths, current tracking information, and sea clutter state. This information will be combined with automatic computations of possible future locations of detected boats based on past siting, direction of motion, and probable speed.

Bayes' rule updating will enable calculation of values of pij( xf | xp, t) : here the subscripts f denotes future ( p denotes past) radar-return values. These calculations will assume normal distribution for historic records of probability-field array-elements pij( x, t) .

Selective Adaptation

This section describes ways to apply parallel programming to enhance likelihood of target detection.

Awareness of potential penetration threat will be automatically found by algorithms that examine Bayesian-updated probability fields. This will be based on probability measures aggregated over regions. We will assume there is a heightened possibility of small boat breaking through the coastal defenses when four or nine neighboring cells have an average probability of 0.8 of a boat target being present. Alternatively, whenever a track has been established we will calculate the probability averages for all six-element linear zones and apply the 0.8 threshold. Exceeding the threshold enables initiating neural network or genetic algorithm parallel programming computations tied to the region and its immediate neighbors.

In general, the area of selective adaptation comprises the central long-term objective of this effort. It is closely related to another phase of the work involving a human-decision maker.

Operator Alerts

Ultimately this effort could have the effect of enabling greater target-locating success by operators. To cause this we plan to devise new displays so a human can cause an adaptive algorithm to focus on a region. We will take advantage of the current computer solid-modeling language best suited to the presentation of imagery involving multiple-dimensions, OpenGL[8] in the human-machine interface aspects of this project. The work will present a far richer display than in [10] where only colors encode different ground motion image values, and the overall situation is presented in a two-dimensional plot.

Radar Illumination of Ocean Surface

Figure 1. Outgoing Radar Beam Path Via Ionosphere (NOAA)

Data Collection

The amount of data collection required in terms of an approximate number of days/hours is ten days, where half that time is concentrated in the field and the remainder is two hours per week for twenty weeks (approximately every other week).

Facility

The intended facility is the company headquarters:

Space Computer Corporation

2800 Olympic Boulevard, Suite 104

Santa Monica, California 90404-4119

Personnel

Allen Klinger, Ph.D. is an Emeritus Professor of Engineering and Applied Science at UCLA where he teaches courses in Pattern Analysis and Machine Intelligence in the Computer Science Department, School of Engineering and Applied Science, and a part-time employee of Space Computer Corporation.

William. Kendall, Ph.D. is a co-founder and principal of Space Computer Corporation.

Alan Stocker, Ph.D. is an employee of Space Computer Corporation.

Eskandar Ensafi is a graduate student in the UCLA Department of Biomathematics and a part-time employee of Space Computer Corporation.

Frank Zee is a graduate student in the UCLA Computer Science Department and an employee of the Jet Propulsion Laboratory who will contribute his services to the project at no cost.

Wei Wang is a graduate student in the UCLA Computer Science Department.

Shervin Farivar is an undergraduate student in the UCLA Computer Science Department.

Bibliography and References

[1] Skolnik, M., ed. Radar Handbook, Second Edition, NY: McGraw-Hill, 1990.

[2] Headrick, J., "HF Over-The-Horizon Radar," Ch. 24 of Skolnik, M., ed. op. cit.

[3] Klinger, A., ed., Human-Machine Interactive Systems, NY: Plenum Press, 1991.

[4] Lin, J-C, and Tsai, W-H, "Feature-Preserving Clustering of 2-D Data for Two-Class Problems Using Analytical Formulas: An Automatic and Fast Approach," IEEE Transactions on Pattern Analysis and Machine Intelligence, May 1994.

[5] Klinger, A. and Pizano, A., "Visual Structure and Data Bases," Visual Database Systems,

Kunii, T. L., ed., NY: North Holland, 3-25, 1989; also see Pizano, A., Klinger, A., and Cardenas, A.,"Specification of Spatial Integrity Constraints in Pictorial Databases,"

IEEE Computer, 22, Dec. 1989: pp. 59 - 71.

[6] Paul, J., Kilgore, T.E., and Klinger, A., "New Algorithms for Automated Symmetry Recognition," Intelligent Robots and Computer Vision, Proceedings of SPIE - The International Society for Optical Engineering, Volume 848, Bellingham Washington, 1987.

[7] Baraghimian, G.A., and Klinger, A., "Space and Time Requirements for Two Image Data Structures," Proceedings of SPIE - The International Society for Optical Engineering, 1002, Intelligent Robots and Computer Vision, 1988, pp. 514-523; and "Preference Voting For Sensor Fusion," Proceedings of SPIE - The International Society for Optical Engineering, 1306, Aerospace Sensing, 1990, Sensor Fusion III, pp. 46 - 57.

[8] Neider, J., Davis, T., Woo, M., OpenGL, NY: Addison-Wesley, 1993.

[9] National Oceanic and Atmospheric Administration (NOAA) over-the-horizon radar world-wide-web page http://www1.etl.noaa.gov/othr/othmain.htm.

[10] Jet Propulsion Laboratory (JPL) earthquake fault and ground-motion location world-wide-web page http://www-aig.jpl.nasa.gov/mls/quakefinder/.

Allen Klinger

12515 Rosy Circle

Los Angeles, California 90066-6926

voice: 310 825-7695; fax: 825-7578;

web address http://www.cs.ucla.edu/csd/faculty/klinger.html; email <klinger@cs.ucla.edu>

EDUCATION - ACADEMIC INFORMATION

Ph.D., University of California, Berkeley, California.

M.S., California Institute of Technology, Pasadena, California; Teaching Assistant.

B.E.E., The Cooper Union, New York City.

Professor, University of California, Los Angeles; previously Assistant/Associate Professor.

HONORS - PROFESSIONAL ACTIVITY

Fellow, Institute of Electronics and Electrical Engineers. "... image analysis by computer." Tau Beta Pi, Eta Kappa Nu. New York State and Caltech graduate-tuition scholar. Fulbright Fellow, India.. Editorial Board, International. Journal Artificial Intelligence Tools. Reviewer, Mathematical Reviews, IEEE Transactions on Software Engineering, Computer Vision and Image Understanding. Committee chair and editor, "Soviet Image Pattern Recognition Research," Science Applications International Corporation. Consultant, image pattern analysis, Los Angeles Unified School District, Gateways Hospital and Long Beach Memorial Hospital.

SELECTED PUBLICATIONS

"Data Structures for Gigabyte Systems," Proceedings of SPIE -The International Society of Optical Engineering, Aerospace Sensing, 1995, SPIE. 2410, 66-76.

"Data Structures", Encyclopedia of Physical Science and Technology, Volume 5, 43-56, New York: Academic Press, 1992.

Klinger, A. ed., Human Machine Interactive Systems, New York: Plenum Press, 1991.

Klinger, A., "Recent Advances in Syntactic Pattern Recognition," Bhatkar, V., Rege, K. eds., Frontiers in Knowledge-based Computing, New Delhi: Vedams Books Int'l, 1991.

Tanimoto, S., Klinger, A. eds., Structured Computer Vision, NY: Academic Press, 1980.

Klinger, A., Fu, K., Kunii, T. eds., Data Structures, Computer Graphics and Pattern Recognition, NY : Academic Press, 1977.