Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних

An algorithm for development of optimal pairs of filters of any complexity for (coding and recovery which are) adaptive to multivariable function is proposed.

Збережено в:

Бібліографічні деталі
Дата:	2009
Автори:	Ligun, A. А., Shumeiko, A. А., Zhurba, V. М.
Формат:	Стаття
Мова:	Українська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2009
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/107269
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1867334304100515840
author	Ligun, A. А. Shumeiko, A. А. Zhurba, V. М.
author_facet	Ligun, A. А. Shumeiko, A. А. Zhurba, V. М.
author_institution_txt_mv	[ { "author": "A. А. Ligun", "institution": null }, { "author": "A. А. Shumeiko", "institution": null }, { "author": "V. М. Zhurba", "institution": null } ]
author_sort	Ligun, A. А.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-04-06T12:33:06Z
description	An algorithm for development of optimal pairs of filters of any complexity for (coding and recovery which are) adaptive to multivariable function is proposed.
first_indexed	2025-07-17T10:22:19Z
format	Article
fulltext	© А.О. Лигун, О.О. Шумейко, В.М. Журба, 2009 Системні дослідження та інформаційні технології, 2009, № 4 47 TIДC ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ, ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ СИСТЕМИ УДК 004.932.4 АЛГОРИТМ ПОБУДОВИ ОПТИМАЛЬНИХ ПАР ФІЛЬТРІВ КОДУВАННЯ І ВІДНОВЛЕННЯ, АДАПТИВНИХ ДО ФУНКЦІЇ БАГАТЬОХ ЗМІННИХ А.О. ЛИГУН, О.О. ШУМЕЙКО, В.М. ЖУРБА Розглянуто алгоритм побудови оптимальних пар фільтрів будь-якої складності кодування і відновлення, адаптивних до функції багатьох змінних, для довіль- ного регулярного паркету. ВСТУП Одне з ключових понять в задачах обробки цифрових сигналів — поняття фільтрації. Для виявлення певних особливостей, закономірностей сигналів, а також в задачах, пов’язаних зі зменшенням фізичного об’єму даних, необ- хідних для відтворення сигналу, використовують різні методи фільтрації [1, 2]. Найбільш поширеними з них є методи, засновані на теорії wavelet- аналізу, дискретному перетворенні Фур’є. Однак, хоча дані методи фільтра- ції оптимальні для того чи іншого класу сигналів, для кожного конкретного сигналу вони не є оптимальними. Питання побудови адаптивно-оптималь- них фільтрів базується на дослідженнях Н. Вінера, А.М. Колмогорова та ін. У даній роботі розглянуто алгоритм побудови пари фільтрів кодування і відновлення, адаптивних до функції (сигналу). Також надані розв’язки за- дач побудови адаптивно-оптимального кодування лінійними методами при відомому методі відновлення та побудови адаптивно-оптимального лінійно- го методу відновлення функції по відомим значенням коду як з певними об- меженнями, так і без них. Розв’язки задач отримані в загальному вигляді для будь-якого регулярного паркету, фільтрів довільної складності та функції довільного числа змінних. ПОСТАНОВКА ЗАДАЧІ Нехай ( )XF — функція багатьох змінних таких, що { } nn kk ZxX ∈= =1 . Крім того, позначимо { }n kkiI 1== — вектор-індекс та { }n kkdD 1== — крок коду- вання функції ( )XF . А.О. Лигун, О.О. Шумейко, В.М. Журба ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 48 Код функції ( )XF позначимо { } nZIIF ∈=Φ=Φ ϕ)( та задамо у вигляді лінійного функціоналу ( )∑ ∈ += V I IDF ς ς ςβϕ , (1) де V — апертура, по якій будується код функції F , така, що { }kvV = та n k Zvk ∈∀ : , тобто елементи апертури представляють собою вектор-індекси розмірністю n , що співпадає з кількістю змінних функції F . Також нехай задано паркет Ξ . Не втрачаючи загальності, будемо вва- жати, що { }n kk 1==Γ γ належить елементові паркету Ξ та відповідним чином визначається D (кроком кодування функції). Побудуємо лінійний метод відновлення функції F за значеннями коду. ( )( ) ( ) ( ) ∑ Γ∈ +Γ=Γ+ K IDIF ξ ξξ ϕα~ , (2) де ( )ΓK — множина вектор-індексів із nZ , що визначає складність форму- ли відновлення в точках виду Ξ∈Γ . Таким чином для Ξ∈Γ∀ можна побу- дувати лінійний метод відновлення (2), складність якого визначається кількістю елементів апертури ( )ΓK . Користуючись (1) та (2), можна отримати екстремальну задачу пошуку адаптивно-оптимальної пари фільтрів кодування і відновлення функції n змінних при заданій складності формул, тобто при заданій кількості відмінних від нуля коефіцієнтів фільтрів. ( )( ) ( )( ) min~ 2 →Γ+−Γ+ DIFDIF . (3) Дана задача є загальною постановкою задачі кодування–відновлення функції n змінних при довільному паркеті Ξ . Вираз ( )( ) ( ) ( )( ) ( ) ∑ ∑ Γ∈ ∈ ++Γ=Γ+ K V DIFDIF ξ ς ςξ ςξβα підставимо у (3). ( )( ) ( ) ( )( ) ( ) ( ){ }{ }ςξ βαξ ς ςξ ςξβα , 2 min Γ ∈ Ξ∈Γ Γ∈ ∈ →⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ++Γ−Γ+= ∑ ∑ ∑ ∑ nZI K V DIFDIFS . Розв’язок даної екстремальної задачі визначається системою рівнянь ( ) ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ∈∀= ∂ ∂ Ξ∈Γ∀Γ∈∀= Γ∂ ∂ .,0 ,,,0 VS KS ς β ξ α ς ξ (4) Запишемо вирази частинних похідних ( ) ( )( ) ( ) ( )( ) ( ) × ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ++Γ−Γ+= Γ′∂ ∂ ∑ ∑ Γ∈ ∈′ K V DIFDIFS ξ ς ςξ ξ ςξβα α 2 Алгоритм побудови оптимальних пар фільтрів кодування і відновлення ... Системні дослідження та інформаційні технології, 2009, № 4 49 ( )( ) ( ) Ξ∈Γ′∀Γ′∈′∀= ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ +′+× ∑ ∈ ,,0 KDIF V ξςξβ ς ς . ( )( ) ( ) ( )( ) ( ) × ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ++Γ−Γ+= ∂ ∂ ∑ ∑ Γ∈ ∈′ K V DIFDIFS ξ ς ςξ ς ςξβα β 2 ( ) ( )( ) ( ) .,0 VDIF K ∈′∀= ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ′++Γ× ∑ Γ∈ ςςξα ξ ξ Отримана система рівнянь не є лінійною та має багато розв’язків. Точ- ний розв’язок навіть при невеликих апертурах отримати вкрай складно, на- віть при суттєвих обмеженнях [3]. Запропоновано ітераційний метод отримання адаптивно-оптимальних пар фільтрів. Аналогічно до методу головних компонент знаходимо розв’язок системи (4), по черзі фіксуючи коефіцієнти ( ){ }Γξα і { }ςβ . Таким чином, задача розпадається на дві окремі задачі — знаходження адаптивно- оптимального методу відновлення функції за існуючими значеннями коду та знаходження адаптивного методу кодування функції таким чином, щоб се- редньоквадратична похибка відновлення відомим фільтром була мінімаль- ною. Розглянемо першу задачу. Нехай числа }{ ςβ фіксовані. Тоді згідно з (1) можна вважати, що відомі значення коду Iϕ . Отже, задача адаптивно-оптимального відновлення функції по відомим значенням коду буде мати вигляд ( )( ) ( ) ( ) ( ){ }Γ ∈ Γ∈ + → ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ Γ−Γ+∑ ∑ ξαξ ξξ ϕα min 2 nZI K IDIF . Запишемо розв’язок даної задачі у вигляді матричного рівняння g=Θα при фіксованому Ξ∈Γ . Елементи матричного рівняння будуть такими: ∑ ∈ ++− =ΦΦ=Θ n lklk ZI IIlk ξξξξ ϕϕ, , ( )( )∑ ∈ +Γ+=Φ= n ll ZI Il DIFFg ξξ ϕ , де lξ — перенумеровані довільно елементи апертури ( )ΓK . Можна також отримати модифікації методу за умови симетрії базисної функції (фільтра відновлення) та точності на константах. При цьому отри- маємо задачу умовної мінімізації ( )( ) ( ) ( )( ) ( )}{ 2 min * * Γ ∈ Γ∈ Ω∈ + →⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ Γ−Γ+∑ ∑ ∑ ξαξ ξξ ξξ ϕα nZI K I DIF при умові ( ) ( ) 1=Γ∑ Γ∈Kξ ξα , А.О. Лигун, О.О. Шумейко, В.М. Журба ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 50 де ( )ξΩ — множина вектор-індексів, отриманих певним симетричним пере- творенням ξ . Розв’язуючи дану задачу методом невизначених коефіцієнтів Лагранжа, приходимо до екстремальної задачі ( )( ) ( ) ( )( ) ( ) ( ) ( ){ }ΓΓ∈∈ Γ∈ Ω∈ + → ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −Γ+⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ Γ−Γ+ ∑∑ ∑ ∑ ξαξ ξ ξ ξξ ξξ αλϕα min1 2 * * KZI K I n DIF . Розв’язок цієї задачі визначається матричним рівнянням ** g=Θ α , де ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ΘΘ ΘΘ =Θ 01...1 1... ............ 1... ,1, ,11,1 * MMM M , ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 1 ... 1 * Mg g g ; M — кількість елементів апертури ( )ΓK ; λα =+1M та для будь-яких Mlk ≤, ( ) ∑ Ω∈ − ΦΦ=Θ ςς ςς * *, lk lk , ( ) ∑ Ω∈ Φ= ςς ς * l Fgl . Якщо звільнитись від однієї з умов, що обмежує, отримаємо такі модифікації методу. За умови лише точності на константах розв’язок задачі визначається рівнянням ** g=Θ α , а елементи Θ та g для Mlk ≤, будуть мати вигляд lklk ςς −ΦΦ=Θ , , l Fgl ςΦ= . У випадку, коли необхідна лише симетрія відповідної базисної функції, розв’язок задачі визначається рівнянням g=Θα . При цьому =Θ lk , ( ) ∑ Ω∈ − 〉ΦΦ〈= ςς ςς * ** lk , ( ) ∑ Ω∈ 〉〈 Φ= ςς ς * * l Fgl . Розглянемо задачу адаптивного лінійного кодування фільтром заданої складності. Розв’язок цієї задачі — це розв’язок (4) за умови, що числа ( ){ }Γξα фіксовані. ( )( ) ( ) ( )( ) ( ) × ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ++Γ−Γ+ ∑ ∑ Γ∈ ∈K V DIFDIF ξ ς ςξ ςξβα ( ) ( )( ) ( ) VDIF K ∈′∀= ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ′++Γ× ∑ Γ∈ ςςξα ξ ξ ,0 . Введемо позначення. ( )( )ςς +Γ+=Γ DIFFI , , ( )Γ=Γ ξξ αα , ∑ ∈ ′ Γ′Γ ′ Γ′Γ = nZI II FFFF ςςςς ,,, , Алгоритм побудови оптимальних пар фільтрів кодування і відновлення ... Системні дослідження та інформаційні технології, 2009, № 4 51 Γ ′ ΓΓ ′ =Λ ξξξξ αα, . Таким чином, користуючись запропонованими позначеннями, маємо ( ) ∑ ∑∑ ∑ ∑ ∑ Ξ∈Γ Γ∈ ′ Γ Γ ∈ Ξ∈Γ Γ∈ Γ∈′ ′ ′ Γ ′ =Λ KV FFFF ξ ς ξξ ς ξ ξ ς ξ ς ξξξς αβ ,, 0 , , V∈′∀ς . Отже, якщо записати отриману систему рівнянь у матричному виді, от- римаємо g=Θβ , де ( )( ) ∑ ∑ ∑ Ξ∈Γ Γ =′ Γ =′ Γ ′′′′ Λ=Θ M k M l lk l l k klk FF 1 1 ,, , ς ξ ς ξξξ ; ( ) ∑ ∑ Ξ∈Γ Γ = Γ Γ= M k l l kk FFg 1 0 , ς ξξα ; { }iς — перенумеровані елементи апертури V ; ( )ΓM — кількість елементів апертури ( )ΓK ; { }iξ — перенумеровані елементи апертури ( )ΓK . Наведемо один приклад використання адаптивної фільтрації. Як дво- вимірний сигнал розглянемо кадр, отриманий у результаті розгортки відео- сигналу (interlace). У цьому випадку відновлення сигналу за допомогою си- метричної базисної функції може бути гірше, ніж несиметричної. Як тестові приклади були використані стоп-кадри кабельної мережі телебачення, ком- позиційний функціонал (децимація). Результат відновлення в залежності від динаміки сигналу відрізняється в межах 10%. Приклади отриманих адап- тивно-оптимальних симетричної та несиметричної базисних функцій наве- дено на рис. 1, 2. ВИСНОВКИ Отриманий результат дає можливість побудови лінійних методів адаптивної до функції оптимальної фільтрації. Для будь-якого методу кодування можна 1,2 –0,2 Рис. 1. Несиметрична базисна функція Interlace Frame (децимація 2×2, апертура 3×3) 1,2 –0,2 Рис. 2. Симетрична базисна функція In- terlace Frame (децимація 2×2, апертура 3×3) А.О. Лигун, О.О. Шумейко, В.М. Журба ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 52 запропонувати оптимальний лінійний метод відновлення, адаптований до сигналу, що дозволяє покращити декодер багатьох відомих методів коду- вання, пов’язаних із задачами розподілу сигналу за частотними характери- стиками, компресією, масштабуванням і т. ін. Для довільних лінійних ме- тодів декодування можна реалізувати лінійний метод кодування, який забезпечить оптимальну фільтрацію, адаптивну до (функції) сигналу та ме- тоду відновлення. ЛІТЕРАТУРА 1. Адаптивные фильтры / Под ред. К.Ф.Н. Коуэна и П.М. Гранта. — М.: Мир, 1988. — 392 с. 2. Розорінов Г.М. Адаптивне дискретне вейвлет-перетворення у системах зв’язку // Вісн. Держ. ун-ту інформаційно-коммунікаційних технологій. — 2004. — 2, № 2. — С. 90–96. 3. Лигун А.А., Шумейко А.А., Журба В.Н. Об адаптивно-оптимальном восста- новлении сигналов линейными методами заданной сложности // Питання прикл. математики і матем. моделювання: Зб. наук. пр. — ДНУ, 2007. — С. 67–77. Надійшла 23.04.2008
id	journaliasakpiua-article-107269
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:22:19Z
publishDate	2009
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/2d/77dfeb97f4f97a285b9332404c9a952d.pdf
spelling	journaliasakpiua-article-1072692018-04-06T12:33:06Z Algorithm for development of optimal pairs of filters (coding and recovery) adaptive to multivariable function Алгоритм построения оптимальных пар фильтров кодирования и восстановления, адаптивных к функции многих переменных Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних Ligun, A. А. Shumeiko, A. А. Zhurba, V. М. An algorithm for development of optimal pairs of filters of any complexity for (coding and recovery which are) adaptive to multivariable function is proposed. Рассмотрен алгоритм построения оптимальных пар фильтров произвольной сложности кодирования и восстановления, адаптивных к функции многих переменных, для любого регулярного паркета. Розглянуто алгоритм побудови оптимальних пар фільтрів будь-якої складності кодування і відновлення, адаптивних до функції багатьох змінних, для довільного регулярного паркету. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2009-09-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/107269 System research and information technologies; No. 4 (2009); 47-52 Системные исследования и информационные технологии; № 4 (2009); 47-52 Системні дослідження та інформаційні технології; № 4 (2009); 47-52 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/107269/102236 Copyright (c) 2021 System research and information technologies
spellingShingle	Ligun, A. А. Shumeiko, A. А. Zhurba, V. М. Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_alt	Algorithm for development of optimal pairs of filters (coding and recovery) adaptive to multivariable function Алгоритм построения оптимальных пар фильтров кодирования и восстановления, адаптивных к функции многих переменных
title_full	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_fullStr	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_full_unstemmed	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_short	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_sort	алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
url	https://journal.iasa.kpi.ua/article/view/107269
work_keys_str_mv	AT ligunaa algorithmfordevelopmentofoptimalpairsoffilterscodingandrecoveryadaptivetomultivariablefunction AT shumeikoaa algorithmfordevelopmentofoptimalpairsoffilterscodingandrecoveryadaptivetomultivariablefunction AT zhurbavm algorithmfordevelopmentofoptimalpairsoffilterscodingandrecoveryadaptivetomultivariablefunction AT ligunaa algoritmpostroeniâoptimalʹnyhparfilʹtrovkodirovaniâivosstanovleniâadaptivnyhkfunkciimnogihperemennyh AT shumeikoaa algoritmpostroeniâoptimalʹnyhparfilʹtrovkodirovaniâivosstanovleniâadaptivnyhkfunkciimnogihperemennyh AT zhurbavm algoritmpostroeniâoptimalʹnyhparfilʹtrovkodirovaniâivosstanovleniâadaptivnyhkfunkciimnogihperemennyh AT ligunaa algoritmpobudovioptimalʹnihparfílʹtrívkoduvannâívídnovlennâadaptivnihdofunkcííbagatʹohzmínnih AT shumeikoaa algoritmpobudovioptimalʹnihparfílʹtrívkoduvannâívídnovlennâadaptivnihdofunkcííbagatʹohzmínnih AT zhurbavm algoritmpobudovioptimalʹnihparfílʹtrívkoduvannâívídnovlennâadaptivnihdofunkcííbagatʹohzmínnih

Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних

Репозитарії

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