Comparando dois histogramas usando a distância do qui-quadrado

18

Eu quero comparar duas imagens de rostos. Eu calculei seus histogramas LBP. Então agora eu preciso comparar esses dois histogramas e obter algo que diga o quanto esses histogramas são iguais (0 - 100%).

Existem várias maneiras de resolver essa tarefa, mas os autores do método LBP enfatizam (Descrição da face com padrões binários locais: aplicação no reconhecimento de faces. 2004) que a distância do qui-quadrado é melhor que a interseção do histograma e a estatística de probabilidade de log.

Os autores também mostram uma fórmula da distância do qui-quadrado:

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

Onde é um número de posições, é o valor da primeira posição, é o valor da segunda posição.x i y inxiyi

Em algumas pesquisas (por exemplo, a família de distância do histograma quadrático-qui), vi que a fórmula da distância do qui-quadrado é:

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

E lá http://www.itl.nist.gov/div898/handbook/eda/section3/eda35f.htm vejo que a fórmula da distância do qui-quadrado é:

Eu=1n(xEu-yEu)2yEu

Eu fiquei com isso. Eu tenho várias perguntas:

  1. Que expressão devo usar?
  2. Como devo interpretar um resultado da diferença? Eu sei que a diferença que é igual a 0 significa que ambos os histogramas são iguais, mas como posso saber quando ambos os histogramas são totalmente diferentes? Preciso usar uma mesa Chi-Square para isso? Ou preciso usar um limite? Basicamente, quero mapear a diferença para porcentagens.
  3. Por que essas três expressões são diferentes?
Anton Holovin
fonte
Yi não é o valor do mesmo compartimento que xi, mas na distribuição do comparador, em vez de um segundo compartimento?
ReneBt

Respostas:

7

A @Silverfish pediu uma expansão da resposta da PolatAlemdar, que não foi fornecida, então tentarei expandir aqui.

Por que o nome chisquare distância? O teste do qui-quadrado para tabelas de contingência é baseado em portanto a idéia é manter esse formulário e usá-lo como um medida de distância. Isso fornece a terceira fórmula do OP, com interpretado como observação e como expectativa, o que explica o comentário de PolatAlemdar "É usado em distribuições discretas de probabilidade", como por exemplo no teste de ajuste de qualidade. Essa terceira forma não é uma função de distância, pois é assimétrica nas variáveis e . Para comparação de histogramas, queremos uma função de distância simétrica em e xiyixyxy1

χ2=células(OEu-EEu)2EEu
xEuyEuxyxy, e as duas primeiras formas fornecem isso. A diferença entre eles é apenas um fator constante , o que não é importante desde que você escolha um formulário de forma consistente (embora a versão com fator extra seja melhor se você quiser comparar com o formato assimétrico). Observe a semelhança nessas fórmulas com a distância euclidiana quadrada, que não é coincidência, a distância do quadrado é um tipo de distância euclidiana ponderada . Por esse motivo, as fórmulas no OP geralmente são colocadas sob um sinal de raiz para obter distâncias . A seguir, seguimos isso. 11212

A distância do quadrado é usada também na análise de correspondência. Para ver o relacionamento com o formulário usado lá, seja as células de uma tabela de contingência com linhas e colunasIndique os totais da linha como e a coluna totalize com . A distância entre os quadrados é dada por No caso de apenas duas linhas (os dois histogramas), ele recupera a primeira fórmula do OP (módulo do sinal raiz). xEujRCx+j=EuxEujxEu+=jxEujeu,k

χ2(eu,k)=j1x+j(xeujxeu+-xkjxk+)2
EDIT

Respondendo à pergunta nos comentários abaixo: Um livro com longas discussões sobre a distância do quadrado é "ANÁLISE DA CORRESPONDÊNCIA EM PRÁTICA (Segunda Edição)", de Michael Greenacre (Chapman & Hall). É um nome bem estabelecido, proveniente de sua semelhança com o chisquare, usado nas tabelas de contingência. Que distribuição tem? Eu nunca estudei isso, mas provavelmente (sob algumas condições ...) ela teria alguma distribuição no quadrilátero, aproximadamente. As provas devem ser semelhantes ao que é feito com as tabelas de contingência; a maioria da literatura sobre análise de correspondência não entra na teoria da distribuição. Um artigo que tem alguma teoria talvez relevante é a http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382016000100023 . Veja também/stats//search?q=%22chisquare+distance%22 para outras postagens relevantes neste site.

kjetil b halvorsen
fonte
Posso perguntar por que sua última equação é chamada de distância do quadrado? É distribuído como tal? Você pode fornecer uma derivação, por favor, ou um link para uma? Parece que não consigo encontrar um.
LeastSquaresWonderer
1
Veja minhas edições acima.
Kjetil b halvorsen 03/08/19
3

Eu achei este link bastante útil: http://docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/histogram_comparison/histogram_comparison.html

Não sei bem por que, mas o OpenCV usa a 3ª fórmula listada para comparação do histograma do qui-quadrado.

Em termos de significado, não tenho certeza se algum algoritmo de medição fornecerá um intervalo limitado, como 0% a 100%. Em outras palavras, você pode ter certeza de que duas imagens são iguais: um valor de correlação de 1,0 ou um valor do qui-quadrado de 0,0; mas é difícil estabelecer um limite para a diferença entre duas imagens: imagine comparar uma imagem completamente branca versus uma imagem completamente preta; o valor numérico seria Infinito ou talvez Não-um-Número.

Russell
fonte
2

Na verdade, você pode usar o que achar correto para o seu caso. O último é diferente. Ele é usado em distribuições de probabilidade discretas, como o último será simétrica se você trocar e .xy

Os outros dois são usados ​​no cálculo de semelhanças de histograma.

PolatAlemdar
fonte
1
Você pode expandir um pouco esta resposta, para explicar como as outras duas podem ser usadas para calcular semelhanças de histograma. Observe que você pode adicionar tipografia matemática no látex à sua resposta usando cifrões: $x$produz por exemplo. x
quer
2
Você precisa explicar em que sentido o terceiro é simétrico em e , pois não parece assim. xy
precisa saber é o seguinte
0

Conforme solicitado pelo OP, o valor em porcentagem (para a equação 1):

p=χS100N

Onde: é a porcentagem de diferença (0..100). é o resultado da equação 1. é o número de posições no histograma. é o valor máximo possível no compartimento.pχNS

Complementado conforme solicitado:

Ao calcular esta equação, pode-se ter a porcentagem de diferença de um histograma completo. Calculando isso para ambos os histogramas e subtraindo um do outro, pode-se ter a diferença em porcentagem.

Carlos Barcellos
fonte
2
É difícil ver como isso é uma resposta para qualquer uma das perguntas. Você pode elaborar?
O Laconic
Isso fornecerá (em porcentagem, conforme solicitado) a diferença de um histograma para um histograma completo. Se você calcular esta equação a partir de ambos os histogramas, saberemos a diferença de uma para outra, como essa usada para triangulação.
Carlos Barcellos