[精品論文]Shape Recovery by a Generalized Topology.doc

精品論文shape recovery by a generalized topologypreserving somdong huang and zhang yicomputational intelligence laboratory, school of computer science andengineering, university of electronic science and technology of china, chengdu610054, p. r. china.e-mail: donnyhuang, .abstractthis paper proposes a new deformable model, i.e., gtpsom, for object shape re- covery. inspired by visom and region-aided active contour, the proposed model is formulated as generalized chain som with an adaptive force field. the adaptive force field is adjusted during the evolvement of the neuron chain according to local consistency of the image edge map. with the topology preserving property inherited from the data mapping model, i.e. visom, the proposed model is suitable for both the precise edge detection and the complex shape recovery with boundary strength variations. detailed formulation and analysis of the proposed model are given. ex- periments on both synthesis and real images are carried out to demonstrate the performances.key words: shape recovery; topology preserving mapping; visom; region-aided active contour1 introductionan important goal in computer vision is to recover the objects shape of interest from visual data. deformable models originated in the work of 1 and the 3d case for 2, have been extensively used in shape recovery and medical imaging 34. their applications also include geometric modeling 5, computer animation 6, texture segmentation 7 and object tracking.1 this work was supported by national science foundation of china under grant60471055 and specialized research fund for the doctoral program of higher edu- cation under grant 20040614017.preprint submitted to elsevier preprint31 october 20071the most popular deformable model snake or active contour model 1, describes a closed parametric curve that deforms dynamically and moves to- wards the desired image features under the influence of internal and external forces. the internal forces keep the contour smooth, while the external forces attract the snake towards lines, edges, or other low-level image features. the geodesic active contour 8 significantly improve the parametric snake by nat- urally handling topological changes. however, it still suffers from drawbacks such as edge leakage and sensitivity to initialization. the gradient vector flow (gvf) snake 9 uses a bi-directional external force field that provides long-range capture of object boundaries from either side. the main drawback of gvf however is that the contour does not propagate where the vector flows are the saddle points or divergence points within a neighborhood. therefore, their contours can only avoid getting trapped at these points by proper ini- tialization.there are also many works 1213 that integrate the conventional som and snake. in these models, shape recovery is regarded as data mapping from the edges to the chain soms. unlike the classical soms that read the input data in random sequences and adjust the network structure over space, in these models, som processes the whole input in parallel and organizes itself over time 14. however, to ensure the proper evolvement to the object boundaries, a number of “batch” updating rules and parameters needs to be determined manually. thus their performances are limited.another framework of deformable model is based on charged particle dy- namics. in the charged particle model (cpm) 15, the charges are attracted towards the objects contours of interest by an electric field computed using the edge magnitude. the electric field plays the same role as the external force in the snake model, while internal interactions are modelled by repulsive elec- trostatic forces, referred to as coulomb forces. cpm is extremely flexible and greatly relieve the initialization problem. however, it is not suitable for the cases where continuous and closed final contours are required.recently, yang et al. proposed the charged active contour based on elec- trostatics (cace) 18 that incorporate both the snake and particle based models cpm. cace adaptively change the external force field with the prop- agation of the active contour by introducing a competition part. this cace successfully move across the saddle points and divergence points. but this ability depends on parameters chosen according to the local edge magnitude. for this reason, cace has difficulties in dealing with images of variant edge strength and complex shapes.in order to overcome the drawbacks in the deformable model reviewed above, we propose a deformable model by incorporating the topology pre- serving self-organizing mapping into the neuron competition. we call this model the generalized topology preserving som (gtpsom). it is inspired by the visual induced self-organizing map (visom) 11 where the mapping pre- serves the inter-point distances of the input data on the neuron map as well5as the topology. following the ideas in 121314, the gtpsom is driven in parallel by an adaptive force field, which imposes constrains on the local boundary variation. region aided active contour and level sets are employed to implement the proposed model. the gtpsom model is suitable for both the precise edge detection and the complex shape recovery with boundary strength variation. detailed formulation and analysis of the proposed model are presented. experiments on both synthesis and real images are carried out to illustrate the performances.the rest of this paper is organized as follows. section 2 gives detailed formulation of the adaptive force field staring with the self-organizing of a neuron chain. then the proposed model is formulated as active contour and level sets. relations between our model and visom and cace are also given. section 3 presents the experimental results and discussions. finally, the paper is concluded in section 4.2 formulationdenote i the input image of n pixels. the edge map of the image can be computed using either gradient operator i or gaussian-based edge detector. we use the gradient operator throughout the following presentation. our de- formable model is first formulated as a closed neuron chain (fig. 1 (a) driven by an adaptive vector field. the neurons are attracted to the nearest edges while compete for these edges. for the efficiency of numerical computation,our model is then translated in to a region-aided active contour and levelsets formulation.2.1 self-organizing of the neuron chainconsider the edge map of the input image as a data set x = xp r2, p =1, , p with all data points located in the pixels grids. the edge magnitudef (ri ) in each pixel ri (i = 1, , n ) can be regarded as the data density ofthe data set, where ri = rx, ry t r2 is the 2-d coordinates of the pixel.k kour model is designed to map the data distribution of the edge map to adeformable neuron chain (fig. 1 (a) with m uniformly distributed neurons. in the 2-d image coordinate, the neurons in the chain som correspond to the control points of a smooth curve. the weight vector of the kth neuron wk = wx, wy t are used to represent the coordinate of the kth control point.k kby repeatedly updating the weight vectors, the chain som approximatesthe two-dimensional input distribution by a one-dimensional neural network. in this way, the control points move toward the pixels of strong object bound- aries. similar to the classic som, the weight vector of the kth neuron can be updated by moving the neuron along the force vector formulated as the difference between the input data point xp and the weight vector wk :ry fxx vpvpfx kfpvkwx,wyt krx(a)(b)fig. 1. (a) the deformable neuron chain with weight vector wk = wx, wy t in thekk2-d image coordinate; (b) the vector graph of the neuron updating.4wk = (xp wk ),where and are the learning rate and the neighborhood function respec- tively. for each input data point, the updating scale for the closer neuron (the winner) is larger than the neurons faraway (the neighbors of the winner). the neuron grids of the classic soms spread uniformly to the data space using the neighborhood function based on the euclidean distances. in the proposed chain som, similar mechanism is used. the updating scale for the neighbors are reduced along the tangent direction of the chain. thus to maintain the spatial structure of the chain som, neurons are “repelled” by theirs neighbors.for each data point xp (p = 1, , n ), there is a winning neuron wv on the neuron chain that is nearest to it. then the updating force from the kth neuron to the input data fxp k (k = 1, , m ) can be decomposed into two parts (see fig. 1 (b) ):fxp k = fxp v + fvk .the first force fxp v , represents the updating force from the winner to the input data. while the second force fvk is a lateral force between the neuron k to the winner, i.e., a contraction force. this contraction force brings neuronsin the neighborhood toward the winner, and thus forms a contraction around the winner on the chain. this is an unfavorable effect for shape recovery. if the neurons clutch to the stronger parts of the boundary while left the weaker parts empty, the boundary topology of the objects in the image is distorted.the proposed generalized topology preserving som (gtpsom) focuses on this problem. to preserve the uniform boundary topology, the lateral con- traction force fvk is constrained. the scale of the competition is controlled by a function of the mapping from input data space to the two neurons. denote this function by h(wk , wvxp ). the updating force for the kth neuron presented with the data point xp is then:vkfxp k = (xp wk ) (wv wk )h(wk , wxp v )= favkxp k+ f r ,xp kwhere f ais the attraction force and f ris the repelling force. the functionh(wk, wvxp) needs to be formulated so that the neuron chain can spread to theregions of continuous data distribution (the closed boundaries in the image),while cling to the dense regions that has already been occupied.2.2 the adaptive force fieldthe classical soms read the input data in random but sequential or- der and adjust the neural networks over multi-passes. in contrast, to achieve smooth propagation of the neuron chain, we implement “batch” updating 12 13 by generating the joint force vector field f = fx, fy 0 at each pixel location of the input image i .here, we treat the neurons on the deformable chain as positive charges 15. the attraction force generated by the edge pixels ri (i = 1, , n ) can be formulated by treating the edge pixels as fixed negative charges of magnitude f (ri ). the joint force field f is composed of the attraction force f a to the edge data points and repelling force f r between neurons.then according to coulombs law, the attracting force field at the kthneuron is computed by summing the force vectors from all edge data point ri :na x f (ri )wk rif =i=140|wk, ri |3where 0 is the permittivity of free space. note the force vector at wk generated by ri is direct proportionate to the data density f (ri ), and inverse proportion- ate to the square of distance between ri and wk . the attraction force field is pre-computed and fixed through time. here the ”coulomb-law” is not the only option. any isotropic measure can be used if the resulted force vectors de- crease smoothly with the increasing of distance. other natural choices include inverse of the squared distance and the gaussian function.next, we compute the repelling part of the force field. let f (ri ) (i =1, , n ) be the data density in the domain of the edge map, and f (wk ) (k = 1, , m ) for the neuron domain. if f (wj ) 0, the jth neuron is on thepotential edge pixel ri (ri = wj ). the neuron j can be regarded as the winner for data at ri , and the neuron k (wk = ri , k = 1, , m ) is the neighbor. the repelling regularization is realized by lettingf (wj ) f (wk )h(wk , wj ) =, (1)f (wj )where control the resolution of the regularization. note that the distance or spacing among data points in the input space is inverse proportional to thedensity. following from the ideas in visom, the function h(wk , wj ) is related to the density distribution in both domains. both visom and gtpsom con- strain the lateral contraction force according to the desired proportion of the distance in the input space and that represented by the neuron network.if wk and wj are in regions of approximately the same data density, i.e. f (wk ) = f (wj ), the contraction force between them is less constrained. the attraction force field f a will lead both k and j to denser regions, i.e., stronger edges in the vicinity. on the other hand, if the data density at location of thekth neuron is lower than that of the jth neuron, that is f (wk ) f (wj ), the kth neuron is on the relatively weaker edges or in the homogeneous regions. the kth neuron moves less to the denser region that has already been occupied by the jth neuron. an opposite force is applied to repel the kth neuron away from the jth neuron. this actually weaken the attraction force of the data points at ri , where ri = wj .then, in the “batch” updating paradigm, the repelling force field at the kth neuron are computed by summing the force vectors from all other winner neurons (wj = ri ) on the deformable chain. the neighborhood concept is based on the square of distance between wj and wk .m f (wk ) # f (wj )wk wjr xfk =j=11f (wj )40|wk. wj |3as:finally, the joint updating force fk at the kth neuron can be computedfk = f a + f rk knm #= x f (ri )wk rixf (wk )+1 f (wj )wk wj. (2)i=140 |wk ri |3j=1f (wj )40 |wk wj |3note the joint updating force is related to the locations of neurons on the deformable chain. when the neuron chain is propagating through time, the force field fk adaptively changes according to the competition among neurons. in this way the neuron chain is able to move across the saddle points and divergence points in the original attraction force field. the advantage of this formulation is that the repelling scale is only controlled by relativedensity at the neuron locations. it can be seen in (3), the force field at wk that is generated by the occupied positions ri = wj , is adjusted in proportion to the edge strength variation in the neighborhood. this enables our model to maintain the boundary consistency in the local regions. the movement of the neuron chain is smoothed along the object boundaries. by introducing h(, ) (1), our deformable model can be more robust to magnitude variations of the edges.精品論文9fk =nf (ri )wk ri3 +m f (wk ) # f (wj )wk wj3 . (3)xi=1,ri =wj40|wk ri |xj=1,ri =wjf (wj )40|wk wj |2.3 the level set formulationfor complex image boundaries, one needs to dynamically add/delete the neurons and merging/splitting the multiple neuron chains. the proposed gtp- som model can be efficiently formulated as region-aided active contour and level sets.our active contour formulation uses the mean curvature flow with the normalized external force field along the contour normal. to achieve topolog- ical flexibility, the active contour is implicitly embedded into the deforming level set function u(x, y, t), where (x, y) is the spatial coordinate and t de- notes the time. the level sets use the signed distance transform such that the deformable snake is given by the zero level set of u at any time. in this way the 2d contour is extended into a 3d level set function u(x, y, t). at the same time, the adaptive force field defined on the 2d space is extended the 3d space. in this study, we simply compute the extended force field by treating each level set as a deforming contour at each time step. thus, the joint forcefield f (wj ) (j = 1, , m ) as given in (2) is extended to f (ri ) (i = 1, , n )across the image domain. thus, the level set representation of our gtpsomsnake is given as:ut = g c urv | 5 u| (1 ) f|f | u, (4)n where (0, 1) is a real constant, c urv denotes the curvature. and the joint force field only acts along the contour normal, = u . the first term|u|of (4) regulates the contour, and the second term attracts the snake towardsthe object boundaries. computation time of the gtpsom is related to size of the iteration steps, the image size and concavity of the object boundaries. iterations end when changes of the neuron we