[Diffusion] Image Retrieval SOTA 논문 & 코드 파악
이번 포스팅은 Image Retireval 분야에서
상위에 랭킹한 Offline Diffusion에 관한 코드를
파악하고 실행하는 포스팅입니다.
Image Retrieval SOTA
Image Retrieval on Oxf5k 분야에서 가장 상위에 rank하고 있는 Offline Diffusion
Papers with Code - Oxf5k Leaderboard
Papers with Code - Oxf5k Leaderboard
The current state-of-the-art on Oxf5k is Offline Diffusion. See a full comparison of 5 papers with code.
paperswithcode.com
가장 상위에 rank 한 방법의 논문과 깃허브를 참고하여 관련 내용을 파악하고 적용 할 예정. 논문이 실제로 구현 된 깃허브가 존재하므로 구현 코드를 파악 및 정리
- 논문 : https://arxiv.org/pdf/1811.10907v2.pdf
- 깃허브 : https://github.com/fyang93/diffusion
- Result
Diffusion에 사용되는 파일 확장자
pkl 파일이란,
일반 텍스트를 저장 할때는 파일 입출력 사용
리스트나 클래스와 같은 자료형 저장을 하기위해 pickle 모듈 제공
import pickle
data = ["값1", "값2", "값3"]
# 쓰기/입력
with open("파일명", "wb") as f:
pickle.dump(data, f)
# 읽기/로드
with open("파일명", "rb") as f:
data = pickle.load(f) # 한줄씩 읽어온다.
npy 파일이란,
numpy 배열을 저장하는 파일
import numpy as np
data = np.arrange(100)
# 쓰기
np.save("test.npy", data) # numpy.array 저장
# 읽기
np_array = np.load("test.npy")
mat 파일이란,
h5py 패키지를 활용하여 mat파일 읽기
[ HDF5의 특징 ]
HDF5에서 중요한 개념은 그룹(Group), 데이터셋(Dataset), 속성(attribute)이다.
그룹=디렉토리, 데이터셋=파일로 이해하면 쉽다. 속성은 일종의 메타데이터로 그룹이나 데이터셋을 부연 설명하는 것을 의미한다.
HDF5는 Hierarchical Data Format이며 self-describing이 되는 고성능 데이터포맷 또는 DB 정도로 이해할 수 있다. 운영체계와 무관하게 사용할 수 있으며, 대용량 데이터를 빠르게 읽고 쓸 수 있다.
import h5py
f = f5py.File("resnet.mat", "r")
f.keys()
jbl 파일이란,
jbl 파일을 로드 할 때는 joblib 라이브러리 사용
import joblib
result = joblib.load("offline.jbl")
Diffusion 실행을 위한 Requirements
SciPy Sparse Matrix(희소행렬)이란,
1과 0으로 구성된 행렬이 존재한다고 가정할 때, 값이 대부분 0일때 희소핼렬이라고 부름 (Sparse matrix), 반대로 대부분 1일 때 밀집행렬 (Dense matrix)라고 부름
어느 한쪽이 아주 많을 때 적은 쪽의 인덱스만 별도로 저장하면 메모리 공간을 효율 적으로 사용할 수 있음. 이때 사용되는 Scipy의 sparse 패키지
import numpy as np
from scipy import sparse
# 희소행렬을 생성
arr = np.eye(3)
sparse_matrix = sparse.csr_matrix(arr)
print("{}".format(sparse_matrix))
Faiss Library
Github링크
facebookresearch/faiss
A library for efficient similarity search and clustering of dense vectors. - facebookresearch/faiss
github.com
# Diffusion에서 유사도 검색에 사용되는 라이브러리 : faiss
> faiss 라이브러리, 효율적인 유사 검색과 밀집 벡터의 클러스터링을 위한 라이브러리이다.
> RAM에 맞지 않는 크기의 벡터 집합 또한 검색할 수 있는 알고리즘이다.
# Similarity 검색이란,
> dimension이 d인 벡터 x_i의 셋이 주어졌을 때, Faiss는 벡터로 부터 램 안쪽에 데이터 구조를 구축한다.
> 그 구조가 구축 된 이후, dimension이 d인 새로운 벡터 x가 주어졌을 때 효율적으로 아래의 작동을 수행한다
> i = argmin_i ||x - x_i|| (여기서 ||.||는 Euclidean distance를 의미함)
> 여기서 argmin_i 는 ||x - x_i|| 를 최솟값으로 만들기 위한 i를 구한다는 의미
> Faiss 라이브러리 용어에서는, 데이터 구조를 index라고 표현. index는 x_i 벡터를 추가하기 위한 add method를 가진다.
실행코드
# Getting some data
# Getting some data
import numpy as np
d = 64 # dimension
nb = 100000 # database size
nq = 10000 # nb of queries
np.random.seed(1234) # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.
- Faiss는 고정 된 dimension d의 벡터의 colletions을 전형적으로 10s - 100s 사용하여 다룬다. 이러한 collections은 matrices안에 우선 저장이 되어야한다.
- 여기서 사용되는 매트릭스는 row-magor storage이다. 즉 벡터 번호 i의 j 번째 성분은 행렬의 행 i, 열 j에 저장되는 매트릭스
- Faiss는 dhwlr 32-bit floating point 매트릭스만 사용한다.
- 우리는 2개의 매트릭스를 필요로 함 xb : 데이터베이스 벡터. 인덱스가 되어야하는 모든 벡터를 포함한다. xq : 쿼리 벡터. 가장 근첩한 이웃벡터를 찾아야 하는 값들. 싱글 쿼리일 경우 np =1
# Building an index and adding the vectors to it
# Building an index and adding the vectors to it
import faiss # make faiss available
index = faiss.IndexFlatL2(d) # build the index
print(index.is_trained)
index.add(xb) # add vectors to the index
print(index.ntotal)
- 위 코드의 실행 결과는 true와 100000(인덱스에 저장된 벡터)를 나타낸다.
# Searching
# Searching
k = 4 # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check / 온정성 검사
print(I)
print(D)
D, I = index.search(xq, k) # actual search
print(I[:5]) # neighbors of the 5 first queries
print(I[-5:]) # neighbors of the 5 last queries
- 인덱스에서 수행할 수 있는 기본 검색 작동은 k-nearest-neighbor 검색이다. 각각의 쿼리 벡터에 대해, 데이터 베이스에서 k개의 최근접 이웃을 검색한다.
- 이 작동의 결과는 편리하게 integer 매트리스로 저장된다. 그 매트리스의 size는 nq-by-k(nq : 쿼리의 수, k는 근접이웃)이며, row i 는 distance결과의 오름차순으로 sorted 되고, 쿼리 벡터인 i의 근접 이웃의 ID값을 포함한다.
- 게다가 이 매트리스에서 search 작동은 nq-by-k의 "corresponding squared idstances"와 부동 소수점 매트릭스를 포함한다.
# Result
각각 쿼리의 최근접 이웃은 실제로 벡터의 인덱스. 그리고 distance에 따른 결과.
하나의 row안에서, distance는 증가한다.
Diffusion github 코드 실행
fyang93/diffusion
Efficient Diffusion for Image Retrieval. Contribute to fyang93/diffusion development by creating an account on GitHub.
github.com
# gpu버전 필요 라이브러리
$ conda install faiss-gpu cudatoolkit=10.0 -c pytorch
$ conda install joblib
$ conda install tqdm
# git clone
$ git clone https://github.com/fyang93/diffusion.git
# diffusion 폴더 접근 후
$ make download # 테스트에 필요한 파일 다운로드
$ make mat2npy # .mat파일을 .npy로 변환
$ CUDA_VISIBLE_DEVICES=0 make rank # 테스트 진행
NOTE : faiss-gpu 버전 사용 시 truncation_size 파라미터의 값은 1024를 넘으면 안된다. 이 제한을 넘겨야 한다면 cpu버전을 사용해야함
Diffusion 코드 분석
MAKEFILE : make rank
############### MAKEFILE ##################
# directory to data
DATA_DIR=./data
# directory to cache files
TMP_DIR=./tmp
# oxford5k, oxford105k, paris6k, paris106k
DATASET=oxford5k
# resnet or siamac
FEATURE_TYPE=resnet
python rank.py \
--cache_dir $(TMP_DIR)/$(DATASET)_$(FEATURE_TYPE) \
--query_path $(DATA_DIR)/query/$(DATASET)_$(FEATURE_TYPE)_glob.npy \
--gallery_path $(DATA_DIR)/gallery/$(DATASET)_$(FEATURE_TYPE)_glob.npy \
--gnd_path $(DATA_DIR)/gnd_$(DATASET).pkl \
--dataset_name $(DATASET) \
--truncation_size 1000
############### 실제 실행파일 ##################
python rank.py \
--cache_dir ./tmp/oxford5k_resnet \
--query_path ./data/query/oxford5k_resnet_glob.npy \
--gallery_path ./data/gallery/oxford5k_resnet_glob.npy \
--gnd_path ./data/gnd_oxford5k.pkl \
--dataset_name oxford5k \
--truncation_size 1000
Python 실행 과정
아래는 실제 make rank 파일을 실행 시켰을 때, 수행 되는 작업들을 순서에 맞게 재 배열 한 과정이다.
상세하게 Diffusion 코드를 보기위해 나열함. 대략적으로 크게 5단계로 나눠져 Diffusion을 수행한다.
데이터 셋 로딩
## rank.py
if __name__ == "__main__":
args = parse_args()
# 캐시 값 저장 할 폴더 생성
if not os.path.isdir(args.cache_dir):
os.makedirs(args.cache_dir)
# 데이터 셋 로딩
dataset = Dataset(args.query_path, args.gallery_path)
queries, gallery = dataset.queries, dataset.gallery
print("query..", queries.shape)
print("gallery..", gallery.shape)
print("np.vstack..", np.vstack([queries, gallery]).shape)
search()
- 쿼리는 벡터 길이가 2048인 데이터 55개가 존재
- 갤러리는 벡터 길이가 2048인 데이터가 5063개가 존재
- np.vstack을 사용하여 쿼리와 갤러리를 위아래로 합친다. 결국 벡터길이가 2048인 데이터가 총 5118개가 존재 함
## dataset.py
# dataset.py
class Dataset(object):
"""Dataset class
"""
def __init__(self, query_path, gallery_path):
self.query_path = query_path
self.gallery_path = gallery_path
self._queries = None
self._gallery = None
@property
def queries(self):
if self._queries is None:
self._queries = load(self.query_path)
return self._queries
@property
def gallery(self):
if self._gallery is None:
self._gallery = load(self.gallery_path)
return self._gallery
- @property 데코레이터를 이용하여 Get, Set 매소드를 표현 할 수있다.
> get method = @property
> set method = @method_name.setter
Searh함수 실행 : Diffusion
## rank.py
def search():
# 쿼리 수 파악 : 55개
n_query = len(queries)
# shape 구조 : (데이터 수, 벡터 길이)
# query shape : (55, 2048)
# gallery shape : (5063, 2048)
# np.vstack([queries, gallery]).shape : (5118, 2048) >> vstack 배열을 위에서 아래로 붙이기
diffusion = Diffusion(np.vstack([queries, gallery]), args.cache_dir)
## diffusion.py
# diffusion 함수 init
class Diffusion(object):
"""Diffusion class
"""
def __init__(self, features, cache_dir):
# features : query와 gallery feature vector를 위 아래로 합침
# features.shape : (5118,2048)
self.features = features
# 총 데이터 개수 확인
# self.N = 5118
self.N = len(self.features)
self.cache_dir = cache_dir
# 10만개 이상의 데이터에 대해서는 ann 수행
# use ANN for large datasets
self.use_ann = self.N >= 100000
if self.use_ann:
self.ann = ANN(self.features, method='cosine')
# 10만개 이하의 데이터에 대해서는 knn 수행
self.knn = KNN(self.features, method='cosine')
- 총 데이터 개수는 diffusion.N = 5118
- 데이터의 수의 10만개 이상을 경우 ANN이 수행되고, 10만개 이하의 경우는 KNN이 수행된다.
## knn.py
# 기본이 되는 Base
class BaseKNN(object):
"""KNN base class"""
def __init__(self, database, method):
if database.dtype != np.float32:
database = database.astype(np.float32)
# Feature의 수 : 데이터 셋의 수
self.N = len(database)
# Feature의 dimension : 벡터 길이 (2048)
self.D = database[0].shape[-1]
print("Dimension", self.D)
self.database = database
def add(self, batch_size=10000):
"""Add data into index"""
if self.N <= batch_size:
self.index.add(self.database)
else:
[self.index.add(self.database[i:i+batch_size])
for i in tqdm(range(0, len(self.database), batch_size),
desc='[index] add')]
def search(self, queries, k):
"""Search
Args:
queries: query vectors
k: get top-k results
Returns:
sims: similarities of k-NN
ids: indexes of k-NN
"""
if not queries.flags['C_CONTIGUOUS']:
queries = np.ascontiguousarray(queries)
if queries.dtype != np.float32:
queries = queries.astype(np.float32)
sims, ids = self.index.search(queries, k)
return sims, ids
# ann.py (10만개 이상의 데이터 셋)
class ANN(BaseKNN):
"""Approximate nearest neighbor search class
Args:
database: feature vectors in database
method: distance metric
"""
def __init__(self, database, method, M=128, nbits=8, nlist=316, nprobe=64):
super().__init__(database, method)
self.quantizer = {'cosine': faiss.IndexFlatIP,
'euclidean': faiss.IndexFlatL2}[method](self.D)
self.index = faiss.IndexIVFPQ(self.quantizer, self.D, nlist, M, nbits)
samples = database[np.random.permutation(np.arange(self.N))[:self.N // 5]]
print("[ANN] train")
self.index.train(samples)
self.add()
self.index.nprobe = nprobe
# knn.py (10만개 이하의 데이터 셋)
class KNN(BaseKNN):
"""KNN class
Args:
database: feature vectors in database
method: distance metric
"""
def __init__(self, database, method):
super().__init__(database, method)
self.index = {'cosine': faiss.IndexFlatIP,
'euclidean': faiss.IndexFlatL2}[method](self.D)
if os.environ.get('CUDA_VISIBLE_DEVICES'):
self.index = faiss.index_cpu_to_all_gpus(self.index)
self.add()
Searh함수 실행 : diffusion.get_offline_results
## rank.py
def search():
# 쿼리 수 파악
# n_query = len(queries)
# shape 구조 : (데이터 수, 벡터 길이)
# query shape : (55, 2048)
# gallery shape : (5063, 2048)
# np.vstack([queries, gallery]).shape : (5118, 5063)
# >> vstack 배열을 위에서 아래로 붙이기
# diffusion = Diffusion(np.vstack([queries, gallery]), args.cache_dir)
offline = diffusion.get_offline_results(args.truncation_size, args.kd)
print("offline..", len(offline.data))
# offline type : scipy.sparse.csr.csr_matrix (희소행렬)
# offline shape : (5118 ,5118) >> query와 gallery의 합
## diffusion.py > get_laplacian
# get_offline_results 에서 사용하는 function
def get_laplacian(self, sims, ids, alpha=0.99):
"""Get Laplacian_alpha matrix
"""
# get_laplacian 아래 함수 참고
affinity = self.get_affinity(sims, ids)
num = affinity.shape[0]
degrees = affinity @ np.ones(num) + 1e-12
# mat: degree matrix ^ (-1/2)
mat = sparse.dia_matrix(
(degrees ** (-0.5), [0]), shape=(num, num), dtype=np.float32)
stochastic = mat @ affinity @ mat
sparse_eye = sparse.dia_matrix(
(np.ones(num), [0]), shape=(num, num), dtype=np.float32)
lap_alpha = sparse_eye - alpha * stochastic
return lap_alpha
# get_laplacian 에서 사용하는 function
def get_affinity(self, sims, ids, gamma=3):
"""Create affinity matrix for the mutual kNN graph of the whole dataset
Args:
sims: similarities of kNN
ids: indexes of kNN
Returns:
affinity: affinity matrix
"""
num = sims.shape[0]
sims[sims < 0] = 0 # similarity should be non-negative
sims = sims ** gamma
# vec_ids: feature vectors' ids
# mut_ids: mutual (reciprocal) nearest neighbors' ids
# mut_sims: similarites between feature vectors and their mutual nearest neighbors
vec_ids, mut_ids, mut_sims = [], [], []
for i in range(num):
# check reciprocity: i is in j's kNN and j is in i's kNN when i != j
ismutual = np.isin(ids[ids[i]], i).any(axis=1)
ismutual[0] = False
if ismutual.any():
vec_ids.append(i * np.ones(ismutual.sum(), dtype=int))
mut_ids.append(ids[i, ismutual])
mut_sims.append(sims[i, ismutual])
vec_ids, mut_ids, mut_sims = map(np.concatenate, [vec_ids, mut_ids, mut_sims])
affinity = sparse.csc_matrix((mut_sims, (vec_ids, mut_ids)),
shape=(num, num), dtype=np.float32)
return affinity
Searh함수 실행 : preprocessing.normalize
## rank.py
def search():
# 쿼리 수 파악
# n_query = len(queries)
# shape 구조 : (데이터 수, 벡터 길이)
# query shape : (55, 2048)
# gallery shape : (5063, 2048)
# np.vstack([queries, gallery]).shape : (5118, 5063) >> vstack 배열을 위에서 아래로 붙이기
# diffusion = Diffusion(np.vstack([queries, gallery]), args.cache_dir)
# offline type : scipy.sparse.csr.csr_matrix (희소행렬)
# offline shape : (5118 ,5118) >> query와 gallery의 합
# offline = diffusion.get_offline_results(args.truncation_size, args.kd)
# print("offline..", len(offline.data))
features = preprocessing.normalize(offline, norm="l2", axis=1)
# features.shape : (5118, 5118)
- offline.shape : (5118, 5118)
- 현재 offline의 shape 은 쿼리와 갤러리의 수의 합인 5118개의 행과 열로 구성된 matrix
## data.py
def normalize(X, norm='l2', axis=1, copy=True, return_norm=False):
"""Scale input vectors individually to unit norm (vector length).
Returns
X : {array-like, sparse matrix}, shape [n_samples, n_features]
Normalized input X.
"""
if norm not in ('l1', 'l2', 'max'):
raise ValueError("'%s' is not a supported norm" % norm)
if axis == 0:
sparse_format = 'csc'
elif axis == 1:
sparse_format = 'csr'
else:
raise ValueError("'%d' is not a supported axis" % axis)
X = check_array(X, sparse_format, copy=copy,
estimator='the normalize function', dtype=FLOAT_DTYPES)
if axis == 0:
X = X.T
if sparse.issparse(X):
if return_norm and norm in ('l1', 'l2'):
raise NotImplementedError("return_norm=True is not implemented "
"for sparse matrices with norm 'l1' "
"or norm 'l2'")
if norm == 'l1':
inplace_csr_row_normalize_l1(X)
elif norm == 'l2':
inplace_csr_row_normalize_l2(X)
elif norm == 'max':
_, norms = min_max_axis(X, 1)
norms_elementwise = norms.repeat(np.diff(X.indptr))
mask = norms_elementwise != 0
X.data[mask] /= norms_elementwise[mask]
else:
if norm == 'l1':
norms = np.abs(X).sum(axis=1)
elif norm == 'l2':
norms = row_norms(X)
elif norm == 'max':
norms = np.max(X, axis=1)
norms = _handle_zeros_in_scale(norms, copy=False)
X /= norms[:, np.newaxis]
if axis == 0:
X = X.T
if return_norm:
return X, norms
else:
return X
Searh함수 실행 : scores
## rank.py
def search():
# 쿼리 수 파악
# n_query = len(queries)
# shape 구조 : (데이터 수, 벡터 길이)
# query shape : (55, 2048)
# gallery shape : (5063, 2048)
# np.vstack([queries, gallery]).shape : (5118, 5063) >> vstack 배열을 위에서 아래로 붙이기
# diffusion = Diffusion(np.vstack([queries, gallery]), args.cache_dir)
# offline type : scipy.sparse.csr.csr_matrix (희소행렬)
# offline shape : (5118 ,5118) >> query와 gallery의 합
# offline = diffusion.get_offline_results(args.truncation_size, args.kd)
# print("offline..", len(offline.data))
# features = preprocessing.normalize(offline, norm="l2", axis=1)
# print("features..",features.shape)
scores = features[:n_query] @ features[n_query:].T
print("1", features[:n_query].shape)
print("2", features[n_query:].shape)
print("3", (features[n_query:].T).shape)
print("4", scores.shape)
- 위에서 출력 된 features.shape : (5118, 5118)
- score는 쿼리 수(n_query = 55) 만큼의 features만 사용
- 최종 score의 shape : (55, 5063)
Searh함수 실행 : np.argsort
## rank.py
def search():
# 쿼리 수 파악
# n_query = len(queries)
# shape 구조 : (데이터 수, 벡터 길이)
# query shape : (55, 2048)
# gallery shape : (5063, 2048)
# np.vstack([queries, gallery]).shape : (5118, 5063) >> vstack 배열을 위에서 아래로 붙이기
diffusion = Diffusion(np.vstack([queries, gallery]), args.cache_dir)
# offline type : scipy.sparse.csr.csr_matrix (희소행렬)
# offline shape : (5118 ,5118) >> query와 gallery의 합
# offline = diffusion.get_offline_results(args.truncation_size, args.kd)
# print("offline..", len(offline.data))
# features = preprocessing.normalize(offline, norm="l2", axis=1)
# print("features..",features.shape)
# scores = features[:n_query] @ features[n_query:].T
# scores.shape : (55, 5063) = (쿼리, 갤러리)
ranks = np.argsort(-scores.todense())
print(ranks.shape)
# np.argsort : 행렬 안에서 값이 작은 값부터 순서대로 데이터의 INDEX 반환
- 마이너스를 붙이면 안에 값에 모두 -가 붙는다.
- 기존 scores의 타입이 <class 'scipy.sparse.csr.csr_matrix'>, todense()를 사용하여 <class 'numpy.matrix'>로 변환작업
- 그 후에 사용되는 np.argsort() : 행렬의 각 로우에서 작은 값부터 순서대로 데이터의 index를 반환함. np.argsort()에 넣을 데이터에 -를 붙였기 때문에 큰 값부터 데이터의 index를 반환 함
- 실제 ranks 결과에서 첫번째 쿼리의 결과를 살펴보면 아래와 같이 인덱스가 출력 되는 것을 확인 할 수 있다 (큰 값 순서대로)
