一种快速的扫描铅笔稿图细化算法

An Efficient Algorithm of Thinning Scanned Pencil Drawings

二维动画计算机辅助制作系统中 ,在对扫描铅笔稿图进行矢量化后 ,可以大大提高描线上色的效率 ,并且能够提取线条和闭包 ,以便于自动上色和中间帧生成等更高级功能的实现 .扫描铅笔稿图的细化是矢量化的第一步 ,在比较了大量现存的图象细化算法后 ,提出了一种改进的非迭代线跟踪细化算法 .该算法效率较高 ,只需对图象进行一遍扫描加两遍轮廓跟踪 ,就能较好地满足二维动画计算机辅助制作系统对细化效率的要求 .该文还对算法的时间复杂性进行了详尽分析 ,并提出对于两类图象噪声和冗余分支的消除方法 .

In computer aided 2D cartoon producing systems, the vectorization of scanned pencil drawings can greatly enhance the efficiency of inking and painting, retrieve lines and closures contained in the drawings and therefore lay the basis for implementation of more advanced functions such as autocoloring, inbetweening and so on. Thinning of scanned pencil drawings is the first step of the vectorization process. Having investigated and compared a lot of thinning algorithms, an improved noniterative thinning algorithm based on the idea of line following is presented. The improved algorithm is very efficient, which, requiring only one pass of image scanning and two passes of contour tracing, meets the high efficiency standard in computer aided 2D cartoon producing systems. Time complexity of the algorithm is analyzed in detail, and the method to reduce two kinds of image noises and to delete redundant branches after thinning are given.