Українська   English
ДонНТУ   Портал магистров

Содержание

Введение

Компьютерная обработка и распознавание объектов на изображениях–одно из интенсивно развиваемых отраслей современной компьютеризации. Распознавание 3D объектов по 2D изображениям является одной из важнейших задач анализа сцен и компьютерного зрения. Базовую информацию для распознавания содержат в себе изображения в разных его частях спектра, различных излучений, например таких как: оптические, инфракрасные, ультразвуковые и так далее, которые были получены разными способами, такими как например: телевизионными, фотографическими, лазерными, радиолокационными, радиационными и тому подобное, преобразованные в цифры и представленные в виде матриц чисел.

Исследования по распознаванию образов объектов отличаются большим разнообразием в постановке задач и выборе средств их реализации, что является одним и следствий разнообразия областей практического применения. Базовыми задачами, которые решались еще в первых разработках систем компьютерного зрения, являются задачи обнаружения и дальнейшего распознавания объектов, имеющих определённую форму на основе зашумленных и неровных изображений. Первопроходцем в практических задачах, подтолкнувших становление и развитие отрасли распознавания объектов на изображениях, являлась задача идентификации и распознавания человеческих лиц. Одним из методов, широко применяемых при решении задач распознавания объектов, является использование билатерального фильтра [1,2], но основным существенным его недостатком является скорость работы. В связи с этим, актуальным является рассмотрение и исследование возможности распараллеливания фильтра для повышения его качества и производительности.

1. Обзор методов распознования объектов на изображениях

Задача распознавания объектов на изображениях является современной и актуальной. Необходимость в решении такого рода задач возникает в самых разных областях – от военного дела и систем безопасности, до оцифровки аналоговых сигналов. Единого алгоритма распознавания не существует, поэтому пользуются определёнными методами для разных предметных областей. Например, для оптического распознавания образов можно применить метод перебора вида объекта под различными углами, масштабами, смещениями и так далее. Для символов нужно перебирать шрифт, свойства шрифта и так далее. Ещё одним подходом является нахождение контура объекта и исследование его свойства (связность, наличие углов). В некоторых областях для эффективной реализации распознавания образов используют нейронные сети, но этот метод требует либо большого количества примеров задач распознавания (с правильными ответами), либо специальной структуры нейронной сети, учитывающей специфику данной задачи.

1.1 Метод контурного анализа

Для распознавания изображений, не обладающих внутренними деталями, применяется контурный анализ [3,4]. Этот метод позволяет распознавать объекты с измененным размером, а также с небольшим (до 15°) углом поворота. Возможна модификация для объектов, повернутых под любым углом. Под контуром понимается граница объекта, т. е. совокупность точек (пикселей), отделяющих объект от фона. Контур кодируется последовательностью, состоящей из комплексных чисел. На контуре фиксируется начальная точка. Затем контур обходится в заданном направлении (например, по часовой стрелке), и каждый вектор смещения V записывается комплексным числом по формуле (1):

Формула 1

где x – смещение точки по оси X; y – смещение по оси Y. Смещение берется относительно предыдущей точки контура. Смещение первой точки определяется относительно точки (0, 0). Вектор – контур R длиной k можно обозначить следующим образом по формуле (2):

Формула 2

где Yi – i–я точка контура. Скалярным произведением контуров R и N называется комплексное число, вычисляемое по формуле (3)

Формула 3

где k – размерность контура; Yn – n–й вектор контура R; Sn– n–й вектор контура N. Скалярное произведение векторов (Yn ,Sn ) вычисляется по формуле (4)

Формула 4

Чтобы вычислить степень сходства контуров, используется нормированное скалярное произведение (НСП) вычисляемое по формуле (5):

Формула 5

где длины контуров вычисляются по формуле (6)

Формула 6

Модуль НСП дает меру сходства контуров, а его аргумент–угол поворота контуров относительно друг друга (при сохранении начальной точки контура). Таким образом, можно найти одинаковые контуры на заданном изображении

1.2 Шок–фильтр

Для выделения четкой границы между зонами с разной интенсивностью цвета используется шок-фильтр [5,6]. Определить близость анализируемой точки к границе можно, вычислив градиент функции интенсивности цвета в этой точке, так как на границе он будет иметь наибольшее значение. Однако градиента недостаточно, чтобы узнать, к какой зоне интенсивности принадлежит пиксел, поскольку большие значения градиента также характеризуют отдельные пикселы, отличающиеся от общего фона. Для того чтобы определить нужную зону, используется оператор Лапласа вычисляемый по формуле (7):

Формула 7

где , gxx gyy – вторые производные от функции g по x и по y соответственно. Если обозначить через f(x,y) исходное изображение, то выражение для шок-фильтра может быть представлено в виде формулы (8):

Формула 8

где sign – знаковая функция; Df – градиент функции f; a–константа. На основании формулы можно сделать следующий вывод: если пиксель относится к зоне минимальной интенсивности цвета, его значение будет уменьшено, а в противном случае ? увеличено. Таким образом, создается четкая граница раздела цветовых областей. К недостаткам шок-фильтра относится создание помех в случае большого количества отдельных пикселей и шумов. На основании рассмотренных методов можно сделать следующие выводы:

  1. Для распознавания изображений, не обладающих внутренними деталями, нужно применять контурный метод. Он позволяет распознавать объекты разных размеров и небольшим углом поворота.
  2. Для выделения чёткой границы между зонами с разной интенсивность цвета целесообразно использовать шок–фильтр.

2. Описание билатерального фильтра

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

Стоит отметить, что алгоритмы, которые ускоряют работу фильтра, разрабатывались раннее, но подавляющее большинство из них в результате приводят к потере качества. Такие алгоритмы описывают набор методов, которые ускоряют работу фильтра.На текущей момент есть два принципа ускорения работы фильтра, первый – специализированные фильтры, выполняющие точные вычисления, но ограничены в определенных задачах. Второй принцип–это использовать округляющие фильтры, они носят общий характер, но не позволяют достичь сверх точных результатов. Математики Дуранд и Дорси преобразовали к линейному виду данный фильтр, что позволяет применять быстрые преобразования Фурье. Чтобы увеличить скорость вычислений до одной секунды или меньше, они используют дискретизацию данных которая понижается, для небольших изображений. В их работе для билатерального фильтра, отводится место для вычисления быстрого преобразования Фурье, и прямая свёртка становится более эффективной, как только данные преобразуются, т. к. ядро достаточно мало. Хотя их исследование не выделяет этого, результаты их работы достигаются с прямой свёрткой, без использования преобразования Фурье. Разработанная ими методика связана напрямую с их работой в том, что в ней через линейные операции выражен билатеральный фильтр и наибольшую часть ускорения взята от понижающей дискретизации. Это позволяет получить повышенную точность обработки изображения при использовании данной фильтрации. Билатеральный фильтр также используется для фильтрования карты глубины. Отфильтрованная карта глубины имеет удовлетворительное визуальное качество, потому что быстрый билатеральный фильтр генерирует гладкую карту глубины внутри гладкой области с аналогичными значениями пикселей и сохраняет резкий разрыв по глубине на границе объекта. После фильтрации быстрым фильтром карта глубины затем используется для генерации левого, правого или мульти–просмотра изображения с использованием глубинного рендеринга на основе изображений (DIBR) для 3D визуализации.

2.1 Проблематика билатерального фильтра

В настоящее время вопросам билатеральной фильтрации посвящено большое количество работ. Билатеральный фильтр был адаптирован для таких задач, как: удаление текстуры, динамическое ранговое сжатие и обработка фотографий. Также успешно используется в других областях: выделение контуров, объемное шумоподавление и коррекция видео. Такой широкий спектр применения фильтр получил из–за нескольких особенностей. С одной стороны, простота формализации и выполнения: пиксель просто заменяется взвешенным средним его соседей. Билатеральный фильтр также может быть определен с использованием быстрого преобразования Фурье, но Гауссов билатеральный фильтр получил большее практическое применение.

Точная обработка билатеральным фильтром с использованием определения требует больших затрат вычислительных ресурсов, что неприменимо, например, для предварительной обработки цифровых данных. Существует четыре приближенных метода билатеральной фильтрации. Классификация методов изображена на рисунке ниже.

Классификация методов БФ

Рисунок 1 – Классификация методов БФ
(анимация: 7 кадров, количество циклов – 7, время задержки 45мс, размер 102 Кб)

2.2 Прямой метод

При реализации билатеральной фильтрации прямым методом вычисление интенсивности пикселя происходит по ограниченной области по следующей формуле (9):

Формула 9

Эта область содержит в себе пиксели, удаленные от центрального не более чем на удвоенное стандартное отклонение, так как вклад остальных пикселей незначителен. Такое приближение эффективно только для небольших ядер (малых значениях параметра) из–за квадратичной зависимости. С помощью данного алгоритма можно получить результат близкий к точному за счет больших временных затрат, например, обработка изображения размером 8 Мп длится более 10 минут [7].

2.3 Метод разделяемого ядра

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

Данный метод фильтрации эффективен при небольших ядрах и применим для обработки видео, при условии применения нескольких итераций фильтра с небольшим ядром. Но фильтр неприменим для больших ядер из–за появления видимых артефактов, так как при увеличении размеров ядра область, обрабатываемая для вычисления веса каждого пикселя, содержит все больше разнообразных деталей изображения, например, несколько краев объекта и его внутренних границ. Но эти особенности не могут повлиять на результат фильтрации из–за раздельной обработки строк и столбцов.

2.4 Метод локальных гисторграмм

Метод локальных гистограмм не учитывает расстояние между пикселями. Результат вычисляется по пикселям, захватываемым квадратным ядром (локальной гистограмме) по следующей формуле (10):

Формула 10

За счет исключения пространственного веса происходит ускорение вычислений, так как для двух соседних пикселей локальные гистограммы почти полностью совпадают. Сложность алгоритма вычисляется как логарифм от радиуса ядра. Таким образом, время выполнения составляет порядка нескольких секунд даже для больших ядер (радиусом 100 пикселей для более чем 8 Мп изображения). Недостатком применения данного метода является появление ореолов возле резких границ, т.н. полос Маха. Избежать этого эффекта можно применив фильтр в три итерации, оставляя ранговые веса постоянными, что сглаживает границы артефактов. Но подобное улучшение приводит к тому, что схема алгоритма становится трудной для адаптации, в особенности для цветных изображений и других задач фильтрации изображений с большим объемом обрабатываемой информации.

2.5 Метод решётки

Основная идея метода билатеральной решетки заключается в том, чтобы результат зависел только от расстояния между пикселями. Изображение представляется в трехмерном пространстве, где к стандартным координатам плоскости изображения добавляется координата интенсивности пикселя, т.е. вычисляем однородный вектор по формуле (11):

Формула 11

Полученное пространство сжимается с заданной частотой дискретизации, при этом информация по каждому пикселю сохраняется в соответствующей ему грубой накопительной ячейке. Объемная структура, состоящая из таких ячеек, называется билатеральной решеткой. Далее производится обработка билатеральным фильтром с учетом только расстояния между пикселями, а именно свертка с трехмерной функцией Гаусса после чего результат восстанавливается по исходным позициям пикселей: трилинейная интерполяция и нормализация результата. Данный алгоритм позволяет производить обработку с ядрами любого размера за короткий промежуток времени (примерно 1 сек). Основным преимуществом метода быстрой билатеральной фильтрации является простота его адаптации для других задач и расширений, например, для цветных изображений или при одновременной обработке двух изображений.

В результате сравнения билатеральной фильтрации со стандартными методами шумоподавления и анализа различных методов билатеральной фильтрации (визуальное сравнение и численные характеристики приведены на рис. 1) можно сделать следующие выводы:

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

3. Направления, цели и задачи дальнейших исследований

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

Данный метод можно быть также достаточно легко параллельно реализован. Например, на графическом процессоре NVIDIA Geforce 8800 GPU при одинаковом качестве результата, метод в среднем в 10 раз быстрее чем остальные методы [8,9]. Так как в методе используется независимая обработка каждого пикселя, метод поддаётся распараллеливанию, что позволит ускорить его работу, и возможно проводить обработку изображений в реальном времени.

Целью и задачами дальнейшего исследования является разбор функционирования метода и исследование характеристик его работы, с дальнейшей оптимизацией метода по качеству и скорости работы, а также отображение полученного модифицированного метода на параллельные структуры вычислительных систем, получение характеристик реализаций и анализ эффективности выполненных разработок. В качестве параллельной вычислительной системы планируется использовать параллельный мультипроцессор видеокарты ПК, работу с ним организовать при помощи технологий GPGPU и OpenACC [10].

Выводы

В ходе выполнения работы выполнен анализ существующих средств распознавания объектов на изображениях, были рассмотрены методы и алгоритмы билатеральной фильтрации для решения задач распознавания объектов на изображениях. Дано описание билатерального фильтра и его математического представления, проанализированы проблемы фильтра и методы их решения. Были рассмотрены возможности ускорения и повышения качества билатеральной фильтрации при обработке изображений за счет распараллеливания вычислительных процессов, выполнен предварительный анализ возможности распараллеливания фильтра. В качестве объекта дальнейших исследований был выбран метод Декомпозиции билатерального фильтра на пространственные фильтры и дальнейшая его параллельная реализация. В качестве параллельной вычислительной системы планируется использовать параллельный мультипроцессор видеокарты ПК, работу с ним организовать при помощи технологий GPGPU и OpenACC.

Список источников

  1. Билатеральные фильтры кратко. [Электронный ресурс] – Режим доступа: http://old.unick-soft.ru – Загл. с экрана.
  2. Bilateral filter [Электронный ресурс] – Режим доступа: https://en.wikipedia.org – Загл. с экрана.
  3. Фурман Я.А Введение в контурный анализ. Москва, ФИЗМАТЛИТ, 2003, 598 с.
  4. Обзор основных методов контурного анализа для выделения контуров движущихся объектов [Электронный ресурс] – Режим доступа: http://www.engjournal.ru – Загл. с экрана.
  5. Weickert J., Coherence-Encahncing Shock Filters. Lecture Notes in Computer Science. Springer, 2003, vol. 2781, pp. 1–8.
  6. Метод предварительной фильтрации изображений для повышения точности распознавания образов. [Электронный ресурс] – Режим доступа: http://www.engjournal.ru – Загл. с экрана.
  7. W.-Y. Chen and Y.-L. Chang and S.-F. Lin and L.-F. Ding and L.-G. Chen.”Efficient depth image based rendering with edge dependent depth filter and interpolation,” in Proc. ICME, pp. 1314-1317, 2005.
  8. Анализ эффективности алгоритмов билатеральной фильтрации. [Электронный ресурс] – Режим доступа: http://engineering-science.ru – Загл. с экрана.
  9. Real-Time Bilateral Filtering. [Электронный ресурс] – Режим доступа: http://vision.ai.illinois.edu – Загл. с экрана.
  10. OpenACC. [Электронный ресурс] – Режим доступа: https://www.openacc.org – Загл. с экрана.