computer vision « demonstrate 的 blog

Archive for the ‘computer vision’ Category

我们这里讨论两个常见的操作，一个是 filtering，一个是 histogram。

filtering

如果我们仅仅考虑小的卷积核，如 3×3 的，一种简单的实现就是直接将每点的值根据上下左右的算一遍。我们可以将每行上下的指针也拿到，这样就可以在遍历过程中同时获得对应的位置的 pixel 进行计算了。这个计算过程必然是需要在新的空间存放结果。

cv::Vec3b* prev_row, cur_row = im.ptr<cv::Vec3b> (0), next_row = im.ptr<cv::Vec3b> (1) ;
for (int i = 1 ; i < nlm1 ; ++i) {
  prev_row = cur_row ; cur_row = next_row ; next_row = im.ptr<cv::Vec3b> (i+1) ;
  cv::Vec3b* cur_output_row = out.ptr<cv::Vec3b> (i) ;
  // similar init for column
  for (int j = 1 ; j < ncm1 ; ++ j) {
    // visit things we need to compute the output
  }
}

另一种实现是直接调用 cv::filter2D，这是一个依赖于 FFT 的实现，卷积等于 ifft(fft(img) * fft(kernel))，这样可以在频域直接相乘就 OK 了。

cv::filter2D (src, dst, 3, kernel, cv::Point (-1, -1), BORDER_DEFAULT) ;

当然，OpenCV2 提供给我们的工具远远不止这些，它还提供了抽象类 cv::FilterEngine，对应的一些 filter 的基类（cv::BaseFiler、cv::BaseRowFilter 与 cv::BaseColumnFilter），我们可以通过 cv::create* 系获得对应的 filter engine 实例（一般用 cv::Ptr 封装的指针），或者 get*Kernel 获得某些 filtering 函数的 kernel。同时提供了控制边界外插的方式（cv::borderInterpolate）。在此之上，还封装了一些常用的 filter 函数。下面列出来了几种常见 filtering 方法，

createBoxFilter 获得的是矩形里面的均值 filter；
createDerivFilter 获得的是求图片梯度的 filter，这实际上通过 getDerivKernel 然后 getSeparableLinearFilter 获得的，cv::Sobel 和 cv::Scharr 均为这个方法获得的特例；
createGaussianFilter 获得 Gaussian filter，这是通过 getGaussianKernel 然后 getSeparableLinearFilter 获得的，cv::GaussianBlur 是对它的封装；
createLinearFilter 是通过 getLinearFilter 然后通过 cv::filter2D 获得的；与 separable linear filter 相比，后者可以 decompose 成为两维 convolution 的直积，因此前者更为 general 一些；
createMorphologyFilter 是通过 getMorpholologyFilter 然后生成的 filter，cv::dilate、cv::erode 与 cv::morphologyEx 都是这类生成的；相关的还有 getStructuringElement，这个使用的是 sepFilter2D。
createSeparableLinearFilter 很简单了。

有了这些还有比如 cv::bilateralFilter（保持边的 blur），cv::BuildPyramid 获得 Gaussian pyramid 作用在图像获得的序列。

直方图

直方图就是统计 pixel 分布的一种工具，通常我们会为每个 channel 建立若干 bin，然后在遍历图片的过程中计算出对应的编号，如果这一维最大是 $m$ ，当前值为 $v$ ，取 $n$ 个 bin，则 bin 编号为 $v / m * n$ 四舍五入即可。我们拿到了编号序列后，根据遍历多维数组的顺序就能计算出来从 hist.data 开始走多远这个值存放的位置了。

为了方便我们计算直方图，OpenCV2.x 提供了 cv::calcHist。同时为了比较两个 histogram 的差距，提供了 cv::compareHist，这个函数支持 correlation、 $\chi^2$ 、交集和 Bhattacharyya 距离。

通常根据直方图我们可以做 cv::threshold 将图片变成二值的，也可以用所谓 LUT（look up table）进行变换（类似 PS 中的 curve 操作），函数为 cv::LUT。另有所谓 histogram equalization，保证有 p% 的 pixel 的颜色在 2.55p 以下，这通常用 cumulative histogram 作为 LUT 即可。

最后提一下的是通过 histogram 选择颜色的一种策略，即首先选定一个小区域，获得这个区域的 histogram，然后将此作为 LUT，即落入 bin 的像素取对应颜色在选取区域中的比例，某些颜色比较单一的场景可以通过这种技术选择连续的物体。注意事后一般会 normalize 一下。

histogram 本身在 vision 中的应用非常多，不少 feature 的 descriptor 选择它，同时可以用来做颜色相近的 retrieval 等等。

——————
And the king of Sodom went out to meet him after his return from the slaughter of Chedorlaomer, and of the kings that were with him, at the valley of Shaveh, which is the king’s dale.

Written by zt

2012/02/19 at 4:18 PM

Posted in c/c++, computer vision

Tagged with convolution, histogram, image filtering

OpenCV 学习笔记（一）

with one comment

本部分摘自 OpenCV 2: Computer Vision Application Programming Cookbook。原来看的是 OpenCV 1.x 的接口，现在来学习下 OpenCV 2 的一些东西。

I/O

这部分 OpenCV 提供了类似 Matlab 的函数 cv::imread 与 cv::imwrite，而提供的容器是 cv::Mat。与 OpenCV 1.x 里面区别对待 IplImage、CvMat 和 CvMatND 来看，这里实际上是实现了某种一致性，将 cv::Mat 当做一个普适性的 container 来使用。cv::Mat 的数据存放在 data 成员指向的内存区域，一般来说 cv::Mat 的 copy 只是对 header 的复用，这会增加内部对该内存的引用数，这样 copy 的代价降低。

// from opencv2/core/core.hpp
class CV_EXPORTS Mat {
  // many stuffs...
  //! the matrix dimensionality, >= 2
  int dims;
  //! the number of rows and columns or (-1, -1) when the matrix has more than 2 dimensions
  int rows, cols;
  //! pointer to the data
  uchar* data;

  //! pointer to the reference counter;
  // when matrix points to user-allocated data, the pointer is NULL
  int* refcount;
  // ...
} ;

比较重要的是既然现在 cv::Mat 可以存放多维数组了，如何记录对应的维数的？这个依赖于 cv::Mat::MSize，

struct CV_EXPORTS MSize {
  MSize(int* _p);
  Size operator()() const;
  const int& operator[](int i) const;
  int& operator[](int i);
  operator const int*() const;
  bool operator == (const MSize& sz) const;
  bool operator != (const MSize& sz) const;
  int* p;
};
MSize size;

这表示我们可以通过 size 成员访问到对应的维数信息。

另外，为了方便存放图片，我们有两种策略，一个是创建一个 3D 的数组，这样每个 channel 对应一个常意下的矩阵（Matlab 读入数据后就是这样组织的），但这样对某些操作显得繁琐；另一种策略就是干脆重新定义元素的类型，使得每个元素本身就能存放几个值。为此 OpenCV 2 引入了一个 cv::Vec 的 template，这是一类特化的 cv::Matx。cv::Matx 是一个模板，它有类型和行列数三个参数，作用是为了存放小规模的矩阵。有不少常用的矩阵类型都直接 typedef 出来了，命名规则是 cv::Matxrct，rct 分别对应行数、列数和类型。这样 cv::Vec<Type, R> 就是 cv::Matx<Type, R, 1> 了，而为了方便某些运算（如取均值、求和），我们还需要 cv::Scalar_ 这个特化的 cv::Vec，本质上是 cv::Vec<Type, 4>。这样我们通过 cv::Vec3u 或者 cv::Vec3f 存放 RGB 三个值就行了。

当然在 OpenCV 2 里面并不是说就没有 cv::MatND，但是它本质上只是 typedef：

typedef Mat MatND; // from opencv2/core/core.hpp

像素的遍历

很重要的一种操作就是遍历像素，从而进行一些常规的操作，如添加噪声，减少使用的颜色数目，前面通过 IO 操作获得 cv::Mat 之后，我们存在几种遍历图片的方式：

cv::Mat im = cv::imread ("some.jpg") ;
if (im.data == NULL) {
  // deal with abnormal cases
}
int nr = im.rows, nc = im.cols ;
for (int i = 0 ; i < nr ; ++ i)
  for (int j = 0 ; j < nc ; ++ j) {
    // visit im.at<Vec3b> (i, j)
  }

一种常见的方式是通过 im.ptr<cv::Vec3b> (i) 获得第 i 行的数据首址，这样的遍历如下：

for (int i = 0 ; i < nr ; ++ i) {
  cv::Vec3b* pr = im.ptr<cv::Vec3b> (i) ;
  for (int j = 0 ; j < nc ; ++ j) {
    // visit im.at<Vec3b> (i, j) with *(pr + j)
  }
}

这两种方式说明，OpenCV 存储数据的方式是将元素对应的值 bind 在一起，继而是按照行来存放，这与 Matlab 使用按照列存放（Fortran 的习惯）是不一样的。前面说了 cv::Mat 还可以存放多维的数组，那么存放一个 $d_1 \times d_2 \times \cdots \times d_k$ 的数组的时候应该是先元素，然后 $d_k$ 个元素对应第 $k$ 维，然后 $d_{k - 1}$ 个对应后两维形成的平面，直到最后是 $d_1$ 个 $(k-1)$ 维的长方体。OpenCV 并没有提供一个多维的 at 模板。但是它提供了一个更有用的 iterator，即 cv::MatIterator_ 模板，我们可以使用 begin 和 end 模板对这样一个多维数组进行遍历，同时，这也使得我们可以直接利用 STL 的 algorithm 来对 cv::Mat 的元素进行操作。

typedef cv::MatIterator_<cv::Vec3b> iter_t ;
for (iter_t iter = im.begin<cv::Vec3b> () ; iter != im.end<cv::Vec3b> (); ++ iter) {
  // visit the pixel with *iter
}

color quantization

这里简单介绍一下 color quantization 的几个做法。color quantization 本身是为了使用更少的几个颜色来表达原来的图像，我们知道 RGB 的 8bit 表示下存在 $256 \times 256 \times 256 = 2^{24}$ 种颜色，简单的做法就是将这些颜色相近的用一种颜色替代，这看起来其实和求 histogram 的时候分 bin 是类似的过程。如果我们分的 bin 个数比较特别，如正好是 2 的倍数，这个过程将非常简洁，利用整数乘除法，我们可以如下处理 $c\mapsto q (c): q(c) = \lfloor \frac{c}{2^k} \rfloor 2^k$ ，这可以用如下两种实现：

typedef cv::MatIterator_<uchar> iter_t ;
int k ;
uchar blk = 1 << k, half = 1 << (k-1), mask = 0xff << k ;
// in one loop
  iter_t iter ;
  *(iter) = (*iter / blk) * blk + half ;
// in another loop
  *(iter) &= mask ;
  *(iter) += half ;

在一篇 CVPR 11 年讲述 saliency 的方法中，它讲述了这样一种 quantization 的策略：

首先将 RGB 分成 $12\times 12 \times 12$ 的 bin，然后每个 bin 里面统计出现 pixel 的个数（对应一个 histogram）；
选择像素个数最多的 bin，个数为占全部像素的 95% 以上的最少 bin 个数；
其他的 bin 里面的像素放在这些被选择的 bin 中最近的 bin 内。

下面是实现这个过程的部分代码。

cv::Mat img = cv::imread (argv [1]) ;

// create a histogram
cv::Mat hist ;
const int channels [] = {0, 1, 2} ;
const float lrange[] = {0, 256} ;
const float* ranges [] = {lrange, lrange, lrange} ;
cv::calcHist (&img, 1, channels, cv::Mat (),
              hist, 3, hist_size, ranges, true, false) ;

// sort
std::vector<int> idx ;
{
  boost::iterator_range <boost::range_detail::integer_iterator<int> > r
    = boost::irange<int> (0, hist_size[0] * hist_size[1] * hist_size[2]) ;
  std::copy (boost::begin (r), boost::end (r),
             std::back_inserter (idx)) ;
  std::sort (idx.begin (), idx.end (),
             boost::indirect_cmp<ipmap_cvmat, std::greater<float> >
             (ipmap_cvmat (hist.begin<float> ()))) ;
}

unsigned long total_pixels = img.rows * img.cols ;
float s = 0.0, thres = 0.95 * total_pixels ;
int n_colors = 0 ;
for (int i = 0 ; i < idx.size (); ++ i) {
  s += *(hist.begin<float> () + idx[i]) ;
  if (s > thres) {
    n_colors = i + 1 ;
    break ;
  }
}

// build a map for compression
std::map<int, int> dict ;
{
  typedef std::map<int, int>::value_type pair_t ;

  for (int i = 0 ; i < n_colors ; ++ i)
    dict.insert (pair_t (idx[i], i)) ;

  for (int i = n_colors ; i < idx.size (); ++ i) {
    float min_dist = std::numeric_limits<float>::infinity () ;
    int min_dist_idx ;
    for (int j = 0 ; j < n_colors ; ++ j) {
      float cur_dist = dist (idx[i], idx [j], dims) ;
      if (cur_dist < min_dist) {
        min_dist = cur_dist ;
        min_dist_idx = j ;
      }
    }
    dict.insert (pair_t (idx[i], min_dist_idx)) ;
    *(hist.begin<float> () + idx [min_dist_idx]) +=
      *(hist.begin<float> () + idx[i]) ;
  }
}

这里利用了几个重要的工具，boost 的 indirect_cmp、property map 以及 STL 的 sort。

——————
And they returned, and came to Enmishpat, which is Kadesh, and smote all the country of the Amalekites, and also the Amorites, that dwelled in Hazezontamar.

Written by zt

2012/02/13 at 4:59 PM

Posted in c/c++, computer vision

Tagged with OpenCV

S	M	T	W	T	F	S
« Apr
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

demonstrate 的 blog

Archive for the ‘computer vision’ Category

关于 visual saliency

OpenCV 学习笔记（二）

OpenCV 学习笔记（一）

争分夺秒

七嘴八舌

叽叽喳喳

本草纲目

穷搜猛索

friends

my online albums

my own blogs

长篇大论

无用操作

千夫已指

鸟言鸟语

机器请阅

Follow “demonstrate 的 blog”