Введение к работе
Актуальность темы. Распознавание, классификация и идентификация плоских изображений – традиционное направление исследований в области теоретической информатики. В частности, актуальным направлением является распознавание печатных и рукописных символов в условиях помех. Минимизация временной сложности и повышение точности схем распознавания и идентификации изображений являются важнейшими требованиями, предъявляемыми к распознающим системам. В то же время обработка изображений сопряжена со значительным объемом вычислений, как правило, в условиях искажения поступающей информации. Широко распространены методы распознавания, основанные на анализе контурных представлений объектов: считается, что форма контуров является наиболее стабильным признаком при яркостных искажениях. Многие задачи распознавания необходимо решать в жестких ограничениях временной сложности, поэтому алгоритмы распознавания должны быть оптимизированы по времени выполнения, временная оптимизация может достигаться за счет распараллеливания. Компьютерная реализация исследуемых алгоритмов, помимо высокого быстродействия, требует практической устойчивости к искажениям и помехам. Ограниченность объемов машинной памяти, выделяемой под пространство эталонов, а также требование минимизации временной сложности делают актуальными разработку и исследование распараллеливаемых алгоритмов распознавания, классификации и идентификации, инвариантных к сдвигу, масштабированию и ротации изображений. Существующие методы сталкиваются с трудностями как при построении схем распознавания, так и при выборе эталонных последовательностей. При этом многие методы характеризуются существенной вычислительной и временной сложностью и либо не адаптированы к параллельным вычислительным системам, либо ориентированы на узкий класс идентифицируемых изображений. В направлении решения существующих проблем целесообразно исследовать применение схем сортировки. Сортировка делает обрабатываемую информацию упорядоченной, на данной основе достигается упрощение алгоритмов распознавания, количество используемых формул и численных методов сокращается. Вследствие этого и по построению сортировки ее применение позволяет снизить рост погрешности: в основе сортировки лежат лишь операции сравнения, сами сортируемые элементы не изменяются. В известных методах распознавания сортировка применяется преимущественно для упорядочения эталонных образов. Методы распознавания с использованием сортировки, как правило, отличаются сугубо технической направленностью, при обработке графической информации сортировка не используется в качестве конструктивной части метода, на ее основе не достигается адаптация к изменениям масштаба и поворота изображений в условиях помех.
Цель диссертационной работы состоит в построении метода распознавания и идентификации плоских изображений, ограниченных связным замкнутым контуром, который достигает сравнительного упрощения на основе упорядочения информации при помощи алгоритмов сортировки. Конструируемый метод должен расширить класс детерминированно идентифицируемых изображений в условиях сдвига, ротации и изменения масштаба, достигать устойчивости идентификации за счет итеративности алгоритма и выполнения условий сходимости. Одной из целей исследования является преобразование метода в параллельную форму и выполнение соответственных оценок временной сложности.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
1. Разработать метод распознавания плоских изображений, инвариантный относительно сдвига, ротации и масштабирования, который позволял бы осуществлять устойчивое построение векторов распознавания изображений с произвольными замкнутыми контурами в условиях растеризации и обладал свойством параллелизма.
2. Синтезировать параллельный алгоритм фильтрации искажений контура, который позволял бы устойчиво идентифицировать изображение в условиях помех с минимизацией временной сложности.
3. Построить структуру данных для базы эталонов и схему идентификации изображения путем последовательного сравнения вектора распознавания с эталонными векторами по норме в условиях искажения контура.
4. Синтезировать алгоритм идентификации отличительных особенностей фрагментов контуров по экстремальным отклонениям от хорд.
5. Выполнить программный эксперимент по распознаванию и идентификации контурно представленных изображений с учетом искажений, сдвига, ротации и масштабирования на растре в аспекте сравнения с известными методами.
Методы исследования опираются на теоретические основы информатики, на методы прикладной информатики, на теорию сложности, используются алгоритмы сортировки, цифровой обработки изображений и распознавания образов, применяются современные информационные технологии, структурное и объектное программирование.
Достоверность результатов вытекает из математического обоснования конструктивных алгоритмов распознавания и идентификации изображений, подтверждается оценками временной сложности, а также результатами программного моделирования и эксперимента.
Научная новизна заключается в следующем:
1. Предложен итерационный метод распознавания плоских изображений, отличающийся формированием экстремальных признаков на основе сортировки, сходимостью для широкого класса изображений, инвариантностью относительно сдвига, ротации и масштабирования, который позволяет осуществлять устойчивое построение векторов распознавания изображений с произвольными замкнутыми контурами в условиях растеризации и обладает параллелизмом.
2. Синтезирован параллельный алгоритм фильтрации искажений контура при радиально-круговой развертке изображения, который отличается от известных фильтров по построению и позволяет на его основе устойчиво идентифицировать изображение при ограниченных искажениях с минимизацией временной сложности: все экстремумы полярного радиуса входного изображения в максимально параллельной форме могут быть идентифицированы и отфильтрованы с временной сложностью.
3. Разработана структура данных для базы эталонов и иерархическая схема однопроходного поиска в подклассе эталонных векторов, которая позволяет идентифицировать изображение путем последовательного сравнения вектора распознавания с эталонными векторами по норме.
4. Представлены схемы изменения размерности векторов распознавания с учетом иерархии эталонов, позволяющие идентифицировать отличительные особенности фрагментов контуров по экстремальным отклонениям от хорд и на этой основе уточнять идентификацию изображения в целом.
5. Выполнен программный эксперимент по распознаванию и идентификации контурно представленных изображений широкого класса с учетом ограниченных искажений, сдвига, ротации и масштабирования, в результате которого выявлено положительное отличие предложенного метода от известных по совокупности компонент сравнения.
Основные положения, выносимые на защиту:
1. Предложен распараллеливаемый сходящийся итерационный метод построения векторов распознавания растровых изображений с произвольными замкнутыми контурами, инвариантный относительно их сдвига, ротации и масштабирования.
2. Синтезирован параллельный алгоритм фильтрации искажений контура при радиально-круговой развертке растрового изображения, позволяющий устойчиво идентифицировать изображение при ограниченных искажениях с минимизацией временной сложности.
3. Разработана структура данных для базы эталонов и иерархическая схема однопроходного поиска, позволяющая идентифицировать изображение путем сравнения вектора распознавания с эталонными векторами по норме.
4. Разработаны схемы изменения размерности векторов распознавания с учетом иерархии эталонов, позволяющие идентифицировать отличительные особенности фрагментов контуров по экстремальным отклонениям от хорд и на этой основе уточнять идентификацию изображения в целом.
Практическая ценность диссертационного исследования состоит в применимости предложенного метода для решения актуальных задач распознавания плоских изображений, в том числе распознавания печатных и рукопечатных символов в условиях искажений. Компоненты метода применимы для помехоустойчивого анализа формы изображений, выделения ключевых точек контуров и получения их топологических характеристик. Предложенный метод может служить основой для разработки параллельной системы распознавания контурно представленных растровых изображений с высоким быстродействием и практической устойчивостью к ограниченным искажениям контуров.
Внедрение и использование результатов работы. Полученные в работе результаты приняты к использованию в ОАО «Таганрогский завод «Прибой» для выявления экстремумов числовых последовательностей при разработке алгоритмического обеспечения параллельной цифровой обработки гидроакустических сигналов и для разработки алгоритмического и программного обеспечения анализа гидроакустических изображений, получаемых от антенных систем высокого разрешения; в ГОУВПО «Таганрогский государственный педагогический институт» на факультете информатики в преподавании курсов «Информатика», «Теоретические основы информатики», «Информационные технологии в математике», «Теоретические основы нейроинформатики», «Архитектура нейрокомпьютеров», «Практикум решения задач на ЭВМ», что подтверждено соответствующими актами, приведенными в приложении 8 к диссертационной работе.
Апробация работы. Основные результаты работы были представлены на I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, ТГПИ, 2003 г.); XI международной научной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2005 г.); международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.); III всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2005 г.); Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» (Таганрог, ТГПИ, 2008 г.); IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2008 г.).
Публикации. По материалам работы опубликовано 10 печатных работ общим объемом около 7 печатных листов, в том числе 2 статьи в журналах из перечня рекомендуемых ВАК РФ.
Структура и объём работы. Диссертационная работа состоит из введения, трех глав основного раздела, заключения, списка литературы и восьми приложений. Основное содержание работы изложено на 182 страницах, включая список литературы из 172 наименований.
