1// tQuantize.cpp 
2// 
3// This module implements exact palettization of an image for cases when full quantization of an image is not necessary. 
4// That is, when there will be no colour losses. Exact palettization is possible if the number of unique pixel colours 
5// is less-than or equal to the number of colours available to the palette. Additionally a function to convert from 
6// palette/index format back to straght pixels is provided. 
7// 
8// Copyright (c) 2022-2024 Tristan Grimmer. 
9// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
10// granted, provided that the above copyright notice and this permission notice appear in all copies. 
11// 
12// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
13// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
14// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
15// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
16// PERFORMANCE OF THIS SOFTWARE. 
17 
18#include <Math/tColour.h> 
19#include <Foundation/tMap.h> 
20#include "Image/tQuantize.h" 
21namespace tImage { 
22 
23 
24namespace tQuantize 
25{ 
26 int FindIndexOfExactColour(const tColour3b* searchSpace, int searchSize, const tColour3b& colour); 
27} 
28 
29 
30const char* tQuantize::GetMethodName(Method method) 
31{ 
32 switch (method) 
33 { 
34 case tQuantize::Method::Fixed: return "Fixed"; 
35 case tQuantize::Method::Spatial: return "Scolorq"; 
36 case tQuantize::Method::Neu: return "Neuquant"; 
37 case tQuantize::Method::Wu: return "Wu"; 
38 } 
39 return "Invalid"; 
40} 
41 
42 
43int tQuantize::FindIndexOfExactColour(const tColour3b* searchSpace, int searchSize, const tColour3b& colour) 
44{ 
45 for (int i = 0; i < searchSize; i++) 
46 if (colour == searchSpace[i]) 
47 return i; 
48 
49 return -1; 
50} 
51 
52 
53// 
54// The functions below make up the external interface. 
55// 
56 
57 
58bool tQuantize::QuantizeImageExact 
59( 
60 int numColours, int width, int height, const tPixel3b* pixels, 
61 tColour3b* destPalette, uint8* destIndices 
62) 
63{ 
64 if ((numColours < 2) || (numColours > 256) || (width <= 0) || (height <= 0) || !pixels || !destPalette || !destIndices) 
65 return false; 
66 
67 // First we need to find how many unique colours are in the pixels. 
68 // We do this using a tMap which forces uniqueness on the key. We'll use the int value to count occurrences. 
69 tMap<tPixel3b, int> pixelCountMap; 
70 for (int xy = 0; xy < width*height; xy++) 
71 pixelCountMap[ pixels[xy] ]++; 
72 
73 // Test print counts of each unique colour. 
74 #if 0 
75 for (auto pair : pixelCountMap) 
76 { 
77 tPixel3& c = pair.Key(); 
78 tPrintf("Key RGB %03d %03d %03d. Value COUNT: %05d]\n", c.R, c.G, c.B, pair.Value()); 
79 } 
80 #endif 
81 
82 int numUnique = pixelCountMap.GetNumItems(); 
83 if (numUnique > numColours) 
84 return false; 
85 
86 // Populate the palette. 
87 tStd::tMemset(dest: destPalette, val: 0, numBytes: numColours*sizeof(tColour3b)); 
88 int entry = 0; 
89 for (auto pair : pixelCountMap) 
90 destPalette[entry++] = pair.Key(); 
91  
92 // Now populate the indices by finding each pixel's colour in the palette. 
93 for (int p = 0; p < width*height; p++) 
94 { 
95 int idx = FindIndexOfExactColour(searchSpace: destPalette, searchSize: numUnique, colour: pixels[p]); 
96 tAssert(idx != -1); 
97 destIndices[p] = idx; 
98 } 
99 
100 return true; 
101} 
102 
103 
104bool tQuantize::ConvertToPixels 
105( 
106 tPixel3b* destPixels, int width, int height, 
107 const tColour3b* srcPalette, const uint8* srcIndices 
108) 
109{ 
110 if (!destPixels || (width <= 0) || (height <= 0) || !srcPalette || !srcIndices) 
111 return false; 
112 
113 for (int y = 0; y < height; y++) 
114 { 
115 for (int x = 0; x < width; x++) 
116 { 
117 int index = x + y*width; 
118 int palIndex = srcIndices[index]; 
119 tColour3b colour = srcPalette[palIndex]; 
120 destPixels[index] = colour; 
121 } 
122 } 
123 
124 return true; 
125} 
126 
127 
128bool tQuantize::ConvertToPixels 
129( 
130 tPixel4b* destPixels, int width, int height, 
131 const tColour3b* srcPalette, const uint8* srcIndices, bool preserveDestAlpha 
132) 
133{ 
134 if (!destPixels || (width <= 0) || (height <= 0) || !srcPalette || !srcIndices) 
135 return false; 
136 
137 for (int y = 0; y < height; y++) 
138 { 
139 for (int x = 0; x < width; x++) 
140 { 
141 int index = x + y*width; 
142 int palIndex = srcIndices[index]; 
143 tColour3b colour = srcPalette[palIndex]; 
144 if (preserveDestAlpha) 
145 destPixels[index].SetRGB(r: colour.R, g: colour.G, b: colour.B); 
146 else 
147 destPixels[index].Set(r: colour.R, g: colour.G, b: colour.B); 
148 } 
149 } 
150 
151 return true; 
152} 
153 
154 
155} 
156