Special Issue: Computer Networks and Distributed Computing

• Computer Graphics and CAD • Previous Articles     Next Articles

An Effective Error Resilient Packetization Scheme for Progressive Mesh Transmission over Unreliable Networks

Bai-Lin Yang1,2, Frederick W. B. Li3, Zhi-Geng Pan2,*, and Xun Wang1   

  1. 1College of Computer Science and Information Engineering, Zhejiang Gongshang University, Hangzhou 310018, China 2State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China 3Department of Computer Science, University of Durham, U.K.
  • Received:2008-01-11 Revised:2008-07-19 Online:2008-11-10 Published:2008-11-10

When a 3D model is transmitted over a lossy network, some model information may inevitably be missing. Under such situation, one may not be able to visualize the receiving model unless the lost model information has been retransmitted. Progressive model transmission offers an alternative to avoid the ``all or nothing situation'' by allowing a model to be visualized with a degraded quality when only part of the model data has been received. Unfortunately, in case some model refinement information is missing, one may still need to wait for such information to be retransmitted before the model can be rendered with a desired visual quality. To address this problem, we have developed a novel error resilient packetization scheme. We first construct a Non-Redundant Directed Acyclic Graph to encode the dependencies among the vertex splits of a progressive mesh. A special Global Graph Equipartition Packing Algorithm is then applied to partitioning this graph into several equal size sub-graphs, which is packed as packets. The packing algorithm comprises two main phases: initial partition phase and global refinement phase. Experimental results demonstrate that the proposed scheme can minimize the dependencies between packets. Hence, it reduces the delay in rendering 3D models with proper quality at the clients.

Key words: logic filter; mammogram diagnosis; image processing for mammograms;

[1] Chen Z, Barnes F J, Bodenheimer B. Hybrid and forward error correction transmission techniques for unreliable transport of 3D geometry. {\it Multimedia Systems Journal}, March 2005, 10(3): 230--244.
[2]} Al-Regib G, Altunbasak Y. 3TP: An application-layer protocol for streaming 3-D models. {\it IEEE Transactions on Multimedia}, 2005, 7(6): 1149--1156.
[3]} Peterson L L, Davie B S. Computer Networks. Academic Press, CA, 2000.
[4]} Al-Regib G, Altunbasak Y. An unequal error protection method for packet loss resilient 3-D mesh transmission. In {\it Proc. IEEE INFOCOM}, New York, USA, 2002, 2: 743--752.
[5]} Tian D, AlRegib G. On-demand transmission of 3D models over lossy networks. {\it SIP Journal on Signal Processing: Image Communication}, 2006, 21(5): 396--415.
[6]} Girod B, Stuhlmuller K, Link M, Horn U. Packet loss resilient Internet video streaming. In {\it Proc. SPIE Visual \hbox{Communication} and Image Processing}, San Jose, CA, USA, 1999, pp.833--844.
[7]} Chen Z, Bodenheimer B, Barnes J F. Extending progressive meshes for use over unreliable networks. In {\it Proc. the IEEE Conference on Multimedia and Expo}, Baltimore, MD, Vol.3, July 2003, pp.253--256.
[8]} Bischoff S, Kobbelt L. Towards robust broadcasting of geometry data. {\it Computers $\&$ Graphics}, 2002, 26(5): 665--675.
[9]} Sung-Bum Park, Chang-Su Kim, Sang-UK Lee. Error resilient coding of 3-D meshes. In {\it Proc. International Conference on Image Processing}, Barcelona, Vol.1, 2003, pp.I-773--I-776.
[10]} Yan Z, Kumar S, Kuo C C J. Mesh segmentation schemes for error resilient coding of 3-D graphic models. {\it IEEE Trans. Circuits Syst. Video Techn}, 2005, 15(1): 138--144.
[11]} Al-regib G, Altunbasak Y, Rossignac J. Error-resilient transmission of 3D models. {\it ACM Transactions on Graphics}, 2005, 24(2): 182--208.
[12]} Hoppe H. Progressive meshes. In {\it Proc. SIGGRAPH 96}, New Orleans, USA, 1996, pp.99--108.
[13]} Floriani L De, Magillo P. Multiresolution Mesh Representation: Models and Data Structures. {Multiresolution in Geometric Modelling}, Floater M, Iske A, Qwak E (eds.), Springer-Verlag, 2002, pp.363--418.
[14]} Gu\'eziec A, Taubin G, Lazarus F, Horn W. Simplicial maps for progressive transmission of polygonal surfaces. In {\it Proc. ACM Int. Conf. Virtual Reality and Modeling Language $($VRML'98$)$}, Monterey, USA, 1998, pp.25--31.
[15]} Zheng Z, Chan T KY. View-dependent progressive mesh using non-redundant DAG hierarchy. In {\it Proc. the 3rd Int. Conf. Computer Graphics and Interactive Techniques in Australia and South East Asia}, Dunedin, New Zeeland, 2005, pp.417--420.
[16]} Pereira F, Ebrahimi T. The MPEG-4 Book [M]. IMSC Press and Prentice Hall, USA, 2002.
[17]} Harris A F, Kravets R. The design of a transport protocol for on-demand graphical rendering. In {\it Proc. NOSSDAV}, Miami, USA, 2002, pp.43--49.
[18]} Gu Y, Ooi W T. Packetization of 3D progressive meshes for streaming over lossy networks. In {\it Proc. International Conference on Computer Communications and Networks $($IC3N$)$}, San Diego, CA, USA, October 17--19, 2005, pp.415--420.
[19]} Mitchell J. Branch-and-cut for the $k$-way equipartition problem. Technical Report, Rensselaer Polytechnique Institute, 2001.
[20]} Frieze A, Jerrum M. Improved approximation algorithms for max $k$-cut and max bisection. In {\it Proc. the Fourth IPCO Conference}, Copenhagen, Denmark, 1995, pp.1--13.
[21]} Karisch S E, Rendl F. Semidenite programming and graph equipartition. Topics in Semide\_nite and Interior-Point Methods, Pardalos P M, Wolkowicz H (eds.), \it Fields Institute Communications, \rm AMS, 1998, 18: 77--95.
[22]} Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning, irregular graphs. {\it SIAM Journal on Scientific Computing}, 1998, 20(1): 359--392.
[23]} Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. \it Bell Sys., Tech. J., \rm 1970, 49: 291--307.
[24]} UCB/LBNL/VINT. Network simulator ns (Version 2). Available on URL: http://www.isi.edu/nsnam/ns/.
[25]} Velten D, Hinden R. Sax v. reliable data protocol. {\it RFC 908}, 1984.
[1] Alberto Rocha; TONG Fu; YAN Zhuangzhi;. A Logic Filter for Tumor Detection on Mammograms [J]. , 2000, 15(6): 629-632.
Full text



[1] Wu Xindong;. Inductive Learning[J]. , 1993, 8(2): 22 -36 .
[2] Zhao Yu; Zhang Qiong; Xiang Hui; Shi Jiaosing; He Zhijun;. A Simplified Model for Generating 3D Realistic Sound in the Multimedia and Virtual Reality Systems[J]. , 1996, 11(4): 461 -470 .
[3] Shuai Dianxun;. Concurrent Competitive Wave Approach to Hyper-Distributed Hyper-Parallel AI Processing[J]. , 1997, 12(6): 543 -554 .
[4] Zhong-Xuan Liu, Shi-Guo Lian, and Zhen Ren. Quaternion Diffusion for Color Image Filtering[J]. , 2006, 21(1): 126 -136 .
[5] Cai-Ming Zhang, Hui-Jian Han, and Fuhua Frank Cheng. Determining Knots by Minimizing Energy[J]. , 2006, 21(2): 261 -264 .
[6] Hong Mei, Dong-Gang Cao, and Fu-Qing Yang. Development of Software Engineering: A Research Perspective[J]. , 2006, 21(5): 682 -696 .
[7] Hui-Zhan Yi and Xue-Jun Yang. Toward the Optimal Configuration of Dynamic Voltage Scaling Points in Real-Time Applications[J]. , 2006, 21(6): 893 -900 .
[8] Fei-Yue Wang, Ning-Hui Sun, Wen-Ji Mao, and Xiao-Wei Li. Preface[J]. , 2009, 24(6): 997 -999 .
[9] Xin Li (李新), Zhang-Jin Huang (黄章进), and Zhao Liu (刘昭). A Geometric Approach for Multi-Degree Spline[J]. , 2012, 27(4): 841 -850 .
[10] Jie Wu. Collaborative Mobile Charging and Coverage[J]. , 2014, 29(4): 550 -561 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved