Redukowanie czasu obliczeń transformaty Hougha z wykorzystaniem preselekcji implementowane na GPGPU

W artykule przedstawiono algorytm rzadkiego próbkowania okręgu dla transformaty Hougha, w celu preselekcji okręgów do dalszego przetwarzania. Rozwiązanie pozwala na skrócenie czasu obliczeń, rzędu dwóch razy dla implementacji z wykorzystaniem programowanej karty graficznej (GPGPU). Może ono być zastosowywane do wykrycia jednokolorowej kryzy wokół lustra sferycznego lub półsferycznego służącego do pomiaru oświetlenia. Dzięki temu można analizować obraz wideo zawierający pomiary z różnych obszarów.

The Hough Transform (HT) is a very powerful algorithm for the detection of shapes. It is used for the detection of the flange of a light probe (Fig. 1). GPGPU processing is necessary for HT computation. The proposed algorithm (Fig. 4) is based on the preselection of circles for further computation (Fig. 3). Selection of the circles based on a limited set of pixel samples allows reduction of the processing time up to two times. The reduction is dependent on the image content, but the test shows that the influence of the number of the tested radiuses is less. About one second of the processing time is necessary, so larger images need tens of seconds for computation (Fig. 5). This algorithm uses exhaustive search over all positions and radiuses. One of the interesting applications of the HT is the estimation of the position and diameter of a circle related to the flange of a light probe [2, 3]. Light probes are used for computer graphics applications and they allow application of the real world measurements of light using the Image Based Lighting (IBL) technique. The GPGPU implementation use CUDA based code (CUDA v4.0) [10,11] and 16x8 organization of threads is assumed. The technique proposed for the time and spatial synchronization of the multiple threads for more synchronous read operation from a global memory is applied [7]. The global memory is large and slow, so a GPGPU-global memory interface is the main bottleneck of the system. Synchronization of accesses allows coalescence read operations.