7.8. Estimating the mask of a polygon shape

spot

A mask is an image in which each pixel has for a value:

• 1 if it is inside the polygon or exactly on its contour,
• 0 if it is outside the polygon

The proposed solution to tackle this exercize is to use a recursive method: a function (or method) which calls itself. The main steps of such an algorithm are:

• mask initialization: the pixels corresponding to the corners of the polygon are set to 1, the others are set to 0,
• contour closure: discontinuities may stem from the fact that the corners aren’t necessarily close to each other, which will be an issue at a later stage of the algorithm. This step is hence used to make the contour continuous.
• determination of a point within the contour (seed): simple algorithm for a polygon similar to a convex polygon (but harder and harder for more complex polygons)
• filling the inner area of the contour: starting from the seed, call a function which recursively modify the value of its 4 neighbours (changing it from 0 to 1.)

1. in the class Polygon, declare a data member m_mask of type Image. Add a method:

   void Polygon::InitMask();
   

   Instantiate the m_mask object with dimensions identical to the ones of the m_box BoundingBox (it isn’t necessary for the mask to have the dimensions of the image.) Initialize all the pixels of the mask to 0, except those stored in m_polygon which will be set to 1.

2. Closing the polygon. For each pair of consecutive corners:

   • compute the slope of the segment joining them,

   • for each point of this segment, set the pixel to 1 in m_mask.

     Attention: if the slope is < 1 (in absolute value,) the loop must run over the x (blue case.) Otherwise, it must run over the y (red case.)

     

     At this stage, the contour should be completely closed.

3. Determination of a point within the polygon (seed). A simple algorithm consists in counting – starting from a point not on the contour (i.e. the seed) – the number of points on an horizontal line passing by the seed point, intersecting with the contour in an arbitrary chosen direction (left or right.) If the count is odd, the point is inside the contour. Otherwise, it is outside.

4. Filling the contour. A recursive function is a function which calls itself. Beware to the boundary conditions to prevent such a function to indefinitely call itself (hence using all the stack memory and then crashing your program.)

   Here, if a calling pixel (x,y) was set to 0, the method changes it to 1 and the method is then applied on each of the 4 direct neighbours (right, left, up and down.) Such a process is stopped when the calling pixel is already set to 1 (the contour is reached) or when the image border is reached (which shouldn’t happen if the contour was correctly closed to start with and if the seed was correctly put inside the contour.)

   void Polygon::Update4Neighbours(Image &mask, int x, int y)
   {
     if (x < 0 || x >= mask.GetNX() ||
         y < 0 || y >= mask.GetNY() || 
         mask.GetData(x, y) ) {
       return;
     }
   
     mask.SetData(true, x, y);
     Update4Neighbours(mask, x+1, y  );
     Update4Neighbours(mask, x-1, y  );
     Update4Neighbours(mask, x,   y-1);
     Update4Neighbours(mask, x,   y+1);
   }
   

5. One should display the mask to check it indeed contains ones inside the contour and zeroes around:

   for (y = 0; y < m_mask.GetNY(); ++y) {
     for (x = 0; x < m_mask.GetNX(); ++x) {
       std::cout << m_mask.GetData(x,y);
     }
     std::cout << "\n";
   }
   

6. This mask must now be used to decide if a given pixel falls within or outside a polygon, and thus compute the area of the polygon (and compute the number of counts.)

The algorithm described above is rather limited (w.r.t the seed search) because it is rather difficult to be sure the point is inside the polygon. One can write a more complex and sophisticated algorithm but one will (almost) always find an edge case. That’s why we’ve actually chosen a different approach in the solution below. The principle of this alternative consists in applying the recursive method on the points outside the contour (a 0 pixel at the image’s border is bound to be outside the contour.) If one applies this method as long as there are 0 pixels on the image’s border, then one gets a sort of negative of the mask, i.e. a mask whose pixels are 1 if they are outside the polygon (or on the contour) and 0 otherwise. One then just has to invert the mask except for the pixels on the contour itself (which need to stay set to 1.) The implementation of this method needs another local variable contour of type Image to store the pixels on the contour. The code below replaces the steps 3 and 4:

// initialize the mask with the closed contour
for (y = 0; y < m_mask.GetNY(); ++y) {
  for (x = 0; x < m_mask.GetNX(); ++x) {
    m_mask.SetData(contour.GetData(x, y), x, y);
  }
}

// call the recursive method for the left- and right-border pixels
for (y = 0; y < m_mask.GetNY(); ++y) {
  if (!m_mask.GetData(0, y)) {
    Update4Neighbours(m_mask, 0, y);
  }

  if (!m_mask.GetData(m_mask.GetNX()-1, y)) {
    Update4Neighbours(m_mask, m_mask.GetNX()-1, y);
  }
}

// call the recursive method for the up- and bottom-border pixels
for (x = 0; x < m_mask.GetNX(); ++x) {
  if (!m_mask.GetData(x, 0)) {
    Update4Neighbours(m_mask, x, 0);
  }

  if (!m_mask.GetData(x, m_mask.GetNY()-1)) {
    Update4Neighbours(m_mask, x, m_mask.GetNY()-1);
  }
}

// inverting the 0s and 1s, except for the contour
for (y = 0; y < m_mask.GetNY(); ++y) {
  for ( x = 0; x < m_mask.GetNX(); ++x) {
    if (!contour.GetData(x, y)) {
      m_mask.SetData(1-m_mask.GetData(x, y), x, y);
    }
  }
}

Validate this step