-
Notifications
You must be signed in to change notification settings - Fork 0
/
component_tree.h
171 lines (143 loc) · 5.44 KB
/
component_tree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
//
//=======================================================================
// Copyright 2010 Institute PICB.
// Authors: Hang Xiao, Axel Mosig
// Data : July 11, 2010
//=======================================================================
//
#ifndef COMPONENT_TREE_H_H
#define COMPONENT_TREE_H_H
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class ComponentTree
{
public:
class Pixel;
class Node;
typedef int Vertex;
typedef vector<Vertex> Vertices;
typedef vector<int> Path;
typedef vector<Path> Paths;
class Pixel
{
public:
Pixel();
bool save(ofstream& ofs, bool saveType = true) const;
bool load(ifstream& ifs, vector<Pixel>& pixels, vector<Node*>& nodes, bool saveType=true);
void merge_entry(Pixel* entry);
public:
int pos;
Pixel * next; // the next pixel
unsigned short level;
Node* node;
};
typedef vector<Node*> Nodes;
class Node
{
public:
Node(){};
bool save(ofstream& ofs, bool saveType=true) const;
bool load(ifstream& ifs, vector<Pixel>& pixels, vector<Node*>& nodes, bool saveType=true);
vector<Pixel*> alpha_pixels();
vector<Pixel*> beta_pixels();
vector<int> alpha_points();
vector<int> beta_points();
void merge_node(Node* node); // node may be a child
Nodes getPostOrderNodes(); //return all the node which stores in post order, equilivalent to m_root
Nodes getPreOrderNodes(); //return all the node which stores in post order, equilivalent to m_root
Nodes getBreadthFirstNodes(); //return all the node which stores in post order, equilivalent to m_root
public:
int label; // the store index in m_nodes, start from 0
int lowest_level; // the lowest level
int highest_alpha_level; // the highest alpha level
int highest_beta_level(); // the highest beta level
double mean_level();
vector<double> center();
int alpha_size; // the pixel in the component exclude the pixels in child nodes
int beta_size; // the total number of pixels
Node* parent; // we will make Node as dynamic memory, for the label is not easy to
Pixel* entry_pixel; // pixel will set static, the entry shoud set as the one of the lowest pixel in this component
vector<Node*> childs;
};
public:
ComponentTree();
ComponentTree(char * imgfile, int _minSize, int _maxSize, int _singleSize);
ComponentTree(char* treefile);
~ComponentTree();
bool create(char * imgfile, int _minSize, int _maxSize, int _singleSize);
bool load(const char* from_tree_file);
bool reload(const char* from_tree_file);
bool load(ifstream& ifs, bool saveType = true);
bool save(const char* to_tree_file) const;
bool save(ofstream& ofs, bool saveType = true) const;
void clear();
int width() const;
int height() const;
int depth() const;
Node* root() const;
Node* getNode(int) const; //node of label
Paths getPaths() const;
int* getReverseAlphaMapping() const; //get the matrix of labels
int* getMatrix(vector<int> labels , vector<int> values, int ini_value) const;
void setWeightMatrix(ComponentTree* tree2, vector<float> &weights);
int nodeNum() const;
int leafNum() const;
int pixelNum() const;
void printTree(int label = -1) const;
void printReverseAlphaMapping() const;
void printPaths() const;
private:
void printTreeRecursively(int , int) const;
private:
int m_width ;
int m_height;
int m_depth;
int m_minSize;
int m_maxSize;
int m_singleSize;
int m_numPixels;
int m_numNodes;
int m_numLeafs;
vector<Pixel> m_pixels;
Nodes m_nodes; //store the nodes in post order
Nodes m_leafs; //store all the leafs
Node* m_root; //the root Node
};
class DisjointSets
{
public:
// Create an empty DisjointSets data structure
DisjointSets();
// Create a DisjointSets data structure with a specified number of pixels (with pixel id's from 0 to count-1)
DisjointSets(int count);
// Copy constructor
DisjointSets(const DisjointSets & s);
// Destructor
~DisjointSets();
// Find the set identifier that an pixel currently belongs to.
// Note: some internal data is modified for optimization even though this method is consant.
int FindSet(int pixel) const;
// Combine two sets into one. All pixels in those two sets will share the same set id that can be gotten using FindSet.
int Union(int setId1, int setId2);
// Add a specified number of pixels to the DisjointSets data structure. The pixel id's of the new pixels are numbered
// consequitively starting with the first never-before-used pixelId.
void AddPixels(int numToAdd);
// Returns the number of pixels currently in the DisjointSets data structure.
int NumPixels() const;
// Returns the number of sets currently in the DisjointSets data structure.
int NumSets() const;
private:
// Internal Node data structure used for representing an pixel
struct Node
{
int rank; // This roughly represent the max height of the node in its subtree
int index; // The index of the pixel the node represents
Node* parent; // The parent node of the node
};
int m_numPixels; // the number of pixels currently in the DisjointSets data structure.
int m_numSets; // the number of sets currently in the DisjointSets data structure.
std::vector<Node*> m_nodes; // the list of nodes representing the pixels
};
#endif