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

Анотація наукової статті з математики, автор наукової роботи - Козирєва Аліна Володимирівна


This paper analyzes the possibility of developing software product for positioning mobile device in the space relative to the other objects. Algorithms of camera calibration as well as the algorithms of finding image features and their further tracing were considered. The change of position in the space is determined by searching the unknown coefficients in the rotation matrix and shift vector on the basis of the obtained calibration data and determined features. Based on founded feature and calibration data rotation matrix and shift vector are calculated. On the basis of the results of different algorithms functioning the simplified technique for solving concrete problems was developed. The results of the work can be used for control mobile devices or in the games.


Область наук:
  • Математика
  • Рік видавництва: 2010
    Журнал: Известия Томського політехнічного університету. Інжиніринг ГЕОРЕСУРСИ
    Наукова стаття на тему 'Алгоритми позиціонування мобільного пристрою на основі даних від вбудованої фотокамери'

    Текст наукової роботи на тему «Алгоритми позиціонування мобільного пристрою на основі даних від вбудованої фотокамери»

    ?УДК 535.31

    АЛГОРИТМИ ПОЗИЦІОНУВАННЯ МОБІЛЬНОГО ПРИСТРОЮ НА ОСНОВІ ДАНИХ ВІД ВБУДОВАНОЇ ФОТОКАМЕРИ

    А.В. Козирєва

    Інститут систем інформатики ім. А.П. Єршова СО РАН, Новосибірськ E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

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

    Ключові слова:

    Калібрування камери, особливості зображення, кутові детектори, алгоритми стеження за особливостями.

    Key words:

    Camera calibration, feature detection, edge detection, feature point tracking.

    Вступ

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

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

    1. Процес калібрування камери

    Розглянемо рис. 1. Точка т = (х, у) в площині камери і точка М = (Х, У, 7) в просторі пов'язані наступним рівністю:

    7у = ЛМ, (1)

    де М = (Х, У, 7Т - тривимірний вектор, відповідний точці М, т = (х, у) Т - двовимірний вектор, що відповідає точці т, \ = (и V 1) Т - вектор однорідних [1] внутрішніх координат камери , а матри-

    ца

    A =

    f / w у 0 f / h

    0

    1

    - матриця, відома

    під назвою матриці внутрішніх параметрів камери, оскільки вона містить тільки параметри оптичної системи і фотоприймача камери.

    Нехай задана точка т = (х, у) на площині, яка є проекцією деякої точки М = (Х, У, 7) в просторі. Співвідношення між цими двома точками можна представити в наступному вигляді:

    sm = Л [R?] М, (2)

    де ^ - деякий скаляр, пара ^ 0 - так звані зовнішні параметри камери, Л - матриця, що представляє собою внутрішні параметри камери. Отримаємо нове співвідношення з (2), використавши матрицю гомографіі Н = Л [г {г2?]:, Ш = НМ. Матрицю гомографіі можна обчислити різними способами [2], будемо вважати, що вона вже є. Покладемо, що Н = [Н {Н2 й3], тоді з (2) отримаємо:

    [До 1 к2 к3] = ЯА [г1 г2 t],

    де Я - скаляр. Виходячи з того, що г і г2 ортогональні, отримуємо

    hT A-TA-1h2 = 0;

    hTlA-TA-lhl = hTA ~ TA ~ Покладемо

    (3)

    (4)

    Vj =

    hilhjl, hilhj 2

    -ht 2hj !, h 2hj 2!

    hi3hjl

    |hnhjз, ht3hj2

    • h h h h

    ri 2'7 3 '' h 3'j 3

    тоді (3) і (4) можна переписати в наступному вигляді:

    T

    b = 0.

    (5)

    _ (Vii V22)

    В (5) b - це 6D вектор, рівний [Bn, B12, B22, B13, B23, B33], де Bj - елементи матриці B = AAl.

    Тоді, використовуючи n зображень шаблону, шляхом нескладних перетворень [3] елементи матриці внутрішніх параметрів можна записати в такий спосіб:

    V = (Bi2Bi3 -ВпВ2з) / (ВцB22 -BiU

    Я = B33 - [Bi23 + Vo (Bi2Bi3 - BiiB23)] / Bii ,

    а = -у / А / вц,

    ? = Л] ЯВП / (ВцB22 - B \ 2), у = -Bi2a2? / Я, u0 = cv0 / а -Bi3a2 / Я,

    де Bj - елементи матриці B = ATAl.

    Калібрування стаціонарної камери можна провести також в такий спосіб [8]. Нехай дано перекривають один одного зображення J0 ... JN, де N>2. Зображення отримані за допомогою однієї камери і реєструють одну і ту ж сцену. Тоді алгоритм самокалібрування наступний:

    • встановити відповідність між точками зображень;

    • для кожного j = 1 ... N обчислити перетворення Pj між J0 і J;

    • знайти верхнетреугольную матрицю К, таку що K1PjK = Rj, де Щ - це матриця обертання для всех7>0 (К - калібрувальна матриця, Щ описує орієнтацію камери в момент j по відношенню до «нульового» моменту);

    • итеративно поліпшити отриману оціночну калибровочную матрицю.

    2. Обертання і зрушення

    Розглянемо загальний випадок, коли оптичні осі камер не паралельні, а напрямок зміщення оптичного центру однієї камери щодо оптичного центру інший довільно (рис. 2). Введемо для кожної камери свою стандартну систему координат. Нехай першій камері відповідає система координат 0'Х'У7 ', а другий -О'Т'Г'7 "(рис. 2). Нехай вектор М = (0 ТГ7) Т характеризує координати деякої точки М тривимірного простору в системі першої камери , а вектор М '' = (0 "Х" у "7 ') Т - в системі другої. Легко показати, що зв'язок між векторами М 'і М "задається співвідношенням

    М '= Щ М +, (6)

    де Щ = Щ "ЩТ - ортогональна матриця, що описує орієнтацію системи координат другої камери щодо першої, а? = - Щ" Щ ^ - вектор

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

    Розглянемо пару камер, внутрішні параметри яких відомі, але невідомі зовнішні параметри (матриця Щ і вектор /). Помноживши обидві частини виразу (6) зліва векторно на?, А потім скаляр-но - на М ", отримаємо М" Т (/ хЩМ) = 0. Це співвідношення формально висловлює той факт, що вектори М, М "і I лежать в одній площині, що проходить через три точки: оптичні центри камер 0 і 0 "і точку спостереження М. Висловлюючи М через V і з огляду на властивості змішаного добутку векторів, отримаємо:

    (У "Тл2-т х ял; -У) Tt = про.

    (7)

    Співвідношення (7) є основою для оцінки матриці Щ і вектора?. Припустимо, що відомі координати п пар пов'язаних точок і, відповідно, п пар векторів V? ' і V ",? = 1, 2 ... п.

    Розглянемо метод оцінювання Щ і?, Який використовує (7). Так як це співвідношення справедливо для будь-якої пари сполучених точок, маємо систему з n рівнянь щодо невідомих Щ і яку можна представити у вигляді:

    ВА = 0, де Вп =

    (У; тл-т х ял; у)

    -1 < \ т

    (^ Л * 'хялуп) т

    (8)

    Система (8) є однорідною лінійної по I. Це означає, що вектор трасляціі можна оцінити тільки з точністю до постійного множника. Вводячи умова нормування || / || 2 = 1, кількість можливих рішень можна обмежити двома, що відрізняються знаком. Система (8) містить п'ять невідомих, отже, і число пар відомих пов'язаних точок п повинно бути не менше п'яти.

    Оскільки на практиці в матрицю Бп входять не точні значення координат пов'язаних точок, а результати їх вимірювань, які можуть містити помилки, то реально система (8) має ненульову праву частину, т. Е. Б / = е, де е - вектор нев'язки, обумовлений наявністю помилок вимірювань.

    Згідно МНК як оцінки матриці обертання і вектора трансляції слід вибрати такі

    Щ і?, Які мінімізують значення функціоналу 72 (Щ, /) = ете = / ТБпТБп /. Як згадувалося раніше, за умови || / || 2 = 1 квадратична форма tTБnTБnt досягає мінімуму 11 = АШП по t (А ^ - мінімальне власне число матриці БпТБп), якщо t - власний вектор матриці, відповідний АШП. Тому процедуру оцінювання Щ і t можна розбити на два етапи. На першому - знаходиться матриця Щ, яка мінімізує АШП. На другому - оцінюється власний вектор матриці БпТБп, відповідний Ашш. Існує безліч алгоритмів і їх програмних реалізацій для обчислення власних векторів, тому другий етап не викликає труднощів.

    Значно більш складним завданням є завдання оцінювання матриці Щ. Один з можливих алгоритмів полягає в наступному. Відомо, що матриця Щ може бути представлена ​​у вигляді Щ = щх (юхЩ (ЮУ) Цю), де

    Я =

    Яу =

    Я =

    1 про про

    0 соб тх - Бт сях 0 ю соб ю

    соб ЮУ 0 б1п ЮУ

    - б1п ЮУ 0 соб ЮУ

    соб ю - б1п ю 0

    г г

    б1п ю соб ю 0

    г г

    0 0 1

    Кути (про "ОЗУ і (oz - три невідомих параметра, від яких залежить матриця R. На практиці завжди відомий діапазон, в якому вони можуть лежати. Виконуючи в цьому діапазоні повний перебір по всіх кутках з досить грубим кроком (наприклад, 1 °) , можна наблизитися до значень, що задовольняє вимогам мінімізації функціоналу J2 по R. Потім в околиці цих значень для уточнення положення мінімуму можна скористатися одним з відомих методів мінімізації (наприклад, найшвидшого спуску, Ньютона, Маркуардт).

    3. Опорні точки зображення

    Введемо поняття точкової особливості x зображення, як точки, чия околиця відрізняється від околиць прилеглих точок по обраної мірою, т. Е. {Vx: | x'-x |<r ^ p (Qx, Qx)>e |, де Qx -окрестность точки x, звана вікном пошуку, а p (fix, Q) - функція близькості околиць по деякій мірі.

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

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

    3.1. Алгоритм Харріса і Стефенса / Плессі

    Кутовий детектор Харріса грунтується на місцевій функції сигналу. Нехай у нас є точка (x, y) і деякий зсув (Ax, Ay), тоді функцію сигналу можна записати в такий спосіб:

    с (y) = Xt7 (ХГ, Уг) (X + Ax, y. + Ay)] 2, (9)

    W

    де I є функцією зображення, а (x;, y;) -точка у вікні W з центром в точці (x, y). Розклавши функцію I по Тейлору і підставивши в (9), отримаємо: Ах

    c (X, y) = [Ax Ay] C (x, y)

    Ay

    де C (x, y) фіксує

    яскравість в локальній околиці.

    Нехай А1, А2 є власними значеннями матриці С (х, у). Можливі три варіанти.

    1. Якщо обидва значення А1 і А2 близькі до 0, то це означає, що функція яскравості в околиці даної точки змінюється незначно, а значить, вона не може бути точкою особливості.

    2. Якщо одна пропозиція значення матриці велике, а інше близьке до нуля, то локальна функція яскравості змінюється в одному напрямку; це «ребро».

    3. Якщо обидва значення високі, то навіть невелике зміщення точки (x, y) в сторону викликає значні зміни в яскравості, що може бути особливістю зображення; це «кут». Точки зображення, відповідні локальним максимумів функції A = detC-k (traceC) 2, і визнаються особливостями. Параметр до зазвичай вважається рівним 0,04 ... 0,15 (запропоновано Харрісом).

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

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

    3.2. Кутовий детектор SUSAN

    Назва SUSAN походить від скорочення повного англійської назви алгоритму: Smallest Univalue Segment Assimilating Nucleus.

    Розглянемо рис. 3 із зображеним темним прямокутником на білому тлі. Кругова маска (з центром в точці, яку будемо називати ядром) показана на малюнку в п'яти можливих позиціях. Якщо яскравість кожного пікселя всередині маски порівнянна з яскравістю ядра даної маски, то тоді область маски може бути визначена як має однакову (або дуже близьку) яскравість з ядром. Ця частина маски називається USAN, скорочено від Univalue Segment Assimilating Nucleus, і зафарбована на малюнку білим кольором.

    Для виявлення особливостей SUSAN використовує круглу маску з центром в «підозрілою» точці, яка називається ядром. Радіус маски зазвичай дорівнює 3,4 пікселя, що дає маску з 37 точок. Нехай M - деяка область маски, m - точка, що належить даному регіону, а m0 - ядро ​​маски. Будемо порівнювати яскравість кожної точки маски з ядром, використовуючи наступну функцію:

    1 if \ 1 (m) -1 (mo) \ ^ t

    c (m, m0) =

    0 if \ I (m) -1 (m0) | > t '

    (10)

    На основі даної функції, пройшовши по всій масці, отримаємо підсумовує функцію:

    n (m) =? c (m, m0).

    (11)

    Ця функція означає число точок в області USAN. Параметр t в рівнянні (10) показує мінімальну межу контрасту для виділення особливо.

    Частина маски, де пікселі мають ту ж яскравість, що і ядро ​​Рис. 3. Кругові маски

    Далі, значення функції (11) в кожній точці (ядра) порівнюється з фіксованим порогом g (геометричним порогом). Значення цього порогу рекомендується встановлювати рівним 3nmJ4, де ігаах - максимальне значення функції n (m) на зображенні.

    Тоді SUSAN оператор обчислюється за такою формулою:

    R (mo) =

    g - n (mo) if n (mo) < g 0 if n (mo) ^ g '

    (12)

    Значення оператора завжди позитивне. Чим менше USAN область, тим більше відгук кута.

    Для більш стабільного результату є сенс замінити формулу (11) на наступну:

    c (m, m0) = e

    I (m) -I (mo)

    (13)

    Ті точки, в яких оператор SUSAN приймає не нульове значення, можуть бути точками особливості.

    3.3. Кутовий детектор Хедлі і Трайкович

    Цей детектор особливостей складається з точок в так званому колі Брезенхама [10] радіуса r з центром в точці передбачуваної особливості. Якщо безперервна послідовність з n точок яскравіше, ніж якесь ядро, на деяке число t або навпаки, темніше, то тоді точка ядра буде особливістю зображення. Радіус r може бути будь-яким, проте краще використовувати значення, що дорівнює 3 (відповідає колу з 16 точок кола). Крім того, експериментально обчислено, що оптимальне значення n - це 9. При n менше 9 - кути не виявляються на зображенні. детектор прямо

    перевіряє точку з навколишнім її простором. Якщо з - розглянута точка, peP - точка в колі P з центром навколо с, а точка p 'протилежна p по лінії діаметра, то функція відгуку виглядає наступним чином:

    г (с) = min [(I (p) -1 (с)) 2 + (I (p ') -1 (с)) 2].

    peP

    Точки, в яких значення функції г (с) буде більше заданого порогу, визначаються як потенційні кути. Обчислити справжні кути можна, використавши придушення в точках відсутності максимуму (non-maximum Suppression).

    3.4. Розвиток алгоритмів стеження

    Всі сучасні алгоритми стеження за особливостями спираються на роботу 1981 р Лукаса і Канаді. У 1991 р математична формулювання цього алгоритму була змінена і стала основою для всіх подальших узагальнень з урахуванням афінних спотворень околиці і освітленості.

    • Lucas-Kanade - особливість вважається тільки зміщається, без спотворень [5];

    • Tomasi-Kanade - переформулювання Lucas-Kanade. Рух вважається зміщенням, і розраховується шляхом ітеративного вирішення побудованої системи лінійних рівнянь [6];

    • Shi-Tomasi-Kanade - враховує аффінниє спотворення особливості [4].

    3.4.1. Алгоритм Lucas-Kanade

    Цей алгоритм в принципі можна застосувати для функцій будь-якої розмірності п. Нехай х - особливість першої функції F. Необхідно знайти таку точку х + h функції G, що різниця околиць цих точок у міру мінімальна.

    Відстань між околицями записується у вигляді E = [F (x + h) - G (x)] 2, де F (x), G (x) -

    дві функції, які можна розкласти в ряд Тейлора. Використовуючи це наближення, шукаємо мінімум E шляхом диференціювання і прирівнювання похідної до нуля. Зсув h можна отримати як

    -1

    h =

    [G (x) - F (x)]

    Sxl f Ilf

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

    3.4.2. алгоритм ТотазіКапаСе

    У цьому алгоритмі рух особливих точок також описується зміщенням виду: delta (x) = x + d. Як і в попередньому алгоритмі, завдання полягає в пошуку такого й, при якому мінімізується різницю

    вікон особливостей: д = X [/ (х + d, t + т) -1 (х, t)] 2.

    Розклавши функцію зображення в ряд Тейлора, різницю між вікнами в міру можна переписати у вигляді Я ~ Х [^! (Х, t) Td +1, (х, Від] 2. Продифференцировав цей вислів по ї і прирівнявши похідну до нуля, отримуємо лінійну систему щодо ї: Cd = g, де

    I..L

    і g

    = -|? I tv.

    4. Рішення завдання і результати

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

    Спочатку будемо шукати опорні точки, т. Е. Такі точки зображення, які можна відрізнити від всіх сусідніх з нею точок зображення. Поділимо зображення на 9 однакових частин, і в кожній частині будемо шукати опорну точку. Таким чином знайдемо найбільш віддалені одна від одної точки. Для пошуку будемо використовувати алгоритм Трайкович. Для другого зображення скористаємося алгоритмом Shi-Tomasi-Kanade через можливе афінного перетворення. Таким чином, отримали в кращому випадку два набори по дев'ять точок. Це надмірно, але дає шанс для більш точних подальших обчислень.

    Є рівняння виду:

    = R

    V

    x

    = до-

    i =

    З цієї системи отримуємо й як dk = C ^ lg.

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

    3.4.3. Алгоритм 5И-Тотаз1-Капас

    У цьому алгоритмі враховуються аффінниє спотворення зображення околиці особливих точок, тому рух пікселів вікна особливості описується в вигляді Ах + й, де А - матриця 2x2, а й -смещеніе.

    Завдання стеження за особливістю зводиться до проблеми визначення параметрів руху та спотворення вікна особливості, при якій мінімізується різниця д = \\ Ж [1 (&х + й) -1 (х)] 1У (х) йх, де Ж - вікно особливості, а V - вагова функція у вікні, 1 (х) і 1 (х) - два зображення.

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

    де (х, у) т - точка в площині першого зображення, що є проекцією точки в просторі (X, У,%) т, (вд) т - це точка в площині другого зображення, що є проекцією точки (ЦУ ^ Щ) т в просторі, К - матриця внутрішніх параметрів камери, R і / - шукані матриця обертання і вектор зсуву відповідно. Кожне рівняння зазначено в «своїх» координатах: перше - в глобальній системі, друге - в системі камери в першому положенні, третє в системі камери, що знаходиться у другій позиції.

    З урахуванням того, що відомі двовимірні координати точки на кожному зображенні і матриця внутрішніх параметрів, можемо вважати, що і тривимірні координати також відомі. Таким чином, отримуємо чотири рівняння виду

    Г X ^ Л Г Uл

    Y i = R V +1.

    1Z У IW j

    Розпишемо їх більш детально:

    Х1 = riiUi + ^ 12V + ЬЩ + ti

    X2 = ri1U2 + ri2V2 + ri3W2 + t1

    X3 = ri1U3 + ri2V3 + Г13Щ3 + t1 "X4 = ri1U4 + ri2V4 + Г13Щ4 + t1 Y1 = r21U1 + r22V1 + r23W1 + t2

    Y2 = r21U2 + r22V2 + r23W2 + t2

    Y3 = r21U3 + r22V3 + r23W3 + t2 Y4 = r21U4 + r22V4 + r23W4 + t2

    ^ 1 * 31 ^ 1 ^ Г32 ^ Г33Ш ^, 3

    ^ 2 = * 31 ^ 2 ^ Г32 ^ 2 ^ ^ 3 ^ 2 ^, 3

    23 = г31і3 + г32К, + г33Ш +, 3

    ^ 4 = * 31 ^ 4 ^ Г32 ^ 4 ^ ^ 33 ^ 4 ^, 3

    Бачимо, що невідомі кожної системи не залежать від невідомих інших систем. У кожній системі чотири невідомих: три з матриці обертання і одна невідома з вектора зсуву. Тому і було потрібно лише чотири особливих точки. Кожна система являє лінійні рівняння. Розпишемо докладніше першу систему:

    Х1 = Г11і1 + Г12 + Г13Ш1 +, 1

    Х2 = ^ 1 ^ 2 ^ Г12 ^ 2 ^ Г13Ш2 ^, 1

    Х3 = ^ 3 ^ Г12 ^ 3 ^ Г13Ш3 ^, 1

    Х4 = ^ 1 ^ 4 ^ Г12 ^ 4 ^ Г13Ш ^, 1

    Л

    11

    1

    -1

    = 0,

    де А =

    ^ 3 V,

    Ш3 1 х

    4 У

    Привівши А до верхньо-трикутного вигляду, отримаємо рішення в загальному вигляді:

    ,, = А45

    Г'3 = - А35 -,;

    Г 2 = -А23Г13 - ^ - А25

    Г'1 = А12Г2 - А13Г3 -, 1 - А15, '= 1 --- 3-

    Час робота алгоритмів перевірялося на трьох зображеннях, заданих заздалегідь. Зображення комбінувалися різними способами, і замірявся час роботи програми. Середній час роботи виявилося рівним 515,5 мс. Зауважимо, що аналогічне завдання в літературі не розглядалася, тому безпосередньо порівняти ефективність нашого рішення з подібним завданням неможливо. Однак, можна спробувати позиціонувати нашу задачу серед аналогічних. Близькі, але більш складні завдання виникають при обробці

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

    5. Висновок

    Значною мірою ця розробка є експериментальною. Тестування алгоритмів проводилося в умовах близьких у ідеальним. Чи не були враховані деякі умови. Отримані з камери знімки можуть відрізнятися різкістю, це може відбуватися з різних причин: не встигла відбутися фокусування, або фокус змістився щодо попереднього об'єкта фокусування. У зв'язку з цим, виникає проблема визначення відповідності точкових особливостей між кадрами зі значно відрізняється різкістю зображення. Традиційні методи, як зіставлення особливостей між кадрами, так і відстеження переміщення особливостей, не справляються з подібною ситуацією.

    Може змінюватися і ступінь освітленості зображення. У цьому випадку також можливо використовувати метод «усереднення» зображення, т. Е. Приводити всі отримані з камери зображення до заздалегідь певним зразком. Один з таких методів описаний в [5] і [7]. Як і в будь-якій роботі з зображеннями, ми не застраховані від наявності шумів на них, позбутися від яких можна за допомогою спеціальних фільтрів. Безліч таких фільтрів описані в [9]. Але будь-яке додаткове дію над зображеннями буде сповільнювати загальну роботу.

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

    і

    СПИСОК ЛІТЕРАТУРИ

    1. Грузман І.С., Киричук В.С., Косих В.П., Перетягін Г.І., Спектор А.А. Цифрова обробка зображень в інформаційних системах. - Новосибірськ: Изд-во НГТУ, 2000. -168 с.

    2. Harker M., O'Leary P. Computation of Homographies // Austria, Leoben: Tech. Rep., Dep. of Product Engineering, Univ. of Leoben, 2005. - 10 p.

    3. Zhengyou Z. A Flexible New Technique for Camera Calibration // Microsoft Research Tech. Rep. MS-98-71. - 1998. - 21 p.

    4. Shi J., Tomasi C. Good Features to Track // Proc. IEEE Conf. on Computer Vision and Pattern Recognition. - Seattle, WA, USA, 1994. - P. 593-600.

    5. Lucas B.D., Kanade T. An Iterative Image Registration Technique with an Application to Stereo Vision // International Joint Conf. on Artificial Intelligence. - 1981. - P. 674-679.

    6. Tomasi C., Kanade T. Detection and Tracking of Point Features // Carnegie Mellon Univ., Tech. Rep. CMU-CS-91-132. - 1991. -20 p.

    7. Jin H., Favaro P., Soatto S. Real-time tracking and outlier rejection with changes in illumination // Proc. IEEE Intern. Conf. on Computer Vision. - 2001. - P. 684-689.

    8. Hartley R.I. Self-Calibration of Stationary Cameras // Intern. J. of Computer Vision. - 1997. - V. 22. - № 1. - P. 5-23.

    9. Методи комп'ютерної обробки зображень / під ред. В.А. Сойфер. - М .: Физматлит, 2003. - 784 с.

    10. Van Aken J.R. An Efficient Ellipse Drawing Algorithm // Computer Graphics & Artificial Intelligence. - 1984. - V. 4. - № 9. -P. 24-35.

    надійшла 03.04.2010г.

    УДК 519.688

    АЛГОРИТМ розпаралелювання ОБРОБКИ цифровий відеопотік

    А.М. Кох

    Томський університет систем управління та радіоелектроніки E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Запропоновано новий алгоритм декодування цифрового відеопотоку, в якому використано розпаралелювання обчислень в поєднанні з синхронізацією реконструкції опорних і передбачених блоків відеоінформації. Алгоритм в два рази продуктивніше існуючих аналогів для відеопотоків стандартного дозволу і на третину для відеопотоків високої чіткості.

    Ключові слова:

    Цифрове відео, паралельні алгоритми, компенсація руху, синхронізація, MPEG, VC-1.

    Key words:

    Digital video, parallel algorithms, motion compensation, synchronization, MPEG, VC-1.

    Сімейство MPEG-форматів, що складається з MPEG-2, MPEG-4, H.264 (AVC) і VC-1, є найбільш поширеним, в зв'язку з чим завдання розробки модифікацій, спрямованих на підвищення продуктивності алгоритмів стиснення і декодування, залишається актуальною.

    Зі збільшенням дозволу і бітрейта цифрового відеопотоку (до 1920x1080 з бітрейтом до 40 Мбіт / с для відеопотоку високої роздільної здатності) застосування алгоритмів розпаралелювання для обробки цифрової відеоінформації виходить на передній план, дозволяючи використовувати всі можливості і переваги багатопроцесорної техніки.

    Відомо, що зображення в MPEG-послідовності підрозділяються на наступні типи [1]:

    • I (intra), які відіграють роль опорних при відновленні інших зображень по їх різницям;

    • Р (predicted), що містять різницю поточного зображення з попереднім I або predicted з урахуванням зсувів окремих фрагментів;

    • В (bidirectionallypredicted), що містять різницю поточного зображення з попереднім і наступним зображеннями типів I або Р з урахуванням зсувів окремих фрагментів.

    Окремі зображення складаються з макроблоків. Макроблок - основна структурна одиниця фрагментації зображення, він відповідає ділянці зображення розміром 16x16 пікселів. Для них визначаються вектори руху щодо I- або Р-зображень. У свою чергу кожен макроблок складається з декількох блоків, кількість яких визначається форматом стиснення, що несуть інформацію про яскравість Y, колірних U- і F-компонентах. Блоки є базовими структурними одиницями, над якими здійснюються основні операції кодування, в тому числі виконується дискретне косинусное перетворення (DCT - Discrete Cosine Transform) і квантування отриманих коефіцієнтів [2]. Вектори руху визначають відстань між двома фрагментами на екрані, грунтуючись на кількості пікселів між цими областями.


    Ключові слова: калібрування камери / особливості зображення / кутові детектори / алгоритми стеження за особливостями / camera calibration / feature detection / edge detection / feature point tracking

    Завантажити оригінал статті:

    Завантажити