Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-07-11
2004-02-17
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06693630
ABSTRACT:
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
, ⇄
&thgr;
,
) and g is a property of line segments while ⇄
i
, ⇄
j
, ⇄
&thgr;
, 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 (&thgr;)}(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 (&rgr;)}(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 (&rgr;)}(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
⇄
&thgr;
l
j
, instantiating [{dot over (&thgr;)}(l
i
)={dot over (&thgr;)}(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 (&rgr;)}(l
i
)·&sgr;≦{dot over (l)}
j
(&rgr;(p(l
i
),l
j
))·&sgr;] 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.
REFERENCES:
patent: 6044306 (2000-03-01), Shapiro et al.
patent: 6243106 (2001-06-01), Regh et al.
Bailey, D., et al., “Extending Embodied Lexical Development”, Proceedings of the 20th Annual Conference of the Cognitive Science Society, 1998.
Regier, T.P., “The acquisition of lexical semantics for spatial terms: A connectionist model of perceptual categorization” Ph.D. Thesis, University of California et Berkeley, 1992.
Siskind, J.M., et al., “A Maximum-Likelihood Approach to Visual Event Classification”, Proceedings of the Fourth European Conference on Computer Vision, pp. 347-360, 1996.
Starner, T.E., “Visual Recognition of American Sign Language Using Hidden Markov Models”, Master's Thesis, Massachusetts Institute of Technology, Cambridge, MA, pp. 2-52, 1995.
Talmy, L., “Force Dynamics in Language and Cognition”, Cognitive Science, vol. 12, pp. 49-100, 1998.
Yamata, J., et al., “Recognizing Human Action in Time-Sequential Images using Hidden Markov Model”, Proceedings of the IEEE Conference in Computer Vision and Pattern Recognition, pp. 379-385, 1992.
Bobick, A.F., et al., “Action Recognition Using Probabilistic Parsing”, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 196-202, 1998.
McCarthy, J., “Circumscription—A Form of Non-Monotomic Reasoning”, Artificial Intelligence, vol. 13, pp. 27-39, 1980.
Blum, M., et al. “A Stability Test For Configurations Of Blocks”, Artificial Intelligence Memo No. 188, pp. 1-31, 1970.
Brand M., et al., “Sensible Scenes: Visual Understanding of Complex Structures through Casual Analysis”, Proceedings of the Eleventh National Conference on Artificial Intelligence, pp. 588-593, 1993.
Fahlman, S.E., “A Planning System for Robot Construction Tasks”, Artificial Intelligence, vol. 5, pp. 1-49, 1974.
Mann, R., “The Computational Perception Of Scene Dynamics”, Ph.D. Thesis, University of Toronto, 1998.
Mann, R., et al., “Towards the Computational Perception of Action”, Proceedings of the IEEE Computer Science Conference on Computer Vision and Pattern Recognition, pp. 794-799, 1998.
Mann, R., et al., “The Computational Perception of Scene Dynamics”, Computer Vision and Image Understanding, vol. 65, No. 2, pp. 113-128, 1997.
Mann, R., et al., “The Computational Perception of Scene Dynamics”, Proceedings of the Fourth European Conference on Computer Vision, 1996.
Siskind, J.M., “Naive Physics, Event Perception, Lexical Semantics, and Language Acquisition”, Ph.D. Thesis, Massachusetts Institute of Technology, 1992.
Siskind, J.M., “Grounding Language in Perception”, Proceedings of the Annual Conference of the Society of Photo-Optical Instrumentation Engineers, Boston, MA 1993.
Siskind, J.M., “Axiomatic Support for Event Perception”, Proceedings of the AAAI-94 Workshop on the Integration of Natural Language and Vision Processing, 1994.
NEC Laboratories America, Inc.
Nguyen Phu K.
Scully Scott Murphy & Presser
LandOfFree
Method of determining the stability of two dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of determining the stability of two dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining the stability of two dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3327397