Finding similarity between the objects ( Actually how to justify the similarity of objects in mathematics form ) I have developed a system to trace the outlines of (images of) objects. Now I want to test whether two independent traces represent a common feature.
Imagine two people (or machines) tracing the outline of a feature in an image, recording it as sequence of vertices. Inaccuracies in recognizing the feature boundaries and in specifying the vertices can be viewed as random errors in vertex positions. The problem is the two traces might use completely different (Cartesian) coordinate systems (set up on two digitizing tablets, for instance). The null hypothesis to test is that they represent a common feature.
This is illustrated below.  I drew a figure and recorded the $x$ and $y$ co-ordinates of its vertices in its coordinate system. Let's call this figure $M$.  It is represented as a sequence $(x_i,y_i), i=1, 2, \ldots, m$.
Then I drew the same figure in a bigger size in another coordinate system (with no known relationship to the first coordinates system) and recorded the $x$ and $y$ co-ordinates. Let's call this $N$, represented as a sequence $(x_i^\prime, y_i^\prime), i=1, 2, \ldots, n$.
Question:
Having these data, how can I test whether the figures $M$ and $N$ represent the same image features even though they have different sizes and co-ordinates?
If the conclusion is that yes, they do represent a common object, then how can I estimate a similarity transformation between $M$ and $N$ so that I can work on formulas or equations to check the results with different figures?

 A: There has been considerable work done in this area in the image processing community.  From a theoretical standpoint, it seems you want to compute a distance metric that given two arbitrary sequences of points determine how similar these sequences of points (vertices) are.  The problem could become much easier if you had a constrained number of shapes you were trying to match against, but you probably have already considered that work.  
For example, there is a whole host of techniques for measuring the similarity of drawn shapes and touch screen devices do this to infer what actions/letters, etc... you are drawing/requesting.  However, generally the algorithm to match what action/shape is being drawn on a device with a 3 inch screen, would be different than the algorithm used on a tablet.  To recognize that a shape drawn on a tablet is similar to a shape drawn on a smart phone is difficult due to the scale changes - as you indicate in your question.  It can be done, and this is essentially what OCR and in particular handwritten OCR attempts to do, and those techniques would help given insight into how to solve your problem.
Based on what I infer from your question you definitely need translation, scale view, and even arbitrary affine transformation invariance - is that correct.  That is, even if one of the figures is rotated by 70 degrees and sheared you want a match.   But should two ellipses always match?  Or do different ellipses need to not match?   What if there are two circles in one of your images.  Should they each match the other image or should the other image have two circles in order to match best?  
From a simple perspective, suppose you only need to match single circles vs single ellipses, then you could pretty easily distinguish between those two classes, by finding the euclidean error using the best fitting circle and ellipse.  This could be generalized to many other classes such as squares, triangles, etc... and there is much work in this area of fitting such sequences of points to various idealized shapes.   In this case notice that we are not directly comparing the two drawn shapes, but comparing each to a model and then comparing the errors of the two models.  This allows us to easily accommodate different number of points for each drawn shape.  
There is another image processing technique called SIFT - Spatial Invariance Feature Transform that computes a sparse set of points from an image - and for each of these sparse points computes the histogram of gradients around that point (at multiple scales).  This technique has a number of variants (SURF, PCA-SIFT, etc...) and has enjoyed considerable success.  You might want to look there even though in your case you do not have image data.
Handling outliers and missing data would be entirely different topics...  
