OpenCL kernel or Shader to find in radius of X pixels around each pixels, highest and lowest greyscale value

[Lapin]

Hello.
I'm working on a tool, in this tool I need to process images.
I'll go straight to the point.
For an image, i need to loop thru each pixels(1) and for all the other pixels(2) if distance pixel(1)->pixels(2) < radius then pick the lowest and the highest greyscale value.

My image format is : greyscale 16bit depth.

If you don't understand, here is a draw :




In other words,

Code: Select all

for each pixel on the image (or in the 2D array) : PIXEL_MAIN
 ­  ­  ­ for each pixels where distance pixel->PIXEL_MAIN < radius
   ­      get min and max value, if PIXEL_MAIN is closer to MAX then make it white, else, make it black

Circle radius is defined on the kernel/shader call, and we need to do this for every single pixel.

If the main pixel is closest to the max one than the min one then we make it white, else it turns black.

Also, if the whole circle is "kinda dark" , the pixel gets goes black even if it's the "highest value" in the circle.

i wrote a OpenCL kernel that does this, but the algorithmic complexity is terrible O(nPixel*(pi*r²))

Code: Select all

__kernel void simple_demo(__global ushort *src, __global ushort *dst,
                          ushort width, ushort height, ushort depth,
                          ushort radius, __global ushort *frameMinColorArray,
                          int progress) {
  int i = progress + get_global_id(0);

  int index = i;
  ushort z = i / (int)((int)width * (int)height);
  i -= (z * width * height);
  ushort y = i / width;
  ushort x = i % width;
  ushort pixelColor = src[index];
  ushort min = pixelColor;
  ushort max = pixelColor;

  short y2 = -radius;
  while (y2 <= radius) {
    short x2 = -radius;
    while (x2 <= radius) {
      if ((x2 * x2 + y2 * y2) < (radius * radius)) {
        short x3 = x + x2;
        short y3 = y + y2;
        if (x3 >= 0 && x3 < width && y3 >= 0 && y3 < height) {
          int circlePixelIndex = (z * width * height) + (y3 * width) + x3;
          ushort circlePixel = src[circlePixelIndex];
          if (circlePixel > max)
            max = circlePixel;
          if (circlePixel < min)
            min = circlePixel;
        }
      }
      x2++;
    }
    y2++;
  }

  ushort mid = min + (max - min) / 2;

  if (max > frameMinColorArray[z] && pixelColor > mid)
    dst[index] = 65535;
  else
    dst[index] = 0;
}

src was a 3 dimentional array I flattened to a 1 dimension one (because OpenCL kernels only takes 1D kernels), 3D one because it contains multiple frames


Could I do this with a Shader ? Would it be faster than the OpenCL kernel ?
I tried to toy with the kernel but i couldn't get my head around the position (using vectors(??) instead of pixel positions is weird)

[Lapin]

I managed to milk few MS with a preprocessor and #pragma unroll, but it "only" a 50% boost

[nameless tee]

Yes, you could also do this using a shader but I don't know whether it'd be slower or faster (assuming you're using OpenCL on the GPU).

The main problem with your approach is that the kernel is doing a lot or redundant work. It is possible to separate the circle into parts that can be computed separately and then reused many times. For example you could do something like this:



Here you'd split the operation into five steps with intermediary results for each pixel:

1. compute min/max along vertical line
2. combine results from step 1 along two horizontal arcs
3. compute min/max along horizontal line for each pixel
4. combine results from step 3 along two vertical arcs
5. compute min/max on results from steps 2 and 4

This would give you a complexity of O(n*r). I'm sure there will be better ways to do this, so it might be a good idea to search for literature on this problem (these kinds of problem come up a lot in computer vision), but this was the best I could come up with.