{'fraction_non_alphanumeric': 0.02655721873491067, 'fraction_numerical': 0.00386286817962337, 'mean_word_length': 5.040816326530612, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sparse image representation via combined transforms

We consider sparse image decomposition, in the hope that a sparser decomposition of an image may lead to a more efficient method of image coding or compression. Recently, many transforms have been proposed. Typically, each of them is good at processing one class of features in an image but not other features. For example, the 2-D wavelet transform is good at processing point singularities and patches in an image but not linear singularities, while a recently proposed method—the edgelet-like transform—is good for linear singularities, but not for points. Intuitively, a combined scheme may lead to a sparser decomposition than a scheme using only a single transform. Combining several transforms, we get an overcomplete system or dictionary. For a given image, there are infinitely many ways to decompose it. How to find the one with the sparsest coefficients? We follow the idea of Basis Pursuit—finding a minimum 1 norm solution. Some intuitive discussion and theoretical results show that this method is optimal in many cases. A big challenge in solving a minimum 1 norm problem is the computational complexity. In many cases, due to the intrinsic nature of the high-dimensionality of images, finding the minimum 1 norm solution is nearly impossible. We take advantage of the recent advances in convex optimization and iterative methods. Our approach is mainly based on two facts: first, we have fast algorithms for each transform; second, we have efficient iterative algorithms to solve for the Newton direction. The numerical results (to some extent) verify our intuitions, in the sense that: [1] the combined scheme does give sparser representations than a scheme applying only a single transform; [2] each transform in the combined scheme captures the features that this transform is good at processing. (Actually, [2] is an extension of [1].) With improved efficiency in numerical algorithms, this approach has the promise of producing more compact image coding and compression schemes than existing ones.