Apparatus and method for combining random set of video features in a non-linear scheme to best describe perceptual quality of video sequences using heuristic search methodology

• US 7,010,159 B2
• Filed: 08/24/2001
• Issued: 03/07/2006
• Est. Priority Date: 04/25/2001
• Status: Expired due to Term

• Current Assignee: Uniloc 2017 LLC (SoftBank Group Corp.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Ali, Walid S. I.
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US09/938,377
• Publication Number:
  US 20030012426A1
• Time in Patent Office: 1,656 Days
• Field of Search: 382155-160, 382/112, 382/278, 382/228, 382/254, 382/286, 706 12- 16, 706/25, 700/47, 700/48, 702 81- 84, 702/179, 702/182, 702/194, 702 66- 69, 348/92, 348/93, 348/180, 348/192, 348/193, 348/438.1, 348/455
• US Class Current: 382/155
• CPC Class Codes: H04N 17/00 Diagnosis, testing or measuring for television systems or their details

Abstract

A method for combining a random set of video features non-linearly to evaluate perceptual quality of video sequences includes (a) receiving a video sequence for image quality evaluation; (b) providing an objective metric image quality controller comprising a random set of metrics ranging from M₁ to M_n without dependency information for each one metric; (c) applying each one metric individually to the video sequence to provide an individual objective scoring value of the video sequence ranging from x₁ to x_n; (d) determining a plurality of sets of weights (w₁ to w_n) which correlate to predetermined subjective evaluations of image quality for a predetermined plurality of video sequences (n), each one set of weights being assigned a range having an incremental value equal to the range divided by a number of combinations for each one set of weights; (e) weighting each individual objective scoring value x₁ to x_n provided by each one metric of the random set of metrics in step (c); (f) combining metrics of the weighted individual objective scoring value of the random set of metrics into a single objective evaluation F, wherein each weighted individual scoring value from step (e) is multiplied by each individual objective scoring value x₁ to x_n from step (c); (g) calculating a correlation factor R to provide a correlation value for the objective evaluation F and the plurality of video sequences (n). Steps (e), (f) and (g) are repeated to provide a plurality of correlation factors which are ranked. A heuristic search uses a genetic algorithm to find the best set of weights to provide objective scores closest to predetermined subjective evaluations. A system provides the hardware and modules that perform the non-linear combination of metrics to provide enhanced perceptual image information.

Claims

1. A method for providing a composite objective image quality metric of a set of a plurality of random video features, said method comprising the steps of:

(a) receiving a video sequence for image quality evaluation;

(b) providing an objective metric image quality controller comprising a random set of metrics ranging from M₁ to M_n without cross correlation information;

(c) applying said each one metric of said set of metrics individually to said video sequence so that said each one metric of said random set of metrics provides an individual objective scoring value of said video sequence ranging from x₁ to x_n;

(d) determining a plurality of sets of weights (w₁ to w_n) which correlate to predetermined subjective evaluations of image quality for a predetermined plurality of video sequences (n), each one set of weights of said plurality of sets of weights being assigned a range having an incremental value equal to said range divided by a number of combinations for said each one set of weights;

(e) weighting by said each one set of weights each individual objective scoring value x₁ to x_n provided by said each one metric of said random set of metrics in step (c);

(f) adding the weighted individual objective scoring values of said random set of metrics into a single objective evaluation F, wherein each weighted individual scoring value from step (e) is multiplied by each individual objective scoring value x₁ to x_n from step (c);

(g) calculating a correlation factor R to provide a correlation value for the objective evaluation F and the plurality of video sequences (n);

(h) repeating steps (e), (f) and (g) for each set of weights provided in step (d) to determine a plurality of correlation factors R;

(i) ranking said plurality of correlation factors R, wherein a particular correlation factor of said plurality of correlation factors having a particular correlation value closest to 1 represents a best ranking of the respective combined metrics in step (e) for each set of weights; and

(j) providing image quality information to at least one of a system optimizer and the video processing module as to the best ranking of the respective combined metrics obtained in step (i) to provide a best perceptual image quality.

2. The method according to claim 1, where the combining recited in step (f) is performed non-linearly by a quadratic model to obtain the objective evaluation F.

3. The method according to claim 2, wherein when a number of the set of metrics =4, then the quadratic model to obtain the objective evaluation F is:

$F=w_1<br><br>x_1^2+w_2<br><br>x_2^2+w_3<br><br>x_3^2+w_4<br><br>x_4^2+w_5<br><br>x_1<br><br>x_2+w_6<br><br>x_1<br><br>x_3+w_7<br><br>x_1<br><br>x_4+w_8<br><br>x_2<br><br>x_3+w_9<br><br>x_2<br><br>x_4+w_{10}<br><br>x_3<br><br>x_4.$

4. The method according to claim 2, wherein when a number of the sets of metrics=n, then the quadratic model to obtain the objective evaluation F is:

$F={\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>w_i<br><br>x_i\right)}^2,$

wherein “

n”

is a non-zero value.

5. The method according to claim 1, wherein a number of sets of metrics=n, and step (f) includes using a polynomial degree for non-linear combination to an Lth order, and said objective evaluation F is obtained according to:

$F={\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>w_i<br><br>x_i\right)}^L$

, wherein “

n”

is a non-zero value.

6. The method according to claim 1, wherein the calculating of the correlation factor R in step (g) is performed by using a Spearman rank order comprising the following equation:

$R=1-\frac{6*{\left(X-Y\right)}^t<br><br>\left(X-Y\right)}{k<br><br>\left(k^2-1\right)},$

wherein X is equal to a vector of ranked k objective values for the k sequences (k*1), and Y is equal to a vector of ranked k subjective evaluation for the k sequences (k*1).

7. The method according to claim 2, wherein the calculating of the correlation factor R in step (g) is performed by using a Spearman rank order comprising the following equation:

$R=1-\frac{6*{\left(X-Y\right)}^t<br><br>\left(X-Y\right)}{k<br><br>\left(k^2-1\right)},$

wherein X is equal to a vector of ranked k objective values for the k sequences (k*1), and Y is equal to a vector of ranked k subjective evaluation for the k sequences (k*1).

8. The method according to claim 4, wherein the calculating of the correlation factor R in step (g) is performed by using a Spearman rank order comprising the following equation:

$R=1-\frac{6*{\left(X-Y\right)}^t<br><br>\left(X-Y\right)}{k<br><br>\left(k^2-1\right)},$

wherein X is equal to a vector of ranked k objective values for the k sequences (k*1), and Y is equal to a vector of ranked k subjective evaluation for the k sequences (k*1).

9. The method according to claim 1, wherein said method further comprises the step of:

(k) selecting a best set of weights from the plurality of sets of weights provided in step (d), said best set of weights being heuristically determined by a genetic algorithm that increases dynamically a size of the assigned range of said each one set of weights provided in step (d).

10. The method according to claim 1, wherein said method further comprises the step of:

(k) selecting a best set of weights from the plurality of sets of weights provided in step (d), said best set of weights being heuristically determined by a genetic algorithm that that enables finding the best solution that maximizes the correlation factor R of the overall objective image quality F with the subjective evaluation without performing an exhaustive search to find the best set of weights.

11. The method according to claim 2, wherein said method further comprises the step of:

(k) selecting a best set of weights from the plurality of sets of weights provided in step (d), said best set of weights being heuristically determined by a genetic algorithm that increases dynamically a size of the assigned range of said each one set of weights provided in step (d).

12. The method according to claim 2, wherein said method further comprises the step of:

(k) selecting a best set of weights from the plurality of sets of weights provided in step (d), said best set of weights being heuristically determined by a genetic algorithm that enables finding the best solution that maximizes the correlation factor R of the overall objective image quality F with the subjective evaluation without performing an exhaustive search to find the best set of weights.

13. The method according to claim 7, wherein said method further comprises the step of:

(k) selecting a best set of weights from the plurality of sets of weights provided in step (d), said best set of weights being heuristically determined by a genetic algorithm that increases dynamically a size of the assigned range of said each one set of weights provided in step (d).

14. The method according to claim 7, wherein said method further comprises the step of:

(k) selecting a best set of weights from the plurality of sets of weights provided in step (d), said best set of weights being heuristically determined by a genetic algorithm that that enables finding the best solution that maximizes the correlation factor R of the overall objective image quality F with the subjective evaluation without performing an exhaustive search to find the best set of weights.

15. The method according to claim 9, wherein said genetic algorithm comprises a chromosome having a number of genes corresponding to quantity of said plurality of sets of weights in step (d), and each gene of said number of genes being represented by a quantity of bits sufficient to represent all possible tested values for said each one weight in binary, wherein all possible tested values being equal to an absolute value of the assigned range for said each one set of weights provided in step (d) divided by the incremental value for said each one set of weights.

16. The method according to claim 15, wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, so that a best solution comprises a deviation closest to zero.

17. The method according to claim 10, wherein said genetic algorithm comprises a chromosome having a number of genes corresponding to quantity of said plurality of sets of weights in step (d), and each gene of said number of genes being represented by a quantity of bits sufficient to represent all possible tested values for said each one weight in binary, wherein all possible tested values being equal to a value of the assigned range for said each one set of weights provided in step (d) divided by the incremental value for said each one set of weights.

18. The method according to claim 17, wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, so that a best solution comprises a deviation closest to zero.

19. The method according to claim 17, wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, so that a best solution comprises one of 1) the deviation within a predetermined percentage of a predetermined value, and 2) the deviation can not be decreased any further after a certain predetermined number of attempts.

20. The method according to claim 11, wherein said genetic algorithm comprises a chromosome having a number of genes corresponding to quantity of said plurality of sets of weights in step (d), and each gene of said number of genes being represented by a quantity of bits sufficient to represent all possible tested values for said each one weight in binary, wherein all possible tested values being equal to a value of the assigned range for said each one set of weights provided in step (d) divided by the incremental value for said each one set of weights.

21. The method according to claim 20, wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, so that a best solution comprises a deviation closest to zero.

22. The method according to claim 12, wherein said genetic algorithm comprises a chromosome having a number of genes corresponding to quantity of said plurality of sets of weights in step (d), and each gene of said number of genes being represented by a quantity of bits sufficient to represent all possible tested values for said each one weight in binary, wherein all possible tested values being equal to a value of the assigned range for said each one set of weights provided in step (d) divided by the incremental value for said each one set of weights.

23. The method according to claim 22, wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, so that a best solution comprises a deviation closest to zero.

24. The method according to claim 13, wherein said genetic algorithm comprises a chromosome having a number of genes corresponding to quantity of said plurality of sets of weights in step (d), and each gene of said number of genes being represented by a quantity of bits sufficient to represent all possible tested values for said each one weight in binary, wherein all possible tested values being equal to a value of the assigned range for said each one set of weights provided in step (d) divided by the incremental value for said each one set of weights.

25. The method according to claim 24, wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, wherein the deviation =1−

R, and a best solution determined by said algorithm comprises a deviation closest to zero.

26. The method according to claim 13, wherein said genetic algorithm comprises a chromosome having a number of genes corresponding to quantity of said plurality of sets of weights in step (d), and each gene of said number of genes being represented by a quantity of bits sufficient to represent all possible tested values for said each one weight in binary, wherein all possible tested values being equal to a value of the assigned range for said each one set of weights provided in step (d) divided by the incremental value for said each one set of weights, and

wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, wherein the deviation =1−

R, and a best solution determined by said algorithm comprises a deviation closest to a predetermined value.

27. The method according to claim 26, wherein said predetermined value comprises a value that cannot be reduced by further search.

28. The method according to claim 24, wherein said genetic algorithm alters a bit pattern of said chromosome by at least one of mutation and crossover while minimizing a deviation in the correlation factor R, wherein the deviation =1−

R, and a best solution determined by said algorithm comprises a deviation closest to a predetermined value.

29. A system for providing a composite image of a random set of video features comprising:

means for receiving a video sequence;

an objective metric image quality controller comprising a plurality of objective metrics without prior dependency information thereof, means for selecting a metric from said plurality of objective metrics for evaluating image quality of the video sequence, and means for applying each of said plurality of objective metrics by said objective metric image quality controller to said video sequence and individually scoring said video sequence from x₁ to x_n;

means for determining a plurality of sets of weights (w₁ to w_n) by said objective metric image quality controller, said plurality of sets of weights correlate to predetermined subjective evaluations of image quality for a predetermined plurality of video sequences (n), each one set of weights being assigned a range having an incremental value equal to a value of said range divided by a number of combinations for said each one set of weights, which includes means for weighting by said each one set of weights each individual objective scoring value x₁ to x_n provided by said each one metric of a random set of metrics;

means for combining metrics of the weighted individual objective scoring values of said random set of metrics corresponding to the random set of video features into a single objective evaluation F, wherein each weighted individual scoring value is multiplied by a corresponding weight; and

means for calculating a plurality of correlation factors R to provide a correlation value for the objective evaluation F and the plurality of video sequences (n), which includes means for ranking said plurality of correlation factors R, wherein a particular correlation factor of said plurality of correlation factors having a particular correlation value closest to 1 represents a best ranked respective combined metrics for each set of weights,

wherein the best ranked respective combined metrics determined by said objective metric image quality controller is used to provide a best objective perceptual quality of said video sequence.

30. The system according to claim 29, wherein said means for combining metrics includes means for non-linear combination by a quadratic model to obtain the objective evaluation F.

31. The system according to claim 29, wherein said means for combining metrics includes means for non-linear combination by a polynomial degree to an Lth order, and a number of sets of metrics=n, to obtain the objective evaluation F according to:

$F={\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>w_i<br><br>x_i\right)}^L$

, wherein “

n”

is a non-zero value.

32. The system according to claim 30, wherein said means for calculating the plurality of correlation factors R includes using a Spearman rank order comprising:

$R=1-\frac{6*{\left(X-Y\right)}^t<br><br>\left(X-Y\right)}{k<br><br>\left(k^2-1\right)},$

wherein X is equal to a vector of ranked k objective values for the k sequences (k*1), and Y is equal to a vector of ranked k subjective evaluation for the k sequences (k*1).

33. The system according to claim 32, wherein said means for determining includes means for selecting a best set of weights from the plurality of sets of weights, said best set of weights being heuristically determined by a genetic algorithm module that increases dynamically a size of the assigned range of said each one set of weights.

34. The system according to claim 33, wherein said means for determining includes means for selecting a best set of weights from the plurality of sets of weights, said best set of weights being heuristically determined by a genetic algorithm module that enables finding the best solution that maximizes the correlation factor R of the overall objective image quality F with the subjective evaluation without performing an exhaustive search to find the best set of weights.