1

I would like to implement a somewhat smarter Laplacian edge enhancement convolution. Right now it is implemented as (generic 3x3 convolution):

sum = 0
for k = -1 to 1 do
   for j = -1 to 1 do
      sum = sum + h(j +1, k + 1)*f(x - j, y - k)
   end for
end for
g(x, y) = sum

Looking for way to improve to implementation all I could find was separable filter optimizations (as Fast / Efficient Way to Decompose a Separable integer 2D Filter Coefficients without the SVD). However Laplacian edge enhancement is not separable:

octave:1> m = [-1 -1 -1 ; -1 8 -1 ; -1 -1 -1];
octave:2> rank(m)
ans =  2

Is there any literature I could be missing ? When looking at the coefficients it feels as if somewhat could be done for matrix of type (CENTER=8, EDGE=-1):

E  E  E
E  C  E
E  E  E
lennon310
  • 3,590
  • 19
  • 24
  • 27
malat
  • 164
  • 1
  • 10

1 Answers1

1

OK here I will put an old trick to reduce number of multiplications dramataically, whether it will render a faster result depends on your overall computational architecture of course.

Now as your filter is highly structured, let us denote two values E and C to describe its elements. Lets decompose your filter into two parts: $$h[n,m] = h1[n,m] + h2[n,m]$$ such that: $$h1[n,m] = E*ones(3,3)$$ and $$h2[n,m]=(C-E)*\delta(n,m)$$

here I put a pseudo-language version of your convolution core, that takes advantage of this simple decomposition:

for (n,m)= beginning:end   // it is a double loop
   sum = 0;
   for (j,k)=-1:1         // it is the core double loop
      sum = sum + f(n-j,m,k);   % Here there is no multiplication, saving 9  multiplies
   end:j,k

   g(n,m) = E*sum + (C-E)*f(n,m); % here is two multiplies
end:n,m

Note1: please take care of indices especially at the edges, since I didn't.
Note2: whether your optimizing compiler can already convert your code into this structure, from your previous code, depends on your filter definition. If your filter is defined only by a pointer without its content, the compiler will have no chance to decompose it. But if the filter is statically defined at compile time, then at least in principle the compiler has a chance to analyse its content. Whether they do it or not is another concern...

Fat32
  • 28,152
  • 3
  • 24
  • 50