[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

실제 SOTA 캡쳐 화면

 

가장 상위에 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

facebookresearch/faiss

# 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

fyang93/diffusion

# 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 결과에서 첫번째 쿼리의 결과를 살펴보면 아래와 같이 인덱스가 출력 되는 것을 확인 할 수 있다 (큰 값 순서대로)