Пристрій медіанної фільтрації

Реферат: Винахід належить до галузі штучного інтелекту, а саме до систем технічного зору, систем цифрового опрацювання зображень та може бути використаний для первинного опрацювання зображень. Пристрій медіанної фільтрації містить блок фільтрації та сортування, тактові входи регістрів даного блока з'єднані з тактовим входом пристрою та тактовим входом вхідного регістра, виходи вузлів порівняння (m-1)-гo блока порівняння з'єднані з відповідними виходами блоку фільтрації та сортування, (m-1) блоків сортування, кожний i-й блок сортування містить (іm+m) двовходових комутаторів, (іm+m) регістрів і (іm+m) вузлів порівняння. Технічним результатом, що досягається даним винаходом, є розширення функціональних можливостей шляхом фільтрації як у ковзному "вікні" розміром m, так і ковзному "вікні" розміром mm. UA 108974 C2 (12) UA 108974 C2 UA 108974 C2 5 10 15 20 25 30 35 40 45 50 55 60 Винахід належить до галузі штучного інтелекту, а саме до систем технічного зору, систем цифрового опрацювання зображень та може бути використаний для первинного опрацювання зображень. Відомий пристрій для медіанної фільтрації [Вишенчук И.М., Черкасский Н.В. Алгоритмические операционние устройства и супер ЄВМ. - К.: Техника, 1990. - с. 131], який 2 містить 2m+1 регістрів, де (2m+1) - кількість елементів сортування в заданому вікні, 1,5 (m -m) вузлів порівняння, кожний з яких містить схему порівняння і дві схеми "І-АБО". Недоліками такого пристрою медіанної фільтрації є невисока швидкодія, яка визначається часом спрацювання (2/m+1) схем порівняння і (2m-1) елементів "І-АБО" та обмежені функціональні можливості (медіанна фільтрація виконується тільки у ковзному "вікні" розміром m). Відомий пристрій для медіанної фільтрації [Палагин А.В., Опанасенко В.Н. Реконфигурируемые вычислительные системы - К.: Просвіта, 2006. - с. 209], який містить m 2 регістрів, де m - розмір вікна, т суматорів, (m -m)\2+m-1 вузлів порівняння, дешифратор і мультиплексор. Однак даний пристрій має невисоку швидкодію виконання медіанної фільтрації, яка визначається часом спрацювання регістра, схеми порівняння, суматора, дешифратора і мультиплексора, та обмежені функціональні можливості (медіанна фільтрація виконується тільки у ковзному "вікні" розміром m). Найбільш близьким до запропонованого пристрою є пристрій медіанної фільтрації [Пат. 105305 України, МПК G 06K9/36. Пристрій медіанної фільтрації / Ю.М. Рашкевич, І.Г. Цмоць, Д.Д. Пелешко, І.В. Ізонін (Україна). - № а201301666; заявл. 12.02.2013; опубл. 25.04.2014, Бюл. № 8.], який містить вхідний регістр, входом якого є інформаційних вхід, (m-m)/2 регістрів, m-1 блоків порівняння, кожний і-й блок порівняння (і=1,…, m-1) містить (i+1) вузлів порівняння, кожний з яких містить схему порівняння та тривходовий комутатор, при цьому перші входи всіх схем порівняння з'єднані між собою, вихід вхідного регістра з'єднаний з першими входами всіх схем порівняння відповідних вузлів порівняння, другим інформаційним входом тривходового комутатора та з входом регістра з першого блока порівняння, в кожному i-у блоці порівняння вихід j-о регістра (j=1,…, i) з'єднаний з другим входом схеми порівняння та третім інформаційним входом тривходового комутатора і першим входом тривходового комутатора (j+1) вузла, вхід j-о регістра (i+1) блока порівняння з'єднаний з виходом тривходового комутатора j-го вузла порівняння і-го блока порівняння, вихід тривходового комутатора з (m+1)/2 вузла порівняння (m-1) блока порівняння з'єднаний з виходом медіани, в кожному і-му блоці порівняння перший вхід управління комутатора першого вузла порівняння з'єднаний з рівнем лог. 1, в кожному блоці порівняння в (i+1) вузлі порівняння другий вхід схеми порівняння та третій інформаційних вхід комутатора з'єднаний з рівнем лог. 0, в кожному блоці порівняння вихід схеми порівняння j вузла порівняння з'єднаний з другим управляючим входом комутатора даного вузла і першим управляючим входом комутатора (j+1) вузла порівняння. Однак даний пристрій має обмежені функціональні можливості - медіанна фільтрація виконується тільки у ковзному "вікні" розміром т, яке складається із непарної кількості елементів. В основу винаходу поставлена задача створення пристрою медіанної фільтрації, в якому введення нових елементів і зв'язків між ними забезпечило б розширення функціональних можливостей шляхом забезпечення медіанної фільтрації як у ковзному "вікні" розміром m, так і ковзному "вікні" розміром mm. Поставлена задача вирішується тим, що пристрій медіанної фільтрації, який містить вхідний 2 регістр, входом якого є інформаційних вхід, (m -m)/2 регістрів, m-1 блоків порівняння, кожний i-й блок порівняння (i=1,…, m-1) містить (i+1) вузлів порівняння, кожний з яких містить схему порівняння та тривходовий комутатор, при цьому перші входи всіх схем порівняння з'єднані між собою, вихід вхідного регістра з'єднаний з першими входами всіх схем порівняння відповідних вузлів порівняння, другим інформаційним входом тривходового комутатора та з входом регістра з першого блока порівняння, в кожному i-у блоці порівняння вихід j-о регістра (j=1,…, i) з'єднаний з другим входом схеми порівняння та третім інформаційним входом тривходового комутатора і першим входом тривходового комутатора (j+1) вузла, вхід j-о регістра (i+1) блока порівняння з'єднаний з виходом тривходового комутатора j-о вузла порівняння і-о блока порівняння, вихід тривходового комутатора з (m+1)/2 вузла порівняння (m-1) блока порівняння з'єднаний з виходом медіани, в кожному і-у блоці порівняння перший вхід управління комутатора першого вузла порівняння з'єднаний з рівнем лог. 1, в кожному блоці порівняння в 0+1) вузлі порівняння другий вхід схеми порівняння та третій інформаційних вхід комутатора з'єднаний з рівнем лог. 0, в кожному блоці порівняння вихід схеми порівняння у вузла порівняння з'єднаний з другим 1 UA 108974 C2 5 10 15 20 25 30 35 40 45 50 55 управляючим входом комутатора даного вузла і першим управляючим входом комутатора (j+1) вузла порівняння, згідно винаходу, додатково містить блок фільтрації та сортування, тактові входи регістрів даного блока з'єднані з тактовим входом пристрою та тактовим входом вхідного регістра, виходи вузлів порівняння (m-1)-гo блока порівняння з'єднані з відповідними виходами блока фільтрації та сортування, (m-1) блоків сортування, кожний i-й блок сортування містить (іm+m) двовходових комутаторів, (іm+m) регістрів і (іm+m) вузлів порівняння, перші m входів першого блока порівняння з'єднані з виходами блока фільтрації та сортування, другі m входів з'єднані з рівнем лог. 0, в кожному і-у блоці сортування вихід k-го (k=1,…, іm+m) двовходового комутатора з'єднаний з входами k-го регістра, виходи якого з'єднані з третіми входами k-го вузла порівняння та першими входами (k+1)-о вузла порівняння, другі входи всіх вузлів порівняння з'єднані з виходами вхідного регістра, перший вхід управління k-го вузла порівняння з'єднаний з виходом управління (k+1)-го вузла порівняння, перший вхід управління l-о вузла порівняння з'єднаний з рівнем лог. 1, вихід к-то вузла порівняння з'єднаний з першим входом kго двовходового комутатора та k-м виходом і-о блока сортування, другі входи 1,…, іm двовходових комутаторів з'єднані з відповідними виходами (i-1)-го блока сортування, другі входи (іm+1),…, (іm+m) двовходових комутаторів з'єднані з рівнем лог. 0,. входи управління двовходових комутаторів з'єднані з входом управління, тактові входи регістрів з'єднані з тактовим входом, (m+1)/2 вихід (m-1)-гo блока сортування з'єднаний з виходом медіани в ковзному "вікні" розміром mm. Додаткове введення входу управління, тактового входу та (m-1) блоків сортування, кожний і2 й з блоків містить по (іm+m) двовходових комутаторів, регістрів і вузлів порівняння (m -m)/2-m, забезпечило виконання медіанної фільтрації як у ковзному "вікні" розміром m, так і ковзному "вікні" розміром mm. На фіг. 1 представлена блок-схема пристрою медіанної фільтрації, на фіг. 2 - схема блока фільтрації та сортування, на фіг. 3 - схема вузла порівняння, на фіг. 4 - схема блока сортування, де: 1 - вхід управління; 2 - тактовий вхід; 3 - інформаційний вхід; 4 - вхідний регістр; 5 - блок фільтрації та сортування; 6 - вихід медіани; 71-7m-1 блоки сортування; 8 - вихід медіани комутатор; 8 - медіани в ковзному "вікні" розміром mm; 91-9m-1 опоки порівняння; 10 - регістри; 11 - вузли порівняння; 12 - схема порівняння; 13 - тривходовий комутатор; 14-2-х вхідний комутатор; 15 - регістр. Вхід управління 1 з'єднаний з входами управління 2-х вхідних комутаторів блоків сортування 71-7m-1, тактовий вхід 2 з'єднаний з тактовими входами всіх регістрів пристрою, інформаційний вхід 3 з'єднаний з інформаційним входом регістра 4, вихід якого з'єднаний з входом регістра 10 1 та першими входами схем порівняння 12 та другими входами тривходових комутаторів 13 всіх вузлів порівняння 11, у кожному i-у блоці порівняння 9i - блока фільтрації та сортування 5 вихід регістра 10, з'єднаний з другим входом схеми порівняння 12, третім інформаційним входом тривходового комутатора 13 вузла порівняння 11j і першим входом тривходового комутатора 13 вузла порівняння 11j+i, вхід регістра 10, блока порівняння 9i+1 з'єднаний з виходом тривходового комутатора 13 вузла порівняння 11j блока порівняння 9i, у кожному з вузлів порівняння 11j вихід схеми порівняння з'єднаний з другим входом управління тривходового комутатора 13 даного вузла порівняння та першим входом тривходового комутатора 13 вузла порівняння 11j+1, перші входи управління тривходового комутаторів 13 всіх перших вузлів порівняння 11 1 блока фільтрації та сортування 5 з'єднані з рівнем лог. 1, треті входи тривходового комутатора 13 вузла порівняння 11i+1 блока порівняння 9i з'єднані з рівнем лог. 0, виходи вузлів порівняння 11 блока порівняння 9m-1 з'єднані з відповідними виходами блока фільтрації та сортування, перші т входів першого блока сортування 7і з'єднані з виходами блока фільтрації та сортування 5, другі т входів з'єднані з рівнем лог. 0, в кожному i-у блоці сортування 7i вихід 2-х вхідного комутатора 14k з'єднаний з входами регістра 15k, виходи якого з'єднані з другим входом схеми порівняння 12 та третім входом тривходового комутатора 13 вузла порівняння 11 k, другий вхід управління якого з'єднаний з виходом схеми порівняння 12 даного вузла порівняння 11 k та першим входом управління тривходового комутатора 13 вузла порівняння 11k+1 даного блока сортування 7i, перший вхід управління 1-го вузла порівняння з'єднаний з рівнем лог. 1, у кожному блоці сортування 7i перший вхід управління тривходового комутатора 13 вузла порівняння 11 1 з'єднаний з рівнем лог. 1, вихід вузла порівняння 11k кожного блока сортування 7i - з'єднаний з першим входом 2-х вхідного комутатора 14k та k-м виходом даного блока сортування, другі входи комутаторів 14і, …,14im блока сортування 7i з'єднані з відповідними виходами блока сортування 7i-1, а другі входи комутаторів 14(im+1),…, 14(im+m) блока сортування 7i з'єднані з 2 рівнем лог. 0, (m +1)/2 вихід блока сортування 7(m-1) з'єднаний з виходом медіани в ковзному "вікні" розміром mm. 2 UA 108974 C2 5 10 15 20 25 30 35 40 45 50 55 Пристрій медіанної фільтрації працює в двох режимах роботи: перший - медіанна фільтрація у ковзному "вікні" розміром m, другий - медіанна фільтрація у ковзному "вікні" розміром mm. У кожному із режимів роботи медіанна фільтрація виконується сортуванням чисел методом вставки. Процес медіанної фільтрації складається з послідовного переміщення вікна, сортуванні у визначеному порядку (за збільшенням, або зменшенням) елементів у середині вікна та формуванні медіани (значення середнього елементу). У першому режимі роботи (медіанна фільтрація у ковзному "вікні" розміром m) процес фільтрації зводиться до сортування m елементів і визначення середнього елемента (медіани). Сортування в пристрої розбивається на (m-1) етапів, в кожному i-му етапі (i=1,…, (m-1)) із і відсортованих елементів шляхом включення нового елемента з виходів регістра 4 формується відсортований масив із (i+1) елементів, який подається на наступний і-й блок сортування 9. Медіанна фільтрація у пристрої здійснюється за конвеєрним принципом, де реалізація кожного і-о етапу виконується і-й блоком порівняння 9і, який є сходинкою конвеєра. В кожному такті роботи у вхідний регістр 4 записується новий відлік. Число з виходів вхідного регістра 2 надходить на вхід регістра 10 першого блока порівняння 91, на перші входи всіх схем порівняння 12 і на другі інформаційні входи всіх комутаторів 13. В кожному i-у блоці порівняння 9, за допомогою схем порівняння 12 виконується порівняння числа з виходів регістра 4 з числами з виходів регістрів 10 даного блока. Порівняння чисел виконується схемами порівняння 12, які формують на виході сигнал лог. 0 коли число з виходу регістра 4 (перший вхід схеми порівняння) є більшим числа, що надходить на другий вхід, а сигнал лог. 1 - у всіх інших випадках. У кожному i-му блоці порівняння 9, результати порівнянь з виходів схем порівняння 12 використовуються для управління комутаторами 13. Формування інформації на виході комутатора 13 кожного вузла порівняння 11 виконується у відповідності з наступною формулою: , ІнфВх1 коли ВхУпр1  ВхУпр2  0  ВихКм  ІнфВх2, коли ВхУпр1  1 ВхУпр2  0, , ІнфВх3, коли ВхУпр1  ВхУпр2  1  1 де ВихКм - вихід комутатора 13, ІнфВх - інформація з першого входу комутатора, ІнфВх2 інформація з другого входу комутатора 13, ІнфВх3 - інформація з третього входу комутатора 13, ВхУпр1 - інформація на першому управляючому вході комутатора 13, ВхУпр2 - інформація на другому управляючому вході комутатора 13. За результатами попарних порівнянь в i-му блоці порівняння 9, здійснюється формування на виходах вузлів порівняння 11j відсортованого масиву із (i+1) чисел (максимальне число на виході 111, мінімальне - на виході 11(i+1)). У наступному такті здійснюється запис нового елемента даних в регістр 4, запис числа із виходів регістра 4 в регістр 10 першого блока порівняння 91 і запис відсортованих масивів з виходів попередніх блоків порівняння в регістри 10 наступних блоків порівняння. Після m-го такту роботи і кожного наступного такту роботи на виході 6 отримуємо результати медіанної фільтрації у ковзному "вікні" розміром m. У другому режимі роботи (медіанна фільтрація у ковзному "вікні" розміром mm) процес фільтрації зводиться до послідовного переміщення вікна фільтру на один стовпець (m 2 елементів), сортуванні m елементів і визначенні середнього елемента (медіани). Переміщення вікна на один стовпець здійснюється за ь тактів. Перед початком роботи на вхід управління 1 подаємо лог. 0, який встановлює комутатори 14 в блоках сортування 7, у положення коли на їх вихід надходить інформація з перших входів комутаторів 14. Перші m тактів роботи пристрій працює аналогічно як у першому режимі роботи. У m-у такті на вхід управління 1 подаємо лог. 1, яка установлює комутатори 14 в блоках сортування 7, у положення коли на їх вихід надходить інформація з других входів комутаторів 14. Після m-о такту роботи на виходах блока фільтрації 5 отримуємо відсортований масив із m чисел (максимальне число на виході 111, мінімальне - на виході 11m). У наступному (m+1) такті роботи в регістри 151-15m та 15m+1-152m першого блока сортування 71 записується відповідно відсортований масив із т чисел і m лог. 0, у вхідний регістр 4 m+1 елемент даних, а на вхід управління 1 подаємо лог. 0, який установлює комутатори 14 в блоках сортування 7i у положення коли на їх вихід надходить інформація з перших входів комутаторів 14. У (im)-му такті роботи на вхід управління 1 подаємо лог. 1, яка встановлює комутатори 14 в блоках сортування 7, у положення коли на їх вихід надходить інформація з других входів комутаторів 14. Після (Im)-го такту роботи на виходах блока фільтрації 5 отримуємо відсортований масив із m чисел, на виходах першого блока сортування 7 Х відсортований масив 3 UA 108974 C2 5 із 2m чисел, а на виходах (i-1)-го блока сортування 7(i-1) відсортований масив із im чисел. У наступному (im+1) такті роботи в регістри 15 блоків сортування 71-7i записуємо інформацію з других входів комутаторів 14. 2 Після m -го такту роботи і кожних наступних m тактів роботи на виході 8 отримуємо результати медіанної фільтрації у ковзному "вікні" розміром mm. ФОРМУЛА ВИНАХОДУ 10 15 20 25 30 35 40 Пристрій медіанної фільтрації, який містить вхідний регістр, входом якого є інформаційних вхід, 2 (m -m)/2 регістрів, (m-1) блоків порівняння, кожний і-й блок порівняння (і=1, …, m-1) містить (i+1) вузлів порівняння, кожний з яких містить схему порівняння та тривходовий комутатор, при цьому перші входи всіх схем порівняння з'єднані між собою, вихід вхідного регістра з'єднаний з першими входами всіх схем порівняння відповідних вузлів порівняння, другим інформаційним входом тривходового комутатора та з входом регістра з першого блока порівняння, в кожному іму блоці порівняння вихід j-огo регістра (j=1, …, i) з'єднаний з другим входом схеми порівняння та третім інформаційним входом тривходового комутатора і першим входом тривходового комутатора (j+1) вузла, вхід j-огo регістра (i+1) блока порівняння з'єднаний з виходом тривходового комутатора j-огo вузла порівняння i-ого блока порівняння, вихід тривходового комутатора з (m+1)/2 вузла порівняння (m-1) блока порівняння з'єднаний з виходом медіани, в кожному і-му блоці порівняння перший вхід управління комутатора першого вузла порівняння з'єднаний з рівнем логічної 1, в кожному блоці порівняння в (i+1) вузлі порівняння другий вхід схеми порівняння та третій інформаційних вхід комутатора з'єднаний з рівнем логічного 0, в кожному блоці порівняння вихід схеми порівняння j-огo вузла порівняння з'єднаний з другим управляючим входом комутатора даного вузла і першим управляючим входом комутатора (j+1) вузла порівняння, який відрізняється тим, що додатково містить блок фільтрації та сортування, тактові входи регістрів даного блока з'єднані з тактовим входом пристрою та тактовим входом вхідного регістра, виходи вузлів порівняння (m-1) блока порівняння з'єднані з відповідними виходами блока фільтрації та сортування, (m-1) блоків сортування, кожний і-й блок сортування містить (іm+m) двовходових комутаторів, (іm+m) регістрів і (іm+m) вузлів порівняння, перші m входів першого блока порівняння з'єднані з виходами блока фільтрації та сортування, другі m входів з'єднані з рівнем логічного 0, в кожному і-му блоці сортування вихід k-ого (k=1, …, іm+m) двовходового комутатора з'єднаний з входами k-ого регістра, виходи якого з'єднані з третіми входами k-ого вузла порівняння та першими входами (k+1) вузла порівняння, другі входи всіх вузлів порівняння з'єднані з виходами вхідного регістра, перший вхід управління (k+1), вузла порівняння з'єднаний з виходом управління (k+1) вузла порівняння, перший вхід управління 1-ого вузла порівняння з'єднаний з рівнем логічної 1, вихід k-ого вузла порівняння з'єднаний з першим входом k-ого двовходового комутатора та k-м виходом i-ого блока сортування, другі входи (1, …, іm) двовходових комутаторів з'єднані з відповідними виходами (i1) блока сортування, другі входи (іm+1), …, (іm+m) двовходових комутаторів з'єднані з рівнем логічного 0, входи управління двовходових комутаторів з'єднані з входом управління, тактові 2 входи регістрів з'єднані з тактовим входом, (m +1)/2 вихід (m-1) блока сортування з'єднаний з виходом медіани в ковзному "вікні" розміром mm. 4 UA 108974 C2 5 UA 108974 C2 Комп’ютерна верстка І. Скворцова Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 6