Line data Source code
1 : /*
2 : * Copyright (c) 2016, Alliance for Open Media. All rights reserved
3 : *
4 : * This source code is subject to the terms of the BSD 2 Clause License and
5 : * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
6 : * was not distributed with this source code in the LICENSE file, you can
7 : * obtain it at www.aomedia.org/license/software. If the Alliance for Open
8 : * Media Patent License 1.0 was not distributed with this source code in the
9 : * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
10 : */
11 :
12 : #include <math.h>
13 : #include <stdlib.h>
14 : #include "EbDefinitions.h"
15 : #include "EbModeDecisionProcess.h"
16 :
17 : #if PAL_SUP
18 :
19 : #define DIVIDE_AND_ROUND(x, y) (((x) + ((y) >> 1)) / (y))
20 :
21 : // Generate a random number in the range [0, 32768).
22 0 : static INLINE unsigned int lcg_rand16(unsigned int *state) {
23 0 : *state = (unsigned int)(*state * 1103515245ULL + 12345);
24 0 : return *state / 65536 % 32768;
25 : }
26 :
27 : #define AV1_K_MEANS_RENAME(func, dim) func##_dim##dim
28 :
29 : void AV1_K_MEANS_RENAME(av1_calc_indices, 1)(const int *data,
30 : const int *centroids,
31 : uint8_t *indices, int n, int k);
32 : void AV1_K_MEANS_RENAME(av1_calc_indices, 2)(const int *data,
33 : const int *centroids,
34 : uint8_t *indices, int n, int k);
35 : void AV1_K_MEANS_RENAME(av1_k_means, 1)(const int *data, int *centroids,
36 : uint8_t *indices, int n, int k,
37 : int max_itr);
38 : void AV1_K_MEANS_RENAME(av1_k_means, 2)(const int *data, int *centroids,
39 : uint8_t *indices, int n, int k,
40 : int max_itr);
41 :
42 : // Given 'n' 'data' points and 'k' 'centroids' each of dimension 'dim',
43 : // calculate the centroid 'indices' for the data points.
44 0 : static inline void av1_calc_indices(const int *data, const int *centroids,
45 : uint8_t *indices, int n, int k, int dim) {
46 0 : if (dim == 1) {
47 0 : AV1_K_MEANS_RENAME(av1_calc_indices, 1)(data, centroids, indices, n, k);
48 : }
49 0 : else if (dim == 2) {
50 0 : AV1_K_MEANS_RENAME(av1_calc_indices, 2)(data, centroids, indices, n, k);
51 : }
52 : else {
53 0 : assert(0 && "Untemplated k means dimension");
54 : }
55 0 : }
56 :
57 : // Given 'n' 'data' points and an initial guess of 'k' 'centroids' each of
58 : // dimension 'dim', runs up to 'max_itr' iterations of k-means algorithm to get
59 : // updated 'centroids' and the centroid 'indices' for elements in 'data'.
60 : // Note: the output centroids are rounded off to nearest integers.
61 0 : static inline void av1_k_means(const int *data, int *centroids,
62 : uint8_t *indices, int n, int k, int dim,
63 : int max_itr) {
64 0 : if (dim == 1) {
65 0 : AV1_K_MEANS_RENAME(av1_k_means, 1)(data, centroids, indices, n, k, max_itr);
66 : }
67 0 : else if (dim == 2) {
68 0 : AV1_K_MEANS_RENAME(av1_k_means, 2)(data, centroids, indices, n, k, max_itr);
69 : }
70 : else {
71 0 : assert(0 && "Untemplated k means dimension");
72 : }
73 0 : }
74 :
75 :
76 : #define AV1_K_MEANS_DIM 1
77 : #include "k_means_template.h"
78 : #undef AV1_K_MEANS_DIM
79 : #define AV1_K_MEANS_DIM 2
80 : #include "k_means_template.h"
81 : #undef AV1_K_MEANS_DIM
82 :
83 0 : static int int_comparer(const void *a, const void *b) {
84 0 : return (*(int *)a - *(int *)b);
85 : }
86 :
87 0 : int av1_remove_duplicates(int *centroids, int num_centroids) {
88 : int num_unique; // number of unique centroids
89 : int i;
90 0 : qsort(centroids, num_centroids, sizeof(*centroids), int_comparer);
91 : // Remove duplicates.
92 0 : num_unique = 1;
93 0 : for (i = 1; i < num_centroids; ++i) {
94 0 : if (centroids[i] != centroids[i - 1]) { // found a new unique centroid
95 0 : centroids[num_unique++] = centroids[i];
96 : }
97 : }
98 0 : return num_unique;
99 : }
100 :
101 0 : static int delta_encode_cost(const int *colors, int num, int bit_depth,
102 : int min_val) {
103 0 : if (num <= 0) return 0;
104 0 : int bits_cost = bit_depth;
105 0 : if (num == 1) return bits_cost;
106 0 : bits_cost += 2;
107 0 : int max_delta = 0;
108 : int deltas[PALETTE_MAX_SIZE];
109 0 : const int min_bits = bit_depth - 3;
110 0 : for (int i = 1; i < num; ++i) {
111 0 : const int delta = colors[i] - colors[i - 1];
112 0 : deltas[i - 1] = delta;
113 0 : assert(delta >= min_val);
114 0 : if (delta > max_delta) max_delta = delta;
115 : }
116 0 : int bits_per_delta = AOMMAX(av1_ceil_log2(max_delta + 1 - min_val), min_bits);
117 0 : assert(bits_per_delta <= bit_depth);
118 0 : int range = (1 << bit_depth) - colors[0] - min_val;
119 0 : for (int i = 0; i < num - 1; ++i) {
120 0 : bits_cost += bits_per_delta;
121 0 : range -= deltas[i];
122 0 : bits_per_delta = AOMMIN(bits_per_delta, av1_ceil_log2(range));
123 : }
124 0 : return bits_cost;
125 : }
126 :
127 0 : int av1_index_color_cache(const uint16_t *color_cache, int n_cache,
128 : const uint16_t *colors, int n_colors,
129 : uint8_t *cache_color_found, int *out_cache_colors) {
130 0 : if (n_cache <= 0) {
131 0 : for (int i = 0; i < n_colors; ++i) out_cache_colors[i] = colors[i];
132 0 : return n_colors;
133 : }
134 0 : memset(cache_color_found, 0, n_cache * sizeof(*cache_color_found));
135 0 : int n_in_cache = 0;
136 : int in_cache_flags[PALETTE_MAX_SIZE];
137 0 : memset(in_cache_flags, 0, sizeof(in_cache_flags));
138 0 : for (int i = 0; i < n_cache && n_in_cache < n_colors; ++i) {
139 0 : for (int j = 0; j < n_colors; ++j) {
140 0 : if (colors[j] == color_cache[i]) {
141 0 : in_cache_flags[j] = 1;
142 0 : cache_color_found[i] = 1;
143 0 : ++n_in_cache;
144 0 : break;
145 : }
146 : }
147 : }
148 0 : int j = 0;
149 0 : for (int i = 0; i < n_colors; ++i)
150 0 : if (!in_cache_flags[i]) out_cache_colors[j++] = colors[i];
151 0 : assert(j == n_colors - n_in_cache);
152 0 : return j;
153 : }
154 :
155 :
156 0 : int av1_get_palette_delta_bits_v(const PaletteModeInfo *const pmi,
157 : int bit_depth, int *zero_count,
158 : int *min_bits) {
159 0 : const int n = pmi->palette_size[1];
160 0 : const int max_val = 1 << bit_depth;
161 0 : int max_d = 0;
162 0 : *min_bits = bit_depth - 4;
163 0 : *zero_count = 0;
164 0 : for (int i = 1; i < n; ++i) {
165 0 : const int delta = pmi->palette_colors[2 * PALETTE_MAX_SIZE + i] -
166 0 : pmi->palette_colors[2 * PALETTE_MAX_SIZE + i - 1];
167 0 : const int v = abs(delta);
168 0 : const int d = AOMMIN(v, max_val - v);
169 0 : if (d > max_d) max_d = d;
170 0 : if (d == 0) ++(*zero_count);
171 : }
172 0 : return AOMMAX(av1_ceil_log2(max_d + 1), *min_bits);
173 : }
174 :
175 0 : int av1_palette_color_cost_y(const PaletteModeInfo *const pmi,
176 : uint16_t *color_cache, int n_cache,
177 : int bit_depth) {
178 0 : const int n = pmi->palette_size[0];
179 : int out_cache_colors[PALETTE_MAX_SIZE];
180 : uint8_t cache_color_found[2 * PALETTE_MAX_SIZE];
181 : const int n_out_cache =
182 0 : av1_index_color_cache(color_cache, n_cache, pmi->palette_colors, n,
183 : cache_color_found, out_cache_colors);
184 0 : const int total_bits =
185 0 : n_cache + delta_encode_cost(out_cache_colors, n_out_cache, bit_depth, 1);
186 0 : return av1_cost_literal(total_bits);
187 : }
188 :
189 0 : int av1_palette_color_cost_uv(const PaletteModeInfo *const pmi,
190 : uint16_t *color_cache, int n_cache,
191 : int bit_depth) {
192 0 : const int n = pmi->palette_size[1];
193 0 : int total_bits = 0;
194 : // U channel palette color cost.
195 : int out_cache_colors[PALETTE_MAX_SIZE];
196 : uint8_t cache_color_found[2 * PALETTE_MAX_SIZE];
197 0 : const int n_out_cache = av1_index_color_cache(
198 0 : color_cache, n_cache, pmi->palette_colors + PALETTE_MAX_SIZE, n,
199 : cache_color_found, out_cache_colors);
200 0 : total_bits +=
201 0 : n_cache + delta_encode_cost(out_cache_colors, n_out_cache, bit_depth, 0);
202 :
203 : // V channel palette color cost.
204 0 : int zero_count = 0, min_bits_v = 0;
205 : const int bits_v =
206 0 : av1_get_palette_delta_bits_v(pmi, bit_depth, &zero_count, &min_bits_v);
207 0 : const int bits_using_delta =
208 0 : 2 + bit_depth + (bits_v + 1) * (n - 1) - zero_count;
209 0 : const int bits_using_raw = bit_depth * n;
210 0 : total_bits += 1 + AOMMIN(bits_using_delta, bits_using_raw);
211 0 : return av1_cost_literal(total_bits);
212 : }
213 :
214 :
215 0 : static void palette_add_to_cache(uint16_t *cache, int *n, uint16_t val) {
216 : // Do not add an already existing value
217 0 : if (*n > 0 && val == cache[*n - 1]) return;
218 :
219 0 : cache[(*n)++] = val;
220 : }
221 :
222 0 : int eb_get_palette_cache(const MacroBlockD *const xd, int plane,
223 : uint16_t *cache) {
224 0 : const int row = -xd->mb_to_top_edge >> 3;
225 : // Do not refer to above SB row when on SB boundary.
226 0 : const MbModeInfo *const above_mi =
227 0 : (row % (1 << MIN_SB_SIZE_LOG2)) ? xd->above_mbmi : NULL;
228 0 : const MbModeInfo *const left_mi = xd->left_mbmi;
229 0 : int above_n = 0, left_n = 0;
230 0 : if (above_mi) above_n = above_mi->palette_mode_info.palette_size[plane != 0];
231 0 : if (left_mi) left_n = left_mi->palette_mode_info.palette_size[plane != 0];
232 0 : if (above_n == 0 && left_n == 0) return 0;
233 0 : int above_idx = plane * PALETTE_MAX_SIZE;
234 0 : int left_idx = plane * PALETTE_MAX_SIZE;
235 0 : int n = 0;
236 0 : const uint16_t *above_colors =
237 0 : above_mi ? above_mi->palette_mode_info.palette_colors : NULL;
238 0 : const uint16_t *left_colors =
239 0 : left_mi ? left_mi->palette_mode_info.palette_colors : NULL;
240 : // Merge the sorted lists of base colors from above and left to get
241 : // combined sorted color cache.
242 0 : while (above_n > 0 && left_n > 0) {
243 0 : uint16_t v_above = above_colors[above_idx];
244 0 : uint16_t v_left = left_colors[left_idx];
245 0 : if (v_left < v_above) {
246 0 : palette_add_to_cache(cache, &n, v_left);
247 0 : ++left_idx, --left_n;
248 : }
249 : else {
250 0 : palette_add_to_cache(cache, &n, v_above);
251 0 : ++above_idx, --above_n;
252 0 : if (v_left == v_above) ++left_idx, --left_n;
253 : }
254 : }
255 0 : while (above_n-- > 0) {
256 0 : uint16_t val = above_colors[above_idx++];
257 0 : palette_add_to_cache(cache, &n, val);
258 : }
259 0 : while (left_n-- > 0) {
260 0 : uint16_t val = left_colors[left_idx++];
261 0 : palette_add_to_cache(cache, &n, val);
262 : }
263 0 : assert(n <= 2 * PALETTE_MAX_SIZE);
264 0 : return n;
265 : }
266 : // Returns sub-sampled dimensions of the given block.
267 : // The output values for 'rows_within_bounds' and 'cols_within_bounds' will
268 : // differ from 'height' and 'width' when part of the block is outside the
269 : // right
270 : // and/or bottom image boundary.
271 0 : void av1_get_block_dimensions(BlockSize bsize, int plane,
272 : const MacroBlockD *xd, int *width,
273 : int *height,
274 : int *rows_within_bounds,
275 : int *cols_within_bounds) {
276 0 : const int block_height = block_size_high[bsize];
277 0 : const int block_width = block_size_wide[bsize];
278 0 : const int block_rows = (xd->mb_to_bottom_edge >= 0)
279 : ? block_height
280 0 : : (xd->mb_to_bottom_edge >> 3) + block_height;
281 0 : const int block_cols = (xd->mb_to_right_edge >= 0)
282 : ? block_width
283 0 : : (xd->mb_to_right_edge >> 3) + block_width;
284 :
285 0 : uint8_t subsampling_x = plane == 0 ? 0 : 1;
286 0 : uint8_t subsampling_y = plane == 0 ? 0 : 1;
287 :
288 0 : assert(block_width >= block_cols);
289 0 : assert(block_height >= block_rows);
290 0 : const int plane_block_width = block_width >> subsampling_x;
291 0 : const int plane_block_height = block_height >> subsampling_y;
292 : // Special handling for chroma sub8x8.
293 0 : const int is_chroma_sub8_x = plane > 0 && plane_block_width < 4;
294 0 : const int is_chroma_sub8_y = plane > 0 && plane_block_height < 4;
295 0 : if (width) *width = plane_block_width + 2 * is_chroma_sub8_x;
296 0 : if (height) *height = plane_block_height + 2 * is_chroma_sub8_y;
297 0 : if (rows_within_bounds) {
298 0 : *rows_within_bounds =
299 0 : (block_rows >> subsampling_y) + 2 * is_chroma_sub8_y;
300 : }
301 0 : if (cols_within_bounds) {
302 0 : *cols_within_bounds =
303 0 : (block_cols >> subsampling_x) + 2 * is_chroma_sub8_x;
304 : }
305 0 : }
306 :
307 : int av1_remove_duplicates(int *centroids, int num_centroids);
308 : // Bias toward using colors in the cache.
309 : // TODO: Try other schemes to improve compression.
310 0 : static AOM_INLINE void optimize_palette_colors(uint16_t *color_cache,
311 : int n_cache, int n_colors,
312 : int stride, int *centroids) {
313 0 : if (n_cache <= 0) return;
314 0 : for (int i = 0; i < n_colors * stride; i += stride) {
315 0 : int min_diff = abs(centroids[i] - (int)color_cache[0]);
316 0 : int idx = 0;
317 0 : for (int j = 1; j < n_cache; ++j) {
318 0 : const int this_diff = abs(centroids[i] - color_cache[j]);
319 0 : if (this_diff < min_diff) {
320 0 : min_diff = this_diff;
321 0 : idx = j;
322 : }
323 : }
324 0 : if (min_diff <= 1) centroids[i] = color_cache[idx];
325 : }
326 : }
327 : // Extends 'color_map' array from 'orig_width x orig_height' to 'new_width x
328 : // new_height'. Extra rows and columns are filled in by copying last valid
329 : // row/column.
330 0 : static AOM_INLINE void extend_palette_color_map(uint8_t *const color_map,
331 : int orig_width, int orig_height,
332 : int new_width, int new_height) {
333 : int j;
334 0 : assert(new_width >= orig_width);
335 0 : assert(new_height >= orig_height);
336 0 : if (new_width == orig_width && new_height == orig_height) return;
337 :
338 0 : for (j = orig_height - 1; j >= 0; --j) {
339 0 : memmove(color_map + j * new_width, color_map + j * orig_width, orig_width);
340 : // Copy last column to extra columns.
341 0 : memset(color_map + j * new_width + orig_width,
342 0 : color_map[j * new_width + orig_width - 1], new_width - orig_width);
343 : }
344 : // Copy last row to extra rows.
345 0 : for (j = orig_height; j < new_height; ++j) {
346 0 : memcpy(color_map + j * new_width, color_map + (orig_height - 1) * new_width,
347 : new_width);
348 : }
349 : }
350 0 : void palette_rd_y(
351 : PaletteInfo *palette_info,
352 : ModeDecisionContext *context_ptr,
353 : BlockSize bsize,
354 : const int *data,
355 : int *centroids, int n, uint16_t *color_cache, int n_cache
356 : )
357 : {
358 0 : optimize_palette_colors(color_cache, n_cache, n, 1, centroids);
359 0 : int k = av1_remove_duplicates(centroids, n);
360 0 : if (k < PALETTE_MIN_SIZE) {
361 : // Too few unique colors to create a palette. And DC_PRED will work
362 : // well for that case anyway. So skip.
363 0 : palette_info->pmi.palette_size[0] = 0;
364 0 : return;
365 : }
366 :
367 : //if (cpi->common.seq_params.use_highbitdepth)
368 : // for (int i = 0; i < k; ++i)
369 : // pmi->palette_colors[i] = clip_pixel_highbd(
370 : // (int)centroids[i], cpi->common.seq_params.bit_depth);
371 : //else
372 0 : for (int i = 0; i < k; ++i)
373 0 : palette_info->pmi.palette_colors[i] = clip_pixel(centroids[i]);
374 0 : palette_info->pmi.palette_size[0] = k;
375 :
376 0 : uint8_t *const color_map = palette_info->color_idx_map;
377 : int block_width, block_height, rows, cols;
378 0 : av1_get_block_dimensions(bsize, 0, context_ptr->cu_ptr->av1xd, &block_width, &block_height, &rows,
379 : &cols);
380 0 : av1_calc_indices(data, centroids, color_map, rows * cols, k, 1);
381 0 : extend_palette_color_map(color_map, cols, rows, block_width, block_height);
382 : }
383 :
384 : int eb_av1_count_colors(const uint8_t *src, int stride, int rows, int cols,
385 : int *val_count);
386 : int av1_count_colors_highbd(uint16_t *src, int stride, int rows, int cols,
387 : int bit_depth, int *val_count);
388 : /****************************************
389 : determine all palette luma candidates
390 : ****************************************/
391 0 : void search_palette_luma(
392 : PictureControlSet *picture_control_set_ptr,
393 : ModeDecisionContext *context_ptr,
394 : PaletteInfo *palette_cand,
395 : uint32_t *tot_palette_cands)
396 : {
397 : int colors, n;
398 0 : EbPictureBufferDesc *src_pic = picture_control_set_ptr->parent_pcs_ptr->enhanced_picture_ptr;
399 0 : const int src_stride = src_pic->stride_y;
400 0 : uint16_t * src16 = 0;
401 0 : const uint8_t *const src = src_pic->buffer_y + (context_ptr->cu_origin_x + src_pic->origin_x) + (context_ptr->cu_origin_y + src_pic->origin_y) * src_pic->stride_y;
402 : int block_width, block_height, rows, cols;
403 0 : uint8_t hbd_md = 0;
404 :
405 0 : Av1Common *cm = picture_control_set_ptr->parent_pcs_ptr->av1_cm;
406 0 : MacroBlockD *xd = context_ptr->cu_ptr->av1xd;
407 0 : TileInfo * tile = &context_ptr->sb_ptr->tile_info;
408 0 : BlockSize bsize = context_ptr->blk_geom->bsize;
409 0 : int32_t mirow = context_ptr->cu_origin_y >> 2;
410 0 : int32_t micol = context_ptr->cu_origin_x >> 2;
411 0 : xd->up_available = (mirow > tile->mi_row_start);
412 0 : xd->left_available = (micol > tile->mi_col_start);
413 0 : const int32_t bw = mi_size_wide[bsize];
414 0 : const int32_t bh = mi_size_high[bsize];
415 0 : xd->mb_to_top_edge = -((mirow * MI_SIZE) * 8);
416 0 : xd->mb_to_bottom_edge = ((cm->mi_rows - bh - mirow) * MI_SIZE) * 8;
417 0 : xd->mb_to_left_edge = -((micol * MI_SIZE) * 8);
418 0 : xd->mb_to_right_edge = ((cm->mi_cols - bw - micol) * MI_SIZE) * 8;
419 0 : xd->tile.mi_col_start = tile->mi_col_start;
420 0 : xd->tile.mi_col_end = tile->mi_col_end;
421 0 : xd->tile.mi_row_start = tile->mi_row_start;
422 0 : xd->tile.mi_row_end = tile->mi_row_end;
423 0 : xd->n8_h = bh;
424 0 : xd->n8_w = bw;
425 0 : xd->is_sec_rect = 0;
426 0 : if (xd->n8_w < xd->n8_h) {
427 : // Only mark is_sec_rect as 1 for the last block.
428 : // For PARTITION_VERT_4, it would be (0, 0, 0, 1);
429 : // For other partitions, it would be (0, 1).
430 0 : if (!((micol + xd->n8_w) & (xd->n8_h - 1))) xd->is_sec_rect = 1;
431 : }
432 :
433 0 : if (xd->n8_w > xd->n8_h)
434 0 : if (mirow & (xd->n8_w - 1)) xd->is_sec_rect = 1;
435 :
436 0 : int mi_stride = cm->mi_stride;
437 0 : const int32_t offset = mirow * mi_stride + micol;
438 0 : xd->mi = cm->pcs_ptr->mi_grid_base + offset;
439 0 : ModeInfo *miPtr = *xd->mi;
440 0 : if (xd->up_available) {
441 0 : xd->above_mbmi = &miPtr[-mi_stride].mbmi;
442 : }
443 : else
444 0 : xd->above_mbmi = NULL;
445 0 : if (xd->left_available) {
446 0 : xd->left_mbmi = &miPtr[-1].mbmi;
447 : }
448 : else
449 0 : xd->left_mbmi = NULL;
450 :
451 :
452 0 : av1_get_block_dimensions(context_ptr->blk_geom->bsize, 0, context_ptr->cu_ptr->av1xd, &block_width, &block_height, &rows,
453 : &cols);
454 :
455 : int count_buf[1 << 12]; // Maximum (1 << 12) color levels.
456 :
457 0 : if(hbd_md)
458 0 : colors = av1_count_colors_highbd(src16, src_stride, rows, cols, picture_control_set_ptr->parent_pcs_ptr->sequence_control_set_ptr->encoder_bit_depth, count_buf);
459 : else
460 0 : colors = eb_av1_count_colors(src, src_stride, rows, cols, count_buf);
461 :
462 0 : if (colors > 1 && colors <= 64) {
463 : int r, c, i;
464 0 : const int max_itr = 50;
465 0 : int *const data = context_ptr->palette_buffer.kmeans_data_buf;
466 : int centroids[PALETTE_MAX_SIZE];
467 : int lb, ub, val;
468 0 : lb = ub = src[0];
469 : {
470 0 : for (r = 0; r < rows; ++r) {
471 0 : for (c = 0; c < cols; ++c) {
472 0 : val = src[r * src_stride + c];
473 0 : data[r * cols + c] = val;
474 0 : if (val < lb)
475 0 : lb = val;
476 0 : else if (val > ub)
477 0 : ub = val;
478 : }
479 : }
480 : }
481 :
482 : uint16_t color_cache[2 * PALETTE_MAX_SIZE];
483 0 : const int n_cache = eb_get_palette_cache(xd, 0, color_cache);
484 :
485 : // Find the dominant colors, stored in top_colors[].
486 0 : int top_colors[PALETTE_MAX_SIZE] = { 0 };
487 0 : for (i = 0; i < AOMMIN(colors, PALETTE_MAX_SIZE); ++i) {
488 0 : int max_count = 0;
489 0 : for (int j = 0; j < (1 << EB_8BIT); ++j) {
490 0 : if (count_buf[j] > max_count) {
491 0 : max_count = count_buf[j];
492 0 : top_colors[i] = j;
493 : }
494 : }
495 0 : assert(max_count > 0);
496 0 : count_buf[top_colors[i]] = 0;
497 : }
498 :
499 : // Try the dominant colors directly.
500 : // TODO: Try to avoid duplicate computation in cases
501 : // where the dominant colors and the k-means results are similar.
502 :
503 0 : int step = (picture_control_set_ptr->parent_pcs_ptr->palette_mode == 6 && picture_control_set_ptr->temporal_layer_index > 0) ? 2 : 1;
504 0 : for (n = AOMMIN(colors, PALETTE_MAX_SIZE); n >= 2; n-=step) {
505 :
506 0 : for (i = 0; i < n; ++i)
507 0 : centroids[i] = top_colors[i];
508 :
509 0 : palette_rd_y(&palette_cand[*tot_palette_cands], context_ptr, bsize, data, centroids, n, color_cache, n_cache);
510 :
511 : //consider this candidate if it has some non zero palette
512 0 : if(palette_cand[*tot_palette_cands].pmi.palette_size[0]>2)
513 0 : (*tot_palette_cands)++;
514 0 : assert((*tot_palette_cands) <= 14);
515 : }
516 :
517 0 : if (picture_control_set_ptr->parent_pcs_ptr->palette_mode == 3)
518 0 : if (picture_control_set_ptr->parent_pcs_ptr->is_used_as_reference_flag == 0)
519 0 : return;
520 :
521 0 : if (picture_control_set_ptr->parent_pcs_ptr->palette_mode == 5 || picture_control_set_ptr->parent_pcs_ptr->palette_mode == 6)
522 0 : if (picture_control_set_ptr->temporal_layer_index > 0)
523 0 : return;
524 :
525 : // K-means clustering.
526 0 : for (n = AOMMIN(colors, PALETTE_MAX_SIZE); n >= 2; --n) {
527 0 : if (colors == PALETTE_MIN_SIZE) {
528 : // Special case: These colors automatically become the centroids.
529 0 : assert(colors == n);
530 0 : assert(colors == 2);
531 0 : centroids[0] = lb;
532 0 : centroids[1] = ub;
533 : }
534 : else {
535 0 : for (i = 0; i < n; ++i) {
536 0 : centroids[i] = lb + (2 * i + 1) * (ub - lb) / n / 2;
537 : }
538 0 : uint8_t *const color_map = palette_cand[*tot_palette_cands].color_idx_map;
539 0 : av1_k_means(data, centroids, color_map, rows * cols, n, 1, max_itr);
540 : }
541 :
542 0 : palette_rd_y(&palette_cand[*tot_palette_cands], context_ptr, bsize, data, centroids, n, color_cache, n_cache);
543 :
544 : //consider this candidate if it has some non zero palette
545 0 : if (palette_cand[*tot_palette_cands].pmi.palette_size[0] > 2)
546 0 : (*tot_palette_cands)++;
547 :
548 0 : assert((*tot_palette_cands) <= 14);
549 : }
550 : }
551 : }
552 :
553 : /* clang-format off */
554 : typedef AomCdfProb(*MapCdf)[PALETTE_COLOR_INDEX_CONTEXTS]
555 : [CDF_SIZE(PALETTE_COLORS)];
556 : typedef const int(*ColorCost)[PALETTE_SIZES][PALETTE_COLOR_INDEX_CONTEXTS]
557 : [PALETTE_COLORS];
558 : /* clang-format on */
559 :
560 : typedef struct {
561 : int rows;
562 : int cols;
563 : int n_colors;
564 : int plane_width;
565 : int plane_height;
566 : uint8_t *color_map;
567 : MapCdf map_cdf;
568 : ColorCost color_cost;
569 : } Av1ColorMapParam;
570 :
571 0 : static void get_palette_params(FRAME_CONTEXT *frame_context, CodingUnit*cu_ptr, int plane,
572 : BlockSize bsize, Av1ColorMapParam *params) {
573 0 : const MacroBlockD *const xd = cu_ptr->av1xd;
574 0 : MbModeInfo * mbmi = &(xd->mi[0]->mbmi);
575 0 : const PaletteModeInfo *const pmi = &mbmi->palette_mode_info;
576 0 : params->color_map = cu_ptr->palette_info.color_idx_map;
577 0 : params->map_cdf = plane ? frame_context->palette_uv_color_index_cdf
578 0 : : frame_context->palette_y_color_index_cdf;
579 0 : params->color_cost = NULL;
580 0 : params->n_colors = pmi->palette_size[plane];
581 0 : av1_get_block_dimensions(bsize, plane, xd, ¶ms->plane_width, NULL,
582 : ¶ms->rows, ¶ms->cols);
583 0 : }
584 :
585 0 : static void get_color_map_params(FRAME_CONTEXT *frame_context, CodingUnit*cu_ptr , int plane,
586 : BlockSize bsize, TxSize tx_size,
587 : COLOR_MAP_TYPE type,
588 : Av1ColorMapParam *params) {
589 : (void)tx_size;
590 0 : memset(params, 0, sizeof(*params));
591 0 : switch (type) {
592 0 : case PALETTE_MAP: get_palette_params(frame_context, cu_ptr, plane, bsize, params); break;
593 0 : default: assert(0 && "Invalid color map type"); return;
594 : }
595 : }
596 0 : static void get_palette_params_rate(PaletteInfo *palette_info, MdRateEstimationContext *rate_table, CodingUnit*cu_ptr, int plane,
597 : BlockSize bsize, Av1ColorMapParam *params) {
598 0 : const MacroBlockD *const xd = cu_ptr->av1xd;
599 0 : const PaletteModeInfo *const pmi = &palette_info->pmi;
600 :
601 0 : params->color_map = palette_info->color_idx_map;
602 0 : params->map_cdf = NULL;
603 0 : params->color_cost = plane ? NULL : &rate_table->palette_ycolor_fac_bitss;
604 0 : params->n_colors = pmi->palette_size[plane];
605 :
606 0 : av1_get_block_dimensions(bsize, plane, xd, ¶ms->plane_width, NULL,
607 : ¶ms->rows, ¶ms->cols);
608 0 : }
609 :
610 0 : static void get_color_map_params_rate(PaletteInfo *palette_info, MdRateEstimationContext *rate_table,/*const MACROBLOCK *const x*/ CodingUnit*cu_ptr, int plane,
611 : BlockSize bsize,
612 : COLOR_MAP_TYPE type,
613 : Av1ColorMapParam *params) {
614 0 : memset(params, 0, sizeof(*params));
615 0 : switch (type) {
616 0 : case PALETTE_MAP: get_palette_params_rate(palette_info, rate_table, cu_ptr, plane, bsize, params); break;
617 0 : default: assert(0 && "Invalid color map type"); return;
618 : }
619 : }
620 : #define MAX_COLOR_CONTEXT_HASH 8
621 : // Negative values are invalid
622 : int palette_color_index_context_lookup[MAX_COLOR_CONTEXT_HASH +
623 : 1] = { -1, -1, 0, -1, -1,
624 : 4, 3, 2, 1 };
625 :
626 : #define NUM_PALETTE_NEIGHBORS 3 // left, top-left and top.
627 0 : int av1_get_palette_color_index_context(const uint8_t *color_map, int stride,
628 : int r, int c, int palette_size,
629 : uint8_t *color_order, int *color_idx) {
630 0 : assert(palette_size <= PALETTE_MAX_SIZE);
631 0 : assert(r > 0 || c > 0);
632 :
633 : // Get color indices of neighbors.
634 : int color_neighbors[NUM_PALETTE_NEIGHBORS];
635 0 : color_neighbors[0] = (c - 1 >= 0) ? color_map[r * stride + c - 1] : -1;
636 0 : color_neighbors[1] =
637 0 : (c - 1 >= 0 && r - 1 >= 0) ? color_map[(r - 1) * stride + c - 1] : -1;
638 0 : color_neighbors[2] = (r - 1 >= 0) ? color_map[(r - 1) * stride + c] : -1;
639 :
640 : // The +10 below should not be needed. But we get a warning "array subscript
641 : // is above array bounds [-Werror=array-bounds]" without it, possibly due to
642 : // this (or similar) bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124
643 0 : int scores[PALETTE_MAX_SIZE + 10] = { 0 };
644 : int i;
645 : static const int weights[NUM_PALETTE_NEIGHBORS] = { 2, 1, 2 };
646 0 : for (i = 0; i < NUM_PALETTE_NEIGHBORS; ++i) {
647 0 : if (color_neighbors[i] >= 0) {
648 0 : scores[color_neighbors[i]] += weights[i];
649 : }
650 : }
651 :
652 : int inverse_color_order[PALETTE_MAX_SIZE];
653 0 : for (i = 0; i < PALETTE_MAX_SIZE; ++i) {
654 0 : color_order[i] = i;
655 0 : inverse_color_order[i] = i;
656 : }
657 :
658 : // Get the top NUM_PALETTE_NEIGHBORS scores (sorted from large to small).
659 0 : for (i = 0; i < NUM_PALETTE_NEIGHBORS; ++i) {
660 0 : int max = scores[i];
661 0 : int max_idx = i;
662 0 : for (int j = i + 1; j < palette_size; ++j) {
663 0 : if (scores[j] > max) {
664 0 : max = scores[j];
665 0 : max_idx = j;
666 : }
667 : }
668 0 : if (max_idx != i) {
669 : // Move the score at index 'max_idx' to index 'i', and shift the scores
670 : // from 'i' to 'max_idx - 1' by 1.
671 0 : const int max_score = scores[max_idx];
672 0 : const uint8_t max_color_order = color_order[max_idx];
673 0 : for (int k = max_idx; k > i; --k) {
674 0 : scores[k] = scores[k - 1];
675 0 : color_order[k] = color_order[k - 1];
676 0 : inverse_color_order[color_order[k]] = k;
677 : }
678 0 : scores[i] = max_score;
679 0 : color_order[i] = max_color_order;
680 0 : inverse_color_order[color_order[i]] = i;
681 : }
682 : }
683 :
684 0 : if (color_idx != NULL)
685 0 : *color_idx = inverse_color_order[color_map[r * stride + c]];
686 :
687 : // Get hash value of context.
688 0 : int color_index_ctx_hash = 0;
689 : static const int hash_multipliers[NUM_PALETTE_NEIGHBORS] = { 1, 2, 2 };
690 0 : for (i = 0; i < NUM_PALETTE_NEIGHBORS; ++i) {
691 0 : color_index_ctx_hash += scores[i] * hash_multipliers[i];
692 : }
693 0 : assert(color_index_ctx_hash > 0);
694 0 : assert(color_index_ctx_hash <= MAX_COLOR_CONTEXT_HASH);
695 :
696 : // Lookup context from hash.
697 0 : const int color_index_ctx =
698 : palette_color_index_context_lookup[color_index_ctx_hash];
699 0 : assert(color_index_ctx >= 0);
700 0 : assert(color_index_ctx < PALETTE_COLOR_INDEX_CONTEXTS);
701 0 : return color_index_ctx;
702 : }
703 : #undef NUM_PALETTE_NEIGHBORS
704 : #undef MAX_COLOR_CONTEXT_HASH
705 0 : static int cost_and_tokenize_map(Av1ColorMapParam *param, TOKENEXTRA **t,
706 : int plane, int calc_rate, int allow_update_cdf,
707 : MapCdf map_pb_cdf) {
708 0 : const uint8_t *const color_map = param->color_map;
709 0 : MapCdf map_cdf = param->map_cdf;
710 0 : ColorCost color_cost = param->color_cost;
711 0 : const int plane_block_width = param->plane_width;
712 0 : const int rows = param->rows;
713 0 : const int cols = param->cols;
714 0 : const int n = param->n_colors;
715 0 : const int palette_size_idx = n - PALETTE_MIN_SIZE;
716 0 : int this_rate = 0;
717 : uint8_t color_order[PALETTE_MAX_SIZE];
718 :
719 : (void)plane;
720 :
721 0 : for (int k = 1; k < rows + cols - 1; ++k) {
722 0 : for (int j = AOMMIN(k, cols - 1); j >= AOMMAX(0, k - rows + 1); --j) {
723 0 : int i = k - j;
724 : int color_new_idx;
725 0 : const int color_ctx = av1_get_palette_color_index_context(
726 : color_map, plane_block_width, i, j, n, color_order, &color_new_idx);
727 0 : assert(color_new_idx >= 0 && color_new_idx < n);
728 0 : if (calc_rate) {
729 0 : this_rate += (*color_cost)[palette_size_idx][color_ctx][color_new_idx];
730 : }
731 : else {
732 0 : (*t)->token = color_new_idx;
733 0 : (*t)->color_map_cdf = map_pb_cdf[palette_size_idx][color_ctx];
734 0 : ++(*t);
735 0 : if (allow_update_cdf)
736 0 : update_cdf(map_cdf[palette_size_idx][color_ctx], color_new_idx, n);
737 : #if CONFIG_ENTROPY_STATS
738 : if (plane) {
739 : ++counts->palette_uv_color_index[palette_size_idx][color_ctx]
740 : [color_new_idx];
741 : }
742 : else {
743 : ++counts->palette_y_color_index[palette_size_idx][color_ctx]
744 : [color_new_idx];
745 : }
746 : #endif
747 : }
748 : }
749 : }
750 0 : if (calc_rate) return this_rate;
751 0 : return 0;
752 : }
753 :
754 0 : void av1_tokenize_color_map(FRAME_CONTEXT *frameContext,CodingUnit*cu_ptr, int plane,
755 : TOKENEXTRA **t, BlockSize bsize, TxSize tx_size,
756 : COLOR_MAP_TYPE type, int allow_update_cdf) {
757 0 : assert(plane == 0 || plane == 1);
758 : Av1ColorMapParam color_map_params;
759 0 : get_color_map_params(frameContext, cu_ptr, plane, bsize, tx_size, type, &color_map_params);
760 : // The first color index does not use context or entropy.
761 0 : (*t)->token = color_map_params.color_map[0];
762 0 : (*t)->color_map_cdf = NULL;
763 0 : ++(*t);
764 0 : MapCdf map_pb_cdf = plane ? frameContext->palette_uv_color_index_cdf
765 0 : : frameContext->palette_y_color_index_cdf;
766 0 : cost_and_tokenize_map(&color_map_params, t, plane, 0, allow_update_cdf,
767 : map_pb_cdf);
768 0 : }
769 0 : int av1_cost_color_map(PaletteInfo *palette_info, MdRateEstimationContext *rate_table, CodingUnit*cu_ptr, int plane, BlockSize bsize,
770 : COLOR_MAP_TYPE type) {
771 0 : assert(plane == 0 || plane == 1);
772 : Av1ColorMapParam color_map_params;
773 0 : get_color_map_params_rate(palette_info,rate_table, cu_ptr, plane, bsize, type, &color_map_params);
774 0 : MapCdf map_pb_cdf = NULL;
775 0 : return cost_and_tokenize_map(&color_map_params, NULL, plane, 1, 0,
776 : map_pb_cdf);
777 : }
778 : #endif
|
