# SDC与ADC

###### tags: `Product Quantizer`

[ToC]
## SDC(Symmetric distance computation)
对称的距离计算，对query和gallery都进行PQ量化，然后计算量化后code的距离。我们以一个sub quantizer的距离计算为例，说明其做法。

### Step 1: 获取量化中心-量化中心距离表

每一个sub quantizer会有k个聚类中心，计算出两两之间的距离，可以得到一个k*k对称的距离矩阵

| |cent 1|cent 2|cent 3|...|cent k|
|------|------|------|------|---|------|
|cent 1|d(1,1)|d(1,2)|d(1,3)|d(1,...)|d(1,k)|
|cent 2|d(2,1)|d(2,2)|d(2,3)|d(2,...)|d(2,k)|
|cent 3|d(3,1)|<font color="red">d(3,2)</font>| d(3,3)|d(3,...)|d(3,k)|
| ...|d(...,1)|d(...,2)|d(...,3)|d(...,...)|d(...,k)|
|cent k|d(k,1)|d(k,2)|d(k,3)|d(k,...)|d(k,k)|

### Step 2: 计算query量化值

来了一个query，计算出它在该sub quantizer所有聚类中心的距离，并找出最小的作为他的量化编码，比如3

### Step 3: 查找表计算SDC
比如gallery在改sub quantizer上的量化值（也就是最近的聚类中心的index）为2，那么query与该gallery在此subquantizer上的距离可以通过查找step 1中的表d(3,2)来获取

## ADC(Asymmetric distance computation)
非对称的距离计算，仅仅对gallery进行量化，对query不需要量化，具体流程为
### Step 1: 计算query-量化中心距离表
来了一个query，计算出它在该sub quantizer所有聚类中心的距离，可以得到一个1*k 的距离向量
| |cent 1|cent 2|cent 3|...|cent k|
|------|------|------|------|---|------|
|query|d(1)|d(2)|d(3)|d(...)|d(k)|
### Step 2: 查找表计算ADC
比如gallery在改sub quantizer上的量化值（也就是最近的聚类中心的index）为2，那么query与该gallery在此subquantizer上的距离可以通过查找step 1中的表d(2)来获取
## SDC与ADC的区别
### 含义
图中每个细胞块儿是一个量化范围，中心的小蓝点是量化中心，SDC是计算的两个胞体中心的距离，ADC计算的是原始特征和一个胞体的距离
### 计算复杂度
引用原文的一段话

One can seethat SDC and ADC have the same query preparation cost.
The only advantage of SDC over ADC is to limit the memory usage 
associated with the queries, as thequery vector is defined by a 
code. This is most cases not relevant and one should then use the
asymmetric version, which obtains a lower distance distortion for 
a similar complexity. We will focus on ADC in the rest of this section.

二者的计算复杂度一致，都是要计算每个query和所有聚类中心的距离。SDC相对于ADC唯一的好处是
当query size很大的时候，SDC可以省一些内存，因为所有query都被量化编码了，但是这在实际中
并不是什么问题。但是ADC相对于SDC有更精确的距离计算，因此实际用的基本都是ADC

<!-- - Auto-generated Table of Content -->