Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2011-07-12
2011-07-12
Ahmed, Samir A (Department: 2624)
Image analysis
Image compression or coding
Lossless compression
C382S232000, C382S233000, C382S246000, C382S250000, C382S251000, C375S240010, C375S240030
Reexamination Certificate
active
07978923
ABSTRACT:
A sequence of n coefficients is compressed by determining a cost-determined sequence of n coefficient indices represented by a cost-determined sequence of (run, index derivative) pairs under a given quantization table and run-index derivative coding distribution, wherein each sequence of (run, index derivative) pairs defines a corresponding sequence of coefficient indices such that (i) each index in the corresponding sequence of coefficient indices is a digital number, (ii) the corresponding sequence of coefficient indices includes a plurality of values including a special value, and (iii) each (run, index derivative) pair defines a run value representing a number of consecutive indices of the special value, and an index-based value derived from a value of the index following the number of consecutive indices of the special value. This involves (a) using the given quantization table and run-index derivative coding distribution to formulate a cost function for a plurality of possible sequences of (run, index derivative) pairs; (b) applying the cost function to each possible sequence in the plurality of possible sequences of (run, index derivative) pairs to determine an associated cost; and, (c) selecting the cost-determined sequence of (run, index derivative) pairs from the plurality of possible sequences of (run, index derivative) pairs based on the associated cost of each of the plurality of possible sequences of (run, index derivative) pairs; and encoding the corresponding selected cost-determined sequence of (run, index derivative) pairs using entropy coding based on a run-index derivative coding distribution.
REFERENCES:
patent: 5682152 (1997-10-01), Wang et al.
patent: 5734755 (1998-03-01), Ramchandran et al.
patent: 5926222 (1999-07-01), Nickerson
patent: 6167162 (2000-12-01), Jacquin et al.
patent: 6212302 (2001-04-01), Honsinger et al.
patent: 6349151 (2002-02-01), Jones et al.
patent: 6356668 (2002-03-01), Honsinger et al.
patent: 6507616 (2003-01-01), Ryu
patent: 6891889 (2005-05-01), Kim et al.
patent: 6925120 (2005-08-01), Zhang et al.
patent: 6999432 (2006-02-01), Zhang et al.
patent: 7010037 (2006-03-01), Ye et al.
patent: 7742643 (2010-06-01), Yang et al.
patent: 2003/0179937 (2003-09-01), Brake et al.
patent: 2004/0028131 (2004-02-01), Ye et al.
patent: 2004/0120398 (2004-06-01), Zhang et al.
patent: 2004/0179606 (2004-09-01), Zhou et al.
patent: 2005/0015248 (2005-01-01), Kadono et al.
patent: 2006/0013300 (2006-01-01), Han
patent: 2007/0047639 (2007-03-01), Ye
patent: 1453208 (2002-11-01), None
patent: 1333679 (2004-04-01), None
W.B. Pennebaker et al., “JPEG Still Image Data Compression Standard”, Kluwer Academic Publishers, Norwell, Massachusetts.
G.K. Walace, “The JPEG Still Picture Compression Standard”, Communications of the ACM, 1991, pp. 31-44, vol. 34, No. 4.
A.C. Hunget al., “Optimal Quantizer Step Sizes for Transform Coders”, Computer Systems Laboratory, IEEE, 1991 pp. 2621-2624.
S.W. Wu, et al., “Rate-Constrained Picture-Adaptive Quantization for JPEG Baseline Coders”, IEEE, Department of Electrical and Computer Engineering, 1993, pp. 389-392.
V. Ratnakar, et al., “RD-OPT: An Efficient Algorithm for Optimizing DCT Quantization Tables”, IEEE, 1995, pp. 332-341.
V. Ratnakar, et al. “An Efficient Algorithm for Optimizing DCT Quantization”, IEEE Transactions on Image Processing, vol. 9, No. 2., Feb. 2000, pp. 267-270.
K. Ramchandran, et al. “Rate-Distortion Optimal Fast Thresholding with Complete JPEG/MPEG Decoder Compatibility”, IEEE Transactions on Image Processing, vol. 3, No. 5, Sep. 1994, pp. 700-704, New York, USA.
M. Crouse, et al., “Joint Thresholding and Quantizer Selection for Transform Image Coding: Entropy-Constrained Analysis and Applications to Baseline JPEG”, IEEE Transactions on Image Processing, Feb. 1997, vol. 6, No. 2, pp. 285-297.
M. Crouse, et al. “Joint Thresholding and Quantizer Selection for Decoder-Compatible Baseline JPEG”, IEEE, 1995, pp. 2331-2334.
E.H. Yang, et al. “Fixed-Slope Universal Lossy Data Compression”, IEEE Transactions on Information Theory, Sep. 1997, vol. 43, No. 5, pp. 1465-1475.
E.H. Yang, et al. “Variable-Rate Trellis Source Encoding”, IEEE Transactions on Information Theory, Mar. 1999, vol. 45, No. 2, pp. 586-608.
J.M. Shapiro, “Embedded Image Coding Using Zerotrees of Wavelet Coefficients”, IEEE Transactions on Information Theory, Dec. 1993, vol. 41, No. 12, pp. 3445-3462.
A. Said, et al., “A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees”, IEEE Transactions on Circuits and Systems for Video Technology, Jun. 1996, vol. 6, No. 3, pp. 243-250.
D. Taubman, et al. “High Performance Scalable Image Compression with EBCOT”, IEEE Transactions on Image Processing, Jul. 2000, vol. 9, No. 7, pp. 1158-1170.
X. Wu, “High-Order Context Modeling and Embedded Conditional Entropy Coding of Wavelet Coefficients for Image Compression”, IEEE, 1998, Department of Computer Science, University of Western Ontario, pp. 1378-1382.
C. Tu, et al., “Adaptive Runlength Coding”, IEEE Signal Processing Letters, Mar. 2003, vol. 10, No. 3, pp. 61-64.
C. Tu, et al., “Context-Based Entropy Coding of Block Transform Coefficients for Image Compression”, IEEE Transactions on Image Processing, Nov. 2002, vol. 11, No. 11, pp. 1271-1283.
A. Ortega, et al., “Optimal Trellis-Based Buffered Compression and Fast Approximations”, IEEE Transactions on Image Processing, Jan. 1994, vol. 3, No. 1, pp. 26-39.
K. Ramchadran, et al., “Bit Allocation for Dependent Quantization with Applications to Multiresolution and MPEG Video Coders”, IEEE Transactions on Image Processing, Sep. 1994, vol. 3, No. 5, pp. 533-545.
E.H. Yang, et al., “Joint Optimization of Run-Length Coding, Huffman Coding and Quantization Table With Complete Baseline JPEG Compatibility”, IEEE, 2007, vol. III, pp. 181-184.
International Search Report and Written Opinion for PCT/CA2005/001084 dated Nov. 2, 2005.
International Search Report and Written Opinion for Application No. PCT/CA2004/001557 dated Mar. 9, 2005.
European Patent Office Communication for Application No. 05763556.7 dated May 9, 2008.
Office Action for Canadian Patent Application No. 2,572,818 dated Apr. 6, 2009.
Wavelet Image Compression Construction Kit http://www.geoffdavis.net/dartmouth/wavelet/wavelet.html.
T.D. Tran, et al., “Lapped Transform via Trime-Domain Pre- and Post-Filtering”, Jun. 2003, IEEE Transactions on Signal Processing, vol. 51, No. 6, pp. 1557-1571.
Notice of Allowance for U.S. Appl. No. 11/180,513, dated Feb. 22, 2010.
Notice of Allowance for U.S. Appl. No. 11/180,513, dated Nov. 3, 2009.
Office Action for U.S. Appl. No. 11/180,513 dated May 12, 2009.
Office Action for U.S. Appl. No. 11/180,513, dated Mar. 27, 2009.
J. Wen, et al., “Trellis-Based R-D Optimal Quantization in H.263+”, Aug. 2000, IEEE Transactions on Image Processing, vol. 9, No. 8, pp. 1431-1435.
International Search Report and Written Opinion for Application No. PCT/CA2005/001084 dated Mar. 9, 2005.
International Preliminary Report on Patentability and Written Opinon for PCT/CA2005/001084 dated Jan. 25, 2007.
European Patent Office Communication under Rule 71(3) EPC for Application No. 05763556.7 dated Sep. 4, 2009.
Annex to EPO Form 2004, Communication pursuant to Rule 71(3) EPC for Application No. EP 05763556.7.
Chinese Office Action for Application No. 200580030761.0 dated Sep. 11, 2009.
European Patent Decision to Grant a European Patent pursuant to Article 97(1) EPC for Application No. 04761723.8 dated May 17, 2010.
European Patent Office Communication pursuant to Article 94(3) EPC for Application No. 04761723.8 dated Dec. 23, 2008.
European Patent Office Communication for Application No. 04761723.8 dated May 7, 2008.
European Patent Office Communication under Rule 71(3) EPC for Application No. 04
Wang Longji
Yang En-hui
Ahmed Samir A
Bayat Ali
Bereskin & Parr LLP/S.E.N.C.R.L.,S.R.L.
SlipStream Data Inc.
LandOfFree
Method, system and computer program product for optimization... 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 optimization..., 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 optimization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2679396