Image Clustering Module

Модуль для кластеризации изображений по визуальному сходству с использованием perceptual hashing и LSH.

---

Быстрый старт

Требования

1. Java 17+
2. Docker-compose

Настройка и запуск в терминале (Linux / macOS / WSL)

Если вы используете Windows без WSL, используйте PowerShell и команды copy вместо mv, .\mvnw вместо ./mvnw

1. Клонируйте репозиторий:

git clone https://github.com/tennyros/image-clustering-module.git
cd image-clustering-module

2. Подготовьте файлы репозитория:

# Переименуйте и при необходимости отредактируйте env.sample файл
mv .env.sample .env

3. Запустите PostgreSQL через docker compose:

# Убедитесь, что порты на Вашей системе, указанные в docker-compose, не заняты и запустите
docker-compose up -d

4. Запустите приложение:

./mvnw spring-boot:run -Dspring-boot.run.profiles=dev

---

Описание алгоритма кластеризации изображений

Общий принцип

Модуль кластеризует изображения на основе их perceptual hash (pHash), используя метод Locality Sensitive Hashing (LSH) для быстрого поиска похожих изображений. Алгоритм группирует похожие изображения в кластеры, чтобы упростить дальнейшую обработку и анализ.

---

Основные используемые библиотеки

Библиотека	Назначение
JImageHash	Вычисление перцептивного pHash (устойчив к масштабированию, яркости, цвету)
Spring Boot	Основной фреймворк приложения
PostgreSQL	Хранение изображений и кластеров
Liquibase	Управление схемой базы данных
JUnit / Mockito	Покрытие логики unit-тестами

JImageHash:

• Поддерживает pHash, dHash, aHash.
• Хорошо документирован.
• Не требует внешних зависимостей типа OpenCV.
• Устойчив к изменению размера, обрезке, цвету, свету.

---

Основные компоненты

Компонент	Назначение
ImageClusterer	Основной сервис кластеризации
ClusteringContext	Контекст кластеризации, содержит индекс и внутренние отображения
LSHIndex	Индекс, хранящий полосы pHash и обеспечивающий быстрый поиск кандидатов
ImageHashService	Вычисляет pHash и расстояние Хэмминга
ClusterInitializer	Загружает и индексирует существующие изображения и кластеры
ClusterMatcher	Ищет подходящий кластер среди кандидатов
ClusterAssigner	Присваивает изображение кластеру или создаёт новый

---

Процесс кластеризации

1. Инициализация контекста

   Создаётся ClusteringContext с пустым LSH-индексом, настроенным по параметрам (число полос и размер полосы).

2. Загрузка данных

   Из базы загружаются все изображения с непустым pHash и все существующие кластеры с их изображениями.

3. Инициализация индекса

   ClusterInitializer добавляет все изображения из существующих кластеров в ClusteringContext: индексирует их в LSH и обновляет внутренние маппинги.

4. Кластеризация новых изображений

   Для каждого нового изображения:

   • Проверяется, не кластеризовано ли оно уже.
   • Через ClusterMatcher ищутся похожие изображения в LSH-индексе.
   • Если найден подходящий кластер (расстояние Хэмминга ниже порога), изображение добавляется туда.
   • Иначе создаётся новый кластер.
   • Изображение добавляется в индекс и внутренние структуры контекста.

5. Сохранение результатов

   Создаются и сохраняются связи (ImageClusterLink) между изображениями и кластерами.

---

Технические детали

• Locality Sensitive Hashing (LSH): разбивает pHash каждого изображения на несколько полос (numBands) фиксированной длины (bandSize). Позволяет быстро находить кандидатов для сравнения.
• Расстояние Хэмминга: используется для точного измерения схожести pHash.
• Порог кластеризации: задаётся в конфигурации (hammingThreshold).
• ClusteringContext: управляет состоянием в процессе кластеризации — обеспечивает быстрый доступ к уже кластеризованным изображениям и поддерживает индекс.

---

Сложность алгоритма

Пусть N — количество изображений, K — количество полос LSH, B — размер полосы (в битах):

• Создание индекса: O(N * K)
• Поиск кандидатов: O(K) — доступ к K множествам (по одной на каждую полосу)
• Сравнение с кандидатами: O(C) — где C ≪ N (обычно 5–20 кандидатов)
• Общая сложность кластеризации всех изображений: O(N * C) — почти линейная

Без LSH (наивный перебор): O(N^2)

---