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 /*!\file
13 * \brief Declares functions used in palette search.
14 */
15 #ifndef AOM_AV1_ENCODER_PALETTE_H_
16 #define AOM_AV1_ENCODER_PALETTE_H_
17
18 #include "av1/common/blockd.h"
19
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23
24 struct AV1_COMP;
25 struct PICK_MODE_CONTEXT;
26 struct macroblock;
27
28 /*!\cond */
29 #define AV1_K_MEANS_RENAME(func, dim) func##_dim##dim##_c
30
31 void AV1_K_MEANS_RENAME(av1_k_means, 1)(const int16_t *data, int16_t *centroids,
32 uint8_t *indices, int n, int k,
33 int max_itr);
34 void AV1_K_MEANS_RENAME(av1_k_means, 2)(const int16_t *data, int16_t *centroids,
35 uint8_t *indices, int n, int k,
36 int max_itr);
37 /*!\endcond */
38
39 /*!\brief Calculates the cluster to which each data point belong.
40 *
41 * \ingroup palette_mode_search
42 * \param[in] data The data points whose cluster indices are
43 * to be computed. The data layout is
44 * NUM_DATA_POINTS X DATA_DIM.
45 * \param[in] centroids Pointer to the centroids. The data layout
46 * is NUM_CENTROIDS X DATA_DIM.
47 * \param[in] indices Pointer to store the computed indices.
48 * \param[in] n Number of data points.
49 * \param[in] k Number of clusters.
50 * \param[in] dim Data dimension.
51 *
52 * \remark Returns nothing, but saves each data's cluster index in \a indices.
53 */
av1_calc_indices(const int16_t * data,const int16_t * centroids,uint8_t * indices,int n,int k,int dim)54 static INLINE void av1_calc_indices(const int16_t *data,
55 const int16_t *centroids, uint8_t *indices,
56 int n, int k, int dim) {
57 assert(n > 0);
58 assert(k > 0);
59 if (dim == 1) {
60 av1_calc_indices_dim1(data, centroids, indices, /*total_dist=*/NULL, n, k);
61 } else if (dim == 2) {
62 av1_calc_indices_dim2(data, centroids, indices, /*total_dist=*/NULL, n, k);
63 } else {
64 assert(0 && "Untemplated k means dimension");
65 }
66 }
67
68 /*!\brief Performs k-means cluster on the data.
69 *
70 * \ingroup palette_mode_search
71 * \param[in] data The data points to be clustered. The data
72 * layout is NUM_DATA_POINTS X DATA_DIM.
73 * \param[in] centroids Pointer to store the computed centroids.
74 * The data layout is
75 * NUM_CENTROIDS X DATA_DIM.
76 * \param[in] indices Pointer to store the computed indices. For
77 * each training data.
78 * \param[in] n Number of data points.
79 * \param[in] k Number of clusters.
80 * \param[in] dim Data dimension.
81 * \param[in] max_itr Maximum number of iterations to run.
82 *
83 * \remark Returns nothing, but saves each cluster's centroid in centroids and
84 * each data's cluster index in \a indices.
85 *
86 * \attention The output centroids are rounded off to nearest integers.
87 */
av1_k_means(const int16_t * data,int16_t * centroids,uint8_t * indices,int n,int k,int dim,int max_itr)88 static INLINE void av1_k_means(const int16_t *data, int16_t *centroids,
89 uint8_t *indices, int n, int k, int dim,
90 int max_itr) {
91 assert(n > 0);
92 assert(k > 0);
93 if (dim == 1) {
94 AV1_K_MEANS_RENAME(av1_k_means, 1)(data, centroids, indices, n, k, max_itr);
95 } else if (dim == 2) {
96 AV1_K_MEANS_RENAME(av1_k_means, 2)(data, centroids, indices, n, k, max_itr);
97 } else {
98 assert(0 && "Untemplated k means dimension");
99 }
100 }
101
102 /*!\brief Removes duplicated centroid indices.
103 *
104 * \ingroup palette_mode_search
105 * \param[in] centroids A list of centroids index.
106 * \param[in] num_centroids Number of centroids.
107 *
108 * \return Returns the number of unique centroids and saves the unique centroids
109 * in beginning of the centroids array.
110 *
111 * \attention The centroids should be rounded to integers before calling this
112 * method.
113 */
114 int av1_remove_duplicates(int16_t *centroids, int num_centroids);
115
116 /*!\brief Checks what colors are in the color cache.
117 *
118 * \ingroup palette_mode_search
119 * \param[in] color_cache A cache of colors.
120 * \param[in] n_cache Number of colors in the cache.
121 * \param[in] colors New base colors.
122 * \param[in] n_colors Number of new colors.
123 * \param[in] cache_color_found Stores what cached colors are presented in
124 * colors.
125 * \param[in] out_cache_colors Stores what colors are not in the cache.
126 *
127 * \return Returns the number of colors that are not in cache. In addition,
128 * records whether each cache color is presented in colors in cache_color_found,
129 * and stores and stores the out of cache colors in out_cache_colors.
130 */
131 int av1_index_color_cache(const uint16_t *color_cache, int n_cache,
132 const uint16_t *colors, int n_colors,
133 uint8_t *cache_color_found, int *out_cache_colors);
134
135 /*!\brief Gets the rate cost for each delta-encoding v palette.
136 *
137 * \ingroup palette_mode_search
138 * \param[in] pmi Struct that stores the palette mode info.
139 * \param[in] bit_depth Pixel bitdepth of the sequence.
140 * \param[in] zero_count Stores the number of zero deltas.
141 * \param[in] min_bits Minimum bits for the deltas. Sets to
142 * bit_depth - 4.
143 *
144 * \return Returns the number of bits used to transmit each v palette color
145 * delta and assigns zero_count with the number of deltas being 0.
146 */
147 int av1_get_palette_delta_bits_v(const PALETTE_MODE_INFO *const pmi,
148 int bit_depth, int *zero_count, int *min_bits);
149
150 /*!\brief Gets the rate cost for transmitting luma palette color values.
151 *
152 * \ingroup palette_mode_search
153 * \param[in] pmi Struct that stores the palette mode info.
154 * \param[in] color_cache Color cache presented at the decoder.
155 * \param[in] n_cache Number of colors in the cache.
156 * \param[in] bit_depth Pixel bitdepth of the sequence.
157 *
158 * \return Returns the rate needed to transmit the palette. Note that this does
159 * not include the cost of transmitted the color map.
160 */
161 int av1_palette_color_cost_y(const PALETTE_MODE_INFO *const pmi,
162 const uint16_t *color_cache, int n_cache,
163 int bit_depth);
164
165 /*!\brief Gets the rate cost for transmitting luma palette chroma values.
166 *
167 * \ingroup palette_mode_search
168 * \param[in] pmi Struct that stores the palette mode info.
169 * \param[in] color_cache Color cache presented at the decoder.
170 * \param[in] n_cache Number of colors in the cache.
171 * \param[in] bit_depth Pixel bitdepth of the sequence.
172 *
173 * \return Returns the rate needed to transmit the palette. Note that this does
174 * not include the cost of transmitted the color map.
175 */
176 int av1_palette_color_cost_uv(const PALETTE_MODE_INFO *const pmi,
177 const uint16_t *color_cache, int n_cache,
178 int bit_depth);
179
180 /*!\brief Search for the best palette in the luma plane.
181 *
182 * \ingroup palette_mode_search
183 * \callergraph
184 * This function is used in both inter and intra frame coding.
185 */
186 void av1_rd_pick_palette_intra_sby(
187 const struct AV1_COMP *cpi, struct macroblock *x, BLOCK_SIZE bsize,
188 int dc_mode_cost, MB_MODE_INFO *best_mbmi, uint8_t *best_palette_color_map,
189 int64_t *best_rd, int *rate, int *rate_tokenonly, int64_t *distortion,
190 uint8_t *skippable, int *beat_best_rd, struct PICK_MODE_CONTEXT *ctx,
191 uint8_t *best_blk_skip, uint8_t *tx_type_map);
192
193 /*!\brief Search for the best palette in the chroma plane.
194 *
195 * \ingroup palette_mode_search
196 * \callergraph
197 * This function is used in both inter and intra frame coding.
198 */
199 void av1_rd_pick_palette_intra_sbuv(const struct AV1_COMP *cpi,
200 struct macroblock *x, int dc_mode_cost,
201 uint8_t *best_palette_color_map,
202 MB_MODE_INFO *const best_mbmi,
203 int64_t *best_rd, int *rate,
204 int *rate_tokenonly, int64_t *distortion,
205 uint8_t *skippable);
206
207 /*!\brief Resets palette color map for chroma channels.
208 */
209 void av1_restore_uv_color_map(const struct AV1_COMP *cpi, struct macroblock *x);
210
211 #ifdef __cplusplus
212 } // extern "C"
213 #endif
214
215 #endif // AOM_AV1_ENCODER_PALETTE_H_
216