Abstract
Person re-identification에 있어서 re-ranking은 accuracy를 향상시키는 데 중요한 역할을 한다. 본 논문에서는 K-reciprocal encoding method를 통해 re-ID results를 re-ranking 하는 것을 제안한다.
Introduction
RE-Ranking이란 person re-ID initial result를 re-ranking하여 query(probe)와 관련된 이미지들이 더 좋은 rank를 받아 재정렬 될 수 있도록 한다. 이는 추가적인 training samples를 필요로 하지 않다는 이점을 가지고 있고 어떠한 initial ranking result에도 적용할 수 있다는 이점을 가지고 있다.
Re-Ranking의 결과는 initial ranking list에 대해 의존성이 크다. 이전의 논문들이 re-ranking을 하는데 있어서 주로 K-neareast neighbors를 이용하였다. 구체적으로, K-nearest neighbors안에 존재하는 이미지들은 true-match일 가능성이 크다는 사실에 기반하였다.
하지만 위 그림에서도 볼 수 있듯이 P1,P2,P3,P4는 true-match임에도 불구하고 top rank 4에 들지 못하였고 오히려 N1, N2가 top rank 4에 들어있는 것을 확인할 수 있다. 이를 통해서 K-nearest neighbor의 결과를 re-ranking에 바로 사용하는 것은 적절하지 않다는 것을 알 수 있다.
이러한 문제점을 해결하기 위해 K-reciprocal nearest neighbor를 사용하고자 한다. 어떤 두 이미지(A, B)가 k-reciprocal nearest neighbor 관계에 있으려면, A가 probe가 되었을 때 K nearest neighbor 결과 안에 B 가 속해있어야 하고 마찬가지로 B가 probe가 되었을 때 K nearest neighbor 결과 안에 A가 속해있어야 한다. 본 논문에서는 K-reciprocal nearest neighbor관계에 있으면 서로 true-match일 가능성이 크다는 가정을 하였다.
본 논문에서는 re-ID ranking을 위해 다음과 같은 process를 제안한다.
1. weighted K-reciprocal neighbor 집합을 vector로 encoding
2. K-reciprocal vectors를 이용하여 Jaccard distance 계산
3. re-ID results 정확도를 높이기 위하여 Local query expansion
4. Final distance = original distance와 Jaccard distance 간의 aggregation
아래의 그림은 4가지 단계를 visualize한 것이다.
가 있다고 가정하자.
p와 gi사이의 original distance는 다음과 같이 Mahalanobis distance로 계산될 수 있다.
여기서 M은 semidefinite matrix(양의 정부호 행렬)이다.
Initiali ranking List
는 p와 gi 사이의 original distance 를 오름차순으로 정렬하여 얻어질 수 있다. 본 논문에서는 L(p, G)를 re-ranking하여 true-match들을 top rank에 들 수 있도록 하여 성능을 높이도록 한다.
이렇게 얻어진 R*(p, k)를 바로 top ranked images라고 간주하지 않는다. Probe와 Gallery 사이의 distance를 re-calculate해주는 contextual knowledge라고 한다.
R *(p, k)와 R *(gi, k)를 차례로 구한다음 위와 같이 p와 gi 사이의 jaccard distance를 계산할 수 있다. 이는 두 이미지 사이의 similarity relationships를 나타낸다. 하지만 다음과 같은 치명적인 단점들이 존재한다.
1. R *(p, k)와 R *(gi, k)를 계산하는데 엄청나게 시간이 오래걸린다. i=0, 1, 2, .... N(number of gallery images) 라고 생각해보면 time-consuming한 process임이 분명하다.
따라서 위와같은 집합을 vector form으로 encoding하여 computational cost를 줄이도록 한다.
2. 기존에는 모든 neighbor에 대해 가중치를 동일하게 줘서 discriminative하지 못한 neighbor set을 가지고 있었다. probe에 가까운 neighbor일 수록 true-positive일 가능성이 높기 때문에 original distance에 따라 가까운 neighbor일 수록 더 큰 가중치를 부여해준다.
3. 두 image간의 similarity 를 비교하는데 단순히 contextual information만을 고려하는 것은 다양한 variation이 있을 수 있으므로 robust한 distance가 될 수 없다. 따라서 original distance와 Jaccard distance의 aggregation으로 final distance 를 계산한다.
앞서 말한 1,2 번 문제들을 해결하기 위하여 k-reciprocal feature 을 도입한다. 즉, K-reciprocal nearest neighbor set을 vector Vp로 아래와 같이 encoding해준다.
이 때, 위의 벡터는 N-dimensional vector이며 각 원소가 R*(p, k)에 속하면 값이 1이 되도록 한다. 하지만 위와 같은 binary indicator는 각각의 neighbor에 대해서 가중치를 두지 않고 동등하게 간주하고 있다. 직관적으로 probe p와 더 가까운 neighbor는 p와 더 비슷하므로 original distance를 이용하여 가중치를 다음과 같이 부여하여 아래와 같이 재정의 하였다.
즉, p에 가까운 neighbor에 대해서는 더 큰 weight를 부여해주고 먼 neighbor에 대해서는 작은 weight를 부여해주도록 하였다.
따라서 Jaccard distance를 계산할 때 아래와 같이 vector 수식 으로 바꿀 수 있다.
min과 max는 element wise minimization과 maxmization을 의미하고 ||1는 L1 norm을 의미한다. 이에 따라 Jaccard distance는 다음과 같이 표현된다.
4. Final distance = original distance와 Jaccard distance 간의 aggregation
아래의 그림은 4가지 단계를 visualize한 것이다.
Proposed Approach
Problem Definition
probe p와 gallery set(N개의 image)
가 있다고 가정하자.p와 gi사이의 original distance는 다음과 같이 Mahalanobis distance로 계산될 수 있다.
여기서 M은 semidefinite matrix(양의 정부호 행렬)이다.
Initiali ranking List
는 p와 gi 사이의 original distance 를 오름차순으로 정렬하여 얻어질 수 있다. 본 논문에서는 L(p, G)를 re-ranking하여 true-match들을 top rank에 들 수 있도록 하여 성능을 높이도록 한다.K-reciprocal Nearest Neighbors
N(p, K)를 p에 대한 k-nearest neighbors라고 하자. 이는 다음과 같은 수식으로 나타낼 수 있다.
여기서 | | 는 집합의 원소의 개수 이다.
다
다음으로 K-reciprocal nearest neighbors를 R(p, k)라고 하면 다음과 같은 수식으로 나타낼 수 있다.
앞서 언급했던 것처럼 K-reciprocal nearest neigbors는 k-nearest neighbors보다는 더 정확한 true-match를 제공해 줄 수 있다. 하지만 true-match가 K-nearest neighbors 안에 속해있지 않아서 결과적으로 K-reciprocal nearest neighbors에도 속하지 않게 되는 문제가 존재한다.
이러한 문제를 해결하기 위해 아래와 같은 과정을 거쳐 p에 대한 positivie samples를 조금 더 확보할 수 있게 하였다.다
아래의 그림은 예시를 통해 R*(p, k)를 얻는 과정을 설명한 것이다.
이렇게 얻어진 R*(p, k)를 바로 top ranked images라고 간주하지 않는다. Probe와 Gallery 사이의 distance를 re-calculate해주는 contextual knowledge라고 한다.
Jaccard Distance
R *(p, k)와 R *(gi, k)를 차례로 구한다음 위와 같이 p와 gi 사이의 jaccard distance를 계산할 수 있다. 이는 두 이미지 사이의 similarity relationships를 나타낸다. 하지만 다음과 같은 치명적인 단점들이 존재한다.
1. R *(p, k)와 R *(gi, k)를 계산하는데 엄청나게 시간이 오래걸린다. i=0, 1, 2, .... N(number of gallery images) 라고 생각해보면 time-consuming한 process임이 분명하다.
따라서 위와같은 집합을 vector form으로 encoding하여 computational cost를 줄이도록 한다.
2. 기존에는 모든 neighbor에 대해 가중치를 동일하게 줘서 discriminative하지 못한 neighbor set을 가지고 있었다. probe에 가까운 neighbor일 수록 true-positive일 가능성이 높기 때문에 original distance에 따라 가까운 neighbor일 수록 더 큰 가중치를 부여해준다.
3. 두 image간의 similarity 를 비교하는데 단순히 contextual information만을 고려하는 것은 다양한 variation이 있을 수 있으므로 robust한 distance가 될 수 없다. 따라서 original distance와 Jaccard distance의 aggregation으로 final distance 를 계산한다.
앞서 말한 1,2 번 문제들을 해결하기 위하여 k-reciprocal feature 을 도입한다. 즉, K-reciprocal nearest neighbor set을 vector Vp로 아래와 같이 encoding해준다.
이 때, 위의 벡터는 N-dimensional vector이며 각 원소가 R*(p, k)에 속하면 값이 1이 되도록 한다. 하지만 위와 같은 binary indicator는 각각의 neighbor에 대해서 가중치를 두지 않고 동등하게 간주하고 있다. 직관적으로 probe p와 더 가까운 neighbor는 p와 더 비슷하므로 original distance를 이용하여 가중치를 다음과 같이 부여하여 아래와 같이 재정의 하였다.
즉, p에 가까운 neighbor에 대해서는 더 큰 weight를 부여해주고 먼 neighbor에 대해서는 작은 weight를 부여해주도록 하였다.
따라서 Jaccard distance를 계산할 때 아래와 같이 vector 수식 으로 바꿀 수 있다.
min과 max는 element wise minimization과 maxmization을 의미하고 ||1는 L1 norm을 의미한다. 이에 따라 Jaccard distance는 다음과 같이 표현된다.
Local Query Expansion
same class imagesms 비슷한 features를 share한다는 아이디어에 착안하여 K-nearest neighbors를 이용하여 local query expansion을 한다.
결과적으로 K-reciprocal feature Vp는 p의 K-nearest neighbors를 이용하여 expand된다. K-nearest neighbors에 noise가 있을 수 있기 때문에 N(p, k)의 size를 줄여서 query expansion을 진행하였다.
R *(gi, k)의 size는 k1이라고 하고 N(p, k)의 size는 k2라고 하겠다.
Final distance
Final distance는 original distance와 Jaccard distance의 aggregation으로 다음과 같이 나타내어진다.
이 때 
는 penalty factor로써 p로부터 멀리 떨어져 있는 gallery image에 대해서 penalty를 부여한다. 값이 0이면 K-reciprocal distnace만 고려하고 1이면 original distance만 고려한다. 이렇게 구해진 d*(p, gi)를 오름차순으로 정렬하고 i=0,1,2,3....N까지 계산하여 
를 구할 수 있게된다.
는 penalty factor로써 p로부터 멀리 떨어져 있는 gallery image에 대해서 penalty를 부여한다. 값이 0이면 K-reciprocal distnace만 고려하고 1이면 original distance만 고려한다. 이렇게 구해진 d*(p, gi)를 오름차순으로 정렬하고 i=0,1,2,3....N까지 계산하여 
를 구할 수 있게된다.
댓글
댓글 쓰기