Browsing by Author "Bixler, J. Patrick"
Now showing 1 - 10 of 10
Results Per Page
Sort Options
- Constraints, a model of computationMantha, Suryanarayana M. (Virginia Tech, 1987-07-05)In this thesis constraint solving/satisfaction is presented as a model of computation. Advantages of using constraints as a paradigm of programming are presented. A semantic schema for constraint based computations is given, following a brief survey of the more important systems based on constraints. These systems range from particular algorithms to problem solvers to constraint based general purpose programming languages. Finally, constraint satisfaction is applied to logic programming and theorem proving. It is shown that incorporating constraint solving in definite clause programs enhances their expressive power. Also, an alternative semantics - based on constraint satisfaction - is given for theorem proving.
- Continuous Homotopies for the Linear Complementarity ProblemWatson, Layne T.; Bixler, J. Patrick; Poore, Aubrey B. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987-05-01)There are various formulations of the linear complementarity problem as a Kakutani fixed point problem, a constrained optimization, or a nonlinear system of equations. These formulations have remained a curiosity since not many people seriously thought that a linear combinatorial problem should be converted to a nonlinear problem. Recent advances in homotopy theory and new mathematical software capabilities such as HOMPACK indicate that continuous nonlinear formulations of linear and combinatorial problems may not be far-fetched. Several different types of continuous homotopies for the linear complementarity problem are presented and analyzed here, with some numerical results. The homotopies with the best theoretical properties (global convergence and no singularities along the zero curve) turn out to also be the best in practice.
- Extending Prolog with type inheritance and arithmeticChitale, Chandan S. (Virginia Tech, 1989-05-15)Prolog is a logic programming language based on first order logic. It uses resolution as a rule of inference, and unification is the heart of resolution. The unification algorithm is a syntactic process and hence attaches no meaning to function and predicate symbols. We incorporate arithmetic into unification by simultaneously solving linear equations that are created during the unification of partially instantiated numeric expressions. Prolog operates on the Herbrand universe, which is a single unstructured domain. In case of large structured domains, the number of resolution steps required for inference is large. We have incorporated type inheritance into Prolog to exploit large structured domains. Types are subuniverses corresponding to sets of objects. The subset of relation between types induces a hierarchy on the universe. Using the property of inheritance it is possible to obtain shorter proofs in inference. We used the constraint satisfaction model and the hierarchical constraint satisfaction concept to incorporate these extensions to Prolog. Thus, we succeeded in obtaining a logic programming language with arithmetic and type inheritance. This implementation extends standard Prolog and can be directly added to the WAM concept.
- Finding Straight Lines and Curves in Engineering Line DrawingsBixler, J. Patrick; Watson, Layne T.; Sanford, J. Patrick (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987)This paper addresses the problem of distinguishing straight lines from curves in noisy gray tone images, and mathematically representing those lines and curves. A method for locating comers is discussed as well as criteria, based on spline representations, for classifying line segments as straight or curved. Results are given for several typical noisy engineering line drawings.
- General purpose visual simulation systemBishop, John Leslie (Virginia Tech, 1989-06-05)The purpose of the research described herein is to prototype a software system that aids a simulationist in developing a general purpose discrete event simulation model. A literature review has shown the need for an integrated visual simulation system that provides for the graphical definition and interactive specification of the model while maintaining application independence. The General Purpose Visual Simulation System (GPVSS) prototyped in this research meets this need by assisting a simulationist to: (1) graphically design the model and its M visualization, (2) interactively specify the model's logic, and (3) automatically generate the executable version of the model, while maintaining domain independence. GPVSS is prototyped on a Sun 3/160C computer workstation using the SunView graphical interface. It consists of over 11,000 lines of documented code. GPVSS has been successfully tested in three different case studies that are described in this work.
- Polyhedra:representation and recognitionParipati, Praveen Kumar (Virginia Tech, 1989-05-15)Computer Aided Design systems intended for three dimensional solid modelling have traditionally used geometric representations incompatible with established representations in computer vision. The utilization of object models built using these systems require a representation conversion before they can be used in automatic sensing systems. Considerable advantages follow from building a combined CAD and sensing system based on a common geometric model. For example, a library of objects can be built up and its models used in vision and touch sensing system integrated into an automated assembly line to 'discriminate between objects and determine- orientation and distance. This thesis studies a representation scheme, the dual spherical representation, useful in geometric modelling and machine recognition. We prove that the representation uniquely represents genus 0 polyhedra. We show by,example that our representation is not a strict dual of the vertex connectivity graph, and hence is not necessarily ambiguous. However, we have not been able to prove that the representation is unambiguous. An augmented dual spherical representation which is unique for general polyhedra is presented. This graph theoretic approach to polyhedra also results in an elegant method for decomposition of polyhedra into combinatorially convex parts. An algorithm implementation details and experimental results for recognition of polyhedra using a large field tactile sensor are given. A theorem relating the edges in the dual spherical representation and the edge under perspective projection is proved. Sensor fusion using visual and tactile sensory inputs is proposed to improve recognition rates.
- A pseudo maximal square moving line tracking algorithmHess, Elizabeth Beien (Virginia Tech, 1989-11-15)A new method for extracting lines from discrete binary images is proposed. The algorithm is capable of extracting individual lines and producing a structure-descriptive representation for every line extracted. The algorithm could be considered as an extension of Wakayama's Maximal Square Moving (MSM) algorithm[37] since pseudo maximal squares are substituted for maximal squares, but essentially, it is distinct from the MSM algorithm because squares are derived only in the most desirable direction while tracking a line. The resulting representation of a line is a set of points that are the centers of the pseudo maximal squares along the tracked line. This information is highly conducive to creating a high-level mathematical representation of the line being tracked. Examples are given for regions of a complex map.
- A Sensory Input System for Autonomous Mobile RobotsBixler, J. Patrick; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987)In order to accomplish navigation in an similar world a robot must be able to build and update its own world map continuously and in real time. This paper proposes a sensory input system based on the fusion of simple low-resolution vision with directed high-resolution sonar. The basic idea is to use a simple vision system to locate the position in which an obstacle lies, and then use an ultrasonic rangefinder to determine the depth of the object and to gain clues about its shape. By fusing two simple systems we attempt to exploit the strengths of each while maintaining an acceptable computational cost. An idealized example is given and we discuss the possibilities and some of the problems.
- Special Valued L-groupsBixler, J. Patrick; Darnel, M. R. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1984)Special elements and values have always been of interest in the study of lattice-ordered groups, arising naturally from totally-ordered groups and lexicographic extensions. Much work has been done recently with the class of lattice-ordered groups whose root system of regular subgroups has a plenary subset of special values. We call such l-groups special valued. In this paper, we first show that several familiar structures of l-groups, namely polars, minimal prime subgroups, and the lex kernel, are recognizable from the lattice and the identity; that is, knowing which element of the lattice is the group identity, we can pick out in the lattice all the dements of polars, minimal primes, and the lex kernel. This then leads to an easy proof that special elements can be recognized from the lattice and the identity. We then prove several results about the class S of special-valued l-groups. We give a simple and direct proof that S is closed with respect to joins of convex l-subgroups, incidentally giving a direct proof that S is a quasi torsion class. This proof is then used to show that the special-valued and finite-valued kernels of l-groups are recognizable from the lattice and the identity. We show also that the lateral completion of a special-valued l-group is special-valued and is an a*-extension of the original l-group. Our most important result is that the lateral completion of a completely-distributive normal-valued l-group is special-valued. This lends itself easily to a new and similar proof of Ball, Conrad, and Darnel's result that every normal-valued l-group can be l-embedded into a special-valued l-group. Readers familiar with the impact of the Conrad-Harvey-Holland Theorem on abelian l-groups will recognize the importance of the last theorem to the study of the class of normal-valued l-groups and to the study of proper varieties of l-groups, all of which are normal valued.
- Tracking Text in Mixed Mode DocumentsBixler, J. Patrick (Department of Computer Science, Virginia Polytechnic Institute & State University, 1988)This paper describes a method for extracting arbitrarily oriented text in documents containing both text and graphics. The technique presented is inspired by the tracking algorithms frequently found in raster to vector conversion systems. By identifying text components in the document, reducing the resolution of the image by the size of the characters, and then tracking the centers of the character components, all text strings can be removed and subsequently reoriented to the horizontal. They can then be presented for automated character recognition. A by-product of the method is that characters are automatically grouped together to form words and/or phrases. We give a detailed description of the algorithm, discuss its strengths and weaknesses, and present some sample results obtained from a typical city street map.