卤化物 - while 循环等效

Question

我正在尝试在 Halide 中实现 Meijster 距离变换算法。我已经重写了this code to C++ (using openCV) and it's working fine. The paper about this algorithm is here。现在我的卤化物代码完成了 50%——第一阶段工作正常，现在我遇到了第 2 阶段的问题（链接代码中的扫描 3）（简化）如下所示：

//g is 2 dimensional cv::Mat (something like array) - result of previous stage
// m is g.width and n is g.height
int(*functionF)(int x, int i, int g_i) = EDT_f;
int(*functionSep)(int i, int u, int g_i, int g_u, int max_value) = EDT_Sep;
cv::Mat dt = cv::Mat(n, m, CV_32SC1);
int* s = new int[m];
int* t = new int[m];
int q = 0, w;

for (int y = 0; y<n; y++)
{
    q = 0;
    s[0] = 0;
    t[0] = 0;

    // Scan 3
    for (int u = 1; u<m; u++)
    {
    //how can i replace this loop:
        while (q >= 0 && functionF(t[q], s[q], g.at<int>(y, s[q])) > functionF(t[q], u, g.at<int>(y, u)))
            q--;
        //some operations which might change value of q, s[] and t[]
    }
    // Scan 4 - not important here
}

是否有任何 卤化物友好 的方法来替换这个 while 循环？目前我唯一的解决方案是这样的（尚未测试）：

Expr calculateQ(Expr currentQValue, Expr y, Func t, Func s, Func g)
{
    //while (q >= 0 && functionF(t[q], s[q], g.at<int>(y, s[q])) > functionF(t[q], u, g.at<int>(y, u)))
        //q--;
    return select(currentQValue >= 0 && functionF(t[q], s[q], g[s[q], y]) > functionF(t[q], u, g[u, y]), calculateQ(currentQValue - 1, y, t, s, g), currentQValue);
}

但即使这行得通，卤化物很可能会在检查条件之前尝试评估 select 的两个值，递归会使它变得非常慢。

如果无法在 Halide 中实现 while 循环，是否有任何方法可以在 Halide 中仅使用部分代码？还有其他想法吗？

Answer 1

您正确地注意到，如何表达动态终止 (while) 循环并不明显——它们现在不可能用纯 Halide 表达！这可能会在（不确定的、长期的）未来发生变化，但添加这些将使循环 Halide 程序成为图灵完备的；没有它们，我们总是可以分析你的循环的边界，但是我们有它们，我们将面临停机问题。

不过，对于这类事情有一个逃生口：您可以从 Halide 管道内部调用外部函数（用 C 或其他语言实现）。 extern 函数的接口看起来与编译管道的接口相同（它采用标量和缓冲区参数，最终缓冲区是输出，如果使用空缓冲区调用，它必须计算其输入所需的边界给定边界请求其输出）。查看 extern_* 测试程序以获取一些示例，例如 https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp。快速浏览一下您的代码，我相信它应该可以使用您已有的 C 代码在外部阶段轻松实现。

卤化物 - while 循环等效

Halide - while loop equivalent

c++

opencv

image-processing

while-loop

halide