본 논문은 CVPR 2018에 게재된 Scene Text Recognition 태스크에 대한 논문으로 동일한 하기 논문의 저자들이 수행한 후속 연구이다
Cheng, Zhanzhan, et al. "Focusing attention: Towards accurate text recognition in natural images."Proceedings of the IEEE International Conference on Computer Vision. 2017.
Introduction
Goal
본 논문은 논문 저자들의 이전 논문과 마찬가지로 attention과 GT string 간의 mis-alignment 문제를 해결하고자 한다.(저자들이 이전 논문에서 attention drift problem이라 명명함.)
Motivation
이전 논문에서는 해당 문제를 학습할 때 attention 영역에 음절 단위의 supervision loss를 직접 주는 방식으로 해결했는데, 이러한 방식은 학습 데이터에 음절 단위의 localization GT가 있어야 한다는 제약조건이 있다. 본 논문에서는 그러한 제약 조건없이도 mis-alignment 문제를 해결할 수 있는 방법을 제안한다.
위 그림의 예시에서 각 column 벡터는 decoder의 출력, probablity distributuib(pd)를 나타내고, 이들 pd 셀의 색이 진할 수록 해당 셀에 해당하는 문자의 확률이 높은 것을 의미한다. pd 시퀀스의 하단에 있는 문자는 GT string이다. (a)의 예시는 가장 높은 값의 pd 출력에서 'O'가 빠진 경우이고,(='missing') (b)의 경우는 'O'가 하나더 추가된 경우(='superfluous')이다. 두 경우 모두 pd 시퀀스와 GT 간의 mis-alignment가 발생한다. 하지만, (a)의 경우 'O'가 missing 되고, (b)의 경우 'O'가 superfluous 하다는 것을 감안하고 해당 pd를 GT와 매칭 시키면, 나머지 시퀀스 간에는 매칭이 잘 된다는 것을 알 수 있다. 따라서, 새로운 alignment에서 missing/superfluos 문자 'O'에만 집중한 다면 학습 과정이 훨씬 간단해질 수 있다.
본 논문에서는 위 현상을 관찰하고, attention-based encoder-decoder 구조에서 probability distribution과 GT string 간의 dissimilarity를 재는 metric인 edit probability(EP)를 이용한 학습 방법을 제안하였다. (EP는 문자 시퀀스간의 거리 metric인 edit distance에서 힌트를 얻은 개념임) EP는 학습과정에서 현재 출력의 pd 시퀀스에 conditioning하여 missing/superfluous된 문자가 있다고 가정할 때의 문자 출력 시퀀스를 예측한다. 이러한 방식의 이점은 학습 프로세스에서 모델이 오직 missing, superfluous, mis-classified된 문자에만 집중하고, mis-alignment의 효과는 줄어들게 된다는 것이다. 결과적으로, 학습된 모델의 recognition 성능이 비약적으로 증가된다.
Contributions
attention-based Recognition 모델에서 발생하는 GT string과 output 간의 mis-alignment 문제를 edit probability라는 metric을 제안하여, 학습과정에서 missing, superfluous 문자를 고려한 output 예측을 하여, 모델 학습이 mis-alignmen에 덜 민감하게 반응하고, missing, superfluois 문자에 집중 하도록 하였다.
그 결과 Scene Text Recognition Task에서 SOTA를 달성.
Proposed Method
The EP Method
Edit Probability는 주어진 이미지 I에 conditioning된 텍스트 T의 확률을 model 파라미터 theta에 의해 구하는 것을 의미한다. 이것은 pd 시퀀스에 y에 기반하여 empty string에서 T로 변환하는 모델에 의해 생성가능 한 모든 edit path 들의 합과 같다. edit path에 대해서는 아래 절에서 좀 더 자세히 설명한다.
EP-based Attention Decoder
기존의 attention decoder와 관련된 수식들은 다음과 같다.
(자세한 설명은 논문의 reference[4]: D. Bahdanau, J. Chorowski, D. Serdyuk, Y. Bengio, et al. End-to-end attention-based large vocabulary speech recog- nition. In ICASSP, pages 4945–4949, 2016. 또는 저자들의 이전 논문 참고.)
제안 방법에서는 기존의 attention decoder 구조에 EP(Edit Probability) 계산을 위해 아래의 모듈들을 추가한다. j번째 스텝에서 아래의 R_j 와 I_j 가 추가로 출력된다.
이 때, W_R과 W_I는 모두 trainable parameter들이다.(FC layer로 구현 가능.)
R^C, R^I, R^D는 각각 j번째 스텝에서 pd y_j 가 being correctly aligned, a character being missing before y_j and y_j being superfluous 경우에 해당할 확률을 의미한다.
I_j는 문자가 missing인 경우(=conditioned on R^I), missing된 문자들의 pd를 나타낸다.
Edit Probability
수식적으로 표현하기 위해 아래와 같이 character와 string 들의 set, 그리고 edit states을 정의한다.
Edit Operation는 다음과 같이 정의된다.
Consumption
Consumption operation은 T와 y의 index를 각각 1개씩 전진시킨다. 이 operation의 확률은 consumption operation의 확률 R^C와 j번째 pd y에서 T_i에 해당하는 문자의 확률을 곱한 것과 같다.
Deletion
Deletion operation은 T의 인덱스는 유지 한채 , y의 인덱스만 전진시키는 operation이다. 이 operation의 확률은 T_i가 EOS(#, End of Sentence)에 이미 도달했을 때는 항상 1이 되고, 그렇지 않을 때는 R^D의 확률을 가진다.
Insertion
Insertion은 y의 인덱스는 유지한채, T의 인덱스만 전진시키는 operation이다. 이 operation의 확률은 y_j가 이미 가능한 길이의 끝에 도달한 경우, insertion만이 오직 가능한 operation이 되어, 이 때의 확률은 I_j에서 예측된 missing된 문자들의 pd에서 Ti에 해당하는 확률이 된다. 만일, y_j가 아직 끝에 도달하지 않은 경우는 앞선 경우에서 해당 operation에 대한 예측값 R_I를 곱하여 구한다.
Edit operation 들의 조합의 결과로 나타나는 edit path E의 확률은, T와 y에 대한 모든 edit operation이 conditional independent하다고 가정할 때 다음과 같이 계산할 수 있다.
Edit probability of states(T_1:i, y_1:j)는 ("",y_1:0)에서 (T_1:i, y_1:j) 로 변환하는 모든 edit path들의 conditional probability의 합과 같다.
하지만, 모든 가능한 edit path들을 계산하는 것은 매우 넓은 검색 공간을 찾아야 되는 문제가 발생한다. 이 문제는 수식 (9)로 부터 유도된 dynamic programming으로 해결할 수 있다.
아래의 그림은 Edit Probability 계산을 하는 과정을 도식화 한 예시이다.
EP Training
EP 학습은 edit probablity의 negative log-likelihood를 minimize 하는 모델 파라미터 theta_hat을 찾는 것을 목적 함수로 한다.
EP Predicting
EP predicting은 edit probability를 최대화 하는 string T^을 찾는 것이다.
하지만 일반적으로 위 수식에서 모든 string set에 대해 optimal T를 찾는 과정은 매우 연산량이 많이 드는 과정이다. 따라서, 논문에서는 lexicon이 주어진 경우와 주어지지 않은 경우에 대해서 효율적인 계산 방법을 제시한다.
Predicting without lexicon
저자들이 prediction 문제를 깊게 분석한 결과(=이 말은 "이론적인 근거는 없지만 경험상 해보니"와 동일), 일반적으로 수식 (16) optimal string T^은 ("",y_1:0) 을 (T,y)로 변환하는 most probable edit path에 해당 하는 string T 의 prefix에 해당하는 것을 발견하였다.
따라서, 먼저, most probable edit path에 해당 하는 string T를 찾는다. 단, 이 때 주의할 점은 해당 edit path에 non-EOS insertion operation이 포함될 경우, 추가된 insertion을 제거후, 이전 보다 더 높은 conditional probability를 가진 새로운 edit path를 얻게 되므로, non-EOS insertion operation이 포함된 path는 제외한다. (insertion은 deletion에 의해 무효화 되므로, insertion과 deletion operation 중 한가지만 허용해야되는 건 알겠는데, 새로운 edit path가 더 높은 conditional probability를 가지게된다는 부분은 이해가 안됨.)
다음, T의 모든 prefix들을 candidate set B로 정의한다.
위 셋의 string 중에서, edit probability를 최대화 하는 string을 찾는다.
Predicting with a lexicon
Lexicon이 제한된 경우의 경우, 입력 영상의 string이 lexicon D에 포함되지 않는 경우를 고려해서, lexicon set D와 most probable edit path string T의 prefix set(=B eq (18))의 교집합을 전체 search space로 정의한 후, 다음과 같은 수식을 통해 string T^을 구한다.
위 수식에서 람다는 [0.5, 1]의 범위를 가지며, 1에 가까울 수록 lexicon D에 포함된 string이 선택될 확률이 높아진다.
하지만, lexicon의 크기가 커질 수록 EP를 구하는데 드는 연산량이 크게 늘어나므로, 제안 방법에서는 Shi et al.이 제안한 a prefix tree(Trie)를 변형한 edit probablity Trie(EP-Trie) 방법을 제안하였다. 이 방법에서는 각 노드가 prefix S를 공유하는 것과 동시에 ep(S, y_1:j) 벡터를 함께 저장한다.
Experiment
Comparison with Existing Methods
제안 방법의 기존의 attention based 방법에 EP-based training/predicting을 적용하는 것으로 구현가능하다. 따라서, 기존의 2가지 work[7,32]을 baseline으로 삼고, 여기에 EP를 적용한 결과를 비교하였다. 그 결과, EP는 baseline에 비해 일관되게, 성능이 향상되었고, 특히, lexicon-free 방식에서 성능 개선의 폭이 매우 컸다. 제안 방법은 대부분의 부분에서 SOTA를 달성하였다.
Performance of EP Training
기존 방법(Framewise Probability, FP)는 mis-align이 발생하면, 그 값이 매우 크게 떨어진다. 하지만, EP의 경우, 상대적으로 훨씬 높은 값을 유지한다. 또한, insertion, deletion에 의한 probability가 가장 높은 값을 가지는 것을 확인 할 수 있다.
Performance of EP prediction
제안 방법에서 람다는 기존 방법과 EP 방식의 결과를 선택할 확률을 조정하는 파라미터이다. lexicon이 있는 데이터셋에서 람다가 1에 매우 가까울 경우, over-correction에 의해 성능이 오히려 급격히 떨어지는데, 0.9~0.98 사이의 범위에 이를 때 까지는 람다에 비례해서 성능이 향상되는 것을 알 수 있다. 즉, groud-truth-unrelatred lexicon을 사용하는 EP 방식이 lexicon이 존재하는 경우에도 도움이 된다는 것을 보여 준다.
마지막으로, prediction을 위한 EP-Trie-based prediction의 경우, 50k lexicon에서 full search와 정확도는 완전히 동일하지만, 연산속도는 2.566 sec vs. 0.11 sec로 훨씬 빠른 것으로 나타났다.
Conclusions
제안 방법은 기존의 attention based recognition 태스크에서 mis-alignment가 학습에 부정적으로 미치는 영향을 제거하고, 기존 구조에 간단히 덧붙여 사용할 수 있는 EP 방법을 제안하여, recognition 성능을 크게 향상시켰다. 제안된 EP 방식은 문자 인식 뿐만이 아니라 machine translation, speech recognition image/video caption 등의 다른 태스크에도 적용될 수 있을 것으로 기대된다.
