Quantum image median filtering in the spatial domain

Abstract

Spatial filtering is one principal tool used in image processing for a broad spectrum of applications. Median filtering has become a prominent representation of spatial filtering because its performance in noise reduction is excellent. Although filtering of quantum images in the frequency domain has been described in the literature, and there is a one-to-one correspondence between linear spatial filters and filters in the frequency domain, median filtering is a nonlinear process that cannot be achieved in the frequency domain. We therefore investigated the spatial filtering of quantum image, focusing on the design method of the quantum median filter and applications in image de-noising. To this end, first, we presented the quantum circuits for three basic modules (i.e., Cycle Shift, Comparator, and Swap), and then, we design two composite modules (i.e., Sort and Median Calculation). We next constructed a complete quantum circuit that implements the median filtering task and present the results of several simulation experiments on some grayscale images with different noise patterns. Although experimental results show that the proposed scheme has almost the same noise suppression capacity as its classical counterpart, the complexity analysis shows that the proposed scheme can reduce the computational complexity of the classical median filter from the exponential function of image size n to the second-order polynomial function of image size n, so that the classical method can be speeded up.

1 Introduction

Quantum computing as a new computing method has received ever greater attention because of its high parallelism. In the near future, quantum computers are expected to replace classical computers. Therefore, it is meaningful to study the mechanisms underlying information processing in quantum computers. In classical image processing, the pixel coordinates and pixel grayscale values are both integers, the latter based on power of two. These features of the classical image have some similarity to the basis states of multi-qubit systems. These similarities helped to make quantum image processing a new inter-discipline at the beginning of this century. In the development of quantum image processing, the earliest literature can be traced back to 2003, and Reference [1] is the first paper in this sub-discipline, which marks the birth of this sub-discipline. For a detailed account of its developmental timeline, the interested reader is referred to [2].

To deal with images on a quantum computer, the first task is to convert classical images into quantum images; hence, the representation of quantum images is the first problem needing to be solved. Concerning the quantum image description, in 2003, Venegas-Andraca and Bose proposed the qubit lattice representation to encode quantum images [3]. This was closely followed by Latorre’s real ket representation for quantum images [4]. Years later, Le et al.’s flexible representation for quantum images (FRQI) was proposed in 2010 [5] and later reviewed in 2011 [6]. These three models are collectively regarded as prototypical of the sub-discipline of quantum image processing [7]. The various models proposed later are a modification or extension of these three models. For example, in a procedure similar to the qubit lattice representation, termed the SQR model [8], the infrared radiation energy from objects was transformed into a quantum state $|I\rangle$ by a converter C, i.e., C detected and recorded radiation energy and then produced a quantum state $|I\rangle$ as output. By extending the grayscale information in FRQI to a color representation, a multichannel representation of quantum images, MCQI, was proposed in [9, 10], which uses the R, G, and B channels to represent the different color information of an image and also retains the normalized state.

Reference [11] notes that the above FRQI has three disadvantages that limit its application: 1) The original classical image cannot be accurately retrieved. According to the postulates of quantum mechanics, the probability amplitudes of a quantum state cannot be accurately determined using a finite number of measurements. 2) Only simple color operations can be performed on the quantum image. This limitation arises because only a single qubit is used to represent the color information for each pixel. Hence, it is difficult to design quantum circuits for image processing tasks that need to separate pixels of different colors to apply distinct transformations. 3) There are practical limitations on the number of colors/positions that can be physically represented using the angle parameter of a qubit. The energy separation between the states of the qubit should be greater than the thermal energy. Therefore, to encode information in $2^{24}$ qubit angles is not feasible even if we have a scheme operating at very low temperatures and with very high frequency radiation.

To overcome these shortcomings, in 2013, Refernce [12] proposed the novel enhanced quantum representation of digital images (NEQR). The model stores images with $(2n+q)$ qubits, where 2n qubits describe the pixel position and q qubits describe the grayscale intensity. In NEQR, both the color and position of a pixel in the image are encoded in the basic quantum states (instead of the superposition state with complex numbers as coefficients). Thus, both color and position information in this representation can be retrieved deterministically through a finite number of projective measurements, and a larger class of color-related image processing operations can be easily achieved. Based on the background given, in this paper, the NEQR model is used to describe quantum images because filtering is then a transformation operation for the grayscale intensity of the pixel. For a concise review of quantum image representations, we refer the reader to [7], which gives the most comprehensive review of the principles, features, and relationships of all the existing models for image description.

After establishing this model for the quantum description from the classical image, quantum image processing becomes the main theme of this sub-discipline. At present, compared with classical image processing, quantum image processing technology is still far from a mature field. Although preliminary research results have been obtained in such some areas such as image matching [13], image location [14], geometric transformation [15], color processing [16], feature extraction [17], image segmentation [18], image scrambling [19, 20], image encryption [21], image steganography [22], image watermarking [23, 24], and quantum movie [25], etc., in the quantum image filtering, the relevant research results are still scarce. This is mainly because, in classical image processing, the filter is related to convolution or correlation; realizing these processes using quantum circuits has been proved impossible [26]. In 2013, Simona et al. proposed the frequency domain filtering of quantum images in [27]. In this approach, they use the principle of a quantum oracle to implement the filter function and described quantum circuits that implement the filtering task and presented the results of several simulation experiments on grayscale images.

Recently, [28] proposed a spatial filtering method for quantum images. In this method, by using quantum addition instead of quantum multiplication, the unrealization of quantum convolution is effectively avoided. Later, [29] pointed out two shortcomings of this method: (1) It is necessary to know exactly the specific value of the filter coefficients before each filtering behavior, and (2) this method is only suitable for integer filter coefficients but not for decimal filter coefficients. In [29], an improved version is proposed which takes full advantage of the quantum multiplication and can overcome these two shortcomings. However, these two methods only apply to mean filtering, not to median filtering. In the spatial domain, the median filtering methods of quantum images have not been reported.

In summary, as an emerging interdisciplinary topic, although quantum image processing has made many advances, it still faces many challenges. Compared with the results of classical images processing, there is a big gap in depth and breadth. For example, the spatial filtering method has been widely used in classical images processing, but there is no quantum counterpart at present. To solve the problem of quantum image filtering in the spatial domain, we must first consider how to avoid convolution or correlation operations. In classical image processing, median filtering is notably a nonlinear process that is unrelated to the convolution or correlation operations, which means that median filtering does not involve convolution or correlation. Similarly, in quantum image processing, median filtering also does not need to deal with convolution or correlation operations, and hence sidesteps the restrictions mentioned in [26]. In this paper, a quantum median filtering method is proposed. Unlike classic median filtering in the spatial domain, we have adopted a different implementation method. The classic median filtering is achieved by sliding the filtering mask over the entire image. In the proposed method, the original image is first translated by one unit in eight directions (i.e., up, down, left, right, up left, up right, down left, down right), and then, for nine images (the original image and the transposed eight images), the median of nine pixels with the same position is calculated, which is the median of the corresponding pixels in the filtered image. Different from the classical method, using the parallelism of quantum computing, all the median calculations can be carried out at the same time, so that the classical method can be speeded up.

The remainder of this paper is organized as follows. Section 2 introduces the quantum median filtering operation, designs the module structure of filtering circuits, and analyzes their complexity. Some simulation experiments are presented in Sect. 3. In Sect. 4, we offer concluding remarks.

2 Median filtering of quantum images

We remark that this method applies only to grayscale images, with a grayscale range of $\{0,\!1,\!\ldots \!,\!2^q-1\}$, and assumes that the size of the image is $2^n\times 2^n$.

2.1 NEQR model of representing quantum images

For a grayscale image, NEQR encodes q bits of binary grayscale values into q qubits. In NEQR, a grayscale image of size $2^n\times 2^n$ has representation,

$$\begin{aligned} \begin{array}{lll} |Q\rangle= & {} \frac{1}{2^n}\sum \limits _{y=0}^{2^n-1}\sum \limits _{x=0}^{2^n-1}|f(y,x)\rangle |yx\rangle =\frac{1}{2^n}\sum \limits _{y=0}^{2^n-1}\sum \limits _{x=0}^{2^n-1}|c_{yx}^{q-1}c_{yx}^{q-2}\ldots c_{yx}^{0}\rangle |yx\rangle , \end{array} \end{aligned}$$

(1)

where $c_{yx}^{q-1}, c_{yx}^{q-2},\ldots \,c_{yx}^{0}\in \{0,1\}$, and $f(y,x)\in \{0,1,\ldots , 2^{q}-1\}$. From [12], NEQR needs $q+2n$ qubits to represent our grayscale image.

2.2 Median filter

As an aid to understand the content of this paper, we first introduce the concept of median filtering.

Order-statistics filters are nonlinear spatial filters whose response is based on ordering (ranking) the pixels contained in the image area falling under the filter window and then replacing the value of the center pixel with the value determined by the ranking result [30]. The best-known filter in this category is the median filter, which, as its name implies, replaces the value of a pixel by the median of the intensity values in the neighborhood of that pixel (the original value of the pixel is included in the computation of the median). The median, $\xi$, of a set of values is such that half the values in the set are less than or equal to $\xi$, and half are greater than or equal to $\xi$.

To perform median filtering at a point in an image, we first sort the values of the pixel in the neighborhood, determine their median, and assign that value to the corresponding pixel in the filtered image. Thus, the principal function of median filters is to force points with distinct intensity levels to be more like their neighbors [30]. Indeed, isolated clusters of pixels that are light or dark with respect to their neighbors, and whose area is less than $m^2/2$ (one-half the filter area), are eliminated by an $m\times m$ median filter. In this case, “eliminated” means forced to the median intensity of the neighbors. Larger clusters are affected considerably less.

Median filters are quite popular because, for certain types of random noise, they provide excellent noise reduction capabilities with considerably less blurring than linear smoothing filters of similar size.

2.3 Modules used in proposed quantum median filter

Although the size of the median filter may be any $m\times m$, where m is an odd number, in most cases, the $3\times 3$ filter has been able to meet filtering requirements. In this paper, for simplicity of description, we only consider design of $3\times 3$ filters.

Designing a median filter circuit is a complex task. We decompose the design task into several modules which can be divided into two categories: basic modules and composite modules. The so-called basic module refers to the module is no longer formed by other modules, such modules include: Cycle Shift modules (i.e., $S_{y-}, S_{y+}, S_{x-}, S_{y+}$), Comparator module, and Swap module. The so-called composite module means that the module is composed of other basic modules, such modules include Sort module and Median Calculation module. The hierarchy of all these modules is depicted in Fig. 1.

Fig. 1

Tree structure reflecting the hierarchy between the various modules in a median filtering circuit. The leaf nodes are the basic modules, the internal nodes are the composite modules, and the root node is the total circuit

2.4 Quantum circuits of basic modules

In Fig. 1, there are the following basic modules: Cycle Shift, Comparator, and Swap. The functions and quantum circuits of these modules are given below.

• (1) Cycle Shift modules

The four cyclic shift modules used in this paper are represented as $S_{y-}$, $S_{y+}$, $S_{x-}$, and $S_{y+}$, respectively, which are derived from [17]. The function of these four modules is to translates all pixels in the image by one unit. Specifically, for an image of sized $2^n\times 2^n$, let the position qubit be $|y\rangle |x\rangle$, then the roles of these four modules can be described as

$$\begin{aligned} \left\{ \begin{array}{ccc}S_{y-}(|y\rangle )&{}=&{}|(y-1)~mod~2^n\rangle \\ S_{y+}(|y\rangle )&{}=&{}|(y+1)~mod~2^n\rangle \\ S_{x-}(|x\rangle )&{}=&{}|(x-1)~mod~2^n\rangle \\ S_{x+}(|x\rangle )&{}=&{}|(x+1)~mod~2^n\rangle \end{array}\right. . \end{aligned}$$

(2)

The quantum circuits of these four modules are shown in Fig. 2.

Fig. 2

(figure adapted from [17])

Cycle Shift modules. a Quantum circuit that translates all pixels in the image to the top by one unit. (i) Circuit, (ii) example. b Quantum circuit that translates all pixels in the image to the bottom by one unit. (i) Circuit, (ii) example. c Quantum circuit that translates all pixels in the image to the left by one unit. (i) Circuit, (ii) example. d Quantum circuit that translates all pixels in the image to the right by one unit. (i) Circuit, (ii) example.

• (2) Comparator module

The Comparator module occupies an important position in the median filter. Here, we use the quantum Comparator designed in [31], and its quantum circuit is shown in Fig. 3.

Fig. 3

(figure adapted from [31])

Comparator module.

The Comparator compares x and y, where $x=x_{n-1}x_{n-2}\ldots x_0$, $y=y_{n-1}y_{n-2}\ldots y_0$, $x_i,y_i\in \{0,1\},i=n-1,n-2,\ldots ,0$. Qubits $e_1$ and $e_0$ are outputs. If $e_1e_0=10$ then $x>y$; if $e_1e_0=01$ then $x<y$; and if $e_1e_0=00$ then $x=y$.

• (3) Swap module

The function of this module is to swap two grayscale values. Specifically, if the grayscale value $c_{q-1}c_{q-2}\!\ldots \! c_0$ is stored in register $|c\rangle$ and the grayscale value $\hat{c}_{q-1}\hat{c}_{q-2}\!\ldots \! \hat{c}_0$ is stored in register $|\hat{c}\rangle$, then, after the module is executed, the $\hat{c}_{q-1}\hat{c}_{q-2}\!\ldots \! \hat{c}_0$ is stored in register $|c\rangle$ and the $c_{q-1}c_{q-2}\!\ldots \! c_0$ is stored in register $|\hat{c}\rangle$. That is, the module implements the interchange of two quantum register contents. Its quantum circuit is shown in Fig. 4.

Fig. 4

Swap module

2.5 Quantum circuits of composite modules

• (1) Sort module

The function of the Sort module is to sort two integers in ascending order. This module consists of a Comparator and a Swap module; see Fig. 5. In this module, we use the quantum Comparator to compare two input integers a and b. We then decide whether to swap a and b according to the value of $e_1e_0$; if and only if $e_1e_0=10$ (i.e., $a>b$) is a and b swapped using the Swap module. At this point, in the output of the module, $\hat{a}$ and $\hat{b}$ are the sorting results of a and b.

Fig. 5

Sort module

• (2) Median Calculation module

The function of the Median Calculation module is to calculate the median of the nine integers. This module is composed of thirty Sort. Figure 6 shows its quantum circuit structure. In Fig. 6, $c_1, c_2, \ldots , c_9$ are nine integers that are input to this module.

Fig. 6

Median Calculation module, where the $|M\rangle$ in the output denotes the median of nine integers

Fig. 7

An explanation of the filtering scheme proposed in this paper. a The original image in a $3 \times 3$ window and the image that is shifted by a unit in 8 directions. b The median calculation process based on the original image and the eight shifted images

We briefly describe the operation of this module. First, to obtain the median of the nine integers, based on the bubble sort principle, we use the 30 Sort modules to order the nine integers $c_1, c_2, \ldots , c_9$. Clearly, after sorting, the fifth integer $\hat{c}_5=M$ is the median of the nine integers.

2.6 Complete median filtering circuits

2.6.1 Background on proposed median filtering technique

In the proposed method, the original image is first translated by one unit in eight directions (i.e., up, down, left, right, up left, up right, down left, down right). At this time, for nine images (the original image$|I\rangle$ and the transposed eight images $|I_1\rangle \sim |I_8\rangle$), nine pixels with the same position (e.g., $|c_{yx}\rangle$, $|c_{y_1x_1=yx}\rangle$, $|c_{y_2x_2=yx}\rangle$, $|c_{y_3x_3=yx}\rangle$, $|c_{y_4x_4=yx}\rangle$, $|c_{y_5x_5=yx}\rangle$, $|c_{y_6x_6=yx}\rangle$, $|c_{y_7x_7=yx}\rangle$, $|c_{y_8x_8=yx}\rangle$) are exactly the same as nine pixels encompassed by a $3\times 3$ filtering mask in the original image (i.e., $|c_{yx}\rangle$, $|c_{(y-1)x}\rangle$, $|c_{(y+1)x}\rangle$, $|c_{y(x-1)}\rangle$, $|c_{y(x+1)}\rangle$, $|c_{(y-1)(x-1)}\rangle$, $|c_{(y-1)(x+1)}\rangle$, $|c_{(y+1)(x-1)}\rangle$, $|c_{(y+1)(x+1)}\rangle$). Therefore, the median of nine pixels from the same position of the nine images is the grayscale value of the corresponding position of the filtered image. Taking the part of the original image in a $3\times 3$ window as an example, an explanation of the filtering scheme proposed in this paper is given in Fig. 7.

2.6.2 Complete median filtering circuits

For the proposed quantum image median filtering method, the complete quantum circuits are shown in Fig. 8, which consists of three types of modules: 12 Cycle Shift, 16 Comparator, and 1 Median Calculation.

Fig. 8

Complete median filtering circuits

Next, we explain the working process of quantum median filtering circuits as follows. The input of the filtering circuits is nine identical quantum images, as shown in the following equation.

$$\begin{aligned} \left\{ \begin{array}{lcl}|I_1\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_1=0}^{2^n-1}\sum \nolimits _{x_1=0}^{2^n-1}|c_{y_1x_1}\rangle |y_1\rangle |x_1\rangle \\ |I_2\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_2=0}^{2^n-1}\sum \nolimits _{x_2=0}^{2^n-1}|c_{y_2x_2}\rangle |y_2\rangle |x_2\rangle \\ |I_3\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_3=0}^{2^n-1}\sum \nolimits _{x_3=0}^{2^n-1}|c_{y_3x_3}\rangle |y_3\rangle |x_3\rangle \\ |I_4\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_4=0}^{2^n-1}\sum \nolimits _{x_4=0}^{2^n-1}|c_{y_4x_4}\rangle |y_4\rangle |x_4\rangle \\ |I\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y=0}^{2^n-1}\sum \nolimits _{x=0}^{2^n-1}|c_{yx}\rangle |y\rangle |x\rangle \\ |I_5\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_5=0}^{2^n-1}\sum \nolimits _{x_5=0}^{2^n-1}|c_{y_5x_5}\rangle |y_5\rangle |x_5\rangle \\ |I_6\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_6=0}^{2^n-1}\sum \nolimits _{x_6=0}^{2^n-1}|c_{y_6x_6}\rangle |y_6\rangle |x_6\rangle \\ |I_7\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_7=0}^{2^n-1}\sum \nolimits _{x_7=0}^{2^n-1}|c_{y_7x_7}\rangle |y_7\rangle |x_7\rangle \\ |I_8\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_8=0}^{2^n-1}\sum \nolimits _{x_8=0}^{2^n-1}|c_{y_8x_8}\rangle |y_8\rangle |x_8\rangle \end{array}\right. , \end{aligned}$$

(3)

where if $y_ix_i=yx$ then $c_{y_ix_i}=c_{yx}, i=1,2,\ldots ,8$. In other words, these nine images are exactly the same.

First of all, with $|I\rangle$ constant, 12 Cyclic Shift modules are used to perform a cyclic shift operation on the other eight images ($|I_1\rangle \sim |I_8\rangle$) to obtain nine images (one original image and eight shifted images), as shown in the following equation.

$$\begin{aligned} \left\{ \begin{array}{rcl}S_{y-}|I_1\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_1=0}^{2^n-1}\sum \nolimits _{x_1=0}^{2^n-1}|c_{y_1x_1}\rangle |(y_1-1)~mod~2^n\rangle |x_1\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_1=0}^{2^n-1}\sum \nolimits _{\hat{x}_1=0}^{2^n-1}|c_{\hat{y}_1\hat{x}_1}\rangle |\hat{y}_1\rangle |\hat{x}_1\rangle \\ S_{y+}|I_2\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_2=0}^{2^n-1}\sum \nolimits _{x_2=0}^{2^n-1}|c_{y_2x_2}\rangle |(y_2+1)~mod~2^n\rangle |x_2\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_2=0}^{2^n-1}\sum \nolimits _{\hat{x}_2=0}^{2^n-1}|c_{\hat{y}_2\hat{x}_2}\rangle |\hat{y}_2\rangle |\hat{x}_2\rangle \\ S_{x-}|I_3\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_3=0}^{2^n-1}\sum \nolimits _{x_3=0}^{2^n-1}|c_{y_3x_3}\rangle |y_3\rangle |(x_3-1)~mod~2^n\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_3=0}^{2^n-1}\sum \nolimits _{\hat{x}_3=0}^{2^n-1}|c_{\hat{y}_3\hat{x}_3}\rangle |\hat{y}_3\rangle |\hat{x}_3\rangle \\ S_{x+}|I_4\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_4=0}^{2^n-1}\sum \nolimits _{x_4=0}^{2^n-1}|c_{y_4x_4}\rangle |y_4\rangle |(x_4+1)~mod~2^n\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_4=0}^{2^n-1}\sum \nolimits _{\hat{x}_4=0}^{2^n-1}|c_{\hat{y}_4\hat{x}_4}\rangle |\hat{y}_4\rangle |\hat{x}_4\rangle \\ |I\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y=0}^{2^n-1}\sum \nolimits _{x=0}^{2^n-1}|c_{yx}\rangle |y\rangle |x\rangle \\ S_{y-}S_{x-}|I_5\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_5=0}^{2^n-1}\sum \nolimits _{x_5=0}^{2^n-1}|c_{y_5x_5}\rangle |(y_5-1)~mod~2^n\rangle |(x_5-1)~mod~2^n\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_5=0}^{2^n-1}\sum \nolimits _{\hat{x}_5=0}^{2^n-1}|c_{\hat{y}_5\hat{x}_5}\rangle |\hat{y}_5\rangle |\hat{x}_5\rangle \\ S_{y-}S_{x+}|I_6\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_6=0}^{2^n-1}\sum \nolimits _{x_6=0}^{2^n-1}|c_{y_6x_6}\rangle |(y_6-1)~mod~2^n\rangle |(x_6+1)~mod~2^n\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_6=0}^{2^n-1}\sum \nolimits _{\hat{x}_6=0}^{2^n-1}|c_{\hat{y}_6\hat{x}_6}\rangle |\hat{y}_6\rangle |\hat{x}_6\rangle \\ S_{y+}S_{x-}|I_7\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_7=0}^{2^n-1}\sum \nolimits _{x_7=0}^{2^n-1}|c_{y_7x_7}\rangle |(y_7+1)~mod~2^n\rangle |(x_7-1)~mod~2^n\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_7=0}^{2^n-1}\sum \nolimits _{\hat{x}_7=0}^{2^n-1}|c_{\hat{y}_7\hat{x}_7}\rangle |\hat{y}_7\rangle |\hat{x}_7\rangle \\ S_{y+}S_{x+}|I_8\rangle &{}=&{}\frac{1}{2^n}\sum \nolimits _{y_8=0}^{2^n-1}\sum \nolimits _{x_8=0}^{2^n-1}|c_{y_8x_8}\rangle |(y_8+1)~mod~2^n\rangle |(x_8+1)~mod~2^n\rangle \\ &{}=&{}\frac{1}{2^n}\sum \nolimits _{\hat{y}_8=0}^{2^n-1}\sum \nolimits _{\hat{x}_8=0}^{2^n-1}|c_{\hat{y}_8\hat{x}_8}\rangle |\hat{y}_8\rangle |\hat{x}_8\rangle \end{array}\right. .\nonumber \\ \end{aligned}$$

(4)

After completing the image cyclic shift, 16 Comparator modules are used to compare the positions in order to find out the pixels with the same position in the 9 images. Taking Eq. (4) as an example, if ($y=\hat{y}_1=\cdots =\hat{y}_8$) and ($x=\hat{x}_1=\cdots =\hat{x}_8$), then $c_{yx}, c_{\hat{y}_1\hat{x}_1}, \cdots , c_{\hat{y}_8\hat{x}_8}$ are the grayscale value of the nine pixels with the same position. Next, using the output of 16 Comparators as a control condition, a Median Calculation module is executed so as to obtain the median of grayscale value of nine pixels with the same position. Let this median be $\hat{c}_{yx}$, at this point, quantum image $|I\rangle =\frac{1}{2^n}\sum \nolimits _{y=0}^{2^n-1}\sum \nolimits _{x=0}^{2^n-1}|\hat{c}_{yx}\rangle |y\rangle |x\rangle$ is the median filtered image.

2.6.3 Difference between the proposed scheme and classical median filtering scheme

The difference between the scheme proposed in this paper and the classical median filtering scheme is as follows.

First, the classic median filtering is achieved by sliding the median filtering mask over the entire image, and each time the mask moves to a new position, it is necessary to calculate the median of 9 pixels encompassed by it so that all median values are calculated one by one. In the scheme of this paper, with the parallelism of quantum computation, all $2^n\times 2^n$ median calculations involving 9 images are performed simultaneously, which can greatly improve the median filtering efficiency.

Second, for the filtered image, the two schemes are slightly different for the boundary pixels, whereas for the internal pixels, the processing results are exactly the same. In other words, if the boundary pixels are ignored, the filtering effect of the two schemes is exactly the same. When the boundary pixels are considered, the filtering effect is slightly different. This is because the two schemes have different ways of dealing with the boundary pixels. In the classic scenario, the method of replicating boundary pixels is used to extend the original image outward by one pixel unit, turning the boundary pixels into internal pixels, so that a $3\times 3$ filtering mask can be used to calculate the median. In the proposed scheme, all pixels in the image are first circularly shifted by one unit in eight different directions, and then the median of nine pixels with the same position in these shifted images is calculated simultaneously. Therefore, for the scheme proposed in this paper, the boundary pixels and internal pixels are handled in exactly the same way.

2.7 Complexity analysis

In quantum image processing (QIP), the circuit network complexity depends on the number of elementary gates used. The complexity of elementary quantum gates is taken to be unity. This includes the NOT-gate, Hadamard gate, Control-Not gate, and any $2\times 2$ unitary operator [32]. Below, we start by analyzing the complexity of each sub-module and gradually establish the complexity of the entire median filtering circuits.

• Cycle Shift modules. In [17], the Cycle Shift module is used to extract local feature points from quantum images. From the analysis shown in [17], the complexity of this model is no more than $O(n^2)$.

• Comparator module. In [33], this module is used in quantum image translation. From the analysis presented in [33], the complexity of this model is no more than $O(n^2)$.

• Swap module. In this module, q simple quantum swap gates are used (Fig. 4). According to Reference [34], each swap gate can be constructed by three Control-Not gates, and hence, the Swap module requires a total of 3q Control-Not gates, that is, its complexity is O(q).

• Sort module. From Fig. 5, this module consists of only one Comparator module and one Swap module, and hence, the complexity is no more than $O(q^2+q)$. If the lower-order term is ignored, its complexity is about $O(q^2)$.

• Median Calculation module. From Fig. 6, this module consists of 30 Sort modules. From the previous analysis, the complexity of this module does not exceed $O(30q^2)$.

Finally, we analyze the complexity of the entire filtering circuits. As is seen from Fig. 8, the entire filtering circuits employs a total of 12 Cycle Shift modules, 16 Comparator modules, and 1 Median Calculation module. For a quantum image, the color depth q of the image is generally fixed (e.g., for a grayscale image, $q=8$, and for a color image $q=24$), whereas the size n of the image is variable. Therefore, without considering the complexity of the image preparation stage, the total complexity is no more than $O(12n^2+16n^2+30q^2)=O(28n^2+30q^2)$.

In summary, the computational complexity of the proposed filtering scheme is only the second-order polynomial function of image size n. However, for classical median filtering, the median of all pixels needs to be calculated one by one, so the complexity must include the factor $2^{2n}$. In terms of this factor alone, the complexity of classical median filtering is necessarily the exponential function of the image size n.

2.8 Example verification

In this section, we employ a $4\times 4$ grayscale image to illustrate a specific median filtering process. Using the NEQR model of the quantum image, this image can be represented as follows.

$$\begin{aligned} \begin{array}{lll} |Q\rangle &{}\!=\!&{}\!\!\frac{1}{4}(|01101111\rangle \!_2|0,\!0\rangle \!\!+\!\!|10000010\rangle \!_2|0,\!1\rangle \!\!+\!\!|10101100\rangle \!_2|0,\!2\rangle \!\!+\!\!|10011111\rangle \!_2|0,\!3\rangle +\\ &{}&{}~~|01101011\rangle \!_2|1,\!0\rangle \!\!+\!\!|11110011\rangle \!_2|1,\!1\rangle \!\!+\!\!|01000100\rangle \!_2|1,\!2\rangle \!\!+\!\!|01011100\rangle \!_2|1,\!3\rangle +\\ &{}&{}~~|01001001\rangle \!_2|2,\!0\rangle \!\!+\!\!|00100011\rangle \!_2|2,\!1\rangle \!\!+\!\!|10010001\rangle \!_2|2,\!2\rangle \!\!+\!\!|10001010\rangle \!_2|2,\!3\rangle +\\ &{}&{}~~|11101001\rangle \!_2|3,\!0\rangle \!\!+\!\!|01000101\rangle \!_2|3,\!1\rangle \!\!+\!\!|01111001\rangle \!_2|3,\!2\rangle \!\!+\!\!|10110000\rangle \!_2|3,\!3\rangle )\\ &{}=&{}\frac{1}{4}(|111\rangle |0,\!0\rangle \!+\!|130\rangle |0,\!1\rangle \!+\!|172\rangle |0,\!2\rangle \!+\!|159\rangle |0,\!3\rangle +\\ &{}&{}~~~|107\rangle |1,0\rangle +|243\rangle |1,1\rangle +|68\rangle |1,2\rangle +|92\rangle |1,3\rangle +\\ &{}&{}~~~|73\rangle |2,0\rangle +|35\rangle |2,1\rangle +|145\rangle |2,2\rangle +|138\rangle |2,3\rangle +\\ &{}&{}~~~|233\rangle |3,0\rangle +|69\rangle |3,1\rangle +|121\rangle |3,2\rangle +|176\rangle |3,3\rangle ), \end{array} \end{aligned}$$

(5)

Figure 9a, b shows the median filtering process for this $4\times 4$ grayscale image using the proposed method and the classical method, respectively. Note, the thin black lines in the image are used to distinguish pixels and are not part of the image. In Fig. 9(b.iv), the 16 pixels in the blue box are the image filtered by the classical method.

Fig. 9

Median filtering process for a $4\times 4$ grayscale image using the proposed method and the classical method. a Filtering process of proposed method. b Filtering process of classical method

As can be seen from Fig. 9, two filtered images are exactly the same for the four internal pixels and the differences between them are only reflected on the edge pixels.

3 Simulation on classical computer

We now describe simulations of filtering operations for several grayscale images on a classical computer while physical quantum computers are currently not at hand. The simulations were run on a classical computer with an Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz 4.00GB RAM and 32-bit operating system. The simulations are based on linear algebra with complex vectors as quantum states and unitary matrices as unitary transforms with calculations performed using MATLAB 7.8.0(R2009a). The six grayscale images (as shown in Fig. 10) used in the experiment are taken from the web [35]. The size of the first four images is $512\times 512$ and that of the last two images is $1024\times 1024$.

Fig. 10

Six grayscale images used in the experiments

Our experimental procedure is as follows. First, we mixed one of three noise patterns in each image: Gaussian noise with mean 0 and variance of 0.05, salt-and-pepper noise with a density of 0.10, and qubit flip noise with a flipping probability of 0.10. We then used the median filter designed for this study to filter each noise-imposed image. Finally, the noise reduction performance of the median filter is investigated by calculating the correlation coefficient of adjacent pixels, peak signal-to-noise ratio, and the quantum-based image fidelity metric (or simply QIFM) proposed in [36]. To further verify the effectiveness of the proposed method, we also compared the filtering performance of our method with that of the classical median filtering method.

Before beginning, we first explain what qubit flip noise is. qubit flip noise is essentially a channel noise that is caused when information is transmitted in a quantum channel. It is consistent with classic channel noise, i.e., “1” is received when “0” is sent, or “0” is received when “1” is sent. For a quantum image transmitted in a channel, the qubit flip noise transitions the state of the qubit from $|0\rangle$ to $|1\rangle$ (or vice versa) with probability $1-p$, and this action can be described by operators such as $E_0=\sqrt{p}I=\sqrt{p}\left[ \begin{array}{cc}1~&{}~0\\ 0~&{}~1\end{array}\right]$ and $E_1=\sqrt{1-p}X=\sqrt{1-p}\left[ \begin{array}{cc}0~&{}~1\\ 1~&{}~0\end{array}\right]$. With respect to the qubit flip noise used in this experiment, the flip probability $1-p$ is equal to 0.10.

3.1 Comparison of filtering effects under different noise

The filtering effects for Gaussian noise, salt-and-pepper noise, and qubit flip noise are shown in Figs. 11, 12, and 13, respectively.

Fig. 11

Noise reduction effect of the median filter on Gaussian noise with mean 0 and variance of 0.05. ai—avi are images after superimposing the Gaussian noise, bi—bvi are the respective median filtering results for ai–avi using the proposed method, and ci–cvi are the respective median filtering results for ai—avi using the classical method

Fig. 12

Noise reduction effect of median filter on salt-and-pepper noise with a density of 0.10. ai—avi are images after superimposing the salt-and-pepper noise, bi—bvi are the respective median filtering results for ai—avi using the proposed method, and ci—(c)vi are the respective median filtering results for ai—avi using the classical method

Fig. 13

Noise reduction effect of the median filter on qubit flip noise with a flipping probability of 0.10. ai—avi are images after superimposing the qubit flip noise, bi—bvi are the respective median filtering results for ai—avi using the proposed method, and ci—cvi are the respective median filtering results for ai—avi using the classical method

For median filtering, its ability to suppress salt-and-pepper noise and qubit flip noise is better than the ability to suppress Gaussian noise. Especially for salt-and-pepper noise, its suppression ability is stronger than that for qubit flip noise. Although the noise density is as high as 0.1, the filtering effect is still good. From the experimental results, in terms of the visual effect of the filtered image, there are almost no differences between the two methods for the three different types of noise filtering.

We give the following explanation for the above experimental results. Median filtering can completely eliminate isolated pulses. In general, the brighter and darker areas in the image that are smaller than half of the template size are removed after filtering. Therefore, the main function of median filtering is, for those pixels that are significantly different from the surrounding pixels, to change their grayscale values to values closest to those of the surrounding pixels. In this way, its ability to eliminate isolated noise is very strong. Because it is not taking the mean, there is less ambiguity. In other words, the median filter can eliminate noise and better retain image details. Because the qubit flip noise and the salt-and-pepper noise are seen as specks added to the original image, the median filter is very efficient at filtering out these two kinds of noise.

Note that the above comparison is based only on observations with the human visual system. To further strengthen our argument, we give a quantitative comparison of the performance of the two methods in the next subsection.

3.2 Correlation analysis for adjacent pixels

In six original images in Fig. 10, each pixel is highly correlated with its adjacent pixels. The addition of noise reduces the correlation of adjacent pixels, so that the image becomes blurred. After the noise image is filtered by median filtering, the correlation between adjacent pixels can be improved by suppressing noise. To quantify and compare the correlations of the adjacent pixels in the original images, noise images, and filtered images, we also calculated the correlation coefficient $R_{xy}$ of adjacent pixels using the following equation [30].

$$\begin{aligned} R(x,y)=\frac{E((x-E(x))(y-E(y)))}{\sqrt{D(x)D(y)}}, \end{aligned}$$

(6)

where E(x) and D(x) denote the expectation and variance, respectively, of the pixel grayscale values.

To investigate the filtering effect of median filter on noise images, the correlation is tested between two horizontally, vertically, and diagonally adjacent pixels in the six original images, and their corresponding noise and filtered images. Specifically, by randomly selecting 10,000 pairs of adjacent pixels in each direction from the images, the correlation between pixels can be obtained. Let $I_\mathrm{O}$, $I_\mathrm{N}$, $I_\mathrm{F1}$, and $I_\mathrm{F2}$ denote, respectively, the original image, noise image, filtered image by our method, and the filtered image by the classical method. The results of the correlation coefficients for the three directions and six images are listed in Table 1, where $R_X$, $(X=R,S,Q)$ denote the correlation coefficients for Gaussian noise images, salt-and-pepper noise images and qubit flip noise images, respectively.

Table 1 Correlation coefficients for horizontal, vertical, and diagonal pairs of adjacent pixels for the original images and their corresponding noise and filtered images

From Table 1, the addition of noise significantly reduces the correlation of adjacent pixels in the original image, but after the median filter is applied, the correlation is restored to approximately equal to that of the original image. Moreover, from the experimental results, for the first four images, the correlation coefficients obtained by the two approaches are almost equal, while for the last two images, the correlation coefficients obtained by the two approaches are exactly the same.

For the above experimental results, we give the following explanation. For the first four images, each image contains $512\times 512$ pixels, of which the number of boundary pixels is $512\times 4-2=2044$. Therefore, in the 10000 randomly selected pixels, there are no more than $10000\times \frac{2044}{512\times 512}\approx 78$ boundary pixels, indicating that the difference of correlation coefficient between the two schemes does not exceed 0.0078. Similarly, for the last two images, each image contains $1024\times 1024$ pixels, of which the number of boundary pixels is $1024\times 4-4=4092$. Therefore, in the 10000 randomly selected pixels, the number of boundary pixels does not exceed $10000\times \frac{4092}{1024\times 1024}\approx 39$, and so, the difference of correlation coefficient between the two schemes does not exceed 0.0039.

3.3 Visual quality comparison

To describe quantitatively the visual quality of a filtered image, the evaluation index used in this paper is the peak signal-to-noise ratio (PSNR) defined by the following equation [22].

$$\begin{aligned} \mathrm{PSNR}=20\log _{10}\frac{255}{\sqrt{\frac{1}{2^{2n}}\sum \limits _{i=0}^{2^n-1}\sum \limits _{j=0}^{2^n-1}[I_\mathrm{Ori}(i,j)-I_\mathrm{NF}(i,j)]^2}}, \end{aligned}$$

(7)

where $I_\mathrm{Ori}$ and $I_\mathrm{NF}$ denote the original image and the noise or filtered image, respectively.

Obviously, the closer $I_\mathrm{Ori}$ and $I_\mathrm{NF}$ are, the greater the PSNR obtained is. Table 2 shows the PSNR of the different noise images and the corresponding filtered images. Here $P_X$, $P_{X1}$, and $P_{X2}$ ($X=G,S,Q$) denote the PSNR of the X noise image and the corresponding filtered images obtained using the proposed and classical methods.

Table 2 PSNR values of the noise images and their corresponding filtered images (dB)

From Table 2, the PSNR obtained by two filtering schemes is quite close, and after filtering the Gaussian noise, salt-and-pepper noise, and qubit flip noise, the PSNR increased by about 7 dB, 17 dB, and 13 dB according to the statistical average, respectively.

In addition, it can be seen from the average PSNR of 6 images (the last row of Table 2) that the average PSNR obtained by proposed scheme is slightly smaller than that of the classical filtering scheme (specifically, 0.0220 dB less than the classical scheme for Gaussian noise, 0.2904 dB for salt-and-pepper noise, and 0.1854 dB for qubit flip noise). However, the computational efficiency advantage of proposed scheme can completely compensate this slight weakness by means of the parallelism of quantum computation.

3.4 Image fidelity comparison

Although most researchers in the field are content with adopting the classical PSNR image quality measure to assess likeness between two or more quantum images, Iliyasu et al. argued that these available classical metrics are insufficient and/or ill-suited to effectively quantify the fidelity between two or more quantum images [36]. In recent work [37], they proposed a wholly quantum-based QIFM to assess the “likeness” between quantum images. They further perfected this method and showed using a statistical analysis that the QIFM metric gave better correlations with a digital expectation of likeness between images than other available quantum image quality measures [37].

To further verify the validity of our proposed method, we used the QIFM metric proposed in [37] to compare the fidelity of the noise image before and after filtering with respect to the original image. Here, we give a brief outline of the steps in the calculation of QIFM. For a more detailed explanations of the concepts and principles of QIFM, the reader is referred to [37].

First, the reference image $I_\mathrm{R}$ and the test image $I_\mathrm{T}$ can be transformed into their binary versions based on a pixel threshold (p) that assigns a value of zero if $0\le p<127$ and one if $128\le p<255$. Then, binary details between $I_\mathrm{R}$ and $I_\mathrm{T}$ are evaluated using the following equation [37]

$$\begin{aligned} \Gamma =I_\mathrm{DR}-T_\mathrm{DT}, \end{aligned}$$

(8)

where

$$\begin{aligned} I_\mathrm{DR}=\left\{ \begin{array}{ll} \frac{\sum (n_\mathrm{b}^\mathrm{R}-n_\mathrm{w}^\mathrm{R})}{N}; &{} if n_\mathrm{b}^R\ne n_\mathrm{w}^\mathrm{R}\\ \frac{\sum (n_\mathrm{b}^\mathrm{R}-n_\mathrm{w}^\mathrm{R})}{N}+1; &{} \mathrm{otherwise}\end{array}\right. , \\ I_\mathrm{DT}=\left\{ \begin{array}{ll} \frac{\sum (n_\mathrm{b}^\mathrm{T}-n_\mathrm{w}^\mathrm{T})}{N}; &{} if n_\mathrm{b}^\mathrm{T}\ne n_\mathrm{w}^\mathrm{T}\\ \frac{\sum (n_\mathrm{b}^\mathrm{T}-n_\mathrm{w}^\mathrm{T})}{N}+1; &{} otherwise\end{array}\right. . \end{aligned}$$

Here $n_\mathrm{b}^\mathrm{R}$, $n_\mathrm{w}^\mathrm{R}$, $n_\mathrm{b}^\mathrm{T}$, and $n_\mathrm{w}^\mathrm{T}$ denote the number of white (0) and black (1) pixels in the reference and test images, and $N=n\times n$ represents the total pixel size of the image.

Next, we count the number of pixel correspondences, D, in the reference and test image pair defined as the following equation [37]

$$\begin{aligned} D=\sum \limits _{i=0}^{2^n-1}\sum \limits _{j=0}^{2^n-1}(I_\mathrm{R}(i,j)=(I_\mathrm{T}(i,j)), \end{aligned}$$

(9)

and compute the total pixel-wise variation (i.e., discordance) in the pair of reference and test images, $B=\frac{\sum \mathrm{BER}}{8N}$, where BER denotes the bit error rate that is widely used in other engineering and computer science domains.

Finally, the QIFM of the fidelity between the test image and the reference image can be obtained from the following equation [37]

$$\begin{aligned} F=\frac{D+(1-B)\times \Gamma }{N}\times 100. \end{aligned}$$

(10)

Table 3 shows the QIFM values of the different noise images and the corresponding filtered images in which $QF_X$ ($X=G, S, Q$) denotes the QIFM values of the X noise images, and $QF_{X1}$ and $QF_{X2}$ that of the corresponding filtered images obtained by the proposed and classical methods.

Table 3 QIFM values of the noise images and their corresponding filtered images (%)

From Table 3, the QIFM values obtained by two filtering schemes is quite close, and after filtering the Gaussian noise, salt-and-pepper noise, and qubit flip noise, the QIFM increased by about 12.1650%, 3.1920%, and 7.7339% according to the statistical average, respectively.

In addition, similar to the analysis of PSNR in Sect. 3.3, although the QIFM obtained by proposed scheme is slightly smaller than that of the classical filtering scheme (specifically, 0.0189% less than the classical scheme for Gaussian noise, 0.0117% for salt-and-pepper noise, and 0.0234% for qubit flip noise), the computational advantages of the parallelism of quantum computation are enough to make up for this very weak defect.

The experimental results verify the effectiveness of the proposed method in four aspects: the filtering effect under different noise patterns, the correlation analysis of adjacent pixels, the peak signal-to-noise ratio, and the image fidelity. For quantum spatial filtering, the mean filtering cannot be implemented by quantum circuits because it involves convolution. Although the median filtering does not involve convolution, the corresponding quantum version is not reported at present. Therefore, the significance of this study was to explore the quantum realization method of image median filtering in the spatial domain, which to a certain extent solves the spatial filtering problem of quantum images.

4 Conclusions

Filtering has a wide range of applications in image processing. It is usually applied in the early stages of vision processing for image enhancement. For example, it can be used to emphasize various structures in the image prior to a segmentation process (e.g., edges) or to eliminate undesirable characteristics introduced in the acquisition process (e.g., noise). In the classic scenario, the linear spatial filtering is easily implemented by employing convolution or correlation of an image with a mask representing the filter. Unfortunately, quantum computation has been shown to be unable to implement the convolution and correlation operations. However, median filtering is a nonlinear filtering that is independent of convolution or correlation, and it does not involve convolution or correlation calculations at all. This feature provides the feasibility for designing quantum median filter. In this paper, we developed a quantum version for the image median filtering operation. From basic modules designed for the elementary quantum gates, two composite modules designed for purposeful tasks were constructed. These two composite modules were used in forming the complete median filtering circuits. Several specific applications related to spatial filtering (noise elimination) were used to verify the feasibility of the proposed circuits. If only the filtering effect is concerned, the performance of the proposed quantum median filtering scheme is almost the same as that of its classical counterparts. However, with the parallelism of quantum computation, the proposed quantum median filter can greatly improve the filtering efficiency of digital image.