diff options
Diffstat (limited to 'meowpp.test/src')
23 files changed, 0 insertions, 4085 deletions
diff --git a/meowpp.test/src/BinaryIndexTree.cpp b/meowpp.test/src/BinaryIndexTree.cpp deleted file mode 100644 index e9a4544..0000000 --- a/meowpp.test/src/BinaryIndexTree.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#include "meowpp/dsa/BinaryIndexTree.h" -#include "meowpp/utility.h" - -#include "dsa.h" - -#include <vector> - -static int N = 100000; - -static std::vector<int> array; - -inline int sum(int k){ - int x = 0; - for(int i = 0; i <= k; i++){ - x += array[i]; - } - return x; -} - -static meow::BinaryIndexTree<int> bit; - -TEST(BinaryIndexTree, "Test with large data"){ - size_t tMe = 0, tBi = 0, t0; - for(int z = 0; z < 10; z++){ - meow::messagePrintf(1, "test %d", z); - bit.reset(N, 0); - array.clear(); - array.resize(N, 0); - - int NN = rand() % 10000; - for(int i = 0; i < NN; i++){ - int index = rand() % N; - if(rand() & 1){ - int val = rand() % 1000; - t0 = clock(); array[i] += val; tMe += clock() - t0; - t0 = clock(); bit.update(i, val); tBi += clock() - t0; - }else{ - if(sum(index) != bit.query(index)){ - meow::messagePrintf(-1, "range-sum query fail"); - return false; - } - } - } - int s = 0; - for(int i = 0; i < N; i++){ - s += array[i]; - if(s != bit.query(i)){ - meow::messagePrintf(-1, "range-sum query fail"); - return false; - } - } - meow::messagePrintf(-1, "ok %.3f/%.3f", - tBi * 1.0 / CLOCKS_PER_SEC, - tMe * 1.0 / CLOCKS_PER_SEC); - } - return true; -} diff --git a/meowpp.test/src/DisjointSet.cpp b/meowpp.test/src/DisjointSet.cpp deleted file mode 100644 index 4a8750b..0000000 --- a/meowpp.test/src/DisjointSet.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include "meowpp/dsa/DisjointSet.h" - -#include "dsa.h" - -#include <vector> - - -TEST(DisjointSet, "..."){ - int N = 10000000; - meow::DisjointSet dsj(N); - - meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N); - for(int i = 1; i < N; i++){ - dsj.merge(0, i); - } - int root = dsj.root(0); - for(int i = 1; i < N; i++){ - if(root != (int)dsj.root(i)){ - meow::messagePrintf(-1, "fail"); - return false; - } - } - meow::messagePrintf(-1, "ok"); - // - - dsj.reset(N); - meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N); - for(int i = 1; i < N; i++){ - dsj.merge(i - 1, i); - } - root = dsj.root(0); - for(int i = 1; i < N; i++){ - if(root != (int)dsj.root(i)){ - meow::messagePrintf(-1, "fail"); - return false; - } - } - meow::messagePrintf(-1, "ok"); - // - - int M = 1000; - N = 1000000; - dsj.reset(N); - std::vector<int> used(N, -1); - std::vector<std::vector<int> > nums(M); - - meow::messagePrintf(1, "random test (N = %d)", N); - for(int i = 0; i < N / 10; i++){ - int grp = rand() % M; - int who; - while(used[who = rand() % N] != -1); - nums[grp].push_back(who); - used[who] = grp; - } - meow::messagePrintf(0, "data created"); - for(int i = 0; i < M; i++){ - for(int k = 0; k < 100; k++){ - int j1 = rand() % nums[i].size(); - int j2 = rand() % nums[i].size(); - dsj.merge(nums[i][j1], nums[i][j2]); - } - for(size_t j = 1; j < nums[i].size(); j++){ - dsj.merge(nums[i][0], nums[i][j]); - } - } - for(int i = 0; i < N; i++){ - bool ok = false; - if((int)used[i] == -1 && (int)dsj.root(i) == i){ - ok = true; - }else{ - if(dsj.root(i) == dsj.root(nums[used[i]][0])){ - ok = true; - } - } - if(!ok){ - meow::messagePrintf(-1, "fail"); - return false; - } - } - meow::messagePrintf(-1, "ok"); - return true; -} diff --git a/meowpp.test/src/KD_Tree.cpp b/meowpp.test/src/KD_Tree.cpp deleted file mode 100644 index 8d4232e..0000000 --- a/meowpp.test/src/KD_Tree.cpp +++ /dev/null @@ -1,190 +0,0 @@ -#include "meowpp/dsa/KD_Tree.h" -#include "meowpp/utility.h" - -#include "dsa.h" - -#include <vector> - -#include <cmath> -#include <cstdlib> -#include <algorithm> -#include <ctime> -#include <queue> - -static int N = 10000; -static int D = 5; - -static double dist2(std::vector<double> const& v1, std::vector<double> const& v2){ - double ret = 0; - for(int i = 0; i < D; i++){ - ret += meow::squ(v1[i] - v2[i]); - } - return ret; -} - -static std::vector< std::vector<double> > data; -static std::vector< double > dist; -static std::vector< int > order; - - -struct Answer{ - double dist; - int id; - Answer(double _dist, int _id): dist(_dist), id(_id){ } - bool operator<(Answer const& b) const{ - if(dist != b.dist) return (dist < b.dist); - return (id < b.id); - } -}; - - -static void find(std::vector<double> const& v, int k){ - std::priority_queue<Answer> qu; - for(int i = 0; i < k; i++){ - qu.push(Answer(dist2(v, data[i]), i)); - } - for(int i = k; i < N; i++){ - qu.push(Answer(dist2(v, data[i]), i)); - qu.pop(); - } - order.resize(k); - for(int i = qu.size() - 1; i >= 0; i--){ - order[i] = qu.top().id; - qu.pop(); - } -} - -static std::vector<double> v; - -/* -static bool sf(const int& a, const int& b){ - if(dist[a] != dist[b]) - return (dist[a] < dist[b]); - return (a < b); -} - -static void show(std::vector<double> const& ask, std::vector<int> kd, std::vector<int> me, int k){ - if(N <= 30 && D <= 3){ - printf("\nData:\n"); - for(int i = 0; i < N; i++){ - printf(" %2d) <", i); - for(int j = 0; j < D; j++){ - printf("%.7f", data[i][j]); - if(j < D - 1) printf(", "); - else printf(">"); - } - printf("\n"); - } - printf("Ask <"); - for(int j = 0; j < D; j++){ - printf("%.7f", ask[j]); - if(j < D - 1) printf(", "); - else printf(">"); - } - printf("\n"); - printf("MyAnswer: "); - for(int i = 0; i < k; i++) printf("%d ", me[i]); - printf("\n"); - printf("KdAnswer: "); - for(int i = 0; i < k; i++) printf("%d ", kd[i]); - printf("\n"); - order.resize(N); - dist .resize(N); - for(int i = 0; i < N; i++){ - dist [i] = dist2(ask, data[i]); - order[i] = i; - } - std::sort(order.begin(), order.end(), sf); - printf("Sorted:\n"); - for(int i = 0; i < N; i++){ - printf(" %2d) <", order[i]); - for(int j = 0; j < D; j++){ - printf("%.7f", data[order[i]][j]); - if(j < D - 1) printf(", "); - else printf(">"); - } - printf(" ((%.7f))", dist[order[i]]); - printf("\n"); - } - } -} -// */ - -struct Node{ - std::vector<double> v; - int id; - double& operator[](size_t d) { return v[d]; } - double operator[](size_t d) const { return v[d]; } - bool operator<(Node const& n) const{ return (id < n.id); } -}; - -TEST(KD_Tree, "It is very slow"){ - - int t0, t1, t2; - - meow::KD_Tree<Node, double> tree(D); - - meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D); - data.resize(N); - for(int i = 0; i < N; i++){ - data[i].resize(D); - Node nd; - nd.v.resize(D); - nd.id = i; - for(int j = 0; j < D; j++){ - data[i][j] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3); - nd[j] = data[i][j]; - } - tree.insert(nd); - } - meow::messagePrintf(-1, "ok"); - meow::messagePrintf(1, "build"); - t0 = clock(); - tree.build(); - meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC); - - meow::messagePrintf(1, "query..."); - v.resize(D); - meow::KD_Tree<Node, double>::Vectors ret; - for(int k = 1; k <= std::min(100, N); k++){ - meow::messagePrintf(1, "range k = %d", k); - t1 = t2 = 0; - for(int i = 0; i < 10; i++){ - Node nd; - nd.v.resize(D); - for(int d = 0; d < D; d++){ - v[d] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3); - nd[d] = v[d]; - } - t0 = clock(); - tree.build(); - ret = tree.query(nd, k, true); - t1 += clock() - t0; - - t0 = clock(); - find(v, k); - t2 += clock() - t0; - if((int)ret.size() != (int)std::min(k, N)){ - meow::messagePrintf(-1, "(%d)query fail, size error", i); - meow::messagePrintf(-1, "fail"); - return false; - } - for(int kk = 1; kk <= k; kk++){ - if(order[kk - 1] != ret[kk - 1].id){ - //show(v, ret, order, k); - meow::messagePrintf(-1, "(%d)query fail", i); - meow::messagePrintf(-1, "fail"); - return false; - } - } - } - meow::messagePrintf(-1, "ok %.3f/%.3f", - t1 * 1.0 / CLOCKS_PER_SEC, - t2 * 1.0 / CLOCKS_PER_SEC - ); - } - meow::messagePrintf(-1, "ok"); - - - return true; -} diff --git a/meowpp.test/src/Matrix.cpp b/meowpp.test/src/Matrix.cpp deleted file mode 100644 index 2579b0b..0000000 --- a/meowpp.test/src/Matrix.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include "meowpp/math/Matrix.h" - -#include "dsa.h" - -#include <cmath> -#include <cstdlib> - -using namespace meow; - - - -void print(Matrix<int> const& m){ - for(size_t r = 0; r < m.rows(); r++){ - printf("["); - for(size_t c = 0; c < m.cols(); c++){ - printf("%8d", m(r, c)); - } - printf("]\n"); - } -} - -TEST(Matrix, "Unfinished"){ - Matrix<int> a(3, 4, 0); - Matrix<int> b(3, 4, 0); - Matrix<int> c(4, 5, 0); - for(int i = 0; i < 3; i++){ - for(int j = 0; j < 4; j++){ - a.entry(i, j, rand() % 100); - b.entry(i, j, rand() % 100); - } - } - for(int i = 0; i < 4; i++){ - for(int j = 0; j < 5; j++){ - c.entry(i, j, rand() % 100); - } - } - printf("A = \n"); print(a); - printf("B = \n"); print(b); - printf("C = \n"); print(b); - printf("A + B = \n"); print(a + b); - printf("A * C = \n"); print(a * c); - printf("A * B^T = \n"); print(a * b.transpose()); - - return true; -}; diff --git a/meowpp.test/src/MergeableHeap.cpp b/meowpp.test/src/MergeableHeap.cpp deleted file mode 100644 index e8183ca..0000000 --- a/meowpp.test/src/MergeableHeap.cpp +++ /dev/null @@ -1,74 +0,0 @@ -#include "meowpp/dsa/MergeableHeap.h" -#include "meowpp/utility.h" - -#include "dsa.h" - -#include <vector> -#include <queue> -#include <cstdlib> - - -TEST(MergeableHeap, "..."){ - int N = 10; - std::vector<std::priority_queue<int> > nhp; - std::vector<meow::MergeableHeap<int> > mhp; - for(int i = 0; i < 10; i++){ - int MM = 5000 + rand() % 10000; - meow::messagePrintf(1, "%d-th test (M = %5d)", i, MM); - nhp.clear(); nhp.resize(N); - mhp.clear(); mhp.resize(N); - int tn = 0, tm = 0, t0; - for(int j = 0; j < MM; j++){ - if((rand() & 3) == 0){ - int a = rand() % N; - int num = rand(); - t0 = clock(); nhp[a].push(num); tn += clock() - t0; - t0 = clock(); mhp[a].push(num); tm += clock() - t0; - }else if(rand() & 1){ - int a = rand() % N; - t0 = clock(); - if(!nhp[a].empty()) nhp[a].pop(); - tn += clock() - t0; - t0 = clock(); - if(!mhp[a].empty()) mhp[a].pop(); - tm += clock() - t0; - }else{ - int a = rand() % N, b = rand() % N; - if(b == a) b = (b + 1) % N; - t0 = clock(); - for( ; !nhp[b].empty(); nhp[b].pop()){ - nhp[a].push(nhp[b].top()); - } - tn += clock() - t0; - t0 = clock(); - mhp[a].merge(&mhp[b]); - tm += clock() - t0; - } - } - bool ok = true; - for(int j = 0; j < N; j++){ - while(!nhp[j].empty() && !mhp[j].empty()){ - if(nhp[j].top() != mhp[j].top()){ - ok = false; - break; - } - nhp[j].pop(); - mhp[j].pop(); - } - if(mhp[j].empty() != nhp[j].empty()){ - ok = false; - } - if(ok == false) break; - } - ok = true; - if(!ok){ - meow::messagePrintf(-1, "fail"); - return false; - }else{ - meow::messagePrintf(-1, "ok %.3f/%.3f", - tm * 1.0 / CLOCKS_PER_SEC, - tn * 1.0 / CLOCKS_PER_SEC ); - } - } - return true; -} diff --git a/meowpp.test/src/SegmentTree.cpp b/meowpp.test/src/SegmentTree.cpp deleted file mode 100644 index c795477..0000000 --- a/meowpp.test/src/SegmentTree.cpp +++ /dev/null @@ -1,157 +0,0 @@ -#include "meowpp/dsa/SegmentTree.h" -#include "meowpp/utility.h" - -#include "dsa.h" - -#include <ctime> -#include <algorithm> - -struct RangeMax{ - int value; - // - RangeMax(){} - RangeMax(int _value): value(_value){ } - RangeMax(RangeMax const& b): value(b.value){ } - // - RangeMax operator*(size_t n) const{ return RangeMax(value); } - RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); } - RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); } - bool operator==(RangeMax const& b) const{ return (value == b.value); } -}; -struct RangeSum{ - int value; - // - RangeSum(){} - RangeSum(int _value): value(_value){ } - RangeSum(RangeSum const& b): value(b.value){ } - // - RangeSum operator*(size_t n) const{ return RangeSum(n * value); } - RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); } - RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); } - bool operator==(RangeSum const& b) const{ return (value == b.value); } -}; - -meow::SegmentTree<RangeMax> s_max; -meow::SegmentTree<RangeSum> s_sum; - -static int N = 1000000; - -std::vector<int> array; - -void override(int a, int b, int c){ - for(int i = a; i <= b; i++) - array[i] = c; -} -void offset(int a, int b, int c){ - for(int i = a; i <= b; i++) - array[i] += c; -} -int bmax(int a, int b){ - int ret = array[a]; - for(int i = a + 1; i <= b; i++) - ret = std::max(ret, array[i]); - return ret; -} -int bsum(int a, int b){ - int sum = 0; - for(int i = a; i <= b; i++) - sum += array[i]; - return sum; -} - -void show(){ - if(N <= 20){ - printf("\n"); - printf("Me : "); - for(int i = 0; i < N; i++){ - printf("%4d ", array[i]); - } - printf("\n"); - printf("Sum: "); - for(int i = 0; i < N; i++){ - printf("%4d ", s_sum.query(i, i).value); - } - printf("\n"); - printf("Max: "); - for(int i = 0; i < N; i++){ - printf("%4d ", s_max.query(i, i).value); - } - printf("\n"); - } -} - -TEST(SegmentTree, "..."){ - s_max.reset(N); - s_sum.reset(N); - s_max.override(0, N - 1, RangeMax(0)); - s_sum.override(0, N - 1, RangeSum(0)); - array.resize(N, 0); - - for(int z = 0; z < 10; z++){ - meow::messagePrintf(1, "test %d", z); - int tMe = 0, tSeg = 0, t0; - int NN = 1 + rand() % 100; - for(int i = 0; i < NN; i++){ - int a = rand() % N; - int b = rand() % (N - a) + a; - int k = rand() % 20000 - 10000; - bool over = (rand() % 2 == 1); - if(over){ - t0 = clock(); - s_max.override(a, b, RangeMax(k)); - s_sum.override(a, b, RangeSum(k)); - tSeg += clock() - t0; - t0 = clock(); - override(a, b, k); - tMe += clock() - t0; - }else{ - t0 = clock(); - s_max.offset(a, b, RangeMax(k)); - s_sum.offset(a, b, RangeSum(k)); - tSeg = clock() - t0; - t0 = clock(); - offset(a, b, k); - tMe += clock() - t0; - } - /* - printf("\n"); - printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k); - show(); - printf("max:"); s_max.print(); - printf("sum:"); s_sum.print(); - // */ - } - NN = 1 + rand() % 100; - for(int i = 0; i < NN; i++){ - int a = rand() % N; - int b = rand() % (N - a) + a; - - t0 = clock(); - RangeMax m(s_max.query(a, b)); - RangeSum s(s_sum.query(a, b)); - tSeg += clock() - t0; - t0 = clock(); - int mm = bmax(a, b); - int ss = bsum(a, b); - tMe += clock() - t0; - if(m.value != mm){ - printf("ask %d~%d, me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value); - meow::messagePrintf(-1, "range-max query fail"); - return false; - } - if(s.value != ss){ - printf("ask %d~%d, max/sum = me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value); - meow::messagePrintf(-1, "range-sum query fail"); - return false; - } - } - meow::messagePrintf(-1, "ok, %.3f/%.3f", - 1.0 * tSeg / CLOCKS_PER_SEC, - 1.0 * tMe / CLOCKS_PER_SEC); - s_max.reset(N); - s_sum.reset(N); - array.clear(); - array.resize(N, 0); - } - return true; -} diff --git a/meowpp.test/src/SplayTree.cpp b/meowpp.test/src/SplayTree.cpp deleted file mode 100644 index ea24fb8..0000000 --- a/meowpp.test/src/SplayTree.cpp +++ /dev/null @@ -1,477 +0,0 @@ -#include "meowpp/dsa/SplayTree.h" -#include "meowpp/utility.h" - -#include "dsa.h" - -#include <algorithm> -#include <utility> -#include <map> -#include <cstdlib> - -static int N; - -static bool detail_fg; - -typedef typename std::map <int, double>:: iterator IterN; -typedef typename std::map <int, double>::reverse_iterator IterR; -typedef typename meow::SplayTree<int, double>::Element IterS; - -static std::vector< std::map <int, double> > normal; -static std::vector<meow::SplayTree<int, double> > splay; - -static void show(bool fg = false){ - if(fg){ - for(int i = 0; i < N; i++){ - printf("normal %d-%lu: ", i, normal[i].size()); - for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ - printf("%d/%.2f ", it->first, it->second); - } - printf("\n"); - printf("splay %d-%lu: ", i, splay[i].size()); - for(size_t j = 0; j < splay[i].size(); j++){ - IterS it = splay[i].order(j); - printf("%d/%.2f ", it->first, it->second); - } - printf("\n"); - } - printf("\n"); - } -} - -static bool lowerBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= lowerBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0; - t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second, - (b == splay[i].end()) ? 0 : b->second); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second == b->second); -} -static bool upperBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= upperBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0; - t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay [i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second, - (b == splay [i].end()) ? 0 : b->second); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second == b->second); -} -static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0; - t0 = clock(); - IterN a, z; - if(normal[i].size() == 0 || normal[i].begin()->first > key){ - a = normal[i].end(); - }else{ - for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){ - if(z->first > key){ - break; - } - } - } - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second, - (b == splay[i].end()) ? 0 : b->second); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second == b->second); -} -static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0; - t0 = clock(); - IterN a, z; - if(normal[i].begin() == normal[i].end()){ - a = normal[i].end(); - }else{ - if(normal[i].begin()->first >= key) a = normal[i].end(); - else{ - for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){ - if(z->first >= key) - break; - } - } - } - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second, - (b == splay[i].end()) ? 0 : b->second); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second == b->second); -} -static bool find(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= find(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0; - t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second, - (b == splay[i].end()) ? 0 : b->second); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second == b->second); -} -static bool order(int i, int order, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= order(%d, %d)\n", i, order); - t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0; - t0 = clock(); - IterN a = normal[i].begin(); - for(int k = 0; k < order; k++) a++; - (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second, - (b == splay[i].end()) ? 0 : b->second); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second == b->second); -} -static bool first_last(int i, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= first_last(%d)\n", i); - IterN a; - t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0; - t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second, - (b == splay[i].end()) ? 0 : b->second); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()); - else{ - if((a->first == b->first && a->second == b->second) == false){ - return false; - } - } - t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0; - t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (r == normal[i].rend()) ? 0 : r->first, - (b == splay[i].end()) ? 0 : b->first, - (r == normal[i].rend()) ? 0 : r->second, - (b == splay[i].end()) ? 0 : b->second); - if((r == normal[i].rend()) != (b == splay[i].end())) return false; - if(r == normal[i].rend()); - else{ - if((r->first == b->first && r->second == b->second) == false){ - return false; - } - } - return true; -} -/* -static bool insert(int i, int key, double val, size_t* tN, size_t* tS){ - size_t t0; - if(rand() & 1){ - t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0; - t0 = clock(); normal[i].insert(std::pair<int, double>(key, val)); (*tN) += clock() - t0; - }else{ - t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0; - t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0; - } - detail_fg && printf("============= insert(%d, %d)\n", i, key); - show(detail_fg); - return true; -} -// */ -static bool split(int i, int j, int key, size_t* tN, size_t* tS){ - size_t t0; - if(i == j){ - return true; - } - detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key); - t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0; - t0 = clock(); - normal[j].clear(); - for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){ - normal[j].insert(*it); - normal[i].erase(it); - } - *tN += clock() - t0; - show(detail_fg); - return true; -} -static bool merge(int i, int j, int key, size_t* tN, size_t* tS){ - size_t t0; - if(i == j){ - return true; - } - if(rand() & 1){ - t0 = clock(); - if(splay[i].size() > 0) - while(splay[j].size() > 0 && - splay[j].first()->first <= splay[i].last()->first){ - splay[j].erase(splay[j].first()->first); - } - *tS += clock() - t0; - t0 = clock(); - if(normal[i].size() > 0) - while(normal[j].size() > 0 && - normal[j].begin()->first <= normal[i].rbegin()->first) - normal[j].erase(normal[j].begin()); - *tN += clock() - t0; - } - t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0; - t0 = clock(); - if(normal[i].size() == 0 || normal[j].size() == 0 || - normal[i].rbegin()->first < normal[j].begin()->first || - normal[j].rbegin()->first < normal[i].begin()->first - ){ - for(IterN it = normal[j].begin(); it != normal[j].end(); it++){ - normal[i].insert(*it); - } - normal[j].clear(); - } - *tN += clock() - t0; - detail_fg && printf("============= merge(%d, %d)\n", i, j); - show(detail_fg); - return true; -} -static bool erase(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= erase(%d, %d)\n", i, key); - t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0; - t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0; - show(detail_fg); - return true; -} -static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta); - t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0; - t0 = clock(); - std::map<int, double> tmp = normal[i]; - normal[i].clear(); - for(IterN it = tmp.begin(); it != tmp.end(); it++){ - normal[i].insert(std::pair<int, double>(it->first + delta, it->second)); - } - (*tN) += clock() - t0; - show(detail_fg); - return true; -} -/* -static bool valueOffset(int i, double delta, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta); - t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0; - t0 = clock(); - for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ - it->second += delta; - } - (*tN) += clock() - t0; - show(detail_fg); - return true; -} -// */ -static bool copy(int i, int j, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("copy(%d, %d)\n", i, j); - t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0; - t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0; - show(detail_fg); - return true; -} - -static bool check(){ - for(int i = 0; i < N; i++){ - if(normal[i].size() != splay[i].size()) return false; - int j = 0; - for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){ - if(it->first != splay[i].order(j)->first || - it->second != splay[i].order(j)->second) - return false; - } - } - return true; -} - -TEST(SplayTree, "Seems buggy"){ - detail_fg = false; - N = 5; - for(int i = 0; i < 10; i++){ - normal.clear(); - splay .clear(); - normal.resize(N); - splay .resize(N); - size_t tn = 0, tm = 0; - int op = 1 + rand() % 2000000; - meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op); - while(op--){ - int wh = rand() % 60; - int i1 = rand() % N, i2, k = rand() % 60; - while((i2 = rand() % N) == i1); - switch(wh){ - case 0: - if(lowerBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "lowerBound"); - show(true); - return false; - } - break; - case 1: - if(rUpperBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "rUpperBound"); - show(true); - return false; - } - break; - case 2: - if(rLowerBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "rLowerBound"); - show(true); - return false; - } - break; - case 3: - if(upperBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "upperBound"); - show(true); - return false; - } - break; - case 4: - case 5: - case 6: - if(find(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "find"); - show(true); - return false; - } - break; - case 7: - case 8: - case 9: - if(normal[i1].size() > 0){ - if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "order"); - show(true); - return false; - } - break; - } - case 10: - if(first_last(i1, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "first_last"); - show(true); - return false; - } - break; - case 21: - case 22: - case 23: - case 24: - case 25: - case 26: - if(split(i1, i2, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "split"); - show(true); - return false; - } - break; - case 27: - case 28: - case 29: - case 30: - case 31: - case 32: - case 33: - case 34: - case 35: - case 36: - if(merge(i1, i2, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "merge"); - show(true); - return false; - } - break; - case 37: - case 38: - case 39: - case 40: - if(erase(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "erase"); - show(true); - return false; - } - break; - case 41: - case 42: - case 43: - case 44: - case 45: - case 46: - case 47: - case 48: - case 49: - if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "keyOffset"); - show(true); - return false; - } - break; - case 50: - case 51: - case 52: - if(copy(i1, i2, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "copy"); - show(true); - return false; - } - break; - case 53: - case 54: - case 55: - case 56: - case 57: - case 58: - case 59: - op++; - /* - if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "valueOffset"); - show(true); - return false; - } - break; - // */ - } - } - if(!check()){ - meow::messagePrintf(-1, "fail"); - show(true); - return false; - } - meow::messagePrintf(-1, "ok %.3f/%.3f", - tm * 1.0 / CLOCKS_PER_SEC, - tn * 1.0 / CLOCKS_PER_SEC); - } - return true; -} diff --git a/meowpp.test/src/SplayTree_Range.cpp b/meowpp.test/src/SplayTree_Range.cpp deleted file mode 100644 index e6d857b..0000000 --- a/meowpp.test/src/SplayTree_Range.cpp +++ /dev/null @@ -1,561 +0,0 @@ -#include "meowpp/dsa/SplayTree.h" -#include "meowpp/utility.h" - -#include "dsa.h" - -#include <algorithm> -#include <utility> -#include <map> -#include <cstdlib> -#include <cmath> - -static int min_sum; -struct Double{ - double k; - Double(): k(0){ } - Double(double _k): k(0){ } - bool operator==(const Double& b) const{ return fabs(k - b.k) <= 1e-9; } - bool operator!=(const Double& b) const{ return fabs(k - b.k) > 1e-9; } - bool operator<(const Double& b) const{ return k < b.k; } - Double operator+(const Double& b) const{ return Double(k + b.k); } - Double operator*(size_t& b) const{ - if(min_sum == 0) return Double(k); - else return Double(k * b); - } - Double operator|(const Double& b) const{ - if(min_sum == 0) return Double(std::min(k, b.k)); - else return Double(k + b.k); - } -}; - -static int N; - -static bool detail_fg; - -typedef typename std::map <int, Double>:: iterator IterN; -typedef typename std::map <int, Double>::reverse_iterator IterR; -typedef typename meow::SplayTree_Range<int, Double>::Element IterS; - -static std::vector< std::map <int, Double> > normal; -static std::vector<meow::SplayTree_Range<int, Double> > splay; - -static void show(bool fg = false){ - if(fg){ - for(int i = 0; i < N; i++){ - printf("normal %d-%lu: ", i, normal[i].size()); - for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ - printf("%d/%.2f ", it->first, it->second.k); - } - printf("\n"); - printf("splay %d-%lu: ", i, splay[i].size()); - for(size_t j = 0; j < splay[i].size(); j++){ - IterS it = splay[i].order(j); - printf("%d/%.2f ", it->first, it->second.k); - } - printf("\n"); - } - printf("\n"); - } -} - -static bool lowerBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= lowerBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0; - t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second.k, - (b == splay[i].end()) ? 0 : b->second.k); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second.k == b->second.k); -} -static bool upperBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= upperBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0; - t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay [i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second.k, - (b == splay [i].end()) ? 0 : b->second.k); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second.k == b->second.k); -} -static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0; - t0 = clock(); - IterN a, z; - if(normal[i].size() == 0 || normal[i].begin()->first > key){ - a = normal[i].end(); - }else{ - for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){ - if(z->first > key){ - break; - } - } - } - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second.k, - (b == splay[i].end()) ? 0 : b->second.k); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second.k == b->second.k); -} -static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0; - t0 = clock(); - IterN a, z; - if(normal[i].begin() == normal[i].end()){ - a = normal[i].end(); - }else{ - if(normal[i].begin()->first >= key) a = normal[i].end(); - else{ - for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){ - if(z->first >= key) - break; - } - } - } - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second.k, - (b == splay[i].end()) ? 0 : b->second.k); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second.k == b->second.k); -} -static bool find(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= find(%d, %d)\n", i, key); - t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0; - t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second.k, - (b == splay[i].end()) ? 0 : b->second.k); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second.k == b->second.k); -} -static bool order(int i, int order, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= order(%d, %d)\n", i, order); - t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0; - t0 = clock(); - IterN a = normal[i].begin(); - for(int k = 0; k < order; k++) a++; - (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second.k, - (b == splay[i].end()) ? 0 : b->second.k); - show(detail_fg); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()) return true; - return (a->first == b->first && a->second.k == b->second.k); -} -static bool first_last(int i, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= first_last(%d)\n", i); - IterN a; - t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0; - t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (a == normal[i].end()) ? 0 : a->first, - (b == splay[i].end()) ? 0 : b->first, - (a == normal[i].end()) ? 0 : a->second.k, - (b == splay[i].end()) ? 0 : b->second.k); - if((a == normal[i].end()) != (b == splay[i].end())) return false; - if( a == normal[i].end()); - else{ - if((a->first == b->first && a->second.k == b->second.k) == false){ - return false; - } - } - t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0; - t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0; - detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", - (r == normal[i].rend()) ? 0 : r->first, - (b == splay[i].end()) ? 0 : b->first, - (r == normal[i].rend()) ? 0 : r->second.k, - (b == splay[i].end()) ? 0 : b->second.k); - if((r == normal[i].rend()) != (b == splay[i].end())) return false; - if(r == normal[i].rend()); - else{ - if((r->first == b->first && r->second.k == b->second.k) == false){ - return false; - } - } - return true; -} -static bool insert(int i, int key, Double val, size_t* tN, size_t* tS){ - size_t t0; - if(rand() & 1){ - t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0; - t0 = clock(); normal[i].insert(std::pair<int, Double>(key, val)); (*tN) += clock() - t0; - }else{ - t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0; - t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0; - } - detail_fg && printf("============= insert(%d, %d)\n", i, key); - show(detail_fg); - return true; -} -static bool split(int i, int j, int key, size_t* tN, size_t* tS){ - size_t t0; - if(i == j){ - return true; - } - detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key); - t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0; - t0 = clock(); - normal[j].clear(); - for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){ - normal[j].insert(*it); - normal[i].erase(it); - } - *tN += clock() - t0; - show(detail_fg); - return true; -} -static bool merge(int i, int j, int key, size_t* tN, size_t* tS){ - size_t t0; - if(i == j){ - return true; - } - if(rand() & 1){ - t0 = clock(); - if(splay[i].size() > 0) - while(splay[j].size() > 0 && - splay[j].first()->first <= splay[i].last()->first){ - splay[j].erase(splay[j].first()->first); - } - *tS += clock() - t0; - t0 = clock(); - if(normal[i].size() > 0) - while(normal[j].size() > 0 && - normal[j].begin()->first <= normal[i].rbegin()->first) - normal[j].erase(normal[j].begin()); - *tN += clock() - t0; - } - t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0; - t0 = clock(); - if(normal[i].size() == 0 || normal[j].size() == 0 || - normal[i].rbegin()->first < normal[j].begin()->first || - normal[j].rbegin()->first < normal[i].begin()->first - ){ - for(IterN it = normal[j].begin(); it != normal[j].end(); it++){ - normal[i].insert(*it); - } - normal[j].clear(); - } - *tN += clock() - t0; - detail_fg && printf("============= merge(%d, %d)\n", i, j); - show(detail_fg); - return true; -} -static bool erase(int i, int key, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= erase(%d, %d)\n", i, key); - t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0; - t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0; - show(detail_fg); - return true; -} -static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta); - t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0; - t0 = clock(); - std::map<int, Double> tmp = normal[i]; - normal[i].clear(); - for(IterN it = tmp.begin(); it != tmp.end(); it++){ - normal[i].insert(std::pair<int, Double>(it->first + delta, it->second.k)); - } - (*tN) += clock() - t0; - show(detail_fg); - return true; -} -static bool valueOffset(int i, Double delta, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta.k); - t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0; - t0 = clock(); - for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ - it->second = it->second + delta; - } - (*tN) += clock() - t0; - show(detail_fg); - return true; -} -static bool valueOverride(int i, Double value, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= valueOverride(%d, %f)\n", i, value.k); - t0 = clock(); splay[i].valueOverride(value); (*tS) += clock() - t0; - t0 = clock(); - for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ - it->second.k = value.k; - } - (*tN) += clock() - t0; - show(detail_fg); - return true; -} -static bool query(int i, int a, int b, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("============= query(%d, %d, %d)\n", i, a, b); - Double ans1, ans2 = 0; - if((rand() & 3) == 3){ - t0 = clock(); ans1 = splay[i].query(); (*tS) += clock() - t0; - t0 = clock(); - for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ - ans2 = ans2 | it->second.k; - } - }else{ - t0 = clock(); ans1 = splay[i].query(a, b); (*tS) += clock() - t0; - t0 = clock(); - for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ - if(a <= it->first && it->first <= b) - ans2 = ans2 | it->second.k; - } - } - detail_fg && printf(">>get %f %f\n", ans1.k, ans2.k); - show(detail_fg); - return true; -} -static bool copy(int i, int j, size_t* tN, size_t* tS){ - size_t t0; - detail_fg && printf("copy(%d, %d)\n", i, j); - t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0; - t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0; - show(detail_fg); - return true; -} - -static bool check(){ - for(int i = 0; i < N; i++){ - if(normal[i].size() != splay[i].size()) return false; - int j = 0; - for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){ - if(it->first != splay[i].order(j)->first || - it->second.k != splay[i].order(j)->second.k) - return false; - } - } - return true; -} - -TEST(SplayTree_Range, "..."){ - detail_fg = false; - N = 5; - for(int i = 0; i < 10; i++){ - normal.clear(); - splay .clear(); - normal.resize(N); - splay .resize(N); - size_t tn = 0, tm = 0; - int op = 1 + rand() % 2000000; - min_sum = rand() & 1; - meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op); - while(op--){ - int wh = rand() % 100; - int i1 = rand() % N, i2, k = rand() % 60; - while((i2 = rand() % N) == i1); - switch(wh){ - case 0: - if(lowerBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "lowerBound"); - show(true); - return false; - } - break; - case 1: - if(rUpperBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "rUpperBound"); - show(true); - return false; - } - break; - case 2: - if(rLowerBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "rLowerBound"); - show(true); - return false; - } - break; - case 3: - if(upperBound(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "upperBound"); - show(true); - return false; - } - break; - case 4: - case 5: - case 6: - if(find(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "find"); - show(true); - return false; - } - break; - case 7: - case 8: - case 9: - if(normal[i1].size() > 0){ - if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "order"); - show(true); - return false; - } - break; - } - case 10: - if(first_last(i1, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "first_last"); - show(true); - return false; - } - break; - case 11: - case 12: - case 13: - case 14: - case 15: - case 16: - case 17: - case 18: - case 19: - case 20: - if(insert(i1, k, rand() * 1.0 / RAND_MAX * 50 + 1, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "insert"); - show(true); - return false; - } - break; - case 21: - case 22: - case 23: - case 24: - case 25: - case 26: - if(split(i1, i2, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "split"); - show(true); - return false; - } - break; - case 27: - case 28: - case 29: - case 30: - case 31: - case 32: - case 33: - case 34: - case 35: - case 36: - if(merge(i1, i2, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "merge"); - show(true); - return false; - } - break; - case 37: - case 38: - case 39: - case 40: - if(erase(i1, k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "erase"); - show(true); - return false; - } - break; - case 41: - case 42: - case 43: - case 44: - case 45: - case 46: - case 47: - case 48: - case 49: - if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "keyOffset"); - show(true); - return false; - } - break; - case 50: - case 51: - case 52: - if(copy(i1, i2, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "copy"); - show(true); - return false; - } - break; - case 53: - case 54: - case 55: - case 56: - case 57: - case 58: - case 59: - if(valueOverride(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "valueOffset"); - show(true); - return false; - } - break; - case 60: - case 61: - case 62: - case 63: - case 64: - case 65: - case 66: - if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "valueOffset"); - show(true); - return false; - } - break; - default: - if(query(i1, rand() % 200 - 100, rand() % 200 - 100, &tn, &tm) == false){ - meow::messagePrintf(-1, "fail(%s)", "query"); - show(true); - return false; - } - break; - } - } - if(!check()){ - meow::messagePrintf(-1, "fail"); - show(true); - return false; - } - meow::messagePrintf(-1, "ok %.3f/%.3f", - tm * 1.0 / CLOCKS_PER_SEC, - tn * 1.0 / CLOCKS_PER_SEC); - } - return true; -} diff --git a/meowpp.test/src/VP_Tree.cpp b/meowpp.test/src/VP_Tree.cpp deleted file mode 100644 index 8e93224..0000000 --- a/meowpp.test/src/VP_Tree.cpp +++ /dev/null @@ -1,189 +0,0 @@ -#include "meowpp/dsa/VP_Tree.h" -#include "meowpp/dsa/KD_Tree.h" -#include "meowpp/utility.h" - - -#include "dsa.h" - -#include <vector> - -#include <cmath> -#include <cstdlib> -#include <algorithm> -#include <ctime> - -extern "C" { -#include <sys/types.h> -} - -#include <queue> - -static int N = 100000; -static int D = 32; -static int MAX = 1000; - -typedef int64_t lnt; - -struct MyVector{ - std::vector<lnt> v; - int w; - // - MyVector(MyVector const& _v): v(_v.v), w(_v.w){ } - MyVector( ):v(D){ for(int i = 0; i < D; i++){ v[i] = (lnt)rand() % MAX; } } - MyVector(lnt k):v(D){ for(int i = 0; i < D; i++){ v[i] = k; } } - // - lnt & operator[](size_t n) { return v[n]; } - lnt const& operator[](size_t n) const{ return v[n]; } - bool operator<(MyVector const& v2) const{ return (w < v2.w); } - bool operator==(MyVector const& v2) const{ - for(int i = 0; i < D; i++) if(v[i] != v2[i]) return false; - return (w == v2.w); - } -}; - - -static lnt dist2(MyVector const& v1, MyVector const& v2){ - lnt k = 0; - for(int i = 0; i < D; i++){ - k += (v1[i] - v2[i]) * (v1[i] - v2[i]); - } - return k; -} - -static std::vector<MyVector> data; - -void show(MyVector const& v, std::vector<MyVector> const& r1, std::vector<MyVector> const& r2){ - if(N <= 20 && r1.size() <= 7){ - printf("\n"); - for(int i = 0; i < N; i++){ - printf("%3d) ", data[i].w); - for(int j = 0; j < D; j++) - printf("%8ld ", data[i][j]); - printf(" ===> %ld\n", dist2(data[i], v)); - } - printf("\n"); - printf("ask) "); - for(int j = 0; j < D; j++) - printf("%8ld ", v[j]); - printf("\n"); - printf("---------\n"); - for(size_t i = 0; i < r1.size(); i++){ - printf("%3d) ", r1[i].w); - for(int j = 0; j < D; j++) - printf("%8ld ", r1[i][j]); - printf(" ===> %ld\n", dist2(r1[i], v)); - } - printf("---------\n"); - for(size_t i = 0; i < r2.size(); i++){ - printf("%3d) ", r2[i].w); - for(int j = 0; j < D; j++) - printf("%8ld ", r2[i][j]); - printf(" ===> %ld\n", dist2(r2[i], v)); - } - } -} - -namespace VP{ - struct Answer{ - int i; - lnt d; - // - Answer(int _i, lnt _d): i(_i), d(_d){ } - Answer(Answer const& _a): i(_a.i), d(_a.d){ } - // - bool operator<(Answer const& b) const{ - if(d != b.d) return (d < b.d); - else return (data[i] < data[b.i]); - } - }; -} - -static std::vector<MyVector> find(MyVector const& v, int k){ - std::priority_queue<VP::Answer> qu; - for(int i = 0; i < std::min(k, N); i++){ - qu.push(VP::Answer(i, dist2(v, data[i]))); - } - for(int i = std::min(k, N); i < N; i++){ - qu.push(VP::Answer(i, dist2(v, data[i]))); - qu.pop(); - } - std::vector<MyVector> ret(qu.size()); - for(int i = (ssize_t)qu.size() - 1; i >= 0; i--){ - ret[i] = data[qu.top().i]; - qu.pop(); - } - return ret; -} - -TEST(VP_Tree, "A little bit slow"){ - int t0, t1, t2; - - meow::VP_Tree<MyVector, lnt> tree(D); - - meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D); - data.resize(N); - for(int i = 0; i < N; i++){ - if(i <= N / 10) - data[i] = MyVector((lnt)i); - else{ - for(int j = 0; j < D; j++){ - data[i][j] = rand() % MAX; - } - } - } - for(int i = 0; i < N; i++){ - data[i].w = i; - } - for(int i = 0; i < N; i++){ - tree.insert(data[i]); - } - meow::messagePrintf(-1, "ok"); - meow::messagePrintf(1, "build"); - t0 = clock(); - tree.build(); - //tree.print(); - meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC); - - meow::messagePrintf(1, "query..."); - meow::KD_Tree<MyVector, lnt>::Vectors ret1, ret2; - for(int k = 1; k <= std::min(100, N); k++){ - meow::messagePrintf(1, "range k = %d", k); - t1 = t2 = 0; - for(int i = 0; i < 10; i++){ - MyVector ask; - - t0 = clock(); - tree.build(); - ret1 = tree.query(ask, k, true); - t1 += clock() - t0; - - t0 = clock(); - ret2 = find(ask, k); - t2 += clock() - t0; - - if(ret1.size() != ret2.size() && false){ - meow::messagePrintf(-1, "(%d)query fail, size error", i); - meow::messagePrintf(-1, "fail"); - return false; - } - for(int kk = 0, KK = ret1.size(); kk < KK; kk++){ - if(ret1[kk] == ret2[kk]){ - continue; - } - show(ask, ret1, ret2); - meow::messagePrintf(-1, "(%d)query fail", i); - meow::messagePrintf(-1, "fail"); - return false; - } - } - meow::messagePrintf(-1, "ok %.3f/%.3f", - t1 * 1.0 / CLOCKS_PER_SEC, - t2 * 1.0 / CLOCKS_PER_SEC - ); - } - meow::messagePrintf(-1, "ok"); - - - return true; -} - diff --git a/meowpp.test/src/autostitch.cpp b/meowpp.test/src/autostitch.cpp deleted file mode 100644 index 8472a74..0000000 --- a/meowpp.test/src/autostitch.cpp +++ /dev/null @@ -1,464 +0,0 @@ -#include <cstdio> - -#include "autostitch.h" - -#include <opencv/cv.h> -#include <opencv/highgui.h> - -#include "meowpp/Usage.h" - -#include "meowpp/colors/RGB_Space.h" - -#include "meowpp/dsa/DisjointSet.h" - -#include "meowpp/geo/Vectors.h" - -#include "meowpp/gra/Bitmap.h" -#include "meowpp/gra/Photo.h" -#include "meowpp/gra/Camera.h" - -#include "meowpp/math/utility.h" -#include "meowpp/math/methods.h" - - -extern "C"{ -#include <sys/types.h> -#include <dirent.h> -} - -#include <vector> -#include <algorithm> -#include <string> -#include <cstdlib> - - -using namespace meow; - -////////////////////////////////////////////////////////////////////// - -Usage usg("autostitch"); - -double p0 = 0.07, P = 0.99; -double q = 0.7, r = 0.01, Q = 0.97; -double stop = 1; -double o_radius = 500; -double angle_t = PI / 4.0; -double aspect_t = 2.0; - -std::vector<std::string> input_name; - -MyK_Match match; -std::vector<Bitmap<RGBf_Space> > input_bitmap; -std::vector<Bitmap<RGBf_Space> > output_bitmap; - -std::vector<std::vector<FeaturePoint<double, double> > > fps; -std::vector<std::vector<Vector<double> > > fpsv; -std::vector<std::vector<FeaturePointIndexPairs > > pairs; - -struct OutputSet { - struct Edge { - std::vector<Vector<double> > v1; - std::vector<Vector<double> > v2; - size_t i1, i2; - bool done; - Edge(size_t ii1, size_t ii2): i1(ii1), i2(ii2) { - done = false; - } - bool operator<(Edge const& e) const { - return (v1.size() < e.v1.size()); - } - }; - std::vector<Camera<RGBf_Space> > cameras; - std::vector<Edge> edges; -}; - -std::vector<OutputSet> outputs; - -//////////////////////////// **# setup #** /////////////////////////// -bool setup(int argc, char** argv) { - usg.optionAdd("h", "Display this help document."); - usg.optionAdd("i", - "Specify the input images are in <type> " - "instead of specifying from arguments", - "<dirname>", "", - false); - usg.optionAdd("o", - "Output file name, (not include '.jpg' suffix)", - "<filename>", - "output", - false); - usg.optionAdd("f", - "File name for output the text data", - "<filename>", - "output.txt", - false); - usg.optionAdd("d", - "Specify which Feature-Point-Detect algorithm to use", - "<algorithm>", - "", - true); - usg.optionAdd("ransac-p0", - "Pribabilicity for RANSAC to choose a right feature point", - "<floating point>", stringPrintf("%.10f", p0), - false); - usg.optionAdd("ransac-ok", - "Pribabilicity for RANSAC access", - "<floating point>", stringPrintf("%.10f", P), - false); - usg.optionAdd("prob-p1", - "p1 for Prob. Model", - "<floationg Point>", stringPrintf("%.10f", q), - false); - usg.optionAdd("prob-p0", - "p0 for Prob. Model", - "<floationg Point>", stringPrintf("%.10f", r), - false); - usg.optionAdd("prob-min", - "p_min for Prob. Model", - "<floationg Point>", stringPrintf("%.10f", Q), - false); - usg.optionAdd("s", - "stop threshold for boundle adjustment", - "<floationg Point>", stringPrintf("%.10f", stop), - false); - usg.optionAdd("output-radius", - "output ball radius", - "<floationg Point>", stringPrintf("%.10f", o_radius), - false); - usg.optionAdd("match-angle", - "angle threshold for matching", - "<floating point>", stringPrintf("%.10f", angle_t / PI * 180), - false); - usg.optionAdd("match-aspect", - "aspect threshold for matching", - "<floating point>", stringPrintf("%.10f", aspect_t), - false); - std::vector<std::string> fpsd_algorithm_list = ObjSelector<FPSD_ID>::names(); - for (size_t i = 0, I = fpsd_algorithm_list.size(); i < I; i++) { - const ObjBase* tmp = ObjSelector<FPSD_ID>::get(fpsd_algorithm_list[i]); - usg.optionValueAcceptAdd("d", - fpsd_algorithm_list[i], - tmp->type()); - usg.import(((MyFeaturePointsDetector*)tmp)->usage()); - } - usg.import(match.usage()); - usg.import(MyRansacCheck::usage()); - // set arg - std::string err_msg; - bool ok = usg.arguments(argc, argv, &err_msg); - if (usg.hasOptionSetup("h")) { - printf("%s\n", usg.usage().c_str()); - exit(0); - } - if (!ok) { - fprintf(stderr, "%s\n", err_msg.c_str()); - exit(-1); - } - return true; -} - - -//////////////// **# Input images and convert it #** ///////////////// -bool input() { - if (!usg.hasOptionSetup("i")) { - input_name = usg.procArgs(); - } - else { - std::string base = usg.optionValue("i", 0); - if (base.length() == 0 || base[base.length() - 1] != '/') { - base += "/"; - } - DIR* dir = opendir(base.c_str()); - if (!dir) { - fprintf(stderr, "can't open dir '%s'\n", base.c_str()); - return -1; - } - for (dirent* ent; (ent = readdir(dir)) != NULL; ) { - if (!cstringEndWith(ent->d_name, 4, ".jpeg", ".jpg", ".JPG", ".JPEG")) { - continue; - } - input_name.push_back(base + std::string(ent->d_name)); - } - } - messagePrintf(1, "Loading images"); - for (size_t i = 0; i < input_name.size(); i++) { - messagePrintf(1, "%s", input_name[i].c_str()); - cv::Mat img = cv::imread(input_name[i], CV_LOAD_IMAGE_COLOR); - if (!img.data) { - messagePrintf(-1, "opencv read error!, ignore"); - continue; - } - size_t width = img.size().width ; - size_t height = img.size().height; - size_t index = input_bitmap.size(); - input_bitmap.resize(index + 1); - input_bitmap[index].size(height, width, RGBf_Space(0)); - for (size_t x = 0; x < width; x++) { - for (size_t y = 0; y < height; y++) { - RGBi_Space tmp(Vector3D<int>( - img.at<cv::Vec3b>(y, x)[2], - img.at<cv::Vec3b>(y, x)[1], - img.at<cv::Vec3b>(y, x)[0])); - RGBf_Space p; - colorTransformate(tmp, &p); - input_bitmap[index].pixel(y, x, p); - } - } - messagePrintf(-1, "%lux%lu, ok", width, height); - } - messagePrintf(-1, "ok"); - return true; -} - -//////////////////////// **# FeaturePoint #** //////////////////////// -bool detect() { - std::string fpsd_algo_name = usg.optionValue("d", 0); - MyFeaturePointsDetector* detector( - (MyFeaturePointsDetector*)ObjSelector<FPSD_ID>::create(fpsd_algo_name)); - detector->usage(usg); - fps .resize(input_bitmap.size()); - fpsv.resize(input_bitmap.size()); - for (size_t i = 0, I = input_bitmap.size(); i < I; i++) { - messagePrintf(1, "Detect the feature points for %lu-th pic", i); - fps[i] = detector->detect(input_bitmap[i]); - messagePrintf(-1, "ok, %lu", fps[i].size()); - for (size_t j = 0, J = fps[i].size(); j < J; j++) { - fpsv[i].push_back(fps[i][j].position()); - } - } - delete detector; - return true; -} - - -//////////////////////////// **# k-match #** ///////////////////////// -bool kmatch() { - match.usage(usg); - messagePrintf( 1, "run k-match"); - FeaturePointIndexPairs mat(match.match(fps)); - pairs.resize(input_bitmap.size()); - for (size_t i = 0, I = input_bitmap.size(); i < I; i++) { - pairs[i].resize(I); - } - for (size_t i = 0, I = mat.size(); i < I; ++i) { - pairs[mat[i].from.first][mat[i].to.first].push_back(mat[i]); - } - messagePrintf(-1, "ok"); - return true; -} - -//////////////////////////// **# RANSAC #** ////////////////////////// -bool ransac() { - messagePrintf( 1, "RANSAC"); - aspect_t = inRange(0.000001, 9999.0, atof(usg.optionValue("match-aspect", 0).c_str())); - angle_t = inRange(0.1,999.0, atof(usg.optionValue("match-angle", 0).c_str()))/180 * PI; - MyRansacCheck::usage(usg); - // tmp output - p0 = inRange(0.00001, 0.9999, atof(usg.optionValue("ransac-p0", 0).c_str())); - P = inRange(0.00001, 0.9999, atof(usg.optionValue("ransac-ok", 0).c_str())); - for (size_t i = 0, I = input_bitmap.size(); i < I; i++) { - for (size_t j = 0, J = input_bitmap.size(); j < J; j++) { - size_t num = 4u; // !!!!!!!!!!!!!!!!!!! - messagePrintf( 1, "ransac %lu --- %lu", i, j); - MyRansacCheck chk(&(fpsv[i]), &(fpsv[j]), - input_bitmap[i].width(), input_bitmap[i].height(), - aspect_t, angle_t); - FeaturePointIndexPairs ret = ransac(pairs[i][j], chk, num, p0, P); - if (!ret.empty()) { - chk.rememberVCalc(ret); - FeaturePointIndexPairs ok(ret); - for (size_t k = 0, K = pairs[i][j].size(); k < K; k++) { - bool chk_again = true; - for (size_t l = 0, L = ret.size(); chk_again && l < L; l++) { - if (ret[l] == pairs[i][j][k]) { - chk_again = false; - } - } - if (chk_again && chk.ok(pairs[i][j][k])) { - ok.push_back(pairs[i][j][k]); - } - } - if (ok.size() >= num) pairs[i][j] = ok; - else pairs[i][j].clear(); - messagePrintf(-1, "ok(%lu)", pairs[i][j].size()); - } - else { - pairs[i][j].clear(); - messagePrintf(-1, "empty"); - } - } - } - messagePrintf(-1, "ok"); - return true; -} - - - -//////////////////// **# checking match again #** //////////////////// -bool match_check() { - q = inRange(0.00001, 0.99999, atof(usg.optionValue("prob-p1", 0).c_str())); - r = inRange(0.00001, 0.99999, atof(usg.optionValue("prob-p0", 0).c_str())); - Q = inRange(0.00001, 0.99999, atof(usg.optionValue("prob-min", 0).c_str())); - aspect_t = inRange(0.000001, 9999.0, atof(usg.optionValue("match-aspect", 0).c_str())); - angle_t = inRange(0.1,999.0, atof(usg.optionValue("match-angle", 0).c_str()))/180 * PI; - double m_ni = log(q * (1 - r)) - log(r * (1 - q)); - double c = log(Q) - log(1 - Q); - double m_nf = log(1 - r) - log(1 - q); - messagePrintf(1, "run prob_mod, ni * %.7f > %.7f + nf * %.7f ???", - m_ni, c, m_nf); - for (size_t i = 0, I = input_bitmap.size(); i < I; i++) { - for (size_t j = 0, J = input_bitmap.size(); j < J; j++) { - if (pairs[i][j].empty()) { - continue; - } - double ni = pairs[i][j].size(), nf = 0; - size_t num = 4u; - MyRansacCheck chk(&(fpsv[i]), &(fpsv[j]), - input_bitmap[i].width(), input_bitmap[i].height(), - aspect_t, angle_t); - FeaturePointIndexPairs ret = ransac(pairs[i][j], chk, num, p0, P); - - chk.rememberVCalc(pairs[i][j]); - if (chk.check()) { - chk.print(); - for (size_t k = 0, K = fpsv[i].size(); k < K; k++) { - Vector2D<double> to(chk.to(Vector2D<double>(fpsv[i][k](0), - fpsv[i][k](1)))); - if (0 <= to.x() && to.x() <= (double)input_bitmap[j].width() && - 0 <= to.y() && to.y() <= (double)input_bitmap[j].height()) { - nf++; - } - } - if (ni * m_ni > c + m_nf * nf) { - messagePrintf(0, "accept %lu --- %lu", i, j); - messagePrintf(0, - "%.0f * %.3f = %.3f ?? %.3f = %.3f + %.3f * %.0f", - ni, m_ni, ni * m_ni, c + m_nf * nf, c, m_nf, nf); - continue; - } - } - pairs[i][j].clear(); - } - } - messagePrintf(-1, "ok"); - return true; -} - -////////////////////// **# Write to output file #** ////////////////// - -bool output() { - messagePrintf(1, "Write images"); - for (size_t i = 0; i < output_bitmap.size(); i++) { - size_t width = output_bitmap[i].width (); - size_t height = output_bitmap[i].height(); - cv::Mat img(height, width, CV_8UC3); - for (size_t x = 0; x < width; x++) { - for (size_t y = 0; y < height; y++) { - RGBi_Space tmp; - colorTransformate(output_bitmap[i].pixel(y, x), &tmp); - img.at<cv::Vec3b>(y, x)[0] = tmp.b(); - img.at<cv::Vec3b>(y, x)[1] = tmp.g(); - img.at<cv::Vec3b>(y, x)[2] = tmp.r(); - } - } - std::string output_name(usg.optionValue("o", 0) - + (output_bitmap.size() > 1 - ? stringPrintf("%lu", i) - : "") - + ".jpg"); - messagePrintf(1, "Write to file '%s'", output_name.c_str()); - if (imwrite(output_name, img) == false) { - messagePrintf(-1, "opencv fail, ignore"); - } - else { - messagePrintf(-1, "%lux%lu, ok", width, height); - } - } - messagePrintf(-1, "ok"); - return true; -} - -bool pair_output(){ - for(size_t i = 0, I = input_bitmap.size(); i < I; i++){ - for(size_t j = 0, J = input_bitmap.size(); j < J; j++){ - if(pairs[i][j].empty()) continue; - MyRansacCheck chk(&(fpsv[i]), &(fpsv[j]), - (double)input_bitmap[i].width(), (double)input_bitmap[i].height(), - aspect_t, angle_t); - chk.rememberVCalc(pairs[i][j]); - size_t index = output_bitmap.size(); - output_bitmap.push_back(input_bitmap[i]); - for(ssize_t x = 0, X = input_bitmap[i].width(); x < X; x++) { - for(ssize_t y = 0, Y = input_bitmap[i].height(); y < Y; y++) { - Vector2D<double> to(chk.to(Vector2D<double>(1.0 * x, 1.0 * y))); - ssize_t x2 = to.x(), y2 = to.y(); - if (0 <= x2 && x2 < (ssize_t)input_bitmap[j].width() && - 0 <= y2 && y2 < (ssize_t)input_bitmap[j].height()) { - output_bitmap[index].pixel(y, x, (input_bitmap[i].pixel(y, x) + - input_bitmap[j].pixel(y2,x2)) / 2 - ); - } - } - } - for (size_t k = 0, K = pairs[i][j].size(); k < K; ++k) { - ssize_t x0 = fpsv[i][pairs[i][j][k].from.second](0); - ssize_t y0 = fpsv[i][pairs[i][j][k].from.second](1); - for (ssize_t d = -10; d <= 10; ++d) { - if (0 <= x0 + d && x0 + d < (ssize_t)input_bitmap[i].width() - 1) { - output_bitmap[index].pixel(y0, x0 + d, - RGBf_Space(Vector3D<double>( - 1.0, 1.0, 0.0 - ))); - } - if (0 <= y0 + d && y0 + d < (ssize_t)input_bitmap[i].height() - 1) { - output_bitmap[index].pixel(y0 + d, x0, - RGBf_Space(Vector3D<double>( - 1.0, 1.0, 0.0 - ))); - } - } - } - } - } - return output(); -} - -bool text_output() { - std::string s = usg.optionValue("f", 0); - FILE* f = fopen(s.c_str(), "w"); - fprintf(f, "%lu\n", input_bitmap.size()); - for (size_t i = 0, I = input_bitmap.size(); i < I; ++i) { - fprintf(f, "%s\n", input_name[i].c_str()); - fprintf(f, "%lu %lu %lu ", - input_bitmap[i].height(), input_bitmap[i].width(), fpsv[i].size()); - for (size_t j = 0, J = fpsv[i].size(); j < J; ++j) { - fprintf(f, "%.10f %.10f ", fpsv[i][j](0), fpsv[i][j](1)); - } - fprintf(f, "\n"); - for (size_t j = 0; j < I; ++j) { - fprintf(f, "%lu ", pairs[i][j].size()); - for (size_t k = 0, K = pairs[i][j].size(); k < K; ++k) { - fprintf(f, "%lu %lu %lu %lu ", - pairs[i][j][k].from.first, - pairs[i][j][k].from.second, - pairs[i][j][k].to.first, - pairs[i][j][k].to.second); - } - fprintf(f, "\n"); - } - } - fclose(f); - return true; -} - -int main(int argc, char** argv){ - setup(argc, argv); - input(); - detect(); - kmatch(); - ransac(); - match_check(); - pair_output(); - text_output(); - return 0; -} diff --git a/meowpp.test/src/autostitch_FeaturePointsDetector_Harris.cpp b/meowpp.test/src/autostitch_FeaturePointsDetector_Harris.cpp deleted file mode 100644 index 573c4b6..0000000 --- a/meowpp.test/src/autostitch_FeaturePointsDetector_Harris.cpp +++ /dev/null @@ -1,73 +0,0 @@ -#include "autostitch.h" - -#include "meowpp/oo/ObjBase.h" -#include "meowpp/oo/ObjSelector.h" -#include "meowpp/geo/Vectors.h" -#include "meowpp/gra/FeaturePointsDetector_Harris.h" - -using namespace meow; - -class Harris: public MyFeaturePointsDetector{ - private: - FeaturePointsDetector_Harris<RGBf_Space> _body; - public: - Usage usage() const{ - Usage ret; - ret.optionAdd("harris-k", - "Specify the constant K of 'R = detM - KtraceM'", - "<floating point>", stringPrintf("%.10f", _body.paramK()), - false); - ret.optionAdd("harris-r", - "Specify the threshold of R to determind whether is " - "featuer point or not", - "<floating point>", stringPrintf("%.10f", _body.paramR()), - false); - ret.optionAdd("harris-w", - "Specify the sigma of the gaussian blur", - "<floating point>", stringPrintf("%.10f", _body.paramW()), - false); - ret.optionAdd("harris-n", - "Specify the sigma of the gaussian blur to de-noise", - "<floating point>", stringPrintf("%.10f", _body.paramN()), - false); - ret.optionAdd("harris-g", - "Specify the sigma of the gaussian blur to generate feature", - "<floating point>", stringPrintf("%.10f", _body.paramG()), - false); - ret.optionAdd("harris-l", - ".........", - "<floating point>", stringPrintf("%.10f", _body.paramL()), - false); - ret.optionAdd("harris-b", - "Description size", - "<number>", stringPrintf("%lu", _body.paramB()), - false); - return ret; - } - bool usage(meow::Usage const& usg){ - double K = atof(usg.optionValue("harris-k", 0).c_str()); - double R = atof(usg.optionValue("harris-r", 0).c_str()); - double W = atof(usg.optionValue("harris-w", 0).c_str()); - double N = atof(usg.optionValue("harris-n", 0).c_str()); - double L = atof(usg.optionValue("harris-l", 0).c_str()); - double G = atof(usg.optionValue("harris-g", 0).c_str()); - size_t B = atoi(usg.optionValue("harris-b", 0).c_str()); - _body.paramK(K); - _body.paramR(R); - _body.paramW(W); - _body.paramN(N); - _body.paramL(L); - _body.paramG(G); - _body.paramB(B); - return true; - } - std::vector<meow::FeaturePoint<double, double> > - detect(meow::Bitmap<RGBf_Space> const& bmp){ - return _body.detect(bmp); - } - - std::string type() const{ return std::string("Harris"); } - ObjBase* create() const{ return new Harris(); } -}; - -static meow::ObjSelector<FPSD_ID> __(new Harris(), true); diff --git a/meowpp.test/src/autostitch_K_Match.cpp b/meowpp.test/src/autostitch_K_Match.cpp deleted file mode 100644 index 6e5c69f..0000000 --- a/meowpp.test/src/autostitch_K_Match.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include "autostitch.h" - -#include "meowpp/utility.h" - -#include "meowpp/gra/FeaturePointsMatch_K_Match.h" - -#include "meowpp/Usage.h" - -using namespace meow; - -MyK_Match::MyK_Match(){ -} - - -MyK_Match::~MyK_Match(){ -} - - -Usage MyK_Match::usage() const{ - Usage usg; - usg.optionAdd("kmatch-k", - "k nearest neighbors", - "<number>", stringPrintf("%d", 5), - false); - return usg; -} - -bool MyK_Match::usage(meow::Usage const& usg){ - _body.paramK(atoi(usg.optionValue("kmatch-k", 0).c_str())); - return true; -} - -FeaturePointIndexPairs MyK_Match::match( - std::vector<std::vector<FeaturePoint<double, double> > > const& fp) { - return _body.match(fp[0][0].description().dimension(), fp); -} diff --git a/meowpp.test/src/autostitch_RansacCheck.cpp b/meowpp.test/src/autostitch_RansacCheck.cpp deleted file mode 100644 index 1516d1a..0000000 --- a/meowpp.test/src/autostitch_RansacCheck.cpp +++ /dev/null @@ -1,171 +0,0 @@ -#include "autostitch.h" - -#include "meowpp/math/Matrix.h" -#include "meowpp/math/Vector.h" -#include <utility> -#include <cmath> -#include <cstdio> -#include <algorithm> - - -using namespace meow; - -double MyRansacCheck::threshold = 5.0; - -meow::Usage MyRansacCheck::usage() { - Usage usg; - usg.optionAdd("ransac-threshold", - "Threshold for RANSAC", - "<floating point>", stringPrintf("%.10f", threshold), - false); - return usg; -} - -bool MyRansacCheck::usage(Usage const& usg) { - threshold = inRange(0.0000001, 1000.0, - atof(usg.optionValue("ransac-threshold", 0).c_str())); - return true; -} - -MyRansacCheck::MyRansacCheck() { -} - - -MyRansacCheck::MyRansacCheck(MyRansacCheck const& __rc): -_from(__rc._from), -_to(__rc._to){ -} - - -MyRansacCheck::MyRansacCheck(std::vector<Vector<double> > const* __from, - std::vector<Vector<double> > const* __to, - double w_max, double h_max, - double rr, double aa): -_from(__from), -_to(__to), -_w(w_max), -_h(h_max), -r_(rr), ang(aa) { -} - - -MyRansacCheck::~MyRansacCheck(){ -} - - -Vector<double> MyRansacCheck::vCalc(std::vector<FeaturePointIndexPair> const& __sample) const { - Matrix<double> m(__sample.size() * 2, 9, 0.0); - for (size_t i = 0, I = __sample.size(); i < I; ++i) { - m(i * 2 , 0, (*_from)[__sample[i].from.second](0)); - m(i * 2 , 1, (*_from)[__sample[i].from.second](1)); - m(i * 2 , 2, 1.0); - m(i * 2 , 6, -(*_from)[__sample[i].from.second](0) * (*_to)[__sample[i].to.second](0)); - m(i * 2 , 7, -(*_from)[__sample[i].from.second](1) * (*_to)[__sample[i].to.second](0)); - m(i * 2 , 8, (*_to)[__sample[i].to.second](0)); - m(i * 2 + 1, 3, (*_from)[__sample[i].from.second](0)); - m(i * 2 + 1, 4, (*_from)[__sample[i].from.second](1)); - m(i * 2 + 1, 5, 1.0); - m(i * 2 + 1, 6, -(*_from)[__sample[i].from.second](0) * (*_to)[__sample[i].to.second](1)); - m(i * 2 + 1, 7, -(*_from)[__sample[i].from.second](1) * (*_to)[__sample[i].to.second](1)); - m(i * 2 + 1, 8, (*_to)[__sample[i].to.second](1)); - } - if (__sample.size() == 4) { - m.triangulared(); - Vector<double> x(8, 0.0); - for (ssize_t i = 7; i >= 0; i--) { - double sum = 0; - for (size_t j = i + 1; j < 8u; j++) { - sum += x(j) * m(i, j); - } - x.scalar(i, (m(i, 8) - sum) / m(i, i)); - } - return x; - } - else { - Matrix<double> b(m.col(8)); - m.cols(8, 0.0); - Vector<double> v((m.transpose() * m).inverse() * m.transpose() * b); - return v; - } -} - - -void MyRansacCheck::rememberVCalc(std::vector<FeaturePointIndexPair> - const& __sample) { - Vector<double> x(vCalc(__sample)); - a_ = x(0); - b_ = x(1); - c_ = x(2); - d_ = x(3); - e_ = x(4); - f_ = x(5); - A_ = x(6); - B_ = x(7); -} - - -bool MyRansacCheck::ok(FeaturePointIndexPair const& __m) const { - Vector2D<double> from( - (*_from)[__m.from.second](0), - (*_from)[__m.from.second](1)); - Vector2D<double> me( - (*_to)[__m.to.second](0), - (*_to)[__m.to.second](1)); - Vector2D<double> me2(to(from)); - return ((me - me2).length2() <= threshold); -} - - -double MyRansacCheck::operator()(std::vector<FeaturePointIndexPair> - const& __sample, - std::vector<FeaturePointIndexPair> - const& __data) const { - for(size_t i = 0, I = __sample.size(); i < I; i++) { - for (size_t j = 0, J = __sample.size(); j < J; j++) { - if(i == j) continue; - if(__sample[i].from.second == __sample[j].from.second) return -1; - if(__sample[i].to .second == __sample[j].to .second) return -1; - } - } - ((MyRansacCheck*)this)->rememberVCalc(__sample); - if (!((MyRansacCheck*)this)->check()) return -999; - size_t ret = 0; - for (size_t i = 0, I = __data.size(); i < I; i++) { - if (ok(__data[i])) { - ret++; - } - } - return 0.001 + ret; -} - -bool MyRansacCheck::check() { - return true; - Vector2D<double> v_x(a_, b_); - Vector2D<double> v_y(c_, d_); - double xx[2] = {0, _w}, yy[2] = {0, _h}; - for (size_t i = 0; i < 2; ++i) { - for (size_t j = 0; j < 2; ++j) { - if (A_ * xx[i] + B_ * yy[j] + 1 <= 0) return false; - } - } - double len1 = v_x.length() * r_; - double len2 = v_x.length() / r_; - double len = v_y.length(); - if (len1 > len2) std::swap(len1, len2); - if (len < len1 || len2 < len) return false; - double sn = fabs(sin(ang)); - double msn = fabs(v_x.cross(v_y) / v_x.length() / v_y.length()); - if (msn < sn) return false; - return true; -} - -void MyRansacCheck::print() const { - printf("%f %f %f %f %f %f %f %f 1\n", a_, b_, c_, d_, e_, f_, A_, B_); -} - -Vector2D<double> MyRansacCheck::to(Vector2D<double> const& v) const { - return Vector2D<double>( - (v.x() * a_ + v.y() * b_ + c_) / (A_ * v.x() + B_ * v.y() + 1), - (v.x() * d_ + v.y() * e_ + f_) / (A_ * v.x() + B_ * v.y() + 1) - ); -} diff --git a/meowpp.test/src/dsa.cpp b/meowpp.test/src/dsa.cpp deleted file mode 100644 index 8a3c499..0000000 --- a/meowpp.test/src/dsa.cpp +++ /dev/null @@ -1,81 +0,0 @@ -#include "dsa.h" - -#include <vector> -#include <string> -#include <cstdlib> -#include <ctime> - -#include "meowpp/Usage.h" - -//////////////////////////// -meow::Usage usg("meowpp"), usg2; -int count = 0; -//////////////////////// - -int main(int argc, char** argv){ - std::vector<std::string> ids(meow::ObjSelector<0>::names()); - usg2.optionAdd("t", "Select which subject to test", - "<number>", "", - false); - for(size_t i = 0; i < ids.size(); i++){ - TestFunction* tmp = (TestFunction*)meow::ObjSelector<0>::get(ids[i]); - usg2.optionValueAcceptAdd("t", ids[i], tmp->name()+", "+tmp->description()); - } - - usg.optionAdd("h", "Display this help document"); - usg.optionAdd("help", "Display this help document"); - usg.usageBeginAdd("<name> is a little test program to check whether" - "the data structures in the template is correct by" - "random generate lots of data to test"); - usg.usageEndAdd ("zzzzzzzzzzzzzzz...."); - usg.import(usg2); - - std::string err; - if(usg.arguments(argc, argv, &err) == false){ - printf("%s\n\n%s\n", err.c_str(), usg.usage().c_str()); - return 1; - }else if(usg.hasOptionSetup("h") || usg.hasOptionSetup("help")) { - printf("%s", usg.usage().c_str()); - return 0; - }else{ - usg2.update(usg); - if(usg2.optionValuesSize("t") > 0){ - for(int i = 0, I = usg2.optionValuesSize("t"); i < I; i++){ - std::string wh = usg2.optionValue("t", i); - TestFunction* f = (TestFunction*)meow::ObjSelector<0>::get(wh); - if(f->run() == false){ - printf("error occure on %s\n", f->name().c_str()); - return 1; - }else{ - printf("%s success\n", f->name().c_str()); - } - } - }else{ - while(true){ - for(int i = 0, I = ids.size(); i < I; i++){ - TestFunction* tmp = (TestFunction*)meow::ObjSelector<0>::get(ids[i]); - printf(" %s) %s\n", ids[i].c_str(), tmp->name().c_str()); - } - printf("please select(EOF to quit): "); - int id; - if(!~scanf("%d", &id)){ - break; - } - printf("\n"); - TestFunction* f = (TestFunction*)meow::ObjSelector<0>::get(meow::stringPrintf("%d", id)); - if(f == NULL){ - printf("Bad value!\n\n"); - continue; - } - if(f->run() == false){ - printf("error occure on %s\n", f->name().c_str()); - return 1; - }else{ - printf("%s success\n", f->name().c_str()); - } - } - printf("\n"); - } - } - return 0; -} diff --git a/meowpp.test/src/features.cpp b/meowpp.test/src/features.cpp deleted file mode 100644 index b3c2ff6..0000000 --- a/meowpp.test/src/features.cpp +++ /dev/null @@ -1,205 +0,0 @@ -#include <cstdio> -#include <string> -#include <cstdlib> - -struct Job; - -void init ( ); -void setup(int argc, char** argv); -void end ( ); - -Job* get(size_t counter); - -void input (Job* job); -void handle(Job* job); -void output(Job* job); -void clear (Job* job); - -void info0 (Job* job); -void info1 (Job* job); -void info2 (Job* job); - -int main(int argc, char** argv) { - Job* now; - try { - init(); - setup(argc, argv); - for (size_t counter = 0; (now = get(counter)) != NULL; clear(now), ++counter) { - try { - input (now); info0(now); - handle(now); info1(now); - output(now); info2(now); - } - catch (std::string reason) { - throw reason.c_str(); - } - catch (char const* reason) { - printf("fail '%s', ignore.\n\n", reason); - continue; - } - printf("\n"); - } - end(); - } - catch (int num) { - return num; - } - return 0; -} - -/////////////////////////////////////////////////////////// - -#include "test_utility.h" -#include "features__.h" - -#include "meowpp/utility.h" -#include "meowpp/Usage.h" -#include "meowpp/oo/ObjSelector.h" - -#include <vector> -#include <algorithm> -#include <string> -#include <cstdio> - -using namespace meow; - -/////////////////////////////////////////////////////////// - -Usage usg("features"); - -FeaturePointsDetectors* detector; - -struct Job { - int id; - std::string file_name; - std::vector<FeaturePoint<double, double, Vector2D<double> > > fps; - Bitmap<RGBf_Space> bmp; -}; - -std::vector<std::string> names; - -std::string out_pre; - - -/////////////////////////////////////////////////////////// - -void init() { - usg.optionAdd("h" , "Display this help document"); - usg.optionAdd("help", "Display this help document"); - usg.optionAdd("i", - "Specify the input images are in a directory instead of" - " process arguments", - "pathname", - "", - false); - usg.optionAdd("r", - "recur"); - usg.optionAdd("o", - "Output images with denoting feature points", - "filename", - "", - false); - usg.optionAdd("d", - "Specify which feature detect algorithm to use", - "name", - "", - true); - std::vector<std::string> algo_list(ObjSelector<kFPSD_ID>::names()); - for (size_t i = 0, I = algo_list.size(); i < I; ++i) { - FeaturePointsDetectors const* f = (FeaturePointsDetectors const*)ObjSelector<kFPSD_ID>::get(algo_list[i]); - usg.optionValueAcceptAdd("d", algo_list[i], f->description()); - if (usg.import(f->usage()) == false) throw -1; - } -} - -void setup(int argc, char** argv) { - std::string err; - bool ret = usg.arguments(argc, argv, &err); - if (usg.hasOptionSetup("h") || usg.hasOptionSetup("help")) { - fprintf(stderr, "%s\n", usg.usage().c_str()); - throw 0; - } - if (ret == false) { - fprintf(stderr, "%s\n", err.c_str()); - throw -2; - } - - detector = (FeaturePointsDetectors*)ObjSelector<kFPSD_ID>::create(usg.optionValue("d", 0)); - if (detector->usage(usg) == false) throw -3; - - if (usg.hasOptionSetup("i")) { - names = cgetFiles(usg.optionValue("i", 0).c_str(), usg.hasOptionSetup("r"), - 4, ".jpg", ".jpeg", ".JPG", ".JPEG"); - } - else { - names = usg.procArgs(); - } - std::sort(names.begin(), names.end(), filenameCompare); - out_pre = usg.optionValue("o", 0); -} - -void end() { - delete detector; -} - -/////////////////////////////////////////////////////////// - -Job* get(size_t counter) { - if (counter >= names.size()) - return NULL; - Job* job = new Job; - job->id = counter; - job->file_name = names[counter]; - return job; -} - -/////////////////////////////////////////////////////////// - -void input(Job* job) { - if (readBitmap(job->file_name, &(job->bmp)) == false) - throw("cannot open image"); -} - -void handle(Job* job) { - job->fps = detector->detect(job->bmp); -} - -void output(Job *job) { - FILE* f = fopen((job->file_name + ".fps").c_str(), "w"); - fprintf(f, "%d %d\n%d\n", - (int)job->bmp.width(), (int)job->bmp.height(), (int)job->fps.size()); - for (size_t i = 0, I = job->fps.size(); i < I; ++i) { - job->fps[i].write(f, false, 0); - } - fclose(f); - if (out_pre.size() > 0) { - for (size_t i = 0, I = job->fps.size(); i < I; ++i) { - int x0 = job->fps[i].position()(0); - int y0 = job->fps[i].position()(1); - int w = std::min(job->bmp.width(), job->bmp.height()) / 32; - for (int x = x0 - w; x <= x0 + w; ++x) - if (0 <= x && x < (int)job->bmp.width()) - job->bmp.pixel(y0, x, RGBf_Space(Vector3D<double>(1.0, 0.0, 0.0))); - for (int y = y0 - w; y <= y0 + w; ++y) - if (0 <= y && y < (int)job->bmp.height()) - job->bmp.pixel(y, x0, RGBf_Space(Vector3D<double>(1.0, 0.0, 0.0))); - } - writeBitmap(stringPrintf("%s%d.jpg", out_pre.c_str(), job->id), job->bmp); - } -} - -void clear(Job *job) { - delete job; -} - -void info0(Job* job) { - printf("file name: %s, %dx%d\n", - job->file_name.c_str(), (int)job->bmp.width(), (int)job->bmp.height()); -} - -void info1(Job* job) { - printf("# of feature points: %d\n", (int)job->fps.size()); -} - -void info2(Job* job) { -} diff --git a/meowpp.test/src/features_Harris.cpp b/meowpp.test/src/features_Harris.cpp deleted file mode 100644 index 3f74145..0000000 --- a/meowpp.test/src/features_Harris.cpp +++ /dev/null @@ -1,96 +0,0 @@ -#include "features__.h" - -#include "meowpp/oo/ObjBase.h" -#include "meowpp/oo/ObjSelector.h" -#include "meowpp/geo/Vectors.h" -#include "meowpp/gra/FeaturePointsDetector_Harris.h" - -using namespace meow; - -class Harris: public FeaturePointsDetectors { - private: - FeaturePointsDetector_Harris<RGBf_Space, FeaturePoint<double, double, Vector2D<double> > > detector_; - public: - std::string description() const { - return "Harris-Corner-Detect"; - } - - Usage usage() const { - Usage ret; - ret.optionAdd("harris-k", - "Specify the constant K of 'R = detM - KtraceM'", - "<floating point>", - stringPrintf("%.10f", detector_.paramK()), - false); - ret.optionAdd("harris-r", - "Specify the threshold of R to determind whether is " - "featuer point or not", - "<floating point>", - stringPrintf("%.10f", detector_.paramR()), - false); - ret.optionAdd("harris-w", - "Specify the sigma of the gaussian blur", - "<floating point>", - stringPrintf("%.10f", detector_.paramW()), - false); - ret.optionAdd("harris-a", - "angle", - "<floating point>", - stringPrintf("%d", (int)detector_.paramA()), - false); - ret.optionAdd("harris-n", - "Specify the sigma of the gaussian blur to de-noise", - "<floating point>", - stringPrintf("%.10f", detector_.paramN()), - false); - ret.optionAdd("harris-g", - "Specify sigma of the gaussian blur to generate feature", - "<floating point>", - stringPrintf("%.10f", detector_.paramG()), - false); - ret.optionAdd("harris-l", - ".........", - "<floating point>", - stringPrintf("%.10f", detector_.paramL()), - false); - ret.optionAdd("harris-b", - "Description size", - "<number>", - stringPrintf("%lu", detector_.paramB()), - false); - return ret; - } - - bool usage(meow::Usage const& usg) { - double K = atof(usg.optionValue("harris-k", 0).c_str()); - double R = atof(usg.optionValue("harris-r", 0).c_str()); - double W = atof(usg.optionValue("harris-w", 0).c_str()); - double N = atof(usg.optionValue("harris-n", 0).c_str()); - double L = atof(usg.optionValue("harris-l", 0).c_str()); - double G = atof(usg.optionValue("harris-g", 0).c_str()); - size_t B = atoi(usg.optionValue("harris-b", 0).c_str()); - size_t A = atoi(usg.optionValue("harris-a", 0).c_str()); - detector_.paramK(K); - detector_.paramR(R); - detector_.paramW(W); - detector_.paramN(N); - detector_.paramL(L); - detector_.paramG(G); - detector_.paramB(B); - detector_.paramA(A); - return true; - } - - FeaturePoints detect(Bitmap<RGBf_Space> const& bmp) { - return detector_.detect(bmp); - } - - size_t dSize() const { - return detector_.descriptionDimension(); - } - - std::string type() const { return std::string("Harris"); } - ObjBase* create() const { return new Harris(); } -}; - -static meow::ObjSelector<kFPSD_ID> __(new Harris(), true); diff --git a/meowpp.test/src/match.cpp b/meowpp.test/src/match.cpp deleted file mode 100644 index 8fec09b..0000000 --- a/meowpp.test/src/match.cpp +++ /dev/null @@ -1,410 +0,0 @@ -#include <cstdio> -#include <string> -#include <cstdlib> - -struct Job; - -void init ( ); -void setup(int argc, char** argv); -void end ( ); - -Job* get(size_t counter); - -void input (Job* job); -void handle(Job* job); -void output(Job* job); -void clear (Job* job); - -void info0 (Job* job); -void info1 (Job* job); -void info2 (Job* job); - -int main(int argc, char** argv) { - Job* now; - try { - init(); - setup(argc, argv); - for (size_t counter = 0; (now = get(counter)) != NULL; clear(now), ++counter) { - try { - input (now); info0(now); - handle(now); info1(now); - output(now); info2(now); - } - catch (std::string reason) { - throw reason.c_str(); - } - catch (char const* reason) { - printf("fail '%s', ignore.\n\n", reason); - continue; - } - printf("\n"); - } - end(); - } - catch (int num) { - return num; - } - return 0; -} - -/////////////////////////////////////////////////////////// - -#include "test_utility.h" -#include "match.h" - -#include "meowpp/utility.h" -#include "meowpp/Usage.h" -#include "meowpp/oo/ObjSelector.h" -#include "meowpp/gra/IdentityPoints.h" - -#include <vector> -#include <algorithm> -#include <string> -#include <cstdio> - -using namespace meow; - -/////////////////////////////////////////////////////////// - -Usage usg("match"); - -MatchAll* match_all; -MatchOne* match_one; -MatchChk* match_chk; - -struct Job { - struct Picture { - std::string fname; - size_t width; - size_t height; - std::vector<FP> features; - std::vector<Vector2D<double> > fvs; - IdentityPoints<int, double, Vector2D<double> > fps; - Picture(): fps(2) { - } - }; - std::vector<Picture> pictures; - std::vector<std::vector<std::vector<Pair> > > pairs; - std::vector<std::vector<MatchInfo> > matches; -}; - -std::vector<Job> jobs; - -std::vector<std::string> names; - -std::string out_pre; - - -/////////////////////////////////////////////////////////// - -void init() { - usg.optionAdd("h" , "Display this help document"); - usg.optionAdd("help", "Display this help document"); - usg.optionAdd("i", - "Specify the input images are in a directory instead of" - " process arguments", - "pathname", - "", - false); - usg.optionAdd("r", - "recur"); - usg.optionAdd("o", - "Output images with denoting matches", - "filename", - "", - false); - usg.optionAdd("a", - "Specify which feature match algorithm to use", - "name", - "", - true); - usg.optionAdd("m", - "Specify which match detect algorithm to use", - "name", - "", - true); - usg.optionAdd("c", - "Specify which match match_chk algorithm to use", - "name", - "", - true); - std::vector<std::string> algo_list; - algo_list = ObjSelector<kMatchAll_ID>::names(); - for (size_t i = 0, I = algo_list.size(); i < I; ++i) { - MatchAll const* f = (MatchAll const*)ObjSelector<kMatchAll_ID>::get(algo_list[i]); - usg.optionValueAcceptAdd("a", algo_list[i], f->description()); - if (usg.import(f->usage()) == false) - throw -1; - } - algo_list = ObjSelector<kMatchOne_ID>::names(); - for (size_t i = 0, I = algo_list.size(); i < I; ++i) { - MatchOne const* f = (MatchOne const*)ObjSelector<kMatchOne_ID>::get(algo_list[i]); - usg.optionValueAcceptAdd("m", algo_list[i], f->description()); - if (usg.import(f->usage()) == false) - throw -1; - } - algo_list = ObjSelector<kMatchChk_ID>::names(); - for (size_t i = 0, I = algo_list.size(); i < I; ++i) { - MatchChk const* f = (MatchChk const*)ObjSelector<kMatchChk_ID>::get(algo_list[i]); - usg.optionValueAcceptAdd("c", algo_list[i], f->description()); - if (usg.import(f->usage()) == false) - throw -1; - } -} - -void setup(int argc, char** argv) { - std::string err; - bool ret = usg.arguments(argc, argv, &err); - if (usg.hasOptionSetup("h") || usg.hasOptionSetup("help")) { - fprintf(stderr, "%s\n", usg.usage().c_str()); - throw 0; - } - if (ret == false) { - fprintf(stderr, "%s\n", err.c_str()); - throw -2; - } - - match_all = (MatchAll*)ObjSelector<kMatchAll_ID>::create(usg.optionValue("a", 0)); - match_one = (MatchOne*)ObjSelector<kMatchOne_ID>::create(usg.optionValue("m", 0)); - match_chk = (MatchChk*)ObjSelector<kMatchChk_ID>::create(usg.optionValue("c", 0)); - if (match_all->usage(usg) == false) throw -3; - if (match_one->usage(usg) == false) throw -4; - if (match_chk->usage(usg) == false) throw -5; - - if (usg.hasOptionSetup("i")) { - names = cgetFiles(usg.optionValue("i", 0).c_str(), usg.hasOptionSetup("r"), - 4, ".jpg", ".jpeg", ".JPG", ".JPEG"); - } - else { - names = usg.procArgs(); - } - std::sort(names.begin(), names.end(), filenameCompare); - out_pre = usg.optionValue("o", 0); -} - -void end() { - delete match_all; - delete match_one; - delete match_chk; -} - -/////////////////////////////////////////////////////////// - -Job* get(size_t counter) { - if (counter >= 1) return NULL; - Job* job = new Job; - for (size_t i = 0, I = names.size(); i < I; ++i) { - Job::Picture pic; - pic.fname = names[i]; - job->pictures.push_back(pic); - } - return job; -} - -/////////////////////////////////////////////////////////// - -void input(Job* job) { - for (int i = 0, I = job->pictures.size(); i < I; ++i) { - bool ok = true; - std::string fname = job->pictures[i].fname + ".fps"; - FILE* f = fopen(fname.c_str(), "r"); - if (f == NULL) { - printf("cannot open %s, ignore\n", fname.c_str()); - ok = false; - } - else { - size_t N; - if (fscanf(f, "%lu %lu %lu", &(job->pictures[i].width), &(job->pictures[i].height), &N) < 3) - ok = false; - for (size_t j = 0; ok && j < N; ++j) { - FeaturePoint<double, double, Vector2D<double> > fp; - if (fp.read(f, false, 0) == false) - ok = false; - job->pictures[i].features.push_back(fp); - } - fclose(f); - } - if (!ok) { - if (i != I - 1) - std::swap(job->pictures[i], job->pictures[I - 1]); - --I; - --i; - printf("format error '%s'\n", fname.c_str()); - } - else - printf("loaded %s\n", fname.c_str()); - } - job->pairs .resize(job->pictures.size()); - job->matches.resize(job->pictures.size()); - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) { - job->pairs [i].resize(job->pictures.size()); - job->matches[i].resize(job->pictures.size()); - } -} - -void handle(Job* job) { - // match all - printf("match all\n"); - std::vector<std::vector<FP> > fpss(job->pictures.size()); - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) - fpss[i] = job->pictures[i].features; - std::vector<PairToPair<size_t> > pps = match_all->match(fpss); - for (size_t i = 0, I = pps.size(); i < I; ++i) { - job->pairs[pps[i].from.first][pps[i].to.first].push_back(Pair(pps[i].from.second, pps[i].to.second)); - } - printf("pairs: \n"); - for (size_t i = 0, I = job->pairs.size(); i < I; ++i, printf("\n")) { - for (size_t j = 0; j < I; ++j) { - printf("%3d ", (int)job->pairs[i][j].size()); - } - } - - // match one - printf("match one\n"); - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) - for (size_t j = 0, J = job->pictures[i].features.size(); j < J; ++j) - job->pictures[i].fvs.push_back(job->pictures[i].features[j].position()); - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) - for (size_t j = 0; j < I; ++j) { - if (i == j) - continue; - job->matches[i][j] = match_one->match(job->pictures[i].fvs, - job->pictures[j].fvs, - job->pairs[i][j], - job->pictures[i].width, - job->pictures[i].height); - if (job->matches[i][j].ok) { - printf("ok for %3lu -- %3lu (%3d)\n", i, j, (int)job->matches[i][j].pairs.size()); - } - } - - // match_chk - printf("match check\n"); - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) - for (size_t j = 0; j < I; ++j) { - if (i == j || job->matches[i][j].ok == false) - continue; - job->matches[i][j].ok = match_chk->check(job->pictures[i].fvs, - job->pictures[i].width, - job->pictures[i].height, - job->pictures[j].fvs, - job->pictures[j].width, - job->pictures[j].height, - job->pairs[i][j], - job->matches[i][j]); - if (job->matches[i][j].ok == true) { - printf("accept %lu %lu (%lu)\n", i, j, job->matches[i][j].pairs.size()); - } - } - - // 整理 - int ct = 0; - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) - for (size_t j = 0; j < I; ++j) { - if (i == j || job->matches[i][j].ok == false) - continue; - for (size_t k = 0; k < job->matches[i][j].pairs.size(); ++k) { - job->pictures[i].fps.pointAdd(ct, job->pictures[i].fvs[job->matches[i][j].pairs[k].first ]); - job->pictures[j].fps.pointAdd(ct, job->pictures[j].fvs[job->matches[i][j].pairs[k].second]); - ct++; - } - } -} - -void output(Job *job) { - printf("output...\n"); - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) { - FILE* f = fopen((job->pictures[i].fname + ".fp2ds").c_str(), "w"); - job->pictures[i].fps.write(f, false, 0); - fclose(f); - } - if (out_pre.size() > 0) { - printf("output pictures\n"); - int ct = 0; - for (size_t i = 0, I = job->pictures.size(); i < I; ++i) - for (size_t j = 0; j < I; ++j) { - if (i == j || job->matches[i][j].ok == false) continue; - Bitmap<RGBf_Space> bmp1, bmp2; - if (readBitmap(job->pictures[i].fname, &bmp1) == false) continue; - if (readBitmap(job->pictures[j].fname, &bmp2) == false) continue; - Bitmap<RGBf_Space> out(bmp2); - Bitmap<double> sum(bmp2.height(), bmp2.width(), 1.0); - Matrix<double> m(3, 3, 0.0); - m.entry(0, 0, job->matches[i][j].x_axis.scalar(0)); - m.entry(0, 1, job->matches[i][j].x_axis.scalar(1)); - m.entry(0, 2, job->matches[i][j].x_offset); - m.entry(1, 0, job->matches[i][j].y_axis.scalar(0)); - m.entry(1, 1, job->matches[i][j].y_axis.scalar(1)); - m.entry(1, 2, job->matches[i][j].y_offset); - m.entry(2, 0, job->matches[i][j].depth(0)); - m.entry(2, 1, job->matches[i][j].depth(1)); - m.entry(2, 2, 1); - m.inversed(); - for (size_t y = 0, Y = bmp1.height(); y < Y; ++y) - for (size_t x = 0, X = bmp1.width(); x < X; ++x) { - RGBf_Space tmp(bmp1.pixel(y, x)); - tmp.b(0); - tmp.r(0); - bmp1.pixel(y, x, tmp); - } - for (size_t y = 0, Y = bmp2.height(); y < Y; ++y) - for (size_t x = 0, X = bmp2.width(); x < X; ++x) { - Vector3D<double> v2(x, y, 1.0), v1(m * v2.matrix()); - int x1 = v1(0) / v1(2); - int y1 = v1(1) / v1(2); - if (x1 < 0 || (int)bmp1.width() <= x1 || y1 < 0 || (int)bmp1.height() <= y1) continue; - sum.pixel(y, x, sum.pixel(y, x) + 1); - out.pixel(y, x, out.pixel(y, x) + bmp1.pixel(y1, x1)); - } - for (size_t y = 0, Y = out.height(); y < Y; ++y) - for (size_t x = 0, X = out.width(); x < X; ++x) - out.pixel(y, x, out.pixel(y, x) / sum.pixel(y, x)); - int w = std::min(out.height() , out.width()) / 32; - for (size_t k = 0, K = job->matches[i][j].pairs.size(); k < K; ++k) { - int id_j = job->matches[i][j].pairs[k].second; - int x0 = job->pictures[j].fvs[id_j].x(); - int y0 = job->pictures[j].fvs[id_j].y(); - for (int d = -w; d <= w; ++d) { - if (0 <= x0 + d && x0 + d < (int)out.width ()) out.pixel(y0, x0 + d, RGBf_Space(Vector3D<double>(1.0, 0.0, 0.0))); - if (0 <= y0 + d && y0 + d < (int)out.height()) out.pixel(y0 + d, x0, RGBf_Space(Vector3D<double>(1.0, 0.0, 0.0))); - } - } - for (size_t k = 0, K = job->pictures[i].fvs.size(); k < K; ++k) { - Vector2D<double> v_tr( - (job->pictures[i].fvs[k].dot(job->matches[i][j].x_axis) + job->matches[i][j].x_offset) / (job->pictures[i].fvs[k].dot(job->matches[i][j].depth) + 1), - (job->pictures[i].fvs[k].dot(job->matches[i][j].y_axis) + job->matches[i][j].y_offset) / (job->pictures[i].fvs[k].dot(job->matches[i][j].depth) + 1) - ); - if (v_tr.x() < 0 || out.width () <= v_tr.x()) continue; - if (v_tr.y() < 0 || out.height() <= v_tr.y()) continue; - for (size_t l = 0, L = job->pairs[i][j].size(); l < L; ++l) { - if (job->pairs[i][j][l].first == k) { - Vector2D<double> v2(job->pictures[j].fvs[job->pairs[i][j][l].second]); - Vector2D<double> delta(v2 - v_tr); - for (int z = 0, Z = delta.length(); z <= Z; ++z) { - Vector2D<double> v(v_tr + delta * (double)z / (double)Z); - if (v.x() < 0 || out.width () <= v.x()) continue; - if (v.y() < 0 || out.height() <= v.y()) continue; - out.pixel(v.y(), v.x(), RGBf_Space(Vector3D<double>(0.0, 0.0, 1.0 * (Z - z) / Z))); - } - } - } - } - writeBitmap(stringPrintf("%s%d.jpg", out_pre.c_str(), ct), out); - printf("write to bmp '%s%d.jpg'\n", out_pre.c_str(), ct); - ct++; - } - } -} - -void clear(Job *job) { - delete job; -} - -void info0(Job* job) { -} - -void info1(Job* job) { -} - -void info2(Job* job) { -} diff --git a/meowpp.test/src/match_MatchAll.cpp b/meowpp.test/src/match_MatchAll.cpp deleted file mode 100644 index 062c1e5..0000000 --- a/meowpp.test/src/match_MatchAll.cpp +++ /dev/null @@ -1,66 +0,0 @@ -#include "match.h" - -#include "meowpp/gra/FeaturePointsMatch_K_Match.h" -#include "meowpp/Usage.h" -#include "meowpp/oo/ObjSelector.h" - -#include <string> -#include <vector> - -using namespace meow; -using namespace std; - - -class MatchAll_K_Match: public MatchAll { -private: - FeaturePointsMatch_K_Match<double, double, FeaturePoint<double, double, Vector2D<double> > > match_; -public: - vector<PairToPair<size_t> > match(std::vector<std::vector<FP> > const& fpss) const { - int des = 0; - bool ok = false; - for (size_t i = 0; !ok && i < fpss.size(); ++i) - for (size_t j = 0; !ok && j < fpss[i].size(); ++j) { - des = fpss[0][0].description().dimension(); - ok = true; - } - /* - vector<PairToPair<size_t> > normal = match_.match(des, fpss); - ((MatchAll_K_Match*)this)->match_.paramK(match_.paramK() * 2); - vector<PairToPair<size_t> > large = match_.match(des, fpss); - for (size_t i = 0, I = normal.size(); i < I; ++i) { - bool found = false; - for (size_t j = 0, J = large.size(); j < J && !found; ++j) { - if (normal[i] == large[j]) { - found = true; - } - } - if (!found) { - printf("!!!!!!!!!!!!\n"); - } - } - // */ - return match_.match(des, fpss); - } - string description() const { - return string("k nearest match"); - } - Usage usage() const { - Usage tmp; - tmp.optionAdd("kmatch-k", - "...", - "number", - stringPrintf("%d", match_.paramK()), - false); - return tmp; - } - bool usage(Usage const& usg) { - int k = atoi(usg.optionValue("kmatch-k", 0).c_str()); - match_.paramK(k); - return true; - } - ObjBase* create() const { - return new MatchAll_K_Match; - } -}; - -static ObjSelector<kMatchAll_ID> __("kmatch", new MatchAll_K_Match, true); diff --git a/meowpp.test/src/match_MatchChk.cpp b/meowpp.test/src/match_MatchChk.cpp deleted file mode 100644 index 6b8239c..0000000 --- a/meowpp.test/src/match_MatchChk.cpp +++ /dev/null @@ -1,102 +0,0 @@ -#include "match.h" -#include "meowpp/oo/ObjSelector.h" - -using namespace meow; -using namespace std; - - -class MatchChk_Prob: public MatchChk { -private: - double p1_, p0_, pmin_; -public: - MatchChk_Prob(): p1_(0.7), p0_(0.01), pmin_(0.97) { - } - bool check(vector<Vector2D<double> > const& fps1, - size_t w1, - size_t h1, - vector<Vector2D<double> > const& fps2, - size_t w2, - size_t h2, - vector<Pair > const& pairs, - MatchInfo const& info) { - double m_ni = log(p1_ * (1 - p0_)) - log(p0_ * (1 - p1_)); - double c = log(pmin_) - log(1 - pmin_); - double m_nf = log(1 - p0_) - log(1 - p1_); - // ni * ?? > c + nf * ?? - double ni = info.pairs.size(); - double nf = 0; - for (size_t i = 0; i < fps1.size(); ++i) { - Vector2D<double> v( - (fps1[i].dot(info.x_axis) + info.x_offset) / (fps1[i].dot(info.depth) + 1), - (fps1[i].dot(info.y_axis) + info.y_offset) / (fps1[i].dot(info.depth) + 1) - ); - if (0 <= v.x() && v.x() < w2 && 0 <= v.y() && v.y() < h2) { - ++nf; - } - } - //printf("nf = %f, ni = %f\n", nf, ni); - return (ni * m_ni > c + nf * m_nf); - } - string description() const { - return string("prob module"); - } - Usage usage() const { - Usage tmp; - tmp.optionAdd("prob-p1", - "p1", - "floating number", - stringPrintf("%.3f", p1_), - false); - tmp.optionAdd("prob-p0", - "p0", - "floating number", - stringPrintf("%.3f", p0_), - false); - tmp.optionAdd("prob-pmin", - "pmin", - "floating number", - stringPrintf("%.3f", pmin_), - false); - return tmp; - } - bool usage(Usage const& usg) { - p1_ = inRange(0.00001, 0.99999, atof(usg.optionValue("prob-p1" , 0).c_str())); - p0_ = inRange(0.00001, 0.99999, atof(usg.optionValue("prob-p0" , 0).c_str())); - pmin_ = inRange(0.00001, 0.99999, atof(usg.optionValue("prob-pmin", 0).c_str())); - return true; - } - ObjBase* create() const { - return new MatchChk_Prob(); - } -}; - -static ObjSelector<kMatchChk_ID> __("prob-module", new MatchChk_Prob, true); - -class MatchChk_Nothing: public MatchChk { -private: -public: - bool check(vector<Vector2D<double> > const& fps1, - size_t w1, - size_t h1, - vector<Vector2D<double> > const& fps2, - size_t w2, - size_t h2, - vector<Pair > const& pairs, - MatchInfo const& info) { - return true; - } - string description() const { - return string("always true"); - } - Usage usage() const { - return Usage(""); - } - bool usage(Usage const& usg) { - return true; - } - ObjBase* create() const { - return new MatchChk_Nothing(); - } -}; - -static ObjSelector<kMatchChk_ID> ___("nothing", new MatchChk_Nothing, true); diff --git a/meowpp.test/src/match_MatchOne.cpp b/meowpp.test/src/match_MatchOne.cpp deleted file mode 100644 index 1ce7bf3..0000000 --- a/meowpp.test/src/match_MatchOne.cpp +++ /dev/null @@ -1,207 +0,0 @@ -#include "match.h" -#include <cmath> -#include <algorithm> -#include "meowpp/oo/ObjSelector.h" -#include <vector> -#include "meowpp/math/methods.h" -#include <utility> - -using namespace meow; -using namespace std; - -inline Vector<double> calc8(vector<pair<Vector2D<double>, Vector2D<double> > > const& p) { - Matrix<double> m(p.size() * 2, 8, 0.0), b(8, 1, 0.0); - for (size_t i = 0; i < p.size(); ++i) { - m.entry(i * 2 + 0, 0, p[i].first.x()); - m.entry(i * 2 + 0, 1, p[i].first.y()); - m.entry(i * 2 + 0, 2, 1); - m.entry(i * 2 + 0, 6, -p[i].first.x() * p[i].second.x()); - m.entry(i * 2 + 0, 7, -p[i].first.y() * p[i].second.x()); - m.entry(i * 2 + 1, 3, p[i].first.x()); - m.entry(i * 2 + 1, 4, p[i].first.y()); - m.entry(i * 2 + 1, 5, 1); - m.entry(i * 2 + 1, 6, -p[i].first.x() * p[i].second.y()); - m.entry(i * 2 + 1, 7, -p[i].first.y() * p[i].second.y()); - b.entry(i * 2 + 0, 0, p[i].second.x()); - b.entry(i * 2 + 1, 0, p[i].second.y()); - } - if (p.size() == 4) { - /* - Vector<double> x = m.inverse() * b; - if (x.dimension() == 8) { - bool ok = true; - printf("size = %d\n", (int)x.dimension()); - for (size_t i = 0; i < p.size(); ++i) { - double a = x(0) * p[i].first.x() + x(1) * p[i].first.y() + x(2) - x(6) * p[i].first.x() * p[i].second.x() - x(7) * p[i].first.y() * p[i].second.x() - p[i].second.x(); - double b = x(3) * p[i].first.x() + x(4) * p[i].first.y() + x(5) - x(6) * p[i].first.x() * p[i].second.y() - x(7) * p[i].first.y() * p[i].second.y() - p[i].second.y(); - printf("ab = %f, %f\n", a, b); - if (fabs(a) > 10 || fabs(b) > 10) ok = false; - } - if (!ok) { - for (size_t i = 0; i < p.size(); ++i) { - printf("<%10.3f, %10.3f> ---> <%10.3f, %10.3f>\n", p[i].first.x(), p[i].first.y(), p[i].second.x(), p[i].second.y()); - } - getchar(); - } - } - // */ - return Vector<double>(m.inverse() * b); - } - else { - return Vector<double>((m.transpose() * m).inverse() * m.transpose() * b); - } -} - -inline vector<Pair> goodPair(vector<Vector2D<double> > const& from, - vector<Vector2D<double> > const& to, - vector<Pair> const& pairs, - Vector<double> const& v, - double t) { - vector<Pair> ret; - for (size_t i = 0; i < pairs.size(); ++i) { - Vector2D<double> v1 = from[pairs[i].first ]; - Vector2D<double> v2 = to [pairs[i].second]; - Vector2D<double> v12( - (v1.x() * v(0) + v1.y() * v(1) + v(2)) / (v1.x() * v(6) + v1.y() * v(7) + 1), - (v1.x() * v(3) + v1.y() * v(4) + v(5)) / (v1.x() * v(6) + v1.y() * v(7) + 1) - ); - if ((v12 - v2).length() <= t) { - ret.push_back(pairs[i]); - } - } - return ret; -} - - -class MatchOne_RANSAC: public MatchOne { -private: - double P_, p0_, t_; - double rat_, ang_; - - class Controller { - vector<Vector2D<double> > v1_; - vector<Vector2D<double> > v2_; - double t_, rat_, ang_; - double x_max_, y_max_; - bool check(Vector<double> const& v) const { - Vector2D<double> vx((double)v(0), v(1)); - Vector2D<double> vy((double)v(3), v(4)); - Vector2D<double> d ((double)v(6), v(7)); - double l1 = vx.length() * rat_, l2 = vx.length() / rat_; - if (vy.length() < min(l1, l2) ) return false; - if ( max(l1, l2) < vy.length()) return false; - double ang = acos(vx.dot(vy) / vx.length() / vy.length()); - if (ang < PI * 0.5 - ang_ || PI * 0.5 + ang_ < ang) return false; - if (d.x() * 0 + d.y() * 0 + 1 <= 0) return false; - if (d.x() * x_max_ + d.y() * 0 + 1 <= 0) return false; - if (d.x() * 0 + d.y() * y_max_ + 1 <= 0) return false; - if (d.x() * x_max_ + d.y() * y_max_ + 1 <= 0) return false; - return true; - } - public: - Controller(vector<Vector2D<double> > const& fps1, - vector<Vector2D<double> > const& fps2, - double threshold, - double rat, double ang, double xmax, double ymax): - v1_(fps1), v2_(fps2), t_(threshold), rat_(rat), ang_(fabs(ang)), x_max_(xmax), y_max_(ymax) { - } - double operator()(vector<Pair> const& p, vector<Pair> const& pairs) const { - vector<pair<Vector2D<double>, Vector2D<double> > > ps; - for (size_t i = 0; i < p.size(); ++i) - for (size_t j = 0; j < p.size(); ++j) - if (i != j && (v1_[p[i].first ] == v1_[p[j].first ] || - v2_[p[i].second] == v2_[p[j].second])) - return -1.0; - for (size_t i = 0; i < p.size(); ++i) { - ps.push_back(pair<Vector2D<double>, Vector2D<double> >(v1_[p[i].first], v2_[p[i].second])); - } - Vector<double> v = calc8(ps); - if (v.valid() == false || check(v) == false) return -1; - return 0.1 + (double)goodPair(v1_, v2_, pairs, v, t_).size(); - } - }; -public: - MatchOne_RANSAC(): P_(0.99), p0_(0.05), t_(5), rat_(0.8), ang_(PI / 2 / 8) { - } - MatchInfo match(vector<Vector2D<double> > const& fps1, - vector<Vector2D<double> > const& fps2, - vector<Pair> const& pairs, - size_t width, size_t height) const { - MatchInfo ret; - if ((int)pairs.size() < minNumber()) { - ret.ok = false; - } - else { - ret.pairs = ransac(pairs, Controller(fps1, fps2, t_, rat_, ang_, width, height), minNumber(), p0_, P_); - if ((int)ret.pairs.size() < minNumber()) { - ret.ok = false; - } - else { - vector<pair<Vector2D<double>, Vector2D<double> > > ps; - for (size_t i = 0; i <ret.pairs.size(); ++i) { - ps.push_back(pair<Vector2D<double>, Vector2D<double> >(fps1[ret.pairs[i].first], fps2[ret.pairs[i].second])); - } - Vector<double> v = calc8(ps); - ret.ok = true; - ret.pairs = goodPair(fps1, fps2, pairs, v, t_); - ret.x_axis.x(v(0)); - ret.x_axis.y(v(1)); - ret.x_offset = v(2); - ret.y_axis.x(v(3)); - ret.y_axis.y(v(4)); - ret.y_offset = v(5); - ret.depth.x(v(6)); - ret.depth.y(v(7)); - } - } - return ret; - } - string description() const { - return string("ransac with eight parameter"); - } - Usage usage() const { - Usage tmp; - tmp.optionAdd("ransac-P", - "prob what I want", - "floating number", - stringPrintf("%.2f", P_), - false); - tmp.optionAdd("ransac-p0", - "prob each time", - "floating number", - stringPrintf("%.2f", p0_), - false); - tmp.optionAdd("ransac-t", - "threshold t", - "floating number", - stringPrintf("%.2f", t_), - false); - tmp.optionAdd("ransac-ratio", - "ratio", - "floating number", - stringPrintf("%.2f", rat_), - false); - tmp.optionAdd("ransac-angle", - "angle", - "floating number", - stringPrintf("%.2f", ang_), - false); - return tmp; - } - bool usage(Usage const& usg) { - P_ = inRange(0.00001, 0.99999, atof(usg.optionValue("ransac-P" , 0).c_str())); - p0_ = inRange(0.00001, 0.99999, atof(usg.optionValue("ransac-p0", 0).c_str())); - t_ = inRange(0.00001, 0.99999, atof(usg.optionValue("ransac-t" , 0).c_str())); - rat_ = inRange(0.00001, 0.99999, atof(usg.optionValue("ransac-ratio", 0).c_str())); - ang_ = inRange(0.00001, 0.99999, atof(usg.optionValue("ransac-angle", 0).c_str())); - return true; - } - int minNumber() const { - return 4; - } - ObjBase* create() const { - return new MatchOne_RANSAC; - } -}; - -static ObjSelector<kMatchOne_ID> __("ransac8", new MatchOne_RANSAC, true); diff --git a/meowpp.test/src/match_MatchOne.h b/meowpp.test/src/match_MatchOne.h deleted file mode 100644 index 9613fa5..0000000 --- a/meowpp.test/src/match_MatchOne.h +++ /dev/null @@ -1,45 +0,0 @@ -#include "match.h" -#include "oo/ObjSelector.h" - -using namespace meow; -using namespace std; - - -class MatchOne_RANSAC: public MatchOne { -private: - double P_, p0_; -public: - MatchOne_RANSAC(): P_(0.99), p0_(0.05) { - } - MatchInfo match(std::vector<meow::Vector2D<double> > const& fps1, - std::vector<meow::Vector2D<double> > const& fps2, - std::vector<std::pair<size_t, size_t> > const& pairs) { - vector<Pair> p = - } - string description() const { - return string("ransac with eight parameter"); - } - Usage usage() const { - Usage tmp; - tmp.optionAdd("ransac-P", - "prob what I want", - "floating number", - stringPrintf("%.2f", P_), - false); - tmp.optionAdd("ransac-p0", - "prob each time", - "floating number", - stringPrintf("%.2f", p0_), - false); - } - bool usage(Usage const& usg) { - P_ = inRange(0.00001, 0.99999, atof(tmp.optionValue("ransac-P" , 0).c_str())); - p0_ = inRange(0.00001, 0.99999, atof(tmp.optionValue("ransac-p0", 0).c_str())); - return true; - } - int minNumber() const { - return 4; - } -}; - -static ObjSelector<kMatchOne_ID> __("ransac8", new MatchOne_RANSAC, true); diff --git a/meowpp.test/src/oo.cpp b/meowpp.test/src/oo.cpp deleted file mode 100644 index ede8a24..0000000 --- a/meowpp.test/src/oo.cpp +++ /dev/null @@ -1,98 +0,0 @@ -#include <cstdio> - -#include "meowpp/Self.h" -#include <vector> -#include <string> -#include <algorithm> - -#include <ctime> -#include <cmath> - -using namespace meow; - -class A { -private: - struct Myself{ - int n; - Myself() { } - Myself(Myself const& m): n(m.n) { - } - ~Myself() { } - }; - Self<Myself> const self; -public: - A(): self(){ self()->n = 0; } - A(A const& b): self(b.self, Self<Myself>::COPY_FROM) { } - ~A() { } - int num() const { return self->n; } - int num(int k) { return (self()->n = k); } - void copyFrom(A const& v) { self().copyFrom(v.self); } - void referenceFrom(A const& v) { self().referenceFrom(v.self); } -}; - -struct B { - int n; - int count; - B() { n = 0; count = 1; } -}; - -static const size_t N = 50; - -static A as[N]; -static B *bs[N]; - -int main(){ - srand(time(0)); - for (size_t i = 0; i < N; i++) { - bs[i] = new B; - } - for (size_t i = 0; i < 500; i++) { - int k = rand(); - if (k % 3 == 0) { // copyFrom - int x, y; - do { - x = rand() % N; - y = rand() % N; - } while(x == y); - as[x].copyFrom(as[y]); - bs[x]->n = bs[y]->n; - } - else if (k % 3 == 1) { // referenceFrom - int x, y; - do { - x = rand() % N; - y = rand() % N; - } while(x == y || x / (N / 5) != y / (N / 5)); - as[x].referenceFrom(as[y]); - bs[x]->count--; - if (bs[x]->count == 0) { - delete bs[x]; - } - bs[x] = bs[y]; - bs[x]->count++; - } - else { // set value - int x = rand() % N, v = rand() % 100; - as[x].num(v); - bs[x]->n = v; - } - bool chk = true; - for (size_t n = 0; n < N; n++) { - if (as[n].num() != bs[n]->n) { - chk = false; - break; - } - } - if (!chk) { - printf("false!\n"); - return 1; - } - //for (size_t j = 0; j < N; j++) { printf("%d ", as[j].num()); } printf("\n"); - } - for (size_t i = 0; i < N; i++) { printf("%d ", as[i].num()); } - printf("\n"); - for (size_t i = 0; i < N; i++) { printf("%d ", bs[i]->n); } - printf("\n"); - printf("true\n"); - return 0; -} diff --git a/meowpp.test/src/rot_bundle.cpp b/meowpp.test/src/rot_bundle.cpp deleted file mode 100644 index 775c573..0000000 --- a/meowpp.test/src/rot_bundle.cpp +++ /dev/null @@ -1,199 +0,0 @@ -#include <cstdio> -#include <string> -#include <cstdlib> -#include <algorithm> -#include <vector> - -#include <opencv/cv.h> -#include <opencv/highgui.h> - -#include "meowpp/dsa/DisjointSet.h" -#include "meowpp/Usage.h" -#include "meowpp/gra/Eye.h" -#include "meowpp/colors/RGB_Space.h" -#include "meowpp/gra/Bitmap.h" -#include "meowpp/utility.h" -#include "meowpp/math/utility.h" -#include "meowpp/geo/Vectors.h" -#include "meowpp/gra/WatchBall.h" - -#include "meowpp/gra/BundleAdjustment_LM.h" - -using namespace meow; - -////////////////////////////////////////////////////////////////// - -Usage usg("rot_bundle"); - -std::vector<std::string > names; -std::vector<Eye<RGBf_Space> > eyes; - -double f_init = 300; -double threshold = 5; -double r = 1000; - -////////////////////////////////////////////////////////////////// - -bool setup(int argc, char** argv) { - usg.optionAdd("f", - "Input text file", - "filename", - "", - true); - usg.optionAdd("h", - "help docu"); - usg.optionAdd("output-radius", - "...", - "floating point", - stringPrintf("%f", r), - false); - usg.optionAdd("o", - "prefix of output images", - "pathname", - "output", - false); - usg.optionAdd("f-init", - "init focal length", - "floating point", - stringPrintf("%f", f_init), - false); - usg.optionAdd("t", - "threshold for bundle adjustment", - "floating point", - stringPrintf("%f", threshold), - false); - std::string s; - bool ok = usg.arguments(argc, argv, &s); - if (usg.hasOptionSetup("h")) { - printf("%s\n", usg.usage().c_str()); - exit(0); - } - if (!ok) { - fprintf(stderr, "%s\n", s.c_str()); - exit(1); - } - return true; -} - -void fmtError(FILE* f) { - fclose(f); - fprintf(stderr, "\nFromat error!\n"); - exit(-1); -} - -bool read() { - messagePrintf(1, "read file"); - FILE* f = fopen(usg.optionValue("f", 0).c_str(), "r"); - size_t N; - if (fscanf(f, "%lu", &N) < 1) fmtError(f); - names[i].resize(N); - for (size_t i = 0; i < N; ++i) { - char s[1000]; - if (fscanf(f, "%s", s) < 1) fmtError(f); - names[i] = s; - } - eyes.resize(N); - size_t M; - if (fscanf(f, "%lu", &M) < 1) fmtError(f); - for (size_t i = 0; i < M; ++M) { - int a, b; - double x1, y1, x2, y2; - if (fscanf(f, "%d %lf %lf %d %lf %lf", &a, &x1, &y1, &b, &x2, &y2) < 6) fmtError(f); - eyes[a].cameraGet().fixedPoints2DGet().pointAdd(i, Vector2D(x1, y1).matrix()); - eyes[b].cameraGet().fixedPoints2DGet().pointAdd(i, Vector2D(x2, y2).matrix()); - } - fclose(f); - messagePrintf(-1, "ok"); -} - -bool bundle() { - messagePrintf(1, "boundle adjustment"); - threshold = inRange(0.0005, 1000.0, atof(usg.optionValue("t" , 0).c_str())); - f_init = inRange(0.0005, 100000.0, atof(usg.optionValue("f-init", 0).c_str())); - BundleAdjustment_LM<RGBf_Space> bdl; - bdl.threshold(threshold); - std::vector<SceneInfo<RGBf_Space> > seq; - for (size_t i = 0, I = eyes.size(); i < I; ++i) { - eyes[i].cameraGet().photoGet().focal(f_init); - seq.push_back(SceneInfo<RGBf_Space>(eyes[i], CAN_ROTATE | CAN_ZOOM)); - } - bdl.adjustEyes(&seq); - messagePrintf(-1, "ok"); - return true; -} - -bool output() { - r = inRange(10.0, 100000.0, atof(usg.optionValue("output-radius", 0).c_str())); - Bitmap<RGBf_Space> output; - Bitmap<double> alpha; - for (size_t i = 0, I = eyes.size(); i < I; ++i) { - messagePrintf(1, "load image"); - cv::Mat img = cv::imread(names[i], CV_LOAD_IMAGE_COLOR); - if (!img.data) { - messagePrintf(-1, "opencv read error!, ignore"); - continue; - } - size_t width = img.size().width ; - size_t height = img.size().height; - Bitmap<RGBf_Space> bmp; - bmp.size(height, width, RGBf_Space(0)); - for (size_t x = 0; x < width; x++) { - for (size_t y = 0; y < height; y++) { - RGBi_Space tmp(Vector3D<int>( - img.at<cv::Vec3b>(y, x)[2], - img.at<cv::Vec3b>(y, x)[1], - img.at<cv::Vec3b>(y, x)[0])); - RGBf_Space p; - colorTransformate(tmp, &p); - bmp.pixel(y, x, p); - } - } - eyes[i].cameraGet().photoGet().bitmap(bmp); - WatchBall<RGBf_Space> ball; - ball.cameras(std::vector<Camera<RGBf_Space> >(1, eyes[i].camera())); - std::pair<Bitmap<RGBf_Space>, Bitmap<double> > p = ball.expandAlpha(r); - if (output.size() == 0) { - output = p.first; - alpha = p.second; - } - else { - output.matrix(output.matrix() + p.first .matrix()); - alpha .matrix(alpha .matrix() + p.second.matrix()); - } - } - for (size_t y = 0, Y = output.height(); y < Y; ++y) - for (size_t x = 0, X = output.width(); x < X; ++x) - if (noEPS(alpha.pixel(y, x)) > 0) - output.pixel(y, x, output.pixel(y, x) / alpha.pixel(y, x)); - messagePrintf(1, "Write images"); - cv::Mat img(height, width, CV_8UC3); - for (size_t x = 0; x < width; x++) { - for (size_t y = 0; y < height; y++) { - RGBi_Space tmp; - colorTransformate(output.pixel(y, x), &tmp); - img.at<cv::Vec3b>(y, x)[0] = tmp.b(); - img.at<cv::Vec3b>(y, x)[1] = tmp.g(); - img.at<cv::Vec3b>(y, x)[2] = tmp.r(); - } - } - std::string output_name(usg.optionValue("o", 0) + ".jpg"); - messagePrintf(1, "Write to file '%s'", output_name.c_str()); - if (imwrite(output_name, img) == false) { - messagePrintf(-1, "opencv fail, ignore"); - } - else { - messagePrintf(-1, "%lux%lu, ok", width, height); - } - messagePrintf(-1, "ok"); - return true; -} - -int main(int argc, char** argv) { - setup(argc, argv); - read(); - bundle(); - input(); - output(); - return 0; -} - |