1 // clang-format off
2 #include <stdlib.h>
3 #include "fast.h"
4
5
6 #define Compare(X, Y) ((X)>=(Y))
7
nonmax_suppression(const xy * corners,const int * scores,int num_corners,int * ret_num_nonmax)8 xy* nonmax_suppression(const xy* corners, const int* scores, int num_corners, int* ret_num_nonmax)
9 {
10 int num_nonmax=0;
11 int last_row;
12 int* row_start;
13 int i, j;
14 xy* ret_nonmax;
15 const int sz = (int)num_corners;
16
17 /*Point above points (roughly) to the pixel above the one of interest, if there
18 is a feature there.*/
19 int point_above = 0;
20 int point_below = 0;
21
22
23 if(num_corners < 1)
24 {
25 *ret_num_nonmax = 0;
26 return 0;
27 }
28
29 ret_nonmax = (xy*)malloc(num_corners * sizeof(xy));
30
31 /* Find where each row begins
32 (the corners are output in raster scan order). A beginning of -1 signifies
33 that there are no corners on that row. */
34 last_row = corners[num_corners-1].y;
35 row_start = (int*)malloc((last_row+1)*sizeof(int));
36
37 for(i=0; i < last_row+1; i++)
38 row_start[i] = -1;
39
40 {
41 int prev_row = -1;
42 for(i=0; i< num_corners; i++)
43 if(corners[i].y != prev_row)
44 {
45 row_start[corners[i].y] = i;
46 prev_row = corners[i].y;
47 }
48 }
49
50
51
52 for(i=0; i < sz; i++)
53 {
54 int score = scores[i];
55 xy pos = corners[i];
56
57 /*Check left */
58 if(i > 0)
59 if(corners[i-1].x == pos.x-1 && corners[i-1].y == pos.y && Compare(scores[i-1], score))
60 continue;
61
62 /*Check right*/
63 if(i < (sz - 1))
64 if(corners[i+1].x == pos.x+1 && corners[i+1].y == pos.y && Compare(scores[i+1], score))
65 continue;
66
67 /*Check above (if there is a valid row above)*/
68 if(pos.y > 0)
69 if (row_start[pos.y - 1] != -1)
70 {
71 /*Make sure that current point_above is one
72 row above.*/
73 if(corners[point_above].y < pos.y - 1)
74 point_above = row_start[pos.y-1];
75
76 /*Make point_above point to the first of the pixels above the current point,
77 if it exists.*/
78 for(; corners[point_above].y < pos.y && corners[point_above].x < pos.x - 1; point_above++)
79 {}
80
81
82 for(j=point_above; corners[j].y < pos.y && corners[j].x <= pos.x + 1; j++)
83 {
84 int x = corners[j].x;
85 if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j], score))
86 goto cont;
87 }
88
89 }
90
91 /*Check below (if there is anything below)*/
92 if(pos.y >= 0)
93 if (pos.y != last_row && row_start[pos.y + 1] != -1 && point_below < sz) /*Nothing below*/
94 {
95 if(corners[point_below].y < pos.y + 1)
96 point_below = row_start[pos.y+1];
97
98 /* Make point below point to one of the pixels belowthe current point, if it
99 exists.*/
100 for(; point_below < sz && corners[point_below].y == pos.y+1 && corners[point_below].x < pos.x - 1; point_below++)
101 {}
102
103 for(j=point_below; j < sz && corners[j].y == pos.y+1 && corners[j].x <= pos.x + 1; j++)
104 {
105 int x = corners[j].x;
106 if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j],score))
107 goto cont;
108 }
109 }
110
111 ret_nonmax[num_nonmax++] = corners[i];
112 cont:
113 ;
114 }
115
116 free(row_start);
117 *ret_num_nonmax = num_nonmax;
118 return ret_nonmax;
119 }
120
121 // clang-format on
122