Содержание к диссертации
Введение
Глава 1 Модель формирования стереопары, восстановление рельефа по стереопаре, точность установления стереосоответствий, метод оценки верхней и нижней границы диспаритета 21
1.1 Модель формирования стереопары и ее особенности 21
1.2 Восстановление рельефа по стерепаре фотоснимков 23
1.3 Подходы оценки точности стереосоответствий 24
1.4 Выбор стереопар для диссертационного исследования 25
1.5 Анализ стереопар из набора 1 и набора 2 29
1.6 Метод оценки границ значений диспаритетов стереопары 31
1.6.1. Снижение вычислительной сложности и увеличение точности 32
1.6.2. Необходимые элементы математической статистики и теории вероятностей
1.6.3. Трехэтапный метод оценки границ диспаритета пикселов стереопар 35
1.6.4. Экспериментальная проверка метода оценки границ диспаритета пикселов,
анализ его эффективности и выводы 38
Глава 2 Анализ и исследование функций сравнения опорных областей 41
2.1 Математическое описание и анализ функций сравнения опорных областей 41
2.2 Схема сопоставления пикселов и опорных окон 45
2.3 Анализ модели сопоставления опорных областей, метод скользящего окна 46
2.4 Оптимизация вычисления значений целевых функций SAD и SSD 47
2.5 Оптимизация SAD и SSD для прямоугольных опорных областей 49
2.6 Анализ функции ZSAD 50
2.7 Анализ функции Census 52
2.8 Выводы 53
Глава 3 Разработка и исследование метода пространственно-цветовой сегментации изображения и статистического уточнения стереосоответствия стереопары 55
3.1 Анализ высокоточных алгоритмов поиска стереосоответствий 55
3.2 Существующие подходы сегментации изображений 57
3.2.1. Метод k-средних (метод главных точек) 58
3.2.2. Метод сдвига среднего (mean-shift) 59
3.2.3. Методы сегментации по гистограмме 59
3.2.4. Методы разрастания областей 60
3.3 Разработка нового метода сегментации изображения стереопары 62
3.4 Метод слияния малых сегментов 68
3.5 Критерии эффективности методов уточнения стереосоответствий 72
3.6 Разработка метода уточнения стереосоответствия в пределах выделенных сегментов изображения 73
3.7 Экспериментальная проверка эффективности многокритериального метода уточнения стереосоотвествия стереопар 74
Глава 4 Комплексный алгоритм поиска стереосоответствий 78
4.1 Метод локализации оценок границ диспаритета стереопар 79
4.2 Разработка комплексного алгоритма установления стереосоответствий 84
4.3 Экспериментальная проверка эффективности комплексных алгоритмов установления стереосоответствий, выводы 86
4.4 Сравнение с контроллером компьютерного зрения Microsoft Kinect 89
Заключение 94
Список сокращений и условных обозначений 98
Словарь терминов 101
Список литературы
- Подходы оценки точности стереосоответствий
- Анализ модели сопоставления опорных областей, метод скользящего окна
- Метод k-средних (метод главных точек)
- Разработка комплексного алгоритма установления стереосоответствий
Подходы оценки точности стереосоответствий
Задача идентификации пикселов стереопар активно изучается с середины 70х годов прошлого века. Для её решения разработано и адаптировано множество подходов, методов и алгоритмов. Среди них находят применение алгоритм распространения доверия (анг. belief propagation) [17, 18], динамическое программирование [19, 20], билатеральная фильтрация (анг. - bilateral filtering) [21, 22], алгоритмы из теории графов [23], методы цифровой обработки сигналов [24]. Многие из существующих подходов имеют высокую точность и быстродействие. Однако достижение высокой точности одновременно с высокой скоростью обработки стереопар – нетривиальная алгоритмическая и техническая задача. Реализация высокоточных трудоемких алгоритмов на специализированных вычислителях, таких как GPU (анг. Graphics Processing Unit), позволяет достичь высокой производительности порядка 10 кадров в секунду и более [1, 25, 26, 27]. В то же время, применение специализированных вычислителей не всегда возможно, так как конечные системы могут иметь ограничения энергопотребления и массо-габаритных характеристик.
Энергопотребление современного видеоадаптера с поддержкой параллельных вычислений CUDA (например, GeForce GTX 760) достигает уровня 200Вт [2]. Такая величина потребляемой мощности является значительной и несет дополнительную габаритную нагрузку на систему охлаждения. Это накладывает ограничения на применимость систем стереозрения, основанных на таких вычислителях. Современные универсальные процессоры могут иметь энергопотребление от 20 до 35 Вт и производительность около 100 GIPS (анг. Giga Istructions per Second, рус. – миллиардов инструкций в секунду) [3]. Кроме того, такие процессоры выпускаются отечественными предприятиями1 [4], что расширяет их применимость в специализированных государственно-значимых областях.
Особое место занимают алгоритмы на основе оценки взаимной корреляции. Их можно назвать классическими, так как история их исследования в области компьютерного зрения берет свое начало в 70х годах XX века [28, 29]. Наиболее часто корреляционно-подобный подход применяется вместе с жадной стратегией выбора значения диспаритета. Из возможных значений диспаритета выбирается такое, которое соответствует локально-экстремальному значению корреляционной функции (анг. – Winner Takes All, WTA). Жадные корреляционно-экстремальные алгоритмы (далее «корреляционно-экстремальные алгоритмы») обладают сравнительно низкой вычислительной сложностью: минимальная доказанная оценка сложности составляет O(Ndmax), здесь и далее N – число пикселов изображения стереопары, dmax – максимальное значение диспаритета [5]. Заметим, что данная оценка сложности справедлива для алгоритмов, устанавливающих так называемые «плотные» (анг. – dense)
Универсальный четырехядерный микропроцессор Эльбрус-4С с частотой 800МГц, пиковой производительностью 107 GIPS выпускается ЗАО «МСЦТ» г. Москва с 2014 года. стереосоответствия, или стереосоответствия для всех пикселов стереопары.
Альтернативой «плотным» являются «разреженные» (анг. – sparse) стереосоответствия, включающие оценку парралакса только части от всех пикселов изображения. Такой подход применяют, как правило, для сокращения вычислительной сложности основного этапа поиска пиксельных соответствий совместно с различными методами аппроксимации [30, 31].
Оценка вычислительной сложности сверху, составляющая O(Ndmax), теоретически позволяет использовать корреляционно-экстремальные алгоритмы с «плотным» результатом в высокопроизводительных системах стереозрения (системах реального времени, анг. – realime systems). Вопросы, связанные с практическим применением таких алгоритмов, рассматриваются в рамках данного диссертационного исследования. Основной недостаток корреляционно экстремальных алгоритмов в «чистом виде» — сравнительно низкая точность установления пиксельных соответствий, особенно в областях перепадов глубины (на границах объектов). Как правило, это проявляется в «утолщении» объектов на переднем плане, размытием границ (анг. – foreground fattening). Степень утолщения зависит от формы и размера опорного окна, а также от вида применяемой функции сравнения опорных областей. Точность работы моделей, реализующих корреляционно-подобные методы без дополнительной обработки полученных результатов, составляет около 15-20% неправильно найденных соответствий на стереопару в среднем [32, с. 1589].
Алгоритмы установления пиксельных соответствий с «разреженным» результатом, как правило, используются для последующей аппроксимации в «плотный» результат. В этом случае подмножество пикселов, для которого находятся стереосоответствия, по сути, является «каркасом» карты диспаритетов, её начальным приближением. Для такого подхода основная сложность заключаются в методе выбора пикселов для «каркаса» и выборе метода аппроксимации полученного стереосоответствия в первом приближении. Методы построения «каркаса» пикселов могут базироваться на различных подходах, таких как применение граничных фильтров или выделение так называемых «точек интереса» на изображении. Рассмотрим примеры реализации такого подхода.
Метод, предлагаемый авторами в работе [30] заключается в выделении границ объектов фильтром Канни [33], нахождении для граничных пикселов соответствий и последующей аппроксимацией диспаритетов остальных пикселов с помощью метода «Compressed sensing» [34]. Авторам удается достичь высокой итоговой точности - порядка 6,5% неверно найденных соответствий (на стереопарах «Tsukuba, Venus, Teddy, Cone»). Проанализируем полученные авторами результаты. Множество "граничных" пикселов составляет около 5% от всех пикселов стереопары. Поиск пиксельных соответстий пикселов "каркаса" производится методом из работы К.-И. Юна [35]. Програмная модель реализована в среде Matlab. Обработка стереопары Tsukuba с разрешением 384х288 занимает около 60 сек., что отчасти объясняется применением среды Matlab. Однако и базовый метод поиска пиксельных соответствий [35] затрачивает на аналогичную стереопару 60 сек. Соответственно поиск пиксельных соответствий для 5% от всей стереопары составит около 3 сек. Также необходимо учесть дополнительные временные затраты на граничный фильтр и аппроксимацию стереосоответствия. Таким образом, рассмотренный подход будет затрачивать как минимум 3 секунды на стереопару разрешения 384х288, что затрудняет его применение в высокопроизводительных системах стереозрения с процессорами общего назначения.
Анализ модели сопоставления опорных областей, метод скользящего окна
Задачи коррекции оптических искажений, устранения шумов и нормировки яркости изображений в рамках данного исследования подробно не рассматриваются. Для их решения существуют множество методов и алгоритмов. Некоторые из них разработаны для аппаратной реализации [43], другие рассчитаны на универсальное применение [44].
Рассмотрим подробнее вопрос угла съемки сцены. В модели, представленной во введении, направление съемки перпендикулярно линии, соединяющей оптические центры камер, однако это может быть не всегда так. На рисунке 1.1 изображена схематически геометрическая модель формирования стереопары для общего случая. Приведем описание данной схемы, основанное на материалах статьи А. Кукарина [6].
Пусть в пространстве имеются две камеры, такие что Со — центр первой камеры, Сі — центр второй камеры. Точка пространства М проецируется в х0 на плоскость изображения левой камеры и в хі на плоскость изображения правой камеры. Прообразом точки x0 на изображении левой камеры является луч x0M. Этот луч проецируется на плоскость второй камеры в прямую l1, называемую эпиполярной линией. Образ точки M на плоскости изображения второй камеры обязательно лежит на эпиполярной линии l1.
Эпиполярная геометрия: а – эпиполярный отрезок, соответствующий одному лучу; б – соответствующие эпиполярные линии и эпиполярная плоскость Таким образом, каждой точке x0 на изображении левой камеры соответствует эпиполярная линия l1 на изображении правой камеры. При этом пара для x0 на изображении правой камеры может лежать только на соответствующей эпиполярной линии. Аналогично, каждой точке x1 на правом изображении соответствует эпиполярная линия l на левом.
При установлении пиксельного соответствия для упрощения поиска изображения выравнивают (ректифицируют) так, чтобы все эпиполярные линии были параллельны сторонам изображения (в частности горизонтальны). Такие преобразования подразумевают предварительный расчет так называемой фундаментальной матрицы, фактически содержащей в себе информацию о положении камер в пространстве и их калибровке. Далее производится поворот изображений, и если необходимо перемасштабирование так, чтобы эпиполярные линии были горизонтальны и совпадали в координатах вертикальной оси изображения [45]. Таким образом достигается возможность поиска соответствующих пикселов вдоль только горизонтальных линий, без смещения вдоль вертикальной оси. Подробное описание всего математического аппарата и методов, с помощью которых можно провести подобные преобразования изображений стереопары, приведено в работах [46-48].
Основная практическая цель поиска пиксельных соответствий на стереопарах получение трехмерной модели проекции части пространства, запечатленной на двух снимках. Для модели формирования стереопары изображений, представленной во введении, справедливо равенство[1, с. 70]: где f – фокусное расстояние камеры, B величина стереобазы (расстояние между точками съемки), d=x2-x1 разность координат соответствующих пикселов на изображениях стереопары, Z расстояние от плоскости съемки до точки пространства M. Необходимо отметить, что разность координат проекций d должна быть преобразована в те же единицы измерения, что и фокусное расстояние и стереобаза, например в метры. Зная физический размер фотоматрицы и её разрешение, можно вычислить размер одного пиксела C в метрах, который затем использовать для преобразования значения диспаритета из пикселов в метры.
Модель восстановления рельефа по стереопаре фотоснимков в общем случае может быть представлена диаграммой, представленной на рисунке 1.2.
Таким образом, при известных параметрах оптической системы (f, B, C) задача восстановления рельефа сводится к задаче установления пиксельных соответствий согласно формуле (1.1). Стереопара изображений
Точность стереосоответствий пикселов является одной из важнейших характеристик технических систем, решающих задачи стереозрения. Для численной оценки точности установленного соответствия существуют два основных подхода. Каждый из них предполагет наличие так называемого «эталона» стереосоответствия стереопары. Здесь и далее «эталоном» будем называть такое стереосоответствие, для которого отличие значений диспаритета от истинных много меньше, чем ожидаемый уровень ошибки алгоритма идентификации пикселов.
Первый подход оценки точности разделяет все соответствия на корректные и некорректные в пределах допустимого интервала погрешности по формуле: N пороговое значения ошибки смещения, dC(x,y) – вычисленная величина смещения пикселя базового изображения с координатами (x,y), dT(x,y) – корректная (эталонная) величина смещения пикселя базового изображения с координатами (x,y), N – общее число точек стереопары.
Второй подход направлен на получение интегральной численной оценки отличия эталона от полученного стереосоответствия. Такой оценкой является среднеквадратическое отклонение, вычисляемое по формуле: RMSE
В наиболее известной на сегодняшний день системе рейтинга алгоритмов нахождения стереосоответствий применяется первый подход, то есть сравнение по доле неверно найденных соответствий [49]. Если точнее, то доля неверно найденных соответствий рассчитывается для точек пространства, присутствующих на обоих изображениях стереопары (не скрытых при смещении камеры) и вблизи перепадов высот. Для этих величин для каждой из четырех стереопар вычисляется ранг в сравнении с существующими алгоритмами. Далее для рангов вычисляется среднее значение, по которому вычисляется итоговый ранг алгоритма.
Метод k-средних (метод главных точек)
Как было сказано выше, функция Census формирует для опорной области двоичный «отпечаток» или двоичный вектор. При сравнении опорных областей фактически вычисляется расстояние Хэмминга между двумя двоичными векторами. По своей сути функция Census соответствует функциям типа «перцептивный хэш». Функции данного типа чаще всего используются для оптимизации поиска изображений в больших базах данных. Для искомого изображения, как правило, вычисляется компактный двоичный вектор (например 64 бита), в котором закодированы так называемые «низкие частоты». После этого в базе данных производится поиск изображений с хэш-значениями равными или близкими к значению хэша искомого изображения. Пример описания таких функций, примеры вычисления значения хэша для изображений приведены в статье Ализара А. «Выглядит похоже. Как работает перцептивный хэш»[11].
Аналогично функции ZSAD целевая функция Census также является контекстно-зависимой. Ключевую роль в формировании двоичного «отпечатка» принимает значение интенсивности центрального пиксела опорного окна, а именно Rp и Lp+d для правого и левого изображения соответственно. В соответствии с формулами (2.8) и (2.9) вычислительная сложность установения стереосоответствия стандартной жадной стратегией на основе функции Census составит 0(Nnmdmax), где N - число пикселов изображения стереопары, п,т -размер опорного окна вокруг пиксела. То есть, при очевидной реализации имеем такую же вычислительную сложность, как у функции ZSAD.
Важной особенностью функции Census является то, что опорные окна представлены в виде двоичных векторов. Пусть Bw и Bw+d - двоичные векторы, описывающие сравниваемые опорные окна так, что каждый бит вектора bq соответствует некоторому пикселу опорного окна q. Пусть бит вектора bq=l только в случае, если интенсивность пиксела q больше интенсивности центрального пиксела опорного окна/?. Тогда итоговое значение функции Census может быть вычислено сл едущим образом: Census(p,d) = 4ucnoEum(BW Є BW+d) (2.18) где ЧислоБит - функция, определяющая число бит, установленных в единицу, а - операция побитового исключающего ИЛИ. Если опорное окно может быть упаковано в стандартный целочисленный регистр процессора, то сложность сравнения двух опорных окон составит 0(1). Сложность предварительного вычисления битовых векторов составляет 0{Nnm). Тогда итоговая вычислительная сложность установения стереосоответствия стандартной жадной стратегией на основе функции Census составит 0(Nnm)+0(NdmaJ, где N - число пикселов изображения стереопары, п,т- размеры опорного окна.
Наиболее точными целевыми функциями оценки подобия опорных окон являются ZSAD, Census и ранговая оценка [32]. Для этих функций можно выделить общее ключевое свойство. Результат вычисления для них является контекстно-зависимым, то есть на результат сравнения некоторой пары пикселов из сопоставляемых опорных окон влияет не только их цвет. В общем случае на результат сравнения пары пикселов влияют соседние пикселы, размер, форма и средняя интенсивность цветовых компонент опорного окна. Именно это свойство обеспечивает большую точность в сравнении с другими целевыми функциями, например SAD. В то же время это свойство ограничивает возможность применения оптимизаций вычисления, таких как метод скользящего окна или метод интегральных массивов.
Стоит отметить важность вопроса применения более точных ресурсоёмких функций сравнения опорных областей и возможности оптимизации их вычисления. Для прояснения данного вопроса нужно провести сравнительную экспериментальную оценку быстродействия и точности. В данном исследовании основными контекстно-независимыми функциями являются функции SAD и SSD, а основной контекстно-зависимой - функция Census. Выбор функции Census объясняется высокой точностью [32], а также возможностью оптимизации с помощью двоичных векторов. Описание эксперимента и его результаты приведены в главе 4 данного исследования. Глава 3 Разработка и исследование метода пространственно-цветовой сегментации изображения и статистического уточнения стереосоответствия стереопары
Практически все наиболее точные алгоритмы установления стереосоответствий являются многошаговыми. Пиксельное соответствие сначала находится в первом приближении, а затем применяются различные подходы его улучшения (refinement steps).
Для компенсации эффекта расширения границ возможно применение минимального фильтра [51]. Для устранения очевидных ложных «всплесков»/«провалов» часто используется медианный фильтр [25]. Однако действия этих фильтров в определенной мере являются противоположными: медианный фильтр усредняет значения, а минимальный фильтр сводит к наименьшему значению в пределах окна. При этом фильтрация производится по всему стереосоответствию независимо от специфики конкретного участка изображения, в том числе там, где это не требуется.
Распространенным альтернативным подходом повышения качества соответствий является рассмотрение пикселов не изолированно, а в группах, выделенных по цветовому признаку. Основой для таких подходов является предположение, что близкорасположенные пикселы похожего цвета принадлежат одному предмету и равноудалены от плоскости съемки. В качестве примера рассмотрим работы, на момент 01.09.2014 занимающие 3, 4 и 5 место в рейтинге портала [49] (на работы, соответствующие первому и второму месту в рейтинге отсутствуют ссылки). Данный рейтинг отражает качество стереосоответствий, но одновременно с этим не учитывает вычислительную сложность применяемых алгоритмов. Так, реализации алгоритмов с наиболее высоким рейтингом демонстрируют производительность порядка десятка секунд и более на стереопару (на процессоре общего назначения). Работа [25] датирована 2011 годом и посвящена разработке итеративного алгоритма установления стереосоответствий. В основе алгоритма лежит сбалансированная компиляция-оптимизация наиболее эффективных техник установления пиксельных соответствий. Особенностями алгоритма являются: композиция цветовой и структурной информации изображения на этапе предварительного расчета соответствия пикселов (AD-Census от «SAD и Census»); метод уточнения стереосоответствия с применением адаптивных окон, сформированных по пространственно-цветовому сходству пикселов; возможность реализации алгоритма на графическом процессоре (GPU). Путем тщательной подборки состава и последовательности шагов алгоритма авторам удается создать алгоритм установления соответствий высокой точности. Основным недостатком алгоритма является его вычислительная сложность: на процессоре Core 2 Duo 2.2GHz обработка одной стереопары занимает от 2,5 до 15 секунд в зависимости от ее размера. Перенос вычислений на графический процессор NVIDIA GeForce GTX 480 позволяет достичь производительности от 16 до 100 миллисекунд на стереопару.
Разработка комплексного алгоритма установления стереосоответствий
Группа методов основана на предположении, что пикселы, соответствующие однородным по цвету областям сцены, компактно локализованы на гистограмме изображения. Сегментация осуществляется путем сопоставления кластеров гистограммы обратно на изображение. Связные области пикселов составляют сегменты изображения.
Основным достоинством данной группы алгоритмов является сравнительно низкая вычислительная сложность, так как для построения гистограммы требуется один проход по пикселам. Недостатком группы алгоритмов является нетривиальность выделения объектов на гистограмме, так как гистограмма отражает только цветовые характеристики пикселов, без учета их расположения на изображении, как показано на рисунке 3.1[58, с. 306-312].
Таким образом, методы сегментации по гистограмме имеют низкую вычислительную сложность только в части построения самой гистограммы. Дальнейшие шаги обработки гистограммы могут оказаться вычислительно сложными в силу необходимости перебора различных вариантов кластеризации гистограммы, нахождения и проверки связности областей и т.д.
Данная группа методов является одной из наиболее хорошо изученных и часто применяемых на практике. Типичный метод группы состоит из двух основных шагов: выделение так называемых «семян» (seeds) и итеративное формирование кластеров вокруг них. Как правило, каждый кластер является связной областью и состоит из пикселов «похожего» цвета. Атомарной операцией данных методов является добавление пиксела, не принадлежащего ни к одному из кластеров к наиболее подходящему кластеру. Критерием сходства может быть расстояние в цветовом пространстве RGB цвета пиксела и среднего значения цвета кластера. Если данное расстояние больше некоторой пороговой величины -пиксел не добавляется к рассматриваемому кластеру. Процесс расширения «семян» продолжается, пока есть пикселы не принадлежащие к какому-либо из кластеров.
В качестве примера рассмотрим алгоритм, представленный в работе [59] (SLIC-SP алгоритм, анг. Simple Linear Iterative Clustering Super Pixels). При разработке алгоритма авторы ставят следующие цели: низкая вычислительная сложность, высокая степень согласованности реальных границ объектов и границ кластеров. По результатам сравнения на различных наборах изображений авторы декларируют превосходство предложенного алгоритма по сравнению с существующими по качеству и производительности. На рисунке 3.2 приведены примеры изображений с выделенными черным цветом границами сегментов для различных режимов работы SLIC-SP-алгоритма.
В основе алгоритма лежит оптимизированный вариант метода -средних. Оптимизация позволяет достичь линейной ассимптотической вычислительной сложности и заключается в следующем: сужение области поиска пикселов относительно центра кластера; применение комбинированного пространственно-цветового критерия сходства пиксела и кластера; постановка исходных центров кластеров в области изображения с наименьшим цветовым градиентом (в области с ровным фоном). Производительность программной модели алгоритма авторы измеряют на изображениях различного размера. По результатам экспериментов подтверждается линейность вычислительной сложности алгоритма и высокая производительность [59, с. 2278]. Сегментация изображения размером 700х600 пикселов на процессоре общего назначения «Intel Dual Core 2.26 GHz» занимает около 2-х секунд. Это лучше, чем у многих алгоритмов сегментации, но неприемлимо для высокопроизводительной системы стереозрения, если время обработки стереопары должно быть менее одной секунды. Приведенная авторами оценка производительности должна быть проверена экспериментально.
В данном диссертационном исследовании проводится разработка и исследование алгоритма сегментации изображения стереопары, также обладающего линейной вычислительной сложностью, но предположительно со значительно меньшей скрытой константой в формуле оценки. Рассмотренный SLIC-SP-алгоритм сегментации представляет научный интерес для сравнения эффективности с предложенным далее алгоритмом многокритериальной сегментации (МКС). Научный интерес обусловлен следующими причинами:
Как правило, на стереопарах изображены объекты реального мира, которые не предназначены для создания оптических иллюзий. Одним из характерных признаков является «одноцветность» в пределах отдельных предметов. Например, книга в одном из частных случаев вся целиком может быть синей. И если это не так, то можно предположить, что расположенные близко пикселы «похожего цвета» принадлежат одному и тому же предмету. Используя данное предположение, разработаем функцию сравнения подобия пикселов.
Функция сравнения должна учитывать близость пикселов и подобие их цветов. Пикселы должны считаться подобными в пределах незначительных изменений цвета и при небольшом/среднем удалении в координатах изображения. При значительном удалении или при значительной разнице в цвете пикселы не должны считаться подобными и соответственно относиться к одному сегменту. Здесь и далее сегментом будем называть связное подмножество пикселов изображения, не имеющее пересечений с другими аналогичными подмножествами.
Рассмотрим функцию вида /О) = е х, где - некоторая положительная константа. Пределами функции на интервале (0, +) являются нуль и единица. Эту функцию можно рассматривать как функцию штрафа от х, где переменная x соответствует некоторой численной оценке различия пикселов, -нормировочный коэффициент для х. Учитывая, что верхний предел функции равен единице, функция F(x)=l-f(x) является функцией подобия пикселов (см. рисунок 3.3).
График функции F(x) при =20 Для объединения критерия расстояния и цветового критерия просуммируем значения соответствующих функций. При этом для оценки подобия пикселов будем использовать Эвклидово расстояние между самими пикселами на изображении и Эвклидово расстояние в цветовом пространстве RGB. В итоге получим функцию вида: F(p,p) = 2-e D -e С( } (3.1) где XD - нормировочный коэффициент расстояния пикселов, Ас -нормировочный коэффициент цветового расстояния пикселов в RGB, D(p,p ) и С(р,р ) - функции вычисления оценок обычного и цветового расстояния пикселов рир .
Для сегментации базового изображения стереопары будем обрабатывать его как планарный невзвешенный неориентированный граф, вершинам которого соответствуют пикселы. Две произвольные вершины графа соединены ребром, если соответствующие им пикселы на изображении являются смежными.
Фактически задача сегментации состоит в разбиении всего множества вершин графа S на подмножества S„, в пределах которых значение функции (3.1) для всех пар вершин (v,-, у,-, /#) не менее некоторой пороговой величины т. В такой постановке задача является сложной в вычислительном плане. Одна только сложность проверки данного условия для произвольного разбиения составляет 0(Nk2), где N - число подмножеств, к - среднее количество вершин в подмножестве. Исследование алгоритмов построения такого разбиения выходит за рамки данной работы. Поэтому в целях упрощения алгоритма сегментации
