Для програм Second Screen існує два основних способи синхронізації контенту за аудіосигналом (Automatic Content Recognition, ACR): на базі аудіо fingerprints і з використанням цифрових водяних знаків (ЦВЗ, digital watermark). Ці технології мають принципово різні підходи.
Fingerprints - це компактне і стійке до спотворень представлення самого контенту. Процес розпізнавання полягає у створенні fingerprint аудіосигналу та пошуку за базою еталонних зразків, з подальшим вилученням необхідних даних, наприклад, назви треку і зсув запиту щодо його початку. У випадку з аудіо ЦВЗ необхідна і достатня для розпізнавання інформація ховається безпосередньо всередині самого аудіосигналу.
Я вже писав про досягнуті нами результати з розпізнавання аудіо на основі fingerprints. У цьому пості хочу розповісти про аудіо ЦВЗ і проблеми, з якими ми зіткнулися при побудові ACR на їх основі.
Недоліки fingerprints
Перш ніж перейти до ЦВЗ, відзначимо ряд проблем, що виникають при використанні ACR на базі fingerprints.
Second Screen виконує постійний запис аудіопотоку і надсилання запитів з fingerprints на сервер. Зберігання бази даних і пошук за нею, як правило, реалізується на серверній стороні. Якщо врахувати, що в Другому Екрані зазвичай зацікавлені проекти з високою популярністю, то ми приходимо до необхідності наявності достатньої кількості ресурсів для витримування високих навантажень.
Успішне розпізнавання на основі fingerprints можливе тільки при унікальності аудіо фрагмента. Однак у реальному контенті можуть бути аудіодублікати, наприклад, однаковий музичний супровід титрів або однакова фонова музика на задньому плані. В умовах шумових спотворень розпізнавання таких ділянок супроводжується високою ймовірністю помилок другого роду (помилково-позитивні спрацювання). Тому для правильної роботи програми Second Screen дані ділянки необхідно вміти заздалегідь ідентифікувати і вносити додаткові коригування в систему ACR.
В якості можливого вирішення даних проблем досить привабливо виглядає перехід на технології digital watermarking. Оскільки всі необхідні дані вже заздалегідь «вбудовані» в аудіопотік, то розпізнавання можна повністю здійснювати на боці клієнта, а унікальність ЦВЗ дозволила б позбутися проблем дублікатів і схожих аудіо фрагментів.
Вимоги до алгоритмів digital watermarking
Залежно від того, чи потрібен детектору ЦВЗ вихідний сигнал чи ні, алгоритми діляться на non-blind watermarking і blind watermarking. У контексті ACR нас цікавили blind алгоритми, які допускають вилучення знака без наявності вихідного аудіосигналу. Огляд таких методів можна переглянути в роботі [1].
Впроваджуваний аудіо watermark повинен бути прозорим (Inaudibility) - не повинен вносити будь-які спотворення, що помітно впливають на якість вихідного сигналу. Простою кількісною характеристикою прозорості є параметр SNR (Signal-to-Noise Ratio), що визначає відношення потужності вихідного сигналу до потужності спотворень викликаних ЦВЗ. Згідно з рекомендаціями IFPI (International Federation of the Phonographic Industry) SNR повинен бути більше 20 дБ. Поряд з SNR для оцінки прозорості використовується параметр ODG (Objective Difference Grade), обчислюваний відповідно до алгоритму PEAQ і змінюється від 0, при абсолютній непомітності, до -4 - при спотворенні викликають сильне роздратування. На відміну від SNR, параметр ODG враховує особливості слухової системи людини, наприклад, такі ефекти як частотне і тимчасове маскування.
Для успішного розпізнавання watermark повинен бути стійкий (robustness) до методів обробки сигналів, іменованих атаками. Він не повинен стиратися при стисненні з втратами, фільтрації, цифро-аналоговому/аналого-цифровому перетворенні, додаванні шуму тощо. Стійкість до атак оцінюють кількістю помилково декодованих біт в одиницю часу BER (Bit Error Rate).
Важливою характеристикою алгоритмів digital watermarking є пропускна здатність, тобто максимальна кількість інформації, яка може бути вкладена в одиницю часу (data rate).
Вимоги до прозорості, стійкості та пропускної здатності є взаємно протилежними - збільшення одного неодмінно призводить до зменшення двох решти (малюнок 1).
Забігаючи вперед, зазначу, що особливістю систем автоматичного розпізнавання контенту є їх відносно високі, за інших рівних умов, вимоги до стійкості ЦВЗ. При цьому алгоритм повинен бути досить швидкий, щоб використовувати його на мобільних пристроях у додатках реального часу.
Техніки Audio Watermarking
Аудіо ЦВЗ можна розглядати як модульований шум, доданий до вихідного сигналу. Алгоритми watermarking зводяться до визначення спектральних характеристик впроваджуваної інформації, щоб даний watermark відповідав пред'являється до нього вимогам.
Багато схем вбудовування та вилучення аудіо ЦВЗ мають блочно-орієнтований підхід і враховують особливості вихідного сигналу (малюнок 2). Watermark, якщо це необхідно, попередньо конвертуються в одномірну послідовність біт. Структура вбудованого потоку показана на малюнку 3. Для збільшення стійкості в ЦВЗ може бути введена надлишковість - проста реплікація біт або додавання кодів корекції (error correcting codes, ECC), наприклад, кодів Ріда-Соломона, LDPC-код (Low-density parity-check code) та ін. Кожен біт потоку вбудовується в окремий часовий блок або сегмент аудіосигналу.
Кожен блок сигналу описується вектором коефіцієнтів. У найпростішому випадку цими коефіцієнтами можуть бути безпосередньо самі семпли сигналу. У такому випадку говорять про маркування в тимчасовій області. Але, як правило, для збільшення стійкості ЦВЗ до атак використовують частотне представлення сигналу за допомогою коефіцієнтів перетворень Фур'є (DFT) [2], косинусного перетворення (DCT) [3] і вейвлет-перетворення (DWT) [4]. Існують роботи з описом сегментів сигналу на основі емпіричної модової декомпозицій (EMD) [5], кепстр-перетворення [6], комбінації частотних перетворень [7] та ряд інших. Наприклад, у роботі [8] як вектор коефіцієнтів виступають сингулярні числа, отримані в результаті сингулярного розкладання (SVD) матриці DWT коефіцієнтів сегмента сигналу.
Процес вбудовування ЦВЗ або маркування полягає у зміні вектора відповідно до обраної технікою кодування біт. В аудіостеганографії широко поширені такі техніки як Spread-Spectrum (SS), Quantization Index Modulation (QIM) і Patchwork.
Кодування біта методом SS описується рівнянням, де - маска сприйняття (у ряді алгоритмів може бути відсутнім), визначається як функція і слухової системи людини (human auditory system, HAS); - псевдопромінювальна послідовність; - значення вбудованого біта; - поелементний твір двох векторів.
У QIM методи коефіцієнти маркірованого блоку визначаються функцією модуляції, що відображає початкове значення коефіцієнта на найближче значення з безлічі при і з, де - крок квантування [9].
Широко поширені два різновиди QIM методу: distortion-compensation (DC) и dither modulation (DM). Функція вбудовування біту у випадку DC описується рівнянням, де. У DM використовується один квантувальник, а функція вбудовування визначається як, де - шум, призначений для маскування викривлень, що виникають при квантуванні, один з алгоритмів його синтезу можна подивитися в роботі [9].
Метод Patchwork полягає в розбитті безлічі коефіцієнтів блоку на два підмножини, що непересікаються, і. Вважається, що різність елементів цих підмножин має розподіл з близьким до нуля середнім значенням, тобто. Вбудовування біт зводиться до такої зміни коефіцієнтів, щоб при: , а при: , де - величина порогу детектування.
Для вставлення і виявлення watermark також можна використовувати відносно прості стратегії, показані на малюнку 4. Біти кодуються на основі функціонального зв'язку між коефіцієнтами. Ілюстрації наведені для трьох або чотирьох ознак, але техніки легко узагальнюються і на більшу кількість. Приклади алгоритмів, що використовують такі підходи, можна переглянути в роботах [2, 10].
Після вбудовування біта обчислюються зворотні перетворення, що відображають змінені коефіцієнти відповідного простору маркування на часову послідовність сигналу. Завершальним етапом вбудовування ЦВЗ є склейка всіх промаркованих блоків в єдиний сигнал, що містить watermark.
Узагальнена схема вилучення ЦВЗ представлена на малюнку 5. Одним з важливих питань у блочно-орієнтованому підході є питання синхронізації. Необхідно визначити точне положення кожного блоку в процесі декодування ЦВЗ. Для цього проводиться відновлення потоку біт при різних початкових зміщеннях і шукається синхрокод. Як критерій виявлення, зазвичай, використовується порогове значення коефіцієнта кореляції або відстань Хеммінга. Як тільки синхрокод знайдено, приступають до відновлення watermark - усувають введену на етапі маркування надлишковість.
Результати наших досліджень
В англомовному сегменті Інтернету досить різного роду публікацій з аудіо ЦВЗ. Спробувавши деякі з технік, ми не досягли результатів, що влаштовують нас. За прозорості ODG близько -1 реалізації алгоритмів [10 - 12] не змогли розпізнати watermark на мобільному пристрої навіть на відстанях близько 5 см від джерела звуку. Також ми відзначили сильну залежність прозорості досліджуваних ЦВЗ від характеру вихідного сигналу. Наприклад, watermark, не різний на слух в рок-музиці, був чуємо в промові. Боротися з цим вдавалося тільки шляхом зменшення агресивності вбудовування (збільшенням SNR), що знижувало і без того низьку стійкість ЦВЗ.
Ми вирішили реалізувати свій алгоритм, який би дозволяв динамічно підлаштовується до спектральних характеристик звуку.
Вбудовування ЦВЗ відбувається в частотній області з використанням віконного перетворення Фур'є (Short-time Fourier transform, STFT). В основу методу покладено ефект тимчасового маскування - слабкий сигнал, що виникає раніше або пізніше сильного, протягом деякого часу залишається непоміченим. Час маскування залежить від частоти і амплітуди сигналу і може досягати сотень мілісекунд.
Ми ховаємо watermark в «тіні» локальних піків спектрограми - в кожен конкретний інтервал часу вибираємо ті коефіцієнти STFT, які можна відносно нешкідливо змінювати для кодування біт (малюнок 6).
Метод дозволяє домогтися пропускної здатності в 50 bits/s, що є цілком достатнім для ACR. Правда, при такому рішенні деякі блоки сигналу залишаються не маркованими, але, як показали наші дослідження, їх частка становить близько 0.01%. Як приклад у таблиці 1 показано результати порівняльних тестів. Атаки проводилися за допомогою утиліти SMFA (StirMark for Audio) версії 1.3.2. Параметри порівнянних алгоритмів підбиралися так, щоб забезпечити однакове, наскільки це можливо, значення прозорості; ODG лежав у діапазоні від -0.5 до -0.1.
Таблиця 1 - Порівняння алгоритмів digital watermarking за параметром Bit Error Rate
Наш метод витримує з BER < 1% низькочастотну фільтрацію до 4.5 кГц, високочастотну фільтрацію до 1.9 кГц, зміну рівня звукового сигналу (від 1% до 150%), зменшення частоти дискретизації до 8 кГц.
Основним тестом, в контексті вирішуваного завдання, звичайно була перевірка стійкості watermark при акустичному поширенні сигналу. Треки з ЦВЗ були відтворені на телевізорі і записані на різні мобільні пристрої (LG-P705, Samsung GT-P7510, HTC Desire 601 тощо). Моносигнали записувалися з частотою дискретизації 44,1 кГц на різних віддаленнях від джерела звуку.
На відміну від алгоритмів [10 - 12], наші ЦВЗ розпізнаються на мобільних пристроях, але їх стійкість все одно недостатня, щоб говорити про рівноцінну заміну fingerprints. Наприклад, LG-P705 на відстані 40 см успішно розпізнавав близько 85% запитів, тоді як Samsung GT-P7510 розпізнавав 80% тільки на відстані до 5 см. У сигналах, записаних на відстанях понад 50 см, watermark вже не виявляється.
Тільки з ЦВЗ поза акустичною областю частот нам вдалося домогтися синхронізації на видаленнях більше 1 м. Для LG-P705 і HTC Desire 601 на відстанях 1.5 метрів частка правильно виявлених watermark становила 80%. Для кодування біт застосовувалася проста амплітудна модуляція гармонік з частотами понад 20 кГц (малюнок 7).
Однак не всі мобільні пристрої однаково добре справляються із записом високих частот. Той же Samsung GT-P7510 жодного разу не розпізнав даний вид watermark. Але головним недоліком таких ЦВЗ є їх нездатність пережити стиснення з втратами, що сильно обмежує можливості застосування.
Ув'язнення
Звичайно, багато що залишилося за рамками наших експериментів, але отриманий досвід змусив нас серйозно засумніватися в можливостях практичного застосування ACR на основі ЦВЗ. Принаймні, якщо говорити про watermark в області акустичних частот.
Більшість знайдених нами робіт з audio watermarking у своїх дослідженнях обмежуються синтетичними атаками SMFA і оцінкою стійкості до стиснення. Публікацій, які досліджують стійкість ЦВЗ при акустичному поширенні сигналу і запису його на мікрофон, - лічені одиниці, і ті досить поверхово зачіпають це питання, без достатньої конкретики.
Наше рішення відносно просте і досить успішно справляється з типовими тестами, а також витримує стиснення з втратами. Однак, нам не вдалося одночасно гарантувати прозорість і достатню для додатків Second Screen стійкість ЦВЗ, порівнянну з технологіями fingerprints.
Список літератури
- Harleen Kaur «Blind Audio Watermarking schemes: A Literature Review»
- Mehdi Fallahpour «High capacity robust audio watermarking scheme based on fft and linear regression»
- Baiying Lei «A multipurpose audio watermarking algorithm with synchronization and encryption»
- Hong Oh Kim «Wavelet-based audio watermarking techniques: robustness and fast synchronization»
- Shaik Jameer «A scheme for digital audio watermarking using empirical mode decomposition with IFM»
- Alok Kumar Chowdhury «A roust audio watermarking in cepsrum domain comosed of samples relation dependent embedding and computationally simple extraction phase»
- Hooman Nikmehr «A new approach to audio watermarking using discrete wavelet and cosine transforms»
- Vivekananda Bhat K «An adaptive audio watermarking based on the singular value decomposition in the wavelet domain»
- Brian Chen «Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding»
- Shijun Xiang «Audio watermarking robust against D/A and A/D conversions»
- Hong Oh Kim «Wavelet-based Audio Watermarking Techniques: Robustness and Fast Synchronization»
- Jong-Tzy Wang «Adaptive Wavelet Quantization Index Modulation Technique for AudioWatermarking»