Border Extension for Neighborhood Operations
Handling "Undefined" Pixel Values in Image Processing Algorithms


fig. 1: 2D plot of the cosine hump function.

TODO: Add comparison image showing effects of various commonly-used kernels (Gaussian, edge enhancement, etc.) with different border extension methods.

TODO: Add image per-approach showing the resulting image after adding a "border" and applying the border extension.

"Neighborhood operations" means any process which operates on pixels surrounding a central pixel that is focused on by the algorithm. Linear filters (also called "recursive filters") are a common class of neighborhood operation. These replace each pixel in an image with a weighted sum of the pixels in a neighborhood around the pixel.

Method #0: Skip

This method isn't really a method for handling border pixels at all. ...

This can be combined with the approaches below as a simplification. Rather than add special-case code to the inner loop for a neighborhood operation, the image can be padded with one of the below approaches,

  1. Add border around the image large enough to accommodate the support of the neighborhood operation (i.e., the size of the kernel), populate the border pixels using one of the border extension approaches below.
  2. Use Method #0 on the resulting enlarged image.
  3. Crop the image back to its original size.
The resulting algorithm is simpler than incorporating any of the approaches below directly into the inner loop. I would have called this combo approach an "optimization" as well, except that with modern CPU architectures, adding more data for the sake of a simpler inner loop will not necessarily lead to faster code.

Method #1: Zero-Padding (Zero Extension)

..... Pros:

Cons:

Method #2: Symmetric Extension (Mirror Repeat)

... In the context of the discrete cosine transform (DCT), this is known as Type-II symmetric extension. Pros:

Cons:

Method #3: Periodic Extension (Wrapping Repeat) (GL_REPEAT)

Pros: TODO: Does this preserve the 3 qualities of wavelet-transformations? (find reference to verify).

Cons:

Method #4: Border Replication (GL_CLAMP)

...

The traditional method is to "square" the corners. Another way to go would be to "round" the corners. The general approach is to use the P-norm.

Pros:

Image Processing Frameworks

JAI's convolution operator (ConvolveOp) has two modes of handling edge conditions:

  1. EDGE_ZERO_FILL: default option, fill "undefined" edge pixels with zero.
  2. EDGE_NO_OP: copy pixels into the , ...

Neither mode results in convolution of pixels in the region at the edge of the image. These modes are simply provided for convenience.

JAI provides several BorderExtender sub-classes that correspond to the methods described above:

References

  1. Recursive Filtering of Images with Symmetric Extension. Ben Appleton. 2005. Studies the effects of symmetric extension on linear filters.
  2. Weickert, ter Haar Romeny, Viergever. 1998. Efficient and Reliable Schemes for Nonlinear Diffusion Filtering. Method for recursive Gaussian filtering on an image with symmetric extension of the borders.
  3. Lindeberg. 1998. Scale-Space for Discrete Signals When constructing a linear scale-space, symmetric extension (mirroring) is equivalent to imposing an adiabatic boundary on the related diffusion process. This constraint has the effect of maintaining the total brightness of the image.
  4. MathWorks's site has extensive documentation regarding this topic.
    Linear Filtering: ...
    imfilter: ...
  5. Wikipedia: Neighborhood Operation.
  6. Wikipedia: Discrete Cosine Transform. Discusses border extension issues for 1D signals.