1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/parjs-benchmarks/liquid-resize.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,463 @@
1.4 +// -*- mode: js2; indent-tabs-mode: nil; -*-
1.5 +
1.6 +// Adapted from
1.7 +//
1.8 +// https://github.com/RiverTrail/RiverTrail/blob/master/examples/liquid-resize/resize-compute-dp.js
1.9 +//
1.10 +// which in turn is based on an algorithm from the paper below (which
1.11 +// also appeared in ACM SIGGRAPH 2007):
1.12 +// Shai Avidan and Ariel Shamir. 2007. Seam carving for content-aware image resizing.
1.13 +// ACM Trans. Graph. 26, 3, Article 10 (July 2007).
1.14 +// DOI=10.1145/1276377.1276390 http://doi.acm.org/10.1145/1276377.1276390
1.15 +
1.16 +///////////////////////////////////////////////////////////////////////////
1.17 +// Inputs
1.18 +
1.19 +function buildArray(width, height, func) {
1.20 + var length = width * height;
1.21 + var array = new Array(length);
1.22 + var index = 0;
1.23 + for (var y = 0; y < height; y++) {
1.24 + for (var x = 0; x < width; x++) {
1.25 + array[index++] = func(y, x);
1.26 + }
1.27 + }
1.28 + return array;
1.29 +}
1.30 +
1.31 +function parImage(seqImage, width, height) {
1.32 + return new ParallelArray([height, width], function (y, x) {
1.33 + return seqImage[y*width + x];
1.34 + });
1.35 +}
1.36 +
1.37 +var tinyImage =
1.38 + buildArray(20, 5, function(y, x) {
1.39 + var ret;
1.40 + if (6 <= x && x < 8 && 0 <= y && y < 4)
1.41 + ret = ".";
1.42 + else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
1.43 + ret = "^";
1.44 + else if ((x-20)*(x-20)+(y-3)*(y-3) < 2)
1.45 + ret = "%";
1.46 + else if ((x-1)*(x-1)+(y-3)*(y-3) < 2)
1.47 + ret = "@";
1.48 + else
1.49 + ret = " ";
1.50 + return ret.charCodeAt(0) - 32;
1.51 + });
1.52 +
1.53 +var SmallImageWidth = 60;
1.54 +var SmallImageHeight = 15;
1.55 +var SmallImage =
1.56 + buildArray(SmallImageWidth, SmallImageHeight, function(y, x) {
1.57 + var ret;
1.58 + if (6 <= x && x < 8 && 0 <= y && y < 7)
1.59 + ret = ".";
1.60 + else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
1.61 + ret = "^";
1.62 + else if ((x-40)*(x-40)+(y-6)*(y-6) < 6)
1.63 + ret = "%";
1.64 + else if ((x-1)*(x-1)+(y-12)*(y-12) < 2)
1.65 + ret = "@";
1.66 + else
1.67 + ret = " ";
1.68 + return ret.charCodeAt(0) - 32;
1.69 + });
1.70 +
1.71 +var SmallImagePar = parImage(SmallImage,
1.72 + SmallImageWidth,
1.73 + SmallImageHeight);
1.74 +
1.75 +var bigImage =
1.76 + buildArray(200, 70, function(y, x) {
1.77 + var ret;
1.78 + if (4 <= x && x < 7 && 10 <= y && y < 40)
1.79 + ret = ".";
1.80 + else if ((x-150)*(x-150)+(y-13)*(y-13) < 70)
1.81 + ret = "^";
1.82 + else if ((x-201)*(x-201)+(y-33)*(y-33) < 200)
1.83 + ret = "%";
1.84 + else if ((x-15)*(x-15)+(y-3)*(y-3) < 7)
1.85 + ret = "@";
1.86 + else
1.87 + ret = " ";
1.88 + return ret.charCodeAt(0) - 32;
1.89 + });
1.90 +
1.91 +// randomImage: Nat Nat Nat Nat -> RectArray
1.92 +function randomImage(w, h, sparsity, variety) {
1.93 + return buildArray(w, h, function (x,y) {
1.94 + if (Math.random() > 1/sparsity)
1.95 + return 0;
1.96 + else
1.97 + return 1+Math.random()*variety|0;
1.98 + });
1.99 +}
1.100 +
1.101 +// stripedImage: Nat Nat -> RectArray
1.102 +function stripedImage(w, h) {
1.103 + return buildArray(w, h, function (y, x) {
1.104 + return (Math.abs(x%100-y%100) < 10) ? 32 : 0;
1.105 + });
1.106 +}
1.107 +
1.108 +var massiveImage =
1.109 + buildArray(70, 10000, function(y, x) (Math.abs(x%100-y%100) < 10) ? 32 : 0);
1.110 +
1.111 +function printImage(array, width, height) {
1.112 + print("Width", width, "Height", height);
1.113 + for (var y = 0; y < height; y++) {
1.114 + var line = "";
1.115 + for (var x = 0; x < width; x++) {
1.116 + var c = array[y*width + x];
1.117 + line += String.fromCharCode(c + 32);
1.118 + }
1.119 + print(line);
1.120 + }
1.121 +}
1.122 +
1.123 +///////////////////////////////////////////////////////////////////////////
1.124 +// Common
1.125 +
1.126 +var SobelX = [[-1.0, 0.0, 1.0],
1.127 + [-2.0, 0.0, 2.0],
1.128 + [-1.0, 0.0, 1.0]];
1.129 +var SobelY = [[ 1.0, 2.0, 1.0],
1.130 + [ 0.0, 0.0, 0.0],
1.131 + [-1.0, -2.0, -1.0]];
1.132 +
1.133 +// computeEnergy: Array -> RectArray
1.134 +//
1.135 +// (The return type is forced upon us, for now at least, until we add
1.136 +// appropriate API to ParallelArray; there's a dependency from each
1.137 +// row upon its predecessor, but the contents of each row could be
1.138 +// computed in parallel.)
1.139 +function computeEnergy(source, width, height) {
1.140 + var energy = new Array(width * height);
1.141 + energy[0] = 0;
1.142 + for (var y = 0; y < height; y++) {
1.143 + for (var x = 0; x < width; x++) {
1.144 + var e = source[y*width + x];
1.145 + if (y >= 1) {
1.146 + var p = energy[(y-1)*width + x];
1.147 + if (x > 0) {
1.148 + p = Math.min(p, energy[(y-1)*width + x-1]);
1.149 + }
1.150 + if (x < (width - 1)) {
1.151 + p = Math.min(p, energy[(y-1)*width + x+1]);
1.152 + }
1.153 + e += p;
1.154 + }
1.155 + energy[y*width + x] = e;
1.156 + }
1.157 + }
1.158 + return energy;
1.159 +}
1.160 +
1.161 +// findPath: RectArray -> Array
1.162 +// (This is inherently sequential.)
1.163 +function findPath(energy, width, height)
1.164 +{
1.165 + var path = new Array(height);
1.166 + var y = height - 1;
1.167 + var minPos = 0;
1.168 + var minEnergy = energy[y*width + minPos];
1.169 +
1.170 + for (var x = 1; x < width; x++) {
1.171 + if (energy[y+width + x] < minEnergy) {
1.172 + minEnergy = energy[y*width + x];
1.173 + minPos = x;
1.174 + }
1.175 + }
1.176 +
1.177 + path[y] = minPos;
1.178 + for (y = height - 2; y >= 0; y--) {
1.179 + minEnergy = energy[y*width + minPos];
1.180 + // var line = energy[y]
1.181 + var p = minPos;
1.182 + if (p >= 1 && energy[y*width + p-1] < minEnergy) {
1.183 + minPos = p-1; minEnergy = energy[y*width + p-1];
1.184 + }
1.185 + if (p < width - 1 && energy[y*width + p+1] < minEnergy) {
1.186 + minPos = p+1; minEnergy = energy[y*width + p+1];
1.187 + }
1.188 + path[y] = minPos;
1.189 + }
1.190 + return path;
1.191 +}
1.192 +
1.193 +///////////////////////////////////////////////////////////////////////////
1.194 +// Sequential
1.195 +
1.196 +function transposeSeq(array, width, height) {
1.197 + return buildArray(height, width, function(y, x) {
1.198 + return array[x*width + y];
1.199 + });
1.200 +}
1.201 +
1.202 +// detectEdgesSeq: Array Nat Nat -> Array
1.203 +function detectEdgesSeq(data, width, height) {
1.204 + var data1 = new Array(width * height);
1.205 + for (var y = 0; y < height; y++) {
1.206 + for (var x = 0; x < width; x++) {
1.207 + var total = compute(y, x);
1.208 + data1[y*width + x] = total | 0;
1.209 + }
1.210 + }
1.211 + return data1;
1.212 +
1.213 + function compute(y, x) {
1.214 + var totalX = 0;
1.215 + var totalY = 0;
1.216 +
1.217 + var offYMin = (y == 0 ? 0 : -1);
1.218 + var offYMax = (y == height - 1 ? 0 : 1);
1.219 + var offXMin = (x == 0 ? 0 : -1);
1.220 + var offXMax = (x == width - 1 ? 0 : 1);
1.221 +
1.222 + for (var offY = offYMin; offY <= offYMax; offY++) {
1.223 + for (var offX = offXMin; offX <= offXMax; offX++) {
1.224 + var e = data[(y + offY) * width + x + offX];
1.225 + totalX += e * SobelX[offY + 1][offX + 1];
1.226 + totalY += e * SobelY[offY + 1][offX + 1];
1.227 + }
1.228 + }
1.229 +
1.230 + return (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
1.231 + }
1.232 +}
1.233 +
1.234 +function cutPathHorizontallyBWSeq(array, width, height, path) {
1.235 + return buildArray(width-1, height, function (y, x) {
1.236 + if (x < path[y]-1)
1.237 + return array[y*width + x];
1.238 + if (x == path[y]-1)
1.239 + return (array[y*width + x] + array[y*width + x+1]) / 2 | 0;
1.240 + else
1.241 + return array[y*width + x+1];
1.242 + });
1.243 +}
1.244 +
1.245 +function cutPathVerticallyBWSeq(array, width, height, path) {
1.246 + return buildArray(width, height-1, function (y, x) {
1.247 + if (y < path[x]-1)
1.248 + return array[y*width + x];
1.249 + if (y == path[x]-1)
1.250 + return (array[y*width + x] + array[(y+1)*width + x]) / 2 | 0;
1.251 + else
1.252 + return array[(y+1)*width + x];
1.253 + });
1.254 +}
1.255 +
1.256 +function cutHorizontalSeamBWSeq(array, width, height)
1.257 +{
1.258 + var edges = detectEdgesSeq(array, width, height);
1.259 + var energy = computeEnergy(edges, width, height);
1.260 + var path = findPath(energy, width, height);
1.261 + edges = null; // no longer live
1.262 + return cutPathHorizontallyBWSeq(array, width, height, path);
1.263 +}
1.264 +
1.265 +function cutVerticalSeamBWSeq(array, width, height)
1.266 +{
1.267 + var arrayT = transposeSeq(array, width, height);
1.268 + var edges = detectEdgesSeq(arrayT, height, width);
1.269 + var energy = computeEnergy(edges, height, width);
1.270 + var path = findPath(energy, height, width);
1.271 + edges = null; // no longer live
1.272 + return cutPathVerticallyBWSeq(array, width, height, path);
1.273 +}
1.274 +
1.275 +function reduceImageBWSeq(image,
1.276 + width, height,
1.277 + newWidth, newHeight,
1.278 + intermediateFunc,
1.279 + finalFunc) {
1.280 + while (width > newWidth || height > newHeight) {
1.281 + intermediateFunc(image, width, height);
1.282 +
1.283 + if (width > newWidth) {
1.284 + image = cutHorizontalSeamBWSeq(image, width, height);
1.285 + width -= 1;
1.286 + }
1.287 +
1.288 + if (height > newHeight) {
1.289 + image = cutVerticalSeamBWSeq(image, width, height);
1.290 + height -= 1;
1.291 + }
1.292 + }
1.293 +
1.294 + finalFunc(image, width, height);
1.295 + return image;
1.296 +}
1.297 +
1.298 +///////////////////////////////////////////////////////////////////////////
1.299 +// Parallel
1.300 +
1.301 +function transposePar(image) {
1.302 + var height = image.shape[0];
1.303 + var width = image.shape[1];
1.304 + return new ParallelArray([width, height], function (y, x) {
1.305 + return image.get(x, y);
1.306 + });
1.307 +}
1.308 +
1.309 +// detectEdgesSeq: Array Nat Nat -> Array
1.310 +function detectEdgesPar(image) {
1.311 + var height = image.shape[0];
1.312 + var width = image.shape[1];
1.313 + return new ParallelArray([height, width], function (y, x) {
1.314 + var totalX = 0;
1.315 + var totalY = 0;
1.316 +
1.317 + var offYMin = (y == 0 ? 0 : -1);
1.318 + var offYMax = (y == height - 1 ? 0 : 1);
1.319 + var offXMin = (x == 0 ? 0 : -1);
1.320 + var offXMax = (x == width - 1 ? 0 : 1);
1.321 +
1.322 + for (var offY = offYMin; offY <= offYMax; offY++) {
1.323 + for (var offX = offXMin; offX <= offXMax; offX++) {
1.324 + var e = image.get(y + offY, x + offX);
1.325 + totalX += e * SobelX[offY + 1][offX + 1];
1.326 + totalY += e * SobelY[offY + 1][offX + 1];
1.327 + }
1.328 + }
1.329 +
1.330 + var result = (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
1.331 + return result;
1.332 + });
1.333 +}
1.334 +
1.335 +function cutPathHorizontallyBWPar(image, path) {
1.336 + var height = image.shape[0];
1.337 + var width = image.shape[1];
1.338 + return new ParallelArray([height, width-1], function (y, x) {
1.339 + if (x < path[y]-1)
1.340 + return image.get(y, x);
1.341 + if (x == path[y]-1)
1.342 + return (image.get(y, x) + image.get(y, x+1)) / 2 | 0;
1.343 + else
1.344 + return image.get(y, x+1);
1.345 + });
1.346 +}
1.347 +
1.348 +function cutPathVerticallyBWPar(image, path) {
1.349 + var height = image.shape[0];
1.350 + var width = image.shape[1];
1.351 + return new ParallelArray([height-1, width], function (y, x) {
1.352 + if (y < path[x]-1)
1.353 + return image.get(y, x);
1.354 + if (y == path[x]-1)
1.355 + return (image.get(y, x) + image.get(y+1, x)) / 2 | 0;
1.356 + else
1.357 + return image.get(y+1, x);
1.358 + });
1.359 +}
1.360 +
1.361 +function cutHorizontalSeamBWPar(image)
1.362 +{
1.363 + var height = image.shape[0];
1.364 + var width = image.shape[1];
1.365 + var edges = detectEdgesPar(image);
1.366 + var energy = computeEnergy(edges.buffer, width, height);
1.367 + var path = findPath(energy, width, height);
1.368 + edges = null; // no longer live
1.369 + return cutPathHorizontallyBWPar(image, path);
1.370 +}
1.371 +
1.372 +function cutVerticalSeamBWPar(image) {
1.373 + var height = image.shape[0];
1.374 + var width = image.shape[1];
1.375 + var imageT = transposePar(image);
1.376 + var edges = detectEdgesPar(imageT);
1.377 + var energy = computeEnergy(edges.buffer, height, width);
1.378 + var path = findPath(energy, height, width);
1.379 + edges = null; // no longer live
1.380 + return cutPathVerticallyBWPar(image, path);
1.381 +}
1.382 +
1.383 +function reduceImageBWPar(image,
1.384 + newWidth, newHeight,
1.385 + intermediateFunc,
1.386 + finalFunc) {
1.387 + var height = image.shape[0];
1.388 + var width = image.shape[1];
1.389 + while (width > newWidth || height > newHeight) {
1.390 + intermediateFunc(image.buffer, width, height);
1.391 +
1.392 + if (width > newWidth) {
1.393 + image = cutHorizontalSeamBWPar(image);
1.394 + width -= 1;
1.395 + }
1.396 +
1.397 + if (height > newHeight) {
1.398 + image = cutVerticalSeamBWPar(image);
1.399 + height -= 1;
1.400 + }
1.401 + }
1.402 +
1.403 + finalFunc(image.buffer, width, height);
1.404 + return image.buffer;
1.405 +}
1.406 +
1.407 +///////////////////////////////////////////////////////////////////////////
1.408 +// Benchmarking via run.sh
1.409 +
1.410 +var BenchmarkImageWidth = 512;
1.411 +var BenchmarkImageHeight = 256;
1.412 +var BenchmarkImage = stripedImage(BenchmarkImageWidth,
1.413 + BenchmarkImageHeight);
1.414 +var BenchmarkImagePar = parImage(BenchmarkImage,
1.415 + BenchmarkImageWidth,
1.416 + BenchmarkImageHeight);
1.417 +
1.418 +var benchmarking = (typeof(MODE) != "undefined");
1.419 +if (benchmarking) {
1.420 + load(libdir + "util.js");
1.421 + benchmark("LIQUID-RESIZE", 1, DEFAULT_MEASURE,
1.422 + function() {
1.423 + return reduceImageBWSeq(
1.424 + BenchmarkImage,
1.425 + BenchmarkImageWidth, BenchmarkImageHeight,
1.426 + BenchmarkImageWidth/2, BenchmarkImageHeight/2,
1.427 + function() {},
1.428 + function() {});
1.429 + },
1.430 +
1.431 + function() {
1.432 + return reduceImageBWPar(
1.433 + BenchmarkImagePar,
1.434 + BenchmarkImageWidth/2, BenchmarkImageHeight/2,
1.435 + function() {},
1.436 + function() {});
1.437 + });
1.438 +}
1.439 +
1.440 +///////////////////////////////////////////////////////////////////////////
1.441 +// Running (sanity check)
1.442 +
1.443 +if (!benchmarking) {
1.444 + var seqData =
1.445 + reduceImageBWSeq(SmallImage, SmallImageWidth, SmallImageHeight,
1.446 + SmallImageWidth - 15, SmallImageHeight - 10,
1.447 + function() {},
1.448 + printImage);
1.449 +
1.450 + var parData =
1.451 + reduceImageBWPar(SmallImagePar,
1.452 + SmallImageWidth - 15, SmallImageHeight - 10,
1.453 + function() {},
1.454 + printImage);
1.455 +
1.456 + var failed = false;
1.457 + assertEq(seqData.length, parData.length);
1.458 + for (var i = 0; i < seqData.length; i++) {
1.459 + if (seqData[i] !== parData[i]) {
1.460 + print("At index ", i, " sequential has ", seqData[i], " parallel has ", parData[i]);
1.461 + failed = true;
1.462 + }
1.463 + }
1.464 + if (failed)
1.465 + throw new Error();
1.466 +}
