автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Принципы дельта-сигма-модуляции в цифровых устройствах предобработки изображений

) V b

\ Q АПР W95

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИМ УНИВЕРСИТЕТ)

На гграгаг рукописи

МИЛЫАН Григорий Юрьевич

ПРИНЦИПЫ ДЕЛЬТА-СИГМ-МОДУЛЯЦИИ В ЦИФРОВЫХ УСТРОЙСТВАХ ПРЕДОБРАБОТКИ ИЗОБРАЖЕНИИ

Специальность 05.13.05 - Элементы и устройства

вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 1995

Работа выполнена з Московском Государственном институте радиотехники, электроника и автоматики (техническом университете)

Научный руководитель: кандидат физико-математических наук,

профессор Папуловский В.Ф.

Официальные оппоненты: доктор технических наук, профессор

Филаретов Г.Ф.,

кандидат физико-математических наук, Колтовой Николай Алексеевич.

Ведущее предприятие: Московский Государственный университет путей сообщения (ШИТ).

Защита диссертации состоится "_" _ 1995 г.

з _ часов _ минут на заседании диссертационного совета

ДС63.54.01 в Московском Государственном институте радиотехники, электроники и автоматики (техническом университете) по адресу: 117454, Москва, пр-т Вернадского 78.

С диссертацией можно ознакомиться в библиотеке МИРЗА. Автореферат разослан " 2 / " 1995 г.

Ученый секретарь диссертационного совета ДС63.54.01,

кандидат технических наук / Хохлов Г.И.

у

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

Методика исследований. Для решения поставленных задач использованы методы теории вероягаостей и математической статистики, теории информации и дискретной обработки сигналов, элементы статистической теории распознавания образов, математические методы компьютерной графики, принципы проектирования узлов ЭВМ.

Научная новизна. В результате проведенных исследований

- определен критерий адекватности визуального восприятия исходного и бинаризованного изображений, которому должна соответствовать оптимальная процедура бинаризации:

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

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

- на основе метода бинаризации изображений Флойда-Стейн-берга разработана обобщенная процедура дельта-сигма-модуляции, обеспечивающая оптимальную бинаризацию изображений с точки зрения визуального восприятия:

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

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

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

- о -

лизации этого метода.

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на хы и xl.ii научно-технических конференциях МИРЗА (Москва, 1992 г. и 1993 г.), на 2-ом съезде Российской Ассоциации Нейроинформатики (Москва, 1992 г.), на Международной выставке-семинаре "Компьютерная геометрия и графика в образовании" (Нижний Новгород, 1993 г.), на семинаре "Еейроинформатика и нейрокомпьютеры" (Красноярск, 1993г.).

Реализация работы. Результаты исследований были внедрены в ТОО "ВВДАР" при создании комплексов медицинской диагностики для обеспечения высококачественной визуализации томографических и УЗ изображений,, а также использованы предприятием "СТИПЛЕР-СОФТ" при создании системы компьютерной факсмодемной связи для передачи изображений с последующей визуализацией на различных устройствах. Программно-аппаратная реализация метода распознавания полутоновых изображений с помощью оптимальных растров была внедрена на предприятии "СТЖШЕР-СОФТ" при создании автоматизированной системы ввода в ЭВМ большеформатннх изображений.

Публикации. По теме диссертации опубликовано 7 печатных

работ.

Объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (49 наименований) и приложений. Объем диссертации составляет 164 страницы, в том числе 116 страниц основного машинописного текста и 30 страниц рисунков.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность выбранной темы, сфор-

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

В первой главе представлен обзор и анализ методов и средств КЕантоЕания, кодирования и визуализации изображений.

Исследования в области преобразований полутоновых изображений в целях уменьшения количества используемых уровней градаций первоначально развивались в рамках создания методов оптимального поэлементного квантования изображений. Этим вопросом занимались У. Прэтт, А.К. Джайн, С.П. Ллойд, Дне. Макс, В.К. Альгази, П.Ф. Пантер, В. Дайт, Б. Смит, Г.М. Рой и др.

Квантованием называют отображение отсчетов сигналов (изображений) , имевших непрерывное множество значений, в отсчеты с дискретными значениями.

Процесс квантования отображает непрерывную переменную х в дискретную переменную х, принадлежащую множеству действительных чисел {г1,..., где г. - уровень градации яркости (контраста) преобразованного изображения (уровень квантования), I - количество таких уровней, г4 < х < г^. При поэлементном квантовании определяют набор возрастающих пороговых (переходных) уровней Сс1 , 3 = + 1), и если X е (С^, с!.^], то X = 1\, ] е [1, Ы,

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

С.П. Ллойд и Дж.Макс предложили в качестве критерия оптимизации использовать минимум среднеквадратичной ошибки квантования при фиксированном числе уровней квантования. Минимизация этой ошибки дает переходные уровни, лежащие посередине между уровнями квантования, и уровни квантования, лежащие в центрах масс плотностей вероятностей между переходными интервалами. В частности, если квантуемая величина распределена равномерно, то Есе переходные уровни и уровни квантования оказываются равноотстоящими.

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

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

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

При квантовании изображений, предназначенных для визуализации, следует учитывать, что структура получаемой видеоинформации должна быть совместима с процессами обработки этой информации зрительным аппаратом наблюдателя. Этот аспект рассматриваемой проблемы нашел отражение в работах Л.П. Ярославского, H.H. Кра-сильникова, Н.З. Завалишина, И.Б. Мучника. Среди зарубежных исследователей здесь можно указать В.М. Гудолла, Т.Г. Стокхэма, Х.С. Хуанга, 0. Третьяка, У. Шрейбера, Д.Да. Гранрата, Т. Павли-диса, Д. Боджерса, Д. Коннора, ?. Брейнарда, Дж. Лимба. В их исследованиях отмечается, что уменьшение уровней квантования приво-

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

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

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

Методы Робертса, упорядоченного возмущения и распространения ошибок (Флойда-Стейнберга), по существу, основываются на добавлении к изображению перед квантованием псевдослучайного шума, значения которого либо не зависят ни от значений яркости элементов (пикселов) исходного изображения, к которым они добавляются, ни от их расположения (метод Робертса), либо зависят только от расположения пикселов (метод упорядоченного возмущения), либо зависят как от расположения пикселов, так и от их значений (метод Флойда-Стейнберга). Б последнем случае обеспечиваются наилучшие

результаты при проведении квантования изображений на два уровня -при бинаризации. Это преобразование определяется следующими выражениями

е. .=

Г1, при X. .;> Т

^ . (1) .0, ПРИ Х;_.< Т

X. .= х..+ э. ., (2)

Д. .= X. - е. ., (3)

„3. .= Ь Д. , .-I- Ь„Д. . + Ь Д. . , (4)

где х и е._,- интенсивности исходного и бинаризованного изображений в точке с координатами (1,3), х. е СО, 1],

е е {0, 1>: 11 1 Т - порог кгантования, Т

э - взвешенная сумма ошибок квантования в точках с координатами (1-1,3), (1-1,3-1), (1,3-1), соседних с данной:

г11, - коэффициенты распространения ошибки квантования

вправо, ениз и по диагонали (вниз и вправо) сот I т

ответственно, . • Ь3="Э" ■

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

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

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

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

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

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

Если х.., х. .е £0,1.....и) - значение интенсивности отсче-

ч ч

та исходного полутонового изображения в точке с координатами (1, 3), а ш - количество градаций яркости, то процедура бинаризации этого изображения должна соответствовать выражению

Г1, при х' .+ (Т - г. .) * Т, е. .= | (5)

м 1о, при Г .+ (Т - Ги) < Т.

Эта формула позволяет интерпритировать вычисление значений отсчетов бинаризованного изображения е._., е^е СО, 1} как проведение квантования нормированных значений отсчетов исходного изображения

х' , х! .€ [0,1], х'.= х. /т с предварительно добавленным шумом,

и ч ч ч

заданном в виде (Т - г,.), при пороге квантования Т, причем слу-

чайная величина г.. должна быть равномерно распределена на отрезке СО, 1], причем значения величины ги в различных точках (1, 3) не являются независимыми, а имеют определенную статистическую структуру.

Процедура дельта-сигма-модуляции последовательности отсчетов (вещественных чисел) уп, где п = 1,2.....Я, упе [-1, 1], для

каждого отсчета уп определяет кодовое значение дпе {-1, 1} по следующему правилу:

п-1

дп= (У,- (6)

¡. = 1

где значения функции () определяются выражением

Г1, при г £ О, з®1'(г)={ (7)

1-1, при г < 0.

Тс "а значения отсчетов последовательности е , ее СО, 1), явля-

п п

ющейся результатом кодирования в сответствии с ДСМ исходной последовательности отсчетов х^, х^е (0, 1], будут определяться выражениями:

е = Гх' + з' 1, (8)

п п п-1-1 ' х '

з'= £х' + з' >, (9)

П ^ п т>— .

где М - целая часть, а -(XI- - дробная часть некоторого числа ц. Исследуя статистические свойства дельта-сигма-модулированных последовательностей, удалось установить, что случайная величина

н

ем=4ГЕ6"' (10)

П = 1

где е , п = 1,2,...,Л определяются выражениямим (3) и (9), имеет математическое ожидание

я

(и)

прячем дисперсия этой случайной величины при всех N > 1 минимальна в классе случайных двоичных кодовых последовательностей gn, п = 1,—,N, таких, что

M(gn) = х;. (12)

Следовательно, если при декодировании на ¡í-ом шаге используется величина им: . •

Н-1

u-=TrE<W <13>

V =0

при М > К, являющаяся оценкой среднего арифметического

М-1

ttZ1^« (14)

I =0

то эта оценка оказывается эффективной в классе оценок, вычисляемых по формуле

м-1

(15)

i =о

где gn - случайная двоичная последовательность, удовлетворяющая условию (12), в том случае, когда значения еп вычисляются в соответствии с выражениями (8) и (9). При этом условие (11) эквивалентно условию несмещенности оценок yu. " Кроме того, удалось установить, что при увеличении объема выборки выборочные средние кодовых значений приближаются к средним значениям соответствующих отсчетов исходной последовательности, т.е.

"^Z2" " е"

. Я = 1,2,... . (16)

Неравенство (16) означает, что при ДСМ обеспечивается-состоятельность выборочных оценок средних кодовых значений, причем

это свойство также имеет место для любой последовательности кодируемых отсчетов.

Из выражений (3) и (9) следует, что

Г1, X' -I- 3' 1, = < " . П_1 (17)

" 1.0, X' + 3' < 1,

4 п п-1

причем при рассмотрении статистических свойств дельта-сигма-моду-лированных последовательностей удалось установить, что значения отсчетов величин распределены равномерно на отрезке СО, 1С. Следовательно, это выражение является частным случаем выражения (5).

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

Процедуру бинаризации нормированных отсчетов последовательностей в соответствии с .дельта-сигма-модуляцией, определяемую выражениями (9) и (17), можно представить как алгоритм, основанный на распространении ошибок квантования нормированных элементов исходной последовательности. Более того, удалось установить, что применительно к бинаризации одномерных последовательностей ДСМ и процедура Флойда-Стейнберга тождественны, и применительно к задаче бинаризации изображений метод Флойда-Стейнберга отвечает требованию совпадения средних значений по- различным соответствующим областям исходного и бинаризованного изображений. Однако при этом требование достижения минимума дисперсии суммы элементов локальных областей бинаризованного изображения не реализуется. Это требование обуславливает наличие указанной выше определенной статистической зависимости между значениями любых двух отсчетов бинаризованного изображения. При использовании метода Флойда-Стейнберга результат бинаризации каждого отсчета изображения с координатами (и, т) зависит только от ошибок бинаризации в тех точках, которые расположены выше и левее данной, т.е. с такими координатами (I, .1). что 1 5 и при ^ 1 т, I * и при .1 * т.

е

Это приводит к появлению на бинаризованных по методу • Флойда-Стейнберга изображениях помеховых структур, снижающих качество визуального восприятия.

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

* <18>

в, _ ри^и^+ми. при 3-ЯС-1.

где к = 1,2,..., , если .Г - четное, либо к = 1,2.....Лг+ 1,

если J - нечетное: Д^.е [О, 1С- нормированная ошибка бинаризации в точке с координатами (I, 3), а усредненная нормированная ошибка бинаризации по ближайшим точкам соседним с данной, с весовыми коэффициентами йэ, соответствующими коэффициентам распространения ошибок Флойда-Стейнберга.

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

Если интенсивности точек исходного полутонового изображения с координатами (1, I = 1,2,3 = 1,2,...,^ характеризуются значениями х^, причем х^е {а,1,.,.,т}, т * 1 и, следовательно, исходное изображение имеет количество градаций т + 1, а надо определить значения интенсивностей точек преобразованного изображения г^е (0,1,...,!>, 1 < ш, 12 1 так, чтобы исходное и преобразованное изображения были визуально максимально близки, то такая задача соответствует равномерному квантованию отсчетов исходного изображения на 1+1 градацию с шагом с учетом визуального восприятия. Решение этой проблемы описывается выражениями

г х. 1 + з.. 1

г I. .1 + 3. 1 -Ач= т 1 " д = К1 * 3чН т-

где (ц.)яюй % - остаток от деления числа ц. на и

_ рА-и+'^Ч-ч-!* ЦАа-1' ^ * = 2к"1'

ГЬ Д. Д. . + Ь Д. . ,

э = ^ 1 1-11 2 1-11-1 3 Ч"1

1' Ц1 Д. + Ь д . + 11 д

г 1-И1-1 эс ¡-I'

при 3 = 2к,

(22)

причем з^е СО, т[, и Д..е [0, тС.

Если значения пикселов преобразованного 'изображения с координатами (1, 3) должны определяться значениями г^., где г^.е {ао, а1,..., ак>, причем ао< а±,... ,ак1 < ак, ао- соответствует минимальной интенсивности исходного изображения, а ак- максимальной, и, в общем случае, значение выражения ак- ак_1 не является константой при 0 < к 5 К, то такая задача соответствует проблеме преобразования изображений при неравномерной шкале квантования. Обозначив

х. .

X' =—1 ч т '

г;.

ч а„

<4= "57' к =

•К,

то х'.6 [0, П, е СО, 11, а'й х' .й а'. Если X'.< а/ . то

1 Ч о к к VJ к*1

равно либо с^, либо а,<+1, причем

х'.- а,'

г; .= а/ + Га/ - а,']

-а/ к*1 к

• + з'. ч

А? .= -

х? .- а/

I 4 к

+ 3' .

^ 4

I к

ГЬ,Д! , .+ йЛ' 4 . .+ Ъ Д' . , ,

2 1-1 л3 14-1'

4 Ь д.' .+ ь д: + ь Д' ,

при 3 = Щ,

(23)

(24)

(25)

■+ 1.

где о = 1, 2,..., 4-, если J - четное, либо д = 1,2,... если J - нечетное.

В диссертации установлено, что М(з^) - математическое, ожидадание величины я' совпадает с Разработана методика оп-

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

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

Выражения, определяющие процедуры преобразований изображений на основе обобщенной дельта-сигма-модуляции, таких как бинаризация и квантование при равномерной и неравномерной шкале градаций соответственно, очень схожи между собой. Для определения кодированного значения интенсивности пиксела преобразованного изображения с координатами(1, 3) необходимо рассчитать значение величины э.. по значениям ошибок квантования трех соседних с данной точек b■i_íi_í и Д..^, если 3 - номер данной строки изображения - четный, либо д^и Д^.^ при нечетном номере строки. После этого определяется ги)- новое значение интенсивности в данной точке, а также ошибка квантования д , необходимая для дальнейших вычислений. Общая структурная схема -вычислительного устройства преобразования изображений на основе обобщенной дельта-сигма-модуляции представлена на рис. 1.

Поскольку для вычислений преобразованных величин интенсивности 3-ой строки необходимы значения ошибок квантования в предыдущей строке с номером 3 - 1, а в результе завершения преобразования всёй 3~ой строки становятся известными ошибки квантования в этой строке, необходимые для проведения вычислений над элементами следующей строки, то для-обеспечения одновременного считывания значений ошибок квантования точек строки с номером 3-1 и записи рассчитываемых ошибок квантования пикселов 3-ой строки предусмотрено наличие двух оперативных запоминающих устройств - ОЗУ До и ОЗУ Дх. Для обеспечения подачи записываемого значения д на вход одного из запоминающих устройств ОЗУ До или ОЗУ А1, в зависимости от того, четный или нечетный номер данной строки, а также для выдачи считываемого значения д 4 с выхода другого из этих двух запоминающих устройств предназначены соответственно ДЕМУЛЬТИЖЕК-СОР и МУЛЬТИПЛЕКСОР Д.. .

Поскольку считанное значение Д. . при обработке следующе-

Рис. 1. Общая структурная схема устройства преобразований изображений на основе обобщенной дельта-сигма-модуляции.

го пиксела данной З-ой строки, у которого номер 1 на 1 больше при 3 - четном, либо на 1 меньше при 3 - нечетном, будет участвовать в вычислениях, соответственно, либо в качестве Д^^» либо как то одновременно с подачей на вход устройства,

обозначенного на рис. 1 как ВЫЧИСЛИТЕЛЬ з , поступает в РЕГИСТР А^^ .^(Д^^.^), после которого, спустя такт, это значение будет использовано уже в соответствующем_ качестве. Аналогично, вычисленное значение д при обработке- следующего пиксела данной строки будет участвовать в вычислениях либо как либо как

в зависимости от того,четный или нет номер данной строки Поэтому это значение одновременно с записью в соответствующее ОЗУ постулат в РЕГИСТР Д (Д^.).

Подобный порядок вычислений характерен для всех пикселов, за исключением имеющих номера 1=0 при 3 - четном (1= 1-1 при 3 -нечетном). В этом случае значения Д. ■ - Д и Д. . = Д

. ' ^ , 1-11 -и 1-11-1 -и-1

[д._ =ДИ и Д^-цА^-!] равны половине интервала квантования. Эта константа перед началом вычислений загружается в РЕГИСТР д (Д ), откуда при обработке пикселов с номерами 1=0 (1=1-1) подается на зход ВЫЧИСЛИТЕЛЯ з.. в качестве д. . и Д. Д. . и Д. . . Поступление значений Д. и Д. .

и Д1,1]_11 на вход ВЫЧИСЛИТЕЛЯ з. . при 1*0 (1*1-1) из РЕГИСТРА Д."1" (Д. .) и РЕГИСТРА Д. . (Д. ), а при 1=0 (1=

V-! 1 1+11 1-11-1 |-*11-1 ' г

=1-1) - из РЕГИСТРА Д_± (Д1.) обеспечивают, соответственно, МУЛЬТИПЛЕКСОР Д. . Гд. .1 и МУЛЬТИПЛЕКСОР Д. . (д. . 1.

Следует отметить, что при обработке пикселов строки с номером 3=0, все значения Д^.^» считываемые из ОЗУ Д1, должны быть также равны половине интервала квантования. Поэтому перед началом вычислений во все ячейки ОЗУ Д4 необходимо записать эту константу (либо необходимо предусмотреть еще один мультиплексор, который бы обеспечивал при 3*0 подачу этого значения от ОЗУ Д0 или от ОЗУ Д4, а при 3=0 - от РЕГИСТРА Д_1.(Д..)),

Исходные данные в виде значений х^ поступают из ОЗУ хс. на один из входов ВЫЧИСЛИТЕЛЯ Д. и на другой вход которого поступают значения, полученные с помощью ВЫЧИСЛИТЕЛЯ е. , а вычисленные значения пикселов - з. . записываются в ОЗУ причем адрес ячейки ОЗУ х , из которого считывается значение х. ., совпадает с адресом ячейки ОЗУ зи, в которое записывается соответствующее значение z.í .

Формирование сигналов управления, необходимых для реализации такого порядка вычислений, а также определение значений адресов запоминающих устройств осуществляется ФОРМИРОВАТЕЛЕМ АДРЕСОВ И ПОТОКОВ ДАННЫХ.

В диссертации подробно рассмотрены вопросы организации ВЫЧИСЛИТЕЛЯ и ФОРМИРОВАТЕЛЯ АДРЕСОВ И ПОТОКОВ ДАННЫХ, аппаратной реализации процедур бинаризациий, сокращения количества градаций от 2м до 21" при равномерной шкале квантования, а также при неравномерной шкале квантования. Приведены результаты моделирования рассматриваемых устройств для визуализации и печати различных изображений.

Четвертая глава диссертации посвящена применению устройств на основе обобщенной дельта-сигма-модуляции для распознавания изображений.

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

(26)

где ??к- критерий рассогласования к-ого образа с эталоном: Н и М - длина и ширина изображений соответственно: х°. и хк. - интенсивности эталонного изобгажения и й-го об-

ч ч

раза в точке с координатами (1, 3) соответственно.

Если значения интенсивностей эталонного и опознаваемого изображений - и х^ представлены в виде положительных ^разрядных даоичных чисел, то значение выражения х*.| также является ^-разрядным деоичным числом. Следовательно, для изображений, содержащих по п точек, значение будет (1г + 1о§гп)-разрядным двоичным числом. Обычно подлежащие распознаванию изображения имеют значительные размеры и содеркат такое количество точек, что превышает значения 1а. Поэтому выполнение п операций сложения для чисел с разрядностью 1г + 1о§,п, а именно столько необхо-

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

В диссертации предлагается следующая процедура распознавания изображений. Для эталонного изображения предварительно строится определенная карта пороговых значений - эталонный растр. Затем эталонное изображение растрируется эталонным растром: пикселы, в которых значение интенсивности превосходит величину порога в соответствующей точке растра, приобретают значение равное 1, а остальные - равное 0. Полученное двухуровневое изображение будем называть бинаризованным эталоном. Подлежащие распознаванию изображения растрируются эталонным растром, и для каждого реультата такого растрирования вычисляется значение меры расхождения с бинаризованным этзлоном, определяемое в соответствии с их множественной корреляцией. Наиболее близким к эталонному считается то опознаваемое изображение, которое обеспечивает минимальное значение меры расхождения. Очевидно, что при таком методе распознавания должен обеспечиваться минимум меры расхождения, когда в качестве опознаваемого изображения предъявляется эталонное.

Если ги- значение эталонного растра в точке (1, 3), х^е {0,1,...,т), то е* - значение результата растрирования к-ого образа (считая, что нулевым является само эталонное изображение) будет определяться следующим выражением:

ек .=

IJ

(1, при хк .г г. .,

(27)

.0, при х*х ги.

Вычисление значения 0к- меры расхождения между результатами растрирования опознаваемого изображения и бинаризованного эталона будем проводить путем подсчета числа точек, в которых интенсивности бинаризованного эталона и растрированного изображения не совпадают, т.е.

«.■114

1=11=1

где

Г'

11 1о.

1, при е° ек. при е°.= ек..

(28)

(29)

Если значения растра определяются в соответствии с обобщенной дельта-сигма-модуляцией, т.е.

г. .= ш - э. .= т(1 - з'.), (30)

где з. - усредненная ошибка квантования трех соседних с данной точек (см. (19)-(20)), то построение бинаризованного эталона сводится к проведению бинаризации эталонного изображения в соответствии с алгоритмом обобщенной дельта-сигма-модуляции, а значение - меры расхоздения результатов растрирования к-ого опознаваемого изображения и бинаризованного эталона, умноженное на т, -является несмещенной оценкой величины Поскольку вычисление значений з*. не сложнее, чем вычисление значений |, а осуществление накапливающего суммирования одноразрядных значений . проще и быстрее, чем значений выражения |х°,- х*.|, то аппаратная реализация метода распознавания изображений с помощью растрирования является более предпочтительной.

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

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

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

ЗАКЛЮЧЕНИЕ

Основные выводы по диссертационной работе состоят в следующем:

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

2. Использование методов поэлементного квантования отсчетов изображений на относительно малое количество градаций яркости (менее чем на 64) не обеспечивает реального высокого качества визуализации из-за возникновения на результирующем изображении ложных контуров.

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

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

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

ных оценок восстановления средних значений исходных отсчетов но дельта-сягма-модулироЕанным последовательностям, а также состоятельность оценки средних значений ДСМ-госледовательностей.

6. В диссертации показано, что методы бинаризации изображений, основанные на распространении ошибок квантования (типа Флойда-Стейнберга), в общем случае можно считать обобщением процедуры бинаризации одномерных последовательностей с помощью ДОМ применительно к изображениям. Но при этом результат бинаризации элемента изображения зависит только от ошибок квантования в тех точках, которые расположены выше и левее данной, что приводит к появлению на бинаризованном изображении помеховых структур, снижающих качество.визуального восприятия.

На основе метода Флойда-Стейнберга разработана процедура бинаризации изображений, при которой результат бинаризации любого элемента изображения зависит от ошибок квантования ео всех точках, бинаризованных до данной.

7. С помощью полученного решения задачи бинаризации изображений разработана процедура равномерного квантования при обеспечении максимального визуального сходства результирующего изображения с оригиналом я аналогичная процедура квантования исходного изображения при неравномерной шкале квантования.

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

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

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

Основные положения диссертации опубликованы в следующих работах:

1. Гусев Д.А., Мильман Г.Ю., Сандлер Е.А. Устройства преобразования градаций сигналов и изображений на основе дельта-сигма-модуляции.// Вопросы кибернетики, устройства и системы. Межвузовский сборник научных трудов. - М., МИРЭА, 1992, с.13-18.'

2. Гусев Д.А., Мильман Г.Ю., Сандлер ЕЛ. Принципы использования оптимальных растров в задачах распознавания образов.// Вопросы кибернетики, устройства и системы. Межвузовский сборник научных трудов. - М., МИРЭА, 1992, с.18-30.

3. Мильман Г.Ю., Сандлер Е.А. Использование нейропарадигм для распознавания объектов на изображениях. //Тезисы докладов рабочего семинара "НеЯроинформатика и нейрокомпьютеры". . - Красноярск, 1993, с.28.

4. Сандлер Е.А., Мильман Г.Ю., Гусев Д.А. Новые методы высококачественной компьютерной печати полутоновых изображений. // Тезисы докладов и сообщений Международной выставки-семинара "Компьютерная геометрия и графика в образовании". - Нижний Новгород, 1993, с.47.

5. Сандлер Е.А., Мильман Г.Ю. Оптимальное квантование изображений.// Вопросы кибернетики, устройства и системы. Межвузовский сборник научных трудов. - М., МИРЭА, 1994, с.37-40.

6. Мильман Г.Ю., Папуловский В.Ф. Аппаратная реализация устройств преобразования градаций сигналов и изображений на основе дельта-сигма-модуляции.// Вопросы кибернетики, устройства и системы. Межвузовский сборник научных трудов. - М., МИРЭА, 1994, с.41-48.

7. Мильман Г.Ю. Применение методов оптимального растрирования для решения задач распознавания изображений.// Вопросы кибернетики, устройства и системы. Межвузовский сборник научных трудов.- М., МИРЭА, 1994, с.49-55.