Keywords: quantum algorithms, high-performance computing, model simplification, point cloud, visualization.

In this paper we introduce a new quantum algorithm to address a problem of great recent interest in computer graphics: the simplification of large data sets for interactive visualization. Such an example is the simplification of point clouds acquired using three-dimensional laser scanners. These devices are able to produce immense amounts of data and the model simplification techniques developed so far have been motivated by the need to reduce the size of such data sets in order to obtain multi-resolution models and to speed-up the rendering.

One such state of the art high quality point cloud simplification technique produces an efficient hybrid representation of the point cloud consisting of textured quads, that replace the large planar surfaces, and remaining points, used to represent highly detailed areas. Identifying the planar subsets in the point cloud and replacing them with textured quads drastically reduces the number of vertices in the model. Thus, the rendering can exploit the fact that on current graphics hardware, the fill rate is 10 to 20 times higher than the vertex transformation rate. In order to detect the planar structures in the point cloud, the random sample consensus (RANSAC) algorithm is used and even though it achieves indisputable results, its time complexity represents a major drawback especially when dealing with very large data sets. From this perspective, we provide a solution that exploits the advantages of the inherent parallelism of quantum systems and introduce a quantum algorithm that implements the RANSAC voting scheme for plane detection in point clouds.

In particular, our aim was to reformulate the algorithm in order to be able to exploit the special properties of quantum superposition. We identified the steps of the algorithm that could be stated in the terms of a search problem and provided the variants of Grover's algorithm suited for solving these specific steps. Thus, we reformulated the algorithm in terms of the approximate counting of the number of solutions to a search problem, searching for a maximum value in a data set and retrieving multiple solutions to a search problem using the semicloning protocol. Before introducing our quantum variant of the RANSAC voting scheme, we present the idea behind Grover's search algorithm and discuss the variants involved in solving various steps of our quantum RANSAC algorithm.

The performance of our quantum algorithm is orders of magnitude faster than its classical variant and represents a promising result for the investigation of more such applications of quantum computing to computer graphics an vision tasks. Building a working quantum computer represents a very challenging task that requires spending a huge amount of resources. Developing efficient quantum algorithms for practical problems would therefore help in justifying these immense efforts.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £72 +P&P)