---
# System prepended metadata

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

---

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

###### tags: `paper`

![](https://i.imgur.com/hKdrq2V.png)

# Retrieve Image Feature

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

### Histogram Equalization
![](https://i.imgur.com/xVa3omn.png)
上圖是灰階值的分布頻率，峰值靠左或靠右象徵影像偏亮或偏暗，靠中間就是明暗的對比不明顯，做Histogram Equalization的目的就是要讓影像的Histogram均勻。
(左至右)![](https://i.imgur.com/4UKdmFD.png) ![](https://i.imgur.com/uq3wwx1.png)


### 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)]]$$

![](https://i.imgur.com/QodtPmO.png =60%x)

![](https://i.imgur.com/2dm6dML.png =60%x)

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

![](https://i.imgur.com/r5fR2P6.png =60%x)


* 做Fourier transform

![](https://i.imgur.com/MYGtoKD.png =50%x)

![](https://i.imgur.com/1hGfrw8.png =50%x)

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

![](https://i.imgur.com/HBOmv5H.png =50%x)

## 2. Retinal Feature Extraction

* 取出skeleton
![](https://i.imgur.com/cF4PcZU.png)
$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}$









