Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2010, Cesme, Izmir, Turkey, August 18-20, ... (Lecture Notes in Computer Science, 6218)

✍ Scribed by Edwin R. Hancock (editor), Richard C Wilson (editor), Terry Windeatt (editor), Ilkay Ulusoy (editor), Francisco Escolano (editor)

• Publisher: Springer
• Year: 2010
• Tongue: English
• Leaves: 773
• Category: Library

✦ Synopsis

This volume in the Springer Lecture Notes in Computer Science (LNCS) series contains the papers presented at the S+SSPR 2010 Workshops, which was the seventh occasion that SPR and SSPR workshops have been held jointly. S+SSPR 2010 was organized by TC1 and TC2, Technical Committees of the International Association for Pattern Recognition(IAPR), andheld inCesme, Izmir, whichis a seaside resort on the Aegean coast of Turkey. The conference took place during August 18–20, 2010, only a few days before the 20th International Conference on Pattern Recognition (ICPR) which was held in Istanbul. The aim of the series of workshops is to create an international forum for the presentation of the latest results and exchange of ideas between researchers in the ?elds of statistical and structural pattern recognition. SPR 2010 and SSPR 2010 received a total of 99 paper submissions from many di?erent countries around the world, giving it a truly international perspective, as has been the case for previous S+SSPR workshops. This volume contains 70 accepted papers, 39 for oral and 31 for poster presentation. In addition to par- lel oral sessions for SPR and SSPR, there were two joint oral sessions of interest to both SPR and SSPR communities. Furthermore, to enhance the workshop experience, there were two joint panel sessions on “Structural Learning” and “Clustering,” in which short author presentations were followed by discussion. Another innovation this year was the ?lming of the proceedings by Videol- tures.

✦ Table of Contents

Title Page
Preface
SPR and SSPR 2010
Table of Contents
Invited Talks
From Region Based Image Representation to Object Discovery and Recognition
Introduction
Regions as Image Features
Segmentation Tree and Region Descriptors
Learning Object Properties
Object Discovery as Graph Matching
Region-Based Object Model
Results
Qualitative Evaluation – Segmentation
Qualitative Evaluation – Model
Quantitative Evaluation
Conclusions
References
Learning on Manifolds
Topological Spaces
Distance on Riemannian Manifolds
Space of Nonsingular Covariance Matrices
Region Covariance Descriptor and Pattern Search
Computing Mean on Riemannian Manifolds
Object Model Update
Computing Kernel Density
Motion Detection
Linear Regression on Riemannian Manifolds
Affine Motion Tracking
Pose Invariant Detection
Classifiers on Riemannian Manifolds
Local Maps and Boosting
LogitBoost on Riemannian Manifolds
Object Detection
Conclusions
References
Classification and Trees
References
Structural Patterns in Complex Networks through Spectral Analysis
Introduction
Background
Local Patterns: Subgraph Centrality
Global Patterns
Structural Classes of Networks
Communicability and Communities in Networks
Conclusions
References
Structural Descriptions
Graph Embedding Using an Edge-Based Wave Kernel
Introduction
Embedding Graphs into Pseudo Riemannian Manifolds
Edge-Based Wave Equation
The Embedded Coordinates Matrix
Edge-Based Eigenvalues and Eigenfunctions
Pseudo Euclidean Space
Distance Function
An Orthonormal Basis
Projection into a 2D Subspace
Hausdorff Distance
Experiments and Results
Conclusion and Future Plan
References
A Structured Learning Approach to Attributed Graph Embedding
Introduction
Graph Theory and Statistical Learning
Structured Learning
The L2-Norm
Implementation Issues
Experimental Results
RelationalMatching
Shape Categorisation
Conclusions
References
Machine Learning
Combining Elimination Rules in Tree-Based Nearest Neighbor Search Algorithms
Introduction
The Basic Algorithm
A Review of Pruning Rules
CPR: Combining Pruning Rules Algorithm
Experiments
Artificial Data with Uniform Distributions
Real World Data
Conclusions and Further Works
References
Localized Projection Learning
Introduction
Reproducing Kernel Hilbert Spaces
Projection Learning (PL)
Support Vector Machines (SVM)
Localized Projection Learning (LPL)
Comparison between SVM and LPL
Approximate Nearest Neighbors
Complexity
Experiments
Comparison of PL and LPL
Comparison of LPL and SVM
Robustness
Conclusion
References
Entropy-Based Variational Scheme for Fast Bayes Learning of Gaussian Mixtures
Introduction
Variational Bayes for Mixtures
Model Order Selection in VB: The EBVS Approach
The EBVS Split Scheme
Entropy Estimation
Experiments
Simple Densities
Overlapping Densities
Symmetric Densities
Real Data
Conclusions and Future Work
References
Structural Learning
Learning Graph Quantization
Introduction
Graph Orbifolds
Representation of Attributed Graphs
Generalized Differentiable Graph Metric
Learning Graph Quantization
LGQ
LGQ2.1
Experiments
Data
Experimental Setup
Results
Conclusion
References
High-Dimensional Spectral Feature Selection for 3D Object Recognition Based on Reeb Graphs
Introduction
Reeb Graphs
Features from Graph Spectra
Feature Selection
Mutual Information Criterion
Entropy Estimation
Experimental Setup
Results and Discussion
Classification Error
Features Analysis
The Impact of Feature Selection
Conclusions
References
Dissimilarity-Based Multiple Instance Learning
Introduction
Multiple Instance Learning in Short
Dissimilarity Representations in Short
Bag Dissimilarity Space
Point Set Distance Measures
Measures Based on between- and within Bag Instance Distances
A Second Dissimilarity Space
Experiments and Results
MUSK1 and MUSK2
Image Retrieval
Evaluation
Discussions and Conclusions
References
A Game Theoretic Approach to Learning Shape Categories and Contextual Similarities
Introduction
Disconnected Skeletons and Category Influenced Matching
Grouping Game
The Proposed Method
Discovering Shape Categories
Computing Contextual Similarities
Experimental Results
Summary and Conclusion
References
Poster Session
A Comparison between Two Representatives of a Set of Graphs: Median vs. Barycenter Graph
Introduction
Definitions
Computation of the Median Graph
Median Graph via Graph Embedding
Computation of the Barycenter Graph
Algorithm
Different Sorting Schemes
Comparison between Median and Barycenter Graphs
Algorithmical Considerations
Stability
Distance to Prototype
Conclusions
References
Impact of Visual Information on Text and Content Based Image Retrieval
Introduction
Visual and Textual Document Model
General Framework
Textual Document Model
Visual Document Model
Combining Textual and Visual Informations
Experiments
ImageCLEF: IR Collection
Evaluation Measures
Experimental Protocol
Setting Up of Our Model
Results
Learning Parameter α
Stability of Parameter α$_g$ regarding the Evaluation Measure
Global Approach vs. Local Approach: Optimizing α w.r.t. a Query
Conclusion and Future Work
References
Automatic Traffic Monitoring from Satellite Images Using Artificial Immune System
Introduction
Correlated Issues
Road Detection
Vehicle and Traffic Detection
Definition of Immunological Terms
Antibody Learning
Strategy of Detection
Results and Conclusions
References
Graduated Assignment Algorithm for Finding the Common Labelling of a Set of Graphs
Introduction
Definitions
Common Labelling Framework
The Graduated Assignment Algorithm
N-Graduated Assignment for the CL Problem
Evaluation
Conclusions and Further Work
References
Affinity Propagation for Class Exemplar Mining
Introduction
Ingredients of Our Method
Image Representation
Pairwise Graph Matching
Obtaining K-Nearest Neighbors Using RSOM Tree
Similarity Propagation Based Graph Clustering(SPGC)
Affinity Propagation Clustering
Mining Exemplars Using Three Stage Clustering
Experimental Results
Datasets
Clustering Results
Recognition Test Results
Conclusion
References
Guided Informative Image Partitioning
Introduction
Generating an Informative Image Partitioning
Use of Oversegments and Oversegment Features
Acquiring User Input
MRF-Based Region Merging
MRF Model with Edge-to-Vertex Transformation
Learning the Data Term with a Support Vector Machine
Inverse Edge-to-Node Transformation
Hierarchical Clustering
Experimental Results
Experimental Setup
Focussing Performance
Conclusions
References
Visual Alphabets on Different Levels of Abstraction for the Recognition of Deformable Objects
Introduction
Noise-Tolerant Syntactical Model
Training on Different Levels of Abstraction
Terminal Elements
Non-terminals for Object Parts
Non-terminals for Object Appearances
Non-terminal Elements for Categorisation
Data Base and Test Results
Conclusion
References
Graph Embedding Based on Nodes Attributes Representatives and a Graph of Words Representation
Introduction
Graph of Words Representation
Node Representatives
Structural Relations of Representatives
Graph of Words Embedding
Definition
Computational Issues and Potential Solutions
Experimental Setup
IAM Letter Database Generalization
COIL-100 Database Generalization
Results
A Reference System
Classification Rates
Conclusions and Future Work
References
Extracting Plane Graphs from Images
Introduction
Definitions
Construction
Segmentation
Extracting and Cleaning Up Interest Pixels
From Pixels to Pointels
Triangulation
Experiments
Losses Due to the Graph Extraction Process
Comparison with Another Plane Graph Extraction Method
Size of the Graph
Discussion, Open Questions and Conclusion
References
Indexing Tree and Subtree by Using a Structure Network
Introduction
Structure Network
Encoding a Structure
Experiments
Experimental Settings
Results
Conclusion
References
Attributed Graph Matching for Image-Features Association Using SIFT Descriptors
Introduction
Preliminaries
A Continuous Labeling Approach
A Discrete Labeling Approach
Experiments
Conclusions
References
A Causal Extraction Scheme in Top-Down Pyramids for Large Images Segmentation
Introduction
Recalls
Combinatorial Maps
Topological Maps
Tiled Top-Down Framework for Combinatorial Pyramids
A Causal Extraction Scheme for Tiled Top-Down Pyramids
Experiments
Conclusion
References
Fast Population Game Dynamics for Dominant Sets and Other Quadratic Optimization Problems
Introduction
Basics of Evolutionary Game Theory
Dominant Sets and Their Characterizations
A New Class of Evolutionary Dynamics
A Pure Strategy Selection Function
Experimental Results
Image Segmentation
Region-Based Hierarchical Image Matching
From QPs to StQPs
References
What Is the Complexity of a Network? The Heat Flow-Thermodynamic Depth Approach
Introduction
Polytopal vs. Heat Flow Complexity
Characterization of Polytopal and Flow Complexity
Characterization of Phase Transition
The Fluctuation Laws
Heat Flow - Thermodynamic Depth Complexity
Experiments: TD of PPIs
Conclusions and Future Work
References
New Partially Labelled Tree Similarity Measure: A Case Study
Introduction
Tree Comparison Methods
Definitions and Notations
Review of Tree Edit Distances
Proposed Partially Labelled Tree Comparison Algorithm
Experiments
Conclusions
References
Complete Search Space Exploration for SITG Inside Probability
Introduction
Inside Probability with SITG
Experiments
IWSLT 2009 Corpus
Hansard Corpus
Conclusions
References
Commute-Time Convolution Kernels for Graph Clustering
Introduction
Commute Time on Graph
Convolution Kernels on Graph
Experiment
Conclusion
References
Geometric Methods
Non-Euclidean Dissimilarities: Causes and Informativeness
Introduction
Dissimilarity Representations
Dissimilarity Space
Pseudo-Euclidean Embedded Space
Causes of Non-Euclidean Dissimilarity Measures
Non-intrinsic Non-Euclidean Dissimilarities
Intrinsic Non-Euclidean Dissimilarities
Informativeness
Discussion and Conclusions
References
Non-parametric Mixture Models for Clustering
Introduction
Non-parametric Mixture Model
Model Description
Estimation of Profile Matrix $Q$
Optimization Methodology
Implementation Details
Results and Discussion
Baseline Methods
Synthetic Datasets
Text Datasets
Sensitivity to Parameters
Conclusions and Future Work
References
Structural Methods for Vision
A Probabilistic Approach to Spectral Unmixing
Introduction
Probabilistic Formulation
General Unmixing Formulation
Illumination Spectrum Estimation
Endmembers from Image Reflectance
Material Association Probability Recovery
Experiments
Conclusions
References
A Game-Theoretic Approach to the Enforcement of Global Consistency in Multi-view Feature Matching
Introduction
Pairwise Geometric Consistency
Game-Theoretic Feature Matching
Experimental Results
Conclusions
References
An Algorithm for Recovering Camouflage Errors on Moving People
Introduction
Proposed Method
Experimental Results
Conclusions
References
Clustering
Semi-supervised Clustering Using Heterogeneous Dissimilarities
Introduction
Idealized Dissimilarity: Impact on Clustering Results
Learning a Combination of Dissimilarities from Equivalence Constraints
Support Vectors and KKT Complementary Conditions
Experimental Results
Conclusions
References
On Consensus Clustering Validation
Introduction
Clustering Combination
Consensus Partition Validation
Validity Measures on the Original Data Space
Validity Measures on the Clustering Ensemble Space
Validity Measures on a Similarity Space
Statistical Validity Index Based on Pairwise Similarity
Experimental Results
Conclusions
References
Pairwise Probabilistic Clustering Using Evidence Accumulation
Introduction
A Probabilistic Model for Clustering
Related Work
The Baum-Eagon Inequality
The Algorithm
Experiments
Conclusion
References
Exploring the Performance Limit of Cluster Ensemble Techniques
Introduction
Problem Statement
Experimental Settings
Metric Distance Functions
Cluster Ensemble Methods
Data Sets
Test Protocol
Experimental Results and Discussions
Extension to Weighted Cluster Ensemble Techniques
Discussions and Conclusion
References
Contour Grouping by Clustering with Multi-feature Similarity Measure
Introduction
Information Based Clustering
Contour Grouping
Multi-feature Grouping Cue
Clustering Process with Multi-feature Similarity Measure
Experimentation and Analysis
Conclusion
References
Poster Session
A Psychophysical Evaluation of Texture Degradation Descriptors
Introduction
Test Data Design
Texture Degradation Descriptors
Translation Non-invariant Features
Translation Invariant Features
Psychophysical Experiment
Perceptual Evaluation and Discussion
Conclusions
References
Content-Based Tile Retrieval System
Introduction
Tile Analysis
Colour Histograms
CAR Textural Features
CAR-Based Tile Analysis
Local Binary Patterns
Experiments
Discussion
Conclusions
References
Performance Improvement in Multiple-Model Speech Recognizer under Noisy Environments
Introduction
Multiple-Model Based Speech Recognizer
Improved Multiple-Model Based Speech Recognizer
Standards for the DSR Front-Ends
Experiments and Results
Databases and Recognition System
Results
Conclusions
References
On Feature Combination for Music Classification
Introduction
Audio Features for Music Classification
Methods for Feature Combination
Decision-Level Fusion Methods
Feature-Level Combination Methods
Recursive Feature Elimination
Experimental Results
Conclusions
References
Information Theoretical Kernels for Generative Embeddings Based on Hidden Markov Models
Introduction
HMM-Based Generative Embeddings
Hidden Markov Models
The Embeddings
Information Theoretic Kernels
Proposed Approach
Experimental Evaluation
Conclusions
References
Dynamic Linear Combination of Two-Class Classifiers
Introduction
Score Decidability Index
Dynamic Linear Combination
Other Dynamic Rules Based on Score Decidability Index
The Score Decidability Index as a normalized Score
Simplified Score Combination
Experimental Results
References
Large-Scale Text to Image Retrieval Using a Bayesian $K$-Neighborhood Model
Introduction
Approach
Parameter Selection
Computational Issues
Experiments
Corel Dataset
ImageCLEF Dataset
Conclusions
References
Maximum $a Posteriori$ Based Kernel Classifier Trained by Linear Programming
Introduction
Maximum a Posteriori (MAP) Estimation
Model Formalization
Experiment
Discussion
Conclusion
References
Improvement of the Disc Harmonic Moments Descriptor by an Exponentially Decaying Distance Transform
Introduction
Our Method
Choice of the Image Function
Overview of the Disc Harmonic Transform
DHMD Extraction Algorithm
Experiments Results
Conclusion and Perspective
References
Feature Level Fusion of Face and Palmprint Biometrics
Introduction
SIFT Keypoints Extraction
Feature Partitioning and Isomorphic Graph Representation
SIFT Keypoints Partitioning
Establishing Correspondence
Isomorphic Graph Representations
Fusion of Keypoints and Matching
Fusion of Keypoints
Matching Criterion and Verification
Experimental Evaluation and Databases
Databases
Experimental Results
Comparison with Other Technique
Conclusion
References
Scale and Rotation Invariant Detection of Singular Patterns in Vector Flow Fields
Introduction
Higher-Order Model of Flow Field
Flow Field Descriptor
Detection of Singular Patterns
Experiments
Conclusion
References
Using K-NN SVMs for Performance Improvement and Comparison to K-Highest Lagrange Multipliers Selection
Introduction
Support Vector Machine
The Proposed Method
Experimental Results
Conclusion and Discussion
References
Automatic Speech Segmentation Based on Acoustical Clustering
Introduction
The Speech Segmentation System
Coarse Segmentation
Progressive Refinement
Boundary Adjustment
Segmentation Evaluation
Experimental Results
Corpora
Coarse Segmentation
Boundary Adjustment
Conclusions
References
An Efficient Iris and Eye Corners Extraction Method
Introduction
Eye Region Extraction
Iris Extraction
Eye Corners Extraction
Eyelid Detection on the Color Segmented Eye Images
Eyelid Detection on the Grayscale Eye Images
Final Edge Map and Eye Corners Detection
Tests and Results
Conclusion
References
Dissimilarity-Based Methods
An Empirical Comparison of Kernel-Based and Dissimilarity-Based Feature Spaces
Introduction
Related Work
Experimental Results
Conclusions
References
The Dissimilarity Representation as a Tool for Three-Way Data Classification: A 2D Measure
Introduction
Three-Way Volcanic Data
Dissimilarity Representation from Three-Way Data: A 2D Measure
Experimental Results and Discussion
Conclusions
References
Regularising the Ricci Flow Embedding
Introduction
Embedding Non-Euclidean Data
Ricci Flow
Curvature Computation
The Algorithm
Regularizing Curvature
Experiments
Conclusion
References
Spherical Embedding and Classification
Introduction
Indefinite Spaces
Spherical Space
The Exponential Map
Spherical Embedding
Classifiers in the Manifold
Experimental Results
Conclusions
References
Language
Language Detection and Tracking in Multilingual Documents Using Weak Estimators
Introduction
Topic Detection and Tracking and Word of Mouth
Contributions of This Paper
Language Classification in Mono/Multilingual Documents
Weak Estimators: The SLWE
SLWE Solution to Language Detection and Tracking
The Basic Algorithm
Experimental Results
Experimental Setup
Results
Discussion and Summary of Results
Conclusion and Future Work
References
Similarity Word-Sequence Kernels for Sentence Clustering
Introduction
Kernel-Based $C$-Means Clustering
Word-Sequence Kernels
Bilingual Word-Sequence Kernels
Experiments
Conclusions and Future Work
References
Bayesian Adaptation for Statistical Machine Translation
Introduction
Related Work
Weight Optimisation in SMT
Bayesian Adaptation for SMT
Experiments
Experimental Setup
Practical Approximations
Experimental Results
Conclusions and Future Work
References
A Generative Score Space for Statistical Dialog Characterization in Social Signalling
Introduction
Mathematical Background
The Observed Influence Model
The SCP Model
The Generative Score Space
Experiments
Conclusions
References
Multiple Classifiers
A Modular Approach to Training Cascades of Boosted Ensembles
Introduction
PSL Training Framework
Positive Sample Bootstrapping
Incremental Learning with PSL
PSL Framework and Overfitting
Anti-overfitting Modifications
Method
Results
Conclusion
References
A Linear Combination of Classifiers via Rank Margin Maximization
Introduction
Margins and Ranking
Rank Margin Maximization via Linear Programming
Experiments
Conclusions and Future Works
References
Combination of Dichotomizers for Maximizing the Partial Area under the ROC Curve
Introduction
ROC Analysis and Partial Area under the ROC Curve
Linear Combination of Two Dichotomizers
Linear Combination of $K$ > 2 Dichotomizers
Experimental Results
Conclusions
References
Graphs
Ihara Coefficients: A Flexible Tool for Higher Order Learning
Introduction
Hypergraph Laplacian
Ihara Zeta Function from Graphs to Hypergraphs
Determinant Expression for Hypergraph Zeta Function
Oriented Line Graph
Characteristic Polynomial
Numerical Computation
Experimental Evaluation
Conclusion
References
A New Spectral Bound on the Clique Number of Graphs
Introduction
Bounds on the Clique Number of Graphs
The η-Bound
Computation of the η-Bound
Experiments on Random Graphs
Conclusions
References
Large Sample Statistics in the Domain of Graphs
Introduction
Representation of Attributed Graphs
The Frechet Mean
The Frechet Mean Set of Graphs
Characterization of Frechet Means
Uniqueness of Frechet Mean
A Strong Law of Large Numbers
A Central Limit Theorem
The Frechet Mean of Two Structures
Conclusion
References
Statistical Pattern Recognition
Analysis of the Multi-Dimensional Scale Saliency Algorithm and Its Application to Texture Categorization
Introduction
MDSS Based on k-Nearest Neighbour Graphs
MDSS Based on the k-d Partition Algorithm
Experimental Results
Entropy Estimation Bias
Divergence Comparison
Number of Features
Choosing a MDSS Approach
A MDSS Application: Texture Categorization
Conclusions and Future Work
References
Interactive Image Retrieval Using Smoothed Nearest Neighbor Estimates
Introduction
Relevance-Guided Interactive Image Retrieval
Nearest Neighbor (NN) Approach
Considerations about NN Estimates in CBIR
Local Searching Using Smoothed NN Estimates
Empirical Evaluation
Concluding Remarks
References
Kernel Fusion of Multiple Histogram Descriptors for Robust Face Recognition
Introduction
Histogram Features
System Fusion
Experimental Result
Conclusions
References
Structural Methods for OCR
Efficient OCR Post-Processing Combining Language, Hypothesis and Error Models
Introduction
Weighted Finite-State Transducers
Description of the Method
The Language Model (LM)
The Hypothesis Model (HM)
The Error Model (EM)
Composing LM, EM and HM
Cost Definition and Parameter Optimization
Pruning
Experiments
Conclusions
References
Rejection Threshold Estimation for an Unknown Language Model in an OCR Task
Introduction
Related Work
Approach
Modeling the Error Rate Distribution of a Language Model
Estimating the Error Rate Distribution of New Language Models
Experiments
Conclusions
References
A New Editing Scheme Based on a Fast Two-String Median Computation Applied to OCR
Introduction
Prototype Construction
Edit Distance
Fast Median String Computation
Editing Algorithm
Computational Cost Analysis
Experimental Results
Conclusions and Future Work
References
Author Index