Software & Systems

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

Подготовка изображения

В большинстве случаев объект на изображении находится рядом с другими объектами, которые мешают анализу изображения. В работах [1, 2] рассмотрены некоторые алгоритмы по удалению фона на растровом изображении, по понижению количества шума, выделению локальных объектов и т.п. Основная идея данных работ заключается в применении волнового алгоритма удаления фона на растровых изображениях. Одним из результатов такого подхода к анализу изображений стало выделение объектов из фона с использованием прозрачности пикселей (alpha-кана­ла). К сожалению, данный метод не лишен недостатков. Так как исследуемые объекты, как правило, имеют причудливую форму и некоторые их части визуально сливаются с фоном, после обработки  отдельные области объектов отделяются и удаляются. Для решения проблемы целостного выделения объектов были разработаны алгоритмы склейки и отсеивания изображений, не отвечающих критерию близости к эталонам. Этим критерием являлось отношение площади выделенного объекта к площади описанного вокруг него круга. На основе дальнейших тестов было выяснено, что данный критерий не универсален и не всегда дает желаемый результат.

Для улучшения алгоритма выделения предлагается учитывать не только размеры объекта, но и его форму, а именно, строить скелет объекта и анализировать полученный граф.

Волновой алгоритм для нахождения скелета

Одним из способов нахождения скелета изображения является волновой алгоритм [3, 4]. В нем используется особый вид волны, названный сферическим. Это комбинация последовательного применения 4- и 8-связной волны. В результате волна распространяется в виде восьмиугольника, уверенно огибающего препятствия. Здесь наблюдается интересный эффект: не более чем через 2*N шагов распространение приобретает устойчивый характер вне зависимости от начальной точки. Поведение волны предсказуемо и на траекториях, отличных от прямой. Огибающие свойства волны имеют свои особенности. Мелкие препятствия (1–2 пикселя) мало влияют на распространение волны, внося незначительные помехи. Более крупные препятствия на изображении вызывают значительные искажения картины распространения волны. Следовательно, необходима предварительная обработка изображения, направленная на устранение нежелательных помех.

Алгоритм утоньшения для нахождения скелета

Рассмотрим подходы к нахождению скелета графического объекта, основанные на последовательном утоньшении границ объекта [5, 6]. Предлагаются два алгоритма утоньшения.

Первый алгоритм основан на применении к изображению восьми масок, полученных из двух (см. табл.) путем поворота каждой на 90, 180 и 270 градусов. Каждая маска отвечает за удаление горизонтальных, вертикальных и диагональных линий, наклоненных под углом 45 градусов.

Маски утоньшения

Алгоритм заключается в следующем. Каждый пиксель изображения и его ближайшие соседи подвергаются тесту на соответствие наложенной маски. Маска накладывается таким образом, что текущий пиксель становится в ее середину, а ближайшие соседи покрываются остальной частью маски. Если сам пиксель и его соседи удовлетворяют условию, что под ячейкой маски с номером 0 находится фон объекта, а под ячейками с номером 1 – сам объект, то пиксель, лежащий под центральной ячейкой маски, удаляется на изображении.

Второй алгоритм основан на применении к изображению взвешенных матриц. Причем вес точки объекта определяется ее яркостью, а яркость каждой точки на скелете объекта убывает пропорционально расстоянию от центра тяжести. Данный алгоритм не подходит в нашем случае, так как скелеты объектов могут распасться на части, что затруднит их дальнейший анализ. На рисунках 1–3 показаны результаты работы указанных алгоритмов. Здесь a) – исходное изображение, b) – результаты работы алгоритма применения восьми ядер, c) – результаты работы алгоритма со взвешенной матрицей.

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

Получение и сравнение графов скелетов

Для анализа скелета объекта необходимо представить его в виде взвешенного графа (см. рис. 4). Для удобства визуализации получившийся граф наложен на исходное изображение (черные точки – вершины графа, серые – его дуги). Веса дуг определяются количеством пикселей, лежащих на пути передвижения по изображению скелета между узловыми точками. На рисунке отображены результаты выделения и анализа скелетов самолетов, в том числе a) – выделенный самолет без фона, b) – полученный граф скелета, c) – упрощенный граф скелета, d) – самый длинный путь в графе скелета (темно-серая линия).

Алгоритм построения графа скелета состоит из следующих этапов.

1.  Изображение со скелетом объекта представляется в виде матрицы, размеры которой соответствуют размерам изображения. Скелет объекта в матрице маркирован цифрами 1, а фон – цифрами 0.

2.  Находится ячейка матрицы с одним соседом, маркированным цифрой 1. Если таких ячеек нет, остановка алгоритма.

3.  Координаты текущей ячейки заносятся в массив описания дуги.

4.  В текущую ячейку ставится цифра 2.

5.  Если у текущей ячейки соседей, маркированных цифрой 1, не больше одного, координаты текущей ячейки изменяются на координаты соседа. Переход к пункту 3.

6.  В массив вершин графа добавляются координаты текущей ячейки.

7.  Если у текущей ячейки нет соседей, маркированных цифрой 1, переход к пункту 10.

8.  В ячейки соседей, маркированных цифрами 1, ставятся цифры 3.

9.  Координаты текущей ячейки заносятся в стек столько раз, сколько было маркировано соседей.

10.   Массив точек дуги добавляется к описанию текущей вершины графа.

11.   Если стек не пуст, извлекаются координаты ячейки. Переход к пункту 3. Иначе описание скелета добавляется в массив и осуществляется переход к пункту 2.

Алгоритм имеет недостаток. Возможна ситуация, когда появится дуга, в которую входят всего две точки – узловая и конечная. Такой пример отражен на рисунке 5, где показаны четыре пути из узловой (черной) точки, маркированные буквами A, B, C и D.

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

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

После достаточного упрощения скелетов сравниваются полученные и эталонные графы. Полное соответствие графов совершенно необязательно, так что, если веса дуг или их отношения мало отличаются, графы считаются похожими. Для решения задачи можно применить метод сравнения иерархий графов [7]. Для этого вершины одного графа упорядочиваются относительно какой-нибудь конечной вершины, а для другого графа подбирается подобная комбинация вершин и дуг. Упорядочение вершин визуально можно представить как подвешивание дерева за одну из конечных вершин. Если находится подобная комбинация вершин и дуг, полученный и эталонный объекты схожи по своей структуре.

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

подхода заключает в том, что при анализе учитываются расстояния между узловыми точками выделенного скелета. Это означает, что графы одинаковых объектов, масштабированных и повернутых в любом направлении, будут подобны.

Литература

1. Выделение и распознавание локальных объектов на аэрокосмических снимках / А.Н. Виноградов [и др.] // Авиакосмическое приборостроение. 2007. № 9. С. 39–45.

2. Kalugin F. Pogodin S. Object contour extraction at aerospace photos. Proceedings of the 9th International Conference (Pattern Recognition and Information Processing). Minsk, Belarus: 2007. Vol. 1. pp. 177–182.

3. Клубков И. Применение волнового алгоритма для нахождения скелета растрового изображения, 2004. URL: http://igdrassil.narod.ru/pc/work/Vectorisation.html (дата обращения: 04.09.2008).

4. Шикин Е.В., Боресков А.В. Компьютерная графика. М.: Мир, 1995.

5. Fisher R., Perkins S., Walker A. and Wolfart E. Skeletonization / Medial Axis Transform, 2003. URL: http://homepages.inf.ed. ac.uk/rbf/HIPR2/skeleton.htm (дата обращения: 15.05.2008).

6. Ballard D. and Brown C. Computer Vision: Prentice-Hall, 1982. 8 p.

7. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та матем., 1999. 270 с.