Quick-Finding of the Nearest Center
Quick-Finding of the Nearest Center is used for
- Fast k-means
- Fast VQ (accelerating the compression speed of VQ)
- Fast classification
Given $k$ centers (codewords) {$\overrightarrow{y_1}, …\overrightarrow{y_k}$}, e.g., $k=128$, and a new point $\overrightarrow{x}=(x_1,x_2, …, x_{d})$, e.g., $d$ = 16, we want to find a center $\overrightarrow{y_{min}}$ such that
\[\|\overrightarrow{y_{min}}-\overrightarrow{x}\| = \min_{1\leq i \leq 128} \|\overrightarrow{y_i}-\overrightarrow{x}\| = \min_{1\leq i \leq 128} \|\sum_{j=1}^{16}(y_{ij}-x_j)^2\|\]Assume some centers (e.g., $\overrightarrow{y_1}, \overrightarrow{y_2}, …$) have been examined so far and the smallest minimum squared error is
\[d_{min}^2=d^2(\overrightarrow{x}, \overrightarrow{y_{min}^{SF}}) = \min_l \|\overrightarrow{x} - \overrightarrow{y_l}\|^2 \\ \forall \overrightarrow{y_l} \in \{ \text{already checked} \} \\ \overrightarrow{y_{min}^{SF}} \text{is the nearest center so far}\]Here we will introduce 5 methods for finding the nearest center:
- Partial Distance Elimination (PDE, 1965)
- Triangle Inequality Elimination (TIE)
- IEEE-T-Communication (1994)
- Optical Engineering: Integral Projection Method (1995)
- Fast VQ encoding by an efficient kick-out condition (2000)
Partial Distance Elimination (PDE, 1965)
When we examine the next $y_i$, if we find
\[(x_1-y_{i1})^2+(x_2-y_{i2})^2+(x_3-y_{i3})^2 > d_{min}^2\]Then we can kick out $y_i$ immediately without computing all $d$ dimensions.
Triangle Inequality Elimination (TIE)
In pre-processing, we record the distance between every pair of centers ($C^k_2$ combinations).
So that in the main program, when we examine the next $y_i$ and see
\[\|\overrightarrow{y_i} -\overrightarrow{y_{min}^{SF}}\| \geq 2 d_{min}^{SF}\]then $y_i$ is impossible to be the nearest center to $\overrightarrow{x}$.
This is because if $|\overrightarrow{y_i} -\overrightarrow{y_{min}^{SF}}| \geq 2 d_{min}^{SF}$ then
\[\begin{equation} \begin{split} \|\overrightarrow{y_i}-\overrightarrow{x}\| & \geq \|\overrightarrow{y_i}-\overrightarrow{y_{min}^{SF}}\| - \|\overrightarrow{y_{min}^{SF}} - \overrightarrow{x}\| \\ & = (\geq 2 d_{min}^{SF}) - d_{min}^{SF} \\ & \geq d_{min}^{SF} \end{split} \end{equation}\]IEEE-T-Communication (1994)
The prerequisitets of this method is that values in all dimensions are non-negative.
$\overrightarrow{y_i}$ will not be better than $\overrightarrow{y_i}^{SF}$
\[\|\overrightarrow{y_i}-\overrightarrow{x}\| \geq \|\overrightarrow{y_i}^{SF}-\overrightarrow{x}\|\]if either of the followings exist
\[\|\overrightarrow{x}\|^2+\|\overrightarrow{y_i}\|^2 - 2\Big(\|\overrightarrow{x}\|_{\infty}\Big)\Big(\sum_{j=1}^{16}y_{ij}\Big) \geq d_{min}^2 \\ \text{or} \\ \|\overrightarrow{x}\|^2+\|\overrightarrow{y_i}\|^2 - 2\Big(\|\overrightarrow{y_{i}}\|_{\infty}\Big)\Big(\sum_{j=1}^{16}x_{j}\Big) \geq d_{min}^2\]This is because
\[\begin{equation} \begin{split} \|\overrightarrow{x}-\overrightarrow{y_i}\|^2 &= (\overrightarrow{x}-\overrightarrow{y_i})(\overrightarrow{x}-\overrightarrow{y_i}) \\ &= \overrightarrow{x} \overrightarrow{x} - 2 \overrightarrow{x}\overrightarrow{y_i} + \overrightarrow{y_i} \overrightarrow{y_i} \\ &=\|\overrightarrow{x}\|^2 + \|\overrightarrow{y_i}\|^2 -2 \Big(\sum_{j = 1}^{16} x_j y_{ij}\Big) \\ &\geq \|\overrightarrow{x}\|^2 + \|\overrightarrow{y_i}\|^2 - 2 \Big(\|\overrightarrow{x}\|_{\infty}\Big) \Big(\sum_{j=1}^{16}y_{ij}\Big) \\ &\geq d_{min}^2 \end{split} \end{equation}\]Optical Engineering: Integral Projection Method (1995)
Assume we can project each 16-dim vector to a 4-by-4 block (any decomposition is okay, e.g., can be 8-by-2 as well) such that
\[H_1(\overrightarrow{x}) = x_1 + x_2 + x_3 + x_4 \\ H_2(\overrightarrow{x}) = x_5 + x_6 + x_7 + x_8 \\ ... \\ ~ \\ V_1(\overrightarrow{x}) = x_1 + x_5 + x_9 + x_{13} \\ V_2(\overrightarrow{x}) = x_2 + x_6 + x_{10} + x_{14} \\ ...\]and
\[S(\overrightarrow{x}) = Sum(\overrightarrow{x}) = x_1 + x_2 + x_3 + ... + x_{16}\]Use $Sum(\overrightarrow{x})$ & $Sum(\overrightarrow{y})$
$\overrightarrow{y_i}$ will not be better than $\overrightarrow{y_i}^{SF}$
\[\|\overrightarrow{y_i}-\overrightarrow{x}\| \geq \|\overrightarrow{y_i}^{SF}-\overrightarrow{x}\|\]if the following exists
\[\big(Sum(\overrightarrow{x}) - Sum(\overrightarrow{y_i})\big)^2 \geq 16 \cdot {d_{min}^2}^{SF}\]This is beacuse
\[\text{Let}~\overrightarrow{\delta} = \overrightarrow{x}- \overrightarrow{y_i} \\ (Sum(\overrightarrow{x})-Sum(\overrightarrow{y_i}))^2 = (Sum(\overrightarrow{\delta}))^2 \\ = (\delta_1+\delta_2+\delta_3+...+\delta_{16})^2 \\ \leq 16(\delta_1^2+\delta_2^2+\delta_3^2+...+\delta_{16}^2) ~(\because \text{Theorem 1.}) \\ = 16\|\overrightarrow{\delta}\|^2 = 16 \|\overrightarrow{x}-\overrightarrow{y_i}\|^2\]so that
\[16 \|\overrightarrow{x}-\overrightarrow{y_i}\|^2 \geq Sum(\overrightarrow{x})-Sum(\overrightarrow{y_i}))^2\]Theorem 1.
\[(a_1+a_2+...+a_m)^2 \leq m(a_1^2+a_2^2+a_3^2+...+a_m^2)~~,\forall m\]Proof
\[(a_1+a_2+...+a_m)^2 = (a_1^2+a_2^2+a_3^2+...+a_m^2) + \sum_{i\neq j}a_ia_j \\ = (a_1^2+a_2^2+a_3^2+...+a_m^2) + \sum_{i < j} (2a_ia_j) \\ \leq (a_1^2+a_2^2+a_3^2+...+a_m^2) + \sum_{i < j}(a_i^2 + a_j^2) \\ \bigg(\because a_i^2+a_j^2-2a_ia_j = (a_i-a_j)^2 \geq 0~~\therefore a_i^2 + a_j^2 \geq 2a_ia_j\bigg) \\ = m(a_1^2+a_2^2+a_3^2+...+a_m^2)\]
Use Horizontal Sum $H(\overrightarrow{x})$ & $H(\overrightarrow{y})$
$\overrightarrow{y_i}$ will not be better than $\overrightarrow{y_i}^{SF}$
\[\|\overrightarrow{y_i}-\overrightarrow{x}\| \geq \|\overrightarrow{y_i}^{SF}-\overrightarrow{x}\|\]if the following exists
\[\sum_{l=1}^4\big(H_l(\overrightarrow{x}) - H_l(\overrightarrow{y_i})\big)^2 \geq 4 \cdot {d_{min}^2}^{SF}\]This is because
\[Let~\overrightarrow{\delta} = \overrightarrow{x} - \overrightarrow{y_i} \\ 4\|\overrightarrow{x}-\overrightarrow{y_i}\| = 4\|\overrightarrow{\delta}\|^2 = 4(\delta_1^2+\delta_2^2+\delta_3^2+...+\delta_{16}^2) \\ = 4 \big[ (\delta_1^2+\delta_2^2+\delta_3^2+\delta_4^2) +(\delta_5^2+\delta_6^2+\delta_7^2+\delta_8^2) +(...)+(...) \big] \\ \geq (\delta_1+\delta_2+\delta_3+\delta_4)^2+(\delta_5+\delta_6+\delta_7+\delta_8)^2 + (...)^2+(...)^2 \\ = \big(H_1(\overrightarrow{x})-H_1(\overrightarrow{y_i})\big)^2 + \big(H_2(\overrightarrow{x})-H_2(\overrightarrow{y_i})\big)^2 + \big(...\big)^2 + \big(...\big)^2\]so that
\[4\|\overrightarrow{x}-\overrightarrow{y_i}\| \geq \sum_{l=1}^4\big(H_l(\overrightarrow{x}) - H_l(\overrightarrow{y_i})\big)^2\]Use Vertical Sum $V(\overrightarrow{x})$ & $V(\overrightarrow{y})$
$\overrightarrow{y_i}$ will not be better than $\overrightarrow{y_i}^{SF}$
\[\|\overrightarrow{y_i}-\overrightarrow{x}\| \geq \|\overrightarrow{y_i}^{SF}-\overrightarrow{x}\|\]if the follwowing exists
\[\sum_{l=1}^4\big(V_l(\overrightarrow{x}) - V_l(\overrightarrow{y_i})\big)^2 \geq 4 \cdot {d_{min}^2}^{SF}\]Which can be proved similarly as the proof in the previous section (Horizontal Sum).
Fast VQ encoding by an efficient kick-out condition (2000)
$\overrightarrow{y_i}$ will not be better than $\overrightarrow{y_i}^{SF}$
\[\|\overrightarrow{y_i}-\overrightarrow{x}\| \geq \|\overrightarrow{y_i}^{SF}-\overrightarrow{x}\|\]if the following exists.
\[\|\overrightarrow{y_i}\|(\|\overrightarrow{y_i}\| - 2\|\overrightarrow{x}\|)>(d_{min}^{SF})^2\]To give the proof, let $\tilde{d}^2(\overrightarrow{x}, \overrightarrow{y_i}) = |\overrightarrow{x} - \overrightarrow{y_i}|^2 - |\overrightarrow{x}|^2$, and the nearest neighbor $\overrightarrow{y_i}$ who minimizes $|\overrightarrow{x} - \overrightarrow{y_i}|$ will also minimizes $\tilde{d}^2(\overrightarrow{x}, \overrightarrow{y_i})$, we know that
\[\tilde{d}^2(\overrightarrow{x}, \overrightarrow{y_i}) = \|\overrightarrow{x} - \overrightarrow{y_i}\|^2 - \|\overrightarrow{x}\|^2 \\ =(\overrightarrow{x}-\overrightarrow{y_i}) \cdot (\overrightarrow{x}-\overrightarrow{y_i}) - \overrightarrow{x} \cdot \overrightarrow{x} = \|\overrightarrow{y_i}\|^2 - 2\overrightarrow{x} \cdot \overrightarrow{y_i} \\ \geq \|\overrightarrow{y_i}\|^2 - 2\|\overrightarrow{x} \|\|\overrightarrow{y_i}\| = \|\overrightarrow{y_i}\|(\|\overrightarrow{y_i}\| - 2\|\overrightarrow{x}\|)\]So we can infer that
\[\|\overrightarrow{y_i}\|(\|\overrightarrow{y_i}\| - 2\|\overrightarrow{x}\|)>(d_{min}^{SF})^2 \rightarrow \tilde{d}^2(\overrightarrow{x}, \overrightarrow{y_i}) > (d_{min}^{SF})^2\]and at the same time,
\[\tilde{d}^2(\overrightarrow{x}, \overrightarrow{y_i}) > (d_{min}^{SF})^2 \rightarrow \|\overrightarrow{y_i}-\overrightarrow{x}\| \geq \|\overrightarrow{y_i}^{SF}-\overrightarrow{x}\|\]The algorithm of VQ using this efficient kick-out condition can be decomposed into 5 steps:
Step 0. Sort {$\overrightarrow{y_1}, …, \overrightarrow{y_{128}}$}
Assume {$\overrightarrow{y_1}, …, \overrightarrow{y_{128}}$} is sorted by their absolute value $|y_i|$ in ascending order and compute $2|\overrightarrow{x}|$.
From the set {$\overrightarrow{y_1}, …, \overrightarrow{y_{128}}$} choose a $\overrightarrow{y_{initial}}$ such that $|\overrightarrow{y_{initial}}| \simeq |\overrightarrow{x}|$ and let
- $(\tilde{d}{min}^{SF})^2$ $=$ $\tilde{d}^2(x, y{initial})$
- $R=$ {$\overrightarrow{y_1}, …, \overrightarrow{y_{128}}$} $\setminus$ {$\overrightarrow{y_{initial}}$}.
Step 1. Choose $\overrightarrow{y_i}$ from $R$.
Step 2. Delete centroids according to kick-out conditions.
Let
\[f(\|\overrightarrow{y_i}\|) = \|y_i\|(\|y_i\|-2\|x\|)\]and if the following statement exist
\[f(\|\overrightarrow{y_i}\|) \geq (\tilde{d}_{min}^{SF})^2\]then
- in the case $|\overrightarrow{y_i}| \geq |\overrightarrow{x}|$, delete $\overrightarrow{y_i}$ and {$\overrightarrow{y_l}$} $_{l \geq i}$ from $R$.
- in the case $|\overrightarrow{y_i}| \leq |\overrightarrow{x}|$, delete $\overrightarrow{y_i}$ and {$\overrightarrow{y_l}$} $_{l \leq i}$ from $R$.
The reason is that since $f(t) = t^2-2t|\overrightarrow{x}|$ then $f$ is a parabola with its minimum occurs at $t = |\overrightarrow{x}|$, thus
\[(\|\overrightarrow{y_l}\| - \|\overrightarrow{x}\|)(\|\overrightarrow{y_i}\| - \|\overrightarrow{x}\|) > 0 ~\text{and}~\bigg|\|\overrightarrow{y_l}\| - \|\overrightarrow{x}\|\bigg| > \bigg|\|\overrightarrow{y_i}\| - \|\overrightarrow{x}\|\bigg| \\ \rightarrow f(\|\overrightarrow{y_l}\|) > f(\|\overrightarrow{y_i}\|)\]
Step 3. Evaluate $\tilde{d}(\overrightarrow{x}, \overrightarrow{y_i})$.
Replace $\overrightarrow{y_i^{SF}}$ with $\overrightarrow{y_i}$ and update $(\tilde{d}_{min}^{SF})^2$ if
\[\tilde{d}^2(\overrightarrow{x}, \overrightarrow{y_i}) < (\tilde{d}_{min}^{SF})^2\]Step 4. Go back to Step 2. if $R$ is not empty.
Comparisons
If there are 128 centers {$\overrightarrow{y_i}$}$_{i=1}^{128}$, then for each method, the storage used is
| Triangle Inequality Elimination | IEEE-T-Communication | Integral Projection Method | efficient kick-out |
|---|---|---|---|
| \(C_2^{128} = \frac{128*127}{2}\) | \(3*128\) | \((2\sqrt{dim}+1)*128\\ = (2*\sqrt{16}+1)*128\\ = 9*128\) | \(128\) |
| $\because |\overrightarrow{y_i}-\overrightarrow{y_j}|$ | \(\because | \overrightarrow{y_i} |_{l2}, | \overrightarrow{y_i} |_{\infty}, | \overrightarrow{y_i} |_{l1}\) | $\because Sum(\overrightarrow{y_i}), H_l(\overrightarrow{y_i}), V_l(\overrightarrow{y_i})~\forall l$ | $\because |\overrightarrow{y_i}|$ |
And if we use 512x512 “Lena” to build up a codebook (with $k$ codewords) and then use this codebook to compress “Jet” by VQ, the computation time will be
| (sec.) | Full Search | Triangle Inequality Elimination | IEEE-T-Communication | Integral Projection Method | efficient kick-out |
|---|---|---|---|---|---|
| k=128 | 29.65 | 4.47 | 5.3 | 4.08 | 1.89 |
| k=256 | 72.9 | 7.99 | 14.37 | 6.44 | 4.15 |
| k=512 | 145.9 | 13.7 | 27.24 | 10.31 | 7.23 |
