The Complexity of Perceptual Search Tasks

Introduction

In this paper, the general task of visual search will be shown to be inherently intractable in the formal sense. Given the ubiquity of visual search tasks in everyday perception, it may be true that visual perception in general is also intractable. Yet, human vision is an effortless and exquisitely precise sense. How can this be? Ancient philoso­ phers were aware of the fact that humans could at­ tend to the relevant and ignore the irrelevant. More recently, psychologists have studied attention, and have proposed that there must be some kind of pro­ cessing limit in the brain to lead to such a phenomenon. Helmholtz claimed that a conscious or voluntary effort may focus attention on a particular spot in the visual field [Helmholtz 1925], and this led to the 'attentional spotlight' idea that is widespread in models of perception. Neisser first claimed that any model of vision that was based on spatial parallelism alone was doomed to failure, sim­ ply because the brain was not large enough [Neisser, 1967]. Stating that the brain is simply not large enough does not yield any useful constraints on the architecture of the visual system. Arguments such as this, namely that a given fixed resource is not large enough to accommodate a specified problem lead naturally within the computational paradigm to consideration of computational complexity. Neisser's claim hinted at the difficult issues of com­ putational complexity that must be addressed, even though when it was made complexity theory was barely in its infancy.

Complexity considerations are commonplace in the computational vision literature. Many researchers (for example, [Mackworth and Freuder, 1985], [Poggio, 1982], [Grimson, 1984] and others) routinely provide an analysis of the complexity of their proposed algorithms - this is simply good com­ puter science. It is important to demonstrate that specific algorithms have tractable requirements in terms of computer size and execution time. But this is not the same as addressing the complexity issues of vision in general.

The task of visual search has not been de­ fined in computational terms by the psychology com­ munity. According to the definition provided in Rabbitt [Rabbitt, 1978], a visual search task is a categorization task in which a subject must distin­ guish between at least two classes of signals, goal signals which must be located and reported and background signals which must be ignored. This de­ finition does not specify how signals are located, how signals are represented, nor how goal and back­ ground are distinguished. In most, but not quite all, experiments of this type, the subject knows the goal before viewing the stimulus. The goal is most often simply shown visually, although in some experiments verbal descriptions are given instead. Visual search experiments typically measure response times for the categorization of signals. Categorization yields a yes/no answer; other types of experiments ask sub­ jects to report on other aspects of the stimulus as well, but these are not considered in this paper. In experiments where the subject knows the goal before viewing the stimulus, observed response times give linear functions of the size of the display (or number of items in the display). Moreover, the search is a linear one because the slope of the negative case is twice that of the positive case. The literature docu­ menting this is large (see [Nakayama & Silverman 86] or [Treisman 88] for example). The data on response time characteristics if the goal is unknown is less conclusive and rather sparse. Treisman and Sato report that unknown goal search produces overall increase in response times, but some show no changes in slope while others show large changes [personal communication]. It is as if features were inhibited in several successive passes, allowing un­ known goals to emerge at different points in the search sequence. The former experimental setup corresponds to my definitions of Task-Directed Visual search while the latter is Bottom-Up Visual Search, both of which are presented later.

Response times are intimately connected to the speed of processing, the amount of processing machinery devoted to the task and the algorithm that is used to solve the task. The study of compu­ tational complexity measures the cost of solving problems, and is thus it is natural to ask whether the tool of complexity can be productively applied to the understanding of visual search performance in humans.

An earlier paper describes some of the pos­ sible approximations and optimizations that human vision may be using [Tsotsos 1988a] while a compan­ ion paper provides supporting neurophysiological and psychophysical evidence for this position [Tsot­ sos 1988b]. It should be noted that there is nothing inherent in the problem or the proof procedure that prohibits the applicability of the proof for signals of a different dimension or modality, for example, speech. It will be claimed therefore, without explicit proof that auditory or other perceptual search tasks are also NP-Complete for bottom-up strategies and have linear time complexity for task-directed stra­ tegies.

A Computational Defmition of Visual Search

The general version of visual search seeks to find the subset of the test image that matches the goal, using some definition of 'match', and in its full generality includes the possibility of noisy or partial matches. The problem is viewed as a pure informa­ tion processing task, with no assumptions made about how the data may be presented or organized. The description presented is an abstract one, and is not intended as an implementation level characteri­ zation. Further, the problem may ·be of arbitrary size and may use arbitrary stimulus qualities. Other characterizations of visual search may be possible; however, it is suggested that all useful ones will in­ clude the notions of images, measurements over im­ ages, and constraints that must be satisfied.

A test image containing an instance of the goal is created by translating, rotating, and/or scal­ ing the goal, and then placing it in the test image. The test image may also contain confounding infor­ mation, such as other items, noise, and occluding objects, or other processes may distort or corrupt the goal. Due to image discretization, there are a finite but large number of possible transforms for a given image: the goal may be translated to anywhere in the test image; the goal may be rotated about its origin by any angular amount; and, the goal may be scaled in two directions by arbitrary amounts. Since images are discretized, there are only a finite number of possibilities along each of these dimen­ sions that would lead to distinct images. 2D spatial transforms are well-known.

The question posed by visual search has two variants: a bottom-up and a task-directed version. In the bottom-up case, the goals are either not known in advance or even if they are they are not used, except to determine when the search ter­ minates. The task-directed case uses the goal to as­ sist in optimizing the solution to the problem. Both will be addressed by the following analysis.

The solution to visual search involves solv­ ing a sub-problem, which we call Visual Match. Given a 2D spatial transformation of the goal, the Visual Match procedure measures the fit of goal to test image and makes a yes/no decision as to its sui­ tability. Therefore, an algorithm for Visual Search may be the following:

1. For each goal:
2. If transform hypotheses not exhausted then hypothesize a new 2D spatial transformation else exit this loop and return 'no'
3. Apply transform to hypothesize location, orientation and scale of goal in test image
4. Execute the Visual Match procedure
5. If Visual Match returns 'yes' exit and return 'yes'

else go back to step 2.

So, the input to the Visual Match procedure is two images (test and goal after a transformation) and a method of measuring goodness of fit. In many ex­ periments, no scale or rotation is present, so in such cases, the only parameter to hypothesize is location. The first theorem presented will be specific for bottom-up Visual Match. An instance of the Visual Match problem is specified as follows: ·

• A test image I
• A goal image G, modified using a 2D spatial transformation
• A difference function diff(p) for p E I, diff(p) E R~

(R~ is the set of non-negative real numbers of fixed precision p)

• A correlation function corr(p) for p E I, corr(p) E R~
• Two thresholds, fJ and <P, both positive integers

The task posed by Bottom-up Visual Match is:

Given a test image, a difference function, and a correlation function, is there a subset of pixels of the test image such that the difference between that subset and the corresponding subset of pixels in the goal image is less than a given threshold and such that the correlation between the two is at least as large as another specified threshold?

In other words, is there a set I' ~ I such that it simultaneously satisfies

One point regarding the above specification of visual matching must be emphasized. This definition is one which forces a bottom-up approach to the solu­ tion of visual matching. The goal image is not per­ mitted to provide direction to any aspect of the com­ putation other than in the computation of the diff and corr functions. The constraints given must be satisfied with subsets of the input image. It is not unexpected that this definition involves two con­ straints to be simultaneously satisfied and that the two constraints represent error and size satisfaction criteria. Note that this definition does not force ac­ ceptance of only the 'best' match, but accepts any 'sufficiently good' match. This is very similar to many other kinds of recognition definitions. For ex­ ample, the standard definition of region growing in­ volves the maximal contiguous subset of pixels that satisfies a given property [Ballard & Brown 82]. Moreover, this definition should not be interpreted as a template-matching operation. Although tem­ plate matching may 'be posed in the above manner, there is nothing inherent in the definition to exclude other matching forms - the notions of image points, measurements, and constraints representing large enough size and low enough error are ubiquitous in visual matching definitions. Details on how this par­ ticular collection of data may represent the Visual Match problem follow.

1. A test image I is the set of pixel/measurement quadruples (x,y,j,mj)· x,y specify a location in a Eu­ clidean coordinate system, with a given origin. Note that the locations are not necessarily contiguous. Mi is the set of measurement types in the image, such as colour, motion, depth, etc., each type coded as a distinct positive integer. mj is a measurement token of type j, represents scene parameters, and is a non-negative real number of fixed precision, that is with positive error due to possible truncation of at most p. (Only a finite number of bits may be stored). I' ~I is a sub-image of I, i.e., an arbitrary subset of quadruples. It is not necessary that all pix­ el locations contain measurements of all types. Further, it is not necessary that the set of pixels be spatially contiguous. For ease of notation, i,.,y,j has value mj. If j f. Mi or if the x,y values are outside the image array then i,.,y,j = 0.
2. A goal image G is a set of pixel/measurement quadruples defined in the same way as I. The set of x,y locations is not necessarily contiguous. M 1 is the set of measurement types in the goal image. The types correspond between I and G, i.e., type 3 in one image is the same type in the other. The two sets of measurement types, however, are not neces­ sarily the same. The coordinate system of the goal image is the same as for the test image and the ori­ gin of the goal image coincides with the origin of the test image. g,.,y,j has value mj. If j ¢ M 1 or if the x,y values are outside the image array g,.,y,j = 0.
3. For purposes of the proof, the diff function will be the sum of the absolute values of the point-wise differences of the measurements of a subset of the test image with the corresponding subset of the goal image. It is expressed as follows for an arbitrary sub­ set I' of the test image:

This sum of differences must be less than a given threshold fJ in order for a match to be potentially ac­ ceptable. Note that other specific functions that could find small enough values of some other pro­ perty may be as suitable. The threshold is a positive integer.

4. Since a null I' satisfies any threshold in the above constraint, we must enforce the constraint that as many figure matches must be included in I' as possi­ ble. 2D spatial transforms that do not align the goal properly with the test items must also be eliminated because they would lead to many background to background matches. One way to do this is to find large enough values of the point-wise product of the goal and image. This is also the cross-correlation commonly used in computer vision to measure simi­ larity between a given signal and a template. A second threshold, <P, provides a constraint on the ac­ ceptable size of the match. Therefore,

Note that there is no claim here that the al­ gorithm necessarily corresponds to human perfor­ mance. The function definitions are given primarily for purposes of the proof and are claimed to be rea­ sonable ones. It is possible to provide other func­ tions for differ~nce and correlation and reconstruct similar proofs using them.

The Complexity of Bottom-Up Visual Matching

The bottom-up visual match problem as stat­ ed above has exactly the same structure as a known NP-Complete problem, namely the Knapsack Prob­ lem [Garey & Johnson 1979). Therefore, it would seem that a direct reduction (by local replacement) of Knapsack to Visual Match is the appropriate proof procedure. The formal statement of Knap­ sack follows:

Knapsack

instance: Finite set U

for each u E U there is a function s(u) E z+

(the set of positive integers)

and a function v(u) E z+

positive integers B, K

question: Find a subset U' ~ U such that

The following then is the main theorem:

Theorem 1:

Bottom-Up Visual Matching is NP-Complete.

It must be clear that this problem is NP­ Complete because it shares with the Knapsack prob­ lem the following characteristics: an arbitrary subset of the input may be the correct solution; and, two constraints must be satisfied simultaneously. Other aspects of the problem statement such as the specif­ ic form of the functions or the fact that real numbers of fixed precision are used do not lead to the NP-Completeness.

One problem must first be solved before proceeding to the reduction. The statement of Visu­ al Match involves images whose measurements may be non-negative real numbers (of finite precision p as stated in the original problem). By stating a preci­ sion p, we mean that the significant digits whose value is less than p are not represented . . Therefore, a f'IXed number of bits are required to represent each value. This is easily solved by first proving that Knapsack with non-negative real numbers is NP­ Complete. It should be stressed that the use of real numbers versus integers in no way leads to the NP­ Completeness of the problem - the inherent struc­ ture of the problem is the same as that of Knapsack, regardless of the representation.

Knapsack-R1

instance: Finite set A

and a function z(a) E R1

for each a E A there is a function w(a) E R1 (the set of non-negative real numbers of fixed precision f)

positive integers C, D

question: Find a subset A' ~ A such that

The proof of NP-Completeness is trivial since the structure is identical. Now we are ready to prove the main theorem of this section.

Proof:

Let the set A, the functions w and z and the integers C and D specify an arbitrary instance of Knapsack­ R1. Set M; = M 8 = {1}. Define a test image and a goal image to be of size r I A r/2 l by r I A r/2 1Since I A I is less than or equal to r I A r/2 1 2 ' r I A 1 1 /2 l 2 - I A I elements of each image will be of value 0, i.e, they join the background in the image. Therefore, I I I= r I A 1 1 /2 f.

The elements of the set A will be used to determine values for the elements of the goal and test images in the following way. Set

for each a E A. p is the point with location (x, y) within both images, and the location is set arbitrari­ ly, as long as each position is used and each unique position is associated with a unique element of A. It is clear from the above why the number 0 must be included as possible values for the functions w and z (it is not in Knapsack) because the difference func­ tion may have value zero, and because the back­ ground has value zero and thus the correlation func­ tion may be zero as well. A correspondence has now been set up between pixels in the test and goal image and elements of the set A. A subset of A has an associated subset of I, and the value of the differ­ ence and correlation functions correspond directly to values of the functions w and z for the corresponding element of A. Now one can solve for the values of g and i given the above pair of equa­ tions, for each spatial position. For ease of nota­ tion, g will be used for g,.,y, 1 and similarly for i. Since i must be non-negative, if we wish g ~ i, then

It does not matter which assumption is made. The problem with this is the fact that the square root may be irrational and thus require an infinite number of bits to represent. This is solved by using the precision p, as given above, thus explaining the need to include this precision in the original defini­ tion. Thus if each value is truncated, then the error f in each would be less than ·p. The value of p can be anywhere within the open interval:

This expression will be derived shortly. The error in the values can be stated explicitly as:

The error for g is the same as for i since no further approximations are necessary.

Next we must address the effect of this ap­ proximation on the diff and corr functions. It should be clear that if there were no truncation error, then the correspondence between the Visual Match problem and Knapsack - RJ is complete and the proof is also complete. In fact, the approxima­ tions do not affect the diff function at all, only the corr function. The diff function becomes

The errors cancel out since they are due to a single source. Therefore, the sums are the same, and if () is set to C, the difference constraint will be satisfied by exactly those subsets that would satisfy it for the Knapsack problem. On the other hand the corr function becomes:

There is an error term of f X (f - icorrect - gcorrect). In an exact representation, it is clear that the values of corr are exactly those of the function z for corresponding subsets. So, we need to show that as £ goes to zero, the error in the sum of the corr values also goes to zero. The largest possible value off is p. In the Knapsack-RJ problem, the sums of the values of the function z(a) for the subsets of A are ordered and each is separated from the other by at least the value off, by definition. It would then be sufficient to show that for p sufficiently small,

i.e., the precision of values is higher than in Knapsack-RJ. The largest possible subset is the en­ tire image, so if this inequality is true for the entire image, then it is also true for all other subsets. Since we do not know the correct values of i and g and we only have the computed values, substitute those into the above expression, giving:

It remains to be shown that there exists some non­ zero value of p that satisfies the above inequality. The value of p that satisfies the inequality is less than the root of:

The values of icomputed and gcomputed are not known before their computation, but the value of p is part of the problem definition and must be known before computation. Therefore, we can replace them with smaller known values and not affect the end result. Since w(a) = g- i, then w(a) is less than g + i, and

Substituting this into the quadratic equation above and solving for p gives:

Since the solution must be positive there is only one possible root (and it is real). All variables have values that are known before the computation of the image elements. The value of precision for the problem can then be stated as any value of p such that 0 < p < p'. Given this precision, which is less than that of the original Knapsack-RJ problem, and if <P is set to D, it follows directly that the the subsets of the image that satisfy the second con­ straint are exactly those corresponding to the subsets of A that satisfy the second constraint of the Knapsack-RJ problem. Therefore, set A' exists if and only if I' exists and Bottom-Up Visual Match is NP-Complete. But, since Visual Match is a sub­ problem of visual search, the Bottom-up Visual Search problem is also NP-Complete.

The Complexity of Task-Directed Visual Search

If we consider task-directed optimizations using the goal item, it is easy to show that the prob­ lem has linear time complexity. The key is to direct the computation of the difference and correlation functions using the goal rather than the test image. However, we still seek the appropriate subset of the test image. If there is a match that satisfies the con­ straints, then its extent can be predicted in the test image; all locations are possible. The Task-Directed Visual Match task is stated as follows:

Given a test image, a goal image, a difference func­ tion, and a correlation function, is there a subset of pixels of the test image such that the difference between that subset and the corresponding subset of pixels in the goal image is less than a given thres­ hold and such that the correlation between the two is as large as possible? In other words, is it true that

Note that the definition of diff and corr have changed slightly in that the pixel locations and meas­ urement set used are that of the goal rather than the test image. The computation of the diff and corr functions is driven by the goal image and the meas­ urements present in the goal. A simple algorithm is apparent. First, center the goal item over each pixel of the test image; compute the diff and corr meas­ ures between the test and goal image at that posi­ tion; among all the positions possible, choose the solution that satisfies the constraints. The resulting time complexity function for visual match would be 0 ( I G I X I M 1 I ). In other words, the worst case number of computations of the diff and corr func­ tions is determined by the product of the size of the goal image in pixels and the number of measure­ ments in the goal image. If the complexity of visual search (within which visual match is embedded) is considered, this would add only a multiplicative term I T I to the above function, where this represents the total number of possible rotations, translations and scalings. If display items can be lo­ calized, (via an attentional spotlight), the complexity is linear in the number of items in the display, but all rotations and scalings must still be considered. Since at least one linear algorithm exists, this leads to the second theorem:

Theorem 2:

Task-Directed Visual Search has Linear Time Complexity

Note that no sacrifice of generality is necessary to deal with the task-directed problem. However, this is true only for the decision problem as stated in­ volving perfect matches. If the problem is stated as one required to 'find' the matching image subset, the task-directed version is constrained to find subsets that are the same size and shape as the goal, whereas the bottom-up version can find subsets of arbitrary sizes and shapes. The bottom-up case is still NP-Complete, and the task-directed case is still linear, but they are not as directly comparable. This is true even if partial matches are permitted.

This provides a strong hypothesis: since visu­ al search experimentation in psychology presents a view of search performance as having linear time complexity, and not exponential, the inherent com­ putational nature of the problem strongly suggests that task-directed influences play an important role in human perception.

Conclusions

Complexity theory has not been previously applied to try and uncover the inherent difficulty of behavioral experimental paradigms (for a comprehensive overview of methods that have been applied to uncover the limits of perception see [van Doorn et al. 1984]), even though several researchers are attempting to incorporate the results of such ex­ periments into computational theories. Is it possible that the consideration of the computational difficul­ ty of the experimental task alone could lend insight into the interpretation of response times of human subjects? This paper demonstrated that indeed ad­ ditional insight is possible. The results argue very strongly against purely bottom-up approaches to the general vision problem and to computational model­ ling of human perception. It is claimed without proof that the same results hold for perceptual search tasks in stimulus modalities other than vision.

Visual search is a common if not ubiquitous sub-task of machine vision algorithms. For example, purely bottom-up versions of region growing, shape matching, structure from motion, the general align­ ment problem, and connectionist recognition pro­ cedures, etc., all are specialized versions of visual search in that the algorithms must determine which subset of pixels is the correct match to a given pro­ totype or description. The problems they attempt to solve are therefore NP-Complete. It must be stressed that the NP-Completeness does not depend on the specific functions used for the two con­ straints nor on the representation of images. NP­ Completeness results from the facts that a subset of pixels must be chosen whose extent cannot be predicted a priori, that simultaneously satisfies (as opposed to optimizes) two constraints.

Acknowledgements

The following assisted with the develop­ ment and verification of the proof: Steve Cook, Hector Levesque, Charles Rackoff, Raymond Reiter, and especially Bart Selman and Gilbert Ver­ ghese. The author is a Fellow of the Canadian Insti­ tute for Advanced Research. This research was conducted with the financial support of the Natural Sciences. and Engineering Research Council of Ca­ nada and the Information Technology Research Center, a Province of Ontario Center of Excellence.