Efficient Interpretation Policies

1 Introduction

Interpretation, i.e., assigning semantically meaningful labels to relevant regions of an image, is the core process underlying a number of imaging tasks, including recognition ("is objectX in the image?") and identification ("which object is in the image?"), as well as several forms of tracking ("find all moving objects of typeX in this sequence of images"), etc. [PL95; HR96]. Of course, it is critical that interpretation systems be accurate. It is typically important that the interpretation process also be fast: For example, to work in real-time, an interpreter examining the frames of a motion picture will have only 1/24 of a second to produce an interpretation. Or consider a web-searcher that is asked to find images of, say, aircraft. Here again speed is critical - and most searchers do in fact sacrifice some accuracy to gain efficiency (i.e., they quickly return a large number of "hits", only some of which are relevant). This paper addresses the challenge of producing an interpreter that is both sufficiently accurate and sufficiently efficient.

Section 2 provides the framework, showing how our framework generalizes the standard (classical) approaches to image interpretation, then providing a formal description of our task: given a distribution of possible images and an inventory of "operators", produce a "policy" that specifies when to apply which operator, towards optimizing

Russell Greiner

Department of Computing Science

University of Alberta Edmonton, AB T6G 2E8 Canada greiner@cs.ualberta.ca

some user-specified objective function. It describes three different policies that could be used, using a simple blocksworld example to illustrate these terms. The rest of this paper demonstrates that one of these policies, "INFOGAIN" (which uses information gain to myopically decide which operator is most useful at each step), is more effective than the other obvious contenders. Section 3 provides an empirical comparison of these approaches in the context of the simple blocks-world situation. Section 4 extends these ideas to deal with face recognition, using the modern eigenvector approach. (This complements Section 3's classical approach to interpretation.) Section 5 quickly surveys some related work. While the results in this paper demonstrate the potential for this approach, they are still fairly preliminary. Section 6 discusses some additional issues that have to be addressed towards scaling up this system.

2 Framework

2.1 Standard Approaches

There are many approaches to scene interpretation. A strictly "bottom-up" classical approach performs a series of passes over all of the information in the scene, perhaps going first from the pixels to edgels, then from edgels to lines, then to regions boundaries and then to descriptions, until finally producing a consistent interpretation for the entire scene. Most "top down", or "model driven", systems likewise begin by performing several bottom-up "sweeps" of the image - applying various low-level processes to the scene to produce an assortment of higher-level tokens, which are then combined to form some plausible hypothesis (e.g., that the scene contains a person, etc.). These systems differ from strictly bottom-up schemes by then switching to a "top-down" mode: given sufficient evidence to support one interpretation, they seek scene elements that correspond to the parts of the proposed real-world object that have yet to be found [LAB90].

Notice the model-based systems have more prior knowledge of the scene contents than the strictly bottom-up schemes - in particular, they have some notion of "models" - which they can exploit to be more efficient. We propose going one step further, by using additional prior knowledge to further increase the efficiency of an interpretation system. Consider a trivial situation in which we only have to determine whether or not a "red fire-engine" appears in an image; and imagine, moreover, we knew that the only red object that might appear in our images is a fire-engine. Here it is clearly foolish to worry about line-detection or region-growing; it is sufficient, instead, to simply sweep the image with an inexpensive "red" detector. Moreover, if we knew that the fireengine would only appear in the bottom third of the image, we could apply this operator only to that region.

This illustrates the general idea of exploiting prior knowledge (e.g., which objects are we seeking, as well as the distribution over the objects and views where they might appear) to produce an effective interpretation process. In general, we will assume our interpretation system also has access to the inventory of possible imaging operators. Given this collection of operators, an "interpretation policy" specifies when and how to apply which operator, to produce an appropriate interpretation of an image.

Our objective is to produce an effective interpretation policy - e.g., one that efficiently returns a sufficiently accurate interpretation, where accuracy and efficiency are each measured with respect to the underlying task and the distribution of images that will be encountered. Such policies must, of course, specify the details: perhaps by specifying exactly which bottom-up operators to use, and over what portion of the image, if and when to switch from bottomup to top-down, which aspects of the model to seek, etc. These policies can include "conditionals"; e.g., "terminate on finding a red object in the scene; otherwise run procedure CG". They may also specify applying a particular operator only to specified regions of the image (e.g., seek only near-horizontal edges, only in the upper left quadrant of the image). Based on the information available, this interpretation policy could then use other operators, perhaps on other portions of the image to further combine the tokens found.

2.2 Input

We assume that our interpretation system "
CB" is given the following information:

BR The distribution of images that the
CB will encounter, encoded in terms of the distribution of objects and views that will be seen, etc. (Here we assume this information is explicitly given to the algorithm; we later consider acquiring this by sampling over a given set of training images.)

As a trivial example, we may know that each scene will contain exactly BEBH sub-objects, each occupying a cell in a BH A2 BH grid; see Figure 1. Each of these cells has a specified "color", "texture" and "shape", and each of these properties ranges over BG values. (Hence, we can identify each image with a BH A2 BH A2 BF BP BJBH tuple of values, where each value is from CUBDBN BEBN BFBN BGCV.) Moreover, our
CB knows the distribution over these BG BJBH possible images; see below.

BR The task includes two parts: First, what objects the
CB should seek, and what it should return - e.g., "is there an airplane in image" or "is there a DC10 centered at CJ BGBFBN BLBE CL in the image", etc. In our trivial blocks-world case, we simply want to know which of the images is being examined.

Second, the task specification should also specify the "evaluation criteria" for any policy, which is based on both the expected "accuracy" and its expected "cost". In general, this will be a constrained optimization task, combining both hard constraints and an optimization criteria (e.g., minimize some linear combination of accuracy and cost, or perhaps maximize the likelihood of a correct interpretation, for a given bound on the expected cost).

For this blocks-world task, we want to minimize the expected cost and also have BDBCBCB1 correctness, assuming the operators are perfect.

• BR The set of possible "operators" includes (say) various edge detectors, region growers, graph matchers, etc. For each operator, we must specify
• AF its input and output, of the form: "given a set of pixel intensities, returns tokens representing the regions of the same color";
• AF its "effectiveness", which specifies the accuracy of the output, as a function of the input. This may be a simple "success probability", or could be of the form: "assuming noise-type CF, can expect a certain ROC curve" [RH92];
• AF its "cost", as a function of (the size of) its input and parameter setting.

When used, each operator may be given some arguments, perhaps identifying the subregion of the image to consider.

Here, we consider three operators:  BD (resp.,  BE ,  BF ) for detecting the "value" of color (resp., "texture", "shape"); each mapping a CJ DCBN DD CL location of the current image to a value in CUBDBN BEBN BFBN BGCV. (Note that location is an argument to the operator.) We assume that each operator, when pointed at a particular "cell", will reliably determine the actual value of that property at the specified location, and will do so with unit cost. (Section 4 considers less trivial operators.)

For each situation, we assume our interpreter will be given a series of scenes, but will always have the same objective and criteria; e.g., it is expected to look for the same objects in each image, and has a single objective function. (It is easy to generalize this to deal with environments that can ask different questions for different images, and impose different costs.)

At each stage, our
CB will use its current knowledge (both prior information - e.g., associated with the distribution and the operators - and information obtained by earlier probes) to decide whether B4BDB5 to terminate, returning some interpretation; or B4BEB5 to perform some operation, which involves specifying both the appropriate operator and the relevant arguments to this operator, and then recur.

2.3 Policies

In general, we could represent an
CB explicitly as a large decision tree, whose leaf nodes each represent a complete interpretation (which is returned as the result of the
CB), and whose internal nodes each correspond to a sequence of zero or more operator applications, followed by a test on the original data and/or some set of inferred tokens. Each arc descending from this node is labeled with a possible result of this test, and descends to new node (containing other operators and tests) appropriate for this outcome.

CB AV (CC BP CWBV D1CPDC BN  D1CXD2 CX: TaskSpecification, B4 B5: Distribution,  BP CUD3 CX CV: Operators, 
: Image) Initialize cost BV BMBP BC Evidence DI  BP CWCX While [BV BO BV D1CPDC B2  D1CXD2 BQ D1CPDC DC  B4Obj BP DC CY DI B5] do Select CJD3 BM operatorBN CP BM argumentsCL (based on policy AV,  B4 A1 B5) (Note CP may specify the region to consider) Apply D3B4CPB5 to 
, yielding DA Extend DI  BMBP DI  B7 CWD3B4CPB5BN DACX Update B4 A1 CY DI  B5, based on result Update BV BMBP BV B7 CostCJ D3B4CPB5 CL Return Best Interpretation: CPD6CVD1CPDC DC  B4Obj BP DC CY DI B5

Given that such explicit strategy-trees can be enormous, we instead represent strategies implicitly, in terms of a "policy" that specifies how to decide, at run-time, which operator to use. Figure 2 shows a general interpretation strategy using any of the policies. We will consider the following three policies: 1

Policy RANDPOL: selects an operator 2 randomly.

Policy BESTHYP: first identifies the object that is most likely to be in the scene (given the evidence seen so far, weighted by the priors, etc.) and then selects the operator that can best verify this object [LHD B7 93, p370]: That is, after gathering information from CZ previous operators DI  BP CWD3 BD BP DA BD BN BM BM BM BN D3 CZ BP DA CZ CX, it computes the posterior probabilities of each possible interpretation D7 CX , B4CB BP D7 CX CY DI  B5. To select the next operator, BESTHYP will first determine which of the scenes is most likely - i.e., D7 A3 BP CPD6CVD1CPDC D7 CUB4CB BP D7 CY DI  B5CV - and then determines which operator has the potential of increasing the probability of this interpretation the most: Assume the operator D3 returns a value in CUDA BD BN DA BE BM BM BM BN DA CY CV; then D3 might increase the probability of D7 A3 to bestB4 D7 A3 BN D3 B5 BP D1CPDC CY CUB4CB BP D7 A3 CY DI BN D3 BP DA CY B5CV. Here, BESTHYP will use the operator

Policy INFOGAIN: selects the operator that provides the largest information gain (per unit cost) at each time. This policy computes, for each possible operator and argument combination D3, the expected information gained by performing this operation: BXIGB4CBBN DI B5D3 BP

1 We view RANDPOL as a baseline; clearly we should not consider any system that does worse that this. These empirical studies are designed to test our hypothesis that INFOGAIN will actually work best in practice - and in particular, work better than BESTHYP, which is actually being used in some deployed applications [LHD B7 93].

2 We will use the term "operator" to refer to the operator instantiated with the relevant arguments. Also, we will further abuse notation by writing D3 CX BP DA CX to mean that the value DA CX was obtained by applying the (instantiated) operator D3 CX to the image.

where B4CBCYBXB5 BP  CX B4CB BP D7 CX CYBX B5 D0D3CVB4CB BP D7 CX CYBX B5 is the entropy of the distribution over the interpretations CB given the evidence BX, for BX BP DI  or BX BP CU DI BN D3 BP DA CY CV. INFOGAIN then uses the operator

that maximizes CJBXIGB4 DI  BN D3 B5BPBVB4D3B5CL, where BVB4D3B5 is the cost of applying the operator.

3 Simple Experiments: Blocks World

This section presents some experiments using the simple blocks world situation presented above. They are designed simply to illustrate the basic ideas, and to help us compare the three policies described earlier. Section 4 below considers a more realistic situation.

We first generated a set of BDBCBCBC images, each with 25 subobjects, by uniformly assigning values for color, texture and shape to each of the sub-objects randomly, for each of BDBCBCBC images; we also assigned each a "prior distribution" D4 CX to these images (this corresponds to taking an empirical sample, with replacement). For each run, we randomly select one of the BDBCBCBC images to serve as a target for identification, then used each of the three policies to identify the image.

After observing  CZ BP CUD3 BD BP DA BD BN D3 BE BP DA BE BN BM BM BM BN D3 CZ BP DA CZ CV from the operators in the first CZ iterations, RANDPOL randomly selects a cell BVCJCXBN CYCL CA and an operator D3 CA to probe the value for a property (color, texture etc), insisting only that D3 CA was not tried earlier on BVCJCXBN CYCL CA in any previous iterations of this run. BESTHYP chooses a cell BVCJCXBN CYCL BU and an operator D3 BU to maximize the posterior probability of the most likely image, as explained earlier. Finally, INFOGAIN chooses BVCJCXBN CYCL
BZ and D3
BZ such that BX
BZB4 DI BN D3
BZ B5BPBVB4D3
BZ B5 is the maximum over all possible cell and operator combinations. For each of these policies, the posterior probability is updated after applying the chosen operator on the cell. The process is repeated until the image is identified - i.e., all other contenders are eliminated.

We considered 10 set-ups (each with its own objects and D4 CX 's), and performed 5 runs for each set-up. Over these 50 runs, RANDPOL required on average BHBMBKBE A6BCBMBEBJ probes, BESTHYP BHBMBGBGA6BCBMBFBE probes and INFOGAIN BHBMBFBEA6BCBMBDBF. INFOGAIN is statistically better than the other two policies, at the D4 BO BCBMBD level.

We then performed a variety of other experiments in this domain, to help quantify the relative merits of the different policies - e.g., in terms of the "average Hamming distances" between the images. See [IG01] for details.

While this particular task is quite simplistic, we were able to use the same ideas for the more interesting task of identifying the make and model of a car (e.g., Toyota Corolla, Nissan Sentra, Honda Civic, etc.) given an image of the car that shows its "rear tail lights assembly"; see Figure 3. Again see [IG01] for details.

4 Scaling Up: Face Recognition

We next investigate the efficiency and accuracy of the three policies in the more complicated domain of "face recognition" [TP91; PMS94; PWHR98; EC97]. This section first discusses the prominent "eigenface" technique of face recognition that forms the basis of our approach; then presents our framework, describing the representation and the operators we use to identify faces; then presents our face interpretation algorithm; and finally shows our empirical results.

4.1 Eigenface, and EigenFeature, Method

Many of today's face recognition systems use Principal Component Analysis (PCA) [TP91]: Given a set of training images of faces, the system first forms the covariance matrix A6 of the images, then computes the CZ main eigenvectors of A6, called "eigenfaces". Every training face CW CX is then projected into this coordinate space ("facespace"), producing a vector, AA CX BP CJAX B4CXB5 BD BN AX B4CXB5 BE BN BM BM BM BN AX B4CXB5 CZ CL.

During recognition, any test face CW D8CTD7D8 is similarly projected into the facespace, producing the vector AA D8CTD7D8 , which is then compared with each of the training faces. The best matching training face is taken to be the interpretation [TP91].

Following [PMS94], we extend this method to recognize facial features - eyes, nose, mouth, etc. - which we then use to help identify the individual in a given test image: We first partition the training data into two sets, CC BP CUCW BDBNCX CV (for constructing the eigenfeatures) and CB BP CUCW BEBNCX CV (for collecting statistics - see below), which each contains at least one face of each of the D2 people. Using idB4CWB5 to denote the person whose face is given by CW, we have idB4CW BDBNCX B5 BP CX BP idB4CW BEBNCX B5 for CX BP BDBMBMD2; each remaining CW BDBNCY and CW BEBNCY (CY BQ D2) also maps to BDBMBMD2.

We use PCA on, say, the mouth regions of each CC image, to produce a set of eigenvectors; here eigen-mouths. For each face image CW CX , let AA B4D1B5 CX be "feature space" encoding of CW CX 's mouth-region. We will later compare the feature space encoding AA B4D1B5 D8CTD7D8 of a new image CW D8CTD7D8 against these CUAA B4D1B5 CX CV vectors, with the assumption that AA B4D1B5 D8CTD7D8 AP AA B4D1B5 CX suggests that CW D8CTD7D8 is really person CX - i.e., finding that CZAA B4D1B5 D8CTD7D8 A0

AA B4D1B5 CX CZ is small should suggest that idB4CW D8CTD7D8 B5 BP CX. (Note CZ A1 CZ refers to the  BE norm, aka Euclidean distance.)

To quantify how strong this belief should be, we compute  BP CYCCCY A2 CYCBCY values CUCS CXBNCY CV where each CS CXBNCY BP CZAA B4D1B5 BDBNCX A0 AA B4D1B5 BEBNCY CZ is the Euclidean distance between the "eigen-mouth encodings" of CC's CW BDBNCX and CB's CW BEBNCY . We considered BDBI buckets BU D6 AQ BO for these CS CXBNCY values: BU BC BP CJBCBN BDBCBCB5, BU BD BP CJBDBCBCBN BEBCBCB5, . . . , BU BDBG BP CJBDBGBCBCBN BDBHBCBCB5, BU BDBH BP CJBDBHBCBCBNBDB5. Then, for each bucket BU D6 , we estimate  B4 CS CXBND8CTD7D8 BE BU D6 CY idB4CW D8CTD7D8 B5 BP CX B5 as

where AZCJ idB4CW BDBNCX B5 BP idB4CW BEBNCY B5 CL is the number of CWCXBN CYCX pairs where CW BDBNCX BE CC is the same person as CW BEBNCY BE CB. (We used the obvious Laplacian correction to avoid using BCs here [Mit97].) We also compute

to estimate B4 CS CXBND8CTD7D8 BE BU D6 B5. (Note this is the average over all images CX in the test set CC .) Figure 4 shows a histogram of the CS CXBNCY values, using the 16 buckets for the left eye feature (see below); it also shows the values of AD B4D0CTB5 B4D6B5 for D6 BP BCBMBMBI.

We use these CUAD B4D1B5 B4D6B5CV D6 and CUAQ B4D1B5 B4D6B5CV D6 values to interpret a new test image of a person's face CW D8CTD7D8 . (While the specific image CW D8CTD7D8 is not in CC CJ CB, it is another face of someone who has other faces in CC CJ CB).) We first project CW D8CTD7D8 's mouth region onto the "eigen-mouth"s space, forming the vector AA B4D1B5 D8CTD7D8 , then compare AA B4D1B5 D8CTD7D8 with the stored eigen-mouth projections (from CC ) - computing the values CS CXBND8CTD7D8 BP CZAA B4D1B5 CX A0AA B4D1B5 D8CTD7D8 CZ for each CX in CC . This CS CXBND8CTD7D8 will be in some bucket, say BU D6 BP CJD6BN D6 B7 BDBCBCB5. We then use Bayes Rule to compute the probability that this face is person CX:

(Here, we assume the faces are drawn from the D2 individuals uniformly; hence  B4 idB4CW D8CTD7D8 B5 BP CX B5 BP BDBPD2.)

So far, we considered only a single feature - here, "mouth projections", as indicated by the B4D1B5 superscript. We similarly compute AD B4D2B5 B4D6B5, AD B4D0CTB5 B4D6B5, AD B4D6CTB5 B4D6B5, values associated with the nose, left-eye and right-eye, as well as the AQ B4D2B5 B4D6B5, AQ B4D0CTB5 B4D6B5, AQ B4D6CTB5 B4D6B5 values.

We then used the Na¨ıve-Bayes assumption [DH73] (that features are independent, given the specified person) to essentially simply multiply the associated probabilities: Assume we observed, for each feature CU, CZAA B4CUB5 D8CTD7D8 A0 AA B4CU B5 CX CZ BE BU D6 CU , then

where ABBN AB BC are scaling constants (as the prior is uniform).

(Note: we had also tried computing individual AD B4D1B5 CX B4D6B5 values, specific to each training face CW BDBNCX . However, we found this was too noisy, as the number of relevant instances was too small.)

4.2 Framework

The distribution is the set of all people who can be seen, which varies over race, gender and age, as well as poses and sizes; we approximate this using the images given in the training set. We assume that any test face-image belongs to one of the people in the training set, but probably with a different facial expression or in a slightly different view, and perhaps with some external features not in the training image (like glasses, hat, etc.), or vice versa. Figure 5 shows three training images (top) and four test images (bottom).

Our task is to identify the person from his/her given test image CW D8CTD7D8 (wrt the people included in the training set), subject to the minimum acceptable accuracy ( D1CXD2 ) and the maximum total cost of identification (BV D1CPDC ).

We use four classes of operators,  BP CUD3 D0CT B4CZB5BN D3 D6CT B4CZB5BN D3 D2 B4CZB5BN D3 D1 B4CZB5 CV to detect respectively "left eye", "right eye", "nose" and "mouth". Each specific operator also takes a parameter CZ which specifies the size of the feature space to consider; here we consider CZ BE CUBEBHBN BFBCBN BFBHBN BGBCBN BGBHCV. As discussed above, each instantiated operator D3 BE  takes an input the test image of a face CW D8CTD7D8 , and returns a probabilistic distribution over the individuals.

Each operator D3 CU B4CZB5 (associated with the feature CU BE CUD0CTBN D6CTBN D2BN D1CV) performs three subtasks: SubTask#1 locates the feature CU D8CTD7D8 fromwithin the entire face CW D8CTD7D8 . Here we use a simple template matching technique in which we search in a fixed "window" of size  A2 pixels in CW D8CTD7D8 for any given feature, of size D4 BO  by D5 BO pixels. SubTask#2 then projects the relevant region CU D8CTD7D8 of the test image into the feature space - computing AA B4CUB5 D8CTD7D8 of dimension CZ. SubTask#3 uses this AA B4CUB5 D8CTD7D8 to compute first the values CS CXBND8CTD7D8 BP CZAA B4CUB5 CX A0 AA B4CU B5 D8CTD7D8 CZ for each person CX, then place each CS CXBND8CTD7D8 value into the appropriate BU D6 bucket, and finally compute the probability B4 idB4CW D8CTD7D8 B5 BP CX CYAA B4CUB5 D8CTD7D8 B5 for each person CX, using Equation 1 (possibly augmented with Equation 2 to update the distribution when considering the 2nd and subsequent features); see Section 4.1. For each eigenspace dimension CZ, we empirically identified the cost (in seconds) of the four classes of operators -BVB4D3 D0CT B4CZB5B5 BP BCBMBIBHB7B4CZA0BEBHB5A2BCBMBCBEBD, BVB4D3 D6CT B4CZB5B5 BP BCBMBKBJB7B4CZA0BEBHB5A2BCBMBCBDBH, BVB4D3 D2 B4CZB5B5 BP BDBMBHBG B7 B4CZ A0 BEBHB5 A2 BCBMBCBEBH and BVB4D3 D1 B4CZB5B5 BP BDBMBEBFB7B4CZA0BEBHB5A2BCBMBCBG.While increasing the dimensionality CZ of the feature space should improve the accuracy of the result, here we see explicitly how this will also increase the cost.

4.3 Interpretation Phase

During interpretation, each current policy (RANDPOL, BESTHYP and INFOGAIN) iteratively selects an operator D3B4CZB5 BE . RANDPOL chooses an operator D3 CA and a value CZ CA randomly, subject only to the condition that D3 CA had not been tried before on the image; BESTHYP first identifies the most likely person CX BP CPD6CVD1CPDCB4 idB4CWB5 BP CX CY A1 B5, then choses the instantiated D3 BU B4CZ BU B5 operator that best confirms this hypothesis (that the image belongs to CX person), provided this D3 BU had not been used earlier for this image; and INFOGAIN chooses an instantiated operator D3 BP D3
BZ B4CZ
BZ B5 that has the maximum BXIGB4 A1 BN D3 B5BPBVB4D3B5B5 value. In each case, the operator is applied to the appropriate region in the given test face image and the distribution is updated. . . until one face is identified with sufficiently high probability (BQ  D1CXD2 ) or the system fails (by exhausting all the possible operators, or having cost BQ BV D1CPDC ); see Figure 2.

4.4 Face Recognition Experiments

We used BHBFBG face images of BDBCBE different people, each BLBE A2 BDBDBE pixels, from which we placed BDBKBJ images into CC , another BDBKBJ images into CB (CC and CB are used in the training phase to collect statistics) and used the remaining BEBIBC as test images. As shown in Figure 5, the faces are more or less in the same pose (facing front), with some small variation in size and orientation. 3 We considered all BEBC operators based on the four features listed above and CZ BE CUBEBHBN BFBCBN BFBHBN BGBCBN BGBHCV for each feature.

Basic Experiment: We set  D1CXD2 BP BCBMBL and BV D1CPDC BP BD (i.e., no upper limit on identification cost). In each "set-up", we assigned a random probability to each person. On each run, we picked one face randomly from the test set as the target, and identified it using each of the three policies. We repeated this for a total of BEBH runs per set-up, then changed the probability distribution and repeated the entire process again, for a total of BK set-ups. The cost of recognition on the average was BKBMBJBIBGA6BCBMBHBKBI, BJBMBIBJBGA6BCBMBJBCBE and BIBMBKBDBDA6BCBMBJBCBE

3 B4BDB5 All these faces were downloaded from the web sites whitechapel.media.mit.edu and www.camorl.co.uk. B4BEB5 This work assumes the head has already been located and normalized; if not, we can use standard techniques [TP91] first. B4BFB5 All the experiments reported in this paper were run on a Pentium 200 MHz. PC with 32 MB. RAM running Linux 2.0.35 OS.

seconds for RANDPOL, BESTHYP and INFOGAIN respectively. INFOGAIN is statistically better than the other two policies, at the D4 BO BCBMBD level. (As expected, these policies had comparable identification accuracy here: BKBLBMBDBIB1, BLBCBMBKBGB1 and BLBCBMBKBGB1, respectively.)

Bounding the Cost: In many situations, we need to impose a hard restriction on the total cost; we therefore considered BV D1CPDC BE CUBEBN BGBN BM BM BM BN BDBECV seconds. We then picked one face randomly from the test set, and identified the test image for each of these maximal costs, using each of the three policies. As always, we terminate whenever the probability of any person exceeds  D1CXD2 or if the cost exceeds BV D1CPDC , and return the most likely interpretation.

We repeated this experiment for a total of BDBC set-ups (each with a different distribution over the people) and with BEBH random runs (target face images) per set-up. The accuracy (the percentage of correct identifications) for each policy is shown for various values of BV D1CPDC in Figure 6(a). INFOGAIN has better accuracy than both BESTHYP and RANDPOL. RANDPOL trailed these two policies significantly for low (AK BG seconds) cost.

Varying the Minimum Accuracy: In this experiment, we varied  D1CXD2 from BCBMBD to BCBMBL. For each of these values, we chose a face randomly from the test set as the target and identified it using each of the three policies. During the process, the first person CX in the training set for which  B4 idB4CWB5 BP CX CY A1 B5 BQ  D1CXD2 is returned (or if cost BQ BV D1CPDC , the most probable face is returned). We repeated this for BEBH different target faces (runs) per set-up, and repeated the entire process for a total of BK different set-ups.

We evaluated the results in two different ways. First, Figure 6(b) compares the percentage of wrong identifications of each policy, for each  D1CXD2 value. INFOGAIN has fewer wrong identifications than BESTHYP and RANDPOL for low accuracy. As expected, for sufficiently high accuracy, all three policies have comparable number of wrong identifications. Secondly, Figure 6(c) compares the average cost of each policy, for each  D1CXD2 value. Again, INFOGAIN has lower cost than BESTHYP and RANDPOL, while RANDPOL trails the other two policies significantly.

5 Literature Survey

Our work formally investigates the use of decision theory in image interpretation, explicitly addressing accuracy versus efficiency tradeoffs [GE91; RSP93]. Geman and Jedynak [GJ96] used information theoretic approaches to find the "optimal sequence of questions" for recognizing objects - hand-written numerals (0-9), and highways from satellite images. Our work also uses information theoretic methods to compute the expected information gain, but we differ as we are seeking the most cost-effective sequence of interpretation operators, rather than the shortest sequence of questions; this forces us to explicitly address the cost vs accuracy tradeoffs. Sengupta and Boyer [SB93] presented a hierarchically structured approach to organizing large structural model-bases using an information theoretic criterion. We do not have explicit model-bases, but consider various interpretation policies that decide, at run time, which operators to apply to what regions of an image, based on expected information gain of the operators.

We used the domain of face recognition to test our approach. While there are several approaches to face recognition [TP91; PMS94; PWHR98; EC97], none explicitly address the issues of efficiency. We used one of the popular and successful methods as the basis to our approach and performed a systematic study of the various efficiency and accuracy related issues.

Levitt et al. [LAB90; BLM89; LHD B7 93] have applied Bayesian inference methods and influence diagrams to image interpretation. We however provide a way to adjust the optimization function. (Our work also further motivates the use of "maximum expected utility" in such systems.)

As our system is seeking a policy that maps the state (here current distribution over possible interpretations) to an appropriate action, it can be viewed as solving a Markov decision problem (MDP), which puts it in the realm of reinforcement learning; cf., [Dra96]. Our research objective differs as we are considering a range of reward functions, which can be various combinations of accuracy and efficiency (some of which may be difficult to word within a MDP framework). We anticipate being able to use many of the Reinforcement Learning techniques as we begin to consider interactions between the actions, and going beyond our current myopic approach.

Finally, there is a growing body of work on providing precise characteristics of various imaging operators, which quantify how they should work [Har94; RH92]. We hope to use these results to quantify the effectiveness of our operators, to help our algorithms decide when to use each. There is also work on building platforms that allow a user to manually assemble these operators [Fua97; PL94], often using an expert-system style approach [Mat89].

Here, we are taking a step towards automating this process, wrt some given task. In particular, our approach suggests a way to automatically assemble the appropriate imaging operators (i.e., without human intervention), as required to effectively interpret a range of images.

6 Conclusions

Future Work: While our face recognition results show that our ideas can be applied to a complex domain, there are a number of extensions that would further scale up our approach. Some are relatively straightforward - e.g., extending the set of operators to cover more features; this will help deal with larger number of faces in the training set, with better accuracy and lower interpretation costs. In other contexts, we will need to deal with thornier issues, such as operators that rely on one another. This may be because one operator requires, as input, the output of another operator (e.g., a line-segmenter produces a set of tokens, which are then used by a line-grower - notice this precondition-situation leads to various planning issues [CFML98]), or because the actual data obtained from one operator may be critical in deciding which next operator (or parameter setting) to consider next: e.g., finding the fuselage at some position helps determine where to look for the airplane's wings.

Clearly we will need to re-think our current myopic approach to cope with these multi-step issues; especially as we expect heuristics will be essential, as this task is clearly NP-hard [Sri95]. Finally, all of this assumes we have the required distribution information. An important challenge is more efficient ways to acquire such information from a set of training images - perhaps using something like Qlearning [SB98].

Contributions: This paper has three main contributions: First, it provides a formal foundation for investigating efficient image interpretation, by outlining the criteria to consider, and suggesting some approaches. Secondly, our implementation is a step towards automating the construction of effective image interpretation systems, as it will automatically decide on the appropriate policies for operator applications, as a function of the user's (explicitly provided) task and the available inventory of operators. Finally, it presents some results related to these approaches - in particular, our results confirm the obvious point that information gain (as embodied in the INFOGAIN policy) is clearly the appropriate measure to use here - and in particular, it is better than the BESTHYP approach. This observation is useful, as there are deployed imaging systems that use this BESTHYP approach [LHD B7 93].

Acknowledgements

RG gratefully acknowledges support from NSERC for this project. RI thanks Sastry Isukapalli for several discussions, general comments and help on the paper. Both authors thank Ramesh Visvanathan, and the anonymous reviewers, for their many helpful and insightful comments.