Interactive Fréchet Distance Visualization
date
Nov 23, 2023
slug
fid_online
status
Published
summary
Walk the walk and walk the dog
tags
Algorithms
Visualization
type
Post
The question
Imagine that you have 2 curves in a 2-D space, how would you measure the similarity of these 2 curves?
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