A morphological shape decomposition algorithm was recently introduced that allows a shape to be represented as a collection of modestly overlapped disk components. In this paper, we present a shape matching algorithm that is based on this decomposition algorithm. The matching algorithm matches two shapes by matching their disk components. A local descriptor that contains both geometric and structural information is built for each disk component. Such descriptors are used to determine the matching of disk components from two shapes. The overall similarity score is established by combining scores from matching individual disk components. The experiments show that the algorithm is tolerant to scale and rotation changes. An advantage of the algorithm is that the matching can be done at different levels of details.

One problem with several leading morphological shape representation algorithms is the heavy overlapping among the representative disks of the same size. A shape component formed by grouping connected disk centers may use many heavily overlapping disks to represent a simple shape part. Sometimes, these representative disks form complicated structures. A generalized skeleton transform was recently introduced which allows a shape to be represented as a collection of modestly overlapped octagonal shape parts. However, the generalized skeleton transform needs to be applied many times. Furthermore, an octagonal component is not easily matched up with another octagonal component. In this paper, we describe a octagon-fitting algorithm which identifies a special maximal octagon for each image point in a given shape. This transform leads to the development of two new shape decomposition algorithms. These algorithms are more efficient to implement; the octagon-fitting algorithm only needs to be applied once. The components generated are better characterized mathematically. The disk components used in the second decomposition algorithm are more primitive than octagons and easily matched up with other disk components from another shape. The experiments show that the new decomposition algorithms produce as efficient representations as the old algorithm for both exact and approximate cases. A simple shape-matching algorithm using disk components is also demonstrated.

A generalized skeleton transform was recently introduced which allows a shape to be represented as a collection of modestly overlapped octagonal shape parts. However, the generalized skeleton transform needs to be applied many times. Furthermore, an octagonal component is not easily matched up with another octagonal component from a different shape. In this paper, we describe a new "distance" transform which identifies a special maximal octagon for each image point in a given shape. This transform leads to the development of a new shape decomposition algorithm. This algorithm is more efficient to implement; the "distance" transform only needs to be applied once. The disk components used in the new algorithm are more primitive than octagons and easily matched up with other disk components from another shape. The experiments show that the new decomposition algorithm produces as efficient representations as the old algorithm.

In this paper, we introduce a generalized morphological skeleton transform that uses eight structuring elements to generate skeleton subsets. The number of representative points needed to represent a given shape is significantly lower than in the standard skeleton transform. A collection of shape components needed to build a structural representation is easily selected from the shape elements generated in the generalized skeleton transform. Each shape component covers a significant area of the given shape and severe overlapping is avoided. The given shape can also be accurately approximated using a small number of shape components.

A common problem shared by several leading morphological shape representation algorithms is that there is much overlapping among the representative disks of the same size. A shape component represented by a group of connected disk centers sometimes uses many heavily overlapping representative disks to represent a relatively simple shape part. A shape component may also contain a large number of representative disks that form a complicated structure. We introduce a generalized discrete morphological skeleton transform that uses eight structuring elements to generate skeleton subsets so that no two skeletal points from the same skeleton subset are adjacent to each other. Each skeletal point represents a shape part that is in general an octagon with four pairs of parallel opposing sides. The number of representative points needed to represent a given shape is significantly lower than that in the standard skeleton transform. A collection of shape components needed to build a structural representation is easily derived from the generalized skeleton transform. Each shape component covers a significant area of the given shape and severe overlapping is avoided. The given shape can also be accurately approximated using a small number of shape components.

In this paper, we propose a new way of generalizing three basic morphological shape representation algorithms to improve representational efficiency. In all three basic algorithms, a fixed overlapping policy is used to control the overlapping relationships between representative disks of different sizes. In our new algorithm, different overlapping policies are used to generate shape components that have different overlapping relationships among themselves. The overlapping policy is selected dynamically according to local shape features. Experiments show that compared to the three basic algorithms, our algorithm produces more efficient representations with lower numbers of representative points.

In many morphological shape decomposition algorithms, either a shape can only be decomposed into shape components of extremely simple forms or a time consuming search process is employed to determine a decomposition. In this paper, we present a morphological shape decomposition algorithm that decomposes a two-dimensional (2-D) binary shape into a collection of convex polygonal components. A single convex polygonal approximation for a given image is first identified. This first component is determined incrementally by selecting a sequence of basic shape primitives. These shape primitives are chosen based on shape information extracted from the given shape at different scale levels. Additional shape components are identified recursively from the difference image between the given image and the first component. Simple operations are used to repair certain concavities caused by the set difference operation. The resulting hierarchical structure provides descriptions for the given shape at different detail levels. The experiments show that the decomposition results produced by the algorithm seem to be in good agreement with the natural structures of the given shapes. The computational cost of the algorithm is significantly lower than that of an earlier search-based convex decomposition algorithm. Compared to nonconvex decomposition algorithms, our algorithm allows accurate approximations for the given shapes at low coding costs.

This paper proposes a new morphological shape representation algorithm, in which a two-dimensional (2-D) binary shape is represented as a union of certain disks contained in the given shape. The representative disks of different sizes may overlap. But excessive overlapping between them is avoided. The algorithm combines the advantages of the morphological skeleton transform (MST) and the morphological shape decomposition (MSD). The representative disks have simple and well-defined mathematical characterizations. The algorithm is simple and efficient to implement. The experimental results show that the number of representative disks used by our algorithm is significant lower than that used by the MSD. The overlapping level between the representative disks is much lower than that of the MST. A simple procedure can be used to combine the representative disks into more meaningful shape components. These shape components seem to correspond better to the natural shape parts than those generated by the MSD. It is also possible to build a good approximation for a given shape using only a small number of major components.

The morphological skeleton transform is a shape representation scheme that decomposes a shape into a union of all minimal homothetics of a structuring element contained in the shape. In this paper, we develop an algorithm that generalizes the skeleton transform by allowing many different rectangles of different sizes and shapes to be used as shape components. The shape components in our representations still have simple and well defined mathematical characterizations. The representation is uniquely defined and the algorithm is simple and efficient to implement. Experiments show that our representations use significantly less shape components than those produced by the regular skeleton transform.

This paper proposes a new morphological shape representation algorithm that does not require searching. A theoretical analysis as well as experimental results are presented to compare the algorithm with two leading morphological shape representation schemes: the morphological skeleton transform (MST) and the morphological shape decomposition (MSD). Our algorithm combines the advantages of the MST and MSD. In our scheme, a binary shape is decomposed into a union of disks of different sizes. The number of disks used is close to that by the MST and the reconstruction cost is close to that by the MSD.

Presents a morphological shape segmentation algorithm that decomposes a 2D binary shape into a collection of restricted convex polygons. The algorithm is simple and the decomposition is always unique. The components produced have well-defined mathematical characterizations and they seem to be in good agreement with the nature structures of the given shape.>

A discussion is presented of the decomposition of convex polygon-shaped structuring elements into neighborhood subsets. Such decompositions will lead to efficient implementation of corresponding morphological operations on neighborhood-processing-based parallel image computers. It is proved that all convex polygons are decomposable. Efficient decomposition algorithms are developed for different machine structures. An O(1) time algorithm, with respect to the image size, is developed for the four-neighbor-connected mesh machines; a linear time algorithm for determining the optimal decomposition is provided for the machines that can quickly perform 3*3 morphological operations.>

A novel morphological shape decomposition algorithm which is based on the skeleton transform is presented. The input to the algorithm is the morphological skeleton of a binary shape. Using simple morphological operations, this algorithm decomposes a binary shape into shape segments that correspond to maximal skeleton-induced subregions of the original shape containing no necks. A skeleton-induced decomposition scheme for 2-D shapes is defined. Many extensions to the basic algorithm are also possible. The shape segments produced can be used to construct structural shape descriptions or for other shape analysis purposes.>

Neighborhood-connected array processors can implement Minkowski addition and Minkowski subtraction operations with structuring elements larger than the neighborhood size by breaking the operation into a sequence of successive neighborhood operations. The author provides a complete solution to the problem of decomposing convex polygons into subsets of the 3*3 neighborhood set. With the help of the Freeman chain code notation, it is proved that all convex polygons have neighborhood decompositions. Based on this result, an efficient algorithm is developed which can find an optimal decomposition for any convex polygon. The decomposition produced by the algorithm can be used to determine the most efficient implementation of a morphological operation with convex polygonal structuring elements as a sequence of successive neighborhood operations. Therefore, the algorithm is applicable to neighborhood-connected array processors, or any machine structure that can quickly perform 3*3 neighborhood operations.>