Theoretical Computer Science 529 (2014) 46–60
Contents lists available at
Theoretical Computer Science
Histogram-based segmentation of quantum images
Simona Caraiman
, Vasile I. Manta
Computer Engineering Department, Technical University of Iasi, Romania
a r t i c l e
i n f o
a b s t r a c t
Article history:
Received 17 September 2012
Received in revised form 14 April 2013
Accepted 6 August 2013
Communicated by C.S. Calude
Keywords:
Quantum information processing
Quantum algorithms
Quantum image processing
Quantum image segmentation
Quantum amplitude amplification
Quantum Fourier transform
In this paper we investigate the use of quantum computing systems in the field of
image processing. We consider histogram-based image processing operations and develop
quantum algorithms for histogram computation and threshold-based segmentation. The
underlying principle used for constructing the proposed quantum algorithms is to
reformulate them in order to exploit the performance of the quantum Fourier transform
and of quantum amplitude amplification. We show that, compared to the classical
correspondents, a significant speedup can be achieved by expressing parts of the
computational process in terms of problems that can be solved using these quantum
techniques.
©
2013 Elsevier B.V. All rights reserved.
1. Introduction
Quantum computation and quantum information systems have recently received a lot of attention due to their spectacu-
lar perspectives especially regarding performance speedup
and secure communication
. Moreover, the extrapolation
of Moore’s Law recommends quantum systems as the natural choice for implementing future computing systems as it seems
that soon the binary unit of information, the bit, will be implemented at subatomic scale. In the last two decades, scientists
have found that the necessary reformulation of information processing in accordance with quantum physics (or Quantum
Information Processing) is a tremendously powerful concept for information processing and communication. Efficient quan-
tum algorithms have been formulated allowing for significantly faster calculations than on classical computers. Nevertheless,
there are fundamental differences between the algorithms that can be run on quantum computers and those run on classi-
cal computers, so a major challenge in quantum computation is to develop efficient quantum algorithms. These differences
come from the probabilistic nature of quantum mechanics which stems from the act of measurement: even though a quan-
tum computer can do exponentially many computations in parallel, a measurement of the resulting quantum state yields
a random outcome which is not necessarily the particular outcome searched for. The common approach to cope with this
behavior is to create constructive interference among the computational paths that lead to ‘right’ answers and thus high
probability of observing those answers. The development of efficient quantum algorithms for practical problems would help
in justifying the immense efforts required for building a working quantum computer as it represents a very challenging task
that requires spending a huge amount of resources.
The remarkable properties of quantum systems led to the emergence of innovative ideas in all major fields of comput-
ing, including graphics processing. A few problems in Computer Graphics have been tackled from the quantum processing
perspective and a few quantum algorithms have been suggested for the rendering problem
and for computational
geometry
. Even though for rendering it has been shown that quantum solutions can be devised for disparate problems
*
Corresponding authors. Tel.: +40 721 27 64 71; fax: +40 232 23 24 30.
E-mail addresses:
(S. Caraiman),
(V.I. Manta).
0304-3975/$ – see front matter
©
2013 Elsevier B.V. All rights reserved.
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
47
such as the visibility of geometric primitives (ex. Z-Buffering), global illumination models (ray tracing, radiosity, photon
mapping) or level of detail management, still the full quantum rendering pipeline has not yet been envisioned. Another
important result is the quantum RANSAC algorithm
, a scheme for robust model fitting, which has significant applications
in both Computer Graphics and Vision.
As for Quantum Image Processing, the research in the field has encountered fundamental difficulties as it is also still in its
infancy. Most of the work done so far refers to fundamental aspects such as representing and storing an image on a quantum
computer and the basic processing operations. Representation of color information on one qubit was proposed for the Qubit
Lattice approach
and was also employed in the FRQI framework
. Several basic processing operations were defined in
the FRQI framework: geometrical transformations
, one-qubit quantum gates applied on the color wire
, a similarity
measure between two images based on pixel differences
. Two strategies for quantum image watermarking were also
developed, one based on restricted geometric transformations
and one based on the quantum Fourier transform
Beach et al.
show that Grover’s quantum search algorithm is applicable to image processing tasks such as pose
recognition in a model-based machine vision system.
Other important contributions to the quantum image-processing field rely on the exploitation of maybe the most valuable
resource of many-qubit quantum systems, entanglement. It was shown that it could lead to the development of efficient
methods for representing and retrieving information about the objects in a quantum image
and also to a quantum
image compression scheme
Also, it is natural to assume that the image processing field could benefit from the quantum processing transformations
(the quantum Fourier transform, the quantum wavelet transform
and the quantum discrete cosine transform
which seem to be more efficient than their classical counterparts. Using these efficient operations in image processing could
underline the potential of the quantum information processing field.
Most of the work done so far in the field of quantum image processing is based on the quantum circuit model of com-
putation. A different approach that uses the adiabatic quantum computing model
was proposed in defining solutions
for image matching
and also for a class of machine learning problems
In this paper we address the problem of representing and segmenting a quantum image. The approach described by
Venegas-Andraca and Ball
for storing and retrieving information about the shapes of objects in quantum images
deals with binary images and thus assumes that the objects be, in fact, already segmented. In contrast, our work pro-
vides quantum algorithms for performing the segmentation process on quantum images. In particular we consider the case
of threshold-based segmentation. To this end, we first devise a quantum algorithm for computing the image histogram. We
show that the representation of quantum images using the method employed by Venegas-Andraca and Bose
and Le et al.
is not directly suitable for accomplishing this task. Using the quantum histogram we describe the quantum algorithms
for image segmentation using two representative techniques for threshold selection: the P-tile method and the iterative
thresholding method. All the quantum image processing techniques described in this paper exhibit significant speedups
compared to the analogous classical procedures. This is mainly due to the speedup introduced by exploiting the quantum
mechanism of amplitude amplification and the quantum Fourier transform.
Before describing the proposed quantum image processing algorithms, background is given to make the paper self-
contained. We give a short introduction to the basic concepts in quantum computing and briefly overview the main quantum
techniques employed in developing the proposed algorithms: quantum search, quantum phase/eigenvalue estimation, quan-
tum counting. Therefore, the reader familiar with these concepts can skip Sections
and
. In Section
we introduce the
problem of histogram-based segmentation and overview the most representative classical techniques for threshold selection.
Sections
and
outline the proposed quantum variants for histogram computation and image segmentation, respectively.
In Section
we summarize our conclusions and discuss the prospects for further development of the quantum image pro-
cessing field in the light of the new contributions presented in this paper.
2. Basic concepts in quantum computing
The quantum analogous of the classical bit is the qubit. A qubit is a quantum system whose states can be completely
described by the superposition of two orthonormal basis states, labeled
|
0
and
|
1
(in a Hilbert space H
=
C
2
,
|
0
= (
1 0
)
T
,
|
1
= (
0 1
)
T
). Any state
|ψ
can be described by:
|ψ =
α
|
0
+ β|
1
, |
α
|
2
+ |β|
2
=
1
,
(1)
where
α
and
β
represent the probability amplitudes of the basis states, i.e., a measurement of the system yields
|
0
with
probability
|
α
|
2
and
|
1
with probability
|β|
2
.
The machine state
|ψ
of an n-qubit quantum computer is a unit vector in Hilbert space H
=
C
2
n
:
|ψ =
2
n
−
1
i
=
0
α
i
|
i
,
(2)
where
2
n
−
1
i
=
0
|
α
i
|
2
=
1 and
|
α
i
|
2
represents the probability of getting value
|
i
when measuring the register.
A quantum register s is represented by a sequence of qubits. If s is an n-qubit quantum register and U is an operator in
the states space H , then the operator U applied to the register s is called a quantum gate. In closed systems, any quantum
48
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
operator is a unitary operator and thus any computational process can be implemented by a sequence of quantum gates. El-
ementary quantum gates include single qubit gates (Not, Hadamard, phase shift, rotations), controlled gates (CNOT, CPHASE)
and the Toffoli gate
. The unitarity of quantum operators ensures the reversibility of the computational process. The only
irreversible operation allowed is the measurement of quantum states, which has the effect of collapsing the superposition
into one of the computational basis states.
The immense computing power provided by a quantum machine compared to that of a classical one comes as a di-
rect consequence of the principles of quantum physics that translate into three remarkable quantum resources: quantum
parallelism, quantum interference and entanglement of quantum states
These remarkable properties of quantum systems allowed the formulation of optimal algorithms for two fundamental
problems: integer factorization (Shor’s algorithm
) and the search in an unstructured database (Grover’s algorithm
Thus, two main classes of quantum algorithms have better time complexity than their classical counterparts. The algorithms
in the first class are based on the quantum Fourier transform and provide remarkable solutions for solving the factorization
and discrete logarithm problems, with an exponential speedup over the best known classical algorithms. The algorithms in
the second class are based on amplitude amplification of quantum states, a technique that generalizes the idea underlying
Grover’s quantum search algorithm
. This class of algorithms provides a quadratic speedup with respect to the best
classical algorithms.
3. Histogram-based segmentation
The term image segmentation refers to the process of partitioning an image into a set of non-overlapping regions that
cover it. The purpose is to separate the regions corresponding to objects of interest, from the regions of the image that
correspond to the background, based on criteria such as similarity and homogeneity. The choice for a segmentation method
is application dependent. Thresholding is an easy and convenient method of performing the special case of foreground vs.
background segmentation. Thresholding techniques are simple and intuitive, relying on the different intensities or colors in
the different regions of an image.
In the thresholding operation a set of optimal thresholds is determined, based on which several meaningful regions
are identified in the image. Various thresholding schemes have been developed, a comprehensive survey being given by
Sezgin and Sankur
. Finding the optimum threshold(s) is the key to a successful segmentation and most methods rely
on histogram processing for this.
The histogram of an image represents the relative frequency of occurrence of the various colors (gray levels) in the
image. For a digital image with a number L of colors (gray levels), the histogram is a discrete function
h
(
g
k
)
=
n
k
N
,
k
=
0
,
1
, . . . ,
L
−
1
(3)
representing the number of pixels n
k
with color g
k
as a fraction of the total number of pixels N.
In the simplest case of images with bi-modal histograms, a single global threshold value T is used to partition the image
histogram. The ideal case is to have the objects and background represented in the image histogram by a deep and sharp
valley between two peaks. The threshold can then be chosen at the bottom of this valley.
Another method for determining the threshold, that is relatively simple, does not require much specific knowledge of
the image and is robust against image noise is the iterative method described by
. Here the threshold is
adjusted in each iteration using the mean intensity values of the partitioned regions, until the change in successive iterations
becomes small enough.
illustrates the result of segmenting a grayscale image using a global threshold computed with
this approach.
Algorithm 1 Iterative threshold selection.
1: Select an initial estimate for T
2: Partition the image using T into two regions: a group G
1
of pixels with gray level values
T (object) and a group of pixels, G
2
, with gray level values
>
T (background)
3: Compute mean intensity values,
μ
1
and
μ
2
, for the two groups
4: Compute the new threshold T
=
μ
1
+μ
2
2
5: Repeat steps 2 to 4 until there is no change in T (or the difference in successive iterations is smaller than a predefined threshold)
The global thresholding technique works only if the peaks in the image histogram, corresponding to the objects of
interest and to the background, are well separated. Hence, this method is not able to deal with images with a strong
illumination gradient where the valleys in the histogram are flat and broad or where the two peaks have very differing
heights. Local adaptive thresholding, on the other hand, selects an individual threshold for each pixel based on the range of
intensity values in its local neighborhood. This allows for thresholding of an image with a histogram that does not contain
distinctive peaks. Some approaches partition the image into sub-images and use the mean or median of the sub-image or
of a neighborhood of the pixel.
In the case when a certain property of an image after segmentation is known a priori, the task of threshold selection is
simplified, since the threshold is chosen to ensure this property is satisfied. The P-tile method uses such information, e.g.,
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
49
Fig. 1. (a) Example of a grayscale image of coins. (b) Histogram of the coins image. (c) Result of threshold-based segmentation of the coins image using the
iterative threshold selection. The initial estimate of the threshold is taken to be the median gray level, i.e. T
=
135, and the iterative loop executes four
times and terminates with T
=
166
.
4.
the object is darker than the background and occupies a certain known fraction (percentile) 1
/
p of the total image area,
as might be the case of a printed text sheet. In this case the threshold is set by finding the intensity level such that the
desired fraction of the image pixels is below this value. This intensity level can be found using the cumulative histogram:
c
(
g
k
)
=
k
i
=
0
h
(
g
i
).
(4)
The threshold T is set such that c
(
T
)
=
1
/
p. For a dark background c
(
T
)
=
1
−
1
/
p.
4. Quantum algorithms for histogram-based segmentation
The main approach we use in order to formulate quantum image processing tasks is to express these tasks in terms of
sub-problems for which efficient quantum solutions have been defined. Thus, as explained in Sections
and
, computing
the histogram of a quantum image and then employing threshold-based segmentation using the histogram information can
be achieved using quantum counting and quantum mean and median estimation. In this section we introduce the basic
concepts on which these quantum algorithms rely. We give special attention to the quantum search problem in order to
emphasize the mechanism of amplitude amplification. It is the base for all the other quantum algorithms that we employ
in order to define quantum solutions for the considered image processing tasks.
4.1. Quantum search
The importance of the quantum search algorithm is underlined by the intensive use of search techniques in classical
algorithms, while, in many cases, a natural adaptation is possible in order to provide a faster quantum algorithm
. Special
interest is given to the quantum counting algorithm, which represents an inspired combination of quantum search with
the Fourier transform and allows the estimation of the number of solutions to a search problem faster than possible on a
classical computer
Many problems in classical computing can be reformulated to express them as a search of a unique element that satisfies
a certain predefined condition. When no additional information about the search condition is available, the best classical
algorithm is a brute-force search, meaning that the elements are sequentially tested against the search condition. For a
list of N elements, an average of N
/
2 comparisons are executed by this algorithm. Exploiting the advantages of quantum
parallelism and interference of quantum states allowed the formulation of a quantum algorithm that can find the searched
element in an unstructured database in only O
(
√
N
)
steps
This algorithm, devised by Lov Grover, is based on the concept of amplitude amplification. Its principle is to encode the
elements in the data set as quantum states of a quantum register. Iteratively an operator G is applied having the effect
of raising the probability that the system finds itself in the marked state (the state encoding the solution of the search
problem). Finally a measurement is performed.
Because only unitary transformations are used to act upon the system, probability conservation takes place. As the
probability that the system finds itself in the desired state grows, the probabilities of all other (unmarked) states are cor-
respondingly diminished. Applying Grover’s operator G a certain number of times will determine the probability of the
marked state to be very close to one.
In order to achieve this behavior of the quantum system, a Grover iteration first inverts the phase of the amplitude of
the marked state and then inverts the phase of the amplitude of all states around the mean. In his original paper
Grover shows that such an iteration can be efficiently implemented using the following unitary transformation:
G
=
H Z H O
,
(5)
50
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
where H denotes the Walsh–Hadamard transform
H
=
1
√
2
1
1
1
−
1
,
(6)
Z denotes the zero-state phase shift
Z
=
2
|
0
0
| −
I
,
(7)
and O represents the oracle operator
O
|
x
= (−
1
)
f
(
x
)
|
x
=
−|
a
,
if x
=
a
,
|
x
,
if x
=
a
.
(8)
The Walsh–Hadamard gate transforms a basis state in an equal superposition of states.
Operator Z flips the sign of the amplitude if and only if the system is in state
|
0
. The application of the Hadamard
transform before and after the Z transform results in a global change of the phase of the amplitude obtaining an inversion
of all states around the mean.
Operator O rotates with
π
radians the phase of all eigenvectors that fulfill the search condition. The inversion of the
solution state (the marked state) can be obtained using a so-called “black box” function (known as a quantum oracle) which
must only be able to identify whether a certain record is member of the solution set, thus the mechanism is very general.
Function f in the oracle operator indicates whether a given input is the searched number a:
f
: {
0
,
1
, . . . ,
N
−
1
} → {
0
,
1
},
f
(
x
)
=
0
,
x
=
a
,
1
,
x
=
a
.
(9)
The amplitude amplification iterations are applied to an initial state
|ψ
, containing an equal superposition of all possible
index values. State
|ψ
can be obtained by applying the Hadamard gate on an n-qubit register initially in state
|
0
:
H
⊗
n
|
0
=
1
√
N
N
−
1
x
=
0
|
x
,
(10)
where N
=
2
n
.
After one application of the Grover operator, the amplitude of the marked state grows with a factor of O
(
1
√
N
)
, while the
amplitudes of the unmarked states decrease correspondingly. To obtain O
(
1
)
probability for the solution state, the Grover
iteration must be applied O
(
√
N
)
times. There is a finite probability that the search operation does not end in success, in
which case, Grover’s algorithm must be repeated.
Grover’s original algorithm is only valid in the case of an unstructured search with a single solution. Nevertheless, most
practical applications involve multiple solutions to the search problem. In this case one can randomly extract one of the t
solutions by applying π
4
N
t
amplitude amplifying steps as described by Brassard et al.
. When the number of solutions t,
is not known in advance, extracting the entire set of solutions can be achieved by counting the number of solutions using
the algorithm described in Section
prior to applying the quantum search algorithm.
In the case of multiple solutions, the quantum search algorithm works by naturally dividing the search space into two
sets: the “good” index values, x
∈
G
, for which f
(
x
)
=
1 and the “bad” index values, x
∈
B
, for which f
(
x
)
=
0, with t being
equal to the cardinality of the good set, i.e. t
= |
f
−
1
(
x
)
| = |
G|
. The superposition of all possible indices defined in
can
be expressed as a combination of two superposition states
|ψ
good
and
|ψ
bad
:
|ψ =
1
√
N
N
−
1
x
=
0
|
x
=
t
N
|ψ
good
+
N
−
t
N
|ψ
bad
,
(11)
where
|ψ
good
=
1
√
t
x
∈G
|
x
,
(12)
|ψ
bad
=
1
√
N
−
t
x
∈B
|
x
.
(13)
By introducing a parameter
θ
, defined by
sin
θ
=
t
N
(14)
state
|ψ
can be written as
|ψ =
sin
θ
|ψ
good
+
cos
θ
|ψ
bad
.
(15)
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
51
Following the reasoning given by Brassard et al.
, the amplitude amplification operator G, expressed in the
{|ψ
good
, |ψ
bad
}
basis takes the form
G
=
cos 2
θ
sin 2
θ
−
sin 2
θ
cos 2
θ
(16)
and has the effect of rotating the initial state
|ψ
with an angle of 2
θ
:
G
|ψ =
G
sin
θ
|ψ
good
+
cos
θ
|ψ
bad
=
cos 2
θ
sin 2
θ
−
sin 2
θ
cos 2
θ
sin
θ
cos
θ
=
sin 3
θ
cos 3
θ
=
sin 3
θ
|ψ
good
+
cos 3
θ
|ψ
bad
.
(17)
After k successive applications of G, state
|ψ
becomes:
G
k
|ψ =
cos 2
θ
sin 2
θ
−
sin 2
θ
cos 2
θ
k
sin
θ
cos
θ
=
cos 2k
θ
sin 2k
θ
−
sin 2k
θ
cos 2k
θ
sin
θ
cos
θ
=
sin
(
2k
+
1
)θ
|ψ
good
+
cos
(
2k
+
1
)θ
|ψ
bad
.
(18)
Thus, if measuring the state
|ψ
after amplitude amplifying it k times, a solution state is found with O
(
1
)
probability,
provided that
(
2k
+
1
)θ
≈
π
2
. This implies that k
=
π
4
N
t
−
1
2
, i.e., O
(
N
t
)
steps are needed to find one of the t solutions
to the search problem.
4.2. Eigenvalue estimation
Given a unitary operator U , the goal is to find the eigenvalue e
i
λ
, of U corresponding to an eigenvector
|ψ
λ
, that is
to find e
i
λ
such that U
|ψ
λ
=
e
i
λ
|ψ
λ
. By setting
λ
=
2
π ϕ
, with 0
ϕ
<
1, the eigenvalue estimation algorithm described
by Abrams and Lloyd
works by employing two steps: the first one is to synthesize the phase state e
i
λ
|ψ
λ
using a
technique called ‘phase kick-back’ and the second one is to estimate
ϕ
by applying the inverse quantum Fourier transform
to this state. The quantum circuit that implements this algorithm uses two registers as input. The first one contains m
qubits and will output the m-bit estimate of
ϕ
, while the second register contains n qubits holding the eigenstate
|ψ
λ
. The
algorithm starts with the registers in the state
|φ
0
=
1
√
2
m
2
m
−
1
y
=
0
|
y
⊗ |ψ
λ
,
(19)
which can be obtained by applying the transform in Eq.
to the first register initially in state
|
0
⊗
m
.
Synthesizing the phase state can be achieved by applying U to
|ψ
λ
y times when the first register is in state
|
y
. This
can be done in superposition using controlled-U
2
j
gates (c-U
2
j
) applied on the second register with each of the qubits in
the first register acting as control qubits. If
|
y
m
−
1
. . . |
y
1
|
y
0
is the binary representation of
|
y
, with y
=
2
m
−
1
y
m
−
1
+
· · · +
2
1
y
1
+
2
0
y
0
, y
j
∈ {
0
,
1
}
, j
=
0
,
m
−
1, the qubit
|
y
j
is used as control for the 2
j
controlled-U gate:
1
√
2
|
0
+ |
1
|ψ
λ
c
−
U
2 j
−−−−→
1
√
2
|
0
+ |
1
U
2
j
|ψ
λ
=
1
√
2
|
0
|ψ
λ
+ |
1
e
i
λ
2
j
|ψ
λ
=
1
√
2
|
0
+ |
1
e
i
λ
2
j
|ψ
λ
.
The resulting state is
|φ
1
=
1
√
2
m
2
m
−
1
y
=
0
e
i
λ
y
|
y
⊗ |ψ
λ
,
(20)
52
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
where the phase factors e
i
λ
y
are propagated from the second register to the first control register. Now the phase estimation
procedure can be applied using the quantum Fourier transform. For any integer M
>
1 and for each integer z
∈ [
0
,
M
−
1
]
the quantum Fourier transform, F
M
, has the following action
F
M
|
z
=
1
√
M
M
−
1
y
=
0
e
2
π
i
z
M
y
|
y
.
(21)
For any
ω
=
z
M
, the inverse Fourier transform, F
−
1
M
, maps the state in Eq.
to
|
z
. Expressing
ϕ
with m bits of precision
as the binary fraction 0
.
x
0
x
1
. . .
x
m
−
1
, then applying the inverse Fourier transform to the first register of state
|φ
1
yields
|φ
2
=
F
−
1
M
⊗
I
|φ
1
=
F
−
1
M
1
√
M
M
−
1
y
=
0
e
i2
π ϕ
y
|
y
⊗ |ψ
λ
=
F
−
1
M
1
√
M
M
−
1
y
=
0
e
i2
π
x
M
y
|
y
⊗ |ψ
λ
= |
x
|ψ
λ
(22)
where the binary representation of x is
(
x
0
x
1
. . .
x
m
−
1
)
2
and M
=
2
m
.
4.3. Quantum counting
The quantum counting algorithm
is an inspired combination of quantum search with the quantum Fourier transform
that appears in the eigenvalue estimation problem. Specifically, the quantum counting algorithm exploits the fact that the
eigenvalues of Grover’s amplitude amplification operator are related to the number of solutions t of the search problem.
This allows the formulation of an algorithm that approximately counts the solutions of a search problem in O
(
√
N
)
time,
with a success probability of at least 8
/
π
2
, where N represents the dimension of the search space.
The quantum counting algorithm estimates the number of index values for which the function f in Eq.
returns value
1, i.e., it returns an estimate
˜
t for t
= |
f
−
1
(
1
)
|
. In order to obtain
˜
t, the algorithm uses the fact that the two eigenvalues
of Grover’s amplitude amplification operator G in the
{|ψ
good
, |ψ
bad
}
basis, depend on
θ
and
θ
depends on t accord-
ing to Eq.
. The two eigenvalues are e
−
2i
θ
and e
2i
θ
corresponding to eigenvectors
|ψ
+
=
i
√
2
|ψ
good
+
1
√
2
|ψ
bad
and
|ψ
−
= −
i
√
2
|ψ
good
+
1
√
2
|ψ
bad
, respectively. Thus, by estimating one of the eigenvalues using the algorithm described in
the previous subsection, one can compute
θ
and hence t
=
N sin
2
θ
. The algorithm for the quantum eigenvalue estimation
requires as input a register containing the eigenstate corresponding to the eigenvalue being estimated. Even though the
eigenstates
|ψ
+
and
|ψ
−
are unknown, the uniform superposition
|ψ =
1
√
N
N
−
1
x
=
0
|
x
, which can be easily prepared with
the transform in Eq.
, can be interpreted as an equally weighted superposition of these two eigenvectors:
|ψ =
1
√
N
N
−
1
x
=
0
|
x
=
sin
θ
|ψ
good
+
cos
θ
|ψ
bad
=
ie
−
i
θ
−
ie
i
θ
2
|ψ
good
+
e
−
i
θ
+
e
i
θ
2
|ψ
bad
=
e
−
i
θ
√
2
i
√
2
|ψ
good
+
1
√
2
|ψ
bad
+
e
i
θ
√
2
−
i
√
2
|ψ
good
+
1
√
2
|ψ
bad
=
e
−
i
θ
√
2
|ψ
+
+
e
i
θ
√
2
|ψ
−
.
(23)
Another input to the quantum counting algorithm is the number of bits of precision, m, for the estimation of the eigen-
values (and hence the precision with which the number of solutions are estimated). Various relations that bound the
accuracy with which the number of solutions can be estimated are summarized in
5. Computing the histogram of a quantum image
In the histogram definition given in Section
it is assumed that each possible intensity value of the image corresponds
to a single bin of the histogram. For purposes of computing the histogram if there are many possible color values, several
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
53
values can be grouped into a single bin. A classical procedure for histogram computation involves initializing the bins of the
histogram to zero and then computing the values associated to each bin by accumulation.
A quantum variant for the histogram computation can be devised if we reinterpret it in terms of a search problem with
multiple solutions. The value associated with a bin is obtained by searching the image pixels having a certain color and
counting the solutions. In this case the quantum counting algorithm can be used for each bin thus providing a quadratic
speedup over the classic procedure. It is important noticing that the solutions to the search problem, i.e., the pixels with a
certain color, need not be found explicitly but only counted. Retrieving these solutions represents a separate problem from
the quantum information processing point of view.
presents the proposed quantum procedure for computing the histogram of a quantum image, while in
we provide the quantum circuit that implements this algorithm. The quantum state prepared in step 3 of this algorithm
is used as input for the quantum counting algorithm described in the previous section. The first register will output an
estimate for the number of pixels having color g
k
, while the second register is used to represent the quantum image,
integrating both color and position information. Pixel positions are encoded in
|
P
using 2n qubits if we consider, without
loss of generality, that there are N
=
2
n
×
2
n
pixels in the image and the color information is encoded in
|
C
.
Algorithm 2 Quantum image histogram.
Input: 2
n
×
2
n
image, q – number of bits of precision for estimation of the histogram values
Output: image histogram h
1: for k
=
0
,
1
, . . . ,
L
−
1 do
2:
g
k
=
color corresponding to bin k
3:
prepare a state
|ψ
0
= |
0
⊗
q
⊗ |
Q
, where
|
Q
= |
C
m
|
P
2n
=
1
2
n
2
2n
−
1
i
=
0
2
m
−
1
j
=
0
α
i j
|
j
|
i
represents the quantum image
4:
apply a Hadamard gate to each qubit of the first register, the resulting state is
|ψ
1
=
H
⊗
q
⊗
I
⊗(
m
+
2n
)
|ψ
0
apply a cascade of c-G
2
j
k
gates:
5:
for j
=
0
,
1
, . . . ,
q
−
1 do
6:
|ψ
2
j
=
c-G
2
j
k
|ψ
2
j
−
1
,
|ψ
2
0
= |ψ
1
7:
end for
the resulting state is
|ψ
2
=
1
√
2
q
2
q
−
1
y
=
0
e
i
λ
k
y
|
y
⊗ |
Q
λ
k
8:
apply the inverse quantum Fourier transform to the first register resulting in
|ψ
3
=
F
−
1
2
q
⊗
I
⊗(
m
+
2n
)
|ψ
2
9:
measure the first register and let the outcome be the binary number x
= (
x
0
x
1
. . .
x
q
−
1
)
2
10:
compute s
=
2
q
−
1
x
0
+
2
q
−
2
x
1
+ · · · +
2
0
x
q
−
1
11:
estimate n
k
=
2
2n
+
m
sin
2 s
π
2
q
12:
compute h
(
g
k
)
=
n
k
2
2n
13: end for
One approach for encoding the color information would be to use a single qubit as suggested by Venegas-Andraca and
Bose
and Le et al.
. It relies on the definition of a machine capable of detecting electromagnetic waves and
producing an initialized qubit. This machine acts like an injective function between the set of electromagnetic waves that
can be detected and the set of quantum states of the following form:
|φ =
cos
θ
2
|
0
+
e
i
γ
sin
θ
2
|
1
.
(24)
The frequency of the detected electromagnetic wave is encoded in the real parameter
θ
while
γ
is left uninitialized. The
quantum state used to represent the image is
|
I
=
1
2
n
2
2n
−
1
j
=
0
|
c
j
⊗ |
j
,
(25)
where
|
c
j
takes the form in Eq.
. In the work of Venegas-Andraca and Bose
a storage and retrieval protocol has
been defined for such a representation of the quantum image. It is based on a statistical procedure involving multiple mea-
surements of identically prepared states. Le et al.
use single qubit unitary operators to achieve basic color processing
operations such as color inversion. However, this representation is not suited for the purpose of applying the mechanism of
quantum amplitude amplification employed in the quantum counting algorithm. The marked states in Grover’s algorithm,
i.e., states representing pixels with a given color, need to be computational basis states.
In order to overcome this problem we propose that m
=
log
2
L
qubits are used to encode the L colors present in the
image. Thus, in the state prepared in step 3 of the algorithm coefficients
α
i j
, with
2
m
−
1
j
=
0
|
α
i j
|
2
=
1 for all 0
i
<
2
2n
, are
used to express the color of a pixel with position i by means of a superposition of all possible representable colors. When
preparing the state
|
Q
that represents the quantum image, coefficients
α
i j
for a given pixel i will be 1 if j represents the
color of pixel i and 0 otherwise.
gives a simple example of a 2
×
2 image with four possible colors and its quantum
representation.
With this representation, the Grover operator used in step 5 of the algorithm is
G
k
=
H Z H O
k
,
(26)
54
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
Fig. 2. Quantum circuit that implements an iteration of the histogram computation procedure described in
. The input to this circuit is given by
a q-qubit register in state
|
0
and the quantum image represented on m
+
2n qubits. After the final measurement, the circuit outputs the binary number
x
= (
x
0
x
1
. . .
x
q
−
1
)
2
which is further used to classically compute the histogram value for bin k.
Fig. 3. Example of a simple 2
×
2 quantum image with four possible colors (two qubits are used to represent the color information and two qubits encode
the position of each pixel).
where the oracle operator O
k
is built according to Eq.
using function f
k
:
{
0
,
1
, . . . ,
2
m
+
2n
−
1
} → {
0
,
1
}
,
f
k
(
x
)
=
0
,
x
2n
=
g
k
,
1
,
x
2n
=
g
k
,
(27)
which is provided as a black box, where x in binary representation is
x
= (
c
m
−
1
c
m
−
2
. . .
c
0
p
2n
−
1
p
2n
−
2
. . .
p
0
)
2
with bits c
m
−
1
c
m
−
2
. . .
c
0
coding the color, bits p
2n
−
1
p
2n
−
2
. . .
p
0
coding pixel positions,
is the bitwise right shift operator
and g
k
= (
g
k
m
−1
g
k
m
−2
. . .
g
k
0
)
2
is the sought after color in step k of the algorithm.
Theoretically, the implementation of the oracle does not need to be specified. However, in practice, the implementation
must be considered because its computational complexity has a major impact on the overall performance of the quantum
procedure. A quantum circuit to implement the oracle operator O
k
can be conceived using the approach described by
Oliveira and Ramos
for building a quantum bit string comparator. The cost of this quantum comparator grows linearly
with the number of qubits used for representing the compared states. This implies that the cost for implementing our oracle
operator would be linear in m as in each iteration k we compare the state of the color register in the image with a quantum
state representing color g
k
.
Each iteration k of the quantum histogram computation procedure counts the pixels having gray level g
k
by applying
the quantum counting algorithm. The two eigenvalues of the operator G
k
in the
{|ψ
good
, |ψ
bad
}
basis are e
±
i
λ
k
=
e
±
2i
θ
k
Here
|ψ
good
represents the state encoding pixels with color g
k
and
|ψ
bad
represents the state encoding pixels with color
different from g
k
. Following the rationale in Section
the number of solutions to the search problem, i.e. the number n
k
of
pixels with gray level g
k
, are related to these eigenvalues by n
k
=
N sin
2
θ
k
=
2
2n
+
m
sin
2
θ
k
. By setting
λ
k
=
2
π ϕ
k
, 0
ϕ
k
<
1,
in order to estimate n
k
two stages are applied in each iteration. The first stage (steps 4–7) corresponds to the synthesis of
the phase state
|ψ
2
. The second stage (steps 8–11) corresponds to estimating the phase parameter
ϕ
k
. This is achieved by
applying the inverse quantum Fourier transform to the first register resulting
|ψ
3
= |
s
|
Q
λ
k
with
ϕ
k
=
s
2
q
=
0
.
x
0
x
1
. . .
x
q
−
1
.
Thus
θ
k
=
λ
k
2
=
2
π ϕ
k
2
=
π
s
2
q
.
It is also important to notice that, in contrast to the quantum counting procedure described in the previous section, in
our algorithm the input state for the second register is the quantum image
|
Q
. In general it is different from the uniform
superposition used in the original quantum search algorithm. As shown in Eq.
, this superposition also conveniently
expresses an equally weighted combination of the eigenstates needed as input by the eigenvalue kick-back mechanism.
A generalization of Grover’s search operator that allows for an arbitrary initial distribution to be used instead was proposed
by Biham et al.
. This more general algorithm results by simply omitting the first step of Grover’s original algorithm
where a uniform superposition is created over all elements. The key observation is that generically, this algorithm also has
O
(
N
t
)
running time.
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
55
6. Histogram-based segmentation of quantum images
As discussed in Section
, having computed the histogram of the quantum image, it can be used in the threshold-based
segmentation process in order to find a suitable value for the threshold. In this section we will show that quantum corre-
spondents for these procedures can be defined using variants of the amplitude amplification mechanism such as quantum
mean estimation, quantum median estimation and the quantum algorithm for finding the minimum/maximum.
6.1. Threshold selection using the P-tile method
In the P-tile method, the threshold selection involves computing a cumulative histogram. This can be accomplished using
a quantum algorithm for computing the mean value of a sequence. Let
¯
h
L
denote the mean over L values of the normalized
histogram function defined in Eq.
¯
h
L
=
1
L
L
−
1
j
=
0
h
(
j
).
(28)
Then, the cumulative histogram can be expressed as
c
(
k
)
=
k
j
=
0
h
(
j
)
= (
k
+
1
) ¯
h
k
+
1
.
(29)
Computing the sum of a sequence, or equivalently the mean, has been studied from the quantum computational per-
spective both independently
and in relation to the problem of numerical integral estimation
. Abrams and Williams
describe two methods for estimating the mean value. The first one is based on amplitude amplification and is a sim-
pler variation of the original algorithm described by Grover
. The basic idea is to construct a rotation operator U
¯
f
. It
depends on the values of the function f
: {
0
,
1
, . . . ,
N
−
1
} → [
0
,
1
]
in a way such that its action on the computational basis
state
|
0
|
0
⊗
n
is to transfer the mean value
¯
f in the amplitude of the
|
0
|
0
⊗
n
component of the output superposition. By
measuring this superposition in the computational basis, the probability of obtaining
|
0
|
0
⊗
n
would then be
| ¯
f
|
2
. Thus, in
order to estimate
¯
f with accuracy
would require O
(
1
2
)
repetitions, which is not better than using the classical direct
sampling method. However, amplitude amplification can be used to increase the accuracy of the estimate by increasing with
a known amount the probability of measuring the state
|
0
|
0
⊗
n
. Performing O
(
D
)
operations the amplitude of the target
state can be increased to D
¯
f . With the same O
(
1
2
)
trials an estimate of
¯
f with accuracy
∗
=
/
D can be provided which
can be reinterpreted as: O
(
1
∗
)
operations are needed to find
¯
f with accuracy
∗
.
The second method for estimating the mean is based on the idea of quantum counting and provides the same speedup
over the best classical procedure. Again, just like in the first method, the number of operations does not depend on the
size of the domain of f , but only on the desired accuracy. In order to use the quantum counting algorithm for estimating
the mean of the real-valued function f , it must be first converted into a Boolean-valued one. This can be accomplished by
adding an extra integer parameter w taking values in the range
[
1
,
W
]
, where W determines the estimation accuracy. Thus,
a Boolean function b can be defined as
b
(
x
,
w
)
=
1
,
if w
W f
(
x
),
0
,
if w
>
W f
(
x
),
(30)
and for a given x, the fraction of the W values for which b
(
x
,
w
)
is 1 represents the best approximation for f
(
x
)
, i.e.
f
(
x
)
=
1
W
W
w
=
1
b
(
x
,
w
)
. Then, the average value of b is identical to the average value of f :
¯
b
=
1
N W
N
−
1
x
=
0
W
w
=
1
b
(
x
,
w
)
=
1
N W
N
−
1
x
=
0
W f
(
x
)
= ¯
f
.
(31)
The average value of b can be estimated using the approximate counting procedure presented in Section
, as it directly
depends on the number r of solutions b
(
x
,
w
)
=
1. That is
¯
f
=
r
N W
. The accuracy 1
/
M of the estimation depends linearly
on the number of points used in the quantum Fourier transform as described in Section
. O
(
M
)
applications of the
amplitude amplification operator are needed for the quantum counting procedure. It follows that with O
(
1
)
operations, the
mean value can be estimated with accuracy
.
The proposed quantum procedure for computing the cumulative histogram c
(
k
)
for a given k is presented in
while the quantum circuit for this task is given in
The quantum state in the first step of the algorithm is the tensor product of three quantum registers. The first one
uses m qubits and will output an m-bit estimate for the number of solutions b
k
(
x
,
w
)
=
1, where b
k
: {
0
,
1
, . . . ,
k
−
1
} ×
{
0
,
1
, . . . ,
W
−
1
} → {
0
,
1
}
b
k
(
x
,
w
)
=
1
,
if w
+
1
W h
k
(
x
),
0
,
if w
+
1
>
W h
k
(
x
).
(32)
The second and third registers use n
+
l qubits, which is enough to hold all possible values for x and w.
56
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
Algorithm 3 Cumulative histogram.
Input: image histogram h, gray level k, integer value W
>
1, integer value M
1
Output: cumulative histogram c
(
k
)
1: prepare a state
|ψ
0
= |
0
⊗
m
⊗ |
0
⊗
n
⊗ |
0
⊗
l
, where m
=
log
2
M
, n
=
log
2
W
, and l
=
log
2
k
2:
|ψ
1
=
H
⊗
m
⊗
H
⊗
n
⊗
F
k
|ψ
0
apply a cascade of c-G
2
j
k
+
1
gates:
3: for j
=
0
,
1
, . . . ,
m
−
1 do
4:
|ψ
2
j
=
c-G
2
j
k
+
1
|ψ
2
j
−
1
,
|ψ
2
0
= |ψ
1
5: end for
6: apply the inverse quantum Fourier transform to the first register
|ψ
3
=
F
−
1
M
⊗
I
⊗
n
+
l
|ψ
2
m
−
1
7: measure the first register and let the outcome be the binary number x
= (
x
0
x
1
. . .
x
m
−
1
)
2
8: compute s
=
2
m
−
1
x
0
+
2
m
−
2
x
1
+ · · · +
2
0
x
m
−
1
9: estimate c
(
k
)
= (
k
+
1
)
sin
2 s
π
M
Fig. 4. Quantum circuit for computing the cumulative histogram for a given gray level k. The measurement of the first m
=
log
2
M
qubits will output the
binary number x
= (
x
0
x
1
. . .
x
m
−
1
)
2
which is further used to classically compute the cumulative histogram value for bin k. M determines the accuracy of
the estimation and also the complexity of the algorithm. The
(
n
+
l
)
-qubit register holds all possible values in the domain of the boolean function which
approximates the histogram according to Eq.
The second step of the algorithm creates the uniform superposition needed as input in the quantum counting algorithm.
Numbers M and W can be picked to be powers of two, so the Hadamard transform can be used. In contrast, k is not
necessarily a power of two, so we use the quantum Fourier transform F
k
as suggested by Brassard et al.
. Likewise, the
amplitude amplification operator used in step 3 of the algorithm is also constructed using the quantum Fourier transform:
G
k
=
F
W
+
k
Z F
−
1
W
+
k
O
k
,
(33)
where the oracle operator is based on function b
k
:
O
k
|
w
|
x
= (−
1
)
b
k
(
x
,
w
)
|
w
|
x
.
(34)
The values of the cumulative histogram are estimated with c
(
k
)
= (
k
+
1
)
r
N W
, where r is the number of solutions
b
k
+
1
(
x
,
w
)
=
1. The same rationale as in
is used to compute r from the m-bit estimate of the phase parameter
of the eigenvalues of G
k
+
1
.
In order to use the values of the cumulative histogram for threshold selection, the value of k must be found so that
c
(
k
)
is closest to the desired fraction 1
/
p of the total image area. A quantum procedure for this task can be devised if we
consider that it is equivalent to finding the minimum value of a function A:
{
0
,
1
, . . . ,
L
−
1
} → [
0
,
1
]
with
A
(
k
)
=
c
(
k
)
−
c
(
L
−
1
)
p
,
(35)
where c
(
L
−
1
)
is also equivalent to the total number of pixels in the image.
illustrates the segmentation of the coins
image in
(a) using the P-tile method.
The value for the segmentation threshold can be determined using the quantum algorithm presented by Durr and Hoyer
for finding the minimum value in an unsorted table of items. This algorithm finds the minimum value after O
(
√
L
)
iterations of an amplitude amplification operator, in contrast with the linear complexity needed to do this classically. Fol-
lowing the rationale provided by Durr and Hoyer
, in
we describe the quantum procedure for threshold
selection.
Durr and Hoyer proved that for a given constant number q
1, measuring the first register after a number of O
(
q
√
L
)
iterations, the algorithm finds the index corresponding to the minimum value with a probability of 1
−
1
/
2
q
.
6.2. Iterative threshold estimation
The iterative method for determining the threshold can also be expressed more advantageously in quantum terms. In
the first step of the algorithm an initial estimate is chosen for the threshold value. If the object and background occupy
comparable areas in the image, a good initial value for T is the average gray level of the image. However, the average
gray level is not a very good initial estimate in the case when the objects are small compared to the area occupied by
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
57
Fig. 5. (a) Cumulative histogram of the coins image in
(a). (b) Graphic representation of function A
(
k
)
, where 1
/
p is taken to be 0
.
5, i.e. we expect
half of the pixels in the image to belong to objects of interest. The value k
=
171 that minimizes this function gives the gray level to be used as threshold
in the segmentation process. (c) Result of threshold-based segmentation of the coins image using a threshold T
=
171.
Algorithm 4 P-tile threshold selection.
Input: cumulative histogram c, percentile p, number of iterations q
Output: segmentation threshold T
1: choose a threshold index k, uniformly at random from
{
0
,
1
, . . . ,
L
−
1
}
2: repeat q
√
L times
3:
prepare a state
|ψ
0
=
1
√
L
L
−
1
i
=
0
|
i
|
k
4:
apply amplitude amplification of multiple marked states to the first register, with an oracle operator given by
O
|
x
=
−|
x
,
if A
(
x
) <
A
(
k
)
|
x
,
otherwise
5:
measure the first register and let the outcome be k
6:
if A
(
k
) <
A
(
k
)
then
7:
set k
=
k
8:
end if
9: end
10: set the threshold T
=
k
the background (or vice versa), because one group of pixels will dominate the histogram. A more appropriate initial value
for T in such cases is the middlemost value of the set of gray levels, that is the halfway value between the minimum
and maximum gray levels. Thus, in the first case, the initial estimate can be computed using the quantum mean algorithm
applied on the histogram function, while in the second case the quantum algorithm for estimating the median can be used.
Grover
considered the problem of estimating the median of N
=
2
n
items with a precision
. The estimate
μ
should be such that, with a large probability, the number of items with values smaller than
μ
is less than
N
2
(
1
+ |
|)
and
those with values greater than
μ
is also less than
N
2
(
1
+ |
|)
. Any classical algorithm to do this needs at least
Ω(
1
/
2
)
samples. In his paper Grover gives an O
(
1
|
|
)
step algorithm for the above problem. Thus, an almost quadratic speedup
over the best classical algorithm was achieved, while Grover’s algorithm was proven to be almost optimal
. The basic
idea of the algorithm is similar to the one used for estimating the mean. The problem of estimating the median is first
translated into the problem of estimating
with a precision of
θ
. By repeating this procedure a logarithmic number of
times with different
μ
using a binary search procedure, one can obtain the median. The procedure of estimating
relies on
a unitary operator that transfers the desired statistic into the amplitude of state
|
0
of an n-qubit quantum system initially
in state
|
0
. By amplifying the amplitude of this state with an appropriate amount,
can be estimated with few repetitions
of this experiment using the same rationale as in the case of the mean estimation.
After selecting an initial threshold, the image pixels are partitioned into two groups based on this threshold and the
mean intensity value is computed for each group. In this step it is not necessary to use the image as input and to effectively
partition it, i.e. to determine the pixels belonging to each group. It suffices to work with the image histogram. This is
because the correct segmentation of the image is only produced at the end of the algorithm after settling the final value for
the threshold.
In the proposed quantum algorithm (
) computing the mean intensity values for the two groups can be
achieved using a procedure similar to the one described for the cumulative histogram. Thus, we are interested in computing
the mean values of two functions, f
1
: {
0
,
1
, . . . ,
T
} → [
0
,
1
]
and f
2
: {
T
+
1
,
T
+
2
, . . . ,
L
−
1
} → [
0
,
1
]
, corresponding to
groups G
1
and G
2
respectively:
μ
1
= ¯
f
1
=
T
i
=
0
h
(
i
)
T
+
1
,
(36)
μ
2
= ¯
f
2
=
L
−
1
i
=
T
+
1
h
(
i
)
L
−
T
−
1
.
(37)
58
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
Algorithm 5 Quantum image segmentation using iterative thresholding.
Input: 2
n
×
2
n
image, histogram h
Output: segmented image, positions of pixels belonging to the segmented object
1: Set the initial value for T to be the median of h, computed using the quantum algorithm described by Grover
2: Use the mean estimation algorithm based on quantum counting to approximate
μ
1
and
μ
2
defined in Eqs.
and
, respectively
3: Compute the new threshold T
=
μ
1
+μ
2
2
4: Repeat steps 2 and 3 until convergence is reached
5: Prepare a state
|
Q
= |
C
m
⊗ |
P
2n
=
1
2
n
2
2n
−
1
i
=
0
2
m
−
1
j
=
0
α
i j
|
j
|
i
representing the quantum image
6: Let t
=
μ
1
(
T
+
1
)
, i.e. the no. of pixels belonging to the object to be segmented
7: Apply a number of
2
m
+
2n
t
amplitude amplification steps on state
|
Q
, with an oracle given by
O
|
x
=
−|
x
,
x
2n
T
|
x
,
x
2n
>
T
The resulting state
|
Q
s
is a uniform superposition of all states representing pixels with intensity
T , i.e., it represents the segmented image
8: while t
>
1 do
9:
Construct a semiclone
|
Q
s
of
|
Q
s
10:
Measure
|
Q
s
. Let the outcome be the number y with binary representation
(
c
m
−
1
c
m
−
2
. . .
c
0
p
2n
−
1
p
2n
−
2
. . .
p
0
)
2
11:
if y is a new solution according to the oracle used in step 7 then
12:
process it (
(
p
2n
−
1
p
2n
−
2
. . .
p
0
)
2
represents the position of a new pixel belonging to the object)
13:
else
14:
goto step 9
15:
end if
16:
Apply a number of
2
m
+
2n
t
−
1
amplitude amplification steps on
|
Q
s
, with an oracle given by
O
|
x
=
−|
x
,
x
=
y
|
x
,
x
=
y
The resulting state is a uniform superposition of all states representing unprocessed pixels with intensity
T
17:
t
=
t
−
1
18: end while
The two Boolean functions used for approximating the mean values using the quantum counting algorithm are b
1
:
{
0
,
1
, . . . ,
T
} × {
0
,
1
, . . . ,
W
−
1
} → {
0
,
1
}
b
1
(
x
,
w
)
=
1
,
if w
+
1
W f
1
(
x
),
0
,
if w
+
1
>
W f
1
(
x
),
(38)
and b
2
: {
T
+
1
,
T
+
2
, . . . ,
L
−
1
} × {
0
,
1
, . . . ,
W
−
1
} → {
0
,
1
}
b
2
(
x
,
w
)
=
1
,
if w
+
1
W f
2
(
x
),
0
,
if w
+
1
>
W f
2
(
x
).
(39)
The amplitude amplification operators and the two oracles are constructed similarly to Eqs.
and
When the final threshold is settled, i.e., when the convergence is reached, this value is used to segment the objects in the
image. This can be interpreted as a search problem with multiple solutions: find the pixels in the image with intensity less
than or equal to the computed threshold. In the quantum algorithm for computing the histogram, we were interested only
in counting the number of solutions for the search problem. In contrast, this time it is important to also actually extract
these solutions representing object pixels.
The variations of Grover’s algorithm for the case of a search problem with multiple solutions allow for the retrieval of one
solution at random when the number of solutions t is unknown. In order to extract the solutions, one must first determine t,
which can be done using the quantum counting algorithm as shown in Section
. The number of solutions to our specific
search problem is known from a previous step of the algorithm, where the mean of group G
1
has been computed. However,
even though the final state of the amplitude amplification algorithm is a uniform superposition of all the solutions to the
search problem, extracting one of these solutions determines the system to collapse to the corresponding state. This means
loosing the rest of the information. Therefore, the extraction of all the solutions cannot be done sequentially, but with
repeated applications of the amplitude amplification algorithm. More exactly O
(
t log t
)
repetitions are expected in order to
extract all t solutions. Fortunately, for our specific problem a more efficient technique can be employed for extracting the
solutions to the search problem in O
(
t
)
steps
. This method uses a semi-cloning protocol in order to make approximate
copies of the final solution superposition and thus allowing for a sequential extraction. Even though the No-Cloning Theorem
states the impossibility to make perfect copies of arbitrary quantum states, it turns out that it is possible to produce
a semi-clone with 0.5 probability of being a perfect clone without loosing the initial superposition. The trick is to be able
to verify whether the semi-clone is valid or not, which can be accomplished with the use of the oracle
. Steps 8–15 of
illustrate this process.
Depending on the further processing requirements of the segmented image, the positions of the pixels belonging to the
object might not need to be extracted. In this case, the algorithm can stop after step 7 and output state
|
Q
s
. This state
actually represents the segmented image as it exhibits non-zero amplitudes only in the states corresponding to object pixels.
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
59
7. Concluding remarks
In this paper we presented new results in the emerging field of Quantum Image Processing by introducing quantum
algorithms for image processing tasks. Specifically, we addressed the problem of histogram-based image processing by
defining quantum procedures for computing the image histogram and for threshold-based segmentation. Our approach was
to emphasize the parts of the computational process that can be reformulated in terms of problems for which existing
quantum algorithms can bring a significant speedup. To this end, we expressed the histogram computation as a search
problem with multiple solutions and used the quantum counting algorithm to return the number of pixels associated with
each bin of the histogram. The histogram can then be further used for selecting an appropriate threshold for segmenting
the image. We considered two representative methods for threshold selection, i.e., the P-tile method and the iterative
approach. We showed that a quantum variant of the P-tile threshold selection method can be devised by employing the
quantum algorithm for finding the minimum, while the iterative method can exploit the quantum algorithms for estimating
the mean and the median. The speedup of these quantum algorithms over their classical variants is directly transferred
into a proportional speedup for the proposed quantum image processing algorithms. The quantum circuits that implement
the proposed quantum algorithms are also provided. Finally, we showed that the actual segmentation process can also be
expressed using the quantum formalism. This can be accomplished by considering it a problem of searching the image
pixels having a gray level less (greater) than the given threshold and applying amplitude amplification of the corresponding
quantum states. The retrieval of the pixels belonging to the segmented object is accomplished by extracting the solutions
to this search problem using the quantum semi-cloning protocol. This allows for the segmented pixels to be returned
sequentially from the final state representing the solution superposition and avoids the need for repeated applications of
the amplitude amplification algorithm.
The mechanism of amplitude amplification of quantum states is at the heart of all the quantum algorithms proposed in
this paper. This has a direct implication on the image representation model that can be used. In contrast to the quantum
image representation employed by Venegas-Andraca and Bose
and Le et al.
, in our case, the color of a pixel is
quantized and represented with an appropriate number of qubits, much like in the classical case (m
=
log
2
L qubits are
needed to represent the L colors of a gray level image). However, the key observation is that the same m qubits are used
to store the colors of all the pixels in the image which is possible by efficiently exploiting the properties of quantum
superpositions. This, in fact, allows for an overall exponentially lower memory space to be used than in the classical case
(m
+
2n qubits are needed to store a 2
n
×
2
n
image with L gray levels compared to m2
2n
classical bits). Moreover, even
though at first sight the single qubit representation of the color information used by Venegas-Andraca and Bose
and Le
et al.
is less space consuming, still several copies of the quantum image need to be prepared as part of the storage
protocol. This is because the image retrieval process relies on a statistical procedure. In our case, the quantum image is
prepared using basis states and not general quantum states and thus the retrieval process need not involve such a statistical
procedure. However, it would be interesting to make a comparison between the memory space needed by the semi-cloning
protocol used in our quantum image segmentation procedure and the space that would be necessary for representing the
color as in Eq.
. In the latter case, the pixels belonging to the segmented object could be determined as part of the image
retrieval procedure but we also have to consider the supplementary computational steps due to the repeated applications
of amplitude amplification.
The results obtained in this paper offer a promising perspective on the investigation of more such applications of
quantum computing to image processing tasks. We believe that a further development of the field could be achieved by
expressing more image processing operations in quantum terms using the approach described in this paper. Quantum algo-
rithms devised in the context of other fields, such as quantum clustering
or quantum pattern matching
could
also be employed in order to develop a higher-level image processing framework. Of course, more spectacular results could
be obtained by developing entirely new quantum image processing algorithms. Nevertheless, we believe that even though
the field of Quantum Image Processing is still in an early stage of development the contributions to this field could result in
interesting ideas for the advent of the main framework of Quantum Information Processing. This would have a significant
impact on the exploration of theoretical concepts of quantum information, the design of new quantum algorithms and the
development of novel applications for quantum information processing. It would also represent an overall justification for
the immense efforts needed for building working quantum computers.
Acknowledgement
This work was supported by the project PERFORM-ERA ”Postdoctoral Performance for Integration in the European Re-
search Area” (ID-57649), financed by the European Social Fund and the Romanian Government.
References
[1]
[2]
[3]
E. Bernstein, U. Vazirani, Quantum complexity theory, SIAM J. Comput. 26 (1997) 1411–1473.
[4]
60
S. Caraiman, V.I. Manta / Theoretical Computer Science 529 (2014) 46–60
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
J. Latorre, Image compression and entanglement, arXiv:quant-ph/0510031, 2005.
[19]
[20]
[21]
C.C. Tseng, T.M. Hwang, Quantum circuit design of 8
8 discrete cosine transform using its fast computation flow graph, in: IEEE International
Symposium on Circuits and Systems, ISCAS 2005, vol. 1, 2005, pp. 828–831.
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
G. Brassard, P. Hoyer, A. Tapp, Quantum counting, arXiv:quant-ph/9805082v1, 1998.
[34]
C.P. Williams, Explorations in Quantum Computing, 2nd edition, Springer, 2011.
[35]
[36]
[37]
[38]
[39]
C. Durr, P. Hoyer, A quantum algorithm for finding the minimum, arXiv:quant-ph/9607014, 1999.
[40]
[41]
[42]
[43]
W.K. Wootters, W.H. Zurek, A single quantum cannot be cloned, Nature 299 (1982) 802–803.
[44]
[45]
M. Sasaki, A. Carlini, R. Jozsa, Quantum template matching, Phys. Rev. A 64 (2001) 022317.
[46]
P. Mateus, Y. Omar, Quantum pattern matching, arXiv:quant-ph/0508237v1, 2005.
[47]
C.A. Trugenberger, Quantum pattern recognition, Quantum Inf. Process. 1 (2002) 471–493.
Document Outline
- Histogram-based segmentation of quantum images
Wyszukiwarka
Podobne podstrony:
opracowanko histogram id 338711 Nieznany
histogramy
Histogramy
Histogram
Histogram
Porównaj symetrię rozkładu na podstawie histogramu oraz wykresu pudełkowego mediana kwartyle
Histogram
HISTOGRAM, hydrologia
HISTOGRAM - jak z niego korzystać, Grafika, Praktyczne porady
histogramy 1
Operacje na histogramie
Porównaj symetrię rozkładu na podstawie histogramu oraz wykresu pudełkowego mediana-kwartyle
histogramy 2
lec4 Pzetwarzanie histogramy obrazu 26
¤ Zarządzanie jakością - histogram i formularz zbierania danych, zarządzanie jakością, Zagadnienia J
histogram
histogielda
Histogramy
więcej podobnych podstron