ABSTRACT
For reduction of the computational complexity of image analysis with large area it is common practice at first to find objects at a low resolution, and then to gaze them at a higher resolution. This article is devoted to a family of algorithms for segmentation of images and techniques for visualization of effectiveness of segmentation and noise reduction algorithms.
Ключевые слова: вейвлет преобразование, сегментация, пирамида изображений, фильтрация изображений, ROC характеристика.
Keywords: wavelet transform, segmentation, image pyramid, image filtering, ROC curve.
Семейство алгоритмов сегментации с различной точностью
В 2006, 2007 и 2013 годах были разработаны идейно близкие способы локализации объектов с пониженной [5], нормальной [3] и повышенной (субпиксельной) точностью. Основная идея заключается в объединении изменяющихся участков кадра («движущихся областей») и смещающихся контуров объектов («движущихся контуров») с помощью операции «ИЛИ».
Изменение пространственной точности определения координат объектов связано с вычислением нужного уровня пирамиды разрешений. В отличие от наиболее часто рассматриваемых способов построения пирамиды, направленных только на снижение разрешения, в статье рассматривается и способ увеличения разрешения изображения.
Первый разработанный алгоритм представлен на рис. 1.
Рисунок 1. Блок-схема алгоритма сегментации, основанного на разнице «нулевых» уровней вейвлет-преобразований
В нём нет изменения площади яркостной составляющей кадра, поэтому можно говорить, что он связан с «нулевым уровнем» вейвлет-преобразования: 
. Вейвлет-преобразование имитируется путем вычисления контуров фильтром Превитт. Разностные кадры бинаризуются и объединяются с помощью операции «ИЛИ».
Традиционное направление связано с понижением разрешения изображения. Ранее это было актуально из-за низкой скорости вычислений даже на небольших изображениях. Сейчас размеры изображений стремительно растут, а также в СПБГУАП активно развивается направление видеопанорам, поэтому скорость вычислений по-прежнему является больной точкой и понижение разрешения актуально в случае обработки изображений больших площадей. В теории рассматриваются разные способы вычисления сглаженной и прореженной версии изображения (Гауссиан [10], фильтр Габора [9], среднее, минимальное или максимальное значение, полусумма минимального и максимального значений, медиана участка изображения предыдущего уровня пирамиды[1], морфологическая операция «размыкание» (чередование базовых операций «эрозия» и «наращивание»), вейвлет преобразование [8]). В данной работе используются вейвлеты.
Второй разработанный алгоритм основан на настоящем вейвлет преобразовании. На основании исследований [7] для вычисления низкочастотной (НЧ) и высокочастотных (ВЧ) составляющих был выбран вейвлет Хаара. После прямого двумерного дискретного вейвлет преобразования (ДВП) изображения кадра три высокочастотных диапазона, соответствующих изменениям в горизонтальном, вертикальном и диагональном направлениях, объединяются суммированием амплитуд трансформант с проверкой переполнения разрядной сетки:
.
Аналогичные операции производятся для изображения оценки фона. Затем следует попарное вычисление разниц НЧ и объединенных ВЧ составляющих (рис. 2). Объединение бинаризованных разностных изображений производится также с помощью операции «ИЛИ».
Рисунок 2. Блок-схема алгоритма сегментации, основанного на разнице первых «отрицательных» уровней вейвлет преобразований
Размеры получаемых изображений в 4 раза меньше, чем исходных, то есть можно сказать, что речь идет о первом отрицательном уровне разложения: 
. Более глубокие «отрицательные уровни» разложения получаются применением вейвлет преобразования к НЧ составляющей ДВП, а затем осуществлением объединения ВЧ диапазонов.
Если требуется точность определения координат объектов меньше пикселя, то необходимо задуматься о реализации «положительных уровней» разложения, т. е. повышении площади яркостной составляющей изображения (рис. 3). Первые работы в направлении повышения разрешения изображений с помощью вейвлет-преобразования были сделаны в начале 2000-х годов [11].
Рисунок 3. Блок-схема алгоритма обнаружения, основанного на разнице первых «положительных» уровней вейвлет преобразований
Размеры получаемых изображений в 4 раза больше, чем исходных, то есть можно сказать, что речь идет о первом положительном уровне разложения: 
(такие обозначения введены из-за специфики процесса вычисления двумерного вейвлет-преобразования, каждый уровень которого выполняется в два этапа — сначала по горизонтали, а затем по вертикали). Следующие «положительные уровни» получаются тем же способом — вычисление контуров изображения в трех направлениях, выполнение обратного вейвлет преобразования.
Различие между алгоритмами семейства в спектральной области приводит к отличающимся характеристикам их эффективности. При вычислении отрицательных уровней контуры сильно ослабляются, что приводит к потере высокочастотной энергии. При вычислении положительных уровней контуры растягиваются в пространстве, что снижает их крутизну и сдвигает высокие частоты в область средних частот. Поэтому по наличию высокочастотной энергии, критически важной для выделения «движущихся контуров», можно априорно расположить эффективность алгоритмов разных уровней в следующем порядке: нулевой, положительные, отрицательные. Это подтверждается результатами эксперимента (рис. 4).
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Рисунок 4. Графики 
для разных уровней семейства алгоритмов. Методы сегментации: зеленый — нулевой уровень, красный — плюс первый, синий — минус первый.
Визуализация эффективности движения к требуемым показателям точности
Разработчику заданы минимально приемлимые значения вероятностей правильного обнаружения Рпо и ложной тревоги Рпо, по которым можно построить минимально приемлемую целевую характеристику Рпо = f(Рпо). Рассмотрим понятие зона требуемой точности — это область в верхнем левом углу характеристики Рпо = f(Рлт), ограниченная требуемыми значениями Рпо и Рлт, в которой должна находиться хотя бы одна точка целевой характеристики. Для примера на рис. 5 показана зона требуемой точности в виде квадрата (1), одна из целевых характеристик (2) и характеристика алгоритма сегментации (3).
Как правило, характеристика алгоритма сегментации сильно отличается от целевой характеристики. Конкретная точка на характеристике, соответствующая определенному соотношению белых и черных пикселей, выбирается критерием. Соответственно на начальном этапе выбранная критерием рабочая точка находится далеко от зоны требуемой точности. Тогда возникает желание скачком переместиться поближе к этой зоне. Для реализации такого скачка часто используют объединение двух и более алгоритмов сегментации.
Рисунок 5 Пояснение к построению зоны требуемой точности и одной из целевых характеристик Рпо=f(Рлт).
После объединения изображений — результатов работы алгоритмов сегментации — получается изображение с определенными мощностями множеств черных и белых пикселей. Эти мощности определяют значения показателей Рпо, Рлт, то есть точку в пространстве характеристики Рпо=f(Рлт). Через эту точки проходит зависимость Рпо=f(Рлт) объединенного алгоритма. Если полученная точка всё еще далека от зоны требуемой точности, то полученное бинарное изображение можно объединять еще с каким-то алгоритмом сегментации или применять к нему фильтры. Это приведет к появлению еще одной точки в пространстве Рпо=f(Рлт). Эти точки, получаемые после каждого блока обработки, можно отобразить в виде графика рабочих точек (рис. 6). Таким образом, в процессе создания алгоритма анализа видеоинформации разработчик реализует одну из траекторий движения к зоне требуемой точности, создавая набор смещающихся характеристик Рпо=f(Рлт).
Рисунок 6. График рабочих точек в пространстве характеристики Рпо=f(Рлт) для алгоритма «нулевого уровня». Цифрами обозначены рабочие точки после этапов обработки изображения.
Особенностью разработанного семейства алгоритмов сегментации являются необычная траектория движения к целевым показателям (целевой характеристике), получающая после объединения алгоритмов с помощью операции «ИЛИ». Нестандартной она является, т. к. наиболее распространены подходы объединения с помощью операции «И» или построенные на определенных правилах.
Алгоритмы сегментации, построенные на операции «ИЛИ», в результате объединения получают высокую вероятность ложных тревог и высокую вероятность правильного обнаружения. Таким образом, разработчик, реализующий операцию «ИЛИ» должен разработать алгоритмы подавления шумов, чтобы приблизиться к зоне требуемой точности.
Визуализация эффективности подавления шума
Объединение результатов работы алгоритмов сегментации с помощью операции «ИЛИ» мало исследовано в связи с возникающими трудностями из-за возрастающей вероятности повреждения изображения. В [4] были приведены сведения о фильтрах, позволяющих значительно снизить вероятность повреждения изображения в блоках подавления шума. К фильтрам подавления шума относится многошаговый медианный фильтр (см. [2, с. 124—125]).
Для иллюстрации эффективности фильтрации изображений в [6] предложен способ визуализации «гистограмма связности». Каждый пиксель растрового изображения имеет вокруг себя некоторое количество других пикселей — множество, называемое окрестностью этого пикселя. Обозначим символом С количество анализируемых пикселей, окружающих пиксель I[x,y], т. е. количество проверяемых связей. Пиксель изображения считается «связанным» с соседним пикселем, принадлежащим окрестности, если их яркости одинаковы. Обозначим количество соседей пикселя символом U[x,y]. Обозначим количество пикселей изображения, имеющих одинаковую связность, символом WU, где U
[0..С].
Понятия, характеризующие изображение:
1. гистограмма связности изображения (области) — это гистограмма, в которой отражается статистика области 
— площадь изображения. Под выделенными пикселями понимаются пиксели того цвета, который в данный момент представляет интерес (как правило, белый в бинарных изображениях);
2. общее количество соседей у всех выделенных пикселей — это величина 
— количество связей у выделенного пикселя;
3. средняя связность изображения — это величина 
— общее количество выделенных пикселей.
Примеры построения гистограмм связности приведены на рис. 7—9.
Рисунок 7. Исходное бинарное изображение и его гистограмма связности. Средняя связность равна 5,3746
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Рисунок 8. Изображение после многошаговой медианной фильтрации и его гистограмма связности. Средняя связность равна 6,0646
Рисунок 9. Изображение после медианной фильтрации и его гистограмма связности. Средняя связность равна 6,8496
Импульсы шума представляют из себя одиночные резкие скачки яркости. В результате у зашумленного изображения средняя связность низкая. В ходе обработки фильтрами на основе порядковой статистики связность повышается за счет подавления одиночных импульсов.
Заключение
По проведенным исследованиям сделаны следующие выводы:
1. к семейству алгоритмов с регулируемой точностью сегментации добавлены положительные уровни, что позволяет определять положение объектов с субпиксельной точностью;
2. наибольшая точность у алгоритмов «нулевого уровня»;
3. разработана методика визуализации эффективности различных этапов в процессе сегментации изображений;
4. на основе методики визуализации «гистограмма связности» установлено, что классический медианный фильтр эффективнее многошагового медианного фильтра в подавлении импульсного шума.
Список литературы:
1.Александров В.В., Горский Н.Д. Представление и обработка изображений. Рекурсивный подход. Л.: Наука, 1985. — 192 с.
2.Егорова С.Д., Колесник В.А. Оптико-электронное цифровое преобразование изображений. М.: Радио и связь, 1991. — 208 с.
3.Кузьмин С.А. Обнаружение движущихся визуальных объектов на основе выделения областей и контуров, не принадлежащих фону// Молодые ученые — промышленности Северо-Западного региона: Материалы конференций политехнического симпозиума. Декабрь 2006 года. СПб.: Изд-во Политехн. ун-та, 2006. — С. 56.
4.Кузьмин С.А. Исследование комбинации детектора импульсного шума в бинарных изображениях и процентильных фильтров// «Естественные и математические науки в современном мире»: материалы IX международной заочной научно-практической конференции. (19 августа 2013 г.) Новосибирск: Изд. «СибАК», 2013. — C. 34—44.
5.Кузьмин С.А. Обнаружение визуальных объектов с использованием вейвлет-преобразования и оценивания фона//Системы управления и информационные технологии, 2.1(28), 2007. — С. 158—162.
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
6.Кузьмин С.А. Повышение вероятности правильного обнаружения объектов в видеопоследовательности с помощью ранговых операторов// Научная сессия ГУАП: Сб. докл.: В 3 ч. Ч. II. Технические науки /СПбГУАП. СПб., 2010. — С. 41—44.
7.Кузьмин С.А. Исследование точности сегментации подвижных объектов с использованием вейвлетов семейства Добеши// Научная сессия ГУАП: Сб. докл.: В 3 ч. Ч. II. Технические науки /СПбГУАП. СПб., 2008. — С. 32—35.
8.Харатишвили Н.Г., Чхеидзе И.М. Морфологические построения в кодировании изображений. Тбилиси: Грузинский технический университет, 2009. — 144 с.
9.Чочиа П.А. Пирамидальный алгоритм сегментации изображений // Информационные процессы, — Том 10, — № 1, — 2010. — С. 23—35.
10.Burt P.J. and Adelson E.H., The Laplacian pyramid as a compact image code, IEEE Trans. Commun., — vol. 31, — № 4, — pp. 532—540, — April 1983.
11.Shcherbakov M.A., Schegolev W.Y. A Wavelet-based Technique for Image Refinement, EUSIPCO-2000, Tampere, pp. 1737—1739.