Apparatus and method for classifying feature data at a high speed

• US 5,142,593 A
• Filed: 05/01/1991
• Issued: 08/25/1992
• Est. Priority Date: 06/16/1986
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Kasano, Akira
• Primary Examiner(s): COUSO, JOSE L
• Application Number:
  US07/696,269
• Time in Patent Office: 482 Days
• Field of Search: 382/1, 382/18, 382/36, 382/39, 382/51, 358/30, 358/75, 364/526
• US Class Current: 382/170
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries

Abstract

In a feature data processing apparatus, one of two designated reference density vectors di and dj, to which a feature vector x corresponding to a feature element is closer, is determined from dij of the equation:

dij=(di-dj)·x-(di-dj)/2

This value is calculated for all the combinations of two reference feature vectors di and dj selected from a reference feature vector group dk (k=0 to n-1), thereby obtaining classification data. The classification data is determined, using a logical formula or a reference table. An average value of the components is calculated from the classification data and the components of all the feature vectors. The above operation is repeated until the calculated average and the components of the reference density vector converge within a predetermined allowance, thereby precisely classifying feature data.

Claims

1. A method for classifying a plurality of feature data elements into a plurality of classes, each feature data element being represented by an object feature vector in a feature space, comprising the steps of:

storing a plurality of reference feature vectors in a memory, each reference feature vector being predetermined;

dividing said feature space into a plurality of partial feature spaces using said plurality of reference feature vectors in response to a classification command, each partial feature space corresponding to one class of said plurality of classes, each object feature vector being assigned to one of said plurality of partial feature spaces in accordance with components of each object feature vector utilizing the sign of a single polynomial equation to determine which of two reference feature vectors is closer to each object feature vector;

determining an average feature vector from object feature vectors for every partial feature space; and

storing each average feature vector as a reference feature vector in said memory and repeating said dividing and assigning step until each average feature vector falls within a predetermined error.

2. A method according to claim 1, wherein said determining step comprises the steps of:

executing histogram operations for every component of assigned object feature vectors; and

calculting said average feature vector using equation (1) from calculated histogram operation results;

##EQU3## where Aqk represents a component along a q axis of said average feature vector of class k, q equals 1 to p, p is a positive integer representing a dimension of each object feature vector, Nk represents a number of object feature vectors classified into class k, m represents a feature amount of one component of each object feature vector, each object feature vector is represented by u-bit data, u is a positive integer, and hgk(m) represents a histogram along said q axis of said average feature vector of class k.

3. A method according to claim 1, wherein said dividing step includes dividing said feature space into said plurality of partial feature spaces by an equidistant plane between two reference feature vectors.

4. A method according to claim 1, wherein said dividing step comprises the steps of:

determining a plurality of assignment data for each object feature vector in response to said classification command, each assignment data comprising a plurality of assignment data portions, each assignment data portion representing which of two reference feature vectors, selected as a combination from said plurality of reference feature vectors, is closer to said object feature vector; and

assigning each object feature vector to one of said plurality of partial feature spaces in accordance with assignment data associated with a corresponding object feature vector.

5. A method according to claim 4, wherein said determining said plurality of assignment data step comprises the steps of:

selecting a select object feature vector of said plurality of object feature vectors;

obtaining assignment data associated with said select object feature vector for all combinations of two of said reference feature vectors; and

executing said selecting step and said obtaining step for all remaining object feature vectors.

6. A method according to claim 4, wherein said determining said plurality of assignment data step comprises the steps of:

selecting a selected combination of two reference feature vectors from said plurality of reference feature vectors;

obtaining an assignment data portion associated with said selected combination for all object feature vectors; and

executing said selecting step and said obtaining step for all remaining combinations.

7. A method according to claim 4, wherein said determining said plurality of assignment data step includes determining assignment data for all object feature vectors with respect to combinations of two arbitrarily selected from said plurality of reference feature vectors except for combinations selected in response to said classification command.

8. A method according to claim 4, wherein said determining said plurality of assignment data step includes:

calculating dij using equation (2),

space="preserve" listing-type="equation">dij=(di-dj){x-(di+dj)/2} (2)

where di and dj are two reference feature vectors, and x is said object feature vector; and

determining an assignment data portion for a combination of said two reference feature vectors in accordance with dij.

9. A method according to claim 4, wherein said assigning step comprises the steps of:

referring to a first table in accordance with assignment data to obtain classification data; and

classifying said object feature vector into one of said plurality of partial feature spaces in accordance with said classification data.

10. A method according to claim 1, wherein said dividing step comprises the steps of:

determining an assignment data portion for one object feature vector in response to said classification command, said assignment data portion representing which of two reference feature vectors, selected as a combination from said plurality of reference feature vectors, is closer to said object feature vector;

assigning said object feature vector to one of said plurality of partial feature spaces in accordance with said assignment data portion; and

repeating said determining said assignment data portion step and said assigning step until all combinations are completed or until a last partial feature space of said plurality of partial feature spaces is assigned to said object feature vector.

11. A method according to claim 10, wherein said determining said assignment data portion step includes determining assignment data for all object feature vectors with respect to combinations of two arbitrarily selected from said plurality of reference feature vectors except for combinations selected in response to said classification command.

12. A method according to claim 10, wherein said determining said assignment data portion step includes:

calculating dij using equation (3),

space="preserve" listing-type="equation">dij=(di-dj){x-(di+dj)/2} (3)

where di and dj are two reference feature vectors and x is said object feature vector; and

determining said assignment data portion for a combination of said two reference feature vectors in accordance with dij.

13. A method according to claim 10, wherein said assigning step comprises the steps of:

determining current classification data in accordance with previous classification data and said assignment data portion;

classifying said object feature vector into one of said plurality of partial feature spaces in accordance with said current classification data; and

holding said current classification data as said previous classification data.

14. A method according to claim 13, wherein said determining current classification data step includes:

referring to a second table in accordance with said previous classification data and said assignment data portion to obtain said current classification data.

15. A feature data processing apparatus for classifying object feature vectors representing feature data elements into classes, said feature data processing apparatus comprising:

first memory means for storing a plurality of reference feature vectors which are predetermined;

second memory means for storing said object feature vectors;

assignment data determining means for determining assignment data for each of said object feature vectors in response to an input classification command, said assignment data including a plurality of assignment data portions, each assignment data portion indicating which of two reference feature vectors, selected from said plurality of reference feature vectors, is closer to each of said object feature vectors based on the sign of a single polynomial equation;

classifying means for classifying said object feature vectors into one of said classes in accordance with assignment data associated with said object feature vectors, said classes respectively corresponding to said reference feature vectors; and

average feature vector determining means for determining an average feature vector of object feature vectors of every class.

16. An apparatus according to claim 15, wherein said assignment data determining means comprises:

selecting means for selecting a selected object feature vector from said object feature vectors;

obtaining means for obtaining assignment data associated with said selected object feature vector for all combinations of two of said reference feature vectors; and

executing means for causing said selecting means and said obtaining means to operate on all object feature vectors.

17. An apparatus according to claim 15, wherein said assignment data determining means comprises:

selecting means for selecting a selected combination from combinations of two of said reference feature vectors;

obtaining means for obtaining an assignment data portion associated with said selected combination for all object feature vectors; and

executing means for causing said selecting means and said obtaining means to operate on all of said combinations.

18. An apparatus according to claim 15, wherein said assignment data determining means includes means for determining assignment data for each object feature vector with respect to combinations of two reference feature vectors arbitrarily selected from said plurality of reference feature vectors except for combinations selected in response to said classification command.

19. An apparatus according to claim 15, wherein said classifying means comprises means for classifying each object feature vector in accordance with a contents of predetermined portions of said assignment data of said corresponding object feature vector.

20. An apparatus according to claim 15, wherein said classifying means comprises:

reading means for reading a read-out content of an assignment data portion of said corresponding object feature vector;

determining means for determining a current class in accordance with said read-out content and a previous class;

means for repeatedly causing said reading means to operate on a next assignment data portion and said determining means to operate on said current class as said previous class until all contents of said assignment data portions are read-out or until said current class is a last class.

21. An apparatus according to claim 15, wherein said average feature vector determining means comprises:

histogram operation means for executing histogram operations for every component of classified object feature vectors of every class; and

calculating means for calculating said average feature vector using equation (1) from calculated histogram operation results;

##EQU4## where Aqk represents a component along a q axis of said average feature vector of class k, q equals 1 to p, p is a positive integer representing a dimension of each object feature vector, Nk represents a number of object feature vectors classified into class k, m represents a feature amount of one component of each object feature vector, each object feature vector is represented by u-bit data, u is a positive integer, and hgk(m) represents a histogram along said q axis of said average feature vector of class k.

22. An apparatus according to claim 15, wherein said assignment data determining means includes:

means for calculating dij using equation (2),

space="preserve" listing-type="equation">dij=(di-dj){x-(di+dj)/2} (2)

where di and dj are said two reference feature vectors, and x is an object feature vector; and

means for determining said assignment data portion for a combination of said two reference feature vectors in accordance with dij.

23. A method for classifying an object feature vector representing feature data, comprising the steps of:

storing a reference feature vector group including a plurality of reference feature vectors in a memory, each reference feature vector being predetermined;

determining assignment data of said object feature vector for combinations of two reference feature vectors sequentially selected from said memory in response to a classification command to obtain classification data in accordance with said assignment data, said assignment data including a plurality assignment data portions which indicate which of said two reference feature vectors of each combination is closer to said object feature vector based on the sign of a single polynomial equation; and

assigning said object feature vector to one of a plurality of categories in accordance with said classification data.

24. A method according to claim 23, wherein said determining assignment data step includes:

calculating dij using equation (1),

space="preserve" listing-type="equation">dij=(di-dj){x-(di+dj)/2} (1)

where di and dj are said two reference feature vectors selected from said reference feature vector group, and x is said object feature vector; and

determining said assignment data portions for a combination of said two reference feature vectors in accordance with dij.

25. A method according to claim 23, wherein said determining assignment data step comprises the steps of:

selecting a selected combination of two reference feature vectors from said reference feature vector group;

obtaining an assignment data portion associated with said selected combination for all of a plurality of object feature vectors; and

executing said selecting step and said obtaining step for all remaining combinations.

26. A method according to claim 25, wherein said selecting step selects all combinations of two reference feature vectors from said reference feature vector group except for combinations which have already been selected.

27. A method according to claim 23, wherein obtaining classification data includes:

referring to a first table in accordance with said assignment data to obtain said classification data.

28. A method according to claim 23, wherein obtaining classification data comprises the steps of:

determining a current assignment data portion;

determining current classification data in accordance with previous classification data and said current assignment data portion;

holding said current classification data as said previous classification data; and

repeating said determining said current assignment data portion, said determining current classification data, and said holding step until all combinations are completed or until a last class classes is assigned to said object feature vector.

29. A method according to claim 28, wherein said determining current classification data includes:

referring to a second table in accordance with said previous classification data and said assignment data portion to obtain said current classification data.