lib/Airways/AirwaysLib/airwaysTree.h

   1 /*
   2  * airwaysTree.h
   3  *
   4  *  Created on: May 3, 2014
   5  *      Author: caceres@creatis.insa-lyon.fr
   6  */
   7
   8 #ifndef _AIRWAYS_TREE_H_
   9 #define _AIRWAYS_TREE_H_
  10
  11 #include "airwaysTreeTypeDefinition.h"
  12
  13 // VTK
  14 #include <vtkVersion.h>
  15 #include <vtkSmartPointer.h>
  16 #include <vtkCellArray.h>
  17 #include <vtkCellData.h>
  18 #include <vtkLine.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>
  25
  26 // ITK
  27 #include "itkImage.h"
  28 #include "itkImageRegionIterator.h"
  29 #include "itkLineIterator.h"
  30 #include <itkImageFileWriter.h>
  31 #include <Airways/AirwaysLib/TempAirwaysAppli_AirwaysLib_Export.h>
  32
  33 namespace airways
  34 {
  35
  36 // Types
  37
  38 // Vector of nodes
  39 typedef std::vector<Node*> vec_nodes;
  40
  41 // Pair of nodes
  42 typedef std::pair<Node*, Node*> pair_nodes;
  43
  44 //Pair of a pair of nodes and a score
  45 typedef std::pair<pair_nodes,double> Pair_PairNodes_Score;
  46
  47 /**
  48  *
  49  */
  50 //typedef std::pair<pair_nodes,double> Pair_PairNodes_Score;
  51
  52 /**
  53  * Vector of pairs of a pair of nodes and a score
  54  */
  55 typedef std::vector<Pair_PairNodes_Score> Vector_Pair_PairNodes_Score;
  56
  57 /*!
  58  * A vector stocking all the points between two nodes
  59  */
  60 typedef std::vector<pair_posVox_rad> vec_pair_posVox_rad;
  61
  62 class TempAirwaysAppli_AirwaysLib_EXPORT AirwaysTree
  63 {
  64 public:
  65
  66         AirwaysTree();
  67
  68         AirwaysTree(TInputImage::Pointer img, TInputImage::Pointer img_sk, Node* root);
  69
  70         AirwaysTree(TInputImage::Pointer image_airwaySegmentation, TInputImage::Pointer image_skeletonDM, EdgeVector& vector_edges, Edge* edge_trachea);
  71
  72
  73     //CERON
  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();
  77
  78         /**
  79          * Getters
  80          */
  81
  82         Node*   GetRoot() const;
  83
  84         std::string     GetImageName() const;
  85
  86         std::string     GetResultPath() const;
  87
  88         TInputImage::Pointer GetSegmentedImage() const;
  89
  90         TInputImage::Pointer GetSkeletonImage() const;
  91
  92         const Node*     GetNode(const Vec3 nodeCoords) const;
  93
  94         /**
  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
  98          */
  99         Node* GetNodeById(unsigned int nId);
 100
 101         /**
 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
 106          */
 107         int GetDepthById(unsigned int nId);
 108
 109         unsigned int CountMarkedNodes(Node* current = NULL) const;
 110
 111         /**
 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.
 114          */
 115         unsigned int GetWeight( ) const;
 116
 117         unsigned int GetHeight(Node* current = NULL) const;
 118
 119         unsigned int GetLevels(Node* current = NULL, unsigned int cLevel = 0) const;
 120
 121         /**
 122          * Method that returns the number of leafs in the tree
 123          * @return the number of leafs in the tree
 124          */
 125         unsigned int GetNumberOfLeafs() const;
 126
 127         const EdgeVector& GetEdges() const;
 128
 129         const vec_nodes& GetNodes() const;
 130
 131         /**
 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
 139          */
 140         const Node* GetClosestBrachNodeToIndex(float point_x, float point_y, float point_z) const;
 141
 142         /**
 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
 146          */
 147         void GetBrancheNodesInfluencingPoint(float point_x, float point_y, float point_z, vec_nodes& vec_nodes_influence);
 148
 149         AirwaysTree& GetTreeFromMarkedNodes(Node* currentNode = NULL, AirwaysTree* tree = NULL);
 150
 151         AirwaysTree& GetSubTreeFromNode(Node* node, AirwaysTree* tree = NULL);
 152
 153         AirwaysTree& GetSubTreeByLevels(const int& level, Node* node = NULL, AirwaysTree* tree = NULL);
 154
 155         AirwaysTree& GetSubTreeByLength(const double& length, Node* node = NULL, AirwaysTree* tree = NULL, double cLenght = 0.0);
 156
 157         AirwaysTree& GetSubTreeByRadius(const double& radius, Node* node = NULL, AirwaysTree* tree = NULL, double cRadius = 0.0);
 158
 159         void MarkLevels(const int& level, Node* currentNode = NULL);
 160
 161         bool IsEmpty() const;
 162
 163         /**
 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
 169          */
 170         bool IsNodeInsidePath(unsigned int idNode_starting, unsigned int  idNode_ending, unsigned int  idNode_searched);
 171
 172         void SetRoot(Node* root);
 173
 174         void SetImageName(const std::string& img_name);
 175
 176         void SetResultPath(const std::string& folderPath);
 177
 178         bool Insert(Edge* edge);
 179
 180         void UnMarkAll(Node* currentNode = NULL);
 181
 182         /**
 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
 191          */
 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);
 193
 194         void MarkPathFromNodeToNode(Node* node_begin, Node* node_end);
 195
 196         /**
 197          * Method that compares the actual tree with another given by parameter
 198          * @param treeB the tree to be compared with
 199          */
 200         void CompareTrees(AirwaysTree& treeB);
 201
 202         /**
 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
 206          */
 207         Pair_PairNodes_Score GetBestLeaf(Vector_Pair_PairNodes_Score vectorPairNodesScore);
 208
 209         /**
 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.
 215          */
 216         double GetPairNodes_Score(Vector_Pair_PairNodes_Score vectorPairNodesScore, const unsigned int idA, const unsigned int idB);
 217
 218         /**
 219          * Method that returns a copy of the tree
 220          * @return the copy of this tree
 221          */
 222         AirwaysTree* GetCopy();
 223
 224         /**
 225          * Method that deleted a node, all his children, from the tree
 226          * @return true if the node was deleted (found), false otherwise
 227          */
 228         bool DeleteNodeById(unsigned int nId);
 229
 230         /**
 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
 236          */
 237         unsigned int DeleteEntriesByIdNode(Vector_Pair_PairNodes_Score& vectorPairNodesScore, unsigned int component, unsigned int nId);
 238
 239         /**
 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
 242          */
 243         Vector_Pair_PairNodes_Score CompareAllBranches(AirwaysTree& treeB);
 244
 245         /**
 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.
 248          */
 249         Edge* GetComposedEdge(unsigned int idNode);
 250
 251         /**
 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
 255          */
 256         AirwaysTree* GetSingleDetachedTreeNodeById(unsigned int nId);
 257
 258         void UpdateLevels(unsigned int levels = 0);
 259
 260         void SubIsomorphism(AirwaysTree& treeB);
 261
 262         bool Isomorphism(AirwaysTree& tree);
 263
 264         void ImageReconstructionFromNode(TInputImage::Pointer& result, Node* node, bool skeleton = false);
 265
 266         void ImageReconstruction(TInputImage::Pointer& result, bool skeleton = false, Node* node = NULL);
 267
 268         void ImageReconstructionBySpheres(TInputImage::Pointer& result, Node* node = NULL, bool useMarks = false);
 269
 270
 271         /**
 272          * Method that prints the airway up to a given level
 273          * @level is the level where the printing stops
 274          */
 275         void printUpToLevel(int level);
 276
 277         void printNodeAndChildrenIds();
 278
 279         /**
 280          * Method that creates the quaternions of the airways up to a given level
 281          * @level is the level where the creation stops.
 282          * @pre level >= 2
 283          */
 284         void createQuaternionsUpToLevel(int level);
 285
 286         /**
 287          * Method that prints the statistics of number of bifurcations in each node
 288          */
 289         void getStatisticsBifurcations();
 290
 291         void saveAirwayAsVTK(const std::string filename, bool common = false);
 292
 293         /**
 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
 299          */
 300         void saveAirwayToImage(std::string filename, int dims[3], double spc[3], double origin[3]);
 301
 302         /**
 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
 307          */
 308         void drawLineInImage(Vec3 initVoxel, Vec3 endVoxel, TInputImage::Pointer imagePointer);
 309
 310         void drawLine(int* pixelPointInit, int* pixelPointEnd, TInputImage::Pointer _imagePointer);
 311
 312
 313 protected:
 314
 315         Node* GetNode(const Vec3 nodeCoords, Node* current = NULL);
 316
 317         Node* GetLeaf(Node* current = NULL);
 318
 319         void UpdateEdges(Node* node = NULL);
 320
 321         AirwaysTree& GetSubTreeByDetachingNode(Node* node);
 322
 323         /**
 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
 328          */
 329         DiGraph_EdgePair AddBoostEdge(const pair_posVox_rad& source, const pair_posVox_rad& target, DiGraph& graph);
 330
 331         bool FindNeighborhood(DiGraph& graph, Vec3Queue& queue, Vec3List& used, const Vec3& end, ConstNeighborhoodIterator& iterator);
 332
 333         /**
 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.
 341          */
 342         DiGraph GetGraphShortestPath(const DiGraph& graph, const Vec3& begin, const Vec3& end);
 343
 344         vec_pair_posVox_rad GetGraphShortestPath_AMP(const DiGraph& graph, const Vec3& begin, const Vec3& end);
 345
 346         vec_pair_posVox_rad GetSkeletonInfoFromEdge(const Vec3& begin, const Vec3& end);
 347
 348         bool ComputeSimpleRegionGrowing(TInputImage::Pointer& img, const Vec3 seedPtn);
 349
 350         void RemoveBranchFromImage(TInputImage::Pointer& img, Node* node);
 351
 352         void CreateSpheres(TInputImage::Pointer& img, Node* node);
 353
 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);
 359
 360 protected:
 361
 362         std::string m_img_name;
 363         std::string m_result_path;
 364         TInputImage::Pointer m_skeleton;
 365         TInputImage::Pointer m_img;
 366         Node* m_root;
 367         vec_nodes m_nodes;
 368         EdgeVector m_edges;
 369 };
 370 } /* namespace airways */
 371
 372 #endif /* AIRWAYSTREE_H_ */