vp8/common/implicit_segmentation.c

/*
 *  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
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */

#include "vp8/common/onyxc_int.h"

#define MAX_REGIONS 24000
#define NULL 0

#define min_mbs_in_region 3

// this linked list structure holds equivalences for connected
// component labeling
struct list_el {
   int label;
   int seg_value;
   int count;
   struct list_el * next;
};
typedef struct list_el item;

// connected colorsegments
typedef struct
{
  int min_x;
  int min_y;
  int max_x;
  int max_y;
  long long sum_x;
  long long sum_y;
  int pixels;
  int seg_value;
  int label;
} segment_info;


typedef enum
{
  SEGMENT_MODE,
  SEGMENT_MV,
  SEGMENT_REFFRAME,
  SEGMENT_SKIPPED
} SEGMENT_TYPE;


// this merges the two equivalence lists and
// then makes sure that every label points to the same
// equivalence list
void merge ( item *labels, int u, int v )
{
  item *a = labels[u].next;
  item *b = labels[v].next;
  item c;
  item *it = &c;
  int count;

  // check if they are already merged
  if(u==v || a==b)
    return;

  count = a->count + b->count;

  // merge 2 sorted linked lists.
  while ( a != NULL && b != NULL )
  {
    if ( a->label < b->label)
    {
      it->next = a;
      a = a->next;
    }
    else
    {
      it->next = b;
      b = b->next;
    }

    it = it->next;
  }

  if ( a == NULL )
    it->next = b;
  else
    it->next = a;

  it = c.next;

  // make sure every equivalence in the linked list points to this new ll
  while( it != NULL)
  {
    labels[it->label].next = c.next;
    it=it->next;
  }
  c.next->count = count;

}

void segment_via_mode_info( VP8_COMMON *oci, int how)
{
    MODE_INFO *mi = oci->mi;
    int i,j;
    int mb_index = 0;

    int label=1;
    int pitch = oci->mb_cols;

    // holds linked list equivalences
    // the max should probably be allocated at a higher level in oci
    item equivalences[MAX_REGIONS];
    int eq_ptr = 0;
    item labels[MAX_REGIONS];
    segment_info segments[MAX_REGIONS];
    int label_count = 1;
    int labeling[400*300];
    int *lp = labeling;

    label_count = 1;
    memset(labels,0,sizeof(labels));
    memset(segments,0,sizeof(segments));

    /* Go through each macroblock first pass labelling */
    for (i = 0; i < oci->mb_rows; i++,lp+=pitch)
    {
        for (j = 0; j < oci->mb_cols; j++)
        {
          // int above seg_value, left seg_value, this seg_value...
          int a=-1,l=-1,n=-1;

          // above label, left label
          int al=-1,ll=-1;
          if(i)
          {
            al=lp[j-pitch];
            a = labels[al].next->seg_value;
          }
          if(j)
          {
            ll=lp[j-1];
            l = labels[ll].next->seg_value;
          }

          // what setting are we going to do the implicit segmentation on
          switch (how)
          {
            case SEGMENT_MODE:
              n= mi[mb_index].mbmi.mode;
              break;
            case SEGMENT_MV:
              n = mi[mb_index].mbmi.mv.as_int;
              if(mi[mb_index].mbmi.ref_frame == INTRA_FRAME)
                 n=-9999999;
              break;
            case SEGMENT_REFFRAME:
              n = mi[mb_index].mbmi.ref_frame;
              break;
            case SEGMENT_SKIPPED:
              n = mi[mb_index].mbmi.mb_skip_coeff;
              break;
          }

          // above and left both have the same seg_value
          if(n==a&&n==l)
          {
            // pick the lowest label
            lp[j] = (al<ll?al:ll);
            labels[lp[j]].next->count++;

            // merge the above and left equivalencies
            merge( labels, al, ll );
          }
          // this matches above seg_value
          else if(n==a)
          {
              // give it the same label as above
              lp[j]=al;
              labels[al].next->count++;
          }
          // this matches left seg_value
          else if(n==l)
          {
              // give it the same label as above
              lp[j]=ll;
              labels[ll].next->count++;
          }
          else
          {
              // new label doesn't match either
              item *e = &labels[label];
              item *nl = &equivalences[eq_ptr++];
              lp[j]=label;
              nl->label = label;
              nl->next = 0;
              nl->seg_value = n;
              nl->count = 1;
              e->next = nl;
              label++;
          }
          mb_index++;
      }
      mb_index++;
    }
    lp = labeling;

    // give new labels to regions
    for(i=1;i<label;i++)
      if(labels[i].next->count >min_mbs_in_region  &&  labels[labels[i].next->label].label == 0 )
      {
        segment_info *cs= &segments[label_count];
        cs->label = label_count;
        labels[labels[i].next->label].label = label_count++;
        labels[labels[i].next->label].seg_value  = labels[i].next->seg_value;
        cs->seg_value = labels[labels[i].next->label].seg_value;
        cs->min_x = oci->mb_cols;
        cs->min_y = oci->mb_rows;
        cs->max_x = 0;
        cs->max_y = 0;
        cs->sum_x = 0;
        cs->sum_y = 0;
        cs->pixels= 0;

      }
    lp = labeling;

    // this is just to gather stats...
    for(i=0;i<oci->mb_rows;i++,lp+=pitch)
    {
      for(j=0;j<oci->mb_cols;j++)
      {
         segment_info *cs;
         int oldlab = labels[lp[j]].next->label;
         int lab = labels[oldlab].label;
         lp[j] = lab;

         cs= &segments[lab];

         cs->min_x = (j<cs->min_x?j:cs->min_x);
         cs->max_x = (j>cs->max_x?j:cs->max_x);
         cs->min_y = (i<cs->min_y?i:cs->min_y);
         cs->max_y = (i>cs->max_y?i:cs->max_y);
         cs->sum_x += j;
         cs->sum_y += i;
         cs->pixels ++;

         lp[j] = lab;
         mb_index++;
      }
      mb_index++;
    }

    {
      lp = labeling;
      printf("labelling \n");
      mb_index = 0;
      for(i=0;i<oci->mb_rows;i++,lp+=pitch)
      {
        for(j=0;j<oci->mb_cols;j++)
        {
          printf("%4d",lp[j]);
        }
        printf("            ");
        for(j=0;j<oci->mb_cols;j++,mb_index++)
        {
          //printf("%3d",mi[mb_index].mbmi.mode );
          printf("%4d:%4d",mi[mb_index].mbmi.mv.as_mv.row,mi[mb_index].mbmi.mv.as_mv.col );
        }
        printf("\n");
        ++mb_index;
      }
      printf("\n");
    }
}