Параллельная. организация расчетов по методу билинейной интерполяции в графических задачах
Технологический институт ВНУ имени В. Даля (г. Северодонецк)
В подсистемах компьютерной графики интерактивных информационных систем часто возникают задачи геометрического преобразования и, в частности, масштабирования растровых изображений. При этом, модифицированное изображение включает в себя различного рода искажения, связанные с округлением результирующих координат точек. Как правило, такие искажения устраняются методами низкочастотной фильтрации или с использованием различных интерполяционных методов. Метод билинейной интерполяции является наиболее простым, хотя для построения качественных изображений используется относительно редко. Но для простейших задач визуализации его можно использовать.
В разрабатываемом алгоритме можно выделить несколько положений, позволяющих ускорить процесс обработки.
Используем интерполяционный метод для расчета яркости точек при движении по узлам сетки вдоль сканирующей строки результирующего изображения с проекцией её на исходное изображение (рис.1).
Точки F определяют растровую решетку исходного изображения, а точки G – результирующего изображения. При этом важно знать коэффициент удаления точки G от узлов пересекаемого квадрата, в рамках которого они будут определять относительные координаты, нормированные от 0 до 1.
Рисунок 1 - Отображение координат точек результирующего изображения на исходное
Ускорить работу метода можно учитывая цикличность перерасчета по аналогии с методом пядей [1]. Перерасчет относительных координат точки выполняем только для первой неповторяющейся последовательности и сохраняем их в выделенной для этого таблице, далее просто используем полученные коэффициенты, так как наклон линии сетки остается неизменным. Таким образом экономится время и вычислительные ресурсы при расчете последующих значений координат.
В процессе выполнения билинейной интерполяции, параллельно рассчитываем яркость в опорных точках. Рационально рассчитывать на многоядерной структуре, т. к. в распределенной структуре процесс обмена данными занимает много времени.
Другой вариант использования параллелизма – одновременная обработка нескольких точек (или в одной строке, или в параллельных строках).
Обрабатывать сразу несколько строк. (до 1024 в одном процессоре).
При этом есть возможность параллельно рассчитывать яркость в искомых точках и для этого рационально использовать многоядерные структуры, потому что при распределенной структуре процесс обмена данными займет много времени по сравнению с основной работой. Например, используем технологию Open MP [2], открытый стандарт для распараллеливания программ на языках Си, Си++ и Фортран, описывающий совокупность директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров не обязательно должно быть больше или равно количеству потоков). Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка — прагм. Количество создаваемых потоков может регулироваться как самой программой при помощи вызова библиотечных процедур, так и извне, при помощи переменных окружения. Можно так же использовать для параллельного расчета библиотеку Intel Threading Building Blocks (также известная как TBB) — это кроссплатформенная библиотека для параллельного программирования, реализованная на языке С++[3]. Библиотека является коллекцией шаблонов классов и функций для параллельного программирования. В библиотеке реализованы: параллельные алгоритмы: for, reduce, do, scan, while, pipeline, sort; потокобезопасные контейнеры: вектор, очередь, хеш-таблица; масштабируемые распределители памяти; мьютексы; атомарные операции; глобальная временная метка; планировщик задач. Кроме того, библиотека обеспечивает совместимость с различными архитектурами и операционными системами. Благодаря библиотеке Intel TBB [4], разработчики получают преимущества в виде ускорения работы, увеличения масштабирования производительности и упрощения поддержки кода. Универсальность библиотеки Intel TBB состоит в том, что она включает набор компонентов, необходимых для реализации параллельного кода с учетом потребностей будущего - производительность приложений автоматически повышается при увеличении количества ядер процессора, а так же библиотека работает с разнообразными ОС и платформами. Оценка возможности использования тех или иных библиотек параллельного программирования - отдельная задача, не являющаяся предметом данной работы.
Выводы. Рассмотренные в работе проблемы позволяют утверждать, что использование параллельной обработки графической информации является рациональным и возможным даже при решении таких задач нижнего уровня логической модели процесса обработки как расчет яркости отдельных пикселей с использованием интерполяционных методов.
Литература:
1. Boyer, V. Auto-adaptive step straight-line algorithm / Boyer, V.; Bourdin J.-J.// Computer graphics and Applications, IEEE, Vol.20, Iss.5, 2000, p(s).67-69.
2. Википедия : OpenMP [Електронний ресурс] - http://ru.wikipedia.org/wiki/OpenMP
3. Википедия : Intel Threading Building Blocks [Електронний ресурс] - http://ru.wikipedia.org/wiki/Intel_Threading_Building_Blocks
4. Компоненты Intel® Threading Building Blocks (Intel® TBB) [Електронний ресурс] - http://software. /ru-ru/articles/intel-tbb/
