Entropia de uma imagem

21

Qual é a maneira correta mais teórica da informação / física para calcular a entropia de uma imagem? Não me preocupo com a eficiência computacional agora - quero teoricamente o mais correto possível.

Vamos começar com uma imagem em escala de cinza. Uma abordagem intuitiva é considerar a imagem como um conjunto de pixels e calcular que é o número de níveis de cinza é a probabilidade associada ao nível de cinza .

H = - \sum_{k} p_{k} eu o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

K

$K$

p_{k}

$p_k$

k

$k$

Existem dois problemas com esta definição:

Funciona para uma banda (escala de cinza), mas como estendê-la de maneira estatisticamente correta para várias bandas? Por exemplo, para 2 bandas, deve-se basear-se em e, portanto, no PMF usando ? Se houver muitas bandas ( >> 2), então , o que parece errado. $(X_1,X_2)$ $P(X_1=x_1,X_2=x_2)$ $B$ $P(X_1=x_1, ..., X_B=x_B) \sim 1/N^B \rightarrow H_{MAX}$
Informações espaciais não são levadas em consideração. Por exemplo, as imagens abaixo (custódia de John Loomis ) têm o mesmo , embora claramente não transmitam a mesma informação. $H$

Alguém quer explicar ou dar conselhos, ou me encaminhar para algum material de referência decente sobre o assunto? Estou interessado principalmente em uma abordagem teoricamente correta do segundo problema (ou seja, informações espaciais).

spatial entropy image-processing Davor Josipovic
fonte

2

Eu acho que você deve olhar para os campos aleatórios markov, por exemplo, files.is.tue.mpg.de/chwang/papers/CVIU2013_MRFSurvey.pdf

seanv507

1

também matrizes de co-ocorrência em tons de cinza

seanv507

@ seanv507, sim, de fato. Modelos gráficos não direcionados ou campos aleatórios de Markov é o que estou estudando agora. Vou postar de volta quando eu souber mais.

Davor Josipovic

17

"Qual é a maneira correta mais teórica da informação / física para calcular a entropia de uma imagem?"

Uma pergunta excelente e oportuna.

Ao contrário da crença popular, é realmente possível definir uma entropia de informação intuitiva (e teoricamente) natural para uma imagem.

Considere a seguinte figura:

Podemos ver que a imagem diferencial possui um histograma mais compacto, portanto sua entropia de informações de Shannon é menor. Portanto, podemos obter redundância mais baixa usando a entropia de Shannon de segunda ordem (ou seja, entropia derivada de dados diferenciais). Se podemos estender essa ideia isotropicamente para 2D, podemos esperar boas estimativas para a entropia de informações da imagem.

Um histograma bidimensional de gradientes permite a extensão 2D.

Podemos formalizar os argumentos e, de fato, isso foi concluído recentemente. Recapitulando brevemente:

A observação de que a definição simples (ver, por exemplo, a definição de entropia de imagem do MATLAB) ignora a estrutura espacial é crucial. Para entender o que está acontecendo, vale a pena retornar brevemente ao caso 1D. Há muito se sabe que o uso do histograma de um sinal para calcular sua informação / entropia de Shannon ignora a estrutura temporal ou espacial e fornece uma estimativa pobre da compressibilidade ou redundância inerente ao sinal. A solução já estava disponível no texto clássico de Shannon; use as propriedades de segunda ordem do sinal, ou seja, probabilidades de transição. A observação em 1971 (Rice & Por exemplo, o melhor preditor de um valor de pixel em uma varredura de varredura é o valor do pixel anterior imediatamente leva a um preditor diferencial e a uma entropia de Shannon de segunda ordem que se alinha com idéias simples de compactação, como codificação de duração da execução. Essas idéias foram refinadas no final dos anos 80, resultando em algumas técnicas clássicas de codificação de imagem sem perda (diferencial) que ainda estão em uso (PNG, JPG sem perda, GIF, JPG sem perda 2000), enquanto wavelets e DCTs são usados apenas para codificação com perda.

Movendo-se agora para 2D; os pesquisadores acharam muito difícil estender as idéias de Shannon para dimensões mais altas sem introduzir uma dependência de orientação. Intuitivamente, podemos esperar que a entropia de informações de Shannon de uma imagem seja independente de sua orientação. Também esperamos que imagens com estrutura espacial complicada (como o exemplo de ruído aleatório do interlocutor) tenham maior entropia de informações do que imagens com estrutura espacial simples (como o exemplo de escala de cinza suave do interlocutor). Acontece que a razão pela qual foi tão difícil estender as idéias de Shannon de 1D para 2D é que existe uma assimetria (unilateral) na formulação original de Shannon que impede uma formulação simétrica (isotrópica) em 2D. Uma vez corrigida a assimetria 1D, a extensão 2D pode prosseguir com facilidade e naturalidade.

Indo direto ao assunto (os leitores interessados podem conferir a exposição detalhada na pré-impressão do arXiv em https://arxiv.org/abs/1609.01117 ), onde a entropia da imagem é calculada a partir de um histograma 2D de gradientes (função de densidade de probabilidade do gradiente).

Primeiro, o pdf 2D é calculado por estimativas binning das imagens x e y derivadas. Isso se assemelha à operação de escaneamento usada para gerar o histograma de intensidade mais comum em 1D. As derivadas podem ser estimadas por diferenças finitas de 2 pixels calculadas nas direções horizontal e vertical. Para uma imagem quadrada NxN f (x, y), calculamos os valores NxN da derivada parcial fx e os valores NxN de fy. Escaneamos a imagem diferencial e para cada pixel que usamos (fx, fy) para localizar uma bandeja discreta na matriz de destino (pdf em 2D), que é incrementada em um. Repetimos para todos os pixels NxN. O pdf 2D resultante deve ser normalizado para ter uma probabilidade geral de unidade (simplesmente a divisão por NxN alcança isso). O pdf 2D está pronto para a próxima etapa.

O cálculo da entropia de informação 2D de Shannon a partir do gradiente 2D pdf é simples. A fórmula clássica de soma logarítmica de Shannon se aplica diretamente, exceto por um fator crucial de metade, que se origina de considerações especiais de amostragem ilimitada em banda para uma imagem de gradiente (consulte o artigo do arXiv para obter detalhes). O meio fator torna a entropia 2D computada ainda mais baixa em comparação com outros métodos (mais redundantes) para estimar entropia 2D ou compressão sem perdas.

Sinto muito por não ter escrito as equações necessárias aqui, mas tudo está disponível no texto de pré-impressão. Os cálculos são diretos (não iterativos) e a complexidade computacional é da ordem (o número de pixels) NxN. A entropia de informação final computada de Shannon é independente da rotação e corresponde precisamente ao número de bits necessários para codificar a imagem em uma representação gradiente não redundante.

A propósito, a nova medida de entropia 2D prevê uma entropia (intuitivamente agradável) de 8 bits por pixel para a imagem aleatória e 0,000 bits por pixel para a imagem de gradiente suave na pergunta original.

Kieran Larkin
fonte

1

Trabalho interessante. Agora, Razlighi fez uma comparação de vários algoritmos de entropia neste artigo . Eu me pergunto como o seu se compara, especialmente na imagem sintética que ele usa lá. Pode valer a pena investigar.

Davor Josipovic

Obrigado por mencionar o artigo de Razlighi. Os resultados cruciais do teste são mostrados na Figura 2. Acredito que minha medida de delentropia 2D teria entropia normalizada unitária para correlação 0,0 e depois cairia para perto de zero entropia normalizada para correlação 1.0. Na verdade, não calculei esses valores, mas segue diretamente a seção 3.2 da minha pré-impressão do arXiv porque a alta correlação corresponde à baixa largura de banda espectral e, portanto, à baixa entropia.

Kieran Larkin

Eu gosto dessa abordagem. Parece intuitivo para mim. O passo adicional de calcular o gradiente antes de calcular a entropia parece codificar a informação espacial intuitivamente. Tentei brincar e calculá-lo com Python aqui . Mas lutei para reproduzir os cáusticos do seu artigo (consulte o código, último exemplo). Só posso reproduzi-los com carros alegóricos! Isso porque, com números inteiros, os gradientes estão em [-6,6] para a minha imagem de teste, mesmo ao usar 16 bits, resultando em apenas 49 posições diferentes de zero para o histograma.

Mxmlnkn 13/07/19

seu artigo foi publicado? Você ou alguém continuou o trabalho?

Andrei

Um código de exemplo do Matlab seria ótimo.

Pedro77 12/07

8

Não existe, tudo depende do contexto e de suas informações anteriores. A entropia tem muitas interpretações, como "medida da ordem" ou "medida da informação", mas, em vez de olhar para as interpretações, você pode apenas olhar para o que realmente é. Entropia é apenas uma maneira de expressar o número de estados de um sistema. Um sistema com muitos estados possui uma alta entropia e um sistema com poucos estados possui uma baixa entropia.

Você e o artigo ao qual você vincula - afirma que as duas imagens têm a mesma entropia. Isso não está correto (para mim).

O artigo calcula corretamente a entropia é.

H = - \sum_{k} p_{k} eu o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

p_{k} = \frac{1}{M} = 2^{- n}

$p_k = \frac{1}{M} = 2^{-n}$

Portanto, a entropia é:

H = - \sum_{k} p_{k} eu o g_{2} (p_{k}) = - \sum_{k} 2^{- n} eu o g_{2} (2^{- n}) = - eu o g_{2} (2^{- n}) = n

$H = - \sum_k p_k log_2(p_k) = - \sum_k 2^{-n} log_2(2^{-n}) = - log_2(2^{-n}) = n$

No entanto, esse não é o caso da segunda imagem.

A entropia ainda pode ser calculada como:

H = - \sum_{k} p_{k} eu o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

$p_k = \frac{1}{M} = 2^{-n}$ $p_1$ $p_2, p_3, p_4 \ldots p_{many}$

Portanto, as duas imagens não têm a mesma entropia.

Pode parecer contra-intuitivo que a entropia dependa de como você olha o problema. No entanto, você provavelmente o conhece por compressão. A compactação máxima de um arquivo é ditada pelo teorema da codificação de origem de Shannon, que define um limite superior para o quão bem um algoritmo de compactação pode compactar um arquivo. Esse limite depende da entropia do arquivo. Todos os compressores modernos compactam um arquivo próximo a esse limite.

No entanto, se você souber que o arquivo é um arquivo de áudio, poderá compactá-lo usando o FLAC em vez de um compressor genérico. O FLAC é sem perdas, portanto todas as informações são preservadas. O FLAC não pode contornar o teorema da codificação de origem de Shannon, isso é matemática, mas pode olhar para o arquivo de uma maneira que reduz a entropia do arquivo e, assim, faz uma melhor compactação.

Identicamente, quando olho para a segunda imagem, vejo que os pixels são classificados pelo valor de cinza e, portanto, não tem a mesma entropia para mim que a imagem com ruído aleatório.

engarrafador
fonte

Eu acho que o OP está ciente se isso - ele está pedindo para os modelos probabilísticos que incluem informação espacial

seanv507

@ seanv507 Reli a pergunta. Não tenho certeza se concordo com você ou não. Acredito que o OP esteja procurando por algo que não existe.

Bottiger

H

$H$

@bottiger FLAC não pode reduzir a entropia de um arquivo de áudio, pois isso, por definição, seria uma compactação com perdas. Ele consegue compactação eliminando redundância.

Paul Uszak

Talvez esteja correto dizer que a fórmula clássica de entropia está correta apenas se os valores de pixel forem estásticamente independentes?

Volperossa 20/05/19

2

Essencialmente, a ideia de entropia é algo como "número de micro-estados consistentes com o macroestado".

$p[\,I,h\,]$ $I$ $p[\,h\mid I\,]$

$h$ $I$

GeoMatt22
fonte

1

H = - \sum_{k} p_{k} eu o g_{2} (p_{k})

$H = - \sum_k p_k log_2(p_k)$

se não funcionar na prática, pela simples razão de que é quase impossível determinar Pk. Você pensa que pode fazê-lo, como fez considerando o número de níveis de cinza. Pk não é isso. Pk é todas as combinações possíveis de níveis de cinza. Portanto, você deve criar uma árvore de probabilidade multidimensional considerando 1, 2, 3 ... combinações de pixels. Se você lê o trabalho de Shannon, vê-o fazer esse cálculo para inglês simples, considerando uma profundidade de 3 letras na árvore. Em seguida, torna-se pesado sem um computador.

Você provou isso com a afirmação 2. É por isso que seu cálculo de entropia retorna o mesmo nível de entropia para as duas imagens, mesmo que uma seja claramente menos ordenada que a outra.

Também não existe esse conceito de distribuição espacial no cálculo da entropia. Se houvesse, você também teria que calcular a entropia de maneira diferente para amostras distribuídas temporalmente. E o que você faria para uma matriz de dados de 11 dimensões? Para entropia informacional; é medido em bytes.

Simplesmente comprima as imagens usando um algoritmo de compactação. Ele produzirá uma estimativa da entropia em bytes. Isso será feito para qualquer imagem ou literalmente qualquer outra coisa que possa ser digitalizada, como música ou peças de Shakespeare.

Tão. Sua imagem aleatória contém aproximadamente 114 KBytes e sua imagem ordenada contém aproximadamente 2,2 KBytes. Isso é o que você esperaria, mas você já sabia disso porque viu que os tamanhos dos arquivos de imagem eram desse tamanho. Reduzi o tamanho compactado em 33% para permitir futuras melhorias nos algoritmos de compactação. Não consigo vê-los melhorando além disso, pois a curva de melhoria está se tornando assintótica para um verdadeiro valor subjacente.

PS: Shakespeare, por interesse, produziu apenas 1 MByte de entropia em toda a obra de sua vida, calculada por essa técnica. A maioria é muito boa.

Paul Uszak
fonte

Entropia de uma imagem

Respostas: