Narrow Results

Assume that a black/white n×n image is stored one pixel per element of a vector of length n². We consider determining some characteristics of such images using the scan model of parallel computation. The scan model was introduced by G.E. Blelloch and is a single instruction multiple data (SIMD) vector model of computation. The primitive operations of the model work on vectors (one dimensional arrays) of values, with three types of primitive operations: Elementwise arithmetic and logical operations, permutation operations, and scan operations, a type of prefix computation (a scan operation takes a binary associative operator ⊗ and a vector [a₁,…, a_n] and returns the vector [a₁, a₁⊗a₂,…, a₁⊗a₂⊗…⊗a_n]). We show that many important characteristics of binary images can be determined in constant time on the scan model of parallel computation. These include the convex hull construction, diameter, width, smallest enclosing box, perimeter, area, detecting digital convexity, parallel and point visibility (determining for each pixel of the image the portion that is visible, i.e., not obstructed by any black pixel, in a given direction from infinity or from a given point, respectively) of an image, smallest, largest and Hausdorff distances between two images, linear separability of two images, and the recognition of digital lines, rectangles and arcs.

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.

There are several cases when tortuous continuous lines have to be discretized in order to measure length and other related quantities. In this methodological paper, we are going to demonstrate the importance of the proper sequencing (ranking) of the discrete points and call attention to some typical errors caused by improper sequencing. For demonstration, the fractal dimensions of an animal track with well-known original sequencing and for some mixed sequencing are estimated and the extent of errors is shown.

The two-dimensional hexagonal grid and the three-dimensional face-centered cubic grid can be described by intersecting ℤ³ and ℤ⁴ with (hyper)planes. Corresponding grids in higher dimensions are examined. Also, we explain the connection between a number of well-known three-dimensional grids by using this construction. The union of four hyperplanes (in a circular way) gives the bcc grid. Based on these connections, several types of neighborhood structures are introduced on these grids. These structures span from the most natural ones (crystal bonds, Voronoi neighbors) to infinite families. In this paper, we define path-based distance functions on the high-dimensional generalizations of the hexagonal grid.

A novel algorithm to detect the isothetic λ-connected components present in a binary image is proposed in this paper. The concept of isothetic λ-connected component (ILCC) is newly introduced in this paper, which is denned as the smallest isothetic polygon that contains a set S of λ-connected components (LCCs).* Two components are said to be λ-connected if an only if the distance^† between them does not exceed λ. Contrary to the existing algorithms that use labeling to detect the (1-)connected components, in our work, a combinatorial technique is used to find the LCCs, and hence ILCCs, which represent the underlying object(s) in an elegant way. Since a real-world object may possess disconnectedness, noisy information, etc., the existing algorithms on component labeling are liable to produce components that are larger in number than sought for. Whereas, in the proposed method, two or more components that are spatially not far off, would be reported in the same ILCC. Further, the derived set of ILCCs are representable in an efficient high level description, which would facilitate subsequent applications where the ILCCs are used. Experimental results including CPU time reinforce the elegance and efficacy of the proposed algorithm.

In this paper, we present a novel approach to measure the shape complexity of objects using the isothetic polygonal envelope. The novelty lies in the fact that to derive the shape complexity, neither the exact contour extraction nor a complete enumeration of the object is required. The complexity measure is derived by merging the consecutive concavity and convexity of the isothetic envelope in multiple tiers to capture the spatial complexity, normalized, in each step, by the polygon perimeter. Since we extract the isothetic polygon against an imposed background grid, it is robust to noise in the object. As it is inherently amenable to multiscale approach, by varying the grid size, the analysis of the complexity of the different objects is shown. We have used different arbitrary shapes in experimentation and the results conform to structural complexity of the objects.

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.