d2/image_weighted_median.h

   1 // Copyright 2002, 2003, 2004 David Hilvert <dhilvert@auricle.dyndns.org>,
   2 //                                          <dhilvert@ugcs.caltech.edu>
   3
   4 /*  This file is part of the Anti-Lamenessing Engine.
   5
   6     The Anti-Lamenessing Engine is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     The Anti-Lamenessing Engine is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with the Anti-Lamenessing Engine; if not, write to the Free Software
  18     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19 */
  20
  21 /*
  22  * image_weighted_median.h: Image representing a weighted median of inputs.
  23  */
  24
  25 #ifndef __image_weighted_median_h__
  26 #define __image_weighted_median_h__
  27
  28 #include "exposure/exposure.h"
  29 #include "point.h"
  30 #include "image.h"
  31
  32 class image_weighted_median : public image_weighted_avg {
  33 private:
  34
  35         /*
  36          * Array 'colors' stores image colors, sorted by intensity for each
  37          * channel at each pixel location.
  38          *
  39          * Array 'weights' stores the weights associated with each color, where
  40          * the weights are represented cumulatively, so that for weights and
  41          * intensities:
  42          *
  43          * Color:  1  2  3  6  7
  44          * Weight: 2  2  1  1  1
  45          *
  46          * The (cumulative) representation would be:
  47          *
  48          * Color:  1  2  3  6  7
  49          * Weight: 2  4  5  6  7
  50          *
  51          * XXX: This storage approach may have poor cache characteristics.
  52          * It might be better to localize elements having identical spatial
  53          * coordinates.
  54          */
  55         image_ale_real **colors;
  56         image_ale_real **weights;
  57         unsigned int capacity;
  58
  59 public:
  60         image_weighted_median (unsigned int dimy, unsigned int dimx, unsigned int
  61                         depth, int capacity = -1, char *name = "anonymous")
  62                         : image_weighted_avg(dimy, dimx, depth, name) {
  63
  64                 if (capacity == -1) {
  65                         this->capacity = image_rw::count();
  66                 } else if (capacity >= 0) {
  67                         this->capacity = (unsigned int) capacity;
  68                 } else
  69                         assert(0);
  70
  71                 colors  = (image_ale_real **) malloc(this->capacity * sizeof(image_ale_real *));
  72                 weights = (image_ale_real **) malloc(this->capacity * sizeof(image_ale_real *));
  73
  74                 assert(colors);
  75                 assert(weights);
  76
  77                 if (!colors || !weights) {
  78                         fprintf(stderr, "Could not allocate memory for image data.\n");
  79                         exit(1);
  80                 }
  81
  82                 for (unsigned int f = 0; f < this->capacity; f++) {
  83                         colors[f] = new image_ale_real(dimy, dimx, depth);
  84                         weights[f] = new image_ale_real(dimy, dimx, depth);
  85
  86                         assert(colors[f]);
  87                         assert(weights[f]);
  88
  89                         if (!colors[f] || !weights[f]) {
  90                                 fprintf(stderr, "Could not allocate memory for image data.\n");
  91                                 exit(1);
  92                         }
  93                 }
  94         }
  95
  96         virtual ~image_weighted_median() {
  97                 for (unsigned int f = 0; f < capacity; f++) {
  98                         delete colors[f];
  99                         delete weights[f];
 100                 }
 101
 102                 free(colors);
 103                 free(weights);
 104         }
 105
 106         /*
 107          * Extend the image area to the top, bottom, left, and right,
 108          * initializing the new image areas with black pixels.  Negative values
 109          * shrink the image.
 110          */
 111         void extend(int top, int bottom, int left, int right) {
 112
 113                 for (unsigned int f = 0; f < capacity; f++) {
 114                         colors[f]->extend(top, bottom, left, right);
 115                         weights[f]->extend(top, bottom, left, right);
 116                 }
 117
 118                 _dimx = colors[0]->width();
 119                 _dimy = colors[0]->height();
 120                 _offset = colors[0]->offset();
 121         }
 122
 123         int accumulate_norender(int i, int j) {
 124                 return 0;
 125         }
 126
 127         /*
 128          * Perform insertion sort on the arrays, where sort is by color.
 129          *
 130          * XXX: This does a poor job of handling multiple contributions from
 131          * the same frame, especially when the number of frames is 1.
 132          */
 133         void accumulate(int i, int j, int f, pixel new_value, pixel new_weight) {
 134                 for (unsigned int k = 0; k < 3; k++) {
 135
 136                         /*
 137                          * XXX: This initialization should not be necessary.
 138                          */
 139                         if (f == 0)
 140                         for (unsigned int ff = 0; ff < capacity; ff++)
 141                                 weights[ff]->pix(i, j)[k] = 0;
 142
 143                         assert (finite(new_weight[k]));
 144
 145                         if (new_weight[k] <= 0)
 146                                 continue;
 147
 148                         for (unsigned int ff = 0; ff < capacity; ff++) {
 149                                 assert (ff <= (unsigned int) f);
 150                                 if (ff == capacity - 1) {
 151                                         colors[ff]->pix(i, j)[k] = new_value[k];
 152                                         weights[ff]->pix(i, j)[k] += new_weight[k];
 153                                         break;
 154                                 }
 155                                 if ((ff == 0 && weights[ff]->pix(i, j)[k] == 0)
 156                                  || (ff >  0 && weights[ff]->pix(i, j)[k] == weights[ff - 1]->pix(i, j)[k])) {
 157                                         colors[ff]->pix(i, j)[k] = new_value[k];
 158                                         for (unsigned int fff = ff; fff < capacity; fff++)
 159                                                 weights[fff]->pix(i, j)[k] += new_weight[k];
 160                                         break;
 161                                 }
 162                                 if (colors[ff]->pix(i, j)[k] == new_value[k]) {
 163                                         for (unsigned int fff = ff; fff < capacity; fff++)
 164                                                 weights[fff]->pix(i, j)[k] += new_weight[k];
 165                                         break;
 166                                 }
 167                                 if (colors[ff]->pix(i, j)[k] > new_value[k]) {
 168                                         for (unsigned int fff = capacity - 1; fff > ff; fff--) {
 169                                                 weights[fff]->pix(i, j)[k] = weights[fff - 1]->pix(i, j)[k] + new_weight[k];
 170                                                 colors[fff]->pix(i, j)[k]  = colors[fff - 1]->pix(i, j)[k];
 171                                         }
 172                                         colors[ff]->pix(i, j)[k] = new_value[k];
 173                                         weights[ff]->pix(i, j)[k] = new_weight[k];
 174                                         if (ff > 0)
 175                                                 weights[ff]->pix(i, j)[k] += weights[ff - 1]->pix(i, j)[k];
 176
 177                                         break;
 178                                 }
 179                         }
 180                 }
 181         }
 182
 183         /*
 184          * XXX: This is inefficient in cases where only one channel is desired.
 185          */
 186         pixel get_pixel(unsigned int y, unsigned int x) const {
 187                 pixel result;
 188
 189                 for (int k = 0; k < 3; k++) {
 190                         ale_real midpoint = weights[capacity - 1]->chan(y, x, k) / 2;
 191
 192                         if (midpoint == 0)
 193                                 return pixel::zero();
 194
 195                         /*
 196                          * Binary search.
 197                          */
 198
 199                         unsigned int l = 0;
 200                         unsigned int h = capacity - 1;
 201                         unsigned int m = h / 2;
 202
 203                         while (h > l + 1) {
 204                                 if (weights[m]->chan(y, x, k) < midpoint)
 205                                         l = m;
 206                                 else
 207                                         h = m;
 208                                 m = (h + l) / 2;
 209                         }
 210
 211                         if (weights[l]->chan(y, x, k) < midpoint)
 212                                 l = h;
 213                         if (weights[l]->chan(y, x, k) > midpoint)
 214                                 result[k] = colors[l]->chan(y, x, k);
 215                         else if (weights[l]->chan(y, x, k) == midpoint)
 216                                 result[k] = (colors[l]->chan(y, x, k)
 217                                            + colors[l + 1]->chan(y, x, k)) / 2;
 218                         else
 219                                 assert(0);
 220
 221                 }
 222
 223                 return result;
 224         }
 225
 226         image *get_weights() {
 227                 return weights[capacity - 1];
 228         }
 229
 230         image *get_colors() {
 231                 return this;
 232         }
 233
 234 };
 235
 236 #endif