Interactive Fréchet Distance Visualization

date

Nov 23, 2023

slug

fid_online

status

Published

summary

Walk the walk and walk the dog

The question

Imagine that you have 2 curves in a 2-D space, how would you measure the similarity of these 2 curves?

Two random curves, how to define the similarity between them?

This question turns out to be of great importance, as it helps answer the following question:

In machine learning, generative models need to be evaluated by comparing the data likelihood of generated output vs. the training dataset

In robotics, different movement trajectories need to be compared to evaluate their performance

In geographic information systems, trajectories of road, river, movements of animals need to be compared, where a similarity measure needs to be defined

There’re some general properties we wish the distance measure to have:

Commutativity: for curve and

Translation invariant: , where is to translating all the points on by

Definition of zero:

There’re also some properties that we want for the specific case of curves:

Global instead of local: we want the distance measure to be defined in a global sense, as opposed to relying on specific points on these curve

Continuous in addition to discrete: we want the distance measure to have a natural extension to continuous curves

Insensitive to length: we don’t want the distance measure to be a function of the length of either curves

It would not be trivial to define a such measure. For example, one can naively define the weighted sum/integral of square distances between all point pairs on these curves, i.e.,

where could be a normalizing factor to normalize out the effect of length of these 2 curves (otherwise the longer curves are, the more dissimilar they will be, despite that they can be very similar). However, because a close-form solution for the length of any finite curve might not exist, it doesn’t have a nice close-form expression. Another downside is that this formulation is basically describing “on average, how distant a point in curve A is from a point in curve B”, which might not be ideal.

Consider the following 2 curves:

These 2 curves are almost parallel, except one has made a rather zigzag “detour”. If we are doing weight average, the distance between these 2 curves will be dominated by the “detour” as the “detour” takes a larger proportion in the upper curve. This might be something we want, but it neglects the fact that these 2 curves are very similar if we don’t look at the detour.

Is there a way to define a measure such that it doesn’t weight the distance so uniformly? But take into account the overall shape?

Fréchet Distance

The Fréchet Distance is mathematically defined as

In English, this is to say:

👉

Let’s suppose you are walking a dog. You are walking along curve A, the dog is walking along curve B. What’s the shortest leash that allows both you and the dog to finish the walk?

I’ve found this explanation quite fascinating, because it gives such a good intuition to an otherwise complicated mathematical definition (especially because it’s doing a min over function space).

It’s such a good explanation that I build a demo for this.

Demo

The following demo allows you to

Draw 2 arbitrary curves

Calculate the Fréchet distance automatically

Demonstrate the effect of walking a dog by sliding the slider