Jak ocenić podobieństwo dwóch histogramów?

Ostatnia praca, którą warto przeczytać, to:

Cao, Y. Petzold, L. Ograniczenia dokładności i pomiar błędów w symulacji stochastycznej układów reagujących chemicznie, 2006.

Chociaż niniejsza praca skupia się na porównaniu algorytmów symulacji stochastycznych, zasadniczo główną ideą jest porównanie dwóch histogramów .

Dostęp do pdf można uzyskać ze strony internetowej autora.

Komentarze

• Cześć, niezły papier, dziękuję za podanie linku do pdf. ' z pewnością przejdę przez ten artykuł ..
• Zamiast tego podania odniesienia dobrze by było, gdybyś ' d podsumował główne punkty artykułu. Linki umierają, więc w przyszłości Twoja odpowiedź może stać się bezużyteczna dla osób, które nie są subskrybentami tego czasopisma (a ogromna większość ludzkiej populacji to osoby niepubliczne).

Jest mnóstwo miary odległości między dwoma histogramami. Dobrą kategoryzację tych miar można przeczytać w:

K. Meshgi i S. Ishii, „Expanding Histogram of Colours with Gridding to Improve Tracking Accuracy ”, w Proc. of MVA15, Tokio, Japonia, maj 2015 r.

Poniżej wymieniono najpopularniejsze funkcje odległości:

• $ L_0 $ lub odległość Hellingera

$ D_ {L0} = \ sum \ limits_ {i} h_1 (i) \ neq h_2 (i) $

• $ L_1 $ , Manhattan lub City Block Distance

$ D_ {L1} = \ sum_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• $ L = 2 $ lub odległość euklidesowa

$ D_ { L2} = \ sqrt {\ sum_ {i} \ left (h_1 (i) – h_2 (i) \ right) ^ 2} $

• L $ _ {\ infty} $ lub Chybyshev Distance

$ D_ {L \ infty} = max_ { i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• L $ _ p $ lub Fractional Odległość (należy do rodziny odległości Minkowskich)

$ D_ {Lp} = \ left (\ sum \ limits_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert ^ p \ right) ^ {1 / p} $ i 0 $ < p < 1 $

• Przecięcie histogramu

$ D _ {\ cap} = 1 – \ frac {\ sum_ {i} \ left (min (h_1 (i)) , h_2 (i) \ right)} {min \ left (\ vert h_1 (i) \ vert, \ vert h_2 (i) \ vert \ right)} $

• Odległość kosinusowa

$ D_ {CO} = 1 – \ sum_i h_1 (i) h2_ (i) $

• Odległość Canberra

$ D_ {CB} = \ sum_i \ frac {\ lvert h_1 (i) -h_2 (i ) \ rvert} {min \ left (\ lvert h_1 (i) \ rvert, \ lvert h_2 (i) \ rvert \ right)} $

• Współczynnik korelacji Pearsona

$ D_ {CR} = \ frac {\ sum_i \ left (h_1 (i) – \ frac {1} {n} \ right ) \ left (h_2 (i) – \ frac {1} {n} \ right)} {\ sqrt {\ sum_i \ left (h_1 (i) – \ frac {1} {n} \ right) ^ 2 \ sum_i \ left (h_2 (i) – \ frac {1} {n} \ right) ^ 2}} $

• Rozbieżność Kołmogorowa-Smirnowa

$ D_ {KS} = max_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• Dopasuj odległość

$ D_ {MA} = \ sum \ limits_ { i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• Odległość Cramera-von Misesa

$ D_ {CM} = \ sum \ limits_ {i} \ left (h_1 (i) – h_2 (i) \ right) ^ 2 $

• $ \ chi ^ 2 $ Statystyki

$ D _ {\ chi ^ 2 } = \ sum_i \ frac {\ left (h_1 (i) – h_2 (i) \ right) ^ 2} {h_1 (i) + h_2 (i)} $

• Odległość Bhattacharyya

$ D_ {BH} = \ sqrt {1- \ sum_i \ sqrt {h_1 (i) h_2 (i)}} $ & hellinger

• Akord kwadratowy

$ D_ {SC} = \ sum_i \ left (\ sqrt {h_1 (i)} – \ sqrt {h_2 (i)} \ right) ^ 2 $

• Kullback -Liebler Divergance

$ D_ {KL} = \ sum_i h_1 (i) log \ frac {h_1 (i)} {m (i)} $

• Jefferey Divergence

$ D_ {JD} = \ sum_i \ left (h_1 (i) log \ frac {h_1 (i)} {m (i)} + h_2 (i) log \ frac {h_2 (i)} {m (i)} \ right) $

• Odległość robota ziemnego (jest to pierwszy element Odległości transportowe, które zawierają informacje o binningu $ A $ w odległości. Aby uzyskać więcej informacji, zapoznaj się z wyżej wymienionym dokumentem lub Wikipedią .

$ D_ {EM} = \ frac {min_ {f_ {ij}} \ sum_ {i, j} f_ {ij} A_ {ij}} {sum_ {i, j} f_ {ij}} $ $ \ sum_j f_ {ij} \ leq h_1 (i), \ sum_j f_ {ij} \ leq h_2 (j), \ sum_ {i, j} f_ {ij} = min \ left (\ sum_i h_1 (i) \ sum_j h_2 (j) \ right) $ i $ f_ {ij} $ reprezentuje przepływ z $ i $ do $ j $

• Dystans kwadratowy ance

$ D_ {QU} = \ sqrt {\ sum_ {i, j} A_ {ij} \ left (h_1 (i) – h_2 (j) \ right) ^ 2} $

• Odległość kwadratowa-Chi

$ D_ {QC} = \ sqrt {\ sum_ {i, j} A_ {ij} \ left (\ frac {h_1 (i) – h_2 (i)} {\ left (\ sum_c A_ {ci} \ left (h_1) (c) + h_2 (c) \ right) \ right) ^ m} \ right) \ left (\ frac {h_1 (j) – h_2 (j)} {\ left (\ sum_c A_ {cj} \ left (h_1) (c) + h_2 (c) \ right) \ right) ^ m} \ right)} $ i $ \ frac {0} {0} \ equiv 0 $

Implementacja niektórych z tych odległości w Matlabie jest dostępna w moim repozytorium GitHub: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Możesz również wyszukać takie osoby, jak Yossi Rubner, Ofir Pele, Marco Cuturi i Haibin Ling, aby znaleźć bardziej nowoczesne odległości.

Aktualizacja: Alternatywne wyjaśnienia dotyczące odległości pojawiają się tu i tam w literaturze, więc ze względu na kompletność wymieniam je tutaj.

• Odległość Canberra (inna wersja)

$ D_ {CB} = \ sum_i \ frac {| h_1 (i) -h_2 (i) |} {| h_1 (i) | + | h_2 (i) |} $

• Różnica Braya-Curtisa, odległość Sorensena (od suma histogramów jest równa jeden, równa się $ D_ {L0} $ )

$ D_ {BC} = 1 – \ frac {2 \ sum_i h_1 (i) = h_2 (i)} {\ sum_i h_1 (i) + \ sum_i h_2 (i)} $

• Odległość Jaccarda (tj. przecięcie nad sumą, inna wersja)

$ D_ {IOU} = 1 – \ frac { \ sum_i min (h_1 (i), h_2 (i))} {\ sum_i max (h_1 (i), h_2 (i))} $

Komentarze

• Witamy na naszej stronie! Dziękujemy za ten wkład.
• Oto link do wersji papierowej: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Dzięki, lista jest cudowna, chociaż nie ' t pozwala na utworzenie operatora porównania dla histogramu, np. powiedzieć, że hist1 < hist2
• Twoja dywergencja KS jest zaimplementowana w kodzie jako $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Wydaje się to niezgodne z równaniem, które masz powyżej. Czy coś mi brakuje?
• Myślę, że to błąd w moim kodzie. Przyjrzę się temu. Dziękujemy za zwrócenie uwagi

Standardową odpowiedzią na to pytanie jest test chi-kwadrat . Test KS dotyczy danych niepowiązanych, a nie danych skategoryzowanych. (Jeśli masz niepowiązane dane, to zdecydowanie użyj testu w stylu KS, ale jeśli masz tylko histogram, test KS nie jest odpowiedni.)

Komentarze

• Masz rację, że test KS nie jest odpowiedni dla histogramów, jeśli jest rozumiany jako test hipotezy dotyczący dystrybucji danych bazowych, ale nie widzę powodu, dla którego statystyki KS nie ' nie działa dobrze jako miara identyczności dowolnych dwóch histogramów.
• Wyjaśnienie, dlaczego test Kołmogorowa-Smirnowa nie jest odpowiedni w przypadku danych podzielonych byłoby przydatne.
• Może to nie być tak przydatne w przetwarzaniu obrazu, jak w statystycznej ocenie umiejętności. Często w przetwarzaniu obrazu histogram danych jest używany jako deskryptor dla regionu obrazu, a celem jest określenie odległości między histogramami, aby odzwierciedlić odległość między obszarami obrazu. Niewiele, a być może wcale, niewiele wiadomo o ogólnych statystykach populacji bazowych danych obrazu użytych do uzyskania histogramu. Na przykład podstawowe statystyki populacji podczas korzystania z histogramów zorientowanych gradientów będą się znacznie różnić w zależności od rzeczywistej zawartości obrazów.
• Na pytanie 101 ' udzielono odpowiedzi przez Stochtastic: stats.stackexchange.com/a/108523/37373

Szukasz testu Kołmogorowa-Smirnowa . Nie zapomnij podzielić wysokości słupków przez sumę wszystkie obserwacje każdego histogramu.

Zauważ, że test KS również zgłasza różnicę, jeśli np środki dystrybucji są przesunięte względem siebie. Jeśli translacja histogramu wzdłuż osi x nie ma znaczenia w twojej aplikacji, możesz najpierw odjąć średnią z każdego histogramu.

Komentarze

• Odejmowanie średniej zmienia rozkład zerowy statystyki KS. @David Wright i tak zgłasza uzasadniony sprzeciw wobec zastosowania testu KS do histogramów.

Jak Odpowiedź Davida wskazuje, że test chi-kwadrat jest niezbędny dla danych binningowych, ponieważ test KS zakłada ciągłe rozkłady. Odnośnie do tego, dlaczego test KS jest niewłaściwy (uwaga 101), omówiono ten problem w zastosowanym literaturę statystyczną, którą warto tutaj zebrać.

Zabawna wymiana zdań rozpoczęła się od stwierdzenia ( García-Berthou i Alcaraz, 2004) , że jedna trzecia artykułów Nature zawiera błędy statystyczne. Jednak kolejny artykuł ( Jeng, 2006 , „ Błąd w testach statystycznych błędu w testach statystycznych ” – być może moja wszystko- tytuł ulubionego artykułu czasu) wykazali, że Garcia-Berthou i Alcaraz (2005) zastosowali testy KS na danych dyskretnych, co doprowadziło do podania niedokładnych wartości p w ich meta-badaniu. Artykuł Jeng (2006) dostarcza miłego omówienia tego zagadnienia, pokazując nawet, że można zmodyfikować test KS, aby działał na danych dyskretnych. W tym konkretnym przypadku rozróżnienie sprowadza się do różnicy między równomiernym rozkładem końcowej cyfry na [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (w nieprawidłowym teście KS) i rozkład grzebieniowy funkcji delta, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (w poprawnej, zmodyfikowanej formie).W wyniku pierwotnego błędu Garcia-Berthou i Alcaraz (2004) błędnie odrzucili wartość zerową, podczas gdy test chi-kwadrat i zmodyfikowany test KS nie. W każdym razie test chi kwadrat jest standardowym wyborem w tym scenariuszu, nawet jeśli KS można zmodyfikować, aby działał tutaj.