Our authors use STL algorithms, the median-filtering algorithm, and sliding windows to solve advanced image-processing problems.

November 01, 2003
URL:http://drdobbs.com/data-structure-independent-algorithms-fo/184401715

Figure 1: Determining conformance with the STL.

Figure 2: Image with speckle noise.

Figure 3: Result of a 3×3 median filter.

Figure 4: New iterator categories.

Listing 1: Textbook implementation of median filtering.

void medianFilter(const Image &in, size_t subWindowSize, Image &out) {
  const int offset = subWindowSize / 2;
  const size_t center = (subWindowSize * subWindowSize) / 2;
  std::vector<unsigned char> tmp(SubWindowSize * SubWindowSize);
  for (int y = 0; y < in.height(); ++y) {
    for (int x = 0; x < in.width(); ++x) {
      for (int yp = y - offset, i = 0; yp <= y + offset; ++yp) {
        for (int xp = x - offset; xp <= x + offset; ++xp, ++i) {
          if ((xp < in.width()) && 
              (xp >= 0) && 
              (yp < in.height()) && 
              (yp >= 0)) {
            tmp[i] = in.get(xp, yp);
          } else  {
            tmp[i] = 0;
          }
        }
      }
      std::nth_element(tmp.begin(), tmp.begin() + center, tmp.end());
      out.set(x, y) = tmp[center];
    }
  }
}    

Listing 2: STL-compliant median filter.

// functor
template<size_t SubWindowWidth> struct MedianFiltering {  
  template<typename SubWindow>
  inline unsigned char operator()(SubWindow &in) {
    std::copy(in.begin(), in.end(), tmp.begin());
    std::nth_element(tmp.begin(), 
                     tmp.begin() + (SubWindowWidth * SubWindowWidth) / 2, 
                     tmp.end());
    return data[(SubWindowWidth * SubWindowWidth) / 2];
  }
  unsigned char tmp[SubWindowWidth * SubWindowWidth];
};
// process all pixels
int main(...) {
  std::transform(windowsBegin(in), windowsEnd(in),
                 sequentialBegin(out), MedianFiltering());
}

Listing 3: Window iterator design.

template<size_t _SubWidth, size_t _SubHeight, typename _Tp> class Window {
  public:
  typedef SubWindow<_SubWidth, _SubHeight, _Tp> SubWindow;
  // the nested iterator definition
  class iterator : public std::iterator<std::forward_iterator_tag, _Tp> {
    // dereference to get a subwindow buffer (must update to current
    // pixel first)
    inline SubWindow &operator*() {
      subWindow_.reset(x_, y_);
      return subWindow_;
    }
    // advance preserving spatial location in image
    inline iterator & operator ++(void) {
      ++x_;
      if (x_ == width_) {
        x_ = 0;
        ++y_;
      }
      return *this;
    }
    // remaining methods and  data members omitted for brevity
    // ...
  };
  // constructor caches the data pointer and dimensions
  Window(_Tp *in, size_t width, size_t height);
  // Access the iterator pair, must reset before returning. Note
  // returning a reference for efficiency
  inline iterator &begin() {
    begin_.x_ = 0;
    begin_.y_ = 0;
    return begin_;
  }
  inline iterator &end()   {
    end_.x_   = 0;
    end_.y_   = end_.height_;
    return end_;
  }    
  private:
  // current subwindow pair stored to reduce number of temporaries
  // that must be created
  iterator begin_;
  iterator end_;    
};

Listing 4: Subwindow iterator design.

template<size_t _SubWidth, size_t _SubHeight, typename _Tp>
class SubWindow: public std::iterator<heavy_forward_iterator_tag, _Tp>
{
  public:
  // the nested iterator definition
  class iterator: public std::iterator<std::forward_iterator_tag, _Tp>  {
    // dereference, add padding if necessary
    inline _Tp operator*(void) const {        
      if ((x_ < 0) || (y_ < 0) || (x_ >= width_) || (y_ >= yOffImage_)) {
        return 0;
      }
      return begin_[y_ + x_];
    }
    // advance preserving spatial location in image
    inline iterator & operator ++(void) {
      x_ += 1;
      if (x_ > stopX_) {
        x_  = startX_;
        y_ += width_;
      }
      return *this;
    }
    // get the lightweight proxy
    proxy_iterator operator&(void)
    {
      return proxy_iterator(this);
    }
    // remaining methods and  data members omitted for brevity
    // ...
  };
  // define a proxy for reducing copy overhead
  class proxy_iterator: public std::iterator<std::forward_iterator_tag, _Tp> {
    // pass operation along to addressee
    inline proxy_iterator& operator++(void)  {
      addressee_->operator++();
      return *this;
    }
    // remaining methods and  data members omitted for brevity
    // ...
  };
  // Access the iterator pair. Note returning a reference for efficiency
  inline iterator &begin()  {
    return begin_;
  }
  inline iterator &end()  {
    return end_;
  }
  // set the position in the larger image (see downloadable code)
  inline void reset(size_t x, size_t y);
  // constructor caches the data pointer and dimensions
  SubWindow(_Tp *in, int width, int height);
private:
  // current location
  iterator begin_;
  iterator end_;
};

Listing 5: Generalized convolution and morphological erosion operations.

template<size_t _SubWidth, size_t _SubHeight, typename _KernelIterator>
    struct Convolution  {
    Convolution(_KernelIterator kernel) : kernel_(kernel)    {
    }
    template<typename SubWindow> inline 
      std::iterator_traits<SubWindow>::value_type
      operator()(SubWindow &in) {
        typename std::iterator_traits<_KernelIterator>::value_type tmp = 0;
        return std::inner_product(in.begin(),in.end(),kernel_,tmp);
    }
   _KernelIterator kernel_;
};
template<size_t _SubWidth, size_t _SubHeight> struct Erode  {
    template<typename SubWindow> inline bool
      operator()(SubWindow &in)    {
        const typename SubWindow::iterator m = std::min_element(in.begin(),
                                                                in.end());
        return (*m == 0);
    }
};

Image Processing

Image processing is the art of transforming 2D-arrays of picture elements — pixels. While the list of popular image-processing transformations is long, you can break down the majority of algorithms into three categories based on how the algorithms access pixels: sequential, random access, or sliding windows.

Algorithms in the sequential category process pixels independently and do not care about the spatial location of those pixels in the image. Example sequential algorithms include adding two images, thresholding images, and gamma correction. The idea behind gamma correction is to adjust the slope of the change in intensity from white to black by changing the value of a pixel x to some new value f(x) based on the function f(x)=x^1/. Gamma correction can be used to increase or decrease the overall brightness of an image.

Random-access algorithms determine the next pixel to visit based on some computation performed at the current pixel. An example of such an algorithm is tracking eyes on a face from image frame to image frame.

Sliding window operations, the most common image-processing algorithms, are conceptually defined as two-dimensional matrices (kernels) that are passed over the image. The kernel is centered over each pixel in the image and some type of operation is performed over the pixels lying under the kernel. The result of the operation is a new pixel value. Examples of typical kernels are 3×3 or 5×5 squares, however, kernels are not restricted to fixed sizes and can be of any arbitrary shape. Example operations are convolution (where each pixel in the kernel is multiplied by the corresponding image pixel and the result is summed) and median filtering (where each pixel in the image from the kernel is sorted and the median is returned as the best value). Figure 2 shows an image with speckle noise and Figure 3 shows the result of a 3×3 median filter.

— V.A., M.R.S., and J.B.P.

Back to Article

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.