floodfill.c

   1 /* Copyright (C) <2010> Douglas Bagnall <douglas@halo.gen.nz>
   2  *
   3  * This library is free software; you can redistribute it and/or
   4  * modify it under the terms of the GNU Library General Public
   5  * License as published by the Free Software Foundation; either
   6  * version 2 of the License, or (at your option) any later version.
   7  *
   8  * This library is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * Library General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Library General Public
  14  * License along with this library; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 02111-1307, USA.
  17  */
  18
  19 #include "sparrow.h"
  20 #include "gstsparrow.h"
  21
  22 #include <string.h>
  23 #include <math.h>
  24
  25
  26
  27 /* Floodfill for find screen */
  28 static inline void
  29 expand_one_mono(int x, int y, int c,
  30     CvPoint *nexts, int *n_nexts, guint8 *im, guint8 *mask, int w, int h){
  31   guint8 p = im[y * w + x];
  32   guint8 *m = &mask[y * w + x];
  33   if (*m && (p == c)){
  34     *m = 0;
  35     nexts[*n_nexts].x = x;
  36     nexts[*n_nexts].y = y;
  37     (*n_nexts)++;
  38   }
  39 }
  40
  41 /*
  42   im: the image to be analysed
  43   mim: the mask image to be written
  44   start: a point of the right colour.
  45 */
  46
  47 static IplImage*
  48 floodfill_mono_superfast(IplImage *im, IplImage *mim, CvPoint start)
  49 {
  50   guint8 * data = (guint8 *)im->imageData;
  51   guint8 * mdata = (guint8 *)mim->imageData;
  52   int w = im->width;
  53   int h = im->height;
  54   int n_starts;
  55   int n_nexts = 0;
  56   CvPoint *starts;
  57   CvPoint *nexts;
  58
  59   //malloc 2 lists of points. These *could* be as large as the image (but never should be)
  60   void * mem = malloc_or_die(w * h * 2 * sizeof(CvPoint));
  61   starts = mem;
  62   nexts = starts + w * h;
  63   n_starts = 1;
  64   starts[0] = start;
  65
  66   while(n_starts){
  67     n_nexts = 0;
  68     int i;
  69     for (i = 0; i < n_starts; i++){
  70       int x = starts[i].x;
  71       int y = starts[i].y;
  72       int c = data[y * w + x];
  73       if (x > 0){
  74         expand_one_mono(x - 1, y, c, nexts, &n_nexts, data, mdata, w, h);
  75       }
  76       if (x < w - 1){
  77         expand_one_mono(x + 1, y, c, nexts, &n_nexts, data, mdata, w, h);
  78       }
  79       if (y > 0){
  80         expand_one_mono(x, y - 1, c, nexts, &n_nexts, data, mdata, w, h);
  81       }
  82       if (y < h - 1){
  83         expand_one_mono(x, y + 1, c, nexts, &n_nexts, data, mdata, w, h);
  84       }
  85     }
  86     CvPoint *tmp = starts;
  87     starts = nexts;
  88     nexts = tmp;
  89     n_starts = n_nexts;
  90   }
  91   free(mem);
  92   return im;
  93 }
  94
  95
  96
  97
  98
  99
 100 /* find a suitable threshold level by looking at the histogram of a monochrome
 101    image */
 102 static int
 103 find_edges_threshold(IplImage *im)
 104 {
 105   int w = im->width;
 106   int h = im->height;
 107   CvSize small_size = {w / 8, h / 8};
 108   IplImage *small = cvCreateImage(small_size, IPL_DEPTH_8U, 1); /*for quicker histogram (stupid, perhaps?)*/
 109   cvResize(im, small, CV_INTER_NN);
 110   int hist_size[] = {255};
 111   float range[] = {0, 255};
 112   float *ranges[] = {range};
 113   CvHistogram* hist = cvCreateHist(1, hist_size, CV_HIST_ARRAY, ranges, 1);
 114   cvCalcHist(&small, hist, 0, NULL);
 115
 116   int pixels = small->width * small->height;
 117   int min_black = pixels / 16;
 118   int max_black = pixels / 2;
 119   int totals[256] = {0};
 120
 121   int best_d = pixels + 1;
 122   int best_t = 0;
 123
 124   /* look for a low region in the histogram between the two peaks.
 125      (big assumption: two peaks, with most in whiter peak) */
 126   int total = 0;
 127   for (int i = 0; i < 255; i++){
 128     int v = (int)cvQueryHistValue_1D(hist, i);
 129     total += v;
 130     totals[i] = total;
 131     if (total >= min_black){
 132       if (i >= 5){
 133         int diff = total - totals[i - 5];
 134         if (diff < best_d){
 135           best_d = diff;
 136           best_t = i - 2;
 137         }
 138         if (total >= max_black){
 139           break;
 140         }
 141       }
 142     }
 143   }
 144   GST_DEBUG("found best threshold %d -- %d pixel change at %d/%d pixels\n",
 145       best_t, best_d, totals[best_t], pixels);
 146
 147   cvReleaseImage(&small);
 148   cvReleaseHist(&hist);
 149
 150   return best_t;
 151 }
 152
 153
 154 /* a minature state progression within this one, in case the processing is too
 155    much for one frame.*/
 156 INVISIBLE sparrow_state
 157 mode_find_screen(GstSparrow *sparrow, guint8 *in, guint8 *out){
 158   sparrow->countdown--;
 159   GST_DEBUG("in find_screen with countdown %d\n", sparrow->countdown);
 160   sparrow_find_screen_t *finder = &(sparrow->findscreen);
 161   IplImage *im = sparrow->in_ipl[0];
 162   IplImage *green = finder->green;
 163   IplImage *working = finder->working;
 164   IplImage *mask = finder->mask;
 165   /* size is 1 byte per pixel, not 4! */
 166   size_t size = sparrow->in.pixcount;
 167   CvPoint middle, corner;
 168   switch (sparrow->countdown){
 169   case 2:
 170     /* time to look and see if the screen is there.
 171        Look at the histogram of a single channel. */
 172     im->imageData = (char*)in;
 173     guint32 gshift = sparrow->in.gshift;
 174     cvSplit(im,
 175         (gshift == 24) ? green : NULL,
 176         (gshift == 16) ? green : NULL,
 177         (gshift ==  8) ? green : NULL,
 178         (gshift ==  0) ? green : NULL);
 179     int best_t = find_edges_threshold(green);
 180     /*XXX if best_t is wrong, add to sparrow->countdown: probably the light is
 181       not really on.  But what counts as wrong? */
 182     cvCmpS(green, best_t, mask, CV_CMP_GT);
 183     goto black;
 184   case 1:
 185     /* floodfill where the screen is, removing outlying bright spots*/
 186     middle = (CvPoint){sparrow->in.width / 2, sparrow->in.height / 2};
 187     memset(working->imageData, 255, size);
 188     floodfill_mono_superfast(mask, working, middle);
 189     goto black;
 190   case 0:
 191     /* floodfill the border, removing onscreen dirt.*/
 192     corner = (CvPoint){0, 0};
 193     memset(mask->imageData, 255, size);
 194     floodfill_mono_superfast(working, mask, corner);
 195     sparrow->screenmask = (guint8*)mask->imageData;
 196     sparrow->screenmask_ipl = mask;
 197     cvReleaseImage(&(finder->green));
 198     cvReleaseImage(&(finder->working));
 199     goto finish;
 200   default:
 201     /*send white and wait for the picture to arrive back. */
 202     memset(out, 255, sparrow->out.size);
 203     return SPARROW_STATUS_QUO;
 204   }
 205  black:
 206   memset(out, 0, sparrow->out.size);
 207   return SPARROW_STATUS_QUO;
 208  finish:
 209   memset(out, 0, sparrow->out.size);
 210   return SPARROW_NEXT_STATE;
 211 }
 212
 213
 214 INVISIBLE void
 215 init_find_screen(GstSparrow *sparrow){
 216   sparrow->countdown = sparrow->lag + 4;
 217   sparrow_find_screen_t *finder = &(sparrow->findscreen);
 218   CvSize size = {sparrow->in.width, sparrow->in.height};
 219   finder->green = cvCreateImage(size, IPL_DEPTH_8U, 1);
 220   finder->working = cvCreateImage(size, IPL_DEPTH_8U, 1);
 221   finder->mask = cvCreateImage(size, IPL_DEPTH_8U, 1);
 222 }