Զѧ
ACTA AUTOMATICA SINICA
1998 24 5  Vol.24  No.5 1998



չHough任
ӾеӦ
ռ塡̵
ժҪHough任ֱչʽļչʽģӾϵͳĤȿռֲľ巽÷Ӿеעӵ켣⣬ȡ˽ΪĽ.
ؼʡչHough任ֱ߲ʽӾעӵ켣.
THE EXTENDED HOUGH TRANSFORM AND ITS
APPLICATIONS IN ACTIVE VISION FIELD
WANG WEIHU ZHANYIMA SONGDE
(National Laboratory of Pattern Recognition,Institute of Automation,
The Chinese Academy of Sciences,Beijing100080)
AbstractIn this paper,the extended Hough transform(EHT)is investigated.It is shown that it is impossible to give the necessary conditions of being an EHT.Two sufficient conditions,however,are introduced.In addition,the EHT is used to simulate a human vision system for the study of gaze control,a problem actively pursued in the active vision field currently.
Key wordsExtended Hough transform,line parameterization,active vision,focus of attention control.
1
Hough任123ԴӱھӰСԲڵжʺڲдŵ㣬ڼӾģʽʶõ˹㷺Ӧ.Ŵģɵ·ķٷչHough任Ӳʵ𽥳ΪܣַҲԽԽܵǵ.
Hough任ĲʽҪӰ45ݣΪˣԲͬӦóֱ߲ʽ67ݣԽԽ²ʽҲڲϳ.Щʽף89ۺֱ߲ʽ׼.
Ӿ1011ǼӾһǳҪоǿӾй۲ߺͻĶ̬̣о¶ⲿɸ֪̼Ķ̬Ϊķչ.עӵ켣ӾһҪо12ݣЧעӵ켣ƶӾʵżҪ.
չֱ߲ʽ13һ෶Χֱܹ߲ʽѱҪֱ߲ʽиһʽӦδõо.Ļף6ΨһԡнԺ;׼չʽֱ߲ʽɳ̽Ӿעӵ켣ƷӦ.
2Hough任ֱչʽ
2.1չʽ
Koshimizuˣ13ֱߵչHough任(EHTExtended Hough Transform)ĻʽΪ
g(,)=x.f1(,)+y.f2(,),(1)
Цֱ̣ߵ.ңֻҪ԰(1)ʽΪEHTһʽ
1.f1(̣),f2(̣),g(̣)ǹڱ̡εĵֵf21(̣)+f22(̣)0.f21+f220(1)ɱ滻Ϊ(2)(3).
(2)
R(̣)=x.cos(̣)+y.sin(̣).(3)
2.R(̣)(̣)ֱڱ̣ε(ݼ)淽(4)
Ṛ0(0)Σ0(0).   (4)
(ͬ)
3.̣н磬ҸԵĽΪk,0L0.BΪ׼ֱ߲ʽ2²ѵķΧ򷽳(5)õ
(̣K)-(̣0)=Уڦ̣(5a)
R(̣K)-R(̣0)=0ڦ̣(5b)
R(L)-R(0)=Bڦ.(5c)
ʵϣ3Ȳֱ߲ʽĳҲǱҪ.ΪΪһֱ߲ʽӦΨһ8ݣ(P1P2)Ϊһֱ߲ʽһԲ(p1,p2)ȷΨһһֱߣһֱ߶ӦΨһһԲ(p1,p2)1).ܱ֤Ψһ.
ΨһEHTʽ׵
1.緽(3)ֱ߲̣ΨһĳҪǣ趨ռں(̣)ĵֵ㼯Ϧ=(̣)(̣)=c2)(11),(22)ʦ(11)(22)R(11)R(22).
ǺԵģΪ緽(3)ֱ߲̣һԲ(r,)(r=R(̣),=(̣))ͼռֱߴһһӦϵΨһȼڲ(r,)(̣)֮佨һһӦϵ.1еǡǸһһӦϵĳҪ.
2.123ǹչʽĳΪҵ(11)(22)((11),R(11))=((22),R(22))(ͼ1ʾ).
(̣)=+3-1),(̣)ʣ01ݣ


ͼ 1123Ĳͼʾ

ԿǼϦ=(,)+3=2,Ρʣ,),̡ʣ01ݣ(1,1)ʦ(2,2)ʦ(1,1)(2,2)У(1,1)=(2,2)=,R(1,1)=R(2,2)=,ɽ1֪Ψһƻ.ˣ123չʽĳ.
3.123ǹչʽıҪ.ķ(ͼ2ʾ)ɳ˵һ.


ͼ 2123ĲҪͼʾ

֤Ψһһչʽ.Ȼͬʱ123.ɼ123ǹչʽıҪ.
2.2չʽΨһĳ
ݽ1ҪʹչʽΨһڲ(r,)(,)֮佨һһԹϵ.ֻR(,)(,)ǵֵԴӼεĽǶȿ൱ڣһ(r,)ֵ(r0,0)ߦ(,)=0R(,)=r0ڶҽһ.һ£ߦ(,)=0R(,)=r0ཻϵʮָӣѸֻһʵӦöԣһֻҪ½ΪѾ㹻.
1.ֱߵչʽR(,)=x.cos(,)+y.sin(,)
1)R(,)(,)ǹڱ̡εĵֵб̡ʣۦ0LݣΡʣۦ0Kݣ
2)ϦΣ0(򦵦Σ0)(,k)-(,0)=У̣
3)Ṛ0(Ṛ0)min(R(0,),R(L,))=0,max(R(0,),R(L,))=L,ΣУۦ0LΪ׼ֱ߲ʽ²ѵķΧ
֮һòʽΨһ.
4.=0,,,
5.R=0,,.
֤.R(,)(,)4
ڦ=0Ժ(,)ʵϽйأ(,)=f().ΪΡ0f()0ֻҪֵͬf()ֵ(,)ֵҲ3)Ӷ(,)ֵζŦֵ.ˣ1ᵽĺ(,)ĵֵ㼯Ϧ=(,)(,)=cʵһƽڦֱߦ=a,aΪζڵĳһ.ǵR̡0ԵֵȶֵʱR(,)ֵȣɴ˵ã(,)ĵֵ㼯ⲻͬR(,)ֵ.ٸݽ1֪ʱչʽΨһ.
ƿ֤R(,)(,)5ʱչʽҲΨһ.ۺϽ֪.֤.
ӼνǶȿ1ʵǰԭѴһཻ򻯳һֱһཻ.4Ц=0ζߦ(,)=0˻һƽеֱߣ5R=0ζR(,)=r0˻һƽеֱ.1ĳԾͺ.
ף6ָŻֱ߲ʽΨһ⣬ӦнԼ.νнԣ˵Hough任£һнͼռӦ任һнĲռ.νԣָڱ׼ʽ£ȱѡΪʱȵܶȺΪȷֱֲʽʾʱͨ׼ʽòʽ֮ĶӦϵøòʽܶȺܶȺҲӦΪȷֲ.ڱоչʽ£Ҫ
1(н).R(,)(,)㶨1չʽн.
֤.һͼϵ(x,y)ʣ-N/2N/2-M/2M/2ݣڶ1еչʽֱӵæ(,)ʣ0),R(,)ʵϺR(,)(,)Ƕнϵ(r,)(,)֮һһӦϵ.ԺR(,)(,)нҲζ(,)Ӧн.
2().R(,)(,)㶨1Ц(,)=a+b(a,bΪⳣ)չʽ.
Զ׼Ϊڱ׼ʽ£ȵܶȺΪȷֲ例=Ҧ=(-b)/aԦεܶȺͬΪȷֲõ.
3չHough任ӾеӦ
3.1չʽעӵ켣
ڼӾӾһǳҪоͻӾй۲ߺΧĶ̬̣ǿһй۲ߵ.עӵ켣ӾһҪо.Чעӵ켣ƶӾʵżҪ.
ӾϵͳУĤĲֶ̼ͬг̶ռֲǲȵ.ṹϿĤӾ(Ҫָ׶ϸ)ĿռֲԽҰ()ܶԽߣԵԽԽ.ӦأĤĵߣԵʱȾͻἱ½.Ӿϵͳһص㱣֤ڹ۲ⲿʱעӵ㸽(Ĥв)󾫶.ĤıԵֻнϴֲڵķֱ.ˣӾϵͳڰҪעҰĸȤֵͬʱҲֵֶܱʶע.ܲϸıעӵ㣬ʵʵľȹ۲Ұеκβ.
ף14вCCDṹģӾϵͳһӦڼӾϵͳȡһĳɹ.ǵķԺĴʵƵӲʵֲ޺ܴҪ.ּǰõĽչʽһ.
ĤȵĿռ仯һΪߵģ.ݴ˶庯R(,)(,)£
(6)
a,b,m,nΪ.
֤R(,)(,)㶨12˿Թֱߵչʽ4).ͼ3ʾչʽصڣR(,)ֵС༴ͼĽϽʱСR(,)ֵ仯ϴĦֵ仯R(,)ֵϴ༴ͼĽԶʱR(,)ֵ仯ֻСĦֵ仯.ԣ̲СR(,)ֵУڴR(,)ֵӰСǡǡӾϵͳ.
ͨռ(,)еķֵԶͼĸֱԺܸߵľȷͬʱҲܼͼԵֱߣԵĲֵȻٸЩԵĲֵʵƶעӵ㣬ѱԵȤĲ۲ģԺܸߵľȷֵ.ͿHough任ķʵӾеעӵ켣ơ


ͼ 3R(,)ڱȡֵ
еעӵ켣.
3.2ʵ
Ϊ֤ʵչʽЧԣʵ
һΪ-192192-144144ݵͼռ䣬Ӧ׼ֱ߲ʽ²ѵȡֵΧǣ-244244.̺ͦȡֵΧֱΪ̡ʣ0100ݣΡʣ0180).ݹʽ(6)庯R(,)(,)5)(R(,)ȡֵͼ3ʾ)
(,)=./180̡ʣ0100ݣΡʣ0180)

ͼ4(a)ΪԭʼͼͼռаֱߣͼģֲͼԵ.
ֱչʽͼ4(a)б任󣬵õӦռ(,)ͼ4(c)ʾ.۲֪ͼԵֱڲռڶӦԽڵķֵͼĵֱӦĸԷֿķֵ.
ȻڷֲܵķֵķֱʱȽϵͣǸЩֵӦĲֵԿԹƳӦֱͼռеĴ·ΧΪһעӵ켣Ƶ.
ƳĲֵͼ4(b)ʾעӵԭͼԵֱ߸ʱ.ֱչʽͼ4(b)б任󣬵õӦռ(,)ͼ4(d)ʾ.ԣڸıעӵԭռڽڵԷֵѾطָԭĸԷֿķֵΪԽڵķֵ.


(a)ԭʼ


(b)ıעӵͼ


(c)ͼaӦռάͼʾ


(d)ͼbӦռάͼʾ
ͼ4ֱߵչʽעӵƶʵ
4
ʵԿĸֱչʽڸ۵ǰģӾϵͳĤȵĿռ仯ԣЧʵӾеעӵ켣.Hough任ԭеŵ㲢ûܵӰ죬˸÷кܴʵüֵ.
863߼չƻȻѧĿ.
1)(p1,p2)(P1P2)һԸֵ.ڱ׼ֱ߲̦=x.cos+y.sinУΪ(ѣ)Ӧֱ2=x.cos45+y.sin45ĲֵΪ(245).
2)ڱ۵չʽԺ(̣)ֻҪ(̣k)-(̣0)=УϦ(̣)ȡֵܳһΪе.Լ(̣)=cʵ(̣)=c+k,kZZ.
3)õֵԦ1٦2,f()0 f(1)-f(2)=f().(1-2)0С(12).
4)Rڦ=b/20붨1ì.ʵϣR̿޸ֵ㴦01Ȼֻ֤ʹֵĲ޸ļɣʧһԣЦ102f()0Ρʣۦ1,0)(0,2,f(0)=0,f(2)-f(1)=(f(2)-f(0))+(f(0)-f(1))=f(2).(2-0)+f(1).(0-1)01(1,0),2(0,2).
5)ѷ(6)гֵnȡΪ19ǻ¿ǣڼʵֱչʽʱռ(,)ɢģϣR(,)ߴ(=50)R(,)ıһشСʱҲӦһۼӵԪ(ڸԪУֵܿܳӦĵԪϵļֵɢڽĵԪӶֵôͻ)ټϦ=100ʱR(,)240Լɽmn.
߼飺1972ںʡ.1994ҵ㽭ѧϵ񹤳ѧʿѧλ1997йѧԺԶ˶ʿѧλ.ҪоΪͼӾģʽʶ.
ռ塡1961ɽʡ.1985ҵڱҵѧԶϵ19881993ȺڱʱLiegeѧѧ˶ʿͲʿѧλ.ΪйѧԺԶģʽʶصʵоԱ.ҪоΪͼӾģʽʶ.
̵¡1946Ϻ.1968ҵ廪ѧԶϵ1983ѧʿѧλ1986ѧScience d'Etatʿѧλ.19831984ΪUniversity of MarylandĿоԱ19841986ΪINRIARobot Vision GroupĿоԱΪйѧԺԶ.ҪоΪӾ񾭼ͻڴĻ˿.
ߵλ(йѧԺԶģʽʶصʵҡ100080)
ο
1Hough P V C.A method and means for recognizing complex patterns,U.S.Patent 3,069,654,1962
2Duda R D,Hart P E.Use of the Hough transform to detect lines and curves in pictures.CACM1972,15(1):11-15
3Ballard D H.Generalizing the Hough transform to detect arbitrary shapes.Pattern Recognition,1981,13(2):111-122
4Maitre H. Contribution to the prediction of performances of the Hough transform.IEEE T-PAMI,1986,8(5):669-674
5Hu Z,Destine J.Performance comparison of line Parameterizations.In:Proceedings,11th International Conference on Pattern Recognition,1992,3:335-338
6Biland H P.The recognition of three-dimensional polyhedral scene by analysis of Hough space structuresPh.D.thesis.ETH,Zrich:Swiss Federal Institute of Technology Zurich,1987
7Risse T.Hough transform for line recognition:complexity of evidence accumulation and cluster detection.CVGIP,1989,46:327-345
8Hu Z,Ma S D.Three conditions of a good line parameterization.Patter Recognition Letters,1995,16:385-388
9Hu Z,Ma S D.Uniform line parameterization.Pattern Recognition Letters,199617503507
10Aloimonos J,Weiss I,Bandyopadhyay A.Active vision.Inter.J.of Computer Vision,1988,1(4):333-356
11Ballard D H,Brown C M.Principles of animate vision.CVGIP:Image understanding,1992,52(51):3-21
12Swain M J,Stricker M A.Promisig directions in active vision,edited.Inter.J.of Computer Vision,1993,11(2):109-126
13Koshimizu H,Numada M,Murakami K.Askant vision architecture using warp model of Hough transformfor realizing dynamic & central/peripheral camera vision.Trans.IEICE.1994,E77-D(11):1206-1212
14Debusschere I,Bronckaers E,Claeys C,Kreider G,Van der Speigel J,Bellutti P,Soncini G,Dario P,Fantini F,Sandini G.A 2D retinal CCD sensor for fast 2D shape recognition and tracking.In:Proceedings,5th International Solid-State Sensor and Transducers,Montreux,1989
ոڡ1997-01-27
