Aspects of the Detection of Scene Congruence

ASPECTS OF THE DETECTION OF SCENE CONGRUENCE*

Martin A. Fischler Lockheed Palo Alto Research Laboratory Palo Alto . California 94304

ABSTRACT

The problem of matching two scenes . one contained in the other. arises in many practical picture processing tasks including stereocompilation. classification of photographic data . and map matching for navigation and guidance . Because the images are not exact rep­ licas . but rather noisy and perhaps geometrically dis­ torted versions of the original scenes, it is necessary to develop a body of theory capable of providing an­ swers to questions concerning effects of various types of error, and means for minimizing th-e effects of such errors . This paper presents a "decision space" ap­ proach to the problem for dealing with small amounts of noise and distortion, and a promising new technique for dealing with "rubber sheet" distortion .

INTRODUCTION

Assume we are given images of two scenes, one scene contained in the other, and we wish to determine where the contained scene appears (i .e., has a best match) in the containing scene. We further assume that the im­ ages are not exact replicas of either of the scenes , but rather noisy and perhaps geometrically distorted ver­ sions of each. The solution to this problem (the de­ tection of scene congruence) has applications in many practical picture processing tasks including stereo­ compilation, classification of photographic data , ter­ rain change detection. map matching for navigation and guidance , etc.

In many of these tasks it is possible to assume that the noise and distortion processes result in relatively small random differences between the contained and containing scenes. Under these conditions , it is both possible and desirable to employ mathematical tech­ niques in contrast to the heuristic approach currently used for general scene analysis. (Reference (1) is a recent survey which considers much of the general scene analysis work .] This allows the formulation of a comprehensive mathematical model which can provide the insight needed to estimate system performance for different proposed configurations. In particular, such a model must address itself to the generic noise and distortion processes peculiar to scene imaging de­ vices, and characterize the effects of simplifications and uncertainties which will necessarily be inherent in any practical system.

This paper is a summary of Fischler (2) and is con­ cerned with the development of a body of theory needed to implement (especially using digital techniques) practical systems for tasks given above. It considers such questions as: ( 1] What is the nature of optimal decision procedures for the detection of scene congruence under fairly general noise assumptions? . ( 2) How do error processes , such as scale change . ro­ tation error, sensor amplitude gain and bias varia­ tions. etc . , affect system performance . and how can the effects of these errors be minimized without pay­ ing an excessive cost penalty? . ( 3) How do various scene properties or characteristics influence system accuracy? . and [ 4) What procedures are available for situations in which the small error model is not realistic?

·work sponsored by the Lockheed Independent Research Program.

In any practical situation. the instruments used ·to view. process . and store scene information have finite resolution or bandwidth . Therefore , invoking the Shannon Sampling Theorem. we can restrict our atten­ tion to scenes which can be characterized by a finite array of bounded integers, each integer representing the sensed scene attribute (such as light intensity for a photographic sensor, or radiometric temperature if we are employing an infrared sensor . etc . ) at some specified geometric location in the given scene . Ques­ tions concerning the analog-digital interface are dis­ cussed in Fischler (2) but will be omitted from this summary .

The framework for much of the analysis presented in this paper is established by considering each match location in the containing scene (a point of potential match between the containing and contained scenes) as being associated with a distinct class . The "ideal " representative of each class is the fixed size segment of the containing scene centered at the corresponding match location. The containing scene is called the reference map (RM) , and the contained scene is called the sensed map (SM) . Any given S:t.I is now assumed to be some (ideal) RM segment which has been per­ turbed by a specified set of noise and distortion proc­ cesses. Match point determination is thus reduced to a classification task . (See Fig. 1. )

Each map, represented by a collection of N discrete numbers . is considered to be a point in a "signal space" of N-dimensions . Using decision theory con­ cepts [see Refs . (3) through (12)] , we show that satis­ fying a minimum error criterion for match point de­ termination corresponds to measuring some weighted distance function between the signal space image of the SM and each of the RM segments .

To present results having the greatest degree of gen­ erality and intuitive appeal, geometric arguments form the basis for most of the development presented here . These geometric arguments are supported by a paral­ lel algebraic development given in Fischler (2).

After developing the decision theoretic model, we con­ sider the effect of scale and rotation error (due to un­ certainties in sensor position ·and orientation) on our decision metric. This analysis is followed by a discus­ sion of amplitude gain and bias errors, i.e., linear transformations of the resolution element values which might be introduced by changes in the medium between the scene and the sensor , or by variations in the sens­ ing system itself. In particular, we consider how the effects of these errors can be eliminated (through "normalization") without specifically detecting their

• b . All Possible I x 2 RM Segments in the Reference Map
• c . R!\t Segments and Sensed Map Depicted in Signal Space

Fig . I Formulation of the Scene Congruence Problem as a Classification Problem With Its Associ­ ated Signal Space Representation

presence. The viewpoint of minimizing error effects, rather than detecting and correcting for them, is re­ lated to system cost considerations.

The question of remote error (RE) is considered next. RE is defined as the occurrence of two or more RM segments which are essentially identical to the SM, but are (typically) separated by some nontrivial physical distance in the RM. The relation of probability of RE to such physical quantities as signal-to-noise ratio and map spatial frequency spectrum is developed . It is also shown that normalization increases the probability of RE .

In many applications, especially those concerned with s cene matching for guidance and navigation, the RM (and possibly the SM) may be freely chosen . A discus­ sion of the factors affecting this choice is given, to­ gether with some supporting experimental data .

The final section of this paper is concerned with the question of extreme distortion . In spite of their ap­ parent generality, unaugmented statistical decision theory techniques are useful only in situations where error and distortion processes are held under reason­ ably tight control. When this is not the case , a differ­ ent approach to decision making is required . A new. efficient, algorithmic technique for locating one scene in another is presented for cases of extreme distor­ tion. This algorithm is an important development in that it has a computation time requirement which grows linearly with map size. even though it performs a combinatorial search for a best fit using a decom­ posed SM. For intermediate distortion problems . a simpler technique also involving SM decomposition is shown to be an effective solution .

DECISION PROCEDURES, NOISE PROCESSES, AND SCENE CHARACTERIZATION

As noted in the introduction, this section will first establish a decision theoretic model for match point determination; it then considers the effects of various noise and distortion mechanisms on the decision proc­ ess, as well as the significance and consequences of normalization. A scene characterization technique based on expressions devised for expected error is offered together with some supporting experimental data.

Since this paper is actually a contracted version of Fischler (2), figure and equation numbers from the original version will be retained where possible to facilitate cross-reference . One effect of this conven­ tion will be the omission of figure numbers 2, 3, and 8 . References to appendices refer to the original paper although abbreviated appendix material is in­ cluded where deemed necessary for comprehension .

A Decision Theoretic Model for Match Point Determination

Let the vector X = (XI , x2 , .. . , xN) designate the SM. Associated with the ith possible digital match location in the RM is a SM-sized subset of the RM which we designate as

Thus (see Fig. I) the RM is decomposed into a set of R "N-tuples" (i.e ., vectors with N components) . The SM is a single N-tuple , which we assume is one of the RM(i) which has been perturbed by a specified set of noise and distortion processes.

We would now like to assign X (the SM) to some RM(i) according to a scheme which will minimize the resultant probability of error. That is , we will use a minimum error criterion.

To minimize error, we must assign X to that RM(i) such that Pr I Y i I XI is maximized. The Bayes rule for computing the a posteriori probability is ·

If we assume that all Yi are equally likely to occur (i . e . , the SM is equally likely to have been derived from any location in the RM) , then we have :

Our decision procedure then consists of evaluating Pr[XIYi) for all values of i (1 :5 i :5 Rj and assign­ ing X to that RM(i) for which Pr[XIYi is maxi­ mum .

To obtain results having the greatest degree of gener­ ality, and still leave our reasoning open to intuitive appraisal, we will employ geometric analysis in a suitably defined "signal space ." Appendix B contains a parallel algebraic development which will be used to verify geometrically derived conclusions , and giv.e some insight into the form of the "expected error" expressions under more specific noise assumptions .

Let us consider an N-dimensional Euclidean Hyper­ space (EN) in which each of the N coordinate axes corresponds to one of the N components of a vector representing a RM(i) or SM. Thus , any given map will be represented by a single point in EN . Figure 1 illustrates this concept for the case of E2 and five arbitrarily contrived maps .

A number of observations can be made about "distance" in signal space (see Appendix A) . Given points Y i = (Yn . Yi2 , . .. , YiN) and Yj , the Euclidean distance between them is dij , where:

The quantity

will be called the energy of RM(i) , and in Appendix A the justification for this designation is given . Thus, the square of the distance of a point Yi [representing RM(i)) from the origin is equal to its "energy" and proportional to its average power. All RM(i) with average power less than or equal to d2 IN lie within the circle centered at the origin with radius d . Simi­ larly, a RM(i) disturbed by additive noise with aver­ age power d~ /N would lie somewhere on a circle of radius dn centered at Y i . In the absence of any special knowledge or assumptions about noise favoring one cell of a RM(i) over another, or one RM(i) over another, it is reasonable to assume that the noise af­ fects each Yik equally and independently for all (i , k) ; that the noise has zero mean value; and that the proba­ bility of a specific disturbance is inversely related to the magnitude or power associated with the disturb­ ance . That is , the noise is spherically symmetric with the same noise power for all map elements . This situ­ ation is illustrated (for N = 2) in Fig. 4a. The equi­ probability contours of a noise-disturbed signal .

• a . Case of Spherically Symmetric Noise V.'hich Is Identical and Uncorrelated for All Variables (o 1 = o) ; pi) = 0)
• b . Case of Elllpsoidally Symmetric Noise Which Is Not Identical but Is Uncorrelated for All Variables (o 1 ., oj; pi) = 0)
• SUFf1CIENT CONDITIONS FOR A LINEAR DECISION SURFACE: ELUPSOIDALLY SYMMETRIC MONOT0t.1CALLY DECREASING EQUAL COVARIANCE MATRICES

~-------------------------·1

1. Case of Elllpeoidally Symmetric Noise Which Is Not Identical and May Be Correlated for All Variables (o 1 "' o); pi)., 0)

Fig. 4 Probability Contours and Decision Surfaces

nominally located at 1-'1 (J.t2) . will be hyper spheres centered at 1-'1 (J.t2) ·

Assume we are given a sensed map X = (x1 , x2). and we must decide whether it should be assigned to RM(i) represented by 1J 1 or RM(j) represented by 1-'2 . Given the situation described above, a minimum error decision procedure would be to compute d(x,IJ1), d(X, IJ2) and

In terms of the signal space representation, we can partition signal space by a hyperplane (dashed line in Fig. 4a) which is the perpendicular bisector on the line joining 1-' 1 and 1-'2 . Then . if X falls on the same side of the hyperplane as l-'1(1l2) , we assign it to~-'1(1l2> ·

Figure 4b depicts a situation in which we know or as­ sume that our measurement of x2 is less reliable (or subject to more variation) than x1 . Note that in this case the equiprobability contours are elliptical with the long axis in the x2 direction . We can restore the situation of Fig . 4a if we scale each xi by a quantity inversely related to our uncertainty in its true or nom­ inal value . This scaling results in a modified distance measure:

\\'e then have an optimal decision procedure identical in form to that given in relation [2) with d replaced by d'.

Figure 4c illustrates the situation in which the disturb­ ances affecting x1 and xz are not independent. In this case, since an error in x1 (xz) implies something about the error affecting x 2 (x 1 ) , the symmetry axes of our equiprobability contours will no longer be paral­ lel to the coordinate axes . We note that if x 1 and x 2 are positively correlated, and a 1 = a 2 , the major axis of the equiprobability contours will have a 45' angle to the x 1 coordinate axis.* To retain the de­ cision rule given in [ 2) , we must further revise the distance measure to effectively eliminate the inter­ active effects . In particular , a general linear trans­ formation is required to rotate the coordinate frame so that its axes are parallel to those of the ellipsoids . The coefficients 7jk fer this transformation can be approximated by tlie elements of a matrix which is the inverse ·of the covariance matrLx of the xi . In func­

tional form . we then have :

*For the bivariat~ normal distribution, the angle of incl ination of the major axis to the x1 coordinate axis can be shown to be I} = 1/2 arctan[pa 1 a 2 1(ai - a~)j ·

Thus . we see that under rather general conditions . the optimal decision procedure (given by [ 2)) in deciding how to assign an unknown object to one of two possible categories is to measure the adjusted signal space distance (given by [ 1), [ 3), or [ 4)) between the ob­ ject (SM) and the expected values of the ideals repre­ senting the two categories [ RM(i) and RM(j)) . To decide between R possible categories, we can make (R - 1) binary decisions, each time eliminating the least likely alternative .

The conceptual generality of the signal space approach has a number of practical limitations . To a large ex­ tent, these can be summarized by saying that the model is useful only in reasonably well controlled sit­ uations where the errors are small and random . Be­ cause these conditions can be met in many applications involving the detection of scene congruence . the signal space approach is very powerful.

Let us now consider the significance of the quantities that appear in the "distance" expressions . The first quantity we wish to consider is 1-'1 . the expected value of RM(i) . The noise-free representation of RM(i) has been defined as Y i = (Yil . Yi2 ..... YiN) . However . as we shall observe shortly. most of the error processes to be considered have a biasing*· ef­ fect on the expected signal space location of RM(i) . Further . it is desirable to normalize RM(i) when we expect to encounter significant signal variations (such as amplitude gain and bias variation) whose parame­ ters we will not or cannot estimate. Normalization changes the expected signal space location of RM(i) in a known way.

The quantity ak , associated with the kth sample of any SM, is a measure of the total unbiased variation we can expect to encounter in attempting to measure Yik. In a more general formulation . we could con­ sider this variation to be a function of the RM(i) as well as the sample index (k) . However, in this treatment we assume that the functional dependence of a on RM(i) is unknown and thus heuristically as­ sumed to be uniform over all RM(i) . In the presence of scale and rotation error, ak will be a function· of k in a manner derived in Appendix C.

The quantity p tk is a measure of the linear depend­ ence of the noise acting on the ith sample to the noise acting on the kth sample . (It in no way reflects on the relationship between the expected values of the samples themselves. )

Given the orientation of the applications to which this paper is directed . it will not be practical in general to attempt to determine the values of the T lk appearing in [4) . Thus . we will typically ignore the interactive effects and pay the associated error penalty; or we will assume some simple structure for the p tk and at­ tempt to compensate for the interaction . For exam­ ple, a reasonable assumption might be that the noise interaction between any two samples in the SM falls off exponentially with their separation . This assump­ tion is discussed in Ref. (4) .

'"*We will define biased noise as any noise or distor­ tion process that has the effect of shifting the ex­ pected location of R:\I(i) in signal space .

Scale Change and Rotation Error

Analysis of the effects of scale and rotation errors is a major theme in this paper . If the SM and its corre­ sponding RM(t) are translated into best alignment under scale and rotation error . it is obvious that cells near the map centers (i.e .. the true match point) will be in better registration than the cells on the map periphery . This point is illustrated in Fig. 5a , and a method for computing overlap is presented in Appen­ dix C. The two main consequences of this phenomenon are :

1. There is an upper limit on the effective size of a SM. (This point is discussed in Appendixes B and C and the section on Extreme Distortion . )
2. The reliability of measurements falls off as distance from the map center increases . Thus , distance metric I 3) should be employed in ap­ plying optimal decision rule [ 2) . This result is formally derived for the Gaussian case in Appendix B.

Another result of the inability to completely align the SM with its RM(t) is the introduction of biased noise. That is, to the extent that two corresponding cells (one in the SM and one in the RM) do not overlap, a ran­ dom component having the same statistics as the com­ posite RM is added to the SM (see Eq . I B. l)) and thus the expected value of every individual RM(i) is biased toward the point in signal space corresponding to

as illustrated in Fig . 5b . The result of this biasing is to reduce the signal space distance between any two RM(i) and thus increase the probability of error in distinguishing between them. In the discussions on map normalization in the following sections . it is im­ portant to note that it is the expected value ~i) of R.M(i) . and not Y i , that is being normalized .

Amplitude Gain Error

Figure 6a illustrates the effect of an amplitude gain change on expected match point error . For no gain variation (G = 1), let RM(l) and RM(2), with ex­ pected values Ill and IJ.2 , be alternative match point possibilities. Assuming that the sample variables have been properly scaled to equalize their variation, the hyperplane which is the perpendicular bisector of the line joining Ill and ll 2 is chosen as the decision surface corresponding to optimal decision rule (2) with distance metric (1). Under a gain change a, all vec­ tors lli are extended radially out from the origin to new locations ( aiJ. . ) . The optimal decision surface now becomes the Kyperplane which is the perpendicu­ lar bisector of the line joining (Cl'IJ.l) and (Cl'll~) . In general, the new and old decision surfaces will not coincide, and any SM falling into the region between b. Effect of "E·riY" Mormallutloa oo Amplltud~ O.ln Error "1

Fig. 6 Normalization for Uniform Amplitude Gain Error

them (shaded in Fig . 6a) will be classified in a nonoptimal manner .

Figure 6b illustrates the effect of "energy" normaliza­ tion on amplitude gain error . If RM(1) and RM(2) are normalized by dividing each of their sample values J..lik by

then they will have expected values J..Li and J..L2 , where J..L' and J..L 2 lie on the same hypersphere centered at t~e origin of the signal space coordinate system. The optimal decision surface in this case can be seen to bisect the angle 0 formed by J..Li -origin-J..L2 . If a gain change a occurs . the angle between Cl'J..L]. -origin­ a/1· is still 0 and the new optimal decision surface co1~cides with the old . Thus . the optimal decision sur face chosen for energy-normalized maps remains invariant under a gain change . It can also be shown tha t the expected error for energy-normalized maps is invariant under gain change . These assertions are \·erified for the case of Gaussian noise in Appendix B. However . in Appendix A it is shown that energy nor­ mal ization itself raises the probability of error over the unnormalized case when no gain variation is possible .

Ampl itude Bias Error

Figure 7 illustrates the effect of an amplitude bias error . For no bias variation . let R:\1(1) and R:\1(2) . wi th expected values J..l1 and J..L 2 , be alternative match po int possibilities . Assuming that the sample variables have been properly scaled to equalize their variation , the hyperplane which is the perpendicular bisector of the line joining J..L 1 and J..l2 is chosen as the decision surface corresponding to rule (2) with dis tance metric (1) . Under a uniform bias error J = b(1 . 1 , ... , 1) , all vectors J..Li are displaced in a direc tion parallel to ;3 (jJ makes a 45· angl~ with each of the coordinate axes) to new locations {l.li +;f) · The optimal dec ision surface now becomes the hyper­ plane which is the perpendicular bisector of the line joi ning (j:" 1 + J) and (j! 2 +;) . In gen~ral , the new and old decision surfaces w1ll not comc1de , and any S:'l! fa ll ing in the r egion between them (shaded in Fig. 7) wi ll be classified in a nonoptimal manner .

If bias normali zation is employed, a vector c;J..Li = kJ..L i (1 . 1 . ... , 1) , which makes a 45· ang_!,e with each of the coordina te axes , is added to each J..Li so that (0J..L i + j;i) = ;7j , where J..L j (en , ci2 . . .. . cinl and

It can now be seen that all_;; lie in the hyperplane normal to the unit vector ,.3 ' = (1 , 1 , . .. , 1) . That is :

Thus . the hyperplane "Y which is the perpendicular bisector of the li!!_e joining ~i and Ji2 is paral!!,l to any b_ias vector j3 . The effect of-~ actln[ ,on J..L 1 and J..L 2. then is simply to move J..L 1 and J..L 2 along paths parallel to "Y and thus leave 1 unaltered . Thus. the optimal decision surface chosen for maps with zero mean value remains invariant under a uniform bias change .

It is worth noting at this point that under nonuniform bias change , the appropriate normalization is to spatially differentiate (perhaps more than once) the maps . In the limiting case , this could result in a two­ level binary map in which intensity contours would provide the necessary information . For such a scheme to be effective . noise cleaning techniques which eliminate high-frequency noise without blurring edges would have to be applied to the differentiated maps prior to match point determination .

Remote Error

It is useful to consider two distinct types of error processes . The first type , which we shall call "Ac­ curacv Errors" (AE) . are local deviations about the "true;, match point . and reflect the fact that physically adjacent maps will have small signal space separation due to system bandwidth limitations . We define a sec­ ond class of errors . called "Remote Errors '' (RE) . which correspond to falsely detecting a match at a point typically remote from the true match point. An RE can arise due to the chance occurrence of more than one area in the RM closely resembling the S:\!.

Thus . we define Remote Error (RE) as the chance occurrence of a Rl\l(g) sufficiently close (in signal space) to the "true" RM(t) so that RM(g) falls into the expected sphere of error surrounding R:\1(t) .

We can now determine that probability of a remote error as follows : Let us assume that the maximum number of distinct RM(i) is DM (see Appendix A) . · Then the probability of a remote error for a RM with R components is:

By the statement of the problem. Pr(g f t) = Pr(g). For the case where all distinct RM(i) are equally likely to occur , we have :

For [ (DM) » 11 :

where P is the maximum value of the average signal power in a RM(i), a2 is the average noise power , N is the number of independent samples in a SM , and R is the number of elements in the RM less the number of elements in the Sl\1 .

Thus , we see that the approximated probability of a RE is proportional to the size of the RM , but in a stronger sense is inversely related to the size of the SM and the signal-to-noise ratio . ln particular, a large number of independent samples can assure a very low probability of remote error.

ln some applications , it may be possible to reduce the probability of RE by rejecting any match point deci­ sion which does not exceed a confidence level based on the relative "cost '' of a RE versus the "cost" of no decision (or reject). Reference (5) presents an analysis of this situation . ·

Scene Characterization and Scene Selection

Scene characterization is defined as a number associ­ ated with a scene which rates the probable effective­ ness of the scene in terms of its ability to minimize match point error . The importance of such a charac­ terization derives from the fact that in many applica­ tions in which the scene congruence problem arises, scene selection is a parameter which can be opti­ mized. For example , in map matching for navigation and guidance, the ground reference scene (RM) may be freely chosen, and we might even have some latitude in choosing the SM .

Based on the definition given above, one appropriate scene characterization measure would be the expected probability of digital match point error using the given scene . In this sense, Eq . [ B. lll or I B . 13l can be used for scene characterization. We note that any use­ ful measure for scene characterization is meaningful only with respect to a particular decision procedure and noise environment. If the noise environment is assumed constant , then the "average weighted signal space distance (D')" between a RM(i) and one of its immediate neighbors (see Eq. I B . 141) can be com­ puted directly from a given scene and used as the desired metric.

*It is important to distinguish between the RM(i) which are the components of some given Reference Map (and not necessarily distinct) , and a catalog of all possible RM(i) which are distinct.

In a situation in which we can choose among a large selection of possible scenes , the computational com­ plexity of a scene characterization measure can be a critical factor . For rough or initial screening : Eq . I B . 14) can be approximated by simply measuring the sum of the squared difference of adjacent samples in the x and y directions . (These measures will be called the x and y Variation while the measures corresponding to Eq . [B . 14) will be called the Weighted Variation . ) The following table gives the results of some preliminary experiments** on the correspondence between Weighted Variation and match point error for a fixed error package and decision rule Eq . [B . 61 .

Scene Num-	X Displace- men\ ~~	y Displace- ment ~		2 y ) Weighted Variation	SM RM Sizt> Si ze
I	0	I	30	I	162 322
2	I	I	I	5	162 322
3	0	0	58	386	162 322
4	I	I	12	42	182 402
5	0	0	235	169	182 402
6	I	0	18	II	182 402
7	I	0	13	7	182 402
8	0	0	112	476	36 2 H 2
9	0	0	296	129	362 s62

It can be seen that for the particular error package employed . a map with a (squared) Weighted Variation of 50 or more in the x or y direction had no dis­ placement error in the corresponding direction.

To a large extent. Variation measures are also meas­ ures of the high frequency content of a map . It is in­ tuitively reasonable to expect that a potential for Yery accurate positioning should be dependent on the pres­ ence of a significant amount of high (spatial) frequency energy in the scene. Further . for a given sampling rate , the relative independence of the measurements increases as a function of the high frequency content of the map . Thus , a high Variation measure also im­ plies a lower probability for remote error.

As noted earlier , errors due to gain or bias changes can be minimized by either normalizing the scenes (both SM and RM) with respect to average value and to "energy" content, or by choosing scenes which are relatively uniform in these quantities . Thus . in addi­ tion to the proposed Variation measures . additional measures relating how statistically uniform the scC'ne is can provide useful information.

**Data used in these experiments were obtained from aerial photography of the San Francisco Bay Area .

EXTREl\IE DISTORTION

It has been noted that Ol'le effect of scale change and rotation error is to produce a "decorrelating" phenom­ enon as scene or map size increases . Thus. under scale and rotation error. there is an upper limit to the useful size of a coherent map (see Appendix C) . Un­ fortunately. SM size is the parameter that offers the greatest latitude for maintaining or improving match accuracy in the presence of excessive noise .

The Concept of Sl\1 Decomposition

One solution to the problem of extreme distortion is to acquire a large sensed map, and decompose it into segments of not greater than critical size . Each of these segments is applied separately to locate a match point, and the set of match points then combined (by a curve-fitting technique . such as direct or weighted a\·eraging. least squares, etc.) either to derive a best estimate match point or to estimate the actual scale and rotation error. In the latter case, the sensed map can be computationally adjusted to eliminate the exist­ ing scale and rotation factors, thus allowing the entire sensed map to be applied coherently . (The process of error estimation and correction can be applied iterati\·ely as many times as desired . )

Figure 9 illustrates some of the above concepts . In Fig . 9a we depict a situation in which the S!\1 is a ro­ tated contracted version of its intended image in the R:'II . In Fig . 9b we see that if the Sl\1 is treated as a coherent entity . and if region A of the S.:'II is in proper registration . then region B of the S~1 will be correlated with the top left corner of the R!\1 . result­ ing in a lo"· correlation score. However. if the S~I is decomposed into subregions (nine are shown in this example) and each subregion independently correlated. a pattern of match points similar to that shown in Fig . 9c will be obtained. From this pattern we can estimate the desired parameters (i . e . , match point . rotation error, scale fa ctors).

The Linear Case*

Gi\·en a correlation pattern similar to that of Fig . 9c, a cu n·e-fi tting technique such as least squares forces us to assume something about the distortion process which produced the given pattern. The simple assump­ tion made up to this point is that the distortion process is linear and thus we \\·ould look for the best rectangu­ lar (or square) grid which fits the pattern in Fig . 9c in a least squares sense. The center of the grid is the desired match point. whi le the slope and stretching of the grid specify the corresponding rotation and scale errors iri the associated S:'II.

If a remote error occurred in one or more of the match points in the correlation pattern given in Fig . 9c, a rather large error could be introduced into our

*The concept of S:\1 decomposition and its use in linear parameter es timation were independently ar­ rived at by Lynn Quam of Stanford University. He is current!~· preparing a Ph . D dissertation which will include his results in this area.

• a . Situation Using Large SM When Rotation and Contraction Errors Are Present
• b . Dashed Square Indicates Subregion of SM Correlated Without Decomposition (i.e., Coherent Correlation)

parameter estimates. Therefore, it is desirable to employ some type of "clustering" technique which will permit us to eliminate "wild" points prior to making the least squares estimate .

The "Rubber Sheet" Case

In many problems of interest, the linear distortion as­ sumption of the preceding section would not be ade­ quate . More to the point, we are frequently faced with a situation in which it is not possible to offer a com­ pletely defined distortion mechanism suitable for prob­ abilistic analysis . In this case, we must first offer a procedure for locating the SM image in the RM ; and then provide a second procedure for finding the match point as a function of this RM image.

Without a model for probabilistically relating a SM (or segment thereof) to a RM , we must (heuristically) se­ lect a distance measure to be used as the basis for classification. Consider some metric ~k(Yj) which defines the "distance" between the kth element of the SM and the jth element of the RM-* Let us now con­ sider the use of this metric with the rather general class of distortion processes which sequentially con­ strain the elements of the SM. That is. for any given SM element xk . a constraint (f!) is placed on the re­ gion in which xk+ 1 can lie. We now define the Rl\1 image of the SM to be that collection of Yj for which

is minimized subject to a sequential constraint on the xk .

Evaluation of metric Eq . [5] can be accomplished con­ ceptually (but not practically) by selecting N elements at a time from the RM and determining if they satisfy the constraint (f!) . For those N-tuples which do sat­ isfy (ll) , we select the one which minimizes metric Eq . [ 5] as the required Rl\1 image of the SM .

A procedure (which is comparable in computation time to conventional correlation), has been devised for find­ ing the RM image of the SM , and is presented below.

Let the RM be represented by the sequence

and let the SM be represented by the sequence

Assume we are given a distance function ~ ; a sequen­ tial constraint set f! ; and we are asked to find the best (according to ~ and r!) embedding of X in Y .

*In general, 11-k can also be a function of the physical distance between the embedded locations of Xk and xk-1 · xk-2 · · · · · xl ·

Consider an M x N tableau where the rows are in­ dexed by the elements of Y and the columns' by suc­ cessively larger subsequences of the elements of X .

We now define the following quantities:

) 1 · k = the best way of embedding the first (k - 1) elements of X into the first (J - 1) elements of Y . given that xk is assigned to Yj

) 2 · k a k-tuple giving the k locations in Y. 1-orre­ sponding to the embedding given by a-1 1 ·

a-! . k 3 the best embedding of the first k elements of X in the first j elements of Y . without necessarily assigning xk to Yj

a k-tuple giving the k locations in Y. 'korre­ sponding to the embedding given by a~

the set of possible embeddings of xk-l given that xk is embedded in location j

0 2

. J where j* is chosen so that

I j * ,k-1 . J

0 /.k-1 = . min {ai.k-1}

J .

1

!(C..'. k 1

l.k

a· 1

The (j k) entry in the tableau is

We append a final column to the tableau whose jth row entry has the form

The "best" embedding is then given by a~f . N and the "distance" between X and its image in Y is given by ar·N

The example presented in Fig. 10 illustrates the oper­ ation of the above algorithm. The constraint set se­ lected for this example would include the case where the scene was stretched by pulling outward on the up­ per left and lower right corners of a rubber sheet containing the scene .

For some applications, we might expect parts of the scene to remain coherent while other parts undergo "rubber sheet" distortion . This situation can be han­ dled by the preceding algorithm by simply allowing certain of the Xi to represent fixed arrangements of resolution elements , rather than single elements. This point is illustrated in the example of Fig . 11 .

For a RM with M elements and a SM with N ele­ ments, simple correlation would require on the order of kMN computations where k is a constant of pro­ portionality which takes into account one multiplication and one or more additions and subtractions . For the algorithm given above, the number of computations is still proportional to MN , where the constant of pro­ portionality is now determined by both the distance metric (~ ) and th~ constraint set (!1) .

Given that we have successfully embedded the dis­ torted RM in the SM, the need to locate a specific match point (i.e ., the point in the RM at which the sensor is pointing) might not be relevant and , in fact . might not even be meaningful. However , if this re­ quirement does exist, then the match point can be de­ termined by comparing the resulting configuration to a number of stored models for distortion , all of which are subsumed by n . A best fit to one of these mod­ els would then determine the specific procedure which derives the match point from the embedded SM .

The algorithm for rubber sheet distortion has a one­ dimensional version which offers significant simplifi­ cations . Let us consider the constraint set

i.e ., we have a situation in which the sequence repre­ senting the RM is stretched relative to the SM . In a practical situation, if it is not clear whether the SM has shrunk or expanded, the desired situation can be obtained by linearly "stretching" the RM sequence .

In the tableau for the one-dim.e~sional ver~ion of th~ algorit.h~, we can replace a'): and oJ 2 · with o~· k and o{· . as column hea.ds for all k ; further we now have, oJJ,k = ~(Yj) + oJ 3 - 1 . k . Figure 12 illustrates the one- imensional case .

Fig . 12 An Example of One-Dimensional Embedding

J	(XI) a~ 1 aj,l		(XI ' X2) a~· 2 al' 2		(XI' X2' X3) a~· 3 al' 3
	·	4		4		4
I	I	I	-	-	-	-
2	0	2	2	I , 2	-	-
3	0	2	0	2, 3	3	I, 2, 3
4	0	2	0	2, 3	2	2, 3, 4
5	0	2	0	2, 3	I	2, 3, 5

SUMMARY

It is shown that the scene congruence problem can be formulated as a classification problem in a suitably defined signal space; this allows both geometric anal­ ysis, and the application of decision theoretic method­ ology . It is then shown that an optimal procedure for match point determination will typically be based upon a weighted Euclidean distance metric . (See section on decision procedures and Eq . [B. 6) . )

The principal effect of scale and rotation error is shown to be a "decorrelating" effect as map size in­ creases . This in turn results in an upper bound on the effective size of a sensed map which is a function of scale factor and rotation. (Match accuracy can decrease if map size exceeds this critical size . ) Fur­ ther , the reliability of a sensed measurement de­ creases as its distance from the sensed map center increases . It is this nonuniformity which must be accounted for in the signal space distance metric. (See section on scale and rotation, Eq . [B. 20) and Appendix C. )

Normalization techniques to minimize the effects of amplitude gain and bias error are presented, and their significance is geometrically analyzed. In particular, normalization involves the effective reduction of signal space dimensionality (and the consequent increase in remote error probability) to produce a situation where the corresponding error process no longer affects either the decision procedure or the error probability . (See sections on gain and bias error , remote error , and Appendix A. )

An analysis of the remote error problem shows that for signal-to-noise ratios greater than 1, the number of independent scene measurements is the predominant factor in assuring protection against remote error . (See section on remote error and Appendix A. )

It is shown that a scene property. closely related to the high spatial energy content of the scene . is a good indicator of the quality of the scene with respect to po­ tential match point error . (See section on scene characterization and Eq. [B. 14) . )

For the "large error " case, two alternatives are of­ fered : sensed map decomposition in the case of linear distortion ; and a new highly efficient algorithm which can be applied to "rubber sheet" distortion. (See section on extreme distortion . )

Appendix A (Abbreviated)

SIGNAL SPACE RELATIONS

If v(t) has duration T and bandwidth W then

where :

N = 2TW

v(n/2W)

Ev

Eucledian distance from signal to origin

Ev p Signal Energy

Peak Signal Power

~ Average Signal Power

(72 Average Noise Power

DM Number of Distinct Signals

DM Number of Distinct Signals After "Energy" Normalization

Vol Volume of Hypersphere of Radius d

Appendix B (Abbreviated)

A BASIC ALGEBRAIC MODEL FOR DIGITAL MATCH POINT DETERMlNATION

The purpose of this appendix is to verify and elaborate on geometrically derived conclusions , as well as to obtain specific numerical expressions under reason­ able noise and distortion assumptions .

Optimum Decision Rule

Using the terminology and notion employed in the body of this paper ,

Let us assume the X is derived from R.M(t) . \\'e make the following assumptions:

1. Each component Yij of the RM is an inde­ pendent Gaussian random variable I I'm . CYfu)
2. Each component xi of the Sl\I is derived from RM(t) in accordance with Eq . [B . 1 I :

where Z is an independent Gaussian variable (aris­ ing from some external noise process) with mean l'n and variance CYfi ; W is an independent Gaussian ran­ dom variable (associated with map element variation) with parameters IJm , <Yfu ; cp is a function of the ro­ tation angle (} , the scale change in the x direction et , the scale change in the y- direction f3 . and the index j of the map element. In particular . <;Jj is the percentage overlap of the jth Sl\1 element with its

corresponding RM element when the SM and corre­ sponding RM are in best registration under the con­ straints imposed by scale change and rotation factors. Appendix C gives a procedure for evaluating tP .

Assuming that the SM is equally likely to have been derived from any location in the R~I. the decision procedure for minimum error is to assign X to R.M(t) if:

where

Then from Eq . [B . 6] we can compute the probability of err or Er[ i j t] as :

wher e <t> is the Gaussian cumulative distribution function :

\\'e then make the approximation :

and if <t>(-D'/2 ) is small. we have

\\·here .\1 is an empirical constant and

Dec ision rule Eq . [B. 6] takes into account the biased noise effec t produced by scale change and rotation e rrors . For practical reasons , it is sometimes de­ si r able to ignore these effects and assume that ok = 1 fo r all k . This simplification results in error pr obability (compare with Eq . [B.10]):

Pr [ i t t]

Note that all for k* such that ct>k· = 0 (i.e., the k* elements in the SM and RM no longer have any area of overlap), the expected value of the summation in the numerator of Eq. [B . 20) over the k· terms is zero . However, the contribution of these terms to the denominator is positive. This means that if the SM is made large enough so that tl>k becomes zero for part of the map . the resultant expected error is 1arger than that which would have resulted from using a smaller SM .

Consider a situation in which scale and rotation errors are absent . but assume that an uncompensated ampli­ tude gain change can occur. The error probability in this case is (G = 1 fer no gain error) :

Pr[ijtl

[B . 28]

For the case where RM(t) and R.\1(i) have equal energy

a gain error can be ignored since it ll'ill not cause a change in the value of Eq . [B . 28] .

Appendix C (Abbreviated)

THE GEOMETRY OF SCALE AND ROTATION ERROR

The Overlap (Qk) Between Corresponding Elementarv Areas in S.\I and R.\1 Under Scale and Rotation

Suppose the Cartesian plane is subjected to scale and rotation changes. That is . it is expanded by a multi­ plying factor of a in the x-direction and ,3 in the y direction (the origin being the fLxed point in both of these expansions) . and then rotated counterclockwise about the origin by an angle of 0 . Suppose further that R is a square centered at the point (x , y) . which has sides parallel to the axes of the unexpanded . unro­ tated Cartesian plane and of length one . and that R' is R subjected to the above scale and rotation changes. We derive an expression approximating the area of R n R' .

Subjecting the point (x. y) . the center of R . to the given expansions yields the new point (ox . .,ly) . and rotating (c.·x . ;Jy ) counterclockll'ise about the origin by U yields the point (u , v) . the center of R' . where u = ax cos U - ,3y sin 0 , and v = [J y cos 0 + ox sin 0.

Let R" be the square whose sides are of length one and are parallel to the axes of the unexpanded unrotated Cartesian plane. and whose center is (u . v).

If e is not far from 0 and a and ;_, are close to 1, then the area of R n R' is approximated by the area of R n R" .

The distance between the left side of R and the left side of R" is 1 x - u 1 . Consequently . it is not hard to see that the length of the bottom side of the rectan­ gle R n R" is 1 ~ I X - u I ' where 1 ~ a is defined as the maximum of the two numbers 0 and 1 - a . Similarly, the other side of the rectangle R n R" has length 1 ~ IY- v1. Hence. the area of R n R " is (1 ~ I X - u I ) X (1 ~ I y - vI ) .

Combining the above results. we determine that the area of R n R' is approximated by

and

0 rotation angle a x scale factor

(3 y scale factor

An Upper Bound on Sense Map Size

Based on the results of the preceding section, it is possible to compute an upper limit on the size of a SM beyond which its area of overlap (with respect to reso­ lution cells) with its original image in the RM ceases to increase. The entries in the following table give this limit as the dimension of one side of a square array of cells , as a function of rotation and uniform x , y scale factor .

·Note that if the map samples are not independent measurements, then the effective value of ok will be larger than the value given above . We are cur­ rently examining the heuristic of making ¢>k an ex­ ponentially decreasing function of the distance between (x . y) and (u . v) .

Scale Factor	Rotation (deg) .
	0	2	4	6
1. 00 1. 02	>50 >50	>50 >50	30 33	21 21 22
1. 04	>50	>50	33
1. 06	34	40	30	22
1. 08	26	30	26	21
1.10	21	25	23	19

• Note : (1) The values given in the above table .are upper bounds rather than least upper bounds on map size .
• If the map samples are not independent measurements . then thetable entries should be scaled upward . Thus . if sam­ pling occurs at r times the Shannon rate . the table values can be r times their listed values .

Acknowledgment

The author would like to ack.nowledge the many techni­ cal contributions to this paper made by R. A. Elschlager . Thanks are also due to 0 . Firschein. J. M. Tannenbaum, and R. D. Merrill for helpful comments. The author's interest in the scene con­ gruence problem was inspired by the work of \\'. G. Eppler [Ref. (13)] .

BibliographY

1. W. Miller and A. Shaw. "Linguistic Methods in Picture Processing." AFIPS (FJCC) Proceed­ ings . Vol. 33. 1968. pp . 279-290 .
2. l\1. A. Fischler. "The Detection of Scene Con­ gruence , " 6-83-il-2 . Lockheed Palo Alto Research Laboratory. Jan 1971.
3. T. W. Anderson. A~ Introduction to :11ultivariate Statistical Anal\'sis. Wiley . 1958.
4. A. Arcese. P . H. 1\lengert. and E . \\'. Trombini. "Image Detection Through Bipolar Correlation, " IEEE Trans. on Information ~- IT-16(5) . Sep 1970, pp . 534-541 .
5. C. K. Chow, "An Optimum Character Recogni­ tion System Using Decision Functions. '' IRE Trans . on Electronic Computers . EC-6 . Dec 1957. pp . 247-254 .
6. P . W. Cooper. "The Hyperplane in Pattern Recognition," Cybernetica. Vol. 4 . 1962
7. S. Goldman, Information Theon . Prentice­ Hall. 1953 .
8. C. \\'. Helstrom, Statistical Theon of Signal Detection . Pergamon Press . 1960 .
9. N. J. Nilsson. Learning :\lachines. McGra\\'­ Hill . 1965 .
10. G. S. Sebestyen, Decision-Making Processes in Pattern Recognition, Macmillan , 1962.
11. J . M. Wozencraft and I. M. Jacobs, Principles of Communication Engineering, Wiley , 1965 .
12. W. B. Davenport, Jr . , and W. L. Root, Random Signals and Noise, McGraw-Hill, 1958.
13. W. G. Eppler and G. A. Simas, "A TI1eon- of Map Matching," 5-26-68-2, Lockheed Missiles & Space Company, Mar 1965.