APPARATUS AND METHOD FOR EFFICIENT INDEXING AND QUERYING OF IMAGES IN SECURITY SYSTEMS AND OTHER SYSTEMS

• US 20100040296A1
• Filed: 08/15/2008
• Published: 02/18/2010
• Est. Priority Date: 08/15/2008
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Cohen, Isaac, Ma, Yunqian
• Granted Patent: US 8,107,740 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06F 18/2136 based on sparsity criteria, e.g. with an overcomplete basis
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06V 10/762 using clustering, e.g. of similar faces in social networks

Abstract

A method includes receiving one or more query images and identifying multiple features associated with an object or an activity using the one or more query images. The method also includes accessing a sparse representation index using the identified features. The sparse representation index includes a multi-dimensional polytope having multiple vertices, and the features identify a point in the polytope. The method further includes identifying multiple vertices in the sparse representation index that are associated with the identified point and providing one or more images associated with the identified vertices. In addition, the method includes identifying one or more clusters of features associated with the identified vertices and providing one or more additional images associated with the one or more identified clusters. The one or more clusters may be identified using a clustering index identifying the clusters and features of training images associated with the clusters.

Claims

1. A method comprising:

receiving one or more query images;

identifying multiple features associated with an object or an activity using the one or more query images;

accessing a sparse representation index using the identified features, the sparse representation index comprising a multi-dimensional polytope having multiple vertices, the features identifying a point in the polytope;

identifying multiple vertices in the sparse representation index that are associated with the identified point;

providing one or more images associated with the identified vertices;

identifying one or more clusters of features associated with the identified vertices; and

providing one or more additional images associated with the one or more identified clusters.

2. The method of claim 1, wherein:

the vertices of the multi-dimensional polytope are associated with features of training images; and

the identified features represent a combination of the features associated with the identified vertices.

3. The method of claim 1, wherein:

the vertices of the polytope define multiple areas; and

identifying the multiple vertices in the sparse representation index comprises identifying the vertices defining the area in which the point resides.

4. The method of claim 1, wherein identifying the one or more clusters comprises using a clustering index identifying the clusters and features of training images associated with the clusters.

5. The method of claim 1, wherein:

providing the one or more images comprises presenting the one or more images to an operator; and

providing the one or more additional images comprises providing the one or more additional images in response to a request for more images from the operator.

6. The method of claim 1, further comprising:

generating the sparse representation index; and

generating a clustering index associated with multiple clusters of features.

7. The method of claim 6, wherein generating the sparse representation index comprises:

identifying multiple features associated with multiple objects or multiple activities using training samples; and

performing an L¹-norm minimization of y=Ax_o, where x₀=[0, . . . ,0,α

_i,1,α

_i,2, . . . ,α

_i,ni,0, . . . ,0]^T and denotes a coefficient vector, α

_i,1 through α

_i,n denote non-zero entries in the coefficient vector associated with an i^th class of training samples, and A represents a concatenation of all training samples from all classes.

8. The method of claim 6, wherein generating the clustering index comprises:

forming an initial set of clusters, each containing at least one image; and

iteratively merging two closest clusters defined using average linkage until a specified number of clusters is obtained.

9. The method of claim 1, wherein receiving the one or more query images comprises receiving a sequence of temporally ordered query images.

10. An apparatus comprising:

at least one memory configured to store images; and

at least one processor configured to;

identify multiple features associated with multiple objects or multiple activities using the images;

generate sparse data representations of the identified features; and

generate a sparse representation index using the sparse data representations, the sparse representation index comprising a multi-dimensional polytope having multiple vertices, the vertices associated with the sparse data representations.

11. The apparatus of claim 10, wherein the at least one processor is configured to generate the sparse data representations by performing an L¹-norm minimization of y=Ax_o, where x₀=[0, . . . ,0,α

_i,1,α

_i,2, . . . ,0, . . . 0]^T and denotes a coefficient vector, α

_i,1 through α

_i,n denote non-zero entries in the coefficient vector associated with an i^th class of training samples in the images, and A represents a concatenation of all training samples from all classes

12. The apparatus of claim 10, wherein the at least one processor is further configured to group the images into multiple clusters.

13. The apparatus of claim 12, wherein the at least one processor is configured to group the images into multiple clusters by:

forming an initial set of clusters, each containing at least one image; and

iteratively merging two closest clusters defined using average linkage until a specified number of clusters is obtained.

14. The apparatus of claim 12, wherein the at least one processor is further configured to:

receive one or more query images;

identify multiple features associated with an object or an activity using the one or more query images;

access the sparse representation index using the identified features;

identify multiple vertices in the sparse representation index that are associated with the identified point; and

provide one or more images associated with the identified vertices.

15. The apparatus of claim 14, wherein the at least one processor is further configured to:

identify one or more of the clusters associated with the identified vertices; and

provide one or more additional images associated with the one or more clusters.

16. A computer readable medium embodying a computer program, the computer program comprising:

computer readable program code for identifying multiple features associated with an activity using one or more query images;

computer readable program code for accessing a sparse representation index using the identified features, the sparse representation index comprising a multi-dimensional polytope having multiple vertices, the features identifying a point in the polytope;

computer readable program code for identifying multiple vertices in the sparse representation index that are associated with the identified point; and

computer readable program code for providing one or more images associated with the identified vertices.

17. The computer readable medium of claim 16, wherein the computer program further comprises:

computer readable program code for identifying one or more clusters of images associated with the identified vertices; and

computer readable program code for providing one or more additional images associated with the one or more identified clusters.

18. The computer readable medium of claim 17, wherein the computer program further comprises:

computer readable program code for generating the sparse representation index; and

computer readable program code for generating a clustering index associated with multiple clusters of features.

19. The computer readable medium of claim 18, wherein the computer readable program code for generating the sparse representation index comprises:

computer readable program code for identifying multiple features associated with multiple objects or multiple activities using training samples; and

computer readable program code for performing an L¹-norm minimization of y=Ax_o, where x₀=[0, . . . ,0,α

_i,1,α

_i,2, . . . ,α

_i,ni,0, . . . ,0]^T and denotes a coefficient vector, α

_i,1 through α

_i,n denote non-zero entries in the coefficient vector associated with an i^th class of training samples, and A represents a concatenation of all training samples from all classes.

20. The computer readable medium of claim 18, wherein the computer readable program code for generating the clustering index comprises:

computer readable program code for forming an initial set of clusters, each containing at least one image; and

computer readable program code for iteratively merging two closest clusters defined using average linkage until a specified number of clusters is obtained.