International Journal of Pattern Recognition and Artificial Intelligence

In this paper, we show the interest of the 3D discrete surface notion for the extraction of object contours. We introduce some notions related to surfaces of 18-and 26-connected objects in 3D discrete images, and a new sequential algorithm to extract the surface and contours of 26-connected objects. Then, we present a PRAM related algorithm to construct the successor function of the surface graph. The complexity of the algorithm is O(log N) for an N×N×N image, with N³ processors.

In this paper, a generic approach for the analysis and design of parallel thinning algorithms is presented. The procedures for designing 4-subcycle/iteration, 2-subcycle/iteration, and 1-subcycle/iteration thinning algorithms are developed. The experimental results show that these thinning algorithms designed by proposed approach preserve image connectivity, produce thinner results, and obtain faster speed than many existing key thinning algorithms. As an example, a 1-subcycle/iteration algorithm and its experimental results were illustrated, which is in general about two times faster than others in the literature.

In a coordinate grammar, the rewriting rules replace sets of symbols having given coordinates by sets of symbols whose coordinates are given functions of the coordinates of the original symbols. Usually, at each step of a derivation, only one rule is applied and only one instance of its left hand side is rewritten. This type is referred to sequential grammars. As a counterpart of this grammar, parallel coordinate grammars are defined as generalized parallel isometric grammars. In the parallel grammars, the rewriting rule are used in parallel in a derivation application. The paper discusses some properties of parallel coordinate grammars and examines a relationship between the sequential coordinate grammars and parallel ones.

The emptiness problem for non-overlapping Basic puzzle grammars is shown to be decidable. An alternate proof of the decidability of the non-overlapping feature for basic puzzle grammars is given. Hierarchy among the various classes of puzzle languages is also established.

Recently, related to the open problem of whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, the inkdot Turing machine was introduced. An inkdot machine is a conventional Turing machine capable of dropping an inkdot on a given input tape for a landmark, but not to pick it up nor further erase it.

In this paper, we introduce a finite state version of the inkdot machine as a weak recognizer of the properties of digital pictures, rather than a Turing machine supplied with a one-dimensional working tape. We first investigate the sufficient spaces of three-way Turing machines to simulate two-dimensional inkdot finite automaton, as preliminary results. Next, we investigate the basic properties of two-dimensional inkdot automaton, i.e. the hierarchy based on the number of inkdots and the relationship of two-dimensional inkdot automata to other conventional two-dimensional automata. Finally, we investigate the recognizability of connected pictures of two-dimensional inkdot finite machines.

This paper introduces a cooperating system of three-way, two-dimensional finite automata (CS-TR2-FA) which is a restricted version of a cooperating system of four- way, two-dimensional finite automata (CS-2-FA), and mainly investigates several fundamental properties of this system as a two-dimensional language acceptor whose input tapes are restricted to square ones. We show that

(1) CS-TR2-FA’s are equivalent in accepting power to three-way, two-dimensional simple multihead finite automata,

(2) CS-2-FA’s are more powerful than CS-TR2-FA’s,

(3) £[CS-TR2-DFA(k)^S] ⊊ £[CS-TR2-NFA(k)^S],

(4) ⋃_1≤k<∞ £[CS-TR2-DFA(k)^S] ⊊ ⋃_1≤k<∞ £[CS-TR2-NFA(k)^S], and

(5) £[CS-TR2-DFA(k)^S] (£[CS-TR2-NFA(k)^S]) ⊊ £[CS-TR2-DFA(k+1)^S] (£[CS-TR2-NFA(k+1)^S]),

where £[CS-TR2-DFA(k)^S] (£[CS-TR2-NFA(k)^S]) denotes the class of sets of square input tapes accepted by CS-TR2-FA’s which consist of k deterministic (non-deterministic) finite automata.

An (m, n)-simple 1 in a binary image I has the property that its deletion “preserves topology” when m-adjacency is used on the 1’s and n-adjacency on the 0’s of I. This paper presents new, easily visualized, necessary and sufficient conditions for a 1 in I to be (m, n)-simple, for (m, n)=(26, 6), (18, 6), (6, 26) or (6, 18) when I is a 3-d image and (m, n)=(8, 4) or (4, 8) when I is a 2-d image.

Systematic and fairly general methods of verifying that a given parallel thinning algorithm always preserves topology are described, for the cases where 8-/26-adjacency is used on the 1’s and 4-/6-adjacency on the 0’s, or vice versa. The verification methods for 2-d algorithms are mainly due to Ronse and Hall; the methods for 3-d algorithms were found by Ma and Kong. New proofs are given of the correctness of these verification methods, using the characterizations of simple 1’s presented in this paper.