В этом задании вы будете создавать приложение с возможностями 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, он подскажет в каком порядке лучше выполнять работу.