1
  
概述
  
近期有研究者提出了有效的基于深度学习计算的设计自动化技术。涵盖了设计自动化的三个方面：专业模型设计、压缩和修剪、混合精度量化。由于算法和硬件协同设计在高效的深度学习计算中起着重要的作用。与将神经网络视为黑匣子不同，在给定固定目标硬件的情况下，神经结构设计中有很大的空间可以提高深度学习的推理效率。这样做的好处通常来自于节省内存和提高局部性。例如，包括剪枝和量化的模型压缩技术可以显著地减少内存占用并节省能源消耗。
  
研究者提出了以硬件为中心的AutoML技术，它可以自动设计出硬件推理效率高的神经网络。这样的联合优化是系统的，可以很好地在任务之间转移。探讨了神经网络设计自动化的三个方面(图1)：自动设计专用模型、自动通道修剪和自动混合精度量化。
  

  
图1 自动模型设计，通道剪枝和混合量化
  
神经网络的专用硬件有很多，但是对于给定的硬件结构(反向专用化)的专用神经网络结构的研究很少。专用模型有几个优点：它可以充分利用目标硬件的并行性(例如，将通道大小与PE大小相匹配)。此外，一个专门的模型可以充分利用片上缓冲区，提高局部性和重用性。专业化还可以使模型的计算强度与硬件的屋顶模型相匹配。然而，设计一个专门的神经网络结构过去是困难的。首先，启发式方法有限。第二，计算成本过去是令人望而却步的：即使在CIFAR-10数据集上搜索模型也需要104gpu小时。
  
在设计了专门的模型之后，压缩和修剪是进一步减少内存占用的有效技术。研究者提出一个自动化的设计流程，利用强化学习来提供最佳的模型压缩策略。这种基于学习的压缩策略比传统的基于规则的压缩策略具有更高的压缩比，更好地保持了压缩的准确性，并且节省了人力。将这种自动匹配的按键压缩管道应用到MobileNet，在Android手机上实现了1.81倍的测量推断延迟加速，在Titan XP GPU上实现了1.43倍的加速，ImageNet Top-1的准确度仅损失了0.1%。
  
2
  
自动化模型专业化
  
为了充分利用硬件资源，研究者建议为给定的硬件搜索一个专门的CNN体系结构。该模型结构紧凑，运行速度快。从一个大的设计空间(图1(a))开始，它包括许多候选操作符(例如，3x3 Conv、5x5 Conv等)，通过梯度下降来学习哪一个是最好的，而不是用基于规则的启发式进行手工挑选。不只是学习权重参数，而是共同学习架构参数(如图1(a)中红色部分所示)。架构参数是选择每个运算符的概率。每个块的搜索空间由许多选项组成。
  
它的结构与设计空间中的CNN模型相似，只是每个特定的操作都被一个具有n个并行操作的混合操作所代替，向每个操作引入一个架构参数αi，以了解哪些操作是冗余的，因此可以修剪。最后，每个块中只剩下一个操作符，研究者从头开始在目标任务上重新训练此模型以进行部署。为了节省GPU内存，只允许一个候选操作符活跃地驻留在GPU内存中。这是通过将每个候选算子的概率硬阈值化为0或1来实现的。
  

  
图2 用CPU(Xeon E5-2640 v4)、GPU(Tesla V100)和手机(Google Pixel-1)演示了研究者的模型专业化在ImageNet数据集上的有效性
  
首先为手机搜索一个专门的CNN模型(图2(b))。与MobileNet-V2(当前人类工程架构的状态)相比，研究者的模型在保持相似延迟的同时，将top-1的准确性提高了2.6%。在相同的一级精度(约74.6%)下，MobileNet-V2的延迟为143ms。
  
图2(a)显示GPU的加速与人工设计的和自动搜索的体系结构相比，研究者的方法获得了更好的性能。与通用模型相比，提高了1.1%～3.1%的top-1精度。
  
3
  
通道的修剪
  
自动模型压缩(AMC)利用强化学习有效地搜索修剪率(图1(b))。并计算每个输入通道的加权张量的平均值，用最小值去除输入通道。然后agent移动到下一层，并接更新接收状态。完成最终层后，在验证集上评估奖励准确性并返回给agent。将AMC应用到MobileNet中，观察到GPU和移动电话都有显著的加速(表1)。在GPU上，还实现了高达1.5倍的加速，这比手机要慢，但在一个已经非常紧凑的机型上仍然很重要。速度越慢是因为GPU的并行度比手机高。
  

  
表1：将AMC应用到MobileNet；表2：在边缘端和云端的延迟量化效果；图3：在MobileNet-V1上使用HAQ后显示Pointwise效果
  
4
  
混合精度量化
  
传统的量化方法将模型的每一层量化到相同的精度。混合精确量化更容易出现，但却受到难以探索的更高设计空间的影响。同时，在一个硬件上优化的量化方案在另一个硬件上可能不是最优的，这就对不同硬件体系结构的专用策略提出了要求，进一步增加了设计空间。假设权重和激活的比特宽度都在1到8之间，那么每个层都有82个选择。如果研究者有M个不同的神经网络模型，每个模型有N层，在H个不同的硬件平台上，总共有O(H×M×82N)个可能的解。研究者不使用基于规则的启发式方法，而是提出了一种自动化的设计流程，以混合精度量化不同的层。使用硬件感知自动量化技术(HAQ)将量化任务建模为强化学习问题。使用模型给出量化策略(每层比特数)(图1(c))，并使用FPGAs提供能量和延迟成本的计算(因为FPGAs很好地支持混合精度)。目标不仅是高精度，而且是低能量和低延迟。
  
基于深度学习计算的设计自动化技术，涵盖了设计自动化的三个方面：专业模型设计、压缩和修剪、混合精度量化。提出的框架揭示了不同硬件架构上的优化设计策略有很大的不同，相信这将启发未来的软硬件协同设计，以实现高效的深度学习计算。
  
资料来源：《AutoML for Architecting Efficient and Specialized Neural Networks》
  
关注我们
  
  

 
 

前言
 
一. 图的基本概念
 
二. 图的存储方式
 
     1. 邻接距阵存储
 
     2. 邻接表存储图
 
     3. 十字链表
 
三. 图的实际应用
 
    1. 存储微信或微博的好友关系
 
四. 图的遍历
 
      广度优先遍历（BFS）
 
      深度优先遍历简称 DFS
 
五. 学习过程中的疑问
 

前言
 
    相信大家都有听过《哥尼斯堡七桥》这个故事吧，正是这个故事引出了数学中的一个新分支---图论。
 
    引用百度百科《七桥问题》的图如下所示
 
 
    其实，在进行图学习之前，由于笔者的孤陋寡闻，只是在记忆中记得大学时好像有学习过图的一些知识。出来工作四年之久，但都未尝直接运用过图，因此对于图这种数据结构到底运用于编程中基本是空白的。
 
    在开始学习图之前，先考虑下如何存储微博或微信等社交网络好友的关系呢？
 
一. 图的基本概念
 
   什么是图：图(Graph )是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G (V,E )，其中，G表示一个图,，V是图G中顶点的集合，E是图G中边的集合。
 
   图(Graph)是一种比线性结构和树形结构更加复杂的数据结构。图研究的对象是多对多的关系，线性表是一对一，树是一对多。
 
  顶点 (vertex)：图中的元素；
 
  边 (Edge)：顶点与顶点之间的相连关系；
 
  无向图：顶点与顶点之间没有指向关系的图；
 
  度：表示一个顶点与多少个顶点连接或者说其有多少条边；
 
  如下图所示：下图各顶点之间并没有指向问题，为无向图，图中的每个字母为一个顶点，每个顶点与其他顶点相连形成的边则为图的边。以 A 顶点为例，其总共与BCD三个顶点相连，说明 A 的度为3，边数也为3。
 
 
有向图：顶点与顶点之间有指向的关系的图；如下图所示：
 
 
对于有指向关系的图，为了方便描述顶点与其他顶点的关系而引入了出度与入度的概念。
 
入度（Indegree）：顶点的入度表示有多少条边指向这个顶点；如上图 A 顶点为入度为 1。
 
出度（OutDegree）：顶点的出度表示有多少条边以该顶点为起点; 如上图 A 顶点的出度为 2。
 
    对应到微博中，入度就相当于有多少人关注了你，出度就相当于你关注了多少人。
 
带权图（通常也称为网）：顶点之间的边上带有权重的图；如下图所示：
 
 
例如 QQ 中好友之间还保存了好友之间的亲密关系，比如两个人经常联系则表示比较亲密（权重数高一点），像这样就关系就比较适合用带树图来表示了，其中权重表示亲密度。
 
带权有向图：对应带权无向图而言就是顶点与顶点之间多了指向；
 
 
 
二. 图的存储方式
 
    对于图来说常用的存储方式主要是邻接距阵与链表式存储了。
 
1. 邻接距阵存储
 
     原理：邻接矩阵的底层依赖一个二维数组。
 
     无向图：顶点 i 与顶点 j 之间有边，就将 A[i][j] 和 A[j][i] 标记为1；
 
     有向图：顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边就将 A[i][j] 标记为1，同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i] 标记为1。对于带权图，数组中就存储相应的权重。
 
 
    通过上图可知对于无向图，如果A[i][j] 为1 那么 A[j][i] 必定也为1，也就是说其实对于无向图只需要存储距阵中对应的一半元素则可，另外一半的空间就完全是浪费了。
 
   因此，对于稀疏图（顶点很多，但是顶点之间的形成的边并不多），例如微信用户有上亿，但每个用户的好友数一般只有几百，这样的数据构成的图则不适合用邻接距阵的方式进行存储，因为会造成相当大的空间浪费。那么对于这类图，我们可以通过什么方式进行存储呢？
 
2. 邻接表存储图
 
   通过数组与链表结合的存储方法就称为邻接表存储，其中，顶点存储在一维数组中，每个数组单元存储一个顶点与其指向的第一个链表指针。顶点与其他顶点形成的关系存储成单链表。（当然这里的数组其实也可以换成单链表）。
 
一图胜千言，如下图便是邻接表存储图了
 
 
   通过上图，感觉这似乎跟散列表一个样呀？
 
   邻接表存储图说明：每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。
 
   如上图为有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。
 
   对于无向图来说，也是类似的，不过，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。
 
   在学习散列时，为了解决散列冲突的问题，当链表过长时，为了加快检索的效率，我们会将链表转变成红黑树，由于该链表基本上跟散列表一个原理，因此也可以对该链表类似进行类似于散列表形式的优化。
 
   通过邻接表，我们可以很方便地找出每个顶点的出度，但是如果要找顶点对应的入度就特别麻烦了。比如上图，要查找有那些顶点指向 1 号顶点，这时只能是遍历整个邻接表了。因此，这里便引入了，逆邻接表。
 
逆邻接表：基本原理与邻接表一样，唯一的区别是邻接表存储的是顶点指向其它顶点的关系（或者说是顶点与其他顶点的出度关系），逆邻接表刚好相反，其存储的是顶点的入度关系。如下图所示：
 
 
  逆邻接表数组依然是存储顶点，但是链表存储的是那些节点指向了该顶点。
 
  有了逆邻接表后，当要查找有那些顶点指向 1 号顶点，直接查找逆邻接表就可以了。
 
  总结：邻接距阵与邻接表存储图的优缺点
 
  邻接距阵：基于数组存储，操作起来方便，比如将图相关的计算可转变成距阵的计算，很容易计算会每个顶点的度。但缺点是对于无向图或稀疏图如果用邻接距阵的方式就比较浪费存储空间。
 
  邻接表：操作起来没有邻接距阵那么快速与方便，查找某个顶点的出度还算方便，但是寻找顶点的入度就需要遍历整个邻接表了，优点是对于顶点多边少的稀疏表其占用空间小。
 
   通过上述邻接表与逆邻接表是可以快速实现查找顶点的出度也入度，但是对于每份数据需要存储两份，以及每插入一个数据时都需要维护正反邻接表，那么有没有什么方法可以其进行优化呢？这里就引入了十字链表。
 
3. 十字链表
 
    十字链表长什么样呢？用最直观的示意，是下面这样：
 
 
注：上图只是十字链表的一个示意图，真正的十字链表并不是这样的，但其实现的功能基本是这样的。（引自小灰漫画）
 
   不过，上图只是一个便于理解的示意图，我们没有必要把链表的节点都重复存储两次。在优化之后的十字链表中，链表的每一个节点不再是顶点，而是一条边，里面包含起止顶点的下标。
 
  十字链表节点和边的对应关系，如下图所示：
 
 
   因此，优化之后的十字链表，是下面这个样子：
 
 
 
 
     图中每一条带有蓝色箭头的链表，存储着从顶点出发的边；每一条带有橙色箭头的链表，存储着进入顶点的边。初学十字链表的时候，可能会觉得有些乱。
 
 
 
三. 图的实际应用
 
1. 存储微信或微博的好友关系
 
    对于微信来说，只有互相关注(暂且忽略其中一方被删除了的情况)，因此其形成的图是无向图，而微博为有向图。这里以微博为例说明：数据结构是为算法服务的，因此具体选择那种算法，与实际业务是有直接关系的，这里以如下业务场景来说明存储微博好友的关系，场景如下：
 
判断用户A是否关注了用户B;
判断用户A是否是用户B的粉丝;
用户A关注用户B;
用户A取消关注用户B;
根据用户名称的首字母排序，分页获取用户的粉丝列表;
根据用户名称的首字母排序，分页获取用户的关注列表。
   对于上述的场景，由于社交图是一种稀疏图，因而很自然地选择了邻接表的方式进行存储；
 
   这里有一个问题是，如果单纯用一个邻接表进行存储，获取指定用户关注了那些用户或用户的关注列表这方面是很容易求出。
 
   但如果要获取一个用户是否是另一个用户的粉丝或用户的粉丝列表就比较麻烦了，因此这里引入逆邻接表。
 
    邻接表存储了用户的关注关系，逆邻接表存储了用户被关注的关系；从图的定义上来说，邻接表表示的是顶点的出度，逆邻接表表示的是顶点的入度。
 
    当我们要查询指定用户关注了那些人则查邻接表，查询指定用户的粉丝则查逆邻接表。如下图所示：
 
 
 
 
   对于微博来说：为了快速查找用户之间的关系，由于单链表遍历只能从头开始遍历，因此基础的邻接表应该比较难以满足这个需求。在这里了，为了提升对链表的遍历速度，我们可以对邻接表进行升级改造，如将普通的单链表升级为跳表或平衡二叉树等（这个操作有点类似与JDK8 升级后的HashMap，HashMap当散列表中链表长度超过8后便将该链表转换成红黑树）；
 
   因为我们需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用跳表这种结构再合适不过了。这是因为，跳表插入、删除、查找都非常高效，时间复杂度是O(logn)，空间复杂度上稍高，是O(n)。
 
   最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。
 
   如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，我们可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。
 
   但是如果像微博那样有上亿的用户，数据规模太大，我们就无法全部存储在内存中了。
 
   我们可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。
 
   如下图，在机器1上存储顶点1, 2, 3 的邻接表，在机器2上,存储顶点4, 5的邻接表。同理，逆邻接表的处理方式也一样。
 
 
  当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器,然后再在相应的机器上查找。
 
  当然，我们还可以将上述信息存储到硬盘中，如数据库。
 
  总结：在数据量比较大的情况下，为了加快链表的遍历，我们可以对邻接表进行升级改造，例如将链表改造成跳表、平衡二叉树等。
 
2. 图还可以应用在一些导航图或城市规划等形成的加权图；
 
3. 做为一些图数据库的底层思想存在；
 
 
 
四. 图的遍历
 
   图的遍历主要有深度遍历与广度遍历，深度优先遍历简称 DFS（Depth First Search），广度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种方式。
 
广度优先遍历（BFS）
 
   原理：类似“地坛式”的进行一层层由内到外的搜索，即从查询起点开始，先查近它最近的，然后依次向外扩展；其实这个类似树的层序遍历，示意图，如下图所示：
 
 
深度优先遍历简称 DFS
 
   假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。
 
   走迷宫的例子很容易能看懂，我们现在再来看下，如何在图中应用深度优先搜索，来找某个顶点到另一个顶点的路径。你可以看我画的这幅图。
 
    搜索的起始顶点是s，终止顶点是t，我们希望在图中寻找一条从顶点s到顶点t的路径。如果映射到迷官那个例子， s就是你起始所在的位置， t就是出口。我用深度递归算法，把整个搜索的路径标记出来了。这里面实线箭头表示遍历，虚线箭头表示回退。从图中我们可以看出，深度优先搜索找出来的路径，并不是顶点s到顶点t的最短路径。
 
 
   实际上，深度优先搜索用的是一种比较著名的算法思想-回溯思想。这种思想解决问题的过程，非常适合用递归来实现。
 
遍历的代码实现
 
如下，引用小灰漫画中的代码
 
package test;

import java.util.LinkedList;

/**
 * 图的顶点
 */
class Vertex {
	int data;

	Vertex(int data) {
		this.data = data;
	}
}

/**
 * 图（邻接表形式）
 */
class Graph {
	private int size;
	private Vertex[] vertexes;
	private LinkedList<Integer> adj[];

	Graph(int size) {
		this.size = size;
		// 初始化顶点和邻接矩阵
		vertexes = new Vertex[size];
		adj = new LinkedList[size];
		for (int i = 0; i < size; i++) {
			vertexes[i] = new Vertex(i);
			adj[i] = new LinkedList();
		}
	}

	/**
	 * 深度优先遍历
	 */
	public static void dfs(Graph graph, int start, boolean[] visited) {
		System.out.println(graph.vertexes[start].data);
		visited[start] = true;
		for (int index : graph.adj[start]) {
			if (!visited[index]) {
				dfs(graph, index, visited);
			}
		}
	}

	/**
	 * 广度优先遍历
	 */
	public static void bfs(Graph graph, int start, boolean[] visited, LinkedList<Integer> queue) {
		queue.offer(start);
		while (!queue.isEmpty()) {
			int front = queue.poll();
			if (visited[front]) {
				continue;
			}
			System.out.println(graph.vertexes[front].data);
			visited[front] = true;
			for (int index : graph.adj[front]) {
				queue.offer(index);
			}
		}
	}

	public static void main(String[] args) {
		Graph graph = new Graph(6);

		graph.adj[0].add(1);
		graph.adj[0].add(2);
		graph.adj[0].add(3);

		graph.adj[1].add(0);
		graph.adj[1].add(3);
		graph.adj[1].add(4);

		graph.adj[2].add(0);

		graph.adj[3].add(0);
		graph.adj[3].add(1);
		graph.adj[3].add(4);
		graph.adj[3].add(5);

		graph.adj[4].add(1);
		graph.adj[4].add(3);
		graph.adj[4].add(5);

		graph.adj[5].add(3);
		graph.adj[5].add(4);

		System.out.println("图的深度优先遍历：");
		dfs(graph, 0, new boolean[graph.size]);

		System.out.println("图的广度优先遍历：");
		bfs(graph, 0, new boolean[graph.size], new LinkedList<Integer>());
	}
}
 
运行结果如下所示：
 
图的深度优先遍历：
0
1
3
4
5
2
图的广度优先遍历：
0
1
2
3
4
5
 
五. 学习过程中的疑问
 
疑问一：
 
    在学习图的邻接距阵存储的时候，其实有一个疑问我们要如何确定图中各顶点的位置关系，也就是说那个顶点对应数组中的那个位置？从而画出其对应的距阵图。
 
   其实有上述疑问，主要原因还是对图这种数据结构的定义不是那么清晰而引起的。对于图这种数据逻辑数据结构，其实它的任何一个顶点都可以说是图的第一个顶点，因此任何一个顶点与顶点之间的邻接关系（或边）也是不存在次序的。如下图仔细观察会发现它们都是同一个图（此处引用《大话数据结构》的部分内容），只是表象不一样罢了。
 
 
    对于图这种复杂的数据结构，任意两个顶点之间都可能存在着关系，因此不可能通过元素在物理内存中的位置关系来表示元素之间的关系。
 
   考虑到图是由顶点与边或弧两部分构成。合起来表示比较困难，因此很自然地想起用两种数据结构来存储它们。我们可以用一维数组不分次序存储顶点，然后用二维数组存储存储顶点与顶点之间的关系。引用《大话数据结构》一书的图如下所示：
 
 
    通过上图，我们可以知道二维数组的次序可以通过顶点对应的一维数组来确定，而顶点对应的一维数组是与顶点次序无关的。      通过上图我们还可以知道对于任一顶点的出度是通过将该顶点的行求和，入度则是列求和。
 
疑问二：为什么需要学习图这种数据结构呢？
 
   1. 线性表与树这些结构只能表示一对一或者一对多的关系，而图可以表示更加复杂的关系，比如多对对，因此引入图可以增强对关系的表示。
 
   2. 现如今有很多现成的图算法，当需要用到时只需要简单引用便可，大大减少了开发成本。
 

注：了解更多数据结构知识
 
该系列博文为笔者学习《数据结构与算法之美》的个人笔记小结
 
参考
 
漫画：什么是 “图”？（修订版）
 
漫画：深度优先遍历 和 广度优先遍历
 
数据结构：图（Graph）
 
《大话数据结构》

Make3D Learning 3D Scene Structure from aSingle Still Image（译文）
 
下载原文：https://cn.bing.com/academic/profile?id=45505ee803dc50067cac97db19e57b67&encoded=0&v=paper_preview&mkt=zh-cn
 
欢迎在下面留言交流。
 
摘要：
 
我们考虑从非结构化的单个静止图像中的估计详细的三维结构的问题。我们的目标是建立三维模型，即能在数量上精确，又能在视觉上令人满意。
 
对于图像中的每一个均匀的小区域，我们使用马尔可夫随机场（MRF）来推断一组“平面参数”，这些参数可以捕捉小区域的三维位置和三维方向。MRF通过用监督学习训练，对图像的深度线索以及图像不同部分之间的关系进行建模，除了假设环境是由许多小平面组成之外，我们的模型对场景的结构没有做出任何明确的假设。这使得算法能够捕捉比现有技术更详细的三维结构，并且在使用基于图像的渲染创建的三维草图中提供更丰富的经验，即使对于具有显著非垂直结构的场景。
 
利用这种方法，我们为从网上下载的588幅图像中的64.8%创建了质量正确的三维模型，我们还扩展了我们的模型，从一些图像生成了大规模的三维模型。
 
引语：机器学习，单目视觉，深度学习，视觉和场景理解，场景分析：深度线索。
 

 一、介绍:
 
在看到如图1a所示的图像时，人类不难理解其三维结构（图1c、d）。然而，对于目前的计算机视觉系统来说，推断出这样的三维结构仍然是一个极具挑战性的课题。实际上，从狭义的数学意义上讲，从一副图像上恢复其三维深度是不可能的，因为，我们永远无法知道它是一副油画的图片（这种情况下，深度是平坦的）还是一副真实的三维环境的图。然而，实际上，只要一副图像，人们就能很好的感知深度；我们希望我们的计算机在场景中也具有类似的感知。
 
理解三维结构是计算机视觉的一个基本问题。对于三维重建的具体问题，以往的工作主要集中于立体视觉、运动结构和其他需要两幅（或多幅）图像的方法上。这些几何算法依赖于三角剖分来估计深度，然而，仅仅依赖于几何的算法往往会忽略大量额外的单目线索，这些线索也可以用来获取丰富的三维信息。在最近的研究中，[6]- [9] (文章的尾部的引用)利用了其中的一些线索来获得一些三维信息。Saxena，Chung和Ng[6]提出了一种基于单目图像特征的深度预测算法。[7]利用单目深度感知自主驾驶遥控车。[8],[9]建立模型时使用了一个强有力的假设，即场景由地面/水平面和垂直墙（可能还有天空）组成;因此，这次方法不使用于许多场景，这些场景并非仅由竖立在水平地板上的表面构成。一些例子包括山脉、树木（如图15b和13d）、楼梯（如图15a）、拱门（如图11a和15k）、屋顶（如图15m）等图像，这些图像通常具有更丰富的三维结构。
 
在这篇论文中，我们的目标是推断出既能在数量上精确有能在视觉上令人满意的三维模型。我们使用的洞察力，大多数三维场景是可以分割成许多下的，近似平面的表面（事实上，现代计算机图形学使用OpenGL或Directx以这种方式建模极其复杂的场景，使用三角面来建模甚至非常复杂的形状）。我们的算法从拍摄图像开始，并尝试将其分割成许多小的平面。使用超像素分割算法，[10]我们发现图像的过渡分割将其分割成许多小区域（超级像素）。在图1b中显示了这样的分割的一个例子。因为我们使用过分割，世界上的平面表面可能被分割成许多超像素；然而，每个超像素很有可能（至少近似地）完全位于一个平面上。
 
对于每个超像素，我们的算法试图推断出它来自的三维表面的三维位置和方向。这个三维表面不仅限于垂直和水平方向。而且可以朝向任何方向。从单个图像推断三维位置是非常重要的，而且人类使用许多不同的视觉深度线索，例如纹理（例如，近距离观察时草的纹理与远距离观察时草的纹理非常不同）；颜色（例如，绿色斑块更可能是草上的地面；蓝色斑块更可能是天空）。我们的算法使用监督学习来学习不同的视觉线索是如何与不同的深度相关联的。我们的学习算法使用马尔可夫随机场模型，该模型也能考虑对邻近超混合体相对深度的限制。例如，它认识到两个相邻的图像块更可能位于相同的深度，甚至是共面的。而不是相隔很远。
 
在推断出每个超像素的三维位置后，我们现在可以构建场景的三维网格模型（图1c）。然后我们将原始图像纹理图构建一个纹理化的三维模型（图1d）,我们可以从不同的角度浏览。
 
除了假设三维结构是由许多小平面组成之外，我们对场景的结构没有做出明确的假设。这使得我们的方法能够很好地概括，即使是对于结构化仅竖立在水平地面上的垂直表面（如山、树等）要丰富得多的场景。我们的算法能够自动推断从互联网下载的588个图像中64.9%的测试图像的三维模型，即能在数量上精确，又能在视觉上令人满意。我们进一步证明，我们的算法比之前的两项工作在数量上预测更精确的深度。
 
扩展这些思想，我们还考虑了在仅给定一组小的稀疏图像的情况下，创建大型新颖环境的三维模型的问题。在此设置中，场景的某些部分可能在多个图像中可见，因此可以使用三角剖分提示（来自运动的结构）帮助重建它们；但场景的较大部分可能仅在一个图像中可见。我们扩展了我们的模型，将三角剖分和单目图像无缝地结合起来。这使我们能够建立完整的，真实的三维模型，更大的场景。最后，我们还演示了如何将对象识别信息合并到我们的模型中。例如，如果我们发现一个站立的人，我们知道人们通常站在地板上，因此他们的脚必须在地面上。了解身高有多高也有助于我们从相机推断出它们的深度（距离）；例如，图像中50像素高的人很可能是100像素高的人的两倍。（这也让人想起[11]，他使用汽车和行人探测器以及已知大小的汽车/行人来估计地平线的位置。）
 
本文的其余部分安排如下。第二节论述了前期工作。第三节描述了我们从人类视觉中获得的直觉。第四节描述了我们为三维模型选择的表示。第五节描述了我们的概率模型，第六节描述了使用的特性。第七节描述了我们为测试我们的模型而进行的实验。第八节将我们的模型扩展到从稀疏视图构建大型三维模型的情况。第九节演示了如何将来自对象识别器的信息合并到我们的三维重建模型中，第十节总结。
 
二、前期工作
 
对于一些特定的设置，一些作者开发了从单个图像进行深度估计的方法。示例包括来自着色的形状[12]、[13]和来自纹理的形状[14]、[15]；但是，这些方法很难应用于颜色和纹理不太均匀的曲面。Nagai等人[16]使用隐马尔可夫模型对已知的、固定的物体（如手和面孔）。Hassner和Basri[17]使用基于实例的方法从已知对象类估计对象的深度。Han和Zhu[18]对放置在无背景区域的已知特定类别的物体进行了三维重建。Criminisi、Reid和Zisserman[19]提供了一种交互式的三维几何计算方法，用户可以在其中指定对象分段、某些点的三维坐标和对象的参考高度。Torralba和Oliva[20]研究了图像的傅里叶谱与其平均深度之间的关系。
 
在当前的工作，Saxena, Chung和Ng (SCN)[6]，[21]提出了一种基于单眼图像特征的深度预测算法，并成功地应用于提高立体视觉的性能[22]。Michels, Saxena和Ng[7]还使用单目深度感知和强化学习在非结构化环境中自主驾驶遥控汽车。Delage, Lee和Ng (DLN)[8]，[23]和Hoiem, Efros和Hebert (HEH)[9]假设环境是由带垂直墙的菲亚特地面构成的。 DLN考虑的是室内图像，而HEH考虑的是室外场景。他们将图像分为水平/地面和垂直区域（也可能是天空），从图像中生成一个简单的“弹出”类型浏览（fiy-through）。
 
我们的方法使用马尔可夫随机场（MRF）来模拟单眼线索和图像各部分之间的关系。MRFs是机器学习的主力，已经被应用于各种局部特征不足和需要使用更多上下文信息的问题。例如立体视觉[4]、[22]、图像分割[10]和对象分类[24]。
 
在多幅图像的三维重建中，如在立体视觉和运动结构中，也有大量的前期工作。我们不可能在这里公正地对待这些文献，但最近的调查包括[4]和[25]，我们将在第八节进一步讨论这项工作。
 
三、场景理解的视觉线索
 
图像是由三维场景投影到二维上形成的。因此，只要给定一幅图像，真正的三维结构就不明确，因为一幅图像可能代表无限多的三维结构。然而，并非所有这些可能的三维结构都有同样的可能性。我们所处的环境结构合理，因此人类通常能够利用先前的经验推断出（几乎）正确的三维结构。
 
给定一幅图像，人类使用各种单眼线索来推断场景的三维结构。其中一些提示基于图像的局部属性，例如纹理变化和渐变、颜色、雾度和散焦[6]、[26]、[27]。例如，当以不同的距离或方向查看时，曲面的纹理会显示不同。带有平行线的平铺地板在图像中也会显示出倾斜的线条，这样远处的区域在线条方向上会有较大的变化，而附近的区域在线条方向上会有较小的变化。同样，在不同的方向/距离查看时，草地也会显示不同。我们将在我们的模型中捕捉这些线索。然而，我们注意到，单靠局部图像线索通常不足以推断三维结构。例如，蓝天和蓝色物体都会产生相似的局部特征；因此很难仅从局部特征估计深度。
 
人类在空间上“整合信息”的能力，即理解图像不同部分之间的关系，对于理解场景的三维结构至关重要。[27，第11章]例如，即使图像的一部分是均匀的、没有特征的灰色斑块，人们通常也可以通过查看图像的附近部分来推断其深度，从而识别该斑块是否是人行道、墙等的一部分。因此，在我们的模型中，我们还将捕获图像不同部分之间的关系。
 
人类认识到许多视觉线索，比如某一特定形状可能是一座建筑物，天空是蓝色的，草是绿色的，树长在地面上，上面有叶子，等等。在我们的模型中，单目线索与三维结构的关系，以及图像各部分之间的关系，都将通过监督学习来学习。具体来说，我们的模型将被训练成使用一个训练集来估计深度，在这个训练集中，地面真实深度是使用激光扫描仪收集的。
 
四、表示
 
我们的目标是从图像中创建一个完整的照片真实的三维模型。在计算机图形学和其他相关领域中的三维模型的大部分工作之后，我们将使用三维模型的多边形网格表示，其中我们假设世界是由一组小平面组成的。
 详细地说，给定场景的图像，我们首先在图像中找到小的均匀区域，称为“超级像素”[10]。每个这样的区域表示场景中的相干区域，所有像素具有相似的特性。（见图2）我们的基本表示单位是世界上的这些小平面，我们的目标是推断每个平面的位置和方向。
 
 
 
 五、概率模型
 
仅从局部线索很难推断出一个区域的三维信息（见第三节），需要根据其他区域的三维信息推断出一个区域的三维信息。
 
在我们的MRF模型中，我们尝试捕获图像的以下属性：
 
图像特征和深度：超级像素的图像特征与超级像素的深度（和方向）有一定关系。
连通结构：除遮挡情况外，相邻的超混合体更容易相互连通。
共面结构：如果相邻的超混合体具有相似的特征并且它们之间没有边，那么它们更可能属于同一平面。
共线性：图像平面中的长直线更可能是三维模型中的直线。例如，建筑物的边缘，人行道，窗户。
 
注意，这四个性质中没有一个本身就足以预测三维结构。例如，在某些情况下，局部图像特征不是深度（和方向）的强指示器（例如，在没有特征的空白墙壁上的补丁）。因此，我们的方法将在mrf中组合这些属性，其方式取决于我们对每个属性的“置信度”。在这里，“置信度”本身是根据本地图像提示来估计的，并且会因图像中的区域而异。
 

 
 
 
 
 
 
 
 
 
 共线性：考虑二维图像中长直线上的两个超混合i和j（图8a）。有无穷多个投影到图像平面中直线的曲线；但是，图像平面中的直线更有可能是三维中的直线（图8b）。因此，在我们的模型中，我们将惩罚点（如）与理想直线的相对（分数）距离。
 
 
 
 
 六、特征
 
对于每个超级像素，我们计算一组特征来捕获第三节中讨论的一些单眼线索。我们还计算特征来预测图像中有意义的边界，例如遮挡和褶皱。我们依赖于大量不同类型的特征，使我们的算法更加健壮，甚至可以将其推广到与训练集非常不同的图像。
 
 
 
 七、实验
 
A.数据收集
 
我们使用定制的三维扫描仪来收集图像（如图11a）及其相应的深度图（如图11b）。我们收集了534幅深度图，图像分辨率2272x1704，深度图分辨率55x305，并使用400幅来训练我们的模型。这些图像是白天在帕洛阿尔托市及其周边地区的不同城市和自然区域收集的。
 
我们在134张图片（使用我们的三维扫描仪收集）和588张互联网图片上测试了我们的模型。这些图片是通过在google图片搜索中发布关键词来收集的。为了收集数据并以完全公正的方式对算法进行评估，要求与项目无关的人员收集环境图像（大于800x600大小）。该人士选择了以下关键词来收集图像：校园、花园、公园、房屋、建筑、学院、大学、教堂、城堡、庭院、广场、湖泊、寺庙、场景。这样收集的图像来自世界各地，所包含的环境与训练集有着显著的不同，例如山、湖、夜景等。人们只选择那些“环境”的图像，即，在搜索关键字"方形"时，删除了几何图形"方形"的图像;没有其他对数据进行了预筛选。
 
 B.结果和讨论
 
我们对588幅互联网测试图像和134幅激光扫描仪采集的测试图像进行了广泛的评估。
 在表格一中，我们比较了以下的算法：
 （a）基线：点式MRF（基线-1）和平面参数MRF（基线-2）。基线MRF是在没有任何的图像特征的情况下训练，因此会重新选择一个“优先”的深度图排序。
 （b）我们的点式MRF：有约束和没有约束（连通性、共面性格共线性）。
 （c）我们的平面参数MRF（PP-MRF）：没有任何约束，只有共面约束，全模型。
 （d）Saxena等人（SCN），[6]，[21]仅适用于定量误差。
 （e）Hoiem等人（呵呵）[9]。为了公平起见，我们在计算错误之前缩放并移动它们的深度映射，以匹配测试图像的全局尺度。没有标度和偏移，它们的误差要高得多（相对深度误差为7.533）。
 
 
 表1显示，我们的模型（点式MRF和平面参数MRF）在深度预测的定量精度方面都优于其他算法。平面参数MRF提供更好的相对深度精度，并产生更尖锐的深度图（图11、12和13）。表1还显示，通过捕获连通结构、共面性和共线性的图像特性，该算法生成的模型变得明显更好。除了减少定量误差外，PP-MRF确实产生了更好的三维模型。当生产三维五面图时，即使定量数字可能仍然显示出小的误差。
 
 
 我们的算法对64.9%的图像给出了定向正确的模型，而HEH的正确率33.1%。定向评估由与项目无关的人员按照脚注6的准则进行。Delage，Lee和Ng[8]以及HEH通过在“地面垂直”边界折叠图像来产生弹出效果——这一假设对于大量图像来说是不正确的。因此，我们的方法在这些图像中失败。三维模型的一些典型示例如图14（注意，图1、13、14和15所示的所有测试用例都来自从互联网下载的数据集，图15a除外，图15a来自激光测试数据集。）这些示例还表明，我们的模型通常更为详细，因为它们通常能够用多个（超过100个）平面来模拟场景。
 
我们做了进一步的比较。即使这两种算法在图像上都被定性地评价为正确的，有一种结果仍然可能是优越的。因此，我们让这个人比较这两种方法，并决定哪一种更好，还是平手。表二显示，我们的算法在62.1%的情况下输出更好的模型，而HEH在22.1%的情况下输出更好的模型（与其他情况相同）。
 完整的文档描述了无偏人类判断过程的细节，以及由我们的算法生成的三维五线谱，可在以下网站上获得：http://make3d.stanford.edu/research
 
我们的一些模型，如图15J中的模型，有外观缺陷——如拉伸纹理；更好的纹理渲染技术将使模型更具视觉美感。在某些情况下，一个小错误（例如，在图15h中，一个人被检测到在远处，而在图15k中，横幅被弯曲）会使模型看起来很糟糕，因此被评估为“不正确”。
 
最后，在一个大规模的网络实验中，我们允许用户将他们的照片上传到互联网上，并通过我们的算法查看由他们的图像生成的三维图片。约有23846名用户上传（并评级）了约26228张图片。位用户评价48.1%的车型为好。如果我们只考虑场景的图像，即排除诸如公司标志、卡通人物、物体特写等图像，那么这个百分比是57.3%。我们提供了以下网站，用于下载数据集/代码，以及将图像转换为三维模型/浏览：http://make3d.stanford.edu
 
我们的算法是在帕洛阿尔托市周围白天拍摄的图像上训练的，能够对各种环境（例如，有上或湖的环境、夜间拍摄的环境，甚至绘画）的三维模型进行定性正确的预测。（参见图15和网站）我们相信，根据我们对不同数量的训练示例（这里没有报道）的实验，拥有更大和更多样化的训练图像集将显著改进算法。
 
 
 八、来自多幅图像的更大的三维模型
 
由一副图像建立的三维模型几乎总是不完整的场景模型，因为场景的许多部分将丢失或被遮挡。在这一节中，我们将使用单目和多视图三角剖分线索来创建更好和更大的三维模型。
 
给定场景的一组稀疏图像，有时可以使用诸如运动结构（SFM）[5]、[32]等技术来构建三维模型，这些技术首先拍摄两张或更多照片，然后找到图像之间的对应关系，最后使用三角剖分来获得点的三维位置。如果图像是从附近的相机拍摄的（即，如果基线距离很小），那么这些方法对于远离相机的点通常会遭受较大的三角测量误差。相反，如果选择相隔较远的图像，则视点的改变通常会导致图像变得非常不同，从而很难找到对应关系，有时会导致虚假或遗漏对应关系。（更糟的是，大基线也意味着图像之间可能几乎没有重叠，因此甚至可能存在一些对应关系。）这些困难使得纯几何3-D重建算法在许多情况下失败，特别是当只给出一小组图像时。
 
然而，当数以万计的图片可用时——例如，对于经常拍照的旅游景点，例如国家纪念碑——人们可以使用在许多视图中呈现的信息来可靠地丢弃只有很少的对应匹配的图像。这样做，一个人只能使用一小部分可用的图像（~15%），仍然可以获得“三维点云”的点匹配使用SFM。这种方法已经非常成功地应用于著名的建筑，如圣母院；这种算法的计算成本非常高，并且需要大约一周的时间在一组计算机上运行[33]。
 
许多基于几何“三角剖分”的方法有时会失败（特别是当只有少数场景图像可用时），原因是它们没有利用单个图像中的信息。因此，我们将扩展我们的mrf模型，以无缝地结合三角剖分和单目图像的线索，以建立一个完整的照片真实的三维场景模型。使用单眼提示也将帮助我们建立仅在一个视图中可见的零件的三维模型。
 

 
 
 
 D.幻影飞机
 此提示在多个摄影机之间强制执行遮挡约束。具体地说，每个小平面（超级像素）都来自于由特定相机拍摄的图像。因此，在相机和那个小平面的三维位置之间必须有一个未被遮挡的视图——也就是说，这个小平面必须从拍摄它的照片的相机位置可见，并且任何其他小平面（一个来自不同的图像）都不可能有一个遮挡这个视图的三维位置。这个线索很重要，因为通常连接的结构项，非正式地试图将两个小平面中的点“连接”在一起，会导致模型与此遮挡约束不一致，并导致我们称之为“幻像平面”的结果，即，从拍摄它的相机看不到的平面。我们通过寻找额外的对应点来惩罚有问题的幻影平面和遮挡它的相机视图的平面之间的距离。这往往会使两个平面位于完全相同的位置（即具有相同的平面参数），从而消除幻影/遮挡问题。
 
E.实验
 
在这个实验中，我们创建了一个场景的真实感三维模型，只给出了一些图像（位置/姿势未知），甚至是从非常不同的视角拍摄的图像或很少重叠的图像。图19、20、21和22显示了由我们的算法创建的一些三维模型的快照。使用单目线索，我们的算法能够创建完整的三维模型，即使大部分图像没有重叠（图19、20和21）。在图19中，单图像的单目预测（未示出）给出了在图像中未能捕获拱形结构的近似3-D模型。然而，使用单眼和三角测量线索，我们能够捕捉到这个三维拱形结构。这些型号可从以下网址获得：http://make3d.stanford.edu/research
 http://make3d.stanford.edu/research
 九、纳入对象信息
 
在本节中，我们将演示我们的模型如何还可以合并其他可能可用的信息，例如，来自对象识别器的信息。在以前的工作中，Sudderth 等人[36]表明物体的知识可以用来获得粗略的深度估计，Hoiem等人[11]利用对物体及其位置的了解来改进对地平线的估计。除了估计视界外，物体的知识和它们在场景中的位置也提供了关于场景三维结构的强有力的线索。例如，一个人更可能站在地面上，而不是在地面下，这就对三维模型施加了某些限制，这些限制可能对给定的图像有效。
 
在这里，我们给出了一些有关对象的信息可用是出现的此类提示的示例，并描述了如何在MRF中对它们进行编码：
 

 
 
 十、总结
 
提出了一种从单个静止图像中推断三维结构细节的算法。与以前的方法相比，我们的算法创建了详细的三维模型，这些模型在数量上更精确，在视觉上更令人满意。我们的方法首先将图像过度分割成许多称为“超级像素”的均匀区域，然后使用MRF推断每个区域的三维位置和方向。除了假设环境是由许多小平面构成外，我们没有对场景的结构做出任何明确的假设，例如Delage等人的假设。[8]和Hoiem等人。[9]场景包括竖立在水平地板上的垂直表面。这使得我们的模型能够很好地推广，甚至可以推广到具有显著非垂直结构的场景。与现有技术相比，我们的算法在预测深度的定量精度和定性校正模型的分数方面都有显著的改善。最后，我们将这些思想扩展到使用稀疏图像集建立三维模型，并展示了如何将目标识别信息合并到我们的方法中。
 
深度知觉问题是计算机视觉的基础，在过去的几十年里，它引起了许多研究者的关注，并取得了重大进展。然而，这项工作的绝大多数，如立体视觉，都使用了多个图像几何线索来推断深度。相比之下，单一的图像线索提供了一个很大程度上正交的信息来源，一个迄今为止一直被相对开发不足的信息来源。鉴于深度和形状感知似乎是许多其他应用的重要组成部分，例如对象识别[11]、[38]、抓取[39]、导航[7]、图像合成[40]和视频检索[41]，我们相信单目深度感知有潜力改进所有这些应用，尤其是在场景只有一个图像可用的设置中
 
致谢
 
我们感谢Rajiv Agarwal和Jamie Schulte在收集数据方面的帮助。我们还感谢杰夫·米歇尔斯、奥尔加·罗斯科夫斯基和塞巴斯蒂安·特龙的有益讨论。这项工作得到了国家科学基金会CNS-0551737奖、海军研究办公室Muri N000140710747和Pixblitz工作室的支持
 
 
 
 
对于大多数人工结构，如建筑物，这种假设是相当准确的。一些自然结构，如树木，也许可以更好地用圆柱来表示。然而，由于我们的模型非常详细，例如，对于一个小场景，大约有2000个平面，因此平面假设在实践中非常有效。 ↩︎
 
为了比较这些算法，研究人员被要求计算每种算法的错误数。当图像中的主平面（占图像面积的15%以上）相对于其相邻平面处于错误位置，或者平面的方向错误超过30度时，我们定义一个错误。例如，如果在错误的地方折叠图像（参见图14，图像2），则将其计为错误。同样地，如果我们预测建筑物的顶部远，底部近，使建筑物倾斜，这将被视为一个错误。 ↩︎
 
对用户可以上传的图像类型没有限制。用户可以将模型评为好（拇指向上）或坏（拇指向下）。 ↩︎
 
即，对于远距离的物体，深度估计往往不准确，因为即使三角测量中的小误差也会导致深度的大误差 ↩︎
 
 

房屋施工图根据专业不同，可分为：
 ⦁    建筑施工图
      总平面图、平面图、立面图、剖面图、详图。
 ⦁    结构施工图
      基础图、结构平面图、构件详图。
 ⦁    设备施工图
      给水排水施工图、供暖施工图、通风与空调施工图、电气施工图。
 
下面详细分析一下建筑施工图。
 
1.总平面图
 
⦁    新建房屋及周围的总体情况
      位置、层数、标高、朝向
      道路、绿化、管线的布置
      周围地形地貌
 ⦁    建筑定位、施工放线、总平面布局
   
 
2.平面图
 
⦁    平面图的形成
       在门、窗洞口处，水平剖切房屋，移去上部，做下部分水平投影。
 ⦁    平面图的内容
       首层、标准层、顶层、屋顶
 ⦁    平面图的识读
       形状、尺寸、布置、朝向
       平面定位轴线网
       各层楼地面标高
       门窗编号、门开启方向
       剖切位置、必要的文字说明
      
 
     
 
3.立面图
 
⦁    立面图的形成
      建筑物外表立面的正投影图，反映体形、外貌、外墙装修
 ⦁    立面图的名称
      按主次、按朝向、按轴线
 ⦁    立面图的识读
      立面形式和外貌、外墙装修
      室外台阶、勒脚、窗台、雨棚、阳台、屋顶等位置、材料做法。
      门窗布置、外形、开启方向
      标高、竖向尺寸，反映高度
 
     
 
4.剖面图
 
⦁    用铅锤剖切面剖开房屋，移去一部分，做剩余部分的投影
 ⦁    位置：内部构造复杂，并通过门窗洞口
 ⦁    剖面图应与平面图对应
 ⦁    剖面图的内容
      被剖到部分的构造做法
      标高、竖向尺寸
      承重构件位置及相互关系
      屋顶形式及泛水坡度
      索引符号:需画详图的部位
 ⦁    剖面图的识读
      建筑标高：装修后标高
      结构标高：结构层标高
      楼地面标注建筑标高，其他部位标注结构标高。
      详细结构由结构施工图表达。