Labeled bunch graphs for image analysis

• US 6,356,659 B1
• Filed: 01/16/2001
• Issued: 03/12/2002
• Est. Priority Date: 06/25/1996
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Neven Vision, Inc. (Alphabet Inc.)
• Inventors: von der Malsburg, Christoph, Wiskott, Laurenz
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/760,685
• Time in Patent Office: 420 Days
• Field of Search: 382/118, 382/119, 382/161, 382/180, 382/181, 382/203, 382/209, 382/215, 382/216, 382/218, 382/219, 382/103, 382/115, 382/190, 382/195, 382/199, 382/243, 382/253, 382/276, 382/282, 382/285, 382/294, 382/305, 358/447, 358/448, 707/100, 707/102
• US Class Current: 382/209
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 10/449 Biologically inspired filters, e.g. difference of Gaussians [DoG] or Gabor filters
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181
• CPC Class Codes: G06V 40/171 Local features and components; Facial parts eye characteristics G06V40/18; Occluding parts, e.g. glasses; Geometrical relationships

Abstract

A process for image analysis which includes selecting a number M of images, forming a model graph from each of the number of images, such that each model has a number N of nodes, assembling the model graphs into a gallery, and mapping the gallery of model graphs into an associated bunch graph by using average distance vectors Δ_ij for the model graphs as edge vectors in the associated bunch graph. A number M of jets is associated with each node of the associated bunch graph, and at least one jet is labeled with an attribute characteristic of one of the number of images. An elastic graph matching procedure is performed wherein the graph similarity function is replaced by a bunch-similarity function.

Claims

1. A process for image analysis, comprising:

selecting a number M of images;

forming a model graph from each of the M images, such that each model graph has a number N of nodes and a plurality of distance vectors, each distance vector denoting a distance between two adjacent nodes of the model graph;

assembling the model graphs into a gallery; and

mapping the gallery of model graphs into an associated bunch graph having N nodes and a plurality of edge vectors, each edge vector denoting an average distance between two adjacent nodes of the bunch graph, the average distance being the average of the corresponding distance vectors of the M images.

2. The process of claim 1, further comprising

selecting a target image;

extracting an image graph from the target image;

comparing the target image graph to model graphs of the gallery to obtain a graph similarity, and

identifying a model graph having a greatest graph similarity with the image graph.

3. The process of claim 1, further comprising

selecting a target image

extracting an image graph from the target image;

comparing the target image graph to model graphs of the gallery to obtain a bunch similarity, and

identifying a model graph having a greatest bunch similarity with the image graph.

4. The process of claim 1, wherein the bunch graph is manually prepared by

placing a predetermined grid of nodes over an object in the image,

correcting individual node positions of the grid such that the node positions are located at designated sites corresponding to attribute characteristics of the object;

extracting jets at the nodes; and

assembling the jets into a structure associated with the bunch graph.

5. The process of claim 4, wherein the attribute characteristics are associated with facial features including the centers of the eyes and the corners of the mouth.

6. The process of claim 1, further comprising

selecting a target image

extracting an image graph from the target image;

comparing the target image graph to the bunch graph to obtain node similarities, and

generating pointers that are directed from the nodes of the image graph to the best-matching nodes in model graphs of the gallery.