Grund Komplexität Frage - Convolution

Question

Ich versuche, die Komplexität einiger grundlegender Bildfilteralgorithmen zu bewerten. Ich habe mich gefragt, ob Sie diese Theorie überprüfen könnten;

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

Es sei S = Länge der Seite des Bildes Sei M = # Pixel Eingabe

Inverse von der Ordnung O (M) oder O (S ^ 2).

Ein Faltungsfilter auf der anderen Seite hat einen Parameter R, der bei der Festlegung des nächsten Pixelwertes für jeden Filter der Größe der Nachbarschaft zu convolve bestimmt.

Es sei R = Radius der Faltungsfilter

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

Oder soll ich sei N die Größe des Faltungsfilters (Umgebung) in Pixel =?

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

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

Wenn Sie irgendwelche Links haben auf ein Papier, wo dies dokumentiert ist wäre es sehr geschätzt werden.

Mit freundlichen Grüßen

Gavin

Answer 1

O (MN) scheint richtig, wenn ich verstehe, dass in dem Bild für jedes Pixel der Faltung der Anpassung der Pixelwerte in der Nachbarschaft N ist, unabhängig von N Platz zu sein. N könnte Best-Fit-Dreieck sein ... aber die Pixel in der Nachbarschaft bietet für jedes Pixel in dem Bild eingestellt dann O (MN) mehr Sinn macht, da die Abhängigkeit in den Pixeln pro Pixel im Quellbild eingestellt.

Interessanterweise wurde in einer nicht-regulären Nachbarschaft einige Pixel kann durch die Nachbarschaft Maske mehr als andere eingestellt werden, sondern O (MN) wird nach wie vor stehen.

Wenn die Nachbarschaft auf einem Pixel P ist von zentraler Bedeutung und bewegte dann zum nächsten P, die nicht in der Nähe war (was bedeutet, jedes Pixel einmal transformiert), dann bedeutet dies nicht stehen.