ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



ʸбʵķֶ*
 ɽ
ժҪͳʸбʽƽݵֶϵ㷨.ϵһϵƽݵ,һȺ˳.ȸʸбʵĶ,Ȼÿƽݵͳʸб,ݸʸбֵӽ,ݵָ,ϸγ߶,Ѹ߶β͵õƽݵķֶ.ʸбʰСͷϢ,ֵΪ44,ֵı仯Ƕڣ180㡫180㣩еı仯һһӦ,ǵĹϵкܺõԶ.ʹôͳбʽзֶ,бֵǶȵĹϵԶȲбȡֵʱ,ЩӰϵľ,㷨ʹ÷Χ.ʸбʿ˷,Ӷṩߵ,㷨.㷨ʱ临ӶΪ.
ؼʡȡ,ֶ,״,,Ե.
ͼšTP391
A Piecewise Linear Approximation Based on Vector Slope
WANG Ming-jiang TANG Pu-shan
Abstract A piecewise linear approximation based on vector slope is presented in this paper. Given a set of planar data points, generally, these points have sequence.The vector slope definition is introduced at first in this paper. The slope of every points in set G is computed. The points cluster in a group, where vector slope of these points are very near. Fitting every group to a line and linking these lines, a fitting curve can be attained. The vector slope defination has the message of size and direction, basic interval is (-44). The varing of vector slope in basic interval with angle(-180㡫180) is in one-to-one correspondence and the relation curve has good linearity. A piecewise linear approximation based on conventional slope has some problems that the slope value is infinite in some cases and the relation curve with angle has bad linearity. All these very effect the quality of fitting curve and confine the application range. This algorithm overcome these problems, so the authors can obtain a high quality fitting curve and the algorithm can be used in every graph. The time complexity is linear. 
Key wordsFeature extraction, piecewise linear approximation, shape analysis, contour analysis, edge detection.
ͼֽͼԶ뼰ʶPCBͼͼ֤Լɵ·,ͼһ㶼ˮƽֱ45߶ιɵ.Щ,Ҫȡͼʾתͼαʾ.һ㷽ͼıԵ,ϳͼ.ͼıԵ߶һϵȺ˳ͼɵ,Խϳͼξ൱ڽƽϵһϵȺ˳ݵϳߵ.ͼ,ԿһЩ򵥵ߣ߶ΡԲȣƱʾЩݵ.򵥵ľǷֶԱʾ,ݵֳɲ,߶ʾеÿһ.㷨Ƿֶεƽϵһϵݵ.
Tomex1,£2,Hakimi3ݺHiroshi4ݵ˶ֱ÷ֶԱʾƽеһϵе㷨.Tomex㷨ƽ߼߶.ļ㸴ӶԵ.ʱ,ĽʱҪӳɱ.Hakimi㷨Tomex㷨.»ͳģ͵㷨,˼Ƚݵз,ȻС˷ֱߵб,бʷұ仯Ϊϵ,ɴ˽ϲΪ,ټεС˷ֱ,߶.Ҫ,ڸϵ㴦ȡƽγɶ,Щ㹹һֶԵıƽ.
µ㷨˼,㷨ӶΪ.µ㷨ʵӦд漸:
(1) µ㷨ǽx1x2...xi...xN(xiΪݵx)֮ϵ.ڱպҪֶ,Ȼ.ͼ1,dy/dxΪ޵.
(2) µ㷨бֵdy/dxȡָ.ͨ(x,y)XĽǼΪ,ı仯׼ȷطӳߵı仯.Сʱ,dy/dxı仯,ӽ90ʱ,ǶȵĺС仯dy/dxĺܴ仯.бʱ仯Χ,㷨һǺܲ.
Ļʸбʵķֶ㷨,Чؽµ㷨ڵ.㷨˼,ͼ.

ͼ1
1 ʸбʵĶ
֪,ֱбûзϢ,ֱֻXύǵֵ.΢ֶΪdy/dx,ȡֵΧΪ(-ޡ+),ֱбǶȲһһӦ,ЩΪһЩ.ʸбʿֱбʵص,ǶֱбʶͲ.ʸбʵĶ.
οͼ2,ǽƽָ4,ÿжʸб:
1,ǶȷΧ(-45㡫45),dy/dx1,ʸбֵΪ(K*8+C*(dy/dx));
2,ǶȷΧ(45㡫135),dy/dx1,ʸбֵΪ(K*8+2+C*(dy/dx));
3,ǶȷΧ(135㡫225),dy/dx1,ʸбֵΪ(K*8+6+C*(dy/dx)).
4,ǶȷΧ(225㡫315),dy/dx1,ʸбֵΪ(K*8+6+C*(dy/dx)).
K,CΪϵ,Kȡֵ.C13ȡֵ1,24ȡֵ-1.ɽʸбʶдͳһʽ:
K*8+A+C*B,(1)
K,Cȡֵͬ.A14зֱȡ0246.B13Ϊdy/dx,24Ϊdy/dx.

ͼ2ʸбʶĻ
Ƕȣ-180㡫+180㣩䶨Ϊֵ,壨-4+4Ϊʸбʵֵ.
֪,ʸбֵVV+K*8ӦͬһǶֵ,VV+K*8ǵȼ۵,ڱ㷨пɽ滻.ֵʸбֵֵĽǶһһӦ,ֵʸбֵȷ,ӦֵĽǶȾȷ,ӶҲȷ.,dy/dx>1ʱ,ȡdy/dxֵʸбʵBֵ,Ӷȡֵ.ͼ3(a)ΪʸбǶȵĹϵ,ͼ3(b)ΪֱбǶȵĹϵ.ͼ3Կ,ʸбǶȣȣԶȱֱбʺõö,Ϊ㷨ļһԺ;ȵߴܴô.

(a)ʸбǶȵĹϵߡ(b)ֱбǶȵĹϵ
ͼ3ʸбʡֱбǶȹϵĶԱ
Ȼѧʽϱֱбʶ帴Щ,ʸбʵĴҪɼɵ,岢ûдӰ,ʸбֵΪ-4+4,ķ,,һҲ˳Ĵ. 
2 ƽݵֶϵ㷨
ʸбоƽݵķֶϵ.ƽݵ㶼ǰһ˳¼ʹ洢,еĸ,ԴǰͺȡһĿĵһ,С˷ݵʸбʵͳֵ,ȡǰǰݵλԼݵλ.ǰλúͺλÿݵֲչ,һʸбʵͳֵõǰʸбֵ.ÿбֵ,бֵӽĵۺϵһ,ϳ߶,߶͹ݵķֶԱʾ.Ǹ㷨.
1. ݵʸбֵ.ѡȡһM1=2m+1N,еÿһ,ȡǰm㡢m͵ǰһ򼯺,ΪSYi.
SYi={(xi+j,yi+j),-mjm}, 1iN,2
ȡʽֵ
fxx=(xi+j-xi)2; fyy=(yI+J-yi)2;
if fxxfyy
Biy=j*yi+jfxx
xb=xj(m+1); xe=xj(m+1);
if xexb
ʸ1,ʸбֵΪBiy.
else
ʸ3,ʸбֵΪ4+Biy.
else
Bix=j*xi+jfyy;
yb=yj(m+1); ye=yi(m+1);
if yeyb
ʸ2,ʸбֵΪ2-Bix.
else
ʸ4,ʸбֵΪ4-Bix.
ʸбʶ,ͨõʸбֵ88Ĳ,ֵֵ.ʵ,BiyΪʸбֵе13еBֵ,BixΪ24еBֵ.(xb,yb)Ϊǰģm1λ,(xe,ye)Ϊģm1λ.ݿʼͽβһЩγɵSYi,ĿСM1,ɲЩ.Bi뵽,õһµ.
S={(xi,yi,Bi), miN-m}.3
2. ԤȸƫE,ѡȡһֵT0,ʽ3ÿһڽγɵӼSi,Ӽÿһ㶼:
1 Bj-BiT, BjSi, ji;
2 Ӽеÿһ뵱ǰ.
ҵʽ3еӼ,ΪS1,ݵзָȥ,ȻʣмѰӼ,ΪS2,ݴзָȥ,ظϲ,ֱеݶָȥ.,Ǿͻһµļ
{S1,S2,S3,...}S1S2S3...=S; SiSj=, ji.4
3. 2еĸݶΰ·S˳½,ɾС3mݶ,ÿݶ,ͷβȥm.Ȼÿһݶζ(x,y)С˷.õֱ߰ÿֱཻ,ö,յӦֱֱ,ýΪ߶ε˵.˵Ͷ͹˷ֶ.
3 㷨
㷨Ļ˼ͨߵбֵı仯ݷָݶ,ÿС˷x,y,õ߶ξ͵õĽ.㷨˼,ʵ.ͼͼ㷨صһЩ.
ͼ4(a)ΪԾͼγɵĺ,ͼ4(b)Ϊκεʸб·SĹϵ.ӴԿ,㷨ӦڴͳбΪĳ.

(a)1(ͼ)(b)θߵʸб·SĹϵ(ABCDA)
ͼ4ͼε
ʹͼ5ʾĺ㷨ľ.ͼ5ĺˮƽΪ0.01ʵȽϱ㷨µ㷨2ݵľ.ȡN=200ݵ,Ըݵ(xi,yi),Ŧi,{i,0iN}ǶN(0,2)ֲ,иǰֱ߷.xi=xi+i*cos,yi=yi+i*sin.(xi,yi)Ϊźݵ;ΪxĽ.ȡ=0.01,ֱµ㷨ͱ㷨ȡ,1ʾ.ӱ1Կ,ĵ㷨֮µ㷨,кܴĸĽ.

ͼ52(ABCD)
1
ʵֵx00.382 61.306 42.306 43.230 23.610 8
y21.076 20.693 60.693 61.076 22
µ㷨=0.01
T=0.30,M=3x00.345 61.406 42.281 33.25. 63.614 1
y2.045 11.159 00.681 50.680 01.101 21.973 9
ĵ㷨=0.01T=0.2,M=3x00.379 11.317 92.291 43.225 02.614 1
y2.003 91.071 40.695 90.687 11.068 52.004 8
Ϸп,㷨ص:1 ʹõбֵΧǣ-4+4.2 бֵǶȦԹϵ.3 Ӧͼ.4 㷨ȽϺ.
һʵ.ڿɵ·ͼͼȡϵͳһԴԵͼ.ͼ6(a)һĶֵԴԵͼ,ͼ6(b)ϸͼ,ͼ6(c)ΪϺĶͼ.


(a) Ķͼ (b) ϸͼͼ (c) ͼ
ͼ6ʵ 
4 ѡȡ㷨Ӷȷ
㷨MT2.ѡĺûֱӰ㷨ľ,ǳҪ.Mѡȡźٶй.Mѡȡϴ,һ̶ڿ,ѸĻʱ;ͬʱ,Mѡȡϴ,ƹսǴбʵı仯.MѡȡС,ٶȿ,ƽ.ʹʱɸݾ趨.һ2345ȽСֵѡȡ.TѡȡϾкܴĹϵ.TѡȡС,ȿ,߶εĿ;Tϴ,߶εĿȻԼ,ȴ½.,TֵѡӾ.
㷨ķз,Ͼ.㷨ʱӶ.NΪܵݵ,ɵ2㷨,1㸴ӶΪC1N,C1Mйصĳ.ڲ2,㵱ǰʱ,ڵĲ.,ST,ST㷽ʱ,һȥT֮,T,Tʱ,ֻǰһλ.,ʱ临Ӷȵõ½.ʱ临ӶȿɽΪC2N,C2Ϊ.3еɾͬʱ.ҵһ,Ȼʣµаеĵȫɾ,Ȼʣµĵظ.ʱ临ӶΪC3N,C3߶θй,ɿ.ʴ,ܵʱ临ӶΪ(C1+C1+C1)N,㷨ʱ临ӶΪ.
5  
Ľһֻʸбʺͳģ͵ƽݵֶ㷨.ǰ㷨,㷨ľкܴ,ͼ,㷨˼,ʱ临ӶΪ,ҳʵ.һ㷨ѱƵļɵ·ͼͼʶϵͳ,ȡЧ.
߽ܣ,1968,ʿ,ҪоΪͼ,ɵ·ϵͳĿ.
ɽ,1934,,ʿʦ,ҪоΪɵ·,.
ͨѶϵ:Ϻ 200433,ѧӹϵCAD
ߵλ ɽѧӹϵ Ϻ 200433
ο
1Arelli C, Massarotti A. On the parallel generation of straight digital lines. Computer Vision, Graphics and Image Processing, 1978,7(1):6783
2.Ӿ.Ϻ:ѧ,1993(Wu Li-de. Computer Vision. Shanghai: Fudan University Press, 1993)
3Hakimi S L. Fitting polygonal functions to a set of points in the plane. Graphical Models and Image Processing, 1991,53(2):132136
4Hiroshi Aoyama, Masahiro Kawagoe. A piecewise linear approximation method preserving visual feature points of original figures. Graphical Models and Image Processing, Sept. 1991,53(5):435446
1997-11-11յԭ,1998-03-03յ޸ĸ
