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 <assert.h>
33 #include <stdlib.h>
34 #include "fast.h"
35
36
37 #define Compare(X, Y) ((X)>=(Y))
38
aom_nonmax_suppression(const xy * corners,const int * scores,int num_corners,int ** ret_scores,int * ret_num_nonmax)39 xy* aom_nonmax_suppression(const xy* corners, const int* scores, int num_corners,
40 int** ret_scores, int* ret_num_nonmax)
41 {
42 int num_nonmax=0;
43 int last_row;
44 int* row_start;
45 int i, j;
46 xy* ret_nonmax;
47 int* nonmax_scores;
48 const int sz = (int)num_corners;
49
50 /*Point above points (roughly) to the pixel above the one of interest, if there
51 is a feature there.*/
52 int point_above = 0;
53 int point_below = 0;
54
55 *ret_scores = 0;
56 *ret_num_nonmax = -1;
57 if(!(corners && scores) || num_corners < 1)
58 {
59 *ret_num_nonmax = 0;
60 return 0;
61 }
62
63 ret_nonmax = (xy*)malloc(num_corners * sizeof(xy));
64 if(!ret_nonmax)
65 {
66 return 0;
67 }
68
69 nonmax_scores = (int*)malloc(num_corners * sizeof(*nonmax_scores));
70 if (!nonmax_scores)
71 {
72 free(ret_nonmax);
73 return 0;
74 }
75
76 /* Find where each row begins
77 (the corners are output in raster scan order). A beginning of -1 signifies
78 that there are no corners on that row. */
79 last_row = corners[num_corners-1].y;
80 row_start = (int*)malloc((last_row+1)*sizeof(int));
81 if(!row_start)
82 {
83 free(ret_nonmax);
84 free(nonmax_scores);
85 return 0;
86 }
87
88 for(i=0; i < last_row+1; i++)
89 row_start[i] = -1;
90
91 {
92 int prev_row = -1;
93 for(i=0; i< num_corners; i++)
94 if(corners[i].y != prev_row)
95 {
96 row_start[corners[i].y] = i;
97 prev_row = corners[i].y;
98 }
99 }
100
101
102
103 for(i=0; i < sz; i++)
104 {
105 int score = scores[i];
106 xy pos = corners[i];
107 assert(pos.y <= last_row);
108
109 /*Check left */
110 if(i > 0)
111 if(corners[i-1].x == pos.x-1 && corners[i-1].y == pos.y && Compare(scores[i-1], score))
112 continue;
113
114 /*Check right*/
115 if(i < (sz - 1))
116 if(corners[i+1].x == pos.x+1 && corners[i+1].y == pos.y && Compare(scores[i+1], score))
117 continue;
118
119 /*Check above (if there is a valid row above)*/
120 if(pos.y > 0 && row_start[pos.y - 1] != -1)
121 {
122 /*Make sure that current point_above is one
123 row above.*/
124 if(corners[point_above].y < pos.y - 1)
125 point_above = row_start[pos.y-1];
126
127 /*Make point_above point to the first of the pixels above the current point,
128 if it exists.*/
129 for(; corners[point_above].y < pos.y && corners[point_above].x < pos.x - 1; point_above++)
130 {}
131
132
133 for(j=point_above; corners[j].y < pos.y && 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
142 /*Check below (if there is anything below)*/
143 if (pos.y + 1 < last_row+1 && row_start[pos.y + 1] != -1 && point_below < sz) /*Nothing below*/
144 {
145 if(corners[point_below].y < pos.y + 1)
146 point_below = row_start[pos.y+1];
147
148 /* Make point below point to one of the pixels belowthe current point, if it
149 exists.*/
150 for(; point_below < sz && corners[point_below].y == pos.y+1 && corners[point_below].x < pos.x - 1; point_below++)
151 {}
152
153 for(j=point_below; j < sz && corners[j].y == pos.y+1 && corners[j].x <= pos.x + 1; j++)
154 {
155 int x = corners[j].x;
156 if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j],score))
157 goto cont;
158 }
159 }
160
161 ret_nonmax[num_nonmax] = corners[i];
162 nonmax_scores[num_nonmax] = scores[i];
163 num_nonmax++;
164 cont:
165 ;
166 }
167
168 free(row_start);
169 *ret_scores = nonmax_scores;
170 *ret_num_nonmax = num_nonmax;
171 return ret_nonmax;
172 }
173
174 // clang-format on
175