-static double image_sig_inertia_scale[3] = { 3, 1, 0.3 };
-
-struct block {
- u32 area; /* block area in pixels (usually 16) */
- u32 v[IMAGE_VEC_F];
- u32 x, y; /* block position */
- struct block *next;
-};
-
-struct region {
- struct block *blocks;
- u32 count;
- u32 a[IMAGE_VEC_F];
- u32 b[IMAGE_VEC_F];
- u32 c[IMAGE_VEC_F];
- u64 e;
- u64 w_sum;
-};
-
-static inline uns
-dist(uns a, uns b)
-{
- int d = a - b;
- return d * d;
-}
-
-#ifdef LOCAL_DEBUG
-static void
-dump_segmentation(struct region *regions, uns regions_count, uns cols, uns rows)
-{
- uns size = (cols + 1) * rows;
- byte buf[size];
- bzero(buf, size);
- for (uns i = 0; i < regions_count; i++)
- {
- byte c = (i < 10) ? '0' + i : 'A' - 10 + i;
- for (struct block *b = regions[i].blocks; b; b = b->next)
- buf[b->x + b->y * (cols + 1)] = c;
- }
- for (uns i = 0; i < rows; i++)
- log(L_DEBUG, "%s", &buf[i * (cols + 1)]);
-}
-#endif
-
-/* Pre-quantization - recursively split groups of blocks with large error */
-
-static inline void
-prequant_init_region(struct region *region)
-{
- bzero(region, sizeof(*region));
-}
-
-static inline void
-prequant_add_block(struct region *region, struct block *block)
-{
- block->next = region->blocks;
- region->blocks = block;
- region->count++;
- for (uns i = 0; i < IMAGE_VEC_F; i++)
- {
- region->b[i] += block->v[i];
- region->c[i] += isqr(block->v[i]);
- }
-}
-
-static void
-prequant_finish_region(struct region *region)
-{
- if (region->count < 2)
- memcpy(region->c, region->a, sizeof(region->c));
- else
- {
- u64 a = 0;
- region->e = 0;
- for (uns i = 0; i < IMAGE_VEC_F; i++)
- {
- region->e += region->c[i];
- a += (u64)region->b[i] * region->b[i];
- }
- region->e -= a / region->count;
- }
-}
-
-static inline uns
-prequant_heap_cmp(struct region *a, struct region *b)
-{
- return a->e > b->e;
-}
-
-#define ASORT_PREFIX(x) prequant_##x
-#define ASORT_KEY_TYPE u32
-#define ASORT_ELT(i) val[i]
-#define ASORT_EXTRA_ARGS , u32 *val
-#include "lib/arraysort.h"
-
-static uns
-prequant(struct block *blocks, uns blocks_count, struct region *regions)
-{
- DBG("Starting pre-quantization");
-
- uns regions_count, heap_count, axis, cov;
- struct block *blocks_end = blocks + blocks_count, *block, *block2;
- struct region *heap[IMAGE_REG_MAX + 1], *region, *region2;
-
- /* Initialize single region with all blocks */
- regions_count = heap_count = 1;
- heap[1] = regions;
- prequant_init_region(regions);
- for (block = blocks; block != blocks_end; block++)
- prequant_add_block(regions, block);
- prequant_finish_region(regions);
-
- /* Main cycle */
- while (regions_count < IMAGE_REG_MAX &&
- regions_count <= DARY_LEN(image_sig_prequant_thresholds) && heap_count)
- {
- region = heap[1];
- DBG("Step... regions_count=%u heap_count=%u region->count=%u, region->e=%u",
- regions_count, heap_count, region->count, (uns)region->e);
- if (region->count < 2 ||
- region->e < image_sig_prequant_thresholds[regions_count - 1] * region->count)
- {
- HEAP_DELMIN(struct region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP);
- continue;
- }
-
- /* Select axis to split - the one with maximum covariance */
- axis = 0;
- cov = region->count * region->c[0] - region->b[0];
- for (uns i = 1; i < 6; i++)
- {
- uns j = region->count * region->c[i] - region->b[i];
- if (j > cov)
- {
- axis = i;
- cov = j;
- }
- }
- DBG("Splitting axis %u with covariance %u", axis, cov / region->count);
-
- /* Sort values on the split axis */
- u32 val[region->count];
- block = region->blocks;
- for (uns i = 0; i < region->count; i++, block = block->next)
- val[i] = block->v[axis];
- prequant_sort(region->count, val);
-
- /* Select split value - to minimize error */
- uns b1 = 0, c1 = 0, b2 = region->b[axis], c2 = region->c[axis];
- uns i = 0, j = region->count, best_v = 0;
- u64 best_err = 0xffffffffffffffff;
- while (i < region->count)
- {
- u64 err = (u64)i * c1 - (u64)b1 * b1 + (u64)j * c2 - (u64)b2 * b2;
- if (err < best_err)
- {
- best_err = err;
- best_v = val[i];
- }
- uns sqr = isqr(val[i]);
- b1 += val[i];
- b2 -= val[i];
- c1 += sqr;
- c2 -= sqr;
- i++;
- j--;
- }
- uns split_val = best_v;
- DBG("split_val=%u best_err=%Lu b[axis]=%u c[axis]=%u", split_val, (long long)best_err, region->b[axis], region->c[axis]);
-
- /* Split region */
- block = region->blocks;
- region2 = regions + regions_count++;
- prequant_init_region(region);
- prequant_init_region(region2);
- while (block)
- {
- block2 = block->next;
- if (block->v[axis] < split_val)
- prequant_add_block(region, block);
- else
- prequant_add_block(region2, block);
- block = block2;
- }
- prequant_finish_region(region);
- prequant_finish_region(region2);
- HEAP_INCREASE(struct region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP, 1);
- heap[++heap_count] = region2;
- HEAP_INSERT(struct region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP);
- }
-
- DBG("Pre-quantized to %u regions", regions_count);
-
- return regions_count;
-}
-
-/* Post-quantization - run a few K-mean iterations to improve pre-quantized regions */
-
-static uns
-postquant(struct block *blocks, uns blocks_count, struct region *regions, uns regions_count)