Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2011-03-08
2011-03-08
Mehta, Bhavesh M (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
Reexamination Certificate
active
07903893
ABSTRACT:
A method, system and computer program product are provided for progressively encoding a digitized color image using a data processing system, the digitized color image being provided by assigning each of M distinct colors to at least one pixel in a set of pixels. This involves initializing and growing a tree structure by selecting a leaf node to become a non-leaf node linked to two new leaf nodes based on an associated achievable cost, wherein the associated achievable cost is based on 1) a determined associated change in distortion resulting from turning the leaf node into the non-leaf node linked to the two new leaf nodes; and 2) a determined associated increase in entropy rate resulting from turning the leaf node into the non-leaf node linked to the two new leaf nodes.
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.
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.
Guillope V.: Conditional Entropy-Constrained Vector Quantization of Chromatic Information in Document Images, retrieved from Internet: URL:http:I/www.site.uottawa.calschool/researchlviva/theses/Guillope—thesis.pdf; Jun. 2002.
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.
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/001564.
International Search Report for PCT/CA2006/001564.
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. Bouman, “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.
Office Action issued in connection with U.S. Appl. No. 11/534,956, mailed on Oct. 5, 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.
Mehta Bhavesh M
Patel Nirav G
SlipStream Data Inc.
LandOfFree
Method, system and computer program product for entropy... 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 entropy..., 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 entropy... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2700112