This paper introduces a novel algorithm for sparse approximation in redundant dictionaries called the M-term pursuit (MTP). This algorithm decomposes a signal into a linear combination of atoms that are selected in order to represent the main signal components. The MTP algorithm provides an adaptive representation for signals in any complete dictionary. The basic idea behind the MTP is to partition the dictionary into L quasi-disjoint subdictionaries. A k-term signal approximation is then iteratively computed, where each iteration leads to the selection of M ≤ L atoms based on thresholding. The MTP algorithm is shown to achieve competitive performance with the matching pursuit (MP) algorithm that greedily selects atoms one by one. This is due to efficient partitioning of the dictionary. At the same time, the computational complexity is dramatically reduced compared to MP due to the batch selection of atoms. We finally illustrate the performance of MTP in image and video compression applications, where we show that the suboptimal atom selection of MTP is largely compensated by the reduction in complexity compared with MP.

This paper presents a highly flexible video coding scheme, based on the use of a redundant dictionary of spatio-temporal three-dimensional (3-D) functions. Directionality and anisotropic scaling are key ingredients to the spatial components, which form a rich collection of two-dimensional (2-D) visual primitives. The temporal component is tuned to capture most of the energy in the temporal signal evolution, along motion trajectories in the video sequence. The video coding scheme (MP3D) first computes motion trajectories that are eventually entropy coded and sent as side information to the decoder. It then applies a spatio-temporal decomposition along motion trajectories, using an adaptive approximation algorithm based on matching pursuit (MP). Quantized coefficients and basis function parameters are entropy-coded in a embedded stream that is constructed to respect multiple rate constraints. The geometric properties of the 2-D primitive dictionary allow for flexible spatial resolution adaptation, so that the flexible MP3D stream enables decoding at different spatio-temporal resolutions, and multiple rates. The MP3D scheme is shown to provide rate-distortion performance that are comparable with state-of-the-art schemes, such as H.264, MPEG-4, at low and medium bit rate. However, the use of a redundant dictionary is penalizing at high coding rate, which makes the MP3D algorithm mostly interesting for low rate applications, or as a flexible base layer in hierarchical coding schemes.

This paper introduces a sparse signal representation algorithm in redundant dictionaries, called the M-term pursuit (MTP), with an application to image representation and scalable coding. The MTP algorithm belongs to the framework of the matching pursuit (MP) (S. Mallat and Z. Zhang, 1993); it expands the image into a linear combination of atoms, selected from a large collection of spatial atoms. The MTP relies on the concept of dictionary partitioning, i.e., as splitting the dictionary into L disjoint sub-dictionaries, each carrying some specific information. Then, it iteratively finds a K-term approximation, by selecting M atoms at a time, where M /spl les/ L, followed by an orthogonal projection. The approximation performances of the MTP algorithm have been shown to yield comparable results with those of the matching pursuit. However, it presents the advantage of a reduced computational complexity. For progressive image compression, an embedded quantization and coding step is applied on the series of obtained atoms based on the subset approach (A. Rahomoune, et al, 2004); to generate a flexible bitstream. The performances of the MTP image coder are finally shown to compare favorably against those of the state-of-the-art JPEG-2000 scheme, in terms of rate-distortion characteristics.

The paper describes a novel video coding scheme based on a three-dimensional matching pursuit algorithm. In addition to good compression performance at low bit rates, the proposed coder allows for flexible spatial, temporal and rate scalability thanks to its progressive coding structure. The matching pursuit algorithm generates a sparse decomposition of a video sequence in a series of spatio-temporal atoms, taken from an overcomplete dictionary of three-dimensional basis functions. The dictionary is generated by shifting, scaling and rotating two different mother atoms in order to cover the whole frequency cube. An embedded stream is then produced from the series of atoms. They are first distributed into sets through the set-partitioned position map algorithm (SPPM) to form the index-map, inspired from bit plane encoding. Scalar quantization is then applied to the coefficients which are finally arithmetic coded. A complete MP3D codec has been implemented, and performances are shown to compare favorably to other scalable coders like MPEG-4 FGS and SPIHT-3D. In addition, the MP3D streams offer an incomparable flexibility for multiresolution streaming or adaptive decoding.