Stereo correspondence search
AssigneeMine One GmbH
InventorsJAMES A. MCCOMBE, CHRISTOPH BIRKHOLD
Life of this patent
Estimating the term…
Abstract
Methods, systems, devices and computer software/program code products enable efficiently finding stereo correspondence between a feature or set of features in a first image or signal, and a search domain in a second image or signal.
Claims110
A method of searching for correspondence between a first selected feature in a first image and an element within a selected search domain in a second image, the method comprising:
- in a digital processing resource comprising a digital processor:
- A) utilizing a multi-level aggregate digital data structure representative of the second image, the multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- B) comparing a relatively lower resolution digital data representation of the first selected feature against a relatively lower resolution digital data representation of a first selected subset of the selected search domain in the multi-level aggregate data structure, the comparing comprising computation of a minimum difference value and a maximum difference value:
- C) iteratively executing the comparing (B) against other subsets of the selected search domain;
- D) identifying a threshold difference value based on maximum difference values from the comparisons against subsets of the selected search domain;
- and
- E) rejecting subsets for which the comparison results in minimum difference values that exceed the identified threshold difference value.
A method for determining disparity between a first image and a second image, the method comprising:
- in a digital processing resource comprising a digital processor:
- A) generating a multi-level aggregate digital data structure representative of the second image, the multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- B) selecting a first feature from the first image;
- C) searching for a corresponding element within the second image, utilizing a selected search method, the corresponding element having correspondence with the selected feature from the first image;
- D) based on results of the search, recording correspondence information relating to correspondence between the selected feature and the corresponding element;
- E) iteratively executing the selecting (B), the searching (C) and the recording (D), using other selected features from the first image, to construct a digital map of correspondences for the selected features from the first image.
A method of searching for correspondence between a first selected feature in an input signal and an element within a selected search domain in a search signal, the method comprising:
- in a digital processing resource comprising a digital processor:
- A) utilizing a multi-level aggregate digital data structure representative of the search signal, the multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- B) comparing a relatively lower resolution digital data representation of the first selected feature against a relatively lower resolution digital data representation of a first selected subset of the selected search domain in the multi-level aggregate data structure, the comparison comprising computation of a minimum difference value and a maximum difference value;
- C) iteratively executing the comparing (B) against other subsets of the selected search domain;
- D) identifying a threshold difference value based on maximum difference values from the comparisons against subsets of the selected search domain;
- and
- E) rejecting subsets for which the comparison results in minimum difference values that exceed the identified threshold difference value.
A variance-aware method of searching for correspondence between a first selected feature in a first image and an element within a selected search domain in a second image, the method comprising:
- in a digital processing resource comprising a digital processor:
- A) utilizing a multi-level aggregate digital data structure representative of the second image, the multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- B) comparing a digital data representation of the first selected feature, at a given resolution, against a digital data representation of a first selected subset of the selected search domain, at a given resolution, in the multi-level aggregate data structure:
- C) determining, based on the comparing, a variance value for the first selected subset and
- D) utilizing the variance value to determine whether to execute another comparing operation in a higher resolution digital data representation in the multi-level aggregate structure, wherein, if the determined variance value is less than a selected threshold value, then not executing another comparing operation for the first selected subset in a higher resolution digital data representation in the multi-level aggregate structure.
A variance-aware method of searching for correspondence between a first selected feature in an input signal and an element within a selected search domain in a search signal, the method comprising:
- in a digital processing resource comprising a digital processor:
- A) utilizing a multi-level aggregate digital data structure representative of the search signal, the multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- B) comparing digital data representation of the first selected feature, at a given resolution against a digital data representation of a first selected subset of the selected search domain, at a given resolution, in the multi-level aggregate data structure;
- C) determining, based on the comparing, a variance value for the first selected subset;
- and
- D) utilizing the variance value to determine whether to execute another comparing operation in a higher resolution digital data representation in the multi-level aggregate structure, wherein, if the determined variance value is less than a selected threshold value, then not executing another comparing operation for the first selected subset in a higher resolution digital data representation in the multi-level aggregate structure.
A method of executing a lossless search for correspondence between a first selected feature in a first image and an element within a selected search domain in a second image, the method comprising:
- in a digital processing resource comprising a digital processor:
- A) utilizing a first multi-level aggregate digital data structure representative of the selected feature, the first multi-level aggregate digital data structure comprising, digital data representations at different resolutions;
- B) utilizing a second multi-level aggregate digital data structure representative of a first selected subset of the selected search domain, the second multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- C) comparing a digital data representation of the selected feature, at a given resolution, to a digital data representation of the first selected subset of the selected search domain, at a given resolution, and computing, based on the comparing, minimum and maximum error for each eligible data element of the digital data representation at the given resolution in the multi-level aggregate digital data structure, wherein an data element is considered to be ineligible if a subsuming data dement in a corresponding lower resolution was indicated to be ineligible;
- D) and if the currently executed comparison was at a highest possible resolution, then determining the lowest value for the error, wherein (1) the error determination can incorporate error values from multiple resolutions of the multi-level aggregate digital data structure, and (2) the result of the search is a transform that produces the lowest error.
A method of searching for a correspondence between a first selected feature in a first image and an element within a selected search domain in a second image, the method comprising:
- in a digital processing resource comprising a digital processor:
- comparing a digital data representation of the selected feature from the first image against a digital data representation of a selected subset of the selected search domain in the second image;
- determining, for a given comparison, an error value corresponding to the given comparison, the error value being representative of the degree to which the selected feature from the first image corresponds with the selected subset of the selected search domain in the second image when the comparing is executed in accordance with selected processing parameters;
- and
- iteratively executing the comparing and determining, while applying selected changes to the processing parameters across the selected subset of the selected search domain, until processing parameters resulting in a smallest error value are found;
- and
- estimating minimum and maximum possible errors for correspondence for the selected feature in the first image at a full resolution, by executing the comparing and determining at reduced resolution on multi-level aggregate digital data structures representative of the first image and the selected subset of the selected search domain in the second image, respectively.
A method of searching for a correspondence between a first selected feature in a first image and an element within a selected search domain in a second image, the method comprising;
- in a digital processing resource comprising a digital processor:
- comparing a digital data representation of the selected feature from the first image against a digital data representation of a selected subset of the selected search domain in the second image;
- determining, for a given comparison, an error value corresponding to the given comparison, the error value being representative of the degree to which the selected feature from the first image corresponds with the selected subset of the selected search domain in the second image when the comparing is executed in accordance with selected processing parameters;
- and
- iteratively executing the comparing and determining, while applying selected changes to the processing parameters across the selected subset of the selected search domain, until processing parameters resulting in a smallest error value are found;
- and
- utilizing, in executing the comparing, a multi-level aggregate digital data structure containing digital data representations at different resolution levels.
A system operable to search for correspondence between a first selected feature in a first image and an element within a selected search domain in a second image, the system comprising:
- a digital processing resource comprising a digital processor, the digital processing resource being configured to:
- A) utilize a multi-level aggregate digital data structure representative of the second image, the multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- B) compare a relatively lower resolution digital data representation of the first selected feature against a relatively lower resolution digital data representation of a first selected subset of the selected search domain in the multi-level aggregate data structure, the comparing comprising computation of a minimum difference value and a maximum difference value;
- C) iteratively execute the comparing (B) against other subsets of the selected search domain;
- D) identify a threshold difference value based on maximum difference values from the comparisons against subsets of the selected search domain;
- and
- E) reject subsets for which the comparison results in minimum difference values that exceed the identified threshold difference value.
A program product for use with a digital processing system to enable the digital processing system to search for correspondence between a first selected feature in a first image and an element within a selected search domain in a second image, the digital processing system comprising a digital processing resource, the digital processing resource comprising at least one digital processor, the program product comprising digital processor-executable program instructions stored on a non-transitory digital processor-readable medium, which when executed in the digital processing resource cause the digital processing resource to:
- A) utilize a multi-level aggregate digital data structure representative of the second image, the multi-level aggregate digital data structure comprising digital data representations at different resolutions;
- B) compare a relatively lower resolution digital data representation of the first selected feature against a relatively lower resolution digital data representation of a first selected subset of the selected search domain in the multi-level aggregate data structure, the comparing comprising computation of a minimum difference value and a maximum difference value:
- C) iteratively execute the comparing (B) against other subsets of the selected search domain;
- D) identify a threshold difference value based on maximum difference values from the comparisons against subsets of the selected search domain;
- and
- E) reject subsets for which the comparison results in minimum difference values that exceed the identified threshold difference value.
Dependencies are inferred from the claim text.