Computer Science – Data Structures and Algorithms
Scientific paper
2002-05-17
IEEE Data Compression Conference (1997)
Computer Science
Data Structures and Algorithms
Scientific paper
Pattern-matching-based document-compression systems (e.g. for faxing) rely on finding a small set of patterns that can be used to represent all of the ink in the document. Finding an optimal set of patterns is NP-hard; previous compression schemes have resorted to heuristics. This paper describes an extension of the cross-entropy approach, used previously for measuring pattern similarity, to this problem. This approach reduces the problem to a k-medians problem, for which the paper gives a new algorithm with a provably good performance guarantee. In comparison to previous heuristics (First Fit, with and without generalized Lloyd's/k-means postprocessing steps), the new algorithm generates a better codebook, resulting in an overall improvement in compression performance of almost 17%.
Danskin John
Young Neal
Zhang Qin
No associations
LandOfFree
A Codebook Generation Algorithm for Document Image Compression does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Codebook Generation Algorithm for Document Image Compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Codebook Generation Algorithm for Document Image Compression will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-599060