Software & Systems

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

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

Обычно пространство  предполагается евклидовым. Для этого случая справедливы следующие преобразования, которые необходимы для перехода от матрицы расстояний D=(dij) к координатам объектов в пространстве для визуального анализа x1,…,xp’.

Метод определения координат точек x1,…,xN (с точностью до ортогонального вращения) и размерности пространства, в которое они отображаются, основан не на непосредственном использовании матрицы D, а на преобразовании ее в матрицу B скалярных произведений центрированных векторов  где m – вектор средних значений.

Между элементами матрицы B и расстояниями dij установлено следующее соотношение:

Процедура перехода от D к B называется двойным центрированием D. Матрица B размера (N´N) обладает следующими свойствами.

1.   Неотрицательно определена.

2.   Ранг матрицы B равен размерности искомого пространства отображения.

3.   Ненулевые собственные числа матрицы B, упорядоченные в порядке убывания, совпадают с соответствующими собственными числами матрицы S=XXT, где X – центрированная матрица данных (не известная нам). Матрица S/N есть матрица ковариаций для X.

4.   Пусть ur есть r-й собственный вектор матрицы S, соответствующий r-му собственному числу lr. Тогда вектор значений r-й главной компоненты будет zr=XTur.

В то же время, пусть yr – r-й собственный вектор матрицы B, соответствующий тому же собственному значению lr, то есть .

Тогда .

Из свойства 4 следует, что, решая задачу собственных чисел и собственных векторов для матрицы B и ограничиваясь ненулевыми собственными числами l1,…,lp, получаем координатное представление точек в пространстве главных компонент, основываясь на приведенных формулах.

Элементы матрицы B могут быть представлены в виде .

Очевидно, решение Z является линейной функцией X и определяется лишь с точностью до ортогонального преобразования, поскольку после применения к матрице Z преобразования вращения преобразованная матрица Z* столь же точно восстанавливает матрицу B, как и матрица Z. Поэтому такое шкалирование называют линейным.

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

С точки зрения задачи нормализации силуэтов объектов методы многомерного шкалирования могут быть использованы для центрирования, ориентирования и приведения к единому масштабу силуэтов того или иного объекта, изображение которого получено в разных ракурсах. В качестве многомерных объектов для изображения могут выступать все точки контура (взятые с определенным шагом) либо некоторые характерные точки силуэта, вычисленные тем или иным способом. Между этими точками вычисляется матрица попарных расстояний D и далее применяется процедура многомерного шкалирования для вычисления новых координат исходных точек. При этом силуэт автоматически центрируется, и первая ось нового пространства ориентируется таким образом, что на нее приходится максимальный разброс координат новых точек, а вторая ось ортогональна первой, и разброс точек на ней соответствует второму собственному числу матрицы S=XXT.

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