Time-of-Flight Surface De-noising through Spectral Decomposition

Abstract

An increasingly popular approach to the acquisition of intraoperative data is the novel Time-of-Flight (ToF) camera technique, which provides surface information with high update rates. This information can be used for intra-operative registration with pre-operative data through surface matching techniques. However, ToF data is subject to different systematic errors and noise, which must be eliminated for the purposes of matching with high-quality pre-operative data. While methods for de-noising of data concentrate on the processing of the range images, we focus directly on the surfaces. We decompose the frequency spectrum of the surface and use it for the computation of a low-pass filter, thus eliminating all the higher frequencies on the surface (noise). The low-pass filter was evaluated on in vitro data and was compared to a previously published method for ToF de-noising, which takes advantage of the fast data acquisition provided by the ToF technology. In almost all cases, the low-pass filter showed a better performance. Decomposition of the frequency spectrum of surfaces allows not only filtering and de-noising, but also the application of other valuable signal processing methods, such as enhancement or homogenization.

-

One of the main challenges for image guided therapy systems is the registration of pre-operative planning data with the intra-operative situation of the patient. In this context, surface-based methods have gained increasing attention. One approach to this registration is surface matching considering similarities between intrinsic surface properties, such as curvatures, as presented by dos Santos et al. [ 1 ]. An increasingly popular approach to surface acquisition is the novel Timeof-Flight (ToF) camera technique, which provides range images in addition to gray-scale intensity images with high update rates [ 2 ]. Due to its measurement principle, however, the images acquired by ToF cameras are still subject to different systematic errors and noise [ 3 ]. In order to allow the application of the ToF camera for intra-operative surface acquisition and registration, there is a need for de-noising the acquired range data.

Recent methods focused on performing the de-noising in the image domain. Huhle et al. [ 4 ] presented a method based on the non-local means filter for de-noising ToF range data. They, however, did not apply their algorithms to ToF data acquired in a clinical setting. Seitel et al. [ 5, 6 ] performed the first in vitro evaluation with ToF images taken from different explanted organs and showed the de-noising performance of the bilateral filter. However, they did not concentrate on generating optimal surfaces for the purpose of surface matching. Furthermore, their method requires multiple sequential ToF images for an optimal performance.

So far, and to the best of our knowledge, the direct de-noising by surface analysis techniques has not been employed for the enhancement of ToF data. Based on the work of Vallet and L´evy [ 7 ], we decompose the frequency spectrum of the ToF surface, and use this decomposition for the implementation of a lowpass filter, eliminating the higher frequencies above the surface. The low-pass filter was evaluated in vitro and compared to the method presented by Seitel et al. [ 5, 6 ]. 2

Methods

In this section, we show how to decompose a surface into different frequency bands (Sec. 2.1) and how to use this decomposition for the implementation of a low-pass filter (Sec. 2.2). 2.1

Spectral decomposition of surfaces It was shown by Taubin [ 8 ] that the eigenvectors of the surface Laplacian matrix are very similar to the basis functions used in the discrete Fourier transform. Vallet and L´evy [ 7 ] used these eigenvectors to decompose the surfaces into different spectral bands. We define a surface as S = fV, Eg, where V is a set of vertices and E V V is a set of edges. The Laplacian matrix ∆ij of the surface S is computed (1) (2) (3) ∆ij = { cot +cot

pjvi jjvj j 0 ∆ii = (vi, vj ) 2 E otherwise ∑ vj2N(vi) ∆ij where vi, vj 2 V , α and β denote the angles opposite to the edge (vi, vj ), jvi j denote the support volume of the vertex vi [ 9 ], and N (vi) denotes the 1neighborhood ring of vertex vi. The set of eigenvectors H¯ of the matrix ∆ij are used for the computation of the vector set H representing the different frequency bands on the surface S

hik = jvi jh¯ik where h¯k 2 H¯ and hk 2 H. The vectors in H can be ordered from lower to higher frequencies by the corresponding eigenvalues of h¯k. where hk 2 H.

The inverse transform back in the Euclidean domain is obtained pk = ∑

k vijvi jhi vi2V vi = m ∑ pkhi

k k=1

Low-pass ltering applied on surfaces Having the ordered set of eigenvectors H of the Laplacian matrix of a surface S, a low-pass filter can be obtained by first converting the geometry to the frequency domain [ 7 ] and converting it back to the Euclidean domain using the lowest frequencies only. The points pi in the frequency domain are obtained where m denotes the amount of frequencies used to recompute the vertice’s position, i.e., the frequency threshold of the filter. After the back-transformation to the Euclidean space, all frequencies higher than m are not present above the surface anymore. 3

Evaluation and Results

In our evaluation, we applied the low-pass filter to ToF surfaces acquired in vitro and compared the results to the ones obtained with a previously published filter for ToF de-noising [ 5, 6 ]. While the latter requires multiple sequential ToF range images for an optimal computation, our low-pass filter requires a single surface. In Fig. 1, the results after applying the low-pass filter to a ToF surface representing a liver are shown. As can be seen, increasing the frequency threshold of the filter, more details (represented by higher frequencies) are preserved.

In Table 1, the results of the comparison between the low-pass filter and the adaptive bilateral filtering presented by Seitel et al. [ 5, 6 ] are shown. For this comparison, both ToF surfaces and high resolution ground truth CT surfaces were acquired. After de-noising, the distances between the ToF surfaces were measured to the CT surface. The distances were measured according to the method presented in [ 5, 6 ]. The low-pass filter was applied using frequency threshold m = 100 in all cases. In almost all cases, the low-pass filter performed better. Furthermore, the low-pass filter is able to strongly reduce the maximal errors, where the bilateral filter is not much effective. 4

Discussion

We presented a method for de-noising of Time-of-Flight surfaces, based on the decomposition of the frequency spectrum of the surface and application of a low-pass filter, thus eliminating the higher frequencies (noise). Additionally, (4) (5)

Mean

Std. dev. RMS Min Max

Liver

Low-pass

2.41 1.69 2.94 0.00 7.71

Bilateral

2.47 1.82 3.07 0.00 17.85

Kidney

Low-pass

4.96 5.82 7.65 0.00 46.68

Bilateral

4.81 7.63 9.00 0.00 131.85

Lung

Low-pass

2.08 1.51 2.57 0.00 8.07

Bilateral 2.32 1.82 2.96 0.00 30.65 our method was evaluated and compared to a previously published method for de-noising of ToF data. The results are very encouraging, showing a better performance of the low-pass filter in almost all cases, when compared to a adaptive bilateral filter. Also important to notice the reduction of the maximal errors ToF m = 20 m = 60 m = 120 m = 200 m = 400 obtained by the low-pass filter, which are considerably smaller than the values obtained with the bilateral filter.

Spectral decomposition of surfaces is a very promising technique. It allows not only the construction of filters, but permits also the application of the signal processing theory to surfaces. Examples are feature enhancement and mesh homogenization. In this context, spectral decomposition should be further investigated for processing of intra-operative data.

Acknowledgement. The work of Thiago R. dos Santos is financed by the CAPES/DAAD (Brazil-Germany) scholarship program, under process number 2775/07-7 of the CAPES foundation.

References

1. dos Santos TR , Seitel A , Meinzer HP , et al. Correspondences search for surfacebased intra-operative registration . In: Proc MICCAI; 2010 . p. 660 - 7 .

2. Kolb A , Barth E , Koch R , et al. Time-of-flight sensors in computer graphics . Eurographics State Art Rep . 2009 ; p. 119 - 34 .

3. Frank M , Plaue M , Rapp H , et al. Theoretical and experimental error analysis of continuous-wave time-of-flight range cameras . Opt Eng . 2009 ; 48 ( 1 ): 013602 - 01 -16.

4. Huhle B , Schairer T , Jenke P , et al. Robust non-local denoising of colored depth data . In: Proc IEEE CVPR ; 2008 . p. 1 - 7 .

5. Seitel A , dos Santos TR , Mersmann S , et al. Time-of-Flight Kameras fu¨r die intraoperative Oberfla¨chenerfassung . In: Proc BVM ; 2010 . p. 11 - 5 .

6. Seitel A , dos Santos TR , Mersmann S , et al. Adaptive bilateral filter for image denoising and its application to in-vitro time-of-flight data . In: Proc SPIE; 2011 . p. in press.

7. Vallet B , L´evy B. Spectral geometry processing with manifold harmonics . In: Proc Eurographics; 2008 . p. 251 - 60 .

8. Taubin G. A signal processing approach to fair surface design . In: Proc ACM CGIT ; 1995 . p. 351 - 8 .

9. Arnold DN , Falk RS , R W. Finite element exterior calculus, homological techniques, and applications . Acta Numerica . 2006 ; 15 .