Задача анализа формы изображений возникает в большинстве разработок современных систем машинного зрения. К таким задачам относятся, например, поиск заданных слов в рукописных документахопределенных символов на географических картах и схемахавтоматическое чтение этикеток, маркировокидентификация, классификация и сортировка деталейобнаружение и опознавание цели в телевизионных системах наблюдения и т. д.
Такой анализ подразумевает этап выявления признаков формы по изображению и составления признакового описания объекта. На последующих этапах на основе полученного признакового описания объекта принимается решение о его форме. Для принятия этого решения могут быть использованы различные методы классификации или, например, сравнение описания с описаниями эталонных объектов.
Можно выделить два традиционных подхода к построению признаковых описаний формы объектов: структурный и контурный. При использовании первого рассматривают объект в целом и принимают решения, исходя из его топологической структуры. Обычно именно таким образом проводится распознавание стилизованных рукописных символов, например, иероглифов, когда идентифицируются штрихи и другие элементарные блоки, из которых строится символ. В качестве признаков формы при таком подходе могут выступать топологические инварианты: число компонент, число отверстий в многосвязных компонентах и т. д. При другом подходе исследуется контур силуэта: обычно отыскиваются углы, выступы, впадины и другие точки с высокими значениями кривизны. Примером использования такого подхода является распознавание силуэтов профилей человеческих лиц.
Для получения информации о форме контура применяются различные представления границы объекта. Для описания структуры объекта широко используется представление в виде скелета (серединных осей). Следует отметить, что большинство существующих методов анализа формы ориентируется на использование либо только граничного, либо только скелетного представления, и, тем самым, только контурных или структурных признаков. В то же время существуют задачи, в которых необходимо использовать как структурные, так и контурные признаки — например, при обработке технических чертежей или распознавании рукописного текста. Поэтому целесообразно иметь возможность комплексного анализа структуры и границы.
Традиционно использование растровых моделей границы и скелета образа, в которых граница и скелет представлены в виде растровых изображений. Но понятия границы и скелета математически строго определены для замкнутой плоской области. Поэтому при таком «дискретном» подходе приходится адаптировать эти понятия к геометрии регулярных точечных пространств. Кроме того, интерпретировать для растрового представления приходится и признаки формы, которые также формулируются исследователем для непрерывных кривых и областей. Такая интерпретация является достаточно сложной задачей.
В то же время возможен более адекватный «непрерывный» подход, при котором по растровому изображению создается его непрерывная модель и эта модель используется для выявления признаков формы.
Недостатком непрерывного подхода является то, что при использовании непрерывного скелета в практических исследованиях возникает проблема неоднозначности его вычисления и, соответственно, толкования. Форма скелета чрезвычайно чувствительна к локальным свойствам границы образа. Две области, имеющие несущественные для глаз различия границы, например, за счет шумов, могут иметь принципиально различные в смысле топологической структуры скелеты. Вместе с тем, сравнительный анализ этих различающихся скелетов показывает, что в них присутствуют общие ветви, которые и определяют фундаментальные свойства структуры образа. Задача состоит в том, чтобы отделить эти существенные элементы скелета от несущественных, определяемых шумовыми эффектами. Решение этой задачи обычно осуществляется путем «стрижки» скелета, т. е. отсечения несущественных ветвей. При этом явные критерии определения существенных и несущественных элементов скелета не формулируются, и отсечение осуществляется на основе эвристических правил. В результате не может быть оценена точность вычисленных скелетов, что затрудняет их дальнейшее использование.
Таким образом, задача построения непрерывной модели дискретного изображения с контролируемой точностью аппроксимации и комплексного анализа его структуры и границы на основе такой модели является актуальной.
Подход, который предлагается в данной работе — непрерывная векторизация. Его суть заключается в построении непрерывной аппроксимирующей границы и непрерывного скелета дискретного образа. Такое непрерывное представление позволяет получить информацию о связи границы и скелета и использовать ее при анализе формы изображения.
Целью настоящей работы является повышение качества обработки и распознавания изображений на основе исследования теоретически корректной непрерывной гранично-скелетной модели дискретного изображения, полученной методом непрерывной векторизации.
Научной задачей является построение теоретически корректной модели непрерывного гранично-скелетного представления дискретного образа и разработка эффективных методов ее получения, а также методов анализа изображений на основе комплексного исследования полученного непрерывного гранично-скелетного представления.
Сложность обусловлена большой размерностью (граница и скелет могут содержать до нескольких десятков тысяч элементов) и высокими требованиями к эффективности алгоритмов (поскольку многие задачи решаются в системах реального времени).
Решение задачи основывается на следующем подходе:
1) дискретно-непрерывное преобразование бинарного изображения в непрерывное гранично-скелетное представление. Исходное дискретное изображение вначале аппроксимируется непрерывным бинарным образом, т. е. некоторой фигурой, имеющей непрерывную границу. Эта аппроксимация может быть осуществлена неоднозначно в пределах точности, определяемой разрешающей способностью дискретного изображения. При аппроксимации границы дискретного образа непрерывной линией кривизна этой линии может очень сильно меняться при сохранении в нужных пределах точности аппроксимации границы. Это приводит к тому, что получаемые скелеты для непрерывных образов с близкой границей сильно различаются в смысле их топологической структуры. Для того чтобы выделить общие существенные структурные свойства всего множества таких скелетов, в работе вводится понятие «скелетного ядра» — множества точек, входящих в окрестность скелета любого непрерывного объекта, аппроксимирующего с заданной точностью исходный дискретный образ. В скелете каждого аппроксимирующего непрерывного объекта можно выделить так называемый «базовый скелет» — подмножество, аппроксимирующее с заданной точностью скелетное ядро. В работе приводится метод построения базового скелета для аппроксимирующей полигональной области. Таким образом, дискретно-непрерывное преобразование осуществляется по следующей схеме: граница растрового бинарного изображения аппроксимируется многоугольниками минимального периметрастроится непрерывный скелет полученной многоугольной фигурыв полученном непрерывном скелете выделяется «базовый скелет» .
2) сегментация скелета на отдельные структурные элементы (штрихи) с учетом гладкости и кривизны сопряженных элементов границы;
3) сравнение элементов гранично-скелетного представления на основе морфингагомеоморфного отображения, минимизирующего заданный критерий.
Новые научные результаты, выносимые на защиту:
• метод построения скелетного представления с контролируемой точностью аппроксимации. Известные методы строят скелет по эвристическим правилам, что не позволяет однозначно определить скелет и оценить точность скелетного представления. В отличие от них предлагаемый метод позволяет корректно определить «базовый скелет», аппроксимирующий образ с заданной точностью;
• метод штриховой сегментации гранично-скелетного представления. Сегментация сводится к выделению в непрерывном скелете, который можно рассматривать как граф, подграфов, степень вершин которых не превышает 2, соответствующих отдельным штрихам. Данное выделение проводится с учетом характеристик гладкости границы в местах соединения штрихов;
• метод сравнения изображений на основе гомеоморфного преобразования контуров. Участки непрерывной границы изображения сравниваются с использованием механической модели, описывающей деформацию контуров путем растяжения и изгиба. В качестве меры различия между контурами используется минимальная величина работы по преобразованию одного контура в другой на основе такой деформации. Предлагаемый метод отличается от известных аналогов тем, что использует полигональную аппроксимацию границы образа и строит гомеоморфное преобразование полигональной границы.
Структура диссертации. Диссертация состоит из введения, четырех глав и заключения. Во введении описана актуальность и цели работы. В первой главе рассматривается задача анализа формы изображений, проводится обзор литературы, посвященной построению различных граничных и скелетных представлений изображения. Во второй главе рассматривается задача построения непрерывного.
4.7. Выводы.
В данной главе предложен метод сравнения изображений, использующий механическую модель, описывающую деформацию непрерывных контуров путем растяжения и изгиба. В отличие от существующих аналогов этот метод сравнения основан на построении гомеоморфного отображения контуров.
Метод позволяет сравнивать полигональные контуры, которые можно эффективно с точки зрения вычислительной сложности построить. Кроме того, можно проводить сравнение не только контуров изображений, но и отдельных участков контуров, а также ветвей непрерывных скелетов изображений;
Приведенные в главе примеры использования предлагаемого метода для решения прикладных задач показывают, что данный метод позволяет эффективно сравнивать изображения с достаточно сложной линией контура, устойчив к изменению линейных размеров контуров, изменению пространственной ориентации объектов на изображении.
Заключение
.
В работе развивается непрерывный подход к анализу формы растровых изображений. Данный подход основывается на идее немедленного перехода от растрового изображения к непрерывной модели изображения без использования растровых преобразований. Это позволяет применять признаки формы без их адаптации к растровым изображениям.
В работе предлагается метод построения информативной, контролируемой по точности непрерывной модели растрового изображения. Модель состоит из границы аппроксимирующей изображение полигональной области и базового скелета данной области, отражающего фундаментальные топологические свойства образа. Несмотря на кажущуюся избыточность такой гранично-скелетной модели, ее применение представляется целесообразным, поскольку такая модель позволяет связать границу и скелет изображения и исследовать их совместно.
В частности, такое комплексное исследование оказывается полезным при решении задачи штриховой сегментации, когда требуется учет информации о структуре объекта и локальных свойствах гладкой границы. В работе представлен и исследован метод такой штриховой сегментации, использующий предложенную гранично-скелетную модель.
Также в работе рассмотрен метод сравнения полигональных линий и замкнутых контуров на основе построения гомеоморфного отображения. Применение этого метода к предложенной гранично-скелетной модели дает возможность распознавания изображений сравнением с эталоном. В роли признака формы в этом случае выступает контур, отдельный участок контура или ветвь скелета изображения. С помощью предложенного метода можно эффективно сравнивать изображения достаточно сложной формы. Метод устойчив к изменениям линейных размеров и пространственной ориентации объектов на изображении.
В работе рассмотрена структура данных, предназначенная для описания, предлагаемой гранично-скелетной модели растрового изображения. Использование этой структуры позволяет эффективно обрабатывать гранично-скелетное представление, реализовать предложенные в работе алгоритмы, осуществлять поиск элементов в представлении и установление взаимосвязей между ними.