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 15 #include "av1/encoder/cost.h" 16 #include "av1/encoder/palette.h" 17 #include "av1/encoder/random.h" 18 19 #define AV1_K_MEANS_DIM 1 20 #include "av1/encoder/k_means_template.h" 21 #undef AV1_K_MEANS_DIM 22 #define AV1_K_MEANS_DIM 2 23 #include "av1/encoder/k_means_template.h" 24 #undef AV1_K_MEANS_DIM 25 26 static int int_comparer(const void *a, const void *b) { 27 return (*(int *)a - *(int *)b); 28 } 29 30 int av1_remove_duplicates(int *centroids, int num_centroids) { 31 int num_unique; // number of unique centroids 32 int i; 33 qsort(centroids, num_centroids, sizeof(*centroids), int_comparer); 34 // Remove duplicates. 35 num_unique = 1; 36 for (i = 1; i < num_centroids; ++i) { 37 if (centroids[i] != centroids[i - 1]) { // found a new unique centroid 38 centroids[num_unique++] = centroids[i]; 39 } 40 } 41 return num_unique; 42 } 43 44 static int delta_encode_cost(const int *colors, int num, int bit_depth, 45 int min_val) { 46 if (num <= 0) return 0; 47 int bits_cost = bit_depth; 48 if (num == 1) return bits_cost; 49 bits_cost += 2; 50 int max_delta = 0; 51 int deltas[PALETTE_MAX_SIZE]; 52 const int min_bits = bit_depth - 3; 53 for (int i = 1; i < num; ++i) { 54 const int delta = colors[i] - colors[i - 1]; 55 deltas[i - 1] = delta; 56 assert(delta >= min_val); 57 if (delta > max_delta) max_delta = delta; 58 } 59 int bits_per_delta = AOMMAX(av1_ceil_log2(max_delta + 1 - min_val), min_bits); 60 assert(bits_per_delta <= bit_depth); 61 int range = (1 << bit_depth) - colors[0] - min_val; 62 for (int i = 0; i < num - 1; ++i) { 63 bits_cost += bits_per_delta; 64 range -= deltas[i]; 65 bits_per_delta = AOMMIN(bits_per_delta, av1_ceil_log2(range)); 66 } 67 return bits_cost; 68 } 69 70 int av1_index_color_cache(const uint16_t *color_cache, int n_cache, 71 const uint16_t *colors, int n_colors, 72 uint8_t *cache_color_found, int *out_cache_colors) { 73 if (n_cache <= 0) { 74 for (int i = 0; i < n_colors; ++i) out_cache_colors[i] = colors[i]; 75 return n_colors; 76 } 77 memset(cache_color_found, 0, n_cache * sizeof(*cache_color_found)); 78 int n_in_cache = 0; 79 int in_cache_flags[PALETTE_MAX_SIZE]; 80 memset(in_cache_flags, 0, sizeof(in_cache_flags)); 81 for (int i = 0; i < n_cache && n_in_cache < n_colors; ++i) { 82 for (int j = 0; j < n_colors; ++j) { 83 if (colors[j] == color_cache[i]) { 84 in_cache_flags[j] = 1; 85 cache_color_found[i] = 1; 86 ++n_in_cache; 87 break; 88 } 89 } 90 } 91 int j = 0; 92 for (int i = 0; i < n_colors; ++i) 93 if (!in_cache_flags[i]) out_cache_colors[j++] = colors[i]; 94 assert(j == n_colors - n_in_cache); 95 return j; 96 } 97 98 int av1_get_palette_delta_bits_v(const PALETTE_MODE_INFO *const pmi, 99 int bit_depth, int *zero_count, 100 int *min_bits) { 101 const int n = pmi->palette_size[1]; 102 const int max_val = 1 << bit_depth; 103 int max_d = 0; 104 *min_bits = bit_depth - 4; 105 *zero_count = 0; 106 for (int i = 1; i < n; ++i) { 107 const int delta = pmi->palette_colors[2 * PALETTE_MAX_SIZE + i] - 108 pmi->palette_colors[2 * PALETTE_MAX_SIZE + i - 1]; 109 const int v = abs(delta); 110 const int d = AOMMIN(v, max_val - v); 111 if (d > max_d) max_d = d; 112 if (d == 0) ++(*zero_count); 113 } 114 return AOMMAX(av1_ceil_log2(max_d + 1), *min_bits); 115 } 116 117 int av1_palette_color_cost_y(const PALETTE_MODE_INFO *const pmi, 118 uint16_t *color_cache, int n_cache, 119 int bit_depth) { 120 const int n = pmi->palette_size[0]; 121 int out_cache_colors[PALETTE_MAX_SIZE]; 122 uint8_t cache_color_found[2 * PALETTE_MAX_SIZE]; 123 const int n_out_cache = 124 av1_index_color_cache(color_cache, n_cache, pmi->palette_colors, n, 125 cache_color_found, out_cache_colors); 126 const int total_bits = 127 n_cache + delta_encode_cost(out_cache_colors, n_out_cache, bit_depth, 1); 128 return av1_cost_literal(total_bits); 129 } 130 131 int av1_palette_color_cost_uv(const PALETTE_MODE_INFO *const pmi, 132 uint16_t *color_cache, int n_cache, 133 int bit_depth) { 134 const int n = pmi->palette_size[1]; 135 int total_bits = 0; 136 // U channel palette color cost. 137 int out_cache_colors[PALETTE_MAX_SIZE]; 138 uint8_t cache_color_found[2 * PALETTE_MAX_SIZE]; 139 const int n_out_cache = av1_index_color_cache( 140 color_cache, n_cache, pmi->palette_colors + PALETTE_MAX_SIZE, n, 141 cache_color_found, out_cache_colors); 142 total_bits += 143 n_cache + delta_encode_cost(out_cache_colors, n_out_cache, bit_depth, 0); 144 145 // V channel palette color cost. 146 int zero_count = 0, min_bits_v = 0; 147 const int bits_v = 148 av1_get_palette_delta_bits_v(pmi, bit_depth, &zero_count, &min_bits_v); 149 const int bits_using_delta = 150 2 + bit_depth + (bits_v + 1) * (n - 1) - zero_count; 151 const int bits_using_raw = bit_depth * n; 152 total_bits += 1 + AOMMIN(bits_using_delta, bits_using_raw); 153 return av1_cost_literal(total_bits); 154 } 155
