Image analysis – Pattern recognition – Classification
Reexamination Certificate
1993-12-28
2001-10-16
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Classification
C382S209000
Reexamination Certificate
active
06304675
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to pattern recognition and multivariate analysis, and in particular to a method and a template used for data clustering which simulates the human visual system.
Clustering analysis is a technique used to explore the relationships between data and assess the interaction among data by organizing the data into groups or clusters. Data within a cluster are more similar to each other than are data belonging to other clusters. Jain, A. K., Chapter 2,
Cluster Analysis
from
Handbook of Pattern Recognition and Image Processing,
Academic Press, Inc., pp. 33-57, (1986). Clustering analysis can be used when no prior knowledge regarding the presence or number of such patterns is available. Cluster analysis has applications in machine vision, pattern recognition, unsupervised and supervised machine learning/classification, medical and biological image and data analysis, crop identification from satellite photos, identification of hazardous chemicals in complex environments.
Pattern recognition uses an existing set of training data which have identified groupings or classes and assigns a grouping to newly measured test data. Specific examples of pattern recognition applications include: recognition of a large set of chemicals using a small set of chemical sensor signals; distinguishing vegetation, water, buildings, mineral deposits, etc. in multispectral satellite images; distinguishing different tissue types in medical magnetic resonance imaging data; target recognition in radar images; threat detection and false alarm avoidance in automated intrusion detection in video surveillance images.
Clustering has been broadly classified into the hierarchical and the partitional approaches. The hierarchical structure also has two models, one of which begins with n clusters, one per pattern, and grows a sequence of clusterings until all n patterns are in a single cluster; this approach is referred to as agglomerative. The other hierarchical model, the divisive approach, begins with one cluster containing all n patterns and successively divides clusters until n clusters are achieved. Partitional clustering techniques organize patterns into small numbers of clusters by labeling each pattern in some way, and make use of criterion functions, density estimators, graphs structure and nearest neighbors. Fuzzy partitional clustering deals with the overlapping case in which each pattern is allowed to belong to several classes with a measure of “belongingness” or a weighting factor for each class.
Some present clustering analysis techniques require prior knowledge or assumptions concerning, for example, the mean and location of the cluster pattern, and the cluster result, especially the number of clusters present in the data set. The available clustering systems may also require pattern-dependent adjustments. An example of a hierarchical clustering analysis technique which requires additional input is U.S. Pat. No. 4,937,747 entitled “Iterative Disjoint Cluster and Discriminant Function Processing of Formation Log Responses and Other Data” to Koller and U.S. Pat. No. 5,012,675 entitled “Integrating Multiple Mappable Variables for Oil and Gas Exploration” to Koller et al. These Koller patents require additional information about subsurface structures and use disjoint clustering which requires specifying the number of clusters into which the data set are to be classified, and then uses discriminant function analysis wherein data of one cluster may be assigned to another cluster. U.S. Pat. No. 5,060,277 entitled “Pattern Classification Means using Feature Vector Regions Preconstructed from Reference Data” to Bokser is a partitional clustering technique which requires a priori knowledge about the classification and then generates feature vectors of word processing font data and then compares with references for appropriate classifying into ringed clusters. U.S. Pat. No. 4,991,092 entitled “Image Processor for Enhancing Contrast between Subregions of a Region of Interest” to Greensite generates a distribution density function of a signal which is assigned to a region of interest, then after convolution of the distribution density function, the variance is compared and assigns a particular value to a pixel of the image corresponding to the region of interest.
Clustering has been recognized as an important component of the human visual system since the Gestalt principles were first discussed in Wertheimer, M., “Laws of organization in perceptual form,” translated into English in
A Source Book of Gestalt Psychology
(W. Ellis, ed.), pp. 71-88 (1938). Despite many studies in subsequent decades, a quantitative understanding of perceptual grouping/clustering has not been achieved for the human visual system. Achieving human-like performance has been a long standing goal of clustering research but the results of existing clustering analysis techniques often disagree with human visual judgments, even for remarkably simple data patterns. Jain, A. K. and Dubes, R. C.,
Algorithms for Clustering Data,
Prentice Hall (1988); Duda, R. O. and Hart, P. E.,
Pattern Classification and Scene Analysis,
John Wiley (1973); Hand, D. J.,
Discrimination and Classification,
John Wiley (1981); and Jain, supra in
Cluster Analysis
all describe many of these approaches. Prior art pattern recognition techniques also do not provide a well-defined warning when a class assignment of a point is uncertain. This is unlike human perception which readily notices points which cannot be unambiguously assigned to one class of the training data. U.S. Pat. No. 5,040,133 entitled “Adaptive Clusterer” to Feintuch et al. attempts to approximate human vision of gestalts by taking any two points and generating a parameter proportional to the distance between the points, and then taking all points within that parameter as being within the cluster. Although Feintuch's system does not require a priori knowledge about the clusters or the number of clusters, it does not in fact adequately approximate human vision. See also Jain, A. K., “Cluster Analysis” in
Handbook of Pattern Recognition and Image Processing,
Academic Press, 1986; and Zahn, C. T., “Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters,” C-20 IEEE TRANS. COMPUTERS 68 (1971).
Another drawback of some existing techniques is the computational time required to compute clusters or class assignments. Computational time becomes important for applications such as image analysis, where large numbers of data points, typically >10
5
, are examined.
Some clustering techniques use a region of influence or template to determine clusterings between each pair of data points. A template area of fixed shape is examined around each pair of points in the data, and the pair is grouped together if no other data points occur within the template area. If other data points do occur in the template area, they are referred to as inhibitor points below. Successful regions of influence must cover an appropriately large and appropriately located area to avoid extra grouping errors while simultaneously being small enough to avoid the onset of missed grouping errors. A number of template shapes have been examined and are shown in
FIG. 21
, but none produce clusters in agreement with human perception. See Toussaint, G. T.,
The Relative Neighborhood Graph of a Finite Planar Set,
12 PATTERN RECOGNITION 261 (1980); Urquhart, R.,
Graph Theoretical Clustering Based on Limited Neighborhood Sets,
15 PATT. RECOGNITION 173 (1982); Krivanek, M.
The Use of Graphs of Elliptic Influence in Visual Hierarchical Clustering,
452 LECTURE NOTES IN COMPUTER SCIENCE 392 (1990). Moreover, the methods of cluster analysis using these templates require computations that scale as N
3
, where N is the number of data points.
It is thus an object of the invention to provide a clustering template and method that achieves human-like judgment of class membership for n-dimensional test points. The feature of the invention, the psychophysical-derived inhibitor
Martinez Rubel Francisco
Osbourn Gordon Cecil
Chang Jon
Ojanen Karuno
Ortiz Luis
Sandia Corporation
LandOfFree
Visual cluster analysis and pattern recognition methods does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Visual cluster analysis and pattern recognition methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Visual cluster analysis and pattern recognition methods will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2594013