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.

  • On those two sites, users said that the question was at the wrong place. That's why I posted here.
    – jmvieira
    Commented Dec 10, 2014 at 14:22
  • 1
    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.
    – jmvieira
    Commented Dec 10, 2014 at 14:33
  • Already deleted the questions on the other places. Is anybody able to help me understand this algorithm?
    – jmvieira
    Commented Dec 10, 2014 at 23:25

1 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."

  • Let's continue with an example of two matrices A1 with size MxM (M=4) and A2 with size NxN (N=5). What you are saying is that you create 5 difference matrices by subtracting A2(n:n+M-1,n:n+M-1) to A1(1:M,1:M), being the values of A2 (1:4,1:4) - (2:5,2:5) - (3:6,3:6) - (4:7,4:7) - (5:8,5:8). Right? But if the matrix is of size 5x5, only the first two ranges are possible to calculate, right? Am I understanding this wrong?
    – jmvieira
    Commented Dec 11, 2014 at 14:49
  • I've already understood how this works. The authors forgot to mention that the notation in A2(n:n+M-1,n:n+M-1) is about the A(K) circular shifts as mentioned in section 2.2. The integral images are created by applying a circular shift to the A2 matrix, and then calculate the differences between A1 and A2. Hope this helps someone in the future! And also, thanks @Stu for providing the best explanation to my question ;)
    – jmvieira
    Commented Jan 20, 2015 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.