C++ Breaks with border pixels

[jarodhanko-crafco]

If you have a skeleton on border pixels, the algorithm does not work well. I tested only with c++.

Here is a test image:

Here is the result:

In addition, when testing, I also noticed that the algorithm results in quite a few gaps when converting from skeleton -> polygons -> back to skeleton. This occurs regardless of chunk size.

Here is my polygon -> skeleton code. It's possible that redrawing the skeleton is broken instead of the actual algorithm for generating polygons, but the polygon count from the algorithm is only 3, so I don't think that is the case.

Adding black border pixels around the entire image mostly fixes the issue although there are a few weird artifacts, so I think it is something with boundary conditions. I haven't been able to figure out what needs to be updated though.

  #include <opencv2/opencv.hpp>

  void display_polylines(skeleton_tracer_t::polyline_t *it)
  {
    uchar *im2 = new uchar[W * H];
    memset(im2, 0, W * H * sizeof(uchar)); // Initialize the image matrix to 0

    while (it)
    {
      point_t *jt = it->head;
      while (jt)
      {
        // set all points to 1
        im2[jt->y * W + jt->x] = 1;
        // draw a line between the points using Bresenham's line algorithm
        if (jt->next)
        {
          int x0 = jt->x;
          int y0 = jt->y;
          int x1 = jt->next->x;
          int y1 = jt->next->y;
          int dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
          int dy = -abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
          int err = dx + dy, e2;
          while (true) // loop over the line
          {
            im2[y0 * W + x0] = 1;     // set the pixel
            if (x0 == x1 && y0 == y1) // if we have reached the end of the line, break
              break;
            e2 = 2 * err; // calculate the error
            if (e2 >= dy) // if the error is greater than the change in y
            {
              err += dy; // increment the error
              x0 += sx;  // increment x
            }
            if (e2 <= dx) // if the error is less than the change in x
            {
              err += dx; // increment the error
              y0 += sy;  // increment y
            }
          }
        }
        jt = jt->next;
      }
      it = it->next;
    }

    cv::Mat imgMat2 = cv::Mat(H, W, CV_8UC1, im2);
    imgMat2 *= 255;
    cv::imshow("skeleton", imgMat2);
    cv::waitKey(0);

    delete im2;
  }

[jarodhanko-crafco]

For now my solution is to add a 1-pixel black border and a coordinate offset. It has something to do with the seam calculation, but I can't figure out what it would need to change to.

struct skeleton_tracer_t 
{
  //...
  int pixelOffset = 0; // if a border is added to image, then need to adjust all coordinates by this value
  //...

  void adjust_by_offset(polyline_t *it)
  {
    while (it)
    {
      point_t *jt = it->head;
      while (jt)
      {
        jt->x -= pixelOffset; // adjust x by pixelOffset
        jt->y -= pixelOffset; // adjust y by pixelOffset
        jt = jt->next;
      }
      it = it->next;
    }
  }

  // add a black (0) border to every side of the image
  // by creating new image and setting image pixels in center
  void add_im_border(int borderWidth = 1)
  {
    int newW = W + 2 * borderWidth;
    int newH = H + 2 * borderWidth;
    uchar *newIm = (uchar *)malloc(newW * newH * sizeof(uchar));
    memset(newIm, 0, newW * newH * sizeof(uchar)); // Initialize the image matrix to 0

    for (int i = 0; i < H; i++)
    {
      for (int j = 0; j < W; j++)
      {
        newIm[(i + borderWidth) * newW + j + borderWidth] = im[i * W + j];
      }
    }

    W = newW;
    H = newH;
    free(im);
    im = newIm;
    pixelOffset = borderWidth;
  }

}

Then adjust trace to:

thinning_zs();
add_im_border(1);
polyline_t *p = (polyline_t *)trace_skeleton(0,0,W,H,0); //unchanged
adjust_by_offset(p);

You can't put the adjust_by_offset in the trace_skeleton unless you ensure its the base case, since it is recursive.