题目背景

来源：https://www.gitlink.org.cn/thusaa/thuwc2018。

2018 清华大学信息学冬季体验营（THUWC 2018）D2T3。$\texttt{3s,0.5G}$。

---

计算机视觉（Computer Vision）中，一个局部特征（local feature）被定义为“一个与其直接邻域有显著不同的小区域”，其中“显著不同”可以是许多可能，如亮度、颜色、纹理等等。足够好的特征可以让我们进一步获取图片中除颜色以外的更多（语义）信息。例如，在卷积神经网络（Convolutional Neural Network）中，特征是通过卷积核来提取的，而其层级结构使得高层的信息能通过低层信息结合来生成。一个用于人脸识别的网络中可以存在感知诸如眼、嘴、耳、发、皮肤的不同神经元，并通过卷积连接来激励感知人脸的单元。

题目描述

在本问题中，我们将会研究一种最基本的局部特征——"角点"。从数学上说，角点可以被认为是两条边相交的点；边在图片中，可以认为是其梯度（导数）图像上的光滑连续段（如果你拿黑笔在白纸上画一条直线，由于黑线是一个有宽度的区域，所以实际上是会有两条非常接近的边）。基于这种考虑，学术界已经提出了若干基于 SUSAN、Harris、CSS 等，并有一定表现的角点算法。我们提供了描述 SUSAN、Harris、CSS 算法的一些阅读材料，而你的任务是则是基于我们给出的资料，选取适合自己的算法并完成对应的实现和优化。

注意在实际图片中，由于存在像素离散、色彩渐变、噪声、失真等等因素，很少会有遵循良定义的边存在，因此按某种数学方法找到的这些特征点，从人的角度而言并不一定是角点，或者说会有一定的偏差。但在具体运用上，虽然这些检测点并非角点，但它们在局部上通常依然有足够的特征，所以依然被广泛应用。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $w$、$h$，表示图片的宽度和高度。保证 $w \le 1280$，$h \le 1280$。

接下来 $h\times w$ 行，每行包含 $3$ 个非负整数，描述一个像素。其中这些行中的第 $(i-1) \times w + j$ 行的三个数表示图片第 $i$ 行，第 $j$ 列的像素的 RGB，即红（red）、绿（green）、蓝（blue）三通道的数值。整数的范围在 $[0, 255]$ 中。

输出格式

输出到标准输出。

第一行一个整数 $k$，表示检测到的角点数量。

接下来 $k$ 行，每行两个非负整数 $x$、$y$，描述一个角点的坐标。注意：坐标中 $x$ 是横坐标，即宽度方向；$y$ 是纵坐标，即高度方向。图像左上角的像素 （第 $1$ 行第 $1$ 列）的坐标规定为 $(0, 0)$。

见附件压缩包中的 1~10.in。

见附件压缩包中的 1~10.ans。

提示

样例 $1$ 解释

这组样例的图片和其参考的检测结果如下左图和右图。

数据和评分方法

测试数据一共 $20$ 张图片，每张图片就是一个测试点。另外有 $10$ 张图片已经作为你的参考用例和预测试数据。注意：本题的预测试数据与样例完全相同，且预测试数据的评测结果与最终评测结果没有关系。

我们使用 CSS + Harris(refine) 的结果作为参考算法，并将在参考算法上人工标注的结果作为参考答案。

在评价你的角点是否正确输出时，我们会对你输出的角点和答案的角点进行二分图最大匹配。其中如果一对点对 $a$，$b$ 满足 $a$ 在以 $b$ 为中心的 $5 \times 5$ 范围以内，那么我们认为这个角点对是可匹配的。如果一个你输出的角点在最大匹配中，那么我们就认为这个角点是正确的。

每个测试点的得分比例用 $F_1$ 表示，它的具体定义为

$$F_1 = \frac{2\mathit{TP}}{2\mathit{TP}+\mathit{FP}+\mathit{FN}} $$

其中 $\mathit{TP}$（true positive）表示是正确输出的角点数量（即最大匹配数），$\mathit{FP}$（false positive）表示你输出的点中错误的角点数量，$\mathit{FN}$（false negative）表示正确的角点中没有被你的角点匹配的数量。

对 $F_1$ 的更进一步解释为：你输出的点中，正确的比例 $\frac{\mathit{TP}}{\mathit{TP}+\mathit{FP}}$ 叫做“准确率”；应该输出的点中，被你输出的比例 $\frac{\mathit{TP}}{\mathit{TP}+\mathit{FN}}$ 叫做“召回率”。$F_1$ 是准确率和召回率的调和平均数。

我们选取的图片会保证提供材料中的算法在特定的优化下都会有较好的表现。在给定的测试图片下，参考算法对角点的 $F_1$ 检测率为 $90\%\sim 100\%$ 左右。

如何完成本题

下发文件除参考用例外，还有两类文件：描述参考算法的文档和其中一部分实现、一些工具。这些材料你可以任意使用，包括阅读并实现、直接使用部分代码、使用它们辅助你实现或调试等。你也可以不使用它们，完全自己完成本题。

我们推荐你实现我们给出材料中三个算法中的一个或者两个，并在此基础上尝试进行自己的调整或魔改。三种算法的实现难度和效果从低到高分别为：SUSAN（或它的一种实现方式FAST），Harris，CSS。

工具中包括：输入和PNG格式图片的转换工具，输出结果的可视化工具。

下发文件的具体使用方法，以及文档的导读请阅读文件中的 README.pdf。

最后请注意：如果你需要用到下发文件中的代码，你应当将其直接复制到你提交的代码中，而不应该使用诸如 #include 的方法尝试包含它。你只能提交一个文件，且测试时无法读取到给你的这些文件。