4 * Created on: May 3, 2014
5 * Author: caceres@creatis.insa-lyon.fr
8 #ifndef _AIRWAYS_TREE_H_
9 #define _AIRWAYS_TREE_H_
11 #include "airwaysTreeTypeDefinition.h"
14 #include <vtkVersion.h>
15 #include <vtkSmartPointer.h>
16 #include <vtkCellArray.h>
17 #include <vtkCellData.h>
19 #include <vtkPolyDataMapper.h>
20 #include <vtkRenderWindow.h>
21 #include <vtkRenderer.h>
22 #include <vtkRenderWindowInteractor.h>
23 #include <vtkPolyDataWriter.h>
24 #include <vtkSphereSource.h>
28 #include "itkImageRegionIterator.h"
29 #include "itkLineIterator.h"
30 #include <itkImageFileWriter.h>
31 #include <appli/TempAirwaysAppli/AirwaysLib/AirwaysLib_Export.h>
39 typedef std::vector<Node*> vec_nodes;
42 typedef std::pair<Node*, Node*> pair_nodes;
44 //Pair of a pair of nodes and a score
45 typedef std::pair<pair_nodes,double> Pair_PairNodes_Score;
50 //typedef std::pair<pair_nodes,double> Pair_PairNodes_Score;
53 * Vector of pairs of a pair of nodes and a score
55 typedef std::vector<Pair_PairNodes_Score> Vector_Pair_PairNodes_Score;
58 * A vector stocking all the points between two nodes
60 typedef std::vector<pair_posVox_rad> vec_pair_posVox_rad;
62 class AirwaysLib_EXPORT AirwaysTree
68 AirwaysTree(TInputImage::Pointer img, TInputImage::Pointer img_sk, Node* root);
70 AirwaysTree(TInputImage::Pointer image_airwaySegmentation, TInputImage::Pointer image_skeletonDM, EdgeVector& vector_edges, Edge* edge_trachea);
74 // New constructor that doesn't update path info between nodes.
75 AirwaysTree(TInputImage::Pointer image, TInputImage::Pointer image_skeleton, Node* root, bool shouldUpdate);
76 virtual ~AirwaysTree();
82 Node* GetRoot() const;
84 std::string GetImageName() const;
86 std::string GetResultPath() const;
88 TInputImage::Pointer GetSegmentedImage() const;
90 TInputImage::Pointer GetSkeletonImage() const;
92 const Node* GetNode(const Vec3 nodeCoords) const;
95 * Method that return the node with the specified id
96 * @param nId is id of the requested node
97 * @return the requested id, NULL if not found
99 Node* GetNodeById(unsigned int nId);
102 * Method that returns the depth of the node whose id is given by parameter
103 * @pre the node exist in the sub-tree
104 * @param idNode is the search node id
105 * @return the depth of the node up to the actual node
107 int GetDepthById(unsigned int nId);
109 unsigned int CountMarkedNodes(Node* current = NULL) const;
112 * Method that returns the weight of the tree
113 * @return the weight of the tree which is the number of nodes in the tree.
115 unsigned int GetWeight( ) const;
117 unsigned int GetHeight(Node* current = NULL) const;
119 unsigned int GetLevels(Node* current = NULL, unsigned int cLevel = 0) const;
122 * Method that returns the number of leafs in the tree
123 * @return the number of leafs in the tree
125 unsigned int GetNumberOfLeafs() const;
127 const EdgeVector& GetEdges() const;
129 const vec_nodes& GetNodes() const;
132 * Method that returns the closest node of a given voxel.
133 * The closes node is the one whose path to the father has the closest point to the given point
134 * in real coordinates of the image.
135 * @param voxel_x x componente of the voxel
136 * @param voxel_y y componente of the voxel
137 * @param voxel_z z componente of the voxel
138 * @return the closest node to the given voxel
140 const Node* GetClosestBrachNodeToIndex(float point_x, float point_y, float point_z) const;
143 * Method that returns the list of nodes that influence the given point
144 * @param point_x, point_y, point_z are the position of the point in real coordinates x, y, and z respectively.
145 * @param vec_nodes_influence vector to save the nodes
147 void GetBrancheNodesInfluencingPoint(float point_x, float point_y, float point_z, vec_nodes& vec_nodes_influence);
149 AirwaysTree& GetTreeFromMarkedNodes(Node* currentNode = NULL, AirwaysTree* tree = NULL);
151 AirwaysTree& GetSubTreeFromNode(Node* node, AirwaysTree* tree = NULL);
153 AirwaysTree& GetSubTreeByLevels(const int& level, Node* node = NULL, AirwaysTree* tree = NULL);
155 AirwaysTree& GetSubTreeByLength(const double& length, Node* node = NULL, AirwaysTree* tree = NULL, double cLenght = 0.0);
157 AirwaysTree& GetSubTreeByRadius(const double& radius, Node* node = NULL, AirwaysTree* tree = NULL, double cRadius = 0.0);
159 void MarkLevels(const int& level, Node* currentNode = NULL);
161 bool IsEmpty() const;
164 * Method that search a node inside a path. The path is defined by the starting and ending nodes
165 * @param idNode_starting is the id of the starting node
166 * @param idNode_ending is the id of the ending node
167 * @param idNode_searched is the of the searched node
168 * @return true if the searched node is inside the path, false otherwise
170 bool IsNodeInsidePath(unsigned int idNode_starting, unsigned int idNode_ending, unsigned int idNode_searched);
172 void SetRoot(Node* root);
174 void SetImageName(const std::string& img_name);
176 void SetResultPath(const std::string& folderPath);
178 bool Insert(Edge* edge);
180 void UnMarkAll(Node* currentNode = NULL);
183 * Method that compares two tree starting from the root node.
184 * @param treeB is the tree to be compared with
185 * @param Q is the depth to select "fathers" nodes
186 * @param F is the depth to select "family" nodes
187 * @param commonA vector to save the common nodes for this subtree
188 * @param commonA vector to save the common nodes for the subtree given by parameter
189 * @param nonCommonA vector to save the non-common nodes for this subtree
190 * @param nonCommonB vector to save the non-common nodes for the subtree given by parameter
192 void CompareTreesOrkiszMorales(AirwaysTree& treeB, unsigned int Q, unsigned int F, vec_nodes& commonA, vec_nodes& commonB, vec_nodes& nonCommonA, vec_nodes& nonCommonB, std::map< unsigned int, std::vector<Node*> >& map_A_to_B, std::map< unsigned int, std::vector<Node*> >& map_B_to_A, std::vector< std::pair< std::pair<Node*, Node*>, std::pair<Node*, Node*> > >& vector_pair_edges_A_to_B);
194 void MarkPathFromNodeToNode(Node* node_begin, Node* node_end);
197 * Method that compares the actual tree with another given by parameter
198 * @param treeB the tree to be compared with
200 void CompareTrees(AirwaysTree& treeB);
203 * Method that finds the pair, at least one is a leaf, with the lowest score
204 * @param vectorPairNodesScore is the vector of pairs
205 * @return the pair, at least one is a leaf, with the lowest score
207 Pair_PairNodes_Score GetBestLeaf(Vector_Pair_PairNodes_Score vectorPairNodesScore);
210 * Method that returns the pair of pair nodes and score for the given ids.
211 * @param vectorPairNodesScore vector of pair nodes and score
212 * @param idA is the first id if the pair nodes
213 * @param idB is the second id if the pair nodes
214 * @return the score for the given pair.
216 double GetPairNodes_Score(Vector_Pair_PairNodes_Score vectorPairNodesScore, const unsigned int idA, const unsigned int idB);
219 * Method that returns a copy of the tree
220 * @return the copy of this tree
222 AirwaysTree* GetCopy();
225 * Method that deleted a node, all his children, from the tree
226 * @return true if the node was deleted (found), false otherwise
228 bool DeleteNodeById(unsigned int nId);
231 * Method that removes all the pairs that contains the a given id is a given component position.
232 * @param vectorPairNodesScore the vector of pair nodes and score
233 * @param component is the component position to be analyzed
234 * @param nId is the searched id
235 * @return the number of deleted pairs
237 unsigned int DeleteEntriesByIdNode(Vector_Pair_PairNodes_Score& vectorPairNodesScore, unsigned int component, unsigned int nId);
240 * Method that compares all the actual branches to all branches in the tree given by parameter
241 * @param treeB in the tree to be compared with
243 Vector_Pair_PairNodes_Score CompareAllBranches(AirwaysTree& treeB);
246 * Method that return the composed edge from the root node to the node whose id is given by parameter
247 * @param idNode is the id of the node where the complex edge ends.
249 Edge* GetComposedEdge(unsigned int idNode);
252 * Method that detaches a node and return a tree with a root and just the detaches node
253 * @param nId is the id node to be searched
254 * @return a tree with a root and just the detaches node
256 AirwaysTree* GetSingleDetachedTreeNodeById(unsigned int nId);
258 void UpdateLevels(unsigned int levels = 0);
260 void SubIsomorphism(AirwaysTree& treeB);
262 bool Isomorphism(AirwaysTree& tree);
264 void ImageReconstructionFromNode(TInputImage::Pointer& result, Node* node, bool skeleton = false);
266 void ImageReconstruction(TInputImage::Pointer& result, bool skeleton = false, Node* node = NULL);
268 void ImageReconstructionBySpheres(TInputImage::Pointer& result, Node* node = NULL, bool useMarks = false);
272 * Method that prints the airway up to a given level
273 * @level is the level where the printing stops
275 void printUpToLevel(int level);
277 void printNodeAndChildrenIds();
280 * Method that creates the quaternions of the airways up to a given level
281 * @level is the level where the creation stops.
284 void createQuaternionsUpToLevel(int level);
287 * Method that prints the statistics of number of bifurcations in each node
289 void getStatisticsBifurcations();
291 void saveAirwayAsVTK(const std::string filename, bool common = false);
294 * Method that save the airways in a image
295 * @param filename is the name of the image to be saved
296 * @param dims is the image dimensions
297 * @param spacing is the image spacing
298 * @param origin is the image origin
300 void saveAirwayToImage(std::string filename, int dims[3], double spc[3], double origin[3]);
303 * Method that draws a line in an image
304 * @initVoxel is the initial voxel
305 * @endVoxel is the final voxel
306 * @imagePointer is the image pointer
308 void drawLineInImage(Vec3 initVoxel, Vec3 endVoxel, TInputImage::Pointer imagePointer);
310 void drawLine(int* pixelPointInit, int* pixelPointEnd, TInputImage::Pointer _imagePointer);
315 Node* GetNode(const Vec3 nodeCoords, Node* current = NULL);
317 Node* GetLeaf(Node* current = NULL);
319 void UpdateEdges(Node* node = NULL);
321 AirwaysTree& GetSubTreeByDetachingNode(Node* node);
324 * Method that adds an edge to the graph given by parameter
325 * @param source is the source vertex of the edge
326 * @param target is the target vertex of the edge
327 * @param graph is the graph to add the new edge
329 DiGraph_EdgePair AddBoostEdge(const pair_posVox_rad& source, const pair_posVox_rad& target, DiGraph& graph);
331 bool FindNeighborhood(DiGraph& graph, Vec3Queue& queue, Vec3List& used, const Vec3& end, ConstNeighborhoodIterator& iterator);
334 * Method that return the shortest* path between two nodes, begin and end. *As we are dealing with arborescent trees
335 * then there is just one path between two nodes!
336 * The path goes from the end to the begin pixel!
337 * @param graph containing all the nodes and edges
338 * @param begin is the starting node
339 * @param end is the ending node
340 * @return the shortest path between the starting and ending nodes or vertices.
342 DiGraph GetGraphShortestPath(const DiGraph& graph, const Vec3& begin, const Vec3& end);
344 vec_pair_posVox_rad GetGraphShortestPath_AMP(const DiGraph& graph, const Vec3& begin, const Vec3& end);
346 vec_pair_posVox_rad GetSkeletonInfoFromEdge(const Vec3& begin, const Vec3& end);
348 bool ComputeSimpleRegionGrowing(TInputImage::Pointer& img, const Vec3 seedPtn);
350 void RemoveBranchFromImage(TInputImage::Pointer& img, Node* node);
352 void CreateSpheres(TInputImage::Pointer& img, Node* node);
354 void CalculateVTKLinesFromEdges(const Node* node, const unsigned int& parentId,
355 unsigned int& cId, vtkSmartPointer<vtkPoints>& pts,
356 vtkSmartPointer<vtkCellArray>& lines,
357 vtkSmartPointer<vtkUnsignedCharArray>& colors, bool common);
358 void FillTree(Node* node);
362 std::string m_img_name;
363 std::string m_result_path;
364 TInputImage::Pointer m_skeleton;
365 TInputImage::Pointer m_img;
370 } /* namespace airways */
372 #endif /* AIRWAYSTREE_H_ */