Families of Heron Digital Filters for Images Filtering Ekaterina Ostheimer1 , Valeriy Labunets2 , and Filipp Myasnikov2 1 Capricat LLC, 1340 S., Ocean Blvd., Suite 209, Pompano Beach, 33062 Florida, USA katya@capricat.com, 2 Ural Federal University, pr. Mira, 19, Yekaterinburg, 620002, Russian Federation vlabunets05@yahoo.com, fsmyasnikov@gmail.com Abstract. The basic idea behind this work is in extraction (estimation) of the uncorrupted image from the distorted or noised one. The idea is also referred to as the image denoising. Noise removal or noise reduction in an image can be done by linear or nonlinear filtering. The most popu- lar linear technique is based on averaging (or meaning) linear operators. Usually, denoising via linear filters does not work sufficiently since both the noise and edges (in the image) contain high frequencies. Therefore, any practical denoising model has to be nonlinear. In this paper, we pro- pose two new nonlinear data-dependent filters, namely, the generalized mean and median Heronian ones. These filters are based on the Hero- nian means and medians that are used for developing a new theoretical framework for image filtering. The main goal of the work is to show that new elaborated filters can be applied to solve problems of image filtering in a natural and effective manner. Keywords: Nonlinear filters, generalized aggregation mean 1 Introduction The basic idea of this work is in application of a systematic method to nonlinear filtering based on the Heronian averaging and median nonlinear operators [1–4]. The classical Heronian mean and median of two positive real numbers a and b have the following forms √ √ √ MeanHeron(a, b) = ( aa + ab + bb)/3, √ √ √ MedHeron(a, b) = ( aa, ab, bb). We are going to generalize and use these mean and median operators for con- structing new classes of nonlinear digital filters. The general aim of this work is to clarify whether the filters based on such exotic meanings have any smoothing properties. 56 2 Generalized Heronian means and medians Let (x1 , x2 , . . . , xN ) be an N -tuple of positive real numbers. Definition 1. The following generalized means and median 1 XX√ MeanHeronI2 (x1 , . . . , xN ) = xi xj , M H2 i 6j s 1 XX MeanHeronII 2 (x 1 , . . . , x N ) = xi xj , (1) M H2 i 6j n s √ o  n o  MedHeron2 (x1 , . . . , xN ) = Med xi xj = Med xi xj i6j i6j are called the Heronian means and median of the first and second kinds [1–3], respectively, where M H2 = N (N + 1)/2 = MeanHeron2 (1, 1, . . . , 1). Here, we want to generalize Definition 1 by summarizing up the k-th roots of all possible distinct products of k elements of (x1 , . . . , xN ) with repetition. k The number of all such products is CN +k−1 = M Hk .. This determines the normalization factor and leads to the following definitions: 1 XX X √ MeanHeronIk (x1 , . . . , xN ) = ··· i1 i2 · · · x ik , k x x M Hk i1 6 i2 6 6ik (2) sX X X 1 MeanHeronII 2 (x1 , . . . , xN ) = k ··· xi1 xi2 · · · xik M Hk i1 6 i2 6 6ik for the generalized Heronian means and n o  √ MedHeronk (x1 , . . . , xN ) = Med k xi1 xi2 · · · xik = i1 6i2 6···6ik (3) s n  o = k Med xi1 xi2 · · · xik . i1 6i2 6···6ik for the generalized Heronian median, where M Hk = MedHeronk (1, 1, . . . , 1). Let us introduce the observation model and notion used throughout the pa- per. We consider noise images in the form f (i, j) = s(i, j)) + η(i, j), where s(i, j) is the original grey-level image and η(i, j) denotes the noise introduced into s(i, j) to produce the corrupted image f (i, j). Here, (i, j) ∈ Z2 are 2D coordinates that represent the pixel location. The aim of image enhancement is to reduce the noise as much as possible or to find a method, which, for the given s(i, j), de- rives an image sb(i, j)) as close as possible to the original s(i, j) subjected to a 57 suitable optimality criterion. In the standard linear and median 2D-filters with the square N -cellular window M(i, j) and located at (i, j), the mean and median replace the central pixel sb(i, j) = Mean [f (m, n)] , sb(i, j) = Med [f (m, n)] , (m,n)∈M (i,j) (m,n)∈M (i,j) (4) where sb(i, j) is the filtered image, {f (m, n)}(m,n)∈M(i,j) is an image block of the fixed size N = Q × Q extracted from f by moving window M(i, j) at the position (i, j), and Mean and Med are the classical mean and median operators, where Q = 2r + 1 is an odd integer. All pixels of this block are numbered by the following way: (m, n) → r has the following form r = Q(m + 1) + (n + 1). For example, for the 9-cellular window of size N = 3 × 3 = 9 we have (−1, −1) → 0, (−1, 0) → 1, (−1, 1) → 2, (0, −1) → 3, (0, 0) → 4, (0, 1) → 5, (1, −1) → 6, (1, 0) → 7, (1, 1) → 8 : f (−1, −1) f (−1, 0) f (−1, 1) f0 f1 f2 {f (m, n)}(m,n)∈M(i,j) = f (0, −1) f (0, 0) f (0, 1) −→ f 3 f 4 f 5 . f (1, −1) f (1, 0) f (1, 1) f6 f7 f8 3 Heronian mean and median filters Now we modify the classical mean and median filters (4) in the following way: h i I r sb(i, j) = MeanHeronIk [f (m, n)] = MeanHeronk f(i,j) = (m,n)∈M(i,j) r=1,2,...,N 1 XX Xq rk r1 r2 = ··· k f(i,j) , f(i,j) , . . . , f(i,j) , (5) M Hk r 1 6 r2 6 6rk h i II r sb(i, j) = MeanHeronII k [f (m, n)] = MeanHeronk f(i,j) = (m,n)∈M(i,j) r=1,2,...,N s 1 XX X rk r1 r2 = k ··· f(i,j) , f(i,j) , . . . , f(i,j) (6) M Hk r1 6 r2 6 6rk for the generalized Heronian meaning filers of the first and the second kinds, respectively, and h i h i MeanHeronIk f(i,j) r = MeanHeronII k r f(i,j) = r=1,2,...,N r=1,2,...,N n q o  r1 r2 rk = Med k f(i,j) , f(i,j) , . . . , f(i,j) (7) r1 6r2 6···6rk for the generalized Heronian median filter. 58 4 Generalized Heronian aggregation The aggregation problem [5, 6] consist in aggregating N -tuples of objects all belonging to a given set D, into a single object of the same set S, i.e., Agg : SN −→ S. In the case of mathematical aggregation operator (AO) the set S, is an interval of the real S = [0, 1] ⊂ R, or integer numbers S = [0, 255] ⊂ Z. In this setting, an AO is simply a function, which assigns a number y to any N -tuple of numbers (x1 , x2 . . . . , xN ): y = Agg(x1 , x2 , . . . , xN ) that satisfies: 1. Agg(x) = x. 2. Agg(a, a, . . . , a) = a. In particular, Agg(0, 0, . . . , 0) = 0 and Agg(1, 1, . . . , 1) = 1 (or Agg(255, 255, . . . , 255) = 255). 3. min(x1 , x2 , . . . , xN ) ≤ Agg(x1 , x1 , . . . , xN )) ≤ max(x1 , x2 , . . . , xN . Here min(x1 , x2 , . . . , xN ) and max(x1 , x2 , . . . , xN are respectively the minimum and the maximum values among the elements of (x1 , x2 . . . . , xN ). All other prop- erties may come in addition to this fundamental group. For example, if for every permutation ∀σ ∈ SN of {1, 2, . . . , N } the AO satisfies: y = Agg(xσ(1) , xσ(2) , . . . , xσ(N ) ) = Agg(x1 , x2 , . . . , xN ), then it is invariant (symmetric) with respect to the permutations of the elements of (x1 , x2 , . . . , xN ). In other words, as far as means are concerned, the order of the elements of (x1 , x2 , . . . , xN ) is - and must be – completely irrelevant. We list below a few particular cases of means: P N 1. Arithmetic mean (K(x) = x): Mean(x1 , x2 , . . . , xN ) = N1 xi .  r i=1 Q N 2. Geometric mean (K(x) = log(x)): Geo(x1 , x2 , . . . , xN ) = N i=1 xi .  N −1 −1 1 P −1 3. Harmonic mean (K(x) = x ): Harm(x1 , x2 , . . . , xN ) = N xi . i=1 4. One-parametric family quasi arithmetic (power or Hólder) s means corre-  N  p p 1 P p sponding to the functions K(x) = x : Hold(x1 , x2 , . . . , xN ) = N xi . i=1 This family is particularly interesting, because it generalizes a group of com- mon means, only by changing the value of p. A very notable particular cases correspond to the logic functions (min, max, median): y = Min(x1 , . . . , xN ), y = Max(x1 , . . . , xN ), y = Med(x1 , . . . , xN ). When filters 5–7 are modified as follows: b s(i, j) = Agg [f (m, n)] , (m,n)∈M (i,j) (8) we get the unique class of nonlinear aggregation filters [8–11]. In this work, we are going to use aggregation operator to the Heronian (ex- tended) data. Let (x1 , x2 , . . . , xN ) be an N -tuple of positive real numbers. 59 Definition 2. The following generalized aggregations √ HeronAggI2 (x1 , . . . , xN ) = Aggi≤j xi xj , (9) q II HeronAgg2 (x1 , . . . , xN ) = Aggi≤j {xi xj } (10) are called the Heronian aggregations of the first and second kinds, respectively. Here, we want to generalize Definition 2 by summarizing up the k-th roots of all possible distinct products of k elements of (x1 , . . . , xN ) with repetition. k The number of all such products is CN +k−1 = M Hk . They form the Heronian (extended) data. This determines the following definitions: HeronAggIk (x1 , . . . , xN ) = Aggi1 ≤i2 ≤···≤ik {xi1 xi2 · · · xik } , (11) q HeronAggII k (x1 , . . . , xN ) = k Aggi1 ≤i2 ≤···≤ik {xi1 xi2 · · · xik }. (12) 5 Heronian aggregation filters Now we modify the classical mean and median filters (4) in the following way: h i h i r1 r2 rk sb(i, j) = HeronAggIk f(i,j) , f(i,j) , . . . , f(i,j) = HeronAggIk f(i,j) r = (m,n)∈M(i,j) r=1,2,...,N nq o r1 r2 rk = Aggr1 ≤r2 ≤...≤k k f(i,j) , f(i,j) , . . . , f(i,j) , (13) h i h i r1 r2 rk sb(i, j) = HeronAggII k f(i,j) , f(i,j) , . . . , f(i,j) = HeronAggII k f r (i,j) = (m,n)∈M(i,j) r=1,2,...,N r n o r1 r2 rk = k Aggr1 ≤r2 ≤...≤k f(i,j) , f(i,j) , . . . , f(i,j) , (14) for the generalized Heronian aggregating filters of the first and the second kinds, respectively. In particular case (k = 1) we get the unique class of nonlinear aggregation filters [8, 9]. 6 Experiments Generalized aggregation Heronian filtering with Agg = Mean, Med has been applied to noised 256 × 256 gray level images “Dog” (Figures 1b, 2b). The de- noised images are shown in Figures 1–2. All filters have very good denoising properties. This fact confirms that further investigation of these new filters is perspective. Particularly, very interesting is a question about the types of noises, for which such filters are optimal. 60 7 Conclusions We suggested and developed a new theoretical framework for image filtering based the Heronian mean and median. The main goal of the work is to show that Heronian mean and median can be used to solve problems of image filtering in a natural and effective manner. Acknowledgment. This work was supported by grants the RFBR Nos. 13-07- 12168 and 13-07-00785. References 1. Mitra, S.K.: Nonlinear Image Processing. Academic Press Series in Communications, Networking, and Multimedia, San Diego, New York, p.248, (2001) 2. Sykora, S.: Mathematical Means and Averages: Generalized Heronian means I. Stan’s Library, Ed. S.Sykora, I (2009) 3. Sykora, S.: Generalized Heronian means II. Stan’s Library, Ed. S.Sykora, II (2009) 4. Sykora, S.: Generalized Heronian means III. Stan’s Library, Ed. S.Sykora, III (2009) 5. Mayor, G., Trillas, E.: On the representation of some Aggregation functions. In Proceeding of ISMVL, 20, 111–114 (1986) 6. Ovchinnikov, S.: On Robust Aggregation Procedures. Aggregation Operators for Fusion under Fuzziness. Bouchon-Meunier B. (eds.), 3–10 (1998) 7. Kolmogorov, A.: Sur la notion de la moyenne. Atti Accad. Naz. Lincei, 12, 388-391 (1930) 8. Labunets V. G.: Filters based on aggregation operators. Part 1. Aggregation Oper- ators. 24th Int. Crimean Conference Microwave & Telecommunication Technology (CriMiCo2014), Sevastopol, Crimea, Russia, 24, 1239–1240 (2014) 9. Labunets, V.G., Gainanov, D.N., Ostheimer, E.: Filters based on aggregation op- erators. Part 2. The Kolmogorov filters. 24th Int. Crimean Conference Microwave & Telecommunication Technology (CriMiCo2014), Sevastopol, Crimea, Russia, 24, 1241–1242 (2014) 10. Labunets, V.G., Gainanov, D.N., Tarasov A.D., Ostheimer E.: Filters based on aggregation operators. Part 3. The Heron filters. 24th Int. Crimean Conference Microwave & Telecommunication Technology (CriMiCo2014), Sevastopol, Crimea, Russia, 24, 1243–1244 (2014) 11. Labunets, V.G., Gainanov, D.N., Arslanova, R.A., Ostheimer, E.: Filters based on aggregation operators. Part 4. Generalized vector median filters . 24th Int. Crimean Conference Microwave & Telecommunication Technology (CriMiCo2014), Sevastopol, Crimea, Russia, 24, 1245–1246 (2014) 61 Appendix. Figures a) Original image b) Noise image, P SN R = 21.83 c) d) MeanHeron, P SN R = 32.364 MedHeron, P SN R = 31.297 Fig. 1. Original (a) and noise (b) images; noise: Salt-Pepper; denoised images (c)–(f) 62 a) Original image b) Noise image, P SN R = 28.24 c) d) MeanHeron, P SN R = 31.293 MedHeron, P SN R = 29.531 Fig. 2. Original (a) and noise (b) images; noise: Laplasian PDF; denoised images (c)-(f) 63