← Back to branch summary

~paparazzi-uav/paparazzi/v5.0-manual

« back to all changes in this revision

Viewing changes to sw/ext/opencv_bebop/opencv/modules/features2d/src/orb.cpp

  • Committer: Paparazzi buildbot
  • Date: 2016-05-18 15:00:29 UTC
  • Revision ID: felix.ruess+docbot@gmail.com-20160518150029-e8lgzi5kvb4p7un9
Manual import commit 4b8bbb730080dac23cf816b98908dacfabe2a8ec from v5.0 branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
sw/ext/opencv_bebop/opencv/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;
 
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 : 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) { nfeatures = maxFeatures; }
 
665
    int getMaxFeatures() const { return nfeatures; }
 
666
 
 
667
    void setScaleFactor(double scaleFactor_) { scaleFactor = scaleFactor_; }
 
668
    double getScaleFactor() const { return scaleFactor; }
 
669
 
 
670
    void setNLevels(int nlevels_) { nlevels = nlevels_; }
 
671
    int getNLevels() const { return nlevels; }
 
672
 
 
673
    void setEdgeThreshold(int edgeThreshold_) { edgeThreshold = edgeThreshold_; }
 
674
    int getEdgeThreshold() const { return edgeThreshold; }
 
675
 
 
676
    void setFirstLevel(int firstLevel_) { firstLevel = firstLevel_; }
 
677
    int getFirstLevel() const { return firstLevel; }
 
678
 
 
679
    void setWTA_K(int wta_k_) { wta_k = wta_k_; }
 
680
    int getWTA_K() const { return wta_k; }
 
681
 
 
682
    void setScoreType(int scoreType_) { scoreType = scoreType_; }
 
683
    int getScoreType() const { return scoreType; }
 
684
 
 
685
    void setPatchSize(int patchSize_) { patchSize = patchSize_; }
 
686
    int getPatchSize() const { return patchSize; }
 
687
 
 
688
    void setFastThreshold(int fastThreshold_) { fastThreshold = fastThreshold_; }
 
689
    int getFastThreshold() const { return fastThreshold; }
 
690
 
 
691
    // returns the descriptor size in bytes
 
692
    int descriptorSize() const;
 
693
    // returns the descriptor type
 
694
    int descriptorType() const;
 
695
    // returns the default norm type
 
696
    int defaultNorm() const;
 
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 );
 
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
    return NORM_HAMMING;
 
728
}
 
729
 
 
730
#ifdef HAVE_OPENCL
 
731
static void uploadORBKeypoints(const std::vector<KeyPoint>& src, std::vector<Vec3i>& buf, OutputArray dst)
 
732
{
 
733
    size_t i, n = src.size();
 
734
    buf.resize(std::max(buf.size(), n));
 
735
    for( i = 0; i < n; i++ )
 
736
        buf[i] = Vec3i(cvRound(src[i].pt.x), cvRound(src[i].pt.y), src[i].octave);
 
737
    copyVectorToUMat(buf, dst);
 
738
}
 
739
 
 
740
typedef union if32_t
 
741
{
 
742
    int i;
 
743
    float f;
 
744
}
 
745
if32_t;
 
746
 
 
747
static void uploadORBKeypoints(const std::vector<KeyPoint>& src,
 
748
                               const std::vector<float>& layerScale,
 
749
                               std::vector<Vec4i>& buf, OutputArray dst)
 
750
{
 
751
    size_t i, n = src.size();
 
752
    buf.resize(std::max(buf.size(), n));
 
753
    for( i = 0; i < n; i++ )
 
754
    {
 
755
        int z = src[i].octave;
 
756
        float scale = 1.f/layerScale[z];
 
757
        if32_t angle;
 
758
        angle.f = src[i].angle;
 
759
        buf[i] = Vec4i(cvRound(src[i].pt.x*scale), cvRound(src[i].pt.y*scale), z, angle.i);
 
760
    }
 
761
    copyVectorToUMat(buf, dst);
 
762
}
 
763
#endif
 
764
 
 
765
/** Compute the ORB_Impl keypoints on an image
 
766
 * @param image_pyramid the image pyramid to compute the features and descriptors on
 
767
 * @param mask_pyramid the masks to apply at every level
 
768
 * @param keypoints the resulting keypoints, clustered per level
 
769
 */
 
770
static void computeKeyPoints(const Mat& imagePyramid,
 
771
                             const UMat& uimagePyramid,
 
772
                             const Mat& maskPyramid,
 
773
                             const std::vector<Rect>& layerInfo,
 
774
                             const UMat& ulayerInfo,
 
775
                             const std::vector<float>& layerScale,
 
776
                             std::vector<KeyPoint>& allKeypoints,
 
777
                             int nfeatures, double scaleFactor,
 
778
                             int edgeThreshold, int patchSize, int scoreType,
 
779
                             bool useOCL, int fastThreshold  )
 
780
{
 
781
#ifndef HAVE_OPENCL
 
782
    (void)uimagePyramid;(void)ulayerInfo;(void)useOCL;
 
783
#endif
 
784
 
 
785
    int i, nkeypoints, level, nlevels = (int)layerInfo.size();
 
786
    std::vector<int> nfeaturesPerLevel(nlevels);
 
787
 
 
788
    // fill the extractors and descriptors for the corresponding scales
 
789
    float factor = (float)(1.0 / scaleFactor);
 
790
    float ndesiredFeaturesPerScale = nfeatures*(1 - factor)/(1 - (float)std::pow((double)factor, (double)nlevels));
 
791
 
 
792
    int sumFeatures = 0;
 
793
    for( level = 0; level < nlevels-1; level++ )
 
794
    {
 
795
        nfeaturesPerLevel[level] = cvRound(ndesiredFeaturesPerScale);
 
796
        sumFeatures += nfeaturesPerLevel[level];
 
797
        ndesiredFeaturesPerScale *= factor;
 
798
    }
 
799
    nfeaturesPerLevel[nlevels-1] = std::max(nfeatures - sumFeatures, 0);
 
800
 
 
801
    // Make sure we forget about what is too close to the boundary
 
802
    //edge_threshold_ = std::max(edge_threshold_, patch_size_/2 + kKernelWidth / 2 + 2);
 
803
 
 
804
    // pre-compute the end of a row in a circular patch
 
805
    int halfPatchSize = patchSize / 2;
 
806
    std::vector<int> umax(halfPatchSize + 2);
 
807
 
 
808
    int v, v0, vmax = cvFloor(halfPatchSize * std::sqrt(2.f) / 2 + 1);
 
809
    int vmin = cvCeil(halfPatchSize * std::sqrt(2.f) / 2);
 
810
    for (v = 0; v <= vmax; ++v)
 
811
        umax[v] = cvRound(std::sqrt((double)halfPatchSize * halfPatchSize - v * v));
 
812
 
 
813
    // Make sure we are symmetric
 
814
    for (v = halfPatchSize, v0 = 0; v >= vmin; --v)
 
815
    {
 
816
        while (umax[v0] == umax[v0 + 1])
 
817
            ++v0;
 
818
        umax[v] = v0;
 
819
        ++v0;
 
820
    }
 
821
 
 
822
    allKeypoints.clear();
 
823
    std::vector<KeyPoint> keypoints;
 
824
    std::vector<int> counters(nlevels);
 
825
    keypoints.reserve(nfeaturesPerLevel[0]*2);
 
826
 
 
827
    for( level = 0; level < nlevels; level++ )
 
828
    {
 
829
        int featuresNum = nfeaturesPerLevel[level];
 
830
        Mat img = imagePyramid(layerInfo[level]);
 
831
        Mat mask = maskPyramid.empty() ? Mat() : maskPyramid(layerInfo[level]);
 
832
 
 
833
        // Detect FAST features, 20 is a good threshold
 
834
        {
 
835
        Ptr<FastFeatureDetector> fd = FastFeatureDetector::create(fastThreshold, true);
 
836
        fd->detect(img, keypoints, mask);
 
837
        }
 
838
 
 
839
        // Remove keypoints very close to the border
 
840
        KeyPointsFilter::runByImageBorder(keypoints, img.size(), edgeThreshold);
 
841
 
 
842
        // Keep more points than necessary as FAST does not give amazing corners
 
843
        KeyPointsFilter::retainBest(keypoints, scoreType == ORB_Impl::HARRIS_SCORE ? 2 * featuresNum : featuresNum);
 
844
 
 
845
        nkeypoints = (int)keypoints.size();
 
846
        counters[level] = nkeypoints;
 
847
 
 
848
        float sf = layerScale[level];
 
849
        for( i = 0; i < nkeypoints; i++ )
 
850
        {
 
851
            keypoints[i].octave = level;
 
852
            keypoints[i].size = patchSize*sf;
 
853
        }
 
854
 
 
855
        std::copy(keypoints.begin(), keypoints.end(), std::back_inserter(allKeypoints));
 
856
    }
 
857
 
 
858
    std::vector<Vec3i> ukeypoints_buf;
 
859
 
 
860
    nkeypoints = (int)allKeypoints.size();
 
861
    if(nkeypoints == 0)
 
862
    {
 
863
        return;
 
864
    }
 
865
    Mat responses;
 
866
    UMat ukeypoints, uresponses(1, nkeypoints, CV_32F);
 
867
 
 
868
    // Select best features using the Harris cornerness (better scoring than FAST)
 
869
    if( scoreType == ORB_Impl::HARRIS_SCORE )
 
870
    {
 
871
#ifdef HAVE_OPENCL
 
872
        if( useOCL )
 
873
        {
 
874
            uploadORBKeypoints(allKeypoints, ukeypoints_buf, ukeypoints);
 
875
            useOCL = ocl_HarrisResponses( uimagePyramid, ulayerInfo, ukeypoints,
 
876
                                          uresponses, nkeypoints, 7, HARRIS_K );
 
877
            if( useOCL )
 
878
            {
 
879
                CV_IMPL_ADD(CV_IMPL_OCL);
 
880
                uresponses.copyTo(responses);
 
881
                for( i = 0; i < nkeypoints; i++ )
 
882
                    allKeypoints[i].response = responses.at<float>(i);
 
883
            }
 
884
        }
 
885
 
 
886
        if( !useOCL )
 
887
#endif
 
888
            HarrisResponses(imagePyramid, layerInfo, allKeypoints, 7, HARRIS_K);
 
889
 
 
890
        std::vector<KeyPoint> newAllKeypoints;
 
891
        newAllKeypoints.reserve(nfeaturesPerLevel[0]*nlevels);
 
892
 
 
893
        int offset = 0;
 
894
        for( level = 0; level < nlevels; level++ )
 
895
        {
 
896
            int featuresNum = nfeaturesPerLevel[level];
 
897
            nkeypoints = counters[level];
 
898
            keypoints.resize(nkeypoints);
 
899
            std::copy(allKeypoints.begin() + offset,
 
900
                      allKeypoints.begin() + offset + nkeypoints,
 
901
                      keypoints.begin());
 
902
            offset += nkeypoints;
 
903
 
 
904
            //cull to the final desired level, using the new Harris scores.
 
905
            KeyPointsFilter::retainBest(keypoints, featuresNum);
 
906
 
 
907
            std::copy(keypoints.begin(), keypoints.end(), std::back_inserter(newAllKeypoints));
 
908
        }
 
909
        std::swap(allKeypoints, newAllKeypoints);
 
910
    }
 
911
 
 
912
    nkeypoints = (int)allKeypoints.size();
 
913
 
 
914
#ifdef HAVE_OPENCL
 
915
    if( useOCL )
 
916
    {
 
917
        UMat uumax;
 
918
        if( useOCL )
 
919
            copyVectorToUMat(umax, uumax);
 
920
 
 
921
        uploadORBKeypoints(allKeypoints, ukeypoints_buf, ukeypoints);
 
922
        useOCL = ocl_ICAngles(uimagePyramid, ulayerInfo, ukeypoints, uresponses, uumax,
 
923
                              nkeypoints, halfPatchSize);
 
924
 
 
925
        if( useOCL )
 
926
        {
 
927
            CV_IMPL_ADD(CV_IMPL_OCL);
 
928
            uresponses.copyTo(responses);
 
929
            for( i = 0; i < nkeypoints; i++ )
 
930
                allKeypoints[i].angle = responses.at<float>(i);
 
931
        }
 
932
    }
 
933
 
 
934
    if( !useOCL )
 
935
#endif
 
936
    {
 
937
        ICAngles(imagePyramid, layerInfo, allKeypoints, umax, halfPatchSize);
 
938
    }
 
939
 
 
940
    for( i = 0; i < nkeypoints; i++ )
 
941
    {
 
942
        float scale = layerScale[allKeypoints[i].octave];
 
943
        allKeypoints[i].pt *= scale;
 
944
    }
 
945
}
 
946
 
 
947
 
 
948
/** Compute the ORB_Impl features and descriptors on an image
 
949
 * @param img the image to compute the features and descriptors on
 
950
 * @param mask the mask to apply
 
951
 * @param keypoints the resulting keypoints
 
952
 * @param descriptors the resulting descriptors
 
953
 * @param do_keypoints if true, the keypoints are computed, otherwise used as an input
 
954
 * @param do_descriptors if true, also computes the descriptors
 
955
 */
 
956
void ORB_Impl::detectAndCompute( InputArray _image, InputArray _mask,
 
957
                                 std::vector<KeyPoint>& keypoints,
 
958
                                 OutputArray _descriptors, bool useProvidedKeypoints )
 
959
{
 
960
    CV_Assert(patchSize >= 2);
 
961
 
 
962
    bool do_keypoints = !useProvidedKeypoints;
 
963
    bool do_descriptors = _descriptors.needed();
 
964
 
 
965
    if( (!do_keypoints && !do_descriptors) || _image.empty() )
 
966
        return;
 
967
 
 
968
    //ROI handling
 
969
    const int HARRIS_BLOCK_SIZE = 9;
 
970
    int halfPatchSize = patchSize / 2;
 
971
    int border = std::max(edgeThreshold, std::max(halfPatchSize, HARRIS_BLOCK_SIZE/2))+1;
 
972
 
 
973
    bool useOCL = ocl::useOpenCL();
 
974
 
 
975
    Mat image = _image.getMat(), mask = _mask.getMat();
 
976
    if( image.type() != CV_8UC1 )
 
977
        cvtColor(_image, image, COLOR_BGR2GRAY);
 
978
 
 
979
    int i, level, nLevels = this->nlevels, nkeypoints = (int)keypoints.size();
 
980
    bool sortedByLevel = true;
 
981
 
 
982
    if( !do_keypoints )
 
983
    {
 
984
        // if we have pre-computed keypoints, they may use more levels than it is set in parameters
 
985
        // !!!TODO!!! implement more correct method, independent from the used keypoint detector.
 
986
        // Namely, the detector should provide correct size of each keypoint. Based on the keypoint size
 
987
        // and the algorithm used (i.e. BRIEF, running on 31x31 patches) we should compute the approximate
 
988
        // scale-factor that we need to apply. Then we should cluster all the computed scale-factors and
 
989
        // for each cluster compute the corresponding image.
 
990
        //
 
991
        // In short, ultimately the descriptor should
 
992
        // ignore octave parameter and deal only with the keypoint size.
 
993
        nLevels = 0;
 
994
        for( i = 0; i < nkeypoints; i++ )
 
995
        {
 
996
            level = keypoints[i].octave;
 
997
            CV_Assert(level >= 0);
 
998
            if( i > 0 && level < keypoints[i-1].octave )
 
999
                sortedByLevel = false;
 
1000
            nLevels = std::max(nLevels, level);
 
1001
        }
 
1002
        nLevels++;
 
1003
    }
 
1004
 
 
1005
    std::vector<Rect> layerInfo(nLevels);
 
1006
    std::vector<int> layerOfs(nLevels);
 
1007
    std::vector<float> layerScale(nLevels);
 
1008
    Mat imagePyramid, maskPyramid;
 
1009
    UMat uimagePyramid, ulayerInfo;
 
1010
 
 
1011
    int level_dy = image.rows + border*2;
 
1012
    Point level_ofs(0,0);
 
1013
    Size bufSize((image.cols + border*2 + 15) & -16, 0);
 
1014
 
 
1015
    for( level = 0; level < nLevels; level++ )
 
1016
    {
 
1017
        float scale = getScale(level, firstLevel, scaleFactor);
 
1018
        layerScale[level] = scale;
 
1019
        Size sz(cvRound(image.cols/scale), cvRound(image.rows/scale));
 
1020
        Size wholeSize(sz.width + border*2, sz.height + border*2);
 
1021
        if( level_ofs.x + wholeSize.width > bufSize.width )
 
1022
        {
 
1023
            level_ofs = Point(0, level_ofs.y + level_dy);
 
1024
            level_dy = wholeSize.height;
 
1025
        }
 
1026
 
 
1027
        Rect linfo(level_ofs.x + border, level_ofs.y + border, sz.width, sz.height);
 
1028
        layerInfo[level] = linfo;
 
1029
        layerOfs[level] = linfo.y*bufSize.width + linfo.x;
 
1030
        level_ofs.x += wholeSize.width;
 
1031
    }
 
1032
    bufSize.height = level_ofs.y + level_dy;
 
1033
 
 
1034
    imagePyramid.create(bufSize, CV_8U);
 
1035
    if( !mask.empty() )
 
1036
        maskPyramid.create(bufSize, CV_8U);
 
1037
 
 
1038
    Mat prevImg = image, prevMask = mask;
 
1039
 
 
1040
    // Pre-compute the scale pyramids
 
1041
    for (level = 0; level < nLevels; ++level)
 
1042
    {
 
1043
        Rect linfo = layerInfo[level];
 
1044
        Size sz(linfo.width, linfo.height);
 
1045
        Size wholeSize(sz.width + border*2, sz.height + border*2);
 
1046
        Rect wholeLinfo = Rect(linfo.x - border, linfo.y - border, wholeSize.width, wholeSize.height);
 
1047
        Mat extImg = imagePyramid(wholeLinfo), extMask;
 
1048
        Mat currImg = extImg(Rect(border, border, sz.width, sz.height)), currMask;
 
1049
 
 
1050
        if( !mask.empty() )
 
1051
        {
 
1052
            extMask = maskPyramid(wholeLinfo);
 
1053
            currMask = extMask(Rect(border, border, sz.width, sz.height));
 
1054
        }
 
1055
 
 
1056
        // Compute the resized image
 
1057
        if( level != firstLevel )
 
1058
        {
 
1059
            resize(prevImg, currImg, sz, 0, 0, INTER_LINEAR);
 
1060
            if( !mask.empty() )
 
1061
            {
 
1062
                resize(prevMask, currMask, sz, 0, 0, INTER_LINEAR);
 
1063
                if( level > firstLevel )
 
1064
                    threshold(currMask, currMask, 254, 0, THRESH_TOZERO);
 
1065
            }
 
1066
 
 
1067
            copyMakeBorder(currImg, extImg, border, border, border, border,
 
1068
                           BORDER_REFLECT_101+BORDER_ISOLATED);
 
1069
            if (!mask.empty())
 
1070
                copyMakeBorder(currMask, extMask, border, border, border, border,
 
1071
                               BORDER_CONSTANT+BORDER_ISOLATED);
 
1072
        }
 
1073
        else
 
1074
        {
 
1075
            copyMakeBorder(image, extImg, border, border, border, border,
 
1076
                           BORDER_REFLECT_101);
 
1077
            if( !mask.empty() )
 
1078
                copyMakeBorder(mask, extMask, border, border, border, border,
 
1079
                               BORDER_CONSTANT+BORDER_ISOLATED);
 
1080
        }
 
1081
        prevImg = currImg;
 
1082
        prevMask = currMask;
 
1083
    }
 
1084
 
 
1085
    if( useOCL )
 
1086
        copyVectorToUMat(layerOfs, ulayerInfo);
 
1087
 
 
1088
    if( do_keypoints )
 
1089
    {
 
1090
        if( useOCL )
 
1091
            imagePyramid.copyTo(uimagePyramid);
 
1092
 
 
1093
        // Get keypoints, those will be far enough from the border that no check will be required for the descriptor
 
1094
        computeKeyPoints(imagePyramid, uimagePyramid, maskPyramid,
 
1095
                         layerInfo, ulayerInfo, layerScale, keypoints,
 
1096
                         nfeatures, scaleFactor, edgeThreshold, patchSize, scoreType, useOCL, fastThreshold);
 
1097
    }
 
1098
    else
 
1099
    {
 
1100
        KeyPointsFilter::runByImageBorder(keypoints, image.size(), edgeThreshold);
 
1101
 
 
1102
        if( !sortedByLevel )
 
1103
        {
 
1104
            std::vector<std::vector<KeyPoint> > allKeypoints(nLevels);
 
1105
            nkeypoints = (int)keypoints.size();
 
1106
            for( i = 0; i < nkeypoints; i++ )
 
1107
            {
 
1108
                level = keypoints[i].octave;
 
1109
                CV_Assert(0 <= level);
 
1110
                allKeypoints[level].push_back(keypoints[i]);
 
1111
            }
 
1112
            keypoints.clear();
 
1113
            for( level = 0; level < nLevels; level++ )
 
1114
                std::copy(allKeypoints[level].begin(), allKeypoints[level].end(), std::back_inserter(keypoints));
 
1115
        }
 
1116
    }
 
1117
 
 
1118
    if( do_descriptors )
 
1119
    {
 
1120
        int dsize = descriptorSize();
 
1121
 
 
1122
        nkeypoints = (int)keypoints.size();
 
1123
        if( nkeypoints == 0 )
 
1124
        {
 
1125
            _descriptors.release();
 
1126
            return;
 
1127
        }
 
1128
 
 
1129
        _descriptors.create(nkeypoints, dsize, CV_8U);
 
1130
        std::vector<Point> pattern;
 
1131
 
 
1132
        const int npoints = 512;
 
1133
        Point patternbuf[npoints];
 
1134
        const Point* pattern0 = (const Point*)bit_pattern_31_;
 
1135
 
 
1136
        if( patchSize != 31 )
 
1137
        {
 
1138
            pattern0 = patternbuf;
 
1139
            makeRandomPattern(patchSize, patternbuf, npoints);
 
1140
        }
 
1141
 
 
1142
        CV_Assert( wta_k == 2 || wta_k == 3 || wta_k == 4 );
 
1143
 
 
1144
        if( wta_k == 2 )
 
1145
            std::copy(pattern0, pattern0 + npoints, std::back_inserter(pattern));
 
1146
        else
 
1147
        {
 
1148
            int ntuples = descriptorSize()*4;
 
1149
            initializeOrbPattern(pattern0, pattern, ntuples, wta_k, npoints);
 
1150
        }
 
1151
 
 
1152
        for( level = 0; level < nLevels; level++ )
 
1153
        {
 
1154
            // preprocess the resized image
 
1155
            Mat workingMat = imagePyramid(layerInfo[level]);
 
1156
 
 
1157
            //boxFilter(working_mat, working_mat, working_mat.depth(), Size(5,5), Point(-1,-1), true, BORDER_REFLECT_101);
 
1158
            GaussianBlur(workingMat, workingMat, Size(7, 7), 2, 2, BORDER_REFLECT_101);
 
1159
        }
 
1160
 
 
1161
#ifdef HAVE_OPENCL
 
1162
        if( useOCL )
 
1163
        {
 
1164
            imagePyramid.copyTo(uimagePyramid);
 
1165
            std::vector<Vec4i> kptbuf;
 
1166
            UMat ukeypoints, upattern;
 
1167
            copyVectorToUMat(pattern, upattern);
 
1168
            uploadORBKeypoints(keypoints, layerScale, kptbuf, ukeypoints);
 
1169
 
 
1170
            UMat udescriptors = _descriptors.getUMat();
 
1171
            useOCL = ocl_computeOrbDescriptors(uimagePyramid, ulayerInfo,
 
1172
                                               ukeypoints, udescriptors, upattern,
 
1173
                                               nkeypoints, dsize, wta_k);
 
1174
            if(useOCL)
 
1175
            {
 
1176
                CV_IMPL_ADD(CV_IMPL_OCL);
 
1177
            }
 
1178
        }
 
1179
 
 
1180
        if( !useOCL )
 
1181
#endif
 
1182
        {
 
1183
            Mat descriptors = _descriptors.getMat();
 
1184
            computeOrbDescriptors(imagePyramid, layerInfo, layerScale,
 
1185
                                  keypoints, descriptors, pattern, dsize, wta_k);
 
1186
        }
 
1187
    }
 
1188
}
 
1189
 
 
1190
Ptr<ORB> ORB::create(int nfeatures, float scaleFactor, int nlevels, int edgeThreshold,
 
1191
           int firstLevel, int wta_k, int scoreType, int patchSize, int fastThreshold)
 
1192
{
 
1193
    return makePtr<ORB_Impl>(nfeatures, scaleFactor, nlevels, edgeThreshold,
 
1194
                             firstLevel, wta_k, scoreType, patchSize, fastThreshold);
 
1195
}
 
1196
 
 
1197
}