Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2007-08-28
2007-08-28
Tung, Kee M. (Department: 2628)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S232000, C345S420000
Reexamination Certificate
active
10727629
ABSTRACT:
Provided are methods and apparatuses for encoding and decoding three-dimensional object data, which consists of point texture data, voxel data, or octree data. The method of encoding three-dimensional object data involves generating three-dimensional object data having a tree structure in which nodes are attached labels indicating their types; encoding nodes of the three-dimensional object data; and generating the three-dimensional object data whose nodes are encoded into a bitstream. The apparatus for encoding three-dimensional object data includes a tree structure generator which generates three-dimensional object data having a tree structure in which nodes are attached labels indicating their types; a merging order selector which merges the nodes of the three-dimensional object data by referring to their labels; a node encoder which encodes merged nodes; and a bitstream generator which generates the three-dimensional object data whose merged nodes are encoded into a bitstream. The method of decoding three-dimensional object data involves reading-continue flag information from a bitstream of encoded three-dimensional object data and decoding the continue flag information; decoding note type information of the bitstream; decoding an ‘S’ node if the note type information indicates that a current node is an ‘S’ node and decoding a PPM node if the note type information indicates that the current node is a PPM node; and restoring the three-dimensional object data whose nodes are encoded to a tree structure. The apparatus for decoding three-dimensional object data includes a bitstream reader which receives a bitstream of encoded three-dimensional object data; a node decoder which decodes the bitstream; and a tree structure restorer which restores decoded nodes to a tree structure.
REFERENCES:
patent: 4694404 (1987-09-01), Meagher
patent: 5123084 (1992-06-01), Prevost et al.
patent: 5999187 (1999-12-01), Dehmlow et al.
patent: 6396492 (2002-05-01), Frisken et al.
patent: 6429864 (2002-08-01), Schwarzer
patent: 6518963 (2003-02-01), Waupotitsch et al.
patent: 6529192 (2003-03-01), Waupotitsch
patent: 6535642 (2003-03-01), De Bonet
patent: 6563499 (2003-05-01), Waupotitsch et al.
patent: 6603484 (2003-08-01), Frisken et al.
patent: 6914601 (2005-07-01), Fujiwara et al.
patent: 6999073 (2006-02-01), Zwern et al.
Chang et al., “LDI tree: a hierarchical representation for image-based rendering”, Proc. of 26th Annual Conf. on Computer Graphics and interactive Techniques, 1999, ACM Press/Addison-Wesley Publishing Co., NY, NY, pp. 291-298.
Moffat, A., “Two-level context based compression of binary images”, Data Compression Conference, 1991, DCC '91, Apr. 8-11, 1991, pp. 382-391.
Jiangang Duan et al., “Compression of the Layered Depth Image”, Proceedings of Data Compression Conference, IEEE Computer Society Press, 2001, pp. 331-340.
Rambally et al., “Octrees and their applications in image processing”, Proceedings of IEEE Southeastcon '90, Apr. 1990, pp. 1116-1120, vol. 3.
Shkarin, D., “PPM: one step to practicality”, Proceedings of Data Compression Conference, DCC 2002, Apr. 2002, pp. 202-211.
Sherwood, T. and Calder, B., “Automated design of finite state machine predictors for customized processors”, Proc. of 28th Annual international Symposium on Computer Architecture, 2001, ISCA '01. ACM Press, NY, NY, pp. 86-97.
Forchhammer, S.; Salinas, J.M., “Progressive coding of palette images and digital maps”, Proceedings of Data Compression Conference, DCC 2002, Apr. 2002, pp. 362-371.
Moffat, A., Neal, R. M., and Witten, I. H., “Arithmetic coding revisited”, ACM Trans. Inf. Syst. vol. 16, Issue 3, Jul. 1998, pp. 256-294.
Jiangang Duan et al., “Compression of the Layered Depth Image”, IEEE Transaction on Image Processing, 2003, pp. 365-372, vol. 12, No. 3.
Marcelo J. Weinberger et al., The LOCO-I Lossless Image Compression algorithm: Principles and Standardization into JPEG-LS, IEEE Transactions on Image Processing, 2000, pp. 1309-1324, vol. 9, No. 8.
Chang-Su Kim et al., “Compact Encoding of 3D Voxel Surfaces Based on Pattern Code Representation”, IEEE Transactions on Image Processing, 2002, pp. 932-943, vol. 11, No. 8.
I. Moccagatta et al., “MPEG-e Video Verification Model Version 13.0”, International Organisation for Standardisation , ISO/JTC1/SC29/WG11, Coding of Moving Pictures and Associated Audio Information, 1999, pp. 362, MPEG99/N2687, Seoul, Korea.
Mikael Vourges-Sevenier (Mindego) et al., “FDIS of ISO/IEC 14496 Part 16: Animation Framework eXtension (AFX)”, International Organisation for Standardisation, ISO?IEC JTC1/SC29/WG11, 2002, pp. 1-182, ISO/IEC JTC1/SC29/WG11 N5397, Awaji.
Paul G. Howard et al., “Arithmetic Coding for Data Compression”, Proceedings of the IEEE, 1994, pp. 857-865, vol. 82, No. 6.
Alexander Zhirkov et al.,, “Result of Core Experiment on Depth Image-Based Representation (AFXA8.3)”, International Organisation for Standardisation, Coding of Moving Pictures and Audio, ISO/IECJTC1/SC29/WG11, MPEG2002/M8259, 2002, pp. 1-10, Fairfax, Virginia, USA.
Khalid Sayood, “Introduction to Data Compression”, 2nd Edition, 2000, pp. 1-179, Academic Press.
Y. Bayakovski et al., “Depth Image-Based Representations for Static And animated 3D Objects”, IEEE ICIP, 2002, pp. 25-28, vol. 3, Rochester, New York, USA.
Mikael Bourges-Sevenier (Mindego) et al., FPDAM Of ISO/IEC 14496-1/AMD4, International Organisation for Standardisation, Coding of Moving Pictures and audio, ISO/IEC JTC1/SC29/WG11, N5071, 2002, pp. 1-367, Klagenfurt, Germany.
European Search Report for corresponding Application No. 03257599.5.
Y. Bayakovski et al., “Depth Image-Based Representations and Compression for Static and Animated 3D Objects”, Laboratory of Computer Graphics at Dep of CS MSU, 2002, pp. 1-27.
Y. Bayakovski et al., “Depth Image-Based Representations for Static and Animated 3D Objects”, Proceedings International Conference on Image Processing, ICIP 2002, pp. 25-28, vol. 2, No. 3. IEEE, New York, NY, USA.
Hanan Samet et al., “Octree Approximation and Compression Methods”, Proceedings of First International Symposium on 3D Data Processing Visualization and Transmission, Padova, Italy, 2002, pp. 1-10, IEEE Computer Society.
John G. Cleary et al., “Data Compression Using Adaptive Coding and Partial String Matching”, IEEE Transactions on Communications, 1984, pp. 396-402, vol. COM-32, No. 4, IEEE Inc., New York, USA.
Alexander Zhirkov, “Binary Volumetric Octree Representation for Image-Based Rendering”, Proc. Of Graphicon'01, 2001, pp. 1-2, Retrieved from the Internet.
Chinese Office Action dated Dec. 13, 2005 with English-language translation.
Tong Cao et al., “Quick Encoding Compression Algorithm of Octree for Modeling Three Dimensional GIS”, Journal of Image and Graphics, vol. 7(A), No. 1, January 2002, pp. 50-54.
Kim Chang-su
Lee Sang-uk
Lee Shin-jun
Park In-kyu
Song In-wook
Buchanan & Ingersoll & Rooney PC
Prendergast Roberta
Samsung Electronics Co,. Ltd.
Seoul National University Industry Foundation
Tung Kee M.
LandOfFree
Method and apparatus for encoding and decoding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for encoding and decoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encoding and decoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3876001