From d90a0c54f56fbe7bb1c0cd5349ebff43e2c6312d Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Sat, 16 Sep 2006 11:13:57 +0200 Subject: [PATCH] simple explain support for fuzzy regions matching --- images/sig-cmp-gen.h | 143 ++++++++++++++++++++++++++++++++++++++----- images/sig-cmp.c | 97 +---------------------------- 2 files changed, 129 insertions(+), 111 deletions(-) diff --git a/images/sig-cmp-gen.h b/images/sig-cmp-gen.h index 5c18fc9a..a50a3c0a 100644 --- a/images/sig-cmp-gen.h +++ b/images/sig-cmp-gen.h @@ -1,15 +1,6 @@ -#ifndef EXPLAIN - -#define MSG(x...) do{}while(0) -#define LINE do{}while(0) - -static uns -image_signatures_dist_integrated(struct image_signature *sig1, struct image_signature *sig2) - -#else - -#define MSG(x...) do{ line += sprintf(line, x); }while(0) -#define LINE do{ line = buf; msg(line, param); }while(0) +#ifdef EXPLAIN +# define MSG(x...) do{ line += sprintf(line, x); }while(0) +# define LINE do{ line = buf; msg(line, param); }while(0) static void explain_signature(struct image_signature *sig, void (*msg)(byte *text, void *param), void *param) @@ -34,12 +25,20 @@ explain_signature(struct image_signature *sig, void (*msg)(byte *text, void *par } } +#else +# define MSG(x...) do{}while(0) +# define LINE do{}while(0) +#endif + +#ifndef EXPLAIN +static uns +image_signatures_dist_integrated(struct image_signature *sig1, struct image_signature *sig2) +#else static uns image_signatures_dist_integrated_explain(struct image_signature *sig1, struct image_signature *sig2, void (*msg)(byte *text, void *param), void *param) - #endif { - DBG("image_signatures_dist_2()"); + DBG("image_signatures_dist_integrated()"); uns dist[IMAGE_REG_MAX * IMAGE_REG_MAX], p[IMAGE_REG_MAX], q[IMAGE_REG_MAX]; uns n, i, j, k, l, s, d; @@ -57,7 +56,7 @@ image_signatures_dist_integrated_explain(struct image_signature *sig1, struct im LINE; return ~0U; } - + /* Compute distance matrix */ n = 0; MSG("Distance matrix:"); @@ -151,6 +150,120 @@ image_signatures_dist_integrated_explain(struct image_signature *sig1, struct im return sum; } +#ifndef EXPLAIN +static uns +image_signatures_dist_fuzzy(struct image_signature *sig1, struct image_signature *sig2) +#else +static uns +image_signatures_dist_fuzzy_explain(struct image_signature *sig1, struct image_signature *sig2, void (*msg)(byte *text, void *param), void *param) +#endif +{ + DBG("image_signatures_dist_fuzzy()"); + +#ifdef EXPLAIN + byte buf[1024], *line = buf; + explain_signature(sig1, msg, param); + explain_signature(sig2, msg, param); +#endif + + /* FIXME: do not mux textured and non-textured images (should be split in clusters tree) */ + if ((sig1->flags ^ sig2->flags) & IMAGE_SIG_TEXTURED) + { + MSG("Textured vs non-textured"); + LINE; + return ~0U; + } + + uns cnt1 = sig1->len; + uns cnt2 = sig2->len; + struct image_region *reg1 = sig1->reg; + struct image_region *reg2 = sig2->reg; + uns mf[IMAGE_REG_MAX][IMAGE_REG_MAX], mh[IMAGE_REG_MAX][IMAGE_REG_MAX]; + uns lf[IMAGE_REG_MAX * 2], lh[IMAGE_REG_MAX * 2]; + uns df = sig1->df + sig2->df, dh = sig1->dh + sig2->dh; + + /* Compute distance matrix */ + for (uns i = 0; i < cnt1; i++) + for (uns j = 0; j < cnt2; j++) + { + uns d = 0; + for (uns k = 0; k < IMAGE_REG_F; k++) + { + int dif = reg1[i].f[k] - reg2[j].f[k]; + d += dif * dif; + } + mf[i][j] = d; + d = 0; + for (uns k = 0; k < IMAGE_REG_H; k++) + { + int dif = reg1[i].h[k] - reg2[j].h[k]; + d += dif * dif; + } + mh[i][j] = d; + } + + uns lfs = 0, lhs = 0; + for (uns i = 0; i < cnt1; i++) + { + uns f = mf[i][0], h = mh[i][0]; + for (uns j = 1; j < cnt2; j++) + { + f = MIN(f, mf[i][j]); + h = MIN(h, mh[i][j]); + } + lf[i] = (df * 0x10000) / (df + fast_sqrt_u32(f)); + lh[i] = (dh * 0x10000) / (dh + fast_sqrt_u32(h)); + lfs += lf[i] * (6 * reg1[i].wa + 2 * reg1[i].wb); + lhs += lh[i] * reg1[i].wa; + } + for (uns i = 0; i < cnt2; i++) + { + uns f = mf[0][i], h = mh[0][i]; + for (uns j = 1; j < cnt1; j++) + { + f = MIN(f, mf[j][i]); + h = MIN(h, mh[j][i]); + } + lf[i + cnt1] = (df * 0x10000) / (df + fast_sqrt_u32(f)); + lh[i + cnt1] = (dh * 0x10000) / (dh + fast_sqrt_u32(h)); + lfs += lf[i] * (6 * reg2[i].wa + 2 * reg2[i].wb); + lhs += lh[i] * reg2[i].wa; + } + + uns measure = lfs * 6 + lhs * 2 * 8; + +#ifdef LOCAL_DEBUG + /* Display similarity vectors */ + byte buf2[2 * IMAGE_REG_MAX * 16 + 3], *b = buf2; + for (uns i = 0; i < cnt1 + cnt2; i++) + { + if (i) + *b++ = ' '; + if (i == cnt1) + *b++ = '~', *b++ = ' '; + b += sprintf(b, "%.4f", (double)lf[i] / 0x10000); + } + *b = 0; + DBG("Lf=(%s)", buf2); + b = buf2; + for (uns i = 0; i < cnt1 + cnt2; i++) + { + if (i) + *b++ = ' '; + if (i == cnt1) + *b++ = '~', *b++ = ' '; + b += sprintf(b, "%.4f", (double)lh[i] / 0x10000); + } + *b = 0; + DBG("Lh=(%s)", buf2); + DBG("Lfm=%.4f", lfs / (double)(1 << (3 + 8 + 16))); + DBG("Lhm=%.4f", lhs / (double)(1 << (8 + 16))); + DBG("measure=%.4f", measure / (double)(1 << (3 + 3 + 8 + 16))); +#endif + + return (1 << (3 + 3 + 8 + 16)) - measure; +} + #undef EXPLAIN #undef MSG #undef LINE diff --git a/images/sig-cmp.c b/images/sig-cmp.c index fef29407..490e931a 100644 --- a/images/sig-cmp.c +++ b/images/sig-cmp.c @@ -17,101 +17,6 @@ #include -static uns -image_signatures_dist_fuzzy(struct image_signature *sig1, struct image_signature *sig2) -{ - DBG("image_signatures_dist_1()"); - - uns cnt1 = sig1->len; - uns cnt2 = sig2->len; - struct image_region *reg1 = sig1->reg; - struct image_region *reg2 = sig2->reg; - uns mf[IMAGE_REG_MAX][IMAGE_REG_MAX], mh[IMAGE_REG_MAX][IMAGE_REG_MAX]; - uns lf[IMAGE_REG_MAX * 2], lh[IMAGE_REG_MAX * 2]; - uns df = sig1->df + sig2->df, dh = sig1->dh + sig2->dh; - - /* Compute distance matrix */ - for (uns i = 0; i < cnt1; i++) - for (uns j = 0; j < cnt2; j++) - { - uns d = 0; - for (uns k = 0; k < IMAGE_REG_F; k++) - { - int dif = reg1[i].f[k] - reg2[j].f[k]; - d += dif * dif; - } - mf[i][j] = d; - d = 0; - for (uns k = 0; k < IMAGE_REG_H; k++) - { - int dif = reg1[i].h[k] - reg2[j].h[k]; - d += dif * dif; - } - mh[i][j] = d; - } - - uns lfs = 0, lhs = 0; - for (uns i = 0; i < cnt1; i++) - { - uns f = mf[i][0], h = mh[i][0]; - for (uns j = 1; j < cnt2; j++) - { - f = MIN(f, mf[i][j]); - h = MIN(h, mh[i][j]); - } - lf[i] = (df * 0x10000) / (df + fast_sqrt_u32(f)); - lh[i] = (dh * 0x10000) / (dh + fast_sqrt_u32(h)); - lfs += lf[i] * (6 * reg1[i].wa + 2 * reg1[i].wb); - lhs += lh[i] * reg1[i].wa; - } - for (uns i = 0; i < cnt2; i++) - { - uns f = mf[0][i], h = mh[0][i]; - for (uns j = 1; j < cnt1; j++) - { - f = MIN(f, mf[j][i]); - h = MIN(h, mh[j][i]); - } - lf[i + cnt1] = (df * 0x10000) / (df + fast_sqrt_u32(f)); - lh[i + cnt1] = (dh * 0x10000) / (dh + fast_sqrt_u32(h)); - lfs += lf[i] * (6 * reg2[i].wa + 2 * reg2[i].wb); - lhs += lh[i] * reg2[i].wa; - } - - uns measure = lfs * 6 + lhs * 2 * 8; - -#ifdef LOCAL_DEBUG - /* Display similarity vectors */ - byte buf[2 * IMAGE_REG_MAX * 16 + 3], *b = buf; - for (uns i = 0; i < cnt1 + cnt2; i++) - { - if (i) - *b++ = ' '; - if (i == cnt1) - *b++ = '~', *b++ = ' '; - b += sprintf(b, "%.4f", (double)lf[i] / 0x10000); - } - *b = 0; - DBG("Lf=(%s)", buf); - b = buf; - for (uns i = 0; i < cnt1 + cnt2; i++) - { - if (i) - *b++ = ' '; - if (i == cnt1) - *b++ = '~', *b++ = ' '; - b += sprintf(b, "%.4f", (double)lh[i] / 0x10000); - } - *b = 0; - DBG("Lh=(%s)", buf); - DBG("Lfm=%.4f", lfs / (double)(1 << (3 + 8 + 16))); - DBG("Lhm=%.4f", lhs / (double)(1 << (8 + 16))); - DBG("measure=%.4f", measure / (double)(1 << (3 + 3 + 8 + 16))); -#endif - - return (1 << (3 + 3 + 8 + 16)) - measure; -} - #define ASORT_PREFIX(x) image_signatures_dist_integrated_##x #define ASORT_KEY_TYPE uns #define ASORT_ELT(i) items[i] @@ -144,7 +49,7 @@ image_signatures_dist_explain(struct image_signature *sig1, struct image_signatu case 0: return image_signatures_dist_integrated_explain(sig1, sig2, msg, param); case 1: - return image_signatures_dist_fuzzy(sig1, sig2); + return image_signatures_dist_fuzzy_explain(sig1, sig2, msg, param); default: ASSERT(0); } -- 2.39.2