Как убрать четырехугольник в прямоугольник?

tl; dr: математическая задача в проективной геометрии: как найти матрицу камеры 4x4, которая дает проекцию, как показано ниже, такую, что точки A, B, C, D находятся где-то на краях блока устройства (например, нормализованное устройство OpenGL координаты), а углы блока блока падают где-то разумно вдоль лучей EA, EB, EC, ED?

(Это может быть особый случай, возможно, гомографии, перспективности и / или коллинеации. Не знаком с терминологией.)

разработка

Учитывая четырехугольник ABCD в области просмотра, я думаю, что существует уникальное (?) Преобразование, которое отображает его обратно в прямоугольник. Как видно на рисунке ниже: четырехугольник ABCD в области просмотра действует как физическое «окно», и если мы отобразим его обратно в прямоугольник, он будет выглядеть искаженным.

(прямоугольник справа представляет НДЦ, о котором я расскажу позже)

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

Первая попытка

Я полагаю, что могу решить проблему нахождения матрицы камеры 3х4, которая делает 3 + 1-мерную однородную координату в 3-пространстве (слева) и проецирует ее до 2 + 1-мерных однородных координат в 2-пространстве (на право). Это можно решить, используя прямое линейное преобразование, чтобы получить систему уравнений Ba=0для неизвестных элементов aматрицы камеры, и решить систему, используя разложение по сингулярным числам.(СВД). Я бы взял векторы EA, EB, EC, ED (где E - ваш физический глаз или камера в мировом пространстве) в качестве точек на изображении, и (0,0), (1,0), (1 , 1), (0,1) или что-то в качестве точек на пост-изображении, и каждая пара точек дает несколько линейных уравнений для подключения к SVD. Результирующая матрица будет отображать EA -> (0,0) и т. Д. (При условии, что имеется достаточно степеней свободы, т. Е. Если решение уникально, в чем я не уверен, см. Примечание [a].)

Но, к моему огорчению, OpenGL работает не так. OpenGL напрямую не проецирует 3d в 2d с матрицей 3x4. OpenGL требует «нормализованных координат устройства» (NDC), которые являются трехмерными точками. После проецирования в NDC все в блоке 'unit' от (-1, -1, -1,1) до (1,1,1,1) рисуется; все снаружи обрезается (поскольку мы имеем дело с однородными координатами: любая точка (x, y, z, w) появится только на экране, только если первые три координаты (x / w, y / w, z / w) , 1) находятся в блоке от -1 до 1).

Таким образом, возникает вопрос: существует ли какое-то разумное преобразование, которое отображает некоторый странно выглядящий кубоид в однородных координатах (в частности, кубоид, нарисованный слева, с ABCD (передние точки) и A'B'C'D '(задние точки, скрытые за передними точками)) к единичному кубу, например, используя матрицу 4x4? Как это сделать?

что я пробовал

Я попробовал что-то более сильное: я сделал ABCD и A'B'C'D 'похожим на обычную пирамидальную усечку (например, gl frustrum) (то есть в этой гипотетической установке на изображении слева будет просто черный прямоугольник, наложенный на это, а не четырехугольник), а затем использовал DLT / прямое линейное преобразование, чтобы найти предполагаемую матрицу 4x4. Однако, когда я попробовал это сделать, мне не хватило степеней свободы ... полученная матрица 4x4 не отображала каждый входной вектор на каждый выходной вектор. При использовании A, B, C, D, A '(5 пар векторов пре-преобразования и пост-преобразования), я / почти / получаю желаемый результат ... векторы отображаются правильно, но, например, B', C ', D' отображаются на (3,3,1,1) вместо (-1, -1,1,1) и обрезаются OpenGL. Если я попытаюсь добавить шестую точку (6 пар точек для матрицы 4x4 для проецирования), мое решение кажется вырожденным (нули, бесконечности). С какими степенями свободы я имею здесь дело, и возможно ли это с помощью матрицы 4x4, отображающей обычные 4 вектора (3 + 1-мерные векторы однородных координат), которые мы знаем и любим?

случайные второстепенные мысли

Я предполагаю, что невозможно отобразить любой произвольный кубоид на любой произвольный кубоид с матрицей 4x4, хотя я запутался, потому что думал, что можно сопоставить любой выпуклый четырехугольник с любым другим выпуклым четырехугольником в 2d с некоторой матрицей, как в скажем, Photoshop? ... может / не может быть это не сделать с помощью проективного преобразования? И как это обобщить в 3d? ...... Также, учитывая неудачную попытку найти матрицу 4x4, линейная алгебра говорит, что мы не должны ожидать, что матрица NxN отобразит более N линейно независимых точек на N целевых точек в лучшем случае, но я чувствую, что каким-то образом однородным координаты обманывают это, потому что происходит какая-то скрытая колинеарность? Я думаю, нет?

другое решение?

Я думаю, можно было бы также сделать следующую уродливую вещь, где вы используете типичную матрицу проецирования камеры фруструма, находите 2d точки, соответствующие углам, а затем выполняете 2-мерную гомографию искажения перспективы, но если это произойдет после того, как пиксели будут отрисованы (например, фотошоп), тогда будут проблемы с разрешением ... возможно, гипотетически можно было бы найти матрицу для выполнения этого преобразования на плоскости XY в пространстве NDC, а затем составить ее с помощью обычной матрицы, основанной на усеченной дроби?

(примечание [a]: Степень свободы: ABCD может быть дополнительно ограничен, чтобы быть пост-изображением проективного преобразования, действующего на прямоугольник, если это необходимо ... то есть черный прямоугольник слева можно сказать, что результат проецирования рамки рисунка картинки)

Я думаю, что решение ищет проективное преобразование, которое правильно преобразовывает четыре пункта.

т.е.

$x' = [x_0, x_1, 1]$$y = [\frac{y'_0}{y'_2}, \frac{y'_1}{y'_2}]$

$P$

Теперь вы можете использовать алгебру для этого или просто использовать OpenCV getPerspectiveTransform:).

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

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

Чтобы получить уравнения, вставьте матрицы (например [x1 x2 x3 x4; x5 x6 x7 x8; x9 x10 x11 x12]) в свою любимую систему компьютерной алгебры, такую ​​как SageMath, затем решите необходимое матричное уравнение, как показано на рисунке, скопируйте и вставьте решения в виде переменных в ваш код и настройте форматирование.

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

Вам понадобится функция декомпозиции SVD или библиотека на вашем языке.