通过投影统计计算二值图朝向

本文最后更新于:2022年9月20日 上午

图像处理中会遇到需要计算物体朝向的情况,前文使用转动惯量计算了物体朝向,本文换一种思路,使用投影统计计算朝向。

问题描述

  • 对于一幅二值图像,需要求解图像的朝向

解决思路

  • 物体上的每个点可以向某个方向投影,完成投影后每个点变为一维数据

  • 直觉上,与真正朝向垂直方向的投影的一维数据,的方差是最小的
  • 按照这个思路,求解二值图物体朝向

计算方法

  • 图中非零的点有 $N$ 个,坐标为 $(x_i, y_i), 0 <i<N$,合并为列向量

$$
\textbf{x}=[x_1,x_2, …,x_N]^T, \textbf{y}=[y_1,y_2, …,y_N]^T
$$

  • 合并为维度 $N \times 2$ 的矩阵 $\textbf{M} = [\textbf{x}, \textbf{y}]$,
  • 给定一条直线,直线过点 $(x_t, y_t)$,直线的法向量 $\textbf{v} = [a, b]^T$,该法向量为单位向量,有:

$$
a^ 2 + b ^2=1
$$

  • 则直线可表示为:

$$
[x-x_t,y-y_t]\textbf{v} = 0
$$

  • 二值图上的点 $(x,y)$ 到直线的有向距离为: 点到$(x_t, y_t)$ 的向量到直线法向量 $\textbf{v}$ 的投影:

$$
d =[x-x_t,y-y_t]\textbf{v}
$$

  • 所有点的有向距离组成向量:

$$
\begin{array}{c}
\textbf{d} &= [\textbf{M}-[x_t,y_t]]\textbf{v}\
&= \textbf{M}\textbf{v}- [x_t,y_t]\textbf{v}
\end{array}
$$

  • 设 $[x_t,y_t]\textbf{v}$ 为常数 $c$,有:

$$
d =[x,y]\textbf{v}-c,\textbf{d} = \textbf{M}\textbf{v}- c
$$

  • 我们的目标是找到所有点的有向距离组成的样本集合的方差统计量最小,有向距离的均值为:

$$
\overline{d} =\frac{1}{N} \sum_{i=1}^N\textbf{m}_i\textbf{v}- c\
=[\overline{x},\overline{y}]\textbf{v}- c
$$

  • 有向距离的方差可表示为:
$$ \begin{array}{c} Var&=&\frac{1}{N} \sum_{i=1}^N (d_i-\overline{d})^2\\ &=&\frac{1}{N} \sum_{i=1}^N ([x_i,y_i]\textbf{v}-c-[\overline{x},\overline{y}]\textbf{v}+c)^2\\ &=&\frac{1}{N} \sum_{i=1}^N ([x_i-\overline{x},y_i-\overline{y}]\textbf{v})^2 \end{array} $$
  • 可见二值图到直线的有向距离的方差与直线的偏置无关,仅与法向量有关,设 $\textbf{M}’=\textbf{M}-[\overline{x}, \overline{y}]$,有:
$$ \begin{array}{c} Var&=&\frac{1}{N} \sum_{i=1}^N ([x_i-\overline{x},y_i-\overline{y}]\textbf{v})^2\\ &=&\frac{1}{N} (\textbf{M}’\textbf{v})^T(\textbf{M}’\textbf{v})\\ &=& \frac{1}{N} \textbf{v}^T\textbf{M}’^T\textbf{M}’\textbf{v} \end{array} $$
  • 可以看做 $Var$ 是关于 $\textbf{v}$ 的二次型,系数矩阵为 $\frac{1}{N}\textbf{M}’^T\textbf{M}’ $
  • 注意:我们需要该方差最小,但不能直接对 $\textbf{v}$ 求导,令其取值为零:
$$ \begin{array}{c}\frac{{\partial Var}}{{\partial {\bf{v}}}} = \frac{2}{N}\textbf{M}’^T\sqrt{\textbf{p}}\sqrt{\textbf{p}}^T\textbf{M}’\bf{v}= 0\\\textbf{M}’^T\sqrt{\textbf{p}}\sqrt{\textbf{p}}^T\textbf{M}’\bf{v}= 0\end{array} $$
  • 因为这样做会得到 $\bf{v}$ 为零向量的平凡解,但是事实上 $\bf{v}$ 是有模长为 1 的约束的,因此我们需要解的是带约束的优化方程:

    $$ \begin{array}{c} minimize \quad Var= \frac{1}{N} \textbf{v}^T\textbf{M}’^T\sqrt{\textbf{p}}\sqrt{\textbf{p}}^T\textbf{M}’\textbf{v}\\ subject \ to \quad \bf{v}^T\bf{v}-1=0 \end{array} $$

解方程

拉格朗日

  • 至此之后的方程解法和之前完全相同,只是矩阵数值根据密度发生了一些变化
  • 之后解该方程需要在 $|\bf{v}|= 1$ 的约束下进行,因此可以引入拉格朗日乘数法
  • 可以参考 拉格朗日解该方程 的流程

特征向量

  • 我们用 $\bf{A}$ 表示上述系数矩阵 $\frac{1}{N}\textbf{M}’^T\textbf{M}’ $(此处为 $2\times 2$ 的矩阵)
  • 因此我们的优化目标变为: $\bf{v}^TA\bf{v}$
  • 拉格朗日方程为:
$$ L =\bf{v}^TA\bf{v}+\lambda(\bf{v}^T\bf{v}-1) $$
  • 对 $\bf{v}$ 求导,令其为 0:
$$ \begin{array}{c} 2A\bf{v}+2\lambda\bf{v}=0\\A\bf{v}+\lambda\bf{v}=0\\(A+\lambda I)\bf{v}=0 \end{array} $$
  • 这就是在求 $\bf{A}$ 的特征向量
  • 求就完了,会得到两个特征向量,特征值小的对应的特征向量为方差最小的投影方向。

参考资料


通过投影统计计算二值图朝向
https://www.zywvvd.com/notes/study/image-processing/robot-vision/chapter-3/obj-orientation/obj-orientation/
作者
Yiwei Zhang
发布于
2022年8月24日
许可协议