Building a fast "blobbing" algorithm

cmisip (184)
I am trying to put together an algorithm for sorting data into containers. Basically, a video frame is subdivided into blocks. Each block will have a value of 0 or 1. I need to identify as fast as possible which blocks are connected or contiguous with other blocks and group those blocks into "blobs" . Data will come in sequentially as it is being read from one big buffer. I don't want to have to go through the data twice, so the sorting needs to happen while each block is received and should be finished by the time the last block is received. I have an implementation but I wonder if there are any optimizations possible. This might be a classic problem with classic highly optimized solutions. Thanks for any input you might provide.

Thanks,
Chris

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
 
// Example program
#include <iostream>
#include <string>
#include <vector>


class Block {
     public:
     int val=0;
     std::vector<Block *> *vect=NULL;
     int r=0;
     int c=0;
     Block():val(0){};
     Block(int i):val(i){};
      
  };      
  
void display_bin(std::vector<Block *> &iblock){
	std::cout << "BIN CONTENTS  : ";
    for ( std::vector<Block*>::iterator it=iblock.begin() ; it!= iblock.end(); it++ )
							   std::cout << (*it)->r << "," << (*it)->c << " " ;
	std::cout << std::endl;	
}	  
      

int main()
{
 
  
  
  int width=320+16;
  int height=192;
  int columns=width/16;//21
  int rows=height/16;//12
  
  std::cout << "Columns " << columns << std::endl;
  std::cout << "Rows " << rows << std::endl;
  
  std::cout << "-------------------------------------------------------------" << std::endl;

Block block[12][21] =
    {  // 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 
        { 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 ,1 }, //0
        { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0 }, //1
        { 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 }, //2
        { 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 }, //3
        { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 }, //4
        { 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1 }, //5
        { 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 }, //6
        { 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0 }, //7
        { 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 }, //8
        { 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //9
        { 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 }, //10
        { 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 }, //11
        
    };
    
    int numblocks=12*21; //252
    
    Block * MBlock=NULL;
    MBlock=(Block*)malloc(numblocks*sizeof(Block));
    
    int count=0;
    for (int j=0; j< rows; j++) {
		for (int k=0; k<columns; k++) {  
		   *(MBlock+count)=block[j][k];
		   (MBlock+count)->r=j;
		   (MBlock+count)->c=k;
		   count++;
	   	}
		
	}	
	
	
	
	std::cout << "Data to be sorted into bins" <<std::endl;
	count=0;
	for (int j=0; j< rows; j++) {
		for (int k=0; k<columns; k++) {  
		   std::cout << (MBlock+count)->val << ",";
		   count++;
	   	}
	   	std::cout << std::endl;
		
	}	
	
	std::vector<Block*> v_arr[50];
	
	Block *block_row_up=NULL;  //the row above the row where the THIS block is
	
	int bcount=0;  //block counter
	int vcount=0;  //container counter
	int ccount=0;  //column counter
	int rcount=0;  //row counter
	
	Block *prev_block=0; //block preceeding 
	Block *up_block=0;   //block above
	Block *cur_block=0;  //this block
	
	//START--OF-BLOBBER
	
	for (int j=0; j< rows; j++) {
		for (int k=0; k<columns; k++) {
		    cur_block=(MBlock+bcount);
		    if (cur_block->val) {  //if THIS is ON
			  if (rcount == 0) {         //if this is first row, no connection to TOP possible, so stuff into CURRENT bin
			     cur_block->vect=&v_arr[vcount];
			     v_arr[vcount].push_back(cur_block);
			     //display_bin(v_arr[vcount]);
			  } else { 
				  if ((ccount >0) && (ccount < columns)) {
					  
				      prev_block=(MBlock+bcount-1);
				      
				      if (prev_block->val) {
						 cur_block->vect=prev_block->vect;
					     prev_block->vect->push_back(cur_block); //add THIS to the left bin if connected to the LEFT
					     //display_bin(*prev_block->vect);
					     
						 up_block = (block_row_up+ccount); 
						 if (up_block->val) {  //add TOP bin contents to the left bin too if connected to the TOP
							 if (prev_block->vect != up_block->vect) {
							   prev_block->vect->reserve( up_block->vect->size() + prev_block->vect->size() );   
                               prev_block->vect->insert( prev_block->vect->end(), up_block->vect->begin(), up_block->vect->end() );
                               //display_bin(*prev_block->vect);
                               up_block->vect->clear();
						     }
						     //display_bin(*prev_block->vect);
						 }	  
					  
					  }	//if prev_block is ON
					    else { 
						  up_block = (block_row_up+ccount); 
						  if (up_block->val) {    //if not connected to the LEFT add THIS to the TOP bin if connected to the TOP
							  cur_block->vect=up_block->vect;
					          up_block->vect->push_back(cur_block);
					          //display_bin(*up_block->vect);
							  
						  } else {             //if not connected to the LEFT and not connected to the TOP, put in a CURRENT bin
						     cur_block->vect=&v_arr[vcount];
			                 v_arr[vcount].push_back(cur_block);
			                 //display_bin(v_arr[vcount]);
						  }
				      }	 //if prev_block is OFF	    
			      } else {//if column 0 
				     cur_block->vect=&v_arr[vcount];
				     v_arr[vcount].push_back(cur_block);
				     //display_bin(v_arr[vcount]);
				     
				     
			      }	  
		   } //if rcount>0 closing bracket 
		   
	   }   else {  //if THIS is OFF
			  
			  if (v_arr[vcount].size()) {  //start a NEW BIN only if the current bin is not empty
			    if (vcount < 50){
			       vcount++;
			    } else { 
				   std::cout << "out of vectors" << std::endl;	     
			       break;
			    } 
			  }    
	   }
		   
		   
	   bcount++;ccount++;	   	   
		  
	   if (ccount==columns) {
			  block_row_up=(MBlock+(ccount*rcount)); //set the row pointer to the proper position in the Block* array  
			  ccount=0;
			  rcount++;
			  if (v_arr[vcount].size()) {
		        vcount++; //when moving from row to row, there needs to be a new container
		      }
	       }
	   	}   //for (int k=0; k<columns; k++)
	 }  //for (int j=0; j< rows; j++)
	 
	 
	 //END--OF--BLOBBER
	 
	 //For containers that have more than 4 elements, change the value of val
	 std::cout << "-------------------------------------------------------------" << std::endl;
	 std::cout << "There were " << vcount << " containers created" << std::endl;
	 int disint=1;
	 for (int m=0; m< vcount ; m++) {
		
	    std::cout << "Vcount " << m << "  with size  " << v_arr[m].size() << "  ==> "  ;
	    if (v_arr[m].size() >4){
			disint++;	
	       for (unsigned int n=0; n< v_arr[m].size() ; n++) {
		      std::cout << v_arr[m][n]->r << "," << v_arr[m][n]->c << " ";
		   
		      v_arr[m][n]->val=disint;
		      
	       }   
		} else {
			for (unsigned int n=0; n< v_arr[m].size() ; n++) {
			std::cout << v_arr[m][n]->r << "," << v_arr[m][n]->c << " ";
		   
		      v_arr[m][n]->val=0;
		  }
		}	
		
		std::cout << std::endl;		
	 }	 
	 
	//DISPLAY the results of blobbing 
	std::cout << "-------------------------------------------------------------" << std::endl; 
	std::cout << "Displaying containers with 4 or more elements" << std::endl;  	
	count=0;
	for (int j=0; j< rows; j++) {
		for (int k=0; k<columns; k++) { 
		   if  ((MBlock+count)->val) 
	     	   std::cout << (MBlock+count)->val << ",";
		   else
		       std::cout << "."<< "," ;
		   count++;
	   	}
	   	std::cout << std::endl;
		
	}	  	
	   	
	 free(MBlock);
		
}
Last edited on
poteto (525)
I'm sorry for whoever reported your post.

But I can't help but feel like this a homework assignment, and it would be easier if you just gave the full question.

I am just trying to figure out why you would ever want this. I strongly doubt there is a way to read a file and turn it into blobs in one swoop, unless you did some weird trickery which would need to be explained in a 20 page article, which included benchmarking to show it is an effective and fast technique.
Repeater (3046)
I suspect the post was reported because it spent the first thirty minutes of its life saying only the word "test" :)
Last edited on
jonnin (11438)
I need to identify as fast as possible which blocks are connected or contiguous with other blocks and group those blocks

^^^ Ok, explain to us why this isnt known? Is there a criteria about the zeros and ones that was not stated here? Do the blocks change per frame, and if so, how was that done? Are you trying to do something jpeg ish or something b-zip ish?
cmisip (184)
I suspect the post was reported because it spent the first thirty minutes of its life saying only the word "test" :)

Yeah, I was having issues in the past with the editor when starting a new post. It was easier to edit a new post and I just kept the habit.

The data here is a uint8_t buffer that contains motion vectors in 4 byte chunks: 2 bytes for sum of absolute differences, and 1 byte each for x and y displacement. Each motion vector data corresponds to a 16x16 macroblock in the video frame that is tiled left to right and then down row by row. The Block class is used to store information about each motion vector but not the motion vector data itself. The 'val' member is set if the motion vector data associated with the Block object has motion meaning there is displacement in the x or y dimension. The Block class here is a simplified version of what I actually use as I am also writing to an rgb buffer so I am also storing coordinates and macroblock pixel indexes into an rgb buffer.

Each video frame from an rtsp input is analyzed via a h264 encoder which performs motion estimation and outputs this motion vector data as side info. So each video frame will have different batch of motion vector data. Analysis of the data happens in between h264 encodes of each frames and the results immediately used as trigger for recording video. This is why the algorithm needs to be fast. My initial or level 1 analysis only involved counting the macroblocks that have motion vectors with displacement. However, I am getting a lot of false positives due to isolated small clusters of macroblocks with motion vectors that do not have anything to do with the major motion event. For example, changes in lighting could trigger. My idea was to provide some kind of exclusion criteria or level 2 analysis by blobbing so I can disregard smaller islands of macroblocks as noise and so trigger only by a major motion event like somebody walking in front of the camera. For each frame, the Block objects are reset to zero value for 'val' and iterate all over the next batch of motion vector data again. The data set above containing zeros and ones is just a simplification that indicates the state of the Block as having motion or not.

If this is fast enough and practical, I could do next step or level 3 analysis of actually looking at motion vector direction and use that as a directional trigger when big macroblock islands are all indicating motion in similar directions.

In the picture below you can see the smaller island of macroblocks on the top that I need to exclude.

https://ibb.co/d5DOJe

Thanks,
Chris
jonnin (11438)
Not part of your question but problems like these can benefit enormously (2-3 orders of magnitude!!) by various deresolution techniques. If you took the input and cut it to black and white, you would have 1/3 the data. If you cut the resolution to 640x480 or even half that again, you would inherently lose the 'noise' and only keep the large motion. Its very cheap to map that back to the original (you are not throwing it away, you are just processing on a much smaller amount of data). The result of the smaller processing maps to the bigger cleanly (I have done this, and its very fast).
Last edited on
cmisip (184)
Thanks for the suggestion jonnin. I have actually done the deresolution already. My input data is 1920x1080 but I am downscaling to 640x360 ( I might go down one more level of deresolution yet If it is not practical to stay at this resolution). This gives me about 943 macroblocks to process and an RGB buffer that is way smaller. The other reason for the deresolution is memory with which I am limited to ~500 MB and keeping 30 RGB buffers in memory is impossible at 1920x1080. This is running on a raspberry pi 3. The other suggestion to use grayscale would entail another trip to the GPU to use its hardware scaler ( which doubles for format conversion) because I need to keep the RGB data. This step would extend the pipeline which is now at Decode (H264->YUV) -> Resize (YUV->RGB)->Encode (motion vector data) -> JPEG block. The neat thing about this is that the entire pipeline is done in hardware accelerated mode and I really don't want to do any software format conversion and use the cpu. I am getting about 35% cpu utilization and 7 frames/second with an input fps of 15/fps ( Lose about half for processing the vectors and writing on the buffer) but I think that a lot of the cpu use is also because the H264 input packets are saved to video file on the original 1920x1080 resolution and decode fps which should be very close to the input fps.

Thanks
Chris
Last edited on
jonnin (11438)
you can do a cheap greyscale on the CPU, if you wanted to. shift R, G, and B by 2 (divide by 4, but shifting is faster) and sum those. If the cpu has multiple cores, its threadable. /shrug sounds like you are on the right track. Let me think some more on the real problem. Its a lot to chew on coming in cold. I don't know what effect that would have on your pipeline, but it shouldn't cost a lot of time to try it.

depending on what it is, you may also be able to process every 2nd or 3rd or 10th frame. We used to use video obstacle avoidance on a robot and it was fine at 6 or so FPS. Depends on how fast you expect something to be moving in the frames how much you can get away with. In video processing in real time, the first steps are usually "what is the least I can get away with here".
Last edited on
cmisip (184)

f you wanted to. shift R, G, and B by 2 (divide by 4, but shifting is faster) and sum those

This is certainly interesting. The formulas I've seen involved more computation. It's worth a shot, however, I'll have to be iterating over 640x360 pixels with three shift operations. In the end, I will still be dealing with the same number of macroblocks because that's a fixed number per frame regardless of the color depth ( It is only resolution dependent as it is the total number of 16x16 tiles with an extra column. ) , however, there may be fewer vectors that need to be analyzed in the next step.

If the cpu has multiple cores, its threadable

It's quadcore and supports threading. However, the program architecture is such that multple instances of the capture and analyze daemon are spawned ( one per camera). I would like to keep the other chores free for that purpose.

depending on what it is, you may also be able to process every 2nd or 3rd or 10th frame

The pipeline is asynchronous and so sending a buffer to a stage does not guarantee a buffer to be returned. Sometimes none is returned, and so I cancel the pipeline and start over on the next frame if a buffer is not successfully received. In effect it is naturally trimming frames but I could also preemptively trim.

We used to use video obstacle avoidance on a robot ...

I am also interested in this application. It's an aside topic but what was your algorithm for visual obstacle avoidance?

Thanks,
Chris
Thomas1965 (4571)
It was probably a long time ago that you could save some ns with shifting but not nowadays with modern compiler. 
1
2
3
4
5
6
7
8
9
10
11
12
 
void f1()
{
    int i = 1;

    i = i * 2;
}

void f2()
{
    int j = 1;
    j = j << 1;
}


Assembler generated:
gcc 8.2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
f1():
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        sal     DWORD PTR [rbp-4]
        nop
        pop     rbp
        ret
f2():
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        sal     DWORD PTR [rbp-4]
        nop
        pop     rbp
        ret


clang 3.0.0
1
2
3
4
5
6
7
8
9
10
11
12
13
 
f1():                                 # @f1()
        mov     DWORD PTR [RSP - 4], 1
        mov     EAX, DWORD PTR [RSP - 4]
        shl     EAX, 1
        mov     DWORD PTR [RSP - 4], EAX
        ret
 
f2():                                 # @f2()
        mov     DWORD PTR [RSP - 4], 1
        mov     EAX, DWORD PTR [RSP - 4]
        shl     EAX, 1
        mov     DWORD PTR [RSP - 4], EAX
        ret


see the Compiler Explorer.
https://godbolt.org/
cmisip (184)
This is neat. I wonder if there is an easy way to convert assembly code to neon assembly. That would be another avenue for optimization that I know nothing about.

Chris
jonnin (11438)
he is just showing that on his compiler shifting and division were the same. Maybe they are all smart about this now. you can stick to c++ unless you want to go down the assembly optimize rabbit hole. if you do that, its the LAST thing you do once you know where it can be applied to best results.


-- the obstacle avoidance we did was a data fusion. Visual was only a small part of the whole, it had other sensors (radar, sonar, and a range finder, and a transponder listener and more) and a bunch of complicated stuff. The robot was on a boat platform, and the algorithm for the visual bit was, in a vastly oversimplified nutshell, "is it water or sky" and "if not, does it seem to be getting closer and is it in my way across several frames". So really it was a classifier problem of what was in the scene, the where was just frame by frame stereoscopic-like analysis.
Last edited on
cmisip (184)
Thanks for the info guys. I have run into a small problem with the code I posted above. I modified the data block and now I am getting this output.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Displaying containers with 4 or more elements
.,3,3,3,3,3,3,.,.,.,.,.,.,4,4,4,.,4,.,.,.,
3,3,3,3,.,.,.,2,2,2,.,.,.,4,4,4,4,4,.,.,.,
.,3,.,3,.,.,.,.,2,2,2,.,.,.,.,4,4,4,.,.,.,
3,3,3,3,.,.,.,.,2,2,.,.,.,.,.,4,4,4,4,.,.,
.,.,.,.,.,.,.,.,2,2,.,.,.,.,.,4,4,4,4,.,.,
.,.,.,5,5,5,.,.,.,.,.,.,.,.,.,.,.,4,4,4,4,
.,5,5,5,.,6,6,6,6,6,.,.,.,.,.,4,4,4,4,.,.,
.,5,5,5,.,6,6,.,6,6,.,.,.,.,.,4,4,4,4,.,.,
.,5,5,5,.,.,.,.,6,6,.,.,.,.,.,4,4,4,4,.,.,
.,.,5,5,5,.,.,.,.,6,6,.,.,.,.,.,.,.,.,.,.,
.,5,5,5,.,.,.,.,6,6,.,.,.,.,.,7,7,7,7,.,.,
.,5,5,5,.,.,.,.,6,6,.,.,.,.,.,7,7,7,7,.,.,


The 6's above should be part of the 5 block. I'm looking for the issue and would welcome any pointers or correction. The code still works at excluding the smaller blobs.

--thanks for info jonnin. My first project in cpp to motivate myself to learn was using an irobot platform and implementing various bits for obstacle navigation and localization. Never finished the project but hope to get to working on it again. My idea was to segment the room into grid pattern, display it in perspective view and look for blobs in each grid from the robot's perspective and mark the grid locations with blobs as obstacles for the navigation code to solve.

Thanks,
Chris
tpb (1495)
If you just need a flood fill algorithm, this seems to work:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
#include <iostream>
#include <iomanip>
#include <queue>
#include <vector>
using namespace std;

void fill(vector<int>& m, int cols, int r, int c, int target, int replacement) {
    if (m[r*cols+c] != target)
        return;
    queue<pair<int,int>> q;
    q.push(make_pair(r, c));
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        int row = p.first, w = p.second, e = p.second;
        while (w >= 0 && m[row*cols+w] == target) --w;
        while (e < cols && m[row*cols+e] == target) ++e;
        for (int n = w + 1; n < e; ++n) {
            m[row*cols+n] = replacement;
            if (row >  0 && m[(row-1)*cols+n] == target)
                q.push(make_pair(row-1, n));
            if (row < int(m.size()/cols) && m[(row+1)*cols+n] == target)
                q.push(make_pair(row+1, n));
        }
    }
}

int main() {
    vector<int> block = {
    //  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
        0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 ,1, //0
        1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, //1
        0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, //2
        1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //3
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //4
        1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, //5
        0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //6
        0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, //7
        0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //8
        0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //9
        0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //10
        0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //11
    };
    int cols = 21, rows = block.size() / cols;

    int n = 1;
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (block[r*cols+c] == 1)
                fill(block, cols, r, c, 1, ++n);
        }
    }

    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c)
            if (block[r*cols+c])
                cout << setw(2) << block[r*cols+c] << ' ';
            else
                cout << " . ";
        cout << '\n';
    }
}

Last edited on
ne555 (10692)
https://docs.opencv.org/3.1.0/d3/dc0/group__imgproc__shape.html

> I have an implementation but I wonder if there are any optimizations possible.
explain your implementation
cmisip (184)
explain your implementation


My naive implementation is the code in the first post in this thread. It was simply checking to see if the block in the current iteration has val set (ON) and to see if it is connected to the block above that is ON and to the left that is ON, and if so, put all the connected blocks into one vector.

tpb solved the problem though. I modified the code so it is more consistent with the program I am writing.

Thanks guys for taking the time. I might have some more questions yet.

Chris

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
#include <iostream>
#include <iomanip>
#include <queue>
#include <vector>
using namespace std;

class Block {
     public:
     int val=0;
     std::vector<Block *> *vect=NULL;
     int r=0;
     int c=0;
     Block():val(0){};
     Block(int i):val(i){};
      
  };  
  
  vector<Block*> v_arr[50];  
  int cols = 21;
  int rows = 12;
    
  int numblocks=12*21; //252  
  
void display_bin(std::vector<Block *> &iblock){
	std::cout << "BIN CONTENTS  : ";
    for ( std::vector<Block*>::iterator it=iblock.begin() ; it!= iblock.end(); it++ )
							   std::cout << (*it)->r << "," << (*it)->c << " " ;
	std::cout << std::endl;	
}	  

void fill(Block *m, int cols, int r, int c, vector<Block *> &target, vector<Block *> &replacement) {
    if ((m+(r*cols+c))->vect != &target) {
        return;
    }    
    queue<pair<int,int>> q;
    q.push(make_pair(r, c));
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        int row = p.first, w = p.second, e = p.second;
        while (w >= 0 && (m+(row*cols+w))->vect == &target) --w;
        while (e < cols && (m+(row*cols+e))->vect == &target) ++e;
        for (int n = w + 1; n < e; ++n) {
            (m+(row*cols+n))->vect = &replacement;
            replacement.push_back(m+(row*cols+n));
            if (row >  0 && (m+((row-1)*cols+n))->vect == &target)
                q.push(make_pair(row-1, n));
            if ((row < rows) && ((m+((row+1)*cols+n))->vect == &target))
                q.push(make_pair(row+1, n));
        }
    }
}


int main() {
	Block block[numblocks] =
    //  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
    {    0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 ,1, //0
        1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, //1
        0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, //2
        1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //3
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //4
        1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, //5
        0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //6
        0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, //7
        0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //8
        0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //9
        0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //10
        0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, //11
    };
    
    
    Block * MBlock=NULL;
    MBlock=(Block*)malloc(numblocks*sizeof(Block));
    
    
    
    int count=0;
    for (int j=0; j< numblocks; j++) {
		   *(MBlock+count)=block[j];
		   (MBlock+count)->r=j/cols;
		   (MBlock+count)->c=j%cols;
		   if ((MBlock+count)->val ==1) {
		       (MBlock+count)->vect=&v_arr[0];
		   }    
		   count++;
	}	

    std::cout << "Data to be sorted into bins" <<std::endl;
	count=0;
	for (int j=0; j< rows; j++) {
		for (int k=0; k<cols; k++) {  
		   std::cout << (MBlock+count)->val << ",";
		   count++;
	   	}
	   	std::cout << std::endl;
		
	}	

    int vcount = 1;
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if ((MBlock+(r*cols+c))->val == 1) {
                fill(MBlock, cols, r, c, v_arr[0] , v_arr[vcount]);
                if (v_arr[vcount].size() >0)  
                   vcount++;
			}
			  
        }
    }
    
    
    
    //For containers that have more than 4 elements, change the value of val
	 std::cout << "-------------------------------------------------------------" << std::endl;
	 std::cout << "There were " << vcount << " containers created" << std::endl;
	 int disint=1;
	 for (int m=0; m< vcount ; m++) {
		
	    std::cout << "Vcount " << m << "  with size  " << v_arr[m].size() << "  ==> "  ;
	    if (v_arr[m].size() >4){
			disint++;	
	       for (unsigned int n=0; n< v_arr[m].size() ; n++) {
		      std::cout << v_arr[m][n]->r << "," << v_arr[m][n]->c << " ";
		   
		      v_arr[m][n]->val=disint;
		      
	       }   
		} else {
			for (unsigned int n=0; n< v_arr[m].size() ; n++) {
			std::cout << v_arr[m][n]->r << "," << v_arr[m][n]->c << " ";
		   
		      v_arr[m][n]->val=0;
		  }
		}	
		
		std::cout << std::endl;		
	 }	 
	 
	//DISPLAY the results of blobbing 
	std::cout << "-------------------------------------------------------------" << std::endl; 
	std::cout << "Displaying containers with 4 or more elements" << std::endl;  	
	count=0;
	for (int j=0; j< rows; j++) {
		for (int k=0; k<cols; k++) { 
		   if  ((MBlock+count)->val) 
	     	   std::cout << (MBlock+count)->val << ",";
		   else
		       std::cout << "."<< "," ;
		   count++;
	   	}
	   	std::cout << std::endl;
		
	}	  	
    
    
     free(MBlock);
}
Topic archived. No new replies allowed.