Results 1 to 4 of 4

Math Help - Spare bin encoding/compression

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    2

    Spare bin encoding/compression

    I am looking for some kind of spare bin compression/encoding technique for histogram data.


    Here is the problem:

    Say for example I have 1024 input values which have to be categorized in to 32 bins. Each input value has a range of 0 to 255. If the input value has a range [0, 15] bin 1 is incremented by 1. If the input value has a range [16, 32], bin 2 incremented by 1..and so on..and bin 32 in incremented by 1 if the input value has a range [240, 255]. At the end if I add up all the bin counts the total adds up to 1024 (as expected). But then the worst case count for a single bin is 1024 since all the input values might be in the same range.

    If I am implementing this in hardware I need 10 bits for each bin and 32 bins ==> 32768 bits. This just grows if instead of 2^10 (i.e. 1024) input values
    I have 2^20 input values.

    So here is my question. Considering that most of the bins might be sparse bins (and the sum of all bins adds up to 1024), is there any way of representing 32 bins in a larger single bin (or a couple of bins) with some overhead for encoding/compression.

    Pls let me know if something is not clear.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by arunrm View Post
    I am looking for some kind of spare bin compression/encoding technique for histogram data.


    Here is the problem:

    Say for example I have 1024 input values which have to be categorized in to 32 bins. Each input value has a range of 0 to 255. If the input value has a range [0, 15] bin 1 is incremented by 1. If the input value has a range [16, 32], bin 2 incremented by 1..and so on..and bin 32 in incremented by 1 if the input value has a range [240, 255]. At the end if I add up all the bin counts the total adds up to 1024 (as expected). But then the worst case count for a single bin is 1024 since all the input values might be in the same range.

    If I am implementing this in hardware I need 10 bits for each bin and 32 bins ==> 32768 bits. This just grows if instead of 2^10 (i.e. 1024) input values
    I have 2^20 input values.

    So here is my question. Considering that most of the bins might be sparse bins (and the sum of all bins adds up to 1024), is there any way of representing 32 bins in a larger single bin (or a couple of bins) with some overhead for encoding/compression.

    Pls let me know if something is not clear.

    Thanks
    10 bits per bin and 32 bins looks to me like 320 bits.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2006
    Posts
    2
    Quote Originally Posted by CaptainBlack View Post
    10 bits per bin and 32 bins looks to me like 320 bits.

    RonL
    Thats right. It should be 320 bits. I don't know what I was thinking when I wrote that.

    But this just keeps growing if the no. of input values is say 2^20 and the bins is 64. A lot of bins would still be sparse. Is there any way to take advantage of the sparse bins and encode them to reduce the total no. of bits required.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by arunrm View Post
    Thats right. It should be 320 bits. I don't know what I was thinking when I wrote that.

    But this just keeps growing if the no. of input values is say 2^20 and the bins is 64. A lot of bins would still be sparse. Is there any way to take advantage of the sparse bins and encode them to reduce the total no. of bits required.

    Thanks
    If you are reasonably confident that the data will be sparse use a list
    to store the data: (BinIdent1, BinTotal1), (BinIdent2, BinTotal2) ..

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding stretch or compression
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 30th 2010, 03:32 AM
  2. Spare time brain teasers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: August 17th 2010, 08:25 PM
  3. Quartics: When you just don't have time to spare
    Posted in the Math Software Forum
    Replies: 1
    Last Post: February 17th 2009, 08:47 PM
  4. horizontal compression / stretch
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: September 29th 2008, 08:04 PM
  5. Replies: 1
    Last Post: September 17th 2008, 10:08 AM

Search Tags


/mathhelpforum @mathhelpforum