Segmentation & Modeling - Department of Computer Science

Segmentation & Modeling - Department of Computer Science

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

Recently Viewed Presentations

  • Levels of metaphor - eil.grad.chula.ac.th

    Levels of metaphor - eil.grad.chula.ac.th

    In conclusion, then, the cognitive linguistic view of metaphor that has been discussed in this book works on three levels: the supraindividual level corresponding to how a given language and culture reflects decontextualized metaphorical patterns, the individual level corresponding to...
  • Visual PPT Quiz 1 - KATMAN SCIENCE

    Visual PPT Quiz 1 - KATMAN SCIENCE

    Question #3: In what order do a hawk, grass, and rabbit form a food chain in a meadow? Question #4: The further along the food chain you go, the less food (and hence energy) remains available. Question #5: This is...
  • Blue Ocean Strategy Objectives  Explain Who developed the

    Blue Ocean Strategy Objectives Explain Who developed the

    Explain What is the ERRC Grid. Explain the Use of the Buyer Utility Map. Explain Steps for Strategy Reorientation & Execution . List the Core Values to Drive Innovation. Describe How to Choose Right Strategic Approach. Objectives.
  • Demographic Redistricting Study

    Demographic Redistricting Study

    Middle school changes only within same high school boundaries. ... as indicated in the lower portion of the below picture. PLArea: 242 - This is a planning area, or "puzzle piece", that represents a small section of the district ......
  • Simile Acrostic Poems on Gingerbread Boys and Girls

    Simile Acrostic Poems on Gingerbread Boys and Girls

    Begin forming similes out of the descriptive words that you have chosen. Example: Sparkly as a . diamond. Remember: you are comparing the descriptive word with a noun (person, place, thing, or idea) that represents what that description means to...
  • Pro Card Review - University of Texas at El Paso

    Pro Card Review - University of Texas at El Paso

    Pro-Card Reconciliation Process. Click on to expand the screen. 1. Use the Pro Card Transactions page to review, manage, and approve pro card transactions loaded by the Load Statement Process. You can view all of the pro card transactions that...
  • OVERCOMING PREJUDICE FOR CAREER IN STEM WITH ... - uni-sofia.bg

    OVERCOMING PREJUDICE FOR CAREER IN STEM WITH ... - uni-sofia.bg

    "European Researchers' Night 2018" in Museum of Palaeontology and Historical Geology at Sofia University "St. KlimentOhridski" Spring Scientific Session FMI- 2019 ... designed her own IBL scenario for presenting the researchers' career to her class of third grade students in...
  • CHAPTER 13 IMPLEMENTING STRATEGY IN COMPANIES THAT COMPETE

    CHAPTER 13 IMPLEMENTING STRATEGY IN COMPANIES THAT COMPETE

    Discuss the strategy-implementation problems associated with the three primary methods used to enter new industries: internal new venturing, joint ventures, and mergers ... Loss of new technology to the company's partner or to a competitor who acquires the partner.