# Fast Planar Detection System Using a GPU-Based 3D Hough Transform for LiDAR Point Clouds
## 3 Planar Detection System Using GPU-Based 3D Hough Transform
### Flag Map Generation  
In the 3D connected component labelling algorithm, a 3D flag map \(L\) is generated as a reference to mark the high-value cells in the Hough space buffer \(H\). The generated Hough space and its corresponding 3D flag map, where \(\theta\), \(\varphi\), and \(r\) are their coordinates. The sizes in length, width, and height of both the Hough space and 3D flag map are same. Using Equation (4), the flag map is initialized by allocating each cell with a unique label before the connected component labeling iteration process. The index pair \((i,j,k)\) presents the cell's location in three directions at the Hough space (\(\theta\), \(\varphi\), \(r\)). The \(h\)\((i,j,k)\) is the cell value at Hough space buffer. The equation \(l\)\((i,j,k)\) represents the cell values of the flag map, where \(i\), \(j\), \(k\) is the cell index in three parameters \(\theta\), \(\varphi\), and \(r\) at the flag map. When cell values \(h\)\((i,j,k)\) in a Hough space buffer are larger than a predefined threshold \(\gamma\), the corresponding values \(l\)\((i,j,k)\) in the flag map are initialized as their unique location indices, as shown in Equation (4), where \(l\), \(J\), \(K\) represents the count of cells at the three dimensions \(\theta\), \(\varphi\), and \(r\). Otherwise, when cell values \(h\)\((i,j,k)\) are less than \(\gamma\), meaning not high-value  
Figure 2: The graphical illustration of a Cartesian coordinate and a 3D Hough space. (**a**) The Cartesian coordinate. (**b**) The Hough space. valid cells in the Hough space, the corresponding values \(l\) (\(i,j,k\)) in the flag map are set as invalid. In this way, each valid cell in the flag map owns a unique value. \[l(i,j,k)=\left\{ \begin{array}{cc}i+k\times I+j\times I\times K&h(i,j,k)\geq \gamma\\ -1&h(i,j,k)<\gamma\end{array} \right. \tag{4}\]  
The self-adaptive threshold value \(\gamma\) is computed according to Equation (5). The threshold \(\gamma\) is indicated based on the maximum value \(H_{max}\) and the average value \(H_{aver}\) of the Hough space. The factor \(\lambda\) is a constant usually located in interval [0.6, 0.8] in our experiment. \[\gamma=H_{\text{max}}-\lambda*(H_{\text{max}}-H_{aver}) \tag{5}\]  
After flag map initialization, a neighbour clique descriptor \(N_{c}\) of the cell \(c\) (\(i,j,k\)) is defined as Equation (6). All valid cells in the 3D flag map is defined as a set \(S\). The distance between centre cell \(c\) (\(i,j,k\)) and its neighbour cell \(c^{\prime}\) (\(i^{\prime},j^{\prime},k^{\prime}\)) is limited. When the distance is less than or equal to a distance threshold \(d\), the \(c^{\prime}\) (\(i^{\prime},j^{\prime},k^{\prime}\)) is considered as belonging to the descriptor \(N_{c}\). \[N_{c}=\left\{c^{\prime}\in S\middle|\sqrt{(i_{c^{\prime}}-i_{c})^{2}+(j_{c^{ \prime}}-j_{c})^{2}+(k_{c^{\prime}}-k_{c})^{2}}\leq d,c\
eq c^{\prime}\right\} \tag{6}\]  
If the threshold \(d\) is equal to 1, a neighborhood clique descriptor contains 6 neighboring cells (\(i^{\prime},j^{\prime}\), \(k^{\prime}\)), as shown in Figure 3. In a 3D flag map updating process, a minimal value is searched out from the value \(l\) (\(i,j,k\)) of the center cell and values \(l\) (\(i^{\prime},j^{\prime},k^{\prime}\)) of its neighboring cells using the descriptor. The center cell value \(l\) (\(i,j,k\)) is subsequently updated as the searched minimum through several iterations based on Equation (7). Variable \(t\) means the iteration time in the label updating process. The values of all valid cells in the flag map are traversed using descriptors for several times until there are no values changes anymore. \[l_{t+1}(c)=\min(\forall l_{t}(c^{\prime}))\ \ \ \ \ c^{\prime}\in N_{c} \tag{7}\]  
In this way, the cells belonging to a same connected component are updated as the same flag value. Each component containing several connected cells has a unique flag value. By matching the flag map to the Hough space, cells owing the same flag value are clustered into same clusters at the Hough space.