Segmentation & ModelingSegmentationPowerPoint PresentationApproachesThresholdingSlide 6Slide 7Slide 8Region GrowingRegion GrowingSlide 11Slide 12Slide 13Deformable SurfacesSlide 15Slide 16Slide 17Slide 18Slide 19ModelingSlide 21Surface RepresentationsPolyhedral Boundary RepsSlide 24Winged EdgeConnected TrianglesSlide 272D-based methodsSlide 293D-based methodsSlide 31Block form methodsSlide 33Beveled form methodsSlide 35Slide 36Beveled form basic approachMarching CubesSlide 39AmbiguitiesSlide 41Slide 42Slide 43Slide 44Slide 45Segmentation & ModelingImages SegmentedImagesModelsSegmentation•Process of identifying structure in 2D & 3D images•Output may be–labeled pixels–edge map–set of contoursApproaches•Pixel-based–Thresholding–Region growing•Edge/Boundary based–Contours/boundary surface–Deformable warping–Deformable registration to atlasesThresholding3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Thresholding3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Thresholding3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Thresholding3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Region Growing3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Region Growing3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Region Growing3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Region Growing3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Region Growing3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Deformable Surfaces3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Deformable Surfaces3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Deformable Surfaces3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Deformable Surfaces3 5 7 3 4 2 12 4 9 10 22 9 33 5 12 11 15 10 35 6 11 9 17 19 12 3 11 12 18 16 23 6 8 10 18 9 54 6 7 8 3 3 1Deformable SurfacesDeformable SurfacesModeling•Representation of anatomical structures•Models can be –Images–Labeled images–Boundary representationsFROM VOXELS TO SURFACESRepresenting solids: • B-REP - surface representation, d/s of vertices, edges, faces.• CSG- composition of primirive solidsbinary image B-REP representationSurface construction algorithms:• 2D-based algrorithms• 3D-based algorithmsSurface Representations•Implicit Representations•Explicit Representations–Polyhedra –Interpolated patches–Spline surfaces–...{ | ( ) }x f x 0Source: CIS p 73 (Lavallee image)•Common in computer graphics•Many data structures. –Winged edge–Connected triangles–etc.Polyhedral Boundary RepsSource: C. Cutting, CIS BookWinged Edge•Baumgart 1974•Basic data structures–winged edge (topology)–vertex (geometry)–face (surfaces)• Key properties–constant element size–topological consistencyPVTNVTPfaceNfacePccwePcweNccweNcweConnected Triangles•Basic data structures–Triangle (topology, surfaces)–Vertex (geometry)•Properties–Constant size elements–Topological consistencyVaNaVbVcNbNcRibbon Stacking2D-based Methods2D-based methods•Treat 3D volume as a stack of slices•Outline–Find contours in each 2D slice–Connect contours to create tiled surfacesSURFACE CONSTRUCTION ALGORITHMS2D-based algorithms1. 2D contour extraction2. tiling of counoursKeppel (1975), Fuchs (1978), Christiansen (1981), Shantz (1981), Ganapathy (1982),Cook (1983), Zyda (1987), Boissonnat (1988), Schwartz (1988) Contour extraction• Sequential scanning• boundary following (random access to pixels)3D-based methods•Segment image into labeled voxels•Define surface and connectivity structure•Can treat boundary element between voxels as a face or a vertexv1v2v1v2Bndry3D-BASED ALGORITHMSBlock-form and Beveled-form representations of surface:Block form methods•“Cuberille”-type methods•Treat voxels as little cubes•May produce self-intersecting volumes•E.g., Herman, UdupaRef: Udupa , CIS Book, p47Beveled form methods•“Marching cubes” type•Voxels viewed as 3D grid points•Vertices are points on line between adjacent grid points•E.g. Lorensen&Cline, Baker, Kalvin, many othersBeveled form methods• “Marching cubes” type• Voxels viewed as 3D grid points• Vertices are points on line between adjacent grid points• E.g. Lorensen&Cline, Barker Kalvin, many othersBeveled-form Algorithms and medical ImagingClassification by definition of vertex adjacency (boundary element adjacency).Vertex adjacency can be calculated:1. Inconsistently2. Tetrahedral tessellation3. Supersampling4. Voxel topology best for 3D medical applications.Beveled form basic approach•Segment the 3D volume•Scan 3D volume to process “8-cells” sequentially•Use labels of 8 cells as index in (256 element) lookup table to determine where surfaces pass thru cell•Connect up topology•Use various methods to resolve ambiguitiesSource: Kalvin surveyMarching Cubes•Lorensen & Kline•Probably best known•Used symmetries to reduce number of cases to consider from 256 to 15•BUT there is an ambiguityWyvill, McPheters, WyvillStep 1: determine edges on each face of 8 cubeStep 2: Connect the edges up to make surfacesAmbiguities•Arise when alternate corners of a 4-face have different labels•Ways to resolve:–supersampling–look at adjacencent cells–tetrahedral tessallationTetrahedral Tessalation•Many Authors•Divide each 8-cube into tetrahedra•Connect tetrahedra•No ambiguitiesALLIGATOR ALGORITHMS1. Phase 1: Initial construction2. Phase 2: Adaptive face-mergingAlligator Algorithm•Phase 1: Initial Construction•Phase 2: Adaptive MergingALLIGATOR ALGORITHMSPhase 2 - Adaptive face mergingAlgorithm exploits the following:1. beveled-form property:•each vertex lies on 4 faces•only 2 possible ways for a vertex to lie on 4 regular faces.2. Euler operators•simple, high-level operations•efficient•simplifies proof of correctness
View Full Document