Porównanie dwóch histogramów przy użyciu odległości Chi-Square

18

Chcę porównać dwa obrazy twarzy. Obliczyłem ich histogramy LBP. Więc teraz muszę porównać te dwa histogramy i uzyskać coś, co powie, ile te histogramy są równe (0 - 100%).

Istnieje wiele sposobów rozwiązania tego zadania, ale autorzy metody LBP podkreślają (Opis twarzy z lokalnymi wzorami binarnymi: Zastosowanie do rozpoznawania twarzy. 2004), że odległość Chi-Square jest lepsza niż przecięcie histogramu i statystyka prawdopodobieństwa Log.

Autorzy pokazują również formułę odległości chi-kwadrat:

i=1n(xiyi)2(xi+yi)

Gdzie jest liczbą przedziałów, jest wartością pierwszego bin, jest wartością drugiego bin.nxiyi

W niektórych badaniach (na przykład Rodzina odległości kwadratowego chi-histogramu) widziałem, że wzór odległości chi-kwadrat to:

12i=1n(xiyi)2(xi+yi)

I tam http://www.itl.nist.gov/div898/handbook/eda/section3/eda35f.htm Widzę, że wzór na odległość Chi-Square to:

i=1n(xiyi)2yi

Utknąłem z tym. Mam kilka pytań:

  1. Jakiego wyrażenia powinienem użyć?
  2. Jak mam interpretować wynik różnicy? Wiem, że różnica równa 0 oznacza, że ​​oba histogramy są równe, ale skąd mam wiedzieć, kiedy oba histogramy są całkowicie różne? Czy muszę do tego użyć stołu Chi-Square? Czy muszę użyć progu? Zasadniczo chcę odwzorować różnicę na procenty.
  3. Dlaczego te trzy wyrażenia są różne?
Anton Holovin
źródło
Czy yi nie jest wartością tego samego przedziału co xi, ale w rozkładzie komparatora, a nie drugim przedziałem?
ReneBt

Odpowiedzi:

7

@Silverfish poprosił o rozszerzenie odpowiedzi przez PolatAlemdar, która nie została podana, więc spróbuję ją rozwinąć tutaj.

Dlaczego nazwa chisquare odległość? Test chisquare dla tabel awaryjnych oparty jest na więc pomysł polega na zachowaniu tej formy i użyciu jej jako miara odległości. To daje trzecią formułę OP, gdzie interpretowane jest jako obserwacja, a jako oczekiwanie, co wyjaśnia komentarz PolatAlemdara „Jest stosowany w dyskretnych rozkładach prawdopodobieństwa”, jak na przykład w testach poprawności dopasowania. Ta trzecia postać nie jest funkcją odległości, ponieważ jest asymetryczna w zmiennych i . Dla porównania histogramu, będziemy chcieli funkcję odległości, która jest symetryczna w X i Y xiyix

χ2=cells(OiEi)2Ei
xjayjaxyxyi dają to dwie pierwsze formy. Różnica między nimi to tylko stały współczynnik , co nie jest ważne, o ile tylko konsekwentnie wybierasz jeden formularz (choć wersja z dodatkowym współczynnikiem112) jest lepsze, jeśli chcesz porównać z formą asymetryczną). Zwróć uwagę na podobieństwo tych wzorów z kwadratową odległością euklidesową, która nie jest przypadkiem, odległość chisquare jest rodzajemważonejodległości euklidesowej. Z tego powodu formuły w OP są zwykle umieszczane pod znakiem root, aby uzyskaćodległości. Poniżej śledzimy to.12)

Odległość Chisquare jest również używana w analizie korespondencji. Aby zobaczyć związek z zastosowaną tam formą, niech będą komórkami tabeli awaryjnej z wierszami R i kolumnami C. Oznaczania sumy rzędów być x + j = Σ i x i j i sumy kolumna po x i + = Σ J x i j . Odległość chisquare między rzędami l , k jest dana przez χ 2 ( l , k ) =xjajotRdox+jot=jaxjajotxja+=jotxjajotl,k W przypadku tylko dwóch wierszy (dwa histogramy) odzyskuje to pierwszą formułę OP (modulo znak root).

χ2)(l,k)=jot1x+jot(xljotxl+-xkjotxk+)2)
EDIT

Odpowiadając na pytanie w komentarzach poniżej: Książka z długimi dyskusjami o odległości chisquare to „ANALIZA KORESPONDENCJI W PRAKTYCE (drugie wydanie)” Michaela Greenacre (Chapman i Hall). Jest to dobrze znana nazwa, wywodząca się z podobieństwa do chisquare w połączeniu z tabelami nieprzewidzianymi. Jaką dystrybucję ma? Nigdy tego nie studiowałem, ale prawdopodobnie (pod pewnymi warunkami ...) miałby w przybliżeniu rozkład chisquare. Dowody powinny być podobne do tego, co robi się z tabelami nieprzewidzianymi, większość literatury na temat analizy korespondencji nie dotyczy teorii dystrybucji. Artykuł zawierający pewną, być może istotną taką teorię, to http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382016000100023 . Zobacz także/stats//search?q=%22chisquare+distance%22 w przypadku niektórych innych istotnych postów na tej stronie.

kjetil b halvorsen
źródło
Czy mogę zapytać, dlaczego ostatnie równanie nazywa się odległością chisquare? Czy jest dystrybuowany jako taki? Czy możesz podać pochodną lub link do niej? Nie mogę tego znaleźć.
LeastSquaresWonderer
1
Zobacz moje zmiany powyżej.
kjetil b halvorsen
3

Uważam, że ten link jest bardzo przydatny: http://docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/histogram_comparison/histogram_comparison.html

Nie jestem pewien, dlaczego, ale OpenCV używa trzeciej formuły, którą podajesz do porównania histogramu Chi-Square.

Pod względem znaczenia nie jestem pewien, czy jakiś algorytm pomiarowy da ci ograniczony zakres, na przykład od 0% do 100%. Innymi słowy, możesz z całą pewnością stwierdzić, że dwa obrazy są takie same: wartość korelacji 1,0 lub wartość chi-kwadrat 0,0; ale trudno jest ustalić limit między dwoma obrazami: wyobraź sobie, że porównujesz obraz całkowicie biały z obrazem całkowicie czarnym, wartością liczbową byłaby nieskończoność, a może brak liczby.

Russell
źródło
2

xy

Pozostałe dwa służą do obliczania podobieństwa histogramu.

PolatAlemdar
źródło
1
$x$x
2
xy
0

Zgodnie z wnioskiem OP wartość procentowa (dla równania 1):

p=χS.100N.

pχN.S.

Uzupełnione zgodnie z wnioskiem:

Obliczając to równanie, można uzyskać procent różnicy od pełnego histogramu. Obliczając to dla obu histogramów, a następnie odejmując jeden od drugiego, można uzyskać różnicę procentową.

Carlos Barcellos
źródło
2
Trudno mi zrozumieć, w jaki sposób jest to odpowiedź na którekolwiek z pytań. Czy możesz rozwinąć?
The Laconic
To da (w procentach, zgodnie z żądaniem), jak różni się jeden histogram od pełnego histogramu. Jeśli obliczysz to równanie z obu histogramów, poznamy różnicę między nimi, jak to używane do triangulacji.
Carlos Barcellos