Method and system for building a support vector machine binary tree for fast object search

• US 8,849,832 B2
• Filed: 04/02/2008
• Issued: 09/30/2014
• Est. Priority Date: 04/02/2008
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Ma, Yunqian
• Primary Examiner(s): Shanmugasundaram, Kannan
• Application Number:
  US12/061,377
• Publication Number:
  US 20090254519A1
• Time in Patent Office: 2,372 Days
• Field of Search: 707/741, 707999001-999005, 707/769, 707/778, 707/797
• US Class Current: 707/741
• 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:

receiving an image frame from a video sensing device;

receiving image motion data from said image frame from an image motion processor;

computing at least one appearance model from said received image frame and said received image motion data, representative of an object within said image frame detected in a plurality of regions in said image frame wherein said object is stored in an object database containing a plurality of multidimensional data objects including said object, wherein said at least one appearance model is represented in a covariance matrix;

storing said appearance model in a database;

assigning a class label to said at least one appearance model in a vector-based format in order to form labeled data corresponding to each of said appearance models including an object index; and

utilizing a support vector machine with respect to said labeled data to generate a classifier with an optimal hyperplane and a particular margin; and

hierarchically constructing a data binary tree utilizing said labeled data for a fast object search thereof;

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, wherein said at least one appearance models and said query appearance model are indexed within said data binary tree;

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.

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 containing leaf nodes and at least one root node.

5. 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.

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

a data bus coupled to a processor; and

a compute-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;

receiving an image frame from a video sensing device;

receiving image motion data from said image frame from an image motion processor;

computing at least one appearance model from said received image frame and said received image motion data, representative of an object within said image frame detected in a plurality of regions in said image frame wherein said object is stored in an object database containing a plurality of multidimensional data objects including said object, wherein said at least one appearance model is represented in a covariance matrix;

storing said appearance model in a database;

assigning a class label to said at least one appearance model in a vector-based format in order to form labeled data corresponding to each of said appearance models including an object index;

utilizing a support vector machine with respect to said labeled data to generate a classifier with an optimal hyperplane and a particular margin; and

hierarchically constructing a data binary tree utilizing said labeled data for a fast object search thereof;

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;

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 system of claim 6 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.

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

9. The system of claim 6 wherein said data binary tree comprises said support vector machine binary tree containing leaf nodes and at least one root node.

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

receiving an image frame from a video sensing device;

receiving image motion data from said image frame from an image motion processor;

computing at least one appearance model from said received image frame and said received image motion data representative of an object within said image frame detected in a plurality of regions in said image frame wherein said object is stored in an object database containing a plurality of multidimensional data objects including said object, wherein said at least one appearance model is represented in a covariance matrix;

storing said appearance model in a database;

assigning a class label to said at least one appearance model in a vector-based format in order to form labeled data corresponding to each of said appearance models including an object index; and

utilizing a support vector machine with respect to said labeled data to generate a classifier with an optimal hyperplane and a particular margin; and

hierarchically constructing a data binary tree utilizing said labeled data for a fast object search thereof;

wherein said embodied computer program code further comprises computer executable instructions configured for automatically searching a query appearance model in said object frame utilizing 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;

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.

11. The computer-usable medium of claim 10, 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.

12. The computer-usable medium of claim 10 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.

13. The computer-usable medium of claim 10 wherein said data binary tree comprises said support vector machine binary tree containing leaf nodes and at least one root node.

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