Pattern Recognition

Jürgen Beyerer, Matthias Richter, Matthias Nagel

• Publisher: De Gruyter Oldenbourg
• Year: 2017
• Print ISBN: 9783110537932
• eBook ISBN: 9783110537963
• Edition: 1
• Topic: Computer Science
• Subtopic: Artificial Intelligence (AI) & Semantics
• Index: Computer Science

The book offers a thorough introduction to Pattern Recognition aimed at master and advanced bachelor students of engineering and the natural sciences. Besides classification - the heart of Pattern Recognition - special emphasis is put on features, their typology, their properties and their systematic construction. Additionally, general principles that govern Pattern Recognition are illustrated and explained in a comprehensible way. Rather than presenting a complete overview over the rapidly evolving field, the book is to clarifies the concepts so that the reader can easily understand the underlying ideas and the rationale behind the methods. For this purpose, the mathematical treatment of Pattern Recognition is pushed so far that the mechanisms of action become clear and visible, but not farther. Therefore, not all derivations are driven into the last mathematical detail, as a mathematician would expect it. Ideas of proofs are presented instead of complete proofs. From the authors' point of view, this concept allows to teach the essential ideas of Pattern Recognition with sufficient depth within a relatively lean book.

Mathematical methods explained thoroughly
Extremely practical approach with many examples
Based on over ten years lecture at Karlsruhe Institute of Technology
For students but also for practitioners

1Fundamentals and definitions

The aim of this chapter is to describe the general structure of a pattern recognition system and properly define the fundamental terms and concepts that were partially used in the Introduction already. A description of the generic process of designing a pattern recognizer will be given and the challenges at each step will be stated more precisely.

1.1Goals of pattern recognition

The purpose of pattern recognition is to assign classes to objects according to some similarity properties. Before delving deeper, we must first define what is meant by class and object. For this, two mathematical concepts are needed: equivalence relations and partitions.

Definition 1.1 (Equivalence relation). Let Ω be a set of elements with some relation ∼. Suppose further that o, o1, o2, o3∈Ω are arbitrary. The relation ∼ is said to be an equivalence relation if it fulfills the following conditions:

1.Reflexivity: o∼o.

2.Symmetry: o1∼o2⇔o2∼o1.

3.Transitivity: o1∼o2 and o2∼o3⇒o1∼o3.

Two elements o1, o2 with o1∼o2 are said to be equivalent. We further write [o]∼⊆Ω to denote the subset

$\left[0\right]=\left\{o^{\prime }\in \Omega |o^{\prime }~o\right\}\left(1.1\right)$

of all elements that are equivalent to o. The object o is also called a representative of the set [o]∼. In the context of pattern recognition, each o∈Ω denotes an object and each [o]∼ denotes a class. A different approach to classifying every element of a set is given by partitioning the set:

Definition 1.2 (Partition, Class). Let Ω be a set and ω1, ω2, ω3, . . . ⊆Ω be a system of subsets. This system of subsets is called a partition of Ω if the following conditions are met:

1.ωi ∩ ∩ ωj = 0 for all i ≠ j, i.e., the subsets are pairwise disjoint, and

2.ωi = Ω, i.e., the system is exhaustive.

Every subset ω is called a class (of the partition).

It is easy to see that equivalence relations and partitions describe synonymous concepts: every equivalence relation induces a partition, and every partition induces an equivalence relation.

The underlying principle of all pattern recognition is illustrated in Figure 1.1. On the left it shows—in abstract terms—the world and a (sub)set Ω of objects that live within the world. The set Ω is given by the pattern recognition task and is also called the domain. Only the objects in the domain are relevant to the task; this is the so called closed world assumption. The task also partitions the domain into classes ω1, ω2, ω3, . . . ⊆Ω. A suitable mapping associates every object oi t to a feature vector mi ∈ M inside the feature space M. The goal is now to find rules that partition M along decision boundaries so that the classes of M match the classes of the domain. Hence, the rule for classifying an object o is

Fig. 1.1. Transformation of the domain Ω into the feature space M.

$\omega \left(0\right):={\omega }_i\text{if}\text{m}\left(0\right)\in {\mathcal{R}}_i.\left(1.2\right)$

This means that the estimated class ̂ω(o) of object o is set to the class ωi i if the feature vector m (o) falls inside the region Ri. For this reason, the Ri are also called decision regions. The concept of a classifier can now be stated more precisely:

Definition 1.3 (Classifier). A classifier is a collection of rules that state how to evaluate feature vectors in order to sort objects into classes. Equivalently, a classifier is a system of decision boundaries in the feature space.

Readers experienced in machine learning will find these concepts very familiar. In fact, machine learning and pattern recognition are closely intertwined: pattern recognition is (mostly) supervised learning, as the classes are known in advance. This topic will be picked up again later in this chapter.

1.2Structure of a pattern recognition system

In the previous section it was already mentioned that a pattern recognition system maps objects onto feature vectors (see Figure 1.1) and that the classification is carried out in the feature space. This section focuses on the steps involved and defines the terms pattern and feature.

Fig. 1.2. Processing pipeline of a pattern recognition system.

Figure 1.2 shows the processing pipeline of a pattern recognition system. In the first steps, the relevant properties of the objects from Ω must be put into a machine readable interpretation. These first steps (yellow boxes in Figure 1.2) are usually performed by methods of sensor engineering, signal processing, or metrology, and are not directly part of the pattern recognition system. The result of these operations is the pattern of the object under inspection.

Definition 1.4 (Pattern). A pattern is the collection of the observed or measured properties of a s...

Table of contents

• Cover
• Title Page
• Copyright
• Preface
• Contents
• List of Tables
• List of Figures
• Notation
• Introduction
• 1 Fundamentals and definitions
• 2 Features
• 3 Bayesian decision theory
• 4 Parameter estimation
• 5 Parameter free methods
• 6 General considerations
• 7 Special classifiers
• 8 Classification with nominal features
• 9 Classifier-independent concepts
• A Solutions to the exercises
• B A primer on Lie theory
• C Random processes
• Bibliography
• Glossary
• Index