Matrices calculations on partial shape matching

Question

I'm working in a shape recognition project where it is supposed for me to develop an application that receives two images: an original one and a sketch made by a user. I am supposed to detect contours of the two images and find the best match in the original image corresponding to the sketch made by the user.

I already have the contours of the image and sketch and I need to find the best match of the sketch in the image, disregarding translation, rotation, scaling and occlusion.

I've searched some of the literature on this subject and found this paper (http://www.icg.tugraz.at/Members/donoser/donoseraccv2009pdf) that seems very promising to accomplish what I want. In Java, I have succeeded in calculating the shape descriptors (matrix of angles between points), however i'm having trouble understanding how the matching algorithm is supposed to work.

On section 2.3, they state that we have two matrices, A1 with size M x M and A2 with size N x N and that for this example, M <= N. They explain that "In terms of comparing two descriptor matrices this equals to finding r×r sized blocks starting at the main diagonal elements A1(s,s) and A2(m,m) of the two descriptor matrices which yield a small angular difference defined by:"

"And to find such blocks all different matching possibilities and chain lenghts have to be considered and the brute-force method becomes inefficient for larger number of points."

Then, they say they use N integral images (that I've already understand how they work) each of size M x M are built for N descriptor difference matrices:

Here is where I am lost. What does n mean? And for example, if M=4 and N=5, how do you create 5 integral images of size 4 x 4 with different data? This notation is strange to me and I can't figure out what they are explaining. Is that how they calculate the integral images?

Maybe I'm just on a dumb day and can't figure this out without bumping my head on the wall :P Anyhow, I would be very grateful for someone who enlightens me and explains this to me like I'm 5 years old.

Thank you for your attention.

Answer 1

n appears to be a free parameter in the equation for M^{n}_D. That is, this equation is defining N difference matrices for n=1:N, quoting from the paper:

"The difference matrices M^{n}_D represent the N possibilities to match the point sequences onto each other."