实践环境为：android-studio-bundle-162.4069837-windows（Android Studio 2.3.3 带 Android SDK 版）、该 Android Studio 自带的 JRE，系统环境为 Win10-1607。

前言

　　由于上一届没有更新任何项目文档和学习文档，Shaun 只能自己去网上查找相关的资料，从零开始学习，顺便留下一些文档，正所谓：「代码未动，文档先行」，也算是实践出真知吧。

PS： 本次实践的项目主要来自 12.1Android 实战 ：DrySister看妹子应用(第一版) — 项目搭建与简单实现（http://www.runoob.com/w3cnote_genre/android） 以及目前手头上正在维护的项目。

布局篇

　　首先打开 Android Studio ，新建项目，一路默认下去即可，等待片刻，“MainActivity.java” 文件的错误提示就会自然消失，将左侧栏上方的 “Android” 切换为 “Project”，打开 app -> src -> main -> res -> layout -> activity_main.xml，由于其默认是以 “Text” 的模式打开（Android Studio 右侧有个 “Preview” 标签可以进行当前布局预览），这对于小白来说不大好控制布局，所以需要在该文件底部将 “Text” 切换为 “Design”，如此可以进行拖拽式布局，以下正式开始进入 Android UI 的布局。至于具体如何进行布局设置，可以参考 Android ConstraintLayout 使用指南 和 Android实现拖拽式布局开发----约束性布局 以下两篇资料。

　　而若要使控件大小根据屏幕大小自适应，一般可使用相对布局，但如今的 Android Studio 默认新建的页面就是一种类似于相对布局的页面，所以直接在控件中设置 android:layout_width="match_parent" 以及 android:layout_height="match_parent" 属性即可，再设置 layout_margin 属性进行调整即可，而若要让控件大小随控件内的内容自适应，则只需要将 match_parent 更改为 wrap_content 即可。

编码篇

　　首先新建自己的业务逻辑 java 代码，具体新建方法可参考 Android studio怎么创建一个Java类文件 ，在 MainActivity.java 文件所在目录上鼠标右键 New -> Java Class，新建完成之后即可编写自己的业务逻辑。若要新建文件夹，则在目录上鼠标右键 New -> Package 。若要使级联目录展开，例如 com.example.admin.myapplicationtest，则需要在该目录的父级目录新建一个 com.example.admin.test Package 即可将com.example.admin 目录展开。

页面跳转

　　首先新建一个页面 jump_test_activity，在 \MyApplicationTest\app\src\main\res\layout，即 layout 文件夹上鼠标右键，“New” ==》“Activity” ==》“Empty Activity” （有多种 Activity 样式可供选择，Shaun 这里就以 Empty Activity为例了），随后弹出窗口，在 Activity Name 栏填写页面逻辑控制代码文件名 JumpTestActivity，在 Layout Name 栏填写页面 UI 设计代码文件名 jump_test_activity，在 Package name 以及页面逻辑控制代码文件所在在包名 com.example.admin.myapplicationtest.ui.activity，其它设置为默认即可，这样新建的页面的有个问题就是会有一个丑陋的标题栏，所以还需要去掉该标题栏，具体方法为：

1. 在 MyApplicationTest\app\src\main\res\values\styles.xml 文件中添加：

   1 2 3 4

   <style name="AppTheme.NoActionBar"> <item name="windowActionBar">false</item> <item name="windowNoTitle">true</item> </style>

2. 将 MyApplicationTest\app\src\main\AndroidManifest.xml 中的 <activity android:name=".ui.activity.JumpTestActivity"></activity> 更改为 <activity android:name=".ui.activity.JumpTestActivity" android:theme="@style/AppTheme.NoActionBar"></activity> ，再次编译运行即可看到标题栏已消失。

好了，准备阶段已经搞完，接下来就是正式的页面跳转了，一般页面跳转是用户点击事件发生的，所以需要添加一个具有点击事件的控件，一般而言就是 Button 了，这里设该 button 的 id 为 page_jump_btn；该 button 所在页面为 MyApplicationTest\app\src\main\res\layout\activity_main.xml，则在对应的逻辑控制文件MyApplicationTest\app\src\main\java\com\example\admin\myapplicationtest\ui\activity\MainActivity.java 中的页面跳转代码为：

1
2
3
4
5
6
7
8

page_jump_btn = (Button) findViewById(R.id.page_jump_btn);
page_jump_btn.setOnClickListener(new View.OnClickListener() {
	@Override
	public void onClick(View v) {
		Intent intent = new Intent(MainActivity.this, JumpTestActivity.class);
		MainActivity.this.startActivity(intent);
	}
});

如此，在主界面中点击跳转按钮，即可跳转到新建页面。

URL 中的坑

　　在学 12.2 的时候，由于请求的URL地址中有中文“福利”，所以其返回的字符串为：

1
2
3
4

{
"error": false,
"results": []
}

可以看到 “results” 的值为空，这显然是错的，后面调试发现需要对 URL 地址转义（这都 8102 年了，为什么 URL 地址中还要有中文，或者说为什么 URL 地址还不支持解析中文 ╮(╯▽╰)╭），具体转义代码如下：

1
2
3

fetch_url = Uri.encode(fetch_url);  // 将URL地址转义
fetch_url = fetch_url.replace("%3A", ":");  // 将%3A替换为:
fetch_url = fetch_url.replace("%2F", "/");  // 将%2F替换为/

主要参考资料为：Android url中文乱码问题及解决办法 和 Android URL encode 空格处理 。

SQL 语句中的坑

　　在使用字符串拼写 SQL 语句时，一定要注意 SQL 语句中的空格，要不然拼起来的 SQL 语句可能语法不通而导致 APP 崩溃。如在使用创建表的 SQL 语句时，可能的错误写法（不注意空格）如下：

1
2
3
4
5
6
7
8
9
10
11
12

String create_table_sql = "CREATE TABLE IF NOT EXISTS" + TableDefine.TABLE_FULI + "("
                + TableDefine.COLUMN_ID + "INTEGER PRIMARY KEY AUTOINCREMENT,"
                + TableDefine.COLUMN_FULI_ID + "TEXT,"
                + TableDefine.COLUMN_FULI_CREATEAT + "TEXT,"
                + TableDefine.COLUMN_FULI_DESC + "TEXT,"
                + TableDefine.COLUMN_FULI_PUBLISHEDAT + "TEXT,"
                + TableDefine.COLUMN_FULI_SOURCE + "TEXT,"
                + TableDefine.COLUMN_FULI_TYPE + "TEXT,"
                + TableDefine.COLUMN_FULI_URL + "TEXT,"
                + TableDefine.COLUMN_FULI_USED + "BOOLEAN,"
                + TableDefine.COLUMN_FULI_WHO + "TEXT"
                + ")";

以上写法无法正确建表，甚至会因为错误 SQL 语句而导致 APP 闪退，正确的写法如下：

1
2
3
4
5
6
7
8
9
10
11
12

String create_table_sql = "CREATE TABLE IF NOT EXISTS " + TableDefine.TABLE_FULI + " ("
                + TableDefine.COLUMN_ID + " INTEGER PRIMARY KEY AUTOINCREMENT, "
                + TableDefine.COLUMN_FULI_ID + " TEXT, "
                + TableDefine.COLUMN_FULI_CREATEAT + " TEXT, "
                + TableDefine.COLUMN_FULI_DESC + " TEXT, "
                + TableDefine.COLUMN_FULI_PUBLISHEDAT + " TEXT, "
                + TableDefine.COLUMN_FULI_SOURCE + " TEXT, "
                + TableDefine.COLUMN_FULI_TYPE + " TEXT, "
                + TableDefine.COLUMN_FULI_URL + " TEXT, "
                + TableDefine.COLUMN_FULI_USED + " BOOLEAN, "
                + TableDefine.COLUMN_FULI_WHO + " TEXT"
                + ")";

调试篇

　　编码完成之后，一般而言需要进行调试，Android Studio 的调试可参考 【Android 开发入门】android studio 控制台打印输出日志 ，进入调试模式具体方法为：点击上方工具栏中的 Debug 'app' 图标，而不是直接 Run 'app'，进入调试模式之后，点击下方的 “Android Monitor”，切换到 “logcat” 标签，即可查看调试信息。

　　华为手机打印调试信息可参考 华为手机logcat不出日志解决方案。这里由于 Shaun 还没有对 AndroidManifest.xml 进行修改，所以该 APP 在点击 Button 的时候会直接闪退，调试窗口出现 java.lang.SecurityException: Permission denied (missing INTERNET permission?) 错误信息，参考 android菜瓜笔记之missing INTERNET permission 和 SecurityException: Permission denied (missing INTERNET permission?) 可知，该 APP 没有网络权限，所以需要在 AndroidManifest.xml 中添加网络权限，具体在 manifest 标签中添加语句 <uses-permission android:name="android.permission.INTERNET" />，如此该 APP 就能正常执行了。

PS： 如果是对应用发生闪退或崩溃的原因进行调试，建议直接在 logcat 中搜索 fatal 关键字。

附录

更换马甲重新发布为另一个 app

　　即一样的代码却编译出另一个相同的 app，在某些特殊的需求（使两个功能大致一样的 app 共存在一台手机上）上可能需要这个技巧，具体步骤如下（以 MyApplicationTest 更名为 MyApplication 为例）：

1. 首先将 MyApplicationTest 文件夹（即 APP 根目录）更名为 MyApplication；（这一步不是刚需）
2. 将 MyApplicationTest\app\src\main\res\values\strings.xml 文件中 <string name="app_name">MyApplicationTest</string> 更改为 <string name="app_name">MyApplication</string>；
3. 将 MyApplicationTest\app\build.gradle 文件中 applicationId "com.example.admin.myapplicationtest" 更改为 applicationId "com.example.admin.myapplication" 。（这一步是刚需）

如此，即可另外安装一个全新 APP，同时保留原有 APP，至于 applicationId 的更多作用和用法可参考 设置应用 ID 。更换 APP 图标只需在 app 文件上鼠标右键， “New” ==》“Image Asset” ，即可弹出设置 app 图标窗口，或者直接更改 AndroidMainfest.xml 文件中的 android:icon 也可。

后记

　　排版可能有点乱，毕竟是随便写的，碰到问题就简单的记录一下，Shaun 这次的实践过程可在 AndroidLearning 中查看，页面跳转的方法来自手头上正在开发维护的一个项目，附录中第一个问题的来源是对方提出的一个特殊需求。

前言

　　在写快排的时候偶然发现了 C++ 数组中的一个坑，具体表现为：对数组元素进行无临时变量的自交换时竟然会将数组该元素置为 0，这应该是 C++ 的一个 BUG Shaun 脑子抽了。

交换函数篇

　　据参考资料 [1] 中， C++ 的交换函数可以有如下三种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 第一种：使用模板，创建临时变量
template <class T> void swap(T &a, T &b)
{
	T temp(a); a = b; b = temp;
}

// 第二种：无临时变量，针对int,double等内建数值类型的基本运算（以double为例）
void swap(double &a, double &b)
{
	a = a + b;
	b = a - b;
	a = a - b;
}

// 第三种：无临时变量，针对int的异或运算
void swap(int &a, int &b)
{
	// a ^= b ^= a ^= b;
	a = a ^ b;
	b = b ^ a;
	a = a ^ b;
}

　　其中，第一种是通用的交换方法，无论做什么交换都能用第一种，但需要创建一个临时对象；而第二种不需要创建一个临时对象，只能用在 int，double 等内建数值类型上，且存在溢出的风险；第三种同样不需要创建临时对象，只能用在 int 类型上，由于采用位运算，所以不存在溢出的风险，且效率最高。

BUG 复现篇

　　bug 复现代码如下：

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

#include <iostream>

template <class T> void swap_1(T &a, T &b)
{
	T temp(a); a = b; b = temp;
}

void swap_2(int &a, int &b)
{
	a = a + b;
	b = a - b;
	a = a - b;
}

void swap_3(int &a, int &b)
{
	a ^= b ^= a ^= b;
}

int main(int argc, char *argv[])
{
    int data[] = { 0, 3, 8, 2, 9, 4, 6, 1, 7, 5 };
	int a = 1, b = 2, c = 3;
	swap_1<int>(data[a], data[b]);
	printf("%d\t%d\n", data[a], data[b]);	// 输出 8	3
	swap_1<int>(data[a], data[a]);
	printf("%d\t%d\n", data[a], data[a]);	// 输出 8	8
	swap_2(data[a], data[b]);
	printf("%d\t%d\n", data[a], data[b]);	// 输出 3	8

	swap_2(data[a], data[a]);
	printf("%d\t%d\n", data[a], data[a]);	// ***输出 0	0***

	swap_3(data[b], data[c]);
	printf("%d\t%d\n", data[b], data[c]);	// 输出 2	8

	swap_3(data[b], data[b]);
	printf("%d\t%d\n", data[b], data[b]);	// ***输出 0	0***
	
	std::swap(data[4], data[5]);
	printf("%d\t%d\n", data[4], data[5]);	// 输出 4	9
	std::swap(data[4], data[4]);
	printf("%d\t%d\n", data[4], data[4]);	// 输出 4	4
	
    return 0;
}

　　目前没有找到什么好的解决方案，只能老老实实的用第一种创建一个临时变量的交换方法，或者在交换之前先判断一下是不是同一个元素，若不为同一个元素，才进行交换，否则不交换，即避免自交换。

后记

　　刚开始出现这个问题的时候，Shaun 还纳闷了，怎么写个快排把数组元素都改变了，刚开始根本没想到这茬，还以为是 Shaun 代码的问题，倒着检查了好几遍，换第一种交换方式以及换个冒泡排序用一样的交换方式进行排序输出结果都没问题，后面使出终极调试法，一个个的输出看看才知道原来是自交换的锅。

　　如果有大佬知道为什么会出现这个问题还望不吝赐教 ◔ ‸◔?。经 @ Magnesium12 大佬提醒，这个问题由于引用引起的，采用第二种方法进行交换时如果两个数是完全一样的（地址也一样），则在进行两数相减时，由于是引用，所以这两个数完全一样，则最后会导致这两个完全一样的数，即自交换的该数置为 0 。

参考资料

[1] 谈谈C++中的swap函数

由于一些历史原因，本篇配置的 Android 开发环境所需的软件对应版本号为：jdk-7u80-windows-x64、android-studio-bundle-162.4069837-windows（Android Studio 2.3.3 带 Android SDK 版），系统环境为 Win10-1607。

前言

　　没想到，时隔两年之后又要重新捡起 Java，还要学基本没怎么做过的 Android，而且还是在这节骨眼上，真是造化弄人 _(´ཀ`」 ∠)_。

Java 环境篇

　　先在 Oracle Java Archive 下载对应的 Java 版本，下载完成后去 这里 校验对应的 Hash 值（若是其它 JDK 版本，则只需将 url 末尾的 7u80 改成相应的版本号即可），并安装，安装时需要注意，在安装完 JDK 之后，该安装器还会继续弹出让安装 JRE 的窗口，此时直接点取消即可，因为 JDK 中已包含 JRE ，所以没必要也不需要再继续安装，安装了之后，就相当于有两个 JRE ，还可能会为以后的工作造成一些麻烦。具体系统环境变量配置如下（若没有相应的变量名则新建）：

配置完之后，键入 Win+R ==》cmd ==》 Enter，在终端输入 “java -version”，“java”，“javac” ，这几个命令，若有正确的响应，则表示配置成功。

Android 篇

※注： 在安装和配置 Android Studio 时最好先自行找好梯子，这其中有一些步骤可能需要连接外网。

　　自然还是先在这里（http://www.android-studio.org/）下载安装 Android Studio ，为避免再下载安装配置 SDK 的麻烦，推荐直接下载带 SDK 版本的 Android Studio 。直接默认安装，其中安装 SDK 的时间略长。安装完成之后，推荐把 SDK 目录下的 tools 和 platform-tools 子目录也添加到系统的 PATH 环境变量中。

　　在第一次打开 Android Studio 的时候，可能需要连接外网以更新 SDK ，所以需要自行设置好代理，更新又要花一段时间 ╮(╯▽╰)╭，当然也可以选择不更新，不更新的办法为：

在AS启动前，打开安装目录，请先将bin目录的idea.properties文件中增加一行：disable.android.first.run=true就行了，避免第一次打开AS时自动重新下载SDK。

　　第一次运行时，首先需要配置 SDK 路径和 JDK 路径，配置 SDK 路径方法为：“Configure” —> “SDK Manager”，编辑 “Android SDK location” ，其会自动找到安装的 SDK 路径；配置 JDK 路径方法为：“Configure” —> “Project Defaults” —> “Project Structure”，编辑 “JDK location”（这里它有个默认内置的 jre，但推荐还是使用自己的 JDK）。

　　Android Studio 默认的编辑器方案无法更改字体（若真想在默认的方案上更改字体，可以先将其另存为一个新方案），而且个人认为其默认的主题（配色，字体等）不好看，所以推荐自行去 Color Themes 选择合适的主题。最终 Shaun 选择 Wombat 主题。至于导入主题的方法为：“Configure” —> “Import Settings”，将下载好的 jar 包导入即可。

　　为了测试方便，就直接装了个 网易MuMu模拟器 ，用起来感觉还可以，至于 Android Studio 连接 MuMu 模拟器的方法为：先打开 MuMu 模拟器，在 Android Studio 底下的 Terminal（终端） 中输入命令：adb connect 127.0.0.1:7555 ，响应 connected to 127.0.0.1:7555 则说明连接成功，这时就能愉快的使用 MuMu 模拟器调试 Android app 了。

后记

　　以后有碰到什么坑再继续记录吧 ╮(╯▽╰)╭。

参考资料

[1] Android Studio安装配置、环境搭建详细步骤及基本使用

[2] 第一次使用Android Studio时你应该知道的一切配置（http://www.cnblogs.com/smyhvae/category/587732.html）

[3] Android Studio连接不到MuMu模拟器

前言

　　本篇主要用来记录在 Windows 下使用命令行能做到的一些特殊技巧。

Windows 粉碎文件技巧

　　有时候 Windows 下会莫名出现文件无法删除的现象，即使通过 Shift+Delete 组合键也还是无法删除，这时可能需要通过一种 “文件粉碎机” 的工具才能删除，但是为了偶尔出现的这种现象而安装一个这样的工具又略显麻烦，这时只需要新建一个 Windows 批处理文件，即新建一个 txt 文本文件，并将后缀改为 .bat 即可，文件内容输入：

1
2

DEL /F /A /Q \\?\%1
RD /S /Q \\?\%1

其中

DEL 表示删除文件，命令参数为： del /?

/F：表示强制刪除

/A：选择文件的属性

/Q：静默模式，在删除时不会弹出提示信息

RD 表示刪除目录，命令参数为： rd /?

/S：连带删除子目录下的文件

/Q：静默模式，在删除时不会弹出提示信息

　　具体用法为将待删除的文件拖拽到该 .bat 文件图标上，用该 .bat 文件打开待删除的文件即可。

　　但有时候即使使用上面的方法，也无法删除文件，同时还会弹出“无法删除文件，文件或目录损坏且无法读取”这样的提示，这可能是文件存储时发生错误造成的，此时需要在 Windows 命令提示符界面中输入命令 CHKDSK 盘符:/F，盘符为需要删除的文件所在的磁盘或 U 盘，比如在 D 盘，则输入命令 CHKDSK D:/F，如出现无法锁定的提示信息，则输入 Y 强制卸载该卷，等待一段时间，等磁盘扫描和修复完成后即可删除待删除的文件。

Windows 校验文件技巧

　　为确保从网络上下载的文件为原文件，一般需要对其进行 hash 校验（如 SHA1、SHA256、SHA384、SHA512、MACTripleDES、MD5、RIPEMD160 值等），一般随原文件一起释放的比较常见的 hash 值有 SHA1、SHA256 或 MD5 等，但是为了校验下载文件的 hash 值可能需要专门的第三方工具，但其实 Windows 、Linux 和 macOS 都自带了校验 hash 值的命令，通过这些命令可以直接对文件的 hash 值进行校验，而不需要使用额外的第三方工具，这里只介绍 Windows 的哈希值校验命令，其命令为 Get-FileHash，具体使用方法如下：

1
2

# []内为待校验的文件 和 所用的hash算法
Get-FileHash [文件路径及名称] -Algorithm [校验的Hash值类型]| Format-List

　　如果觉得每次这样输入比较麻烦，可以使用参考资料[2]提供的注册表文件（.reg 后缀），双击运行，即可在鼠标右键菜单添加「文件哈希校验」，如此可以通过鼠标右键直接对文件进行 hash 校验。附其中代码如下：

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

Windows Registry Editor Version 5.00

[HKEY_CLASSES_ROOT\*\shell\文件哈希校验]

"SubCommands"="MACTripleDES;MD5;RIPEMD160;SHA1;SHA256;SHA384;SHA512"

"MUIVerb"="文件哈希校验"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\MACTripleDES]

@="MACTripleDES"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\MACTripleDES\command]

@="PowerShell Get-FileHash -Algorithm MACTripleDES \\\"%1\\\" | format-list;“按任意键退出...”;[Console]::Readkey() | Out-Null;exit"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\MD5]

@="MD5"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\MD5\command]

@="PowerShell Get-FileHash -Algorithm MD5 \\\"%1\\\" | format-list;“按任意键退出...”;[Console]::Readkey() | Out-Null;exit"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\RIPEMD160]

@="RIPEMD160"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\RIPEMD160\command]

@="PowerShell Get-FileHash -Algorithm RIPEMD160 \\\"%1\\\" | format-list;“按任意键退出...”;[Console]::Readkey() | Out-Null;exit"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA1]

@="SHA1"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA1\command]

@="PowerShell Get-FileHash -Algorithm SHA1 \\\"%1\\\" | format-list;“按任意键退出...”;[Console]::Readkey() | Out-Null;exit"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA256]

@="SHA256"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA256\command]

@="PowerShell Get-FileHash -Algorithm SHA256 \\\"%1\\\" | format-list;“按任意键退出...”;[Console]::Readkey() | Out-Null;exit"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA384]

@="SHA384"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA384\command]

@="PowerShell Get-FileHash -Algorithm SHA384 \\\"%1\\\" | format-list;“按任意键退出...”;[Console]::Readkey() | Out-Null;exit"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA512]

@="SHA512"

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\CommandStore\shell\SHA512\command]

@="PowerShell Get-FileHash -Algorithm SHA512 \\\"%1\\\" | format-list;“按任意键退出...”;[Console]::Readkey() | Out-Null;exit"

Windows 隐写文件技巧

　　在 Windows 下可以通过 copy 命令实现简单的文件合并，即隐写，例如：将压缩文件隐写入 jpg 文件中，将 txt 文件隐写入 jpg 文件中。这样在没改后缀名的情况下，该文件是以图片形式存在，若要恢复原有隐写文件信息，则只需要将 jpg 后缀名更改为相应文件后缀名，例如：若隐写的是 rar 文件，则只需将后缀名 .jpg 改为 .rar ，再用解压缩软件打开即可，也可以直接用解压缩软件打开相应 jpg 文件；若隐写的是 txt 文件，则需要用记事本打开该文件，通过 ctrl+end 组合键让光标定位到文件最末尾，即可看到隐写的 txt 文件内容。

具体命令如下：

1
2
3
4
5
6
7
8
9
10
11

# 将 b.txt 隐写进 a.jpg 中，并输出为 c.jpg
copy/b a.jpg+b.txt c.jpg

# 将当前目录下 2.rar 隐写进 1.jpg 中，并输出为 3.jpg
copy /b ./1.jpg + ./2.rar ./3.jpg

# 将 b.txt 隐写进 a.jpg 中，并输出为 c.jpg
copy a.jpg /b + b.txt /a c.jpg

# 将 b.rar 隐写进 a.jpg 中，并输出为 c.jpg
copy a.jpg /b + b.rar c.jpg

※注：图片文件要放在前面，需要隐写的信息放在后面，不然输出的图片无法正常查看和显示。

　　其中参数 /b 表示以二进制格式复制、合并文件，在合成图片和压缩文件等二进制文件时必须使用该参数，不然会丢失信息，从而造成合成失败，当然合成 txt 文本文件时也可以使用该参数；参数 /a 表示以 ASCII 码格式复制、合并文件，参数 /a 只适用于 txt 文本文件合并。

　　至于其它需要注意的就是：1、要合成的两个文件最好放在同一目录下，不然输入路径有点麻烦； 2、txt 文本文件前面最好空三行，这样它头部的内容就不会丢失。

　　输出的图片 c.jpg 和原图片 a.jpg 显示是一样的，看起来就是同一张图片，因此达到隐写的目的。

Win10 开启休眠方法

　　不知道巨硬是怎么肥事，居然 Win10 中默认电源选项中没有「休眠」选项，需要手动开启。虽然睡眠和休眠有重叠的地方，但是休眠是完全关机，再次开机时会恢复原有工作状态，更多的情况是必须要关机（因为需要考虑电量情况），相反如果有充足电力的情况下，还不如使用锁定代替睡眠，从这里的需求看还不如在默认电源选项中去掉「睡眠」选项。好了，抱怨吐槽的话就说这么多了，具体开启「休眠」的方法为：只需要在命令行（需要以管理员身份打开「命令提示符」）中输入一下命令：

1

powercfg /H on

回车 执行即可在电源选项中发现「休眠」选项。

Windows 新建用户命令

　　前一段时间电脑系统升级之后崩了，资源管理器损坏，没有任务栏，没有桌面，Win 键都无法使用，还好可以使用任务管理器，通过任务管理器调出 cmd，输入以下命令新建一个用户：

1
2
3
4
5

# 添加用户tmp、密码123  
net user tmp 123 /add  
  
# 设置tmp为管理员  
net localgroup administrators tmp /add  

　　通过 tmp 用户可以正常使用电脑，因此猜测应该是原来的用户系统配置文件（例如注册表文件，系统设置文件等等）损坏。系统损坏之后捣鼓了两天，这没办法修复了，即使新建用户也还是有些软件没法使用，还不如直接重装系统（系统出现问题果然重装系统才是最快的解决方案），还好可以新建用户以备份原有系统盘文件，不然就是真 gg 了。既然新建命令记录了，也顺便记录一下删除命令吧，删除用户 tmp 命令为：net user tmp /del 。

Windows 解除 U盘或移动移动硬盘被占用技巧

　　Windows 在弹出 U盘或移动硬盘时，有时会出现 “该设置正在使用中，请关闭可能使用该设备的所有程序或窗口，然后重试。” 的提示，导致 弹出 USB 大容量存储设备时出现问题，无法弹出。解决该问题需要知道是那个或哪些程序占用该存储设备，然后结束该进程即可。查看存储设备占用程序 Shaun 知道的有两种方法：

1. 通过 “Windows 日志”。Windows 每次弹窗提示都会有相应的日志，右键计算机 ==》管理 ==》事件查看器 ==》Windows日志 ==》系统，然后在窗口左侧查找其中有黄色警告的日志信息，找到来源为 Kernel-PnP 的日志，双击该日志即可看到 “进程 ID 为 XXX 的应用程序 XXX 已停止删除或弹出设备 XXX。” 之类的信息，从而知道是哪个进程占用该存储设备，停止该进程即可正常弹出。停止进程一般通过 任务管理器 ==》详细信息，找到对应的 名称 和 PID，右键 ==》结束任务即可。
2. 通过 “资源监视器”。右键计算机 ==》管理 ==》性能，打开资源监视器。然后在 “CPU” 栏中找到 “关联的句柄”，在后面的搜索栏中输入存储设备的盘符（D: 、E: 或 F: 等 ），即可显示占用程序的 名称 和 PID，随后在任务管理器中停止该进程即可。

　　※注： 有时只有 System 进程阻止存储设备弹出，这时可以直接关机了 :），因为 System 进程是系统核心进程，不能结束，结束之后系统会崩溃，并自动关机。当然，如果是其他进程阻止，可以用上述方法正常弹出，一般阻止存储设备弹出的都是 explorer.exe，在停止该进程后，Windows 的任务栏将会消失，所以需要在任务管理器中重新运行该任务（任务管理器 ==》文件 ==》运行新任务， 输入 “explorer” 即可）。

后记

　　如果以后碰到更多有意思的小技巧再继续和大家分享吧 ↖(^ω^)↗。

参考资料

[1] windows文件夹删不掉怎么办

[2] 巧在Win10右键菜单添加校验文件Hash值命令（MD5、SHA1/256等）

[3] 【命令行copy命令】将txt文档与jpg图片合并

[4] 升級Win10後，為何筆電專有的休眠選項消失了

[5] CMD命令（添加删除管理员账户）

前言

　　前面有一段时间需要对视频做一些简单的处理，所以就去查了一下一些常用的视频处理工具，因为不想再另外装个什么软件，所以就决定直接采用 FFmpeg 了，毕竟其它的一些视频处理软件也极有可能只是对 FFmpeg 进行一些图形化界面的封装而已。

　　而在查找 FFmpeg 相关资料的时候，也同时发现了 Libav ， 对于 FFmpeg 和 Libav Shaun 只想说，开源界的战争总是这么莫名其妙，有各种各种一些奇怪的原因（或许大佬们都是各有各的脾性吧 ╮(╯▽╰)╭），像两个小飞机的战争也是如此，不过神仙打架，凡人享福也好 ~\(≧▽≦)/~。神仙们的想法我等凡人是无法揣测了，不过这种事还是少出点为好，不然下次变为小鬼遭殃就不好了。

　　使用 FFmpeg 而不是 Libav 是因为 FFmpeg 的相关资料相对来说要多很多；而且Libav 更新的特性，FFmpeg 全都支持；更重要的是 FFmpeg 是更新特别频繁，差不多是日更了，几乎每天都会发布一个稳定版；而且从两者的下载页面来看， FFmpeg 好像更会照顾跨平台用户一点。下文主要是对 FFmpeg 的部分命令进行记录总结。

Shaun 的系统环境为 Win10 1607，测试的 FFmpeg 版本为 ffmpeg-20180429-19c3df0-win64-static。

　　在 Win10 下使用 FFmpeg 前首先需要配置系统环境变量，Windows 下 FFmpeg 的安装是下载完 Windows 版编译好的 FFmpeg 压缩包后直接解压即可，将解压后的 FFmpeg 文件夹中的 bin 目录添加到系统环境变量 Path 中，不然系统会无法找到 ffmpeg 命令。

提取命令

　　FFmpeg 的提取命令的参数很多，因此可以使用不同参数排列组合达到不同的提取效果，具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# （1）快速提取video.mp4从第一分钟开始持续两分钟的视频，即到第三分钟，并将提取结果输出为cut.mp4
ffmpeg -ss 00:01:00 -i video.mp4 -to 00:02:00 -c copy cut.mp4

# （2）快速提取video.mp4从第一分钟开始持续两分钟的视频，即到第三分钟，并将提取结果输出为cut.mp4
ffmpeg -ss 00:01:00 -i video.mp4 -t 00:02:00 -c copy cut.mp4

# （3）快速提取video.mp4从第一分钟开始到第二分钟的视频，并将提取结果输出为cut.mp4
ffmpeg -ss 00:01:00 -i video.mp4 -to 00:02:00 -c copy -copyts cut.mp4

# （4）精确提取video.mp4从第一分钟开始到第二分钟的视频，并将提取结果输出为cut.mp4
ffmpeg -i video.mp4 -ss 00:01:00 -to 00:02:00 -c copy cut.mp4

# （5）精确提取video.mp4从第一分钟开始持续两分钟的视频，即到第三分钟，并将提取结果输出为cut.mp4
ffmpeg -i video.mp4 -ss 00:01:00 -t 00:02:00 -acodec copy -vcodec copy cut.mp4

# （6）快速提取video.mp4从第三分钟开始持续60秒的视频，即到第四分钟，并将提取结果输出为cut.mp4
ffmpeg -ss 00:03:00 -i video.mp4 -t 60 -c copy -avoid_negative_ts 1 cut.mp4

以下为各参数的含义：

• -i：用法为 -i INPUT_VIDEO，代表输入的视频，该视频应为 MPEG 编码（h.264, MPEG4/divx/xvid, MPEG2; MP2, MP3, AAC） ；
• -ss：用法为 -ss START_TIME，代表提取的开始时间，时间格式有两种写法：1、纯数字格式，以秒为单位（eg: -ss 90，代表从第90秒开始提取）；2、时:分:秒 格式（eg: -ss 00:01:30，代表从 0 时 1 分 30 秒开始提取）；
• -to：用法为 -to STOP_TIME，代表提取的结束时间，时间格式同样有两种写法：1、纯数字格式，以秒为单位（eg: -to 180，代表第180秒结束提取）；2、时:分:秒 格式（eg: -to 00:03:00，代表 0 时 3 分 00 秒结束提取）；
• -t：用法为 -t DURATION_TIME，代表提取的持续时间，时间格式同样有两种写法：1、纯数字格式，以秒为单位（eg: -to 180，代表提取持续180秒）；2、时:分:秒 格式（eg: -to 00:03:00，代表提取持续 0 时 3 分 00 秒）；
• -c：用法为 -c CODEC，代表音视频编码格式（若 CODEC 为 copy 则代表输出视频的音视频编码格式与原视频一样），其实 -c 是 -codec 的缩写，其中包含音频编码参数 -acodec 和 视频编码参数 -vcodec ；
• -copyts：保持原有时间戳，即使当 -ss 在 -i 之前时，仍使 -t 和 -to 保持原有效果，不会被同化；
• -avoid_negative_ts：当开启该参数时，提取视频会找到首尾的相邻关键帧（这样会造成提取时间不精确），补全视频，当 -ss 在 -i 之前时该参数默认开启；
• -accurate_seek：使提取时间更精确，在转码时该参数默认启用。
• 更多参数可参考：Format-Options 。

※注： 1、-t 和 -to 不能同时使用，若同时使用，将以 -t 为准；　　2、当 -ss 在 -i 之前时，可以实现快速提取，但提取的时间点不精确，此时-to 和 -t 的效果一样，都表现为 -t ，此时可以加上 -copyts 参数使两者效果不一样；　　3、当 -ss 在 -i 之后时，提取的时间点比较精确，但提取速度比较慢。

　　以上命令（1）、（2）是一样的提取结果，命令（3）的 -t 和 -to 会产生不一样的结果，（6）的 -t 和 -to 会产生一样的结果。因此若只考虑速度，可以使用命令（3），若需使提取时间精确，则需使用命令（4）和（5）。

PS：当然还有一种更精确的方式，通过命令 ffmpeg -i input.mp4 -strict -2 -qscale 0 -intra output.mp4 将输入视频由原来的帧间编码转换为帧内编码，使每一帧都成为关键帧，如此转换之后再进行提取，可使提取时间十分精确，但该转换方式会造成视频文件空间成倍增大。

合并命令

　　FFmpeg 的合并命令大概有 4 种，可参考： FFMpeg无损合并视频的多种方法 。这里主要介绍两种：

方法一：使用 FFmpeg concat 分离器（推荐）

　　该方法使用命令为：ffmpeg -f concat -i filelist.txt -c copy output.mp4，其中 filelist.txt 文件最好和待合并的视频在同一个文件夹中，文件中内容就是待合并的视频的描述，具体内容如下：

1
2

file 'input1.mp4'
file 'input2.mp4'

或

1
2

file ./input1.mp4
file ./input2.mp4

※注： 待合并的视频文件名最好由英文、数字、连接符（-）或下划线（_）组成，且中间最好不要有空格，不然可能会因为文件名而在合并时出现一些奇怪的错误。

方法二：利用中间格式合并

　　所谓利用中间格式进行合并是因为可能有些待合并的视频编码不一致，这时采用方法一可能无法进行合并，这时需要对待合并的视频的进行统一转码，都转成同一个编码格式。若要采用这种方法，建议都转成 mpg 格式，因为 mpg 格式可以直接 cat 命令进行合并，具体如下：

1
2
3
4
5
6
7
8

# 将input1.avi转成intermediate1.mpg,输出视频质量为1
ffmpeg -i input1.avi -qscale:v 1 intermediate1.mpg
# 将input2.mp4转成intermediate2.mpg,输出视频质量为1
ffmpeg -i input2.mp4 -qscale:v 1 intermediate2.mpg
# 合并intermediate1.mpg和intermediate2.mpg，输出合并结果intermediate_all.mpg
cat intermediate1.mpg intermediate2.mpg > intermediate_all.mpg
# 将intermediate_all.mpg转成output.avi,输出视频质量为2
ffmpeg -i intermediate_all.mpg -qscale:v 2 output.avi

　　其中参数 -qscale 是指使用固定的视频量化标度 ，取值范围为 0.01 ~ 255 ，越小代表质量越好，一般推荐取值为 2 ~ 5，实际使用不能超过 50， -qscale:v 代表设置视频输出质量。

PS： 方法一为无损合并，方法二为有损合并。

后记

　　以后有用到新的命令再继续记录吧 ↖(^ω^)↗ 。纯命令行不太方便的话，可以试试 Avidemux，全平台通用。

参考资料

[1] ffmpeg Documentation（https://ffmpeg.org/documentation.html）

[2] FFmpeg wiki: Seeking（http://trac.ffmpeg.org/wiki）

[3] FFmpeg：视频转码、剪切、合并、播放速调整

[4] 通过 ffmpeg 无损剪切/拼接视频

[5] 使用ffmpeg合并视频文件的三种方法

前言

　　Shaun 最近想换换新口味，想尝试用 Cmder 作为 VSCode 下的默认终端，不想再继续使用 git-bash 了，因为 git-bash 有时会出现一些乱码问题。但是在用 VSCode 集成 Cmder 时出现了几个问题。

问题篇

　　如果在 VSCode 用户设置文件中直接添加 Cmder.exe 及其路径，那么在使用 VSCode 终端时会重新打开一个 Cmder 窗口，而不是直接显示在 VSCode 的「终端」里。Shaun 想要的是 Cmder 就是 VSCode 的终端，就在 VSCode 里，就和原有cmd 终端一样，在 VSCode 下的终端可以直接输入相关命令，而不是另外弹出一个命令行窗口。

解决方案篇

方法一

将 Cmder 放进一个文件夹中，文件夹名不带空格，比如 Shaun 所有的绿色软件全部放在 D:\ProgramFiles 下，在 VSCode 用户设置文件中添加：

1
2
3
4

"terminal.integrated.shell.windows": "C:\\Windows\\Sysnative\\cmd.exe",
"terminal.integrated.shellArgs.windows": [
    "/k D:\\ProgramFiles\\Cmder\\vendor\\init.bat"
],

方法二

一部分用户可能有点强迫症 ๑乛◡乛๑，硬是要把绿色软件还放入系统盘中的 Program Files 文件夹里，这样在 VSCode 里配置 Cmder 作为默认终端时就会出现问题。主要是因为 Program Files 文件夹名中有空格（这里吐槽一下带空格的文件名真鸡儿坑爹，命令行中根本无法访问，这应该是巨硬的历史遗留问题了， 特立独行的支持带空格的路径名，想显摆一下自己，但以目前的情况看，这种支持简直无力吐槽，造成了一堆问题，和 Windows 路径名中的 \ 有的一拼，都是逼死现代程序员的设计 _(´ཀ`」 ∠)_）。好了，吐槽的话也就说到这里了，如果配置路径里无法避免 Program Files 文件夹，这里有三种解决方案：

1. Windows 在支持带空格的长文件名的同时，也会分配一个短名称，可以称为该文件夹的别名，通过这个别名就可以在命令行中访问该文件夹，获取这个别名的方法有：在命令行中输入 dir /X ，即可在文件夹名之前的一列的看到该别名，若没有别名则为空白，若要添加别名则需要加入 /N 参数。Shaun 这里显示别名如下：

   1 2 3 4 5 6 7 8 9 10 11 12 13

   $ dir /X 驱动器 C 中的卷是 System 卷的序列号是 XXXX-XXXX C:\ 的目录 ......... 2018/05/16 19:21 <DIR> PROGRA~1 Program Files 2018/05/17 15:14 <DIR> PROGRA~2 Program Files (x86) ..........

   由上面可知 Program Files 文件夹的别名为 PROGRA~1，而 Program Files (x86) 文件夹的别名为 PROGRA~2，在配置路径时只需要用别名替换相应的文件夹名即可，如下：

   1 2 3 4 5 6

   { "terminal.integrated.shell.windows": "C:\\Windows\\Sysnative\\cmd.exe", "terminal.integrated.shellArgs.windows": [ "/k C:\\PROGRA~1\\Cmder\\vendor\\init.bat" ] }

2. 通过转义符添加 " " 使 Program Files 作为一个整体，如下：

   1 2	"terminal.integrated.shell.windows": "cmd.exe", "terminal.integrated.shellArgs.windows": ["/k", "C:\\\"Program Files\"\\Cmder\\vendor\\init.bat"],

3. 直接在系统环境变量中新建一个变量，将 Cmder 的根目录加进去，如下：

   变量名	变量值
   CMDER_ROOT	C:\Program Files

   再在 VSCode 用户设置文件中添加：

   1 2 3 4

   "terminal.integrated.shell.windows": "C:\\Windows\\system32\\cmd.exe", "terminal.integrated.shellArgs.windows": [ "/k %CMDER_ROOT%\\vendor\\init.bat" ]

通过以上几种方法（推荐直接使用方法一），就能成功在 VSCode 中集成 Cmder，可以直接在 VSCode 的终端里享受 Cmder 了。

后记

　　没有什么好说的了，该吐槽也已经吐槽完了。方法二 Shaun 没试过，只是感觉应该可行，有问题的小伙伴可以在下方留言（这是不可能的，这辈子都不会有人留言的，反正也没人会看到的 ╮(╯▽╰)╭）。以上解决方案全部来自网络，Shaun 只是做个总结记录，万一以后碰到类似问题至少有多种方案可以尝试。

参考资料

[1] How to use Cmder in Visual Studio Code?

[2] Setting Cmder.exe as integrated shell still opens in separate window

[3] IntelliJ idea webstrom Visual Studio Code vscode 设置cmder为默认终端 Terminal

前言

　　图割算法主要有两个发展方向，一个是 Shaun 上次写过的 Graph Cuts ，通过边界项和区域项（有的可能还会添加一个约束项，或者叫标签项）之和建立能量方程，并利用一定程度的交互式构建一个 S/T 图，最后采用最大流/最小割（Max-flow/Min-cut ）算法寻找 S/T 图的最小“割”，从而对图像进行分割；而另一个方向就是 NCuts（Normalized Cuts），中文一般叫规范割、标准割等等，该方法主要出自：Shi J, Malik J. Normalized cuts and image segmentation[J]. IEEE Transactions on pattern analysis and machine intelligence, 2000, 22(8): 888-905. 。

提到 NCuts，就不得不提「谱聚类」，因为 NCuts 可以说是谱聚类的一个应用。

谱聚类篇

谱聚类（Spectral Clustering， SC）是一种基于图论的聚类方法——将无向带权图划分为两个或两个以上的最优子图(sub-Graph)，使子图内部尽量相似，而子图间距离尽量远，以达到常见的聚类的目的。

在了解谱聚类之前需要先了解两个概念：拉普拉斯矩阵（Laplace Matrix）和瑞利熵（Rayleigh quotient）。

拉普拉斯矩阵

拉普拉斯矩阵的定义如下：

设 \(W\) 为无向带权图 \(G=(V,E)\) 的邻接矩阵，\(D\) 为无向带权图 \(G\) 的度矩阵，（所谓的度矩阵即为图中各顶点邻接的所有边权值之和构成的矩阵，是一个对角矩阵，若设顶点 \(i\) 和顶点 \(j\) 之间的权值为 \(w(i,j)\)，则度矩阵对角线上的元素 \(d_{i,i}=\sum \limits_{j=1}^n w(i,j)\) ），则拉普拉斯矩阵 \(L=D-W\)。如下图：

若图的邻接矩阵：\(\mathbf{W}=\begin{pmatrix} 0 & 0.1 & 0 & 0 & 0.2 & 0 \\ 0.1 & 0 & 0 & 0.5 & 0.1 & 0 \\ 0 & 0 & 0 & 0.3 & 0 & 0.4 \\ 0 & 0.5 & 0.3 & 0 & 0 & 0.1 \\ 0.2 & 0.1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.4 & 0.1 & 0 & 0 \end{pmatrix}\) ，其中图中不连通的顶点之间的权值为 0；

则对应的度矩阵为：\(\mathbf{Ｄ}=\begin{pmatrix} 0.3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.7 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.7 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.9 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.5 \end{pmatrix}\)

则拉普拉斯矩阵 \(L\) 为：\(\mathbf{L}=\mathbf{D}-\mathbf{W}=\begin{pmatrix} 0.3 & -0.1 & 0 & 0 & -0.2 & 0 \\ -0.1 & 0.7 & 0 & -0.5 & -0.1 & 0 \\ 0 & 0 & 0.7 & -0.3 & 0 & -0.4 \\ 0 & -0.5 & -0.3 & 0.9 & 0 & -0.1 \\ -0.2 & -0.1 & 0 & 0 & 0.3 & 0 \\ 0 & 0 & -0.4 & -0.1 & 0 & 0.5 \end{pmatrix}\)

以上三个矩阵都为实对称矩阵。对于拉普拉斯矩阵，由 $L* [1,1,1,1,1,1]^T =0* [1,1,1,1,1,1]^T= $ 可知其一定存在一个特征值为 0，对应的特征向量为 \([1,1,1,1,1,1]^T\) 。

拉普拉斯矩阵是半正定的，且对应的 n 个实数特征值都大于等于 0，即 \(0=λ_1≤λ_2≤\cdots≤λ_n\)， 且最小的特征值为 0 。

至于拉普拉斯矩阵的更多性质，可参考：Laplacian matrix 。

瑞利熵

　　瑞利熵的公式形如：\(R(M,x)=\frac{x^*Mx}{x^*x}\) ，其中 M 是厄米特矩阵（Hermitian matrix），满足 \(M=M^H\) ，即矩阵 \(M\) 与其共轭转置矩阵相等，\(x\) 为非 0 向量，\(x^*\) 是指 \(x\) 向量的共轭转置向量。对于实数而言，厄米特矩阵就是对称阵 \(M=M^T\)，\(x^*\) 就是 \(x\) 向量的转置向量 \(x'\) 或 \(x^T\)。

　　若设 \(x^*x=c\)，其中 \(c\) 为一个常数，则 \(R(M,x)=\frac{x^*Mx}{c}\) ，则其极值问题可转化为：\(\min R(M,x) = \min x^*Mx \qquad s.t.\ x^*x=c\) ，可利用拉格朗日乘数法求取 \(x^*Mx\) 的极值。 具体求法如下： \[ \mathcal{L}(x) = x^T M x -\lambda \left (x^Tx - c \right) \\ \begin{align} &\frac{d\mathcal{L}(x)}{dx} = 0 \\ &\Rightarrow x^TM - \lambda x^T = 0 \\ &\Rightarrow Mx - \lambda x = 0 \\ &\Rightarrow M x = \lambda x \end{align} \\ \therefore R(M,x) = \frac{x^T M x}{x^T x} = \lambda \frac{x^Tx}{x^T x} = \lambda. \]

瑞利熵有如下几个性质：

• R 的最大值就是 M 最大特征值，R 的最小值就是 M 最小特征值 ；
• x 的解，就是 M 对应的特征向量。

至于瑞利熵的更多性质，可参考：Rayleigh quotient 。

　　以上只是一般意义上的普通瑞利熵，还有一个广义瑞利熵（generalized Rayleigh quotient ），其定义为：\(R(M,D;x)=\frac{x^*Mx}{x^*Dx}\) ，即在分母上添加一个 D 矩阵相乘，其中 D 为 Hermite 正定矩阵 ，满足 \(D=D^*\)，普通瑞利熵是广义瑞利熵中 D 矩阵为单位矩阵时的情况。广义瑞利熵可以通过以下变换转换为普通瑞利熵： \[ \begin{equation} \begin{aligned} R(M,D;x) &= \frac{x^*Mx}{x^*Dx} \xlongequal{x=D^{-\frac{1}{2}}y} \frac{(D^{-\frac{1}{2}}y)^*M(D^{-\frac{1}{2}}y)}{(D^{-\frac{1}{2}}y)^*D(D^{-\frac{1}{2}}y)} \\ &= \frac{y^*(D^{-\frac{1}{2}})^*M(D^{-\frac{1}{2}}y)}{y^*(D^{-\frac{1}{2}})^*D(D^{-\frac{1}{2}}y)}=\frac{y^*D^{-\frac{1}{2}}MD^{-\frac{1}{2}}y}{y^*D^{-\frac{1}{2}}DD^{-\frac{1}{2}}y} \\ &= \frac{y^*(D^{-\frac{1}{2}}MD^{-\frac{1}{2}})y}{y^*y} \end{aligned} \end{equation} \]

只需要求出矩阵 \(D^{-\frac{1}{2}}MD^{-\frac{1}{2}}\) 的特征值和特征向量即可。

好了，这两个概念介绍完了，就可以真正介绍谱聚类了。

　　上面说了，谱聚类是一种基于图论的聚类方法，既然有图，则必有相应的邻接矩阵。设图 G 的顶点被聚类成两类，即将图 G 分割为子图 A 和 B，则所要断开的边的权值之和为代价函数（也叫损失函数），类似于“Graph Cuts”中的能量方程。割边 Cut(A,B) 的具体表示为：\(Cut(A,B)=\sum \limits_{i \in A,j \in B} w(i,j)\) 。

　　设图 \(G\) 中共有 \(n\) 个顶点，则需要构建一个 \(n \times n\) 的邻接矩阵 \(W\)，其相应的度矩阵为 \(D\)，对应的拉普拉斯矩阵为 \(L=D-W\)，令 \(p_i = \begin{cases} l_1 & i \in A \\ l_2 & i \in B\end{cases}\) ，则 \[ Cut(A,B)=\sum \limits_{i \in A,j \in B} w(i,j) = \frac{\sum \limits_{i=1}^n \sum \limits_{j=i}^n w(i,j) (p_i-p_j)^2}{(l_1-l_2)^2}= \frac{\sum \limits_{i=1}^n \sum \limits_{j=1}^n w(i,j) (p_i-p_j)^2}{2(l_1-l_2)^2} \]

当且仅当 \(i\) 和 \(j\) 不属于同一子图时，\((p_i-p_j)^2/(l_1-l_2)^2=1\)，否则 \((p_i-p_j)^2/(l_1-l_2)^2=0\)，（为什么采取这种计算方式，是因为在无法直接确定割边时，用这种计算方式能确保全部割边且只有割边会被加入权重之和），至于为什么等式最后还要除以 2 ，是因为等式最后的那种写法每条边会被遍历两次，每条割边权值会被计入两次，所以还要除以2。

而： \[ \begin{equation} \begin{aligned} & \sum \limits_{i=1}^n \sum \limits_{j=1}^n w(i,j) (p_i-p_j)^2 = \sum \limits_{i=1}^n \sum \limits_{j=1}^n w(i,j) (p_i^2-2p_ip_j+p_j^2) \\ &= \sum \limits_{i=1}^n \sum \limits_{j=1}^n w(i,j) (p_i^2) + \sum \limits_{i=1}^n \sum \limits_{j=1}^n w(i,j) (p_j^2) - \sum \limits_{i=1}^n \sum \limits_{j=1}^n w(i,j) (2p_ip_j) \\ &= \sum \limits_{i=1}^n p_i^2 (\sum \limits_{j=1}^n w(i,j)) + \sum \limits_{j=1}^n p_j^2 (\sum \limits_{i=1}^n w(i,j)) - 2\sum \limits_{i=1}^n \sum \limits_{j=1}^n p_iw(i,j) p_j \\ &= p^TDp+p^TDp-2p^TWp = 2p^T(D-W)p = 2p^TLp \end{aligned} \end{equation} \]

则：\(Cut(A,B)=\frac{p^TLp}{(l_1-l_2)^2}\) ，当 \(l_1=1,l_2=-1\) 时， \(\min Cut(A,B) = \min p^TLp \qquad s.t.\ p^Tp=n\) ，n 为图的顶点个数。由上可知，该最小割问题即是一个瑞利熵问题，只需求取 \(L\) 的特征值和特征向量。

　　对 \(L\) 的特征值进行从小到大排列（即取最小 k 个特征向量），若要分成 k 类，则需要取前 k 个特征值（除 0 以外）对应的特征向量，并归一化，将每一个特征向量按列排列构成一个 \(n \times k\) 的特征矩阵，对特征矩阵的行向量使用 k-means 或其它聚类算法，将 n 个行向量聚成 k 类，每一行都属于某一类，根据聚类结果为每个顶点分配相应的类标签，从而完成谱聚类。所以利用谱聚类求的解相当于是一个近似解，它将连续的 n 维问题离散化为 k 维问题，p 是一个 n 维的标签向量，标签值为 \(\{1,2,\cdots,k\}\) ，而 \(L\) 的特征向量中的元素并不是离散化的 \(\{1,2,\cdots,k\}\) ，无法直接用 \(L\) 的特征向量作为标签向量，所以需要将其离散化，对特征矩阵的行向量进行聚类，从而近似的生成标签向量；由于只取前 k 个特征向量，所以在对特征矩阵进行聚类时被聚类的 n 条数据只有 k 维，而本来 \(L\) 的特征向量至少有 n 个，即被聚类的 n 条数据至少有 n 维，所以从某种程度上，谱聚类同时也对数据进行了降维处理。

※注： 推荐使用 SVD 代替特征值和特征向量的求取。至于谱聚类的更多性质，可参考：Spectral clustering。

　　因为有时候简单的全局最小割，可能并不是最优割，所以需要对割做一个归一化，即 Normalized Cuts ，简称 NCuts。

图篇

　　同样，Shaun 还从图的构造开始，NCuts 所需要构造的图就是最普通的无向带权图，图的顶点由图像中像素点构成，相邻的像素点之间互相连接构成图的边。边的权值计算公式为： \[ w(i,j) = e^{\dfrac{-\|\mathbf{F}(i)-\mathbf{F}(j)\|_2^2}{\sigma_I}} * \begin{cases} e^{\dfrac{-\|\mathbf{X}(i)-\mathbf{X}(j)\|_2^2}{\sigma_X}} & \text{if } \|\mathbf{X}(i)-\mathbf{X}(j)\|_2 < r \\ 0 & \text{otherwise}. \end{cases} \] 　　其中 \(\mathbf{X}(·)\) 是指该顶点的空间位置向量，即图像中像素点的坐标； \(\mathbf{F}(·)\) 可指像素点的强度（灰度）值，颜色向量或纹理值；\(\|\mathbf{X}(i)-\mathbf{X}(j)\|_2\) 表示向量的「2-范数」，即欧氏距离。当 \(\mathbf{F}(·)\) 表示强度（灰度）值时，NCuts 分割的是灰度图；当 \(\mathbf{F}(·)\) 表示颜色向量（一般在 HSV 颜色空间，有 \((h,s,v)\) 三个颜色分量）时，NCuts 分割的是彩色图。对于这个权值的计算说人话就是：当两个像素点之间的距离大于一个人为指定的 \(r\) 时（其实也就用这个 \(r\) 判断到底是连接 4 邻域还是连接 8 邻域，一般不会连接 8 邻域之外的像素点），就不连接，此时权值设为 0 ；否则，则计算两像素点颜色向量的 RBF 核的值和两像素点坐标向量的 RBF 核的值，并取其乘积作为权值。

好了，Ncuts 的图的构成大致就是这样。接下来就是它的割法了。

割篇

　　NCuts 中定义割 \(Cut(A,B)=\sum \limits_{i \in A,j \in B} w(i,j)\) ，定义 \(assoc(A,V)=\sum\limits_{i \in A,t \in V}w(i,t)\) 为子图 A 内所有像素点连接的所有边权重之和，最终的 NCuts 目标函数如下： \[ Ncut(A,B)= \frac{cut(A,B)}{assoc(A,V)}+\frac{cut(A,B)}{assoc(B,V)} \] 即通过除以两个子图内所有像素点连接的所有边权值之和对割做了个归一化处理。

　　令 \(\mathbf{W}\) 为图的邻接矩阵， \(\mathbf{D}\) 为其对应的度矩阵，\(L=D-W\) 为其对应的拉普拉斯矩阵，令 \(S_1 = assoc(A,V) = \sum\limits_{i \in A}D_{ii}\)，\(S_2 = assoc(B,V) = \sum\limits_{i \in B}D_{ii}\)，则 \(S = S_1+S_2=\sum\limits_{i \in A}D_{ii}+\sum\limits_{i \in B}D_{ii}=\sum D_{ii}= \sum \limits_{i=1}^n\sum \limits_{j=1}^n w(i,j)\) ，则：\(NCut(A,B)=\frac{p^TLp}{(l_1-l_2)^2}*(\frac{1}{S_1}+\frac{1}{S_2})\) ，其中向量 \(p\) 为 \(N=|V|\) 维的标签向量， \(p_i = \begin{cases} l_1 & i \in A \\ l_2 & i \in B\end{cases}\) ，令 \(l_1 = \sqrt{\frac{S_2}{S_1S}},l_2=-\sqrt{\frac{S_1}{S_2S}}\) ，则 \(NCut(A,B)=p^TLp\) ，此时 \(p^TDp=\sum p_i^2D_{ii}=\sum\limits_{i \in A}l_1^2D_{ii}+\sum\limits_{i \in B}l_2^2D_{ii}=l_1^2S_1+l_2^2S_2=1\) ，则可化为 \(NCut(A,B)=\frac{p^TLp}{p^TDp}\) ，即 \(\min NCut(A,B) = \min p^TLp \qquad s.t.\ p^TDp=1\) ，该式即为一个广义瑞利熵，只需要求出矩阵 \(D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\) 的特征值和特征向量，按照谱聚类最后的聚类方式将顶点（像素点）聚成 k 类，从而完成图像的分割。而 NCuts 有个特殊的变换，具体如下： \[ \begin{equation} \begin{aligned} NCut(A,B) &=\frac{p^TLp}{p^TDp}\xlongequal{p=D^{-\frac{1}{2}}x} \frac{x^T(D^{-\frac{1}{2}}LD^{-\frac{1}{2}})x}{x^Tx} \\ &= \frac{x^T(D^{-\frac{1}{2}}(D-W)D^{-\frac{1}{2}})x}{x^Tx} \\ &= \frac{x^T(D^{-\frac{1}{2}}DD^{-\frac{1}{2}})x}{x^Tx} - \frac{x^T(D^{-\frac{1}{2}}WD^{-\frac{1}{2}})x}{x^Tx} \\ &= I - \frac{x^T(D^{-\frac{1}{2}}WD^{-\frac{1}{2}})x}{x^Tx} \end{aligned} \end{equation} \] 使用该变换可得出：\(\min NCut(A,B) = \max x^T(D^{-\frac{1}{2}}WD^{-\frac{1}{2}})x \qquad s.t.\ x^Tx=1\) ，这样可不求出拉普拉斯矩阵，直接求出 \(D^{-\frac{1}{2}}WD^{-\frac{1}{2}}\) 的特征值和特征矩阵即可，而此时在谱聚类最后聚类的时候要将其特征值从大到小排列（即取最大 k 个特征向量），取前 k 个特征值对应的特征向量构造特征矩阵进行聚类。

附录

　　Ratio Cuts（RCuts） 和 NCuts 的目标函数差不多，两者间的差异就是：RCuts 是除以子图内顶点的个数；NCuts 是除以子图内所有顶点的边权值之和；最后变换完之后 RCuts 是个普通瑞利熵，而 NCuts 是个广义瑞利熵。具体的 RCuts 割法等以后有机会用到再写吧，毕竟子图顶点个数多不代表所占权重就大，而且在割时一般是基于权重的，所以一般而言 NCuts 的结果要比 RCuts 的结果要好。

总结

　　由上文中应该可以看出 NCuts 与 Graph Cuts 需要构造的图是不一样，所使用的能量方程从形式上看也是完全不一样的（虽然本质上都是求“最小割”），其构成的图主要差别在于 Graph Cuts 多了 S 和 T 两个顶点，而这两个顶点由交互式获取，NCuts 不需要交互式，因此也没有这两个顶点，Ncuts 构造的图就相当于只由 Graph Cuts 的普通顶点和边界项 n-links 构成图，因此 Ncuts 没有 Graph Cuts 所谓的区域项 t-links ，也不需要求区域项 t-links 的权值。而这两种方法边界项 n-links 的权值求法都是差不多的，都是用 （高斯）RBF 核函数进行相似性度量，即 \(w_{\{i,j\}} \propto exp\left(-\frac{(I_i-I_j)^2}{2\sigma^2}\right)\) 。

后记

　　后面查阅资料发现图割其实还有好几个方向（井底之蛙了o(╯□╰)o），等有机会把用图割做超像素分割的那篇论文看一下吧 😜 。

　　5 月份的时候自己抽空实现了一下该算法，发现效果很糟糕，分割效果很不理想，当然不排除 Shaun 代码有 BUG 的原因，或者是还有一些步骤或 trick 漏掉了 ╮(╯▽╰)╭。而且不管是用 svds 还是 eigs 其分割结果都是随机的，只能保证邻域内像素点大概在一起，但具体谁和谁在一起这就是随机的了，这导致每次运行程序都可能有不同的分割结果 _(´ཀ`」 ∠)_ ，后面发现分割结果随机应该是 k-means 的锅（与 svd 和 eig 无关），原因是因为 k-means 每次初始化 k 个种子点时都是随机的，这自然会导致每次分割结果不完全一致 o(╯□╰)o。

参考资料

[1] 【聚类算法】谱聚类(Spectral Clustering)

[2] 谱聚类算法(Spectral Clustering)

[3] 拉普拉斯矩阵（Laplace Matrix）与瑞利熵（Rayleigh quotient）（http://www.cnblogs.com/xingshansi/category/958994.html）

[4] Normalized cuts and image segmentation 简单实现

[5] 谱聚类（spectral clustering）原理总结 （http://www.cnblogs.com/pinard/category/894692.html）

前言

　　以后可能需要用图割算法做一些事情，所以就简单阅读了一下图割算法中最基础的一篇论文，Boykov Y Y, Jolly M P. Interactive graph cuts for optimal boundary & region segmentation of objects in ND images. Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on. IEEE, 2001, 1: 105-112. 。

图篇

　　图割算法（Graph Cuts），顾名思义，是基于图的一种图像分割方法，这里的图既是指数据结构中的图结构也是指数学中的图论，毕竟数据结构中的图结构也来自于数学中图论。既然是图，必然离不开图的构建，论文中图的构建如下，可以简称为 S/T 图：

和普通的无向图 \(G=(V,E)\) 一样，该图也是由顶点集合 \(V\) 和边集合 \(E\) 构成，不一样的是，该图有两种顶点和两种边：

1. 第一种顶点是普通顶点。由图像中各像素点组成，每个顶点对应于图像中每个像素点。每两个邻域顶点，对应于图像中每相邻两个像素点（对2维图像来说，是8邻域；对3维图像来说，是26邻域），的连接就是一条边，这种边叫做 n-links (neighborhood links)。
2. 第二种顶点是两个终端顶点，代表目标（object）的 source terminal（简称 S）和代表背景（background）的 sink terminal（简称 T），每个终端顶点都与所有普通顶点相连，这种相连构成的边叫做 t-links (terminal links)。

　　设图像 \(P\) 中每个像素点为 \(p\)，则 \(p \in P\)，目标终端顶点 \(S\)，背景终端顶点 \(T\) ，则构建的图 \(G\) 中顶点集合可表示为：\(V = P \cup \{S,T\}\) ；每个 \(p\) 都有两种 t-links 边，分别为 \(\{p,S\}\) 和 \(\{p,T\}\) ，每个 \(p\) 与其邻域内像素 \(q\) 构成的 n-links 边为 \(\{p,q\}\) ，设 \(N\) 代表 n-links 边集合，即邻域边集合，则 \(\{p,q\} \in N\) ，则构建的图 \(G\) 中边集合可表示为：\(E = N \bigcup\limits_{p \in P} \{\{p,S\},\{p,T\}\}\) 。

因为这构建的是一个无向带权图，所以还需要设定边的权值，论文中边的权值设定如下：

• 其中集合 \(O\) 代表确定为目标的像素点的集合，即在交互时手动标注为目标的像素点；
• 集合 \(B\) 代表确定为背景的像素点的集合，即在交互时手动标注为背景的像素点；
• \(B_{\{p,q\}}\) 可以表示 {p,q} 不连续的惩罚因子，其正比于一个指数函数，具体为：\(B_{\{p,q\}} \propto exp\left(-\frac{(I_p-I_q)^2}{2\sigma^2}\right) \cdot \frac{1}{dist(p,q)}\) ，其中 \(I_p\) 和 \(I_q\) 代表像素 \(p\) 和像素 \(q\) 的像素值，\(dist(p,q)\) 代表其两像素点之间的距离。从 \(B_{\{p,q\}}\) 对应的函数中可以看出当两像素点之间的差异越大时，其权值越小；两像素点之间距离越大时，权值越小（这里对于二维图像来说，一般只考虑周围 8 邻域内像素点，因此可以简单认为相邻两像素点之间距离为 1）。
• \(R_p("bkg")\) 和 \(R_p("obj")\) 分别是指像素 p 分配给背景和前景目标的惩罚因子，该惩罚因子与像素 p 属于前景目标的概率 \(Pr(I|O)\) 和背景的概率 \(Pr(I|B)\) 有关，一般取概率的负对数值，具体如下：\(R_p(“obj”) = −lnPr(I_p|O)\) 和 \(R_p(“bkg”) = −lnPr(I_p|B)\) 。至于概率的计算方法可以用简单的直方图概率模型，因为 \(O\) 和 \(B\) 为手动标注的确定的前景目标和背景的像素点集合，因此可以分别统计其灰度直方图，再对直方图频数进行归一化得到分布概率直方图，将像素 p 与 背景分布概率直方图和前景目标概率分布直方图进行对比，即可得到其属于背景的概率和属于前景目标的概率（当然更好的一种计算前景和背景概率的方法是用高斯混合模型）。
• \(K\) 表示整个无向带权图中最大的权值，具体计算方法如下：\(K=1+\max\limits_{p \in P} \sum \limits_{q:\{p,q\} \in N} B_{\{p,q\}}\) ，即取图像中像素点邻域边权值之和的最大值再加 1 （对于二维图像而言，邻域边权值之和是指 8 邻域边权值之和，图像中每个像素点都有其邻域边权值之和，取所有像素点中的最大值），至于为什么要令 K 为整个无向带权图中权值最大值？请详见下文。
• 至于其中的参数 \(\lambda\) 和 \(\sigma\) 论文中没有明确指定，在初始计算时可以将其置为 1，随后再慢慢调整。

至此，整个 Graph Cuts 算法中关于图的构建已经完全确定，接下来就是割（cut）的算法了。

割篇

　　割（cut）是构建的无向带权图中边集合 \(E\) 的一个子集 \(C\)，即割 \(C \subset E\) ，该 cut 的 代价（cost）可表示为：\(|C|=\sum \limits_{e \in C} W_e\)，即该割边集合的所有边权值之和。

如果一个割，其包含的所有边的权值之和最小，那么这个割就称为最小割，也就是图割的结果。在图分割里，是要求两个终端顶点被分离开的，即最小割把图的顶点划分为两个不相交的子集 \(S\) 和 \(T\) ，其中 \(s∈S\)，\(t∈T\)，\(T=V/S\)。事实上，这两个子集对应于图像的前景像素集和背景像素集，也就相当于完成了图像分割。

　　割相关的算法有很多，eg：Max-flow/Min-cut、GrabCut、One cut、 Normalized cut、Ratio cut 等等，但是其最关键的地方在于能量方程（或称 代价函数，损失函数）的优化，能量优化的目的在于最小化能量函数，而最小化能量函数时取得割就是最小割，即图割的结果。论文中能量方程的定义如下： \[ E(A)= \lambda \cdot R(A)+B(A) \] 其中： \[ R(A)= \sum_{p \in P} R_p(A_p) \\ B(A)= \sum_{\{p,q\} \in N} B_{\{p,q\}} \cdot \delta(A_p,A_q) \\ 其中　\delta(A_p,A_q) = \begin{cases} 1 & \text{if } A_p \neq A_q \\ 0 & \text{otherwise}. \end{cases} \]

• 其中令 \(A=(A_1,\cdots,A_p,\cdots,A_{|P|})\) 为二值向量，每个 \(A_p\) 可赋值为 “obj”（可用 1 表示前景） 或 “bkg”（可用 0 表示背景）；
• \(R(A)\) 表示区域项，即上文中的两种 t-links 边相连的图像像素点权值，代表像素点分配给 “obj” 或 “bkg” 的惩罚项，对应于 \(R_p("obj")\) 和 \(R_p("bkg")\) ，求和后即可得到 \(R(A)\) 。当像素点 p 属于前景目标的概率 \(Pr(I|O)\) 大于背景的概率 \(Pr(I|B)\) 时，由上文 \(R_p(A_p) = −lnPr(I_p|A_p)\) 可知，此时 \(R_p("obj")\) 小于 \(R_p("bkg")\) ，即当像素 p 更有可能属于目标时，将 p 归类为目标就会使能量 \(R(A)\) 小，也因此要取概率的负对数值，由此，如果所有像素点都能正确划分为前景和背景，则总能量会达到最小。当像素点 p 已经人为手动标注为确定的前景目标时，这时其与顶点 \(S\) 相连的边的权值为 K，为整个无向带权图中最大的权值，即能量也最大，此时就不可能被分割，这就是为什么要令 K 为整个无向带权图中权值最大值，而其与顶点 \(T\) 相连的权值为 0 ，能量也为 0，此时一定会被分割。
• \(B(A)\) 表示边界项，即上文中 n-links 边的权值，代表邻域像素点 \({p,q}\) 不连续的惩罚，当其差异越大时， \(B(A)\) 越趋近于 0，即当邻域像素点差异越大时，由上文 \(B_{\{p,q\}} \propto exp\left(-\frac{(I_p-I_q)^2}{2\sigma^2}\right) \cdot \frac{1}{dist(p,q)}\) 可知其权值越小，能量 \(B(A)\) 也越小，则越应该被分割。
• 参数 \(\lambda\) 用来表示区域项和边界项的重要性，初始计算时同样可以将其置为 1。
• 至于 \(\delta(A_p,A_q)\) 的个人理解为：当邻域像素点 \(p,q\) 被分配的二值变量不同时，即一个是前景另一个是背景，这时在进行能量计算时需要考虑连接亮点的边 \(\{p,q\}\) 的权值，否则可以不考虑其权值。

最后，本文割的具体实施是采用基于「最大流/最小割」算法进行的，而「最大流/最小割」算法针对的是有向图，所以需要把本文 S/T 图的每条无向边都转化为一去一回的两条有向边。

附录

　　该论文还有一个有意思的地方就是其证明了能量函数 E(A) 的值只与割 \(C\) 有关，最小割与最小化能量函数对应。证明过程如下：

由上文可知，对于图像中每个像素点，割 \(C\) 切断且仅切断一条 t-links 边，即要么切断 \(\{p,S\}\) 边，要么切断 \(\{p,T\}\) 边，毕竟一个像素点不可能同时属于前景和背景，也不可能既不属于前景也不属于背景；不属于同一终端顶点相连的 n-links 边也会被割 \(C\) 切断，因为如果不断开，则整个图还是相连的，而如果属于同一终端顶点相连的 n-links 边不应该被割 \(C\) 切断，否则，该割就不是最小割。

对于任意割 \(C\) ，可定义其对应的图像分割结果向量 \(A(C)\) ，如下： \[ A_p(C) = \begin{cases} "obj" & \text{if } \{p,T\} \in C \\ "bkg" & \text{if } \{p,S\} \in C \end{cases} \] 因此当 C 确定之后，分割结果 A 也就确定了。

利用上文给出的边的权值计算方法结合定义的 A 可得出割的代价（cost）： \[ \begin{align} |C| &= \sum_{p \notin O \cup B} \lambda \cdot R_p(A_p(C)) + \sum_{p \in O} \lambda \cdot R_p(A_p(C)) + \sum_{p \in B} \lambda \cdot R_p(A_p(C)) + \sum_{\{p.q\} \in N} B_{\{p,q\}} \cdot \delta((A_p(C)),A_q(C))) \\ &= \sum_{p \notin O \cup B} \lambda \cdot R_p(A_p(C)) +0 + 0 + \sum_{\{p.q\} \in N} B_{\{p,q\}} \cdot \delta((A_p(C)),A_q(C))) \end{align} \] 这里是因为 \(O \cap B = \emptyset\) ，而且如果确定像素点 p 属于前景或背景，则其割边的权值必为 0，相应的代价也为 0，eg：设 p 确定为前景，则必定断开 {p,T} 边，而 {p,T} 边的权值为 0。

又因为：\(E(A) = \lambda \cdot R(A) + B(A)\) ，则： \[ \begin{align} E(A(C)) &= \lambda \cdot R(A(C)) + B(A(C)) \\ &= \sum_{p \in P} \lambda \cdot R_p(A_p(C)) + \sum_{\{p.q\} \in N} B_{\{p,q\}} \cdot \delta((A_p(C)),A_q(C))) \\ &= \sum_{p \notin O \cup B} \lambda \cdot R_p(A_p(C)) + \sum_{p \in O} \lambda \cdot R_p("obj") + \sum_{p \in B} \lambda \cdot R_p("bkg") + \sum_{\{p.q\} \in N} B_{\{p,q\}} \cdot \delta((A_p(C)),A_q(C))) \end{align} \] 所以：\(|C| = E(A(C)) - \sum \limits_{p \in O} \lambda \cdot R_p("obj") - \sum \limits_{p \in B} \lambda \cdot R_p("bkg")\)

又因为对于标注确定的前景和背景，任意割 C 的 \(\sum \limits_{p \in O} \lambda \cdot R_p("obj")\) 和 \(\sum \limits_{p \in B} \lambda \cdot R_p("bkg")\) 都是完全确定不变的，可以令其为 const，则 \(E(A) = |C| + const\) ，当 \(C\) 取最小时，对应的 \(E(A)\) 也最小，即当割最小时，能量函数也最小。

后记

　　虽说关于 Graph Cuts 网上已经有了无数篇博客对其进行描述，但其中或多或少感觉还是有些令人困惑的地方，于是写下本文将那些个人感觉有些困惑的地方重新梳理一下，再改变一下原论文的行文思路，个人感觉更好理解一点，不然一上来就是神马能量方程，简直一脸懵逼 (･ัω･ั) 。

参考资料

[1] Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D ImageS

[2] Graph Cuts

[3] 图像分割之（二）Graph Cut（图割）

[4] 图像分割算法——Graph Cuts

[5] Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images 阅读笔记

前言

　　static 是 C++ 中很常用的一个关键字，它的用法也很多，时常会将其弄混，索性做个小结，以免以后忘记了或者继续弄混 (｡･ω･｡)。

预备篇

　　首先要了解程序中数据的存储形式，一般而言数据的存储形式有三种：

• 栈区（stack）—— 由编译器自动分配释放，一般用来存放函数的参数值，局部变量的值等；
• 堆区（heap）—— 由程序员分配释放，对应于对象的 new 或 malloc 和 delete 或 free，若程序员忘记释放，则在程序完全退出之后由操作系统回收；
• 静态存储区（static）—— 在编译时由编译器分配，在程序完全退出时由操作系统回收，一般用来存放全局变量和 static 变量。

　　一般¹声明的变量默认（如果变量类型，eg: int, double, ... 等，前不加 static 或其它关键字）都是 auto ²的，其一般存放在栈区，生存周期就只在包围其的 { } 内，在包围其的 { } 外就无法使用该变量。而 static 存放在静态存储区，其生存周期是全局的，它要等整个程序完全退出时才会销毁，在程序运行过程中，每次调用 static 变量都保持上一次调用结束后的值。

类中篇

静态成员变量

　　类中的静态成员变量被该类的所有实例共享，也可以不通过类的实例使用，在使用时首先需要对其初始化，也必须对其进行初始化，因为类中的静态成员变量只是声明，而且，类中的静态成员变量和普通静态变量一样是在程序初始化的时候分配的，在程序完全退出时由操作系统回收。具体用法如下：

1
2
3
4
5
6
7
8

class Test
{
private:
    static int s_value;	// 注意，这里不能初始化！因为其不属于类对象，只属于类作用域，独立于该类的任何实例
};

// 在cpp中或类定义体外必须对它进行定义和初始化，因为在程序编译时首先执行的就是对其初始化并分配内存：
int Test::s_value = 0;	// 注意，这里没有static的修饰！

总而言之就是：类中的静态成员变量可以简单理解为一个名为 Test::s_value 的全局变量，被所有该类的实例共用，但独立于该类的任何实例，只属于该类作用域，在类的定义中能且只能被声明，不能在类定义体中进行初始化，必须要在类定义体外被定义和初始化。

静态成员函数

　　类中的静态成员函数和类中的静态成员变量有点类似，其在实现时不需要再加 static 修饰，同样能被该类的所有实例复用，同样只属于类作用域中的全局函数，同样不需要类的实例即可调用。类中的静态成员函数不能访问类的普通成员变量，只能访问类的静态成员变量（可以参考 C++静态成员函数访问非静态成员的几种方法 中的小 trick 访问普通成员变量，但非特殊情况不建议这么做）。具体用法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Test
{  
private:
    static void func(int i);
    
    // 静态成员函数调用非静态成员变量方法
    static void staticTest(Test *t)
    {
        t->value += 1;
    }
private:
	int value;
};

// 在cpp中可以不通过类的实例进行调用：
void Test::func(int);

总而言之就是：类中的静态成员函数可以简单理解为一个名为 Test::func(int) 的全局函数，能被该类的所有实例复用，但独立于该类的任何实例，只属于该类作用域，可以不通过类的实例进行调用，也可以像普通成员函数一样通过类的实例进行调用。

特定范围篇

　　为了使全局变量或函数只在特定 cpp 文件中起作用，需要在 cpp 文件中相应变量或函数前添加static 修饰，如下表：

• 如果在头文件中声明 static 全局变量，则在包含该头文件的每个 .cpp 文件中都会生成一个独立的同名变量，而这种写法没有任何意义；如果在 .cpp 文件中不使用 static 声明全局变量，则该全局变量可能会被其它 .cpp 文件共享，也可能不会，造成该变量的不确定性；所以如果该全局变量要被所有 .cpp 文件共享，则需要在头文件中声明 extern 全局变量（eg：extern int g_value; // 注意，不要初始化值！），再在某个 .cpp 文件中单独进行定义和初始化（仅一次）（eg：int g_value = 0; // 不要extern修饰！），如此即可在每个 .cpp 文件中共享该全局变量；而若只想在单个 .cpp 文件中使用全局变量，则需要在该 .cpp 文件中全局范围类声明和定义 static int g_value = 0;，如此可保证该变量能且只能被该 .cpp 文件使用。
• 如果在 .cpp 文件中不使用 static 声明全局函数，则该全局函数可能会被其它 .cpp 文件共享，也可能不会，这样在别的 .cpp 文件调用同名函数时可能会出现问题；而在头文件中使用 static 声明全局函数同样没有任何意义；所以如果要被多个 .cpp 文件复用，就将其声明移到头文件中，且不需要 static 修饰，而若只想在特定 .cpp 文件中使用该全局函数，则需要在声明时添加 static 修饰。

最后，若是在 .hpp 文件中，则需要去除全局对象，将全局函数封装为类的静态方法。

　　PS：若在函数中使用 static 修饰变量，则该函数无法做到线程安全，在程序运行过程中，每次调用该函数，函数内的 static 变量都将保持上一次调用结束后的值，所以在函数中慎用 static 变量，除非需要这个特性。

后记

　　写这篇文章的初衷在于时常需要 static 时老是忘记或弄混它的用法，不得不去网上查找，虽说网上的相关资料也有很多，但在找的时候还是有点麻烦，毕竟有很多不是自己需要的，而且自己总结一下对其理解又更深一些，下次要用时也能马上找到自己所需。

参考资料

[1] c/c++ static 用法总结（三版本合一）

[2] C++中static的用法总结

[3] C++ 类中的static成员的初始化和特点

[4] C++静态成员函数访问非静态成员的几种方法

前言

　　本文预示着 Shaun 开始着手准备找工作的事了，初步计划是先把『剑指Offer』上的题先做一遍，对照着 牛客网 上的题进行测试，尽量争取先把书上的题都能 AC 。一般定义的斐波那契数列数列为：0,1,1,2,3,5,8……（对应 \(F(0)=0, F(1)=1, F(2)=1, \cdots \cdots\)），用数学公式表示即为：\(F(n)=F(n-1)+F(n-2)\)。以下代码均用 C++ 实现，且均通过牛客的测试。

循环写法

1
2
3
4
5
6
7
8
9
10
11

int fibonacci_loop(const unsigned int &n)
{
	int fn = 0, f1 = 0, f2 = 1;
	for (int i = 0; i < n; i++)
	{
		fn = f1 + f2;
		f2 = f1;
		f1 = fn;
	}
	return fn;
}

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int fibonacci_recursive(const unsigned int &n)
{
	if (n == 0)
	{
		return 0;
	}
	else if (n == 1 || n == 2)
	{
		return 1;
	} 
	else
	{
		return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
	}
}

　　※注：这里 Shaun 在牛客上进行测试的时候，如果把 || n == 2 去掉的话，就没法通过，可见多递归一次花费的时间并不是线性增长的。

尾递归写法

　　说来惭愧，这个概念还是在一个小学弟那里得知的，后面才逐渐了解并学会使用。

　　尾递归，简而言之就是最后会且仅会调用函数本身，递归调用函数之后没有其它的语句需要执行。就像上面的递归，它在递归调用之后还会执行加法运算，而尾递归在执行递归调用之后就没有其它的运算了。

1
2
3
4
5
6
7
8
9
10
11

int fibonacci_tailRecursive(unsigned int n, unsigned int f1 = 1, unsigned int fn = 0)
{
	if (n == 0)
	{
		return fn;
	}
	else
	{
		return fibonacci_tailRecursive(n - 1, fn, fn + f1);
	}
}

总结

　　循环和尾递归花费的时间和空间都差不多，都要比普通的递归要小，普通的递归优势在于便于理解，代码好写，在不强调性能的前提下，用递归写法的代码可读性可能要好些。

参考资料

[1] 递归与尾递归总结（http://www.cnblogs.com/Anker/category/436371.html）