Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів
Запропоновано модель багатовимiрних часових рядiв, яка настроюється, на базi модифiкацiї алгоритму експоненцiйно зваженої стохастичної апроксимацiї для задачi пошуку змiн у вiдеоданих....
Gespeichert in:
| Datum: | 2012 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Schriftenreihe: | Доповіді НАН України |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/84775 |
| 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: | Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів / Є.В. Бодянський, С.В. Машталiр // Доповiдi Нацiональної академiї наук України. — 2012. — № 11. — С. 30-33. — Бібліогр.: 12 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84775 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-847752015-07-16T03:01:51Z Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів Бодянський, Є.В. Машталір, С.В. Інформатика та кібернетика Запропоновано модель багатовимiрних часових рядiв, яка настроюється, на базi модифiкацiї алгоритму експоненцiйно зваженої стохастичної апроксимацiї для задачi пошуку змiн у вiдеоданих. Предложена настраиваемая модель многомерных временных рядов на базе модификации экспоненциально взвешенной стохастической аппроксимации для задачи поиска изменений в видеоданных. The multidimensional time series adjusted model is offered on the basis of a modification of the exponentially self-weighted stochastic approximation for the search for video changes. 2012 Article Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів / Є.В. Бодянський, С.В. Машталiр // Доповiдi Нацiональної академiї наук України. — 2012. — № 11. — С. 30-33. — Бібліогр.: 12 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/84775 004.9 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Бодянський, Є.В. Машталір, С.В. Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів Доповіді НАН України |
| description |
Запропоновано модель багатовимiрних часових рядiв, яка настроюється, на базi модифiкацiї алгоритму експоненцiйно зваженої стохастичної апроксимацiї для задачi пошуку змiн у вiдеоданих. |
| format |
Article |
| author |
Бодянський, Є.В. Машталір, С.В. |
| author_facet |
Бодянський, Є.В. Машталір, С.В. |
| author_sort |
Бодянський, Є.В. |
| title |
Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів |
| title_short |
Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів |
| title_full |
Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів |
| title_fullStr |
Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів |
| title_full_unstemmed |
Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів |
| title_sort |
виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2012 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84775 |
| citation_txt |
Виявлення змін у потоці відеоданих на основі аналізу багатовимірних часових рядів / Є.В. Бодянський, С.В. Машталiр // Доповiдi Нацiональної академiї наук України. — 2012. — № 11. — С. 30-33. — Бібліогр.: 12 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT bodânsʹkijêv viâvlennâzmínupotocívídeodanihnaosnovíanalízubagatovimírnihčasovihrâdív AT maštalírsv viâvlennâzmínupotocívídeodanihnaosnovíanalízubagatovimírnihčasovihrâdív |
| first_indexed |
2025-07-06T11:54:22Z |
| last_indexed |
2025-07-06T11:54:22Z |
| _version_ |
1836898439651131392 |
| fulltext |
оповiдi
НАЦIОНАЛЬНОЇ
АКАДЕМIЇ НАУК
УКРАЇНИ
11 • 2012
IНФОРМАТИКА ТА КIБЕРНЕТИКА
УДК 004.9
© 2012
Є.В. Бодянський, С.В. Машталiр
Виявлення змiн у потоцi вiдеоданих на основi аналiзу
багатовимiрних часових рядiв
(Представлено членом-кореспондентом НАН України М.Ф. Бондаренком)
Запропоновано модель багатовимiрних часових рядiв, яка настроюється, на базi модифi-
кацiї алгоритму експоненцiйно зваженої стохастичної апроксимацiї для задачi пошуку
змiн у вiдеоданих.
Задача виявлення змiн мультимедiйних даних привертає сьогоднi все бiльшої уваги. Це по-
в’язано, насамперед, зi значним збiльшенням iнформацiйних потокiв i з тим, що виникає
потреба виявлення змiн у масивах даних, що динамiчно змiнюються, таких, як звук або
вiдеоданi. При цьому слiд зазначити, що одним iз шляхiв обробки мультимедiйних даних
є подання їх у виглядi одно- або багатовимiрного часового ряду з подальшим виявленням
змiн його властивостей. Задача дослiдження змiн властивостей часових рядiв i їх сегментацiї
досить давно цiкавить дослiдникiв [1–4], а для її розв’язання до теперiшнього часу склалася
низка вiдносно незалежних пiдходiв, серед яких, в першу чергу, необхiдно вiдзначити ста-
тистичний, адаптивний та заснований на методах класифiкацiї. I якщо для одновимiрних
рядiв розробленi досить ефективнi алгоритми аналiзу [5–7], результати, що вiдносяться до
багатовимiрних послiдовностей, значно скромнiшi [4, 8].
В той же час зрозумiло, що у важливих застосуваннях, пов’язаних, насамперед, з оброб-
кою вiдеосигналiв, доводиться мати справу з багатовимiрними сигналами i необхiднiстю їх
аналiзу в реальному часi. В зв’язку з цим можна говорити про таку важливу задачу в рам-
ках загальної проблеми iнтелектуального аналiзу даних [2] як розбиття тимчасових рядiв на
вiдносно однорiднi сегменти i виявлення моменту переходу вiд одного сегмента до iншого.
Iншими словами, можна казати про необхiднiсть розв’язання задачi покадрового аналiзу
результатiв сегментацiї вiдеоданих.
Найбiльш компактною формою опису багатовимiрного часового ряду, яким можна по-
дати довiльнi вiдеоданi, особливо у випадку, коли число спостережень не фiксоване i росте
з часом, є його математична модель, що в тiй або iншiй формi описує характеристики, якi
нас цiкавлять. Для розв’язання задачi виявлення змiни властивостей багатовимiрних рядiв
30 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №11
зручним, компактним i ефективним їх описом є так званi векторнi авторегресiйнi моделi
(VAR-моделi) [3].
У загальному випадку VAR-модель зв’язує минулi i поточнi спостереження векторного
сигналу x(k) у формi
x(k) = B0 +
p∑
l=1
Blx(k − l) + ξ(k), (1)
де B0 = {b0i} − (n × 1)-вектор середнiх значень; Bl = {blij} − (n × n)-матрицi параметрiв;
p — порядок моделi.
Початковою iнформацiєю для розв’язання задачi iдентифiкацiї i виявлення змiн є тiльки
сам n-вимiрний часовий ряд x(k), значення якого в реальному часi надходять на адаптивний
iдентифiкатор.
Для спрощення подальших викладок введемо в розгляд складену матрицю B =
= (B0
...B1
... . . .
...Bp) i вектор передiсторiї X(k) = (1, xT (k − 1), . . . , xT (k − p))T розмiрностi
((pn + 1) × 1)), пiсля чого перепишемо рiвняння (1) у виглядi
x(k) = BX(k) + ξ(k), (2)
де матриця апрiорi невiдомих параметрiв B мiстить практично всю необхiдну iнформацiю
про властивостi контрольованого сигналу.
Задача iдентифiкацiї полягає в тому, що у вiдповiднiсть сигналу (2) ставиться модель,
що настроюється
x̂(k) = B(k − 1)X(k), (3)
матриця параметрiв B(k) якої уточнюється на кожному тактi часу k шляхом мiнiмiзацiї
прийнятого критерiю iдентифiкацiї, що є деякою функцiєю рiзницi розрахованих x̂(k) i екс-
периментальних даних x(k). При цьому синтезована модель (3) має бути працездатною i
в режимi прогнозування, а порушення прогнозуючих властивостей може бути ознакою ви-
никнення тих або iнших змiн у сигналi. Процес настроювання моделi (3) можливо реалiзо-
вувати за допомогою рекурентних процедур, якi зручно навести в узагальненому виглядi [9]
{
B(k) = B(k − 1) + γ(k)e(k)XT (k),
e(k) = x(k)− x̂(k) = x(k)−B(k − 1)X(k),
(4)
де γ(k) — скалярний або матричний коефiцiєнт кроку пошуку алгоритму, що визначає його
властивостi i залежить вiд прийнятого критерiю iдентифiкацiї; e(k) — векторна похибка
iдентифiкацiї.
Пропонується ввести в розгляд багатовимiрну модифiкацiю алгоритму експоненцiйно
зваженої стохастичної апроксимацiї [10] у виглядi
B(k) = B(k − 1) +
e(k)XT (k)
βr(k − 1) + ‖X(k)‖2
,
r(k) = βr(k − 1)− ‖X(k)‖2
(5)
(тут 0 6 β 6 1 — параметр пам’ятi алгоритму), яка є своєрiдним компромiсом мiж одно-
кроковою процедурою, що є узагальненням оптимального за швидкодiєю алгоритму Кач-
мажа [11] на векторно-матричну модель, i рекурентним експоненцiйно зваженим методом
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №11 31
найменших квадратiв. Ця модифiкацiя позбавлена недолiкiв своїх прототипiв i має необ-
хiднi згладжуючi i слiдкуючi властивостi.
Механiзм адаптацiї алгоритму (5) заснований на “пригнiченнi” застарiлої iнформацiї,
при цьому динамiчнi властивостi алгоритму повнiстю визначаються пам’яттю, на основi
якої вiдбувається уточнення матрицi поточних оцiнок B(k).
Слiд зазначити, що найкращi фiльтруючi властивостi мають алгоритми з необмеженою
пам’яттю, такi як рекурентний метод найменших квадратiв, в той же час цi процедури
мають поганi слiдкуючi властивостi у разi, якщо характеристики контрольованого сигналу
змiнюються в часi. В цьому випадку перевагу мають алгоритми з “короткою” пам’яттю типу
алгоритму Качмажа, проте цi процедури погано працюють в умовах перешкод.
Таким чином, при оцiнюваннi систем, в яких можуть вiдбуватися змiни, об’єм пам’я-
тi алгоритму слiд вибирати на основi компромiсу мiж його згладжуючими i слiдкуючими
властивостями. На жаль, в реальних ситуацiях характеристики збурень, дрейфiв та стриб-
кiв апрiорi невiдомi i можуть змiнюватися в процесi функцiонування контрольованої сис-
теми. В цих умовах важко вiддати перевагу одному алгоритму з фiксованою пам’яттю,
а тому доцiльно використовувати алгоритми зi змiнною пам’яттю, величину якої можна
оперативно змiнювати залежно вiд наявностi або вiдсутностi змiн у сигналi.
Для контролю за змiнами багатовимiрного часового ряду доцiльно використовувати мо-
дифiкацiю критерiю Манна–Уiтнi [12] у виглядi
max
(
k∑
u=k−S+1
sign(xi(u)− x̂i(u))
)
> γ (6)
(тут γ — деякiй порiг, що обирається з емпiрiчних мiркувань), тобто одночасно контролю-
вати усi компоненти i фiксувати факт змiни, якщо розладнання станеться в хоч би однiй
компонентi xi(k).
Запропонований метод пошуку змiн був експерементально перевiрений у задачi пошуку
та аналiзу в базах вiдеоданих медицинської тематики. Результати аналiзу методу дозво-
ляють стверджувати, що якщо вiдбуваються швидкi змiни сцен, цей процес добре вiдслiд-
ковується, однак з бiльш плавними змiнами є деякi питання, якi ще потребують свого ви-
рiшення.
1. Клигенс Н., Тельскис Л. Методы обнаружения моментов изменения свойств случайных процессов //
Автоматика и телемеханика. – 1983. – № 10. – С. 5–56.
2. Abonyi J., Feil B., Nemett S., Arva P. Fuzzy clustering based segmentation of timeseries // Lecture Notes
in Computer Science. – 2810. – Berlin: Springer, 2003. – P. 275–285.
3. Гребенюк Е.А. Обнаружение изменений свойств нестационарных случайных процессов // Автомати-
ка и телемеханика. – 2003. – № 12. – С. 44–59.
4. Гребенюк Е.А. Методы анализа нестационарных временных рядов с неявными изменениями
свойств // Там же. – 2005. – № 12. – С. 3–30.
5. Isermann R. Process fault detection based modeling and estimating methods – a survey // Automatica. –
1984. – 20, No 4. – P. 387–404.
6. Бассвиль М., Вилски А., Банвенист А. Обнаружение изменений свойств сигналов и динамических
систем. – Москва: Мир, 1989. – 278 с.
7. Badavas P.C. Real-time statistical process control. – Englewood Cliffs: Prentice-Hall, 1993. – 232 p.
8. Abonyi J., Feil B., Nemett S., Arva P. Modified Gath-Geva clustering for fuzzy segmentation of multivari-
able timeseries // Fuzzy Sets and Systems. – 2005. – 149. – P. 39–56.
9. Льюнг Л. Идентификация систем. Теория для пользователя. – Москва: Наука, 1991. – 432 с.
32 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №11
10. Бодянський Є.В., Плiсс I. П., Соловйова Г.В. Синтез квазiпрямих адаптивних регуляторiв // Доп.
АН УРСР. Сер. А. – 1987. – № 1. – С. 59–61.
11. Kaczmarz S. Approximate solution of systems of linear equations // Int. J. Control. – 1993. – 57, No 5. –
P. 1269–1271.
12. Chow E.Y., Willsky A. S. Issues in the development of a general design algorithm for reliable failure
detection // Proc. 19-th IEEE Conf. Decis. Aut. Contr. – Albuquerque, 1980. – P. 1006–1012.
Надiйшло до редакцiї 20.03.2012Харкiвський нацiональний унiверситет радiоелектронiки
Е.В. Бодянский, С.В. Машталир
Обнаружение изменений в потоке видеоданных на основе анализа
многомерных временных рядов
Предложена настраиваемая модель многомерных временных рядов на базе модификации
экспоненциально взвешенной стохастической аппроксимации для задачи поиска изменений
в видеоданных.
Ye. V. Bodyanskiy, S.V. Mashtalir
Search for video stream changes via multidimensional time series
analysis
The multidimensional time series adjusted model is offered on the basis of a modification of the
exponentially self-weighted stochastic approximation for the search for video changes.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №11 33
|