From d1755701779b88389dc1d2e30d2430320a17f78e Mon Sep 17 00:00:00 2001 From: jaseg Date: Sun, 30 May 2021 19:39:45 +0200 Subject: Add beginnings of minimalist contour tracing code --- .gitmodules | 6 + svg-flatten/src/nopencv.cpp | 157 +++++++++++++++++++++++ svg-flatten/src/nopencv.hpp | 98 ++++++++++++++ svg-flatten/src/nopencv_test.cpp | 198 +++++++++++++++++++++++++++++ svg-flatten/testdata/blank.png | Bin 0 -> 450 bytes svg-flatten/testdata/blob-border-w.png | Bin 0 -> 463 bytes svg-flatten/testdata/blobs-borders.png | Bin 0 -> 469 bytes svg-flatten/testdata/blobs-corners.png | Bin 0 -> 469 bytes svg-flatten/testdata/blobs-crossing.png | Bin 0 -> 474 bytes svg-flatten/testdata/cross.png | Bin 0 -> 464 bytes svg-flatten/testdata/letter-e.png | Bin 0 -> 471 bytes svg-flatten/testdata/paper-example-inv.png | Bin 0 -> 471 bytes svg-flatten/testdata/paper-example.png | Bin 0 -> 462 bytes svg-flatten/testdata/single-px-inv.png | Bin 0 -> 461 bytes svg-flatten/testdata/single-px.png | Bin 0 -> 453 bytes svg-flatten/testdata/two-blobs.png | Bin 0 -> 470 bytes svg-flatten/testdata/two-px-inv.png | Bin 0 -> 472 bytes svg-flatten/testdata/two-px.png | Bin 0 -> 459 bytes svg-flatten/testdata/white.png | Bin 0 -> 454 bytes upstream/minunit | 1 + upstream/stb | 1 + 21 files changed, 461 insertions(+) create mode 100644 svg-flatten/src/nopencv.cpp create mode 100644 svg-flatten/src/nopencv.hpp create mode 100644 svg-flatten/src/nopencv_test.cpp create mode 100644 svg-flatten/testdata/blank.png create mode 100644 svg-flatten/testdata/blob-border-w.png create mode 100644 svg-flatten/testdata/blobs-borders.png create mode 100644 svg-flatten/testdata/blobs-corners.png create mode 100644 svg-flatten/testdata/blobs-crossing.png create mode 100644 svg-flatten/testdata/cross.png create mode 100644 svg-flatten/testdata/letter-e.png create mode 100644 svg-flatten/testdata/paper-example-inv.png create mode 100644 svg-flatten/testdata/paper-example.png create mode 100644 svg-flatten/testdata/single-px-inv.png create mode 100644 svg-flatten/testdata/single-px.png create mode 100644 svg-flatten/testdata/two-blobs.png create mode 100644 svg-flatten/testdata/two-px-inv.png create mode 100644 svg-flatten/testdata/two-px.png create mode 100644 svg-flatten/testdata/white.png create mode 160000 upstream/minunit create mode 160000 upstream/stb diff --git a/.gitmodules b/.gitmodules index e42d3c4..deedaea 100644 --- a/.gitmodules +++ b/.gitmodules @@ -16,3 +16,9 @@ [submodule "upstream/subprocess.h"] path = upstream/subprocess.h url = https://github.com/sheredom/subprocess.h +[submodule "svg-flatten/upstream/minunit"] + path = upstream/minunit + url = https://github.com/siu/minunit +[submodule "upstream/stb"] + path = upstream/stb + url = https://github.com/nothings/stb diff --git a/svg-flatten/src/nopencv.cpp b/svg-flatten/src/nopencv.cpp new file mode 100644 index 0000000..77c6cc6 --- /dev/null +++ b/svg-flatten/src/nopencv.cpp @@ -0,0 +1,157 @@ + +#include + +#include "nopencv.hpp" + +using namespace gerbolyze; +using namespace gerbolyze::nopencv; + +/* directions: + * 0 + * 7 1 + * ^ + * | + * 6 <--- X ---> 2 + * | + * v + * 5 3 + * 4 + * + */ +enum Direction { + D_N, + D_NE, + D_E, + D_SE, + D_S, + D_SW, + D_W, + D_NW +}; + +//const char * const dir_str[8] = { "N", "NE", "E", "SE", "S", "SW", "W", "NW" }; + +static struct { + int x; + int y; +} dir_to_coords[8] = {{0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}}; + +static Direction flip_direction[8] = { + D_S, + D_SW, + D_W, + D_NW, + D_N, + D_NE, + D_E, + D_SE +}; + +static void follow(gerbolyze::nopencv::Image32 img, int start_x, int start_y, Direction initial_direction, int nbd, int connectivity, Polygon &poly) { + + //cerr << "follow " << start_x << " " << start_y << " | dir=" << dir_str[initial_direction] << " nbd=" << nbd << " conn=" << connectivity << endl; + int dir_inc = (connectivity == 4) ? 2 : 1; + + int probe_x, probe_y; + + /* homing run: find starting point for algorithm steps below. */ + bool found = false; + int k; + for (k=initial_direction; k= current_direction; k -= dir_inc) { + probe_x = center_x + dir_to_coords[k % 8].x; + probe_y = center_y + dir_to_coords[k % 8].y; + if (k%8 == D_E) + flag = true; + + if (img.at_default(probe_x, probe_y) != 0) { + break; + } + } + + int set_val = 0; + if (flag && img.at_default(center_x+1, center_y) == 0) { + img.at(center_x, center_y) = -nbd; + set_val = -nbd; + } else if (img.at(center_x, center_y) == 1) { + img.at(center_x, center_y) = nbd; + set_val = nbd; + } + + for (int l = (current_direction + 8 - 2 + 1) / 2 * 2; l > k; l -= dir_inc) { + switch (l%8) { + case 0: poly.emplace_back(d2p{(double)center_x, (double)center_y}); break; + case 2: poly.emplace_back(d2p{(double)center_x+1, (double)center_y}); break; + case 4: poly.emplace_back(d2p{(double)center_x+1, (double)center_y+1}); break; + case 6: poly.emplace_back(d2p{(double)center_x, (double)center_y+1}); break; + } + } + + center_x = probe_x; + center_y = probe_y; + current_direction = flip_direction[k % 8]; + + //cerr << " " << center_x << " " << center_y << " / " << dir_str[current_direction] << " -> " << set_val << endl; + } while (center_x != start_x || center_y != start_y || current_direction != start_direction); +} + + +void gerbolyze::nopencv::find_blobs(gerbolyze::nopencv::Image32 img, gerbolyze::nopencv::ContourCallback cb) { + int nbd = 1; + Polygon poly; + for (int y=0; y= 1 && img.at_default(x+1, y) == 0) { /* hole border starting point */ + nbd += 1; + follow(img, x, y, D_E, nbd, 4, poly); + cb(poly, CP_HOLE); + poly.clear(); + } + } + } +} + diff --git a/svg-flatten/src/nopencv.hpp b/svg-flatten/src/nopencv.hpp new file mode 100644 index 0000000..b749808 --- /dev/null +++ b/svg-flatten/src/nopencv.hpp @@ -0,0 +1,98 @@ +/* + * This file is part of gerbolyze, a vector image preprocessing toolchain + * Copyright (C) 2021 Jan Sebastian Götte + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see . + */ + +#pragma once + +#include +#include +#include +#include +#include +#include + +#include "geom2d.hpp" + +using namespace std; + +namespace gerbolyze { + namespace nopencv { + + enum ContourPolarity { + CP_CONTOUR, + CP_HOLE + }; + + typedef std::function ContourCallback; + + class Image32 { + public: + Image32(int size_x, int size_y, const int32_t *data=nullptr) { + assert(size_x > 0 && size_x < 100000); + assert(size_y > 0 && size_y < 100000); + m_data = new int32_t[size_x * size_y] { 0 }; + m_rows = size_y; + m_cols = size_x; + if (data != nullptr) { + memcpy(m_data, data, sizeof(int32_t) * size_x * size_y); + } + } + + Image32(const Image32 &other) : Image32(other.cols(), other.rows(), other.ptr()) {} + + ~Image32() { + delete m_data; + } + + int32_t &at(int x, int y) { + assert(x >= 0 && y >= 0 && x < m_cols && y < m_rows); + assert(m_data != nullptr); + + return m_data[y*m_cols + x]; + }; + + const int32_t &at(int x, int y) const { + assert(x >= 0 && y >= 0 && x < m_cols && y < m_rows); + assert(m_data != nullptr); + + return m_data[y*m_cols + x]; + }; + + int32_t at_default(int x, int y, int32_t default_value=0) const { + assert(m_data != nullptr); + + if (x >= 0 && y >= 0 && x < m_cols && y < m_rows) { + return at(x, y); + + } else { + return default_value; + } + }; + + int rows() const { return m_rows; } + int cols() const { return m_cols; } + const int32_t *ptr() const { return m_data; } + + private: + int32_t *m_data = nullptr; + int m_rows=0, m_cols=0; + }; + + void find_blobs(Image32 img, ContourCallback cb); + } +} + diff --git a/svg-flatten/src/nopencv_test.cpp b/svg-flatten/src/nopencv_test.cpp new file mode 100644 index 0000000..cc1c988 --- /dev/null +++ b/svg-flatten/src/nopencv_test.cpp @@ -0,0 +1,198 @@ + +#include +#include +#include +#include +#include + +#include "nopencv.hpp" + +#include +#include + +#define STB_IMAGE_IMPLEMENTATION +#include "stb_image.h" + +using namespace gerbolyze; +using namespace gerbolyze::nopencv; + +char msg[1024]; + +MU_TEST(test_complex_example_from_paper) { + int32_t img_data[6*9] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 1, 1, 1, 1, 1, 1, 1, 0, + 0, 1, 0, 0, 1, 0, 0, 1, 0, + 0, 1, 0, 0, 1, 0, 0, 1, 0, + 0, 1, 1, 1, 1, 1, 1, 1, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, + }; + Image32 test_img(9, 6, static_cast(img_data)); + + const Polygon expected_polys[3] = { + { + {1,1}, {1,2}, {1,3}, {1,4}, {1,5}, + {2,5}, {3,5}, {4,5}, {5,5}, {6,5}, {7,5}, {8,5}, + {8,4}, {8,3}, {8,2}, {8,1}, + {7,1}, {6,1}, {5,1}, {4,1}, {3,1}, {2,1} + }, + { + {2,2}, {2,3}, {2,4}, + {3,4}, {4,4}, + {4,3}, {4,2}, + {3,2} + }, + { + {5,2}, {5,3}, {5,4}, + {6,4}, {7,4}, + {7,3}, {7,2}, + {6,2} + } + }; + + const ContourPolarity expected_polarities[3] = {CP_CONTOUR, CP_HOLE, CP_HOLE}; + + int invocation_count = 0; + gerbolyze::nopencv::find_blobs(test_img, [&invocation_count, &expected_polarities, &expected_polys](Polygon poly, ContourPolarity pol) { + invocation_count += 1; + mu_assert((invocation_count <= 3), "Too many contours returned"); + + mu_assert(poly.size() > 0, "Empty contour returned"); + mu_assert_int_eq(pol, expected_polarities[invocation_count-1]); + + d2p last; + bool first = true; + Polygon exp = expected_polys[invocation_count-1]; + //cout << "poly: "; + for (d2p &p : poly) { + //cout << "(" << p[0] << ", " << p[1] << "), "; + if (!first) { + mu_assert((fabs(p[0] - last[0]) + fabs(p[1] - last[1]) == 1), "Subsequent contour points have distance other than one"); + mu_assert(find(exp.begin(), exp.end(), p) != exp.end(), "Got unexpected contour point"); + } + last = p; + } + //cout << endl; + }); + mu_assert_int_eq(3, invocation_count); + + int32_t tpl[6*9] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 2, 2, 2, 2, 2, 2,-2, 0, + 0,-3, 0, 0,-4, 0, 0,-2, 0, + 0,-3, 0, 0,-4, 0, 0,-2, 0, + 0, 2, 2, 2, 2, 2, 2,-2, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, + }; + + + for (int y=0; y<6; y++) { + for (int x=0; x<9; x++) { + int a = test_img.at(x, y), b = tpl[y*9+x]; + if (a != b) { + cout << "Result:" << endl; + cout << " "; + for (int x=0; x<9; x++) { + cout << x << " "; + } + cout << endl; + cout << " "; + for (int x=0; x<9; x++) { + cout << "---"; + } + cout << endl; + for (int y=0; y<6; y++) { + cout << y << " | "; + for (int x=0; x<9; x++) { + cout << setfill(' ') << setw(2) << test_img.at(x, y) << " "; + } + cout << endl; + } + + snprintf(msg, sizeof(msg), "Result does not match template @(%d, %d): %d != %d\n", x, y, a, b); + mu_fail(msg); + } + } + } +} + +MU_TEST(test_round_trip) { + int x, y; + uint8_t *data = stbi_load("testdata/paper-example.png", &x, &y, nullptr, 1); + Image32 ref_img(x, y); + for (int cy=0; cy" << endl; + svg << "" << endl; + + gerbolyze::nopencv::find_blobs(ref_img, [&svg](Polygon poly, ContourPolarity pol) { + mu_assert(poly.size() > 0, "Empty contour returned"); + mu_assert(poly.size() > 2, "Contour has less than three points, no area"); + mu_assert(pol == CP_CONTOUR || pol == CP_HOLE, "Contour has invalid polarity"); + + svg << "" << endl; + }); + svg << "" << endl; + svg.close(); + + const char *command_line[] = {"resvg", tmp_svg.c_str(), tmp_png.c_str()}; + struct subprocess_s subprocess; + int rc = subprocess_create(command_line, subprocess_option_inherit_environment, &subprocess); + mu_assert_int_eq(rc, 0); + + int resvg_rc = -1; + rc = subprocess_join(&subprocess, &resvg_rc); + mu_assert_int_eq(rc, 0); + mu_assert_int_eq(resvg_rc, 0); + + rc = subprocess_destroy(&subprocess); + mu_assert_int_eq(rc, 0); + + int out_x, out_y; + uint8_t *out_data = stbi_load(tmp_png.c_str(), &out_x, &out_y, nullptr, 1); + mu_assert_int_eq(out_x, x); + mu_assert_int_eq(out_y, y); + + for (int cy=0; cy