SYSTEM, METHOD, AND COMPUTER PROGRAM PRODUCT FOR PERFORMING ONE-DIMESIONAL SEARCHES IN TWO-DIMENSIONAL IMAGES

• US 20150243048A1
• Filed: 02/26/2014
• Published: 08/27/2015
• Est. Priority Date: 02/26/2014
• Status: Abandoned Application

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Pajak, Dawid Stanislaw, Pulli, Kari Antero, Kim, Kihwan
• Application Number:
  US14/191,332
• Publication Number:
  US 20150243048A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06V 10/421 by analysing segments intersecting the pattern
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A system, method, and computer program product are provided for implementing a search of a digital image along a set of paths. The method includes the steps of selecting a set of paths in an image and identifying at least one feature pixel in the set of paths by comparing gradients for each of the pixels in the set of paths. The set of paths includes at least one line of pixels in the image, and a total number of pixels in the set of paths is less than half of a number of pixels in the image.

Claims

1. A method comprising:

selecting a set of paths in an image, wherein the set of paths includes at least one line of pixels in the image, and wherein a total number of pixels in the set of paths is less than half of a number of pixels in the image; and

identifying at least one feature pixel in the set of paths by comparing gradients for each of the pixels in the set of paths.

2. The method of claim 1, wherein identifying at least one feature pixel in the set of paths comprises, for each line of pixels in the set of paths, selecting one or more pixels in the line of pixels associated with gradient data that identifies a feature.

3. The method of claim 1, further comprising dividing the image into a plurality of blocks, wherein each block in the plurality of blocks includes at least one line of pixels in the set of paths.

4. The method of claim 3, wherein identifying at least one feature pixel in the set of paths comprises processing at least two blocks in parallel by calculating gradients for each of the pixels in the at least one line of pixels in each block and identifying at least one feature pixel per block based on the gradient data.

5. The method of claim 3, wherein, for each block in the plurality of blocks, the at least one line of pixels in the set of paths includes a first horizontal line of pixels and a first vertical line of pixels in the block.

6. The method of claim 5, wherein the horizontal line of pixels and the vertical line of pixels are selected based on a random sample point in the block.

7. The method of claim 5, wherein identifying at least one feature pixel in the set of paths comprises, for each block in the plurality of blocks, selecting a pixel in the horizontal line of pixels and the vertical line of pixels based on gradient data associated with each pixel in the horizontal line of pixels and the vertical line of pixels and identifying the selected pixel as a first feature pixel for the block.

8. The method of claim 7, further comprising, for each block:

selecting a portion of the block based on a location of the feature pixel for the block;

selecting a second horizontal line of pixels and a second vertical line of pixels in the portion of the block, wherein the second horizontal line of pixels and the second vertical line of pixels are included in the set of paths; and

identifying a second feature pixel for the block based on gradient data associated with each pixel in the second horizontal line of pixels and the second vertical line of pixels.

9. The method of claim 1, further comprising:

selecting a corresponding set of paths in a second image; and

identifying at least one matching pixel in the second image corresponding to the at least one feature pixel in the image.

10. The method of claim 9, wherein a location of the set of paths in the first image matches a location of the corresponding set of paths in the second image.

11. The method of claim 9, wherein a location of the corresponding set of paths in the second image is based on a coarse translation of a location of the set of paths in the first image.

12. The method of claim 9, wherein the corresponding set of paths in the second image is selected based on a location and at least one gradient value for each feature pixel in the at least one feature pixel.

13. The method of claim 1, further comprising, for each feature pixel in the at least one feature pixel in the image, locating a matching pixel in a second image based on a sparse optical flow.

14. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform steps comprising:

selecting a set of paths in an image, wherein the set of paths includes at least one line of pixels in the image, and wherein a total number of pixels in the set of paths is less than half of a number of pixels in the image; and

identifying at least one feature pixel in the set of paths by comparing gradients for each of the pixels in the set of paths.

15. The non-transitory computer-readable storage medium of claim 14, the steps further comprising dividing the image into a plurality of blocks, wherein each block in the plurality of blocks includes at least one line of pixels in the set of paths.

16. The non-transitory computer-readable storage medium of claim 15, wherein identifying at least one feature pixel in the set of paths comprises processing at least two blocks in parallel by calculating gradients for each of the pixels in the at least one line of pixels in each block and identifying at least one feature pixel per block based on the gradient data.

17. The non-transitory computer-readable storage medium of claim 14, the steps further comprising:

selecting a corresponding set of paths in a second image; and

identifying at least one matching pixel in the second image corresponding to the at least one feature pixel in the image.

19. The system of claim 17, the processor further configured to divide the image into a plurality of blocks, wherein each block in the plurality of blocks includes at least one line of pixels in the set of paths.

20. The system of claim 17, wherein the memory stores a second image, the processor further configured to:

select a corresponding set of paths in the second image; and

identify at least one matching pixel in the second image corresponding to the at least one feature pixel in the image.

18. A system, comprising:

a memory that stores an image; and

a processor coupled to the memory and configured to;

select a set of paths in an image, wherein the set of paths includes at least one line of pixels in the image, and wherein a total number of pixels in the set of paths is less than half of a number of pixels in the image; and

identify at least one feature pixel in the set of paths by comparing gradients for each of the pixels in the set of paths.