Signal processing disparity resolution

• US 4,745,562 A
• Filed: 08/16/1985
• Issued: 05/17/1988
• Est. Priority Date: 08/16/1985
• Status: Expired due to Fees

• Current Assignee: Schlumberger Limited (Schlumberger NV)
• Original Assignee: Schlumberger Limited (Schlumberger NV)
• Inventors: Prazdny, Kvetoslav F.
• Primary Examiner(s): Paschall, M. H.
• Assistant Examiner(s): Evans, Geoffrey S.
• Application Number:
  US06/766,747
• Time in Patent Office: 1,005 Days
• Field of Search: 364/551, 364/556, 364/559, 364/560, 356/390, 382/30, 382/33, 382/34, 901/47, 340/146.2
• US Class Current: 702/71
• CPC Class Codes: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 2201/06 Recognition of objects for industrial automation
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects

Abstract

A process for signal matching. The process is general and can be applied to matching signals of arbitrary dimension. To implement the process, a suitable discretized description of the two signals to be matched is defined. Such descriptions can be the local signal extrema or any other qualitative signal significant points of interest or features. Allowable feature matches and values for matches are defined, and determined for all potential matches. Matches are confined to the features within defined matching windows and are mapped for each significant point. Within a defined similarity disparity window, a neighborhood of potentially interacting matches are evaluated. Matches within a neighborhood contribute to the decision about the appropriate match for each significant point to determine a composite similarity weighted best value match for each point. Mapping is piecewise continuous. The two signals are matched with disparities therebetween resolved and removed responsive to the best match values. Following the coherence process, the overall process of the present invention provides a superposition of several such piecewise transformations.

In an illustrated application domain, a stereo correspondence technique provides for matching of figurally similar three dimensional images, according to a simple no iterative, parallel and local process that can successfully detect disparities of opaque as well as transparent surfaces.

Claims

1. A process for matching two related but transformed signal waveforms representative of sensor outputs in a particular application domain, said process comprising the steps of:

selecting criteria, associated with the particular application domain, for use in the determination of significant points of interest, type sets of allowable types of point matches, type match valuation, match windows, disparity windows, and disparity similarity valuation;

identifying significant points of interest in each data set;

determining positional offset information and type information for significant points of interest in each data set responsive to said criteria;

determining a match window for each significant point of interest responsive to said criteria;

locating and determining match values for all allowable matches between significant points in the two data sets, within respective match windows;

determining disparity windows for all significant points in the two data sets;

determining composite similarity values for each allowable match to a particular significant point in the first data set, responsive to the positional offset information for each allowable match to said particular point and to the positional offset information for correspondingly offset allowable matches for other significant points in the first data set, for such points within the disparity window with said particular point, responsive to the match values;

determining a best match for each said particular point within the first data set corresponding to the allowable match point in the second data set having the maximum composite similarity value for the respective particular point, responsive to the match values and the composite similarity values; and

matching the two signal waveforms responsive to the criteria and the determined best matches.

2. The process as in claim 1 further comprising the steps of:

storing said determined type information associatively mapped to positional information for each significant point of interest in each data set;

storing, for each significant point of interest in the first data set, said match values each associatively mapped to positional offset data representative of the respective relative distance offset between each significant point in the first data set and each respective allowable match point in the second data set;

storing said composite similarity values, associatively mapped to positional offset data, for each allowable match to a particular point in the first data set; and

storing said best match values associatively mapped to the positional offset information for the particular point, and for the allowable match point in the second data set having the maximum composite similarity value for the respective particular point, responsive to the match value and the composite similarity value.

3. The process as in claim 1 further comprising the step of:

analyzing relationships in parallel of multiple points of the two data sets within the window, to determine a best value match for each point of interest on the first waveform.

4. The process as in claim 1 further comprising the step of:

relating positional offset data for corresponding best match points between the first and second waveforms to yield a fused data set representing coherent data about the related waveforms.

5. The process as in claim 1 wherein the step of determining composite similarity values is further characterized as being based on cooperatively and local consensus.

6. The process as in claim 1 wherein the step of determining composite similarity values is further comprised of the step of:

allowing for local deformations in the interaction of the data sets.

7. The process as in claim 1 wherein the step of determining the composite similarity value is further comprised of the step of:

scaling the valuation of neighboring allowable matches by the spatial separation of the points at which the disparities are measured.

8. The process of claim 1 wherein the step of determining the composite similarity value is further comprised of the steps of:

determining a predominant gradient orientation for each waveform, and

modifying the disparity window responsive to the predominant gradient.

9. The process as in claim 1 further comprising the step of:

biasing the determination of composite similarity in favor of local continuity.

10. A system for matching two related but transformed signal waveforms representative of sensor outputs, said system comprising:

means for providing criteria for use in the determination of significant points of interest, type sets of allowable types of point matches, type match valuation, matching widows, disparity windows, and disparity similarity valuation;

means for determining significant points of interest in each data set;

means for determining positional offset information and type information for significant points of interest in each data set responsive to said criteria;

means for determining a match window for each significant point of interest responsive to said criteria;

means for locating and determining match values for all allowable matches between points in the two data sets, within said respective match windows, responsive to the criteria;

means for determining disparity windows for all significant points in the two data sets, responsive to the criteria;

means for determining, and storing, composite similarity values, associatively mapped to positional offset data, for each allowable match to a particular point in the first data set, responsive to the positional offset information for each allowable match to said point and to the positional offset information for corespondingly offset allowable matches for other significant points in the first data set, for significant points within the disparity window for said particular point, responsive to the criteria and to the match values for each respective allowable match;

means for storing as a best match, for each said particular point within the first data set, positional information for the particular point and for the respective allowable match point in the second data set having the maximum composite similarity value for the respective particular point, responsive to the criteria, the respective match value, and the composite similarity value store; and

means for matching the two signal waveforms and resolving ambiguities therebetween responsive to said criteria and the best match store.

11. The system as in claim 10 further comprising:

means for determining in parallel the best match for multiple significant points of interest on the first waveform.

12. The system as in claim 10 further comprising:

means for relating positional offset data for corresponding best match points between the first and second waveform to yield a fused data set representing coherent data about the two related waveforms.

13. The system as in claim 10 further characterized as determining composite similarity based on cooperativity and local consensus.

14. The system as in claim 10 wherein said means for determining composite similarity values is further characterized as allowing for local deformations in the interaction of the data sets.

15. The system as in claim 10 further characterized in that said composite similarity value contribution for each allowable match is scaled by the spatial separation of the significant points of interest at which the disparities are measured.

16. The system as in claim 10 wherein said means for determining said composite similarity value is further comprised of:

means for determining a predominant gradient orientation, means for measuring the local image intensity gradient, and means for modifying the disparity window responsive to said predominant gradient, said local gradient, and to the criteria.

17. The system as in claim 10 further comprising:

means for biasing the determination of composite similarity in favor of local continuity.

18. A stereo correspondence process for matching of figurally similar three dimensional images responsive to discretized representations of the images, comprising the step of

determining significant features and positions there for each of the images;

determining all potential matches of features as between the two images in accordance with predefined feature matching windows;

determining support for each potential match of features responsive to a predefined disparity valuation function for valving support of potential matches of neighboring features within a predefined window;

utilizing all support disparity values for each potential feature match to determine a composite value for each potential feature match;

selecting as a best match the maximum composite value for each individual feature of one image to features of the other image;

matching the images for stereo correspondence according to the selected best matches.

19. The process as in claim 18 further comprising:

storing identifying characteristic data representative of determined significant features for each image in a memory, said identifying characteristic data associatively mapped to its respective position in the respective image;

storing value characteristic data representative of determined potential matches in a memory, said value characteristic data associately mapped to positional data for the respective features in the images; and

summing in respective separate memories, the respective support disparity values for each respective feature in one image, associatively mapped according to relative offset of potential matches.

20. A process for matching two transformed but related signals, comprising the steps of:

provding selection criteria for significant points of interest, type sets for allowable matches, matching window, disparity window, disparity similarity valuation and type match valuation;

storing separately digitized data sets for the two signals, each data set associately mapped by relative positional information within each signal;

analyzing each data set according to the selection criteria to determine location and type value for each significant point of interest, and storing the type value associatively mapped to the position of each point;

determining match windows responsive to the selection criteria;

locating allowable matches between significant points of interest in the two data sets within each mach window responsive to the selection criteria and to the associatively mapped type store;

valuing each allowable match responsive to the selection criteria, and

storing the match values, associatively mapped according to positional offset and according to each particular points'"'"' position within the first data set;

determining disparity windows responsive to the selection criteria for all points within the data sets;

determining composite similarity values for each allowable match for each particular point in the first data set based on disparity similarity of allowable matches for the particular point and of neighboring points in the first data set within the disparity window;

accumulating sums in separate "activity cells" for the disparity similarity values for allowable matches to the particular point and neighboring points according to positional offsets, responsive to the associatively mapped match value store to the selection criteria;

selecting the maximally valued activity cell for each particular point as identifying the best match for the particular point;

storing positional data for the best match from the second data set for each point of interest in the first data, associatively mapping the corresponding best match points to each other;

matching the two signals and removing disparities therebetween responsive to the selection criteria and to the best match mapped store.