Image analysis – Image compression or coding – Quantization
Reexamination Certificate
2009-10-26
2011-11-08
Bhatnagar, Anand (Department: 2624)
Image analysis
Image compression or coding
Quantization
C358S426090, C708S203000
Reexamination Certificate
active
08055088
ABSTRACT:
Novel, computationally efficient schemes for deterministic wavelet thresholding with the objective of optimizing maximum-error metrics are provided. An optimal low polynomial-time algorithm for one-dimensional wavelet thresholding based on a new dynamic-programming (DP) formulation is provided that can be employed to minimize the maximum relative or absolute error in the data reconstruction. Directly extending a one-dimensional DP algorithm to multi-dimensional wavelets results in a super-exponential increase in time complexity with the data dimensionality. Thus, novel, polynomial-time approximation schemes (with tunable approximation guarantees for the target maximum-error metric) for deterministic wavelet thresholding in multiple dimensions are also provided.
REFERENCES:
patent: 5710835 (1998-01-01), Bradley
patent: 5966465 (1999-10-01), Keith et al.
patent: 6148111 (2000-11-01), Creusere
patent: 6392705 (2002-05-01), Chaddha
patent: 6466698 (2002-10-01), Creusere
patent: 7050640 (2006-05-01), Acharya et al.
patent: 2007/0058871 (2007-03-01), Deligiannakis et al.
J. M. Hellerstein, et al., “Online Aggregation”, SIGMOD '97, Arizona, pp. 171-182.
A. Natsev et al., “Walrus: A Similarity Retrieval Algorithm for Image Databases”, SIGMOD '99 Philadelphia, PA, pp. 395-406.
K. Chakrabarti et al., “Approximate Query Processing Using Wavelets”, Proceedings of the 26th VLDB Conference, Cairo, Egypt, 2000, pp. 111-122.
Y. Matias, “Dynamic Maintenance of Wavelet-Based Histograms”, Proceedings of the 26thVLDB Conference, Cairo, Egypt, 2000.
A. Gilbert et al., “Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries”, Proceedings of the 27thVLDB Conference, Roma, Italy, 2001.
A. Deshpande et al., “Independence is Good: Dependency-Based Histogram Synopses for High Dimensional Data”, ACM SIGMOD May 21-24, 2001. Santa Barbara, CA.
M. Garafalakis and P. B. Gibbons, “Wavelet Synopses With Error Guarantees”, ACM SIGMOD 'Jun. 4-6, 2002, Madison, Wisconsin.
A. Deligiannakis and N. Roussopoulos, “Extended Wavelets for Multiple Measures”, SIGMOD 2003, Jun. 9-12, San Diego, CA, pp. 229-240.
M. Garafalakis and P. B. Gibbons, “Probabilistic Wavelet Synopses”, ACM Transactions on Database Systems, vol. 29, No. 1, Mar. 2004, pp. 43-90.
S. Guha, “A Note on Wavelet Optimization”, Sep. 8, 2004.
Garofalakis Minos N.
Kumar Amit
Alcatel Lucent
Bhatnagar Anand
Wall & Tong LLP
LandOfFree
Deterministic wavelet thresholding for general-error metrics does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deterministic wavelet thresholding for general-error metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic wavelet thresholding for general-error metrics will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4273698