Афонін Д. Г.1, Миколаїв Д. П.2, Карпенко С. М.3

1                              Московський Державний Університет ім. М. В. Ломоносова Воробйови гори, МГУ, фізичний факультет, Москва – 119992, Росія Тел.: +7 (095) 9392094; e-mail: afonin@phys.msu.su

2                                                                            Інститут проблем передачі інформації РАН Б. Каретний пров., 19, Москва – 101447, Росія 3 ТОВ Когнітивні технології Пр. 60-річчя Жовтня, 9, Москва – 117312, Росія

Анотація – Розглянуто економічна схема обчислення перетворення Хафа для стиснення відеопотоків. Схема призначена для використання при сегментації та фільтрації зображень у рамках сімейства протоколів MPEG-4/MPEG-7.

I. Вступ

З розвитком високошвидкісних каналів зв’язку все більшу частину переданої інформації стали представляти відеопотоки. У зв’язку з цим з’явилася потреба в новому, більш ефективному поколінні алгоритмів стиснення відеопотоків. На цю роль зараз претендує сімейство стандартів MPEG-4/MPEG-7. Важливою заявленої функціональністю протоколів MPEG є механізм передачі різних об’єктів на зображенні з різним ступенем стиснення. Для реалізації цього механізму, очевидно, потрібно рішення задачі об’єктної сегментації відеопотоку. Як було показано в [1], задача об’єктної сегментації може бути ефективно вирішена з опорою на математичний апарат перетворення Хафа [2]. Цей же апарат використовується для іншої важливої ​​задачі обробки потоків зображень – фільтрації зображення зі збереженням структури [3], що дозволяє досягти високого рівня стиснення при тій же якості зображення, і, тим самим, більш ефективно використовувати канал зв’язку.

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

Перетворення Хафа традиційно вважається досить ресурсномістких. Показано, однак, що воно може бути точно і вельми ефективно обчислено за допомогою швидкого Фур’є-перетворення [3].

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

Нам, проте, вдалося показати, що існує згладжує перетворення в просторі Хафа, еквівалентну згладжування вихідного розподілу, що дозволяє істотно скоротити обчислення.

II. Основна частина

Розглянемо варіанти перетворення Хафа для пошуку прямих на площині і в тривимірному просторі.

Пряма задається рівнянням прямої в канонічній формі. Параметрами моделі є координати точки ь, через яку проходить ця пряма, і вектора 3, задає її напрямок. Зажадаємо а2 = 1 і (а-б) = о. Тоді квадрат відхилення елемента вибірки С; від моделі буде дорівнює

та

Співвідношення (10) доводиться аналогічно (6). Таким чином, ізотропне гауссових згладжування в просторі вихідного розподілу в нашому випадку еквівалентно згладжування в просторі параметрів, причому по меншому числу координат. Крім того, аналогічне властивість виконується і для масштабування. Це дозволяє вести підбір масштабу і рівня згладжування безпосередньо в просторі параметрів, без додаткових обчислювальних витрат на перетворення Хафа.

III. Висновок

Таким чином, розроблена економічна схема обчислення перетворення Хафа для стиснення відеопотоків.

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

Вказана можливість поєднання схеми з використанням швидкого перетворення Хафа.

IV. Список літератури

[1]  Nikolaev D. P., Nikolayev P. P. Linear color segmentation and its implementation. Computer Vision and Image Understanding. Special issue on colour for image indexing and retrieval. 2004. V. 94. pp. 115-139.

[2]  Hough P. V. Methods and means for recognizing complex patterns. U. S. Patent 069654.1962.

[3]  StarckJ.-L., CandesE. J., Donoho D. L. The curvelet transform for image denoising. IEEE Transactions on Image Processing. 2002. V. 11. pp. 670-684.

[4] Гельфанд І. М., Гіндікін С. Г., Гоаев М. І. Вибрані задачі інтегральної геометрії. М.: Добросвет, 2000. 208 с.

EFFICIENT SCHEME OF HOUGH TRANSFORM COMPUTING FOR VIDEOSEQUENCE COMPRESSION

Afonin D. G.1, Nikolaev D. P.2, Karpenko S. M.3

1                      Moscow State University Vorobjovy gory, MSU, Physical department Moscow – 119992, Russia phone: (095) 9392094 e-mail: afonin@physmsu.su

2

Institute for information transmission problems RAS

Bol’shoj Karetnyj lane, 19, Moscow – 101447, Russia

з

Cognitive Technology Ltd. pr. 60-letija Oktyabrya, 9, Moscow – 117312, Russia

Abstract – Efficient Hough transform calculation scheme intended for image compression is considered.

I.  Introduction

With arise of high-speed communication channels a need in new, more efficient video stream compression algorithms appeared. These algorithms involve both image filtration and segmetation. As shown in [1, 3], these tasks can be efficiently solved using Hough Transform [2].

Preliminary sample smoothing is needed for Hough Transform stability. Generally, smoothing level is not given in advance. So, parameter fitting scheme should be used. However, it leads to multiple calculations of Hough Transform.

We show that smoothing transform in the Hough space exists, which is equivalent to preliminary sample smoothing. Such scheme is much more efficient.

II.  Main part

Let us consider Hough Transform parameterizations in the

2-     D (3) and 3-D (8) spaces. Isotropic Gaussian smoothing of source distribution then equivalent to the smoothing in the Hough space (6, 10). Scaling has similar feature with regard to the Hough Transform (4, 9). It allows to fit scale and smoothing level in the Hough space directly, with no additional computational load.

III.  Conclusion

So, efficient Hough transform calculation scheme intended for image compression was developed.

Джерело: Матеріали Міжнародної Кримської конференції «СВЧ-техніка і телекомунікаційні технології»