Category Archives: Mathematics

Notes on Differential Equations (4) —— Step Function $H(t)$ and Delta Function $\delta(t)$

The step function $H(t)$ is always 0 until a time point $t=0$, it becomes a constant and then stay at that constant forever.

\begin{align}H(t)=\left\{\begin{aligned} 0 &\, &t \lt 0\\ 1 &\, &t \ge 0 \end{aligned}\right.\end{align}

And we can shift the $H(t)$ by $T$ time, that is $H(t-T)$.

The delta function $$\delta (t) is always 0, except for a single time point $t=0$, it has a value 1. Thus delta function is all in one instant, an impulse. Also, the delta function can be shifted by $T$ time, that is $\delta (t-T)$.

Although this is not a continuous function, this is what we do in real life. Because the deposits are always made at some specific instants.

Continue reading Notes on Differential Equations (4) —— Step Function $H(t)$ and Delta Function $\delta(t)$

Notes on Differential Equations (3) —— $\frac{dy}{dt}=ay+q(t)$

The general form for any input (or source term) with first order differential equations can be written as below, and it starts at $y(0)$.

$$\frac{dy}{dt}=ay+q(t)$$

One way to interpret this equation is to think it as a bank account, where $a$ is the interest rate and $q(t)$ is the new deposits.

$$\frac{dy}{dt}=\underbrace{ay}_\textrm{interest added}+\underbrace{q(t)}_\textrm{new deposits}$$

The general formula of the solution is

$$y(t)=\underbrace{y(0)e^{at}}_\textrm{null solution}+\underbrace{\int_{s=0}^{s=t}e^{a(t-s)}q(s)ds}_\textrm{particular solution}$$

where $s$ is the running clock, and $t$ is the time we look at it. Why the integral term has $(t-s)$ inside? Because the deposits $q(s)$ is made at time point $s$, and you only get interests after you made the deposits.

Continue reading Notes on Differential Equations (3) —— $\frac{dy}{dt}=ay+q(t)$

Notes on Differential Equations (1) —— $\frac{dy}{dx}=ay+e^{st}$

This series will be my personal notes on differential equations (including ordinary differential equation (ODE), partial differential equation (PDE) and stochastic differential equation (SDE)). These posts may contain mistakes.

The first a few posts will be different solutions for different forms of first order ODE.

The first form is $\frac{dy}{dx}=ay+e^{st}$.

Continue reading Notes on Differential Equations (1) —— $\frac{dy}{dx}=ay+e^{st}$

Rust Learning from Zero (25) —— Handle Continuous Features in Decision Tree with Rust

This post has two main purposes, 1) serves as personal notes for handling continuous features in decision tree; 2) try to use trait to add more computation operations to vectors, because the original Vec shipped with Rust is nowhere near the numpy in Python when it comes to scientific computation. (Though I know that Vec may not be designed to do handle such task.)

There are many ways to handle continuous descriptive features, such as discretions. This post will exploit weighted variance as a measurement for splitting continuous feature at a node.

The weighted variance is computed by the following equation, where $n$ is the number of rows in the data, $\mathcal{L}$ is the set of all unique labels, $D$ is the column with continuous features ($n$ rows), $p^*$ denotes the best split position in $D$.

$p^*=argmin_{p\in [1, n)} \sum_{l\in \mathcal{L}}\frac{\|\mathcal{L}_{i=l}\|}{\|\mathcal{L}\|} [var(D_{[0, p)}, \mathcal{L}_{i=l}) + var(D_{[p, n)}, \mathcal{L}_{i=l})]$

Once the algorithm decides the best split position of $D$, we can apply divide and conquer! For example, if $p^*$ has been computed, then we recursively apply this mechanism to both $D[0 .. p^*]$ and $D[p^* ..]$. When the split position arrays, $S_i$ and $S_j$, of $D[0 .. p^*]$ and $D[p^* ..]$ return, $S_i$ and $S_j$ will be merged and sorted as final value.

Let's try this algorithm on this small dataset,

Continuous DataLabel
00
20
31
70
150
352
451
471
550
571
612
672
811
920
962
972

Looks good to me! And code goes below.

Continue reading Rust Learning from Zero (25) —— Handle Continuous Features in Decision Tree with Rust

Gambling Problem

The problem is described below:

For the match Limp Stoners vs Exmouth Breathers the two bookmakers A and C offer different odds,

Stoners WinDrawBreathers Win
A4/1 (5.00)3/1 (4.00)2/3 (1.67)
C3/1 (4.00)2/1 (3.00)1/1 (2.00)

You have £100. How do you have to place your bets in order to maximize guaranteed profit no matter what the outcome of the game?

Noticing,

  • One is allowed to put money on different outcomes simultaneously. So, you can bet £50 on Stoners and £20 on Draw at A, and £30 on Breathers at C.
  • The numbers for the odds mean that, for example, if you bet £1 on Stoners at BrokeLads you will get £5.00 back (your own £1 and £4 winning). The fraction format specifies how much you would win if you bet £1, the decimal format specifies how much you would get back if you bet £1 (so, it’s the same as the fraction + 1.
Continue reading Gambling Problem

「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

Continue reading 「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\)柱即可。

Continue reading 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

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