ref: fcccbcbb395ce4cf31b54ce1245cc28e5e3ef4c1
dir: /vp9/common/vp9_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 "vp9/common/vp9_onyxc_int.h"
#define MAX_REGIONS 24000
#ifndef NULL
#define NULL 0
#endif
#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(VP9_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[0].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[0].as_mv.row,
mi[mb_index].mbmi.mv[0].as_mv.col);
}
printf("\n");
++mb_index;
}
printf("\n");
}
}