| 1 | use super::Pixel; |
| 2 | |
| 3 | struct RNG { |
| 4 | seed: u16, |
| 5 | } |
| 6 | |
| 7 | impl RNG { |
| 8 | fn new() -> Self { Self { seed: 0x1234 } } |
| 9 | fn next(&mut self) -> u8 { |
| 10 | if (self.seed & 0x8000) != 0 { |
| 11 | self.seed = ((self.seed & 0x7FFF) * 2) ^ 0x1B2B; |
| 12 | } else { |
| 13 | self.seed <<= 1; |
| 14 | } |
| 15 | self.seed as u8 |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | #[derive(Default,Clone,Copy,PartialEq,Debug)] |
| 20 | struct Entry { |
| 21 | pix: Pixel, |
| 22 | count: u64, |
| 23 | } |
| 24 | |
| 25 | struct Cluster { |
| 26 | centroid: Pixel, |
| 27 | dist: u64, |
| 28 | count: u64, |
| 29 | sum_r: u64, |
| 30 | sum_g: u64, |
| 31 | sum_b: u64, |
| 32 | } |
| 33 | |
| 34 | impl Cluster { |
| 35 | fn new(centroid: Pixel) -> Self { |
| 36 | Self { |
| 37 | centroid, |
| 38 | dist: 0, |
| 39 | count: 0, |
| 40 | sum_r: 0, |
| 41 | sum_g: 0, |
| 42 | sum_b: 0, |
| 43 | } |
| 44 | } |
| 45 | fn reset(&mut self) { |
| 46 | self.count = 0; |
| 47 | self.sum_r = 0; |
| 48 | self.sum_g = 0; |
| 49 | self.sum_b = 0; |
| 50 | self.dist = 0; |
| 51 | } |
| 52 | fn add_pixel(&mut self, entry: &Entry) { |
| 53 | self.sum_r += u64::from(entry.pix.r) * entry.count; |
| 54 | self.sum_g += u64::from(entry.pix.g) * entry.count; |
| 55 | self.sum_b += u64::from(entry.pix.b) * entry.count; |
| 56 | self.count += entry.count; |
| 57 | } |
| 58 | fn add_dist(&mut self, entry: &Entry) { |
| 59 | self.dist += u64::from(self.centroid.dist(entry.pix)) * entry.count; |
| 60 | } |
| 61 | fn calc_centroid(&mut self) { |
| 62 | if self.count != 0 { |
| 63 | self.centroid.r = ((self.sum_r + self.count / 2) / self.count) as u8; |
| 64 | self.centroid.g = ((self.sum_g + self.count / 2) / self.count) as u8; |
| 65 | self.centroid.b = ((self.sum_b + self.count / 2) / self.count) as u8; |
| 66 | } |
| 67 | } |
| 68 | fn calc_dist(&mut self) { |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | pub struct ELBG { |
| 73 | clusters: Vec<Cluster>, |
| 74 | } |
| 75 | |
| 76 | impl ELBG { |
| 77 | #[allow(dead_code)] |
| 78 | pub fn new(initial_pal: &[[u8; 3]; 256]) -> Self { |
| 79 | let mut clusters = Vec::with_capacity(256); |
| 80 | for i in 0..256 { |
| 81 | let pix = Pixel { r: initial_pal[i][0], g: initial_pal[i][1], b: initial_pal[i][2] }; |
| 82 | let cluster = Cluster::new(pix); |
| 83 | clusters.push(cluster); |
| 84 | } |
| 85 | Self { |
| 86 | clusters, |
| 87 | } |
| 88 | } |
| 89 | #[allow(dead_code)] |
| 90 | pub fn new_random() -> Self { |
| 91 | let mut rng = RNG::new(); |
| 92 | let mut clusters = Vec::with_capacity(256); |
| 93 | for _ in 0..256 { |
| 94 | let pix = Pixel { r: rng.next(), g: rng.next(), b: rng.next() }; |
| 95 | let cluster = Cluster::new(pix); |
| 96 | clusters.push(cluster); |
| 97 | } |
| 98 | Self { |
| 99 | clusters, |
| 100 | } |
| 101 | } |
| 102 | fn sort<F>(arr: &mut [Pixel], idx: F) where F: Fn(&Pixel) -> u8 { |
| 103 | let mut dst = vec![Pixel::default(); arr.len()]; |
| 104 | let mut counts = [0; 256]; |
| 105 | for pix in arr.iter() { |
| 106 | counts[idx(pix) as usize] += 1; |
| 107 | } |
| 108 | let mut last = counts[0]; |
| 109 | counts[0] = 0; |
| 110 | for count in counts.iter_mut().skip(1) { |
| 111 | let plast = last; |
| 112 | last += *count; |
| 113 | *count = plast; |
| 114 | } |
| 115 | for pix in arr.iter() { |
| 116 | let bucket = idx(pix) as usize; |
| 117 | dst[counts[bucket]] = *pix; |
| 118 | counts[bucket] += 1; |
| 119 | } |
| 120 | arr.copy_from_slice(dst.as_slice()); |
| 121 | } |
| 122 | fn new_split(old_index: usize, entries: &[Entry], indices: &[usize]) -> Option<(Pixel, Pixel)> { |
| 123 | let mut max = Pixel { r: 0, g: 0, b: 0 }; |
| 124 | let mut min = Pixel { r: 255, g: 255, b: 255 }; |
| 125 | let mut found = false; |
| 126 | for (entry, idx) in entries.iter().zip(indices) { |
| 127 | if *idx == old_index { |
| 128 | max = max.max(entry.pix); |
| 129 | min = min.min(entry.pix); |
| 130 | found = true; |
| 131 | } |
| 132 | } |
| 133 | if !found { |
| 134 | return None; |
| 135 | } |
| 136 | let dr = max.r - min.r; |
| 137 | let dg = max.g - min.g; |
| 138 | let db = max.b - min.b; |
| 139 | let cent0 = Pixel { r: min.r + dr / 3, g: min.g + dg / 3, b: min.b + db / 3 }; |
| 140 | let cent1 = Pixel { r: max.r - dr / 3, g: max.g - dg / 3, b: max.b - db / 3 }; |
| 141 | Some((cent0, cent1)) |
| 142 | } |
| 143 | fn old_centre(&self, old_index1: usize, old_index2: usize, entries: &[Entry], indices: &[usize]) -> Pixel { |
| 144 | let mut max = Pixel { r: 0, g: 0, b: 0 }; |
| 145 | let mut min = Pixel { r: 255, g: 255, b: 255 }; |
| 146 | let mut found = false; |
| 147 | for (entry, idx) in entries.iter().zip(indices) { |
| 148 | if *idx == old_index1 || *idx == old_index2 { |
| 149 | max = max.max(entry.pix); |
| 150 | min = min.min(entry.pix); |
| 151 | found = true; |
| 152 | } |
| 153 | } |
| 154 | if !found { |
| 155 | max = self.clusters[old_index1].centroid.max(self.clusters[old_index2].centroid); |
| 156 | min = self.clusters[old_index1].centroid.min(self.clusters[old_index2].centroid); |
| 157 | } |
| 158 | let dr = max.r - min.r; |
| 159 | let dg = max.g - min.g; |
| 160 | let db = max.b - min.b; |
| 161 | Pixel { r: min.r + dr / 2, g: min.g + dg / 2, b: min.b + db / 2 } |
| 162 | } |
| 163 | fn estimate_old(old_idx0: usize, old_idx1: usize, c: Pixel, entries: &[Entry], indices: &[usize]) -> u64 { |
| 164 | let mut clu = Cluster::new(c); |
| 165 | let mut count = 0; |
| 166 | for (entry, idx) in entries.iter().zip(indices) { |
| 167 | if *idx == old_idx0 || *idx == old_idx1 { |
| 168 | clu.add_dist(entry); |
| 169 | count += entry.count; |
| 170 | } |
| 171 | } |
| 172 | clu.count = count; |
| 173 | clu.calc_dist(); |
| 174 | clu.dist |
| 175 | } |
| 176 | fn estimate_new(c0: Pixel, c1: Pixel, old_idx: usize, entries: &[Entry], indices: &[usize]) -> u64 { |
| 177 | let mut clu0 = Cluster::new(c0); |
| 178 | let mut clu1 = Cluster::new(c1); |
| 179 | let mut count0 = 0; |
| 180 | let mut count1 = 0; |
| 181 | for (entry, idx) in entries.iter().zip(indices) { |
| 182 | if *idx == old_idx { |
| 183 | if c0.dist(entry.pix) < c1.dist(entry.pix) { |
| 184 | clu0.add_dist(entry); |
| 185 | count0 += entry.count; |
| 186 | } else { |
| 187 | clu1.add_dist(entry); |
| 188 | count1 += entry.count; |
| 189 | } |
| 190 | } |
| 191 | } |
| 192 | clu0.count = count0; |
| 193 | clu1.count = count1; |
| 194 | clu0.calc_dist(); |
| 195 | clu1.calc_dist(); |
| 196 | clu0.dist + clu1.dist |
| 197 | } |
| 198 | #[allow(clippy::cyclomatic_complexity)] |
| 199 | pub fn quantise(&mut self, src: &[Pixel], dst: &mut [[u8; 3]; 256]) { |
| 200 | if src.len() < 3 { |
| 201 | return; |
| 202 | } |
| 203 | let mut old_cb: [Pixel; 256] = [Pixel::default(); 256]; |
| 204 | let mut prev_dist = std::u64::MAX; |
| 205 | let mut dist = std::u64::MAX / 2; |
| 206 | let mut indices = Vec::with_capacity(src.len()); |
| 207 | let mut pixels = Vec::with_capacity(src.len()); |
| 208 | pixels.extend_from_slice(src); |
| 209 | Self::sort(pixels.as_mut_slice(), |pix| pix.r); |
| 210 | Self::sort(pixels.as_mut_slice(), |pix| pix.g); |
| 211 | Self::sort(pixels.as_mut_slice(), |pix| pix.b); |
| 212 | let mut entries = Vec::with_capacity(pixels.len() / 2); |
| 213 | let mut lastval = pixels[0]; |
| 214 | let mut run = 1; |
| 215 | for pix in pixels.iter().skip(1) { |
| 216 | if &lastval == pix { |
| 217 | run += 1; |
| 218 | } else { |
| 219 | entries.push(Entry { pix: lastval, count: run }); |
| 220 | lastval = *pix; |
| 221 | run = 1; |
| 222 | } |
| 223 | } |
| 224 | entries.push(Entry { pix: lastval, count: run }); |
| 225 | drop(pixels); |
| 226 | |
| 227 | let mut low_u: Vec<usize> = Vec::with_capacity(256); |
| 228 | let mut high_u: Vec<usize> = Vec::with_capacity(256); |
| 229 | let mut rng = RNG::new(); |
| 230 | let mut iterations = 0usize; |
| 231 | let mut do_elbg_step = true; |
| 232 | while (iterations < 10) && (dist < prev_dist - prev_dist / 100) { |
| 233 | prev_dist = dist; |
| 234 | for i in 0..256 { |
| 235 | old_cb[i] = self.clusters[i].centroid; |
| 236 | self.clusters[i].reset(); |
| 237 | } |
| 238 | // put pixels into the nearest clusters |
| 239 | indices.truncate(0); |
| 240 | for entry in entries.iter() { |
| 241 | let mut bestidx = 0; |
| 242 | let mut bestdist = std::u32::MAX; |
| 243 | for (i, cluster) in self.clusters.iter().enumerate() { |
| 244 | let dist = entry.pix.dist(cluster.centroid); |
| 245 | if bestdist > dist { |
| 246 | bestdist = dist; |
| 247 | bestidx = i; |
| 248 | if dist == 0 { |
| 249 | break; |
| 250 | } |
| 251 | } |
| 252 | } |
| 253 | indices.push(bestidx); |
| 254 | self.clusters[bestidx].add_pixel(entry); |
| 255 | } |
| 256 | // calculate params |
| 257 | for cluster in self.clusters.iter_mut() { |
| 258 | cluster.calc_centroid(); |
| 259 | } |
| 260 | dist = 0; |
| 261 | for (idx, entry) in indices.iter().zip(entries.iter()) { |
| 262 | self.clusters[*idx].add_dist(entry); |
| 263 | } |
| 264 | for cluster in self.clusters.iter_mut() { |
| 265 | cluster.calc_dist(); |
| 266 | dist += cluster.dist; |
| 267 | } |
| 268 | |
| 269 | let dmean = dist / 256; |
| 270 | low_u.truncate(0); |
| 271 | high_u.truncate(0); |
| 272 | let mut used = [false; 256]; |
| 273 | for (i, cluster) in self.clusters.iter().enumerate() { |
| 274 | if cluster.dist < dmean { |
| 275 | low_u.push(i); |
| 276 | } else if cluster.dist > dmean * 2 { |
| 277 | high_u.push(i); |
| 278 | used[i] = true; |
| 279 | } |
| 280 | } |
| 281 | |
| 282 | if do_elbg_step { |
| 283 | do_elbg_step = false; |
| 284 | for low_idx in low_u.iter() { |
| 285 | if high_u.is_empty() { |
| 286 | break; |
| 287 | } |
| 288 | let high_idx_idx = (rng.next() as usize) % high_u.len(); |
| 289 | let high_idx = high_u[high_idx_idx]; |
| 290 | let mut closest_idx = *low_idx; |
| 291 | let mut closest_dist = std::u32::MAX; |
| 292 | let low_centr = self.clusters[*low_idx].centroid; |
| 293 | for i in 0..256 {//low_u.iter() { |
| 294 | if i == *low_idx || used[i] { |
| 295 | continue; |
| 296 | } |
| 297 | let dist = self.clusters[i].centroid.dist(low_centr); |
| 298 | if closest_dist > dist { |
| 299 | closest_dist = dist; |
| 300 | closest_idx = i; |
| 301 | } |
| 302 | } |
| 303 | if closest_idx == *low_idx { |
| 304 | continue; |
| 305 | } |
| 306 | let old_dist = self.clusters[*low_idx].dist + self.clusters[closest_idx].dist + self.clusters[high_idx].dist; |
| 307 | let old_centr = self.old_centre(*low_idx, closest_idx, entries.as_slice(), indices.as_slice()); |
| 308 | let ret = Self::new_split(high_idx, entries.as_slice(), indices.as_slice()); |
| 309 | if ret.is_none() { |
| 310 | continue; |
| 311 | } |
| 312 | let (centr0, centr1) = ret.unwrap(); |
| 313 | let dist_o = if old_dist > self.clusters[high_idx].dist { |
| 314 | Self::estimate_old(*low_idx, closest_idx, old_centr, entries.as_slice(), indices.as_slice()) |
| 315 | } else { 0 }; |
| 316 | let dist_n = Self::estimate_new(centr0, centr1, high_idx, entries.as_slice(), indices.as_slice()); |
| 317 | if dist_o + dist_n < old_dist { |
| 318 | self.clusters[*low_idx ].centroid = old_centr; |
| 319 | self.clusters[closest_idx].centroid = centr0; |
| 320 | self.clusters[high_idx ].centroid = centr1; |
| 321 | used[*low_idx] = true; |
| 322 | used[closest_idx] = true; |
| 323 | used[high_idx] = true; |
| 324 | high_u.remove(high_idx_idx); |
| 325 | do_elbg_step = true; |
| 326 | } |
| 327 | } |
| 328 | } |
| 329 | iterations += 1; |
| 330 | } |
| 331 | if dist < prev_dist { |
| 332 | for i in 0..256 { |
| 333 | old_cb[i] = self.clusters[i].centroid; |
| 334 | } |
| 335 | } |
| 336 | for i in 0..256 { |
| 337 | dst[i][0] = old_cb[i].r; |
| 338 | dst[i][1] = old_cb[i].g; |
| 339 | dst[i][2] = old_cb[i].b; |
| 340 | } |
| 341 | } |
| 342 | } |