METHOD AND SYSTEM FOR BUILDING A SUPPORT VECTOR MACHINE BINARY TREE FOR FAST OBJECT SEARCH

• US 20090254519A1
• Filed: 04/02/2008
• Published: 10/08/2009
• Est. Priority Date: 04/02/2008
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Ma, Yunqian
• Granted Patent: US 8,849,832 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/945 User interactive design; Environments; Toolboxes
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69
• CPC Class Codes: Y10S 707/914 Video
• CPC Class Codes: Y10S 707/915 Image

Abstract

Method and system for building a support vector machine binary tree for fast object search. An appearance model can be generated for objects in a database and computed on regions detected in an image frame. A covariance matrix can be utilized for representing the appearance model of the detected regions. The covariance matrix appearance model can be preprocessed and/or transferred into a vector-based format. The data in the vector-based format can be added with a class label to form labeled data. A support vector machine (SVM) can be utilized on the labeled data to generate a classifier with an optimal hyperplane and a margin area in order to hierarchically build a balanced SVM binary tree. A query appearance model can be searched rapidly utilizing the SVM binary tree during a search phase.

Claims

1. A computer-implemented method for configuring and providing a data binary tree for a fast object search, comprising:

computing at least one appearance model with respect to a plurality of detected regions in an object frame of an object stored in an object database containing a plurality of multidimensional data objects including said object, said at least one appearance model represented in a covariance matrix;

assigning a class label to said at least one appearance model in a vector-based format in order to form labeled data; and

utilizing a support vector machine with respect to said labeled data to generate a classifier with an optimal hyperplane and a particular margin in order to hierarchically construct a data binary tree for a fast object search thereof.

2. The computer-implemented method of claim 1 further comprising initially generating said at least one appearance model with respect to said plurality of multidimensional data objects contained in said object database

3. The computer-implemented method of claim 1 further comprising pre-processing said at least one appearance model in said covariance matrix into said vector-based format.

4. The computer-implemented method of claim 1 wherein said data binary tree comprises said support vector machine binary tree.

5. The computer-implemented method of claim 1 further comprising:

automatically searching a query appearance model in said object frame utilizing said data binary tree in accordance with said classifier and said particular margin, such that if a query point of said query appearance model falls within a particular margin, then, wherein said at least one appearance models and said query appearance model are indexed within said data binary tree.

6. The computer-implemented method of claim 5 wherein utilizing said binary tree in accordance with said classifier and said particular margin further comprises:

querying a left child and a right child of said binary tree in order to obtain a classification result, if a query point of said query appearance model falls within said particular margin; and

thereafter processing said left child if said classification result is positive or thereafter processing said right child if said classification result is negative.

7. The computer-implemented method of claim 1 wherein said object comprises an image contained within said object database and/or video data contained with said object database.

8. A system for configuring and providing a data binary tree for a fast object search, comprising:

a data bus coupled to said processor; and

a computer-usable medium embodying computer code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for;

computing at least one appearance model with respect to a plurality of detected regions in an object frame of an object stored in an object database containing a plurality of multidimensional data objects including said object, said at least one appearance model represented in a covariance matrix;

assigning a class label to said at least one appearance model in a vector-based format in order to form labeled data; and

utilizing a support vector machine with respect to said labeled data to generate a classifier with an optimal hyper-plane and a particular margin in order to hierarchically construct a data binary tree for a fast object search thereof.

9. The system of claim 8 wherein said instructions are further configured for initially generating said at least one appearance model with respect to said plurality of multidimensional data objects contained in said object database

10. The system of claim 8 wherein said instructions are further configured for pre-processing said at least one appearance model in said covariance matrix into said vector-based format.

11. The system of claim 8 wherein said data binary tree comprises said support vector machine binary tree.

12. The system of claim 8 wherein said instructions are further configured for automatically searching a query appearance model in said object frame utilizing said data binary tree in accordance with said classifier and said particular margin, wherein said at least one appearance models and said query appearance model are indexed within said data binary tree.

13. The system of claim 12 wherein utilizing said binary tree in accordance with said classifier and said particular margin further comprises:

querying a left child and a right child of said binary tree in order to obtain a classification result, if a query point of said query appearance model falls within said particular margin; and

thereafter processing said left child if said classification result is positive or thereafter processing said right child if said classification result is negative.

14. A computer-usable medium embodying computer program code, said computer program code comprising computer executable instructions configured for:

computing at least one appearance model with respect to a plurality of detected regions in an object frame of an object stored in an object database containing a plurality of multidimensional data objects including said object, said at least one appearance model represented in a covariance matrix;

assigning a class label to said at least one appearance model in a vector-based format in order to form labeled data; and

utilizing a support vector machine with respect to said labeled data to generate a classifier with an optimal hyper-plane and a particular margin in order to hierarchically construct a data binary tree for a fast object search thereof.

15. The computer-usable medium of claim 14, wherein said embodied computer program code further comprises computer executable instructions configured for initially generating said at least one appearance model with respect to said plurality of multidimensional data objects contained in said object database

16. The computer-usable medium of claim 14 wherein said embodied computer program code further comprises computer executable instructions configured for pre-processing said at least one appearance model in said covariance matrix into said vector-based format.

17. The computer-usable medium of claim 14 wherein said data binary tree comprises said support vector machine binary tree.

18. The computer-usable medium of claim 14, wherein said embodied computer program code further comprises computer executable instructions configured for automatically searching a query appearance model in said object frame utilizing said data binary tree in accordance with said classifier and said particular margin, wherein said at least one appearance models and said query appearance model are indexed within said data binary tree.

19. The computer-usable medium of claim 18 wherein utilizing said binary tree in accordance with said classifier and said particular margin further comprises:

querying a left child and a right child of said binary tree in order to obtain a classification result, if a query point of said query appearance model falls within said particular margin; and

thereafter processing said left child if said classification result is positive or thereafter processing said right child if said classification result is negative.

20. The computer-usable medium of claim 14 wherein said object comprises an image contained within said object database and/or video data contained within said object database.