Buchumschlag

Использование вейвлет-преобразования при локализации последовательностей символов

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2009
Hauptverfasser: Антощук, С.Г., Николенко, А.А., Ткаченко, Е.В., Бабилунга, О.Ю.
Format: Artikel
Sprache:Russisch
Veröffentlicht: Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:
Интеллектуальный анализ данных
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/8141
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:Использование вейвлет-преобразования при локализации последовательностей символов / С.Г. Антощук, А.А. Николенко, Е.В. Ткаченко, О.Ю. Бабилунга // Штучний інтелект. — 2009. — № 4. — С. 23-29. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859728721096736768
author Антощук, С.Г.
Николенко, А.А.
Ткаченко, Е.В.
Бабилунга, О.Ю.
author_facet Антощук, С.Г.
Николенко, А.А.
Ткаченко, Е.В.
Бабилунга, О.Ю.
citation_txt Использование вейвлет-преобразования при локализации последовательностей символов / С.Г. Антощук, А.А. Николенко, Е.В. Ткаченко, О.Ю. Бабилунга // Штучний інтелект. — 2009. — № 4. — С. 23-29. — Бібліогр.: 5 назв. — рос.
collection DSpace DC
description В статье предложен метод автоматического определения масштаба вейвлет-преобразования при локализации квазипериодических последовательностей (текстур, областей с символьной информацией и т.д.) путем анализа функции энергии коэффициентов вейвлет-преобразования. Реализация предложенного метода при разработке приложений, связанных с локализацией и распознаванием символьной информации, повысила универсальность таких систем за счет повышения точности локализации символьной информации путем автоматизации выбора масштаба вейвлет-преобразования. У статті запропоновано метод автоматичного визначення масштабу вейвлет-перетворення при локалізації квазіперіодичних послідовностей (текстур, областей з символьною інформацією (СІ) тощо) шляхом аналізу функції енергії коефіцієнтів вейвлет-перетворення. Реалізація методу при розробці додатків, які пов’язані з локалізацією та розпізнаванням символьної інформації, підвищила універсальність таких систем за рахунок збільшення точності локалізації СІ шляхом автоматизації вибору масштабу вейвлет-перетворення. Method of automatically determining wavelet transform scale on the base of analyzing the function of the energy wavelet transform coefficients is proposed. It is used for localization of quasiperiodic sequences (patterns, areas with character information, etc.). The proposed method is used in image processing systems related to the localization and recognition of the symbolic information. It is allowed to increase versatility of such systems by improving the accuracy localization of the symbolic information by automating choice of scale wavelet transform.
first_indexed 2025-12-01T11:52:54Z
format Article
fulltext «Штучний інтелект» 4’2009 23 2А УДК 004.932.001.57 C.Г. Антощук, А.А. Николенко, Е.В. Ткаченко, О.Ю. Бабилунга Одесский национальный политехнический университет, г. Одесса, Украина anatolyn@ukr.net Использование вейвлет-преобразования при локализации последовательностей символов В статье предложен метод автоматического определения масштаба вейвлет-преобразования при локализации квазипериодических последовательностей (текстур, областей с символьной информацией и т.д.) путем анализа функции энергии коэффициентов вейвлет-преобразования. Реализация предложенного метода при разработке приложений, связанных с локализацией и распознаванием символьной информации, повысила универсальность таких систем за счет повышения точности локализации символьной информации путем автоматизации выбора масштаба вейвлет-преобразования. Введение Для многих практических приложений, связанных с анализом изображений, акту- альна задача поиска характерных фрагментов, содержащих последовательность симво- лов, которую построчно (постолбцово) можно рассматривать как квазипериодическую последовательность импульсов [1]. Задача поиска таких характерных фрагментов часто сводится к нахождению границ квазипериодических последовательностей, что позво- ляет локализовать необходимый фрагмент на изображении. Квазипериодические последовательности в строке изображения рассматриваются как характерные области с отличительными пространственно-частотными свойствами. Поэтому для их локализации целесообразно использовать вейвлет-преобразование (ВП) [2], которое представляет собой свертку исходного сигнала с импульсной характе- ристикой определенного вейвлет-фильтра (вейвлета) заданного масштаба. Изменение масштаба ВП приводит к изменению его частотно-избирательных свойств. Выбор необходимого масштаба проводится с учетом априорной информации и осуществля- ется разработчиком субъективно на основании полученных результатов, требует кор- рекции при изменении исходных данных, что ограничивает возможности построения систем автоматического анализа изображений. Поэтому задача адаптивного определения масштаба ВП, которая рассматривается в данной работе, является актуальной. Целью данной работы является разработка метода адаптивной локализации квазипериодической последовательности символов на изображениях с использованием вейвлет-преобразования. Для решения задачи локализации квазипериодических после- довательностей могут применяться действительные вейвлеты, заданные в виде нечетных симметричных функций )()( tt  , имеющие компактный или эффективный носитель. Выбор и реализация базиса вейвлет-преобразования В качестве базисных функций ВП рассмотрены вейвлеты Хаара, Гаусса, «расще- пленная» функция Гаусса, ограниченный синус, функции гиперболического вейвлет- преобразования (ГВП) (табл. 1), где s – масштабный уровень,  ,  – некоторые Антощук C.Г., Николенко А.А., Ткаченко Е.В., Бабилунга О.Ю. «Искусственный интеллект» 4’2009 24 2А параметры преобразования. Эти функции могут использоваться в качестве базисных вейвлет-преобразования, поскольку удовлетворяют необходимым требованиям (лока- лизации, допустимости, осцилляции и ограниченности) [2], [3]. Для оценки частотно- избирательных свойств базисных функций выполнен анализ их амплитудно-частотных характеристик, в результате которого установлено, что значение частоты в точке экстре- мума для всех функций определяется зависимостью s k extr  , (1) где s – масштабный уровень, k – некоторая константа, определяемая типом базисной функции. Таблица 1– Частотно-избирательные свойства базисных вейвлет-функций Вейвлет Функция Модуль преобразования Фурье extr , ,maxs f nd Хаара     0, , , x s x s sign x x s        24sin 2, s s           2.33 s 120max 0.07 15 s c f Гцd n     Гаусса   21, exp 22 2 x xx s s s               2 2 2 2, s s s e       1 s 12.0max 0.16 9 s c f Гцd n     «Расщеплен- ная» функция Гаусса     2 , exp 22 2 sign x xx s s                     2 0 2 2 22 2 s z s dzees, s .311 114max 0.21 25 s c f Гцd n     Ограничен- ный синус   0, , sin , x s x s x s x s s                   2, sin2 21 ss s s        0.838 s 1.5max 0.08 9 s c f Гцd n     Функция ГВП   0, 1 ,11 , 0, 1 ,11 x s s xx sx s t x sx s                              sin , 2 1 s x s s dx s x           2.84 s 6.9maxs c  8, 1   0.08 16 f Гцd n   Использование вейвлет-преобразования при локализации последовательностей… «Штучний інтелект» 4’2009 25 2А Таким образом, все анализируемые базисные вейвлет-функции имеют похожие частотно-избирательные свойства, но значение частоты в точке экстремума на одинако- вом масштабе отличается. Это необходимо учитывать при выборе базиса для выделения структурных особенностей изображения с разной степенью детализации. Вторым важным вопросом, связанным с непрерывным ВП, является его реали- зация при обработке изображений. При компьютерной обработке изображение рассма- тривается как двумерный массив. Причем двумерные операции обработки могут быть заменены одномерными по строкам и по столбцам (строка либо столбец изображения может рассматриваться как дискретная последовательность  nf ). Непрерывное ВП неко- торой дискретной последовательности определяется как свертка этой последовательности с базисной функцией 0 , которая соответствующим образом перенормируется с масштабом s и сдвигается по пространственной шкале на интервал xn :               s xnnfs,nW N n * n 1 0 . Таким образом, изменение масштабного уровня s непрерывного вейвлета с шагом дискретизации x эквивалентно дискретизации начального вейвлета с новым шагом s xxs   . Полученный в результате дискретный вейвлет является масштабированным начальным вейвлетом. При таком подходе к определению масштаба вейвлета дискретный вейвлет является аппроксимацией непрерывного вейвлета и совпадает с ним при s ( 0 sx ), а аналогом масштабного коэффициента s выступает изменяющееся ко- личество отсчетов импульсной характеристики, т.е. длина дискретного вейвлет-фильтра. Тогда, изменяя масштабный коэффициент s и величину сдвига вейвлетной функции, можно локализовать любые особенности изображения в пространстве масштабов. При выборе шага дискретизации x стараются его максимизировать (или миними- зировать частоту дискретизации), это обусловлено желанием снизить количество арифме- тических операций, требуемых для реализации алгоритма, которое пропорционально числу отсчетов, подвергаемых обработке. Таким образом, правильный выбор частоты дискретизации позволяет сохранить свойства непрерывного вейвлет-преобразования при дискретной реализации и определяет быстродействие алгоритма преобразования. Непосредственно применить теорему Котель- никова не представляется возможным, поскольку базисные функции ВП имеют конечный носитель (т.е. удовлетворяют условию локализации) и неограниченный спектр. Поэтому для определения максимальной частоты max в спектре базисной функции найдем вклад частот от 0 до max в энергию сигнала, т.е. положим 1max  E E , где maxE – энергия сигнала в полосе частот max0  , E – полная энергия сигнала, имеем         ,,2,,€ 2 1 0 222        dxsxdxsxdsE          .ds,€ds,€E maxmax max max         0 22 1 2 1 Антощук C.Г., Николенко А.А., Ткаченко Е.В., Бабилунга О.Ю. «Искусственный интеллект» 4’2009 26 2А Тогда уравнение для определения max имеет вид:       0 2 0 2 2 dxs,xds,€ max . (2) Решая (2) для конкретной базисной функции, можно найти max . Например, если для ГВП         2 2 2 0 , , 1 111 s sdxx s dx s s sx s                      уравнение (2) приобретает вид        max 2 22 0 sin4 2 1 1 1 s x s ss dx d s x s s s                     или        .sss sddx xs xsinmax s 11210 2           (3) При 950. , 8 и 1 численно решая (3), находим значение 866.smax  с-1. Отсюда можно определить период дискретизации Т, частоту дискретизации fd и минимальное количество точек дискретизации базисной функции (порядок n дискретного фильтра, реализующего ВП) max T    , 2 sn T   и T f d 1  . Результаты аналогичных расчетов для остальных базисных функций приведены в табл. 1. При полученных значениях частота дискретизации df является рациональной, т.е. достаточно высокой для того, чтобы не возникало наложение спектров дискретизирован- ных функций. Основные свойства непрерывных функций сохраняются. Эксперименты показали, что амплитудно-частотные характеристики соответствующей непрерывной функции и ее дискретной реализации достаточно близки. Среднеквадратическая ошибка при этом (ошибка аппроксимации) не превышала 5%. Методика выбора масштаба вейвлет-преобразования Анализ амплитудно-частотных характеристик этих функций показал, что значение частоты, соответствующей экстремуму АЧХ, определяется выражением (1) и обратно пропорционально величине масштаба. Это свойство предлагается использовать при локализации квазипериодических последовательностей. Исследован характер функции энергии коэффициентов ВП в зависимости от его масштаба (длины вейвлет-фильтра) (рис. 1). Было установлено, что такая зависимость для квазипериодических объектов имеет несколько экстремальных точек (не менее двух – локальный максимум и мини- мум), в то время как аналогичная зависимость для однородного объекта имеет монотон- Использование вейвлет-преобразования при локализации последовательностей… «Штучний інтелект» 4’2009 27 2А но возрастающий характер. Значение масштаба, соответствующее первому локальному максимуму, характеризуется резонансом вейвлета и последовательности (совпадением периодов) и позволяет зафиксировать необходимый масштаб для обнаружения отдель- ных элементов данной последовательности. При достаточно большом масштабе s вей- влет-преобразования (превышающем значение, соответствующее последнему локаль- ному минимуму) квазипериодическая последовательность воспринимается как однород- ный объект, отдельные импульсы последовательности становятся неразличимы. Поэтому для обнаружения границ последовательности можно использовать значение масштаба, превышающее величину, при которой наблюдается последний локальный минимум. Следует заметить, что при дальнейшем увеличении масштаба вид зависимости энергии становится монотонно возрастающим и стремится к некоторому предельному значению, определяемому типом базисной функции и количеством импульсов в квазипериоди- ческой последовательности. Рисунок 1 – Зависимость энергии вейвлет-преобразования от масштаба ВП: а), в) – графики исходных сигналов одиночного объекта и последовательности, б), г) – соответствующие зависимости энергии ВП от масштаба На рис. 1 представлена нормированная зависимость энергии ВП (для вейвлета Хаара) квазипериодической последовательности Enorm от длины вейвлет-фильтра L = 2 s + 1 (s – масштаб ВП). Зависимость энергии от длины вейвлета имеет харак- терный первый максимум, координата которого определяется периодом следования импульсов, а последующие максимумы повторяются через интервал, равный удвоенному периоду следования импульсов. Следовательно, по количеству локальных экстремумов можно оценить количество импульсов в последовательности. Исследование зависимости энергии ВП от масштаба для разных базисных функций показало, что многоэкстремаль- ный характер этой зависимости наблюдается только при наличии значительных боко- вых лепестков в их АЧХ (вейвлет Хаара, гиперболическое вейвлет-преобразование, ограниченный синус [3]). Для «гладких» вейвлет-функций многоэкстремальность не наблюдается. Метод адаптивно-структурной локализации На базе проведенных исследований был предложен метод адаптивно-структурной локализации с целью интерпретации изображений в системах автоматической обра- ботки. Проиллюстрируем его на примере решения задачи локализации символьной информации (СИ). Структурная схема метода адаптивно-структурной локализации СИ на основе разработанной методики выбора масштаба представлена на рис. 2. Антощук C.Г., Николенко А.А., Ткаченко Е.В., Бабилунга О.Ю. «Искусственный интеллект» 4’2009 28 2А Рисунок 2 – Структурная схема метода адаптивно-структурной локализации СИ Для реализации метода выполняются следующие этапы: 1. Вычисляется зависимость значения энергии ВП на разных масштабах (масш- табных уровнях) s, обработки изображения, демонстрирующие работу метода адап- тивной проводится ее анализ и делаются выводы о присутствии СИ; по положению экстремумов зависимости определяются необходимые масштабные уровни ВП. 2. Производится ВП изображения на выбранном масштабном уровне. 3. Определяются левая и правая границы СИ по положению экстремумов ВП. 4. Выполняется локализация СИ разных размеров. При таком подходе на каждой итерации происходит подстройка масштабного уровня с целью достижения экстремума функции энергии, что может быть осуществ- лено итеративными методами поиска в пространстве ВП [4], [5]. Результаты компьютерной локализации СИ, приведены на рис. 3. Исходное изображение содержит квазипериодические последовательности (участки СИ с разными шрифтами), однородный объект и фон. Предложенный метод позво- лил при адаптивном выборе масштаба локализовать характерные фрагменты – области символов различной величины. Рисунок 3 – Примеры выделения областей символьных надписей с разными размерами шрифта на изображении Использование вейвлет-преобразования при локализации последовательностей… «Штучний інтелект» 4’2009 29 2А Выводы Предложен метод автоматического определения масштаба вейвлет-преобразования при локализации квазипериодических последовательностей (текстур, областей с символь- ной информацией и т.д.) путем анализа функции энергии коэффициентов ВП. Показано, что при этом базисные функции ВП должны быть симметричными и нечетными. Прове- денные исследования легли в основу метода адаптивно-структурной локализации квази- периодических последовательностей на изображении. Исследования помехоустойчивости метода адаптивно-структурной локализации СИ на изображениях показало его работо- способность при воздействии гауссовского шума с отношением сигнал/шум 5 и более (по мощности). Реализация предложенного метода при разработке приложений, связан- ных с локализацией и распознаванием символьной информации, повысила универсаль- ность таких систем за счет повышения точности локализации СИ путем автоматизации выбора масштаба ВП. Литература 1. Антощук С.Г. Адаптивна локалізація символьних написів на зображеннях методом вейвлет- аналізу / С.Г. Антощук, О.Ю. Бабілунга, А.О. Ніколенко, О.В. Ткаченко // Вісник ЖІТІ. – 2008. – № 4. – С. 125-130. 2. Малла С. Вейвлеты в обработке сигналов / Малла С. – М. : Мир, 2005. – 671 с. 3. Антощук С.Г. Анализ базисных функций вейвлет-преобразования при мультимасштабном контурном представлении изображений / С.Г. Антощук, А.А. Николенко, Е.В. Ткаченко // Електромашино- будування та електрообладнання. – 2009. – Вип. 72. – С. 15-19. 4. Антощук С.Г. Контурная сегментация полутоновых изображений методами вейвлет-анализа / С.Г. Ан- тощук, О.Ю. Бабилунга, А.А. Николенко, Т.А. Буряк // Искусственный интеллект. – 2007. – № 3. – С. 187-192. 5. Антощук С.Г. Повышение быстродействия контурного описания полутоновых изображений при- ближенными методами / С.Г. Антощук, О.Ю. Бабилунга, А.А. Николенко // Труды Одесс. политехн. ун-та. – Одесса, 2007. – Вып. 1(27). – С. 118-123. C.Г. Антощук, А.О. Ніколенко, О.В. Ткаченко, О.Ю. Бабілунга Використання вейвлет-перетворення при локалізації послідовностей символів У статті запропоновано метод автоматичного визначення масштабу вейвлет-перетворення при локалізації квазіперіодичних послідовностей (текстур, областей з символьною інформацією (СІ) тощо) шляхом аналізу функції енергії коефіцієнтів вейвлет-перетворення. Реалізація методу при розробці додатків, які пов’язані з локалізацією та розпізнаванням символьної інформації, підвищила універсальність таких систем за рахунок збільшення точності локалізації СІ шляхом автоматизації вибору масштабу вейвлет-перетворення. S.G. Antoshchuk, A.A. Nikolenko, E.V. Tkachenko, O.Yu. Babilunga Localization of Symbolic Sequences Using Wavelet Transforms Method of automatically determining wavelet transform scale on the base of analyzing the function of the energy wavelet transform coefficients is proposed. It is used for localization of quasiperiodic sequences (patterns, areas with character information, etc.). The proposed method is used in image processing systems related to the localization and recognition of the symbolic information. It is allowed to increase versatility of such systems by improving the accuracy localization of the symbolic information by automating choice of scale wavelet transform. Статья поступила в редакцию 30.06.2009.
id nasplib_isofts_kiev_ua-123456789-8141
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1561-5359
language Russian
last_indexed 2025-12-01T11:52:54Z
publishDate 2009
publisher Інститут проблем штучного інтелекту МОН України та НАН України
record_format dspace
spelling Антощук, С.Г.
Николенко, А.А.
Ткаченко, Е.В.
Бабилунга, О.Ю.
2010-05-13T09:00:58Z
2010-05-13T09:00:58Z
2009
Использование вейвлет-преобразования при локализации последовательностей символов / С.Г. Антощук, А.А. Николенко, Е.В. Ткаченко, О.Ю. Бабилунга // Штучний інтелект. — 2009. — № 4. — С. 23-29. — Бібліогр.: 5 назв. — рос.
1561-5359
https://nasplib.isofts.kiev.ua/handle/123456789/8141
004.932.001.57
В статье предложен метод автоматического определения масштаба вейвлет-преобразования при локализации квазипериодических последовательностей (текстур, областей с символьной информацией и т.д.) путем анализа функции энергии коэффициентов вейвлет-преобразования. Реализация предложенного метода при разработке приложений, связанных с локализацией и распознаванием символьной информации, повысила универсальность таких систем за счет повышения точности локализации символьной информации путем автоматизации выбора масштаба вейвлет-преобразования.
У статті запропоновано метод автоматичного визначення масштабу вейвлет-перетворення при локалізації квазіперіодичних послідовностей (текстур, областей з символьною інформацією (СІ) тощо) шляхом аналізу функції енергії коефіцієнтів вейвлет-перетворення. Реалізація методу при розробці додатків, які пов’язані з локалізацією та розпізнаванням символьної інформації, підвищила універсальність таких систем за рахунок збільшення точності локалізації СІ шляхом автоматизації вибору масштабу вейвлет-перетворення.
Method of automatically determining wavelet transform scale on the base of analyzing the function of the energy wavelet transform coefficients is proposed. It is used for localization of quasiperiodic sequences (patterns, areas with character information, etc.). The proposed method is used in image processing systems related to the localization and recognition of the symbolic information. It is allowed to increase versatility of such systems by improving the accuracy localization of the symbolic information by automating choice of scale wavelet transform.
ru
Інститут проблем штучного інтелекту МОН України та НАН України
Интеллектуальный анализ данных
Использование вейвлет-преобразования при локализации последовательностей символов
Localization of Symbolic Sequences Using Wavelet Transforms
Використання вейвлет-перетворення при локалізації послідовностей символів
Article
published earlier
spellingShingle Использование вейвлет-преобразования при локализации последовательностей символов
Антощук, С.Г.
Николенко, А.А.
Ткаченко, Е.В.
Бабилунга, О.Ю.
Интеллектуальный анализ данных
title Использование вейвлет-преобразования при локализации последовательностей символов
title_alt Localization of Symbolic Sequences Using Wavelet Transforms
Використання вейвлет-перетворення при локалізації послідовностей символів
title_full Использование вейвлет-преобразования при локализации последовательностей символов
title_fullStr Использование вейвлет-преобразования при локализации последовательностей символов
title_full_unstemmed Использование вейвлет-преобразования при локализации последовательностей символов
title_short Использование вейвлет-преобразования при локализации последовательностей символов
title_sort использование вейвлет-преобразования при локализации последовательностей символов
topic Интеллектуальный анализ данных
topic_facet Интеллектуальный анализ данных
url https://nasplib.isofts.kiev.ua/handle/123456789/8141
work_keys_str_mv AT antoŝuksg ispolʹzovanieveivletpreobrazovaniâprilokalizaciiposledovatelʹnosteisimvolov
AT nikolenkoaa ispolʹzovanieveivletpreobrazovaniâprilokalizaciiposledovatelʹnosteisimvolov
AT tkačenkoev ispolʹzovanieveivletpreobrazovaniâprilokalizaciiposledovatelʹnosteisimvolov
AT babilungaoû ispolʹzovanieveivletpreobrazovaniâprilokalizaciiposledovatelʹnosteisimvolov
AT antoŝuksg localizationofsymbolicsequencesusingwavelettransforms
AT nikolenkoaa localizationofsymbolicsequencesusingwavelettransforms
AT tkačenkoev localizationofsymbolicsequencesusingwavelettransforms
AT babilungaoû localizationofsymbolicsequencesusingwavelettransforms
AT antoŝuksg vikoristannâveivletperetvorennâprilokalízacííposlídovnosteisimvolív
AT nikolenkoaa vikoristannâveivletperetvorennâprilokalízacííposlídovnosteisimvolív
AT tkačenkoev vikoristannâveivletperetvorennâprilokalízacííposlídovnosteisimvolív
AT babilungaoû vikoristannâveivletperetvorennâprilokalízacííposlídovnosteisimvolív

Ähnliche Einträge