Básico Complexidade Pergunta - Convolution

Question

Eu estou tentando avaliar a complexidade de alguns algoritmos básicos de filtragem imagem. Eu queria saber se você poderia verificar essa teoria;

Para um pixel de base por filtro de pixel como inverso do número de operações cresce linearmente com o tamanho da entrada (em pixels) e

Seja S = comprimento do lado da imagem Seja M = # pixels de entrada

Inverso é de ordem O (H) ou O (S ^ 2).

Um filtro de convolução, por outro lado tem um parâmetro R que determina o tamanho da vizinhança para convolve no estabelecimento do próximo valor de pixel para cada filtro.

Seja R = raio do filtro de convolução

convolução é de ordem O (H * ((R + R * 2) ^ 2) = O (H * (4R ^ 2) = O (MR ^ 2)

Ou eu deveria deixá-N = o tamanho do filtro de convolução (Bairro) em pixels?

O (H * (N)) = O (MN)

Em última análise, um filtro de convolução é linearmente dependente do produto do número de pixels e o número de pixels na vizinhança.

Se você tiver quaisquer links para um papel onde este tem sido documentado que seria muito apreciado.

Atenciosamente,

Gavin

Answer 1

O (MN) parece certo se eu entender que para cada pixel da imagem a convolução é o ajuste de valores de pixels na vizinhança N, independentemente de N ser quadrado. N poderia ser melhor ajuste triângulo ... mas fornecendo os pixels na vizinhança são ajustados para cada pixel da imagem, em seguida, O (MN) faz mais sentido, porque a dependência é nos pixels ajustados por pixel na imagem de origem.

Curiosamente, em um bairro não regular alguns pixels pode ser ajustado pela máscara bairro mais do que outros, mas O (MN) ainda permanecerá.

Se o bairro é central na um pixel P e, em seguida, mudou-se para a próxima P que não foi no bairro (ou seja, cada pixel é transformado uma vez), então este não resiste.