Theoretical Analysis of the Hilbert Curve Efficiency for Sliding Filter Image Processing

Arzumanyan Roman Vadimovich graduate student, Department of Intellectual and Multiprocessing Systems, Institute of Computer Technology and Information Security, Southern Federal University 347922, Russia, Rostovskaya oblast', g. Taganrog, ul. Chekhova, 2 roman.arzum@gmail.com Other publications by this author

Sukhinov Aleksandr Ivanovich Doctor of Physics and Mathematics Vice-Rector for Research and Innovation, Don State Technical University 344010, Russia, Rostovskaya oblast', g. Rostov-Na, pl. Gagarina, 1 sukhinov@gmail.com Other publications by this author

Введение. В последнее десятилетие наметились изменения в темпах прогресса в вычислительной технике – переход от экстенсивного роста частот к интенсивному наращиванию мощности ^[1] путём горизонтального масштабирования вычислительных систем. В этой связи, всё большее значение приобретает разработка локальных алгоритмов – тех, которые бы использовали для передачи данных низкоуровневые быстрые локальные каналы передачи данных ^[2,3]. Это необходимо потому, что скорость обмена информацией значительно ниже, чем скорость её обработки на современных компьютерах ^[4,5]. Ускорители вычислений с архитектурой массового параллелизма особенно нуждаются в таких алгоритмах, поскольку массовые обращения к глобальной памяти на таких устройствах приводят к значительным просадкам производительности ^[6]. Кривая Гильберта (далее КГ) является частным случаем кривой, заполняющей пространство. Впервые класс подобных кривых был рассмотрен в работе Пеано ^[7] в 1890 г. Пространственные кривые, заполняющие пространство можно рассматривать как непрерывное отображение . При этом – образ в , имеет положительную Жорданову меру (площадь для двумерного случая). Несмотря на первенство Пеано, именно в работе Гильберта ^[8] в 1891 г. был предложен обобщённый алгоритм построения подобного класса кривых. Отметим то, что Гильбертом был рассмотрен случай . Обобщение для трёхмерного случая было дано в работах ^{[9, 10]}. Примечательно то, что первоначально рассматривалось применение пространственных многомерных кривых в общем, и кривой Гильберта в частности для сжатия многомерных данных ^{[11, 12]}. В работах ^[13,14] был описан алгоритм построения кривой, ориентированный на его компьютерную реализацию, параметризованный по числу бит в байте и длине машинного слова. Свойство пространственной локальности КГ было рассмотрено в работе ^[15], где было произведено сравнение КГ с другими пространственными кривыми, такими как кривая Пеано и Z-кривые. По ряду метрик, предложенных авторами упомянутых работ, КГ оказывается наиболее предпочтительной. Дадим формальное определение КГ для двумерного случая: для через будем обозначать КГ -го порядка. отображает . На плоскости, можно получить из заменой каждой вершины в на . Поскольку в число вершин равно , то в будет вершин. В работе ^[15] был проведён асимптотический анализ свойства пространственной локальности КГ для общего случая и . Воспользуемся следующим определением из упомянутой работы: Кластером в заданной области будем называть группу точек расчётной области, которые можно последовательно соединить кривой. Количество кластеров в заданной области равно числу входов (выходов) КГ в эту область. Одной из важных гипотез работы ^[15] является предположение о зависимости числа кластеров от Жордановой меры расчётной области. В дальнейшем, в упомянутой работе доказывается, что распределение граней всех возможных различных ориентаций носит равномерный характер. Применительно к рассматриваемому в данной работе случаю, это означает что вертикальные и горизонтальные переходы между точками расчётной области при совершении очередного шага вдоль КГ равновероятны. В дальнейшем, в данной работе мы неоднократно будем обращаться к данному свойству кривой. Подробно доказательство этого утверждения было изложено в работе ^[16].

Цель работы. Цель данной работы – дать теоретическое объяснение эффективности применения КГ для задач обработки изображений фильтрами со скользящим окном, при условии применения упомянутой кривой для обхода точек изображения. Практическая эффективность подобного подхода была показана в предыдущих работах ^{[14, 17]}, однако теоретическое обоснование подобного эффекта не было рассмотрено достаточно подробно.

Постановка задачи. Для простоты обозначений, будем рассматривать изображения с соотношением сторон 1:1 и фильтры с квадратным скользящим окном. Пусть – множество точек изображения размера пикселов. – у каждой точки изображения есть окрестность внутри окна фильтра размера . Пикселы изображения хранятся внутри памяти построчно: . Будем считать, что вычислитель, обрабатывающий изображения, имеет write-through кэш данных. Кэш разбит на линии, размер которых сопоставим с количеством данных в одной строке пикселов в пределах окна фильтра. На практике наиболее распространены кэши данных с размером линии 64 байта, что хорошо подходит под описание вычислителя.

Основная часть. Рассмотрим группу точек изображения. Число точек в группе будем полагать равным . На 4.2 показан пример группировки точек и порядок их обхода. На примере кривой 4го порядка, рассмотрим то, как располагаются на плоскости группы точек вдоль кривой. Так, возможно сгруппировать 16 точек в прямоугольники со сторонами 1×16, 2×8 и 4×4. Для заданного порядка , периметр прямоугольника, содержащего точки, будет однозначно определять размеры сторон. Проще всего показать это в двоичном виде. - площадь прямоугольника со сторонами . Через обозначим полупериметр. ∃ВОС :

Если представить P в двоичном виде, то единичные биты будут располагаться на местах:

однозначно определяются из :

в том случае, если единичные биты в двоичном представлении находятся на позициях соответственно, и

в том случае, если в двоичном представлении один единичный бит находится на позиции . Обратим внимание ещё на одно свойство: приращение площади прямоугольника, содержащего фильтруемых точек изображения, имеет прямую зависимость от периметра прямоугольника. Это несложно показать: - полупериметр прямоугольника. Тогда площадь , где - длина стороны. При увеличении периметра на величину , площадь будет равна .

Из этого следует, что прямоугольник с наименьшим периметром при заданной площади (квадрат) даёт наименьшее приращение площади при увеличении периметра. Физический смысл этого утверждения таков: при использовании фильтров со скользящим окном, приращение периметра равно размеру окна фильтрации. Если сгруппировать фильтруемые пикселы в квадрат, то нужно будет прочесть из памяти минимально возможное количество пикселов из окрестности для фильтрации. Данное свойство очень важно, поскольку производительность многие алгоритмов обработки изображений ограничена быстродействием памяти. Уменьшение числа чтений для таких алгоритмов позволяет повысить их производительность. Таким образом, кривая Гильберта обладает следующими свойствами, важными для применения её в качестве порядка обхода точек изображения:

· Кривая Гильберта группирует точек, где - чётное число в квадрат со стороной . А значит, такая группа потребует чтения минимально возможного числа пикселов из окрестности.

· Если порядок кривой - чётное число, то она группирует точек, где - нечётное число в прямоугольник с шириной и высотой .

· Если порядок кривой - нечётное число, то она группирует точек, где - нечётное число в прямоугольник с высотой и шириной .

· При большом порядке кривой, количество вертикальных и горизонтальных переходов можно считать равным. Точные формулы для расчёта числа переходов: горизонтальных переходов и вертикальных переходов.

Для любого фильтра с окном размера нужно на каждом шаге после первого обхода расчётной области прочесть из памяти не более пикселов при смещении по горизонтали, и столько же пикселов при смещении по вертикали. Данное свойство кривой так же важно с точки зрения минимизации числа обращений к памяти, поскольку оно даёт оценку сверху для точного числа чтений на каждом шаге обхода расчётной области. В том случае, если процессор имеет SRAM (быстродействующая память на кристалле), возможна загрузка минимально необходимого числа пикселов из памяти для каждой точки изображения. На 4.3 проиллюстрировано это свойство. Сравним с аналогичным числом пикселов для растрового порядка обхода. На 4.4 показано, что при проходе вдоль строки, каждый раз необходимо читать из памяти пикселов, однако при переходе с одной строки на другую, необходимо прочесть все пикселы из окна фильтра заново в том случае, если загруженные пикселы для начала строки были вытеснены из кэша. Дадим оценку того, сколько пикселов из области окна фильтра необходимо будет прочесть для выполнения фильтрации изображения. При растровом обходе точек изображения, необходимо будет прочесть пикселов при переходе на новую строку, и пикселов при обходе строк. В случае обхода точек вдоль кривой Гильберта, нужно будет прочесть пикселов. Разница будет равна:

Приведём оценку числа пикселов, которые не нужно читать при обходе точек вдоль кривой Гильберта, по сравнению с растровым порядком обхода. Данные приведены для изображения размером 1024×1024 пиксела.

Так, из Таб. 1 видно, что для фильтров со скользящим окном размера 8х8 и 16х16, выигрыш составляет от 5.5% до 23.44% от общего числа точек изображения. Для того, чтобы избежать загрузки пикселов при переходе на новую строку, достаточно использовать непрерывный порядок обхода точек изображения, на каждом шаге которого происходит смещение на одну точку либо по вертикали, либо по горизонтали. Для сравнения с КГ, рассмотрим два таких простейших порядка обхода. Первый из них предусматривает обход порядок обхода строк (например, чётные строки обходим слева направо, нечётные – справа налево). Подобный порядок обхода будем называть чередованием по строкам. Второй порядок обхода точек аналогичен первому с тем лишь отличием, что обход производится по столбцам. Его для краткости будем называть чередованием по столбцам.

Таблица 2: сравнение числа горизонтальных и вертикальных переходов при обходе точек изображения

В таблице 2 приведены оценки для числа горизонтальных и вертикальных переходов для описанных ранее порядков обхода точек изображения размера пикселов. Через обозначено число горизонтальных переходов, через – число вертикальных переходов. Для вычислителя с загрузкой данных через построчный кэш, горизонтальные и вертикальные переходы создают различный тип нагрузки на шину памяти. Так, при загрузке пикселов строки, происходит чтение числа байт, равного размеру кэш-линии. После того, как данные для скользящего окна загружены, в момент горизонтального перехода фактического чтения из памяти не происходит в том случае, если размер кэш-линии больше размера окна фильтра. Последовательность чтений будет выглядеть следующим образом: Данный тип нагрузки хорош тем, что повышает число повторных использований загруженных ранее данных. Недостаток данного подхода таков, что чтения длятся долго, и конвейер вычислителя может простаивать сотни тактов в ожидании данных из памяти. Напротив, при вертикальном переходе, чтение происходит построчно, последовательность операций выглядит как При этом возможно «прятать» время вычислений за задержками чтения, но кэш используется хуже в том случае, если размер кэш-линии превышает число данных для пикселов в пределах одной строки окна фильтра. КГ комбинирует оба типа чтений. Необходимо отметить, что в том случае, когда алгоритмы фильтрации при горизонтальном и вертикальном переходе отличаются, на кэш инструкций будет ложиться дополнительная нагрузка.

Кривая Гильберта является частным случаем кривой, при которой возможен непрерывный обход точек изображения, который минимизирует число повторных обращений к памяти за счёт повторного использования ранее загруженных пикселов в пределах окрестности окна фильтра. Свойство минимизации числа повторных обращений к памяти при обработке соседних точек расчётной области будем далее называть свойством локальности. Свойство локальности хорошо подходит для реализации алгоритмов на графических ускорителях с поддержкой вычислений общего назначения (далее GPGPU) – обращения к памяти из соседних потоков будут происходить к соседним адресам. Так как объём кэшей на GPGPU и ускорителях вычислений небольшой, а обращения к памяти - медленные, то использование алгоритмов с хорошим шаблоном доступа к памяти может существенно увеличить производительность. Однако, у предлагаемого способа есть недостаток – вычисление координаты точки по длине кривой в заданной точке является для графического процессора (далее GPU) неподходящей задачей, так как требует последовательных вычислений в цикле ^[13]. Кроме того, за счёт чередования направлений перехода, может падать эффективность использования кэша инструкций в том случае, если алгоритмы фильтрации различны для горизонтального и вертикального переходов. Практическая эффективность применения КГ для обхода точек изображения в задачах фильтрации изображения показана в работе ^[17].

Выводы. В данной работе было произведён анализ свойства пространственной локальности КГ в двумерном случае. Данное свойство определяет эффективность обхода точек изображения вдоль упомянутой кривой при обработке изображений фильтрами со скользящим окном за счёт минимизации числа обращений к памяти и повторного использования ранее прочитанных пикселов в пределах скользящего окна фильтра и чередования вертикальных и горизонтальных переходов между точками изображения в сравнении с другими непрерывными порядками обхода. Так же, дана оценка числа операций чтения из памяти, которых можно избежать при обходе точек изображения вдоль КГ в сравнении с растровой кривой. Было показано, что за счёт равного числа вертикальных и горизонтальных переходов, обход точек изображения вдоль КГ создаёт смешанный тип нагрузки на контроллер памяти в том случае, если чтение данных проходит через write-through кэш вычислителя, разбитый на линии, размер которых сопоставим с объёмом данных для одной строки пикселов в пределах окна фильтра.