Федеральное Агентство Высшего Образования Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

Уральский государственный университет им.

Математико-механический факультет

Кафедра Высокопроизводительных компьютерных технологий

Алгоритм калибровки системы технического зрения.

“Допущен к защите”

___________________

“ “ 2007г
Квалификационная работа на степень бакалавра наук по направлению “Математика, прикладная математика”

Студента группы Мт-408

Научный руководитель

Старший преподаватель кафедры Высокопроизводительных компьютерных технологий.

1. Постановка задачи

Разработать алгоритм, вычисляющий взаимное расположение камер технического зрения по фотографиям калибровочного шаблона и оценить точность калибровки.

Эта задача имеет прикладной характер. На самом деле существует помещение, в котором проверяются на износ железнодорожные тележки. В этом помещении существует система видеокамер, которая с разных точек снимает эти железнодорожные тележки. В данный момент разрабатывается программа, которая по информации с видеокамер производила бы оценку износа тележек. Т. е. оценку отклонений от нормы у данного объекта. Естественно для корректной работы этой системы надо уметь ее калибровать, так как под действием внешних факторов видеокамеры могут быть сдвинуты. Понадобится какой-нибудь объект, снимая который, мы бы и производили калибровку. В качестве этого объекта, для алгоритма приведенного ниже, была предложена плоскость (Рис.1).

Мы знаем все фокусные расстояния видеокамер, знаем размеры помещения и примерное месторасположения видеокамер. Для решения задачи основным параметром видеокамеры является фокусное расстояние, остальными параметрами пренебрегаем. Объектив рассматривается как одна точка.

Была дана полная свобода действий. Т. е. можно потребовать любые величины, к примеру, высоты камер, расстояния между камерами и т. д. Но так как задача имеет прикладной характер, то данные, передаваемые в алгоритм, нужно требовать очень осторожно. Так как угол поворота камеры, относительно каких либо внешних осей координат, померить с достаточно большой точностью не представляется возможным. И в результате мы будем получать огромную итоговую погрешность.

1.1 Входные данные

Дано поле , в углах которого нанесены точки (Рис 1). В каждом углу по 3 точки и известно, что если соединить между собой эти точки, то получится прямоугольный треугольник. В каждой группе точек известно взаимное расположение этих точек. Известны также расстояния от точек, являющихся вершинами треугольников при прямом угле (a, b, c). Также даны четыре видеокамеры, каждая из которых снимает свою группу точек. Нам известны координаты проекций точек на матричную плоскость видеокамеры (по фотографиям). Известны фокусные расстояния для каждой видеокамеры.

Рис 1. Плоскость

2. Общая идея решения

Попытаться связать системы координат разных камер через одну систему координат (глобальную). Для этого нужно связать каждую систему координат видеокамер с глобальной системой путем матрицы преобразований координат. Для этого нужно знать взаимное расположение центров систем координат (глобальной и камерной). Т. е. первоначальная задача – научиться находить координаты видеокамеры в глобальной системе координат.

Далее нужно будет оценить погрешность, которая возникнет при решении, если будем задавать погрешности входных данных.

3. Реализация

Введем систему координат, которую в дальнейшем будем называть глобальной системой координат (Рис. 2). За ось OX возьмем прямую соединяющую угловые точки группы 1 и 2, за ось OY прямую соединяющую угловые точки 1 и 4 группы. Ось OZ направим перпендикулярно плоскости на нас. Таким образом, получили правую тройку XYZ –глобальная система координат.

При таком выборе системы координат можно однозначно определить координаты всех точек на плоскости.

Рис. 2. Глобальная система координат

Рассмотрим, к примеру, видеокамеру, которая снимает группу точек №3. Рассмотрим матрицу видеокамеры (Рис. 3). Через центр локальной системы координат связанной с видеокамерой обозначим центр матрицы. Ось - прямая проходящая через центр матрицы и параллельная горизонтальной границе матрицы. Ось - прямая проходящая через центр матрицы и параллельная вертикальной границе матрицы. Ось - направлена перпендикулярно плоскости матрицы (на нас). Таким образом, правая тройка - локальная система координат связанная с видеокамерой.

Рис. 3.Матрица видеокамеры. Локальная система координат.

При таком выборе локальной системы координат, координаты образов точек группы №3 будут такого вида , а координаты центра линзы видеокамеры , где - это фокусное расстояние данной видеокамеры.

Тогда через точки и точку проведем три прямых. С помощью уравнений (1)

(1)

можно найти уравнение прямой проходящей через две точки. Подставив координаты наших точек, получим уравнения (2).

(2)

Имеем три прямых проходящих через точки на матричной плоскости и центр линзы видеокамеры (Рис.4). Где точка P центр линзы, а M1 M2 M3 образы точек из группы №3 на матричной плоскости.

Рис. 4.

Измерим расстояние между точками в группе №3 (Рис. 5) и через обозначим расстояние между точкой и т. е.

(3)

Рис. 5. Группа точек №3 в глобальной системе координат

Расстояние между точками и равно расстоянию между этими же точками в локальной системе координат. Тогда на прямых из уравнения (2) будем искать такие точки , чтобы выполнялись следующие равенства

(3`)

Т. е. будем искать треугольник как на (Рис.6)

Рис. 6. Треугольник, прообраз которого лежит в

НЕ нашли? Не то? Что вы ищете?

Для этого перепишем уравнение (2) в виде

(4)

где параметры, а .

Тогда подставив в уравнения (3`) уравнения (4) получим

(5)

Раскрыв скобки и возведя в квадрат правую и левую часть получим:

Обозначим через

Получим систему нелинейных уравнений с тремя неизвестными.

(6)

3.1 Метод Ньютона решения систем нелинейных уравнений

Задача решения системы нелинейных уравнений:

задано

найти , такое, что

где предполагается, что F непрерывно дифференцируемо.

Метод Ньютона для задачи решения системы нелинейных уравнений получается из нахождения корня аффинной аппроксимации для F, соответствующей текущему приближению . Эта аппроксимация строится с использованием тех же приемов, что и в случае задачи с одной переменной. Итак,

Поскольку в целях получения аффинной аппроксимации для F относительно приращений p к мы аппроксимируем интеграл линейным членом , то

Затем находится из условия , что дает итерацию метода Ньютона, решения системы нелинейных уравнений. Таким образом, решается система

Т. е. на очередной k-ой итерации надо решить

3.2 Проверка возможности использования метода Ньютона

Рассмотрим (6). Каждая функция непрерывно дифференцируема и

Найдем аналитически

3.3 Начальное приближение

Во многом быстрота отыскания приближенного решения системы нелинейных уравнений зависит от начального приближения. Так же важно начальное приближение и в случае не единственности решения системы.

Заметим, что если точки лежат на одной плоскости, то чем дальше одна из точек от камеры, тем ниже она на матричной плоскости и, на оборот, чем ближе к камере, тем выше.

Воспользуемся этим фактом для нахождения начального приближения для метода Ньютона. Рассмотрим уравнения (4). Каждый из должен быть отрицательным, т. к. при положительном точки на рассматриваемых прямых будут иметь отрицательные координаты по Z, а при все прямые пересекаются в фокусе. Тогда если мы положим , где это параметр при прямой, проходящей через точку с максимальным Y (так как ось направлена в низ), a параметр при прямой, проходящей через точку с минимальным Y, то мы будем искать именно то решение, которое нам надо. Теперь осталось подобрать такие , чтобы метод сошелся как можно быстрее.

3.4 Нахождение плоскости в локальной системе координат

Таким образом, мы имеем , по этим значениям мы можем написать уравнение плоскости, в которой лежат оси OX и OY нами выбранной глобальной системы координат.

(7)

Тогда, уравнение плоскости в локальной системе координат есть

(8)

Теперь наша задача найти координаты центра локальной системы координат в глобальной системе координат. Для этого опустим перпендикуляр из центра локальной системы координат на найденную нами плоскость (8). Найдем точку пересечения этой перпендикулярной прямой и плоскости и посчитаем длину между точкой пересечения и центром локальной системы координат.

Уравнение прямой, перпендикулярной плоскости и проходящей через точку , имеет вид

(9)

Значит, уравнение прямой проходящей через начало координат и перпендикулярной плоскости (8), имеет вид

(10)

Теперь введем параметр

(11)

Подставим эти значения в уравнение плоскости (8) и выразим

Теперь подставим вычисленный обратно в (11) и получим координаты точки пересечения перпендикуляра и плоскости . Рассмотрим уравнения прямых и . В глобальной системе координат эти прямые были параллельны осям OX и OY соответственно. Значит и в локальной системе координат они остались параллельны. Если мы опустим перпендикуляры от точки до этих прямых (найдем d2 d3) и затем вычтем из координат точки (d2 вычтем из , а d3 из ) найденные расстояния, то получим координаты центра локальной системы координат в глобальной системе координат.

Уравнения прямых и имеют вид

i=2,3 (12)

Уравнение длины перпендикуляра от точки до прямой имеет вид

(13)

Тогда координаты центра локальной системы координат в глобальной системе координат имеют вид

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

(14)

Будем иметь три системы линейных уравнений, в каждой из которых по три неизвестных

(15)

Таким образом, однозначно определим матрицу перехода

(16)

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

Построим матрицу обратную для матрицы . Определитель матрицы равен

(17)

Тогда матрица будет иметь вид

,

(18)

где каждый элемент есть

,

(19)

а каждый элемент - алгебраическое дополнение элемента матрицы

Тогда возьмем точку с координатами (0,0,1) в локальной системе координат и переведем ее в глобальную систему координат умножив на матрицу и прибавим координаты центра локальной системы координат в глобальной. Построим уравнение прямой, соединяющую полученную точку и центр локальной системы координат.

Найдем углы между получившейся прямой и осями OX, OY, OZ по формуле

(20)

Где - направляющие коэффициенты. Из (20) следует, что углы между прямой и осями OX, OY, OZ соответственно равны

(21)

Но этих углов недостаточно, чтобы точно определить положение камеры. Переведем из локальной системы координат точку (1,0,0) и найдем угол наклона между осью OZ и прямой соединяющую образ (1,0,0) и центр локальной системы координат в глобальных координатах. Теперь мы знаем о локальной системе координат все!

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

4. Погрешность

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

Воспользуемся известными формулами. Даны две величины с абсолютной погрешностью

тогда, сумма этих величин равна

,

а абсолютная погрешность суммы и разности есть сумма абсолютных погрешностей

Произведение есть

тогда абсолютная погрешность произведения равна

А относительная погрешность частного - есть сумма относительных погрешностей делимого и делителя

При нахождении величин получаем абсолютную погрешность вида

,

обозначим эту погрешность через .

Далее эти используются в уравнениях (6), которые решаются с помощью метода Ньютона. Тогда каждая величина из уравнения (4) будет иметь погрешность такую же, как и .

Тогда уравнение плоскости (8) получаемое из уравнения (7) будет иметь абсолютную погрешность

,

где элемент i – ой строки j – го столбца определиА тогда и все точки на этой плоскости будут иметь абсолютную погрешность такую же как и сама плоскость.

Тогда абсолютная погрешность высоты камеры над плоскостью будет равна

5. Заключение

Итак, если мы знаем координаты 3-х точек на плоскости и координаты этих же трех точек на матричной плоскости , то

1.  по координатам точек и зная фокусное расстояние используя формулу (1) построим прямые вида (2).

2.  По (3) найдем расстояния между точками и подставим получившиеся значения в (3`).

3.  Подставим в уравнение (3`) уравнения (4) получим уравнения вида (5).

4.  Преобразовав получившиеся уравнения, получим систему вида (6).

5.  Систему вида (6) будем решать численно с помощью метода Ньютона для систем нелинейных уравнений.

6.  Из метода Ньютона получим . Подставим эти в (4) получим координаты точек лежащих на образе плоскости в локальной системе координат. Т. е. точки с координатами .

7.  Подставив точки в (7) получим уравнение плоскости (8).

8.  Построим уравнение прямой, перпендикулярной найденной плоскости и проходящей через начало локальных координат. Т. е. по (9) используя (8) и точку получим уравнения прямой вида (10).

9.  Находим координаты точки пересечения плоскости (8) и прямой (10) .

10.  Найдем расстояние между и , получим координату видеокамеры в глобальной системе координат по оси Z.

11.  Используя (12) и подставляя точку в (13) мы находим d2 и d3.

12.  Тогда координаты видеокамеры в глобальной системе координат есть .

13.  Получаем точки и используя координаты точек переходим к решению (14).

14.  Решив системы (15) мы однозначно определили матрицу преобразований координат (16)

15.  С помощью (17), (18), (19) строим обратную матрицу к матрице (16)

16.  Используя уравнения(20) и координаты нормали видеокамеры в глобальной системе координат получаем (21)

И так мы научились определять координаты точек в локальной системы координат зная их глобальные координаты и на оборот. Теперь остается проделать тоже самое с остальными видеокамерами и перевести все координаты в глобальную систему координат.

6. Пример

Рассмотрим пример пусть в глобальной системе координат координаты точек соответственно равны (5,5,0),(4,5,0),(5,4,0). Координаты центра матрицы видеокамеры (4,4,4) и центра линзы (4,4,3). Тогда в глобальной системе координат проекции точек на матричную плоскость есть (11/3;11/3;4), (4;11/3;4), (11/3;4;4). А в локальной системе координат связанной с видеокамерой эти координаты представляются так (1/3;1/3;0), (1/3,0,0), (0,1/3,0). А координаты центра линзы есть (0,0,1)

Тогда используя (4) получаем

А система (6) имеет вид

Решая численно методом Ньютона получаем

Тогда координаты точек есть соответственно (-1,-1,4), (-1,0,4), (0,-1,4)

Плоскость являющаяся образом имеет вид

Уравнение перпендикуляра к плоскости проходящего через начало координат , тогда точка пересечения имеет координаты и высота камеры в глобальной системе координат равна 4.

Расстояния до прямых параллельных глобальным осям координат .

Тогда координаты камеры в глобальной системе координат имеют вид

, что совпадает с начальными предположениями.

Затем строим матрицу перехода. Она равна и убеждаемся, что если из начала глобальных координат вычесть координаты камеры (получаем (-4,-4,-4)) и умножить на матрицу перехода справа, то получим координаты в локальной системе координат (4,4,4).

Решение с погрешностью

Введем погрешность

Тогда , а координаты точек равны

Тогда уравнение плоскости имеет вид

,

Тогда а высота камеры в глобальной системе координат есть , т. е. если за единицу принять 10см то абсолютная погрешность высоты есть или 3,8 мм при начальной абсолютной погрешности в 0,5мм.