как я могу реверсировать 2d точки в 3d?

<p>у меня есть 4 2d точки в пространстве экрана, и мне нужно перевести их обратно в 3d пространство. я знаю, что каждая из 4 точек является углом жесткого прямоугольника, повернутого в 3d, и знаю размер прямоугольника. как я могу получить 3d-координаты из этого?</p><p>я не использую какой-либо конкретный api, и у меня нет существующей матрицы проекции. я просто ищу основную математику, чтобы сделать это. конечно, недостаточно данных для преобразования одной 2d-точки в 3d без какой-либо другой ссылки, но я представляю, что если у вас есть 4 точки, вы знаете, что все они находятся под прямым углом друг к другу в одной плоскости, и вы знаете расстояние между ними, вы должны быть в состоянии выяснить это оттуда. к сожалению, я не могу понять, как, хотя.</p><p>это может подпадать под эгиду фотограмметрии, но поиск в google не привел меня к какой-либо полезной информации.</p>

<p>хорошо, я пришел сюда в поисках ответа и не нашел ничего простого и понятного, поэтому я пошел дальше и сделал глупую, но эффективную (и относительно простую) вещь: оптимизацию монте-карло.</p><p>проще говоря, алгоритм выглядит следующим образом: случайным образом возмущает вашу проекционную матрицу, пока она не проецирует ваши известные трехмерные координаты на ваши известные двухмерные координаты.</p><p>вот еще фотография томаса паровозика:</p><p> <a href="https://i.stack.imgur.com/yuhsm.png"><img src="https://i.stack.imgur.com/yuhsm.png" alt="thomas the tank engine"></a> </p><p>допустим, мы используем gimp, чтобы найти 2d-координаты того, что мы считаем квадратом на плоскости земли (действительно ли это квадрат, зависит от вашего суждения о глубине):</p><p> <a href="https://i.stack.imgur.com/u8nkf.png"><img src="https://i.stack.imgur.com/u8nkf.png" alt="with an outline of the square"></a> </p><p>я получаю четыре очка на 2d-изображении: <code>(318, 247)</code>, <code>(326, 312)</code>, <code>(418, 241)</code> и <code>(452, 303)</code>.</p><p>по соглашению мы говорим, что эти точки должны соответствовать трехмерным точкам: <code>(0, 0, 0)</code>, <code>(0, 0, 1)</code>, <code>(1, 0, 0)</code> и <code>(1, 0, 1)</code>. другими словами, единичный квадрат в плоскости y = 0.</p><p>проецирование каждой из этих трехмерных координат в 2d выполняется путем умножения 4d-вектора <code>[x, y, z, 1]</code> на матрицу проекции 4x4, а затем деления компонентов x и y на z, чтобы фактически получить коррекцию перспективы. это более или менее то, что --- <a href="https://www.opengl.org/sdk/docs/man2/xhtml/gluproject.xml">gluproject ()</a> делает, за исключением того, что <code>gluproject()</code> также учитывает текущий видовой экран и учитывает отдельную матрицу вида модели (мы можем просто предположить, что матрица вида модели - это единичная матрица). очень удобно смотреть на документацию <code>gluproject()</code>, потому что я на самом деле хочу решение, которое работает для opengl, но учтите, что в документации отсутствует разделение по z в формуле.</p><p>помните, что алгоритм состоит в том, чтобы начать с некоторой матрицы проекций и беспорядочно возмущать ее, пока она не даст необходимую нам проекцию. итак, что мы собираемся сделать, это спроектировать каждую из четырех трехмерных точек и посмотреть, насколько мы приблизились к желаемым 2d точкам. если наши случайные возмущения приводят к тому, что проецируемые двумерные точки становятся ближе к тем, которые мы отметили выше, мы сохраняем эту матрицу как улучшение по сравнению с нашим первоначальным (или предыдущим) предположением.</p><p>давайте определим наши точки:</p><pre><code># known 2d coordinates of our rectangle i0 = point2(318, 247) i1 = point2(326, 312) i2 = point2(418, 241) i3 = point2(452, 303) # 3d coordinates corresponding to i0, i1, i2, i3 r0 = point3(0, 0, 0) r1 = point3(0, 0, 1) r2 = point3(1, 0, 0) r3 = point3(1, 0, 1) </code></pre><p>нам нужно начать с некоторой матрицы, тождественная матрица кажется естественным выбором:</p><pre><code>mat = [ [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], ] </code></pre><p>нам нужно на самом деле реализовать проекцию (которая в основном является умножением матрицы):</p><pre><code>def project(p, mat): x = mat[0][0] * p.x + mat[0][1] * p.y + mat[0][2] * p.z + mat[0][3] * 1 y = mat[1][0] * p.x + mat[1][1] * p.y + mat[1][2] * p.z + mat[1][3] * 1 w = mat[3][0] * p.x + mat[3][1] * p.y + mat[3][2] * p.z + mat[3][3] * 1 return point(720 * (x / w + 1) / 2., 576 - 576 * (y / w + 1) / 2.) </code></pre><p>это в основном то, что делает <code>gluproject()</code>, 720 и 576 - это ширина и высота изображения соответственно (т.е. область просмотра), и мы вычитаем из 576, чтобы рассчитывать на то, что мы посчитали координаты y сверху, в то время как opengl обычно считает их от дно. вы заметите, что мы не вычисляем z, это потому, что нам это здесь не нужно (хотя это может быть удобно, чтобы убедиться, что оно попадает в диапазон, который opengl использует для буфера глубины).</p><p>теперь нам нужна функция для оценки того, насколько мы близки к правильному решению. значение, возвращаемое этой функцией - это то, что мы будем использовать, чтобы проверить, является ли одна матрица лучше другой. я выбрал сумму квадратов расстояний, т.е.</p><pre><code># the squared distance between two points a and b def norm2(a, b): dx = b.x - a.x dy = b.y - a.y return dx * dx + dy * dy def evaluate(mat): c0 = project(r0, mat) c1 = project(r1, mat) c2 = project(r2, mat) c3 = project(r3, mat) return norm2(i0, c0) + norm2(i1, c1) + norm2(i2, c2) + norm2(i3, c3) </code></pre><p>чтобы возмущать матрицу, мы просто выбираем элемент для возмущения на случайную величину в некотором диапазоне:</p><pre><code>def perturb(amount): from copy import deepcopy from random import randrange, uniform mat2 = deepcopy(mat) mat2[randrange(4)][randrange(4)] += uniform(-amount, amount) </code></pre><p>(стоит отметить, что наша функция <code>project()</code> на самом деле вообще не использует <code>mat[2]</code>, так как мы не вычисляем z, а все наши координаты y равны 0, значения <code>mat[*][1]</code> также не имеют значения. мы могли бы использовать этот факт и никогда не пытаться возмущать те значения, которые дали бы небольшое ускорение, но это осталось в качестве упражнения ...)</p><p>для удобства давайте добавим функцию, которая выполняет основную часть аппроксимации, многократно вызывая <code>perturb()</code> для определения наилучшей матрицы, которую мы до сих пор нашли:</p><pre><code>def approximate(mat, amount, n=100000): est = evaluate(mat) for i in xrange(n): mat2 = perturb(mat, amount) est2 = evaluate(mat2) if est2 < est: mat = mat2 est = est2 return mat, est </code></pre><p>теперь все, что осталось сделать, это запустить ...:</p><pre><code>for i in xrange(100): mat = approximate(mat, 1) mat = approximate(mat, .1) </code></pre><p>я считаю, что это уже дает довольно точный ответ. через некоторое время я нашел следующую матрицу:</p><pre><code>[ [1.0836000765696232, 0, 0.16272110011060575, -0.44811064935115597], [0.09339193527789781, 1, -0.7990570384334473, 0.539087345090207 ], [0, 0, 1, 0 ], [0.06700844759602216, 0, -0.8333379578853196, 3.875290562060915 ], ] </code></pre><p>с ошибкой около <code>2.6e-5</code>. (обратите внимание, что элементы, которые мы сказали, не использовались в вычислениях, на самом деле не были изменены по сравнению с нашей исходной матрицей; это потому, что изменение этих записей не приведет к изменению результата оценки, и поэтому изменение никогда не будет перенесено)</p><p>мы можем передать матрицу в opengl, используя <code>glloadmatrix()</code> (но не забудьте сначала транспонировать ее, и не забудьте загрузить матрицу вида модели с матрицей идентификаторов):</p><pre><code>def transpose(m): return [ [m[0][0], m[1][0], m[2][0], m[3][0]], [m[0][1], m[1][1], m[2][1], m[3][1]], [m[0][2], m[1][2], m[2][2], m[3][2]], [m[0][3], m[1][3], m[2][3], m[3][3]], ] glloadmatrixf(transpose(mat)) </code></pre><p>теперь мы можем, например, переместить вдоль оси z, чтобы получить разные позиции вдоль дорожек:</p><pre><code>gltranslate(0, 0, frame) frame = frame + 1 glbegin(gl\_quads) glvertex3f(0, 0, 0) glvertex3f(0, 0, 1) glvertex3f(1, 0, 1) glvertex3f(1, 0, 0) glend() </code></pre><p> <a href="https://i.stack.imgur.com/dfeex.gif"><img src="https://i.stack.imgur.com/dfeex.gif" alt="with 3d translation"></a> </p><p>конечно, это не очень элегантно с математической точки зрения; вы не получите уравнение в замкнутой форме, в которое вы можете просто вставить свои числа и получить прямой (и точный) ответ. однако, это позволяет вам добавлять дополнительные ограничения, не беспокоясь о усложнении ваших уравнений; например, если мы хотели бы также указать высоту, мы могли бы использовать этот угол дома и сказать (в нашей функции оценки), что расстояние от земли до крыши должно быть примерно одинаковым, и снова запустить алгоритм. так что да, это своего рода грубая сила, но она работает и работает хорошо.</p><p> <a href="https://i.stack.imgur.com/smdr8.png"><img src="https://i.stack.imgur.com/smdr8.png" alt="choo choo!"></a> </p>

<p>это классическая проблема для маркеров на основе дополненной реальности.</p><p>у вас есть квадратный маркер (2d штрих-код), и вы хотите найти его позу (перемещение и вращение относительно камеры) после нахождения четырех краев маркера. <a href="http://www.brightsideofnews.com/data/2009\_10\_26/zombies-nvidia-tegra-augmented-reality/zombies\_ar\_marker\_675.jpg">обзор-picture</a> </p><p>я не знаю о последнем вкладе в эту область, но, по крайней мере, до определенного момента (2009 г.) rpp должен был превзойти позит, который упомянут выше (и это действительно классический подход для этого). пожалуйста, смотрите ссылки, они также предоставить источник.</p><ul> <li> <p> <a href="http://www.emt.tugraz.at/~vmg/schweighofer">http://www.emt.tugraz.at/~vmg/schweighofer</a> </p> </li> <li> <p> <a href="http://www.emt.tugraz.at/publications/emt\_tr/tr-emt-2005-01.pdf">http://www.emt.tugraz.at/publications/emt\_tr/tr-emt-2005-01.pdf</a> </p> </li> <li> <p> <a href="http://www.emt.tugraz.at/system/files/rpp\_matlab\_ref\_implementation.tar.gz">http://www.emt.tugraz.at/system/files/rpp\_matlab\_ref\_implementation.tar.gz</a> </p> </li> </ul><p>(ps - я знаю, что это немного старая тема, но в любом случае, пост может быть полезен для кого-то)</p>

<p><em> d. dementhon </em> разработал алгоритм для вычисления <em> позы </em> объекта (его положения и ориентации в пространстве) из характерных точек в 2d-изображении при знании модели объекта - <strong> это ваша точная проблема </strong>:</p><blockquote> <p>опишем метод нахождения позы объекта по одному изображению. мы предполагаем, что мы можем обнаружить и сопоставить на изображении четыре или более некомпланарных характерных точки объекта и что мы знаем их относительную геометрию на объекте.</p> </blockquote><p>алгоритм известен как <strong> posit </strong> и описан в классической статье "поза объекта на основе модели в 25 строках кода" (доступно на <a href="http://www.cfar.umd.edu/~daniel/site\_2/research.html">его сайт</a> , раздел 4).</p><p>прямая ссылка на статью: <a href="http://www.cfar.umd.edu/~daniel/daniel\_papersfordownload/pose25lines.pdf">http://www.cfar.umd.edu/~daniel/daniel\_papersfordownload/pose25lines.pdf</a> реализация opencv: <a href="http://opencv.willowgarage.com/wiki/posit">http://opencv.willowgarage.com/ вики/posit</a> </p><p>идея состоит в том, чтобы многократно аппроксимировать перспективную проекцию масштабированной <em> масштабированной ортографической проекцией </em> до схождения в точную позу.</p>

<p>из двумерного пространства будет 2 допустимых прямоугольника, которые можно построить. не зная исходную матричную проекцию, вы не узнаете, какая из них правильная. это то же самое, что и проблема "коробки": вы видите два квадрата, один внутри другого, с 4 внутренними вершинами, соединенными с 4 соответствующими внешними вершинами. вы смотрите на коробку сверху вниз или снизу вверх?</p><p>при этом вы ищете матричное преобразование t, где ...</p><p>{{x1, y1, z1}, {x2, y2, z2}, {x3, y3, z3}, {x4, y4, z4}} x t = {{x1, y1}, {x2, y2}, { x3, y3}, {x4, y4}}</p><p>(4 х 3) х т = (4 х 2)</p><p>поэтому t должна быть (3 x 2) матрица итак, у нас есть 6 неизвестных.</p><p>теперь создайте систему ограничений на t и решите ее с помощью simplex. чтобы построить ограничения, вы знаете, что линия, проходящая через первые две точки, должна быть параллельна линии, проходящей ко вторым двум точкам. вы знаете, что линия, проходящая через точки 1 и 3, должна быть параллельной линиям, проходящим через точки 2 и 4. вы знаете, что линия, проходящая через точки 1 и 2, должна быть ортогональной линии, проходящей через точки 2 и 3. вы знаете, что длина линии от 1 и 2 должны равняться длине строки от 3 и 4. вы знаете, что длина строки от 1 и 3 должна равняться длине строки от 2 и 4.</p><p>чтобы сделать это еще проще, вы знаете о прямоугольнике, поэтому вы знаете длину всех сторон.</p><p>это должно дать вам множество ограничений для решения этой проблемы.</p><p>конечно, чтобы вернуться, вы можете найти t-inverse.</p><p>@rob: да, существует бесконечное количество проекций, но не бесконечное количество проектов, где точки должны удовлетворять требованиям прямоугольника.</p><p>@nlucaroni: да, это решаемо, только если у вас есть четыре точки в проекции. если прямоугольник проецируется только на 2 точки (то есть плоскость прямоугольника ортогональна поверхности проекции), то это не может быть решено.</p><p>хммм ... я должен пойти домой и написать этот маленький драгоценный камень. это звучит как веселье.</p><p>обновления:</p><ol> <li>существует бесконечное количество проекций, если вы не исправите один из пунктов. если вы фиксируете одну из точек исходного прямоугольника, то есть два возможных исходных прямоугольника.</li> </ol>

<p>для моего движка opengl следующий фрагмент преобразует координаты мыши/экрана в трехмерные мировые координаты. прочитайте комментарии для реального описания того, что происходит.</p><pre>[.\_\_ нет описание: преобразование координат мыши в мировые координаты */ </pre><p><code>void ycamera :: calculateworldcoordinates(float x, float y, yvector3 *vec) { // start glint viewport[4]; gldouble mvmatrix[16], projmatrix[16];</code></p><pre><code><code>glint real\_y; gldouble mx, my, mz; glgetintegerv(gl\_viewport, viewport); glgetdoublev(gl\_modelview\_matrix, mvmatrix); glgetdoublev(gl\_projection\_matrix, projmatrix); real\_y = viewport[3] - (glint) y - 1; // viewport[3] is height of window in pixels gluunproject((gldouble) x, (gldouble) real\_y, 1.0, mvmatrix, projmatrix, viewport, &mx, &my, &mz); /* 'mouse' is the point where mouse projection reaches far\_plane. world coordinates is intersection of line(camera->mouse) with plane(z=0) (see lamothe 306) equation of line in 3d: (x-x0)/a = (y-y0)/b = (z-z0)/c intersection of line with plane: z = 0 x-x0 = a(z-z0)/c <=> x = x0+a(0-z0)/c <=> x = x0 -a*z0/c y = y0 - b*z0/c */ double lx = fposition.x - mx; double ly = fposition.y - my; double lz = fposition.z - mz; double sum = lx*lx + ly*ly + lz*lz; double normal = sqrt(sum); double z0\_c = fposition.z / (lz/normal); vec->x = (float) (fposition.x - (lx/normal)*z0\_c); vec->y = (float) (fposition.y - (ly/normal)*z0\_c); vec->z = 0.0f; </code> </ код></pre><p>}</p>

<p>для продолжения подхода ронса: вы можете найти свои z-значения, если знаете, как вы повернули прямоугольник.</p><p>хитрость заключается в том, чтобы найти проективную матрицу, которая сделала проекцию. к счастью, это возможно и даже дешево. соответствующая математика может быть найдена в статье пола хекберта "проективные отображения для деформации изображения".</p><p> <a href="http://pages.cs.wisc.edu/~dyer/cs766/readings/heckbert-proj.pdf">http://pages.cs.wisc.edu/~dyer/cs766/readings/heckbert-proj.pdf</a> </p><p>таким образом, вы можете восстановить однородную часть каждой вершины назад, которая была потеряна во время проецирования.</p><p>теперь у вас осталось четыре линии вместо точек (как объяснил рон). так как вы знаете размер вашего оригинального прямоугольника, ничего не потеряно. теперь вы можете подключить данные из метода рона и из двумерного подхода в решатель линейных уравнений и решить для z. таким образом вы получите точные значения z каждой вершины.</p><p>примечание: это просто работает, потому что:</p><ol> <li>первоначальная форма была прямоугольником</li> <li>вы знаете точный размер прямоугольника в трехмерном пространстве.</li> </ol><p>это действительно особый случай.</p><p>надеюсь, это поможет, нильс</p>

<p>предполагая, что точки действительно являются частью прямоугольника, я даю общую идею:</p><p>найдите две точки с максимальным расстоянием между ними: они, скорее всего, определяют диагональ (исключение: особые случаи, когда прямоугольник почти параллелен плоскости yz, оставленный для студента). назовите их a, c. рассчитайте bad, bcd углы. они, по сравнению с прямыми углами, дают вам ориентацию в трехмерном пространстве. чтобы узнать расстояние z, необходимо сопоставить проекционные стороны с известными сторонами, а затем, основываясь на методе трехмерного проецирования (это 1/z?), вы на правильном пути, чтобы узнать расстояния.</p>

<p>я достану книгу по линейной алгебре, когда вернусь домой, если никто не ответит. но при @ d g не все матрицы обратимы. <a href="http://mathworld.wolfram.com/singularmatrix.html">сингулярные матрицы необратимы</a> (когда определитель = 0). это будет происходить постоянно, так как матрица проекции <em> должна </em> иметь собственные значения 0 и 1 и быть квадратной (поскольку она идемпотентна, поэтому p ^ 2 = р).</p><p>простой пример: [[0 1] [0 1]], так как определитель = 0, и это проекция на линию x = y!</p>

<p>проекция, которую вы имеете на 2d-поверхность, имеет бесконечно много 3d-прямоугольников, которые будут проецироваться в одну и ту же 2d-форму.</p><p>подумайте об этом так: у вас есть четыре 3d-точки, которые составляют 3d-прямоугольник. назовите их (x0, y0, z0), (x1, y1, z1), (x2, y2, z2) и (x3, y3, z3). когда вы проецируете эти точки на плоскость x-y, вы отбрасываете координаты z: (x0, y0), (x1, y1), (x2, y2), (x3, y3).</p><p>теперь, когда вы хотите спроецировать обратно в трехмерное пространство, вам нужно перепроектировать то, что было z0, .., z3. но любой набор z-координат, которые а) сохраняют одинаковое расстояние между точками по оси x и б) сохраняют форму прямоугольника, будут работать. итак, любой член этого (бесконечного) множества будет делать: {(z0 + i, z1 + i, z2 + i, z3 + i) | я <- r}.</p><p>edit @jarrett: представьте, что вы решили это и получили прямоугольник в трехмерном пространстве. теперь представьте, что вы двигаете этот прямоугольник вверх и вниз по оси z. те бесконечные количества переведенных прямоугольников имеют одинаковую проекцию x-y. откуда ты знаешь, что нашел "правильный"?</p><p>edit # 2: хорошо, это из комментария, который я сделал по этому вопросу - более интуитивный подход к рассуждению об этом.</p><p>представьте себе, что вы держите лист бумаги над столом. представьте, что к каждому углу бумаги прикреплена невесомая лазерная указка, направленная вниз к столу. бумага - это 3d-объект, а точки лазерной указки на столе - это 2d-проекция.</p><p>теперь, как вы можете определить, насколько высоко находится стол, глядя на <em>просто</em> точки лазерного указателя?</p><p>ты не можешь переместите бумагу прямо вверх и вниз. лазерные указки по-прежнему будут светиться в тех же точках на столе, независимо от высоты бумаги.</p><p>найти координаты z в обратной проекции - это все равно, что попытаться найти высоту бумаги на основе точек лазерного указателя только на столе.</p>

<p> <a href="http://library.wolfram.com/infocenter/articles/2794/">http://library.wolfram.com/infocenter/articles/2794/</a> </p><p> <a href="http://campar.in.tum.de/students/sepposeestimation">http://campar.in.tum.de/students/sepposeestimation</a> </p><p> <a href="http://opencvlibrary.sourceforge.net/posit">http://opencvlibrary.sourceforge.net/posit</a> будет работать, но может расходиться или зацикливаться.</p>

<p>если вы знаете, что фигура представляет собой прямоугольник на плоскости, вы можете значительно ограничить проблему. вы, конечно, не можете определить, "какая" плоскость, поэтому вы можете выбрать, чтобы она лежала на плоскости, где z = 0, а один из углов находится в точке x = y = 0, а ребра параллельны оси x/y.</p><p>следовательно, точки в 3d - это {0,0,0}, {w, 0,0}, {w, h, 0} и {0, h, 0}. я почти уверен, что абсолютный размер не будет найден, поэтому только соотношение w/h является релевантным, так что это неизвестно.</p><p>относительно этой плоскости камера должна находиться в некоторой точке cx, cy, cz в пространстве, должна указывать в направлении nx, ny, nz (вектор длины один, поэтому один из них является избыточным) и иметь focal\_length/image\_width фактор ш. эти числа превращаются в матрицу проекции 3х3.</p><p>это дает в общей сложности 7 неизвестных: w/h, cx, cy, cz, nx, ny и w.</p><p>всего вам известно 8 пар: 4 пары x + y.</p><p>так что это можно решить.</p><p>следующим шагом является использование matlab или mathmatica.</p>

<p>да, монте-карло работает, но я нашел лучшее решение для этой проблемы. этот код отлично работает (и использует opencv):</p><pre><code>cv2.calibratecamera(new list<list<point3f>>() { points3d }, new list<list<point2f>>() { points2d }, new size(height, width), cameramatrix, distcoefs, out rvecs, out tvecs, calibrationflags.zerotangentdist | calibrationflags.fixk1 | calibrationflags.fixk2 | calibrationflags.fixk3); </code></pre><p>эта функция принимает известные 3d и 2d точки, размер экрана и возвращает вращение (rvecs [0]), перевод (tvecs [0]) и матрицу внутренних значений камеры. это все, что вам нужно.</p>

<p>когда вы проецируете из 3d в 2d, вы теряете информацию.</p><p>в простом случае одной точки обратная проекция даст вам бесконечный луч через трехмерное пространство.</p><p>стереоскопическая реконструкция обычно начинается с двух 2d-изображений и проецируется обратно в 3d. затем найдите пересечение двух трехмерных лучей.</p><p>проекция может принимать разные формы. ортогональный или перспективный. я предполагаю, что вы предполагаете ортогональную проекцию?</p><p>в вашем случае, если у вас есть исходная матрица, у вас будет 4 луча в трехмерном пространстве. после этого вы сможете ограничить проблему своими размерами в 3d-прямоугольнике и попытаться ее решить.</p><p>решение не будет уникальным, поскольку вращение вокруг любой оси, параллельной 2-й плоскости проекции, будет неоднозначным в направлении. другими словами, если двумерное изображение перпендикулярно оси z, то вращение трехмерного прямоугольника по часовой стрелке или против часовой стрелки вокруг оси x приведет к тому же изображению. аналогично для оси у.</p><p>в случае, когда плоскость прямоугольника параллельна оси z, у вас есть еще больше решений.</p><p>поскольку у вас нет исходной матрицы проекций, дальнейшая неоднозначность вносится произвольным масштабным коэффициентом, который существует в любой проекции. вы не можете различить масштабирование в проекции и перемещение в 3d в направлении оси z. это не проблема, если вас интересуют только относительные положения 4-х точек в трехмерном пространстве, когда они связаны друг с другом, а не с плоскостью 2-мерной проекции.</p><p>в перспективе все становится сложнее ...</p>

<p>спасибо @vegard за отличный ответ. я немного очистил код:</p><pre><code>import pandas as pd import numpy as np class point2: def \_\_init\_\_(self,x,y): self.x = x self.y = y class point3: def \_\_init\_\_(self,x,y,z): self.x = x self.y = y self.z = z # known 2d coordinates of our rectangle i0 = point2(318, 247) i1 = point2(326, 312) i2 = point2(418, 241) i3 = point2(452, 303) # 3d coordinates corresponding to i0, i1, i2, i3 r0 = point3(0, 0, 0) r1 = point3(0, 0, 1) r2 = point3(1, 0, 0) r3 = point3(1, 0, 1) mat = [ [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], ] def project(p, mat): #print mat x = mat[0][0] * p.x + mat[0][1] * p.y + mat[0][2] * p.z + mat[0][3] * 1 y = mat[1][0] * p.x + mat[1][1] * p.y + mat[1][2] * p.z + mat[1][3] * 1 w = mat[3][0] * p.x + mat[3][1] * p.y + mat[3][2] * p.z + mat[3][3] * 1 return point2(720 * (x / w + 1) / 2., 576 - 576 * (y / w + 1) / 2.) # the squared distance between two points a and b def norm2(a, b): dx = b.x - a.x dy = b.y - a.y return dx * dx + dy * dy def evaluate(mat): c0 = project(r0, mat) c1 = project(r1, mat) c2 = project(r2, mat) c3 = project(r3, mat) return norm2(i0, c0) + norm2(i1, c1) + norm2(i2, c2) + norm2(i3, c3) def perturb(mat, amount): from copy import deepcopy from random import randrange, uniform mat2 = deepcopy(mat) mat2[randrange(4)][randrange(4)] += uniform(-amount, amount) return mat2 def approximate(mat, amount, n=1000): est = evaluate(mat) for i in xrange(n): mat2 = perturb(mat, amount) est2 = evaluate(mat2) if est2 < est: mat = mat2 est = est2 return mat, est for i in xrange(1000): mat,est = approximate(mat, 1) print mat print est </code></pre><p>примерный звонок с .1 у меня не сработал, поэтому я его вынул. я тоже запускал его некоторое время, и последний раз проверял, что это</p><pre><code>[[0.7576315397559887, 0, 0.11439449272592839, -0.314856490473439], [0.06440497208710227, 1, -0.5607502645413118, 0.38338196981556827], [0, 0, 1, 0], [0.05421620936883742, 0, -0.5673977598434641, 2.693116299312736]] </code></pre><p>с ошибкой около 0,02.</p>