Koda za razdaljo odseljevalcev zemlje (EMD)

Uvod

To je izvedba razdalje med kmeti, kot je opisano v [1]. EMD izračuna razdaljo med dvema distribucijama, ki jih predstavljajo podpisi. Podpisi so nabori ponderiranih funkcij, ki zajemajo porazdelitve. Funkcije so lahko poljubne vrste in v poljubnem številu dimenzij ter jih definira uporabnik.

EMD je opredeljen kot najmanjši znesek dela, potrebnega za spremembo enega podpisa v drugega. Pojem “delo” temelji na uporabniško določeni razdalji tal, ki je razdalja med dvema funkcijama. Velikost obeh podpisov je lahko drugačna. Tudi vsota uteži enega podpisa se lahko razlikuje od vsote uteži druge (delne tekme). Zaradi tega se EMD normalizira z manjšo vsoto.

Koda se izvaja v C in temelji na rešitvi za težavo Transport, kot je opisano v [2]

Prosim, povejte me o morebitnih napakah, ki jih najdete, ali o morebitnih vprašanjih, komentarjih, predlogih in kritikah. Če boste našli to kodo koristno za vaše delo, bi rad zelo slišal od vas. Ko boste to storili, vas bom obvestil o kakršnih koli izboljšavah itd. Poleg tega bi bilo v vseh publikacijah, ki opisujejo delo, ki uporablja to kodo, zelo cenjeno potrdilo.

Uporaba

Če želite uporabiti kodo, storite naslednje:

  1. prenesite datoteke emd.h in emd.c (preverite dnevnik sprememb za zadnje spremembe).
    V emd.h spremenite vrstico
  2. typedef int function_t;
    da odraža vašo podatkovno značilnost. Tudi na primer lahko uporabite strukture

typedef struct {
int X, Y, Z;
} funkcija_t;

3. Če želite izračunati EMD, pokličite:

float emd (signature_t * Podpis1, signature_t * podpis2,
float (* func) (funkcija_t *, funkcija_t *),
flow_t * Flow, int * FlowSize);

kje

Podpis1, podpis2:

Pokažite dvema podpisoma, da želimo izračunati njihovo razdaljo.

Dist:

Kazalec na funkcijo razdalje tal. to je funkcija, ki izračuna razdaljo med dvema funkcijama.

Tok:

(Neobvezno) Kazalec na vektor flow_t (opredeljen v emd.h), kjer se bo shranil nastali tok. Tok mora imeti n1 + n2-1 elemente, pri čemer sta n1 in n2 velikosti obeh podpisov. Če je NULL, se tok ne vrne.

FlowSize:

(Neobvezno) Če Flow ni NULL, mora FlowSize kazati na celo število, kjer bo zapisano število elementov pretoka (vedno manj ali enako n1 + n2-1).

4. Compile emd.c in jo povežite s svojo kodo.

Podatek podatkov tipa signature_t je definiran v emd.h kot:

typedef struct
{
int n; / * Število funkcij v distribuciji * /
feature_t * Funkcije; / * Kazalec na vektorske funkcije * /
float * uteži; / * Kazalec na uteži funkcij * /
} signature_t;

Vrsta podatkovne funkcije funkcija_t je definirana v emd.h in jo mora uporabnik spremeniti, tako da odraža njegovo vrsto funkcije.

V posebnih primerih lahko uporabnik morda želi spremeniti nekatere vrednosti v definicijah v emd.h:

#define MAX_SIG_SIZE 100
Največje dovoljeno število funkcij v podpisu

#define MAX_ITERATIONS 100
Največje število ponovitev. Za navadne probleme mora biti 100 več kot dovolj.

#define INFINITY 1e20
INFINITY mora biti veliko večja od katere koli druge vrednosti v težavah

#define EPSILON 1e-6
EPSILON določa točnost rešitve.

Primeri

1. primer1.c

V tem primeru so funkcije v tridimenzionalnem prostoru, zemeljska razdalja pa je evklidska razdalja.

Če želite preizkusiti ta primer, morate spremeniti funkcijo_t v emd.h

typedef struct {int X, Y, Z; } funkcija_t;
2. primer2.c
Tukaj namesto da bi zagotovili funkcijo za izračun zemeljskih razdalj, so podane v vnaprej določeni matrici. To naredite tako, da določite funkcijo_t kot int (privzeto) in nastavite funkcije v vsakem podpisu za zaporedne številke. Funkcija razdalj na tleh te številke uporablja kot indekse vnaprej definirane stroškovne matrike.
Dobljeni tok se vrne iz funkcije emd tako, da kot zadnje parametre prenese vektor flow_t in kazalec na int, kjer bo zapisano dejansko število tokovnih elementov.
Tudi v tem primeru so skupne teže obeh podpisov drugačne. Prvi podpis ima skupno težo 1, medtem ko ima drugi podpis skupno težo 0,9.

Dnevnik sprememb
Datum Razkritje
05/10/98 Sprememba je bila od absolutnega preverjanja napak do relativnega preverjanja napak + Popravljena napaka, ki je povzročila sporočilo o napaki »Nepričakovana napaka pri iskanju najdenih« (zahvaljujoč Marku Ruzonu)
03/04/98 Popravila napako, ki je nekoč povzročila nesrečo, ko je drugi podpis imel samo eno funkcijo (zahvaljujoč Marku Ruzonu)

 

Reference
[1] Y. Rubner, C. Tomasi in L. J. Guibas. Metrika za porazdelitve z aplikacijami na slikovne podatkovne baze. Zbornik IEEE mednarodne konference 1998 Computer Vision, Bombay, Indija, januar 1998, str. 59-66.

[2] F. S. Hillier in G. J. Lieberman. Uvod v matematično programiranje McGraw-Hill, 1990.

Vir: https://users.cs.duke.edu/~tomasi/software/emd.htm

Leave a Reply

Your email address will not be published. Required fields are marked *