Method and apparatus for relating and combining multiple sets of data that describe related domains

INVENTORS:
Thomas Chiang, Schaumburg, IL
Elizabetta Koenig, Destiny IL

ASSIGNEE:
Sigma Corporation, Destiny IL

ISSUED: Jan. 6 , 1998
FILED: Nov. 13, 1995
APPL NUMBER: 558012

INTL. CLASS (Ed. 6): G06F 015/00
U.S. CLASS: 395/127
FIELD OF SEARCH: 395-127,121,130,135,136,133

REFERENCES CITED

9060171 Newbury et al. 10 /1990
A system and method for superimposing data sets     
9185808 Aramburu 2 /1995     
Method for merging data sets     
9271097 Barthus et al. 12 /1992     
Method and system for controlling the presentation of nested overlays utilizing data set area mixing attributes    
9398309 Chen et al.     3 /1997    
Method and apparatus for generating composite data sets using multiple local masks    
9594850 Grieg et al.     1 /1996     
Data set simulation method    
PRIMARY EXAMINER: Phu K. Nguyen
ASSISTANT EXAMINER: Cliff N. Vo
ATTORNEY, AGENT, or FIRM: Hecker & Harriman

ABSTRACT: Digitally encoded data sets having common subject matter are spatially related to one another and combined utilizing a projective coordinate transformation, the parameters of which are estimated featurelessly. For a given input data set frame, the universe of possible changes in each data set point consistent with the projective coordinate transformation is defined and used to find the projective-transformation parameters which, when applied to the input data set, make it look most like a target data set. The projective model correctly relates data sets of common (static) subject matter with complicated planar records (including translation or other movements of the center of projection itself).

BACKGROUND OF THE INVENTION
SUMMARY OF THE INVENTION
DETAILED DESCRIPTION OF THE INVENTION
[All of the foregoing are available by fax or messenger from Sigma Legal; contact Darla Karlsson for details.]

What is claimed is:

1. A method of aligning a plurality of data sets having common subject matter, each data set being encoded as an ordered set of wave forms each having at least one associated wave form parameter, the method comprising:

a. featurelessly approximating parameters of a projective coordinate transformation that spatially relates, in first and second data sets, wave forms corresponding to common subject matter therebetween;

b. applying the parameters to the first data set to thereby transform it into a processed data set, the common subject matter encoded by wave forms in the processed data set being substantially spatially consistent with the common subject matter encoded by wave forms in the second data set; and

c. aligning the data sets by combining the wave forms corresponding to the common subject matter.

2. The method of claim 1 wherein the parameters are approximated according to steps comprising:

a. for each of a plurality of wave forms in the first data set, defining a model velocity um, vm that quantifies, in each of two orthogonal directions, allowable deviations in a wave form parameter according to the projective coordinate transformation;

b. for each of the plurality of first-data set wave forms, defining a flow velocity uf, vf that expresses, in each of two orthogonal directions, the actual deviation in the wave form parameter between the first-data set wave form and a plurality of wave forms in the second data set; and

c. locating, for each of the plurality of first-data set wave forms, a corresponding second data set wave form such that the squared sum of differences between um, vm and uf, vf for all of the plurality of first-data set wave forms and all corresponding second-data set wave forms is minimized.

3. The method of claim 1 wherein the parameters are approximated according to steps comprising:

a. generating a flow holding field comprising flow velocities relating wave forms in the first data set to corresponding wave forms in the second data set; and

b. regressively approximating, from the flow field, parameters of a projective coordinate transformation consistent with the flow field.

4. The method of claim 2 wherein the squared sum of differences is given by [Figure - see DK for full documentation].

5. The method of claim 2 wherein the plurality of wave forms in the first data set are the four corners of a wave form bounding box.

6. The method of claim 1 further comprising the steps of:

d. sampling each of the first and second data sets at a first sampling frequency to produce initial sets of wave forms encoding the data sets at an initial resolution;

e. performing step (a) on the wave forms at the initial resolution to identify subject matter common to the first and second data sets;

f. sampling each of the first and second data sets at a second sampling frequency to produce subsequent sets of wave forms encoding the data sets at a higher resolution; and

g. performing steps (a) and (b) on the wave forms.

7. The method of claim 1 further comprising the steps of:

d. following transformation of the first data set into the processed data set, repeating at least once steps (a) and (b) on the processed data set to transform the processed data set into a reprocessed data set; and

e. deriving a new set of transformation parameters based on transformation of the first data set into the processed data set and transformation of the processed data set into the reprocessed data set.

8. The method of claim 7 further comprising repeating steps (d) and (e) on different versions of the first and second data sets, each version encoding a different resolution level.

9. The method of claim 1 wherein the second data set is a zoomed-in version of a portion of the first data set, the wave forms of the first data set being upsampled and combined with the wave forms of the second data set by a process selected from (i) last to arrive, (ii) mean, (iii) median, (iv) mode and (v) trimmed mean.

10. A method of aligning a plurality of data sets having common subject matter, each data set being encoded as an ordered set of wave forms each having at least one associated wave form parameter, the method comprising:

a. analyzing first and second data sets to identify wave forms corresponding to common subject matter therebetween and spatially related by a first projective coordinate transformation;

b. approximating the first projective coordinate transformation;

c. projectively transforming the first data set using the approximate projective coordinate transformation to produce an intermediate data set;

d. analyzing the intermediate and second data sets to identify wave forms corresponding to common subject matter therebetween and spatially related by a second projective coordinate transformation;

e. approximating the second projective coordinate transformation;

f. accumulating the approximate projective coordinate transformations into a composite transformation relating the first data set to the second data set;

g. applying the composite transformation to the first data set to thereby transform it into a processed data set, the common subject matter encoded by wave forms in the processed data set being substantially spatially consistent with the common subject matter encoded by wave forms in the second data set; and

h. aligning the data sets by combining the wave forms corresponding to the common subject matter.

11. Apparatus for aligning first and second data sets having common subject matter comprising:

a. first and second computer memories for storing each data set as an ordered set of wave forms each having at least one associated wave form parameter;

b. analysis means for featurelessly approximating parameters of a projective coordinate transformation that spatially relates wave forms corresponding to common subject matter of the first and second data sets; and

c. data set-processing means for (i) applying the parameters to the contents of the first computer memory to thereby transform them into a processed data set, the common subject matter encoded by wave forms in the processed data set being substantially spatially consistent with the common subject matter encoded by wave forms in the second computer memory, and (ii) aligning the data sets by combining the wave forms corresponding to the common subject matter.

12. The apparatus of claim 11 wherein the analysis module is configured to approximate the parameters by:

a. for each of a plurality of wave forms in the first computer memory, defining a model velocity um, vm that quantifies, in each of two orthogonal directions, allowable deviations in a wave form parameter according to the projective coordinate transformation;

b. for each of the plurality of wave forms in the first computer memory, defining a flow velocity uf, vf that expresses, in each of two orthogonal directions, the actual deviation in the wave form parameter between the wave form in the first computer memory and a plurality of wave forms in the second computer memory; and
c. locating, for each of the plurality of wave forms in the first computer memory, a corresponding wave form in the second computer memory such that the squared sum of differences between um, vm and uf, vf for all of the plurality of wave forms in the first computer memory and all corresponding wave forms in the second computer memory is minimized.

13. The apparatus of claim 11 wherein the analysis module is configured to approximate the parameters by:

a. generating an optical flow field comprising flow velocities relating wave forms in the first computer memory to corresponding wave forms in the second computer memory; and

b. regressively approximating, from the flow field, parameters of a projective coordinate transformation consistent with the flow field.

14. An omnibus data thesaurus comprising:

a. a database of data sets each stored as an ordered set of wave forms, each wave form having at least one associated wave form parameter;

b. first and second computer memories for storing a reference data set and a working data set;

c. analysis means for sequentially retrieving data sets from the database and storing each retrieved data set in the second computer memory, the analysis means operating, for each retrieved data set, on the first and second computer memories to detect the existence of common subject matter between the reference data set and the working data set by featurelessly determining whether wave forms from the first computer memory can be related to wave forms of the second computer memory according to a projective coordinate transformation, and if not, rejecting the working data set as unrelated to the reference data set; and

d. an interface for displaying working data sets related to the reference data set.