Research On Superpixel And Supervoxel Segmentation Algorithms Based On Quadratic Error Metrics

Superpixel or supervoxel segmentation is an important technology in the field of computer vision,and it is the basis of many graphics and visual processing.Usually,we call the over-segmentation result of a 2D image as the superpixel,and the over-segmentation result of a 3D video or point cloud as the supervoxel.Most segmentation algorithms define a distance function in the feature space to measure the similarity between pixels.The quadratic error-based distance metric plays an important role in image,video and point cloud segmentation algorithms.Since the quadratic energy can be converted into matrices of different forms,only a series of matrix operations need to be performed when calculating the energy change of a pixel set,regardless of the number of pixels in it,so the energy optimization algorithm is efficient.We define quadratic distance metrics for different data types,and combine various optimization frameworks to solve data segmentation problems.The current challenge of image over-segmentation is that the detection of weak boundaries with similar colors on both sides is not accurate enough,and it is easy to collect objects on both sides of the weak boundary into the same superpixel.In response to this problem,this thesis proposes a superpixel generation algorithm based on quadratic error minimization.The superpixels generated by our method are very sensitive to color changes and can accurately segment object boundaries.The main contributions are as follows:(1)A quadratic distance metric is designed based on color and coordinate space.Based on this,we can convert the energy calculation of superpixels into matrix operations.(2)We propose a bottom-up greedy merging algorithm.By calculating the merging cost between superpixels,the superpixels are continuously merged in decending order of merging cost until the number of superpixels reaches the pre-set value.(3)On the basis of the merging algorithm,an optimization algorithm is designed to try to reduce the overall segmentation energy by updating the superpixel labels to which the boundary pixels belong.Due to the energy definition in quadratic form,the merge and update operations in the algorithm can be transformed into a series of matrix operations,which ensures the efficiency of the method.The superpixels generated by our algorithm can not only detect the weak boundary of the image,but also have a regular shape,which shows a huge advantage in the quality of superpixel segmentation compared with existing methods.At present,the biggest problem faced by video over-segmentation is the difficult balance between quality and efficiency.In order to obtain high-quality video supervoxel segmentation more quickly,this thesis proposes an anisotropic supervoxel generation algorithm based on GPU.This algorithm is based on seed-based segmentation method.The main optimization techniques are as follows:(1)An anisotropic distance metric is designed for the seed points using the video optical flow field,which helps to segment moving objects.(2)A simple and effective seed point initialization strategy is proposed to adaptively adjust the distribution of seed points to segment objects more accurately.(3)In order to ensure quality and efficiency at the same time,we design a parallel algorithm that can be implemented on GPU,so that the processing speed of the algorithm in this thesis far exceeds existing algorithms.Experiments prove that the video supervoxel algorithm proposed in this thesis achieves a high balance between segmentation quality and processing efficiency,and is the best choice for video segmentation of moving objects.Point cloud over-segmentation also faces the same inefficiency problem.This thesis proposes a high-quality supervoxel parallel algorithm for point clouds.Different from videos,point cloud data is disordered and sparse.We first organize the data into voxels,and take voxels as the basic processing unit for segmentation.The algorithm mainly has the following innovations:(1)Define the quadratic error metric suitable for point cloud segmentation,and convert the energy calculation into matrix and vector operations.(2)We propose a clustering algorithm that can be implemented in parallel,using Lloyd iterations to generate the initial point cloud segmentation.(3)We design an optimization algorithm to further update the supervoxel segmentation.By changing the supervoxel label to which each voxel belongs,the energy of point cloud segmentation is gradually reduced and the compactness of the supervoxel is improved.The two-stage algorithm can be highly parallelized on the GPU,so it can process faster than existing methods.In addition,the algorithm generates compact supervoxels which preserve the sharp features of objects.Experiments show that GPU-based supervoxels can generate segmentation results for large point clouds very quickly.