Использование спектра оператора Лапласа в контурном анализе

DOI:

Доктор физико-математических наук, заведующий кафедрой компьютерных наук и экспериментальной математики, Волгоградский государственный университет ,

Контурный анализ – это один из методов анализа изображений и построения систем компьютерного зрения [3; 4; 6]. Наиболее известная библиотека компьютерного зрения OpenCV реализует построение контуров на изображении на основе предобработки изображения с использованием фильтров Канни и дискретного аналога производных Собеля [5]. Также эта библиотека снабжена алгоритмами вычисления различных геометрических характеристик контуров, которые могут играть роль признаков, например, в задачах классификации или идентификации изображений методами машинного обучения. Несмотря на это, в упомянутой библиотеке отсутствуют реализации алгоритмов приближенного вычисления спектра оператора Лапласа области Q, ограниченной контуром. Как нам кажется, этот спектр и, возможно, некоторые дополнительные геометрические характеристики также могут быть успешно использованы в задачах компьютерного зрения. Отчасти, это подтверждается недавними теоретическими результатами С.А. Титаренко [2] о решении известной задачи М. Каца. В указанном препринте доказано, что почти любая область однозначно определяется своим спектром оператора Лапласа с точностью до движения. В определенной степени исследование возможностей извлечения признаков на основе подходов геометрического анализа было начато в работе [1].

Дискретизация краевой задачи вычисления спектр оператора Лапласа

Ди = Ли, u l da = 0

приводит к задаче вычисления спектра линейного оператора L в некотором конечномерном пространстве. Опишем вкратце, как это делается.

Ввиду того что растровая плоскость дискретна, задача вычисления спектра области контура может быть записана в дискретной форме следующим образом. Будем считать, что контур dQ расположен на сетке с шагом 1 и представляет собой последовательность пар (хк,ук) таких, что max{|xk - Xk-i|, |ук — Ук-11} = 1,к = 1, ...,К.

Тогда приближенным значением оператора Лапласа будет выражение

(^Дu) ij ~ ^u i - 1j + ^u i+1j + ^u ij - 1 + ^u ij+1 ^— 4^U ij •

При этом вычисление происходит только для внутренних узлов области контура Q. На рисунке 1 белыми точками изображены внутренние узлы сетки, а черными – граничные точки, они же – точки контура.

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

^u i - 1j + ^u i+1j + ^u ij - 1 + ^u ij + 1 4^U ij — ^{Л и} ij ,                        (1)

где пары (i,j ) соответствуют внутренним точкам. При этом мы требуем выполнения граничного условия

U ki = 0

для пар (к,Г), соответствующих точкам контура.

Пронумеруем узлы сетки, которые лежат внутри области G произвольным образом, и пусть N - их число. Тогда найдется такой линейный оператор L _q : R ^N ^ R ^N , что задача (1) будет эквивалентна задаче

L q u + Ли = 0,

Рис. 1. Граф Gq расчетной области где и = (и1, ...,un) - вектор значений искомой сеточной функции во внутренних узлах.

Определим граф G _q = (V, Е) следующим образом. В качестве вершин рассмотрим все узлы сетки, которые лежат внутри области О или на контуре д О. Две вершины в графе G определяют ребро, если соответствующие узлы сетки являются соседними (см. рис. 1).

Несложно доказывается следующая лемма.

Лемма 1. Матрица оператора L q получается из матрицы Кирхгофа графа G q удалением строк и столбцов, соответствующих точкам контура д О с точностью до перестановки строк и столбцов.

Напомним, что матрица К = К (G) Кирхгофа для графа G определяется следующим образом:

{ deg(i) i = j,

• - 1       (i,j ) Е Е,

• 0 в противном случае.

Здесь deg(i) - степень вершины i e V .

1.    Представление расчетной области

Область О, которую ограничивает контур на растровой плоскости, будем, как сказано выше, рассматривать как множество узлов целочисленной сетки с шагом 1. Зададим такое множество трехмерным массивом B _ij_k . Срез этого массива B _i представляет собой двумерный массив двуместных массивов вида [х 1 ,х₂], х 1 <  х ₂ , причем для всякого х 1 <  х <  х ₂ точка (х, i) Е О и является либо ее внутренней точкой, либо граничной. Таким образом, видно, что массив представляет собой расслоение области О на горизонтальные отрезки вида [х 1 ,х ₂ ], х 1 < х ₂ . Для такого представления расчетной области опишем алгоритм построения соответствующего графа G _q .

Шаг 1. Построение множества вершин графа. Выполняя обход массива В по первым двум индексам i,j , извлекаем отрезки [х 1 ,х ₂ ]. Для всякого х 1 <  х <  х ₂ формируем вершину (х,i) графа G _q .

Шаг 2. Построение множества ребер графа. Для всякой пары вершин v _i ,V j Е Е V ( G _q ) определяем величину 5 = l v _i — V j | ² в обычной евклидовой метрике. Тогда пара (i,j ) Е Е ( G _q ) тогда и только тогда, когда 5 = 1.

Шаг 3. Вычисление граничных точек. Для каждой вершины v графа вычисляется ее степень deg(v). Это легко делается за один проход по массиву ребер Е . Гранич-ность точки определяется условием deg(v) <  4.

Bj —* [Xj               [x2,x3]                        [x4]

Рис. 2. Массив списков В _г

2. Представление контура в OpenCV

Библиотека OpenCV вычисленный контур представляет двумерным тензором C ij , где индекс i отвечает за номер опорной точки на контуре, индекс j = 1, 2, так, что C _ij представляет собой j -ю координату i-й опорной точки контура. Заметим также, что C _ij – это целочисленный тензор. При этом выполнено условие

\Сц - C(i+i)i\ =к   И   \Ci2 - C(i+i)2| = к для некоторого натурального к = 1,2,..., или

\Сц — C(i+i)i| = 0 или   \Ci2 — С^+1)2 \ = о для всех i = 1, 2,...,N — 1, где N - число опорных точек контура. Таким образом, контур определяется последовательностью своих опорных точек, такой, что две соседние опорные точки расположены на одной горизонтали, на одной вертикали, либо диагонали. Заметим, что контур целиком восстанавливается по этим опорным точкам. Для вычисления спектра матрицы оператора L требуется перевести представление контура в представление расчетной области, которое описано в предыдущем параграфе. Ниже мы приводим соответствующий алгоритм такого перевода.

Шаг 1. Вычисление пересечений контура с горизонтальными прямыми. Формируется массив В , индексируемый целым числом i, таким образом, что B _i представляет список одно- или двуместных массивов b Е B _i (см. рис. 2). В первом случае список содержит единственное значение ж, такое, что (х,i) - точка, лежащая на контуре. Во втором случае список содержит два числа [х 1 ,х ₂ ], х 1 < х ₂ , такие, что для всякого х 1 <  х <  х ₂ точка (х, i) лежит на заданном контуре. Такой массив В строится за один последовательный проход по точкам контура.

Шаг 2. Сортировка. На следующем шаге осуществляется сортировка списков b из B _i в порядке возрастания их первых элементов b[0].

Шаг 3. Удаление дубликатов. Для каждого массива X = B _i удаляем одноместные массивы X [j ], если его элемент равен последнему элементу в X [j — 1] или равен первому элементу в X [j + 1]. Таким образом, сформировался массив В граничных точек (точек контура). При этом B _i содержит упорядоченный по оси абсцисс массив значений х-координат точек контура.

Шаг 4. Слияние списков. На этом этапе мы основываемся на том, что внутренние точки области находятся между нечетными и четными списками массива B _i . Поэтому пару соседних списков [х 2j _{- 1} , х 2j _{- 1} ] и [х 2j ,х ^ ] заменяем на список [х 2j _{- 1} ,х 2j ]. В результате получаем массив B представления расчетной области контура Q.

3.    Тестирование

Для тестирования алгоритмов был создан массив изображений геометрических фигур: квадратные области и круги. Для каждого изображения вычислен контур области

Q фигуры и с использованием описанных выше алгоритмов построен граф G _q и соответствующая матрица оператора L _q . Далее, для матрицы оператора L _q с использованием библиотеки SciPy, вычислены первые п собственных чисел, которые дополнительно были умножены на площадь области Ω. Последнее действие необходимо для того, чтобы данные контура зависели только от его формы. Для тестирования эффективности извлеченных признаков контуров на изображении на основе спектра оператора Лапласа проведены численные эксперименты на предмет линейной разделимости двух классов изображений – двух, указанных выше, геометрических фигур. С этой целью использовался метод опорных векторов с ядром «linear». Известно, что на линейно разделимой выборке этот метод дает 100 % правильных предсказаний. Ниже в таблице представлены результаты расчетов. Размер изображений был выбран 28 на 28 точек, количество изображений - по 100 каждого класса. В первом столбце указано число п собственных чисел матрицы оператора L _q , участвующих в формировании выборки.

n	Точность
2	76 %
4	93 %
8	96 %
12	100 %
16	100 %

Следует заметить, что уже для п =12 выборка становится линейно разделимой. Другими словами, предлагаемый метод дает эффективное уменьшение размерности признакового пространства в 28 • 28/12 >  9 • 7 = 63 раз. Среднее время обработки одного файла изображения составило 0, 015 секунд.

Для оценки точности распознавания геометрической фигуры на изображении различными моделями машинного обучения был сгенерирован набор из 200 таких изображений. В таблице ниже представлены результаты тестирования в зависимости от параметров: размеров изображений size и количества п собственных чисел оператора ^L q .

Параметр size	(32 , 32)	(48 , 48)	(48 , 48)	(48 , 48)
Параметр п	32	8	16	36
Метод ближайших соседей	98 %	98 %	98 %	100 %
Случайный лес	98 %	98 %	98 %	100 %
Метод опорных векторов (kernel = «linear»)	98 %	98 %	98 %	100 %
Наивный байесовский классификатор	96 %	98 %	98 %	100 %
Линейный дискриминантный анализ	100 %	100 %	100 %	100 %
Метод решающих деревьев	100 %	98 %	98 %	98 %

Рис. 3. Примеры изображений силуэтов самолетов и птиц (в полете)

На втором этапе тестирования рассмотрены изображения силуэтов самолетов и птиц. Пример таких изображений показан на рисунке 3. Рассматривалась задача классификации изображений – силуэт самолета или птицы изображен на рисунке. Из наглядного рассмотрения примеров этих изображений следует, что контуры объектов сложно различимы. Поэтому в этой задаче ожидать хороших результатов не приходится. Тем не менее в некоторых случаях ML-модели неплохо справляются с задачей распознавания типа контура объекта. Сводная таблица с результатами приведена ниже. Варианты, превышающие 80 % правильных предсказаний, выделены полужирным шрифтом.

Параметр size	(96 , 96)	(96 , 96)	(100 , 100)	(90 , 90)
Параметр п	32	36	32	36
Метод ближайших соседей	77 %	90 %	82 %	82 %
Случайный лес	72 %	77 %	69 %	82 %
Метод опорных векторов	77 %	86 %	74 %	82 %
Наивный байесовский классификатор	63 %	77 %	82 %	69 %
Линейный дискриминантный анализ	50 %	68 %	69 %	65 %
Метод решающих деревьев	63 %	72 %	65 %	69 %

4.    Программная реализация

Описанные выше алгоритмы реализованы на языке программирования Python. Все программные модули доступны в открытом репозитории автора статьи по адресу Для скачивания репозитория в свой локальный репозиторий достаточно воспользоваться командой

В каталоге dataset-npz репозитория лежат готовые файлы данных – результат обработки соответствующих файлов изображений. Для извлечения массивов необходимо выполнить операции:

X_train = data["X_train"]

Y_train = data["Y_train"]

X_test = data["X_test"]

Y_test = data["Y_test"]

В название npz файла данных включены параметры размера изображений size и число п извлеченных собственных чисел оператора L q .