w434's blog

排序主要分为两类：内排序和外排序： 内排序：待排序的记录个数较少，整个排序过程中所有的记录都可以直接存放在内存中 外排序：待排序的记录数量太大，内存无法容纳所有记录，在排序过程中还需要访问外存 基于比较的排序方式，时间代价为O(nlogn) 排序问题的基本概念 排序码 (Sort Key)：作为排序运算依据的一个或多个域 记录或元素 (Record)：结点，进行排序的基本单位 序列 (Sequence)：线性表，由记录组成 关键码 (Key)：唯一确定记录的一个或多个域，有人翻译为“键” 排序码不一定是关键码，关键码是唯一确定记录的一个域或多个域 排序：将序列中的记录按照排序码顺序排列起来的过程。其中，排序码域的值具有不减（或不增）的顺序。如果排序码不重复，则递增或递减 排序问题： 给定一个序列 R = { r0, r1, …，rn-1 }，其排序码分别为 k = { k0, k1, …，kn-1 } 排序的目的：将记录按排序码重排。形成新的有序序列 R’= { r’0, r’1, …，r’n-1 }。相应排序码为 k’= ...

Photometric Stereo 一个3D物体在不同的光照条件下重建法向量，再进一步求解三维 通过在不同照明条件下观察对象的表面法线来估计该对象的表面法线 为什么要估计法向： 法向量与颜色相关 法向量可以得到梯度从而得到平面 输入：使用固定相机和不同的光照条件拍摄多张图像。相机不动，光线改变 Image Intensity Image Intensity = 𝒇 (Light, Surface Reflectance,Surface Normal)。其中Intensity表示图像颜色，为已知。Light已知。Surface Reflectance反映了物体的材质为未知。Surface Normal为法向量为所求 目标是从约束不足的图像强度中恢复法线 解决歧义性： 多张图片消除歧义性 人为的增加假设或限制 Surface Reflectance 镜面反射(Specular reflection)：光线围绕 Surface Normal 反射 漫反射(Diffuse reflection)：光线向各个方向均匀散射 此外还有折射、表面 ...

Multi-View Stereo 和Two-View Stereo的区别：多张图片重建三维而非两张对应的图片 输入：使用校准相机拍摄同一物体或场景的多张图像 任意数量的图像 任意摄像机位置（摄像机网络或视频） 通常校准具有SFM或特殊设备的相机 输出：计算相应 3D 形状的表示。不同于两相机的单视角深度问题，要求重建稠密的3D表达 体素表达：通过0,1控制显示 三角网络表达 点云表达 核心思想：多图片的一致性，稠密的重建要求稠密的一致性 找一个参考图，衡量像素块的相似程度，构建函数图像找到误差最小的进行重建，其中，参考图在其他相机中的对应点都在极线上 Why Multi-View Stereo?(为什么需要多个视角) 对象表面上的不同点在某些相机子集中将更加清晰可见。如果视角不够则可能出现遮挡，倾斜的情况从而导致重建出的3D物体不完整 多视角可以减小误差使得相交区域更小从而形成更强的约束 MVS Visual Hull based MVS(基于体素) 核心思想：在多个(3个)视角进行拍摄，重建轮廓线： 有像素的部分记为1 没有像素的部分记为 ...

Structure from Motion 输入：多张照片 输出：相机的参数以及位置和场景的3D模型 Structure from Motion vs Calibration & Triangulation Calibration： 输入：从 3D 到 2D 的点对 输出：相机参数 Triangulation: 输入：相机的参数和2D点对 输出：3D点 Structure from Motion 输入：2D到2D的点对 输出：3D点以及相机参数 Structure from Motion: Problem formulation(问题设置) 输入：n 个固定 3D 点的 m 个图像（忽略可见性），使得：Pi是第i个相机的参数，Xj是3D其次坐标，二者均为未知。Xij是第i张图片的投影点 输出：估计 m 个投影矩阵 Pi 和 n 个 3D 点 Xj 来自 mn 对应关系Xij The Ambiguity of Structure from Motion SFM有歧义性是不可解的，因此必须加以约束才可解出唯一值，否则会得到一族解。例如下图对同 ...

Two-View Stereo 输入：具有已知摄像机矩阵的stereo对（已校准） 输出：密集深度图 Basic Stereo Matching Algorithm 使用一对校准的相机，我们可以通过以下方式重建 3D：Correspondence + Triangulation 具体流程：对左图中的每一个像素 在右侧图像中找到相应的极线 检查极线上的所有像素点并选择最佳匹配 对匹配点进行三角测量(Triangulate)以获取深度信息 A Simple Stereo System 最简单的情况：极线 = 相应的扫描线 相机的图像平面彼此平行并平行于baseline 相机中心位于同一高度 焦距相同 然后极线沿着图像的水平扫描线落下 The Essential Matrix for Simple Stereo Epipolar constraint for simple stereo: 对应点的 v 坐标是相同的 A General Stereo System 对于一般的stereo系统，图像平面通常不平行 我们可以使用fundamenta ...

Two-View Stereo(双视图立体) 用两个相机解决单一视角的模糊性：Stereo: use 2 calibrated cameras in different views and correspondences Typical 3D Reconstruction Pipeline Review: Camera Calibration with a Single Camera 两台相机的设置能否提供更多校准功能？ Camera Calibration 所需： 需要校准板 准确定位消失点很棘手，并且至少需要两个有限的消失点 Review: Triangulation 问题设置：给定一个 3D 点在两个或多个图像（具有已知相机矩阵）中的投影，找到该点的坐标 两台相机的设置能否为 3D 估计提供更多功能？ Two-view Stereo: Key Idea 考虑相机中心和视觉光线到另一个视图中的投影，而无需明确的 3D 推理 可以校准两台相机 可以找到约束条件，以便更轻松地对应和 3D 重建 如下图：对应的点在固定的线上 Epipolar Geom ...

考试加油鸭！！！

第十五章 全局光照 渲染管线主要形式： 光栅化：高效、易行，但却牺牲了渲染质量，难以处理软阴影、镜面反射、间接光照等全局现象 光线追踪：法善于解决上述困难，而其代价则是渲染时间的成倍提升 光线投射 在渲染一幅画面的过程中，屏幕上任意一个点所对应的颜色应该来自于场景中的哪一个物体?从人眼 (摄像机) 向屏幕上的点连一条射线，该射线在场景中击中的第一个物体将决定该点的颜色 发出射线、击中物体的过程，也就是所谓的光线投射。算法流程： 对于每一个像素点 (x, y)，从观察者的眼睛发出一条穿过 (x, y) 的光线 找出这条光线与场景中的物体第一次发生相交的位置 将这个交点与每一个光源相连，分别形成一根 shadow ray（这根光线也可能被障碍物遮挡） 通过 shadow ray 和我们一开始发出的光线，我们得到了入射方向和出射方向，结合交点的几何信息，我们也已知了法线方向，从而可以运用之前介绍过的着色模型计算出交点的颜色 将算出的颜色作为像素点 (x, y) 的颜色写入 利用光线投射法来渲染场景的伪代码： 1234567891011121314151617181920 ...

3D VisionSingle-view Ambiguity(单一视角的歧义性) 3D Vision:从图片中重建三维结构 关键问题：单一视角的歧义性。给定一个相机和一个图像，许多 3D 点可能会投影到同一个 2D 像素 单一视角的模糊性使得投影具有歧义性，产生投影错觉 Resolve Single-view Ambiguity F1:从传感器中射出光（激光、结构光等） F2:双目立体视觉：使用 2 个不同视图和对应关系的校准相机。拍两张照片，类似于双目视差进行校准 F3:多视图几何图形：移动相机并查找对应关系以求解 X,拍摄多张照片用SIFTfeature来求解 F4:Shape from Shading(三维明暗重建三维)：固定相机，并使用在不同阴影下拍摄的照片重建几何图形 F5:从数据中学习：训练神经网络以预测 3D 信息。用神经网络估计深度解释歧义性 Camera Calibration(相机校准) 核心：找匹配点 Review: Camera Parameters Camera calibration 任务描述：Given 𝑛 ...