Coverage Report

Created: 2022-08-24 06:15

/src/aom/third_party/fastfeat/nonmax.c
Line
Count
Source (jump to first uncovered line)
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
0
#define Compare(X, Y) ((X)>=(Y))
37
38
xy* aom_nonmax_suppression(const xy* corners, const int* scores, int num_corners, int* ret_num_nonmax)
39
0
{
40
0
  int num_nonmax=0;
41
0
  int last_row;
42
0
  int* row_start;
43
0
  int i, j;
44
0
  xy* ret_nonmax;
45
0
  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
0
  int point_above = 0;
50
0
  int point_below = 0;
51
52
53
0
  if(num_corners < 1)
54
0
  {
55
0
    *ret_num_nonmax = 0;
56
0
    return 0;
57
0
  }
58
59
0
  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
0
  last_row = corners[num_corners-1].y;
65
0
  row_start = (int*)malloc((last_row+1)*sizeof(int));
66
67
0
  for(i=0; i < last_row+1; i++)
68
0
    row_start[i] = -1;
69
70
0
  {
71
0
    int prev_row = -1;
72
0
    for(i=0; i< num_corners; i++)
73
0
      if(corners[i].y != prev_row)
74
0
      {
75
0
        row_start[corners[i].y] = i;
76
0
        prev_row = corners[i].y;
77
0
      }
78
0
  }
79
80
81
82
0
  for(i=0; i < sz; i++)
83
0
  {
84
0
    int score = scores[i];
85
0
    xy pos = corners[i];
86
87
    /*Check left */
88
0
    if(i > 0)
89
0
      if(corners[i-1].x == pos.x-1 && corners[i-1].y == pos.y && Compare(scores[i-1], score))
90
0
        continue;
91
92
    /*Check right*/
93
0
    if(i < (sz - 1))
94
0
      if(corners[i+1].x == pos.x+1 && corners[i+1].y == pos.y && Compare(scores[i+1], score))
95
0
        continue;
96
97
    /*Check above (if there is a valid row above)*/
98
0
    if(pos.y > 0)
99
0
      if (row_start[pos.y - 1] != -1)
100
0
      {
101
        /*Make sure that current point_above is one
102
          row above.*/
103
0
        if(corners[point_above].y < pos.y - 1)
104
0
          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
0
        for(; corners[point_above].y < pos.y && corners[point_above].x < pos.x - 1; point_above++)
109
0
        {}
110
111
112
0
        for(j=point_above; corners[j].y < pos.y && corners[j].x <= pos.x + 1; j++)
113
0
        {
114
0
          int x = corners[j].x;
115
0
          if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j], score))
116
0
            goto cont;
117
0
        }
118
119
0
      }
120
121
    /*Check below (if there is anything below)*/
122
0
    if(pos.y >= 0)
123
0
      if (pos.y != last_row && row_start[pos.y + 1] != -1 && point_below < sz) /*Nothing below*/
124
0
      {
125
0
        if(corners[point_below].y < pos.y + 1)
126
0
          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
0
        for(; point_below < sz && corners[point_below].y == pos.y+1 && corners[point_below].x < pos.x - 1; point_below++)
131
0
        {}
132
133
0
        for(j=point_below; j < sz && corners[j].y == pos.y+1 && corners[j].x <= pos.x + 1; j++)
134
0
        {
135
0
          int x = corners[j].x;
136
0
          if( (x == pos.x - 1 || x ==pos.x || x == pos.x+1) && Compare(scores[j],score))
137
0
            goto cont;
138
0
        }
139
0
      }
140
141
0
    ret_nonmax[num_nonmax++] = corners[i];
142
0
cont:
143
0
    ;
144
0
  }
145
146
0
  free(row_start);
147
0
  *ret_num_nonmax = num_nonmax;
148
0
  return ret_nonmax;
149
0
}
150
151
// clang-format on