dijkstra最短路径算法在三维图像上的实现。
dijkstra3d的Python项目详细描述
dijkstra3d
Dijkstra的最短路径变体，用于26个连接的三维图像卷或8个连接的二维图像。
在三维图像网格上执行dijkstra的最短路径算法。顶点是体素，边是26个最近的邻居（除了图像的边，边的数量减少）。对于给定的输入体素A和B，从A到B的边权重为B，从B到A的边权重为A。所有权重必须为非负（包括负零）。
这个包能解决什么问题？
该软件包是在探索三维图像体的teasar骨架化过程中开发的（核心部分现在可以在Kimimaro中找到）。其他实现dijkstra的常用包使用矩阵或对象图作为其底层实现。在这两种情况下，这些通用图包都需要显式地创建图的边和顶点，与执行时间相比，这是一个很大的计算开销。此外，一些实现需要顶点数量的二次内存（例如，n个节点的nxn矩阵）。在某些情况下，使用压缩稀疏矩阵表示保持在内存限制内。
对于图像分析应用程序，这两种成本都不是必需的。在图像的矩形结构中，体素（3d像素）之间的边是规则的且隐式的。此外，每个边缘的成本可以存储一次，而不是26次在连续的未压缩内存区域中，以获得更快的性能。
提供Dijkstra变体
以下变体有二维和三维两种版本：
- dijkstra-源和目标之间的最短路径。在找到目标时提前终止。
- parental_field/query_shortest_path-计算源和所有目标之间的最短路径。使用query_shortest_path对结果集进行重复查询。
- euclidean_distance_field-给定布尔标记字段和源顶点，计算从源到所有标记顶点的各向异性euclidean距离。
- 距离场-给定一个数值场，对于相邻体素a和b的每个定向边，使用b作为边权重。以这种方式，计算所有有限体素到源点的距离。
python使用
importdijkstra3dimportnumpyasnpfield=np.ones((512,512,512),dtype=np.int32)path=dijkstra3d.dijkstra(field,(0,0,0),(511,511,511))# terminates earlyprint(path.shape)parents=dijkstra3d.parental_field(field,source=(0,0,0))path=dijkstra3d.path_from_parents(parents,target=(511,511,511))print(path.shape)dist_field=dijkstra3d.euclidean_distance_field(field,source=(0,0,0),anisotropy=(4,4,40))dist_field=dijkstra3d.distance_field(field,source=(0,0,0))使用C++
#include<vector>#include"dijkstra3d.hpp"// 3d array represented as 1d arrayfloat*labels=newfloat[512*512*512]();// x + sx * y + sx * sy * zintsource=0+512*5+512*512*3;// coordinate <0, 5, 3>inttarget=128+512*128+512*512*128;// coordinate <128, 128, 128>vector<unsignedint>path=dijkstra::dijkstra3d<float>(labels,/*sx=*/512,/*sy=*/512,/*sz=*/512,source,target);uint32_t*parents=dijkstra::parental_field3d<float>(labels,/*sx=*/512,/*sy=*/512,/*sz=*/512,source);vector<unsignedint>path=dijkstra::query_shortest_path(parents,target);float*field=dijkstra::euclidean_distance_field3d<float>(labels,/*sx=*/512,/*sy=*/512,/*sz=*/512,/*wx=*/4,/*wy=*/4,/*wz=*/40,source);float*field=dijkstra::distance_field3d<float>(labels,/*sx=*/512,/*sy=*/512,/*sz=*/512,source);
pythonpip二进制安装
pip install dijkstra3d
pythonpip源安装
^ {EM1}$需要一个C++编译器。
pip install numpy pip install dijkstra3d
python直接安装
需要一个C++编译器。git clone https://github.com/seung-lab/dijkstra3d.git cd dijkstra3d virtualenv -p python3 venv source venv/bin/activate pip install -r requirements.txt python setup.py develop
性能
在512x512x512 float32图像的左下角到右上角的一个字段中，在3.7 GHz Intel i7-4920K CPU上，大约需要41秒的时间才能达到约3 MVX/秒的性能评级。此测试强制算法处理几乎所有的卷（找到目标时dijkstra会提前终止）。
图1:dijkstra.dijkstra的基准运行在从左下角到右上角目标的5123体素场上。分配细分：512 MB源图像，512 MB距离字段，512 MB父字段。
那是什么配对的heap.hpp？
早期，我预计在堆中使用decrease键并实现了一个配对堆，这应该是对fibbonacci堆的改进。但是，我最终没有使用reduce key，stl优先级队列的速度更快。如果需要boost之外的配对堆，请检查它。
参考文献
- 迪杰斯特拉。”关于图“数字数学1”中两个问题的注记第269-271页。（1959年）
- 迪杰斯特拉。”转到被认为有害的声明”。ACM的通信。第11卷，第3期，第147-148页。（1968年）
欢迎加入QQ群-->： 979659372
