Створення користувацьких інтерфейсів для систем автомобільної навігації – задача, котра часто стоїть перед розробниками на Automotive проєктах.
Під час тестування цих UI виникає ряд кейсів, котрі можна вирішувати за допомогою технологій Computer Vision. У своїй статті я хотів би оглянути такі кейси.
У якості ілюстрацій будемо використовувати приклади з Google Maps – одного з найбільш поширених сьогодні навігаційних додатків. Набір його функцій досить простий і водночас достатній для того, щоб побачити основні проблеми автоматизованого тестування систем навігації.
Пропоную почати із загального знайомства з теорією комп’ютерного зору та принципами роботи алгоритмів, що порівнюють зображення. Далі перейдемо до спостережень за роботою скриптів для ідентифікації об’єктів на графічних файлах.
У цій статті я не планую розповідати про методологію, за якою OpenCV працює із зображеннями (малювання фігур, читання з файлу тощо). Однак за потреби, базову інформацію ви знайдете за цими посиланнями:
Основні проблеми
Більшість елементів інтерфейсу в навігаційних додатках кодуються HTML або XML мовами, а також засобами CSS. Подібні кейси можна вважати найпростішими. Підхід до тестування тут зводиться до того, що ми знаходимо відповідний елемент у коді сторінки і співставляємо його характеристики із заданими.
Якщо додаток передбачає кілька сценаріїв взаємодії юзера з тим чи іншим UI елементом, ми можемо автоматично імітувати різні user flow. Радити для цього якийсь конкретний інструмент сенсу немає, як правило, його вибір визначається особистими уподобаннями AQA інженера, що працює у команді. Appium, Ranorex, Webdriver та інші повністю покривають задачі автоматизованого тестування елементів, описаних мовами розмітки. Усі вони придатні для роботи з будь-якою платформою - web, mobile, desktop.
Приклад такого елементу – кнопка «Ресторани» у Google Maps. У верстці без проблем можна ідентифікувати і сам елемент, і його характеристики: колір, розмір, статус тощо.
Google Maps: кнопка “Ресторани” в HTML
На жаль, далеко не всі складові інтерфейсу під час тестування можна ідентифікувати у верстці. Частина картографічних об’єктів Google Maps – населені пункти, дороги, вулиці, будівлі тощо – реалізовані у рамках canvas. Анімовані елементи, динамічно побудовані графіки та діаграми також неможливо “витягнути” з HTML чи XML.
Усе це призводить до того, що стандартними засобами автоматизованого тестування ми не зможемо виконати навіть базовий тест – чи є коректною отримана користувачем локація на карті?
Приклад інтерфейсу системи навігації
Питання ускладнюється і тим, що інструментів для подібних тестів мало і майже всі вони не є безкоштовними.
Почнемо з очевидних рішень. Для того, щоб у ході тесту встановити, чи відображено на моніторі користувача потрібний елемент, ми можемо співставляти скрін поточного стану додатку із зображенням, котре ми вказуємо як еталонне.
Додатково можна вказати координати тієї частини екрану, в межах якої розташований об’єкт тестування і саме його порівнювати з еталоном.
Цей метод є релевантним для тестування статичних елементів, котрі не переміщаються під час роботи користувача з додатком і завжди зберігають один і той самий вигляд, не перекриваються іншими елементами і не змінюються при взаємодії з ними.
Відразу зазначимо, що ймовірність повного співпадіння тестованого та еталонного зображень дуже низька. Кілька скріншотів з одним і тим самим елементом можуть мати відмінності, наприклад, через різні точки погляду чи через рендерингові артефакти.
Використання pHash для тестування навігаційних систем
Отже, при тестуванні навігаційних сервісів перед нами часто стоятиме задача співставлення спотвореної картинки з еталоном. Зараз розробникам доступний цілий ряд інструментів, здатних здійснювати таке співставлення, “ігноруючи” певний рівень спотвореності. Для прикладу, на проектах з Ruby можна використовувати RMagick, Imatcher, Vips.
Надалі у статті ми розглянемо, як співставляє картинки pHash – поширений мультиплатформений сервіс, котрий ми використовуємо на нашому проєкті. З демоверсію pHash можна ознайомитися на офіційному сайті.
Якою є базова послідовність роботи цієї бібліотеки, якщо нам, наприклад, потрібно порівняти еталон і зашумлене фото?
- Алгоритм обраховує у байтах різницю між двома картинками – так звану hamming distance.
- Вираховується максимальне (порогове) значення, за межами якого картинки вже вважатимуться неоднаковими.
Демо: порівняння еталонного і зашумленого зображень (з сайту pHash)
Поглянемо на нашу тестову картинку. При пороговому значенні у 26 байт відмінність склала усього 12. За висновками pHash, ці два фото є ідентичними.
Тести позиціонування автомобіля
Перейдемо власне до тестування інтерфейсів навігаційних систем. Подивимося, як pHash працює у тестах, пов’язаних з поточним місцезнаходженням автомобіля.
Під час тесту нас цікавила та частина мапи, на якій був відображений автомобіль. На ілюстрації нижче ця зона закрита чорним чотирикутником. Факторів для спотворень порівнюваної зони було чимало: ДТП і затори на дорозі, ремонтні роботи і тимчасові зміни схем руху, нові об’єкти на карті (ресторани, супермаркети, АЗС), різні версії аплікації і мапи тощо. Як наслідок – численні спотворення: накладання іконок одна на одну або поява нових, перекриття написів іконками, зміщення напрямку, у якому рухається автомобіль.
Розглянемо числові показники нашого тесту. Праворуч показано, на скільки байтів кожен з фрагментів відрізняється від еталонного. Мінімальна відмінність між картинками становить 6 байт, максимальна – 17. Таким чином, якщо порогове значення установити в 20 байт, тест, вірогідно, буде пройдений успішно – за умови, що на картинках відображена коректна локація (низька ймовірність помилки другого роду – хибний fail).
З іншого боку, неправильні картинки (випадок помилки першого роду – хибний pass), скоріше за все, тест не пройдуть.
Фрагменти з аналогічним розташуванням автомобіля: праворуч – різниця у байтах
Тестування функції Zoom In
Порогові значення можуть суттєво відрізнятися для різних типів тестів.
Поглянемо на різницю з еталонним фрагментом при тестуванні функції Zoom In. Максимальний показник у даному випадку – 27, і, якщо б ми встановили порогове значення 20 у цьому тесті, то друге і третє зображення були б кваліфіковані як помилка другого роду. Насправді ж функція збільшення спрацювала коректно на усіх картинках.
Фрагменти з аналогічним розташуванням автомобіля після використання функції Zoom in
Яким чином можна мінімізувати кількість подібних помилок? Ми вдалися до збільшення кількості еталонів, з якими проводилося порівняння. Для окремих тестів ми створювали до 8 еталонних зображень.
Це дозволило зменшити ймовірність помилок другого типу (хибний fail), але водночас зросла вірогідність помилок першого типу (хибний pass). Це закономірно: чим більше у нас еталонів, тим вище ризик, що один з них співпаде з некоректною локацією.
На ілюстрації нижче ми бачимо такий приклад. На картинках з різними локаціями pHash оцінює hamming distance у 21, що дуже близько до порогового значення 20, або навіть у 18, що означає, що у нас виник хибний фейл.
Фрагменти з різним розташуванням автомобіля: різниця у байтах
Кількість тестів на нашому проєкті зростала, і ми все більше переконувалися, що метод порівняння спотворених зображень з еталонним для тестування навігаційних систем не підходить.
На цьому етапі ми прийшли до використання комп'ютерного зору.
OpenCV – “універсальний солдат” комп’ютерного зору
Почнемо з визначення. У сучасних інформаційних системах Computer Vision - це набір теорій та методологій, покликаних навчити машини розрізняти та інтерпретувати візуальні об’єкти.
Найбільш популярною бібліотекою з алгоритмами компьютерного зору є Open Source Computer Vision Library (OpenCV). Вона реалізована для С/С++, Java, Ruby, Python та інших мов програмування.
OpenCV – це, без перебільшення, “універсальний солдат” у сфері Computer Vision. Він використовується для локалізації та аналізу руху графічних об’єктів, їх сегментування тощо. Ми розглянемо детальніше лише методологію Template Matching. Саме її ми будемо використовувати для переважної більшості тестів навігаційних систем. Через простоту інсталяції і створення скриптів ми будемо працювати з OpenCV, реалізованою для Python2.
Що таке Template Matching
У чому полягає суть методу Template Matching? Ми створюємо темплейт – фрагмент вихідного зображення, котрий нам необхідно виявити на тестових картинках. У ході Template Matching система попіксельно переміщує заданий шаблон по висоті і по ширині тестованого зображення. Щоразу, коли темплейт перемістився на один піксель, система співставляє сканований фрагмент з темплейтом і обчислює рівень співпадіння обох зображень.
Усі проскановані ділянки маркуються відтінками сірого. Чим більше фрагмент співпадає з шаблоном, тим світлішим кольором він буде позначений.
Після завершення сканування у нашому розпорядженні буде монохромне зображення, де кожен піксель матиме свій колір. Нам залишається лише застосувати фільтр і визначити найбільш світлу ділянку. Саме вона і буде тим фрагментом, котрий максимально співпав з темплейтом.
Розглянемо роботу метода на конкретному прикладі. Нижче ви бачите фото знаменитого аргентинського форварда в момент удара по м’ячу. Застосуємо метод Template Matching, щоб визначити фрагмент фотографії, де розташоване обличчя футболіста.
Шаблонна, тестова та підсумкова картинки у методі Template Matching
Готуємо темплейт – вирізаний з вихідного фото прямокутник з обличчям. Запускаємо сканування. Результат співставлення – монохромна картинка, на якій найсвітлішу точку видно навіть без застосування додаткових фільтрів.
Потрібно враховувати, що підсумкове зображення в Template Matching буде меншим, ніж вихідне, на висоту і ширину заданого шаблона, оскільки при порівнянні крайніми пікселями стануть внутрішні межі темплейта у тих місцях, де його зовнішній край досяг края вихідної картинки.
Методи співставлення картинок
Кілька слів про інструменти. Для Python ми працюємо з методом machTemplate у модулі сv2. Для роботи знадобляться 3 параметри: зображення, котре ми будемо тестувати, шаблон і найменування алгоритму для співставлення.
Визначити максимально світлі й темні фрагменти на підсумковому зображенні допоможе функція minMaxLoc.
Для співставлення шаблону можуть використовуватися три різних алгоритми. Одні з них маркують фрагменти з найвищим матчингом максимально світлою точкою (TM_CCOEFF, TM_CCORR), інші – темною (TM_SQDIFF).
Дефолтним є алгоритм TM_CCOEFF, котрий добре працює з різними типами зображень. Проте не в усіх випадках він виявляється оптимальним, тому є сенс експериментувати з різними алгоритмами.
На основі чого приймається остаточне рішення про співпадіння фрагменту? Усі згадані вище алгоритми можуть працювати з нормованим і ненормованим методом.
При використанні ненормованого методу у нас відсутні заздалегідь визначені числові значення, котрі б вказували на рівень співпадіння. Фрагменти з максимальним матчингом на підсумковому зображенні будуть позначені пікселем з довільною яскравістю – наприклад, 1392 одиниці. На підставі цих даних важко ідентифікувати достатній рівень матчингу.
У нормованому матчингу усі співставлені зображення оцінюються по шкалі від 0 до до 1, де 0 дорівнює 0% співпадіння, а 1 – 100%. Відповідно, ми можемо вказати мінімально допустиме значення матчингу, наприклад, 0.7 і приймати рішення про співпадіння фрагменту на основі його відповідності нашому пороговому значенню.
Розглянемо роботу нормованої версії матчингу на прикладі картинки з усім відомої гри. Нам потрібно порахувати кількість монет. Монетка, власне, і буде нашим еталонним зображенням. Встановлюємо порогове значення (припустимо, 0.8), визначаємо найбільш світлі ділянки, застосовуємо фільтр, щоб визначити ті з них, котрі більше або дорівнюють 0.8. Саме ці ділянки і будуть тими місцями, де на вихідному зображенні є наш об’єкт – монета.
Використання Template Matching для ідентифікації кількох об’єктів
Template Matching і спотворення зображень
Повернемося до теми нашої статті. Чи підходить Template Matching для тестування геолокаційних сервісів? Коротка відповідь – ні. Це незамінний сервіс для роботи зі статичними елементами інтерфейсу – кнопками, іконками, полями, формами тощо. Однак у навігаційних додатках зображення і написи – назви вулиць, напрямки руху, позначки автомобіля, – спотворюються, зміщуються і накладаються одне на одне. У цих випадках Template Matching видає багато помилок.
Щоб остаточно переконатися у невідповідності методу потребам тестування локацій, спробуємо порівняти розташування двох київських описів Intellias – на вул. Кирилівській, 39 і на вул. Кирилівській 15/1. У якості темплейта візьмемо локацію на Кирилівській, 39 і порівняємо його з локацією на Кирилівській, 15/1.
Template Matching для співставлення локацій
Отриманий результат – 0.85, при максимальному значенні 0.8. Отже, при тестуванні методом Template Matching ми зробили б висновок, що це – дві ідентичних локації.
Ідентифікація об’єктів на спотворених малюнках
Щоб проілюструвати, як алгоритми комп’ютерного зору здійснюють пошук тих чи інших елементів на карті, достатньо згадати заняття, відоме усім нам з дитинства: складання пазлів.
Пригадайте, які частини картинок завжди залишаються наостанок? Ті, котрі скласти найважче: великі ділянки фону. Небо, стіни, хвилі, крони дерев – шматочки пазлу, з яких вони складаються, мало чим відрізняються один від одного.
Подивимося на ілюстрацію нижче. Однотипні фрагменти на ній позначені буквами А і В. По малюнку на фрагментах C та D вже можна визначити вертикальну або горизонтальну орієнтацію фрагмента, проте усе ще залишаються варіанти відносно його розташування вздовж цих вертикальних чи горизонтальних площин. А от фрагменти Е і F – це кутики. Вони настільки характерні, що ми точно можемо сказати, де саме вони мають розташовуватися.
У методології комп’ютерного зору елементи яким можна дати характеристику, називаються Features. Процес опису цих елементів - це Feature Description, а їх ідентифікація алгоритмом – Feature Detection.
Ще наприкінці 80-х років минулого століття Кріс Харріс розробив метод, покладений в основу сучасних Corner Detectors – алгоритмів у Computer Vision, мета яких – ідентифікація кутиків на зображеннях.
Метод Харріса полягав у тому, що весь малюнок розділявся на окремі частини. Далі, у процесі руху вздовж кожної частини, алгоритм порівнював їх з сусідніми частинами – по горизонталі і вертикалі. Далі усе залежало від того, чи змінюються характеристики зображеного об’єкта при русі. Метод оперував трьома основними визначеннями:
- плаский об’єкт – якщо характеристики на сусідніх частинах не відрізняються ні по вертикалі, ні по горизонталі;
- межа – характеристики змінюються тільки по одному з напрямків;
- кут – спостерігаємо зміну характеристик і у вертикальній, і у горизонтальній площині.
Метод Харріса
Головна задача, котру вирішують сучасні алгоритми при співставленні об’єктів – це ідентифікація кутів.
Метод cornerHarris, застосовуваний в OpenCV, призначений власне для пошуку кутів. Під час ідентифікації об’єктів можна задавати коефіцієнти, котрі визначатимуть отримані точки якісно і кількісно. В залежності від потреб, можна використовувати значення коефіцієнтів за замовчуванням або встановлювати власні.
Метод cornerHarris
Після того, як ми ідентифікували усі кути на тестованому зображенні, нам необхідно визначити їх характеристики.
Описаний Девідом Лоу алгоритм Масштабно-інваріантної трансформації ознак (Scale-Invariant Feature Transform, SIFT) виділяє з “тренувального зображення” ряд точок кута (дескрипторів), котрі надалі допоможуть алгоритму розпізнати той самий кут на зашумлених зображеннях, зображеннях з іншим масштабом, при частковому перекритті об’єкта тощо.
SIFT: обчислення дескрипторів
Отже, у нашому розпорядженні є кути – точки, за якими ми будемо порівнювати об’єкти, і їхні характеристики – дескриптори. Ми можемо переходити власне до співставлення тестованих зображень.
Для початку розглянемо, як відбувається порівняння у тесті Девіда Лоу, про якого ми вже згадували у цій статті.
Суть тесту полягає у тому, що алгоритм знаходить для кожної точки-дескриптора на зображенні 1 аналогічну точку-дескриптор на зображенні 2. Різниця між ними, у разі, якщо зображення ідентичні, має наближатися до 0. Для неоднакових зображень ця різниця буде значно вищою.
При проведенні тесту ми можемо встановлювати мінімальну різницю між найкращими матчингами та усіма іншими матчингами. Наприклад, вкажемо, що прийнятні для нас співпадіння мають будуть кращими за інші мінімум на 75%.
Подивимось на порівнювані трикутники на ілюстрації. Для верхнього кута першого трикутника маємо результати порівняння з іншими точками – 3, 7, 8. Результат 3 складає 42% від результату 7 та 37% від 8. Оскільки пороговим значенням ми встановили 75%, то це співпадіння ми приймаємо.
Метод Девіда Лоу
Перейдемо до середньої з трьох точок. Для неї у нас є дескриптори 4, 5, 6. У результату 4 відношення сягає 66% від 6, але 80% від 5. Порогове значення перевищено на 5%, тому ці точки ми вважаємо неідентичними.
Для порівняння зображень широко використовується ще одна методологія – Cross Check. На відміну від теста Девіда Лоу, тут проводиться подвійна перевірка – спочатку проводиться матчинг усіх точок зображення 1 з точками зображення 2, а потім навпаки – точки зображення 2 порівнюються з точками зображення 1. Матчинг є прийнятним за умови, що різниця між двома точками в обох напрямках є меншою за різницю з усіма іншими точками.
Повернемося до прикладу з трикутниками. Серед трьох точок співставлення для верхнього кута на обох зображеннях метод зматчить лише точки з найменшою різницею (і нашому випадку - 33%).
Метод Cross Check
Стислі підсумки
У цій статті ми обговорили окремі складові теорії комп’ютерного зору і розглянули можливості бібліотеки OpenCV, котрі, сподіваюся, стануть у пригоді під час автоматизованого тестування навігаційних сервісів.
