Please see PDF version
JOURNAL OF COMPLEXITY 5, 261 270 (1989)
Certifying Smoothness of Discrete Functions and
Measuring Legitimacy of Images*
J. MICHAEL STEELE
Program in Statistics and Operations Research, School of Engineering and Applied
Science, Princeton University, Princeton, New Jersey 08544
Received April 3, 1989
Several problems that deal with smoothness of discrete functions and that are motivated by the task of deciding whether an N x N array of distances is a feasible laser radar (LADAR) image are investigated. The main observation is that there is a simple and explicit graph that is tightly related to the smoothness problem. The graph is used to show that a function can be verified to be Lipschitz on a random finite subset of R' by testing the Lipschitz condition at only 0(n) pairs of points. 0 1989 Academic Press, Inc.
1. INTRODUCTION
The problems studied here are motivated in part by the investigation of statistical models for laser radar images. The salient feature of such images is that they consist of an array of N x N pixels where each pixel is associated with the actual distance to a corresponding part of a physical scene being viewed. This direct link to distances contrasts powerfully with more traditional image data where the value associated with each pixel is typically the intensity (in some range of the EM spectrum) of either the reflection or the emission from the scene being viewed.
For many practical applications, laser radar (LADAR) images have important advantages over spectrally based images; and, while most of these advantages come directly from the distance interpretation of the pixel values, there are also technical considerations that make LADAR applications easier. For example, LADAR images do not force us to worry about the direction of the illumination source as we must in many applications of optical images. Still, even with its technical and concep
Invited Paper.
261
0885 064X/89 $3.00
Copyright 0 1989 by Academic Press, Inc. All rights of reproduction in any form reserved.
262 J. MICHAEL STEELE
tual advantages, there are features of LADAR images that provide new challenges; and, in particular, one must come to grips with their genuinely three dimensional nature.
In several approaches to the understanding of 31) images, like those that LADAR gives for a view of a physical scene, one needs an efficient way to judge whether a specified set of N X N pixel values is a physically feasible image. Certainly if one wishes to provide an effective prior distribution on the set of feasible LADAR images in order to permit a Bayesian analysis, then it is almost essential to have some reasonably simple criteria for a realization of N X N pixels to correspond to a real view.
In Section 4, we engage the LADAR problem as squarely as possible, but, in intermediate sections, we look at more stylized problems. These new problems may cast some light on the particular problems that need to be solved in the context of LADAR, but they are of more general applicability.
The most stripped down question we address is Howcan we certify
that a function f. Rd > R is smooth?" The way we choose to frame a
discrete (and possibly answerable) version of this question uses the verifi
cation of a Lipschitz condition at a finite set of points in order to gauge
smoothness. Specifically, given a finite set S = {Xl, X2, . . . ? XJ C [0, Ild
andf. S > R, we examine the information that is needed to certify truth of
the statement S(a): for all xi and xi contained in S we have if (xi) f (x)J:5
a Ixi xii.
One model of complexity that is reasonable in many contexts (though admittedly strained in the context of LADAR imaging) is to suppose there is an oracle such that for each i andj the oracle can verify the truth of the statement SU(a) that If (xi) f (xj)l :5 aixi xjl. The natural question that presents itself in this model is Howmany times must we query the oracle before we can certify the smoothness of f ? Obviously, S(a) can be certified by n(n ~ 1)/2 queries of the form Sjj(a), but we aim to do better.
If d = 1 the problem is easy; just order the points xl :!~ X2 :5 . . . 25~ X~ and ask the oracle the n 1 questions Sjj, (a). If all of these are answered in the affirmative, we knowf is smooth in the sense that S(a) is proved. In this case we can also be sure that no fewer queries can suffice since each xi must figure into some query.
After d = 1, the most natural setting to consider is that where n = N2 points on the rectangular lattice of R2. This and other lattice problems are solved in Section 2. The lattice problems are still easy, but they are worth considering because they do a good job of isolating the essential features that underlie the complexity of certifying smoothness. In particular, we are led to the useful notion of a transit graph, i.e., a spanning graph G = W, E) Of V = {Xl, X2, . . . , Xn} such that for each pair of vertices xi and x.,.
i
1
SMOOTHNESS OF DISCRETE FUNCTIONS 263
there is a path from xi to xj consisting of edges of E with slope of constant sign. We will show that the transit graph is an apt tool for studying Lipschitz smoothness. Somewhat surprisingly, it is also possible to give an explicit characterization of the transit graph of any V. One further aspect of the transit graph is that it is often sparse. In particular, we find the expected number of edges of the transit graph on n random points in [0, 112 is 0(n) even though in the worst case it can have fl(nl) edges.
We return to the problem of laser radar images in Section 4 and try to lay out the basic decision criteria for physical feasibility. Naturally, aspects of smoothness are among the criteria, but the characteristic feature of physically realistic LADAR images is strong limitation on the discontinuities that are present.
2. LATTICE CONSIDERATIONS
The nearest neighbor graph G = (V, E) of the N x N lattice has n = N 2 vertices, and, since G has N 1 horizontal edges in each of N rows and a similar number of vertical edges, we see that the total number of edges 1E1 is exactly 2N(N 1). Now, suppose we know Sij (a) for each UJ) E E. By joining any pair of points x,, and Xb of V with a path consisting of horizontal path PH from x,, to x, and a vertical path Pv from X, to Xb, we can derive essentially the same bound for lattice points in R 2 that we found for general points in d = 1; specifically we.find by telescoping and a little geometry that
lf(X.) f(Xb)l a 1 Jel + a 1 lel
eepv eE=PH
a 1X. X,l + a JXb Xcl
21/2alX,' Xbi.
We can amplify the logic of the last step and also see how one might improve the factor of 2112 by considering the hexagonal lattice. Consider a set of n = N(N 1)/2 points placed at the vertices of that part of a regular hexagonal lattice of side 1 that is contained in an equilateral triangle of side N 1 (see Fig. 1).
Given any x,, and Xb in S there is again a shortest path that consists of two straight segments that connect x,, and Xb. If x, is the lattice point at the turn, and, if Sjj(a) is valid for all nearest neighbor pairs (i, j) of S in the hexagonal lattice, then again by telescoping we have
lf(X,,) f(XbA aix. x,l + alX, Xbi.
264 J. MICHAEL STEELE
b
FIG. 1, Hexagonal lattice configuration.
This time we need a more explict calculation to bound the sum. By the law of sines we have
]X,, Xbi/sin 01 = lx,, x,l/sin 02 = IX, Xbi/sin 03
and, of course 01 = 21T/3, so since sin 01 = \~3/2, we have
IX,, X,1 + IXb X,1 :5 21x,, Xbi(sin 02 + sin 03Y\/5.
Since 0 :5 02, 03 :5 7r/3, and 02 + 03 = 7r/3, we maximize sin 02 + sin 03 by taking 02 = 03 = ir/6, and since sin 7r/6 = 1, we find
IXa X,1 + jXb XJ :5 (2/V35)1x,, Xbi.
We therefore find that for the hexagonal lattice S(P) is verfied with P (2/V53)a.
This value of P is a slight improvement over the value,8 = V 2a that we obtained in the rectangular case; but this improvement comes at a price, and in terms of the number of queries required we do slightly worse with the hexagonal lattice than with the rectangular lattice. For large n, the number of tested edges per vertex in the rectangular lattice is approximately 2 whereas the number of tested edges per vertex in the hexagonal lattice is approximately 3. These values would be exact if it were not for the influence of boundary effects.
The main lead we take from the lattice point investigation concerns the use of special paths, but before we pursue this lead, there are two observations that should be made concerning d > 2. By the same counting we applied in d = 2, one also finds for the set S of N d rectangular lattice points in Rd that there are d(N I)Nd 1 edges in the nearest neighbor graph and that therefore the verification of d(N I)Nd 1 queries of the form Sjj(a) is enough to verify S(d112a). We will not pursue the consideration of d > 2 any further here, but one might expect the investigation of
SMOOTHNESS OF DISCRETE FUNCTIONS 265
the higher dimensional problems to be particularly interesting because of the rich increase in the possible lattices.
3. GENERAL POSITION
The possibility of verifying S(p) with only 0(n) queries in two dimensional lattices came from using telescoping sums along special paths. In this respect the lattice computation suggests a generalization that offers promise in a number of different problems. If a sequence M xi, = (xi,, y), 1 :5j::~ k, of points in R' that satisfies eitherxi, :s xi, and y,' :5 yi,,, for alIj, or x,.,. :5 xij, , and yij ~~t yij,, for all 1 :s j :f~ k then we will call M a monotone sequence. In other words, a path M connecting a sequence of points in R2 is monotone if all of the slopes of the edges of M have the same sign.
We will call G = (V, E) a transit graph of V = {Xl, X2, Xn} provided that for each pair of points xi and xj of V there is a monotone path Mij consisting of edges of E. One can easily check that the arguments we applied for lattices apply directly to any set of points spanned by a transit graph. This is recorded more formally in the following proposition.
PROPOSITION 1. If G = (V, E) is a transit graph for V = {X I, X2,
x.} and if (x) f (y)l :5 afor all (x, y) E E, then If (x) f (y)i :5 2112afor all x, y contained in V.
One fact that makes the notion of a transit graph useful is that we can easily characterize the smallest spanning transit graph of a finite set of points in R 2 . Given any two points x and x' in R2, we can determine a box B(x, x') in R2 by letting B(x, x) denote the smallest closed rectangle containing x and x'. For example, if x = (x, y) and x' = (x', y') with x < x' and y < y', then we have B(x, x') = [x, x'l x [y, y']. It turns out that boxes lead to an explicit characterization of the minimal spanning transit graph.
LEMMA 1. Let G = (V, E) be the graph with vertex set V = {Xl, X2, . , Xn} and edge set E such that (x, x') E E if and only if B(x, x,) n v = {x, x'}. The graph G is then a spanning transit graph for V. Moreover, if G' is any other spanning transit graph, then G C G'.
Proof. To see that the G defined by the lemma is a transit graph, we use induction on n. If x and x' are given, we need to find a monotone path in G from x to x'. By symmetry, there is no loss of generality in assuming that x = (x, y) and x' = (x', y') satisfy x < x' and y < y'. If (x, x') is not already an edge of E there is a point x" E V such that x" E B(x, x') and x" distinct from x and x'. By the induction hypothesis applied to G {x'} there is a monotone M, from x to x" and by the induction hypothesis applied to G {x} there is a monopath M2 from x" to x'. We can take M =
266 J. MICHAEL STEELE
M1 U M2 as a monotone path from x to x'. If B(x, x') does not contain such an x", then by definition of G we have (x, x') E E, and we can simply take M = {(x, x')} as the desired path. a
It would be pleasing if the transit graph G = (V, E) of a set V = {Xl, X2, ... ~ Xn} could be guaranteed to be relatively small, say with E1 = 0(n) or even 1E1 = o(n2). While we can show that in a sense this is typically the case, we can also show that E1 = fl(n2) is possible for worst case configurations.
To obtain an example that shows the transit graph can be large, consider the set of 2n points given by V = {(i, i), (n + i, 2n i), 1 5 i :5 n}. For each 1 5 i :5 n and 1 :5 j :5 n the boxes Bffi, i), (n + j, 2n j)) contain no points of V other than their defining vertices, so the transit graph of G contains at least the W edges required by the boxes for the pairs Q, i) and (n + j, 2n j) for 1 :5 i 5 nand 1 :5 j t~ n. In fact, by considering the boxes &Q, i), (i + 1, i 1)) and B(n + j, 2n j), (n + j + 1, 2n j 1) we see that the minimal spanning transit graph of V has exactly W + 2(n 1) edges.
A more optimistic view of the world is provided by considering points chosen at random from the unit square.
PROPOSITION 2. If xi, 1 i n, are independent uniformly distributed random variables with values in [0, 112, then the expected number of edges of the minimal spanning transit graph G = (V, E) of V = {Xl, X2, i Xn} satisfies E(IE1) = 0(n).
Proof. If B12 denotes the rectangle determined by xl = (xl, yi) and X2 = (X2, Y2) then B12 has the random area lx, X21 1Y1 Y21. For B12 to be empty the other n 2 points of V must fall outside of B12, so by conditioning we have
P(B12 empty) = froj], (1 1Xl X21 1Y1 Y2 1)n 'dXldX2dYIdY2.
By applying 1 x 5 e for x 0 and changing variables, we further find
P(B12 empty) f~1,1]4 exp{ lxl X21 1Y1 Y21(n 2)}
dXldX2dYIdY2 0(n 1).
Finally, since there are n(n 1)/2 pairs of points that have associated boxes we have
E(IE1) = (n) P(B12 empty) = 0(n). a
2
SMOOTHNESS OF DISCRETE FUNCTIONS
We will not pursue further calculations of this type, but it should be clear from the preceding propositions that the transit graph is quite tractable. Also, by Proposition 1, it is clear that possession of the transit graph is a useful step in Lipschitz verification.
4. CRITERIA FOR LADAR REALISM
We now return to the issue of judging the physical feasibility of LADAR images. This pursuit differs in spirit from the preceding analysis in several respects, and in particular it no longer seems possible to give results that can be expressed in tidy propositions. In fact, almost anything one says about criteria for a LADAR image must rest substantially on judgments that one makes about the physical world and current technology.
The applications that are currently envisioned for LADAR involve carrying the LADAR device in a helicopter. The elevation of the helicopter and its distance from the scene of interest are typically determined so that the line of sight makes about a 15' angle with the horizontal. By examining typical scenes at the resolution that can be assumed, it is possible to make some assumptions about the sizes of the discontinuities one can expect in the distances represented in the pixels of the N X N image array in A.
To avoid the extra layer of complexity associated with the discretized image, first consider a continuous version of the image. That is, we view the image as if it were given by a distance functionf. [0, 112 ). R. The class of functions that one is led to consider in this representation is a little unusual by the standards of traditional analysis. In particular, by considering the simple image sketched in Figs. 2a and 2b, one finds that it is essential to consider functions f with discontinuities, and, in order for the representing function to have discontinuities that are physically realistic, they must be of a highly confined nature. In fact the discontinuities of f cannot amount to much more than the two dimensional analogs of simple jump discontinuities.
By considering Fig. 2, it also seems appropriate to assume that the set of discontinuities of f yields a set of curves in [0, 112 such that as one traverses one of these curves of discontinuity Cj obliquely, one sees only either an increase in f (a plus jump) or a decrease in f (a minus jump). Moreover, because of the relationship between the physical scene and the orientation of the image, there are constraints on the types of jumps that can occur along specified paths in [0, 1]2. For example, in a world where we view features like overhanging eaves as too rare to worry about, one
268 J. MICHAEL STEELE
a b
C=
FiG. 2. Distance function geometry. (a) Scene. (b) Discontinuities off.
sees either plus jumps or minus jumps as we move from right to left, and only plus jumps as one moves from bottom to top.
The restriction to pure jump discontinuities of these confined types seems to be about as far as it seems appropriate to go in terms of the topological constraints one should place on realistic LADAR images. There are obviously additional metric constraints one should impose, but at that point one has to dig more deeply into the technology of the moment, and we will not puruse the abstract modeling of LADAR images beyond this first cut. In fact, the steps that remain in the engineering problem are probably best addressed via the Edisonian shotgun approach of trying the many reasonable variants that present themselves. Still, one should have confidence that the remaining problems will receive attention for the good reason that the technology of LADAR offers such promise that its refinement and development is almost inevitable.
From the point of view of the complexity of approximately solved problems, there is an interesting distinction between line of applied research suggested by LADAR and the work in remote sensing that preceded LADAR. The distinction is that, in LADAR, in order to identify the items of interest in the remotely sensed scene one has a compelling need for geometry, while in older areas of remote sensing, geometry has not been nearly so essential. There are two reasons that underlie this shift. First, in older technologies one simply did not have enough geometric detail to make serious use of geometry in the identification process. Second, there is the lucky fact that in older technologies one often found characteristic signatures for items of interest in the remotely sensed scene and useful identification was possible even without geometric detail.
The intention of this section has been to describe the flavor of the questions that are of interest in the analysis of LADAR images. The subject is new, yet vast, so the discussion has been narrowed to the discussion of the topological constraints although we readily admit that a
SMOOTHNESS OF DISCRETE FUNCTIONS 269
technologically useful answer to the criteria for realism needs to engage many metric issues as well.
Before we leave the question of criteria for realism of LADAR images, it is useful to record two benefits of a full answer. In the first place, by knowing the domain of realistic LADAR images we are in a far better position to specify a family of probability distributions on the set of LADAR images. Naturally, such a step is necessary if one is to use Bayesian methods in the analysis of LADAR images. A more immediate application for a criterion of realistic images is that it permits real time feedback to the LADAR device. This can in some cases provide the mechanism for improving the LADAR device itself, and at a minimum it provides a command and control tool that can suggest when a LADAR device should be taken out of use.
5. CONCLUSION
We entered this exploration by considering the distinctive features of LADAR images, and we have left by the same door. In the middle we addressed the complexity of certifying the smoothness of a function
Rd > R, and it was there that the most satisfying steps were taken.
Both of these problem areas fall within the scope of the theory of complexity of approximately solved problems as delineated by Traub (1985). Also, we should note that even though image understanding is ultimately connected to the aims of LADAR, the simpler step contemplated here of checking for legitimacy must be satisfactorily resolved before one can address broader issues of image understanding such as those contemplated by Lee (1985).
The certification of smoothness seems like a natural and interesting problem. It also seems not to have been treated before, though naturally, there is work with a related flavor. One example is given by the work on the realizability of metric spaces in graphs (e.g., Altenh6fer, 1988), and a second is the work on the approximate isometric embedding of finite subsets of Rn into Rk, where k is much smaller than n (e.g., FrankI and Maehara, 1988). We hope that Sections 2 and 3 illustrate that there are interesting issues in the complexity of smoothness, and at least that they should leave little doubt that many issues remain essentially unexplored.
REFERENCES
ALTHENH6FER, 1. (1988), On optimal realizations of finite metric spaces by graphs, Discrete Comput. Geom. 3, 103 122.
270 J. MICHAEL STEELE
FRANKL, P_ AND MAE11ARA, H. (1988), The Johnson Lindenstrauss lemma and the sphericity of some graphs, J. Combin. Theory Ser. B 44, 355 362.
LEE, D. (1985), Optimal algorithms for image understanding: Current status and future plans, J. Complexity 1, 138 146.
TRAuB, J. F. (1985), Complexity of approximately solved problems, J. Complexity 1, 3 10.
ill,
1 1