Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Иванов, В.Г., Любарский, М.Г., Ломоносов, Ю.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы обработки информации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207343
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2011. — № 5. — С. 98–109. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207343
record_format	dspace
spelling	irk-123456789-2073432025-10-07T00:00:55Z Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных Стиснення зображення тексту на основі формування і класифікації вертикальних елементів рядка в графічному словнику символьних даних Compression of Image of Text on the Basis of Forming and Classification of Vertical Elements of Line in the Graphic Dictionary of Character Data Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. Методы обработки информации Запропоновано метод стиснення зображень тексту на основі формування і класифікації вертикальних елементів рядка символьних даних графічного словника, отриманого на першому етапі автоматичної класифікації символів. Це дозволило сформувати новий словник вертикальних елементів рядка і карту їх розміщення, які в сукупності мають менший обсяг, ніж початковий графічний словник. Запропонований двоетапний алгоритм стиснення зображення тексту має перевагу в ступені стиснення порівняно з алгоритмом JB2 (формат DjVu) близько 25 % при роздільній здатності зображення тексту від 200 до 600 dpi. A method of compression of text images on the basis of forming and classification of vertical elements of character data line of graphic dictionary obtained on the first stage of automatic classification of characters is proposed. It allows forming the new dictionary of vertical elements of line and the map of their placing which have a less volume in an aggregate, than initial graphic dictionary. The offered two-stage algorithm of compression of image of text has about 25 % advantage in the degree of compression in comparison with algorithm of JB2 format of DjVu at resolution of text from 200 to 600 dpi. 2011 Article Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2011. — № 5. — С. 98–109. — Бібліогр.: 15 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207343 621.391:519.728 10.1615/JAutomatInfScien.v43.i10.40 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных Проблемы управления и информатики
description	Запропоновано метод стиснення зображень тексту на основі формування і класифікації вертикальних елементів рядка символьних даних графічного словника, отриманого на першому етапі автоматичної класифікації символів. Це дозволило сформувати новий словник вертикальних елементів рядка і карту їх розміщення, які в сукупності мають менший обсяг, ніж початковий графічний словник. Запропонований двоетапний алгоритм стиснення зображення тексту має перевагу в ступені стиснення порівняно з алгоритмом JB2 (формат DjVu) близько 25 % при роздільній здатності зображення тексту від 200 до 600 dpi.
format	Article
author	Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В.
author_facet	Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В.
author_sort	Иванов, В.Г.
title	Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных
title_short	Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных
title_full	Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных
title_fullStr	Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных
title_full_unstemmed	Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных
title_sort	сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207343
citation_txt	Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2011. — № 5. — С. 98–109. — Бібліогр.: 15 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT ivanovvg sžatieizobraženiâtekstanaosnoveformirovaniâiklassifikaciivertikalʹnyhélementovstrokivgrafičeskomslovaresimvolʹnyhdannyh AT lûbarskijmg sžatieizobraženiâtekstanaosnoveformirovaniâiklassifikaciivertikalʹnyhélementovstrokivgrafičeskomslovaresimvolʹnyhdannyh AT lomonosovûv sžatieizobraženiâtekstanaosnoveformirovaniâiklassifikaciivertikalʹnyhélementovstrokivgrafičeskomslovaresimvolʹnyhdannyh AT ivanovvg stisnennâzobražennâtekstunaosnovíformuvannâíklasifíkacíívertikalʹnihelementívrâdkavgrafíčnomuslovnikusimvolʹnihdanih AT lûbarskijmg stisnennâzobražennâtekstunaosnovíformuvannâíklasifíkacíívertikalʹnihelementívrâdkavgrafíčnomuslovnikusimvolʹnihdanih AT lomonosovûv stisnennâzobražennâtekstunaosnovíformuvannâíklasifíkacíívertikalʹnihelementívrâdkavgrafíčnomuslovnikusimvolʹnihdanih AT ivanovvg compressionofimageoftextonthebasisofformingandclassificationofverticalelementsoflineinthegraphicdictionaryofcharacterdata AT lûbarskijmg compressionofimageoftextonthebasisofformingandclassificationofverticalelementsoflineinthegraphicdictionaryofcharacterdata AT lomonosovûv compressionofimageoftextonthebasisofformingandclassificationofverticalelementsoflineinthegraphicdictionaryofcharacterdata
first_indexed	2025-10-07T01:10:29Z
last_indexed	2025-10-08T01:05:02Z
_version_	1845373700806803456
fulltext	© В.Г. ИВАНОВ, М.Г. ЛЮБАРСКИЙ, Ю.В. ЛОМОНОСОВ, 2011 98 ISSN 0572-2691 УДК 621.391:519.728 В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов СЖАТИЕ ИЗОБРАЖЕНИЯ ТЕКСТА НА ОСНОВЕ ФОРМИРОВАНИЯ И КЛАССИФИКАЦИИ ВЕРТИКАЛЬНЫХ ЭЛЕМЕНТОВ СТРОКИ В ГРАФИЧЕСКОМ СЛОВАРЕ СИМВОЛЬНЫХ ДАННЫХ Введение Теория и практика сжатия данных служит основным и эффективным инстру- ментом формирования и архивации цифрового контента огромного числа различ- ных текстовых документов: книг, журналов, технической документации и т.д. Оче- видно, что наибольшей степени сжатия этого типа изображений можно достичь только с помощью методов классификации и распознавания образов [1–7]. В част- ности, на классификации изображений символов, составляющих изображение тек- ста, основан наиболее эффективный алгоритм JB2, который как составная часть входит в графический формат DjVu [8, 9]. В работе [10] авторы предложили более совершенный алгоритм классификации, соответственно позволяющий достичь более высокого, чем алгоритм JB2, сжатия изображений текста. Тот или иной метод классификации, применяемый для сжатия изображения текста, основан на декомпозиции исходного изображения текста на изображения отдельных символов, которые в совокупности составляют этот текст. Основная задача классификации — разбить изображения символов на классы так, чтобы различные изображения одного и того же символа попадали в один и тот же класс. Эта задача довольно сложная из-за шумов печати и сканирования, которые приводят к тому, что, как правило, на странице нет ни одного повторяющегося изображения одного и того же символа, скажем, буквы «а». В идеале после проведения классификации все изображения одного и того же символа в тексте попадают в один класс. В таком случае можно заменить все изоб- ражения из каждого класса одним, например усредненным изображением данного символа. Изображение текста после классификации символов можно представить в виде «графического словаря» — набора усредненных изображений каждого симво- ла, и «картой регионов» — описанием положения каждого символа в тексте. В итоге результирующий размер файла изображения текста существенно уменьшится [10]. В реальности не удается получить для каждого символа только один класс его изображений и соответственно иметь для него в «графическом словаре» толь- ко одно изображение. Чем выше уровень шумов (при одном и том же качестве классификации), тем больше изображений одного и того же символа находится в словаре и тем больший объем имеет «графический словарь». Это существенно снижает степень сжатия изображения, так как «графический словарь» занимает значительный объем в закодированном изображении текста. Цель настоящей работы — усовершенствование алгоритма сжатия текстовых изображений, основанное на дополнительном сжатии «графического словаря». Предлагаемый метод базируется на представлении всех изображений символов, входящих в состав «графического словаря», последовательностью вертикальных элементов строки и их автоматической классификации с последующим построе- нием карты их размещения. Таким образом, предлагаемый алгоритм сжатия текстовых изображений раз- бивается на два этапа (рис. 1). Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 99 1.1. Графический словарь символов 1.2. Карта регионов символов графического словаря 2.1. Словарь вертикальных элементов строки (ВЭС) 2.2. Карта размещения ВЭС 1. Изображение текста Первый этап Второй этап Рис. 1 На первом этапе при создании «графического словаря» и «карты регионов» используется технология выделения связных символов и разбиение их на классы, предложенная в работе [10]. Основное отличие применяемой здесь классифика- ции — использование новой методики определения степени близости изображе- ний двух символов при их сравнении. Предложенная методика мало чувствитель- на к шумам печати и сканирования, так как основана на стабильных характери- стиках, которые не зависят от характерных контурных шумов печати и сканирования. Это в значительной степени повышает качество классификации изображений символов, осуществляемой с помощью известного алгоритма «про- сеивания» [11]. Второй этап — сжатие «графического словаря» изображений символов, по- лученного на первом этапе. Этот этап и рассматривается в данной статье (бло- ки 2.1 и 2.2 на рис. 1). Постановка задачи Если представить строку в изображении текста как прямоугольник с горизон- тальным основанием, охватывающий текст строки, то вертикальным элементом строки (ВЭС) является пересечение этого прямоугольника с любой вертикальной линией шириной в один пиксел. На рис. 2 показано разбиение изображения буквы «е» на ВЭС. Таким образом, все символы можно представить как объединение различных ВЭС одного и того же размера. (Более строгое определение ВЭС приводится ниже после введения необходимых геометрических параметров строки, употребляемых в типографском шрифте.) Итак, для сжатия «графического словаря», полученного на первом этапе ал- горитма и содержащего изображения символов, необходимо решить следующие основные задачи: 1) разделить все символы, входящие в состав «графического словаря», на ВЭС одинакового размера; 2) провести автоматическую классификацию ВЭС; 3) представить «графический словарь» как совокупность словаря ВЭС и кар- ты размещения для минимизации его объема. Рис. 2 100 ISSN 0572-2691 Фрагмент графического словаря для изображения страницы текста форма- та А4 при разрешении сканирования 300 dpi, сформированного в результате пер- вого этапа алгоритма (рис. 1, блок 1.1) представлен на рис. 3, a. На рис. 3, б пока- зан восстановленный «графический словарь» после второго этапа обработки (рис. 1, блоки 2.1 и 2.2). а б Рис. 3 Влияние шумов печати и сканирования, искажающих формы изображений символов, приводит к тому, что после проведенной классификации в сформиро- ванном «графическом словаре» (рис. 3, а) есть повторяющиеся изображения неко- торых символов. Кроме того, число классов увеличивается из-за образовавшихся в результате слияния двух и больше изображений символов, например «fh». Эти обстоятельства значительно увеличивают размер «графического словаря», что, в свою очередь, уменьшает степень компрессии всего изображения текста. Основная идея предлагаемого алгоритма — разбиение «графического слова- ря» (рис. 3, а) на совокупность ВЭС для их последующей автоматической класси- фикации. Это необходимо для создания нового словаря ВЭС (рис. 1, блок 2.1), в котором будет исключен основной недостаток исходного «графического слова- ря», а именно, повторение изображений одних и тех же символов, принадлежа- щих разным классам. Следует отметить, что подобный недостаток присущ ал- горитму JB2 еще в большей степени — словарь, который дает алгоритм JB2 по количеству классов, примерно вдвое превосходит тот, который получается в ре- зультате первого этапа алгоритма, предложенного в работе [10]. Таким образом, представив «графический словарь» изображений символов (см. рис. 1, блок 1.1) как совокупность нового словаря ВЭС (см. рис. 1, блок 2.1), значительно меньшего размера, и картой размещения ВЭС (см. рис. 1, блок 2.2), мож- но увеличить общую степень компрессии всего исходного изображения текста. Метод сжатия изображений символов «графического словаря» Предлагаемый метод обработки «графического словаря» изображений сим- волов можно разделить на несколько этапов: 1) предобработка — выравнивание изображений символов «графического словаря» в строке, фильтрация контурных шумов изображений символов на гра- ничных ВЭС; 2) разбиение изображений символов «графического словаря» на ВЭС и фор- мирование групп ВЭС по количеству связных компонент; 3) предварительное определение количества классов в каждой группе ВЭС; 4) автоматическая классификация ВЭС, формирование словаря ВЭС и карты размещения в «графическом словаре». Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 101 Восстановление изображения текста происходит в два этапа (см. рис. 1): 1) восстановление изображений символов «графического словаря» (см. рис. 1, блок 1.1); 2) синтез изображения всего текста. Двухэтапный алгоритм сжатия асимметричен по количеству операций и со- ответственно по быстродействию. 1. Предобработка: выравнивание изображений символов «графического сло- варя» в строке. Фильтрация контурных шумов изображений символов на гранич- ных ВЭС. Определение линий привязки символов в строке «графического слова- ря» решается построением гистограммы строки, показывающей количество пере- сечений произвольной горизонтальной линии с изображениями символов текста. На рис. 4 представлен фрагмент изображений символов «графического словаря» и соответствующая ему гистограмма. С помощью полученных гистограмм опреде- ляется высота строки как расстояние между линией верхних выносных элементов (ЛВВЭ) и линией нижних выносных элементов (ЛНВЭ). Так же определяются ли- ния строчных знаков (ЛСЗ) и базовая линия (БЛ) как два максимальных значения гистограммы в пределах заданной строки. Наибольший интерес представляет БЛ для решения следующей задачи — выравнивание символов в строке. Цель этой операции — привязать все изображе- ния символов строки к уровню БЛ. ЛВВЭ ЛCЗ БЛ ЛНВЭ ЛВВЭ ЛCЗ БЛ ЛНВЭ Рис. 4 В результате все символы «графического словаря» располагаются между ЛВВЭ и ЛНВЭ и привязаны к БЛ строки. Это расстояние одинаково для всех символов «графического словаря» и соответствует высоте ВЭС. На рис. 5 показана замена искаженных вертикальных элементов в изображе- ниях символов «графического словаря». Необходимо отметить, что влияние кон- турных шумов особенно заметно на граничных ВЭС, рис. 5 а. Напомним, что шу- мы печати и сканирования имеют контурный, а не структурный характер. Гра- ничные ВЭС уникальны в силу влияния шумов и при классификации могут порождать большое количество классов с одним представителем. Для устранения подобного недостатка граничные вертикальные элементы изображений символов «графического словаря» заменяются на соседние ВЭС этого же символа. Резуль- тат замены искаженных шумами граничных вертикальных элементов представлен на рис. 5, б (более светлый фон). Искажения символов изображения при этом ма- ло заметны, а количество классов ВЭС значительно уменьшается. В результате предложенной предобработки изображений символов «графи- ческого словаря» достигаются следующие результаты: 1) все изображения символов «графического словаря» выравниваются в пре- делах строки по БЛ; 2) ВЭС имеют одинаковый размер, равный расстоянию от ЛНВЭ до ЛВВЭ (рис. 4) которое для каждого символа «графического словаря» одинаково; 3) заменены искаженные шумами граничные элементы символов (рис. 5). 102 ISSN 0572-2691 а б Рис. 5 2. Разбиение изображений символов «графического словаря» на ВЭС и фор- мирование групп ВЭС по количеству связных компонент. После предобработки все изображения символов «графического словаря» требуется разложить на ВЭС, как показано на рис. 6, где все ВЭС, формирующие изображение символа «e», имеют одинаковый размер по высоте, что является необходимым условием для их автоматической классификации. ЛВВЭ ЛCЗ БЛ ЛНВЭ В Э С 1 компонента 3 компоненты 2 компоненты Рис. 6 В данном случае ВЭС, составляющие изображение символа «e», будут распре- делены в группы ВЭС с одной, двумя и тремя связными компонентами (рис. 6). Разделение ВЭС на группы по количеству компонент необходимо для того, чтобы при их классификации исключить возможность сравнения ВЭС с различным ко- личеством компонент и дальнейшим их возможным объединением в один класс. 3. Предварительное определение количества классов в каждой группе ВЭС. Для проведения автоматической классификации ВЭС разбиваются на группы, в каждой находятся ВЭС с одинаковым количеством связных компонент (рис. 6). Для автоматической классификации каждой группы требуется определить коли- чество классов. Для этого в каждой группе ВЭС с одинаковым количеством ком- понент проводится предварительная классификация методом «просеивания» [11]. В каждой группе с одинаковым числом компонент выбирается произвольный элемент из классифицируемого множества и в один класс с ним помещаются все элементы, достаточно близкие к нему. Далее рассматриваются только ВЭС из этой же группы, не вошедшие в первый класс. Если такие ВЭС имеются, то из них произвольно выбирается какой-либо элемент и аналогичным образом строится второй класс. Этот процесс повторяется до тех пор, пока не будут исчерпаны все элементы группы ВЭС с одинаковым количеством компонент. Основным моментом алгоритма «просеивания» является выбор метода, кото- рый определяет понятие достаточной близости двух элементов (ВЭС). Этот метод определяется тем важным обстоятельством, что шумы печати и сканирования носят контурный характер, т.е. искажение изображений символов текста происходит только на их границах. В предлагаемом алгоритме два ВЭС, принадлежащие одной группе, считаются близкими, если для каждой связной компоненты сравниваемых ВЭС выполняется условие ,0 1 или ,2 где  — задаваемый параметр, Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 103 который определяет количество возможных точек не- совпадения для каждой компоненты в составе ВЭС. Две компоненты могут считаться близкими, если они отли- чаются на заданное количество точек несовпадения: 1) 0 — полное совпадение двух связных ком- понент при их совмещении; 2) 1 — допускается несовпадение двух связ- ных компонент при их совмещении на 1 точку толь- ко с одной стороны компоненты (сверху или снизу); 3) 2 — допускается несовпадение двух связ- ных компонент при их совмещении на 1 точку с обеих сторон компоненты (сверху и снизу). Возможные варианты несоответствия связных компонент, сравниваемых ВЭС для заданных 1 и ,2 представлены на рис. 7, а, б соответственно. Допуск несовпадения связных компонент 1( точка) обусловлен тем фактом, что искажения, вносимые контурными шумами сканирования, в каждой связной компоненте могут находиться только на ее концах — сверху и снизу. Таким образом, задаваемый параметр  существенно органичен в своем диапазоне значений 0(  — условие полного соответствия сравнивае- мых компонент, 1 — возможность несовпадения с одной стороны компонен- ты и 2 — возможность несовпадения с двух сторон компоненты). В результате предварительной классификации можно найти число классов для автоматической классификации. Эта задача решается путем определения цент- ров классов при задаваемом  , который и определяет степень близости связных компонент и соответственно ВЭС. В табл. 1 приведены значения количества клас- сов ВЭС для различной степени близости связных компонент . Минимальное количество классов формируется при большей степени свободы параметра несо- ответствия связных компонент, но и искажения в изображении текста, вносимые при такой классификации, будут значительнее. Таблица 1 Разрешение изображения (dpi) 200 300 400 500 600 Количество классов при Δ  0 936 1119 1359 1707 2055 Количество классов при Δ  1 492 613 822 1045 1272 Количество классов при Δ  2 278 399 562 745 906 4. Автоматическая классификация ВЭС. Формирование его словаря и карты размещения ВЭС в «графическом словаре». Предлагаемый метод автоматической классификации базируется на алгоритме k-средних [11, 12]. Алгоритм, решающий эту задачу, состоит в следующем. ВЭС рассматриваются как векторы с бинарными координатами. Параметром классификации является k — число классов. Произвольно из множества X выбирается k элементов kee ,...,1 — цент- ров класса (в первом приближении). Все элементы изображения разбиваются на k классов kSSS ,...,, 21 по правилу: для каждого элемента x определяется ближай- ший центр класса, т.е. вектор je , минимизирующий величину jex  , затем в один класс объединяются все элементы, имеющие один и тот же ближайший центр класса. Далее определяются новые центры класса (во втором приближении) путем усреднения элементов в каждом классе: а б Рис. 7 104 ISSN 0572-2691 , 1    SSxs s x N e (1) где sN — число элементов в классе S и .,...,2,1 kS  После этого процедура повторяется, исходя из новых центров класса. Опи- санные итерации заканчиваются, когда центры классов перестают изменяться. Напомним, что в данной работе этот алгоритм дополнен предварительным «про- сеиванием» элементов [11]. Эта процедура состоит в том, что, задавшись пара- метром 0 ,0(  1 или )2 и произвольным элементом 1x из со- вокупности векторов X, объединяют в один класс 1X все элементы множества, находящиеся от 1x на расстоянии, меньшем, чем , т.е. удовлетворяющие нера- венству .1  xx (2) Эти векторы могут находиться на расстоянии ,0(  ,1 )2 или расстояние между ними равно бесконечности. Далее произвольно выбирается элемент ,2x не принадлежащий классу ,1X и аналогичным образом строится класс .2X Процесс заканчивается, когда каждый элемент из X попадет в какой- либо класс. После этого в качестве центров первого приближения для алгоритма автома- тической классификации используются векторы, являющиеся средними в полу- ченных методом «просеивания» классах, т.е. , 1    jXxj j x M e (3) где jM — число элементов в классе ,jX ,,...,2,1 mj  и )( mm — число по- лученных классов (см. табл. 1). Предварительное применение метода просеивания значительно улучшает сходимость алгоритма k-средних и, следовательно, сокращает вычислительное время. Это объясняется тем, что уже на первом шаге центры нулевого приближе- ния аппроксимируют члены своего класса с точностью, не меньшей значения па- раметра . Еще одним преимуществом предложенной предобработки является то, что метод просеивания позволяет автоматически определить необходимое число классов. Для кодирования «графического словаря» символов необходимо составить карту размещения ВЭС, которая определяет размещение векторов kSS ,...,1 , и для каждого вектора jS указать соответствующий ему центр .je Далее карта разме- щения ВЭС и сам словарь ВЭС кодируются стандартными методами сжатия без потерь в бинарном виде. Фрагмент полученного словаря ВЭС для изображения текста с разрешением 300 dpi после автоматической классификации представлен на рис. 8 (серые полосы — искусственно введенные разделители для отдельных классов ВЭС). Рис. 8 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 105 Сравнительная характеристика количественных показателей первого и второго этапов сжатия изображений текста Объем графического файла, который сжат каким-либо алгоритмом, основан- ным на классификации, состоит из объема, занимаемого «графическим словарем», и объема «карты регионов». Первый объем пропорционален количеству классов, полученных при классификации, второй зависит от количества классов логариф- мически (разрядность каждого символа уменьшается на 1 бит при уменьшении количества классов вдвое). Поэтому можно ожидать, что предложенный в этой статье алгоритм автоматической классификации ВЭС (см. табл. 1) обеспечит бо- лее высокую степень компрессии исходного изображения текста. В табл. 2 представлены количественные показатели объемов первичного «гра- фического словаря», а также словаря ВЭС и карты их размещения. Приведенные показатели отображают как оригинальный размер, так и размер данных после ком- прессии энтропийными методами (полужирный шрифт). Объем данных приведен в килобайтах (kb). Для всех данных в качестве алгоритма сжатия без потерь исполь- зовался алгоритм 7-zip, который является модификацией словарного метода ком- прессии LZ77 [13, 14, 15] — LZMA (Lempel-Ziv-Markov chain-Algorithm). Следует заметить, что несмотря на значительное отличие в оригинальных размерах «графи- ческого словаря» символов (первый этап, рис. 1) и суммарного оригинального раз- мера словаря ВЭС и карты размещения ВЭС (второй этап, рис. 1), в сжатом виде (полужирный шрифт) эти различия существенно снижаются для всех значений разрешения изображения текста. Результирующий размер после суммарного сжа- тия словаря ВЭС и карты размещения ВЭС несколько меньше, чем размер словаря ВЭС и карты их размещения после сжатия, взятые по отдельности. Это расхожде- ние обусловлено общей обработкой двух массивов, представленных в едином по- токе данных. Таблица 2 Разрешение изображения текста (dpi) 200 300 400 500 600 Размер «графического словаря» символов (kb)/ после сжатия (kb) 34,8 /4,4 46,4 /5,0 67,7 /4,7 94,6 /5,4 140,2 /6,7 Второй этап Размер словаря ВЭС (kb)/после сжатия (kb) 1,2 /1,0 2,5 /1,5 4,4 /2,1 7,3 /3,0 10,8 /3,8 Карта размещения ВЭС (kb)/после сжатия (kb) 6,1 /2,2 6,2 /2,1 5,7 /2,3 6,4 /2,5 8,0 /3,0 Словарь ВЭС + карта разме- щения ВЭС (kb)/после сжатия (kb) 7,3 /3,0 8,7 /3,4 10,1 /4,2 13,7 /5,2 18,8 /6,6 Наиболее значимые различия в выходных (сжатых) объемах данных наблю- даются при малых значениях разрешения изображения текста (200, 300 и частич- но 400 dpi), а при более высоких разрешениях (500, 600 dpi) разница между сжа- тыми данными «графического словаря» символов и суммарными выходными данными словаря ВЭС и карты их размещения практически отсутствует (по- лужирный шрифт). Это свидетельствует о том, что при больших разрешениях изображения текста «графический словарь» символов фактически не содержит различных классов с одинаковыми представителями. В таком случае взаимная корреляция между символами «графического словаря» может присутствовать только в связных компонентах ВЭС, представляющих различные символы «гра- фического словаря» (см. рис. 6), что, в свою очередь, существенно снижает эф- фективность второго этапа при сжатии «графического словаря» символов. При малых разрешениях (200–400 dpi), наоборот, «графический словарь» символов содержит значительное количество разных классов, представляющих одинаковые символы или фрагменты одинаковых символов. Повторяющиеся сим- волы в «графическом словаре» существенно повышают взаимную корреляцию 106 ISSN 0572-2691 между ВЭС. Поэтому после разбиения такого «графического словаря» на ВЭС и проведения автоматической классификации эффективность суммарного сжатия словаря ВЭС и карты их размещения существенно возрастает. В табл. 3 представлены значения коэффициентов сжатия «графического сло- варя» символов (первый этап), а также значения общего коэффициента сжатия словаря ВЭС и карты их размещения (второй этап) при различных разрешениях изображения текста. Таблица 3 Разрешение изображения текста (dpi) 200 300 400 500 600 Коэффициент сжатия «графического словаря» символов (первый этап) 7,9 9,28 14,4 17,51 20,92 Коэффициент сжатия словаря ВЭС + карта размещения ВЭС (второй этап) 11,6 13,64 16,11 18,19 21,24 На рис. 9 представлены значения коэффициентов сжатых данных «графическо- го словаря» символов (первый этап) и суммарных данных словаря ВЭС и карты их размещения (второй этап) при различных разрешениях изображения текста. Из приведенных кривых можно сделать вывод, что применение второго этапа обработки изображения текста эффективно при малых разрешениях исходного изображения текста, когда «графический словарь» связных символов имеет боль- шую повторяемость классов и соответственно более высокую степень близости ВЭС между отдельными представителями классов символов «графического сло- варя». В таком случае разбиение «графического словаря» на ВЭС и их последую- щая автоматическая классификация существенно снижают взаимную корреляцию между представителями словаря ВЭС, что позволяет сформировать очень малень- кий по размеру словарь ВЭС (см. табл. 2, 3) и карту их размещения, которые в сумме имеют бóльшую степень компрессии, чем «графический словарь» симво- лов непосредственно. При высоких значениях разрешения (500, 600 dpi) и соответственно хорошем качестве исходного изображения «графический словарь» не имеет в своем составе одинаковых классов, и, следовательно, второй этап обработки изображения текста не будет иметь существенного влияния на степень сжатия «графического слова- ря» символов и соответственно и на итоговый показатель компрессии исходного изображения. В качестве исходного изображения выбрана страница текста на английском языке, набранная шрифтом Times New Roman, кегль 12 pt с интерлиньяжем 1. Изображения этой страницы формировались с помощью планшетного сканера при разрешениях 200, 300, 400, 500 и 600 dpi, глубина цвета 1 бит, формат *.bmp. Степень компрессии оценивалась в абсолютных величинах (см. табл. 2) — коли- честве килобайт (kb) после сжатия (полужирный шрифт) и относительных вели- чинах — коэффициенте сжа- тия (табл. 3). Как видно из приведен- ных в табл. 4 данных, резуль- таты компрессии (полужир- ный шрифт) у предлагаемого в этой статье алгоритма после второго этапа обработки су- щественно превышают анало- гичные показатели первого этапа (обычный шрифт [10]). 0 5 10 15 20 25 0 100 200 300 400 500 600 700 Разрешение (dpi) К о эф ф и ц и ен т сж ат и я Первый этап Второй этап Рис. 9 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 107 Таблица 4 Разрешение изображения текста (dpi) 200 300 400 500 600 Исходный размер файла (kb) 505,3 1080,2 2003,9 3111,2 4498,0 Этапы обработки изображения текста Исходный размер (kb) /Размер после сжатия (kb) Первый этап Размер «графического словаря» символов (kb)/ после сжатия (kb) 34,8/4,4 46,4/5,0 67,7/4,7 94,6/5,4 140,2/6,7 Размер карты регионов символов «графического словаря» (kb)/ после сжатия (kb) 10,9/3,9 10,7/3,3 11,0/3,5 10,9/3,6 10,9/3,7 Результат обработки первого этапа (kb)/после сжатия (kb) 45,7/8,1 57,1/8,0 78,7/8,0 105,5/8,8 151,1/10, 3 Второй этап Размер «графического словаря» символов после второго этапа (kb)/ после сжатия (kb) 7,3/3,0 8,7/3,4 10,1/4,2 13,7/5,2 18,8/6,6 Результат сжатия изображения текста после первого и второго этапов обработки (kb) 6,8 6,5 7,5 8,6 10,1 Алгоритм JB2 в формате DjVu (kb) 9,6 8,7 9,9 11,4 13,6 Следует отметить, что оригинальные и сжатые размеры карты регионов сим- волов «графического словаря» на первом этапе обработки мало изменяются при различных разрешениях исходного изображения текста. Такое постоянство в раз- мерах данных говорит об их структурной близости. Действительно, при всех рас- сматриваемых разрешениях исходного изображения текста структура карты реги- онов символов «графического словаря» определяется последовательностью зна- чений отображающих номера классов символов «графического словаря», а по количественному составу эти последовательности довольно близки. Следователь- но, при любых разрешениях изображения на первом этапе обработки сжатие по- следовательности данных будет давать практически одинаковые результаты. Необходимо отметить, что оригинальный размер «графического словаря» сим- волов (обычный шрифт) с увеличением разрешения исходного изображения про- порционально возрастает, однако в сжатом виде (полужирный шрифт) преимуще- ства второго этапа обработки наиболее заметны при малых разрешениях исходного изображения (рис. 9), что объясняется низким качеством классификации связных символов на первом этапе обработки [10]. По отношению к первому этапу обработки [10] применение второгого этапа дает следующий выигрыш в сжатии изображения текста при разных разрешениях: 200 dpi — 16 %; 300 dpi — 19 %; 400 dpi — 6 %; 500 dpi — 3 %; 600 dpi — 2 % (табл. 5). По сравнению с алгоритмом JB2 (DjVu) использование первого и второго этапов обработки в предложенном алгоритме позволяет уменьшить объемы вы- ходных данных на 29 % при 200 dpi, 25 % при 300 dpi, 24 % при 400 dpi, 24,5 % при 500 dpi и 25,5 % при 600 dpi соответственно. В табл. 5 приведены значения коэффициентов сжатия всего изображения тек- ста после первого и второго этапов обработки и степень сжатия алгоритмом JB2 формата DjVu , а также преимущество в процентном соотношении. Таблица 5 Разрешение изображения текста (dpi) 200 300 400 500 600 Коэффициент сжатия изображения текста (первый этап) 62,38 135 250,48 353,54 436,7 Коэффициент сжатия изображения текста (первый и второй этапы) 74,3 166,18 267,18 361,76 445,34 Преимуществo первого и второго этапов в сравнении с первым этапом, в % 16 19 6 3 2 Коэффициент сжатия изображения текста JB2 (DjVu) 52,63 124,16 202,41 272,91 330,73 Преимущества предложенного метода (первый и второй этапы) в сравнении с JB2, в % 29 25 24 24,5 25,5 108 ISSN 0572-2691 На рис. 10 приведены гра- фики, отображающие значения коэффициентов сжатия данных на первом этапе обработки, по- следовательном применении пер- вого и второго этапов обработки и при сжатии изображения тек- ста алгоритмом JB2 формата DjVu. Преимущество предло- женного метода составляет око- ло 25 % для всех разрешений изображения (см. табл. 5). Заключение С помощью дополнительного этапа обработки изображений текста, который состоит в разбиении «графического словаря» символов на совокупность ВЭС, и их классификации, удалось сформировать новый словарь ВЭС и карту их раз- мещения, которые заменяют исходный «графический словарь», имея существенно меньший объем в совокупности. Предложенная двухэтапная обработка изображения текста позволила уве- личить степень компрессии при различных разрешениях исходного изображе- ния: на 16 % для 200 dpi; на 19 % для 300 dpi; на 6 % для 400 dpi; на 3 % для 500 dpi; на 2 % при 600 dpi, по сравнению с первым этапом обработки. Качество «графического словаря» символов при визуальном оценивании, в результате второго этапа обработки, не изменилось, что в свою очередь не влияет на вос- приятие изображения всего текста. Сравнение с лучшим в настоящее время специальным алгоритмом для сжа- тия изображений текста — JB2, входящим в формат DjVu, показало, что предла- гаемый двухэтапный алгоритм сжатия изображения текста имеет преимущество в степени сжатия данных в среднем на 25 % (табл. 5) и на 9 % лучше результатов работы [10] при наиболее часто используемых на практике разрешениях изобра- жения текста (200–600 dpi). Это является знаковой характеристикой метода и дает широкие возможности повышения информативности представления графических данных в инженерных реализациях. В.Г. Іванов, М.Г. Любарський, Ю.В. Ломоносов СТИСНЕННЯ ЗОБРАЖЕННЯ ТЕКСТУ НА ОСНОВІ ФОРМУВАННЯ І КЛАСИФІКАЦІЇ ВЕРТИКАЛЬНИХ ЕЛЕМЕНТІВ РЯДКА В ГРАФІЧНОМУ СЛОВНИКУ СИМВОЛЬНИХ ДАНИХ Запропоновано метод стиснення зображень тексту на основі формування і кла- сифікації вертикальних елементів рядка символьних даних графічного словни- ка, отриманого на першому етапі автоматичної класифікації символів. Це до- зволило сформувати новий словник вертикальних елементів рядка і карту їх ро- зміщення, які в сукупності мають менший обсяг, ніж початковий графічний словник. Запропонований двоетапний алгоритм стиснення зображення тексту має перевагу в ступені стиснення порівняно з алгоритмом JB2 (формат DjVu) близько 25 % при роздільній здатності зображення тексту від 200 до 600 dpi. 0 100 200 300 400 500 0 100 200 300 400 500 600 700 Разрешение (dpi) К о эф ф и ц и ен т сж ат и я JB2 (DjVu) Первый этап Первый и второй этапы Рис. 10 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 109 V.G. Ivanov, M.G. Lyubarsky, Yu.V. Lomonosov COMPRESSION OF IMAGE OF TEXT ON THE BASIS OF FORMING AND CLASSIFICATION OF VERTICAL ELEMENTS OF LINE IN THE GRAPHIC DICTIONARY OF CHARACTER DATA A method of compression of text images on the basis of forming and classification of vertical elements of character data line of graphic dictionary obtained on the first stage of automatic classification of characters is proposed. It allows forming the new dictionary of vertical elements of line and the map of their placing which have a less volume in an aggregate, than initial graphic dictionary. The offered two-stage algo- rithm of compression of image of text has about 25 % advantage in the degree of compression in comparison with algorithm of JB2 format of DjVu at resolution of text from 200 to 600 dpi. 1. Шлезингер М.И. Математические средства обработки изображений. — Киев : Наук. думка, 1983. — 200 с. 2. Форсайт Д., Понс Д. Компьютерное зрение. Современный подход : Пер. с англ. — М. : Ви- льямс, 2004. — 928 с. 3. Цифровое кодирование графики // ТИИЭР. Тем. выпуск. — М. : Мир, 1980. — 68, № 7. — 214 с. 4. Gupta Maya R., Stroilov A. Segmenting for wavelet compression // Data Compression Conf. (DCC). — USA, Utah, Snowbird, 2005. — http://www.cs.brandeis.edu/. 5. Кириченко Н.Ф., Полищук А.А. Метод контейнеров в распознавании рукописных математи- ческих текстов // Проблемы управления и информатики. — 2003. — № 6. — С. 54–71. 6. Иванов В.Г., Любарский М.Г., Ломоносов Ю.В. Сокращение содержательной избыточности изображений на основе классификации объектов и фона // Там же. — 2007. — № 3. — С. 93–102. 7. Иванов В.Г., Ломоносов Ю.В., Любарский М.Г. Сжатие изображений на основе автоматиче- ской и нечеткой классификации фрагментов // Там же. — 2009. — № 1 — С. 52–63. 8. Technical papers from AT&T labs. — http://djvuzone.org/techpapers/index.html. 9. Портал DjVu-сообщества. — http://www.djvu.org/. 10. Иванов В.Г., Любарский М.Г., Ломоносов Ю.В. Сжатие изображения текста на основе вы- деления символов и их классификации // Международный научно-технический журнал «Проблемы управления и информатики». — 2010. — № 6. — С. 111–122. 11. Прикладная статистика: Классификация и снижение размерности / С.А. Айвазян, В.М. Бух- штабер, И.С. Енюков и др.; Под ред. С.А. Айвазяна. — М. : Финансы и статистика, 1989. — 607 с. 12. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознава- нию. — Киев : Наук. думка, 2004. — 535 с. 13. Гонсалес Р., Вудс Р. Цифровая обработка изображений. — М. : Техносфера, 2005. — 1072 с. 14. Соломон Д. Сжатие данных, изображений и звука. — М. : Техносфера, 2004. — 368 с. 15. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. — М. : Техносфера, 2006. — 616 с. Получено 22.11.2010 http://www.djvu.org/

Сжатие изображения текста на основе формирования и классификации вертикальных элементов строки в графическом словаре символьных данных

Institution

Ähnliche Einträge