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