Advanced Techniques for Face-based Biometrics
Massimo Tistarelli (tistauniss.it)
DAP - Computer Vision Laboratory
University of Sassari
Massimo Tistarelli was born on November 11, 1962 in Genoa, Italy.
He received a MS degree in Electronic Engineering from the
University of Genoa, Italy in 1987 and the Phd in Computer
Science and Robotics in 1991 from the same university.
Since 1986 he has been involved as project coordinator and task
manager in several projects on computer vision and image analysis
funded by the European Community. During 1986, 1991 and 1996 he
has been visiting the Department of Computer Science, Trinity
College, and in 1989 he was a visiting scientist at Thinking
Machines Co. and MIT in Cambridge, Massachusetts, developing
parallel algorithms for dynamic image processing on the
Connection Machine system. Since 1994 he has been the director of
the Computer Vision Laboratory at the Department of
Communication, Computer and Systems Science of the University of
Genoa, leading several national and European projects on computer
vision applications and image-based biometrics. He is member of
the steering board of the Biosecure, European Network of
Excellence and founding member of the Biosecure foundation for
His main research interests cover biological and artificial
vision (particularly in the area of recognition and dynamic scene
analysis), biometrics, robotic navigation and visuo-motor
coordination. He is author of more than 80 papers in scientific
conferences and international journals. In 2000 he was the
chairman for the International workshop on "Advances in Facial
Image Analysis and Recognition Technology" and in 2002 for the
International workshop on "Biometric Authentication". In 2007 he
was the general chair for the 5th IEEE Int.l Workshop on
Automatic Identification Advanced Technologies . He was track co-
chair for track 7 on Biometrics of ICPR 2008 and the general
chairman of the 3rd IAPR Int.l Conference on Biometrics, held in
June 2009. Since 2003 he is the permanent director for the
International Summer School on Biometrics held in Alghero, Italy.
He is associate editor of Image and Vision Computing journal and
member of the program committee in several international
conferences on computer vision and image analysis. He is a IAPR
fellow and senior member of IEEE.
Massimo Tistarelli is currently Full Professor in Computer
Science at the University of Sassari, Italy.
The tutorial will consists of two sessions devoted to the
description of the basic techniques related to face recognition.
The lectures will provide a comprehensive outline of face-based
biometrics, its relation to biological systems (the psychophysics
of the human visual system), including the existing applications
and commercial systems.
The lectures will then provide an in-depth analysis of the state-
of-the-art algorithms for face-image analysis including: face
detection and tracking, landmark localization, feature
extraction, face representation and classification.
The lectures will be mostly devoted to the image processing
aspects of the recognition process, rather than on the
classification itself. As for classification, machine learning
algorithms will be also presented, including kernel methods as
related to learning and the approximation theory. The most
relevant issues and problems will be raised, providing practical
solutions and algorithms responding to them. Particular attention
will be given to the most advanced and new techniques for face
representation and classification, as well as the current
approaches presented in the literature.
Finally, the tutorial will present three relevant and novel
issues: the use of face image sequences for exploiting the time
domain, the extension to expression and emotion recognition, 3D
face analysis, and the how to cope with ageing and data quality.
- Topics Covered
1. Basic concepts of biometric systems: motivations, potential applications, techniques and
2. Notions from the psychophysics of the human visual system and related experiments.
3. How a face-based recognition system works
4. Example of existing systems and applications
1. Algorithmic issues in face recognition:
a. Face detection and tracking
b. Geometric and photometric normalization
c. Landmark localization
d. Features extraction, selection and face representation
e. Classification and learning
2. Open problems: outstanding issues and possible solutions
3. New frontiers in face recognition:
a. Exploitation of the time dimension and emotion recognition
b. 3D face image analysis
c. Dealing with ageing and data quality.
Fabio Roli (rolidiee.unica.it)
Dept. of Electrical and Electronic Engineering
University of Cagliari
Fabio Roli received his M.S. degree, with honours, and Ph.D.
degree in Electronic Engineering from the University of Genoa,
Italy. He was a member of the research group on Image Processing
and Understanding of the Dept. of Biophysical and Electronic
Engineering of the University of Genoa, Italy, from 1988 to 1994.
He was adjunct professor at the University of Trento, Italy, in
1993 and 1994. In 1995, he joined the Dept. of Electrical and
Electronic Engineering of the University of Cagliari, Italy,
where he is now professor of computer engineering and head of the
research group on pattern recognition and applications
(http://prag.diee.unica.it). Prof. Rolis current research
activity is focused on multiple classifier systems and their
applications to biometric personal identification, multimedia
document categorization, and computer security. On such topics,
he has published more than one hundred papers at conferences and
on journals and has given lectures and tutorials. He is Senior
member of the IEEE and Fellow of the International Association
for Pattern Recognition. Prof. Roli was the chairman of the IAPR
Technical Committee on Statistical Techniques in Pattern
Recognition from 2004 to 2008.
Dept. of Electrical and Electronic Engineering
University of Cagliari
Giorgio Fumera received the M.Sc. degree in Electronic Eng. with
honours, in 1997, and the Ph.D. in Electronic and Computer Eng.,
in 2002, from the University of Cagliari. Since 2002 he is
assistant professor of computer engineering in the Dep. of
Electrical and Electronic Eng. of the same University. His
research interests are in the field of statistical pattern
recognition and its applications. His research topics include the
reliability of pattern recognition systems, multiple classifier
systems, and multimedia document categorization. G. Fumera is a
member of the IEEE and IEEE Computer Society, and of the Italian
chapter of the International Association for Pattern Recognition.
Pattern classifiers are currently used in several applications,
like biometric recognition, spam filtering, and intrusion
detection in computer networks, which are different from
traditional pattern recognition tasks. The difference lies in the
fact that in these applications an intelligent, adaptive
adversary can actively manipulate patterns with the aim of making
a classifier ineffective, namely, with the aim of evading it.
Traditional pattern recognition techniques do not take into
account the adversarial nature of classification problems like
the ones mentioned above. One of the consequences is that the
performance of standard pattern classifiers can significantly
degrade when they are used in adversarial tasks.
This kind of problem has been named adversarial classification,
and is the subject of an emerging research field in the machine
learning community. Despite many pattern recognition applications
are basically adversarial classification tasks, so far this
research field received little attention in the pattern
The purposes of this tutorial are: (a) to introduce the
fundamentals of adversarial classification from the perspective
of a designer of a pattern recognition system; (b) to illustrate
the design cycle of a pattern recognition system for adversarial
tasks, (c) to present the new techniques that have been recently
proposed to assess performance of pattern classifiers under
attack, evaluate classifiers vulnerabilities, and implement
defence strategies that make classifiers more robust against
attacks; (d) to show some applications of adversarial
classification techniques to pattern recognition tasks like
biometric recognition and spam filtering.
- Topics Covered
1. Introduction to adversarial pattern classification
- Introduction by examples from biometrics, spam filtering,
and intrusion detection in computer networks.
- Previous works on adversarial learning and classification.
- Basic concepts and terminology.
2. Design of pattern classification systems in adversarial environments
- Modelling of adversarial tasks.
- The two-player model (the attacker and the classifier).
- The design cycle of adversarial pattern classification systems.
3. System design: vulnerability assessment and performance evaluation
- Attack models against pattern classifiers.
- Performance evaluation.
- Vulnerability assessment by performance evaluation.
- Examples of performance evaluation of classifiers under attack.
4. System design: defence strategies
- Taxonomy of possible defence strategies.
- Examples from biometrics, spam filtering, and intrusion detection
in computer networks
- General-purpose defence strategies: hiding information about
the pattern classifier, randomized classifiers, evade hard multiple
Read more ...
Michal Haindl (haindlutia.cas.cz)
Institute of Information Theory and Automation
Academy of Sciences of the Czech Republic
Michal Haindl graduated in control engineering from the Czech Technical University (1979), Prague, received PhD in technical cybernetics from the Czechoslovak Academy of Sciences (1983) and the ScD (DrSc) degree from the Czech Technical University (2001). He is a fellow of the IAPR and professor. From 1983 to 1990 he worked in the Institute of Information Theory and Automation of the Czechoslovak Academy of Sciences, Prague on different adaptive control, image processing and pattern recognition problems. From 1990 to 1995, he was with the University of Newcastle, Newcastle; Rutherford Appleton Laboratory, Didcot; Centre for Mathematics and Computer Science, Amsterdam and Institute National de Recherche en Informatique et en Automatique, Rocquencourt working on several image analysis and pattern recognition projects. In 1995 he rejoined the Institute of Information Theory and Automation where he is head of the Pattern Recognition department. His current research interests are random fields applications in pattern recognition and image processing and automatic acquisition of virtual reality models. He is the author of about 250 research papers published in books, journals and conference proceedings.
Institute of Information Theory and Automation
Academy of Sciences of the Czech Republic
Jiri Philip received the MSc degree in technical cybernetics and the PhD degree in artificial intelligence and biocybernetics from the Czech Technical University in Prague in 2002 and 2006, respectively. He is currently with the Pattern Recognition Department at the Institute of Information Theory and Automation of the AS CR, Praha, Czech Republic. Between 2002 and 2007, he was a researcher at the Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic. Between 2007-2008, he was a postdoctoral Marie Curie research fellow in the Texture Lab at the School of Mathematical and Computer Sciences, Heriot-Watt University. His current research is focused on analysis, modeling, and human perception of high-dimensional texture data and video sequences.
The methodology of colour texture modelling in computer
vision, computer graphics and virtual reality applications
will be presented. The problem will be introduced in the
wider context of modelling multi-spectral images and videos
which can be accomplished either by a multi-dimensional
mathematical models or sophisticated sampling methods
from the original measurement space. The tutorial will focus
on the former. The main aspects of the problem, i.e., different
multi-dimensional data models with their corresponding
benefits and drawbacks, optimal model selection, parameter
estimation and model synthesis techniques will be discussed.
Special attention will be devoted to recent trends
towards Bidirectional Texture Function (BTF) modelling,
i.e., textures which do not obey Lambertian law, whose reflectance
is illumination and viewing angle dependent and
recently represent the best known texture representation. The
techniques covered will include efficient Markov random
field-based algorithms, intelligent sampling algorithms, reflectance
models and problems with their possible implementation
using contemporary graphics cards programming.
The objectives are to bring participants up to date on the
state-of-the-art methodology of texture modelling. This tutorial
is intended as a hands-on knowledge event for practitioners
wishing to become more familiar with this important
research area, its methods, and their critical analysis useful
for variety of practical applications.
- Topics Covered
- Problem Formulation, Modeling Taxonomy
- Markov Random Field Model-Based Approaches - Numerically Efficient Methods
- Mixtures Based Approach
- BTF Textures Modelling Approaches
- Applications of Texture Models
Read more ...
Coloring Image Search (CANCELED)
Theo Gevers (th.geversuva.nl)
Faculty of Science
University of Amsterdam
Theo Gevers is an Associate Professor of Computer Science at the
University of Amsterdam, The Netherlands and an ICREA Research
Professor at the Computer Vision Center (UAB), Barcelona, Spain.
At the University of Amsterdam he is a teaching director of the
MSc of Artificial Intelligence. He currently holds a VICI-award
(for excellent researchers) from the Dutch Organisation for
Scientific Research. His main research interests are in the
fundamentals of content-based image retrieval, colour image
processing and computer vision specifically in the theoretical
foundation of geometric and photometric invariants. He is an
associate editor for IEEE Transactions on Image Processing. He is
co-chair of the Internet Imaging Conference (SPIE 2005, 2006),
co-organizer of the First International Workshop on Image
Databases and Multi Media Search (1996), the International
Conference on Visual Information Systems (1999, 2005), the
Conference on Multimedia & Expo (ICME, 2005), and the European
Conference on Colour in Graphics, Imaging, and Vision (CGIV,
2012). He is guest editor of the special issue on content-based
image retrieval for the International Journal of Computer Vision
(IJCV 2004) and the special issue on Colour for Image Indexing
and Retrieval for the journal of Computer Vision and Image
Understanding (CVIU 2004). He has published over 130 papers on
colour image processing, image retrieval and computer vision. He
is program committee member of a various number of conferences,
and an invited speaker at major conferences. He is a lecturer of
post-doctoral courses given at various major conferences (CVPR,
ICPR, SPIE, CGIV). He is member of the IEEE.
Joost van de Weijer
Computer Vision Center
Universitat Autonoma de Barcelona
Joost van de Weijer is a Ramon y Cajal fellow at the Computer
Vision Center in Barcelona. He received his M.Sc. degree in
applied physics at Delft University of Technology in 1998. In
2005, he obtained the Ph.D. degree at the University of
Amsterdam. During 2005-2007 he was a Marie Curie Intra-European
Fellow in the LEAR team at INRIA Rhone-Alpes in France. He is
currently involved in research on the application of color to
bag-of-word approaches for object recognition, image
classification and image retrieval. Joost van de Weijer research
has focused primarily on the application of color to computer
vision. Color information is both investigated from a physical
perspective as from a human vision viewpoint. He has made
contributions to color constancy, color feature detection, color
feature extraction, and color saliency theory. More recently he
has performed research on the application of learning techniques
to solve more complex color imaging problems, such as the
automatic learning of color names from image search engines and
top-down color constancy.
Lucassen Colour Research
Marcel Lucassen received an M.S. degree in Technical Physics from
Twente University (The Netherlands) in 1988 and a Ph.D. in
Biophysics (color constancy) from Utrecht University in 1993. In
the period 1993-2007 he worked with Akzo Nobel Coatings and TNO
Human Factors. He is now a freelance color scientist (Lucassen
Colour Research, www.lucr.nl) and holds a part-time position at
the University of Amsterdam. His interests lie in basic and
applied vision research, and color vision in particular. He is an
associate editor for Color Research and Application.
The increasing capacity of digital video cameras and connectivity
of the world provides us with rapidly growing digital image/video
archives. As visual information becomes more and more available
in color format, there is an increasing demand for the use and
understanding of color information. In this tutorial, we focus on
the challenges in image search using color, present methods how
to achieve state-of-the-art performance, and indicate how to
obtain improvements in the near future. Moreover, we give an
overview of the latest developments and future trends in the
field of image search based on the Pascal VOC and TRECVID
benchmarks -- the leading benchmarks for image and video
- Topics Covered
Problem statement: social, business, and scientific,
Course organization: image processing fundamentals, image concept detection, image
and video retrieval, evaluation.
- Low-level: Interest Point and Region Detection
Invariance and color constancy: the sensory and semantic gap,
Color models and fusion: representation,
Interest points: color vs intensity,
Region descriptors: SIFT and color SIFT.
- High-level: Concept Detection and Image Search
Concept detection: compact feature representations, kernel-based supervised learning,
the model gap,
Classifier fusion: supervised and unsupervised methods,
Search engine architectures: component optimization, process-optimization.
Large-scale concept detection: annotation efforts, detector performance,
Benchmarks: data, tasks, and results,
Benchmark criticism: broad-domain applicability, repeatability,
Resources: annotations, baselines, and software,
Concluding remarks: achievements and discussion,
Future work: challenges and opportunities for the image processing community.
Bart M. ter Haar Romeny (B.M.terHaarRomenytue.nl)
Eindhoven University of Technology and Maastricht University Department of Biomedical Engineering
Bart M. ter Haar Romeny received the MSc degree in Applied
Physics from Delft University of Technology in 1978. He spent 4
months at UC Berkeley in the lab of prof. Lawrence Stark, and
acquired his Ph.D. from Utrecht University in 1983 in biophysics.
Subsequently, he became principal physicist of the Utrecht
University Hospital Radiology Department and (1986-1989) project
leader of the Dutch PACS project. He was co-founder and associate
professor at the Image Sciences Institute (ISI) of Utrecht
University (1989-2001). From 2001, ter Haar Romeny holds the
chair of Biomedical Image Analysis at the Department of
Biomedical Engineering of Eindhoven University of Technology and
Maastricht University. He closely collaborates with Philips
Healthcare and Philips Research, several other industries and
(national and international) hospitals and research groups.
His research interests include quantitative medical image
analysis, its physical foundations and clinical applications. His
interests are in particular the mathematical modeling of the
brain (visual perception) and applying this knowledge in
operational computer-aided diagnosis systems. He authored an
interactive tutorial book on multi-scale computer vision
techniques, edited a book on non-linear diffusion theory in
computer vision and is involved in (resp. initiated) a number of
international collaborations on these subjects. He founded the
conference series on Multi-Scale Image Analysis. He is author of
over 90 refereed journal papers, 8 books and book chapters, 75
refereed proceedings contributions and holds 2 patents. He is
reviewer for many journals and conferences. He is on the
editorial board of the Journal of Mathematical Imaging and
Vision. For 6 years, ter Haar Romeny has been a member of the
Program Planning Committee of the European Congress of Radiology
(Vienna, 18.000 participants), responsible for the computer
applications section. He is an active teacher (best BME MSc
teacher award 2008 and 2009) and has presented dozens of keynote
The tutorial consists of 4 lectures of 45 minutes.
It is a tutorial in effective algorithm design for medical imaging.
All examples will be taken from medical image analysis
Image analysis is the extraction of useful information from
images. To design useful algorithms a powerful language for
geometric reasoning is needed. In this tutorial we focus on
differential geometry with multi-scale ('scale-space')
differential operators. We show everything interactively in the
new Mathematica version 7.
- Topics Covered
- Introduction on the relevance of multi-scale image analysis
- Introduction of first order gauge coordinates, giving a powerful
framework for differential invariant features to high order. We
derive operators for corners, vesselness, colon polyp detection,
and T-junction detection.
- Design of geometry-driven diffusion algorithms, by incorporation
of proper reasoning of the task. We present elegant derivations
of Perona and Malik, Euclidean shortening flow, and coherence
enhancing diffusion. All with short-code live demonstrations.
- Multi-scale analysis of optic flow. We introduce the multi-scale
Horn & Schunck equation, and show how high order dense flow
fields can be extracted, for the calculation of e.g. strain and
strain rate in the ventricular wall.
- Deep multi-scale structure of images. We discuss the notion of
edge focusing, the multi-scale watershed algorithm and how the
so-called 'toppoints' can be effectively used for image
retrieval, and image matching.
Read more ...
Joni-Kristian Kamarainen (Joni.Kamarainenlut.fi)
Lappeenranta University of Technology
Professor Kamarainen is the vice director of Machine Vision and
Pattern Recognition laboratory in Lappeenranta University of
Technology, Finland, and the principal investigator of
Computational Vision Group. Some of his main research interests
are Gabor filter based features and he has published almost 30
frequently cited conference and journal articles related to the
theory and applications of Gabor features.
2D Gabor filters have maintained their popularity as a successful and
general feature extraction method in computer vision and image processing
for almost three decades. The original article of Nobel laureate Dennis
Gabor dates back to 1946, but the most cited is Prof John Daugman's famous
article in 1985, which introduced the 2D Gabof filter - 25 years ago.
During the 00's the research activity on Gabor features has again
increased according to IEEE Xplore database. The most important reason
is their remarkable success in emerging application areas, such as
biometric authentication. Gabor feature based Iris code is The Method
for iris recognition (Daugman 2006), Gabor methods have continuously
outperformed other competitors in large scale face recognition contests
(e.g. the two best methods in the ICPR 2004 contest), and provide
state-of-the-art accuracy in fingerprint matching (Jain et al. PAMI 2007)
and face detection (Hamouz et al. PAMI 2005). Even the old adage of their
correspondence to simple cells in the visual cortex has recently been
resurrected (Serre et al. PAMI 2007). Since their invention Gabor features
have succeeded in numerous applications, and therefore, are important and
general tools every computer vision and image processing scientist should
In this tutorial we explain the principles why still, after 25
years, features based on Gabor filters provide remarkable results in many
problems and applications of computer vision and image processing. Our
tutorial covers the theory, practical issues and state-of-the-art applications,
and we provide free source code for Gabor feature extraction (Matlab M-files).
- Topics Covered
- Today & Future
2. Principles - "Theory of Communication"
- Theory of Communication - Two Domains
- Gabor filter
3. Gabor features
- Original idea revised
- Multi-resolution Gabor features
- Main Idea and Justification
- Main Properties
2. Feature Construction
- Direct Utilisation
- Analytical Approach
- Learning Approach
3. Multi-resolution Gabor feature - ``Simple Gabor feature space''
- Local Feature
- Practical Considerations
1. Usage of Gabor Filters
- Important Properties
2. Face recognition - Gabor jets and elastic bunch graph matching
3. Iris recognition - Daugman's phase descriptor
- Background and main principles
- Iris code generation
- Statistical matching
4. Supervised object detection - Multi-resolution Gabor features
- Basic principle and problem statement
- Local feature descriptor and learning
- Full model including the constellation
- Selecting good hypotheses for detection
Read more ...
Game Theory in Pattern Recognition and Machine Learning
Marcello Pelillo (pelillodsi.unive.it)
Dipartimento di Informatica
Universita Ca' Foscari di Venezia
Marcello Pelillo joined in 1991 the faculty of the University of
Bari, Italy, as an assistant professor of computer science. Since
1995, he has been with the University of Venice, Italy, where he
is currently an associate professor of computer science and
serves as the chair of the board of studies of the Computer
He held visiting research positions at Yale University, the
University College London, McGill University, the University of
Vienna, York University (UK), and the National ICT Australia
Prof. Pelillo has published more than a hundred technical papers
in refereed journals, handbooks, and conference proceedings in
the areas of computer vision, pattern recognition and neural
computation. He has been actively involved in the organization of
several scientific meetings including the NIPS*99 Workshop on
"Complexity and Neural Computation: The Average and the Worst
Case," the 2008 International Workshop on Computer Vision
and the ICML 2010 Workshop on
"Learning in non-(geo)metric spaces." In 1997, he co- established
a new series of international conferencess devoted to energy
minimization methods in computer vision and pattern recognition
(EMMCVPR), which has now reached the seventh edition.
He was a guest coeditor of four journal special issues: two for
IEEE Transactions on Pattern Analysis and Machine Intelligence
and two for Pattern Recognition, the last one, in 2006, being
devoted to "similarity-based pattern recognition."
He serves on the editorial board for the journals IEEE
Transactions on Pattern Analysis and Machine Intelligence and
Pattern Recognition, and is regularly on the program committees
of the major international conferences and workshops of his
He is (or has been) scientific coordinator of several research
projects, including SIMBAD, an EU-FP7 project devoted to
similarity-based pattern analysis and recognition (http://simbad-
fp7.eu). Prof. Pelillo is a Fellow of the IAPR and a Senior
Member of the IEEE.
Dipartimento di Informatica
Universita Ca' Foscari di Venezia
Andrea Torsello received his PhD in computer science at the
University of York, UK. Since 2007 he is assistant professor at
Ca' Foscari University of Venice, Italy. In 2007 he held a
visiting research position at the Information Technology Faculty
of Monash University, Australia.
His research interests are in the areas of computer vision and
pattern recognition, in particular, the interplay between
stochastic and structural approaches as well as game-theoretic
Dr. Torsello has published over 50 technical papers in refereed
journals and conference proceedings and has been in the program
committees of various international conferences and workshops. In
2009 he co-chaired GbR, a well-established IAPR workshop on
Graph-based methods in Pattern Recognition, and he will be
cochairing GbR 2011.
He was a guest coeditor for a special issue for Pattern
Recognition, devoted to "similarity-based pattern recognition,"
which was printed in 2006. He is currently acting as a guest
coeditor for a special issue for Computer Vision and Image
Understanding devoted to "graph based representations in pattern
A classical and natural strategy to attack pattern recognition
problems consists of formulating them in terms of optimization
problems. Here, a plausible (global) objective function is first
derived (often heuristically) in an attempt to quantify the
gqualityh of a solution (e.g., a cluster or a partition of the
input data). Then, an algorithm is developed which aims at
finding global optima of the objective function. The main merit
of optimizationbased techniques is their ability of providing (by
definition) a quantitative measure of a solution's quality. In
many real-world situations, however, the complexity of the
problem at hand is such that no single objective function would
satisfactorily capture its intricacies. Game theory was developed
precisely to overcome the limitations of single-objective
optimization (von Neumann and Morgenstern, 1944). It aims at
modeling complex situations where players make decisions in an
attempt to maximize their own (mutually conflicting) returns.
Nowadays, game theory is a well-established field on its own and
offers a rich arsenal of powerful concepts and algorithms
(Fudenberg and Tirole, 1991; Weibull, 1995). Its main point is to
shift the emphasis from (global) optimality criteria to
In pattern recognition and machine learning there has been a long
thread of the use of game theory for its ability of integrating
multiple sources of information, ranging from the integration of
visual cues for image analysis and segmentation (Bozma and
Duncan, 1992; Bozma and Duncan, 1994; Chakraborty and Duncan,
1999; Yu and Berthod, 1995) to the integration of
classifiers/predictors through regret minimization (Cesa-Bianchi
and Lugosi, 2006) to the use of coalitional games for feature
selection and tracking (Cohen, Dror, and Ruppin, 2007; Dowdall,
Pavlidis, and Tsiamyrtzis, 2007). These game-theoretic
integration approaches have seen a recent surge in interest in
the machine learning community due to their links with boosting
(Freund and Schapire, 1996). The ability of finding an
equilibrium among multiple gcompetingh cues has also seen
strong application in contextual pattern recognition (Hummel and
Zucker, 1983; Miller and Zucker, 1991; Miller and Zucker, 1992;
Sastry, Phansalkar, and Thathachar, 1994) and has recently been
used as the basic definition of the notion of a gclusterh for
unsupervised and semi-supervised classification (Pelillo, 2009;
Torsello, Rota Bulo, and Pelillo, 2006; Rota Bulo and Pelillo,
2009; Pavan and Pelillo, 2007).
With the recent development of algorithmic game theory (Nisan et
al., 2007; Shoham and Leyton-Brown, 2009) the interest in the
machine learning, pattern recognition and signal/image processing
communities around gametheoretic models and algorithms is growing
at a fast pace (see, e.g., the NIPS 2005 Workshop on "Game
theory, machine learning and reasoning under uncertainty," the
2007 Machine Learning special issue on "Learning and
computational game theory," and the two 2009 special issues of
the IEEE Signal Processing Magazine and the EURASIP Journal of
Advances in Signal Processing on "Game theory in signal
processing and communications"). From a practical perspective,
problems recently tackled with game]theoretic or related methods
include: image and video segmentation (Pavan and Pelillo, 2007;
Torsello, Rota Bulo, and Pelillo, 2006), analysis of functional
magnetic resonance images (Muller et al., 2007; Neumann et al.,
2005; Neumann et al., 2006), content]based image retrieval (Wang
et al., 2008), image matching (Albarelli et al., 2009; Todorovic
and Ahuja, 2008), object tracking (Dowdall, Pavlidis, and
Tsiamyrtzis, 2007; Gualdi et al., 2008), detection of anomalous
activities in video streams (Hamid et al., 2005; Hamid et al.,
2006), human action recognition (Wei et al., 2007).
- Topics Covered
1. Introduction to game theory
- What is a game?
- Mixed strategies, expected payoffs, and Nash equilibria.
- Other equilibrium concepts (evolutionary stable strategies, correlated equilibria)
- Complexity and algorithmic issues (including "graphical games")
2. Game equilibria and pattern recognition
- Polymatrix games and contextual pattern recognition
- Nash equilibria and clustering (dominant sets)
- Transductive inference
3. Repeated games for inference and prediction
- Boosting with scalar utility and the minimax theorem
- Regret minimization and Blackwell's approachability theorem
- Fictitious play and Bayesian inference
- Feature selection
- Image/video segmentation and medical image analysis
- Content-based image retrieval
- Matching, in-outlier detection, detection of anomalous behavior
You may download tutorial notes.
Similarity Searching: Indexing, Nearest Neighbor Finding, Dimensionality Reduction, and Embedding Methods for Applications in Multimedia Databases
Hanan Samet (hjsumiacs.umd.edu)
Department of Computer Science
University of Maryland
Hanan Samet is a Professor of Computer Science at the University
of Maryland, College Park. He is a member of the Computer Vision
Laboratory of the Center for Automation Research and also has an
appointment in the University of Maryland Institute for Advanced
Computer Studies. At the Computer Vision Laboratory he leads a
number of research projects on the use of hierarchical data
structures for geographic information systems.
His research group has developed the QUILT system which is a GIS
based on hierarchical spatial data structures such as quadtrees
and octree, the SAND system which integrates spatial and non-
spatial data and provides a spatial browser to visualize the
underlying data, the VASCO system of JAVA applets for visualizing
and animating spatial constructs and operations on the world wide
web (http://www.cs.umd.edu/~hjs/quadtree/index.html), and the
MARCO system for map retrieval by content which consists of a
sophisticated pictorial query specification method. He received
his Ph.D. in Computer Science from Stanford University in 1975.
During that time he was a Research Assistant at the Stanford
Artificial Intelligence Project. His doctoral dissertation dealt
with proving the correctness of translations of LISP programs.
He has written over 300 papers
(http://www.cs.umd.edu/~hjs/hjsyear.html). He is the author of
the recent book titled "Foundations of Multidimensional and
Metric Data Structures" (http://www.mkp.com/multidimensional)
published by Morgan-Kaufmann, an imprint of Elsevier, in 2006, an
award winner in the 2006 best book in Computer and Information
Science competition of the Professional and Scholarly Publishers
(PSP) Group of the American Publishers Association (AAP), and of
the first two books on spatial data structures titled "Design and
Analysis of Spatial Data Structures", and "Applications of
Spatial Data Structures: Computer Graphics, Image Processing,
and GIS", both published by Addison-Wesley in 1990.
He is an Area Editor of "Graphical Models", and on the Editorial
Board of "Computer Vision and Image Understanding", Journal of
Visual Languages", and "GeoInformatica". He served as the co-
general chair of the 15th and 16th ACM International Symposium on
Advances in Geographic Information Systems (ACM GIS 2007 and ACM
He is the founding chair of the ACM Special Interest Group on
Spatial Information (SIGSPATIAL). He is a Fellow of the ACM,
IEEE, and IAPR (International Association for Pattern
Recognition), and a Science Foundation of Ireland (SFI) E. T. S.
Walton Fellow (2009). He was elected to the ACM Council in 1989-
1991 where he served as the Capital Region Representative. He is
the recipient of the 2009 UCGIS Research Award.
He received best paper awards in the 2008 SIGMOD Conference, the
2008 SIGSPATIAL ACMGIS'08 Conference, and the 2007 Computers &
Graphics Journal. His paper at the 2009 IEEE International
Conference on Data Engineering (ICDE) was selected as one of the
best papers for publication in the IEEE Transactions on Knowledge
and Data Engineering.
Similarity searching is a crucial part of retrieval in multimedia databases used
for applications such as pattern recognition, image databases, and content-based
retrieval. It involves finding objects in a data set S that are similar to a
query object q based on some distance measure d which is usually a distance
metric. The search process is usually achieved by means of nearest neighbor
finding. Existing methods for handling similarity search in this setting fall
into one of two classes. The first is based on mapping to a low-dimensional
vector space which is then indexed using one of a number of different data
structures such as k-d trees, R-trees, quadtrees, etc. The second directly
indexes the objects based on distances making use of data structures such as the
vp-tree, M-tree, etc. The process of mapping from a high-dimensional space into
a low-dimensional space is known as dimensionality reduction. There are a number
of techniques of achieving dimensionality reduction including representative
points, SVD, and DFT. At times, when we just have distance information, the data
objects are embedded in a vector space so that the distances of the embedded
objects as measured by the distance metric in the embedding space approximate
the actual distances. Once a satisfactory embedding has been obtained, the
actual search is facilitated by making use of conventional indexing methods,
perhaps coupled with dimensionality reduction. Some commonly known embedding
methods are multidimensional scaling, Lipschitz embeddings, and FastMap. This
tutorial is organized into five parts that cover the basic concepts outlined
above: indexing low and high dimensional spaces, distance-based indexing,
dimensionality reduction, embedding methods, and nearest neighbor searching. It
is based in part on the book titled "Foundations of Multidimensional and Metric
Data Structures" by Hanan Samet, published
by Morgan-Kaufmann, an imprint of Elsevier, in 2006.
- Topics Covered
Part A: Indexing low and high dimensional spaces
1. Quadtree variants
2. K-d tree
5. Bounding sphere methods
a. Sphere tree
6. Methods based on decreasing the fanout
a. TV tree
b. Hybrid tree
7. Methods based on Voronoi diagrams: OS-tree
8. Pyramid technique
9. Methods based on a sequential scan
Part B. Distance-based indexing
a. Distance metrics
b. Properties for pruning the search
2. Ball partitioning methods
3. General hyperplane partitioning methods
6. Distance matrix methods
Part C: Dimensionality reduction
1. Curse of dimensionality
2. Pruning property and contractiveness
3. Using only one dimension
4. Representative point methods
5. Singular value decomposition (SVD, PCA, KLT)
6. Discrete Fourier transform (DFT)
Part D: Embedding methods
1. Problem statement
2. Multidimensional scaling (MDS)
3. Lipschitz embeddings
Part E: Nearest neighbor finding
1. Classical methods such as branch and bound
2. K nearest neighbors
3. Incremental nearest neighbor finding
a. General method
b. Permitting duplicate instances of objects
4. Approximate nearest neighbor finding
5. Probably approximately correct (PAC) nearest neighbor finding
6. Furthest neighbor finding
We are Building a Topological Pyramid
Walter G. Kropatsch (krwprip.tuwien.ac.at)
Pattern Recognition and Image Processing Group
Institute of Computer Aided Automation
Vienna University of Technology
Walter G. Kropatsch is full professor at Vienna University of
Technology since 1990. His interest in image pyramids goes back
to 1984 when he spent one year at the Center for Automation
Research of the University of Maryland on invitation of Prof.
Azriel Rosenfeld. Since then he explored different variants of
hierarchical data and processing structures. In collaboration
with Peter Meer, Annick Montanvert and Jean-Michel Jolion he
extended the scope of pyramids to graphs and then to plane graphs
for which the first proof of topology preservation could be
shown. His current interest are in the extension of the pyramidal
concept towards dynamical hierarchical description of the 3D
moving objects in their environment and its derivation from one
or more 2D image sequences. In this high dimensional context,
topology receives more importance. Prof. Kropatsch served the
IAPR in many positions and was its president from 2004 to 2006.
Together with J.-M. Jolion he initiated the IAPR TC15 on Graph-
based Representations in 1996.
Ecole nationale superieure d'ingenieurs de Caen
Professor Luc Brun got a PhD on topological segmentation
in 1996, an assistant professor position in 1998 and a professor
position at the engineering school ENSICAEN in 2004. Its main
research areas concern hierarchical segmentation with topological
models and structural pattern recognition. He designed together
with Walter Kropatsch the model of combinatorial pyramids which
provide several advantages over previous models. Indeed, such a
model encode explicitely the orientation of the plane thus
providing a richer description of the image content, he may be
implicitely encoded thus providing an efficient encoding of the
whole pyramid. His current work in these field aims to extend
this framework to any dimensions. He is currently the head of
the image team of the GREYC laoratory and the chairman of the
Vision sensors observe 3D objects in a dynamic environment.
Objects consist of several connected 3D parts and
these parts can be connected in different ways:
rigidly, articulated, smoothly deformable.
In most cases objects move independently and smoothly.
This 3D scene topology is projected into the 2D image topology
where noise and occlusions and the enormous amount of data
introduce further difficulties.
We plan to elaborate the concept of the topological pyramid from the
classical, regular image pyramids by means of examples. We review the
classical concepts of Gaussian and Laplacian pyramids, and their
application to segmentation: pyramid linking. Participants will
explore cases where the topology of the classical results do not
conform to the scene topology. At the transition to the irregular
pyramids was the idea to consider the treatment of the hierarchical
structure and the content separately but in a synchronous way. We will
discuss in detail the basic concept of dual graph pyramids and
combinatorial pyramids and show results for connected component
analysis and segmentation. We will also discuss their main properties
among which the preservation of the image topology, its connected
components and holes. We will finally conclude this lecture on the
extension of the above framework to arbitrary dimensions.
- Topics Covered
One main characteristic of this lecture will be its emphasis on
interactions with the audience through many exercises. These
exercises will be mainly based on two initial image: One binary image
with a small bridge (similar to the classical example of Bister etal.)
and a hole and one small 3x3 image encoding two partitions.
After a short review of the pyramid framework we will study a first
example (with exercises) illustrating the effect of sampling on the
topological relationships (mainly the adjacency). This example will be
based on a map of the roman empire superposed with few regular
grids. The audience will have to compute adjacency relationships
deduced from the grid to get the intuition of the loss of information
induced by the sampling.
The second exercise aims to illustrate the loss of topological
information within a non overlapping regular pyramid. The audience
will have to build manually a small regular pyramid with the base
image composed of a hole and a small bridge between two large
blobs. The audience will be decomposed into three groups each group
having an initial image slightly shifted compared to the two other
ones. The comparison of the results of the different groups will
illustrate the shift variance of regular pyramids.
The third example illustrates the basic concepts of Laplacian
pyramids on the same binary image. Rewriting rules replace
difference between levels usually performed on grey level images.
The fourth exercise provide an explanation of properties and
limitations of overlapping pyramids. Using still the same example as
above the three groups have to build a 4x4/4 pyramid on the binary
image using appropriate rewriting rules. The loss of the connectivity
information will be illustrated by computing the down projection of
We next provide the basics of the irregular dual graph
pyramid framework and explain their construction scheme (contraction
kernel, dual simplification kernel). This construction scheme is
illustrated on the same basic image as above in a problem of connected
component labeling. The audience have to use small contraction
kernels. Small kernels allow variations between intermediate results
but all participants should obtain the same final result with a
correct encoding of connected components and holes. We further
plan to subdivide the base graph into smaller subgraphs each of
which will be processed independently by different groups.
the individual results will be merged in a final step of the exercise.
We then present the combinatorial map framework (definitions, main
properties). This small section ends on an exercise where participants
have to build the permutations of one combinatorial map and its dual from a
single example. The audience is divided in two groups one group
working with a drawing of the primal graph while the other group works
on its dual. Both groups should obtain the same results thus
illustrating the fact that the dual operation is idempotent.
The next section is devoted to the construction scheme of combinatorial
pyramids and to the connection between levels encoded by connecting
walks. The audience has to build on a 3x3 image a small combinatorial
pyramid made of five levels including: the base level combi. map, two
intermediate contraction steps and two simplified versions of the
contracted combinatorial maps. Since such a computation may lead to many
calculus the reduced combinatorial maps is provided with only some
missing elements which have to be computed from the level below using
connecting walks. Both primal and dual graph are provided and the
audience will be invited to check results obtained on one combinatorial map
on its dual.
The next slides are devoted to the extension of connecting walks to
several levels. This extension is called a connecting dart
sequence. After some definitions and basic properties of this object,
the audience is invited to compute a few connecting dart sequences using
the connecting walks previously computed.
Given the notion of connecting dart sequence we explain the basic idea
of the folding and unfolding of combinatorial pyramids. This last
section on combinatorial pyramids is concluded by an exercise where
the base level combinatorial map is drawn with different colors
indicating the level of either contraction or removal of the different
elements. The audience will be first invited to retrieve few of the
connecting dart sequences previously computed directly from the base
using these colors. The second exercise will consist to build the top
level combinatorial map directly from the base still using the colors
Given the basic construction scheme and properties of dual graph and
combinatorial pyramids we review the main methods used to build such
pyramids, their main application fields and the preservation of the
topology by such pyramids.
The lecture concludes on the extension to 3D of such pyramids.
You may download tutorial notes.
Introduction to GPU Computing; GPUs for Computer Vision
Edmondo Orlotti (Introduction to GPU Computing, 1 hr)
Micha Feign (GPUs for Computer Vision, 2 hrs)
Introduction to GPU Computing
Graphics chips started as fixed function graphics pipelines. Over the years, these graphics chips became increasingly programmable, which led NVIDIA to introduce the first GPU or Graphics Processing Unit. Computer scientists in particular, along with researchers in fields such as medical imaging and electromagnetics started using GPUs for running general purpose computational applications. They found the excellent floating point performance in GPUs led to a huge performance boost for a range of scientific applications. This was the advent of the movement called GPGPU or General Purpose computing on GPUs. This 1 hour introduction will help to understand the ecosystem that has been built to leverage GPU processing power.
GPUs for Computer Vision
GPU computing has emerged in recent years as a powerful computing tool that can
provide amazing performance, reaching multi tera-flop in a single desktop PC.
Many computer vision algorithms are well-suited for harnessing the power of the
GPU as they map really well to massively parallel architectures.
Techniques previously limited to off-line experimentation or expensive
supercomputers can now be deployed for real-time use in consumer machines.
CUDA, NVIDIA's parallel computing architecture enables dramatic increases in
computing performance on the GPU.
This talk aims to familiarize computer vision researchers with the emerging and
exciting area of fast computer vision algorithms on the GPU.
In this talk we introduce GPU computing and CUDA with an emphasis on computer
vision on the GPU and highlight some features especially well suited towards
We'll show CUDA based examples of computationally intensive computer vision
algorithms enabled for real-time use on the GPU.
Finally we'll conclude with a discussion of interesting future directions and
exciting opportunities for research and products.
|Deadline for tutorial proposals
||Feb 15, 2010
|Notification of acceptance of tutorials
||Mar 30, 2010
|ICPR 2010 tutorials - full day
||Aug 22, 2010
Call for Tutorials