images/image-idx.c

   1 #undef LOCAL_DEBUG
   2
   3 #include "sherlock/sherlock.h"
   4 #include "lib/mempool.h"
   5 #include "lib/conf.h"
   6 #include "lib/getopt.h"
   7 #include "lib/fastbuf.h"
   8 #include "lib/chartype.h"
   9 #include "sherlock/object.h"
  10 #include "lib/url.h"
  11 #include "lib/unicode.h"
  12 #include "sherlock/lizard-fb.h"
  13 #include "sherlock/tagged-text.h"
  14 #include "charset/charconv.h"
  15 #include "charset/unicat.h"
  16 #include "charset/fb-charconv.h"
  17 #include "indexer/indexer.h"
  18 #include "indexer/lexicon.h"
  19 #include "indexer/params.h"
  20 #include "utils/dumpconfig.h"
  21 #include "lang/lang.h"
  22 #include "lib/base224.h"
  23 #include "lib/bbuf.h"
  24 #include "lib/clists.h"
  25
  26 #include "images/images.h"
  27 #include "images/image-obj.h"
  28 #include "images/image-sig.h"
  29 #include "images/dup-cmp.h"
  30 #include "images/kd-tree.h"
  31 #include "images/color.h"
  32
  33 #include <stdlib.h>
  34 #include <fcntl.h>
  35 #include <string.h>
  36
  37 static struct fastbuf *fb_cards;
  38 static struct fastbuf *fb_card_attrs;
  39 static struct buck2obj_buf *buck2obj;
  40
  41 /* This should happen in gatherer or scanner */
  42 static void
  43 generate_signatures(uns limit)
  44 {
  45   fb_cards = index_bopen("cards", O_RDONLY);
  46   fb_card_attrs = index_bopen("card-attrs", O_RDONLY);
  47   struct fastbuf *fb_signatures = index_bopen("image-sig", O_CREAT | O_WRONLY | O_TRUNC);
  48   struct card_attr ca;
  49   struct image_signature sig;
  50   struct mempool *pool = mp_new(1 << 16);
  51   struct buck2obj_buf *bob = buck2obj_alloc();
  52   uns count = 0;
  53
  54   if (limit == ~0U)
  55     log(L_INFO, "Generating image signatures");
  56   else
  57     log(L_INFO, "Generating at most %d image signatures", limit);
  58   bputl(fb_signatures, 0);
  59   imo_decompress_thumbnails_init();
  60
  61   for (oid_t oid = 0; bread(fb_card_attrs, &ca, sizeof(ca)); oid++)
  62     if ((uns)((ca.type_flags >> 4) - 8) < 4)
  63       {
  64         bsetpos(fb_cards, (sh_off_t)ca.card << CARD_POS_SHIFT);
  65         uns buck_len = bgetl(fb_cards) - (LIZARD_COMPRESS_HEADER - 1);
  66         uns buck_type = bgetc(fb_cards) + BUCKET_TYPE_PLAIN;
  67         mp_flush(pool);
  68         struct odes *obj = obj_read_bucket(bob, pool, buck_type, buck_len, fb_cards, NULL);
  69         struct oattr *attr;
  70         if (!obj)
  71           die("Failed to read card");
  72         if (attr = obj_find_attr(obj, 'N'))
  73           {
  74 #ifdef LOCAL_DEBUG
  75             byte *url = obj_find_aval(obj_find_attr(obj, 'U' + OBJ_ATTR_SON)->son, 'U');
  76             DBG("Reading oid=%d url=%s", oid, url);
  77 #endif
  78             struct image_obj imo;
  79             imo_init(&imo, pool, obj);
  80             if (imo_decompress_thumbnail(&imo))
  81               {
  82                 if (compute_image_signature(&imo.thumb, &sig))
  83                   {
  84                     bwrite(fb_signatures, &oid, sizeof(oid));
  85                     bwrite(fb_signatures, &sig.vec, sizeof(struct image_vector));
  86                     bputc(fb_signatures, sig.len);
  87                     if (sig.len)
  88                       bwrite(fb_signatures, sig.reg, sig.len * sizeof(struct image_region));
  89                     count++;
  90                     if (count % 10000 == 0)
  91                       log(L_DEBUG, "... passed %d images", count);
  92                     if (count >= limit)
  93                       break;
  94                   }
  95                 else
  96                   DBG("Cannot create signature");
  97               }
  98             else
  99               DBG("Cannot decompress thumbnail");
 100           }
 101       }
 102   brewind(fb_signatures);
 103   bputl(fb_signatures, count);
 104   DBG("%d signatures written", count);
 105
 106   imo_decompress_thumbnails_done();
 107   buck2obj_free(bob);
 108   mp_delete(pool);
 109   bclose(fb_cards);
 110   bclose(fb_card_attrs);
 111   bclose(fb_signatures);
 112 }
 113
 114 struct signature_record {
 115   oid_t oid;
 116   struct image_vector vec;
 117 };
 118
 119 #define ASORT_PREFIX(x) build_search_tree_##x
 120 #define ASORT_KEY_TYPE struct signature_record *
 121 #define ASORT_ELT(i) rec[i]
 122 #define ASORT_LT(x,y) x->vec.f[dim] < y->vec.f[dim]
 123 #define ASORT_EXTRA_ARGS , uns dim, struct signature_record **rec
 124 #include "lib/arraysort.h"
 125
 126 #if 0
 127 #define DBG_KD(x...) DBG(x)
 128 #else
 129 #define DBG_KD(x...) do{}while(0)
 130 #endif
 131
 132 static struct image_tree tree;
 133 static struct signature_record *records;
 134 static struct signature_record **precords;
 135
 136 static void
 137 build_kd_tree(void)
 138 {
 139   log(L_INFO, "Building KD-tree");
 140
 141   struct fastbuf *fb_signatures = index_bopen("image-sig", O_RDONLY);
 142   tree.count = bgetl(fb_signatures);
 143   ASSERT(tree.count < 0x80000000);
 144   if (!tree.count)
 145     {
 146       /* FIXME */
 147       bclose(fb_signatures);
 148       die("There are no signatures");
 149     }
 150   else
 151     {
 152       DBG("Reading %d signatures", tree.count);
 153       records = xmalloc(tree.count * sizeof(struct signature_record));
 154       precords = xmalloc(tree.count * sizeof(void *));
 155       for (uns i = 0; i < tree.count; i++)
 156         {
 157           bread(fb_signatures, &records[i].oid, sizeof(oid_t));
 158           bread(fb_signatures, &records[i].vec, sizeof(struct image_vector));
 159           uns len = bgetc(fb_signatures);
 160           bskip(fb_signatures, len * sizeof(struct image_region));
 161           precords[i] = records + i;
 162           if (likely(i))
 163             for (uns j = 0; j < IMAGE_VEC_K; j++)
 164               {
 165                 tree.bbox.vec[0].f[j] = MIN(tree.bbox.vec[0].f[j], records[i].vec.f[j]);
 166                 tree.bbox.vec[1].f[j] = MAX(tree.bbox.vec[1].f[j], records[i].vec.f[j]);
 167               }
 168           else
 169             tree.bbox.vec[0] = tree.bbox.vec[1] = records[0].vec;
 170         }
 171       bclose(fb_signatures);
 172
 173       for (tree.depth = 1; (uns)(2 << tree.depth) < tree.count; tree.depth++);
 174       DBG("depth=%d nodes=%d bbox=[(%s), (%s)]", tree.depth, 1 << tree.depth,
 175           stk_print_image_vector(tree.bbox.vec + 0), stk_print_image_vector(tree.bbox.vec + 1));
 176       uns leaves_index = 1 << (tree.depth - 1);
 177       tree.nodes = xmalloc_zero((1 << tree.depth) * sizeof(struct image_node));
 178       tree.leaves = xmalloc_zero(tree.count * sizeof(struct image_leaf));
 179
 180       /* Initialize recursion */
 181       struct stk {
 182         struct image_bbox bbox;
 183         uns index, count;
 184         struct signature_record **start;
 185       } stk_top[32], *stk = stk_top + 1;
 186       stk->index = 1;
 187       stk->start = precords;
 188       stk->count = tree.count;
 189       stk->bbox.vec[0] = tree.bbox.vec[0];
 190       for (uns i = 0; i < IMAGE_VEC_K; i++)
 191         stk->bbox.vec[1].f[i] = tree.bbox.vec[1].f[i] - tree.bbox.vec[0].f[i];
 192       uns entry_index = 0;
 193
 194       /* Main loop */
 195       while (stk != stk_top)
 196         {
 197           DBG_KD("Main loop... depth=%d index=%d count=%d, start=%d, min=%s dif=%s",
 198               stk - stk_top, stk->index, stk->count, stk->start - precords,
 199               stk_print_image_vector(stk->bbox.vec + 0), stk_print_image_vector(stk->bbox.vec + 1));
 200           ASSERT(stk->count);
 201
 202           /* Create leaf node */
 203           if (stk->index >= leaves_index || stk->count < 2)
 204             {
 205               tree.nodes[stk->index].val = IMAGE_NODE_LEAF | entry_index;
 206               for (; stk->count--; stk->start++)
 207                 {
 208                   struct image_leaf *leaf = &tree.leaves[entry_index++];
 209                   struct signature_record *record = *stk->start;
 210                   leaf->oid = record->oid;
 211                   leaf->flags = 0;
 212                   for (uns i = IMAGE_VEC_K; i--; )
 213                     {
 214                       uns bits = IMAGE_LEAF_BITS(i);
 215                       leaf->flags <<= bits;
 216                       if (stk->bbox.vec[1].f[i])
 217                         {
 218                           uns value =
 219                             (record->vec.f[i] - stk->bbox.vec[0].f[i]) *
 220                             ((1 << bits) - 1) / stk->bbox.vec[1].f[i];
 221                           ASSERT(value < (uns)(1 << bits));
 222                           leaf->flags |= value;
 223                         }
 224                     }
 225                   if (!stk->count)
 226                     leaf->flags |= IMAGE_LEAF_LAST;
 227                   DBG_KD("Creating leaf node; oid=%d vec=(%s) flags=0x%08x",
 228                       leaf->oid, stk_print_image_vector(&record->vec), leaf->flags);
 229                 }
 230               stk--;
 231             }
 232
 233           /* Create internal node */
 234           else
 235             {
 236               /* Select dimension to splis */
 237               uns dim = 0;
 238               for (uns i = 1; i < IMAGE_VEC_K; i++)
 239                 if (stk->bbox.vec[1].f[i] > stk->bbox.vec[1].f[dim])
 240                   dim = i;
 241
 242               /* Sort... FIXME: we only need the median */
 243               build_search_tree_sort(stk->count, dim, stk->start);
 244
 245               /* Split in the middle */
 246               uns index = stk->index;
 247               stk[1].index = stk[0].index * 2;
 248               stk[0].index = stk[1].index + 1;
 249               stk[1].count = stk[0].count >> 1;
 250               stk[0].count -= stk[1].count;
 251               stk[1].start = stk[0].start;
 252               stk[0].start += stk[1].count;
 253
 254               /* Choose split value */
 255               uns lval = stk->start[-1]->vec.f[dim];
 256               uns rval = stk->start[0]->vec.f[dim];
 257               uns pivot = stk->bbox.vec[0].f[dim] + (stk->bbox.vec[1].f[dim] >> 1);
 258               if (pivot <= lval)
 259                 pivot = lval;
 260               else if (pivot >= rval)
 261                 pivot = rval;
 262
 263               DBG_KD("Created internal node; dim=%d pivot=%d", dim, pivot);
 264
 265               /* Split the box */
 266               stk[1].bbox = stk[0].bbox;
 267               stk[1].bbox.vec[1].f[dim] = pivot - stk[0].bbox.vec[0].f[dim];
 268               stk[0].bbox.vec[0].f[dim] += stk[1].bbox.vec[1].f[dim];
 269               stk[0].bbox.vec[1].f[dim] -= stk[1].bbox.vec[1].f[dim];
 270
 271               /* Fill the node structure */
 272               tree.nodes[index].val = dim + (pivot << 8);
 273               stk++;
 274             }
 275         }
 276
 277       DBG("Tree constructed, saving...");
 278
 279       struct fastbuf *fb_tree = index_bopen("image-tree", O_CREAT | O_WRONLY | O_TRUNC);
 280       bputl(fb_tree, tree.count);
 281       bputl(fb_tree, tree.depth);
 282       bwrite(fb_tree, &tree.bbox, sizeof(struct image_bbox));
 283       bwrite(fb_tree, tree.nodes + 1, ((1 << tree.depth) - 1) * sizeof(struct image_node));
 284       bwrite(fb_tree, tree.leaves, tree.count * sizeof(struct image_leaf));
 285       bclose(fb_tree);
 286
 287       //xfree(tree.leaves);
 288       //xfree(tree.nodes);
 289       //xfree(precords);
 290       //xfree(records);
 291     }
 292 }
 293
 294 /*********************************************************************************/
 295
 296 static uns pass1_buf_size = 400 << 20;
 297 static uns pass1_max_count = 100000;
 298 static uns pass1_search_dist = 40;
 299 static uns pass1_search_count = 500;
 300
 301 static struct mempool *pass1_pool;
 302 static byte *pass1_buf_start;
 303 static byte *pass1_buf_pos;
 304 static uns pass1_buf_free;
 305 static uns pass1_buf_used;
 306 static clist pass1_buf_list;
 307 static clist pass1_lru_list;
 308 static u64 pass1_lookups;
 309 static u64 pass1_reads;
 310 static u64 pass1_pairs;
 311 static u64 pass1_dups;
 312 static u64 pass1_shrinks;
 313
 314 struct pass1_node {
 315   cnode lru_node;
 316   cnode buf_node;
 317   uns buf_size;
 318   byte *buf;
 319   oid_t oid;
 320   byte *url;
 321   struct image image;
 322   struct image_dup dup;
 323 };
 324
 325 #define HASH_PREFIX(x) pass1_hash_##x
 326 #define HASH_NODE struct pass1_node
 327 #define HASH_KEY_ATOMIC oid
 328 #define HASH_WANT_CLEANUP
 329 #define HASH_WANT_FIND
 330 #define HASH_WANT_NEW
 331 #define HASH_WANT_REMOVE
 332 #include "lib/hashtable.h"
 333
 334 static inline void
 335 pass1_buf_init(void)
 336 {
 337   //DBG("pass1_buf_init()");
 338   pass1_buf_free = pass1_buf_size;
 339   pass1_buf_start = pass1_buf_pos = xmalloc(pass1_buf_size);
 340   pass1_buf_used = 0;
 341 }
 342
 343 static inline void
 344 pass1_buf_cleanup(void)
 345 {
 346   //DBG("pass1_buf_cleanup()");
 347   xfree(pass1_buf_start);
 348 }
 349
 350 static void
 351 pass1_node_free(struct pass1_node *node)
 352 {
 353   //DBG("pass1_node_free(%d)", (uns)node->oid);
 354   if (node->buf_size)
 355     {
 356       pass1_buf_used -= node->buf_size;
 357       clist_remove(&node->buf_node);
 358     }
 359   clist_remove(&node->lru_node);
 360   pass1_hash_remove(node);
 361 }
 362
 363 static inline void
 364 pass1_node_free_lru(void)
 365 {
 366   ASSERT(!clist_empty(&pass1_lru_list));
 367   pass1_node_free(SKIP_BACK(struct pass1_node, lru_node, clist_head(&pass1_lru_list)));
 368 }
 369
 370 static inline void
 371 pass1_node_after_move(struct pass1_node *node, addr_int_t move)
 372 {
 373   //DBG("pass1_node_after_mode(%d, %d)", (uns)node->oid, (uns)move);
 374   /* adjust internal pointers */
 375 #define MOVE(x) x = (byte *)(x) - move
 376   MOVE(node->url);
 377   MOVE(node->image.pixels);
 378   MOVE(node->dup.buf);
 379 #undef MOVE
 380 }
 381
 382 static inline void
 383 pass1_buf_shrink(void)
 384 {
 385   DBG("pass1_buf_shrink()");
 386   pass1_shrinks++;
 387   pass1_buf_free = pass1_buf_size;
 388   pass1_buf_pos = pass1_buf_start;
 389   CLIST_FOR_EACH(void *, p, pass1_buf_list)
 390     {
 391       struct pass1_node *node = SKIP_BACK(struct pass1_node, buf_node, p);
 392       if (node->buf != pass1_buf_pos)
 393         {
 394           memmove(pass1_buf_pos, node->buf, node->buf_size);
 395           pass1_node_after_move(node, node->buf - pass1_buf_pos);
 396           node->buf = pass1_buf_pos;
 397         }
 398       pass1_buf_pos += node->buf_size;
 399       pass1_buf_free -= node->buf_size;
 400     }
 401 }
 402
 403 static void *
 404 pass1_buf_alloc(uns size)
 405 {
 406   //DBG("pass1_buf_alloc(%d)", size);
 407
 408   /* if there is not enough free space at the end of the buffer */
 409   if (size > pass1_buf_free)
 410     {
 411       /* free some lru nodes */
 412       //DBG("freeing lru nodes");
 413       while (size > pass1_buf_size - pass1_buf_used || pass1_buf_used * 2 > pass1_buf_size)
 414         {
 415           if (unlikely(clist_empty(&pass1_lru_list))) // FIXME
 416             die("Buffer too small");
 417           pass1_node_free_lru();
 418         }
 419
 420       pass1_buf_shrink();
 421     }
 422
 423   /* final allocation */
 424   void *result = pass1_buf_pos;
 425   pass1_buf_pos += size;
 426   pass1_buf_free -= size;
 427   pass1_buf_used += size;
 428   return result;
 429 }
 430
 431 static struct pass1_node *
 432 pass1_node_new(oid_t oid)
 433 {
 434   DBG("pass1_node_new(%d)", (uns)oid);
 435   if (pass1_hash_table.hash_count == pass1_max_count)
 436     pass1_node_free_lru();
 437   struct pass1_node *node = pass1_hash_new(oid);
 438   mp_flush(pass1_pool);
 439   pass1_reads++;
 440
 441   /* read object */
 442   struct card_attr ca;
 443   bsetpos(fb_card_attrs, (sh_off_t)oid * sizeof(ca)); /* FIXME: these seeks can be easily removed */
 444   bread(fb_card_attrs, &ca, sizeof(ca));
 445
 446   bsetpos(fb_cards, (sh_off_t)ca.card << CARD_POS_SHIFT); /* FIXME: maybe a presort should handle these random seeks */
 447   uns buck_len = bgetl(fb_cards) - (LIZARD_COMPRESS_HEADER - 1);
 448   uns buck_type = bgetc(fb_cards) + BUCKET_TYPE_PLAIN;
 449   struct odes *obj = obj_read_bucket(buck2obj, pass1_pool, buck_type, buck_len, fb_cards, NULL);
 450   if (unlikely(!obj))
 451     die("Failed to read card");
 452   byte *url = obj_find_aval(obj_find_attr(obj, 'U' + OBJ_ATTR_SON)->son, 'U');
 453   uns url_len = strlen(url);
 454
 455   /* decompress thumbnail */
 456   struct image_obj imo;
 457   imo_init(&imo, pass1_pool, obj);
 458   if (unlikely(!imo_decompress_thumbnail(&imo)))
 459     die("Cannot decompress thumbnail");
 460   node->image = imo.thumb;
 461
 462   /* create duplicates comparision object */
 463   image_dup_init(&node->dup, &node->image, pass1_pool);
 464
 465   /* copy data */
 466   //DBG("loaded image %s s=%d d=%d", url, node->image.size, node->dup.buf_size);
 467   node->buf_size = node->image.size + node->dup.buf_size + url_len + 1;
 468   if (node->buf_size)
 469     {
 470       byte *buf = node->buf = pass1_buf_alloc(node->buf_size);
 471       clist_add_tail(&pass1_buf_list, &node->buf_node);
 472 #define COPY(ptr, size) ({ void *_p=buf; uns _size=(size); buf+=_size; memcpy(_p,(ptr),_size); _p; })
 473       node->url = COPY(url, url_len + 1);
 474       node->image.pixels = COPY(node->image.pixels, node->image.size);
 475       node->dup.buf = COPY(node->dup.buf, node->dup.buf_size);
 476 #undef COPY
 477     }
 478
 479   /* add to lru list */
 480   return node;
 481 }
 482
 483 static inline struct pass1_node *
 484 pass1_node_lock(oid_t oid)
 485 {
 486   DBG("pass1_node_lock(%d)", (uns)oid);
 487   pass1_lookups++;
 488   struct pass1_node *node = pass1_hash_find(oid);
 489   if (node)
 490     {
 491       clist_remove(&node->lru_node);
 492       return node;
 493     }
 494   else
 495     return pass1_node_new(oid);
 496 }
 497
 498 static inline void
 499 pass1_node_unlock(struct pass1_node *node)
 500 {
 501   //DBG("pass1_node_unlock(%d)", (uns)node->oid);
 502   clist_add_tail(&pass1_lru_list, &node->lru_node);
 503 }
 504
 505 static void
 506 pass1(void)
 507 {
 508   log(L_INFO, "Looking for duplicates");
 509   ASSERT(tree.nodes);
 510
 511   /* initialization */
 512   pass1_lookups = pass1_reads = pass1_pairs = pass1_dups = pass1_shrinks = 0;
 513   fb_cards = bopen("index/cards", O_RDONLY, 10000); // FIXME
 514   fb_card_attrs = bopen("index/card-attrs", O_RDONLY, sizeof(struct card_attr)); // FIXME
 515   buck2obj = buck2obj_alloc();
 516   imo_decompress_thumbnails_init();
 517   clist_init(&pass1_lru_list);
 518   clist_init(&pass1_buf_list);
 519   pass1_hash_init();
 520   pass1_buf_init();
 521   pass1_pool = mp_new(1 << 20);
 522
 523   /* main loop */
 524   for (uns i = 0; i < tree.count; )
 525     {
 526       /* lookup next image */
 527       oid_t oid = tree.leaves[i].oid;
 528       struct pass1_node *node = pass1_node_lock(oid);
 529
 530       /* compare with all near images */
 531       struct image_search search;
 532       image_search_init(&search, &tree, &precords[i]->vec, pass1_search_dist);
 533       /* FIXME: can be faster than general search in KD-tree */
 534       oid_t oid2;
 535       uns dist;
 536       for (uns j = 0; j < pass1_search_count && image_search_next(&search, &oid2, &dist); j++)
 537         {
 538           if (oid < oid2)
 539             {
 540               struct pass1_node *node2 = pass1_node_lock(oid2);
 541               DBG("comparing %d and %d", oid, oid2);
 542               if (image_dup_compare(&node->dup, &node2->dup, IMAGE_DUP_TRANS_ALL))
 543                 {
 544                   pass1_dups++;
 545                   log(L_DEBUG, "*** Found duplicates oid1=0x%x oid=0x%x", (uns)node->oid, (uns)node2->oid);
 546                   log(L_DEBUG, "  %s", node->url);
 547                   log(L_DEBUG, "  %s", node2->url);
 548                 }
 549               pass1_pairs++;
 550               pass1_node_unlock(node2);
 551             }
 552         }
 553       image_search_done(&search);
 554       pass1_node_unlock(node);
 555       i++;
 556       if (i % 1000 == 0)
 557         log(L_DEBUG, "... passed %d images", i);
 558     }
 559
 560   /* clean up */
 561   pass1_hash_cleanup();
 562   pass1_buf_cleanup();
 563   mp_delete(pass1_pool);
 564   bclose(fb_cards);
 565   bclose(fb_card_attrs);
 566   buck2obj_free(buck2obj);
 567   imo_decompress_thumbnails_done();
 568
 569   /* print statistics */
 570   log(L_INFO, "%d count, %Ld lookups, %Ld reads, %Ld pairs, %Ld dups, %Ld shrinks", tree.count,
 571     (long long int)pass1_lookups, (long long int)pass1_reads,
 572     (long long int)pass1_pairs, (long long int)pass1_dups, (long long int)pass1_shrinks);
 573 }
 574
 575 /*********************************************************************************/
 576
 577 static char *shortopts = CF_SHORT_OPTS "";
 578 static struct option longopts[] =
 579 {
 580   CF_LONG_OPTS
 581   { NULL, 0, 0, 0 }
 582 };
 583
 584 static char *help = "\
 585 Usage: image-indexer [<options>]\n\
 586 \n\
 587 Options:\n" CF_USAGE;
 588
 589 static void NONRET
 590 usage(byte *msg)
 591 {
 592   if (msg)
 593   {
 594     fputs(msg, stderr);
 595     fputc('\n', stderr);
 596   }
 597   fputs(help, stderr);
 598   exit(1);
 599 }
 600
 601
 602 int
 603 main(int argc UNUSED, char **argv)
 604 {
 605   int opt;
 606
 607   log_init(argv[0]);
 608   while ((opt = cf_getopt(argc, argv, shortopts, longopts, NULL)) >= 0)
 609     switch (opt)
 610     {
 611       default:
 612       usage("Invalid option");
 613     }
 614   if (optind != argc)
 615     usage("Invalid usage");
 616
 617   srgb_to_luv_init();
 618
 619   generate_signatures(20000);
 620   build_kd_tree();
 621   pass1();
 622
 623   return 0;
 624 }