diff --git a/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.cpp b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.cpp index 44f3044b73..cccc2b4b89 100644 --- a/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.cpp +++ b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.cpp @@ -1,37 +1,107 @@ /*=================================================================== The Medical Imaging Interaction Toolkit (MITK) Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See LICENSE.txt or http://www.mitk.org for details. ===================================================================*/ #include #include -#include +#include #include -mitk::UnstructuredGridClusteringFilter::UnstructuredGridClusteringFilter() +mitk::UnstructuredGridClusteringFilter::UnstructuredGridClusteringFilter() : m_eps(0.0), m_MinPts(0) { this->m_UnstructGrid = mitk::UnstructuredGrid::New(); } mitk::UnstructuredGridClusteringFilter::~UnstructuredGridClusteringFilter(){} +std::map visited; +std::map isNoise; +std::map clusterMember; +vtkSmartPointer pLocator; + void mitk::UnstructuredGridClusteringFilter::GenerateOutputInformation() { - mitk::UnstructuredGrid::Pointer inputImage = const_cast(this->GetInput()); - if(inputImage.IsNull()) return; + mitk::UnstructuredGrid::Pointer inputGrid = const_cast(this->GetInput()); + if(inputGrid.IsNull()) return; + + vtkSmartPointer vtkInpGrid = inputGrid->GetVtkUnstructuredGrid(); + vtkSmartPointer inpPoints = vtkInpGrid->GetPoints(); + pLocator =vtkSmartPointer::New(); + std::vector clusterVector; + + pLocator->SetDataSet(vtkInpGrid); + pLocator->AutomaticOn(); + pLocator->SetNumberOfPointsPerBucket(2); + pLocator->BuildLocator(); + + //fill the visited map with false for checking + for(int i=0; iGetNumberOfPoints();i++) + { + visited[i] = false; + isNoise[i] = false; + clusterMember[i] = false; + } + + for(int i=0; iGetNumberOfPoints();i++) + { + visited[i] = true; //mark P as visited + vtkSmartPointer idList = vtkSmartPointer::New(); + pLocator->FindPointsWithinRadius(m_eps, inpPoints->GetPoint(i), idList); //find neighbours + if(idList->GetNumberOfIds() < m_MinPts) + { + isNoise[i] = true;//point is noise - maybe just skip it? + } + else + { + vtkSmartPointer cluster = vtkSmartPointer::New(); + clusterVector.push_back(cluster); + this->ExpandCluster(i,idList,cluster,inpPoints); + } + } m_UnstructGrid = this->GetOutput(); } + +void mitk::UnstructuredGridClusteringFilter::ExpandCluster(int id, vtkIdList *pointIDs, vtkPoints* cluster, vtkPoints* inpPoints) +{ + cluster->InsertNextPoint(inpPoints->GetPoint(id)); //add Point to Cluster + + vtkSmartPointer neighbours = vtkSmartPointer::New(); + inpPoints->GetPoints(pointIDs,neighbours); + + for(int i=0; iGetNumberOfIds();i++) + { + if(!visited[pointIDs->GetId(i)]) //if P is not visited + { + visited[pointIDs->GetId(i)] = true; // mark P as visited + vtkSmartPointer idList = vtkSmartPointer::New(); + pLocator->FindPointsWithinRadius(m_eps, inpPoints->GetPoint(pointIDs->GetId(i)), idList); //find neighbours + if(idList->GetNumberOfIds() >= m_MinPts) + { + for(int j=0; jGetNumberOfIds();j++)//join every point in range to the points + { + pointIDs->InsertNextId(idList->GetId(j)); + } + } + } + if(!clusterMember[pointIDs->GetId(i)]) //P ist not yet member of any cluster + { + clusterMember[pointIDs->GetId(i)] = true; + cluster->InsertNextPoint(inpPoints->GetPoint(pointIDs->GetId(i))); + } + } +} diff --git a/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.h b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.h index 4123e47a22..942ed72f88 100644 --- a/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.h +++ b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.h @@ -1,57 +1,99 @@ /*=================================================================== The Medical Imaging Interaction Toolkit (MITK) Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See LICENSE.txt or http://www.mitk.org for details. ===================================================================*/ #ifndef _MITKUNSTRUCTUREDGRIDCLUSTERINGFILTER_h__ #define _MITKUNSTRUCTUREDGRIDCLUSTERINGFILTER_h__ #include #include #include #include +#include +#include namespace mitk { + /** + * @brief The UnstructuredGridClusteringFilter class + * + * DBSCAN algorithm: + * + * DBSCAN(D, eps, MinPts) + * C = 0 + * for each unvisited point P in dataset D + * mark P as visited + * N = D.regionQuery(P, eps) + * if sizeof(N) < MinPts + * mark P as NOISE + * else + * C = next cluster + * expandCluster(P, N, C, eps, MinPts) + * + * expandCluster(P, N, C, eps, MinPts) + * add P to cluster C + * for each point P' in N + * if P' is not visited + * mark P' as visited + * N' = D.regionQuery(P', eps) + * if sizeof(N') >= MinPts + * N = N joined with N' + * if P' is not yet member of any cluster + * add P' to cluster C + */ + class MitkAlgorithmsExt_EXPORT UnstructuredGridClusteringFilter : public UnstructuredGridToUnstructuredGridFilter { public: mitkClassMacro(UnstructuredGridClusteringFilter, UnstructuredGridToUnstructuredGridFilter) itkFactorylessNewMacro(Self) itkCloneMacro(Self) + itkSetMacro(eps, double) + itkGetMacro(eps, double) + + itkSetMacro(MinPts, int) + itkGetMacro(MinPts, int) + virtual void GenerateOutputInformation(); protected: UnstructuredGridClusteringFilter(); virtual ~UnstructuredGridClusteringFilter(); private: + void ExpandCluster(int id, vtkIdList* pointIDs, vtkPoints* cluster, vtkPoints *inpPoints); + mitk::UnstructuredGrid::Pointer m_UnstructGrid; + double m_eps; + + int m_MinPts; + }; } // namespace mitk #endif //_MITKUNSTRUCTUREDGRIDCLUSTERINGFILTER_h__