کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
527453 869325 2007 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Analysis of the rubberband algorithm
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر چشم انداز کامپیوتر و تشخیص الگو
پیش نمایش صفحه اول مقاله
Analysis of the rubberband algorithm
چکیده انگلیسی

We consider simple cube-curves in the orthogonal 3D grid of cells. The union of all cells contained in such a curve (also called the tube of this curve) is a polyhedrally bounded set. The curve’s length is defined to be that of the minimum-length polygonal curve (MLP) contained and complete in the tube of the curve. Only one general algorithm, called rubberband algorithm, was known for the approximative calculation of such an MLP so far.An open problem in [R. Klette and A. Rosenfeld. Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco, 2004.] is related to the design of algorithms for the calculation of the MLP of a simple cube-curve: Is there a simple cube-curve such that none of the nodes of its MLP is a grid vertex? This paper constructs an example of such a simple cube-curve, and we also characterize the class of all of such cube-curves. This study leads to a correction in Option 3 of the rubberband algorithm (by adding one missing test).We also prove that the rubberband algorithm has linear time complexity O(m)O(m) where m is the number of critical edges of a given simple cube-curve, which solves another open problem in the context of this algorithm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Image and Vision Computing - Volume 25, Issue 10, 1 October 2007, Pages 1588–1598
نویسندگان
, ,