What is a 'Degenerate' View?
Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Perception. Pages 801-803.
© 1987 International Joint Conferences on Artificial Intelligence
Abstract
In this paper••, we attempt to quantify what is meant by the terms "degenerate view", and its relatives, "characteristic view", "visual event", and "general viewing position". We propose that the defmition of degeneracy is itself degenerate, taking on differing meanings at different times. We claim (at least for the case of polyhedra) that one can only speak of a two-dimensional stimulus as being degenerate with respect to a given heuristic for inverting the image function. Additionally, we show that given the fmite viewing resolution of a two-dimensional retina, in practice the concept of a characteristic view is often not characteristic of real imagery. Even precisely defined general viewing positions are sensitive to camera acuity: any viewpoint ceases to be characteristic at some resolution, and non-characteristic views are not vanishingly improbable. We provide initial quantitative e~timates on these probabilities for some simple cases, and relate them to a minimal disambiguation distance. It follows that an aspect graph is less a discrete graph, and more properly a partitioning of the surface of the viewing sphere into "fuzzy" regions of non-zero area: an aspect map. This viewpoint is more in keeping with recent and proposed work on optimal viewing strategies.
- and Jain 85]
- Besl, P. J., and Jain, R. C. Three-Dimensional Object Recognition. ACM Computing Surveys, 1985. '
- Castore, G. M. Solid Modeling, Aspect Graphs, and Robot Vision. In Solid Modeling by Computers: From Theory to Applications. Plenum Press, 1984.
- Chakravarty, I. The Use of Characteristic Views as a Basis for Recognition of Three-Dimensional Objects.
- Chin and Dyer 86]
- Chin, R. T., and Dyer, C. R. Model-Based Recognition in Robot Vision. ACM Computing Surveys, 18(1):67-108, March, 1986.
- Kanade, T. A Theory of Origami World. Artificial Intelligence, 13(3):279-311, May, 1980.
- Kender and Freudenstein 87]
- Kender, J. R. and Freudenstein~ D. G. What is a Degenerate View? In Proceedings of the DARPA Image Understanding Workshop, pages 589-598.
- Koenderink and van Doom 79]
- Koenderink, J. J., and van Doom, A. J. Internal Representation of Shape with Respect to Vision. Biological Cybernetics, 1979.
- Lavin, M. A. An Application of Line-Labeling and other Scene-Analysis Techniques to the Problem of Hidden- Line Removal. Technical Report, MIT Artificial Intelligence Lab, 1974.
- Natarajan 86
- Natarajan, B.K. On Moving and Orienting Objects. PhD thesis, Cornell University, 1986.
- Sabbah 82
- Sabbah, D. A Connectionist Approach to Visual Recognition. PhD thesis, Rochester University, 1982.
- Thorpe and Shafer 83)
- Thorpe, C., and Shafer, S. Topological Correspondence in Line Drawings of Multiple Views of Objects. Technical Report, Department of Computer Science, Carnegie- Mellon University, 1983.
- Werman, Baugher, and Gualtieri 86]
- Werman, M., Baugher, S., and Gualtieri, J. A. The Convex Visual Potential. Technical Report, University of Maryland, Center for Automation Research, 1986.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Abstract
In this paper··, we attempt to quantify what is meant by the terms "degenerate view", and its relatives, "characteristic view", "visual event", and "general viewing position". We propose that the defmition of degeneracy is itself degenerate, taking on differing meanings at different times. We claim (at least for the case of polyhedra) that one can only speak of a two-dimensional stimulus as being degenerate with respect to a given heuristic for inverting the image function. Additionally, we show that given the fmite viewing resolution of a two-dimensional retina, in practice the concept of a characteristic view is often not characteristic of real imagery. Even precisely defined general viewing positions are sensitive to camera acuity: any viewpoint ceases to be characteristic at some resolution, and non-characteristic views are not vanishingly improbable. We provide initial quantitative e~timates on these probabilities for some simple cases, and relate them to a minimal disambiguation distance. It follows that an aspect graph is less a discrete graph, and more properly a partitioning of the surface of the viewing sphere into "fuzzy" regions of non-zero area: an aspect map. This viewpoint is more in keeping with recent and proposed work on optimal viewing strategies.
2 Introduction
Robotic vision systems must both obtain images and analyze them. However, a primary characteristic of many realistic imaging situations is that the data acquisition is much less costly than the subsequent data analysis. In such domains it is therefore reasonable to dedicate significant computational effort towards the task of calculating an optimal viewing point for the next image capture. Defining and obtaining this optimum is necessarily probabilistic; it must incorporate an understanding of the limits of resolution of the camera, and of the .limits of resolution of the placing agent. The overall goal is to obtain maximal information from a sequence of inexact images in inexact placements, while minimizing some wortc function which expresses the relative costs of image acquisition and image analysis. Such calculations necessarily place a heavy premium on avoiding what are often referred to as "degenerate views".
Nevertheless, it is not apparent what makes a view degenerate, how such a view is reco2nized or forecast, or even whether such views are rare or commonplace. Thus, the first concern of this paper is to define and quantify the meaning of the term "degenerate", and to show the varying imaging contexts in which it can arise. Secondly, we suggest a representation useful for ~aleulating the likelihood of such views (whatever their definition); It takes the form of mappings over the viewing sphere. This representation extends existing wortc on aspect graphs by explicitly
·This research was supported in part by ARPA grant #N00039-84-C-016S, by a NSF Presidential Young Investigator Award, and by Faculty Development Awards from AT&T, Ford Motor Co., and Digital Equipment Corporation.
·· A more detailed version or this paper, lncludin& a survey or multiple viewpoint representatloos, as well as complete references · and appendices, may be round In [Kender and Freudensteln 87]
What Is A "Degenerate" View?
John R. Kender* David G. Freudenstein
Department of Computer Science Columbia Umversitv New York, NY 10027-6699
incorporating the known limits of visual acuity. It also leads directly to methods of associating with each view a probability of its being attained, and the placement cost of attaining such a view.
3 Degenerate Viewpoints in Theory
If it is to be useful, a representation for the views of a three dimensional object or object assembly must give some insight into those viewing positions which are less helpful in resolving ambiguities of object structure, position, or orientation. We present two common views of what such degeneracy is, show that they are deficient, and redefine them in ways that are more quantifiable.
3.1 Slight Movements Giving Drastic Changes?
Perhaps the simplest example of ambiguity is the case of a head on view of a cube, which is ideally imaged as a square. Such an· image has often been noted as giving no information as to the three-dimensionality of the object, and has therefore been described as a degenerate image (see for example, [Kanade 80; Sabbah 82] ). Degeneracy in this context, however, refers to the fact that a "slight" change in the viewpoint which generated the image would cause a "drastic" change in the image (sometimes called an "image event").
This definition (and related descriptions of what makes a viewing position general or an image characteristic [Chakravarty 82]) is inadequate in two ways:
- It is vague with respect to the meanings of "slight" and "drastic".
- It does not encompass all the phenomena that would seem to be properly described as examples of degeneracy.
What changes drastically in the cube-as-square image can be characterized in many ways: the number of regions change, the topology of the image regions is altered, apparent symmetries are modified, and (if lines are labeled in the Huffman-Clowes manner) the junctions are relabelled (cf. [Lavin 74; Thorpe and Shafer 83]). Still other derived properties of the image change, too. More generally, depending on the means of analysis, this view of the cube would be called degenerate if a slight change in viewpoint would alter the "quality" of the ensemble of extracted image features used in shape analysis. A rigorous definition of this "quality" change must then include the requirement that a qualitative change is one that ultimately affects the derivation of those object's "semantic" properties (such as identity, scale, rotation, coloring, etc.) considered important by the system. ·
The drastic change is therefore a drastic change in interpretation, not in image. Therefore the perception of a drastic change can vary from system to system. For example, if the system distinguishes cubes from spheres by detecting the presence or absence of long straight lines, the cube-as-square cannot be considered degenerate. (And, in fact, if the cube is the only model in the system at all, no view is ever degenerate.)
What is hiding behind this implicit definition of "drastic" is the interpretation equivalence relation; a dmstic change is a change of interpretation equivalence classes. However, since in many systems the interpretation classes are inherited from the feature equivalence classes 1 commonly the drastic change has been attributed to image cnaracteristics alone.
Similarly, the notion of "sliaht movement" is imprecise. What is usually implicit in such deimition is that there is at least one direction in which an arbitrarily small movement of the camera causes the drastic change. (Usuall)' the direction is on a line perpendicular to an image edge). The meaning of "arbitrarily smill" only a~ to make sense when taken in the sense of mathematiCal lrialysis. That is, the drastic change must occur for positive movements of magnitude less than some epsilon, in the i1irection of de~eneracy.
Such a defirution would imply that degeneracy can be qualified as a matter of varying degree, althou2h this is apparently never stated. That is, what can vary from degeneracy to degeneracy is the number of possible ("quillitative") drastic changes, and the relative number of directions in which such resolutions (or non resolutions) occur. For example, the cube-as-square image can resolve itself into an image with either two or thiee rejions, with the two region image possible only for four discrete dfrections of camera movement. All other directions resolve it into an im~e. with three regions, even if some of those regions are vanishin y thin. Further, some "degenerate" views sometimes do not reso ve at all. For example, the cube imaged as two rectangles remain8( two rectangles for two discrete directions of movement, resolving itself into three regions under movement in all other directions. The space of allowable degeneracies is apparently very large, and perhaps can be quantified in absolute terms as some measure Clefined on the ways in which the view fails to resolve into something more ''cliaracteristic' .
The converse of the common "small gives drastic" definition is perhaps easier to implement. This converse definition is stated as follows: An image IS seen from a "general viewpoint" if there is some positive epsilon for which camera movements in any direction can be taken without effect on resulting semantic anal~sis. Here, too, the definition is based ultimately on system performance; an ima~e can be degenerate to one system but not another. Note that thls definition of degeneracy need not directly appeal to any consideration of three dimensional models.
3.2 Unlikely VieW$?
Even this definition of a degenerate viewpoint is incomplete; basicall,Y it says that generality IS a form of stability. Many stable viewP.Omts ought to tie considered degenerate, at least in the sense that ihat they are less likely to allow a system to instantiate a proper model than other viewpoints.
Conaider a pyramid with a IICJU&re base and arbitrary heiaht. {Customaril,Y, ft bu equilateral tnangles for its sides, but we rilax that resttiction.) Imaged from many viewe,oints from below, its image a~ to be a type of rhombOid: a tilting square. None of these viewpoints is desenerate according to the statiility definition above, since a sHght Change in viewpoint does not cause a draatic change in the image; it merely tilts the rhomboid. In fact, there is a great deal of viewpoint freedom, and many views appear to yield the same semantic result: a partly inatantiaied ,PY1'81J11d with height information largely missing. What is most disturbing about such views is that they ire potentially the most common. FOr a very flat pyramid, such rhombOids appear from nearly half of all viewing airectio111.
Yet it seems plausible to auggest that these particular views be conaidered at least partially de~nerate; in contrast to some other views, these images give liitle iiiformation about how to inatantiate the ~d's heiJhi (They do place weak upper limits on the height: t1:1e peak 11 co111trained to heights that bep it invisible.) Further, if our model base were more complete, we would not be able to distinguish such a view from among similar views of a trian&ular we<ige with square base, or &n)' aimilarly tapering polyliedron witll a aquare tiase, despite the atabUity of our vantage
poiDt. Thus, we may wish to include in our definition of ~~ thole vie~ha from which "relatively little" three dimeDSiorial inform~tion may be obtained, regardless of stability.
Operationally, this as~ of degeneracy can be quantified as the e~ nUJilber of additional views~ to disambiguate the ob ect; a degenerate view is therefore one that is relatively u nformative and will ~uire more images. This number clearly defpends on the compleXIty of the model data base, the intelligence o the system ~urea for determining the "best" next view,
!Jnd ~ (neCessarily) heuristic procedures of the system for . mverung the ima~e projection. A~ain, this is a system performance defininon, and an image s degree of degeneracy would change as system parameters change. ·
It would appear that this definition must be probabilistic. It is not ~ to conceive of objects or object assemblies in which multiple viewpoints give identical images, but for which the resoluti~n into a single ~nterpretation takes varying strategic paths dependin~ on the diffenng 1mage features that can appear in the second v1ew. (Take as an example a cube witli a single distinguished face 1 viewed initially so that only one non distinguished face 11 visible.) 'fhe li)'elihood of taking each path can tie quantified: the most mclus1ve meuure of an image's deg~neracy would be then be its probability-labeled search tree. yanous measures baaed on the full tree (one of which is, of course, 11 expected depth) could also serve as a measure of degeneracy pnder this deffnitio!l, tree. breadth has no strong role: a degenerate 1ma~e can. resolve 1tself mto hundreds of images, but as long as eacli new 1mage was interpretable, the origiruil image is no less dege~ra.te thali .the pyramid viewed from below.
It IS , m~resnng to note a paradoxical consequence of this systems vt.ew .of degeneracy. As .a ~ystem's power increases due to the availability of more sophisticated shape analyzing tools (such as when shape from skewed symmetry 1s used with shape f~m sha~in$), more types of ambiguity are possible. Each methOd bl}ngs WI~ It a weakness. The implication is that vision systems With mulnple sources of knowledge must know when to ignore a sou~. undergoing d~ge~~acy. This meta-knowledge can be explicitly coded, or 1mplic1tly handled by means of a flexible enough representation that permits "don't know much" as a valid answer.
4 Specific Imaging Degeneracies
Considering now only 1mages of polyhedral objects, it is possible to ~ve a catalogue of ima&e degeneracies. Each is based on a specific heuristic for invertin$ the three-dimension to two dimension image function. The hst is partial 1 and omits some heuristics that are even more fundamental, sucn as the generally assumed heuristic rules that lines in the image have been caused by lines in three-space. (In this last case, this would imply that any planar curve Imaged from within its plane would often be considered as degenerate, if the system were unable to interpret it u other than a linear object.)
4.1 Vertices Imaged in the Plane of Scene Edges
Apparent!)' the major source of "degenerate views" in the blockS worlCI (see Fill!re 1), so-called coincidental alignments occur when the image of a vertex appears to fall on the image of an edge. They confound the basic imaging assumption that three or more Hnes coincident in the image are coincident in the scene. If the scene is analyzed using labeiHng, the labellin& will fail. The image is then degenerate because another image 1s required. In

theory, such coi~idental alig~nts have probability zero, since ~ c.am~ra mus~ he on a spec~fic plane (or more precisely, in the mfirute mtersectton of two co-planar half-planes).
4.2 ~a~llel Scene Lines Imaged in Their Own Plane
This IS one of the degeneracies observed with the cube (see figu~ 2). . It v!olates the heuristi~ ~ colinear in the image 1mphes colmear m the scene, a heunsnc often not used. Hence it is system-sensitive. In theory, it also has probability ze~, althouah the camera placement IS somewhat more free than in the case of' vertex-on-edge.
4.3 Coincident Scene Lines Imaged in Their Own Plane
This is a special case violation of linear in the image implies linear in space. Again, this is system dependent and has probability of zero. (Figure 3 illustrates one example of this aegeneracy while viewing a pyramid.)
4.4 Perfect Symmetry
This is an interesting extreme case, and one apparently avoided by professional photographers as it appears to flatten relief (we provide a straiglitforwaro example of perfect symmetry in Figure ~). It is apparently based on the heuristic that symmetry in the image implies symmetry in the scene perpendicular to the line of aiglit. Arialogoua to wliat happens when a cube is imaged as two congruent rectangles, it is often degenerate since ~rfectly symmetric images lack the cues to depth that broken (skewea) symmetries provide. It has a probability of zero of occurring ideally, althOugh the camera now has the freedom to move in at least one entire plane.

5 The Effect of Finite Resolution
The various viewing points for our camera may be modeled 11 points on a viewing sphere at whose center lies the object of mterest Therefore, in the ideal case of the cube with mfinite resolution under orthography (or, for that matter, under perspective) there are precisely six viewing directions from which we see exactly one face of the cube and no more. Similarly, a family of three mutually orthogonal great circles which intersect at these six points determine the set of directions from which we would see exactly two faces of the cube. Anywhere else on the sphere we see three faces (see Figure 5). A point on the sphere chosen at random will be a viewpoint imaging three faces with probability 1.
Of course, any real system will have only finite resolution, How this resolution IS measured and how repeatable it is, eat1 vary depending on application. For the cube, resolution appears to be the ability to separate two nearly concurrent parallel lines into their separate sources. (Under perspective, the pafallellines would only be nearly parallel.) Assuming this resolvability of parallels IS independent of the line segment lengths (adinittedly, this is somewhat unrealistic), then the zero probabilities of degeneracy become finite. On the viewing sphere, the great circles have become bands, and the points of single face viewing have become spherical squares (see Figure 6). Their relative areas (and hence tlie probability of de~eneracy) are straightforward to compute in terms of camera acu1ty. The less accurate the camera, or the farther it is away, or the smaller the object, the larger the likelihood that a vie)NPOint is degenerate. In the extreme, the bands mer&e !ind ~ Viewpoint sees a "characteristic" view: the images are mfirutely degenerate.
The edg~~ of the bands, however, c~nnot be sharp. Although the bands partition the surface of the VIewing sphere their bOrders represent those viewing directions at which parallel lines are "first" seen as two lines. Given camera inaccuracy and noise this transition to resolvability cannot be sudden. Dependina o~ the camera ~d the accuracy of the algorithms processin_g 1ts data, ~epeatabihty may .best be represented by a fuzzy boundary. Thus Instead ?f e!lch pomt .on the sphere having a label, it has a vector of (la~l. l~kelihoo<i).Parrs. Each degeneracy region, then, fades away m likelihood as It extends farther from its ideal point or great circle. The actual computation of the shape of this probability density depends on the image heuristic used for image function invers1on, as well as some measure of camera ana software precision. Nevertheless, the relative size of the integral of probability over the l'lf?tion eat1 give an accurate estimate of the likelihood that a particular view, degenerate or not, will be visible after a random camera placement.

Degeneracies Delineated
5.1 Comments
In a sense these aspect maps are property spheres, where the property is a type of deJCneracy. Com_p~ting them demands substantial computational ume and storage [Best and Jain 85]; both would benefit from a hierarchic, trixel.:Jike approach. Note that aince the sphere ia toPQloaically ~!Qui valent to· the extended plane, all auch maps eat1 be drawn 11 planar graphs [Werman, Baugher, and Gualtieri 86]. (Seo Pi~ 7, wliere the "standard"aspect araph has been augmented to ahow all possible transitiona out of degenerate viewa, u alluded to in [Cutore 84t··).
6 Minimal Dlsambipatlon Distance
Transitions between die various regions of the sphere re~sent what [Koenderink and van Doom 79] term a "visual event' . Only such a transition is capable of yielding qualitatively new information. Thus these transitions clearly re~nt a useful change of viewpoint, which would be worth paying for in terms of traveling distance. , .
For the purposes of minimizing the distance traveled in obtaining fuithei' images, it wiU be useful to quantify the minimal distance we must travel on our viewing spheie, to ensure that we will experience a visual event If we reach a characteristic view from which an image has not yet been obtained, then we will ~aximize the. probability tliat any degeneracy will be
···m partlcul.-, we have lddecl, without lou of plllllrity, the dlroct llalllili0111 between regions wha'e 1 fece iJ vilible, aDd regions where 3 facca are vilible. We DOticed that in their exullent aurvey 011 3D objec:t m:opitioo, [Bealllld Jain 85, p. 89] did not allow auch lrlnlilionl in their upect graph of 1 cube, DOr did their analoguea appear in the upect graph of 1 lclnhedroa, praentecl by Koeaderink aDd van Doom. Fer an intereatlng diacllllion of the relevance of auch llalllitlona to robotic vilioo, aeethe reiDIIrb of N. Badlc:r in [Cutore 84]

[Planar] Aspect Graph for Cube, including 1-face to 3-face Transitions
disambiguated by The new inJonnation. In the case of our viewing sphere of a cube, this would mean ensuring that a 3-faced image is obtained.
Using the assum,Ptions of orthographic projection, we can easily quantity this mirumum distance (for die geometric proof, see [Kender and Freudenstein 87]). For a fixed viewing-sphere radius of resolution n (i.e. n is an absolute number equal to the number of pixels our object will occupy in the image), the distance we must travel along the viewing sphere is equal to the product of the length of the radius and the arcsin of (1 In) radians.
In other words, we can quantify the minimal disambiguation angle as theta, where
7 Relative Probabilities for the Cube
We might, in a given situation, wish to know the probability of reaching a particular class of viewpoint, given a random decision as to "where to go next." For the case of the cube, we can obtain the probabilities of 1, 2, and 3-faced views, by using spherical geometry to calculate the relative surface areas on the viewing sphere of the 3 regions described above and depicted in figure 6 (square, rectangular, and triangular patches).
An analysis of the cube shows that these probabilities are generally a function of system resolution : Systems capable of higher resolution will generally be less likely to yield " uncharacteristic" views, as one would expect.
Our results, the complete derivations of which are presented in [Kender and Freudenstein 87], are as follows :
8 Closing Observations and Future Research
Calculatm$ the number of necessary views and the effort to obtain them IS a formidable task. In some senses it resembles the design of part feeders [Natarajan 86]: that is, given an unknown position on the viewing sphere, determine what series of camera movements would inevitably lead to a distinguished configuration, namely, the a~uisition of all relevant semantic information about an object or object assembly. Even assuming one knows perfectly where one is on the viewing sphere, the determination of even the distance to the neare~t visual event is complex, given its probabilistic nature. Circutnstances are easy to construct (for example, when the object is too small) where it is actually impossible.
The aspect map can be augmented with other infonnation. It can incorporate probabilities such as the likelihood of a given gravity-induced preferred orientation, or it can be convolved with a placement uncertainty spread function. The spread function can be variable, itself incorporating such infonnation as the robotic work space or other constraints on placement motion. A search for the optimal next view could then also minimize camera placement error and also, by related methods, camera placement costs:
Such algorithms would be particularly valuable if ways exist to formally combine the aspect maps of individual objects to create the aspect map of an object assemblr. Thus, from a few primitives and a little kilowledge of the robooc placer and its workspace, a single representation could direct active sensin~. Whether or not such a rel'resentation is ultimately practical, It has nevertheless been helpful in elucidating the meanings of "general viewing position' and ''degenerate view''.
@inproceedings{ijcai1987p165,
title = {What is a 'Degenerate' View?},
author = {Kender, John R. and Freudenstein, David G.},
booktitle = {Proceedings of the Tenth International Joint Conference on
Artificial Intelligence, {IJCAI-87}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John McDermott},
pages = {801--803},
year = {1987},
note = {Perception},
url = {https://ijcai.org/proceedings/1987/165},
}
TY - CPAPER TI - What is a 'Degenerate' View? AU - Kender, John R. AU - Freudenstein, David G. T2 - Proceedings of the Tenth International Joint Conference on Artificial Intelligence, IJCAI-87 PB - International Joint Conferences on Artificial Intelligence PY - 1987 SP - 801 EP - 803 UR - https://ijcai.org/proceedings/1987/165 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: