Halide - while while loop

Question

我正試圖在Halide中實現Meijster距離變換算法。我已經將this code改寫爲C++（使用openCV）並且工作正常。關於這種算法的文章是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循環？現在唯一的解決辦法，到目前爲止我來是smething像這樣（沒有測試過）：

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); 
} 

但即使這會的工作，最有可能的鹵化物將試圖評估選擇這兩個值檢查條件之前遞歸會使其非常緩慢。

如果沒有辦法實現while Halide循環有什麼方法可以在Halide中使用代碼的一部分？任何其他想法？

Answer 1

你說得沒錯，如何表達一個動態終止（while）循環 - 他們不可能在純粹的Halide中表現出來！這可能會在（無限期的，長期的）未來發生變化，但是增加這些可以使循環Halide程序圖靈完成;沒有他們，我們總是可以分析你的循環的邊界，但是我們他們，我們會面臨停滯的問題。

儘管有這樣的事情的逃生艙口蓋：你可以從Halide管道內調用外部函數（用C或其他任何東西實現）。 extern函數的接口看起來與編譯管道的接口相同（它需要標量和緩衝區參數，最終的緩衝區是輸出，如果使用空緩衝區調用，它必須計算其輸入所需的邊界，給定邊界要求輸出）。查看extern_*測試程序的一些示例，例如https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp。快速瀏覽你的代碼，我相信它應該很容易在extern階段使用你已經擁有的C代碼來實現。