Faster version of dec2bin function for converting many elements?

Question

I am reading a bitmap file and converting each of the RGB values ranging from 0 to 255 to binary.

So a 240 by 320 bitmap will have 230400 RGB values to convert. The original dec2bin function was too slow, so I wrote my own as I know my value will always be between 0 to 255.

But going through 230400 values will still take approx. 6sec on my machine, and a single colour bitmap will take about 2.3sec.

Is there anyway to speed things up to be under 1sec or even better 0.5sec, as every msec counts for my application?

Here is my code:

function s = dec2bin_2(input)

if input == 255
    s = [1;1;1;1;1;1;1;1];
    return;
end

s = [0;0;0;0;0;0;0;0];

if input == 0
    return;
end

if input >= 128
    input = input - 128;
    s(1) = 1;
    if input == 0
        return;
    end
end

if input >= 64
    input = input - 64;
    s(2) = 1;
    if input == 0
        return;
    end
end

if input >= 32
    input = input - 32;
    s(3) = 1;
    if input == 0
        return;
    end
end

if input >= 16
    input = input - 16;
    s(4) = 1;
    if input == 0
        return;
    end
end

if input >= 8
    input = input - 8;
    s(5) = 1;
    if input == 0
        return;
    end
end

if input >= 4
    input = input - 4;
    s(6) = 1;
    if input == 0
        return;
    end
end

if input >= 2
    input = input - 2;
    s(7) = 1;
    if input == 0
        return;
    else
        s(8) = 1;
    end
end
end

I was thinking if I'm not able to do it in MATLAB then maybe I'll do the conversion in C++. Is this advisable?

Thanks.

Answer 1

Can't you use bitand to get the bits directly ?

s(0) = 256 bitand input
s(1) = 128 bitand input
s(2) = 64 bitand input

etc...

Answer 2

Option #1: Loop over each pixel and use BITGET

You can loop over each pixel (or RGB value) in your image and use BITGET to get a vector of zeroes and ones. Here's an example of how to use BITGET:

>> bitget(uint8(127),8:-1:1)  % Get bits 8 through 1 for a uint8 value

ans =

    0    1    1    1    1    1    1    1

Option #2: Vectorized solution with BITGET

It's possible to create a vectorized solution where you loop over each bit instead of each pixel, performing a BITGET operation on the entire image matrix each time through the loop. The following is one such implementation:

function B = get_bits(A,N)
  % Gets the N lowest bits from each element of A
  B = zeros([size(A) 0]);
  nDims = ndims(A)+1;
  for iBit = N:-1:1
    B = cat(nDims,B,bitget(A,iBit));
  end
end

If the matrix A is 2-D (n-by-m) or 3-D (n-by-m-by-p), the matrix B will be one dimension larger. The extra dimension will be of size N with the highest bit in index 1. You can either index into this dimension to get a bit value or reshape B to a more easily visualized form. Here's an example of the usage:

>> A = uint8([126 128; 127 129]);  % A 2-by-2 matrix of uint8 values
>> B = get_bits(A,8);              % B is a 2-by-2-by-8 matrix
>> B(:,:,1)                        % Get bit 8 for each value in A

ans =

     0     1
     0     1

>> reshape(B,4,8)                  % Reshape B into a 4-by-8 matrix

ans =

     0     1     1     1     1     1     1     0
     0     1     1     1     1     1     1     1
     1     0     0     0     0     0     0     0
     1     0     0     0     0     0     0     1

Answer 3

An even faster way is to use lookup tables. Since you know all the values are intensities between 0 and 255, you construct the binary equivalent of each to speed up the process.

% build table (computed once) [using gnovice option#1]
lookupTable = cell2mat(arrayfun(@(i)bitget([0:255]',9-i),1:8,'UniformOutput',0));

% random' image
I = randi(256, [240 320])-1;

% decimal to binary conversion
binI = lookupTable(I(:)+1,:);

On my machine, it took on average 0.0036329 seconds (only the conversion). Note the lookup table has almost no space overhead:

>> whos lookupTable
  Name               Size            Bytes  Class    Attributes
  lookupTable      256x8              2048  uint8

Answer 4

This kind of problem (perform a per-element operation on a large array, because Matlab's built-in code is too slow) sometimes calls for a solution in Java, since Matlab runs on a JRE and converting/passing array arguments is usually a fairly fast operation.

gnovice's solution sounds like it works for you, but if you run into a situation you can't solve in pure Matlab, and you're proficient in Java, consider writing a custom JAR file. It's pretty easy. (well, a whole lot easier than trying to interface C++ to Matlab!)