GTSAM 中的 gtsam::Scatter解读和实战示例

一、Scatter 在 GTSAM 中到底干什么？

概述

gtsam::Scatter负责把 GaussianFactorGraph 中“局部因子块”散射（scatter）到“全局线性系统结构”中。

它是“因子图 → 线性代数” 的桥梁。

稍微严谨一点

在 GTSAM 的线性化阶段，我们面对的是：

min ⁡ δ x ∣ A δ x − b ∣ 2 \min_{\delta x} | A \delta x - b |^2δxmin​∣Aδx−b∣2

其中：

• 每个 GaussianFactor 只涉及部分变量

• 每个变量在全局向量中有一个slot（位置）

• Scatter 的任务就是：

  把 factor 的局部 Jacobian block，复制到全局系统的正确 block 位置

二、Scatter 的输入和输出

2.1 输入

2.2 输出（逻辑意义）

Scatter 本身不直接生成矩阵，而是：

• 构造Block Index / Slot 信息

• 为后续构建：

  • HessianFactor
  • BayesTree
  • EliminationTree
    提供快速访问结构

三、Scatter 的核心数据结构

3.1 Slot（槽位）

在 GTSAM 中，每个变量被映射到一个slot：

Key → Slot Index → (起始列, 维度)

例如：

3.2 Scatter 的原子单位

structGTSAM_EXPORTSlotEntry{Key key;size_t dimension;SlotEntry(Key _key,size_t _dimension):key(_key),dimension(_dimension){}std::stringtoString()const;friendbooloperator<(constSlotEntry&p,constSlotEntry&q){returnp.key<q.key;}staticboolZero(constSlotEntry&p){returnp.dimension==0;}};

重点：
Scatter 解决的不是“数值问题”，而是“索引 + 布局问题”

3.2.1、SlotEntry 是什么？

SlotEntry= 一个变量在 Scatter 中的“占位符”

它回答三个问题：

1. 是谁？→Key key
2. 占多大？→size_t dimension
3. 怎么排序？→operator<

Scatter 本质上就是：

FastVector<SlotEntry>

3.2.2、结构定义逐行拆解

structGTSAM_EXPORTSlotEntry{

• struct：纯数据结构

• GTSAM_EXPORT：

  • DLL 导出宏（Windows）
  • 允许跨库使用

说明 SlotEntry 是公共 ABI 的一部分

1 Key：变量的“符号 ID”

Key key;

• Key是gtsam::Key

• 本质上是uint64_t

• 通常由：

  • 字符 + index 组合（如X(5)）

SlotEntry 不关心变量的类型（Pose / Point / etc）

• 只认Key

2 dimension：这个变量占几列？

size_t dimension;

• 表示：

  • 该变量在线性系统中占用的自由度

• 例如：

  • Pose3→ 6
  • Point3→ 3
  • Vector2→ 2

Scatter 后续会计算：

key → dimension → offset → [offset, offset+dim)

3 构造函数

SlotEntry(Key _key,size_t _dimension):key(_key),dimension(_dimension){}

• 不做任何检查

• 不关心：

  • dimension 是否为 0
  • 是否重复 key

SlotEntry 是“哑结构”，逻辑在 Scatter 里保证

四、Scatter 的核心算法流程

4.1 构造阶段

Scatter(constGaussianFactorGraph&gfg,constOrdering&ordering)

这一步做了什么？

1. 遍历ordering
2. 为每个 key 分配一个 slot
3. 查询该变量的维度
4. 计算 prefix sum（列偏移）

数学/内存视角

| x1 (6) | x0 (6) | x2 (3) | ^ ^ ^ 0 6 12

4.2 Scatter 行为（逻辑）

当一个 GaussianFactor 要被处理时：

foreach variable in factor:col=colOffsets_[slot(key)]copy(local_block → global_block)

Scatter不关心数值计算是否正确
只关心“放哪”

五、Scatter 在 GTSAM 流水线中的位置

NonlinearFactorGraph ↓ linearize GaussianFactorGraph ↓ Scatter BlockIndex / Slot layout ↓ Eliminate BayesTree / Hessian

Scatter 是Elimination 的前置基础设施

六、FastScatter 扩展应用

FastScatter 代码如下：

classFastScatter:publicgtsam::Scatter{public:FastScatter(constgtsam::GaussianFactorGraph&gfg,constgtsam::Ordering&ordering);};

6.1 FastScatter 的设计动机

原版 Scatter 的问题

• 构造过程涉及：

  • Key 查找
  • 多次 map / vector 操作

• 在大规模问题中：

  • Scatter 构造本身成为瓶颈

6.2 FastScatter 的核心优化思路

一次性预计算 + 最小化间接访问

典型优化点：

6.3 FastScatter 的典型内部策略

classFastScatter:publicScatter{std::vector<Key>ordered_keys_;// slot → keystd::vector<size_t>slot_of_key_;// key → slot（压缩）};

FastScatter 仍然是 Scatter
它只改变“怎么更快地算 slot”

七、FastScatter 在工程中的实际意义

什么时候需要？

• 大规模 SLAM / STEAM
• Batch 优化
• 高频线性化 + 消元

不需要的时候？

• 小图
• 教学代码
• 非性能关键路径

八、Scatter vs HessianFactor vs Elimination（区分清楚）

Scatter 不做数值累加
Scatter 不做高斯消元

九、手写极简 Scatter示例

目标：我们这个 Scatter 要干什么？

把一组变量 Key → 映射成线性系统里的列区间

也就是：

Key → dimension → offset → [offset, offset + dim)

一、极简 Scatter 的职责（只保留 4 件事）

我们删掉 GTSAM 的一切复杂性，只保留：

1. 变量 Key
2. 变量维度 dim
3. 排序
4. offset 计算

不做的事情：

• 不支持动态 factor
• 不支持多种 elimination
• 不支持 BayesTree
• 不做错误检查

二、极简 SlotEntry

usingKey=uint64_t;structSlotEntry{Key key;size_t dim;size_t offset;// 线性系统中的起始列SlotEntry(Key k,size_t d):key(k),dim(d),offset(0){}booloperator<(constSlotEntry&other)const{returnkey<other.key;}};

对比 GTSAM：

• GTSAM 的SlotEntry不存 offset
• 我们为了展示显式存出来

三、极简 Scatter 类

classMiniScatter{public:// 添加变量voidadd(Key key,size_t dim){slots_.emplace_back(key,dim);}// 排序 + 计算 offsetvoidfinalize(){std::sort(slots_.begin(),slots_.end());size_t cur=0;for(auto&s:slots_){s.offset=cur;cur+=s.dim;}total_dim_=cur;}// 查询size_toffset(Key key)const{for(constauto&s:slots_){if(s.key==key)returns.offset;}throwstd::runtime_error("Key not found");}size_tdim(Key key)const{for(constauto&s:slots_){if(s.key==key)returns.dim;}throwstd::runtime_error("Key not found");}size_ttotalDim()const{returntotal_dim_;}voidprint()const{for(constauto&s:slots_){std::cout<<"Key "<<s.key<<" dim="<<s.dim<<" offset="<<s.offset<<std::endl;}}private:std::vector<SlotEntry>slots_;size_t total_dim_{0};};

四、如何使用这个 Scatter

intmain(){MiniScatter scatter;// 假设这是 ordering + factor 推出来的scatter.add(1,6);// Pose3scatter.add(3,3);// Point3scatter.add(2,6);// Pose3scatter.finalize();scatter.print();std::cout<<"Total dim = "<<scatter.totalDim()<<std::endl;}

输出示例：

Key 1 dim=6 offset=0 Key 2 dim=6 offset=6 Key 3 dim=3 offset=12 Total dim = 15

五、这一刻，已经“本质等价于 Scatter”

现在已经理解了：

六、Scatter 在矩阵构建中的真实用途

当构建线性系统：

A.block(row,scatter.offset(key),rdim,scatter.dim(key))+=J;

这句代码所有 magic 都来自 Scatter。

七、为什么 GTSAM 的 Scatter 比这个复杂？

GTSAM 版本额外支持：

十、总结

gtsam::Scatter是一个“结构构建器”，不是一个“数值求解器”。

它的存在是为了：

• 把“因子图世界”
• 映射到
• “稀疏线性代数世界”