Sampling Shape Contours Using Optimization over a Geometric Graph

Kazuya OSE  Kazunori IWATA  Nobuo SUEMATSU  

IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.12   pp.2547-2556
Publication Date: 2019/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7353
Type of Manuscript: PAPER
Category: Pattern Recognition
contour sampling,  shape representation,  shape retrieval,  geometric graph,  

Full Text: PDF(979.7KB)>>
Buy this Article

Consider selecting points on a contour in the x-y plane. In shape analysis, this is frequently referred to as contour sampling. It is important to select the points such that they effectively represent the shape of the contour. Generally, the stroke order and number of strokes are informative for that purpose. Several effective methods exist for sampling contours drawn with a certain stroke order and number of strokes, such as the English alphabet or Arabic figures. However, many contours entail an uncertain stroke order and number of strokes, such as pictures of symbols, and little research has focused on methods for sampling such contours. This is because selecting the points in this case typically requires a large computational cost to check all the possible choices. In this paper, we present a sampling method that is useful regardless of whether the contours are drawn with a certain stroke order and number of strokes or not. Our sampling method thereby expands the application possibilities of contour processing. We formulate contour sampling as a discrete optimization problem that can be solved using a type of direct search. Based on a geometric graph whose vertices are the points and whose edges form rectangles, we construct an effective objective function for the problem. Using different shape datasets, we demonstrate that our sampling method is effective with respect to shape representation and retrieval.