Содержание

Введение

1. Актуальность темы

2. Цель и задачи исследования, планируемые результаты

3. Обзор исследований и разработок

3.1 Обзор моделей шумов. Зашумление изображения

3.2 Обзор алгоритмов размытия изображения

3.3 Обзор локальных источников

4. Сравнительный анализ стандартного средства размытия изображений Renderscript и алгоритма Stack Blur

Выводы

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

Введение

Обработка изображений — любая форма обработки информации, для которой входные данные представлены изображением, например, фотографиями или видеокадрами. Обработка изображений может осуществляться как для получения изображения на выходе (например, подготовка к полиграфическому тиражированию, к телетрансляции и т. д.), так и для получения другой информации (например, распознание текста, подсчёт числа и типа клеток в поле микроскопа и т. д.). Кроме статичных двухмерных изображений, обрабатывать требуется также изображения, изменяющиеся со временем, например, видео [1]. Повышение качества изображения для восприятия человеком, создание спецэффектов, обработка изображений (выделение объектов, поиск лиц, улыбок) - это задачи, которые решаются с помощью фильтрации изображений.
Ещё в середине XX века обработка изображений была по большей части аналоговой и выполнялась оптическими устройствами. Подобные оптические методы до сих пор важны, в таких областях как, например, голография. Тем не менее, с резким ростом производительности компьютеров, эти методы всё в большей мере вытеснялись методами цифровой обработки изображений. Методы цифровой обработки изображений обычно являются более точными, надёжными, гибкими и простыми в реализации, нежели аналоговые методы. В цифровой обработке изображений широко применяется специализированное оборудование, такое как процессоры с конвейерной обработкой инструкций и многопроцессорные системы [2].

1. Актуальность темы

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

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

• распознавание текста;
• обработка спутниковых снимков;
• машинное зрение;
• обработка данных для выделения различных характеристик;
• обработка изображений в медицине;
• идентификация личности (по лицу, радужке, дактилоскопическим данным);
• автоматическое управление автомобилями;
• определение формы интересующего нас объекта;
• определение перемещения объекта;
• наложение фильтров [1].

2. Цель и задачи исследования, планируемые результаты

Задачи исследования заключаются в следующем:

• составить качественный обзор существующих алгоритмов фильтрации изображений, таких как размытие, резкость, зашумление, удаление шума;
• провести сравнительный анализ разных алгоритмов одного и того же фильтра по таким критериям, как время работы и качество полученного изображения в зависимости от языка программирования (Java или C++);
• оптимизировать выбранные наилучшие алгоритмы под операционную систему Android.

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

3. Обзор исследований и разработок

3.1 Обзор моделей шумов. Зашумление изображения

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

При попытке математически скорректировать подобную сложную модель регистрации изображения говорят уже не о фильтрации от шума, а о реставрации или реконструкции изображений. Наиболее общей моделью независимого зашумления пикселов является шум замещения. Пусть дано исходное (незашумленное) полутоновое изображение I_m [x,y], каждый пиксел которого может принимать значения в диапазоне [0,…,I_max-1]. Общая модель шума замещения предполагает, что после зашумления каждый пиксел изображения, имевший ранее значение яркости i, либо с некоторой известной вероятностью p(i) это значение сохранит, либо данное значение яркости будет случайным образом замещено с вероятностью q(i,j) некоторым другим значением яркости j из того же конечного дискретного диапазона [0,…,I_max-1]. Как видно, для описания такой общей модели случайного замещения необходимо задать таблицу переходных вероятностей размера I_max², что составляет весьма значительное количество в случае обычного 8-битового полутонового изображения (размер таблицы - 256×256 элементов). Такое описание явно является некомпактным и поэтому редко используется на практике для полутоновых изображений. Для полутоновых изображений, как правило, рассматривают другую, более частную модель зашумления – аддитивный шум, которая предполагает, что зашумленное изображение порождается по закону:

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

Рисунок 1 — Исходное полутоновое изображение, σ=0

Рисунок 2 — Зашумление полутонового изображения аддитивным гауссовским шумом, σ=20

Рисунок 3 — Зашумление полутонового изображения аддитивным гауссовским шумом, σ=40

Рисунок 4 — Зашумление полутонового изображения аддитивным гауссовским шумом, σ=60

3.2 Обзор алгоритмов размытия изображения

Размытие изображений играет большую роль в современных областях компьютерной графики. Размытие изображений часто бывает направлено на имитацию близорукости (в тех случаях, когда близорукость становится желательной или даже необходимой). Так, размытие отдельных частей изображения часто используют из соображений цензуры. В ряде случаев размытие является неотъемлемой частью различных техник коррекции изображения, направленных на устранение специфических дефектов (излишняя детализация, дефекты сканирования, царапины, пыль). Известно, что фотомодели и их фотографы используют специальные процедуры размытия фотографических изображений для достижения эффекта устранения морщин. Размытые изображения так же лучше поддаются сжатию (так, при сохранении в формате JPEG графический файл имеет меньший размер, а также менее выраженные арте- факты компрессии). Различные техники размытия изображения доступны во всех современных графических редакторах.

Размытие по Гауссу — это характерный фильтр размытия изображения, который использует нормальное распределение (также называемое Гауссовым распределением, отсюда название) для вычисления преобразования, применяемого к каждому пикселю изображения. Уравнение распределения Гаусса в N измерениях имеет вид:

Размытие изображения по Гауссу при различных радиусах размытия выглядит следующим образом:

Рисунок 5 – Размытие изображения по Гауссу
(анимация: 7 кадров, 10 циклов повторения, 144 килобайта)
(R — радиус размытия изображения в пикселях).

В целом, для того, чтобы размыть изображение, необходимо каким-то образом усреднить значения цвета каждого пикселя изображения с цветами его соседей в пределах некоторого диапазона. Этот диапазон называется радиусом размытия. Очевидным решением будет следующее: сложить значения цвета для каждого пикселя, расположенного не дальше, чем радиус размытия от текущего, по X и Y координате, а затем поделить их на квадрат двух радиусов размытия плюс единица (так как лева, справа, сверху и снизу выбираются пиксели на расстоянии не больше чем радиус + центральные пиксели). Кроме того, при размытии изображения следует учитывать веса пикселей. При их вариации можно получить различный результат. Так, если все пиксели будут иметь одинаковый вес, мы получим усредненное изображение. Если же придать центральным пикселям больше веса, чем крайним, то изображение будет более сконцентрировано. Для вариации весов можно использовать различные законы распределения, известные из математической статистики.

Алгоритм усреднения соседних пикселей использует равномерный закон распределения. В этом случае все пиксели будут иметь одинаковый вес. В случае, когда радиус размытия равен десяти:

Треугольный закон распределения – алгоритм размытия, использующий закон распределения Симпсона. В данном законе распределения веса соседних точек на текстуре с увеличением расстояния до центральной точки убывают линейно. Как и раньше, радиус размытия равен десяти. Необходимо найти сумму всех весов соседних пикселей текстуры и поделить конечный результат на неё. Для этого пусть вес центрального пикселя будет равен (r+1). В таком случае веса соседних пикселей будут изменяться в соответствии с функцией f(x). Веса крайних точек в этом случае будут равны единице.

3.3 Обзор локальных источников

В пределах портала магистров Донецкого национального технического университета не было найдено ни одной работы, соответствующей тематике данного дипломного проекта. Однако, есть несколько работ в направлении обработки изображений, например, проекты Д. И. Метелицы – Разработка и анализ алгоритма выделения контура на полутоновом изображении при условии слабоконтрастных границ объектов [7]; Д. А. Савченко – Исследование методов сегментации изображений  [8]; А. В. Колесника – Распределенная программная система для распознавания изображений  [9]. Не было найдено ни одной выпускной работы, которая включала бы в себя любые операции с изображениями на платформе Android. На данный момент программирование под операционную систему Android стремительно набирает популярность, поэтому существует большая вероятность, что в дальнейшем на портале магистров будет появляться все больше дипломных работ, связанных с этой сферой.

4. Сравнительный анализ стандартного средства размытия изображений Renderscript и алгоритма Stack Blur

В последнее время все больше приложений, появляющихся на просторах Google Play Store, используют эффект размытия. Например, известное приложение Muzei от +RomanNurik или популярный виджет Yahoo Weather. Изучив эти приложения можно заметить, что при умелом обращении с размытием можно добиться очень впечатляющих результатов. В данном дипломном проекте алгоритмы фильтрации изображений необходимо оптимизировать, учитывая особенности операционной системы Android. Чем быстрее работает алгоритм, тем лучше, так как операция размытия, зашумления и т. д. должны производиться максимально незаметно для пользователя. Не стоит забывать о том, что Android-приложения работают на мобильных устройствах, а не на компьютере.

Одним из самых популярных и удобных способов быстрого размытия картинки в Android является Renderscript. Это очень мощный инструмент для работы с изображениями. Несмотря на его кажущуюся сложность, многие его части достаточно просты в использовании. Renderscript — это новый API, направленный на высокую производительность при 3D рендеринге и сложных вычислительных операциях. Renderscript будет интересен при попытке максимизировать производительность приложений. Для разработчиков доступны три инструмента: простой API для 3D рендеринга, поддерживающего аппаратное ускорение, API для моделирования сложных вычислений, и язык стандарта, близкого к C99.

Улучшение производительности достигается путем выполнения нативного кода на устройстве. Однако, в отличие от NDK, это решение кроссплатформенно. Язык разработки для Renderscript — это C99 с некоторыми расширениями, во время процесса разработки, он компилируется в аппаратно-независимом промежуточном формате и размещается в пакете приложения. Когда приложение запускается, то скрипт компилируется в машинный код и оптимизируется. Это позволяет избежать проблем, связанных с необходимостью выбирать какую-то определенную машинную архитектуру. Renderscript не предназначен для замены существующего высокоуровневого API, его следует использовать в тех случаях, когда текущая необходимость в производительности не обеспечивается с помощью API [10]. Renderscript доступен в Android с версии 3.0 и выше.

В результате поиска способов оптимизации размытия изображений было установлено, что Render Script - не самый быстрый метод размытия графического файла. Был найден алгоритм Stack Blur, автором которого является Mario Klingemann. Этот алгоритм после реализации на С++ NDK показал существенно лучшую производительность по сравнению с Render Script. При обработке изображения размером 325×60 с радиусом размытия 20 пикселей Renderscript показал результат в 13 мс, а Stack Blur - 2 мс. При этом качество результата получилось примерно одинаковым.

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

Выводы

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

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