UDK 004.5

ANALYSIS OF METHODS FOR GRAPHIC IMAGES COMPARISON

L. I Tymchenko, S.O. Romaniuk, M. P. Piddubetska

Vinnytsia National Technical University

This article provides an overview of modern methods and means for graphic images comparison. We consider the comparison of two images can be calculating by mean squared error, entropy, correlation coefficient, and the method of expert assessments to determine the similarity of two images.

Key words: mean squared error, entropy, correlation coefficient, SEME, PSNR, the method of expert assessments.

Introduction

Tasks of comparing digital images are complex and include several stages: preliminary processing of input data, segmentation data, direct description, comparison and classification of images.

Analysis and characterization methods for image comparison

Digital images may be exposed by various distortions during processing, design, storage, transmission and reproduction, which may lead to changes in image quality. In the mass of the final image viewing quality is measured by the human eye by some subjective judgments. In practice, for comparing two images, a subjective evaluation is usually too time-consuming and resource-intensive.

Analysis of images similarity is very important for applications that perform image compression operation. In evaluating and comparison of two images the best results gives algorithm that are as close to human perception of the visual system. Algorithms that use image recognition techniques similar to human perception of optic nerve called metrics Human Visual System (HVS) [1].

The most common methods for comparing two images include the mean square error (Mean Squared Error, MSE, NMSE) and peak signal / noise ratio (Peak signal-to-noise ratio, PSNR).

Most of the methods and algorithms to calculate the similarity of images is quite simple and can be presented in the form of mathematical equations and variables. These include MSE, PSNR, mean absolute error (MAE), mean-square error (RMS). Others try to use metrics human visual system (HVS), such as universal quality index (UQI) and SSIM [1].

Here are the formulas for determining NMSE and PSNR. Larger values when calculating PSNR show a greater similarity of images, while higher values indicate lower MSE image similarity [2].

,

where - the number of pixels that make up the object; ( ),

( ) - color intensity of red, green and blue components of the color and the second pixel image under reference and comparable object.

PSNR is calculated as follows:

_where – is the maximum value that takes 8 bits pixel image_{, = 255.}

In computer graphics images are used for testing such estimates: if the value not more than 0,0001, image is visually indistinguishable from each other; if ranges , then the two images are minor differences; if ranges , the image are visible differences; if greater than , then the two images differ significantly from each other [2].

Figure 1 shows the original image, which has been distorted and changed in five different ways. For each case was calculated value MSE and PSNR, and values SSIM and SEME. In each case, MSE and PSNR almost equivalent, although all five images has different quality. Methods SEME and SSIM, excluding distortions contrast, change their values according to the type of distortion. Therefore, methods that use metrics HVS, accurately compare each of the five distortion of the original image, and methods MSE and PSNR issued almost the same result for all the compared images. This experiment suggests benefits of methods based on human visual perception images.

Figure 1 – Comparison five images with the original using different similarity metrics

_{SSIM –} this method is an alternative to PSNR, which compares the similarity of two images with very high accuracy _[3].

Two images are divided into some equal number of frames. Considered i-th frame size.

K×L the first image and the brightness value component , k=1÷K и l=1÷L. Elected window W and scales for each j-point of the window, j=1÷J, J – the number of pixels in the window. Weights normalized per unit: .In practice usually choose a square box with weights distributed symmetrically with respect to a center of Gaussians. For each point of the center of the frame window placed at this point. Calculated average brightness value components and encoded output window ( and ), average brightness dispersion of components and encoded output window ( и ), average covariance between components and brightness of the original encoded windows

( by the following formulas [3]:

where - brightness value components of j-point of the window, whose center is located at coordinates (k,l) of i-frame.

Further, the value calculated metrics SSIM at the point:

where і . – maximum possible value of y-components. For example, if a default value of y-components is 8 bit, then the maximum value is: .

By default coefficients і . averaged by i-frame separately:

Mean entropy measure (SEME) – a method that calculates the value of the minimum and maximum brightness of images to be compared. If the value of the minimum and maximum brightness of the two images match – two images with a high similarity degree [4].

SEME determined by the formula:

where k1, k2 - the number of horizontal and vertical blocks in the image (this value depends on image size), Imax i, j, Imin i.j – maximum and minimum of each block respectively [4].

Table 1 shows how well each of the methods of image comparison calculates various metrics of similarity of images: CC – the coefficient of correlation, OR –similarity ratio, RMS – root mean square error, MAE – mean absolute error.

Table 1 - Calculation of similarity metrics

Model	Metrics similarity
	СС	OR	RMS	MAE
PSNR	0.852	0.217	8.36	6.75
MSSIM	0.923	0.166	5.96	4.52
MSE	0.858	0.200	8.22	6.35
SEME	0.855	0.154	8.28	6.08

Table 1 shows that most accurately calculates the similarity metric method SEME, but the best method shows accuracy SSIM [4, 5].

Another widely used method of image comparison is calculating the correlation coefficient of the two images. Normalized cross-correlation coefficient R is used in photometry as one of the basic measures of similarity of images. The correlation is calculated as follows [6]:

where r – normalized cross-correlation coefficient, , - the standard deviation of the gray values in the template and comparable area of the image; - covariance gray values in an image area; , - gray values for comparable pattern and image areas; , - the average of the mean values; R, C – the number of rows and columns in images.

The value of the normalized correlation coefficient ranges 1<=R<=1. A value of 1 is achieved only when the image area , associated linear coupling. Values close to 0 indicate a difference, and the value - 1 is obtained when the negative and positive images match, the two graphic image that is almost identical [6].

Because of this method creates a template that pixel-by-pixel moves on both the compared images and the correlation coefficient calculated in each position. The position where the correlation coefficient reaches its highest value position is the best match two images.

To compare of two graphic images often used the method of expert evaluations. This method of comparison is indispensable when some of the existing properties and relationships do not allow a quantitative description where it is impossible or at a particular time to receive numeric data on these properties. Therefore, in these cases, with the help of experts to get the necessary information qualitative nature, based on experience and intuition of experts. These qualitative assessments referred to expert estimates [6].

When using experts to analyze the subject area introduces the concept of factor, which defines the properties, characteristics and attributes of objects and the relationships between them. Conventionally factors can be divided into discrete and continuous current. The most common practice in expert evaluations are personal techniques and methods of group assessment. By statement belongs ranking and regulation, as well as the method of paired comparisons.

Results of the survey of experts with respect to n m factors are reduced to a matrix of dimension m×n, called matrix poll. – the rank of j-factor given by i-expert. When processing matrices poll transferred to rank transformed by the formula:

After this by the relative weight of each factor is determined on all experts:

In analyzing the estimates obtained from experts often, need to identify concordance - consistency of their opinions on several factors. For this purpose, the coefficient of concordance, which is a numerical criterion of consistency of expert opinion in a particular group. The coefficient of concordance is given by:

where S – sum of the squares difference of ranks (deviation from the mean), which is given by:

- maximum value of S, which occurs when all the experts give the same assessment.

It can be shown that the total deviation from their mean values for total (all experts) ranks with the best consistency factors will be determined by the value:

The value of the coefficient of concordance ranges from 0 to 1, and its equity unit means that all the experts gave similar estimates and vanishing means that the connection between the estimates obtained from various experts, does not exist. The coefficient of concordance conveniently calculate the formula proposed by Kendal:

In case: talk about weak coordination experts, and large quantities indicate strong coherence experts. Weak consistency is usually the result of the following reasons: a group of experts really is no consistency of thought; intra-group coalition are high consistency of opinions, but the general opinion opposing coalitions.

Conclusions

This article provides an analysis of current methods and means of comparison images. It is possible to determine their strengths and weaknesses, and to assess the basic characteristics. Developed comparative description of the main methods specified time of the most common algorithms. The method of expert evaluations to compare images.

List of references:

1. Erosh I. L., Soloviev N. V. Digital image processing and recognition / I. L. Erosh, N. V. Soloviev. GOU VPO Saint Petersburg State University of Aerospace Instrumentation. – 2006. – P. 20–24.

2. Romaniuk O. N. Highly methods and tools for visualization of the final three-dimensional images in computer graphics systems / O. N. Romaniuk // Thesis for the Degree of Doctor of Science, NTB. – 2008.

3. Comparison of images. [Electron resource]. - Mode of access: http://masters.donntu.edu.ua

4. Medennikov P. A, Pavlov N. I. Adaptive algorithm and system of feature recognition / P. A. Medennikov, N. I. Pavlov // Opt. – 2000. – №1. S. 46–51.

5. Kovalenko S. V., Kovalenko S. N., Biryukova N. V. Analysis of methods to search for the gangway image among large collections of image files / S. V. Kovalenko, S. N. Kovalenko, N. V. Biryukova // Kharkiv. – 2002. – S. 34-36.

6. Pytev Y. P., Chulikov A. I. Morphological analysis of the images / Y. P. Pytev, A. I. Chulikov // M .: Fizmalit. – 2010. – S. 336.