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

V I 0 ин

1 о АПР 1995

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

На оравах рукописи

ЖЛЬМАН Григорий Юрьевич

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

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

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

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

Москва - 1955

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

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

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

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

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

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

Ведущее предприятие: Московский Государственный универс:

тет путей сообщения (ШИТ).

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

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

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

С диссертацией можно ознакомиться в библиотеке ЖРЭА.

Автореферат разослан " 1995 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

лизании этого метола.

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

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

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

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

работ.

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

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

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

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

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

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

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

Процесс квантования отображает непрерывную переменную х в дискретную переменную х, принадлежащую множеству действительных чисел Crt,..., г^}, где г. - уровень градации яркости (контраста) преобразованного изображения (уровень квантования), L - количество таких уровней, гА < z < rL. При поэлементном квантовании определяют набор возрастающих пороговых (переходных) уровней id., J = 1,,..,L + 1), и если х е (d., dVt ], то х = г , J е CI, L], причем г е (d .d^J. Поскольку отображение квантования необратимо, то в результате возникают искажения, которые пытаются минимизировать. Задача разработки оптимальной процедуры квантования состоит в нахождении оптимальных уровней квантования и пороговых уровней при заданной плотности и некотором критерии оптимизации.

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

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

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

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

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

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

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

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

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

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

е. .=

•<■ и

"1, при X. :г Т .0, при Х.^Х т'

(1)

X..= х..+ з..,

1 з ч ч

А..= X. .- е. .,

Ч Ч Ч

.3. .= ПЛ. , .+ , . + Ь А. . ,

Ч 1 V-!) 2 1-11-1 3 4-1

(2)

(3)

(4)

где и е^- интенсивности исходного и бинаризованного изображений в точке с координатами (1,3). з^-е £0, 13» е ^ {0, 1>:

1

Т - порог квантования, Т =-£:

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

'V Ь-э ~ коэф{ициенгы распространения ошибки квантования вправо, вниз и по диагонали (вниз и вправо) соответственно, Ь2=4" •

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

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

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

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

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

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

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

Г1, при V. .+ (Т - г. .) г Т, еи= Р ч ^ (5)

11 10, при (Т - г. .) < Т.

Эта формула позволяет янтерпритировать вычисление значений отсчетов бинаризованного изображения е.., ее {0, 1> как проведение квантования нормированных значений отсчетов исходного изображения х(., х( е СО.и, х( = х._ /т с предварительно добавленным шумом, заданном в виде (Т - г,.), при пороге квантования Т, причем слу-

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

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

п п

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

п-1

(у,-д.)), (6)

<.=1

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

"1, при 2 > О,

sgn'(s)=

-1, при z < 0.

(7)

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

п п

ющейся результатом кодирования в сотвегствии с ДСМ исходной последовательности отсчетов х^, x'n<s СО, 1], будут определяться выражениями:

еп=[х; + з^], (8)

К' ÍK + (9)

где [р.] - целая часть, a {ji}- - дробная часть некоторого числа (л. Исследуя статистические свойства дельта-сигма-модулированных последовательностей, удалось установить, что случайная величина

N

vil(10)

п = 1

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

же,,) =i¿x;,

(и)

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

М(вп) = г;. (12)

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

V =0

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

М- 1

1=0

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

ы-1

1=о

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

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

< , Н = 1,2..........(16)

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

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

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

е =

1, X' + 3' > 1-,

" . (17)

10, X' + 3' < 1,

г» п-1 *

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

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

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

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

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

э' .=

I л

при Л=2к-1,

при

(20)

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

<ы ¿и

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

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

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

г х. .1 + э. . т

2,Г [ " ш ]- <20)

г X. .1 + 3. П ,

Аи= т { м ш 7 = (V + аиН га-

где (|1)тос2 х ~ остаток от деления числа ц на %, и

ГЬ, Д. Д. .. + ¡11 при 3 = 2к-1,

1 V-! 3 2 1.-1^-1 3 4-1 '

3. -

V 1

(22)

Мч-.' при Л = 2к»

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

г ч ч

Если значения пикселов преобразованного изображения с координатами (1, 3) должны определяться значениями 2.где г. .6 (ао, а1,..., ак>, причем ао< ак, а0- соответствует

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

х. .

X' =—->

4 т '

и а.

а,

х'= —

к О...

» 1с — Оу!»«***!^*

то х' е [0, 1], г! е [0, 1], а'^ х' .й а' Если х'.< а' . то

4 * ' I ] ' о V.) к к к*-1 '

2и равно либо ак, либо ак+1, причем

:'.= а/ + Га' - аЛ( ^ + з'.|,

ч к 1. к,» Л

(23)

Д' -

^ J

х! .- а' а,' - а,'

Л * 1 <

+ 3.

(24)

д. _ Ми-1' при * = аи» (25)

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

если J - нечетное.

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

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

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

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

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

сор и шьтиплексор д. .

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

ДЕШБПШЕКСОР ?

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

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

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

- ^ , 1-и -и 1-11-1 -11-1

1д. =Д и <4,^1 равны половине интервала квантова-

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

, « Ч <--11

Д. Д. . и Д. . . Поступление значений Д. и Д.

[1-11-1 I. 14-11 . 4-11-^ " __I» —1 1 1.-11-1

Д.^ . и Д.^ I на вход ВЫЧИСЛИТЕЛЯ э.. при 1*0 (1*1-1) из РЕГИСТРА Д./. (Д* .) и РЕГИСТРА Д. , . (Д.',.,), а при 1=0 (1= =1-1) - из РЕГИСТРА Д_1 (Дг.) обеспечивают, соответственно, МУЛЬТИПЛЕКСОР Д. 4 . ("д. Г и МУЛЬТИПЛЕКСОР Д.. Гд. . . 1.

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

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

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

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

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

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

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

»-а л

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

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

К N

(26)

1=1

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

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

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

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

(27)

- -

м к

|=и = 1

где

в,

к Г1, при ек

(29)

чГ 1о. при е*

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

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

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

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

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

р. .= т - з. .= т(1 - з?.)

м м ч

(30)

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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