臺灣博碩士論文加值系統

在本論文中，我們舉出手術模擬的重要性，也調查了手術模擬相關的技巧，了解了因為容積可以解析到解剖結構內部資訊，所以準確度較表面模型為高。然後我們調查了容積模型學及操作容積實體、表面的方法，探討了這些方法於手術模擬的不足。
所以我們提出一個新的容積資料結構，及新的在容積內描述表面的演算法。也提出了改進操作容積實體的效率的演算法。而利用這些演算法及資料結構，我們開發了可以模擬操作容積化實體的功能，特別是應用在模擬骨骼肌肉手術。這些功能包括碰撞偵測、實體間的布林運算、切割一個解剖骨塊(即容積中的實體)、以及辨識，移動骨塊和癒合兩個骨塊等。
這篇論文以數個手術模擬測試以上提到的功能。首先是一個下顎骨突出矯正手術：這個實例中顯示了，複雜的幾何和拓樸的改變可以藉由以上提到的功能，得到良好的模擬。在第二個例子中，這些功能結合一個利用三唯幾何限制的分析與評估方法，用以決定選擇最佳的商業上人工膝關節的尺寸和最佳的植入位置。這個分析與評估方法所獲致的結果，被用來當作人工膝關節置換術的模擬手術的重要依據。第三個例子是結合診斷椎間盤突出病例的方法，這個方法利用了中心式貝氏曲線的特性來近似斷層片中的椎間盤邊界。我們求出椎間盤邊界的中心，並以相鄰像素半徑的變化率得出特徵點，再以特徵點的所在位置，決定出椎間盤突出的等級和算出突出物的體積。這個椎間盤突出的診斷方法，可以有效的偵測出可能的突出位置與大小，提供後續手術模擬中，所需的切割位置與辨識的資訊。
第一個實驗結果顯示，我們所提出的資料結構演算法和模擬的功能，完全符合骨骼肌肉手術模擬系統的需求。第二及第三個實驗結果顯示，基於容積操作的模擬方法可以藉由相關演算法的輔助，進一步擴充到診斷、驗證以及提供可能的處置對策。

In this thesis, we reveal the importance of surgical simulation, survey the related simulation techniques and realize that volume model is more accurate than others as it can resolve the inner information of anatomic structure. Then, we survey varied volume models with extended data structures and methodologies for manipulating solids, surfaces and find out the insufficiencies of them.
We propose a new volume data structure and algorithms for surface representation in a volume, also promote the algorithms that can efficiently manipulate volumetric solids. With these algorithms and data structure, we develop some simulation functions to manipulate volumetric solids and especially simulate musculoskeletal surgery, including collision detection and Boolean operations between solids, tear an anatomic structure (a solid), recognize, reposition the structure and fuse two separate structure, etc.
This study testifies the functions with several surgical examples. First, a corrective osteotomy for correcting a maxilla extrusion is demonstrated. This example shows a complex musculoskeletal surgery with complicated topologic and geometric changes can be well simulated by our functions. In the second example, the functions combine with an algorithm of evaluating and analyzing 3D geometric constraints for determining commercial knee prosthesis. The evaluation and analysis results are used as parameters for simulating the knee arthroplasty. In the last example, functions combining HIVD (Herniated Inter-Vertebral Disc) detection method is demonstrated. This method accommodates the radial B-spline to approximate the spline curve composed by disc boundary on slice. We calculate the center of inter-vertebral disc, determine the concave and convex features on the disc based on the change rate of radii and determine the HIVD degree based on the feature characteristics. This method provides effective information for the followed-up HIVD surgical simulation.
The first experimental result shows that proposed data structure, algorithms and simulation functions completely fulfill the requirements of simulating the musculoskeletal surgery. The second and last experimental results show the simulation method based on volumetric manipulation can be extended to a diagnosis, verification and treatment tool by combining the related algorithms.

Abstract
Acknowledgement
List of Figures
List of Tables
Chapter 1 Introduction
1.1 Background
1.2 Organization of thesis
Chapter 2 Literature Review
2.1 Computer-aided surgery simulation
2.2 Volume modeling algorithms
2.3 Voxelization algorithms
2.4 Drawbacks of existed approaches on volume modeling and surface voxelization
Chapter 3 Surface Voxelization
3.1 Basics of surface in volume model
3.2 Data structure for representing volumetric surface
3.3 Surface voxelization algorithms
3.3.1 Calculation of sample points and distance-level replacement
3.3.2 Treatment of voxels sharing the face of incremented point
3.3.3 Seed-curve update
3.3.4 Boundary generation and discontinuity-counter
Chapter 4 Manipulation of Volumetric Solids
4.1 Seed and fill algorithm
4.2 A modified algorithm with 2 ½ D linked lists
4.2.1 Problems of original algorithm: redundant seeds and searches
4.2.2 Possible solutions for preventing redundant seeds and searches
4.2.3 2 1/2 D linked lists reducing repeated searches on seeds and recounting fills
4.2.4 Experiments for proposed modification
4.3 Manipulation of volumetric solids
4.3.1 Topology-changed operations
4.3.2 Non topology-changed operations
4.3.3 Boolean operations
Chapter 5 Applications of Musculoskeletal Surgeries
5.1 Osteotomy correcting maxilla extrusion
5.2 Knee arthroplasty
5.2.1 Three-dimensional geometric constraint evaluation and analysis for determining commercial knee prosthesis
5.2.2 Knee arthroplasty
5.3 Diagnosis of herniated inter-vertebral disc based on image analysis of transverse sections
5.3.1 Theory study
5.3.2 Approximated B-spline for disc boundary
5.3.3 2D herniation feature recognition for classification of HIVD
5.3.4 3D herniation geometry inference from 2D features on transverse sections
5.3.5 Implementation example
Chapter 6 Conclusions and Discussions
6.1 Conclusions
6.2 Discussion
References
List of Published Papers

1.Albert, T.A. and Slaaf, D.W., 1995, “A Rapid Regional Filling Technique for Complex Binary Images”, Computer & Graphics, Vol.9 no.4, pp.541-549.
2.Anne, G.O., 1994, Diagnostic Neuroradiology. Mosby, pp. 836-872.
3.Anouchi, Y.S., Whiteside, L.A., Kaiser, A.D. and Milliano, M.T., 1993, “The Effects of Axial Rotational Alignment of the Femoral Component on Knee Stability and Patellar Tracking in Total Knee Arthroplasty Demonstrated on Autopsy Specimens”, Clin. Orthop., Vol.287, pp.170-177.
4.Berger, R.A., Rubash, H.E. and Seel, M.J., 1993, “Determining the Rotational Alignment of the Femoral Component in Total Knee Arthroplasty Using the Epicondylar, Axis”, Clin. Orthop., Vol.173, pp.40-47.
5.Baumrind, S., Moffit, F. and Curry, S., 1983, “The Geometry of Three-Dimensional Measurement from Paired Coplanar X-Ray Images”, Am. J. Orthod., Vol.84, pp.313-326.
6.Bro-Nielsen, M., Helfrick, B., Zeng, X. and Connacher, H., 1998, “VR Simulation of Abdominal Trauma Surgery”, Medicine Meets Virtual Reality VI.
7.Burger, P. and Gillies, D., 1989, “Interactive Computer Graphics, Cubic B-spline”, Addison Wesley company, New York, pp.250-264.
8.Cates, H.E., Ritter, M.A., Keating, E.M. and Faris, P.M., 1993, “Intramedullary Versus Extramedullary Femoral Alignment Systems in Total KneeReplacement”, Clin. Orthop., Vol.286, pp.32-39.
9.Chuang, S.H.F. and Kuo, C.Z., 1999, “One-Sided Arc Approximation of B-spline Curves for Interference-Free Offsetting”, Computer-Aided Design, Vol. 31 no.2 pp.111-118.
10.Cohen, D. and Kaufman, A., 1997, “3D Line Voxelization and Connectivity Control”, IEEE Computer Graphics and Applications, Vol.17 no.6, pp.80-87.
11.Delibasis, K.S., Matsopoulos, G.K. and Mouravliansky, N.A. and Nikita, K.S., 2001, “A Novel and Efficient Implementation of the Marching Cubes Algorithm”, Computerized Medical Imaging and Graphics, Vol.25 no.4, pp.343-352.
12.Feng, L. and Soon, S.H., 1998, “An Effective 3D Seed Fill Algorithm”, Computer & Graphics, Vol.22 no.5, pp.641-644.
13.Finkelstein, J.A., Gross, A.E. and Davis, A., 1996, “Varus Osteotomy of the Distal Part of the Femur: A Survivorship Analysis”, J. Bone Joint Surg. Am. Vol.78A, pp.1348-1352.
14.Fishkin, K.P. and Barsky, B.A., 1985, “An Analysis and Algorithm for Filling Propagation”, Graphics Interface Proceedings, pp.203-212.
15.Fu, M.W., Fuh, J.Y.H. and Nee, A.Y.C., 1999, “Undercut Feature Recognition in an Injection Module Design System”, Computer-Aided Design, Vol.31 no.12, pp.777-790.
16.Garfin, S.R. and Vaccaro, A.R., 1997, “Orthopaedic Knowledge Update: In: S.R. Garfin, A.R. Vaccaro (Eds.)”, Spine. Rosemont, American Academy of Orthopaedic Surgeons, pp.5-61.
17.Gelder, A.V. and Wilhelms, J., 1994, “Topological Consideration in Isosurface Generation”, ACM Transaction on Graphics, Vol.13 no.4, pp.337-375.
18.Gibson, S. F. F., 1999, “Using Linked Volumes to Model Object Collision, Deformation, Cutting, Carving, and Joining”, IEEE Transaction on Visualization and Computer Graphics, Vol.5 no.4, pp.333-348.
19.Gibson, S. F. F., 1998, “Using Distance Maps for Accurate Surface Representation in Sampled Volumes”, IEEE Volume Visualization’ 98, pp.23-30.
20.González, E., Suárez, A., Moreno, C. and Artigue, F., 1996, “Complementary Regions: a Surface Filling Algorithm”, IEEE international Conference on Robotics and Automation, pp.909-914.
21.Grevera, G.J., Udupa, J.K. and Odhner, D., 2000, “An Order of Magnitude Faster Isosurface Rendering in Software on a PC than Using Dedicated, General Purpose Rendering Hardware”, IEEE Transaction on Visualization and Computer Graphics, Vol.6 no.4, pp.335-344.
22.Gunnar, B.J.A., Gregory, P.G., James, D.K. and Ira, M.P.IV., 1998, “Lumbar Degenerative Disorders. In: James D.H. Orthopaedic Knowledge Update 6”, American Academy of Orthopaedic Surgeons, pp.685-763.
23.Hall, J.E., 1981, “Dwyer Instrumentation in Anterior Fusion of the Spine”, J. Bone Joint Surg., Am. Vol.63A, pp.1188-1190.
24.Haynor, D.R., Larson, E.B. and Deyo, R.A., 1992, “Diagnosis of Lumbar Spinal Stenosis in Adults: A Metaanalysis of the Accuracy of CT, MR and Myelography”, American Journal of Roentgenology, Vol. 158 no.5, pp.1135-1144.
25.He, T. and Kaufman, A., 1997, “Collision Detection for Volumetric Objects”, IEEE Visualization’ 97, pp.159-166.
26.Hsu, H.P., Garg, A., Walker, P.S., Spector, M. and Ewald, F.C., 1989, “Effect of Knee Component Alignment on Tibial Load Distribution with Clinical Correlation”, Clinical Orthopaedics & Related Research, Vol.248, pp.135-144.
27.Hsu, P.L. and Yang, W.T., 1993, “Real-time 3D Simulation of 3-axis Milling Using Isometric Projection”, Computer Aided Design, Vol.25 no. 4, pp.215-224.
28.Huang, J., Yagel, R., Filippov, V. and Kurzion, Y., 1998, “An Accurate Method for Voxelizing Polygon Meshes”, IEEE Volume Visualization’ 98, pp.119-126.
29.Hunt, W.A. and Voelcker, H.B., 1982, “An Exploratory Study of Automatic Verification of Programs for Numerically Controlled Machine Tools”, Production Automation Project Tech. Memo., no.34, University of Rochester.
30.Hunter, I.W., Jones, L.A., Sagar, M.A., Lafontaine, S.R. and Hunter P.J., 1995, “Ophthalmic Microsurgical Robot and Associated Virtual Environment”, Computer in Biology and Medicine, Vol.25 no.2, pp.173-182.
31.James, L.G., 1998, Arthoplasty of Ankle and Knee. Canale S.T., Campbell’s Operative Orthopaedics, 9th ed., Vol.1, pp.232-290.
32.Jaureguito, J.W., Dubois, C.M., Smith, S.R., Gottlieb, L.J. and Finn, J.A., 1997, “Medial gastrocnemius Transposition Flap for the Treatment of Disruption of the Extensor Mechanism After TKR”, J. Bone Joint Surg., Vol. 79, pp.866-873.
33.Kaufman, A. and Shimony, E., 1986, “3D Scan-Conversion Algorithms for Voxel-Based Graphics”, Interactive 3D Graphics, pp.45-75.
34.Laura, C. and Anna, M. F., 1993, “Computer-Aided Simulation for Bone Surgery”, IEEE Computer Graphics and Applications, Vol.13 no.6 pp.86-92.
35.Kobbelt, L., Botsch, M., Schwanecke, U. and Seidel, H.-P., 2001, “Feature Sensitive Surface Extraction from Volume Data”, ACM Siggraph, LA.
36.Lemaire, P., Pioletti, D.P., Meyer, F.-M., Meuli, R., Dörfl, J. and Leyvraz, P.F., 1997, “Tibial Component Positioning in Total Knee Arthroplasty: Bone Coverage and Extensor Apparatus Alignmen”, Knee Surg, Sports Traumatol, Arthrosc, Vol.5 no.4, pp.251-257.
37.Levoy, M., 1990, “Efficient Ray tracing of Volume Data”, ACM Trans on Graph, Vol.9 no.3, pp.245-261.
38.Li, C.L. and Hui, Y.S., 2000, “Feature Recognition by Template Matching”, Computers and Graphics Vol.24 no.4, pp.569-582.
39.Liu, S. and Ma, W., 1999, “Seed-Growing Segmentation of 3-D Surface from CT-Contour Data”, Computer-Aided Design, Vol.31 no.8, pp.517-536.
40.Lorensen, W. E. and Cline, H. E., 1987, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm”, ACM Computer Graphics, Vol.21 no.4, pp.163-169.
41.Ludwing, A., Werner, K., Dietrich, M.-E., Rainer, R., Joachim, M., Gilsbach, R. M., and Georg, S., 1990 “Computer-Assisted Surgery”, IEEE Computer Graphics and Applications. Vol.10 no.3, pp.43-51.
42.Magaenat-Thalmann, N., Cordier, F., 2000, “Construction of a Human Topological Model from Medical Data”, IEEE Transactions on Information Technology in Biomedicine, Vol.4 no.2, pp.137-143.
43.Muschik, M., Zippel, H. and Perka, C., 1997, “Surgical Management of Severe Spondylolisthesis in Children and Adolescents. Anterior Fusion in Situ Versus Anterior Spondylodesis with Posterior Transpedicular Instrumentation and Reduction”, Spine, Vol.22 no.17, pp.2036-2042.
44.Nagel, A., Insall, J.N. and Scuderi, G.R., 1996, “Proximal tibial osteotomy. A Subjective Outcome Study”, J. Bone Joint Surg. Am. Vol.78A, pp.1353-1358.
45.Oikarinen, J.T. and Jyrkinen, L.J., 1998a, “Maximum Intensity Projection by 3-Dimensional Seed Filling in View Lattice”, Computer Networks and ISDN systems, Vol.30 no.20-21, pp.2003-2014.
46.Oikarinen, J., 1998b, “Using 2- and 21/2 Dimensional Seed Filling in View Lattice to Accelerate Volumetric Rendering”, Computers and Graphics, Vol.22 no.6, pp.745-757.
47.Panda, B. and Chatteji, B.N., 2001, “Least Square Generalized B-spline Signal and Image Processing”, Signal Processing, Vol.81 no.10, pp.2005-2017.
48.Regan, J.J., Yuan, H. and McCullen, G., 1997, “Minimally Invasive Approaches to the Spine”, AAOS Instr. Course Lect., Vol.46, pp.127-141.
49.Regan, J.J., Yuan, H., P.C. and Mc, A., 1999, “Laparoscopic Fusion of the Lumbar Spine: Minimally Invasive Spine Surgery, a Prospective Multicenter Study Evaluating Open and Laparoscopic Lumbar Fusion”, Spine, Vol.24, pp. 402-411.
50.Rosenthal, D., Rosenthal, R. and de Simone, A., 1994, “Removal of a Protruded Thoracic Disc Using Microsurgical Endoscopy: A New Technique”, Spine, Vol. 19, pp.1087-1091.
51.Scott, W.A., 1996, “Magnetic Resonance Imaging of the Brain and Spine”, 2nd ed. Lippincott-Raven publishers, Philadelphia, pp.1093.
52.Sealy, G. and Novins, K., 1999, “Effective Volume Sampling of Solid Models using Distance Measures”, Computer Graphics International’ 99, pp.26-32.
53.Seipel, S., Wagner, I.V., Koch, S. and Schneide, W., 1998, “Oral Implant Treatment Planning in a Virtual Reality Environment”, Computer Methods and Programs in Biomedicine, Vol.57 no.2, pp.95-103.
54.Shareef, N. and Yagel, R., 1995, “Rapid Previewing Via Volume-Based Solid Modeling”, ACM Solid Modeling’ 95, pp.285-291.
55.Sramek, M. and Kaufman, A., 1998, “Object Voxelization by Filtering”, IEEE Volume Visualization’ 98, pp.111-118.
56.Cotin, S., Delingette, H. and Ayache, N., 1999, “Real-Time Elastic Defoemations of Soft Tissues for Surgery Simulation”, IEEE Transaction on Visualization and Computer Graphics, Vol.5 no.1, pp.62-73.
57.Steven, A.C., Norberto, F. E., J.F.O’., Brien, R.R., Thomas, G. and Ellen, P., 1993, “Interactively Deformable Models for surgery Simulation”, IEEE Computer Graphics and Applications. Vol.13 no.6, pp.68-75.
58.Sourin, A. and Sourina, O., 2000, “Virtual Orthopedic Surgery Training”, IEEE Computer Graphics and Applications. Vol.20 no.3, pp.6-9.
59.Suárez, A., González, E., Cabo, J.C.Y., Rollot, Y., Manuel, B., Moreno, C. and Artigue, F., 1995, “An Autonomous Vehicle for Surface Filling”, Proceedings of the Intelligent Vehicles '95 Symposium, pp.364-369.
60.Tsai, M.D. and Hsieh, M.S., 2001a, “Surface Rendering for Multi-axial Cross Sections”, Journal of Information Science and Engineering, Vol.17 no.1, pp. 113-132.
61.Tsai, M.D., Jou, S.B. and Hsieh, M.S., 2001b, “Accurate Surface Voxelization for Manipulating Volumetric Surfaces and Solids with Application in Simulating Musculoskeletal Surgery”, Proceedings of the Tenth Pacific Conference on Graphics and Applications, IEEE CS Press, pp.234-243.
62.Tsai, M.D., Hsieh, M.S. and Jou, S.B., 2001c, “Virtual Reality Orthopedic Surgery Simulator”, Computers in Biology and Medicine, Vol.31 no.5, pp.333-351.
63.Tsai, M.D., Jou, S.B. and Hsieh, M.S., 2002a, “Three-Dimensional Geometric Constraint Evaluation and Analysis for Determining Commercial Knee Prosthesis”, Journal of Medical and Biological Engineering, To appear。
64.Tsai, M.D., Jou, S.B. and Hsieh, M.S., 2002b, “A New Method for Lumbar Herniated Computerized, Inter-Vertebral Disc Diagnosis based on Image Analysis of Transverse Sections”, Computerized Medical Imaging and Graphics, To appear。
65.Udupa, J.K. and Odhner, D., 1991, “Fast Visualization, Manipulation and Analysis of Binary Volumetric Objects”, IEEE Computer Graphics and Applications, Vol.11 no.5, pp.53-63.
66.Wang, S. and Kaufman, A., 1995, “Volume Sculpting", ACM Interactive 3D Graphics”, pp.151-156.
67.Whiteside, L.A., Arima, J. and McCarthy, D.S., 1995, “Rotational Alignment of the Femoral Component in Valgus Total Knee Arthroplasty Based Upon the Anterior-Posterior Axis”, in the AAOS Knee Society Meeting.
68.William, C.L. and Micbael, E.G., 2000, “Spine: In: Mark D.M. Review of Orthopaedics”, 3rd ed. W.B. Saunders company, New York, pp.353-378.
69.Yu, Y.W. and Wang, J.H., 1999, “Image Segmentation Based on Region Growing and Edge Detection”, IEEE SMC '99 Conference Proceedings, pp. 798-803.
70.Yu, S.W., Haughton, V.M., Sether, L.A. and Wagner, M., 1989, “Comparison of MR and Discography in Detecting Radial Tears of the Annulus: A Postmortem Study”, American Journal of Neuroradiology, Vol.10 no.5, pp.1077-1081.
71.Zhou, Y. and Toga, A.W., 2000, “Turning Unorganized Points into Contours”, Proceedings of the Eighth Pacific Conference on Graphics and Applications, IEEE CS Press, pp.243-252.