OpenCV中KdTree的用法

编程入门行业动态更新时间:2024-10-25 01:26:42

OpenCV中KdTree的用法

KdTree是一种非常好用的搜索算法。特别是在处理高维度数据时，仅通过KdTree进行近邻搜索，就能获取到不错的模糊搜索效果。

对于OpenCV这样的老牌优秀图像库，自然是提供了KdTree函数的。下面我们来通过一个小例子简单介绍下OpenCV中KdTree的用法。

这个例子的目的是输入一张图片，然后我们根据图片的内容，将其转换为ascii字符的形式输出。这就要求每一个ascii字符要建立一个图素，比如8x8像素的图素，或是16x16、32x32像素的图素等。我们通过OpenCV将ascii字符打印到一个i乘j的小图片上。其中i和j分别为图素的宽和高，一般i和j是相同的，比如都是8、16、32等。然后将该小图片转换为一维向量。最后将所有的图素一维向量组成一个矩阵，矩阵大小是m x n，m是行数即样本数，也即图素数，也即ascii字符数；相应的n为图素的像素数，也就是前文提到的i乘j。这个矩阵将会输入到KdTree中用来建立KdTree。建立好后，用户即可以通过该KdTree进行搜索。

先看一段代码。如下：

#include <iostream>
#include <fstream>
#include <opencv2/opencv.hpp>
#include <opencv2/flann.hpp>cv::Mat char2Mat(uchar c, int width = 32, int height = 32, float scale = 1.0f, int fontFace = cv::FONT_HERSHEY_DUPLEX)
{cv::Size elemSize(width, height);cv::Mat elem(elemSize, CV_8UC1, cv::Scalar(0));int baseline = 0;std::string text;text += c;cv::Size textSize = cv::getTextSize(text, fontFace, scale, 1, &baseline);std::cout << "baseline = " << baseline << std::endl;std::cout << "text size of " << text << " = " << textSize << std::endl;cv::Point textPos((elemSize.width - textSize.width) / 2, elemSize.height - (elemSize.height - textSize.height) / 2 - 2);cv::putText(elem, text, textPos, fontFace, 1, cv::Scalar(255), scale, 8);elem.convertTo(elem, CV_32F);return elem.reshape(1, 1);
}int main(int argc, char** argv)
{// 通过命令行参数设置要转换的图片名。std::string filename;if (argc == 2){filename = std::string(argv[1]);}// 设置图素大小int elemSize = 8;// 在ascii字符集中选取32到126之间的字符作为图素点阵std::vector<uchar> chars;std::map<int, uchar> dic;for (int i = 32; i <= 126; i++){chars.push_back(static_cast<uchar>(i));dic[i - 32] = static_cast<uchar>(i);}//cv::Mat_<float> samples(0, elemSize * elemSize);    // 使用该行声明，与下一行作用相同。cv::Mat samples(0, elemSize * elemSize, CV_32F);    // 将ascii字符写到elem x elem大小的点阵中，然后生成一个1 x (elemSizex elemSize)大小的向量，作为一个数据样本。for (int i = 0; i < chars.size(); i++){cv::Mat elem = char2Mat(chars[i], elemSize, elemSize);std::cout << elem.size() << std::endl;samples.push_back(elem);}// 最后再补充两个图素点阵，用于处理全黑与全白的情况。cv::Mat_<float> white(0, elemSize * elemSize, 255.f);cv::Mat_<float> black(0, elemSize * elemSize, 0.f);samples.push_back(white);dic[samples.rows - 1] = '@';samples.push_back(black);dic[samples.rows - 1] = ' ';// 创建KdTree，方向是使用cv::flann::Indexcv::flann::Index flannIndex(samples, cv::flann::KDTreeIndexParams(1));// 从命令行参数读取一张图片，作为待转换的图片。cv::Mat image = cv::imread(filename);cv::cvtColor(image, image, cv::COLOR_BGR2GRAY);    // 转为灰度图。image = 255 - image;    // 视图片情况，可以给图片反一下色。//cv::imshow("image", image);    // 去掉注释，可以显示图片预览。// 对图片做一点小小的处理，使图片的宽高正好是图素宽高的整数倍int imgWidth = image.cols / elemSize * elemSize;int imgHeight = image.rows / elemSize * elemSize;cv::resize(image, image, cv::Size(imgWidth, imgHeight), 0.0, 0.0, cv::INTERSECT_NONE);// 将结果转出到文本文件中std::ofstream file;file.open("result.txt", std::ios_base::trunc | std::ios_base::out);// 遍历图片，每个elemSize x elemSize的子区域通过KdTree找到最接近的图素，然后再找到对应的ascii字符，将其输出。for (int j = 0; j < imgHeight; j += elemSize){for (int i = 0; i < imgWidth; i += elemSize){cv::Mat roi = image(cv::Rect(i, j, elemSize, elemSize));cv::Mat query(elemSize, elemSize, CV_32F);roi.convertTo(query, CV_32F);query = query.reshape(1, 1);cv::Mat indices, dists;flannIndex.knnSearch(query, indices, dists, 1);char chr = dic[indices.ptr<int>(0)[0]];std::cout << chr;file.write(&chr, 1);}std::cout << std::endl;file << std::endl;}file.close();cv::waitKey(0);return 0;
}

该段代码中真正与KdTree相关的代码不多，主要就是

cv::flann::Index flannIndex(samples, cv::flann::KDTreeIndexParams(1));

这一句。这里要注意的是：第一个参数samples是输入的数据集，用于创建KdTree，是样本集合，用矩阵的形式。每个样本是这个矩阵中的一行。所以如果用户要用图片作为样本的话，就必须把图片转换为一个行向量。因而我们可以在char2Mat这个函数中看到如下的代码：

return elem.reshape(1, 1)；

这句代码的作用即是将一个普通的图片矩阵转为只有一行的向量。第二个参数，大家可以直接去OpenCV中看一下它的参数说明，里面有更详细的解释。

这里还要注意的是，OpenCV中的KdTree中是用Flann来实现的。它要求提供的数据输入必须是32位浮点型。所以，切记，要把你的Mat转换为CV_32F。这里，我们的代码中均做了处理，如下：

1. 在函数char2Mat中，我们在倒数第二行用了 elem.converTo(elem. CV_32F)；将elem转换为32位浮点型。

2. 在main函数中声明samples数据集时，也是用的CV_32F。

3. 在main函数中最后一段双循环中，也是用了roi.convertTo(query. CV_32F)；把roi中的小图像矩阵转换为CV_32F类型。

如果用户不做该处理，是必然会得到OpenCV提示的数据类型错误的。

最后，使用KdTree执行搜索用的是knnSearch函数，即按近邻数搜索。当然大家也可以使用radiusSearch，即半径搜索。

我提供一个运行后的示例：