基于组合Hodge理论的图像视频质量评价方法

Image/video quality assessment lies in the core topics in multimedia analysis community, and plays an important role in a broad range of applications, e.g. collection, display, storage, transmission, compression, etc. With the advent of ubiquitous Internet access, crowdsourcing strategy provides us a new opportunity to conduct user studies from an Internet crowd in Big Data era. Since such a crowd can be quite large, crowdsourcing enables researchers to conduct experiments with a more diverse set of participants at a lower economic cost than would be impossible under laboratory conditions. Among various subjective measures, paired comparison method is expected to yield more reliable results and thus a desired approach to collect crowd data via Internet. However, paired comparison leaves a heavier burden on participants with a larger number of comparisons. Therefore, we exploit a randomized sampling scheme based on random graph theory where small subsets of all possible pairs are randomly chosen for each assessor to view. Equipped with recent developments in random complex theory, we further derive the constraints on sampling complexity (i.e., O(nlogn) distinct random edges are necessary to ensure the inference of a global ranking and O(n^2/3) distinct random edges are sufficient to remove the global inconsistency). Based on this, we then make a comprehensive analysis of the performance between random sampling and active sampling in sparse sampling case. Moreover, to deal with possibly incomplete and imbalanced data emerged from random sampling, we introduce a unified statistical reconstruction methodology, based on Hodge Theoretical approach to statistical ranking. Then extend it to an effective online setting considering the streaming and dynamic attributes of the data in crowdsourceable scenarios. Additionally, since participants perform experiments without supervision, the quality of the data we collected is not all trustworthy. We therefore attempt to establish a Huber-LASSO-based method for outlier detection in this project.

图像视频质量评价是多媒体分析领域的核心研究之一，其在采集、显示、存储、传输、压缩等领域都发挥着重要作用。由于传统实验室环境下的主观测试代价昂贵，网络众包因其具有成本低、参与人员广泛、数据量大等优点，提供了大数据时代下通过群体来完成主观评测的新途径。鉴于此，本项目采用网络众包收集比对数据，考虑到比对测试法存在样本组合数据量过大的问题，本项目从基于随机图的采样方法入手，利用拓扑约束得到采样率的下界，并在此基础上研究稀疏采样条件下随机采样和主动采样的性能差异。考虑到网络众包收集的数据具有不完全、不均衡、在线收集的特点，本项目引入几何拓扑学中的组合Hodge理论构建重建被测函数，并在此基础上发展在线、快速的评价方法，为网络众包实验中遇到的动态序列数据提供高效的处理手段。此外，考虑到测试者是在无监督环境下进行测试，数据质量有很大的不确定性，本项目提出基于Huber-LASSO的去除异常样本的方法。

近年来，随着一些外包平台的出现，如：Amazon Mechanical Turk (MTurk)， CrowdFlower, Innocentive, Allourideas, CrowdRank等，越来越多的研究者把主观评测任务放到网上让大众来共同完成，即网络众包（Crowdsourcing） 技术。与传统的外包技术不同，网络众包是把任务外包给网络上不确定的个体，比传统的实验室测试成本要低。因而，最近一些研究者通过网络众包做些与图像标注、文件关联、文档评估、情感挖掘、以及图像视频质量评价等方面相关的测试。在众多的主观评价测试方法中，成对比较法被认为是可信度较高的一种，因此本项目采用成对比较法进行测试。然而，考虑到网络众包下测试者是在无监督环境下进行测试，测试流程难以控制，本项目从基于随机图的采样机制入手，系统研究了Erdös-Rényi随机图、随机正则图和Preferential Attachment随机图三种随机图指导下的采样机制。实验结果表明这三种随机图指导下的采样模式都没有降低评价的准确率因而都很有应用前景。具体地，由于随机正则图固有的均衡属性，在采样率比较低的时候，它的实验性能要优于Erdos-Renyi随机图。但是，随着采样率的增加或待测对象数量的增加，它们的实验性能越来越接近，使得Erdos-Renyi随机图这种基于I.I.D.（独立同分布）的采样模式几乎可以逼近隶属于依赖型采样的随机正则图的实验结果。此外，由于preferential attachment随机图具有“Rich-get-Richer”属性，使得它在得到top-k的排序时更具优势。第二，基于代数连通性，我们成功提出了一种效率更高的混合采样模式，初期采用贪婪采样后期采用随机无放回采样。第三，针对网络众包收集到的动态流数据，我们提出了一种基于随机梯度下降的在线算法，它不但效率高，而且能和批量HodgeRank的性能接近。通过这个方法，我们还可以实时跟踪图的拓扑结构变化和每个时刻不一致程度的值。最后，我们提出了一种基于Huber-LASSO的进行统计抑噪的方法从而得到更加鲁棒的结果。在此基础上，我们还提出了一种基于Linearized Bregman Iteration的异常样本检测方法，与LASSO相比，该方法更加简单、快速、无偏差，因而适合大数据。总之，本项目中我们所提出的方法在仿真和真实