Abstract:
A method for determining the stability of a two dimensional polygonal scene. Each polygon in the scene includes data representing a set L of line segments comprised of individual line segments l. The method determines whether the line segments are stable under an interpretation I. I is a quintuple (g, ⇄ i , ⇄ j , ⇄ θ , ) and g is a property of line segments while ⇄ i , ⇄ j , ⇄ θ , and  are relations between pairs of line segments. The method includes the steps of: initializing a set Z of constraints and to an empty set; for each l contained in L, if g(l), instantiating [{dot over (c)}(l)=0] and [{dot over (θ)}(l)=0] and adding them to Z; for each l i , l j  contained in L, if l i ⇄ i l j  instantiating [{dot over (ρ)}(I(l i , l j ), l j )=0] between l i  and l j  and adding it to Z; for each l i , l j  contained in L, if l i ⇄ j l j  instantiating [{dot over (ρ)}(I(l i , l j ), l j )= 0 ] between l i  and l j  and adding it to Z; for each l i , l j  contained in L, if l i ⇄ θ l j , instantiating [{dot over (θ)}(l i )={dot over (θ)}(l j )] between l i  and l j  and adding it to Z; for each l j , l j  contained in L, if l i l j  instantiating [{dot over (ρ)}(l i )·σ≦{dot over (l)} j (ρ(p(l i ),l j ))·σ] between l i  and l j  and adding it to Z; instantiating [{dot over (E)}=−1] between all l of L and adding it to Z; and determining the stability of the scene based upon whether Z has a feasible solution. Also provided are a program storage device and computer program product for carrying out the method of the present invention.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to a method for determining the stability of two dimensional polygonal scenes and, more particularly, to a kinematics based method for determining the stability of two dimensional polygonal scenes which designates each scene in a sequence of scenes as either stable or unstable. 
     2. Prior Art 
     Methods are known in the art for determining the stability of a collection of blocks. These methods differ from the one presented here in that these prior methods use an approach based on dynamics whereas the method presented herein is based on kinematics. 
     Kinematics is a branch of mechanics which deals with the motion of a physical system without reference to the forces which act on that system and without reference to the precise velocities and accelerations of the components of that system. A kinematic model takes the form of a set of constraints which specify the allowed combinations of positions of system components. The allowed motions follow from the possible transitions between allowed positions. 
     In contrast, dynamics is a branch of mechanics which deals with the motion of a physical system under the influence of forces applied to the components of that system. A dynamic model takes the form of a set of constraints which specify the relation between the positions of system components and the forces on those components. The motions follow by relating forces on system components to accelerations of those components and, in turn, to velocities and positions of those components. 
     Methods are also known in the art for determining the stability of a collection of line segments and circles. These methods differ from the one presented here in that they are based on a naive physical theory rather than on kinematics. Yet other methods are known in the art for determining the stability of a collection of line segments and circles. While these methods are based on kinematics, they have some fundamental flaws which lead them to produce incorrect results. Lastly, still another method is known in the art for determining the stability of a collection of rectangles. This method differs from the one presented herein in that it is based on a heuristic that does not always work. 
     SUMMARY OF THE INVENTION 
     Therefore it is an object of the present invention to provide a method for determining stability of two dimensional polygonal scenes which overcomes the problems of the prior art. 
     Accordingly, a method for determining the stability of a two dimensional polygonal scene is provided. Each polygon in the scene includes data representing a set L of line segments comprised of individual line segments l. The method determines whether the line segments are stable under an interpretation I. I is a quintuple (g, ⇄ i , ⇄ j , ⇄ θ , ) and g is a property of line segments while ⇄ i , ⇄ j , ⇄ θ , and  are relations between pairs of line segments. The method comprises the steps of: initializing a set Z of constraints to an empty set; for each l contained in L, if g(l), instantiating [{dot over (c)}(l)=0] and [{dot over (θ)}(l)=0] and adding them to Z; for each l i , l j  contained in L, if l i ⇄ i l j , instantiating [{dot over (ρ)}(I(l i , l j ), l i )=0] between l i  and l j  and adding it to Z; for each l i , l j  contained in L, if l i ⇄ j l j , instantiating [{dot over (ρ)}(I(l i , l j ), l j )=0] between l i  and l j  and adding it to Z; for each l i , l j  contained in L, if l i ⇄ θ l j , instantiating [{dot over (θ)}(l i )={dot over (θ)}(l j )] between l i  and l j  and adding it to Z; for each l i , l j  contained in L, if l i l j , instantiating [{dot over (ρ)}(l i )·σ≦{dot over (l)} j (ρ(p(l i ),l j ))·σ] between l i  and l j  and adding it to Z; instantiating [{dot over (E)}=−1] between all l of L and adding it to Z; and determining the stability of the scene based upon whether Z has a feasible solution. 
     Also provided are a computer program product and program storage device for carrying out the method of the present invention and for storing a set of instructions to carry out the method of the present invention, respectively. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other features, aspects, and advantages of the methods of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where: 
     FIG. 1 is a schematic diagram depicting various support relations of blocks A, B, C, D, E, and F shown in the Figure. 
     FIGS.  2 ( a ) and  2 ( b ) are schematic diagrams of the same scene but with different ground relationships and therefore different stability interpretation. 
     FIG.  3 ( a ) is a schematic diagram representing a block F resting on two blocks G and H that are rigidly attached to a grounded table top. 
     FIG.  3 ( b ) is a schematic diagram representing an attachment relation between a hand I and a block J. 
     FIGS.  4 ( a ),  4 ( b ) are schematic diagrams representing a rigid joint, a revolute joint, and a prismatic joint, respectively. 
     FIGS.  5 ( a ),  5 ( b ),  5 ( c ), and  5 ( d ) are schematic diagrams which define differing attachment relations and therefore different stability interpretations. 
     FIGS.  6 ( a ) and  6 ( b ) are schematic diagrams depicting different depth interpretations effecting differing stability judgments on similar scenes. 
     FIGS.  7 ( a ),  7 ( b ),  7 ( c ), and  7 ( d ) are sets of sequential frames of four movies which were analyzed by a machine vision system utilizing the stability determination method of the present invention. 
     FIG. 8 is a schematic flow diagram depicting one embodiment of the stability determination method of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Although this invention is applicable to numerous and various types of scenes, it has been found particularly useful in the environment of scenes generated by placing polygons around objects in a video frame. Therefore, without limiting the applicability of the invention to scenes generated by placing polygons around objects in a video frame, the invention will be described in such an environment. 
     For the purposes of this direction, a scene is defined as a set of polygons having a relationship to one another. Each polygon is represented by a number of line segments, each line segment having two endpoints. Preferably, the scenes are generated by taking a video sequence as input and outputting a sequence of scenes, one scene for each video input frame. Each scene consists of a collection of convex polygons placed around the objects in the corresponding image. 
     Referring now to FIG. 1, there is illustrated a scene  100  having a polygons A-F in various positions in relation to a table top  102 . If one were to look at the scene  100  in FIG. 1, he or she would say that polygon A is supported by the table top  102 , and hence will not fall, while polygon B is unsupported, and hence will fall. Humans have the ability to make stability judgments. The method of the present invention presents a way that such judgments can be made artificially, such as by a computer (not shown). 
     In FIG. 1, polygon A is supported by virtue of the fact that it is above and in contact with the table top  102 . This alone is not sufficient to guarantee stability, for polygon C is also above and in contact with the table top  102  yet is not stable because it can rotate either clockwise or counterclockwise. An object may require more than one source of support. For example, in FIG. 1, polygons D and E are not stable, because they can slide off their pedestals, while F is stable. Thus determining the stability of a scene requires analyzing the degrees of freedom of motion of the polygons in the scene and showing that no polygon can move under the force of gravity. 
     So far, the only notion used to explain the stability of a scene is surface-to-surface contact. However, this is insufficient. In FIG. 1, the table top  102  supports polygons A and F and prevents them from falling. But what supports the table top  102  and prevents it from falling? To account for the stability of the table top, one needs to ascribe to it the distinguished property of being grounded, i.e. of being inherently supported and not requiring any further source of support. This property is indicated by the ground symbol  202  attached to the table top  102  in FIG.  2 ( a ). In doing so, one analyzes a scene under an interpretation. Some aspects of a scene are visible. For example, the positions, orientations, shapes, and sizes of the polygons in the scene. Other aspects of a scene are invisible and subject to interpretation. For example, which polygons are grounded. This leads to the possibility of multiple interpretations of a scene, some of which are stable and some of which are not. For example, if the table top  102  is grounded and polygon A is not, as in FIG.  2 ( a ), the scene is stable, while if polygon A is grounded while the table top  102  is not, as in FIG.  2 ( b ), the scene is not stable. 
     In actuality, polygon F in FIG. 1 is also unstable. Because, in the absence of friction, the two polygons G and H that support polygon F can slide sideways along axis X—X. To explain the stability of polygon F, one can hypothesize the polygons G and H are attached to the table top  102 , as shown in FIG.  3 ( a ). Likewise, suppose that FIG.  3 ( b ) depicts a hand I grasping a block J. To explain the stability of polygon J, one must hypothesize that polygon J is attached to polygon I, even if polygon I is grounded. These attachment relations are indicated by small solid circles in FIGS.  3 ( a ) and  3 ( b ). 
     There are a wide variety of different kinds of attachment relations. Each kind of attachment relation imposes different constraints on the relative motion of the attached polygons. In this patent disclosure, three kinds of attachment relations are considered, namely rigid joints, revolute joints, and prismatic joints. Rigid joints, indicated by small solid circles, constrain the relative rotation and translation of the attached objects. FIG.  4 ( a ) depicts a rigid joint  402 , hand I grasping block J. Revolute joints  404 , indicated by small unfilled circles, constrain the relative translation of the attached polygons but allow one polygon to rotate relative to the other about the revolute joint  404 . FIG.  4 ( b ) depicts a revolute joint  404  between a washing machine cover  406  and its base  408 . Prismatic joints  410 , indicated by small solid circles with small thick lines along one of the joined edges, constrain the relative rotation of the two attached polygons but allow one polygon to translate relative to the other along the direction of the small thick line. FIG.  4 ( c ) depicts a prismatic joint  410  between a drawer  412  and its cabinet  414 . 
     Attachment relations, like the grounded property, are subject to interpretation. And just as is the case for the grounded property, different interpretations of the same scene that specify different attachment relations will lead to different stability judgments. FIGS.  5 ( a )- 5 ( d ) show four different interpretations of the same scene  500 . The interpretations of scene  500  shown in FIGS.  5 ( b ) and  5 ( c ) are stable, because polygons K and L cannot move under the force of gravity, while the interpretations in FIGS.  5 ( a ) and  5 ( d ) are not stable, because polygon L is free to rotate clockwise in FIG.  5 ( a ) about revolute joint  404  and polygon L is free to translate vertically in FIG.  5 ( d ) along prismatic joint  410 . 
     The world is three dimensional while images are 2D projections of the 3D world. When you see a scene  600 , like that in FIGS.  6 ( a ) and  6 ( b ), it is unclear whether polygon A is in front of, on, or behind the table  102 . Like the grounded property and attachment relations, different interpretations of the relative depth of polygons will lead to different stability judgments. If polygon A is on the table  102 , as shown in FIG.  6 ( a ), then the scene  600  is stable. If polygon A is in front of or behind the table  102 , as shown in FIG.  6 ( b ), then the scene  600  is not stable. For purposes of this disclosure, it is assumed that each polygon lies on a plane that is parallel to the image plane. Any two polygons are said to either be on the same layer or on different layers. Two polygons are depicted as being on the same layer by giving them the same layer index (FIG.  6 ( a ) shows both polygon A and the table  102  as having the same layer index  0 ). Two polygons are depicted as being on different layers by giving them different layer indices (FIG.  6 ( b ) shows polygon A at layer index  1  and the table  102  at layer index  0 ). Two polygons can be in contact only if they are on the same layer. Thus one polygon can support another polygon by contact only if they are on the same layer. 
     The methods of the present invention use an algorithm STABLE (P, I) for determining the stability of a polygonal scene under an interpretation. The input to this method consists of a scene having a set P of polygons and an interpretation I. The output is a designation of Stable or Unstable indicating whether or not the scene is stable. 
     The primary application that is currently being considered for the methods of the present invention is visual event perception. In this application, a video camera is connected to a computer system and the computer system recognizes simple actions performed by a human in front of the video camera. For example, the human can pick up or put down blocks. The counter system takes the video input, digitizes it, segments each frame of the video input into the participant objects and tracks those objects over time. A scene is generated for each frame by placing polygons around the human&#39;s hand and other objects in the scene. The computer then generates all possible interpretations for each scene, checks the stability of each interpretation for each scene and constructs a preferred set of stable interpretations for each scene. With a sequence of such preferred stable interpretations, a pick up event can be recognized by detecting a state change where the object being picked up starts out being supported by being in contact with the table and is subsequently supported by being attached to the hand. Likewise, a put down event can be recognized by detecting the reverse state change. The approaches to visual event classification of the prior art use motion profiles rather than changes in support, contact, and attachment relations. 
     A prototype implementation has been constructed for the methods of the present invention. FIGS.  7 ( a )- 7 ( d ) show the results of processing four short movies with this implementation, the movies illustrated in FIGS.  7 ( a )- 7 ( d ) are referred to generally by reference numerals  700 ,  720 ,  740 , and  760 , respectively. Each Figure shows a subset of the frames from a single movie. From FIGS.  7 ( a ) to  7 ( d ), the movies  700 ,  720 ,  740 , and  760  have 29, 34, 16, and 16 frames, respectively, of which six frames are shown. Each movies was processed by a segmentation procedure to place convex polygons around the colored and moving objects in each frame. A tracking procedure computed the correspondence between the polygons in each frame and those in the adjacent frames. Such segmentation and tracking procedures are well known in the art and can be automatically or manually carried out by software. A model reconstruction procedure was used to construct a preferred stable interpretation of each frame. This model reconstruction procedure used the stability determination methods of the present invention. Each frame is shown with the results of segmentation and model reconstruction superimposed on the original video image. 
     Referring to movie  700  illustrated in FIG.  7 ( a ), notice that the method of the present invention determines that the lower block  702  and the hand  704  are grounded for the entire movie  700 , that the upper block  706  is supported by being on the same layer as the lower block  702  for frames  2 ,  4 , and  8 , and that the upper block  706  is supported by being rigidly attached to the hand  704  for frames  20 ,  22 , and  24 . Referring to movie  720  illustrated in FIG.  7 ( b ), notice that the method of the present invention determines that the lower block  722  and the hand  724  are grounded for the entire movie  720 , that the upper block  726  is supported by being rigidly attached to the hand  724  for frames  5  and  10 , and that the upper block  726  is supported by being on the same layer as the lower block  722  for frames  21 ,  24 ,  26 , and  29 . Referring to movie  740  illustrated in FIG.  7 ( c ), notice that the method of the present invention determines that the lower block  742  and the hand  744  are grounded for the entire movie  740  and that the upper block  746  is supported for the entire movie  740  by being on the same layer as the lower block  742 . Referring to movie  760  illustrated in FIG.  7 ( d ), notice that the method of the present invention determines that the lower block  762  and the hand  764  are grounded for the entire movie  760  and that the upper block  766  is supported for the entire movie  760  by being rigidly attached to the hand  764 . 
     The prototype implementation was given the following lexicon when processing the movies  700 ,  720 ,  740 , and  760  of FIGS.  7 ( a )- 7 ( d ):        PICKUP        (     x   ,   y     )                                [                  SUPPORTED        (   x   )              SUPPORTED        (   y   )                      (            ATTACHED        (     x   ,   y     )         ;     ATTACHED        (     x   ,   y     )         )           ]               PUTDOWN        (     x   ,   y     )                                  [                  SUPPORTED        (   x   )              SUPPORTED        (   y   )                      (       ATTACHED        (     x   ,   y     )       ;          ATTACHED        (     x   ,   y     )           )           ]                            
     Essentially, these define pick up and put down as events where the agent (hand) is not supported throughout the event, the patient (block) is supported throughout the event, and the agent grasps or releases the patient, respectively. The methods of the present invention correctly recognize the movie  700  in FIG.  7 ( a ) as depicting a pick up event and the movie  720  in FIG.  7 ( b ) as depicting a put down event. More importantly, the methods of the present invention correctly recognize that the remaining two movies  740 ,  760  of FIGS.  7 ( c ) and  7 ( d ) do not depict any of the defined event types. 
     Note that systems of the prior art that classify events based on motion profiles will often mistakenly classify these last two movies  740 ,  760  as either pick up or put down events because they have similar motion profiles. 
     An algorithm used in the methods of the present invention to make a determination of stability for a given score will now be described. The algorithm, named STABLE (P, I), that determines whether a set P of polygons is stable under an interpretation I is determined by reducing the problem to determining whether a set L of line segments is stable under an interpretation I. Thus, the algorithm STABLE (P, I) is defined from STABLE (L, I) simply by considering each polygon to be a set of rigidly joined line segments on the same layer. 
     The line segments in a scene have fixed positions and orientations. The coordinates of a point p are denoted as x(p) and y(p). The endpoints of a line segment l are denoted as p(l) and q(l). The length of a line segment l is denoted as ||l||. The position of a line segment is denoted as the position of its midpoint c. The orientation θ(l) of a line segment l is denoted as the angle of the vector from p(l) to q(l). The quantities p(l), q(l), ||l||, c(l), and θ(l) are all fixed in a given scene. And p(l) and q(l) are related to ||l||, c(l), and θ(l) as follows:          c        (   l   )       =         p        (   l   )       +     q        (   l   )         2                  l        =         (       q        (   l   )       -     p        (   l   )         )     ·     (       q        (   l   )       -     p        (   l   )         )                   θ                   (   l   )       =       tan     -   1                           y        (     q        (   l   )       )       -     y        (     p        (   l   )       )             x        (     q        (   l   )       )       -     x        (     p        (   l   )       )                       x        (     p        (   l   )       )       =       x        (     c        (   l   )       )       -       1   2             l           cos                 θ                   (   l   )                   y        (     p        (   l   )       )       =       y        (     c        (   l   )       )       -       1   2             l           sin                 θ                   (   l   )                   x        (     q        (   l   )       )       =       x        (     c        (   l   )       )       +       1   2             l           cos                 θ                   (   l   )                   y        (     q        (   l   )       )       =       y        (     c        (   l   )       )       +       1   2             l           sin                 θ                   (   l   )                                
     An interpretation I is a quintuple &lt;g, ⇄ i , ⇄ j , ⇄ θ , &gt;, g is a property of line segments while ⇄ i , ⇄ j , ⇄ θ , and &#39;s are relations between pairs of line segments. The assertion g(l) indicated that line segment l is grounded. The assertion l i ⇄ i  l j  indicates that the position of the intersection of l i  and l j  is fixed along l i . The assertion l i ⇄ j  l j  indicates that the position of the intersection of l i  and l j  is fixed along l j . The assertion l i ⇄ θ l j  indicates that the angle between l i  and l j  is fixed. Collectively, ⇄ i , ⇄ j , and ⇄ θ  describe the attachment relations. 
     IF l i ⇄ i  l j Λl i ⇄ j  l j Λl i ⇄ θ l j , then l i  and l j  are joined by a rigid joint  402 . If l i ⇄ i l j Λl i ⇄ j l j Λl i  not ⇄ θ l j , then l i  and l j  are joined by a revolute joint  404 . If l i  not ⇄ i l j Λl i ⇄ j l j Λl i ⇄ θ l j , then l i  and l j  are joined by a prismatic joint  410  that allows l j  to slide along l i . IF l i ⇄ i l j Λl i  not ⇄ j l j Λl i ⇄ θ l j , then l i  and l j  are joined by a prismatic joint  410  that allows l i  to slide along l j . If l i  not ⇄ i l j Λl i  not ⇄ j l j Λl i  not ⇄ θ l j , then l i  and l j  are not joined. Finally, the assertion l i l j  indicates that l i  and l j  are on the same layer. 
     An interpretation is admissible if the following conditions hold: 
     For all l i  and l j , if l i ⇄ i l j , l i ⇄ j l j , or l i l j , then l i  intersects l j . 
     For all l i  and l j , l i ⇄ i l j  if l j ⇄ j l i . 
     ⇄ θ  is symmetric. 
     For all l i  and l j , if l i l j , then l i  and l j  do not overlap. Two line segments overlap if they intersect in a non-collinear fashion and the point of intersection is not an endpoint of either line segment. 
      is symmetric and transitive. Only admissible interpretations are considered. 
     Let us postulate an unknown instantaneous motion for each line segment l in a scene. This can be represented by associating a linear and angular velocity with each line segment l. Such velocities are denoted with the variables {dot over (c)}(l) and {dot over (θ)}(l). It is assumed that there is no motion in depth so the  relation does not change. If the scene contains n line segments, then there will be 3n scalar variables, because {dot over (c)} has x and y components. Assuming that the line segments are rigid, i.e. that instantaneous motion does not lead to a change in their length, one can relate {dot over (p)}(l) and {dot over (q)}(l), the instantaneous velocities of the endpoints, to {dot over (c)}(l) and {dot over (θ)}(l), using the chain rule as follows:            p   .          (   l   )       =           ∂     p        (   l   )           ∂     x        (     c        (   l   )       )                x        (       c   .          (   l   )       )         +         ∂     p        (   l   )           ∂     y        (     c        (   l   )       )                y        (       c   .          (   l   )       )         +         ∂     p        (   l   )             ∂   θ                     (   l   )              θ   .                     (   l   )                     q   .          (   l   )       =           ∂     q        (   l   )           ∂     x        (     c        (   l   )       )                x        (       c   .          (   l   )       )         +         ∂     q        (   l   )           ∂     y        (     c        (   l   )       )                y        (       c   .          (   l   )       )         +         ∂     q        (   l   )             ∂   θ                     (   l   )              θ   .                     (   l   )                                
     where each of {dot over (p)}(l) and {dot over (q)}(l) are linear in {dot over (c)}(l) and {dot over (θ)}(l). 
     Each of the components of an admissible interpretation of a scene can be viewed as imposing constraints on the instantaneous motions of the line segments in that scene. The simplest case is the g property. If g(l), then 
     
       
         {dot over (c)}(l)=0  (1)  
       
     
     and 
     
       
         {dot over (θ)}(l)=0  (2)  
       
     
     Note that equations (1) and (2) are linear in {dot over (c)}(l) and {dot over (θ)}(l). 
     Let us now consider the l i ⇄ i l j  and l i ⇄ j l j  relations and the constraint that they impose on the motions of l i  and l j . First, the intersection of the l i  and l j  is denoted as I(l i ,l j ). If we let        A   =     (             y        (     p        (     l   i     )       )       -     y        (     q        (     l   i     )       )                 x        (     q        (     l   i     )       )       -     x        (     p        (     l   i     )       )                     y        (     p        (     l   j     )       )       -     y        (     q        (     l   j     )       )                 x        (     q        (     l   j     )       )       -     x        (     p        (     l   j     )       )               )             b   =     (               y        (     p        (     l   i     )       )            (       x        (     q        (     l   i     )       )       -     x        (     p        (     l   i     )       )         )       +       x        (     p        (     l   i     )       )            (       y        (     p        (     l   i     )       )       -     y        (     q        (     l   i     )       )         )                       y        (     p        (     l   j     )       )            (       x        (     q        (     l   j     )       )       -     x        (     p        (     l   j     )       )         )       +       x        (     p        (     l   j     )       )            (       y        (     p        (     l   j     )       )       -     y        (     q        (     l   j     )       )         )               )                            
     then I(l i ,l j )=A −1 b. 
     Next, let us denote by ρ(p,l), where p is a point on l, the fraction of the distance where p lies between p(l) and q(l).          ρ        (     p   ,   1     )       =           (     p   -     p        (   l   )         )     ·     (     p   -     p        (   l   )         )            l                                   
     Recall that I(l i , l j ) is the intersection of l i  and l j . Thus ρ(I(l i , i j ), l i ) is the fraction of the distance of that intersection point along l i . Next, let us compute {dot over (ρ)}(I(l i , l j ), l i ), which is the change in ρ(I(l i , l j ), l i ). Let α be the vector containing the elements x(p(l i )), y(p(l i )), x(q(l i )), y(q(l i )), x(p(l j )), y(p(l j )), x(q(l j )), and y(q(l j )), let β be the vector containing the elements x(c(l i )), y(c(l i )), θ(l i ), x(c(l j )), y(c(l j )), and θ(l j ), let γ be the vector where            Y   k     =       ∂     ρ        (       I        (       l   i     ,     l   j       )       ,     l   i       )           ∂     α   k           ,                          
     and let D be the matrix where D kl =aα k/ aβ l . {dot over (ρ)}(I(l i , l j ), l i ) can be computed by the chain rule as follows: 
     
       
         {dot over (ρ)}(I(l i ,l j ),l i )=γ T D{dot over (⇄)} 
       
     
     Note that {dot over (ρ)}(I(l i , l j ), l i ) is linear in {dot over (c)}(l i ), {dot over (θ)}(l i ), {dot over (c)}(l j ), and {dot over (θ)}(l j ) because all of the partial derivatives are constant. 
     Similarly, ρ(I(l i , l j ), l j ) is the fraction of the distance of the intersection of l i  and l j  along l j . Next, let us compute {dot over (ρ)}(I(l i , l j ), l j ), which is the change in ρ(I(l i , l j ), l j ). Let α be the vector containing the elements x(p(l i )), y(p(l i )), x(q(l i )), y(q(l i )), x(p(l j )), y(p(l j )), x(q(l j ), and y(q(l j )), let β be the vector containing the elements x(c(l i )), y(c(l i )), θ(l i ), x(c(l j )), y(c(l j ), and θ(l j ), let γ be the vector where          Y   k     =       ∂     ρ        (       I        (       l   i     ,     l   j       )       ,     l   j       )           ∂     α   k                                
     and let D be the matrix where D kl =aα k /aβ l , {dot over (ρ)}(I(l i , l j ), l j ) can be computed by the chain rule as follows: 
     
       
         {dot over (ρ)}(I(l i ,l j ),l j =γ T D{dot over (β)} 
       
     
     Note the {dot over (ρ)}(I(l i , l j ), l j ) is linear in {dot over (c)}(l i ), {dot over (θ)}(l i ), {dot over (c)}(l j ), and {dot over (θ)}(l j ) because all of the partial derivatives are constant. 
     The ⇄ i  constraint can then be formulated as follows: if l i ⇄ i l j , then 
     
       
         {dot over (ρ)}(I(l i , l j ), l i )=0  (3)  
       
     
     And the ⇄ j  constraint can then be formulated as follows: if l i ⇄ j l j , then 
     
       
         {dot over (ρ)}(I(l i , l j ), l j )=0  (4)  
       
     
     Again, note that equations (3) and (4) are linear in {dot over (c)}(l i ), {dot over (θ)}(l j ), and {dot over (θ)}(l j ). 
     Let us now consider the l i ⇄ θ l j  relation and the constraint that it imposes on the motions of l i  and l j . If l i ⇄ θ l j , then 
     
       
         {dot over (θ)}(l i )={dot over (θ)}(l j )  (5)  
       
     
     Again, note that equation (5) is linear in {dot over (θ)}(l i ) and {dot over (θ)}(l j ). 
     The same-layer relation l i l j imposes the constraint that the motion of l i  and l j  must not lead to an instantaneous penetration of one by the other. An instantaneous penetration can occur only when the endpoint of one line segment touches the other line segment. Without loss of generality, let us assume that p(l i ) touches l j . Let {overscore (p)} a denote a vector of the same magnitude as p rotated counterclockwise 90°. 
     
       
         {overscore ((x,y))}=(−y,x)  
       
     
     Let σ be a vector that is normal to l j , in the direction towards l i . 
     
       
         σ=−{overscore ([q(l j )−p(l j ))}·(q(l i )−p(l i ))]{overscore (q(l j )−p(l j ))} 
       
     
     If 0≦ρ≦1, let us denote by l(ρ) the point that is the fraction ρ of the distance between p(l) and q(l). 
     
       
         l(ρ)=p(l)+ρ(q(l)−p(l))  
       
     
     And let us denote by {dot over (l)}(ρ) the velocity of the point that is the fraction ρ of the distance between p(l) and q(l) as l moves. Let α be the vector containing the elements x(p(l)), y(p(l)), x(q(l)), and y(q(l)), let β be the vector containing the elements x(c(l)), y(c(l)), and θ(l), let γ be the vector where γ k =al(ρ)/aα k , and let D be the matrix where D kl =aα k /aβ l . 
     Again, by the chain rule: 
     
       
         {dot over (l)}(ρ)=γ T D{dot over (β)} 
       
     
     Again, not that {dot over (l)}(ρ) is linear in {dot over (c)}(l) and {dot over (θ)}(l) because all of the partial derivatives are constant. 
     An instantaneous penetration can occur only when the velocity of p(l i ) in the direction of σ is less than the velocity of the point of contact in the same direction. The velocity of p(l i ) is {dot over (ρ)}(l i ) and the velocity of the point of contact is {dot over (l)} j (ρ(p(l i , l j )). Thus if l i l j  and p(l i ) touches l j , then 
     
       
         {dot over (p)}(l i )·σ≦{dot over (l)} j (ρ(p(l i ),l j ))·σ  (6)  
       
     
     Again, note that inequality (6) is linear in {dot over (c)}(l i ), {dot over (θ)}(l i ), {dot over (c)}(l j ), and {dot over (θ)}(l j ). 
     We now wish to determine the stability of a scene under an admissible interpretation. A scene is unstable if there is an assignment of linear and angular velocities to the line segments in the scene that satisfies the above constraints and decreases the potential energy of the scene. The potential energy of a scene is the sum of potential energies of the line segments in that scene. The potential energy of a line segment l is proportional to its mass times y(c(l)). We can take the mass of a line segment to be proportional to its length. So the potential energy E can be taken as Σ lεL ||l||y(c(l)). 
     The potential energy can decrease if {dot over (ε)}&lt;0. By scale invariance, if E can be less then zero, then it can be equal to any value less than zero, in particular −1. Thus a scene is unstable under an admissible interpretation is the constraint 
     
       
         {dot over (E)}=−1  (7)  
       
     
     is consistent with the above constraints. Note that E is linear in all of the {dot over (c)}(l) values. Thus the stability of a scene under an admissible interpretation can be determined by a reduction to linear programming. 
     This leads to the following algorithm STABLE (L,I) for determining whether a set L of line segments is stable under an interpretation I where I=&lt;g, ⇄ i , ⇄ j , ⇄ θ , &gt;. 
     In summary, the method of the present invention for determining the stability of a scene can be summarized by reference to the flowchart of FIG.  8 : 
     At step  800 : Initialize the set Z of constraints to the empty set; 
     At step  802 : For each element l contained in L, if g(l), instantiate equations {dot over (c)}(l)=0 and {dot over (θ)}(l)=0, and then add them to Z; 
     At step  803 : For each l i , l j  ε L, if l i ⇄ i l j , instantiate the equation {dot over (ρ)}(I(l i , l j ), l i )=0 between l i  and l j  and add it to Z; 
     At step  804 : For each l i , l j  ε L, if l i ⇄ j l j , instantiate the equation {dot over (ρ)}(I(l i , l j ), l j )=0 between l i  and l j  and add it to Z; 
     At step  805 : For each l i , l j  ε L, if l i ⇄ θ l j , instantiate the equation {dot over (θ)}(l i )={dot over (θ)}(l j ) between l i  and l j  and add it to Z; 
     At step  806 : For each l i , l j  ε L, if l i l j , instantiate the equation {dot over (p)}(l i )·σ≦{dot over (l)} j (ρ(p(l i ),l j ))·σ between l i  and l j  and add it to Z; 
     At step  807 : Instantiate the equation {dot over (E)}=−1 between all l ε L and add it to Z; and 
     At step  808 : Pass Z to a linear programming solver as understood by one skilled in the art. 
     At step  810  a test is done to determine if Z has a feasible solution. The method outputs a designation indicating Unstable if there is a feasible solution (step  810   a ); otherwise the method outputs a designation indicating Stable (step  810   b ). These designations can take on any number of forms. Preferably, a binary logical value in which case 1 indicates a stable scene and a logical value of 0 indicates an unstable scene (or vice versa). 
     It will be apparent to those skilled in the art that the methods of the present invention disclosed herein may be embodied and performed completely by software contained in an appropriate storage medium for controlling a computer. 
     While there has been shown and described what is considered to be preferred embodiments of the invention, it will, of course, be understood that various modifications and changes in form or detail could readily be made without departing from the spirit of the invention. It is therefore intended that the invention be not limited to the exact forms described and illustrated, but should be constructed to cover all modifications that may fall within the scope of the appended claims.