Image analysis – Pattern recognition – Classification
Reexamination Certificate
1999-01-20
2001-08-07
Boudreau, Leo (Department: 2721)
Image analysis
Pattern recognition
Classification
C382S155000, C382S159000, C382S162000, C382S165000, C382S224000
Reexamination Certificate
active
06272250
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method and apparatus for clustering color data in video sequences, and more particularly to color clustering methods for detecting video sequence scene changes and color clustering methods for tracking objects in a video sequence.
Conventional methods for clustering color data of an image are based on block truncation and vector quantization. Block truncation of image data is a coding process in which significant visual features are retained while other data is discarded. Vector quantization is a process for mapping a sequence of vectors into a digital sequence suitable for communication over a digital channel and for storage on a digital media. In a typical block truncation implementation an image is divided iteratively to achieve an optimal number of component subimages. Classification criterion is used to truncate the data within a window. Each color class within a window is represented by a corresponding mean color vector. A linear vector quantizer determines a mapping of the subimage pixels.
Another method for clustering data is found in pattern learning and recognition systems based upon adaptive resonance theory (ART). Adaptive resonance theory, as coined by Grossberg, is a system for self-organizing stable pattern recognition codes in real-time data in response to arbitrary sequences of input patterns. (See “Adaptive Pattern Classification and Universal Recoding: II . . . ,” by Stephen Grossberg, Biological Cybernetics 23, pp. 187-202 (1976)). It is based on the problem of discovering, learning and recognizing invariant properties of a data set, and is somewhat analogous to the human processes of perception and cognition. The invariant properties, called recognition codes, emerge in human perception through an individual's interaction with the environment. When these recognition codes emerge spontaneously, as in human perception, the process is said to be self-organizing.
It is desirable that neural networks implementing adaptive resonance theory be capable of self-organizing, self-stabilizing and self-scaling the recognition codes in response to temporal sequences of arbitrary, many-input patterns of varying complexity. A system implementing adaptive resonance theory generates recognition codes in response to a series of environmental inputs. As learning proceeds, interactions between the inputs and the system generate new steady states and basins of attraction. These steady states are formed as the system discovers and learns critical feature patterns that represent invariants of the set of all experienced input patterns. This ability is referred to as plasticity. The learned codes are dynamically buffered against relentless recoding due to irrelevant inputs. The buffering process suppresses possible sources of instability.
Adaptive Resonance Theory-1 (‘ART 1’) networks implement a set of differential equations responsive to arbitrary sequences of binary input patterns. Adaptive Resonance Theory-2 (‘ART 2’) networks self-organize stable recognition categories in response to arbitrary sequences of not only binary, but also analog (gray-scale, continuous-valued) input patterns. See “ART 2: Self-Organization of Stable Category Recognition Codes for Analog Input Patterns,” by Gail A. Carpenter and Stephen Grossberg. To handle arbitrary sequences of analog input patterns, ART 2 architectures employ a stability-plasticity tradeoff, a search-direct access tradeoff and a match-reset tradeoff. Top down learning expectation and matching mechanisms are significant features in self-stabilizing the code learning process. A parallel search scheme updates itself adaptively as the learning process unfolds. After learning stabilizes, the search process is disengaged. Thereafter input patterns directly access their recognition codes without any search. A novel input pattern can directly access a category if it shares invariant properties with a set of exemplars of that category. A parameter called an attentive vigilance parameter determines how fine the categories are to be. If vigilance decreases due to environmental feedback, then the system automatically searches for and learns finer recognition categories. If vigilance increases due to environmental feedback, then the system automatically searches for and learns coarser recognition categories.
An ART-2 network is modified to achieve an inventive clustering and pattern recognition system of this invention.
SUMMARY OF THE INVENTION
According to the invention, a set of pixel data forming an input image is clustered into groups of data of similar color. All pixels of approximately the same color are grouped into one cluster. A vigilance parameter determines how many clusters are derived and how wide a range of colors are included in a cluster.
In a sequence of image frames a given frame corresponds to a data set. One member of the set is a data point. A data point, for example, corresponds to a pixel and is coded using RGB, YUV or another known or standard color coding scheme. Each data point is an input vector. The input vectors are grouped into clusters. A given cluster has a corresponding centroid value, referred to herein as a prototype vector. The prototype vector corresponds to a weighted centroid (color) for such cluster.
The process for allocating input vectors into clusters is based upon a minimum distance measure. An input vector is allocated to the cluster having a prototype vector to which the input vector is closest (i.e., minimal distance from the cluster's prototype vector). As a self-organizing control for allocating data into clusters, a vigilance parameter, also referred to herein as a vigilance value, is used. If the minimum euclidean distance is not less than the vigilance value, then a new cluster is defined. The input vector is the initial prototype vector for such new cluster. Thus, an input vector is allocated to a pre-existing cluster or a new cluster.
A given image frame is allocated into clusters in an iterative process. According to one aspect of this invention, after any given iteration the number of input vectors in each resulting cluster is tested. If there are less than a threshold number of input vectors in a cluster, then such cluster is discarded. More specifically, the prototype vector for such cluster is discarded. During a subsequent iteration for allocating input vectors of the same image frame, the remaining prototype vectors from the prior iteration are the initial prototype vectors. The input vectors are compared to each of these remaining prototype vectors to find the one prototype vector to which is closest (e.g., minimum euclidean distance between input vector and prototype vector; this corresponds physically to the closest color). It is expected that the input vectors in the discarded cluster from the preceding iteration will be allocated among the old or into one or more new clusters in the next iteration.
According to another aspect of this invention, self-stabilizing of the clustering process is achieved by testing if the number of input vectors in each cluster after an iteration has changed by an insignificant amount. If only an insignificant change has occurred, then the iterative process is complete, because clustering has stabilized for such image frame. Otherwise another iteration, up to a prescribed maximum number of iterations, is performed.
According to another aspect of the invention, the final prototype vectors for a given image frame are used as the initial prototype vectors for the next image frame in a sequence of image frames.
According to another aspect of the invention, a first vigilance value is used for allocating input vectors of an initial image frame, while a higher vigilance value is used for allocating input vectors of subsequent image frames in a related sequence of image frames.
According to another aspect of this invention, a select subset of clusters from an initial image frame are treated as featured clusters. The featured clusters correspond to one or more objects within the initial image fra
Kim Yongmin
Sun Shijun
Boudreau Leo
Koda Steven P.
Mariam Daniel G.
University of Washington
LandOfFree
Color clustering for scene change detection and object... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Color clustering for scene change detection and object..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Color clustering for scene change detection and object... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2451273