СПІВПРОЦЕСОР ДЛЯ ОБЧИСЛЕННЯ ФУНКЦІЇ РІЗНИЦІ ГАУСІАНІВ

1. Співпроцесор для обчислення функції різниці гаусіанів, який містить вхідний блок пам'яті, вхід якого є входом співпроцесора, перший блок фільтрації, вхід якого підключений до виходу вхідного блока пам'яті, проміжний блок пам'яті, вхід якого підключений до виходу першого блока фільтрації, другий блок фільтрації, вхід якого підключений до виходу проміжного блока пам'яті, блок пам'яті результатів, вихід якого є виходом співпроцесора, який відрізняється тим, що вихід другого блока фільтрації підключений до входу блока пам'яті результатів, причому кожен з блоків фільтрації виконаний як послідовно з'єднані перший смуговий фільтр, вхід якого є входом блока фільтрації, блок буферної пам'яті та другий смуговий фільтр, вихід якого є виходом блока фільтрації. 2. Співпроцесор за п. 1, який відрізняється тим, що кожен смуговий фільтр кожного з блоків фільтрації містить фазовий фільтр з нескінченною імпульсною характеристикою, вхід якого є входом смугового фільтра, суматор, вхід додавання якого під'єднано до входу фазового фільтра, а вхід віднімання - до виходу фазового фільтра, та містить фільтр нижніх частот зі скінченною імпульсною характеристикою, вхід якого під'єднаний до виходу суматора, а вихід під'єднаний до виходу смугового фільтра. 3. Співпроцесор за п. 2, який відрізняється тим, що фазовий рекурсивний фільтр в p-й октаві має передаточну характеристику: H1(z)=(b+cz-k+z-2k)/(1+cz-k+bz-2k), де b - коефіцієнт для регулювання ширини смуги пропускання; с - коефіцієнт для здебільшого регулювання фазового положення полюсів фільтра і, відповідно, центральної частоти смуги пропускання; z - комплексна змінна; k=2p-1 - кількість регістрів у затримках фазового рекурсивного фільтра р-ї октави, а фільтр нижніх частот у 1<р-й октаві має нулі на частотах, які дорівнюють верхнім частотам полюсів фазового фільтра, k=2p-1.

Корисна модель належить до галузі цифрової обробки зображень. Він використовується для виявлення країв та ознак зображення, таких як контури, кути, плями, та для аналізу руху об'єктів на основі цих ознак з визначенням їх положення або орієнтації, для попередньої обробки та вибору області інтересу, виявлення перекриття об'єктів і згладжування зображення, для знаходження ключових точок у зображенні на основі його ознак як у методі з масштабно-інваріантним перетворенням ознак (англ. Scale-Invariant Feature Transform, SIFT), для розпізнавання друкованих і рукописних символів, розпізнавання біометричних даних, таких як відбитки пальців чи характеристики ока, розпізнавання руху або поведінки об'єктів, наприклад їх траєкторії, а також для розпізнавання жестів чи виявлення жвавості людей. Цифрова обробка відеозображень з розпізнаванням графічних образів у реальному часі потребує великої продуктивності обчислювальних засобів. При цьому існуючі комп'ютерні засоби або не встигають виконувати обробку в реальному часі, коли багатоядерний мікропроцесор здатний обробити лише один кадр зображення за кілька секунд, або є надмірно високовартісними, такими як високоякісні графічні акселератори. Тому застосування спеціалізованих систем для цієї мети дозволяє одночасно забезпечити швидке оброблення відеозображень у реальному часі та знизити вартість необхідного обладнання. Сучасні методи цифрової обробки зображень, що ґрунтуються на пошуку у ньому ознак у вигляді кутів, країв, плям, такі як метод перетворення ознак, що інваріантний до масштабу (англ. scale-invariant feature transform, SIFT), дають змогу спростити вирішення багатьох задач оброблення та розпізнавання графічних образів. Вони ґрунтуються на перетворенні зображення у зображення ознак, що складені з кутів, країв та плям з подальшим виявленням в ньому характерних або ключових точок (feature points) і кодуванням їх дескрипторами. На основі цих дескрипторів створені різні алгоритми розпізнавання образів, такі як алгоритми розпізнавання обличь, відбитків пальців, рукописного тексту, дорожньої обстановки тощо. Причому такі алгоритми виявляються на один-три порядки простішими за поширені алгоритми згортувальних нейронних мереж, що використовуються з тією самою метою. Одним зі складних етапів алгоритму SIFT є перетворення вхідного чорно-білого зображення у стос зображень ознак, які мають різні масштаби [1]. Для такого перетворення вхідне чорно-біле зображення І(х, у) кілька разів обробляють за алгоритмом згортки з двовимірним гаусовим ядром G(x, у, ) з різним параметром масштабу з: L(x, у, ) = G(x, у, )*I(x, y), де * - символ згортки, х, у - координати пікселів, причому значення двовимірного гаусового ядра визначають за наступною формулою: . Результатом такої обробки є зображення гаусіанів L(x, у, ), яке ще називають просто гаусіаном, з масштабом е, яке виглядає як згладжене, розмите чорно-біле зображення зі ступенем розмиття, пропорційним ,. Для одного вхідного зображення будується стос зображень гуасіанів з різними значеннями .. Далі обчислюють функцію різниці гаусіанів (англ. Difference of Gaussians, DoG): D(x, у, )=L(x, у, qq)-L(x, у, ). де q - це масштабний коефіцієнт, який визначає, наскільки збільшується параметр - у кожному наступному зображенні у стосі, зазвичай або . У результаті обчислення функції різниці гаусіанів з різними масштабами У утворюється стос зображень різниці гаусіанів, який і є стосом зображень ознак, оскільки саме він містить краї, кути, плями та контури об'єктів, які необхідні для подальшого пошуку ключових точок. Причому у зображенні різниці гаусіанів з більшим масштабом а виражені, відповідно, ознаки більших розмірів. Таким чином, завдяки обробці стосу зображень різниці гаусіанів з різними масштабами забезпечується надійне розпізнавання об'єктів незалежно від їхнього масштабу, повороту чи часткового перекриття іншими об'єктами. Водночас швидкість і точність виконання всього алгоритму SIFT та подібних методів розпізнавання образів безпосередньо визначаються ефективністю обчислення функції різниці гаусіанів. Типовий співпроцесор для реалізації алгоритму SIFT [2] містить два блоки фільтрації, призначені для формування зображень гаусіанів шляхом згортки з двовимірним гаусовим ядром, що виконується у паралельно-послідовному режимі, а також суматор-віднімач для обчислення різниці гаусіанів (DoG). Причому розмір ядра згортки зазвичай становить не менше ніж 33х33, а мінімальне значення параметра масштабу ,=1,6. Недоліком такого співпроцесора є значна затримка виконання обчислень та високі апаратні витрати, пов'язані з реалізацією згортки з великими ядрами. Відомий також співпроцесор [3], у якому по два блоки фільтрації виконують згортку з двовимірним гаусовим ядром, результати яких віднімаються у суматорі-віднімачі. Завдяки реалізації двовимірної згортки у паралельній схемі одержують прискорення обчислень. Але використані гаусові ядра мають замалий розмір (від 3×3 до 15×15), що призводить до формування функцій різниці гаусіанів (DoG) з низькою точністю та обмежує їх використання лише для невеликих значень параметра масштабу х. Відомий співпроцесор [4], в якому для підвищення швидкодії і зменшення апаратних витрат згортку з двохвимірним гаусовим ядром заміняють на двокрокову згортку з одновимірним гаусовим ядром. Така згортка можлива завдяки властивості сепарабельності двовимірного гаусового ядра: . На першому кроці виконують згортку з ядром по рядках зображення I(x, у) (координата у), а на другому кроці виконують згортку з ядром по колонках (координата x), або навпаки. Для обчислення функції різниці гаусіанів використовують два блоки фільтрації зі скінченною імпульсною характеристикою для масштабу ) з проміжним блоком пам'яті між ними та два таких самих блоки фільтрації і блок пам'яті але для масштабу qq, різницю результатів фільтрації одержують на суматорі-віднімачі. Недоліком цього співпроцесора є те, що діапазон масштабів є обмеженим (р=1.6-4.0) через складність реалізації згортки з одновимірним гаусовим ядром, яка потребує використання фільтра зі скінченною імпульсною характеристикою довжиною до 25 і більше. Відомий співпроцесор [5], у якому для обчислень з великими значеннями а виконують децимацію зображення з подальшим обчисленням функції різниці гаусіанів, тобто, різниці гаусіанів одержують у кількох октавах. Для цього зображенню L(x, у, ,) виконують децимацію, після чого воно стає зображенням I(x, y) але зменшеним за розмірами удвічі, тобто, зображенням для другої октави і далі його обробляють на такому самому обладнанні, як і зображення першої октави. При цьому застосовують обладнання таке, як у співпроцесора [4]. Недоліком цього співпроцесора є те, що різниці гаусіанів у верхніх октавах для подальшої обробки необхідно додатково інтерполювати, або ж координати ключових точок, визначених у цих октавах, слід визначати за складним інтерполяційним алгоритмом, що суттєво ускладнює обчислення. Відомий співпроцесор [6], у якому замість кожного блока фільтрації зі скінченною імпульсною характеристикою використовують одну пару рекурсивних фільтрів, які ще називають фільтрами з нескінченною імпульсною характеристикою, сумарна амплітудно-частотна характеристика яких відповідає характеристиці блока фільтрації з одновимірним гаусовим ядром, завдяки чому є можливість збільшувати значення в при істотно меншій кількості обчислень, ніж у відповідному фільтрі зі скінченною імпульсною характеристикою. Для компенсації фазової нелінійності притаманної рекурсивному фільтру, рядок чи колонку зображення фільтрують (проводять згортку) двома рекурсивними фільтрами, один з яких фільтрує у прямому напрямку, а другий - зворотному. Результат фільтрації, еквівалентний згортці з ядром G(у, (), одержують як суму відфільтрованих кожним з рекурсивних фільтрів зображень з подальшим відніманням від цієї суми вхідного зображення. Недоліками цього співпроцесора є необхідність застосування рекурсивних фільтрів високого порядку для великих значень масштабу г, необхідність обчислень з підвищеною точністю для запобігання збудженню (нестабільності) рекурсивних фільтрів та, відповідно, великі апаратні витрати. Найближчим аналогом до корисної моделі є співпроцесор для обчислення різниці гаусіанів (DoG) [7], який містить вхідний блок пам'яті, вхід якого є входом співпроцесора, перший блок фільтрації, вхід якого підключений до виходу вхідного блока пам'яті, проміжний блок пам'яті, вхід якого підключений до виходу першого блока фільтрації, другий блок фільтрації, вхід якого підключений до виходу проміжного блока пам'яті, блок пам'яті результатів, вихід якого є виходом співпроцесора. В ньому згортку з двохвимірним гаусовим ядром заміняють на згортку з одновимірним ядром, яку застосовують до колонок зображення, а потім - до рядків. Найближчий аналог має додатково ще третій і четвертий блоки фільтрації, другий проміжний блок пам'яті та суматор-віднімач, який входами під'єднаний до виходів другого і четвертого блоків фільтрації, третій блок фільтрації, вхід якого під'єднаний до виходу вхідного блока пам'яті, а виходом - до входу другого проміжного блока пам'яті, вихід якого під'єднаний до входу четвертого блока фільтрації. Він функціонує за наступним принципом: чотири блоки фільтрації виконують згортку зображення з одновимірними гаусовими ядрами G(x, ,), G(у, (), G(x, q ) та G(y, q ). Причому блоки фільтрації, які підключені до виходу вхідного блока пам'яті виконують згортку по колонках зображення, а решта блоків фільтрації - по рядках. Результати обчислень другого і четвертого блоків фільтрації формують двовимірні гаусіани з масштабами та qq. Подальше віднімання суматором-віднімачем цих двох гаусіанів забезпечує отримання функції різниці гаусіанів (DoG), яка використовується для виділення ознак зображення. Блоки фільтрації аналогу обчислюють згортку з одновимірним гаусовим ядром з одержанням одного результату за такт на основі спеціалізованої схеми табличного множення на коефіцієнти та дерева суматорів, а також конвеєрної організації обчислень. Завдяки цьому, співпроцесор має високу продуктивність в один результуючий піксель за такт, не потребує блоків множення і тому він має зменшені апаратні витрати. Недоліком найближчого аналога є значні апаратні витрати, зумовлені використанням надмірної кількості блоків фільтрації та виконанням суматора-віднімача як окремого блока та складністю спеціалізованих схем табличного множення. Це обмежує діапазон масштабів д лише однією октавою ( 3,2), що, у свою чергу, знижує ефективність застосування співпроцесора для розпізнавання образів. В основу корисної моделі поставлено задачу створення такого співпроцесора обчислення функції різниці гаусіанів, який забезпечує зменшені апаратні витрати та високу пропускну здатність, при цьому підтримує широкий діапазон масштабів функції різниці гаусіанів. Поставлена задача вирішується тим, що співпроцесор для обчислення функції різниці гаусіанів, який містить вхідний блок пам'яті, вхід якого є входом співпроцесора, перший блок фільтрації, вхід якого підключений до виходу вхідного блока пам'яті, проміжний блок пам'яті, вхід якого підключений до виходу першого блока фільтрації, другий блок фільтрації, вхід якого підключений до виходу проміжного блока пам'яті, блок пам'яті результатів, вихід якого є виходом співпроцесора, згідно з корисною моделлю, вихід другого блока фільтрації підключений до входу блока пам'яті результатів, причому кожен з блоків фільтрації виконаний як послідовно з'єднані перший смуговий фільтр, вхід якого є входом блока фільтрації, блок буферної пам'яті та другий смуговий фільтр, вихід якого є виходом блока фільтрації. Кожен смуговий фільтр кожного з блоків фільтрації містить фазовий фільтр з нескінченною імпульсною характеристикою, вхід якого є входом смугового фільтра, суматор, вхід додавання якого під'єднано до входу фазового фільтра, а вхід віднімання - до виходу фазового фільтра, та містить фільтр нижніх частот зі скінченною імпульсною характеристикою, вхід якого під'єднаний до виходу суматора, а виходом під'єднаний до виходу смугового фільтра. Фазовий рекурсивний фільтр в p-й октаві має передаточну характеристику: H1(z)=(b+cz-k+z-2k)/(1+cz-k+bz-2k), де b - коефіцієнт для регулювання ширини смуги пропускання; с - коефіцієнт для здебільшого регулювання фазового положення полюсів фільтра і відповідно, центральної частоти смуги пропускання; z - комплексна змінна; k=2p-1 - кількість регістрів у затримках фазового рекурсивного фільтра р-ї октави, а фільтр нижніх частот у 1<р-й октаві має нулі на частотах, які дорівнюють верхнім частотам полюсів фазового фільтра, k=2p-1. У переважних прикладах виконання співпроцесора смуговий фільтр кожного з блоків фільтрації містить фазовий фільтр з нескінченною імпульсною характеристикою, вхід якого є входом смугового фільтра, суматор, вхід додавання якого під'єднано до входу фазового фільтра, а вхід віднімання - до виходу фазового фільтра, та фільтр нижніх частот зі скінченною імпульсною характеристикою, вхід якого підключений до виходу суматора, а вихід - до виходу смугового фільтра. Додатковою ознакою також є те, що фазовий фільтр має передаточну функцію , де b - коефіцієнт для регулювання ширини смуги пропускання; с - коефіцієнт для здебільшого регулювання фазового положення полюсів фільтра і відповідно, центральної частоти смуги пропускання; z - комплексна змінна; k=2p-1 - кількість регістрів у затримках фазового рекурсивного фільтра р-ї октави. Причому фільтр нижніх частот у 1<р-й октаві має нулі на частотах, які дорівнюють частотам полюсів фазового фільтра, що відповідають смугам пропускання на верхніх частотах. Окрім того, фільтр нижніх частот у практичному застосуванні, при значенні О=1,6 та ==3,2, у першій та другій октавах, відповідно, має передаточну функціюH1(z)=0,277+0,447z-1+0,277z-2. (2) З вищезазначених додаткових ознак випливає, що кожен фазовий фільтр, згідно з (1), має однакову структуру за винятком того, що для р-ї октави структура фільтра має кількість регістрів затримки, що дорівнює 2p-1. Додатковою ознакою до (1) є те, що коефіцієнти b і с визначають з точністю не більше ніж з 8 двійковими розрядами і їх представляють у знакозмінній двійковій системі, а відповідні помножувачі на ці константні коефіцієнти виконані як дерева суматорів. Така ознака дозволяє зменшити апаратурну складність конструкції шляхом можливості використання примітивних помножувачів. Поставлена задача вирішується тим, що блоки фільтрації мають менші апаратні витрати, за такі самі блоки, використані для аналогів завдяки тому, що для проведення обчислювальних операцій рекурсивним фільтром необхідно в кілька разів менше операцій множення, ніж для проведення таких операцій фільтром зі скінченною імпульсною характеристикою, рекурсивні фільтри також здатні обчислювати функцію різниці гаусіанів для великих значень масштабу а. Загальна передаточна функція кожного блока фільтрації з урахуванням запису у блок буферної пам'яті з інкрементом адрес (за послідовно зростаючими адресами), а читанням з нього - з декрементом адрес (за послідовно спадаючими адресами) дорівнює добутку передаточних функцій його фазових фільтрів та фільтрів нижніх частот, наприклад, для фільтрації рядків: Hx(z)=(1-H1(z)).H2(z).(1-H1(z)).H2(z); і з великою точністю відповідає передаточній функції різниці гаусіанів в одновимірному випадку HxG(z), тобто Hx(z)=HxG(z), Hx(z)=Hxqx(z)-Hxx(z), де Hxqx(z), - передаточна функція фільтра згортки з ядром G(x,qG), Hxx(z) - передаточна функція фільтра згортки з ядром G(x, ,), які використовували в найближчому аналогу. Завдяки сепарабельності двовимірної функції різниці гаусіанів, фільтрація зображення спочатку першим, а потім другим блоками фільтрації дає результат обчислення D(x, y, ); Віднімання від вхідних даних результату фільтрації фазовим рекурсивним фільтром з передаточною функцією (1) відповідає передаточній функції смугового фільтра, яка дорівнює Hp(z)=1-H1(z). (3) Причому запропонований смуговий фільтр, на відміну від інших реалізацій смугових фільтрів, має невелику чутливість до похибки представлення своїх коефіцієнтів, а також гарантовано дає нульовий відгук на нульовій частоті. Крім того, на відміну від традиційних смугових рекурсивних фільтрів, він є стабільним для дуже низьких частот пропускання [8], Це дозволяє обмежити розрядність коефіцієнтів b і с лише вісьмома розрядами, що як правило, дає змогу замінити складну схему множення на суттєво простішу. Схеми множення на такі коефіцієнти виконують у вигляді невеликого дерева суматорів або табличним способом так само, як це зроблено у найближчому аналозі. Також у першій октаві амплітудно-частотна характеристика двох таких смугових фільтрів, з'єднаних послідовно, з невеликим відхиленням збігається з амплітудно-частотною характеристикою фільтра з одновимірним гаусовим ядром HxG(z), при відповідному підборі коефіцієнтів b і с: (4) де Hp(z) - це передаточна функція смугового фільтра (3) при фільтрації даних, зчитаних за зростаючими адресами, H2(z) - це передаточна функція фільтра нижніх частот при фільтрації даних, зчитаних за зростаючими адресами, Hp(-z) - це передаточна функція смугового фільтра (3) при фільтрації даних, зчитаних за спадаючими адресами, H2(-z) - це передаточна функція фільтра нижніх частот при фільтрації даних, зчитаних за спадаючими адресами. Отже, на відміну від інших видів цифрових фільтрів, форма амплітудно-частотної характеристики (4) наближається до форми амплітудно-частотної характеристики функції різниці гаусіанів при лише другому порядку смугового фільтра у кожному блоці фільтрації (3). Таких властивостей не мають блоки фільтрації усіх відомих аналогів. Існують більше двадцяти різних схем реалізації фазового рекурсивного фільтра з передаточною функцією (1), серед яких можна вибрати схему з мінімальною кількістю апаратних витрат та мінімальною розрядністю коефіцієнтів [9]. Зокрема, існують схеми, у яких застосовано лише два помножувачі, її і використовували для прикладу реалізації конструкції співпроцесора. Фільтр нижніх частот зі скінченною імпульсною характеристикою у першій та другій октаві, що входить до складу смугового фільтра кожного з блоків фільтрації, має другий порядок, тобто, має другий степінь полінома від змінної z у його передаточної функції H2(z) і також при своїй реалізації має не більше двох помножувачів, які так само реалізуються як дерева суматорів або табличним способом. З урахуванням того, що для використання функції різниці гаусіанів немає значення загальний коефіцієнт підсилення співпроцесора, можна один з коефіцієнтів фільтра зі скінченною імпульсною характеристикою виконати тривіальним, наприклад, рівним 1. Тоді для цього фільтра буде необхідний лише один помножувач. Отже, у запропонованому співпроцесорі для реалізації блока фільтрації в першій октаві досить виконати лише 6 множень. У ньому на один результуючий піксел одного масштабу припадає 12 множень. Для порівняння, у блоці фільтрації найближчого аналога виконується від 5 до 15 множень залежно від масштабу є. Відповідно, через те, що найближчий аналог обчислює лише функцію з одним масштабом, кількість множень в ньому становитиме від 28 до 60 для одержання одного результату з урахуванням того, що для обчислення функції різниці гаусіанів йому потрібно вдвічі більше блоків фільтрації, які мають різні масштаби. Таким чином, запропонований співпроцесор має у 2.3 - 5 разів менші апаратні витрати, принаймні на обчислення множень. Варто додати, що це відношення дещо зменшується не більше, ніж у два рази у випадку, коли аналог обчислює результати з кількома масштабами одночасно. Збільшення кількості регістрів у затримках цифрових фільтрів у k разів призводить до того, що початкова амплітудно-частотна характеристика таких фільтрів зменшує у k разів свій масштаб по осі частот. Як результат, передаточна функція (3) при k=1 має одну смугу пропускання на частоті fр, при k=2, тобто, у другій октаві - дві смуги пропускання на частотах fp/2 та fs/2 – fp/2, а при k=4, тобто, у третій октаві - чотири смуги пропускання на частотах fр/4, fs/4-fр/4, fs/4+fp/4 та fs/2-fp/4, де fs - частота дискретизації послідовності даних, що обробляються. При k=2 і при k=4 порядок фазового фільтра збільшується до 4 і 8, відповідно, але кількість операцій множення залишається тією самою. За рахунок цього одержують мінімізовані апаратні витрати на побудову фільтрів при великому масштабі к в порівнянні з аналогами. Отже, щоб одержати істинні результати функції різниці гаусіанів, слід приглушити одну високочастотну смугу у другій октаві та три високочастотні смуги у третій октаві, піки яких розташовані на частотах, що відповідають полюсам фільтра (1) чи (3). З цією метою в запропонованому співпроцесорі застосовують нерекурсивний фільтр нижніх частот, який служить маскуючим фільтром, бо пропускає лише нижні частоти. Для цього він у співпроцесорі другої октави має два нулі передаточної функції, що компенсують полюси передаточної функції фазового рекурсивного фільтра, які мають таку саму частоту, а у співпроцесорі третьої октави - шість нулів, відповідно. Метод такої фільтрації ґрунтується на тому, що фільтр нижніх частот відсікає високочастотні смуги смугового фільтру за рахунок компенсації полюсів, які визначають частоту пропускання, нулями, які визначають частоту придушення. У загальному випадку, для фільтрів на основі фазових фільтрів цей метод описано в [10]. Фільтр з передаточною функцією (2) має положення нулів, яке в першій октаві сприяє покращенню сумарної амплітудно-частотної характеристики, а в другій октаві компенсує повністю або частково полюси фазового рекурсивного фільтра для р=1.6 і більше. Як результат, запропонований співпроцесор має змогу обчислювати функцію різниці гаусіанів у кількох октавах, тобто, для і=12,8 і більше, не збільшуючи суттєво апаратні витрати на верхніх октавах і не виконуючи децимацію зображення, на що не здатні усі аналоги, включаючи найближчий аналог. Суть корисної моделі пояснюють креслення, на яких зображено: Фіг. 1 - структурна схема співпроцесора; Фіг. 2 - структурна схема кожного з блоків фільтрації співпроцесора; Фіг. 3 - схема смугового фільтра на рівні регістрових передач; Фіг. 4 - схема блока множення на коефіцієнт; Фіг. 5 - амплітудно-частотна характеристика співпроцесора при обчисленні у першій октаві для масштабу а1=1,6; Фіг. 6 - амплітудно-частотні характеристики смугового фільтра та його складових у другій октаві: Фіг. 7 - приклад використання співпроцесора для формування дев'яти зображень різниць гаусіанів у трьох октавах, з трьома масштабами в кожній. Позначення на фігурах: 1 - вхідний блок пам'яті; 2 - вхід співпроцесора; 3 - перший блок фільтрації; 4 - проміжний блок пам'яті; 5 - другий блок фільтрації; 6 - блок пам'яті результатів; 7 - вихід співпроцесора; 8 - перший смуговий фільтр; 9 - блок буферної пам'яті; 10 - другий смуговий фільтр; 11 - вхід блока фільтрації; 12 - вихід блока фільтрації; 13 - фазовий фільтр з нескінченною імпульсною характеристикою; 14 - суматор; 15 - фільтр нижніх частот зі скінченною імпульсною характеристикою; 16 - перший суматор фазового фільтра; 17 - другий суматор фазового фільтра; 18 - третій суматор фазового фільтра; 19 - перший помножувач фазового фільтра; 20 - другий помножувач фазового фільтра; 21 - перша затримка фазового фільтра; 22 - друга затримка фазового фільтра; 23 - третя затримка фазового фільтра; 24 - четверта затримка фазового фільтра; 25 - перший помножувач фільтра нижніх частот; 26 - другий помножувач фільтра нижніх частої: 27 - перший суматор фільтра нижніх частот; 28 - другий суматор фільтра нижніх частот; 29 - перший регістр фільтра нижніх частот; 30 - другий регістр фільтра нижніх частот; 31 - вхід помножувача; 32 - перший суматор помножувача; 33 - другий суматор помножувача; 34 - вихід помножувача; 35 - вхід системи для обчислення функцій різниці гаусіанів; 36.1 - блок обчислення функцій різниці гаусіанів першої октави; 36.2 - блок обчислення функцій різниці гаусіанів другої октави; 36.3 - блок обчислення функцій різниці гаусіанів третьої октави; 37.1 - співпроцесор для обчислення функцій різниці гаусіанів з масштабом 31; 37.2 - співпроцесор для обчислення функцій різниці гаусіанів з масштабом 32; 37.3 - співпроцесор для обчислення функцій різниці гаусіанів з масштабом л3; 38.1 - вихід функції різниці гаусіанів з масштабом 31.1 в першій октаві; 38.2 - вихід функції різниці гаусіанів з масштабом 31.2 в другій октаві; 38.3 - вихід функції різниці гаусіанів з масштабом 31.3 в третій октаві; 39.1 - вихід функції різниці гаусіанів з масштабом 32.1 в першій октаві; 39.2 - вихід функції різниці гаусіанів з масштабом 32.2 в другій октаві; 39.3 - вихід функції різниці гаусіанів з масштабом 32.3 в третій октаві; 40.1 - вихід функції різниці гаусіанів з масштабом і3.1 в першій октаві; 40.2 - вихід функції різниці гаусіанів з масштабом 43.2 в другій октаві; 40.3 - вихід функції різниці гаусіанів з масштабом 43.3 в третій октаві. На Фіг. 1 зображено структурну схему співпроцесора, яка містить вхідний блок пам'яті 1, вхід якого є входом співпроцесора 2, перший блок фільтрації 3, вхід якого підключений до виходу вхідного блока пам'яті 1, проміжний блок пам'яті 4, вхід якого підключений до виходу першого блока фільтрації 3, другий блок фільтрації 5, вхід якого підключений до виходу проміжного блока пам'яті 4, блок пам'яті результатів 6, вхід якого підключений до виходу блока другий блок фільтрації 5, а вихід якого є виходом співпроцесора 7. На Фіг. 2 зображено структурну схему кожного з блоків фільтрації, який містить перший смуговий фільтр 8, вхід якого є входом блока фільтрації 11, блок буферної пам'яті 9, вхід якого підключений до першого смугового фільтра 8, та другий смуговий фільтр 10, вхід якого підключений до блока буферної пам'яті 9 та вихід якого є виходом блока фільтрації 12. Кожен зі смугових фільтрів 8 та 10 містить фазовий фільтр з нескінченною імпульсною характеристикою 13, вхід якого є входом смугового фільтра 8 або 10, суматор 14, вхід додавання якого під'єднано до входу фазового фільтра 13, а вхід віднімання - до виходу фазового фільтра 13, та містить фільтр нижніх частот зі скінченною імпульсною характеристикою 15, , вхід якого підключений до виходу суматора 14, а виходом до виходу смугового фільтра 8 або 10. На Фіг. 3 зображено схему смугового фільтра на рівні регістрових передач в можливій реалізації співпроцесора. Вона містить перший 16, другий 17 і третій 18 суматори фазового фільтра, перший помножувач фазового фільтра на коефіцієнт b 19, другий помножувач фазового фільтра на коефіцієнт с 20, першу 21 і другу 22 затримки фазового фільтра на 2k регістрах, третю 23 і четверту 24 затримки фазового фільтра на k регістрах, перший помножувач фільтра нижніх частот на коефіцієнт є 25, другий помножувач фільтра нижніх частот на коефіцієнт d 26, перший 27 і другий 28 суматори фільтра нижніх частот та перший 29 і другий 30 регістри фільтра нижніх частот. Вхід затримки 22 під'єднаний до виходу помножувача 19, а вихід - до входу суматора 17, другий вхід якого під'єднаний до виходу затримки 23, вхід якої під'єднаний до виходу помножувача 20, який також під'єднаний виходом до входу затримки 24. Суматор 18 своїми входами під'єднаний до виходів затримок 21 і 24, а також помножувача 19, а виходом -до виходу фазового фільтра 13. Вхід фільтра нижніх частот зі скінченною імпульсною характеристикою 15 під'єднаний до входу першого регістра 29, вихід якого під'єднаний до входу помножувача 25 і входу другого регістра 30, вихід якого під'єднаний до першого входу суматора 27, другий вхід якого під'єднаний до входу фільтра нижніх частот 15, а виходом під'єднаний до входу помножувача 26, Суматор 28 входами під'єднаний до виходів помножувачів 25 і 26, а виходом - до виходу фільтра нижніх частот 15. Передаточна функція (2) фільтра нижніх частот була одержана на основі обчислених полюсів передаточної функції (1) при k=2. На Фіг. 4 зображено функціональну схему одного з помножувачів двійкових чисел з фіксованою комою на коефіцієнт, який застосований у фільтрах. Він містить перший суматор помножувача 32, входами підключений до входу помножувача 31, і другий суматор помножувача 33, перший вхід якого з'єднаний з виходом суматора 32, другий вхід з'єднаний зі входом 31, а вихід - з виходом помножувача 34. Причому входи суматора 32 під'єднані до входу 31 зі зсувом двійкового даного на h і g розрядів вправо, а другий вхід суматора 33 - зі зсувом на f розрядів вправо. Наприклад, при множенні на коефіцієнт b=76/256=0.0100112 слід виконати зсув на h=6, g=5 і f=2 розрядів, а якщо множення на коефіцієнт с=-220/256=-0.11011b=1.00100b, то h=6, g=3 і f=0, причому тут другий вхід суматора 33 є входом з інверсією. Алгоритм обчислення функції різниці гаусіанів D(x, у у) реалізують у описаному співпроцесорі наступним чином. Спочатку вхідне зображення І(х, у) розміром m рядків на n колонок зі входа співпроцесора 2 записують у вхідний блок пам'яті 1. Потім з блока пам'яті 1 читають значення пікселів по рядках зображення, які надходять на вхід першого блока фільтрації 3, тобто, у=0,…,n-1. Перший смуговий фільтр 8 першого блока фільтрації 3 фільтрує кожен рядок зображення з початку до кінця і результати фільтрації записують у блок буферної пам'яті 9 за зростаючими адресами, тобто, у=0,…,n-1. Потім ці відфільтровані рядки зображення зчитують за спадаючими адресами з блока 9, тобто, у порядку y=n-1,…,0, на вхід другого смугового фільтра 10, який виконує фільтрацію цього рядка в протилежному напрямку. Результати фільтрації рядків записують в проміжний блок пам'яті 4 також за спадаючими адресами, тобто, у=n-1,...,0. Після заповнення проміжного блока пам'яті 4 відфільтрованими рядками зображення з нього зчитують пікселі колонок зображення за зростаючим адресами, тобто, х=0,…,m-1, які фільтруються першим смуговим фільтром 8 другого блока фільтрації 5. Результати фільтрації записуються в блок буферної пам'яті 9 за зростаючими адресами, тобто, х=0,…,m-1. Далі пікселі колонок зображення зчитуються з блокі буферної пам'яті 9 другого блокі фільтрації 5 за спадаючими адресами, тобто, х=m-1,…, 0 і подаються на фільтрацію в другий смуговий фільтр 10 другого блокі фільтрації 5. Результати фільтрації D(x, у, у) фільтром 10 записуються в блок пам'яті результатів 6 за зростаючими адресами х=0,…,m-1. Далі одержані результати функції різниці гаусіанів D(x, у, у) читаються з блока пам'яті результатів 6 і видаються на вихід 7 співпроцесора. Обробка даних у співпроцесорі ведеться за конвеєрним принципом. В той час, коли дані колонок наявного зображення з проміжного блока пам'яті 4 читаються, обробляються в другому блоці фільтрації 5 і результати записуються в блок пам'яті результатів 6, зі вхідного блока пам'яті 1 дані наступного зображення читаються по рядках, обробляються в першому блоці фільтрації 3 і записуються в проміжний блок пам'яті 4, а результати обробки попереднього зображення з блока пам'яті результатів 6 видаються на вихід 7 співпроцесора. Приклад реалізації фільтрування рядка або колонки зображення в межах одного зі смугових фільтрів виконується в схемі смугового фільтра на рівні регістрових передач (Фіг. 3). В ньому затримки 21-24 виконані як ланцюжки k та 2k регістрів, тобто в першій октаві затримки 21 і 22 мають по два регістри, а затримки 23 і 24 - по одному регістру. Фазовий фільтр 13 кожного з блоків фільтрації згідно з його передаточною функцією (1) виконує обчислення в першій октаві, які задані різницевим рівнянням: yi=b xi+c xi-1+x1-2-c yi-1-b у1-2, де xі - вхідні дані фільтра; xi-1, xi-2 - вхідні дані, затримані на один і два такти; yі - результат фільтрації; yi-1, yi-2 - результат фільтрації, затриманий на один і два такти. Для зменшення кількості множень на коефіцієнти b і с це рівняння перетворене у наступні рівняння: qi=xi-c.qi-1-b.qi-1; (5) yi=b.qi+c.qi-1+ qi-2, де qi - проміжний результат обчислень в суматорах 16 і 17; qi-2 - проміжний результат, який зберігається в затримці 21; c.qi-1 - результат множення на коефіцієнт с, який зберігається в затримках 23 і 24; b.qi-2 - результат множення на коефіцієнт b, який зберігається в затримці 22. Фазовий рекурсивний фільтр має одиничне значення амплітудно-частотної характеристики на всіх частотах, але виконує перекручування фази на кут а на частоті fp, що відповідає полюсам передаточної функції (1), а на інших частотах фаза його фазочастотної характеристики наближається до 0 та до 2 ,. Віднімання відліків результатів уi від відліків вхідних даних хi на суматорі 14 призводить до того, що їх різниця прямує до нуля на нижніх і верхніх частотах, а на частоті fр результат дорівнює 2хі. Як результат, фільтр 13 разом з суматором 14 виконує смугову фільтрацію з піком смуги пропускання на частоті fp. Такий смуговий фільтр не має затримки в кількості тактів. Процес фільтрування в схемі фазового фільтра 13 у першій октаві при k=1 виконується по тактах. Спочатку затримки 21-24 встановлюють в нульовий стан. В нульовому такті дане х0 через вхід смугового фільтра надходить на вхід суматора 16, на інший вхід якого надходить нульове дане з виходу суматора 17. З виходу суматора 16 видається результат q0=x0, який надходить на входи помножувачів 19 і 20, а також записується в перший регістр затримки 21. Помножувач 20 видає добуток cq0=cx0, який записується в затримки 23 і 24, а помножувач 19 видає добуток bq0=bх0, який записується в перший регістр затримки 22. На вхід суматора 18 затримки 21, 24 видають нульове значення і суматор 18 видає суму у0=bx0. В першому такті суматор 17 виконує додавання операнда сх0 з виходу затримки 23 з нулем з виходу затримки 22 і результат сх0 віднімається від вхідного даного xi на суматорі 16, з виходу якого операнд q1=х1-сх0 записується в затримку 21, помножується на b і на с в помножувачах 19, 20. Результати множення bqi та сqi записуються в затримки 22, 23 і 24. На вхід суматора 18 надходить нуль з другого регістра затримки 21, операнд bq1 з виходу помножувача 19 і затриманий операнд cq0 з затримки 24 і він видає результат у1=bq1+cq0 на вихід фазового фільтра. В цьому ж такті дані q0 і bqo з перших регістрів затримок 21 і 22 переписуються у їхні другі регістри. У другому такті суматор 17 виконує додавання операнду сх1 з виходу затримки 23 з операндом bq0 з виходу затримки 22 і результат bq0-сх1 віднімається від вхідного даного х2 на суматорі 16, з виходу якого операнд q2=x2-bq0-cx1 записується в затримку 21, помножується на b і на с в помножувачах 19, 20. Результати множення bq1 та cq1 записуються в затримки 22, 23 і 24. На вхід суматора 18 надходить q0 з другого регістра затримки 21, операнд bq1 з виходу помножувача 19 і затриманий операнд cq1 з затримки 24 і він видає результат у2=bq1+cq1+q0 на вихід фазового фільтра. В цьому ж такті дані q1 і bq1 з перших регістрів затримок 21 і 22 переписуються у їхні другі регістри. Слід зауважити, що одержані вирази для операндів q2 та у2 збігаються з виразами (5) при і=2. Оскільки схема фазового фільтра не змінюється під час обчислень і вона не має зовнішніх керуючих сигналів крім встановлення в нуль її регістрів, у подальших тактах i=3,4,… процес фільтрування продовжується з виконанням тих самих дій, як і в другому такті. В блоці фільтрації другої і третьої октав фазовий фільтр має вдвічі і в чотири рази довші затримки, тобто, кількість регістрів в них збільшена удвічі і в чотири рази, відповідно, завдяки чому амплітудно-частотна характеристика смугового фільтра має 2 і 4 смуги пропускання. Віднімання від вхідних даних хi - результату фільтрації фазовим рекурсивним фільтром уі виконується в кожному такті на суматорі-віднімачі 14, результатом чого є смугова фільтрація з передаточною функцією (3): ui=xi-yi, Фільтр нижніх частот 15 виконує відсікання піків на верхніх частотах, а також покращує амплітудно-частотну характеристику смугового фільтра у першій октаві. У першій та другій октавах він виконує обчислення наступного різницевого рівняння =e.ui-1+d.(ui+ui-1), (6) де е=0,447, d.=0.277 - коефіцієнти фільтра (2); ui - проміжний результат з виходу суматора 14; ui-1, ui-2 - проміжні результати, які зберігаються в регістрах 29 і 30, відповідно. Процес фільтрування в схемі фільтра нижніх частот 15 виконується по тактах. Спочатку регістри 29, 30 встановлюють в нульовий стан. В нульовому такті дане u0 з виходу суматора-віднімача 14 записується в регістр 29 і надходить на вхід суматора 27, на інший вхід якого надходить нульове дане з виходу регістра 30 і результат додавання u0 помножується у помножувачі 26 на коефіцієнт d. Помножувач 25 помножує нуль з виходу регістра 29 на коефіцієнт e, нульовий результат якого додається у суматорі 28 до операнда d.u0 з виходу помножувача 26 з одержанням вихідного даного v0=d.u0, В першому такті дане u1 з виходу суматора-віднімача 14 записується в регістр 29 і надходить на вхід суматора 27, на інший вхід якого надходить нульове дане з виходу регістра 30 і результат додавання u1 помножується у помножувачі 26 на коефіцієнт d. Помножувач 25 помножує операнд u0 з виходу регістра 29 на коефіцієнт e, результат якого е.u0 додається у суматорі 28 до операнда d.u0 з виходу помножувача 26 з одержанням вихідного даного v1=е.u0+du0. В цьому ж такті дане u0 з регістра 29 переписується у регістр 30. В другому такті дане u2 з виходу суматора-віднімача 14 записується в регістр 29 і надходить на вхід суматора 27, на інший вхід якого надходить операнд u0 з виходу регістра 30 і результат додавання u2+u0 помножується у помножувачі 26 на коефіцієнт d. Помножувач 25 помножує операнд u1 з виходу регістра 29 на коефіцієнт e, результат якого е.u0 додається у суматорі 28 до операнда d(u2+u0) з виходу помножувача 26 з одержанням вихідного даного v2=е.u1+d(u2+u0). В цьому ж такті дане u1 з регістра 29 переписується у регістр 30. Слід відмітити, що одержані вираз для результату v2 збігається з виразом (6) при i=2. Отже, у подальших тактах і=3, 4,… процес фільтрування продовжується з виконанням тих самих дій, як і в другому такті. В умовах реалізації заявленого співпроцесора коефіцієнти фазового фільтра можуть дорівнювати bі=76/256, b2=122/256, b3=156/256, і с1=-220/256, c2=- 292/256, с3=-360/256 для масштабів функції різниці гаусіанів, що дорівнюють р1=1,6, та , відповідно, які дорівнюють масштабам, які використані в аналогах. Дані значення коефіцієнтів були знайдені шляхом мінімізації середньоквадратичного відхилення амплітудно-частотної характеристики оригінальної функції різниці гаусіанів від амплітудно-частотної функції (4) для першої октави. Ці значення представляються не більше ніж вісьмома двійковими розрядами коефіцієнтів з фіксованою комою. Множення на них виконується схемою, такою як на Фіг. 4. Фіг. 5 ілюструє збіг графіків амплітудно-частотних характеристик найближчого аналога (пунктирна лінія) і запропонованого співпроцесора (суцільна лінія) при обчисленні різниці гаусіанів для масштабу 1=1,6. Графіки побудовані у системі Scilab при моделюванні алгоритмів цих співпроцесорів. Порівняння цих графіків показує невелику похибку апроксимації функції різниці гаусіанів у запропонованому співпроцесорі. Також одержаний збіг таких графіків, одержаних при моделюванні співроцесора, описаного мовою VHDL з урахуванням розрядностей усіх даних і коефіцієнтів. Крім того, основними вимогами до амплітудно-частотної характеристики функції різниці гаусіанів є задовільна апроксимація амплітудно-частотної характеристики ланки диференціатора (крутизна кривої характеристики 6 дБ на октаву) на проміжку від нуля до центральної частоти смуги пропускання, зокрема, нульове її значення на нульовій частоті, а також придушення сигналу на частотах вище частоти піка. У запропонованому співпроцесорі ці вимоги виконуються гідним чином. Фіг. 6 ілюструє одержання амплітудно-частотної характеристики співпроцесора при обчисленні функції різниці гаусіанів у другій октаві при k=2, При цьому смуговий фільтр, який сформований фільтром 13 та суматором 14 у його амплітудно-частотній характеристиці (3) має дві смуги пропускання на частотах fр та fs/2-fр. Фільтр нижніх частот 15 має у своїй амплітудно-частотній характеристиці смугу придушення з центральною частотою fs/2-fр, за рахунок чого він маскує другу смугу пропускання в характеристиці і в результаті дає амплітудно-частотну характеристику , яка є гідною апроксимацією функції різниці гаусіанів у другій октаві, На Фіг. 7. показане типове використання співпроцесора у системі, яка обчислює по три функції різниці гаусіанів у трьох октавах. Система складається з блоків обчислення функцій різниці гаусіанів першої октави 36.1, другої октави 36.2, третьої октави 36.3, які входами під'єднані до входу системи і виходи функції різниці гаусіанів яких 38,1, 39,1, 40,1, 38,2, 39,2, 40,2, 38,3, 39,3, 40,3 є виходами системи, на які видаються результати дев'яти масштабів у трьох октавах, починаючи з 31=1,6. Блок обчислення функції різниці гаусіанів першої октави 36.1 складається з трьох співпроцесорів для обчислення функцій різниці гаусіанів з масштабом і1 37,1, з масштабом 12 37,2 і з масштабом 33 37,3, входи яких з'єднані зі входом блока 36,1, на вихід 38,1 якого надходять результати функції для першої октави з масштабом н1.1==1, на вихід 39,1 - результати з масштабом , а на вихід 40,1 - результати з масштабом . Блок 36,2 має три співпроцесори, фільтри яких налаштовані з параметром k=2 і обчислюють функції з масштабами , та , результати яких виводяться на виходи 38.2, 39.2 і 40.2, відповідно. Блок 36.3 також має три співпроцесори, фільтри яких налаштовані з параметром k=4 і обчислюють функції з масштабами , та результати яких виводяться на виходи 38,3, 39,3 і 40,3, відповідно. В умовах такої реалізації, для мінімізації пам'яті вхідний блок пам'яті 1 може бути виконаний окремо і входом бути підключений до входу системи 35, а виходом з'єднаний зі входами першого блока фільтрації 3 усіх співпроцесорів системи. Результатом обчислень у даній системі є стос із 9 зображень ознак D(x, у, у). Цей стос далі використовують у реалізації алгоритму SIFT наступним чином. У стосі вибирають З сусідні зображення з масштабами н, qq і q22 і шукають такі пікселі D(x, у, qq), які за абсолютною величиною є більшими за сусідні пікселі у цих трьох зображеннях. Знайдені пікселі є центрами кандидатів у шукані ключові точки. Таким чином, дана система дає змогу шукати ключові точки з сімома параметрами масштабів одночасно. Слід зауважити, що у відомих аналогів менша кількість застосованих масштабів. Джерела інформації: 1. Lowe, D.G. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision. Vol. 60, pp. 91-110, 2004, https://doi.org/10.1023/B:VlSI.0000029664.99615.94 2. Li S, -A., Wang W. -Y., Pan W. -Z., Hsu C. -C. J., Lu C. -K. FPGA-Based Hardware Design for Scale-Invariant Feature Transform, IEEE Access, vol. 6, pp. 43850-43864, 2018, https://doi.org/ 10.1109/ACCESS.2018.2863019, 3. Reconfigurable hardware acceleration method and system for Gaussian pyramid construction: patent US 2022/0351432 Al USA: G06T 11/40; G06T 3/40; G06T 1/60; Filed: 28.04. 2022; Date of Patent: 3. 11. 2022, 15 p. 4. Qasaimeh M., Sagahyroon A. Shanableh T. A parallel hardware architecture for Scale Invariant Feature Transform (SIFT), 2014 International Conference on Multimedia Computing and Systems (ICMCS), Marrakech, Morocco, pp. 295-300, 2014, https://dolorg/ 10.1109/ICMCS.2014.6911251 5. Wang J., Sheng Z., Xu W., Zhang W., Cao Z. A FPGA-based architecture for real-time image matching. Proceedings of the SPIE. Vol. 8920, id. 892003.8 pp. 2013. https://doi.org/l 0.1117/12.2031050 6. Method and apparatus for filtering an image: patent US 7,305,145 B2 USA: G06K 9/36, H04N 5/225, G0IB II/4; Filed: 23.05. 2003; Date of Patent: 4. 12. 2007, 10 p. 7. Multiplierless coprocessor for difference of Gaussian (DoG): patent US 9,014,508 B2 USA: G06K 9/60, G06T5/50, G06T5/00, G06T L/20; Filed: 24.04." 2013; Date of Patent: 21. 04.2015, 15 p. 8. Regalia P. A., Mitra S. K., Vaidyanathan P. P. The digital all-pass filter: a versatile signal processing building block, in Proceedings of the IEEE, vol. 76, no. 1, pp. 19-37, Jan. 1988, https://doi.org/10.1109/5.3286. 9. Nikolova K., Stoyanov G., Kawamata M. Low-sensitivity design and implementation of allpass based fractional delay digital filters, 2009 F.uropean Conference on Circuit Theory and Design, Antalya, Turkey, pp. 603-606, 2009, https://doi.org/ 10.1109/ECCTD.2009.5275050, 10. Krukowski A., Kale I. DSP System Design: Complexity Reduced IIR Filter Implementation for Practical Applications. Springer. 2003. 234 p.