У цьому завданні ви будете створювати додаток до можливостей Computer Vision. Вам належить створити веб сервіс для пошуку схожих зображень.
Для розпізнавання зображень ми будемо використовувати хешування. Популярними алгоритмами для даного завдання є * aHash *, * pHash * і * dHash *. Ми будемо використовувати dHash, даний алгоритм заснований на підрахунку напрямки градієнта зображення. Хешування здійснюється в 3 етапи: 0) Ініціалізувати значення хешу 0
- Знебарвити зображення, перетворивши його в півтони (grayscale)
- зменшити зображення до певного розміру (9x8, 8x9, 9x9)
- Підрахунок хешу. Для його підрахунку можна використовувати 3 варіанти: вертикальний, горизонтальний і діагональний. Ми розглянемо діагональний алгоритм - для цього нам знадобиться зображення 9х9. Починаючи з позиції (1,1) ми обходимо зображення і виставляємо поточний біт хешу в одиницю, якщо значення яскравості поточного пікселя більше, ніж значення яскравості в пікселі по діагоналі зверху-ліворуч. При цьому на кожній ітерації ми зрушуємо значення хешу на 1 вліво. Більш детально про алгоритм можно почитати тут
Словесний опис алгоритму звучить досить складно, однак псевдокод показує, що алгоритм дуже простий:
long dHash(Image image){
long hash = 0;
Image colorless = grayScale(image);
Image scaled = resizeImage(image, 9, 9); //resize(Image target, int width, int height)
int colorArray = scaled.toColorArray();
for(int i = 1; i < 9; i++){
for(int j = 1; j < 9; j++){
if(colorArray[i][j] > colorArray[i - 1][j - 1]){
hash |= 1;
}
hash = hash << 1;
}
}
return hash;
}
Після того, як ми обрахували 2 хешу, ми можемо порівняти їх. Для цього використовується відстань Хеммінга - кількість біт, які розрізняються між двома хешамі. Для його підрахунку необхідно використовувати побітовое виключаюче або (XOR) і порахувати кількість одиниць в отриманому числі і поділити їх на 64. Це дозволить дізнатися наскільки два хешу відрізняються один від одного. Для того, щоб дізнатися наскільки вони схожі необхідно від 1 відняти отримане число
double diffPercent = count_set_bits(hash1 ^ hash2) / 64;
double matchPercent = 1 - diffPercent
Сервіс повинен підтримувати 4 операції:
- завантажити кілька зображень в базу для розпізнавання
- Завантажити 1 зображення для пошуку. Якщо схожих зображень знайдено не було, то додати його в базу
- видалити зображення з бази по id
- видалити всі зображення з бази
Завантажені зображення зберігаються на жорсткому диску. Підрахований хеш з id і шляхом до зображення зберігається в "пресистентне сховище". Це може бути як просто колекція в пам'яті, так і база даних (в цьому випадку використовуй PostgreSQL). Операції з файлової системою слід винести в сервіс, який буде надавати асинхронний API.
При обробці батч запиту запис на жорсткий диск і підрахунок хешу повинні відбуватися паралельно, після того як обидві операції закінчаться необхідно створити запис з інформацією про зображення в персистентному сховищі. Після збереження всіх зображень в масиві необхідно повернути відповідь клієнту:
Зображення 1 -----> обрахунок хешу --------------> запис до персистентного сховища--\
/ \ / \
/ --- запис на жорсткий диск ---/ \
/ \
- Отримання масиву зображень -- -----> відправка відповіді клієнту
\ /
\ /
\ /
Зображення 2 -----> обрахунок хешу --------------> запис до персистентного сховища--/
\ /
--- запис на жорсткий диск ---/
У разі пошуку зображення, якщо не було знайдено жодного збігу, необхідно також як і при батч завантаженні записати файл на диск і створити запис в персистентному сховищі, проте відповідь відправляється не чекаючи закінчення даних операцій:
Зображення --> обрахунок хешу ----> пошук збігів в персистентному сховищі ------> відправка відповіді клієнту ---------------------------------------------->
\
\
\---запис на жорсткий диск --------> запис до персистентного сховища ------------>
Видалення сутностей реалізуйте на ваш розсуд.
Застосунок має впроваджувати 4 ендпоінти:
POST /image/batch
content-type: multipart/form-data
images: MultipartFile[]
Завантажує кілька файлів, обраховує хеш, зберігає зображення на диску і створює запис в персистентному сховище.
POST /image/search?threshold=?
content-type: multipart/form-data
image: MultipartFile
Response: [
{
id: "92c73b0f-77d6-41b9-be87-1e0ebf20be31",
image: "http://127.0.0.1:8080/files/92c73b0f-77d6-41b9-be87-1e0ebf20be31.jpg",
match: 96.1265
}
]
Завантажує файл, пошук якого необхідно виконати в персистентному сховище з вказаними мінімальним відсотком збігу (threshold). Threshold повинен знаходиться в межах (0, 1], при його відсутності в якості значення за замовчуванням використовувати 0.9. Якщо схожі зображення не знайдені, то необхідно зберегти його на диск і додати запис до персистентного сховища.
DELETE /image/{id}
Видаляє вказане зображення з персистентного сховища і з жорсткого диска
DELETE /image/purge
Видаляє всі зображення з жорсткого диска і з персистентного сховища
Також додаток має впроваджувати доступ до збереженних зображень за посиланням.
- З багатьма елементами домашки ви вже знайомі за попередніми домашку. Для спрощення завдання ми підготували репозиторій з боійлерплейтом.
- Почни роботу з реалізації хешу. Можеш обрати будь-який варіант (горизонтальний, вертикальний, діагональний). Якщо застряг, то ми підготували приклад реалізації алгоритму в цьому гісті (ніякі залежності підключати не треба)
- Пошук збігів в базі даних буде досить складно реалізувати, але за це ми додамо додаткові бали. Якщо хочеш спробувати його реалізувати, то тобі доведеться писати нативний запит до бази даних. Швидкодію такого запиту ми оцінювати не будемо, важливий сам факт його наявності;)
- Не забудь обмежити конкаренсі в сервісах, які виконують паралельні обчислення. Для цього можеш створити свій ExecutorService або використовувати будь-які інші засоби.
- Використовуй сучасні можливості Java - CompletableFuture і паралельні стрім. Уникай створення нативних потоків вручну. Також не варто забувати про можливість використовувати
@Asyncанотацію. - Чи буде плюсом, якщо ви налаштуєте обмеження наразмер тіла multipart/form-data. Тільки не виставляйте занадто мале значення.
- Логування всі вхідних запитів буде плюсом :)
- Для тестування завантаження файлів на сервер вам швидше за все знадобиться сторонній HTTP клієнт. Ми рекомендуємо Postman або Insomnia, але ви можете використовувати будь-який зручний вам клієнт.
- Прочитайте додатковий гайд в
ConcurrencyApplication, він підкаже в якому порядку краще виконувати роботу.