6
$\begingroup$

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.

universal typeface

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

$\endgroup$
  • $\begingroup$ Parametrize them both by arclength and normalize to have equal lengths? Even then you'd get ghastly results. Not to speak too generally, but averaging is just terrible. Cheers! $\endgroup$ – Matthew Conroy Mar 21 '17 at 2:36
  • 1
    $\begingroup$ @MatthewConroy What with letters you write in different amount of union of curves: the letter I can be written in 1 vertical line, but you can also add 2 horizontal lines. $\endgroup$ – Simon Marynissen Mar 21 '17 at 3:14
  • $\begingroup$ Yeah, that's a problem. Still, you could parametrize all curves of a single letter in a piecewise fashion, reparametrize by arc length, and then average just the way you indicate in your example. But that just seems like it would give awful results. What is one trying to achieve by "averaging" two letters? What features of the two letters do you want to have maintained in the average? Perhaps answering questions like these would help address how best to create an average. $\endgroup$ – Matthew Conroy Mar 21 '17 at 3:42
  • 2
    $\begingroup$ There's a whole field in mathematics on this topic of shape matching/analysis, but note that the approaches can become quite technical. A possible starting point for reading is the book "Shapes and Diffeomorphisms" (2010) by Laurent Younes, Springer Applied Mathematical Sciences vol. 171. For many approaches you would need that all curves for a letter are at least diffeomorphic. $\endgroup$ – Jaap Eldering Mar 21 '17 at 13:02
  • $\begingroup$ @MatthewConroy I added a picture to make it more clear. $\endgroup$ – Simon Marynissen Mar 21 '17 at 14:52
2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Do you assume that our letters have finite non-zero width? $\endgroup$ – Simon Marynissen Mar 21 '17 at 14:50
  • 1
    $\begingroup$ In principle, no. You can define a singular distribution concentrated on (the union of) infinitely thin curves. $\endgroup$ – Rahul Mar 21 '17 at 15:16
  • $\begingroup$ That last link is absolutely beautiful!! $\endgroup$ – Simon Marynissen Mar 21 '17 at 19:33
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not completely satified, since $S_{\mathop{universal}}$ is not a union of curves. I was maybe thinking you could make a statistical model and find the central element in it. $\endgroup$ – Simon Marynissen Mar 21 '17 at 12:12
  • 1
    $\begingroup$ This is a problem in which the obvious way to proceed is a bad one: If one person draws an "I" on the left side of the image, and another person draws it on the right side, the average should be an "I" halfway between them, but that's not what you will get with this approach. $\endgroup$ – Rahul Mar 21 '17 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.