在没有define_extern函数的情况下在Halide中实现Canny算法的滞后步骤的困难 [英] Difficulties implementing the Hysteresis step of Canny Algorithm in Halide without define_extern func
问题描述
- The problem is that when a pixel marked as weak-edge (between the two thresholds) changes to strong-edge (accepted, as described here) it is required to apply the same logic to your connected neighbors recursively (tracking the edges).
- In an imperative language, when changing from weak to strong edge, a Stack could be used to store the position (x,y). Then, at the end, process the neighbors while the stack is not empty, updating the Stack as needed. But, how to implement anything similar in pure Halide, without define_extern func?
我已使用此代码进行磁滞，但是缺少动态递归和/或堆栈，以便在需要时对邻居执行磁滞，这是我找不到的实现方式:
I have used this code to hysteresis, but lacks the dynamic recursion and/or stack to do hysteresis on the neighbors when needed, which is what I can't find how to implement:
magnitude = input(x, y);
// mask receives only 0, 1, or 2.
mask(x, y) = select(magnitude > high_threshold, 2/*strong-edge*/, magnitude < low_threshold, 0/*no-edge*/, 1/*weak-edge*/);
// when mask(x,y) == 1 checks the neighbors to decide.
hysteresis(x, y) = select(mask(x, y) == 0, 0, mask(x, y) == 2, 255,
mask(x-1, y-1) == 2 || mask(x, y-1) == 2 || mask(x+1, y-1) == 2 ||
mask(x-1, y) == 2 || mask(x+1, y) == 2 ||
mask(x-1, y+1) == 2 || mask(x, y+1) == 2 || mask(x+1, y+1) == 2, 255/*weak-to-strong edge*/, 0);
值得怀疑的是，是否有一种方法可以通过递归，堆栈或其他任何方式来执行以下操作:
The doubt, is there a way to, with recursion, stack, or anything else, do something like this:
if (hysteresis(x, y) above changes from weak to strong edge, do) {
hysteresis(x-1, y-1); hysteresis(x, y-1); hysteresis(x+1, y-1);
hysteresis(x-1, y); hysteresis(x+1, y);
hysteresis(x-1, y+1); hysteresis(x, y+1); hysteresis(x+1, y+1);
}
推荐答案
简短答案:否.
无法使用非图像数据结构(如堆栈)，也无法进行动态递归.尚不清楚Halide是否会真正在这里增加很多价值，因为编写该算法时似乎并不能将其平铺，并行化或向量化.
There's no way to use non-image data structures (like a stack), and no way to do dynamic recursion. It's not clear that Halide would really add much value here, because that algorithm doesn't seem to be tileable, parallelizable or vectorizable as it is written.
但是，您可能可以将算法重新编写为一种算法，从而可以对从弱到强的图像翻转边缘进行迭代扫描.可以认为它是在三种状态(弱，强，不是边缘)运行时完成的元胞自动机，我们可以矢量化/并行化每个遍.有关示例，请参阅Halide回购中的test/correctity/gameoflife.cpp.我认为，这样做的方式虽然会带来糟糕的计算复杂性.您将在每个像素上进行工作，而不仅仅是在正在翻转的像素的活动边缘上进行工作.
You may however be able to re-write the algorithm as one that makes iterative sweeps over the image flipping edges from weak to strong. It can be thought of as a cellular automata on three states (weak, strong, not an edge) run to completion, and we could vectorize/parallelize each pass. See test/correctness/gameoflife.cpp in the Halide repo for an example. I think this way of doing it would have a lousy computational complexity though. You'd be doing work at every pixel, not just at the live edge of pixels that are flipping.
您还可以将其作为元胞自动机运行，沿某些波前进行就地更新，例如从上到下，从下到上，从左到右和从右到左进行扫描.然后，您可以沿波前矢量化.该时间表类似于IIR(请参见 https://github. com/halide/CVPR2015/blob/master/RecursiveFilter/IirBlur.cpp ).这种方法可以处理沿任何方向的线性边缘，但是任何固定数量的扫掠都将错过从弱到强的螺旋运动.
You could also run it as a cellular automata that does in-place updates along some wavefront, e.g. do a sweep from top to bottom, bottom to top, left to right, and right to left. You can then vectorize along the wavefront. The schedule would be similar to an IIR (see https://github.com/halide/CVPR2015/blob/master/RecursiveFilter/IirBlur.cpp). That approach would handle a linear edge along any direction, but any fixed numbers of sweeps would miss a spiral moving from weak to strong.
但是，我不会使用这些方法来扭曲您的代码，而只是使用其他算法或使用define_extern.
But rather than contort your code in these ways, I would just use a different algorithm, or use define_extern.
这篇关于在没有define_extern函数的情况下在Halide中实现Canny算法的滞后步骤的困难的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
