https://wiki.videolan.org/api.php?action=feedcontributions&user=Keram&feedformat=atomVideoLAN Wiki - User contributions [en]2022-08-08T03:53:45ZUser contributionsMediaWiki 1.34.0https://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12197SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-30T09:10:03Z<p>Keram: /* Week 8 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored a few fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, [http://jdegges.googlepages.com/x264-mref-avg.patch.txt moving averages], relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The third method, [http://jdegges.googlepages.com/x264-mref-slope.patch.txt average slope], keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 )<br />
c_ref8x8[h++] = i_ref;<br />
else if ( cost16x16[i_ref] < $F * bcost16x16 )<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
The 4-step patch can be found [http://jdegges.googlepages.com/x264-mref-4step.patch.txt here].<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition. [http://jdegges.googlepages.com/x264-mref-4part.patch.txt Here] is the patch to the 4-part algorithm.<br />
<br />
As with the 4-step algorithm this one can perform very differently depending on the selected thresholds. Thresholds 75-50-25 give relatives speedups from 0-16% and costs from 0-25%.<br />
<br />
==== Week 8 ====<br />
<br />
I have attempted to merge some search methods together to create a hybrid algorithm that can give better results. For preliminary testing the average bref was computed between 8 threshold intervals.<br />
<br />
for( i = 0; i < 9; i++ ) {<br />
if( cost16x16[bref]/bcost16x16 < threshold[i] ) {<br />
average_values[i] += bref;<br />
break;<br />
}<br />
}<br />
<br />
The threshold[0] is the difference between bcost16x16 and cost16x16[bref8x8]. The other seven thresholds are each half a standard deviation greater than the previous threshold.<br />
<br />
Similar to the original 4-step algorithm this one uses similarities between the costs/refs from the p16x16 search. If a ref cost is within one of the threshold intervals and the ref is close to the average ref for that interval then it will be searched. If any threshold intervals were not represented in the p16x16 costs then all of the refs will be searched:<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( aint != bint && aint != bint+1 ) {<br />
for( i = i_ref; i <= i_maxref; i++ )<br />
s_ref[k++] = ref16x16[i];<br />
break;<br />
}<br />
for( i = 0; i < 9; i++ ) {<br />
if( cost16x16[i_ref]/bcost16x16 <= threshold[i][0] && i_ref <= threshold[i][1] ) {<br />
s_ref[k++] = ref16x16[i_ref];<br />
bint = aint;<br />
aint = i;<br />
}<br />
}<br />
}<br />
p8x8_search( s_ref );<br />
<br />
This method is somewhat more robust than the previous methods in that it does not rely on any static thresholds. All of the thresholds can be computed live with moving averages. Using thresholds computed over the entire source (touhou) the results look very good when compared to other methods. Below is a graph showing the relative cost and speedups with a different number of references and at different target bitrates.<br />
<br />
[[Image:wk8-time_vs_bitrate.png]]<br />
<br />
As you can see the cost/speedup scales with the number of references used and the cost/speedup ratio is close to 1. It is not clearly marked on the graph, but the number of references used at different bitrate are 16, 12, 8, 4, and 1. As the number of references is increased so are the cost and time savings.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=File:Wk8-time_vs_bitrate.png&diff=12196File:Wk8-time vs bitrate.png2008-07-30T09:01:45Z<p>Keram: </p>
<hr />
<div></div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12195SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-30T09:01:04Z<p>Keram: /* Weekly Progress */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored a few fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, [http://jdegges.googlepages.com/x264-mref-avg.patch.txt moving averages], relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The third method, [http://jdegges.googlepages.com/x264-mref-slope.patch.txt average slope], keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 )<br />
c_ref8x8[h++] = i_ref;<br />
else if ( cost16x16[i_ref] < $F * bcost16x16 )<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
The 4-step patch can be found [http://jdegges.googlepages.com/x264-mref-4step.patch.txt here].<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition. [http://jdegges.googlepages.com/x264-mref-4part.patch.txt Here] is the patch to the 4-part algorithm.<br />
<br />
As with the 4-step algorithm this one can perform very differently depending on the selected thresholds. Thresholds 75-50-25 give relatives speedups from 0-16% and costs from 0-25%.<br />
<br />
==== Week 8 ====<br />
<br />
I have attempted to merge some search methods together to create a hybrid algorithm that can give better results. For preliminary testing the average bref was computed between 8 threshold intervals.<br />
<br />
for( i = 0; i < 9; i++ ) {<br />
if( cost16x16[bref]/bcost16x16 < threshold[i] ) {<br />
average_values[i] += bref;<br />
break;<br />
}<br />
}<br />
<br />
The threshold[0] is the difference between bcost16x16 and cost16x16[bref8x8]. The other seven thresholds are each half a standard deviation greater than the previous threshold.<br />
<br />
Similar to the original 4-step algorithm this one uses similarities between the costs/refs from the p16x16 search. If a ref cost is within one of the threshold intervals and the ref is close to the average ref for that interval then it will be searched. If any threshold intervals were not represented in the p16x16 costs then all of the refs will be searched:<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( aint != bint && aint != bint+1 ) {<br />
for( i = i_ref; i <= i_maxref; i++ )<br />
s_ref[k++] = ref16x16[i];<br />
break;<br />
}<br />
for( i = 0; i < 9; i++ ) {<br />
if( cost16x16[i_ref]/bcost16x16 <= threshold[i][0] && i_ref <= threshold[i][1] ) {<br />
s_ref[k++] = ref16x16[i_ref];<br />
bint = aint;<br />
aint = i;<br />
}<br />
}<br />
}<br />
p8x8_search( s_ref );<br />
<br />
This method is somewhat more robust than the previous methods in that it does not rely on any static thresholds. All of the thresholds can be computed live with moving averages. Using thresholds computed over the entire source (touhou) the results look very good when compared to other methods. Below is a graph showing the relative cost and speedups with a different number of references and at different target bitrates.<br />
<br />
[[Image:wk8-time_vs_bitrate.png]]<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12194SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-30T04:45:20Z<p>Keram: /* Week 6 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored a few fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, [http://jdegges.googlepages.com/x264-mref-avg.patch.txt moving averages], relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The third method, [http://jdegges.googlepages.com/x264-mref-slope.patch.txt average slope], keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 ) {<br />
c_ref8x8[h++] = i_ref;<br />
} else if ( cost16x16[i_ref] < $F * bcost16x16 ) {<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
The 4-step patch can be found [http://jdegges.googlepages.com/x264-mref-4step.patch.txt here].<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition. [http://jdegges.googlepages.com/x264-mref-4part.patch.txt Here] is the patch to the 4-part algorithm.<br />
<br />
As with the 4-step algorithm this one can perform very differently depending on the selected thresholds. Thresholds 75-50-25 give relatives speedups from 0-16% and costs from 0-25%.<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12191SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-29T09:37:02Z<p>Keram: /* Weekly Progress */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, [http://jdegges.googlepages.com/x264-mref-avg.patch.txt moving averages], relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The second method, sorts, attempts to rank each ref by its p16x16 cost prior to searching. Once the refs are sorted there are a number of ways to determine which refs are likely to be the best choices. One is to only search the best 2 or 3 refs which results in a fairly high cost increase. Another can be to search only refs within a certain cost percentage of the best ref. However, this depends on some magic percentage which may change from source to source. Depending on the percentage this can result in fast and costly or slow and accurate encoding.<br />
<br />
<br />
The third method, [http://jdegges.googlepages.com/x264-mref-slope.patch.txt average slope], keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 ) {<br />
c_ref8x8[h++] = i_ref;<br />
} else if ( cost16x16[i_ref] < $F * bcost16x16 ) {<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
The 4-step patch can be found [http://jdegges.googlepages.com/x264-mref-4step.patch.txt here].<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition. [http://jdegges.googlepages.com/x264-mref-4part.patch.txt Here] is the patch to the 4-part algorithm.<br />
<br />
As with the 4-step algorithm this one can perform very differently depending on the selected thresholds. Thresholds 75-50-25 give relatives speedups from 0-16% and costs from 0-25%.<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12190SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-29T06:37:56Z<p>Keram: /* Week 7 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, [http://jdegges.googlepages.com/x264-mref-avg.patch.txt moving averages], relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The second method, sorts, attempts to rank each ref by its p16x16 cost prior to searching. Once the refs are sorted there are a number of ways to determine which refs are likely to be the best choices. One is to only search the best 2 or 3 refs which results in a fairly high cost increase. Another can be to search only refs within a certain cost percentage of the best ref. However, this depends on some magic percentage which may change from source to source. Depending on the percentage this can result in fast and costly or slow and accurate encoding.<br />
<br />
<br />
The third method, [http://jdegges.googlepages.com/x264-mref-slope.patch.txt average slope], keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 ) {<br />
c_ref8x8[h++] = i_ref;<br />
} else if ( cost16x16[i_ref] < $F * bcost16x16 ) {<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
The 4-step patch can be found [http://jdegges.googlepages.com/x264-mref-4step.patch.txt here].<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition.<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12189SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-29T06:35:54Z<p>Keram: /* Week 6 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, [http://jdegges.googlepages.com/x264-mref-avg.patch.txt moving averages], relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The second method, sorts, attempts to rank each ref by its p16x16 cost prior to searching. Once the refs are sorted there are a number of ways to determine which refs are likely to be the best choices. One is to only search the best 2 or 3 refs which results in a fairly high cost increase. Another can be to search only refs within a certain cost percentage of the best ref. However, this depends on some magic percentage which may change from source to source. Depending on the percentage this can result in fast and costly or slow and accurate encoding.<br />
<br />
<br />
The third method, [http://jdegges.googlepages.com/x264-mref-slope.patch.txt average slope], keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 ) {<br />
c_ref8x8[h++] = i_ref;<br />
} else if ( cost16x16[i_ref] < $F * bcost16x16 ) {<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition.<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12188SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-29T06:34:30Z<p>Keram: /* Week 6 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, [http://jdegges.googlepages.com/x264-mref-avg.patch.txt moving averages], relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The second method, sorts, attempts to rank each ref by its p16x16 cost prior to searching. Once the refs are sorted there are a number of ways to determine which refs are likely to be the best choices. One is to only search the best 2 or 3 refs which results in a fairly high cost increase. Another can be to search only refs within a certain cost percentage of the best ref. However, this depends on some magic percentage which may change from source to source. Depending on the percentage this can result in fast and costly or slow and accurate encoding.<br />
<br />
<br />
The third method, average slope, keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 ) {<br />
c_ref8x8[h++] = i_ref;<br />
} else if ( cost16x16[i_ref] < $F * bcost16x16 ) {<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition.<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12186SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-28T19:06:18Z<p>Keram: /* Week 7 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, moving average, relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The second method, sorts, attempts to rank each ref by its p16x16 cost prior to searching. Once the refs are sorted there are a number of ways to determine which refs are likely to be the best choices. One is to only search the best 2 or 3 refs which results in a fairly high cost increase. Another can be to search only refs within a certain cost percentage of the best ref. However, this depends on some magic percentage which may change from source to source. Depending on the percentage this can result in fast and costly or slow and accurate encoding.<br />
<br />
<br />
The third method, average slope, keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 ) {<br />
c_ref8x8[h++] = i_ref;<br />
} else if ( cost16x16[i_ref] < $F * bcost16x16 ) {<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
<br />
<br />
In addition to the 4-step algorithm I noticed that some parallels can be drawn between the 4 partitions in the p8x8 search. Currently all 4 partitions search the same set of references without taking advantage of the exhaustive search of the previous partition. Here all refs are searched in the first partition and the best $A percentage of those refs are used in the second partition. Then the p8x8[0] costs are averaged with the p8x8[1] costs and the best $B percentage are used in the third partition. The costs are then again averaged/sorted and the best $C percentage are used in the fourth partition.<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12184SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-28T17:06:56Z<p>Keram: /* Week 7 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, moving average, relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The second method, sorts, attempts to rank each ref by its p16x16 cost prior to searching. Once the refs are sorted there are a number of ways to determine which refs are likely to be the best choices. One is to only search the best 2 or 3 refs which results in a fairly high cost increase. Another can be to search only refs within a certain cost percentage of the best ref. However, this depends on some magic percentage which may change from source to source. Depending on the percentage this can result in fast and costly or slow and accurate encoding.<br />
<br />
<br />
The third method, average slope, keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
After running some of my ideas past Dark_Shikari he advised me to try his '4 step' algorithm:<br />
1. Check all possibilities with $fastmetric<br />
2. If better than $closethreshold, check with $slowmetric<br />
3. If worse than $farthreshold, don't check at all<br />
4. Take all the remaining modes in between the thresholds, sort, pick the best ones, and $slowmetric them<br />
Here the $fastmetric is the p16x16 search, and the slow metric is p8x8.<br />
<br />
p16x16_search();<br />
for( i_ref = 0; i_ref <= i_maxref; i_ref++ ) {<br />
if( cost16x16[i_ref] < $C * bcost16x16 ) {<br />
c_ref8x8[h++] = i_ref;<br />
} else if ( cost16x16[i_ref] < $F * bcost16x16 ) {<br />
f_ref8x8[k++] = i_ref;<br />
}<br />
}<br />
pick_best(f_ref8x8);<br />
p8x8_search( c_ref8x8, f_ref8x8 );<br />
<br />
This method relies heavily upon the selection of adequate thresholds and the method of picking the best far refs. On some sources a threshold of 200 can achieve an overall improvement in quality (0-5%) with minimal speedups (0-5%). On the other hand with thresholds closer to the mean more dramatic speedups can be seen with much higher costs. Here is a table with rough relative costs and speedup percentages:<br />
Threshold Cost Speedup<br />
200 0 - -5% 0 - 5%<br />
150 0 - 8% 0 - 11%<br />
112 0 - 35% 0 - 22%<br />
<br />
<br />
2) quarter search heuristics<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12182SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-28T05:39:14Z<p>Keram: /* Weekly Progress */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
The first method, moving average, relies on the tendency of the best ref to be ref-0. Many sources have been examined (touhou,300,pirates) and on average 70% of the time the best reference frame is ref-0. This means that 70% of the time it is pointless to search the remaining references. To exploit this tendency a moving average is computed for all searched blocks where the best ref is ref-0. Every 10,000 blocks the average is updated with the cost of a best ref-0. When the average is not being updated the search will be terminated if the cost of ref-0 is within 3 standard deviations of the average.<br />
<br />
Relative to the current method of early termination this method increases PSNR/SSIM/bitrate by ~40% and offers from ~15% to 35% speed increase. Ideally the speedup should be larger than the cost of the speedup so this method is suboptimal.<br />
<br />
<br />
The second method, sorts, attempts to rank each ref by its p16x16 cost prior to searching. Once the refs are sorted there are a number of ways to determine which refs are likely to be the best choices. One is to only search the best 2 or 3 refs which results in a fairly high cost increase. Another can be to search only refs within a certain cost percentage of the best ref. However, this depends on some magic percentage which may change from source to source. Depending on the percentage this can result in fast and costly or slow and accurate encoding.<br />
<br />
<br />
The third method, average slope, keeps a moving average of the difference between ref-0 and ref-1 in the same manner as the first method. Other metrics can be used in a similar fashion. For example a ratio between ref-0 and ref-1 could be used.<br />
<br />
==== Week 7 ====<br />
<br />
1) 4step<br />
2) quarter search heuristics<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12181SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-28T03:12:36Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
<br />
==== Week 6 ====<br />
<br />
I have explored three fast reference search approaches this week. Each method uses a different metric for signaling early termination. The first method uses a moving average of the cost of the best ref to predict a low cost point of termination. The second method sorts the references in order of the p16x16 cost and only searches the lowest cost references. The third method is similar to the first except it maintains a moving average of the slope between the references to signal termination.<br />
<br />
<br />
<br />
==== Week 7 ====<br />
<br />
1) 4step<br />
2) quarter search heuristics<br />
<br />
==== Week 8 ====<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12035SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-02T03:34:34Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12032SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-01T09:48:52Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching. [http://jdegges.googlepages.com/x264-mixed-ref.patch Here] is a link to the patch.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12031SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-01T09:46:18Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12030SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-01T09:45:59Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs Y% = 100 * (1 - sum satd for best ref / sum satd for ref 0). Then the time saved using the proposed method T% = 100 * (1 - # of ref searches / max refs) and the compression cost C% = 100 * (sum of satd for selected refs / sum of satd for best ref - 1).<br />
<br />
For the LosslessTouhou source I have found Y% = 6.6, T% = 74%, and C% = .4.<br />
<br />
Upon further analysis I found that it is somewhat likely that the best ref is two away from the selected ref. When tested I found T% = 73 and C% = .1<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12024SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-01T08:30:37Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) which shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
Although this method does decrease the overall execution time, the effective bitrate increase and quality loss do not justify the savings in time.<br />
<br />
<br />
Next I attempted to come up with a method for speeding up the ref search in x264_mb_analyse_inter_p8x8_mixed_ref. After looking at some of the reference costs I came up with a very simple method for skipping searches: if the cost of the current ref is greater than the previous ref two times in a row then stop searching.<br />
<br />
To compute the effectiveness of this method I first compute the percentage of compression improvement gained by using mixedrefs as 1 - (sum satd for best ref / sum satd for ref 0). <br />
<br />
<math>\,\! \sin x + \ln y</math><br />
: <math>\sum_{n=0}^\infty \frac{x^n}{n!}</math><br />
&alpha;<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=File:Quality-test-t1.png&diff=12018File:Quality-test-t1.png2008-07-01T07:40:25Z<p>Keram: </p>
<hr />
<div></div>Keramhttps://wiki.videolan.org/index.php?title=File:Bitrate-time-t1.png&diff=12017File:Bitrate-time-t1.png2008-07-01T07:39:59Z<p>Keram: </p>
<hr />
<div></div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12016SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-01T07:39:41Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) that shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
[[Image:bitrate-time-t1.png]] [[Image:quality-test-t1.png]]<br />
<br />
provides an average decrease in execution time. Where it does not show improvement the execution times are roughly similar.<br />
[[Image:exec-time.png]]<br />
<br />
[http://jdegges.googlepages.com/accu.png Here] is an accuracy comparison graph which shows the change in SSIM, PSNR, and bitrate between the proposed and original algorithm for each of the 36 test cases. On average the SSIM difference is very close to zero and the PSNR difference can be bounded by approximately .1. In most of the cases the bitrate difference is less than zero.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=12015SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-07-01T07:37:54Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph comparing the execution time and bitrate between the two algorithms. As you can see, the proposed algorithm does not provide any bitrate improvement over the original algorithm. This with the combined with a quality improvement analysis (the second graph) that shows a maximum quality decrease of 3.5% further proves that this method is not a viable method for making inter mode decisions.<br />
[[Image:exec-time.png]] [[Image:bitrate-time.png]]<br />
<br />
provides an average decrease in execution time. Where it does not show improvement the execution times are roughly similar.<br />
[[Image:exec-time.png]]<br />
<br />
[http://jdegges.googlepages.com/accu.png Here] is an accuracy comparison graph which shows the change in SSIM, PSNR, and bitrate between the proposed and original algorithm for each of the 36 test cases. On average the SSIM difference is very close to zero and the PSNR difference can be bounded by approximately .1. In most of the cases the bitrate difference is less than zero.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11984SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-06-26T06:57:37Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and below is a graph of each tests overall execution time. As you can see, the proposed algorithm provides an average decrease in execution time. Where it does not show improvement the execution times are roughly similar.<br />
[[Image:exec-time.png]]<br />
<br />
[http://jdegges.googlepages.com/accu.png Here] is an accuracy comparison graph which shows the change in SSIM, PSNR, and bitrate between the proposed and original algorithm for each of the 36 test cases. On average the SSIM difference is very close to zero and the PSNR difference can be bounded by approximately .1. In most of the cases the bitrate difference is less than zero.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11978SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-06-26T04:08:02Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and [http://jdegges.googlepages.com/exec-time.png here] is a graph of each tests overall execution time. As you can see, the proposed algorithm provides an average decrease in execution time. Where it does not show improvement the execution times are roughly similar.<br />
<br />
[http://jdegges.googlepages.com/accu.png Here] is an accuracy comparison graph which shows the change in SSIM, PSNR, and bitrate between the proposed and original algorithm for each of the 36 test cases. On average the SSIM difference is very close to zero and the PSNR difference can be bounded by approximately .1. In most of the cases the bitrate difference is less than zero.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11977SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-06-26T03:58:49Z<p>Keram: /* Week 5 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and [http://jdegges.googlepages.com/exec-time.png here] is a graph of each tests overall execution time. As you can see, the proposed algorithm provides an average decrease in execution time. Where it does not show improvement the execution times are roughly similar and in only one case does the original algorithm finish executing a significant amount of time before the proposed one.<br />
<br />
[http://jdegges.googlepages.com/accu.png Here] is an accuracy comparison graph which shows the change in SSIM, PSNR, and bitrate between the proposed and original algorithm for each of the 36 test cases. On average the SSIM difference is very close to zero and the PSNR difference can be bounded by approximately .1. In most of the cases the bitrate difference is less than zero.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11976SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-06-26T02:01:15Z<p>Keram: /* Week 4 */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
==== Week 5 ====<br />
<br />
The tests have finished and [http://jdegges.googlepages.com/exec-time.png here] is a graph of each tests overall execution time. As you can see, the proposed algorithm provides an average decrease in execution time. Where it does not show improvement the execution times are roughly similar and in only one case does the original algorithm finish executing a significant amount of time before the proposed one.<br />
<br />
On the other hand the proposed algorithm is always slightly less accurate than the original one. So in many cases there is not much motivation to switch to this method.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11954SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-06-24T04:46:03Z<p>Keram: /* Goals */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Weekly Progress ==<br />
==== Week 4 ====<br />
<br />
Due to university commitments this was my first real week working on the project. I have primarily spent this week getting more familiar with the x264 code. To help familiarize myself with the code I have implemented a fast inter mode search algorithm which was inspired from an IEEE conference paper.<br />
<br />
Here is the pseudo code for the search method. The patch can be found [http://jdegges.googlepages.com/x264-fast-inter-decision.patch here]<br />
<br />
analyse_mode_16x16()<br />
threshold1 = 48 * pow(1.12246,qp)<br />
threshold2 = threshold1 + lambda2*192<br />
if ( cost_16x16 < threshold1 )<br />
{<br />
done<br />
}<br />
else if ( cost_16x16 < threshold2 )<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
else<br />
{<br />
analyse_mode_8x8()<br />
if ( cost_8x8 < cost_16x16 )<br />
{<br />
if( frame_type == B_FRAME )<br />
done<br />
else<br />
analyse_mode_sub8x8()<br />
}<br />
else<br />
{<br />
analyse_mode_16x8()<br />
analyse_mode_8x16()<br />
}<br />
}<br />
<br />
I am currently running many tests comparing the current algorithm with the proposed algorithm to see where it can be improved. Overall I am conducting 36 tests which are being driven with [http://jdegges.googlepages.com/x264-bench.sh this] bash script. The script compares the results of a patched x264 and an unmodified x264 on two different sources with 3 different bitrates (1500,1000,500), 3 different numbers of reference frames (8,4,1), as well as with and without mixed-refs. Results will be posted shortly!<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11681SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-05-27T06:37:29Z<p>Keram: /* Schedule */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time. I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.<br />
<br />
School starts back up ~28th of September so if all goes as planned my project will be completed by then :]</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11679SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-05-27T06:31:44Z<p>Keram: /* Goals */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.<br />
<br />
== Schedule ==<br />
<br />
All finals will be finished June 10th and starting June 11th I will be working full time.<br />
I will be camping sometime in late June for 1.5 days and possibly once more later in the summer. Other than that I do not plan to take any more vacation.</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11678SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-05-27T06:25:56Z<p>Keram: /* Goals */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
== Goals ==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11677SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-05-27T06:25:27Z<p>Keram: /* Abstract */</p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
== Abstract ==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
==Goals==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11610SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-05-22T04:04:54Z<p>Keram: </p>
<hr />
<div>{{SoCProject|year=2008|student=[[User:keram|Joey Degges ]]|mentor=Jason Garrett-Glaser}}<br />
<br />
==Abstract==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
==Goals==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.</div>Keramhttps://wiki.videolan.org/index.php?title=SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization&diff=11539SoC 2008/x264 Improve Fast Inter Refinement and Adaptive Quantization2008-05-15T05:02:40Z<p>Keram: New page: ==Abstract== The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve va...</p>
<hr />
<div>==Abstract==<br />
The goal of this project is to improve heuristics and decision-making for inter refinement in order to improve efficiency given average encoding settings. This will involve various early termination heuristics along with methods of deciding which partition modes need to be searched while performing minimal actual searching on them. I also plan to experiment with different methods that can be used to improve psycho-visual optimizations for mode decisions and quantization. This will include improving variance adaptive quantization by experimenting with different methods which could be used to weight the variance in order to select a more optimized quantizer.<br />
<br />
==Goals==<br />
Goals:<br />
<br />
* Improve inter prediction algorithms through the addition of early termination heuristics<br />
# Analyze the costs of using the different reference frames and partition modes.<br />
# Uses these results to create rules for early termination in order to avoid exhaustive searches.<br />
<br />
* Explore the usage of texture and shape in inter prediction<br />
# Implement curvature/first derivative algorithms (edge detection).<br />
# Compare edge count with the costs associated with the reference frames and partition modes.<br />
# Explore other metrics of texture/shape and their usefulness in this situation.<br />
# Implement early termination heuristics that depend on these texture and shape metrics.<br />
<br />
* Improve psycho-visual optimizations for mode decisions and quantization<br />
# Explore methods for SSIM-QNS optimization.<br />
# Adaptive dead zone / lambda.<br />
# Make improvements upon the Adaptive Quantization algorithms to achieve higher visual quality.<br />
## Investigate the usage of NSSE and noise shaping techniques.<br />
## Explore the usage of curvature as a means of weighting the variance in order to achieve a more optimized quantizer.<br />
## Determine the most effective metric or combination of metrics.</div>Keramhttps://wiki.videolan.org/index.php?title=User:Keram&diff=11538User:Keram2008-05-15T04:54:11Z<p>Keram: </p>
<hr />
<div>'''Name:''' Joey Degges<br />
<br />
'''Country:''' USA<br />
<br />
'''University:''' UCLA<br />
<br />
'''SoC 2008 Project:''' I will be working on x264 this summer improving fast inter refinement and adaptive quantization. Check out [[SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization]] for more details about the project.<br />
<br />
'''Other:''' I don't have much of a personal website, but you can find what I do have [http://jdegges.googlepages.com/ here]</div>Keramhttps://wiki.videolan.org/index.php?title=User:Keram&diff=11537User:Keram2008-05-15T04:53:45Z<p>Keram: </p>
<hr />
<div>'''Name:''' Joey Degges<br />
'''<br />
Country:''' USA<br />
'''<br />
University:''' UCLA<br />
'''<br />
SoC 2008 Project:''' I will be working on x264 this summer improving fast inter refinement and adaptive quantization. Check out [[SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization]] for more details about the project.<br />
'''<br />
Other:''' I don't have much of a personal website, but you can find what I do have [http://jdegges.googlepages.com/ here]</div>Keramhttps://wiki.videolan.org/index.php?title=User:Keram&diff=11536User:Keram2008-05-15T04:52:21Z<p>Keram: </p>
<hr />
<div>Name: Joey Degges<br />
<br />
Country: USA<br />
<br />
University: UCLA<br />
<br />
SoC 2008 Project: I will be working on x264 this summer improving fast inter refinement and adaptive quantization. Check out [[SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization]] for more details about the project.<br />
<br />
Other: I don't have much of a personal website, but you can find what I do have [http://jdegges.googlepages.com/ here]</div>Keramhttps://wiki.videolan.org/index.php?title=User:Keram&diff=11535User:Keram2008-05-15T04:50:32Z<p>Keram: New page: Name: Joey Degges Country: USA University: UCLA SoC 2008 Project: I will be working on x264 this summer improving fast inter refinement and adaptive quantization. Check out [[SoC_2008/x264...</p>
<hr />
<div>Name: Joey Degges<br />
Country: USA<br />
University: UCLA<br />
SoC 2008 Project: I will be working on x264 this summer improving fast inter refinement and adaptive quantization. Check out [[SoC_2008/x264_Improve_Fast_Inter_Refinement_and_Adaptive_Quantization]] for more details about the project.<br />
Other: I don't have much of a personal website, but you can find what I do have [http://jdegges.googlepages.com/ here]</div>Keram