title: Blobs detecting algorithm
body: <p>I am trying to make <strong>blobs finding algorithm with 8 connectivity for binary image(monochrome)</strong> (coordinates of bounding boxes up-left and down-right dots)which <strong>use small amount of memory (needed because the large resolution of the image) on C++</strong>.</p>
  <p>There are such tools like OpenCV, but it has a lot of filters and is too slow if you want to detect <strong>each blob in binary image</strong>, there is also CvBlobsLib but the support is outdated(last version is before 5 years) and I couldn't set it up for <strong>Visual Studio 2013</strong> (it must be compiled with Cmake, and it is giving errors). In wikipedia there are two types of algorithms - &quot;one component of a time&quot; and &quot;two-pass&quot; <a href="https://en.wikipedia.org/wiki/Connected-component_labeling" rel="nofollow noreferrer">connected-component</a> , but they both use labels, which mean you will have another 2D array of integers, but this will take a lot of memory because of the size of int(4 bytes), and we need int because of the image size and possibility of more than 65535 labels(which is short). If it is even short it will take twice less memory, which is again a lot of it. I found a &quot;quickblob&quot; written in C <a href="http://kmkeen.com/quickblob/index.html" rel="nofollow noreferrer">quicblobsalgol</a> but I couldn't run it from the source(but exe is working properly), tried to analyze the code, and I got something, but the whole idea behind it stayed vague for me, so I tried also something like <strong>floodFill algorithm and something like &quot;disjoined-set data structure&quot;</strong> <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow noreferrer">link</a> which to hold the blobs, and this means the used memory theoretically is defined of the number of blobs(single black pixels are not recognize as blobs). Here is the C++ code:</p>
  <pre><code> #include &lt;cstdlib&gt; 
      #include &lt;iostream&gt;
      #include &lt;ctime&gt;
      #include &lt;math.h&gt;
      #define ROWS 4000
      #define COLS 4000
      #define BLOBS 1000000
      using namespace std;
  
      void floodFillAlgorithm(short(&amp;arr)[ROWS][COLS]);
      int recurciveMarkBlob(short(&amp;arr)[ROWS][COLS], int **ptr_labels, int i, int j, int group);
  
      int main(){
  
      short arr[ROWS][COLS];
  
      srand((unsigned int)time(0)); // use current time as seed for random generator
  
      for (int i = 0; i &lt; ROWS; i++)
      {
          for (int j = 0; j &lt; COLS; j++)
          {
              arr[i][j] = rand() % 2;
          }
      }
      
      
      /*for (int i = 0; i &lt; ROWS; i++)
      {
          for (int j = 0; j &lt; COLS; j++)
          {
              cout &lt;&lt; arr[i][j] &lt;&lt; '\t';
          }
      cout &lt;&lt; '\n';
      }*/
      
  
      floodFillAlgorithm(arr);
      cout &lt;&lt; '\n';
      cout &lt;&lt; '\n';
  
      /*for (int i = 0; i &lt; ROWS; i++)
      {
          for (int j = 0; j &lt; COLS; j++)
          {
              cout &lt;&lt; arr[i][j] &lt;&lt; '\t';
          }
          cout &lt;&lt; '\n';
      }*/
  
      system(&quot;PAUSE&quot;);
      return 0;}
  
      void floodFillAlgorithm(short(&amp;arr)[ROWS][COLS])
      {
      int group = 0;
      int **ptr_labels;   
  
      ptr_labels = (int **)malloc(BLOBS * sizeof(int*));
  
      if (ptr_labels == 0)
      {
          printf(&quot;ERROR: Out of memory\n&quot;);       
      }
  
      for (int i = 0; i &lt; BLOBS; i++)
      {
          ptr_labels[i] = NULL;       
      }   
  
      for (int i = 0; i &lt; ROWS; i++)
      {
          for (int j = 0; j &lt; COLS; j++)
          {
              if (arr[i][j] == 1)
              {
                  recurciveMarkBlob(arr, ptr_labels,i, j, ++group);
                  arr[i][j] = 1;
              }
          }
      }
  
      int count = 0;
      for (int i = 0; i &lt; BLOBS; i++)
      {
          if (ptr_labels[i] != NULL)
          {
              count++;
              //cout &lt;&lt; &quot;Label: &quot; &lt;&lt; i &lt;&lt; &quot; ; X1: &quot; &lt;&lt; ptr_labels[i][0] &lt;&lt; &quot; ;       Y1: &quot; &lt;&lt; ptr_labels[i][1] &lt;&lt; &quot; ; X2: &quot; &lt;&lt; ptr_labels[i][2] &lt;&lt; &quot; ; Y2: &quot; &lt;&lt; ptr_labels[i][3] &lt;&lt; &quot; ; X3: &quot; &lt;&lt; ptr_labels[i][4] &lt;&lt; &quot; ; Y3: &quot; &lt;&lt; ptr_labels[i][5] &lt;&lt; &quot; ; POINTS: &quot; &lt;&lt; ptr_labels[i][6] &lt;&lt; endl;
          }
      }
  
      cout &lt;&lt; &quot;Count: &quot; &lt;&lt; count &lt;&lt; endl;
  
      system(&quot;PAUSE&quot;);
  
      for (int i = 0; i &lt; BLOBS; i++)
      {
          if (ptr_labels[i] != NULL)
          {
              free(ptr_labels[i]);
          }
      }
  
      free(ptr_labels);
      }
  
       int recurciveMarkBlob(short(&amp;arr)[ROWS][COLS], int **ptr_labels, int i, int j, int group)
      {   
      //cout &lt;&lt; &quot; i : &quot; &lt;&lt; i &lt;&lt; &quot; j: &quot; &lt;&lt; j &lt;&lt; endl;
      if (j != 0)
      {
          if ((arr[i][j] == arr[i][j - 1]) &amp;&amp; (arr[i][j - 1] == 1))
          {
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j - 1;
                  ptr_labels[group][1] = i;
                  ptr_labels[group][2] = j;
                  ptr_labels[group][3] = i;
                  ptr_labels[group][4] = j;
                  ptr_labels[group][5] = i;
                  ptr_labels[group][6] = 2;   // taken points (area) for current shape
              }
              else
              {
                  if (ptr_labels[group][0] &gt; j - 1)
                  {
                      ptr_labels[group][0] = j - 1;
                  }       
                  ptr_labels[group][6]++;
              }
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i, j - 1, group);
              arr[i][j] = 1;
          }
      }
      
      if (j != COLS - 1)
      {
          if ((arr[i][j] == arr[i][j + 1]) &amp;&amp; (arr[i][j + 1] == 1))
          {
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j;
                  ptr_labels[group][1] = i;
                  ptr_labels[group][2] = j + 1;
                  ptr_labels[group][3] = i;
                  ptr_labels[group][4] = j;
                  ptr_labels[group][5] = i;
                  ptr_labels[group][6] = 2;   // taken points (area) for current shape
              }
              else
              {
                  if (ptr_labels[group][2] &lt; j + 1)
                  {
                      ptr_labels[group][2] = j + 1;
                  }
                  ptr_labels[group][6]++;
              }
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i, j + 1, group);
              arr[i][j] = 1;
          }
      }
      
      if (i != 0)
      {
          if ((arr[i][j] == arr[i - 1][j]) &amp;&amp; (arr[i - 1][j] == 1))
          {
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j;
                  ptr_labels[group][1] = i - 1;
                  ptr_labels[group][2] = j;
                  ptr_labels[group][3] = i;
                  ptr_labels[group][4] = j;
                  ptr_labels[group][5] = i;
                  ptr_labels[group][6] = 2;   // taken points (area) for current shape
              }
              else
              {
                  if (ptr_labels[group][1] &gt; i - 1)
                  {
                      ptr_labels[group][1] = i - 1;
                  }
                  ptr_labels[group][6]++;
              }
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i - 1, j, group);
              arr[i][j] = 1;
          }
      }   
      if (i != ROWS - 1)
      {
          if ((arr[i][j] == arr[i + 1][j]) &amp;&amp; (arr[i + 1][j] == 1))
          {
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j;
                  ptr_labels[group][1] = i;
                  ptr_labels[group][2] = j;
                  ptr_labels[group][3] = i + 1;
                  ptr_labels[group][4] = j;
                  ptr_labels[group][5] = i;
                  ptr_labels[group][6] = 2;   // taken points (area) for current shape
              }
              else
              {
                  if (ptr_labels[group][3] &lt; i + 1)
                  {
                      ptr_labels[group][3] = i + 1;
                  }
                  ptr_labels[group][6]++;
              }
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i + 1, j, group);
              arr[i][j] = 1;
          }
      }
      
      if ((i != 0) &amp;&amp; (j != 0))
      {
          if ((arr[i][j] == arr[i - 1][j - 1]) &amp;&amp; (arr[i - 1][j - 1] == 1))
          {
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j - 1;
                  ptr_labels[group][1] = i - 1;
                  ptr_labels[group][2] = j;
                  ptr_labels[group][3] = i;
                  ptr_labels[group][4] = j;
                  ptr_labels[group][5] = i;
                  ptr_labels[group][6] = 2;   // taken points (area) for current shape
              }
              else
              {
                  if (ptr_labels[group][0] &gt; j - 1)
                  {
                      ptr_labels[group][0] = j - 1;
                  }
                  if (ptr_labels[group][1] &gt; i - 1)
                  {
                      ptr_labels[group][1] = i - 1;
                  }
                  ptr_labels[group][6]++;
              }       
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i - 1, j - 1, group);
              arr[i][j] = 1;
          }
      }       
      if ((i != 0) &amp;&amp; (j != COLS - 1))
      {
          //cout &lt;&lt; &quot;i: &quot; &lt;&lt; i &lt;&lt; &quot; ; j: &quot; &lt;&lt; j &lt;&lt; endl;
          if ((arr[i][j] == arr[i - 1][j + 1]) &amp;&amp; (arr[i - 1][j + 1] == 1))
          {
              //cout &lt;&lt; &quot;i: &quot; &lt;&lt; i &lt;&lt; &quot; ; j: &quot; &lt;&lt; j &lt;&lt; endl;
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j;
                  ptr_labels[group][1] = i - 1;
                  ptr_labels[group][2] = j + 1;
                  ptr_labels[group][3] = i;
                  ptr_labels[group][4] = j;
                  ptr_labels[group][5] = i;
                  ptr_labels[group][6] = 2;   // taken points (area) for current shape
                  //cout &lt;&lt; &quot;Label: &quot; &lt;&lt; group &lt;&lt; &quot; ; X1: &quot; &lt;&lt; ptr_labels[group][0] &lt;&lt; &quot; ; Y1: &quot; &lt;&lt; ptr_labels[group][1] &lt;&lt; &quot; ; X2: &quot; &lt;&lt; ptr_labels[group][2] &lt;&lt; &quot; ; Y2: &quot; &lt;&lt; ptr_labels[group][3] &lt;&lt; endl;
              }
              else
              {
                  if (ptr_labels[group][2] &lt; j + 1)
                  {
                      ptr_labels[group][2] = j + 1;
                  }
                  if (ptr_labels[group][1] &gt; i - 1)
                  {
                      ptr_labels[group][1] = i - 1;
                  }
                  ptr_labels[group][6]++;
              }   
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i - 1, j + 1, group);
              arr[i][j] = 1;
          }
      }   
      if ((i != ROWS - 1) &amp;&amp; (j != 0))
      {
          if ((arr[i][j] == arr[i + 1][j - 1]) &amp;&amp; (arr[i + 1][j - 1] == 1))
          {
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j - 1;
                  ptr_labels[group][1] = i;
                  ptr_labels[group][2] = j;
                  ptr_labels[group][3] = i + 1;
                  ptr_labels[group][4] = j;
                  ptr_labels[group][5] = i;
                  ptr_labels[group][6] = 2;   // taken points (area) for current shape
              }
              else
              {
                  if (ptr_labels[group][0] &gt; j - 1)
                  {
                      ptr_labels[group][0] = j - 1;
                  }
                  if (ptr_labels[group][3] &lt; i + 1)
                  {
                      ptr_labels[group][3] = i + 1;
                  }
                  ptr_labels[group][6]++;
              }       
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i + 1, j - 1, group);
              arr[i][j] = 1;
          }
      }
      
      if ((i != ROWS - 1) &amp;&amp; (j != COLS - 1))
      {
          if ((arr[i][j] == arr[i + 1][j + 1]) &amp;&amp; (arr[i + 1][j + 1] == 1))
          {
              if (ptr_labels[group] == NULL)
              {
                  ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
                  ptr_labels[group][0] = j;
                  ptr_labels[group][1] = i;
                  ptr_labels[group][2] = j + 1;
                  ptr_labels[group][3] = i + 1;
                  ptr_labels[group][4] = j;   // x of pixel in black
                  ptr_labels[group][5] = i;   // y of pixel in black
                  ptr_labels[group][6] = 2;   // taken points (area) for   current shape
              }
              else
              {
                  if (ptr_labels[group][2] &lt; j + 1)
                  {
                      ptr_labels[group][2] = j + 1;
                  }
                  if (ptr_labels[group][3] &lt; i + 1)
                  {
                      ptr_labels[group][3] = i + 1;
                  }
                  ptr_labels[group][6]++;
              }   
              arr[i][j] = 0;
              recurciveMarkBlob(arr, ptr_labels, i + 1, j + 1, group);
              arr[i][j] = 1;
          }
      }
      /**/
      arr[i][j] = 0;
  
      return 0;
  }
  </code></pre>
  <p><strong>The main question is why before end of the main function so much RAM is still in use(147 MB).</strong> The tail recursion &quot;recurciveMarkBlob()&quot; is using parameters by value i,j, group, and dynamic allocation of memory and that is why the memory temporary jumps to 600 MB(mostly from the parameters),  after freeing the dynamically allocated memory it still takes 148 MB, the image is 4 000 x 4 000 x 2 bytes = 16 000 000 bytes = 16 MB. I have read about &quot;function taken memory&quot; <a href="https://stackoverflow.com/questions/13485967/how-much-memory-does-a-function-use">here</a> but I still cant understand why. If someone can explain it with assembler code what is happening and is this occurrence normal. <strong>I am using Release mode</strong> <a href="https://stackoverflow.com/questions/32523171/recursion-in-visual-studio?noredirect=1#comment52931819_32523171">release vs debug</a></p>
  <p>system(&quot;PAUSE&quot;) in main()
  <a href="https://i.stack.imgur.com/kms4j.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/kms4j.png" alt="enter image description here" /></a></p>
  <p>In process of recursion
  <a href="https://i.stack.imgur.com/Yfuwc.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Yfuwc.png" alt="enter image description here" /></a></p>
  <p>Also everyone can give idea for fast and low memory taking algorithm for blob detection of large binary images.</p>