Free(cid:2)Form Surface Registration Using Surface Signatures
`
`Sameh M(cid:2) Yamany and Aly A(cid:2) Farag
`Computer Vision and Image Processing Lab(cid:3) Electrical Engineering Dept(cid:2)
`University of Louisville(cid:3) Louisville(cid:3) KY  (cid:3) USA
`email(cid:8) yamany(cid:3)farag(cid:11)cvip(cid:2)uo(cid:2)edu
`
`Abstract
`
`This paper introduces a new free(cid:2)form surface rep(cid:2)
`resentation scheme for the purpose of fast and accu(cid:2)
`rate registration and matching(cid:3) Accurate registration
`of surfaces is a common task in computer vision(cid:3) The
`proposed representation scheme captures the surface
`curvature information(cid:4) seen from certain points and
`produces images(cid:4) called surface signatures(cid:4) at these
`points(cid:3) Matching signatures of dierent surfaces en(cid:2)
`ables the recovery of the transformation parameters
`between these surfaces(cid:3) We propose to use template
`matching to compare the signature images(cid:3) To enable
`partial matching(cid:4) another criterion(cid:4) the overlap ratio(cid:4)
`is used(cid:3) This representation scheme can be used as a
`global representation of the surface as well as a local
`one and performs near real(cid:2)time registration(cid:3) We show
`that the signature representation can be used to match
`objects in (cid:2)D scenes in the presence of clutter and oc(cid:2)
`clusion(cid:3) Applications presented include free(cid:2)form ob(cid:2)
`ject matching(cid:4) multimodal medical volumes registra(cid:2)
`tion and dental teeth reconstruction from intra(cid:2)oral
`images(cid:3)
`
`I
`
`Introduction
`
`The registration process is an integral part of com(cid:2)
`puter and robot vision systems and still presents a
`topic of high interest in both elds(cid:4) The importance
`of the registration problem in general comes from the
`fact that it is found in dierent applications including
`surface matching (cid:9) (cid:2)D medical imaging(cid:9)  (cid:9) pose
`estimation(cid:9) object recognition(cid:9) (cid:9)  and data
`fusion(cid:4)
`In order for any surface registration algorithm to
`perform accurately and eciently(cid:9) appropriate repre(cid:2)
`sentation scheme for the surface is needed(cid:4) Most of
`the surface representation schemes found in literature
`have adopted some form of shape parameterization es(cid:2)
`pecially for the purpose of object recognition(cid:4) One
`benet of the parametric representation is that the
`shape of the object is dened everywhere which en(cid:2)
`ables high level tasks such as visualization(cid:9) segmen(cid:2)
`
`This work was supported in part by grants from
`the NSF ECS(cid:3)  and the DoD under contract(cid:11)
`USNV N (cid:3) (cid:3) (cid:13)
`
`tation and shape analysis to be performed(cid:4) More(cid:2)
`over(cid:9) such representation allows stable computation of
`geometric entities such as curvatures and normal di(cid:2)
`rections(cid:4) However(cid:9) parametric representation are not
`suitable to present general shapes especially if the ob(cid:2)
`ject is not of planar(cid:9) cylindrical or toroidal topology(cid:4)
`Free(cid:2)form surfaces(cid:9) in general(cid:9) may not have simple
`volumetric shapes that can be expressed in terms of
`parametric primitives(cid:4) Dorai and Jain have dened
`a free(cid:2)form surface to be a smooth surface(cid:4) such that
`the surface normal is well dened and continuous al(cid:2)
`most everywhere(cid:4) except at vertices(cid:4) edges and cusps(cid:3)(cid:9)
`Discontinuities in the surface normal or curvature(cid:9) and
`consequently in the surface depth(cid:9) may be present
`anywhere in a free(cid:2)form surface(cid:4) Some representation
`schemes for free(cid:2)form surfaces found in literature in(cid:2)
`clude the splash representation proposed by Stein and
`Medioni (cid:9) the point signature by Chua and Jarvis 
`and COSMOS by Dorai and Jain(cid:4) Recently John(cid:2)
`son and Hebert introduced the spin image repre(cid:2)
`sentation(cid:4) Their surface representation(cid:9) comprises de(cid:2)
`scriptive images associated with oriented points on the
`surface(cid:4) Using a single point basis(cid:9) the positions of
`the other points on the surface are described by two
`parameters(cid:4) These parameters are accumulated for
`many points on the surface and result in an image at
`each oriented point which is invariant to rigid trans(cid:2)
`formation(cid:4)
`
`This paper contributes in the developement of a
`similar surface representation with the exception of
`using the curvature information rather than the point
`density to create the signature image(cid:4) Furthermore(cid:9)
`we apply a selection process to select feature points on
`the surface to be used in the matching process(cid:4) This
`reduction process solves the long registration time re(cid:2)
`ported in the literature(cid:9) especially for large surfaces(cid:4)
`Our technique starts by generating a signature image
`capturing the surface curvature information seen from
`each feature point(cid:4) This image represents a signature
`of the surface at that point due to the fact that it is
`almost unique for each point location on the surface(cid:4)
`Surface registration is then performed by matching
`signature images of dierent surfaces and hence nd(cid:2)
`ing corresponding points in each surface(cid:4) For rigid
`registration(cid:9) three point correspondences are enough
`
`0-7695-0164-8/99 $10.00 (c) 1999 IEEE
`
`Align Ex. 1021
`U.S. Patent No. 9,962,244
`
`0001
`
`

`

`P
`
`P3
`
`P1
`
`P2
`
`Up
`
`P2
`
`P
`
`P1
`
`r
`
`R
`
`P3
`
`Triangulation
`
`Simplex mesh
`
`(a)
`
`Up
`
`(b)
`
`θ
`
`P
`
`r
`
`R
`
`P1
`
`(c)
`
`Fig(cid:2) (cid:2) a Duality between triangulation and simplex mesh(cid:2) b
`The circumsphere of radius R that includes the four points(cid:2)
`c Cross section of the sphere and the calculation of the
`simplex angle(cid:2)
`
`of the surface at the point P as follows(cid:20)
`
`H (cid:21)
`
`sin


`r
`
`
`
`The idea is to use this curvature measure and cre(cid:3)
`ate a reduced representation of the surface at certain
`points(cid:2) This reduced representation encodes the cur(cid:3)
`vature values at all other points and creates an image(cid:2)
`This image is called a signature image(cid:6) for this point(cid:2)
`This is because the change in curvature values with the
`distribution of all points forming the surface relative
`to the point in study is unique(cid:2) This is not true for
`surfaces of revolution SOR(cid:2)
`The signature image is generated as follows(cid:20) As
`shown in Fig(cid:2) (cid:5) for each point P (cid:5) dened by its (cid:3)
`D coordinates and the normal (cid:3)UP (cid:5) each other point
`Pi on the surface can be related to P by two param(cid:3)
`eters(cid:20)   the distance di (cid:21) jjP (cid:3) Pijj and  the
`angle i (cid:21) cos(cid:0)
` (cid:2)UP (cid:3)P (cid:0)Pi
`jjP (cid:0)Pijj (cid:2) This is a polar imple(cid:3)
`mentation of the signature image and it can be easily
`converted into cartesian form(cid:2) Also we can notice that
`there is a missing degree of freedom in this representa(cid:3)
`tion which is the cylindrical angular parameter(cid:2) This
`parameter depends on the surface orientation which
`dees the purpose of having an orientation indepen(cid:3)
`dent representation scheme(cid:2) The size of the image
`depends on the object size but for the sake of gener(cid:3)
`alization(cid:5) each object is normalized to its maximum
`
`to estimate the transformation parameters(cid:2) This pa(cid:3)
`per is organized as follows(cid:2) The signature represen(cid:3)
`tation is described in section II(cid:2) The points selection
`process is introduced in section III and the matching
`process in section IV(cid:2) Results and discussions are given
`in section V and the paper concluded in section VI(cid:2)
`
`II Surface Signature Generation
`
`Our approach for fast registration is to establish a
`surface signature(cid:5)(cid:6) for selected points on the surface(cid:5)
`rather than just depending on the (cid:3)D coordinates of
`the points(cid:2) The idea of obtaining a signature(cid:6) at each
`surface point is not new  (cid:5)  (cid:5) (cid:2) The signature(cid:5)
`computed at each point encodes the surface curvature
`seen from this point using all other points(cid:2) This re(cid:3)
`quires an accurate measure of the surface curvature at
`the point in focus(cid:2)
`For parametric curves or surfaces(cid:5) curvature mea(cid:3)
`sures can be obtained using the Frenet Frame values
`for the case of a curve or the Weingarten Map for the
`case of surfaces (cid:2) This requires the calculation of
`curve or surface derivative which is a complex oper(cid:3)
`ation and may introduce computational errors to the
`representation scheme used(cid:2) Moreover(cid:5) such measures
`are hard to obtain for the case of unstructured free(cid:3)
`form surfaces(cid:2) Hebert  used a simplex angle to de(cid:3)
`scribe changes in a simplex mesh surface(cid:2) We use the
`simplex angle to estimate the curvature value at points
`on a free(cid:3)form surface(cid:2)
`A free(cid:3)form surface(cid:5) in its general form(cid:5) is com(cid:3)
`posed of unstructured triangular patches(cid:2) There ex(cid:3)
`ists a dual form consisting of unstructured simplex
`mesh as shown in Fig(cid:2) a(cid:2) A topological transfor(cid:3)
`mation is used to associate a k(cid:3)simplex mesh to a
`k(cid:3)triangulations or k(cid:3)manifolds(cid:2) This transformation
`works dierently for vertices and edges located at the
`boundary of the triangulation from those located in(cid:3)
`side(cid:2) The outcome of this transformation is a k(cid:3)p(cid:3)cell
`associated with a p(cid:3)face of a k(cid:3)triangulation  (cid:2) In
`this work(cid:5) a (cid:3)simplex mesh form is considered in the
`curvature calculation(cid:2) Let P be a vertex of a (cid:3)simplex
`mesh and having three neighbors P (cid:2) P(cid:2) P (cid:2) The three
`neighboring points dene a plane with normal (cid:3)UP (cid:2)
`They also lie on a circumscribe circle with radius r
`and the four points are circumscribed by a sphere with
`center O and radius R as shown in Fig(cid:2) b(cid:2) The sim(cid:3)
`plex angle

shown in Fig(cid:2) c is dened as  (cid:20)
`
`sign (cid:3)P P (cid:3)UP 
`
` 
`
`r R
`
`sin

 (cid:21)
`
`This denition is made with the assumption that the
`three neighbors are linearly independent(cid:5) thus r (cid:21) (cid:2)
`The simplex angle is related to the mean curvature H
`
`0-7695-0164-8/99 $10.00 (c) 1999 IEEE
`
`0002
`
`

`

`UP
`
`αi
`
`αj
`
`P
`
`di
`
`αi
`
`θi
`
`di
`
`d
`
`Signature image at P
`
`Pi
`
`UPi
`
`α
`
`TABLE I
`
`A at different (cid:2) their  from the total M points in
`
`the model and the time taken to obtain them on an
`
`SGI(cid:4)O
`
`Fig(cid:2) (cid:2) For each point P we generate a signature image where
`the image axis are the distance d between P and each other
`point on the surface and the angle between the normal
`at P (cid:4) (cid:3)UP and the vector from P to each other point(cid:2) The
`image encodes the simplex angle

(cid:2)
`
`Fig(cid:2) (cid:2) Examples of signature images taken at dierent point
`locations(cid:2) Notice how the image features the curvature in(cid:7)
`formation(cid:2) The dark intensity in the image represents a
`high curvature seen from the point while the light intensity
`represents a low curvature(cid:2)
`
`length(cid:2) At run(cid:3)time matching(cid:4) the scene(cid:3)image is nor(cid:3)
`malized to the maximum length of the object in study(cid:2)
`At each location in the image the simplex angle

i is
`encoded(cid:2) Ignoring the cylindrical angular degree re(cid:3)
`sults in the case where the same pixel in the image
`can represent more than one (cid:3)D point on the surface(cid:2)
`This usually occurs when the object have surfaces of
`revolution around the axis represented by the normal
`at the point P (cid:2) These points have the same di and i
`and lie on the circle that has a radius dicosi and is
`distant by disini from the point P along the axis
`(cid:3)UP (cid:2) The average of their simplex angles is encoded in
`the corresponding pixel location(cid:2)
`Figure shows some signature images taken at dif(cid:3)
`ferent points on a statue and a phone handset(cid:2) Each
`image uniquely denes the location of the point on
`the surface due to the encoded curvature information(cid:2)
`In SOR(cid:4) similar images can be obtained for dierent
`points(cid:2) This can be expected as the registration of
`SOR objects is not unique and has innite number of
`solutions(cid:2)
`
`statue
`(cid:2)
`
`
` 
` sec
`
`statue
`(cid:2)
` 
`
`
` sec
`
`speaker
`(cid:2)
`
`  
`
`sec
`
`speaker
`(cid:2)
`
`  
`
`sec
`
`
`jAj
`M
` jAj
`M
`Time
`
`III Surface Points Selection
`
`The concept of using special points for registration
`is not new(cid:2) Thirion used the same concept to reg(cid:3)
`ister multimodal medical volumes(cid:4) and he used ex(cid:3)
`tremal(cid:22) points on the volume edges or ridges(cid:2) Chua
`and Jarvis  used seeds(cid:22) points in their match(cid:3)
`ing approach(cid:2) Stein and Medioni  used only highly
`structured regions in their approach(cid:2)
`In many real life objects(cid:4) the majority of points
`forming the surface are of low curvature value(cid:2) These
`points are reduntant and do not serve as landmarks of
`the object(cid:2) In this work(cid:4) points of low curvature are el(cid:3)
`eminated and signature images are only generated for
`the set of remaing points(cid:2) A test is also performed to
`eleminate spike points that have considerable higher
`curvature than its neighbors(cid:2) These points are consid(cid:3)
`ered as noise(cid:2)
`The simplex angle is used as a criterion to reduce
`the surface points and use only a subset A S in the
`registration process(cid:4) where S is the set of the simplex
`mesh points(cid:2)The subset A is dened with respect to a
`threshold  such that A contains the landmark regions
`of the surface(cid:2)
`
`A (cid:24) fPi  Sj
`
`jsin

ij  (cid:5)   g
`
` 
`
`Figure  shows two examples of objects and their
`scanned models(cid:2) Figure  shows the reduced set of
`points A obtained for each model using dierent 
`and table I summarizes the values obtained(cid:2) With low
`threshold values(cid:4) more details about the object model
`are considered with considerable reduction in the set
`cardinality(cid:2) Even with higher threshold values(cid:4) most
`of the landmarks of the object are still present in the
`set A(cid:2)
`There are two cases(cid:4) however(cid:4) where the above anal(cid:3)
`ysis will fail(cid:2) The rst is when the surface is a plane
`or is a piece(cid:3)wise dened surface e(cid:2)g(cid:2) a cube(cid:2) In this
`case for any  the set A will be empty(cid:2) This can
`be deduced from Fig(cid:2) c when P falls in the plane
`formed by its neighbors(cid:2) In this case there exists no
`
`0-7695-0164-8/99 $10.00 (c) 1999 IEEE
`
`0003
`
`

`

`matching(cid:6) hence reducing the time taken to nd accu(cid:8)
`rate transformation(cid:3) The developed matching engine
`should be simple based on the fact that the signature
`images of corresponding points should be identical in
`their content(cid:3) Yet(cid:6) due to the fact that (cid:8)D scanning
`sensors are noisy in nature and that the (cid:8)D scene
`may contain clutter or suer from partial occlusion(cid:6) a
`robust matching criteria is needed(cid:3) One such criteria
`is template matching in which a measure denes how
`well a portion of an image matched a template(cid:3) Let
`gi(cid:2) j be one of our scene signature images and ti(cid:2) j
`one of the library object or original surface signature
`templates and let D be the domain of denition of the
`template(cid:3) Then a measure of how well a portion of
`the scene image matches the template can be dened
`as  (cid:17)
`
`M m(cid:2) n (cid:4) X
`j(cid:2)
`
`X
`i(cid:2)i(cid:0)m(cid:2)j(cid:0)nD
`
`jgi(cid:2) j (cid:2) ti (cid:2) m(cid:2) j (cid:2) nj(cid:3)
`
`
`For surface signature matching(cid:6) translation is not
`needed as the corresponding signature images have
`the same origin point at (cid:6) which means that only
`M (cid:2)  is calculated(cid:3) Another more discriminating
`measure(cid:6) based on the standard Euclidean distance(cid:6)
`can be(cid:17)
`
`jgi(cid:2) j (cid:2) ti(cid:2) jj(cid:3)
`
`
`
`X
`iD
`
`X 
`
`j(cid:2)
`
`D
` N
`
`E
`n (cid:4)
`
`where ND is the total number of pixels in the domain
`D(cid:3) The domain D is dened over the template size(cid:3)
`To enable partial matching(cid:6) the matching measure is
`augmented by adding the overlap ratio O (cid:4) Do
`D (cid:6) where
`Do is the domain of the overlapping pixels(cid:3) Figure 
`shows an example of two objects with known trans(cid:8)
`formation parameters and another example where al(cid:8)
`most half of the object is missing(cid:3) Table II shows that
`reducing the size of the signature image leads to a de(cid:8)
`crease in the number of correct points correspondence
`which means that more points are needed(cid:3) Yet(cid:6) the
`reduction in time with the smaller size is more suit(cid:8)
`able for real(cid:8)time applications(cid:3) It should be noticed
`that more reduction in the signature image size may
`lead to incorrect matching due to the averaging pro(cid:8)
`cess(cid:3) The end result of the matching process is a list
`of groups of likely three point correspondences that
`satisfy the geometric consistency constraint(cid:3) The list
`is sorted such that correspondences that are far apart
`are at the top of the list(cid:3) A rigid transformation is
`calculated for each group of correspondences and the
`verication is performed using a modied ICP tech(cid:8)
`nique (cid:3) Groups are ranked according to their veri(cid:8)
`cation scores(cid:6) and the best group is rened using the
`modied ICP technique(cid:3)
`
`Fig(cid:2) (cid:2) Top Two examples of real objects(cid:6) a statue and a
`speaker(cid:2)
`Bottom Rendered views of the scanned (cid:8)D
`model of the objects(cid:2) The statue (cid:8)D model consists of
` patches and the speaker (cid:8)D model consists of  
`patches(cid:2)
`
` (c)
`
`(a) (b) (d)
`
`Fig(cid:2) (cid:2) The reduced set of points obtained for the statue and
`speaker models using a  (cid:14) (cid:2)(cid:6) b  (cid:14) (cid:2) (cid:6) c  (cid:14) (cid:2)
`and d  (cid:14) (cid:2) (cid:2)
`
`sphere circumscribing the four points i(cid:3)e(cid:3) R (cid:4) (cid:6)
`thus H (cid:4) (cid:3) The second case is when the surface is
`part of a spherical(cid:6) cylindrical or toroidal shape(cid:3) In
`this case the curvature measure will be constant over
`the surface(cid:3) Fortunalty(cid:6) in either cases(cid:6) these surfaces
`can be easily parameterized and the transformation
`parameters can be analytically recovered(cid:3)
`
`IV Signature Matching
`
`The next step in the registration process is to
`match corresponding signature images of two sur(cid:8)
`facesobjects or between a (cid:8)D scene and objects in
`a library(cid:3) The ultimate goal of the matching process
`is to nd at least three points correspondence to be
`able to calculate the transformation parameters(cid:3) The
`benet of using the signature images to nd the corre(cid:8)
`spondence is the use of image processing tools in the
`
`0-7695-0164-8/99 $10.00 (c) 1999 IEEE
`
`0004
`
`

`

`Fig(cid:2) (cid:2) The signature matching enabled fast recovery of the
`transformation parameter between these two models(cid:2)
`
`1
`
`Occlusion
`
`clutter
`
`Statue Signature
`Template (ST)
`Statue ST
`E
`O
`
`n2
`
`Signature 1
`
`0.008 0.9
`
`Signature 2
`
`0.3712 0.899
`
`Speaker Signature
`Template (ST)
`
`Speaker ST
`E
`O
`
`n2
`
`Signature 3
`
`1.773 0.558
`
`Signature 4
`
`0.01 1.0
`
`2
`
`3
`
`4
`
`Occlusion
`
`clutter
`
`Scene
`Signature
`
`Signature
`Template
`
`Fig(cid:2) (cid:2) Illustration of the eect of scene clutter and occlusion
`on the signature matching(cid:2)
`
`the (cid:2)D scenes are scanned using a Cyberware
`laser scanner with a resolution of mm(cid:3) Some models
`e(cid:3)g(cid:3)
`the duck(cid:5) bell and cup were obtained from a
`CADCAM library(cid:3) Table III shows the time needed
`to match objects in a scene using their signature tem(cid:2)
`plates(cid:3) We compared the performance of our approach
`with the ICP and the spin image approaches(cid:3) For the
`case of matching the statue object(cid:5) it took  sec(cid:2)
`onds using the ICP and   seconds using the spin
`image(cid:3) Applying the feature points selection process
`with the spin image(cid:5) it took  seconds to match
`the object(cid:3) This is due to the fact that we needed
`more feature points to match the spin image com(cid:2)
`pared to the points needed to match the signature
`image(cid:3) The second application is multimodal medi(cid:2)
`
`(a) (b)
`
`Fig(cid:2) (cid:2) a case (cid:7) Two telephone handsets with known transfor(cid:8)
`mation parameters(cid:2) Notice how similar are the correspond(cid:8)
`ing signature images(cid:2) b case (cid:7) Part of a telephone hand(cid:8)
`set(cid:10) almost  of the original model(cid:10) and example of the
`corresponding signature images(cid:2) Partial matching is needed
`to establish the correspondence(cid:2)
`
`Comparison in matching for different signature image
`
`TABLE II
`
`sizes
`
`A XA
`image size
` of Correct
`matching
`Reg(cid:2) time
`
`case
` X 
` X 
`X
`
`
`
`case 
` X
` X 
`X
` 
`
`
`sec
`
`sec
`
` sec
`
` sec
`
`V Results and Discussions
`
`We used the signature implementation in three ap(cid:2)
`plications(cid:3) The rst is object registration(cid:5) an exam(cid:2)
`ple of which is shown in Fig(cid:3)  where two dierently
`scanned objects are matched together(cid:3) The signature
`registration was successful in recovering the transfor(cid:2)
`mation parameters(cid:3) Also the signature representation
`was used in matching objects in a (cid:2)D scene with their
`corresponding models in a library(cid:3) The proximity of
`the objects in the scene creates large amounts of clut(cid:2)
`ter and occlusion(cid:3) These contribute to extra andor
`missing parts in the signature images(cid:3) Using the sig(cid:2)
`nature polar representation(cid:5) the eect of clutter(cid:5) for
`many points(cid:5) is only found in the third andor fourth
`quadrant of the image as shown in Fig(cid:3) (cid:3) Examples of
`such application is shown in Fig(cid:3) (cid:3) Using the signa(cid:2)
`ture matching criterion(cid:5) all of the models in the scene
`are simultaneously matched and localized in their cor(cid:2)
`rect scene positions(cid:3) The models in the library and
`
`0-7695-0164-8/99 $10.00 (c) 1999 IEEE
`
`0005
`
`

`

`Approx(cid:2) matching Time in Recognition on an SGI(cid:3)O
`
`TABLE III
`
`model
`Statue
`Speaker
`Bottle
`Duck
`Cup
`Bell
`Dino
`Tiger
`Tank
`Pin
`
` points matching time sec(cid:2)
`
` 
`  
`
` 
`
` 
`
` 
`
`
`
` 
`
` 
`
`
`
`
`
`
`cal image registration as shown in Fig(cid:2) a(cid:2) The red
`surface represents the skin model reconstructed from
`the MR data and the grey represents the skin model
`obtained from the CT(cid:2) These models where obtained
`using a deformable contour algorithm that nds the
`outer contour in each slice and reconstructs a D mesh
`by connecting these contours(cid:2) As the skin is mod(cid:9)
`eled dierently in the two image modalities(cid:11) surface
`registration will only produce an initial registration(cid:2)
`Other techniques like maximizing the mutual informa(cid:9)
`tion MI   can be used to enhance the result(cid:2) The
`registration using signature and MI was much faster
`than using MI alone  (cid:2) The third application(cid:11) shown
`in Fig(cid:2) b(cid:11) is in the dental teeth reconsturction (cid:11)
`(cid:2) The overall purpose of this system is to develop a
`model(cid:9)based vision system for orthodontics to replace
`traditional approaches that can be used in diagnosis(cid:11)
`treatment planning(cid:11) surgical simulation and for im(cid:9)
`plant purposes(cid:2)
`Image acquisition is obtained using
`intra(cid:9)oral video camera and range data are obtained
`using a D digitizer arm(cid:2) A shape from shading tech(cid:9)
`nique is then applied to the intra(cid:9)oral images(cid:2) The
`required accurate orthodontic measurements cannot
`be deduced from the resulting shape(cid:11) hence the need
`of some reference range data to be integrated with the
`shape from shading results(cid:2) An neural network fu(cid:9)
`sion algorithm  is used to integrate the shape from
`shading results and the range data(cid:2) The output of the
`integration algorithm to each teeth segment image is
`a description of the teeth surface in this segment(cid:2) The
`registration technique is then performed to register the
`surfaces from dierent views together(cid:2)
`
`VI Conclusions
`
`This paper proposed a new surface representation
`of free(cid:9)form surfaces and objects(cid:2) The proposed rep(cid:9)
`resentation reduces the complexity of the registration
`and matching problems from the (cid:9)D space into the (cid:9)
`D image space(cid:2) This was done by capturing the surface
`curvature information seen from feature points on the
`
`Objects Library
`
`Scene mesh
`
`Results of matching
`
`Intensity Image
`
`
`
`Scene mesh
`
`
`
`Results of Matching
`
`Fig(cid:2) (cid:2) Examples of using the signature representation in object
`matching(cid:2) A library of objects is used(cid:2) Some of these
`objects were scanned using a Cyberware laser scanner
`with a resolution of mm(cid:2) Others are obtained from CAD
`libraries(cid:2)
`
`0-7695-0164-8/99 $10.00 (c) 1999 IEEE
`
`0006
`
`

`

`
`
`puter Vision (cid:10) pp(cid:2)  (cid:10) (cid:2)
`J(cid:2)(cid:7)P(cid:2) Thirion(cid:10) Extremal points(cid:18) Denition and application
`to d image registration(cid:10)(cid:12) IEEE conf on Computer Vision
`and Pattern Recognition (cid:10) (cid:2) Seatle(cid:2)
`  A(cid:2) Gueziec and N(cid:2) Ayache(cid:10) Smoothing and matching of (cid:7)
`d space curves(cid:10)(cid:12) International Journal of Computer Vision
`  (cid:10) pp(cid:2)   (cid:10) (cid:2)
` S(cid:2) Lavallee and R(cid:2) Szeliski(cid:10) Recovering the position and
`orientation of free(cid:7)form objects from image contours using
` d distance maps(cid:10)(cid:12) IEEE Transactions on Pattern Analy(cid:2)
`sis and Machine Intelligence (cid:10) pp(cid:2)  (cid:10) April (cid:2)
` C(cid:2) Dorai and A(cid:2) K(cid:2) Jain(cid:10) Cosmos(cid:7)a representation scheme
`for d free(cid:7)form objects(cid:10)(cid:12) IEEE Transactions on Pattern
`Analysis and Machine Intelligence (cid:10) pp(cid:2)  (cid:10) Oc(cid:7)
`tober (cid:2)
` C(cid:2) S(cid:2) Chua and R(cid:2) Jarvis(cid:10)  d free(cid:7)form surface registration
`and object recognition(cid:10)(cid:12) International Journal of Com(cid:2)
`puter Vision (cid:10) pp(cid:2)  (cid:10) (cid:2)
` A(cid:2) Johnson and M(cid:2) Hebert(cid:10) Surface matching for object
`recognition in complex three(cid:7)dimensional scenes(cid:10)(cid:12) Image
`and Vision Computing (cid:10) pp(cid:2)   (cid:10) (cid:2)
` R(cid:2) Bergevin(cid:10) D(cid:2) Laurendeau(cid:10) and D(cid:2) Poussart(cid:10) Registering
`range views of multipart objects(cid:10)(cid:12) Computer Vision and
`Image Understanding  (cid:10) pp(cid:2)  (cid:10) January (cid:2)
`  F(cid:2) Stein and G(cid:2) Medioni(cid:10) Structural indexing(cid:18) Ecient
` (cid:7)d object recognition(cid:10)(cid:12) IEEE Trans(cid:3) Patt(cid:3) Anal(cid:3) Machine
`Intell(cid:3) (cid:10) pp(cid:2)  (cid:10) (cid:2)
`  C(cid:2) S(cid:2) Chua and R(cid:2) Jarvis(cid:10) Point signatures(cid:18) A new repre(cid:7)
`sentation for d object recognition(cid:10)(cid:12) Internation Journal
`of Computer Vision  (cid:10) pp(cid:2)  (cid:10) (cid:2)
`  J(cid:2) Opera(cid:10) Dierential Geometry and its Applications(cid:10)
`Prentice Hall(cid:10) (cid:2)
`  M(cid:2) Hebert(cid:10) K(cid:2) Ikeuchi(cid:10) and H(cid:2) Delingette(cid:10) A spherical
`representation for recognition of free(cid:7)form surfaces(cid:10)(cid:12) IEEE
`Trans(cid:3) Patt(cid:3) Anal(cid:3) Machine Intell(cid:3) (cid:10) p(cid:2)  (cid:10) (cid:2)
`  H(cid:2) Delingette(cid:10) Simplex meshes(cid:18) a general representation
`for d shape reconstruction(cid:10)(cid:12) Tech(cid:2) Rep(cid:2)  (cid:10) Unite de
`recherche INRIA Sophia(cid:7)Antipolis(cid:10)  route des Luciols(cid:10)
`BP (cid:10)  Sophia(cid:7)Antipolis Cedex France(cid:10) Mars (cid:2)
`  H(cid:2) Delingette(cid:10) M(cid:2) Hebert(cid:10) and K(cid:2) Ikeuchi(cid:10) Shape represen(cid:7)
`tation and image segmentation using deformable surfaces(cid:10)(cid:12)
`Image and Vision Computing (cid:10) pp(cid:2)  (cid:10) April (cid:2)
`  R(cid:2) O(cid:2) Duda and P(cid:2) E(cid:2) Hart(cid:10) Pattern Classication and
`Scene Analysis(cid:10) John Wiley and Sons(cid:10)  (cid:2)
`  S(cid:2) M(cid:2) Yamany(cid:10) M(cid:2) N(cid:2) Ahmed(cid:10) and A(cid:2) A(cid:2) Farag(cid:10) A new
`genetic(cid:7)based technique for matching d curves and sur(cid:7)
`faces(cid:10)(cid:12) Pattern Recognition  (cid:10) p(cid:2)  (cid:10) (cid:2)
`  W(cid:2) M(cid:2) Wells(cid:10) P(cid:2) Viola(cid:10) H(cid:2) Atsumi(cid:10) S(cid:2) Nakajima(cid:10) and
`R(cid:2) Kikinis(cid:10) Multi(cid:7)modal volume registration by maxi(cid:7)
`mization of mutual information(cid:10)(cid:12) Medical Image Analysis
` (cid:10) pp(cid:2) (cid:10) March (cid:2)
`  A(cid:2) Eldeib(cid:10) S(cid:2) M(cid:2) Yamany(cid:10) and A(cid:2) A(cid:2) Farag(cid:10) Multi(cid:7)
`modal medical volumes fusion by surface matching(cid:10)(cid:12) nd
`International Conference on Medical Image Computing
`and Computer(cid:2)Assisted Intervention MICCAI(cid:8) (cid:11) Cam(cid:2)
`bridge(cid:11) England (cid:10) Sept (cid:2)
`  M(cid:2) Ahmed(cid:10) S(cid:2) M(cid:2) Yamany(cid:10) E(cid:2) E(cid:2) Hemayed(cid:10) S(cid:2) Roberts(cid:10)
`S(cid:2) Ahmed(cid:10) and A(cid:2) A(cid:2) Farag(cid:10)  d reconstruction of the hu(cid:7)
`man jaw from a sequence of images(cid:10)(cid:12) Proc(cid:3) IEEE Comp(cid:3)
`Vis(cid:3) and Patt(cid:3) Recog(cid:3) CVPR(cid:11) Puerto Rico (cid:10) pp(cid:2)  (cid:10)
` (cid:2)
` S(cid:2) M(cid:2) Yamany(cid:10) A(cid:2) A(cid:2) Farag(cid:10) D(cid:2) Tazman(cid:10) and A(cid:2) G(cid:2) Farman(cid:10)
`A robust (cid:7)d reconstruction system for human jaw mod(cid:7)
`eling(cid:10)(cid:12) nd International Conference on Medical Image
`Computing and Computer(cid:2)Assisted Intervention MIC(cid:2)
`CAI(cid:8) (cid:11) Cambridge(cid:11) England (cid:10) Sept (cid:2)
`  M(cid:2) G(cid:2)(cid:7)H(cid:2) Mostafa(cid:10) S(cid:2) M(cid:2) Yamany(cid:10) and A(cid:2) A(cid:2) Farag(cid:10) In(cid:7)
`tegrating shape from shading and range data using neu(cid:7)
`ral networks(cid:10)(cid:12) Proc(cid:3) IEEE Int(cid:3) Conf(cid:3) Comp(cid:3) Visi(cid:3) Patt(cid:3)
`Recog(cid:3) CVPR (cid:10) June (cid:2) Fort Collins(cid:10) Colorado(cid:2)
`
`Overlaped CT/MRI
`before Registration
`
`Overlaped CT/MRI
`after Registration
`
`(a) Multimodal Volume Registration
`
`Two Intra−
`Oral Images
`
`Output of the
`SFS and Data
`Fusion Process
`
`Resluting tooth
`mesh after
`registration
`
`(b) Registration in Dental Application
`
`Fig(cid:2) (cid:2) Application of the signature representation for a Mut(cid:7)
`limodal medical volume registration and b teeth recon(cid:7)
`struction from intra(cid:7)oral images
`
`surface and encoding it into a signature image(cid:2) Reg(cid:3)
`istration and matching were performed by matching
`corresponding signature images(cid:2) The signature im(cid:3)
`ages were only generated for selected feature points(cid:2)
`The results show a reduction in the registration and
`matching time compared to other known techniques(cid:4)
`a major requirement for real(cid:3)time applications(cid:2) Ap(cid:3)
`plications included free(cid:3)form object matching(cid:4) multi(cid:3)
`modal medical volumes registration and dental teeth
`reconstruction from intra(cid:3)oral images(cid:2) Currently(cid:4) we
`are exploiting the use of the signature representation
`in scale independent object matching(cid:2) Regions of same
`curvature can be detected and segmented in the sig(cid:3)
`nature image and scale can be recovered by observing
`the inter(cid:3)relationship between segmented curvature re(cid:3)
`gions in dierent signature images(cid:2) Future research in(cid:3)
`cludes studying the eect of shape deformation on the
`signature representation and modeling the change in
`the signature image with a deformation model(cid:2) This
`will enable the signature representation to be used in
`non(cid:3)rigid registration(cid:2)
`
`References
`
`  Z(cid:2) Zhang(cid:10) Iterative point matching for registration of free(cid:7)
`form cur