A survey of efficient Hough transform methods <s> Parallel architectures. <s> Much of the progress in the fields constituting cognitive science has been based upon the use of explicit information processing models, almost exclusively patterned after conventional serial computers. An extension of these ideas to massively parallel, connectionist models appears to offer a number of advantages. After a preliminary discussion, this paper introduces a general connectionist model and considers how it might be used in cognitive science. Among the issues addressed are: stability and noise-sensitivity, distributed decision-making, time and sequence problems, and the representation of complex concepts. <s> BIB001 </s> A survey of efficient Hough transform methods <s> Parallel architectures. <s> The recently developed Fast Hough Transform algorithm [3,4] alleviated the traditional exponential growth in computing complexity and storage of the Hough transform at a factor of several orders of magnitude thus enlightened the possibility of serving as a fundamental algorithm for multidimensional signal processing. This paper investigates its implementation on SIMD architectures consisting of a large number of identical bit-serial processing elements. <s> BIB002
One of the main characteristics of the HT is that it consists of a series of fairly simple calculations carried out independently on every feature in an image. In this section we will review ideas and attempts to capture this inherent paralellism on specialised parallel architectures. Several authors have investigated the implementation of the HT on currently available SIMD architectures. These usually consist of square arrays of simple processing elements, P.E.s, connected so that each can communicate with its 4 or 8 neighbours. All processors concurrently execute the same instructions on different items of data. Most often each P.E. has only a single bit arithmetic logic unit, several registers and a few kilobits of on chip RAM. The mapping of the HT onto these architectures has been considered by both Silberberg  and Li BIB002 . Silberberg considered distributing both the image and the accumulator arrays among all P.E.s i.e. each P.E. is assigned both an image feature and a cell of parameter space. However this necessitated a great deal of data transfers between P.E.s in order to pass votes to the correct P.E. for accumulation. Over 98% of the time of the algorithm was taken in shifting data around the processing array and the end result was that the use of 8000 simple P.E.s led to a speedup factor of only 7 relative to a standard implementaion on a VAX 11/785. This poor result illustrates the care required in mapping algorithms onto parallel machines. Li BIB002 considered two schemes for running his Fasi Hough Transform, FHT, on a SIMD architecture. In the first scheme each P.E. is assigned an image feature and the coordinates of a parameter cell are broadcast simultaneouly to every P.E. by a central controller. Each P.E. decides whether the hypersurface generated by its image feature intersects the cell and if it does it sends a vote back to the controller. The votes from each P.E. can be summed by the central controller and stored for later analyis. A second scheme is to assign each P.E. a volume of parameter space and broadcast the image features. The choice of method depends on the number of available P.E.'s, the number of image features and the number of parameter cells. For the standard HT the number of parameter cells increases exponentially with dimensionality of the problem and therefore the first alternative is likely to be the most feasible. Simplistically one might argue that the use of n P.E.s, one for each of n image features, should speed up the HT by a factor of O(n). However votes have to be routed to their correct places in the accumulator and on a simple square 2D mesh with only local shifting operations this requires O(^/n) steps. As Silberberg found out this can be a significant overhead and even the dominant time factor. However if the array is augmented by a tree based voting network this can be reduced to O(log(n)) and the expected gains in efficiency should again approach O(n). Little et al  describe a possible implementation of the HT on an architecture called the Connection Machine. This is similar to the previously mentioned SIMD architectures but as well as P.E.s communicating with near neighbours there is a hardware router which implements rapid communication between any pair of processors. The architecture is based on a 12 dimensional hypercube i.e. every processor can be reached from any other by traversing at most 12 edges of the cube. Unfortunately this paper concentrates on aspects of programming and addressing and does not give any figures on the efficiency gains in using this parallel implementation. Olsen et al  discuss the operation of the HT on a MIMD computer architecture. They use a commercially available system called the BBN Butterfly Parallel Processor™. This consists of 256 processing nodes connected by a switching network. Each processor is a microprocessor from the Motorola 68000 series and each node has a substantial amount of local memory i.e. 1 megabyte. Memory is shared in the sense that a switching network allows any processor to address the local memory of any other processor. Olsen et al implemented two different line finding HTs using different parameterisations for lines. The versions differed in whether the image was partitioned among the processors with the parameter cells accessed from common memory or vice versa. They consider whether the algorithm is computation or communication resource bound and their results indicate that it is possible to achieve processor utilisation factors in the region of 80% i.e. if 100 processors are used they will give a speedup of 80 times relative to using a single processor. The HT has attracted attention from researchers interested in human vision as it is a prime example of the ideas of the connectionist school of artificial intelligence  BIB001 . The unifying principle of this approach to intelligence is that low and medium level vision tasks are done by massively parallel, cooperative computations on large networks of simple neuron like units. Low level pixel based properties, like edge or gray level estimates, can be represented by nodes in a feature network which is spatially indexed to the image while parameter values associated with higher level image entities, such as straight lines, can be represented by nodes in a seperate parameter network. Each node records a measure of confidence of the occurrence of its feature or parameter value and direct connections between the two networks define possible ways in which nodes can influence these confidence values. Different connection patterns can be used to impose different image space to parameter space mappings i.e. connections can be established so that when many low level units which lie on a straight line have high confidence then the higher level unit describing the parameters of this line will acquire a large confidence value. The major characteristic of this type of implementation is the huge number of feature and parameter units needed and the very large number of connections which are required between them.