Improved performance for Kmeans filter.

Bug: 7739334
Change-Id: I5ab1eb429d65f84449a61deca962a47f2b6dbc8b

3 files changed, 114 insertions, 34 deletions

diff --git a/jni/filters/kmeans.cc b/jni/filters/kmeans.cc
index 599657c8e..97cead7bc 100644
--- a/jni/filters/kmeans.cc
+++ b/jni/filters/kmeans.cc
@@ -21,25 +21,59 @@
 extern "C" {
 #endif
 
-void JNIFUNCF(ImageFilterKMeans, nativeApplyFilter, jobject bitmap, jint width, jint height, jint p)
+/*
+ * For reasonable speeds:
+ * k < 30
+ * small_ds_bitmap width/height < 64 pixels.
+ * large_ds_bitmap width/height < 512 pixels
+ *
+ * bad for high-frequency image noise
+ */
+
+void JNIFUNCF(ImageFilterKMeans, nativeApplyFilter, jobject bitmap, jint width, jint height,
+        jobject large_ds_bitmap, jint lwidth, jint lheight, jobject small_ds_bitmap,
+        jint swidth, jint sheight, jint p, jint seed)
 {
     char* destination = 0;
+    char* larger_ds_dst = 0;
+    char* smaller_ds_dst = 0;
     AndroidBitmap_lockPixels(env, bitmap, (void**) &destination);
+    AndroidBitmap_lockPixels(env, large_ds_bitmap, (void**) &larger_ds_dst);
+    AndroidBitmap_lockPixels(env, small_ds_bitmap, (void**) &smaller_ds_dst);
     unsigned char * dst = (unsigned char *) destination;
 
-    int len = width * height * 4;
+    unsigned char * small_ds = (unsigned char *) smaller_ds_dst;
+    unsigned char * large_ds = (unsigned char *) larger_ds_dst;
+
+    // setting for small bitmap
+    int len = swidth * sheight * 4;
     int dimension = 3;
     int stride = 4;
-    int iterations = 4;
+    int iterations = 20;
     int k = p;
+    unsigned int s = seed;
     unsigned char finalCentroids[k * stride];
 
-    // TODO: add downsampling and better heuristic to improve speed, then up iterations
+    // get initial picks from small downsampled image
+    runKMeans<unsigned char, int>(k, finalCentroids, small_ds, len, dimension,
+            stride, iterations, s);
+
+
+    len = lwidth * lheight * 4;
+    iterations = 8;
+    unsigned char nextCentroids[k * stride];
+
+    // run kmeans on large downsampled image
+    runKMeansWithPicks<unsigned char, int>(k, nextCentroids, large_ds, len,
+            dimension, stride, iterations, finalCentroids);
+
+    len = width * height * 4;
 
-    // does K-Means clustering on rgb bitmap colors
-    runKMeans<unsigned char, int>(k, finalCentroids, dst, len, dimension, stride, iterations);
-    applyCentroids<unsigned char, int>(k, finalCentroids, dst, len, dimension, stride);
+    // apply to final image
+    applyCentroids<unsigned char, int>(k, nextCentroids, dst, len, dimension, stride);
 
+    AndroidBitmap_unlockPixels(env, small_ds_bitmap);
+    AndroidBitmap_unlockPixels(env, large_ds_bitmap);
     AndroidBitmap_unlockPixels(env, bitmap);
 }
 #ifdef __cplusplus
diff --git a/jni/filters/kmeans.h b/jni/filters/kmeans.h
index eb6544c63..24506058a 100644
--- a/jni/filters/kmeans.h
+++ b/jni/filters/kmeans.h
@@ -17,7 +17,6 @@
 #ifndef KMEANS_H
 #define KMEANS_H
 
-#include <ctime>
 #include <cstdlib>
 #include <math.h>
 
@@ -86,11 +85,12 @@ inline N euclideanDist(T val1[], T val2[], int dimension) {
  * Picks k random starting points from the data set.
  */
 template <typename T>
-void initialPickHeuristicRandom(int k, T values[], int len, int dimension, int stride, T dst[]) {
+void initialPickHeuristicRandom(int k, T values[], int len, int dimension, int stride, T dst[],
+        unsigned int seed) {
     int x, z, num_vals, cntr;
     num_vals = len / stride;
     cntr = 0;
-    srand((unsigned)time(0));
+    srand(seed);
     unsigned int r_vals[k];
     unsigned int r;
 
@@ -175,36 +175,45 @@ int calculateNewCentroids(int k, T values[], int len, int dimension, int stride,
     return ret;
 }
 
+template <typename T, typename N>
+void runKMeansWithPicks(int k, T finalCentroids[], T values[], int len, int dimension, int stride,
+        int iterations, T initialPicks[]){
+        int k_len = k * stride;
+        int x;
+
+        // zero newCenters
+        for (x = 0; x < k_len; x++) {
+            finalCentroids[x] = 0;
+        }
+
+        T * c1 = initialPicks;
+        T * c2 = finalCentroids;
+        T * temp;
+        int ret = 1;
+        for (x = 0; x < iterations; x++) {
+            ret = calculateNewCentroids<T, N>(k, values, len, dimension, stride, c1, c2);
+            temp = c1;
+            c1 = c2;
+            c2 = temp;
+            if (ret == 0) {
+                x = iterations;
+            }
+        }
+        set<T, T>(finalCentroids, c1, dimension);
+}
+
 /**
  * Runs the k-means algorithm on dataset values with some initial centroids.
  */
 template <typename T, typename N>
 void runKMeans(int k, T finalCentroids[], T values[], int len, int dimension, int stride,
-        int iterations){
+        int iterations, unsigned int seed){
     int k_len = k * stride;
-    int x;
     T initialPicks [k_len];
-    initialPickHeuristicRandom<T>(k, values, len, dimension, stride, initialPicks);
-
-    // zero newCenters
-    for (x = 0; x < k_len; x++) {
-        finalCentroids[x] = 0;
-    }
+    initialPickHeuristicRandom<T>(k, values, len, dimension, stride, initialPicks, seed);
 
-    T * c1 = initialPicks;
-    T * c2 = finalCentroids;
-    T * temp;
-    int ret = 1;
-    for (x = 0; x < iterations; x++) {
-        ret = calculateNewCentroids<T, N>(k, values, len, dimension, stride, c1, c2);
-        temp = c1;
-        c1 = c2;
-        c2 = temp;
-        if (ret == 0) {
-            x = iterations;
-        }
-    }
-    set<T, T>(finalCentroids, c1, dimension);
+    runKMeansWithPicks<T, N>(k, finalCentroids, values, len, dimension, stride,
+        iterations, initialPicks);
 }
 
 /**
diff --git a/src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java b/src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java
index 3c725ac81..f03baca39 100644
--- a/src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java
+++ b/src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java
@@ -13,13 +13,17 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
+
 package com.android.gallery3d.filtershow.filters;
 
 import android.graphics.Bitmap;
+import android.text.format.Time;
 
 import com.android.gallery3d.R;
 
 public class ImageFilterKMeans extends ImageFilter {
+    private int mSeed = 0;
+
     public ImageFilterKMeans() {
         mName = "KMeans";
         mMaxParameter = 20;
@@ -27,9 +31,16 @@ public class ImageFilterKMeans extends ImageFilter {
         mPreviewParameter = 4;
         mDefaultParameter = 4;
         mParameter = 4;
+
+        // set random seed for session
+        Time t = new Time();
+        t.setToNow();
+        mSeed = (int) t.toMillis(false);
     }
 
-    native protected void nativeApplyFilter(Bitmap bitmap, int w, int h, int p);
+    native protected void nativeApplyFilter(Bitmap bitmap, int width, int height,
+            Bitmap large_ds_bm, int lwidth, int lheight, Bitmap small_ds_bm,
+            int swidth, int sheight, int p, int seed);
 
     @Override
     public int getButtonId() {
@@ -50,8 +61,34 @@ public class ImageFilterKMeans extends ImageFilter {
     public Bitmap apply(Bitmap bitmap, float scaleFactor, boolean highQuality) {
         int w = bitmap.getWidth();
         int h = bitmap.getHeight();
+
+        Bitmap large_bm_ds = bitmap;
+        Bitmap small_bm_ds = bitmap;
+
+        // find width/height for larger downsampled bitmap
+        int lw = w;
+        int lh = h;
+        while (lw > 256 && lh > 256) {
+            lw /= 2;
+            lh /= 2;
+        }
+        if (lw != w) {
+            large_bm_ds = Bitmap.createScaledBitmap(bitmap, lw, lh, true);
+        }
+
+        // find width/height for smaller downsampled bitmap
+        int sw = lw;
+        int sh = lh;
+        while (sw > 64 && sh > 64) {
+            sw /= 2;
+            sh /= 2;
+        }
+        if (sw != lw) {
+            small_bm_ds = Bitmap.createScaledBitmap(large_bm_ds, sw, sh, true);
+        }
+
         int p = Math.max(mParameter, mMinParameter) % (mMaxParameter + 1);
-        nativeApplyFilter(bitmap, w, h, p);
+        nativeApplyFilter(bitmap, w, h, large_bm_ds, lw, lh, small_bm_ds, sw, sh, p, mSeed);
         return bitmap;
     }
 }