Comments 22
Так надо было в заголовке так и писать. Нахрена мне читать гору расчётов если это не 0(1). Любая студентота напишет алгоритм с О(n) для центра масс
Интересная статья и идея. У вас уже есть реализация? Было бы очень интересно увидеть результы сравнения с другими реализациями.
В целом, на мой взгляд, интегральные изображения ― один из самых недооцененных алгоритмов.
Может оно и так. Но для трёх измерений получаются просто запредельные объёмы интегральных изображений, а т.к. для вычислений требуется прыгать в разные их части, то это очень негативно сказывается на скорости вычислений, особенно на GPU.
Ещё интересен вопрос точности. Мне в аналогичной ситуации, при суммировании даже точности double не хватило. Пришлось алгоритм Кохена использовать.
Я несколько озадачен. Кажется, однократный проход по матрице MxN — это О(MxN), а не О(1), как в статье. Или я что-то упустил?
Потом при получении суммы — просто прибавляете среднее значение необходимое количество раз. Такой трюк особенно полезен для картинок, где значения обычно от 0 до 255 и интегральные значения растут до невообразимых высот :) Если эе сместить range пикселей к интервалу -128...127 интегральное значение будет бегать около нуля, что в случае floating-point значений сильно улучшает точность.
Но вообще говоря, в image processing community, интегральные изображения давно отошли на задний план. С недавним прогрессом в Convolutional Neural Networks все эти ручные оптимизации и алгоритмические потуги постепенно сходят на нет. Самая тупая нейро-сетка справляется с задачами гораздо лучше чем алгоритмы, разрабатываемые десятками лет. Я думаю и вам нужно смотреть в том-же направлении.
С недавним прогрессом в Convolutional Neural Networks все эти ручные оптимизации и алгоритмические потуги постепенно сходят на нет.
В тех местах, где можно задавить задачу вычислительной мощностью и памятью. Большинство задач до сих пор решаются на изображениях смешного разрешения требуя при этом невменяемой памяти и специализированного железа, которого чаще нет чем есть.
И да, сетки и интегральные изображения можно скрещивать, как в работе вот этих ребят где они добиваются более быстрого инференса за счет этих самых интегральных исзображений.
Спасибо за статью, было интересно почитать про подход.
На картинке, где сравнивается методы аппроксимации функций гравитации, хотелось бы увидеть еще катринку с честно просчитаной гравитацией. Она вообще сильно отличается от интегральной со взвешенными координатами? У меня такое подозрение, что отличия должны быть, т.к. на картинке все-таки заметны концентрические окружности, которых скорее всего не должно быть на честно просчитаной картинке.
Я понял, что мы переходом в центр масс мы поднимаем точность до квадратичной, так как убиваем дипольный момент. А не знаете какого-нибудь способа хоть как-нибудь посчитать квадрупольный тензор, чтобы поднять точность до куба? Понятно, что в лоб не вариант, там сложность будет квадрат от числа элементов в секторе. Но может есть какие-нибудь фокусы?
Вычисление интегрального изображения — это просто суммирование по строкам, транспонирование, еще одно суммирование по строкам и еще одно транспонирование.
Решение дифференциальных уравнений — это алгоритм RK4, и в абсолютном отношении оно примерно вчетверо сложнее вычисления интегрального изображения.
Вычисление центра масс за O(1) с помощью интегральных изображений