ECE533 Final Project 1/19 Robust and efficient 2D Skeleton Shape Representation using Shock Graphs Chung, In Young Lee, Kang Eui 1. Introduction An important approach to representing the structural shape of a plane region is to reduce it to a graph. This reduction may be accomplished by obtaining the ‘skeleton’ of the region via a thinning (or skeletonizing) algorithm. There have been lots of algorithms on obtaining skeleton. However, there are some drawbacks in the performance and time complexities of these algorithms [1]. There has recently been significant interest in using representations based on abstractions of Blum’s skeleton into a graph for qualitative shape matching. The application of these techniques to large databases of shapes hinges on the availability of numerical algorithms for computing the medial axis. Unfortunately, this computation can be extremely subtle [2]. Approaches based on Voronoi techniques preserve topology, but heuristic pruning measures are introduced to remove unwanted edges. Methods based on Euclidean distance functions can localize skeletal points accurately, but often at the cost of altering the object’s topology [3]. The new algorithm for computing subpixel skeletons which is robust and accurate, has low computational complexity, and preserves topology has been proposed by P. Dimitrov, C. Phillips and K. Siddiqi. The key idea is to measure the net outward flux of a vector field per unit area, and to detect locations where a conservation of energy principle is violated. This is done in conjunction with a thinning process applied in a rectangular lattice. However, there are, also, some disadvantages in this algorithm [2]. In this project, we attempt to modify and advance this algorithm and define a new one using Shock Graphs. In this report, we implement the new method proposed by P. Dimitrov, C. Phillips and K. Siddiqi and compare its result with that of Blum’s methodECE533 Final Project 2/19 2. Approach and Work Performed A. Blum’s method In recent years there has been significant interest in using graph-based abstractions of Blum’s skeleton for qualitative shape recognition [4]. The application of such methods to large image databases hinges on the availability of robust and efficient algorithms for computing the medial axis, or approximations to it. Blum proposed that the skeleton of a region may be defined via the medial axis transformation (MAT). The MAT of a region R with border B is as follows. For each point P in R, we find its closest neighbor in B. If p has more than one of closest depend on the definition of a distance. The MAT of a region has an intuitive definition based on the so-called “prairie fire concept.” Consider an image region as a prairie of uniform, dry grass and suppose that a fire is lit along ints border. All fire fronts will advance into the region at the same speed. The MAT of the region is the set of points reached by more than one fire front at the same time [1]. Following figure shows the resulted skeleton image using Blum’s method. (a) Original imageECE533 Final Project 3/19 (b) Resulted Skeleton image using Blum’s method Figure 1. (a) shows the original image and the bottom one (b) shows the resulted image. B. New method a. Euclidean Distance Transformation (EDT) The Euclidean distance between the points p and q with their coordinates),( ),,( tsyx , respectively, is defined as [1] 2122])()[(),( tysxqpD −+−= b. Computing Vector Field. Consider Blum’s grassfire flow NtC=∂∂ acting on a 2D closed curve C, such that each point on its boundary is moving with unit speed in the direction of the inward normal N. This formulation leads to a Hamilton-Jacobi equation on the Euclidean distance function to the initial curve [12]. In physics, such equations are typically solved by looking at the evolution of the phase space of the equivalent Hamiltonian system. Since Hamiltonian systems are conservative, the locus of skeletal points coincides with locations where a conservation of energy principle is violated. This loss of energy can be used to formulate a natural criterion for detecting singularities of the distance function.ECE533 Final Project 4/19 More specifically, let D be the Euclidean distance function to the initial curve C0. The magnitude of its gradient D∇ is identical to 1 in its smooth regime. With),(),,( yx DDpyxq == , the Hamiltonian system is given by ),( ),0 ,0( yx DDpHqqHp −=∂∂==∂∂−= with an associated Hamiltonian function 2122)1(yxDDH +−= [12]. It is straightforward to show that all Hamiltonian systems are conservative and hence divergence free. Conversely, when trajectories of the system intersect, a conservation of energy principle is violated. This suggests a natural approach for detecting the skeleton: compute the divergence of the gradient vector field q and detect locations where it is not zero [2]. Figure 2. Computed vector fieldECE533 Final Project 5/19 c. Computing Divergence (Flux) The divergence is defined as the net outward flux per unit area, as the area about the point shrinks to zero: adlNqqdivLaΔ<≡∫→Δ),lim)(0 Here aΔ is the area, L is its bounding contour and N is the outward normal at each point on the contour. Via the divergence theorem ∫∫><=aLdlNqdaqdiv ,)( In other words, the integral of the divergence of the vector field within a finite area gives the net outward flux through the contour which bounds it. Locations where the flux is negative, and hence energy is lost, correspond to sinks or skeletal points of the interior. Similarly, locations where the flux is positive correspond to sources or skeletal points of the exterior [2].ECE533 Final Project 6/19 Figure 3. Computed FluxECE533 Final Project 7/19 d. Thinning Some definitions Removable point; A point can be removed if and only if its 3x3 neighborhood graph, with cycles of length 3 removed, is a tree. A straightforward way of determining whether or not a graph is a tree is to check that its Euler characteristic EV −(the number of vertices minus the number of edges) is identical to 1. Figure 4. Example of a ‘tree’ End point; A point could be an end point of a 1 pixel thick digital curve if, in a 3x3 neighborhood, it has a single neighbor, or it has two neighbors, both of which are 4-adjacent to one another. Figure 5. Example of an ‘end point’
View Full Document
Unlocking...