International Journal of Pattern Recognition and Artificial Intelligence

The main contribution of this work is to show that a number of digital geometry problems can be solved elegantly on meshes with multiple broadcasting by using a time-optimal solution to the leftmost one problem as a basic subroutine. Consider a binary image pretiled onto a mesh with multiple broadcasting of size one pixel per processor. Our first contribution is to prove an Ω(n^1/6) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically, the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n^1/6) time algorithms for these problems. As previously mentioned, an interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.

This paper discusses several data allocation strategies used for the parallel implementation of basic imaging operators. It shows that depending on the operator (sequential or parallel, with regular or irregular execution time), the image data must be partitioned in very different manners: The square sub-domains are best adapted for minimizing the communication volume, but rectangles can perform better when we take into account the time for constructing messages. Block allocations are well adapted for inherently parallel operators since they minimize interprocessor interactions, but in the case of recursive operators, they lead to nearly sequential executions. In this framework, we show the usefulness of block-cyclic allocations. Finally, we illustrate the fact that allocating the same amount of image data to each processor can lead to severe load imbalance in the case of some operators with data-dependant execution times.

A new very efficient linear algorithm for the segmentation of 8-connected digital curves is given. The simplicity comes from a definition of digital lines using a linear double diophantine inequality. A complete Pascal source code is given.

The multiple-query nearest-neighbor (MQNN) problem is stated as follows: given a set S of n points in plane and a set Q of m(1≤m≤n) query points, determine for every point in Q its closest neighbor in S. Besides the pure theoretical interest, this problem has many practical applications in various areas such as: computer graphics, pattern recognition and image processing. First, this paper proposes a new time-optimal algorithm to solve the all nearest-neighbor (ANN) problem in time on a mesh-connected computer of size . Next, using this result in conjunction with the generalized multiple search (GMS) paradigm of Bokka et al.^3,5 we devise a time-optimal algorithm that solves the MQNN problem in time on a mesh with multiple broadcasting (MMB) of size .

The direct binary hypercube interconnection network has been very popular for the design of parallel computers, because it provides a low diameter and can emulate efficiently the majority of the topologies frequently employed in the development of algorithms. The last fifteen years have seen major efforts to develop image analysis algorithms for hypercube-based parallel computers. The results of these efforts have culminated in a large number of publications included in prestigious scholarly journals and conference proceedings. Nevertheless, the aforementioned powerful properties of the hypercube come at the cost of high VLSI complexity due to the increase in the number of communication ports and channels per PE (processing element) with an increase in the total number of PE’s. The high VLSI complexity of hypercube systems is undoubtedly their dominant drawback; it results in the construction of systems that contain either a large number of primitive PE’s or a small number of powerful PE’s. Therefore, low-dimensional k-ary n-cubes with lower VSLI complexity have recently drawn the attention of many designers of parallel computers. Alternative solutions reduce the hypercube’s VLSI complexity without jeopardizing its performance. Such an effort by Ziavras has resulted in the introduction of reduced hypercubes (RH’s). Taking advantage of existing high-performance routing techniques, such as wormhole routing, an RH is obtained by a uniform reduction in the number of edges for each hypercube node. An RH can also be viewed as several connected copies of the well-known cube-connected-cycles network. The objective here is to prove that parallel computers comprising RH interconnection networks are definitely good choices for all levels of image analysis. Since the exact requirements of high-level image analysis are difficult to identify, but it is believed that versatile interconnection networks, such as the hypercube, are suitable for relevant tasks, we investigate the problem of emulating hypercubes on RH’s. The ring (or linear array), the torus (or mesh), and the binary tree are the most frequently used topologies for the development of algorithms in low-level and intermediate-level image analysis. Thus, to prove the viability of the RH for the two lower levels of image analysis, we introduce techniques for embedding the aforementioned three topologies into RH’s. The results prove the suitability of RH’s for all levels of image analysis.

Our goal is to implement skeletonization algorithms on distribution memory mechines. This implementation is not trivial, because we cannot apply locally thinning operators based on 26-neighborhood, sequentially or simultaneously on all the points of the image. After summarizing the problem, we describe two methodologies to implement these algorithms on MIMD machines, one based on the decomposition of the thinning operator into sub-operators, and the other based on the decomposition of the study domain (image) into sub-domains.