Segmentation & Modeling Images Segmented Images Models Segmentation Process of identifying structure in 2D & 3D images Output may be labeled pixels edge map set of contours Approaches Pixel-based Thresholding Region growing Edge/Boundary based Contours/boundary surface Deformable warping Deformable registration to atlases Thresholding 3 5 7 3

4 2 1 2 4 9 10 22 9 3 3 5 12 11 15 10 3

5 6 11 9 17 19 1 2 3 11 12 18 16 2 3 6 8 10

18 9 5 4 6 7 8 3 3 1 Thresholding 3 5 7 3 4 2 1

2 4 9 10 22 9 3 3 5 12 11 15 10 3 5 6 11

9 17 19 1 2 3 11 12 18 16 2 3 6 8 10 18 9 5

4 6 7 8 3 3 1 Thresholding 3 5 7 3 4 2 1 2 4 9

10 22 9 3 3 5 12 11 15 10 3 5 6 11 9 17 19

1 2 3 11 12 18 16 2 3 6 8 10 18 9 5 4 6 7

8 3 3 1 Thresholding 3 5 7 3 4 2 1 2 4 9 10 22 9

3 3 5 12 11 15 10 3 5 6 11 9 17 19 1 2 3

11 12 18 16 2 3 6 8 10 18 9 5 4 6 7 8 3 3

1 Region Growing 3 5 7 3 4 2 1 2 4 9 10 22 9 3 3 5

12 11 15 10 3 5 6 11 9 17 19 1 2 3 11 12 18

16 2 3 6 8 10 18 9 5 4 6 7 8 3 3 1 Region Growing 3

5 7 3 4 2 1 2 4 9 10 22 9 3 3 5 12 11 15

10 3 5 6 11 9 17 19 1 2 3 11 12 18 16 2 3

6 8 10 18 9 5 4 6 7 8 3 3 1 Region Growing 3 5 7 3

4 2 1 2 4 9 10 22 9 3 3 5 12 11 15 10 3 5

6 11 9 17 19 1 2 3 11 12 18 16 2 3 6 8 10

18 9 5 4 6 7 8 3 3 1 Region Growing 3 5 7 3 4 2 1

2 4 9 10 22 9 3 3 5 12 11 15 10 3 5 6 11 9

17 19 1 2 3 11 12 18 16 2 3 6 8 10 18 9 5

4 6 7 8 3 3 1 Region Growing 3 5 7 3 4 2 1 2 4 9

10 22 9 3 3 5 12 11 15 10 3 5 6 11 9 17 19 1

2 3 11 12 18 16 2 3 6 8 10 18 9 5 4 6 7

8 3 3 1 Deformable Surfaces 3 5 7 3 4 2 1 2 4 9 10 22 9

3 3 5 12 11 15 10 3 5 6 11 9 17 19 1 2 3 11

12 18 16 2 3 6 8 10 18 9 5 4 6 7 8 3 3

1 Deformable Surfaces 3 5 7 3 4 2 1 2 4 9 10 22 9 3 3 5

12 11 15 10 3 5 6 11 9 17 19 1 2 3 11 12 18 16

2 3 6 8 10 18 9 5 4 6 7 8 3 3 1 Deformable Surfaces 3 5

7 3 4 2 1 2 4 9 10 22 9 3 3 5 12 11 15

10 3 5 6 11 9 17 19 1 2 3 11 12 18 16 2 3 6

8 10 18 9 5 4 6 7 8 3 3 1 Deformable Surfaces 3 5 7 3 4

2 1 2 4 9 10 22 9 3 3 5 12 11 15 10 3 5

6 11 9 17 19 1 2 3 11 12 18 16 2 3 6 8 10 18

9 5 4 6 7 8 3 3 1 Deformable Surfaces Deformable Surfaces Modeling Representation of anatomical structures Models can be Images Labeled images Boundary representations FROM VOXELS TO SURFACES Representing solids: B-REP - surface representation, d/s of vertices, edges, faces. CSG- composition of primirive solids

binary image B-REP representation Surface construction algorithms: 2D-based algrorithms 3D-based algorithms Surface Representations Implicit Representations {x | f ( x ) 0} Explicit Representations Polyhedra Interpolated patches Spline surfaces ... Source: CIS p 73 (Lavallee image) Polyhedral Boundary Reps Common in computer graphics Many data structures. Winged edge Connected triangles etc. Source: C. Cutting, CIS Book Winged Edge Baumgart 1974 Basic data structures winged edge (topology) vertex (geometry) face (surfaces)

Key properties constant element size topological consistency Pccwe Pcwe PVT Nface Pface NVT Nccwe Ncwe Connected Triangles Basic data structures Vc Triangle (topology, surfaces) Vertex (geometry) Na Nb Properties Constant size elements Topological consistency Vb

Va Nc 2D-based Methods Ribbon Stacking 2D-based methods Treat 3D volume as a stack of slices Outline Find contours in each 2D slice Connect contours to create tiled surfaces SURFACE CONSTRUCTION ALGORITHMS 2D-based algorithms 1. 2D contour extraction 2. tiling of counours Keppel (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

vertex v1 v2 Bndry v1 v2 3D-BASED ALGORITHMS Block-form and Beveled-form representations of surface: Block form methods Cuberille-type methods Treat voxels as little cubes May produce selfintersecting volumes E.g., Herman, Udupa Ref: Udupa , CIS Book, p47 Beveled 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 others Beveled 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 others Beveled-form Algorithms and medical Imaging Classification by definition of vertex adjacency (boundary element adjacency). Vertex adjacency can be calculated: 1. Inconsistently 2. Tetrahedral tessellation 3. Supersampling 4. 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 ambiguities Source: Kalvin survey Marching Cubes Lorensen & Kline Probably best known

Used symmetries to reduce number of cases to consider from 256 to 15 BUT there is an ambiguity Wyvill, McPheters, Wyvill Step 1: determine edges on each face of 8 cube Step 2: Connect the edges up to make surfaces Ambiguities Arise when alternate corners of a 4-face have different labels Ways to resolve: supersampling look at adjacencent cells tetrahedral tessallation Tetrahedral Tessalation Many Authors Divide each 8-cube into tetrahedra Connect tetrahedra No ambiguities Alligator ALGORITHMS Algorithm ALLIGATOR 1. Phase 1: Initial construction 2. Phase 2: Adaptive face-merging

Phase 1: Initial Construction Phase 2: Adaptive Merging ALLIGATOR ALGORITHMS Phase 2 - Adaptive face merging Algorithm 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 (e.g. topological genus) ALLIGATOR ALGORITHMS Phase 2 - Adaptive face merging Source: C. Cutting, CIS Book