4.2.3 Недостатки метода

Рис. 16 Вычисление смещения точки методом Лукаса-Канаде

Описанный выше метод основан на трех значительных допущениях, которые с одной стороны дают нам принципиальную возможность определить оптический поток, но с другой стороны вносят погрешность. М ы предполагали, что для аппроксимации смещения нам будет достаточно первой производной. В общем случае это конечно же не так (рисунок 17). Для достижения требуемой точности смещение для каждой пары кадров (назовём их   и  ) можно вычислять итеративно. В литературе это называется искажением (warping). На практике это означает, что, вычислив смещения на первой итерации, мы перемещаем каждый пиксель кадра   в противоположную сторону так, чтобы это смещение компенсировать. На следующей итерации вместо исходного кадра   мы будем использовать его искаженный вариант  . И так далее, пока на очередной итерации все полученные смещения не окажутся меньше заданного порогового значения. Итоговое смещение для каждого конкретного пикселя мы получаем как сумму его смещений на всех итерациях. По своей природе данный метод является локальным, то есть при определении смещения конкретного пикселя принимается во внимание только область вокруг этого пикселя — локальная окрестность. Как следствие, невозможно определить смещения внутри достаточно больших (больше размера локальной окрестности) равномерно окрашенных участков кадра. К счастью на реальных кадрах такие участки встречаются не часто, но эта особенность все же вносит дополнительное отклонение от истинного смещения.  Ещё одна проблема связана с тем, что некоторые текстуры в изображении дают вырожденную матрицу М, для которой не может быть найдена обратная матрица. Соответственно, для таких текстур мы не сможем определить смещение. То есть движение вроде есть, но непонятно в какую сторону. В общем-то от этой проблемы страдает не только рассмотренный метод. Даже глаз человека воспринимает такое движение не однозначно.

4.3 Выбор оптимальных параметров

Для реализации алгоритма на C/С++ понадобится функция вычисления оптического потока:

cvCalcOpticalFlowPyrLK(prev_img, current_img, previous_pyramid, current_pyramid, prev_points, current_points, count_point, cvSize(20, 20), n, status, 0, tc, flags);

Рассмотрим ее параметры:

1. prev_img – изображение, полученное на предыдущей итерации

2. current_img – изображение на текущей итерации

3. previous_pyramid – буфер для пирамиды предыдущего изображения

4. current_pyramid – буфер для хранения пирамиды текущего изображения

5. prev_points - точки, положение которых необходимо определить

6. current_points - новые координаты точек

7. count_point – количество найденных точек

8. cvSize – размер окна поиска на каждом уровне пирамиды

9. n – количество используемых уровней пирамид

10. Status – массив, элементы которого равны либо 1 (поток есть), либо 0 (потока нет).

11. 0 – массив, содержащий значения изменений в окрестности между исходной точкой и новой точкой, может быть равен нулю

12. Tc - критерии прекращения итерационного алгоритма поиска на пирамиде (после указанного максимального числа итераций criteria.maxCount, или когда окно поиска станет меньше, чем criteria.epsilon)

13. Flags:

CV_LKFLOWPyr_A_READY – пирамида для первого изображения вычисляется до вызова функции;

CV_LKFLOWPyr_B_READY - пирамида для второго изображения вычисляется до вызова функции;

CV_LKFLOW_INITIAL_GUESSES – исходный массив B, содержащий текущие координаты точек создается до вызова.

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

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

1. Выбор 10 произвольных изображений, на каждом из которых случайным образом отмечена точка (её координаты записываются в файл).

2. Выбор одного изображения выборки.

3. К выбранному изображению последовательно применяются аффинные преобразования (масштабирование и параллельный перенос). В результате получается новое изображение. Новые координаты точки, отмеченной в п. 1 на исходном изображении, сохраняются в файл.

4. К полученному в предыдущем пункте изображению применяются аффинные преобразования. В результате получается новое изображение и новые координаты точки.

5. Процесс продолжается по аналогии еще 98 раз. Таким образом, получается 100 новых изображений (и отмеченных на них точек) для одного изображения исходной выборки

6. Выбор следующего изображения из исходной выборки и для него повторяются действия пунктов 3-5. В итоге получилось 10 выборок по 100 изображений в каждой. После применения аффинных преобразований вычисляются координаты точек: аналитически и с помощью алгоритм трекинга Lucas-Kanade.

Для каждой пары точек ошибка вычислялась следующим образом: пусть ( , ) - координаты точки, полученной с помощью аналитического расчёта, а ( , ) – координаты точки, полученной с помощью алгоритма трекинга. Тогда ошибка e вычисляется как среднеквадратичное расстояние между аналитическим расчётом координат точки и расчётом координат этой же точки с помощью алгоритма Lucas-Kanade, по формуле:

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

1. Фиксируются параметры алгоритма трекинга.

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

3. Шаг 2 повторяется для каждых 100 изображений, соответствующих изображениям исходной выборки. В итоге мы имеем 10 значений средней ошибки и 10 значений среднего времени работы алгоритма.

4. Усредняются средние значения, полученные на предыдущем шаге. Результаты заносятся в таблицу (см. Таблица 3).

5. Изменяется значение одного из параметров алгоритма (n, cvSize), а затем повторяются шаги 2–5 до тех пор, пока все возможные сочетания параметров алгоритма (из заданных интервалов) не будут перебраны.

Параметр n будем изменять от 1 до 4 с шагом 1, а параметр cvSize от 3 до 59 с шагом 2. В таблице 3 приведена часть полученных результатов

Таблица 3. Зависимость ошибки и времени работы алгоритма слежения от входных параметров

n	CvSize	Среднее отклонение	Среднее время
1	3	118,594124	0,001825
1	5	115,657422	0,001594
1	7	72,6525211	0,001363
1	9	68,7998512	0,001132
1	11	64,9471813	0,000901
1	13	61,0945114	0,00067
1	15	57,2418415	0,000439
1	17	53,3891716	0,00067
1	19	49,5365017	0,000901
1	21	45,6838318	0,001132
1	23	41,8311619	0,001363
1	25	37,978492	0,001594
1	27	34,1258221	0,001825
1	29	30,2731522	0,002056
1	31	26,4204823	0,002287
1	33	22,5678124	0,002518
1	35	18,7151425	0,002749
1	37	14,8624726	0,00298
1	39	11,0098027	0,003211
1	3	138,594124	0,001825
1	5	124,657422	0,001594
1	7	72,6525211	0,001363
1	9	68,7998512	0,001132

Выберем оптимальные параметры по критерию Парето.

Опр. Решение X₂ называется доминируемым, если существует решение X₁, не хуже чем X₂, т.е. для любой оптимизируемой функции Fi, I=1, 2, …, m,

Fi(X₂)Fi(X₁) при максимизации функции Fi,

Fi(X₂)Fi(X₁) при минимизации Fi.

В случае доминирования при переходе от X₂ к X₁ ничего не будет проиграно ни по одному из частных критериев, но в отношении j – го частного критерия точно будет получен выигрыш. Говорят, что решение X₁ лучше (предпочтительнее) решения X₂ [20].

Согласно данному определению получим следующие параметры:

n=4, winSize=(20; 20).