Automatically assigned DDC number: 005746

Manually assigned DDC number: 005746

Number of references: 8

Title: 2D-Pattern Matching Image and Video Compression: Theory, Algorithms, and Experiments

Author:

Author:

Author:

Subject: Marc Alzina,Wojciech Szpankowski,Ananth Grama 2D-Pattern Matching Image and Video Compression: Theory, Algorithms, and Experiments

Description: We propose a lossy data compression scheme based on an approximate two dimensional pattern matching (2D-PMIC) extension of the Lempel-Ziv lossless scheme. We apply the scheme to image and video compression and report on our theoretical and experimental results. Theoretically, we show that the so called fixed database model leads to suboptimal compression. Furthermore, the compression ratio of this model is as low as the generalized entropy that we define in the paper. We use this model for our video compression scheme and present experimental results. For image compression we use a growing database model for which we provide an approximate analysis. The implementation of 2D-PMIC is a challenging problem from the algorithmic point of view. We use a range of novel techniques and data structures such as k-d trees, generalized run length coding, adaptive arithmetic coding, and variable and adaptive maximum distortion level to achieve good compression ratios at high compression speeds. We ...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1999-01-27

Pubyear: 1999

Format: ps

Identifier: http://citeseer.ist.psu.edu/160365.html

Source: http://www.cs.purdue.edu/homes/spa/asg99.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/554004.html"   Type="article"   CiteSeer_Book="IEEE   Transactions   on   Pattern   Analysis   and   Machine   Intelligence"   CiteSeer_Volume="21"   Title="Pattern   Matching   Image   Compression:   Algorithmic   and   Empirical   Results,">

            <identifier   Org="ISBN:0387789081"   Paper_ID="/554004.html"   Extracted="0387789081"   DDC="005.746"   Normalized_DDC="005746"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:0769519164"   Paper_ID="/554004.html"   Extracted="0769519164"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:0849314704"   Paper_ID="/554004.html"   Extracted="0849314704"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:8884535263"   Paper_ID="/554004.html"   Extracted="8884535263"   DDC="621"   Normalized_DDC="621"   Normalized_Weight="0.25"   />

      </rec>

      <rec   ID="/99914.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="The   asymptotics   of   waiting   times   between   stationary   processes,"   />

      <rec   ID="/85731.html"   Type="article"   CiteSeer_Book="Information   Processing   and   Management"   CiteSeer_Volume="28"   Title="Analysis   of   Arithmetic   Coding   for   Data   Compression,">

            <identifier   Org="ISBN:0126208611"   Paper_ID="/85731.html"   Extracted="0126208611"   DDC="006.7/6"   Normalized_DDC="00676"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0792376684"   Paper_ID="/85731.html"   Extracted="0792376684"   DDC="005.74/6"   Normalized_DDC="005746"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818624477"   Paper_ID="/85731.html"   Extracted="0818624477"   />

            <identifier   Org="ISBN:0818681837"   Paper_ID="/85731.html"   Extracted="0818681837"   DDC="621.367"   Normalized_DDC="621367"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0849316316"   Paper_ID="/85731.html"   Extracted="0849316316"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0849335566"   Paper_ID="/85731.html"   Extracted="0849335566"   DDC="005.74/6"   Normalized_DDC="005746"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0898713293"   Paper_ID="/85731.html"   Extracted="0898713293"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1558605703"   Paper_ID="/85731.html"   Extracted="1558605703"   DDC="651.5/0285574"   Normalized_DDC="65150285574"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1581133839"   Paper_ID="/85731.html"   Extracted="1581133839"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1584883138"   Paper_ID="/85731.html"   Extracted="1584883138"   DDC="005.74/6"   Normalized_DDC="005746"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540664084"   Paper_ID="/85731.html"   Extracted="3540664084"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.1"   />

      </rec>

      <rec   ID="/67490.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="An   implementable   lossy   version   of   the   Lempel-Ziv   algorithm   --   Part   II:   Optimality   for   sources   with   memory,"   />

      <rec   ID="/32721.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   the   5th   Annual   Symposium   on   Combinatorial   Pattern   Matching"   CiteSeer_Volume=""   Title="A   Lossy   Data   Compression   Based   on   String   Matching:   Preliminary   Analysis   and   Suboptimal   Algorithms,">

            <identifier   Org="ISBN:0387580948"   Paper_ID="/32721.html"   Extracted="0387580948"   DDC="006.4/01/5116"   Normalized_DDC="0064015116"   Normalized_Weight="1.0"   />

      </rec>

      <rec   ID="/9842.html"   Type="article"   CiteSeer_Book="IEEE   Trans   Inf   Theory"   CiteSeer_Volume="43"   Title="A   Suboptimal   Lossy   Data   Compression   Based   on   Approximate   Pattern   Matching,">

            <identifier   Org="ISBN:0818681322"   Paper_ID="/9842.html"   Extracted="0818681322"   DDC="003/.54"   Normalized_DDC="00354"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:3540403175"   Paper_ID="/9842.html"   Extracted="3540403175"   DDC="005.7/13"   Normalized_DDC="005713"   Normalized_Weight="0.5"   />

      </rec>

      <rec   ID="/577550.html"   Type="article"   CiteSeer_Book="IEEE   Transactions   on   Information   Theory"   CiteSeer_Volume="23"   Title="A   Universal   Algorithm   for   Sequential   Data   Compression,">

            <identifier   Org="ISBN:0121197921"   Paper_ID="/577550.html"   Extracted="0121197921"   DDC="621.36/7"   Normalized_DDC="621367"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0387301623"   Paper_ID="/577550.html"   Extracted="0387301623"   DDC="518.103"   Normalized_DDC="518103"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0387952608"   Paper_ID="/577550.html"   Extracted="0387952608"   DDC="005.74/6"   Normalized_DDC="005746"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0471460540"   Paper_ID="/577550.html"   Extracted="0471460540"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0780320166"   Paper_ID="/577550.html"   Extracted="0780320166"   />

            <identifier   Org="ISBN:0821800868"   Paper_ID="/577550.html"   Extracted="0821800868"   DDC="005.7"   Normalized_DDC="0057"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0824722868"   Paper_ID="/577550.html"   Extracted="0824722868"   />

            <identifier   Org="ISBN:0824742516"   Paper_ID="/577550.html"   Extracted="0824742516"   DDC="621.36/03"   Normalized_DDC="6213603"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:084931173X"   Paper_ID="/577550.html"   Extracted="084931173X"   DDC="621.382/03"   Normalized_DDC="62138203"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0849326494"   Paper_ID="/577550.html"   Extracted="0849326494"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354028558X"   Paper_ID="/577550.html"   Extracted="354028558X"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540403116"   Paper_ID="/577550.html"   Extracted="3540403116"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540441263"   Paper_ID="/577550.html"   Extracted="3540441263"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540614222"   Paper_ID="/577550.html"   Extracted="3540614222"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540625925"   Paper_ID="/577550.html"   Extracted="3540625925"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540664084"   Paper_ID="/577550.html"   Extracted="3540664084"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540708804"   Paper_ID="/577550.html"   Extracted="3540708804"   />

      </rec>

      <rec   ID="/580359.html"   Type="article"   CiteSeer_Book="IEEE   Transactions   on   Information   Theory"   CiteSeer_Volume="24"   Title="Compression   of   Individual   Sequences   via   Variable-Rate   Coding,">

            <identifier   Org="ISBN:0262100924"   Paper_ID="/580359.html"   Extracted="0262100924"   DDC="572.8/01/51"   Normalized_DDC="57280151"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0306445441"   Paper_ID="/580359.html"   Extracted="0306445441"   DDC="003/.54"   Normalized_DDC="00354"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0387953876"   Paper_ID="/580359.html"   Extracted="0387953876"   DDC="005.8"   Normalized_DDC="0058"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:047122202X"   Paper_ID="/580359.html"   Extracted="047122202X"   DDC="004.67/8/03"   Normalized_DDC="00467803"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0471460540"   Paper_ID="/580359.html"   Extracted="0471460540"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0471484229"   Paper_ID="/580359.html"   Extracted="0471484229"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0521880688"   Paper_ID="/580359.html"   Extracted="0521880688"   DDC="518/.0285"   Normalized_DDC="5180285"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0780339576"   Paper_ID="/580359.html"   Extracted="0780339576"   />

            <identifier   Org="ISBN:0821804146"   Paper_ID="/580359.html"   Extracted="0821804146"   DDC="510   s"   Normalized_DDC="51"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:0821842560"   Paper_ID="/580359.html"   Extracted="0821842560"   />

            <identifier   Org="ISBN:0824722906"   Paper_ID="/580359.html"   Extracted="0824722906"   />

            <identifier   Org="ISBN:0824729056"   Paper_ID="/580359.html"   Extracted="0824729056"   />

            <identifier   Org="ISBN:0898713293"   Paper_ID="/580359.html"   Extracted="0898713293"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:1584884657"   Paper_ID="/580359.html"   Extracted="1584884657"   DDC="621.384"   Normalized_DDC="621384"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540000097"   Paper_ID="/580359.html"   Extracted="3540000097"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540403116"   Paper_ID="/580359.html"   Extracted="3540403116"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540625925"   Paper_ID="/580359.html"   Extracted="3540625925"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540708804"   Paper_ID="/580359.html"   Extracted="3540708804"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="2D-Pattern   Matching   Image   and   Video   Compression:   Theory,   Algorithms,   and   Experiments">

            <identifier   Org="ISBN:0849314704"   Paper_ID="SELF"   Extracted="0849314704"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:3540281010"   Paper_ID="SELF"   Extracted="3540281010"   DDC="005.7/3"   Normalized_DDC="00573"   Normalized_Weight="0.5"   />

      </rec>

</references_metadata>