輪郭線追跡による画像の切り抜き

Abstract

An efficient edge following algorithm is presented. It is a one-pass sequential scanning procedure. Given two separate points near a region boundary of a digital gray scale picture, it extracts a path from one point to the other in such a way that the average of the evaluation value (mainly the edge strength) of the points along the path becomes 'near' maximum. A sequence of points outlining a region of a picture provided, it is possible to extract the entire boundary curve of the region by repeatedly using the algorithm. Generally, there are two ways, in graph search, to get an optimum path which connects the two point. One is to find a path which gives the minimum cost. The other is to find that of the maximum merit. The former tends to extract a shorter path, because the shorter the path, the smaller the cost gets. The latter inclined to have a longer path. In this regard, the averaging process of the cost or the merit along the path is introduced for normalization which enables to compare a long path with a short one on a common base. Divisions, however, are required to do it. A large number of divisions may sacrifice the processing speed. A method is suggested to avoid them. It is to add a penalty (a negative value) to the sum of the merit along the path whenever the path gets a unit longer while maximizing the sum. A number of experiments are done with good results.