Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA

Розглянуто пошук фрагментів зображень довільної форми в кадрі за шаблоном методом повного перебору із використанням паралельної обчислювальної архітектури CUDA. Запропоновано і проаналізовано різні способи кешування області пошуку в пам’яті мультипроцесора. Експериментально оцінено прискорення порі...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
Hauptverfasser:	Ладиженський, Ю.В., Середа, А.О.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2010
Schriftenreihe:	Штучний інтелект
Schlagworte:	Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/58400
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA / Ю.В. Ладиженський, А.О. Середа // Штучний інтелект. — 2010. — № 4. — С. 236-244. — Бібліогр.: 7 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-58400
record_format	dspace
spelling	irk-123456789-584002014-03-24T03:01:29Z Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA Ладиженський, Ю.В. Середа, А.О. Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений Розглянуто пошук фрагментів зображень довільної форми в кадрі за шаблоном методом повного перебору із використанням паралельної обчислювальної архітектури CUDA. Запропоновано і проаналізовано різні способи кешування області пошуку в пам’яті мультипроцесора. Експериментально оцінено прискорення порівняно з центральним процесором. Запропоновані алгоритми можуть використовуватись для прискорення відстежування об’єктів у відео. Рассмотрен поиск фрагментов изображений произвольной формы по шаблону методом полного перебора с использованием параллельной вычислительной архитектуры CUDA. Предложены и проанализированы различные способы кэширования области поиска в памяти мультипроцессора. Экспериментально оценено ускорение по сравнению с центральным процессором. Предложенные алгоритмы могут использоваться для ускорения отслеживания объектов в видео. A search of arbitrary shape image fragments with full-search template matching on CUDA is examined. Different approaches to search area caching in a multiprocessor’s memory are proposed and analyzed. Acceleration on GPU in comparison to CPU is evaluated. The proposed algorithms can be used to accelerate object tracking in video. 2010 Article Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA / Ю.В. Ладиженський, А.О. Середа // Штучний інтелект. — 2010. — № 4. — С. 236-244. — Бібліогр.: 7 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/58400 004.932.2:004.383.5 uk Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений
spellingShingle	Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений Ладиженський, Ю.В. Середа, А.О. Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA Штучний інтелект
description	Розглянуто пошук фрагментів зображень довільної форми в кадрі за шаблоном методом повного перебору із використанням паралельної обчислювальної архітектури CUDA. Запропоновано і проаналізовано різні способи кешування області пошуку в пам’яті мультипроцесора. Експериментально оцінено прискорення порівняно з центральним процесором. Запропоновані алгоритми можуть використовуватись для прискорення відстежування об’єктів у відео.
format	Article
author	Ладиженський, Ю.В. Середа, А.О.
author_facet	Ладиженський, Ю.В. Середа, А.О.
author_sort	Ладиженський, Ю.В.
title	Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA
title_short	Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA
title_full	Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA
title_fullStr	Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA
title_full_unstemmed	Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA
title_sort	пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі cuda
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2010
topic_facet	Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений
url	http://dspace.nbuv.gov.ua/handle/123456789/58400
citation_txt	Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA / Ю.В. Ладиженський, А.О. Середа // Штучний інтелект. — 2010. — № 4. — С. 236-244. — Бібліогр.: 7 назв. — укр.
series	Штучний інтелект
work_keys_str_mv	AT ladižensʹkijûv pošukfragmentívzobraženʹzašablonomdlâvídstežuvannâobêktívuvídeonaparalelʹníjarhítekturícuda AT seredaao pošukfragmentívzobraženʹzašablonomdlâvídstežuvannâobêktívuvídeonaparalelʹníjarhítekturícuda
first_indexed	2025-07-05T09:35:25Z
last_indexed	2025-07-05T09:35:25Z
_version_	1836799099717812224
fulltext	«Искусственный интеллект» 4’2010 236 4Л УДК 004.932.2:004.383.5 Ю.В. Ладиженський, А.О. Середа Донецький національний технічний університет, Україна ly@cs.dgtu.donetsk.ua, aas11@bk.ru Пошук фрагментів зображень за шаблоном для відстежування об’єктів у відео на паралельній архітектурі CUDA Розглянуто пошук фрагментів зображень довільної форми в кадрі за шаблоном методом повного перебору із використанням паралельної обчислювальної архітектури CUDA. Запропоновано і проаналізовано різні способи кешування області пошуку в пам’яті мультипроцесора. Експериментально оцінено прискорення порівняно з центральним процесором. Запропоновані алгоритми можуть використовуватись для прискорення відстежування об’єктів у відео. Вступ Необхідність відстежування об’єктів у відеопотоці виникає в системах безпеки, автоматизації аналізу спортивних змагань, контролю технологічних процесів, при орга- нізації людино-машинного інтерфейсу. Під відстежуванням розуміється отримання множини видимих об’єктів і їх координат у кожному кадрі. Пошук зображень за шаблоном є одним із методів відстежування об’єктів у відео. У [1] шаблон цілого об’єкта представлений зображенням об’єкта і матрицею, що задає ймовірність приналежності до об’єкта кожного пікселя цього зображення. У [2] описано метод відстежування об’єктів у відеопотоці на основі відстежування перемі- щення фрагментів об’єктів, які представлені шаблонами. Близька задача пошуку прямокутних блоків зображення у кадрі виникає при кодуванні відео [3]. Одним із методів пошуку фрагмента зображення у кадрі є метод Lucas-Kanade tracker, який базується на обчислені градієнтна зображення і переміщенні у напрямку зменшення функції різниці між кадром та шаблоном [4]. Іншим підходом є безпосе- реднє порівняння шаблона з областями кадру [3], [5], яке звичайно використовується при кодуванні відео. Пошук фрагмента зображення в кадрі може займати багато часу і потребує прискорення. Пошук складається з однотипних операцій над елементами матриць і може бути ефективно реалізований на паралельній обчислювальній архітектурі. Можна використовувати як спеціалізовані обчислювальні структури для пошуку фрагментів зображень в кадрі [5], так і паралельну архітектуру загального призначення. На даний час поширеними і доступними пристроями, придатними для паралельної обробки зображень і відео, є відеокарти NVIDIA з підтримкою технології CUDA [6]. Хоча існують послідовні алгоритми пошуку шаблонів [3], [4] та паралельні реалі- зації алгоритмів пошуку блоків при кодуванні відео [3], [5], не існує паралельних алгоритмів пошуку шаблонів зображень довільної форми, які можуть бути використані у методі відстежування об’єктів [2]. Метою даної роботи є розробка нових алгоритмів пошуку шаблонів зображень довільної форми у кадрі для архітектури CUDA. У даній статті розглядається пошук шаблону методом повного перебору. Пошук фрагментів зображень за шаблоном для відстежування об’єктів... «Штучний інтелект» 4’2010 237 4Л Постановка задачі Нехай фрагмент зображення, який шукають, вписано у прямокутник завширшки W та заввишки H. Нехай F – матриця розміром WH  , що містить пікселі шаблону. Кожен піксель шаблону )1,0,1,0(,  WxHyf xy характеризується наступними властивостями: r xyf , , g xyf , , b xyf , – відповідно красна, зелена та синя компоненти кольору;  1,0, m xyf – оцінка приналежності пікселя з координатами  yx, до фрагмента. Значен- ня m xyf , може бути чисельно не рівним ймовірності, але зі збільшенням ймовірності монотонно зростає. Назвемо областю пошуку прямокутну область кадру, що містить пікселі шаблону при всіх його можливих положеннях. Нехай її висота дорівнює H0, ширина – W0, а С – матриця розміром 00 WH  , що містить її пікселі. Кожен піксель області пошуку xyc , складається з r xyc , , g xyc , , b xyc , – відповідно красної, зеленої та синьої компонент кольору. Нехай осі системи координат кадру і шаблону спрямовані вправо і вниз, а піксель із координатами (0,0) розташовано в лівому верхньому куті. Міру різниці між пікселем шаблону xyf , і пікселем області кадру ',' xyc визначимо як  b xy b dydx g xy g dydx r xy r yx m yxxyyx cfcfcffcf ',',',',',',,',', ,  . (1) Накладемо шаблон на кадр без повороту так, що піксель шаблону з коорди- натами  0,0 співпаде з пікселем кадру з координатами  yx, . Міру різниці між шаблоном і областю кадру під ним визначимо як   1 1 , , 0 0 , , W H dx dy x dx y dy dx dy D x y f c        . (2) Нехай   ii yxS , – множина всіх можливих координат лівого верхнього піксе- ля шаблону в системі координат області пошуку, причому si Wx 0 , si Hy 0 , 10  WWWs , 10  HHH s . Найкращу позицію шаблону визначимо як  bestbestbest yxDD , і      yxDyx Syxbestbest ,minarg, ,   . У методі відстежування [2] для визначення ймовірності успішного відстежування фраг- мента зображення об’єкта необхідно також визначати альтернативну найкращу по- зицію фрагмента, тобто кращу з позицій, що залишилися в області пошуку, з якої вилучено околицю кращої позиції:      yxDD dyyxxSyxalt bestbest ,min ,min,,   , де d – константа, що визначає розмір околиці, яка вилучається. Для визначення  bestbest yx , і bestD можна використовувати як повний перебір всіх можливих положень шаблону, так і швидкі алгоритми пошуку, засновані на монотонному зменшенні міри різниці між шаблоном і кадром при наближенні до оптимального рішення, такі, як Three-Step Search [3]. Для визначення Dalt доцільно використовувати алгоритм повного перебору. Пошук шаблонів повним перебором є найбільш ресурсоємним етапом відстежування об’єктів у методі [2] і потребує прискорення. Далі розглядаються його реалізації на архітектурі CUDA. Ладиженський Ю.В., Середа А.О. «Искусственный интеллект» 4’2010 238 4Л Відображення алгоритму пошуку шаблону зображення на архітектуру CUDA Спрощена архітектура CUDA [6] наведена на рис. 1. Розглядаються пристрої з compute compatibility 1.1, як найпоширеніші на момент написання. Рисунок 1 – Спрощена архітектура CUDA На одному мультипроцесорі може одночасно виконуватись один або більше блоків потоків. Загальна кількість потоків на мультипроцесорі звичайно перевищує кількість скалярних процесорів, і групи потоків виконуються на них по черзі. Планувальник потоків оперує групами (warp) із 32 потоків одного блоку із послідовними номерами. Блоки, для виконання яких не вистачає вільних ресурсів, чекають у черзі, поки інші блоки не завершать роботу. Для мінімізації обміну даними між пам’яттю пристрою та пам’яттю кожного мультипроцесора дані, що багато разів використовуються, доцільно читати один раз і поміщати в текстурний кеш або спільну пам’ять. Для завантаження кожного пікселя F і C з пам’яті пристрою мінімальне число раз, а також для усунення необхідності синхро- нізації і обміну даними між різними мультипроцесорами доцільно проводити пошук одного шаблону на одному мультипроцесорі, тобто використовувати для цього один блок потоків. Залежно від кількості потоків та спільної пам’яті в одному блоці мульти- процесор може одночасно шукати один чи більшу кількість шаблонів. На сучасних пристроях цілочисельні арифметичні операції виконуються приблиз- но в чотири рази повільніше, ніж операції з плаваючою точкою [7]. Доцільно зберігати в пам’яті колір пікселів як цілі однобайтні числа, а перед обчисленнями перетво- рювати їх в дійсні числа. При зверненні до пам’яті пристрою без використовування текстурного кешу бажано проводити з’єднані (coalesced) запити до пам’яті пристрою. Для цього 16 потоків, що виконуються одночасно, повинні звертатися до 16 чотирибайтних слів, розташо- ваних в пам’яті послідовно з адреси, кратної 64 (деякі потоки можуть не брати участь). Необхідність обчислювати Dalt спричиняє необхідність зберігати знайдені значення  yxD , для   Syx , . Їх об’єм може бути завеликий для зберігання в пам’яті мультипроцесора, тому вони зберігаються в пам’яті пристрою. Щоб набувати готові Мультипроцесор N Мультипроцесор 1 Пам’ять пристрою (device memory) Спільна пам’ять (shared memory) Процесор 1 Регістри Процесор 2 Регістри Процесор M Регістри … Текстурний кеш Кеш констант Пристрій інструкцій … Пошук фрагментів зображень за шаблоном для відстежування об’єктів... «Штучний інтелект» 4’2010 239 4Л значення (2) в регістрах, кожне значення D повинне обчислюватися одним потоком. Зручно, щоб група з 16 потоків обчислювала 16 значень D, розташованих в пам’яті послідовно. Якщо потоків менше, ніж HsWs, то деякі потоки можуть обчислювати і зберігати більше одного значення D. При запропонованій організації обчислень прискорення пошуку множини шаблонів досягається як за рахунок одночасного пошуку різних шаблонів на різних мультипроцесорах, так і за рахунок одночасного обчислення значень (2) різними потоками для різних позицій шаблону. Загальний алгоритм пошуку шаблону Розглянемо частину алгоритму пошуку шаблону, яка не залежить від способу кешування області пошуку. Нехай є M потоків і i-й потік ( 1,0  Mi ) обробляє множину позицій шаблону SS i  . Він обчислює і зберігає в пам’яті пристрою  yxD , для всіх   iSyx , . В про- цесі обчислення різних значень D кожен потік обчислює і зберігає у своїх регістрах значення      yxDyx iSyx i best i best ,minarg, ,   і  i best i best i best yxDD , . Після завершення обчислення  yxD , для   Syx , , а також i bestx , i besty і i bestD , для 1,0  Mi , визначається такий номер потоку ibest, що  [0, 1] bestii i M best bestD D     ( ) ( )bestii best best bestD D i i    . Потік ibest зберігає в змінних в спільній пам’яті значення besti bestbest xx  , besti bestbest yy  , besti bestbest DD  . Після обчислення Dbest кожен потік обчислює    yxDD i altSyx i alt ,min ,   , де     dyyxxyxSS bestbest ii alt  ,min:,\ . При цьому використовуються раніше збережені в пам’яті пристрою значення D. altD вибирається з  i altD так само, як на попередньому кроці bestD з  i bestD . bestD і altD діляться на норму      1 0 1 0 , W x H y m dydxf . Нижче розглянуто різні способи обчислення D залежно від способу кешування області пошуку. В описаних нижче алгоритмах пікселі шаблону можуть бути розташовані як у текстурному кеші, так і в спільній пам’яті. Кешування області пошуку у текстурному кеші Пропонується схема розподілу задач по потоках: i-й потік обчислює множину позицій   ss i WjMiyWjMixS div)(,mod)(  для   MiMWHj ss div1,0  , де div позначає цілочисельне ділення, а mod – залишок від ділення. Елементи масиву D розташовано в пам’яті послідовно по рядках без дір з адреси, кратної 64. На рис. 2 показані три послідовні етапи пошуку шаблону розміром 3×3 пікселя в області пошуку розміром 7×11 пікселів з використанням 16 потоків. Заштрихова- ними квадратиками показані пікселі, з якими на кожному кроці збігається лівий верхній кут шаблону, а сірим – вже оброблені пікселі. Псевдокод алгоритму обчислення i bestx , i besty , i bestD і масиву D показано на рис. 3. Алгоритм може працювати при будь-яких значеннях W0, H0, W та H і забезпечує повне завантаження всіх потоків при )(mod0 MWH ss  . Усі звернення до пам’яті пристрою є з’єднаними. Ладиженський Ю.В., Середа А.О. «Искусственный интеллект» 4’2010 240 4Л Рисунок 2 – Обробка області пошуку з використанням текстурного кешу i bestD := ∞; { підготовка до обчислень } k := i; поки k < HsWs { цикл по позиціях шаблону } x0 := k mod Ws; { визначення координат шаблону } y0 := k div Ws; s := 0; { обчислення  00 , yxD } для y від 0 до H-1 для x від 0 до W-1 s := s +  ],[],,[ 00 xxyycxyfDist  ; зберегти ],[ 00 xyD = s; { збереження результату } якщо i bestD > s { перевірка найкращого результату у потоці } i bestD := s; i bestx := x0; i besty := y0; k := k + M; { перехід до наступної позиції шаблону } Рисунок 3 – Алгоритм пошуку шаблону при використанні текстурного кешу Кешування області пошуку у спільній пам’яті Пропонується читати рядки області пошуку зверху вниз і зберігати використо- вувані на кожному кроці рядки в циклічному буфері. Нехай на кожному кроці (окрім першого) в буфер завантажується h рядків, а після кожного читання перевіряється Wsh позицій шаблону. Щоб на кожному кроці при обчисленні D (окрім, можливо, останнього кроку) були зайняті всі потоки, повинна виконуватись умова )(mod0 MhWs  . Визначимо мінімальну достатню для обчислень кількість блоків зав- вишки h у буфері як   hHhk /1 . Кожен j-й рядок області пошуку зберігати- меться в рядку буфера із номером (j mod kh). Наприклад, при W = H = 3, W0 = 10, H0 = 7 можна вибрати значення h = 2, M = 16 і k = 2 (такі малі значення звичайно не виникають в задачі відстежування об’єктів, не є оптимальними і наведені для пояснення алгоритму). На рис. 4 а) показаний циклічний буфер, на рис. 4 б) показані три послідовні етапи обробки області пошуку. Заштрихованими квадратиками показані пікселі, з якими поєднується лівий верхній кут шаблону. Рисунок 4 – Розбиття області пошуку по рядках не прочитано оброблено оброблено у буфері у буфері у буфері h W0 Ws h не прочитано б) а) оброблено не оброблено оброблено j = 0 j = 1 j = 2 не оброблено Пошук фрагментів зображень за шаблоном для відстежування об’єктів... «Штучний інтелект» 4’2010 241 4Л Для оптимальної роботи планувальника потоків CUDA повинна виконуватись умова  32mod0M [7], а значить,  32mod0hWs . Для досягнення повного заван- таження потоків на останньому кроці повинна виконуватися умова    hHH mod010  . Читання кожного елементу області пошуку відбувається рівно один раз. Описаний алгоритм можна узагальнити на випадок, коли спільної пам’яті мультипроцесора не вистачає для зберігання буфера заввишки kh і завширшки W0. Пропонується використовувати циклічний буфер заввишки kh і завширшки w, причому (w ≥ W). Величини k и h визначаються так само, як в попередньому алго- ритмі. На кожному кроці (окрім першого) в буфер завантажується h рядків, а після кожного читання перевіряється  hWw 1 позицій шаблону. Кількість потоків є діль- ником  hWw 1 . Кожен j-й рядок області пошуку зберігається в рядку буфера  modj kh . Область пошуку розбивається на стовпці завширшки  1Ww . Кожен стовпець, окрім останнього, обробляється так само, як в попередньому алгоритмі. Оскільки ширина буфера перевищує ширину стовпця, при завантаженні в буфер рядків j-го стовпця в буфер також потрапляють деякі елементи  1j -го. Останній стовпець може мати ширину менше ніж  1Ww , і він обробляється, тільки якщо його ширина не менше W. Наприклад, при W = H = 3, W0 = 12, H0 = 8 можна вибрати значення h = 3, w = 6, M = 8 і k = 2. На рис. 5 а) показаний циклічний буфер, на рис. 5 б) показані три з дев’яти послідовних етапів обробки області пошуку при обраних параметрах. Рисунок 5 – Розбиття області пошуку по рядках і стовпцях Для оптимальної роботи планувальника потоків CUDA повинна виконуватись умова  32mod0M , а значить,    32mod01  hWw . Для досягнення повного завантаження потоків при обробці нижнього ряду і правого стовпця блоків повинні виконуватися умови    hHH mod010  і     1mod010  WwWW . При w = W0 даний алгоритм виконує розбиття області тільки по рядках і поводиться аналогічно попередньому. При w ≠ W0 алгоритм проводить повторні читання з пам’яті пристрою деяких значень xyc , : в середньому на кожні  1Ww пік- селів алгоритм проводить w читань. Псевдокод алгоритму, що проводить розбиття по рядках і стовпцях, приведений на рис. 6. Не для всіх можливих значень W0, H0, W і H можливо вибрати значення h, k і M, що забезпечують оптимальне завантаження процесорів. У обох алгоритмах при будь- яких розмірах шаблону і області пошуку можливо зробити всі запити до пам’яті пристрою з’єднаними. у буфері h w w – W + 1 h б) а) у буфері оброблено оброблено оброблено у буфері Ладиженський Ю.В., Середа А.О. «Искусственный интеллект» 4’2010 242 4Л i bestD := ∞; { підготовка до обчислень } x1 := 0; { (x1, y1) – координати лівого верхнього кута частини області пошуку, що кешується } поки sWx 1 { цикл по стовпцях області пошуку } j := i; поки j < wh {завантаження верхньої частини стовпця} якщо ( 01 mod Wwjx  ) і ( 0div Hwj  ) b [(j div w) mod h, j mod w] := С [j div w, x1 + j mod w]; j := j + M; y1 := 0; поки 01 Hhy  { цикл по рядках області пошуку } j := i; поки j < wh { завантаження рядків стовпця } якщо ( 01 mod Wwjx  ) і ( 01 div Hwjy  ) b [(y1 + j div w) mod h, j mod w] := С [y1 + j div w, x1 + j mod w]; j := j + M; виконати синхронізацію потоків; { дочекатися кінця завантаження області пошуку} j := i; поки j <  1Ww h { цикл по позиціях шаблону } x0 := j mod  1Ww ; { (x0, y0) – координати позиції шаблону } y0 := j div  1Ww ; { всередині частини області пошуку у кеші } якщо ( sHyy  10 ) і ( sWxx  01 ) s := 0; { обчислення D(x0 + x1, y0 + y1)} для y від 0 до H-1 p := посилання на b[(y0 + y1 + y) mod h, x0 + x1]; для x від 0 до W-1 s := s +   xpxyfDist ],,[ ; зберегти ],[ 1010 xxyyD  = s; { збереження результату } якщо i bestD > s { перевірка найкращого результату у потоці } i bestD := s; i bestx := x0; i besty := y0; j := j + M; y1 := y1 + h; { перехід униз до наступної групи рядків } виконати синхронізацію потоків; { дочекатися закінчення обчислень перед початком завантаження наступної частини області пошуку } x1 := 11  Wwx ; { перехід управо до наступного стовпця } Рисунок 6 – Алгоритм пошуку шаблону при розбитті області по рядках і стовпцях Для алгоритму, що проводить розбиття по стовпцях і рядках, можлива модифі- кація: якщо ширина останнього стовпця не рівна (W – 1), то при його обробці можливо використовувати менше значення w і більше значення h, ніж для решти стовпців. Це може зменшити число кроків, необхідних для його обробки, внаслідок чого розши- риться множина значень W0, H0, W і H, при яких алгоритм може працювати ефективно. Практичні результати Описані алгоритми реалізовано і протестовано на відеокарті GeForce 9800 GT. Результати порівнювалися з однопотоковою реалізацією на процесорі Athlon X2 5400. Час пошуку 1000 фрагментів для запропонованих алгоритмів із використанням цілочисельної і дійсної арифметики приведено в табл. 1. Для CUDA наведено чистий час обчислень без урахування накладних витрат на передачу даних на відеокарту. Пошук фрагментів зображень за шаблоном для відстежування об’єктів... «Штучний інтелект» 4’2010 243 4Л Таблиця 1 – Середній час пошуку 1000 фрагментів на CPU та GPU Час на CUDA з використанням текстурного кешу, мс Час на CUDA з використанням спільної пам’яті, мс Розмір шаблону Розмір області пошуку На центральному процесорі, мс цілочисельні дійсні цілочисельні дійсні 8 39 328 13,3 9,4 11,8 10,6 8 71 1344 51,5 36,1 46,3 41,3 16 79 4860 196 130 167 149 16 143 19437 782 514 658 582 Як видно з табл. 1, використання відеокарти середнього рівня забезпечує при- скорення в порівнянні з одним ядром процесора приблизно в 36 разів. При цьому знижується завантаження ЦП і він може паралельно проводити інші обчислення. При використанні двох або чотирьох ядер процесора час обробки множини шаблонів скоротиться майже в два або чотири рази; очікується, що при відеокарті рівня GeForce GTS 295 час обчислень на CUDA також скоротиться приблизно у чотири рази. На практиці прискорення може бути меншим через накладні витрати на підготовку даних у пам’яті пристрою. При використанні цілочисельної арифметики алгоритм з явним кешуванням даних в спільній пам’яті, оптимізованим для даної задачі, виявився ефективнішим за алгоритм, що використовує апаратно реалізований текстурний кеш, навіть коли об’єм використовуваної спільної пам’яті був менший за об’єм текстурного кешу. При приведенні даних до дійсного типу перед обчисленням (1) текстурний кеш виявився ефективнішим за рахунок швидкого перетворення цілого числа в норма- лізоване дійсне, що є неможливим для даних в спільній пам’яті. Це співвідношення може змінитися в майбутніх пристроях на користь спільної пам’яті при прискоренні операцій цілочисельної арифметики або перетворення типів. Висновки У статті представлено апаратно-орієнтовані алгоритми пошуку шаблонів зобра- жень довільної форми для паралельної архітектури CUDA. Вони можуть бути вико- ристані для підвищення швидкості відстежування об’єктів у відеопотоці за методом [2]. Алгоритми реалізовані і досліджені експериментально. В порівнянні з одним ядром процесора Athlon X2 5400 на відеокарті GeForce 9800 GT досягнуте зменшення часу пошуку множини фрагментів зображень до 36 разів. Використання пристрою з архітектурою CUDA може стати хорошою альтернативою використанню багатопро- цесорних ЕОМ або кластеру при відстежуванні об’єктів у відеопотоці. Досліджено кешування області пошуку у спільній пам’яті мультипроцесора та текстурному кеші. На сучасних пристроях CUDA доцільно використовувати текстур- ний кеш, але якщо у майбутніх пристроях буде прискорено виконання цілочисельних арифметичних операцій [7], для певних розмірів фрагменту та області пошуку може стати доцільним кешування області пошуку у спільній пам’яті. При великому розмірі області пошуку більше прискорення за рахунок зниження точності можна отримати при реалізації швидких алгоритмів пошуку шаблонів [3]. При великому розмірі шаблону доцільно кешувати його у спільній пам’яті мульти- процесора по частинах. Ладиженський Ю.В., Середа А.О. «Искусственный интеллект» 4’2010 244 4Л Ще більше прискорення відстежування фрагментів при меншому енергоспо- живанні і апаратних витратах можливе при реалізації на ПЛІС спеціалізованого вектор- ного процесора для пошуку фрагментів зображень. При цьому можуть бути використані представлені в статті алгоритми кешування області пошуку. Література 1. Cucchiara R. Track-based and object-based occlusion for people tracking refinement in indoor surveillance [Електронний ресурс] / R. Cucchiara, C. Grana, G. Tardini // Proceedings of the ACM 2nd international workshop on Video surveillance & sensor networks 2004. – New York, NY, USA, October 15, 2004. – 10 p. – Режим доступу : http://doi.acm.org/10.1145/ 1026799.1026814. 2. Ладиженський Ю.В. Відстежування об’єктів у відеопотоці на основі відстежування переміщення фрагментів об’єктів / Ю.В. Ладиженський, А.О. Середа // Наукові праці Донецького національного технічного університету. Серія: «Обчислювальна техніка та автоматизація». Випуск 17 (148). – Донецьк : ДонНТУ, 2009. – 215 с. 3. Adaptive Motion Estimation Processor for Autonomous Video Devices / T. Dias, S. Momcilovic, N. Roma, L. Sousa [Електронний ресурс]// EURASIP Journal on Embedded Systems. – 2007. – Article ID 57234. – P. 10. – Режим доступу : http://www. hindawi.com/GetArticle.spx?doi=10.1155/2007/57234. 4. Baker S. Lucas-Kanade 20 Years On: A Unifying Framework. / S. Baker, I. Matthews // Int. Journal of Computer Vision. – 2004. –Vol. 56, № 3, March. – P. 221-255. – Режим доступу: http://www.ri.cmu.edu/ pub_files/ pub3/baker_simon_2004_1/baker_simon_2004_1.pdf. 5. Sheu-Chih Cheng. A comparison of Block-Matching Algorithms Mapped to Systolic-Array Implementa- tion / Sheu-Chih Cheng, Hsueh-Ming Hang // IEEE Transactions on Circuits and Systems for Video Technology. – 1997. – Vol. 7, № 5. – P. 741-747. 6. NVIDIA CUDA Programming Guide Version 2.3.1, 2009. [Електронний ресурс]. – 145 p. – Режим доступу : http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf. 7. NVIDIA CUDA C Programming Best Practices Guide CUDA Toolkit 2.3, 2009. [Електронний ресурс]. – 145 p. – Режим доступу : http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_ CUDA_BestPracticesGuide_ 2.3pdf. Ю.В. Ладыженский, А.А. Середа Поиск фрагментов изображений по шаблону для отслеживания объектов в видео на параллельной архитектуре CUDA Рассмотрен поиск фрагментов изображений произвольной формы по шаблону методом полного перебора с использованием параллельной вычислительной архитектуры CUDA. Предложены и проанализированы различные способы кэширования области поиска в памяти мультипроцессора. Экспериментально оценено ускорение по сравнению с центральным процессором. Предложенные алгоритмы могут использоваться для ускорения отслеживания объектов в видео. Y. Ladyzhenskyy, A. Sereda A Search of Image Fragments for Object Tracking in Video with Template Matching on the CUDA Parallel Architecture A search of arbitrary shape image fragments with full-search template matching on CUDA is examined. Different approaches to search area caching in a multiprocessor’s memory are proposed and analyzed. Acceleration on GPU in comparison to CPU is evaluated. The proposed algorithms can be used to accelerate object tracking in video. Стаття надійшла до редакції 02.07.2010.

Пошук фрагментів зображень за шаблоном для відстежування об'єктів у відео на паралельній архітектурі CUDA

Institution

Ähnliche Einträge