• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright (c) 2006, 2008 Edward Rosten
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions
6 // are met:
7 //
8 //  *Redistributions of source code must retain the above copyright
9 //   notice, this list of conditions and the following disclaimer.
10 //
11 //  *Redistributions in binary form must reproduce the above copyright
12 //   notice, this list of conditions and the following disclaimer in the
13 //   documentation and/or other materials provided with the distribution.
14 //
15 //  *Neither the name of the University of Cambridge nor the names of
16 //   its contributors may be used to endorse or promote products derived
17 //   from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
23 // OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 
31 // clang-format off
32 #include <stdlib.h>
33 #include "fast.h"
34 
35 
36 #define Compare(X, Y) ((X)>=(Y))
37 
aom_nonmax_suppression(const xy * corners,const int * scores,int num_corners,int * ret_num_nonmax)38 xy* aom_nonmax_suppression(const xy* corners, const int* scores, int num_corners, int* ret_num_nonmax)
39 {
40   int num_nonmax=0;
41   int last_row;
42   int* row_start;
43   int i, j;
44   xy* ret_nonmax;
45   const int sz = (int)num_corners;
46 
47   /*Point above points (roughly) to the pixel above the one of interest, if there
48     is a feature there.*/
49   int point_above = 0;
50   int point_below = 0;
51 
52 
53   if(num_corners < 1)
54   {
55     *ret_num_nonmax = 0;
56     return 0;
57   }
58 
59   ret_nonmax = (xy*)malloc(num_corners * sizeof(xy));
60 
61   /* Find where each row begins
62      (the corners are output in raster scan order). A beginning of -1 signifies
63      that there are no corners on that row. */
64   last_row = corners[num_corners-1].y;
65   row_start = (int*)malloc((last_row+1)*sizeof(int));
66 
67   for(i=0; i < last_row+1; i++)
68     row_start[i] = -1;
69 
70   {
71     int prev_row = -1;
72     for(i=0; i< num_corners; i++)
73       if(corners[i].y != prev_row)
74       {
75         row_start[corners[i].y] = i;
76         prev_row = corners[i].y;
77       }
78   }
79 
80 
81 
82   for(i=0; i < sz; i++)
83   {
84     int score = scores[i];
85     xy pos = corners[i];
86 
87     /*Check left */
88     if(i > 0)
89       if(corners[i-1].x == pos.x-1 && corners[i-1].y == pos.y && Compare(scores[i-1], score))
90         continue;
91 
92     /*Check right*/
93     if(i < (sz - 1))
94       if(corners[i+1].x == pos.x+1 && corners[i+1].y == pos.y && Compare(scores[i+1], score))
95         continue;
96 
97     /*Check above (if there is a valid row above)*/
98     if(pos.y > 0)
99       if (row_start[pos.y - 1] != -1)
100       {
101         /*Make sure that current point_above is one
102           row above.*/
103         if(corners[point_above].y < pos.y - 1)
104           point_above = row_start[pos.y-1];
105 
106         /*Make point_above point to the first of the pixels above the current point,
107           if it exists.*/
108         for(; corners[point_above].y < pos.y && corners[point_above].x < pos.x - 1; point_above++)
109         {}
110 
111 
112         for(j=point_above; corners[j].y < pos.y && corners[j].x <= pos.x + 1; j++)
113         {
114           int x = corners[j].x;
115           if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j], score))
116             goto cont;
117         }
118 
119       }
120 
121     /*Check below (if there is anything below)*/
122     if(pos.y >= 0)
123       if (pos.y != last_row && row_start[pos.y + 1] != -1 && point_below < sz) /*Nothing below*/
124       {
125         if(corners[point_below].y < pos.y + 1)
126           point_below = row_start[pos.y+1];
127 
128         /* Make point below point to one of the pixels belowthe current point, if it
129            exists.*/
130         for(; point_below < sz && corners[point_below].y == pos.y+1 && corners[point_below].x < pos.x - 1; point_below++)
131         {}
132 
133         for(j=point_below; j < sz && corners[j].y == pos.y+1 && corners[j].x <= pos.x + 1; j++)
134         {
135           int x = corners[j].x;
136           if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j],score))
137             goto cont;
138         }
139       }
140 
141     ret_nonmax[num_nonmax++] = corners[i];
142 cont:
143     ;
144   }
145 
146   free(row_start);
147   *ret_num_nonmax = num_nonmax;
148   return ret_nonmax;
149 }
150 
151 // clang-format on
152