Fast correlation search for stereo algorithm
AssigneeIntel Corporation
InventorsDror Reif, Jacob Minsky
Life of this patent
Estimating the term…
Abstract
Techniques are disclosed for carrying our correlation search in contexts such as stereo algorithms of graphics systems. In accordance with an embodiment, the techniques employ a locality-sensitive hashing (LSH) function to reduce the number of bits to be processed during the correlation process, and to identify a sub-set of available image points that are likely to be the best match to a given target image point. Once such a sub-set of likely image points is identified, a more comprehensive correlation algorithm can be run, if so desired, to further ensure the quality of the match.
Claims30
A stereo image correlation method, comprising:
- receiving a multi-bit descriptor of an image point of a first image;
- applying a first hash function to a sub-set of bits from the descriptor of the image point of the first image to provide a first hash function value;
- storing a coordinate of the image point of the first image into a location of a first hash table, the location identified by the first hash function value;
- receiving a multi-bit descriptor of an image point of a second image, the first and second images forming a stereo image pair;
- applying the first hash function to the sub-set of bits from the descriptor of the image point of the second image to provide a second hash function value;
- and
- querying the first hash table using the second hash function value to identify a coordinate of an image point of the first image that may be a match to the image point of the second image.
A computer readable medium having instructions encoded thereon that, when executed by one or more processors, cause a stereo image correlation process to be carried out, the process comprising:
- receiving a multi-bit descriptor of an image point of a first image;
- applying a first hash function to a sub-set of bits from the descriptor of the image point of the first image to provide a first hash function value;
- storing a coordinate of the image point of the first image into a location of a first hash table, the location identified by the first hash function value;
- receiving a multi-bit descriptor of an image point of a second image, the first and second images forming a stereo image pair;
- applying the first hash function to the sub-set of bits from the descriptor of the image point of the second image to provide a second hash function value;
- and
- querying the first hash table using the second hash function value to identify a coordinate of an image point of the first image that may be a match to the image point of the second image.
A stereo image correlation device, comprising:
- a first image hashing module configured for receiving a multi-bit descriptor of an image point of a first image, and for applying a first hash function to a sub-set of bits from the descriptor of the image point of the first image to provide a first hash function value;
- a first hash table having a location for storing a coordinate of the image point of the first image, the location identified by the first hash function value;
- a second image hashing module configured for receiving a multi-bit descriptor of an image point of a second image, and for applying the first hash function to the sub-set of bits from the descriptor of the image point of the second image to provide a second hash function value, the first and second images forming a stereo image pair;
- and
- a correlation module configured for querying the first hash table using the second hash function value to identify a coordinate of an image point of the first image that may be a match to the image point of the second image.
The device 23 wherein the additional correlation computation to confirm the match is carried out only if the querying indicates positive disparity between corresponding coordinates of the first and second images.
The device 23 wherein the additional correlation computation to confirm the match is carried out only if the querying indicates a disparity between corresponding coordinates of the first and second images that is within a given maximum disparity.
Dependencies are inferred from the claim text.