Image recognation

Humans currently have substantial performance advantages over machines in several areas, including
object recognition, knowledge representation, reasoning, learning and natural language processing
[RN03]. Intruigingly, most of the hard problems arising in these areas can naturally be cast as
NP-hard optimization problems, with the majority reducible to pattern matching problems such as
maximum common subgraph [Smi99, EV07, Bun00, BDK+08, Sin02]. The formal intractability
of most problems associated with human intelligence is at the heart of the continued difficulties AI
researchers face in mimicking or surpassing human capabilities in these areas.
It may seem surprising that capabilities that we take for granted and perform quite easily could
be computationally intractable. However it is important to remember that this intractability does not
preclude efficient generation of approximate solutions. In practice, exact solutions to optimization
problems arising in AI are not required. Generally there is a graceful degradation of performance
as a solution moves away from global optimality. Because of this behavior the ideal computational
1
Figure 1: Object recognition by image matching proceeds by pairing points in two images that correspond
to the same structure in the outside world. In the algorithms considered here, both feature
similarity and geometric consistency are considered in determining to what extent two images are
similar.
approach is to use specialized heuristic algorithms to attack these problems [Sim95]. It is interesting
to note that human brains are thought to contain structures specialized for pattern matching
(‘wetware heuristics’) that are used to support a variety of capabilities for which humans still hold a
performance advantage over machines, and that these structures have been used as inspirations for
development of successful heuristic algorithms [Sin02, Mou97, Mac91].
In this article we focus on the quintessential pattern recognition problem of deciding whether
two images contain the same object. This is a typical example of a capability in which humans
outperform modern computing systems and can be thought of as an NP-hard optimization problem.
We begin to explore whether quantum adiabatic algorithms [EFS00, CFGG00, BBTA99, SMTC02]
can be employed to obtain better solutions to this problem than can be achieved with classical optimization
algorithms. The first step in this exploration is to map image recognition into the particular
input format required for running quantum adiabatic algorithms on D-Wave superconducting AQC
processors.
2 Image matching
A popular method to determine whether two images contain the same object is image matching.
Image matching in its simplest form attempts to find pairs of image features from two images
that correspond to the same physical structure. An image feature is a vector that describes the
neighborhood of a given image location. In order to find corresponding features two factors are
typically considered: feature similarity, as for instance determined by the scalar product between
feature vectors, and geometric consistency. The latter is best defined when looking at rigid objects.
In this case the feature displacements are not random but exhibit correlations brought about by
a change in viewpoint. For instance, if the camera moves to the left we observe translations of
the feature locations in the image to the right. If the object is deformable or articulate then the
feature displacements are not solely determined by the camera viewpoint anymore but one can
2
Figure 2: Representation of images as labeled graphs. Shown are three exemplary interest points
for each image. The number of interest points detected is content dependent but is on the order
of several hundred for 640x480 resolution images with content as shown. Each interest point is
assigned a position, scale, and orientation [Low99]. In the figure the scale is indicated by a circle
and the orientation by a pointer. This information can be used to characterize the relative pose and
position of two interest points denoted by the vectors ~g next to the dotted lines.
still expect that neighboring features tend to move in a similar way. Thus image matching can
be cast as an optimization problem in which one attempts to minimize an objective function that
consists of two terms. The first term penalizes mismatches between features drawn from image one
and placed at corresponding locations in image two. The second term enforces spatial consistency
between neighboring matches by measuring the divergence between them. It has been shown that
this constitutes an NP-hard optimization problem [FH05].