Tipografía universal: ¿cómo hacer la media de las letras?

Question

En 2014, BIC puso en marcha el experimento tipográfico universal . Fue un intento de crowdsourcing para crear un tipo de letra universal. Los usuarios podían introducir su forma escrita de las letras y el experimento sacaba la media de todas las letras de todos los que participaban.

Se puede definir una letra como la unión de curvas finitas acotadas (cerradas). Cómo se definiría la media de dos letras?

Observaciones

Sea $\gamma_1:[0,1] \rightarrow \mathbb{R}^2$ y $\gamma_2:[0,1] \rightarrow \mathbb{R}^2$ sean dos curvas. Podríamos definir ingenuamente la media como: $$\gamma:[0,1]\rightarrow \mathbb{R}^2:x \mapsto \frac{\gamma_1(x)+\gamma_2(x)}{2}.$$ Pero una parametrización diferente daría un resultado distinto. Esto significa que no es una buena definición de media.

Se necesitaría la propiedad obvia de que la media de $n$ las copias de la misma carta deberían dar como resultado la misma carta.

Editar He incluido una imagen de cómo debería ser una media.

(No sabía cómo etiquetar esto, así que siéntete libre de añadir más etiquetas).

Answer 1

Consideremos primero un problema relacionado, el de las fuentes en mapa de bits (raster) en lugar de las fuentes vectoriales (por ejemplo, curvas de Bezier u otras funciones analíticas que representan cada curva, como en este problema).

En el caso de los mapas de bits, hay una forma obvia de proceder. Si la imagen de la fuente está representada por un $n\times n$ cuadrícula de píxeles, entonces cada usuario está especificando un elemento de $\{0,1\}^{n\times n}$ . Tomar la media en el espacio vectorial $\mathbb R^{n\times n}$ para obtener un elemento de $[0,1]^{n\times n}$ y aplicar algún tipo de redondeo para obtener una imagen en $\{0,1\}^{n\times n}$ .

Consideremos ahora el análogo continuo de esto. Supongamos que el $k^{th}$ el usuario especifica un subconjunto cerrado (y, por tanto, compacto) $S_k\subset [0,1]^2$ como una unión de curvas (aquí el cuadrado de la unidad denota la región sobre la que el usuario dibuja la curva). Fije $\epsilon>0$ y considerar la $\epsilon$ -engrosamiento de $S_k$ Este es el conjunto $$ B(S_k,\epsilon):=\{v\in [0,1]^2\colon d(v,S_k)\leq \epsilon\}, $$ donde la notación $d(v,S_k)$ denota la distancia mínima desde un punto en $S_k$ a $v$ con respecto a la distancia euclidiana.

Podemos hacer una media de las funciones indicadoras de estos conjuntos engrosados para obtener una especie de función de "mapa de calor" sobre $[0,1]^2$ dado por $$ f(v)=\frac{\#\{1\leq k\leq N\colon v\in B(S_k,\epsilon)\}}{N}. $$ Es de esperar que converja en el límite (teórico) como $\epsilon\to 0$ y $N\to\infty$ simultáneamente, pero tomando algunas pequeñas $\epsilon$ probablemente sería suficiente (por ejemplo $\epsilon=10^{-3}$ en función del número de personas $N$ y la precisión en coma flotante deseada). Por último, aplique algún tipo de procedimiento de redondeo. Para simplificar las cosas, digamos que una intensidad mayor que $\alpha\in (0,1)$ cuenta como que esa parte de la región está presente. Entonces el conjunto que describe nuestra fuente universal sería $$ S_{universal}:=\{v\in[0,1]^2\colon f(v)>\alpha\}. $$ Desenrollando las definiciones, podríamos escribir esto de la siguiente manera: $$ 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\}. $$ Por supuesto, si los conjuntos se dan explícitamente como una unión de curvas (suficientemente simples) como líneas, círculos, curvas de Bézier, el mínimo interior podría calcularse como una función explícita que incluyera raíces cuadradas, raíces cúbicas, etc., y así $S_{universal}$ podría describirse o aproximarse mediante una unión finita de curvas "bonitas".

Answer 2

Consideremos primero una versión discreta del problema: Se tienen dos conjuntos de $n$ puntos $\{p_1,\ldots,p_n\}$ y $\{q_1,\ldots,q_n\}$ y quieres interpolar entre ellos, pero no sabes qué punto debe coincidir con cuál. Una forma de definir la mejor correspondencia es elegir la que minimice la distancia total que deben recorrer los puntos. Se trata de un ejemplo del método problema de asignación y puede resolverse eficazmente (puede ver algunos ejemplos geométricos aquí ).

Su análogo continuo es el Métrica Wasserstein Si se interpretan las curvas como una distribución de tinta en la página y se minimiza la distancia que habría que mover la tinta para pasar de una letra a otra (es decir, se minimiza la integral tinta-masa-veces-distancia). Los últimos trabajos en gráficos por ordenador también pueden calcular esto de forma eficiente:

Solomon y otros, " Distancias convolucionales de Wasserstein: Transporte óptimo eficiente en dominios geométricos " (pdf), SIGGRAPH 2015.

Véanse especialmente las Figs. 12 y 13, que muestran la interpolación de formas en 2D:

A la izquierda se muestra lo que se obtiene interpolando imágenes como vectores en $\mathbb R^{m\times m}$ como se sugiere en respuesta de prekidney .

Véase también otro trabajo sobre la interpolación automática de las formas de las letras: Campbell y Kautz, " Aprender un sinfín de fuentes ", SIGGRAPH 2014.