diff options
21 files changed, 459 insertions, 0 deletions
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 <iostream> + +#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<initial_direction+8; k += dir_inc) { + probe_x = start_x + dir_to_coords[k % 8].x; + probe_y = start_y + dir_to_coords[k % 8].y; + + if (img.at_default(probe_x, probe_y) != 0) { + found = true; + break; + } + } + + if (!found) { /* No nonzero pixels found. This is a single-pixel contour */ + img.at(start_x, start_y) = nbd; + poly.emplace_back(d2p{(double)start_x, (double)start_y}); + poly.emplace_back(d2p{(double)start_x+1, (double)start_y}); + poly.emplace_back(d2p{(double)start_x+1, (double)start_y+1}); + poly.emplace_back(d2p{(double)start_x, (double)start_y+1}); + return; + } + + /* starting point found. */ + int current_direction = k % 8; + int start_direction = current_direction; + int center_x = start_x, center_y = start_y; + //cerr << " init: " << center_x << " " << center_y << " / " << dir_str[current_direction] << endl; + + do { + bool flag = false; + for (k = current_direction + 8 - dir_inc; 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<img.rows(); y++) { + for (int x=0; x<img.cols(); x++) { + int val_xy = img.at(x, y); + /* Note: outer borders are followed with 8-connectivity, hole borders with 4-connectivity. This prevents + * incorrect results in this case: + * + * 1 1 1 | 0 0 0 + * | + * 1 1 1 | 0 0 0 + * ----------+---------- <== Here + * 0 0 0 | 1 1 1 + * | + * 0 0 0 | 1 1 1 + */ + if (img.at_default(x-1, y) == 0 && val_xy == 1) { /* outer border starting point */ + nbd += 1; + follow(img, x, y, D_W, nbd, 8, poly); + cb(poly, CP_CONTOUR); + poly.clear(); + + } else if (val_xy >= 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 <gerbolyze@jaseg.de> + * + * 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 <https://www.gnu.org/licenses/>. + */ + +#pragma once + +#include <array> +#include <string> +#include <sstream> +#include <cmath> +#include <algorithm> +#include <assert.h> + +#include "geom2d.hpp" + +using namespace std; + +namespace gerbolyze { + namespace nopencv { + + enum ContourPolarity { + CP_CONTOUR, + CP_HOLE + }; + + typedef std::function<void(Polygon, ContourPolarity)> 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 <iostream> +#include <fstream> +#include <iomanip> +#include <cmath> +#include <filesystem> + +#include "nopencv.hpp" + +#include <subprocess.h> +#include <minunit.h> + +#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<int*>(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<y; cy++) { + for (int cx=0; cx<x; cx++) { + ref_img.at(cx, cy) = data[cy*x + cx]; + } + } + stbi_image_free(data); + Image32 ref_img_copy(ref_img); + + filesystem::path tmp_svg = { filesystem::temp_directory_path() /= (std::tmpnam(nullptr) + string(".svg")) }; + filesystem::path tmp_png = { filesystem::temp_directory_path() /= (std::tmpnam(nullptr) + string(".png")) }; + ofstream svg(tmp_svg.c_str()); + + svg << "<svg width=\"" << x << "px\" height=\"" << y << "px\" viewBox=\"0 0 " + << x << " " << y << "\" " + << "xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">" << endl; + svg << "<rect width=\"100%\" height=\"100%\" fill=\"black\">" << 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 << "<path fill=\"" << (pol == CP_HOLE ? "black" : "white") << "\" d=\""; + svg << "M " << poly[0][0] << " " << poly[0][1]; + for (size_t i=1; i<poly.size(); i++) { + svg << " L " << poly[i][0] << " " << poly[i][1]; + } + svg << " Z\">" << endl; + }); + svg << "</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<y; cy++) { + for (int cx=0; cx<x; cx++) { + int actual = out_data[cy*x + cx]; + int expected = ref_img_copy.at(x, y); + if (actual != expected) { + snprintf(msg, sizeof(msg), "Result does not match input @(%d, %d): %d != %d\n", cx, cy, actual, expected); + mu_fail(msg); + } + } + } + stbi_image_free(out_data); +} + +MU_TEST_SUITE(nopencv_contours_suite) { + MU_RUN_TEST(test_complex_example_from_paper); +// MU_RUN_TEST(test_round_trip); +} + +int main(int argc, char **argv) { + (void)argc; + (void)argv; + + MU_RUN_SUITE(nopencv_contours_suite); + MU_REPORT(); + return MU_EXIT_CODE; +} diff --git a/svg-flatten/testdata/blank.png b/svg-flatten/testdata/blank.png Binary files differnew file mode 100644 index 0000000..8dd7068 --- /dev/null +++ b/svg-flatten/testdata/blank.png diff --git a/svg-flatten/testdata/blob-border-w.png b/svg-flatten/testdata/blob-border-w.png Binary files differnew file mode 100644 index 0000000..b904783 --- /dev/null +++ b/svg-flatten/testdata/blob-border-w.png diff --git a/svg-flatten/testdata/blobs-borders.png b/svg-flatten/testdata/blobs-borders.png Binary files differnew file mode 100644 index 0000000..e183bd4 --- /dev/null +++ b/svg-flatten/testdata/blobs-borders.png diff --git a/svg-flatten/testdata/blobs-corners.png b/svg-flatten/testdata/blobs-corners.png Binary files differnew file mode 100644 index 0000000..d2bfb45 --- /dev/null +++ b/svg-flatten/testdata/blobs-corners.png diff --git a/svg-flatten/testdata/blobs-crossing.png b/svg-flatten/testdata/blobs-crossing.png Binary files differnew file mode 100644 index 0000000..30e4214 --- /dev/null +++ b/svg-flatten/testdata/blobs-crossing.png diff --git a/svg-flatten/testdata/cross.png b/svg-flatten/testdata/cross.png Binary files differnew file mode 100644 index 0000000..7936bde --- /dev/null +++ b/svg-flatten/testdata/cross.png diff --git a/svg-flatten/testdata/letter-e.png b/svg-flatten/testdata/letter-e.png Binary files differnew file mode 100644 index 0000000..141f187 --- /dev/null +++ b/svg-flatten/testdata/letter-e.png diff --git a/svg-flatten/testdata/paper-example-inv.png b/svg-flatten/testdata/paper-example-inv.png Binary files differnew file mode 100644 index 0000000..64250f1 --- /dev/null +++ b/svg-flatten/testdata/paper-example-inv.png diff --git a/svg-flatten/testdata/paper-example.png b/svg-flatten/testdata/paper-example.png Binary files differnew file mode 100644 index 0000000..a724556 --- /dev/null +++ b/svg-flatten/testdata/paper-example.png diff --git a/svg-flatten/testdata/single-px-inv.png b/svg-flatten/testdata/single-px-inv.png Binary files differnew file mode 100644 index 0000000..fd1223e --- /dev/null +++ b/svg-flatten/testdata/single-px-inv.png diff --git a/svg-flatten/testdata/single-px.png b/svg-flatten/testdata/single-px.png Binary files differnew file mode 100644 index 0000000..22228fd --- /dev/null +++ b/svg-flatten/testdata/single-px.png diff --git a/svg-flatten/testdata/two-blobs.png b/svg-flatten/testdata/two-blobs.png Binary files differnew file mode 100644 index 0000000..bc2d549 --- /dev/null +++ b/svg-flatten/testdata/two-blobs.png diff --git a/svg-flatten/testdata/two-px-inv.png b/svg-flatten/testdata/two-px-inv.png Binary files differnew file mode 100644 index 0000000..2768d0f --- /dev/null +++ b/svg-flatten/testdata/two-px-inv.png diff --git a/svg-flatten/testdata/two-px.png b/svg-flatten/testdata/two-px.png Binary files differnew file mode 100644 index 0000000..90db5e6 --- /dev/null +++ b/svg-flatten/testdata/two-px.png diff --git a/svg-flatten/testdata/white.png b/svg-flatten/testdata/white.png Binary files differnew file mode 100644 index 0000000..efe9983 --- /dev/null +++ b/svg-flatten/testdata/white.png diff --git a/upstream/minunit b/upstream/minunit new file mode 160000 +Subproject b15ad0ae28f1a7a43881ea17defb0a4367d9582 diff --git a/upstream/stb b/upstream/stb new file mode 160000 +Subproject c9064e317699d2e495f36ba4f9ac037e88ee371 |
