running_max_vertical_2d.cpp 7.38 KB
Newer Older
Edwin Carlinet's avatar
Edwin Carlinet committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <fmt/core.h>
#include <mln/morpho/experimental/private/dilation_vertical_block2d.hpp>


#include <functional>
#include <gtest/gtest.h>
#include <numeric>
#include <vector>
#include <range/v3/view/span.hpp>


template <class T, class Compare>
void running_max_v_2d_naive(const T* input, int width, int height, int k, Compare cmp, T* output)
{

  for (int y = 0; y < height; ++y)
  {
    // Compute the Max input on the range [i - k, i + k]
    const T* begin = input + std::max(y - k, 0) * width;
    const T* end   = input + std::min(y + k + 1, height) * width;
    T*       out   = output + y * width;

    std::memcpy(out, begin, width * sizeof(T));
    begin += width;

    for (; begin != end; begin += width)
      std::transform(begin, begin + width, out, out, [cmp](auto a, auto b) { return std::max(a, b, cmp); });
  }
}

template <class T, class Compare>
void running_max_v_2d_g(const T* input, int width, int height, int k, Compare cmp, T* output)
{
  for (int y = 0; y < height; ++y)
  {
    // Compute the Max input on the range [⌊i/k⌋*k, i]
    const T* begin = input + (y / k) * k * width;
    const T* end   = input + std::min(height, y + 1) * width;
    T*       out   = output + y * width;

    std::memcpy(out, begin, width * sizeof(T));
    begin += width;

    for (; begin != end; begin += width)
      std::transform(begin, begin + width, out, out, [cmp](auto a, auto b) { return std::max(a, b, cmp); });
  }
}

template <class T, class Compare>
void running_max_v_2d_h(const T* input, int width, int height, int k, Compare cmp, T* output)
{
  for (int y = 0; y < height; ++y)
  {
    // Compute the Max input on the range [⌊i/k⌋*k, i]
    const T* begin = input + y * width;
    const T* end   = input + std::min(height, (y / k + 1) * k) * width;
    T*       out   = output + y * width;

    std::memcpy(out, begin, width * sizeof(T));
    begin += width;

    for (; begin != end; begin += width)
      std::transform(begin, begin + width, out, out, [cmp](auto a, auto b) { return std::max(a, b, cmp); });
  }
}

template <class T>
void compare_span2d(const T* a, const T* b, int width, int height)
{
  for (int y = 0; y < height; ++y)
    EXPECT_EQ(::ranges::make_span(a + y * width, width), ::ranges::make_span(b + y * width, width)) << "at line: " << y;
}


class RunningMax2dBase : public ::testing::TestWithParam<std::tuple<int, int>>
{
public:


  void Check(bool increasing) const
  {
    int n      = std::get<0>(this->GetParam());
    int radius = std::get<1>(this->GetParam());

    int width      = n;
    int height     = n;
    int stride     = width;

    int size       = width * height;
    int total_size = width * (height + 2 * radius);
    int chunk_size = 2 * radius + 1;

    std::vector<int> input(size);
    if (increasing)
      std::iota(input.begin(), input.end(), 42);
    else
      std::iota(input.rbegin(), input.rend(), 42);

    std::vector<int> f(total_size, m_zero);
    std::copy(input.begin(), input.end(), f.data() + radius * width);

    // Generate references
    std::vector<int> gref(total_size);
    std::vector<int> href(total_size);
    std::vector<int> fref(size);
    running_max_v_2d_g(f.data(), width, 2 * radius + height, chunk_size, m_cmp, gref.data());
    running_max_v_2d_h(f.data(), width, 2 * radius + height, chunk_size, m_cmp, href.data());
    running_max_v_2d_naive(input.data(), width, height, radius, m_cmp, fref.data());

    // Run algorithm
    std::vector<int> g(total_size);
    std::vector<int> h(total_size);


    sup_t sup = {m_sup, m_sup_vec};
    mln::morpho::experimental::details::vertical_running_max_algo_t<int, sup_t> algo(sup);
Edwin Carlinet's avatar
Edwin Carlinet committed
117
118
    
    mln::experimental::box2d roi(width, height);
Edwin Carlinet's avatar
Edwin Carlinet committed
119
120
121
    algo.running_max_block2d((std::byte*)(f.data() + radius * stride), //
                             (std::byte*)(g.data() + radius * stride), //
                             (std::byte*)(h.data() + radius * stride), //
Edwin Carlinet's avatar
Edwin Carlinet committed
122
                             stride * sizeof(int), stride * sizeof(int), stride * sizeof(int), roi, radius,
Edwin Carlinet's avatar
Edwin Carlinet committed
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
                             true);

    compare_span2d(gref.data(), g.data(), width, height + 2 * radius);
    compare_span2d(href.data(), h.data(), width, height + 2 * radius);
    compare_span2d(fref.data(), f.data() + radius * stride, width, height);
    //EXPECT_EQ(href, h);
    //EXPECT_EQ(::ranges::make_span(fref.data(), size), ::ranges::make_span(f.data() + radius * width, size));
  }


protected:
  using simd_t = std::experimental::native_simd<int>;

  struct sup_t
  {
    int    operator()(int x, int y) const { return m_sup(x, y); }
    simd_t operator()(const simd_t& x, const simd_t& y) const { return m_sup_vec(x, y); }

    std::function<int(int, int)>                         m_sup;
    std::function<simd_t(const simd_t&, const simd_t&)>  m_sup_vec;
  };


  std::function<int(int, int)>                         m_sup;
  std::function<simd_t(const simd_t&, const simd_t&)>  m_sup_vec;
  std::function<bool(int, int)>                        m_cmp;
  int                                                  m_zero;
};

class RunningMax2D : public RunningMax2dBase
{
public:


  RunningMax2D()
  {
    m_sup  = [](int x, int y) { return std::max(x, y); };
    m_sup_vec  = [](const simd_t& x, const simd_t& y) { return std::experimental::max(x, y); };
    m_zero = 0;
    m_cmp  = std::less<int>();
  }
};

class RunningMin2D : public RunningMax2dBase
{
public:
  RunningMin2D()
  {
    m_sup  = [](int x, int y) { return std::min(x, y); };
    m_sup_vec  = [](const simd_t& x, const simd_t& y) { return std::experimental::min(x, y); };
    m_zero = 255;
    m_cmp  = std::greater<int>();
  }
};

TEST_P(RunningMax2D, check)
{
  this->Check(true);
  this->Check(false);
}

TEST_P(RunningMin2D, check)
{
  this->Check(true);
  this->Check(false);
}




INSTANTIATE_TEST_CASE_P(se_leq_size, RunningMax2D,
                        ::testing::Values(std::make_tuple(0, 0),    // Identity
                                          std::make_tuple(12, 0),   // Identity
                                          std::make_tuple(12, 1),   // radius = 1
                                          std::make_tuple(13, 1),   // radius = 1
                                          std::make_tuple(14, 1),   // radius = 1
                                          std::make_tuple(12, 3),   // radius = 3
                                          std::make_tuple(13, 3),   // radius = 3
                                          std::make_tuple(14, 3),   // radius = 3
                                          std::make_tuple(13, 6))); // n == k

INSTANTIATE_TEST_CASE_P(se_ge_size_, RunningMax2D, ::testing::Values(std::make_tuple(12, 6)));

INSTANTIATE_TEST_CASE_P(se_leq_size, RunningMin2D,
                        ::testing::Values(std::make_tuple(0, 0),    // Identity
                                          std::make_tuple(12, 0),   // Identity
                                          std::make_tuple(12, 1),   // radius = 1
                                          std::make_tuple(13, 1),   // radius = 1
                                          std::make_tuple(14, 1),   // radius = 1
                                          std::make_tuple(12, 3),   // radius = 3
                                          std::make_tuple(13, 3),   // radius = 3
                                          std::make_tuple(14, 3),   // radius = 3
                                          std::make_tuple(13, 6))); // n == k

INSTANTIATE_TEST_CASE_P(se_ge_size_, RunningMin2D, ::testing::Values(std::make_tuple(12, 6)));