Circle parameters estimation using Hough transform implemented on GPGPU

摘要

In the paper implementation of the Hough transform using Nvidia CUDA platform is considered. The GPGPU implementation is based on processing in parallel a set of Hough transforms with synchronized memory accesses for better utilization of the texture cache. The best code variant is based on quadrature sine and cosine functions, an unrolled loop and a single write to the global memory. The processing time is about 1000 shorter in comparison to the Matlab code, which is necessary for processing the video data.%W artykule rozpatruje się implementację transformaty Hougha [1] dla okręgów (1). Celem implementacji jest skrócenia czasu przetwarzania wielu obrazów o dużej rozdzielczości na potrzeby estymacji położenia i promienia pólsferycznego próbnika oświetlenia stosowanego [3] podczas pomiarów światła na potrzeby realistycznej grafiki i animacji komputerowej (rys. 1). Kolorowy obraz przetwarzany jest za pomocą algorytmu [2] (rys. 3), a w celu redukcji czasu przetwarzania skoncentrowano się na wykorzystaniu platformy NVidia CUDA 3.2 [5, 6] do równoległej realizacji transformaty Hougha [7-12]. Wykorzystano oryginalną konfigurację bloków wątków oraz siatki w celu efektywnego wykorzystania pamięci podręcznej tekstur przy równoległym próbkowaniu obrazu. W implementacji 32 wątki bloku wykonują transformatę Hougha pobierając wartości obrazu z pierścienia w sposób synchroniczny w celu optymalizacji wykorzystania pamięci tekstur. Porównano 14 metod wyznaczania (tab. 1) próbkowanego piksela. Porównano metodę zapisu wyniku najlepszego dla bloku z wykorzystaniem jednego i wszystkich wątków. Najbardziej efektywnym rozwiązaniem jest wykorzystanie funkcji kwadraturowej wraz z rozwijaniem pętli i pojedynczym zapisem. Dla procesora G80 (Geforce 8800 GTS) uzyskano 1000-krotne przyspieszenie obliczeń w stosunku do kodu w Matlabie wykonywanego na procesorze Pentium 4 (2.4GHz). Dla 32 sąsiednich promieni i 100 próbek każdego okręgu czas przetwarzania jest rzędu 1 sekundy.