9.4 Quadratic Penalty Method for Hypergraph Matching在线视频

Hi, everyone.

Welcome to modern optimization methods.

Today we will introduce the fourth part

of chapter nine,

hypergraph matching problems,

as well as the quadratic penalty method.

Now in this part,

we will begin with introducing the hypergraph

matching problem,

then we introduce the relaxation problem,

finally,

we apply the quadratic penalty method

to solve this problem.

Then we conclude this part.

Now let's first take a look at

what is graph matching.

So the idea of graph matching is that

you got two images or multi-images.

We try to match them together.

For example,

got this point,

may corresponds to this point here.

So you try to match

the corresponding points

in two images together.

So the black box here

is actually the graph matching algorithm.

The graph matching problem

has many applications in computer vision.

For example,

in recognition,

we can apply this to face recognition,

action recognition, and tracking.

In retrievial,

we can retrieve the object

or motion from a figure.

This is the application of the graph matching.

If we take a detailed look at

how this graph matching works,

it actually contains several steps here.

Let me explain it one by one.

At the very beginning step,

we input two images,

and these are the images that we want to match,

then we use some algorithms

to select the point or pixels.

These points, or pixels,

are representative points in the figure.

After that,

we do feature extraction,

the feature extraction basically means that

we need to extract meaningful features

from the pixels or points here,

and we need to evaluate some initial feature evaluations

in this part.

Finally, with the stages before.

The fourth part is that

we build optimization models

to do the graph matching algorithm.

Then the final output is that

we put the two figures or images

and we match them together.

By pointing some feature points

to another pixel or point.

This is the main stage

for the graph matching.

Here the mathematical model,

or the optimization model part

is what we're going to focus on.

We assume that the three stages before are already

executed for us then we try to

focus on the fourth step.

The aim of graph matching

is that we try to match two sets of points

by some mathematical model.

So this is the aim of graph matching.

Now let's take a look at hypergraph matching.

Compared to graph matching,

hypergraph matching uses more information between points,

we start with graph matching.

In graph matching,

we may use point-to-point matching information,

meaning that we build up some correspondence

between points from one group

to another point in the other group,

we have some matching score called Ai1i2.

If we use pair-to-pair matching,

then we can include the distance matrix information.

So if we pick up two points in one set

and we match this edge with the other edge

in the other set,

then we can include the distance information

to do the matching.

And for hypergraph matching,

we actually have hyperedges in each set.

For example,

we take triple-to-triple matching as an example.

We can pick up three points in one set,

and this will construct a triangle,

and then we match this triangle to

another triangle in the other set,

then they will get a matching score.

By using the hyperedge,

which contains more than two points,

then we can include more information

such as angle information,

as well as rotation and stretch.

By using more information,

we can improve the matching performance

or matching result.

Now

let's take a look at the mathematical formulation

for hypergraph matching.

So we are given hypergraph G1 and G2,

each G contains a set of points V1 and V2,

they are sets of points

representing that they collect the points

in the figure, actually.

For example,

V1 contains four points,

and V2 contains five points.

We try to match the points

between the two sets.

And for the edges E1 and E2,

they are sets of hyperedges.

So what is hyperedges?

As you may recall,

that for each edge,

it is actually connecting two points,

that's called an edge.

For hyperedge,

it contains more points.

As I mentioned before,

for 1, 2, 3, the three points,

it contains a hyperedge.

For example,

(1,2,3) in E1 is a hyperedge,

and (a,b,c), if it is contained in E2,

then it is also a hyperedge.

Now the aim here is that

we try to find an assignment matrix X,

where this X

is in n1×n2-dimensional space.

So each of its element

is defined in the following.

If it is one,

then it means that the l1 point

is assigned to l2 point in V2.

If they are not assigned,

then it is zero.

In other words,

in order to measure the assignment,

we introduce an assignment matrix X

which is either zero or one.

And the row of X

is actually the number of points in V1,

and the column of X is actually the number of elements in V2.

Now let's take a look at hypergraph matching.

Matching of hyperedges how

we represent this.

If two hyperedges are matched,

it means the following way that

the X(l1l2)X(j1j2)X(k1k2)=1.

In this sense,

we can see that l1 is matched to l2,

and k1 is matched to k2,

and j1 is matched to j2.

So we can find the correspondence,

otherwise,

then they are not matched.

For matching score,

this B is defined as the matching score

between l1, j1, k1 and l2, j2, k2.

So assume that

they have a correspondence,

then they got a matching score

with six indices below.

Because for each hyperedge

you got three indices,

so the matching score between two hyperedges

they got six indices.

We have some assumptions

that for all the hyperedges in the edge set,

the corresponding matching score is nonnegative.

If either of the edges

is not in the hyperedges,

then we will set it as zero.

In our hypergraph matching optimization model,

we assume that this B is available.

As we can see that,

this B got sixth indices,

therefore it is the sixth order tensor.

Now let's take a look at the mathematical formulation

for hypergraph matching.

So given the hypergraph G1 and G2,

as well as the matching score B,

we are trying to find the correspondence

between the feature sets V1 and V2.

So this is the aim of our problem.

The objective is that we try to make

the sum of the matching scores

achieve the maximum.

So this is the objective.

In other words,

we can put it in terms of optimization problem,

we try to maximize the sum of the matching score

such that this matrix X is an assignment matrix.

So what is assignment matrix?

It basically means that for each point in the left hand side,

it can only be assigned to one unique point

in the other set.

So this is assignment matrix.

If we put the assignment matrix

in mathematical formulation,

it basically says that

for each row of this matrix X,

the sum of this row must be one.

And also,

X is in zero and one,

X is either zero or one.

We refer to this as an assignment matrix

or assignment constraints.

So this is the mathematical formulation

for the problem.

As you can see that it is actually very complicated

because you got so many indices in the variable.

And also the matching score matrix.

Next,

let's consider a special case

that if you got the left hand side and right hand side

the same size of feature points,

then the constraints reduce to a more complicated one.

That you have the sum of row is one,

as well as the column of X is also one.

In other words,

when you got the same size of feature points

for V1 and V2,

then each point on the left hand side

can only be matched to one point in the other set.

Conversely,

it is also the same.

Therefore,

we got two constraints,

for the special case n1 equals n2.

Now

let's first try to reduce or reformulate this problem

into a vector case.

Recall that the variable at the moment is the matrix,

we transform this matrix X

into a vector x by putting each row of X

as a block in the vector x.

So each row here,

if we do a transformation,

we put it as a one block in this x.

After that,

we have some calculations for the indices xj

corresponding to the elements in X.

Similarly,

we can transfer the sixth order tensor

into a three order tensor by the same calculation.

Then the problem can be transferred

to a more neat form

that you got a three order tensor Aljkxlxjxk,

so the sum of them.

We also transfer it into a minimization problem

by adding a minus.

So this is the objective function.

And the constraints,

now we transfer it into vector x,

so the constraint is transferred to each block of x,

they will have the sum to be one.

And then for each x,

it is either zero or one.

So the constraint is also equivalent to the previous one.

Therefore,

this is the hypergraph matching problem.

If we take a look at this problem,

how can we solve it to get the matching?

There are some difficulties.

The first difficulty is that this problem is a 0-1 programming,

meaning that it is an integer programming.

Integer programming,

in general,

it is NP hard problem,

meaning that solving this problem is not that easy.

So we have to be very careful to design the algorithm.

There are some traditional methods to solve it,

including basically four types.

One is the power iteration algorithm.

The second is the Reweighted Random Walks method.

The third one is the

projected successive projecting method.

The last one is the Block Coordinate Ascent method.

So the four methods can be summarized into two types.

The first type is that we relax the 0-1 integer constraint

into an interval,

or box constraint between zero and one.

Therefore,

the problem will reduce to a relaxation

continuous optimization problem.

And then we solve the relaxation problem,

after that,

we do truncation to get an optimal solution.

The second way is to reduce the original problem

to a series of small size of assignment problems.

By doing this,

they keep the 0-1 constraints,

however,

the size of the problem is reduced.

Let's make a brief summary about this part.

In this part,

we basically introduce the hypergraph matching problem,

as well as its mathematical reformulation.

We also review the existing methods to solve it.

In the next part,

we will show

how we apply the quadratic penalty method

to solve this problem.

We stop here and see you next time.