Nicolas Bonneel

David Coeurjolly

Pierre Gueth

Jacques-Olivier Lachaud

Mumford-Shah Mesh Processing using the Ambrosio-Tortorelli Functional

Denoising (c) Inpainting (d) Segmentation (e) Embossing Figure 1: Our discretization of the MS functional along with our new vertex projection technique allows for applications such as mesh denoising, segmentation, inpainting and normal map embossing. (b) Our method removes heavy noise while preserving sharp features shown in yellow. (c) We remove vertices highlighted in cyan from the original mesh (a): our method finds sharp features (shown in yellow) and sucessfully inpaints the missing area. (d) We decompose the original mesh (a) into piecewise smooth segments whose boundaries are characterized by sharp features shown on edges in red. (e) We emboss a normal map into the mesh vertices.

Introduction

The Mumford-Shah (MS) functional, originally intended for image segmentation [MS89], is a well-known functional which models an image as a piecewise-smooth function. Minimizing this functional recovers both a piecewise-smooth image that can be useful for applications such as image denoising, and the set of discontinuities can be useful for edge detection. Since the nineties, this model has seen a tremendous success in image processing and has found many applications from image segmentation [START_REF] Tsai | Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[END_REF][START_REF] Vese | A multiphase level set framework for image segmentation using the Mumford and Shah model[END_REF] to denoising [START_REF] Tsai | Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[END_REF], inpainting [ES02], magnification [START_REF] Tsai | Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[END_REF], deblurring [BSK06] or registration [START_REF] Ben- | Stereo matching with Mumford-Shah regularization and occlusion handling[END_REF]. This functional has however attracted little attention in geometry processing, where similar problems are encountered. Notable ex-ceptions include the work of Zhang et al. [ZZWC12] that makes use of a convexified version of the MS model for mesh segmentation, and the finite element method of Tong and Tai [TT16] to construct feature lines on meshes. This lack of interest might have come from several challenges that need to be overcome. First, the model itself is not suited to a computational resolution. Hence, numerical methods only solve approximate MS models. Second their computational complexity makes algorithms tuned for regular grids difficult to scale to large unstructured meshes. Third, the MS formulation, once adapted to manifolds, exhibits differential operators that need careful handling when discretized over triangular meshes. Last, the MS model represents a piecewise-smooth scalar function over a domain; it is thus not obvious what this function should be in the context of mesh processing and for which applications.

Fortunately, recent progress on the first two issues allows to paint a brighter picture. On the computational side, various approximations of the MS functional have recently been proposed. In this paper, we are interested with an accurate approximation of the MS functional: the Ambrosio-Tortorelli's functional [AT90]. Recent advances have further made calculus on meshes practical and affordable. In particular, Discrete Exterior Calculus (DEC) [Hir03] has become popular for easily formulating and solving differential equations on meshes. We will formulate the MS functional as a discrete AT model in the language of DEC, in the spirit of the method of Coeurjolly et al. [CFGL16].

Regarding the choice of scalar function to use in the MS functional, it obviously depends on the targeted applications. For our applications, we take advantage of our DEC formulation to consider each component of the normal vector at each point of the surface as a 0-form stored on the faces of a dual mesh. This results in a set of three scalar functions, generalizing MS to vector functions [START_REF] Focardi | Asymptotic analysis of ambrosiotortorelli energies in linearized elasticity[END_REF]. We will jointly minimize MS over these three scalar functions. Overall, this essentially allows to smooth out the normals of an input mesh so they better match the underlying continuous surface being approximated while preserving mesh discontinuities.

Benefitting from these advances, we formulate a set of classical mesh processing problems using the MS functional applied to the manifold's normal vector field. From the resulting regularized normal vector field, we further introduce a shape optimization routine as an easy-to-implement projection operator which deforms the geometry so that geometric normals match the obtained regularized normals. We illustrate our method on a number of applications, such as mesh denoising, normal map embossing, mesh inpainting and mesh segmentation.

Related work

The Mumford-Shah Model. Mumford and Shah described a functional representing an input image by a piecewise-smooth approximation [MS89]. This functional reads:

MS[u,C] = α Ω (u -g) 2 dx + β Ω\C |∇u| 2 dx + γ C ds , (1)
with g the input image on a two-dimensional planar domain Ω, u its (unknown) approximation, and C a set of (unknown) curves describing the set of discontinuities. The parameters of the model intuitively model the tightness α of the approximation to the input image, the smoothness β of the approximation, and the length of discontinuities γ. While for segmentation purpose, it is often assumed that C forms a closed curve or is the boundary of some partition of the space, this is not a requirement of the model nor the optimal solution to it. In addition, this model is not restricted to images: in the general case, Ω need not be a plane and can be an arbitrary surface, and g a real-valued function over this surface.

Unfortunately, except in limited scenarios, this functional is nonconvex and very difficult to optimize.

Optimizing the MS functional. To avoid these difficulties, various approximations to MS have been proposed, and among them, the most natural ones are convex enveloppes or convex approximations to MS functional. When restricting the problem to fore-ground / background extraction, the MS functional can be convexified by replacing the term accounting for the length of segment boundaries by the total variation of the gradient of a segment binary indicator function [CEN06]. Instead of a piecewise-smooth assumption, this assumes a piecewise constant function and precludes open segment boundaries or isolated discontinuities. This can be extended to multiple segments but still necessarily produces disjoint sets. While this assumption can be appropriate for certain segmentation applications and has indeed been sucessfully used for mesh segmentation [ZZWC12], this may not be suitable in our context where our function of interest is the normal field that varies relatively smoothly across the surface [ZZWC12] and may exhibit internal discontinuities (see Fig. 5, first row). Similarly, Tsai et al. [START_REF] Tsai | Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[END_REF] directly optimize the MS functional using level sets, but also requires closed segments boundaries. These approaches thus lack the generality we are targeting. We instead resort to an early approximation from Ambrosio and Tortorelli [AT90] that relies on Γ-convergence results, and provably converges towards the MS functional. Its numerical optimization is nonetheless far from being trivial. For instance, Chambolle and Dal Maso [START_REF] Chambolle | Discrete approximation of the mumford-shah functional in dimension two[END_REF] and Bourdin and Chambolle [START_REF] Bourdin | Implementation of an adaptive finite-element approximation of the mumford-shah functional[END_REF] employ a Finite Element Method with adaptive mesh refinement and edge alignment is required for its optimization. Even with such advanced technique, these numerical methods are very sensitive to noise [START_REF] Foare | Image restoration and segmentation using the ambrosio-tortorelli functional and discrete calculus[END_REF]. Fortunately, new discretization schemes for the Ambrosio-Tortorelli (AT) model have been designed on grids [FLT16, CFGL16] and do not require FEM anymore nor adaptive mesh to get piecewise smooth solutions. This discretization has seen applications for image restoration [START_REF] Foare | Image restoration and segmentation using the ambrosio-tortorelli functional and discrete calculus[END_REF] and feature extraction on voxel-based digital geometries [CFGL16]. A first discrete differential calculus version of AT has been employed by Pokrass et al. [PBB11] to solve the partial matching of non-rigid 3D shapes. Their discretization is different from ours since discontinuities and values live on vertices, while the cross-term is evaluated on faces, resulting in smoother features. This is fine for their specific objective but limits its range of applications. In contrast our approach allows coarse-to-fine detection of features for a variety of geometry processing tasks. An alternative finite element discretization of AT has been recently proposed for triangle meshes [TT16]. This approach is the closest one to our formulation but it is not able to recover piecewise smooth patchs on noisy data as illustrated in Figure 2. We propose a specific Discrete Exterior Calculus discretization of this functional, which achieves sharper and more robust features, as we show in our experiments.

Applications in image processing. The MS functional originated from the image processing community as a way to represent an image as a piecewise-smooth function. In the last 40 years, it has led to numerous applications, even if most of the time it is only simpler variants of the MS functional that are solved. Image segmentation [TYW01, VC02] and denoising [START_REF] Tsai | Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[END_REF] are the two main applications that directly follow from the variables being optimized for (that is, discontinuity boundaries and piecewise smooth approximations). Image inpainting [ES02] is rendered possible by removing the data attachment term inside the inpainted area. A 3x image magnification [START_REF] Tsai | Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[END_REF] is performed by interlacing the input image in a 3x upsampled grid, and inpainting the missing pixel values. Bar deconvolution method with piecewise smoothness prior. Similarly, Ben-Ari and Sochen integrate the MS model in a stereo-matching functional, resulting in piece-wise smooth disparity maps [START_REF] Ben- | Stereo matching with Mumford-Shah regularization and occlusion handling[END_REF].

We believe the MS model has the potential to produce a similar number of applications in geometry processing, and this paper presents an initial set of applications.

Variational methods in mesh processing. Variational methods for mesh processing have long been studied. A variational method optimizes a given functional over a space of functions. The most common examples of such functionals used in mesh processing include Lloyd's functional [START_REF] Cohen-Steiner D | Variational shape approximation[END_REF], Total Variation [ZWZD15], the variational problem associated with the Poisson equation [YZX * 04], the curvature energy [START_REF] Zorin | Curvature-based energy for simulation and variational modeling[END_REF] or the MS functional [CFGL16,ZZWC12]. Individual mesh processing applications have their own set of priors, hypotheses and constraints, and it is illusory to search for an all-purpose functional. However, we show that the MS functional appropriately solves a number of problems and is of value to the geometry processing community.

Discretizing Mumford-Shah over Surfaces

This section describes our model for mesh processing, that extends the model of Coeurjolly et al. [CFGL16] tailored for voxel-based geometries. In particular, we briefly discuss the AT approximation, and expose our discretization over triangular meshes within the DEC framework.

Ambrosio-Tortorelli's Approximation

Ambrosio and Tortorelli reformulates the MS functional [AT90] by working on a smoothness indicator function rather than the set of discontinuities C. This indicator function, denoted by v in the following, is optimized such that it takes the value v(x) = 1 wherever g(x) is smooth, and v(x) = 0 on discontinuities. Therefore we call it the feature function. In their model, this function v is smooth and kept close to 1 where g is smooth, and its oscillations are prevented by keeping ∇v close to 0. Their functional can be written as follows:

ATε[u, v] = Ω α(u -g) 2 + |v∇u| 2 + λ ε|∇v| 2 + λ ε (1 -v) 2 4 dx . (2)
This functional now depends on the same parameters α and λ (β is set to 1 without loss of generality), but also requires a parameter ε. Parameter λ is still such that 1/λ represents the length of discontinuities, and parameter ε controls the smoothness of the feature v. Ambrosio and Tortorelli proved that when ε tends to zero, minimizers of this functional exactly corresponds to those of the MS functional. However, the problem is now quasi convex, and the integration domain is fixed and does not involve unknown curves.

Minimizing the Energy

For a fixed ε, since the energy (2) is quasi convex, we can minimize it by alterning minimizations over u and v. We follow the AT energy formulation proposed in [CFGL16]. The feature scalar field v is discretized as a primal 0-form, that is a collection of scalar values associated with each vertex of the mesh. The normal vector fields (both u and g) are each discretized as three dual 0-forms, one for each coordinate of the R 3 embedding space. Note that Focardi and Iurlano showed that AT in the vectorial case also converges towards an approximation of MS [START_REF] Focardi | Asymptotic analysis of ambrosiotortorelli energies in linearized elasticity[END_REF]. Each of those three dual 0-forms can be seen as a scalar value associated with each primal face (or dual vertex) of the mesh. Denoting d and d the primal and dual exterior derivatives, it follows that dv is a primal 1-form and du corresponds to three dual 1-forms. Norms are induced by the natural inner products between k-forms. We rewrite then the AT functional as a sum of inner products on primal and dual 0 and 1-forms:

ATε[u, v] =α u -g, u -g 0 + v du, v du 1 + λ ε dv, dv 1 + λ 4ε 1 -v, 1 -v 0 . (3)
Note that we have discretized (2) such that our feature function v does not not become identically one when epsilon tends to 0, and remains zero around feature edges. To achieve such discontinuities, the function v acts as a rescaling of the derivatives of u and not as a rescaling of the squared gradient norm. Hence it operates directly on edges in (3) and it does not operate on vertices as would give a standard DEC discretization of (2). Our discretization of AT is thus more related to discontinuous FEM than to continuous and linear basis elements. For instance, the FEM approach of Tong and Tai [TT16] oversmoothes features (function v becomes almost 1 everywhere) and requires post-processing to find its valleys.

We write the ATε energy in matrix form, using the following no- tations using thec classical discrete exterior calculus (DEC) framework where the dual vertices are circumcircle of primal triangles [START_REF] Crane | Digital geometry processing with discrete exterior calculus[END_REF]: the Hodge star i is written as the diagonal matrix S i , the vector diagonalization operator is denoted by Diag, differential operators d 0 and d1 are respectively denoted by matrices A and B, and the matrix M is the operator averaging incident 0-form values at each 1-cell (M := abs(A)/2). We thus have:

ATε[u, v] =α(u -g) T S 0(u -g) + u T B T Diag(Mv)S 1 Diag(Mv)Bu + λ ε v T A T S 1 Av + λ 4ε (1 -v) T S 0 (1 -v). (4)
The cross term can indifferently be written with the vectors v or u inside or outside the inner product. Observe that the energy gradient with respect to u (5) (resp. v (6)) is a linear operator with respect to u (resp. v). Thus the alternating minimization method amounts to alternating between the resolution of the following linear systems:

∇uATε[u, v] = 0 ⇔ α S 0 -B T Diag(Mv)S 1 Diag(Mv)B u = α S 0 g, (5
)

∇vATε[u, v] = 0 ⇔ λ 4ε S 0 + λ ε A T S 1 A + M T Diag(Bu)S 1 Diag(Bu)M v = λ 4 ε S 0 , (6)
As long as the diagonal Hodge stars S 0 and S 0 are nondegenerate, the left-hand sides are full rank, yielding a unique minimum at each iteration. It is a known result in convex analysis linked to block coordinate descent algorithms [Ber99, Prop. 2.7.1], that these iterations must converge to a stationary point of ATε.

Convergence and stability are improved by progressively reducing ε rather than directly solving the problem with a small ε. We hence perform the above minimization repeatedly, dividing ε by 2 at each iteration (we typically start at ε 0 = 2 and decrease until ε = 0.25). This allows to better infer the general position of features at a coarse scale (large ε), and then to better precisely delineate them at a fine scale (small ε). This coarse-to-fine optimization is especially important in the inpainting case, where the value of ε 0 should be around the radius size of the inpainted region.

Deforming a Mesh to a Prescribed Normal Field

Given a regularized normal field u over an input mesh (e.g., given by a first AT minimization), we wish to deform the mesh by moving its vertices such that the triangles normal vectors match the prescribed normal field u. We perform this operation by minimizing an energy E consisting of three terms: a normal matching term Em, a fairness term E f , and a data attachment term E d , described in this section. Note that some terms may appear in various forms in other works [Tau01, FDCO03, PAH * 07, SRML07]. We describe them for self-containedness and propose a fairness energy to take into account the feature field. Our method then proceeds by alternately solving for the unknown positions of the deformed mesh with a fixed feature field v and solving the AT functional to update the feature field v and piecewise smooth normals u.

Matching normals. Let p be the vertices positions of the deformed mesh, and F = { f i } i=1..N the set of triangles where f j i denotes the j th vertex of the i th triangle, with j ∈ {0, 1, 2}. As we are deforming the mesh, the topology (and hence the set of triangles) of the deformed mesh is the same as that of the input mesh. We denote by |p| the number of vertices. Our goal is to find p such that per-triangle geometric normals match the prescribed normal field u. We formulate this condition by imposing that each edge of each triangle be orthogonal to u:

Em = ∑ fi∈F ((p f 1 i -p f 0 i ) • u) 2 + ((p f 2 i -p f 1 i ) • u) 2 + ((p f 0 i -p f 2 i ) • u) 2 = ∑ fi∈F Em( f i ) .
Note that the summation is performed over all triangles and not over edges since u is known per triangle. This induces sharper discontinuities. Its gradient with respect to each triangle vertex position is given by: ∇p

f j i Em( f i ) = 2((2p f j i -∑ k = j p f k i ) • u)u = A( f i )p ,
where A( f i ) is a 3 × 9 matrix, that can be assembled in a 3|p| × 3|p| matrix A for all vertices of all triangles of the mesh.

Fairness. We additionally enforce the piecewise smoothness of the deformed mesh by adding a fairness term. This term forces neighboring triangles to share similar geometric normals, at least wherever the feature v = 1 and corresponds to a thin plate energy. Its effect can be appreciated in Fig. 4. For an edge e = (p i1 , p i2 ) between triangles t 1 = (p i1 , p i2 , p i3 ) and t 2 = (p i1 , p i2 , p i4 ), the fairness energy reads:

E f (e) = v(p i1 ) + v(p i2) 2 2 p i1 + p i2 -p i3 -p i4 2 ,
and we obtain E f by summing over all edges E f = ∑ e E f (e). Fixing v, the gradient of E f (e) with respect to p i1 (resp. p i2 ) is:

∇p i 1 E f (e) = 2 v(p i1 ) + v(p i2 ) 2 2 (p i1 + p i2 -p i3 -p i4 ) = B(e i )p ,
where B(e i ) is a 3 × 12 matrix. These matrices again be assembled in a 3|p| × 3|p| matrix by summing contributions of all edges. Data attachment. We finally prevent vertices to depart too much from their original position, and add a data attachment term. Denoting q the original position of the vertices, this reads:

E d = ∑ i p i -q i 2 .
Its gradient is ∇pE d = 2(pq).

Solving for positions. Denoting E = Em + w 1 E f + w 2 E d the weighted sum of the energies, we can now obtain p by solving ∇pE = 0. This amounts to solving the linear system

(A + w 1 B + w 2 Id)p = w 2 q ,
where Id is the 3|p| × 3|p| identity matrix. The left-hand linear operator being positive and definite (as long as weights are positive), efficient inversion algorithms can be used to solve the system. Except for inpainting which requires large values of w 1 as discussed next, most results were obtained with w 1 = 1, though decreasing w 1 can be useful for large noise or unreliable vertex positions. We have kept w 2 fixed and small throughout all our experiments, with w 2 = 0.05. Note that meshes are uniformly scaled to fit the unit ball, so that parameters are comparable across meshes.

Applications

Inspired by image processing, our method serves various geometry processing applications illustrated in this section. This includes restoring noisy meshes, segmenting meshes, inpainting missing data, or embossing a normal map into the mesh vertices.

Denoising

Given an input noisy mesh, our method smoothes out noise while preserving features. For this application, we alternate between solving for the MS functional to regularize the normal vector field, and conforming the mesh vertices to the estimated normals. In our examples, our method achieves visually satisfactory results within 2 to 6 such iterations (see Fig. 6). In this experiment, we have considered both synthetic shapes perturbed using a Gaussian noise in order to have a ground-truth, and more realistic noisy LiDAR shapes.

We illustrate these results in Fig. 5 and show the effect of varying λ in Fig. 7. In practice, decreasing λ produces longer discontinuities, and thus less smooth denoising results. Numerical and visual comparisons with state-of-the-art denoising techniques can be found respectively in Table 1 and in Fig. 5. We compare our features to that of Tong and Tai [TT16] who solve a similar AT functional via a Finite Elements discretization, using a noisy non-uniform mesh (Fig. 2) and meshes with varying amount of noise (Fig. 8). We show that our features are more robust to noise, making our method suitable for denoising applications.

[TT16] Our method Figure 8: We compare our method (bottom) to that of Tong and Tai [TT16] on meshes with weak, moderate and extreme noise levels. Our approach remains robust even to extreme noise levels.

Segmentation

We segment meshes into piecewise smooth parts. Note that, contrary to semantic mesh segmentation, our segmentation is purely geometric and bears no semantic meaning. This can find applications in mesh parameterization where seams should remain as little visible as possible [RNLL10], or as a preprocessing for further feature extraction (see the mesh segmentation survey of Attene et al. [AKM * 06]). However, this makes numerical evaluation difficult since no ground truth segmentation is available, in contrast to semantic segmentation benchmarks [START_REF] Golovinskiy | A benchmark for 3d mesh segmentation[END_REF].

To perform this segmentation, we make use of our MS solver to obtain the feature field v for each vertex of the mesh. We further clamp v since it can occasionally take values outside of the range [0, 1] due to approximations. We then make use of the method of Keuper et al. [KLB * 15] which solves a minimum multicut problem in the triangle adjacency graph using the Kernighan Lin method. This method takes as input the probability of two adjacent triangles to belong to different segment, which amounts to bringing the feature v from vertices to edges. For each edge, we obtain a splitting probability by averaging the value 1-v of both vertices of the edge, while forcing this probability to 0.1% when adjacent triangles have their (regularized) normals further than 5 • apart. Segmentation results can be seen in Fig. 9.

In Fig. 10, we illustrate the differences between our geometric segmentation and state-of-the-art semantic segmentation meth-

Ground truth Noisy

[ZDZ * 15] [SRML07] [FDCO03] [ZFAT11] [HS13]
Our denoising ods. Our method is agnostic to the underlying semantics and produces geometrically consistent segmentations with piecewise smooth parts minimizing a well-defined AT energy, while semantic segmentation methods often produce semantically meaningful parts from heuristics or learning from large manually segmented databases [START_REF] Golovinskiy | A benchmark for 3d mesh segmentation[END_REF].

Inpainting

Inpainting seeks to fill in missing areas of a mesh. To perform mesh inpainting, one should first triangulate the missing area. The first step is to recover the topology of the missing area, which we perform using the hole filling algorithm

Embossing Normal Maps

Normal mapping is a useful technique for interactive applications, and allows for efficient low-polygon rendering by encoding geometric details as variations in normals stored in a high resolution texture. However, when it comes to realistic or physicallybased rendering, this comes at the expense of several shortcomings. First, as these shading normal variations merely fake geometric details, silhouettes remain coarse, hence precluding renderings of close-ups. Second, as shading normals are not aligned with geometric normals, this can produce artifacts in physically-based renderers such as light leaks or black regions (Fig. 12,(b)), or artifacts due to the lack of energy conservation if not handled with particular care [START_REF] Veach | Robust Monte Carlo methods for light transport simulation[END_REF]SHHD17]. Our projection step allows to recover finely detailed models for offline rendering from coarse assets along with their normal map. First, we increase the resolution of the input model (for subdivision surfaces, we apply a Catmull-Clark scheme). We then look up the normal value at each vertex from the normal map, and finally apply the projection step described in Sec. 4. Several embossing results are shown in Fig. 12.

6. Discussions

Implementation and Performance

We implemented our method in C++ using the DEC operators within the libDCC library [START_REF] Crane | Digital geometry processing with discrete exterior calculus[END_REF]. Our implementation is mono-threaded, although fast parallel sparse linear solvers could be used instead [GJ * 10]. Still, our unoptimized code already produces results in a reasonable amount of time. It processes meshes of nearly 300k triangles in less than 15 minutes, or in less than a minute if only the projection step is required (see Table . 2). Our implementation is available within our supplemental materials.

Limitations

First of all, to better capture the geometry, our approach requires to have meshes with enough triangles. For instance, low resolution shapes may lead to unrelevant segmentations (see Fig. 13, first row). For a more extreme case, since the feature vector v is represented as a 0-form we may highlight as feature all edges of a thin triangular strip (see Fig. 13, second row).

We also believe the normal map embossing would benefit from a mesh refinement strategy that adapts to the local frequency content of the normal map. Some details from the normal map indeed appear to be lost, and this is due to a too coarse underlying mesh at some places. This could be investigated in the future.

Conclusions and Future Work

We have introduced a discretization of a functional for mesh processing along with a series of preliminary applications, which pro- duces state-of-the-art results in mesh denoising, segmentation, inpainting and embossing. We leave as a future work a more extensive validation of each individual application, and rather emphasize the broad scope of our method. In particular, we expect the features detected by our Mumford-Shah discretization to be useful for feature sensitive remeshing [START_REF] Nivoliers | Anisotropic and feature sensitive triangular remeshing using normal lifting[END_REF]. We also believe that stitching meshes together [START_REF] Sharf | Snappaste: an interactive technique for easy mesh composition[END_REF] and mesh super-resolution [START_REF] Tsai | Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[END_REF] could be performed similarly to our inpainting application. More generally, we expect the success of the MS model in geometry processing could parallel its success in image processing.

Figure 2 :

 2 Figure 2: We compare our features (b) to that extracted by the finite element discretization of Tong and Tai [TT16] (a) using the same parameters (λ = 0.06, α = 0.07). The feature function is shown in yellow, while extracted feature lines are shown in red. Our method is able to detect features even at relatively high noise levels.

Figure 3 :

 3 Figure 3: Notations on a primal and dual mesh for the energy optimization (edge orientation not shown for the sake of clarity): v is a 0-form on vertices. In red (resp. green), we have the Av values (resp. Mv values) on edges. In blue, the triple of dual 0-forms, u on dual vertices and the Bu values in magenta on dual edges.

Figure 4 :

 4 Figure 4: Denoising the model of Fig. 2 without (a) and with (b) a small fairness term E f (w 1 = 0.5). The fairness term favors more regular near-Delaunay meshes. The colormap indicates the aspect ratio of each triangle (1 -αT π/3 with α T the minimum angle of triangle T ) .

Figure 5 :

 5 Figure 5: Denoising results comparisons. For our method, features (v) are shown in yellow. The last two rows illustrate denoising on LiDAR acquired geometries where no ground-truth information is available.

  [Lie03] implemented in CGAL [FP09]. Then, we set the data attachment terms α and w 2 to a large value (typically, α = 2 = 1000) outside of the inpainted area to prevent known vertices from moving, and w 2 to zero inside. Since the hole filling tends to oversmooth the inpainted area, we(

Figure 6 :

 6 Figure 6: Influence of the number of MS / vertex projection iterations.

Figure 7 :

 7 Figure 7: Influence of λ on denoising results. First row: Original and noisy models. Second row: denoising with λ = 0.05 (left) and λ = 0.01 (right). Decreasing λ produces longer features, and more discontinuities.

  ), and the perceptual metric of Lavoué et al. [LGD * 06] (ranks are given as cell colors from dark blue -rank 1-to light-blue -rank 6-). Our method performs better according to perceptual distances. This is due to a slight shrinkage of our denoising results which drastically impacts purely geometric metrics. Parameters were not adjusted to perform well under these metrics. Columns are named following: Z15 [ZDZ * 15], S07 [SRML07], F03[START_REF] Fleishman | Bilateral mesh denoising[END_REF], Z11[START_REF] Zheng | Bilateral normal filtering for mesh denoising[END_REF], and H13 [HS13], and AT is our method.

Figure 9 :Figure 11 :

 911 Figure 9: Segmentation results. Edge splitting probabilities are shown in red.

Figure 10 :

 10 Figure 10: Comparison of semantic segmentations (a-f) with our geometric segmentation (g). While semantic segmentation produces parts of meaningful semantics such as the base, the neck, or the handle of this jar, our geometric segmentation detects sharp edges and results in piecewise smooth segments regardless of the underlying semantic.

Figure 12 :

 12 Figure 12: Embossing results. We subdivide (c) the input model (a), and emboss the normal map (c) onto the subdivided model (d). When shading normals are not aligned with geometric normals, physically-based renderers can produce artifacts such as black regions (b) if not handled with particular care.

Table 1 :

 1 We provide numerical evaluation with state-of-the-art methods, with respect to the Hausdorff distance (RMS, normalized by the bounding box diameter

			Hausdorff Distance (×100)				Perceptual Metric
		Z15	S07	F03		H13	Our	Z15	S07	F03	Z11	H13	Our
	Chair	0.0677	0.1221	0.0762	0.0636	0.0786	0.1695	0.587	0.539	0.577	0.531	0.557	0.546
	Skull	0.1082	0.1773	0.1180	0.1017	0.1078	0.1689	0.635	0.626	0.650	0.623	0.603	0.592
	Helmet 0.1748	0.2595	0.1691	0.1408	0.1874	0.1963	0.577	0.524	0.596	0.510	0.558	0.507
	Pirate	0.0853	0.1170	0.0898	0.0892	0.0838	0.0860	0.277	0.404	0.304	0.326	0.387	0.318
	Shell	0.0386	0.0500	0.0641	0.0331	0.0464	0.1324	0.346	0.499	0.698	0.410	0.410	0.349

Table 2 :

 2 Performance of the MS solver and vertex projection steps with respect to the model complexity, using an unoptimized monothreaded implementation.

	Helmet	10,022	20,247	28.9	2.5
	Shell	30,036	60,068	120	10
	Chair	57,933	115,910	214	15
	Lion	60,066	120,128	248	14
	Skull	81,051	162,120	315	18
	Pirate	136,770	273,536	832	46
	Boar	223,251	444,809	1,133	53
	Gun	392,747	784,785	2,189	87
	Skull (HR)	324,251	648,480	N/A	104
	Armor	447,052	806,144	N/A	65

Model

# vertices # triangles MS (s) Projection (s)

Acknowledgments The authors acknowledge the CoMeDiC ANR Grant (ANR-15-CE40-0006).


Yu-Tsun Chien

Dong Chen

Jea-Hong Lou

Gin-Kou Ma

Rob A Rutenbar

Tamal Mukherjee

Designer-Driven Topology Optimization for Pipelined Analog to Digital Converters

This paper suggests a practical "hybrid" synthesis methodology which integrates designer-derived analytical models for system-level description with simulation-based models at the circuit level. We show how to optimize stageresolution to minimize the power in a pipelined ADC. Exploration (via detailed synthesis) of several ADC configurations is used to show that a 4-3-2… resolution distribution uses the least power for a 13-bit 40 MSPS converter in a 0.25 µm CMOS process.

Introduction

In the digital world, RTL/logic synthesis is an indispensable tool for allowing system designers to explore high-level architecture, functional partitioning, and performance tradeoffs. Synthesis serves the role of completing a block to a level of concreteness that can be used to properly evaluate the merits of architecture-level tradeoff decisions. The questions we address in this paper are how recently introduced commercial-quality analog synthesis tools (e.g., [START_REF] Gielen | Computer-aided design of analog and mixed-signal integrated circuits[END_REF] [START_REF] Oda | A New Methodology for Analog/Mixed-Signal (AMS) SoC Design that Enables AMS Design Reuse and Achieves Full-Custom Performance[END_REF]) might play the same role in system-level analog design, and what a systematic methodology for this sort of design might look like. Two broad approaches have been suggested:

• Equation-based methods avoid simulation entirely, and strive to represent the design at all levels in an analytical form [START_REF] Harjani | OASYS: a framework for analog circuit synthesis[END_REF][START_REF] Hershenson | GPCAD: a tool for CMOS Op-Amp Synthesis[END_REF][START_REF] Hershenson | Design of pipeline analog-to-digital converters via geometric programming[END_REF]. Convex models are the most successful here [START_REF] Hershenson | GPCAD: a tool for CMOS Op-Amp Synthesis[END_REF][START_REF] Hershenson | Design of pipeline analog-to-digital converters via geometric programming[END_REF]. However, the method makes some serious tradeoffs emphasizing speed at the cost of design accuracy. • Hierarchical simulation-based methods use macromodels for the system-level design, and detailed models for the basic blocks, and then link these numerically. [START_REF] Phelps | A case study of synthesis for industrial-scale analog IP: redesign of the equalizer/filter frontend for an ADSL CODEC[END_REF] is perhaps the most aggressive attempt in this direction. An alternative approach builds Pareto tradeoff curves for each basic block via detailed synthesis [START_REF] Stehr | Performance trade-off analysis of analog circuits by normal-boundary intersection[END_REF][START_REF] Smedt | Watson: Design Space Boundary Exploration and Model Generation for Analog and RF IC Design[END_REF][START_REF] Rutenbar | Pareto-Optimal Modeling for Efficient PLL Optimization[END_REF], then uses these to "parameterize" a system-level model. Both techniques are attractive, but not yet well-supported in commercial synthesis tools. We suggest a practical "hybrid" approach which integrates well with the current crop of commercial synthesis tools, and is moreover consistent with the style in which most analog system designers prefer to work. To make this concrete, we look at system-level architecture/topology power minimization for 40 MSPS pipelined ADCs in a 0.25µm 3.3V CMOS process with resolutions from 10 to 13 bits.

Candidate Enumeration

The pipelined ADC consists of a front-end sample and hold amplifier (S/H amplifier) and M pipelined stages and the number of bits to be converted in each stage (mi). One extra bit from each stage is used to implement digital correction logic. Designers have used a variety of configurations m1ˀm2m 3Ξ to design pipelined ADCs, starting from the classical 22 ˀ2Ξ or 1.5 bits per stage topology [START_REF] Hershenson | Design of pipeline analog-to-digital converters via geometric programming[END_REF] to the recent 4ˀ2ˀ2Ξʳ [START_REF] Yang | A 3-V 340-mW 14-b 75-Msample/s CMOS ADC with 85-dB SFDR at Nyquist input[END_REF]. The possible configuration sets {m1ˀm2ˀm3,Ξ} for a Kbit pipelined ADC is governed by

= = - M i i K m 1 ) 1 (
where K is the total effective number of bits over M stages with digital correction circuitry.

In this paper, candidate enumeration is used to explore all possible configurations such that m i Љ4 and m i Њm i+1 . The m i Љ4 constraint is due to closed-loop bandwidth concerns. The m i Њm i+1 constraint arises because of the area factor and is often used implicitly [START_REF] Hershenson | Design of pipeline analog-to-digital converters via geometric programming[END_REF] [START_REF] Yang | A 3-V 340-mW 14-b 75-Msample/s CMOS ADC with 85-dB SFDR at Nyquist input[END_REF]. Additionally, we only consider the first few stages such that the output resolution exceeds 7 bits. This is because ADC power is mainly consumed by the starting few bits [START_REF] Hershenson | Design of pipeline analog-to-digital converters via geometric programming[END_REF]. These reduce the design space complexity to a manageable enumerated set of seven different candidates. Each candidate has several MDAC stages to be synthesized using method in section 3. The MDAC block-level specifications can be translated from the ADC system-level specifications and the value mi for the enumerated candidate

Block-level Synthesis Design Flow

The proposed block-level synthesis design flow combines circuit analysis with simulation to reduce the design space and speed up transistor-level evaluation, enabling use of commercial cell-level synthesis tools. First, once the circuit topology of the MDAC block is decided, Driving-Point Impedances (DPI) / Signal-Flow Graphs (SFG) is used to draw the signal flow graph equivalent of the circuit. Second, the circuit symbolic transfer function is derived from the SFG by using Mason's rule. With SFG and symbolic transfer function information, circuit characteristics such as poles/zeros, gain, phase-margin, are analyzed. The range of the design variables that define the design space and the design constraints are reduced using the DPI/SFG analysis results.

When circuits experience large dynamic swing, simulation-based evaluation produces trustworthy results within a short period of time. When circuit behavior is linear, transfer functions based on small signal parameters evaluate circuit performances accurately and efficiently. Combining these approaches has the advantage of high simulation accuracy and fast equation evaluation. Thus, evaluation of each candidate solution involves: 1) DC simulation to extract small signal values, 2) formulating the numerical transfer function, and using the toolkit for hybrid equation+simulation evaluation.

This evaluation procedure is performed automatically in each synthesis iteration.

Topology Optimization Results

Eleven MDACs used to enumerate the seven 13-bit ADC configurations were synthesized (using the Cadence NeoCircuit tool). Fig. 1 shows that the power of the first stage is mostly independent of the resolution of the first stage. Choosing 4-bits in the first stage, which minimizes the bits in the other stages, optimizes the power in the 13-bit case.

2-2-2-2-2-2 3-2-2-2-2 3-3-3 4-3-2 4-2-2-2 3-3-2-2 4-4

Fig. 1 Stage power for 13-bit ADC configuration

MDAC power is added to the sub-ADC comparator power to obtain the overall ADC power. Fig. 2 presents the total power for the stages with output resolution exceeding 7 bits in each of the enumerated architectures for the 10~13-bit pipelined ADCs. 3-2…, 4-2…, 4-2-2…, 4-3-2… are the optimum candidate numeration for 10, 11, 12 and 13-bit, respectively. 2-bit at the last stage is the common optimum candidate numeration for 10~13-bit. More data raises some instructive implications that can be summarized in Fig. 3.

Total power for first 6 bits of pipelined ADC

} 4 , 3 , 2 { ∈ ∀ i m 11 ≥ MSB 1 + ≥ i i m m 8 ≤ Bit } 4 , 3 , 2 { ∈ i m } 10 , 9 { ∈ MSB

Fig. 3 Pipelined ADC optimum candidate enumeration

Setting up the first synthesis required 2-3 weeks, however, the time reduced dramatically to 1 day for subsequent blocks, which only involve retargeting of specifications. In contrast, manual design for each block costs a designer 1-2 weeks in our experience, depending on performance requirements. This use of enumeration and cell synthesis with fast evaluation is suitable for system level optimization of circuits that are composed of similar blocks with varying specifications.

Conclusion

Existing analog synthesis methodologies are limited by their ability to scale to larger circuits. A system-level synthesis method which enumerates block architecture alternatives, and then performs block-synthesis using a hybrid of simulationbased and equation-based evaluation overcomes this limitation. Enumeration of MDAC synthesis results for optimizing pipelined ADC power is used to demonstrate the efficacy of this method.

  ˀ˅ ˆˆ˅ ˇ˅ ˀ˅ ˇˆ˄ ˄ ˀ˵ ˼ ̇˅ ˀ˅ ˀ˅ ˀ˅ ˆ˅ ˀ˅ ˇ˅ ˆˆ˄ ˃ ˀ˵ ˼ ̇˅ ˀ˅ ˀ˅ ˆ˅ Fig.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Acknowledgements

The authors would like to thank the Industrial Technology Research Institute Laboratory @ Carnegie Mellon for financial support and Neolinear/Cadence for access to NeoCircuit®.


Jonathan R Carter

Sule Ozev

Daniel J Sorin

Circuit-Level Modeling for Concurrent Testing of Operational Defects due to Gate Oxide Breakdown

As device sizes shrink and current densities increase, the probability of device failures due to gate oxide breakdown (OBD) also increases. To provide designs that are tolerant to such failures, we must investigate and understand the manifestations of this physical phenomenon at the circuit and system level. In this paper, we develop a model for operational OBD defects, and we explore how to test for faults due to OBD. For a NAND gate, we derive the necessary input conditions that excite and detect errors due to OBD defects at the gate level. We show that traditional pattern generators fail to exercise all of these defects. Finally, we show that these test patterns can be propagated and justified for a combinational circuit in a manner similar to traditional ATPG.

Introduction

With decreasing feature dimensions and increasing transistor counts in typical designs, the reliability of semiconductor devices is an increasing concern. One emerging reliability problem is gate oxide breakdown (OBD). The technology trend towards decreasing gate oxide thicknesses results in a greater probability of oxide degradation and breakdown during the lifetime of the devices.due.

Most fault tolerance techniques, such as error correcting codes or high level redundancy, work at the behavioral level without the assumption of any fault model. However, this generality typically imposes high overheads in terms of hardware, performance, and power consumption. Circuit level fault tolerance methods, such as dynamic memory repair, on the other hand, rely on traditional fault models, such as the stuck-at fault model, or coupling fault model. Thus, they may be incapable of detecting errors due to operational defects that do not manifest themselves in traditional ways. To provide fault tolerance at the circuit level, we must investigate the underlying physical defects and understand their manifestations at the circuit level.

The OBD phenomenon has been studied extensively at the device level, yet little research has explored OBD's circuit level implications. It may appear that new fault models are not needed, since oxide breakdown does not result in logic errors at its early stages of soft breakdown, and it results in a simple stuck-at logic error when the final hard breakdown happens. However, OBD affects the dynamic behavior of the circuit long before the final hard breakdown, starting from the early stages of the process. Soft OBD causes much longer delays than expected for the circuit and can thus introduce logic errors. Despite the manifestation of logic errors, traditional fault models may not predict the behavior of such defects accurately. Section 2 discusses related previous work in fault modeling, and it focuses on existing circuit-level fault modeling and the recent device-level modeling of OBD.

In the context of operational defects due to OBD, we address the issues of fault modeling and testing. We show that, for both issues, OBD operational defects demand careful circuit-level consideration. Our contributions in these two areas are the following:

• Fault modeling (Section 3): We show that circuit behavior in the presence of OBD defects exhibits similar aspects to general transition or delay faults, but differs in important ways. Based on published data at the device level, we develop a circuit-level model that closely matches the underlying physical phenomenon.

• Concurrent testing (Section 4): We show that OBD defects require more sophisticated approaches for fault excitation and detection. Particularly, the window of opportunity for detecting OBD defects before they reach their final hard breakdown status depends on the latency of the detection mechanism and the delay caused by these defects. We develop the necessary input conditions for a NAND gate and infer conclusions for other gates. We show that the derived input conditions and output behavior can be propagated to the primary inputs and outputs of a combinational circuit in a manner similar to traditional ATPG.

Related Work

Physical Causes of Faults. The reliability of electronic devices under discrete environmental stress, such as radiation [START_REF] Srour | Radiation Effects on and Dose Enhancement of Electronic Materials[END_REF], and continuous functional stress due to applied electric fields [START_REF] Rodriguez | Oxide Breakdown Model and Its Impact on SRAM Cell Functionality[END_REF][START_REF] Tao | Modeling and Characterization of Electromigration Failures Under Bidirectional Current Stress[END_REF][START_REF] Blaauw | Static Electromigration Analysis for On-Chip Signal Interconnects[END_REF] has been studied since the early days of semiconductor manufacturing. Extensive research has been conducted on the failure-causing physical phe-nomena, such as electromigration (EM) [START_REF] Tao | Modeling and Characterization of Electromigration Failures Under Bidirectional Current Stress[END_REF][START_REF] Blaauw | Static Electromigration Analysis for On-Chip Signal Interconnects[END_REF] and OBD [START_REF] Dumin | Oxide Reliability: A Summary of Silicon Oxide Wearout, Breakdown and Reliability[END_REF]. The effect of OBD at the circuit level is a shift in the LOW and HIGH voltage values and eventually bit errors for CMOS devices [START_REF] Stathis | Physical and Predictive Models of Ultrathin Oxide Reliability in CMOS Devices and Circuits[END_REF][START_REF] Rodriguez | A Model for Gate Oxide Breakdown in CMOS Inverters[END_REF][START_REF] Rodriguez | Modeling and Experimental Verification of the Effect of Gate Oxide Breakdown on CMOS Inverters[END_REF].

OBD defects have been studied in the past decade, although this research has focused on hard breakdowns (also known as gate oxide shorts or GOS). Segura et al. manufacture circuits with intentional hard OBD defects and measure their characteristics [START_REF] Segura | Analysis and Modeling of MOS Devices with Gate Oxide Short Failures[END_REF]. They also study the distinct responses of NMOS and PMOS transistors to hard OBD defects [START_REF] Segura | A Detailed Analysis of GOS Defects in MOS Transistors: Testing Implications at Circuit Level[END_REF], and they propose test patterns for I DDQ measurements to detect these defects. Renovell et al. [START_REF] Renovell | Modeling Gate Oxide Short Defects in CMOS Minimum Transistors[END_REF] develop a transistor-level model for hard OBD defects that does not rely on splitting transistor dimensions. They also propose test patterns for detecting hard OBD defects through delay testing [START_REF] Renovell | Delay Testing of MOS Transistor with Gate Oxide Short[END_REF]. While hard OBD defects, which are typically tested after manufacturing, are identical to the final stage of the OBD defects that we analyze here, our goal is to create a model to help us develop concurrent test/ diagnose/repair mechanisms for OBD defects before final hard breakdown occurs. Since hard OBD can potentially harm the rest of the circuit, modeling OBD progression is essential to ensure fault-tolerant operation.

Fault Modeling. Several structural fault models have been developed for logic circuits and storage components over the past few decades [START_REF] Abramovici | Digital Systems Testing and Testable Design[END_REF]. The stuck-at fault model is the most commonly used model in VLSI testing and fault tolerant design. In this model, a defect manifests itself as a signal consistently having a certain value (zero or one) independent of the input. For example, an unintended short circuit between the two inputs of an XOR gate results in a stuck-at-zero fault at the output. The coupling fault model-in which a write to a certain memory location always prompts a write to a neighboring location or locations-has been defined for storage components [START_REF] Chen | A Self-Testing and Self-Repairing Structure for Ultra-Large Capacity Memories[END_REF].

The path delay fault model [START_REF] Park | The Total Delay Fault Model and Statistical Delay Fault Coverage[END_REF][START_REF] Park | A Statistical Model for Delay-Fault Testing[END_REF] and the transition fault model [START_REF] Pomeranz | On n-detection Test Sets and Variable n-detection Test Sets for Transition Faults[END_REF][START_REF] Cheng | A Single-State-Transition Fault Model for Sequential Machines[END_REF][START_REF] Tseng | Multiple-Output Propagation Transition Fault Test[END_REF][START_REF] Saxena | Scan-Based Transition Fault Testing -Implementation and Low Cost Test Challenges[END_REF] have been used to test for manufacturing defects and process variations. In the path delay fault model, unexpectedly high process variations as well as point defects increase the overall delay of a path beyond the designated clock period. Paths with the highest logic depth are most likely to incur logic errors. Transition faults are based on point defects as opposed to the collective defects in the path delay fault model. In the transition fault model, resistive connections cause a circuit node to rise or fall too slowly. While both transition and path delay fault models are dynamic, they do not differentiate among the underlying physical defect locations and types. Thus, test generation methods targeting these faults are insensitive to which input combinations cause the desired transition at the fault location. For example, for a NAND gate, input transitions (11,00), [START_REF] Pomeranz | On n-detection Test Sets and Variable n-detection Test Sets for Transition Faults[END_REF]01), and [START_REF] Pomeranz | On n-detection Test Sets and Variable n-detection Test Sets for Transition Faults[END_REF][START_REF] Park | The Total Delay Fault Model and Statistical Delay Fault Coverage[END_REF] are identical in testing for a slow-to-rise transition fault at the output.

While the physical phenomena causing OBD have been studied in detail, limited work has been devoted to investigating the circuit level manifestations and modeling of these defects. Some recent work [START_REF] Rodriguez | Modeling and Experimental Verification of the Effect of Gate Oxide Breakdown on CMOS Inverters[END_REF][START_REF] Rodriguez | A Model for Gate Oxide Breakdown in CMOS Inverters[END_REF] models the oxide breakdown phenomenon for an inverter using SPICE circuit elements. This work matches the model data to the measured data for the transfer characteristics of the inverter. Based on this circuit model, it is clear that oxide breakdown progressively impacts the circuit behavior and finally results in a logic error.

Gate Oxide Breakdown Defects

In this section, we describe the underlying physical phenomenon for OBD defects, our simulation model, and the dynamic behavior of circuits with OBD defects.

Underlying Physical Phenomenon

In a newly manufactured device, there is a random number of traps (imperfections) within the oxide. Over time, due to operational stress, more traps form, leading to small transient conductive paths within the oxide. During this process, current conduction is due to a combination of conductive paths formed by oxide traps and tunneling through the oxide. The formation of these conductive paths is referred to as soft breakdown (SBD). These paths may disappear after an initial injection of high current density that causes high temperature at the defect location. High temperature may relocate some of the oxide traps, breaking the conduction path. However, after a number of SBD incidents, many traps exist within the oxide, leading to a consistently high current density. Eventually, the resulting heat may generate holes in the oxide and melt the conductive material at the gate. Thus, a persistent low-resistance path is formed, leading to a hard breakdown (HBD). This progressive phenomenon is illustrated in Figure 1.

As discussed in Section 2, prior work [START_REF] Rodriguez | Modeling and Experimental Verification of the Effect of Gate Oxide Breakdown on CMOS Inverters[END_REF] concluded that oxide breakdown has negligible effect on circuit timing and that the degraded logic value can be restored by the next logic stage. This argument is true if either the breakdown process is in its early stages or the source driving the breakdown gate has large current supply capability. Since OBD is a progressive process, once soft breakdown starts, the leakage current starts continuously increasing, as experimentally shown in previous work [START_REF] Linder | Growth and Scaling of Oxide Conduction After Breakdown[END_REF][START_REF] Oussalah | On the Oxide Thickness Dependence of the Time-Dependent Dielectric Breakdown[END_REF]. Allowing the defect to reach its final HBD stage, where it generates a stuck-at like fault, may potentially result in catastrophic impacts for upstream logic, as shown in Figure 2. Since a HBD for transistor M2 practically results in a short circuit between the gate and source/drain of the transistor, the drain of the driving transistor M1 will be effectively shorted to ground. This persistent connection to ground can potentially damage M1 and/or the supply. Thus, such defects need to be detected and repaired before HBD.

The progression of the breakdown may result in appreciable timing delays, creating logic errors if the defective transistor is driven by upstream logic. The timing delay is due to two factors, as illustrated in Figure 2. First, the leakage current through the breakdown path in M2 diverts a large portion of the current supplied by M1 to charge the gate capacitance of M2. Second, the degraded logic level at M2 results in a lower current for transistor M3, slowing down its operation as well. Thus, even if the HBD stage is not reached, the defect may cause logic errors.

Simulation Circuit Model

In order to understand the progression of OBD and how to detect OBD faults in embedded logic circuits during their operation, we developed a circuit model that can be used with HSPICE. As illustrated in Figure 3a, the oxide breakdown results in a resistive connection between the gate and the bulk of the device. This connection is followed by pn junctions to the source and the drain of the device. There is also a resistive connection between the breakdown location and the substrate. We assume that the substrate connection is farther away, resulting in a high resistance. Thus, the breakdown transistor can be modeled with two resistors and two diodes, as shown in Figure 3b.

With the diode-resistor based model illustrated in Figure 3b, the progression of OBD can be explained by an increase in the saturation currents of the diodes and a decrease in the resistance. This progression is mainly due to the high current density through the oxide causing high heat and generating fast deformations in the neighboring regions, resulting in an increase in the effective contact area between the gate and the bulk right underneath the gate.We have experimentally verified this model with respect to the measured data reported by Rodriguez et al. [START_REF] Rodriguez | Modeling and Experimental Verification of the Effect of Gate Oxide Breakdown on CMOS Inverters[END_REF]. In terms of the voltage transfer characteristics of an inverter, the OBD in an NMOS transistor results in an upward shift in the VOL value, as illustrated in Figure 4. The OBD in a PMOS transistor results in a downward shift in the VOH value [START_REF] Rodriguez | Modeling and Experimental Verification of the Effect of Gate Oxide Breakdown on CMOS Inverters[END_REF]. Considering only static voltage transfer characteristics is not sufficient. The timing effect of OBD results in logic errors long before the static characteristics start impacting the output.

Dynamic Behavior of Transistors with OBD

OBD in an internal transistor of a gate results in a transition delay at its output. However, the manifestation of this defect is different from the traditional transition fault model since the input conditions play an important role in its excitation. In HSPICE, to simulate the OBD effect for a gate that is embedded in a logic path, we need to ensure that the defective gate is driven by other gates rather than by a voltage source (as in previous work). Thus, we employ the simulation set-up shown in Figure 5 for a NAND gate.

V DD GND … … … M 1 M 2 M 3
As explained in the previous sections, two events play a role in the transition delay of a gate under OBD breakdown. First, the leakage current through the oxide impedes the charging or discharging of the output node. Second, the lower swing of the output node due to the breakdown slows down the downstream logic driven by the defective gate.

Since OBD is a progressive defect, there is a window of opportunity in which to detect the errors caused by it. We would like to detect these defects long before the final HBD status is reached, since there is a potential danger of harming other components at this stage. The window of opportunity to detect the OBD defects is between the SBD stage and HBD stage as explained in Section 3.1. We refer to the state of the breakdown process within this time as medium breakdown (MBD).

Based on data from Linder et al. [START_REF] Linder | Growth and Scaling of Oxide Conduction After Breakdown[END_REF], the time between the first SBD incident and the final HBD is roughly 27 hours for a PFET with a 15Å oxide thickness. However, the detectability of an initial SBD defect is quite low since the delay caused by it can be transient and/or small. Thus, the window for detection/repair is really much shorter than 27 hours. The increase in the leakage current between SBD and HBD is exponential. Table 1 shows the saturation currents (I sat ) and resistance (R) values used in our model and the resulting transition delays for the NAND gate. The "Fault Free" row refers to the case with no OBD. Input sequences are shown in the first row of the table. The columns corresponding to entries N y (P y ) indicate an NMOS (PMOS) OBD in the transistor connected to input y.

Figure 6 shows the impact of an NMOS OBD on the timing of the NAND gate in Figure 5, assuming the defective NMOS transistor is connected to input A (i.e., N A ). We observe from Figure 6 that breakdown in the NMOS transistor causes a transition fault at the output of the gate that is independent of which input switches. The reason for this behavior is that the OBD defect mainly injects current into the drain of the transistor and limits the overall discharge current through the series connection regardless of which input switches. The same effect can be observed when the defective transistor is connected to input B.

Concurrent Testing for OBD Defects

The experiments in Section 3 show that transition faults caused by OBD can be detected only through a timing sensitive testing method. However, to excite the faults caused by OBD defects, specific input transitions are necessary.

Input Conditions for Detecting OBD Defects

While the NMOS OBD defects can be detected through any combination of input switching that results in a highto-low switching at the output, this is not the case for the PMOS defects. Since the PMOS transistors are in parallel, the defective transistor can only cause a timing delay at the output if it is the only transistor charging the output node. Thus, PMOS defects in a NAND gate can be detected only through specific input combinations that result in a low-tohigh transition at the output node.

The input-specific nature of PMOS OBD defect manifestation can be observed from Figure 7. The defective PMOS transistor in this case is connected to the input A. While seemingly all PMOS OBD defects result in a slow-to-rise transition fault, an OBD defect in the PMOS transistor that is connected to input A can only be detected if input A is switched from 1 to 0 while input B is kept at 1. This input- Similarly, an OBD defect in the PMOS transistor that is connected to input B can only be detected if input A is held at 1 and B is switched from 1 to 0.

To detect all OBD defects in a NAND, one of the input sequences { [START_REF] Park | The Total Delay Fault Model and Statistical Delay Fault Coverage[END_REF][START_REF] Pomeranz | On n-detection Test Sets and Variable n-detection Test Sets for Transition Faults[END_REF], (00,11), (01,11)} and the sequences {(11,10)} and {(11,01)} are necessary and sufficient.

Propagation of fault effects

Once the excitation conditions are met, an OBD defect results in a transition delay at the output of the defective gate. This transition delay can be propagated to the primary output through other gates in a similar fashion to traditional fault models, such as the stuck-at fault model. However, the detection of this fault may necessitate output capture earlier than the designated clock frequency of the digital circuit. This problem is similar to transition fault testing and several early capture methods have been developed [START_REF] Saxena | Scan-Based Transition Fault Testing -Implementation and Low Cost Test Challenges[END_REF].

It can be argued that the timing delay due to an OBD defect will eventually generate detectable logic errors at the output independent of the slack in the clock period due to the progressive nature of these defects. However, as experimentally shown [START_REF] Linder | Growth and Scaling of Oxide Conduction After Breakdown[END_REF][START_REF] Boyko | Time Dependent Dielectric Breakdown at 210 Å Oxides[END_REF], the progression of OBD defects from the onset of appreciable leakage current is exponential. Thus, defects must be identified as soon as appreciable leakage current starts flowing. This window of opportunity depends on the timing slack in the detection mechanism. The diode-resistor based model can be used to determine the delay caused by the OBD defects at various stages of the progression. This information helps the scheduling of test/diagnosis/repair intervals of fault-tolerance schemes.

Illustrative example: Sum output of full adder

In this section, we show that the manifestations of OBD defects can be propagated through a logic path and can be observed at the output through a timing delay, even though the degraded logic value is restored in the end. As an experimental circuit, we have used a combinational circuit: the sum bit of a full adder, implemented using 14 NAND gates and 11 inverters, as shown in Figure 8. For illustrative purposes, we implemented this logic function without any optimizations, resulting in a logic depth of 9.

We injected single OBD errors into the NAND gate that has four stages in both the upstream and downstream logic. Figure 9 shows the inputs and outputs of this circuit for the injected faults. The necessary input sequences for the NAND gate have been propagated to the primary inputs, A, B, and C. The delays due to the OBD defects in the four transistors inside the NAND gate (injected one at a time) can be observed at the primary output, the sum bit.

In the example circuit, there are 56 distinct locations for OBD defects in the 14 NAND gates. Some of these faults are undetectable due to the intentional redundancy in the circuit. 18 out of 72 input transitions are necessary and sufficient to detect the 32 testable OBD faults in the circuit.

Applicability to General Circuits

Our analysis for the NAND gate can be generalized as follows. The OBD breakdown of a transistor can be detected at an output node only if that transistor is excited at the switching of the output node and if no other transistor that is connected to the defective transistor in parallel is excited. As an example, for a traditional NOR gate, one of the input combinations {(10,00), (01,00), (11,00)}, and the input sequences {(00,01)}, and {(00,10)} are necessary and sufficient to detect all four OBD defects.

Testing for OBD defects requires transitional inputs. For combinational circuits, test pattern generation (TPG) for OBD defects is of the same computational complexity as for stuck-at faults. Similar to transition faults, sequential TPG for OBD defects is more complicated than sequential TPG for stuck-at faults due to the need to generate two distinct input combinations at consecutive clock cycles. Thus, we need design-for-testability methods to enhance controllability and/or observability of circuit nodes. In the full adder example, the small set of input transitions (18 out of the 72 possible) that suffices to detect all OBD faults makes built-in-testing for such defects promising, particularly for safety-critical applications.

For a traditional NAND gate, the input sequences that detect all the internal intra-gate EM faults are {(11,01)}, {(11,10)}, and {(01,11), [START_REF] Park | The Total Delay Fault Model and Statistical Delay Fault Coverage[END_REF][START_REF] Pomeranz | On n-detection Test Sets and Variable n-detection Test Sets for Transition Faults[END_REF], (00,11)}. At a first glance it may seem that the test inputs that target internal EM defects also detect all OBD defects in a logic gate. However, due to the current injecting nature of OBD defects, this may not always be true, especially for complex gates and high performance logic. Therefore, there is a need to use the circuit models for OBD defects in order to generate test input conditions to detect errors caused by them.

Conclusions

Traditional fault modeling techniques that focus only on static behavior or only on the transition of inter-gate nodes may fail to target emerging defects due to gate oxide breakdown. Detecting the faults caused by such defects is particularly important for safety critical applications and applications that need to run autonomically for long periods of time. In this study, we have used a NAND gate to show that to target such defects, the circuit-level implications need to be considered for test generation.

Figure 1 .

 1 Figure 1. Oxide breakdown process in transistor

Figure 2 .Figure 4 .BFigure 5 .

 245 Figure 2. Impact of OBD on upstream and downstream logic

Figure 6 .

 6 Figure 6. Progression of NMOS OBD for NAND

Figure 8 .Figure 9 .

 89 Figure 7. Input-specific detection of transition faults caused by PMOS OBD defects

TABLE 1 : NMOS and PMOS OBD progression in terms of transition delays for the set-up in Figure 5

 1

			(01,11)	(10,11)		(11,10)	(11,01)
		I sat , R	N A	N B	N A	N B	I sat , R	P A	P B	P A	P B
	Fault Free	1e-30,10k	96ps	96ps	96ps	96ps	1e-30,10k	110ps	110ps	110ps	110ps
	MBD1	2e-28,500	118ps	118ps	118ps	118ps	1e-29,1k	110ps	360ps	360ps	110ps
	MBD2	1e-27,100	156ps	143ps	144ps	156ps	1.1e-29,900	110ps	736ps	740ps	110ps
	MBD3	5e-27,20	190ps	228ps	230ps	190ps	1.2e-29,830	110ps	sa-0	sa-0	110ps

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant CCR-0309164, the National Aeronautics and Space Administration under Grant NNG04GQ06G, and a Duke Warren Faculty Scholarship (Sorin).