Normalized bitmap representation of visual object's shape for search/query/filtering applications

• US 6,882,746 B1
• Filed: 02/01/2000
• Issued: 04/19/2005
• Est. Priority Date: 02/01/1999
• Status: Expired due to Fees

• Current Assignee: Gvbb Holdings SARL (Vislink Technologies, Inc.)
• Original Assignee: Thomson Licensing SA (Vantiva SA)
• Inventors: Murching, Anil M., Naveen, Thumpudi
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US09/495,597
• Time in Patent Office: 1,904 Days
• Field of Search: 382/293, 382/291, 382294-296, 382/305, 382173-180, 382155-161, 382/190, 707 3- 6, 707/104, 707/1
• US Class Current: 382/173
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 10/32 Normalisation of the pattern dimensions
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method of generating normalized bitmap representation for the shape of a visual object for use in search/query/filtering applications segments an image into visual objects. The samples belonging to a visual object of interest are identified. The identified samples that form the largest connected blob are reduced to an un-normalized bitmap. The un-normalized bitmap is then normalized using the mean and covariance of the valid samples to generate the normalized bitmap representation having a standard height and having an orientation such that a principal direction is along a vertical direction. The normalized bitmap representation may be used with a query to search a database of images where the visual objects all have associated normalized bitmap representations. The query bitmap is normalized and matched to each normalized bitmap representation. The visual objects having the lowest mismatch values of their normalized bitmap representation with the query bitmap are identified as the objects of the search.

Claims

1. A method of generating a normalized bitmap representation of the shape of a visual object in an image comprising the steps of:

segmenting the image to generate a segmentation map of visual objects;

identifying samples from the segmentation map belonging to a visual object of interest;

identifying the largest connected blob to form an un-normalized bitmap; and

normalizing the un-normalized bitmap to form a normalized bitmap representation, wherein said normalizing step additionally comprises the steps of;

estimating a mean and covariance for each valid sample in the un-normalized bitmap;

computing a principal direction for the un-normalized bitmap based upon the mean and covariance as eigenvectors of a covariance matrix; and

back projecting the un-normalized bitmap as a function of the mean and eigenvectors to normalize the un-normalized bitmap for translation, rotation and scale so that after normalization the normalized bitmap representation has a standard height and is oriented such that the principal direction is along a vertical direction.

2. The method as recited in claim 1 further comprising the step of searching a database of images, each image having associated visual objects with normalized bitmap representations, in response to a query specifying a desired normalized bitmap representation to identify a plurality of visual objects having normalized bitmap representations that closely match the desired normalized bitmap representation.

3. The method as recited in claim 2 wherein the searching step comprises the steps of:

providing a query bitmap seeking similarly shaped visual objects from the database;

normalizing the query bitmap;

obtaining various mirror versions of the normalized query bitmap;

for each normalized bitmap representation in the database compute a mismatch value with the normalized query bitmap; and

identifying the visual objects having normalized bitmap representations with low mismatch values.

4. The method as recited in claim 2 wherein the searching step comprises the steps of:

providing a query bitmap to find visual object in the database having a similar aspect ratio;

normalizing the query bitmap;

computing a query aspect ratio for the normalized query bitmap;

computing an aspect ratio for each normalized bitmap representation in the database;

obtaining an absolute difference between the aspect ratios for each normalized bitmap representation and the query aspect ratio; and

identifying the visual objects where the absolute difference has low values.

5. The method as recited in claim 2 wherein the searching step comprises the steps of:

providing a query bitmap to find visual objects with a similar density of valid samples;

computing a query density of valid samples for the query bitmap;

computing a density for each normalized bitmap representation in the database;

obtaining an absolute difference between the density for each normalized bitmap representation and the query density; and

identifying the visual object where the absolute difference is low.