dcv.features.corner.fast.nonmax source code

1 module dcv.features.corner.fast.nonmax;
2 
3 /**
4  * Authors: Edward Rosten
5  * Copyright: Copyright (c) 2006, 2008 Edward Rosten, All rights reserved.
6  * 
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 
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  * Additional notice:
36  * Module integrates FAST implementation present in the Edward Rosten's
37  * github repository: https://github.com/edrosten/fast-C-src
38  */
39 
40 import core.stdc.stdlib : malloc, free, realloc;
41 
42 import dcv.features.corner.fast.base;
43 
44 alias Compare = (X, Y) => (X>=Y);
45 
46 
47 xy* nonmax_suppression(const xy* corners, const int* scores, int num_corners, int* ret_num_nonmax)
48 {
49     int num_nonmax=0;
50     int last_row;
51     int* row_start;
52     int i, j;
53     xy* ret_nonmax;
54     const int sz = cast(int)num_corners; 
55 
56     /*Point above points (roughly) to the pixel above the one of interest, if there
57      is a feature there.*/
58     int point_above = 0;
59     int point_below = 0;
60 
61     
62     if(num_corners < 1)
63     {
64         *ret_num_nonmax = 0;
65         return null;
66     }
67 
68     ret_nonmax = cast(xy*)malloc(num_corners * xy.sizeof);
69 
70     /* Find where each row begins
71      (the corners are output in raster scan order). A beginning of -1 signifies
72      that there are no corners on that row. */
73     last_row = corners[num_corners-1].y;
74     row_start = cast(int*)malloc((last_row+1)*int.sizeof);
75 
76     for(i=0; i < last_row+1; i++)
77         row_start[i] = -1;
78     
79     {
80         int prev_row = -1;
81         for(i=0; i< num_corners; i++)
82             if(corners[i].y != prev_row)
83         {
84             row_start[corners[i].y] = i;
85             prev_row = corners[i].y;
86         }
87     }
88     
89     
90     
91     for(i=0; i < sz; i++)
92     {
93         int score = scores[i];
94         xy pos = corners[i];
95         
96         /*Check left */
97         if(i > 0)
98             if(corners[i-1].x == pos.x-1 && corners[i-1].y == pos.y && Compare(scores[i-1], score))
99                 continue;
100         
101         /*Check right*/
102         if(i < (sz - 1))
103             if(corners[i+1].x == pos.x+1 && corners[i+1].y == pos.y && Compare(scores[i+1], score))
104                 continue;
105         
106         /*Check above (if there is a valid row above)*/
107         if(pos.y != 0 && row_start[pos.y - 1] != -1) 
108         {
109             /*Make sure that current point_above is one
110              row above.*/
111             if(corners[point_above].y < pos.y - 1)
112                 point_above = row_start[pos.y-1];
113             
114             /*Make point_above point to the first of the pixels above the current point,
115              if it exists.*/
116             for(; corners[point_above].y < pos.y && corners[point_above].x < pos.x - 1; point_above++)
117             {}
118             
119             
120             for(j=point_above; corners[j].y < pos.y && corners[j].x <= pos.x + 1; j++)
121             {
122                 int x = corners[j].x;
123                 if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j], score))
124                     goto cont;
125             }
126             
127         }
128         
129         /*Check below (if there is anything below)*/
130         if(pos.y != last_row && row_start[pos.y + 1] != -1 && point_below < sz) /*Nothing below*/
131         {
132             if(corners[point_below].y < pos.y + 1)
133                 point_below = row_start[pos.y+1];
134             
135             /* Make point below point to one of the pixels belowthe current point, if it
136              exists.*/
137             for(; point_below < sz && corners[point_below].y == pos.y+1 && corners[point_below].x < pos.x - 1; point_below++)
138             {}
139 
140             for(j=point_below; j < sz && corners[j].y == pos.y+1 && corners[j].x <= pos.x + 1; j++)
141             {
142                 int x = corners[j].x;
143                 if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j],score))
144                     goto cont;
145             }
146         }
147         
148         ret_nonmax[num_nonmax++] = corners[i];
149     cont:
150         ;
151     }
152 
153     free(row_start);
154     *ret_num_nonmax = num_nonmax;
155     return ret_nonmax;
156 }