X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=images%2Fsig-seg.c;h=cdcb71c8417ba147af293d0a1eb334fc644f66e1;hb=d46d9596c225dbbcaef4b76e0828036e3addfbe3;hp=948305735ce39e68df08b70a3a1f75891ae073b0;hpb=4bc6b76423665d7bfdf27a372b031a0161876a5f;p=libucw.git

diff --git a/images/sig-seg.c b/images/sig-seg.c
index 94830573..cdcb71c8 100644
--- a/images/sig-seg.c
+++ b/images/sig-seg.c
@@ -26,8 +26,8 @@ dump_segmentation(struct image_sig_region *regions, uns regions_count)
   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];
@@ -68,7 +68,9 @@ static void
 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;
@@ -79,6 +81,7 @@ prequant_finish_region(struct image_sig_region *region)
 	  a += (u64)region->b[i] * region->b[i];
 	}
       region->e -= a / region->count;
+      DBG("Finished region %u", (uns)region->e / region->count);
     }
 }
 
@@ -89,9 +92,9 @@ prequant_heap_cmp(struct image_sig_region *a, struct image_sig_region *b)
 }
 
 #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
+#define ASORT_EXTRA_ARGS , uns *val
 #include "lib/arraysort.h"
 
 static uns
@@ -99,7 +102,7 @@ prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_regi
 {
   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;
 
@@ -119,54 +122,86 @@ prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_regi
       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]);
 
       /* Split region */
@@ -177,7 +212,7 @@ prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_regi
       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);
@@ -291,7 +326,7 @@ postquant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_reg
 	  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;
 	}
     }