American Institute of Mathematical Sciences

Advanced
  • 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

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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[4]

M. Levoy and P. Hanrahan, Light field rendering, Computer Graphics SIGGRAPH, 30 (1996), 31-42. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[9]

H. Samet, "The Design and Analysis of Spatial Data Structures," Addison-Wesley, New York, 1989. Google Scholar

[10]

H. Samet, "Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS," Addison-Wesley, New York, 1990. Google Scholar

[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.  Google Scholar

[12]

B. Smits, Efficient bounding box intersection, Ray Tracing News, 15 (2002). Google Scholar

[13]

J. Strain, Tree methods for moving interfaces, J. Comput. Phys., 151 (1999), 616-648. doi: 10.1006/jcph.1999.6205.  Google Scholar

[14]

J. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. on Automatic Control, 40 (1995), 1528-1538. doi: 10.1109/9.412624.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[4]

M. Levoy and P. Hanrahan, Light field rendering, Computer Graphics SIGGRAPH, 30 (1996), 31-42. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[9]

H. Samet, "The Design and Analysis of Spatial Data Structures," Addison-Wesley, New York, 1989. Google Scholar

[10]

H. Samet, "Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS," Addison-Wesley, New York, 1990. Google Scholar

[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.  Google Scholar

[12]

B. Smits, Efficient bounding box intersection, Ray Tracing News, 15 (2002). Google Scholar

[13]

J. Strain, Tree methods for moving interfaces, J. Comput. Phys., 151 (1999), 616-648. doi: 10.1006/jcph.1999.6205.  Google Scholar

[14]

J. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. on Automatic Control, 40 (1995), 1528-1538. doi: 10.1109/9.412624.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2021  doi: 10.3934/jimo.2021100
[17]

Anita Mayo. Accurate two and three dimensional interpolation for particle mesh calculations. Discrete & 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 & 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 & 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 & Continuous Dynamical Systems, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553

2018 Impact Factor: 1.313

Tools

Metrics

  • PDF downloads (41)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences