Method and apparatus for data set classification based on generator features

• US 10,026,014 B2
• Filed: 10/26/2016
• Issued: 07/17/2018
• Est. Priority Date: 10/26/2016
• Status: Active Grant

• Current Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Inventors: Krutsch, Robert Cristian
• Primary Examiner(s): WOLDEMARIAM, AKLILU K
• Application Number:
  US15/334,920
• Publication Number:
  US 20180114094A1
• Time in Patent Office: 629 Days
• Field of Search: 382104, 382128, 382133, 382154, 382173, 382298
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• 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
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads

Abstract

A method including receiving, by an image classification engine, a number K of clusters to be created by a clustering algorithm. The method further including receiving, by the image classification engine, a set of elements based on an image, executing, by the image classification engine, the clustering algorithm on the set of elements to create K clusters, each cluster having a respective subset of the set of elements, for each cluster, computing, by the image classification engine, a centroid of the cluster, for each cluster, creating, by the image classification engine, a generator of the cluster based on the respective subset of the set of elements corresponding to each cluster, and for each element of each cluster, computing, by the image classification engine, a cost function corresponding to the element based on the centroid, the respective subset of the set of elements, and the generator corresponding to the cluster.

Claims

1. A method comprising:

receiving, by a circuit including an image classification engine, a number K of clusters to be created by a clustering algorithm;

receiving, by the circuit including the image classification engine, a set of elements based on an image;

executing, by the circuit including the image classification engine, the clustering algorithm on the set of elements to create K clusters, each cluster having a respective subset of the set of elements;

for each cluster, computing, by the circuit including the image classification engine, a centroid of the cluster, wherein computing the centroid of the cluster is based on one or more of a value selected from a group consisting of color values of pixels associated with each element of the respective subset of the set of elements of the cluster, position values of each element of the cluster within the image, a simple average of values associated with each element of the cluster, a center of mass of the respective subset of the set of elements of the cluster, and values learned from data associated with each element of the cluster;

for each cluster, creating, by the circuit including the image classification engine, a generator of the cluster based on the respective subset of the set of elements corresponding to each cluster; and

for each element of each cluster, computing, by the circuit including the image classification engine, a cost function corresponding to the element based on the centroid, the respective subset of the set of elements, and the generator corresponding to the cluster, wherein the cost function corresponding to the element is computed by;

Abs(I−

I0*Exp(IG)),

wherein I is the element, I0 is the centroid of the cluster, G is a multidimensional generator matrix corresponding to the generator, Exp( ) is a matrix exponential function, and Abs( ) is a matrix absolute value function.

2. The method of claim 1, further comprising:

computing, for each cluster of the K clusters, a feature based on each cost function corresponding to each element of the respective subset of the set of elements corresponding to the cluster.

3. The method of claim 1, further comprising:

for each cost function corresponding to each element of the respective subset of the set of elements corresponding to each cluster, in response to determining that the cost function exceeds a cost function threshold, increasing the number K of clusters to be created by the clustering algorithm and repeat the method.

4. The method of claim 1, wherein the feature corresponding to the cluster is computed by:

Sum(cost-function₁+ . . . +cost-function_N)²,

wherein cost-function₁, and cost-function_N are the 1^st and the N^th cost functions corresponding to the 1^st and the N^th elements of the N elements of the cluster, and Sum( )² is a matrix squared summation function that squares the sum of the N cost functions corresponding to the N elements of the cluster.

5. The method of claim 1, further comprising:

receiving, by the circuit including the image classification engine, a starting element indicating the element of the set of elements to be used at the start of the clustering algorithm.

6. The method of claim 1, wherein the generator of an associated cluster corresponds to a multidimensional generator matrix comprising characteristics learned from data associated with each element of the respective subset of the set of elements of the cluster including one or more of pixel values associated with the element, relationship values amongst the respective subset of the set of elements of the cluster, position values of the element within the image, and dimension values of the corresponding cluster.

7. The method of claim 1, wherein the clustering algorithm is one or more of a centroid based clustering algorithm, a k-means clustering algorithm, a hierarchical clustering algorithm, an expectation maximization algorithm, a dense model algorithm, a bi-clustering algorithm, a grouping algorithm, and a Lloyd'"'"'s clustering algorithm.

16. The method of claim 1, wherein executing the clustering algorithm is further based on a starting element indicating the element of the set of elements to be used at the start of the clustering algorithm.

8. A circuit including an image classification engine, the image classification engine comprising:

a clustering module, and a classifier module,

the circuit including the image classification engine to;

receive a number K of clusters to be created by a clustering algorithm of the clustering module;

receive a set of elements based on an image;

execute the clustering algorithm on the set of elements to create K clusters, each cluster having a respective subset of the set of elements;

for each cluster, execute a classifier algorithm of the classifier module to compute a centroid of the cluster, wherein computing the centroid of the cluster is based on one or more of a value selected from a group consisting of color values of pixels associated with each element of the respective subset of the set of elements of the cluster, position values of each element of the cluster within the image, a simple average of values associated with each element of the cluster, a center of mass of the respective subset of the set of elements of the cluster, and values learned from data associated with each element of the cluster;

for each cluster, execute the classifier algorithm to create a generator of the cluster based on the respective subset of the set of elements corresponding to each cluster; and

for each element of each cluster, execute the classifier algorithm to compute a cost function corresponding to the element based on the centroid, the respective subset of the set of elements, and the generator corresponding to the cluster, wherein the cost function corresponding to the element is computed by;

Abs(I−

I0*Exp(IG)),

wherein I is the element, I0 is the centroid of the cluster, G is a multidimensional generator matrix corresponding to the generator, Exp( ) is a matrix exponential function, and Abs( ) is a matrix absolute value function.

9. The circuit including the image classification engine of claim 8, further to:

for each cluster of the K clusters, execute the classifier algorithm to compute a feature based on each cost function corresponding to each element of the respective subset of the set of elements corresponding to the cluster.

10. The circuit including the image classification engine of claim 8, further to:

for each cost function corresponding to each element of the respective subset of the set of elements corresponding to each cluster, in response to determining that the cost function exceeds a cost function threshold, execute the classifier algorithm to increase the number K of clusters to be created by the clustering algorithm and repeat the execution of the clustering algorithm.

11. The circuit including the classification engine of claim 8, wherein the feature corresponding to the cluster is computed by:

Sum(cost-function₁+ . . . +cost-function_N)²,

wherein cost-function₁, and cost-function_N are the 1^st and the N^th cost functions corresponding to the 1^st and the N^th elements of the N elements of the cluster, and Sum( )² is a matrix squared summation function that squares the sum of the N cost functions corresponding to the N elements of the cluster.

12. The circuit including the image classification engine of claim 8, further to:

receive a starting element indicating the element of the set of elements to be used at the start of the clustering algorithm.

13. A method comprising:

executing, by a circuit including an image classification engine, a clustering algorithm on a set of elements based on an image to create a number K clusters, each cluster having a respective subset of the set of elements;

for each cluster, computing, by the circuit including the image classification engine, a centroid of the cluster, wherein computing the centroid of the cluster is based on one or more of a value selected from a group consisting of color values of pixels associated with each element of the respective subset of the set of elements of the cluster, position values of each element of the cluster within the image, a simple average of values associated with each element of the cluster, a center of mass of the respective subset of the set of elements of the cluster, and values learned from data associated with each element of the cluster;

for each cluster, creating, by the circuit including the image classification engine, a generator of the cluster based on the respective subset of the set of elements corresponding to each cluster;

for each element of each cluster, computing, by the circuit including the image classification engine, a cost function corresponding to the element based on the centroid, the respective subset of the set of elements, and the generator corresponding to the cluster; and

computing, for each cluster of the K clusters, a feature based on each cost function corresponding to each element of the respective subset of the set of elements corresponding to the cluster, wherein the cost function corresponding to the element is computed by;

Abs(I−

I0*Exp(IG)),

wherein I is the element, I0 is the centroid of the cluster, G is a multidimensional generator matrix corresponding to the generator, Exp( ) is a matrix exponential function, and Abs( ) is a matrix absolute value function.

14. The method of claim 13, further comprising:

for each cost function corresponding to each element of the respective subset of the set of elements corresponding to each cluster, in response to determining that the cost function exceeds a cost function threshold, increasing the number K of clusters to be created by the clustering algorithm and repeat the method.

15. The method of claim 13, wherein the feature corresponding to the cluster is computed by:

Sum(cost-function₁+ . . . +cost-function_N)²,

wherein cost-function₁, and cost-function_N are the 1^st and the N^th cost functions corresponding to the 1^st and the N^th elements of the N elements of the cluster, and Sum( )² is a matrix squared summation function that squares the sum of the N cost functions corresponding to the N elements of the cluster.