Быстрый алгоритм для многолинейных интегралов по двумерной дискретной функции

Question

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

У меня есть изображение I и его градиентное изображение G. Я хочу вычислить интеграл прямой из двух произвольных точек a и b в изображении абсолютного значения G. Очевидно, что я могу перешагнуть черту (1-т ) a + t * b, t в [0, 1] и суммируем, учитывая правильный размер шага t. Однако я хочу сделать это несколько миллионов раз, поэтому мне нужна некоторая ускоряющая структура, которая предпочтительно не требует, чтобы я запускал цикл для каждой пары (a, b).

Кто-нибудь знает существующий алгоритм для выполнения подобных задач?

Answer 1

Вы, кажется, знаете свою математику, поэтому я предложу алгоритм адаптивной квадратуры .

Чаще всего он используется для эффективного вычисления простых 2D-интегралов, но вы, вероятно, сможете использовать его для своей работы.

Answer 2

Я думаю, что ответ - нет. Если бы вы интегрировали градиент, а не его абсолютное значение, это было бы тривиально.

У меня была бы другая проблема: как вы интерполируете на G? У вас будут значения в пикселях, а точки выборки, которые вы будете использовать для вычисления интеграла, обычно не попадают точно в пиксели. Подойдет либо «выбрать значение ближайшего пикселя», либо «интерполировать между четырьмя соседями». Последний точнее, первый быстрее.

С | G | скорее всего не будет гладким, у вас не будет выбора, кроме (дорогого) трапециевидного правила для интеграции.

РЕДАКТИРОВАТЬ: Посмотрите на алгоритм Брезенхэма . Поскольку вы не будете интерполировать, это должно обеспечить полезную оптимизацию.