Ускорение суммации по отрезкам с использованием пирамиды быстрого преобразования Хафа

В работе предложен алгоритм быстрого приближенного вычисления на изображении сумм по произвольным отрезкам, задаваемым парой пикселей. Используя результаты промежуточных вычислений быстрого преобразования Хафа, предложенный алгоритм позволяет рассчитать сумму по произвольному отрезку линии с логарифмической сложностью, зависящей от линейного размера исходного изображения. Предподсчет реализован как модификация алгоритма Брейди быстрой суммации по диадическим аппроксимациям прямых. При таком подходе ключевым элементом алгоритма является поиск диадической прямой, проходящей через два данных пикселя. В работе предложен алгоритм решения этой задачи, не ухудшающий общую асимптотику, для него доказана корректность. Также в работе описывается обобщение этого подхода на трехмерный случай для отрезков и для сегментов плоскостей.