# Week 1：CRNN + CTC
###### tags: `技術研討`

## 與會者

晟瑋、昊中、沛筠、宜昌、育銓、信賢 + CV Team

## Agenda

1. 前言 (LiLi)
2. CNN (LiLi)
3. RNN (昱睿)
4. Transcription (昱睿)
5. Loss (昱睿)
6. github code 的執行流程架構圖 (LiLi)
7. data_manager.py (LiLi)
8. crnn.py (昱睿)

## 論文研讀： An End-to-End Trainable Neural Network for Image-based Sequence Recognition and Its Application to Scene Text Recognition

* 論文連結：[link](https://arxiv.org/pdf/1507.05717.pdf)

- 前言
- 舊有的演算法都是將訓練和調教分開，但 CRNN 可以做到 end-to-end 的訓練
- DCNN 模型
- 從詞彙當中把每個字元裁切出來 (問題點：要先訓練強字元偵測器)
- 把每個詞彙都當成一個分類，改為分類模型 (問題點：預測的詞至少要在訓練集有看過才行)
- RNN 模型
- 雖可處理不同長度的詞彙，但要先抽取影像當中的特徵 (e.g., SIFT)
- CRNN 模型 (結合 DCNN + RNN)
- 只需針對詞彙標註，不用標註當中的字元
- 不須進行影像預處理 (e.g., 字元定位、字元分割)
- 長度無約束、只要對高度進行規一化
- 參數較過往的 DCNN 模型少很多，因此占用的儲存空間較少

- 網路架構
- 卷積層 (Convolutional Layers)：提取影像特徵
- [Convolutional Layer、Pooling Layer、Fully Connected Layer 簡要回顧](https://medium.com/jameslearningnote/資料分析-機器學習-第5-1講-卷積神經網絡介紹-convolutional-neural-network-4f8249d65d4f)
- [stride & padding 解釋](https://chih-sheng-huang821.medium.com/卷積神經網路-convolutional-neural-network-cnn-卷積計算中的步伐-stride-和填充-padding-94449e638e82)
- 迴圈層 (Recurrent Layers)：預測每一幀的標籤分布
- 上下文資訊有助於訓練
- 透過反向傳播 (back propagation) 可以將誤差差值傳到卷積層，讓迴圈層和卷積層可以共同訓練
- 可以對任意長度的序列進行操作
- 轉錄層 (Transciption Layer)：將每一幀的預測變為最終的標籤
- 無詞典轉錄 (lexicon-free)
- 基於詞點的轉錄 (lexicon-based)

### Sequence Labeling (RNN 的建構)

- [在這裏 RNN 扮演什麼角色？] 講 CNN 產生出來的 feature sequences 轉換成序列性的 label
- input: feature maps
- output: sequence of labels (e.g.)

#### RNN 的特色

* 一個講 RNN 不錯的網站: [link](https://baubibi.medium.com/速記ai課程-深度學習入門-二-954b0e473d7f)
* <font color='red'>**[優點]**</font> 使用 RNN 有三個優點
1. 擅長抓語意分析
* 基於圖片的背景資訊比符號資訊還要可靠
* 圖片的特徵可以讓模型分辨出模稜兩可的字，e.g. i & l
2. 能夠將誤差反向傳輸到上一層 (CNN layers)，所以才可以 end-to-end 訓練
3. 能夠作用在不定長度的內容
* <font color='blue'>**[缺點]**</font> 因為 RNN 容易 gradient vanishing
* 所以用 LSTM 比較會避免這個問題

#### 採用 LSTM

* [bi-directional] 但是 LSTM 是有方向性的，他會參考，但也只會參考過去的預測資訊；不過在影像問題可以用**雙向** LSTM 而且是很有幫助的
* 影像資料有個特別之處是個小格 input data 出現的順序跟時間沒有關係，不會因為在分析第 5 格 feature 的時候看不到第 6 格的 feature (至少在現在的應用場景是這樣)。因此，這裡的 LSTM 可以再加一個反過來做的 LSTM；也就是參考比較前面的 feature 然後回推上一個字是甚麼。所以，兩個合起來就會是雙向的 LSTM
* [deep] 而且，多個雙向 LSTM 是可以被疊再一起的，就會變成 <font color='red'>**deep bi-directional LSTM**</font>，深層的成效看起來比較好 (從語音的例子是這樣顯示的)
* [SPEECH RECOGNITION WITH DEEP RECURRENT NEURAL NETWORKS
](https://arxiv.org/pdf/1303.5778.pdf)

#### back-propagation in RNN case

* [BPTT] 在 RNN 的例子，要計算誤差時一樣是使用反向傳播法。因為 RNN 本來就是一層一層傳遞，因此計算反向誤差時方向就會是正向計算反向。又因為 RNN 的不同層就好比在不同時間發生，所以這時的反向傳播也常稱為 "back-propagation through time" **(時間性的反向傳播)**
* [Map-to-Sequence] 實際上，會製造一個叫做 Map-to-Sequence 的 神經網路層 ，當作 RNN 與 CNN 的橋樑，目的是將 RNN 的 feature sequences 變成 feature map 傳給 CNN

#### RNN 先前筆記區

- RNN 變形 (<font color='red'>RNN & LSTM & 雙向 LSTM & 深度雙向 LSTM 在應用上的差異?<<待釐清>></font>)
- RNN
- LSTM
- 雙向LSTM
- 在影象的序列中，兩個方向的上下文是相互有用且互補的
- 深雙向LSTM
- 在語音識別任務中取得了顯著的效能改進

### Transcription Layer (轉錄層)

- 目的：將 RNN 預測出來的值轉換成 label sequence
- 數學上的意思就是找到條件機率最大的那個 label sequence，已知 RNN 預測出來的值
- 實務上這邊有兩種模式
- lexicon-free transcription: 預測值不基於任何辭典 (直接組起來？)
- lexicon-based transcription: 從 lexicon 裡面挑出機率最高的那一個 (有點像分類問題？)
- 什麼是 lexicon？
- [answer] 就是辭典，一個收集很多詞彙的集合
- [e.g.]

    lexicon = {
        'hello world',
        'good morning',
        'I feel very hungry', ...
    }

#### 2.3.1 Probability of label sequence

* CTC Layer
* 當我們使用 negative log-likelihood 作為訓練目標的誤差函數，我們只需要圖片的 label sequence 以及 image data 本身，不需要針對上面一個一個字去人工標註
* 怎麼去對應？
* 一個 $\mathcal{B}$ 函數，會做兩件事情
1. 消除重複的 label
2. 把空白去除
* [e.g. ] $\mathcal{B}$("--hh-e-l-ll-oo--") = "hello"，其中 "-" 為空白的意思
* 想辦法調整參數讓下面這個條件機率最大化
* $p(\textbf{l}|\textbf{y}) = \sum\limits_{\pi: \mathcal{B}(\pi)=1}\,p(\pi|\textbf{y})$ --> Eq. 1
* $\textbf{l}$ = "hello"
* $\pi$ 就是經過消除重複、刪除空白後會變成 "hello" 的原始 label sequence，例如 "--hh-e-l-ll-oo--", "--h--e-l-ll-ooo--", ...
* $\textbf{y}$ 是一個長度為 $T$ 的向量，每一個分量都是一個機率分佈
* $\textbf{y} = (y_1, y_2, ..., y_T)$
* $p(\pi|y) = \prod\limits_{t=1}^T\,y_{\pi_t}^t$， 其中 $y_{\pi_t}^t$ 是在時間 $t$ 被預測為 $\pi_t$ 的機率
* 在我們的例子，時間 $t$ 意思是第 $t$ 張小格子圖
* $\pi_t$ 就是第 $t$ 個小格子圖被預測的值
* 最後利用 CTC 來最大化 Eq. 1

#### 2.3.2 Lexicon-free transcription

* 因為沒有 lexicon，所以就是找每個條件機率所對應到的 $\pi_t$，然後再把這些字組起來，也就是這個算式： $l^* \approx \mathcal{B}({argmax}_\pi\, p(\pi|y))$

#### 2.3.3 Lexicon-based transcription

* 因為有 lexicon，所以會用這種算式去極大化 $l^* \approx \mathcal{B}(arg\max\limits_{\textbf{l}\in\mathcal{D}}p(\textbf{l}|\textbf{y}))$
* 其中 $\mathcal{D}$ 就是辭典 (lexicon)
* 但是這樣子找 $\textbf{l}^*$ 是非常耗時的，所以會採取 lexicon-free 的方式先找到最一個 label ($\textbf{l}'$) ，然後再用 edit distance metric 去算一個集合，然後再去找這附近最像的
* $l^*=arg\max\limits_{\textbf{l}\in\mathcal{N}_{\delta}(\textbf{l}')}p(\textbf{l}|\textbf{y})$
* 這個集合 $\mathcal{N}_{\delta}(\textbf{l}')$ 就是在找候選字的意思
* 說用 B-K tree 可以找很快，運算複雜度是 $\mathcal{O}(log(|\mathcal{D}|))$
* 然後候選字跟正確答案的字，距離是 edit distance
* 新增
* 替換
* 刪除
* [e.g. ] $ED("123", "124") = 1$, $ED("123", "142" = 2)$

### 整個模型的 Loss 要怎麼計算？

* 誤差函數：$\mathcal{O} = -\sum\limits_{I_i, \mathcal{\mathcal{l}_i}\in \chi}log(P(\mathcal{l}_i, \textbf{y}_i))$ $\to$ 想辦法最小化這個值 ($\mathcal{O}$)
* 訓練資料在數學上我們這樣表示: $\chi = {(I_i, \mathcal{\mathcal{l}_i})}$，其中 $I_i$ 是影像資料的意思， $\mathcal{l}_i$ 是那個影像的正確答案
* end-to-end
* SGD
* back-propagation
* 用 ADADELTA 用調整不同維度的 learning-rate (這個意思是每個參數的更新速度不同嗎?)

* CTC 計算方式：[Connectionist temporal classification: labelling unseg- mented sequence data with recurrent neural networks.](https://www.cs.toronto.edu/~graves/icml_2006.pdf)

- 實驗
- Pooling 採用 1×2 大小的矩形池化視窗而不是傳統的正方形，有助於識別一些具有窄形狀的字元，例如i和l
- 在 convolutional layer 後加入 batch normalization layer 可讓訓練過程大大加快

## [code] [Belval/CRNN](https://github.com/Belval/CRNN)

### 程式大致架構

### data_manager.py

#### def load_data():

    def load_data(self):
        """Load all the images in the folder
        """

        print("Loading data")

        examples = []

        count = 0
        skipped = 0
        for f in os.listdir(self.examples_path):
            ### ----------------------------------
            # 圖檔的 label 是直接寫在檔名上
            # 後面帶隨機碼 (e.g., $1,000_a3hf.jpg)
            # 這樣的做法會有一些限制
            # 像是 110/03/09 就沒辦法在檔名上呈現，因為檔名不支援 /
            ### ----------------------------------
            # label 長度會根據 cnn 的 output 而定
            ### ----------------------------------
            if len(f.split("_")[0]) > self.max_char_count:
                continue
            ### ----------------------------------
            # resize_image 寫法詳見下方說明
            ### ----------------------------------
            arr, initial_len = resize_image(
                imread(os.path.join(self.examples_path, f), mode="L"),
                self.max_image_width,
            )
            examples.append(
                (
                    arr,
                    f.split("_")[0],
                    label_to_array(f.split("_")[0], self.char_vector),
                )
            )
            count += 1

        return examples, len(examples)

#### def resize_image(): (utils.py)
影像在丟進CRNN前，皆會轉為 32(高) x W(寬) 【在此用 W=200 示意】

- 如果影像的寬大於 200，會直接變形為 32 x 200
- 示意圖

- 範例圖

- 如果影像的高小於 32，會先等比例放大至高等於 32。接著若影像的寬大於 200，就會將圖截斷；反之，會將影像的寬補足至200 (補黑底)
- 示意圖

- 範例圖

----------------------------------------

#### def label_to_array(): (utils.py)

# 將各字元轉成對應的 index
def label_to_array(label, char_vector):
    try:
        return [char_vector.index(x) for x in label]
    except Exception as ex:
        print(label)
        raise ex

#### def generate_all_train_batches():

    def generate_all_train_batches(self):
        train_batches = []
        while not self.current_train_offset + self.batch_size > self.test_offset:
            old_offset = self.current_train_offset

            new_offset = self.current_train_offset + self.batch_size

            self.current_train_offset = new_offset
            # 根據 batch_size 產出 batch data
            raw_batch_x, raw_batch_y, raw_batch_la = zip(
                *self.data[old_offset:new_offset]
            )

            batch_y = np.reshape(np.array(raw_batch_y), (-1))
            
            ### ----------------------------------
            # 這邊不需要攤平
            # 錯誤寫法：
            #   batch_dt = sparse_tuple_from(np.reshape(np.array(raw_batch_la), (-1)))
            # 直接將各 label 對應的 index list 餵進 sparse_tuple_from() 即可
            # batch_dt 主要會產出 3 個東西：
            #  1. 每個字元是在第幾張圖中的第幾個位置
            #  2. 每個字元是在第幾張圖中，還有在 CHAR_VECTOR 中的 index
            #  3. (batch_size, batch data中最長的字元數)
            batch_dt = sparse_tuple_from(raw_batch_la)

            raw_batch_x = np.swapaxes(raw_batch_x, 1, 2)

            raw_batch_x = raw_batch_x / 255.0

            batch_x = np.reshape(
                np.array(raw_batch_x), (len(raw_batch_x), self.max_image_width, 32, 1)
            )

            train_batches.append((batch_y, batch_dt, batch_x))
        return train_batches

### crnn.py

* tensorflow 精神：先畫圖，再實際跑資料
* 先畫圖：在 python 上產生一堆變數，這些變數都是神經網路的框架，在 python 裡面就是 Tensor (這個時候 data 還沒進來喔！)
* 實際跑
* 定義 init 然後叫他 run

        session = tf.Session()
        with session.as_default():
            output, input, init = nn(a, b, c)# 等一下要跑的網路架構
            init.run()

* 初始化： tf.Session().as_default()
* 餵入資料開始在網路架構執行

        real_cnn_output = session.run([cnn_output],
                              feed_dict={
                                  inputs: train_batches[0][2]
                              }
                             )

#### 看 code 可能會有的問題

* 到底我這樣 train 最多會預測多長的字元？
* A: 在這個 code 的例子會是 seq_len = (max_image_width $\div$ 4) $- 1$，原因是 CNN 的網路結構讓最後的 feature map 的形狀是這樣；如果是不同的疊法可能會產生不同的 shape，那麼最大字元數也會不同
* $\div$ <font color='red'>**4**</font> 的意義是，原始圖片的可辨識最小字元至少要 4 個 pixels；再小的話就無法被訓練，當然也無法預測
* CNN 層如何 output 給 RNN 層？
* 就是 CNN output 的 feature maps 轉換成 RNN 要 input 的形狀，方式不拘。在我們的例子是 tf.Squeeze，效果如下

cnn_output #<tf.Tensor 'conv2d_104/Relu:0' shape=(?, 49, 1, 512) dtype=float32>
rnn_input = tf.squeeze(cnn_output, [2])
'''
把位置 2 的 1 給壓縮掉
'''
rnn_input #<tf.Tensor 'Squeeze_2:0' shape=(?, 49, 512) dtype=float32>

#### 常見的 tensorflow 指令

##### 1. 神經元
* tf.placeholder (預設 Tensor 的形狀，給 input data 用的)
* tf.Variable (裡面的值會在過程中被更新)
* tf.constant (常數項)
* tf.nn.ctc_loss (loss 也是神經元之一喔！因為他要被更新)
* tf.nn.ctc_beam_search_decoder

##### 2. 網路架構運算法
* tf.layers.conv2d
* tf.layers.max_pooling2d
* tf.nn.relu
* tf.layers.batch_normalization
* tf.nn.rnn_cell.BasicLSTMCell
* tf.nn.bidirectional_dynamic_rnn

##### 3. 看起好像很可怕，其實就是 numpy 的指令
* tf.matmul
* tf.add
* tf.concat
* tf.reshape
* tf.reduce_mean
* tf.transpose
* tf.Squeeze
* ......

##### 4. 運算指令
* tf.global_variables_initializer
* tf.Session
* tf.Session().as_default()
* tf.Session().run()
* tf.train
* tf.train.Saver
* tf.train.AdamOptimizer

## 提問區

|姓名|問題|解答|
| - | - |-|
| 昊中 | CRNN模型的input data是不是無法直接輸入多行文字影像?得先手動將文字切成一列一列的?|對，每個 frame 只會預測一個字元，所以實務上沒辦法預測多行文字的影像，要先切好|
| 沛筠 | 目前Map-to-Sequence的方式除了Squeeze之外，還有其他的嗎？ |其實是有的，只是在這裡的用法是直接合併然後將資料餵給 RNN，當然也可以在 CNN output 之後做一個矩陣相乘然後再給 RNN ；只是還是要符合某些形狀。e.g. 在我們的例子是 24 x 1 x 512 (tf.Squeeze)$\to$ 24 x 512 $\to$ RNN，也可以嘗試這樣 24 x 1 x 512 (tf.matmul)$\to$ 24 x 1024 $\to$ RNN|
| Track 2 | 1. 論文裡的 Figure 2. 說到 feature sequence 的每一個 vector 都對應到圖片的其中一區的感受視野 (receptive field)，好奇為什麼是一個 feature sequence 對應某幾個 columns 而不是全部的圖 (過程中每個 kernel 不都會掃過整個 feature maps 嗎？)<br>2. 想要再聽一次宜昌版本的 CTC loss 解說，beam search 是什麼？|1. 詳見附錄1<br>2. 宜昌老師說請先看這篇: [answer](https://www.ycc.idv.tw/crnn-ctc.html)(昱睿)|
| 信賢 | 1.(講者準備的資料)想詢問resize若有補黑底，不會造成訓練不準嗎？<br>2.(第8頁table 4.)是說CRNN對於真實的圖像反而表現比較好？但清楚的影像反而比較差@@ 不太能理解 |1. 黑底可以把它想成和白底一樣，都是無意義的背景，所以在萃取feature的時候，黑底的部分就不會是重要資訊<br>2. paper 中並無針對三種資料的訓練集和測試集多做描述，但若以實務來看，乾淨的樂譜的準確度應該要較高才對|
|軒彤|我現場版||
|倚任副理|1. SIFT 的 output 怎麼變成 sequence 餵進 RNN？||

- 附錄1

- 補充
- CRNN 可以處理任意長度的序列，此外不需要字元分割、scaling 以及 normalization (CRNN中切小圖的CNN的寬是固定的還是會根據整張圖的寬而切大小的小圖?)

- scaling (min-max scaling) [(詳細說明)](https://kharshit.github.io/blog/2018/03/23/scaling-vs-normalization)
$$ x' = \frac{x-xmin}{xmax-xmin} $$

- normalizationl (符合常態分布)
$$ x' = \frac{x-xmean}{xmax-xmin} $$