X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=inline;f=images%2Fdup-cmp.c;h=b71feaef9fa871fc4e4ff8675b593e956e9604ea;hb=150d10693b285ce5ff296571100b23b884f30560;hp=6b8155ae20bc1e4d99a10063cab4c7d2779a8ffe;hpb=cd8337db5e67bec5aaaceb84252b63b3a9e23eea;p=libucw.git

diff --git a/images/dup-cmp.c b/images/dup-cmp.c
index 6b8155ae..b71feaef 100644
--- a/images/dup-cmp.c
+++ b/images/dup-cmp.c
@@ -5,115 +5,18 @@
  *
  *      This software may be freely distributed and used according to the terms
  *      of the GNU Lesser General Public License.
- *
- *
- *      FIXME:
- *      - many possible optimization
- *      - compare normalized pictures (brightness, ...)
- *      - a blur should help to deal with scaling errors
- *      - maybe better/slower last step
- *      - different thresholds for various transformations
- *      - do not test all transformations for symetric pictures
- *      - allocated memory could be easily decreased to about 1/3
- *        for aspect ratio threshold near one
  */
 
-#define LOCAL_DEBUG
+#undef LOCAL_DEBUG
 
-#include "sherlock/sherlock.h"
+#include "lib/lib.h"
 #include "lib/mempool.h"
+#include "lib/fastbuf.h"
 #include "images/images.h"
-#include "images/dup-cmp.h"
+#include "images/duplicates.h"
 
-#include "lib/mempool.h"
-#include "lib/fastbuf.h"
 #include <fcntl.h>
 
-static uns image_dup_ratio_threshold = 140;
-static uns image_dup_error_threshold = 600;
-static uns image_dup_tab_limit = 8;
-
-static inline byte *
-image_dup_block(struct image_dup *dup, uns tab_col, uns tab_row)
-{
-  return dup->tab_pixels + (dup->tab_row_size << tab_row) + (3 << (tab_row + tab_col));
-}
-
-static inline struct image *
-image_dup_subimage(struct image_thread *thread, struct image_dup *dup, struct image *block, uns tab_col, uns tab_row)
-{
-  return image_init_matrix(thread, block, image_dup_block(dup, tab_col, tab_row),
-      1 << tab_col, 1 << tab_row, 3 << tab_col, COLOR_SPACE_RGB);
-}
-
-static inline void
-pixels_average(byte *dest, byte *src1, byte *src2)
-{
-  dest[0] = ((uns)src1[0] + (uns)src2[0]) >> 1;
-  dest[1] = ((uns)src1[1] + (uns)src2[1]) >> 1;
-  dest[2] = ((uns)src1[2] + (uns)src2[2]) >> 1;
-}
-
-int
-image_dup_init(struct image_thread *thread, struct image_dup *dup, struct image *img, struct mempool *pool)
-{
-  DBG("image_dup_init()");
-
-  ASSERT((img->flags & IMAGE_PIXEL_FORMAT) == COLOR_SPACE_RGB);
-
-  dup->image = img;
-  for (dup->tab_cols = 0; (uns)(2 << dup->tab_cols) < img->cols && dup->tab_cols < image_dup_tab_limit; dup->tab_cols++);
-  for (dup->tab_rows = 0; (uns)(2 << dup->tab_rows) < img->rows && dup->tab_rows < image_dup_tab_limit; dup->tab_rows++);
-  dup->tab_pixels = mp_alloc(pool, dup->tab_size = (12 << (dup->tab_cols + dup->tab_rows)));
-  dup->tab_row_size = 6 << dup->tab_cols;
-
-  /* Scale original image to right bottom block */
-  {
-    struct image block;
-    if (!image_dup_subimage(thread, dup, &block, dup->tab_cols, dup->tab_rows))
-      return 0;
-    if (!image_scale(thread, &block, img))
-      return 0;
-  }
-
-  /* Complete bottom row */
-  for (uns i = dup->tab_cols; i--; )
-    {
-      byte *d = image_dup_block(dup, i, dup->tab_rows);
-      byte *s = image_dup_block(dup, i + 1, dup->tab_rows);
-      for (uns y = 0; y < (uns)(1 << dup->tab_rows); y++)
-	for (uns x = 0; x < (uns)(1 << i); x++)
-	  {
-	    pixels_average(d, s, s + 3);
-	    d += 3;
-	    s += 6;
-	  }
-    }
-
-  /* Complete remaining blocks */
-  for (uns i = 0; i <= dup->tab_cols; i++)
-    {
-      uns line_size = (3 << i);
-      for (uns j = dup->tab_rows; j--; )
-        {
-          byte *d = image_dup_block(dup, i, j);
-          byte *s = image_dup_block(dup, i, j + 1);
-          for (uns y = 0; y < (uns)(1 << j); y++)
-            {
-              for (uns x = 0; x < (uns)(1 << i); x++)
-                {
- 	          pixels_average(d, s, s + line_size);
-		  d += 3;
-		  s += 3;
-		}
-	      s += line_size;
-	    }
-        }
-    }
-
-  return 1;
-}
-
 static inline uns
 err (int a, int b)
 {
@@ -162,18 +65,18 @@ err_sum_transformed(byte *pos1, byte *pos2, uns cols, uns rows, int row_step_1,
 }
 
 static inline int
-aspect_ratio_test(uns cols1, uns rows1, uns cols2, uns rows2)
+aspect_ratio_test(struct image_dup_context *ctx, uns cols1, uns rows1, uns cols2, uns rows2)
 {
   DBG("aspect_ratio_test(cols1=%u rows1=%u cols2=%u rows2=%u)", cols1, rows1, cols2, rows2);
   uns r1 = cols1 * rows2;
   uns r2 = rows1 * cols2;
   return
-    r1 <= ((r2 * image_dup_ratio_threshold) >> 7) &&
-    r2 <= ((r1 * image_dup_ratio_threshold) >> 7);
+    r1 <= ((r2 * ctx->ratio_threshold) >> 7) &&
+    r2 <= ((r1 * ctx->ratio_threshold) >> 7);
 }
 
 static inline int
-average_compare(struct image_dup *dup1, struct image_dup *dup2)
+average_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 {
   byte *block1 = image_dup_block(dup1, 0, 0);
   byte *block2 = image_dup_block(dup2, 0, 0);
@@ -181,13 +84,14 @@ average_compare(struct image_dup *dup1, struct image_dup *dup2)
     err(block1[0], block2[0]) +
     err(block1[1], block2[1]) +
     err(block1[2], block2[2]);
-  return e <= image_dup_error_threshold;
+  return e <= ctx->error_threshold;
 }
 
 static int
-blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns tab_row, uns trans)
+blocks_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns tab_row, uns trans)
 {
   DBG("blocks_compare(tab_col=%d tab_row=%d trans=%d)", tab_col, tab_row, trans);
+  ctx->sum_pixels += 1 << (tab_col + tab_row);
   byte *block1 = image_dup_block(dup1, tab_col, tab_row);
   byte *block2;
   int col_step, row_step;
@@ -200,7 +104,8 @@ blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns
       case 0: ;
 	uns err = (err_sum(block1, block2, 1 << (tab_col + tab_row)) >> (tab_col + tab_row));
 	DBG("average error=%d", err);
-	return err <= image_dup_error_threshold;
+	ctx->error = err;
+	return err <= ctx->error_threshold;
       case 1:
 	col_step = -3;
 	row_step = (3 << tab_col);
@@ -240,14 +145,18 @@ blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns
     }
   uns err = (err_sum_transformed(block1, block2, (1 << tab_col), (1 << tab_row), (3 << tab_col), col_step, row_step) >> (tab_col + tab_row));
   DBG("average error=%d", err);
-  return err <= image_dup_error_threshold;
+  ctx->error = err;
+  return err <= ctx->error_threshold;
 }
 
 static int
-same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
+same_size_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns trans)
 {
-  struct image *img1 = dup1->image;
-  struct image *img2 = dup2->image;
+  struct image *img1 = &dup1->image;
+  struct image *img2 = &dup2->image;
+  if (!img1->pixels || !img2->pixels)
+    return 1;
+  ctx->sum_pixels += img1->cols * img1->rows;
   byte *block1 = img1->pixels;
   byte *block2 = img2->pixels;
   int col_step, row_step;
@@ -297,23 +206,25 @@ same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
     }
   uns err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows));
   DBG("average error=%d", err);
-  return err <= image_dup_error_threshold;
+  ctx->error = err;
+  return err <= ctx->error_threshold;
 }
 
-int
-image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags)
+uns
+image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 {
-  DBG("image_dup_compare()");
-  if (!average_compare(dup1, dup2))
+  DBG("image_dup_compare(%p, %p)", dup1, dup2);
+  if (!average_compare(ctx, dup1, dup2))
     return 0;
-  struct image *img1 = dup1->image;
-  struct image *img2 = dup2->image;
+  struct image *img1 = &dup1->image;
+  struct image *img2 = &dup2->image;
+  uns flags = ctx->flags;
   if (flags & IMAGE_DUP_SCALE)
     {
       DBG("Scale support");
-      if (!aspect_ratio_test(img1->cols, img1->rows, img2->cols, img2->rows))
+      if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->cols, img2->rows))
 	flags &= ~0x0f;
-      if (!aspect_ratio_test(img1->cols, img1->rows, img2->rows, img2->cols))
+      if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->rows, img2->cols))
 	flags &= ~0xf0;
     }
   else
@@ -335,21 +246,26 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags)
 	if (flags & (1 << t))
 	  {
 	    DBG("Testing trans %d", t);
-            for (uns i = MAX(cols, rows); i--; )
+	    uns i = MAX(cols, rows), depth = 1;
+            while (i--)
               {
+		depth++;
 	        uns col = MAX(0, (int)(cols - i));
 	        uns row = MAX(0, (int)(rows - i));
-	        if (!blocks_compare(dup1, dup2, col, row, t))
+	        if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 		  break;
 		if (!i &&
 		    (img1->cols != img2->cols || img1->rows != img2->rows ||
-		    same_size_compare(dup1, dup2, t)))
+		    same_size_compare(ctx, dup1, dup2, t)))
 		  {
 		    result |= 1 << t;
 		    if (!(flags & IMAGE_DUP_WANT_ALL))
 		      return result;
+		    else
+		      break;
 		  }
 	      }
+	    ctx->sum_depth += depth;
 	  }
     }
   if (flags & 0xf0)
@@ -360,21 +276,26 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags)
 	if (flags & (1 << t))
 	  {
 	    DBG("Testing trans %d", t);
-            for (uns i = MAX(cols, rows); i--; )
+	    uns i = MAX(cols, rows), depth = 1;
+            while (i--)
               {
+		depth++;
 	        uns col = MAX(0, (int)(cols - i));
 	        uns row = MAX(0, (int)(rows - i));
-	        if (!blocks_compare(dup1, dup2, col, row, t))
+	        if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 		  break;
 		if (!i &&
 		    (img1->cols != img2->rows || img1->rows != img2->cols ||
-		    same_size_compare(dup1, dup2, t)) )
+		    same_size_compare(ctx, dup1, dup2, t)) )
 		  {
 		    result |= 1 << t;
 		    if (!(flags & IMAGE_DUP_WANT_ALL))
 		      return result;
+		    else
+		      break;
 		  }
 	      }
+	    ctx->sum_depth += depth;
 	  }
     }
   return result;