Сначала ответьте на второй вопрос:
И что я могу сделать, чтобы улучшить реализацию C # MinHash?
Вы пытаетесь сравнить изображения на уровне byte для файлов, которые по своей сути структурированы по-разному (вы используете TIFF в качестве одного изображения и GIF в другом). Даже если бы визуально эти файлы были совершенно одинаковыми, ваша реализация никогда не обнаружила бы дубликатов, если бы файлы не были одного типа.
При этом ваша реализация minhash должна зависеть от сопоставимых атрибутов изображений. который вы хешируете для создания подписей.
Хотя значения байтов определенно являются атрибутами изображения, их нельзя сравнивать друг с другом, если они находятся в разных форматах.
Для изображений вы можете использовать, например, значения RGB (и, возможно, альфа) для каждого пикселя изображения. Эти значения сопоставимы независимо от формата изображения (вы можете использовать CMYK или любое другое цветовое пространство хочешь).
Однако использование индивидуальных значений для каждого пикселя даст плохие результаты. Сходство по Жаккарту используется для сравнения значений из каждого набора (независимо от того, хешируете ли вы что-нибудь ), и поскольку наборы не имеют никакого назначенного им порядка, изображения, которые имеют одинаковое количество пикселей одного цвета, но расположены в разных пространствах, приведут к ложному срабатыванию.
Возьмем, к примеру, следующие изображения:
Оба они имеют размер 100 x 100 пикселей, 50 пикселей красного и 50 пикселей зеленого цвета.
Используя подобие Жаккара для сравнения этих двух, вы получите следующее (обратите внимание, что, поскольку значения одинаковы, набор содержит только один элемент для каждого цвета. Если вы хотите, вы можете использовать Сравнение сумок 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 }, поэтому они в действительности одинаковы, даже без вычисления сравнения Жаккара, этот момент делает это очевидным.
Но очевидно, что эти изображения не совпадают.
Вот почему черепица обычно используется для поиска отдельных мини-регионов в наборе, которые могут использоваться вместе, чтобы однозначно идентифицировать элемент.
Для изображений вы можете использовать последовательные значения 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. Однако из-за ограничений систем типов (или из-за того, что вы не хотите хранить очень большие числа на другом носителе), ваше внимание должно быть сосредоточено на хэш-функциях, которые минимизируют коллизии.
Если вы знаете количество возможных элементов во вселенной элементов, это может помочь вам сгенерировать хэш-функции, уменьшающие количество конфликтов.
В реализации , на которую вы ссылаетесь, этот размер юниверса используется для генерации случайного числа, а затем передачи этих чисел для генерации нескольких хеш-функций для минимального хеширования, которые в идеале должны вызывать минимальные коллизии.
person
casperOne
schedule
10.08.2012
