The article describes the research of image analysis methods. The methods of indexing images for the search of duplicate images, as well as methods for finding similar images based on the definition of key points are described. The prototype of the system was created, and testing of the described methods was carried out.
Introduction Graphic images are no less important than text, and sometimes it is impossible to reveal a topic without them. In addition, some types of images themselves are copyright objects and are protected by the copyright law of Ukraine. But this does not prevent you from copying or scanning images and publishing them for your own. In order to find duplicates or borrowing images in documents, it is necessary to determine which graphic elements are considered similar. Obviously, such are full duplicates that can in turn be reduced or stretched. When copying other people's images, a plagiarist can resort to various tricks, but the basic problem as with other forms of borrowing – do not visually similar to the original and keep its informative value. The modifications include changing the brightness, contrast, color gamut (putting the image in grayscale), etc. Among the modifications that affect the information content of the image, but can also be used in some cases is image cropping or gluing of several elements into one.
On the one hand, such images are not borrowings, although they are completely identical, and on the other hand, the value of an image may be precisely in the context of its use, if the author used this illustration in the possible set of solutions. A computer program is not able to assess the content of the image and make a conclusion about the licenses under which this image is licensed, so the final decision has to be made by an expert who checks the work using the program.
The Analysis of Recent Researches and Publications
Among approaches to the processing of graphic information into two main areas:
the definition of key points on the image and the use of locally-sensitive hashing can
be identified. These methods can be combined and generally give good results in the
search for similar images. First, the key points in the image are determined, and then
the image is divided into small fragments. By performing indexing of each fragment
separately, an array of signatures that are responsible for the image as a whole is
received. Using Hamming's measure [
A. O. Biloshchitsky and O. V. Dichtyarenko [
The most popular are three methods for indexing images to find duplicate images: Average Hash; Difference Hash; Hash Perceptual.
To find similar images, the method is used to select key points. A key point, or
point feature of an image, is a point whose placement stands out against the
background of any other point. As features of the point of the image for most modern
algorithms a square box is taken, the size of which is 5 by 5 pixels. The process of
determining these points in the image is achieved using the method of using a detector and
a descriptor. A detector is a method for determining a key point that allocates it to the
background of an image. In turn, the descriptors should ensure the invariance of
finding the correspondence between the key points of image transformation. A descriptor
is a method which allows removing the key points of both images and comparing
them with each other. In the case of modifications to research objects, the detector
helps find the same key points on both objects [
Key points must have a number of features [
So, to find snippets of an image or similar content of the illustrations – it is necessary to experiment with the methods of determining key points, each of which also has its own set of advantages and disadvantages.
The main methods used in the construction of detectors and descriptors are FAST, SIFT, ORB, AKAZE, BRIEF, BRISK .
FAST (Features from Accelerated Segment Test). For a point-candidate P, using
the Brezenham algorithm, a circle of 16 pixels is constructed. The point is an angle if
there are N adjacent pixels on a circle whose intensity is greater than IP + t or the
intensity of all less than IP - t, where IP is the intensity of the point P, it is the limiting
value. Next, it is necessary to compare the intensity of the vertical and horizontal
points on the circle with the intensity at the point P. If for 3 of these points the
condition IPi > (IP + t) or IPi < (IP + t), i = 1, ... , 4, then a full test is conducted for all 16
points [
SIFT (Scale Invariant Feature Transform). A variable-size space is created, which
calculates the functions LoG (Laplacian of Gaussian) with a different smoothing
parameter. A point is considered key if it is a local extremum of the Hawsian difference.
After the set of expected key points are specified (the points with a small contrast at
the boundaries of objects are deleted) and their orientation is determined. For this
purpose, a histogram of gradients is constructed in this area, the direction chosen
corresponding to the maximum component of the histogram is selected. Points are
assigned to all directions that correspond to the values of the components of the
histogram, which are larger than the given threshold. Invariant with respect to landslides,
rotations, changes in scale [
ORB (Oriented FAST and Rotated BRIEF). Uses FAST to find key points. FAST
takes the threshold value of the intensity between the central pixel and the area around
the pixels around it as a parameter. The ORB [
AKAZE (Accelerated KAZE). Searching for key points is based on non-linear
image scaling using the FED (Fast Explicit Diffusion) scheme. As a binary descriptor,
M-LDB (Modified-Local Difference Binary) is used. It is currently considered one of
the best [
BRIEF (Binary Robust Independent Elementary Features). A descriptor that
allows representing the original image in the form of binary strings is constructed for
domains. The smoothed image is divided into sections and for them a unique set of
points nd (x, y) is chosen. Then they compare intensity. As a result, we get a binary
string of dimension ND (128, 256 or 512). The obtained descriptors are compared
using Hamming's metric [
BRISK (Binary Robust Invariant Scalable Keypoints). Gaussian smoothing is
applied to the circular areas of potential key points. To determine the direction of the
key point, the amount of local gradients is used [
The main requirements for a method for finding identical images, more precisely for the results of his work, are the maximum accuracy and minimum errors. The information system must not only find all explicit duplicates (those that have changed only the colors, sizes or format), but also "similar" images, while minimizing the amount of work for the system operator. 3
Analysis of methods for finding identical images
For the choice of methods for analysis and the search for identical images, it is
necessary to explore the methods of indexing images; definition of a measure of
similarity; methods used in the construction of detectors and descriptors. The result of the
research is the basis for the design of an information reverse image search system
[1219]. To conduct research, test modules for the program realization of the prototype of
the information system of reverse pattern search was created based on their own data
sample [
To obtain exactly identical, but not similar images, the method of hashing for the average value was analyzed, and for the determination of similarity dimensions, the Hamming distance was used. The main objective of the study is to determine the threshold function, which allows asserting that the images are complete duplicates.
A picture from the database is chosen and the result is shown in (Fig. 1-2). a) a)
On the right there is the image of the user, and on the left - the image found in the database, the window below shows the Hamming distance in percentage terms. For identical images, Hemming's distance is 100% – the image is found and it is completely identical (Fig. 1a).
Now the task will be complicated, the drawing in black and white with shades of gray is completed, after which, the experiment is repeated (Fig. 1b). The system reported minor changes, but still chose the correct image, showing a deviation of only 2%.
Now the brightness and partially paint are changed (Fig. 2a). Hamming distance has decreased by 10% to 88%, but the system has found and correctly identified the need.
In the case of different images (Fig. 2b), as a result of the program's work, the most similar image was found, but the percentage of similarity has fallen by as much as 32%, indicating that it is impossible to speak of the image as identical.
Consequently, it has been experimentally proved that the threshold function should be set between 68-88%, so the smaller this figure, the more exact similarity is determined, (based on the average colors) of images, rather than full duplicates. 4
Analysis of methods working with control points
In order to find similar content in the image, a comparative analysis of the methods that work with the key points, namely: ORB, BRISK, AKAZE, FAST, respectively, based on the results of the classifier will be conducted. The size of the inbound images was compressed to 128, 256, and 512 pixels on each side. Input images are divided into three groups: 30 images with a lot of details (Tabl. 1); 30 images with a monitor set (Tabl. 2); 30 portrait photographs of people (Tabl. 3).
To submit the results, the following abbreviations are used: PK – а total number of key points found; TPK – the total amount of time spent searching for key points (ms); TD – descriptor time (ms); S – the average time to search for a single key point and calculate its descriptor, which looks like:
S = (TPK + TD) / PK (ms); (1) T – total time spent in the program in seconds (s).
Analysis of the results of the first group. All images in this group have a large number of parts located in different places. Information on evaluating methods for various image extensions is provided in Table 1.
The largest number of key points was found using the BRISK method, this number increases in geometric progression, respectively, the higher the resolution of the image under study, the more time will be needed for its processing.
Method Method
PK 10444 11768 5041 6568 12311 26767 7286 15568 15719 78395 8688 32210
PK 1409 2178 995 1024 1661 4954 1438 2427
The ORB method was not too sensitive to resizing the image within the selected range, its complexity increases in arithmetic progression. The shortest execution time for the AKAZE descriptor. The FAST method takes the least time to search for similar images.
Analysis of the results of the second group. 30 illustrations of a monitor image are taken, each of which will represent images in different windows of different programs. This group for various image extensions will be analyzed (Tabl. 2).
S 0,5214 2,1269 0,4166 0,6524 0,5327 0,9591 0,5218 0,3879 0,5234 0,3415 0,7272 0,2767
S 0,3187 2,7231 0,5206 0,6514 0,3278 1,2276 0,6465 0,3996
T
T
The number of key points in the sum of all images significantly decreased compared to the first group, which affected the program's run time, the descriptor, and the cost, respectively, the less the key points generate any algorithm, the less time it takes to process them. All time costs are proportional to the number of key points. The results of the algorithms practically do not differ from the previous group, this indicates that their work does not depend on the input data.
Analysis of the results of the third group. For the last group, portraits of 30 people were selected (Tabl. 3).
The average number of generating key points is greater than the same average number of points in the second group, and less than the first. If each algorithm is taken separately, their results for each group are proportional. Consequently, the program's running time depends on the method selected and the number of key points it detects.
PK
To develop a reverse search information system project, a threshold function was searched for duplicate searches, using hashing on average and Hemming's measure. On the basis of the experimental path, it can assumed that the threshold function should be chosen between 68-88%, accordingly, the smaller this indicator, the more it will determine exactly the similar (based on average colors) of images, rather than full duplicates. Also similar images based on key points were tested by algorithms for finding similar ones. The main element in this study was the time taken to find the key points and compare them to the similarity of the methods: ORB, BRISK, AKAZE and FAST. The worst was the BRISK algorithm, because the number of points generated by them was considerably larger, which led to a rapid increase in processing time. Experimentally it was discovered that the image size of 256x256 pixels is the most optimal for its processing. 6