# Best distance measure to use

### Context

I have two sets of data that I want to compare. Each data element in both sets is a vector containing 22 angles (all between $-\pi$ and $\pi$). The angles relate to a given human pose configuration, so a pose is defined by 22 joint angles.

What I am ultimately trying to do is determine the "closeness" of the two sets of data. So for each pose (22D vector) in one set, I want to find its nearest neighbour in the other set, and create a distance plot for each of the closest pairs.

### Questions

• Can I simply use Euclidean distance?
• To be meaningful, I assume that the distance metric would need to be defined as: $\theta = |\theta_1 - \theta_2| \quad mod \quad \pi$, where $|...|$ is absolute value and mod is modulo. Then using the resulting 22 thetas, I can perform the standard Euclidean distance calculation, $\sqrt{t_1^2 + t_2^2 + \ldots + t_{22}^2}$.
• Is this correct?
• Would another distance metric be more useful, such as chi-square, or Bhattacharyya, or some other metric? If so, could you please provide some insight as to why.
-
As a side note: I don't think you mean $|\theta_1 - \theta_2| \mod \pi$. Rather something like $\min\{|\theta_1 - \theta_2|, 2 \pi - |\theta_1 - \theta_2|\}$. – Erik P. Feb 4 '11 at 23:16
Rather than working with angles, I suggest converting to (x, y)-coordinates on the unit-circle first. You can then calculate normally (distances and the like), and averaging isn't a problem like with angles. – caracal Feb 4 '11 at 23:19
@Josh Erik P.'s suggestion is a good one. Alternatively, consider each angle $\theta$ to be a point $\left(\cos(\theta), \sin(\theta)\right)$ on the unit circle and compute the Euclidean distances between them using the usual (Pythagorean) formula. The difference between these distances and the angular distances shouldn't matter. (I believe this may be what Caracal suggested, too.) – whuber Feb 5 '11 at 2:34
@Josh The average of, e.g., $\pi/4$ and $7\pi/4$ is $\pi$. In many circumstances, this doesn't make sense, and it should be $0$ instead. In your specific situation, this might not be an issue since maybe human joints don't have a range of motion past $\pi$. Also, in your case, maybe you want the aforementioned average to be $\pi$ since the joint motion is uni-directional. @whuber's suggestion is exactly what I meant. – caracal Feb 5 '11 at 10:45
Your problem will probably become much easier to solve if you can specify the consequences of "getting it wrong". So if you say the data sets are the same or similar, but they in fact aren't, what will happen to you? Will it depend on "how wrong" your decision was? What will happen if you declare the data/poses different, but they are in fact the same or similar? What is lost? answering these questions will help determine what matters for the comparison you want to make. This ensures that you are answering the right question. – probabilityislogic Feb 5 '11 at 13:39

What are you trying to do with the nearest neighbor information?

I would answer that question, and then compare the different distance measures in light of that.

For example, say you are trying to classify poses based on the joint configuration, and would like joint vectors from the same pose to be close together. A straightforward way to evaluate the suitability of different distance metrics is to use each of them in a KNN classifier, and compare the out-of-sample accuracies of each of the resulting models.

-

you can calculate the covariance matrix for each set and then calculate the Hausdorff distance between the two set using the Mahalanobis distance.

The Mahalanobis distance is a useful way of determining similarity of an unknown sample set to a known one. It differs from Euclidean distance in that it takes into account the correlations of the data set and is scale-invariant.

-

This sounds like it is similar to a certain application of Information Retrieval (IR). A few years ago I attended a talk about gait recognition that sounds similar to what you are doing. In Information Retrieval, "documents" (in your case: a person's angle data) are compared to some query (which in your case could be "is there a person with angle data (.., ..)"). Then the documents are listed in the order of the one that matches the closest down to the one that matches the least. That, in turn, means that one central component of IR is putting a document in some kind of vector space (in your case: angle space) and comparing it to one specific query or example document or measuring their distance. (See below.) If you have a sound definition of the distance between two individual vectors, all you have to do is coming up with a measure for the distance of two data sets. (Traditionally in IR the distance in vector space model is calculated either by the cosine measure or Euclidean distance but I don't remember how they did it in that case.) In IR there is also a mechanism called "relevance feedback" that, conceptually, works with the distance of two sets of documents. That mechanism normally uses a measure of distance that sums up all individual distances between all pairs of documents (or in your case: person vectors). Maybe that is of use to you.

The following page has some papers that seem relevant to your issue: http://www.mpi-inf.mpg.de/~mmueller/index_publications.html Especially this one http://www.mpi-inf.mpg.de/~mmueller/publications/2006_DemuthRoederMuellerEberhardt_MocapRetrievalSystem_ECIR.pdf seems interesting. The talk of Müller that I attended mentions similarity measures from Kovar and Gleicher called "point cloud" (see http://portal.acm.org/citation.cfm?id=1186562.1015760&coll=DL&dl=ACM) and one called "quaternions". Hope, it helps.

-
 It would be useful to have the reference if you are able to find it. Thanks. – Josh Jul 5 '11 at 14:04

This problem is called Distance Metric Learning. Every distance metric can be represented as $\sqrt{(x-y)^tA(x-y)}$ where $A$ is positive semi-definite. Methods under this sub-area, learn the optimal $A$ for your data. In fact, if the optimal $A$ happens to be an identity matrix, it is okay to use euclidean distances. If it is the inverse covariance, it would be optimal to use the Mahalanobis distance, and so on and so forth. Hence, a distance metric learning method must be used to learn the optimal $A$, to learn the right distance metric.

-

One problem with using the angles as a proxy for shape is that small perturbations in the angles can lead to large perturbations in the shape. Further, different angle configurations could result in the same (or similar) shape.

-