Lecture “Algorithms for Picture Analysis”

 

BASICS

1. Pictures; Pixels and Voxels; Adjacency and Connectedness

2. History of Digital Picture Analysis

3. Component Labeling

 

DIGITIZATION; MEASURING PROPERTIES

4. Digitization of Curves; Bresenham Algorithm

5. Approximation of pi; Failure of "Staircase Counts"

6. Multigrid Convergence: Gauss Digitization and Area of a Planar Set

 

METRICS; DISTANCE TRANSFORMS

7. Metrics: Euclidean and Integer-Valued Metrics

8. Basic Distance Transforms; Distances between Sets

9. MAT and Euclidean Distance Transform (for EDT, see also here or the PhD thesis by Gisela Klette)

 

====== Exercises for Lectures 01 - 10

 

BORDERS; REGION ADJACENCY GRAPHS

10. Borders and Border Tracing

11. Holes, Planarity, and Region Adjacency

12. Properties of 2D Regions; Frontier Grid

 

GRID CELL TOPOLOGY; FRONTIERS

13. The 2D and 3D Cellular Grid; Grid Cell Topology

14. 2D Frontier Tracing and Euler Characteristic

 

DSSs and MLPs; LENGTH OF A DIGITAL CURVE

15. DSSs: Definition and Characterization

16. DSS Approximation of Frontiers (K1990)

17. DSS Approximation of Borders (DR1995)

18. Relative Convex Hull; MLP Approximation of Borders

19. The Length of a Digital Curve; MLP

20. Experimental Evaluation of Length Estimators

 

====== Exercises for Lectures 11 - 20

 

CURVATURE; CORNERS

21. Definition of Curvature for Planar Curves

22. Algorithms for Curvature Estimation

23. Algorithms for Corner Detection

24. Evaluation of Curvature/Corner Algorithms

 

STEPS INTO 3D PICTURE ANALYSIS

25. 3D Components, Borders, and Frontiers

26. Artzy-Herman Algorithm for Frontier Tracing

 

====== Exercises for Lectures 21 - 26

 


COURSEWORK OPTIONS

A solution should be submitted via email to the tutor, or to the e-dropbox, containing source code for testing, and explaining text in pdf format, all zipped into one file named by ID number and number of assignment (for example 1234567_4.zip, if for assignment A.4)

(A) Each student has to submit her/his solution to 4 of the assignments (e.g., A.1, A.2, and so forth). Deadline is 3 weeks after the lecture presenting the exercise (limited by the general deadline of one week after the end of the lectures).

(B) Each student has to obtain 10 marks or more for passing the coursework part. Assignments (e.g., A.1, A.2, and so forth) are labeled by marks, ranging between 3 and 7. Deadline is 1 week after the lecture presenting the exercise (limited by the general deadline of the end of the lectures).

(C) Each student has to solve two assignments (e.g., A.1, A.2, and so forth) for passing the coursework part, where "solve" means that at least 50 percent of the submission is correct. Deadline is 2 weeks after the lecture presenting the exercise (limited by the general deadline of the end of the lectures).


EXAM OPTIONS

The questions in the exam will be (minor) modifications of some of the exercises provided in the three exercise files above. Calculators, computers, or any hardcopies are not allowed for the exam.

(A) Written exam: two hours.

(B) Oral exam: 20 minutes.


These lecture notes have been used for courses at

CINVESTAV (Departmento de Control Automatico), Mexico-City, Mexico
in February 2005 (without assignments or exam),

The University of Auckland (Tamaki campus, COMPSCI 375 FS 2005), Auckland, New Zealand,
in March - May 2005,
using option (A) for coursework and a written exam,

the University of Freiburg (Institut fuer Informatik, Algorithms for Picture Analysis SS 2005), Freiburg, Germany
in June - July 2005,
using option (B) for coursework and having an oral exam,

NTNU (Graduate Institute of Computer Science and Information Engineering, Algorithms for Picture Analysis), Taipei, Taiwan,
in November - December 2005,
using option (C) for coursework and having a written exam, and

ISS (International School of Software, Multimedia Imaging), Wuhan, China,
in September 2006.


This site contains material (figures, definitions, algorithms, and so forth) from the book

[R. Klette and A. Rosenfeld: Digital Geometry - Geometric Methods for Picture Analysis.
Morgan Kaufmann, San Francisco, 2004].

If cited at all, then it should be cited with respect to this source. However, some material in
these lecture notes is not contained in the book, and it could be cited as
[R. Klette: Algorithms for Picture Analysis. Lecture XX,
www.mi.auckland.ac.nz/books/KR/Algorithms.htm,
(date as at the bottom of pages of Lecture XX)].