Диссертация (1090939), страница 4
Текст из файла (страница 4)
Предположим, что камера находится водномерномпространстве,иееположениехарактеризуетсяоднойпеременной x . Тогда p (x ) будет распределением вероятности x , имеющимгауссовуформу.Теперь,еслиx22отражаетположениекамерыиотносительные положения ориентиров в многомерном пространстве, тораспределение вероятностивозможныхпеременныхp (x )будет определять вероятности всехсостояния.Такимобразом,законp ( x | u 0 , u1 ,..., ui , z 0 , z1 ,..., zi ) описывает вероятности всех величин текущегосостояния системы – показаний датчиков и информации о перемещениикамеры, полученных в момент времени i .
Ту же роль играют величины Pi иX i в расширенном Фильтре Калмана, однако там они представлены взначительно более сложной форме. Для удобства введем обозначенияU i = {u 0 , u1 ,..., ui }иZ i = z 0 , z1 ,..., z i .Переменнаяxвсвоюочередьхарактеризует положение камеры v и положения ориентиров p0 , p1 ,..., pm .Вероятность p ( x | U i , Z i ) можно представить в следующем виде:p( x | U i , Z i ) = p(v, p0 , p1 , pm | U i , Z i ).Для упрощения задачи SLAM удобно воспользоваться законами изоснов теории вероятностей.
Предположим, что есть две независимыеслучайные величины A и B . Можно сказать что p( A, B) = p( A) * p( B) . Ноэто выражение несправедливо для случая, когда A зависит от B . В этомслучае оно будет иметь вид p( A, B) = p( A) * p( B | A) . Как известно, оценкаположения ориентиров зависит от оценки положения робота, а это значит чтовыражение(1) можно представить в следующем виде:p (v, p0 , p1 , p m | U i , Z i ) = p (v | U i , Z i ) p ( p0 , p1 , p m | U i , Z i ).В силу независимости наблюдений ориентиров друг от друга, что вреальных условиях соблюдается в большинстве случаев, можно разделитьp ( p0 , p1 ,..., pm | U i , Z i , ) на m независимых выражений:p(v | U i , Z i ) p( p0 , p1 , pm | U i , Z i ) =p(v | U i , Z i ) p( p0 | U i , Z i ) p( p1 | U i , Z i )...
p( pm | U i , Z i ).Итоговое выражение для описания распределения вероятности имеетследующий вид:23p ( x | U i , Z i ) = p (v | U i , Z i ) m p ( p m | U i , Z i ) .Анализ полученного выражения показывает, что проблема SLAMможет быть разбита на m 1 задач, в результате чего ни одна из оценокположения ориентира не зависит от других оценок. Это свойстворассматриваемой задачи позволяет решить проблему полиномиальнойсложности алгоритма, характерную для решения на основе расширенногофильтра Калмана, и избежать ее в FastSLAM. Единственная цена, которуюприходится платить за такое упрощение – это возможность паденияточности,связаннаясигнорированиемкорреляцииошибокоценкиположений ориентиров.
Алгоритм FastSLAM обрабатывает целый рядвозможных маршрутов камеры одновременно, в то время как расширенныйфильтр Калмана работает с положением робота – последним шагом текущегомаршрута. В оригинальном виде FastSLAM сохраняет маршрут, но ввычислениях использует только предыдущий шаг.Применение фильтра частицДля рассматриваемой практической задачи, более точная оценкасостояния системы требует уйти от предположения, что шум имеет Гауссовораспределение[84].Вэтомслучаепредлагаетсяввестипонятиемультимодального распределения шума, как распределения, обладающегонесколькими локальными максимумами. Для моделирования подобныхсистем используются фильтры частиц.
Фильтры частиц являются болееобщим подходом к решению задачи сопровождения с применениемвероятностных методов [25, 82]. Базовым алгоритмом фильтра частиц, накотором строится большинство подобных алгоритмов технического зренияявляется алгоритм воспроизведения условной плотности [46]. Далеерассмотрим в общих понятиях принцип его работы.Пусть система может находиться в состояниях X t = ( x1 , x2 ,... xt ) и вмомент времени t характеризуется определенным значением плотности24вероятности. Так же, как и при использовании фильтра Кальмана,последовательность наблюдений имеет вид Z t = ( z1 , z 2 ,...
z t ) . Наряду с этимвведем предположение о том, что состояние системы зависит только от еепредыдущего состояния x t 1 , то есть она удовлетворяет условию Марковскойцепи.Такимобразом,получаемсистемуснезависимымнаборомнаблюдений.Рис. 1.3. Итерации алгоритма воспроизведения условной плотностиТехника фильтрации частиц представляет распределение вероятности ввиде коллекции взвешенных выборок, называемых частицами. Генерациятаких выборок регулируется посредством введения весов. Определимфункцию плотности вероятности для состояния x t при заданном наборенаблюдений S t как множество S t :S t = {( S it , it ), i = 1, N , i=1 it = 1}.NЗадача сводится к построению метода восстановления множества StиспользуяSt-1.Формальноалгоритмможнопоследовательности определенных шагов [46, 82].25представитьввиде1. Пусть имеется некоторая коллекция взвешенных выборок в моментвремени t 1 :St 1 = {( Sit 1 , it 1 ), i = 1, N , i=1 it 1 = 1}.N2.
Вычисление интегральных весов:ci = ci1 it 1 , i = 1, N , c0 = 0.3. Определение n -ого экземпляра выборки S t . Для этого случайнымобразомвыбираетсячислоизrотрезка[0..1]ивычисляетсяj = argmin i ( xi > r ) . Отсюда известна текущая оценка состояния s tj1 .4. Предсказание следующегосостояния. Действие аналогичноефильтру Калмана за исключением того, что в данном случае нетограничений, связанных с линейностью системы и видом распределенияшума:Snt = Ft 1Sit 1 wt 1 .5. Коррекция с помощью текущего наблюдения z t и его распределения.Вес определяется следующим образом: nt = p( zt | xt = xnt ).6. Нормализация последовательности весов itдля выполненияравенства: Nti =1 i= 1.Вычисление наилучшей оценки для состояния x t как линейной сверткиполученного набора экземпляров выборки:xt = i =1 it sit .NОписанный процесс можно проинтерпретировать графически сиспользованием понятия частицы (рис.
1.3). На входе итерации алгоритмаимеется множество частиц (sit 1 , it 1 ) (верхний уровень диаграммы). Врезультате N -кратного случайного выбора частиц из S t 1 получается26некоторый набор экземпляров (2-ой уровень сверху). Применение шагапредсказания приводит к формированию множества оценочных состоянийчастиц (3-ий уровень), затем для каждой оценки выполняется коррекция наосновании имеющихся наблюдений. Как следствие, создается множествочастиц(sit , it )в следующий момент времени(последний уровеньдиаграммы).1.3.Детекторы и дескрипторы особых точекВ решениях задачи одновременной локализации и картирования,основанных на использовании телевизионной системы в качестве основногосенсора, в качестве естественных ориентиров пространства выступаютлокальныеособенностиизображений–особыеточки.Проблемыдетектирования и описания особых точек для дальнейшего распознаваниясоставляютширокуюобластьисследований.Втекущемразделерассматриваются основные современные алгоритмы детектирования иописания особых точек изображений.1.3.1.
Алгоритмы детектирования особых точекДля определения на изображении областей, обладающей некоторойинтерпретируемой информацией, необходимо ввести понятие особой точки,как важной локальной особенности изображения. Особая точка m , илиточечная особенность изображения, характеризуется тем, что некоторая ееокрестность O ( p n ) обладает уникальными особенностями, позволяющимиотличить ее от окрестности любой другой точки изображения O ( p m ) .
Вкачестветакойокрестностибольшинствоалгоритмовиспользуетпрямоугольное окно с центром в рассматриваемой точке и размером стороныот 3 до 7 пикселей. Процесс определения и сопровождения особых точекпроисходит с использованием детектора и дескриптора. Детекторомназываетсяметодизвлеченияособыхточекизизображения,обеспечивающий инвариантность определения одних и тех же особенностей27относительно преобразований изображений. Идентификация особой точкиобеспечиваетя дескриптором, выделяющим её из остального множестваособых точек.
В свою очередь, дескрипторы должны обеспечиватьинвариантностьнахождениясоответствиямеждуособымиточкамиотносительно преобразований изображений [89].В 2008 Tuytelaars и Mikolajczyk [90] определили перечень требований кособым точкам в виде следующих свойств: Повторяемость (repeatability) – особая точка находится в одном и томже месте сцены или объекта изображения, несмотря на измененияточки обзора и освещённости. Отличительность / информативность (distinctiveness/informativeness) –окрестности особых точек должны иметь большие отличия друг отдруга, так, чтобы возможно было выделить и сопоставить особыеточки. Локальность (locality) – особая точка должна занимать небольшуюобластьизображения,чтобыбытьуменьшитьвероятностьчувствительности к геометрическим и фотометрическим искаженияммежду двумя изображениями, снятых в различных точках обзора. Количество (quantity) – число обнаруженных особых точек должнобыть достаточно большим, так чтобы их хватило для обнаружениядаже небольших объектов.
Однако оптимальное количество особыхточекзависитотпредметнойобласти.Видеалеколичествообнаруженных особых точек должно адаптивно определяться сиспользованиемпростогоиинтуитивногопорога.Плотностьрасположения особых точек должна отражать информационноесодержимоеизображения,чтобыпредставление.28обеспечитьегокомпактное Точность (accuracy) – обнаруженные особые точки должны точнолокализовываться, как в исходном изображении, так и взятом в другоммасштабе. Эффективность (efficiency) – время обнаружения особых точек наизображении должно быть допустимым в критичных по времениприложениях.Одним из наиболее распространенных типов особых точек являютсяуглы на изображении [82], т.к. в отличие от ребер углы на паре изображенийможно однозначно сопоставить.