Цифровий гібридний медіанний фільтр

УКРАЇНА (19) UA (11) 63200 (13) U (51) МПК G06F 17/18 (2006.01) ДЕРЖАВНА СЛУЖБА ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ УКРАЇНИ видається під відповідальність власника патенту ОПИС ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) ЦИФРОВИЙ ГІБРИДНИЙ МЕДІАННИЙ ФІЛЬТР 1 2 (13) 63200 (11) анних фільтрів з'єднані з відповідними групами елементів ковзного вікна розміром 33 пікселів, а їх виходи з'єднані із входами четвертого медіанного фільтра, всі чотири цифрові медіанні фільтри виконані однаково, при цьому кожний з чотирьох цифрових медіанних фільтрів містить три однакових селектори мінімального елемента і один селектор максимального елемента, причому кожний вхід кожного із селекторів мінімального елемента з'єднаний з одним входом одного із двох інших селекторів мінімального елемента, а виходи селекторів мінімального елемента з'єднані із входами селектора максимального елемента, причому всі входи й виходи цифрових медіанних фільтрів, а також селекторів мінімального і максимального елементів є q-бітовими шинами даних. Недоліком зазначеного фільтра є низька точність оцінки медіани серед елементів ковзного вікна розміром 33 пікселів. В основу корисної моделі поставлено задачу збільшення фільтром точності оцінки медіани у ковзному вікні розміром 33 пікселів. Поставлена задача досягається тим, що у цифровий гібридний медіанний фільтр згідно з корисною моделлю введено групу з дев'яти лічильників, вихідний лічильник, групу з дев'яти елементів UA Корисна модель належить до галузі обчислювальної техніки, зокрема до цифрових фільтрів для обробки зображень, а саме, до цифрових медіанних фільтрів для обробки зображень. Відомий цифровий гібридний медіанний фільтр (Bernacchia G., Khriji L., Gabbouj M., Sicuranza G. Hardware Implementation of the Median-Rational Hybrid Filters// Proceedings of the 6th IEEE International Conference on Electronics, Circuits and Systems - ICECS'99, 1999, pp. 229232.), що містить чотири цифрові медіанні фільтри, причому перші три з них з'єднані паралельно, а четвертий з'єднаний послідовно, при цьому входи перших трьох медіанних фільтрів з'єднані з відповідними групами елементів ковзного вікна розміром 33 пікселів, а їх виходи з'єднані із входами четвертого медіанного фільтра. Недоліком зазначеного фільтра є низька точність оцінки медіани серед елементів ковзного вікна розміром 33 пікселів. Найбільш близьким технічним рішенням, обраного за прототип, є цифровий гібридний медіанний фільтр (патент України на корисну модель № 50590, кл. G06F17/18, 2010), що містить чотири цифрові медіанні фільтри, причому перші три з них з'єднані паралельно, а четвертий з'єднаний послідовно, при цьому входи перших трьох меді U ра, причому перший вхід вхідного елемента І з'єднаний з входом тактових імпульсів, вихід вхідного елемента І з'єднаний з першими входами групи забороняючих елементів І, виходи яких з'єднані з входами віднімання відповідних лічильників, вихід вхідного елемента І з'єднаний з входом додавання вихідного лічильника, виходи якого порозрядно з'єднані з першими входами групи елементів І, інверсні виходи ознаки нуля групи лічильників з'єднані відповідно з другими входами групи забороняючих елементів І та входами групи елементів НІ, виходи яких з'єднані з входами блока підрахунку, вихід якого з'єднаний з другими входами групи елементів І та з інверсним входом вхідного елемента І, входи групи лічильників з'єднані з відповідними елементами ковзного вікна розміром 3*3 пікселів, вхід скиду підключений до входів скиду групи лічильників та вихідного лічильника. (19) (21) u201107118 (22) 06.06.2011 (24) 26.09.2011 (46) 26.09.2011, Бюл.№ 18, 2011 р. (72) ШОСТАК АНАТОЛІЙ ВАСИЛЬОВИЧ, ДОРОШЕНКО ЮРІЙ ІВАНОВИЧ, КОЛОМІЙЦЕВ ОЛЕКСІЙ ВОЛОДИМИРОВИЧ, ЛОСЄВ МИХАЙЛО ЮРІЙОВИЧ, РИСОВАНИЙ ОЛЕКСАНДР МИКОЛАЙОВИЧ (73) НАЦІОНАЛЬНИЙ АЕРОКОСМІЧНИЙ УНІВЕРСИТЕТ ІМ. М.Є.ЖУКОВСЬКОГО "ХАРКІВСЬКИЙ АВІАЦІЙНИЙ ІНСТИТУТ" (57) Цифровий гібридний медіанний фільтр, який відрізняється тим, що в нього введено групу з дев'яти лічильників, вихідний лічильник, групу з дев'яти елементів НІ, вхідний елемент І, групу з дев'яти забороняючих елементів І, блок підрахунку та групу елементів І, виходи яких є виходом фільт 3 НІ, вхідний елемент І, групу з дев'яти забороняючих елементів І, блок підрахунку та групу елементів І, виходи яких є виходом фільтра, причому перший вхід вхідного елемента І з'єднаний з входом тактових імпульсів, вихід вхідного елемента І з'єднаний з першими входами групи забороняючих елементів І, виходи яких з'єднані з входами віднімання відповідних лічильників, вихід вхідного елемента І з'єднаний з входом додавання вихідного лічильника, виходи якого порозрядно з'єднані з першими входами групи елементів І, інверсні виходи ознаки нуля групи лічильників з'єднані відповідно з другими входами групи забороняючих елементів І та входами групи елементів НІ, виходи яких з'єднані з входами блока підрахунку, вихід якого з'єднаний з другими входами групи елементів І та з інверсним входом вхідного елемента І, входи групи лічильників з'єднані з відповідними елементами ковзного вікна розміром 33 пікселів, вхід скиду підключений до входів скиду лічильників групи та вихідного лічильника. На фіг. показана структурна схема цифрового гібридного медіанного фільтра. Цифровий гібридний медіанний фільтр містить групу з дев'яти лічильників 11,...,19, вихідний лічильник 2, групу з дев'яти елементів НІ 31,...,39, вхідний елемент І 4, групу з дев'яти забороняючих елементів І 51,...,59, блок підрахунку 6 та групу елементів І 71,...,7k. Виходи групи елементів І 71,...,7k (де k - розрядність елементів ковзного вікна розміром 33 пікселів) є виходом фільтра 11, причому перший вхід вхідного елемента І 4 з'єднаний з входом тактових імпульсів 10, вихід вхідного елемента I 4 з'єднаний з першими входами групи забороняючих елементів І 51,...,59, виходи яких з'єднані з входами віднімання відповідних лічильників 11,...,19, вихід вхідного елемента І 4 з'єднаний з входом додавання вихідного лічильника 2, виходи якого порозрядно з'єднані з першими входами групи елементів І 71,...,7k, інверсні виходи ознаки нуля 81,...,89 групи лічильників 11,...,19 з'єднані відповідно з другими входами групи забороняючих елементів І 51,...,59 та входами групи елементів НІ 31,...,39, виходи яких з'єднані з входами блока підрахунку 6, вихід якого з'єднаний з другими входами групи елементів І 71...,7k та з інверсним входом вхідного елемента І 4, входи групи лічильників 11,...,19 з'єднані з відповідними елементами ковзного вікна розміром 33 пікселів, вхід скиду 9 підключений до входів скиду групи лічильників 11,...,19 та вихідного лічильника 2. Прототип (патент України на корисну модель № 50590, кл. G06F17/18, 2010) формує результат обробки даних у ковзному вікні розміром 33 пікселів W=||w1k|| (де w1k, 1 = 1, 2, 3; k = 1, 2, 3) у вигляді медіани медіан даних у кожному із трьох рядків значень пікселів ковзного вікна W: Y’ = med w1, w2, w3), де w1 = med (w11, w12, w13), 1 = 1, 2, 3. 63200 4 Такий алгоритм оцінки медіани не завжди дає точний результат. Нехай, наприклад, вікно розмі 1 2 3   ром 33 має вигляд W   4 5 6  ,  1 2 3   тоді w1 = med (w11, w12, w13) = med (1, 2, 3) = 2, w2 = med (w21 w22, w23) = med (4, 5, 6) = 5, w3=med (w31, w32, w33) = med (1, 2, 3) = 2 і результат оцінки медіани має вигляд Y’ = med (w1, w2, w3) = med (2, 5, 2) = 2. Тоді як точний алгоритм пошуку медіани дає наступний результат Y = med (w11, w12, w13, w21, w22, w23, w31, w32, w33) = med (1, 2, 3, 4, 5, 6, 1, 2, 3) = 3. (Дійсно, медіана має у відсортованому вихідному масиві (1, 1, 2, 2, 3, 3, 4, 5, 6) індекс і = (9 + 1)/2 = 5, тобто медіана даного масиву дорівнює 3, а не 2.) Відповідно до (Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:МЦНМО, 2000. - 960 с., с. 180) медіаною називається елемент безлічі з m елементів, що перебуває (по рахунку) посередині між мінімумом і максимумом. Точніше, якщо m непарне, то медіана по рахунку має номер і = (m + 1)/2. Тобто медіаною серед чисел {3 6 2 8 7} є число 6, тому що у відсортованому масиві (2, 3, 6, 7, 8) число 6 стоїть на 3ому по рахунку місці. Запропонований цифровий гібридний медіанний фільтр виконує точний алгоритм пошуку медіани і працює наступним чином. Спочатку лічильники 11,...,19 і вихідний лічильник 2 встановлюють у початковий (нульовий) стан за одиничним сигналом на вході скиду 9, який подають на їх входи скиду. Потім дев'ять цифрових відліків значень пікселів w1k, 1 = 1, 2, 3; k = 1, 2, 3 з ковзного вікна W=||w1k|| двовимірного масиву вихідного зображення надходять на відповідні входи дев'яти лічильників 11,...,19 фільтра (фіг.). На виході блоку підрахунку 6 присутній нульовий сигнал, так як вміст лічильників 11,...,19 не дорівнює нулю і на їх інверсних виходах 81,...,89 ознаки нуля зафіксовані одиничні сигнали. Блок підрахунку 6 виконує підрахунок числа одиниць у двійковому числі з непарним числом розрядів, яке формується інверсними значеннями інверсних виходів ознаки нуля 81...,89 лічильників 11,...,19. На виході блоку підрахунку 6 з'являється одиничний сигнал, коли кількість одиничних сигналів на його входах буде дорівнювати або більше 5 і нульовий сигнал - у противному випадку. Опис і схема блоку підрахунку 6 наведені в А.с. СССР № 1751749 Устройство для подсчета количества единиц в двоичном числе G06F7/52 1992. Коли на вхід 10 фільтра буде подано кількість тактових імпульсів, що відповідає значенню мінімального числа серед дев'яти цифрових відліків, що були записані в лічильниках 11,...,19, а тепер сформовані у вихідному лічильнику 2, вміст лічильника 1і де і = 1,...,9, в якому записане мінімальне число, стане дорівнювати нулю, на його інверсному виході 8і ознаки нуля з'являється нульовий сигнал, що закриває забороняючий елемент І 5і і відповідно вхід віднімання лічильника 1і. Але на 5 виході блоку підрахунку 6 залишиться нульовий сигнал. Тактові імпульси продовжують надходити на входи віднімання лічильників 11,...,19, крім вже обнулених лічильників, та на вхід додавання вихідного лічильника 2. Коли на вхід 10 фільтра буде подано кількість тактових імпульсів, що відповідає значенню медіани серед чисел, що були записані в лічильниках 11,...,19, а тепер сформоване у вихідному лічильнику 2, вміст лічильника 1j, де j = l,...,9, в якому записана медіана, стане дорівнювати нулю. При цьому всього буде обнулено 5 лічильників, тобто на інверсних виходах ознаки нуля цих лічильників присутні нульові сигнали. Тоді на виході блока підрахунку 6 сформується одиничний сигнал, який подається на інверсний вхід вхідного елемента І 4. Одиничний сигнал на інверсному вході елемента вхідного І 4 припинить надходження тактових імпульсів на вхід додавання вихідного лічильника 2 і на входи віднімання ще не обнулених лічильників групи. Комп’ютерна верстка Л.Литвиненко 63200 6 Тактові імпульси на входи віднімання лічильників 11,...,l9 і на входи додавання вихідного лічильника 2 не поступають. При цьому у вихідному лічильнику 2 залишається зафіксовано значення медіани серед пікселів ковзного вікна розміром 33. Одиничний сигнал з виходу блоку підрахунку 6, будучи поданий на другі входи елементів І 71...,7k групи, дозволяє проходження через них на виходи 11 фільтра інформації з виходів вихідного лічильника 2, тобто медіани. Таким чином здійснюється фільтрація пікселів у вікні розміру 33, тобто вибір медіани цифровим гібридним медіанним фільтром. Запропонований цифровий гібридний медіанний фільтр має більшу точність оцінки медіани у ковзному вікні розміром 33 пікселів за рахунок реалізації точного алгоритму пошуку медіани. Підписне Тираж 23 прим. Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601