Parallel approximation of distance maps

Patent metadata

Field	Value
Publication number	US-9489708-B2
Application number	US-201514624733-A
Country	US
Kind code	B2
Filing date	Feb 18, 2015
Priority date	Feb 14, 2007
Publication date	Nov 8, 2016
Grant date	Nov 8, 2016

Abstract

Method for parallel approximation of distance maps on a discrete representation of a manifold, the method comprising: for at least one Euclidean grid applied on the discrete representation of a manifold, iterating over rows of the Euclidean grid in a first direction, and for each row currently visited during the iterating in the first direction, calculating a distance value for each single cell of the currently visited row in parallel, wherein the calculating is carried out according to a predefined approximation rule, using a distance value calculated for each one of respective cells of a row visited immediately before the currently visited row, wherein the cells of the row visited before the currently visited row are adjacent to the single cell in the Euclidean grid.

First claim

What is claimed is:

1. A method for parallel approximation of distance maps on a discrete representation of a single manifold, the method comprising:
determining a plurality of characteristics of the manifold;
applying a plurality of two-dimensional Euclidean grids over the manifold according to said characteristics; and
for each Euclidean grid, iterating over rows of said Euclidean grid in a first direction.

2. The method of claim 1 , further comprising a preliminary step of applying said plurality of Euclidean grids on the discrete representation of said single manifold.

3. The method of claim 1 , wherein said Euclidean grids comprise a plurality of different Euclidean grids, and each grid is applied on a respective portion of the discrete representation of said single manifold according to said characteristics of said manifold.

4. The method of claim 1 , further comprising:
in a second direction, iterating over rows of said Euclidean grid; and
for each row currently visited during said iterating in said second direction, calculating a distance value for each single cell of said currently visited row in parallel, wherein said calculating is carried out according to a predefined approximation rule, using a distance value calculated for each one of respective cells of a row visited immediately before said currently visited row, wherein said cells of said row visited before said currently visited row are adjacent to said single cell in said Euclidean grid.

5. The method of claim 4 , wherein said iterating in said second direction is carried out in parallel to said iterating in said first direction.

6. The method of claim 4 , further comprising:
in a third direction, iterating over columns of said Euclidean grid; and
for each column currently visited during said iterating in said third direction, calculating a distance value for each single cell of said currently visited column in parallel, wherein said calculating is carried out according to said predefined approximation rule, using a distance value calculated for each one of respective cells of a column visited immediately before said currently visited column, wherein said cells of said column visited before said currently visited column are adjacent to said single cell in said Euclidean grid.

7. The method of claim 6 , further comprising:
in a fourth direction, iterating over columns of said Euclidean grid;
for each column currently visited during said iterating in said fourth direction, calculating a distance value for each single cell of said currently visited column in parallel, wherein said calculating is carried out according to said predefined approximation rule, using a distance value calculated for each one of respective cells of a column visited immediately before said currently visited column, wherein said cells of said column visited before said currently visited column are adjacent to said single cell in said Euclidean grid.

8. The method of claim 7 , wherein said iterating in said fourth direction is carried out in parallel to said iterating in said third direction.

9. The method of claim 1 , including calculating according to a predefined approximation rule wherein said predefined approximation rule comprises a Fast Marching based update scheme or said predefined approximation rule comprises a predefined geometric scheme or both.

10. The method of claim 1 , further comprising automatically calculating geometrical parameters for said Euclidean grid.

11. The method of claim 1 , wherein said iterating and said calculating are carried out using a Graphical Processing Unit (GPU).

12. The method of claim 11 , further comprising assigning each of at least two portions of said Euclidean grid to a respective kernel of said Graphical Processing Unit (GPU).

13. The method of claim 1 , wherein said manifold is an image or a parametric surface or a three-dimensional volume.

14. An apparatus for parallel approximation of distance maps on a discrete representation of a manifold, the apparatus comprising:
an iterator, configured for a plurality of Euclidean grids applied on the discrete representation of a manifold, to iterate over rows of said Euclidean grids in a plurality of directions, wherein said Euclidean grids are two-dimensional grids; and
a distance value calculator, associated with said iterator, and configured for each row currently visited during said iterating in said plurality of directions, to calculate a distance value for each single cell of said currently visited row in parallel;
wherein said Euclidean grids comprise a plurality of different Euclidean grids, each one of said Euclidean grids being applied on a respective portion of the discrete representation of a manifold.

15. The apparatus of claim 14 further comprising a grid applier, associated with said iterator, and configured to apply said Euclidean grid on the discrete representation of a manifold.

16. The apparatus of claim 14 , wherein said iterator is further configured to iterate in a second direction in parallel to iterating in a first direction.

17. The apparatus of claim 14 , wherein said calculating is carried out according to a predefined approximation rule that comprises a Fast Marching based update scheme.

18. The apparatus of claim 14 , wherein said calculating is carried out according to a predefined approximation rule that comprises a predefined geometric scheme.

19. The apparatus of claim 18 , wherein said distance value calculator is further configured to automatically calculate geometrical parameters for said Euclidean grid, and said predefined geometric scheme involves said calculated geometrical parameters.

20. The apparatus of claim 14 , wherein said distance value calculator is implemented on a Graphical Processing Unit (GPU).

21. The apparatus of claim 20 , further comprising a portion assigner, associated with said iterator, and configured to assign each of at least two portions of said Euclidean grid to a respective kernel of said Graphical Processing Unit (GPU).

Assignees

• Technion Res & Dev Foundation
• Intel Corp

Inventors

• Bronstein Alexander
• Bronstein Michael
• Kimmel Ron
• Devir Yohai
• Weber Ofir

Classifications

• G06V10/761

  Proximity, similarity or dissimilarity measures · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06T2207/20041

  Distance transform · CPC title

• G06T7/60

  Analysis of geometric attributes · CPC title

• G06T5/30

  Erosion or dilatation, e.g. thinning · CPC title