1793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Copyright 2011 Google Inc. All Rights Reserved. 2793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 3793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Use of this source code is governed by a BSD-style license 4793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// that can be found in the COPYING file in the root of the source 5793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// tree. An additional intellectual property rights grant can be found 6793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// in the file PATENTS. All contributing project authors may 7793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// be found in the AUTHORS file in the root of the source tree. 8793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// ----------------------------------------------------------------------------- 9793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 10793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Macroblock analysis 11793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 12793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Author: Skal (pascal.massimino@gmail.com) 13793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 14793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include <stdlib.h> 15793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include <string.h> 16793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include <assert.h> 17793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 18793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include "./vp8enci.h" 19793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include "./cost.h" 20793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include "../utils/utils.h" 21793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 22793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#if defined(__cplusplus) || defined(c_plusplus) 23793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerextern "C" { 24793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#endif 25793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 26793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define MAX_ITERS_K_MEANS 6 27793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 28793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler//------------------------------------------------------------------------------ 29793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Smooth the segment map by replacing isolated block by the majority of its 30793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// neighbours. 31793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 32793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic void SmoothSegmentMap(VP8Encoder* const enc) { 33793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int n, x, y; 34793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int w = enc->mb_w_; 35793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int h = enc->mb_h_; 36793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int majority_cnt_3_x_3_grid = 5; 37793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler uint8_t* const tmp = (uint8_t*)WebPSafeMalloc((uint64_t)w * h, sizeof(*tmp)); 38793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler assert((uint64_t)(w * h) == (uint64_t)w * h); // no overflow, as per spec 39793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 40793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (tmp == NULL) return; 41793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (y = 1; y < h - 1; ++y) { 42793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (x = 1; x < w - 1; ++x) { 43793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int cnt[NUM_MB_SEGMENTS] = { 0 }; 44793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const VP8MBInfo* const mb = &enc->mb_info_[x + w * y]; 45793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int majority_seg = mb->segment_; 46793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Check the 8 neighbouring segment values. 47793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[-w - 1].segment_]++; // top-left 48793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[-w + 0].segment_]++; // top 49793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[-w + 1].segment_]++; // top-right 50793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[ - 1].segment_]++; // left 51793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[ + 1].segment_]++; // right 52793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[ w - 1].segment_]++; // bottom-left 53793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[ w + 0].segment_]++; // bottom 54793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cnt[mb[ w + 1].segment_]++; // bottom-right 55793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n < NUM_MB_SEGMENTS; ++n) { 56793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (cnt[n] >= majority_cnt_3_x_3_grid) { 57793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler majority_seg = n; 58793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 59793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 60793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler tmp[x + y * w] = majority_seg; 61793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 62793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 63793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (y = 1; y < h - 1; ++y) { 64793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (x = 1; x < w - 1; ++x) { 65793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8MBInfo* const mb = &enc->mb_info_[x + w * y]; 66793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->segment_ = tmp[x + y * w]; 67793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 68793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 69793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler free(tmp); 70793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 71793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 72793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler//------------------------------------------------------------------------------ 73793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// set segment susceptibility alpha_ / beta_ 74793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 75793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic WEBP_INLINE int clip(int v, int m, int M) { 76793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return (v < m) ? m : (v > M) ? M : v; 77793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 78793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 79793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic void SetSegmentAlphas(VP8Encoder* const enc, 80793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int centers[NUM_MB_SEGMENTS], 81793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mid) { 82793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int nb = enc->segment_hdr_.num_segments_; 83793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int min = centers[0], max = centers[0]; 84793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int n; 85793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 86793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (nb > 1) { 87793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n < nb; ++n) { 88793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (min > centers[n]) min = centers[n]; 89793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (max < centers[n]) max = centers[n]; 90793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 91793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 92793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (max == min) max = min + 1; 93793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler assert(mid <= max && mid >= min); 94793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n < nb; ++n) { 95793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int alpha = 255 * (centers[n] - mid) / (max - min); 96793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int beta = 255 * (centers[n] - min) / (max - min); 97793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->dqm_[n].alpha_ = clip(alpha, -127, 127); 98793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->dqm_[n].beta_ = clip(beta, 0, 255); 99793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 100793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 101793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 102793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler//------------------------------------------------------------------------------ 103793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Compute susceptibility based on DCT-coeff histograms: 104793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// the higher, the "easier" the macroblock is to compress. 105793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 106793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define MAX_ALPHA 255 // 8b of precision for susceptibilities. 107793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define ALPHA_SCALE (2 * MAX_ALPHA) // scaling factor for alpha. 108793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define DEFAULT_ALPHA (-1) 109793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define IS_BETTER_ALPHA(alpha, best_alpha) ((alpha) > (best_alpha)) 110793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 111793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic int FinalAlphaValue(int alpha) { 112793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler alpha = MAX_ALPHA - alpha; 113793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return clip(alpha, 0, MAX_ALPHA); 114793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 115793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 116793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic int GetAlpha(const VP8Histogram* const histo) { 117793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int max_value = 0, last_non_zero = 1; 118793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int k; 119793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int alpha; 120793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (k = 0; k <= MAX_COEFF_THRESH; ++k) { 121793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int value = histo->distribution[k]; 122793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (value > 0) { 123793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (value > max_value) max_value = value; 124793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler last_non_zero = k; 125793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 126793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 127793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // 'alpha' will later be clipped to [0..MAX_ALPHA] range, clamping outer 128793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // values which happen to be mostly noise. This leaves the maximum precision 129793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // for handling the useful small values which contribute most. 130793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler alpha = (max_value > 1) ? ALPHA_SCALE * last_non_zero / max_value : 0; 131793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return alpha; 132793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 133793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 134793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic void MergeHistograms(const VP8Histogram* const in, 135793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8Histogram* const out) { 136793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int i; 137793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (i = 0; i <= MAX_COEFF_THRESH; ++i) { 138793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler out->distribution[i] += in->distribution[i]; 139793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 140793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 141793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 142793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler//------------------------------------------------------------------------------ 143793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Simplified k-Means, to assign Nb segments based on alpha-histogram 144793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 145793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic void AssignSegments(VP8Encoder* const enc, 146793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int alphas[MAX_ALPHA + 1]) { 147793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int nb = enc->segment_hdr_.num_segments_; 148793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int centers[NUM_MB_SEGMENTS]; 149793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int weighted_average = 0; 150793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int map[MAX_ALPHA + 1]; 151793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int a, n, k; 152793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int min_a = 0, max_a = MAX_ALPHA, range_a; 153793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // 'int' type is ok for histo, and won't overflow 154793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int accum[NUM_MB_SEGMENTS], dist_accum[NUM_MB_SEGMENTS]; 155793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 156793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // bracket the input 157793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n <= MAX_ALPHA && alphas[n] == 0; ++n) {} 158793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler min_a = n; 159793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = MAX_ALPHA; n > min_a && alphas[n] == 0; --n) {} 160793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler max_a = n; 161793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler range_a = max_a - min_a; 162793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 163793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Spread initial centers evenly 164793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 1, k = 0; n < 2 * nb; n += 2) { 165793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler centers[k++] = min_a + (n * range_a) / (2 * nb); 166793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 167793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 168793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (k = 0; k < MAX_ITERS_K_MEANS; ++k) { // few iters are enough 169793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int total_weight; 170793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int displaced; 171793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Reset stats 172793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n < nb; ++n) { 173793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler accum[n] = 0; 174793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dist_accum[n] = 0; 175793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 176793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Assign nearest center for each 'a' 177793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler n = 0; // track the nearest center for current 'a' 178793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (a = min_a; a <= max_a; ++a) { 179793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (alphas[a]) { 180793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler while (n < nb - 1 && abs(a - centers[n + 1]) < abs(a - centers[n])) { 181793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler n++; 182793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 183793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler map[a] = n; 184793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // accumulate contribution into best centroid 185793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dist_accum[n] += a * alphas[a]; 186793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler accum[n] += alphas[a]; 187793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 188793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 189793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // All point are classified. Move the centroids to the 190793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // center of their respective cloud. 191793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler displaced = 0; 192793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler weighted_average = 0; 193793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler total_weight = 0; 194793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n < nb; ++n) { 195793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (accum[n]) { 196793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int new_center = (dist_accum[n] + accum[n] / 2) / accum[n]; 197793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler displaced += abs(centers[n] - new_center); 198793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler centers[n] = new_center; 199793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler weighted_average += new_center * accum[n]; 200793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler total_weight += accum[n]; 201793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 202793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 203793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler weighted_average = (weighted_average + total_weight / 2) / total_weight; 204793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (displaced < 5) break; // no need to keep on looping... 205793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 206793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 207793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Map each original value to the closest centroid 208793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) { 209793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8MBInfo* const mb = &enc->mb_info_[n]; 210793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int alpha = mb->alpha_; 211793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->segment_ = map[alpha]; 212793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->alpha_ = centers[map[alpha]]; // for the record. 213793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 214793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 215793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (nb > 1) { 216793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int smooth = (enc->config_->preprocessing & 1); 217793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (smooth) SmoothSegmentMap(enc); 218793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 219793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 220793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler SetSegmentAlphas(enc, centers, weighted_average); // pick some alphas. 221793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 222793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 223793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler//------------------------------------------------------------------------------ 224793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Macroblock analysis: collect histogram for each mode, deduce the maximal 225793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// susceptibility and set best modes for this macroblock. 226793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Segment assignment is done later. 227793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 228793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Number of modes to inspect for alpha_ evaluation. For high-quality settings 229793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// (method >= FAST_ANALYSIS_METHOD) we don't need to test all the possible modes 230793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// during the analysis phase. 231793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define FAST_ANALYSIS_METHOD 4 // method above which we do partial analysis 232793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define MAX_INTRA16_MODE 2 233793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define MAX_INTRA4_MODE 2 234793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#define MAX_UV_MODE 2 235793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 236793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic int MBAnalyzeBestIntra16Mode(VP8EncIterator* const it) { 237793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int max_mode = 238793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler (it->enc_->method_ >= FAST_ANALYSIS_METHOD) ? MAX_INTRA16_MODE 239793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler : NUM_PRED_MODES; 240793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mode; 241793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int best_alpha = DEFAULT_ALPHA; 242793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int best_mode = 0; 243793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 244793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8MakeLuma16Preds(it); 245793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (mode = 0; mode < max_mode; ++mode) { 246793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8Histogram histo = { { 0 } }; 247793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int alpha; 248793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 249793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8CollectHistogram(it->yuv_in_ + Y_OFF, 250793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler it->yuv_p_ + VP8I16ModeOffsets[mode], 251793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 0, 16, &histo); 252793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler alpha = GetAlpha(&histo); 253793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (IS_BETTER_ALPHA(alpha, best_alpha)) { 254793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_alpha = alpha; 255793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_mode = mode; 256793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 257793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 258793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8SetIntra16Mode(it, best_mode); 259793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return best_alpha; 260793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 261793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 262793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic int MBAnalyzeBestIntra4Mode(VP8EncIterator* const it, 263793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int best_alpha) { 264793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler uint8_t modes[16]; 265793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int max_mode = 266793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler (it->enc_->method_ >= FAST_ANALYSIS_METHOD) ? MAX_INTRA4_MODE 267793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler : NUM_BMODES; 268793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int i4_alpha; 269793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8Histogram total_histo = { { 0 } }; 270793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int cur_histo = 0; 271793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 272793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8IteratorStartI4(it); 273793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler do { 274793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mode; 275793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int best_mode_alpha = DEFAULT_ALPHA; 276793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8Histogram histos[2]; 277793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const uint8_t* const src = it->yuv_in_ + Y_OFF + VP8Scan[it->i4_]; 278793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 279793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8MakeIntra4Preds(it); 280793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (mode = 0; mode < max_mode; ++mode) { 281793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int alpha; 282793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 283793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler memset(&histos[cur_histo], 0, sizeof(histos[cur_histo])); 284793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8CollectHistogram(src, it->yuv_p_ + VP8I4ModeOffsets[mode], 285793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 0, 1, &histos[cur_histo]); 286793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler alpha = GetAlpha(&histos[cur_histo]); 287793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (IS_BETTER_ALPHA(alpha, best_mode_alpha)) { 288793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_mode_alpha = alpha; 289793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler modes[it->i4_] = mode; 290793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cur_histo ^= 1; // keep track of best histo so far. 291793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 292793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 293793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // accumulate best histogram 294793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler MergeHistograms(&histos[cur_histo ^ 1], &total_histo); 295793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Note: we reuse the original samples for predictors 296793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } while (VP8IteratorRotateI4(it, it->yuv_in_ + Y_OFF)); 297793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 298793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler i4_alpha = GetAlpha(&total_histo); 299793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (IS_BETTER_ALPHA(i4_alpha, best_alpha)) { 300793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8SetIntra4Mode(it, modes); 301793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_alpha = i4_alpha; 302793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 303793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return best_alpha; 304793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 305793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 306793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic int MBAnalyzeBestUVMode(VP8EncIterator* const it) { 307793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int best_alpha = DEFAULT_ALPHA; 308793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int best_mode = 0; 309793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int max_mode = 310793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler (it->enc_->method_ >= FAST_ANALYSIS_METHOD) ? MAX_UV_MODE 311793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler : NUM_PRED_MODES; 312793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mode; 313793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8MakeChroma8Preds(it); 314793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (mode = 0; mode < max_mode; ++mode) { 315793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8Histogram histo = { { 0 } }; 316793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int alpha; 317793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8CollectHistogram(it->yuv_in_ + U_OFF, 318793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler it->yuv_p_ + VP8UVModeOffsets[mode], 319793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 16, 16 + 4 + 4, &histo); 320793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler alpha = GetAlpha(&histo); 321793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (IS_BETTER_ALPHA(alpha, best_alpha)) { 322793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_alpha = alpha; 323793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_mode = mode; 324793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 325793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 326793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8SetIntraUVMode(it, best_mode); 327793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return best_alpha; 328793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 329793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 330793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic void MBAnalyze(VP8EncIterator* const it, 331793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int alphas[MAX_ALPHA + 1], 332793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int* const alpha, int* const uv_alpha) { 333793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const VP8Encoder* const enc = it->enc_; 334793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int best_alpha, best_uv_alpha; 335793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 336793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8SetIntra16Mode(it, 0); // default: Intra16, DC_PRED 337793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8SetSkip(it, 0); // not skipped 338793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8SetSegment(it, 0); // default segment, spec-wise. 339793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 340793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_alpha = MBAnalyzeBestIntra16Mode(it); 341793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (enc->method_ >= 5) { 342793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // We go and make a fast decision for intra4/intra16. 343793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // It's usually not a good and definitive pick, but helps seeding the stats 344793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // about level bit-cost. 345793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // TODO(skal): improve criterion. 346793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_alpha = MBAnalyzeBestIntra4Mode(it, best_alpha); 347793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 348793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_uv_alpha = MBAnalyzeBestUVMode(it); 349793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 350793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Final susceptibility mix 351793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_alpha = (3 * best_alpha + best_uv_alpha + 2) >> 2; 352793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler best_alpha = FinalAlphaValue(best_alpha); 353793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler alphas[best_alpha]++; 354793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler it->mb_->alpha_ = best_alpha; // for later remapping. 355793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 356793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Accumulate for later complexity analysis. 357793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler *alpha += best_alpha; // mixed susceptibility (not just luma) 358793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler *uv_alpha += best_uv_alpha; 359793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 360793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 361793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic void DefaultMBInfo(VP8MBInfo* const mb) { 362793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->type_ = 1; // I16x16 363793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->uv_mode_ = 0; 364793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->skip_ = 0; // not skipped 365793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->segment_ = 0; // default segment 366793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mb->alpha_ = 0; 367793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 368793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 369793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler//------------------------------------------------------------------------------ 370793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Main analysis loop: 371793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Collect all susceptibilities for each macroblock and record their 372793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// distribution in alphas[]. Segments is assigned a-posteriori, based on 373793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// this histogram. 374793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// We also pick an intra16 prediction mode, which shouldn't be considered 375793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// final except for fast-encode settings. We can also pick some intra4 modes 376793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// and decide intra4/intra16, but that's usually almost always a bad choice at 377793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// this stage. 378793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 379793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic void ResetAllMBInfo(VP8Encoder* const enc) { 380793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int n; 381793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) { 382793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler DefaultMBInfo(&enc->mb_info_[n]); 383793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 384793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Default susceptibilities. 385793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->dqm_[0].alpha_ = 0; 386793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->dqm_[0].beta_ = 0; 387793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Note: we can't compute this alpha_ / uv_alpha_. 388793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_); 389793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 390793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 391793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerint VP8EncAnalyze(VP8Encoder* const enc) { 392793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int ok = 1; 393793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int do_segments = 394793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->config_->emulate_jpeg_size || // We need the complexity evaluation. 395793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler (enc->segment_hdr_.num_segments_ > 1) || 396793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler (enc->method_ == 0); // for method 0, we need preds_[] to be filled. 397793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->alpha_ = 0; 398793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->uv_alpha_ = 0; 399793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (do_segments) { 400793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int alphas[MAX_ALPHA + 1] = { 0 }; 401793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8EncIterator it; 402793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 403793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8IteratorInit(enc, &it); 404793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler do { 405793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler VP8IteratorImport(&it); 406793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler MBAnalyze(&it, alphas, &enc->alpha_, &enc->uv_alpha_); 407793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ok = VP8IteratorProgress(&it, 20); 408793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Let's pretend we have perfect lossless reconstruction. 409793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } while (ok && VP8IteratorNext(&it, it.yuv_in_)); 410793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->alpha_ /= enc->mb_w_ * enc->mb_h_; 411793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler enc->uv_alpha_ /= enc->mb_w_ * enc->mb_h_; 412793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if (ok) AssignSegments(enc, alphas); 413793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } else { // Use only one default segment. 414793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ResetAllMBInfo(enc); 415793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 416793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return ok; 417793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 418793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 419793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#if defined(__cplusplus) || defined(c_plusplus) 420793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} // extern "C" 421793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#endif 422