diff options
author | Ruben Brunk <rubenbrunk@google.com> | 2012-12-12 21:35:12 -0800 |
---|---|---|
committer | Ruben Brunk <rubenbrunk@google.com> | 2012-12-13 00:49:28 -0800 |
commit | 27fb72ee1413871b4958ab2f24a229574de6ffa2 (patch) | |
tree | bad70566be85c1b807ce785ad1260a5a84a321a1 | |
parent | 8fd29857977e3ca763266704e2a2c35a59cb522d (diff) | |
download | android_packages_apps_Gallery2-27fb72ee1413871b4958ab2f24a229574de6ffa2.tar.gz android_packages_apps_Gallery2-27fb72ee1413871b4958ab2f24a229574de6ffa2.tar.bz2 android_packages_apps_Gallery2-27fb72ee1413871b4958ab2f24a229574de6ffa2.zip |
Added K-Means clustering filter.
Change-Id: If8961d4a21de953b754cf74aefc222b6bec902a3
-rw-r--r-- | jni/Android.mk | 3 | ||||
-rw-r--r-- | jni/filters/kmeans.cc | 47 | ||||
-rw-r--r-- | jni/filters/kmeans.h | 223 | ||||
-rw-r--r-- | res/values/filtershow_ids.xml | 1 | ||||
-rw-r--r-- | res/values/filtershow_strings.xml | 3 | ||||
-rw-r--r-- | src/com/android/gallery3d/filtershow/FilterShowActivity.java | 4 | ||||
-rw-r--r-- | src/com/android/gallery3d/filtershow/filters/ImageFilterEdge.java | 16 | ||||
-rw-r--r-- | src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java | 57 |
8 files changed, 352 insertions, 2 deletions
diff --git a/jni/Android.mk b/jni/Android.mk index 6f12b3ef4..adc5bd32f 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 000000000..599657c8e --- /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 000000000..eb6544c63 --- /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 diff --git a/res/values/filtershow_ids.xml b/res/values/filtershow_ids.xml index 4ccbd960d..7b18d2d0a 100644 --- a/res/values/filtershow_ids.xml +++ b/res/values/filtershow_ids.xml @@ -32,4 +32,5 @@ <item type="id" name="curvesButtonRGB" /> <item type="id" name="negativeButton" /> <item type="id" name="edgeButton" /> + <item type="id" name="kmeansButton" /> </resources> diff --git a/res/values/filtershow_strings.xml b/res/values/filtershow_strings.xml index 5095e48e1..526982f8f 100644 --- a/res/values/filtershow_strings.xml +++ b/res/values/filtershow_strings.xml @@ -137,6 +137,9 @@ <string name="none" msgid="3601545724573307541">None</string> <!-- Label for the image edges effect (highlights edges in image) [CHAR LIMIT=10] --> <string name="edge">Edges</string> + <!-- Label for an image effect that replicates the "pop art" style of segmenting + images into solid colors, as popularized by Andy Warhol [CHAR LIMIT=10] --> + <string name="kmeans">Warhol</string> <!-- Labels for the curves tool --> diff --git a/src/com/android/gallery3d/filtershow/FilterShowActivity.java b/src/com/android/gallery3d/filtershow/FilterShowActivity.java index a3da0c6be..161321904 100644 --- a/src/com/android/gallery3d/filtershow/FilterShowActivity.java +++ b/src/com/android/gallery3d/filtershow/FilterShowActivity.java @@ -65,6 +65,7 @@ import com.android.gallery3d.filtershow.filters.ImageFilterEdge; import com.android.gallery3d.filtershow.filters.ImageFilterExposure; import com.android.gallery3d.filtershow.filters.ImageFilterFx; import com.android.gallery3d.filtershow.filters.ImageFilterHue; +import com.android.gallery3d.filtershow.filters.ImageFilterKMeans; import com.android.gallery3d.filtershow.filters.ImageFilterNegative; import com.android.gallery3d.filtershow.filters.ImageFilterParametricBorder; import com.android.gallery3d.filtershow.filters.ImageFilterRS; @@ -311,7 +312,8 @@ public class FilterShowActivity extends Activity implements OnItemClickListener, new ImageFilterSaturated(), new ImageFilterBwFilter(), new ImageFilterNegative(), - new ImageFilterEdge() + new ImageFilterEdge(), + new ImageFilterKMeans() }; for (int i = 0; i < filters.length; i++) { diff --git a/src/com/android/gallery3d/filtershow/filters/ImageFilterEdge.java b/src/com/android/gallery3d/filtershow/filters/ImageFilterEdge.java index e2ce0dacd..9eda64874 100644 --- a/src/com/android/gallery3d/filtershow/filters/ImageFilterEdge.java +++ b/src/com/android/gallery3d/filtershow/filters/ImageFilterEdge.java @@ -1,3 +1,19 @@ +/* + * 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. + */ + package com.android.gallery3d.filtershow.filters; import android.graphics.Bitmap; diff --git a/src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java b/src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java new file mode 100644 index 000000000..3c725ac81 --- /dev/null +++ b/src/com/android/gallery3d/filtershow/filters/ImageFilterKMeans.java @@ -0,0 +1,57 @@ +/* + * 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. + */ +package com.android.gallery3d.filtershow.filters; + +import android.graphics.Bitmap; + +import com.android.gallery3d.R; + +public class ImageFilterKMeans extends ImageFilter { + public ImageFilterKMeans() { + mName = "KMeans"; + mMaxParameter = 20; + mMinParameter = 2; + mPreviewParameter = 4; + mDefaultParameter = 4; + mParameter = 4; + } + + native protected void nativeApplyFilter(Bitmap bitmap, int w, int h, int p); + + @Override + public int getButtonId() { + return R.id.kmeansButton; + } + + @Override + public int getTextId() { + return R.string.kmeans; + } + + @Override + public boolean isNil() { + return false; + } + + @Override + public Bitmap apply(Bitmap bitmap, float scaleFactor, boolean highQuality) { + int w = bitmap.getWidth(); + int h = bitmap.getHeight(); + int p = Math.max(mParameter, mMinParameter) % (mMaxParameter + 1); + nativeApplyFilter(bitmap, w, h, p); + return bitmap; + } +} |