Применение параллельных вычислений при расчете признаков в системах автоматического аннотирования изображений

Применение параллельных вычислений при расчете признаков в системах автоматического аннотирования изображений

, д-р техн. Наук, , канд. Техн. Наук, , канд. Техн. Наук,

СТА №2, 2015г.

Аннотация

В статье представлены структуры параллельных вычислений цветовых, текстурных и фрактальных признаков ландшафтных изображений для систем автоматического анноти­рования в сети Интернет. Полученные экспериментальные оценки демонстрируют повышение быстродействия на 26—32%, что является существенным улучшением производительности систем автоматического аннотирования.

Основная часть

В настоящее время поиск и просмотр изо­бражений является обычной функцией Интернета. Однако объем визуальной информации

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

Начало развития поисковых систем от­носится к 1970 г., а именно к их первому по­колению — текстовым поисковым системам (TBIR, Text-Based Retrieval System), в которых текстовый комментарий к изображениям за­носился вручную. Контекстно-зависимые поисковые системы (CBIR, Context-Based Retrieval System) относятся ко второму по­колению, начиная с 1980 г. Они имели более разнообразные функции, например, поиск по цветовым примитивам, форме и простран­ственному положению, поиск абстрактных или конкретных объектов. Третье поколе­ние — системы автоматического аннотиро­вания изображений (AIAS, Automatic Image Annotation System) разрабатываются с 2000 г. В них автоматический поиск изображений осуществляется по аналогии с поиском в тек­стовых документах. Основной идеей систем автоматического аннотирования является автоматическое формирование семантиче­ских концептуальных моделей из обучающей выборки изображений большого объема. Поиск изображений выполняется по ключе­вым словам или так называемым визуальным словам (VW, Visual Word).

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

Базовый дескриптор описания изображений

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

Цветовые признаки

Известны различные цветовые признаки, построенные на основе цветовой гистограм­мы, цветовых моментов, цветового ко­герентного вектора  и других. Отметим, что стандарт MPEG-7 устанавливает такие цве­товые признаки, как доминантный цветовой дескриптор, дескриптор цветового слоя, де­скриптор цветовой структуры и масштабиру­емый цветовой дескрипто.

Наиболее простыми и популярными признаками являются цветовые момен­ты, такие как среднее значение, отклоне­ние и асимметрия. Причем они могут вы­числяться в различных цветовых про­странствах — RGB (Red, Green, Blue), LAB (Lightness, А и В — цветовые компонен­ты, основанные на нелинейном сжатии), LUV (Lightness, Uniform chromaticity scale, Valence), HSV (Hue, Saturation, Value), HSL (Hue, Saturation, Lightness), HMMD (Hue, троHSV как одно из наиболее удобных для сегментации.

Согласно теории моментов, нормализо­ванное среднее |ДС, нормализованное стан­дартное отклонение ас и нормализованная асимметрия 0С (значения указанных параме­тров нормализуются по количеству пикселов в регионе) вычисляются для каждой HSV - компоненты по следующим выражениям:

где Pj — значение пиксела соответствующей цветовой компоненты; NP — количество пик­селов в регионе.

Отметим, что предварительная сегмента­ция изображения выполняется с помощью алгоритма JSEG [8]. В результате для каждого региона будут получены девять цветовых при­знаков FC0, ..., FC8, вычисленные по форму­лам (1)—(3).

Текстурные признаки

Для вычисления текстурных признаков используются признаки Харалика [9], ло­кальные статистические оценки [10], мето­ды, основанные на моментах, спектральные характеристики и многие другие. Для распоз­навания текстур изучались моменты перво­го и второго порядков, а также их произво­дные [11].

Пусть z — случайное значение интенсив­ности, a h(z,), i = 0, 1, 2, (Q - 1) — ее ги­стограмма, где Q — количество уровней ин­тенсивности. Тогда статистические призна­ки нормализованного среднего значения А V, нормализованной дисперсии DS, нормализо­ванной однородности НМ, нормализованной гладкости SM, нормализованной энтропии EN, нормализованной асимметрии SK и нор­мализованного эксцесса KR можно найти по следующим формулам: где SR — площадь региона, ц3 и ц4 — моменты третьего и четвертого порядков, а3 и а4 — стан­дартные отклонения в третьей и четвертой степенях. Все значения, полученные по фор­мулам (4)—(10), нормализованы по площади региона SR.

Семь текстурных признаков (AV, DS, НМ, SM, EN, SK и KR) определены как компо­ненты РТ9, FTi5 в базовом дескрипторе ре­гиона.

Фрактальные признаки

В качестве фрактальных признаков ис­пользуется фрактальная размерность FD, в общем случае вычисляемая по формуле

где N — непересекающиеся и самоподобные копии; г — коэффициент масштабирования копий по координатным осям.

Выражение  трудно, а в некоторых слу­чаях невозможно использовать. В работах показаны способы вычисления фрактальной размерности, пригодные для изображений, а также анализируется лакунарность FL — термин, введенный впервые Мандельбротом. Два фрактальных признака FD и FL являются компонентами FFl6 и FF{1 базо­вого дескриптора региона. Далее на осно­ве полученных значений строится вектор RF = {/Го,..., FCS, FT9,..., FTl5, FFl6, FFX1), ко­торый впоследствии преобразуется в регион дескриптора RD,-,, где / — это счетчик регио­нов в изображении j, a j — счетчик изображе­ний в тестовом наборе.

Вычисление базовых дескрипторов, вклю­чающих 18 признаков, является довольно тру­доемкой задачей, требующей распараллели­вание вычислений.

Виды и среды распараллеливания программного кода

Существуют следующие виды распаралле­ливания программного кода, а именно:

параллелизм данных. Ему соответству­ют задачи, которые включают неоднократ­ное выполнение одного и того же алгоритма с различными исходными данными. Такие вычисления могут производиться параллель­но в случае разделения данных на фрагменты и обработки каждого фрагмента выделенным ядром; функциональный параллелизм. Это параллелизм групп операций, объеди­ненных по функциональному признаку. Распараллеливание выполняется путем функ­циональной декомпозиции. Простейшим примером такой декомпозиции является де­композиция задачи на подзадачи: ввод исход­ных данных, обработка, вывод результатов, визуализация результатов. Параллелизм при этом достигается параллельным выполнени­ем указанных подзадач и созданием «конвейе­ра» (последовательного или последовательно­параллельного) между ними. При этом каж­дая подзадача может обладать параллелизмом данных; алгоритмический параллелизм. К этому типу относится параллелизм, выявляющий в алгоритме фрагменты, которые могут вы­полняться параллельно. Синтез параллель­ных алгоритмов (распараллеливание) на ос­нове алгоритмического параллелизма назы­вается алгоритмической декомпозицией. При использовании алгоритмической декомпози­ции следует стремиться к разбиению задачи на крупные и редко взаимодействующие вет­ви. По возможности должно быть обеспеченооднородное распределение обработки данных по ветвям параллельного алгоритма. Отличие алгоритмического параллелизма от функци­онального состоит в том, что функциональ­ный параллелизм предполагает объединение только функционально близких операторов алгоритма, в то время как алгоритмический параллелизм не учитывает функциональную близость операторов.

Для реализации параллельных алгорит­мов широкое распространение получил стан­дарт ОрепМР  для распараллеливания программ на языках Си, Си++ и Фортран. Помимо него в последнее время развивается расширение языка Си++, названное как Intel Cilk Plus.

Распараллеливание в стандарте ОрепМР выполняется явно при помощи вставки в текст программы специальных директив, а также вызова вспомогательных функций. Стандарт ОрепМР реализует параллельные вычисления с помощью многопоточности, когда «главный» поток создает набор подчи­ненных потоков, между которыми распреде­ляется задача. При этом программа выполня­ется в последовательной области — сначала работает один процесс (поток), при входе в па­раллельную область порождаются несколько потоков, между которыми в дальнейшем рас­пределяются части кода. По завершении па­раллельной области все потоки, за исключе­нием «главного», завершаются и начинается последовательная область. Стандарт ОрепМР поддерживает вложение параллельных обла­стей.

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

Псевдокод базового дескриптора описания изображений

Базовый дескриптор вычисляет цветовые, текстурные и фрактальные признаки в неко­торой окрестности рассматриваемого пик­села. При этом расчет цветовых и текстур­ных признаков по статистическим форму­лам (1)—(10) можно проводить параллельно, в то время как фрактальные признаки требу­ют отдельного расчета. Вычисление цветовых и фрактальных признаков сводится к выпол­нению двух основных этапов. На первом эта­пе происходит сбор статистических данных в окрестности пиксела, когда для цветовых признаков рассчитываются нормализован­ные средние для цветовых каналов по фор­муле (1), а для текстурных признаков фор­мируется локальная гистограмма. На втором этапе происходит непосредственный расчет признаков по формулам (2)—(10). Таким об­разом, алгоритм формирования дескриптора с учетом расчета цветовых и текстурных при­знаков включает два базовых типа циклов — внешний цикл по изображению размером (w/kw)x(h/kh) и вложенные циклы по окрест­ности сегмента, в котором рассматриваются все пиксели, где wwh — ширина и высота изо­бражения; kw и kh — ширина и высота сегмен­та. Алгоритм включает следующие шаги.

Начало алгоритма 1.

Шаг 1. В цикле от 0 до h/kh+ lno Yimg вы­полняем шаг 2.

Шаг 2. В цикле от 0 до w/kw+1 по Ximg вы­полняем шаг 3.

Шаг 3. Инициализация нулевыми значе­ниями массива рядов, строк или блоков (в за­висимости от метода распараллеливания).

Шаг 4. Инициализация нулевыми значе­ниями массива для хранения значений рс.

Шаг 5. В цикле от Yimgx. kh до Yimgxkh+kh по ку выполняем шаг 6.

Шаг 6. В цикле от Ximgx, kw до Ximgxkw+kw по кх выполняем шаг 7.

Шаг 7. Проверка корректности координат кх, ку, в случае успешной проверки выполне­ние шагов 8 и 9.

Шаг8. h[z[kx-,ky]] + +.

Шаг 9. Выполнение итерации расчета нор­мализованного среднего цс для цветовых ка­налов по формуле (1).

Конец цикла шага 6.

Конец цикла шага 5.

Шаг 10. Вычисление итоговых значений цс.

Шаг 11. Вычисление множества цветовых и текстурных признаков RF = {FC0, ..., FCS, FT9, ..., FTIS) в окрестности пиксела (Ximg; Yimg).

Шаг 12. FeatureMap[Ximg\ Yimg] = RF.

Конец цикла шага 2.

Конец цикла шага 1.

Конец алгоритма 1.

Непосредственное вычисление множества цветовых и текстурных признаков (шаг 11) ре­ализовано в виде следующего алгоритма.

Начало алгоритма 2.

Шаг 1. В цикле от Yimgxk,, до Yimgxkh+kh по ку выполняем шаг 2.

Шаг 2. В цикле от Ximgx. kw до Ximgx. kw+kw по кх выполняем шаг 3.

Шаг 3. Выполнение итерации расчета нор­мализованного стандартного отклонения ас по формуле (2).

Шаг 4. Выполнение итерации расчета нор­мализованной асимметрии 0С по формуле (3).

Конец цикла шага 2.

Конец цикла шага 1.

Шаг 5. Вычисление итоговых значений ас и 0С.

Шаг 6. В цикле от 0 до Q — 1 по / выполня­ем шаг 7.

Шаг 7. Выполнение итерации расчета нор­мализованного среднего значения ^(форму­ла (4)), нормализованной однородности НМ (формула (6)), нормализованной энтропии EN(формула (8)).

Шаг 8. Вычисление итоговых значений Л V, НМ и EN.

Шаг 9. В цикле от 0 до Q — 1 по / выполня­ем шаг 10.

Шаг 10. Выполнение итерации расче­та нормализованной дисперсии DS (форму­ла (5)).

Шаг 11. Вычисление итогового значе­ния DS.

Шаг 12. Расчет нормализованной гладко­сти SM (формула (7)).

Шаг 13. В цикле от 0 до Q — 1 по / выпол­няем шаг 14.

Шаг 14. Выполнение итерации расчета нормализованной асимметрии SK (формула (9)) и нормализованного эксцесса KR (форму­ла (10)).

Шаг 15. Вычисление итоговых значений SKhKR.

Шаг 16. Заполнение структуры RF.

Конец алгоритма 2.

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

Для повышения быстродействия алгорит­мов расчета текстурных признаков целесо­образно проводить распараллеливание для внешних циклов прохода по изображению. Для этого в случае ОрепМР необходимо ис­пользовать директиву препроцессора #pragma omp parallel for, а для Intel Cilk Plus — ключевое слово cilk for. Расчеты цветовых и текстурных признаков не взаимосвязаны, поэтому мож­но дополнительно определить параллельные области вычисления отдельно для цветовых и текстурных признаков — шаги 1—5 и шаги 6—15 в алгоритме 2 — вычисление множества цветовых и текстурных признаков.

Заключение

Методы распараллеливания алгоритма вычисления цветовых, текстурных и фрак­тальных признаков на основе разделения изображения на фрагменты позволяют зна­чительно ускорить обработку изображения, обеспечивая псевдореальное время обработ­ки изображения HD-качества. Было выясне­но, что при применении алгоритмов распа­раллеливания быстродействие повышается на 26—32%. Также эксперименты показали, что ускорение обработки с применением сре­ды Intel Cilk Plus в среднем выше на 9—14%. Это связано с тем, что в среде Intel Cilk Plus реализована более эффективная балансиров­ка нагрузки.