Участник:OscarFox/Обобщенный прокрустов анализ

Автор: Фостенко О.А.

Свойства и структура алгоритма

Общее описание алгоритма

Обобщенный прокрустов анализ (Generalized Procrustes Analysis, GPA) - это метод, предназначенный для сравнения и выравнивания нескольких наборов из одного и того же числа точек (форм) в пространстве одной размерности. Цель GPA - найти оптимальные преобразования, включающие вращения, масштабирование и сдвиги, для наилучшего согласования форм друг с другом.

Формулировка похожей задачи встречается в работе B. F. Green 1952 года, аналитическое решение задачи выравнивания двух множеств точек друг относительно друга (классическое прокрустово преобразование) было предложено P. H. Schönemann в 1966 году, а непосредственно алгоритм GPA был разработан и опубликован J. C. Gower в 1975 году.

GPA - это итеративный алгоритм: он последовательно согласовывает все формы относительно некоторой «средней формы», обновляя её до тех пор, пока изменения не станут незначительными. К «средней форме» набор из точек приводится с помощью классического прокрустова преобразования. Иллюстрация выравнивания, выполняемого с помощью как классического, так и обобщенного прокрустовых преобразований, приведена на рисунке 1.

Рис. 1. Иллюстрация прокрустова преобразования на примере форм, отвечающих трехмерным человеческим позам

Математическое описание алгоритма

Описание данных и формул

Входные данные:

• [math]\displaystyle{ \{X_1, X_2,\dots,X_m\} }[/math] - набор входных форм, то есть матриц одного размера: [math]\displaystyle{ X_i \in \mathbb{R}^{n \times d}, \; i=1,\dots,m }[/math]. Каждая матрица [math]\displaystyle{ X_i }[/math] представляет собой набор из [math]\displaystyle{ n }[/math] точек в [math]\displaystyle{ d }[/math]-мерном пространстве. Точки с одинаковыми индексами (т.е. строки матриц с одинаковыми номерами) предполагаются соответствующими друг другу.

Выходные данные:

• Выровненные формы [math]\displaystyle{ \{ X_1', X_2',\dots,X_m'\} }[/math], где [math]\displaystyle{ X_i'\in \mathbb{R}^{n \times d}, \; i=1,\dots,m }[/math].

Описание алгоритма

Выровненные формы [math]\displaystyle{ \{ X_i' \}_{i=1}^m }[/math], где [math]\displaystyle{ X_i' = s_i X_i R_i + \mathbf{1}_n t_i^T }[/math]. Здесь [math]\displaystyle{ s_i\in \mathbb{R} }[/math] есть константа масштаба, [math]\displaystyle{ R_i\in \mathbb{R}^{d \times d} }[/math] - ортогональная матрица, отвечающая вращению, [math]\displaystyle{ \mathbf{1}_n\in \mathbb{R}^{n \times 1} }[/math] - вектор-столбец из единиц, а [math]\displaystyle{ t_i\in \mathbb{R}^{n \times 1} }[/math] - вектор переноса.

Средняя форма (консенсус): [math]\displaystyle{ M = \frac{1}{m} \sum_{i=1}^m X_i' }[/math].

Шаг 1. Центрирование и масштабирование форм.

Для каждой формы [math]\displaystyle{ X_i }[/math] вычисляется её геометрический центр (среднее по строкам): [math]\displaystyle{ \bar{X}_i = \frac{1}{n} mathbf{1}_n^T X_i, \; i=1,\dots,m, }[/math]

[math]\displaystyle{ \sum{j=1}^{n} x_{ij}, }[/math] где [math]\displaystyle{ x_{ij} }[/math] — j-я точка формы [math]\displaystyle{ X_i }[/math] (строка матрицы).

Затем форма центрируется по этому среднему: [math]\displaystyle{ X_i \leftarrow X_i - \mathbf{1}_n \bar{x}_i^T, }[/math] где [math]\displaystyle{ \mathbf{1}_n \in \mathbb{R}^{n \times 1} }[/math] — вектор единиц.

[math]\displaystyle{ \bar{X}_i = \frac{1}{n} \mathbf{1}_n^T X_i, \quad i=1,\dots,m }[/math] [math]\displaystyle{ X_i^{(0)} = X_i - \mathbf{1}_n \bar{X}_i }[/math]