home *** CD-ROM | disk | FTP | other *** search
/ Dream 52 / Amiga_Dream_52.iso / Linux / Divers / bomb.tar.gz / bomb.tar / bomb / match.c < prev    next >
C/C++ Source or Header  |  1997-07-15  |  8KB  |  339 lines
  1. /*
  2.     bomb - automatic interactive visual stimulation
  3.     Copyright (C) 1994  Scott Draves <spot@cs.cmu.edu>
  4.  
  5.     This program is free software; you can redistribute it and/or modify
  6.     it under the terms of the GNU General Public License as published by
  7.     the Free Software Foundation; either version 2 of the License, or
  8.     (at your option) any later version.
  9.  
  10.     This program is distributed in the hope that it will be useful,
  11.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.     GNU General Public License for more details.
  14.  
  15.     You should have received a copy of the GNU General Public License
  16.     along with this program; if not, write to the Free Software
  17.     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18. */
  19.  
  20. #include <math.h>
  21.  
  22. #include "defs.h"
  23. #include "image.h"
  24. #include "image_db.h"
  25. #include "match.h"
  26.  
  27.  
  28. #define FR R8b
  29.  
  30. /* dot product of two sub-rectangles.  the image8_t is 8 bit per pixel and
  31.    the Image is 32, so we compare only to SIG_CHAN */
  32.  
  33. #define SIG_CHAN 1
  34.  
  35. int
  36. image8_compare(Image *image1, image8_t *image2)
  37. {
  38.   int t, i, j;
  39.   int diff = 0;
  40.   Image im1 = *image1;
  41.   image8_t im2 = *image2;
  42.  
  43.   for (i = 0; i < im1.height; i++)
  44.      for (j = 0; j < im1.width; j++) {
  45.     u_char *p1 = (u_char *)(im1.pixels + (i * im1.stride + j));
  46.     u_char *p2 = (u_char *)(im2.p + (i * im2.stride + j));
  47.     u_char  g = p1[SIG_CHAN];
  48.     t = g - *p2;
  49.     diff += t * t;
  50.  
  51.      }
  52.   return diff;
  53. }
  54.  
  55. int
  56. image8_climb(image8_t *base, Image *tile)
  57. {
  58.    Image try;
  59.    int t, current = image8_compare(tile, base);
  60.    if (0 == current)
  61.       return 1;
  62.       
  63.    try = *tile;
  64.    if (try.origin_y + try.height < try.parent->height) {
  65.       try.pixels += try.stride;
  66.       try.origin_y++;
  67.       t = image8_compare(&try, base);
  68.       if (t < current) {
  69.      *tile = try;
  70.      current = t;
  71.       }
  72.       try.pixels -= try.stride;
  73.       try.origin_y--;
  74.    }
  75.    if (try.origin_y > 0) {
  76.       try.pixels -= try.stride;
  77.       try.origin_y--;
  78.       t = image8_compare(&try, base);
  79.       if (t < current) {
  80.      *tile = try;
  81.      current = t;
  82.       }
  83.       try.pixels += try.stride;
  84.       try.origin_y++;
  85.    }
  86.    if (try.origin_x + try.width < try.parent->width) {
  87.       try.origin_x++;
  88.       try.pixels += 1;
  89.       t = image8_compare(&try, base);
  90.       if (t < current) {
  91.      *tile = try;
  92.      current = t;
  93.       }
  94.       try.origin_x--;
  95.       try.pixels -= 1;
  96.    }
  97.    if (try.origin_x > 0) {
  98.       try.pixels -= 1;
  99.       try.origin_x--;
  100.       t = image8_compare(&try, base);
  101.       if (t < current) {
  102.      *tile = try;
  103.      current = t;
  104.       }
  105.       try.pixels += 1;
  106.       try.origin_x++;
  107.    }
  108.    return 0;
  109. }
  110.  
  111. void
  112. image8_match_init(image8_t *base,
  113.           Image *images, int nimages,
  114.           int nbest, Image *best, int *best_diffs, int *origins)
  115. {
  116.    int i;
  117.    int w = base->width;
  118.    int h = base->height;
  119.    for (i = 0; i < nbest; i++) {
  120.       int ii = R % nimages;
  121.       Image *img = &images[ii];
  122.       origins[i] = ii;
  123.       if (0 >  (img->width - w)) {
  124.     printf("pping\n");
  125.     exit(1);
  126.       }
  127.       if (0 >  (img->height - h)) {
  128.     printf("zing\n");
  129.     exit(1);
  130.       }
  131.       (void) image_subimage(best + i, img,
  132.                 R % (img->width - w + 1),
  133.                 R % (img->height - h + 1),
  134.                 w, h);
  135.       best_diffs[i] = image8_compare(best + i, base);
  136.    }
  137. }
  138.  
  139. /* BIG_IMAGES and SMALL_IMAGES are NIMAGES length arrays of images.  the
  140.    small ones are filtered down (by SMALL_FACTOR) versions of the big ones.
  141.    search for PATTERN and return the best match found in MATCH.  it tries
  142.    NSMALL matches in each of the small images, and the NBIG best of those
  143.    are matched against the big images. */
  144.  
  145. #define MAX_NBIG 300
  146.  
  147. void
  148. image8_match2(image8_t *pattern, Image *match,
  149.           Image *big_images, Image *small_images, int nimages,
  150.           int nbig, int nsmall)
  151. {
  152.    int i;
  153.    Image big_match;
  154.    static Image small_matches[MAX_NBIG];
  155.    static int diffs[MAX_NBIG];
  156.    static int origins[MAX_NBIG];
  157.    int best, best_i;
  158.  
  159.    if (nbig > MAX_NBIG) {
  160.       nbig = MAX_NBIG;
  161.       fprintf(stderr, "nbig truncated from %d to %d\n",
  162.           nbig, MAX_NBIG);
  163.    }
  164.  
  165.    image8_filter_down(pattern, &small_pattern);
  166.  
  167.    image8_match_init(&small_pattern, small_images, nimages,
  168.              nbig, small_matches, diffs, origins);
  169.  
  170.    for (i = 0; i < nimages; i++)
  171.       image8_match(&small_pattern, &small_images[i],
  172.            nsmall, nbig, small_matches, diffs, origins, i);
  173.      
  174.    for (i = 0; i < nbig; i++) {
  175.       Image *small_match = &small_matches[i];
  176.       int match_i, diff;
  177.       match_i = origins[i];
  178.       image_subimage(&big_match, &big_images[match_i],
  179.              small_match->origin_x * SMALL_FACTOR,
  180.              small_match->origin_y * SMALL_FACTOR,
  181.              pattern->width, pattern->height);
  182.       diff = image8_compare(&big_match, pattern);
  183.       if (0 == i || diff < best) {
  184.      best = diff;
  185.      *match = big_match;
  186.       }
  187.    }
  188. }
  189.  
  190.  
  191.  
  192. int
  193. image8_find_largest(int n, int *diffs)
  194. {
  195.    int i;
  196.    int j = 0;
  197.    int v = diffs[j];
  198.  
  199.    for (i = 1; i < n; i++)
  200.       if (diffs[i] > v) {
  201.      v = diffs[i];
  202.      j = i;
  203.       }
  204.    return j;
  205. }
  206.    
  207.  
  208. /* match NTRIES rectangles in IMAGE against BASE.  return the NBEST matches
  209.    in BEST, and how good each match is in BEST_DIFFS.  the BEST and
  210.    BEST_DIFFS arrays must be initialized on entry.  should use a heap
  211.    instead of an array */
  212.  
  213. void
  214. image8_match(image8_t *base,
  215.          Image *image, int ntries,
  216.          int nbest, Image *best, int *best_diffs,
  217.          int *origins, int index)
  218. {
  219.    int w = base->width;
  220.    int h = base->height;
  221.    int y, i, j;
  222.    int n_per_row, d_row;
  223.    int npix;
  224.    int worst_of_best;
  225.    int worst_index;
  226.    Image try;
  227.  
  228.    if (ntries > (image->height - h)) {
  229.       n_per_row = (int) ceil(ntries / (double)(image->height - h + 1));
  230.       d_row = 1;
  231.    } else {
  232.       n_per_row = 1;
  233.       d_row = (int) ceil((image->height - h + 1) / (double)ntries);
  234.    }
  235.  
  236.    worst_index = image8_find_largest(nbest, best_diffs);
  237.    worst_of_best = best_diffs[worst_index];
  238.  
  239.    image_subimage(&try, image, 0, 0, w, h);
  240.                 
  241.    for (y = 0; y < image->height - h; y += d_row) {
  242.       Pixel *row_base = image->pixels + y * image->stride;
  243.       try.origin_y = y;
  244.       for (j = 0; j < n_per_row; j++) {
  245.      int diff;
  246.      try.origin_x = FR % (image->width - w + 1);
  247.      try.pixels = row_base + try.origin_x;
  248.      diff = image8_compare(&try, base);
  249.      if (diff < worst_of_best) {
  250.         origins[worst_index] = index;
  251.         best_diffs[worst_index] = diff;
  252.         best[worst_index] = try;
  253.         worst_index = image8_find_largest(nbest, best_diffs);
  254.         worst_of_best = best_diffs[worst_index];
  255.      }
  256.       }
  257.    }
  258. }
  259.  
  260. void
  261. image8_fill(image8_t *image, int v)
  262. {
  263.    int w = image->width;
  264.    int h = image->height;
  265.    u_char *p = image->p;
  266.    int s = image->stride;
  267.    int i, j;
  268.    
  269.    for (i = 0; i < h; i++)
  270.       for (j = 0; j < w; j++)
  271.      p[i * s + j] = v;
  272. }
  273.  
  274.  
  275. void
  276. image8_filter_down(image8_t *from, image8_t *to)
  277. {
  278.    image8_t f = *from;
  279.    image8_t t = *to;
  280.    int h_scale = f.height / t.height;
  281.    int w_scale = f.width / t.width;
  282.    int i, j;
  283.    int npix;
  284.    npix = h_scale * w_scale;
  285.  
  286.    for (i = 0; i < t.height; i++)
  287.       for (j = 0; j < t.width; j++) {
  288.      int ii, jj;
  289.      int tot = 0;
  290.      for (ii = 0; ii < h_scale; ii++)
  291.         for (jj = 0; jj < w_scale; jj++) {
  292.            tot += f.p[f.stride * (i * h_scale + ii) +
  293.               (j * w_scale + jj)];
  294.         }
  295.      t.p[t.stride * i + j] = tot / npix;
  296.       }
  297. }
  298.  
  299. /* 24->8, just uses the red channel */
  300. void
  301. image8_blit(Image *from, image8_t *to)
  302. {
  303.    Image f = *from;
  304.    int stride = to->stride;
  305.    u_char *tp = to->p;
  306.    int i, j;
  307.  
  308. #if 1
  309.    if (f.height > to->height)
  310.       fprintf(stderr, "f.height > to->height (%d > %d)\n",
  311.           f.height, to->height);
  312.    if (f.width > to->width)
  313.       fprintf(stderr, "f.width > to->width (%d > %d)\n",
  314.           f.width, to->width);
  315. #endif
  316.  
  317.    for (i = 0; i < f.height; i++)
  318.       for (j = 0; j < f.width; j++) {
  319.      tp[stride * i + j] =
  320.         f.pixels[f.stride * i + j].r;
  321.       }
  322. }
  323.  
  324. void
  325. image8_blit8(image8_t *from, image8_t *to)
  326. {
  327.    int w = from->width;
  328.    int h = from->height;
  329.    u_char *fp = from->p;
  330.    int fstride = from->stride;
  331.    int tstride = to->stride;
  332.    u_char *tp = to->p;
  333.    int i, j;
  334.  
  335.    for (i = 0; i < h; i++)
  336.       for (j = 0; j < w; j++)
  337.      tp[tstride * i + j] = fp[fstride * i + j];
  338. }
  339.