diff --git a/CMakeExternals/MITKData.cmake b/CMakeExternals/MITKData.cmake index 499210521b..b6f96d9211 100644 --- a/CMakeExternals/MITKData.cmake +++ b/CMakeExternals/MITKData.cmake @@ -1,36 +1,36 @@ #----------------------------------------------------------------------------- # MITK Data #----------------------------------------------------------------------------- # Sanity checks if(DEFINED MITK_DATA_DIR AND NOT EXISTS ${MITK_DATA_DIR}) message(FATAL_ERROR "MITK_DATA_DIR variable is defined but corresponds to non-existing directory") endif() set(proj MITK-Data) set(proj_DEPENDENCIES) set(MITK-Data_DEPENDS ${proj}) if(BUILD_TESTING) - set(revision_tag 15387de2) # first 8 characters of hash-tag + set(revision_tag 7a7d873f) # first 8 characters of hash-tag # ^^^^^^^^ these are just to check correct length of hash part ExternalProject_Add(${proj} URL ${MITK_THIRDPARTY_DOWNLOAD_PREFIX_URL}/MITK-Data_${revision_tag}.tar.gz UPDATE_COMMAND "" CONFIGURE_COMMAND "" BUILD_COMMAND "" INSTALL_COMMAND "" DEPENDS ${proj_DEPENDENCIES} ) set(MITK_DATA_DIR ${ep_source_dir}/${proj}) else() mitkMacroEmptyExternalProject(${proj} "${proj_DEPENDENCIES}") endif(BUILD_TESTING) diff --git a/Modules/AlgorithmsExt/Testing/files.cmake b/Modules/AlgorithmsExt/Testing/files.cmake index 6c05504feb..06daaeba52 100644 --- a/Modules/AlgorithmsExt/Testing/files.cmake +++ b/Modules/AlgorithmsExt/Testing/files.cmake @@ -1,14 +1,15 @@ set(MODULE_TESTS mitkAutoCropImageFilterTest.cpp mitkBoundingObjectCutterTest.cpp mitkImageToUnstructuredGridFilterTest.cpp mitkPlaneFitTest.cpp mitkSimpleHistogramTest.cpp mitkCovarianceMatrixCalculatorTest.cpp mitkAnisotropicIterativeClosestPointRegistrationTest.cpp + mitkUnstructuredGridClusteringFilterTest.cpp mitkUnstructuredGridToUnstructuredGridFilterTest.cpp ) set(MODULE_CUSTOM_TESTS mitkLabeledImageToSurfaceFilterTest.cpp ) diff --git a/Modules/AlgorithmsExt/Testing/mitkUnstructuredGridClusteringFilterTest.cpp b/Modules/AlgorithmsExt/Testing/mitkUnstructuredGridClusteringFilterTest.cpp new file mode 100644 index 0000000000..8f2409f9e7 --- /dev/null +++ b/Modules/AlgorithmsExt/Testing/mitkUnstructuredGridClusteringFilterTest.cpp @@ -0,0 +1,129 @@ +/*=================================================================== + +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 "mitkTestingMacros.h" +#include +#include +#include +#include + +#include + +#include +#include +#include +#include + +class mitkUnstructuredGridClusteringFilterTestSuite : public mitk::TestFixture +{ + CPPUNIT_TEST_SUITE(mitkUnstructuredGridClusteringFilterTestSuite); + + vtkDebugLeaks::SetExitError(0); + + MITK_TEST(testUnstructuredGridClusteringFilterInitialization); + MITK_TEST(testInput); + MITK_TEST(testUnstructuredGridGeneration); + MITK_TEST(testReturnedCluster); + MITK_TEST(testClusterVector); + MITK_TEST(testGetNumberOfFoundClusters); + CPPUNIT_TEST_SUITE_END(); + +private: + + mitk::UnstructuredGrid::Pointer m_UnstructuredGrid; + +public: + + void setUp() + { + m_UnstructuredGrid = mitk::UnstructuredGrid::New(); + + //Loading the test data + std::vector< mitk::BaseData::Pointer > vector = mitk::IOUtil::Load(GetTestDataFilePath("UnstructuredGrid/scoredGrid.vtu")); + mitk::BaseData::Pointer base = vector.at(0); + m_UnstructuredGrid = dynamic_cast(base.GetPointer()); + } + + void testUnstructuredGridClusteringFilterInitialization() + { + mitk::UnstructuredGridClusteringFilter::Pointer clusterFilter = mitk::UnstructuredGridClusteringFilter::New(); + CPPUNIT_ASSERT_MESSAGE("Testing instantiation of filter object", clusterFilter.IsNotNull()); + } + + void testInput() + { + mitk::UnstructuredGridClusteringFilter::Pointer clusterFilter = mitk::UnstructuredGridClusteringFilter::New(); + clusterFilter->SetInput(m_UnstructuredGrid); + CPPUNIT_ASSERT_MESSAGE("Testing set / get input!", clusterFilter->GetInput() == m_UnstructuredGrid); + } + + void testUnstructuredGridGeneration() + { + mitk::UnstructuredGridClusteringFilter::Pointer clusterFilter = mitk::UnstructuredGridClusteringFilter::New(); + clusterFilter->SetInput(m_UnstructuredGrid); + clusterFilter->SetMeshing(false); + clusterFilter->SetMinPts(4); + clusterFilter->Seteps(1.2); + clusterFilter->Update(); + CPPUNIT_ASSERT_MESSAGE("Testing output generation!", clusterFilter->GetOutput() != NULL); + } + + void testReturnedCluster() + { + mitk::UnstructuredGridClusteringFilter::Pointer clusterFilter = mitk::UnstructuredGridClusteringFilter::New(); + clusterFilter->SetInput(m_UnstructuredGrid); + clusterFilter->SetMeshing(false); + clusterFilter->SetMinPts(4); + clusterFilter->Seteps(1.2); + clusterFilter->Update(); + mitk::UnstructuredGrid::Pointer cluster = clusterFilter->GetOutput(); + CPPUNIT_ASSERT_MESSAGE("Testing the output cluster!", cluster->GetVtkUnstructuredGrid()->GetPoints()->GetNumberOfPoints() == 620); + } + + void testClusterVector() + { + mitk::UnstructuredGridClusteringFilter::Pointer clusterFilter = mitk::UnstructuredGridClusteringFilter::New(); + clusterFilter->SetInput(m_UnstructuredGrid); + clusterFilter->SetMeshing(false); + clusterFilter->SetMinPts(4); + clusterFilter->Seteps(1.2); + clusterFilter->Update(); + std::vector< mitk::UnstructuredGrid::Pointer > clustervector = clusterFilter->GetAllClusters(); + //test that all clusters have points: + bool havePoints = true; + for(unsigned int i=0; iGetVtkUnstructuredGrid()->GetPoints()->GetNumberOfPoints()<1) + havePoints = false; + } + CPPUNIT_ASSERT_MESSAGE("Testing number of found clusters!", havePoints && clustervector.size() == 17); + } + + void testGetNumberOfFoundClusters() + { + mitk::UnstructuredGridClusteringFilter::Pointer clusterFilter = mitk::UnstructuredGridClusteringFilter::New(); + clusterFilter->SetInput(m_UnstructuredGrid); + clusterFilter->SetMeshing(false); + clusterFilter->SetMinPts(4); + clusterFilter->Seteps(1.2); + clusterFilter->Update(); + CPPUNIT_ASSERT_MESSAGE("Testing number of found clusters!", clusterFilter->GetNumberOfFoundClusters() == 17); + } + +}; + +MITK_TEST_SUITE_REGISTRATION(mitkUnstructuredGridClusteringFilter) diff --git a/Modules/AlgorithmsExt/files.cmake b/Modules/AlgorithmsExt/files.cmake index 8da26c4dd3..72ee58aa5c 100644 --- a/Modules/AlgorithmsExt/files.cmake +++ b/Modules/AlgorithmsExt/files.cmake @@ -1,32 +1,33 @@ set(CPP_FILES mitkAutoCropImageFilter.cpp mitkBoundingObjectCutter.cpp mitkBoundingObjectToSegmentationFilter.cpp mitkGeometryClipImageFilter.cpp mitkGeometryDataSource.cpp mitkHeightFieldSurfaceClipImageFilter.cpp mitkImageToUnstructuredGridFilter.cpp mitkLabeledImageToSurfaceFilter.cpp mitkMaskAndCutRoiImageFilter.cpp mitkMaskImageFilter.cpp mitkMovieGenerator.cpp mitkNonBlockingAlgorithm.cpp mitkPadImageFilter.cpp mitkPlaneFit.cpp mitkPlaneLandmarkProjector.cpp mitkPointLocator.cpp mitkSegmentationSink.cpp mitkSimpleHistogram.cpp mitkSimpleUnstructuredGridHistogram.cpp mitkCovarianceMatrixCalculator.cpp mitkAnisotropicIterativeClosestPointRegistration.cpp mitkWeightedPointTransform.cpp mitkAnisotropicRegistrationCommon.cpp + mitkUnstructuredGridClusteringFilter.cpp mitkUnstructuredGridToUnstructuredGridFilter.cpp ) if(WIN32 AND NOT MINGW) list(APPEND CPP_FILES mitkMovieGeneratorWin32.cpp ) endif() diff --git a/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.cpp b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.cpp new file mode 100644 index 0000000000..9b1f089927 --- /dev/null +++ b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.cpp @@ -0,0 +1,218 @@ +/*=================================================================== + +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 +#include +#include + + +mitk::UnstructuredGridClusteringFilter::UnstructuredGridClusteringFilter() : m_eps(0.0), m_MinPts(0), m_Meshing(true) +{ + this->m_UnstructGrid = mitk::UnstructuredGrid::New(); +} + +mitk::UnstructuredGridClusteringFilter::~UnstructuredGridClusteringFilter(){} + +std::map visited; +std::map isNoise; +std::map clusterMember; +vtkSmartPointer pLocator; + +void mitk::UnstructuredGridClusteringFilter::GenerateOutputInformation() +{ + m_UnstructGrid = this->GetOutput(); +} + +void mitk::UnstructuredGridClusteringFilter::GenerateData() +{ + 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< vtkSmartPointer > 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++) + { + if(!visited[i]) + { + visited[i] = true; //mark P as visited + vtkSmartPointer idList = vtkSmartPointer::New(); //represent N + pLocator->FindPointsWithinRadius(m_eps, inpPoints->GetPoint(i), idList); //N = D.regionQuery(P, eps) + if(idList->GetNumberOfIds() < m_MinPts) //if sizeof(N) < MinPts + { + isNoise[i] = true; //mark P as NOISE + } + else + { + vtkSmartPointer cluster = vtkSmartPointer::New(); //represent a cluster + clusterVector.push_back(cluster); //C = next cluster + this->ExpandCluster(i,idList,cluster,inpPoints); //expandCluster(P, N, C, eps, MinPts) mod. the parameter list + } + } + } + + //OUTPUT LOGIC + m_Clusters = clusterVector; + int numberOfClusterPoints = 0; + int IdOfBiggestCluster = 0; + + for(unsigned int i=0; i points = m_Clusters.at(i); + for(int j=0; jGetNumberOfPoints();j++) + { + double point[3]; + points->GetPoint(j,point); + } + if(points->GetNumberOfPoints() > numberOfClusterPoints) + { + numberOfClusterPoints = points->GetNumberOfPoints(); + IdOfBiggestCluster = i; + } + } + + vtkSmartPointer biggestCluster = vtkSmartPointer::New(); + + vtkSmartPointer points = vtkSmartPointer::New(); + points = m_Clusters.at(IdOfBiggestCluster); + + vtkSmartPointer verts = vtkSmartPointer::New(); + verts->GetPointIds()->SetNumberOfIds(m_Clusters.at(IdOfBiggestCluster)->GetNumberOfPoints()); + for(int i=0; iGetNumberOfPoints(); i++) + { + verts->GetPointIds()->SetId(i,i); + } + + biggestCluster->Allocate(1); + biggestCluster->InsertNextCell(verts->GetCellType(), verts->GetPointIds()); + biggestCluster->SetPoints(m_Clusters.at(IdOfBiggestCluster)); + + if(m_Meshing) + { + vtkSmartPointer mesher = vtkSmartPointer::New(); + mesher->SetInputData(biggestCluster); + mesher->SetAlpha(0.9); + mesher->Update(); + + vtkSmartPointer output = mesher->GetOutput(); + m_UnstructGrid->SetVtkUnstructuredGrid(output); + } + else + { + m_UnstructGrid->SetVtkUnstructuredGrid(biggestCluster); + } +} + +void mitk::UnstructuredGridClusteringFilter::ExpandCluster(int id, vtkIdList *pointIDs, vtkPoints* cluster, vtkPoints* inpPoints) +{ + cluster->InsertNextPoint(inpPoints->GetPoint(id)); //add P to cluster C + clusterMember[id] = true; //right? + + vtkSmartPointer neighbours = vtkSmartPointer::New(); //same N as in other function + inpPoints->GetPoints(pointIDs,neighbours); + + for(int i=0; iGetNumberOfIds();i++) //for each point P' in N + { + if(!visited[pointIDs->GetId(i)]) //if P' is not visited + { + visited[pointIDs->GetId(i)] = true; //mark P' as visited + vtkSmartPointer idList = vtkSmartPointer::New(); //represent N' + pLocator->FindPointsWithinRadius(m_eps, inpPoints->GetPoint(pointIDs->GetId(i)), idList); //N' = D.regionQuery(P', eps) + if(idList->GetNumberOfIds() >= m_MinPts) //if sizeof(N') >= MinPts + { + for(int j=0; jGetNumberOfIds();j++) //N = N joined with N' + { + pointIDs->InsertNextId(idList->GetId(j)); + } + } + } + if(!clusterMember[pointIDs->GetId(i)]) //if P' is not yet member of any cluster + { + clusterMember[pointIDs->GetId(i)] = true; + cluster->InsertNextPoint(inpPoints->GetPoint(pointIDs->GetId(i))); //add P' to cluster C + } + } +} + +std::vector mitk::UnstructuredGridClusteringFilter::GetAllClusters() +{ + std::vector< mitk::UnstructuredGrid::Pointer > mitkUGridVector; + + for(unsigned int i=0; i cluster = vtkSmartPointer::New(); + + vtkSmartPointer points = m_Clusters.at(i); + + vtkSmartPointer verts = vtkSmartPointer::New(); + + verts->GetPointIds()->SetNumberOfIds(points->GetNumberOfPoints()); + for(int i=0; iGetNumberOfPoints(); i++) + { + verts->GetPointIds()->SetId(i,i); + } + + cluster->Allocate(1); + cluster->InsertNextCell(verts->GetCellType(), verts->GetPointIds()); + cluster->SetPoints(points); + + mitk::UnstructuredGrid::Pointer mitkGrid = mitk::UnstructuredGrid::New(); + + if(m_Meshing) + { + vtkSmartPointer mesher = vtkSmartPointer::New(); + mesher->SetInputData(cluster); + mesher->SetAlpha(0.9); + mesher->Update(); + + vtkSmartPointer output = mesher->GetOutput(); + mitkGrid->SetVtkUnstructuredGrid(output); + } + else + { + mitkGrid->SetVtkUnstructuredGrid(cluster); + } + + mitkUGridVector.push_back(mitkGrid); + } + + return mitkUGridVector; +} + +int mitk::UnstructuredGridClusteringFilter::GetNumberOfFoundClusters() +{ + return m_Clusters.size(); +} diff --git a/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.h b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.h new file mode 100644 index 0000000000..606c18ca99 --- /dev/null +++ b/Modules/AlgorithmsExt/mitkUnstructuredGridClusteringFilter.h @@ -0,0 +1,112 @@ +/*=================================================================== + +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 +#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) + + itkSetMacro(Meshing, bool) + + virtual std::vector< mitk::UnstructuredGrid::Pointer> GetAllClusters(); + + virtual int GetNumberOfFoundClusters(); + + virtual void GenerateOutputInformation(); + + virtual void GenerateData(); + + protected: + + UnstructuredGridClusteringFilter(); + + virtual ~UnstructuredGridClusteringFilter(); + + private: + + void ExpandCluster(int id, vtkIdList* pointIDs, vtkPoints* cluster, vtkPoints *inpPoints); + + mitk::UnstructuredGrid::Pointer m_UnstructGrid; + + std::vector< vtkSmartPointer > m_Clusters; + + double m_eps; + + int m_MinPts; + + bool m_Meshing; + + }; + +} // namespace mitk + +#endif //_MITKUNSTRUCTUREDGRIDCLUSTERINGFILTER_h__ + +