Matrices calculations on partial shape matching

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.

• – gnat
Commented Dec 10, 2014 at 14:20
• On those two sites, users said that the question was at the wrong place. That's why I posted here. Commented Dec 10, 2014 at 14:22
• Maybe it is best to delete the questions on the other places? I guess Programmers SE could be the most correct place to ask this question. Commented Dec 10, 2014 at 14:33
• Already deleted the questions on the other places. Is anybody able to help me understand this algorithm? Commented Dec 10, 2014 at 23:25