# how to know there is a transition in a string of binary numbers

hi, if i have a string of binary number scan from a binary image from this code

     for( int y=0; y< frame_gray.rows; y+=10){
for (int x=0;x< frame_gray.cols;x+=1){

if (frame_gray.at<uchar>(y,x)==0)
{  cout << "0 binary=" << endl;}

else
{  cout << "1 binary=" << endl;width++;}
//waitKey(0);

}

cout << "width=" << width << endl;
width=0;
cout << "new pixel line" << endl;
}


as example output is 0000000111111000000, how can i write a code to tell me there is two times of value transition 0-->1 and 1--->0? or

00001111100000111100000 there are 4 times of transition happened.

thanks

edit retag close merge delete

Sort by » oldest newest most voted

the general idea is:

1. bitwise shift to the right
2. xor with original value, so only transition bits are left
3. count remaining bits

here's a demo implementation, using std::bitset (for demo purpose), same idea works with uints, too, ofc.

#include <bitset>
bitset<24> a("00001111100000111100000");
// 000001111100000111100000
auto b = a >> 1;
// 000000111110000011110000
auto c = a ^ b;
// 000001000010000100010000
auto len = c.count();  // popcnt() , if you use integers.
// 4

more

to make it as bitset, the output as in 0000001111110000 should be converted to string then bitset? Or is it possible just to take the string from the Mat array [1x50] and convert it, into bitset to perform the operation?

Edit2:

A much simpler solution should be to just count the number of times the current value is different of the next value (demo code here).

Edit:

The size of a bitset cannot be dynamic (the size is fixed at the compilation). You can use dynamic_bitset from Boost instead or just allocate a big size and fill from 1 to avoid the mentioned issues above (no need to pad here).

I extended the answer of @berak to be able to handle edge cases as:

• binary shift to the right will "lose" the value of the first bit (or least significant bit): 01 >> 1 produces 00
• binary shift to the right will introduce a 0 for the last bit (or most significant bit): 11 >> 1 produces 01

To solve this issue, I increase the size of the bitset by 2 and I pad the least and most significant bit with the values of the original bitset. The XOR is performed only on the same bit positions than the original bitset.

If you want to count the number of transitions on a horizontal scan line (for a binary image), you can iterate over the image and fill a bitset for each row.

Implementation:

template<int N>
size_t transitionCount2(const std::bitset<N> &b)
{
assert(N > 0);
if (N <= 1)
return 0;

for (size_t i = 0; i < b.size(); i++)
{
}

auto c = b_pad >> 1;
for (size_t i = 0; i < c_pad_cut.size(); i++)
{
}

auto d = b ^ c_pad_cut;
return d.count();
}


The full test code can be executed here.

more

Official site

GitHub

Wiki

Documentation