Сложности реализации шага гистерезиса алгоритма Канни в Halide без функции define_extern

Question

• Проблема заключается в том, что когда пиксель, помеченный как слабый край (между двумя пороговыми значениями), меняется на сильный край (принятый, как описано здесь), необходимо рекурсивно применять ту же логику к подключенным соседям (отслеживая края).
• В императивном языке при переходе от слабого к сильному краю может использоваться стек для сохранения позиции (x,y). Затем, в конце, обработайте соседей, пока стек не пуст, обновляя стек по мере необходимости. Но как реализовать что-то подобное в чистом Halide, без функции define_extern?

Я использовал этот код для гистерезиса, но не хватает динамической рекурсии и / или стека для выполнения гистерезиса по соседям, когда это необходимо, что я не могу найти, как реализовать:

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

Сомнение, есть ли способ с помощью рекурсии, стека или чего-либо еще сделать что-то вроде этого:

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

Answer 1

Краткий ответ: Нет.

Нет способа использовать структуры данных без изображений (например, стек), и нет способа сделать динамическую рекурсию. Не ясно, что Halide действительно принесет большую пользу, потому что этот алгоритм не выглядит мозаичным, распараллеливаемым или векторизованным, как он написан.

Тем не менее, вы можете переписать алгоритм как алгоритм, который делает итеративные развертки по краям изображения, переворачивающим от слабого к сильному. Его можно представить как клеточный автомат в трех состояниях (слабое, сильное, а не ребро), идущий к завершению, и мы могли бы векторизовать / распараллелить каждый проход. См. Test / correctness / gameoflife.cpp в репозитории Halide для примера. Я думаю, что этот способ будет иметь паршивую вычислительную сложность. Вы будете работать с каждым пикселем, а не только с живым краем переворачивающихся пикселей.

Вы также можете запустить его в качестве сотового автомата, который выполняет обновления на месте вдоль некоторого волнового фронта, например, совершает развертку сверху вниз, снизу вверх, слева направо и справа налево. Затем вы можете векторизовать вдоль волнового фронта. Расписание будет аналогично IIR (см. https://github.com/halide/CVPR2015/blob/master/RecursiveFilter/IirBlur.cpp). Этот подход будет обрабатывать линейный край вдоль любого направления, но любое фиксированное число разверток будет пропускать спираль, переходящую от слабой к сильной.

Но вместо того, чтобы искажать ваш код этими способами, я бы просто использовал другой алгоритм или использовал define_extern.