Design and implementation of a multivalued quantum circuit for threshold based color image segmentation

Abstract

Color image segmentation is one of the very useful applications in the field of image processing at present. The main aim of this article is to deal with the application of quantum computation aspects to image processing task. The benefit of using quantum version of its corresponding classical image processing task is the speedup and efficiency. In this article, a circuit level implementation of the quantum multilevel threshold based color image segmentation technique is proposed and designed. Then the prospects of this technique are analyzed on some sample RGB color images. This article deals with the detailed design of quantum based multilevel color image segmentation circuit based on some predefined thresholds. The threshold based quantum circuit is built using the concepts of multivalued quantum parallelism, superposition and quantum oracle. This article also describes how the segmented image can be retrieved from quantum superposition states. Finally a detail comparison of the proposed modified technique with some well-known conventional techniques is discussed in this article.

Keywords

Quantum information quantum image processing quantum superposition quantum computing threshold-based color image segmentation quantum parallelism

1. Introduction

Now a day’s quantum computing and quantum information processing play a revolutionary role on the field of computer science. It has a high impact to build powerful quantum machine using the principles of quantum physics, which leads to the set of important concepts like quantum superposition, parallelism, entanglement, and interference. At present, it is a part of futuristic high performance computing but a set of small quantum systems (2-qubits to 5-qubits) have already been built by the collaboration of “Nutshell, Google, Microsoft” and it is running quite successfully. So the present aim of the researchers is to deal with the various properties (like high speed up, high performance, power saving, reliability) of quantum computing and how these properties are used to increase the performance of some real-time processing like data analysis, computer vision, computer graphics, pattern recognition, machine learning, and image processing fields [2, 22, 27]. Quantum computing research is not bounded by only binary-valued quantum logic, it is also extended to multivalued quantum systems (like ternary quantum system, quaternary quantum system, etc.). Binary quantum system exists in a linear superposition of two basis states, labeled by $|0>$ and $|1>$ . In binary information processing, $|0>$ and $|1>$ qubit states are not only used to store information but also the superposition of $|0>$ and $|1>$ , like

$\displaystyle|\psi>=\alpha|0>+\beta|1>$ (1)

where $\alpha$ and $\beta$ represent probability amplitudes of the basis states in a Hilbert space ( $H=C^{2}$ ) and the probability of storing the information is higher to $|0>$ basis state if $|\alpha|^{2}$ is greater than $|\beta|^{2}$ and vice versa [1, 2]. The basic unit to represent information in binary quantum system is qubit. So the superposition state $|\psi>$ of an n-qubit quantum computer is a unit vector in the Hilbert space of n dimensional and it can be represented as

$\displaystyle|\psi>=\sum_{i=0}^{2^{n}-1}\alpha_{i}|i>$ (2)

where $|\alpha_{i}|^{2}$ represents the probability of getting value $|i>$ . A quantum register is a storage of qubits and a quantum gate is an application of unitary operator (U) over quantum register in state space H [3]. This article uses the extended universal quantum logic to the multivalued domain, where the basic unit of information representation is the qudit. This multivalued logic provides greater flexibility in terms of storage and processing of quantum information and specially provides an alternate way to speed up the quantum computation process [7]. Image processing with the help of quantum computing is one of the very hot research topics to the researchers today but still the work progress in this area is bounded by some fundamental aspects. In this article, some existing quantum color image representation models are represented and analyzed first and then a very new quantum version of threshold based color image segmentation process is introduced in terms of quantum circuitry. This article deals with a implementation of multivalued logic based quantum circuit that accomplishes the task of threshold based image segmentation. To implement the thresholding function for color image segmentation, it takes the help of quantum oracle circuit which actually made of some basic quantum gates and some remarkable quantum properties like quantum superposition, quantum parallelism and so on [9]. As a numerical example, the detail implementation of the quantum circuit and it’s application is experimented on a $3\times 3$ small demo color image. Finally, it also provides an example of applying the quantum segmentation procedure on sample RGB color images (Lena.jpg and Baboon.jpg).

2. Multivalued quantum computing

In multi-valued quantum logic, the unit of information is the qudit. In this article, a 4-dimensional quantum system with the basis states, $|0>$ , $|1>$ , $|2>$ and $|3>$ are used for threshold based color image segmentation process and these basis states are represented in a $4^{n}$ -dimensional Hilbert space, also known as Liouville space in quantum logic. This logic allows us to use quaternary (the basic unit of information for 4-valued quantum logic) based quantum computation and various superoperators which act on n-ququat state [8]. Inspired from the aspects of multivalued logic [3, 7, 8], the superposition state of a ququat can be described by

$\displaystyle|\psi>=\alpha|0>+\beta|1>+\gamma|2>+\delta|3>,|\alpha|^{2}+|\beta% |^{2}+|\gamma|^{2}+|\delta|^{2}=1$ (3)

where $\alpha$ , $\beta$ , $\gamma$ , and $\delta$ represent probability amplitudes of the basis states in a Hilbert space ( $H=C^{4}$ ). Similar to the binary quantum system, a measurement of the ququat yields $|0>$ with probability $|\alpha|^{2}$ , $|1>$ with probability $|\beta|^{2}$ and $|2>$ with probability $|\gamma|^{2}$ and $|3>$ with probability $|\delta|^{2}$ . This ququat based 4-level quantum system is suitable for RGB color image storage, representation, segmentation and for other image processing activities due to its large storage flexibility. Most of the previous approaches mainly deal with binary (2-levels) quantum system, which is suitable for binary or grayscale image processing tasks, where image sizes are generally small [1, 10]. However, here the n-ququat system can hold maximum of $4^{n}$ values simultaneously in its n-size quantum register. In this article, a set of multilevel universal quantum gates are required to build proposed quantum circuit for threshold based color image segmentation.

3. Quantum image representation

In this article, some widely used quantum image representation approaches are explored. Most of them have been proposed using a system of qubits or qutrits. According to the famous Flexible Representation of Quantum Images (FRQI) model [5, 12], images on quantum computers are represented in the form of a normalized state, which captures information about colors ( $|C>$ ) and their corresponding positions ( $|P>$ ) in the images. It states that an image can be represented as

$\displaystyle|I(\theta)>=|C>\otimes\ |P>$ (4) $\displaystyle|I(\theta)>=\frac{1}{2^{n}}\sum_{i=0}^{2^{2n}-1}(\cos\theta_{i}|0% >+\sin\theta_{i}|1>)\otimes|P>$ (5)

where $\theta_{i}\in[0,\pi]$ , $i=0,1,2,\ldots,2^{2n}-1$ and $\theta=\theta_{0},\theta_{1},\ldots,\theta_{2^{2n}-1}$ is the vector of angles encoding colors. There are two parts in the FRQI representation of an image; $\cos\theta_{i}|0>+\sin\theta_{i}|1>$ which encodes the information about colors and $|P>$ that about the corresponding positions in the image, respectively [5, 12].

Srivastava et al. introduced an idea to represent a color image using 2-D quantum states and normalized amplitudes [16]. They have introduced this concept for color images in a binary quantum system. In our work, this concept is used to represent color images for ternary quantum system. Unlike FRQI model, this approach is suitable for color images of any dimension. The storage space for the proposed method would only depend on the image dimensions [16]. The concept of dual representation of a 2-D image by row-location and column location vectors is used here. To represent a pixel location in its 2-D matrix, the tensor product of row-location and column-location vectors are used

$\displaystyle L_{p,q}=|I>_{p}\otimes<J|_{q}$ (6)

where

$\displaystyle|I>_{p}=|i>\otimes^{m}$ (7)

and

$\displaystyle<J|_{q}=|j>\otimes^{n}$ (8)

where $|I>_{p}$ is the row-location vector or the state of $m-\textit{qutrit}$ , $i\in{0,1,2}$ , $m=\textit{log}_{2}M$ and $p$ is the row number of pixel and $<J|_{q}$ is the column location vector or the state of $n-\textit{qutrit}$ , $j\in{0,1,2}$ , $n=\textit{log}_{2}N$ and $q$ is the row number of pixel. $L_{p,q}$ is the 2-D quantum state of a pixel at $p^{th}$ row and $q^{th}$ column using $m-\textit{qubits}$ and $n-\textit{qubits}$ , respectively (Suppose we have $M-\textit{length}$ row location vector with m qutrits and $N-\textit{length}$ column location vector with n qutrits).

To illustrate with an example, a pixel location in terms of 2-D quantum states using row-location and column-location vector for any $3\times 3$ image matrix is given by,

$\displaystyle L_{p,q}^{3\times 3}=\@setsize{\scriptsize}{8pt}{\viipt}{\@viipt}% \begin{bmatrix}|00>\otimes<00|&|00>\otimes<01|&|00>\otimes<02|\\ |01>\otimes<00|&|01>\otimes<01|&|01>\otimes<02|\\ |02>\otimes<00|&|02>\otimes<01|&|02>\otimes<02|\end{bmatrix}$

where 2-qutrit vector is obtained from the single qutrit constituent vectors as follows

$\displaystyle|01>=|0>\otimes|1>=\begin{bmatrix}1\\ 0\\ \par \end{bmatrix}\otimes\begin{bmatrix}0\\ 1\\ \par \end{bmatrix}=(010000000)^{T}$ $\displaystyle|12>=|1>\otimes|2>=\begin{bmatrix}0\\ 1\\ \par \end{bmatrix}\otimes\begin{bmatrix}0\\ 0\\ 1\end{bmatrix}=(000001000)^{T}$

Similarly, we can follow the same representation for other row-location vectors and for the column location vector, it can be represented as $<01|=(010000000)$ , $<12|=(000001000)$ etc. Let $A_{p,q}$ be the amplitude/intensity of the pixel at $p^{th}$ row and $q^{th}$ column and $\alpha_{p,q}$ is the scalar amplitude of the pixel quantum state at $p^{th}$ row and $q^{th}$ column. $\alpha_{p,q}$ can be written as [16]

$\displaystyle\alpha_{p,q}=\frac{\sqrt{A_{p,q}}}{\sqrt{A_{T}^{\textit{MXN}}}}$ (9)

where $A_{T}^{\textit{MXN}}=\sum_{p=1}^{M}\sum_{q=1}^{N}A_{p,q}$ . As for example, the scalar amplitudes for 2-D quantum state for each pixel in images with $3\times 3$ dimension is

$\displaystyle\alpha_{p,q}^{3\times 3}=\frac{1}{\sqrt{A_{T}^{3\times 3}}}\begin% {bmatrix}\sqrt{A_{1,1}}&\sqrt{A_{1,2}}&\sqrt{A_{1,3}}\\ \sqrt{A_{2,1}}&\sqrt{A_{2,2}}&\sqrt{A_{2,3}}\\ \sqrt{A_{3,1}}&\sqrt{A_{3,2}}&\sqrt{A_{3,3}}\end{bmatrix}$

Now we incorporate these structures for complete representation as an image. There is a third kind of model proposed in [19], which states that the color information $C_{i}$ ( $i^{th}$ pixel) in an image is encoded using the basis states of qubits

$\displaystyle|C_{i}>=\sum_{j=0}^{2^{m}-1}\alpha_{ij}|j>$ (10)

where image contains total $2^{m}$ possible colors and the coefficients $\alpha_{ij}$ are used to represent the color of a pixel by means of superposition of all $2^{m}$ possible colors. The quantum register $|R>$ encodes the pixel positions using $2n$ qubits and color using m qubits. So the final quantum image can be represented as

$\displaystyle|Q>=|C>_{m}\otimes|R>_{2n}=\frac{1}{\sqrt{2^{2n}}}\sum_{j=0}^{2^{% m}-1}\sum_{i=0}^{2^{2n}-1}\alpha_{ij}|j>|i>$ (11)

Due to the principle of quantum superposition of states, unlike classical case the different m qubits are used to store the colors of all the pixels in the image. So it uses comparatively much lower memory space than classical case to store an image with $2^{m}$ different color levels. One simple and a new model of color image representation and storage in a ternary (3-levels) quantum system is presented in the article [27].

All these approaches are considered as general multiqudits approaches here. Any one kind of the above image representation techniques can be used for representing color images after analyzing their suitability and appropriateness. In this article, the third type of representation model is used to represent an RGB color image and its segmentation process.

4. Threshold based image segmentation

Image segmentation is a process to classify or cluster an image into some regions for helping us to detect objects or regions of interest separately. Several techniques of image segmentation (region based, edge based, threshold based, data clustering based, etc.) have been proposed to segment an image before recognition or compression. Generally one image is subdivided into several parts based on some features of images like amplitude values of the pixels [1, 13, 17]. Image segmentation has been already performed using some optimal iterations like quantum entropy and pulse-coupled neural network [11]. One of the widely used segmentation technique is thresholding where the changes in the color values of the pixels play a vital role to subdivide an image into different regions. It gets popularity because of its simplicity of implementation, fast computational speed, and intuitive properties [17]. Generally, all the thresholding schemes are based on the assumption of the optimum global threshold values. In the previous works [10, 14], a single level thresholding is applied through quantum circuit where a binary image containing two gray levels, e.g., black and white is classified. This single level thresholding assigned to the pixels based on a condition of the form

$\displaystyle g(x,y)=\begin{cases}L-1,f(x,y)>T\\ 0,f(x,y)\leqslant T\end{cases}$ (12)

where $T$ is the selected threshold lies in between 0 and $L$ (maximum value). The functions $f(x,y)$ and $g(x,y)$ are the input and output images for the pixel position $(x,y)$ . However for the color image segmentation, a multiple thresholding based classification technique is needed [17]. This single level thresholding assigned to the pixels based on a condition of the form

$\displaystyle g(x,y)=\begin{cases}a,T_{1}\leqslant f(x,y)<T_{2}\\ b,T_{2}\leqslant f(x,y)<T_{3}\\ c,T_{3}\leqslant f(x,y)<T_{4}\\ d,f(x,y)\geqslant T_{4}\end{cases}$ (13)

In the above equations, $T_{1}$ will be assumed as an initial value of a pixel and $a, b, c$ and $d$ will be assumed as a red, green, blue and background (white) color values of a pixel in the RGB color image respectively. Several works on multilevel thresholding based image segmentation have been already done in the classical computing [4, 6]. In those techniques, firstly the basic optimum thresholding is used on the input color image based on the three primary colors R, G and B. After primary segmentation of the image, the data fusion rule is applied, where the resulting images are integrated by selecting the optimal threshold in each image.

5. Quantum circuit for threshold based color image segmentation

In order to build a quantum circuit for threshold-based color image segmentation, it is required to implement a quantum version of the multilevel thresholding function. To apply this thresholding process to all the pixels of a color image simultaneously, the principle of quantum parallelism must be exploited. Quantum parallelism helps quantum computers to evaluate $f(x)$ for many different values of $x$ simultaneously. According to the process, if a binary function ranges (0,1) is computed on a quantum computer, then it considers a two qubit quantum computer initially in the state of $|x,y>$ . Where $|x>$ is the data register and $|y>$ is the target register. So function $f$ is applied and evaluated by the help of unitary transformation $U_{f}$ defined by $|x,y\oplus f(x)>$ , where $\oplus$ indicates addition modulo 2 operator. So a quantum version of function f can be computed using the unitary transformation $U_{f}$ , which is called quantum oracle or quantum black box [15]. This procedure can easily be generalized to functions on an arbitrary number of bits by applying n-Hadamard gates acting in parallel on n qubits. In proposed approach instead of using qubits, qudits or ququat play the central role to prepare the data register in a superposition of states by applying Hadamard gates on $|0>$ , $|1>$ , $|2>$ , $|3>$ and followed by $U_{f}$ . The resulting state is

$\displaystyle|\psi>=\frac{1}{\sqrt{4}}(|0>|f(0)>+|1>|f(1)>{}+|2>|f(2)>+|3>|f(3% )>)$ (14)

Figure 1.

Multilevel thresholding based color regions division.

Figure 2.

Quantum circuit to represent threshold based segmentation of a RGB color image.

In order to apply function $f$ , the information $f(0)$ , $f(1)$ , $f(2)$ and $f(3)$ can be obtained. In this approach, the final superposition state must be processed further to achieve the parallelism effectively. Exploiting the quantum parallelism property, a multilevel thresholding $f$ is described as $F:(0,1,2,\ldots,2^{m+2n}-1)\rightarrow(0,1,2,3)$ , where $m$ represents the color information and $n$ represents the positions of pixels in an color image. This multilevel thresholding function $f$ is applied in the form of oracle operator $U_{f}$ on the state $|Q>\otimes|0>|1>|2>|3>$ , where $|Q>$ is the quantum image and operator $U_{f}$ can be built with

$\displaystyle f(q)=\begin{cases}0,\text{if }T_{1}\leqslant q<T_{2}(\text{Red % pixels})\\ 1,\text{if }T_{2}\leqslant q<T_{3}(\text{Green pixels})\\ 2,\text{if }T_{3}\leqslant q<T_{4}(\text{Blue pixels})\\ 3,q\geqslant T_{4}(\text{White pixels})\end{cases}$ (15)

The pictorial representation of the above multilevel threshold based color region splitting is given in Fig. 1. In the above equation, the $q$ is the coding representation of color bits $(C_{m})$ and position bits $(P_{2n})$ of the pixels $(q=C_{m-1}C_{m-2}\ldots C_{0}P_{2n-1}P_{2n-2}\ldots P_{0})$ and $T_{1}$ , $T_{2}$ , $T_{3}$ and $T_{4}$ are the multilevel segmentation thresholds. For sake of simplicity, $T_{1}$ is assumed as an initial threshold value start at 0 and the other threshold values with white background are also assumed here. The quantum circuit for threshold based color image segmentation is presented in Fig. 2. According to Fig. 2, $|Q_{in}>$ represents a set of quantum states of the input image, multilevel threshold function $|T>=|T_{1}>|T_{2}>|T_{3}>|T_{4}>$ is implemented through Quantum oracle $(U_{f})$ , $|I_{0}>$ , $|I_{1}>$ , $|I_{2}>$ , $|I_{3}>$ represent different intermediate states of each step of the computation and $|Q_{\text{out}}>$ represents quantum state of the output image. The input state $|I_{0}>$ is represented by the input image, oracle qudits and ancilla qudits:

$\displaystyle|I_{0}>=|1>^{\otimes m}|0>^{\otimes m}|2>^{\otimes m}|3>^{\otimes m% }|T>_{m}|Q_{in}>_{m+2n}|0>|1>|2>|3>$ (16)

where $|T>$ is combination of multilevel thresholds stored in a $m$ -qubit register and $|Q_{in}>$ holds the quantum image represented using $m+2n$ qubits. The quantum image $|Q_{in}>$ can be interpreted as a superposition of four states, one state represents background pixel having white color values $|Q_{in}^{bg}>$ and the other three states represent segmented objects with red, green, and blue color levels, like $|Q_{in}^{R}>$ , $|Q_{in}^{G}>$ and $|Q_{in}^{B}>$ . It can be represented as

$\displaystyle|Q_{in}>=\sqrt{\frac{2^{2n}-(t_{2}-t_{3})}{2^{2n}}}|Q_{in}^{R}>{}% +\sqrt{\frac{2^{2n}-(t_{1}-t_{3})}{2^{2n}}}|Q_{in}^{G}>{}+\sqrt{\frac{2^{2n}-(% t_{1}-t_{2})}{2^{2n}}}|Q_{in}^{B}>{}+\sqrt{\frac{t_{3}}{2^{2n}}}|Q_{in}^{Bg}>$ (17)

where

$\displaystyle|Q_{in}^{R}>=\frac{1}{\sqrt{2^{2n}-(t_{2}-t_{3})}}\sum_{y=0}^{2^{% n}-1}\sum_{x=0}^{2^{n}-1}\sum_{j=T_{1}}^{T_{2}}\alpha_{\textit{yxj}}|j>|y>|x>$ (18) $\displaystyle|Q_{in}^{G}>=\frac{1}{\sqrt{2^{2n}-(t_{1}-t_{3})}}\sum_{y=0}^{2^{% n}-1}\sum_{x=0}^{2^{n}-1}\sum_{j=T_{2}}^{T_{3}}\alpha_{\textit{yxj}}|j>|y>|x>$ (19) $\displaystyle|Q_{in}^{B}>=\frac{1}{\sqrt{2^{2n}-(t_{1}-t_{2})}}\sum_{y=0}^{2^{% n}-1}\sum_{x=0}^{2^{n}-1}\sum_{j=T_{3}}^{T_{4}}\alpha_{\textit{yxj}}|j>|y>|x>$ (20) $\displaystyle|Q_{in}^{Bg}>=\frac{1}{\sqrt{t_{3}}}\sum_{y=0}^{2^{n}-1}\sum_{x=0% }^{2^{n}-1}\sum_{j=T_{4}}^{2^{m}-1}\alpha_{\textit{yxj}}|j>|y>|x>$ (21)

In the above equations, $t_{1}$ , $t_{2}$ and $t_{3}$ are the number of red, green and blue object pixels respectively. According to the Fig. 2, the oracle operator $U_{f}$ is applied on this superposition and produces state $|I_{1}>$ , the intermediate state $|I_{1}>$ can be interpreted as a superposition of four states:

$\displaystyle|I_{1}>=|1>^{\otimes m}|0>^{\otimes m}|2>^{\otimes m}|3>^{\otimes m% }|T>(|Q_{in}^{R}>|0>+|Q_{in}^{G}>|1>{}+|Q_{in}^{B}>|2>+|Q_{in}^{Bg}>|3>)$ (22)

Now, oracle qubit is used to make a distinction among the four states. From Fig. 2, it is seen that the Fredkin gates (it is three qubit cswap gate that swaps the first and second qubit states if and only if third qubit is in state $|1>$ ) are used to set the state of the color register to $|0>^{\otimes m}$ for representing red color if the oracle qubit is $|0>$ , $|1>^{\otimes m}$ for representing green color if the oracle qubit is $|1>$ , $|2>^{\otimes m}$ for representing blue color if the oracle qubit is $|2>$ and so on.

$\displaystyle|I_{2}>=|1>^{\otimes m}|0>^{\otimes m}|2>^{\otimes m}|T>\sqrt{% \frac{t_{3}}{2^{2n}}}|Q_{in}^{Bg}>|3>+|C^{R}_{\textit{obj}}|0>^{\otimes m}|T>% \sqrt{\frac{2^{2n}-(t_{2}-t_{3})}{2^{2n}}}|Q^{R}_{\textit{out}}>|0>)$ (23) $\displaystyle|I_{3}>=|1>^{\otimes m}|0>^{\otimes m}|2>^{\otimes m}|T>\sqrt{% \frac{t_{3}}{2^{2n}}}|Q_{in}^{Bg}>|3>+|C^{G}_{\textit{obj}}|1>^{\otimes m}|T>% \sqrt{\frac{2^{2n}-(t_{1}-t_{3})}{2^{2n}}}|Q^{G}_{\textit{out}}>|1>)$ (24) $\displaystyle|I_{4}>=|1>^{\otimes m}|0>^{\otimes m}|2>^{\otimes m}|T>\sqrt{% \frac{t_{3}}{2^{2n}}}|Q_{in}^{Bg}>|3>+|C^{B}_{\textit{obj}}|2>^{\otimes m}|T>% \sqrt{\frac{2^{2n}-(t_{1}-t_{2})}{2^{2n}}}|Q^{B}_{\textit{out}}>|2>)$ (25)

where

$\displaystyle|Q_{\textit{out}}^{R}>=\frac{1}{\sqrt{2^{2n}-(t_{2}-t_{3})}}\sum_% {y=0}^{2^{n}-1}\sum_{x=0}^{2^{n}-1}|0>^{\otimes m}|y>|x>$ (26) $\displaystyle|Q_{\textit{out}}^{G}>=\frac{1}{\sqrt{2^{2n}-(t_{1}-t_{3})}}\sum_% {y=0}^{2^{n}-1}\sum_{x=0}^{2^{n}-1}|1>^{\otimes m}|y>|x>$ (27) $\displaystyle|Q_{\textit{out}}^{B}>=\frac{1}{\sqrt{2^{2n}-(t_{1}-t_{2})}}\sum_% {y=0}^{2^{n}-1}\sum_{x=0}^{2^{n}-1}|2>^{\otimes m}|y>|x>$ (28)

5.1 Numerical example multilevel threshold based quantum color image segmentation

In order to better understanding, the above procedure is applied on a $3\times 3$ demo color image with nine possible color variations and the state of the quantum system at each step is numerically described here. Suppose, a $3\times 3$ color image is considered in Fig. 3 and according to Fig. 1, $T_{1}=0(|00>)$ , $T_{2}=2(|02>)$ , $T_{3}=4(|11>)$ and $T_{4}=6(|20>)$ are used for the multilevel segmentation thresholds.

Figure 3.

Example of a $3\times 3$ color Image.

Figure 4.

Quantum comparator circuit operates on four qubit states $|a>$ , $|b>$ , $|c>$ and $|d>$ .

In the Fig. 3, first cell represents red color, second cell represents green color, third cell represents blue color, fourth cell represents (red $+$ green) yellow color, fifth cell represents (red $+$ blue) purple color, sixth cell represents (green $+$ blue) magenta color, seventh cell represents white color, eight cell represents (red $+$ white) pink color and ninth cell represents (green+white) light green color. Thus, the input state $|I_{0}>$ is

$\displaystyle|I_{0}>=|00>|11>|22>|33>|02>|11>|20>\frac{1}{\sqrt{2^{3}}}(|0000>% +|1101>{}+|2202>+|0110>)+|0211>{}+|1212>+|3320>+|0321>{}+|1322>)|0>|1>|2>|3>$ (29)

Applying oracle operator ( $U_{f}$ ) on the above input image state

$\displaystyle|I_{1}>=|00>|11>|22>|33>|02>|11>|20>\frac{1}{\sqrt{2^{3}}}(|0000>% |0>+|1101>|1>+|2202>|2>+|0110>|0>|1>+|0211>|0>|2>+|1212>|1>|2>+|3320>|3>+|0321% >|0>|2>+|1322>|1>|3>)$ (30)

In order to implement the quantum circuit for the oracle operator, a modified quantum bit string comparator [18, 20] is needed that compares among four quantum states. The unitary evolution, $U_{\textit{CMP}}$ of a four quantum states comparator can be described by

$\displaystyle U_{\textit{CMP}}|a>|b>|c>|d>|0>^{\otimes p}|0>|0>$ $\displaystyle|0>|0>=|a>|b>|c>|d>|\psi>|x>$ $\displaystyle|y>|z>|w>$ (31)

This comparator uses $p+4$ ancillae, p-qubit registers $|a>$ , $|b>$ , $|c>$ and $|d>$ contain the compared states and $|x>,|y>,|z>$ and $|w>$ carry the comparison result.

if $a=b=c=d$ , then $x=y=z=w=0$ else if $a>b>c>d$ , then $x=1,y=0,z=0,w=0$ else if $b>a>c>d$ , then $x=0,y=1,z=0,w=0$ else if $c>a>b>d$ , then $x=0,y=0,z=1,w=0$ else $a<b<c<d$ , then $x=1,y=0,z=0,w=1$ .

Figure 4 presents a quantum comparator circuit, which can compare among four quantum states ( $|0>$ , $|1>$ , $|2>$ , $|3>$ ) with any number of qubits in straightforward fashion. Now the oracle operator $U_{f}$ can be implemented using the quantum comparator operator that flips the oracle qubits,

if $T_{1}(0)\leqslant C_{R}(|a>)<T_{2}(2)$ ( $U_{\textit{CMP}}^{1}$ ) else if $T_{2}(2)\leqslant C_{G}(|b>)<T_{3}(4)$ ( $U_{\textit{CMP}}^{2}$ ) else if $T_{3}(4)\leqslant C_{B}(|c>)<T_{4}(6)$ ( $U_{\textit{CMP}}^{3}$ ) else $C_{Bg}(|d>)\geqslant T_{4}(6)$ ( $U_{\textit{CMP}}^{4}$ )

According to the above conditions the total quantum comparator circuit of $U_{f}$ is divided into four sub-circuits $U_{\textit{CMP}}^{1}$ , $U_{\textit{CMP}}^{2}$ , $U_{\textit{CMP}}^{3}$ and $U_{\textit{CMP}}^{4}$ and they are shown in Fig. 5. Finally, Fig. 6 represents the entire quantum comparator circuit $U_{\textit{CMP}}$ . These sub-circuits can be represented as

$\displaystyle U_{\textit{CMP}}|a>|b>|c>|d>|0>^{\otimes p}|0>|0>$ $\displaystyle=|a>|b>|c>|\psi>|x>|y>$ (32)

where $U_{\textit{CMP}}^{1}$ is built, when $c>a$ , then $x=1,y=0$ ( $|x>=|a^{\prime}\wedge c>$ ) and when $b>c$ , then $x=0,y=1$ ( $|y>=|c^{\prime}\wedge b>$ ). The similar logic is applicable for other sub-circuits and similar quantum circuit for $U_{\textit{CMP}}^{3}$ can be drawn.

Figure 5.

Quantum comparator sub-circuits.

Figure 6.

Implementation of the oracle operator $U_{f}$ representing RGB color levels using multilevel thresholds.

5.2 Retrieving a segmented image from a quantum system

In quantum image processing, the resulting image stored in the form of quantum state. However, unlike classical image retrieval process, the final quantum state $|Q_{\textit{out}}>$ of the quantum segmented image can be retrieved by applying the appropriate measurement operators (like Projective measurements or Von-Neumann measurements). The quantum register is generally used to store the quantum image superposition state. This superposition state collapses to one of its basis states. So, multiple copies needs to be prepared to retrieve the whole image from a superposition state. However, in this article the color of a pixel is encoded using the combination of computational basis states. So, in this quantum scheme, a deterministic retrieval process is allowed to retrieve color information for each pixel position in the image. It states that the result of measuring the color register for a given pixel position corresponds to the pixel color with unit probability. The famous FRQI approach encodes the color of a pixel using the angle parameter of a qubit state [12], however projective measurements are applied on a finite number of identical copies to estimate the color of a pixel. Note that there is a chance of uncertainty due to the probabilistic nature of quantum measurements.

The main idea of projective measurement is based on some projection operators in quantum measurement theory that gives the possibility of a system state among a set of mutually exclusive possible states. A projection operator $P$ is hermitian in nature, $P=P^{\dagger}$ . Now let the dimension of the system be $n$ and consider a set of mutually orthogonal projection operators $P_{1}$ , $P_{2}$ , $P_{3}$ , …, $P_{n}$ . Let the system be prepared in a state $|\psi>$ . The probability of finding the $i^{th}$ outcome when a measurement is made [21] is

$\displaystyle Pr(i)=|P_{i}|\psi>|^{2}=(P_{i}|\psi>)^{\dagger}(P_{i}|\psi>)=<% \psi|P_{i}^{2}|\psi>=<\psi|P_{i}|\psi>$ (33)

Next consider some observable set of projection operators, which we denote by $K$ , and let the eigenvectors of $K$ be denoted with eigenvalue $k$ . The spectral decomposition of $K$ allows us to write the operator as, $K=\sum_{i=1}^{n}kP_{i}$ . The probability to measure a quantum state $|\psi>$ is denoted by Eq. (5.1). However, the post-measurement state is

$\displaystyle|\psi^{{}^{\prime}}>=\frac{P_{i}|\psi>}{\sqrt{<\psi|P_{i}|\psi>}}$ (34)

The expectation value or average of an observable K with respect to a state $|\psi>$ is given by

$\displaystyle\textit{Exp}(K)=\sum_{k=1}^{n}<\psi|kP_{k}|\psi>$ (35)

However, the basic representation of a quantum color image is given in Eq. (10). A classical image can be retrieved from a quantum state is described below and the idea of retrieving it from its corresponding superposition states is achieved from [10],

Initialize the classical image matrix with the value of $-$ 1, $im(y,x)=-1$ , for all $0\leqslant y$ and $x<2^{n}$ .

LOOPING:

Equation (10) describes, $|Q>=|C>_{m}\otimes|R$ $>_{2n}=\frac{1}{\sqrt{2^{2n}}}\sum_{j=0}^{2^{m}-1}\sum_{i=0}^{2^{2n}-1}\alpha_% {ij}|j>|i>$ . where $|Q>$ is the quantum image state, $|C>$ is the color quantum state of pixels and $|R>$ is the quantum state for pixel’s position.

Now measure the position register using projective measurement, $K_{\textit{pos}}=I^{\otimes m}\otimes\sum_{k=0}^{2^{2n}-1}kP_{k}=I^{\otimes m}% \otimes\sum_{k=0}^{2^{2n}-1}k|k><k|$ . Then, the post measurement state of the image register is $|Q^{\prime}>=|C_{k}>\otimes|k>=\sum_{j=0}^{2^{m}-1}\alpha_{kj}|j>|k>.$

If condition 1 for image matrix is not satisfied then go to step 3.

Now projective measurement is used to measure the color register, $K_{\textit{col}}=\sum_{r=0}^{2^{m}-1}rP_{r}=\sum_{r=0}^{2^{m}-1}r|r><r|$ . The value is, $<C_{k}|K_{\textit{col}}|C_{k}>$ $=\sum_{r=0}^{2^{m}-1}|\alpha_{kr}|^{2}r=\textit{color}_{k}$ ( $\alpha_{kr}$ is 1 if $r=\textit{color}_{k}$ and 0 otherwise).

Update the existing image matrix $im(y,x)$ using the $\textit{color}_{k}$ .

Until, $im(y,x)\neq-1$ for all $0\leqslant y$ and $x<2^{n}$ .

The probability of reading result k in step 4 is $p(k)=<P|P_{k}|P>=\frac{1}{n}$ for $0\leqslant k<N,N=2^{2n}$ . It corresponds to a problem of random sampling with replacement: The same quantum superposition state is measured; each measurement produces result $k$ out of $N$ possible results with a fixed probability $p(k)$ , independent of all past events. Let $T(p)$ denote the number of samples needed to complete the collection of all possible $N$ results, where $p=(p(0),p(1),\ldots,p(N-1))$ is the sample probability vector. The expectation value for $T(p)$ in the equally likely case, i.e., $p=(1,1,\ldots,1)/N$ , is [23, 24]

$\displaystyle\textit{Exp}[T(p)]=NH_{N}$ (36)

where $H_{N}$ denotes the $N^{th}$ Harmonic number, i.e. $H_{N}=\sum_{k=1}^{n}\frac{1}{k}$ . Thus, the time complexity required to retrieve the whole image is $O(N\textit{ log }N)$ , and exponential in the number of qubits in the position register, $O(2^{n})$ .

5.3 Benefits of quantum image segmentation with result and cost analysis

Figure 7.

Original Lena RGB color image.

Figure 8.

Thresholded test Lena image after exercising proposed technique for multi-level thresholding.

Figure 9.

Original Baboon RGB color image.

Figure 10.

Thresholded test Baboon image after exercising proposed technique for multi-level thresholding.

Figure 11.

Segmented color image based on RGB objects using multilevel thresholds.

Figure 12.

Statistical analysis among various execution times of proposed quantum technique with other well known techniques over Lena and Baboon tested images.

Table 1

Results obtained for proposed modified quantum multilevel thresholding of color images

Image types	$\theta_{R}$	$\theta_{G}$	$\theta_{B}$	$t_{\textit{Proposed}}$	$t_{\textit{QIPSO}}$ [25]	$t_{\textit{QIDE}}$ [25]	$t_{\textit{Classical}}$
Lena	167	140	131	24.45	25.32	86.28	28.75
Baboon	160	150	130	21.55	23.5	82.37	26.65

The proposed quantum segmentation technique is applied on a set of color images in this section. The images in Figs 7 and 9 are original RGB color images of size $<480\times 640\times 3\textit{ uint }8>$ . In this approach, the proposed quantum segmentation technique is implemented and applied on these original images in Matlab environment. The oracle operator $U_{f}$ is applied on the ( $m+2n$ ) qudits of image, which is stored in the color quantum register. However, to implement the multilevel thresholding function for the color image segmentation, this proposed approach uses the logic of quantum oracle or quantum black box. More specifically, this complex quantum oracle circuit is built using a quantum string comparator, some basic quantum gates and a set of fredkin gates that are used to swap the color of the pixels with the various color values (RGB) of different ranges. However, the practical implementation including cost of this entire circuit and its computational complexity provides an important impact on the performance of the overall process. For sake of simplicity, we assume that the threshold oracle takes O(1) time to perform its operations, then the overall complexity of the proposed quantum approach with measurements is $O(\textit{nlogn})$ , where n is the total number of pixels present in the image. Whereas, in amplitude amplification scheme for histogram based image segmentation technique [1] requires $O(\sqrt{nt})$ including retrieval of $t$ object pixels. Our proposed approach requires only the estimation of the initial threshold values not the number of object pixels like the amplitude amplification model for image segmentation [1]. Actually, the segmentation operation is normally using as a part of several computational processes that extracts some important information about the image, e.g., the edge detection of the objects in the image, object detection and recognition from the image etc. The proposed approach is advantageous over the general classical threshold based segmentation approach in terms of speedup. In classical image processing, each pixel’s color is compared with the threshold in a sequential fashion which increase complexity for the classical algorithm. The main cause for this increasing overall speedup is to incorporate inherent quantum parallelism with the superposition states. So in this article, the proposed quantum image segmentation algorithm uses quantum parallelism to perform better than their classical counter parts.

The cost of the quantum comparator sub-circuits [18] in Fig. 5 are $U_{\textit{CMP}}^{1}=5+5+1+1=12$ , $U_{\textit{CMP}}^{2}=12$ , $U_{\textit{CMP}}^{3}=12$ and $U_{\textit{CMP}}^{4}=5+1=6$ and the total cost of quantum oracle from Fig. 6 is, $U_{f}=5+5+5+5+1+1+1+1+5+1=30$ . The cost of implementing quantum oracle is independent on the size of the input image. The statistical analysis of the various execution times (Table 1) has been shown in Fig. 12.

The proposed modified quantum segmentation technique for multilevel thresholding of color images has been examined on the Lena test image(intensity ranges varies in [55,255] for red component, in [0,245] for green component and in [35,225] for blue component) which has a dimension of $512\times 512$ . The original Lena test image is shown in Fig. 7. The optimal threshold values for Lena image are considered as 167, 140 and 131 for red, green and blue components respectively after 10 runs. The similar proposed technique is tested on the Baboon ( $512\times 512$ ) image, where the optimal threshold values are considered as 160, 150 and 130. Table 1 includes the optimal threshold values as $\theta_{R}$ $\theta_{G}$ , and $\theta_{B}$ for both the images. Table 1 also shows the required execution times (in seconds)for our proposed approach, existing QIPSO and the classical segmentation approach respectively. This execution time $t_{\textit{Proposed}}$ is the average result of the 10 best runs on the Lena and Baboon test images. The result is solely analysed on the basic Window 7 (64 bit) OS, Intel (R) Core (TM) i3, 2.89 GHz processor and 2 GB RAM. So, the simulation results with the proposed quantum image segmentation technique are shown in Figs 8, 10, and 11 that is similar with the result obtained in classical approach.

6. Compared with some well-known conventional techniques

i
This proposed quantum color image segmentation technique is presented here using a detailed quantum circuit level implementation. The proposed circuit uses a quantum oracle and a quantum comparator sub-circuits to build the entire model. It also applies some basic principles of quantum mechanics and quantum computing with it. The other conventional techniques [1, 4, 25, 26] do not show the circuit level implementation for multi-threshold based color image segmentation. This quantum circuit is first of its own kind.
ii
Compare to classical histogram based image segmentation technique, which requires $O(\sqrt{nt})$ processing time [1], whereas our proposed quantum technique requires $O(\textit{nlogn})$ time to complete, where n is the number of pixels in the image (Assume that the threshold oracle takes O(1) time to perform its operations).
iii
This proposed technique gives quantum states of the segmented images as an output which helps to develop other image processing operations in future with ease, whereas some technique [6] gives the positions of the object pixels as outputs.
iv
The algorithm devised in these articles [25, 26] are hybrid quantum based multi-level thresholding algorithms. It is a combination of classical selection and quantum inspired processes. The overall time complexity of QIPSO algorithm [25] is $O(U\times M\times Gen)$ , where $U$ defines the total size of population of the red, green and blue particles, $M$ denotes the length of each particle according to the width and height of the image, Gen defines the number of generations to be executed. Whereas our proposed technique occupies less time than that due to use of a powerful quantum phenomena, i.e. quantum parallelism (a statistical comparison is shown in Fig. 12).
v
In terms of execution time our proposed technique performs better than the other conventional threshold based image segmentation techniques. It has been already shown in Table 1 of this article.

7. Conclusions

In this article, a quantum view of the multilevel thresholds based color image segmentation is proposed, presented, and measured. The entire procedure is described using qudit based multivalued quantum logic, which is suitable for RGB color image segmentation procedure. In order to build the quantum circuit, it takes the help of quantum superposition, quantum parallelism and quantum oracle techniques. In this article, multilevel thresholding is implemented using qubit string comparator and also illustrated using a simple $3\times 3$ demo color image example. This procedure gives the output as a set of quantum states, that is why any other image processing operations may be also applied to this output quantum states with ease. The disadvantage of this work is that the threshold values must be given prior to the experiment. So the threshold value can be evaluated or it can be provided by the user at prior. Based on optimal threshold values of three different color components of the selected Lena and Baboon images, the execution time of the proposed method have been reported and compared with other existing techniques. However, a quantum version of automatic clustering-based image thresholding technique (like Otsu’s method) can be used to calculate the initial thresholds in future. So, it can conclude that further development of the Quantum Image Processing field can provide a great impact on the overall backbone of the quantum information processing.

References

Caraiman

Manta

. Histogram-based segmentation of quantum images, Theoretical Computer Science, vol. 529, no. 2, pp. 46-60, 2014.

Nielsen

Chuang

. Quantum Computation and Quantum Information, Cambridge University Press, ISBN-13: 978-0521635035, 2010.

Lipton

Regan

. Quantum Algorithms via Linear Algebra, The MIT Press, Cambridge, Massachusetts, ISBN: 9780262323550, 2014.

Harrabi

Braiek

. Color Image Segmentation by Multilevel Thresholding using a Two Stage Optimization Approach and Fusion, International Journal of Engineering and Innovative Technology, vol. 3, no. 1, pp. 14-20, 2014.

Ostaszewski

PSM

Gawron

. Quantum image classification using principal component analysis, Theoretical and Applied Informatics, vol. 27, no. 1, pp. 1-12, 2015.

Harrabi

Braiek

. Color image segmentation using multi-level thresholding approach and data fusion techniques: application in the breast cancer cells images, EURASIP Journal on Image and Video Processing, vol. 11, no. 5, pp. 1-11, 2012.

Muthukrishnan

CRSA

. Multi-Valued Logic Gates for Quantum Computation, arXiv: quant-ph/0002033v2, pp. 1-8, 2008, Available: http://cds.cern.ch/record/426611/files/0002033.pdf.

Tarasov

. Quantum computer with mixed states and four-valued logic, Journal of Physics A: Mathematical and General, vol. 35, no. 13, pp. 5207-5235, 2002.

Caraiman

Manta

. Quantum Image Filtering in the Frequency Domain, Advances in Electrical and Computer Engineering, vol. 13, no. 2, pp. 77-84, 2013.

10.

Caraiman

Manta

. Image segmentation on a Quantum Computer, Quantum Information Processing, vol. 14, no. 1, pp. 1693-1715, 2015.

11.

Yan

. Effective and fully automatic image segmentation using quantum entropy and pulse coupled neural networks, Sixth International Conference on Graphic and Image Processing (ICGIP), SPIE, Beijing, China, vol. 9443, pp. 366-375, 2014.

12.

Dong

Hirota

. A flexible representation of quantum images for polynomial preparation, image compression, and processing operations, Quantum Information Processing, vol. 10, no. 1, pp. 63-84, 2011.

13.

Wang

. Image representation and processing using ternary quantum computing, In: Tutorial: Image Segmentation. National Taiwan University Press, 2010.

14.

Caraiman

Manta

. Image Processing Using Quantum Computing, 16th IEEE International Conference on System Theory, Control and Computing, Sinaia, Romania, pp. 387-391, 2012.

15.

Caraiman

Manta

. Image Representation and Processing Using Ternary Quantum Computing, 11th International Conference on Adaptive and Natural computing Algorithms, Lausanne, Switzerland, pp. 366-375, 2013.

16.

Srivastava

PKPM

Moulick

. Quantum Image Representation Through Two-Dimensional Quantum States and Normalized Amplitude, arxivorg/pdf/13052251, 2015, Available: https://arxiv.org/pdf/1305.2251.pdf.

17.

Gonzalez

Woods

. Image Segmentation, In: Digital Image Processing, Prentice Hall, Pearson Education India, ISBN: 9780131687288, 2009.

18.

Oliveira

Ramos

. Quantum bit string comparator: circuits and applications, Quantum Computers and Computing, vol. 7, no. 1, pp. 17-26, 2007.

19.

Zhang

. NEQR: a novel enhanced quantum representation of digital images, Quantum Information Processing, vol. 12, no. 5, pp. 2833-2860, 2013.

20.

Zadeh

Haghparast

. A new reversible/quantum ternary comparator, Australian Journal of Basic and Applied Sciences, vol. 5, no. 12, pp. 2348-2355, 2011.

21.

McMahon

. “Quantum Computing Explained”, Published by John Wiley and Sons, ISBN: 978-0-470-09699-4, 2008.

22.

Chakraborty

Dey

. Image Representation, Filtering, and Natural Computing in a Multivalued Quantum System, Handbook of Research on Natural Computing for Optimization Problems, IGI-Global, 2016.

23.

Leung

. Quantum computation by measurements. Int. J. Quantum Inf., vol. 2, no. 01, pp. 33-43, 2004.

24.

Lanzagorta

Uhlmann

. Hybrid quantum computing: semicloning for general database retrieval, Proceedings of SPIE 2005: Quantum Information and Quantum Computation Conference, vol. 5815, Orlando, Florida, USA, pp. 78-86, 2005.

25.

Dey

Bhattacharyya

Maulik

. Quantum Inspired Meta-heuristic Algorithms for Multi-level Thresholding for True Colour Images, Annual IEEE India Conference (INDICON), India, pp. 1-6, 2013.

26.

Dey

Bhattacharyya

Maulik

, New quantum inspired tabu search for multi-level colour image thresholding, International Conference on Computing for Sustainable Global Development (INDIACom), India, pp. 311-316, 2014.

27.

Chakraborty

Mandal

Shaikh

. Ternary Quantum Circuit for Color Image Representation, 3rd International Doctoral Symposium on Applied Computation and Security Systems (ACSS), Springer-Advances in Intelligent Systems and Computing (AISC) Book Chapter, 2016.