Contours matching - finding contours displacement

I found contours on two images with same object and I want to find displacement and rotation of this object. I've tried with rotated bounding boxes of this contours and then its angles and center points but rotations of bounding boxes don't tell about contour rotation correctly because it's the same for angles a+0, a+90, a+180 etc. degrees. Is it any other good way to find rotation and displacement of contours? Maybe some use of convex hull, convexity defects? I've read in Learning OpenCv about matching contours but it hasn't helped. Could someone give some example?

Examples:

I want to detect for example pink square, and in the second case pen. Other examples could be squares with some holes, stars etc. As I said I want to make some uniwersal thing. Any suggestions are appreciated because I want to test as many methods as it's possible.

• Picture would help here Nov 24, 2011 at 18:32
• I want to make some universal function. So as test picture can be anything. Simple shaped element as rectangle, or little more complex shaped. Nov 25, 2011 at 10:07
• Well, you can't fit single method to all cases. Practical method depend on contrast range, noise estimation, background and shape itself - it's smoothness, topology etc.That's why picture would help. Nov 25, 2011 at 17:23

Do you have to worry about a difference in scale between contours? If not than you can simply find the centroid of each contour, and compute displacement by subtracting one from the other. Then you can calculate the principal axes of the contours, and find the rotation angle between them.

If scaling is involved, then you can calculate the scale factor by taking the ratio of the corresponding principal axes.

• Yes scale can also differ. I thought also about something similar to freeman chains from opencv making freeman chains of each contour and then comparing them and trying to find translaton some way, but I can't figure out some good algorithm for it. Nov 23, 2011 at 19:29
• It's same as creating minimum rotated bounding box and taking its rotation and displacement. Tried this approach and the results are unsatisfying. So I think this method isn't good at all. Nov 24, 2011 at 8:06
• Can you be more specific as to why that didn't work? Are contours only related by translation, rotation, and scaling, or can they be deformed in other ways? Some pictures really would help. If you need to handle non-affine transformations or random noise, you might try the shape context. Let me know, I can point you to some papers.
– Dima
Nov 25, 2011 at 22:08
• They are only related by translation, rotation and scaling, deformations are connected to little different contour detection on different photos. Shape context? Could you expand this? Nov 26, 2011 at 10:11
• @kzych It looks like your biggest problem here would be noise in the edge detection. How do you find the minimum rotated box? I am still not clear why that doesn't work right. Shape context is a way of representing a contour. The details are here: en.wikipedia.org/wiki/Shape_context
– Dima
Nov 30, 2011 at 17:34

If you don't have to worry about scale or projective distortions chain codes may help here. If you have chain codes of approximately same shape with the same scale you can find translation with one-dimensional FFT phase correlation http://en.wikipedia.org/wiki/Phase_correlation

If you have to take into account projective distortion you may also consider possibility of using feature points (like corners) instead of contours.

• Any advice how to build good chain code? Mayby something from OpenCv (as far as I know it only has freeman chains)? For now I'm building chain codes using each contour point and calculating angle to x axis of neighbours points, but maybe there is some better idea? If you have reference to any good papers about chains it would be appreciated. Nov 28, 2011 at 9:13

In the question you say

As I said I want to make some uniwersal thing

but I am afraid it's quite difficult to find a "universal" solution to the problem.

You can buy a commercial available pattern locator software and integrate it in your application, usually they perform quite well for a wide range of applications. Just to give you an idea this is the reference manual for such a product http://www.lmi3d.com/sites/default/files/support/4.2.0.70-hexsight_user_guide.pdf

Also, you can develop an ad hoc solution for some particular case (for example for the pen in your image).

Otherwise you can study hard the problem, starting from the very basic foundations rooted in computational geometry (http://www.cs.sunysb.edu/~algorith/files/shape-similarity.shtml), where your "contours" are called "polygon", reading stuff like:

M. de Berg, O. Devillers, M. Kreveld, O. Schwarzkopf, and M. Teillaud. Computing the maximum overlap of two convex polygons under translations. Theoretical Computer Science, 31:613–628, 1998.

and

H. Ahn, O. Cheong, C. Park, C. Shin, and A. Vigneron. Maximizing the overlap of two planar convex sets under rigid motions. Computational Geometry: Theory and Applications, 37:3–15, 2007.

and ending with "Hierarchical Real-Time Recognition of Compound Objects in Images" by Markus Ulrich who collaborates with MVTec, another software house selling object recognition software tools.