Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2011-08-16
2011-08-16
Werner, Brian P (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
Reexamination Certificate
active
08000547
ABSTRACT:
A method, system and computer program product for progressively encoding a digitized color image with M distinct colors by assigning each of the M distinct colors to an associated subset of pixels in the image, is provided. This involves: (a) initializing a tree structure with at least one starting leaf node comprising a subset of the M distinct colors; (b) determining at least one representative color for each starting leaf node; and (c) growing the tree structure by (i) selecting a leaf node n to become a non-leaf node based on the combined distortion and entropy rate resulting from turning the leaf node into the non-leaf node; (ii) allocating each color in leaf node n to one of the two new leaf nodes; (iii) determining a representative color for each new leaf node; and (iv) encoding the resulting index information, representative color information, and pixel information.
REFERENCES:
patent: 5047842 (1991-09-01), Bouman et al.
patent: 6496198 (2002-12-01), Wang
patent: 2004/0170332 (2004-09-01), Andrew
patent: 2006/0188024 (2006-08-01), Suzuki et al.
Guillope V.: Conditional Entropy-Constrained Vector Quantization of Chromatic Information in Document Images, retrieved from Internet: URL:http:|/www.site.uottawa.calschool/research|viva/theses/Guillope—thesis.pdf; Jun. 2002.
de Garrido, D.P.; Ligang Lu; Pearlman, W.A., “Conditional entropy-constrained vector quantization of displaced frame difference subband signals,” Image Processing, 1994. Proceedings. ICIP-94., IEEE International Conference , vol. 1, no., pp. 745-749 vol. 1, Nov. 13-16, 1994.
Balakrishnan, M.; Pearlman, W.A.; Lu, L., “Variable-rate tree-structured vector quantizers,” Information Theory, IEEE Transactions on , vol. 41, No. 4, pp. 917-930, Jul. 1995.
Ping Wah Wong, “Entropy-Constrained Halftoning Using Multipath Tree Coding,” IEEE Transaction on Image Processing vol. 6, No. 11, Nov. 1997.
Written Opinion of the International Searching Authority for PCT/CA2006/001558.
International Search Report for PCT/CA2006/001558.
U. Rauschenbach, “Compression of palettized images with progressive coding of the color information,” in Proc. SPIE Visual Communications and Image Processing, Perth, Australia, Jun. 2000, vol. 4067.
X. Chen, S. Kwong, and J. Feng, “A new compression scheme for color-quantized images,” IEEE Transactions on Circuits and System for Video Technology, vol. 12, No. 10, pp. 904-908, Oct. 2002.
M. Orchard and C. Bauman, “Color quantization of images,” IEEE Transactions on Signal Processing, vol. 39, No. 12, pp. 2677-2690, Dec. 1991.
Y. Linde, A. Buzo, and R. Gray, “An algorithm for vector quantizer design,” IEEE Trans. Communications, vol. COM-28, No. 1, pp. 84-95, Jan. 1980.
P. Chou, T. Lookabaugh, and R. Gray, “Entropy-constrained vector quantization,” IEEE Trans. Acous., Speech, and Signal Processing, vol. 37, No. 1, pp. 31-42, Jan. 1989.
P. Chou and T. Lookabaugh, “Conditional entropy constrained vector quantization of Linear Predictive Coefficients,” IEEE, 1990, pp. 197-200.
A. Buzo, A. Gray, Jr., R. Gray, and J. Markel, “Speech coding based upon vector quantization,” IEEE Trans. Acous., Speech, and Signal Processing, vol. ASSP-28, No. 5, pp. 562-574, Oct. 1980.
E. Riskin, and R. Gray, “A greedy tree growing algorithm for the design of variable rate vector quantizers,” IEEE Transactions on Signal Processing, vol. 39, No. 11, pp. 2055-2507, Nov. 1991.
M. Balakrishnan, W. Pearlman, and L. Lu, “Variable-rate tree-structured vector quantizers,” IEEE Trans. Information Theory, vol. 41, No. 4, pp. 917-930, Jul. 1995.
Supplementary European Search Report for European Application No. 06790725.3.
Supplementary European Search Report for European Application No. 06790730.3.
Effros M Ed—Storer J A et al: “Practical multi-resolution source coding: TSVQ revisited”, Data Compression Conference, 1998, DCC '98, Mar. 30, 1998, pp. 53-62.
Gersho et al: “Vector Quantization and Signal Compression”, Vector Quantization and Signal Compression, Boston, Kluwer, US, Jan. 1, 1991, pp. 352-355.
Chadda N. et al: “Color Quantization of Images Based on Human Vision Perception”, Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, vol. V, Apr. 19, 1994, pp. 89-92.
Guillope V.: Conditional Entropy-Constrained Vector Quantization of Chromatic Information in Document Images, retrieved from Internet: URL:http://www.site.uottawa.ca/school/research/viva/theses/Guillope—thesis.pdf; Jun. 2002.
Office Action issued in connection with U.S. Appl. No. 11/534,942, mailed on Oct. 1, 2009.
RJ Barrilleaux, R. Hinkle, and S. Wells, “Efficient vector quantization for color image encoding”, Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP'87, vol. 12, pp. 740-743, Apr. 1987.
I. Ashdown, “Octree color quantization,” C/C++ Users Journal, vol. 13, No. 3, pp. 31-43, 1994.
X. Wu, “Yiq vector quantization in a new color palette architecture,” IEEE Trans. on Image Processing, vol. 5, No. 2, pp. 321-329, 1996.
L. Velho, J. Gomes, and M.V.R. Sobreiro, “Color image quantization by pairwise clustering,” Proc. Tenth Brazilian Symp. Comput. Graph. Image Process., L. H. de Figueiredo and M. L.Netto, Eds. Campos do Jordao, Spain, pp. 203-210, 1997.
S. Wan, P. Prisinkiewicz, and S. Wong, “Variance-based color image quantization for frame buffer display,” Res. Appl., vol. 15, pp. 52-58, 1990.
A. Zaccarin and B. Liu, “A novel approach for coding color quantized image,” Image Processing, IEEE Transactions on, vol. 2, No. 4, pp. 442-453, Oct. 1993.
N.D. Memon and A. Venkateswaran, “On ordering color maps for lossless predictive coding, ” IEEE Transactions on Image Processing, vol. 5, No. 11, pp. 1522-1527, 1996.
D.A. Huffman, “A method for the construction of minimum-redundancy codes,” Proc. IRE, vol. 40, No. 9, pp. 1098-1101, 1952.
J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. on Information Theory, vol. 23, pp. 337-343, 1977.
I. H. Witten, M. Neal, and J.G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, vol. 30, pp. 520-540, Jun. 1987.
E.-H. Yang and J.C. Kieffer, “Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform—part one: Without context models,” IEEE Trans. on Information Theory, vol. 46, No. 3, pp. 755-777, May 2000.
J.C. Kieffer and E.-H. Yang, “Grammar based codes: A new class of universal lossless source codes,” IEEE Trans. on Information Theory, vol. 46, No. 3, pp. 737-754, May 2000.
E.-H. Yang and D.-K. He, “Efficient Universal Lossless Data Compression Algorithms Based on a Greedy Sequential Grammar Transform-Part Two: Within Context Models”, IEEE Trans. on Information Theory, vol. 49, pp. 2874-2894, 2003.
J. Miano, “Compressed image file formats: Jpeg, png, gif, xbm, bmp,” ACM Press, 2000.
Z. Zhang, “Variable rate trellis source encoding,” IEEE Trans. on Information Theory, vol. 45, No. 2, pp. 586-608, Mar. 1999.
E.-H. Yang, Z. Zang. and T. Berger, “Fixed-slope universal lossy data compression,” IEEE Trans. on Information Theory, vol. 43, No. 5, pp. 1465-1476, Sep. 1997.
Written Opinion issued in connection with corresponding PCT application PCT/CA2006/001564, mailed on Jan. 2, 2007.
Wang Longji
Yang En-hui
Bereskin & Parr LLP / S.E.N.C.R.L., s.r.l.
Patel Nirav G
SlipStream Data Inc.
Werner Brian P
LandOfFree
Method, system and computer program product for providing... 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, system and computer program product for providing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system and computer program product for providing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2710940