Matching

Overview

We will describe here the comparison between two shapes, which is the next logical step to our goal, the image database. We will derive a measure (not in the mathematical sense) for polygonal arcs, representing parts of our curve. With this measure, the comparison of the whole shapes is built up by finding the optimal combination of arcs, using dynamical programming.

If you are not interested in details, you can skip the formal description and continue with results.

Formal Description

As seen in previous chapters, the shape is represented as a digital polygonal curve, which is then decomposed into a set of maximal convex (or concave) arcs.

Definitions:
We denote:

s_i: a digital line segment
curve C=(s₀,...,s_ns): the polygonal digital curve, representing the shape, consisting of (ns+1) line segments.
ns: number of segments in C minus one
We decompose the curve C into maximal convex/concave arcs ma:
ma_i=(s_start,...,s_end), start>=0, end<=ns: a maximal convex (or concave) arc. Two consecutive max. arcs ma_i, ma_i+1 intersect in one line segment: s_end(ma_i) = s_start(ma_i+1)
na: number of max. arcs in the decomposed representation of C minus one
l(ma_i): length of ma_i

Comparison of two curves C₁, C₂

To compare curves, we compare the arcs the curves are composed of.

We derived a measure for arc comparison, for details click here.

It is not possible, to make a simple one to one comparison of maximal convex/concave arcs ma, due to the following reasons:

The curves may consist of a different number of maximal arcs
Even similar shapes may have different (small) features

Hence we join together maximal arcs, forming groups:

Definition:
A group g is a polygonal subarc of the curve C, consisting of the segments of consecutive maximal arcs:

g:=(s_start,...,s_end), start>=0, end<=ns,
where

s_start is the first segment of a maximal arc ma_i
s_end is the last segment of a maximal arc ma_j, j>i

We will call the decomposition of a curve C into groups a grouping G:

Definition:
A grouping G is an ordered set of consecutive groups, covering the whole curve C:
G:=(g₀,...,g_ng) where

ng is the number of groups in G minus one
Two consecutive groups intersect in one line segment:
s_end(g_i) = s_start(g_i+1)
The whole curve is covered:
s_start(g₀) =s_end(g_ng) =s_start(C)

Definition:
We denote the set of all possible groupings G of a curve C as SG(C).

Given two curves C₁,C₂ their comparison can be defined as a mapping on a special subset of groupings SG₁,SG₂, called the correspondence:
Definition:
We call a relation CO on SG₁ x SG₂ a correspondence if:

(G₁,G₂) is in CO <==> #G₁ = #G₂, where #G_i denotes the number of groups in G_i (#G_i = ng(G_1,2))

(G₁,G₂) is in CO ==> min(#g_j(G₁) , #g_j(G₂) = 1 for all j=0..ng(G_1,2)
The first condition means that both curves are decomposed into the same amount of groups,
the second condition means, that at least one group in the decomposition of both curves having the same index contains exactly one maximal arc, the other group contains at least one maximal arc.
The reason herefore is, that in the following comparison, we only want to allow mappings between one to many arcs or many to one arcs, but never between many to many arcs.
This rule has an intuitive motivation:

if you compare a curve with its image in a higher stage of abstraction, every single arc in the higher stage should exactly match to the arcs it originated of.
maximal convex arcs determine visual parts, hence the correspondence guarantees preservation of visual parts.

At least, the comparison between the curves:
Definition:
Given two curves C₁,C₂, we define a mapping GM on the correspondence CO, called the groupmatching:
GM:

CO -> R

(G₁,G₂) -> sum_i=0..ng of (D(g_i(G₁),g_i(G₂)), where ng=ng(G₁) = ng(G₂) and
D(g_i(G₁),g_i(G₂)) is the arc-comparison of the groups.

For a description of the arc-comparison click here.

With these definitions, we can easily formulate the task for comparison:

Find the element BE in the correspondence CO such that the groupmatching is minimal, i.e. GM(BE)<=GM(e) for all elements e in CO.

Note that the grouping takes respect of the order of groups, and hence of the order of the digital segments. This means, that in every element (G₁,G₂) in CO the first groups g₀(G₁) and g₀(G₂) always contain the first digital segment of their corresponding curves.
This leads to the problem, that for an intuitive groupmatching the correct starting point must be found. We will come later to the solution of this problem.

Finding the best comparison

As seen in the previous chapter, finding the best comparison is the solution of finding an element in the correspondence that minimizes the groupmatching. This problem can be solved by finding the cheapest path in a graph in a sense described in this chapter.

We will explain the strategy by a special example, see curve right. The two fishlike shapes are decomposed into three maximal arcs each. We want to find the minimal correspondence (intuitively we expect that the best correspondence is a one to one mapping of each maximal arc).

The figure on the left shows the correspondence CO between the left fish (a), which is composed of the arcs a₀ to a₃, and the right one (arcs a₀ to a₃).

CO consists of all possible combinations of groupings that hold the conditions stated in its definition above.

We assign a value to each of the nine elements of CO by the groupmatching.

Finding the best comparison be explained by the following graph:

The vertices, denoted by D(g₁,g₂) are assigned to the arcmeasure, given by the comparison of the groups g₁,g₂.
The nodes are denoted by the indices of arcs matched so far by travelling from the starting node to them
The groupmatching of an element in CO can be computed by travelling from the starting node to the endnode (0123,0123), taking the vertices corresponding to the groups and adding their values D(g₁,g₂)

An example:
Let's take the upper right element in the correspondence. The grouping of each curve consists of three groups:

group 0: a₀ for curve a, b₀ for curve b
group 1: a₁ for curve a, b₁,b₂ for curve b
group 2: a₂,a₃ for curve a, b₃ for curve b

hence our way on the graph will lead

through vertex D(0,0) to node (0,0),
through vertex D(1,1 2) to node (01,012),
through vertex D(2 3, 3) to node (0123,0123),

the groupmatching is given by adding D(0,0), D(1,1 2), D(2 3, 3).

Hence to get the best comparison is the task to find the cheapest way in the graph.

This is typically solved by dynamical programming.

Continue with Results

Matching

Overview

Formal Description

Comparison of two curves C1, C2

Finding the best comparison

Comparison of two curves C₁, C₂