1// Aseprite Render Library
2// Copyright (c) 2020 Igara Studio S.A.
3// Copyright (c) 2001-2015 David Capello
4//
5// This file is released under the terms of the MIT license.
6// Read LICENSE.txt for more information.
7
8#ifndef RENDER_COLOR_HISTOGRAM_H_INCLUDED
9#define RENDER_COLOR_HISTOGRAM_H_INCLUDED
10#pragma once
11
12#include <limits>
13#include <vector>
14
15#include "doc/color.h"
16#include "doc/image.h"
17#include "doc/image_traits.h"
18#include "doc/palette.h"
19
20#include "render/median_cut.h"
21
22namespace render {
23 using namespace doc;
24
25 template<int RBits, // Number of bits for each component in the histogram
26 int GBits,
27 int BBits,
28 int ABits>
29 class ColorHistogram {
30 public:
31 // Number of elements in histogram for each RGB component
32 enum {
33 RElements = 1 << RBits,
34 GElements = 1 << GBits,
35 BElements = 1 << BBits,
36 AElements = 1 << ABits
37 };
38
39 ColorHistogram()
40 : m_histogram(RElements*GElements*BElements*AElements, 0)
41 , m_useHighPrecision(true) {
42 }
43
44 // Returns the number of points in the specified histogram
45 // entry. Each rgba-index is in the range of the histogram, e.g.
46 // r=[0,RElements), g=[0,GElements), etc.
47 std::size_t at(int r, int g, int b, int a) const {
48 return m_histogram[histogramIndex(r, g, b, a)];
49 }
50
51 // Add the specified "color" in the histogram as many times as the
52 // specified value in "count".
53 void addSamples(doc::color_t color, std::size_t count = 1) {
54 int i = histogramIndex(color);
55
56 if (m_histogram[i] < std::numeric_limits<std::size_t>::max()-count) // Avoid overflow
57 m_histogram[i] += count;
58 else
59 m_histogram[i] = std::numeric_limits<std::size_t>::max();
60
61 // Accurate colors are used only for less than 256 colors. If the
62 // image has more than 256 colors the m_histogram is used
63 // instead.
64 if (m_useHighPrecision) {
65 std::vector<doc::color_t>::iterator it =
66 std::find(m_highPrecision.begin(), m_highPrecision.end(), color);
67
68 // The color is not in the high-precision table
69 if (it == m_highPrecision.end()) {
70 if (m_highPrecision.size() < 256) {
71 m_highPrecision.push_back(color);
72 }
73 else {
74 // In this case we reach the limit for the high-precision histogram.
75 m_useHighPrecision = false;
76 }
77 }
78 }
79 }
80
81 // Creates a set of entries for the given palette in the given range
82 // with the more important colors in the histogram. Returns the
83 // number of used entries in the palette (maybe the range [from,to]
84 // is more than necessary).
85 int createOptimizedPalette(Palette* palette) {
86 // Can we use the high-precision table?
87 if (m_useHighPrecision && int(m_highPrecision.size()) <= palette->size()) {
88 for (int i=0; i<(int)m_highPrecision.size(); ++i)
89 palette->setEntry(i, m_highPrecision[i]);
90
91 return m_highPrecision.size();
92 }
93 // OK, we have to use the histogram and some algorithm (like
94 // median-cut) to quantize "optimal" colors.
95 else {
96 std::vector<doc::color_t> result;
97 median_cut(*this, palette->size(), result);
98
99 for (int i=0; i<(int)result.size(); ++i)
100 palette->setEntry(i, result[i]);
101
102 return result.size();
103 }
104 }
105
106 bool isHighPrecision() { return m_useHighPrecision; }
107 int highPrecisionSize() { return m_highPrecision.size(); }
108
109 private:
110 // Converts input color in a index for the histogram. It reduces
111 // each 8-bit component to the resolution given in the template
112 // parameters.
113 std::size_t histogramIndex(doc::color_t color) const {
114 return histogramIndex((rgba_getr(color) >> (8 - RBits)),
115 (rgba_getg(color) >> (8 - GBits)),
116 (rgba_getb(color) >> (8 - BBits)),
117 (rgba_geta(color) >> (8 - ABits)));
118 }
119
120 std::size_t histogramIndex(int r, int g, int b, int a) const {
121 return
122 r
123 | (g << RBits)
124 | (b << (RBits+GBits))
125 | (a << (RBits+GBits+BBits));
126 }
127
128 // 3D histogram (the index in the histogram is calculated through histogramIndex() function).
129 std::vector<std::size_t> m_histogram;
130
131 // High precision histogram to create an accurate palette if RGB
132 // source images contains less than 256 colors.
133 std::vector<doc::color_t> m_highPrecision;
134
135 // True if we can use m_highPrecision still (it means that the
136 // number of different samples is less than 256 colors still).
137 bool m_useHighPrecision;
138 };
139
140} // namespace render
141
142#endif
143