#undef LOCAL_DEBUG
-#include "sherlock/sherlock.h"
-#include "lib/math.h"
-#include "lib/fastbuf.h"
-#include "lib/conf.h"
-#include "lib/heap.h"
-#include "images/math.h"
-#include "images/images.h"
-#include "images/color.h"
-#include "images/signature.h"
-
-#include <alloca.h>
+#include <ucw/lib.h>
+#include <ucw/conf.h>
+#include <ucw/heap.h>
+#include <images/images.h>
+#include <images/signature.h>
+#include <images/math.h>
+
+#include <string.h>
#ifdef LOCAL_DEBUG
static void
-dump_segmentation(struct image_sig_region *regions, uns regions_count)
+dump_segmentation(struct image_sig_region *regions, uint regions_count)
{
- uns cols = 0, rows = 0;
- for (uns i = 0; i < regions_count; i++)
+ uint cols = 0, rows = 0;
+ for (uint i = 0; i < regions_count; i++)
for (struct image_sig_block *b = regions[i].blocks; b; b = b->next)
{
- cols = MAX(cols, b->x);
- rows = MAX(rows, b->y);
+ cols = MAX(cols, b->x + 1);
+ rows = MAX(rows, b->y + 1);
}
- uns size = (cols + 1) * rows;
+ uint size = (cols + 1) * rows;
byte buf[size];
bzero(buf, size);
- for (uns i = 0; i < regions_count; i++)
+ for (uint i = 0; i < regions_count; i++)
{
byte c = (i < 10) ? '0' + i : 'A' - 10 + i;
for (struct image_sig_block *b = regions[i].blocks; b; b = b->next)
buf[b->x + b->y * (cols + 1)] = c;
}
- for (uns i = 0; i < rows; i++)
+ for (uint i = 0; i < rows; i++)
log(L_DEBUG, "%s", &buf[i * (cols + 1)]);
}
#endif
block->next = region->blocks;
region->blocks = block;
region->count++;
- for (uns i = 0; i < IMAGE_VEC_F; i++)
+ for (uint i = 0; i < IMAGE_VEC_F; i++)
{
region->b[i] += block->v[i];
region->c[i] += isqr(block->v[i]);
prequant_finish_region(struct image_sig_region *region)
{
if (region->count < 2)
- memcpy(region->c, region->a, sizeof(region->c));
+ {
+ region->e = 0;
+ }
else
{
u64 a = 0;
region->e = 0;
- for (uns i = 0; i < IMAGE_VEC_F; i++)
+ for (uint 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;
+ DBG("Finished region %u", (uint)region->e / region->count);
}
}
-static inline uns
+static inline uint
prequant_heap_cmp(struct image_sig_region *a, struct image_sig_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"
+#define ASORT_KEY_TYPE uint
+#include <ucw/sorter/array-simple.h>
-static uns
-prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_region *regions)
+static uint
+prequant(struct image_sig_block *blocks, uint blocks_count, struct image_sig_region *regions)
{
DBG("Starting pre-quantization");
-
- uns regions_count, heap_count, axis, cov;
+
+ uint regions_count, heap_count, axis;
struct image_sig_block *blocks_end = blocks + blocks_count, *block, *block2;
struct image_sig_region *heap[IMAGE_REG_MAX + 1], *region, *region2;
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);
+ DBG("Step... regions_count=%u heap_count=%u region->count=%u, region->e=%u",
+ regions_count, heap_count, region->count, (uint)region->e);
if (region->count < 2 ||
- region->e < image_sig_prequant_thresholds[regions_count - 1] * region->count)
+ region->e < image_sig_prequant_thresholds[regions_count - 1] * blocks_count)
{
- HEAP_DELMIN(struct image_sig_region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP);
+ HEAP_DELETE_MIN(struct image_sig_region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP);
continue;
}
- /* Select axis to split - the one with maximum covariance */
+ /* Select axis to split - the one with maximum average quadratic error */
axis = 0;
- cov = region->count * region->c[0] - region->b[0];
- for (uns i = 1; i < 6; i++)
+ u64 cov = (u64)region->count * region->c[0] - (u64)region->b[0] * region->b[0];
+ for (uint i = 1; i < 6; i++)
{
- uns j = region->count * region->c[i] - region->b[i];
+ uint j = (u64)region->count * region->c[i] - (u64)region->b[i] * region->b[i];
if (j > cov)
{
axis = i;
cov = j;
}
}
- DBG("Splitting axis %u with covariance %u", axis, cov / region->count);
+ DBG("Splitting axis %u with average quadratic error %u", axis, (uint)(cov / (region->count * 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);
+ uint val[256], cnt[256], cval;
+ if (region->count > 64)
+ {
+ bzero(cnt, sizeof(cnt));
+ for (block = region->blocks; block; block = block->next)
+ cnt[block->v[axis]]++;
+ cval = 0;
+ for (uint i = 0; i < 256; i++)
+ if (cnt[i])
+ {
+ val[cval] = i;
+ cnt[cval] = cnt[i];
+ cval++;
+ }
+ }
+ else
+ {
+ block = region->blocks;
+ for (uint i = 0; i < region->count; i++, block = block->next)
+ val[i] = block->v[axis];
+ prequant_sort(val, region->count);
+ cval = 1;
+ cnt[0] = 1;
+ for (uint i = 1; i < region->count; i++)
+ if (val[i] == val[cval - 1])
+ cnt[cval - 1]++;
+ else
+ {
+ val[cval] = val[i];
+ cnt[cval] = 1;
+ cval++;
+ }
+ }
/* 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)
+ uint b1 = val[0] * cnt[0];
+ uint c1 = isqr(val[0]) * cnt[0];
+ uint b2 = region->b[axis] - b1;
+ uint c2 = region->c[axis] - c1;
+ uint i = cnt[0], j = region->count - cnt[0];
+ u64 best_err = c1 - (u64)b1 * b1 / i + c2 - (u64)b2 * b2 / j;
+ uint split_val = val[0];
+ for (uint k = 1; k < cval - 1; k++)
{
- u64 err = (u64)i * c1 - (u64)b1 * b1 + (u64)j * c2 - (u64)b2 * b2;
+ uint b0 = val[k] * cnt[k];
+ uint c0 = isqr(val[k]) * cnt[k];
+ b1 += b0;
+ b2 -= b0;
+ c1 += c0;
+ c2 -= c0;
+ i += cnt[k];
+ j -= cnt[k];
+ u64 err = (u64)c1 - (u64)b1 * b1 / i + (u64)c2 - (u64)b2 * b2 / j;
if (err < best_err)
{
best_err = err;
- best_v = val[i];
+ split_val = val[k];
}
- 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]);
+ DBG("split_val=%u best_err=%llu b[axis]=%u c[axis]=%u", split_val, (long long)best_err, region->b[axis], region->c[axis]);
/* Split region */
block = region->blocks;
while (block)
{
block2 = block->next;
- if (block->v[axis] < split_val)
+ if (block->v[axis] <= split_val)
prequant_add_block(region, block);
else
prequant_add_block(region2, block);
}
prequant_finish_region(region);
prequant_finish_region(region2);
- HEAP_INCREASE(struct image_sig_region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP, 1);
- heap[++heap_count] = region2;
- HEAP_INSERT(struct image_sig_region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP);
+ HEAP_INCREASE(struct image_sig_region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP, 1, region);
+ HEAP_INSERT(struct image_sig_region *, heap, heap_count, prequant_heap_cmp, HEAP_SWAP, region2);
}
DBG("Pre-quantized to %u regions", regions_count);
/* Post-quantization - run a few K-mean iterations to improve pre-quantized regions */
-static uns
-postquant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_region *regions, uns regions_count)
+static uint
+postquant(struct image_sig_block *blocks, uint blocks_count, struct image_sig_region *regions, uint regions_count)
{
DBG("Starting post-quantization");
-
+
struct image_sig_block *blocks_end = blocks + blocks_count, *block;
struct image_sig_region *regions_end = regions + regions_count, *region;
- uns error = 0, last_error;
+ uint error = 0, last_error;
/* Initialize regions and initial segmentation error */
for (region = regions; region != regions_end; )
{
- uns inv = 0xffffffffU / region->count;
- for (uns i = 0; i < IMAGE_VEC_F; i++)
+ uint inv = 0xffffffffU / region->count;
+ for (uint i = 0; i < IMAGE_VEC_F; i++)
{
region->a[i] = ((u64)region->b[i] * inv) >> 32;
error += region->c[i] - region->a[i] * region->b[i];
}
/* Convergation cycle */
- for (uns step = 0; step < image_sig_postquant_max_steps; step++)
+ for (uint step = 0; step < image_sig_postquant_max_steps; step++)
{
DBG("Step...");
-
+
/* Clear regions */
for (region = regions; region != regions_end; region++)
{
for (block = blocks; block != blocks_end; block++)
{
struct image_sig_region *best_region = NULL;
- uns best_dist = ~0U;
+ uint best_dist = ~0U;
for (region = regions; region != regions_end; region++)
{
- uns dist =
+ uint dist =
isqr(block->v[0] - region->a[0]) +
isqr(block->v[1] - region->a[1]) +
isqr(block->v[2] - region->a[2]) +
region->count++;
block->next = region->blocks;
region->blocks = block;
- for (uns i = 0; i < IMAGE_VEC_F; i++)
+ for (uint i = 0; i < IMAGE_VEC_F; i++)
{
region->b[i] += block->v[i];
region->c[i] += isqr(block->v[i]);
for (region = regions; region != regions_end; )
if (region->count)
{
- uns inv = 0xffffffffU / region->count;
- for (uns i = 0; i < IMAGE_VEC_F; i++)
+ uint inv = 0xffffffffU / region->count;
+ for (uint i = 0; i < IMAGE_VEC_F; i++)
{
region->a[i] = ((u64)region->b[i] * inv) >> 32;
error += region->c[i] - region->a[i] * region->b[i];
if (error > last_error)
break;
u64 dif = last_error - error;
- if (dif * image_sig_postquant_threshold < last_error * 100)
+ if (dif * image_sig_postquant_threshold < (u64)last_error * 100)
break;
}
}
DBG("Post-quantized to %u regions with average square error %u", regions_end - regions, error / blocks_count);
-
+
return regions_end - regions;
}
-uns
-image_sig_segmentation(struct image_sig_block *blocks, uns blocks_count, struct image_sig_region *regions)
+void
+image_sig_segmentation(struct image_sig_data *data)
{
- uns regions_count;
- regions_count = prequant(blocks, blocks_count, regions);
-#ifdef LOCAL_DEBUG
- dump_segmentation(regions, regions_count);
-#endif
- regions_count = postquant(blocks, blocks_count, regions, regions_count);
-#ifdef LOCAL_DEBUG
- dump_segmentation(regions, regions_count);
-#endif
- return regions_count;
+ data->regions_count = prequant(data->blocks, data->blocks_count, data->regions);
+#ifdef LOCAL_DEBUG
+ dump_segmentation(data->regions, data->regions_count);
+#endif
+ data->regions_count = postquant(data->blocks, data->blocks_count, data->regions, data->regions_count);
+#ifdef LOCAL_DEBUG
+ dump_segmentation(data->regions, data->regions_count);
+#endif
}
projects / libucw.git / blobdiff