# [Retina Verification System Based on Biometric Graph Matching](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6523153)

###### tags: `paper`


# Retrieve Image Feature

## 1. Retinal Image Enhancement
影像前處理，目的是要加強血管的特徵，共兩步驟，第一步是先進行Histogram Equalization，第二步是matched filter detection。

### Histogram Equalization
上圖是灰階值的分布頻率，峰值靠左或靠右象徵影像偏亮或偏暗，靠中間就是明暗的對比不明顯，做Histogram Equalization的目的就是要讓影像的Histogram均勻。
(左至右) 

### matched filter detection
基本上就是把下面的式子做Fourier Transform，這樣把convolution變成相乘，再inverse transform回來
* $$o(x,y) = \max_\theta[i(x,y)*g_\theta(x,y)]=\max_\theta \Re[F^{-1}[I(l_1,l_2)G_\theta(u,v)]]$$



$\theta$有六個，每個增加$\pi/6$


* 做Fourier transform



* 下一步把大於threshold的值=1，小於的=0，形成binary image


## 2. Retinal Feature Extraction

* 取出skeleton
$i_s = $
$i_b^p=(i_b\ominus pw)-(i_b\ominus pw)\circ w$
$N_s=\max\{p|(i_b\ominus pw) \neq \phi\}$

上式是取出骨架標準式，查Lantuéjoul's formula可以找到相關資料
$\ominus$符號為侵蝕運算，$\circ$為開運算
$i_b\ominus pw$的意思是對影像使用structure element(或者說kernel)w進行侵蝕運算，連續侵蝕p次
所謂的開運算則是侵蝕之後再膨脹

這篇論文所使用的是3\*3的kernel

# Graph Matching

1. 把2張要match的graph(g和g')找到最好的起始點做對齊

Step1.
計算2個graph之間兩兩edge dissimilarity的分數
$$s_{ab}=\frac{1}{0.5(l_a+l_b^{'})}\sqrt{(l_a-l_b^{'})^2+(\theta_a-\theta_b^{'})^2}$$
把剛剛計算所有的$s_{ab}$做increasing排序，因為分數越低代表2個edge個性越接近

Step2.
根據剛剛排序後的pair取N組來計算哪一組edge最適合做對齊標準。
iteration:
把目前選到的edge當x軸，並把兩張圖的vertices兩兩配對計算分數
if $\sqrt{((q_1)_i-(q_1^{'})_j)^2 + ((q_2)_i-(q_2^{'})_j)^2} <= \epsilon$:
C += 1;
這裡要把有配過的vertices label成matched，直到換下一組edge
才恢復unmatched。
$d_k(g_o, g_o^{'}) = 1 - \frac{C}{\sqrt{m \times m^{'}}}$
如果選到比較好的起點就記錄

2. Error-Tolerant Graph Matching Module
* 先製作cost matrix，也就是把g換成g'會差多少值
$\left(
\begin{array}{cc}
C_1 & C_2 \\
C_3 & C_4 \\
\end{array}
\right)$

$C_1 = [c_{ij}|1\leq i\leq m, 1\leq j\leq m^{'}]$
$C_1:$ $c_{ij} = \sqrt{((q_1)_i-(q_1^{'})_j)^2 + ((q_2)_i-(q_2^{'})_j)^2}$

$C_2\ C_3$ are diagonal matrix with outside the diagonal are $\infty$
$C_2:$ $c_{\delta j}=C_{ID}(1+D(v^{'}_j))$
$C_3:$ $c_{i\delta}=C_{ID}(1+D(v^{'}_j))$
$C_4:$ All zero matrix

[來源在此](https://bougleux.users.greyc.fr/articles/ssspr14-approxged.pdf)

## 補充 maximum common subgraph(**Hungarian Algorithm**)

[參考影片](https://www.youtube.com/watch?v=cQ5MsiGaDY8)
[參考連結](https://blog.csdn.net/u014754127/article/details/78086014)
* input: cost matrix
$\left(
\begin{array}{ccc}
40 & 60 & 15 \\
25 & 30 & 45 \\
55 & 30 & 25 \\
\end{array}
\right)$

1. Find the minimum of each row

$\left(
\begin{array}{ccc}
40 & 60 & 15 \\
25 & 30 & 45 \\
55 & 30 & 25 \\
\end{array}
\right)$

15
25
25

2. column reduction

$\left(
\begin{array}{ccc}
25 & 45 & 0 \\
0 & 5 & 20 \\
30 & 5 & 0 \\
\end{array}
\right)$

min of each column
0 5 0

3. test for an optimal assigment
用最少直線包含全部的0，至少要有m條(這裡m=3)

$\left(
\begin{array}{ccc}
25 & 40 & 0 \\
0 & 0 & 20 \\
30 & 0 & 0 \\
\end{array}
\right)$

>[color=#00a000]
>
>最少直線的選法可以用Greedy 的方式：依序選擇覆蓋最多「還沒被覆蓋的」0的直線
>[name=Omnom]

4. (maybe don't need to do)
shift zeros

find the smallest uncovered value: X

uncovered values減去X
intersection 加上X

這裡只有兩條直線，所以要把0移到其他地方來創造最多的直線

$\left(
\begin{array}{ccc}
15 & 15 & 0 \\
0 & 0 & 10 \\
5 & 5 & 0 \\
\end{array}
\right)$

$\left(
\begin{array}{ccc}
10 & 10 & 0 \\
0 & 0 & 15 \\
0 & 0 & 0 \\
\end{array}
\right)$

>[color=#00a000]
>
>如果說要找所有的解，可以先看哪些列、行只有一個0，
>那種0就只有一種對應方式。
>
>然後把關於該0的列、行刪除，
>接下來繼續判斷有哪些可能的對應方式。
>
>以下圖為例，假設$row:\{A,B,C,D\}$ match $col:\{1,2,3,4\}$
>$\left(
>\begin{array}{ccc}
>0 & 0 & & 0\\
>0 & 0 & & 0\\
> & & 0 & 0\\
>0 & & 0 & \\
>\end{array}
>\right)$
>
>``` graphviz
>digraph hierarchy{
> A1->B2->C4->D3[color=red]
> A2->B1->C4->D3[color=blue]
> A2->B4->C3->D1[color=blue]
> A4->B2->C3->D1[color=darkGreen]
>}
>```
>[name=Omnom]

最後的計算:
1.
$$d_v = 1 - \frac{|mcs(g_a, g_a^{'})|}{\sqrt{|g_a||g_a^{'}|}}$$

2.
$$d_c = 1 - \frac{\sum_{i=1}^2 C_i}{\sqrt{|g_a||g_a^{'}|}}$$
$C_i$ is the number of vertices in the $i^{th}$ largest connected component in $mcs(g_a, g_a^{'})$

3.
$D_{max} = max(D(v_k)), k=1,2,...,|mcs(g_a, g_a^{'})|$

# Experiments

* VARIA database

* parameters to be tuned:
* number of most similar edge pairs $N_i$
* toerance $\epsilon$
* cost $C_{ID}$

A. Single Graph Measure
這裡他使用$d_v$來當衡量標準
* FMR: false match rate
* FNMR: false non-match rate
* EER(equal error rate): The rate at which FMR is equal to FNMR.

* KDE(kernel density estimation): estimate probability density function.
* Bandwidth of KDE: mean integrated squared error

B. Multiple Graph Measure
這裡使用$d_c$、$d_v$、$D_{max}$