Difference between revisions of "Applied Computer Vision"

From David Vernon's Wiki
Jump to: navigation, search
(→‎Learning objectives)
(→‎Content details)
Line 46: Line 46:
 
The course will cover the following topics:
 
The course will cover the following topics:
  
−
* Introduction: The Software Development Life Cycle
+
# Optics, sensors, image formation
−
* Formalisms for Representing Algorithms
+
# Image acquisition & image representation
−
* Analysis of Complexity
+
# Image processing and image filtering.
−
* Searching and Sorting Algorithms
+
# Point &  neighbourhood operationsm, convolution, Fourier transform
−
* Abstract Data Types (ADT)
+
# Geometric operations, morphological operations, blob detection and analysis
−
* Containers, Dictionaries, and Lists
+
# Segmentation: edge detection, region growing, and boundary detection
−
* Stacks
+
# Hough transform: line, circle, and generalized transform; extension to codeword features.
−
* Queues
+
# Colour-based segmentation.
−
* Trees
+
# Object detection and recognition in 2D; Template matching.
−
* Heaps
+
# Interest point operators: Harris and Difference of Gaussian. Gradient orientation histogram - SIFT descriptor.
−
* Graphs
+
# Colour histogram intersection and back-projection.
−
* Complex Networks
+
# 3D vision Homogeneous coordinates and transformations. Perspective transformation.  Camera model and inverse perspective transformation.
−
* Hashing
+
# Stereo vision. Epipolar geometry. 
−
* Algorithmic Strategies
+
# Structured light & RGB-D cameras.
−
* Analysis of Correctness
+
# Optical flow.
−
<!-- * Databases -->
+
#Visual attention. Saliency. Bottom-up and top-down attention. 
−
<!-- * Programming Paradigms -->
+
# Clustering, grouping, and segmentation. Gestalt principles. Clustering algorithms.
−
* Automata Theory
+
# Object recognition in 2D and 3D.  Object detection, object recognition, object categorisation.
−
* Computability Theory
+
# Affordances.
 +
# Haar features. HOG.
 +
# Point cloud methods.
 +
 
  
 
''The detailed content for each of these topics follows.''
 
''The detailed content for each of these topics follows.''
Line 70: Line 73:
  
 
<span style="color:#AB0000">Introduction: The Software Development Life Cycle</span><BR>
 
<span style="color:#AB0000">Introduction: The Software Development Life Cycle</span><BR>
−
* Motivation
+
* xyz
−
* Goals of the course
+
−
* Syllabus and lecture schedule
+
−
* Course operation
+
−
* Software development tools for assignments
+
−
* Preview of course material
+
−
* Levels of abstraction in information processing systems
+
−
* The software development life cycle: Yourdon Structured Analysis - functional,  data, and behavioural models (hierarchical decomposition trees, architecture diagrams, data flow diagrams DFD, data dictionaries, entity relationship ER diagrams, state transition diagrams)
+
−
* Software process models: waterfall, evolutionary, formal transformation, re-use, hybrid, spiral
+
  
 
<span style="color:#AB0000">Formalisms for Representing Algorithms</span><BR>
 
<span style="color:#AB0000">Formalisms for Representing Algorithms</span><BR>
−
* Definition of an algorithm
+
* xyz
−
* Modelling software
+
−
* Relational modelling
+
−
* State modelling
+
−
* Practical representations
+
−
* Pseudo code
+
−
* Flow charts
+
−
* Finite state machines
+
−
* UML
+
−
* Predicate logic
+
−
* Analysis
+
  
 
<span style="color:#AB0000">Analysis of Complexity</span><BR>
 
<span style="color:#AB0000">Analysis of Complexity</span><BR>
−
* Performance of algorithms, time and space tradeoff, worst case and average case performance
+
* xyz
−
* Big O notation
+
−
* Recurrence relationships
+
−
* Analysis of complexity of iterative and recursive algorithms
+
−
* Recursive vs. iterative algorithms: runtime memory implications
+
−
* Complexity theory: tractable vs intractable algorithmic complexity
+
−
* Example intractable problems: travelling salesman problem, Hamiltonian circuit, 3-colour problem, SAT, cliques
+
−
* Determinism and non-determinism
+
−
* P, NP, and NP-Complete classes of algorithm
+
  
 
<span style="color:#AB0000">Searching and Sorting Algorithms</span><BR>
 
<span style="color:#AB0000">Searching and Sorting Algorithms</span><BR>
−
* Linear and binary search (iterative and recursive)
+
* xyz
−
* In-place sorts:  bubblesort (efficient and inefficient), selection sort, insertion sort.
+
−
* Not-in-place sorts: Quicksort, merge sort.
+
−
* Complexity analysis
+
−
* Characteristics of a good sort
+
−
* Speed, consistency, keys, memory usage, length & code complexity, stability
+
−
* Other sorts ordered by complexity
+
  
 
<span style="color:#AB0000">Abstract Data Types (ADT)</span><BR>
 
<span style="color:#AB0000">Abstract Data Types (ADT)</span><BR>
−
* Vector example exercise
+
* xyz
−
* History of abstraction
+
−
* Abstract Data Types (ADT)
+
−
* Information hiding
+
−
* Types and typing
+
−
* Encapsulation
+
−
* Efficiency
+
−
* Design practices
+
  
 
<span style="color:#AB0000">Containers, Dictionaries, and Lists</span><BR>
 
<span style="color:#AB0000">Containers, Dictionaries, and Lists</span><BR>
−
* Basic operations
+
* xyz
−
* Implementation with arrays and linked lists
+
−
* Singly linked lists
+
−
* Doubly linked lists
+
−
* Performance considerations
+
  
 
<span style="color:#AB0000">Stacks</span><BR>
 
<span style="color:#AB0000">Stacks</span><BR>
−
* Stack (LIFO): push, pop, peek, size, numItems operations
+
* xyz
−
* Array implementation (directly and array of pointers to data)
+
−
* Stack applications, including evaluation of infix, prefix, and postfix expressions
+
  
 
<span style="color:#AB0000">Queues</span><BR>
 
<span style="color:#AB0000">Queues</span><BR>
−
* Queue (FIFO): enqueue, dequeue, peek, size, numItems operations
+
* xyz
−
* Array implementation (directly and array of pointers to data)
+
−
* Linked list implementation
+
−
* Circular queues
+
−
* Performance considerations
+
−
<!-- * Deque -->
+
  
 
<span style="color:#AB0000">Trees</span><BR>
 
<span style="color:#AB0000">Trees</span><BR>
−
* Concepts and terminology: level, height, external and internal nodes, skinny, fat, complete, left-complete, perfect, multi-way, d-ary
+
* xyz
−
* Types of tree: binary, binary search, B-tree, 2-3 tree, AVL, Red-Black
+
−
* Binary trees and binary search trees
+
−
* Tree traversals: inorder, preorder, postorder
+
−
* Fixed-length codes, variable length codes, optimal code trees, Huffman's algorithm and implementation
+
−
* Height-balanced trees: AVL Trees, RR, RL, LR, LL rotations
+
−
* Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring
+
−
<!-- * Non-search trees: parse trees, array implementation, linked list implementation -->
+
−
<!-- * Forests -->
+
  
 
<span style="color:#AB0000">Heaps</span><BR>
 
<span style="color:#AB0000">Heaps</span><BR>
−
* Heap basics
+
* xyz
−
* Types of heap: min heaps and max heap
+
−
* Heap characteristics
+
−
* Heap operations: delete max/min, down heap, up heap, merge, construct, heapify; complexity of operations
+
−
* Priority queues
+
−
* Operating systems heaps
+
−
* Implementation of heap
+
−
* Heap sort
+
−
<!-- * d-ary heaps -->
+
−
<!-- * Leftist  heaps -->
+
  
 
<span style="color:#AB0000">Graphs</span><BR>
 
<span style="color:#AB0000">Graphs</span><BR>
−
* Types of graphs: directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, non-simple, implicit, explicit, embedded, topological
+
* xyz
−
* Adjacency matrix representation,
+
−
* Adjacency list representation
+
−
* Topological sort
+
−
* Euler's theorem
+
−
* Graph traversal: breadth-first and depth-first, uses of
+
−
* Depth-first search and maze traversal
+
−
* Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm
+
−
* Dijkstra's shortest path algorithm
+
−
* Floyd-Warshall's all-pairs algorithm
+
−
<!-- * Graphs problems: routes, Hamilton paths, network flows, covering problems, museum guard problem -->
+
−
<!-- * Fleury's Euler circuit algorithm -->
+
  
 
<span style="color:#AB0000">Complex Networks</span><BR>
 
<span style="color:#AB0000">Complex Networks</span><BR>
−
<!-- * Complex systems and large networks
+
* xyz
−
* Community detection
+
−
* Network evolution -->
+
−
* The importance of complex networks and network science
+
−
* Euler's theorem: the Bridges of Königsberg
+
−
* Networks vs. graphs
+
−
* Degree, average degree, and degree distribution
+
−
* Bipartite networks
+
−
* Path length, BFS, Connectivity, Components
+
−
* Clustering coefficient
+
−
* Random graph model
+
−
* Small world phenomena
+
−
* Scale free networks
+
−
* Communities
+
−
* Fundamental Hypothesis
+
−
* Connectedness and Density Hypothesis
+
−
* Strong and weak communities
+
−
* Graph partitioning
+
−
* Community detection
+
−
* Hierarchical clustering
+
−
* Girvan-Newman Algorithm
+
−
* Modularity
+
−
* Random Hypothesis
+
−
* Maximum Modularity Hypothesis
+
−
* Greedy algorithm for community detection by maximizing modularity
+
−
* Overlapping communities
+
−
* Clique percolation algorithm and CFinder
+
  
 
<span style="color:#AB0000">Hashing</span><BR>
 
<span style="color:#AB0000">Hashing</span><BR>
−
* Using keys to address data
+
* xyz
−
* Mappings: injection, surjection, bijection
+
−
* Map ADT
+
−
* Hash functions
+
−
* Hash tables: current value tables, direct access tables
+
−
* Managing collisions: chaining, overflow areas, re-hashing, linear probing, quadratic probing
+
−
<!-- * Evaluating hash functions: prime division, mid-square, folding, load factor -->
+
−
* Example application: dictionaries
+
−
<!-- * Generating hash functions and using hash structures -->
+
  
 
<span style="color:#AB0000">Algorithmic Strategies</span><BR>
 
<span style="color:#AB0000">Algorithmic Strategies</span><BR>
−
* Classes of algorithms
+
* xyz
−
* Brute force
+
−
* Divide and conquer
+
−
* Greedy algorithms
+
−
* Dynamic programming
+
−
* Combinatorial search and backtracking
+
−
* Branch and bound
+
−
<!-- * Heuristics and heuristic algorithms -->
+
−
<!-- * Probabilistic algorithms -->
+
  
 
<span style="color:#AB0000">Analysis of Correctness</span><BR>
 
<span style="color:#AB0000">Analysis of Correctness</span><BR>
−
* Types of software defects
+
* xyz
−
* Code module design
+
−
* Syntactic, semantic, logical defects
+
−
* (Semi-)formal verification: partial vs. total correctness
+
−
* Invariant assertion method
+
−
* Simple proof strategies: by contradiction, counterexample, induction
+
−
* Dynamic testing: unit tests, test harness, stubs, drivers, integration testing, regression testing.
+
−
* Static tests: reviews, walkthroughs, inspections, reviewing algorithms and software
+
−
* Pair programming
+
−
* Verification and validation strategies
+
  
−
<!--
 
−
<span style="color:#AB0000">Databases</span><BR>
 
−
* Databases: relational databases, hierarchical databases, NoSQL databases
 
−
* Relational databases: entity relationship modelling, relational algebra, SQL, normalization
 
−
* Compression strategies, dictionary algorithm, LZ algorithm
 
−
* File structure strategies.
 
−
-->
 
−
<!--
 
−
<span style="color:#AB0000">Programming Paradigms</span><BR>
 
−
* Imperative programming
 
−
* Logic programming
 
−
* Functional programming
 
−
* OO programming; classes; type, operational and functional polymorphism; inheritance, attributes, methods, instantiations, abstract classes, object-oriented languages
 
−
* OO design methodology: UML class diagram, composite-structure diagram, architecture diagram, package diagram, object diagram, component diagram, deployment diagram, activity diagram, sequence diagram, communication diagram, interaction diagram, timing diagram, use case diagram, state machine diagram
 
−
* OO design principles: open/close principle, design by contract principle, dependency inversion principle, other design principles, documentation
 
−
-->
 
−
<span style="color:#AB0000">Automata Theory</span><BR>
 
−
* Regular Languages
 
−
* Finite Automata
 
−
* Nondeterminism
 
−
* Regular Expressions
 
−
* Nonregular Languages
 
−
*Context-free Languages
 
−
* Context-free Grammars
 
−
* Pushdown Automata
 
−
* Deterministic Context-Free Languages
 
  
 
<span style="color:#AB0000">Computability Theory</span><BR>
 
<span style="color:#AB0000">Computability Theory</span><BR>
−
* The Church-Turing Thesis
+
* xyz
−
* Turing Machines
+
−
* Variants of Turing Machines
+
−
* The Definition of Algorithm
+
−
* Decidability
+
−
* Decidable Languages
+
−
* Undecidability
+
−
* Reducibility
+
  
 
==<span style="color:#AB0000">Lecture Schedule</span> ==
 
==<span style="color:#AB0000">Lecture Schedule</span> ==

Revision as of 06:48, 19 April 2017

|CARNEGIE MELLON UNIVERSITY AFRICA|

04-800
Applied Computer Vision

Elective

Units: 12

Lecture/Lab/Rep hours/week: 4 hours lectures/week

Semester: Spring

Pre-requisites: programming skills

Students are expected to be familiar with programming in at least one programming language, ideally C/C++.

Course description

This course provides students with a solid foundation in the key elements of computer vision, emphasizing the practical application of the underlying theory. It focusses mainly on the techniques required to build robot vision applications but the algorithms can also be applied in other domains such as industrial inspection and video surveillance. A key focus of the course is on effective implementation of solutions to practical computer vision problems in a variety of environments using both bespoke software authored by the students and standard computer vision libraries.

Learning objectives

The course covers optics, sensors, image formation, image acquisition & image representation before proceeding to the essentials of image processing and image filtering. This provides the basis for a treatment of image segmentation, including edge detection, region growing, and boundary detection, the Hough transform, and colour-based segmentation.

Building on this, the course then proceeds to deal with object detection and recognition in 2D, addressing template matching, interest point operators, gradient orientation histograms, the SIFT descriptor, and colour histogram intersection and back-projection.

The problem of recovery of 3D information is then addressed, introducing homogeneous coordinates and transformations, the perspective transformation, camera model, inverse perspective transformation, stereo vision, and epipolar geometry.

The interpretation of visual information in unstructured environments poses many problems. To deal with these, the course then addresses visual attention, clustering, grouping, and segmentation, building on Gestalt principles, before proceeding to deal with object detection, object recognition, and object categorization in both 2D and 3D.

Outcomes

After completing this course, students should be able to:

  • Apply their knowledge of image acquisition, image processing, and image analysis to extract the required information from visual images.
  • Design, implement, and document appropriate, effective, and efficient software solutions for a variety of real-world computer vision problems.
  • Exploit standard computer vision software libraries in the development of these solutions.

Content details

Refer to the Lecture Schedule for information on course delivery, including lectures, labs, assignments, and exercises.

The course will cover the following topics:

  1. Optics, sensors, image formation
  2. Image acquisition & image representation
  3. Image processing and image filtering.
  4. Point & neighbourhood operationsm, convolution, Fourier transform
  5. Geometric operations, morphological operations, blob detection and analysis
  6. Segmentation: edge detection, region growing, and boundary detection
  7. Hough transform: line, circle, and generalized transform; extension to codeword features.
  8. Colour-based segmentation.
  9. Object detection and recognition in 2D; Template matching.
  10. Interest point operators: Harris and Difference of Gaussian. Gradient orientation histogram - SIFT descriptor.
  11. Colour histogram intersection and back-projection.
  12. 3D vision Homogeneous coordinates and transformations. Perspective transformation. Camera model and inverse perspective transformation.
  13. Stereo vision. Epipolar geometry.
  14. Structured light & RGB-D cameras.
  15. Optical flow.
  16. Visual attention. Saliency. Bottom-up and top-down attention.
  17. Clustering, grouping, and segmentation. Gestalt principles. Clustering algorithms.
  18. Object recognition in 2D and 3D. Object detection, object recognition, object categorisation.
  19. Affordances.
  20. Haar features. HOG.
  21. Point cloud methods.


The detailed content for each of these topics follows.


Introduction: The Software Development Life Cycle

  • xyz

Formalisms for Representing Algorithms

  • xyz

Analysis of Complexity

  • xyz

Searching and Sorting Algorithms

  • xyz

Abstract Data Types (ADT)

  • xyz

Containers, Dictionaries, and Lists

  • xyz

Stacks

  • xyz

Queues

  • xyz

Trees

  • xyz

Heaps

  • xyz

Graphs

  • xyz

Complex Networks

  • xyz

Hashing

  • xyz

Algorithmic Strategies

  • xyz

Analysis of Correctness

  • xyz


Computability Theory

  • xyz

Lecture Schedule

Refer to the Lecture Schedule for information on course delivery, including lectures, labs, assignments, and exercises.

Faculty

David Vernon

Delivery

Face-to-face.

Student assessment

This course includes several hands-on programming and analysis assignments. Students will program mainly in C/C++. The programming assignments include individual assignments and a team capstone project in teams of 2-3 people. In addition to programming assignments, students will be assigned readings to support the lecture material.

Marks will be awarded as follows.

Seven individual assignments 70%. Final examination 30%.

Software tools

We will use Microsoft Visual C++ Express compiler, version 10.0 (also known as Visual C++ 2010) and CMake running on Windows 7 (64 bit).

Please follow the instructions provided in the Software Development Environment installation guide.

Course texts

David Harel and Yishai Feldman, Algorithmics: The Spirit of Computing, Third Edition.

Alfred V. Aho, Jeffrey D. Ullman, and John E. Hopcroft, Data Structures and Algorithms.

A selection of examples will be taken from Steven Skiena, "The Algorithm Design Manual", Second Edition.

A selection of papers and readings will be provided to complement these required textbooks.

Acknowledgments

This syllabus is based mainly on Course 04-630 Computer Science Principles for Practicing Engineers given by Mel Rosso-Llopart and Anthony J. Lattanze at Carnegie Mellon University, USA, Course CS-CO-412 Algorithms and Data Structures given by David Vernon at Innopolis University, Russia, and Course IT706A Scientific Theory in Informatics given by David Vernon and others at the University of Skövde, Sweden.

Retrieved from "http://www.vernon.eu/w/index.php?title=Applied_Computer_Vision&oldid=1433"