## PA170 Digital Geometry

Faculty of Informatics
Autumn 2009
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
doc. RNDr. Pavel Matula, Ph.D. (lecturer)
Guaranteed by
prof. Ing. Jiří Sochor, CSc.
Department of Visual Computing – Faculty of Informatics
Contact Person: doc. RNDr. Pavel Matula, Ph.D.
Timetable
Fri 10:00–11:50 C525, Fri 12:00–13:50 C525
Prerequisites
The basic knowledge of mathematics and graph theory is recommended.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
there are 24 fields of study the course is directly associated with, display
Course objectives
At the end of the course students should be able to: understand and explain basic problems that arise after object digitization and an object representation using a grid of points (e.g., in the form of digital image); measure geometric and topological properties of digital objects (e.g., length, area, perimeter, volume, Euler characteristic, and the number of holes); compare digital metrics; efficiently implement the key algorithms of digital geometry (e.g., region labeling, border tracing, and distance map computation); identify the fundamentals of the discussed methods.
Syllabus
• Basic terms: digital image, pixel, voxel, image resolution, types of grids, grid scanning
• grid point and grid cell models: adjacency, incidence, connectedness, components, component labeling algorithms.
• Digitalization: digitization models, line digitization.
• Measurement in digital images: metrics, integer-valued metrics approximating Euclidean metric, distance transform, distance measurement between sets.
• Oriented adjacency graphs: border, boundary, border tracing algorithm, holes, combinatorial results for regular graphs (grids)
• Application of graph theory in image processing, graph-cut based image segmentation.
• Incidence pseudographs, open and closed regions, ordered labeling of multilevel images.
• Introduction to topology. Basic topological concepts. Definition of continuous as well as digital curve. Jordan Veblen theorem.
• Euclidean and simplex complexes (triangulation). Topological definition of surfaces and their classification. Combinatorial results. Regular tilings.
• Estimation and computation of geometric and topological properties of digital sets: volume, surface, area, perimeter, length, curvature, Euler characteristic, etc.
• Digital straight segment recognition, digital straightness, digital convex hull and its computation.
• Image deformations: Thinning, skeletons.
Literature
• KLETTE, Reinhard and Azriel ROSENFELD. Digital geometry: geometric methods for digital picture analysis. Amsterdam: Elsevier, 2004, 656 pp. info
Teaching methods
Lectures followed by class exercises where we will solve practical problems by taking the advantage of lecture findings. Homework.
Assessment methods
Written test, oral exam. Obligatory attandance at exercises. Homework score.
Language of instruction
Czech