summaryrefslogtreecommitdiffstats
path: root/jni
diff options
context:
space:
mode:
authorRuben Brunk <rubenbrunk@google.com>2012-12-13 05:35:12 (GMT)
committerRuben Brunk <rubenbrunk@google.com>2012-12-13 08:49:28 (GMT)
commit38993ed6b4bf0ac767083afb443d7f791d23efce (patch)
tree8fe1bcad5ddc22e37d4be863316770167907eb87 /jni
parentba8175a4ab682d334aef0a2af11240ecc9e9be81 (diff)
downloadandroid_packages_apps_Snap-38993ed6b4bf0ac767083afb443d7f791d23efce.zip
android_packages_apps_Snap-38993ed6b4bf0ac767083afb443d7f791d23efce.tar.gz
android_packages_apps_Snap-38993ed6b4bf0ac767083afb443d7f791d23efce.tar.bz2
Added K-Means clustering filter.
Change-Id: If8961d4a21de953b754cf74aefc222b6bec902a3
Diffstat (limited to 'jni')
-rw-r--r--jni/Android.mk3
-rw-r--r--jni/filters/kmeans.cc47
-rw-r--r--jni/filters/kmeans.h223
3 files changed, 272 insertions, 1 deletions
diff --git a/jni/Android.mk b/jni/Android.mk
index 6f12b3e..adc5bd3 100644
--- a/jni/Android.mk
+++ b/jni/Android.mk
@@ -43,7 +43,8 @@ LOCAL_SRC_FILES := filters/bw.c \
filters/wbalance.c \
filters/redeye.c \
filters/bwfilter.c \
- filters/tinyplanet.cc
+ filters/tinyplanet.cc \
+ filters/kmeans.cc
LOCAL_CFLAGS += -ffast-math -O3 -funroll-loops
LOCAL_ARM_MODE := arm
diff --git a/jni/filters/kmeans.cc b/jni/filters/kmeans.cc
new file mode 100644
index 0000000..599657c
--- /dev/null
+++ b/jni/filters/kmeans.cc
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "filters.h"
+#include "kmeans.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void JNIFUNCF(ImageFilterKMeans, nativeApplyFilter, jobject bitmap, jint width, jint height, jint p)
+{
+ char* destination = 0;
+ AndroidBitmap_lockPixels(env, bitmap, (void**) &destination);
+ unsigned char * dst = (unsigned char *) destination;
+
+ int len = width * height * 4;
+ int dimension = 3;
+ int stride = 4;
+ int iterations = 4;
+ int k = p;
+ unsigned char finalCentroids[k * stride];
+
+ // TODO: add downsampling and better heuristic to improve speed, then up iterations
+
+ // 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);
+
+ AndroidBitmap_unlockPixels(env, bitmap);
+}
+#ifdef __cplusplus
+}
+#endif
diff --git a/jni/filters/kmeans.h b/jni/filters/kmeans.h
new file mode 100644
index 0000000..eb6544c
--- /dev/null
+++ b/jni/filters/kmeans.h
@@ -0,0 +1,223 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef KMEANS_H
+#define KMEANS_H
+
+#include <ctime>
+#include <cstdlib>
+#include <math.h>
+
+// Helper functions
+
+template <typename T, typename N>
+inline void sum(T values[], int len, int dimension, int stride, N dst[]) {
+ int x, y;
+ // zero out dst vector
+ for (x = 0; x < dimension; x++) {
+ dst[x] = 0;
+ }
+ for (x = 0; x < len; x+= stride) {
+ for (y = 0; y < dimension; y++) {
+ dst[y] += values[x + y];
+ }
+ }
+}
+
+template <typename T, typename N>
+inline void set(T val1[], N val2[], int dimension) {
+ int x;
+ for (x = 0; x < dimension; x++) {
+ val1[x] = val2[x];
+ }
+}
+
+template <typename T, typename N>
+inline void add(T val[], N dst[], int dimension) {
+ int x;
+ for (x = 0; x < dimension; x++) {
+ dst[x] += val[x];
+ }
+}
+
+template <typename T, typename N>
+inline void divide(T dst[], N divisor, int dimension) {
+ int x;
+ if (divisor == 0) {
+ return;
+ }
+ for (x = 0; x < dimension; x++) {
+ dst[x] /= divisor;
+ }
+}
+
+/**
+ * Calculates euclidean distance.
+ */
+
+template <typename T, typename N>
+inline N euclideanDist(T val1[], T val2[], int dimension) {
+ int x;
+ N sum = 0;
+ for (x = 0; x < dimension; x++) {
+ N diff = (N) val1[x] - (N) val2[x];
+ sum += diff * diff;
+ }
+ return sqrt(sum);
+}
+
+// K-Means
+
+
+/**
+ * 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[]) {
+ int x, z, num_vals, cntr;
+ num_vals = len / stride;
+ cntr = 0;
+ srand((unsigned)time(0));
+ unsigned int r_vals[k];
+ unsigned int r;
+
+ for (x = 0; x < k; x++) {
+
+ // ensure randomly chosen value is unique
+ int r_check = 0;
+ while (r_check == 0) {
+ r = (unsigned int) rand() % num_vals;
+ r_check = 1;
+ for (z = 0; z < x; z++) {
+ if (r == r_vals[z]) {
+ r_check = 0;
+ }
+ }
+ }
+ r_vals[x] = r;
+ r *= stride;
+
+ // set dst to be randomly chosen value
+ set<T,T>(dst + cntr, values + r, dimension);
+ cntr += stride;
+ }
+}
+
+/**
+ * Finds index of closet centroid to a value
+ */
+template <typename T, typename N>
+inline int findClosest(T values[], T oldCenters[], int dimension, int stride, int pop_size) {
+ int best_ind = 0;
+ N best_len = euclideanDist <T, N>(values, oldCenters, dimension);
+ int y;
+ for (y = stride; y < pop_size; y+=stride) {
+ N l = euclideanDist <T, N>(values, oldCenters + y, dimension);
+ if (l < best_len) {
+ best_len = l;
+ best_ind = y;
+ }
+ }
+ return best_ind;
+}
+
+/**
+ * Calculates new centroids by averaging value clusters for old centroids.
+ */
+template <typename T, typename N>
+int calculateNewCentroids(int k, T values[], int len, int dimension, int stride, T oldCenters[],
+ T dst[]) {
+ int x, pop_size;
+ pop_size = k * stride;
+ int popularities[k];
+ N tmp[pop_size];
+
+ //zero popularities
+ memset(popularities, 0, sizeof(int) * k);
+ // zero dst, and tmp
+ for (x = 0; x < pop_size; x++) {
+ tmp[x] = 0;
+ }
+
+ // put summation for each k in tmp
+ for (x = 0; x < len; x+=stride) {
+ int best = findClosest<T, N>(values + x, oldCenters, dimension, stride, pop_size);
+ add<T, N>(values + x, tmp + best, dimension);
+ popularities[best / stride]++;
+
+ }
+
+ int ret = 0;
+ int y;
+ // divide to get centroid and set dst to result
+ for (x = 0; x < pop_size; x+=stride) {
+ divide<N, int>(tmp + x, popularities[x / stride], dimension);
+ for (y = 0; y < dimension; y++) {
+ if ((dst + x)[y] != (T) ((tmp + x)[y])) {
+ ret = 1;
+ }
+ }
+ set(dst + x, tmp + x, dimension);
+ }
+ return ret;
+}
+
+/**
+ * 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 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;
+ }
+
+ 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);
+}
+
+/**
+ * Sets each value in values to the closest centroid.
+ */
+template <typename T, typename N>
+void applyCentroids(int k, T centroids[], T values[], int len, int dimension, int stride) {
+ int x, pop_size;
+ pop_size = k * stride;
+ for (x = 0; x < len; x+= stride) {
+ int best = findClosest<T, N>(values + x, centroids, dimension, stride, pop_size);
+ set<T, T>(values + x, centroids + best, dimension);
+ }
+}
+
+#endif // KMEANS_H