From da373475ed24169ee0578f6d79978e7f07348164 Mon Sep 17 00:00:00 2001 From: Angie Chiang Date: Tue, 16 Apr 2019 11:31:44 -0700 Subject: [PATCH] Refine vp9_kmeans() Reduce the number of group_idx initialization. Initialize the center to the median of the data group. Change-Id: Ie16150610480bf54a6b5e2bc048ba1e940bef10f --- vp9/encoder/vp9_encodeframe.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/vp9/encoder/vp9_encodeframe.c b/vp9/encoder/vp9_encodeframe.c index 084552e..a0a978b 100644 --- a/vp9/encoder/vp9_encodeframe.c +++ b/vp9/encoder/vp9_encodeframe.c @@ -5841,7 +5841,7 @@ void vp9_kmeans(double *ctr_ls, double *boundary_ls, int *count_ls, int k, // initialize the center points for (j = 0; j < k; ++j) { - ctr_ls[j] = arr[(size * j) / k].value; + ctr_ls[j] = arr[(size * (2 * j + 1)) / (2 * k)].value; } for (itr = 0; itr < 10; ++itr) { @@ -5851,10 +5851,13 @@ void vp9_kmeans(double *ctr_ls, double *boundary_ls, int *count_ls, int k, count[i] = 0; } + // Both the data and centers are sorted in ascending order. + // As each data point is processed in order, its corresponding group index + // can only increase. So we only need to reset the group index to zero here. + group_idx = 0; for (i = 0; i < size; ++i) { - // place samples into clusters - group_idx = 0; while (arr[i].value >= boundary_ls[group_idx]) { + // place samples into clusters ++group_idx; if (group_idx == k - 1) { break; -- 2.7.4