Улучшите свое понимание коник и получите знания о том, как построить эллипс из набора 2D-точек.

1. Введение

Цель

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

При работе с гиперплоскостью параметризация относительно проста и может быть легко включена в уравнение, подобное приведенному ниже. Получив оптимальные коэффициенты (a,b,c,d), мы можем без особых усилий получить нормаль к гиперплоскости (a,b,c).

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

Ключевые публикации

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

В 1996 году Фитцгиббон ​​предложил минимизировать алгебраическое расстояние при ограничении эллиптичности (Прямая подгонка эллипсов методом наименьших квадратов). Это гарантирует, что оптимальные конические параметры соответствуют, например, эллипсу, а не параболе.

Впоследствии, в 1998 году, Халир и Флюссер представили численно стабильный вариант этого подхода (Числово стабильная прямая подгонка эллипсов методом наименьших квадратов).

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

Я рекомендую читателям обратиться к оригинальной публикации для более подробного изучения численной стабильности.

Публичные реализации

Несколько реализаций, основанных на численно стабильной версии Halir и Flusser, общедоступны на GitHub:

2) Общее уравнение коники

Коники

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

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

Уравнение

Полиномиальное уравнение второй степени с участием x и y, включая линейные и квадратичные члены, может определить любую конику.

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

Давайте рассмотрим некоторые конкретные уравнения коник, возникающие в практических ситуациях.

Параболы и гиперболы

Самая известная парабола, безусловно, образована графиком квадратичной функции (синяя левая кривая ниже). Коэффициенты b и c общих конических уравнений остаются равными нулю в случае полинома второй степени от x.

Его часто упускают из виду, так как он больше не является функцией x, но мы можем перевести квадрат показателя x в y, чтобы повернуть параболу (оранжевая средняя кривая ниже). Функция квадратного корня соответствует положительной ветви этой кривой.

В отличие от парабол, образующих непрерывные кривые, гиперболы, как и график обратной функции, состоят из двух бесконечно уходящих ветвей (красная правая кривая внизу). Одной из примечательных особенностей гипербол является наличие асимптот, тогда как параболы не обладают этой характеристикой. Асимптоты — это воображаемые линии, к которым ветви гиперболы приближаются, но никогда не пересекаются.

Круги и эллипсы

И гиперболы, и параболы являются неограниченными кривыми, а это означает, что они простираются бесконечно без какой-либо конечной точки. Напротив, круги и эллипсы представляют собой замкнутые кривые, образующие полную петлю, не продолжающуюся до бесконечности.

Окружность определяется как набор точек, равноудаленных от центральной точки (синяя левая кривая ниже). Расширение или сжатие осей, т. Е. Изменение коэффициентов a и c перед x² и y², приводит к эллипсу, выровненному по оси (оранжевая средняя кривая ниже). Эллипс можно повернуть, включив ненулевое значение b перед перекрестным членом xy (красная правая кривая ниже).

Прямые и вырожденные коники

Как было сказано ранее, вырожденная коника может быть одной точкой, прямой или парой прямых. Я не рассматривал случай прямой линии, определенной как y=x, поскольку общее уравнение коники неявно предполагает, что по крайней мере один из квадратичных членов отличен от нуля.

3) Фитинг эллипса (Фитцгиббон)

Конический дискриминант

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

Легче подойти к нему через матричное представление, чтобы лучше понять его. Общее уравнение коники можно изменить, как показано ниже, используя симметричную матрицу Q 2x2, вектор P 2x1 и коэффициент f.

Это квадратное уравнение также можно записать в однородных координатах.

Если матрица 3x3 A вырождена, то коника вырождена. Когда A неособо, мы можем определить конический тип, исследуя определитель матрицы 2x2 Q.

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

В случае круга Q представляет собой масштабированную версию единичной матрицы. В случае повернутого эллипса мы можем преобразовать Q путем диагонализации в диагональную матрицу с квадратами обратных величин малой и большой осей (с точностью до масштабного коэффициента).

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

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

Оптимизация

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

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

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

Конический дискриминант должен быть строго отрицательным, чтобы конический представлял эллипс. Чтобы исправить масштаб и сохранить согласованность, мы можем установить дискриминант равным -1. Обратите внимание, что это ограничение квадратично по коническим коэффициентам.

Задача подгонки эллипса представляет собой минимизацию с ограничениями с помощью квадратичной матрицы ограничений 6x6 C.

Введение множителя Лагранжа λ и дифференцирование для нахождения минимума дает уравнение, где θ — собственный вектор, а λ — собственное значение.

Примечательно, что минимизируемая нами положительная величина равна множителю Лагранжа λ.

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

Н.Б. Халир и Флюссер рассматривают случай, когда все точки лежат точно на плоскости, а λ равно 0.

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

Введение

Фантастика! У нас есть оптимальные конические коэффициенты (a,b,c,d,e,f)! Но подождите секунду, как мы можем получить малую и большую оси, угол поворота и центр из этих коэффициентов?

Форма матрицы эллипса

По сути, любой эллипс можно получить, взяв единичный круг, сжав или расширив оси X и Y, повернув его и, наконец, применив смещение. На изображении ниже показано, как отменить эти преобразования, чтобы сопоставить эллипс с единичным кругом, где коническое уравнение является простым, а именно x²+y²=1.

Н.Б. Введенная здесь буква с обозначает центр эллипса и не имеет ничего общего с коническим коэффициентом с.

Таким образом, уравнение эллипса может быть записано следующим образом, гдеRφ является матрицей поворота угла φ.

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

Идентификация параметров

Оптимальные параметры θ=(a,b,c,d,e,f) используются для построения матрицы Q и вектора P общего уравнения коники.

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

Идентификацию параметра можно выполнить с неизвестным масштабным коэффициентом s.

Центр эллипса

Интересно, что комбинация Q и p дает центр эллипса c, эффективно устраняя влияние масштабного коэффициента s.

Шкала

Используя связь между Q и M, мы можем выразить шкалу s как функцию Q, f и вновь полученного центра c.

Матрица вращения и длины осей

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

Н.Б. Ограничение эллиптичности гарантирует, что диагональные значения Σ строго положительны.

К счастью, выразить M несложно, так как его можно получить путем масштабирования Q с помощью вновь вычисленного масштабного коэффициента s.

Угол поворота

Важно помнить, что матрица вращения 2x2 может быть выражена с помощью синуса и косинуса угла поворота φ.

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

Поскольку φ покрывает весь диапазон ]-π, π], мы должны использовать arctan2, который является вариантом arctan, который правильно выбирает квадрант.

Последние мысли

Теперь у нас есть все параметры нашего эллипса.

Заключение

Надеюсь, вам понравилось читать эту статью, и она дала вам больше информации о кониках и аппроксимации эллипсов!

Смотрите больше моего кода на GitHub.