Home | History | Annotate | Download | only in src
      1 /* This is FAST corner detector, contributed to OpenCV by the author, Edward Rosten.
      2    Below is the original copyright and the references */
      3 
      4 /*
      5 Copyright (c) 2006, 2008 Edward Rosten
      6 All rights reserved.
      7 
      8 Redistribution and use in source and binary forms, with or without
      9 modification, are permitted provided that the following conditions
     10 are met:
     11 
     12     *Redistributions of source code must retain the above copyright
     13      notice, this list of conditions and the following disclaimer.
     14 
     15     *Redistributions in binary form must reproduce the above copyright
     16      notice, this list of conditions and the following disclaimer in the
     17      documentation and/or other materials provided with the distribution.
     18 
     19     *Neither the name of the University of Cambridge nor the names of
     20      its contributors may be used to endorse or promote products derived
     21      from this software without specific prior written permission.
     22 
     23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     26 A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
     27 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
     28 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     29 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     30 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
     31 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     32 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     33 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     34 */
     35 
     36 /*
     37 The references are:
     38  * Machine learning for high-speed corner detection,
     39    E. Rosten and T. Drummond, ECCV 2006
     40  * Faster and better: A machine learning approach to corner detection
     41    E. Rosten, R. Porter and T. Drummond, PAMI, 2009
     42 */
     43 
     44 #include "fast_score.hpp"
     45 
     46 #define VERIFY_CORNERS 0
     47 
     48 namespace cv {
     49 
     50 void makeOffsets(int pixel[25], int rowStride, int patternSize)
     51 {
     52     static const int offsets16[][2] =
     53     {
     54         {0,  3}, { 1,  3}, { 2,  2}, { 3,  1}, { 3, 0}, { 3, -1}, { 2, -2}, { 1, -3},
     55         {0, -3}, {-1, -3}, {-2, -2}, {-3, -1}, {-3, 0}, {-3,  1}, {-2,  2}, {-1,  3}
     56     };
     57 
     58     static const int offsets12[][2] =
     59     {
     60         {0,  2}, { 1,  2}, { 2,  1}, { 2, 0}, { 2, -1}, { 1, -2},
     61         {0, -2}, {-1, -2}, {-2, -1}, {-2, 0}, {-2,  1}, {-1,  2}
     62     };
     63 
     64     static const int offsets8[][2] =
     65     {
     66         {0,  1}, { 1,  1}, { 1, 0}, { 1, -1},
     67         {0, -1}, {-1, -1}, {-1, 0}, {-1,  1}
     68     };
     69 
     70     const int (*offsets)[2] = patternSize == 16 ? offsets16 :
     71                               patternSize == 12 ? offsets12 :
     72                               patternSize == 8  ? offsets8  : 0;
     73 
     74     CV_Assert(pixel && offsets);
     75 
     76     int k = 0;
     77     for( ; k < patternSize; k++ )
     78         pixel[k] = offsets[k][0] + offsets[k][1] * rowStride;
     79     for( ; k < 25; k++ )
     80         pixel[k] = pixel[k - patternSize];
     81 }
     82 
     83 #if VERIFY_CORNERS
     84 static void testCorner(const uchar* ptr, const int pixel[], int K, int N, int threshold) {
     85     // check that with the computed "threshold" the pixel is still a corner
     86     // and that with the increased-by-1 "threshold" the pixel is not a corner anymore
     87     for( int delta = 0; delta <= 1; delta++ )
     88     {
     89         int v0 = std::min(ptr[0] + threshold + delta, 255);
     90         int v1 = std::max(ptr[0] - threshold - delta, 0);
     91         int c0 = 0, c1 = 0;
     92 
     93         for( int k = 0; k < N; k++ )
     94         {
     95             int x = ptr[pixel[k]];
     96             if(x > v0)
     97             {
     98                 if( ++c0 > K )
     99                     break;
    100                 c1 = 0;
    101             }
    102             else if( x < v1 )
    103             {
    104                 if( ++c1 > K )
    105                     break;
    106                 c0 = 0;
    107             }
    108             else
    109             {
    110                 c0 = c1 = 0;
    111             }
    112         }
    113         CV_Assert( (delta == 0 && std::max(c0, c1) > K) ||
    114                    (delta == 1 && std::max(c0, c1) <= K) );
    115     }
    116 }
    117 #endif
    118 
    119 template<>
    120 int cornerScore<16>(const uchar* ptr, const int pixel[], int threshold)
    121 {
    122     const int K = 8, N = K*3 + 1;
    123     int k, v = ptr[0];
    124     short d[N];
    125     for( k = 0; k < N; k++ )
    126         d[k] = (short)(v - ptr[pixel[k]]);
    127 
    128 #if CV_SSE2
    129     __m128i q0 = _mm_set1_epi16(-1000), q1 = _mm_set1_epi16(1000);
    130     for( k = 0; k < 16; k += 8 )
    131     {
    132         __m128i v0 = _mm_loadu_si128((__m128i*)(d+k+1));
    133         __m128i v1 = _mm_loadu_si128((__m128i*)(d+k+2));
    134         __m128i a = _mm_min_epi16(v0, v1);
    135         __m128i b = _mm_max_epi16(v0, v1);
    136         v0 = _mm_loadu_si128((__m128i*)(d+k+3));
    137         a = _mm_min_epi16(a, v0);
    138         b = _mm_max_epi16(b, v0);
    139         v0 = _mm_loadu_si128((__m128i*)(d+k+4));
    140         a = _mm_min_epi16(a, v0);
    141         b = _mm_max_epi16(b, v0);
    142         v0 = _mm_loadu_si128((__m128i*)(d+k+5));
    143         a = _mm_min_epi16(a, v0);
    144         b = _mm_max_epi16(b, v0);
    145         v0 = _mm_loadu_si128((__m128i*)(d+k+6));
    146         a = _mm_min_epi16(a, v0);
    147         b = _mm_max_epi16(b, v0);
    148         v0 = _mm_loadu_si128((__m128i*)(d+k+7));
    149         a = _mm_min_epi16(a, v0);
    150         b = _mm_max_epi16(b, v0);
    151         v0 = _mm_loadu_si128((__m128i*)(d+k+8));
    152         a = _mm_min_epi16(a, v0);
    153         b = _mm_max_epi16(b, v0);
    154         v0 = _mm_loadu_si128((__m128i*)(d+k));
    155         q0 = _mm_max_epi16(q0, _mm_min_epi16(a, v0));
    156         q1 = _mm_min_epi16(q1, _mm_max_epi16(b, v0));
    157         v0 = _mm_loadu_si128((__m128i*)(d+k+9));
    158         q0 = _mm_max_epi16(q0, _mm_min_epi16(a, v0));
    159         q1 = _mm_min_epi16(q1, _mm_max_epi16(b, v0));
    160     }
    161     q0 = _mm_max_epi16(q0, _mm_sub_epi16(_mm_setzero_si128(), q1));
    162     q0 = _mm_max_epi16(q0, _mm_unpackhi_epi64(q0, q0));
    163     q0 = _mm_max_epi16(q0, _mm_srli_si128(q0, 4));
    164     q0 = _mm_max_epi16(q0, _mm_srli_si128(q0, 2));
    165     threshold = (short)_mm_cvtsi128_si32(q0) - 1;
    166 #else
    167     int a0 = threshold;
    168     for( k = 0; k < 16; k += 2 )
    169     {
    170         int a = std::min((int)d[k+1], (int)d[k+2]);
    171         a = std::min(a, (int)d[k+3]);
    172         if( a <= a0 )
    173             continue;
    174         a = std::min(a, (int)d[k+4]);
    175         a = std::min(a, (int)d[k+5]);
    176         a = std::min(a, (int)d[k+6]);
    177         a = std::min(a, (int)d[k+7]);
    178         a = std::min(a, (int)d[k+8]);
    179         a0 = std::max(a0, std::min(a, (int)d[k]));
    180         a0 = std::max(a0, std::min(a, (int)d[k+9]));
    181     }
    182 
    183     int b0 = -a0;
    184     for( k = 0; k < 16; k += 2 )
    185     {
    186         int b = std::max((int)d[k+1], (int)d[k+2]);
    187         b = std::max(b, (int)d[k+3]);
    188         b = std::max(b, (int)d[k+4]);
    189         b = std::max(b, (int)d[k+5]);
    190         if( b >= b0 )
    191             continue;
    192         b = std::max(b, (int)d[k+6]);
    193         b = std::max(b, (int)d[k+7]);
    194         b = std::max(b, (int)d[k+8]);
    195 
    196         b0 = std::min(b0, std::max(b, (int)d[k]));
    197         b0 = std::min(b0, std::max(b, (int)d[k+9]));
    198     }
    199 
    200     threshold = -b0-1;
    201 #endif
    202 
    203 #if VERIFY_CORNERS
    204     testCorner(ptr, pixel, K, N, threshold);
    205 #endif
    206     return threshold;
    207 }
    208 
    209 template<>
    210 int cornerScore<12>(const uchar* ptr, const int pixel[], int threshold)
    211 {
    212     const int K = 6, N = K*3 + 1;
    213     int k, v = ptr[0];
    214     short d[N + 4];
    215     for( k = 0; k < N; k++ )
    216         d[k] = (short)(v - ptr[pixel[k]]);
    217 #if CV_SSE2
    218     for( k = 0; k < 4; k++ )
    219         d[N+k] = d[k];
    220 #endif
    221 
    222 #if CV_SSE2
    223     __m128i q0 = _mm_set1_epi16(-1000), q1 = _mm_set1_epi16(1000);
    224     for( k = 0; k < 16; k += 8 )
    225     {
    226         __m128i v0 = _mm_loadu_si128((__m128i*)(d+k+1));
    227         __m128i v1 = _mm_loadu_si128((__m128i*)(d+k+2));
    228         __m128i a = _mm_min_epi16(v0, v1);
    229         __m128i b = _mm_max_epi16(v0, v1);
    230         v0 = _mm_loadu_si128((__m128i*)(d+k+3));
    231         a = _mm_min_epi16(a, v0);
    232         b = _mm_max_epi16(b, v0);
    233         v0 = _mm_loadu_si128((__m128i*)(d+k+4));
    234         a = _mm_min_epi16(a, v0);
    235         b = _mm_max_epi16(b, v0);
    236         v0 = _mm_loadu_si128((__m128i*)(d+k+5));
    237         a = _mm_min_epi16(a, v0);
    238         b = _mm_max_epi16(b, v0);
    239         v0 = _mm_loadu_si128((__m128i*)(d+k+6));
    240         a = _mm_min_epi16(a, v0);
    241         b = _mm_max_epi16(b, v0);
    242         v0 = _mm_loadu_si128((__m128i*)(d+k));
    243         q0 = _mm_max_epi16(q0, _mm_min_epi16(a, v0));
    244         q1 = _mm_min_epi16(q1, _mm_max_epi16(b, v0));
    245         v0 = _mm_loadu_si128((__m128i*)(d+k+7));
    246         q0 = _mm_max_epi16(q0, _mm_min_epi16(a, v0));
    247         q1 = _mm_min_epi16(q1, _mm_max_epi16(b, v0));
    248     }
    249     q0 = _mm_max_epi16(q0, _mm_sub_epi16(_mm_setzero_si128(), q1));
    250     q0 = _mm_max_epi16(q0, _mm_unpackhi_epi64(q0, q0));
    251     q0 = _mm_max_epi16(q0, _mm_srli_si128(q0, 4));
    252     q0 = _mm_max_epi16(q0, _mm_srli_si128(q0, 2));
    253     threshold = (short)_mm_cvtsi128_si32(q0) - 1;
    254 #else
    255     int a0 = threshold;
    256     for( k = 0; k < 12; k += 2 )
    257     {
    258         int a = std::min((int)d[k+1], (int)d[k+2]);
    259         if( a <= a0 )
    260             continue;
    261         a = std::min(a, (int)d[k+3]);
    262         a = std::min(a, (int)d[k+4]);
    263         a = std::min(a, (int)d[k+5]);
    264         a = std::min(a, (int)d[k+6]);
    265         a0 = std::max(a0, std::min(a, (int)d[k]));
    266         a0 = std::max(a0, std::min(a, (int)d[k+7]));
    267     }
    268 
    269     int b0 = -a0;
    270     for( k = 0; k < 12; k += 2 )
    271     {
    272         int b = std::max((int)d[k+1], (int)d[k+2]);
    273         b = std::max(b, (int)d[k+3]);
    274         b = std::max(b, (int)d[k+4]);
    275         if( b >= b0 )
    276             continue;
    277         b = std::max(b, (int)d[k+5]);
    278         b = std::max(b, (int)d[k+6]);
    279 
    280         b0 = std::min(b0, std::max(b, (int)d[k]));
    281         b0 = std::min(b0, std::max(b, (int)d[k+7]));
    282     }
    283 
    284     threshold = -b0-1;
    285 #endif
    286 
    287 #if VERIFY_CORNERS
    288     testCorner(ptr, pixel, K, N, threshold);
    289 #endif
    290     return threshold;
    291 }
    292 
    293 template<>
    294 int cornerScore<8>(const uchar* ptr, const int pixel[], int threshold)
    295 {
    296     const int K = 4, N = K*3 + 1;
    297     int k, v = ptr[0];
    298     short d[N];
    299     for( k = 0; k < N; k++ )
    300         d[k] = (short)(v - ptr[pixel[k]]);
    301 
    302 #if CV_SSE2
    303     __m128i v0 = _mm_loadu_si128((__m128i*)(d+1));
    304     __m128i v1 = _mm_loadu_si128((__m128i*)(d+2));
    305     __m128i a = _mm_min_epi16(v0, v1);
    306     __m128i b = _mm_max_epi16(v0, v1);
    307     v0 = _mm_loadu_si128((__m128i*)(d+3));
    308     a = _mm_min_epi16(a, v0);
    309     b = _mm_max_epi16(b, v0);
    310     v0 = _mm_loadu_si128((__m128i*)(d+4));
    311     a = _mm_min_epi16(a, v0);
    312     b = _mm_max_epi16(b, v0);
    313     v0 = _mm_loadu_si128((__m128i*)(d));
    314     __m128i q0 = _mm_min_epi16(a, v0);
    315     __m128i q1 = _mm_max_epi16(b, v0);
    316     v0 = _mm_loadu_si128((__m128i*)(d+5));
    317     q0 = _mm_max_epi16(q0, _mm_min_epi16(a, v0));
    318     q1 = _mm_min_epi16(q1, _mm_max_epi16(b, v0));
    319     q0 = _mm_max_epi16(q0, _mm_sub_epi16(_mm_setzero_si128(), q1));
    320     q0 = _mm_max_epi16(q0, _mm_unpackhi_epi64(q0, q0));
    321     q0 = _mm_max_epi16(q0, _mm_srli_si128(q0, 4));
    322     q0 = _mm_max_epi16(q0, _mm_srli_si128(q0, 2));
    323     threshold = (short)_mm_cvtsi128_si32(q0) - 1;
    324 #else
    325     int a0 = threshold;
    326     for( k = 0; k < 8; k += 2 )
    327     {
    328         int a = std::min((int)d[k+1], (int)d[k+2]);
    329         if( a <= a0 )
    330             continue;
    331         a = std::min(a, (int)d[k+3]);
    332         a = std::min(a, (int)d[k+4]);
    333         a0 = std::max(a0, std::min(a, (int)d[k]));
    334         a0 = std::max(a0, std::min(a, (int)d[k+5]));
    335     }
    336 
    337     int b0 = -a0;
    338     for( k = 0; k < 8; k += 2 )
    339     {
    340         int b = std::max((int)d[k+1], (int)d[k+2]);
    341         b = std::max(b, (int)d[k+3]);
    342         if( b >= b0 )
    343             continue;
    344         b = std::max(b, (int)d[k+4]);
    345 
    346         b0 = std::min(b0, std::max(b, (int)d[k]));
    347         b0 = std::min(b0, std::max(b, (int)d[k+5]));
    348     }
    349 
    350     threshold = -b0-1;
    351 #endif
    352 
    353 #if VERIFY_CORNERS
    354     testCorner(ptr, pixel, K, N, threshold);
    355 #endif
    356     return threshold;
    357 }
    358 
    359 } // namespace cv
    360