Технології комп’ютерного зору в UI-тестуванні. Частина 1
Всім привіт! Мене звати Дмитро, я працюю AQA інженером в компанії Intellias на automotive проєкті. У цій статті я хочу розказати про технології комп’ютерного зору, які допомогли вирішити багато складних задач у тестуванні UI автомобільної навігаційної системи.
У першій частині ми розглянемо деякі алгоритми порівняння зображень та познайомимося з теорією Computer Vision. У другій частині перейдемо до реалізації скриптів для пошуку об’єктів на зображеннях та інтегруємо їх у тестовий фреймворк. Для прикладів будемо використовувати Google Maps — відомий додаток з простим функціоналом, на якому можна показати всі складнощі автоматизації навігаційної системи.
У статті наведені деякі приклади коду, проте їх ціль більше демонстративна, ніж практична. Посилання на програмне рішення з повним описом його встановлення та роботи буде доступне у кінці другої частини.
Базові методи роботи із зображеннями в OpenCV, такі як: читання з файлу, збереження, малювання фігур тощо, виходять за рамки цієї статті, однак ви можете ознайомитися з ними тут і ось тут.
Проблематика
Зазвичай в аплікаціях UI елементи описуються мовою розмітки (HTML чи XML) у поєднанні з таблицею стилів. У цьому випадку тестування UI зводиться до пошуку елементу в розмітці і перевірці його характеристик. За необхідності можемо емулювати дії користувача, щоб автоматизувати сценарії та різноманітні user flow. Для кожної платформи (веб, мобайл, десктоп) існує достатньо інструментів, які дозволяють організувати автоматизоване тестування (Webdriver, Appium, Ranorex тощо). Вибір того чи іншого фреймворку часто залежить від уподобань і досвіду спеціаліста, який відповідає за автоматизацію на проєкті.
Кнопка «Restaurants» у додатку Google Maps — гарний приклад елементу, який легко знайти в горстці та отримати вичерпну інформацію про розмір, колір, розміщення на екрані, статус та інші характеристики. Але бувають UI елементи, які представлені не за допомогою горстки, а іншим способом. Анімація, мапа, об’єкти на мапі, різноманітні діаграми і графіки не доступні в HTML/XML. Автоматизувати перевірку цих елементів досить важко — вибір інструментів невеликий i більшість з них розповсюджується на платній основі.
Усі елементи мапи Google (міста, вулиці, площі, будинки, ріки, мости і т.д.) «намальовані» всередині елементу canvas. Очевидно, що інформації, отриманої з горстки, недостатньо навіть для простого тесту отриманої локації на мапі.
Кнопка Restaurants і мапа в HTML Google Maps
У навігаційній системі намальованих функціональних елементів ще більше, ніж у мапі. Тут є позиція машини, активний маршрут, проміжні точки руху, кінцева зупинка, іконки маневрів, іконки локацій, схеми заторів, відстані і т.д. Щоб перевірити правильність відображення цих елементів необхідно працювати безпосередньо з зображенням (картинкою).
UI типової навігаційної системи
Найпростішим рішенням, що дозволяє перевірити наявність чи відсутність елементу на картинці, є повне або часткове порівняння скріншоту додатку з еталонною картинкою. За допомогою цього методу можна досягти надійних результатів порівняння для тих елементів, які:
- не змінюють свого положення на екрані, тобто відображаються статично;
- не спотворені іншими елементами.
В тестовому методі можна вказати координати фрагменту, яким буде виділено цікавий для нас малюнок, і вже його порівнювати з еталонним зображенням. Очевидно, що з різних причин — артефакти рендеренгу, перекриття елементів, зображення елементів з різних точок спостереження тощо, одні і ті ж елементи на різних скріншотах будуть зображені по-різному, тому 100% збіг картинок малоімовірний.
Порівняння зображень за допомогою pHash
Існує багато інструментів, які дозволяють порівняти картинки з допустимим рівнем спотворень. Наприклад, для Ruby — це Imatcher, RMagick, Vips тощо. На проєкті ми використовували pHash — популярну бібліотеку, доступну для різних платформ. Демо pHash можна переглянути онлайн.
Наприклад, ми хочемо порівняти дві картинки: еталонну і картинку, на якій є шум. Алгоритм обчислює величину «hamming distance» в байтах, що фактично означає різницю між картинками. Також для даної картинки алгоритм робить прогнозний розрахунок порогового значення, на яке можна опиратися при прийнятті рішення — збігаються ці картинки чи ні. Для демо картинки з котиками ми отримали різницю в 12 байт і порогове значення в 26 байт. Таким чином система дає рекомендацію, що картинки ідентичні, бо різниця менша за порогове значення.
Демоверсія сайту з алгоритмом pHash
Ми використовували pHash у тестах позиціонування автомобіля — порівнювали ту частину екрану, яка містить current car position (на картинці нижче закрита чорним квадратом). Різні версії мапи та додатку, затори, інциденти на дорозі, нові заклади і т. д. призводили до появи додаткових спотворень: зміщення позиції напрямку руху, перекриття назви вулиці з іконкою машини тощо.
Ось приклад фрагментів екрану, які порівнюються в тесті. З правої сторони наведена різниця в байтах кожного фрагменту у порівнянні з першим. Бачимо, що різниця першої і другої картинки — 8 байт, першої і третьої — 17 байт, далі — 16, 14 та 6 байт. Тобто для тесту цієї локації, встановлення порогового значення у 20 байт забезпечує високу ймовірність проходження тесту, якщо на картинках правильна локація (помилка
Різниця в байтах між фрагментами рисунків з однаковим положенням автомобіля на вулиці
Але в іншому тесті, де перевіряється функціонал збільшення (Zoom In test), вже зовсім інші цифри: haming distance від 0 до 27. Тобто, якщо встановити порогове значення на рівні 20, то у
Різниця в байтах між фрагментами рисунків з однаковим положенням автомобіля в разі збільшення (Zoom In)
Щоб зменшити ймовірність таких помилок, можна зберегти декілька еталонних зображень і використовувати їх, якщо попереднє порівняння було невдалим. У моїй практиці, для деяких локацій кількість зображень сягала
Нижче наведені картинки з різними локаціями та haming distance при порівнянні їх між собою. Через те, що наша система має сіру тему оформлення (сірі будівлі, сірі вулиці), іноді результат порівняння зовсім різних картинок дорівнює 18 (менше за поріг у 20 байт). Порівнюючи
Різниця в байтах між фрагментами рисунків з різними положеннями автомобіля
Очевидно, що для перевірки правильності локацій даний метод не підходив. З написанням великої кількості тестів ми почали отримувати все більше хибних фейлів і все менше були впевнені в успішному проходженні тестів. Необхідно було знайти інший підхід, і ми звернулися до Computer Vision.
Computer Vision та OpenCV
Computer Vision — це технології та методи для виявлення, відстеження та класифікування об’єктів на зображенні. Однією з найпопулярніших бібліотек, в якій реалізовані алгоритми Computer Vision, є OpenCV. Існує реалізація на Python, С++ та інших мовах. Через зручність встановлення і написання скриптів ми будемо використовувати реалізацію на Python 2. OpenCV має широкі можливості у роботі з зображеннями — пошук об’єктів, сегментація, трекінг і т. д. Це «швейцарський ніж» у комп’ютерному зорі, однак, нас цікавить саме те, що допоможе нам у тестуванні. У 90% випадках тестування зображень нам допоможе метод Template Matching.
Метод Template Matching
Розглянемо роботу методу на прикладі. Нижче наведено картинку, на якій Мессі б’є по м’ячу. Припустимо, нам цікаво знайти місце, де зображено обличчя Мессі. Готуємо заздалегідь шаблон (темплейт) з обличчям — вирізаємо його з тієї ж самої картинки і зберігаємо. Цей метод рухає наш темплейт по кожному пікселю довжини і висоти, утворюючи скануюче віконце, в яке потрапляють фрагменти тестової картинки. Для кожного такого фрагмента обчислюється результат порівняння з темплейтом. Таким чином, на виході методу ми отримуємо монохромне зображення, в якому кожен піксель є результатом порівняння темплейта з фрагментом тестового зображення. Зображення, отримане в результаті, менше, ніж тестове, на висоту і ширину темплейту, оскільки крайніми пікселями порівняння виступатимуть ті точки, де темплейт доходить до границі тестового зображення.
Що нам дає це результуюче зображення? У тому місці (набір пікселів), де матчинг найкращий, картинка буде найсвітліша. Застосувавши фільтр, щоб знайти найсвітлішу точку, ми знайдемо положення найкращого матчингу.
Template Matching в Python реалізований через метод machTemplate модуля cv2, який приймає три параметри — тестове зображення, темплейт і назву алгоритму порівняння. На виході отримуємо набір пікселів, які формують результуюче зображення. Знайти положення та яскравість найсвітлішої та найтемнішої точки на результуючому зображенні можна за допомогою методу minMaxLoc.
Template Matching: шаблон, тестове зображення й підсумкове зображення
Існує три алгоритми матчингу темплейту. Деякі алгоритми результатом найкращого матчингу повертають найсвітлішу точку (TM_CCOEFF, TM_CCORR), деякі — найтемнішу (TM_SQDIFF). Їхня ефективність варіюється для різних категорій зображень, тому щоб отримати найкращий результат, їх треба підбирати. За замовчуванням використовується алгоритм TM_CCOEFF, який дає непогані результати для багатьох типів зображень.
Методи порівняння зображень
Також, для кожного алгоритму існує нормована версія, коли найкращий результат матчингу приводиться до значення від 0 до 1 (0% і 100% матчинг). Це зручно для прийняття рішення щодо якості матчингу. При ненормованому методі в найкращому місці матчингу яскравість пікселя буде довільної величини (скажімо 1428 одиниць). Цієї інформації недостатньо, щоб прийняти рішення. У випадку з нормованим методом ми знаємо, що 100% матчинг має результат, який дорівнює 1, і ми можемо ввести порогове значення (скажімо 0.8) для визначення прийнятного результату. Більш того, нормований метод допомагає при визначенні кількості об’єктів на картинці. Застосувавши фільтр, ми можемо вибрати ті точки, де результат вищий за порогове значення, і порахувати ці точки.
Наприклад, у нас є картинка з гри Супер Маріо і наша задача порахувати кількість монеток у підземеллі. Темплейт — це монетка. Застосовуємо метод, знаходимо найсвітліші точки, фільтруємо точки, де результат більший від порогового значення (0.8) і отримуємо позиції, де розташовані монетки.
Template Matching. Пошук декількох об’єктів
Template Matching — потужний інструмент, який дозволяє перевірити багато кейсів: знайти елемент на екрані, визначити його координати (щоб зробити клік), порахувати елементи на екрані, пересвідчитись, що елемента немає на екрані і т. д. Проте все ж є обмеження його використання. Як і в порівнянні картинок через pHash, Template Matching дуже чутливий до спотворень і перекриттів на зображеннях. Він чудово знайде іконки, кнопки, графічні позначки та інші елементи UI, але буде видавати помилки при роботі з локаціями і мапою, де є багато варіацій перекриттів назв вулиць, трафіку і додаткових об’єктів.
Наприклад, спробуємо перевірити правильність позиціонування адреси в Google Maps через Template Matching. Якщо ми введемо в пошук адресу офісу Intellias — «Intellias Kyrylivska 39», підготуємо з нього темплейт і спробуємо порівняти його із зображенням, на якому інша локація (інший офіс Intellias «Intellias Kyrylivska 15/1») , то ми отримаємо результат, вищий за порогове значення (0.85 при порозі 0.8). Тобто для алгоритму ці дві локації схожі з результатом 85%.
Template Matching у Google Maps
Очевидно, що Template Matching не підходить для перевірки локацій.
Пошук об’єктів на зображеннях зі спотворенням
У Computer Vision існує набір методів, які дозволяють організувати пошук об’єктів на мапі. Але для того, щоб зрозуміти як ними користуватися, необхідно трохи заглибитись в теорію, зокрема, згадати, як ми складаємо пазли.
Уявімо, що наша картинка — це великий пазл. Які частини пазлу складати найважче? Зазвичай, це частини, які створюють фон: небо, хмари, море, земля, стіни будинків і т.д. Щоб скласти таку чистину, потрібно багато шматочків пазлу, які мало відрізняються один від одного. На картинці знизу ці елементи позначені літерами A і В. Трохи легше складати картинку, де є переходи кольору або границі об’єктів. Вони мають прив’язку до горизонталі чи вертикалі (позначені літерами C і D). Тут вже можемо визначити, що С — лінія даху правої будівлі, а D — лівої. Але все ще залишається невизначеність, в якому саме місці мають бути ці частинки. Якщо ж подивитися на елементи E і F, то ми побачимо, що це кутики, які можна встановити тільки в одному місці на картинці. Ці кутики дають найбільше інформації про характеристики об’єкту.
Об’єкти на картинці, які ми описали (площини, границі і кутики), в Computer Vision називаються Features. Пошук цих об’єктів називається Feature Detection, а опис і знаходження їхніх характеристик — Feature Description.
Пошук та опис об’єктів на зображенні
Одна з найважливіших задач, яку треба вирішити при порівнянні об’єктів, — це пошук кутиків на картинках. Алгоритми, які займаються цим, називаються Corner Detectors. Чи не найперший алгоритм був описаний Крісом Харрісом у
Модель Гарріса
В OpenCV існує метод cornerHarris, який дозволяє знаходити кутики на картинці. В параметрах, крім зображення, він приймає коефіцієнти, які впливають на кількість і якість отриманих точок. В документації рекомендують почати з дефолтних значень і змінювати їх при потребі.
Детектор Гарріса в OpenCV
Наступним кроком після знаходження кутиків є обчислення їхніх характеристик. В алгоритмі SIFT (Scale-Invariant Feature Transform), описаному у 2004 році, Девід Лоу уточнив пошук кутиків за рахунок додаткових перевірок на різних масштабах зображення. При збільшенні виявляється, що кутик складається з кількох границь і точки перетину, яку нам і треба визначити якомога точніше. Також він запропонував розбивати фрагмент з кутиком на менші фрагменти (128 фрагментів) і обчислювати вектор збільшення яскравості для кожного з них. Таким чином, для кожної точки з кутиком обчислюється 128 бітове значення (дескриптор), яке використовується у порівнянні.
Обчислення дескрипторів у SIFT
На прикладі показано, як обчислюється дескриптор для кольорової і чорно-білої картинок. У разі кольорової картинки для кожного фрагменту вимірюється кут зміни кольору відповідно до кругової діаграми відтінків. При обчисленні чорно-білого дескриптора, береться до уваги напрямок і величина зміни яскравості фрагменту від темнішого до світлішого.
Обчислення дескрипторів для кольорового й чорно-білого зображень
В OpenCV алгоритм обчислення дескрипторів (а також точок з кутиками) реалізований через метод detectAndCompute об’єкту SIFT. За допомогою методу drawKeypoints можна позначити на картинці знайдені точки.
SIFT в OpenCV
Існує багато способів знайти кутики на картинці і обчислити їхні характеристики, але їх розгляд вимагає більшого заглиблення в теорію. Втім, приклади і алгоритми, які ми вже розглянули, дозволяють нам порівнювати не просто картинки, а об’єкти, зображені на картинках.
Feature Matching
Після того як ми знайшли ключові точки порівняння (кутики) і обчислили їх характеристики (дескриптори), можна переходити до їх порівняння. Існує два основних методи порівняння об’єктів — Cross Check та тест Девіда Лоу. Наприклад, ми маємо один і той самий трикутник, зображений на
У методі Cross Check ми обчислюємо різницю між кожною точкою першого зображення і кожною точкою другого, а потім обчислюємо різницю для кожної точки другого зображення з кожною точкою першого (перехресна перевірка). Після цього ми робимо висновки щодо отриманих результатів. Дві точки вважаються відповідними (позначено зеленою лінією), коли у двох напрямках різниця між ними менша за різницю з іншими точками. Так, для верхньої точки першого трикутника найменша різниця дорівнює 3, але для верхньої точки другого трикутника, найменша різниця дорівнює 2, тож ці точки не відповідні (червона лінія). У цьому випадку серед
Метод Cross Check
Інший метод був запропонований Девідом Лоу, який також є автором SIFT. У ньому ми визначаємо різницю в одному напрямку: для кожної точки першого зображення з кожною точкою другого зображення. Ідея полягає в тому, що якщо два зображення містять один об’єкт, то для кожної точки першого зображення існує тільки одна точка на другому зображенні, різниця з якою буде прагнути до нуля. Різниці з іншими точками будуть суттєво відрізнятися в більшу сторону. Тому щоб матчинг був прийнятий, його результат має бути набагато кращим за всі інші результати матчингів для цієї точки. Можна задати параметр цього порівняння, наприклад, найменша різниця має бути на 75% менша за всі інші різниці. Маємо ті самі 2 трикутники і обчислені різниці для кожної точки. Для найвищої точки першого трикутника результати — 3, 7 і 8. Найкращий результат 3, що становить 42% від 7, і 37% від 8. Це набагато менше за 75%, тому цей матчинг приймається. Для середньої точки маємо результати 5, 4 і 6. Найкращий результат 4, що є 80% від 5 і 66% від 6. Це більше за 75%, тому чей матчинг вибраковується. Бачимо, що доцільно порівнювати тільки 2 найкращих результати, бо якщо хоча б один з результатів буде більший за 75%, матчинг вибраковується. У даному прикладі серед
Тест Девіда Лоу
При прийнятті рішення також можна брати до уваги координати точок, які порівнюються. Якщо ми знаємо, що у фрагментах має бути один і той самий об’єкт і його спотворення не передбачають поворотів, то ми можемо додати перевірку того, що координати точок не мають відрізнятися суттєво.
В OpenCV існує класс BFMatcher (Brute-Force), який використовується для порівняння дескрипторів. Відповідно до того, яким методом були обчислені дескриптори (SIFT чи інші), та який метод буде використано для порівняння (Cross-Check чи тест Девіда Лоу), створюється об’єкт bf класу BFMatсher. Якщо використовується Cross-Check, то метод bf.match приймає два масиви дескрипторів (для першої і другої картинки) і повертає масив з об’єктами типу match. Кожен об’єкт match містить координати, дескриптори і результат порівняння для двох точок які пройшли Cross-Check.
Якщо використовується тест Девіда Лоу, то метод bf.knnMatch приймає два масиви дескрипторів і параметр k — кількість порівнянь для кожної точки, які будуть приймати участь у тесті Девіда Лоу. На прикладі вище ми бачили, що 2 найкращих результати для кожної точки достатньо для порівняння, тому k=2. Метод повертає масив масивів з результатами для кожної точки (результати сортовані від меншого). Далі застосовується тест, де у циклі перевіряється, чи з двох найкращих результатів один менший за другий на 75%. З тих результатів, що пройшли тест, формується масив good. Метод drawMatches дозволяє намалювати лінії між картинками, які порівнюються.
Brute Force matching в OpenCV
Порівнюючи співвідношення точок, які були знайдені, і точок, що пройшли тест, ми можемо визначити, який метод порівняння є кращим для наших задач. При тестуванні локацій на мапі кращі результати показав тест Девіда Лоу, тому ми взяли його за основу для написання скрипту перевірки.
Висновки
Ми розглянули деякі елементи теорії Computer Vision та познайомилися з бібліотекою OpenCV. Це дуже мала частина усіх знань про обробку зображень, але вона дозволяє створити інструменти, які будуть корисними у тестуванні.
У наступній частині ми розберемо на прикладі простого фреймворку, як працюють скрипти для пошуку темплейтів та об’єктів, протестуємо їх на скріншотах екрану Android-смартфону, визначимо особливості такого тестування.
