Project Title: Point Cloud Interpolation Using Natural-Neighbors on the GPU
Click here for our presentation video on YouTube!!!
Project and Algorithm Description: Data acquired in certain imaging modalities yield data that does not necessarily lie on a grid. This prevents us from using commonly used interpolation techniques, such as bilinear interpolation, when increasing image resolution, acquiring data that lies between the collected data points, or displaying the data on a screen. Natural-neighbors interpolation enables us to conform the data points to a grid, which enables us to perform the operations mentioned above.
Natural-neighbors interpolation is a method for sampling and constructing a gridded representation of non-gridded data. Natural-neighbors interpolation (NNI) works by combining weighted portions of data from surrounding data points (neighbors) in order to create a new (interpolated) data point at the query location. One method of determining these weights is by forming a Voronoi diagram of the data, and then calculating how much area the new point steals from its neighbors. A Voronoi diagram is a method for partitioning a given set of points. The Voronoi diagram defines the boundary in space that is equidistant from each pair of neighboring points. A major problem here is that calculating the Voronoi diagram is computationally expensive, and serial implementations make it impossible for NNI to be used in real-time.
We use a parallelized method for computing a discretized version of the Voronoi diagram, called the Jump-Flooding Algorithm (JFA), specifically, the 1+JFA variant of this algorithm. In JFA, the original data points are discretized (snapped to a grid) and used as seeds for flooding the grid (we can think of these seeds as holes in the bottom of a boat). It is important to note that, the finer the grid, the more accurate the results are, since the points will be snapped to locations that are closer to their original positions, however increasing the mesh resolution increases the computation time. Each square on the grid is mapped to a thread on the GPU. At every step, the thread looks in eight directions around it and a certain step size away from itself, in order to determine which seed it belongs to. This can be thought of as back-tracing the source of a water molecule on the bottom of my boat; the source of the molecule should be the hole that is closest to the molecule (assuming that water molecules from different sources do not mix). By halving the step size after each iteration, we compute the Voronoi diagram. The 1+JFA variant starts with a step size of 1, then sets the step size to half the width of the grid, and then proceeds with the steps described above. This yields a much more accurate Voronoi diagram, as shown by Rong et al. Now that we can compute the Voronoi diagram of our data, we can interpolate it. The interpolated points will form a grid. For each square in this grid, we can compute how much area this square is stealing from each seed, and divide by the area of the square in order to get the weights for the interpolation. Multiplying these weights by the value the corresponding seed and summing these numbers we get the interpolated value for the square, and we are done. The interpolation process in our program starts by computing the Voronoi diagram of both the original data and the query points. These two diagrams are then compared in the query kernel, and the interpolation weights are determined depending on how much area a query steals from the surrounding Voronoi regions. Interpolation is performed, and the resulting image is saved.
The diagram above is a simplified representation of the path that data follows in the pipeline.
In this example, we have two points at the locations indicated by the blue dots. The image on the left is the Voronoi diagram of these two points.The other two images show the interpolation with a coarse and a fine query grid. Note that the finer query grid results in better interpolation, however takes longer to compute.
	(1)	(2)	(3)
(1) shows the Voronoi diagram of two points. (2) shows the NNI of these two points with a grid spacing of 1. (3) shows the NNI of these two points with a grid spacing of 0.25. Map resolution is 0.01 in all cases, resulting in a 2500 x 2500 image. The blue dots in (2) and (3) show the center of each element on the grid.
In this example, a bitmap image is used as the input. On the left, we feed the full image into the algorithm. On the right, we feed only half of the rows of the image. We can see that the natural neighbors interpolation is able to reconstruct the image quite successfully.
The performance of our algorithm depends mainly on the size of the output image. This is because the jump flooding takes longer to compute as the image width increases. We also observe weaker dependencies on the size of the input and the number of queries. These factors can be minimized by optimizing the code to coalesce memory access. We have met our goal in this project, which was to allow for real-time interpolation of non-gridded data. The jump flooding part of our algorithm performs better than the implementation of the algorithm's creators. Future work includes implementing this process in 3 and 4 dimensions, and interpolating data streams, such as ultrasound images, on the fly.
Future Work: NNI only runs on square grids, however it is quite simple to make it run on rectangular grids. We would like to extend to 3D/4D. Currently, NNI computes the Voronoi diagram for both the input points, and the query points. When the query points are assumed to form a grid, computing the Voronoi diagram is unnecessary, and can be constructed using simpler means that will take much less time. This will reduce the computation time by almost a factor of 2. This is especially important if a stream of data is being interpolated, where the query grid structure remains the same. Comments on Performance: We are quite happy with the performance of our implementation. The runtime seems to increase almost linearly with image size. This is probably mainly due to the atomicAdd function being used in the query_kernel. As we increase the image size, we also increase the number of iterations of the jump-flooding algorithm (# iterations =log_2((image width)). Comments on the Project: This was a highly valuable and enjoyable learning experience. Getting to learn about and practice some of the most recent developments in parallel computing was extremely rewarding and interesting. Although understanding how jump-flooding and computing the Voronoi diagrams took a while, we were able to finish on time. Learning how to write kernels that can adapt to different inputs, and was one of the most valuable lessons we learned from this project. We would like to thank Cris Cecka for his valuable comments and insights on our project. Resources: [1] Fan, Quanfu, et al. "Hardware-assisted natural neighbor interpolation." Proc. 7th Workshop on Algorithm Engineering and Experiments (ALENEX). 2005. [2] Beutel, Alex, Thomas M�lhave, and Pankaj K. Agarwal. "Natural neighbor interpolation based grid DEM construction using a GPU." Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2010. [3] Rong, Guodong, and Tiow-Seng Tan. "Variants of jump flooding algorithm for computing discrete Voronoi diagrams." Voronoi Diagrams in Science and Engineering, 2007. ISVD'07. 4th International Symposium on. IEEE, 2007. [4] Rong, Guodong, and Tiow-Seng Tan. "Jump flooding in GPU with applications to Voronoi diagram and distance transform." Proceedings of the 2006 symposium on Interactive 3D graphics and games. ACM, 2006. [5] D. Maljovec. �Delaunay Triangulation on the GPU�, (presentation) www.cs.utah.edu/~maljovec/files/ DT_on_the_GPU_Print.pdf [6] http://en.wikipedia.org/wiki/Natural_neighbor