Journal of Computer and Communications, 2014, 2, 3440 Published Online November 2014 in SciRes. http://www.scirp.org/journal/jcc http://dx.doi.org/10.4236/jcc.2014.213005 How to cite this paper: Dung, L.R., Yang, C.W. and Wu, Y.Y. (2014) 3D EIT Image Reconstruction Using a BlockBased Compressed Sensing Approach. Journal of Computer and Communications, 2, 3440. http://dx.doi.org/10.4236/jcc.2014.213005 3D EIT Image Reconstruction Using a BlockBased Compressed Sensing Approach LanRong Dung1, ChianWei Yang1, YinYi Wu2 1Departmentof Electrical and Computer Engineering, National Chiao Tung University, Hsinchu, Chinese Taipei 2ChungShan Institute of Science Technology, Taoyuan, Chinese Taipei Email: lennon@faculty.nctu.edu.tw Received 16 September 2014 Abstract Electrical impedance tomography (EIT) is a fast and costeffective technique that provides a to mographic conductivity image of a subject from boundary currentvoltage data. This paper pro poses a time and memory efficient method for solving a large scale 3D EIT image reconstruction problem and the illposed linear inverse problem. First, we use blockbased sampling for a large number of measured data from many electrodes. This method will reduce the size of Jacobian ma trix and can improve accuracy of reconstruction by using more electrodes. And then, a sparse ma trix reduction technique is proposed using thresholding to set very small values of the Jacobian matrix to zero. By adjusting the Jacobian matrix into a sparse format, the element with zeros would be eliminated, which results in a saving of memory requirement. Finally, we built up the relationship between compressed sensing and EIT definitely and induce the CS: twostep Iterative Shrinkage/Thresholding and blockbased method into EIT image reconstruction algorithm. The results show that bloc kbased compressed sensing enables the large scale 3D EIT problem to be efficient. For a 72electrodes EIT system, our proposed method could save at least 61% of memory and reduce time by 72% than compressed sensing method only. The improvements will be ob vious by using more electrodes. And this method is not only better at antinoise, but also faster and better resolution. Keywords EIT, Compressed Sensing, Image Reconstruction 1. Introduction Electrical Impedance Tomography (EIT) [1] is an imaging technique which calculates the electrical conductivity distribution within medium using electrical measurements from a series of electrodes on the medium surface. In this paper, threedimensional EIT is taken into consideration. Increasing the number of electrodes will increase the number of independent measurements. This increase will provide more impedance information to the mea surement s . For 3D EIT [2], information required extends to multiple layers; a large number of electrodes could mean better coverage of 3D space. If the number of electrodes increases to 256 electrodes (e.g. 16 planes of 16
L.R. Dung et al. electrodes), the number of independent measurement is as high as 64,768. When the problem of a large number of electrodes and a large number of voxels happens, limitations appearing as large size matrices need to be stored and large matrix inversion is required. This paper proposes a time and memory efficient method for solving a large scale 3D EIT image reconstruc tion problem and the illposed linear inverse problem. We use blockbased sampling [3], threshold limits on Ja cobian matrix [4] and compressed sensing [5] in 3D EIT reconstruction image. We will introduce this method in the following section. In this section, we will present shock filter algorithm in detail. Firstly, the Xray images need to be noisefree images. In order to remove noise of Xray image, we propose an anisotropic diffusion filter, and it’s an adaptive smoothing technique. Secondly, shock filter algorithm is proposed for the Xray image segmentation and en hancement. Finally, a twostage shock filter is proposed to optimize the result of shock processing. 2. BlockBased Compressed Sensing in 3D EIT In this section, we will illustrate the proposed algorithm in detail. Fig ure 1 is the flow chart of blockbased compressed sensing algorithm with the improved three steps: blockbased sampling, sparse Jacobian matrix and reconstruction algorithm using compressed sensing. 2.1. EIT Image Reconstruction Most EIT reconstruction methods consider a linear model of the form: (1) where is the Jacobian or sensitivity matrix and is the measurement noise, which is assumed to be uncorrelated white Gaussian. J is calculated from the FEM as , and depends on the FEM, the current injection patterns, the reference conductivity and the electrode models. This system is underdetermined since . In order to obtain approximation solution; we need to solve the following minimization prob lem, which is classical regularization method , called Tikhonov regularization: (2) where is the regularization parameter and denotes penalty function or regularization function. Figure 1. Flow chart of blocbased compressed sensing algorithm.
L.R. Dung et al. 2.2. BlockBased Sampling EIT image is the image of impedance changes. If the measurement data from the specific electrodes has a large of changes, it represents impedance will have a large of changes near the specific electrodes, vice versa. So we want to sample the measurement data of huge changes by using blockbased sampling. This method will reduce the size of Jacobian matrix and can improve accuracy of reconstruction by using more electrodes. And then, in order to retain image quality, the paper use the size of 1/3 original signal as our measurement data, e.g. Figure 2. Consider a class S of signal vectors , with J and N integers. This signal can be reshaped into a matrix, X and we use both notations interchangeably in the sequel. We will restrict entire columns of to be part of the support of the signal as a group. That is, signals in a blockspa rse model have entire columns as zeros or non zeros. The measure of sparsity for X is its number of nonzero columns. More formally, we make the fol lowing definition (3). { } 1 {[]such that 0 for,1,,,} JN KN n SXxx R x nNK × ==…∈ =∉Ω Ω⊆…Ω= (3) We can extend this formulation to ensembles of J, lengthN signa ls with common support. Denote this signal ensemble by , with . The matrix features the same structure as the matrix X obtained from a blocksparse signal; thus, the matrix can be converted into a blocksparse vector that represents the signal ensemble. And then, we use the algorithm to obtain the best blockbased ap proximation of the signal X as follows: ˆ2,2 2,0 ˆ ˆ arg min.. S KX XXXstXK =−≤ (4) It is easy to show that to obtain the approximation, it suffices toperform columnwise hard thresholding: let be the Kth largest L2norm among the columns of. Then our approximation algorithmis ( ) ,1 , , [] ss s k kkN XK Xxx= =… whe re ( ) ,1 ,, , ,where 0, nn S SSS K k kNknn xx XK Xxxxx ρ ρ ≥ ==…= < (5) for each . Alternatively, a recursive approximation algorithm can be obtained by sorting the columns of X by their L2 norms, and then selecting the columns with largest norms. Figure 2. The measurement data is made up of 3904, and a blockbased measurement data is made up of 1302 for a 64electrod eEIT s yst em.
L.R. Dung et al. Accordingly, the measurement data is reduced so that it is made up of only entries ratherthan the pre vious Mindices. The Jacobian is now determined for each separate sampled measurement i = (d, ) by integrating over finite element from the electrical potential calculated in terms of the measured voltage at electrode multiplied by the potential induced by injected current , i.e., , ,: b bb j dm bdm jdm j V JJ d x φφ Ω ∂ === ∇∇Ω ∂∫ (6) where represents the sampled measurements resulting from injected current . Computing the Jaco bian by E q uation (6) yields a reduced matrix of size × N. 2.3. Sparse Jacobian and Threshold Limits Due to the nature of 3D EIT, the sensitivity of the measurements to conductivity changes far from the relevant electrodes is small. Those values from the sensitivity map would appear to be very small. The zero elements still remain in the matrix which takes up memory and means they are used in the inverse calculation. The sparse ma trix reduction method indicates that values which are very small, typically below a certain threshold, can belo cated and transformed to zeros. These zero elements are then eliminated from the Jacobian matrix. This effect would decrease the total number of nonzero elements of the Jacobian matrix hence reducing the memory sto rage. Figure 3 shows an example of the effect after thresholding. The level of sparsity (LOS) is defined as the number of nonzero elements divided by the total number of elements in the matrix. The new Jacobian after being sparsed is then formed: max( ) max( ) if % 0 if% ij ijh s ij h J JtJ JJt J ≥× =<× ∑ ∑ (7) whe re the threshold is of the average value of a sum of h biggest numbers in each row of the Jacobian ma trix . The Jacobian matrix now contains a large amount of zero values. In order to retain the original image quality, this paper sets the threshold value of 0.5%. And, it can be seen that LOS is at 50% and approximately 50% of total matrix are transformed to zero and can be eliminated. 2.4. Compressed Sensing: TwoStep Iterative Shrinkage/Thresholding Algorithm (TwIST) This paper uses Twostep iterative shrinkage/thresholding algorithm [6] which are used in compressed sensing [7]. TwIST has been proposed to handle a class of convex unconstrained optimization problems for applications whe re the observation operator is illposed or illconditioned. Fortunately, TwIST can actually solve the L0 re gularized LSP which can be expressed as: (8) whe re is the regularization parameter and is the L0norm of the conductivity changes. The TwIST algorithm has the form (9) Figure 3. Histogram of the level of sparsity of Jacobian for a 64electrod eEIT system. Threshold value (% of J_max)
L.R. Dung et al. ( )() 11 1 () t ttt x xxx λ α αβ +− = −+−+Γ (10) for , where is defined as ( )() ( ) T xxJ yJx λλ ψ Γ= + − (11) whe re is the denoising operator. This paper uses hard threshold function as denoising function. To con verge this algorithm, it has the optimal choice of (12) (13) where is the real numbers such that ( )( ) min max 01 TT JJ JJ ξλ λ <≤ ≤= . is the eigenvalue of its argument . 3. Simulation Results This paper simulates 3D EIT models by using EIDORS software [8] and modifies EIDORS to use the proposed algorithm introduced in Section 2. All simulation results are performed on a EIT configuration using adjacent current stimulation and voltage measurements. We set sparse jacobian threshold value of 0.5%. 10 dB SNR white Gaussian noise is added in the measurement data. Figure 4(a) is a 3D EIT model with one circle target. The target is located at (x, y, z) = (0, 0.1, 0.75) and its radius is 0.2. Figure 4(b) is a 3D EIT model with two circle target. Two targets are located at (x, y, z) = (0.5, 0, 0.75) and (−0.5, 0, 0.75). Their radiuses are 0.2. 3.1. Analysis of Memory and Time Figure 5 shows comparison of memory storage and reconstruction time for 4 different methods. We use a 3D EIT model with one circle target at the different number of electrode, and reconstruct them by using 4 different methods. Onestep Gauss Newton and Total variation [9] is conventional EIT reconstruction methods. They need use more memory usage and calculation time than compressed sensing algorithm. Less than 56electrode EIT system, onestep GN is fastest, because there is only the iteration of calculation every computing. For many electrodes, compressed sensing algorithm will meet significant problems regarding storage space and recon struction time. If we use our proposed improved method in large scale 3D EIT, the problems can be solved ef fectively. We can use memory efficiently and reduce a lot of reconstruction time. 3.2. Comparisons The results reconstruct 3D EIT model with one circle target for48electrodesand 64electrodes EIT system, as shown in Figure 4(a). We compare our proposed method with TwIST and use a set of figure of merit to charac terize the image qualities based on GREIT [10]. Table 1 and Table 2 show that the average value of AR, POS and SD is the same at z = 0.55 − 0.95. From the results, 3D EIT image can retain image quality after using blockbased sampling. Table 3 and Table 4 show comparison blockbased TwIST with one step GN. Blockbased TwIST is more robust to noise and the edges of the objects are more clearly defined. These table also show better spatial resolu tion with our propose method. And then, with conventional method the hyper parameter needs to be optimized with respect to noise level while our method doesn’t need such optimization. Table 1. Comparison of blockbased TwIST with original TwIST for 48electrodes EIT system. 48electrodes AR POS (x, y) SD TwIST 467.5308 0.1113, 0.0026 0.1 048 Blockbased TwIST 467.5308 0.1113, 0.0026 0.1048
L.R. Dung et al. (a) (b) Figure 4. Simulate a 3D EIT model with one and two circle target. (a) One circle target; (b) Two circle target. (a) (b) Figure 5. Analysis of memory and time by using 4 d ifferen t reconstruction image algorithms in 3D EIT. (a) M e mory; (b) Ti me. Table 2. Comparison of blockbased TwIST with original TwIST for 64electrodes EIT system. TwIST 379.5438 0.1086, 0.0016 0.4 431 Blockbased TwIST 379.5438 0.1086, 0.0016 0.4431 Table 3. Different reconstruction results with one circus.
L.R. Dung et al. Table 4. Different reconstruction results with two circuses. 4. Conclusion In this paper, we presented a time and memory efficient method for solving a large scale 3D EIT image recon struction problem and the illposed linear inverse problem. For a 72electrode EIT system, our proposed method could save at least 61% of memory and reduce time by 72% than compressed sensing method only. The im provements will be obvious by using more electrodes. And this method is not only better at antinoise, but also faster and better resolution than the conventional method. References [1] Ch eney, M., Isaacson, D. and Newell, J.C. (1999) Electrical Impedance Tomography. SIAM Review, 41, 85101. http://dx.doi.org/10.1137/S0036144598333613 [2] Vauhkonen, P.J., Vauhkonen, M. and Savo lai, T. (1999) Three Dimensional Electrical Impedance Tomography Based on the Complete Electrode Model. IEEE Transactions on Biomedical Engineering, 46, 11501160. http://dx.doi.org/10.1109/10.784147 [3] Baran iuk, R.G. , Cevher, V., Duarte, M.F. and Hegde, C. (2010) ModelBased Compressive Sensing. IEEE Transac tions on Information Theory, 56, 19822001. http://dx.doi.org/10.1109/TIT.2010.2040894 [4] Yang, C.L., Wei , H.Y., Adl e r , A. and Soleimani, M. (2013) Reducing Computational Costs in Large Scale 3D EIT by Using a Sparse Jacobian Matrix with BlockWise CGLS Reco nst ructi on. Physiological Measurement, 34, 645658. http://dx.doi.org/10.1088/09673334/34/6/645 [5] Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 12891306. http://dx.doi.org/10.1109/TIT.2006.871582 [6] Bio ucasDi as, J. and Figueiredo, M. (2007) A New TwIST: TwoStep Iterative Shrinkage/Thresholding Algorithms for Image Restoration. IEEE Transactions on Image Processing, 16, 29923004. http://dx.doi.org/10.1109/TIP.2007.909319 [7] Tehran i, J.N., Jin , C., McE wan, A. and van Schaik, A. (2010 ) A Comparison between Compressed Sensing Algorithms in Electrical Impedance Tomography. IEEE Engineering in Medicine & Biology Society, 2010, 31093112. [8] Ad l e r , A. and Lionheart, W.R. B. (2006) Uses and Abuses of EIDORS: An Extensible Software Base for EIT. Ph ysio logical Measuremen t, 27, S25S42 . http://dx.doi.org/10.1088/09673334/27/5/S03 [9] Borsic, A., Grah am, B.M., Adler, A. and Lionheart, W.R. B. (2010) In Vivo Impedance Imaging with Total Variation Regulari zation . IEEE Transactions on Medical Imaging, 29, 4454. http://dx.doi.org/10.1109/TMI.2009.2022540 [10] Ad l e r , A., Arnold, J.H., Bayford, R., Borsic, A. , Brown, B., Dixon, P., Faes, T.J.C., F rerich s, I., Gagnon, H., Gärber, Y., Grychtol, B., Hahn , G., Lion heart, W.R. B., Malik, A. , P atterson , R.P., Sto c ks, J., Tizzard, A. , Weil er, N. and Wolf, G.K. (2009) GREIT: A Unified Approach to 2D Linear EIT Reconstruction of Lung Images. Physiological Measure ment, 30 , S35 S55. http://dx.doi.org/10.1088/09673334/30/6/S03
