摘要

为藏在摄像机视域外的物品成像，是一个在很多研究领域非常重要且基础的问题。在很多领域都有应用潜力如机器人视觉、防御、遥感、自动驾驶等。宏观来讲，非视域成像（NLOS）可以用脉冲激光和时间分辨探测器扫描一个可见的表面得到测量数据。光探测与测距（LIDAR）系统利用此类测量从直接反射中恢复可见物体的形状，而 NLOS 成像是从多次散射的光中重建隐藏物体的形状和反照率。尽管近期取得了进展，但由于现有重建算法高昂的内存和处理需求，以及多次散射光信号极其微弱，NLOS 成像仍然不切实际。

在此，我们展示了一种共聚焦扫描程序可以通过简化光锥变换的推导来解决 NLOS 重建问题，从而应对这些挑战。该方法所需的计算和内存资源远小于以往的重建方法，并能以前所未有的分辨率对隐藏物体成像。在对逆反射物体成像时，共聚焦扫描还能大幅增加信号强度和探测距离。我们量化了 NLOS 成像的分辨率极限，展示了其在实时追踪方面的潜力，并推导出了能融合图像先验和物理精确噪声模型的高效算法。此外，我们还描述了在间接日光下成功的户外 NLOS 成像实验。

摘要

第一段简述 DSP 和 SP 的定义和目的，简要介绍二者的 NP-Hard 本质。

第二段引入本文发现的解的结构结论，并针对该结论提出本文的解决方案：在两种结构特征下分别运行对应的算法，取其中最优的结果。该算法可以得到 $(\frac{3}{2}+\varepsilon)OPT$ 的近似保证。

1 引言

1.1 研究问题

1.1.1 需求条带包装（DSP，Demand Strip Packing）

• 给定：

  • 一个包含 $n$ 个项目（工作）的集合 $\mathcal{I}={1,…,n}$ 和一个宽度 $D$（截止时间） 。每个项目 $i∈I$ 都有一个宽度（处理时间）$w(i)$ 和一个高度（需求）$h(i)$ 。

• 定义：

  • 一个D-可行的包装 (D-feasible packing)是一个分配函数 $σ:I→[0,D]$，它为每个项目 $i$ 指定一个开始时间 $σ(i)$，满足 $0≤σ(i)≤D−w(i)$，即所有项目都在时间 $0$ 或之后开始，并在截止时间 $D$ 之前结束 。
  • 对于一个给定的包装方案 $σ$ 和任意时间点 $t∈[0,D]$，我们将 $\mathcal{I}^σ(t)$ 定义为在 $t$ 时间点正在被处理的项目集合，即 $I^σ(t):={i∈I∣σ(i)≤t<σ(i)+w(i)}$。

• 目标：

  • 计算一个 D-可行的包装方案 $σ$，使其高度 $h(σ)$ 最小化，其中 $h(\sigma)=max_{t\in[0,D]}\Sigma_{i\in\mathcal{I}^\sigma(t)}h(i)$ 。该高度被定义为所有时间点中，并行处理的项目需求总和的最大值，即峰值需求 。

1 引言

该篇教程来源于本人为搭载了 Ubuntu 25 的树莓派 5 配置 SEU 校园网认证的痛苦过程，原先网上大部分教程聚焦于如何通过构造请求为设备提供校园网认证，但是该方法具备以下局限性：

1. 许多命令行设备设备难以在保证通信的前提下进行请求的发送。以树莓派为例，如果可以使用显示设备，那安装具备 GUI 的系统版本即可，如果无法使用显示设备，那你就会面临一个困境，如果连接热点，就无法连接到 w.seu.edu 进行认证，如果提前连接 SEU-WLAN，那你和你的设备将失去通信，所以你只能构造一个自动脚本，像放飞一个信鸽一样，祈祷他可以连接成功，而这个脚本却往往因为下面的原因难以在短短几次内成功运行。
2. 如果认证的请求格式在后续的维护中发生变化，教程对请求的构造内容将难以复用。
3. 如果认证的请求使用复杂的加密，构造将难以解析。
4. 不是所有的设备都有命令行界面，比如网络对时时钟（我的宿舍刚好也摆放了一台）

所以本篇博客采取了全新的思路，使用另外一台具备图形化界面的设备（下面以最常见的 Windows 为例，如果没有可以向周边同学借一下）伪装命令行设备的 Mac 地址，“帮他”进行认证。

我相信很多人看到这里就已经恍然大悟了，这时候你就可以提前离开进行实践了

2 过程

2.1 连接命令行设备

下文成立的前提是你可以连接到设备的命令行，如果是无命令行设备，你需要根据不同的设备研究“如何获取它的 Mac 地址”，然后带着珍贵的 Mac 地址跳到 2.3 步。下文我们以树莓派这种开发板设备为例。

该笔记基于教程 Let’s Build A Simple Interpreter. from Ruslan’s Blog，原文使用 Python 为 Pascal 编写解释器，在该笔记中我将使用 Rust 进行解释器的编写。

1 核心概念

1.1 语法分析

根据语言的上下文无关文法，检查词法单元流的排列顺序是否符合语法规则，并将其组织成一个树形结构，称为语法树（Syntax Tree）。

2 语法分析（编译第二步）

2.1 任务

token流 -> 语法树: 语法分析器（Parser）通过自顶向下（如 LL）或自底向上（如 LR）的算法，来解析词法单元流，并生成语法树。这棵树清晰地展示了代码的层次结构，例如，一个 if-else 语句是如何由条件、then 块和 else 块构成的。

该笔记基于教程 Let’s Build A Simple Interpreter. from Ruslan’s Blog，原文使用 Python 为 Pascal 编写解释器，在该笔记中我将使用 Rust 进行解释器的编写。

1 核心概念

1.1 词素（lexeme）

Token	Sample lexemes
INTEGER	342, 9, 0, 17, 1
PLUS	+
MINUS	-
词素指的是形成一个 Token 的字符序列。

2 问题

对上节的解释器进行升级，解释器需要在上节的基础上实现如下拓展：

1. 无视输入的任意位置的空格
2. 实现多位数字的识别
3. 实现两个正数的减法

3 代码实现

3.1 interpreter/token.rs

该笔记基于教程 Let’s Build A Simple Interpreter. from Ruslan’s Blog，原文使用 Python 为 Pascal 编写解释器，在该笔记中我将使用 Rust 进行解释器的编写。

1 核心概念

1.1 编译器与解释器的区别

编译器：先对源代码进行预处理翻译为机器码，再交给机器运行（预处理、执行）
解释器：直接执行源代码（边解释边执行）

1.2 标记（token）

概念: 一个具有类型和值的对象
结构: {TokenType, Value}

Value 在原字符串中形成一个词素（lexeme）

1.3 词法分析（lexical analysis）

概念: 将输入字符串分解成标记（token）的过程
工具: 词法分析器（lexer, scanner, tokenizer）

2 词法分析（编译第一步）

2.1 任务

字符流 -> token流: 指针在原字符串上移动，构建 token 流