分类目录归档:Mathematics

「Single Image Haze Removal Using Dark Channel Prior」Python Implementation with OpenCV

Haze Removed via Dark Channel Prior
Haze Removed via Dark Channel Prior

A Brief Review


Single Image Haze Removal Using Dark Channel Prior」是 2009 年 CVPR 最佳论文,何凯明博士在这篇论文中提出了暗通道先验的图像去雾算法。

那么暗通道先验是什么呢?这种方法是基于这样的一个观察:

It is based on a key observation most local patches in haze-free outdoor images contain some pixels which have very low intensities in at least one color channel.

简单来说就是对绝大多数没有雾的图像来说,它们的一些局部区域的像素中,某些像素至少有一个颜色通道的值很低。或者对应于原文的「low intensities」,即光强度很低。

我们需要对图像去雾的原因主要是图像中的雾会给很多算法带来麻烦,比如物体识别,特征提取等,它们都默认输入的图像是清晰的,没有雾的。或者不考虑算法,对于在野外或者无人机上的监视摄像头,遇到有雾的场景也是经常的事,即使是人工监视也是需要去雾的。

顺便一提,利用暗通道先验的算法去雾,还可以得到不错的景深图。

Last, the haze removal can produce depth information and benefit many vision algorithms and advanced image editing. Haze or fog can be a useful depth clue for scene understanding. The bad haze image can be put to good use.

在有雾的图像中,一个广泛使用的成像数学模型如下

\begin{equation}
    \mathbf{I}(\mathbf{x})=\mathbf{J}(\mathbf{x})t(\mathbf{x})+\mathbf{A}(1-t(\mathbf{x}))\tag{1}
\end{equation}

我们可以简单的将$\mathbf{x}$理解为图像中的某一个位置,那么,$\mathbf{I}(\mathbf{x})$则是我们最终观察到的有雾的图像在该点的强度;$\mathbf{J}(\mathbf{x})$是在没有雾的情况下,该点应有的强度;$t(\mathbf{x})$是该点的透射率(the medium transmission describing the portion of the light that is not scat- tered and reaches the camera);最后,$\mathbf{A}$是全局大气光强(global atmospheric light)。

图像去雾的目标就是从一张有雾的图像$\mathbf{I}(\mathbf{x})$中,恢复出没有雾的图像$\mathbf{J}(\mathbf{x})$,透射率$t(\mathbf{x})$以及$\mathbf{A}$,全局大气光强(global atmospheric light)。

其中,我们又把$\mathbf{J}(\mathbf{x})t(\mathbf{x})$的结果叫做「直接衰减,direct attenuation」,这个应该比较好理解,就是原始位置反射的光,经过介质(如雾、空气中的其他颗粒)时发生的衰减。然后我们又把$\mathbf{A}(1-t(\mathbf{x}))$叫做Airlight,也就是(先前经过介质时的)散射光导致的色偏。

airlight-and-direct-attenuation

继续阅读「Single Image Haze Removal Using Dark Channel Prior」Python Implementation with OpenCV

There is only one problem to solve——汉诺塔问题

汉诺塔问题的描述如下,汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从上往下从小到大顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘,只能移动在最顶端的圆盘。

那么这里我们也先来思考最简单的情况(变量当然是盘子的个数\(n\)啦),那么最简单的就是\(n=1\)了(当然,\(n=0\)也可以算是一种情况,不过没必要分析了)

不妨假设原始的柱子为\(A\),目标柱子为\(C\),

hanoi-tower-1

此时直接将盘子从\(A\)柱移动到\(C\)柱即可。

继续阅读There is only one problem to solve——汉诺塔问题

There is only one problem to solve——\(2^k\times 2^k\)棋盘覆盖问题

\(2^k\times 2^k\)棋盘覆盖问题描述如下,给出\(k\)的值,得到一块\(2^k\times 2^k\)大小的棋盘,棋盘上有一格是特殊方格。随后给出如下4种L型的骨牌,要求使用这四种L型的骨牌覆盖给定棋盘上的,除特殊方格以外的所有格子,并且任何两个L型骨牌不得重叠覆盖。

L

继续阅读There is only one problem to solve——\(2^k\times 2^k\)棋盘覆盖问题

从百鸡问题到数学思维

鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、母、雏各几何?

——张丘建《算经》

这里从最最简单的算法开始一步一步讲如何优化,主要涉及的还是数学,Roger Bacon曾在《Opus Majus》写到

It is impossible to know things of this world unless you know mathematics.

——Roger Bacon《Opus Majus》

虽然这篇 post 会一直讲百鸡问题,但是主要还是想以此记录一些在解决某些问题是可能用到的数学思维,并不是只为了做百鸡问题。当然,我的数学也不怎么样qwq不过至少在这道题上,应用数学之后的算法在时间上的减少是比较明显的。

这篇 post 由以下几个部分构成

继续阅读从百鸡问题到数学思维

Congested network笔记(4)

第二个谬误的思考方式是在估计和进度安排中使用的工作量单位: 人月。成本的确随开发产品的人数和时间的不同有着很大的变化, 进度却不是如此。因此我认为用人月作为衡量一项工作的规模是一个危险和带有欺骗性的神话。 它暗示着人员数量和时间是可以相互替换的。……从而,添加更多的人手,实际上是延长了而不是缩短了时间。

——人月神话

继续阅读Congested network笔记(4)

Congested network笔记(3)

上一篇 Congested network笔记(2) 的最后,我们把问题变成了变分不等式的求解,那么这两个变分不等式在什么情况下存在解,且解唯一呢?

$$\left\{\begin{align}\frac{\partial\mathcal{Z(F)}}{\partial\underline{\mathcal{F}}}\cdot(\mathcal{F}-\underline{\mathcal{F}})&\ge 0&\forall \mathcal{F}\in S&\text{  最优解}\\
\mathcal{C}(\mathcal{F}^*)\cdot(\mathcal{F}-\mathcal{F}^*)&\ge 0&\forall \mathcal{F}\in S&\text{ 均衡解}\end{align}\right.$$

继续阅读Congested network笔记(3)

Congested network笔记(1)

人类天性是自私的,而经济行为植根于此"事实"之上。博弈论看似也反映了此种假设。在博弈论最初的形式中,博弈论数学描述"理性的"行为,本质上是将"理性"和"自私"当作同义词。但按照今天的解释,博弈论并非假设人类总是表现得自私——或理性。博弈论告诉你如果人类确实表现得自私或理性,会是怎么样的情形。

——A BEAUTIFUL MATH
John Nash, Game Theory
AND THE MODERN QUEST FOR A CODE OF NATURE

继续阅读Congested network笔记(1)