Алгоритм quick shift на GPU.

Авторы: Brian Fulkerson, Stefano Soatto

Перевел: Комаричев Максим

Источник: http://www.vision.ucla.edu/papers/fulkersonS10really.pdf

Аннотация. В работе представлена реализация на GPU алгоритма сегментации изображений quick shift. Представлены варианты реализации, которые используют глобальную память и кэширование текстур, а также показано, что метод использующий кэширование текстур может давать ускорение в 10 -50 раз для реальных изображений, что делает вычисление суперпикселей возможным на 5-10Гц для небольших изображений (256x256).

Ключевые слова: супер-пиксели, сегментация, CUDA GPU программирование.

Введение

Алгоритмы сегментации сыграли важную роль в исследованиях компьютерного зрения, как в виде конечной цели [1-3], а в последнее время и в качестве предварительного этапа в других областях, в том числе стерео [4] и анализе сцены на уровне категорий [5, 6]. Разбиение изображения на меньшие компоненты, обычно называемые суперпикселями, позволяет алгоритмам рассматривать изображение как набор значимых частей вместо обработки отдельных пикселей.

К сожалению, зачастую алгоритмы сегментации требовательны как к объему памяти, так и к вычислительным ресурсам. Это ограничивает масштабы применения алгоритмов и области, в которых они могут быть использованы.

В этой работе мы показываем, что GPU реализация алгоритма quick shift [3] может повысить производительность уже (относительно) быстрого алгоритма сегментации в 10-50 раз, открывая множество новых потенциальных приложений, таких как «понимание» сцен в видео, а также улучшить реальную абстракцию времени в видео [7].

Подобные работы

Большинство подобных работ, в которых GPU использовалось для сегментации, относятся к медицине, где наличие дополнительного измерения данных (трехмерные данные, а не двумерные), обусловило высокие требования к скорости алгоритма [8-11]. Примером применения вне медицины является работа Catanzaro и др. [12], в которой была адаптирована техника обнаружения границы (gPb [13]) для GPU. Хотя gPb могут быть использованы для сегментации [14], наша реализация быстрого сдвига в десять раз быстрее на аналогичном оборудовании.

Основанные на GPU детекторы и трекеры [15,16] были предложены, как компоненты, требующие обучения, такие как метод опорных векторов [17] или алгоритм k-ближних [18]. Недавно Wojek и др. [19] предложил использовать схему скользящего окна для категоризации, ускоренную с помощью GPU.

Другие недавние достижения в использовании GPU для машинного зрения включают библиотеки общего назначения, такие как OpenVIDIA [20], а также специфические приложения, зачастую направленные на детектирование движения [21] и фильтрацию частиц [22].

Carreira и др. [23] выполнили работу по аппроксимации Гауссового среднего сдвига (Gaussian Mean Shift, GMS) за счет уменьшения общего количества итераций и стоимости каждой итерации (путем аппроксимации плотности). Мы избежали необходимости уменьшения количества итераций, поскольку алгоритм quick shift имеет лишь одну итерацию. Вместо аппроксимации плотности мы просто использовали параллелизм для ускорения, используя аппаратные ресурсы (GPU). Мы отметили, что можно было также аппроксимировать и плотность как в [23] и это привело бы к еще большему ускорению.

Алгоритм Quick shift

Quick shift это ядерная версия алгоритма mode seeking, похожего по принципу на mean shift [2, 24] или medoid shift [25]. Даны N точек , он вычисляет оценку плотности по Парцену (Parzen) вокруг каждой точки, например, используя изотопическое окно Гаусса:

.

Как только оценка плотности P(x) получена, quick shift соединяет каждую точку с каждой ближайшей точкой, имеющей наибольшую плотность. Каждое соединение имеет расстояние , ассоциированное с ним, а также множество соединений с другими пикселями образует дерево, корнем которого является точка с наибольшей оценочной плотностью.

Quick shift может быть использован в любом пространстве признаков, но в данной работе рассматривается работа с «сырыми» данным RGB и координатами (x, y) на изображении. Итак, рассматриваемое пространство признаков имеет пять измерений (r, g, b, x, y). Для того, чтобы сгладить различия между значимостью цветовой и пространственной составляющей, мы просто масштабируем знаения (r, g, b) с помощью параметра , который для наших экспериментов имеет значение .

Для получения сегментации из дерева, сформированного алгоритмом quick shift, мы выбираем пороговое значение и разрываем все связи в дереве, где . Пиксели, образующие деревья после разбиения, образуют искомую сегментацию.

Специфические оптимизации для сегментации

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

Во-первых, когда вычисляется энергия, мы можем ограничить область пикселей, попадающих в окно, меньшее 3σ пикселей, потому что вне его распределение плотности будет гарантировано невысоким. Во-вторых, при соединении соседей, естественным образом образуется граница для окна поиска, потому что пиксели, находящиеся далее чем на в плоскости изображения, должны быть как минимум на столько же удалены в пространстве признаков. Концептуально, мы поговорим о вычислении плотности и процессе связывания как о независимых частях алгоритма, потому что один из них (вычисление плотности) предшествует другому и они оба оперируют различными наборами данных. Псеводкод реализации показан на рисунке 2, а сегментации, с разными параметрами на рисунке 1.

Quick shift на GPU

Поскольку quick shift работает с каждым пикселем изображения, а проводимые вычисления независимы, это является хорошей предпосылкой для использования параллельной архитектуры.

Мы использовали CUDA 3.0 для разработки первой реализации, которая просто копирует изображение на устройство и разбивает вычисление плотности и соседей на блоки для обработки на GPU.

Несмотря на то, что этот вариант быстрее чем реализация для CPU, узким местом остаются задержки при работе с памятью. Глобальная память на GPU медленная, требует сотен циклов для доступа, а для каждого пикселя quick shift требует доступа к соседям.

В качестве решения этой проблемы была предпринята попытка загружать в общую память множество пикселей, окружающих блок, таким образом, что когда вычисляется схожесть элемента в блоке с элементом вне его, то обращение к памяти кешируется. В любом случае, поскольку эта операция не всегда легко разделима, потребность в общей памяти растет квадратично вместе с . Даже небольшие значения быстро исчерпают 16000 байт общей памяти, доступной на современных GPU.

Поэтому мы отобразили изображение и оценочную плотность в трех- и двухмерные текстуры соответственно. В этом случае каждый поток получает доступ к блоку пикселей вокруг него. Результаты, основанные на этом подходе кеширования текстур, помечены суффиксом «Tex» в следующем разделе.

Оценка

Необходимо оценить два аспекта алгоритма — качество и время, затрачиваемое на сегментацию. Чтобы оценить качество реализации на GPU, мы сравнили энергию и сегментацию с одной из доступных публично реализаций quick shift в VLFeat [26].

Для замеров скорости алгоритма, мы случайным образом выбрали несколько изображений из набора PASCAL-2007 (рис. 3). Изображения обрезаны до разрешения 1024х1024. Все приведенные показатели производительности получены усреднением результатов, полученных при работе со всеми изображениями.

Мы исследовали влияние каждого параметра, изменяющего время работы алгоритма. Во-первых, на рисунке 4 показана производительность алгоритма при увеличении разрешения изображения, при неизменных и . Далее, на рисунке 5 мы установили разрешение изображения на 512х512, зафиксировали и изменяли ; отображено влияние на время работы алгоритма. На рисунке 6 зафиксированы значения разрешения изображения и и, в этом случае, изменяется , показывая время, необходимое для связывания соседей.

Аппаратное обеспечение. В качестве CPU использовался 2.4Ghz Core 2 Duo. Для GPU реализации использовались 2 видеокарты — GeForce 869M GT и GeForce 9800 GT. 8600M GT имеет 4 мультипроцессора, 32 ядра и тактовую частоту 475MHz. 9800 GT имеет 14 мультипроцессоров, 112 ядер и тактовую частоту 550MHz. Из-за ограничений на время выполнения ядра CUDA на 8600M, на рисунке 5 и 6 не показаны результаты для самого медленного случая. Хотим отметить, что новое аппаратное обеспечение (например карты, основанные на недавно вышедшей архитектуре FERMI) несомненно могут быть быстрее, однако мы хотели показать, что возможно при ограниченных вложениях в аппаратное обеспечение.

Для обоих исследуемых GPU мы использовали размер блока 16х16, даже если подбор размера под конкретный GPU мог дать прирост производительности.

Наш исходный код доступен на нашем сайте http://vision.

ucla.edu/~brian/gpuquickshift.html.

Заключение

Мы представили реализацию алгоритма quick shift для GPU, которая позволяет получить ускорение по сравнению с версией для CPU в 10-50 раз, для результирующего алгоритма супер-пикслеизации, который может работать на аппаратуре с частотой 10Hz для изображений с разрешением. Данная реализация является точной копией алгоритма quick shift и может быть еще ускорена при помощи аппроксимации плостности, посредством подвыборки или другими методами.

Рисунок 1. Пример результатов quick shift.

Рисунок 2. Алгоритм quick shift для изображения. Псевдокод. Алгоритм выполняет обработку в два шага. На первом он обходит изображения, вычисляя оценочную плотность по Парцену (Parzen) для каждого пикселя. После этого он связывает каждый пиксель с ближайшим (в пространстве признаков), который увеличивает оценочную плотность.

Рисунок 3. Изображения для экспериментов. Четыре изображения из PASCAL-2007, использованные для измерения скорости предложенного алгоритма.

Рисунок 4. Сравнительная характеристика quick shift на CPU и GPU. Этот график показывает зависимость времени на разных GPU в зависимости от разрешениея изображения. Результаты усреднены по четырем изображениям из PASCAL-2007, показанных на рисунке 3. Для этих данных и . При разрешении 1024х1024 достигнуто ускорение в 54 раза по сравнению с версией для CPU.

Рисунок 5. Влияние на время расчета плотности. На рисунке 4 мы показали, что при увеличении время обработки увеличивается, а использование варианта алгоритма с кешированием даёт наилучшие результаты. Здесь мы установили значение , разрешение изображения 512х512. Результаты, усредненные для тех же четырех изображений как и выше.

Рисунок 6. Влияние на время соединения соседей. Мы показали, что по мере роста временные затраты на поиск ближайшего соседа, увеличивающего оценку плотности, увеличиваются. Здесь мы установили значение , а разрешение изображения 512х512. Результаты усреднены для тех же четырех изображений, что и выше.