Image clustering apparatus

• US 5,519,789 A
• Filed: 10/26/1993
• Issued: 05/21/1996
• Est. Priority Date: 11/04/1992
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Etoh, Minoru
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US08/141,073
• Time in Patent Office: 938 Days
• Field of Search: 382/9, 382/36, 382/39, 382/225, 382/228, 382/173
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

For determining class mean and covariance in class so as to make distribution parameters of pixels express statistical properties of the object, and for clustering the image stably at high speed, the apparatus has: (a) frame memory storing image composed of coded pixels, (b) reading device for reading out values of pixels randomly about horizontal and vertical positions from the frame memory, and generating a sample vector containing coupling of read out pixels values and corresponding horizontal and vertical position data, (c) memory for holding a plurality of sets of covariance matrix and mean vector of sample vector as class data, (d) likelihood calculating circuit calculating likelihood of sample vector to plural sets of class data as the distance between sample classes which is sum of a distance obtained by normalizing difference of sample vector and mean vector by covariance matrix, and a magnitude of covariance matrix, (e) maximum likelihood class selecting device selecting set minimizing distance between sample classes among combinations of class data, and (f) class data changing device sequentially changing mean vector and covariance matrix composing class data in direction of reducing distance between sample classes, by using difference vector of sample vector and mean vector.

Claims

1. An image clustering apparatus which changes sample class data representative of a selected sample class in response to reading of a new sample vector, the sample class data representative of the selected sample class including covariance matrix data and mean vector data, said apparatus changing the sample class data representative of the selected sample class to provide changed sample class data, said apparatus comprising:

(a) a frame memory for storing an image represented by coded pixels,

(b) reading means for reading out, from the frame memory, values associated with a pixel at a random horizontal and vertical position on the image, and generating a new sample vector that includes the read out values and horizontal and vertical position data corresponding to the pixel at the random position,

(c) a memory means for holding a plurality of sets of sample class data representing sample classes, the sample class data including covariance matrix data and mean vector data derived from sample vectors,

(d) likelihood calculating means for determining a likelihood that the new sample vector generated by said reading means is included in one of the plural sets of sample classes based on distances between the new sample vector and the sample classes, the distances each being a sum of;

a distance value obtained by determining a difference vector indicative of the difference between the new sample vector and the class data mean vector, and normalizing the difference vector by the covariance matrix, and the magnitude of the covariance matrix,

(e) maximum likelihood class selecting means for selecting a selected sample class from among the sample classes represented by the sample class data sets in said memory, the selected sample class having a minimum distance from the new sample vector, and

(f) class data changing means for changing the mean vector data and the covariance matrix data of the class data representative of the selected sample class to provide the changed sample class data for said sample data holding memory, said changing means providing the changed sample class data such that the distance between the selected sample class and the new sample vector is reduced by using the difference vector.

2. An image clustering apparatus comprising:

(a) a frame memory for storing an image represented by coded pixels,

(b) reading means for reading out, from the frame memory, values associated with a pixel at a random horizontal and vertical position on the image, and generating a new sample vector that includes the read out values and horizontal and vertical position data corresponding to the pixel at the random position,

(c) a memory for holding a plurality of sets of sample class data representing sample classes, the sample class data including covariance matrix data and mean vector data derived from sample vectors,

(d) likelihood calculating means for determining a likelihood that the new sample vector is included in one of the plural sets of sample classes based on distances between the new sample vector and the sample classes, the distances each being a sum of;

a distance value obtained by determining a difference vector indicative of the difference between the new sample vector and the class data mean vector, and normalizing the difference vector by the covariance matrix, and

the magnitude of the covariance matrix,

(e) maximum likelihood class selecting means for selecting a sample class with a minimum distance from the new sample vector from among the sample classes to provide a selected sample class,

(f) teaching means for determining whether the sample class selected by the maximum likelihood class selecting means is within a predetermined region within said image, and

(g) class data changing means for changing the mean vector and covariance matrix of the selected sample class after comparison with the new sample vector so as to reduce the distance between the selected sample class and the new sample vector, when the selected sample class is determined to be within the predetermined region by the teaching means, and

changing the mean vector and the covariance matrix of the selected sample class so as to increase the distance between the selected sample class and the new sample vector by using the difference vector, when the selected sample class is determined to be outside the predetermined region by the teaching means.

3. The image clustering apparatus as claimed in claim 2 further comprising:

a writing circuit for providing an indicator associated with said predetermined region;

a mask memory for storing an indicator received from said writing circuit; and

a reading circuit for reading an indicator stored in said mask memory and transmitting the indicator to the teaching means.