Информационная технология восстановления изображений, основанная на принципах распознавания образов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Чернов, Андрей Владимирович

• Чернов, Андрей Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Чернов, Андрей Владимирович

ВВЕДЕНИЕ

ГЛАВА 1. РЕШЕНИЕ ЗАДАЧИ ВОССТАНОВЛЕНИЯ ИЗОБРАЖЕНИЙ

НА ОСНОВЕ МЕТОДОЛОГИИ РАСПОЗНАВАНИЯ ОБРАЗОВ

1.1. Постановка задачи восстановления изображений

1.2. Общая схема преобразования данных

1.3. Постановка задачи построения восстанавливающих процедур с использованием Р/Ы-методов

1.4. Выводы и результаты

ГЛАВА 2. ФОРМИРОВАНИЕ ПРИЗНАКОВ НА ИЗОБРАЖЕНИИ

2.1. Эффективно вычисляемые семейства признаков, используемые в РЛ1-методах

2.1.1. Локальные обобщенные моменты

2.1.2. Рекурсивно формируемые локальные обобщенные моменты

2.1.3. Моментные инварианты

2.2. Система признаков, описывающих форму'изображения

2.2.1. Обеспечение инвариантности к повороту для системы признаков, описывающих форму изображения

2.2.2. Нормализация признаков, описывающих форму, к линейному преобразованию значений яркости изображения в окне

Выводы и результаты

ГЛАВА 3. БЫСТРОЕ РЕКУРСИВНОЕ ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ ПРИЗНАКОВ НА ОСНОВЕ РЕКУРСИВНЫХ ФИЛЬТРОВ С КОНЕЧНОЙ

ИМПУЛЬСНОЙ ХАРАКТЕРИСТИКОЙ

3.1. Общие сведения из теории линейных рекуррентных соотношений

3.2. Расчет одномерных КИХ-фильтров

3.2.1. Вычисление одномерной свертки с конечной импульсной характеристикой, удовлетворяющей ЛРС

3.2.2. Нахождение оптимальных коэффициентов ЛРС, приближающего заданную конечную импульсную характеристику

3.2.3. Методы улучшения устойчивости алгоритма нахождения оптимальных коэффициентов ЛРС 50 3.2.4. Вычисление одномерных сверток с рекуррентными последовательностями специального вида

3.3. Расчет рекурсивных двумерных КИХ-фильтров

3.3.1. Вычисление двумерной свертки с разделимой рекуррентной последовательностью

3.3.2. Аппроксимация неразделимой импульсной характеристики разделимыми импульсными характеристиками общего вида

3.3.3. Аппроксимация двумерной неразделимой ИХ произведением разделимых ИХ, удовлетворяющих ЛРС

3.3.4. Алгоритм аппроксимации неразделимой ИХ семейством разделимых ИХ, удовлетворяющих ЛРС

3.4. Экспериментальные исследования методов рекурсивного вычисления одномерных сверток 61 Выводы и результаты

ГЛАВА 4. ПОСТРОЕНИЕ КЛАССИФИКАТОРОВ И ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ ВОССТАНОВЛЕНИЯ

ИЗОБРАЖЕНИЙ

4.1. Линейный классификатор

4.2. Классификатор в виде нейронной сети

4.3. Древовидные классификаторы

4.3.1. Древовидный классификатор с кусочно-постоянной аппроксимацией

4.3.2. Древовидный классификатор с кусочно-линейной аппроксимацией

4.4. Построение древовидных классификаторов

4.4.1. Параметры построения древовидных классификаторов

4.4.2. Способы разбиения признакового пространства

4.4.3. Методы повышения устойчивости вычислительного алгоритма кусочно-линейной аппроксимации

4.5. Соотнесение сложности решающей функции с объемом обучающей выборки

4.6. Параметрическая оптимизация семейства признаков

4.6.1. Подбор оптимальных параметров значений признаков

4.6.2. Определение оптимального размера окна обработки при вычислении признаков

4.7. Описание информационной технологии построения восстанавливающих процедур на основе Р/Я-методов

4.8. Экспериментальные исследования информационной технологии восстановления изображений

4.8.1. Эксперименты по определению достаточного объема выборки

4.8.2. Общее описание экспериментов по оценке эффективности информационной технологии восстановления и фильтрации изображений

4.8.3. Исследование эффективности фильтрации изображений

4.8.4. Исследование эффективности восстановления изображений

4.8.5. Экспериментальные исследования нахождения оптимального параметра двумерного гауссовского фильтра

4.8.6. Экспериментальное сравнение различных видов классификаторов

4.9. Выводы и результаты 106 ЗАКЛЮЧЕНИЕ 107 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Введение диссертации (часть автореферата) на тему «Информационная технология восстановления изображений, основанная на принципах распознавания образов»

Диссертация посвящена разработке информационной технологии восстановления и фильтрации изображений, базирующейся на принципах теории распознавания образов.

Актуальность темы. Восстановление и фильтрация изображений являются обязательным этапом любых информационных, технологий: обработки двумерных сигналов. Традиционный путь решения этих задач [1,2,4,9,23,35] включает в себя подбор или полуэвристический синтез большого числа обрабатывающих процедур, что объективно обусловлено разнообразием и сложностью математических моделей формирования оптических сигналов, плохой формализуемостью решаемых задач, критериев качества обработки и т.д. Вопросам разработки методов восстановления посвящено большое количество работ отечественных (Д.С.Лебедев, Л.П.Ярославский, Г.И.Василенко, В:А.Сойфер, А.А.Спектор, Ю.П.Пытьев и др.) и зарубежных ученых (У.Прэтт, Р.Бейтс,. Р.Мерсеро, и др.). Основной используемый в этих работах подход состоит в выборе моделей рассматриваемых входных сигналов, искажающей системы и шумов, оценивании их параметров на основе исходной информации и построении восстанавливающей процедуры. Широко известен \ винеровский фильтр, являющийся г наилучшим в классе линейных восстанавливающих систем по критерию минимума среднеквадратичной ошибки восстановления [2,20].

Однако традиционный путь решения задачи восстановления обладает рядом существенных недостатков;

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

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

В третьих, классический путь решения задачи? восстановления изображений; подразумевает идентификацию искажающей системы и построение «обратной к ней», что не всегда удается сделать с учетом принятых ограничений на скорость и качество обработки. Вместо этого разумнее было бы подбирать параметры именно восстанавливающей системы.

Дополнительным ограничением на выбор конкретных алгоритмов-восстановления является жесткие требования к вычислительной эффективности.

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

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

Задачи диссертационной работы. Для достижения указанной цели решаются следующие задачи:

1. Разработка общей схемы преобразования данных для применения метода локальной "обработки через распознавание" изображений к задачам восстановления и фильтрации.

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

3. Синтез и исследование конечных импульсных характеристик (КИХ), обеспечивающих рекурсивное вычисление свертки для формирования локальных признаков изображения, и разработка соответствующих алгоритмов рекурсивного формирования признаков.

4. Разработка алгоритмов обучения классификаторов, осуществляющих преобразование признаков в выходное (восстановленное) изображение, выработка критериев остановки процесса обучения.

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

6. Экспериментальное исследование эффективности общей информационной технологии восстановления изображений, а также ее составных частей - методов построения и быстрого вычисления локальных признаков, алгоритмов обучения классификаторов.

Перечисленные задачи определяют структуру работы и содержание отдельных глав.

Краткое содержание диссертации; Диссертация состоит из введения, четырех глав, заключения, списка литературы, и приложения; Основной текст диссертационной работы изложен на 113 страницах машинописного текста, содержит 25 рисунков; 5 таблиц, список использованных источников из 53 наименований. /

Заключение диссертации по теме «Теоретические основы информатики», Чернов, Андрей Владимирович

4.9. Выводы и результаты/

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

Разработаны следующие методы и алгоритмы, используемые при построении древовидных классификаторов:

1) способы разбиения признакового пространства (пункт 4.4.2);

2) правила остановки процесса обучения классификатора (усложнение решающего правила) на основе методов минимизации среднего риска (параграф 4.5);

3) алгоритмы параметрической оптимизации семейства признаков (параграф 4.6).

На основе разработанных методов (вместе с методами формирования признаков и их быстрого вычисления, предложенными в; предыдущих главах) построена информационная технология восстановления изображений.

Приведены экспериментальные исследования эффективности предложенных методов. Из приведенных экспериментальных данных можно сделать общий вывод о существенно более высокой эффективности предлагаемых методов по сравнению с известным фильтром Винера.

Заключение

В диссертационной работе разработана общая схема и информационная технология синтеза и применения восстанавливающих процедур с использованием метода "обработки через распознавание" (P/R-метода), в рамках которой решены следующие задачи.

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

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

3. Разработаны способы разбиения признакового пространства и правила остановки процесса обучения древовидных классификаторов,

4. Разработаны алгоритмы параметрической оптимизации семейства признаков в P/R методах.

5. Выполнено экспериментальное сравнение эффективности предложенных методов, показавшее преимущества использования предложенной технологии как по качеству восстановления, так и по скорости обработки.

Список литературы диссертационного исследования кандидат технических наук Чернов, Андрей Владимирович, 2004 год

1. Анисимов Б.В., Курганов В.Д. Злобнн В.К. Распознавание и цифровая обработка изображений;-М.: Высшая школа, 1983.

2. Василенко Г.И., Тараторин A.M. Восстановление изображений. М.: Радио и связь, 1986.

3. Алгоритмы и программы восстановления зависимостей /Под. ред. Вапника В. Н.-Mi: Наука, 1984.

4. Виттих В.А., Сергеев В.В. Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований. М.: Наука, 1982.

5. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблемам распознавания // Журнал вычислительной математики и математической физики, т.40, №1, 2000, стр. 166-176

6. Гельфонд; А.О. Исчисление конечных разностей /2-е изд.,доп.- М.:Гос.изд-во физ.-мат.лит-ры, 1959.

7. Глумов Н.И. Построение и применение моментных инвариантов для.обработки изображений//Компьютерная оптика, Выпуск 14-15, 1995, Часть 1, стр. 46-54.

8. Глумов Н.И., Мясников В.В., Сергеев? В.В. Применение полиномиальных; базисов для обработки изображений в скользящем окне // Компьютерная оптика, Выпуск 14-15, 1995, Часть 1, стр. 55-68.

9. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. М.: Мир, 1998.

10. Демиденко Е.З. Линейная и нелинейная регрессии. М.: Финансы и статистика, 1991;

11. П.Дорофенюк A.A.,. Бауман Е.В., Корнилов Г.В. Оптимальные методы классификационного анализа в задаче кусочно-линейной аппроксимации // Труды международной конференции "Интеллектуализация обработки информации", Алушта, 2004 г., стр. 70-74.

12. Журавлев Ю.И.: Корректные алгебры над множеством некорректных эвристических алгоритмов // Кибернетика, 1977, № 4. стр. 14-21; 1977, № 6, стр. 21-27; 1978, № 2, стр. 35-43.

13. Каппелини В., Константинидис А.Дж., Эмилиани П. Цифровые фильтры и их применение. М.: Энергоатомиздат, 1983;

14. Лбов P.C., Старцева Н.Г. Логические решающие функции и вопросы статистической устойчивости решений. Новосибирск: Изд-во Ин-та математики, 1999.

15. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. -М.: Наука, 198618;'Мантра С. Моментные инварианты // ТИИЭР, 1979, N4, стр. 297-299.

16. Методы, критерии и алгоритмы, используемые при преобразовании, выделении и выборе признаков в анализе данных: Сборник статей АН ЛитССР. Вильнюс: Институт математики и кибернетики, 1988.,

17. Методы компьютерной обработки изображений (под ред. В.А. Сойфера). М.: Физматлит, 2001.

18. Оппенгейм A.B., Шафер Р.В; Цифровая обработка сигналов. М;: Мир, 1979.

19. Прэтт У. Цифровая обработка изображений. М.: Мир, т. 1-2, 1982 г.

20. Тихонов А.Н;, Арсенин В.Я.: Методы решения некорректных задач. М.: Наука, 1974.

21. Уоссермен Ф. Нейрокомпьютерная техника. М.: Мир, 1992.

22. Фукунага К. Введение в статистическую теорию распознавания образов: Пер. с англ. М;: Наука, 1979.

23. Фурсов В .А. Идентификация моделей систем формирования изображений по малому числу наблюдений. — Самара: СГАУ, 1998.

24. Холл F., Комбинаторика. М.: Мир, 1970.

25. Чернов А.В. Быстрое рекурсивное вычисление одномерных и двумерных конечных сверток// Компьютерная оптика, 2003, Вып. 25, стр. 190-197.

26. Ярославский Л.П. Введение в цифровую обработку изображений. М.: Советское радио, 1979.

27. Chernov A.V.: Constructing Classifiers for Image Filtering Algorithms Based on Pattern Recognition Theory //Pattern Recognition and Image Analysis. 2001; - Vol ll,No.l - pp. 144-146.

28. Chernov A.V., Kopenkov V. N.: Parametric Optimization of Families of Features in Image Reconstruction Methods Based on the Principles of Pattern Recognition Theory //Pattern Recognition and Image Analysis. 2003 - Vol. 13 No.4. - pp. 8081.

29. Chernov A.V., Myasnikov V.V., Sergeyev V.V.: Fast Method for Local Image Processing and Analysis // Pattern Recognition and Image Analysis, Vol.9, No.4,1999, pp. 572-577

30. Chernov A.V., Myasnikov V.V., Sergeyev V.V.: Fast method of the local processing and analysis of images //Proceedings of the 5-th Open German-Russian Workshop on Pattern Recognition and Image Understanding, 21-25 сентября 1998 г., Херршинг, Германия.

31. Chernov A.V., Sergeev V.V. Image Reconstruction Methods Based on the Principles of Pattern Recognition Theory//Pattern Recognition and Image Analysis. 1997. -Vol. 6. No.4 - pp. 474-479.

32. Evans A.G., R Fischl Optimal Laest Square Time Domain Synthesis of Recursive Digital Filters // IEEE Trans. AudioElectroacoust., Vol AU-23, 1973, pp. 63-65

33. Flusser J. On the independence of rotation moment invariants //Pattern Recognition 33 (2002) pp. 1405-1410;

34. Flusser J. On the inverse problem of rotation moment invariants //Pattern Recognition 35 (2002) pp. 3015 3017.

35. Glumov, N. I., Kolomiec, E. I., Sergeyev, V. V. Detection of the Objects on the Image Using a Sliding Windows Mode. I I Optic and Laser Technology, No.4, 1995, pp. 241-249.

36. Glumov, N. I., Myasnikov, V. V., Sergeyev, V. V. Application of Polynomial Bases for Image Processing Using Sliding Window//Proc. Vol. 2363, 1995, pp. 4049.

37. Glumov, N. I., Myasnikov, V. V., Sergeyev, V. V. Polynomial; Bases for Image Processing in a Sliding Window// Pattern Recognition and Image Analysis, No.4, 1994, pp. 408-413.

38. Hinamoto T. Design of 2D Separable Denominator Recursive Digital Filter// IEEE Trans, Circuit Systems Vol. CAS-31, November; 1984 , pp. 1925-1934.

39. Ни M. Visual : pattern recognition by moment invariants // IRE Trans Information Theory. 1962. vol.TT-8 -pp.179-187.

40. Li B.C. andShen J. Fast computation of moment invariants II Pattern Recognition, Yol.24, No. 8,1991, pp. 807-813.

41. Sankar K. Pal, Sushmita Mitra: Multilayer Perceptron, Fuz2y Sets and Classification

42. EE Transactions on Neural Networks, Vol.3, N5, 1992, pp. 683-696.

43. Show A. Design of Denominator Separable 2-D IIR Filters // Signal Processing 421995), pp. 191-206.

44. Bernard Widrow, Michael A. Lehr : 30 Years of Adaptive NeuralNetworks: Perceptron, Madaline, and Backpropagation //Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press, 1992, pp. 327-354.

45. Paul J. Werbos: Backpropagation Through Time: What It Does and How to Do It //Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press, 1992, pp. 309-319.