Base Complessità Domanda - Convolution

Question

Sto cercando di valutare la complessità di alcuni algoritmi di filtraggio immagine di base. Mi chiedevo se si potrebbe verificare questa teoria;

Per un pixel di base per filtra pixel come Inverse il numero di operazioni cresce linearmente con la dimensione dell'input (in pixel) e

Sia S = lunghezza del lato dell'immagine Lasciate ingresso M = # pixel

Inversa è dell'ordine O (M) o O (S ^ 2).

Un filtro convoluzione invece ha un parametro R che determina la dimensione della zona di convolve stabilire il valore di pixel successivo per ciascun filtro.

Sia R = raggio del filtro di convoluzione

convoluzione è dell'ordine O (M * ((R + R * 2) ^ 2) = O (M * (4R ^ 2) = O (MR ^ 2)

O dovrei sia N = la dimensione del filtro di convoluzione (vicinato) in pixel?

O (M * (N)) = O (MN)

In definitiva un filtro di convoluzione è linearmente dipendente dal prodotto del numero di pixel e il numero di pixel nella zona.

In caso di link ad un documento in cui questo è stato documentato che sarebbe molto apprezzato.

Cordiali saluti,

Gavin

Answer 1

O (MN) sembra giusto se comprendo che per ogni pixel nell'immagine della convoluzione è la regolazione dei valori dei pixel nella zona N, indipendentemente N è quadrato. N potrebbe essere triangolo best-fit ... ma fornendo i pixel nella zona sono regolati per ciascun pixel dell'immagine poi O (MN) rende più senso, perché la dipendenza è nei pixel corretti per pixel nell'immagine sorgente.

È interessante notare che, in un quartiere non regolare alcuni pixel possono essere regolati dalla maschera quartiere più di altri, ma O (MN) saranno ancora in piedi.

Se il quartiere è centrale su un pixel P e poi spostato nella successiva P che non era nel quartiere (cioè ogni pixel si trasforma una volta) allora questo non sta in piedi.