Universal typeface: how to take average of letters?

Question

In 2014, BIC launched the universal typeface experiment. It was a crowdsourcing attempt to make a universal typeface. Users could enter their written form of the letters and the experiment then took the average of all the letters of everyone who participated.

You can define a letter as a union of finite bounded (closed) curves. How would one define the average of two letters?

Remarks

Let $\gamma_1:[0,1] \rightarrow \mathbb{R}^2$ and $\gamma_2:[0,1] \rightarrow \mathbb{R}^2$ be two curves. We could naively define the average as: $$\gamma:[0,1]\rightarrow \mathbb{R}^2:x \mapsto \frac{\gamma_1(x)+\gamma_2(x)}{2}.$$ But taking a different parametrisation would give a different result. This means that this is not a good definition for an average.

One would need the obvious property that the average of $n$ copies of the same letter should yield the same letter.

Edit I included an image for how an average should look like.

(I didn't know how to tag this, so feel free to add more tags.)

Answer 1

Consider first a discrete version of the problem: You have two sets of $n$ points $\{p_1,\ldots,p_n\}$, and $\{q_1,\ldots,q_n\}$ and you want to interpolate between them, but you don't know which point should be matched with which. One way to define the best matching is to choose the one which minimizes the total distance the points have to move. This is an instance of the assignment problem, and can be solved efficiently (you can see some geometrical examples here).

The continuous analogue of this is the Wasserstein metric, if you interpret the curves as a distribution of ink on the page and minimize how far you would have to move the ink to morph one letter to the other (i.e. minimize the ink-mass-times-distance integral). Recent work in computer graphics can compute this efficiently as well:

Solomon et al., "Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains" (pdf), SIGGRAPH 2015.

See especially Figs. 12 and 13, which show shape interpolation in 2D:

On the left is what you get by interpolating images as vectors in $\mathbb R^{m\times m}$, as suggested in pre-kidney's answer.

See also another work on automatically interpolating letter shapes: Campbell and Kautz, "Learning a Manifold of Fonts", SIGGRAPH 2014.

Answer 2

Let's first consider a related problem, that of bitmapped (raster) fonts instead of vector fonts (e.g. Bezier curves or other analytical functions representing each curve, like in this problem).

In the bitmapped case, there is an obvious way to proceed. If the font image is represented by an $n\times n$ grid of pixels, then each user is specifying an element of $\{0,1\}^{n\times n}$. Take the average in the vector space $\mathbb R^{n\times n}$ to get an element of $[0,1]^{n\times n}$, and apply some sort of rounding to get back an image in $\{0,1\}^{n\times n}$.

Now let's consider the continuum analog of this. Suppose the $k^{th}$ user specifies a closed (and hence compact) subset $S_k\subset [0,1]^2$ as a union of curves (here the unit square denotes the region on which the user draws the curve). Fix $\epsilon>0$ and consider the $\epsilon$-thickening of $S_k$: this is the set $$ B(S_k,\epsilon):=\{v\in [0,1]^2\colon d(v,S_k)\leq \epsilon\}, $$ where the notation $d(v,S_k)$ denotes the minimum distance from a point in $S_k$ to $v$, with respect to the Euclidean distance.

We can take an average over the indicator functions of these thickened sets, to produce a kind of "heat map" function on $[0,1]^2$, given by $$ f(v)=\frac{\#\{1\leq k\leq N\colon v\in B(S_k,\epsilon)\}}{N}. $$ We would expect this to converge in the (theoretical) limit as $\epsilon\to 0$ and $N\to\infty$ simultaneously, but taking some small fixed $\epsilon$ would probably suffice (say $\epsilon=10^{-3}$, depending on the number of people $N$ and the desired floating point precision). Finally, apply some sort of rounding procedure. To keep things simple, let's say that an intensity greater than $\alpha\in (0,1)$ counts as that part of the region being present. Then the set describing our universal font would be $$ S_{universal}:=\{v\in[0,1]^2\colon f(v)>\alpha\}. $$ Unrolling the definitions, we could write this in the following way: $$ S_{universal}=\left\{(x,y)\in[0,1]^2\colon \#\bigl\{k\colon \min_{(u,v)\in S_k}\left[(x-u)^2+(y-v)^2\right]\leq \epsilon^2\bigr\}>N\alpha\right\}. $$ Of course, if the sets are given explicitly as a union of (simple enough) curves like lines, circles, Bezier curves, the innermost minimum could be computed as an explicit function involving square roots, cube roots, etc, and thus $S_{universal}$ itself could be described or approximated by a finite union of "nice" curves.