CORNELL CS 664 - Distance Transforms

Unformatted text preview:

CS664 Computer Vision7. Distance TransformsDan Huttenlocher2Comparing Binary Feature Maps Binary “image” specifying feature locations– In x,y or x,y,scale Even small variations will cause maps not to align precisely Distance transforms a natural way to “blur” feature locations geometrically Natural generalization also applies not just to binary data but to any cost or height map3Distance Transform Map of distances from any point to nearest point of some type– Distances to object boundaries in computer graphics, robotics and AI– Distances to image features in computer vision Generally used for data on grid– Pixels or voxels, 2D or 3D– Related to exact algorithms for Voronoi diagrams Efficient algorithms for computing– Linear in number of pixels, fast in practice4Uses of Distance Transforms Image matching and object recognition– Hausdorff and Chamfer matching– Skeletonization Path planning and navigation– High clearance paths5Uses of Distance Transforms Proximity-based matching– For each point of set A nearest point of set B– But not correspondence or one-to-one matching– Related to morphological dilation• Replace each point with disc Path planning and obstacle avoidance– Maximal clearance path– Re-compute if moving obstacles• But bound on how fast changes6Distance Transform Formula Set of points, P, and measure of distanceDT(P)[x] = miny∈Pdist(x,y) For each location x distance to nearest point y in P– Can think of “cones” rooted at each y ∈ P– Min over all the cones (lower envelope)7Different Distance Measures Euclidean distance (L2norm)sqrt((x1– y1)2+ (x2- y2)2 + … ) City block distance (L1norm)|x1– y1| + |x2- y2| + … Chessboard distance (L∞norm)max(|x1– y1|, |x2- y2|, …)8Relation to Voronoi Diagram Equidistant from two or more points– Dual of Delaunay triangulation– Compute in O(nlogn) time (Graham scan)– Use to efficiently find closest point, O(logn)9Grid Formulation of Distance Trans. Commonly computed on a grid Γ, for set of points P ⊆ΓDT(P)[x] = miny∈Γ(dist(x,y) + 1P(y)) Where 1P(y) indicator function for P– Value of 0 when y∈P, ∞ otherwise– Can think of cone rooted at each point of grid, rather than of P– Cones not at points of P are infinitely large so don’t figure into minimum001121211212322310Naïve Computation For each point on the grid, explicitly consider each point of P and minimize– For n grid points and m points in P take time O(mn)– Note that m is O(n), so O(n2) method Not very practical even for moderate size grids such as images– Even a low-resolution video frame has about 300K pixels• About 100 billion distance computations11Better Methods on Grid 1D case, L1norm: |x1– y1| + |x2- y2| – Two passes: • Find closest point on left• Find closest on right if closer than one on left– Incremental:• Moving left-to-right, closest point on left either previous closest point or current point• Analogous for moving right-to-left – Can keep track of closest point as well as distance to it• Will illustrate distance only, less book-keeping12L1 Distance Transform Algorithm Two pass O(n) algorithm for 1D L1norm(just distance and not source point)1. Initialize: For all jD[j] ← 1P[j]2. Forward: For j from 1 up to n-1D[j] ← min(D[j],D[j-1]+1)3. Backward: For j from n-2 down to 0D[j] ← min(D[j],D[j+1]+1)∞0∞0∞∞∞0∞∞01012301101012101100113L1Distance Transform 2D case analogous to 1D– Initialization– Forward and backward pass• Forward pass adds one to closest above and to left, takes min with self• Backward pass analogous below and to right0011212112123223001∞∞∞∞∞∞∞∞∞∞∞∞∞001∞∞∞∞∞ 1∞ 12∞223s101011s00∞∞∞ ∞∞∞∞∞∞∞∞∞∞∞14L∞Distance Transform What about Chessboard distance max(|x1– y1|, |x2- y2|) ? Same approach of initialization and two passes– Now also consider point one away on both axes0011111111112222001∞∞∞∞∞∞∞∞∞∞∞∞∞001∞∞∞∞∞1∞ 11∞222s111111s00∞∞∞ ∞∞∞∞∞∞∞∞∞∞∞15L2Distance Transform What about Euclidean distancesqrt((x1– y1)2+ (x2- y2)2 ) ? Not linear function of location on grid– Simple local propagation methods not correct Local propagation just approximation– Introduces considerable error, particularly at larger distances– Bigger neighborhood can helpbut not fixs1√2116Exact L2Distance Transform 1D case doesn’t seem helpful– Same as L1– But just saw 2D case not same as L1 Several quite involved methods– Linear or O(nlogn) time, but at edge of practical Revisit 1D– Decompose 2D into two 1D transforms– Yield relatively simple method, though not local– Requires more advanced way of understanding running time – amortized analysis17Squared Distance on 2D Grid Consider f(x,y) on grid– For instance, indicator function for membership in point set P, 0 or ∞ Distance transformDf(x,y) = minx′,y′((x-x′)2 + (y-y′)2 + f(x′,y′)) First term does not depend on y’= minx′((x-x′)2 + miny′((y-y′)2 + f(x′,y′))) But then can view as 1D distance transform restricted to column indexed by x’= minx′((x-x′)2 + Df|x’(y))18Approach for L2Distance Transform Start with point set on grid Initialize to 0,∞ cost function Perform 1D transform on columns of cost function Perform 1D transform on rows of result– Cascade results in each dimension Compute square roots if actual distance needed– Note, as does not change minima, often more efficient to leave as squared distance19Computing 1D L22 Transform Efficiently  Compute h(x)=minx’((x-x’)2+f(x’)) Intuition: each value defines a constraint– Geometric view: in one dimension, lowerenvelope of arrangement of n quadratics • Each rooted at (x,f(x))− Related to convex hull in computational geometry20Algorithm for 1D Lower Envelope Incrementally add quadratics– Keep only those “lower envelope”• Maintain ordered list of visible quadratics and the intersections of successive ones Consider in left-to-right order– Compare new intersection with rightmost quadratic to rightmost existing intersection• If to left, hides rightmost quadratic so remove and repeatNewRightmostNew Rightmost21Running Time of LE Algorithm Consider adding each quadratic just once– Intersection and


View Full Document
Download Distance Transforms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Distance Transforms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Distance Transforms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?