A shape matching technique based on the straight line Hough transform (SLHT) is presented. In the theta - rho space, the transform can be expressed as the sum of the translation term and the intrinsic term. This formulation allows the translation, rotation, and intrinsic parameters of the curve to be easily decoupled. A shape signature, called the scalable translation invariant rotation-to-shifting (STIRS) signature, is obtained from the theta - rho space by computing the distances between pairs of points having the same theta value. This signature is invariant to translation and can be easily normalized, and rotation in the image space corresponds to circular shifting of the signature. Matching two signatures only amounts to computing a 1D correlation. The height and location of a peak (if it exists) indicate the similarity and orientation of the test object with respect to the reference object. The location of the test object is obtained, once the orientation is known, by an inverse transform (voting) from the theta - rho space to the x-y plane.>

A novel approach for the detection of parametric curves using the straight-line Hough transform is presented. The transform function of a curve can be expressed as the sum of two terms, namely, the intrinsic term and the translation term. This representation allows a natural decomposition of the high-dimensional parameter space into three subspaces: the intrinsic curve parameters, translation, and rotation. By eliminating either the translation term or the intrinsic term, one can easily determine the parameters of the remaining term. The complexity of this method depends mainly on the angular resolution, which is relatively independent of the arc length of the curve. The computational complexity of this approach compares favorably with that of other approaches based on the Hough transform.>

Presents a critical study of two approaches, the classical RC-cut approach and H.T. Kung and M.S. Lam's (Proc. 1984 MIT Conf. Advanced Res. VLSI p.74-83, 1984) RCS-cut approach, for reconfiguring faulty systolic arrays. The amount of cell (processing element) redundancy needed to ensure successful reconfiguration into an n*n array is considered. It is shown that no polynomial bounded redundancy is sufficient for the classical approach, whereas O(n/sup 2/log n) redundancy is sufficient for the Kung and Lams approach. The number of faulty cells that can be tolerated in a given array regardless of their locations is characterized and derived. It is shown that, for both approaches, in almost all cases a square array has better fault tolerance than a rectangular array having the same number of cells. A minimal fault pattern in a 2n*2n array with 3n+1 faults that is not reconfigurable into an n*n array using either of the two approaches is established.>

The problem of restructuring systolic arrays with faulty cells is considered. An approach to derive the required data-flow paths and computational sites is proposed. The data skewing requirement, which must be satisfied to find an input schedule, is also discussed. Algorithms to restructure systolic arrays for three different architectures of processing elements are presented. A systematic method to retime the restructured array using additional programmable delays so that the retimed array satisfies the data skewing requirements is developed.>

The authors present two O(n/sup 2/) planarization algorithms, PLANARIZE and MAXIMAL-PLANARIZE. These algorithms are based on A. Lempel, S. Even, and I. Cederbaum's (1967) planarity testing algorithm and its implementation using PQ-trees. Algorithm PLANARIZE is for the construction of a spanning planar subgraph of an n-vertex nonplanar graph. The algorithm proceeds by embedding one vertex at a time and, at each step, adds the maximum number of edges possible without creating nonplanarity of the resultant graph. Given a biconnected spanning planar subgraph G/sub p/ of a nonplanar graph G, the MAXIMAL-PLANARIZE algorithm constructs a maximal planar subgraph of G which contains G/sub p/. This latter algorithm can also be used to planarize maximally a biconnected planar graph.>