| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "marin_l_mark_components/omp/include/ops_omp.hpp" | ||
| 2 | |||
| 3 | #include <omp.h> | ||
| 4 | |||
| 5 | #include <algorithm> | ||
| 6 | #include <cstddef> | ||
| 7 | #include <cstdint> | ||
| 8 | #include <numeric> | ||
| 9 | #include <vector> | ||
| 10 | |||
| 11 | #include "marin_l_mark_components/common/include/common.hpp" | ||
| 12 | |||
| 13 | namespace marin_l_mark_components { | ||
| 14 | |||
| 15 | namespace { | ||
| 16 | |||
| 17 | constexpr std::uint64_t kMaxPixels = 100000000ULL; | ||
| 18 | constexpr int kMinRowsPerStripe = 64; | ||
| 19 | |||
| 20 | struct StripeRange { | ||
| 21 | int row_start; | ||
| 22 | int row_end; | ||
| 23 | int base_label; | ||
| 24 | }; | ||
| 25 | |||
| 26 | int FindRoot(std::vector<int> &parent, int x) { | ||
| 27 |
3/4✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 5 times.
|
6 | while (parent[x] != x) { |
| 28 | 1 | parent[x] = parent[parent[x]]; | |
| 29 | x = parent[x]; | ||
| 30 | } | ||
| 31 | return x; | ||
| 32 | } | ||
| 33 | |||
| 34 | 5 | void UnionLabels(std::vector<int> &parent, int a, int b) { | |
| 35 | int root_a = FindRoot(parent, a); | ||
| 36 | int root_b = FindRoot(parent, b); | ||
| 37 |
1/2✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
|
5 | if (root_a == root_b) { |
| 38 | return; | ||
| 39 | } | ||
| 40 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if (root_a < root_b) { |
| 41 | ✗ | parent[root_b] = root_a; | |
| 42 | } else { | ||
| 43 | 5 | parent[root_a] = root_b; | |
| 44 | } | ||
| 45 | } | ||
| 46 | |||
| 47 | StripeRange GetStripeRange(int stripe, int height, int stripe_count, const std::vector<int> &stripe_offsets) { | ||
| 48 | return { | ||
| 49 | .row_start = (stripe * height) / stripe_count, | ||
| 50 | .row_end = ((stripe + 1) * height) / stripe_count, | ||
| 51 | .base_label = 1 + stripe_offsets[static_cast<std::size_t>(stripe)], | ||
| 52 | }; | ||
| 53 | } | ||
| 54 | |||
| 55 | 626 | void AssignPixelLabel(std::vector<int> &labels_flat, std::vector<int> &parent, std::size_t idx, int left_label, | |
| 56 | int top_label, int &next_label) { | ||
| 57 |
2/2✓ Branch 0 taken 468 times.
✓ Branch 1 taken 158 times.
|
626 | if (left_label == 0) { |
| 58 |
2/2✓ Branch 0 taken 395 times.
✓ Branch 1 taken 73 times.
|
468 | if (top_label == 0) { |
| 59 | 395 | parent[static_cast<std::size_t>(next_label)] = next_label; | |
| 60 | 395 | labels_flat[idx] = next_label++; | |
| 61 | 395 | return; | |
| 62 | } | ||
| 63 | 73 | labels_flat[idx] = top_label; | |
| 64 | 73 | return; | |
| 65 | } | ||
| 66 | |||
| 67 |
2/2✓ Branch 0 taken 57 times.
✓ Branch 1 taken 101 times.
|
158 | if (top_label == 0) { |
| 68 | 57 | labels_flat[idx] = left_label; | |
| 69 | 57 | return; | |
| 70 | } | ||
| 71 | |||
| 72 | const int min_label = std::min(left_label, top_label); | ||
| 73 | 101 | labels_flat[idx] = min_label; | |
| 74 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 96 times.
|
101 | if (left_label != top_label) { |
| 75 | 5 | UnionLabels(parent, left_label, top_label); | |
| 76 | } | ||
| 77 | } | ||
| 78 | |||
| 79 | 24 | void ProcessStripe(const std::vector<std::uint8_t> &binary, std::vector<int> &labels_flat, std::vector<int> &parent, | |
| 80 | std::vector<int> &stripe_used_counts, int width, const StripeRange &stripe_range, int stripe) { | ||
| 81 | 24 | int next_label = stripe_range.base_label; | |
| 82 | |||
| 83 |
2/2✓ Branch 0 taken 200 times.
✓ Branch 1 taken 24 times.
|
224 | for (int row = stripe_range.row_start; row < stripe_range.row_end; ++row) { |
| 84 | 200 | const std::size_t row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width); | |
| 85 | 200 | const bool has_top = row > stripe_range.row_start; | |
| 86 |
2/2✓ Branch 0 taken 176 times.
✓ Branch 1 taken 24 times.
|
200 | const std::size_t top_row_offset = has_top ? row_offset - static_cast<std::size_t>(width) : 0; |
| 87 | |||
| 88 |
2/2✓ Branch 0 taken 1888 times.
✓ Branch 1 taken 200 times.
|
2088 | for (int col = 0; col < width; ++col) { |
| 89 |
2/2✓ Branch 0 taken 1262 times.
✓ Branch 1 taken 626 times.
|
1888 | const std::size_t idx = row_offset + static_cast<std::size_t>(col); |
| 90 |
2/2✓ Branch 0 taken 1262 times.
✓ Branch 1 taken 626 times.
|
1888 | if (binary[idx] == 0U) { |
| 91 | 1262 | continue; | |
| 92 | } | ||
| 93 | |||
| 94 |
2/2✓ Branch 0 taken 560 times.
✓ Branch 1 taken 66 times.
|
626 | const int left_label = (col > 0) ? labels_flat[idx - 1ULL] : 0; |
| 95 |
2/2✓ Branch 0 taken 564 times.
✓ Branch 1 taken 62 times.
|
626 | const int top_label = has_top ? labels_flat[top_row_offset + static_cast<std::size_t>(col)] : 0; |
| 96 | 626 | AssignPixelLabel(labels_flat, parent, idx, left_label, top_label, next_label); | |
| 97 | } | ||
| 98 | } | ||
| 99 | |||
| 100 | 24 | stripe_used_counts[static_cast<std::size_t>(stripe)] = next_label - stripe_range.base_label; | |
| 101 | 24 | } | |
| 102 | |||
| 103 | } // namespace | ||
| 104 | |||
| 105 |
1/2✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
|
24 | MarinLMarkComponentsOMP::MarinLMarkComponentsOMP(const InType &in) { |
| 106 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 107 | GetInput() = in; | ||
| 108 | 24 | } | |
| 109 | |||
| 110 | ✗ | bool MarinLMarkComponentsOMP::IsBinary(const Image &img) { | |
| 111 |
2/4✓ Branch 0 taken 200 times.
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
224 | for (const auto &row : img) { |
| 112 |
2/4✓ Branch 0 taken 1888 times.
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
2088 | for (int pixel : row) { |
| 113 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 1888 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
1888 | if (pixel != 0 && pixel != 1) { |
| 114 | return false; | ||
| 115 | } | ||
| 116 | } | ||
| 117 | } | ||
| 118 | return true; | ||
| 119 | } | ||
| 120 | |||
| 121 |
1/2✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
|
24 | bool MarinLMarkComponentsOMP::ValidationImpl() { |
| 122 | const auto &img = GetInput().binary; | ||
| 123 |
2/4✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
|
24 | if (img.empty() || img.front().empty()) { |
| 124 | return false; | ||
| 125 | } | ||
| 126 | |||
| 127 | const std::size_t width = img.front().size(); | ||
| 128 |
2/2✓ Branch 0 taken 200 times.
✓ Branch 1 taken 24 times.
|
224 | for (const auto &row : img) { |
| 129 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 200 times.
|
200 | if (row.size() != width) { |
| 130 | return false; | ||
| 131 | } | ||
| 132 | } | ||
| 133 | return IsBinary(img); | ||
| 134 | } | ||
| 135 | |||
| 136 | 24 | bool MarinLMarkComponentsOMP::PreProcessingImpl() { | |
| 137 |
1/2✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
|
24 | const auto &input_binary = GetInput().binary; |
| 138 | 24 | height_ = static_cast<int>(input_binary.size()); | |
| 139 | 24 | width_ = static_cast<int>(input_binary.front().size()); | |
| 140 | |||
| 141 |
2/4✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
|
24 | if (height_ <= 0 || width_ <= 0) { |
| 142 | return false; | ||
| 143 | } | ||
| 144 | |||
| 145 | 24 | const std::uint64_t pixels = static_cast<std::uint64_t>(height_) * static_cast<std::uint64_t>(width_); | |
| 146 |
1/2✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
|
24 | if (pixels > kMaxPixels) { |
| 147 | return false; | ||
| 148 | } | ||
| 149 | |||
| 150 | 24 | binary_.assign(static_cast<std::size_t>(pixels), 0); | |
| 151 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
|
24 | labels_flat_.assign(static_cast<std::size_t>(pixels), 0); |
| 152 | labels_.clear(); | ||
| 153 | 24 | parent_.assign(static_cast<std::size_t>(pixels) + 1ULL, 0); | |
| 154 | 24 | root_to_compact_.assign(static_cast<std::size_t>(pixels) + 1ULL, 0); | |
| 155 | 24 | root_generation_.assign(static_cast<std::size_t>(pixels) + 1ULL, 0); | |
| 156 | 24 | max_label_id_ = 0; | |
| 157 | 24 | generation_id_ = 1; | |
| 158 | |||
| 159 | 24 | stripe_count_ = std::max(1, omp_get_max_threads()); | |
| 160 | stripe_count_ = std::min(stripe_count_, height_); | ||
| 161 |
1/2✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
|
24 | stripe_count_ = std::min(stripe_count_, std::max(1, height_ / kMinRowsPerStripe)); |
| 162 | 24 | stripe_offsets_.assign(static_cast<std::size_t>(stripe_count_) + 1ULL, 0); | |
| 163 | 24 | stripe_used_counts_.assign(static_cast<std::size_t>(stripe_count_), 0); | |
| 164 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
|
48 | for (int stripe = 0; stripe < stripe_count_; ++stripe) { |
| 165 | 24 | const int row_start = (stripe * height_) / stripe_count_; | |
| 166 | 24 | const int row_end = ((stripe + 1) * height_) / stripe_count_; | |
| 167 | 24 | stripe_offsets_[static_cast<std::size_t>(stripe) + 1ULL] = (row_end - row_start) * width_; | |
| 168 | } | ||
| 169 | std::partial_sum(stripe_offsets_.begin(), stripe_offsets_.end(), stripe_offsets_.begin()); | ||
| 170 | 24 | max_label_id_ = stripe_offsets_[static_cast<std::size_t>(stripe_count_)]; | |
| 171 | |||
| 172 | #ifdef _MSC_VER | ||
| 173 | # pragma omp parallel for schedule(static) | ||
| 174 | #else | ||
| 175 | 24 | # pragma omp parallel for default(none) shared(binary_, height_, input_binary, width_) schedule(static) | |
| 176 | #endif | ||
| 177 | for (int row = 0; row < height_; ++row) { | ||
| 178 | const std::size_t row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width_); | ||
| 179 | for (int col = 0; col < width_; ++col) { | ||
| 180 | binary_[row_offset + static_cast<std::size_t>(col)] = | ||
| 181 | static_cast<std::uint8_t>(input_binary[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)]); | ||
| 182 | } | ||
| 183 | } | ||
| 184 | |||
| 185 | 24 | return true; | |
| 186 | } | ||
| 187 | |||
| 188 | 24 | bool MarinLMarkComponentsOMP::RunImpl() { | |
| 189 | 24 | FirstPassOMP(); | |
| 190 | 24 | MergeStripeBorders(); | |
| 191 | 24 | SecondPassOMP(); | |
| 192 | 24 | return true; | |
| 193 | } | ||
| 194 | |||
| 195 | 24 | void MarinLMarkComponentsOMP::FirstPassOMP() { | |
| 196 | const auto labels_count = static_cast<std::ptrdiff_t>(labels_flat_.size()); | ||
| 197 | #ifdef _MSC_VER | ||
| 198 | # pragma omp parallel for schedule(static) | ||
| 199 | #else | ||
| 200 | 24 | # pragma omp parallel for default(none) shared(labels_count, labels_flat_) schedule(static) | |
| 201 | #endif | ||
| 202 | for (std::ptrdiff_t i = 0; i < labels_count; ++i) { | ||
| 203 | labels_flat_[static_cast<std::size_t>(i)] = 0; | ||
| 204 | } | ||
| 205 | |||
| 206 | #ifdef _MSC_VER | ||
| 207 | # pragma omp parallel for schedule(static) | ||
| 208 | #else | ||
| 209 | 24 | # pragma omp parallel for default(none) shared(binary_, height_, labels_flat_, parent_, stripe_count_, \ | |
| 210 | stripe_offsets_, stripe_used_counts_, width_) schedule(static) | ||
| 211 | #endif | ||
| 212 | for (int stripe = 0; stripe < stripe_count_; ++stripe) { | ||
| 213 | const StripeRange stripe_range = GetStripeRange(stripe, height_, stripe_count_, stripe_offsets_); | ||
| 214 | ProcessStripe(binary_, labels_flat_, parent_, stripe_used_counts_, width_, stripe_range, stripe); | ||
| 215 | } | ||
| 216 | 24 | } | |
| 217 | |||
| 218 | 24 | void MarinLMarkComponentsOMP::MergeStripeBorders() { | |
| 219 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | for (int stripe = 0; stripe < stripe_count_ - 1; ++stripe) { |
| 220 | ✗ | const int border_row = ((stripe + 1) * height_) / stripe_count_; | |
| 221 | ✗ | const std::size_t top_row_offset = static_cast<std::size_t>(border_row - 1) * static_cast<std::size_t>(width_); | |
| 222 | ✗ | const std::size_t bottom_row_offset = static_cast<std::size_t>(border_row) * static_cast<std::size_t>(width_); | |
| 223 | ✗ | for (int col = 0; col < width_; ++col) { | |
| 224 | ✗ | const std::size_t top_idx = top_row_offset + static_cast<std::size_t>(col); | |
| 225 | ✗ | const std::size_t bottom_idx = bottom_row_offset + static_cast<std::size_t>(col); | |
| 226 | ✗ | if ((binary_[top_idx] != 0U) && (binary_[bottom_idx] != 0U)) { | |
| 227 | ✗ | const int top_label = labels_flat_[top_idx]; | |
| 228 | ✗ | const int bottom_label = labels_flat_[bottom_idx]; | |
| 229 | ✗ | if (top_label > 0 && bottom_label > 0 && top_label != bottom_label) { | |
| 230 | ✗ | UnionLabels(parent_, top_label, bottom_label); | |
| 231 | } | ||
| 232 | } | ||
| 233 | } | ||
| 234 | } | ||
| 235 | |||
| 236 | #ifdef _MSC_VER | ||
| 237 | # pragma omp parallel for schedule(static) | ||
| 238 | #else | ||
| 239 | 24 | # pragma omp parallel for default(none) shared(parent_, stripe_count_, stripe_offsets_, stripe_used_counts_) \ | |
| 240 | schedule(static) | ||
| 241 | #endif | ||
| 242 | for (int stripe = 0; stripe < stripe_count_; ++stripe) { | ||
| 243 | const int base_label = 1 + stripe_offsets_[static_cast<std::size_t>(stripe)]; | ||
| 244 | const int used_count = stripe_used_counts_[static_cast<std::size_t>(stripe)]; | ||
| 245 | for (int label = base_label; label < base_label + used_count; ++label) { | ||
| 246 | parent_[static_cast<std::size_t>(label)] = FindRoot(parent_, label); | ||
| 247 | } | ||
| 248 | } | ||
| 249 | 24 | } | |
| 250 | |||
| 251 | 24 | void MarinLMarkComponentsOMP::SecondPassOMP() { | |
| 252 |
2/4✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
|
24 | if (height_ == 0 || width_ == 0) { |
| 253 | return; | ||
| 254 | } | ||
| 255 | |||
| 256 |
1/2✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
|
24 | if (max_label_id_ == 0) { |
| 257 | return; | ||
| 258 | } | ||
| 259 | |||
| 260 | 24 | ++generation_id_; | |
| 261 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | if (generation_id_ == 0) { |
| 262 | ✗ | generation_id_ = 1; | |
| 263 | std::ranges::fill(root_generation_, 0); | ||
| 264 | } | ||
| 265 | |||
| 266 | int next_id = 1; | ||
| 267 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
|
48 | for (int stripe = 0; stripe < stripe_count_; ++stripe) { |
| 268 | 24 | const int base_label = 1 + stripe_offsets_[static_cast<std::size_t>(stripe)]; | |
| 269 | 24 | const int used_count = stripe_used_counts_[static_cast<std::size_t>(stripe)]; | |
| 270 |
2/2✓ Branch 0 taken 395 times.
✓ Branch 1 taken 24 times.
|
419 | for (int label = base_label; label < base_label + used_count; ++label) { |
| 271 |
2/2✓ Branch 0 taken 390 times.
✓ Branch 1 taken 5 times.
|
395 | const int root = parent_[static_cast<std::size_t>(label)]; |
| 272 |
2/2✓ Branch 0 taken 390 times.
✓ Branch 1 taken 5 times.
|
395 | if (root_generation_[static_cast<std::size_t>(root)] != generation_id_) { |
| 273 | 390 | root_generation_[static_cast<std::size_t>(root)] = generation_id_; | |
| 274 | 390 | root_to_compact_[static_cast<std::size_t>(root)] = next_id++; | |
| 275 | } | ||
| 276 | } | ||
| 277 | } | ||
| 278 | |||
| 279 | 24 | const std::size_t pixels = static_cast<std::size_t>(height_) * static_cast<std::size_t>(width_); | |
| 280 | 24 | const auto pixels_count = static_cast<int64_t>(pixels); | |
| 281 | #ifdef _MSC_VER | ||
| 282 | # pragma omp parallel for schedule(static) | ||
| 283 | #else | ||
| 284 | 24 | # pragma omp parallel for default(none) shared(labels_flat_, parent_, pixels_count, root_to_compact_) schedule(static) | |
| 285 | #endif | ||
| 286 | for (int64_t idx = 0; idx < pixels_count; ++idx) { | ||
| 287 | const int label = labels_flat_[static_cast<std::size_t>(idx)]; | ||
| 288 | if (label == 0) { | ||
| 289 | continue; | ||
| 290 | } | ||
| 291 | |||
| 292 | const int root = parent_[static_cast<std::size_t>(label)]; | ||
| 293 | labels_flat_[static_cast<std::size_t>(idx)] = root_to_compact_[static_cast<std::size_t>(root)]; | ||
| 294 | } | ||
| 295 | } | ||
| 296 | |||
| 297 | 24 | bool MarinLMarkComponentsOMP::PostProcessingImpl() { | |
| 298 | 24 | ConvertLabelsToOutput(); | |
| 299 | 24 | OutType out; | |
| 300 |
1/2✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
|
24 | out.labels = labels_; |
| 301 | GetOutput() = out; | ||
| 302 | 24 | return true; | |
| 303 | } | ||
| 304 | |||
| 305 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | void MarinLMarkComponentsOMP::ConvertLabelsToOutput() { |
| 306 | labels_.clear(); | ||
| 307 | 24 | labels_.resize(static_cast<std::size_t>(height_)); | |
| 308 | |||
| 309 | #ifdef _MSC_VER | ||
| 310 | # pragma omp parallel for schedule(static) | ||
| 311 | #else | ||
| 312 | 24 | # pragma omp parallel for default(none) shared(height_, labels_, labels_flat_, width_) schedule(static) | |
| 313 | #endif | ||
| 314 | for (int row = 0; row < height_; ++row) { | ||
| 315 | labels_[static_cast<std::size_t>(row)].resize(static_cast<std::size_t>(width_)); | ||
| 316 | const std::size_t row_offset = static_cast<std::size_t>(row) * static_cast<std::size_t>(width_); | ||
| 317 | for (int col = 0; col < width_; ++col) { | ||
| 318 | labels_[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)] = | ||
| 319 | labels_flat_[row_offset + static_cast<std::size_t>(col)]; | ||
| 320 | } | ||
| 321 | } | ||
| 322 | 24 | } | |
| 323 | |||
| 324 | } // namespace marin_l_mark_components | ||
| 325 |