Втілення простору масштабів

У галузях комп'ютерного бачення, ^[en] та обробки сигналів поняття масштабопросторового подання використовують для обробки даних вимірювань у декількох масштабах, а саме для посилення або пригнічування ознак зображення в різних діапазонах масштабу (див. статтю про простір масштабів). Особливий тип масштабопросторового подання забезпечує гауссів простір масштабів, де дані зображення в N вимірах зазнають згладжування гауссовою згорткою. Більша частина теорії гауссового простору масштабів має справу з безперервними зображеннями, тоді як при втіленні цієї теорії доведеться зіткнутися з тим, що більшість даних вимірювань є дискретними. Отже, виникає теоретична проблема щодо того, як здискретувати цю неперервну теорію, зберігаючи або добре наближуючи бажані теоретичні властивості, що ведуть до обрання гауссового ядра (див. статтю про масштабопросторові аксіоми). У цій статті описано основні підходи для цього, які було розроблено в літературі.

Простір масштабів
Масштабопросторові аксіоми
Втілення простору масштабів
Виявляння ознак
Виявляння контурів
Виявляння плям
Виявляння кутів
Виявляння хребтів
(Виявляння особливих точок)
(Обирання масштабу)
Афінне пристосовування форми
Масштабопросторове сегментування

Постановка проблеми

Гауссове масштабопросторове подання N -вимірного безперервного сигналу,

${\displaystyle f_{C}\left(x_{1},\cdots ,x_{N},t\right),}$

отримують згортанням f _C з N -вимірним гауссовим ядром:

${\displaystyle g_{N}\left(x_{1},\cdots ,x_{N},t\right).}$

Іншими словами:

${\displaystyle L\left(x_{1},\cdots ,x_{N},t\right)=\int _{u_{1}=-\infty }^{\infty }\cdots \int _{u_{N}=-\infty }^{\infty }f_{C}\left(x_{1}-u_{1},\cdots ,x_{N}-u_{N},t\right)\cdot g_{N}\left(u_{1},\cdots ,u_{N},t\right)\,du_{1}\cdots du_{N}.}$

Проте для втілення це визначення непрактичне, оскільки воно безперервне. Для застосування концепції простору масштабів до дискретного сигналу f_D можливо використовувати різні підходи. Ця стаття являє собою короткий виклад деяких з найчастіше вживаних методів.

Роздільність

Використання властивості роздільності гауссового ядра

${\displaystyle g_{N}\left(x_{1},\dots ,x_{N},t\right)=G\left(x_{1},t\right)\cdots G\left(x_{N},t\right)}$

дає можливість розкласти N-вимірну операцію згортки на набір роздільних кроків згладжування з одновимірним гауссовим ядром G вздовж кожного виміру

${\displaystyle L(x_{1},\cdots ,x_{N},t)=\int _{u_{1}=-\infty }^{\infty }\cdots \int _{u_{N}=-\infty }^{\infty }f_{C}(x_{1}-u_{1},\cdots ,x_{N}-u_{N},t)G(u_{1},t)\,du_{1}\cdots G(u_{N},t)\,du_{N},}$

де

${\displaystyle G(x,t)={\frac {1}{\sqrt {2\pi t}}}e^{-{\frac {x^{2}}{2t}}}}$

а стандартне відхилення гауссіана σ пов'язано з параметром масштабу t як t = σ².

В подальшому роздільність вважатиметься припущеною, навіть якщо ядро не є точно гауссовим, оскільки роздільність вимірів є найпрактичнішим способом втілення багатовимірного згладжування, особливо у більших масштабах. Тому решту статті зосереджено на одновимірному випадку.

Вибіркове гауссове ядро

При втілюванні кроку одновимірного згладжування на практиці, ймовірно, найпростіший підхід полягає в згортанні дискретного сигналу f_D з вибірковим гауссовим ядром (англ. sampled Gaussian kernel):

${\displaystyle L(x,t)=\sum _{n=-\infty }^{\infty }f(x-n)\,G(n,t)}$

де

${\displaystyle G(n,t)={\frac {1}{\sqrt {2\pi t}}}e^{-{\frac {n^{2}}{2t}}}}$

(де t = σ²), що, своєю чергою, обрізається на кінцях, щоб отримати фільтр зі скінченною імпульсною характеристикою

${\displaystyle L(x,t)=\sum _{n=-M}^{M}f(x-n)\,G(n,t)}$

для M, обраного достатньо великим (див. функцію похибки), щоби

${\displaystyle 2\int _{M}^{\infty }G(u,t)\,du=2\int _{\frac {M}{\sqrt {t}}}^{\infty }G(v,1)\,dv<\varepsilon .}$

Поширений вибір — встановлювати M у сталу C, помножену на стандартне відхилення гауссового ядра

${\displaystyle M=C\sigma +1=C{\sqrt {t}}+1}$

де C часто обирають десь між 3 та 6.

Використання вибіркового гауссового ядра може, проте, призводити до проблем із втіленням, зокрема при обчисленні похідних вищих порядків у тонших масштабах шляхом застосування вибіркових похідних гауссових ядер. Якщо основними критеріями проєктування є точність та робастність, слід розглядати альтернативні підходи до втілення.

Для малих значень ε (від 10⁻⁶ до 10⁻⁸) похибки, що вносить обтинання гауссіана, зазвичай незначні. Проте для більших значень ε існує багато кращих альтернатив прямокутній віконній функції. Наприклад, для заданої кількості точок вікно Геммінга, ^[en], або ^[en] завдасть менше шкоди спектральним та іншим властивостям гауссіана, ніж просте обтинання. Незважаючи на це, оскільки гауссове ядро швидко зменшується у хвостах, головна рекомендація все ще полягає у використанні достатньо малого значення ε, щоб ефекти обтинання залишалися неважливими.

Дискретне гауссове ядро

Ідеальне дискретне гауссове ядро (суцільне) у порівнянні з вибірковим звичайним гауссіаном (пунктир) для масштабів t = [0,5, 1, 2, 4]

Досконалішим підходом є згортання первинного сигналу з дискретним гауссовим ядром T(n, t)

${\displaystyle L(x,t)=\sum _{n=-\infty }^{\infty }f(x-n)\,T(n,t)}$

де

${\displaystyle T(n,t)=e^{-t}I_{n}(t)}$

а ${\displaystyle I_{n}(t)}$ позначує (інші мови) цілого порядку, n. Це дискретний аналог безперервного гауссіана в тому, що він є розв'язком дискретного рівняння дифузії (дискретний простір, безперервний час), так само як безперервний гауссіан є розв'язком безперервного рівняння дифузії.

Цей фільтр можливо обітнути в просторовій області, як і вибірковий гауссіан,

${\displaystyle L(x,t)=\sum _{n=-M}^{M}f(x-n)\,T(n,t)}$

або втілити в області Фур'є, використовуючи вираз замкненого вигляду для його ^[en]:

${\displaystyle {\widehat {T}}(\theta ,t)=\sum _{n=-\infty }^{\infty }T(n,t)\,e^{-i\theta n}=e^{t(\cos \theta -1)}.}$

За цього частотнообласного підходу масштабопросторові властивості передаються до дискретної області точно, або з чудовим наближенням з використанням періодичного розширення та відповідно довгого дискретного перетворення Фур'є для наближення ^[en] згладжуваного сигналу. Понад те, наближення похідних вищого порядку можливо обчислювати прямим чином (зі збереженням масштабопросторових властивостей), застосуючи до дискретного масштабопросторового подання оператори центральної різниці з невеликою кількістю опорних точок.

Як і у випадку вибіркового гауссіана, звичайне обтинання нескінченної імпульсної характеристики в більшості випадків буде достатнім наближенням для малих значень ε, тоді як для більших значень ε краще використовувати або розкладання дискретного гауссіана на каскад узагальнених біномних фільтрів або, як варіант, будувати скінченне наближене ядро шляхом множення на віконну функцію. Якщо ε було обрано занадто великим, щоби почав проявлятися вплив похибки обтинання (наприклад, як помилкові екстремуми, або помилкові відгуки на оператори похідних вищого порядку), тоді можливі варіанти зменшити значення ε так, щоби використовувалося більше скінченне ядро з обтинанням з дуже малою опорою, або використовувати конічне вікно.

Рекурсивні фільтри

Масштабопросторові ядра. Ідеальний дискретний гауссіан на основі функцій Бесселя (червоний) і поступально/зворотні рекурсивні згладжувальні фільтри з двома парами полюсів (сині) з полюсами, як описано в тексті. Вгорі показано окремі ядра, а знизу — їхня сукупна згортка одне з одним; t = [0,5, 1, 2, 4].

Оскільки обчислювальна ефективність часто важлива, для масштабопросторового згладжування часто використовують рекурсивні фільтри низького порядку. Наприклад, Янг і ван Вліет використовують рекурсивний фільтр третього порядку з одним дійсним полюсом та парою комплексних полюсів, застосовуваний поступально й зворотно, щоби робити симетричне наближення гауссіана шостого порядку з низькою обчислювальною складністю для будь-якого масштабу згладжування.

Послабивши деякі аксіоми, Ліндеберг виснував, що добрими згладжувальними фільтрами будуть «нормовані частотні послідовності Поя», сімейство дискретних ядер, яке містить усі фільтри з дійсними полюсами при 0 < Z < 1 та/або Z > 1, а також з дійсними нулями при Z < 0. Для симетрії, яка призводить до приблизної напрямової однорідності, ці фільтри мусить бути додатково обмежено парами полюсів і нулів, що веде до нульфазових фільтрів.

Щоби забезпечити відповідність кривини передавальної функції при нульовій частоті дискретного гауссіана, що забезпечує наближену напівгрупову властивість адитивного t, можливо застосовувати поступально й зворотно два полюси в

${\displaystyle Z=1+{\frac {2}{t}}-{\sqrt {\left(1+{\frac {2}{t}}\right)^{2}-1}}}$

для симетрії та стабільності. Цей фільтр є найпростішим втіленням ядра нормованої частотної послідовності Поя, яке працює для будь-якого масштабу згладжування, але він не є таким чудовим наближення гауссіана як фільтр Янга та ван Вліета, що не є нормованою частотною послідовністю Поя через свої складні полюси.

Передавальна функція H₁ рекурсивного фільтра з симетричною парою полюсів тісно пов'язана з ^[en] дискретного гауссового ядра через наближення першого порядку експоненти

${\displaystyle {\widehat {T}}(\theta ,t)={\frac {1}{e^{t(1-\cos \theta )}}}\approx {\frac {1}{1+t(1-\cos \theta )}}=H_{1}(\theta ,t),}$

де параметр t тут пов'язаний зі стабільним положенням полюса Z = p через

${\displaystyle t={\frac {2p}{(1-p)^{2}}}.}$

Крім того, такі фільтри з N парами полюсів, як-от двополюсні пари, показані в цьому розділі, є ще кращим наближенням експоненти

${\displaystyle {\frac {1}{\left(1+{\frac {t}{N}}(1-\cos \theta )\right)^{N}}}=H_{N}(\theta ,t),}$

де стабільні положення полюсів підлаштовуються розв'язанням

${\displaystyle {\frac {t}{N}}={\frac {2p}{(1-p)^{2}}}.}$

Імпульсні характеристики цих фільтрів не дуже близькі до гауссової, якщо не використовувати понад дві пари полюсів. Проте навіть з однією або двома парами полюсів на масштаб, сигнал, послідовно згладжений на збільшуваних масштабах, буде дуже близьким до гауссово згладженого сигналу. Напівгрупова властивість наближується погано, якщо використовувати занадто мало пар полюсів.

Масштабопросторові аксіоми, яким все ще задовольняють ці фільтри:

• лінійність
• інваріантність щодо зміщення (цілочислові зміщення)
• нестворення локальних екстремумів (перетинів нуля) в одному вимірі
• непосилення локальних екстремумів у будь-якій кількості вимірів
• додатність
• нормування

Наведеним нижче вони задовольняють лише наближено, наближення краще для більшої кількості пар полюсів:

• існування нескінченно малого породжувача A (нескінченно малий породжувач дискретного гауссіана або фільтр, що його наближує, наближено відображує відгук рекурсивного фільтра на один із нескінченно більших t)
• напівгрупова структура з пов'язаною властивістю каскадного згладжування (цю властивість наближують, вважаючи ядра еквівалентними, коли вони мають однакове значення t, навіть якщо вони не зовсім рівні)
• обертова симетрія
• масштабоінваріантність

Цей метод рекурсивного фільтра та його варіації для обчислення як гауссового згладжування, так і гауссових похідних було описано кількома авторами. Тан та ін. проаналізували та порівняли деякі з цих підходів і вказали, що фільтри Янга та Ван Вліета — це каскад (множення) поступальних і зворотних фільтрів, тоді як фільтри Деріша та Джіна та ін. фільтри — це суми поступальних і зворотних фільтрів.

На тонких масштабах підхід рекурсивного фільтрування, як й інші роздільні підходи, не гарантовано дають найкраще можливе наближення до обертової симетрії, тому як альтернативу для двовимірних зображень можна розглядати нероздільні втілення.

При одночасному обчисленні кількох похідних в N-струмені дискретне масштабопросторове згладжування дискретним аналогом гауссового ядра, або наближенням рекурсивним фільтром, за яким слідують різницеві оператори з невеликою опорою, може бути як швидшим, так і точнішим, ніж обчислення рекурсивних наближень кожного оператора похідної.

Згладжувачі зі скінченною імпульсною характеристикою (СІХ)

Для малих масштабів фільтр СІХ низького порядку може бути кращим згладжувальним фільтром, ніж рекурсивний. Симетричне 3-ядро [t/2, 1-t, t/2], для t ≤ 0,5 згладжує до масштабу t з використанням пари дійсних нулів у Z < 0 і наближається до дискретного гауссіана за гранично малого t. Фактично, за нескінченно малого t як нескінченно малий породжувач для дискретних гауссових ядер, описаних вище, можливо використовувати або цей двонульовий фільтр, або двополюсний фільтр з полюсами в Z = t/2 та Z = 2/t.

Нулі фільтра СІХ можливо поєднувати з полюсами рекурсивного фільтра для створення загального високоякісного згладжувального фільтра. Наприклад, якщо процес згладжування полягає в тому, щоб завжди застосовувати біквадратичний (двополюсний, двонульовий) фільтр поступально, а потім зворотно до кожного рядка даних (і до кожного стовпця у двовимірному випадку), як полюси так і нулі можуть виконувати частину згладжування. Нулі обмежуються на t = 0,5 на пару (нулі при Z = –1), тому для великих масштабів більшу частину роботи виконують полюси. У тонших масштабах це поєднання дає чудове наближення дискретного гауссіана, якщо як полюси, так і нулі виконують приблизно половину згладжування. Значення t для кожної частини згладжування (полюсів, нулів, поступальних і зворотних багаторазових застосувань тощо) адитивні, відповідно до наближено напівгрупової властивості.

Положення на площині Z чотирьох полюсів (X) і чотирьох нулів (кола) для згладжувального фільтра, який використовує поступально/зворотний біквадрат для згладжування до масштабу t = 2, із половиною згладжування від полюсів і половиною від нулів. Усі нулі в Z = –1; а полюси в Z = 0,172 та Z = 5,83. Полюси за межами одиничного кола втілюють зворотним фільтруванням зі стабільними полюсами.

Передавальна функція фільтра СІХ тісно пов'язана з ДЧПФ дискретного гауссіана, так само як і для рекурсивного фільтра. Для однієї пари нулів передавальною функцією є

${\displaystyle {\widehat {T}}(\theta ,t)=e^{-t(1-\cos \theta )}\approx {1-t(1-\cos \theta )}=F_{1}(\theta ,t),}$

де параметр t тут пов'язано з нульовими положеннями Z = z через

${\displaystyle t=-{\frac {2z}{(1-z)^{2}}},}$

і ми вимагаємо t ≤ 0,5, щоби передавальна функція була невід'ємною.

Крім того, такі фільтри з N парами нулів є ще кращим наближенням експоненти й поширюються на вищі значення t :

${\displaystyle \left(1-{\frac {t}{N}}(1-\cos \theta )\right)^{N}=F_{N}(\theta ,t),}$

де стабільні нульові положення встановлюють шляхом розв'язання

${\displaystyle {\frac {t}{N}}=-{\frac {2z}{(1-z)^{2}}}.}$

Ці СІХ та полюсно-нульові фільтри є чинними масштабопросторовими ядрами, які задовольняють ті ж аксіоми, що й виключно полюсні рекурсивні фільтри.

Реальночасове втілення в пірамідах та дискретному наближенні масштабонормованих похідних

Стосовно теми автоматичного обирання масштабу на основі нормованих похідних, то для отримання реальночасової продуктивності часто використовують пірамідні наближення. Доречність наближування масштабопросторових операцій в пірамідах випливає з того факту, що повторне каскадне згладжування з узагальненими біномними ядрами призводить до еквівалентних ядер згладжування, які за помірних умов наближаються до гауссового. Крім того, можливо продемонструвати, що біномні ядра (або, загальніше, клас узагальнених біномних ядер) становлять унікальний клас ядер зі скінченною опорою, які гарантують нестворення локальних екстремумів або перетину нуля зі збільшенням масштабу (докладніше див. статтю про багатомасштабні підходи). Проте може знадобитися особлива обережність задля уникнення артефактів дискретування.

Інші багатомасштабні підходи

Для одновимірних ядер існує добре розроблена теорія багатомасштабних підходів, що стосуються фільтрів, які зі збільшенням масштабів не створюють нових локальних екстремумів чи нових перетинів нуля. Для безперервних сигналів до цього класу належать фільтри з дійсними полюсами в s-площині, тоді як для дискретних сигналів ці критерії задовольняють вищеописані рекурсивні фільтри та фільтри СІХ. У поєднанні з суворою вимогою безперервної напівгрупової структури, безперервний гауссіан та дискретний гауссіан становить унікальний вибір для безперервних і дискретних сигналів.

Існує багато інших методик багатомасштабної обробки сигналів, обробки зображень і стискання даних, що використовують вейвлети та безліч інших ядер, які не використовують чи не висувають тих же вимог, що й описи простору масштабів; тобто вони не залежать від непороджування грубішим масштабом нового екстремуму, якого не було в тоншому масштабі (в єдиному вимірі), або непосилення локальних екстремумів між сусідніми рівнями масштабу (у будь-якій кількості вимірів).

Див. також

• Простір масштабів
• Піраміда (обробка зображень)
• Багатомасштабні підходи
• Гауссів фільтр

Примітки

1. Lindeberg, T., "Scale-space for discrete signals," PAMI(12), No. 3, March 1990, pp. 234-254. (англ.)
2. Lindeberg, T., Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994, (англ.)
3. R.A. Haddad and A.N. Akansu, "A Class of Fast Gaussian Binomial Filters for Speech and Image Processing," IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 39, pp 723-727, March 1991. (англ.)
4. Campbell, J, 2007, The SMM model as a boundary value problem using the discrete diffusion equation, Theor Popul Biol. 2007 Dec;72(4):539-46. (англ.)
5. Lindeberg, T. Discrete derivative approximations with scale-space properties: A basis for low-level feature extraction, J. of Mathematical Imaging and Vision, 3(4), pp. 349--376, 1993. (англ.)
6. Ian T. Young & Lucas J. van Vliet (1995). Recursive implementation of the Gaussian filter. Signal Processing. 44 (2): 139—151. CiteSeerX 10.1.1.12.2826. doi:10.1016/0165-1684(95)00020-E. (англ.)
7. Deriche, R: Recursively implementing the Gaussian and its derivatives, INRIA Research Report 1893, 1993. (англ.)
8. Richard F. Lyon. "Speech recognition in scale space," Proc. of 1987 ICASSP. San Diego, March, pp. 29.3.14, 1987. (англ.)
9. Jin, JS, Gao Y. "Recursive implementation of LoG Filtering". Real-Time Imaging 1997;3:59–65. (англ.)
10. . [ 2006-05-09 у Wayback Machine.] Sovira Tan; Jason L. Dale & Alan Johnston (2003). Performance of three recursive algorithms for fast space-variant Gaussian filtering. Real-Time Imaging. Т. 9, № 3. с. 215—228. doi:10.1016/S1077-2014(03)00040-8. (англ.)
11. Lindeberg, Tony & Bretzner, Lars (2003). Real-time scale selection in hybrid multi-scale representations. Lecture Notes in Computer Science. Т. 2695. с. 148—163. doi:10.1007/3-540-44935-3_11. ISBN . {{}}: Проігноровано |journal= () (англ.)
12. Crowley, J, Riff O: Fast computation of scale normalised Gaussian receptive fields, Proc. Scale-Space'03, Isle of Skye, Scotland, Springer Lecture Notes in Computer Science, volume 2695, 2003. (англ.)
13. Lowe, D. G., “Distinctive image features from scale-invariant keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004. (англ.)