Трёхмерны сканер. Построение трёхмерной модели по двумерному изображению с лазерным «зайчиком». С учётом явления перспективы.

Нецветаев Д.С. Школа 135, ВНИИТФ.

Содержание.

Введение

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

Вводится система координат, связанная с камерой. Удобней всего в качестве начала координат О выбрать центр входного зрачка камеры, а ось Z направить ровно по оптической оси камеры от матрицы во внешний мир. Ось X выбирается так, чтобы она проходила через О, была перпендикулярна оси Z и лежала в плоскости, параллельной горизонтальным рядам пикселей матрицы. Положительное направление вправо. Ось Y выбираем также, её плоскость параллельна вертикальным рядам пикселей. Положительное направление вверх.

На изображении вводим двумерную систему отсчёта X’O’Y’. Центр O’ помещается в центр кадра (граница 640 и 641 пикселей по горизонтали и аналогично граница 480 и 481 пикселей по вертикали для матрицы 1280 на 960). Ось X’ горизонтальная вдоль горизонтальных рядов пикселей матрицы, с положительным направлением вправо. Ось Y’ вертикальная, вдоль вертикальных рядов пикселей, положительное направление вверх.

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

Задача №1. Написать выражение, связывающее координаты заданной точки А (A_x, A_y, A_z) и координаты её изображения (A’₁, A’₂).

Схема размещения точки А и её изображения приведена на рисунке ниже. Представлен вид сверху. В точку А на схеме идёт лазерный луч. Но для дальнейшего использования это совершенно неважно. На схеме С – это точка на оси Z, имеющая ту же z –координату, что точка А. Предполагается, что фокусное расстояние f камеры известно и выражено в пикселях (f=1545.1 пикселей для угла обзора 45^о), и что физические размеры пикселя по горизонтали и вертикали одинаковы. Координаты изображения точки А выражены в пикселях, A’₁ – горизонтальная координата, A’₂ – вертикальная. Координаты в трёхмерном пространстве заданы в мм.

Используя подобие прямоугольных треугольников OO’A’ и OAC, можно написать

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

Схема выглядит аналогично при взгляде «сбоку», поэтому из подобия соответствующих треугольников можно написать аналогичные уравнения для вертикальных координат

Окончательно можно написать следующие выражения, связывающие координаты точки и её изображения

В виде векторов – столбцов формула выглядит так

 (1)

Последняя формула подсказывает, что для установления трёхмерных координат какой-либо точки достаточно знать координаты её изображения  и расстояние от зрачка камеры до этой точки. То есть необходимо сделать всего одно измерение, а не три! Координаты получаются в тех единицах, в которых в формулу подставлено расстояние |OA| (все остальное там в пикселях).

O’

A’

O

A

C

Ось Z

f

Рисунок 1 – схема подобных треугольников, использованная для нахождения связи координат точки и её изображения

Задача №2. В конфигурации дальномера по координатам точек лазерного «зайчика» на изображении восстановить координаты точек в трёхмерном пространстве.

Схема размещения лазера и камеры (вид сверху) показана на рисунке 1. Лазер развёрнут цилиндрической линзой в вертикальной плоскости. Расстояние от этой лазерной плоскости до оси Z равно h. На кадре видна вертикальная строчка изображений точек, куда падает лазерное излучение. По координатам точек лазерного «зайчика» на изображении восстановить их координаты в трёхмерном пространстве.

Решение.

Для любой точки А, куда падает лазерное излучение, известна её x-координата: A_x=h. Из этого условия и формулы (1) можно получить уравнение для определения расстояния |OA|

Из него следует формула для расстояния

Подставляя это выражение вместо расстояния |OA| в формулу (1), получаем окончательно

Формула для z-координаты совпала, естественно, с формулой для вычисления расстояния в случае лазерного дальномера с неразвёрнутым лазерным лучом.

Задача №3. То же, но с учётом непараллельности оптической оси камеры и лазерной плоскости.

Схема размещения лазера и камеры (вид сверху) показана на рисунке 1. Лазер развёрнут цилиндрической линзой в строго вертикальной плоскости. Расстояние от этой лазерной плоскости до оси Z равно h при z=0. Плоскость не параллельна оси Z . Из-за этого при увеличении z координата x точек лазерной плоскости меняется линейно по формуле x=h+z. ( - просто число) На кадре видна вертикальная строчка изображений точек, куда падает лазерное излучение. По координатам точек лазерного «зайчика» на изображении восстановить их координаты в трёхмерном пространстве.

Решение.

Для любой точки А, куда падает лазерное излучение, известна связь её x- и z-координат: A_x=h+A_z. Из этого условия и формулы (1) можно получить систему двух уравнений для определения A_x и A_z

Из второго уравнения системы следует формула

Подставляя это выражение в первое уравнение системы, получаем уравнение, содержащее из неизвестных только A_z:

Разрешая его относительно A_z, получаем

Окончательный результат

Формула для z-координаты совпала, естественно, с формулой для вычисления расстояния в случае лазерного дальномера с неразвёрнутым лазерным лучом и корректировкой для учёта непараллельности оптических осей камеры и лазера. Когда эти оси почти параллельны, значение числа  совершенно небольшое (0.01). Его значение надо определить опытным путём в процессе калибровки дальномера. Знаменатель выражения стремится к нулю для некоторого значения горизонтальной координаты A₁’, которое соответствует изображению лазерной точки на бесконечно удалённом предмете.

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

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

Даны три точки в трёхмерном пространстве А (A_x, A_y, A_z), В (B_x, B_y, B_z) , С (C_x, C_y, C_z) в системе отсчёта, связанной с центром зрачка камеры. Даны также координаты изображения четвёртой точки D (D’₁, D’₂). Требуется найти координаты точки D в трёхмерном пространстве при условии, что точка D лежит в плоскости (ABC).

Решение.

Четыре точки A, B, C, D лежат в одной плоскости тогда и только тогда, когда

При доказательстве этого использую понятие смешанного векторного произведения (см. математическое приложение).

Это уравнение формально содержит три неизвестных – координаты точки D.

С помощью формулы (1) выражаем D_x и D_y через D_z и известные координаты изображения точки D:

После подстановки получаем выражение

Теперь это уравнение содержит одно неизвестное D_z.

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

(Так как определитель равен нулю, за его знаком вообще можно не следить)

Разложим получившийся определитель по первому столбцу. Получим уравнение

Введя обозначения для значений определителей второго порядка буквы K_x, K_y, K_z согласно записи, получим линейное уравнение для нахождения D_z

Раскрывая скобки, собирая слева члены с множителем D_z, а справа – без него, умножая обе части на (-1), получим

Отсюда уже получаем решение

Окончательный ответ для всех трёх компонент точки D :

где

Фактически мы находили точку пересечения плоскости (ABC) с прямой (D’O). Поэтому при вычислении не понадобились координаты изображений точек A, B, C. Интересно, что значения определителей K_x, K_y, K_z являются компонентами вектора, перпендикулярного плоскости, и их нужно вычислить только один раз. Фактически

Выводы.

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

Открываются некоторые интересные возможности.

Например, можно снабдить сканер лазерным дальномером и автоматизировать процесс установления координат точек плоскости (ABC), то есть процесс привязки камеры к определённой плоскости.

Ещё возможность. Допустим, в кадре неподвижно закреплённой камеры находится плоская поверхность стола. Мы вручную с помощью программы – просмоторщика можем пометить три пикселя, соответствующие трём углам стола. Померив расстояние от камеры до реальных выбранных углов и введя эти данные в программу, можем установить их трёхмерные координаты. И вычислить вектор К. Далее по изображениям перемещающейся по столу точки можно определять её координаты в системе отсчёта, связанной с камерой. Далее можно просто пересчитывать координаты к любой другой системе отсчёта, например, связанной со столом.

Если по углам стола на подставках определённой высоты поставить горящие лампочки, а робота, перемещающегося по столу, снабдить светодиодом заданного цвета, находящимся на той же высоте от стола, мы получим локальный («столовый») аналог системы GPS. Камера будет выполнять роль спутника. Компьютер, подключённый к камере, может каждому роботу слать по каналу связи Bluetooth его координаты на столе. Это открывает путь для создания своего собственного «лего-футбола», «морского боя», рисовальщика с обратной связью и много чего ещё!

Можно поставить две или более камеры, снимать координаты робота со всех камер и использовать их более интеллектуально. Например, координаты объекта (робота), определённые ближайшей к нему камерой, содержат меньшую ошибку, чем определённые дальней камерой. Поэтому реальные координаты можно вычислять получаем усреднения координат со всех камер с весами, обратно пропорциональными расстояниям от камер до объекта.

Благодарю Александра Пенкина за постановку задачи, за постоянную совместную работу по развитию идей двумерного и трёхмерного сканирования. Благодарю Ваню Нецветаева за постоянный интерес к этой теме и сотрудничество.

Математическое приложение.

Из двух векторов можно составить произведение двумя способами.

Первый способ называется векторным произведением.

Записывается двумя способами: 

Результатом векторного произведения двух векторов является вектор, перпендикулярный плоскости, задаваемой векторами – сомножителями. Длина вектора – произведения равна произведению длин векторов – сомножителей и синуса угла между ними. Или (что то же самое) площади параллелограмма, построенному на векторах – сомножителях. Вектор, перпендикулярный заданной плоскости, можно построить двумя способами – вверх и вниз (если представить плоскость сомножителей горизонтальной плоскостью). Выбирается то направление вектора , которое соответствует правилу правого винта (точнее было бы назвать это правило правилом правого штопора или шурупа). Штопор ставится остриём перпендикулярно плоскость сомножителей так, что остриё упирается в точку, из которой построены оба вектора - сомножителя. Ручку штопора начинают крутить от направления первого сомножителя к направлению второго сомножителя (от  к ). Направление, в котором при этом будет перемещаться штопор (ввинчиваться или вывинчиваться) принимается за направление вектора . Таким образом, при перестановке сомножителей векторное произведение меняет направление на противоположное. Примером векторного произведения в физике является момент силы. Момент силы относительно точки О является векторным произведением вектора силы и радиус-вектора, проведённого из точки О в точку приложения силы.

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

Если каждый из векторов – сомножителей представить в виде разложения по трём ортам - единичным векторам, проведённым в положительных направлениях трёх осей координат, из сочетательного закона легко получить запись векторного произведения через коэффициенты разложения (координаты векторов). Особенно просто запись выглядит в «правой» ортогональной системе отсчёта, где три оси взаимно перпендикулярны, а направления орт выбраны так, что векторное произведение орт по OX и OY даёт орт по OZ. (Если правый штопор крутить от положительного направления оси OX к положительному направлению оси OY, штопор должен перемещаться в положительном направлении оси OZ. ) В этом случае формула легко запоминается

Второй способ называется скалярным произведением.

Записывается двумя способами: 

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

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

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

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

Наконец, смешанное произведение трёх векторов есть скалярное произведение первого из векторов на векторное произведение двух других сомножителей. От порядка сомножителей зависит знак.

Знак не меняется при циклических перестановках сомножителей.

Результатом смешанного произведения трёх векторов является число, по модулю равное объёму параллелепипеда, построенного на трёх векторах – сомножителях, проведённых из одной общей точки. Знак числа положительный, если тройка векторов - сомножиелей– «правая». И отрицателен в противоположном случае.

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

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

Список использованных источников

1. 
   Г. Корн, Т. Корн. Справочник по математике. Для научных работников и инженеров. Изд-во «Наука», Москва, 1974 г.