数据的均匀化分割算法(网格划分法、四叉树法(含C++代码))

2024-05-12 01:28

本文主要是介绍数据的均匀化分割算法(网格划分法、四叉树法(含C++代码)),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数据的均匀化分割主要是指在分割过程中尽可能均匀地将数据点分布在各个子区域中,以保持数据分布的平衡和优化数据结构的性能。以下是几种可以实现数据均匀化分割的方法:

一. 网格划分法

1. 基本概念

        虽然传统的网格划分法不是动态调整的,但通过设计可以实现均匀的空间分割。例如,可以根据数据点的分布密度来调整网格的划分粒度,使得每个网格单元内包含的数据点数量尽量均匀。

        具体的,二维网格划分是一种对二维空间进行均匀分割的技术,用于将这种空间划分为多个小的、有时是规则的区域或单元,称为“网格”或“格子”。在图像处理中,二维网格划分可以用于将图像划分成小块进行局部分析或并行处理,从而加速图像处理任务如滤波、特征检测等。

2. 示例

  我有一组特征点存储在 std::vector<cv::KeyPoint> 类型的变量 vToDistributeKeys 中。这些特征点位于一张大小为宽1276像素、高378像素的图片上。为了在二维空间上实现点的均匀分布,我需要将图片分割成一个6x6的网格(共36个方块)。在每个方块内,我希望只保留具有最大置信度的特征点,并删除该方块内的其他点。下面是实现这一功能的具体C++代码。

#include <iostream>
#include <vector>
#include <opencv2/core/types.hpp>// 将特征点按网格均匀分布,每个网格只保留置信度最高的特征点
std::vector<cv::KeyPoint> distributeAndFilterKeys(const std::vector<cv::KeyPoint>& keypoints, int width, int height, int gridRows, int gridCols) {// 计算每个网格的尺寸int cellWidth = width / gridCols;int cellHeight = height / gridRows;// 初始化网格,用于存储每个网格的最高置信度的特征点std::vector<std::vector<cv::KeyPoint>> grid(gridRows, std::vector<cv::KeyPoint>(gridCols));// 遍历所有特征点for (const auto& keypoint : keypoints) {int gridX = keypoint.pt.x / cellWidth;int gridY = keypoint.pt.y / cellHeight;// 确保网格索引不越界if (gridX >= gridCols) gridX = gridCols - 1;if (gridY >= gridRows) gridY = gridRows - 1;// 检查当前网格是否已有特征点,或者当前特征点置信度是否更高if (!grid[gridY][gridX].empty() && grid[gridY][gridX][0].response < keypoint.response) {grid[gridY][gridX][0] = keypoint;} else if (grid[gridY][gridX].empty()) {grid[gridY][gridX].push_back(keypoint);}}// 收集所有网格中的最佳特征点std::vector<cv::KeyPoint> filteredKeyPoints;for (int y = 0; y < gridRows; ++y) {for (int x = 0; x < gridCols; ++x) {if (!grid[y][x].empty()) {filteredKeyPoints.push_back(grid[y][x][0]);}}}return filteredKeyPoints;
}int main() {// 假设的特征点数据std::vector<cv::KeyPoint> keypoints = {{cv::Point2f(100, 50), 1.f, -1, 0.8},{cv::Point2f(120, 60), 1.f, -1, 0.9},{cv::Point2f(130, 55), 1.f, -1, 0.95},// 添加更多点以测试};// 图片尺寸和网格配置int width = 1276;int height = 378;int gridRows = 6;int gridCols = 6;// 处理特征点std::vector<cv::KeyPoint> filteredKeyPoints = distributeAndFilterKeys(keypoints, width, height, gridRows, gridCols);// 输出结果for (const auto& kp : filteredKeyPoints) {std::cout << "Keypoint at (" << kp.pt.x << ", " << kp.pt.y << ") with response: " << kp.response << std::endl;}return 0;
}

二. 四叉树均匀化与非极大值抑制结合使用

在实际应用中,可以先对ORB特征点进行四叉树均匀化,然后再对每个子区域内的特征点进行非极大值抑制。这样可以在保证特征点分布均匀性的同时,提高特征点的质量和稳定性,最终得到更优的特征点集合。

1. 四叉树的基本概念

        在图像中,某些区域可能存在大量的特征点,而其他区域可能只有很少的特征点。这种不均匀分布会影响特征点的代表性和匹配效果。

        首先把一幅图案或一个幅面分割成多个分区或者部分。如果某个子区域内的特征点数量少于某个预设阈值,或者已经达到了分割的最小尺度,则这个子区域不再进行分割。如果特征点过于密集,则继续将这个区域分割成四个更小的子区域,并递归地对每个子区域进行同样的分割过程,直至每个子区域内的特征点数量满足预设条件。

        通过控制划分的停止条件(如特征点数量少于阈值、达到最小分割尺寸等),可以在保证足够的特征点总数的同时,让特征点在图像的不同区域内尽可能均匀分布。

        在划分完成后,每个子区域内可能包含多个特征点。为了进一步提高均匀性和代表性,可以在每个子区域内只保留响应值最大的特征点,去除其他的特征点。

2. 非极大值抑制

        非极大值抑制是一种常用的特征点后处理方法,主要用于去除临近区域内响应值较低的特征点,保留局部最大的特征点。其基本原理是,对于每个特征点,检查其周围邻域内是否存在响应值更大的特征点。如果存在,则将当前特征点去除;如果不存在,则保留当前特征点。

3. 示例

      一组特征点存储在 std::vector<cv::KeyPoint> 类型的变量 vToDistributeKeys 中。这些特征点分布在一张宽为1276像素、高为378像素的图片上。要求将图片分割成至少25个区域。

#include <opencv2/opencv.hpp>
#include <vector>
#include <algorithm>// 定义四叉树节点结构体
struct QuadTreeNode {cv::Rect rect;  // 节点代表的区域std::vector<cv::KeyPoint> keypoints;  // 节点内的特征点QuadTreeNode* children[4];  // 子节点指针QuadTreeNode(cv::Rect _rect) : rect(_rect) {for (int i = 0; i < 4; i++) {children[i] = nullptr;}}
};// 递归建立四叉树
void buildQuadTree(QuadTreeNode* node, const std::vector<cv::KeyPoint>& keypoints, int minPoints, int maxLevel, int level) {if (level >= maxLevel || node->keypoints.size() <= minPoints) {return;}// 将当前节点划分为四个子区域int halfWidth = node->rect.width / 2;int halfHeight = node->rect.height / 2;cv::Rect childRects[4] = {cv::Rect(node->rect.x, node->rect.y, halfWidth, halfHeight),cv::Rect(node->rect.x + halfWidth, node->rect.y, halfWidth, halfHeight),cv::Rect(node->rect.x, node->rect.y + halfHeight, halfWidth, halfHeight),cv::Rect(node->rect.x + halfWidth, node->rect.y + halfHeight, halfWidth, halfHeight)};// 为每个子区域创建子节点for (int i = 0; i < 4; i++) {node->children[i] = new QuadTreeNode(childRects[i]);}// 将特征点分配到子节点中for (const auto& keypoint : node->keypoints) {for (int i = 0; i < 4; i++) {if (node->children[i]->rect.contains(keypoint.pt)) {node->children[i]->keypoints.push_back(keypoint);break;}}}// 递归建立子节点的四叉树for (int i = 0; i < 4; i++) {buildQuadTree(node->children[i], node->children[i]->keypoints, minPoints, maxLevel, level + 1);}
}// 非极大值抑制
void nonMaximumSuppression(std::vector<cv::KeyPoint>& keypoints, float radius) {std::vector<cv::KeyPoint> nmsKeypoints;std::sort(keypoints.begin(), keypoints.end(), [](const cv::KeyPoint& a, const cv::KeyPoint& b) {return a.response > b.response;});std::vector<bool> mask(keypoints.size(), true);for (size_t i = 0; i < keypoints.size(); i++) {if (mask[i]) {nmsKeypoints.push_back(keypoints[i]);for (size_t j = i + 1; j < keypoints.size(); j++) {if (cv::norm(keypoints[i].pt - keypoints[j].pt) <= radius) {mask[j] = false;}}}}keypoints = nmsKeypoints;
}// 四叉树均匀化结合非极大值抑制
void quadTreeUniformNMS(std::vector<cv::KeyPoint>& keypoints, int minPoints, int maxLevel, float nmsRadius) {// 创建根节点QuadTreeNode* root = new QuadTreeNode(cv::Rect(0, 0, 1276, 378));root->keypoints = keypoints;// 建立四叉树buildQuadTree(root, keypoints, minPoints, maxLevel, 0);// 对每个叶子节点进行非极大值抑制std::vector<cv::KeyPoint> uniformKeypoints;std::function<void(QuadTreeNode*)> traverseQuadTree = [&](QuadTreeNode* node) {if (node->children[0] == nullptr) {nonMaximumSuppression(node->keypoints, nmsRadius);uniformKeypoints.insert(uniformKeypoints.end(), node->keypoints.begin(), node->keypoints.end());} else {for (int i = 0; i < 4; i++) {traverseQuadTree(node->children[i]);}}};traverseQuadTree(root);keypoints = uniformKeypoints;// 释放内存std::function<void(QuadTreeNode*)> deleteQuadTree = [&](QuadTreeNode* node) {if (node->children[0] != nullptr) {for (int i = 0; i < 4; i++) {deleteQuadTree(node->children[i]);delete node->children[i];}}};deleteQuadTree(root);delete root;
}int main() {std::vector<cv::KeyPoint> vToDistributeKeys;// ... 初始化 vToDistributeKeys ...int minPoints = 1;  // 每个区域最少特征点数量int maxLevel = 5;  // 最大分割层数float nmsRadius = 10.0f;  // 非极大值抑制半径quadTreeUniformNMS(vToDistributeKeys, minPoints, maxLevel, nmsRadius);// ... 使用均匀化后的特征点 vToDistributeKeys ...return 0;
}

这篇关于数据的均匀化分割算法(网格划分法、四叉树法(含C++代码))的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/981211

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

Hadoop集群数据均衡之磁盘间数据均衡

生产环境,由于硬盘空间不足,往往需要增加一块硬盘。刚加载的硬盘没有数据时,可以执行磁盘数据均衡命令。(Hadoop3.x新特性) plan后面带的节点的名字必须是已经存在的,并且是需要均衡的节点。 如果节点不存在,会报如下错误: 如果节点只有一个硬盘的话,不会创建均衡计划: (1)生成均衡计划 hdfs diskbalancer -plan hadoop102 (2)执行均衡计划 hd

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个