New techniques for computing multicolored polygonal masks for image analysis and computer vision applications are presented. The procedures do not require random access of the image memory. They are based on efficient generation of coordinate-reference images (ramps) and other simple general purpose architectural features such as look-up tables. The techniques presented are, unlike their predecessors, highly parallel and can be efficiently implemented in existing pipeline image processors. In addition, we show an architecture in the form of functional building blocks that will enable us to compute polygonal and other masks much faster than commercially available pipeline systems. Extensive motivation and use of the new algorithms for digital visual inspection applications are given throughout.
Computing Profession
Advertisement
The effect of data structures on the logical complexity of programs
The logical complexity of a program is a measure of the effort required to understand it. We hypothesize that the logical complexity of a program increases with the increase in the opaqueness of the relationship between the physical data structures used in the program and their corresponding abstract data types. The results of an experiment conducted to investigate this hypothesis are reported. Documentation techniques for making programs easier to understand using complex data structures are discussed. Data structure diagrams, data structure invariants, stepwise transformation of data structures, and formal specification of the mapping between abstract and concrete data structures are illustrated using two nontrivial examples.
Instead of limiting functionality, usability complements functionality. It affects how and with what effectiveness a system is used, and even whether or not it is used at all.
Computer science: the emergence of a discipline
The continued rapid development of computer science will require an expansion of the science base and an influx of talented new researchers. Computers have already altered the way we think and live; now they will begin to elevate our knowledge of the world.
Pairing heaps: experiments and analysis
The pairing heap has recently been introduced as a new data structure for priority queues. Pairing heaps are extremely simple to implement and seem to be very efficient in practice, but they are difficult to analyze theoretically, and open problems remain. It has been conjectured that they achieve the same amortized time bounds as Fibonacci heaps, namely, O(log n) time for delete and delete_min and O(1) for all other operations, where n is the size of the priority queue at the time of the operation. We provide empirical evidence that supports this conjecture. The most promising algorithm in our simulations is a new variant of the twopass method, called auxiliary twopass. We prove that, assuming no decrease_key operations are performed, it achieves the same amortized time bounds as Fibonacci heaps.
The quest for efficiency in computational methods yields not only fast algorithms, but also insights that lead to elegant, simple, and general problem-solving methods.
An interview with the 1986 A. M. Turing Award recipients—John E. Hopcroft and Robert E. Tarjan
In the following interview, which took place at the 1986 Fall Joint Computer Conference in Dallas, Texas, John Hopcroft and Robert Tarjan discuss their collaboration and its influence on their separate research today. They also comment on supercomputing and parallelism, particularly with regard to statements by FJCC Keynote speakers Kenneth Wilson, Nobel laureate and director of Cornell University's Supercomputer Center, and C. Gordon Bell, chief architect on the team that designed DEC's VAX and now with the National Science Foundation. Finally the Turing Award winners air their views on the direction of computer science as a whole and on funding and the Strategic Defense Initiative.
The ACM SIGOPS Workshop on Accommodating Heterogeneity was conducted in December 1985 in Eastbound, Wash., as a forum for an international group of fifty researchers to discuss the technical issues surrounding heterogeneous computing environments.
Computer system reliability and nuclear war
Given the devastating consequences of nuclear war, it is appropriate to look at current and planned uses of computers in nuclear weapons command and control systems, and to examine whether these systems can fulfill their intended roles.
An improved parallel thinning algorithm
An iterative thinning algorithm reduces a two-dimensional pattern of strokes to its skeleton by removing layers of edge elements until each stroke has unit thickness. A parallel solution requires the independent calculation of new values for each iteration, using a window of nearest neighbors for each element. The traditional need for at least two subiterations can be avoided by modifying the window to permit the availability of intermediate calculations. Timings on an ICL DAP (an array processor) indicate an improvement of over 40 percent. Additional refinements are suggested to reduce noise in the final skeleton.
COBOL on a PC: a new perspective on a language and its performance
A comparison of Cobol performance on the PC AT Enhanced versus an IBM 370 mainframe suggests that high-quality PC compiler implementations—combined with the new language features of the Cobol 85 Standard—are improving the PC environment for Cobol to the point where serious applications can now be developed and debugged on the PC, either to be run on the PC itself, or for eventual uploading to a mainframe.
MATCH—a new high-level relational operator for pattern matching
Pattern matching is a common and fundamental operation of many applications, such as expert systems (ES). With continued growth the knowledge bases of such systems will need database management systems (DBMS) support. Providing this support will require extending DBMS to meet the needs of these systems. We have developed an operator that extends the relational data model to do pattern matching with very complex stored patterns.
Beyond the chalkboard: computer support for collaboration and problem solving in meetings
Although individual use of computers is fairly widespread, in meetings we tend to leave them behind. At Xerox PARC, an experimental meeting room called the Colab has been created to study computer support of collaborative problem solving in face-to-face meetings. The long-term goal is to understand how to build computer tools to make meetings more effective.
A relational information resource dictionary system
A relational implementation of IRDS using SQL demonstrates how the flexibility of the relational environment enhances the extensibility of the IRDS while at the same time providing more powerful dictionary capabilities than are typically found in relational systems.
Interface design issues for advice-giving expert systems
Advice giving could become the first successful domain for intelligent interfaces.
Contention is no obstacle to shared-memory multiprocessing
Contention in large-scale shared-memory systems is less of a concern than generally believed. Through careful engineering of a parallel system, the effects of contention can be controlled.
The intensive use of memory to recall specific episodes from the past—rather than rules—should be the foundation of machine reasoning.
Parallel free-text search on the connection machine system
A new implementation of free-text search using a new parallel computer—the Connection Machine®—makes possible the application of exhaustive methods not previously feasible for large databases.
Advanced compiler optimizations for supercomputers
Compilers for vector or multiprocessor computers must have certain optimization features to successfully generate parallel code.
Parallel computers with tens of thousands of processors are typically programmed in a data parallel style, as opposed to the control parallel style used in multiprocessing. The success of data parallel algorithms—even on problems that at first glance seem inherently serial—suggests that this style of programming has much wider applicability than was previously thought.
Schematic pseudocode for program constructs and its computer automation by SCHEMACODE
To achieve program control flow representation that is relatively independent of any given programming language, schematic pseudocode (SPC) uses a perceptual notation system composed of schemata whose syntax rules are described by a grammar. Source code documentation is supported by operational comments, and translation into a target procedural language is fully automatic.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More