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

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

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Проблемы управления и информатики
Дата:	2010
Автори:	Иванов, В.Г., Любарский, М.Г., Ломоносов, Ю.В.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Теми:	Методы обработки информации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/210849
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Сжатие изображения текста на основе выделения символов и их классификации / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2010. — № 6. — С. 74-85. — Бібліогр.: 13 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859477874767036416
author	Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В.
author_facet	Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В.
citation_txt	Сжатие изображения текста на основе выделения символов и их классификации / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2010. — № 6. — С. 74-85. — Бібліогр.: 13 назв. — рос.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Запропоновано і досліджено метод стиснення зображень тексту на основі нової класифікуючої метрики, застосовуючи яку вдалося значно, більш ніж удвічі, зменшити кількість класів зображень символів. Це дозволило в середньому збільшити ступінь стиснення на 20 % порівняно з кращим на сьогоднішній день алгоритмом стиснення зображень тексту JB2 (DjVu). The method of compression of images of text based on new classifying metric, the use of which enabled one to decrease essentially (more than 2 times) the number of classes of characters images, is offered and investigated. It allowed to increase the degree of compression on the average by 20 % as compared with the best and the most modern algorithm of compression of text images JB2 (DjVu)
first_indexed	2026-03-12T17:24:51Z
format	Article
fulltext	© В.Г. ИВАНОВ, М.Г. ЛЮБАРСКИЙ, Ю.В. ЛОМОНОСОВ, 2010 74 ISSN 0572-2691 УДК 621.391:519.728 В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов СЖАТИЕ ИЗОБРАЖЕНИЯ ТЕКСТА НА ОСНОВЕ ВЫДЕЛЕНИЯ СИМВОЛОВ И ИХ КЛАССИФИКАЦИИ Введение Использование методов классификации является весьма перспективным и многообещающим направлением в теории и практике сжатия изображений [1–5]. Особое значение эти методы могут иметь при сжатии изображений текста, кото- рые используются для перевода печатной продукции в электронный вид. Из-за резких контрастных границ символов и их большого числа в тексте неудовлетво- рительно работают стандартные методы сжатия, основанные на ортогональных преобразованиях, в том числе на преобразовании Фурье и вейвлет-анализе. В данной работе предложен и исследован метод сжатия изображений текста, основанный на выделении связных символов (букв и знаков пунктуации) и такой их классификации, что в каждый класс попадают только изображения одного и того же символа. Сложность этой задачи вызвана шумами, возникающими при печати текста на бумаге и последующем его сканировании. Необходимо также отметить, что в качестве связных символов могут выступать такие сочетания букв, как «fh», а при невысоком разрешении сканирования — не только полные изображения букв, но и их фрагменты. Наиболее совершенный алгоритм сжатия изображений текста, который ис- пользуется в настоящее время — JB2, он как составная часть входит в известный графический формат DjVu [6, 7]. Для сжатия изображений в DjVu применяется специальная технология, разделяющая исходное изображение на три слоя: перед- ний план, задний план и черно-белую (битовую) маску. Эта маска имеет разреше- ние исходного файла, содержит изображение текста и сжимается алгоритмом JB2. Известно, что особенностью алгоритма JB2 является то, что он ищет повторяю- щиеся изображения символов и сохраняет для каждой группы только одно изоб- ражение. В изображении, полученном в результате сканирования текстового докумен- та, имеется большое количество одинаковых букв и других символов, но из-за шумов печати и сканирования может не быть ни одной пары в точности одинако- вых изображений этих букв. Поэтому естественной является следующая идея. Ес- ли научиться разбивать изображения букв и других символов на классы так, что различные изображения одного и того же символа попадут в один и тот же класс, то можно заменить все изображения из каждого класса одним изображением, например усредненным. При этом читаемость текста не только не ухудшится, но качество изображения может даже улучшиться, так как при усреднении уменьша- ются шумы печати и сканирования. Изображение текста теперь можно представить «графическим словарем» — набором усредненных изображений каждого символа, и «картой регионов» — описанием совокупности положений каждого символа в тексте. В результате размер файла изображения существенно уменьшится [8]. Следует отметить, что полное и подробное описание алгоритма JB2 как ос- новы коммерческого формата DjVu [7] в открытых публикациях отсутствует. Есть общее описание работы алгоритма DjVu, но нигде не представлена информация, каким образом обрабатывается текстовое изображение алгоритмом JB2. Существует еще один хорошо известный формат сжатия изображения текста — PDF. Данный формат предназначен для распространения полиграфической про- Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 6 75 дукции в Интернет. Кроме того, значительное количество современного профес- сионального печатного оборудования позволяет обрабатывать PDF-документы непосредственно. Цель настоящей статьи — разработка нового алгоритма сжатия текстовых изображений с открытой технологической процедурой и высокой эффективно- стью обработки. Постановка задачи Для достижения поставленной цели необходимо решить следующие основ- ные задачи:  разделить все символы, входящие в изображения текста, на классы так, что- бы в каждом классе содержались только изображения одного символа;  обеспечить минимально возможное количество этих классов. Гипотетически количество обрабатываемых классов равняется числу различ- ных символов в изображении текста, но это, как правило, недостижимо из-за шу- мов печати и сканирования, т.е. искажений формы символа при печати текста на бумаге и последующем сканировании. Шумы печати в основном вызваны диффу- зией краски, жидкой или твердой, на поверхности бумаги, вдоль хаотически рас- положенных капилляров бумаги, шумы сканирования — несовпадением контуров символа с линиями сетки сенсоров сканирования, подобно тому, как прямая наклонная линия на экране монитора отображается «ступеньками». На рис. 1 представлено три варианта из различных 257 изображений символа «n», входя- щих в изображение страницы текста формата А4, при разрешении сканирования 300 dpi. Рис. 1 Наличие указанных шумов приводит к тому, что почти все изображения какого-либо символа отличаются друг от друга. Так что найти одинаковые изоб- ражения символа намного сложнее, чем разные. Рис. 1 демонстрирует еще одну важную особенность шумов печати и скани- рования — эти шумы являются «контурными», т.е. возникают на границах чер- ных и белых областей. Эффективность предлагаемой ниже классификации в боль- шой мере основана на учете этого обстоятельства. Метод сжатия изображения текста Предлагаемый метод обработки текстовых изображений можно разделить на несколько отдельных этапов. 1. Выделение из изображения текста связных символов в виде минимальных прямоугольных областей, содержащих этот символ. 2. Предварительная классификация выделенных изображений символов по простым признакам, таким как высота, ширина и полный периметр. 3. Основная процедура — разбиение совокупности всех изображений связ- ных символов на классы, каждый из которых содержит изображения только одно- го символа. Нахождение для каждого класса его «представителя» путем усредне- ния всех изображений, входящих в этот класс. 76 ISSN 0572-2691 4. Создание «графического словаря», заключающегося в классификации со- вокупности усредненных изображений, полученных в результате основной про- цедуры, для уменьшения их числа. Построение карты регионов, описывающей со- вокупность положений каждого символа из графического словаря в изображении текста. Восстановление изображения текста происходит в один этап. Изображения символов из «графического словаря» размещаются на изобра- жении текста согласно «карте регионов». Из перечисленных этапов обработки изображения текста (сжатия и восста- новления) можно сделать вывод, что предлагаемый алгоритм является асиммет- ричен по количеству операций и соответственно по быстродействию. В дальнейшем рассматриваются черно-белые изображения текста. Условимся для определенности считать фон белым, а точки (пикселы), из которых состоят символы (буквы и знаки препинания), — черными. Выделение изображений связных символов. Нужно найти совокупности всех прямоугольных областей изображения, каждая из которых содержит один связный символ. Эти области должны быть минимальными в том смысле, что не содержат лишних точек фона. Поставленная задача решается в три этапа. На первом этапе каждая строка, т.е. полоса, ограниченная сверху и снизу го- ризонтальными линиями, охватывающими символы строки, разделяется на пря- моугольные области вертикальными линиями, имеющими ширину в одну точку и состоящими из белых (в пределах этой полосы) точек. Среди образовавшихся та- ким образом прямоугольных областей далее рассматриваются только те, которые содержат черные точки. Назовем их предварительными областями. На втором этапе в каждой предварительной области ищутся заключенные в ней связные символы. Их может быть несколько, например, буква «ё» дает три связных символа: символ «е» и две точки. Поиск осуществляется известным алго- ритмом «выращивания областей» [9], который применительно к решаемой задаче состоит в следующем. В предварительной области находим какую-либо черную точку изображения и добавляем к ней смежные (по всем восьми направлениям) черные точки. Далее для каждой найденной смежной точки добавляем новые черные точки, смежные с ними, и так далее. Процедура завершается, когда ни у одной из добавленных то- чек не остается новых смежных черных точек. Найденная совокупность точек представляет собой связный символ. Если в предварительной области остались еще черные точки, не принадлежащие найденному символу, то аналогичным об- разом ищем второй связный символ и так далее. На третьем этапе для каждого символа определяем окончательную прямо- угольную область, которая ограничена горизонтальными и вертикальными лини- ями, касающимися символа (рис. 1). Предварительная классификация. Цель предварительной классифи- кации — уменьшение числа операций сравнения при последующей основной классификации. Предварительная классификация — очень быстрая процедура, так как сравнение происходит по небольшому числу параметров, таких как шири- на символа, его высота и полный периметр. В результате, например, изображения букв «c», «e» и «o» могут войти в один класс, но изображения букв «m» ,«i» и «С» в этот класс заведомо не войдут. Векторы параметров каждого изображения символа [10], на сравнении кото- рых проводится классификация, состоят из следующих величин: H — высота символа, W — его ширина, P — полный (внешний и внутренний) периметр. Кроме того, на этом этапе подсчитывается «центр тяжести» каждого изобра- жения символа как точка, чьи координаты ( в пределах прямоугольной области) Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 6 77 являются средним арифметическим соответствующих координат черных точек, составляющих символ. Предварительная классификация проводится методом «просеивания» [9], который состоит в следующем. Выбирается произвольный элемент из класси- фицируемого множества и в один класс с ним помещаются все элементы, доста- точно близкие к нему. Далее рассматриваются только элементы, не вошедшие в первый класс. Если такие элементы найдутся, то из них произвольно выбирается какой-либо элемент и аналогичным образом строится второй класс. Этот про- цесс повторяется до тех пор, пока не будут исчерпаны все элементы исходного множества. Основным моментом алгоритма «просеивания» является выбор метрики, ко- торая конкретизирует понятие достаточной близости двух элементов. В рассмат- риваемом случае два вектора, описывающие изображения двух символов, счита- ются близкими, если попарно близки их координаты [10]. При сравнении разме- ров двух символов вычисляется разность их физических размеров, например, для высоты — величина , 100 )dpi( 21 res HHH  (1) где 21, HH — высоты первого и второго сравниваемых символов в точках (пик- селах), и )dpi(res — разрешение сканирования. Таким образом, разность высот выражается в сотых частях дюйма. Анало- гично вычисляется разность ширин W сравниваемых символов. Переход к физическим линейным размерам оправдан тем, что на отклонения высоты и ширины изображений одного и того же символа в основном влияют шумы печати, а не сканирования. Последние могут изменить линейный размер не более, чем на 1 пиксел. Экспериментально установлено, что отклонение в линей- ных размерах, вызванное расплыванием краски, находится в пределах 0,01 дюйма. Поэтому линейные размеры символов вне зависимости от разрешения и размера шрифта считаются близкими, если 1H и .1W Размер периметра символа определяется как число граничных точек в изоб- ражении символа. В основном они выражают индивидуальные особенности сим- волов, т.е. гарантированно различают, например, такие буквы, как «n» и «r». По- этому для их сравнения вводится в рассмотрение безразмерная, т.е. не зависящая ни от разрешения сканирования, ни от размера шрифта величина %,100 21 21 PP PP P   (2) где 1P и 2P — периметры сравниваемых символов. Удовлетворительная предварительная классификация получается, если пери- метры символов считать достаточно близкими при выполнении условия %.10P Такая классификация, с одной стороны, имеет небольшое число клас- сов, каждый из которых содержит изображения близких по начертанию символов. С другой стороны, изображения разных символов не попадают в один и тот же класс. Основная классификация. Полученные при предварительной классифика- ции классы изображений символов могут состоять из изображений нескольких разных символов. Цель основной классификации — разбиение этих классов на подклассы так, чтобы в каждом подклассе находились изображения только одного 78 ISSN 0572-2691 символа. Число получившихся новых классов определяет качество классифика- ции. Чем оно меньше, тем выше степень сжатия исходного изображения. Основная классификация, как и предварительная, проводится с помощью ал- горитма «просеивания». При сравнении двух изображений символов 1S и 2S с допустимыми откло- нениями ,H W и P эти изображения накладываются друг на друга с помо- щью плоскопараллельного переноса так, чтобы их центры тяжести совпадали. Да- лее подсчитываются две величины: ),( 21 SSR — количество «существенных от- личий» и ),( 21 SSD — количество общих черных точек. Первая величина — это количество несовпадающих по яркости (белое — черное) точек, которые не являются смежными для совокупности общих черных точек. Таким образом, количество существенных отличий ),( 21 SSR игнорирует несовпадения в тех точках, которые лежат на периметрах изображений и, как пра- вило, представляют собою шумы печати и сканирования. Например, при сравне- нии изображений букв «с» и «е» точки существенных отличий составляют гори- зонтальный отрезок, который имеется в букве «е» и отсутствует в букве «с». Вторая величина — нужна для обезразмеривания первой, чтобы диапазон возможных значений величины %100 ),( ),( ),( 21 21 21 SSD SSR SS  (3) для всех пар символов не менялся при изменении размера шрифта и разрешения сканирования. На рис. 2 показано, какие совокупности точек рассматриваются при сравне- нии двух трудно различимых букв: «b» и «h». Справа показаны их геометрические расположения, а слева — поясняющая схема. «b» «h» Наложение символов Множество общих черных точек — D(S1, S2) Множество точек несовпадения Точки несовпадения на контуре Существенные отличия R(S1, S2) Рис. 2 Величина  (см. (3)), является мерой близости изображений двух символов (метрикой), используемой в алгоритме «просеивания». На рис. 2 показано, что даже среди точек существенного отличия имеются одиночные точки и малые группы точек, которые носят случайный характер, вы- званный контурными шумами печати и сканирования. Действительные отличия в начертании букв «b» и «h» демонстрируют большие группы точек. Поэтому вместо определенной выше функции ),,( 21 SSR подсчитывающей количество «существенных отличий», в настоящей работе используется ее модификация, ко- торая подсчитывает это число с учетом веса [11]. Весовой коэффициент каждой точки в ),( 21 SSR тем больше, чем больше у данной точки таких же смежных то- чек. Эта функция (по-прежнему будем обозначать ее )),,( 21 SSR дает классифика- цию с меньшим числом классов, чем первоначальный ее вариант (без учета весов). Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 6 79 Таким образом, предлагаемая метрика , определяющая степень близости изображений двух символов при классификации алгоритмом «просеивания», мало чувствительна к шумам печати и сканирования. Она основана на стабильных ха- рактеристиках )( 21SSR и ),,( 21 SSD которые подавляют (не учитывают) контур- ные шумы сравниваемых символов при их наложении. После выбора метрики требуется подобрать такое ее пороговое значение ,max чтобы при выполнении условия max21 ),(  SS можно было считать, что два сравниваемых изображения 1S и 2S принадлежат одному и тому же символу. Слишком большие значения параметра max приведут к недопустимым ошибкам: будут отождествляться (попадать в один класс) изображения разных символов. Слишком малое значение приведет к тому, что некоторые изображения одного и того же символа будут квалифицироваться как изображения разных символов (и попадать в разные классы). В этом случае при классификации возникнет боль- шое число классов, что понизит эффективность сжатия изображения текста. Далее под max понимается наибольшее значение, при котором не происхо- дит недопустимых ошибок, т.е. не отождествляются отличные друг от друга сим- волы. Иначе говоря, при восстановлении изображения текста никакие символы не замещаются другими символами, как, например, в слове «ооона» вместо «сосна». Определенная так величина max — сложный нелинейный функционал от изображения всего текста, точнее, от совокупности всех изображений всех симво- лов, составляющих изображение текста. Поэтому, несмотря на безразмерность метрики , которая не зависит от размера шрифта и разрешения сканирования, функционал max заметно зависит от этих величин. Это показано в табл. 1, в ко- торой приведены значения max для различных разрешений, а также показано количество классов, получающихся при классификации с соответствующим зна- чением .max (Зависимость max от размера шрифта здесь и далее не приводится, так как из соображений подобия ясно, что увеличение размера шрифта в k раз практически эквивалентно увеличению разрешения во столько же раз.) Таблица 1 dpi ,min % ,max % Количество классов при пороге min Количество классов при пороге max Количество классов при среднеквадратическом отклонении max 600 2 70 74 72 137 500 1 38 74 71 166 400 1 31 73 71 545 300 0 26 96 95 190 200 4 7 153 145 322 Из данных, приведенных в табл. 1, вытекает, что с увеличением разрешения метрика  все меньше зависит от шумов печати и сканирования, а качество клас- сификации возрастает, т.е. количество классов уменьшается. Для сравнения в табл. 1 приведены аналогичные характеристики для метрики, общеупотребитель- ной при сравнении изображений, — среднеквадратичного отклонения . Эта мет- рика очень подходит для тех вариантов, когда случайные шумы более или менее равномерно распределены по поверхности сравниваемых изображений. Если же, как в рассматриваемом случае, шумы носят контурный характер, классифициру- ющие свойства метрики  далеки от оптимальных. Пороговое значение ,max определенное выше, слишком абстрактно. Не учтен ряд важных обстоятельств, например, вид шрифта (Arial, Times New Roman 80 ISSN 0572-2691 и т.д.), его написание (курсив, полужирный, подчеркнутый), особенности нацио- нальных алфавитов и др. Поэтому для универсального в этом смысле алгоритма необходимо пользоваться пороговым значением ,opt несколько меньшим, .max При этом, конечно, качество классификации в среднем ухудшится, но будет га- рантия, что не произойдут недопустимые ошибки: замены одних символов други- ми, алгоритм при этом становится более универсальным. На рис. 3, a–e показаны зависимости количества классов от выбора порогово- го значения  при различных разрешениях сканирования. Графики заканчиваются справа при значениях, равных max для каждого разрешения.  % Kкл 72 73 74 76 104 1 2 3 6 0 70 600 dpi εmax εmin 500 dpi εmax εmin  % Kкл 71 72 73 74 83 1 2 8 11 0 38 а б 1 2 3 31 , % 0,5 0 71 72 73 80 75 Kкл 400 dpi εmax εmin , % 95 96 1 2 3 4 5 6 26 0 Kкл 300 dpi εmax εmin в г Kкл 145 148 153 158 161 173 176 1 2 3 4 5 6 7 0 , % 300 dpi εmax εmin dpi ε 1 4 6 7 26 38 300 500 0 εопт 200 400 600 70 2 31 д е Рис. 3 Вызывает интерес случай разрешения 300 dpi. Здесь качество классификации практически не зависит от уровня порога, что свидетельствует об очень удачном выборе классифицирующей метрики. Но та же метрика при разрешениях 200 и 400 dpi (и выше) заметно увеличивает число классов и уменьшает значение поро- га. Это связано с тем, что до разрешения 300 dpi в искажении изображения симво- ла основную роль играют шумы сканирования — размер одного пиксела превос- ходит характерный размер искажений контура символа при печати. При разреше- Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 6 81 ниях, больших, 300 dpi, наоборот, размер пиксела меньше, чем характерный раз- мер искажений при печати. Поэтому при разрешении 300 dpi, когда шумы печати и сканирования дают искажения примерно одного размера, в полной мере выпол- няется принятое нами предположение о контурном характере шумов печати и сканирования. При разрешениях, больших 300 dpi, искажения в изображении символов, вносимые при печати, приобретают характер значимых отличий, так как частично находятся от действительного контура символа на расстоянии боль- ше одного пиксела. При разрешениях, меньших 300 dpi, значимые отличия изоб- ражения, например, такие как горизонтальный отрезок в букве «е» при сравнении с буквой «с», частично квалифицируются алгоритмом как контурные шумы. Отметим, что при уменьшении порога от максимального значения количе- ство классов возрастает достаточно медленно (особенно при разрешении 300 dpi и больше). Если считать допустимой классификацию, которая дает на 5 % больше классов, чем минимально возможное их число при значении порога ,max то диа- пазон для выбора порога opt довольно широк. На рис. 3, а показан этот диапазон (от ,min соответствующего 5 % увеличению числа классов, до )max при раз- личных разрешениях. Там же указан возможный выбор универсального порога ,opt равного 6 %. Это число выбрано экспериментально и показало вполне при- емлемые результаты. Кроме того, на следующем этапе алгоритма сжатия прово- дится еще одна, вторая, классификация, компенсирующая неоптимальность первой. Завершает третий этап нахождение усредненных изображений в каждом классе. После этого все изображения символов можно отбросить, остается только совокупность «представителей» каждого класса — усредненные изображения. Процедура усреднения состоит в наложении друг на друга всех изображений класса при совмещенных «центрах тяжести» каждого изображения, вычисления среднего значения яркости для каждой точки и округления. На рис. 4 иллюстри- руется процесс усреднения для трех классов изображений одного и того же сим- вола «n». Черные точки означают, что среднее значение яркости в них равно 0, серые — что среднее значение меньше или равно 0,5, а светлые — больше 0,5. При округлении черные и серые точки превращаются в черные, а светлые — в бе- лые. Результат показан на рис. 5 Рис. 4 Рис. 5 Создание графического словаря. В полученном на предыдущем этапе се- мействе усредненных изображений по-прежнему имеются разные изображения одних и тех же символов, хотя и в значительно меньшем количестве, чем до клас- сификации, например, три различных изображения символа «n», приведенные на рис. 5. Ситуацию можно улучшить, применив еще одну классификацию, призван- ную отождествить изображения одного и того же символа. 82 ISSN 0572-2691 Для этой классификации, как и для предыдущей, используется нечувстви- тельная к контурным шумам метрика  с тем же порогом ,opt но алгоритм клас- сификации выбирается другим. Дело в том, что теперь изображения одного сим- вола очень близки друг к другу: случайная компонента изображения в значитель- ной мере подавлена (сравните рис. 5 и рис. 1, где приведены изображения символов до обработки). Поэтому существенно меньше опасность спутать изоб- ражения двух разных символов. Это позволяет применить алгоритм «наращива- ния областей», который в простейшем случае использовался на втором этапе. Алгоритм «наращивания областей» состоит в том, что на первом шаге, начи- ная с произвольно выбранного элемента классифицируемого множества, к его классу присоединяются все достаточно близкие элементы. На втором шаге к вновь присоединенным элементам добавляются все элементы, близкие к ним. Процесс «наращивания» повторяется до тех пор, пока на каком-то шаге не ока- жется новых элементов, которые можно было бы присоединить. Далее все элементы «выращенного» класса исключаются из классифицируе- мого множества и «выращивается» следующий класс. Алгоритм заканчивает ра- боту, когда в классифицируемом множестве не остается ни одного элемента. После получения новых классов изображения в каждом из них усредняют- ся [12], и получившийся набор изображений представляет собой «графический словарь». В результате на рис. 6 показано единственное изображение символа «n», вошедшее в графический словарь. Можно утверждать, что контурные шумы практически от- сутствуют и внешний вид символа значительно улучшился по сравнению с вариантами его изображения в исходном тексте. В табл. 2 для различных разрешений приводятся количе- ства классов после основной и повторной классификаций. Для сравнения приведено количество классов после классифика- ции алгоритмом JB2 (формат DjVu в режиме Bitonal). Таблица 2 Разрешение изображения текста (dpi) Количество классов в исходном изображении Количество классов после основной классификации %6opt  Количество классов после второй классификации %6opt  Количество классов после классификации алгоритмом JB2 600 3558 197 72 314 500 3557 137 72 259 400 3557 130 71 199 300 3545 122 95 235 200 3890 237 148 451 Данные, приведенные в таблице, демонстрируют достаточно высокую эф- фективность как первой, так и повторной классификаций и несомненные пре- имущества предлагаемого алгоритма перед алгоритмом JB2 . Анализ количественных показателей сжатия изображений текста Объем графического файла, который сжат каким-либо алгоритмом, основан- ным на классификации, состоит из объема, занимаемого «графическим словарем», и объема «карты регионов». Первый объем пропорционален количеству классов, возникших при классификации, второй зависит от количества классов логариф- мически (разрядность каждого символа уменьшается на 1 бит при уменьшении количества классов вдвое). Поэтому можно ожидать, что предложенный в этой статье алгоритм классификации более эффективен, чем алгоритм JB2, дающий при всех разрешениях сканирования в два с половиною раза больше классов. Однако все современные методы сжатия данных комплексные, т.е. содержат последовательность алгоритмов компрессии данных. Другими словами, и «графи- Рис. 6 Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 6 83 ческий словарь», и «карту регионов» можно дополнительно сжать какими-то дру- гими методами. В нашем случае для сжатия «графического словаря» последова- тельно применяются алгоритм группового кодирования RLE (Run-length encoding) и модификация словарного метода компрессии LZ77 [13] – LZMA (Lempel-Ziv- Markov chain-Algorithm). Сжатие «карты регионов» проводится только с помощью метода LZMA. Результаты приведены в табл. 3. Кроме того, для сравнения приве- дены аналогичные данные для сжатого графического формата JPEG 2000, форма- та PDF и алгоритма JB2. В качестве исходного изображения была выбрана страница текста на англий- ском языке, набранная шрифтом Times New Roman, кегль 12 pt с межстрочным интервалом 1. Изображения этой страницы формировались с помощью планшет- ного сканера при разрешениях 200, 300, 400, 500 и 600 dpi, глубина цвета 1 бит, формат *.bmp. Степень компрессии оценивалась в абсолютных величинах (коли- честве килобайт (кбайт) после сжатия и относительных величинах (коэффициент сжатия comp(K — отношение объема данных до и после сжатия). Как видно из приведенных данных (табл. 3), результаты компрессии у пред- лагаемого в этой статье алгоритма и алгоритма JB2 наиболее близки и намного превышают полученные другими методами. Оба алгоритма в отличие от осталь- ных демонстрируют стабильную степень компрессии при различных разрешениях сканирования. Это позволяет сделать вывод о совпадении основных идей, зало- женных в эти алгоритмы, хотя методы, реализованные в JB2, неизвестны. Таблица 3 Разрешение сканирования (dpi) Исходный размер файла (кбайт) Размеры файла после сжатия различными методами (кбайт) / коэффициент сжатия Формат JPEG 2000 Формат PDF JB2 в форма- те DjVu Предлагаемый алгоритм 200 505,3 132,8 / 3,8 61,4 / 8,2 9,6 / 52,6 8,1 / 62,3 300 1080,2 288,6 / 3,74 96,1 / 11,2 8,7 / 124,1 8,0 / 135,0 400 2003,9 532,4 / 3,76 119,6 / 16,7 9,9 / 202,4 8,0 / 250,4 500 3111,2 830,0 / 3,75 148,9 / 20,9 11,4 / 272,9 8,5 / 366,0 600 4498,0 1200,3 / 3,75 178,9 / 25,1 13,6 / 330,7 9,7 / 463,7 По сравнению с алгоритмом JB2 использование предложенного алгоритма позволяет уменьшить объемы выходных данных на 15,6 % при 200 dpi, 8 % при 300 dpi, 19 % при 400 dpi, 25 % при 500 dpi и 28,6 % при 600 dpi соответственно. Заключение Используя контурный характер шумов, вносимых в изображения символов (букв и знаков препинания) при печати и последующем сканировании, в работе предложена новая метрика в пространстве черно-белых изображений символов, которая позволяет хорошо различать эти символы даже при наличии сильных шумов печати и сканирования. Соответственно двухэтапная классификация изоб- ражений символов, использующая эту метрику, дает число классов, близкое к ми- нимально возможному. Это позволило создать эффективный алгоритм сжатия изображений текста, основанный на выделении изображения символов и даль- нейшей их классификации. Сравнение с лучшим в настоящее время специальным алгоритмом для сжа- тия изображений текста — JB2, включенным в формат DjVu, показало, что, ско- рее всего, оба алгоритма построены на одинаковых принципах (отсутствие по- дробных сведений об алгоритме JB2 не позволяет непосредственно сравнить эти алгоритмы). Однако качество классификации у предлагаемого в этой работе ме- тода значительно выше, чем у алгоритма JB2. Количество классов, получающееся в результате предложенной классификации, более чем в два раза меньше при всех 84 ISSN 0572-2691 разрешениях сканирования. Это основная качественная характеристика метода, которая дает широкие возможности повышения информативности этого алгорит- ма в инженерных внедрениях. Реализованный в работе алгоритм позволяет уменьшить размеры выходных данных, по сравнению с алгоритмом JB2 для всех разрешений сканирования (от 8 % до 28,6 % при соответствующих разрешениях, (см. табл. 3)), что в среднем составляет около 20 %. В.Г. Іванов, М.Г. Любарський, Ю.В. Ломоносов СТИСНЕННЯ ЗОБРАЖЕННЯ ТЕКСТУ НА ОСНОВІ ВИДІЛЕННЯ СИМВОЛІВ І ЇХ КЛАСИФІКАЦІЇ Запропоновано і досліджено метод стиснення зображень тексту на основі нової класифікуючої метрики, застосовуючи яку вдалося значно, більш ніж удвічі, зменшити кількість класів зображень символів. Це дозволило в середньому збільшити ступінь стиснення на 20 % порівняно з кращим на сьогоднішній день алгоритмом стиснення зображень тексту JB2 (DjVu). V.G. Ivanov, M.G. Lyubarskiy, Yu.V. Lomonosov COMPRESSION OF IMAGE OF TEXT ON THE BASIS OF SELECTION OF CHARACTERS AND THEIR CLASSIFICATION The method of compression of images of text based on new classifying metric, the use of which enabled one to decrease essentially (more than 2 times) the number of classes of characters images, is offered and investigated. It allowed to increase the degree of compression on the average by 20 % as compared with the best and the most modern algorithm of compression of text images JB2 (DjVu) 1. Земсков В.Н., Ким И.С. Сжатие изображений на основе автоматической классификации // Изв. вузов. Электроника. — 2003. — № 2. — С. 50–56. 2. Gupta Maya R., Stroilov A. Segmenting for wavelet compression // Data Compression Confer- ence (DCC). — USA, Utah, Snowbird, 2005. — http://www.cs.brandeis.edu/. 3. Шлезингер М.И. Математические средства обработки изображений. — Киев : Наук. думка, 1983. — 200 с. 4. Иванов В.Г., Любарский М.Г., Ломоносов Ю.В. Сокращение содержательной избыточности изображений на основе классификации объектов и фона // Проблемы управления и инфор- матики. — 2007. — № 3. — С. 93–102. 5. Иванов В.Г., Ломоносов Ю.В., Любарский М.Г. Сжатие изображений на основе автоматиче- ской и нечеткой классификации фрагментов // Там же. — 2009. — № 1. — С. 52–63. 6. Technical papers from AT&T labs. — http://djvuzone.org/techpapers/index.html. 7. Портал DjVu-сообщества. — http://www.djvu.org/. 8. Автоматический анализ сложных изображений [Сборник переводов] / Под ред. Э.М. Бра- верманна. — М. : Мир, 1969. — 308 с. 9. Прикладная статистика: Классификация и снижение размерности: [Справочник] / С.А. Ай- вазян, В.М. Бухштабер, И.С. Енюков и др.; Под ред. С.А. Айвазяна. — М. : Финансы и ста- тистика, 1989. — 607 с. 10. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознава- нию. — Киев : Наук. думка, 2004. — 535 с. 11. Цифровое кодирование графики. Тематический выпуск. ТИИЭР. — М. : Мир, 1980. — Т. 68, № 7. — 214 с. 12. Бутаков Е.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. — М. : Ра- дио и связь, 1987. — 240 с. 13. Сэломон Д. Сжатие данных, изображений и звука. — Москва : Техносфера, 2004. — 368 с. http://www.cs.brandeis.edu/ http://www.djvu.org/ Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 6 85 Получено 19.01.2010
id	nasplib_isofts_kiev_ua-123456789-210849
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Russian
last_indexed	2026-03-12T17:24:51Z
publishDate	2010
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. 2025-12-18T10:04:25Z 2010 Сжатие изображения текста на основе выделения символов и их классификации / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2010. — № 6. — С. 74-85. — Бібліогр.: 13 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210849 621.391:519.728 10.1615/JAutomatInfScien.v42.i11.50 Запропоновано і досліджено метод стиснення зображень тексту на основі нової класифікуючої метрики, застосовуючи яку вдалося значно, більш ніж удвічі, зменшити кількість класів зображень символів. Це дозволило в середньому збільшити ступінь стиснення на 20 % порівняно з кращим на сьогоднішній день алгоритмом стиснення зображень тексту JB2 (DjVu). The method of compression of images of text based on new classifying metric, the use of which enabled one to decrease essentially (more than 2 times) the number of classes of characters images, is offered and investigated. It allowed to increase the degree of compression on the average by 20 % as compared with the best and the most modern algorithm of compression of text images JB2 (DjVu) ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Сжатие изображения текста на основе выделения символов и их классификации Стиснення зображення тексту на основі виділення символів і їх класифікації Compression of image of text on the basis of selection of characters and their classification Article published earlier
spellingShingle	Сжатие изображения текста на основе выделения символов и их классификации Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. Методы обработки информации
title	Сжатие изображения текста на основе выделения символов и их классификации
title_alt	Стиснення зображення тексту на основі виділення символів і їх класифікації Compression of image of text on the basis of selection of characters and their classification
title_full	Сжатие изображения текста на основе выделения символов и их классификации
title_fullStr	Сжатие изображения текста на основе выделения символов и их классификации
title_full_unstemmed	Сжатие изображения текста на основе выделения символов и их классификации
title_short	Сжатие изображения текста на основе выделения символов и их классификации
title_sort	сжатие изображения текста на основе выделения символов и их классификации
topic	Методы обработки информации
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/210849
work_keys_str_mv	AT ivanovvg sžatieizobraženiâtekstanaosnovevydeleniâsimvoloviihklassifikacii AT lûbarskiimg sžatieizobraženiâtekstanaosnovevydeleniâsimvoloviihklassifikacii AT lomonosovûv sžatieizobraženiâtekstanaosnovevydeleniâsimvoloviihklassifikacii AT ivanovvg stisnennâzobražennâtekstunaosnovívidílennâsimvolívííhklasifíkacíí AT lûbarskiimg stisnennâzobražennâtekstunaosnovívidílennâsimvolívííhklasifíkacíí AT lomonosovûv stisnennâzobražennâtekstunaosnovívidílennâsimvolívííhklasifíkacíí AT ivanovvg compressionofimageoftextonthebasisofselectionofcharactersandtheirclassification AT lûbarskiimg compressionofimageoftextonthebasisofselectionofcharactersandtheirclassification AT lomonosovûv compressionofimageoftextonthebasisofselectionofcharactersandtheirclassification

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

Репозитарії

Схожі ресурси