1 use super::{VQElement, VQElementSum};
3 // very simple RNG for internal needs
9 fn new() -> Self { Self { seed: 0x1234 } }
10 fn next(&mut self) -> u8 {
11 if (self.seed & 0x8000) != 0 {
12 self.seed = (self.seed & 0x7FFF) * 2 ^ 0x1B2B;
25 struct Cluster<T: VQElement, TS: VQElementSum<T>> {
32 impl<T: VQElement, TS: VQElementSum<T>> Cluster<T, TS> {
33 fn new(centroid: T) -> Self {
43 self.sum = TS::zero();
46 fn add_point(&mut self, entry: &Entry<T>) {
47 self.sum.add(entry.val, entry.count);
48 self.count += entry.count;
50 fn add_dist(&mut self, entry: &Entry<T>) {
51 self.dist += u64::from(self.centroid.dist(entry.val)) * entry.count;
53 fn calc_centroid(&mut self) {
54 self.centroid = self.sum.get_centroid();
56 fn calc_dist(&mut self) {
58 self.dist = (self.dist + self.count / 2) / self.count;
63 pub struct ELBG<T: VQElement, TS: VQElementSum<T>> {
64 clusters: Vec<Cluster<T, TS>>,
67 impl<T: VQElement+Default, TS: VQElementSum<T>> ELBG<T, TS> {
68 pub fn new(initial_cb: &[T]) -> Self {
69 let mut clusters = Vec::with_capacity(initial_cb.len());
70 for elem in initial_cb.iter() {
71 let cluster = Cluster::new(*elem);
72 clusters.push(cluster);
78 fn new_split(old_index: usize, entries: &[Entry<T>], indices: &[usize]) -> Option<(T, T)> {
79 let mut max = T::min_cw();
80 let mut min = T::max_cw();
81 let mut found = false;
82 for (entry, idx) in entries.iter().zip(indices) {
83 if *idx == old_index {
84 max = max.max(entry.val);
85 min = min.min(entry.val);
92 let mut ts0 = TS::zero();
93 let mut ts1 = TS::zero();
94 ts0.add(min, 2); ts0.add(max, 1);
95 ts1.add(min, 1); ts1.add(max, 2);
96 Some((ts0.get_centroid(), ts1.get_centroid()))
98 fn old_centre(&self, old_index1: usize, old_index2: usize, entries: &[Entry<T>], indices: &[usize]) -> T {
99 let mut max = T::min_cw();
100 let mut min = T::max_cw();
101 let mut found = false;
102 for (entry, idx) in entries.iter().zip(indices) {
103 if *idx == old_index1 || *idx == old_index2 {
104 max = max.max(entry.val);
105 min = min.min(entry.val);
110 max = self.clusters[old_index1].centroid.max(self.clusters[old_index2].centroid);
111 min = self.clusters[old_index1].centroid.min(self.clusters[old_index2].centroid);
113 let mut ts = TS::zero();
114 ts.add(min, 2); ts.add(max, 1);
117 fn estimate_old(old_idx0: usize, old_idx1: usize, c: T, entries: &[Entry<T>], indices: &[usize]) -> u64 {
118 let mut clu: Cluster<T, TS> = Cluster::new(c);
120 for (entry, idx) in entries.iter().zip(indices) {
121 if *idx == old_idx0 || *idx == old_idx1 {
123 count += entry.count;
130 fn estimate_new(c0: T, c1: T, old_idx: usize, entries: &[Entry<T>], indices: &[usize]) -> u64 {
131 let mut clu0: Cluster<T, TS> = Cluster::new(c0);
132 let mut clu1: Cluster<T, TS> = Cluster::new(c1);
135 for (entry, idx) in entries.iter().zip(indices) {
137 if c0.dist(entry.val) < c1.dist(entry.val) {
138 clu0.add_dist(entry);
139 count0 += entry.count;
141 clu1.add_dist(entry);
142 count1 += entry.count;
150 clu0.dist + clu1.dist
152 pub fn quantise(&mut self, src: &[T], dst: &mut [T]) {
153 if src.len() < 1 || dst.len() != self.clusters.len() {
156 let mut old_cb = vec![T::default(); self.clusters.len()];
157 let mut prev_dist = std::u64::MAX;
158 let mut dist = std::u64::MAX / 2;
159 let mut indices = Vec::with_capacity(src.len());
160 let mut elements = Vec::with_capacity(src.len());
161 elements.extend_from_slice(src);
162 for comp in 0..T::num_components() {
163 T::sort_by_component(elements.as_mut_slice(), comp);
165 let mut entries = Vec::with_capacity(elements.len() / 2);
166 let mut lastval = elements[0];
168 for point in elements.iter().skip(1) {
169 if &lastval == point {
172 entries.push(Entry { val: lastval, count: run });
177 entries.push(Entry { val: lastval, count: run });
180 let mut low_u: Vec<usize> = Vec::with_capacity(self.clusters.len());
181 let mut high_u: Vec<usize> = Vec::with_capacity(self.clusters.len());
182 let mut rng = RNG::new();
183 let mut iterations = 0usize;
184 let mut do_elbg_step = true;
185 while (iterations < 20) && (dist < prev_dist - prev_dist / 1000) {
187 for i in 0..dst.len() {
188 old_cb[i] = self.clusters[i].centroid;
189 self.clusters[i].reset();
191 // put points into the nearest clusters
193 for entry in entries.iter() {
195 let mut bestdist = std::u32::MAX;
196 for (i, cluster) in self.clusters.iter().enumerate() {
197 let dist = entry.val.dist(cluster.centroid);
206 indices.push(bestidx);
207 self.clusters[bestidx].add_point(entry);
210 for cluster in self.clusters.iter_mut() {
211 cluster.calc_centroid();
214 for (idx, entry) in indices.iter().zip(entries.iter()) {
215 self.clusters[*idx].add_dist(entry);
217 for cluster in self.clusters.iter_mut() {
219 dist += cluster.dist;
222 let dmean = dist / (dst.len() as u64);
225 let mut used = vec![false; dst.len()];
226 for (i, cluster) in self.clusters.iter().enumerate() {
227 if cluster.dist < dmean {
229 } else if cluster.dist > dmean * 2 {
236 do_elbg_step = false;
237 for low_idx in low_u.iter() {
238 if high_u.len() == 0 {
241 let high_idx_idx = (rng.next() as usize) % high_u.len();
242 let high_idx = high_u[high_idx_idx];
243 let mut closest_idx = *low_idx;
244 let mut closest_dist = std::u32::MAX;
245 let low_centr = self.clusters[*low_idx].centroid;
246 for i in 0..dst.len() {//low_u.iter() {
247 if i == *low_idx || used[i] {
250 let dist = self.clusters[i].centroid.dist(low_centr);
251 if closest_dist > dist {
256 if closest_idx == *low_idx {
259 let old_dist = self.clusters[*low_idx].dist + self.clusters[closest_idx].dist + self.clusters[high_idx].dist;
260 let old_centr = self.old_centre(*low_idx, closest_idx, entries.as_slice(), indices.as_slice());
261 let ret = Self::new_split(high_idx, entries.as_slice(), indices.as_slice());
262 if let Some((centr0, centr1)) = ret {
263 let dist_o = if old_dist > self.clusters[high_idx].dist {
264 Self::estimate_old(*low_idx, closest_idx, old_centr, entries.as_slice(), indices.as_slice())
266 let dist_n = Self::estimate_new(centr0, centr1, high_idx, entries.as_slice(), indices.as_slice());
267 if dist_o + dist_n < old_dist {
268 self.clusters[*low_idx ].centroid = old_centr;
269 self.clusters[closest_idx].centroid = centr0;
270 self.clusters[high_idx ].centroid = centr1;
271 used[*low_idx] = true;
272 used[closest_idx] = true;
273 used[high_idx] = true;
274 high_u.remove(high_idx_idx);
282 if dist < prev_dist {
283 for i in 0..dst.len() {
284 old_cb[i] = self.clusters[i].centroid;
287 dst.copy_from_slice(&old_cb);