稀疏子空间聚类算法及其在运动分割中的应用研究

发布时间：2019-07-06 15:10

【摘要】：如今社会,人们不满足于仅仅播放多媒体信息,转向基于视频对象的访问、检索和操作,于是基于视频的运动分割技术成为了研究重点。运动分割是将视频中有着不同运动的物体分开,是基于对象的视频编码、视频检索、多媒体交互的基石。传统的运动分割算法采用运动目标检测和目标跟踪,在利用帧差法和光流法对运动目标检测时,极易受到噪声的影响,目标跟踪又涉及目标的遮挡、扭曲和变形等问题,于是复杂场景下进行运动分割很难得到理想效果。通过转换问题的角度,采用稀疏子空间聚类算法,避开运动检测和目标跟踪遇到的难题,来实现复杂场景下的运动分割。基于同一运动的特征点轨迹在同一线性流形上,于是可以利用稀疏子空间聚类算法对特征点轨迹进行聚类来实现运动分割。稀疏子空间聚类算法在处理高维数据时,能够将高维数据分割到所属的低维子空间中去,揭示高维数据所在本质子空间,算法可以同时处理奇异点和噪声对聚类的影响,针对稀疏子空间算法的研究,本文做了如下工作:(1)通过对比k-means算法,深入研究自适应谱聚类算法。由于稀疏子空间聚类算法是基于谱聚类,对谱聚类的相关基础和理论知识做了深入研究,分析谱聚类的研究成果和应用现状,针对谱聚类需要手动输入聚类数目的缺点,本文依据矩阵的扰动理论,同时计算矩阵的特征间隙,从而实现聚类算法自动确定聚类数目。为了证明谱聚类算法能处理任意样本形状的数据集,而且不陷入局部最优,本文选取各种形状的样本集进行实验,同时用k-means算法处理这些样本集,通过实验对比,发现自适应谱聚类算法在处理样本集上的优势。(2)提出混合最小二乘回归的稀疏子空间聚类算法。针对稀疏子空间聚类算法如何构造真实合理反映数据集的相似度矩阵的问题,相似度矩阵既要类间稀疏又要内类均匀,这样才能保证属于同一个类的数据点相似度最大,属于不同类的数据点相似度最小,对于样本集存在各种噪声点、奇异样本点和孤立点,本文采用数据项矩阵来处理噪声的影响,通过分析稀疏子空间聚类专注于每一个数据表示系数的最大稀疏性,缺乏对数据集全局结构的描述;低秩子空间聚类算法保证了同一类数据的结构相关性,但是不够稀疏。本文决定将最小二乘回归引入稀疏子空间聚类算法中,从而保证数据的相似度矩阵兼具稀疏性和分组效应,并用数据集验证改进算法性能。(3)研究改进稀疏子空间聚类算法在运动分割中的应用。将稀疏子空间聚类算法应用于视频对象处理中,建立运动分割模型,进行运动分割实验,实验结果表明,改进的算法在保证时间复杂度的情况下,提高了运动分割的准确率。
文内图片：

图片说明：无向图G
[Abstract]:Nowadays, people are not satisfied with just playing multimedia information, but turn to video object-based access, retrieval and operation, so video-based motion segmentation technology has become the focus of research. Motion segmentation is the cornerstone of object coding, video retrieval and multimedia interaction, which separates objects with different motion in video. The traditional motion segmentation algorithm adopts moving target detection and target tracking. When using frame difference method and optical flow method to detect moving target, it is easy to be affected by noise. Target tracking also involves the occlusion, distortion and deformation of the target, so it is difficult to get the ideal effect of motion segmentation in complex scene. From the point of view of the problem, sparse subspace clustering algorithm is used to avoid the problems encountered in motion detection and target tracking, so as to realize the motion segmentation in complex scenes. The feature point trajectory based on the same motion is on the same linear manifold, so the sparse subspace clustering algorithm can be used to cluster the feature point trajectory to realize motion segmentation. When dealing with high-dimensional data, sparse subspace clustering algorithm can segment high-dimensional data into its own low-dimensional subspace, reveal the local proton space of high-dimensional data, and the algorithm can deal with the influence of singularity and noise on clustering at the same time. aiming at the research of sparse subspace algorithm, this paper does the following work: (1) by comparing k-means algorithm, the adaptive spectral clustering algorithm is deeply studied. Because the sparse subspace clustering algorithm is based on spectral clustering, the related basic and theoretical knowledge of spectral clustering is deeply studied, and the research results and application status of spectral clustering are analyzed. Aiming at the disadvantage that spectral clustering needs to manually input the number of clustering, this paper calculates the characteristic gap of matrix according to the perturbation theory of matrix, so as to realize the automatic determination of clustering number by clustering algorithm. In order to prove that spectral clustering algorithm can deal with arbitrary sample shape data sets, and does not fall into local optimization, this paper selects various shapes of sample sets to carry out experiments, and uses k-means algorithm to deal with these sample sets. Through experimental comparison, the advantages of adaptive spectral clustering algorithm in dealing with sample sets are found. (2) mixed least square regression sparse subspace clustering algorithm is proposed. In order to solve the problem of how to construct the similarity matrix which truly and reasonably reflects the dataset, the similarity matrix should be sparse between classes and uniform within classes, so as to ensure that the similarity of data points belonging to the same class is the largest and the similarity of data points belonging to different classes is the smallest. For the sample set, there are all kinds of noise points, singular sample points and isolated points. In this paper, the data item matrix is used to deal with the influence of noise. By analyzing the sparse subspace clustering, it focuses on the maximum sparsity of each data representation coefficient, and lacks the description of the global structure of the data set. The low rank subspace clustering algorithm ensures the structural correlation of the same kind of data, but it is not sparse enough. In this paper, we decide to introduce least square regression into sparse subspace clustering algorithm, so as to ensure that the similarity matrix of data has both sparsity and grouping effect, and the performance of the improved algorithm is verified by data set. (3) the application of improved sparse subspace clustering algorithm in motion segmentation is studied. The sparse subspace clustering algorithm is applied to video object processing, and the motion segmentation model is established and the motion segmentation experiment is carried out. the experimental results show that the improved algorithm improves the accuracy of motion segmentation under the condition of ensuring the time complexity.
【学位授予单位】：重庆理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.41;TP311.13

【参考文献】