《J Math Imaging Vis 25 341–352, 2006 c ○ 2006 Springer Science + Business Media, LLC. Manu.pdf》由会员分享，可在线阅读，更多相关《J Math Imaging Vis 25 341–352, 2006 c ○ 2006 Springer Science + Business Media, LLC. Manu.pdf（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。
1、J Math Imaging Vis25: 341352, 2006c 2006 Springer Science + Business Media, LLC. Manufactured in The Netherlands.DOI: 10.1007/s10851-006-7249-8HarmonicHarmonic EmbeddingsEmbeddings forfor LinearLinear ShapeShape AnalysisAnalysisALESSANDRO DUCIComputer Science Department, University of California at
2、Los Angeles, Los Angeles - CA 90095alessandro.ducisns.itANTHONY YEZZIElectrical and Computer Engineering, Georgia Institute of Technology,Atlanta - 30332ayezziece.gatech.eduSTEFANOSOATTOComputer Science Department, University of California at Los Angeles, Los Angeles - CA 90095soattoucla.eduKELVINRO
3、CHAElectrical and Computer Engineering, Georgia Institute of Technology,Atlanta - 30332gtg185jmail.gatech.eduPublishedPublished online:online: 9 9 OctoberOctober 20062006Abstract.Abstract.We present a novel representation of shape for closed contours in R2or for compact surfaces in R3explicitlydesig
4、nedtopossessalinearstructure.Thisgreatlysimplifieslinearoperationssuchasaveraging,principalcomponent analysis or differentiation in the space of shapes when compared to more common embedding choicessuch as the signed distance representation linked to the nonlinear Eikonal equation. The specific choi
5、ce of implicitlinear representation explored in this article is the class of harmonic functions over an annulus containing thecontour. The idea is to represent the contour as closely as possible by the zero level set of a harmonic function,thereby linking our representation to the linear Laplace equ
6、ation. Wenote that this is a local represenation withinthe space of closed curves as such harmonic functions can generally be defined only over a neighborhood of theembedded curve. We also make no claim that this is the only choice or even the optimal choice within the classof possible linear implic
7、it representations. Instead, our intent is to show how linear analysis of shape is greatlysimplified (and sensible) when such a linear representation is employedin hopes to inspire newideas and additionalresearch into this type of linear implicit representations for curves. We conclude by showing an
8、 application forwhich our particular choice of harmonic representation is ideally suited.1. 1.IntroductionIntroductionThe analysis and representation of shape is at thebasis of many visual perception tasks, from classifi-cation and recognition to visual servoing.This is avastand complex problem, whi
9、ch we have no intention ofaddressing in its full generality here. Instead, we con-centrate on a specific issue that relates to the represen-tation of closed, planar contours or compact surfacesin 3D space. Even this issue has receivedconsiderableattention in the literature. In particular, in their w
10、orkon statistical shape influence in segmentation 20,342Duci et al.Leventon et al. have proposed representing a closedplanar contour as the zero level set of a function inorder to perform linear operations such as averag-ing or principal component analysis. The contour isrepresented by the embedding
11、 function, and all op-erations are then performed on the embedded repre-sentation. They choose as their embedding functionthe signed distance from the contour (whose differen-tial structure is described by the non-linear EikonalEquation) and implement its evolution in the numer-ical framework of lev
12、el sets pioneered by Osher andSethian 27.While this general program has proven effectivein various applications, the particular choice of em-bedding function presents several difficulties, becausesigned distance functions are not a closed set underlinear operations: the sum or difference of two sign
13、eddistance functions is not a signed distance function(an immediate consequence of their nonlinear differ-ential structures). Consequently, the space cannot beendowed with a probabilistic structure in a straight-forward manner, and repeated linear operations, in-cludingincrementsanddifferentiation,e
14、ventuallyleadto computational difficulties that are not easily ad-dressed within this representation. Alternative meth-ods that possess a linear structure rely on parametricrepresentations. For instance various forms of splines6, 7, cannot guarantee that topology (or even theembeddedness) of the sha
15、pe is preserved under sig-nificant variations of the control points. Furthermore,such representations are not geometric as they dependupon an arbitrary choice of parameterization for thecontour.Geometricizedparametricrepresentationsuti-lizing the arclength parameter suffer from the samenonlinearity
16、problem as implicit representations uti-lizing the signed distance to the curve. While it ispossible to generalize the notions of mean shapes andPCAtononlinearrepresentations,especiallywhentheycan be endowed with a Riemannian structure, (seefor example 17), it is decidely more complicatedand often i
17、nvolves rather expensive computationalalgorithms.In this paper, we present a novel implicit represen-tation of shape for closed planar contours and compactsurfacesinR3thatisgeometricand explicitlydesignedto possess a (locally) linear structure. This allows lin-ear operations such as principal compon
18、ent analysis ordifferentiation to be naturally defined and easily car-ried out. The basic idea consistsof, again,representingthecontourorsurfaceasthezerolevelsetofafunction,but this time the function belongs to a linear (or quasi-linear1) space. While previous methods relied on the(non-linear) Eikon
19、al equation, ours relies on Laplaceequation,whichislinear.Ourrepresentationallowsex-ploring the neighborhood of a givenshape while guar-anteeingthatthetopologyandtheembeddednessoftheoriginalshapeispreserved,evenunderlargevariationsof the parameters in our representation (the boundaryvalues of the ha
20、rmonic function).We should point out that the primary goal here isto show through an example how a linear implicit rep-resentation of contours or surfaces can simplify (andjustify) linear operations such as averaging and prin-ciple component analysis. It is not our claim that theuse of Laplaces equa
21、tion is the optimal choice. It is,however,a well studied PDE whose known propertiesallowustoconcludevariousanalyticalandtopologicalproperties of the curves we seek to represent. Furthersome recent attention to shape analysis via Rieman-nain structures based on nonlinear representations ofcurves usin
22、g harmonic functions is presented in 29(The authors wonder, in fact, if the linear representa-tionpresentedheremaybetiedtooflocallinearizationof this representation in the neighborhood of a givenshape).WealsoshowinSection5anapplicationthatisideallysuitedforourparticularchoiceofharmonicem-bedding. Be
23、yond these considerations, however,mostof what we are illustrating in this work could carrythrough for other classes of linear or quasilinear em-bedding functions.Weintroducethesimplestformofharmonicembed-ding in Section 2, where we point out some of its diffi-culties. Wethen extend the representati
24、on to a relatedanisotropicoperator inSection3,anddiscussitsfinite-dimensional implementation in Section 4. In Section 5we show an application to measuring tissue thicknessonsegmentedmedicalimagedata.Finally,weillustratesome of the properties of this representation in Section6. While the detailed dis
25、cussion is restricted to the 2Dcase, the extension to 3D is straight-forward and obvi-ous.Wethereforewillmakenotrepeatthesamedetailsin 3D, but we will however show 3D examples in theresults section.1.1.Relation to PreviousWorkThe literature on shape modeling and representation istoo vast to review i
26、n the limited scope of this paper.It spans at least a hundred years of research in dif-ferent communities from mathematical morphologyHarmonic Embeddings for Linear Shape Analysis343to statistics, geology,neuroanatomy,paleontology,as-tronomy etc. Some of the earlier attempts to formalizea notion of
27、shape include DArcy Thompsonstreatise“Growth and Form” 32, the work of Matheron on“Stochastic Sets” 24 as well as that of Thom, Gib-lin and others 8, 31. The most common represen-tations of shape rely on a finite collection of points,possibly defined up to equivalenceclasses of group ac-tions 5, 13,
28、 19, 23. These tools have proven usefulin contexts where distinct “landmarks” are available,for instance in comparing biological shapes with dis-tinct “parts.” However,comparing objects that have adifferent number of parts, or objects that do not haveanydistinct landmark, is elusiveunder the aegisof
29、 sta-tistical shape spaces. Koenderink 18 is credited withprovidingsomeofthekeyideasinvolvedinformalizinga notion of shape that matches our intuition. However,Mumfordhascritiquedcurrenttheoriesofshapeonthegrounds that they fail to capture the essential featuresof perception 26.“Deformable Templates,
30、” pioneered by Grenander11, do not rely on “features” or “landmarks;” rather,images are directly deformed by a (possibly infinite-dimensional) group action and compared for the bestmatchinan“image-based”approach38.Anotherlineof work uses variational methods and the solution ofpartial differential eq
31、uations (PDEs) to model shapeand to compute distances and similarity.In this frame-work, not only can the notion of alignment or distancebe made precise 3, 15, 25, 28, 37, but quite sophis-ticated theories that encompass perceptually relevantaspects can be formalized in terms of the properties ofthe
32、 evolution of PDEs (e.g. 16). The work of Kimiaet al. 14 describes a scale-space that corresponds tovarious stages of evolution of a diffusing PDE, and a“reacting”PDEthatsplits“salientparts”ofplanarcon-tours by generating singularities. 14 also contains anice taxonomy of existing work on shape and d
33、efor-mation and a review of the state of the art as of 1994.The variational framework has also proven very ef-fective in the analysis of medical images 21, 22, 33,36. Although most of the ideas are developed in adeterministic setting, many can be transposed to aprobabilistic context Scale-space is a
34、 very active re-search area, and some of the key contributions asthey relate to the material of this paper can be foundin 1, 2, 12, 30 and references therein. Leventon etal. 20 perform principal component analysis in thealigned frames to regularize the segmentation of re-gionswithlowcontrastinbraini
35、mages.Similarly,35performsthejointsegmentationofanumberofimagesby assuming that their registration (stereo calibration)is given.Wepresent a novelrepresentation of shape that sup-portslinearoperations.Weonlyconsiderclosedplanarcontours, and even within this set our representationcannot capture any sh
36、ape; it does not include a notionof hierarchy or compositionality, which are crucial ina complete theory of shape. Despite its limitations thatrestrict the class of shapes and the analysis to theirglobal properties, our representation has desirable fea-tures when it comes to linear analysis. In fact
37、, it allowsus to naturally takelinear combinations of shapes; per-forming principal component analysis (PCA) on theembeddingfunctionresultsinanaturalnotionofdefor-mation on the underlying shapes. Endowing the spacewith a probabilistic structure, although not addressedin this paper,is greatly facilit
38、ated by the (quasi-)linearnature of the representation.Wenote that, although we represent a contour as thezero level set of an embedding function, our approachisnotalevelsetmethodinthetraditionalsense27:infact, in local shape analysis we are interested in guar-anteeing that changes of topology do no
39、t occur.In thissense, our approach is far less general, butin ways thatare desirable for the specific problem we address, thatof representing a neighborhood of a given shape.As we will see in Section 4, our approach relies on afinite-dimensional set of boundary values at specifiedlocations. In this
40、sense, therefore, our technique couldbe thought of as an implicit version of splines 6, 7,in the sense that changing the location of the controlpoints results in an evolution of the contour.2. 2.HarmonicHarmonic EmbeddingEmbeddingThe basic idea is to represent a closed planar con-tour, , as the zero
41、 level set of a function u thatinherits the linear structure of its embedding space.This linear space is chosen to be the set of harmonicfunctions, which naturally leads to the contour beingrepresented as the solution of certain Laplace equa-tions. More formally, consider the domain .R2= x : r |x| R
42、; we will restrict our atten-tion to contours that are contained in such a domain,for some r, R R. In particular, wesmooth contours C=.will considerC(S1,) from theunit circle to . We call the inner and outer bound-aries of , x R20 =.x R2: |x| = r and .1 =: |x| = R respectively. Each contour is344Duc
43、i et al.then represented by a function u : R, and inparticular by the value of this function in theand outer boundaries h=.innerC0(S1) C0(S1). Amongall possible u, we restrict ourfunctions, i.e. to the set H=.attention to harmonicu C() C0(u = 0.) :Definition 2.1.(Harmonic Embedding).We saythat a con
44、tour Chas an harmonic embeddingif there exists a function u Hsuch thatu(x) = 0 for x ,u(x) = 0 for x .(1)We say that the function u is an harmonic represen-tation associated to . The set of contours that admitan harmonic embedding will be indicated by Crepresents an harmonic contour. Wesay that u Hi
45、f thezero level set of u is an element of Cthe harmonic representations will be indicated. The set of allby H.In plain words, we plan to represent a contour by the values that a harmonic function u, that is zeroon the contour,takeson the inner and outer boundaries0, 1.Naturally,notallcontoursadmitah
46、armonicembedding.PropositionProposition 2.1.2.1.If Cand u Hfunction associated to , then u hasis an har-monica constantsign on each connected component of the boundary,0 and 1, where it takes opposite signs.Proof:Proof:The function u cannot be zero on the bound-ary of , because does not belong to 0
47、1and the function u is continuous. This implies that ithas constant sign on each connected component of theboundary.If u has the same sign on both the connectedcomponents of the boundary, then the zero level setmustbeemptyasaconsequenceofthemaximumprin-ciple.The relevance of this proposition is that
48、, if we as-sign negative values to u on the inner boundary andpositive values on the outer boundary, the maximumprinciple guarantees that the resulting zero level setis always simply connected. This is desirable in localshapeanalysissincewedonotwantsmallperturbationsof a contour to result in changes
49、 of topology.Note thatthis feature is quite different than traditional level setmethodsthataddressmoregeneraldeformationswherechanges of topology are desirable. Due to the unique-ness of solution to the Laplace equation, knowing u isequivalent to knowing its values at the boundaries ofthe set . Ther
50、efore, we can use as a representative of not the entire u, but the values f0and f1that u takesat the boundaries.Definition 2.2.(Boundary representation). Let hhsuch thath=.( f0, f1) h: f0 0 .(2)The elements of hset hare the harmonic shapes and wecall thethe harmonic shape space.The map : H hassociat
黑公网安备:91230400333293403D