Code execution breaking during recursion

问题:

In a pattern of single alphabet in an image I've written a small function which will start from any pixel and traverse all the contiguous pixels. In short in a matrix it will turn on all the contiguous pixels to true and rest will be zero.

This function has done it correctly. However with little change in input pattern it is behaving abnormally. I'm finding that this line onwards: //process left-up diagonally is not getting called.

What could be the reason?

Also valgrind shows no memory corruption. The input jpg file size is 170x30 pixels maximum

System Ubuntu-16

Makefile:

CFLAGS= -O2 -c  -I$(INC_DIR) -fpermissive  -std=c++11
CC=g++-5


%.o: %.cpp
        $(CC) $(CFLAGS) -c $< -o $@


readpattern: readpattern.o
        g++ -IPNG/include  -o readpattern readpattern.o libcorona.a -lpng -ljpeg

Code

void do_start_extract_char(char **output, int x, int y, int width, int height) {

    //if pixel location croses boundary then return
    if (x < 0 || y < 0 || x > width - 1 || y > height - 1) {
        return;
    }

    //if the same pixel has already been visited then just return
    if (output[y][x]) {
        return;
    }

    if (isUsefulPixel(x, y)) {
        //store it

        output[y][x] = 1;

    } else {

        return;
    }


    //process left
    do_start_extract_char(output, x - 1, y, width, height);


    //process down
    do_start_extract_char(output, x, y + 1, width, height);


    //process right
    do_start_extract_char(output, x + 1, y, width, height);

//process up
    do_start_extract_char(output, x, y - 1, width, height);

    //process left-down diagonally
    //          /
    //         /
    do_start_extract_char(output, x - 1, y + 1, width, height);

    //process left-up diagonally
    //        \
    //         \
    do_start_extract_char(output, x - 1, y - 1, width, height);


    //process right-down diagonally
    //          \
    //           \
    do_start_extract_char(output, x + 1, y + 1, width, height);

    //process right-up diagonally
    //            /
    //           /
    do_start_extract_char(output, x + 1, y - 1, width, height);


    return;

}

回答1:

Starting from most pixels, going left, down, right and up recursively is enough to cover every single pixel in the entire image.

Left-down pixels would only be the way a pixel is reached when a pixel cannot be reached via left, down, right and up.

Note that naive recursion is a bad plan here. If your image has a few billion pixels, that means the first call may ends up with a few billion recursive calls. And that can blow your stack.

Instead, maintain your own stack of pixels to visit, and recurse by queuing up more tasks in there.

struct location {
  int x,y;
};
bool visited_already(bool const*const* visit_flag, location l) {
  return visit_flag[l.y][l.x];
}
struct size {
  int x,y;
};
struct rectangle {
  location l;
  size s;
};
bool in_bounds( location l, rectangle b ) {
  if (l.x < b.l.x || l.y < b.l.y) return false;
  if (l.x >= b.l.x+b.s.x || l.y >= b.l.y+b.s.y) return false;
  return true;
}

bool do_visit(char*const* output, location l) {
  if (isUsefulPixel(l.x, l.y)) {
    output[l.y][l.x] = 1;
    return true;
  } else {
    return false;
  }
}

using todo_list = std::vector<location>;

bool extract_char( char*const* output, bool*const*visited, location where, rectangle bounds) {
  if (!in_bounds(where, bounds)) return false;
  if (visited_already(visited, where)) return false;
  visited[where.y][where.x] = 1;
  return do_visit(output, where);
}

void extract_chars(char*const* output, bool*const*visited, todo_list& list, rectangle bounds)
{
  while (!list.empty()) {
    auto next = list.back();
    list.pop_back();
    if (extract_char(output, visited, next, bounds))
    {
      list.push_back( {l.x+1, l.y-1} );
      list.push_back( {l.x+1, l.y+0} );
      list.push_back( {l.x+1, l.y+1} );
      list.push_back( {l.x+0, l.y-1} );
      list.push_back( {l.x+0, l.y+0} );
      list.push_back( {l.x+0, l.y+1} );
      list.push_back( {l.x-1, l.y-1} );
      list.push_back( {l.x-1, l.y+0} );
      list.push_back( {l.x-1, l.y+1} );
    }
  }
}
void do_start_extract_char(char *const*output, bool*const*visited, location where, rectangle bounds) {
  extract_chars( output, visited, {where}, bounds );
}