XGG Blog
Locality-Constrained Linear Coding was proposed in CVPR 2010. The coding scheme utilizes the locality constraints to project each descriptor into its local-coordinate system. The author had published the Matlab code for coding descriptors, however, the code for codebook optimization is not mentioned in the same web page.
Wang, J., Yang, J., Yu, K., Lv, F., Huang, T., & Gong, Y. (2010, June). Locality-constrained linear coding for image classification. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on (pp. 3360-3367). IEEE.Brief Introduction
As can be seen in the figure above, LLC is used for image classification. LLC codes a descriptor using the its nearest neighbours, which assumes that the descriptors with small differences in the origin space should have relatively small differences in the projected space, and should have few significant values.
Codebook Optimization
As proposed in the paper, a simple way for codebook generation is to use clustering based methods, while the codebook could be optimized afterwards. The optimization problem is:
{% math-block %}
\begin{matrix}\arg\min_{\mathbf{C},\mathbf{B}}\sum_{i=1}^N{\left\|\mathbf{x}_i-\mathbf{B}\mathbf{c}_i\right\|}^2+\lambda{\left\|\mathbf{d}_i\odot\mathbf{c}_i\right\|}^2\\\begin{matrix}s.t.&\mathbf{1}^T\mathbf{c}_i=1,&\forall_i\\&{\left\|\mathbf{b}_j\right\|}^2\leq1,&\forall_j\end{matrix}
\end{matrix} {% endmath-block %}
where means the codebook should be normalized.
In the provided algorithm for solving this optimization problem, there are another two optimization problems, which are:
{% math-block %}
\begin{matrix}\arg\min_{\mathbf{c}}{\left\|\mathbf{x}_i-\mathbf{B}\mathbf{c}\right\|}^2+\lambda{\left\|\mathbf{d}^T\mathbf{c}\right\|}^2\\\begin{matrix}s.t.&\mathbf{1}^T\mathbf{c}=1\end{matrix}
\end{matrix} {% endmath-block %}
{% math-block %}
\begin{matrix}\arg\min_{\mathbf{c}’}{\left\|\mathbf{x}_i-\mathbf{B}_i\mathbf{c}’\right\|}^2\\\begin{matrix}s.t.&\mathbf{1}^T\mathbf{c}’=1\end{matrix}
\end{matrix} {% endmath-block %}
Actually, the first optimization problem is just the same as in coding step, which could be solved by:
{% math-block %} \mathbf{C}_i = (\mathbf{B}-\mathbf{1}\mathbf{x}_i^T)(\mathbf{B}-\mathbf{1}\mathbf{x}_i^T)^T \ \tilde{\mathbf{c}_i}=(\mathbf{C}_i + \lambda diag(\mathbf{d})) \backslash \mathbf{1} \ \mathbf{c}_i=\tilde{\mathbf{c}_i} / \mathbf{1}^T\tilde{\mathbf{c}_i} {% endmath-block %}
M = size(B, 1);c = zeros([1, M]);% Find k nearest neighbours.d = zeros([1, M]);for j = 1 : Md(j) = norm(x – B(j, :));end[~, index] = sort(d, ‘ascend’);index = index(1 : knn);Bi = B(index, :);% Coding.z = Bi – repmat(x, knn, 1);C = z * z’;C = (C + 1e-4 * eye(knn, knn) * trace(C)) \ ones(knn, 1);C = C / sum(C);c(index) = C;end
The second optimization problem is equal to the first one when . The optimization of the codebook is:
N = size(X, 1);% Initialize codebook.[~, B] = kmeans(X, M);for i = 1 : Nxi = X(i, :);% Solve coding optimization.[c, index] = llc_solve(xi, B, knn);ci = c(index);Bi = B(index, :);% Update basis.detBi = – 2 * ci’ * (xi – ci * Bi);mu = sqrt(1.0 / i);Bi = Bi – mu * detBi / norm(ci);B(index, 🙂 = Bi;endend即将转出来的那一面，是快乐或痛苦，是爱还是恨。
