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

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

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

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

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

Формулировка похожей задачи встречается в работе B. F. Green 1952 года, аналитическое решение задачи выравнивания двух множеств точек друг относительно друга с учетом только вращений (ортогональная задача Прокруста) было предложено P. H. Schönemann в 1966 году, в 1970 году им же в соавторстве с R. M. Carroll предложено аналитическое решение для модификации, учитывающей, помимо вращений, смещения и масштабирование (классический прокрустов анализ), а непосредственно алгоритм 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{ CPA(X, Y): \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times d} \rightarrow \mathbb{R}^{n \times d} }[/math] - функция, выполняющая классический прокрустов анализ, вращая, смещая и масштабируя форму [math]\displaystyle{ X }[/math] так, чтобы она наилучшим образом подходила под форму [math]\displaystyle{ Y }[/math]. Возвращает матрицу из [math]\displaystyle{ \mathbb{R}^{n \times d} }[/math], отвечающую преобразованной форме [math]\displaystyle{ X }[/math].

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

Шаг 1. Инициализация.

Задаем начальные значения выравниваемых форм, центрируя их:

Вычисляем смещение для центрирования форм: [math]\displaystyle{ \bar{X_i} = \frac{1}{n} \mathbf{1}_n^T X_i }[/math], где [math]\displaystyle{ \mathbf{1}_n\in \mathbb{R}^{n \times 1} }[/math] - вектор-столбец из единиц;

Центрируем формы: [math]\displaystyle{ X_i' := X_i - \mathbf{1}_n \bar{X_i}^T, \; i = 1,\dots,m. }[/math]

Задаем начальную среднюю форму, выбирая одну из центрированных форм входного набора (например, первую): [math]\displaystyle{ M^{(0)} := X_1' }[/math].

Устанавливаем номер итерации [math]\displaystyle{ k := 0 }[/math]

Шаг 2. Выравнивание форм относительно средней.

Для всех форм выполняется их выравнивание относительно средней формы (консенсуса):

[math]\displaystyle{ X_i' }[/math] присваивается новое значение: [math]\displaystyle{ X_i' := CPA(X_i', M^{(k)}), \; i=1,\dots,m }[/math].

, \; i=2,\dots,m;</math> [math]\displaystyle{ X_1' := \frac{X_1}{\left\|X_1\right\|_F} }[/math], где [math]\displaystyle{ \left\|X_1\right\|_F = \sqrt{tr(X_1 X_1^T)} }[/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].

Для каждой формы [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]