Диссертация (1091367), страница 8
Текст из файла (страница 8)
В данном случае было выбрано 3 кластера.472.4. Структурная схема и описание этапов работы системы2.4.1. Упрощенная схема работы алгоритмаУпрощенная блок схема алгоритма представлена на рис. 2.4.11Получаем изображение22Фильтрация изображения33Перевод в HSV44Построение трапецоида55Кластеризация трапецоида66Построение центров кластеров втрапецоиде77Считаем расстояние Махаланобиса до ближайшегокластера88Маркировка пикселей пола ипрепятсвийРис.
2.4. Упрощенная версия алгоритмаДляначалаработынужнополучитьвходноеизображениестелевизионной камеры, установленной на мобильной платформе (блок 1): это48может быть как видеопоследовательность, так и просто статическоеизображение, в случае, если платформа стоит на месте.Затем идет фильтрация изображения (блок 2).
Блок-схема фильтрапредставлена на рис. 2.5. Она представляет собой обычную схему децимациииинтерполяции(применение ФНЧ,удалениелишнейинформации,увеличение сигнала пустыми отсчетами и интерполяция с помощью ФНЧ).Применение этого фильтра обусловлено тем, что после него схожие по цветуобластибудутмаксимальнооднородны,чтоактуальнодлязадачкластеризации.Применение фильтраГаусса 5*5Применение фильтраГаусса 5*5ДецимацияизображенияУвеличение размераизображенияРис. 2.5.
Блок-схема фильтраПри применении фильтра Гаусса значение пикселя [х, у] взвешиваетсяс использованием весовой функции:d2 21g ( x, y ) e 2 ,2где d ( x xc )2 ( y yc )2– представляет расстояние пикселя [х, у] отцентрального пикселя окрестности [хс, ус] на выходном изображении, дляформирования которого применяется фильтр.Отфильтрованное изображение можно перевести из цветовой системыRGB (красный, синий, зеленый) в цветовую систему HSV (оттенок,насыщенность, яркость) – блок 3. Как этот переход влияет на работуалгоритма, будет показано позже.49Для анализа подстилающей поверхности, на которой отсутствуютпрепятствия, на изображении выделяется трапецоид (блок 4). Эта процедурапродемонстрирована на рис.
2.6.Рис. 2.6. Выделение трапецоидаОбласть трапецоида разделяется на 3 кластера (блок 5) с помощьюалгоритма K-means.Для всех пикселей изображения считаем расстояние Махаланобиса d доближайшего кластера. Для каждого кластера в трапецоиде рассчитываетсясреднее расстояние Махаланобиса d’ для всех точек, принадлежащихкластеру (блок 7). Далее выполняется пометка пикселей, не представляющихпрепятствия (блок 8) рис. 2.7. Если следующее условие выполнено, топиксель считается подстилающей поверхностью, иначе – препятствием:d d ' .(2.1)Для пояснения выбора расстояния Махаланобиса вместо евклидовогорасстояния, рассмотрим, что оно из себя представляет.Рассмотрим задачу нахождения вероятности того, что некоторая точкав N-мерном евклидовом пространстве принадлежит множеству, заданномунабором точек, которые точно принадлежат данному множеству.
Если найтицентр масс множества, то интуитивно понятно, что, чем ближе точка кцентру масс, тем больше вероятность того, что она принадлежит множеству.50Рис. 2.7. Разметка подстилающей поверхностиЧтобы понять, насколько значимо расстояние между заданной точкой ицентром масс, необходимоучитывать размеробласти, на которойрассредоточены точки множества. Самый простой подход заключается ввычислении среднеквадратического отклонения (СКО) точек множества отцентра масс.
Если расстояние между заданной точкой и центром массменьше СКО, то можно заключить, что вероятность принадлежности точкимножеству высока. Чем дальше точка, тем больше вероятность того, что онане принадлежит множеству.Этот интуитивный подход можно определить математически черезрасстояние между заданной точкой и множеством по формуле ( x ) / . Спомощью подстановки этого значения в нормальное распределение можнонайти вероятность принадлежности точки множеству.Недостаток такого подхода заключается в том, что используетсяпредположение о сферическом распределении точек множества сферическивокруг центра масс (равномерно по всем измерениям).
В случае несферическогораспределения(например,эллипсоидальное),естественнымучитыватьвероятностипринадлежностивбылонебытолькорасстояние до центра масс, но и направление на него. В направлениидлинной оси эллипсоида заданная точка должна быть дальше от центра масс,чтобы принадлежать множеству, в то время как в направлении короткой осиона может быть ближе.51Для записи этого в математическом виде эллипсоид, лучшим образомпредставляющий вероятностное распределение множества, может быть заданматрицейковариациймножества.РасстояниеМахаланобиса—эторасстояние между заданной точкой и центром масс, делѐнное на ширинуэллипсоида в направлении заданной точки [95].Формально же, расстояние Махаланобиса от многомерного вектораx x( x1 , x2 , , xn )T до множества со средним значением x( 1 , 2 , , n )Tиматрицей ковариации S определяется следующим образом:DM x ( x )T S 1 ( x ) .ТакжерасстояниеМахаланобиса можноопределить какмерунесходства между двумя случайными векторами и из одного распределениявероятностей с матрицей ковариации S: d x , y ( x y)T S 1 ( x y) .В том случает, когда матрица ковариации является единичнойматрицей, то расстояние Махаланобиса равняется расстоянию Евклида.Когда матрица ковариации имеет диагональный вид (но необязательноединичный), то получившаяся мера расстояния является нормализованнымрасстоянием Евклида [96]: d x, y Ni 1( xi yi ) 2 i2.Здесь σi — среднеквадратическое отклонение xi от yi в выборке.Таким образом, при расчете расстояния Махаланобиса от конкретногопикселя изображения до найденного кластера будет учитываться не толькоцентр масс кластера, но также и распределение точек внутри кластера.522.4.2.
Расчет моделей подстилающей поверхностиСледует отметить, что если на каждом кадре анализировать изменения,происходящее с эталонным участком, то система будет устойчива кизменениям освещенности. Такие изменения могут происходить из-заприближенияподстилающейкисточникусвета(будетменятьсяповерхности).Такжеизменениеосвещенностьосвещенностиможетпроявляться при изменении времени суток. Таким образом, надо хранитьинформацию об изученных с текущего кадра цветовых моделях. Те модели,которые хранятся в памяти в течение нескольких кадров, назовемизученными моделями (их изучили и запомнили). Затем происходитобновление изученных моделей с помощью моделей, полученных натекущем кадре.
Алгоритм обновления представлен на рис. 2.8.В качестве параметров, характеризующих модель, выберем:1.Число пикселей из трапецоида, попавших в заданный кластер.2.Процент пикселей, попавших в кластер, по отношению к общемучислу пикселей.3.Матрицу ковариации кластера.4.Среднеезначениепикселей,попавшихвкластер,посоответствующим цветовым компонентам.Все эти показатели необходимы для удобства обновления информациипо изученным моделям.Сначала происходит удаление всех старых моделей (тех, которыесуществует более 30 кадров).
Далее перебираются все обучаемые модели исравниваются с изученными моделями. Если модели похожи, то ониобъединяются, и «вес» модели увеличивается, иначе замещается одна изустаревших моделей. Для сравнения моделей используется коэффициент S,рассчитываемый следующим образом:M D MT M L ,CD CT CL ,53S M DT CD1M D ,гдеM T – вектор средних значений для обучаемой модели,M L – вектор средних значений для изученной модели,CT – матрица ковариации для обучаемой модели,C L – матрица ковариации для изученной модели.Удаление старых изученных моделей( существует дольше 30 кадров)22Перебираем обучаемыемодели33Рассчитываем коэффициентпохожести S44Хотя бы для однойS<1НетОбновление недействительноймодели или модели с наименьшим NT55 ДаОбновление соответствующей моделиРис.
2.8. Алгоритм обновления моделейПри обновлении одной из уже существующих моделей ее показатели54перерассчитываются:M NL M T NT M L N L,NT N LС NL СT NT СL N L,NT N LN NL NT N L ,гдеNT – число пикселей обучаемой модели,N L – число пикселей изученной модели,M NL – новый вектор средних значений,C NL – новая матрица ковариации,N NL – новое число точек.Отметим, что число изученных и текущих моделей может быть разным.Число текущих моделей может быть значительно меньше, чем числохранимых моделей.
По типу заполнения изученных моделей можно выделитьнесколько режимов работы системы:1Полностью эвристическое – изначально в памяти нет ни однойизученной модели, вся информация получается в ходе работы системы.2Езда в полностью изученном помещении – в данном режимесистема не обучается, а использует изначально заложенную в нееинформацию, полученную в ходе предыдущего обучения.3модели,Езда с обучением – в памяти есть определенные цветовыекоторыевсегдабудутвосприниматьсякакподстилающаяповерхность, но при этом система может дополнительно обучаться, чтобыотслеживать непредвиденные изменения освещенности (которые могутвозникнуть вследствие скачка освещенности).552.5. Алгоритм удаления тениУсловия освещения вызывают проблемы для многих алгоритмовкомпьютерного зрения [75, 76, 81].
В частности, тени на изображении могутвызвать ошибки в алгоритмах сегментации, отслеживания и распознавания.Инвариантное к освещению изображение очень полезно в широкомдиапазоне проблем компьютерного зрения и компьютерной графики. Однакочтобы найти инвариантное изображение, требуется калибровка, и этоограничивает применимость метода. В этом разделе будет рассмотрен метод,позволяющий найти инвариантное изображение без калибровки камеры,даже если ничего не известно об изображении.На сегодняшний день большинство методов опираются на схемыкалибровки для конкретного цвета камеры.
Они исходят из того, чтопредставляют изображение как набор цветовых пятен. Изображениязахватываются при различных вариантах освещения – чем большеисточников, тем лучше. Знание того, что все это изображение одной и той жесцены при различных условиях освещения позволяет построить всезахваченные RGB значения для каждого пикселя как изменение освещения.Если пиксели сначала перевести из 3D пространства RGB в 2D пространствоцветности {G / R, B / R} , а потом взять от них логарифм, то значения приразличных условиях освещения отображаются в виде прямой линии на 2Dграфике. И, как оказывается, все подобные линии параллельны для заданнойкамеры.Если изменение освещенности представляет собой движение по такойлинии, то тогда, чтобы получить инвариантное к освещению изображениенужноспроецировать2Dточкицветностинанаправление,перпендикулярное к этим линиям.