Detection of Targets in Terrain Images with alisa




Yüklə 52.38 Kb.
tarix26.04.2016
ölçüsü52.38 Kb.
Detection of Targets in Terrain Images with ALISA
Peter Bock, James Hubshman, and Maral Achikian
The George Washington University, Washington DC

Research Institute for Applied Knowledge Processing (FAW), Ulm, Germany



Abstract


This paper describes an initial investigation of the ability of the ALISA image-processing engine to learn to detect anomalous artifacts in geographical terrain images. In general, ALISA is trained with a set of training images belonging to a single class, defined to be “normal”. Once trained, it is then asked to attempt to detect the presence of anomalous artifacts in otherwise normal images. In this investigation, ALISA was trained with three classes of terrain images, one for each of three background clutter levels: Low, Medium, and High. Once training had been completed for each class of background clutter, ALISA was presented with sets of test images of each class that also contained, such as tanks or trucks. Even though the training sets were very small, they proved sufficient to train ALISA to detect and discriminate the anomalous tanks with high statistical confidence.

Introduction


Collective Learning Systems Theory [1] has been applied to a difficult image-processing problem: the phase, translation, and scale-invariant detection, discrimination, and localization of anomalous features in otherwise normal images. Designed and implemented at the Research Institute for Applied Knowledge Processing (FAW) in Ulm, Germany, with funding by Robert Bosch GmbH, this image processing engine has been given the trademark ALISA, which stands for Adaptive Learning Image and Signal Analysis.*

This paper describes the use of ALISA to detect tanks and other vehicles in geographical terrain images. The images were captured with an 8mm video camera by Booz-Allen, Inc, under conditions specifically designed to test the ability of image processing systems to detect and locate tanks and other vehicles on desert terrains. However, the demonstration of the ability of a Collective Learning System to perform well in this task has important implications beyond the obvious defense applications. The ability to recognize the difference between an artifact and naturally occurring terrain features, such as rocks, sand dunes, and scrub vegetation, demonstrates a significant level of cognitive processing and is therefore of interest in a wide variety of application domains.



The ALISA Engine

Image processing using ALISA consists of three phases: the training phase, in which the spatial characteristics of normal images are learned; the control phase, in which unique images of the training class are evaluated to provide a statistical basis for subsequent tests; and the test phase, in which test images of are analyzed for the possible presence of abnormalities. [2, 3]

The input images for ALISA are rectangular arrays of 8-bit pixels. During its training phase, ALISA is presented with a sequence of normal images without anomalies belonging to a particular equivalence class. Examples of such classes in the geographical domain might include deserts, agricultural lands, mountain terrain, forests, river estuaries, cityscapes, and so forth. After being exposed to a sufficient number of training images, ALISA acquires a statistical hypothesis of the normal spatial features which characterize the image class. Note that it does this without using an a priori model of the class; it begins with no knowledge whatsoever and learns from experience.

When training is complete, on the basis of its learned hypothesis of normality for the particular class of images, ALISA may be presented with test images of arbitrary composition which have been intentionally or unintentionally corrupted with one or more anomalies, i.e., artifacts which are not expected in normal images of the learned class. The output of ALISA, then, is a spatial map indicating the normality, location, and geometry of these anomalies.

The logical architecture of ALISA is a three-layer network of non-learning cells and learning cells. As shown in Figure 1, each input image is processed simultaneously by a number of parallel channels, called ranks. The number of ranks used is a function of experimental requirements and hardware limitations, not the inherent design of ALISA. Multi-rank ALISA systems can be run on most major desktop systems. For more detailed information about the logical and physical design of ALISA, see the references listed at the end of the paper.

At each rank of the Analysis Layer, an image may be preprocessed using various spatial filters to produce the Transformed Image. After preprocessing, an Analysis Token is used to scan the Transformed Image horizontally and vertically in a fully overlapped manner, producing a stream of Analysis Patterns. A user-specified set of marginal features is then extracted from each Analysis Pattern. Currently available features including Gradient Direction, Gradient Magnitude, Average, Standard Deviation, Gradient Direction Activity, X-Position, Y-Position, Contrast, Hue, Saturation, and Intensity. These feature values are then transmitted to the corresponding rank in the Hypothesis Layer.

As each rank in the Hypothesis Layer receives the marginal feature values, it first reduces the dynamic range and the precision of these values as specified by a set of input parameters, and then concatenates the scaled and quantized results into a single feature vector. During training, each learning cell in the Hypothesis Layer accumulates statistical knowledge about the normality of all possible feature vectors by increasing a weight, called the Normality, for every encountered feature vector and decreasing the Normality for every feature vector not encountered. These weights are stored in its knowledge base, which is called the State Transition Matrix or STM. Currently available update policies use either the total number of occurrences of each feature vector in an image (Frequency Learning), or a single count per image if the feature vector occurred at all, regardless of the total number of occurrences (Discovery Learning). For both policies, infrequent occurrences of feature vectors produce low Normalities and are interpreted as abnormal, while frequent occurrences of feature vectors produce high Normalities and are interpreted as normal.

F
igure 1 -
The ALISA logical architecture

During testing, each rank of ALISA assembles the accumulated Normalities for all the feature vectors extracted from a test image and generates a Rank Hypothesis, which is an estimate of the Normality of the Transformed Image for the rank. ALISA then transmits all the Rank Hypotheses to the Synthesis Layer, where a single non-learning cell combines them into a single Super Hypothesis, a summarial estimate of the normality of the Original Image.

For display and analysis, Normalities are scaled into the range 0 to 255, where zero is completely abnormal, and 255 is completely normal. These values are mapped to colors or gray-scale levels, providing the user with visual representations of the Hypotheses, which are spatially isomorphic with the Original Images. By varying two display parameters, pmin and pmax, the user may adjust the dynamic range of the displayed Normalities. Note that these parameters do not effect the actual Normalities accumulated in the memories of the learning cells, but are for display and statistical analysis purposes only.

In summary, the input parameters for ALISA at each rank include the pre-processing filter coefficients (if any), the set of marginal features, the size of the Analysis Token, the precision and dynamic range of the components of the feature vector, and the update policy. The output display parameters include pmin and pmax.




Investigation


Objective

The objective of the investigation reported in this paper was to measure the ability of ALISA to detect, discriminate, and localize tanks or other vehicles in desert terrain images.


Definitions

In the interest of clarity, some basic definitions are needed. A background is a section of terrain with a constant clutter level, C. Clutter is a spatial distribution of “natural” objects in the image. The clutter level is an approximate categorical measure of the density of clutter within an image: C  {Low, Medium, High}. A target is an artifact, usually a vehicle, such as a truck or a tank. A background image is an image consisting entirely of a background at a particular clutter level. A target image is an image consisting of both a background and one or more targets. Figure 2 shows examples of three target images with backgrounds at all three clutter levels.

A training set is a set of background images with a constant clutter level. A control set is a set of background images of the same clutter level as the training set, but does not include any images used in the training set. A test set is a set of target images with the same clutter level as the training set.

F
igure 2
- Examples of target images representing all three background levels

Hypotheses

The null hypotheses for this investigation may be stated as follows:


H10: ALISA is not able to detect targets in test sets with low clutter.

H20: ALISA is not able to detect targets in test sets with medium clutter.

H30: ALISA is not able to detect targets in test sets with high clutter.
The statistical confidence with which each of these hypotheses may be rejected serves as a measure of the performance of ALISA with the terrain images.

Experiments


To validate these hypotheses, three formal experiments were designed to measure the ability of ALISA to detect and discriminate targets on backgrounds with the three different clutter levels.

Parameters and Factors

Informal initial analysis revealed that a single-rank ALISA engine was sufficient to accomplish the objective. Because of their dependency on absolute image structure attributes, the X-Position, Y-Position, Average, and Gradient Direction features were eliminated from consideration. For all the experiments, the postulated update policy was Frequency.


The parameters for these experiments included the following:
• the size of the Analysis Token

• the marginal features comprising the feature vector

• the dynamic range of each marginal feature

• the precision of the quantization of each marginal feature

• the display parameters, pmin and pmax
The most useful dynamic range for each marginal feature was obtained by analyzing their histograms for a wide range of Analysis Token sizes. For each Analysis Token size, the sub-range of non–zero counts in the histogram was used to define the useful dynamic range for the feature.

The specific combination of marginal features for a feature vector is critical to successful anomaly detection with ALISA. ALISA allows any number and any precision of any combination of features for its feature vector. However, it is generally desirable to as few features as possible with as little precision as possible to reduce the size of, and thus promote faster saturation of, the STM. On the other hand, if a feature is eliminated or if the precision of a feature is reduced, performance may degrade. Because these experiments were limited to very small training sets, this trade-off was an important consideration.

The value of each pixel in the Rank and Super Hypotheses indicates the Normality of the corresponding pixel in the Original Image. The display parameters pmin and pmax function as thresholds in the range {0, 1} that can be adjusted to force Normality values arbitrarily close to the maximum value (255) to be considered completely normal, and Normality values arbitrarily close to the minimum value (0) to be considered completely abnormal. As Pmax is decreased, a larger range of the highest Normality values will be considered completely normal; as pmin is increased, a larger range of the lowest Normality values will be considered completely abnormal. For instance, if pmax is set to 0.75, which corresponds to a Normality value of 180, all Normality values of 180 through 255 will be considered completely normal.

Gray levels (or colors) are used to represent the range of Normality values on the ALISA output display of its Rank and Super Hypotheses. Pure white indicates completely normal pixels (as specified by pmax); medium gray represents a mid-range or “unknown” Normality; and black indicates completely abnormal pixels (as specified by pmin).

To limit the number of factors for the formal experiments , a series of informal qualitative experiments was used to systematically search for useful ranges of the aforementioned parameters for the formal quantitative experiments described below. For each combination of parameters, ALISA was trained with a set of background images and then presented with a series of control and test images to determine the level to which ALISA had acquired the statistics of the background, yielding normal Rank and Super Hypotheses, and was able to localize the targets and discriminate them from the background.
Quantitative Experiments

The objective of the formal quantitative experiments was to measure the ability of ALISA to detect and discriminate targets against backgrounds with Low, Medium, and High Clutter. Table 1 lists the parameters for the three experiments, as determined by the preliminary analysis described above. Note that for the Low and Medium clutter experiments, only one feature was specified for an 8-bit feature vector. There were two reasons for this restriction: 1) the single feature does an excellent job of capturing the spatial characteristics of both the backgrounds and the targets, and 2) the extremely small number of training images available to the experimenters encouraged using as few input states as possible to guarantee sufficient saturation of the learning cell weights in the STM. If more training images were available, performance could probably be improved by using higher-precision feature vectors comprised of additional features. For the High Clutter experiment with 43 training images, two marginal features were used, specifying a 16-bit feature vector.



Table 1 - Experiment Parameters



Low Clutter Medium Clutter High Clutter

Training Set 29 images 25 images 43 images

Control Set 5 images 5 images 5 images

Test Set 10 images 11 images 11 images

Number of Ranks 1 1 1

Transformation none none none

Analysis Token 8x8 20x20 24x24

Learning Policy Frequency Linear Frequency Linear Frequency Linear

Marginal Feature 1 Pixel Activity Gradient Magnitude Pixel Activity

precision 8 bits 8 bits 8 bits

dynamic range 0 - 3% 0 - 18% 0 - 5%

Marginal Feature 2 Gradient Direction

precision 8 bits

dynamic range 0 - 1%

pmin / pmax 0 / 0.0000005 0 / 0.000001 0 / 0.000001

A separate experiment was run for each clutter level, the major factor of the experiments. The experiment procedure consisted of three phases: the Training Phase, the Control Phase, and the Test Phase. In the Training Phase, with learning enabled, ALISA was presented with the Training Set of images, from which it accumulated the statistics for the feature vector specified in Table 1. In the Control Phase, with learning was disabled, ALISA was presented with the Control Set of images to measure its statistical response to unique examples of the training class. Finally, in the Test Phase, with learning still disabled, ALISA was presented with the Test Set of images containing a variety of targets, and the response of ALISA to these targets was statistically compared with its response to the Control Set images.


Performance Metrics

Three different metrics were used to evaluate the results of the experiments: a summary metric to assess the ability of ALISA to detect targets across a sample of images (Sample Detection) [5], a transient metric to assess the ability of ALISA to detect targets in any single image (Unit Detection), and a transient metric to assess the ability of ALISA to discriminate a target from the background in the rest of the image (Discrimination). Each metric is based on a score derived from the results of the experiment.

The summary metric Sample Detection is a statistical comparison of the response of ALISA to a set of test images with its response to normal images. The score used for the Sample Detection metric is the Overall Average (OVA), which is the average of all the Normalities in a Super Hypothesis. The test set is detected if and only if the difference between the Test and Control Set scores is statistically significant.

The transient metric Unit Detection is a statistical comparison of the response of ALISA to an individual test image with its response to normal images. The score used for the Unit Detection metric is the Non-Normal Average (NNA), which is the average of only those Normalities in the Super Hypothesis that are less than 255 (absolutely normal). A test image is detected if and only if the NNA of the test image is greater than the mean NNA of the Control Set.

The transient metric Discrimination is a measure of how well ALISA recognizes that an anomalous region in a test image is less normal than the rest of the image. The score used for computing this metric is the Minimum Non–Normal (MNN), which is the minimum Normality in the Super Hypothesis. The anomaly is discriminated if and only if the MNN inside the anomalous region is less than the MNN outside the anomalous region. This single comparison provides a reasonable basis for measuring discrimination, because the associated pixel, whether inside or outside the anomalous region, will always survive a reasonable Normality threshold applied to the Hypothesis.


Results


Figure 3 illustrates three sample responses of ALISA to three typical test images. Note that even when only a small portion of a target is shown in the Original Image, as is the case in the high-clutter image, it is nonetheless strongly detected in the Super Hypothesis.





Figure 3 - Examples of target images and their corresponding Super Hypotheses

Figures 4, 5, and 6 report the Overall Average Normality (OVA) scores and Sample Detection metric values for the Low, Medium, and High Clutter Experiments. The raw scores used for computing the Unit Detection and Discrimination metrics are not shown. Table 2 summarizes the results for all three metrics.







Figure 4 - Low Clutter scores for Sample Detection




Figure 5 - Medium Clutter scores for Sample Detection




Figure 6 - High Clutter scores for Sample Detection

Table 2 - Summary of experiment results



Clutter Level Sample Detection Discrimination Unit Detection

Low 0.99+ 10 out of 10 10 out of 10

Medium 0.99+ 8 out of 11 9 out of 11

High 0.99 6 out of 11 11 out of 11

Validation of Hypotheses

The hypotheses for these three experiments are restated below:


H10: ALISA is not able to detect targets in test sets with low clutter.

H20: ALISA is not able to detect targets in test sets with medium clutter.

H30: ALISA is not able to detect targets in test sets with high clutter.
On the basis of the Sample Detection results shown in Table 2, all three hypotheses may be rejected with extremely high confidence. This implies that ALISA was able to consistently detect target images for all clutter levels. There is one important caveat, however. For the Medium Clutter case, two of the target images in the Test Set were simply not detected at all; the Super Hypothesis was completely normal (all white).

Except for the Low Clutter case, however, Discrimination and Unit Detection were not perfect. In fact, for the High Clutter case the Discrimination was quite poor. However, often this was caused by a large number of very small concentrations of pixels outside the target that were completely abnormal. In most cases, the application of a suitable spatial filter to these Super Hypotheses would cause these small concentrations to be smoothed into higher Normality values, but would still preserve the large abnormal concentration corresponding to the target itself. Moreover, the use of additional features and larger training sets would undoubtedly allow the structural detail of the High Clutter background terrain to be learned more completely, resulting in improved Discrimination.




Conclusions


After training the ALISA image processing engine with small sets of “normal” terrain images, it was presented with examples of images of the same class that also contained several types of vehicles, such as tanks and trucks. For the images with low and medium clutter levels, ALISA was able to detect and discriminate these vehicles with high confidence. For high clutter levels, ALISA detected the vehicles with high confidence, but exhibited poor discrimination.

It is important to note that the training images originally acquired for this experiment contained a mixture of different classes of background clutter, such as rocks, sand, trees, tracks, etc. Different images contained different amounts of each of these types of clutter. Because the total number of available images was so small, it was necessary to provide ALISA with more homogeneous training sets. Thus, the training images were sorted into three sub-classes, each with approximately the same amount of background clutter (Low, Medium, or High) and trained on each separately. However, although this separation of training images improved performance, it necessarily reduced the generality of the learned knowledge. If a larger number of training images were available, it is hypothesized that ALISA would be able to achieve acceptable detection and discrimination across all clutter levels.

It is also recommended that further investigations be performed to determine if including more marginal features in the feature vectors will improve performance. However, as mentioned previously, the more marginal features included in the feature vector, the larger the cardinality of the input domain, and therefore a larger number of training images will be required for saturation and convergence of the knowledge base in the STM.

Because it exhibits robust and high-speed detection of anomalies in gray-scale images, requires only a single pass through very small training sets, and is relatively insensitive to variation in its learning parameters, ALISA can function as a practical and powerful tool for inspection and quality-control tasks. For example, ALISA could be used to examine remote sensor images to locate unusual terrain signatures, check tolerances on printed circuit boards, detect incorrect spacing and orientation of mechanical parts, alert air traffic controllers when aircraft approach each other too closely, examine medical images for anomalies, or detect reproduction errors in printed graphics. Several such applications are currently being developed for the sponsor of the ALISA project, Robert Bosch GmbH, at the Research Institute for Applied Knowledge Processing (FAW) in Ulm, Germany.

Many potential applications do not involve images, per se. Although it is currently configured to process pixelated images, it is important to point out that ALISA is inherently a general-purpose signal processing engine. It does not know that the signals being presented to it are images. To map any kind of multi-dimensional signal into the input domain for ALISA is reasonably straightforward. This gives ALISA access to another extremely large domain of signal-processing applications, including real-time process control, voice recognition, and speech analysis.

ALISA has been recently enhanced to automatically recognize, classify, and assign semantic labels to normal and anomalous spatial and temporal structures.[7] This, in turn, leads quite naturally to a vertical extension of ALISA, using higher-level modules to combine the results from lower-level modules to learn a hierarchy of related symbolic concepts, such as “symmetry”, “proximity”, “obstacle”, and “danger”. Such concepts derive directly from the integration of learned associations among recognized and classified structures. It is just this potential which the forthcoming research phases of the ALISA project will attempt to realize. Over the coming years under the international joint sponsorship of the FAW, Robert Bosch, the University of Ulm, and The George Washington University, these new avenues of research and industrial application will be explored, directed toward significant enhancements and extensions of the fundamental capabilities of ALISA, continuing to provide conclusive evidence of the essential viability and utility of Collective Learning Systems Theory.



The authors would like to thank Booz-Allen, Inc for the video terrain images.

References


[1] P. Bock, The Emergence of Artificial Cognition: An Introduction to Collective Learning, World Scientific Publishing Company, River Edge NJ, 1993.
[2] P. Bock, G. Becker, H. Holz, C.J. Kocinski, R. Rovner, “An Application of Collective Learning Systems Theory to an Adaptive Learning Image Analysis System: Project ALIAS”, Proceedings of the International Workshop Neuro Nimes '89: Neural Networks and Their Applications, Nimes, France, November 1989.
[3] R. Klinnert, R. Kober, R. Rovner, H. Schmidt, and P. Bock, "Gray-Scale ALIAS", Special Issue of the IEEE Transactions on Knowledge and Data Engineering on Self-Organizing Knowledge and Data Representation in Distributed Environments, March 1992.
[4] P. Bock, H. Holz, R. Rovner, C.J. Kocinski, “An Initial Performance Evaluation of Unsupervised Learning with ALIAS”, Proceedings of the International Joint Conference on Neural Networks, San Diego, CA, June 1990.
[5] P. Bock, C.J. Kocinski, R. Rovner, “A Performance Evaluation of ALIAS for the Detection of Geometric Anomalies on Fractal Images”, Advanced Neural Computers, pps 237-246, Elsevier North-Holland, The Netherlands, July 1990.
[6] R. Kober, C. Howard, and P. Bock, “Anomaly Detection in Video Images”, Proceedings of the Fifth Neuro-Nimes Conference: Neural Networks and their Applications, Nimes, France, November 1992.
[7] R. Rovner, “Multi-Class Classification with ALIAS”, FAW technical report.

* The ALISA image-processing engine is patented under US and international law by Robert Bosch GmbH and is distributed exclusively in North America by The ALIAS Corporation of Alexandria, Virginia, USA.



Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə