о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



ݵ㷨
㡡ġ
ժҪڻģ͵ı뼼УѡʵģͶģ͵˶ƾȡЧʺ͵õĽͼҪ.ĻͼݵӦģ㷨ѧ̬ѧеˮ㷨ѱͼָһµָӳͼĽṹͱ߽磻ٶЩı߽жϣõθߵĶ˵Ϊģ͵Ľڵ㣬ЩڵΪһDelaunay.ͨ㷨õЧͼĽṹӶиõ˶͸ߵıЧ.
ؼʡģ͵ı룬ݵɣѧ̬ѧˮ㷨
ͼšTP391.4
CONTENT-BASED MESH GENERATION ALGORITHM
WU FengGAO Wen Gao Peng*, and QU Li-Jun**
(Department of Computer Science and Technology, Harbin Institute of Technology, Harbin150001)
*(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
**(Institute of Automation, Chinese Academy of Sciences, Beijing 100080)
AbstractIt is critical to choose a suitable model for accurate motion estimation, efficiently encoding image signal, and high quality decoding image in model-based coding. A content-based adaptive mesh generation algorithm is proposed in this paper. At first, a watershed algorithm of mathematical morphology is used to segment image into many homogeneous regions so that watershed lines can better represent image structure, contours, and edges. Boundaries of these regions are approximated by polygons that can be represented with a few parameters. Each end point of polygonal sides serves as candidate node of mesh model. Because interval between candidate nodes may be too large or small, some mesh elements based on these nodes are unsuitable for later tracking and motion estimation in quality and size. Some preprocessing are adopted to delete or insert some candidate nodes. A content-based Delaunay triangular mesh can be generated on these nodes with limitation in nodal interval. The results of this algorithm can more efficiently represent encoding image structure, so accurate motion estimation and efficiently encoding can better achieve in model-based coding.
Key wordsmodel-based encoding, content-based mesh generation, mathematical morphology, watershed algorithm
1
ͳĿ˶ƺDCT任ϵı뷽ƵаʱȺΪ֡ÿһ֡ͼַΪ1616ĺ˶ͱ룬ֱ뷽ͼľṹݽͼ̶ֳͬСĿ飬õļ򵥿ƥ似Ҳֻܲƽ˶ڵʱʱȻصĿЧӦ.ģ͵ı뷽12ݰͼķͺϳɼڱ֮УΪͼ񶼾һĽṹһģͼ.ѡʺϱͼĽṹģͺ˶ģҪ.
ڼMPEG-4µıʱ׼У3ݣģ͵ı뼼.ñ׼涨˱ģͽڵλú˶㷨ʽεõģͼȷģ͵ĽڵλãԼιƽڵλõ˶仯ڸñ׼вûκι涨Ϊһо.ҪλͼӦģ.
2ģͽ
ģ͵ı뼼Դ80󣬹ȡͼģͽо.Щоģ͵ķ¿ԷΪ3ࣺӦͻݵ.
46ǰͼһĹֳͬСλıΣͳİͼ񻮷Ϊ1616ı뷽ǹһͬڻģ͵ı뷽ͨһ˶ģ˶.Ƭ˶ģͨ÷任

(1)
aijƬ˶6Щͨε3ȷ.ıƬ˶ģͨ˫Ա任

(2)
aijı˶8Щͨıε4ȷ.˶ģŵ£ȱκΣͬģ5.ͬƬ£ҪĽڵ٣õ˸оӦ.ڱвҪԱͼзֻҪ򵥹涨ͼˮƽʹֱĽڵҪ涨Խߵķ򣬾ڽ˺ͱͬģͣҲҪģ͸ڵλ.ģͲܺܺõطӳͼĽṹͬһƬϿܰͬ˶ԺԣؽӰ˶ƵľȺӳ.
Ӧ78ڹģ͵ĻϣһۺжÿƬǷ˶죬Դھֲ˶ԲܴƬһϸ֣ƬĲһڵ㽫Ϊ3СΣı4ߵĲһڵ㽫仮Ϊ4Сı.ģһӦͼӻھֲ˶ڸƬ.ģ͵ĽڵλÿͨͼЧ.
ݵģͣ910Ҫͼķģͣõģܺܺõķӳͼı߽Ӷȷع˶ȷӳ.ף9ͼʱͿݶϢѡģ͵Ľڵ㣬Delaunayף10ݵ㷨Ҳǻݶȵķģʱشǰ帲Ǳͱ±¶.ΪȷͼЩһ֡б¶Щ򽫱ǣҪָͼǰ׼ȷ˶㷨ĸӶȸߣ׼ȷҲ޷֤.ʱݶȺͿݶȡģͽڵķѡĽڵλúͼӰ죬Ҳȷͼı߽ģ͵ı.һȽģҲڻݵģͣҪͼе.ģ͸ĹȽͨģͣ1112ݣڱиض˵κͽṹϵϸ΢𣬵ͨģƥضȻ󽫸ģͼı.
һµĻͼݵģ͵ɷ.ǲˮ㷨Թؼ֡ͼI֡зЩͼָΪһµ򣬵õˮ߾ܷӳͼĽṹͱ߽磻ٶЩı߽жϣȷЧͼṹϢĹؼ㣬ЩؼΪģ͵Ľڵ㣬ӶһͼݵDelaunay.ģͲǻݶȡķָͨķõģͼкܺõ³ԣģ͵ıҲܺܺöͼͱ߽磬ģ͵˶ƾȺӳ.
3㷨
㷨ĺ˼ѧ̬ѧɻݵģ.ѧ̬ѧ1314ṩͼļηܹȽ״ͼС״ԱȶȺͨԵһЩͼеõ㷺Ӧãˮ߱任ΪͼָĹߣ1517.㷨4֣̬Ԥˮ߷ָϺDelaunay ɣ潫ֱ۸ֵ㷨ʵ.
3.1̬Ԥ
̬ԤĿǼҪˮ߷ָͼ񣬷ֹڷָвȷָ.̬Ԥѧ̬ѧĹ.ڸԤ㷨ǰȶ弸ӺͲ.
1. (dilatation)͸ʴ(erosion).
f(x)ʾͼAnʾߴΪnĽṹԪأô̬Ӻ͸ʴӶ£
ӣn(f)=maxf(x-a),aAn(3)
ʴӣn(f)=minf(x+a),aAn(4)
2. (opening)ͱ(closing)˲.
˲an(f)=n(n(f))(5)
˲n(f)=n(n(f))(6)
̬˲ͱ˲ͨȥͼСڽṹԪصͰͼΪͼԤߣЩ˲ڼͼͬʱҲʹͼʧ˲ֱ߽Ϣ.Ϊ˻ָʧı߽Ϣͨʽ(7)Ŀعָûȫʧı߽磺
(rec)(n(f),f)=1(1(n(f),f)f)
(7)
ϸԤΪȶԭͼ̬ͨݶȹʽ8õṹԪΪ33̬ݶͼ񣻶̬ݶͼнṹԪΪ55ı˲Ϳ˲ֱСڽṹԪصİ͹Ϊ˻ָ˲ʧı߽Ϣ˲ǰͼΪοԴͼпع
f=n(f)-n(f)
(8)
3.2ˮ߷ָ
轫άͼf(x,y)һάĵͼͼĻҶֵʾεĸߵͣҶֵԽСʾԽ.ˮ㷨ģѸõͼˮеĹ.ڶάĵͼֲʹһСףõͼٰˮ棬ˮȴЩС׽ֲİ.ˮĽ룬ֲͬˮ۵һ.Ϊ˷ֹˮĻۣҪڻˮ.ͼˮ£¶ˮľֻЩˮӣЩˮӳˮߣͼָΪͬ.
ˮ㷨õŵķʵһ̣ͨ3.1ԤͼСҶֵΪhminЩСˮ߷ָĸʼ.㷨£
1.ص㰴ҶֵСһȽȳУ
2.ȡлҶֵΪhminص㣬ĹֱΨһıţ
 ص㸳Ψһıţÿһűʾһ
 ڵص㸳ͬıţʾЩصͬһ
3.شӶȡһҶֵص㣬Щص3
 صڴѾ˱ŵص㣬Щ˱ŵصͬص㸳ͬıţ
 صڴѾ˱ŵص㣬Щ˱ŵصŲͬصһıţžˮߣ
 صڲڷ˱ŵص㣬ʾصһ°ʼ㣬طһµıţ
4.ظֱеص㶼б.
бΪˮߵص͹˽ͼָɸˮ.ˮ㷨ľͼԲοף18.
3.3
ϵĿһľ£þٵĵͼ״Ϣ.ˮ㷨õˮȻܺܺ÷ӳͼĽṹҪһЧı﷽ʽξͨĽڵͼ״.ǲһ˼·ȴЧĶϷʾ3.2еõˮߣ㷨Ϊ:
1.ȡͼˮߵĽбcrosspointlistϵˮߵĽ㣬ЩҲǶϵĶ˵㣻
2.crosspointlistȡһcross1crosspointlistȥ.8صıΪˮߣĽбstacklistУѡһΪˮߵصΪ㣬ıΪʾˮѾ
3.ˮֱ߽ˮߵһcross2㼰֮ص㱣һбpointlist.ڵڶеĿǽЩصıͬ.cross2ڻصıΪˮߣcross2stacklist.cross2crosspointlistУӸбȥcross2
4.µĵ
 pointlistи㵽㣨˵㣩ߵŷϾ룻
 pointlistоĵ㼰HH趨ֵصΪεĶ˵.pointlistһΪõбآ٣ִһ
5.stacklistǿգstacklistȡһ㣬ز3
6.crosspointlistǿգز2.END.
ϵõж˵ˮߵĹؼ㣬Ҳģ͵ĺѡڵ.
3.4Delaunay
ͨԷָı߽жϣǵõͼĽṹͱ߽һЩؼ㣬Щؼģ͵Ľڵ.ģʱҪЩڵд.ѡĽڵ⣺ϵĽڵܽԼͼ߽Ͻڵľ̫ĽڵģʹεС̫Сε̫̫С⣬ЩƬ˶.ǰһĽڵȡڵĽڵ㣺

(9)
Ա߽Ͻڵ̫ͨ޶ڵһЩµĽڵ.ѡģ͵Ľڵ󣬿Delaunay㷨Ψһ񣬾㷨Բοף19.
4ʵ
ʵ1.ʵ1ñ㷨ģ͵Ḷ́Miss AmericaCCITTṩĲɫУͼĸʽQCIFͼߴ176144ɹֻõͼϢ.ͼ1(a)ͼеһ֡ԭͼ(b)Ǿ̬ݶȡ˲ؽԤͼ(c)ͼˮ߷ָĽ(d) ǶԷָжϺĽ.ͼ2(a)Ǳ㷨õģ.ͼ2(b) ģͺͼ2(c)ʱͿݶѡģͽڵģͱȽϿԿͬڵ£㷨õģ͸ܷӳͼĽṹģ͵ıҲܱȽϺõضͼı߽.

(a)

(b)

(c)

(d)
ͼ1(a)ԭͼ(b)̬ݶȺؽԤͼ(c)ˮ߷ָĽ
(d)ϵĽ

(a)

(b)

(c)
ͼ2(a)㷨ɵģ(b)ģ(c)ݶȵģ
ʵ2.оģɷĿΪ߻ģ͵ı뷽ЧʺͺϳͼʵȽ˹ݶͱ˶.ʵMiss America(1150֡)Akiyo(1300֡)Mother and Daughter(100400֡)3ͼУԭͼе֡30Hzʵʵı֡10 Hzͼĵ147֡.ΪصӰ죬ʵǰһ֡ͼԭͼΪοͼ.ģ͵˶Ʋƥ㷨Ϊ1ֻ3ͼĵһ֡ͼģͼI֡룬֡˶ķP֡.13ģڱ3ͼеģͲ˶ƽȣͬһͼе3ģͽڵͬ.ģMiss AmericaбҪȹ1.3dBݶҪ0.47dB.ͼ3ͼпԿе60110֡ͼƶĹУģ͵˶ЧԶԶģ.ڱAkiyoMother & Daughterʱɵģ˶ƵҲͬڹݶ.
1ģ͵˶
ͼйݶĵ
Miss America
(150֡)ڵ()707171
()108110118
ƽ(dB)37.9938.8339.30
Akiyo
(300֡)ڵ()817879
()128124137
ƽ(dB)39.4539.8340.21
Mother & Daughter
(300֡)ڵ()110109109
()180186191
ƽ(dB)36.1136.8037.30


ͼ 3 Miss America ˶
5
Ļݵ㷨Ҫͼ֪ʶȫͨͼķԶõӳͼṹģͣ㷨ļҲбȽϹ㷺Ӧñ.Ŀǰ㷨̬ѧģҪǸͼе˶ϢܵõõЧ.㷨жǰ˶Ҵ໥˶ͼеģ.Ϊ˽ͼģ͵ɣҪָ˶׼ȷ˶ÿģͿñ㷨õ.
ע:õȻѧ(Ŀ69789301)͹ҡ߿Ƽ(Ŀ863-306-03-01-1).
߼:㣬У1969ʿоҪоΪ˶ͼͼӾ.
ģУ1956ڣʿʦҪоΪ˹ܺͶý弼.
У1966оԱҪоΪֻHDTV.
У1972˶ʿоҪоΪͼָ.
ߵλ:㡡ġҵѧѧ빤ϵ150001
йѧԺ㼼о100080
йѧԺԶо100080
ο
1Li H, Lundmark A, Forchheimer R. Image sequence coding at very low bitrates: A review. IEEE Trans Image Processing, 1994, 3(5): 589609
2Aizawa K, Huang H S. Model-based image coding: Advanced video coding techniques for very low bitrate applications. in Proc of IEEE, 1995, 83(2): 259271
3MPEG-4 overview. ISO/IEC JTC1/SC29/WG11, N2564, 46th MPEG Meeting, Roma, 1998
4Brusewitz H. Motion compensation with triangles. In: Proc 3rd Int Conf 64-Kbit Coding of Moving Video, Rotterdam, Netherlands, 1990
5Yuichiro Nakaya, Hiroshi Harashima. Motion compensation based on spatial transformations. IEEE Trans on Circuits and System for Video Technology, 1994, 14(3): 339356
6Sullivan G J, Baker R L. Motion compensation for video compression using control grid interpolation. In: Proc International Conf on Acoustics, Speed and Signal Processing, Toronto, Canada, 1991. 27132716
7Huang Chunglin, Hsu Chaoyuen. A new motion compensation method for image sequence coding using hierarachical grid interpolation. IEEE Trans on Circuits and System for Video Technology, 1994, 4(1): 4252
8Lee W F, Yuen P C, Chan C K. Two-dimensional split and merge algorithm for image coding. SPIE Visual Communications and Image Processing, Minneapolis, MN, 1995, 2501: 694704
9Dudon M, Avaro O, Roux O. Triangular active mesh for Motion estimation. Signal Processing: Image Communication, 1997, 10: 2141
10 Altunbasan Y, Tekalp A M. Occlusion-adaptive, content-based mesh design and forward tracking. IEEE Trans on Image Processing,1997, 16(9): 12701280
11 Rydfalk M. CANDIDE: A parameterized face. Link Oping Univ, Dep Elec Eng Rep: LiTH-ISY-I-0866, 1987
12 Aizawa K, Harashima H, Saito T. Model-based analysis synthesis image coding for a person's face. Image communication, 1989, 1(2): 139152
13 Serra J.Image analysis and mathematical morphology, London, Academic Press, 1982
14 Serra J. Image analysis and mathematical morphology, Part II:Theoretical advances, London, Academic Press, 1988
15 Salembier P, Oardas M. Hierarchical morphological segmentation for image sequence coding. IEEE Trans Image processing,1994,3(5):639651
16 Demin W.A multiscale gradient algorithm for image segmentation using watershed. Pattern Recognization, 1997, 30(20): 2141
17 Beucher S,Meyer F.The morphological approach to segmentation: The watershed transformation. In: Dougherty E R eds.Mathematical Morphology in Image Processing. 1992, 453482
18 Vincent L, Soille P. Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Trans PAMI, 1991, 13(6): 583598
19 Shewchuk J R.Delaunay refinement mesh generation Ph D thesis, Carnegie Mellon University, 1997
ԭյڣ1999-01-05޸ĸյڣ1999-03-19.
