From d558e5450310239fee2667bc3d528bb87ccf1d63 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Mon, 28 Aug 2006 11:29:46 +0200 Subject: [PATCH] - experimenting with different signatures comparision algorithm --- cf/images | 2 + images/config.c | 2 + images/sig-cmp.c | 113 +++++++++++++++++++++++++++++++++++++++++++-- images/signature.h | 3 +- 4 files changed, 116 insertions(+), 4 deletions(-) diff --git a/cf/images b/cf/images index 9d767e6f..09d148d1 100644 --- a/cf/images +++ b/cf/images @@ -19,6 +19,8 @@ PostQuantThreshold 2 TexturedThreshold 0.32 +CompareMethod 2 + } ######## Duplicates finder ###################################################### diff --git a/images/config.c b/images/config.c index a6e69a19..931cc199 100644 --- a/images/config.c +++ b/images/config.c @@ -20,6 +20,7 @@ uns image_sig_postquant_min_steps; uns image_sig_postquant_max_steps; uns image_sig_postquant_threshold; double image_sig_textured_threshold; +uns image_sig_compare_method; static struct cf_section sig_config = { CF_ITEMS{ @@ -30,6 +31,7 @@ static struct cf_section sig_config = { CF_UNS("PostQuantMaxSteps", &image_sig_postquant_max_steps), CF_UNS("PostQuantThreshold", &image_sig_postquant_threshold), CF_DOUBLE("TexturedThreshold", &image_sig_textured_threshold), + CF_UNS("CompareMethod", &image_sig_compare_method), CF_END } }; diff --git a/images/sig-cmp.c b/images/sig-cmp.c index ec3f1e86..c4137239 100644 --- a/images/sig-cmp.c +++ b/images/sig-cmp.c @@ -14,12 +14,13 @@ #include "images/math.h" #include "images/images.h" #include "images/signature.h" + #include -uns -image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2) +static uns +image_signatures_dist_1(struct image_signature *sig1, struct image_signature *sig2) { - DBG("image_signatures_dist()"); + DBG("image_signatures_dist_1()"); uns cnt1 = sig1->len; uns cnt2 = sig2->len; @@ -110,3 +111,109 @@ image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2 return (1 << (3 + 3 + 8 + 16)) - measure; } + +#define ASORT_PREFIX(x) image_signatures_dist_2_##x +#define ASORT_KEY_TYPE uns +#define ASORT_ELT(i) items[i] +#define ASORT_EXTRA_ARGS , uns *items +#include "lib/arraysort.h" + +static uns +image_signatures_dist_2(struct image_signature *sig1, struct image_signature *sig2) +{ + DBG("image_signatures_dist_2()"); + + uns dist[IMAGE_REG_MAX * IMAGE_REG_MAX], p[IMAGE_REG_MAX], q[IMAGE_REG_MAX]; + uns n, i, j, k, l, s, d; + struct image_region *reg1, *reg2; + + /* Compute distance matrix */ + n = 0; + /* ... for non-textured images */ + if ((sig1->flags | sig2->flags) & IMAGE_SIG_TEXTURED) + for (j = 0, reg2 = sig2->reg; j < sig2->len; j++, reg2++) + for (i = 0, reg1 = sig1->reg; i < sig1->len; i++, reg1++) + { + // FIXME + /*uns ds = + isqr(reg1->h[0], reg2->h[0]) + + isqr(reg1->h[1], reg2->h[1]) + + isqr(reg1->h[2], reg2->h[2]);*/ + uns dt = + isqr(reg1->f[0] - reg2->f[0]) + + isqr(reg1->f[1] - reg2->f[1]) + + isqr(reg1->f[2] - reg2->f[2]) + + isqr(reg1->f[3] - reg2->f[3]) + + isqr(reg1->f[4] - reg2->f[4]) + + isqr(reg1->f[5] - reg2->f[5]); + dist[n++] = (CLAMP(dt * 0xffff / (64 * 64 * 6), 0, 0xffff) << 8) + i + (j << 4) ; + } + /* ... for textured images (ignore shape properties) */ + else + for (j = 0, reg2 = sig2->reg; j < sig2->len; j++, reg2++) + for (i = 0, reg1 = sig1->reg; i < sig1->len; i++, reg1++) + { + uns dt = + isqr(reg1->f[0] - reg2->f[0]) + + isqr(reg1->f[1] - reg2->f[1]) + + isqr(reg1->f[2] - reg2->f[2]) + + isqr(reg1->f[3] - reg2->f[3]) + + isqr(reg1->f[4] - reg2->f[4]) + + isqr(reg1->f[5] - reg2->f[5]); + dist[n++] = (CLAMP(dt * 0xffff / (64 * 64 * 6), 0, 0xffff) << 8) + i + (j << 4) ; + } + + /* One or both signatures have no regions */ + if (!n) + return 1 << IMAGE_SIG_DIST_SCALE; + + /* Get percentages */ + for (i = 0, reg1 = sig1->reg; i < sig1->len; i++, reg1++) + p[i] = reg1->wa; + for (i = 0, reg2 = sig2->reg; i < sig2->len; i++, reg2++) + q[i] = reg2->wa; + + /* Sort entries in distance matrix */ + image_signatures_dist_2_sort(n, dist); + + /* Compute significance matrix and resulting distance */ + uns sum = 0; + for (k = 0, l = 128; l; k++) + { + i = dist[k] & 15; + j = (dist[k] >> 4) & 15; + d = dist[k] >> 8; + if (p[i] <= q[j]) + { + s = p[i]; + q[j] -= p[i]; + p[i] = 0; + } + else + { + s = q[j]; + p[i] -= q[j]; + q[j] = 0; + } + l -= s; + sum += s * d; + DBG("s[%u][%u]=%u d=%u", i, j, s, d); + } + + return sum << (IMAGE_SIG_DIST_SCALE - 7 - 16); +} + +uns +image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2) +{ + switch (image_sig_compare_method) + { + case 1: + return image_signatures_dist_1(sig1, sig2); + case 2: + return image_signatures_dist_2(sig1, sig2); + default: + die("Invalid image signatures compare method."); + } +} + diff --git a/images/signature.h b/images/signature.h index 1bf166aa..d59e043d 100644 --- a/images/signature.h +++ b/images/signature.h @@ -6,6 +6,7 @@ extern uns image_sig_min_width, image_sig_min_height; extern uns *image_sig_prequant_thresholds; extern uns image_sig_postquant_min_steps, image_sig_postquant_max_steps, image_sig_postquant_threshold; extern double image_sig_textured_threshold; +extern uns image_sig_compare_method; #define IMAGE_VEC_F 6 #define IMAGE_REG_F IMAGE_VEC_F @@ -104,7 +105,7 @@ void image_sig_detect_textured(struct image_sig_data *data); /* sig-cmp.c */ -#define IMAGE_SIG_DIST_SCALE (3 + 3 + 8 + 16) +#define IMAGE_SIG_DIST_SCALE 30 uns image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2); -- 2.39.5