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

Привет.

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Перепишем радиус-вектора точек в следующем виде:

    , где — радус-вектора в системе координат с центром в точке .

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

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

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

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

    ,

    где

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

    ,

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

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

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

    ,

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

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

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

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

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

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

    Оставить комментарий