CV: Optical Flow

1. Use it for MNIST or
2. signature verification?
3. scale and rotation using optical flow

Introduction

Computer vision is a scientific field that deals with how computers can gain high-level understanding from digital images or videos. It seeks to understand and automate tasks that the human visual system can do. [@wikiComputerVision2020]

人的視覺系統包含眼和腦：眼主要是負責成像（看的清楚）；腦主要是負責視覺（看到什麼和看懂）。包含 edge and object detection, color detection, object classification, face detection, face recognition, depth detection. 以及 motion detection and estimation.

除了上述比較客觀的功能，視覺系統也會主動“腦補”，根據 context 主動生成不存在的內容，一個例子是盲點的腦補。Reference [Ramachandra].

Why Motion Detection and Estimation

分為兩類：(1) image or video quality; (2) object (mainly human and car) detection, tracking and warning (e.g. transpass, intruding)
(1) high motion => short shutter to avoid motion blur or lower temporal filtering (e.g. 3DNR) to avoid motion blur
(2) motion estimation 可以用於 object detection 似乎也 make sense. 同一個 object 的 motion 基本一致。但僅限於剛性物體。對於人（手，腳，身體移動都不同）就不一定適用。

Optical Flow

Why optical flow

Optical flow 就是 address CV 的 motion detection and estimation.

一般人對 motion detection and estimation 如此習以為常，而忽略其中的困難和奧秘。
視覺系統處理 motion 的幾個特點

• 3D motion is projected to 2D motion losing depth information. 注意雙眼視覺雖然提供了 depth information, 但是單眼仍然可以很好判斷非深度方向的 motion. 深度方向的 motion 是一個 ill-posed problem. 需要其他的 information 輔助判斷 e.g. 物體大小變化。
• 一個直觀的想法是先作 object detection, 根據 object 位置和大小的變化 detect and estimate motion. 這個方法有兩個問題：
  • 必須先作 object detection, 需要大量的運算。特別是非常多 objects (e.g. crowds, traffic jam), 不大可能大量 object detection and motion detection.
  • 液體(e.g. 水波，海浪)或氣體(雲，煙)沒有固定的形狀，但仍然有 motion.
• So what is the solution? Light! Detect change of light (i.e. optical flow) is more fundamental and easier than detect object motion.

What is optical flow （什麼是光流）

在計算機視覺中，光流是一個有關物體運動的概念，指在一幀視頻圖像中，代表同一目標的像素點到下一幀的移動量，用向量表示。

根據光流的亮度恆定假設（或是無窮遠光源，如太陽），同一物體在連續的幀間運動時，像素值不變 (一隻小鳥不會在運動時突然變成鴨或者飛機)。

所以這個運動的過程，就像是光的「流動」過程，簡稱光流，預測光流的過程，就被稱之為光流預測。

Optical Flow Formulation

Input: 一般是一段 2D video, i.e. sequence of images, with some moving objects. 通常 CV (computer vision) 算法只用到 luminance (亮度)而不用 chroma (色度)。DL (deep learning) 算法用 RGB training and inference.

Output: a sequence of 2D motion vector fields corresponding to motions of two consecutive images.

Assumption: 非常重要。（1）亮度恆定假設；（2）通常是兩張 consecutive images, 稱為 one pair. 但我們應該了解，更多的 continuous images (all pairs) 可以讓結果更準確，例如使用 some smoothing algorithm.

Math formula:
use fluid mechanics: laplacian operator I (space) = source/sink change of time (time derivative).

How

• Optical flow 算法依場景可分為兩類: (1) sparse optical flow (下圖左), and (2) dense optical flow algorithms (下圖右)。

• Sparse 算法基本上假設背景和鏡頭為固定，算法針對少數移動物體的 optical flow. 常見於 surveillance camera 的應用。

• 上述不正確。 Sparse 應是集中在一些特徵點如 edge, corners 計算 optical flow 而非 mobile object. (mobile object detection 要更 high level algorithm 才能偵測。通常是 based on optical flow 的結果。倒因為果) 另外 sparse 算法也不用假設背景和鏡頭固定! 也非只用於 surveillance. Sparse 的好處是 computation 少，比較容易用於 real-time application. 但比較不 robust, 容易受 noise or other factors 影響。

• Sparse 包含：TLD (Track-Learn-Detect) algorithm. Sparse 一般用於 object tracking. 比較不適用於 image quality improvement. 包含：Lucas-Kanade (LK) or pyramid LK method?

• Dense 算法基本是 estimating per-pixel motion between video frames. 包含：Lucas-Kanade (LK) or pyramid LK method (?), and Horn-Schuchck

Li Fei-Fei ECCV No. 1 FlowNet

這篇名為《RAFT: Recurrent All-Pairs Field Transforms for Optical Flow》的論文，
應用上，光流通常會用於視頻中的目標跟蹤，例如TLD算法。

先前光流預測法的缺陷

根據是否選取圖像稀疏點（特徵明顯，梯度較大），可以將光流預測分為稀疏光流和稠密光流，如下圖左和右。

其中，稀疏光流會選取圖像稀疏點進行光流估計；而在稠密光流里，為了表示方便，會使用不同的顏色和亮度表示光流的大小和方向。

針對這兩種方法，目前有傳統預測和基於深度學習的兩種經典算法。

傳統 Computer Vision：稀疏光流估計算法

求解光流預測算法前，首先要知道孔徑問題。

如圖，從圓孔中觀察移動條紋的變化，發現條紋無論往哪個方向移動，從圓孔來看，移動的變化都是一致的。

其中一種傳統的Lucas-Kanade算法，是求解稀疏光流的方法，選取了一些可逆的像素點估計光流，這些像素點是亮度變化明顯（特徵明顯）的角點，借助可逆相關性質，預測光流方向。

传统算法是指基于变分模型的光流算法

深度學習 Optical Flow: FlowNet(s), SpyNet, RAFT

隨著CNN在圖像分割、深度預測和邊緣預測方面的成功，同樣是每個 pixel 都要給出預測結果的光流預測問題能否也利用CNN進行預測呢？

FlowNet

FlowNet [@dosovitskiyFlowNetLearning2015] 是第一個嘗試利用CNN去直接預測光流的工作，它將光流預測問題建模為一個有監督的深度學習問題如下圖。 Input 是兩張 images with motion, output 是 optical flow 的 motion vector field.

接下來針對深度學習的煉丹五大重點：Model, Loss function, Dataset, Training, Accuracy 進行討論。

Model

Two image inputs 的 neural network 有一個有名的例子：Siamese network for face recognition, ReID, or signature verification.

[@pendurkarKerasImplementation2018]

Siamese 有兩個 CNNs with shared weights. 只有 contracting (encoding) network (大變小), output 是 binary logic (True or False).

FlowNet 可以 leverage 的是 contracting (encoding) CNN, 另外再加上 expanding (decoding) CNN (小變大) 才能產生 pixel base output.

Contracting CNN1: FlowNetS

Two input images 直接 concatenate (384x512x6), 之後融合在一起。感覺比較適合 smaller motion?? Input image 384×512 = 3×4

Contracting CNN2: FlowNetC

Two input images 前面幾層(3 layers) 分開 (384x512x3), 比較類似 Siamese network 之後融合在一起。有用 shared weight as Siamese?? or separate weight??
為了提升網絡的匹配性能，人為模仿標準的匹配過程，設計出「互相關層」，即先提取特徵，再計算特徵的相關性。相關性的計算實際上可以看做是兩張圖像的特徵在空間維做卷積運算。

Expanding CNN

在解碼細化的過程中，對每層的反卷積Relu層，不僅輸入前一層的輸出，同時還輸入前一層預測的低尺度的光流和對應編碼模塊中的特徵層。這樣使得每一層反卷積層在細化時，不僅可以獲得深層的抽象信息，同時還可以獲得淺層的具象信息，以彌補因特徵空間尺度的縮小而損失的信息。Output size 136×320 = 17×40? 另外 output 是 2D motion vector or color map?
應該是 2D motion vector. (136×160)x2 2D motion vector.

Loss function

在損失設計上，對於每個像素，損失定義為預測的光流值和真值（groundtruth）之間的歐氏距離，稱這種誤差為EPE，全稱End-Point-Error。

Dataset

現在另一個問題來了，是否有足夠的數據去訓練網絡呢？

為了訓練網絡，我們需要大量的具有光流真值的數據。而目前已知的具有光流真值的數據庫規模都太小，即使利用數據增加的技術也相差甚遠。另外，要獲得真實世界中，自然圖片的準確光流往往更是難以獲得。

Flying Chair: [1]中為解決這個問題，研究員們以犧牲圖片真實性為代價，轉而人為去合成大量的虛擬圖像對。通過將一些3D椅子模型[3]隨機的覆蓋在一些從Flickr上檢索的圖片上合成圖像，再對椅子和背景分別做隨機的仿射變化。圖像雖然看上去不是很自然，但是卻很容易的獲得了約22k帶有光流真值的圖像對。如圖4，其中光流以顏色編碼的形式展示，色調代表方向，強度代表大小。

結果

Flying Chair

Sintel

最后的结果表明设计出的网络具有学习和预测光流的能力，证明CNN可以用来解决光流预测问题。并且实验表明，即使是人工合成的非自然图像，依然可以用来训练深度神经网络来预测光流。

精度方面，FlowNetC结果出现了过拟合，与FlowNetS相比也是难分伯仲，然而在FlowNet2.0中，研究者又更新了结论。速度方面，在NVIDIA GTX Titan上运行时，FlowNetS的运行时间为0.08s，FlowNetC因为加入了互相关层的计算，因此运行时间增加到0.15s。

比较其他算法和FlowNet的性能。在精度方面，虽然在公共数据库上离最好的传统算法还有差距，但是在合成的FlyingChair数据库上，FlowNet的结果精度是最好的。这使我们看到只要拥有合适充足的数据，基于CNN的算法还是非常有前景的。另外，由于FlowNet只需要简单的卷积运算，加上GPU的加速，在算法速度方面，FlowNet具有很大优势，远远快于目前其他领先的传统算法，可以实现实时的光流计算系统。

FlowNet2.0

FlowNet提出了第一個基於CNN的光流預測算法，雖然具有快速的計算速度，但是精度依然不及目前最好的傳統方法。這在很大程度上限制了FlowNet的應用。

FlowNet2.0是FlowNet的增強版，在FlowNet的基礎上進行提升，在速度上只付出了很小的代價，使性能大幅度提升，追平了目前領先的傳統方法。[@ilgFlowNetEvolution2017]

主要有以下改進：

Model

Use FlowNetC and FlowNetS as building blocks, 加上 cascade, warp, and stack networks.

Dataset

增加了訓練數據，改進了訓練策略

深度學習算法的一大優勢即是具有學習能力，算法的性能會隨著不斷學習而提升。FlowNet2.0在FlowNet的基礎上，額外增加了具有3維運動的數據庫FlyingThings3D[4]和更加複雜的訓練策略。

實驗表明，先在FlyingChair上按S_long策略，再在FlyingThings3D上按S_fine策略後，所得結果最好。單獨在FlyingThing3D上訓練的結果反而下降。文中給出瞭解釋是儘管FlyingThings3D比較真實，包含更豐富的運動信息，但是過早的學習複雜的運動信息反而不易收斂到更好的結果，而先從簡單的運動信息學起，由易到難反得到了更好的結果。

結果

相比於FlyingChair中的圖像只具有平面變換，FlyingThings3D中的圖像具有真實的3D運動和亮度變化，按理說應該包含著更豐富的運動變換信息，利用它訓練出的網絡模型應該更具魯棒性。然而實驗發現，訓練結果不僅與數據種類有關，還與數據訓練的順序有關。

S_short即為FlowNet中的訓練策略，FlowNet2中增加S_long策略和S_fine策略。

相比於FlyingChair中的圖像只具有平面變換，FlyingThings3D中的圖像具有真實的3D運動和亮度變化，按理說應該包含著更豐富的運動變換信息，利用它訓練出的網絡模型應該更具魯棒性。然而實驗發現，訓練結果不僅與數據種類有關，還與數據訓練的順序有關。

實驗表明，先在FlyingChair上按S_long策略，再在FlyingThings3D上按S_fine策略後，所得結果最好。單獨在FlyingThing3D上訓練的結果反而下降。文中給出瞭解釋是儘管FlyingThings3D比較真實，包含更豐富的運動信息，但是過早的學習複雜的運動信息反而不易收斂到更好的結果，而先從簡單的運動信息學起，由易到難反得到了更好的結果。

同時，結果發現FlowNetC的性能要高於FlowNetS。

Cascade Model (Flow CNN + Post processing CNN)

所有最好的光流預測算法都利用了循環優化的方法。而基於CNN的像素級預測算法結果往往都含有很多噪聲和模糊 (similar to ray tracing?)。通常的做法都是利用一些後處理方法對結果進行優化，如FlowNet中，利用傳統變分優化方法對FlowNet輸出結果進行再優化。那麼是否也能夠利用CNN來代替後處理方法對結果進行再優化呢？文中對這一問題進行了探究。 (Again, similar to ray tracing?)

How to do it? Use (backward) warp on image2 to compare with image1

實驗結果證明在FlowNetC的基礎上堆疊FlowNetS，當以每個FlowNet為單位逐個進行訓練時，得到的結果最優。也就是說在訓練當前FlowNet模塊時，前面的FlowNet模塊參數均為固定狀態。

此外，發現後續的堆疊FlowNet模塊，除了輸入 Image1 and Image2 外，再輸入前一模塊的預測光流W_i，Image2 經預測 W_i 的 Warp 以及誤差圖像 |L1-L2(Warp)| 後，可以使新堆疊的FlowNet模塊專注去學習 L1 與 L2(Warp) 之間剩下的運動變換，從而有效的防止堆疊後的網絡過擬合。

實驗表明，當以FlowNetC為基礎網絡，額外堆疊兩個FlowNetS模塊後，所得結果最好，[2]中用FlowNet2-CSS表示。

同時指出，隨著優化模塊的堆疊，FlowNet2的計算速度會有所下降，因此可以通過按比例消減FlowNet各層的特徵通道數來減少計算量。[2]推薦保留每層3/8的通道數是一個不錯的選擇。文中將消減後的網絡用FlowNet2-c和FlowNet2-s表示。最快的FlowNet2-s精度與FlowNetS的精度近似，而運算速率可以達到140fps（在Nvidia GTX 1080上測試）。

最後，由於FlowNet在真實圖片的小位移情況下，結果往往不夠理想。因此[2]中，針對小位移情況改進了FlowNet模塊的結構，首先將編碼模塊部分中大小為7×7和5×5的卷積核均換為多層3×3卷積核以增加對小位移的分辨率。其次，在解碼模塊的反卷積層之間，均增加一層卷積層以便對小位移輸出更加平滑的光流預測。文中將針對小位移改進後的網絡結構命名為FlowNet2-SD。在訓練數據的選擇上，針對小位移，又重新合成了以小位移為主的新的數據庫ChairsSDHom,並將此前的堆疊網絡FlowNet2-CSS在ChairsSDHom和FlyingThings3D的混合數據上繼續微調訓練，將結果網絡表示為FlowNet2-CSS-ft-sd。

Stack Network 針對小位移的情況引入特定的子網絡進行處理

最後，由於FlowNet在真實圖片的小位移情況下，結果往往不夠理想。因此[2]中，針對小位移情況改進了FlowNet模塊的結構，首先將編碼模塊部分中大小為7×7和5×5的卷積核均換為多層3×3卷積核以增加對小位移的分辨率。其次，在解碼模塊的反卷積層之間，均增加一層卷積層以便對小位移輸出更加平滑的光流預測。文中將針對小位移改進後的網絡結構命名為FlowNet2-SD。在訓練數據的選擇上，針對小位移，又重新合成了以小位移為主的新的數據庫ChairsSDHom,並將此前的堆疊網絡FlowNet2-CSS在ChairsSDHom和FlyingThings3D的混合數據上繼續微調訓練，將結果網絡表示為FlowNet2-CSS-ft-sd。

最後，再利用一個新的小網絡對FlowNet2-CSS-ft-sd的結果和FlowNet2-SD的結果進行融合，並將整個網絡體系命名為FlowNet2。結構如下：

結果

从实验结果来看，FlowNet2在各个公共数据库上，在精度方面已经追平了目前最好的一些传统算法。同时，在速度上依然保持着高效快速的优势。下面我们看一下各种情况下FlowNet2的输出结果：

小位移情况下，FlowNet2-CSS的光流预测噪声非常大，而FlowNet2-SD的输出非常光滑，最后融合结果充分利用了FlowNet2-SD的结果。

大位移情况下，FlowNet2-CSS预测出了大部分运动，而FlowNet2-SD则丢失了大部分运动信息，最后融合结果又很好的利用了FlowNet2-CSS的结果。

综上，FlowNet2-CSS与FlowNet2-SD做到了很好地互补，共同保证了FlowNet2在各种情况下的预测质量。

文中还通过将FlowNet2的预测结果直接用于运动分割和动作识别的任务中，证明FlowNet2的精度已完全可以和其他传统算法媲美的程度，已达到可以实际应用的阶段。

SpyNet: Pyramid Model

Another idea is the coarse to fine refinement.

PWCNet: Pyramid Model (Nvidia)

PWC stands for Pyramid, Warp, and Cost volume.

Why Pyramid in Optical Flow?

1. Pyramid at the top has smaller motion, and smaller search space! Can capture the global motion!!
2. Pyramid at the bottom can capture local motion.
3. 注意 pyramid 的 CNN 是 Siamese Network (shared weight).

Excellent Talk! [@sunROB20182018]
Pyramid, Warp, Cost volume,(PWCnet from Nvidia) (ECCV2018) use domain knowledge model

Pyramid, warp, cost volume (PWCnet from Nvidia) (ECCV2018)

該網絡基於三個簡單但是由來已久的原則：金字塔式處理（pyramidal processing）；基於上一層習得的光流偏移下一層特徵，逐層學習下一層細部光流（warping）；設計代價容量函數（cost volume). 儘管PWC-Net的網絡尺寸比flownet2小了17倍（Flownet2需要640MB的memory footprint），也更加容易訓練，卻在MPI Sintel final pass 和 KITTI 2015 benchmarks表現的最好。

成功關鍵
Cost volume: 存儲了兩幀圖像之間對應像素的匹配代價。其最初的定義適用於stereo matching這一特殊的光流情景。近期有一些改良用於普遍的光流場景，他們基於單一範圍，而且computationally expensive and memory intensive. 我們（指作者）重新定義的方法…….(很好就是了)（constructing a partial cost volume at multiple pyramid levels leads to both effective and efficient models. ）

IRR-FlowNet

Introduce Iterative Residue Refinement concept. Residue is very popular concept in resnet. [@hurIterativeResidual2019] 但在這裡反而很像 SDM 的 feedback path!!! Excellent paper!!!
No coarse to fine procedure!

看起來很像 Sigma-Delta Modulator!! Compared with high order SDM with mesh SDM? What is optical flow = motion estimation = delta of input!

Joint flow and occlusion estimation

IRR PWCNet (Mesh -> xxx)

ECCV2020 Optical Flow RAFT (Princeton)

然而，上述基於深度學習的經典光流預測算法，存在著幾個缺點，無論怎麼優化，這些缺點都會因為框架自身而一直存在。

但在RAFT，這個全稱光流循環全對場變換的框架中，過往的3大缺點都被一一解決了

三點創新

第一，先前的框架普遍採用從粗到細的設計，也就是先用低分辨率估算流量，再用高分辨率採樣和調整。

相比之下，RAFT以高分辨率維護和更新單個固定的光流場。

這種做法帶來了如下幾個突破：低分辨率導致的預測錯誤率降低，錯過小而快速移動目標的概率降低，以及超過1M參數的訓練通常需要的迭代次數降低。

第二，先前的框架包括某種形式上的迭代細化，但不限制迭代之間的權重，這就導致了迭代次數的限制。

例如，IRR 使用的 FlowNetS 或 PWC-Net 作為循環單元，前者受網絡大小（參數量38M）限制，只能應用5次迭代，後者受金字塔等級數限制。
相比之下，RAFT的更新運算是週期性、輕量級的：這個框架的更新運算器只有2.7M個參數，可以迭代100多次。

第三，先前框架中的微調模塊，通常只採用普通卷積或相關聯層。

相比之下，更新運算符是新設計，由卷積GRU組成，該卷積GRU在4D多尺度相關聯向量上的表現更加優異。

介紹了遞歸全對場變換(RAFT)，這是一種新的光流深層網絡結構。RAFT提取每個像素的特徵，為所有像素對建立多尺度4D相關體，並通過在相關體上執行查找的遞歸單元迭代地更新光流場。RAFT具有SOTA的性能，跨數據集泛化能力強，在推理時間、訓練速度和參數統計等方面具有較高的效率。

Model

MEMC/FRC/Slow Motion

Optical flow or motion estimation 基本是其中一塊。其中一些 concept, 例如 warping 可以用於 optical flow.

Interpolate two or more images to generate intermediate images. 一般用於 video 的 Frame rate conversion (FRC) or Motion estimation motion compensation (MEMC) purpose. 例如把 24 or 30 FPS (frame-per-second) 的 video 轉成 60 or 120 FPS 的 video. [@huangDLMEMC2019]

則非常類似 optical flow 也密切相關, output 也是 pixel base image. 唯一的差異是 FRC/MEMC output 是 intermediate
leverage from Warping.

事實上一些 MEMC network 是基於 optical flow computation, 例如 Super SloMo (Nvidia) [@jiangSuperSloMo2018];

或是 MEMC-Net [@baoMEMCNetMotion2019].