Results 1 to 19 of 19

Thread: Two dimentional Multimedia preprocessor

  1. #1
    Member chornobyl's Avatar
    Join Date
    May 2008
    Location
    ua/kiev
    Posts
    153
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Two dimentional Multimedia preprocessor

    I got an idea about preprocessing multimedia data this way:
    -choose some pixel
    -select second pixel with closest color
    among his 4 (maybe more) neighbours
    -write addictional data about the choise to 2bit stream

    As a resul we'll have two streams:
    slowly changing 8bit data which could de easy compressed
    addictional 2bit data which is not so easy but still compressible

    Also this may be applied to 1,2,3 and more dimentional data as well as bitdepth

    I would be glad to hear your opinions about this
    sad but my skills not allow me to test it myself

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    Switching algorithms like that introduce some redundancy,
    so it won't be really efficient.
    By redundancy I mean that it would be possible to decode
    the same pixel from 4 different codes.
    With "switching schemes" like that its always possible to
    improve compression by transforming them into "mixing schemes"
    (by removing the redundancy).
    For that you have to subdivide the interval (arithmetic coder's interval)
    into subintervals per each coding choice, proportional to the probability
    of that choice, and then merge the subintervals corresponding to the
    same pixel value.
    But its up to you how to make it fast
    It might be more practical to make a contextual predictor... actually
    PNG does have something like that ("filters"), not very adaptive though.

  3. #3
    Member chornobyl's Avatar
    Join Date
    May 2008
    Location
    ua/kiev
    Posts
    153
    Thanks
    0
    Thanked 0 Times in 0 Posts
    >By redundancy I mean that it would be possible to decode the same pixel >from 4 different codes.
    then how would decompressor decode it from 1 single code?

    >With "switching schemes" like that its always possible to improve >compression by transforming them into "mixing schemes" (by removing the >redundancy).

    remove redutancy from that "service stream" yep,
    and how much mixing could squeze out of that 2bits

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    > then how would decompressor decode it from 1 single code?

    I actually explained how.
    By summing the probabilities of different codes corresponding
    to the same decoded data.
    Actually, algorithms like you explained are very simple cases
    where redundancy really can be removed.
    While there're still algorithms like LZ which have a similar
    redundancy, but cannot be "fixed" that easily, as string
    probabilities have to be merged there and its complex and slow.
    Another, even more complicated case is spectral transformations
    (like DCT in jpeg). DCT implementations are usually not bijective
    even without quantization, so the only precise way to work with
    them is imho by enumerating all the possible outputs from all the
    possible spectral sets.

    > remove redutancy from that "service stream" yep,

    I meant removing whole "service stream".
    But there's also another way.
    You can mask the delta values for different bases
    in such a way that there won't be alternate codes
    for the same decoder output.
    This is a PPM-like approach and its usually better
    than keeping the redundancy, but worse than mixing.

    > and how much mixing could squeze out of that 2bits

    Up to 2 bits, I guess, but of course that depends on
    data properties.
    To get some estimation you can compare eg. Shkarin's
    BMF with png, or PPMD vs LZMA on raw image data.

  5. #5
    Member chornobyl's Avatar
    Join Date
    May 2008
    Location
    ua/kiev
    Posts
    153
    Thanks
    0
    Thanked 0 Times in 0 Posts
    >DCT implementations are usually not bijective even without quantization
    imho their precision is limited to ~12bit for 8 bit data, (ijg do so) if i remember right
    What precision need to make it losless(bijective), i thought 16bit int is enough but now i'm doubt about that.

    >To get some estimation you can compare eg. Shkarin's BMF with png, or >PPMD vs LZMA on raw image data.

    tested on some drawing scans
    Code:
      size  c.time 
     1953439   5 6-o2.7z
     1955696   4 6-o3.7z
     1960722   5 6-o4.7z
     1985729   7 6-o8.7z
     2218561 144 6-lz.7z
    56431320     6.tif
    
     4639565   6 4-o3.7z
     4643738   8 4-o4.7z
     4676973   4 4-o2.7z
     4716066  15 4-o8.7z
     5328316 178 4-lz.7z
    56433616     4.tif
    Last edited by chornobyl; 28th September 2008 at 22:06.

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    > > DCT implementations are usually not bijective even
    > > without quantization
    >
    > imho their precision is limited to ~12bit for 8 bit data,
    > (ijg do so) if i remember right

    There might be clipping. DCT is a sum of x[i]*cos()
    so it looks like 15 bits (8+log2(8*+1) would be
    a rough upper bound.

    > What precision need to make it losless(bijective),

    Lossless is one thing (x=iDCT(DCT(x)), but bijectivity
    is necessary to avoid redundancy (one-to-one mapping).
    If transformation is lossless, it doesn't mean that its not redundant.

    > i thought 16bit int is enough but now i'm doubt about that.

    Well, I have a lossless DCT-based audio codec which transforms
    16-bit samples to 32-bit coefficients and back.
    But its not only a matter of precision. Depending on implementation,
    it might be lossy even with infinite precision, if rounding
    is wrong.

    > > To get some estimation you can compare eg. Shkarin's BMF
    > > with png, or PPMD vs LZMA on raw image data.
    >
    > tested on some drawing scans

    Yeah, something like that.

  7. #7
    Member chornobyl's Avatar
    Join Date
    May 2008
    Location
    ua/kiev
    Posts
    153
    Thanks
    0
    Thanked 0 Times in 0 Posts
    >but bijectivity is necessary to avoid redundancy (one-to-one mapping)
    if i get right bijective compressor have unique output for every input
    even more, if compressor:
    for 2 intputs got 1 output=lossy
    for 1 input got 2 outputs=redutant
    for 2 input got 2 output=optimal(bijective)

    is it true that bijective compressor could de/compress anything?

    >Well, I have a lossless DCT-based audio codec which transforms 16-bit >samples to 32-bit coefficients and back.
    i mean 16bit for 8bit input and of course 32bit for 16bit (as in your case)
    And how good is it compress audio?

    >But its not only a matter of precision. Depending on implementation, it >might be lossy even with infinite precision, if rounding is wrong.

    well yes badly constructed program could destroy benefits of any algorithm
    Last edited by chornobyl; 29th September 2008 at 13:37.

  8. #8
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    > > but bijectivity is necessary to avoid redundancy (one-to-one mapping)
    >
    > if i get right bijective compressor have unique output for every input

    And vice versa.
    http://en.wikipedia.org/wiki/Bijection

    > > But its not only a matter of precision. Depending on
    > > implementation, it might be lossy even with infinite
    > > precision, if rounding is wrong.
    >
    > well yes every badly constructed program could destroy
    > benefits of any algorithm

    This is not the case. Algorithm description using traditional
    infinite-precision maths is the cause of problems here.

  9. #9
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    > is it true that bijective compressor could de/compress anything?

    It can transform anything.
    But only data which fits the model is compressed.
    Also its interesting how some unique tricks are required to stabilize
    the output of bijective decompressor applied to random data
    (basically, explicit randomization is required to avoid infinite
    expansion of some common samples).

    > > Well, I have a lossless DCT-based audio codec
    > And how good is it compress audio?

    Hardly compresses at all

  10. #10
    Member
    Join Date
    Jun 2008
    Location
    L?vis, Canada
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Shelwien View Post
    There might be clipping. DCT is a sum of x[i]*cos()
    so it looks like 15 bits (8+log2(8*+1) would be
    a rough upper bound.
    11 bits (8 + log2(). I explained how to do a lossless DCT here:
    http://groups.google.ca/group/comp.c...c0db6605a14b19

    After that, ladder operators can be used. This uses the property that the matrix
    [1 a]
    [0 1]
    is invertible over the integers.

  11. #11
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    Why, thanks.
    I don't really have much experience with spectral transforms - had been
    mostly using some libraries.
    So, do you say that you know how to design a bijective DCT?
    What about 1D DCT with N=1024? MDCT?
    I see some clipping in your code (pixels?). How's that lossless?
    Also its quite reasonable that the transform would be lossless
    with integer coefficients, if you can get an integer inverse matrix.
    But how far's that from real DCT then? More so with only 7bit coefficients...

  12. #12
    Member
    Join Date
    Jun 2008
    Location
    L?vis, Canada
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Shelwien View Post
    Why, thanks.
    I don't really have much experience with spectral transforms - had been
    mostly using some libraries.
    So, do you say that you know how to design a bijective DCT?
    Yes. Any orthonormal transformation can be made lossless because any orthonormal matrix can be composited from plane rotations. Any plane rotation can be composited from three matrices of the form,
    [1 a]
    [0 1]

    Suppose this matrix is applied to a vector [x y]. In general, a will be real. This can be done as,
    x += round(a * y)
    The inverse of this is,
    x -= round(a * y)

    This is the technique I use in libima.

    What about 1D DCT with N=1024? MDCT?
    The 2D case is easier because much of the work can be done using additions and shifts (see my posts in the thread). In 1D you have a choice between doing lots of multiplications and have all the coefficients normalised. Or starting with the S transformation as a base, in which case the coefficients will have different normalisations. Duno.

    I see some clipping in your code (pixels?). How's that lossless?
    What are you refering to? I gave a proof of losslessness. Because the highest bit orders are not truncated by the shifts, the invertibility can be calculated algebraically for all but the lowest order of bits (hint: express each sample s as, s = s_e + s_o, with s_e a multiple of 2 and 0 <= s_o < 2). pixels/samples.

    But how far's that from real DCT then? More so with only 7bit coefficients...
    With real numbers, the technique I just described is exact. In the integer invertible case, I don't know. I never implemented a lossless DCT.

  13. #13
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    Well, I didn't miss anything then.
    Of course, in theory DCT is lossless (and I have a lossless MDCT-based
    audio codec which I made), but using real coefficients and rounding
    requires a lot of attention to keep it lossless and avoid redundancy
    at the same time, and it doesn't seem like there're sources of such
    functions available.

    Btw, there's a DCT-related problem which I'm especially interested in.
    That is, probability mapping.
    The idea is, basically, that while there're context correlations
    (and quantization) in DCT space, that doesn't mean that all the
    data dependencies can be tracked like that.
    So, ideally, predictions of sequential model have to be mixed with
    predictions of DCT model... which means that probability estimations
    for DCT coefficients have to be somehow mapped back to the data
    through the transform.
    So, are there any ideas on which space to select for prediction
    merging (original or spectral) and how to efficiently implement this
    mapping? Taking into account that quantized spectral values map
    to an intelval (or set?) of data values?

  14. #14
    Member
    Join Date
    Jun 2008
    Location
    L?vis, Canada
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I'll let Thomas Richter explain it:
    http://groups.google.com/group/comp....e0d15ee28a8daa

    And work out a small example. Suppose we want to have a lossless version of the 1D Haar transformation:
    [sqrt(2)/2 sqrt(2)/2]
    [-sqrt(2)/2 sqrt(2)/2]

    This is a rotation:
    [cos(theta) sin(theta)]
    [-sin(theta) cos(theta)]

    with theta = pi/4 radians. We express this as a composition of three matrices:
    [1 a][1 0][1 a] = [cos(theta) sin(theta)]
    [0 1][b 1][0 1] = [-sin(theta) cos(theta)]

    multiplying, this gives,
    a = (1 - cos(theta)) / sin(theta)
    b = - sin(theta)

    In this example,
    a = sqrt(2) - 1
    b = - sqrt(2)/2

    This gives the algorithm,
    x += round(a * y)
    y += round(b * x)
    x += round(a * y)

    To get back our original samples, we invert every step in reverse order:
    x -= round(a * y)
    y -= round(b * x)
    x -= round(a * y)

    For a numerical example, we can pick [x y] = [100 0]. Doing the forward transformation:
    x = x + round(a * 0) = 100 + 0 = 100
    y = y + round(b * x) = 0 + round(-sqrt(2)/2 * 100) = -71
    x = x + round(a * y) = 100 + round( (sqrt(2) - 1) * -71) = 100 - 29 = 71

    So the transformed coefficients are [71 -71].

    The inverse transformation is,
    x = x - round(a * y) = 71 - round( (sqrt(2) - 1) * -71) = 71 + 29 = 100
    y = y - round(b * x) = -71 - round(-sqrt(2)/2 * 100) = -71 + 71 = 0
    x = x - round(a * y) = 100 - 0 = 100

    And we get [100 0].

  15. #15
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    Thanks again
    Anyway I don't understand how do I extend this to DCT of 1024 values
    (with window function and reasonable speed),
    but maybe your explanation would be of help if I give it some time.

  16. #16
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    btw, what would you recommend to use as a jpeg2000 decoder source?
    most readable one, not speed-optimized or anything?
    (For Ocarina Contest .

  17. #17
    Member
    Join Date
    Jun 2008
    Location
    L?vis, Canada
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    To do a 1D 4 DCT, first you would have to do a 1D 4 Hadamard transformation using the 4-point transformation in the first thread. This would give basis functions like this:

    ----

    -__-

    --__

    -_-_

    Then to rotate the third and fourth coefficients by an angle,
    cos(theta)/2 + sin(theta)/2 = cos(pi/ / sqrt(2)

    Writing x = sin(theta), this can be reduced to a quadratic equation.
    Last edited by Mihai Cartoaje; 4th October 2008 at 09:21. Reason: mathematical correction

  18. #18
    Member
    Join Date
    Jun 2008
    Location
    L?vis, Canada
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I don't know how much work it would be to program a lossless 1024 DCT. You could design 8 and 16 DCTs and see if there is a pattern, and/or look if the fast Fourier transform can be used.

    I only have common knowledge about Jpeg 2000 decoders.

  19. #19
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    > I don't know how much work it would be to program a lossless 1024 DCT.

    Actually I use MDCT, which is slightly different.
    And I don't really have any use for bijective DCT or MDCT currently -
    its just that it'd be convenient to have one when i'd like to play with it
    But I can send you that MDCT-based lossless codec source if you'd like
    to check it out and maybe advice something.

    > You could design 8 and 16 DCTs and see if there is a pattern,

    Thing is, I don't have a clear view of this area.
    I understand how's a working implementation works, but not quite
    recognize the possibility to apply some relevant trick for optimization.
    To learn that, once I tried to start from a dumb O(N^2) MDCT algorithm
    and fully optimize it myself. And got something very ugly after
    wasting quite a lot of time.

    > and/or look if the fast Fourier transform can be used.

    In fact, its already used. But there're lossy shifts which prevent
    it from overflowing, and other lossy transformations in a few more
    places.

Similar Threads

  1. Dict preprocessor
    By pat357 in forum Data Compression
    Replies: 5
    Last Post: 2nd May 2014, 21:51
  2. Images PreProcessor - PrePNG
    By PAQer in forum Data Compression
    Replies: 3
    Last Post: 21st May 2010, 12:21
  3. flzp, new LZP compressor/preprocessor
    By Matt Mahoney in forum Data Compression
    Replies: 13
    Last Post: 23rd June 2008, 17:24
  4. Delta: binary tables preprocessor
    By Bulat Ziganshin in forum Forum Archive
    Replies: 14
    Last Post: 1st April 2008, 09:43
  5. impresseed by RPE preprocessor
    By SvenBent in forum Forum Archive
    Replies: 6
    Last Post: 24th October 2007, 12:43

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •