python

О барицентрических координатах на пальцах

  • вторник, 15 октября 2019 г. в 00:32:22
https://habr.com/ru/post/471194/
  • Python
  • Алгоритмы
  • Математика


Привет.

Наверняка всем доводилось быть свидетелями оценки на глазок степени сходства ребенка с родителями: что-нибудь типа «вылитый папа, но на маму тоже похож!!!»

image
(взято отсюда)

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


И будет это выглядеть и восприниматься вполне естественно для «обычного» человека, не связанного с антропологией, или, например, криминалистикой. Для профессионала в области анализа и распознавания лиц, человеческое лицо представляется, скорее, набором параметров. То есть, точкой (набор координат) в некотором пространстве с базисом (оси, соответствующие параметрам). И если описывать лицо ребенка в сравнении с его родственниками, то скорее всего, точка, соответствующая лицу ребенка окажется в этом пространстве параметров внутри выпуклой оболочки облака точек, соответствующих лицам ближайших родственников (но это не точно).

Собственное, к чему я это все… Эти два подхода к описанию лиц соответствуют двум системам координат:

  1. барицентрической, описание точки в пространстве (в нашем примере: лица) через взвешенную смесь других точек;
  2. аффинной, описание точки в пространстве через координаты в некотором базисе.


Так что же такое барицентрические координаты?


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

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

Тогда любая точка пространства image может быть представлена радиус-вектором image:

image

Набор image и есть барицентрические координаты.

Чем барицентрические координаты лучше/хуже аффинных?


Пожалуй, начнем с относительных недостатков:

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

Отчасти первый недостаток компенсируется тем, что не смотря на необходимость использования image барицентрической координаты при описании точки в image-мерном пространстве, количество степеней не повышается. Барицентрические координаты, определенные в формуле (1), связаны соотношением:

image

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

Каковы же бонусы от использования барицентрических координат?

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

    image

    image
  2. По барицентрическим координатам легко определить, принадлежит ли точка image части пространства, ограниченной многогранником с вершинами image: это выполняется только в том случае, если image. Равенство i-й барицентрической координаты 1 означает, что точка image совпадает с image. Если несколько барицентричесих координат равны 0, то это означает, что точка принадлежит подпространству, натянутому на радиус-вектора остальных точек, соответствующие координаты которых больше 0.

Наверное, они очень сложно вычисляются?


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

Перепишем радиус-вектора точек в следующем виде:
image, где image — радус-вектора в системе координат с центром в точке image.

Тогда формулу (1) можно переписать в следующем виде:

image

Раскроем скобки в сумме:

image

Согласно свойства (2):

image

Соответственно:

image,

где image

Учитывая (2), ограничимся вычислением первых n барицентрических координат. Представим переход в барицентрические координаты как линейное преобразование:

image,

где image — вектор n барицентрических координат (кроме последней), image — матрица преобразования.

Учитывая свойства барицентрического представления, если в качестве image подставить один из векторов image (image), то мы получим вектор с нулевыми компонентами, кроме одной i-й, которая будет равна 1.

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

image,

где image, image — единичная матрица (image — символ Кронекера: 1, если image, иначе — 0).

Из (10) находим image:

image

Таким образом, имея набор из точек с радиус-векторами image, image мы можем вычислить матрицу для преобразования в барицентрические координаты:

image

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

image

Вновь воспользовавшись соотношением (2), получим последнюю барицентрическую координату:

image

Заключение


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