Как лучше всего улучшить время выполнения алгоритма бикубической интерполяции?

Я разрабатываю программное обеспечение для обработки изображений на С++ на Intel, которое должно снова и снова запускать алгоритм бикубической интерполяции на небольших (около 1kpx) изображениях. Это занимает много времени, и я стремлюсь ускорить его. Сейчас у меня есть базовая реализация, основанная на литературе, несколько улучшенная (с точки зрения скорости) версия, которая не выполняет умножение матриц, а использует предварительно вычисленные формулы для частей интерполирующего многочлена и, наконец, фиксированный -точечная версия кода умножения матриц (на самом деле работает медленнее). У меня также есть внешняя библиотека с оптимизированной реализацией, но она все еще слишком медленная для моих нужд. Далее я рассматривал следующее:

  • векторизация с использованием потоковой обработки MMX/SSE как в версиях с плавающей, так и в фиксированной запятой
  • выполнение интерполяции в области Фурье с использованием свертки
  • перенос работы на графический процессор с использованием OpenCL или аналогичного

Какой из этих подходов может дать наибольший прирост производительности? Не могли бы вы предложить другой? Спасибо.


c++ performance interpolation image-processing bicubic
person neuviemeporte    schedule 28.01.2011    source источник
comment
Насколько медленно мы говорим? Медленно, потому что вы много раз выполняете относительно быструю операцию или потому что она намного медленнее, чем вы ожидаете?   -  person Neil    schedule 28.01.2011
comment
Я полагаю, что это относительно быстро, но мне нужно делать это МНОГО раз. Внешняя библиотека работает примерно за 27 мкс (с SSE), моя лучшая реализация тянет около 50 мкс.   -  person neuviemeporte    schedule 28.01.2011
comment
Если вы используете GPU, что вы делаете с выводом алгоритма, нужно ли будет возвращаться к основной памяти, которая сама по себе может быть узким местом?   -  person Chris O    schedule 28.01.2011
comment
О какой внешней библиотеке вы говорите? Также является ли изображение 1k px размером 100x10 или 1000x1000?   -  person Dat Chu    schedule 28.01.2011
comment
Я использую библиотеку OpenCV. Что касается размера изображения, я имел в виду всего 1000 пикселей. Обычно они квадратные, то есть размером 32х32.   -  person neuviemeporte    schedule 28.01.2011
comment
вы интерполируете в обычную сетку, 32x32 -> n x n ? или как ?   -  person denis    schedule 29.01.2011
comment
Я интерполирую нерегулярные координаты в более крупном (обычно 1024x768) изображении в обычное изображение 32x32. Нерегулярные координаты получаются из формулы, создающей карту деформации (сопоставление каждой из обычных точек 32x32 с нестандартными местоположениями на исходном изображении, которые необходимо интерполировать). Это проясняет? Я смущен. ;)   -  person neuviemeporte    schedule 30.01.2011

Ответы (4)


arrow_upward
5
arrow_downward

Я думаю, что GPU — это путь. Это, наверное, самая естественная задача для такого типа железа. Я бы начал с изучения CUDA или OpenCL. Старые методы, такие как простые пиксельные/фрагментные шейдеры DirectX/OpenGL, также должны работать нормально.

Некоторые ссылки, которые я нашел, может быть, они могли бы помочь вам:

person detunized    schedule 28.01.2011

arrow_upward
3
arrow_downward

Существуют библиотеки Intel IPP, которые используют SIMD для внутреннего использования. для более быстрой обработки. Intel IPP также использует OpenMP, если он настроен, вы можете получить выгоду от относительно простой многопроцессорности.

Эти библиотеки поддерживают бикубическую интерполяцию и являются платными (вы покупаете лицензию на разработку, но распространяете бесплатно).

person Chris O    schedule 28.01.2011
comment
+1: теперь вы получаете лицензию IPP при покупке компилятора Intel ICC (и нет проблем с лицензированием во время выполнения). Только ICC должен дать некоторое улучшение производительности по сравнению с gcc или Visual Studio, и IPP определенно будет первым, что нужно попробовать, прежде чем писать собственный код SIMD. - person Paul R; 28.01.2011
comment
@Paul R, спасибо за отличный совет, я серьезно посмотрю на этот компилятор. - person Chris O; 28.01.2011
comment
@ChrisO Я вижу, что IPP поддерживает кубическую интерполяцию, но не бикубическую. Считаются ли они одинаковыми? - person johnildergleidisson; 07.07.2014
comment
@JoaoMilasch Да, я считаю, что бикубический и кубический - это одно и то же понятие, если вы посмотрите на рис. B-2 в ippiman.pdf, вы увидите использование кубических многочленов в двух измерениях. - person Chris O; 09.07.2014

arrow_upward
3
arrow_downward

Будьте осторожны, выбирая маршрут GPU. Если ваше ядро ​​свертки слишком быстрое, вы в конечном итоге будете привязаны к вводу-выводу. Вы не будете знать наверняка, какой из них самый быстрый, если не реализуете оба.

В GPU Gems 2 есть глава о быстрой фильтрации текстур третьего порядка, которая должна быть хорошая отправная точка для вашего решения GPU.

Сочетание Intel Threading Building Blocks и инструкций SSE может стать достойным решением для ЦП.

person Krypes    schedule 28.01.2011

arrow_upward
0
arrow_downward

Не ответ для бикубического, но, возможно, альтернатива:
если я вас понимаю, у вас есть изображение 32 x 32 xy, 1024 x 768, и вы хотите интерполировать image[xy].
Простое округление xy, image[ int( xy )], было бы слишком зернистым.
Но подождите, вы можете сделать сглаженное двойное изображение 2k x 1,5k, один раз, и взять
image2[ int( 2*xy )]: менее зернистый, очень быстрый. Или аналогичным образом
image4[ int( 4*xy )] на сглаженном изображении 4k x 3k.
Насколько хорошо это работает, зависит от...

person denis    schedule 04.02.2011
comment
На самом деле все наоборот; У меня есть изображение 1024x768, и я хочу создать интерполированное xy 32x32 на основе неравномерно распределенных точек данных из изображения. - person neuviemeporte; 07.02.2011
comment
да, изображение [xy] 32x32 от изображения. Рассмотрим 1d, 32 значения в x0 .. x31 из 1k точек: если вы хотите интерполировать много разных xy из одного изображения (это ваш случай?), сделайте плавное увеличение изображения один раз, до 2k или 4k, и возьмите 32 значения от xy округляются до целых. Они быстро сэмплируют исходное изображение с размером половины/четверти пикселя. - person denis; 08.02.2011