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

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

Яковлева Елена Сергеевна

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

Специальность 05.13.01 — Системный анализ, управление и обработка информации (в технических системах)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

005012500

Санкт-Петербург - 2012

005012500

Работа выполнена в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики.

Научный руководитель:

Научный консультант:

Официальные оппоненты:

доктор технических наук, профессор Ушаков Анатолий Владимирович

кандидат физико-математических наук, доцент Горбачев Валерий Николаевич

доктор физико-математических наук, Вакуленко Сергей Августович

Ведущая организация:

кандидат технических наук, доцент Скорубский Владимир Иванович

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» ■:

Защита состоится «21» февраля 2012 г. в 16 ч. 00 мин. на заседании диссертационного совета Д 212.227.03 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49, НИУ ИТМО.

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

Автореферат разослан «20» января 2012 г.

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

Дударенко Н.А.

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

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

Для вывода на печать цифровое изображение преобразует Raster Image Processor (RIP), представляющий собой программно-аппаратный комплекс, который осуществляет процедуру цифрового растрирования. Термин растрирование имеет много значений. В полиграфии под ним понимают (Ю.В. Кузнецов, 2002) преобразование иллюстративной информации в битовую карту из нулей и единиц, управляющих устройством печати. В настоящей работе рассматривается цифровой вариант растрирования, представляющий собой преобразование полутонового изображения, представленного в цифровом виде, в бинарное. В литературе по цифровой обработке такое преобразование называют бинаризация.

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

Вопросами применения информационных технологий допечатных процессов в полиграфии занимались Гасов В.М. и Цыганенко A.M. ■

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

Диссертационная работа посвящена решению данной задачи.

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

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

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

2. Обзор методов бинаризации и выбор объективных мер искажения для оценки работы алгоритмов бинаризации.

3. Алгоритмизация и реализация помехоустойчивого алгоритма бинаризации цифровых изображений (Д-алгоритм).

4. Исследование работы Д-алгоритма бинаризации и сравнение с другими алгоритмами бинаризации.

5. Разработка теоретико-информационной модели бинарного канала для описания ошибок процесса печати.

6. Применение условных операций для описания шумов процесса печати.

7. На основе объективных мер искажения изучение свойств . Д-алгоритма при воздействии бинарного шума и сравнение с другими алгоритмами.

8. Модифицирование Д-алгоритма с целью улучшения качества па основе метода рандомизации.

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

Научная новизна заключается в том, что:

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

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

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

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

/

процесса печати с целью анализа помехоустойчивости алгоритмов бинаризации цифровых изображений.

Реализация результатов. С 2008 года комплекс по бинаризации цифровых изображений, содержащий два учебных видеофрагмента с иллюстрацией методов бинаризации, внедрен в учебный процесс СЗИП СПГУТД в специальном курсе «Компьютерная обработка изображений» для специальностей 230203.65 «Информационные технологии в дизайне» и 230204.65 «Информационные технологии в медиаиндустрии». Теоретические положения диссертации и практические эксперименты используются в учебном процессе НИУ ИТМО и включены в курс лекций и практических занятий по дисциплинам: «Инженерная и компьютерная графика» для дипломированных специалистов, обучающихся по специальности 220201.65 и магистерского курса обучения «Методы цифровой обработки информации» направления 220200.

Апробация работы. Основные результаты диссертации были представлены на научных конференциях и семинарах:

1. На международной конференции «Optoinformatics - 2008» (Санкт-Петербург, 2008 г.);

2. На семинаре кафедры Автоматизированного полиграфического оборудования Северо-Западного института печати СПГУТД (Санкт-Петербург, 2008 г.);

3. На XI Санкт-Петербургской международной конференции «Региональная информатика - 2008» (Санкт-Петербург, 2008 г.); ^

4. На международной конференции студентов и молодых ученых «Print - 2009». (Санкт-Петербург, 2009 г.);

5. На семинарах кафедр Автоматизации полиграфического производства и Прикладной математики и моделирования систем Московского государственного университета печати (Москва, 2009, 2010 гг.);

6. На семинаре кафедры Обработка сигналов мультимедиа университета г. Констанца, (Германия, 2009 г., 2010 г., 2011 г.);

7. На семинаре Российско-Германских программ «Михаил Ломоносов / Иммануил Кант» (Бонн, Германия, 2009 г.);

8. На международной конференции студентов и молодых ученых «Printing Future Days 2011» (Хемниц, Германия, 2011 г.).

Работа поддержана грантом Министерства Рособразования и Германской службы академических обменов DAAD для выполнения НИР по проекту «Разработка и исследование методов компьютерной обработки изображений (полиграфия)» в 2009 г., грантом правительства г. Санкт-Петербурга, комитетом по науке и высшей школе для молодых ученых в 2009 г., для выполнения НИР по проекту «Использование методов квантовой теории информации в задачах обработки и анализа изображений», а также грантом Германской службы академических обменов DAAD для выполнения НИР по проекту «Алгоритмическое обеспечение растровых процессоров изображений» в 2010 г. В 2009-2011 гг. соискатель дважды проходила многомесячную стажировку в университете, г. Констанца (Германия), на кафедре Обработка сигналов мультимедиа под руководством профессора Дитмара Заупе, всемирно известного ученого в области обработки изображений, занимаясь изучением свойств Д-алгоритма, его сравнением по отношению к современным алгоритмам бинаризации,

программированием в Matlab, работой с иностранной литературой и выступлением на семинарах кафедры.

Публикации. Основные результаты по теме диссертации опубликованы в 13 работах, из них 6 - в журналах, включенных в Перечень ВАК РФ.

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

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

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

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

Показано, что бинаризация является важным инструментом обработки изображений. Бинаризацию полутоновых изображений можно рассматривать как процесс квантования с двумя уровнями, при котором возникают потери информации. Дело в том, что в ряде случаев свойства интересующих нас объектов исследуются по его изображению, методы анализа которых весьма разнообразны. С помощью бинаризации полутоновое изображение (grayscale) преобразуется в двухцветное или бинарное. Такое преобразование преследует разные цели, например: 1) выявление особенностей объектов, которые несут нужную информацию; 2) компактное описание; 3) создание иллюзии большого числа оттенков или цвета. Бинаризация используется в задачах исследования и диагностики сложных технических и биологических систем, в число которых входит распознавание образов, контроль и анализ материалов, видеонаблюдение, видеокодирование и другие.

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

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

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

Процесс бинаризации можно рассматривать как преобразование яркости, когда элемент f{x,y), где х =1,2,..,М, У = 1,2,..,<¥, MxN - размер изображения, матрицы

к

полутонового изображения, принимающий 2 значений, где к= 1,2,..., в общем случае преобразуется в матрицу R, состоящую из нулей и единиц

tf = fe(*,y):ir(x,y)e{0,l}}. (1)

Число элементов |/?| матрицы R определяет характер преобразования. Если [/?(> 2*, то преобразование будет происходить без потери информации, в этом случае информация не убывает, и само преобразование может быть выбрано обратимым. Однако при этом увеличивается размер матрицы бинарного изображения, которое будет содержать в |/?| раз больше элементов, чем исходное полутоновое изображение. При |Д|=2

/" (л-,з0 -> V, v) С {0,1}, (2)

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

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

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

В литературе выделяют: 1) пороговые методы бинаризации; 2) методы на основе равенства яркостей.

В пороговых методах значение яркости f{x,y) заменяется на 0, если f {x,y)<T, или на 1 в противоположном случае, где Т— порог. Выбор порога представляет собой самостоятельную задачу. В этой главе кратко описаны методы бинаризации, где порог выбирается на основе гистограммы яркостей или энтропии, а также приведены методы бинаризации со скользящим и случайным порогом.

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

^ИД^ЫХ^), (3)

X у х у

где Ent{Z)— целая часть Z. Яркость бинарной матрицы определяется числом единиц b = TZ.g{x,y).

X у

Если в бинарной матрице фиксировать число единиц Ъ, то при большом количестве элементов и »1 задача остается трудной. Действительно, количество всех матриц с фиксированным числом единиц Ъ равно

к= (4)

Ь\{п-Ь)\

Если число элементов велико: и» 1, то, воспользовавшись формулой Стерлинга к^2и!«/71о§2«-я, найдем, что К определяется числом элементов п и шенноновской энтропией Н(р) в бинарном элементе:

К*2"Н(Р\ (5)

где р = Ып относительное число единиц, Н(р) = -р\о%2 р — {\ —р)\о%2(\ —р) — энтропия случайной бинарной величины. Произведение пН(р) имеет простой смысл: это количество информации в бинарной матрице. Известно, что максимальная энтропия бинарной величины, равная одному биту, получается, если р = 1/2, когда единицы и нули встречаются одинаково часто. В итоге из полученной оценки следует, что К может экспоненциально зависеть от числа элементов п. Это означает, что задача поиска необходимой бинарной матрицы сводится к задаче перебора, которая является вычислительно сложной, в силу указанной экспоненциальной зависимости.

Трудность задачи перебора хорошо известна в литературе, например, в видеокодировании при поиске близких блоков из предыдущего и текущего кадров в стандартах МРЕО-4, Н.264. К настоящему времени быстрый алгоритм не известен, поэтому на практике используются методы, дающие частичное решение типа «поиск за три шага», «иерархический поиск» и другие. Примером частичного решения задачи служит рассмотренный в этой главе метод бинаризации известный как псевдотонирование, в котором используется условие сохранения яркости.

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

Субъективная визуальная оценка качества определяется системой человеческого зрения, где выделяют два уровня: низкий и высокий, который называют психофизиологическим. Некоторые тестовые процедуры субъективного оценивания качества приведены в рекомендации ШЛ-И. ВТ.500-11.

Объективные меры искажения основаны на вычислении различных числовых показателей, определенных для матриц. Они используют всевозможные метрики расстояний между матрицами, корреляционные показатели, энтропийные количества и другие. Из рассмотренного набора использовались меры, основанные на гельдеровой метрике, которая для двух матриц А и В размером М х N имеет вид

ЬР =

\ М N . .р

(6)

где аху, Ьху элементы матриц А и В.

При р = 1 и 2 возникает средняя разность и евклидово расстояние между матрицами. Чем меньше гельдерова метрика, тем матрицы А и В «ближе» друг к

8

другу, такое поведение меры должно соответствовать зрительному восприятию. На основе гельдеровой метрики строится пиковое отношение сигнал/шум (Peak Signal Noise Ratio (PSNR)), которое определяется следующим образом

PSNR = 20\ogl0maxxyAxy/e, (7)

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

Наряду с гельдеровой метрикой в качестве меры искажения в работе использовалась относительная энтропия, которая устанавливает соответствие между гистограммами яркости рА (/) и рн (/) двух матриц А и В

H{A\\B) = ZpMO^Eat:, (8)

РвО)

где i = 0,1,...255 — значения яркости. Относительная энтропия является неотрицательной, она равна нулю, если гистограммы одинаковы. Чем больше отличаются гистограммы, тем значение относительной энтропии больше.

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

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

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

2. В каждом блоке вычисляется яркость, которая определяет число единиц Ьш в бинарном блоке:

Е'А IЯх,у)\ = Ьа, (9)

(.»О'бт J

где Ent выделение целой части, f{x,y) значение яркости элемента матрицы полутонового изображения, нормированное условием max.f(x,y) = \. При таком выборе число единиц в блоке (о будет Ьт е[о, /г2]. Бинарный блок имеет тот же размер, что и полутоновый.

3. В бинарном блоке единицы расставляются в те позиции, где значения яркости f(x,y) убывают, начиная с максимального значения.

4. Из бинарных блоков собирается полное бинариое изображение.

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

Непосредственный анализ доказывает, что алгоритм является простым с вычислительной точки зрения, поскольку число шагов, которые требуется для решения задачи s = bmn._ полиномиально зависит от объема входных данных п, где п число элементов в ш. Это свойство делает его привлекательным для практики.

Для определения свойств Д-алгоритма его работа сравнивалась с работой двух алгоритмов RANDOM и KONUS, основанных на пороговом методе бинаризации, и работой алгоритма DITHER, который использует метод диффузии ошибок Флойда-Стейнберга. Так, было найдено, что Д-алгоритм имеет более хорошие показатели мер искажений для сильноконтрастных полутоновых изображений с плавным изменением яркости фона и объекта. Он плохо справляется с передачей равномерного фона.

Интересной особенностью оказался эффект увеличения контраста, что позволяет выявить слабоконтрастную структуру изображения, которая при зрительном восприятии или воспроизведении электронными средствами может быть недоступной (рис. 1).

МЕРЫ ИСКАЖЕНИИ

AD е PSNR

1-алг. 0.0128 0.0718 22.8809

EITHER 0.0100 0.0483 26.3282

IANDOM 0.0157 0.0897 20.9453

KONUS 0.0154 0.0880 21.1116 е

Рисунок 1 — Увеличение контраста при бинаризации изображения со слабоконтрастной структурой фона:

а) исходное полутоновое изображение; б) Д-алгоритм; в) DITHER; г) RANDOM; д) KONUS; е) меры искажений: AD - среднее расстояние, е - евклидово расстояние, PSNR - пиковое отношение сигнал/шум

При обработке цветных изображений, характер цветопередачи у Д-алгоритма оказался лучше, чем у RANDOM, KONUS и DITHER, что соответствует поведению объективных мер искажения.

В дополнении к этим алгоритмам, работа Д-алгоритма сравнивалась с набором современных алгоритмов бинаризации — BAYER, ERRDIF, DOTDIF, ULICHNEY, LAU, CDOD, основанных на диффузии ошибки. Из проведенных экспериментов , следует, что объективные меры искажения у Д-алгоритма лучше, а наиболее близкие 1 значения мер искажения имеет алгоритм ERRDIF. На рис. 2 приведены два изображения, полученные с помощью ERRDIF и Д-алгоритма. В качестве исходного 1 было выбрано изображение с равномерным изменением яркости, что представляет наибольшую трудность для Д-алгоритма.

а б

Рисунок 2 — Обработка деталей фрагмента изображения с медленным изменением яркости:

а) увеличенный фрагмент изображения, полученный ERRDIF; б) увеличенный фрагмент изображения, полученный Д-алгоритмом

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

Г, (10)

которая может быть решена перебором всех 2" бинарных матриц, где п — число элементов в блоке со .

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

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

Для зрительного восприятия работа модификации выглядит хуже: она не воспроизводит слабоконтрастные детали, усиливает контраст и насыщенность цвета. Однако модификация оказалась способной решить тест Тьюринга САРТСНА по различению человека и машины. Для тестирования был выбран образец со словом «flag», который обрабатывался алгоритмами RANDOM, KONUS, DITHER и исследуемым алгоритмом, как показано на рис. 3. Однако только после обработки модификацией текст был распознан. Полученный результат означает, что весьма естественное для глаза условие равенства яркости изображений хорошо соответствует оценке качества при зрительном восприятии, однако для машинного зрения более предпочтительным является условие минимума евклидова расстояния.

а б

г '

« м • i ы >äI * (

I «4«« Л * ««I

5 fT'^Jl, 1 1 »'Iff, (■■ 1 шва ■ 1 ш"{' щ < < V. . - г 1 ** t im i i ..J .

ш ......Ш flag

Рисунок 3 — Распознавание текста с шумом с помощью ABBYY FineReader 9.5: а) пример САРТСНА; б) образец для тестирования со словом «flag» на шумовом фоне; в) результат работы ABBYY FineReader 9.5: текст не распознан; г) образец обработан исследуемым Д-алгоритмом, текст не распознан; д) образец обработан модификацией, текст распознан

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

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

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

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

Для исследования помехоустойчивости алгоритмов бинаризации применительно к процессу печати была введена модель бинарного канала со стирающим шумом. Эта модель, где два входных сигнала 0 и 1 с некоторой вероятностью преобразуются в один, хорошо известна в теории информации. Для случая цифрового преобразования изображений такая модель шума не рассматривалась. В этой модели канал представляет собой устройство печати, на вход которого подается бинарное изображение, полученное из полутонового, а выходом служит «бумага», где «краска» воспроизводит бинарное изображение. Элементы «краска» и «бумага» могут иметь разную реализацию, например, можно говорить об электронной бумаге или'чернилах, основанных на современных технологиях. Однако методы воспроизведения полутонового или цветного изображения не меняются. В итоге имеем бинарный канал, где нули и единицы на входе, бинарное изображение в цифровом виде, преобразуются в нули и единицы на выходе, наличие или отсутствие печатного элемента на бумаге. В стирающем канале оба входных символа преобразуются в один: {0, 1}—> 1.

Шум в бинарном канале, который описывает процесс печати, имеет разные источники, например, вибрация печатающей головки. Тогда может возникать лишняя точка, точка может ставиться в неправильную позицию, размер точки может увеличиться и прочее. Имея в виду приведенный пример, такие шумы можно описывать с помощью условных операций вида С — V \х® у —> х®11"у, где х е {0,1} — управляющий бит, в качестве которого выступает бинарный шум, у е {0,1} — управляемый бит, которым является бинарное изображение, ® — знак тензорного произведения, а IIх равно либо единичному оператору, либо II, поскольку х = 0, либо х = 1. Из определения следует, что операция и действует на управляющий бит тогда и только тогда, когда значение управляемого бита равно 1. Такая операция позволяет моделировать более сложные источники шумов, которые действуют на окрестность бинарного изображения. Примером, используемым дальше, будет служить условная

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

(дс.вхОвО;,®^...®^)^^®^)®^1^®^...®^). (И)

Х1

Х2

окрестность бинарного изображения

У1 и

У2

уз

Рисунок 4 — Условная операция С-V для моделирования шума с двумя управляющими входами х, и х2 , где операция II действует на окрестность бинарного изображения у,, у2, у3

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

При численном моделировании мощность бинарного шума описывалась параметром Т, принадлежащим интервалу [0, 1 ], где значение 1 отвечает максимальной мощности.

Рассматривалась следующая схема проверки помехоустойчивости (рис. 5).

Рисунок 5 — Схема проверки помехоустойчивости алгоритмов бинаризации

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

v(x,y)®g(x>y)^^v(x,y)®(v(x,y)vg(x,y)), (12)

где управляющим сигналом служит матрица у с элементами У(х,у) е {0,1}, отвечающая бинарному шуму, управляемый сигнал — бинарная матрица g с элементами е {0,1}, представляющая изображение. В результате возникает

зашумленное бинарное изображение g'. Если считать, что 1 на выходе соответствует печатному элементу, 0 — его отсутствию, то стирающий канал описывает те ошибки, когда вместо пробельного элемента на бумаге возникает черная точка. Поскольку изображение g' носит случайный характер, то его характеристики, в частности меры искажения, будут случайными. Поэтому для вычисления интересующих характеристик проводилось усреднение по ансамблю реализаций бинарного шума, представленного случайной матрицей V. Так для вычисления евклидова расстояния между матрицами g ш g' использовалось выражение

где О — число реализаций.

Чтобы получить бинарный шум, использовался пороговый метод бинаризации полутонового изображения, представленного случайной матрицей г с элементами г(х,у), принимающими 28 =256 значений из интервала [0, 1]. Для эксперимента был выбран случай равномерного распределения. Бинарная матрица V или.бинарный шум получается следующим образом

, ч , ч 10, если г(х,у)>Т (14)

г{х,у)-+у{х,у) = \

[1, если г(х,у)<1

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

Для характеристики бинарного шума использовалась шенноновская энтропия Н(у), которая для рассматриваемого случая равна энтропии бинарного источника Н(у) = рЪё2р-{[-р)\оёг(\-р), (15)

где р — частота появления единиц. Здесь энтропия, как и другие характеристики бинарного шума, является случайной величиной, которая определяется реализацией случайной матрицы г. Этот факт иллюстрирует рис. 6а, где приведены значения энтропии бинарного шума, полученного из разных реализаций случайной матрицы г с порогом бинаризации Г = 0.4. Для вычисления среднего значения использовалось усреднение по 1000 реализаций г. В результате при 7 = 0.4 получается среднее значение энтропии Я Ду) = 0.9709. На рис. 66 приведена зависимость энтропии от порога Т, где каждая точка получена путем усреднения по 1000 реализаций

матрицы г. Энтропия имеет максимум при Г = 0.5, где появление 0 и 1 является практически независимыми. Для остальных уровней порога Т между элементами возникает корреляция, при Т- 0 и Т = 1 энтропия равна нулю, поскольку порог выбран так, что все значения в бинарной матрице либо нули, либо единицы.

Значение энтропии, Т=0.4

0.9735 -1-,-1-1-1-1-1-1-,-

0.973

0.9725

0.369 -1-1-1-1-1-1-1-1-1-

0 100 200 300 ¿00 500 600 700 ¡100 900 1000

Число реализаций

а

Энтропия

Значение порога

б

Рисунок 6 — Энтропия бинарного шума:

а) энтропия в зависимости от числа реализаций при значении порога Г = 0.4. Среднее значение по 1000 реализаций равно 0.9709; б) энтропия в зависимости от порога 7

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

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

При оценке помехоустойчивости Д-алгоритма и набора из BAYER, ERRDIF, DOTDIF, ULICHNEY, LAU, CDOD, использовались различные базы изображений, для которых наблюдалось разнообразное поведение алгоритмов. Это означает, что при обработке таких сложных объектов, как изображения, универсальных решений нет. Вместе с тем была найдена коллекция цифровых изображений для которой значение относительной энтропии у Д-алгоритма оказалось наименьшим. Этот результат показан на рис. 7, где представлено значение относительной энтропии, усредненное по 80 изображениям найденной коллекции. Поскольку относительная энтропия может служить критерием помехоустойчивости алгоритма, то чем меньше ее значение, тем более устойчивым оказывается алгоритм.

Относительная энтропия

| BAYER, ERRDIF, DOTDIF, ULICHNEY, LAU, CDOD i

I д

Значение порога

Рисунок 7 — Относительная энтропия, усредненная по 80 изображениям, для алгоритмов бинаризации BAYER, ERRDIF, DOTDIF, ULICHNEY, LAU, CDOD и Д-алгоритма

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

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

где И — размер обрабатываемого блока ю, который подлежал выбору, — его яркость. Значение дисперсии определяло порог, выше которого работает алгоритм без добавления шумов. ■

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

а б в

Рисунок 8 — Рандомизация:

а) работа рандомизированного алгоритма, А = 6, Ог: =0.009 б) исходное полутоновое изображение; в) работа исходного Д-алгоритма, И-6

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

4. Применение Д-алгоритма к слабоконтрастным полутоновым изображениям приводит к усилению контраста и выявлению слабоконтрастных деталей.

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации из перечня ВАК:

1. Горбачев, В.Н. Усиление перепутанного света при отражении от резонатора с нелинейной средой / В. П. Горбачев, А.И. Трубилко, Е.С. Яковлева // Журнал Оптика и спектроскопия. — М.: Наука, 2008. — том 105, №3. — С. 427r431.

2. Basharov, A.M. One-way gates based on EPR, GHZ and decoherence-free states of W class / A.M. Basharov, V.N. Gorbachev, A.I. Trubilko, E.S. Yakovleva // Журнал Physics Letters A. —Netherlands, Amsterdam.: Elsevier, 2009. — volume 373, issue 38. —P. 3410-3412.

3. Горбачев, В.Н. Один алгоритм бинаризации полутоновых изображений / В.Н. Горбачев, В.Н. Дроздов, Е.С. Яковлева // Журнал Дизайн. Материалы. Технологии. — СПб.: СПГУТД, 2009. — № 2(9). — С. 104-107.

4. Горбачев, В.Н. О вычислительной сложности одного алгоритма бинаризации полутоновых изображений / В.Н. Горбачев, Е.С. Яковлева II Журнал Дизайн. Материалы. Технологии. — СПб.: СПГУТД, 2009. — № 3(10). — С. 91-93.

5. Яковлева, Е.С. Алгоритмическое обеспечение растрирования при допечатной подготовке оригиналов / Е.С. Яковлева // Журнал Научно-технические ведомости СПбГТТУ, серия «Информатика. Телекоммуникации. Управление». — СПб.: СПбГПУ, 2009. — № 4. — С. 197-200.

6. Горбачев, В.Н. Устойчивость к стирающим шумам Д-алгоритма бинаризации изображений / В.Н. Горбачев, В.Н. Дроздов, Е.С. Яковлева II Журнал Проблемы полиграфии и издательского дела. —М.: МГУП, 2010. —№ 1. — С. 28-33.

Другие публикации

7. Горбачев, В.Н. Алгоритм бинарного кодирования цветных изображений / В.Н. Горбачев, И.К. Метелев, А.В. Резанов, Е.С. Яковлева // Труды XI Санкт-Петербургской международной конференции «Региональная информатика -2008». — СПб.: СПОИСУ, 2009. — С. 300-303.

8. Горбачев, В.Н. Об одном алгоритме бинаризации для полутоновых цифровых изображений с выделением слабоконтрастных структур / В.Н. Горбачев, В.Н. Дроздов, Е.С. Яковлева // Журнал Вестник МГУП. — М.: МГУП, 2009. — № 3. — С. 66-69.

9. Яковлева, Е.С. Изучение устойчивости бинарного изображения к шумам / Е.С. Яковлева // Материалы международной конференции молодых ученых «Print 2009». — СПб.: Петербургский институт печати, 2009. — С. 91.

Ю.Горбачев, В.Н. Устойчивость к шумам Д-алгоритма бинаризации / В.Н. Горбачев, В.Н. Дроздов, Е.С. Яковлева // Юбилейный сборник научных трудов кафедры автоматизированного полиграфического оборудования / под ред. В.Н. Дроздова. — СПб.: СПГУТД, 2010. — С. 94-112. П.Яковлева, Е.С. Алгоритмическое обеспечение растровых процессоров изображений (RIP) / Е.С. Яковлева // Сборник материалов научного семинара стипендиатов программ «Михаил Ломоносов II» и «Иммануил Кант II» 2009/10 года — М.: Германская служба академических обменов DAAD, 2010. — С. 5861.

12.Gorbachev, V.N. Modeling of printing noises and estimation of robustness to noise of the halftoning algorithms / V.N. Gorbachev, E.S. Yakovleva // Proceeding of the international student conference «Printing Future Days» — Ger., Chemnitz.: University of Technology, 2011. — P. 339-345.

13.Gorbachev, V.N. A binary noisy channel to model errors in printing process / V.N. Gorbachev, E.S. Yakovleva // 2011. http://arxiv.org/abs/! 110.0463, 12 P.

4

Подписано в печать 16.01.2012 Формат 60x90/16 Бумага офсетная. Усл. печ. л. I Тираж 100 экз. Заказ 15

Отпечатано в типографии «Адмирал» 199048, Санкт-Петербург, В.О., 6-я линия, д. 59 корпус 1, оф. 40

61 12-5/1589

САНКТ-ПЕТЕРБУРГСКИИ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

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

Яковлева Елена Сергеевна

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

05.13.01 — Системный анализ, управление и обработка информации

(в технических системах)

ДИССЕРТАЦИЯ

На соискание ученой степени кандидата технических наук

Научный руководитель

Доктор технических наук, профессор Ушаков А.В.

Научный консультант Кандидат физико-математических наук, доцент Горбачев В.Н.

Санкт-Петербург - 2011

СОДЕРЖАНИЕ

СОКРАЩЕНИЯ, ИСПОЛЬЗУЕМЫЕ В ДИССЕРТАЦИИ.....................................5

ВВЕДЕНИЕ..................................................................................................................7

ГЛАВА 1. ПРОБЛЕМА БИНАРИЗАЦИИ В ПОЛИГРАФИИ.............................17

1.1. Цифровые изображения.....................................................................................17

1.2. Процесс бинаризации........................................................................................20

1.3. Задача растрирования........................................................................................25

1.3.1. Линейные растры..........................................................................................25

1.3.2. Цифровые растры.........................................................................................27

1.3.3. Линиатура и количество градаций серого.................................................30

1.3.4. Модель зрения..............................................................................................32

1.3.5. Модель растрирования................................................................................34

1.3.6. Постановка задачи........................................................................................35

1.4. Другие области применения бинаризации......................................................36

1.4.1. Алгоритмы выделения границ....................................................................37

1.4.2. Морфологические операторы.....................................................................41

1.4.3. Преобразование Хафа..................................................................................42

Выводы по главе 1.....................................................................................................45

ГЛАВА 2. МЕТОДЫ БИНАРИЗАЦИИ..................................................................46

2.1. Пороговые методы.............................................................................................46

2.1.1. Выбор порога на основе гистограммы.......................................................47

2.1.2. Скользящий порог........................................................................................48

2.1.3. Энтропийные подходы................................................................................49

2.1.4. Стохастические методы................................ ...............................................51

2.2. Методы на условии равенства яркостей..........................................................53

2.2.1. Вычислительная сложность............................. ............................................53

2.2.2. Псевдотонирование......................................................................................55

2.3. Сравнение............................................................................................................56

2.3.1. Субъективные критерии..............................................................................57

2.3.2. Объективные меры искажения...................................................................58

Выводы по главе 2.....................................................................................................62

ГЛАВА 3. АЛГОРИТМ БИНАРИЗАЦИИ..............................................................63

3.1. Д-алгоритм и его вычислительная сложность................................................63

3.2. Минимизация евклидова расстояния...............................................................65

3.3. Деление полутоновых изображений в зависимости от плавности изменения яркости объекта и фона............................................................................................69

3.4. Бинаризация полутоновых изображений........................................................70

3.5. Современные алгоритмы бинаризации............................................................83

3.6. Увеличение контраста.......................................................................................90

3.7. Преобразование цветных изображений...........................................................94

3.8. Модификация и тест Тьюринга САРТСНА....................................................98

Выводы по главе 3...................................................................................................102

ГЛАВА 4. ПОМЕХОУСТОЙЧИВОСТЬ АЛГОРИТМОВ БИНАРИЗАЦИИ... 104 4.1. Шумы в полиграфии........................................................................................104

4.2. Бинарный канал................................................................................................105

4.3. Модель шума....................................................................................................108

4.4. Бинарный шум с заданной мощностью.........................................................111

4.5. Схема проверки помехоустойчивости...........................................................117

4.6. Относительная энтропия для определения помехоустойчивости алгоритмов бинаризации........................................................................................118

4.7. Модель стирающего канала............................................................................124

4.8. Размытие границ..............................................................................................125

4.9. Евклидово расстояние и относительная энтропия.......................................127

4.10. Случайное изменение размера......................................................................133

4.11. Рандомизация.................................................................................................138

Выводы по главе 4...................................................................................................145

ЗАКЛЮЧЕНИЕ.......................................................................................................147

ЛИТЕРАТУРА.........................................................................................................149

ПРИЛОЖЕНИЕ 1. КОДЫ ПРОГРАММ, РЕАЛИЗОВАННЫХ В СРЕДЕ MATLAB..................................................................................................................159

СОКРАЩЕНИЯ, ИСПОЛЬЗУЕМЫЕ В ДИССЕРТАЦИИ

RIP — Raster Image Processor, растровый процессор изображений PCL— Printer Control Language, язык описания страниц, созданный фирмой Hewlett-Packard

lpc — lines per centimeter, число линий на сантиметр lpi — lines per inch, число линий на дюйм dpi — dots per inch, число точек на дюйм Р задача — polynomial, задача полиномиального типа NP задача — non-polynomial, задача не полиномиального типа MPEG-4 (Moving Pictures Expert Group) — стандарт по изготовлению интерактивного видео на компакт-дисках, DVD-дисках и для цифрового телевидения, разработанный группой экспертов в области перемещения изображения Moving Picture Experts Group

ITU-R — Recommendations of International Telecommunication Union, набор международных технических стандартов, разработанный радиокоммуникационным сектором Международного телекоммуникационного общества

HVS — Human visual system, зрительная система человека CMYK — Cyan (голубой), Magenta (пурпурный), Yellow (желтый), black (черный), цветовая модель

RGB — Red (красный), Green (зеленый), Blue (синий), цветовая модель Н.264 — современный (High) стандарт видеосжатия, часть 10 стандарта MPEG-4, AVC (Advanced video coding, расширенное видеокодирование), основан на блочном гибридном кодировании, с уменьшенными размерами блока, встроенным фильтром уменьшения видимости блочных искажений NC — Normalized correlation, нормированная взаимная корреляция HS — Histograms similarity, подобие гистограмм PSNR — Peak signal-to-noise ratio, пиковое отношение сигнал/шум MD — Maximum difference, максимальная разность

AD — Average difference, средняя разность

MSE — Mean square error, среднеквадратичная ошибка

e — Euclidian distance, евклидово расстояние

LP — LP norm, норма

LMSE — Laplacian mean square error, Лапласова среднеквадратичная ошибка

SNR — Signal-to-noise ratio, отношение сигнал/шум CQ — Correlation quality, качество корреляции IF — Image fidelity, качество изображения

GSSNR — Global Sigma Signal to Noise Ratio, общее сигма-отношение сигнал/шум

SSNR — Sigma Signal to Noise Ratio, сигма-отношение сигнал/шум LGN — Lateral geniculate nucleus, латеральное коленчатое тело PSF — Point-Spread function, функция размытия точки

ВВЕДЕНИЕ

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

Для вывода на печать цифровое изображение преобразует Raster Image Processor (RIP), представляющий собой программно-аппаратный комплекс, который осуществляет процедуру цифрового растрирования. Термин растрирование имеет много значений. В полиграфии под ним понимают [1] преобразование иллюстративной информации в битовую карту из нулей и единиц, управляющих устройством печати. В настоящей работе рассматривается цифровой вариант растрирования, представляющий собой преобразование полутонового изображения, представленного в цифровом виде, в бинарное. В литературе по цифровой обработке такое преобразование называют бинаризация.

Значительные результаты в исследовании методов растрирования представлены в классических работах Шеберстова В.И. [2], Шашлова Б.А. [3], и др., в работах современных авторов, в частности Андреева Ю.С. [4, 5], Дроздова В.Н. [6], Кузнецова Ю.В. [1], Самарина Ю.Н. [7, 8], в работах зарубежных авторов, таких как Аллебах Я.П. [9], Арче Г.Р. [10]. Большое число методов бинаризации рассмотрено в монографии отечественных специалистов Фурмана Я.А., Юрьева А.Н. и Яншина В.В. [11], в работах по цифровой обработке изображений Сойфера В.А. [12, 13], Потапова А. А. [14] и многих других. Вопросы повышения качества методом цифровой обработки обсуждались рядом зарубежных авторов, таких как Прэтт У. [15, 16], Форсайт Д., ПонсЖ. [17], Стейнберг М.В., Флойд Р.В. [18], Лоу Д.Л. [10], Сэломон Д. [19].

Вопросами применения средств информационных технологий в полиграфии и использования программного обеспечения допечатных процессов занимались Гасов В.М. и Цыганенко A.M. [20 - 22]. Методы оценки искажений полутоновых оригиналов в автотипном процессе и методы адаптивного растрового преобразования обсуждались в работах сотрудников СевероЗападного института печати СПГУТД Желудева Д.Е. [23] и Щаденко A.A. [24].

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

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

Диссертационная работа посвящена решению данной задачи.

В работе рассматриваются классические методы и алгоритмы. Новые возможности следуют из применения для обработки изображений квантовых алгоритмов с использованием перепутанных состояний света, реализация которых на основе односторонних логических ячеек кратко обсуждалась в работах [25, 26].

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

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

Рис. В.1. Общая схема цифрового преобразования изображений с использованием процесса бинаризации

В работе будет разработан и исследован один алгоритм бинаризации, который далее будем называть Д-алгоритм [27]. Основные вопросы, которые подлежат рассмотрению, следующие: программная реализация, вычислительная сложность Д-алгоритма, его свойства и области применения, сравнение с другими алгоритмами бинаризации, помехоустойчивость. Первоначальная идея о создании Д-алгоритма бинаризации принадлежит проф. В.Н. Дроздову, а разработка, реализация, сравнительный анализ с другими алгоритмами — автору диссертации Яковлевой Е.С.

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

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

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

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

Хотя недостатка в алгоритмах бинаризации нет, однако защищенность их кода не позволяет проследить методы, положенные в их основу и определить их возможности. Высокая степень защищенности характерна для алгоритмов RIP профессионального уровня, что затрудняет их сравнение при выборе того или иного разработчика. По мнению экспертов [28 - 30], растет потребность использования решений на основе открытого исходного кода («open source»), поскольку они более доступны для анализа, позволяют снизить уровень пиратства, обеспечить информационную безопасность путем сертификации и т.д. Поэтому представляют интерес программы начального уровня, которые бы наглядно, шаг за шагом демонстрировали весь процесс, что может быть использовано не только на практике, но и в учебном процессе при подготовке специалистов в сфере полиграфии.

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

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

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

2. Обзор методов бинаризации и выбор объективных мер искажения для оценки работы алгоритмов бинаризации.

3. Алгоритмизация и реализация помехоустойчивого алгоритма бинаризации цифровых изображений (Д-алгоритм).

4. Исследование работы Д-алгоритма бинаризации и сравнение с другими алгоритмами бинаризации.

5. Разработка теоретико-информационной модели бинарного канала для описания ошибок процесса печати.

6. Применение условных операций для описания шумов процесса печати.

7. На основе объективных мер искажения изучение свойств Д-алгоритма при воздействии бинарного шума и сравнение с другими алгоритмами.

8. Модифицирование Д-алгоритма с целью улучшения качества на основе метода рандомизации.

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

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

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

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

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

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

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

Полученные результаты являются новыми, основные из них приведены в работах [25 - 27, 31 - 40