Labeled bunch graphs for image analysis

• US 6,222,939 B1
• Filed: 06/25/1997
• Issued: 04/24/2001
• 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 H.
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US08/882,223
• Time in Patent Office: 1,399 Days
• Field of Search: 382/118, 382/119, 382/203, 382/209, 382/215, 382/216, 382/218, 382/219, 382/278, 382/190, 382/180, 382/181, 348/161
• 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 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, such that ${\mathrm{\Delta <br><br>}}_{\mathrm{ij}}=\frac{1}{M}<br><br>\underset{m}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\Delta <br><br>}}_{\mathrm{ij}}^m$

where Δ

_ij^m is a distance vector between nodes i and j in model graph m.

2. The process of claim 1, wherein a number M of jets is associated with each node of the associated bunch graph, and further comprising labeling at least one jet with an attribute characteristic of one of the number of images.

3. The process of claim 1, wherein forming a model graph from each of the number of images comprises

associating a standard grid of points over an image;

correcting node positions to fall over designated sites characteristic of the image; and

extracting jets at the nodes.

4. 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 gallery of model graphs to obtain a graph similarity function S such that $S<br><br>\left(G^M,G^I\right)=\frac{1}{N}<br><br>\underset{n}{\sum <br><br>}<br><br>S<br><br>\left(J_n^M,J_n^I\right)-\frac{\mathrm{\lambda <br><br>}}{E}<br><br>\underset{e}{\sum <br><br>}<br><br>{\left(\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\stackrel{\to <br><br>}{x}}_e^M-\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\stackrel{\to <br><br>}{x}}_e^I\right)}^2;<br><br>$

where G^M is a model graph of the gallery of model graphs G^I is the image graph of the target image, n is the number of jet coefficients. J_n^M are the jets of the model graph, J_n^I are the jets of the image graph, Δ

{overscore (x)}_e^M are distance vectors in the model graph, Δ

{overscore (x)}_e^I are distance vectors in the image graph, and

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

5. The process of claim 4, further comprising performing an elastic graph matching procedure, wherein the graph similarity function is replaced by a bunch-similarity function S such that $S$

(G,GI)=1N

∑

n

maxm

S

(Jnm,JnI).

6. The process of claim 1, wherein a number M of jets is associated with each node of the associated bunch graph, and jets that are attached to an associated node in the model graphs encode a similar qualitative region of objects in the model graphs.

7. The process of claim 6, wherein objects in the model graphs include human faces and the nodes are associated with facial features.

8. The process of claim 7, wherein the nodes are associated with facial features including eyes, nose, and mouth.