Random partial paired comparison for subjective video quality assessment via hodgerank

Subjective visual quality evaluation provides the groundtruth and source of inspiration in building objective visual quality metrics. Paired comparison is expected to yield more reliable results; however, this is an expensive and timeconsuming process. In this paper, we propose a novel framework of HodgeRank on Random Graphs (HRRG) to achieve efficient and reliable subjective Video Quality Assessment (VQA). To address the challenge of a potentially large number of combinations of videos to be assessed, the proposed methodology does not require the participants to perform the complete comparison of all the paired videos. Instead, participants only need to perform a random sample of all possible paired comparisons, which saves a great amount of time and labor. In contrast to the traditional deterministic incomplete block designs, our random design is not only suitable for traditional laboratory and focus-group studies, but also fit for crowdsourcing experiments on Internet where the raters are distributive over Internet and it is hard to control with precise experimental designs. Our contribution in this work is three-fold: 1) a HRRG framework is proposed to quantify the quality of video; 2) a new random design principle is investigated to conduct paired comparison based on Erdos-Re??nyi random graph theory; 3) Hodge decomposition is introduced to derive, from incomplete and imbalanced data, quality scores of videos and inconsistency of participants' judgments. We demonstrate the effectiveness of the proposed framework on LIVE Database. Equipped with random graph theory and HodgeRank, our scheme has the following advantages over the traditional ones: 1) data collection is simple and easy to handle, and thus is more suitable for crowdsourcing on Internet; 2) workload on participants is lower and more flexible; 3) the rating procedure is efficient, labor-saving, and more importantly, without jeopardizing the accuracy of the results. ? 2011 ACM.EI