Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 1 | /* |
Yaowu Xu | bde4ac8 | 2016-11-28 15:26:06 -0800 | [diff] [blame] | 2 | * Copyright (c) 2016, Alliance for Open Media. All rights reserved |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 3 | * |
Yaowu Xu | bde4ac8 | 2016-11-28 15:26:06 -0800 | [diff] [blame] | 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. |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 10 | */ |
| 11 | |
| 12 | #include <math.h> |
| 13 | #include <stdlib.h> |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 14 | |
| 15 | #include "av1/encoder/cost.h" |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 16 | #include "av1/encoder/palette.h" |
Alex Converse | 9d068c1 | 2017-08-03 11:48:19 -0700 | [diff] [blame] | 17 | #include "av1/encoder/random.h" |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 18 | |
Alex Converse | 15aa8c0 | 2017-08-03 12:31:16 -0700 | [diff] [blame] | 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 |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 25 | |
Hui Su | 5891f98 | 2017-12-18 16:18:23 -0800 | [diff] [blame] | 26 | static int int_comparer(const void *a, const void *b) { |
| 27 | return (*(int *)a - *(int *)b); |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 28 | } |
| 29 | |
Hui Su | 5891f98 | 2017-12-18 16:18:23 -0800 | [diff] [blame] | 30 | int av1_remove_duplicates(int *centroids, int num_centroids) { |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 31 | int num_unique; // number of unique centroids |
| 32 | int i; |
Hui Su | 5891f98 | 2017-12-18 16:18:23 -0800 | [diff] [blame] | 33 | qsort(centroids, num_centroids, sizeof(*centroids), int_comparer); |
Yaowu Xu | c27fc14 | 2016-08-22 16:08:15 -0700 | [diff] [blame] | 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 | |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 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; |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 58 | } |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 59 | int bits_per_delta = AOMMAX(av1_ceil_log2(max_delta + 1 - min_val), min_bits); |
hui su | fa4ff85 | 2017-05-15 12:20:50 -0700 | [diff] [blame] | 60 | assert(bits_per_delta <= bit_depth); |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 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; |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 68 | } |
| 69 | |
hui su | fa4ff85 | 2017-05-15 12:20:50 -0700 | [diff] [blame] | 70 | int av1_index_color_cache(const uint16_t *color_cache, int n_cache, |
| 71 | const uint16_t *colors, int n_colors, |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 72 | uint8_t *cache_color_found, int *out_cache_colors) { |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 73 | if (n_cache <= 0) { |
hui su | fa4ff85 | 2017-05-15 12:20:50 -0700 | [diff] [blame] | 74 | for (int i = 0; i < n_colors; ++i) out_cache_colors[i] = colors[i]; |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 75 | return n_colors; |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 76 | } |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 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) { |
hui su | fa4ff85 | 2017-05-15 12:20:50 -0700 | [diff] [blame] | 83 | if (colors[j] == color_cache[i]) { |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 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) |
hui su | fa4ff85 | 2017-05-15 12:20:50 -0700 | [diff] [blame] | 93 | if (!in_cache_flags[i]) out_cache_colors[j++] = colors[i]; |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 94 | assert(j == n_colors - n_in_cache); |
| 95 | return j; |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 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; |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 103 | int max_d = 0; |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 104 | *min_bits = bit_depth - 4; |
| 105 | *zero_count = 0; |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 106 | for (int i = 1; i < n; ++i) { |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 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 | } |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 116 | |
| 117 | int av1_palette_color_cost_y(const PALETTE_MODE_INFO *const pmi, |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 118 | uint16_t *color_cache, int n_cache, |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 119 | int bit_depth) { |
| 120 | const int n = pmi->palette_size[0]; |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 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); |
Hui Su | 751a233 | 2018-01-23 11:35:03 -0800 | [diff] [blame] | 128 | return av1_cost_literal(total_bits); |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 129 | } |
| 130 | |
| 131 | int av1_palette_color_cost_uv(const PALETTE_MODE_INFO *const pmi, |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 132 | uint16_t *color_cache, int n_cache, |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 133 | int bit_depth) { |
| 134 | const int n = pmi->palette_size[1]; |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 135 | int total_bits = 0; |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 136 | // U channel palette color cost. |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 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 | |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 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; |
hui su | 33567b2 | 2017-04-30 16:40:19 -0700 | [diff] [blame] | 152 | total_bits += 1 + AOMMIN(bits_using_delta, bits_using_raw); |
Hui Su | 751a233 | 2018-01-23 11:35:03 -0800 | [diff] [blame] | 153 | return av1_cost_literal(total_bits); |
hui su | d13c24a | 2017-04-07 16:13:07 -0700 | [diff] [blame] | 154 | } |