We are a sharing community. So please help us by uploading **1** new document or like us to download:

OR LIKE TO DOWNLOAD IMMEDIATELY

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

1827

Finite-Element-Based Discretization and Regularization Strategies for 3-D Inverse Electrocardiography Dafang Wang, Student Member, IEEE, Robert M. Kirby, Member, IEEE, and Chris R. Johnson∗

Abstract—We consider the inverse electrocardiographic problem of computing epicardial potentials from a body-surface potential map. We study how to improve numerical approximation of the inverse problem when the finite-element method is used. Being ill-posed, the inverse problem requires different discretization strategies from its corresponding forward problem. We propose refinement guidelines that specifically address the ill-posedness of the problem. The resulting guidelines necessitate the use of hybrid finite elements composed of tetrahedra and prism elements. Also, in order to maintain consistent numerical quality when the inverse problem is discretized into different scales, we propose a new family of regularizers using the variational principle underlying finiteelement methods. These variational-formed regularizers serve as an alternative to the traditional Tikhonov regularizers, but preserves the L2 norm and thereby achieves consistent regularization in multiscale simulations. The variational formulation also enables a simple construction of the discrete gradient operator over irregular meshes, which is difficult to define in traditional discretization schemes. We validated our hybrid element technique and the variational regularizers by simulations on a realistic 3-D torso/heart model with empirical heart data. Results show that discretization based on our proposed strategies mitigates the ill-conditioning and improves the inverse solution, and that the variational formulation may benefit a broader range of potential-based bioelectric problems. Index Terms—Forward/inverse electrocardiographic problem, hybrid finite-element method, regularization, variational formulation.

I. INTRODUCTION LECTROCARDIOGRAPHY (ECG) investigates the relationship between the electrical activity of the heart and its induced voltages measured on the torso surface. This relationship can be characterized mathematically as a forward problem

E

Manuscript received November 15, 2010; revised January 22, 2011; accepted February 14, 2011. Date of publication March 3, 2011; date of current version May 18, 2011. The work of R. M. Kirby and C. R. Johnson was supported in part by the NSF Career Award under Grant NSF-CCF0347791 and in part by the NIH NCRR Center for Integrative Biomedical Computing (www.sci.utah.edu/cibc) under Grant 5P41RR012553-12. Asterisk indicates corresponding author. D. Wang and R. M. Kirby are with the Scientific Computing and Imaging (SCI) Institute and the School of Computing, University of Utah, Salt Lake City, UT 84112 USA (e-mail: [email protected]; [email protected]). ∗ C. R. Johnson is with the Scientific Computing and Imaging (SCI) Institute and the School of Computing, University of Utah, Salt Lake City, UT 84112 USA (e-mail: [email protected]). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TBME.2011.2122305

in which one estimates the body-surface potentials based upon cardiac activities represented either by epicardial potentials or current sources within the heart; or as an inverse problem where the goal is to noninvasively estimate cardiac electrical activity from voltage distributions measured on the body surface. This paper studies one type of potential-based inverse ECG problem: to reconstruct epicardial potentials from recorded body-surface potential maps. This inverse problem is a basis for some promising clinical applications, such as noninvasive diagnosis [1], [2] and guidance for intervention [3], [4]. The underlying bioelectric model is a potential-based boundary value problem [5], [6]. ECG simulation involves solving the mathematical equations over a geometric domain that approximates the anatomical structure of a human body. Computational methods are applied to obtain a numerical solution suitable for clinical purposes. In order to validate the results obtained, one needs to ensure that the simulation accurately reflects the actual process concerned, a step often known as validation and verification (V&V) in the engineering literature [7]. The goal of this paper is to develop discretization and refinement strategies to be employed when solving the inverse ECG problem with finite-element methods (FEM). Refinement decreases discretization errors by increasing the resolution (or fidelity) of the numerical approximation at the cost of increased computational work. With such strategies in place, one can specify an acceptable discrepancy between the true and approximate solutions and can tune (or refine) the numerical and geometric approximations accordingly. Although refinement methods are widely used in many engineering fields including the ECG community, they are mostly targeted toward the “forward simulation” [8]–[10], which may be inappropriate for the inverse ECG problem [11]. The inverse problem requires different discretization considerations from its corresponding forward problem because of its ill-posed nature, i.e., small input errors may result in unbounded errors in the solution. However, the literature on discretization specifically for the inverse problem is limited. Although the impact of discretization of the epicardium and the body surface has been investigated [12], it still remains an open question as to how discretization is related to the ill-conditioning, and accordingly how one should develop discretizations that optimize the problem’s conditioning while minimizing the approximation error. This paper aims to address this gap at a practical level. To tackle the ill-posedness of an inverse problem, one typically needs “regularization” techniques, which impose constraints on the original problem so as to yield a better-posed

0018-9294/$26.00 © 2011 IEEE

1828

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

problem [13]–[17]. While most regularization methods are applied in the problem-solving phase, it is worth noting that discretization itself is one form of regularization, impacting the numerical conditioning of the discretized problem [18]. A sensible discretization can be readily combined with classical regularization methods to achieve additional improvement to the inverse problem solution. Using a 2-D torso model, our prior study [11] proposed finiteelement refinement strategies specifically for the inverse ECG problem and introduced hybrid finite elements in 2-D. This paper extends our finite-element discretization study to 3-D for simulations based on realistic human anatomical structures with clinical applications. Another major contribution of this paper is a new formulation of regularizers that facilitates finite-element simulation under multiscale simulations. Formed by the variational principle underlying the FEM, the variational-formed regularizers work within the classic Tikhonov regularization framework but have several advantages over the traditionally implemented Tikhonov regularizers. First, the variational regularizers keep the connection between the discretized model and its underlying continuous model, and automatically conform to certain variational properties inherently assumed by the discrete model resulting from FEM. Second, the variational regularizers preserve their norms, and thereby maintain consistent regularization when the inverse ECG problem is computed under multiscale simulations. Third, the variational formulation enables easy construction of the discrete gradient operator, which is traditionally difficult to obtain over irregular mesh. Fourth, it allows efficient imposition of multiple constraints simultaneously. This formulation may provide new insights into a broader range of potential-based bioelectric problems. This paper is structured as follows. Section II describes the mathematical model of the forward/inverse ECG problem and its discretization by FEM. Section III discusses the ill-posedness, based on which we propose the discretization strategies for the inverse ECG problem. Section IV presents the variational-formbased regularization. Section V presents our simulation results based on a realistic 3-D torso model. Section VI presents further discussion and the proposed future work.

A. Mathematical Model The potential field u within a torso is modeled by the Laplace equation as follows: ∇ · (σ(x)∇u(x)) = 0,

u(x) = uH (x), n · σ(x)∇u(x) = 0,

An inverse problem is typically solved within a framework known as model-based optimization or partial differential equations (PDE)-constrained parameter estimation [19]. In such a framework, one first builds a forward model that is able to predict measurement data if the source parameters (in our case, epicardial potentials) are given. The forward model is often governed by PDE. Then, the inverse model is formed as an optimization problem to determine the values of parameters such that their resulting prediction is closest to the measurements. In this section, we present the mathematical model of the forward/inverse ECG problem. We then review how to convert the continuous model into a discrete system by using FEM.

x ∈ ΓH

x ∈ ΓT

(1) (2) (3)

where Ω is the torso volume bounded by the epicardial surface ΓH and the torso surface ΓT . uH is the epicardial potentials (a Dirichlet condition), and σ(x) is the conductivity. Equation (3) means no electric flux leaves the body into the air. The forward problem estimates the potential field u(x) given uH . The inverse problem aims to recover uH from u(x) that reside on ΓT . B. Finite-Element Discretization Here, we describe how to apply the FEM to discretize (1)– (3) over a realistic 3-D torso domain. A comprehensive FEM formulation can be found in our previous paper [11]. The FEM tessellates the 3-D domain Ω into a mesh, which is normally composed of nonoverlapping tetrahedral, prismatic, or cubic elements. One then builds an approximate solution that is a combination of certain element-wise basis functions. The solution is identified by making it satisfy the differential equation in the Galerkin sense. ˆi φi (x), where u ˆi is We consider linear FEM: u(x) = i u the voltage at node i, and φi (x) is the linear hat function associated with node i and is nonzero only on its adjacent elements. Substituting the expansion into the differential equation (1), applying the Galerkin method and integrating by parts, one will get a linear system as follows: uV −AV H A V V AV T (4) = uH AT V AT T uT −AT H where mesh nodes are divided into three groups, indicated by the subscripts: the nodes on the heart surface H, on the torso surface T , and in the interior torso volume V . uV , uT , and uH denote the vectors of voltages at each group of nodes. The submatrices are given by J, K ∈ {V, T, H} (5) where (·, ·) means the inner product taken over the domain Ω: (∇φi , ∇φj ) = Ω ∇φi ∇φj dΩ. The matrix on the left side is known as the stiffness matrix and the right-side vector is the “forcing term” induced by the known Dirichlet boundary conditions. Normally, no element spans from the heart surface to the torso surface, and AT H = 0. From (4), we derive the relation between the torso potentials uT and the epicardial potentials uH as follows: AJ K = (∇φj , σ∇φk );

II. PROBLEM FORMULATION OF THE INVERSE PROBLEM

x∈Ω

j ∈ J, k ∈ K;

uT = KuH , K = M−1 N.

(6)

Here, K is often referred to as the transfer matrix. M = AT T − AT V A−1 V V AV T is well conditioned and invertible. N = AT V A−1 V V AV H is severely ill-conditioned.

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

Based on (6), the discretized forward ECG problem can be stated as: calculate uT given uH and K. Its corresponding inverse problem is given uT and K; find uH that minimizes the functional KuH − uT in certain appropriate norms. III. DISCRETIZATION FOR INVERSE PROBLEM A. Ill-Posedness of the Inverse Problem Despite having a unique solution [20], the aforementioned inverse ECG problem is severely ill-posed and its solution is highly unstable. The ill-posedness stems from information of the heart surface being attenuated when propagating through the body volume conductor. Hence, the inverse calculation is a process of amplification in which both the signal and noise are magnified. We briefly discuss how the discretization process translates the ill-posedness into an ill-conditioned numerical model problem, i.e., the transfer matrix. We refer readers to our previous study [11] for details. The magnitude of amplification (hence the degree of illconditioning) can be estimated by O((rT /rH )m ), where rH and rT are the average distance from the center of the heart to the heart surface and to the torso surface. It is an exponential function in m, the spatial frequency of the epicardial potential distribution. In a discrete problem, the spatial frequency bandlimit is dictated by the resolution on the epicardium, in analogy with the sampling theory about the bandlimit of a sampled signal with its sampling rate. Therefore, arbitrarily refining the heart surface may not be appropriate for solving the inverse problem. We evaluate the conditioning of the discrete problem by examining the singular value decomposition (SVD) of the transfer matrix K. Initially introduced in [21] and further developed in [11], the SVD analysis reveals how each frequency component of the epicardial potential contributes to the torso-surface potential, and the contribution is given by the corresponding singular value. The SVD also builds the concept of the valid space and the null space. The valid space of K is spanned by its right eigenvectors corresponding to nontrivial singular values, and the fraction of uH in that space can be recovered. The null space of K corresponds to near-zero singular values, and the fraction of uH in this space is not recoverable. Therefore, a better conditioned transfer matrix can be characterized by a slowly descending singular value spectrum with a broader range of nonzero singular values, whereas a poorly conditioned transfer matrix is characterized by a large portion of near-zero singular values. The SVD analysis provides a useful means for estimating the conditioning of an inverse problem, regardless of regularization methods, regularization parameters, input noise, or other method-specific factors. Different discretization choices lead to different singular value patterns of the transfer matrix. We use this methodology to evaluate our discretization strategies as follows. B. Discretization Strategy for the Inverse Problem In [11], we argue that through examining the solution procedure given by FEM, one can see three factors that jointly dictate the discretization quality for the inverse problem: 1) how ac-

1829

curate one should represent the cardiac source uH ; 2) how to approximate the volume conductor [the stiffness matrix on the left side of (4)]; and 3) how to compute the heart-to-volume projector AV H . Section III-A has argued that the fidelity on the heart surface determines how much information of epicardial potentials one seeks to recover. Meanwhile, the discretization of the torso volume determines how much of that information can actually pass through the body and be recoverable. The torso volume should be discretized in the same resolution as the heart surface, otherwise it will cause unnecessary, “artificial” ill-conditioning reflected as an expanded null space in the transfer matrix. Finally, to better approximate the heart-to-volume projection, one needs to refine the high potential gradient region around the heart. Based on these considerations, we proposed the following finite-element discretization guidelines for the inverse problem and verified the guidelines on a 2-D torso model [11]. This paper extends these guidelines to 3-D torso models. Results are presented in Section V. 1) Set the resolution on the heart surface based on the problem of interest, but be cautious not to add additional fidelity beyond what is needed. 2) While keeping the epicardial surface resolution fixed, increase the resolution in the normal direction to the heart surface. Such refinement captures the potential field around the heart where the spatial gradient is high, thereby improving the heart-to-volume projection AV H . 3) With the aforementioned two items in place, refine the volume conductor to a sufficient level so as to capture both the features of body-surface measurement and the features implied by the fidelity on the heart surface. For computational efficiency, exceeding that level is unnecessary. 4) Increasing the resolution of the torso surface is desirable, but only when the new resolutions are associated with the measured data. C. Hybrid Finite Elements The discretization guidelines mainly require refining the region around the heart while preserving the discretization of the heart surface. For a tetrahedral element mesh, which is popular in ECG simulation due to its simplicity, the previous requirement will lead to flat tetrahedra with high aspect ratios, which may induce numerical instability by themselves [22]. To overcome this issue, we adopted a hybrid mesh scheme that places layers of prismatic elements around the heart before filling the rest of the body volume with tetrahedral elements. Unlike tetrahedral elements, a prismatic element effectively decouples the resolution in its normal direction and the resolution on its base [23], thus enabling us to refine the direction normal to the heart without changing the resolution of the heart surface. The hybrid mesh is simple to implement. Mesh generation starts from triangulated bounding surfaces for each organ and tissue. Prisms are padded around any organ by extruding its triangulated surface into the body volume. The layers and the thickness of prisms can be adapted when the potential gradient is expected to change dramatically. The padded prisms form a

1830

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

new closed, triangulated surface, upon which standard tetrahedral mesh generation can be performed to fill the rest of the volume. The prisms and tetrahedra conform well at their bounding interface. D. Truncation from High-Order Finite Elements An alternative to spatial refinement is to use high-order finite elements, which achieve higher accuracy with more efficiency than linear finite elements. High-order FEM often increases the resolution uniformly, so we still need to limit the resolution on the heart surface. The traditional way is to use transitional elements but they are difficult to implement. Instead, we decompose the discrete model (6) into a hierarchy of an element-wise linear component, an element-wise quadratic component, and so on. We then extract and solve only the linear component of epicardial potentials, by truncating the transfer matrix properly. The high-order finite elements achieve the goal of refining the volume and the heart/torso interface, whereas the truncation keeps the epicardial resolution unchanged. Compared to the method of hybrid mesh, the truncation scheme provides a seamless solution for selective refinement. Conducted in the polynomial space, the truncation maintains the smoothness of the solution and circumvent the aspect-ratio problem that obstructs spatial refinement methods. The details of our truncation scheme can be found in our previous work [24]. IV. REGULARIZATION VIA A NEW FAMILY OF VARIATIONAL-FORM-BASED REGULARIZERS

ΓH

A. Classic Tikhonov Regularization The most common regularization for an inverse problem is the Tikhonov method given as follows: uH = argmin {KuH − uT 2 + λ2 (LuH 22 )}

such as the FOT [25], [26] or recently total-variation regularization [27]. Although a gradient field is not difficult to compute (by Taylor approximation or Gauss–Green theorem), it is difficult to derive an accurate discrete gradient operator in an explicit matrix form, especially on irregular, unstructured meshes. The matrix form requires representing the gradient at one node by the data at its neighboring nodes, an ill-posed problem when mesh nodes are irregularly distributed. The study [27] obtains the gradient operator over the heart surface via the boundary element method (BEM). This derivation can be found in [5, eq. (13)]. This method does not work for FEM because FEM and BEM treat boundary conditions differently. BEM includes both the Neumann boundary condition and the Dirichlet boundary condition on the heart surface, thus enabling a gradient operator relating the two. FEM only includes the Neumann boundary condition, and applies the Dirichlet boundary condition later as an external constraint. So, a gradient operator of this form is not available. 2) Variational-Based Formulation: We borrow the name “variational” from the context of FEM, upon which the formulation is based. The main idea is to consider epicardial potentials not as a vector, but as a continuous function represented by finite-element expansion: u ˜H (x) = k ukH φk (x), k ∈ H. The potential field is evaluated by the continuous L2 norm, which is defined as 1/2 1/2 uH , u ˜H ) = u ˜H u ˜H ds . (8) ˜ uH L 2 = (˜ Substituting the finite-element expansion into (8) yields ⎞ ⎛ j uiH φi , uH φj ⎠ = uTH MuH (˜ uH )2L 2 = ⎝ i

(7)

where · 2 is the Euclidean norm. The first term is the residual error and the second term is the regularizer constraining certain properties of the epicardial potentials. There are three basic Tikhonov schemes depending on the choice for L. The zero-order Tikhonov (ZOT) takes L as an identity matrix, constraining the amplitude of epicardial potentials. The first-order Tikhonov (FOT) takes L as a gradient operator, constraining the spatial gradient. The second-order Tikhonov (SOT) takes L as a surface Laplacian operator, constraining the curvature of epicardial potentials. B. Operators in a Variational Form 1) Motivation: Our study of variational formulation originated from the quest for a closed-form gradient operator defined over a mesh: given a potential field uH located on some mesh nodes, find a matrix LG such that LG uH gives the magnitude of ∇uH located on the same set of nodes. The gradient operator plays an important role in PDE-constrained optimization as a basis for Newton’s method. For the inverse ECG problem, the gradient operator over a heart surface enables gradient-based regularization methods, which have reported superior results in recovering spatio-temporal characteristics of epicardial data,

(9)

j

where M is the mass matrix over the heart. Similarly, one may evaluate the L2 norm of the potential gradient field by ⎞ ⎛ j ∇˜ uH 2L 2 = ⎝ uiH ∇φi , uH ∇φj ⎠ = uTH SuH (10) i

j

where S is the stiffness matrix over the heart. Detailed definitions of M and S are given in Table I. The Euclidean norm · 2 with an operator L has the property that LuH 22 = uTH LT LuH .

(11)

Hence, if L is to describe the magnitude of the field u ˜H , it should satisfy LT L = M. Such L can be computed as the Cholesky factor of M and inserted into (7) for the ZOT representation, as opposed to the traditional choice of an identity matrix. If L is to describe ∇˜ uH , it should satisfy LT L = S, or equivalently be the Cholesky factor of S. We name such L the “variational-form” gradient operator because it is equivalent to the real gradient operator in the variational principle. L can be used in (7) for the FOT regularization. Table I compares variational-formed operators with traditional operators up to the second order (the surface Laplacian). One may extend this formulation to operators regarding even

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

TABLE I CHOICE OF L FOR TIKHONOV REGULARIZATION

higher-order Sobolev norms, provided that the finite-element formulation maintains stronger differentiability—the variational Laplacian operator requires C 1 continuous finite elements; higher order operators may need C P continuous elements. This paper only considers C 0 elements and accordingly, constraints up to first-order derivatives. The Cholesky decomposition always exists because the mass matrix, the stiffness matrix or matrices formed by higher order derivatives are symmetric and at least positive semidefinite. More discussion of their Cholesky decomposition will be presented in Section VI. C. Norm Preservation One advantage of the variational-form operators over conventional discrete operators is that the former preserves the norms under different resolutions—the continuous L2 norm is independent of the discretization resolution, and the weights made by FEM basis functions take mesh spacing into account. Consequently, the variational operators achieve consistent regularization when the inverse problem is computed under multiple scales. In contrast, conventional regularizers are evaluated by the Euclidean norm, which heavily relies on the discretization resolution and cannot effectively relate the discrete model with its underlying continuous field. Taking the ZOT, for example, with the variational regularizer, changing mesh spacing affects basis functions and then the mass matrix, so the L2 norm of epicardial potentials is preserved. With the conventional identity matrix, however, the regularizer’s Euclidean norm is sensitive to the mesh resolution. D. Imposition of Multiple Variational Regularizers Tikhonov regularization with multiple spatial/temporal constraints [28], [29] is often desirable. Each constraint imposes its own bias on the inverse solution, so combining several constraints may moderate the bias and provide a more comprehensive account of the solution. Inverse solutions are sensitive to the values of regularization parameters, and by distributing regularization to multiple constraints one may improve the robustness of the solution to any individual parameter. The Tikhonov method with multiple constraints is given as uH = argmin KuH − uT 22 + λ2i Li uH 22 . (12) i

Its solution is conceptually expressed as uH = (KT K + T 2 −1 T i λi (Li Li )) K uT . For numerical stability, in practice, the minimization is achieved by solving a linear least-squares

1831

problem of the form

u 2 K T . u − uH = argmin H λL 0 2

(13)

Equation (13) can be solved by standard routines such as the QR factorization, or most efficiently by the bidiagonalization algorithm [30] With multiple constraints, λL is made by concatenating each λi Li . Note that although (13) is in the Euclidean norm, if Li is the variational regularizer,LuH 2 actually gives the value of the continuous L2 norm. To promote additional efficiency, one may construct a compact constraint, denoted as L∗ , that is equivalent to the superposition of all constraints λ2i LTi Li 2 , λ1 = 0. (14) L∗T L∗ = i=1

Equation (13) then just takes L∗ in place of all Li s. Moreover, since only the term LTi Li is needed, one may directly use the mass matrix or the stiffness matrix, without factorizing each Li . The compact operator greatly saves memory when the problem size is large and there are many constraints. It also improves efficiency when all λi s need to be optimized over a large number of admissible values. V. RESULTS A. Simulation Setup We tested our proposed discretization guidelines and the variational-form-based regularization technique using finiteelement simulations of a phantom experiment consisting of a live canine heart suspended in a human torso tank filled with a homogeneous electrolytic medium [31]. This experiment enables simultaneous recording of epicardial and torso potentials in vivo. Both the heart and torso boundaries are triangulated surfaces tessellated from MRI scans. Voltages were measured at mesh nodes. The heart mesh consists of 337 nodes and 670 triangles, and epicardial potentials are recorded at each node over a complete cardiac cycle. The torso surface consists of 771 nodes and 1538 triangles. From the surface meshes, we generated the volume meshes in different ways, in order to identify the impact of discretization on the finite-element solution for the inverse ECG problem. The mesh generation strategies will be given with each test presented later. With each mesh, we conducted a forward simulation to obtain the torso potentials and the transfer matrix K. After adding noise to the torso potentials, we inversely calculated the epicardial potentials, electrograms, and isochrones, and compared these reconstructed heart data with recorded data. Unless otherwise stated, the inverse calculation uses the Tikhonov method given in (7) and solved in (13), whereas the regularization parameter λ was determined by an exhaustive search. While not optimal, the Tikhonov method enables us to consistently isolate the impact of changing the discretization. The numerical conditioning of the discretized inverse problem is evaluated by examining the singular value spectrum of the transfer matrix K and its components N and AV H . Inverse solutions are measured both quantitatively and visually.

1832

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

Fig. 1. Singular values of the transfer matrices resulting from the sphere/torso model. The torso mesh remains unchanged while three sphere meshes are tested. N h denotes the number of nodes of on the surface of each sphere.

Quantitative measures include the relative error (RE) and the correlation-coefficients (CC) between the reconstructed epicarˆ H ) and the measured potentials dial potentials (denoted as u (denoted as uH ). RE and CC are defined as follows: RE =

ˆ uH − uH 2 uH 2

(15)

CC =

ˆM )T (uH − uM ) (ˆ uH − u ˆ uH − u ˆM 2 · uH − uM 2

(16)

ˆH where u ˆM and uM are scalars representing the mean value of u and uH , respectively. Visual assessment of the inverse solutions includes visualizing the reconstructed epicardial potential map and the activation isochrone map. The activation time at each site is determined by the time instant with the most negative temporal derivative of its electrogram (i.e., the minimum du/dt). B. Regularization via Discretization 1) Resolution of the Pursued Inverse Solution: Here, we show how the desired fidelity of an inverse solution affects the ill-conditioning of the inverse problem. We present a multiscale simulation over a model composed of a sphere (approximating the heart) contained in a torso tank. The spherical geometry made it easier for us to set different discretization scales for the heart. With the torso mesh unchanged, we tested three sphere models, each with 134, 236, and 612 nodes on the surface. Fig. 1 shows that the ill-conditioning of the transfer matrix is worsened with the increase of the heart resolution, or equivalently, the fidelity of the inverse solution. Fig. 1 indicates that arbitrary refinement may be inappropriate for inverse problems—a discrete heart model of 612 nodes already has singular values of K below double-digit precision. Considering the extra geometric complexities, the inverse problem with a real heart is even more ill-conditioned than the sphere model considered here. Therefore, we have a good reason to believe that one should cautiously discretize the heart surface based on practical needs rather than perform arbitrary refinement. 2) Discretization of the Torso Volume: Here, we explore the impact of the discretization of the torso volume. Keeping both

Fig. 2. Fixing the boundary discretization and refining the volume conductor. N e denotes the number of elements in each mesh. (A) Singular values of AV H . (B) Singular values of K.

the torso surface and the heart surface unchanged, we set the torso volume mesh in four resolutions. Fig. 2 shows the singular values of the resulting transfer matrix K and its components AV H . Panel A shows that volume refinement significantly improves the “heart-to-volume” projector AV H , because such refinement well represents the high-gradient region around the heart. The improvement of AV H subsequently improves K. The way we interpret the singular value spectra of K in Panel B exemplifies how to evaluate the conditioning of a discrete inverse problem. With a good discretization (37 444 elements), the singular values descend slowly, reflecting the intrinsic illposedness of the underlying continuous problem. In contrast, with a coarse discretization (10 454 elements), the singular values of K abruptly drops to near zero from the position 175 among a total of 337 values, enlarging the proportion of the null space of K. This expansion of the null space represents a supplementary ill-conditioning not stemming from the intrinsic ill-posed nature, but rather caused by insufficient discretization. As discussed in Section III-A, the resolution on the epicardium sets the frequency bandlimit of potentials one seeks to recover, whereas the resolution of the volume conductor determines the bandlimit that is actually solvable. When the former exceeds the latter, the formed transfer matrix K cannot hold the relationship of the two frequency bandlimits, resulting in an artificially introduced null space. This discrepancy should be and can be avoided, so we regard the smoothing of singular values as a sign of improvement in the conditioning of the inverse problem. One may see that refinement from 27 361 elements to 37 444 elements does not noticeably change the singular value spectra of the matrices concerned. This is because the improvement brought by discretization is bounded by the ill-posed nature of the continuum problem. Hence, overrefinement beyond a certain level is not cost effective. To further compare the quality of the numerical systems shown in Figs. 2 and 3 shows their reconstructed epicardial potential maps at several representative time instants in a cardiac cycle. In early activation phase (3 ms after the QRS onset), the refined mesh (Mesh 3) better reconstructs the amplitude than the coarse mesh (Mesh 1). When epicardial potentials exhibit diverse pattern (21 ms), the refined mesh outperforms the coarse

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

1833

Fig. 4. Activation isochrones derived from reconstructed epicardial potentials in Fig. 3. Top row: Anterior view. Bottom row: Posterior view.

Fig. 3. Epicardial potentials calculated from the meshes discussed in Fig. 2, under 30-dB white noise. N e denotes the number of elements each in mesh. To effectively visualize the difference in potential patterns, the view is changed at each instant. Epicardial potentials at 21 ms exhibit the most diverse spatial pattern in the entire cardiac cycle, and hence is the hardest to recover.

mesh in recovering the saddle region in the center of the heart. Also at this instant, the isopotential contours from Meshes 2 and 3 outline the negative minimum point located at the center left of the measured potential map, while the contours from Mesh 1 captures this feature poorly. Fig. 4 presents the activation isochrones derived from the epicardial potentials presented in Fig. 3. It shows that volume refinement improves the recovery of the activation time, particularly eliminating artifacts in the activation map. 3) 3-D Hybrid Mesh Setup: The hybrid mesh was formed by padding layers of prisms around the epicardium (or the surface of any tissue). Prism elements then form a new closed triangular surface (like an enlarged heart), from which we used BioMesh3D [32] to generate tetrahedral mesh for the rest body volume (see Fig. 5 for illustration). The refinement in the normal direction was achieved by making more layers of thinner prisms. 4) Refining the Normal Direction: We explored the impact of the resolution in the normal direction by refining a region of prism layers around the heart while fixing the rest of the volume mesh. We set the “prism zone” to be within 10 mm from the epicardium, and create three hybrid meshes having one, two, and four layers of prisms within the “10-mm prism zone.” The thickness of prisms are 10, 5, and 2.5 mm accordingly. All three

Fig. 5. (a) Cross section of a torso mesh, where the heart is surrounded by two layers of prism elements. (b) Hybrid mesh at the heart-volume interface.

Fig. 6. Refining the resolution normal to the heart by prismatic elements. (a) Singular values of AV H . (b) Singular values of K.

meshes share a coarse tetrahedral mesh in the volume (8106 tetrahedra), which is fixed so as to isolate the effects of refinement in the normal direction. To isolate the effect induced by prisms, we compared the hybrid meshes with a pure tetrahedral mesh in approximate resolution. Fig. 6 presents the singular values of the heart-to-volume projector AV H and the transfer matrix K. Compared to the pure tetrahedral mesh, all three hybrid meshes improve AV H significantly and improve K moderately. Panel B shows that refining the normal direction beyond a certain level may not bring much difference in the resulting numerical system. Fig. 7

1834

Fig. 7. Activation time derived from epicardial potentials calculated from the meshes in Fig. 6. (a) From measured potentials. (b) From the pure tetrahedral mesh. (c) From the hybrid mesh with one layer of 10-mm-thick prisms. (d) From the hybrid mesh with two layers of 5-mm-thick prisms. (e) From the hybrid mesh with four layers of 2.5-mm-thick prisms.

Fig. 8. Epicardial potentials computed from hybrid meshes. (a) Exact value. (b) Pure tetrahedral mesh. (c) Hybrid mesh with one layer of prisms. (d) Hybrid mesh with two layers of prisms. (e) Hybrid mesh with four layers of prisms. rg ra d is the ratio of the computed value to the real value of ∇uH , the norm of the epicardial potential gradient field.

compares the activation map derived from the reconstructed epicardial potentials. Hybrid meshes result in better recovery of activation isochrones. The effect of the normal-direction resolution is more evident when the inverse problem is solved by the gradient-oriented FOT. We implemented the FOT using the variational-formed gradient operator. Fig. 8 shows the recovered epicardial potentials at a representative instant, when the potentials exhibit the most diverse spatial pattern. Refining the normal direction improves RE and CC slightly, but recovers a larger proportion of the potential gradient field on the epicardium, as indicated by rgrad rising from 76% to 91%. rgrad is the ratio of the computed value to the real value of the norm of the gradient field ∇uH . Maintaining sharp gradients is an important goal in inverse calculation because the Tikhonov method tends to oversmooth its inverse solution. Such improvement is achieved in two ways. First, refinement in the normal direction assumes higher gradients to be represented by discretization, thereby improving the transfer matrix. Second, the refinement increases the magnitude of the stiffness matrix, which then enhances the regularizing effect of the variational gradient operator (based on the stiffness matrix). This test exemplifies how discretization choices may achieve regularization effects and affect inverse solutions. 5) Volume Refinement With the Hybrid Mesh: This test was meant to be a comparative study to the volume-refining test presented in Section V-B2. Because the test uses tetrahedral elements only, refining the volume inevitably changes the discretization of the heart-to-volume interface. With the hybrid mesh, we are able to isolate the impact of volume refinement by

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

Fig. 9. Refining the volume while fixing the meshes around the heart by two layer of 5-mm-thick prisms. Meshes 1, 2, and 3 contain 8106, 13 636, and 23 361 tetrahedral elements, respectively. (A) Singular values of N and AV H . (B) Singular values of K.

fixing the prism mesh around the heart while refining the rest of the volume. We set two layers of 5-mm-thick prisms so as to reasonably approximate the gradient field around the heart. The rest of the torso volume was filled with 8106, 13 635, and 23 361 tetrahedral elements, respectively, with the torso surface triangulation unchanged. Fig. 9 presents the resulting AV H , N, and K. It confirms our conjecture that the extension of singular values N and K are attributed to the refinement of interior volume, not the refinement of the heart-volume interface. Note that AV H was intact in this test because the discretization of the heart-volume interface was fixed by prism elements. C. Variational-Form Regularizers 1) Variational Gradient Operator in Regularization: Here, we demonstrate the efficacy of the variational gradient operator given by Table I when used in the FOT regularization. We compare the FOT with conventional ZOT and SOT. The ZOT uses an identity matrix as regularizer. The SOT uses a discrete Laplacian operator obtained by solving a least-squares problem arising from second-order Taylor expansion at each point, proposed by [33]. Fig. 10 compares the epicardial potentials reconstructed by the three methods. Overall, the FOT and SOT perform closely, both outperforming the ZOT. The FOT sometimes outperforms the SOT in capturing local spatial patterns or isopotential contours: e.g., the contours at 10 ms, the saddle point at the heart center at 21 ms, and the isopotential contours at 27 ms. These observations are reasonable, for the Laplacian regularizer tends to smooth contours, whereas the gradient-based regularizer preserves contours better. 2) Norm Preservation in Multiscale Simulation: In multiscale discretization, variational-form operators preserve the norm because they consider the continuous L2 norm which is irrespective of resolution. In contrast, conventional discrete operators consider the Euclidean norm, which depends on the size of discretization. We illustrate this point by comparing the traditional regularizer and the variational one under the ZOT regularization. The traditional regularizer is an identity matrix, whereas the variational-formed regularizer is derived from the mass matrix given by Table I. Each regularizer was tested with two discrete models: a coarse Mesh 1 and a uniformly refined Mesh 2. On the

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

Fig. 10. Epicardial potentials calculated under 30-dB SNR input white noise. ZOT, FOT, and SOT denote the zero-, first-, and second-order Tikhonov regularization. To better show spatial patterns, the view is rotated.

heart surface, Mesh 2 has four times as many nodes as Mesh 1, i.e., the discrete problem yielded by Mesh 2 is four times the size of that from Mesh 1. Fig. 11 compares the L-curves resulting from the multiscale test of each regularizer. Panel A shows the L-curves from the identity matrix, and Panel B shows the L-curves from the mass matrix. In Panel A, refinement pushes the L-curve to the upper right, indicating that refinement increases both the residual error and the constraint (here the solution norm). In contrast, in Panel B, the L-curve is not significantly affected by refinement. Note that Panels A and B have different axis scales. Fig. 11 marks the value of λ associated with the corner of each L-curve, which typically estimates a reasonable amount of regularization one should apply. In Panel B, both the residual error and the solution norm at the corner are preserved during refinement. In Panel A, the residual error and the solution norm at the corner are nearly doubled. Recall that the size of the inverse solution vector is increased by four times from Mesh 1 to Mesh 2, but uH , the Euclidean norm of the solution vector, is only doubled. This indicates that the traditional Tikhonov regularization tends to oversmooth the inverse solution when discretization is refined, causing inconsistent regularization under multiscale simulations. This inconsistency is also manifested in Fig. 12, where we compare the inverse solutions at a time instant when the

1835

Fig. 11. L-curves of the solution norm versus the residual error when ZOT is performed. The inverse problem is discretized in two scales. Mesh 1 has 27 361 tetrahedral elements with 670 triangular elements on the heart surface. Mesh 2 has 60 617 volume elements with 2680 triangles on the heart surface. (a) Regularizer is the identity matrix, with the residual error and the regularizer evaluated by the Euclidean norm. (b) Variational regularizer derived from the mass matrix given by Table I, evaluated by the continuous L 2 norm. λ indicates the regularization parameter corresponding to the corner of L-curves.

epicardial potential pattern is the most diverse. When refining Mesh 1 to Mesh 2, the identity-matrix regularizer yields inconsistent potential patterns, increasing the RE from 0.50 to 0.53. In contrast, the variational-formed regularizer maintains the solution pattern overrefinement, reducing the error from 0.48 to 0.42. VI. DISCUSSION A. Finite-Element Discretization Our primary goal is to explore how the finite-element discretization of the ECG model influences the numerical conditioning of the inverse ECG problem, so as to formulate a, numerical problem optimal for inversion. While there are a large number of research studies targeted at stabilizing the ill-posedness by various regularization techniques, few studies concentrate efforts on improving the numerical quality of inverse problems before their inverse solutions are sought. In fact, proper discretization strategies can be used in combination with regularization methods so as to achieve additional improvement to the inverse solution accuracy.

1836

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

problem; and 2) the time for solving the minimization. The first time is dominant and is linear in the number of elements being used. Hybrid meshes enables us to improve accuracy without dramatically increasing the mesh size and hence the CPU time. The time for minimizing (13) (for each value of λ) is 1–2 s in MATLAB with four 2.66-GHz Intel Xeon cores, given that the size of the linear problem is 771 × 337 (the number of nodes on the torso and heart surfaces, respectively). B. Variational-Form Regularizers

Fig. 12. Epicardial potentials reconstructed under 30-dB SNR input noise by ZOT using the traditional and the variational regularizers, corresponding to the L-curves in Fig. 11. For each inverse solution, RE and CC are given.

To assess the impact of discretization, our methodology includes testing different finite-element discretization strategies and then evaluating their resulting transfer matrix (the inverse problem) by singular value analysis. We then evaluate the inverse solutions in terms of quantitative metrics, epicardial potential patterns, and activation isochrone maps. The inverse solutions are calculated by a fixed regularization method (mostly SOT) in order to isolate the effect of discretization and to minimizing the effect of regularization. Our experiments based on 3-D models obtained consistent results with our previous study in the 2-D case [11]. The results corroborate the inverse-problem discretization guidelines proposed in Section III-B. Fig. 1 indicates that the epicardial resolution for which we seek should be limited based on practical needs lest the discretized inverse problem become overly ill-conditioned. Meanwhile, refining the volume conductor improves the conditioning of the transfer matrix (see Fig. 2), the reconstructed epicardial potentials (see Fig. 3), and activation isochrones (see Fig. 4). The use of hybrid meshes enables one to refine the high gradient field around the heart without incurring aspect-ratio problems. Such refinement improves the accuracy of the heartto-volume projection (see Fig. 6) and the reconstruction of epicardial potential gradients (see Fig. 8), which in turn improves the recovery of the activation isochrone map (see Fig. 7). It is worth comparing the refinement in the normal direction to the heart to previous studies that use the potential gradient or current density (from a physical view) as a constraint in regularizing the inverse ECG problem [26], [27]. The spatial refinement implicitly assumes that a higher gradient is being sought, so it achieves a similar regularizing effect often referred to as “regularization by discretization” [14], [34]. The CPU time of our ECG simulation consists of: 1) the time for building the finite-element model and the minimization

The central idea of the variational-form-based regularization is to measure the potential field by the L2 norm in place of the Euclidean norm. Because the L2 norm is inherently assumed by common FEM (e.g., Galerkin formulation), the variationalformed regularization automatically conforms to certain variational principles underlying the discrete inverse problem formulated by FEM. Defined over a continuous domain, the L2 norm is independent of discretization resolution, thereby ensuring that the discretized problem is handled in conformity to its underlying continuous problem. The Euclidean norm, in contrast, does not reflect the features of the continuous problem. The preservation of norms is important when applied to multiscale simulation of inverse problems, because it ensures regularization be performed consistently among numerical problems of different scales. Here, the consistency means that the balance between the residual error and the regularizing term is maintained. The requirement of consistency is based on the understanding that all discrete problems should reflect the nature of their common continuous origin. The consistency cannot hold when the Euclidean norm is used. When conventional discrete operators are used in the Tikhonov regularization, the residual error and the regularizer may not increase by the same rate under refinement. If the residual error increases faster than the regularizer, more weight will be put on the residual error and the inverse problem tends to be underregularized. Conversely, the inverse problem will be overregularized. In our example of testing ZOT method under multiscale discretization, Fig. 11 shows that the preservation of L2 norm leads to consistent regularization, which consequently leads to consistent reconstruction of epicardial potentials, as shown by Fig. 12. The traditional Euclidean-norm-based regularization does not exhibit the consistency. The introduction of resolution-consistent regularization may pave the way for adaptive FEM to be used for solving inverse problems. Despite its many successes in reducing complexity and enhancing efficiency for solving PDE-based forward problems, adaptive FEM has not yet been widely applied to inverse problems. By taking advantage of their natural consistency within the FEM Galerkin framework, resolution-consistent regularization may solve the issues that arise with nonuniform volumetric resolution. It is straightforward to implement the variational-formed regularization in the L2 norm, by slightly modifying the implementation of traditional Tikhonov methods. The Euclidean norm of the epicardial potentials uH is given by uH 2 = (uTH uH )1/2 , ˜H is given whereas the L2 norm of the continuous distribution u

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

by ˜ uH L 2 = (uTH MuH ), where the mass matrix M is given in Table I. Evaluating the L2 norm is achieved by adding a weighing matrix that is based on finite-element basis functions. The norm of the residual error defined on the torso surface, or the norm of any gradient field, can be obtained in a similar way by modifying the weighing matrix accordingly. The weighing matrix can be precomputed using the mesh information only. The stiffness matrix and matrices formed by higher order derivatives are positive semidefinite because the derivative of any constant field is always zero. The Cholesky decomposition for these matrices is not unique, but we do not believe that this fact will effect the outcome of Tikhonov regularization because the Tikhonov method considers the L2 norm of the regularizers. We selected a Cholesky factorization in a systematic way. Assume, we decompose the stiffness matrix S. We take the sequence Sk = S + k1 I, where I is the identity matrix. Sk → S when k → ∞. Each {Sk } is positive definite and has a unique Cholesky factor Lk . We take L = limk →∞ Lk as the Cholesky factor of S. The convergence of {Lk } holds because the operators are bounded and their underlying vector space is finite dimensional. VII. CONCLUSION We investigated how finite-element discretization can be constructed specifically for the inverse ECG problem so as to optimize its numerical conditioning. Extending our previous 2-D study to 3-D, this paper provides discretization guidelines for practical ECG simulations and their realization via a hybrid mesh scheme. We also proposed a new family of variational regularizers based on the continuous L2 norm. These regularizers are an alternative to the traditional Tikhonov regularization but achieve consistent regularization over multiscale simulation. The variational formulation also enables a simple construction of the discrete gradient operator over an irregular mesh, which is difficult to obtain with traditional discretization techniques. The hybrid mesh scheme and the variational-formed regularization were validated via simulation based on a realistic 3-D torso/heart model with real heart data. Future work includes coupling the maximum fidelity allowed for the heart with other biophysical constraints (such as the distributed current density source within the heart). Evaluating the impact of tissue conductivity on the inverse ECG will also be valuable, while the impact on the forward ECG has been reported [35], [36]. Human tissue conductivities are estimated by electrical impedance tomography, a technique under active research both mathematically [37] and clinically [38]. ACKNOWLEDGMENT

[3]

[4]

[5]

[6] [7] [8] [9] [10] [11] [12]

[13] [14] [15] [16] [17] [18] [19] [20] [21]

[22] [23] [24] [25]

The authors would like to thank Dr. MacLeod for sharing the ECG data. [26]

REFERENCES [1] A. Intini, R. Goldstein, Y. Rudy, P. Jia, and A. Waldo, “Electrocardiographic imaging (ECGI), a novel diagnostic modality used for mapping of focal left ventricular tachycardia in a young athlete,” Heart Rhythm, vol. 2, no. 11, pp. 1250–1252, 2005. [2] P. Jia, C. Ramanathan, Y. Rudy, R. N. Ghanem, K. Ryu, and N. Varma, “Electrocardiographic imaging of cardiac resynchronization therapy in

[27] [28]

1837

heart failure: Observation of variable electrophysiologic responses,” Heart Rhythm, vol. 3, no. 3, pp. 296–310, 2006. S. Ghosh, J. Avari, Y. Rudy, E. K. Rhee, and P. K. Woodard, “Noninvasive electrocardiographic imaging of epicardial activation before and after catheter ablation of the accessory pathway in a patient with ebstein anomaly,” Heart Rhythm, vol. 5, no. 6, pp. 857–860, 2008. S. Ghosh, E. Rhee, Y. Rudy, J. N. Avari, and P. K. Woodard, “Cardiac memory in patients with Wolff-Parkinson-White syndrome: Noninvasive imaging of activation and repolarization before and after catheter ablation,” Circulation, vol. 118, no. 9, pp. 907–915, 2008. R. C. Barr, M. Ramsey, and M. S. Spach, “Relating epicardial to body surface potential distributions by means of transfer coefficients based on geometry measurements,” IEEE Biomed. Eng., vol. BME-24, no. 1, pp. 1– 11, Jan. 1977. R. M. Gulrajani, Bioelectricity and Biomagnetism. New York: Wiley, 1998. I. Babuˇska, T. Strouboulis, C. Upadhyay, S. Gangaraj, and K. Copps, “Validation of a posteriori error estimators by a numerical approach,” Int. J. Numer. Methods Eng., vol. 37, pp. 1073–1123, 1994. D. Weinstein, C. Johnson, and J. Schmidt, “Effects of adaptive refinement on the inverse EEG solution,” SPIE, vol. 2570, pp. 2–11, 1995. C. Johnson and R. S. MacLeod, “Nonuniform spatial mesh adaptation using a posteriori error estimates: Applications to forward and inverse problems,” Appl. Numer. Math., vol. 14, pp. 311–326, 1994. C. Johnson, “Computational and numerical methods for bioelectric field problems,” Crit. Rev. Biomed. Eng., vol. 25, no. 1, pp. 1–81, 1997. D. Wang, R. Kirby, and C. Johnson, “Resolution strategies for the finiteelement-based solution of the ECG inverse problem,” IEEE Trans. Biomed. Eng., vol. 57, no. 2, pp. 220–237, Feb. 2010. P. R. Johnston, S. J. Walker, J. A. K. Hyttinen, and D. Kilpatrick, “Inverse electrocardiographic transformations: Dependence on the number of epicardial regions and body surface data points,” Math. Biosci., vol. 120, pp. 165–187, 1994. V. Isakov, Inverse Problems for Partial Differential Equations, 2nd ed. ed. New York: Springer-Verlag, 2006. H. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems. Norwell, MA: Kluwer, 2000. A. Kirsch, An Introduction to the Mathematical Theory of Inverse Problems. New York: Springer-Verlag, 1996. J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems. New York: Springer-Verlag, 2004. A. Tikhonov and V. Arsenin, Solutions of Ill-Posed Problems. Washington, DC: V. H. Winston & Sons, 1977. F. Natterer, “Error bounds for Tikhonov regularization in Hilbert scales,” Appl. Anal., vol. 18, pp. 29–37, 1984. W. Bangerth and A. Joshi, “Adaptive finite element methods for the solution of inverse problems in optical tomography,” Inverse Problems, vol. 24, no. 3, p. 034011, 2008. Y. Yamashita, “Theoretical studies on the inverse problem in electrocardiography and the uniqueness of the solution,” J-BME, vol. 29, pp. 719–725, 1982. B. Messnarz, M. Seger, R. Modre, G. Fischer, F. Hanser, and B. Tilg, “A comparison of noninvasive reconstruction of epicardial versus transmembrane potentials in consideration of the null space,” IEEE Trans. Biomed. Eng., vol. 51, no. 9, pp. 1609–1618, Sep. 2004. J. Shewchuk, “What is a good linear finite element? interpolation, conditioning, anisotropy, and quality measures,” in Proc. 11th Int. Mesh Roundtable, 2002, p. 70. E. M. Karniakakis and S. P. Sherwin, Spectral/hp Element Methods for CFD. Oxford, U.K.: Oxford Univ. Press, 1999. D. Wang, R. Kirby, and C. Johnson, “Finite element refinements for inverse electrocardiography: Hybrid shaped elements and high-order element truncation,” Comput. Cardiol., vol. 36, pp. 193–196, 2009. R. Throne and L. Olson, “A comparison of spatial regularization with zero and first order Tikhonov regularization for the inverse problem of electrocardiography,” Comput. Cardiol., vol. 27, pp. 493–496, 2000. D. S. Khoury, “Use of current density in regularization of the inverse problem of electrocardiography,” in Proc. 16th Int. Conf. IEEE EMBS, vol. 3–6, Baltimore, MD, 1994, pp. 133–134. S. Ghosh and Y. Rudy, “Application of l1-norm regularization to epicardial potential solution of the inverse electrocardiography problem,” Ann. Biomed. Eng., vol. 37, no. 5, pp. 902–912, 2009. G. F. Ahmad, D. H. Brooks, and R. S. MacLeod, “An admissible solution approach to inverse electrocardiography,” Ann. Biomed. Eng., vol. 26, pp. 278–292, 1998.

1838

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

[29] D. Brooks, G. Ahmad, and R. MacLeod, “Inverse electrocardiography by simultaneous imposition of multiple constraints,” IEEE Trans. Biomed. Eng., vol. 46, no. 1, pp. 3–18, Jan. 1999. [30] L. Eld´en, “Algorithms for the regularization of ill-conditioned least squares problems,” BIT, vol. 17, pp. 134–145, 1977. [31] R. MacLeod, B. Taccardi, and R. Lux, “Electrocardiographic mapping in a realistic torso tank preparation,” in Proc. 17th IEEE Eng. Med. Bio. Conf., 1995, pp. 245–246. [32] BioMesh3D: Quality Mesh Generator for Biomedical Applications. Scientific Computing and Imaging Institute (SCI), Univ. Utah, Salt Lake City. (2011). [Online]. Available: http://www.biomesh3d.org [33] G. Huiskamp, “Difference formulas for the surface laplacian on a triangulated surface,” J. Comp. Phys., vol. 95, no. 2, pp. 477–496, 1991. [34] H. Engl and A. Neubauer, “Convergence rates for Tikhonov regularization in finite-dimensional subspaces of hilbert scales,” Proc. Amer. Math. Soc, vol. 102, pp. 587–592, 1988. [35] S. Geneser, R. Kirby, and R. MacLeod, “Application of stochastic finite element methods to study the sensitivity of ECG forward modeling to organ conductivity,” IEEE Trans. Biomed. Eng., vol. 55, no. 1, pp. 31–40, Jan. 2008. [36] D. U. J. Keller, F. M. Weber, G. Seemann, and O. D¨ossel, “Ranking the influence of tissue conductivities on forward-calculated ECGs,” IEEE Trans. Biomed. Eng., vol. 57, no. 7, pp. 1568–1576, Jul. 2010. [37] M. Cheney, D. Isaacson, and J. C. Newell, “Electrical impedance tomography,” SIAM Rev., vol. 41, no. 1, pp. 85–101, 1999. [38] T. J. C. Faes, H. A. v. derMeij, J. C. d. Munck, and R. Heethaar, “The electric resistivity of human tissues (100 Hz—10 MHz): A meta-analysis of review studies,” Physio. Meas., vol. 20, pp. 1–10, 1999.

Robert M. Kirby (M’02) received the M.S. degree in applied math, the M.S. degree in computer science, and the Ph.D. degree in applied mathematics from Brown University, Providence, RI, in 1999, 2001, and 2002, respectively. He is currently an Associate Professor of Computer Science at the School of Computing, an Adjunct Associate Professor in the Departments of Bioengineering and of Mathematics, and a member of the Scientific Computing and Imaging Institute, all at the University of Utah, Salt Lake City. His research interests include scientific computing and visualization.

Dafang Wang (S’09) was born in Hangzhou, China, in 1984. He received the B.S. degree in computer science from Zhejiang University, Hangzhou, China, in 2005. He is currently working toward the Ph.D. degree in computer science at the School of Computing, University of Utah, Salt Lake City. He is also a Research Assistant at Scientific Computing and Imaging Institute, University of Utah. His research interests include inverse problems, scientific computing, bioelectricity, and electrocardiography.

students. Dr. Johnson has received several awards, including the NSF Presidential Faculty Fellow (PFF) Award from the President Clinton in 1995 and the Governor’s Medal for Science and Technology from the Governor Michael Leavitt in 1999. He is a Fellow of the American Institute for Medical and Biological Engineering (AIMBE), a Fellow of the American Association for the Advancement of Science (AAAS), and a Fellow of the Society of Industrial and Applied Mathematics (SIAM). He serves on several international journal editorial boards, as well as on advisory boards to several national research centers.

Chris R. Johnson received the Ph.D. degree from the University of Utah, Salt Lake City, in 1989. He directs the Scientific Computing and Imaging (SCI) Institute, University of Utah, where he is currently a Distinguished Professor of Computer Science and holds Faculty appointments in the Departments of Physics and Bioengineering. His research interests are in the areas of scientific computing and scientific visualization. He founded the SCI Research Group in 1992, which has since grown to become the SCI Institute employing over 150 faculty, staff, and

View more...
1827

Finite-Element-Based Discretization and Regularization Strategies for 3-D Inverse Electrocardiography Dafang Wang, Student Member, IEEE, Robert M. Kirby, Member, IEEE, and Chris R. Johnson∗

Abstract—We consider the inverse electrocardiographic problem of computing epicardial potentials from a body-surface potential map. We study how to improve numerical approximation of the inverse problem when the finite-element method is used. Being ill-posed, the inverse problem requires different discretization strategies from its corresponding forward problem. We propose refinement guidelines that specifically address the ill-posedness of the problem. The resulting guidelines necessitate the use of hybrid finite elements composed of tetrahedra and prism elements. Also, in order to maintain consistent numerical quality when the inverse problem is discretized into different scales, we propose a new family of regularizers using the variational principle underlying finiteelement methods. These variational-formed regularizers serve as an alternative to the traditional Tikhonov regularizers, but preserves the L2 norm and thereby achieves consistent regularization in multiscale simulations. The variational formulation also enables a simple construction of the discrete gradient operator over irregular meshes, which is difficult to define in traditional discretization schemes. We validated our hybrid element technique and the variational regularizers by simulations on a realistic 3-D torso/heart model with empirical heart data. Results show that discretization based on our proposed strategies mitigates the ill-conditioning and improves the inverse solution, and that the variational formulation may benefit a broader range of potential-based bioelectric problems. Index Terms—Forward/inverse electrocardiographic problem, hybrid finite-element method, regularization, variational formulation.

I. INTRODUCTION LECTROCARDIOGRAPHY (ECG) investigates the relationship between the electrical activity of the heart and its induced voltages measured on the torso surface. This relationship can be characterized mathematically as a forward problem

E

Manuscript received November 15, 2010; revised January 22, 2011; accepted February 14, 2011. Date of publication March 3, 2011; date of current version May 18, 2011. The work of R. M. Kirby and C. R. Johnson was supported in part by the NSF Career Award under Grant NSF-CCF0347791 and in part by the NIH NCRR Center for Integrative Biomedical Computing (www.sci.utah.edu/cibc) under Grant 5P41RR012553-12. Asterisk indicates corresponding author. D. Wang and R. M. Kirby are with the Scientific Computing and Imaging (SCI) Institute and the School of Computing, University of Utah, Salt Lake City, UT 84112 USA (e-mail: [email protected]; [email protected]). ∗ C. R. Johnson is with the Scientific Computing and Imaging (SCI) Institute and the School of Computing, University of Utah, Salt Lake City, UT 84112 USA (e-mail: [email protected]). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TBME.2011.2122305

in which one estimates the body-surface potentials based upon cardiac activities represented either by epicardial potentials or current sources within the heart; or as an inverse problem where the goal is to noninvasively estimate cardiac electrical activity from voltage distributions measured on the body surface. This paper studies one type of potential-based inverse ECG problem: to reconstruct epicardial potentials from recorded body-surface potential maps. This inverse problem is a basis for some promising clinical applications, such as noninvasive diagnosis [1], [2] and guidance for intervention [3], [4]. The underlying bioelectric model is a potential-based boundary value problem [5], [6]. ECG simulation involves solving the mathematical equations over a geometric domain that approximates the anatomical structure of a human body. Computational methods are applied to obtain a numerical solution suitable for clinical purposes. In order to validate the results obtained, one needs to ensure that the simulation accurately reflects the actual process concerned, a step often known as validation and verification (V&V) in the engineering literature [7]. The goal of this paper is to develop discretization and refinement strategies to be employed when solving the inverse ECG problem with finite-element methods (FEM). Refinement decreases discretization errors by increasing the resolution (or fidelity) of the numerical approximation at the cost of increased computational work. With such strategies in place, one can specify an acceptable discrepancy between the true and approximate solutions and can tune (or refine) the numerical and geometric approximations accordingly. Although refinement methods are widely used in many engineering fields including the ECG community, they are mostly targeted toward the “forward simulation” [8]–[10], which may be inappropriate for the inverse ECG problem [11]. The inverse problem requires different discretization considerations from its corresponding forward problem because of its ill-posed nature, i.e., small input errors may result in unbounded errors in the solution. However, the literature on discretization specifically for the inverse problem is limited. Although the impact of discretization of the epicardium and the body surface has been investigated [12], it still remains an open question as to how discretization is related to the ill-conditioning, and accordingly how one should develop discretizations that optimize the problem’s conditioning while minimizing the approximation error. This paper aims to address this gap at a practical level. To tackle the ill-posedness of an inverse problem, one typically needs “regularization” techniques, which impose constraints on the original problem so as to yield a better-posed

0018-9294/$26.00 © 2011 IEEE

1828

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

problem [13]–[17]. While most regularization methods are applied in the problem-solving phase, it is worth noting that discretization itself is one form of regularization, impacting the numerical conditioning of the discretized problem [18]. A sensible discretization can be readily combined with classical regularization methods to achieve additional improvement to the inverse problem solution. Using a 2-D torso model, our prior study [11] proposed finiteelement refinement strategies specifically for the inverse ECG problem and introduced hybrid finite elements in 2-D. This paper extends our finite-element discretization study to 3-D for simulations based on realistic human anatomical structures with clinical applications. Another major contribution of this paper is a new formulation of regularizers that facilitates finite-element simulation under multiscale simulations. Formed by the variational principle underlying the FEM, the variational-formed regularizers work within the classic Tikhonov regularization framework but have several advantages over the traditionally implemented Tikhonov regularizers. First, the variational regularizers keep the connection between the discretized model and its underlying continuous model, and automatically conform to certain variational properties inherently assumed by the discrete model resulting from FEM. Second, the variational regularizers preserve their norms, and thereby maintain consistent regularization when the inverse ECG problem is computed under multiscale simulations. Third, the variational formulation enables easy construction of the discrete gradient operator, which is traditionally difficult to obtain over irregular mesh. Fourth, it allows efficient imposition of multiple constraints simultaneously. This formulation may provide new insights into a broader range of potential-based bioelectric problems. This paper is structured as follows. Section II describes the mathematical model of the forward/inverse ECG problem and its discretization by FEM. Section III discusses the ill-posedness, based on which we propose the discretization strategies for the inverse ECG problem. Section IV presents the variational-formbased regularization. Section V presents our simulation results based on a realistic 3-D torso model. Section VI presents further discussion and the proposed future work.

A. Mathematical Model The potential field u within a torso is modeled by the Laplace equation as follows: ∇ · (σ(x)∇u(x)) = 0,

u(x) = uH (x), n · σ(x)∇u(x) = 0,

An inverse problem is typically solved within a framework known as model-based optimization or partial differential equations (PDE)-constrained parameter estimation [19]. In such a framework, one first builds a forward model that is able to predict measurement data if the source parameters (in our case, epicardial potentials) are given. The forward model is often governed by PDE. Then, the inverse model is formed as an optimization problem to determine the values of parameters such that their resulting prediction is closest to the measurements. In this section, we present the mathematical model of the forward/inverse ECG problem. We then review how to convert the continuous model into a discrete system by using FEM.

x ∈ ΓH

x ∈ ΓT

(1) (2) (3)

where Ω is the torso volume bounded by the epicardial surface ΓH and the torso surface ΓT . uH is the epicardial potentials (a Dirichlet condition), and σ(x) is the conductivity. Equation (3) means no electric flux leaves the body into the air. The forward problem estimates the potential field u(x) given uH . The inverse problem aims to recover uH from u(x) that reside on ΓT . B. Finite-Element Discretization Here, we describe how to apply the FEM to discretize (1)– (3) over a realistic 3-D torso domain. A comprehensive FEM formulation can be found in our previous paper [11]. The FEM tessellates the 3-D domain Ω into a mesh, which is normally composed of nonoverlapping tetrahedral, prismatic, or cubic elements. One then builds an approximate solution that is a combination of certain element-wise basis functions. The solution is identified by making it satisfy the differential equation in the Galerkin sense. ˆi φi (x), where u ˆi is We consider linear FEM: u(x) = i u the voltage at node i, and φi (x) is the linear hat function associated with node i and is nonzero only on its adjacent elements. Substituting the expansion into the differential equation (1), applying the Galerkin method and integrating by parts, one will get a linear system as follows: uV −AV H A V V AV T (4) = uH AT V AT T uT −AT H where mesh nodes are divided into three groups, indicated by the subscripts: the nodes on the heart surface H, on the torso surface T , and in the interior torso volume V . uV , uT , and uH denote the vectors of voltages at each group of nodes. The submatrices are given by J, K ∈ {V, T, H} (5) where (·, ·) means the inner product taken over the domain Ω: (∇φi , ∇φj ) = Ω ∇φi ∇φj dΩ. The matrix on the left side is known as the stiffness matrix and the right-side vector is the “forcing term” induced by the known Dirichlet boundary conditions. Normally, no element spans from the heart surface to the torso surface, and AT H = 0. From (4), we derive the relation between the torso potentials uT and the epicardial potentials uH as follows: AJ K = (∇φj , σ∇φk );

II. PROBLEM FORMULATION OF THE INVERSE PROBLEM

x∈Ω

j ∈ J, k ∈ K;

uT = KuH , K = M−1 N.

(6)

Here, K is often referred to as the transfer matrix. M = AT T − AT V A−1 V V AV T is well conditioned and invertible. N = AT V A−1 V V AV H is severely ill-conditioned.

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

Based on (6), the discretized forward ECG problem can be stated as: calculate uT given uH and K. Its corresponding inverse problem is given uT and K; find uH that minimizes the functional KuH − uT in certain appropriate norms. III. DISCRETIZATION FOR INVERSE PROBLEM A. Ill-Posedness of the Inverse Problem Despite having a unique solution [20], the aforementioned inverse ECG problem is severely ill-posed and its solution is highly unstable. The ill-posedness stems from information of the heart surface being attenuated when propagating through the body volume conductor. Hence, the inverse calculation is a process of amplification in which both the signal and noise are magnified. We briefly discuss how the discretization process translates the ill-posedness into an ill-conditioned numerical model problem, i.e., the transfer matrix. We refer readers to our previous study [11] for details. The magnitude of amplification (hence the degree of illconditioning) can be estimated by O((rT /rH )m ), where rH and rT are the average distance from the center of the heart to the heart surface and to the torso surface. It is an exponential function in m, the spatial frequency of the epicardial potential distribution. In a discrete problem, the spatial frequency bandlimit is dictated by the resolution on the epicardium, in analogy with the sampling theory about the bandlimit of a sampled signal with its sampling rate. Therefore, arbitrarily refining the heart surface may not be appropriate for solving the inverse problem. We evaluate the conditioning of the discrete problem by examining the singular value decomposition (SVD) of the transfer matrix K. Initially introduced in [21] and further developed in [11], the SVD analysis reveals how each frequency component of the epicardial potential contributes to the torso-surface potential, and the contribution is given by the corresponding singular value. The SVD also builds the concept of the valid space and the null space. The valid space of K is spanned by its right eigenvectors corresponding to nontrivial singular values, and the fraction of uH in that space can be recovered. The null space of K corresponds to near-zero singular values, and the fraction of uH in this space is not recoverable. Therefore, a better conditioned transfer matrix can be characterized by a slowly descending singular value spectrum with a broader range of nonzero singular values, whereas a poorly conditioned transfer matrix is characterized by a large portion of near-zero singular values. The SVD analysis provides a useful means for estimating the conditioning of an inverse problem, regardless of regularization methods, regularization parameters, input noise, or other method-specific factors. Different discretization choices lead to different singular value patterns of the transfer matrix. We use this methodology to evaluate our discretization strategies as follows. B. Discretization Strategy for the Inverse Problem In [11], we argue that through examining the solution procedure given by FEM, one can see three factors that jointly dictate the discretization quality for the inverse problem: 1) how ac-

1829

curate one should represent the cardiac source uH ; 2) how to approximate the volume conductor [the stiffness matrix on the left side of (4)]; and 3) how to compute the heart-to-volume projector AV H . Section III-A has argued that the fidelity on the heart surface determines how much information of epicardial potentials one seeks to recover. Meanwhile, the discretization of the torso volume determines how much of that information can actually pass through the body and be recoverable. The torso volume should be discretized in the same resolution as the heart surface, otherwise it will cause unnecessary, “artificial” ill-conditioning reflected as an expanded null space in the transfer matrix. Finally, to better approximate the heart-to-volume projection, one needs to refine the high potential gradient region around the heart. Based on these considerations, we proposed the following finite-element discretization guidelines for the inverse problem and verified the guidelines on a 2-D torso model [11]. This paper extends these guidelines to 3-D torso models. Results are presented in Section V. 1) Set the resolution on the heart surface based on the problem of interest, but be cautious not to add additional fidelity beyond what is needed. 2) While keeping the epicardial surface resolution fixed, increase the resolution in the normal direction to the heart surface. Such refinement captures the potential field around the heart where the spatial gradient is high, thereby improving the heart-to-volume projection AV H . 3) With the aforementioned two items in place, refine the volume conductor to a sufficient level so as to capture both the features of body-surface measurement and the features implied by the fidelity on the heart surface. For computational efficiency, exceeding that level is unnecessary. 4) Increasing the resolution of the torso surface is desirable, but only when the new resolutions are associated with the measured data. C. Hybrid Finite Elements The discretization guidelines mainly require refining the region around the heart while preserving the discretization of the heart surface. For a tetrahedral element mesh, which is popular in ECG simulation due to its simplicity, the previous requirement will lead to flat tetrahedra with high aspect ratios, which may induce numerical instability by themselves [22]. To overcome this issue, we adopted a hybrid mesh scheme that places layers of prismatic elements around the heart before filling the rest of the body volume with tetrahedral elements. Unlike tetrahedral elements, a prismatic element effectively decouples the resolution in its normal direction and the resolution on its base [23], thus enabling us to refine the direction normal to the heart without changing the resolution of the heart surface. The hybrid mesh is simple to implement. Mesh generation starts from triangulated bounding surfaces for each organ and tissue. Prisms are padded around any organ by extruding its triangulated surface into the body volume. The layers and the thickness of prisms can be adapted when the potential gradient is expected to change dramatically. The padded prisms form a

1830

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

new closed, triangulated surface, upon which standard tetrahedral mesh generation can be performed to fill the rest of the volume. The prisms and tetrahedra conform well at their bounding interface. D. Truncation from High-Order Finite Elements An alternative to spatial refinement is to use high-order finite elements, which achieve higher accuracy with more efficiency than linear finite elements. High-order FEM often increases the resolution uniformly, so we still need to limit the resolution on the heart surface. The traditional way is to use transitional elements but they are difficult to implement. Instead, we decompose the discrete model (6) into a hierarchy of an element-wise linear component, an element-wise quadratic component, and so on. We then extract and solve only the linear component of epicardial potentials, by truncating the transfer matrix properly. The high-order finite elements achieve the goal of refining the volume and the heart/torso interface, whereas the truncation keeps the epicardial resolution unchanged. Compared to the method of hybrid mesh, the truncation scheme provides a seamless solution for selective refinement. Conducted in the polynomial space, the truncation maintains the smoothness of the solution and circumvent the aspect-ratio problem that obstructs spatial refinement methods. The details of our truncation scheme can be found in our previous work [24]. IV. REGULARIZATION VIA A NEW FAMILY OF VARIATIONAL-FORM-BASED REGULARIZERS

ΓH

A. Classic Tikhonov Regularization The most common regularization for an inverse problem is the Tikhonov method given as follows: uH = argmin {KuH − uT 2 + λ2 (LuH 22 )}

such as the FOT [25], [26] or recently total-variation regularization [27]. Although a gradient field is not difficult to compute (by Taylor approximation or Gauss–Green theorem), it is difficult to derive an accurate discrete gradient operator in an explicit matrix form, especially on irregular, unstructured meshes. The matrix form requires representing the gradient at one node by the data at its neighboring nodes, an ill-posed problem when mesh nodes are irregularly distributed. The study [27] obtains the gradient operator over the heart surface via the boundary element method (BEM). This derivation can be found in [5, eq. (13)]. This method does not work for FEM because FEM and BEM treat boundary conditions differently. BEM includes both the Neumann boundary condition and the Dirichlet boundary condition on the heart surface, thus enabling a gradient operator relating the two. FEM only includes the Neumann boundary condition, and applies the Dirichlet boundary condition later as an external constraint. So, a gradient operator of this form is not available. 2) Variational-Based Formulation: We borrow the name “variational” from the context of FEM, upon which the formulation is based. The main idea is to consider epicardial potentials not as a vector, but as a continuous function represented by finite-element expansion: u ˜H (x) = k ukH φk (x), k ∈ H. The potential field is evaluated by the continuous L2 norm, which is defined as 1/2 1/2 uH , u ˜H ) = u ˜H u ˜H ds . (8) ˜ uH L 2 = (˜ Substituting the finite-element expansion into (8) yields ⎞ ⎛ j uiH φi , uH φj ⎠ = uTH MuH (˜ uH )2L 2 = ⎝ i

(7)

where · 2 is the Euclidean norm. The first term is the residual error and the second term is the regularizer constraining certain properties of the epicardial potentials. There are three basic Tikhonov schemes depending on the choice for L. The zero-order Tikhonov (ZOT) takes L as an identity matrix, constraining the amplitude of epicardial potentials. The first-order Tikhonov (FOT) takes L as a gradient operator, constraining the spatial gradient. The second-order Tikhonov (SOT) takes L as a surface Laplacian operator, constraining the curvature of epicardial potentials. B. Operators in a Variational Form 1) Motivation: Our study of variational formulation originated from the quest for a closed-form gradient operator defined over a mesh: given a potential field uH located on some mesh nodes, find a matrix LG such that LG uH gives the magnitude of ∇uH located on the same set of nodes. The gradient operator plays an important role in PDE-constrained optimization as a basis for Newton’s method. For the inverse ECG problem, the gradient operator over a heart surface enables gradient-based regularization methods, which have reported superior results in recovering spatio-temporal characteristics of epicardial data,

(9)

j

where M is the mass matrix over the heart. Similarly, one may evaluate the L2 norm of the potential gradient field by ⎞ ⎛ j ∇˜ uH 2L 2 = ⎝ uiH ∇φi , uH ∇φj ⎠ = uTH SuH (10) i

j

where S is the stiffness matrix over the heart. Detailed definitions of M and S are given in Table I. The Euclidean norm · 2 with an operator L has the property that LuH 22 = uTH LT LuH .

(11)

Hence, if L is to describe the magnitude of the field u ˜H , it should satisfy LT L = M. Such L can be computed as the Cholesky factor of M and inserted into (7) for the ZOT representation, as opposed to the traditional choice of an identity matrix. If L is to describe ∇˜ uH , it should satisfy LT L = S, or equivalently be the Cholesky factor of S. We name such L the “variational-form” gradient operator because it is equivalent to the real gradient operator in the variational principle. L can be used in (7) for the FOT regularization. Table I compares variational-formed operators with traditional operators up to the second order (the surface Laplacian). One may extend this formulation to operators regarding even

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

TABLE I CHOICE OF L FOR TIKHONOV REGULARIZATION

higher-order Sobolev norms, provided that the finite-element formulation maintains stronger differentiability—the variational Laplacian operator requires C 1 continuous finite elements; higher order operators may need C P continuous elements. This paper only considers C 0 elements and accordingly, constraints up to first-order derivatives. The Cholesky decomposition always exists because the mass matrix, the stiffness matrix or matrices formed by higher order derivatives are symmetric and at least positive semidefinite. More discussion of their Cholesky decomposition will be presented in Section VI. C. Norm Preservation One advantage of the variational-form operators over conventional discrete operators is that the former preserves the norms under different resolutions—the continuous L2 norm is independent of the discretization resolution, and the weights made by FEM basis functions take mesh spacing into account. Consequently, the variational operators achieve consistent regularization when the inverse problem is computed under multiple scales. In contrast, conventional regularizers are evaluated by the Euclidean norm, which heavily relies on the discretization resolution and cannot effectively relate the discrete model with its underlying continuous field. Taking the ZOT, for example, with the variational regularizer, changing mesh spacing affects basis functions and then the mass matrix, so the L2 norm of epicardial potentials is preserved. With the conventional identity matrix, however, the regularizer’s Euclidean norm is sensitive to the mesh resolution. D. Imposition of Multiple Variational Regularizers Tikhonov regularization with multiple spatial/temporal constraints [28], [29] is often desirable. Each constraint imposes its own bias on the inverse solution, so combining several constraints may moderate the bias and provide a more comprehensive account of the solution. Inverse solutions are sensitive to the values of regularization parameters, and by distributing regularization to multiple constraints one may improve the robustness of the solution to any individual parameter. The Tikhonov method with multiple constraints is given as uH = argmin KuH − uT 22 + λ2i Li uH 22 . (12) i

Its solution is conceptually expressed as uH = (KT K + T 2 −1 T i λi (Li Li )) K uT . For numerical stability, in practice, the minimization is achieved by solving a linear least-squares

1831

problem of the form

u 2 K T . u − uH = argmin H λL 0 2

(13)

Equation (13) can be solved by standard routines such as the QR factorization, or most efficiently by the bidiagonalization algorithm [30] With multiple constraints, λL is made by concatenating each λi Li . Note that although (13) is in the Euclidean norm, if Li is the variational regularizer,LuH 2 actually gives the value of the continuous L2 norm. To promote additional efficiency, one may construct a compact constraint, denoted as L∗ , that is equivalent to the superposition of all constraints λ2i LTi Li 2 , λ1 = 0. (14) L∗T L∗ = i=1

Equation (13) then just takes L∗ in place of all Li s. Moreover, since only the term LTi Li is needed, one may directly use the mass matrix or the stiffness matrix, without factorizing each Li . The compact operator greatly saves memory when the problem size is large and there are many constraints. It also improves efficiency when all λi s need to be optimized over a large number of admissible values. V. RESULTS A. Simulation Setup We tested our proposed discretization guidelines and the variational-form-based regularization technique using finiteelement simulations of a phantom experiment consisting of a live canine heart suspended in a human torso tank filled with a homogeneous electrolytic medium [31]. This experiment enables simultaneous recording of epicardial and torso potentials in vivo. Both the heart and torso boundaries are triangulated surfaces tessellated from MRI scans. Voltages were measured at mesh nodes. The heart mesh consists of 337 nodes and 670 triangles, and epicardial potentials are recorded at each node over a complete cardiac cycle. The torso surface consists of 771 nodes and 1538 triangles. From the surface meshes, we generated the volume meshes in different ways, in order to identify the impact of discretization on the finite-element solution for the inverse ECG problem. The mesh generation strategies will be given with each test presented later. With each mesh, we conducted a forward simulation to obtain the torso potentials and the transfer matrix K. After adding noise to the torso potentials, we inversely calculated the epicardial potentials, electrograms, and isochrones, and compared these reconstructed heart data with recorded data. Unless otherwise stated, the inverse calculation uses the Tikhonov method given in (7) and solved in (13), whereas the regularization parameter λ was determined by an exhaustive search. While not optimal, the Tikhonov method enables us to consistently isolate the impact of changing the discretization. The numerical conditioning of the discretized inverse problem is evaluated by examining the singular value spectrum of the transfer matrix K and its components N and AV H . Inverse solutions are measured both quantitatively and visually.

1832

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

Fig. 1. Singular values of the transfer matrices resulting from the sphere/torso model. The torso mesh remains unchanged while three sphere meshes are tested. N h denotes the number of nodes of on the surface of each sphere.

Quantitative measures include the relative error (RE) and the correlation-coefficients (CC) between the reconstructed epicarˆ H ) and the measured potentials dial potentials (denoted as u (denoted as uH ). RE and CC are defined as follows: RE =

ˆ uH − uH 2 uH 2

(15)

CC =

ˆM )T (uH − uM ) (ˆ uH − u ˆ uH − u ˆM 2 · uH − uM 2

(16)

ˆH where u ˆM and uM are scalars representing the mean value of u and uH , respectively. Visual assessment of the inverse solutions includes visualizing the reconstructed epicardial potential map and the activation isochrone map. The activation time at each site is determined by the time instant with the most negative temporal derivative of its electrogram (i.e., the minimum du/dt). B. Regularization via Discretization 1) Resolution of the Pursued Inverse Solution: Here, we show how the desired fidelity of an inverse solution affects the ill-conditioning of the inverse problem. We present a multiscale simulation over a model composed of a sphere (approximating the heart) contained in a torso tank. The spherical geometry made it easier for us to set different discretization scales for the heart. With the torso mesh unchanged, we tested three sphere models, each with 134, 236, and 612 nodes on the surface. Fig. 1 shows that the ill-conditioning of the transfer matrix is worsened with the increase of the heart resolution, or equivalently, the fidelity of the inverse solution. Fig. 1 indicates that arbitrary refinement may be inappropriate for inverse problems—a discrete heart model of 612 nodes already has singular values of K below double-digit precision. Considering the extra geometric complexities, the inverse problem with a real heart is even more ill-conditioned than the sphere model considered here. Therefore, we have a good reason to believe that one should cautiously discretize the heart surface based on practical needs rather than perform arbitrary refinement. 2) Discretization of the Torso Volume: Here, we explore the impact of the discretization of the torso volume. Keeping both

Fig. 2. Fixing the boundary discretization and refining the volume conductor. N e denotes the number of elements in each mesh. (A) Singular values of AV H . (B) Singular values of K.

the torso surface and the heart surface unchanged, we set the torso volume mesh in four resolutions. Fig. 2 shows the singular values of the resulting transfer matrix K and its components AV H . Panel A shows that volume refinement significantly improves the “heart-to-volume” projector AV H , because such refinement well represents the high-gradient region around the heart. The improvement of AV H subsequently improves K. The way we interpret the singular value spectra of K in Panel B exemplifies how to evaluate the conditioning of a discrete inverse problem. With a good discretization (37 444 elements), the singular values descend slowly, reflecting the intrinsic illposedness of the underlying continuous problem. In contrast, with a coarse discretization (10 454 elements), the singular values of K abruptly drops to near zero from the position 175 among a total of 337 values, enlarging the proportion of the null space of K. This expansion of the null space represents a supplementary ill-conditioning not stemming from the intrinsic ill-posed nature, but rather caused by insufficient discretization. As discussed in Section III-A, the resolution on the epicardium sets the frequency bandlimit of potentials one seeks to recover, whereas the resolution of the volume conductor determines the bandlimit that is actually solvable. When the former exceeds the latter, the formed transfer matrix K cannot hold the relationship of the two frequency bandlimits, resulting in an artificially introduced null space. This discrepancy should be and can be avoided, so we regard the smoothing of singular values as a sign of improvement in the conditioning of the inverse problem. One may see that refinement from 27 361 elements to 37 444 elements does not noticeably change the singular value spectra of the matrices concerned. This is because the improvement brought by discretization is bounded by the ill-posed nature of the continuum problem. Hence, overrefinement beyond a certain level is not cost effective. To further compare the quality of the numerical systems shown in Figs. 2 and 3 shows their reconstructed epicardial potential maps at several representative time instants in a cardiac cycle. In early activation phase (3 ms after the QRS onset), the refined mesh (Mesh 3) better reconstructs the amplitude than the coarse mesh (Mesh 1). When epicardial potentials exhibit diverse pattern (21 ms), the refined mesh outperforms the coarse

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

1833

Fig. 4. Activation isochrones derived from reconstructed epicardial potentials in Fig. 3. Top row: Anterior view. Bottom row: Posterior view.

Fig. 3. Epicardial potentials calculated from the meshes discussed in Fig. 2, under 30-dB white noise. N e denotes the number of elements each in mesh. To effectively visualize the difference in potential patterns, the view is changed at each instant. Epicardial potentials at 21 ms exhibit the most diverse spatial pattern in the entire cardiac cycle, and hence is the hardest to recover.

mesh in recovering the saddle region in the center of the heart. Also at this instant, the isopotential contours from Meshes 2 and 3 outline the negative minimum point located at the center left of the measured potential map, while the contours from Mesh 1 captures this feature poorly. Fig. 4 presents the activation isochrones derived from the epicardial potentials presented in Fig. 3. It shows that volume refinement improves the recovery of the activation time, particularly eliminating artifacts in the activation map. 3) 3-D Hybrid Mesh Setup: The hybrid mesh was formed by padding layers of prisms around the epicardium (or the surface of any tissue). Prism elements then form a new closed triangular surface (like an enlarged heart), from which we used BioMesh3D [32] to generate tetrahedral mesh for the rest body volume (see Fig. 5 for illustration). The refinement in the normal direction was achieved by making more layers of thinner prisms. 4) Refining the Normal Direction: We explored the impact of the resolution in the normal direction by refining a region of prism layers around the heart while fixing the rest of the volume mesh. We set the “prism zone” to be within 10 mm from the epicardium, and create three hybrid meshes having one, two, and four layers of prisms within the “10-mm prism zone.” The thickness of prisms are 10, 5, and 2.5 mm accordingly. All three

Fig. 5. (a) Cross section of a torso mesh, where the heart is surrounded by two layers of prism elements. (b) Hybrid mesh at the heart-volume interface.

Fig. 6. Refining the resolution normal to the heart by prismatic elements. (a) Singular values of AV H . (b) Singular values of K.

meshes share a coarse tetrahedral mesh in the volume (8106 tetrahedra), which is fixed so as to isolate the effects of refinement in the normal direction. To isolate the effect induced by prisms, we compared the hybrid meshes with a pure tetrahedral mesh in approximate resolution. Fig. 6 presents the singular values of the heart-to-volume projector AV H and the transfer matrix K. Compared to the pure tetrahedral mesh, all three hybrid meshes improve AV H significantly and improve K moderately. Panel B shows that refining the normal direction beyond a certain level may not bring much difference in the resulting numerical system. Fig. 7

1834

Fig. 7. Activation time derived from epicardial potentials calculated from the meshes in Fig. 6. (a) From measured potentials. (b) From the pure tetrahedral mesh. (c) From the hybrid mesh with one layer of 10-mm-thick prisms. (d) From the hybrid mesh with two layers of 5-mm-thick prisms. (e) From the hybrid mesh with four layers of 2.5-mm-thick prisms.

Fig. 8. Epicardial potentials computed from hybrid meshes. (a) Exact value. (b) Pure tetrahedral mesh. (c) Hybrid mesh with one layer of prisms. (d) Hybrid mesh with two layers of prisms. (e) Hybrid mesh with four layers of prisms. rg ra d is the ratio of the computed value to the real value of ∇uH , the norm of the epicardial potential gradient field.

compares the activation map derived from the reconstructed epicardial potentials. Hybrid meshes result in better recovery of activation isochrones. The effect of the normal-direction resolution is more evident when the inverse problem is solved by the gradient-oriented FOT. We implemented the FOT using the variational-formed gradient operator. Fig. 8 shows the recovered epicardial potentials at a representative instant, when the potentials exhibit the most diverse spatial pattern. Refining the normal direction improves RE and CC slightly, but recovers a larger proportion of the potential gradient field on the epicardium, as indicated by rgrad rising from 76% to 91%. rgrad is the ratio of the computed value to the real value of the norm of the gradient field ∇uH . Maintaining sharp gradients is an important goal in inverse calculation because the Tikhonov method tends to oversmooth its inverse solution. Such improvement is achieved in two ways. First, refinement in the normal direction assumes higher gradients to be represented by discretization, thereby improving the transfer matrix. Second, the refinement increases the magnitude of the stiffness matrix, which then enhances the regularizing effect of the variational gradient operator (based on the stiffness matrix). This test exemplifies how discretization choices may achieve regularization effects and affect inverse solutions. 5) Volume Refinement With the Hybrid Mesh: This test was meant to be a comparative study to the volume-refining test presented in Section V-B2. Because the test uses tetrahedral elements only, refining the volume inevitably changes the discretization of the heart-to-volume interface. With the hybrid mesh, we are able to isolate the impact of volume refinement by

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

Fig. 9. Refining the volume while fixing the meshes around the heart by two layer of 5-mm-thick prisms. Meshes 1, 2, and 3 contain 8106, 13 636, and 23 361 tetrahedral elements, respectively. (A) Singular values of N and AV H . (B) Singular values of K.

fixing the prism mesh around the heart while refining the rest of the volume. We set two layers of 5-mm-thick prisms so as to reasonably approximate the gradient field around the heart. The rest of the torso volume was filled with 8106, 13 635, and 23 361 tetrahedral elements, respectively, with the torso surface triangulation unchanged. Fig. 9 presents the resulting AV H , N, and K. It confirms our conjecture that the extension of singular values N and K are attributed to the refinement of interior volume, not the refinement of the heart-volume interface. Note that AV H was intact in this test because the discretization of the heart-volume interface was fixed by prism elements. C. Variational-Form Regularizers 1) Variational Gradient Operator in Regularization: Here, we demonstrate the efficacy of the variational gradient operator given by Table I when used in the FOT regularization. We compare the FOT with conventional ZOT and SOT. The ZOT uses an identity matrix as regularizer. The SOT uses a discrete Laplacian operator obtained by solving a least-squares problem arising from second-order Taylor expansion at each point, proposed by [33]. Fig. 10 compares the epicardial potentials reconstructed by the three methods. Overall, the FOT and SOT perform closely, both outperforming the ZOT. The FOT sometimes outperforms the SOT in capturing local spatial patterns or isopotential contours: e.g., the contours at 10 ms, the saddle point at the heart center at 21 ms, and the isopotential contours at 27 ms. These observations are reasonable, for the Laplacian regularizer tends to smooth contours, whereas the gradient-based regularizer preserves contours better. 2) Norm Preservation in Multiscale Simulation: In multiscale discretization, variational-form operators preserve the norm because they consider the continuous L2 norm which is irrespective of resolution. In contrast, conventional discrete operators consider the Euclidean norm, which depends on the size of discretization. We illustrate this point by comparing the traditional regularizer and the variational one under the ZOT regularization. The traditional regularizer is an identity matrix, whereas the variational-formed regularizer is derived from the mass matrix given by Table I. Each regularizer was tested with two discrete models: a coarse Mesh 1 and a uniformly refined Mesh 2. On the

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

Fig. 10. Epicardial potentials calculated under 30-dB SNR input white noise. ZOT, FOT, and SOT denote the zero-, first-, and second-order Tikhonov regularization. To better show spatial patterns, the view is rotated.

heart surface, Mesh 2 has four times as many nodes as Mesh 1, i.e., the discrete problem yielded by Mesh 2 is four times the size of that from Mesh 1. Fig. 11 compares the L-curves resulting from the multiscale test of each regularizer. Panel A shows the L-curves from the identity matrix, and Panel B shows the L-curves from the mass matrix. In Panel A, refinement pushes the L-curve to the upper right, indicating that refinement increases both the residual error and the constraint (here the solution norm). In contrast, in Panel B, the L-curve is not significantly affected by refinement. Note that Panels A and B have different axis scales. Fig. 11 marks the value of λ associated with the corner of each L-curve, which typically estimates a reasonable amount of regularization one should apply. In Panel B, both the residual error and the solution norm at the corner are preserved during refinement. In Panel A, the residual error and the solution norm at the corner are nearly doubled. Recall that the size of the inverse solution vector is increased by four times from Mesh 1 to Mesh 2, but uH , the Euclidean norm of the solution vector, is only doubled. This indicates that the traditional Tikhonov regularization tends to oversmooth the inverse solution when discretization is refined, causing inconsistent regularization under multiscale simulations. This inconsistency is also manifested in Fig. 12, where we compare the inverse solutions at a time instant when the

1835

Fig. 11. L-curves of the solution norm versus the residual error when ZOT is performed. The inverse problem is discretized in two scales. Mesh 1 has 27 361 tetrahedral elements with 670 triangular elements on the heart surface. Mesh 2 has 60 617 volume elements with 2680 triangles on the heart surface. (a) Regularizer is the identity matrix, with the residual error and the regularizer evaluated by the Euclidean norm. (b) Variational regularizer derived from the mass matrix given by Table I, evaluated by the continuous L 2 norm. λ indicates the regularization parameter corresponding to the corner of L-curves.

epicardial potential pattern is the most diverse. When refining Mesh 1 to Mesh 2, the identity-matrix regularizer yields inconsistent potential patterns, increasing the RE from 0.50 to 0.53. In contrast, the variational-formed regularizer maintains the solution pattern overrefinement, reducing the error from 0.48 to 0.42. VI. DISCUSSION A. Finite-Element Discretization Our primary goal is to explore how the finite-element discretization of the ECG model influences the numerical conditioning of the inverse ECG problem, so as to formulate a, numerical problem optimal for inversion. While there are a large number of research studies targeted at stabilizing the ill-posedness by various regularization techniques, few studies concentrate efforts on improving the numerical quality of inverse problems before their inverse solutions are sought. In fact, proper discretization strategies can be used in combination with regularization methods so as to achieve additional improvement to the inverse solution accuracy.

1836

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

problem; and 2) the time for solving the minimization. The first time is dominant and is linear in the number of elements being used. Hybrid meshes enables us to improve accuracy without dramatically increasing the mesh size and hence the CPU time. The time for minimizing (13) (for each value of λ) is 1–2 s in MATLAB with four 2.66-GHz Intel Xeon cores, given that the size of the linear problem is 771 × 337 (the number of nodes on the torso and heart surfaces, respectively). B. Variational-Form Regularizers

Fig. 12. Epicardial potentials reconstructed under 30-dB SNR input noise by ZOT using the traditional and the variational regularizers, corresponding to the L-curves in Fig. 11. For each inverse solution, RE and CC are given.

To assess the impact of discretization, our methodology includes testing different finite-element discretization strategies and then evaluating their resulting transfer matrix (the inverse problem) by singular value analysis. We then evaluate the inverse solutions in terms of quantitative metrics, epicardial potential patterns, and activation isochrone maps. The inverse solutions are calculated by a fixed regularization method (mostly SOT) in order to isolate the effect of discretization and to minimizing the effect of regularization. Our experiments based on 3-D models obtained consistent results with our previous study in the 2-D case [11]. The results corroborate the inverse-problem discretization guidelines proposed in Section III-B. Fig. 1 indicates that the epicardial resolution for which we seek should be limited based on practical needs lest the discretized inverse problem become overly ill-conditioned. Meanwhile, refining the volume conductor improves the conditioning of the transfer matrix (see Fig. 2), the reconstructed epicardial potentials (see Fig. 3), and activation isochrones (see Fig. 4). The use of hybrid meshes enables one to refine the high gradient field around the heart without incurring aspect-ratio problems. Such refinement improves the accuracy of the heartto-volume projection (see Fig. 6) and the reconstruction of epicardial potential gradients (see Fig. 8), which in turn improves the recovery of the activation isochrone map (see Fig. 7). It is worth comparing the refinement in the normal direction to the heart to previous studies that use the potential gradient or current density (from a physical view) as a constraint in regularizing the inverse ECG problem [26], [27]. The spatial refinement implicitly assumes that a higher gradient is being sought, so it achieves a similar regularizing effect often referred to as “regularization by discretization” [14], [34]. The CPU time of our ECG simulation consists of: 1) the time for building the finite-element model and the minimization

The central idea of the variational-form-based regularization is to measure the potential field by the L2 norm in place of the Euclidean norm. Because the L2 norm is inherently assumed by common FEM (e.g., Galerkin formulation), the variationalformed regularization automatically conforms to certain variational principles underlying the discrete inverse problem formulated by FEM. Defined over a continuous domain, the L2 norm is independent of discretization resolution, thereby ensuring that the discretized problem is handled in conformity to its underlying continuous problem. The Euclidean norm, in contrast, does not reflect the features of the continuous problem. The preservation of norms is important when applied to multiscale simulation of inverse problems, because it ensures regularization be performed consistently among numerical problems of different scales. Here, the consistency means that the balance between the residual error and the regularizing term is maintained. The requirement of consistency is based on the understanding that all discrete problems should reflect the nature of their common continuous origin. The consistency cannot hold when the Euclidean norm is used. When conventional discrete operators are used in the Tikhonov regularization, the residual error and the regularizer may not increase by the same rate under refinement. If the residual error increases faster than the regularizer, more weight will be put on the residual error and the inverse problem tends to be underregularized. Conversely, the inverse problem will be overregularized. In our example of testing ZOT method under multiscale discretization, Fig. 11 shows that the preservation of L2 norm leads to consistent regularization, which consequently leads to consistent reconstruction of epicardial potentials, as shown by Fig. 12. The traditional Euclidean-norm-based regularization does not exhibit the consistency. The introduction of resolution-consistent regularization may pave the way for adaptive FEM to be used for solving inverse problems. Despite its many successes in reducing complexity and enhancing efficiency for solving PDE-based forward problems, adaptive FEM has not yet been widely applied to inverse problems. By taking advantage of their natural consistency within the FEM Galerkin framework, resolution-consistent regularization may solve the issues that arise with nonuniform volumetric resolution. It is straightforward to implement the variational-formed regularization in the L2 norm, by slightly modifying the implementation of traditional Tikhonov methods. The Euclidean norm of the epicardial potentials uH is given by uH 2 = (uTH uH )1/2 , ˜H is given whereas the L2 norm of the continuous distribution u

WANG et al.: FINITE-ELEMENT-BASED DISCRETIZATION AND REGULARIZATION STRATEGIES FOR 3-D INVERSE ELECTROCARDIOGRAPHY

by ˜ uH L 2 = (uTH MuH ), where the mass matrix M is given in Table I. Evaluating the L2 norm is achieved by adding a weighing matrix that is based on finite-element basis functions. The norm of the residual error defined on the torso surface, or the norm of any gradient field, can be obtained in a similar way by modifying the weighing matrix accordingly. The weighing matrix can be precomputed using the mesh information only. The stiffness matrix and matrices formed by higher order derivatives are positive semidefinite because the derivative of any constant field is always zero. The Cholesky decomposition for these matrices is not unique, but we do not believe that this fact will effect the outcome of Tikhonov regularization because the Tikhonov method considers the L2 norm of the regularizers. We selected a Cholesky factorization in a systematic way. Assume, we decompose the stiffness matrix S. We take the sequence Sk = S + k1 I, where I is the identity matrix. Sk → S when k → ∞. Each {Sk } is positive definite and has a unique Cholesky factor Lk . We take L = limk →∞ Lk as the Cholesky factor of S. The convergence of {Lk } holds because the operators are bounded and their underlying vector space is finite dimensional. VII. CONCLUSION We investigated how finite-element discretization can be constructed specifically for the inverse ECG problem so as to optimize its numerical conditioning. Extending our previous 2-D study to 3-D, this paper provides discretization guidelines for practical ECG simulations and their realization via a hybrid mesh scheme. We also proposed a new family of variational regularizers based on the continuous L2 norm. These regularizers are an alternative to the traditional Tikhonov regularization but achieve consistent regularization over multiscale simulation. The variational formulation also enables a simple construction of the discrete gradient operator over an irregular mesh, which is difficult to obtain with traditional discretization techniques. The hybrid mesh scheme and the variational-formed regularization were validated via simulation based on a realistic 3-D torso/heart model with real heart data. Future work includes coupling the maximum fidelity allowed for the heart with other biophysical constraints (such as the distributed current density source within the heart). Evaluating the impact of tissue conductivity on the inverse ECG will also be valuable, while the impact on the forward ECG has been reported [35], [36]. Human tissue conductivities are estimated by electrical impedance tomography, a technique under active research both mathematically [37] and clinically [38]. ACKNOWLEDGMENT

[3]

[4]

[5]

[6] [7] [8] [9] [10] [11] [12]

[13] [14] [15] [16] [17] [18] [19] [20] [21]

[22] [23] [24] [25]

The authors would like to thank Dr. MacLeod for sharing the ECG data. [26]

REFERENCES [1] A. Intini, R. Goldstein, Y. Rudy, P. Jia, and A. Waldo, “Electrocardiographic imaging (ECGI), a novel diagnostic modality used for mapping of focal left ventricular tachycardia in a young athlete,” Heart Rhythm, vol. 2, no. 11, pp. 1250–1252, 2005. [2] P. Jia, C. Ramanathan, Y. Rudy, R. N. Ghanem, K. Ryu, and N. Varma, “Electrocardiographic imaging of cardiac resynchronization therapy in

[27] [28]

1837

heart failure: Observation of variable electrophysiologic responses,” Heart Rhythm, vol. 3, no. 3, pp. 296–310, 2006. S. Ghosh, J. Avari, Y. Rudy, E. K. Rhee, and P. K. Woodard, “Noninvasive electrocardiographic imaging of epicardial activation before and after catheter ablation of the accessory pathway in a patient with ebstein anomaly,” Heart Rhythm, vol. 5, no. 6, pp. 857–860, 2008. S. Ghosh, E. Rhee, Y. Rudy, J. N. Avari, and P. K. Woodard, “Cardiac memory in patients with Wolff-Parkinson-White syndrome: Noninvasive imaging of activation and repolarization before and after catheter ablation,” Circulation, vol. 118, no. 9, pp. 907–915, 2008. R. C. Barr, M. Ramsey, and M. S. Spach, “Relating epicardial to body surface potential distributions by means of transfer coefficients based on geometry measurements,” IEEE Biomed. Eng., vol. BME-24, no. 1, pp. 1– 11, Jan. 1977. R. M. Gulrajani, Bioelectricity and Biomagnetism. New York: Wiley, 1998. I. Babuˇska, T. Strouboulis, C. Upadhyay, S. Gangaraj, and K. Copps, “Validation of a posteriori error estimators by a numerical approach,” Int. J. Numer. Methods Eng., vol. 37, pp. 1073–1123, 1994. D. Weinstein, C. Johnson, and J. Schmidt, “Effects of adaptive refinement on the inverse EEG solution,” SPIE, vol. 2570, pp. 2–11, 1995. C. Johnson and R. S. MacLeod, “Nonuniform spatial mesh adaptation using a posteriori error estimates: Applications to forward and inverse problems,” Appl. Numer. Math., vol. 14, pp. 311–326, 1994. C. Johnson, “Computational and numerical methods for bioelectric field problems,” Crit. Rev. Biomed. Eng., vol. 25, no. 1, pp. 1–81, 1997. D. Wang, R. Kirby, and C. Johnson, “Resolution strategies for the finiteelement-based solution of the ECG inverse problem,” IEEE Trans. Biomed. Eng., vol. 57, no. 2, pp. 220–237, Feb. 2010. P. R. Johnston, S. J. Walker, J. A. K. Hyttinen, and D. Kilpatrick, “Inverse electrocardiographic transformations: Dependence on the number of epicardial regions and body surface data points,” Math. Biosci., vol. 120, pp. 165–187, 1994. V. Isakov, Inverse Problems for Partial Differential Equations, 2nd ed. ed. New York: Springer-Verlag, 2006. H. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems. Norwell, MA: Kluwer, 2000. A. Kirsch, An Introduction to the Mathematical Theory of Inverse Problems. New York: Springer-Verlag, 1996. J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems. New York: Springer-Verlag, 2004. A. Tikhonov and V. Arsenin, Solutions of Ill-Posed Problems. Washington, DC: V. H. Winston & Sons, 1977. F. Natterer, “Error bounds for Tikhonov regularization in Hilbert scales,” Appl. Anal., vol. 18, pp. 29–37, 1984. W. Bangerth and A. Joshi, “Adaptive finite element methods for the solution of inverse problems in optical tomography,” Inverse Problems, vol. 24, no. 3, p. 034011, 2008. Y. Yamashita, “Theoretical studies on the inverse problem in electrocardiography and the uniqueness of the solution,” J-BME, vol. 29, pp. 719–725, 1982. B. Messnarz, M. Seger, R. Modre, G. Fischer, F. Hanser, and B. Tilg, “A comparison of noninvasive reconstruction of epicardial versus transmembrane potentials in consideration of the null space,” IEEE Trans. Biomed. Eng., vol. 51, no. 9, pp. 1609–1618, Sep. 2004. J. Shewchuk, “What is a good linear finite element? interpolation, conditioning, anisotropy, and quality measures,” in Proc. 11th Int. Mesh Roundtable, 2002, p. 70. E. M. Karniakakis and S. P. Sherwin, Spectral/hp Element Methods for CFD. Oxford, U.K.: Oxford Univ. Press, 1999. D. Wang, R. Kirby, and C. Johnson, “Finite element refinements for inverse electrocardiography: Hybrid shaped elements and high-order element truncation,” Comput. Cardiol., vol. 36, pp. 193–196, 2009. R. Throne and L. Olson, “A comparison of spatial regularization with zero and first order Tikhonov regularization for the inverse problem of electrocardiography,” Comput. Cardiol., vol. 27, pp. 493–496, 2000. D. S. Khoury, “Use of current density in regularization of the inverse problem of electrocardiography,” in Proc. 16th Int. Conf. IEEE EMBS, vol. 3–6, Baltimore, MD, 1994, pp. 133–134. S. Ghosh and Y. Rudy, “Application of l1-norm regularization to epicardial potential solution of the inverse electrocardiography problem,” Ann. Biomed. Eng., vol. 37, no. 5, pp. 902–912, 2009. G. F. Ahmad, D. H. Brooks, and R. S. MacLeod, “An admissible solution approach to inverse electrocardiography,” Ann. Biomed. Eng., vol. 26, pp. 278–292, 1998.

1838

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING, VOL. 58, NO. 6, JUNE 2011

[29] D. Brooks, G. Ahmad, and R. MacLeod, “Inverse electrocardiography by simultaneous imposition of multiple constraints,” IEEE Trans. Biomed. Eng., vol. 46, no. 1, pp. 3–18, Jan. 1999. [30] L. Eld´en, “Algorithms for the regularization of ill-conditioned least squares problems,” BIT, vol. 17, pp. 134–145, 1977. [31] R. MacLeod, B. Taccardi, and R. Lux, “Electrocardiographic mapping in a realistic torso tank preparation,” in Proc. 17th IEEE Eng. Med. Bio. Conf., 1995, pp. 245–246. [32] BioMesh3D: Quality Mesh Generator for Biomedical Applications. Scientific Computing and Imaging Institute (SCI), Univ. Utah, Salt Lake City. (2011). [Online]. Available: http://www.biomesh3d.org [33] G. Huiskamp, “Difference formulas for the surface laplacian on a triangulated surface,” J. Comp. Phys., vol. 95, no. 2, pp. 477–496, 1991. [34] H. Engl and A. Neubauer, “Convergence rates for Tikhonov regularization in finite-dimensional subspaces of hilbert scales,” Proc. Amer. Math. Soc, vol. 102, pp. 587–592, 1988. [35] S. Geneser, R. Kirby, and R. MacLeod, “Application of stochastic finite element methods to study the sensitivity of ECG forward modeling to organ conductivity,” IEEE Trans. Biomed. Eng., vol. 55, no. 1, pp. 31–40, Jan. 2008. [36] D. U. J. Keller, F. M. Weber, G. Seemann, and O. D¨ossel, “Ranking the influence of tissue conductivities on forward-calculated ECGs,” IEEE Trans. Biomed. Eng., vol. 57, no. 7, pp. 1568–1576, Jul. 2010. [37] M. Cheney, D. Isaacson, and J. C. Newell, “Electrical impedance tomography,” SIAM Rev., vol. 41, no. 1, pp. 85–101, 1999. [38] T. J. C. Faes, H. A. v. derMeij, J. C. d. Munck, and R. Heethaar, “The electric resistivity of human tissues (100 Hz—10 MHz): A meta-analysis of review studies,” Physio. Meas., vol. 20, pp. 1–10, 1999.

Robert M. Kirby (M’02) received the M.S. degree in applied math, the M.S. degree in computer science, and the Ph.D. degree in applied mathematics from Brown University, Providence, RI, in 1999, 2001, and 2002, respectively. He is currently an Associate Professor of Computer Science at the School of Computing, an Adjunct Associate Professor in the Departments of Bioengineering and of Mathematics, and a member of the Scientific Computing and Imaging Institute, all at the University of Utah, Salt Lake City. His research interests include scientific computing and visualization.

Dafang Wang (S’09) was born in Hangzhou, China, in 1984. He received the B.S. degree in computer science from Zhejiang University, Hangzhou, China, in 2005. He is currently working toward the Ph.D. degree in computer science at the School of Computing, University of Utah, Salt Lake City. He is also a Research Assistant at Scientific Computing and Imaging Institute, University of Utah. His research interests include inverse problems, scientific computing, bioelectricity, and electrocardiography.

students. Dr. Johnson has received several awards, including the NSF Presidential Faculty Fellow (PFF) Award from the President Clinton in 1995 and the Governor’s Medal for Science and Technology from the Governor Michael Leavitt in 1999. He is a Fellow of the American Institute for Medical and Biological Engineering (AIMBE), a Fellow of the American Association for the Advancement of Science (AAAS), and a Fellow of the Society of Industrial and Applied Mathematics (SIAM). He serves on several international journal editorial boards, as well as on advisory boards to several national research centers.

Chris R. Johnson received the Ph.D. degree from the University of Utah, Salt Lake City, in 1989. He directs the Scientific Computing and Imaging (SCI) Institute, University of Utah, where he is currently a Distinguished Professor of Computer Science and holds Faculty appointments in the Departments of Physics and Bioengineering. His research interests are in the areas of scientific computing and scientific visualization. He founded the SCI Research Group in 1992, which has since grown to become the SCI Institute employing over 150 faculty, staff, and

Download "Download Finite-Element-Based Discretization and Regularization Strategies for 3-D Inverse Electrocardiography , Student Member, IEEE"

We are a sharing community. So please help us by uploading **1** new document or like us to download:

OR LIKE TO DOWNLOAD IMMEDIATELY