Grundlegende Komplexität Frage - Faltung

Question

Ich versuche, die Komplexität einiger grundlegender Bildfilterungsalgorithmen zu bewerten. Ich habe mich gefragt, ob Sie diese Theorie bestätigen könnten;

Für einen Grundpixel Filter wie Inverse der Anzahl der Operationen mit der Größe des Eingangs linear wächst (in Pixel) und

S = Länge der Seite des Bildes sei M = # Pixel zu Lassen Eingabe

Invers ist in der Reihenfolge O (M) oder O (S^2).

Ein Faltungsfilter hat andererseits einen Parameter R, der die Größe der zu faltenden Nachbarschaft beim Erstellen des nächsten Pixelwertes für jeden Filter bestimmt.

Let R = Radius des Faltungsfilters

Convolution von der Ordnung O (M * ((R + R * 2)^2) = O (M * (4R^2) = O (MR^2

)

Oder sollte ich sei N die Größe des Faltungsfilters = (Nachbarschaft) in Pixeln?

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

Letztlich ein Faltungsfilter ist linear abhängig von dem Produkt aus der Anzahl der Pixel und der Anzahl der Pixel in der Nachbarschaft

Wenn Sie irgendwelche Links zu einem Papier haben, wo dies dokumentiert wurde, würde es sehr geschätzt werden.

Mit freundlichen Grüßen

Gavin

Answer 1

O (MN) scheint richtig, wenn ich verstehe, dass für jedes Pixel in dem Bild die Faltung die Anpassung der Pixelwerte in der Nachbarschaft ist N, und zwar unabhängig von N quadratisch . N könnte das am besten passende Dreieck sein ... aber wenn die Pixel in der Nachbarschaft für jedes Pixel in dem Bild eingestellt werden, macht O (MN) mehr Sinn, weil die Abhängigkeit in den Pixeln liegt, die pro Pixel in dem Quellbild eingestellt sind.

Interessanterweise können in einer nicht regulären Umgebung einige Pixel durch die Nachbarschaftsmaske mehr als andere angepasst werden, aber O (MN) wird immer noch stehen.

Wenn die Nachbarschaft auf einem Pixel P zentral ist und dann zum nächsten P verschoben wird, das nicht in der Nachbarschaft war (was bedeutet, dass jedes Pixel einmal transformiert wird), dann steht das nicht.