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

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Ворошилін Олена Павлівна, Ворошилін Євген Павлович, Тисленко Володимир Ілліч


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2009
    Журнал: Доповіді Томського державного університету систем управління і радіоелектроніки

    Наукова стаття на тему 'Алгоритми супроводу рухомих об'єктів'

    Текст наукової роботи на тему «Алгоритми супроводу рухомих об'єктів»

    ?УДК 621.396: 969.1

    Є.П. Ворошилін, Є.П. Ворошилін, В.І. Тисленко

    Алгоритми супроводу рухомих об'єктів *

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

    Ключові слова: вторинна обробка, розподіл спостережень, фільтрація, супровід, оцінка координат.

    Вступ

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

    1. Розподіл оцінок - кожна позначка прив'язується до тієї чи іншої мети або вважається помилковою.

    2. Фільтрація - формування оцінок параметрів траєкторії цілі за відмітками, які були до неї прив'язані.

    розподіл спостережень

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

    На кожному такті в блок вторинної обробки (ВО) надходить сукупність відміток, які потрапляють в обраний стрибає селекції, побудований навколо екстраполювати положення цілі. Під тактом розуміється інтервал часу між двома сусідніми моментами спрацьовування алгоритму обробки. Введемо наступні позначення:'ь = {&до, г'Л = 1,2, ... №і} - сукупність тк відміток, що надійшли на до -м такті;

    'К = {'у; у = 1,2, ___, до} - сукупність всіх відміток, що надійшли з 1 по до -й такт. Кількість траєкторій, яке можна провести по цих позначок, визначається виразом

    до

    Ьк = П (1 + ту) (рис. 1). Позначимо окремо взяту траєкторію 6к, г; 1 = 1,...,.

    1 = 1

    1-й такт 2-й такт 3-й такт

    стрибає / відмітка \ варіант траєкторії 9к, г

    Мал. 1. Варіант побудови траєкторії руху цілі

    * Стаття написана в рамках реалізації ФЦП «Наукові та науково-педагогічні кадри інноваційної Росії» на 2009-2013 роки (Державний контракт № 02.740.11.0183).

    Розглянемо подія% к'1, що складається в появі траєкторії Qk'1, і позначимо його апостеріорну ймовірність bh'1 = P (xh'1 / Zk). Оптимальний фільтр супроводу повинен формувати оцінку умовного середнього стану цілі x ^ в момент часу k:

    xk = E {xk / Zk} =? bk, lE {xk / ykl, Zk} =? Pk'Z • Xk. (1)

    l = 1 i = i

    З (1) випливає, що оптимальна оцінка є лінійною комбінацією всіх приватних оцінок xk, які формуються за різними варіантами траєкторій 9k, 1. Ваговий коефіцієнт р ^ 1,1 вважається рівним достовірності l -й траєкторії. При цьому враховуються також ймовірності, що жодна з відміток на j-му такті ні породжене метою

    (Всі є помилковими). Ймовірності р ^ 1 можуть бути визначені за допомогою байєсівського правила [1]. Приватна оцінка формується обраним алгоритмом фільтрації.

    Зі збільшенням часу спостереження обсяг пам'яті і обчислювальні витрати оптимального підходу необмежено зростають. Подолати ці труднощі можна, якщо використовувати субоптимальних алгоритми - зі спрощеною структурою. Підходи до побудови фізично реалізованого фільтра [4-16], що працює в реальному масштабі часу, можна розділити на дві групи: байєсовські і небайесовскіе. Перша група [4-6, 10] заснована на різних спрощення рівняння (1), а друга - на використанні функції правдоподібності [14]. Існують також алгоритми, що використовують теорію нечітких множин та нейромереж [11, 12].

    фільтрація

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

    xk = f (xk-1) + vk, (2)

    zk = h (xk) + wk, (3) де v (k) і w (k) - випадкові векторні шумові гаусові послідовності, які не корельовані між собою і в часі.

    Відомо [1], що оптимальні байєсовські оцінки при симетричній і неубивающей функції втрат визначені у вигляді функціоналів, обчислення яких вимагає знання апостеріорної щільності розподілу ймовірностей (АПРВ) оцінюваного параметра на поточному часовому кроці при спостереженнях Zk. Класичні байєсовські оцінки зводяться до обчислення середнього, моди і медіани АПРВ. Таким чином, в загальному випадку рішення задачі фільтрації передбачає формування в пристрої обробки функції p (xk / Zk), яке містить вичерпну інформацію про поточний

    стані мети. Марківське властивість випадкового вектора xk при спостереженнях (3) дозволяє визначити рекурсивну процедуру формування АПРВ, яка складається з наступних чергуються кроків:

    1) передбачення апостеріорної функції розподілу:

    p (xk / Zk-1) = j p (xk / xk-1) • P (xk-J Zk-1) dxk-1; (4)

    2) оновлення апостеріорної функції розподілу:

    p (xk / Zk) = -P (zkl xk) • p (xk / Zfe-1) -. (5)

    j p (zkl xk-1) • p (xk-1 / Zk 1) dxk-1

    Якщо моделі (2) і (3) лінійні, а шум білий гаусів, то апостеріорне розподіл p (x ^ Zk) нормальне і рекурсія (4) - (5) є широко відомий

    фільтр Калмана, який оперує з математичним очікуванням і дисперсією цього розподілу. У загальному випадку рекурсія (4) - (5) не має замкнутого уявлення. Тому застосовуються різні наближення, які розрізняються способом апроксимації АПРВ. Серед них можна відзначити наступні:

    • Розширений фільтр Калмана (Extended Kalman Filter - EKF) - фільтр, в якому векторні функції f (x) і h (x) на кожному такті в точці передбаченого значення

    вектора стану xfe / fe-1 розкладаються в ряд Тейлора зі збереженням лінійних членів [1]. Ефективний при одномодової АПРВ.

    • Фільтр гауссовских сум (Gaussian Sum Filter - GSF) - апостеріорне розподіл апроксимується лінійною комбінацією гауссовских:

    . n

    P (Xkl Zk) ='ak, i • N (xk - ak, i, Pk, i) • P (Zk - h (xk)) !

    i = 1

    де aki - вагові коефіцієнти; a ^ i, Pki - параметри нормального розподілу i -й компоненти суміші; p (zk -h (xk)) - щільність розподілу нев'язки спостережень. Дана апроксимація використовується при багатомодовою АПРВ.

    • Фільтр частинок (Particle Filter - PF) - заснований на чисельному методі розрахунку інтегралів рекурсії (4) - (5). На кожному такті апостеріорне розподіл аппроксимирует-

    ся зваженою сумою часток x

    (P)

    k

    на безлічі можливих станів:

    N

    part

    р (хь / Zk) »^ |d (xk -xkp)), де 5 - дельта-функція, ю ^ р) - вага частинки, Npart - ко-Р = 1

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

    На рис. 2 графічно показана апроксимація цими методами.

    -J1F " >г 1 |

    0,15 -! Ukt --гЧ. ь ' !

    АПРВ 0,1 н д

    0,05 1 ДНЯ HKni 1 HHUCLi

    0 2 б

    0 2 в

    Мал. 2. Апроксимація двовимірного апостеріорного розподілу: а - розширеним ФК; б - фільтром гауссовских сум; в - фільтром частинок

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

    Алгоритм ймовірнісного об'єднання даних (Probabilistic Data Association - PDA) є субоптимальних Байєсова підходом до вирішення завдання оцінки координат цілей при наявності помилкових відміток [3]. На відміну від оптимального підходу до розподілу відміток, тут аналізуються дані тільки поточного такту. Рекурсивно по оцінці стану на попередньому такті і кожному з m (k) спостережень, що надійшли на поточному такті, формується приватна оцінка за допомогою алгоритму фільтра Калмана.

    m (k)

    Підсумкова оцінка являє собою зважену суму приватних оцінок Xk = ^ Pi Xk.

    i = 1

    Ваги Pi відповідають ймовірності того, що дане спостереження дійсно породжене метою. Обробка інформації виконується в міру надходження спостережень, тобто в режимі реального часу. Алгоритм синтезований в наступних припущеннях: кількість цілей відомо і постійно; на кожному такті від кожної мети надходить не бо-

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

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

    Імовірнісний многогіпотезний алгоритм

    У імовірнісний многогіпотезном алгоритмі (Probabilistic Multi-Hypothesis Tracker -PMHT) оцінка формується по максимуму апостеріорного розподілу P (x / Z). Пошук

    максимуму виконується за допомогою ітеративного алгоритму максимізації очікування [10]. У більшості алгоритмів ВО вважається, що від кожної мети на поточному такті обробки надходить не більше однієї позначки. На практиці ця умова може не виконуватися. Алгоритм PMHT синтезований за умови, що на кожному такті кількість відміток, породжених метою, необмежена. Це спрощує процес розподілу даних і зменшує обсяг обчислень. В іншому алгоритм PMHT синтезований при тих же припущеннях, що і PDA. Слід зазначити, що обробка даних в алгоритмі PMHT виконується не в режимі реального часу, а після надходження всіх спостережень і складається з наступних етапів:

    1. На кожному часовому такті k = 1 ... T для кожного r-го спостереження, що потрапив в стрибає селекції, розраховується апостериорная ймовірність того, що воно породжене метою: ®n (k) = N {zr (k); zn / k-1, Rn (k)}. Тут n - номер ітерації; ^ K / k-1 передбачене зна-

    чення спостереження на поточний такт; І "(й) - ковариационная матриця невязки спостережень.

    2. З урахуванням вагових коефіцієнтів ю "(й) на кожному такті по всьому спостереженнями,

    3. За «штучним» спостереженнями (на кожному такті воно одне) за допомогою фільтра Калмана рекурсивно формуються оцінки на наступних тактах.

    4. Проводиться процедура згладжування в зворотному напрямку. При цьому оцінка на останньому такті уточнює оцінку на попередньому і т.д.

    5. Пункти 1-3 итеративно повторюються до тих пір, поки різниця між оцінкою стану на поточній ітерації і попередньої не стане нижче деякого порогового значення.

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

    Серед достоїнств алгоритму PMHT слід зазначити, що обсяг обчислень лінійно зростає з числом цілей. За точносних характеристиками імовірнісний многогіпо-тезний алгоритм поступається алгоритму імовірнісного об'єднання даних. Однак при нелінійної задачі фільтрації алгоритм PMHT може дати виграш. Це пов'язано з тим, що буде итеративно уточнюватися точка лінеаризації розширеного фільтра Калмана.

    Многогіпотезний алгоритм

    Многогіпотезний алгоритм (Multi-Hypothesis Tracker - MHT) - субоптимальний підхід, заснований не так на Байєсова методі, а на методі максимальної правдоподібності [14]. При попаданні кількох позначок в стрибає селекції траєкторія розгалужується по кожній з них. При цьому розглядаються такі варіанти: а) позначка породжена однією з виявлених цілей; б) відмітка породжена новою метою; в) оцінка є помилковою. Всім варіантів траєкторій 6i присвоюється вага, рівний відповідної функції правдоподібності:

    потрапили в стрибає, формується одне «штучне»: z (k) ^^ m ^ f ю ™ (k) zr (k).

    де Zk - поточне спостереження за деякому варіанті траєкторії 6i; c - нормуючий коефіцієнт; Uk - оновлююча послідовність, що обчислюється за неузгодженості поточного спостереження з передбаченим; Sk - ковариационная матриця відновлюючої послідовності.

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

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

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

    Алгоритм об'єднання даних з використанням вейвлет-перетворення

    Більшість алгоритмів ВО (PDA, MHT, PMHT і ін.) Синтезовані за умови, що розподіл помилкових відміток рівномірний. У реальних системах воно не завжди виконується. Тому характеристики таких алгоритмів погіршуються в складній помеховой обстановці. У 2005 р був запропонований новий алгоритм об'єднання даних, що використовує вейвлет-перетворення (Multi-Space Data Association - MSDA) [15]. Він, як і метод найближчого сусіда, не вимагає знань про навколишнє середовище (щільності перешкод, ймовірності правильного виявлення і т.п.). В алгоритмі MSDA на кількох тактах вибирається спостереження, найближчим до передбаченого. За цим спостереженням за допомогою вейвлет-перетворення формується єдиний образ Zp. Він використовується для поновлення оцінки стану мети на поточному такті за допомогою алгоритму фільтрації Кал-мана. Таким чином, в процесі розподілу відміток і формування оцінки використовується не одне спостереження, а їх послідовність на кількох тактах. Це збільшує точності характеристики алгоритму в порівнянні з методом найближчого сусіда. Крім того, зменшуються обчислювальні витрати в порівнянні з PDA і MHT, тому що не всі вимірювання (а тільки найближчі «сусіди») поточного такту беруть участь в оновленні стану цілі. Моделювання алгоритму MSDA показало, що його точності характеристики краще, ніж у PDA, а обчислювальні витрати значно менше.

    висновок

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

    література

    1. Фарина А. Цифрова обробка радіолокаційної інформації. Супровід цілей: Пер. з англ. / А. Фарина, Ф. Студер. - М .: Радио и связь, 1993. - 319 с.

    2. Теорія оцінювання та її застосування в зв'язку та управлінні: Пер. з англ. / Е. Сейдж, Дж. Мелс; Ред. Б.Р. Левін. - М .: Связь, 1976. - 495 с.

    3. Інформаційні технології в радіотехнічних системах: навч. посібник / І.Б. Федоров. - М .: Изд-во МГТУ імені Н.Е. Баумана, 2004. - 764 с.

    4. Kirubaraian T. Probabilistic data association techniques for target tracking in clutter / T. Kirubaraian, Y. Bar-Shalom // Proc. IEEE. - 2004. - Vol. 92, № 3. - P. 536-557.

    5. Lee M.S. New multi-target data association using OSJPDA algorithm for automotive radar / M.S. Lee, Y.H. Kim // IEICE Trans. Electron. - 2001. - Vol. E84, № 8. -P. 1077-1082.

    6. Roecker J.A. Suboptimal joint probabilistic data association / J.A. Roecker, G.L. Phillis // IEEE Trans. Aerospace and Electronic Systems. - 1993. - Vol. 29, № 2. -P. 510-516.

    7. Musicki D. Joint integrated probabilistic data association - JIPDA / D. Musicki, R. Evams // Information fusion: The Fifth International Conference. - Melbourne, 2002. -Vol. 1. - P. 1120-1150.

    8. Bar-Shalom Y. Tracking methods in a multitarget environment // IEEE Trans. Automatic Control. - 1978. - Vol. AC-23, № 4. - P. 618-626.

    9. Pulford G.W. Taxonomy of multiple target tracking methods // IEE Proc. Radar, Sonar and Navigation. - 2005. - Vol. 152, № 5. - P. 291-303.

    10. Efe M. Probabilistic multi-hypothesis tracker: addressing some issues / M. Efe, Y. Ruan, P. Willett // IEE Proc. Radar, Sonar and Navigation. - 2005. - Vol. 151, № 4. -P. 189-196.

    11. Chin L. Application of neural networks in data fusion // Intelligent Control and Instrumentation: Singapore International Conference. - Singapore, 1992. - Vol. 2. -P. 1103-1107.

    12. Ching I.P. Neuro-fuzzy techniques for airborne target tracking / I.P. Ching, L. Yongzhi // Knowledge-based Intelligent Electronic Systems: Second International Conference. - Singapore, 1998. - Vol. 2. - P. 251-257.

    13. Chong C.Y. Ground target tracking - a historical perspective / C.Y. Chong, D. Garren, T.P. Grayson // Proc. IEEE Proc. Aerospace. - 2000. - Vol. 3. - P. 433-448.

    14. Reid D.B. An algorithm for tracking multiple targets // IEEE Trans. Automatic Control. - 1979. - Vol. AC-24, № 6. - P. 843-854.

    15. Tian H-W. A multi-space data association algorithm for target tracking systems [Інтернет] / H-W. Tian, ​​Z-L. Jing. - Режим доступу:

    http://adsabs.harvard.edu/abs/2007CNSNS .. 12. .608T, вільний.

    16. Qin Z. Interacting multiple model particle-type filtering approaches to ground target tracking [Інтернет] / Z. Qin, X. Li, J. Chen. - Режим доступу: www.academypublisher.com/jcp/vol03/no07/jcp03072330.pdf, вільний.

    Ворошилін Олена Павлівна

    Аспірант кафедри. радіотехнічних систем

    Томського державного університету систем управління і радіоелектроніки Тел .: 8-923-408-46-71 (для ред.) Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Ворошилін Євген Павлович

    Старший викладач каф. радіотехнічних систем

    Томського державного університету систем управління і радіоелектроніки Тел .: 8-923-421-19-56 (для ред.) Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Тисленко Володимир Ілліч

    Канд. техн. наук, доцент каф. радіотехнічних систем

    Томського державного університету систем управління і радіоелектроніки Тел .: (3822) 41-38-89, 8-913-802-61-41 (для ред.) Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    E.P. Voroshilina, E.P. Voroshilin, V.I. Tislenko Target tracking methods

    The article presents modern overview of target tracking algorithms in clutter environment. Keywords: secondary treatment, data association, filtration, tracking, target position estimation.


    Ключові слова: вторинна обробка / розподіл спостережень / ФІЛЬТРАЦІЯ / супровід / оцінка координат

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

    Завантажити