用Mendeley进行文献管理

在做一个有关科研的项目时，我常常把该项目相关的论文全部放到同一文件夹下。一个pdf文件刚下载下来的时候，我还能分辨出这个文件是哪篇论文。但过了一两天，我还想找这篇论文时，就只能望着文件夹里乱七八糟的pdf文件名而不知所措了（论文pdf的命名方式五花八门）。我深知对论文进行管理的重要性，但由于之前的项目涉及的论文数量较少，我勉勉强强没有在搜索文献时碰到太多困难，出于懒惰，我没有对文献进行管理。最近，我要开始写毕业论文了，恰好有了一个让自己开始学习文献管理的理由。

我用极快的速度在网上搜索文献管理软件有关信息，在知乎上稍微浏览一会儿后，选择了Mendeley这款软件。我没用过其他软件，无法给出不同软件之间的优劣，只能根据别人的信息，学习一下Mendeley这款文献管理软件的用法，并把这些有用的信息分享出来。本文将包括以下内容：

• Mendeley基本安装使用方法
• 如何用Mendeley达成自己的文献管理目标

Mendeley下载安装

开始使用Mendeley前，要完成以下几件事：

• 注册账号
• 下载软件
• 安装word引用插件

直接在搜索引擎中搜索“Mendeley”即可找到官网(https://www.mendeley.com )。官网上有一个很大的“DOWNLOAD”，可以跳转到软件版本选择界面，有各个平台的软件版本以供下载。官网上还有一个很显著的“Create Account”，设置邮箱密码，不需邮箱验证即可注册。

软件下载安装输入账号密码后即可开始使用软件。

初次点开软件后，有一个添加word文献引用插件的提示，可以在关闭了所有word文档后点击安装。

Mendeley基本使用方法

Mendeley包括以下功能：

• 文档层级管理
• 文档导入
• 文档重命名
• 文档辅助标记
• 文档同步
• 文档搜索

文档层级管理保证了文档能按一定逻辑结构进行存储，这是一切后续文档操作的基础。文档经导入后，可以按照你熟悉的方式进行重命名，也可以对文档添加一些标记，方便从文献的检索和管理。文档同步保证了一台电脑上导入的文档能够在其他设备上方便地访问。

文档层级管理

软件左上角My Library就是文件夹列表。你可以自己创建文件夹并重命名，并在文件夹中再创建文件夹，实现对论文的分项目、分类管理。

除了自定义文件夹外，还有一些预定义文件夹，从这些文件夹的名字基本就可以知道它们的用途。比如Recently Added文件夹，就和win10系统下资源管理器左上角的”快速访问“一样，能找到最近访问的文档。

文档导入

为了把pdf格式的论文导入，可以点击左上角Add在操作系统的资源管理器中添加文档，也可以直接在资源管理器（此电脑）中框选一堆文档拖入中间的空白处。注意到中上处有一个文件夹的提示（本图中是Undergraduate Capstone)，表明论文是被导入了一个具体的文件夹中。

文档导入不仅仅是让软件”知道“了你有哪些论文，在文档导入后，软件还会根据pdf自动分析出论文的发表时间、作者、期刊。

文档重命名

重命名功能能够把重新把文档在操作系统里的文件名按一定格式进行修改，而不只是在软件中取了一个虚拟的名字。当然，为了保证重命名的正确运行，需要关掉正在打开的pdf文件。重命名的具体操作如下:

选择一些文档后，点击右键，可以在选项中找到“重命名文档”这一功能。

重命名功能能让每篇论文的文件名以任意的顺序包含期刊、发表年份、作者、标题这四种信息。比如在上面的截图中，我是按“年份-作者-标题”这样的格式对所有文件重命名。

重命名结束后，可以再次右键点击文档选择”打开文档所在文件夹“（Open Containing Folder)，在操作系统里查看这些文件。

文档辅助标记

右键点击文档，可以看到一个叫做”标记为“（Mark As）的选项，该选项能给每个文档一些标记，包括是否读完，是否喜欢，是否需要回顾。

界面右端有三个选项卡，其中笔记（Note）一栏可以对每一个文档做一些简要的笔记。

界面右端Details选项卡里有一个标签（Tags）选项，可以给文章添加标签。

文档同步

界面上方有一个循环箭头图标，点击该图标即可同步。理论上只要是登录同一个账号，就可以在不同的电脑上访问同样的内容。

文档搜索

界面右上角有一个搜索框，输入东西就可以搜索。

理论上，不管是论文名、文章内容、还是添加的一些辅助标记，都可以通过搜索功能搜索到。这也是添加辅助标记的意义所在。

使用文献管理软件的目标

使用工具一般有两种出发点：知道有哪些需求，而去寻找工具；得知了工具有哪些功能，再去看这些功能能做什么。前几节只介绍了Mendeley这个工具本身能做什么，而这一节将按照第一种使用工具的出发点，忽视工具而只谈论文献管理有哪些需求。下一节将结合工具和需求分析一下该怎么使用Mendeley。

我的阅读论文经验尚浅，这里仅能给出两个文献管理的需求：快速检索、快速预览。

在读某一篇论文的时候，经常会碰到一个子问题已经有了一个成熟的解决方法，作者直接贴了一篇参考文献的情况。这个时候，你肯定很希望能够立马看到这篇参考文章，和刚刚阅读的内容关联起来。如果这篇参考文献没有下载下来，你还可以发出一两句怨天尤人的抱怨：”世界上论文怎么这么多啊“，”下载个论文怎么这么麻烦啊“。但如果这篇论文已经下载了，你在电脑里找不到，你只能怪自己道：”我之前下载论文的时候怎么没有好好整理一下啊！“我们希望脑中想到一篇论文，屏幕上就能立刻出现哪篇论文。

还有一些情况，我们看到一篇以前读过的论文，突然忘记了它讲了什么。打开文档、浏览全文、关闭文档可要花费不少时间。一个最简单的方法，就是对每一篇文章做一些自己的笔记。看着自己对论文的描述，一般就能想起论文的内容。问题是，电脑里有那么多论文，存在文件夹的各个角落里，该把笔记写哪里，怎么写呢？

使用Mendeley完成文献管理

有了Mendeley，完成文献的快速检索和快速预览讲不再是梦想。Mendeley本身提供了多种给文档添加标记的方式，利用搜索功能能方便快捷地定位到你想要的文章。同时，利用软件的笔记功能，能够给每篇文章添加自己的描述，配合上搜索功能，达到快速找到文章，并快速想起文章的”combo“。

根据我现在对Mendeley的认知，一个合理的使用该软件的流程如下：

1. 为当前项目创建新的文件夹，让自己有一种”我要开始做大事了“的仪式感
2. 找一堆论文，下载并导入Mendeley
3. 重命名所有论文，使得哪怕不打开Mendeley也能快速在文件系统中找到文章
4. 每看完一篇论文后，添加一些能让自己看得懂的简短笔记，视心情添加标签
5. 如果对该项目相关的论文有了一定的认识，建立子文件夹，对文献进行一级分类
6. 动态维护添加这个文件夹，根据需要对文献进行搜索

总结

我向来觉得写一篇大部分都是信息（比如软件安装方法）的文章没什么意义。网上参考资料那么多，何必要再写一些原创性较低的东西呢？但最后我还是完成了这样一篇”工具使用指南“的文章，介绍了Mendeley这个文献管理软件的用法。其原因是，我写这篇文章的目的是为了让我自己有动力去学习这个软件的使用方法，并通过费曼学习法，利用向他人重述来加深自己对信息的记忆。

这篇文章主要面向的是没有用过Mendeley的读者，尤其是从未用过文献管理软件的读者。读者通过文章前半部分，在没有下载软件的情况下，能大致知道Mendeley有哪些功能；下载了软件后，可以知道如何使用这些功能。文章后半部分对科研经验尚浅的人较有帮助，提出了一些简单的文献管理需求，并探讨了如何结合软件达成这些需求。

Poisson Image Editing 图像融合/图像无缝编辑经典文献阅读

想不想把自己的头P到别人的图片中？

想不想把别人图片里的彩虹放进自己拍的风景照中？

想不想自己修掉脸上的皱纹？

掌握图像融合技术，以上的一切图像编辑任务都可以轻松完成。

(图片来自论文)

如图所示，利用图像融合技术，可以把一幅图片的部分区域复制到一幅图片（可以是同一幅图片）上，并且让复制过去的图片块保持之前的色彩风格。因此，这种技术有时可以叫做图像无缝复制(image seamless cloning)

论文整体结构

该论文介绍了一种图像编辑的方法，其主要作用是图像边缘的无缝拼合。该方法可以应用到图像融合和图像风格变换等任务中。论文的结构如下：

从结构图可以看出，这种方法的输入是待修改图像、待修改区域及待修改区域的目标梯度，输出是编辑后的图像。基于该图像编辑方法，能产生各式各样的图像融合结果，产生不同结果的方法是修改输入中目标梯度的获取方法。

具体介绍一下这种图像融合方法。这种方法的思想是让图像编辑后的梯度域尽可能和源图像（图像编辑是从源图像复制一块到目标图像）一样，并且编辑区域边缘的梯度值和目标图像一样。图像的梯度可以理解为图像相邻像素的变化量。有研究指出，比起绝对的像素值，人眼对梯度值更敏感，因此维持编辑区域内部梯度不变，边界和目标图像“接轨”能让图像融合的质量更高。梯度值尽可能不变，就是让图像编辑前后梯度域的差值尽可能小，问题就变成了一个纯数学问题。通过相关的数学工具，可以求解出编辑后的图像来。

论文细节

优化目标的建模与求解

该论文方法的核心是建立了梯度域的优化目标后，如何用数学方法对这个问题求解。

首先，稍微介绍一下这个优化问题是如何建模的。输入图像、输出图像都可以看成一个定义域在平面上的一个函数。对输出图像的求解即对一个未知函数的求解。求解未知函数，涉及泛函的知识，需要用到欧拉-拉格朗日方程，有一篇非常好的博客[2]介绍了有关的数学知识。

有了对问题的建模后，论文直接给出化简后的待求解方程。该方程是一个泊松方程，即与函数二阶导数相关的偏微分方程。对该方程求解，即可得到最终的图像。

图像的数值都是离散的，对一个图像的求解，最终可以转化成对该图像每个像素值的求解，即求解一个多元方程。此问题中，该方程是一个线性方程。利用求解多元线性方程的方法即可解出此问题。

事实上，该问题的建模和求解中涉及了很多数学定义，这些数学的细节是否理解对整篇文章的理解、方法的创新不是十分重要。对于一个研究计算机技术的人来说，优化目标的设定才是最重要的。

利用方法产生不同的编辑效果

论文的所有图像效果都是基于同一种方法。也就是说，只要理解了最基本的把一幅图片无缝融合进另一幅图片的原理，其他图像编辑效果都可以通过同样的原理推导而来。

如果把源图像的待修改区域的梯度做为目标梯度直接输入进方法，由于图像边缘梯度和目标图像一样，内部和源图像一样，复制过去的图像可以无缝地对接到目标图像上。利用该图像融合方法，可以实现“图像隐藏”：比如把脸上没有皱纹的地方复制到有皱纹的地方，达到去皱纹效果。

只用源图像的梯度，而忽视目标图像待修改区域的梯度，则会完全抛弃待修改区域原来的信息。在复制一些半透明的图像（如彩虹）时，如果抛弃掉目标图像待修改区域本身的性质，就会产生很差的效果。论文中提出，可以把源图像梯度和目标梯度的较大值做为方法的目标梯度，这样经过图像编辑后图像的待修改区域能融合两幅图像的性质。

通过上述例子，可以得知目标区域的梯度是如何决定图像编辑效果的。对目标区域的梯度进行一些“魔改”，就能得到不同的结果，比如结构图中提到的扁平化、光照修改和地砖无缝拼接等。

论文实现

理论上，我会对论文进行实现。以后我会更新此文，加入实现的代码仓库链接。

其实随便一搜就能找到很多该论文的实现，毕竟这篇论文是图像融合的一个非常经典的方法。很多matlab代码技术性较弱，很多东西都写好了，因此我附上了一个该论文的C++实现[3]。当然，用C++的话也要调用不少库函数，最烦人的线性方程组求解是必须得调一下库的。

总结

本文对论文“Poisson Image Editing”进行了一个简要介绍，其本意是通过总结论文大意来加深我自己对论文的认识，并且方便之后对其他图像融合领域的对比阅读。

当然，这篇文章对读者来说也有一定可读性。本文并没有对原文进行死板的翻译，而是从整体到局部，大致介绍了论文中的主要内容。对于只是想浏览该文章的读者，可以学到一种新的P图方法，图一乐；对于在精读论文之前看到这篇文章的读者，可以大致知晓文章是在讲什么，解决什么问题，用了什么方法，产生什么结果；对于读完论文之后的读者，可以把这篇文章和自己的收获进行对比，看看哪些内容是读到了的，哪些内容文章没有提到，甚至哪些地方写错了，写得不够好，以加深自己对论文的理解。当然了，如果你觉得我讲的你都读到了，你也可以写出一样的东西，那说明你是个高手，学得很不错，毕竟想要掌握我这种概述能力是十分困难的。

参考资料

[1] Pérez P, Gangnet M, Blake A. Poisson image editing[M]//ACM SIGGRAPH 2003 Papers. 2003: 313-318.

[2] https://www.cnblogs.com/bigmonkey/p/9519387.html

[3] https://github.com/cheind/poisson-image-editing

2023.4 更新：
最近在重新温习Poison Image Editing，看了看自己以前写的文章，发现这篇文章写得一塌糊涂。写得这么简单，谁看得懂啊？或许我当时为了便于理解，没有在文章里用数学符号。但这文章也写得太不清楚了吧。我现在来稍微重新总结一下这个方法。

泊松图像编辑要解决的基本问题是图像融合：输入源图像、源图像上的编辑区域、目标图像、目标图像上的编辑区域，我们想把源图像的编辑区域「贴」到目标图像的编辑区域上。相比于最朴素的复制粘贴，我们希望图像贴过去后看起来没有那么突兀，就像文章展示出来的一些融合结果一样。

作者把这种图像融合看成了一个优化问题：在编辑区域边界处的像素值应该保持不变（保持原来目标图像在此处的像素值）的前提下，令编辑区域内部的梯度值与源图像该处的梯度值尽可能相似。求解这个优化问题，就能得到编辑区域内的像素值。

归根结底，泊松图像编辑的输入是一幅目标图像、一个梯度值、一个编辑区域。图像融合只是应用之一。通过修改输入的来源，可以完成多种任务。

泊松图像编辑的原理就是这么简单。更详细的介绍在那篇代码实现的博文里有介绍。

这篇文章确实是一篇实实在在的「博文」：只有我自己能看懂，别人都看不太懂。可见，我当时的描述能力比现在差远了。反过来说，没过几年，我的描述水平就大有提升。这真是太可怕了。

套磁，据传来自北京方言，意为“套近乎”，特指在申请出国留学时，提前给导师发邮件推荐自己，以增加录取几率。套磁信都是拿英文写的，我写起来很不顺手。现在，我打算解开封印，用中文写出一篇套磁信，让任何阅读者仅通过文字就能感觉到我的强大之处。

如果套磁信可以用中文写

尊敬的教授：

您好。

我是北京理工大学一名计算机专业的大四学生。我正在申请你们学校的博士。我对您的研究十分感兴趣。我没有名列前茅的排名或顶会的论文的来证明我的实力，但我依然敢断言，我是一名非常优秀的学生，我能够为您的研究做出贡献。请允许我介绍自己的背景，以及我为什么很适合加入您的研究团队。

为什么有那么多优秀的学生在博士期间退学呢？一个科研工作者最重要的品质是什么呢？在我看来，参与科研的动机是最重要的。许多人从小知晓科学家的事迹，抱有改变世界的理想，寒窗苦读，披荆斩棘，登堂入室，成为博士在读生。然而，现实与理想产生了割裂，博士生每天的工作是读论文、做实验。不知何时，儿时的幻想逐渐破灭，绞尽脑汁地发论文毕业成了最重要的事。我认为自己已经认清了博士生在做什么，并依然渴望成为一名博士生。在两名美国教授（一对老夫妇，已经培养出了数十个知名教授）的教导下，我找到了令我持之以恒的动力：与有思想的人交流合作，创造新知识并把我的思想传递给其他人。在这强大的动力下，我能克服读博士期间的一切挑战，成为一名优秀的研究者。

光有斗志，没有实力是不够的。据我所知，在科研中，最重要的实力不是考高分、拿奖的能力。科研，需要发现分析解决问题的思考能力，以及把自己的想法和他人分享沟通的交流能力。这两种能力都是我的强项。可惜的是，这两种能力难以用客观的标准来衡量，只能通过某些事情来体现。我打算用一些例子和事实来证明我这两方面的能力。我常常把编程的思想用于生活：在学习新知识的时候，我会建立一颗“树”来梳理知识的自浅到深的结构；在解决一个较为具体的问题的时候，我会像写程序先写主函数再实现各个子函数一样，先把问题划分成互不相交的子问题，梳理整理的流程，再逐个解决子问题。我在演讲和分享知识上颇有经验：我的中国导师听了我的两次演讲，他感到“印象深刻”；我给同年级和低年级的同学都上过算法课，得到了广泛好评。

通过以上的介绍，您应该知道我是一个有科研潜力的人了。接下来，我将从我的专业技能和科研经历来分析为什么我适合加入您的团队。我自认为我的编程水平堪称顶尖：我在ACM中拿过金牌，有算法实现经验；我实现过C编译器、路径追踪渲染器、光线跟踪算法、图像分割算法……等程序，有复杂项目编程经验。我能够又快又准地实现一个功能复杂的程序，同时保证所使用的算法与数据结构尽可能高效。图形学研究涉及的算法十分复杂，经常需要编写大型程序。我有图形学知识基础，也有过硬的编程经验。我的专业技能定能在研究中发挥重要作用。

通过看您的网站，您之前的研究是………………………………………………。我之前参与过图形学的研究 …………………………………………。我认为我们的研究方向非常匹配。对于您的……………………论文，我也许可以…………………………，我的……………………技能或许能够对改进这篇论文提供帮助。

从您的介绍中，我认为您是一个………………的人，我也是………………的人，我觉得我加入您的团队十分合适……………………………………这是我的CV与个人网站。如果您对我的背景感兴趣，欢迎进行进一步的交流。

Best，

周弈帆

套磁信评析

严格来说，这不能算一个套磁信模板。里面的文字太多了，老师没那么多时间来看的。也正因为这样，我拿英文写起套磁信来的时候浑身不适，感觉手脚都被束缚了。今天用中文写一封套磁信，并发到这里，就是为了能够在完全自由的情况下用文字展示我的科研能力。我相信，如果你是一个高手，你读完了我的这封信，一定会明白我是有多么强大；如果你没有这种感觉，说明你还年轻，还有很多事需要想清楚。这里我也不能说得太明白，如果我把道理全部说出来，你就无法得到成长。

以下是套磁信的赏析：

正文第一段开门见山，用最少的文字介绍自己的背景和目的。之后，别出心裁地先提自己的缺点，与绝大多数先提自己优越客观条件的套磁信形成对比，吸引老师的眼球，激发阅读兴趣。最后，介绍邮件的目的：介绍自己，并用议论的说法证明自己时候老师的科研。

第二段，从科研动机证明自己的科研能力。因为我认为，科研的动机的最重要的一件事，所以放到第二段介绍。我先使用较为夸张的口吻，描述了一般的博士生的悲惨经历，再使用对比的手法，写出自己与他们的不同，以证明自己对于读博士的心理准备。

第三段，再从一个刁钻的角度证明自己的能力。思想能力、沟通能力都是难以量化的。但不可否认，它们都是重要的能力。老师看到你对于这两种能力的重视，首先就会认为你很有思想，已经把事情看透了。之后，我论证我能力的方法堪称绝妙：我用例子证明思考能力，用事实证明沟通能力。短短几句话，一个睿智、高傲、善辩的形象逐渐树立起来。

其实，整篇文章都使用了欲扬先抑的手法，从第一段的“没有客观成就”开始，一直是“抑”。从第三到第四段开始，是“扬“。ACM金牌、项目经验，证明自己的手牌一张一张打出。我用一些简历里不是很明显的客观事实来证明我的专业能力。前面几段算是论证，这一段就算是在举例子辅助论证了。

再接下来一段讲自己和导师的科研经历，这一段要具体问题具体分析，我在这里没有认真写。

最后一段，如果导师的个人网站的内容写得多，我认为可以写一些有关导师个人的东西，以证明自己的导师的重视，有强烈地进行合作的意愿。最后一句话点名整封邮件的意图：如果老师对我感兴趣，快点给我回信。

通篇看下来，整篇套磁信抑扬顿挫、起承转合，一应俱全。主要思想言简意赅，文章结构清晰明了，复杂想法的表达别出心裁，不可谓不是一篇优秀的文字作品，值得赏析和玩味。

抛开信本身的写作方法不谈，光谈内容。我认为，一个厉害的导师，看到了我的信，一定会认为我是一个厉害的学生；如果他看了我的信没有什么反应，说明他不是一个厉害的导师，那么我不被接受也没有任何遗憾。有人读到这，可能会说，你太狂妄了吧？你本科还没毕业吧？你成绩不是很好吧？你凭什么这么说啊？作为一个读者，你读完后会这样想吗？对此，我只能说，因为你不会，所以你才会。你”不会“对这件事进行深刻的分析，所以你”才会“得出这样的观点。首先，我想说，什么是厉害的导师？没有一个这样的定义。那么，可以说，我认为一个导师厉害，那么这个导师就厉害，因为是我在选导师，不是把这个导师推荐给别人。一个导师没有通过我的筛选，那么我通不通过他的筛选已经无所谓了。有点逻辑思维的人看了我这段解释，又会说：”看了你的邮件接受了你的导师，就是厉害的导师，你就跟着导师干，这不是废话吗？导师不接受你，你想跟着他干也没用啊。“我承认我的第一个解释不太对。那么，我真正想说的是，通过和我的美国导师以及一个优秀的同学的交流，我得出了评价博士录取的最重要的因素。一个人的科研潜力远比客观的证明材料重要，虽然这种潜力难以被挖掘。我对自己的语言表达能力十分自信，我通过文字很好地展示了自己的能力。那么，一个当上了教授的人，自然知道该如何选择学生，自然会被我的语言所打动。

扯了这么多，我是否能被最终录取还是个未知数。这只能算一个套磁信的分享与分析。我说的对不对，我想的能不能成，已经不重要了。做为读者，你学到了什么，才是最重要的。当然对于我来说，能不能成功录取还是有点重要的；哪怕事情没那么顺利，也问题不大。总之，我认为这封套磁信非常有趣，非常欢迎大家来阅读。

最近有好多东西想写，今天先写一篇比较短的文章。

想得越多，干得越少，做得越差

我发现，我在做事的时候，经常会考虑太多东西。考虑得太多，反而在事情开始干活的时候畏手畏脚，不知道该怎么下手。最后，什么事情都没有做成，还不如少想一点。今天，我想讨论一下这种现象的具体表现及其负面影响，以及这种现象的解决方法。

写这篇文章的时候我头脑不是很清楚，很多地方不是很严谨。在描述一个事情/例子的时候，如果用的人称是”你“，这表示我认为这种现象比较普遍，大家可能都会碰到；如果用的人称是”我“，表示这种现象可能比较特别一点，且确确实实发生在了我自己身上。

我的“过载思考”

我在认真对待一项任务的时候，会全方位深入思考这件任务的完成方法，我把我的这种思考方法叫做”过载思考“。过载思考本身是一个非常复杂的话题，我以后可能会专门花一篇文章来总结，现在就简要介绍一下这种思考方法。

在做事情之前，我要求自己明确知道自己的目标是什么。比如在大学里上一门课，正常来说大家的目标是获取更高的分数。我会去问自己：获取高分真的就是我的目标吗？是不是获取这门课的知识才是我的真正目标？还是通过完成这门课的一个项目，来提升项目经验，而不是掌握这门课的知识？只有搞清楚了自己真正的目标，才能针对目标选择最优的每部操作。搞清楚了真正目标后，你会发现一些看似正确的做法，其实并不正确。比如我们学校的操作系统课，拿着一本烂书，讲着没有用的知识，考试考背诵，老师上课在大谈自己的人生经历。在这样一门课上，认真听课，认真准备考试获取高分，在我看来都是浪费时间。我在这门课上学不到任何知识，所以我的目标是获得一个看得过去的分数，我要花最少的时间，让自己在背最少的东西的情况下达成目标，而不是所谓的“认真学习”。

确定了目标之后，要思考达成目标的过程中，哪些是重要的东西，哪些是看似重要的东西。很多时候，你不自己实际经历一遍这件事，踩一遍坑，你可能就不知道哪些事是重要的。但一旦你能提前把可能遇到的坑想好，提前发现完成一件事的最重要的因素，你就能节约大量时间，以及减少陷入负面情绪的时间和可能。比如你为了获得一个好成绩，天天去占前排的座位，去做漂亮的笔记，以”认真的态度“去面对学习，结果学习还是很吃力。其实，学好一门课的重点根本不是一些形式上的东西，不是一个主观上努力认真的态度。要取得更好的成绩，首先要改变思考方法，要去主动地学习；其次，一些技巧还尤为关键，比如获取前几年的题目。凭着主观的意识，去在意那些自己以为重要的东西，取得了不好的结果，最终只能怪自己没有早点看清完成目标的过程中，最重要的某些因素。

有了目标（一个目标函数），有了重要因素（目标函数中权重较大的变量），现在就要考虑计划了。事实上，有了重要因素，计划是一件很显然的事，不如说重要因素的提炼就是为了计划。还是拿刚刚的例子，你知道取得好成绩，要去获取前几年的卷子，你去努力向学长学姐要题目就行了。

准备工作结束，在开始做事情之后，我会不自觉地，以批判的角度看待自己的每一个行为。我会去考虑诸如这样问题：我的每一步行动是否能让我更靠近目标？我是否有的时候在凭借着主观看法一厢情愿地做事？我的哪些做法是不够好的，可以改进的？我是不是做错了一些事？

以上是我的”过载思考“的一个大致介绍。之所以取这个名字，是因为在完全开启这个能力的之后，我会消耗大量脑力在推进任务进度之外的思考上，大脑有一种过载的感觉。过载思考帮助我成功完成了很多事，避开了许多弯路。但是，有的时候我过度使用这种思考方式，导致了很多负面的结果。

过载思考的弊端

犹豫

使用过载思考时，要花很多时间在准备上，这意味着不能及时地开展行动。而有的时候，时间又是任务中重要的限制因素。比如在棋类比赛中，先有一个总的保留用时，再会对每步棋进行读秒。如果思考时不注意时间，因为时间的限制而导致思考中断，只会导致产生极差的做事成果。

另外，有些任务随着时间的变化，其性质也会发生变化。这种事情一般发生在抢占资源的任务上。比如你看上了一个人，思考太久，结果别人都结婚了。由于思考得太久，任务本质发生了变化，使得你不得不又去重新思考，陷入了一种无法开始做事的死循环中。这样往往会导致机会的错失。

自责

我在使用过载思考时，会批判地看待自己。结果我经常会产生某些不必要的，对于过去已经无法改变的事情的批判。比如一手牌打错了，我会对自己说：”这也太菜了吧。“一些事情做得慢了，拖到ddl前才完成，我会想：”我为什么这么拖拉啊。“这些想法是完全没有意义、没有建设性的，不能对未来产生任何利处，只会凭空损害自己的内心，让自己产生负面情绪。

其实，我完全知道这种现象产生的原因：在一件事做的不够好的时候，人会下意识地感到难受。为了掩盖这种难受，人会产生一些习惯性的应对方法。对我来说，所谓的自责，只是掩盖这种难受的下意识反应。这可能和我童年生活有关：我小时候有事情做好时会挨骂，以至于长大后事情没做好后，会自己责怪自己。我潜意识里虚伪地认为，自责就能让自己看上去意识到了自己的错误，能让自己更好一点。但从理性的角度来看，自责没有任何意义。

大脑崩溃

人的大脑是是有极限的。我从短暂的人生中学到这样一件事……越是工于心计，越会发现人的大脑是有极限的……除非超越人类。

当我也想不做人时，却发现自己大脑崩溃了。

过载思考，意味着需要对任务建模，深刻了解任务的一些细节、原理。当这个任务过于复杂，超过了某个阈值后，大脑就无法处理了。这和电脑内存不够大概是一个道理。这样的例子不太好找，我举一个可能不容易理解的，在我身上发生的例子。我在高考前，发现自己经常考试时间不够。于是，我开始尝试对考试用时安排进行建模。我去思考了一个叫思考效率的东西：人在刚开始思考的时候，思考不是很集中，思考效率不是很高。当思考一段时间后，思维逐渐集中，思考效率较高。真正的思考成果，是思考效率在思考时间上的积分。不同学科的不同类型的题目，有着不同的思考效率-时间曲线。但是，这里面的工作量实在是太大了，而且很多东西是不能量化的，只能是定性地看待，我的大脑完全处理不了这么多东西。结果，我想了一些很没用的东西，对我的高考一点帮助也没有。

大脑崩溃可能会产生严重的后果。如果在一件无关紧要的事情上崩溃，可能只会让我放弃这件事。但最近，我在一些重要的事情上产生了崩溃。结果我突然完全丧失了思考和行动的能力，陷入了不知所措中。好在我吃了个饭，扩充了大脑内存，立马kill了之前的进程，想出了暂时解决问题的方法。

自我怀疑

我一直依靠我的过载思考完成重要任务，以至于我忽略了这种思考方式不是万能的。一旦我没能成功地完成任务，我就会下意识对自己进行全面的否定。一旦陷入了自我怀疑，就会害怕思考，从而失去了正常工作的能力。

解决方法

其实，从弊端的分析中，基本就能得到解决方法了。针对每种弊端，给出对应的方案即可。

为了避免犹豫，应该把时间纳入考虑范围内，不能不加约束地过分细致地计划事情。

为了解决自责，要从理性上认识到自责的原因，克服长期以来的潜在的思考方式，不去做没有意义的事情。如果自己想被责怪，就痛痛快快地骂自己一顿，再向前方看去就好。

为了解决大脑崩溃，首先要意识到世界的复杂性，不要考虑把什么事情都建模清楚。再考虑事情之前，要先考虑事情的规模，考虑可行性。之后，在具体执行任务的时候，可以不看那么远，先尝试把任务拆成能力范围内的子任务，先把子任务完成，再考虑进一步的事情。

为了解决自我怀疑，只需要告诉自己过载思考不是万能的即可。一两次的失败，不能代表这种思考方式的错误，反而代表自己有更多的提升空间。

本文转载自我的知乎回答如何评价北京理工大学第十五届“连山科技”程序设计大赛？

最近时间开始多了起来，我准备多写点东西。

如何评价北京理工大学第十五届“连山科技”程序设计大赛？

光阴似箭，从大一我第一次参加新生赛，到昨天最后一次参加校赛，已经过了三年了。最开始的时候，还能见到14级的强神、庆神，现在20级的新生都已经在比赛中大放光彩了，真是让人感觉时光荏苒；不过，年年比赛都能看到易大师、龙神、牟神、沈帝等人的身影，又仿佛一切都没变过，我的时间永远定格在大一的暑假集训。做为一个退役选手，本次比赛的意义对我的意义已经不在于过了多少题，更多的是一些比赛之外的东西。

按照老规矩，我还是会完全站在个人视角，先对比赛的出题质量、服务质量进行评论，再以时间顺序从网络赛到正赛谈个人经历和感想。个人感想可能有点多，可以直接跳到最后面看总结。

评价

由于这次命题组人数较多，且有龙神等出题经验丰富的前辈，整体试题质量极高。从题型覆盖看，模拟、签到（排序）、dp、博弈、字符串、图论、计算几何、构造……应有尽有；从难度分布来看，正赛6题快银，8题快金，冠军队更是以唯一10题队的身份稳稳占据榜首，题目区分度十分明显。具体到每道题上，不少题目出得十分精彩，其中最令人印象深刻的是网络赛G题构造，讨论完普遍情况，特判完所有特殊情况后，一发畅快淋漓的AC令人意犹未尽。

但是，题目的质量仍有提升空间。从题面上看，亮皇出的热身赛J题中文语法混乱、逻辑不清，参赛者不得不凭借自己的脑补能力把题意理解清楚。正赛最后一题M题对于d的解释不够清楚。正赛又是网络流，又是高斯消元，又是后缀自动机，需要使用模板的地方略多。

服务质量仅讨论中关村正赛。打印服务一开始不能正常工作，且奇慢无比，严重阻塞了三线程的运行。编译环境恶劣，只有不带c++11的devc稍微好用，codeblocks一开始没编译器，后来编译器不能在32位系统上运行。比赛完回到良乡后，滚榜都快结束了，冷餐就剩了一点“给中关村选手准备的食物”。好的地方不是没有，志愿者和裁判组倒是十分积极努力地在提升选手的参赛体验。虽然很多问题是客观问题，再怎么样也不能改变，但该喷还是得喷。

网络选拔赛

我一直很想再参加一次团队算法竞赛，但比赛报名前夕才发现没队友。幸好喵神把我拉进了她们队里，三个退役选手组了个队。现在的我，回想起那个因找到队伍而欣喜的下午，绝对想不到之后我竟然会成为一个工具人。报名开始后，喵神不肯做队长，要我去报名时，我就感到不对劲。之后，各种繁琐的流程接踵而至。又是填报名信息，又是接邮件记密码，之后还要领衣服，比赛完了还要填获奖信息。热身赛我一个人去检查环境，比赛完我一个人回去领奖。虽然如此，比赛的时候大家还是在愉快地讨论，参赛体验还是不错的。

网络赛的时候，为了创造更好的参赛体验，不让学弟们感到太多的压力，我们选择不发挥全力，在实力上有所保留（实际上是，队友不在校内，编程环境不太好，代码只能让我提交）。最终我们过了9题，既向大家展现了实力，又把宝贵的前几名让给了学弟们，可谓是用心良苦。

比赛开始前一小时，我去cf随便写了几题。当我熟练地在5秒内敲完for(int i =0; i < n; i++)时，我感到一切都回来了。手速、算法知识、编程技巧，我完完全全地找回了它们。我自信地迎接着网络赛的到来。

比赛一开始，一股熟悉的想抢一血的冲动涌上心头。我本能地点开I题，浏览题目之后，发现事情不对，立马换题。抱着想抢一血的功利心，我不想花费一分一秒在看榜上。很快，我准备写F题。

F题很明显是个排序签到题，写惯了正经代码的我，从这样一道算法少、流程繁琐的题开写是十分妥当的。可惜意识尚在，熟练度尽失。我仔仔细细地读了遍题，工工整整地定义了类和两个排序函数，main函数里用简短优美的代码完成了整个算法流程。我颤颤巍巍地把代码上传，确认再三后才点击了提交。焦躁地按了几下F5刷新后，屏幕上出现了一行绿色的CORRECT。看到代码通过后，我体会到久违而熟悉的成就感。此时比赛已过去21分钟，不仅F题一血没了，其他水题也被陆陆续续地通过了。但我的斗志丝毫没有衰退，带着首次过题的成就感BUFF，心态良好地开始跟榜做题。

我看L题过题人数最多，就开始写L题。L题是个超级签到题，用第一个月学C语言的知识就能轻松做出。

A题一看就是个“模拟”题。久经战阵的我，发现了题目和数据的不一致性，并且知道样例才是正确的。我用一个比较繁琐的方法才把图片导入进代码：先读入样例文件，把空格和符号转化成01串，再把01串粘贴进代码。我及其稳健地一次通过A题。

B题过的人也不少，但乍看之下不是什么简单的题：和普通背包问题类似，你要保证不超出背包容量的前提下选择物品，获得最大价值。只是每次选择的物品不大于上次物品的重量。但仔细观察数据范围可以发现，物品数、重量全都不超过100。我一边写代码，一边以极强的基本功在心里推出转移函数，顺利过了B题。

J题全是用中文写的，但读起来和天书一样，在跟榜做题的原则下，我不得不开了这题。题目给了一行数，每个数字表示一个物品；又给了一个每种物品的数量要求。你要从这行数中选一个连续区间，使得选的物品满足物品数量要求，求最小区间长。数的规模是1e6。我看答案是单调的，先考虑了二分答案，再想到用尺取判断答案。后来发现不用二分直接尺取就可以过了。不过出题人比较善良，加了二分也没有t。J题也被轻松通过。

这个时候，我的队友加入了战场。湛学姐读完了D题E题，以极强的思考能力迅速理论AC了这两道题。于是，我选择去实现E题。

E题是计算几何题，给出平面上若干点，保证不存在三点共线。要求找到一对点，使得过这两点的直线能恰好平分剩余的点，或者说明这样的点对不存在。由于要求正好平分，奇数个点的情况就之前pass了。对于偶数个点，以某个点为原点进行极角排序，找到排序后最中间的点。原点和中间点就是答案。极角排序的原点可以选择最左下角的点，但比赛的时候我先找了下凸包，再选了凸包上一点。由于我对自己的板子很不熟悉，WA了两发。但是，此刻我知道我不能再浪了。为了契合我们的队名，我发出了“从现在开始，不会再WA”的宣言。

喵神负责写D题，似乎看出了只需计算素因子贡献就行了，一次性顺利过题。

湛学姐又读完了C题，快速给出了做法。我用两分钟时间看完并理解了转述的题意和解法，用二十分钟稳健地AC这题。题目给了一个元素不重复的数组，在保持元素不重复的前提下，可以进行一种操作，操作每次可以把数组里的一个数转换成另一个数。现在给出数组的初始状态和操作若干次之后的状态，问最早需要操作几次及具体方案。一个数在被转换之前，需要保证转换之后的数不在当前的数组中出现。因此，如果数组初始状态和最终状态中不同位置出现相同数字，可以对把这两个位置连一条有向边，表示对两个位置操作的先后性。最终得到的图如果没有环，可以直接按着有向边的顺序进行操作；如果出现环，就把某个位置先修改成一个tmp值，把环拆掉，再进行操作。

剩下的题目中最有希望的是G题。G题过题人数较多，且是构造题，想到就能过。题目要求用两种形状的积木拼出一个给定长宽的矩形，问方案是否存在，若存在要输出具体方案。积木的形状是

1
2

***      **
 *       *

经讨论，2X3，2X5~2Xn都能构造出来。4X4特判。3X5无法构造。仅需讨论5X5能否构造即可构造出剩余比较大的矩形。湛学姐以极强的洞察力和丰富的想象力，构造出了5X5的方案。我负责把代码写出来。由于这题要求输出方案，代码极其繁琐。我凭借着多年积累的结构化编程经验，把每个操作模块化实现，先后实现了声明新积木、画积木、转积木、反转矩形、画矩形等函数。整个程序变量名、函数名清楚易懂，代码逻辑清晰，堪称代码中的典范，入选世界10大优美ACM代码也不令人奇怪。最终2发AC，第一发WA在了2X2上。

后来学姐们发现I题是个原题，以前打多校赛的时候写过，本来准备粘一份代码。但喵神坚持着网络选拔赛过题影响正赛RP的封建迷信，拒绝了这种做法。我也秉承着给学弟们保留信心的做法，没有过题。网络赛就这样结束了。很久没有这么爽快地过题，我感到神清气爽。

正赛

刚才，有个朋友，和我说：“帆神，写个答案吧。”

我说：“怎么回事？”他给我发了一个知乎链接，我一看，噢，原来是佐天，有一个竞赛，叫“连山科技”，算法竞赛。我和两个学姐，退役选手，一个研一，一个研二，参加了比赛。

比赛前，我说：“加入你们，让你们丢了最佳女队，不好意思。”塔们说：“没事，你可以carry。”我说：“我carry不了，但我们可以抢一血。按传统的比赛情况来看呢，我是抢一血的。去年校赛，前年新生赛，我的队伍都拿到了全场一血，啊。（笑）”

塔们也很服气，说可以试试。比赛一开始，喵神啪地一下就撕开试题册，很快啊。然后就是，一个找题，一个写题，一个交题。代码提交了，手放到提交键上没有点。这时间，按照传统的比赛情况来看，如果这个键点下去，一血就是我们队的了。塔知道这个代码一定能过，但塔又去检查了一遍代码，塔知道这个代码能提交通过的，啊。但提交一看呢，噢，一血没了，额，大概几分钟前没了，老年人，手速慢了。

但没关系啊。我手里还有题的啊。我老规矩，开局看了I题。发现不对，又去看了G题。G题很明显是个签到题，sg函数，搞个二维的，随便写一写就过了啊。我啪、啪，敲了几下键盘，额这个题目就写好了，很快啊。交上去一看，RE！

喵神说，塔有H题可以写，要我去打印代码。我说：“可以。”我大意了啊，不知道，这个打印机呢，坏了。这个三线程工作，给阻塞了。但我也不傻啊，又去看L题，说：”题目简单，我可以写。“

当时急着过题，我又大意了啊。交了L题，WA了。我一改代码，咋样例又不对呢。湛学姐和我讲了遍题意，噢，原来是题读错了。我说：”对不起对不起，我题读错了，我是乱写的。“喵神又把我踢下去了。

湛学姐急了，塔一直在读题，额，大概有4，5道题，都已经理论AC了。塔说：”I题是个签到题。”塔和我讲了讲题意，一个排序，再随便搞一搞，就好了。噢，原来我上当了。我说：“你来写I题。”总算啊，81分钟，过了第二道，签到题。

之后，我又说：“L题我可以改。”写完了，感觉很正确，交上去，又WA了。喵神看了看，发现有一个排序，有一个小问题，写反了。塔指点了一下，就稍微指点了一下啊，我改完，题就过了。两个小时，我才写了一题。为了表示谦让，我是全队最后一个过题的人啊。

这时间，那个打印机啊，搞好了。G题代码，给送了过来。我一看，噢，一个数组下标，本来是a-b，给写成了b-a。数组下标成了负数，这不RE才奇怪呢。一改完，题就过了。本来开场20分钟就过了，现在两小时20分钟才过，整整120分钟，啊。我们呢，刻意的呢，想多让学弟们，让塔们一些罚时。

喵神又去写H题去了。湛学姐又理论AC了一题，就是那个J题，枚举一下，套个高斯消元就过了啊。我用我的人脑评测机啊，测了测塔的算法，感觉确实没问题。D题、M题，早就会写了，我说：“你来写。”塔说：“我不写。这是码农题。传统码农题是讲代码量的，一题二百行。”我说：”那我来写。”这时候，我们等于呢，已经过了7题。喵神H一过，那就算过了8题了，啊。

喵神呢，交了两发H，然后发现题读错了。我说：”停停。没关系啊，我也读错了题。但现在，要以大局为重，让我写D和M。“我上去，一个手起键落，以迅雷不及掩耳之势，花了一个小时，才把，就把D和M写完了啊。我练过三、四年算法竞赛啊，训练有素。三小时的时间里，我们AC了6题。

喵神说H题过不了。我问，怎么回事，算法问题还是写法问题。塔说，算法和湛学姐讨论了，没有问题。一个DAG，点有点权，边有次数限制。从1点到n点，可以走无限趟，求最大价值。塔说，贪心，每趟取最大价值，不用写网络流。二十分钟就有人过了题啊。我一下没找出反例，说打印代码看看。

这时候啊，一个裁判，龙神，走了过来。他说，出题人，牟神，让喵神去写字符串。挑衅我们啊。我们哪有不理他的道理啊。既然这H题算法没问题，我说那我来看H题代码，你们去写E题字符串吧。塔们说，可以。

我拿过H题代码一看，没毛病啊。正着看，反着看，代码都倒背如流了，也没发现什么大问题啊。我用人脑编译器，诶，编译了一下，二进制代码都生成了，跑了样例，流程没问题，结果没问题。我啥也干不了了。

只听那边啊，谈论得，风生水起，什么后缀自动机、fail边，后来又是multiset，很复杂啊。我后缀自动机，都全忘，不能说全忘，都策略性地存储到了大脑深处了啊。没办法，很烦，帮不上忙。

最后半小时，没事干，我又看起了H题。突然，我想出了一组反例，嚯，算法假了。网络流带回边的，这样贪心表示不了操作撤销啊。最后也来不及想了，就也没过题了。

赛后一看，E题做法没错，F题也是会写，但没写。不算H题，理论上我们过了8题。四舍五入，其实就是一等奖队伍啊。最后，发现我们只有三等奖。其实，减去G题打印机导致的罚时，还是有二等奖的。但是出于对后辈的考虑啊，刻意没拿这个二等奖。

后来去问出题人，塔们说I题本来是A题，怕大家不敢看A和A调换了一下。塔们说是乱换的，塔们可不是乱换的啊。仔细反思，这次比赛，没有抢到更多的钱，原因有三点。一，签到题I题被替换了；二，打印机坏了；三，出题人挑衅参赛选手。这些出题人、裁判员，不讲武德，来，骗，来，偷袭，我们三个，加起来六十多岁的，老选手。这好么？这不好。我劝，这些出题人，耗子尾汁，好好反思，以后不要在题目顺序搞聪明，小聪明啊。

比赛结果，重要吗？不重要。重要的是你学会了什么，你得到了什么。比赛，要以和为贵，要讲娱乐，要讲友谊，不要搞，内卷化。谢谢朋友们！

总结

这次比赛，貌似是我生涯中结果最差的一次比赛。但是，这是非常有趣，令人难忘的一次比赛。不去追求名次，而是享受比赛本身，享受交流、合作、共同自闭，这是之前我从来没有做到的。很荣幸能参加这次比赛，能最后一次体会到算法竞赛合作的乐趣。

赛后仔细看了看榜，排名前列的好几个队都是大一队。正如其他人所说的，后生可畏，北理进Final有望了。但除此之外，我还有一些其他的期待：北理ACM集训队的寒假集训和暑假集训做的非常棒，通过大一一年的学习，有志于竞赛的同学能学到很多东西。但是，之后就没有什么正式的培养学生的流程了，很多情况下只能靠学生的自律来进行训练。ACM固然是强调个人能力的竞赛，个人能力是取得好成绩的前提条件。但是，个人的某些竞赛经验、思考方式是可以传承的，也有许多有潜力却没经验的人需要更好的指导才能成长。祝愿现役选手、未来即将加入集训队的同学们取得好的成绩。也希望你们在保证了自己的比赛成绩后，能把自己收获的东西传承下去，让北理的ACM水平一直提升。

最后打个广告，欢迎关注我的博客。我即将在一个月后对我的ACM经历进行回忆和整理，会发到博客和知乎。希望大家保持关注。

我对这篇文章的评论

文章以幽默的语气，生动形象地描写了老年选手在比赛时候的手足无措，同时其中透露出的欢快之情体现了选手享受比赛本身的放松心态，旨在让读者以一种全新的视角来看待算法竞赛。

我已经半年多没有认真写博客，没有静静地分析、思考一个问题了。最近，几个“项目”（有明确结束条件的事情）已经结束， 我可以抽出一些时间，来反思一下生活中的事情。

过去这半年，我的整体表现和之前一样：没有产生什么突出的成果，也说不上毫无作为。一切都还算顺利地进行着。未来，准备出国的材料，再申请一所符合我水平的学校，一切也估计会正常进行下去。这半年我也有许多做的不好的地方，或许以后时间多了我会抽时间来专门反思一下。

回到今天的主题。大四开学后，我周围的学习（努力）氛围发生了翻天覆地的变化。步入大学的最后一年后，所有同学都忙了起来，为未来拼搏着。我的室友要考研，他们都早出晚归，去教室自习；隔壁宿舍有找工作的同学，三天两头出去面试；和我一样出国的同学，为推荐信等材料烦恼焦虑着。我虽然一开始就目标十分明确，且不会因周围的环境而改变自己的行动，但我依然被周围的环境震撼了：命运的分岔口就在前方，所有人都很忙啊！

大学本科有一个共识：大四的成绩是没有用的。无论是保送研究生，还是出国，都只计算前三年的成绩。对于还有着其他目标要达成的同学来说，大四的课程就是一个累赘。我自然也不例外。我深刻地感受到，大四的课程严重占用了我准备出国的时间，尤其我们大四的第一门课还是一个要三周完成的大项目。

这个时候，我产生了一种看起来很矛盾的想法：如果说准备出国，或者考研、找工作等事情是我们的主要目标的话，那么认真花时间学习大四的课程，不就是在浪费时间吗？这和平时打游戏，不去认真上课，不是本质上相同吗？

这话乍看之下确实很有道理。当然，这句话默认了一个前提：大四的课对你未来的目标几乎毫无帮助。有过上大学经历的人大概都会同意这句话，因为绝大多数的大学课程，在它的分数失去了功利的作用后，就变得毫无价值了。和自己的人生目标相比，上课竟然变成了和玩游戏本质一样的浪费时间的事情，真是十分讽刺。

我虽然产生了这种想法，但我隐隐感觉有一些不对劲，我本能地认为这种想法是错误的。我把这种想法概括成了一个问题：做无益目标的事情是在浪费时间吗？经过一定时间的思考，我认为这种说法完全是错误的。

人们习惯于单一目标

从小学开始，我们就被灌输了一个概念：学习成绩是最重要的。在高考之前，我们所做的一切事情就是取得好的学习成绩，考上一所好大学。上大学后，大家的目标会稍有变化。有些人专心刷绩点，争取保研名额；有些人一边保持着绩点，一边想办法接触国外的教授，为出国准备优秀的材料。再过一段时间后，有些人会开始准备复习考研的各个科目，还有些人会看面经，准备工作面试。大部分人，哪怕是本身对人生不够有主见的人，都能在环境的影响下找到一个短期内值得奋斗的目标。人们基本上都在为单一目标奋斗着。

有些观点说，人们习惯于单一目标，是我们从小的应试教育造成的。但我看未必，因为人本身就习惯于单一目标。竞技项目中，无论是传统的体育竞技，还是智力竞技，都只要完成在本项目上提升自己，战胜对手这一目标即可。在面对单一目标的时候，我们能很明确地知道哪些事情是有益的，哪些事情是无益的。s在刷绩点的时候，玩游戏就是无意义的；在当职业电竞选手时，不玩游戏反而是不对的。可以说，追求单一目标本身就是简单的。只要有一定来自内心或外界的动力，明确了每件事是否有益，全力去做有益的事情即可。人们选择去实现单一目标，本质上是选择了一种简单的做事方式。

另一方面，单一目标意味着评价标准唯一。在单一目标上取得优秀成果的人，往往能收获到很多世俗上的利益，这鼓励着其他人也追求着单一目标的优秀。高考分数高，意味着你能上一个好大学，“改变命运”；绩点高，推荐信强，有学术成果，你能去世界一流大学研究，“成为学术大牛，改变世界”；在竞技项目上成为顶尖选手，你能收获荣誉、收获粉丝的崇拜、收获名利。

可以说，人们习惯于单一目标，人们往往为单一目标而奋斗。确实，许多人因为单一目标的成功而成了受人羡慕的人，这鼓励着其他人继续为单一目标而奋斗。

更多目标与更远的目标

其实说了这么久，我一直没有解释单目标是什么。或者说，从对立面来看，什么不是单目标的态度。事实上，我自己也习惯了单目标的思维，单目标成为了一种普遍、唯一存在的事情。解释什么是单目标，其实意味着思考单目标的对立面是什么，这本身就是一件很有挑战的事情。

从单目标，很容易想到多目标。除了我们当前正在做的事情以外，还有许多重要的事情。沉浸于心流之中（玩游戏）、与他人进行一次有趣的谈话（吹牛）、欣赏作品（看动画），这些事情都能令我们很开心，却又常常与我们的当前目标无关。你能说这些事不重要吗？我们当前主要目标之外的其他一些事情，同样很重要。

此外，我们眼中无比重要的单一目标，往往只不过是我们人生中的一个岔路口。回头望去，很多当时我们觉得天都要塌的要紧的事，其实根本不重要；很多我们当时的无心之举，往往深刻了影响了我们的一生。小时候，一不小心丢了东西，一不小心考砸了，可能觉得自己要被骂死了，事后之后成为有趣的谈资；以前无心接触的爱好，可能一直推动着我们前进，最后成为终身的职业。那么未来何尝不是如此呢？未来的目标与现在的目标有多少关系呢？你保研成功了，又意味着什么呢？你进入了世界一流学校，又意味着什么呢？你选择了自己心仪的专业，或者选择了天坑专业，又意味着什么呢？你高考复读了一年，或本科毕业gap一年，又意味着什么呢？你成绩不好，无奈选择考研又意味着什么呢？你的一时的成功或者一时的失败，真的就是一辈子的成功和一辈子的失败吗？现在的事情，对以后的工作、升职、赚钱、成家、糊口、育儿，有多大的影响呢？即使你赚了大钱，有着无数可以挥霍的财产，你接下来又该做些什么呢？未来有无限的可能，更有无数要考虑的目标。现在的单一目标，很难说对未来的目标有多少影响，甚至大部分情况下毫无影响。

再进一步思考，上文中提到的更多目标，比如在娱乐中收获的快乐，这些重要的事情该如何概括呢？我认为，这些事情其实就是人生意义的本质。人生是为了什么呢？不就是为了获得满足感，享受开心的时刻。能够直接通过生活中的一些小事，收获快乐，实现人生的意义，何乐而不为呢？我认为单一目标外的更多目标，是能直接实现的人生终极目标。而上文提到的更远的目标，实际上也有一个尽头。工作、赚钱，最终可能是实现自我的价值，或者是实现自我对社会的价值。所谓更远的目标，实际上是比较困难，需要间接实现的人生终极目标。这两者本质上都是我们要实现的终极目标，只是表现的形式、难易不同。

简单的满足感、自我价值的实现，这两者的本质相同，性质却不太一样，得分开讨论。做无益单一目标的事，显然不是在浪费时间。除了单一目标外，我们要考虑如何实现这两种目标。当然，这两方面的话题拓展下去又可以谈出更多东西，我今天只稍微谈一些比较浅显的看法。

实现简单的满足

实际上，大家都会自然地追求这种简单的满足。学累了玩一盘游戏，周末和他人聚个会。不过，在各种错误的宣传下，有些人会认为这些放松是不对的。因此，在实现简单的满足这件事上，主要是要让自己摆正态度，让自己明白放松是非常正确的，不应有任何负罪感。在有了正确的认识后，再去考虑发现生活中能令自己开心的事情，多去享受那些快乐的瞬间。

这里跑一点题，稍微谈一下游戏的事情。我之前把大四时花时间学习课程，和平时花时间打游戏对比，其实已经表明了我不认为做无益目标的事是没意义的——我向来是支持玩游戏的。玩正确的游戏本身能带来很多精神上的享受，这本来是一件中性的事情。有些沉迷打游戏的人，只是为了逃避生活中的事情，选择了一件能快速大量获得享受的事情而已。能在合适的时候里玩合适的游戏，一定是有益于生活的。就获得满足的角度上来看，玩游戏和出去运动、和别人聚会等事情没有本质的区别。一定要对放松的事情有正确的认识。

能获取简单满足的事情可就多了，每类事都可以都可以花很多文字来分析。但稍微分一下类的话，可以分成直接的感官刺激，比如吃美食，去游乐园；个人精神的享受，比如玩游戏、看视频；社交的享受，比如聚会、聊天。

准备更远的目标

实现眼前的单一目标，很多时候是必须的事情。但是，我们不能忘记未来有更多的目标，不能忽视现在一些对未来有益的事情。有些做法看似不是当前目标的最优解，甚至对当前目标的完成有负面影响，但对我们的长远发展有利。比如准备语言考试，去报只学解题技巧，和自己稳扎稳打地准备。虽然后者效率更低，但显然更能提升自身的语言水平。尽量追求全局的最大价值，就是我最喜欢讲的“大局观”。显然，人不是机器，生活也不是一个可以用公式表达出来的有最优值的函数。我们永远做不到最优，却可以找到一些更优的原则。

提升自我对世界的认识，这在任何情况下都是最重要的，因为自我对世界的认识决定了你做一切事的方法和态度。自我对世界的认识就是如何看待自己及自己与周围事物的关系，比如：我在这个世界上的地位是怎么样的？我想成为怎样的人？我该怎么样提升自己？我这篇文章所说的内容也包含在内：如何看待当前最优目标与其他事情的关系。在提升对世界的认识上，一个非常有用的经验是：越是去思考，并去改变自己的看法，越能对世界有更正确的认识——所谓更正确，指在做事的时候更加顺利，毕竟对世界的规律了解得越多，越能利用这些规律。

提升自己的核心竞争力。这点要和学生时代唯分数论的观点比较起来看。分数大致上能反映一个人的综合能力，却无法反映一个人的技能水平。但在社会上，想要活下去，或者更好的活下去，必须得有比别人更突出的地方。无论当前的主要目标是什么，都不要忘记自己的优势是什么，如何提升自己优势，让自己的优势别人发掘，或者主动利用优势创造价值。

最后再重新提一次，由于我人生经验尚浅，很多内容了解的不够多，在人生其他目标的了解不足，无法展开来讲。其实本篇文章主要是因为我发现了一种普遍存在的“学生思维”，我自己也没能脱离这种思维后，想专门针对大四面对主要目标的矛盾时应该怎么做写一篇议论性的文章。

大学本科的学习即将结束，我感觉我将面对更多的事情，经历更多的挑战与机会。不论如何，我认为自己在某些方面非常强。在反复确认了自己认为重要的事情是什么后，我有信心去实现我看重的人生目标。

和上一篇博文一样，这篇博文也是一个项目回顾与总结。

这个项目是我NLP的第二个大作业。在这个大作业中，老师要求做一个能完成某个功能（而不是做句法分析等预处理工作）的NLP程序。选题时可以从老师给定的题目中选，也可以自己找一个题目。当时我时间并不是很充足（感觉这学期我就没有在时间充裕的情况下写过项目），准备尽快把项目做完，因此决定从老师给的题目里挑一个来实现。一开始我挑了垃圾评论检测，因为老师明确指出，只要实现一篇论文的内容就行了。我去搜了那篇论文，却发现论文的数据集不是公开的，想获取数据集需要发邮件去申请，十分麻烦。我只好在剩下的题目中再找一个题目出来。排除掉了一些看上去不是那么实用的题目后，我选择了”汉语自动纠错系统“这个题目。在论文中，这个问题被称作”中文拼写检查(Chinese Spelling Check)”。

我很快搜索到了一篇非常好的综述博客[4]。根据博客中的介绍，我去读了几篇论文。比较幸运的是，这些论文中的算法对我来说非常简单，我很快就理解了算法的细节。比较了各种方法的实现难度并参考了综述博客对各种方法的比较结果后，我选择了[3]中的方法。一般来说，拼写检查问题可以分成两个部分：先对句子进行分词，再根据分词结果进行拼写检查。[3]的方法可以同时完成这个两个步骤，处理起来比较方便。

我很快实现了分词算法，并且按照评估标准评价了我的程序的表现。我本以为这个项目就这样结束了，但我对我程序极差的表现产生了一丝怀疑。我更仔细地阅读了一下论文，发现论文除了提出分词算法外，还提出了一种利用数据统计文字错误概率的方法。文章利用了谷歌1T的数据库来训练。我难以获取这个数据库，哪怕获取了电脑也存不下，哪怕存得下训练时间我也接受不了。考虑到这是大作业，老师不会只按结果给分，而更看重程序的原理、工作量。我于是决定用其他数据来代替论文中的1T数据，用论文中同样的方法来统计文字出错概率。

找数据又花费了我很多工夫。我需要一个包含文字错误的语料，标注可有可无。我找来找去，总算在Github上一个比较出名的中文语料库中找到了一个台湾论坛聊天语料。虽然数据量不够，但勉强可以在这个语料库上执行文章中的训练算法了。

在统计文字出错概率之前，需要先用一个分词语料库训练出一个语言模型。我用的是比较常用的北大人民日报语料。但是，所有的中文拼写检查都是基于繁体字的，这就出现了一个问题：语言模型仅用了简体语料，无法处理繁体字。我决定把人民日报语料转换成繁体。一开始我用word转换，一按简繁转换按钮程序就卡死了。我又去网上随便下了一个简繁转换程序。这个程序的转换速度倒是很快，但我发现转换结果有一些问题：一个简体字可能对应多个繁体字，比如简体”后“字有”(皇)后“，”後(面)“这两个对应的繁体字，而转换程序只能进行一对一的转换。最后我在Github上找了一个运用了NLP技术的简繁体转换程序，总算得到了一个能用的繁体语料库了。

至此，我总算解决了所有的问题，准备好了编程所需的所有资源。剩下的编程、写实验报告的工作就没什么值得讲的了。

这次项目对我来说意义很大。倒不是说我在这个项目中学到了多少NLP知识，或者说留下了一段比较有趣的工作过程。我在这次项目中，最大的收获是初步掌握了检索文献并了解一个领域前沿知识的能力。我第一次了解了什么是综述，虽然这篇综述放在博客上，并不是按照标准的论文格式写的。我第一次读懂论文并实现了论文的算法。我之前一直觉得论文都很高深，涉及的方法非常复杂。多亏这几篇论文算法相对来说比较简单，给了我读论文的自信。在这个项目之后，我还碰到了很多需要自主学习领域前沿知识的项目。得益于这次项目的经验，我能够快速搜索到一篇好的综述文章并开展学习，高效率地完成对相关领域前沿知识的了解。

以下项目介绍绝大多数内容摘自实验报告。

中文拼写检查器（基于图网格，C++实现）

Github链接

https://github.com/SingleZombie/Simple-Chinese-Spelling-Checker

任务定义

1. 找出一个句子中出错字的位置。

2. 把出错的字修改成正确的字。

实现思路

实现思路和参考论文[3]大致相同。

对一个句子同时进行分词和纠错。假设每个字都可能出错。列出每个字的混淆字，这样对于整个句子来说，就形成了一个图格。分词和纠错等于在图格上找一条权值最大的路径。在这个图格中，每个字都看成一个节点。如果相邻的几个字可能构成一个词（无论这些字是否来自混淆集），就把这个词当成一个节点。两个节点的之间的权值就是转移的概率。

节点间的概率来自两个部分，一部分是语言模型概率（判断分词是否正确），一部分是字会出错的概率（判断修改的是否正确）。

对于语言模型，使用大作业一的二元语言模型，即基于人民日报语料库构建的模型。每次可以查询前后两个词一起出现的概率。

对于字会出错的概率，使用互联网文本来训练模型。对文本的每句话进行分词（分词采用大作业一的算法），之后考虑任意连续的两个或三个词，试图用混淆集的字替换其中的一个字（混淆集来自汉语的同音字、近音字），看看这两个或三个词能否合并成一个词。如果能，则把改之前和改之后的字符串作为一个pair储存。这些pair表示候选错误串。

统计所有pair的情况。把每个pair的出错字符串的前面一个词看成一个向量（向量的维度是上一个字符串，向量该维度的值是上一个字符串出现次数）。同时，用同样方法统计pair的正确字符串的前一个向量，这个向量可以从语言模型中获得。对两个向量求cos值，该值可以表示两个向量的相似程度。若这个cos值大于一个人工设置的阈值，则认为错误串和正确串上文相同，这个串确实出错了。之后，把串中出错的字找到，统计一个字出错变成另一个字的个数。

有了一个字出错成另一个字的个数，就可以统计一个字出错成另一个字的概率。一个字符串出错变成另一个字符串的概率，就是每个字出错成对应字概率的乘积。

节点的转移权值由以上两部分概率相乘得到。

由于图格构成一个DAG，且已经拓扑排序好，可以用DP找最大权值的路。寻找每一个可能的词以构成节点时，在词典的字典树上查找以减少时间开销。找到最大权值的路后倒序得到每一个节点，出错纠错结果。

程序设计与实现

数据预处理

由于测试集是繁体，词典用的分词语料、汉语词典被转换成了繁体。

混淆集文本预处理模块如下所示：

由于原始数据是json型的，数据先被提取出来，保存到txt文件里。（这一步程序里没有，只保留了最后的txt文件）

之后main函数调用outputConfusionPair进行候选串的获取。选取候选串的主要算法函数存在ConfusionTrainer.cpp文件中。其算法先对句子进行分词，再每次找相邻的两个、三个词，尝试从完整的混淆集（来自于汉语的同音、近音字）替换每个字，看这两个、三个词能否构成一个词典里的词。其具体算法和后面的替换算法类似，都是在词典的字典树上查找。最终这一步会输出三元组（上一个词，可能出错的词，正确的词）。

之后main函数调用calPotentialConfusionPair，LanguageModel统计上一步得到的三元组，根据出现次数计算输出出混淆对概率信息，这个信息文件里包含每一个混淆对的cos值，混淆对的出现次数。cos值是把对可能错误的词的上一个词的出现次数乘上语言模型中正确的词也是这个上一个词的出现次数再相加，最后除以正确的词上一个词的总个数，除以可能错误词上一个词的总个数。和向量求cos值方法相同。

最后confusionSet根据cos值和混淆对出现次数筛选掉一些不合法的混淆对（实现时cos值>=0.2，出现次数>=2），之后对合法的混淆对统计是哪个字出错了，最后得到一个字错误成另一个字的次数。根据一个字错成另一个字的个数，可以得到一个字错成另一个字的概率，具体公式是：

ch是正确字符，ch'是某一个被混淆的字符。S(ch)指字符ch的混淆集。由于样本数据较小，这里用了加1的数据平滑。

由于最后一步预处理很快，这一步的结果没有写进文件，在程序执行的时候才会处理。

程序执行

最终可执行程序的结构如下：

词典读入分词语料库，得到二元语法模型，同时所有词构成一个字典树。混淆集读入每个字所有可能的混淆字，以及每个混淆字的概率。语言模型综合二者的信息。算法模块提供了所有核心算法。主程序对整个程序的过程进行控制。

程序开始运行后，会先读入分词语料库，以及一个成语库，二者会插入进语言模型的词典。词典在内部建一棵字典树以维护所有词语，并统计相邻两个词出现概率。之后主程序会读入一个有概率的混淆集。最后调用Language Mode再调用NLPAlgorithm文件中的算法对测试集进行纠错并评价结果。

CSCAlgorithm.cpp包含本程序主要的纠错算法。主要函数的算法流程图如下：

分词函数先定义了节点二维数组vertice[i][j],从字符串的每个位置开始进行DFS。DFS在递归过程中，会尝试替换每一个字符，并且在词典的字典树上移动。如果字典树上没这条路径，即当前节点号crtTrieIndex==0，就可以对DFS进行剪枝。通过DFS可以生成图网格中所有可能的词节点，并且得到每一节点的最大概率。通过最后一个节点可以反向遍历出结果字符串。

具体节点概率（准确来说是权值）计算公式如下：

word指当前词，preword是上一词。$P_{LM}$是语言模型的概率，直接调用二元语法模型的函数就可以计算。$P_{err}$为出错概率，其公式为：

公式就是把出错词中每一个出错字的出错概率累乘。其中：

根据这个字是否出错，这个概率分两部分来计算。其中perr是一个超参数，表示某个字出错的概率。如果这个字确实是错的字，就去之前的错误模型里寻找概率。程序中这个值是CHARACTER_ERROR_P = 0.0003

程序结果

使用SIGHAN Bake-off 2013作为测试集。其中subtask1用于错误查找，subtask2用于错误纠正。根据测试集论文的描述，评价标准有以下几项：

错误查找：

• FAR（错误识别率）：没有笔误却被识别为有笔误的句子数/没有笔误的句子总数

• DA（识别精准率）：正确识别是否有笔误的句子数（不管有没有笔误）/句子总数

• DP（识别准确率）：识别有笔误的句子中正确的个数/识别有笔误的句子总数

• DR（识别找回率）：识别有笔误的句子中正确的个数/有笔误的句子总数

• DF1（识别F1值）：2 * DP * DR/ (DP + DR)

• ELA（错误位置精准率）：位置识别正确的句子（不管有没有笔误）/句子总数

• ELP（错误位置准确率）：正确识别出笔误所在位置的句子/识别有笔误的句子总数

• ELR（错误位置召回率）：正确识别出笔误所在位置的句子/有笔误的句子总数

• ELF1（错误位置准确率）：2 * ELP * ELR / (ELP+ELR)

错误纠正：

• LA位置精确率：识别出笔误位置的句子／总的句子

• CA修改精确率：修改正确的句子／句子总数

• CP修改准确率：修改正确的句子／修改过的句子

我的结果：

FAR:16.5714% DA:70.0000% DP:50.0000% DR:38.6667% DF1:43.6090%

ELA:63.7000% ELP:22.8448% ELR:17.6667% ELF1:19.9248%

LA:16.3000% CA:15.2000% CP:37.1638%

使用的公共资源

语言模型

北大人民日报语料库

新华成语词典：https://github.com/pwxcoo/chinese-xinhua

混淆集

原始混淆集：SIGHAN2013 ConfusionSet

训练用互联网语料：https://github.com/zake7749/Gossiping-Chinese-Corpus

工具

简体繁体转换程序：https://github.com/hankcs/HanLP

测试集

SIGHAN2013 finalTest

程序实用说明

输入文件的格式必须是Unicode BE。

txt文件描述：

ChatData.txt 混淆集训练用的互联网原始文本

ChatDataConfusionSet.txt 互联网文本中提取的候选混淆对

ConfusionInfo.txt 候选混淆对筛选出的词对cos值和出现次数

FinalTest.txt SIGHAN测试集subtask2

FinalTest_Result.txt 程序跑出来的subtask2结果

FinalTest_Truth.txt subtask2正确答案

FinalTest_SubTask1.txt SIGHAN 测试集 subtask1

FinalTest_SubTask1_result.txt 程序跑出来的subtask1结果

FinalTest_SubTask1_Truth.txt subtask1正确答案

IdiomDictionary.txt 成语词典

SimilarPronunciation.txt SIGHAN原始混淆集

SimilarShape.txt SIGHAN原始混淆集

TrainDataCht.txt 北大分词语料

参考文献

[1]. Shih-Hung Wu, Chao-Lin Liu, and Lung-Hao Lee (2013). Chinese Spelling Check Evaluation at SIGHAN Bake-off 2013. Proceedings of the 7th SIGHAN Workshop on Chinese Language Processing (SIGHAN’13), Nagoya, Japan, 14 October, 2013, pp. 35-42.

[2]. Chao-Lin Liu, Min-Hua Lai, Kan-Wen Tien, Yi-Hsuan Chuang, Shih-Hung Wu, and Chia-Ying Lee. Visually and Phonologically similar characters in incorrect Chinese Words: analyses, Identification, and Applications. ACM Transactions on Asian Language Information Processing, 10(2), 10:1-39.

[3]. Hsieh Y M, Bai M H, Huang S L, et al. Correcting Chinese spelling errors with word lattice decoding[J]. ACM Transactions on Asian and Low-Resource Language Information Processing (TALLIP), 2015, 14(4): 18.

[4]. hqc888688.中文输入纠错任务整理[EB/OL].https://blog.csdn.net/hqc888688/article/details/74858126,2017-07-09.

由于套暑研要准备一个简单的简历，我打算总结一下之前做的一些项目，发博客并上传Github。虽然我能明确地知道，做这些事情对看我简历的人来说毫无影响，但写博客记录自己人生是我自己想做的一件事。

做之前这些项目的时候我都没有去写博客，当时我还没有想好博客该怎么用。以后应该不会出现这些情况了。只要是有一些规模的项目，我都会把从技能学习到编程实现的整个过程发到博客上。

写这个项目是因为我图形学的导师在写一本图形学教程书，其中有一些习题要附上源代码。他让我帮忙实现真实感渲染章节的习题，顺便学习一下这一章的内容。

由于是项目总结，内容会十分简略。

CPU光线追踪C++OpenGL实现

Github地址

https://github.com/SingleZombie/Ray-Tracing-OpenGL

编译项目需要包含一些额外的文件，具体的要求见Github里的readme。

任务定义

实现一个使用光线追踪技术渲染的场景：一个带反射的球放在黑白相间的棋盘格地面上。

知识背景

光线追踪的思想比较简单：以摄像机为端点，向屏幕上每一个像素的处发射一条光线。光线接触到第一个物体后，既会接收物体自身的颜色，还会进行反射和折射，产生更多的光线。这些后续的反射、折射以及物体本身的颜色都会对最开始的这条光线产生贡献。这条光线的强度就能转化成产生光线的像素的颜色值。

从实现的角度来看，光线追踪就是一个递归的过程。为了计算一条光线的强度，还要计算它反射光和折射光的强度。

由于光每次都可以反射和折射，光线与物体的碰撞次数与递归层数成指数级增长，并且客观上光线的反射和折射是无穷无尽的，光线追踪算法需要一些停止递归的规则。递归层数过多、光没碰到物体都能让算法中止。不过即使有了一些限制规则，不经过优化的光线追踪算法运行得依然很慢。

设计

当时我写的伪代码如下：（不过是写完了程序再写的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

// plane是一个平面结构，分量有平面上任意一点、平面法向量、材质
// ball是一个球体结构，分量有中心点、半径、材质
// scene是一个场景类，存储了平面、球等物体，存储了光照信息，可以进行光线追踪计算
// pixelPos表示屏幕上某个像素在世界坐标的位置
// ray是一个光线结构，表示从观察点射向pixelPos的一条光线
// color(i, j)表示屏幕坐标为(i, j)处的颜色
// CreatePlane(p, n)用平面上一点p和法向量n构造平面
// CreateSphere(p, r)用点p和半径r构造球体
// pixelToWorldPos(i, j)计算屏幕(i, j)处像素在世界坐标的位置
// Ray(p, d)用点p和方向向量d构造光线

plane = CreatePlane(vec3(0, 0, 0), vec3(0, 1, 0));
plane.setMaterial(checkMaterial);
ball = CreateSphere(vec3(0, 1, 0), 1);
ball.setMaterial(ballMaterial);
scene.add(plane);
scene.add(ball);

for i = 1:640
	for j = 1:480
		pixelPos = pixelToWorldPos(i, j);
		ray = Ray(viewPos, pixelPos – viewPos);
		color(i, j) = scene.traceRay(ray, 0);
	end
end

// traceRay(ray, recursionTime)接收参数当前光线ray,当前递归次数recursionTime,递归计算并返回光照强度light
// MAX_RECURSION_TIME为常量最大递归次数，递归超过次次数函数会停止执行
// intersectedPoint表示当前光线照射到的第一个物体的照射点
// intersectedEntity表示当前光线照射到的第一个物体
// normal表示照射点处物体的法向量
// material是一个材质结构，表示照射点处物体的材质，分量有着色比例kShade、反射光比例kReflect、折射光比例kRefract。
// light是表示当前点的光照强度
// reflectDir表示光线经照射点反射后光的方向
// refractDir表示光线经照射点折射后光的方向
// getIntersection(ray)是场景scene的函数，用于计算场景中光线与物体的交点以及照射到的物体
// shade(entity, fragPos, ray)接收参数物体、着色点、光线，利用Phong等局部着色模型计算出该点的光强

function traceRay(ray, recursionTime)
	if (recursionTime >= MAX_RECURSION_TIME) then
		return;
	end
	(intersectedPoint, intersectedEntity) = getIntersection(ray)
	if (intersectedEntity == NULL) then
		return;
end
	normal = intersectedEntity.calNormal(intersectedPoint);
	material = intersectedEntity.calMaterial(intersectedPoint);
	light = material.kShade * 
shade(intersectedEntity, intersectedPoint, ray);
	if (material.kReflect > 0) then
reflectDir = reflect(ray.direcion, normal);
		light += material.kReflect * 
traceRay(Ray(intersectedPoint, reflectDir), recursionTime + 1);
	end
	if (material.kRefract > 0) then
		if (intersectedEntity.rayEnterEntity(ray)) then
			refractDir = 
refract(ray.direction, -normal, material.index, airIndex);
else 
			refractDir = 
refract(ray.direction, normal, airIndex, material.index);
end
		light += material.kRefract * 
traceRay(Ray(intersectedPoint, refractDir), recursionTime + 1);
	end
	return light;
end

实现方法

从软件工程的角度来看，根据光线追踪的描述，很快可以得到编程所涉及的对象：射线（光线）、物体、光源、场景。物体、光源属于场景，每帧从视点向所有像素发出光线与物体判断相交，计算颜色时要用到光源、物体参数。再具体来说，光源包含颜色等参数，物体包含自身的几何信息及材质信息。有了类和类间关系，代码结构很容易写出来。

从算法实现的角度来看，只要理解了光线追踪算法，看懂了上面的伪代码，很容易写出对应的代码。

由于光线追踪算法的像素值完全来自射线和物体的交，物体可以以解析式的形式定义。比如球只需要定义一个中心点位置，一个半径。在判断射线和物体的交时，求解一个射线的参数方程即可。

结果

SLICAP图像分割C++实现

代码仓库

https://github.com/SingleZombie/SLICAP-image-segmentation-cpp

需求分析

输入一幅图像，输入图像中每个像素的分类。比如产生以下的效果：

由于我的软件工程天赋过于高超，加上用户、产品经理、程序员都是我自己，因此分析阶段的功能建模部分就略过了。

技能学习

算法原理

见上一篇博客

概要设计

学完算法，准备开始写程序后，我的脑中立刻就浮现了以下的程序结构图：

和以往一样，主函数分成预处理、执行操作、输出处理三个模块。执行操作可以分成生成超像素和利用超像素进行图像分割，在用超像素模块分割模块中会利用到AP聚类算法。

这次程序的两个主要模块非常清晰：用SLIC生成超像素的模块和用AP聚类的模块。两个模块独立性高，且具有先后关系。应该逐模块进行开发，每个模块开发完成后进行单元测试，确认模块工作正常后再进行后续的开发。同时，由于项目时间十分紧张，我还需要采用敏捷开发，不浪费一分一秒在无谓的写文档上。

详细设计

虽然划分模块用的是结构化设计的思想，但我还是喜欢设计类并进行面向对象编程。

超像素生成模块

时间紧张，不画UML图了，直接用文字表达思想，之后直接写代码。

首先要有一个SuperPixels类。该类用于在超像素生成和超像素图像分割模块间传递信息。该类存了一个图像矩阵、一个存储每个像素所述超像素类的数组、一个存储每个超像素信息（平均颜色向量）的数组。外部操作有根据图像矩阵创建新对象。由于算法对数据操作较多，该类可以被看成一个“结构”，标记数组、超像素信息是透明的。超像素信息用SuperPixel结构表示，该结构就是一个五维量（颜色和坐标）加一个像素数。

SuperPixelsGenerator提供生成超像素的算法，与一个SuperPixels关联，被处理模块调用。该类要存储一个图像矩阵，超像素期望的个数superPixelCount, 颜色距离参数colorDisM，最大迭代次数maxIterTime，计算一个期望距离expectedDis。我按算法流程顺序来设计每一个部分。设计时参考了这篇博客。

首先我需要一个RGB和LAB互相转换的函数，供SuperPixelsGenerator调用。这个函数应该单独写在一个模块中。上面那篇博客的作者还写了一篇RGB转LAB的博客。但由于自己实现比较复杂，我打算直接用OpenCV自带的方法转换。

std::vector SuperPixelsGenerator::computeGradient()，计算图像每一点的梯度。

void SuperPixelsGenerator::initSuperPixelsCenter()调用computeGradient()来计算初始的超像素中心。

void SuperPixelsGenerator::updateEachPixel()更新每个像素的标记（类别）。

void SuperPixelsGenerator::updateSuperPixelsCenter()更新超像素中心为平均值。

void SuperPixelsGenerator::enforceConnectivity()对最终的标记进行强制连续性的处理。

超像素聚类模块

我先完成AP算法模块的设计，再完成调用AP算法模块的设计。

AP算法应该可以对任何形式的数据进行。因此，AP算法应该写成一个模板函数。

AP算法接收一个数据间相似二元关系的矩阵，输出一个标记表，表示每一个数据的数据中心是哪个数据。唯一一个可调参数是更新率$\lambda$。我本来想写一个和STL风格类似的模板函数，结果发现我忘记了怎么声明一个参数的指针或迭代器参数。再进一步思考，不管什么类型的数据，都可以用一个整数索引来表示，相似度可以直接存在一个数组里。那么我就不需要使用模板函数了。最终，函数声明写成了这样：

1

std::vector<int> apClustering(const std::vector<int>& similarity, unsigned dataCount,double lambda = 0.5)

再思考一下程序设计细节。对于每对数据，要计算除某点之外的某值的最大值，这个可以通过记录每对点某值的最大值和次大值实现（打ACM做树形dp的时候实现了好多遍了）。另外，每对数据间还需要一个除了某两点以外的累计值，这个直接存一个累计值，用的时候减掉那两个不要的值就可以了。

这个算法直接写在一个函数里没什么问题。要让代码模块性更好的话，可以把$r,a$矩阵的更新分别写一个函数。

超像素聚类算法单独写一个类。该类初始化时接收算法权值参数。调用该类的clustering函数可以对一个超像素集合进行聚类，直接返回AP聚类的标记数组。该函数调用一个函数计算相似度，在调用AP算法返回结果。

1
2
3

SuperPixelClusteringAlgorithm::SuperPixelClusteringAlgorithm(int wl = 3, int wa = 10, int wb = 10);
std::vector<int> SuperPixelClusteringAlgorithm::clustering(const SuperPixel&);
std::vector<int> SuperPixelClusteringAlgorithm::getSimilarity(const SuperPixel&);

程序设计及性能优化

由于时间紧、算法对数据操作量复杂而软件流程复杂性低，本次程序我写得十分“暴力”，很多地方都没有进行模块化、封装。

超像素生成模块

我用四个半小时的实际工作时间完成了看似正确的超像素生成模块。在三种参数下的生成结果如下：（鼠标放到图片上可以看到参数信息）

但是，程序的性能非常差。明明我已经有意识地降低时间和空间使用程度，但程序依然要20多秒才能完成4次迭代的生成算法（生成上面的第三幅图）。

凭借着上次软件工程项目的经验，我使用VS的性能分析工具来改进程序，结果如下：

大部分时间都是画在迭代函数上。令我惊讶的是，几乎所有时间都浪费在了这个计算五维量距离的函数上。

仔细看了一遍网上实现代码和论文中的算法，发现我对算法的理解错了！每次是搜索超像素中心附近的$2S\times2S$个像素，不是对每个像素进行搜索。我立马修改了上一篇博客和代码。

这下算法的结果也正常了，性能也正常了。程序1.7秒可以完成4次迭代、500个超像素、图片大小510X385的超像素生成算法。哪怕不经过任何优化，这个性能也能满足一般的要求。调试的时候不会浪费太多时间，做为作业提交也十分足够。有机会的话，我还是会优化一下代码。

在算法正确的基础上，我又做了3次实验：

目前开发调试外加吹牛的时间共计五个半小时。

超像素聚类模块

这个模块实现起来并不复杂，但我还是浪费了很多时间在调试上。

一开始，我发现我没有正确理解AP算法，没有对相似度矩阵对角线上的值进行特殊处理。我把对角线的值设为平均值后，还是发现聚类算法只会把每一块的数据中心划成自己。由于图片不好调试，我构造了6个点相似度矩阵进行算法调试，其中每三个点有一个很明确的数据中心。算法迟迟得不到正确结果。我浪费了大量时间在代码比对上。突然，我一气之下修改了AP算法的循环停止条件，让它迭代进行100次，结果竟然正常了。我发现在AP算法迭代的过程中，每个点的数据中心可能会固定一段时间，但实际上两个矩阵的值还没有收敛。我把循环停止条件改成了数据中心连续5次迭代都不变才解决AP算法的收敛问题。可是，我把数据从6个点换成了原图像，算法还是进行失败。我又偶然间把计算相似度矩阵对角线的公式去掉了SLICAP论文中提到的比例系数，算法竟然正常工作了。不知道是不是我没有认真看那篇论文，我觉得那篇论文太坑人了，加上比例系数后算法完全工作不了，我还以为是自己写错了。

和设计的一样SuperPixelClusteringAlgorithm类只负责相似度计算和算法调用，AP算法的细节在APClustering中。

程序设计真的没什么可以说的。假设有$N$个数据，迭代$I$次，那么AP算法时间复杂度是$O(IN^2)$，空间复杂度$O(N^2)$。稍微优化一下求最大值和求和的过程就能把看似$O(N^3)$的单次迭代变成$O(N^2)$。

图片显示模块

我打算显示3幅图片：超像素分割结果、超像素聚类结果、图片分割处理结果。

理论上需要一个模块来专门处理输出图片的处理。由于时间不够，我也很懒，只把超像素聚类结果生成函数放到了单独的文件里。超像素分割结果图像放到了超像素类里，图像分割处理结果直接放到了main函数里。这样写程序是非常不好的，我会在之后的版本中修改。

命令行参数模块

理论上，所有的参数都是可以调整的，而且程序可以在不关闭的情况下保存之前的参数设定，循环处理图片。做为一个完整的软件来说，应该提供这些丰富的功能。但我暂时没有写，我写的东西暂时只能算一个程序。

最终结果

（我也忘了当时参数是什么了，但这绝对是程序生成出来的）

感想

我觉得自己很帅。在一天之内不仅实现了图像分割程序的功能，而且凭借着强大的心理抗挫折能力，没有被烦人的BUG击溃，最终站到了胜利的高点。当我回首过去，看着一条条充满荆棘的路，看着我踩的一个个坑，我感到一丝心酸；但当我俯视大地，看着程序能够产生较好的图像分割结果时，我又感到苦尽甘来，心旷神怡。

更新记录

20.2.1

• 上传博客

本文先对论文“SLIC Superpixels Compared to State-of-the-Art Superpixel Methods”做一个论文阅读报告，再稍微介绍一下其他论文，介绍算法原理。下一篇文章会按之前小作业的格式写技能学习、编程过程、代码结构介绍、实验结果分析与感想。

SLIC论文阅读报告

在搜索引擎中可以找到很多分析此论文的中文博客。比如这篇博客分析了代码实现原理。论文中的代码实现网页我怎么都打不开，只能从这篇博客里来获取代码实现的细节。另一篇博客分析了论文代码实现上的性能缺陷。直接看一些中文博客的分析就能对论文的方法理解个大概，再看论文的时候就会比较顺利。

内容梗概

本文对当时的5种超像素方法进行了比较，并提出了一种simple linear iterative clustering (SLIC)(简单线性迭代聚类)的生成超像素的算法。

超像素就是一些像素的集合。超像素的边缘要和图像中物体边缘大致符合。一般获取超像素是其他数字图像处理的预处理工作。图像分割就可以先进行超像素预处理，把每个超像素当成原来算法中的像素来处理，减少数据规模。

算法流程

算法整体上接受一个参数$k$，表示期望的超像素的个数。算法输出$k$个超像素中心以及每个像素属于哪个超像素。

每个像素被看成一个五维量$(l,a,b,x,y)$，前三维是LAB颜色空间信息，后两维是像素位置信息。算法均匀地初始化$k$个超像素中心，并计算超像素间距$S=\sqrt{N/k}$（$N$是像素个数）。之后遍历所有像素中心，找到每个像素周围$2S\times2S$范围内在一种距离度量下”最近“的超像素中心。每个像素”分类“完成后，把一类像素的五维平均值当成新的超像素中心，并以计算本轮分类方式和上一轮的残差。算法不断重复上述过程直到残差收敛至0。

以上只是一个算法的大致描述，算法的具体细节如下：

距离度量方式

如果单纯地把两个像素的距离定义成五维量的距离，就会出现一个问题：像素距离给整体距离的影响是不确定的。如果要求的$k$值较小，每个像素离超像素中心的距离较大，那么像素距离就会给整体的距离带来更大的影响。为了让像素距离和颜色距离对距离的影响权重更为平衡，文章提出了如下的距离度量方式：

其中$i,j$表示两个进行距离比较的像素，$N_c,N_s$是用于标准化颜色距离和像素距离的量。

文章取 $N_s = S=\sqrt{N/k} $，$N_c$直接定义为一个常数$m$。文章建议$m$取$[1,40]$。现在距离定义成了如下形式：

实际实现时出于方便，距离用以下公式计算：

另外，当图片的形式发生变化时，公式可以很方便地修改。如果图片是灰度图，那么颜色度量只需要考虑灰度之间的差就行了；如果不是图片而是三维体素，那么只需要把空间距离加上$z$分量。

保证超像素连续性

由于像素分类的时候除了位置的相似性外，还考虑了颜色的相似性，这样会出现一些问题：一个靠左的像素，可能属于右边像素中心；一个靠右的像素，可能属于左边像素中心。这样的话同类的像素可能被另一类的像素切成了两块，在图像上并不连续。

为了强制同一类超像素连通，算法在迭代结束后又对超像素进行了处理。算法从上到下，从左到右尝试搜索未标记的像素。对正在搜索的像素，把其四邻域中与它属于同一个旧超像素的像素加入搜索队列，并标记其和当前搜索像素属于同一个新超像素。当前这片新超像素搜索结束后，若新超像素总数少于期望超像素大小的一半，则把当前超像素的标记改成上一个新超像素的标记。上一个新超像素是当前新超像素搜索起点四邻域中的一个新超像素。

初始超像素中心优化

初始的超像素中心如果处于梯度比较大的点的话，可能会影响算法之后的表现。

该算法实现时，计算每个初步选择的超像素中心的$3\times3$邻域的梯度，把梯度最小的像素作为最终的初始超像素中心。

梯度的计算是$x,y$方向上梯度之和。$x$方向梯度是左右两个像素颜色向量的差平方和，$y$方向梯度是上下两个像素颜色向量的差平方和。

默认参数

由于残差收敛很快，算法默认迭代10次。这样残差可以不用计算了。

颜色距离参数$m$固定为10。

基于超像素的图像分割

仅获得了图像的超像素还不够，还需要一些其他的方法来做图像分割。我又去找了一些基于超像素的图像分割论文。

我浏览了以下论文：

[1] Li Z, Wu X M, Chang S F. Segmentation using superpixels: A bipartite graph partitioning approach[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2012: 789-796.

[2] Zhou B. Image segmentation using SLIC superpixels and affinity propagation clustering[J]. Int. J. Sci. Res, 2015, 4(4): 1525-1529.

[1]论文本身质量较高，且没有使用深度学习的方法。论文提出了一种基于超像素和二分图分割的图像分割方法，需要输入类别数$k$，输出图像分割结果。我一开始看到了标题中的二分图，以为图像分割会被转换成一个可以用我十分熟悉的二分图算法解决的问题。但是文章莫名其妙地把问题变成了一个我很陌生的二分图分割的问题。我既没有从文章不清晰的叙述中理解问题转换的原理，也不愿去学一个看起来比较复杂的二分图分割算法。所以最后放弃了实现这篇论文的方法。

在Google上搜索”superpixel based segemenataion”或”image segmentation using superpixel”，都能搜出这个网站。该网站的作者实现了一个基于超像素的图像分割算法，其算法来自论文[2]。论文[2]非常直接地把SLIC和AP聚类两个算法拼接起来，得到了一种基于超像素和聚类的图像分割算法，该算法不用指定类别数。正好，我觉得超像素这个预处理已经对图像分割帮助很大了，只需要一个简单的超像素分类算法即可。我最终决定学习论文[2]的方法。

学论文[2]不应该去看那篇论文，而应该去看AP聚类算法的论文Clustering by Passing Messages Between Data Points。这种聚类算法比较有名气，搜索引擎上可以找到不少分析此算法的中文内容。

AP算法需要提供数据间的相似度这一二元关系矩阵，输出每个数据点属于的数据中心。AP算法的思想我没有理解，但其流程十分简单：算法构建了两个关系矩阵$r，a$，用以描述某个点适合作为另一个但数据中心的程度。算法用两个公式来更新这两个关系矩阵直至矩阵收敛。特别地，为了防止数值上的问题，算法引入了一个更新系数$\lambda$，每次保留$\lambda$倍的上一轮值，加上$(1 - \lambda)$倍更新值。这个比例系数在数值算法中非常常见，有点像梯度下降中的学习率。

如果我把AP算法理解了，会写一篇博客来详细介绍这一算法。

把AP算法运用在图像分割中，只需要定义图像任意两个超像素间的相似度就行了。论文[2]的主要贡献也就是定义相似度。论文[2]比较了3种相似度定义方式，最终选择了效果最好，也最简单的一种定义方式：相似度定义为负带权颜色向量差平方和，即：

其中$s(i,j)$表示超像素$i,j$间相似度，$L,a,b$是超像素平均LAB颜色空间颜色向量分量。

论文中超像素数$K=600$，超像素颜色距离参数$m=20$，颜色权值$w_l=3,w_a=10,w_b=10$。理论上这些参数都是可以调的，甚至相似度的定义参数也是可以调的。