Что алгоритм мог использоваться, чтобы определить, являются ли изображения “тем же” или подобный, независимо от размера?
Иногда лучше позволить байт-коду говорить. Изучение кода с использованием JAVAP
public static void main(java.lang.String[]);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=3, locals=3, args_size=1
0: new #16 // class java/lang/String
3: dup
4: ldc #18 // String xyz
6: invokespecial #20 // Method java/lang/String."<init>":(Ljava/lang/String;)V
9: astore_1
10: ldc #23 // String abc
12: astore_2
13: new #25 // class java/lang/StringBuilder
16: dup
17: aload_1
18: invokestatic #27 // Method java/lang/String.valueOf:(Ljava/lang/Object;)Ljava/lang/String;
21: invokespecial #31 // Method java/lang/StringBuilder."<init>":(Ljava/lang/String;)V
24: aload_2
25: invokevirtual #32 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/St
ringBuilder;
28: invokevirtual #36 // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
31: astore_1
32: return
LineNumberTable:
line 6: 0
line 7: 10
line 8: 13
line 9: 32
LocalVariableTable:
Start Length Slot Name Signature
0 33 0 args [Ljava/lang/String;
10 23 1 x Ljava/lang/String;
13 20 2 y Ljava/lang/String;
}
Теперь, как видно из кода
At `0: new` Creates a new String Object
At `3:dup` ; make an extra reference to the new instance
At `4:ldc #18` as seen literal "xyz" has been placed in the pool (one string Object)
At `6: invokespecial;` ; now call an instance initialization method with parameter and creates a object in nonpool memory.
At `9: astore_1` Stores the above reference in local variable 1(i.e x)
Итак, к этому времени у нас есть два объекта String
At `10:ldc #23` as seen literal "abc" has been placed in the pool (third string )
At `12: astore_2` Stores the above reference in local variable (i.e y)
, так что к этому времени у нас есть три объекта String
28: invokevirtual #36 // Method java/lang/StringBuilder.toString:
()Ljava/lang/String;;(fourth String Object is Created)
Таким образом, у нас есть четыре объекта String в этом коде.
Поскольку я новичок в программировании и начал изучать его всего несколько месяцев назад, укажите мне, если я где-то ошибся, и какая верная версия этого. Спасибо:)
7 ответов
These algorithms are usually fingerprint-based. Fingerprint is a reasonably small data structure, something like a long hash code. However, the goals of fingerprint function are opposite to the goals of hash function. A good hash function should generate very different codes for very similar (but not equal) objects. The fingerprint function should, on contrary, generate the same fingerprint for similar images.
Just to give you an example, this is a (not particularly good) fingerprint function: resize the picture to 32x32 square, normalize and and quantize the colors, reducing the number of colors to something like 256. Then, you have 1024-byte fingerprint for the image. Just keep a table of fingerprint => [list of image URLs]. When you need to look images similar to a given image, just calculate its fingerprint value and find the corresponding image list. Easy.
What is not easy - to be useful in practice, the fingerprint function needs to be robust against crops, affine transforms, contrast changes, etc. Construction of good fingerprint functions is a separate research topic. Quite often they are hand-tuned and uses a lot of heuristics (i.e. use the knowledge about typical photo contents, about image format / additional data in EXIF, etc.)
Another variation is to use more than one fingerprint function, try to apply each of them and combine the results. Actually, it's similar to finding similar texts. Just instead of "bag of words" the image similarity search uses a "bag of fingerprints" and finds how many elements from one bag are the same as elements from another bag. How to make this search efficient is another topic.
Now, regarding the articles/papers. I couldn't find a good article that would give an overview of different methods. Most of the public articles I know discuss specific improvement to specific methods. I could recommend to check these:
"Content Fingerprinting Using Wavelets". This article is about audio fingerprinting using wavelets, but the same method can be adapted for image fingerprinting.
PERMUTATION GROUPING: ИНТЕЛЛЕКТУАЛЬНЫЙ ДИЗАЙН ХЕШ-ФУНКЦИЙ ДЛЯ ВОССТАНОВЛЕНИЯ АУДИО И ИЗОБРАЖЕНИЯ . Информация о хэшах с учетом местоположения.
Функции объединения для крупномасштабного поиска частичных дубликатов изображений в Интернете . В очень хорошей статье рассказывается о функциях SIFT и комплектации для повышения эффективности. В конце также есть хорошая библиография
Преобразование Хафа - это очень старый алгоритм извлечения признаков, который может показаться вам интересным. Я сомневаюсь, что это то, что использует tinyeye, но это хорошая и простая отправная точка для изучения извлечения признаков.
Есть также слайды к аккуратному докладу некоторых сотрудников из Университета Торонто об их работе на ] astrometry.net . Они разработали алгоритм сопоставления телескопических изображений ночного неба с местоположениями в звездных каталогах, чтобы идентифицировать особенности изображения. Это более конкретная проблема, чем та, которую пытается решить tinyeye, но я ожидаю, что многие основные идеи, о которых они говорят, применимы к более общей проблеме.
It's probably based on improvements of feature extraction algorithms, taking advantage of features which are scale invariant.
Take a look at
or, if you are REALLY interested, you can shell out some 70 bucks (or at least look at the Google preview) for
Based on this, Igor Krivokon's answer seems to be on the mark.
They may well be doing a Fourier Transform to characterize the complexity of the image, as well as a histogram to characterize the chromatic distribution, paired with a region categorization algorithm to assure that similarly complex and colored images don't get wrongly paired. Don't know if that's what they're using, but it seems like that would do the trick.
Как насчет изменения размера изображений до стандартного небольшого размера и проверки значений SSIM или PSNR только для яркости? вот что я бы сделал.
Check out this blog post (not mine) for a very understandable description of a very understandable algorithm which seems to get good results for how simple it is. It basically partitions the respective pictures into a very coarse grid, sorts the grid by red:blue and green:blue ratios, and checks whether the sorts were the same. This naturally works for color images only.
The pros most likely get better results using vastly more advanced algorithms. As mentioned in the comments on that blog, a leading approach seems to be wavelets.