10215 FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 35, No 2, June 2022, pp. 283-300 https://doi.org/10.2298/FUEE2202283S © 2022 by University of Niš, Serbia | Creative Commons License: CC BY-NC-ND Original scientific paper OPTIMIZATION OF THE 3P KEYS KERNEL PARAMETERS BY MINIMIZING THE RIPPLE OF THE SPECTRAL CHARACTERISTIC Nataša Savić, Zoran Milivojević, Zoran Veličković Academy of Applied Technical and Preschool Studies, Niš, Serbia Abstract. The ideal interpolation kernel is described by the sinc function, and its spectral characteristic is the box function. Due to the infinite length of the ideal kernel, it is not achievable. Therefore, convolutional interpolation kernels of finite length, which should better approximate the ideal kernel in a specified interval, are formed. The approximation function should have a small numerical complexity, so as to reduce the interpolation execution time. In the scientific literature, great attention is paid to the polynomial kernel of the third order. However, the time and spectral characteristic of the third-order polynomial kernels differs significantly from the shape of the ideal kernel. Therefore, the accuracy of cubic interpolation is lower. By optimizing the kernel parameters, it is possible to better approximate the ideal kernel. This will increase the accuracy of the interpolation. The first part of the paper describes a three-parameter (3P) Keys interpolation kernel, r. After that, the algorithm for optimizing the parameters of the 3P Keys kernel, is shown. First, the kernel is disassembled into components, and then, over each kernel component, Fourier transform is applied. In this way the spectral characteristic of the 3P Keys kernel, H, was determined. Then the spectral characteristic was developed in the Taylor series, HT. With the condition for the elimination of the members of the Taylor series, which greatly affect the ripple of the spectral characteristic, the optimal kernel parameters (αopt, βopt, opt) were determined. The second part of the paper describes an experiment, in which the interpolation accuracy of the 3P Keys kernel, was tested. Parametric cubic convolution (PCC) interpolation, with the 3P kernel, was performed over the images from the Test database. The Test database is created with standard Test images, which are intensively used in Digital Image Processing. By analyzing the interpolation error, which is represented by the Mean Square Error, MSE, the accuracy of the interpolation was determined. The results (αopt, βopt, opt, MSEmin) are presented on tables and graphs. Detailed comparative analysis showed higher interpolation accuracy with the proposed 3P Keys interpolation kernel, compared to the interpolation accuracy with, 1P Keys and 2P Keys interpolation kernels. Finally, the numerical values of the optimal kernel parameters, which are determined by the optimization algorithm proposed in this paper, were experimentally verified. Key words: convolution, interpolation, interpolation kernel, PCC interpolation, Keys kernel Received November 23, 2021; received in revised form April 5, 2022 Corresponding author: Nataša Savić Academy of Applied Technical and Preschool Studies, Generala Milojka Lešjanina 39, 18000 Niš, Serbia E-mail: natasa.savic@akademijanis.edu.rs 284 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ 1. INTRODUCTION Interpolation is the process of estimating intermediate values between discrete samples of a continuous signal. Among other things, interpolation can be realized by applying a convolution between a discrete signal and a continuous interpolation kernel. The interpolation kernel significantly affects the accuracy and time execution of interpolation [1]. For interpolation of band-limited signals, the ideal interpolation kernel is of the form sin(x)/x (in the notation sinc) where -∞ ≤ x ≤ +∞ [1, 2]. The spectral characteristic of the sinc interpolation kernel is a rectangular function, Hsinc. The sinc kernel cannot be practically realized because it has infinite limits. For this reason, there is a need to truncate the sinc interpolation kernel to a finite length. As a consequence of the truncated sinc kernel, its spectral characteristic deviates from the ideal, rectangular, characteristic, which leads to: a) ripple in the passband and stopband, and b) finite slope in the transition band. The idea is to approximate the truncated sinc interpolation kernel with a low-degree polynomial function. In this way, the interpolation kernel has a small numerical complexity, and thus, allows a higher interpolation speed. These features of kernel are especially important when implemented in real-time systems. Signal interpolation using finite length interpolation kernels is realized by applying convolution. A polynomial zeroth-degree kernel allows interpolation by rounding to the nearest-neighbor [3, 4]. Nearest-neighbor interpolation is the most efficient in terms of computational speed, but in doing so, the largest interpolation error is generated. A linear, first-degree interpolation kernel is described in [5]. A quadratic, second-degree interpolation kernel is described in [3, 6]. A cubic, third-degree interpolation kernel, intended for parametric cubic convolution, PCC, is described in [1, 5]. Using numerical examples, it has been shown that cubic convolution is more precise than nearest-neighbor and linear interpolation [7 - 9]. The parameterization of the cubic interpolation kernel, by introducing the kernel parameter α, is shown in [1]. The paper [1] is one of the basic papers in the field of interpolation in digital image processing. Later, in the scientific literature, the parametric interpolation kernel from [1] was named, in honor of the author, the 1P Keys interpolation kernel. By changing the value of the kernel parameter α, the characteristics of the kernel can be changed and, in this way, adjusted to the corresponding signal that is interpolated. The process of changing the kernel parameter for customization is called parameter optimization. In [1], the optimization of the parameter α was performed by minimizing the interpolation error by developing the error function into a Taylor series in f = 0 (Maclaurin series). In this way, it is shown that the optimal value of the parameter αopt = -0.5. The ripple of the spectral characteristic is reduced by eliminating the members of the Taylor series that predominantly influence on the ripple. In [10], the ripple of the spectral characteristic was reduced by eliminating the members of the Taylor series that affect on the concavity of the spectral characteristic. In [11], the reduction of ripple of the spectral characteristic was achieved with α = -0.5. The construction of a two-parameter interpolation kernel is shown in [12, 13]. This kernel is based on the extended parameterization of the 1P Keys kernel [1]. In the scientific literature, this kernel is called the 2P Keys kernel. Optimal values of kernel parameters (αopt = 0.1, βopt = 0.2975) in estimating the fundamental frequency of the speech signal determined in [14]. Further expansion of parameterization, in order to improve the characteristics of the kernel, led to the construction of 3P Keys kernel [15]. The optimal values of kernel parameters in the estimates of the fundamental frequency of the speech signal are αopt = - 1.7, βopt = -4.7, γopt = -3.8. A detailed analysis of the error estimate, presented using MSE, Optimization of the 3P Keys Kernel Parameters ... 285 shows a higher accuracy of estimation using 3P kernels compared to the use of 1P Keys and 2P Keys kernels [15]. In the paper [16] the results of precision of the interpolation of audio signals, which was realized using the 3P Keys kernel [15], are presented. Audio test signals were acquired by recording G tones (G1 - G7) on a Steinway B concert piano. A detailed comparative analysis showed that the interpolation error, when the 3P Keys kernel was used, was compared to the following: a) 1P Keys kernel, 7.374 times smaller, and b) 2P Keys kernels, 2.4166 times smaller. Encouraged by the results of the papers, which unequivocally indicate the fact that increasing the number of interpolation kernel parameters reduces the interpolation error, the authors of this paper performed optimization of 3P Keys kernel parameters, in order to increase similarity with the ideal kernel, sinc. Thus created, optimized kernel, will further reduce interpolation error. In this paper, the process of optimization of parameters of the 3P Keys kernel [15] in the spectral domain, is presented. Optimization of kernel parameters was performed by minimizing the ripple of the spectral characteristic. The first part of the paper describes the algorithm for optimizing kernel parameters. First, by applying the Fourier transform on the 3P kernel, r, the analytical form of the spectral characteristic, H, was determined. After that, the spectral characteristics were approximated using the Taylor series, HT. The ripple reduction was achieved by eliminating the members of the Taylor series, HT, which have a dominant effect on the ripple increase. Then, the degree of similarity of the spectral characteristics of the ideal sinc kernel, Hsinc, and the optimized kernel, Hopt, was determined by comparative analysis. MSE were used as a measure of similarity [11]. Finally, the optimal parameters, (αopt, βopt, opt), were determined based on the minimum of the MSE. The second part of the paper presents the results of an experiment in which the optimal parameters for 1P Keys, 2P Keys and 3P Keys kernels were determined. An algorithm for interpolation Test images, error interpolation estimation, and determination of experimental optimal parameters, is described. For the purposes of the experiment, the Image Test base was formed. Image Test base consists of: a) standard Test images for Digital Signal Processing (Lena, Barbara, Cameraman, Peppers, Boats, Tulips, and Watch), and b) images from the BSDS500 Image base [17]. Test images from the BSDS500 base have numeric labels, so they will be named in the same way later in this paper. By applying the algorithm for each image, the optimal parameters and the corresponding estimate errors were determined. The results are presented in tables and graphs. Finally, a comparative analysis of the experimental results with the results obtained by optimizing the spectral characteristic, was performed. Comparative analysis will determine: a) the accuracy of interpolation using MSE and b) the accuracy of estimating kernel parameters using absolute error. Finally, in the last part of the paper, an analysis of the execution time of all analyzed kernels was performed. Testing of the execution time was performed on a computer DESKTOP - S2AC43P, Processor: Intel (R) Pentium (R), CPU: G3220 3 GHZ, RAM: 8 GB and a Windows 10 operating system. The Matlab R2017b program was applied (to determine the execution time, the tic and toc functions are used). It should be emphasized that the realized experiment, within which the algorithm for PCC interpolation is described, is intended, exclusively, for the comparative analysis of the interpolation accuracy of the 1P Keys, 2P Keys and 3P Keys kernels. It was implemented using the Matlab. Therefore, the time of interpolation execution, in this case, is not of primary importance, because the condition for real-time is not set. The paper is organized as follows: Section 2 describes 3P Keys kernel. Section 3 describes the 3P Keys kernel parameterization algorithm. Experimental results and comparative analysis are presented in Section 4. Section 5 is the Conclusion. 286 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ 2. KEYS PARAMETRIC INTERPOLATION KERNELS In paper [1], for the field of convolutional interpolation fundamental paper, the author defined a parametric interpolation kernel. The kernel was intended to image interpolation. Later, in the scientific literature, the interpolation kernel from [1] was called the 1P Keys kernel. 2.1. 1P Keys kernel The proposed 1P Keys kernel [1] is defined as: 3 2 3 2 ( 2) | | ( 3) | | 1, | | 1, ( ) | | 5 | | 8 | | 4 , 1 | | 2 0, | | 2 x x x r x x x x x x        + − + +   = − + −     , (1) where α is parameter of the 1P Keys kernel. The length of this kernel is L = 4. 2.2. 2P Keys kernel A modification of the 1P Key kernel, with the introduction of the second kernel parameter, with length L = 6, is shown in [13]. The analytical form of the 2P Keys kernel is: ( ) 3 2 3 2 3 2 ( 2) | | ( 3) | | 1, | | 1 | | (5 ) | | (8 3 ) | | (4 2 ), 1 | | 2 | | 8 | | 21 | | 18 , 2 | | 3 0, | | 3 x x x x x x x r x x x x x x                 − + − − + +   − − + − − −   =  − + −     , (2) where α and β are the parameters of the kernel. For β = 0 is obtained 1P Keys kernel. In [12 - 14], it was shown that the precision of the PCC interpolation with the 2P Keys kernel was increased compared to the interpolation of the PCC interpolation with the 1P Keys kernel. 2.3. 3P Keys kernel The results in [12 - 14] show that the precision of the PCC interpolation with 2P Keys kernel, compared to interpolation with 1P Keys kernel, is increased. With the idea of further increasing the interpolation accuracy, the parameterization of the 1P kernel, using three parameters, was performed [15]. The three-parameter kernel is called the 3P Keys kernel. The analytical form of the Keys 3P kernel is: 3 2 3 2 3 2 3 2 ( 2) | | ( 3) | | 1, | | 1 | | ( 5 ) | | (8 3 3 ) | | ( 4 2 2 ), 1 | | 2 ( ) | | ( 8 ) | | (21 5 ) | | ( 18 6 ), 2 | | 3 | | 11 | | 40 | | 48 , 3 | | 4 0, | | 4 x x x x x x x r x x x x x x x x x x                             − + + + − + − − +   + − − − + − + + − + −    = + − + + − + − +    − + −      ,(3) where α, β and  are the parameters of the 3P Keys kernel. As an example, Fig. 1.a shows the time characteristics of the ideal interpolation kernel, rsinc, and the 3P Keys kernel, rαβ, for kernel parameters α = -1.2, β = -0.1 and  = -0.1. Optimization of the 3P Keys Kernel Parameters ... 287 a) b) Fig. 1 Characteristics of the ideal sinc and 3P Keys kernels (α = -1.2, β = -0.1,  = -0.1): a) time characteristics (rsinc, rαβγ) and b) spectral characteristics (Hsinc, Hαβ) 3. OPTIMIZATION OF THE KEYS 3P KERNEL PARAMETERS The spectral characteristic, H, of the 3P Keys kernel (Eq. 3) is different from the spectral characteristic, Hsinc of the ideal interpolation kernel rsinc (Fig. 1.b). The deviation of the spectral characteristic H from Hsinc is described as the ripple of the spectral characteristic. The optimization process minimizes the difference between the spectral characteristics of H and Hsinc. Optimization involves selecting the kernel parameters α, β, and , so as to minimize the Mean Square Error between H and Hsinc. In this way, the optimal parameters of the 3P Keys kernel αopt, βopt and opt are obtained. 3.1. Algorithm for minimizing of the ripple of the spectral characteristic This part of the paper conducts the optimization of Keys 3P kernel parameters by minimizing the ripple of the spectral characteristic. The algorithm for parameters optimization consists of the following steps: Input: r - 3P Keys kernel Output: αopt, βopt and opt - kernel parameters. Step 1: Decomposition 3P Keys kernel r to its components r0, r1, r2 and r3. Step 2: Determining the spectral characteristic H(f) by applying the Fourier transform over the kernel components r0, r1, r2 and r3. Step 3: The expansion of the spectral characteristic H( f ) into Taylor series HT( f ). Step 4: Eliminating coefficients of the members of the spectral characteristic HT( f ) which dominantly affect on the ripple of the spectral characteristic. Determining the optimal kernel parameters αopt, βopt and opt. A more detailed explanation of the algorithm steps (Step 1 - Step 4) is shown below. 3.2. Kernel components (Step 1) The 3P Keys kernel r (Eq. (3)) can be represented as the sum of the kernel components: 288 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ 0 1 2 3 ( ) ( ) ( ) ( ) ( )r x r x r x r x r x  = + + + , (4) where 3 2 0 2 | | 3 | | 1. | | 1 ( ) 0, | | 1 x x x r x x  − +  =   , (5) 3 2 3 2 1 | | | | , | | 1 ( ) | | 5 | | 8 | | 4, 1 | | 2 0, | | 2 x x x r x x x x x x  −   = − + −     , (6) 3 2 2 2 3 2 | | | | , | | 1 | | 3 | | 2, 1 | | 2 ( ) | | 8 | | 21 | | 18, 2 | | 3 0, | | 3 x x x x x x r x x x x x x  − +   − +   =  − + −     , (7) and 3 2 2 2 3 3 2 | | | | , | | 1 | | 3 | | 2, 1 | | 2 ( ) | | 5 | | 6, 2 | | 3 | | 11 | | 40 | | 48, 3 | | 4 0, | | 4 x x x x x x r x x x x x x x x x  −   − + −    = − +    − + −      , (8) are components of the 3P Keys kernel. Fig. 2 shows the components of 3P Keys kernel r0, r1, r2 and r3. Fig. 2 3P Keys kernel components: r0, r1, r2 and r3 3.3. Spectral characteristic of the 3P Keys kernel (Step 2) In order to optimize the parameters α, β, and , of the 3P Keys kernel r in the spectral domain, by using the Fourier transform (FT) the spectral characteristic of the kernel H was obtained: 0 1 2 3 0 1 2 3 ( ) ( ( )) ( ( ) ( ) ( ) ( )) ( ) ( ) ( ) ( ) H f FT r x FT r x r x r x r x H f H f H f H f       = = + + + = + + + (9) where H0, H1, H2 and H3 are spectral components of the 3P Keys kernel: Optimization of the 3P Keys Kernel Parameters ... 289 2 0 ( ) ( ) xfi o H f r x e dx   − − =  , (10) 2 1 1 ( ) ( ) xfi H f r x e dx   − − =  , (11) 2 2 2 ( ) ( ) xfi H f r x e dx   − − =  , (12) and 2 3 3 ( ) ( ) xfi H f r x e dx   − − =  . (13) By substituting Eq. (5) in Eq. (10) is obtained: 0 1 3 2 2 3 2 2 0 1 0 ( ) ( 2 3 1) (2 3 1) xfi xfi H f x x e dx x x e dx  − − − = − − + + − +  , (14) By substituting Eq. (6) in Eq. (11) is obtained: -1 0 3 2 -2 3 2 -2 1 -2 -1 1 2 3 2 -2 3 2 -2 0 1 ( ) ( 5 8 4) ( ) ( ) ( 5 8 4) xfi xfi xfi xfi H f x x x e dx x x e dx x x e dx x x x e dx     = − − − − + − − + − + − + −     , (15) By substituting Eq. (7) in Eq. (12) is obtained: 2 1 3 2 2 2 2 2 3 2 0 1 2 3 2 2 3 2 2 2 2 1 0 1 3 3 2 2 2 ( ) ( 8 21 18) ( 3 2) ( ) ( ) ( 3 2) ( 8 21 18) xfi xfi xfi xfi xfi xfi H f x x x e dx x x e dx x x e dx x x e dx x x e dx x x x e dx       − − − − − − − − − − − = − − − − + + + + + + − + + − + + − + −       , (16) By substituting Eq. (8) in Eq. (13) is obtained: 3 2 3 2 2 2 2 3 4 3 1 0 1 2 2 3 2 2 3 2 2 2 1 0 2 3 2 2 2 2 1 2 4 3 2 3 ( ) ( 11 40 48) ( 5 6) ( 3 2) ( ) ( ) ( 3 2) ( 5 6) ( 11 40 48) xfi xfi xfi xfi xfi xfi xfi H f x x x e dx x x e dx x x e dx x x e dx x x e dx x x e dx x x e dx x x x        − − − − − − − − − − − − − − = − − − − + + + + − − − + − − + − + − + − + − + + − + −        2 xfi e dx −  , (17) After applying Euler's formula and partial integration, the spectral components of the kernel can be written in the following form: 290 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ 2 0 4 4 6 sin ( ) 3 sin(2 ) ( ) 2 f f f H f f     − = , (18) 2 1 4 4 3sin (2 ) 4 sin(2 ) sin(4 ) ( ) 2 f f f f f H f f       − − = , (19) 2 2 2 2 4 4 4 4 3sin ( ) 3sin (2 ) 3sin (3 ) ( ) 2 3 sin(2 ) 3 sin(4 ) sin(6 ) 2 f f f H f f f f f f f f f            − − + = + − − , (20) and 2 2 2 3 4 4 4 4 3(sin ( ) sin (3 ) sin (4 )) ( ) 2 (3sin(2 ) 2 sin(4 ) 3sin(6 ) sin(8 )) 2 f f f H f f f f f f f f           − + = − − + − − . (21) Spectral components H0 (Eq. (18)), H1 (Eq. (19)), H2 (Eq. (20)) and H3 (Eq.(21)), are shown in Fig. 3. Fig. 3 Spectral components H0, H1, H2 and H3. of the 3P Keys kernel 3.4. Optimal kernel parameters (Step 3, Step 4) In order to determine the optimal parameters of the 3P Keys kernel r in the spectral domain, the Taylor expansion HT of spectral characteristic H (Eq. (9)) was determined. (Step 3) By expansion into Taylor series in the neighborhood f = 0 (Maclaurin series), spectral components of the kernel were obtained: Optimization of the 3P Keys Kernel Parameters ... 291 2 4 6 8 0 4 1 8 2 ( ) 1 ( ) ( ) ( ) ( ) ... 15 35 4725 31185 T H f f f f f   = − + − + + , (22) 2 4 6 8 1 8 16 232 4112 ( ) ( ) ( ) ( ) ( ) ... 15 35 1575 155925 T H f f f f f   = − + − + + , (23) 2 4 6 8 2 8 272 4232 205808 ( ) ( ) ( ) ( ) ( ) ... 15 105 1575 155925 T H f f f f f   = − + − + + , (24) and 2 4 6 8 3 16 256 25904 2640832 ( ) ( ) ( ) ( ) ( ) ... 15 35 1575 155925 T H f f f f f   = − + − + + . (25) By substituting Eq. (22)-(25) in Eq. (9) is obtained: 0 1 2 3 2 4 6 8 ( ) ( ) ( ) ( ) ( ) 4 1 1 (1 2 2 4 )( ) (3 48 272 768 )( ) 15 105 8 (1 87 1587 9714 )( ) ( ) 4725 T T T T T H f H f H f H f H f f f f O f                 = + + + = − + + + + + + + − + + + + . (26) (Step 4) The minimization of the spectral characteristic (Eq. (26)) ripple is carried out by eliminating the dominant members of the spectral characteristic: 1 2 2 4 0 3 48 272 768 0 1 87 1587 9714 0          + + + =  + + + =  + + + = . (27) After calculating the system of equations Eq. (27) is obtained: 4945 0.6132 8064 409 0.1522 2688 157 0.0195 8064 opt opt opt    = −  − =  = −  − . (28) By substituting the optimal parameter αopt = -0.5 [11], the optimal interpolation 1P Keys kernel, ropt_1P, was obtained: 3 2 3 2 _1 1.5 | | 2.5 | | 1, | | 1, ( ) 0.5 | | 2.5 | | 4 | | 2, 1 | | 2 0, | | 2 opt P x x x r x x x x x x  − +   = − − +     . (29) The spectral characteristic of the 1P Keys kernel, Hopt_1P, is shown in Fig. 4. By substituting the optimal parameters αopt = -0.5938, βopt = 0.0938 [12] the optimal interpolation 2P Keys kernel, ropt_2P, was obtained: 292 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ 3 2 3 2 _ 2 3 2 1.3124 | | 2.3124 | | 1, | | 1 0.5938 | | 3.0628 | | 5.0318 | | 2.5628, 1 | | 2 ( ) 0.0938 | | 0.7504 | | 1.9698 | | 1.6884, 2 | | 3 0, | | 3 opt P x x x x x x x r x x x x x x  − +   − + − +   =  − + −     . (30) The spectral characteristic of the 2P Keys kernel, Hopt_2P, is shown in Fig. 4. By substituting the optimal parameters αopt = -0.6132, βopt = 0.1522, opt = -0.0195 (Eq. (28)) in Eq. (3), the optimal interpolation 3P Keys kernel, ropt_3P, was obtained: 3 2 3 2 3 2 _ 3 3 2 1.2151 | | 2.2151 | | 1, | | 1 0.6132 | | 3.2377 | | 5.4207 | | 2.7962, 1 | | 2 ( ) 0.1522 | | 1.2371 | | 3.2937 | | 2.8566, 2 | | 3 0.0195 | | 0.2145 | | 0.78 | | 0.936, 3 | | 4 0, | | 4 opt P x x x x x x x r x x x x x x x x x x  − +   − + − +    = − + −    − − − −      . (31) The spectral characteristic of the 3P Keys kernel, is shown in Fig. 4. Moreover, Fig. 4 shows the spectral characteristics of the ideal rsinc kernel (Hsinc). Paper [11] presents the total mean square error, MSET, i.e. the difference between the spectral characteristic H and the ideal box characteristic Hsinc: 1 2 sinc 0 1 ( ) ( ) K T k k k MSE H f H f K − = = − . (32) Fig. 4 Spectral characteristic of the ideal interpolation kernel Hsinc and optimal spectral characteristics H of: a) 1P (αopt = -0.5), b) 2P (αopt = -0.5938, βopt = 0.0938) and c) 3P (αopt = -0.6132, βopt = 0.1522, opt = -0.0195) Keys kernel Optimization of the 3P Keys Kernel Parameters ... 293 4. EXPERIMENTAL RESULTS AND ANALYSIS 4.1. Experiment An experiment, with the aim of determining: a) interpolation accuracy with the 3P Keys kernel, and b) interpolation execution time with the 3P Keys kernel, TE, in relation to interpolations with the 1P and 2P Keys kernels, was realized. Interpolations were performed on Test Images, TI, from the Image base. The Image base is created from some: a) standard Test images used in Digital Image Processing, and b) Test images from the BSDS500 base. Some Test images from the Image base are in color (RGB) and some are in black-white (Y). In this Experiment, interpolations were performed on black-white images. Therefore, color images were transformed into black-white images in accordance with the colorimetric equation Y = 0.3R + 0.59G + 0.11B. The Experiment was performed as follows. First, the experimental optimal values of the kernel parameters for: a) 1P Keys (αopt), b) 2P Keys (αopt, βopt) and c) 3P Keys (αopt, βopt, opt), using the algorithm described below, were determined. After that, a comparative analysis of the error estimation of the optimal parameters of the kernels obtained: a) by optimizing the ripple of the spectral characteristic and b) obtained by experiments. Finally, a comparative analysis of interpolation accuracy between the proposed 3P Keys versus 1P Keys and 2P Keys was performed. For these reasons, the Test image , TI, which, for analysis purposes, is presented as a two-dimensional matrix, with dimensions (L x K), was transformed into a one-dimensional matrix. The transformation was performed by connecting the rows of the Test image matrix one after the other, and, in this way, a one- dimensional matrix, X, with dimensions N = L x K, was obtained (these activities are realized by the Algorithm described in Section 4.3). The interpolation is organized as follows. The interpolation of the intensity of the pixel I, X(I), was performed by convolution between the interpolation kernel and intensity of the pixels X(I- K), X(I - K + 1), ..., X(I + K), where K is the length of the interpolation kernel. The interpolated value of pixel I is ˆIx . On the other hand, intensity of the pixel I is known (X(I)), and, in the Experiment, it is considered to be the True value of the pixel intensity. Further analysis involved defining interpolation error. The interpolation error was defined by MSE (Eq. (32)), which was calculated between True, X(I), and the interpolated intensity, ˆIx , of the pixel I. MSE was used in a comparative analysis of interpolation accuracy, between interpolation results with applied 1P, 2P and 3P Keys kernels. The interpolation results (MSEmin) are presented using graphs and tables. By comparative analysis of MSEmin, the precision of interpolation with the 3P Keys kernel, in relation to the precision of interpolation with the 1P and 2P keys kernels, was determined. In addition, the executions time of the PCC interpolation, TE, was determined. Testing of the of the execution time was performed on a computer DESKTOP - S2AC43P, Processor: Intel (R) Pentium (R), CPU: G3220 3 GHZ, RAM: 8 GB and a Windows 10 operating system. The Matlab R2017b program was applied (to determine the execution time, TE, the tic and toc functions are used). Execution time was measured for: a) complete convolution with kernels (Eq. (1), Eq. (2) and Eq. (3)), where, based on the kernel parameters α, β and , the coefficients of third order polynomials are calculated, and then the value of the polynomials were calculated, b) convolution with the optimized kernel parameters (Eq. (29), Eq. (30) and Eq. (31)), where the coefficients of the polynomial were previously calculated, and, after that, the value of the polynomial is were calculated, and c) convolutional kernel execution time, without interpolation. All interpolation execution times, as the arithmetic mean of the value of the results for 100000 interpolations, were determined. 294 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ 4.2. Image base For the purpose of realizing the Experiment, in which the accuracy of PCC interpolation with image interpolation, is tested, an Image base was created. Image base consists of: a) standard Test images for Digital Signal Processing, and b) images from the BSDS500 Image base [17]. Standard Test images are: Lena (512 x 512, RGB) (fig. 5.a), Barbara (225 x 675, RGB) (fig. 5.b), Cameraman (225 x 675, Y) (fig. 5). c), Peppers (225 x 675, RGB) (fig. 5.d), Boats (225 x 675, RGB) (fig. 5.e), Tulips (512 x 768, RGB) (fig. 5.f) , and Watch (768 x 1024, RGB) (Fig. 5.d). Test images from the BSDS500 base have numeric labels: 3096 (321 x 481, RGB) (fig. 5.h), 14037 (321 x 481, RGB) (fig. 5.i), 295087 (321 x 481, RGB) ( fig. 5.j), 126007 (321 x 481, RGB) (fig. 5.k), 260058 (321 x 481, RGB) (fig. 5.l), 160068 (321 x 481, RGB) (fig. 5.m), 241004 (321 x 481, RGB) (fig. 5.n), 197017 (321 x 481, RGB) (fig. 5.o), 143090 (321 x 481, RGB) (fig. 5.p). a) b) c) d) e) f) g) h) i) j) k) l) m) n) o) p) Fig. 5 Test image for Digital Image Processing: a) Lena, b) Barbara, c) Cameraman, d) Pappers, e) Boats, f) Tulips, d) Watch. Test images from BSDS500 database, with numeric labels: h) 3096, i) 14037, j) 295087, k) 12607, l) 260058, m) 160068, n) 241004, o) 197017, p) 143090 Optimization of the 3P Keys Kernel Parameters ... 295 4.3. Algorithm for interpolation error determining The following Algorithm performs interpolation of the Test images, determines the interpolation error and determines the MSE depending on the parameters α, β and γ. Optimal parameters were determined by minimizing MSE. Algorithm is realized in the following steps: Input: (r0, r1, r2, r3) – 3P Keys kernel parameters, (αmin, Δα, αmax, βmin, Δβ, βmax, γmin, Δγ, γmax) - parameter boundaries and iteration steps, L – kernel length, TI (L x K) - Test image. Output: αopt, βopt, γopt. optimal parameters. MSEα, MSEαβ, MSEαβγ. Step 1: Converting a color image to a black-white image. IF Test image == Color Image 0.3 0.59 0.11 I T R G B=  +  +  END Step 2: Transformation of the image TI (L x K) into a one-dimensional matrix X: FOR = 1 : L FOR k = 1 : K (( 1) ) ( , ) I X K k T k−  + = END k END The dimensions of the one-dimensional matrix X are (1, N), where N = L x K. FOR γ = γmin : Δγ :γmax. FOR β = βmin : Δβ : βmax FOR α = αmin : Δα : αmax Step 3: Construction of the kernel: 0 1 2 3 r r r r r  = + + + , Step 4: The length of interpolation frame is: 2 1M L=  − FOR I = 1: N-M+1, Step 5: Selecting the I-th frame: XI = X (1: I+M-1) Step 6: Estimation of ˆ i x by applying PCC: ˆ [1: 2 : ] I I x X M r=  , where the symbol  stands for convolution. Step 7: Estimation error is: ˆ( ) ( ) I I e I X L x= − END I Step 8: Mean square error of estimation of 1P kernel: 1 2 1 ( ) 1 ( 1) | ( ) | N M k MSE N M e k  − + = = − +  , END α Step 9: Mean square error of estimation of 2P kernel: ( )MSE MSE  = , END β Step 10: Mean square error of estimation of 3P kernel: ( )MSE MSE  = , END γ Step 11:. Optimal values of 3P kernel parameters: , , ( , , ) arg min( ) opt opt opt MSE       = . 296 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ The described algorithm had the purpose of testing the interpolation error with the 3P Keys kernel in relation to the interpolation error with the 1P and 2P Keys kernels. The algorithm was implemented in Matlab, and, except for testing, is not intended for real- time systems. Therefore, the execution time of the algorithm is not of dominant importance. However, in the Experiment, using the Matlab function tic and toc, for the case of applying 1P, 2P and 3P Keys kernels, the interpolation execution time, TE, is determined. Based on the execution time, a comparative analysis was performed. 4.4. Experimental Results Using the Test Algorithm described in Section 4.3, interpolation of the Test images was performed. Interpolation for some values of α, β and γ parameters from the specified range has been performed. In addition, interpolation with the 1P, 2P and 3P Keys kernels with all parameters from the range was performed. For each interpolation, the interpolation error, MSE, is determined. Based on the minimum interpolation error, MSEmin, the optimal interpolation kernel parameter was determined. Figure 5.a shows the dependence of the MSEα on the parameter α, for the 1P Keys kernel (Test image Boats). The optimal parameter, αopt, was determined as ( ) arg min( )opt MSE   = . Figure 5.b shows the dependence of MSEαβ on the parameters α and β for the 2P Keys kernel (Test image Boats). The optimal parameters αopt and βopt, were determined as , ( , ) arg min( ) opt opt MSE      = . The minimum interpolation errors, MSEmin, and the corresponding optimal kernel parameters, when interpolating all Test images from the Image base, are shown in: a) Table 1 (1P Keys, αopt, MSE1P), b) Table 2 (2P Keys, αopt, βopt, MSE2P) and c) Table 3 (3P Keys, αopt, βopt, γopt, MSE3P). Table 4 shows the execution time of PCC convolution for: a) complete convolution with kernels (label in the table: Int1), (Eq. (1), Eq. (2) and Eq. (3)), b) convolution with the optimized kernel parameters (label in the table: Int2) (Eq. (29), Eq. (30) and Eq. (31)) and c) convolutional kernel execution time, without interpolation (label in the table: KerT). All interpolation execution times, as the arithmetic mean of the value of the results for 100000 interpolations, were determined. a) b) Fig. 5 Dependence of MSE on kernel parameters for the Test image Boats: a) 1P Keys kernel and b) 2P Keys Kernel Optimization of the 3P Keys Kernel Parameters ... 297 Table 1 Optimal parameter α and minimum MSE for 1P Keys kernel. Image base Image αopt MSE1P D S P t e st b a se Lena -0.3000 11.3234 Barbara -0.1000 247.0271 Cameraman -0.5000 0.3133 Pappers -0.6200 75.7521 Boats -0.3000 263.2390 Tulips -0.7000 14.5797 Watch -0.4000 49.9283 B S D S 5 0 0 b a z e 3096 0.200 0.7933 14037 -0.6000 10.0185 295087 0.1000 2.3780 126007 -0.4000 19.1678 260058 -0.300 4.8327 160068 0.6000 0.5835 241004 -0.300 6.4673 197017 0.3000 6.4499 143090 -0.01 18.2042 _1opt P 1PMSE -0.1706 45.6911 Table 2 Optimal parameters α and β, and minimum MSE for 2P Keys kernel Image base Image αopt βopt MSE2P D S P t e st b a se Lena -0.3000 -0.1000 11.3137 Barbara -0.1000 0 247.0271 Cameraman -0.3000 -0.2000 0.3114 Pappers -0.5400 0.1000 75.2829 Boats -0.4000 0.1000 262.7854 Tulips -0.6000 0.2000 14.1536 Watch 0 0.3000 49.2893 B S D S 5 0 0 b a z e 3096 0.2100 0.0030 0.6346 14037 -0.300 0.200 7.9427 295087 0.0400 -0.0100 1.9018 126007. -0.4000 0.0100 15.3342 260058 -0.300 -0.010 3.8658 160068 0.7000 0.1000 0.4663 241004 -0.3000 -0.0300 5.1729 197017 0.4000 0.0900 5.1557 143090 -0.0100 0.0040 14.5632 _ 2opt P _ 2opt P 2 PMSE -0.1375 0.0473 44.7000 298 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ Table 3 Optimal parameters α, β and γ , and minimum MSE for 3P Keys kernel Imag e base Image αopt βopt γopt MSE3P D S P t e st b a se Lena -0.3000 -0.1000 -0.0500 11.3130 Barbara -0.1000 -0.3000 -0.3000 242.1622 Cameraman 0.3000 -0.1000 0.1000 0.3113 Pappers -0.5200 0.1000 -0.0200 75.2664 Boats 0.5000 0.2000 0.0500 262.7747 Tulips -0.6000 0.2000 -0.0500 14.1407 Watch -0.1000 0.1000 -0.1500 49.2107 B S D S 5 0 0 b a z e 3096 0.2000 -0.007 -0.005 0.4760 14037 -0.300 0.2000 -0.010 5.9566 295087 0 0 0.0400 1.4259 126007. -0.400 0.1000 0.0800 11.4961 260058 -0.400 -0.060 0.0001 2.8970 160068 0.7000 0 -0.110 0.3491 241004 -0.300 0 0.0400 3.8780 197017 0.400 0.0800 -0.014 3.8666 143090 -0.020 0.0900 0.1000 10.9091 _ 3opt P _ 3opt P _ 3opt P 3PMSE -0.1587 0.0314 -0.0187 43.5271 Table 4 Execution time for PCC interpolation. Execution time TE (s) TE_1P_Keys TE_2P_Keys TE_3P_Keys Int1 1.430510-6 2.487610-6 2.522510-6 Int2 1.190310-6 2.070410-6 2.099010-6 KerT 5.649910-7 5.649210-7 5.648910-7 4.5. Comparative analysis According to the results presented in Table 1, Table 2 and Table 3, it is obvious that: a) MSE when applying 2P Keys kernel compared to 1P Keys kernel: 1P MSE / 2 PMSE = 45.6911 / 44.700 = 1.0222 times smaller, b) MSE when applying 3P Keys kernel compared to 1P Keys kernel: 1P MSE / 3P MSE = 45.6911 / 43.5271 = 1.0497 times smaller, and c) MSE when applying 3P Keys kernel compared to 2P Keys kernel: 2 P MSE / 3P MSE = 44.700 / 43.5970 = 1.0269 times smaller. The optimal values of the kernel parameters, determined by minimizing the ripple of the characteristic of the 3P Keys kernel (Eq. (28)), are: αopt = -0.6132, βopt = 0.1522 i γopt = 0.0195. Using the experimental results (Table 3), it was shown that the mean values of the optimal kernel parameters, determined for all Test images, are: _ 3opt P  = -0.1587, _ 3opt P  = 0.0314 and _ 3opt P = -0.0187. The absolute error of the kernel parameters, determined by algorithm for minimizing of the ripple of the spectral characteristic, in relation to the experimentally determined kernel parameters, are: a) α3P = _ 3 | | opt opt P  − = | 0.6132 ( 0.1587) |− − − = 0.4545, b) β3P = _ 3| |opt opt P − = | 0.1522 0.0314 |− = 0.1208, Optimization of the 3P Keys Kernel Parameters ... 299 c) 3P = | | opt opt  − = | 0.0195 ( 0.0187) |− − − = 0.0008. The Total absolute error of kernel parameter estimation for all Test images is ET = 2 2 2 3 3 3P P P    + + = 0.4703. In accordance with the results presented in Table 4, for a complete convolution with non- optimized kernels, (Eq. (1), Eq. (2) and Eq. (3)), (label in the Table 1: Int1), it is concluded that Time execution, TE, when applying: a) 2P Keys kernel compared to 1P Keys kernel is TE_2P_Keys / TE_1P_Keys = 2.487610 -6 / 1.430510-6 = 1.7389 times bigger, b) 3P Keys kernel compared to 1P Keys kernel is TE_3P_Keys / TE_1P_Keys = 2.522510 -6 / 1.430510-6 = 1.7633 times larger, and c) 3P Keys kernel compared to 2P Keys kernel is TE_3P_Keys / TE_2P_Keys = 2.522510 - 6 / 2.487610-6 = 1.014 times larger In accordance with the results presented in Table 4, for a complete convolution with optimized kernels, (Eq. (29), Eq. (30) and Eq. (31)), (label in the Table 1: Int1), it is concluded that Time execution, TE, when applying: a) 2P Keys kernel compared to 1P Keys kernel is TE_2P_Keys / TE_1P_Keys = 2.070410 -6 / 1.190310-6 = 1.7393 times bigger, b) 3P Keys kernel compared to 1P Keys kernel is TE_3P_Keys / TE_1P_Keys = 2.099010 -6 / 1.190310-6 = 1.7634 times larger, and c) 3P Keys kernel compared to 2P Keys kernel is TE_3P_Keys / TE_2P_Keys = 2.099010 -6 / 2.070410-6 = 1.013 times larger. The convolutional kernel execution time, TE, without interpolation (label in the table: KerT) is approximately 5.64910-7 for all Keys kernels. The reason is that all kernels, after optimization, have the same numerical complexity: a third-order polynomial with constant coefficients. When a 3P Keys interpolation kernel with optimized parameters is applied, the convolution execution time, compared to non-optimized kernels, is TE 3P Keys / TE 3P Keys opt = 2.522510 -6 / 2.099010-6 = 1.2017 times less. The results from the described Experiment and the conducted detailed comparative analysis of interpolation error, which were expressed through MSE, indicated the fact that the accuracy of interpolation when the 3P Keys kernel was applied, in relation to 1P and 2P kernels, increased. The testing algorithm is implemented in the Matlab programming language. The interpolation execution times were calculated using the Matlab function tic and toc. The experiment only showed precision interpolation with 3P Keys kernels compared to precision with 1P Keys and 2P Keys kernels. In addition, the relative ratio of the interpolation execution times is determined. However, for real-time interpolation, the convolution algorithm must be written in a programming language (for example, programming language C) where, in the compilation process, optimizations can be made to reduce program execution time (Eq. 31). In this way, image processing can be provided in real-time mode and, among other things, on Personal Computers. 5. CONCLUSION The paper presents an algorithm for optimizing the parameters of the 3P Keys interpolation kernel. Parameter optimization was performed in the spectral domain by minimizing the ripple of the spectral characteristic. First, the spectral characteristic was developed in the Taylor series, and, after that, the members of the Taylor series that have a great effect on increasing the riple of the spectral characteristic, were eliminated. From the conditions of elimination of the dominant members of the Taylor series, the optimal values of the parameters 3P Keys kernel (αopt = -0.6132, βopt = 0.1522, γopt = -0.0195) were determined. Verification of the accuracy of the 3P Keys kernel when interpolating images 300 N. SAVIĆ, Z. MILIVOJEVIĆ, Z. VELIČKOVIĆ was performed experimentally. The interpolation accuracy is expressed through the MSE interpolation error. Detailed comparative analysis showed that the 3P Keys kernel, with experimentally determined optimal parameters, has a higher interpolation accuracy compared to the 1P Keys kernel 1.0497 times, and compared to the 2P Keys kernel 1.0269 times. Based on the presented results, it is concluded that the 3P Keys kernel is superior to the 1P Keys and 2P kernels and that the interpolation error is very small. Experimental results show that the 3P Keys kernel, with the optimal parameters, which are determined by the optimization algorithm presented in this paper, performed the interpolation of the Test images with great precision. The 3P Keys kernel with optimal parameters, compared to the ideal sinc kernel, has a small numerical complexity, and therefore, it is suitable for implementation in convolutional interpolations for operation in real-time systems. REFERENCES [1] R. G. Keys, "Cubic convolution interpolation for digital image processing" IEEE Trans. Acout. Speech, & Signal Processing, vol. ASSP-29, pp. 1153–1160, Dec. 1981. [2] E. Meijering, M. Unser, "A Note on Cubic Convolution Interpolation", IEEE Transactions on Image Processing, vol. 12, no. 4, pp. 447–479, April 2003. [3] N. Dodgson, "Quadratic Interpolation for Image Resampling", IEEE Transactions On Image Processing, vol. 6, no. 9, pp. 1322–1326, Sept. 1997. [4] O. Rukundo, B. Maharaj, "Optimization of image interpolation based on nearest neighbor algorithm", In Proceedings of the International Conference on Computer Vision Theory and Applications (VISAPP), 2014, vol. 1, pp. 641–647. [5] S. S. Rifman, "Digital rectification of ERTS multispectral imagery", In Proceedings of the Symp. Significant Results Obtained From the Earth Resources Technology Satellite-1, 1973, vol 1, sec. B, pp. 1131–1142. [6] T. B. Deng, "Frequency-domain weighted-least-squares design of signal-dependent quadratic interpolators", IET Signal Process., vol. 4, no. 1, pp. 102–111, Feb. 2010. [7] N. Gajalakshmi, S. Karunanithi, "Cubic Convolution and Osculatory Interpolation for Image Analysis", International Journal of Creative Research Thoughts (IJCRT), vol. 9, issue 12, pp. 836–841, December 2021. [8] Y. Li, F. Qi, Y. Wan, "Improvements On Bicubic Image Interpolation", In Proceedings of the IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), 2019, pp. 1316– 1320. [9] S.-H. Hong, L. Wang, T.-K. Truong, "An Improved Approach to the Cubic-Spline Interpolation", In Proceedings of the 25th IEEE International Conference on Image Processing (ICIP) 2018, pp. 1468– 1472. [10] K. S. Park, R. A. Schowengerdt, "Image reconstruction by parametric cubic convolution", Computer Vision, Graphics & Image Processing, vol. 23, pp. 258–272, 1982. [11] E. Meijering, K. Zuiderveld, M. Viegever, "Image Reconstruction by Convolution with Symmetrical Piecewise nth-Order Polynomial Kernels", IEEE Transactions on Image Processing, vol. 8, no. 2, pp. 192–201, Feb. 1999. [12] Z. Milivojević, N. Savić, D. Brodić, P. Rajković, "Optimization parameters of two parameter Keys kernel in the spectral domain", In Proceedings of the XV International Scientific-Professional Symposium INFOTEH-Jahorina, Bosnia, 2016, pp. 392–397. [13] R. Hanssen, R. Bamler, "Evaluation of Interpolation Kernels for SAR Interferometry", IEEE Transactions on Geoscience and Remote Sensing, vol. 37, no. 1, pp. 318–321, Jan. 1999. [14] Z. Milivojević, D. Brodić, "Estimation Of The Fundamental Frequency Of The Real Speech Signal Compressed By MP3 Algorithm", Archives of Acoustics, vol. 38. no. 3, pp. 363–373, 2013. [15] Z. Milivojević, N. Savić, D. Brodić, "Three-Parametric Cubic Convolution Kernel For Estimating The Fundamental Frequency Of The Speech Signal", Computing and Informatics, vol. 36, pp. 449–469, 2017. [16] N. Savić, Z. Milivojević, "Optimization of the 3P Keys Kernel Parameters for Interpolacion of Audio Signals", In Proceedings of the International Scientific Conference UNITECH'20, Gabrovo, Bulgaria, 2020, pp. 200–205. [17] https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/