Libpuzzle Индексирование миллионов изображений?

Ответ 1

Итак, давайте взглянем на пример, который они дают, и попытаемся расширить.

Предположим, у вас есть таблица, в которой хранится информация, относящаяся к каждому изображению (путь, имя, описание и т.д.). В этой таблице вы укажете поле для сжатой подписи, которое будет подсчитано и сохранено при первоначальном заполнении базы данных. Таким образом, определим эту таблицу:

CREATE TABLE images (
    image_id INTEGER NOT NULL PRIMARY KEY,
    name TEXT,
    description TEXT,
    file_path TEXT NOT NULL,
    url_path TEXT NOT NULL,
    signature TEXT NOT NULL
);

Когда вы изначально вычисляете подпись, вы также собираетесь вычислить несколько слов из подписи:

// this will be run once for each image:
$cvec = puzzle_fill_cvec_from_file('img1.jpg');
$words = array();
$wordlen = 10; // this is $k from the example
$wordcnt = 100; // this is $n from the example
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) {
    $words[] = substr($cvec, $i, $wordlen);
}

Теперь вы можете поместить эти слова в таблицу, определяемую следующим образом:

CREATE TABLE img_sig_words (
    image_id INTEGER NOT NULL,
    sig_word TEXT NOT NULL,
    FOREIGN KEY (image_id) REFERENCES images (image_id),
    INDEX (image_id, sig_word)
);

Теперь вы вставляете в эту таблицу, добавляя индекс позиции, где было найдено слово, чтобы вы знали, когда слово соответствует тому, что оно совпало в том же месте в сигнатуре:

// the signature, along with all other data, has already been inserted into the images
// table, and $image_id has been populated with the resulting primary key
foreach ($words as $index => $word) {
    $sig_word = $index.'__'.$word;
    $dbobj->query("INSERT INTO img_sig_words (image_id, sig_word) VALUES ($image_id,
        '$sig_word')"); // figure a suitably defined db abstraction layer...
}

Таким образом, ваши инициализированные данные, вы можете легко сопоставить изображения с соответствующими словами:

// $image_id is set to the base image that you are trying to find matches to
$dbobj->query("SELECT i.*, COUNT(isw.sig_word) as strength FROM images i JOIN img_sig_words
    isw ON i.image_id = isw.image_id JOIN img_sig_words isw_search ON isw.sig_word =
    isw_search.sig_word AND isw.image_id != isw_search.image_id WHERE
    isw_search.image_id = $image_id GROUP BY i.image_id, i.name, i.description,
    i.file_path, i.url_path, i.signature ORDER BY strength DESC");

Вы можете улучшить запрос, добавив предложение HAVING, для которого требуется минимум strength, что приведет к дальнейшему уменьшению вашего соответствия.

Я не гарантирую, что это самая эффективная настройка, но она должна быть примерно функциональной, чтобы выполнить то, что вы ищете.

В принципе, разделение и сохранение слов таким образом позволяет выполнить грубую дистанционную проверку без необходимости запуска специализированной функции для подписей.

Ответ 2

Я экспериментировал с libpuzzle раньше - дошел до вас. На самом деле не началась правильная реализация. Было также непонятно, как именно это сделать. (и отказался от проекта из-за нехватки времени), так что на самом деле он не сохранился)

В любом случае, глядя сейчас, попробуем предложить свое понимание - возможно, между нами мы сможем это сделать:)

Запросы используют двухэтапный процесс -

• сначала вы используете таблицу слов.
  • возьмите "ссылочный" образ и выработайте его подпись.
  • выработать его составные слова,
  • обратитесь к таблице слов, чтобы найти все соответствия . Это может использовать индексы баз данных для эффективных запросов.
  • скомпилировать список всех sig_ids. (получится несколько дубликатов в 3.)
• Затем проконсультируйтесь с таблицей подписи
  • восстановить и распаковать все возможные из сигнатур (поскольку у вас есть предварительно фильтрованный список, число должно быть относительно небольшим)
  • используйте puzzle_vector_normalized_distance для определения фактического расстояния.
  • сортировать и ранжировать результаты по мере необходимости

(т.е. вы используете только сжатие в таблице подписей, слова остаются несжатыми, поэтому могут запускать быстрые запросы на нем)

Таблица слов - это форма инвертированного индекса. На самом деле я имею в виду использовать fooobar.com/questions/tagged/... вместо таблицы базы данных слов, потому что это специально разработано как очень быстрый инвертированный индекс.

... в теории в любом случае...

Ответ 3

Я также работаю над libpuzzle в php и имею некоторые сомнения относительно того, как генерировать слова из сигнатур изображения. Ответ Jasons выше кажется правильным, но у меня есть проблема с этой частью:

// this will be run once for each image:
$cvec = puzzle_fill_cvec_from_file('img1.jpg');
$words = array();
$wordlen = 10; // this is $k from the example
$wordcnt = 100; // this is $n from the example
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) {
    $words[] = substr($cvec, $i, $wordlen);
}

Ответ 4

Я создал проект DEMO на libpuzzle на GitHub: https://github.com/alsotang/libpuzzle_demo.

В проекте используется способ, предложенный Джейсоном выше.

Схема базы данных показывает: https://github.com/alsotang/libpuzzle_demo/blob/master/schema.sql

И я расскажу больше о сигнатуре libpuzzle.

Теперь у нас есть два изображения, и я могу рассчитать их подпись.

Нечетные строки для изображения 1 (левый), а четные - для изображения 2.

Вы можете обнаружить, что в большинстве случаев число в той же позиции одинаково.

....

Мой английский настолько беден, поэтому я не могу выразить свой ум дальше... Я думаю, что любой, кто хочет индексировать миллионы изображений, должен проверить мой репозиторий GitHub на libpuzzle DEMO..