Search

The basic shape features of an object in a binary image, i.e., the area, perimeter, circularity, and centroid, are important for image analysis and pattern recognition. In conventional algorithms, to calculate the basic shape features of objects in a binary image, it is usually necessary to first perform connected-component labeling to generate a labeled image (intermediate image), in which every image object is assigned a unique label so that it may be distinguished. Using the labeled image, the basic shape features of the object corresponding to each label can then be calculated. When a two-scan labeling algorithm is used, three scans are necessary. This paper proposes an efficient algorithm for calculating the shape features of objects in a binary image. Instead of a labeled image, our proposed algorithm calculates the basic shape features of objects using the image and the representative label table generated by the first scan of an efficient two-scan labeling algorithm. Thus, we can compute shape features using two scans. Experiments demonstrate that our proposed algorithm is much more efficient than conventional algorithms for calculating the basic shape features of objects in a binary image.

This paper proposes a fast algorithm for integrating connected-component labeling and Euler number computation. Based on graph theory, the Euler number of a binary image in the proposed algorithm is calculated by counting the occurrences of four patterns of the mask for processing foreground pixels in the first scan of a connected-component labeling process, where these four patterns can be found directly without any additional calculation; thus, connected-component labeling and Euler number computation can be integrated more efficiently. Moreover, when computing the Euler number, unlike other conventional algorithms, the proposed algorithm does not need to process background pixels. Experimental results demonstrate that the proposed algorithm is much more efficient than conventional algorithms either for calculating the Euler number alone or simultaneously calculating the Euler number and labeling connected components.

The shape features of objects (connected components) in binary images are very important for image analysis, pattern (object) recognition, and computer vision. Conventional algorithms for calculating the shape features of objects in binary images can only calculate the shape features of objects without holes. This paper presents an algorithm or calculating the shape features of objects in binary images with holes. Based on a contour-tracing-based connected-component labeling algorithm, our proposed algorithm can calculate the number of objects, the number of holes, the Euler number in a binary image, extract the contours of objects, and calculate the area, perimeter, circularity, centroid of each object. Our proposed algorithm is able to make a contribution to image analysis, pattern recognition, and computer vision.

It is known that the set of all redexes for a left-linear term rewriting system is recognizable by a tree automaton, which means that we can construct a tree automaton that accepts redexes. The present paper extends this result to Nipkow’s higher-order rewrite systems, in which every left-hand side is a linear fully-extended pattern. A naive extension of the first-order method causes the automata to have infinitely many states in order to distinguish bound variables in λ-terms, even if they are closed. To avoid this problem, it is natural to adopt de Bruijn notation, in which bound variables are represented as natural numbers (possibly finite symbols, such as 0, s(0), and s(s(0))). We propose a variant of de Bruijn notation in which only bound variables are represented as natural numbers because it is not necessary to represent free variables as natural numbers.

The present paper discusses a head-needed strategy and its decidable classes of higher-order rewrite systems (HRSs), which is an extension of the head-needed strategy of term rewriting systems (TRSs). We discuss strong sequential and NV-sequential classes having the following three properties, which are mandatory for practical use: (1) the strategy reducing a head-needed redex is head normalizing (2) whether a redex is head-needed is decidable, and (3) whether an HRS belongs to the class is decidable. The main difficulty in realizing (1) is caused by the β-reductions induced from the higher-order reductions. Since β-reduction changes the structure of higher-order terms, the definition of descendants for HRSs becomes complicated. In order to overcome this difficulty, we introduce a function, PV, to follow occurrences moved by β-reductions. We present a concrete definition of descendants for HRSs by using PV and then show property (1) for orthogonal systems. We also show properties (2) and (3) using tree automata techniques, a ground tree transducer (GTT), and recognizability of redexes.

This paper describes an extension of head-needed rewriting on term rewriting systems to higher-order rewrite systems. The main difficulty of this extension is caused by the ?-reductions induced from the higher-order reductions. In order to overcome this difficulty, we define a new descendant of higher-order rewrite systems. This paper shows the new definition of descendant, its properties and head normalization of head-needed rewriting on orthogonal higher-order rewrite systems.