From 4b8265e5bcfd2332a3333c4129352e10c2d59c2f Mon Sep 17 00:00:00 2001 From: Stefan Huber Date: Tue, 19 Nov 2013 09:45:10 +0100 Subject: [PATCH] Add image to simplex conversion code --- include/libstick-0.1/booleanmatrix.h | 2 +- include/libstick-0.1/image.h | 86 ++++++++++++++++++++++++ include/libstick-0.1/persistence.h | 2 +- include/libstick-0.1/simplicialcomplex.h | 36 ++++++++-- tests/CMakeLists.txt | 1 + tests/image.h | 80 ++++++++++++++++++++++ tests/main.cc | 2 + 7 files changed, 200 insertions(+), 9 deletions(-) create mode 100644 include/libstick-0.1/image.h create mode 100644 tests/image.h diff --git a/include/libstick-0.1/booleanmatrix.h b/include/libstick-0.1/booleanmatrix.h index 1fb4dd2..8626f53 100644 --- a/include/libstick-0.1/booleanmatrix.h +++ b/include/libstick-0.1/booleanmatrix.h @@ -375,7 +375,7 @@ size_t count_set_intersection (InputIterator1 first1, InputIterator1 last1, Inpu size_t count = 0; // As long as we did not either end, look for common elements - while (first1!=last1 && first2!=last2) + while (first1 != last1 && first2 != last2) { if (*first1 < *first2) ++first1; diff --git a/include/libstick-0.1/image.h b/include/libstick-0.1/image.h new file mode 100644 index 0000000..abb1df0 --- /dev/null +++ b/include/libstick-0.1/image.h @@ -0,0 +1,86 @@ +#ifndef image_h_uiHiKahYooroomai +#define image_h_uiHiKahYooroomai + +#include "simplicialcomplex.h" + + +namespace libstick { + +/** We consider an image, i.e. a rectangular arrangement of pixels, of given + * height and width. Every pixel has a specific value (e.g., grey value) given + * by the 'values' array as concatenation of all rows. We add every pixel as + * vertex with its value as simplex value. We further triangulate the resulting + * rectangular latice as a grid graph together with south-west to north-east + * edges for each of the small squares of the grid graph. Finally the resulting + * triangles are added. For all non-vertex simplices the maximum of its + * vertex-values is used as its value. The first pixel is considered to be at + * bottom-left. */ +template +void add_image_to_complex(simplicial_complex<2, IT, VT> &s, const VT *values, size_t width, size_t height) { + // Add the vertices + const IT v1st = s.size(); + for (unsigned i=0; i < height; ++i) + for (unsigned j=0; j < width; ++j) + s.add_simplex(0, NULL, values[i*width + j]); + + // row i+1 o-------o + // | /| + // | / | + // | 2/ | + // 0 | / | + // | / | + // | / | + // |/ 1 | + // row i o-------o + // ^ + // column j + + IT faces[3]; + + // Adding horizontal edges + const IT he1st = s.size(); + for (unsigned i=0; i < height; ++i) + for (unsigned j=0; j < width-1; ++j) { + faces[0] = v1st + i*width + j; + faces[1] = faces[0] + 1; + s.add_simplex(1, faces); + } + + // Adding vertical edges + const IT ve1st = s.size(); + for (unsigned i=0; i < height-1; ++i) + for (unsigned j=0; j < width; ++j) { + faces[0] = v1st + i*width + j; + faces[1] = faces[0] + width; + s.add_simplex(1, faces); + } + + // Adding diagonal edges + const IT de1st = s.size(); + for (unsigned i=0; i < height-1; ++i) + for (unsigned j=0; j < width-1; ++j) { + faces[0] = v1st + i*width + j; + faces[1] = faces[0] + width + 1; + s.add_simplex(1, faces); + } + + // Add triangles + for (unsigned i=0; i < height-1; ++i) + for (unsigned j=0; j < width-1; ++j) { + faces[0] = he1st + i*(width-1) + j; + faces[1] = ve1st + i*width + j + 1; + faces[2] = de1st + i*(width-1) + j; + s.add_simplex(2, faces); + + faces[0] = he1st + (i+1)*(width-1) + j; + faces[1] = ve1st + i*width + j; + faces[2] = de1st + i*(width-1) + j; + s.add_simplex(2, faces); + } +} + + +} + +#endif + diff --git a/include/libstick-0.1/persistence.h b/include/libstick-0.1/persistence.h index c048f13..3840bd2 100644 --- a/include/libstick-0.1/persistence.h +++ b/include/libstick-0.1/persistence.h @@ -245,7 +245,7 @@ class persistence { } } #ifndef NDEBUG - // Shakespeare principle: A simplex either gaves birth or kills, be + // Shakespeare principle: A simplex either gives birth or kills, be // or not be, tertium non datur. for (unsigned c=0; c < lowestones.size(); ++c) { if (lowestones.get_column(c).size() != 0) diff --git a/include/libstick-0.1/simplicialcomplex.h b/include/libstick-0.1/simplicialcomplex.h index 707fd4f..988c090 100644 --- a/include/libstick-0.1/simplicialcomplex.h +++ b/include/libstick-0.1/simplicialcomplex.h @@ -23,7 +23,7 @@ namespace libstick { * Each 0-dimensional simplex automatically has this simplex as its face. * Consequently, the innner class simplex_order gives the extended boundary * matrix. */ -template +template class simplicial_complex { public: @@ -116,7 +116,7 @@ class simplicial_complex { } /** Get i-th simplex in the simplex order. */ - const Simplex& get_simplex(size_t i) const { + const Simplex& get_simplex(index_type i) const { assert(i < size()); return c.simplices[order.at(i)]; } @@ -204,14 +204,31 @@ class simplicial_complex { } /** Add a simplex to the complex. The dimension of the faces must be - * dim-1, and they must already be part of the complex. */ - void add_simplex(int dim, index_type* faces, value_type value) { - add_simplex(Simplex::create(dim, faces, value)); + * dim-1, and they must already be part of the complex. Returns the + * index of the added simplex. */ + index_type add_simplex(int dim, index_type* faces, value_type value) { + return add_simplex(Simplex::create(dim, faces, value)); + } + + /** Add a simplex to the complex of at least dimension 1. The dimension + * of the faces must be dim-1, and they must already be part of the + * complex. The value of the simplex is set to the maximum value of its + * faces. Returns the index of the added simplex. */ + index_type add_simplex(int dim, index_type* faces) { + assert(dim >= 1); + + // Get max value of its faces + VT value = simplices[faces[0]].value; + for (size_t i=0; i < Simplex::face_count_bydim(dim); ++i) + value = std::max(value, simplices[faces[i]].value); + + return add_simplex(dim, faces, value); } /** Add a simplex to the complex. The dimension of the faces must be - * dim-1, and they must already be part of the complex. */ - void add_simplex(Simplex s) { + * dim-1, and they must already be part of the complex. Returns the + * index of the added simplex. */ + index_type add_simplex(Simplex s) { // Check requirements for faces for (unsigned i=0; i < s.face_count(); ++i) { // Faces are already in complex. @@ -220,7 +237,12 @@ class simplicial_complex { assert(simplices[s.faces[i]].dim == s.dim-1); } + // index_type must be large enough + assert(simplices.size() < std::numeric_limits::max()); + + index_type idx = simplices.size(); simplices.push_back(s); + return idx; } /** Add an array of simplices */ diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt index 15fe760..e068b45 100644 --- a/tests/CMakeLists.txt +++ b/tests/CMakeLists.txt @@ -10,4 +10,5 @@ include_directories(${libstick_SOURCE_DIR}/include) add_executable(tests ${tests_SRC}) target_link_libraries(tests #stick + m ${libcpptest_LIBRARIES}) diff --git a/tests/image.h b/tests/image.h new file mode 100644 index 0000000..ff7817a --- /dev/null +++ b/tests/image.h @@ -0,0 +1,80 @@ +#ifndef image_h_PooBeibuceushabo +#define image_h_PooBeibuceushabo + +#include +#include + +#include + +#include +#include + + +using namespace libstick; + + +class image_TestSuite: public Test::Suite { + + private: + + public: + image_TestSuite() + { + TEST_ADD(image_TestSuite::test_incidences); + } + + protected: + virtual void setup() { + } + + virtual void tear_down() { + } + + void test_incidences() { + const size_t height=128, width=64; + + //Create "some" image + float image[height*width]; + for (unsigned i=0; i < height; ++i) + for (unsigned j=0; j < width; ++j) + image[i*width + j] = (sin(j/10.0) + 0.5*sin(j/4.0))*cos(i/7.0) + i*j*0.5*1e-3; + + // Create complex and add image + typedef simplicial_complex<2, uint32_t, float> scomplex; + scomplex s; + add_image_to_complex(s, image, width, height); + assert(s.is_monotone()); + + typedef scomplex::simplex_order sorder; + sorder so(s); + assert(so.is_filtration()); + + typedef sorder::boundary_matrix bmatrix; + bmatrix bm = so.get_boundary_matrix(); + + // Check for the right vertex incidences + for (unsigned i=0; i < height; ++i) { + for (unsigned j=0; j < width; ++j) { + // Get matrix row of this vertex. Its size is the number of edges + // incident to this vertex + const bmatrix::row_type &row = bm.get_row(1 + i*width + j); + + // Somewhere at the boundary of the image + if (i == 0 || i == height-1 || j == 0 || j == width-1) { + // top-left and bottom-right corner + if ((i == 0 && j == 0) || (i == height - 1 && j == width - 1)) { + TEST_ASSERT(row.size() == 3); + } else if ((i == 0 && j == width - 1) || (i == height - 1 && j == 0)) { + TEST_ASSERT(row.size() == 2); + } else { + TEST_ASSERT(row.size() == 4); + } + } else { + TEST_ASSERT(row.size() == 6); + } + } + } + } +}; + +#endif diff --git a/tests/main.cc b/tests/main.cc index 6016b3b..dcf0abe 100644 --- a/tests/main.cc +++ b/tests/main.cc @@ -4,6 +4,7 @@ #include "booleanmatrix.h" #include "simplicialcomplex.h" #include "persistence.h" +#include "image.h" using namespace std; @@ -17,6 +18,7 @@ int main(int argc, char* argv[]) { ts.add(auto_ptr(new boolean_matrix_TestSuite)); ts.add(auto_ptr(new simplicial_complex_TestSuite)); ts.add(auto_ptr(new persistence_TestSuite)); + ts.add(auto_ptr(new image_TestSuite)); Test::TextOutput output(Test::TextOutput::Verbose); if (ts.run(output)) -- 2.39.5