modules/legacy/doc/feature_detection_and_description.rst

   1 Feature Detection and Description
   2 =================================
   3
   4 .. highlight:: cpp
   5
   6 RandomizedTree
   7 --------------
   8 .. ocv:class:: RandomizedTree
   9
  10 Class containing a base structure for ``RTreeClassifier``. ::
  11
  12     class CV_EXPORTS RandomizedTree
  13     {
  14     public:
  15             friend class RTreeClassifier;
  16
  17             RandomizedTree();
  18             ~RandomizedTree();
  19
  20             void train(std::vector<BaseKeypoint> const& base_set,
  21                      RNG &rng, int depth, int views,
  22                      size_t reduced_num_dim, int num_quant_bits);
  23             void train(std::vector<BaseKeypoint> const& base_set,
  24                      RNG &rng, PatchGenerator &make_patch, int depth,
  25                      int views, size_t reduced_num_dim, int num_quant_bits);
  26
  27             // next two functions are EXPERIMENTAL
  28             //(do not use unless you know exactly what you do)
  29             static void quantizeVector(float *vec, int dim, int N, float bnds[2],
  30                      int clamp_mode=0);
  31             static void quantizeVector(float *src, int dim, int N, float bnds[2],
  32                      uchar *dst);
  33
  34             // patch_data must be a 32x32 array (no row padding)
  35             float* getPosterior(uchar* patch_data);
  36             const float* getPosterior(uchar* patch_data) const;
  37             uchar* getPosterior2(uchar* patch_data);
  38
  39             void read(const char* file_name, int num_quant_bits);
  40             void read(std::istream &is, int num_quant_bits);
  41             void write(const char* file_name) const;
  42             void write(std::ostream &os) const;
  43
  44             int classes() { return classes_; }
  45             int depth() { return depth_; }
  46
  47             void discardFloatPosteriors() { freePosteriors(1); }
  48
  49             inline void applyQuantization(int num_quant_bits)
  50                      { makePosteriors2(num_quant_bits); }
  51
  52     private:
  53             int classes_;
  54             int depth_;
  55             int num_leaves_;
  56             std::vector<RTreeNode> nodes_;
  57             float **posteriors_;        // 16-byte aligned posteriors
  58             uchar **posteriors2_;     // 16-byte aligned posteriors
  59             std::vector<int> leaf_counts_;
  60
  61             void createNodes(int num_nodes, RNG &rng);
  62             void allocPosteriorsAligned(int num_leaves, int num_classes);
  63             void freePosteriors(int which);
  64                      // which: 1=posteriors_, 2=posteriors2_, 3=both
  65             void init(int classes, int depth, RNG &rng);
  66             void addExample(int class_id, uchar* patch_data);
  67             void finalize(size_t reduced_num_dim, int num_quant_bits);
  68             int getIndex(uchar* patch_data) const;
  69             inline float* getPosteriorByIndex(int index);
  70             inline uchar* getPosteriorByIndex2(int index);
  71             inline const float* getPosteriorByIndex(int index) const;
  72             void convertPosteriorsToChar();
  73             void makePosteriors2(int num_quant_bits);
  74             void compressLeaves(size_t reduced_num_dim);
  75             void estimateQuantPercForPosteriors(float perc[2]);
  76     };
  77
  78
  79
  80 RandomizedTree::train
  81 -------------------------
  82 Trains a randomized tree using an input set of keypoints.
  83
  84 .. ocv:function:: void RandomizedTree::train( vector<BaseKeypoint> const& base_set, RNG & rng, int depth, int views, size_t reduced_num_dim, int num_quant_bits )
  85
  86 .. ocv:function:: void RandomizedTree::train( vector<BaseKeypoint> const& base_set, RNG & rng, PatchGenerator & make_patch, int depth, int views, size_t reduced_num_dim, int num_quant_bits )
  87
  88     :param base_set: Vector of the ``BaseKeypoint`` type. It contains image keypoints used for training.
  89
  90     :param rng: Random-number generator used for training.
  91
  92     :param make_patch: Patch generator used for training.
  93
  94     :param depth: Maximum tree depth.
  95
  96     :param views: Number of random views of each keypoint neighborhood to generate.
  97
  98     :param reduced_num_dim: Number of dimensions used in the compressed signature.
  99
 100     :param num_quant_bits: Number of bits used for quantization.
 101
 102
 103
 104 RandomizedTree::read
 105 ------------------------
 106 Reads a pre-saved randomized tree from a file or stream.
 107
 108 .. ocv:function:: RandomizedTree::read(const char* file_name, int num_quant_bits)
 109
 110 .. ocv:function:: RandomizedTree::read(std::istream &is, int num_quant_bits)
 111
 112     :param file_name: Name of the file that contains randomized tree data.
 113
 114     :param is: Input stream associated with the file that contains randomized tree data.
 115
 116     :param num_quant_bits: Number of bits used for quantization.
 117
 118
 119
 120 RandomizedTree::write
 121 -------------------------
 122 Writes the current randomized tree to a file or stream.
 123
 124 .. ocv:function:: void RandomizedTree::write(const char* file_name) const
 125
 126 .. ocv:function:: void RandomizedTree::write(std::ostream &os) const
 127
 128     :param file_name: Name of the file where randomized tree data is stored.
 129
 130     :param os: Output stream associated with the file where randomized tree data is stored.
 131
 132
 133
 134 RandomizedTree::applyQuantization
 135 -------------------------------------
 136 .. ocv:function:: void RandomizedTree::applyQuantization(int num_quant_bits)
 137
 138     Applies quantization to the current randomized tree.
 139
 140     :param num_quant_bits: Number of bits used for quantization.
 141
 142
 143 RTreeNode
 144 ---------
 145 .. ocv:struct:: RTreeNode
 146
 147 Class containing a base structure for ``RandomizedTree``. ::
 148
 149     struct RTreeNode
 150     {
 151             short offset1, offset2;
 152
 153             RTreeNode() {}
 154
 155             RTreeNode(uchar x1, uchar y1, uchar x2, uchar y2)
 156                     : offset1(y1*PATCH_SIZE + x1),
 157                     offset2(y2*PATCH_SIZE + x2)
 158             {}
 159
 160             //! Left child on 0, right child on 1
 161             inline bool operator() (uchar* patch_data) const
 162             {
 163                     return patch_data[offset1] > patch_data[offset2];
 164             }
 165     };
 166
 167
 168
 169 RTreeClassifier
 170 ---------------
 171 .. ocv:class:: RTreeClassifier
 172
 173 Class containing ``RTreeClassifier``. It represents the Calonder descriptor originally introduced by Michael Calonder. ::
 174
 175     class CV_EXPORTS RTreeClassifier
 176     {
 177     public:
 178             static const int DEFAULT_TREES = 48;
 179             static const size_t DEFAULT_NUM_QUANT_BITS = 4;
 180
 181             RTreeClassifier();
 182
 183             void train(std::vector<BaseKeypoint> const& base_set,
 184                     RNG &rng,
 185                     int num_trees = RTreeClassifier::DEFAULT_TREES,
 186                     int depth = DEFAULT_DEPTH,
 187                     int views = DEFAULT_VIEWS,
 188                     size_t reduced_num_dim = DEFAULT_REDUCED_NUM_DIM,
 189                     int num_quant_bits = DEFAULT_NUM_QUANT_BITS,
 190                              bool print_status = true);
 191             void train(std::vector<BaseKeypoint> const& base_set,
 192                     RNG &rng,
 193                     PatchGenerator &make_patch,
 194                     int num_trees = RTreeClassifier::DEFAULT_TREES,
 195                     int depth = DEFAULT_DEPTH,
 196                     int views = DEFAULT_VIEWS,
 197                     size_t reduced_num_dim = DEFAULT_REDUCED_NUM_DIM,
 198                     int num_quant_bits = DEFAULT_NUM_QUANT_BITS,
 199                      bool print_status = true);
 200
 201             // sig must point to a memory block of at least
 202             //classes()*sizeof(float|uchar) bytes
 203             void getSignature(IplImage *patch, uchar *sig);
 204             void getSignature(IplImage *patch, float *sig);
 205             void getSparseSignature(IplImage *patch, float *sig,
 206                      float thresh);
 207
 208             static int countNonZeroElements(float *vec, int n, double tol=1e-10);
 209             static inline void safeSignatureAlloc(uchar **sig, int num_sig=1,
 210                             int sig_len=176);
 211             static inline uchar* safeSignatureAlloc(int num_sig=1,
 212                              int sig_len=176);
 213
 214             inline int classes() { return classes_; }
 215             inline int original_num_classes()
 216                      { return original_num_classes_; }
 217
 218             void setQuantization(int num_quant_bits);
 219             void discardFloatPosteriors();
 220
 221             void read(const char* file_name);
 222             void read(std::istream &is);
 223             void write(const char* file_name) const;
 224             void write(std::ostream &os) const;
 225
 226             std::vector<RandomizedTree> trees_;
 227
 228     private:
 229             int classes_;
 230             int num_quant_bits_;
 231             uchar **posteriors_;
 232             ushort *ptemp_;
 233             int original_num_classes_;
 234             bool keep_floats_;
 235     };
 236
 237
 238
 239 RTreeClassifier::train
 240 --------------------------
 241 Trains a randomized tree classifier using an input set of keypoints.
 242
 243 .. ocv:function:: void RTreeClassifier::train( vector<BaseKeypoint> const& base_set, RNG & rng, int num_trees=RTreeClassifier::DEFAULT_TREES, int depth=RandomizedTree::DEFAULT_DEPTH, int views=RandomizedTree::DEFAULT_VIEWS, size_t reduced_num_dim=RandomizedTree::DEFAULT_REDUCED_NUM_DIM, int num_quant_bits=DEFAULT_NUM_QUANT_BITS )
 244
 245 .. ocv:function:: void RTreeClassifier::train( vector<BaseKeypoint> const& base_set, RNG & rng, PatchGenerator & make_patch, int num_trees=RTreeClassifier::DEFAULT_TREES, int depth=RandomizedTree::DEFAULT_DEPTH, int views=RandomizedTree::DEFAULT_VIEWS, size_t reduced_num_dim=RandomizedTree::DEFAULT_REDUCED_NUM_DIM, int num_quant_bits=DEFAULT_NUM_QUANT_BITS )
 246
 247     :param base_set: Vector of the ``BaseKeypoint``  type. It contains image keypoints used for training.
 248
 249     :param rng: Random-number generator used for training.
 250
 251     :param make_patch: Patch generator used for training.
 252
 253     :param num_trees: Number of randomized trees used in ``RTreeClassificator`` .
 254
 255     :param depth: Maximum tree depth.
 256
 257     :param views: Number of random views of each keypoint neighborhood to generate.
 258
 259     :param reduced_num_dim: Number of dimensions used in the compressed signature.
 260
 261     :param num_quant_bits: Number of bits used for quantization.
 262
 263
 264 RTreeClassifier::getSignature
 265 ---------------------------------
 266 Returns a signature for an image patch.
 267
 268 .. ocv:function:: void RTreeClassifier::getSignature(IplImage *patch, uchar *sig)
 269
 270 .. ocv:function:: void RTreeClassifier::getSignature(IplImage *patch, float *sig)
 271
 272     :param patch: Image patch to calculate the signature for.
 273     :param sig: Output signature (array dimension is ``reduced_num_dim)`` .
 274
 275
 276
 277 RTreeClassifier::getSparseSignature
 278 ---------------------------------------
 279 Returns a sparse signature for an image patch
 280
 281 .. ocv:function:: void RTreeClassifier::getSparseSignature(IplImage *patch, float *sig, float thresh)
 282
 283     :param patch: Image patch to calculate the signature for.
 284
 285     :param sig: Output signature (array dimension is ``reduced_num_dim)`` .
 286
 287     :param thresh: Threshold used for compressing the signature.
 288
 289     Returns a signature for an image patch similarly to ``getSignature``  but uses a threshold for removing all signature elements below the threshold so that the signature is compressed.
 290
 291
 292 RTreeClassifier::countNonZeroElements
 293 -----------------------------------------
 294 Returns the number of non-zero elements in an input array.
 295
 296 .. ocv:function:: static int RTreeClassifier::countNonZeroElements(float *vec, int n, double tol=1e-10)
 297
 298     :param vec: Input vector containing float elements.
 299
 300     :param n: Input vector size.
 301
 302     :param tol: Threshold used for counting elements. All elements less than ``tol``  are considered as zero elements.
 303
 304
 305
 306 RTreeClassifier::read
 307 -------------------------
 308 Reads a pre-saved ``RTreeClassifier`` from a file or stream.
 309
 310 .. ocv:function:: void RTreeClassifier::read(const char* file_name)
 311
 312 .. ocv:function:: void RTreeClassifier::read( std::istream & is )
 313
 314     :param file_name: Name of the file that contains randomized tree data.
 315
 316     :param is: Input stream associated with the file that contains randomized tree data.
 317
 318
 319
 320 RTreeClassifier::write
 321 --------------------------
 322 Writes the current ``RTreeClassifier`` to a file or stream.
 323
 324 .. ocv:function:: void RTreeClassifier::write(const char* file_name) const
 325
 326 .. ocv:function:: void RTreeClassifier::write(std::ostream &os) const
 327
 328     :param file_name: Name of the file where randomized tree data is stored.
 329
 330     :param os: Output stream associated with the file where randomized tree data is stored.
 331
 332
 333
 334 RTreeClassifier::setQuantization
 335 ------------------------------------
 336 Applies quantization to the current randomized tree.
 337
 338 .. ocv:function:: void RTreeClassifier::setQuantization(int num_quant_bits)
 339
 340     :param num_quant_bits: Number of bits used for quantization.
 341
 342 The example below demonstrates the usage of ``RTreeClassifier`` for matching the features. The features are extracted from the test and train images with SURF. Output is
 343 :math:`best\_corr` and
 344 :math:`best\_corr\_idx` arrays that keep the best probabilities and corresponding features indices for every train feature. ::
 345
 346     CvMemStorage* storage = cvCreateMemStorage(0);
 347     CvSeq *objectKeypoints = 0, *objectDescriptors = 0;
 348     CvSeq *imageKeypoints = 0, *imageDescriptors = 0;
 349     CvSURFParams params = cvSURFParams(500, 1);
 350     cvExtractSURF( test_image, 0, &imageKeypoints, &imageDescriptors,
 351                      storage, params );
 352     cvExtractSURF( train_image, 0, &objectKeypoints, &objectDescriptors,
 353                      storage, params );
 354
 355     RTreeClassifier detector;
 356     int patch_width = PATCH_SIZE;
 357     iint patch_height = PATCH_SIZE;
 358     vector<BaseKeypoint> base_set;
 359     int i=0;
 360     CvSURFPoint* point;
 361     for (i=0;i<(n_points > 0 ? n_points : objectKeypoints->total);i++)
 362     {
 363             point=(CvSURFPoint*)cvGetSeqElem(objectKeypoints,i);
 364             base_set.push_back(
 365                     BaseKeypoint(point->pt.x,point->pt.y,train_image));
 366     }
 367
 368             //Detector training
 369      RNG rng( cvGetTickCount() );
 370     PatchGenerator gen(0,255,2,false,0.7,1.3,-CV_PI/3,CV_PI/3,
 371                             -CV_PI/3,CV_PI/3);
 372
 373     printf("RTree Classifier training...n");
 374     detector.train(base_set,rng,gen,24,DEFAULT_DEPTH,2000,
 375             (int)base_set.size(), detector.DEFAULT_NUM_QUANT_BITS);
 376     printf("Donen");
 377
 378     float* signature = new float[detector.original_num_classes()];
 379     float* best_corr;
 380     int* best_corr_idx;
 381     if (imageKeypoints->total > 0)
 382     {
 383             best_corr = new float[imageKeypoints->total];
 384             best_corr_idx = new int[imageKeypoints->total];
 385     }
 386
 387     for(i=0; i < imageKeypoints->total; i++)
 388     {
 389             point=(CvSURFPoint*)cvGetSeqElem(imageKeypoints,i);
 390             int part_idx = -1;
 391             float prob = 0.0f;
 392
 393             CvRect roi = cvRect((int)(point->pt.x) - patch_width/2,
 394                     (int)(point->pt.y) - patch_height/2,
 395                      patch_width, patch_height);
 396             cvSetImageROI(test_image, roi);
 397             roi = cvGetImageROI(test_image);
 398             if(roi.width != patch_width || roi.height != patch_height)
 399             {
 400                     best_corr_idx[i] = part_idx;
 401                     best_corr[i] = prob;
 402             }
 403             else
 404             {
 405                     cvSetImageROI(test_image, roi);
 406                     IplImage* roi_image =
 407                              cvCreateImage(cvSize(roi.width, roi.height),
 408                              test_image->depth, test_image->nChannels);
 409                     cvCopy(test_image,roi_image);
 410
 411                     detector.getSignature(roi_image, signature);
 412                     for (int j = 0; j< detector.original_num_classes();j++)
 413                     {
 414                             if (prob < signature[j])
 415                             {
 416                                     part_idx = j;
 417                                     prob = signature[j];
 418                             }
 419                     }
 420
 421                     best_corr_idx[i] = part_idx;
 422                     best_corr[i] = prob;
 423
 424                     if (roi_image)
 425                             cvReleaseImage(&roi_image);
 426             }
 427             cvResetImageROI(test_image);
 428     }
 429
 430 ..