[Code] Mixture-of-Gaussian C++ 实现

一个拟合高斯混合模型(GMM)的C++实现: https://github.com/CVLearner/Mixture-of-Gaussians

只依赖于Eigen,但是因为Eigen可以用到MKL的LAPACK/BLAS实现,所以间接地可以利用MKL加速。相比于OpenCV的实现,一个好处是可以用到多核。所以目前速度尚可,但还有提升空间。感觉上Eigen并没有完全利用到MKL的速度。

[Bug] g++4.6 参数顺序

遇到一个bug, 看起来像是g++-4.6的问题。

问题是这样的。这个源文件用到了OpenCV:

//< file: test.cpp
#include 

int main (int argc, char** argv) {
    cv::Mat image;
    return 0;
}

用这样一行命令编译:

g++-4.6 `pkg-config --libs opencv`  -o test.bin test.cpp

遇到了错误:

/tmp/ccs2MlQz.o: In function `cv::Mat::~Mat()':
test.cpp:(.text._ZN2cv3MatD2Ev[_ZN2cv3MatD5Ev]+0x39): undefined reference to `cv::fastFree(void*)'
/tmp/ccs2MlQz.o: In function `cv::Mat::release()':
test.cpp:(.text._ZN2cv3Mat7releaseEv[cv::Mat::release()]+0x47): undefined reference to `cv::Mat::deallocate()'
collect2: ld returned 1 exit status

错误的原因应该是g++没有正确的链接到OpenCV的库。各种尝试之后发现只要调换一下参数的位置就可以正常编译 -_-!!
改用这样一行命令编译就没有问题了。

g++-4.6 test.cpp `pkg-config --libs opencv`  -o test.bin

具体原因不明,但是如果把g++-4.6换作g++-4.4就没有这个问题。
这行命令也可以正常编译:

g++-4.4 `pkg-config --libs opencv`  -o test.bin test.cpp 

这么看起来很有可能是g++-4.6的bug,或者是改进..?

On 2 dimensional array of C++

I was asked about this today. In practice, I rarely use 2-dimensional array, instead I use vector of vectors.

To allocate a 2-d array on the stack, a C-style array is

int d[2][3];

Then to refer to an element it is like

d[i][j];

To make a dynamical allocation, one can NOT write his code like this

int **wrong_d = new int[2][3];

since the d in int d[2][3]; is not a int**, instead it is of the type

int (*)[3]

or in your evil human words, it is a int[3] pointer.

It is a little tricky to declare a 2-d array dynamically.

int (*d)[3] = new int[2][3];

Or

int v1 = 2;
int (*d)[3] = new int[v1][3];

The number 3 here can NOT be replace by a non-constant. My understanding is that since this value is associated with the type of d, in a strong type language like C/C++ which should be known by the compiler.

We can check the size of variables to verify this interpretation.

 1 #include 
  2 
  3 using namespace std;
  4 
  5 int main(int argc, char **argv)
  6 {
  7     int v1 = 2;
  8     int (*d)[3] = new int[v1][3];
  9     cout << "sizeof(d): " << sizeof(d) << endl;
 10     cout << "sizeof(d[0]): " << sizeof(d[0]) << endl;
 11     cout << "sizeof(d[1]): " << sizeof(d[1]) << endl;
 12     cout << "sizeof(d[0][0]): " << sizeof(d[0][0]) << endl;
 13     return 0;
 14 }

The output is:

$./test 
sizeof(d): 8        //< 2 pointers, &d[0] and &d[1]
sizeof(d[0]): 12    //< int[3], d[0][0] d[0][1] d[0][2]
sizeof(d[1]): 12    //< int[3], d[1][0] d[1][1] d[1][2]
sizeof(d[0][0]): 4  //< an integer

To save your life, I would recommend to use vectors.

int v1 = 2;
int v2 = 3;
vector > d(v1, vector(v2, 0)); 

Tips 2013-02-17

  • 如果有需要把工程从Linux下面移植一份到Windows下,却又不熟悉Visual Studio的各种配置,那么用CMake来管理工程是一个不错的选择。从Makefile改写CMakeLists.txt并不麻烦,而且CMake可以自动生成VS的工程文件,很好用。
  • 用 floor 和 ceil 这类函数最好先对参数做显示的类型转换,否则VS会报错。
  • isinf 和 isnan 能不能则不用,VS没有现成好用的对应版本。
  • 关于把一份Git工程同步到SVN的版本库里去的方法,网上讨论的很多,比如这个: http://stackoverflow.com/questions/661018/pushing-an-existing-git-repository-to-svn 但是如果你的Git的工程已经有了悠久历史,那么在rebase那一步你可能会有非常多的conflicts要处理。一个小办法是每次出现了冲突都用这一行代码:
    $git checkout . --theirs && git add . && git rebase --continue

    当然前提是当前目录下面没有不在git管理下的其他文件。这个虽然不解决根本问题,但是会方便很多。

总是有想要重构自己实验工程的想法,看起来工程的框架还是不太好。我总觉得好的框架应该是很容易修改的,现在每次想要往工程里新加一组实验就觉得有些代码碍手碍脚。如果不想有重复代码函数粒度就太小,而且接口复杂不可读,时间一长就看不出它们都是干什么的了。否则就有大段的重复代码,十分难看。如果把实验操作部分放到Bash脚本里面,移植又是一个问题。很少看到讲这种不大的工程怎么去搭框架的问题,苦于自己技术水平不够,想想真是头疼…

PCA的实现

PCA,全称是Principal component analysis,中文叫做主成分分析,是一种常用的数据处理手段。

直观的说,PCA是一种降维的手法。比如现在我们有1000个数据点,每个数据点是一个128维的向量,存储上可以是一个1000×128维的数组。经过PCA处理,我们仍然得到1000个数据点,但是每个数据点是一个小于128维的向量,比如我们用PCA将128维的数据降到64维。
PCA可以保证,在降维之后,数据表示的信息损失最小。

“损失最小”具体怎么定义?
还是以1000个128维的点为例,这1000个点,也就是1000个向量在一个128维的空间中。从在任何一维,也就是一个方向上来看,如果在这个方向上,各个向量大小差异很大,那么这个方向是很重要的。
也就是,反过来看,如果在某个方向上,每一个向量大小都很接近,那么如果不考虑这个方向,也就是去掉这一维的数据,对我们分析这1000个点并没有多大的影响。所以,“损失最小”对应着“差异最小”。

那么具体怎么做呢?

这里是两种常用的方法: SVD分解和EIG分解(特征值分解)。
共同点在于先从数据得到一个矩阵M,M的特征值个数对应着数据的维度,特征值越大那么对应的这一维越重要,也就是“差异越大”。

SVD分解, matlab

    sub_input_data = (input_data - repmat(mean(input_data),count,1))/sqrt(count-1);
    [U,S,V] = svd(sub_input_data);
    % First out_dim columns as PCA bases
    pcaV = V(:,1:out_dim);
    output_data = input_data * pcaV;

EIG分解, matlab

    mean_input_data = mean(input_data);
    sub_input_data = input_data - repmat(mean_input_data, count,1);
    mean_mat = sub_input_data' * sub_input_data ./ (count - 1);
    cov_mat = mean_mat;
    [V D] = eig(cov_mat);
    % Last out_dim columns as PCA bases
    pcaV = V(:,in_dim - out_dim + 1: in_dim);
    output_data = input_data * pcaV;

如果用C++的话,OpenCV本身就提供PCA,当然也可以自己实现。
OpenCV下可以用这个方法做EIG分解。

cv::eigen(covMat, eigenValues, eigenVectors);

具体Matlab代码也比较简单,放在Github上了。
MatlabPCA

原始数据:

PCA之后:

fstream issue under 64-bits cygwin

This is a question I posted on StackOverflow: fstream issue under 64-bits cygwin, glad to get help from Nemo on Stackflow, all credits goes to him.

The problem is when I use 64-bits g++ to compile the same piece of code, I get unexpected different result.

The source code looks like this:

#include 
#include 
using namespace std;

int main()
{
    int rows = 200;
    int cols = 200;
    float data[rows*cols];
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            data[i*cols+j] = i*cols+j;
        }
    }
    const char *file = "tmp.txt";
    ofstream fs(file);
    if (fs.is_open())
    {
        fs.write((char*)&rows, sizeof(int));
        cout << fs.tellp() << endl;
        fs.write((char*)&cols, sizeof(int));
        cout << fs.tellp() << endl;
        fs.write((char*)data, sizeof(float)*rows*cols);
        cout << fs.tellp() << endl;
        fs.close();
    }
    return 0;
}

I am writing two integers and a block of float values into a binary file. It prints out how many bytes it wrote.

The expected result is:

4
8
160008

All the actions were performed under Cygwin. When the code was compiled with g++.exe, the result is right.

But when I use x86_64-w64-mingw32-g++.exe (only by which can generate 64-bits binary), the result is wired.

4
8
160506

It is wired.

According to Nemo's answer, this is because by default fstream will be opened in binary mode under *nix. This also holds for 32 bits g++ under Cygwin, but not for 64 bits cygwin g++.

It leads to an unexpected behavior, fstream will replace some special bytes, say 'newline' in the binary data, with different special bytes, say 'unix-style newline'.

To solve this problem, replace the line

ofstream fs(file);

with

ofstream fs(file,ios_base::binary);

We can alter the content of the float data array to see what will happen.

#include 
#include 
using namespace std;

int main()
{
    int rows = 200;
    int cols = 200;
    float data[rows*cols];
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            data[i*cols+j] = 0;
        }
    }
    const char *file = "tmp.txt";
    ofstream fs(file);
    if (fs.is_open())
    {
        fs.write((char*)&rows, sizeof(int));
        cout << fs.tellp() << endl;
        fs.write((char*)&cols, sizeof(int));
        cout << fs.tellp() << endl;
        fs.write((char*)data, sizeof(float)*rows*cols);
        cout << fs.tellp() << endl;
        fs.close();
    }
    return 0;
}

The output is:

4
8
160208

It somehow supports the above explanation.

UnitTest框架GoogleTest

回到C++下,随着代码量增加,遇到维护问题了。
找到一个Google的UnitTest框架,GoogleTest
有很详细的Sample,推荐一下 :]

编译的时候需要先编译出libgtest.a和gtest_main.o,自己的testXX.cpp文件需要和ligtest.a, gtest_main.o链接。

$g++ testXX.cpp path/to/gtest_main.o -Lpath/to/libgtest.a -lgtest -o testXX