Reproduce PersonLab (2)

Bilinear interpolation kernel + Hough voting + Greedy Algorithm

个人认为： - PersonLab中最给人启发的是：构造 geometric embedding: short-range offsets, mid-range offsets and long-range offsets 几何信息来表示人体姿态, 以此监督神经网络的预测，并根据预测结果，施以贪婪算法，关联出所有人的姿态和分割区域。

• PersonLab中最值得琢磨的数学部分是：如何将表示keypoints大致位置的heatmaps和short-offsets maps通过双线性插值核，然后进行Hough Vote得到精确位置的Hough Score Maps的过程。

后者是我复现过程中遇到的一个难题。其实构造Hough Score maps在Google的上一篇论文 G-RMI 中就出现了，然而因为G-RMI没有开源的代码，所以我对其提到的双线性插值核函数\(G(\cdot)\)的理解仍然还是很模糊。另外，如果按照论文公式给出的Hough Voting公式，去遍历图像的每一个像素位置进行计算的话，计算的时间复杂度会很高，所以，作者一定有什么巧妙的方式可以处理它，可是PersonLab也没有开源。

后来我发现，github上有一个KerasPersonLab的实现，论文的所有细节都几乎实现了，所以来看看他的关于构造Hough Score Maps的。

不禁佩服这个项目的开发者，为什么他们就可以有这个能力把论文中没有提到的细节完美地实现出来，这一定是他们的功底比我强很多，或者他们知道了一些我不知道的先验知识。对两人的了解后，我发现他们是Octi公司的两位算法工程师, 我的猜测是开发APP需要将PersonLab的算法移植到手机上面，所以激发了两个人完成了实现，PersonLab的ArXiv发布时间是2018年三月底，这个项目的发布时间是2018年5月份，真的是厉害了。GitHub上其他的Personlab实现版本都是在此之后，不少repo借鉴了他们的这个项目。

关于构造Hough Score Map 有这样的一段代码：

def accumulate_votes(votes, shape):
    xs = votes[:,0]
    ys = votes[:,1]
    ps = votes[:,2]
    tl = [np.floor(ys).astype('int32'), np.floor(xs).astype('int32')]
    tr = [np.floor(ys).astype('int32'), np.ceil(xs).astype('int32')]
    bl = [np.ceil(ys).astype('int32'), np.floor(xs).astype('int32')]
    br = [np.ceil(ys).astype('int32'), np.ceil(xs).astype('int32')]
    dx = xs - tl[1]
    dy = ys - tl[0]
    tl_vals = ps*(1.-dx)*(1.-dy)
    tr_vals = ps*dx*(1.-dy)
    bl_vals = ps*dy*(1.-dx)
    br_vals = ps*dy*dx
    data = np.concatenate([tl_vals, tr_vals, bl_vals, br_vals])
    I = np.concatenate([tl[0], tr[0], bl[0], br[0]])
    J = np.concatenate([tl[1], tr[1], bl[1], br[1]])
    good_inds = np.logical_and(I >= 0, I < shape[0])
    good_inds = np.logical_and(good_inds, np.logical_and(J >= 0, J < shape[1]))
    heatmap = np.asarray(coo_matrix( (data[good_inds], (I[good_inds],J[good_inds])), shape=shape ).todense())
    return heatmap

当我刚看到这些的时候是无法理解的，我认为这里面有着论文Hough voting最核心的部分。我想Accumulate——vote的出现一定和Hough Transform有一定的关联，另外，为什么会出现np.ceil和np.floor?这个tl_vals = ps*(1.-dx)*(1.-dy)又是什么鬼？似乎和双线性有着一点点的联系。我要慢慢摸清楚，顺藤摸瓜。

Hough Transform

回顾一下最经典的Hough transform 算法，那就以Hough Line Transform 为例子。OpenCV关于Hough Line Transform，有一个比较好的解释文档.

我想简洁地概括一下Hough Line Transform：

在二维数据空间坐标中，线其上的点，\((x,y)\)的满足 \(y = mx+c\)，一条直线就确定了一个唯一的参数坐标 \((m,c)\)

换一种视角去理解。

在二维参数空间坐标中，“线”其上的“点”，\((m,c)\)满足于\(c=-xm+y\), 一条参数空间上的“线”就确定了二维平面中的唯一数据坐标\((x,y)\) (参数空间上的一条“线”，对应了数据空间中某个点的直线簇)

这里的参数空间就是，hough space

什么是Hough Voting呢？

举直线（可以进一步泛化，称之为模型A）的例子

我们可以把数据空间上的数据点，想象成是由其模型A--直线生成的，那么数据空间中的一个点，在直线模型的参数空间（hough Space）上，可能属于很多个直线（点的直线簇）。我们用一个2维数组来记录直线的参数，构造出Hough Space。比如Hough Line Transform给出的参数形式 \(\rho = x \cos \theta + y \sin \theta\) 中的 \((\rho,\theta)\) 来构造一个二维Hough Space, 然后我们需要选择一个量化等级，来控制其中一个参数增减的最小单位。这样的话，拿到一个点，我们就可以给其在Hough Space中可能属于的所有模型各投一次票。如果对数据空间中的所有数据点进行上述操作，并用Accumulator累积Hough Space各个模型的投票总数，我们就可以获得不同模型的得分，那么根据得分最大的模型对应的参数，就能够刻画出数据空间中数据点们共同依赖的那个模型！

根据这种思想我们可以将直线模型泛化到更一般的圆模型、椭圆甚至无规则的形状！！

这就是Hough Transform 和hough Voting的基本要义了。

然后我研究了一下coo_matrix函数，它能快速地构造一个稀疏矩阵，并且注意到，代码给出的格式满足：

coo_matrix((data, (i, j)), [shape=(M, N)])
to construct from three arrays:
    1. data[:]   the entries of the matrix, in any order
    2. i[:]      the row indices of the matrix entries
    3. j[:]      the column indices of the matrix entries

Where ``A[i[k], j[k]] = data[k]``.  When shape is not
specified, it is inferred from the index arrays

并且它具有累积功能，而就是它，完成了hough voting的功能

bilinear interpolation

再去分析一下，与np.ceil和np.floor作差以及连乘的意义

xs = votes[:,0]
ys = votes[:,1]
ps = votes[:,2]
tl = [np.floor(ys).astype('int32'), np.floor(xs).astype('int32')]
tr = [np.floor(ys).astype('int32'), np.ceil(xs).astype('int32')]
bl = [np.ceil(ys).astype('int32'), np.floor(xs).astype('int32')]
br = [np.ceil(ys).astype('int32'), np.ceil(xs).astype('int32')]
dx = xs - tl[1]
dy = ys - tl[0]
tl_vals = ps*(1.-dx)*(1.-dy)
tr_vals = ps*dx*(1.-dy)
bl_vals = ps*dy*(1.-dx)
br_vals = ps*dy*dx

其功能相当于在进行双线性插值：

f(dx,dy)=f(0,0)(1-dx)(1-dy)+f(1,0)x(1-dy)+f(0,1)(1-dx)dy+f(1,1)dxdy

针对，每个位置上预测的小数点精度上（如果预测为整数，仅有tl_vals不为0）的偏量，以双线性的方式，并乘以预测置信度，累积到相邻的整数像素位置（这样可以不会牺牲任何量化上的精度），进而可以得到精确的预测位置，即反应在Hough Score Maps的极大值位置上

对于Hough Score Maps对应的每一个关键点类型，最后施以：

def compute_heatmaps(kp_maps, short_offsets,radius, kpts_num):
    heatmaps = []
    map_shape = kp_maps.shape[:2]
    idx = np.rollaxis(np.indices(map_shape[::-1]), 0, 3).transpose((1,0,2))
    for i in range(kpts_num):
        this_kp_map = kp_maps[:,:,i:i+1]
        votes = idx + short_offsets[:,:,i]
        votes = np.reshape(np.concatenate([votes, this_kp_map], axis=-1), (-1, 3))
        heatmaps.append(accumulate_votes(votes, shape=map_shape) / (np.pi*radius**2))

    return np.stack(heatmaps, axis=-1)

即得到了Hough Score Maps.

Greedy Decoding 和 Assign pixels to person skeleton instance

• PersonLab中巧妙的算法是：利用树结构，通过Greedy Decoding将偏移向量连通成独立的人体骨架；利用mask中像素与keypoints的偏移向量，以聚类的方式形成人体intance mask。

关于Greedy Decoding部分，可以参考我的另一篇博客。

关于长向量long-range-offset的预测部分,从直观上看，可以发现，偏移量向内指向人体的关节，可以形成了论文提到的basins of attraction. 体现了一种区域分割的思想。

更多请参考如下：

• KerasPersonLab
• Hough Line Transform
• PersonLab