#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 "ucw/lib.h"
+#include "ucw/conf.h"
+#include "ucw/heap.h"
#include "images/images.h"
-#include "images/color.h"
#include "images/signature.h"
+#include "images/math.h"
-#include <alloca.h>
+#include <string.h>
#ifdef LOCAL_DEBUG
static void
for (uns 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;
byte buf[size];
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;
a += (u64)region->b[i] * region->b[i];
}
region->e -= a / region->count;
+ DBG("Finished region %u", (uns)region->e / region->count);
}
}
}
#define ASORT_PREFIX(x) prequant_##x
-#define ASORT_KEY_TYPE u32
+#define ASORT_KEY_TYPE uns
#define ASORT_ELT(i) val[i]
-#define ASORT_EXTRA_ARGS , u32 *val
-#include "lib/arraysort.h"
+#define ASORT_EXTRA_ARGS , uns *val
+#include "ucw/arraysort.h"
static uns
prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_region *regions)
{
DBG("Starting pre-quantization");
-
- uns regions_count, heap_count, axis, cov;
+
+ uns 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",
+ 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)
+ 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);
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];
+ u64 cov = (u64)region->count * region->c[0] - (u64)region->b[0] * region->b[0];
for (uns i = 1; i < 6; i++)
{
- uns j = region->count * region->c[i] - region->b[i];
+ uns 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, (uns)(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);
+ uns 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 (uns i = 0; i < 256; i++)
+ if (cnt[i])
+ {
+ val[cval] = i;
+ cnt[cval] = cnt[i];
+ cval++;
+ }
+ }
+ else
+ {
+ block = region->blocks;
+ for (uns i = 0; i < region->count; i++, block = block->next)
+ val[i] = block->v[axis];
+ prequant_sort(region->count, val);
+ cval = 1;
+ cnt[0] = 1;
+ for (uns 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)
+ uns b1 = val[0] * cnt[0];
+ uns c1 = isqr(val[0]) * cnt[0];
+ uns b2 = region->b[axis] - b1;
+ uns c2 = region->c[axis] - c1;
+ uns i = cnt[0], j = region->count - cnt[0];
+ u64 best_err = c1 - (u64)b1 * b1 / i + c2 - (u64)b2 * b2 / j;
+ uns split_val = val[0];
+ for (uns k = 1; k < cval - 1; k++)
{
- u64 err = (u64)i * c1 - (u64)b1 * b1 + (u64)j * c2 - (u64)b2 * b2;
+ uns b0 = val[k] * cnt[k];
+ uns 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);
postquant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_region *regions, uns 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;
for (uns step = 0; step < image_sig_postquant_max_steps; step++)
{
DBG("Step...");
-
+
/* Clear regions */
for (region = regions; region != regions_end; region++)
{
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