WebM Experimental Codec Branch Snapshot

This is a code snapshot of experimental work currently ongoing for a
next-generation codec.

The codebase has been cut down considerably from the libvpx baseline.
For example, we are currently only supporting VBR 2-pass rate control
and have removed most of the code relating to coding speed, threading,
error resilience, partitions and various other features.  This is in
part to make the codebase easier to work on and experiment with, but
also because we want to have an open discussion about how the bitstream
will be structured and partitioned and not have that conversation
constrained by past work.

Our basic working pattern has been to initially encapsulate experiments
using configure options linked to #IF CONFIG_XXX statements in the
code. Once experiments have matured and we are reasonably happy that
they give benefit and can be merged without breaking other experiments,
we remove the conditional compile statements and merge them in.

Current changes include:
* Temporal coding experiment for segments (though still only 4 max, it
  will likely be increased).
* Segment feature experiment - to allow various bits of information to
  be coded at the segment level. Features tested so far include mode
  and reference frame information, limiting end of block offset and
  transform size, alongside Q and loop filter parameters, but this set
  is very fluid.
* Support for 8x8 transform - 8x8 dct with 2nd order 2x2 haar is used
  in MBs using 16x16 prediction modes within inter frames.
* Compound prediction (combination of signals from existing predictors
  to create a new predictor).
* 8 tap interpolation filters and 1/8th pel motion vectors.
* Loop filter modifications.
* Various entropy modifications and changes to how entropy contexts and
  updates are handled.
* Extended quantizer range matched to transform precision improvements.

There are also ongoing further experiments that we hope to merge in the
near future: For example, coding of motion and other aspects of the
prediction signal to better support larger image formats, use of larger
block sizes (e.g. 32x32 and up) and lossless non-transform based coding
options (especially for key frames). It is our hope that we will be
able to make regular updates and we will warmly welcome community
contributions.

Please be warned that, at this stage, the codebase is currently slower
than VP8 stable branch as most new code has not been optimized, and
even the 'C' has been deliberately written to be simple and obvious,
not fast.

The following graphs have the initial test results, numbers in the
tables measure the compression improvement in terms of percentage. The
build has  the following optional experiments configured:
--enable-experimental --enable-enhanced_interp --enable-uvintra
--enable-high_precision_mv --enable-sixteenth_subpel_uv

CIF Size clips:
http://getwebm.org/tmp/cif/
HD size clips:
http://getwebm.org/tmp/hd/
(stable_20120309 represents encoding results of WebM master branch
build as of commit#7a15907)

They were encoded using the following encode parameters:
--good --cpu-used=0 -t 0 --lag-in-frames=25 --min-q=0 --max-q=63
--end-usage=0 --auto-alt-ref=1 -p 2 --pass=2 --kf-max-dist=9999
--kf-min-dist=0 --drop-frame=0 --static-thresh=0 --bias-pct=50
--minsection-pct=0 --maxsection-pct=800 --sharpness=0
--arnr-maxframes=7 --arnr-strength=3(for HD,6 for CIF)
--arnr-type=3

Change-Id: I5c62ed09cfff5815a2bb34e7820d6a810c23183c

1 files changed, 259 insertions, 6 deletions

diff --git a/vp8/encoder/segmentation.c b/vp8/encoder/segmentation.c
index fc0967db3..c36246a02 100644
--- a/vp8/encoder/segmentation.c
+++ b/vp8/encoder/segmentation.c
@@ -1,5 +1,5 @@
 /*
- *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
+ *  Copyright (c) 2012 The WebM project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
@@ -9,8 +9,10 @@
  */
 
 
-#include "segmentation.h"
+#include "limits.h"
 #include "vpx_mem/vpx_mem.h"
+#include "segmentation.h"
+#include "vp8/common/pred_common.h"
 
 void vp8_update_gf_useage_maps(VP8_COMP *cpi, VP8_COMMON *cm, MACROBLOCK *x)
 {
@@ -37,8 +39,10 @@ void vp8_update_gf_useage_maps(VP8_COMP *cpi, VP8_COMMON *cm, MACROBLOCK *x)
 
                 // If using golden then set GF active flag if not already set.
                 // If using last frame 0,0 mode then leave flag as it is
-                // else if using non 0,0 motion or intra modes then clear flag if it is currently set
-                if ((this_mb_mode_info->mbmi.ref_frame == GOLDEN_FRAME) || (this_mb_mode_info->mbmi.ref_frame == ALTREF_FRAME))
+                // else if using non 0,0 motion or intra modes then clear
+                // flag if it is currently set
+                if ((this_mb_mode_info->mbmi.ref_frame == GOLDEN_FRAME) ||
+                    (this_mb_mode_info->mbmi.ref_frame == ALTREF_FRAME))
                 {
                     if (*(x->gf_active_ptr) == 0)
                     {
@@ -46,14 +50,15 @@ void vp8_update_gf_useage_maps(VP8_COMP *cpi, VP8_COMMON *cm, MACROBLOCK *x)
                         cpi->gf_active_count ++;
                     }
                 }
-                else if ((this_mb_mode_info->mbmi.mode != ZEROMV) && *(x->gf_active_ptr))
+                else if ((this_mb_mode_info->mbmi.mode != ZEROMV) &&
+                         *(x->gf_active_ptr))
                 {
                     *(x->gf_active_ptr) = 0;
                     cpi->gf_active_count--;
                 }
 
                 x->gf_active_ptr++;          // Step onto next entry
-                this_mb_mode_info++;           // skip to next mb
+                this_mb_mode_info++;         // skip to next mb
 
             }
 
@@ -62,3 +67,251 @@ void vp8_update_gf_useage_maps(VP8_COMP *cpi, VP8_COMMON *cm, MACROBLOCK *x)
         }
     }
 }
+
+void vp8_enable_segmentation(VP8_PTR ptr)
+{
+    VP8_COMP *cpi = (VP8_COMP *)(ptr);
+
+    // Set the appropriate feature bit
+    cpi->mb.e_mbd.segmentation_enabled = 1;
+    cpi->mb.e_mbd.update_mb_segmentation_map = 1;
+    cpi->mb.e_mbd.update_mb_segmentation_data = 1;
+}
+
+void vp8_disable_segmentation(VP8_PTR ptr)
+{
+    VP8_COMP *cpi = (VP8_COMP *)(ptr);
+
+    // Clear the appropriate feature bit
+    cpi->mb.e_mbd.segmentation_enabled = 0;
+}
+
+void vp8_set_segmentation_map(VP8_PTR ptr,
+                              unsigned char *segmentation_map)
+{
+    VP8_COMP *cpi = (VP8_COMP *)(ptr);
+
+    // Copy in the new segmentation map
+    vpx_memcpy( cpi->segmentation_map, segmentation_map,
+                (cpi->common.mb_rows * cpi->common.mb_cols) );
+
+    // Signal that the map should be updated.
+    cpi->mb.e_mbd.update_mb_segmentation_map = 1;
+    cpi->mb.e_mbd.update_mb_segmentation_data = 1;
+}
+
+void vp8_set_segment_data(VP8_PTR ptr,
+                          signed char *feature_data,
+                          unsigned char abs_delta)
+{
+    VP8_COMP *cpi = (VP8_COMP *)(ptr);
+
+    cpi->mb.e_mbd.mb_segment_abs_delta = abs_delta;
+
+    vpx_memcpy(cpi->mb.e_mbd.segment_feature_data, feature_data,
+               sizeof(cpi->mb.e_mbd.segment_feature_data));
+
+    // TBD ?? Set the feature mask
+    // vpx_memcpy(cpi->mb.e_mbd.segment_feature_mask, 0,
+    //            sizeof(cpi->mb.e_mbd.segment_feature_mask));
+}
+
+// Based on set of segment counts calculate a probability tree
+static void calc_segtree_probs( MACROBLOCKD * xd,
+                                int * segcounts,
+                                vp8_prob * segment_tree_probs )
+{
+    int count1,count2;
+    int tot_count;
+    int i;
+
+    // Blank the strtucture to start with
+    vpx_memset(segment_tree_probs, 0, sizeof(segment_tree_probs));
+
+    // Total count for all segments
+    count1 = segcounts[0] + segcounts[1];
+    count2 = segcounts[2] + segcounts[3];
+    tot_count = count1 + count2;
+
+    // Work out probabilities of each segment
+    if (tot_count)
+        segment_tree_probs[0] = (count1 * 255) / tot_count;
+    if (count1 > 0)
+        segment_tree_probs[1] = (segcounts[0] * 255) / count1;
+    if (count2 > 0)
+        segment_tree_probs[2] = (segcounts[2] * 255) / count2;
+
+    // Clamp probabilities to minimum allowed value
+    for (i = 0; i < MB_FEATURE_TREE_PROBS; i++)
+    {
+        if (segment_tree_probs[i] == 0)
+            segment_tree_probs[i] = 1;
+    }
+}
+
+// Based on set of segment counts and probabilities calculate a cost estimate
+static int cost_segmap( MACROBLOCKD * xd,
+                        int * segcounts,
+                        vp8_prob * probs )
+{
+    int cost;
+    int count1,count2;
+
+    // Cost the top node of the tree
+    count1 = segcounts[0] + segcounts[1];
+    count2 = segcounts[2] + segcounts[3];
+    cost = count1 * vp8_cost_zero(probs[0]) +
+           count2 * vp8_cost_one(probs[0]);
+
+    // Now add the cost of each individual segment branch
+    if (count1 > 0)
+        cost += segcounts[0] * vp8_cost_zero(probs[1]) +
+                segcounts[1] * vp8_cost_one(probs[1]);
+
+    if (count2 > 0)
+        cost += segcounts[2] * vp8_cost_zero(probs[2]) +
+                segcounts[3] * vp8_cost_one(probs[2]) ;
+
+    return cost;
+
+}
+
+void choose_segmap_coding_method( VP8_COMP *cpi )
+{
+    VP8_COMMON *const cm = & cpi->common;
+    MACROBLOCKD *const xd = & cpi->mb.e_mbd;
+
+    int i;
+    int tot_count;
+    int no_pred_cost;
+    int t_pred_cost = INT_MAX;
+    int pred_context;
+
+    int mb_row, mb_col;
+    int segmap_index = 0;
+    unsigned char segment_id;
+
+    int temporal_predictor_count[PREDICTION_PROBS][2];
+    int no_pred_segcounts[MAX_MB_SEGMENTS];
+    int t_unpred_seg_counts[MAX_MB_SEGMENTS];
+
+    vp8_prob no_pred_tree[MB_FEATURE_TREE_PROBS];
+    vp8_prob t_pred_tree[MB_FEATURE_TREE_PROBS];
+    vp8_prob t_nopred_prob[PREDICTION_PROBS];
+
+    // Set default state for the segment tree probabilities and the
+    // temporal coding probabilities
+    vpx_memset(xd->mb_segment_tree_probs, 255,
+               sizeof(xd->mb_segment_tree_probs));
+    vpx_memset(cm->segment_pred_probs, 255,
+               sizeof(cm->segment_pred_probs));
+
+    vpx_memset(no_pred_segcounts, 0, sizeof(no_pred_segcounts));
+    vpx_memset(t_unpred_seg_counts, 0, sizeof(t_unpred_seg_counts));
+    vpx_memset(temporal_predictor_count, 0, sizeof(temporal_predictor_count));
+
+    // First of all generate stats regarding how well the last segment map
+    // predicts this one
+
+    // Initialize macroblock decoder mode info context for the first mb
+    // in the frame
+    xd->mode_info_context = cm->mi;
+
+    for (mb_row = 0; mb_row < cm->mb_rows; mb_row++)
+    {
+        for (mb_col = 0; mb_col < cm->mb_cols; mb_col++)
+        {
+            segment_id = xd->mode_info_context->mbmi.segment_id;
+
+            // Count the number of hits on each segment with no prediction
+            no_pred_segcounts[segment_id]++;
+
+            // Temporal prediction not allowed on key frames
+            if (cm->frame_type != KEY_FRAME)
+            {
+                // Test to see if the segment id matches the predicted value.
+                int seg_predicted =
+                    (segment_id == get_pred_mb_segid( cm, segmap_index ));
+
+                // Get the segment id prediction context
+                pred_context =
+                    get_pred_context( cm, xd, PRED_SEG_ID );
+
+                // Store the prediction status for this mb and update counts
+                // as appropriate
+                set_pred_flag( xd, PRED_SEG_ID, seg_predicted );
+                temporal_predictor_count[pred_context][seg_predicted]++;
+
+                if ( !seg_predicted )
+                    // Update the "unpredicted" segment count
+                    t_unpred_seg_counts[segment_id]++;
+            }
+
+            // Step on to the next mb
+            xd->mode_info_context++;
+
+            // Step on to the next entry in the segment maps
+            segmap_index++;
+        }
+
+        // this is to account for the border in mode_info_context
+        xd->mode_info_context++;
+    }
+
+    // Work out probability tree for coding segments without prediction
+    // and the cost.
+    calc_segtree_probs( xd, no_pred_segcounts, no_pred_tree );
+    no_pred_cost = cost_segmap( xd, no_pred_segcounts, no_pred_tree );
+
+    // Key frames cannot use temporal prediction
+    if (cm->frame_type != KEY_FRAME)
+    {
+        // Work out probability tree for coding those segments not
+        // predicted using the temporal method and the cost.
+        calc_segtree_probs( xd, t_unpred_seg_counts, t_pred_tree );
+        t_pred_cost = cost_segmap( xd, t_unpred_seg_counts, t_pred_tree );
+
+        // Add in the cost of the signalling for each prediction context
+        for ( i = 0; i < PREDICTION_PROBS; i++ )
+        {
+            tot_count = temporal_predictor_count[i][0] +
+                        temporal_predictor_count[i][1];
+
+            // Work out the context probabilities for the segment
+            // prediction flag
+            if ( tot_count )
+            {
+                t_nopred_prob[i] = ( temporal_predictor_count[i][0] * 255 ) /
+                                   tot_count;
+
+                // Clamp to minimum allowed value
+                if ( t_nopred_prob[i] < 1 )
+                    t_nopred_prob[i] = 1;
+            }
+            else
+                t_nopred_prob[i] = 1;
+
+            // Add in the predictor signaling cost
+            t_pred_cost += ( temporal_predictor_count[i][0] *
+                               vp8_cost_zero(t_nopred_prob[i]) ) +
+                           ( temporal_predictor_count[i][1] *
+                               vp8_cost_one(t_nopred_prob[i]) );
+        }
+    }
+
+    // Now choose which coding method to use.
+    if ( t_pred_cost < no_pred_cost )
+    {
+         cm->temporal_update = 1;
+         vpx_memcpy( xd->mb_segment_tree_probs,
+                     t_pred_tree, sizeof(t_pred_tree) );
+         vpx_memcpy( &cm->segment_pred_probs,
+                     t_nopred_prob, sizeof(t_nopred_prob) );
+    }
+    else
+    {
+         cm->temporal_update = 0;
+         vpx_memcpy( xd->mb_segment_tree_probs,
+                     no_pred_tree, sizeof(no_pred_tree) );
+    }
+}