SkelGraph.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Extract Skeleton
  Module:    $HeadURL$
  Language:  C++
  Date:      $Date$
  Version:   $Revision$

  Copyright (c) Brigham and Women's Hospital (BWH) All Rights Reserved.

  See License.txt or http://www.slicer.org/copyright/copyright.txt for details.

==========================================================================*/
#ifndef _SKEL_GRAPH_H_
#define _SKEL_GRAPH_H_

#include <deque>
#include <list>
#include "coordTypes.h"

struct skel_branch
  {
  skel_branch()
  {
    branchID = -1;
    length = 0;
    acc_length = 0;
    max_path_length = 0;
  }
  int branchID;     // == position in m_Graph
  double length; // length between end points
  std::deque<Coord3i> points;

  double acc_length;  // for temporary use when searching maximal path
  std::deque<int> acc_path;

  double max_path_length;
  std::deque<int> max_path;         // maximal path

  Coord3i end_1_point;
  Coord3i end_2_point;
  std::deque<int> end_1_neighbors; // id's == one can use advance for random access
  std::deque<int> end_2_neighbors;
  };

class SkelGraph
{
public:
  SkelGraph();
  virtual ~SkelGraph();

  // Print info on all m_Graph nodes to standard output
  void PrintGraph();

  // Extract skeletal m_Graph
  // Limitation: currently image spacing is not taken into account.
  // If image spacing is highly anisotropic then longest path computation
  // may not give optimal results, and sampling distance (when calling
  // SampleAlongMaximalPath) may be uneven.
  void ExtractSkeletalGraph(const unsigned char *image, const int dim[3], const double spacing[3]);

  // Extract maximal path between 2 points in the m_Graph
  void FindMaximalPath();

  // Sample points along the maximal path.
  // requestedNumberOfPoints is an approximate number of points to be returned.
  void SampleAlongMaximalPath(int requestedNumberOfPoints, std::deque<Coord3i> &axis_points);

private:

  // private routines

  // adds a new element with default values to To_do list
  skel_branch* AddNewBranchToDo(std::list<skel_branch> &branchesToDo);

  // find all endpoints in image
  void FindEndpoints(std::deque<Coord3i> &endPoints, const unsigned char *image, const int dim[3]);

  // tests whether (x,y,z) is an endpoint
  int IsEndpoint(int x, int y, int z, const unsigned char *image, const int dim[3]);

  // returns a list of valid neighbors at act_point
  // points that exist in skeleton, but are yet unlabeled
  void GetValidNeighbors(int* label_image, Coord3i &act_point, std::deque<Coord3i> &neighbors, const unsigned char *image, const int dim[3]);

  void ResetGraph();

  // Extracted Graph
  std::deque<skel_branch> m_Graph;

  // To_Do list, only of temporary use for extract m_Graph
  //std::deque<skel_branch> * branchesToDo;

  // List of branch IDs that make up the longest path
  std::deque<int> m_MaximalPath;
  double m_MaximalPathLength;
  double m_Spacing[3];

};

#endif