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

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

Full description

Saved in:

Bibliographic Details
Published in:	Системні дослідження та інформаційні технології
Date:	2009
Main Authors:	Лигун, А.О., Шумейко, О.О., Журба, В.М.
Format:	Article
Language:	Ukrainian
Published:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2009
Subjects:	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/42237
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних / А.О. Лигун, О.О. Шумейко, В.М. Журба // Систем. дослідж. та інформ. технології. — 2009. — № 4. — С. 47–52. — Бібліогр.: 3 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-42237
record_format	dspace
spelling	Лигун, А.О. Шумейко, О.О. Журба, В.М. 2013-03-13T16:54:39Z 2013-03-13T16:54:39Z 2009 Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних / А.О. Лигун, О.О. Шумейко, В.М. Журба // Систем. дослідж. та інформ. технології. — 2009. — № 4. — С. 47–52. — Бібліогр.: 3 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/42237 004.932.4 Розглянуто алгоритм побудови оптимальних пар фільтрів будь-якої складності кодування і відновлення, адаптивних до функції багатьох змінних, для довільного регулярного паркету. Рассмотрен алгоритм построения оптимальных пар фильтров произвольной сложности кодирования и восстановления, адаптивных к функции многих переменных, для любого регулярного паркета. An algorithm for development of optimal pairs of filters of any complexity for (coding and recovery which are) adaptive to multivariable function is proposed. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних Алгоритм построения оптимальных пар фильтров кодирования и восстановления, адаптивных к функции многих переменных Algorithm for development of optimal pairs of filters (coding and recovery) adaptive to multivariable function Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
spellingShingle	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних Лигун, А.О. Шумейко, О.О. Журба, В.М. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
title_short	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_full	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_fullStr	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_full_unstemmed	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
title_sort	алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних
author	Лигун, А.О. Шумейко, О.О. Журба, В.М.
author_facet	Лигун, А.О. Шумейко, О.О. Журба, В.М.
topic	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
topic_facet	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
publishDate	2009
language	Ukrainian
container_title	Системні дослідження та інформаційні технології
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
format	Article
title_alt	Алгоритм построения оптимальных пар фильтров кодирования и восстановления, адаптивных к функции многих переменных Algorithm for development of optimal pairs of filters (coding and recovery) adaptive to multivariable function
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.
issn	1681–6048
url	https://nasplib.isofts.kiev.ua/handle/123456789/42237
citation_txt	Алгоритм побудови оптимальних пар фільтрів кодування і відновлення, адаптивних до функції багатьох змінних / А.О. Лигун, О.О. Шумейко, В.М. Журба // Систем. дослідж. та інформ. технології. — 2009. — № 4. — С. 47–52. — Бібліогр.: 3 назв. — укр.
work_keys_str_mv	AT ligunao algoritmpobudovioptimalʹnihparfílʹtrívkoduvannâívídnovlennâadaptivnihdofunkcííbagatʹohzmínnih AT šumeikooo algoritmpobudovioptimalʹnihparfílʹtrívkoduvannâívídnovlennâadaptivnihdofunkcííbagatʹohzmínnih AT žurbavm algoritmpobudovioptimalʹnihparfílʹtrívkoduvannâívídnovlennâadaptivnihdofunkcííbagatʹohzmínnih AT ligunao algoritmpostroeniâoptimalʹnyhparfilʹtrovkodirovaniâivosstanovleniâadaptivnyhkfunkciimnogihperemennyh AT šumeikooo algoritmpostroeniâoptimalʹnyhparfilʹtrovkodirovaniâivosstanovleniâadaptivnyhkfunkciimnogihperemennyh AT žurbavm algoritmpostroeniâoptimalʹnyhparfilʹtrovkodirovaniâivosstanovleniâadaptivnyhkfunkciimnogihperemennyh AT ligunao algorithmfordevelopmentofoptimalpairsoffilterscodingandrecoveryadaptivetomultivariablefunction AT šumeikooo algorithmfordevelopmentofoptimalpairsoffilterscodingandrecoveryadaptivetomultivariablefunction AT žurbavm algorithmfordevelopmentofoptimalpairsoffilterscodingandrecoveryadaptivetomultivariablefunction
first_indexed	2025-11-26T07:27:23Z
last_indexed	2025-11-26T07:27:23Z
_version_	1850617276270641152
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

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

Institution

Similar Items