modules/features2d/src/orb.cpp

   1 /*********************************************************************
   2 * Software License Agreement (BSD License)
   3 *
   4 *  Copyright (c) 2009, Willow Garage, Inc.
   5 *  All rights reserved.
   6 *
   7 *  Redistribution and use in source and binary forms, with or without
   8 *  modification, are permitted provided that the following conditions
   9 *  are met:
  10 *
  11 *   * Redistributions of source code must retain the above copyright
  12 *     notice, this list of conditions and the following disclaimer.
  13 *   * Redistributions in binary form must reproduce the above
  14 *     copyright notice, this list of conditions and the following
  15 *     disclaimer in the documentation and/or other materials provided
  16 *     with the distribution.
  17 *   * Neither the name of the Willow Garage nor the names of its
  18 *     contributors may be used to endorse or promote products derived
  19 *     from this software without specific prior written permission.
  20 *
  21 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32 *  POSSIBILITY OF SUCH DAMAGE.
  33 *********************************************************************/
  34
  35 /** Authors: Ethan Rublee, Vincent Rabaud, Gary Bradski */
  36
  37 #include "precomp.hpp"
  38 #include "opencl_kernels_features2d.hpp"
  39 #include <iterator>
  40
  41 #ifndef CV_IMPL_ADD
  42 #define CV_IMPL_ADD(x)
  43 #endif
  44
  45 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  46
  47 namespace cv
  48 {
  49
  50 const float HARRIS_K = 0.04f;
  51
  52 template<typename _Tp> inline void copyVectorToUMat(const std::vector<_Tp>& v, OutputArray um)
  53 {
  54     if(v.empty())
  55         um.release();
  56     else
  57         Mat(1, (int)(v.size()*sizeof(v[0])), CV_8U, (void*)&v[0]).copyTo(um);
  58 }
  59
  60 #ifdef HAVE_OPENCL
  61 static bool
  62 ocl_HarrisResponses(const UMat& imgbuf,
  63                     const UMat& layerinfo,
  64                     const UMat& keypoints,
  65                     UMat& responses,
  66                     int nkeypoints, int blockSize, float harris_k)
  67 {
  68     size_t globalSize[] = {(size_t)nkeypoints};
  69
  70     float scale = 1.f/((1 << 2) * blockSize * 255.f);
  71     float scale_sq_sq = scale * scale * scale * scale;
  72
  73     ocl::Kernel hr_ker("ORB_HarrisResponses", ocl::features2d::orb_oclsrc,
  74                 format("-D ORB_RESPONSES -D blockSize=%d -D scale_sq_sq=%.12ef -D HARRIS_K=%.12ff", blockSize, scale_sq_sq, harris_k));
  75     if( hr_ker.empty() )
  76         return false;
  77
  78     return hr_ker.args(ocl::KernelArg::ReadOnlyNoSize(imgbuf),
  79                 ocl::KernelArg::PtrReadOnly(layerinfo),
  80                 ocl::KernelArg::PtrReadOnly(keypoints),
  81                 ocl::KernelArg::PtrWriteOnly(responses),
  82                 nkeypoints).run(1, globalSize, 0, true);
  83 }
  84
  85 static bool
  86 ocl_ICAngles(const UMat& imgbuf, const UMat& layerinfo,
  87              const UMat& keypoints, UMat& responses,
  88              const UMat& umax, int nkeypoints, int half_k)
  89 {
  90     size_t globalSize[] = {(size_t)nkeypoints};
  91
  92     ocl::Kernel icangle_ker("ORB_ICAngle", ocl::features2d::orb_oclsrc, "-D ORB_ANGLES");
  93     if( icangle_ker.empty() )
  94         return false;
  95
  96     return icangle_ker.args(ocl::KernelArg::ReadOnlyNoSize(imgbuf),
  97                 ocl::KernelArg::PtrReadOnly(layerinfo),
  98                 ocl::KernelArg::PtrReadOnly(keypoints),
  99                 ocl::KernelArg::PtrWriteOnly(responses),
 100                 ocl::KernelArg::PtrReadOnly(umax),
 101                 nkeypoints, half_k).run(1, globalSize, 0, true);
 102 }
 103
 104
 105 static bool
 106 ocl_computeOrbDescriptors(const UMat& imgbuf, const UMat& layerInfo,
 107                           const UMat& keypoints, UMat& desc, const UMat& pattern,
 108                           int nkeypoints, int dsize, int wta_k)
 109 {
 110     size_t globalSize[] = {(size_t)nkeypoints};
 111
 112     ocl::Kernel desc_ker("ORB_computeDescriptor", ocl::features2d::orb_oclsrc,
 113                          format("-D ORB_DESCRIPTORS -D WTA_K=%d", wta_k));
 114     if( desc_ker.empty() )
 115         return false;
 116
 117     return desc_ker.args(ocl::KernelArg::ReadOnlyNoSize(imgbuf),
 118                          ocl::KernelArg::PtrReadOnly(layerInfo),
 119                          ocl::KernelArg::PtrReadOnly(keypoints),
 120                          ocl::KernelArg::PtrWriteOnly(desc),
 121                          ocl::KernelArg::PtrReadOnly(pattern),
 122                          nkeypoints, dsize).run(1, globalSize, 0, true);
 123 }
 124 #endif
 125
 126 /**
 127  * Function that computes the Harris responses in a
 128  * blockSize x blockSize patch at given points in the image
 129  */
 130 static void
 131 HarrisResponses(const Mat& img, const std::vector<Rect>& layerinfo,
 132                 std::vector<KeyPoint>& pts, int blockSize, float harris_k)
 133 {
 134     CV_Assert( img.type() == CV_8UC1 && blockSize*blockSize <= 2048 );
 135
 136     size_t ptidx, ptsize = pts.size();
 137
 138     const uchar* ptr00 = img.ptr<uchar>();
 139     int step = (int)(img.step/img.elemSize1());
 140     int r = blockSize/2;
 141
 142     float scale = 1.f/((1 << 2) * blockSize * 255.f);
 143     float scale_sq_sq = scale * scale * scale * scale;
 144
 145     AutoBuffer<int> ofsbuf(blockSize*blockSize);
 146     int* ofs = ofsbuf.data();
 147     for( int i = 0; i < blockSize; i++ )
 148         for( int j = 0; j < blockSize; j++ )
 149             ofs[i*blockSize + j] = (int)(i*step + j);
 150
 151     for( ptidx = 0; ptidx < ptsize; ptidx++ )
 152     {
 153         int x0 = cvRound(pts[ptidx].pt.x);
 154         int y0 = cvRound(pts[ptidx].pt.y);
 155         int z = pts[ptidx].octave;
 156
 157         const uchar* ptr0 = ptr00 + (y0 - r + layerinfo[z].y)*step + x0 - r + layerinfo[z].x;
 158         int a = 0, b = 0, c = 0;
 159
 160         for( int k = 0; k < blockSize*blockSize; k++ )
 161         {
 162             const uchar* ptr = ptr0 + ofs[k];
 163             int Ix = (ptr[1] - ptr[-1])*2 + (ptr[-step+1] - ptr[-step-1]) + (ptr[step+1] - ptr[step-1]);
 164             int Iy = (ptr[step] - ptr[-step])*2 + (ptr[step-1] - ptr[-step-1]) + (ptr[step+1] - ptr[-step+1]);
 165             a += Ix*Ix;
 166             b += Iy*Iy;
 167             c += Ix*Iy;
 168         }
 169         pts[ptidx].response = ((float)a * b - (float)c * c -
 170                                harris_k * ((float)a + b) * ((float)a + b))*scale_sq_sq;
 171     }
 172 }
 173
 174 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 175
 176 static void ICAngles(const Mat& img, const std::vector<Rect>& layerinfo,
 177                      std::vector<KeyPoint>& pts, const std::vector<int> & u_max, int half_k)
 178 {
 179     int step = (int)img.step1();
 180     size_t ptidx, ptsize = pts.size();
 181
 182     for( ptidx = 0; ptidx < ptsize; ptidx++ )
 183     {
 184         const Rect& layer = layerinfo[pts[ptidx].octave];
 185         const uchar* center = &img.at<uchar>(cvRound(pts[ptidx].pt.y) + layer.y, cvRound(pts[ptidx].pt.x) + layer.x);
 186
 187         int m_01 = 0, m_10 = 0;
 188
 189         // Treat the center line differently, v=0
 190         for (int u = -half_k; u <= half_k; ++u)
 191             m_10 += u * center[u];
 192
 193         // Go line by line in the circular patch
 194         for (int v = 1; v <= half_k; ++v)
 195         {
 196             // Proceed over the two lines
 197             int v_sum = 0;
 198             int d = u_max[v];
 199             for (int u = -d; u <= d; ++u)
 200             {
 201                 int val_plus = center[u + v*step], val_minus = center[u - v*step];
 202                 v_sum += (val_plus - val_minus);
 203                 m_10 += u * (val_plus + val_minus);
 204             }
 205             m_01 += v * v_sum;
 206         }
 207
 208         pts[ptidx].angle = fastAtan2((float)m_01, (float)m_10);
 209     }
 210 }
 211
 212 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 213
 214 static void
 215 computeOrbDescriptors( const Mat& imagePyramid, const std::vector<Rect>& layerInfo,
 216                        const std::vector<float>& layerScale, std::vector<KeyPoint>& keypoints,
 217                        Mat& descriptors, const std::vector<Point>& _pattern, int dsize, int wta_k )
 218 {
 219     int step = (int)imagePyramid.step;
 220     int j, i, nkeypoints = (int)keypoints.size();
 221
 222     for( j = 0; j < nkeypoints; j++ )
 223     {
 224         const KeyPoint& kpt = keypoints[j];
 225         const Rect& layer = layerInfo[kpt.octave];
 226         float scale = 1.f/layerScale[kpt.octave];
 227         float angle = kpt.angle;
 228
 229         angle *= (float)(CV_PI/180.f);
 230         float a = (float)cos(angle), b = (float)sin(angle);
 231
 232         const uchar* center = &imagePyramid.at<uchar>(cvRound(kpt.pt.y*scale) + layer.y,
 233                                                       cvRound(kpt.pt.x*scale) + layer.x);
 234         float x, y;
 235         int ix, iy;
 236         const Point* pattern = &_pattern[0];
 237         uchar* desc = descriptors.ptr<uchar>(j);
 238
 239     #if 1
 240         #define GET_VALUE(idx) \
 241                (x = pattern[idx].x*a - pattern[idx].y*b, \
 242                 y = pattern[idx].x*b + pattern[idx].y*a, \
 243                 ix = cvRound(x), \
 244                 iy = cvRound(y), \
 245                 *(center + iy*step + ix) )
 246     #else
 247         #define GET_VALUE(idx) \
 248             (x = pattern[idx].x*a - pattern[idx].y*b, \
 249             y = pattern[idx].x*b + pattern[idx].y*a, \
 250             ix = cvFloor(x), iy = cvFloor(y), \
 251             x -= ix, y -= iy, \
 252             cvRound(center[iy*step + ix]*(1-x)*(1-y) + center[(iy+1)*step + ix]*(1-x)*y + \
 253                     center[iy*step + ix+1]*x*(1-y) + center[(iy+1)*step + ix+1]*x*y))
 254     #endif
 255
 256         if( wta_k == 2 )
 257         {
 258             for (i = 0; i < dsize; ++i, pattern += 16)
 259             {
 260                 int t0, t1, val;
 261                 t0 = GET_VALUE(0); t1 = GET_VALUE(1);
 262                 val = t0 < t1;
 263                 t0 = GET_VALUE(2); t1 = GET_VALUE(3);
 264                 val |= (t0 < t1) << 1;
 265                 t0 = GET_VALUE(4); t1 = GET_VALUE(5);
 266                 val |= (t0 < t1) << 2;
 267                 t0 = GET_VALUE(6); t1 = GET_VALUE(7);
 268                 val |= (t0 < t1) << 3;
 269                 t0 = GET_VALUE(8); t1 = GET_VALUE(9);
 270                 val |= (t0 < t1) << 4;
 271                 t0 = GET_VALUE(10); t1 = GET_VALUE(11);
 272                 val |= (t0 < t1) << 5;
 273                 t0 = GET_VALUE(12); t1 = GET_VALUE(13);
 274                 val |= (t0 < t1) << 6;
 275                 t0 = GET_VALUE(14); t1 = GET_VALUE(15);
 276                 val |= (t0 < t1) << 7;
 277
 278                 desc[i] = (uchar)val;
 279             }
 280         }
 281         else if( wta_k == 3 )
 282         {
 283             for (i = 0; i < dsize; ++i, pattern += 12)
 284             {
 285                 int t0, t1, t2, val;
 286                 t0 = GET_VALUE(0); t1 = GET_VALUE(1); t2 = GET_VALUE(2);
 287                 val = t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0);
 288
 289                 t0 = GET_VALUE(3); t1 = GET_VALUE(4); t2 = GET_VALUE(5);
 290                 val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 2;
 291
 292                 t0 = GET_VALUE(6); t1 = GET_VALUE(7); t2 = GET_VALUE(8);
 293                 val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 4;
 294
 295                 t0 = GET_VALUE(9); t1 = GET_VALUE(10); t2 = GET_VALUE(11);
 296                 val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 6;
 297
 298                 desc[i] = (uchar)val;
 299             }
 300         }
 301         else if( wta_k == 4 )
 302         {
 303             for (i = 0; i < dsize; ++i, pattern += 16)
 304             {
 305                 int t0, t1, t2, t3, u, v, k, val;
 306                 t0 = GET_VALUE(0); t1 = GET_VALUE(1);
 307                 t2 = GET_VALUE(2); t3 = GET_VALUE(3);
 308                 u = 0, v = 2;
 309                 if( t1 > t0 ) t0 = t1, u = 1;
 310                 if( t3 > t2 ) t2 = t3, v = 3;
 311                 k = t0 > t2 ? u : v;
 312                 val = k;
 313
 314                 t0 = GET_VALUE(4); t1 = GET_VALUE(5);
 315                 t2 = GET_VALUE(6); t3 = GET_VALUE(7);
 316                 u = 0, v = 2;
 317                 if( t1 > t0 ) t0 = t1, u = 1;
 318                 if( t3 > t2 ) t2 = t3, v = 3;
 319                 k = t0 > t2 ? u : v;
 320                 val |= k << 2;
 321
 322                 t0 = GET_VALUE(8); t1 = GET_VALUE(9);
 323                 t2 = GET_VALUE(10); t3 = GET_VALUE(11);
 324                 u = 0, v = 2;
 325                 if( t1 > t0 ) t0 = t1, u = 1;
 326                 if( t3 > t2 ) t2 = t3, v = 3;
 327                 k = t0 > t2 ? u : v;
 328                 val |= k << 4;
 329
 330                 t0 = GET_VALUE(12); t1 = GET_VALUE(13);
 331                 t2 = GET_VALUE(14); t3 = GET_VALUE(15);
 332                 u = 0, v = 2;
 333                 if( t1 > t0 ) t0 = t1, u = 1;
 334                 if( t3 > t2 ) t2 = t3, v = 3;
 335                 k = t0 > t2 ? u : v;
 336                 val |= k << 6;
 337
 338                 desc[i] = (uchar)val;
 339             }
 340         }
 341         else
 342             CV_Error( Error::StsBadSize, "Wrong wta_k. It can be only 2, 3 or 4." );
 343         #undef GET_VALUE
 344     }
 345 }
 346
 347
 348 static void initializeOrbPattern( const Point* pattern0, std::vector<Point>& pattern, int ntuples, int tupleSize, int poolSize )
 349 {
 350     RNG rng(0x12345678);
 351     int i, k, k1;
 352     pattern.resize(ntuples*tupleSize);
 353
 354     for( i = 0; i < ntuples; i++ )
 355     {
 356         for( k = 0; k < tupleSize; k++ )
 357         {
 358             for(;;)
 359             {
 360                 int idx = rng.uniform(0, poolSize);
 361                 Point pt = pattern0[idx];
 362                 for( k1 = 0; k1 < k; k1++ )
 363                     if( pattern[tupleSize*i + k1] == pt )
 364                         break;
 365                 if( k1 == k )
 366                 {
 367                     pattern[tupleSize*i + k] = pt;
 368                     break;
 369                 }
 370             }
 371         }
 372     }
 373 }
 374
 375 static int bit_pattern_31_[256*4] =
 376 {
 377     8,-3, 9,5/*mean (0), correlation (0)*/,
 378     4,2, 7,-12/*mean (1.12461e-05), correlation (0.0437584)*/,
 379     -11,9, -8,2/*mean (3.37382e-05), correlation (0.0617409)*/,
 380     7,-12, 12,-13/*mean (5.62303e-05), correlation (0.0636977)*/,
 381     2,-13, 2,12/*mean (0.000134953), correlation (0.085099)*/,
 382     1,-7, 1,6/*mean (0.000528565), correlation (0.0857175)*/,
 383     -2,-10, -2,-4/*mean (0.0188821), correlation (0.0985774)*/,
 384     -13,-13, -11,-8/*mean (0.0363135), correlation (0.0899616)*/,
 385     -13,-3, -12,-9/*mean (0.121806), correlation (0.099849)*/,
 386     10,4, 11,9/*mean (0.122065), correlation (0.093285)*/,
 387     -13,-8, -8,-9/*mean (0.162787), correlation (0.0942748)*/,
 388     -11,7, -9,12/*mean (0.21561), correlation (0.0974438)*/,
 389     7,7, 12,6/*mean (0.160583), correlation (0.130064)*/,
 390     -4,-5, -3,0/*mean (0.228171), correlation (0.132998)*/,
 391     -13,2, -12,-3/*mean (0.00997526), correlation (0.145926)*/,
 392     -9,0, -7,5/*mean (0.198234), correlation (0.143636)*/,
 393     12,-6, 12,-1/*mean (0.0676226), correlation (0.16689)*/,
 394     -3,6, -2,12/*mean (0.166847), correlation (0.171682)*/,
 395     -6,-13, -4,-8/*mean (0.101215), correlation (0.179716)*/,
 396     11,-13, 12,-8/*mean (0.200641), correlation (0.192279)*/,
 397     4,7, 5,1/*mean (0.205106), correlation (0.186848)*/,
 398     5,-3, 10,-3/*mean (0.234908), correlation (0.192319)*/,
 399     3,-7, 6,12/*mean (0.0709964), correlation (0.210872)*/,
 400     -8,-7, -6,-2/*mean (0.0939834), correlation (0.212589)*/,
 401     -2,11, -1,-10/*mean (0.127778), correlation (0.20866)*/,
 402     -13,12, -8,10/*mean (0.14783), correlation (0.206356)*/,
 403     -7,3, -5,-3/*mean (0.182141), correlation (0.198942)*/,
 404     -4,2, -3,7/*mean (0.188237), correlation (0.21384)*/,
 405     -10,-12, -6,11/*mean (0.14865), correlation (0.23571)*/,
 406     5,-12, 6,-7/*mean (0.222312), correlation (0.23324)*/,
 407     5,-6, 7,-1/*mean (0.229082), correlation (0.23389)*/,
 408     1,0, 4,-5/*mean (0.241577), correlation (0.215286)*/,
 409     9,11, 11,-13/*mean (0.00338507), correlation (0.251373)*/,
 410     4,7, 4,12/*mean (0.131005), correlation (0.257622)*/,
 411     2,-1, 4,4/*mean (0.152755), correlation (0.255205)*/,
 412     -4,-12, -2,7/*mean (0.182771), correlation (0.244867)*/,
 413     -8,-5, -7,-10/*mean (0.186898), correlation (0.23901)*/,
 414     4,11, 9,12/*mean (0.226226), correlation (0.258255)*/,
 415     0,-8, 1,-13/*mean (0.0897886), correlation (0.274827)*/,
 416     -13,-2, -8,2/*mean (0.148774), correlation (0.28065)*/,
 417     -3,-2, -2,3/*mean (0.153048), correlation (0.283063)*/,
 418     -6,9, -4,-9/*mean (0.169523), correlation (0.278248)*/,
 419     8,12, 10,7/*mean (0.225337), correlation (0.282851)*/,
 420     0,9, 1,3/*mean (0.226687), correlation (0.278734)*/,
 421     7,-5, 11,-10/*mean (0.00693882), correlation (0.305161)*/,
 422     -13,-6, -11,0/*mean (0.0227283), correlation (0.300181)*/,
 423     10,7, 12,1/*mean (0.125517), correlation (0.31089)*/,
 424     -6,-3, -6,12/*mean (0.131748), correlation (0.312779)*/,
 425     10,-9, 12,-4/*mean (0.144827), correlation (0.292797)*/,
 426     -13,8, -8,-12/*mean (0.149202), correlation (0.308918)*/,
 427     -13,0, -8,-4/*mean (0.160909), correlation (0.310013)*/,
 428     3,3, 7,8/*mean (0.177755), correlation (0.309394)*/,
 429     5,7, 10,-7/*mean (0.212337), correlation (0.310315)*/,
 430     -1,7, 1,-12/*mean (0.214429), correlation (0.311933)*/,
 431     3,-10, 5,6/*mean (0.235807), correlation (0.313104)*/,
 432     2,-4, 3,-10/*mean (0.00494827), correlation (0.344948)*/,
 433     -13,0, -13,5/*mean (0.0549145), correlation (0.344675)*/,
 434     -13,-7, -12,12/*mean (0.103385), correlation (0.342715)*/,
 435     -13,3, -11,8/*mean (0.134222), correlation (0.322922)*/,
 436     -7,12, -4,7/*mean (0.153284), correlation (0.337061)*/,
 437     6,-10, 12,8/*mean (0.154881), correlation (0.329257)*/,
 438     -9,-1, -7,-6/*mean (0.200967), correlation (0.33312)*/,
 439     -2,-5, 0,12/*mean (0.201518), correlation (0.340635)*/,
 440     -12,5, -7,5/*mean (0.207805), correlation (0.335631)*/,
 441     3,-10, 8,-13/*mean (0.224438), correlation (0.34504)*/,
 442     -7,-7, -4,5/*mean (0.239361), correlation (0.338053)*/,
 443     -3,-2, -1,-7/*mean (0.240744), correlation (0.344322)*/,
 444     2,9, 5,-11/*mean (0.242949), correlation (0.34145)*/,
 445     -11,-13, -5,-13/*mean (0.244028), correlation (0.336861)*/,
 446     -1,6, 0,-1/*mean (0.247571), correlation (0.343684)*/,
 447     5,-3, 5,2/*mean (0.000697256), correlation (0.357265)*/,
 448     -4,-13, -4,12/*mean (0.00213675), correlation (0.373827)*/,
 449     -9,-6, -9,6/*mean (0.0126856), correlation (0.373938)*/,
 450     -12,-10, -8,-4/*mean (0.0152497), correlation (0.364237)*/,
 451     10,2, 12,-3/*mean (0.0299933), correlation (0.345292)*/,
 452     7,12, 12,12/*mean (0.0307242), correlation (0.366299)*/,
 453     -7,-13, -6,5/*mean (0.0534975), correlation (0.368357)*/,
 454     -4,9, -3,4/*mean (0.099865), correlation (0.372276)*/,
 455     7,-1, 12,2/*mean (0.117083), correlation (0.364529)*/,
 456     -7,6, -5,1/*mean (0.126125), correlation (0.369606)*/,
 457     -13,11, -12,5/*mean (0.130364), correlation (0.358502)*/,
 458     -3,7, -2,-6/*mean (0.131691), correlation (0.375531)*/,
 459     7,-8, 12,-7/*mean (0.160166), correlation (0.379508)*/,
 460     -13,-7, -11,-12/*mean (0.167848), correlation (0.353343)*/,
 461     1,-3, 12,12/*mean (0.183378), correlation (0.371916)*/,
 462     2,-6, 3,0/*mean (0.228711), correlation (0.371761)*/,
 463     -4,3, -2,-13/*mean (0.247211), correlation (0.364063)*/,
 464     -1,-13, 1,9/*mean (0.249325), correlation (0.378139)*/,
 465     7,1, 8,-6/*mean (0.000652272), correlation (0.411682)*/,
 466     1,-1, 3,12/*mean (0.00248538), correlation (0.392988)*/,
 467     9,1, 12,6/*mean (0.0206815), correlation (0.386106)*/,
 468     -1,-9, -1,3/*mean (0.0364485), correlation (0.410752)*/,
 469     -13,-13, -10,5/*mean (0.0376068), correlation (0.398374)*/,
 470     7,7, 10,12/*mean (0.0424202), correlation (0.405663)*/,
 471     12,-5, 12,9/*mean (0.0942645), correlation (0.410422)*/,
 472     6,3, 7,11/*mean (0.1074), correlation (0.413224)*/,
 473     5,-13, 6,10/*mean (0.109256), correlation (0.408646)*/,
 474     2,-12, 2,3/*mean (0.131691), correlation (0.416076)*/,
 475     3,8, 4,-6/*mean (0.165081), correlation (0.417569)*/,
 476     2,6, 12,-13/*mean (0.171874), correlation (0.408471)*/,
 477     9,-12, 10,3/*mean (0.175146), correlation (0.41296)*/,
 478     -8,4, -7,9/*mean (0.183682), correlation (0.402956)*/,
 479     -11,12, -4,-6/*mean (0.184672), correlation (0.416125)*/,
 480     1,12, 2,-8/*mean (0.191487), correlation (0.386696)*/,
 481     6,-9, 7,-4/*mean (0.192668), correlation (0.394771)*/,
 482     2,3, 3,-2/*mean (0.200157), correlation (0.408303)*/,
 483     6,3, 11,0/*mean (0.204588), correlation (0.411762)*/,
 484     3,-3, 8,-8/*mean (0.205904), correlation (0.416294)*/,
 485     7,8, 9,3/*mean (0.213237), correlation (0.409306)*/,
 486     -11,-5, -6,-4/*mean (0.243444), correlation (0.395069)*/,
 487     -10,11, -5,10/*mean (0.247672), correlation (0.413392)*/,
 488     -5,-8, -3,12/*mean (0.24774), correlation (0.411416)*/,
 489     -10,5, -9,0/*mean (0.00213675), correlation (0.454003)*/,
 490     8,-1, 12,-6/*mean (0.0293635), correlation (0.455368)*/,
 491     4,-6, 6,-11/*mean (0.0404971), correlation (0.457393)*/,
 492     -10,12, -8,7/*mean (0.0481107), correlation (0.448364)*/,
 493     4,-2, 6,7/*mean (0.050641), correlation (0.455019)*/,
 494     -2,0, -2,12/*mean (0.0525978), correlation (0.44338)*/,
 495     -5,-8, -5,2/*mean (0.0629667), correlation (0.457096)*/,
 496     7,-6, 10,12/*mean (0.0653846), correlation (0.445623)*/,
 497     -9,-13, -8,-8/*mean (0.0858749), correlation (0.449789)*/,
 498     -5,-13, -5,-2/*mean (0.122402), correlation (0.450201)*/,
 499     8,-8, 9,-13/*mean (0.125416), correlation (0.453224)*/,
 500     -9,-11, -9,0/*mean (0.130128), correlation (0.458724)*/,
 501     1,-8, 1,-2/*mean (0.132467), correlation (0.440133)*/,
 502     7,-4, 9,1/*mean (0.132692), correlation (0.454)*/,
 503     -2,1, -1,-4/*mean (0.135695), correlation (0.455739)*/,
 504     11,-6, 12,-11/*mean (0.142904), correlation (0.446114)*/,
 505     -12,-9, -6,4/*mean (0.146165), correlation (0.451473)*/,
 506     3,7, 7,12/*mean (0.147627), correlation (0.456643)*/,
 507     5,5, 10,8/*mean (0.152901), correlation (0.455036)*/,
 508     0,-4, 2,8/*mean (0.167083), correlation (0.459315)*/,
 509     -9,12, -5,-13/*mean (0.173234), correlation (0.454706)*/,
 510     0,7, 2,12/*mean (0.18312), correlation (0.433855)*/,
 511     -1,2, 1,7/*mean (0.185504), correlation (0.443838)*/,
 512     5,11, 7,-9/*mean (0.185706), correlation (0.451123)*/,
 513     3,5, 6,-8/*mean (0.188968), correlation (0.455808)*/,
 514     -13,-4, -8,9/*mean (0.191667), correlation (0.459128)*/,
 515     -5,9, -3,-3/*mean (0.193196), correlation (0.458364)*/,
 516     -4,-7, -3,-12/*mean (0.196536), correlation (0.455782)*/,
 517     6,5, 8,0/*mean (0.1972), correlation (0.450481)*/,
 518     -7,6, -6,12/*mean (0.199438), correlation (0.458156)*/,
 519     -13,6, -5,-2/*mean (0.211224), correlation (0.449548)*/,
 520     1,-10, 3,10/*mean (0.211718), correlation (0.440606)*/,
 521     4,1, 8,-4/*mean (0.213034), correlation (0.443177)*/,
 522     -2,-2, 2,-13/*mean (0.234334), correlation (0.455304)*/,
 523     2,-12, 12,12/*mean (0.235684), correlation (0.443436)*/,
 524     -2,-13, 0,-6/*mean (0.237674), correlation (0.452525)*/,
 525     4,1, 9,3/*mean (0.23962), correlation (0.444824)*/,
 526     -6,-10, -3,-5/*mean (0.248459), correlation (0.439621)*/,
 527     -3,-13, -1,1/*mean (0.249505), correlation (0.456666)*/,
 528     7,5, 12,-11/*mean (0.00119208), correlation (0.495466)*/,
 529     4,-2, 5,-7/*mean (0.00372245), correlation (0.484214)*/,
 530     -13,9, -9,-5/*mean (0.00741116), correlation (0.499854)*/,
 531     7,1, 8,6/*mean (0.0208952), correlation (0.499773)*/,
 532     7,-8, 7,6/*mean (0.0220085), correlation (0.501609)*/,
 533     -7,-4, -7,1/*mean (0.0233806), correlation (0.496568)*/,
 534     -8,11, -7,-8/*mean (0.0236505), correlation (0.489719)*/,
 535     -13,6, -12,-8/*mean (0.0268781), correlation (0.503487)*/,
 536     2,4, 3,9/*mean (0.0323324), correlation (0.501938)*/,
 537     10,-5, 12,3/*mean (0.0399235), correlation (0.494029)*/,
 538     -6,-5, -6,7/*mean (0.0420153), correlation (0.486579)*/,
 539     8,-3, 9,-8/*mean (0.0548021), correlation (0.484237)*/,
 540     2,-12, 2,8/*mean (0.0616622), correlation (0.496642)*/,
 541     -11,-2, -10,3/*mean (0.0627755), correlation (0.498563)*/,
 542     -12,-13, -7,-9/*mean (0.0829622), correlation (0.495491)*/,
 543     -11,0, -10,-5/*mean (0.0843342), correlation (0.487146)*/,
 544     5,-3, 11,8/*mean (0.0929937), correlation (0.502315)*/,
 545     -2,-13, -1,12/*mean (0.113327), correlation (0.48941)*/,
 546     -1,-8, 0,9/*mean (0.132119), correlation (0.467268)*/,
 547     -13,-11, -12,-5/*mean (0.136269), correlation (0.498771)*/,
 548     -10,-2, -10,11/*mean (0.142173), correlation (0.498714)*/,
 549     -3,9, -2,-13/*mean (0.144141), correlation (0.491973)*/,
 550     2,-3, 3,2/*mean (0.14892), correlation (0.500782)*/,
 551     -9,-13, -4,0/*mean (0.150371), correlation (0.498211)*/,
 552     -4,6, -3,-10/*mean (0.152159), correlation (0.495547)*/,
 553     -4,12, -2,-7/*mean (0.156152), correlation (0.496925)*/,
 554     -6,-11, -4,9/*mean (0.15749), correlation (0.499222)*/,
 555     6,-3, 6,11/*mean (0.159211), correlation (0.503821)*/,
 556     -13,11, -5,5/*mean (0.162427), correlation (0.501907)*/,
 557     11,11, 12,6/*mean (0.16652), correlation (0.497632)*/,
 558     7,-5, 12,-2/*mean (0.169141), correlation (0.484474)*/,
 559     -1,12, 0,7/*mean (0.169456), correlation (0.495339)*/,
 560     -4,-8, -3,-2/*mean (0.171457), correlation (0.487251)*/,
 561     -7,1, -6,7/*mean (0.175), correlation (0.500024)*/,
 562     -13,-12, -8,-13/*mean (0.175866), correlation (0.497523)*/,
 563     -7,-2, -6,-8/*mean (0.178273), correlation (0.501854)*/,
 564     -8,5, -6,-9/*mean (0.181107), correlation (0.494888)*/,
 565     -5,-1, -4,5/*mean (0.190227), correlation (0.482557)*/,
 566     -13,7, -8,10/*mean (0.196739), correlation (0.496503)*/,
 567     1,5, 5,-13/*mean (0.19973), correlation (0.499759)*/,
 568     1,0, 10,-13/*mean (0.204465), correlation (0.49873)*/,
 569     9,12, 10,-1/*mean (0.209334), correlation (0.49063)*/,
 570     5,-8, 10,-9/*mean (0.211134), correlation (0.503011)*/,
 571     -1,11, 1,-13/*mean (0.212), correlation (0.499414)*/,
 572     -9,-3, -6,2/*mean (0.212168), correlation (0.480739)*/,
 573     -1,-10, 1,12/*mean (0.212731), correlation (0.502523)*/,
 574     -13,1, -8,-10/*mean (0.21327), correlation (0.489786)*/,
 575     8,-11, 10,-6/*mean (0.214159), correlation (0.488246)*/,
 576     2,-13, 3,-6/*mean (0.216993), correlation (0.50287)*/,
 577     7,-13, 12,-9/*mean (0.223639), correlation (0.470502)*/,
 578     -10,-10, -5,-7/*mean (0.224089), correlation (0.500852)*/,
 579     -10,-8, -8,-13/*mean (0.228666), correlation (0.502629)*/,
 580     4,-6, 8,5/*mean (0.22906), correlation (0.498305)*/,
 581     3,12, 8,-13/*mean (0.233378), correlation (0.503825)*/,
 582     -4,2, -3,-3/*mean (0.234323), correlation (0.476692)*/,
 583     5,-13, 10,-12/*mean (0.236392), correlation (0.475462)*/,
 584     4,-13, 5,-1/*mean (0.236842), correlation (0.504132)*/,
 585     -9,9, -4,3/*mean (0.236977), correlation (0.497739)*/,
 586     0,3, 3,-9/*mean (0.24314), correlation (0.499398)*/,
 587     -12,1, -6,1/*mean (0.243297), correlation (0.489447)*/,
 588     3,2, 4,-8/*mean (0.00155196), correlation (0.553496)*/,
 589     -10,-10, -10,9/*mean (0.00239541), correlation (0.54297)*/,
 590     8,-13, 12,12/*mean (0.0034413), correlation (0.544361)*/,
 591     -8,-12, -6,-5/*mean (0.003565), correlation (0.551225)*/,
 592     2,2, 3,7/*mean (0.00835583), correlation (0.55285)*/,
 593     10,6, 11,-8/*mean (0.00885065), correlation (0.540913)*/,
 594     6,8, 8,-12/*mean (0.0101552), correlation (0.551085)*/,
 595     -7,10, -6,5/*mean (0.0102227), correlation (0.533635)*/,
 596     -3,-9, -3,9/*mean (0.0110211), correlation (0.543121)*/,
 597     -1,-13, -1,5/*mean (0.0113473), correlation (0.550173)*/,
 598     -3,-7, -3,4/*mean (0.0140913), correlation (0.554774)*/,
 599     -8,-2, -8,3/*mean (0.017049), correlation (0.55461)*/,
 600     4,2, 12,12/*mean (0.01778), correlation (0.546921)*/,
 601     2,-5, 3,11/*mean (0.0224022), correlation (0.549667)*/,
 602     6,-9, 11,-13/*mean (0.029161), correlation (0.546295)*/,
 603     3,-1, 7,12/*mean (0.0303081), correlation (0.548599)*/,
 604     11,-1, 12,4/*mean (0.0355151), correlation (0.523943)*/,
 605     -3,0, -3,6/*mean (0.0417904), correlation (0.543395)*/,
 606     4,-11, 4,12/*mean (0.0487292), correlation (0.542818)*/,
 607     2,-4, 2,1/*mean (0.0575124), correlation (0.554888)*/,
 608     -10,-6, -8,1/*mean (0.0594242), correlation (0.544026)*/,
 609     -13,7, -11,1/*mean (0.0597391), correlation (0.550524)*/,
 610     -13,12, -11,-13/*mean (0.0608974), correlation (0.55383)*/,
 611     6,0, 11,-13/*mean (0.065126), correlation (0.552006)*/,
 612     0,-1, 1,4/*mean (0.074224), correlation (0.546372)*/,
 613     -13,3, -9,-2/*mean (0.0808592), correlation (0.554875)*/,
 614     -9,8, -6,-3/*mean (0.0883378), correlation (0.551178)*/,
 615     -13,-6, -8,-2/*mean (0.0901035), correlation (0.548446)*/,
 616     5,-9, 8,10/*mean (0.0949843), correlation (0.554694)*/,
 617     2,7, 3,-9/*mean (0.0994152), correlation (0.550979)*/,
 618     -1,-6, -1,-1/*mean (0.10045), correlation (0.552714)*/,
 619     9,5, 11,-2/*mean (0.100686), correlation (0.552594)*/,
 620     11,-3, 12,-8/*mean (0.101091), correlation (0.532394)*/,
 621     3,0, 3,5/*mean (0.101147), correlation (0.525576)*/,
 622     -1,4, 0,10/*mean (0.105263), correlation (0.531498)*/,
 623     3,-6, 4,5/*mean (0.110785), correlation (0.540491)*/,
 624     -13,0, -10,5/*mean (0.112798), correlation (0.536582)*/,
 625     5,8, 12,11/*mean (0.114181), correlation (0.555793)*/,
 626     8,9, 9,-6/*mean (0.117431), correlation (0.553763)*/,
 627     7,-4, 8,-12/*mean (0.118522), correlation (0.553452)*/,
 628     -10,4, -10,9/*mean (0.12094), correlation (0.554785)*/,
 629     7,3, 12,4/*mean (0.122582), correlation (0.555825)*/,
 630     9,-7, 10,-2/*mean (0.124978), correlation (0.549846)*/,
 631     7,0, 12,-2/*mean (0.127002), correlation (0.537452)*/,
 632     -1,-6, 0,-11/*mean (0.127148), correlation (0.547401)*/
 633 };
 634
 635
 636 static void makeRandomPattern(int patchSize, Point* pattern, int npoints)
 637 {
 638     RNG rng(0x34985739); // we always start with a fixed seed,
 639                          // to make patterns the same on each run
 640     for( int i = 0; i < npoints; i++ )
 641     {
 642         pattern[i].x = rng.uniform(-patchSize/2, patchSize/2+1);
 643         pattern[i].y = rng.uniform(-patchSize/2, patchSize/2+1);
 644     }
 645 }
 646
 647
 648 static inline float getScale(int level, int firstLevel, double scaleFactor)
 649 {
 650     return (float)std::pow(scaleFactor, (double)(level - firstLevel));
 651 }
 652
 653
 654 class ORB_Impl CV_FINAL : public ORB
 655 {
 656 public:
 657     explicit ORB_Impl(int _nfeatures, float _scaleFactor, int _nlevels, int _edgeThreshold,
 658              int _firstLevel, int _WTA_K, int _scoreType, int _patchSize, int _fastThreshold) :
 659         nfeatures(_nfeatures), scaleFactor(_scaleFactor), nlevels(_nlevels),
 660         edgeThreshold(_edgeThreshold), firstLevel(_firstLevel), wta_k(_WTA_K),
 661         scoreType(_scoreType), patchSize(_patchSize), fastThreshold(_fastThreshold)
 662     {}
 663
 664     void setMaxFeatures(int maxFeatures) CV_OVERRIDE { nfeatures = maxFeatures; }
 665     int getMaxFeatures() const CV_OVERRIDE { return nfeatures; }
 666
 667     void setScaleFactor(double scaleFactor_) CV_OVERRIDE { scaleFactor = scaleFactor_; }
 668     double getScaleFactor() const CV_OVERRIDE { return scaleFactor; }
 669
 670     void setNLevels(int nlevels_) CV_OVERRIDE { nlevels = nlevels_; }
 671     int getNLevels() const CV_OVERRIDE { return nlevels; }
 672
 673     void setEdgeThreshold(int edgeThreshold_) CV_OVERRIDE { edgeThreshold = edgeThreshold_; }
 674     int getEdgeThreshold() const CV_OVERRIDE { return edgeThreshold; }
 675
 676     void setFirstLevel(int firstLevel_) CV_OVERRIDE { CV_Assert(firstLevel_ >= 0);  firstLevel = firstLevel_; }
 677     int getFirstLevel() const CV_OVERRIDE { return firstLevel; }
 678
 679     void setWTA_K(int wta_k_) CV_OVERRIDE { wta_k = wta_k_; }
 680     int getWTA_K() const CV_OVERRIDE { return wta_k; }
 681
 682     void setScoreType(int scoreType_) CV_OVERRIDE { scoreType = scoreType_; }
 683     int getScoreType() const CV_OVERRIDE { return scoreType; }
 684
 685     void setPatchSize(int patchSize_) CV_OVERRIDE { patchSize = patchSize_; }
 686     int getPatchSize() const CV_OVERRIDE { return patchSize; }
 687
 688     void setFastThreshold(int fastThreshold_) CV_OVERRIDE { fastThreshold = fastThreshold_; }
 689     int getFastThreshold() const CV_OVERRIDE { return fastThreshold; }
 690
 691     // returns the descriptor size in bytes
 692     int descriptorSize() const CV_OVERRIDE;
 693     // returns the descriptor type
 694     int descriptorType() const CV_OVERRIDE;
 695     // returns the default norm type
 696     int defaultNorm() const CV_OVERRIDE;
 697
 698     // Compute the ORB_Impl features and descriptors on an image
 699     void detectAndCompute( InputArray image, InputArray mask, std::vector<KeyPoint>& keypoints,
 700                      OutputArray descriptors, bool useProvidedKeypoints=false ) CV_OVERRIDE;
 701
 702 protected:
 703
 704     int nfeatures;
 705     double scaleFactor;
 706     int nlevels;
 707     int edgeThreshold;
 708     int firstLevel;
 709     int wta_k;
 710     int scoreType;
 711     int patchSize;
 712     int fastThreshold;
 713 };
 714
 715 int ORB_Impl::descriptorSize() const
 716 {
 717     return kBytes;
 718 }
 719
 720 int ORB_Impl::descriptorType() const
 721 {
 722     return CV_8U;
 723 }
 724
 725 int ORB_Impl::defaultNorm() const
 726 {
 727     switch (wta_k)
 728     {
 729     case 2:
 730         return NORM_HAMMING;
 731     case 3:
 732     case 4:
 733         return NORM_HAMMING2;
 734     default:
 735         return -1;
 736     }
 737 }
 738
 739 #ifdef HAVE_OPENCL
 740 static void uploadORBKeypoints(const std::vector<KeyPoint>& src, std::vector<Vec3i>& buf, OutputArray dst)
 741 {
 742     size_t i, n = src.size();
 743     buf.resize(std::max(buf.size(), n));
 744     for( i = 0; i < n; i++ )
 745         buf[i] = Vec3i(cvRound(src[i].pt.x), cvRound(src[i].pt.y), src[i].octave);
 746     copyVectorToUMat(buf, dst);
 747 }
 748
 749 typedef union if32_t
 750 {
 751     int i;
 752     float f;
 753 }
 754 if32_t;
 755
 756 static void uploadORBKeypoints(const std::vector<KeyPoint>& src,
 757                                const std::vector<float>& layerScale,
 758                                std::vector<Vec4i>& buf, OutputArray dst)
 759 {
 760     size_t i, n = src.size();
 761     buf.resize(std::max(buf.size(), n));
 762     for( i = 0; i < n; i++ )
 763     {
 764         int z = src[i].octave;
 765         float scale = 1.f/layerScale[z];
 766         if32_t angle;
 767         angle.f = src[i].angle;
 768         buf[i] = Vec4i(cvRound(src[i].pt.x*scale), cvRound(src[i].pt.y*scale), z, angle.i);
 769     }
 770     copyVectorToUMat(buf, dst);
 771 }
 772 #endif
 773
 774 /** Compute the ORB_Impl keypoints on an image
 775  * @param image_pyramid the image pyramid to compute the features and descriptors on
 776  * @param mask_pyramid the masks to apply at every level
 777  * @param keypoints the resulting keypoints, clustered per level
 778  */
 779 static void computeKeyPoints(const Mat& imagePyramid,
 780                              const UMat& uimagePyramid,
 781                              const Mat& maskPyramid,
 782                              const std::vector<Rect>& layerInfo,
 783                              const UMat& ulayerInfo,
 784                              const std::vector<float>& layerScale,
 785                              std::vector<KeyPoint>& allKeypoints,
 786                              int nfeatures, double scaleFactor,
 787                              int edgeThreshold, int patchSize, int scoreType,
 788                              bool useOCL, int fastThreshold  )
 789 {
 790 #ifndef HAVE_OPENCL
 791     CV_UNUSED(uimagePyramid);CV_UNUSED(ulayerInfo);CV_UNUSED(useOCL);
 792 #endif
 793
 794     int i, nkeypoints, level, nlevels = (int)layerInfo.size();
 795     std::vector<int> nfeaturesPerLevel(nlevels);
 796
 797     // fill the extractors and descriptors for the corresponding scales
 798     float factor = (float)(1.0 / scaleFactor);
 799     float ndesiredFeaturesPerScale = nfeatures*(1 - factor)/(1 - (float)std::pow((double)factor, (double)nlevels));
 800
 801     int sumFeatures = 0;
 802     for( level = 0; level < nlevels-1; level++ )
 803     {
 804         nfeaturesPerLevel[level] = cvRound(ndesiredFeaturesPerScale);
 805         sumFeatures += nfeaturesPerLevel[level];
 806         ndesiredFeaturesPerScale *= factor;
 807     }
 808     nfeaturesPerLevel[nlevels-1] = std::max(nfeatures - sumFeatures, 0);
 809
 810     // Make sure we forget about what is too close to the boundary
 811     //edge_threshold_ = std::max(edge_threshold_, patch_size_/2 + kKernelWidth / 2 + 2);
 812
 813     // pre-compute the end of a row in a circular patch
 814     int halfPatchSize = patchSize / 2;
 815     std::vector<int> umax(halfPatchSize + 2);
 816
 817     int v, v0, vmax = cvFloor(halfPatchSize * std::sqrt(2.f) / 2 + 1);
 818     int vmin = cvCeil(halfPatchSize * std::sqrt(2.f) / 2);
 819     for (v = 0; v <= vmax; ++v)
 820         umax[v] = cvRound(std::sqrt((double)halfPatchSize * halfPatchSize - v * v));
 821
 822     // Make sure we are symmetric
 823     for (v = halfPatchSize, v0 = 0; v >= vmin; --v)
 824     {
 825         while (umax[v0] == umax[v0 + 1])
 826             ++v0;
 827         umax[v] = v0;
 828         ++v0;
 829     }
 830
 831     allKeypoints.clear();
 832     std::vector<KeyPoint> keypoints;
 833     std::vector<int> counters(nlevels);
 834     keypoints.reserve(nfeaturesPerLevel[0]*2);
 835
 836     for( level = 0; level < nlevels; level++ )
 837     {
 838         int featuresNum = nfeaturesPerLevel[level];
 839         Mat img = imagePyramid(layerInfo[level]);
 840         Mat mask = maskPyramid.empty() ? Mat() : maskPyramid(layerInfo[level]);
 841
 842         // Detect FAST features, 20 is a good threshold
 843         {
 844         Ptr<FastFeatureDetector> fd = FastFeatureDetector::create(fastThreshold, true);
 845         fd->detect(img, keypoints, mask);
 846         }
 847
 848         // Remove keypoints very close to the border
 849         KeyPointsFilter::runByImageBorder(keypoints, img.size(), edgeThreshold);
 850
 851         // Keep more points than necessary as FAST does not give amazing corners
 852         KeyPointsFilter::retainBest(keypoints, scoreType == ORB_Impl::HARRIS_SCORE ? 2 * featuresNum : featuresNum);
 853
 854         nkeypoints = (int)keypoints.size();
 855         counters[level] = nkeypoints;
 856
 857         float sf = layerScale[level];
 858         for( i = 0; i < nkeypoints; i++ )
 859         {
 860             keypoints[i].octave = level;
 861             keypoints[i].size = patchSize*sf;
 862         }
 863
 864         std::copy(keypoints.begin(), keypoints.end(), std::back_inserter(allKeypoints));
 865     }
 866
 867     std::vector<Vec3i> ukeypoints_buf;
 868
 869     nkeypoints = (int)allKeypoints.size();
 870     if(nkeypoints == 0)
 871     {
 872         return;
 873     }
 874     Mat responses;
 875     UMat ukeypoints, uresponses(1, nkeypoints, CV_32F);
 876
 877     // Select best features using the Harris cornerness (better scoring than FAST)
 878     if( scoreType == ORB_Impl::HARRIS_SCORE )
 879     {
 880 #ifdef HAVE_OPENCL
 881         if( useOCL )
 882         {
 883             uploadORBKeypoints(allKeypoints, ukeypoints_buf, ukeypoints);
 884             useOCL = ocl_HarrisResponses( uimagePyramid, ulayerInfo, ukeypoints,
 885                                           uresponses, nkeypoints, 7, HARRIS_K );
 886             if( useOCL )
 887             {
 888                 CV_IMPL_ADD(CV_IMPL_OCL);
 889                 uresponses.copyTo(responses);
 890                 for( i = 0; i < nkeypoints; i++ )
 891                     allKeypoints[i].response = responses.at<float>(i);
 892             }
 893         }
 894
 895         if( !useOCL )
 896 #endif
 897             HarrisResponses(imagePyramid, layerInfo, allKeypoints, 7, HARRIS_K);
 898
 899         std::vector<KeyPoint> newAllKeypoints;
 900         newAllKeypoints.reserve(nfeaturesPerLevel[0]*nlevels);
 901
 902         int offset = 0;
 903         for( level = 0; level < nlevels; level++ )
 904         {
 905             int featuresNum = nfeaturesPerLevel[level];
 906             nkeypoints = counters[level];
 907             keypoints.resize(nkeypoints);
 908             std::copy(allKeypoints.begin() + offset,
 909                       allKeypoints.begin() + offset + nkeypoints,
 910                       keypoints.begin());
 911             offset += nkeypoints;
 912
 913             //cull to the final desired level, using the new Harris scores.
 914             KeyPointsFilter::retainBest(keypoints, featuresNum);
 915
 916             std::copy(keypoints.begin(), keypoints.end(), std::back_inserter(newAllKeypoints));
 917         }
 918         std::swap(allKeypoints, newAllKeypoints);
 919     }
 920
 921     nkeypoints = (int)allKeypoints.size();
 922
 923 #ifdef HAVE_OPENCL
 924     if( useOCL )
 925     {
 926         UMat uumax;
 927         if( useOCL )
 928             copyVectorToUMat(umax, uumax);
 929
 930         uploadORBKeypoints(allKeypoints, ukeypoints_buf, ukeypoints);
 931         useOCL = ocl_ICAngles(uimagePyramid, ulayerInfo, ukeypoints, uresponses, uumax,
 932                               nkeypoints, halfPatchSize);
 933
 934         if( useOCL )
 935         {
 936             CV_IMPL_ADD(CV_IMPL_OCL);
 937             uresponses.copyTo(responses);
 938             for( i = 0; i < nkeypoints; i++ )
 939                 allKeypoints[i].angle = responses.at<float>(i);
 940         }
 941     }
 942
 943     if( !useOCL )
 944 #endif
 945     {
 946         ICAngles(imagePyramid, layerInfo, allKeypoints, umax, halfPatchSize);
 947     }
 948
 949     for( i = 0; i < nkeypoints; i++ )
 950     {
 951         float scale = layerScale[allKeypoints[i].octave];
 952         allKeypoints[i].pt *= scale;
 953     }
 954 }
 955
 956
 957 /** Compute the ORB_Impl features and descriptors on an image
 958  * @param img the image to compute the features and descriptors on
 959  * @param mask the mask to apply
 960  * @param keypoints the resulting keypoints
 961  * @param descriptors the resulting descriptors
 962  * @param do_keypoints if true, the keypoints are computed, otherwise used as an input
 963  * @param do_descriptors if true, also computes the descriptors
 964  */
 965 void ORB_Impl::detectAndCompute( InputArray _image, InputArray _mask,
 966                                  std::vector<KeyPoint>& keypoints,
 967                                  OutputArray _descriptors, bool useProvidedKeypoints )
 968 {
 969     CV_INSTRUMENT_REGION();
 970
 971     CV_Assert(patchSize >= 2);
 972
 973     bool do_keypoints = !useProvidedKeypoints;
 974     bool do_descriptors = _descriptors.needed();
 975
 976     if( (!do_keypoints && !do_descriptors) || _image.empty() )
 977         return;
 978
 979     //ROI handling
 980     const int HARRIS_BLOCK_SIZE = 9;
 981     int halfPatchSize = patchSize / 2;
 982     // sqrt(2.0) is for handling patch rotation
 983     int descPatchSize = cvCeil(halfPatchSize*sqrt(2.0));
 984     int border = std::max(edgeThreshold, std::max(descPatchSize, HARRIS_BLOCK_SIZE/2))+1;
 985
 986     bool useOCL = ocl::isOpenCLActivated() && OCL_FORCE_CHECK(_image.isUMat() || _descriptors.isUMat());
 987
 988     Mat image = _image.getMat(), mask = _mask.getMat();
 989     if( image.type() != CV_8UC1 )
 990         cvtColor(_image, image, COLOR_BGR2GRAY);
 991
 992     int i, level, nLevels = this->nlevels, nkeypoints = (int)keypoints.size();
 993     bool sortedByLevel = true;
 994
 995     if( !do_keypoints )
 996     {
 997         // if we have pre-computed keypoints, they may use more levels than it is set in parameters
 998         // !!!TODO!!! implement more correct method, independent from the used keypoint detector.
 999         // Namely, the detector should provide correct size of each keypoint. Based on the keypoint size
1000         // and the algorithm used (i.e. BRIEF, running on 31x31 patches) we should compute the approximate
1001         // scale-factor that we need to apply. Then we should cluster all the computed scale-factors and
1002         // for each cluster compute the corresponding image.
1003         //
1004         // In short, ultimately the descriptor should
1005         // ignore octave parameter and deal only with the keypoint size.
1006         nLevels = 0;
1007         for( i = 0; i < nkeypoints; i++ )
1008         {
1009             level = keypoints[i].octave;
1010             CV_Assert(level >= 0);
1011             if( i > 0 && level < keypoints[i-1].octave )
1012                 sortedByLevel = false;
1013             nLevels = std::max(nLevels, level);
1014         }
1015         nLevels++;
1016     }
1017
1018     std::vector<Rect> layerInfo(nLevels);
1019     std::vector<int> layerOfs(nLevels);
1020     std::vector<float> layerScale(nLevels);
1021     Mat imagePyramid, maskPyramid;
1022     UMat uimagePyramid, ulayerInfo;
1023
1024     int level_dy = image.rows + border*2;
1025     Point level_ofs(0,0);
1026     Size bufSize((cvRound(image.cols/getScale(0, firstLevel, scaleFactor)) + border*2 + 15) & -16, 0);
1027
1028     for( level = 0; level < nLevels; level++ )
1029     {
1030         float scale = getScale(level, firstLevel, scaleFactor);
1031         layerScale[level] = scale;
1032         Size sz(cvRound(image.cols/scale), cvRound(image.rows/scale));
1033         Size wholeSize(sz.width + border*2, sz.height + border*2);
1034         if( level_ofs.x + wholeSize.width > bufSize.width )
1035         {
1036             level_ofs = Point(0, level_ofs.y + level_dy);
1037             level_dy = wholeSize.height;
1038         }
1039
1040         Rect linfo(level_ofs.x + border, level_ofs.y + border, sz.width, sz.height);
1041         layerInfo[level] = linfo;
1042         layerOfs[level] = linfo.y*bufSize.width + linfo.x;
1043         level_ofs.x += wholeSize.width;
1044     }
1045     bufSize.height = level_ofs.y + level_dy;
1046
1047     imagePyramid.create(bufSize, CV_8U);
1048     if( !mask.empty() )
1049         maskPyramid.create(bufSize, CV_8U);
1050
1051     Mat prevImg = image, prevMask = mask;
1052
1053     // Pre-compute the scale pyramids
1054     for (level = 0; level < nLevels; ++level)
1055     {
1056         Rect linfo = layerInfo[level];
1057         Size sz(linfo.width, linfo.height);
1058         Size wholeSize(sz.width + border*2, sz.height + border*2);
1059         Rect wholeLinfo = Rect(linfo.x - border, linfo.y - border, wholeSize.width, wholeSize.height);
1060         Mat extImg = imagePyramid(wholeLinfo), extMask;
1061         Mat currImg = extImg(Rect(border, border, sz.width, sz.height)), currMask;
1062
1063         if( !mask.empty() )
1064         {
1065             extMask = maskPyramid(wholeLinfo);
1066             currMask = extMask(Rect(border, border, sz.width, sz.height));
1067         }
1068
1069         // Compute the resized image
1070         if( level != firstLevel )
1071         {
1072             resize(prevImg, currImg, sz, 0, 0, INTER_LINEAR_EXACT);
1073             if( !mask.empty() )
1074             {
1075                 resize(prevMask, currMask, sz, 0, 0, INTER_LINEAR_EXACT);
1076                 if( level > firstLevel )
1077                     threshold(currMask, currMask, 254, 0, THRESH_TOZERO);
1078             }
1079
1080             copyMakeBorder(currImg, extImg, border, border, border, border,
1081                            BORDER_REFLECT_101+BORDER_ISOLATED);
1082             if (!mask.empty())
1083                 copyMakeBorder(currMask, extMask, border, border, border, border,
1084                                BORDER_CONSTANT+BORDER_ISOLATED);
1085         }
1086         else
1087         {
1088             copyMakeBorder(image, extImg, border, border, border, border,
1089                            BORDER_REFLECT_101);
1090             if( !mask.empty() )
1091                 copyMakeBorder(mask, extMask, border, border, border, border,
1092                                BORDER_CONSTANT+BORDER_ISOLATED);
1093         }
1094         if (level > firstLevel)
1095         {
1096             prevImg = currImg;
1097             prevMask = currMask;
1098         }
1099     }
1100
1101     if( useOCL )
1102         copyVectorToUMat(layerOfs, ulayerInfo);
1103
1104     if( do_keypoints )
1105     {
1106         if( useOCL )
1107             imagePyramid.copyTo(uimagePyramid);
1108
1109         // Get keypoints, those will be far enough from the border that no check will be required for the descriptor
1110         computeKeyPoints(imagePyramid, uimagePyramid, maskPyramid,
1111                          layerInfo, ulayerInfo, layerScale, keypoints,
1112                          nfeatures, scaleFactor, edgeThreshold, patchSize, scoreType, useOCL, fastThreshold);
1113     }
1114     else
1115     {
1116         KeyPointsFilter::runByImageBorder(keypoints, image.size(), edgeThreshold);
1117
1118         if( !sortedByLevel )
1119         {
1120             std::vector<std::vector<KeyPoint> > allKeypoints(nLevels);
1121             nkeypoints = (int)keypoints.size();
1122             for( i = 0; i < nkeypoints; i++ )
1123             {
1124                 level = keypoints[i].octave;
1125                 CV_Assert(0 <= level);
1126                 allKeypoints[level].push_back(keypoints[i]);
1127             }
1128             keypoints.clear();
1129             for( level = 0; level < nLevels; level++ )
1130                 std::copy(allKeypoints[level].begin(), allKeypoints[level].end(), std::back_inserter(keypoints));
1131         }
1132     }
1133
1134     if( do_descriptors )
1135     {
1136         int dsize = descriptorSize();
1137
1138         nkeypoints = (int)keypoints.size();
1139         if( nkeypoints == 0 )
1140         {
1141             _descriptors.release();
1142             return;
1143         }
1144
1145         _descriptors.create(nkeypoints, dsize, CV_8U);
1146         std::vector<Point> pattern;
1147
1148         const int npoints = 512;
1149         Point patternbuf[npoints];
1150         const Point* pattern0 = (const Point*)bit_pattern_31_;
1151
1152         if( patchSize != 31 )
1153         {
1154             pattern0 = patternbuf;
1155             makeRandomPattern(patchSize, patternbuf, npoints);
1156         }
1157
1158         CV_Assert( wta_k == 2 || wta_k == 3 || wta_k == 4 );
1159
1160         if( wta_k == 2 )
1161             std::copy(pattern0, pattern0 + npoints, std::back_inserter(pattern));
1162         else
1163         {
1164             int ntuples = descriptorSize()*4;
1165             initializeOrbPattern(pattern0, pattern, ntuples, wta_k, npoints);
1166         }
1167
1168         for( level = 0; level < nLevels; level++ )
1169         {
1170             // preprocess the resized image
1171             Mat workingMat = imagePyramid(layerInfo[level]);
1172
1173             //boxFilter(working_mat, working_mat, working_mat.depth(), Size(5,5), Point(-1,-1), true, BORDER_REFLECT_101);
1174             GaussianBlur(workingMat, workingMat, Size(7, 7), 2, 2, BORDER_REFLECT_101);
1175         }
1176
1177 #ifdef HAVE_OPENCL
1178         if( useOCL )
1179         {
1180             imagePyramid.copyTo(uimagePyramid);
1181             std::vector<Vec4i> kptbuf;
1182             UMat ukeypoints, upattern;
1183             copyVectorToUMat(pattern, upattern);
1184             uploadORBKeypoints(keypoints, layerScale, kptbuf, ukeypoints);
1185
1186             UMat udescriptors = _descriptors.getUMat();
1187             useOCL = ocl_computeOrbDescriptors(uimagePyramid, ulayerInfo,
1188                                                ukeypoints, udescriptors, upattern,
1189                                                nkeypoints, dsize, wta_k);
1190             if(useOCL)
1191             {
1192                 CV_IMPL_ADD(CV_IMPL_OCL);
1193             }
1194         }
1195
1196         if( !useOCL )
1197 #endif
1198         {
1199             Mat descriptors = _descriptors.getMat();
1200             computeOrbDescriptors(imagePyramid, layerInfo, layerScale,
1201                                   keypoints, descriptors, pattern, dsize, wta_k);
1202         }
1203     }
1204 }
1205
1206 Ptr<ORB> ORB::create(int nfeatures, float scaleFactor, int nlevels, int edgeThreshold,
1207            int firstLevel, int wta_k, int scoreType, int patchSize, int fastThreshold)
1208 {
1209     CV_Assert(firstLevel >= 0);
1210     return makePtr<ORB_Impl>(nfeatures, scaleFactor, nlevels, edgeThreshold,
1211                              firstLevel, wta_k, scoreType, patchSize, fastThreshold);
1212 }
1213
1214 String ORB::getDefaultName() const
1215 {
1216     return (Feature2D::getDefaultName() + ".ORB");
1217 }
1218
1219 }