Multiple small convolutions: image processing

2
votes

I'm writing a CUDA program which will attempt to locate about 35 sub-images, or patterns, within a base image. Each sub-image (pattern) can only exist in a small area (say a 10x10 pixel window) of the base image. The sub-images vary in size from 1000 to 10000 pixels. The base image is 640x480 pixels.

I do this by convolving the sub-image with a sub-section of the base image and if the convolution result is smaller than a threshold, than that is considered a match. I have to do about 100 convolutions per sub-image (since I only check a 10x10 window of allowable positions).

First question: has this been implemented and is it available in Open Source?

Second question: which is the better implementation strategy?

  1. Coarse-grained: Each CUDA thread does a full convolution of the sub-image within the base image. There is one CUDA thread for each sub-image and position.
  2. Fine-grained: each CUDA thread computes one component (pixel) of the convolution: so, the CUDA thread multiples a pixel of the sub-image by the appropriate pixel of the base image. Then, use syncblock() to sum these multiples.

UPDATE: I trid both approaches. I think the best method is a variant on method one where I divide the larger sub-images into smaller sub-images. Now all the sub-images are approximately the same size (say, 1024 pixels). Then each CUDA thread does a full convolution for a single position. When done, I send all results to the host, and the host is responsible for putting the intermediate pieces back together (for the sub-images that were divided into smaller pieces). The advantage is that all CUDA threads perform the same amount of work. This seems to be twice as fast as the second approach, which is problematic since the sub-images vary in size.

1
image-processingcuda
Have you checked if opencv provieds similar functions? - kangshiyin
Have you taken a look at the convolutionSeparable and convolutionTexture samples? Why are not using FFTs to perform convolutions (see the convolutionFFT2D example)? Are the matrices too small for FFTs? In that case, approaches for fastly calculating FFTs of small matrices in CUDA could be of interest. Finally, are you considering using dynamic parallelism? For the latter two, have a look at my answer to the Best approach for convolution of multiple small matrices using CUDA. - Vitality
OpenCV might provide these functions, but is OpenCV implemented in CUDA? I already have the serial C code, and it's trivial. But I want a CUDA implementation for speed. - JB_User
The matrices are typically 1000 to 10000 pixels. I can't believe FFTs will be faster then doing a pixel-by-pixel multiply/accumulate of the sub-image with the base image. - JB_User
Do you mean that your convolution result for each sub-image is a 10x10 matrix, which is same as your allowable positions ? - kangshiyin

1 Answers

1
votes

I suggest you use 1 cuda thread block (containing multiple cuda threads) for each sub-image and position.

Since your sub-images vary in size, batched processing all sub-images in 1 kernel may not be a good choice. You could design a kernel to do one full convolution of the sub-image with the base image and invoke it 35 times for each sub-image.

In the kernel, the grid contain multiple thread blocks, whose number is equal to the number of the allowable positions. Each thread block then compute the sum of the multiples of the pixels between the sub-image and the given position of the base image.

This is similar to your strategy 2. The main difference is each thread may compute multiple pixels and the kernel uses only one thread block to do the summation, which does not need synchronization between thread blocks through global memory.

Suppose your sub-image have 2000 pixels, the allowable position is 10x10. You could create a kernel containing 100 blocks, each block containing 256 threads. The 256 threads within a block will do the parallel sum of the 2000 multiples of pixels.

UPDATE

Your proposed approach may have 2 issues,

  1. too few threads per kernel. as you described your kernel may have 10x10=100 threads for the allowable positions, and each thread sum up about 1024 multiples of pixels. generally you may need at least 32 thread blocks and 64~256 threads per block in a kernel to fully utilize the GPU.
  2. more kernel launches often means more launching overhead and lower speed, so partitioning sub-image into smaller ones is not a good choice.

binary-tree-like parallel reduction is actually faster then linear reduction. you could find parallel reduction sample code here

http://docs.nvidia.com/cuda/cuda-samples/index.html#cuda-parallel-reduction

and a good whitepaper here

http://docs.nvidia.com/cuda/samples/6_Advanced/reduction/doc/reduction.pdf