- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我写了一个 k-means 聚类算法和一个颜色量化算法。它们在结果方面按预期工作,但我想让它们更快。在这两种实现中我都需要解决一个问题:在 3D 空间中有两个点数组,然后对于第一个数组中的每个点,你需要从第二个数组中找到最近的点。我这样做:
size_t closest_cluster_index;
double x_dif, y_dif, z_dif;
double old_distance;
double new_distance;
for (auto point = points.begin(); point != points.end(); point++)
{
//FIX
//as suggested by juvian
//K = 1
if (point != points.begin())
{
auto cluster = &(clusters[closest_cluster_index]);
r_dif = cluster->r - point->r;
g_dif = cluster->g - point->g;
b_dif = cluster->b - point->b;
new_distance = r_dif * r_dif + g_dif * g_dif + b_dif * b_dif;
if (new_distance <= std::sqrt(old_distance) - ColorU8::differenceRGB(*(point - 1), *point))
{
old_distance = new_distance;
//do sth with closest_cluster_index;
continue;
}
}
//END OF FIX
old_distance = std::numeric_limits<double>::infinity();
for (auto cluster = clusters.begin(); cluster != clusters.end(); cluster++)
{
x_dif = cluster->x - point->x;
y_dif = cluster->y - point->y;
z_dif = cluster->z - point->z;
new_distance = x_dif * x_dif + y_dif * y_dif + z_dif * z_dif;
if (new_distance < old_distance)
{
old_distance = new_distance;
closest_cluster_index = cluster - clusters.begin();
}
}
//do sth with: closest_cluster_index
}
我该如何改进它?(我不想让它成为多线程或由 GPU 计算)
最佳答案
有多种数据结构可用于高效的最近邻查询。对于 3d,一个 kdtree工作得很好,平均每个查询的复杂度为 O(log n),这将改善您当前的 O(n)。
因此,使用此结构,您可以将集群中的所有点添加到其中,然后对于 points 中的每个点,您可以使用该结构查询最近的点。对于您的特定情况,静态 kdtree 就足够了,因为您不需要更新点。
另一种方法:
我们可以尝试冒险对某些点进行额外的计算,以换取对其他点进行更少的计算。此方法应适用于以下假设:
我认为这些适用于您的情况,因为您的聚类颜色很少,而且您的点来自真实图像,而真实图像往往在相邻像素之间具有相似的颜色。
对于每个点,创建一个堆。不是存储最近的集群,而是存储在 max heap 中最近的 k 个簇。当您移动到下一个点时,我们可以使用此信息。我们将此点称为 P 及其第 k 个最接近的簇 C。
现在对于一个新点 P2,在与所有集群进行比较之前,我们将检查离 P2 最近的集群是否在我们的堆中。仅当来自堆的任何集群与 P2 之间的距离 <= distance(P, C) - distance(P, P2) 时,这才为真。当这成立时,我们可以只检查我们的堆而不是所有集群。如果不成立,我们将与所有人进行比较并重建我们的堆,P 将是 P2。
您需要尝试不同的 k 值,看看它是否有所改善。对于 K = 2 的情况,可能值得避免增加堆的复杂性并仅使用变量。
关于c++ - 最近点算法 |如何改进?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53264167/
我对编码还比较陌生,但并非完全没有经验。处理有关金融计算器的学校作业。如果你们中的任何人可以查看我的代码以了解不良做法/可能的改进等,那就太好了。 我确实添加了一个“动画”启动(有很多 printf
小目标Trick 论文链接: https://paperswithcode.com/paper/slicing-aided-hyper-inference-and-fine-tuning 代码链接:h
if (firstPositionCpc && (firstPosition > 0 && firstPositionCpc 0 && topOfPageCpc 0 && firstPageCpc
我有 2 个表:“packages”和“items”。 “packages”有以下列:pack_id | item_id “items”有以下列......:item_id |输入 一个包可以有多个
我目前有一个 Pandas Dataframe,我在其中执行列之间的比较。我发现一种情况,在进行比较时存在空列,由于某种原因比较返回 else 值。我添加了一个额外的语句来将其清理为空。看看我是否可以
我正在处理一个查询,通过首先舍入它们的主要日期时间键来连接一个数据库中的多个表。数据库包含来自 openhab 的性能数据,每个表只有一个名为 Time 的主日期时间行和一个名为 Value 的值行。
问候 我有一个程序创建一个类的多个实例,在所有实例上运行相同的长时间运行的 Update 方法并等待完成。我从 this question 开始关注 Kev 的方法将更新添加到 ThreadPool.
我想在下学期的类(class)中取得领先,所以我制作了这个基本版本的 Blackjack 来开始理解 C 的基础知识,我希望您有任何想法可以帮助我更好地理解 C 和其正常的编码实践。 C 中的很多东西
我有一个要求,比如: 给定一个数组,其中包含随机数。需要输出元素出现的次数,有自带解决方案: var myArr = [3,2,1,2,3,1,4,5,4,6,7,7,9,1,123,0,123];
这是我的数据库项目。 表user_ select id, name from user_; id | name ----+---------- 1 | bartek 2 | bartek
我已经完成了一个小批量脚本来调整(动态)一些图像的大小: for a in *.{png,PNG,jpg,JPG,jpeg,JPEG,bmp,BMP} ; do convert "$a" -resiz
是否有更 pythonic 的方法来执行以下代码?我想在一行中完成 parsed_rows 是一个可以返回大小为 3 或 None 的元组的函数。 parsed_rows = [ parse_row(
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题? 更新问题,以便 editing this post 可以用事实和引用来回答它. 关闭 9 年前。 Improv
下面的代码完成了我想要的,但还有其他更像 python 风格的方式吗? 文件格式: key1:value1,key2:value2,... key21:value21,key22:value22,..
如果两个英文单词只包含相同的字母,则它们是相似的。例如,food 和 good 不相似,但 dog 和 good 相似。 (如果A与B相似,则A中的所有字母都包含在B中,B中的所有字母都包含在A中。)
我有以下结构来表示二叉树: typedef struct node *pnode; typedef struct node { int val; pnode left; pnode
我有一个区域,它由受约束的 delaunay 三角剖分表示。我正在解决在两点之间寻找路径的问题。我正在使用 Marcelo Kallmann 提供的论文作为解决此问题的引用点。然而,而不是使用 Kal
如果我需要检查文本(字符串)中是否存在单词 A 或单词 B,如果我这样做会有性能差异: if(text.contains(wordA) || text.contains(wordB)) 要使用一些正则
Adjust To 我有上面这个简单的页面,上面有一个标签和一个文本框。我想在文本框中输入文本。 对我有帮助的 XPATH 是 //*[contains(tex
以下伪代码的elisp代码 if "the emacs version is less than 23.1.x" do something else something-else 写成 (if
我是一名优秀的程序员,十分优秀!