I am trying to implement the Maidster distance conversion algorithm in Halide. I have already rewritten this code in C ++ (using openCV) and it works great. An article about this algorithm is here . Currently, my halide code is 50% complete - the first phase is working fine, now I have a problem with phase 2 (scan 3 in the linked code), which (simplified) look like this:
//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 }
Is there any halogen way to replace this cycle? Right now, the only solution I came up with looks like this (not yet tested):
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); }
but even if this works, most likely the halogen will try to evaluate both select values before checking the state, and recursion will make it very slow.
If there is no way to implement while loop in Halide, is there a way to use part of the code inside Halide? Any other ideas?