Fast two dimensional to three dimensional registration of fluoroscopy and CT-scans using Octrees on segmentation maps

Previous Article
Impact of vaccine arrival on the optimal control of a newly emerging infectious disease: A theoretical study
MBE Home
This Issue
Next Article
A comparison of computational efficiencies of stochastic algorithms in terms of two infection models

2012, 9(3): 527-537. doi: 10.3934/mbe.2012.9.527

Fast two dimensional to three dimensional registration of fluoroscopy and CT-scans using Octrees on segmentation maps

Luca Bertelli ^1, and Frédéric Gibou ^2,

1.	ECE Department, UCSB, Santa Barbara, CA 93106, United States
2.	Department of Computer Science and Department of Mechanical Engineering, University of California at Santa Barbara, CA 93106-5070

Received April 2011 Revised May 2012 Published July 2012

Abstract
Related Papers

We introduce a computationally efficient approach to the generation of Digital Reconstructed Radiographs (DRRs) needed to perform three dimensional to two dimensional medical image registration and apply this algorithm to virtual surgery. The DRR generation process is the bottleneck of any three dimensional to two dimensional registration system, since its computational complexity scales with the number of voxels in the Computed Tomography Data, which can be of the order of tens to hundreds of millions. Our approach originates from the segmentation of the volumetric data into multiple regions, which allows a compact representation via Octree Data Structures. This, in turn, yields efficient storage and access of the attenuation indexes of the volumetric cells, required in the projection procedure that generates the DRR. A functional based on Mutual Information is then maximized to obtain the alignment of the DRR with the two dimensional X-ray fluoroscopy scans acquired during the operation. Promising experimental results on real data are presented.

Keywords: Digital reconstructed radiography, Octree mesh generation..

Mathematics Subject Classification: Primary: 00A72, 68U10; Secondary: 65N5.

Citation: Luca Bertelli, Frédéric Gibou. Fast two dimensional to three dimensional registration of fluoroscopy and CT-scans using Octrees on segmentation maps. Mathematical Biosciences & Engineering, 2012, 9 (3) : 527-537. doi: 10.3934/mbe.2012.9.527

References:

[1]	L. Bertelli, S. Chandrasekaran, F. Gibou and B. Manjunath, On the length and area regularization for multiphase level set segmentation, International Journal on Computer Vision, 90 (2010), 267-282. doi: 10.1007/s11263-010-0348-4.
[2]	T. F. Chan and L. A. Vese, Active contours without edges, IEEE Transactions on Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291.
[3]	F. Gibou and R. Fedkiw, Fast hybrid k-means level set algorithm for segmentation, Technical report, Stanford, 2002, Also in proceeding of the $4^{th}$ International Conf. on Stat., Math. and Related Fields, Honolulu, 2005.
[4]	M. Levoy and P. Hanrahan, Light field rendering, Computer Graphics SIGGRAPH, 30 (1996), 31-42.
[5]	C. Min, Local level set method in high dimension and codimension, J. Comput. Phys., 200 (2004), 368-382. doi: 10.1016/j.jcp.2004.04.019.
[6]	C. Min and F. Gibou, A second order accurate level set method on non-graded adaptive Cartesian grids, J. Comput. Phys., 225 (2007), 300-321. doi: 10.1016/j.jcp.2006.11.034.
[7]	S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2.
[8]	D. Russakoff, T. Rohlfing and C. R. Maurer, Fast intensity-based 2d-3d image registration of clinical data using light fields, IEEE International Conference on Computer Vision, 1 (2003), 416-422.
[9]	H. Samet, "The Design and Analysis of Spatial Data Structures," Addison-Wesley, New York, 1989.
[10]	H. Samet, "Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS," Addison-Wesley, New York, 1990.
[11]	J. Sethian, A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci. U.S.A., 93 (1996), 1591-1595. doi: 10.1073/pnas.93.4.1591.
[12]	B. Smits, Efficient bounding box intersection, Ray Tracing News, 15 (2002).
[13]	J. Strain, Tree methods for moving interfaces, J. Comput. Phys., 151 (1999), 616-648. doi: 10.1006/jcph.1999.6205.
[14]	J. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. on Automatic Control, 40 (1995), 1528-1538. doi: 10.1109/9.412624.
[15]	L. A. Vese and T. F. Chan, A multiphase level set framework for image segmentation using the mumford and shah model, International Journal of Computer Vision, (2002), 271-293. doi: 10.1023/A:1020874308076.
[16]	A. Williams, S. Barrus, R. K. Morley and P. Shirley, An efficient and robust ray-box intersection algorithm, International Conference on Computer Graphics and Interactive Techniques, 2005.
[17]	L. Zollei, E. Grimson, A. Norbash and W. Wells, 2D-3D rigid registration of x-ray fluoroscopy and ct images using mutual information and sparsely sampled histogram estimators, IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2 (2001), 696-673.

show all references

References:

[1]	L. Bertelli, S. Chandrasekaran, F. Gibou and B. Manjunath, On the length and area regularization for multiphase level set segmentation, International Journal on Computer Vision, 90 (2010), 267-282. doi: 10.1007/s11263-010-0348-4.
[2]	T. F. Chan and L. A. Vese, Active contours without edges, IEEE Transactions on Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291.
[3]	F. Gibou and R. Fedkiw, Fast hybrid k-means level set algorithm for segmentation, Technical report, Stanford, 2002, Also in proceeding of the $4^{th}$ International Conf. on Stat., Math. and Related Fields, Honolulu, 2005.
[4]	M. Levoy and P. Hanrahan, Light field rendering, Computer Graphics SIGGRAPH, 30 (1996), 31-42.
[5]	C. Min, Local level set method in high dimension and codimension, J. Comput. Phys., 200 (2004), 368-382. doi: 10.1016/j.jcp.2004.04.019.
[6]	C. Min and F. Gibou, A second order accurate level set method on non-graded adaptive Cartesian grids, J. Comput. Phys., 225 (2007), 300-321. doi: 10.1016/j.jcp.2006.11.034.
[7]	S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2.
[8]	D. Russakoff, T. Rohlfing and C. R. Maurer, Fast intensity-based 2d-3d image registration of clinical data using light fields, IEEE International Conference on Computer Vision, 1 (2003), 416-422.
[9]	H. Samet, "The Design and Analysis of Spatial Data Structures," Addison-Wesley, New York, 1989.
[10]	H. Samet, "Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS," Addison-Wesley, New York, 1990.
[11]	J. Sethian, A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci. U.S.A., 93 (1996), 1591-1595. doi: 10.1073/pnas.93.4.1591.
[12]	B. Smits, Efficient bounding box intersection, Ray Tracing News, 15 (2002).
[13]	J. Strain, Tree methods for moving interfaces, J. Comput. Phys., 151 (1999), 616-648. doi: 10.1006/jcph.1999.6205.
[14]	J. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. on Automatic Control, 40 (1995), 1528-1538. doi: 10.1109/9.412624.
[15]	L. A. Vese and T. F. Chan, A multiphase level set framework for image segmentation using the mumford and shah model, International Journal of Computer Vision, (2002), 271-293. doi: 10.1023/A:1020874308076.
[16]	A. Williams, S. Barrus, R. K. Morley and P. Shirley, An efficient and robust ray-box intersection algorithm, International Conference on Computer Graphics and Interactive Techniques, 2005.
[17]	L. Zollei, E. Grimson, A. Norbash and W. Wells, 2D-3D rigid registration of x-ray fluoroscopy and ct images using mutual information and sparsely sampled histogram estimators, IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2 (2001), 696-673.

[1]	Ismet Cinar, Ozgur Ege, Ismet Karaca. The digital smash product. Electronic Research Archive, 2020, 28 (1) : 459-469. doi: 10.3934/era.2020026
[2]	Xiaoxue Gong, Ying Xu, Vinay Mahadeo, Tulin Kaman, Johan Larsson, James Glimm. Mesh convergence for turbulent combustion. Discrete and Continuous Dynamical Systems, 2016, 36 (8) : 4383-4402. doi: 10.3934/dcds.2016.36.4383
[3]	Vincent Ducrot, Pascal Frey, Alexandra Claisse. Levelsets and anisotropic mesh adaptation. Discrete and Continuous Dynamical Systems, 2009, 23 (1&2) : 165-183. doi: 10.3934/dcds.2009.23.165
[4]	Birol Yüceoǧlu, ş. ilker Birbil, özgür Gürbüz. Dispersion with connectivity in wireless mesh networks. Journal of Industrial and Management Optimization, 2018, 14 (2) : 759-784. doi: 10.3934/jimo.2017074
[5]	Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems and Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010
[6]	Lizhong Peng, Shujun Dang, Bojin Zhuang. Localization operator and digital communication capacity of channel. Communications on Pure and Applied Analysis, 2007, 6 (3) : 819-827. doi: 10.3934/cpaa.2007.6.819
[7]	Rongjie Lai, Jiang Liang, Hong-Kai Zhao. A local mesh method for solving PDEs on point clouds. Inverse Problems and Imaging, 2013, 7 (3) : 737-755. doi: 10.3934/ipi.2013.7.737
[8]	Nahid Banihashemi, C. Yalçın Kaya. Inexact restoration and adaptive mesh refinement for optimal control. Journal of Industrial and Management Optimization, 2014, 10 (2) : 521-542. doi: 10.3934/jimo.2014.10.521
[9]	Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete and Continuous Dynamical Systems, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1
[10]	Michael Baur, Marco Gaertler, Robert Görke, Marcus Krug, Dorothea Wagner. Augmenting $k$-core generation with preferential attachment. Networks and Heterogeneous Media, 2008, 3 (2) : 277-294. doi: 10.3934/nhm.2008.3.277
[11]	Johannes Giannoulis. Transport and generation of macroscopically modulated waves in diatomic chains. Conference Publications, 2011, 2011 (Special) : 485-494. doi: 10.3934/proc.2011.2011.485
[12]	Hiroyuki Torikai. Basic spike-train properties of a digital spiking neuron. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 183-198. doi: 10.3934/dcdsb.2008.9.183
[13]	Yi Zhang, Xiao-Li Ma. Research on image digital watermarking optimization algorithm under virtual reality technology. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1427-1440. doi: 10.3934/dcdss.2019098
[14]	Ahmad Jazlan, Umair Zulfiqar, Victor Sreeram, Deepak Kumar, Roberto Togneri, Hasan Firdaus Mohd Zaki. Frequency interval model reduction of complex fir digital filters. Numerical Algebra, Control and Optimization, 2019, 9 (3) : 319-326. doi: 10.3934/naco.2019021
[15]	Hiroaki Uchida, Yuya Oishi, Toshimichi Saito. A simple digital spiking neural network: Synchronization and spike-train approximation. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1479-1494. doi: 10.3934/dcdss.2020374
[16]	Yan-Xin Chai, Steven Ji-Fan Ren, Jian-Qiang Zhang. Managing piracy: Dual-channel strategy for digital contents. Journal of Industrial and Management Optimization, 2022, 18 (4) : 3001-3027. doi: 10.3934/jimo.2021100
[17]	Anita Mayo. Accurate two and three dimensional interpolation for particle mesh calculations. Discrete and Continuous Dynamical Systems - B, 2012, 17 (4) : 1205-1228. doi: 10.3934/dcdsb.2012.17.1205
[18]	Vyacheslav K. Isaev, Vyacheslav V. Zolotukhin. Introduction to the theory of splines with an optimal mesh. Linear Chebyshev splines and applications. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 471-489. doi: 10.3934/naco.2013.3.471
[19]	Zheng-Ru Zhang, Tao Tang. An adaptive mesh redistribution algorithm for convection-dominated problems. Communications on Pure and Applied Analysis, 2002, 1 (3) : 341-357. doi: 10.3934/cpaa.2002.1.341
[20]	Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553

2018 Impact Factor: 1.313

Tools

Metrics

Other articles
by authors

on AIMS
Luca Bertelli Frédéric Gibou
on Google Scholar
Luca Bertelli Frédéric Gibou

[Back to Top]