Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!milano!cadillac!sunshine!finn
From: finn@sunshine.cad.mcc.com (Chris Finn)
Newsgroups: comp.graphics
Subject: Re: 3D shape fitting
Summary: correlate first then measure
Keywords: 3D SHAPE ANALYSIS
Message-ID: <3419@cadillac.CAD.MCC.COM>
Date: 20 Oct 89 13:57:12 GMT
References: <134@adam.ua.oz>
Sender: news@cadillac.CAD.MCC.COM
Reply-To: finn@MCC.COM (Chris Finn)
Organization: MCC CAD Program, Austin, TX
Lines: 45

In article <134@adam.ua.oz> gtravan@adam.ua.oz (george travan dentistry) writes:
>
>you can imagine a mesh with a hill and another mesh with a trough, how can
>you determine how close they can be made to correspond?
>
>i hope this makes sense...
>
I tried to email a response but it bounced so I'll post this and
maybe someone can add more concrete info.

	From what I understand you are trying to devise a 
measure of the similarity or dissimilarity of two shapes.
For instance if you have two functions (or discrete samples
of two functions) of one independent variable (y=f1(x) & y=f2(x) )
you don't want to just measure the vertical distance between
them f1(x)-f2(x), and you don't want to measure the perpendicular
distance between them. You want to first correlate the features
you see in one function with the corresponding features in the other 
function and then measure the difference between them in the direction 
in which the correlation is a maximum. In a sense one function is a 
stretched or contracted, and possibly amplified version of the other. 
	These kinds of similarity measures are used on one 
dimensional functions in speech recognition. The computer receives
a digitized version of the spoken word and tries to match it against
words in its vocabulary library. 
	I think similar techiques are used for two dimensional 
signals when interpolating between two images. For instance, an
artist draws a cartoon but doesn't want to draw all 24 frames
per second (or whatever it is). He draws the picture at two instances
which are seperated by a larger gap in time and the computer fills
in the missing images. I think this would be more like your case,
where, from what I understand, you want to measure the distance 
between z=f1(x,y) and z=f2(x,y).
	I don't have any references handy but if you have an 
engineering library at your disposal look up "speech recognition" and in
particular "time warping" or "dynamic time warping" you can 
quickly hunt down these algorithms for the one-dimensional case.

Hope this helps,


Chris Finn
MCC CAD Program, P.O. Box 200195, Austin, TX 78720 [512] 343-0978
ARPA: finn@mcc.com
UUCP: {uunet,harvard,gatech,pyramid}!cs.utexas.edu!milano!cadillac!finn