1/*M///////////////////////////////////////////////////////////////////////////////////////
2//
3//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4//
5//  By downloading, copying, installing or using the software you agree to this license.
6//  If you do not agree to this license, do not download, install,
7//  copy or use the software.
8//
9//
10//                        Intel License Agreement
11//                For Open Source Computer Vision Library
12//
13// Copyright (C) 2000, Intel Corporation, all rights reserved.
14// Third party copyrights are property of their respective owners.
15//
16// Redistribution and use in source and binary forms, with or without modification,
17// are permitted provided that the following conditions are met:
18//
19//   * Redistribution's of source code must retain the above copyright notice,
20//     this list of conditions and the following disclaimer.
21//
22//   * Redistribution's in binary form must reproduce the above copyright notice,
23//     this list of conditions and the following disclaimer in the documentation
24//     and/or other materials provided with the distribution.
25//
26//   * The name of Intel Corporation may not be used to endorse or promote products
27//     derived from this software without specific prior written permission.
28//
29// This software is provided by the copyright holders and contributors "as is" and
30// any express or implied warranties, including, but not limited to, the implied
31// warranties of merchantability and fitness for a particular purpose are disclaimed.
32// In no event shall the Intel Corporation or contributors be liable for any direct,
33// indirect, incidental, special, exemplary, or consequential damages
34// (including, but not limited to, procurement of substitute goods or services;
35// loss of use, data, or profits; or business interruption) however caused
36// and on any theory of liability, whether in contract, strict liability,
37// or tort (including negligence or otherwise) arising in any way out of
38// the use of this software, even if advised of the possibility of such damage.
39//
40//M*/
41
42#include "precomp.hpp"
43#include <limits>
44#include "opencl_kernels_features2d.hpp"
45
46#if defined(HAVE_EIGEN) && EIGEN_WORLD_VERSION == 2
47#include <Eigen/Array>
48#endif
49
50namespace cv
51{
52
53/////////////////////// ocl functions for BFMatcher ///////////////////////////
54
55static void ensureSizeIsEnough(int rows, int cols, int type, UMat &m)
56{
57    if (m.type() == type && m.rows >= rows && m.cols >= cols)
58        m = m(Rect(0, 0, cols, rows));
59    else
60        m.create(rows, cols, type);
61}
62
63static bool ocl_matchSingle(InputArray query, InputArray train,
64        UMat &trainIdx, UMat &distance, int distType)
65{
66    if (query.empty() || train.empty())
67        return false;
68
69    const int query_rows = query.rows();
70    const int query_cols = query.cols();
71
72    ensureSizeIsEnough(1, query_rows, CV_32S, trainIdx);
73    ensureSizeIsEnough(1, query_rows, CV_32F, distance);
74
75    ocl::Device devDef = ocl::Device::getDefault();
76
77    UMat uquery = query.getUMat(), utrain = train.getUMat();
78    int kercn = 1;
79    if (devDef.isIntel() &&
80        (0 == (uquery.step % 4)) && (0 == (uquery.cols % 4)) && (0 == (uquery.offset % 4)) &&
81        (0 == (utrain.step % 4)) && (0 == (utrain.cols % 4)) && (0 == (utrain.offset % 4)))
82        kercn = 4;
83
84    int block_size = 16;
85    int max_desc_len = 0;
86    bool is_cpu = devDef.type() == ocl::Device::TYPE_CPU;
87    if (query_cols <= 64)
88        max_desc_len = 64 / kercn;
89    else if (query_cols <= 128 && !is_cpu)
90        max_desc_len = 128 / kercn;
91
92    int depth = query.depth();
93    cv::String opts;
94    opts = cv::format("-D T=%s -D TN=%s -D kercn=%d %s -D DIST_TYPE=%d -D BLOCK_SIZE=%d -D MAX_DESC_LEN=%d",
95        ocl::typeToStr(depth), ocl::typeToStr(CV_MAKETYPE(depth, kercn)), kercn, depth == CV_32F ? "-D T_FLOAT" : "", distType, block_size, max_desc_len);
96    ocl::Kernel k("BruteForceMatch_Match", ocl::features2d::brute_force_match_oclsrc, opts);
97    if(k.empty())
98        return false;
99
100    size_t globalSize[] = {(query.size().height + block_size - 1) / block_size * block_size, block_size};
101    size_t localSize[] = {block_size, block_size};
102
103    int idx = 0;
104    idx = k.set(idx, ocl::KernelArg::PtrReadOnly(uquery));
105    idx = k.set(idx, ocl::KernelArg::PtrReadOnly(utrain));
106    idx = k.set(idx, ocl::KernelArg::PtrWriteOnly(trainIdx));
107    idx = k.set(idx, ocl::KernelArg::PtrWriteOnly(distance));
108    idx = k.set(idx, uquery.rows);
109    idx = k.set(idx, uquery.cols);
110    idx = k.set(idx, utrain.rows);
111    idx = k.set(idx, utrain.cols);
112    idx = k.set(idx, (int)(uquery.step / sizeof(float)));
113
114    return k.run(2, globalSize, localSize, false);
115}
116
117static bool ocl_matchConvert(const Mat &trainIdx, const Mat &distance, std::vector< std::vector<DMatch> > &matches)
118{
119    if (trainIdx.empty() || distance.empty())
120        return false;
121
122    if( (trainIdx.type() != CV_32SC1) || (distance.type() != CV_32FC1 || distance.cols != trainIdx.cols) )
123        return false;
124
125    const int nQuery = trainIdx.cols;
126
127    matches.clear();
128    matches.reserve(nQuery);
129
130    const int *trainIdx_ptr = trainIdx.ptr<int>();
131    const float *distance_ptr =  distance.ptr<float>();
132    for (int queryIdx = 0; queryIdx < nQuery; ++queryIdx, ++trainIdx_ptr, ++distance_ptr)
133    {
134        int trainIndex = *trainIdx_ptr;
135
136        if (trainIndex == -1)
137            continue;
138
139        float dst = *distance_ptr;
140
141        DMatch m(queryIdx, trainIndex, 0, dst);
142
143        std::vector<DMatch> temp;
144        temp.push_back(m);
145        matches.push_back(temp);
146    }
147    return true;
148}
149
150static bool ocl_matchDownload(const UMat &trainIdx, const UMat &distance, std::vector< std::vector<DMatch> > &matches)
151{
152    if (trainIdx.empty() || distance.empty())
153        return false;
154
155    Mat trainIdxCPU = trainIdx.getMat(ACCESS_READ);
156    Mat distanceCPU = distance.getMat(ACCESS_READ);
157
158    return ocl_matchConvert(trainIdxCPU, distanceCPU, matches);
159}
160
161static bool ocl_knnMatchSingle(InputArray query, InputArray train, UMat &trainIdx,
162                               UMat &distance, int distType)
163{
164    if (query.empty() || train.empty())
165        return false;
166
167    const int query_rows = query.rows();
168    const int query_cols = query.cols();
169
170    ensureSizeIsEnough(1, query_rows, CV_32SC2, trainIdx);
171    ensureSizeIsEnough(1, query_rows, CV_32FC2, distance);
172
173    trainIdx.setTo(Scalar::all(-1));
174
175    ocl::Device devDef = ocl::Device::getDefault();
176
177    UMat uquery = query.getUMat(), utrain = train.getUMat();
178    int kercn = 1;
179    if (devDef.isIntel() &&
180        (0 == (uquery.step % 4)) && (0 == (uquery.cols % 4)) && (0 == (uquery.offset % 4)) &&
181        (0 == (utrain.step % 4)) && (0 == (utrain.cols % 4)) && (0 == (utrain.offset % 4)))
182        kercn = 4;
183
184    int block_size = 16;
185    int max_desc_len = 0;
186    bool is_cpu = devDef.type() == ocl::Device::TYPE_CPU;
187    if (query_cols <= 64)
188        max_desc_len = 64 / kercn;
189    else if (query_cols <= 128 && !is_cpu)
190        max_desc_len = 128 / kercn;
191
192    int depth = query.depth();
193    cv::String opts;
194    opts = cv::format("-D T=%s -D TN=%s -D kercn=%d %s -D DIST_TYPE=%d -D BLOCK_SIZE=%d -D MAX_DESC_LEN=%d",
195        ocl::typeToStr(depth), ocl::typeToStr(CV_MAKETYPE(depth, kercn)), kercn, depth == CV_32F ? "-D T_FLOAT" : "", distType, block_size, max_desc_len);
196    ocl::Kernel k("BruteForceMatch_knnMatch", ocl::features2d::brute_force_match_oclsrc, opts);
197    if(k.empty())
198        return false;
199
200    size_t globalSize[] = {(query_rows + block_size - 1) / block_size * block_size, block_size};
201    size_t localSize[] = {block_size, block_size};
202
203    int idx = 0;
204    idx = k.set(idx, ocl::KernelArg::PtrReadOnly(uquery));
205    idx = k.set(idx, ocl::KernelArg::PtrReadOnly(utrain));
206    idx = k.set(idx, ocl::KernelArg::PtrWriteOnly(trainIdx));
207    idx = k.set(idx, ocl::KernelArg::PtrWriteOnly(distance));
208    idx = k.set(idx, uquery.rows);
209    idx = k.set(idx, uquery.cols);
210    idx = k.set(idx, utrain.rows);
211    idx = k.set(idx, utrain.cols);
212    idx = k.set(idx, (int)(uquery.step / sizeof(float)));
213
214    return k.run(2, globalSize, localSize, false);
215}
216
217static bool ocl_knnMatchConvert(const Mat &trainIdx, const Mat &distance, std::vector< std::vector<DMatch> > &matches, bool compactResult)
218{
219    if (trainIdx.empty() || distance.empty())
220        return false;
221
222    if(trainIdx.type() != CV_32SC2 && trainIdx.type() != CV_32SC1) return false;
223    if(distance.type() != CV_32FC2 && distance.type() != CV_32FC1)return false;
224    if(distance.size() != trainIdx.size()) return false;
225    if(!trainIdx.isContinuous() || !distance.isContinuous()) return false;
226
227    const int nQuery = trainIdx.type() == CV_32SC2 ? trainIdx.cols : trainIdx.rows;
228    const int k = trainIdx.type() == CV_32SC2 ? 2 : trainIdx.cols;
229
230    matches.clear();
231    matches.reserve(nQuery);
232
233    const int *trainIdx_ptr = trainIdx.ptr<int>();
234    const float *distance_ptr = distance.ptr<float>();
235
236    for (int queryIdx = 0; queryIdx < nQuery; ++queryIdx)
237    {
238        matches.push_back(std::vector<DMatch>());
239        std::vector<DMatch> &curMatches = matches.back();
240        curMatches.reserve(k);
241
242        for (int i = 0; i < k; ++i, ++trainIdx_ptr, ++distance_ptr)
243        {
244            int trainIndex = *trainIdx_ptr;
245
246            if (trainIndex != -1)
247            {
248                float dst = *distance_ptr;
249
250                DMatch m(queryIdx, trainIndex, 0, dst);
251
252                curMatches.push_back(m);
253            }
254        }
255
256        if (compactResult && curMatches.empty())
257            matches.pop_back();
258    }
259    return true;
260}
261
262static bool ocl_knnMatchDownload(const UMat &trainIdx, const UMat &distance, std::vector< std::vector<DMatch> > &matches, bool compactResult)
263{
264    if (trainIdx.empty() || distance.empty())
265        return false;
266
267    Mat trainIdxCPU = trainIdx.getMat(ACCESS_READ);
268    Mat distanceCPU = distance.getMat(ACCESS_READ);
269
270    return ocl_knnMatchConvert(trainIdxCPU, distanceCPU, matches, compactResult);
271}
272
273static bool ocl_radiusMatchSingle(InputArray query, InputArray train,
274        UMat &trainIdx,   UMat &distance, UMat &nMatches, float maxDistance, int distType)
275{
276    if (query.empty() || train.empty())
277        return false;
278
279    const int query_rows = query.rows();
280    const int train_rows = train.rows();
281
282    ensureSizeIsEnough(1, query_rows, CV_32SC1, nMatches);
283
284    if (trainIdx.empty())
285    {
286        ensureSizeIsEnough(query_rows, std::max((train_rows / 100), 10), CV_32SC1, trainIdx);
287        ensureSizeIsEnough(query_rows, std::max((train_rows / 100), 10), CV_32FC1, distance);
288    }
289
290    nMatches.setTo(Scalar::all(0));
291
292    ocl::Device devDef = ocl::Device::getDefault();
293    UMat uquery = query.getUMat(), utrain = train.getUMat();
294    int kercn = 1;
295    if (devDef.isIntel() &&
296        (0 == (uquery.step % 4)) && (0 == (uquery.cols % 4)) && (0 == (uquery.offset % 4)) &&
297        (0 == (utrain.step % 4)) && (0 == (utrain.cols % 4)) && (0 == (utrain.offset % 4)))
298        kercn = 4;
299
300    int block_size = 16;
301    int depth = query.depth();
302    cv::String opts;
303    opts = cv::format("-D T=%s -D TN=%s -D kercn=%d %s -D DIST_TYPE=%d -D BLOCK_SIZE=%d",
304        ocl::typeToStr(depth), ocl::typeToStr(CV_MAKETYPE(depth, kercn)), kercn, depth == CV_32F ? "-D T_FLOAT" : "", distType, block_size);
305    ocl::Kernel k("BruteForceMatch_RadiusMatch", ocl::features2d::brute_force_match_oclsrc, opts);
306    if (k.empty())
307        return false;
308
309    size_t globalSize[] = {(train_rows + block_size - 1) / block_size * block_size, (query_rows + block_size - 1) / block_size * block_size};
310    size_t localSize[] = {block_size, block_size};
311
312    int idx = 0;
313    idx = k.set(idx, ocl::KernelArg::PtrReadOnly(uquery));
314    idx = k.set(idx, ocl::KernelArg::PtrReadOnly(utrain));
315    idx = k.set(idx, maxDistance);
316    idx = k.set(idx, ocl::KernelArg::PtrWriteOnly(trainIdx));
317    idx = k.set(idx, ocl::KernelArg::PtrWriteOnly(distance));
318    idx = k.set(idx, ocl::KernelArg::PtrWriteOnly(nMatches));
319    idx = k.set(idx, uquery.rows);
320    idx = k.set(idx, uquery.cols);
321    idx = k.set(idx, utrain.rows);
322    idx = k.set(idx, utrain.cols);
323    idx = k.set(idx, trainIdx.cols);
324    idx = k.set(idx, (int)(uquery.step / sizeof(float)));
325    idx = k.set(idx, (int)(trainIdx.step / sizeof(int)));
326
327    return k.run(2, globalSize, localSize, false);
328}
329
330static bool ocl_radiusMatchConvert(const Mat &trainIdx, const Mat &distance, const Mat &_nMatches,
331        std::vector< std::vector<DMatch> > &matches, bool compactResult)
332{
333    if (trainIdx.empty() || distance.empty() || _nMatches.empty())
334        return false;
335
336    if( (trainIdx.type() != CV_32SC1) ||
337        (distance.type() != CV_32FC1 || distance.size() != trainIdx.size()) ||
338        (_nMatches.type() != CV_32SC1 || _nMatches.cols != trainIdx.rows) )
339        return false;
340
341    const int nQuery = trainIdx.rows;
342
343    matches.clear();
344    matches.reserve(nQuery);
345
346    const int *nMatches_ptr = _nMatches.ptr<int>();
347
348    for (int queryIdx = 0; queryIdx < nQuery; ++queryIdx)
349    {
350        const int *trainIdx_ptr = trainIdx.ptr<int>(queryIdx);
351        const float *distance_ptr = distance.ptr<float>(queryIdx);
352
353        const int nMatches = std::min(nMatches_ptr[queryIdx], trainIdx.cols);
354
355        if (nMatches == 0)
356        {
357            if (!compactResult)
358                matches.push_back(std::vector<DMatch>());
359            continue;
360        }
361
362        matches.push_back(std::vector<DMatch>(nMatches));
363        std::vector<DMatch> &curMatches = matches.back();
364
365        for (int i = 0; i < nMatches; ++i, ++trainIdx_ptr, ++distance_ptr)
366        {
367            int trainIndex = *trainIdx_ptr;
368
369            float dst = *distance_ptr;
370
371            DMatch m(queryIdx, trainIndex, 0, dst);
372
373            curMatches[i] = m;
374        }
375
376        std::sort(curMatches.begin(), curMatches.end());
377    }
378    return true;
379}
380
381static bool ocl_radiusMatchDownload(const UMat &trainIdx, const UMat &distance, const UMat &nMatches,
382        std::vector< std::vector<DMatch> > &matches, bool compactResult)
383{
384    if (trainIdx.empty() || distance.empty() || nMatches.empty())
385        return false;
386
387    Mat trainIdxCPU = trainIdx.getMat(ACCESS_READ);
388    Mat distanceCPU = distance.getMat(ACCESS_READ);
389    Mat nMatchesCPU = nMatches.getMat(ACCESS_READ);
390
391    return ocl_radiusMatchConvert(trainIdxCPU, distanceCPU, nMatchesCPU, matches, compactResult);
392}
393
394/****************************************************************************************\
395*                                      DescriptorMatcher                                 *
396\****************************************************************************************/
397DescriptorMatcher::DescriptorCollection::DescriptorCollection()
398{}
399
400DescriptorMatcher::DescriptorCollection::DescriptorCollection( const DescriptorCollection& collection )
401{
402    mergedDescriptors = collection.mergedDescriptors.clone();
403    std::copy( collection.startIdxs.begin(), collection.startIdxs.begin(), startIdxs.begin() );
404}
405
406DescriptorMatcher::DescriptorCollection::~DescriptorCollection()
407{}
408
409void DescriptorMatcher::DescriptorCollection::set( const std::vector<Mat>& descriptors )
410{
411    clear();
412
413    size_t imageCount = descriptors.size();
414    CV_Assert( imageCount > 0 );
415
416    startIdxs.resize( imageCount );
417
418    int dim = -1;
419    int type = -1;
420    startIdxs[0] = 0;
421    for( size_t i = 1; i < imageCount; i++ )
422    {
423        int s = 0;
424        if( !descriptors[i-1].empty() )
425        {
426            dim = descriptors[i-1].cols;
427            type = descriptors[i-1].type();
428            s = descriptors[i-1].rows;
429        }
430        startIdxs[i] = startIdxs[i-1] + s;
431    }
432    if( imageCount == 1 )
433    {
434        if( descriptors[0].empty() ) return;
435
436        dim = descriptors[0].cols;
437        type = descriptors[0].type();
438    }
439    CV_Assert( dim > 0 );
440
441    int count = startIdxs[imageCount-1] + descriptors[imageCount-1].rows;
442
443    if( count > 0 )
444    {
445        mergedDescriptors.create( count, dim, type );
446        for( size_t i = 0; i < imageCount; i++ )
447        {
448            if( !descriptors[i].empty() )
449            {
450                CV_Assert( descriptors[i].cols == dim && descriptors[i].type() == type );
451                Mat m = mergedDescriptors.rowRange( startIdxs[i], startIdxs[i] + descriptors[i].rows );
452                descriptors[i].copyTo(m);
453            }
454        }
455    }
456}
457
458void DescriptorMatcher::DescriptorCollection::clear()
459{
460    startIdxs.clear();
461    mergedDescriptors.release();
462}
463
464const Mat DescriptorMatcher::DescriptorCollection::getDescriptor( int imgIdx, int localDescIdx ) const
465{
466    CV_Assert( imgIdx < (int)startIdxs.size() );
467    int globalIdx = startIdxs[imgIdx] + localDescIdx;
468    CV_Assert( globalIdx < (int)size() );
469
470    return getDescriptor( globalIdx );
471}
472
473const Mat& DescriptorMatcher::DescriptorCollection::getDescriptors() const
474{
475    return mergedDescriptors;
476}
477
478const Mat DescriptorMatcher::DescriptorCollection::getDescriptor( int globalDescIdx ) const
479{
480    CV_Assert( globalDescIdx < size() );
481    return mergedDescriptors.row( globalDescIdx );
482}
483
484void DescriptorMatcher::DescriptorCollection::getLocalIdx( int globalDescIdx, int& imgIdx, int& localDescIdx ) const
485{
486    CV_Assert( (globalDescIdx>=0) && (globalDescIdx < size()) );
487    std::vector<int>::const_iterator img_it = std::upper_bound(startIdxs.begin(), startIdxs.end(), globalDescIdx);
488    --img_it;
489    imgIdx = (int)(img_it - startIdxs.begin());
490    localDescIdx = globalDescIdx - (*img_it);
491}
492
493int DescriptorMatcher::DescriptorCollection::size() const
494{
495    return mergedDescriptors.rows;
496}
497
498/*
499 * DescriptorMatcher
500 */
501static void convertMatches( const std::vector<std::vector<DMatch> >& knnMatches, std::vector<DMatch>& matches )
502{
503    matches.clear();
504    matches.reserve( knnMatches.size() );
505    for( size_t i = 0; i < knnMatches.size(); i++ )
506    {
507        CV_Assert( knnMatches[i].size() <= 1 );
508        if( !knnMatches[i].empty() )
509            matches.push_back( knnMatches[i][0] );
510    }
511}
512
513DescriptorMatcher::~DescriptorMatcher()
514{}
515
516void DescriptorMatcher::add( InputArrayOfArrays _descriptors )
517{
518    if(_descriptors.isUMatVector())
519    {
520        std::vector<UMat> descriptors;
521        _descriptors.getUMatVector(descriptors);
522        utrainDescCollection.insert( utrainDescCollection.end(), descriptors.begin(), descriptors.end() );
523    }
524    else if(_descriptors.isUMat())
525    {
526        std::vector<UMat> descriptors = std::vector<UMat>(1, _descriptors.getUMat());
527        utrainDescCollection.insert( utrainDescCollection.end(), descriptors.begin(), descriptors.end() );
528    }
529    else if(_descriptors.isMatVector())
530    {
531        std::vector<Mat> descriptors;
532        _descriptors.getMatVector(descriptors);
533        trainDescCollection.insert( trainDescCollection.end(), descriptors.begin(), descriptors.end() );
534    }
535    else if(_descriptors.isMat())
536    {
537        std::vector<Mat> descriptors = std::vector<Mat>(1, _descriptors.getMat());
538        trainDescCollection.insert( trainDescCollection.end(), descriptors.begin(), descriptors.end() );
539    }
540    else
541        CV_Assert( _descriptors.isUMat() || _descriptors.isUMatVector() || _descriptors.isMat() || _descriptors.isMatVector() );
542}
543
544const std::vector<Mat>& DescriptorMatcher::getTrainDescriptors() const
545{
546    return trainDescCollection;
547}
548
549void DescriptorMatcher::clear()
550{
551    utrainDescCollection.clear();
552    trainDescCollection.clear();
553}
554
555bool DescriptorMatcher::empty() const
556{
557    return trainDescCollection.empty() && utrainDescCollection.empty();
558}
559
560void DescriptorMatcher::train()
561{}
562
563void DescriptorMatcher::match( InputArray queryDescriptors, InputArray trainDescriptors,
564                              std::vector<DMatch>& matches, InputArray mask ) const
565{
566    Ptr<DescriptorMatcher> tempMatcher = clone(true);
567    tempMatcher->add(trainDescriptors);
568    tempMatcher->match( queryDescriptors, matches, std::vector<Mat>(1, mask.getMat()) );
569}
570
571void DescriptorMatcher::knnMatch( InputArray queryDescriptors, InputArray trainDescriptors,
572                                  std::vector<std::vector<DMatch> >& matches, int knn,
573                                  InputArray mask, bool compactResult ) const
574{
575    Ptr<DescriptorMatcher> tempMatcher = clone(true);
576    tempMatcher->add(trainDescriptors);
577    tempMatcher->knnMatch( queryDescriptors, matches, knn, std::vector<Mat>(1, mask.getMat()), compactResult );
578}
579
580void DescriptorMatcher::radiusMatch( InputArray queryDescriptors, InputArray trainDescriptors,
581                                     std::vector<std::vector<DMatch> >& matches, float maxDistance, InputArray mask,
582                                     bool compactResult ) const
583{
584    Ptr<DescriptorMatcher> tempMatcher = clone(true);
585    tempMatcher->add(trainDescriptors);
586    tempMatcher->radiusMatch( queryDescriptors, matches, maxDistance, std::vector<Mat>(1, mask.getMat()), compactResult );
587}
588
589void DescriptorMatcher::match( InputArray queryDescriptors, std::vector<DMatch>& matches, InputArrayOfArrays masks )
590{
591    std::vector<std::vector<DMatch> > knnMatches;
592    knnMatch( queryDescriptors, knnMatches, 1, masks, true /*compactResult*/ );
593    convertMatches( knnMatches, matches );
594}
595
596void DescriptorMatcher::checkMasks( InputArrayOfArrays _masks, int queryDescriptorsCount ) const
597{
598    std::vector<Mat> masks;
599    _masks.getMatVector(masks);
600
601    if( isMaskSupported() && !masks.empty() )
602    {
603        // Check masks
604        size_t imageCount = std::max(trainDescCollection.size(), utrainDescCollection.size() );
605        CV_Assert( masks.size() == imageCount );
606        for( size_t i = 0; i < imageCount; i++ )
607        {
608            if( !masks[i].empty() && (!trainDescCollection[i].empty() || !utrainDescCollection[i].empty() ) )
609            {
610                int rows = trainDescCollection[i].empty() ? utrainDescCollection[i].rows : trainDescCollection[i].rows;
611                    CV_Assert( masks[i].rows == queryDescriptorsCount &&
612                        (masks[i].cols == rows || masks[i].cols == rows) &&
613                        masks[i].type() == CV_8UC1 );
614            }
615        }
616    }
617}
618
619void DescriptorMatcher::knnMatch( InputArray queryDescriptors, std::vector<std::vector<DMatch> >& matches, int knn,
620                                  InputArrayOfArrays masks, bool compactResult )
621{
622    if( empty() || queryDescriptors.empty() )
623        return;
624
625    CV_Assert( knn > 0 );
626
627    checkMasks( masks, queryDescriptors.size().height );
628
629    train();
630    knnMatchImpl( queryDescriptors, matches, knn, masks, compactResult );
631}
632
633void DescriptorMatcher::radiusMatch( InputArray queryDescriptors, std::vector<std::vector<DMatch> >& matches, float maxDistance,
634                                     InputArrayOfArrays masks, bool compactResult )
635{
636    matches.clear();
637    if( empty() || queryDescriptors.empty() )
638        return;
639
640    CV_Assert( maxDistance > std::numeric_limits<float>::epsilon() );
641
642    checkMasks( masks, queryDescriptors.size().height );
643
644    train();
645    radiusMatchImpl( queryDescriptors, matches, maxDistance, masks, compactResult );
646}
647
648void DescriptorMatcher::read( const FileNode& )
649{}
650
651void DescriptorMatcher::write( FileStorage& ) const
652{}
653
654bool DescriptorMatcher::isPossibleMatch( InputArray _mask, int queryIdx, int trainIdx )
655{
656    Mat mask = _mask.getMat();
657    return mask.empty() || mask.at<uchar>(queryIdx, trainIdx);
658}
659
660bool DescriptorMatcher::isMaskedOut( InputArrayOfArrays _masks, int queryIdx )
661{
662    std::vector<Mat> masks;
663    _masks.getMatVector(masks);
664
665    size_t outCount = 0;
666    for( size_t i = 0; i < masks.size(); i++ )
667    {
668        if( !masks[i].empty() && (countNonZero(masks[i].row(queryIdx)) == 0) )
669            outCount++;
670    }
671
672    return !masks.empty() && outCount == masks.size() ;
673}
674
675
676////////////////////////////////////////////////////// BruteForceMatcher /////////////////////////////////////////////////
677
678BFMatcher::BFMatcher( int _normType, bool _crossCheck )
679{
680    normType = _normType;
681    crossCheck = _crossCheck;
682}
683
684Ptr<DescriptorMatcher> BFMatcher::clone( bool emptyTrainData ) const
685{
686    Ptr<BFMatcher> matcher = makePtr<BFMatcher>(normType, crossCheck);
687    if( !emptyTrainData )
688    {
689        matcher->trainDescCollection.resize(trainDescCollection.size());
690        std::transform( trainDescCollection.begin(), trainDescCollection.end(),
691                        matcher->trainDescCollection.begin(), clone_op );
692    }
693    return matcher;
694}
695
696static bool ocl_match(InputArray query, InputArray _train, std::vector< std::vector<DMatch> > &matches, int dstType)
697{
698    UMat trainIdx, distance;
699    if (!ocl_matchSingle(query, _train, trainIdx, distance, dstType))
700        return false;
701    if (!ocl_matchDownload(trainIdx, distance, matches))
702        return false;
703    return true;
704}
705
706static bool ocl_knnMatch(InputArray query, InputArray _train, std::vector< std::vector<DMatch> > &matches, int k, int dstType, bool compactResult)
707{
708    UMat trainIdx, distance;
709    if (k != 2)
710        return false;
711    if (!ocl_knnMatchSingle(query, _train, trainIdx, distance, dstType))
712        return false;
713    if (!ocl_knnMatchDownload(trainIdx, distance, matches, compactResult) )
714        return false;
715    return true;
716}
717
718void BFMatcher::knnMatchImpl( InputArray _queryDescriptors, std::vector<std::vector<DMatch> >& matches, int knn,
719                             InputArrayOfArrays _masks, bool compactResult )
720{
721    int trainDescType = trainDescCollection.empty() ? utrainDescCollection[0].type() : trainDescCollection[0].type();
722    CV_Assert( _queryDescriptors.type() == trainDescType );
723
724    const int IMGIDX_SHIFT = 18;
725    const int IMGIDX_ONE = (1 << IMGIDX_SHIFT);
726
727    if( _queryDescriptors.empty() || (trainDescCollection.empty() && utrainDescCollection.empty()))
728    {
729        matches.clear();
730        return;
731    }
732
733    std::vector<Mat> masks;
734    _masks.getMatVector(masks);
735
736    if(!trainDescCollection.empty() && !utrainDescCollection.empty())
737    {
738        for(int i = 0; i < (int)utrainDescCollection.size(); i++)
739        {
740            Mat tempMat;
741            utrainDescCollection[i].copyTo(tempMat);
742            trainDescCollection.push_back(tempMat);
743        }
744        utrainDescCollection.clear();
745    }
746
747    int trainDescVectorSize = trainDescCollection.empty() ? (int)utrainDescCollection.size() : (int)trainDescCollection.size();
748    Size trainDescSize = trainDescCollection.empty() ? utrainDescCollection[0].size() : trainDescCollection[0].size();
749    int trainDescOffset = trainDescCollection.empty() ? (int)utrainDescCollection[0].offset : 0;
750
751    if ( ocl::useOpenCL() && _queryDescriptors.isUMat() && _queryDescriptors.dims()<=2 && trainDescVectorSize == 1 &&
752        _queryDescriptors.type() == CV_32FC1 && _queryDescriptors.offset() == 0 && trainDescOffset == 0 &&
753        trainDescSize.width == _queryDescriptors.size().width && masks.size() == 1 && masks[0].total() == 0 )
754    {
755        if(knn == 1)
756        {
757            if(trainDescCollection.empty())
758            {
759                if(ocl_match(_queryDescriptors, utrainDescCollection[0], matches, normType))
760                {
761                    CV_IMPL_ADD(CV_IMPL_OCL);
762                    return;
763                }
764            }
765            else
766            {
767                if(ocl_match(_queryDescriptors, trainDescCollection[0], matches, normType))
768                {
769                    CV_IMPL_ADD(CV_IMPL_OCL);
770                    return;
771                }
772            }
773        }
774        else
775        {
776            if(trainDescCollection.empty())
777            {
778                if(ocl_knnMatch(_queryDescriptors, utrainDescCollection[0], matches, knn, normType, compactResult) )
779                {
780                    CV_IMPL_ADD(CV_IMPL_OCL);
781                    return;
782                }
783            }
784            else
785            {
786                if(ocl_knnMatch(_queryDescriptors, trainDescCollection[0], matches, knn, normType, compactResult) )
787                {
788                    CV_IMPL_ADD(CV_IMPL_OCL);
789                    return;
790                }
791            }
792        }
793    }
794
795    Mat queryDescriptors = _queryDescriptors.getMat();
796    if(trainDescCollection.empty() && !utrainDescCollection.empty())
797    {
798        for(int i = 0; i < (int)utrainDescCollection.size(); i++)
799        {
800            Mat tempMat;
801            utrainDescCollection[i].copyTo(tempMat);
802            trainDescCollection.push_back(tempMat);
803        }
804        utrainDescCollection.clear();
805    }
806
807    matches.reserve(queryDescriptors.rows);
808
809    Mat dist, nidx;
810
811    int iIdx, imgCount = (int)trainDescCollection.size(), update = 0;
812    int dtype = normType == NORM_HAMMING || normType == NORM_HAMMING2 ||
813        (normType == NORM_L1 && queryDescriptors.type() == CV_8U) ? CV_32S : CV_32F;
814
815    CV_Assert( (int64)imgCount*IMGIDX_ONE < INT_MAX );
816
817    for( iIdx = 0; iIdx < imgCount; iIdx++ )
818    {
819        CV_Assert( trainDescCollection[iIdx].rows < IMGIDX_ONE );
820        batchDistance(queryDescriptors, trainDescCollection[iIdx], dist, dtype, nidx,
821                      normType, knn, masks.empty() ? Mat() : masks[iIdx], update, crossCheck);
822        update += IMGIDX_ONE;
823    }
824
825    if( dtype == CV_32S )
826    {
827        Mat temp;
828        dist.convertTo(temp, CV_32F);
829        dist = temp;
830    }
831
832    for( int qIdx = 0; qIdx < queryDescriptors.rows; qIdx++ )
833    {
834        const float* distptr = dist.ptr<float>(qIdx);
835        const int* nidxptr = nidx.ptr<int>(qIdx);
836
837        matches.push_back( std::vector<DMatch>() );
838        std::vector<DMatch>& mq = matches.back();
839        mq.reserve(knn);
840
841        for( int k = 0; k < nidx.cols; k++ )
842        {
843            if( nidxptr[k] < 0 )
844                break;
845            mq.push_back( DMatch(qIdx, nidxptr[k] & (IMGIDX_ONE - 1),
846                          nidxptr[k] >> IMGIDX_SHIFT, distptr[k]) );
847        }
848
849        if( mq.empty() && compactResult )
850            matches.pop_back();
851    }
852}
853
854static bool ocl_radiusMatch(InputArray query, InputArray _train, std::vector< std::vector<DMatch> > &matches,
855        float maxDistance, int dstType, bool compactResult)
856{
857    UMat trainIdx, distance, nMatches;
858    if (!ocl_radiusMatchSingle(query, _train, trainIdx, distance, nMatches, maxDistance, dstType))
859        return false;
860    if (!ocl_radiusMatchDownload(trainIdx, distance, nMatches, matches, compactResult))
861        return false;
862    return true;
863}
864
865void BFMatcher::radiusMatchImpl( InputArray _queryDescriptors, std::vector<std::vector<DMatch> >& matches,
866                                float maxDistance, InputArrayOfArrays _masks, bool compactResult )
867{
868    int trainDescType = trainDescCollection.empty() ? utrainDescCollection[0].type() : trainDescCollection[0].type();
869    CV_Assert( _queryDescriptors.type() == trainDescType );
870
871    if( _queryDescriptors.empty() || (trainDescCollection.empty() && utrainDescCollection.empty()))
872    {
873        matches.clear();
874        return;
875    }
876
877    std::vector<Mat> masks;
878    _masks.getMatVector(masks);
879
880    if(!trainDescCollection.empty() && !utrainDescCollection.empty())
881    {
882        for(int i = 0; i < (int)utrainDescCollection.size(); i++)
883        {
884            Mat tempMat;
885            utrainDescCollection[i].copyTo(tempMat);
886            trainDescCollection.push_back(tempMat);
887        }
888        utrainDescCollection.clear();
889    }
890
891    int trainDescVectorSize = trainDescCollection.empty() ? (int)utrainDescCollection.size() : (int)trainDescCollection.size();
892    Size trainDescSize = trainDescCollection.empty() ? utrainDescCollection[0].size() : trainDescCollection[0].size();
893    int trainDescOffset = trainDescCollection.empty() ? (int)utrainDescCollection[0].offset : 0;
894
895    if ( ocl::useOpenCL() && _queryDescriptors.isUMat() && _queryDescriptors.dims()<=2 && trainDescVectorSize == 1 &&
896        _queryDescriptors.type() == CV_32FC1 && _queryDescriptors.offset() == 0 && trainDescOffset == 0 &&
897        trainDescSize.width == _queryDescriptors.size().width && masks.size() == 1 && masks[0].total() == 0 )
898    {
899        if (trainDescCollection.empty())
900        {
901            if(ocl_radiusMatch(_queryDescriptors, utrainDescCollection[0], matches, maxDistance, normType, compactResult) )
902            {
903                CV_IMPL_ADD(CV_IMPL_OCL);
904                return;
905            }
906        }
907        else
908        {
909            if (ocl_radiusMatch(_queryDescriptors, trainDescCollection[0], matches, maxDistance, normType, compactResult) )
910            {
911                CV_IMPL_ADD(CV_IMPL_OCL);
912                return;
913            }
914        }
915    }
916
917    Mat queryDescriptors = _queryDescriptors.getMat();
918    if(trainDescCollection.empty() && !utrainDescCollection.empty())
919    {
920        for(int i = 0; i < (int)utrainDescCollection.size(); i++)
921        {
922            Mat tempMat;
923            utrainDescCollection[i].copyTo(tempMat);
924            trainDescCollection.push_back(tempMat);
925        }
926        utrainDescCollection.clear();
927    }
928
929    matches.resize(queryDescriptors.rows);
930    Mat dist, distf;
931
932    int iIdx, imgCount = (int)trainDescCollection.size();
933    int dtype = normType == NORM_HAMMING ||
934        (normType == NORM_L1 && queryDescriptors.type() == CV_8U) ? CV_32S : CV_32F;
935
936    for( iIdx = 0; iIdx < imgCount; iIdx++ )
937    {
938        batchDistance(queryDescriptors, trainDescCollection[iIdx], dist, dtype, noArray(),
939                      normType, 0, masks.empty() ? Mat() : masks[iIdx], 0, false);
940        if( dtype == CV_32S )
941            dist.convertTo(distf, CV_32F);
942        else
943            distf = dist;
944
945        for( int qIdx = 0; qIdx < queryDescriptors.rows; qIdx++ )
946        {
947            const float* distptr = distf.ptr<float>(qIdx);
948
949            std::vector<DMatch>& mq = matches[qIdx];
950            for( int k = 0; k < distf.cols; k++ )
951            {
952                if( distptr[k] <= maxDistance )
953                    mq.push_back( DMatch(qIdx, k, iIdx, distptr[k]) );
954            }
955        }
956    }
957
958    int qIdx0 = 0;
959    for( int qIdx = 0; qIdx < queryDescriptors.rows; qIdx++ )
960    {
961        if( matches[qIdx].empty() && compactResult )
962            continue;
963
964        if( qIdx0 < qIdx )
965            std::swap(matches[qIdx], matches[qIdx0]);
966
967        std::sort( matches[qIdx0].begin(), matches[qIdx0].end() );
968        qIdx0++;
969    }
970}
971
972///////////////////////////////////////////////////////////////////////////////////////////////////////
973
974/*
975 * Factory function for DescriptorMatcher creating
976 */
977Ptr<DescriptorMatcher> DescriptorMatcher::create( const String& descriptorMatcherType )
978{
979    Ptr<DescriptorMatcher> dm;
980    if( !descriptorMatcherType.compare( "FlannBased" ) )
981    {
982        dm = makePtr<FlannBasedMatcher>();
983    }
984    else if( !descriptorMatcherType.compare( "BruteForce" ) ) // L2
985    {
986        dm = makePtr<BFMatcher>(int(NORM_L2)); // anonymous enums can't be template parameters
987    }
988    else if( !descriptorMatcherType.compare( "BruteForce-SL2" ) ) // Squared L2
989    {
990        dm = makePtr<BFMatcher>(int(NORM_L2SQR));
991    }
992    else if( !descriptorMatcherType.compare( "BruteForce-L1" ) )
993    {
994        dm = makePtr<BFMatcher>(int(NORM_L1));
995    }
996    else if( !descriptorMatcherType.compare("BruteForce-Hamming") ||
997             !descriptorMatcherType.compare("BruteForce-HammingLUT") )
998    {
999        dm = makePtr<BFMatcher>(int(NORM_HAMMING));
1000    }
1001    else if( !descriptorMatcherType.compare("BruteForce-Hamming(2)") )
1002    {
1003        dm = makePtr<BFMatcher>(int(NORM_HAMMING2));
1004    }
1005    else
1006        CV_Error( Error::StsBadArg, "Unknown matcher name" );
1007
1008    return dm;
1009}
1010
1011
1012/*
1013 * Flann based matcher
1014 */
1015FlannBasedMatcher::FlannBasedMatcher( const Ptr<flann::IndexParams>& _indexParams, const Ptr<flann::SearchParams>& _searchParams )
1016    : indexParams(_indexParams), searchParams(_searchParams), addedDescCount(0)
1017{
1018    CV_Assert( _indexParams );
1019    CV_Assert( _searchParams );
1020}
1021
1022void FlannBasedMatcher::add( InputArrayOfArrays _descriptors )
1023{
1024    DescriptorMatcher::add( _descriptors );
1025    std::vector<UMat> descriptors;
1026    _descriptors.getUMatVector(descriptors);
1027
1028    for( size_t i = 0; i < descriptors.size(); i++ )
1029    {
1030        addedDescCount += descriptors[i].rows;
1031    }
1032}
1033
1034void FlannBasedMatcher::clear()
1035{
1036    DescriptorMatcher::clear();
1037
1038    mergedDescriptors.clear();
1039    flannIndex.release();
1040
1041    addedDescCount = 0;
1042}
1043
1044void FlannBasedMatcher::train()
1045{
1046    if( !flannIndex || mergedDescriptors.size() < addedDescCount )
1047    {
1048        // FIXIT: Workaround for 'utrainDescCollection' issue (PR #2142)
1049        if (!utrainDescCollection.empty())
1050        {
1051            CV_Assert(trainDescCollection.size() == 0);
1052            for (size_t i = 0; i < utrainDescCollection.size(); ++i)
1053                trainDescCollection.push_back(utrainDescCollection[i].getMat(ACCESS_READ));
1054        }
1055        mergedDescriptors.set( trainDescCollection );
1056        flannIndex = makePtr<flann::Index>( mergedDescriptors.getDescriptors(), *indexParams );
1057    }
1058}
1059
1060void FlannBasedMatcher::read( const FileNode& fn)
1061{
1062     if (!indexParams)
1063         indexParams = makePtr<flann::IndexParams>();
1064
1065     FileNode ip = fn["indexParams"];
1066     CV_Assert(ip.type() == FileNode::SEQ);
1067
1068     for(int i = 0; i < (int)ip.size(); ++i)
1069     {
1070        CV_Assert(ip[i].type() == FileNode::MAP);
1071        String _name =  (String)ip[i]["name"];
1072        int type =  (int)ip[i]["type"];
1073
1074        switch(type)
1075        {
1076        case CV_8U:
1077        case CV_8S:
1078        case CV_16U:
1079        case CV_16S:
1080        case CV_32S:
1081            indexParams->setInt(_name, (int) ip[i]["value"]);
1082            break;
1083        case CV_32F:
1084            indexParams->setFloat(_name, (float) ip[i]["value"]);
1085            break;
1086        case CV_64F:
1087            indexParams->setDouble(_name, (double) ip[i]["value"]);
1088            break;
1089        case CV_USRTYPE1:
1090            indexParams->setString(_name, (String) ip[i]["value"]);
1091            break;
1092        case CV_MAKETYPE(CV_USRTYPE1,2):
1093            indexParams->setBool(_name, (int) ip[i]["value"] != 0);
1094            break;
1095        case CV_MAKETYPE(CV_USRTYPE1,3):
1096            indexParams->setAlgorithm((int) ip[i]["value"]);
1097            break;
1098        };
1099     }
1100
1101     if (!searchParams)
1102         searchParams = makePtr<flann::SearchParams>();
1103
1104     FileNode sp = fn["searchParams"];
1105     CV_Assert(sp.type() == FileNode::SEQ);
1106
1107     for(int i = 0; i < (int)sp.size(); ++i)
1108     {
1109        CV_Assert(sp[i].type() == FileNode::MAP);
1110        String _name =  (String)sp[i]["name"];
1111        int type =  (int)sp[i]["type"];
1112
1113        switch(type)
1114        {
1115        case CV_8U:
1116        case CV_8S:
1117        case CV_16U:
1118        case CV_16S:
1119        case CV_32S:
1120            searchParams->setInt(_name, (int) sp[i]["value"]);
1121            break;
1122        case CV_32F:
1123            searchParams->setFloat(_name, (float) ip[i]["value"]);
1124            break;
1125        case CV_64F:
1126            searchParams->setDouble(_name, (double) ip[i]["value"]);
1127            break;
1128        case CV_USRTYPE1:
1129            searchParams->setString(_name, (String) ip[i]["value"]);
1130            break;
1131        case CV_MAKETYPE(CV_USRTYPE1,2):
1132            searchParams->setBool(_name, (int) ip[i]["value"] != 0);
1133            break;
1134        case CV_MAKETYPE(CV_USRTYPE1,3):
1135            searchParams->setAlgorithm((int) ip[i]["value"]);
1136            break;
1137        };
1138     }
1139
1140    flannIndex.release();
1141}
1142
1143void FlannBasedMatcher::write( FileStorage& fs) const
1144{
1145     fs << "indexParams" << "[";
1146
1147     if (indexParams)
1148     {
1149         std::vector<String> names;
1150         std::vector<int> types;
1151         std::vector<String> strValues;
1152         std::vector<double> numValues;
1153
1154         indexParams->getAll(names, types, strValues, numValues);
1155
1156         for(size_t i = 0; i < names.size(); ++i)
1157         {
1158             fs << "{" << "name" << names[i] << "type" << types[i] << "value";
1159             switch(types[i])
1160             {
1161             case CV_8U:
1162                 fs << (uchar)numValues[i];
1163                 break;
1164             case CV_8S:
1165                 fs << (char)numValues[i];
1166                 break;
1167             case CV_16U:
1168                 fs << (ushort)numValues[i];
1169                 break;
1170             case CV_16S:
1171                 fs << (short)numValues[i];
1172                 break;
1173             case CV_32S:
1174             case CV_MAKETYPE(CV_USRTYPE1,2):
1175             case CV_MAKETYPE(CV_USRTYPE1,3):
1176                 fs << (int)numValues[i];
1177                 break;
1178             case CV_32F:
1179                 fs << (float)numValues[i];
1180                 break;
1181             case CV_64F:
1182                 fs << (double)numValues[i];
1183                 break;
1184             case CV_USRTYPE1:
1185                 fs << strValues[i];
1186                 break;
1187             default:
1188                 fs << (double)numValues[i];
1189                 fs << "typename" << strValues[i];
1190                 break;
1191             }
1192             fs << "}";
1193         }
1194     }
1195
1196     fs << "]" << "searchParams" << "[";
1197
1198     if (searchParams)
1199     {
1200         std::vector<String> names;
1201         std::vector<int> types;
1202         std::vector<String> strValues;
1203         std::vector<double> numValues;
1204
1205         searchParams->getAll(names, types, strValues, numValues);
1206
1207         for(size_t i = 0; i < names.size(); ++i)
1208         {
1209             fs << "{" << "name" << names[i] << "type" << types[i] << "value";
1210             switch(types[i])
1211             {
1212             case CV_8U:
1213                 fs << (uchar)numValues[i];
1214                 break;
1215             case CV_8S:
1216                 fs << (char)numValues[i];
1217                 break;
1218             case CV_16U:
1219                 fs << (ushort)numValues[i];
1220                 break;
1221             case CV_16S:
1222                 fs << (short)numValues[i];
1223                 break;
1224             case CV_32S:
1225             case CV_MAKETYPE(CV_USRTYPE1,2):
1226             case CV_MAKETYPE(CV_USRTYPE1,3):
1227                 fs << (int)numValues[i];
1228                 break;
1229             case CV_32F:
1230                 fs << (float)numValues[i];
1231                 break;
1232             case CV_64F:
1233                 fs << (double)numValues[i];
1234                 break;
1235             case CV_USRTYPE1:
1236                 fs << strValues[i];
1237                 break;
1238             default:
1239                 fs << (double)numValues[i];
1240                 fs << "typename" << strValues[i];
1241                 break;
1242             }
1243             fs << "}";
1244         }
1245     }
1246     fs << "]";
1247}
1248
1249bool FlannBasedMatcher::isMaskSupported() const
1250{
1251    return false;
1252}
1253
1254Ptr<DescriptorMatcher> FlannBasedMatcher::clone( bool emptyTrainData ) const
1255{
1256    Ptr<FlannBasedMatcher> matcher = makePtr<FlannBasedMatcher>(indexParams, searchParams);
1257    if( !emptyTrainData )
1258    {
1259        CV_Error( Error::StsNotImplemented, "deep clone functionality is not implemented, because "
1260                  "Flann::Index has not copy constructor or clone method ");
1261        //matcher->flannIndex;
1262        matcher->addedDescCount = addedDescCount;
1263        matcher->mergedDescriptors = DescriptorCollection( mergedDescriptors );
1264        std::transform( trainDescCollection.begin(), trainDescCollection.end(),
1265                        matcher->trainDescCollection.begin(), clone_op );
1266    }
1267    return matcher;
1268}
1269
1270void FlannBasedMatcher::convertToDMatches( const DescriptorCollection& collection, const Mat& indices, const Mat& dists,
1271                                           std::vector<std::vector<DMatch> >& matches )
1272{
1273    matches.resize( indices.rows );
1274    for( int i = 0; i < indices.rows; i++ )
1275    {
1276        for( int j = 0; j < indices.cols; j++ )
1277        {
1278            int idx = indices.at<int>(i, j);
1279            if( idx >= 0 )
1280            {
1281                int imgIdx, trainIdx;
1282                collection.getLocalIdx( idx, imgIdx, trainIdx );
1283                float dist = 0;
1284                if (dists.type() == CV_32S)
1285                    dist = static_cast<float>( dists.at<int>(i,j) );
1286                else
1287                    dist = std::sqrt(dists.at<float>(i,j));
1288                matches[i].push_back( DMatch( i, trainIdx, imgIdx, dist ) );
1289            }
1290        }
1291    }
1292}
1293
1294void FlannBasedMatcher::knnMatchImpl( InputArray _queryDescriptors, std::vector<std::vector<DMatch> >& matches, int knn,
1295                                     InputArrayOfArrays /*masks*/, bool /*compactResult*/ )
1296{
1297    Mat queryDescriptors = _queryDescriptors.getMat();
1298    Mat indices( queryDescriptors.rows, knn, CV_32SC1 );
1299    Mat dists( queryDescriptors.rows, knn, CV_32FC1);
1300    flannIndex->knnSearch( queryDescriptors, indices, dists, knn, *searchParams );
1301
1302    convertToDMatches( mergedDescriptors, indices, dists, matches );
1303}
1304
1305void FlannBasedMatcher::radiusMatchImpl( InputArray _queryDescriptors, std::vector<std::vector<DMatch> >& matches, float maxDistance,
1306                                         InputArrayOfArrays /*masks*/, bool /*compactResult*/ )
1307{
1308    Mat queryDescriptors = _queryDescriptors.getMat();
1309    const int count = mergedDescriptors.size(); // TODO do count as param?
1310    Mat indices( queryDescriptors.rows, count, CV_32SC1, Scalar::all(-1) );
1311    Mat dists( queryDescriptors.rows, count, CV_32FC1, Scalar::all(-1) );
1312    for( int qIdx = 0; qIdx < queryDescriptors.rows; qIdx++ )
1313    {
1314        Mat queryDescriptorsRow = queryDescriptors.row(qIdx);
1315        Mat indicesRow = indices.row(qIdx);
1316        Mat distsRow = dists.row(qIdx);
1317        flannIndex->radiusSearch( queryDescriptorsRow, indicesRow, distsRow, maxDistance*maxDistance, count, *searchParams );
1318    }
1319
1320    convertToDMatches( mergedDescriptors, indices, dists, matches );
1321}
1322
1323}
1324