modules/video/src/bgfg_gmg.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   5 //  By downloading, copying, installing or using the software you agree to this license.
   6 //  If you do not agree to this license, do not download, install,
   7 //  copy or use the software.
   8 //
   9 //
  10 //                          License Agreement
  11 //
  12 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  13 // Third party copyrights are property of their respective owners.
  14 //
  15 // Redistribution and use in source and binary forms, with or without modification,
  16 // are permitted provided that the following conditions are met:
  17 //
  18 //   * Redistribution's of source code must retain the above copyright notice,
  19 //     this list of conditions and the following disclaimer.
  20 //
  21 //   * Redistribution's in binary form must reproduce the above copyright notice,
  22 //     this list of conditions and the following disclaimer in the documentation
  23 //     and/or other materials provided with the distribution.
  24 //
  25 //   * The name of Intel Corporation may not be used to endorse or promote products
  26 //     derived from this software without specific prior written permission.
  27 //
  28 // This software is provided by the copyright holders and contributors "as is" and
  29 // any express or implied warranties, including, but not limited to, the implied
  30 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  31 // In no event shall the Intel Corporation or contributors be liable for any direct,
  32 // indirect, incidental, special, exemplary, or consequential damages
  33 // (including, but not limited to, procurement of substitute goods or services;
  34 // loss of use, data, or profits; or business interruption) however caused
  35 // and on any theory of liability, whether in contract, strict liability,
  36 // or tort (including negligence or otherwise) arising in any way out of
  37 // the use of this software, even if advised of the possibility of such damage.
  38 //
  39 //M*/
  40
  41 /*
  42  * This class implements an algorithm described in "Visual Tracking of Human Visitors under
  43  * Variable-Lighting Conditions for a Responsive Audio Art Installation," A. Godbehere,
  44  * A. Matsukawa, K. Goldberg, American Control Conference, Montreal, June 2012.
  45  *
  46  * Prepared and integrated by Andrew B. Godbehere.
  47  */
  48
  49 #include "precomp.hpp"
  50
  51 cv::BackgroundSubtractorGMG::BackgroundSubtractorGMG()
  52 {
  53     /*
  54      * Default Parameter Values. Override with algorithm "set" method.
  55      */
  56     maxFeatures = 64;
  57     learningRate = 0.025;
  58     numInitializationFrames = 120;
  59     quantizationLevels = 16;
  60     backgroundPrior = 0.8;
  61     decisionThreshold = 0.8;
  62     smoothingRadius = 7;
  63 }
  64
  65 cv::BackgroundSubtractorGMG::~BackgroundSubtractorGMG()
  66 {
  67 }
  68
  69 void cv::BackgroundSubtractorGMG::initialize(cv::Size frameSize, double min, double max)
  70 {
  71     CV_Assert(min < max);
  72     CV_Assert(maxFeatures > 0);
  73     CV_Assert(learningRate >= 0.0 && learningRate <= 1.0);
  74     CV_Assert(numInitializationFrames >= 1);
  75     CV_Assert(quantizationLevels >= 1 && quantizationLevels <= 255);
  76     CV_Assert(backgroundPrior >= 0.0 && backgroundPrior <= 1.0);
  77
  78     minVal_ = min;
  79     maxVal_ = max;
  80
  81     frameSize_ = frameSize;
  82     frameNum_ = 0;
  83
  84     nfeatures_.create(frameSize_);
  85     colors_.create(frameSize_.area(), maxFeatures);
  86     weights_.create(frameSize_.area(), maxFeatures);
  87
  88     nfeatures_.setTo(cv::Scalar::all(0));
  89 }
  90
  91 namespace
  92 {
  93     float findFeature(int color, const int* colors, const float* weights, int nfeatures)
  94     {
  95         for (int i = 0; i < nfeatures; ++i)
  96         {
  97             if (color == colors[i])
  98                 return weights[i];
  99         }
 100
 101         // not in histogram, so return 0.
 102         return 0.0f;
 103     }
 104
 105     void normalizeHistogram(float* weights, int nfeatures)
 106     {
 107         float total = 0.0f;
 108         for (int i = 0; i < nfeatures; ++i)
 109             total += weights[i];
 110
 111         if (total != 0.0f)
 112         {
 113             for (int i = 0; i < nfeatures; ++i)
 114                 weights[i] /= total;
 115         }
 116     }
 117
 118     bool insertFeature(int color, float weight, int* colors, float* weights, int& nfeatures, int maxFeatures)
 119     {
 120         int idx = -1;
 121         for (int i = 0; i < nfeatures; ++i)
 122         {
 123             if (color == colors[i])
 124             {
 125                 // feature in histogram
 126                 weight += weights[i];
 127                 idx = i;
 128                 break;
 129             }
 130         }
 131
 132         if (idx >= 0)
 133         {
 134             // move feature to beginning of list
 135
 136             ::memmove(colors + 1, colors, idx * sizeof(int));
 137             ::memmove(weights + 1, weights, idx * sizeof(float));
 138
 139             colors[0] = color;
 140             weights[0] = weight;
 141         }
 142         else if (nfeatures == maxFeatures)
 143         {
 144             // discard oldest feature
 145
 146             ::memmove(colors + 1, colors, (nfeatures - 1) * sizeof(int));
 147             ::memmove(weights + 1, weights, (nfeatures - 1) * sizeof(float));
 148
 149             colors[0] = color;
 150             weights[0] = weight;
 151         }
 152         else
 153         {
 154             colors[nfeatures] = color;
 155             weights[nfeatures] = weight;
 156
 157             ++nfeatures;
 158
 159             return true;
 160         }
 161
 162         return false;
 163     }
 164 }
 165
 166 namespace
 167 {
 168     template <int cn> struct Quantization_
 169     {
 170         template <typename T>
 171         static inline int apply(T val, double minVal, double maxVal, int quantizationLevels)
 172         {
 173             int res = 0;
 174             res |= static_cast<int>((val[0] - minVal) * quantizationLevels / (maxVal - minVal));
 175             res |= static_cast<int>((val[1] - minVal) * quantizationLevels / (maxVal - minVal)) << 8;
 176             res |= static_cast<int>((val[2] - minVal) * quantizationLevels / (maxVal - minVal)) << 16;
 177             return res;
 178         }
 179     };
 180     template <> struct Quantization_<1>
 181     {
 182         template <typename T>
 183         static inline int apply(T val, double minVal, double maxVal, int quantizationLevels)
 184         {
 185             return static_cast<int>((val - minVal) * quantizationLevels / (maxVal - minVal));
 186         }
 187     };
 188     template <typename T> struct Quantization
 189     {
 190         static int apply(const void* src_, int x, double minVal, double maxVal, int quantizationLevels)
 191         {
 192             const T* src = static_cast<const T*>(src_);
 193             return Quantization_<cv::DataType<T>::channels>::apply(src[x], minVal, maxVal, quantizationLevels);
 194         }
 195     };
 196
 197     class GMG_LoopBody : public cv::ParallelLoopBody
 198     {
 199     public:
 200         GMG_LoopBody(const cv::Mat& frame, const cv::Mat& fgmask, const cv::Mat_<int>& nfeatures, const cv::Mat_<int>& colors, const cv::Mat_<float>& weights,
 201                      int maxFeatures, double learningRate, int numInitializationFrames, int quantizationLevels, double backgroundPrior, double decisionThreshold,
 202                      double maxVal, double minVal, int frameNum) :
 203             frame_(frame), fgmask_(fgmask), nfeatures_(nfeatures), colors_(colors), weights_(weights),
 204             maxFeatures_(maxFeatures), learningRate_(learningRate), numInitializationFrames_(numInitializationFrames),
 205             quantizationLevels_(quantizationLevels), backgroundPrior_(backgroundPrior), decisionThreshold_(decisionThreshold),
 206             maxVal_(maxVal), minVal_(minVal), frameNum_(frameNum)
 207         {
 208         }
 209
 210         void operator() (const cv::Range& range) const;
 211
 212     private:
 213         const cv::Mat frame_;
 214
 215         mutable cv::Mat_<uchar> fgmask_;
 216
 217         mutable cv::Mat_<int> nfeatures_;
 218         mutable cv::Mat_<int> colors_;
 219         mutable cv::Mat_<float> weights_;
 220
 221         int     maxFeatures_;
 222         double  learningRate_;
 223         int     numInitializationFrames_;
 224         int     quantizationLevels_;
 225         double  backgroundPrior_;
 226         double  decisionThreshold_;
 227
 228         double maxVal_;
 229         double minVal_;
 230         int frameNum_;
 231     };
 232
 233     void GMG_LoopBody::operator() (const cv::Range& range) const
 234     {
 235         typedef int (*func_t)(const void* src_, int x, double minVal, double maxVal, int quantizationLevels);
 236         static const func_t funcs[6][4] =
 237         {
 238             {Quantization<uchar>::apply, 0, Quantization<cv::Vec3b>::apply, Quantization<cv::Vec4b>::apply},
 239             {0,0,0,0},
 240             {Quantization<ushort>::apply, 0, Quantization<cv::Vec3w>::apply, Quantization<cv::Vec4w>::apply},
 241             {0,0,0,0},
 242             {0,0,0,0},
 243             {Quantization<float>::apply, 0, Quantization<cv::Vec3f>::apply, Quantization<cv::Vec4f>::apply},
 244         };
 245
 246         const func_t func = funcs[frame_.depth()][frame_.channels() - 1];
 247         CV_Assert(func != 0);
 248
 249         for (int y = range.start, featureIdx = y * frame_.cols; y < range.end; ++y)
 250         {
 251             const uchar* frame_row = frame_.ptr(y);
 252             int* nfeatures_row = nfeatures_[y];
 253             uchar* fgmask_row = fgmask_[y];
 254
 255             for (int x = 0; x < frame_.cols; ++x, ++featureIdx)
 256             {
 257                 int nfeatures = nfeatures_row[x];
 258                 int* colors = colors_[featureIdx];
 259                 float* weights = weights_[featureIdx];
 260
 261                 int newFeatureColor = func(frame_row, x, minVal_, maxVal_, quantizationLevels_);
 262
 263                 bool isForeground = false;
 264
 265                 if (frameNum_ >= numInitializationFrames_)
 266                 {
 267                     // typical operation
 268
 269                     const double weight = findFeature(newFeatureColor, colors, weights, nfeatures);
 270
 271                     // see Godbehere, Matsukawa, Goldberg (2012) for reasoning behind this implementation of Bayes rule
 272                     const double posterior = (weight * backgroundPrior_) / (weight * backgroundPrior_ + (1.0 - weight) * (1.0 - backgroundPrior_));
 273
 274                     isForeground = ((1.0 - posterior) > decisionThreshold_);
 275
 276                     // update histogram.
 277
 278                     for (int i = 0; i < nfeatures; ++i)
 279                         weights[i] *= 1.0f - learningRate_;
 280
 281                     bool inserted = insertFeature(newFeatureColor, learningRate_, colors, weights, nfeatures, maxFeatures_);
 282
 283                     if (inserted)
 284                     {
 285                         normalizeHistogram(weights, nfeatures);
 286                         nfeatures_row[x] = nfeatures;
 287                     }
 288                 }
 289                 else
 290                 {
 291                     // training-mode update
 292
 293                     insertFeature(newFeatureColor, 1.0f, colors, weights, nfeatures, maxFeatures_);
 294
 295                     if (frameNum_ == numInitializationFrames_ - 1)
 296                         normalizeHistogram(weights, nfeatures);
 297                 }
 298
 299                 fgmask_row[x] = (uchar)(-isForeground);
 300             }
 301         }
 302     }
 303 }
 304
 305 void cv::BackgroundSubtractorGMG::operator ()(InputArray _frame, OutputArray _fgmask, double newLearningRate)
 306 {
 307     cv::Mat frame = _frame.getMat();
 308
 309     CV_Assert(frame.depth() == CV_8U || frame.depth() == CV_16U || frame.depth() == CV_32F);
 310     CV_Assert(frame.channels() == 1 || frame.channels() == 3 || frame.channels() == 4);
 311
 312     if (newLearningRate != -1.0)
 313     {
 314         CV_Assert(newLearningRate >= 0.0 && newLearningRate <= 1.0);
 315         learningRate = newLearningRate;
 316     }
 317
 318     if (frame.size() != frameSize_)
 319         initialize(frame.size(), 0.0, frame.depth() == CV_8U ? 255.0 : frame.depth() == CV_16U ? std::numeric_limits<ushort>::max() : 1.0);
 320
 321     _fgmask.create(frameSize_, CV_8UC1);
 322     cv::Mat fgmask = _fgmask.getMat();
 323
 324     GMG_LoopBody body(frame, fgmask, nfeatures_, colors_, weights_,
 325                       maxFeatures, learningRate, numInitializationFrames, quantizationLevels, backgroundPrior, decisionThreshold,
 326                       maxVal_, minVal_, frameNum_);
 327     cv::parallel_for_(cv::Range(0, frame.rows), body);
 328
 329     cv::medianBlur(fgmask, buf_, smoothingRadius);
 330     cv::swap(fgmask, buf_);
 331
 332     // keep track of how many frames we have processed
 333     ++frameNum_;
 334 }