2013B读论文笔记
问题描述
拼接碎纸片成为完整的纸片，问题难度循序渐进，分为三个 - 一张写有汉字的纸纵切成19条，要求复原 - 一张写有汉字的纸，一张写有英文的纸分别横纵切为1119个块，要求分别复原 - 一张双面写有汉字的纸，横纵切为1119个块，要求区分开正反面复原 可以人工干预，各个片(条)没有旋转，边缘信息保留较好。
处理思路
Q1
- step1 将19个条建立对应的灰度值矩阵，（考虑）转化为0,1矩阵
- step2 找到每个矩阵对应的最左边和最右边向量，依次与其他矩阵的最左最右向量遍历比较，定义一个量描述差异度 采用曼哈顿距离，注意：最左侧碎片判断为左留白最多者 δ(n, k) = ∑|gn, R − gk, L|
Q2
step1 先行后列的方法，因为每个碎片竖向距离更大，蕴含信息更多。考虑采用聚类的方法聚类出十一个类别（行），比如使用k-means算法。自然地我们需要选取进行聚类的特征，对汉字来说，基准线是一个很好的选择，因为汉字排列是公正的，以每一条基准线开始的位置作为特征进行聚类可以方便的得到结果。对于英文，基准线方法较为困难，考虑双基准线的方法即可
step2 每一行的内部碎片进行匹配时，边缘信息量较少，需要更优的距离函数描述差异。采用斯皮尔曼相关系数。
斯皮尔曼秩相关系数(The Spearman’s rank coefficient of correlation)，简称斯皮尔曼相关系数，是秩相关(rank correlation)的一种非参数度量(nonparametric measure)。得名于英国统计学家Charles Spearman，通常记为希腊字母‘ρ’ (rho)( often called Spearman’s rho)或者 。在讨论斯皮尔曼相关系数之前，首先要理解皮尔逊相关(Pearson’s correlation)，斯皮尔曼相关可以看作是皮尔逊相关的非参数版本（nonparametric version）。皮尔逊相关是关于两个随机变量之间的线性关系强度的统计度量(statistical measure)，而斯皮尔曼相关考察的是两者单调关系（monotonic relationship）的强度，通俗地说就是两者在变大或变小的趋势上多大程度上保持步调一致，哪怕没有保持比例关系。计算皮尔逊相关系数时使用的是数据样本值本身，而计算斯皮尔曼相关系数使用的是数据样本排位位次值（有时候数据本身就是位次值，有时候数据本身不是位次值，则在计算斯皮尔曼相关系数之前要先计算位次值）。
这里”非参数”有两层含义。首先，当X和Y的关系是由任意单调函数描述的，则它们是完全皮尔逊相关的。与此相应的，皮尔逊相关系数只能给出由线性方程描述的X和Y的相关性。其次，斯皮尔曼不需要先验知识(也就是说，除了数据本身不需要知道其它参数，比如说关于数据的分布的先验信息)便可以准确获取X和Y的采样概率分布之间的相关性。
$$\rho=\frac{\frac1n\sum_{i=1}^n\left(R(x_i)-\overline{R(x)})\cdot(R(y_i)-\overline{R(y)}\right)}{\sqrt{\left(\frac1n\sum_{i=1}^n\left(R(x_i)-\overline{R(x)}\right)^2\right)\cdot\left(\frac1n\sum_{i=1}^n\left(R(y_i)-\overline{R(y)}\right)^2\right)}}$$
## Q3