Introducción
Esta es una implementación de la Distancia de Mover la Tierra, como se describe en [1]. El EMD calcula la distancia entre dos distribuciones, que están representadas por firmas. Las firmas son conjuntos de características ponderadas que capturan las distribuciones. Las características pueden ser de cualquier tipo y en cualquier cantidad de dimensiones, y están definidas por el usuario.
El EMD se define como la cantidad mínima de trabajo necesaria para cambiar una firma por la otra. La noción de “trabajo” se basa en la distancia a tierra definida por el usuario que es la distancia entre dos características. El tamaño de las dos firmas puede ser diferente. Además, la suma de los pesos de una firma puede ser diferente a la suma de los pesos de la otra (coincidencia parcial). Debido a esto, el EMD se normaliza por la suma más pequeña.
El código se implementa en C y se basa en la solución para el problema de transporte como se describe en [2]
Por favor, avísenme de cualquier error que encuentre, o cualquier pregunta, comentario, sugerencia o crítica que tenga. Si encuentras este código útil para tu trabajo, me gustaría mucho saber de ti. Una vez que lo haga, le informaré sobre cualquier mejora, etc. También agradecería mucho un reconocimiento en cualquier publicación que describa el trabajo que utiliza este código.
Uso
Para usar el código, realice los siguientes pasos:
- descargue los archivos emd.h y emd.c (revise el registro de cambios para ver los últimos cambios)
- En emd.h, modifica la línea
typedef int feature_t;
para reflejar su tipo de datos de características. Las estructuras también se pueden usar, por ejemplo
typedef struct {
int X, Y, Z;
} feature_t;
- Para calcular un EMD, llame al:
float emd (signature_t * Signature1, signature_t * Signature2,
float (* func) (feature_t *, feature_t *),
flow_t * Flow, int * FlowSize);
dónde
Firma1, Firma2:
Punteros a las dos firmas que su distancia queremos calcular.
Dist:
Puntero a la función de distancia a tierra. es decir, la función que calcula la distancia entre dos características.
Fluir:
(Opcional) Puntero a un vector de flow_t (definido en emd.h) donde se almacenará el flujo resultante. El flujo debe tener n1 + n2-1 elementos, donde n1 y n2 son los tamaños de las dos firmas, respectivamente. Si es NULL, el flujo no se devuelve.
FlowSize:
(Opcional) En caso de que Flow no sea NULL, FlowSize debe apuntar a un entero donde se escribirá el número de elementos de flujo (siempre menos o igual a n1 + n2-1).
- Compila emd.c y vincúlalo a tu código.
El tipo de datos de firma signature_t se define en emd.h como:
typedef struct
{
int n; / * Número de características en la distribución * /
feature_t * Funciones; / * Puntero al vector de características * /
flotar * Pesos; / * Puntero a los pesos de las características * /
} signature_t;
El tipo de datos de características feature_t se define en emd.h y debe ser modificado por el usuario para reflejar su tipo de característica.
En casos especiales, el usuario puede querer cambiar algunos de los valores en las definiciones en emd.h:
#define MAX_SIG_SIZE 100
El número máximo permitido de características en una firma
#define MAX_ITERATIONS 100
Número máximo de iteraciones Para problemas comunes, 100 debería ser más que suficiente.
#define INFINITY 1e20
INFINITY debería ser mucho más grande que cualquier otro valor en el problema
#define EPSILON 1e-6
EPSILON determina la precisión de la solución.
Ejemplos
- ejemplo1.cEn este ejemplo, las características se encuentran en el espacio tridimensional, y la distancia al suelo es la distancia euclidiana.Para probar este ejemplo, debe modificar feature_t en emd.h para que seatypedef struct {int X, Y, Z; } feature_t;
- ejemplo2.cAquí, en lugar de proporcionar una función para calcular las distancias al terreno, se dan en una matriz predefinida. Esto se hace definiendo feature_t como int (el valor predeterminado) y estableciendo las características en cada firma para tener números consecutivos. La función de distancia al suelo usa estos números como índices de la matriz de costos predefinida.El flujo resultante se devuelve desde la función emd pasando como los últimos parámetros un vector de flow_t, y un puntero a int donde se escribirá el número real de elementos de flujo.Además, en este ejemplo, los pesos totales de las dos firmas son diferentes. La primera firma tiene un peso total de 1 mientras que la segunda firma tiene un peso total de 0.9.
Registro de cambios
| Fecha | Descripción |
| 05/10/98 | Se cambió de la comprobación de error absoluta a la verificación de error relativa + Se corrigió un error que causaba el mensaje de error “Error inesperado en findBasicVariables” (gracias a Mark Ruzon) |
| 03/04/98 | Se corrigió un error que alguna vez causaba un bloqueo cuando la segunda firma tenía una sola característica (gracias a Mark Ruzon) |
| 03/31/98 | Se corrigió un error en el caso donde * ambas * firmas tienen una sola característica (gracias Rajesh Batra) |
eferencias
- Rubner, C. Tomasi y L. J. Guibas. Una métrica para distribuciones con aplicaciones a bases de datos de imágenes. Actas de la Conferencia Internacional IEEE de 1998 sobre Visión por Computadora, Bombay, India, enero de 1998, págs. 59-66.
- S. Hillier y G. J. Lieberman. Introducción a la programación matemática McGraw-Hill, 1990.
Orignal Source: https://users.cs.duke.edu/~tomasi/software/emd.htm
