modules/ocl/test/test_sort.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   5 //  By downloading, copying, installing or using the software you agree to this license.
   6 //  If you do not agree to this license, do not download, install,
   7 //  copy or use the software.
   8 //
   9 //
  10 //                           License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2010-2012, Multicoreware, Inc., all rights reserved.
  14 // Copyright (C) 2010-2012, Advanced Micro Devices, Inc., all rights reserved.
  15 // Third party copyrights are property of their respective owners.
  16 //
  17 // @Authors
  18 //    Peng Xiao, pengxiao@outlook.com
  19 //
  20 // Redistribution and use in source and binary forms, with or without modification,
  21 // are permitted provided that the following conditions are met:
  22 //
  23 //   * Redistribution's of source code must retain the above copyright notice,
  24 //     this list of conditions and the following disclaimer.
  25 //
  26 //   * Redistribution's in binary form must reproduce the above copyright notice,
  27 //     this list of conditions and the following disclaimer in the documentation
  28 //     and/or other oclMaterials provided with the distribution.
  29 //
  30 //   * The name of the copyright holders may not be used to endorse or promote products
  31 //     derived from this software without specific prior written permission.
  32 //
  33 // This software is provided by the copyright holders and contributors as is and
  34 // any express or implied warranties, including, but not limited to, the implied
  35 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  36 // In no event shall the Intel Corporation or contributors be liable for any direct,
  37 // indirect, incidental, special, exemplary, or consequential damages
  38 // (including, but not limited to, procurement of substitute goods or services;
  39 // loss of use, data, or profits; or business interruption) however caused
  40 // and on any theory of liability, whether in contract, strict liability,
  41 // or tort (including negligence or otherwise) arising in any way out of
  42 // the use of this software, even if advised of the possibility of such damage.
  43 //
  44 //M*/
  45 #include <map>
  46 #include <functional>
  47 #include "test_precomp.hpp"
  48
  49 using namespace std;
  50 using namespace cvtest;
  51 using namespace testing;
  52 using namespace cv;
  53
  54
  55 namespace
  56 {
  57 IMPLEMENT_PARAM_CLASS(IsGreaterThan, bool)
  58 IMPLEMENT_PARAM_CLASS(InputSize, int)
  59 IMPLEMENT_PARAM_CLASS(SortMethod, int)
  60
  61
  62 template<class T>
  63 struct KV_CVTYPE{ static int toType() {return 0;} };
  64
  65 template<> struct KV_CVTYPE<int>  { static int toType() {return CV_32SC1;} };
  66 template<> struct KV_CVTYPE<float>{ static int toType() {return CV_32FC1;} };
  67 template<> struct KV_CVTYPE<Vec2i>{ static int toType() {return CV_32SC2;} };
  68 template<> struct KV_CVTYPE<Vec2f>{ static int toType() {return CV_32FC2;} };
  69
  70 template<class key_type, class val_type>
  71 bool kvgreater(pair<key_type, val_type> p1, pair<key_type, val_type> p2)
  72 {
  73     return p1.first > p2.first;
  74 }
  75
  76 template<class key_type, class val_type>
  77 bool kvless(pair<key_type, val_type> p1, pair<key_type, val_type> p2)
  78 {
  79     return p1.first < p2.first;
  80 }
  81
  82 template<class key_type, class val_type>
  83 void toKVPair(
  84     MatConstIterator_<key_type> kit,
  85     MatConstIterator_<val_type> vit,
  86     int vecSize,
  87     vector<pair<key_type, val_type> >& kvres
  88     )
  89 {
  90     kvres.clear();
  91     for(int i = 0; i < vecSize; i ++)
  92     {
  93         kvres.push_back(make_pair(*kit, *vit));
  94         ++kit;
  95         ++vit;
  96     }
  97 }
  98
  99 template<class key_type, class val_type>
 100 void kvquicksort(Mat& keys, Mat& vals, bool isGreater = false)
 101 {
 102     vector<pair<key_type, val_type> > kvres;
 103     toKVPair(keys.begin<key_type>(), vals.begin<val_type>(), keys.cols, kvres);
 104
 105     if(isGreater)
 106     {
 107         std::sort(kvres.begin(), kvres.end(), kvgreater<key_type, val_type>);
 108     }
 109     else
 110     {
 111         std::sort(kvres.begin(), kvres.end(), kvless<key_type, val_type>);
 112     }
 113     key_type * kptr = keys.ptr<key_type>();
 114     val_type * vptr = vals.ptr<val_type>();
 115     for(int i = 0; i < keys.cols; i ++)
 116     {
 117         kptr[i] = kvres[i].first;
 118         vptr[i] = kvres[i].second;
 119     }
 120 }
 121
 122 class SortByKey_STL
 123 {
 124 public:
 125     static void sort(cv::Mat&, cv::Mat&, bool is_gt);
 126 private:
 127     typedef void (*quick_sorter)(cv::Mat&, cv::Mat&, bool);
 128     SortByKey_STL();
 129     quick_sorter quick_sorters[CV_64FC4][CV_64FC4];
 130     static SortByKey_STL instance;
 131 };
 132
 133 SortByKey_STL SortByKey_STL::instance = SortByKey_STL();
 134
 135 SortByKey_STL::SortByKey_STL()
 136 {
 137     memset(instance.quick_sorters, 0, sizeof(quick_sorters));
 138 #define NEW_SORTER(KT, VT) \
 139     instance.quick_sorters[KV_CVTYPE<KT>::toType()][KV_CVTYPE<VT>::toType()] = kvquicksort<KT, VT>;
 140
 141     NEW_SORTER(int, int);
 142     NEW_SORTER(int, Vec2i);
 143     NEW_SORTER(int, float);
 144     NEW_SORTER(int, Vec2f);
 145
 146     NEW_SORTER(float, int);
 147     NEW_SORTER(float, Vec2i);
 148     NEW_SORTER(float, float);
 149     NEW_SORTER(float, Vec2f);
 150 #undef NEW_SORTER
 151 }
 152
 153 void SortByKey_STL::sort(cv::Mat& keys, cv::Mat& vals, bool is_gt)
 154 {
 155     instance.quick_sorters[keys.type()][vals.type()](keys, vals, is_gt);
 156 }
 157
 158 bool checkUnstableSorterResult(const Mat& gkeys_, const Mat& gvals_,
 159                                const Mat& /*dkeys_*/, const Mat& dvals_)
 160 {
 161     int cn_val = gvals_.channels();
 162     int count  = gkeys_.cols;
 163
 164     //for convenience we convert depth to float and channels to 1
 165     Mat gkeys, gvals, dkeys, dvals;
 166     gkeys_.reshape(1).convertTo(gkeys, CV_32F);
 167     gvals_.reshape(1).convertTo(gvals, CV_32F);
 168     //dkeys_.reshape(1).convertTo(dkeys, CV_32F);
 169     dvals_.reshape(1).convertTo(dvals, CV_32F);
 170     float * gkptr = gkeys.ptr<float>();
 171     float * gvptr = gvals.ptr<float>();
 172     //float * dkptr = dkeys.ptr<float>();
 173     float * dvptr = dvals.ptr<float>();
 174
 175     for(int i = 0; i < count - 1; ++i)
 176     {
 177         int iden_count = 0;
 178         // firstly calculate the number of identical keys
 179         while(gkptr[i + iden_count] == gkptr[i + 1 + iden_count])
 180         {
 181             ++ iden_count;
 182         }
 183
 184         // sort dv and gv
 185         int num_of_val = (iden_count + 1) * cn_val;
 186         std::sort(gvptr + i * cn_val, gvptr + i * cn_val + num_of_val);
 187         std::sort(dvptr + i * cn_val, dvptr + i * cn_val + num_of_val);
 188
 189         // then check if [i, i + iden_count) is the same
 190         for(int j = 0; j < num_of_val; ++j)
 191         {
 192             if(gvptr[i + j] != dvptr[i + j])
 193             {
 194                 return false;
 195             }
 196         }
 197         i += iden_count;
 198     }
 199     return true;
 200 }
 201 }
 202
 203 #define INPUT_SIZES  Values(InputSize(0x10), InputSize(0x100), InputSize(0x10000)) //2^4, 2^8, 2^16
 204 #define KEY_TYPES    Values(MatType(CV_32SC1), MatType(CV_32FC1))
 205 #define VAL_TYPES    Values(MatType(CV_32SC1), MatType(CV_32SC2), MatType(CV_32FC1), MatType(CV_32FC2))
 206 #define SORT_METHODS Values(SortMethod(cv::ocl::SORT_BITONIC),SortMethod(cv::ocl::SORT_MERGE),SortMethod(cv::ocl::SORT_RADIX)/*,SortMethod(cv::ocl::SORT_SELECTION)*/)
 207 #define F_OR_T       Values(IsGreaterThan(false), IsGreaterThan(true))
 208
 209 PARAM_TEST_CASE(SortByKey, InputSize, MatType, MatType, SortMethod, IsGreaterThan)
 210 {
 211     InputSize input_size;
 212     MatType key_type, val_type;
 213     SortMethod method;
 214     IsGreaterThan is_gt;
 215
 216     Mat mat_key, mat_val;
 217     virtual void SetUp()
 218     {
 219         input_size = GET_PARAM(0);
 220         key_type   = GET_PARAM(1);
 221         val_type   = GET_PARAM(2);
 222         method     = GET_PARAM(3);
 223         is_gt      = GET_PARAM(4);
 224
 225         using namespace cv;
 226         // fill key and val
 227         mat_key = randomMat(Size(input_size, 1), key_type, INT_MIN, INT_MAX);
 228         mat_val = randomMat(Size(input_size, 1), val_type, INT_MIN, INT_MAX);
 229     }
 230 };
 231
 232 TEST_P(SortByKey, Accuracy)
 233 {
 234     using namespace cv;
 235     ocl::oclMat oclmat_key(mat_key);
 236     ocl::oclMat oclmat_val(mat_val);
 237
 238     ocl::sortByKey(oclmat_key, oclmat_val, method, is_gt);
 239     SortByKey_STL::sort(mat_key, mat_val, is_gt);
 240
 241     EXPECT_MAT_NEAR(mat_key, oclmat_key, 0.0);
 242     EXPECT_TRUE(checkUnstableSorterResult(mat_key, mat_val, oclmat_key, oclmat_val));
 243 }
 244 INSTANTIATE_TEST_CASE_P(OCL_SORT, SortByKey, Combine(INPUT_SIZES, KEY_TYPES, VAL_TYPES, SORT_METHODS, F_OR_T));