Использование MinHash, чтобы найти сходство между 2 изображениями

Question

Я использую алгоритм MinHash для поиска похожих изображений между изображениями. Я наткнулся на этот пост, How can I recognize slightly modified images?, который указал мне на MinHash алгоритм.

Я использовал реализацию C # из этого поста в блоге, Set Similarity and Min Hash.

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

• Какое значение я должен установить для universe value?
• При передаче байтового массива изображения в HashSet, он содержит только отдельные байтовые значения; таким образом сравнивая значения от 1 до 256.

Что это за universe в MinHash?
И что я могу сделать, чтобы улучшить реализацию C # MinHash?

Поскольку HashSet<byte> содержит значения до 256, значение сходства всегда получается равным 1.

Вот источник, использующий реализацию C # MinHash из Set Similarity and Min Hash:

class Program
{
    static void Main(string[] args)
    {
        var imageSet1 = GetImageByte(@".\Images\01.JPG");
        var imageSet2 = GetImageByte(@".\Images\02.TIF");
        //var app = new MinHash(256);
        var app = new MinHash(Math.Min(imageSet1.Count, imageSet2.Count));
        double imageSimilarity = app.Similarity(imageSet1, imageSet2);
        Console.WriteLine("similarity = {0}", imageSimilarity);
    }

    private static HashSet<byte> GetImageByte(string imagePath)
    {
        using (var fs = new FileStream(imagePath, FileMode.Open, FileAccess.Read))
        using (var br = new BinaryReader(fs))
        {
            //List<int> bytes = br.ReadBytes((int)fs.Length).Cast<int>().ToList();
            var bytes = new List<byte>(br.ReadBytes((int) fs.Length).ToArray());
            return new HashSet<byte>(bytes);
        }
    }
}

Answer 1

Сначала отвечу на ваш второй вопрос:

А что я могу сделать, чтобы улучшить реализацию C # MinHash?

Вы пытаетесь сравнить изображения на уровне byte для файлов, которые по своей природе структурированы очень по-разному (вы используете TIFF в качестве одного изображения и GIF в другом). Даже если визуально эти файлы были точно такими же, ваша реализация никогда не найдет дубликаты, если файлы не одного типа.

Тем не менее, ваша minhash реализация должна зависеть от сопоставимых атрибутов изображений, которые вы хэшируете для создания подписей.

Хотя значения байтов, безусловно, являются атрибутами изображения, их нельзя сравнивать друг с другом, если они находятся в разных форматах.

Для изображений вы можете использовать, например, значения RGB (и, возможно, альфа) для каждого пикселя изображения. Эти значения сравнимы независимо от формата изображения (вы можете использовать CMYK или любое другое цветовое пространство , которое вы хотите).

Однако использование отдельных значений для каждого пикселя даст вам плохие результаты. Жаккардовое сходство используется для сравнения значений из каждого набора (независимо от того, хешируется ли у вас что-либо) и потому, что для наборов не назначен какой-либо порядок, изображения с одинаковым числом пикселей один и тот же цвет, но расположенный в разных местах, приведет к ложному положительному результату.

Возьмем, к примеру, следующие изображения:

Они имеют размер 100 x 100 пикселей и 50 пикселей красного цвета и 50 пикселей зеленого цвета.

Используя сходство Jaccard для сравнения двух, вы получите следующее (обратите внимание, что, поскольку значения одинаковы, набор содержит только один элемент на цвет. Если вы хотите, вы можете использовать сумку Jaccard сравнение для сравнения сумок с несколькими счетами одного и того же предмета, но в этом случае значение окажется одинаковым):

Legend:
    g = green
    r = red

left image = { r, g }
right image = { r, g }

similarity = intersection(left, right) / union(left, right)

similarity = 1 / 1 = 100%

Примечание о представлении right image = { r, g }: поскольку множества неупорядочены, { r, g } - это то же самое, что и { g, r }, поэтому они действительны, то же самое, даже без вычисления сравнения по Джакарду, эта точка делает это очевидным .

Но очевидно, что эти изображения не совпадают.

Именно поэтому shingling обычно используется для нахождения отдельных мини-областей в наборе, которые могут использоваться совместно для уникальной идентификации элемента.

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

left image = { [r, r, r], [r, r, g], [r, g, g], [g, g, g] }
right image = { [g, g, g], [g, g, r], [g, r, r], [r, r, r] } 

И дает вам сходство с Жакаром:

intersection(left, right) = 2
union(right, left) = 6

similarity(left, right) = 2 / 6 = 33.33%

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

Обратите внимание, что черепица может быть любой длины, которую вы выберете. Вам нужно будет решить, из какой черепицы будут получены соответствующие результаты сходства Жакара (и порог), ответить на вопрос «насколько они похожи?»

Теперь, отвечая на ваш первый вопрос:

какова ценность вселенной?

В данном конкретном случае это количество предметов, которые могут существовать во вселенной. Если бы вы использовали одиночные пиксели RGB, юниверс был бы:

255 * 255 * 255 = 16,581,375

При использовании шинглинга ценность намного, намного выше, так как вы имеете дело с комбинациями этих предметов. В идеале вы хотите сгенерировать набор совершенных хеш-функций для вашего набора хеш-функций minhash. Однако из-за ограничений систем типов (или из-за того, что вы не хотите хранить очень большие числа на другом носителе), вам следует сосредоточиться на хэш-функциях, которые минимизируют коллизии.

Если вы знаете количество возможных элементов во вселенной элементов, то это может помочь вам сгенерировать хеш-функции, уменьшающие количество столкновений.

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

Answer 2

Вкратце, Минхаш сам по себе является плохим решением для поиска похожих изображений. При использовании вместе с соответствующим извлечением функции изображения , оно должно работать хорошо. Но это далеко не так просто. Я объясню:

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

Для текстовых документов это легко: обычно используются такие функции, как черепица текста, например "кот сидел", "кот сидел", "сидел на", "на коврике". Они просты в генерировании и могут использоваться совместно с похожими документами.

С изображениями намного сложнее. Вы не можете сравнивать серии байтов, так как JPEG и PNG одного и того же изображения будут иметь совершенно разные шаблоны байтов. Вы также не можете сравнивать серии значений цвета пикселей, так как эти значения цвета будут немного отличаться между изображениями JPEG и PNG. А затем подумайте, что произойдет, если одно изображение будет немного масштабировано, размыто или слегка повернуто, или будет отрегулирован его цветовой баланс: это все виды модификаций, против которых должно быть устойчиво обнаружение сходства, но любое из них приведет к изменениям для всех пикселей, поэтому, если функции основаны просто на серии пикселей, изображения будут считаться совершенно не похожими.

Обнаружение сходства изображений является сложным и основано на использовании функций, которые не изменяются при масштабировании, повороте, кадрировании, размытии или существенных настройках цвета. Есть много методов, и они обычно обнаруживают широкие формы и цветовые отношения в изображении. Это не для новичка, и вы должны быть готовы прочитать некоторые довольно математические статьи в области компьютерного зрения. Как только вы сможете обнаружить такие функции, они могут быть полезны для алгоритма minhash и дают хорошие результаты.

Что это за вселенная в MinHash?

Автор этого блога, по-видимому, намеревается universeSize быть числом различных функций, которые могут когда-либо существовать, но не делают ничего разумного с этим значением. Они просто используют его для уменьшения случайности хеш-функций, что всегда является плохой идеей. Вселенную следует рассматривать как бесконечную для всех практических целей, и нет никакой причины использовать такую ​​переменную в реализации с минимальным хешем. Я вижу много проблем в этом коде.