1. Field of the Invention
The present invention relates to the field of sonar signal processing and more particularly, to detecting the presence or absence of spatial random processes in physical phenomena.
2. Description of the Prior Art
In some cases, it can be important or critical to know with a high probability whether data received by a sonar system is simply random noise (which may be a false alarm) or is more likely due to the detection of a vessel of interest. In either situation, it is critical to make a determination as quickly as possible.
Naval sonar systems require that signals be categorized according to structure (i.e., periodic, transient, random or chaotic). A variety of large sample data processing methods such as spectral analysis, correlogram plots, and the like are available. However, a number of scenarios may also or only comprise small samples. These small samples include loss, or intermittent contact, transients, equipment failure, own ship maneuver, and the like. The existence of such sparse data sets requires methods that are appropriate for reliable and valid processing.
As such, there is a need for sparse data set methods in which the methods are separate from those methods which evaluate large sample distributions. It is well known in the art that large sample methods often fail when applied to small sample data sets.
The term “randomness” in regard to random noise has different meanings in science and engineering. Random (or randomness) is herein defined in terms of a “random process” as measured by a probability distribution model—namely a stochastic (Poisson) process. In naval engineering applications, waveform distributions in the time domain may be considered purely random if the distributions conform to a noise structure such as WGN (White Gaussian Noise). This determination is made regardless of the underlying generating mechanism that produced the “noise.”
Pure randomness may be considered a data distribution for which no mathematical function, relation, or mapping can be constructed that provides an insight into the underlying structure. For example: no prediction model can be generated from the noise/time waveform in order to derive estimates of a target range, course, speed, depth, etc. Also, one must distinguish the term “stochastic” randomness from “deterministic” randomness (chaos) as described in U.S. Pat. No. 5,781,460.
The theoretical and practical considerations relevant to the inventive process are contained in the following publications, which are incorporated herein by reference:
Abramowitz, Milton and Irene Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Washington, D.C. United States Government Printing Office: (1964).
Feller, William. Introduction to the Theory of Probability and Its Applications. 2nd ed. Vol. I., NY: John Wiley and Sons (1957).
Ruhkin, A. L. “Testing Randomness: A Suite of Statistical Procedures.” Theory of Probability and its Applications, Vol. 45, No. 1, pp. 111-132 (2000).
Preparata, Franco P. and Michael I. Shamos, Computational Geometry—An Introduction, Springer Verlag (1985).
Swed, F. S. and C. Eisenhart. “Tables for testing randomness of grouping in a sequence of alternatives.” The Annals of Mathematical Statistics, 14(1), pp. 66-87 (March 1943).
Wald, A. and J. Wolfowitz. “On a test whether two samples are from the same population.” The Annals of Mathematical Statistics, Vol. 11, pp 147-162 (1940)
Wilks, S. S. “Order statistics.” Bulletin of the American Mathematical Society. Volume 54, Number 1, Part 1, pp. 6-50 (1948).
The standard approach for assessing the hypothesis of spatial randomness for large samples is outlined in the known work on probability theory by W. Feller (Ch. 6, “The Binomial and Poisson Distributions”) [Feller, William. Introduction to the Theory of Probability and Its Applications. 2nd ed. Vol. I., NY: John Wiley and Sons. 1957].
Typically, from a frequency table derived from counts of spatial data in a partitioned subspace, a Chi-square test for homogeneity of Poisson frequency levels is computed and compared to a level of statistical certainty. The Feller reference (pp. 149-154), demonstrates the utility of this procedure for several large samples of naturalistic data analyzed in finite rectangular and circular space. The noted data sets include radioactive decay measurements, micro-organism distribution on a Petri dish, and others. However, the Feller reference provides little guidance on the matter of subspace partitioning including how many partitions should be used and what should be done about non-whole subset partitions.
Furthermore, most prior art randomness assessment methods are one time tests designed for one-dimensional or two-dimensional space. The methods are primarily applicable for truly random distributions. However, these quantitative techniques sometimes even fail to correctly label truly nonrandom distributions—as pointed out by Ruhkin (A. L. Ruhkin, “Testing Randomness: A Suite of Statistical Procedures”, Theory of Probability and its Applications, 2000, Vol. 45, No. 1, pp. 111-132).
The following United States patents significantly improve the above-noted situation.
U.S. Pat. No. 7,277,573 provides a multi-stage method for automatically characterizing data sets containing data points in which are each defined by measurements of three variables as either random or non-random. A three-dimensional Cartesian volume is sized to contain a total number N of data points in the data set which is to be characterized. The Cartesian volume is partitioned into equal-sized cubes, wherein each cube may or may not contain a data point. A predetermined route is defined that goes through every cube one time and scores each cube as a one or a zero; thereby, producing a stream of ones and zeros. The number of runs is counted and utilized to provide a Runs test which predicts if the N data points in any data set are random or non-random. Additional tests are used in conjunction with the Runs test to increase the accuracy of characterization of each data set as random or non-random.
U.S. Pat. No. 7,409,323 provides a method for automatically characterizing data sets containing data points, which may be produced by measurements such as with sonar arrays, as either random or non-random. The data points for each data set are located within a Cartesian space and a polygon envelope is constructed which contains the data points. The polygon is divided into grid cells by constructing a grid over the polygon. A prediction is then made as to how many grid cells would be occupied if the data were merely a random process. The prediction becomes one of two forms depending on the sample size. For small sample sizes, an exact Poisson probability method is utilized. For large sample sizes, an approximation to the exact Poisson probability is utilized. A third test is utilized to test whether the Poisson based model is adequate to assess the data set as either random or non-random.
As evidenced and in summary, the prior art does not disclose a method to provide a faster solution with greater reliability and for widely varying sizes of three-dimensional data sets. The solutions to the above-described and/or related problems have been long sought without success. Consequently, those skilled in the art will appreciate the present invention that addresses the above-described and other related problems.