简介 生成树（spanning tree） 在图论中，无向图 \(G=(V,E)\) 的生成树（spanning tree)是具有 \(G\) 的全部顶点，但边数最少的联通子图。假设 \(G\) 中一共有 \(n\) 个顶点，一颗生成树满足下列条件 \(n\) 个顶点； \(n-1\) 条边； \(n\) 个顶点联通； 一个图的生成树可能有多个。 最小生成树（minimum spanning tree， MST）/最小生成森林 ：联通加权无向图中边缘权重加和最小的生成树。给定无向图 \(G=(V,E)\) ， \((u,v)\) 代表顶点 \(u\) 与顶点 \(v\) 的边， \(w(u,v)\) 代表此边的权重，若存在生成树T使得： \[w(T) = \sum_{(u,v)\in T}w(w,v)\] 最小，则 \(T\) 为 \(G\) 的最小生成树。对于非连通无向图来说，它的每一 连通分量 同样有最小生成树，它们的并被称为 最小生成森林 。最小生成树除了继承生成树的性质之外，还存在下面两个特点： 当图的每一条边的权值都相同时，该图的所有生成树都是最小生成树；...
Hough Voting 本文的标题是Deep Hough Voting，先来说一下Hough Voting。 用Hough变换检测直线大家想必都听过：对于一条直线，可以使用 \((r,θ)\) 两个参数进行描述，那么对于图像中的一点，过这个点的直线有很多条，可以生成一系列的 \((r,θ)\) ，在参数平面内就是一条曲线，也就是说，一个点对应着参数平面内的一个曲线。那如果有很多个点，则会在参数平面内生成很多曲线。那么，如果这些点是能构成一条直线的，那么这条直线的参数 \((r,θ)\) 就在每条曲线中都存在，所以看起来就像是多条曲线相交在 \((r,θ)\) 。可以用多条曲线投票的方式来看，其他点都是很少的票数，而 \((r,θ)\) 则票数很多，所以直线的参数就是 \((r,θ)\) 。 所以Hough变换的思想就是在于，在参数空间内进行投票，投票得数高的就是要得到的值。 文中提到的Hough Voting如下： A traditional Hough voting 2D detector comprises an offline and an online step....
3D Model
2026-02-12
三维深度学习简介 多视角（multi-view）：通过多视角二维图片组合为三维物体，此方法将传统CNN应用于多张二维视角的图片，特征被view pooling procedure聚合起来形成三维物体； 体素（volumetric）：通过将物体表现为空间中的体素进行类似于二维的三维卷积（例如，卷积核大小为5x5x5），是规律化的并且易于类比二维的，但同时因为多了一个维度出来，时间和空间复杂度都非常高，目前已经不是主流的方法了； 点云（point clouds）：直接将三维点云抛入网络进行训练，数据量小。主要任务有分类、分割以及大场景下语义分割； 非欧式（manifold，graph）：在流形或图的结构上进行卷积，三维点云可以表现为mesh结构，可以通过点对之间临接关系表现为图的结构。 点云的特性 无序性...
概括 这篇文章将卷积比较自然地拓展到点云的情形，思路很赞！ 文章的主要创新点：“weight function”和“density function”，并能实现translation-invariance和permutation-invariance，可以实现层级化特征提取，而且能自然推广到其deconvolution的情形实现分割，在二维CIFAR-10图像分类任务中精度堪比CNN（表明能够充分近似卷积网络），达到了SOTA的性能。 缺点：每个kernel都需要由“kernel function”生成，而“kernel function”实质上是一个CNN网络，计算量比较大。 思想 察觉到：二维卷积中pixel的相对centroid位置与kernel vector的生成方式有关。 以二维卷积为例说明一下如何将卷积拓展到点云。这里只考虑使用一个kernel在一个location的一次卷积操作。 对于二维图像，我们可以将图像的pixels看作是一个点，那么图像就是整齐排列的点阵。每个point都有维度为 \(C_{in}\)...
160. 相交链表 题目 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交 ： 题目数据 保证 整个链式结构中不存在环。 注意 ，函数返回结果后，链表必须 保持其原始结构 。 自定义评测： 评测系统 的输入如下（你设计的程序 不适用 此输入）： intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。 示例 1： 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2,...
进程 一个在内存中运行的应用程序。每个进程都有自己独立的一块内存空间，一个进程可以有多个线程，比如在Windows系统中，一个运行的xx.exe就是一个进程。 线程 进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据。 与进程不同的是同类的多个线程共享进程的堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是在各个线程之间作切换工作时，负担要比进程小得多，也正因为如此，线程也被称为轻量级进程。 Java 程序天生就是多线程程序，我们可以通过 JMX 来看一下一个普通的 Java 程序有哪些线程，代码如下。 [代码] 上述程序输出如下（输出内容可能不同，不用太纠结下面每个线...
杂七杂八
2026-01-11
分布式深度学习里的通信严重依赖于规则的集群通信，诸如 allreduce, reducescatter, allgather 等，因此，实现高度优化的集群通信，以及根据任务特点和通信拓扑选择合适的集群通信算法至关重要。 本文以数据并行经常使用的 allreduce 为例来展示集群通信操作的数学性质。 Allreduce 在干什么？ 如图 1 所示，一共 4个设备，每个设备上有一个矩阵（为简单起见，我们特意让每一行就一个元素），allreduce 操作的目的是，让每个设备上的矩阵里的每一个位置的数值都是所有设备上对应位置的数值之和。 如图 2 所示， allreduce 可以通过 reducescatter 和 allgather 这两个更基本的集群通信操作来实现。基于 ring 状通信可以高...