Method of tracking changes in a multi-dimensional data structure

• US 6,611,609 B1
• Filed: 11/08/1999
• Issued: 08/26/2003
• Est. Priority Date: 04/09/1999
• Status: Active Grant

• Current Assignee: Board of Regents of the University of Nebraska
• Original Assignee: Board of Regents of the University of Nebraska
• Inventors: Zhu, Qiuming
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/436,541
• Time in Patent Office: 1,387 Days
• Field of Search: 382/162, 382/254, 382/274, 382/103, 382/275, 382/288, 382/199, 382/289, 382/295, 382/297, 382/296, 382/298, 382/305, 348/169, 348/171, 348/172, 348/208.14, 348/582, 348/583, 345/589, 345/648, 345/649, 345/653, 345/672, 345/472
• US Class Current: 382/103
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06V 10/435 Computation of moments

Abstract

Disclosed is a method for pre-selecting pixels in data structures which demonstrate significant intensity and/or color gradients with respect to surrounding pixels, (tyically the result of depicted-object-edge-effects in the data structure), in “X” and/or “Y” and/or “Z” direction(s), and utilizing the pre-selected pixels in data structure characterizing spatial first and second central moment calculations, to the end that data structure characterizing vector(s) are constructed. Preferred characterizing vector(s) consist of typically orthogonally specific frequency integer counts of said pre-selected pixels, as well as spatial data structure first central monent value(s), and non-degenerate parameter(s) determined from Eigenvalues derived from second central moments, all spatially dependent values being calculated utilizing the pre-selected pixels with data structure intensity and/or color gradients in “X” and/or “Y” and/or “Z” direction(s), within one or more range(s). Also disclosed, in combination with the pixel pre-selection method, is methodology for enabling easy characterization, indexing, storage and retrieval of multi-dimensional data structures involving use of a translation, rotation and scaling invariant index which results from concatenating a series of Eigenvalue calculation mediated index elements determined at a plurality of hierarchical data depth levels.

Claims

1. A method of tracking changes in a multi-dimensional data structure comprising the steps of:

a. providing a first frame of a sequence of frames in a multi-dimensional data structure, each of said frames being comprised of pixels and with each of said pixels there being associated intensity and/or color(s);

b. defining at least three selected ranges of gradient(s) and defining pixel pre-selection technique gradient range selection criteria, then based on a selection from the group consisting of;

intensity gradiant;

color gradient; and

gradiant based on intensity and color;

 

determining pixels in said multi-dimensional data structure which demonstrate an intensity and/or color gradient within at least one of said at least three selected ranges of gradient(s); and

c. for each of said at least three ranges of gradients separately performing calculations on said pre-selection technique determined pixels to determine first and second central moment values and non-degenerate parameter(s) based upon said second central moment values, said first and second central moment values being based on spatial location distributions of said pixels identified by said pre-selection technique;

d. utilizing information from the separate calculations performed in three of said at least three ranges of gradients in step c. to form three points which are assigned as verticies of a triangle for said first frame of a sequence of frames in a multi-dimensional data structure comprising pixels;

e. providing a second frame of a sequence of frames in a multi-dimensional data structure, each of said frames being comprised of pixels and with each of said pixels there being associated intensity and/or color(s);

f. defining gradient range selection criteria the same as in step b. and utilizing an intensity and/or color gradient determining pre-selection technique which is the same as in step b. to determine pixels in said multi-dimensional data structure which demonstrate an intensity and/or color gradient within at least three of said at least three selected range of gradient(s), said at least three selected range of gradient(s) being the same as in step b.; and

g. for each of said at least three ranges of gradients separately performing calculations on said step f. pre-selection technique determined pixels to determine first and second central moment values and non-degenerate parameter(s) based upon said second central moment values, said first and second central moment values being based on spatial location distributions of said pixels identified by said pre-selection technique;

h. utilizing information from the separate calculations performed in said three ranges of gradients in step g. to form three points which are assigned as verticies of a triangle for said second frame of a sequence of frames in a multi-dimensional data structure comprising pixels; and

i. comparing the results of practice of steps d. and h. to determine translation, rotation and scaling of objects identified in said first and second sequential frames of said multi-dimensional data structure.