Image 8-connectivity without excessive branching?

Question

I'm writing a low level image processing algorithm which needs to do alot of 8-connectivity checks for pixels. For every pixel I often need to check the pixels above it, below it and on its sides and diagonals.

On the edges of the image there are special cases where there are only 5 or 3 neighbors instead of 8 neighbors for a pixels. The naive way to do it is for every access to check if the coordinates are in the right range and if not, return some default value.

I'm looking for a way to avoid all these checks since they introduce a large overhead to the algorithm. Are there any tricks to avoid it altogether?

Answer 1

If there are suitable values for your algorithm, add a 1-pixel border and only check your original pixel data.

Answer 2

For performance-critical code you might do something like the following:

process row 0
for r = 1 to M - 2
  process row r, pixel 0
  for c = 1 to N - 2
    process row r, pixel c 
  process row r, pixel N - 1
process row M - 1

The bulk of the operations are in the inner loop and are branchless. You just handle the first/last row, and the first/last pixel of each row, as special cases. It makes the code bulkier, but that's the nature of the beast when it comes to optimisation.

Answer 3

Or, to turn @Roger's suggestion around, ignore the outermost pixel along each border, if this works for you. In other words, only process the interior pixels of your image.