michael@0: // -*- mode: js2; indent-tabs-mode: nil; -*-
michael@0: 
michael@0: // Adapted from
michael@0: //
michael@0: // https://github.com/RiverTrail/RiverTrail/blob/master/examples/liquid-resize/resize-compute-dp.js
michael@0: //
michael@0: // which in turn is based on an algorithm from the paper below (which
michael@0: // also appeared in ACM SIGGRAPH 2007):
michael@0: // Shai Avidan and Ariel Shamir. 2007. Seam carving for content-aware image resizing.
michael@0: // ACM Trans. Graph. 26, 3, Article 10 (July 2007).
michael@0: // DOI=10.1145/1276377.1276390 http://doi.acm.org/10.1145/1276377.1276390
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // Inputs
michael@0: 
michael@0: function buildArray(width, height, func) {
michael@0:   var length = width * height;
michael@0:   var array = new Array(length);
michael@0:   var index = 0;
michael@0:   for (var y = 0; y < height; y++) {
michael@0:     for (var x = 0; x < width; x++) {
michael@0:       array[index++] = func(y, x);
michael@0:     }
michael@0:   }
michael@0:   return array;
michael@0: }
michael@0: 
michael@0: function parImage(seqImage, width, height) {
michael@0:   return new ParallelArray([height, width], function (y, x) {
michael@0:     return seqImage[y*width + x];
michael@0:   });
michael@0: }
michael@0: 
michael@0: var tinyImage =
michael@0:   buildArray(20, 5, function(y, x) {
michael@0:     var ret;
michael@0:     if (6 <= x && x < 8 && 0 <= y && y < 4)
michael@0:       ret = ".";
michael@0:     else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
michael@0:       ret = "^";
michael@0:     else if ((x-20)*(x-20)+(y-3)*(y-3) < 2)
michael@0:       ret = "%";
michael@0:     else if ((x-1)*(x-1)+(y-3)*(y-3) < 2)
michael@0:       ret = "@";
michael@0:     else
michael@0:       ret = " ";
michael@0:     return ret.charCodeAt(0) - 32;
michael@0:   });
michael@0: 
michael@0: var SmallImageWidth = 60;
michael@0: var SmallImageHeight = 15;
michael@0: var SmallImage =
michael@0:   buildArray(SmallImageWidth, SmallImageHeight, function(y, x) {
michael@0:     var ret;
michael@0:     if (6 <= x && x < 8 && 0 <= y && y < 7)
michael@0:       ret = ".";
michael@0:     else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
michael@0:       ret = "^";
michael@0:     else if ((x-40)*(x-40)+(y-6)*(y-6) < 6)
michael@0:       ret = "%";
michael@0:     else if ((x-1)*(x-1)+(y-12)*(y-12) < 2)
michael@0:       ret = "@";
michael@0:     else
michael@0:       ret = " ";
michael@0:     return ret.charCodeAt(0) - 32;
michael@0:   });
michael@0: 
michael@0: var SmallImagePar = parImage(SmallImage,
michael@0:                              SmallImageWidth,
michael@0:                              SmallImageHeight);
michael@0: 
michael@0: var bigImage =
michael@0:   buildArray(200, 70, function(y, x) {
michael@0:     var ret;
michael@0:     if (4 <= x && x < 7 && 10 <= y && y < 40)
michael@0:       ret = ".";
michael@0:     else if ((x-150)*(x-150)+(y-13)*(y-13) < 70)
michael@0:       ret = "^";
michael@0:     else if ((x-201)*(x-201)+(y-33)*(y-33) < 200)
michael@0:       ret = "%";
michael@0:     else if ((x-15)*(x-15)+(y-3)*(y-3) < 7)
michael@0:       ret = "@";
michael@0:     else
michael@0:       ret = " ";
michael@0:     return ret.charCodeAt(0) - 32;
michael@0:   });
michael@0: 
michael@0: // randomImage: Nat Nat Nat Nat -> RectArray
michael@0: function randomImage(w, h, sparsity, variety) {
michael@0:   return buildArray(w, h, function (x,y) {
michael@0:     if (Math.random() > 1/sparsity)
michael@0:       return 0;
michael@0:     else
michael@0:       return 1+Math.random()*variety|0;
michael@0:   });
michael@0: }
michael@0: 
michael@0: // stripedImage: Nat Nat -> RectArray
michael@0: function stripedImage(w, h) {
michael@0:   return buildArray(w, h, function (y, x) {
michael@0:     return (Math.abs(x%100-y%100) < 10) ? 32 : 0;
michael@0:   });
michael@0: }
michael@0: 
michael@0: var massiveImage =
michael@0:   buildArray(70, 10000, function(y, x) (Math.abs(x%100-y%100) < 10) ? 32 : 0);
michael@0: 
michael@0: function printImage(array, width, height) {
michael@0:   print("Width", width, "Height", height);
michael@0:   for (var y = 0; y < height; y++) {
michael@0:     var line = "";
michael@0:     for (var x = 0; x < width; x++) {
michael@0:       var c = array[y*width + x];
michael@0:       line += String.fromCharCode(c + 32);
michael@0:     }
michael@0:     print(line);
michael@0:   }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // Common
michael@0: 
michael@0: var SobelX = [[-1.0,  0.0,  1.0],
michael@0:               [-2.0,  0.0,  2.0],
michael@0:               [-1.0,  0.0,  1.0]];
michael@0: var SobelY = [[ 1.0,  2.0,  1.0],
michael@0:               [ 0.0,  0.0,  0.0],
michael@0:               [-1.0, -2.0, -1.0]];
michael@0: 
michael@0: // computeEnergy: Array -> RectArray
michael@0: //
michael@0: // (The return type is forced upon us, for now at least, until we add
michael@0: // appropriate API to ParallelArray; there's a dependency from each
michael@0: // row upon its predecessor, but the contents of each row could be
michael@0: // computed in parallel.)
michael@0: function computeEnergy(source, width, height) {
michael@0:   var energy = new Array(width * height);
michael@0:   energy[0] = 0;
michael@0:   for (var y = 0; y < height; y++) {
michael@0:     for (var x = 0; x < width; x++) {
michael@0:       var e = source[y*width + x];
michael@0:       if (y >= 1) {
michael@0:         var p = energy[(y-1)*width + x];
michael@0:         if (x > 0) {
michael@0:           p = Math.min(p, energy[(y-1)*width + x-1]);
michael@0:         }
michael@0:         if (x < (width - 1)) {
michael@0:           p = Math.min(p, energy[(y-1)*width + x+1]);
michael@0:         }
michael@0:         e += p;
michael@0:       }
michael@0:       energy[y*width + x] = e;
michael@0:     }
michael@0:   }
michael@0:   return energy;
michael@0: }
michael@0: 
michael@0: // findPath: RectArray -> Array
michael@0: // (This is inherently sequential.)
michael@0: function findPath(energy, width, height)
michael@0: {
michael@0:   var path = new Array(height);
michael@0:   var y = height - 1;
michael@0:   var minPos = 0;
michael@0:   var minEnergy = energy[y*width + minPos];
michael@0: 
michael@0:   for (var x = 1; x < width; x++) {
michael@0:     if (energy[y+width + x] < minEnergy) {
michael@0:       minEnergy = energy[y*width + x];
michael@0:       minPos = x;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   path[y] = minPos;
michael@0:   for (y = height - 2; y >= 0; y--) {
michael@0:     minEnergy = energy[y*width + minPos];
michael@0:     // var line = energy[y]
michael@0:     var p = minPos;
michael@0:     if (p >= 1 && energy[y*width + p-1] < minEnergy) {
michael@0:       minPos = p-1; minEnergy = energy[y*width + p-1];
michael@0:     }
michael@0:     if (p < width - 1 && energy[y*width + p+1] < minEnergy) {
michael@0:       minPos = p+1; minEnergy = energy[y*width + p+1];
michael@0:     }
michael@0:     path[y] = minPos;
michael@0:   }
michael@0:   return path;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // Sequential
michael@0: 
michael@0: function transposeSeq(array, width, height) {
michael@0:   return buildArray(height, width, function(y, x) {
michael@0:     return array[x*width + y];
michael@0:   });
michael@0: }
michael@0: 
michael@0: // detectEdgesSeq: Array Nat Nat -> Array
michael@0: function detectEdgesSeq(data, width, height) {
michael@0:   var data1 = new Array(width * height);
michael@0:   for (var y = 0; y < height; y++) {
michael@0:     for (var x = 0; x < width; x++) {
michael@0:       var total = compute(y, x);
michael@0:       data1[y*width + x] = total | 0;
michael@0:     }
michael@0:   }
michael@0:   return data1;
michael@0: 
michael@0:   function compute(y, x) {
michael@0:     var totalX = 0;
michael@0:     var totalY = 0;
michael@0: 
michael@0:     var offYMin = (y == 0 ? 0 : -1);
michael@0:     var offYMax = (y == height - 1 ? 0 : 1);
michael@0:     var offXMin = (x == 0 ? 0 : -1);
michael@0:     var offXMax = (x == width - 1 ? 0 : 1);
michael@0: 
michael@0:     for (var offY = offYMin; offY <= offYMax; offY++) {
michael@0:       for (var offX = offXMin; offX <= offXMax; offX++) {
michael@0:         var e = data[(y + offY) * width + x + offX];
michael@0:         totalX += e * SobelX[offY + 1][offX + 1];
michael@0:         totalY += e * SobelY[offY + 1][offX + 1];
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     return (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
michael@0:   }
michael@0: }
michael@0: 
michael@0: function cutPathHorizontallyBWSeq(array, width, height, path) {
michael@0:   return buildArray(width-1, height, function (y, x) {
michael@0:     if (x < path[y]-1)
michael@0:       return array[y*width + x];
michael@0:     if (x == path[y]-1)
michael@0:       return (array[y*width + x] + array[y*width + x+1]) / 2 | 0;
michael@0:     else
michael@0:       return array[y*width + x+1];
michael@0:   });
michael@0: }
michael@0: 
michael@0: function cutPathVerticallyBWSeq(array, width, height, path) {
michael@0:   return buildArray(width, height-1, function (y, x) {
michael@0:     if (y < path[x]-1)
michael@0:       return array[y*width + x];
michael@0:     if (y == path[x]-1)
michael@0:       return (array[y*width + x] + array[(y+1)*width + x]) / 2 | 0;
michael@0:     else
michael@0:       return array[(y+1)*width + x];
michael@0:   });
michael@0: }
michael@0: 
michael@0: function cutHorizontalSeamBWSeq(array, width, height)
michael@0: {
michael@0:   var edges = detectEdgesSeq(array, width, height);
michael@0:   var energy = computeEnergy(edges, width, height);
michael@0:   var path = findPath(energy, width, height);
michael@0:   edges = null; // no longer live
michael@0:   return cutPathHorizontallyBWSeq(array, width, height, path);
michael@0: }
michael@0: 
michael@0: function cutVerticalSeamBWSeq(array, width, height)
michael@0: {
michael@0:   var arrayT = transposeSeq(array, width, height);
michael@0:   var edges = detectEdgesSeq(arrayT, height, width);
michael@0:   var energy = computeEnergy(edges, height, width);
michael@0:   var path = findPath(energy, height, width);
michael@0:   edges = null; // no longer live
michael@0:   return cutPathVerticallyBWSeq(array, width, height, path);
michael@0: }
michael@0: 
michael@0: function reduceImageBWSeq(image,
michael@0:                           width, height,
michael@0:                           newWidth, newHeight,
michael@0:                           intermediateFunc,
michael@0:                           finalFunc) {
michael@0:   while (width > newWidth || height > newHeight) {
michael@0:     intermediateFunc(image, width, height);
michael@0: 
michael@0:     if (width > newWidth) {
michael@0:       image = cutHorizontalSeamBWSeq(image, width, height);
michael@0:       width -= 1;
michael@0:     }
michael@0: 
michael@0:     if (height > newHeight) {
michael@0:       image = cutVerticalSeamBWSeq(image, width, height);
michael@0:       height -= 1;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   finalFunc(image, width, height);
michael@0:   return image;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // Parallel
michael@0: 
michael@0: function transposePar(image) {
michael@0:   var height = image.shape[0];
michael@0:   var width = image.shape[1];
michael@0:   return new ParallelArray([width, height], function (y, x) {
michael@0:     return image.get(x, y);
michael@0:   });
michael@0: }
michael@0: 
michael@0: // detectEdgesSeq: Array Nat Nat -> Array
michael@0: function detectEdgesPar(image) {
michael@0:   var height = image.shape[0];
michael@0:   var width = image.shape[1];
michael@0:   return new ParallelArray([height, width], function (y, x) {
michael@0:     var totalX = 0;
michael@0:     var totalY = 0;
michael@0: 
michael@0:     var offYMin = (y == 0 ? 0 : -1);
michael@0:     var offYMax = (y == height - 1 ? 0 : 1);
michael@0:     var offXMin = (x == 0 ? 0 : -1);
michael@0:     var offXMax = (x == width - 1 ? 0 : 1);
michael@0: 
michael@0:     for (var offY = offYMin; offY <= offYMax; offY++) {
michael@0:       for (var offX = offXMin; offX <= offXMax; offX++) {
michael@0:         var e = image.get(y + offY, x + offX);
michael@0:         totalX += e * SobelX[offY + 1][offX + 1];
michael@0:         totalY += e * SobelY[offY + 1][offX + 1];
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     var result = (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
michael@0:     return result;
michael@0:   });
michael@0: }
michael@0: 
michael@0: function cutPathHorizontallyBWPar(image, path) {
michael@0:   var height = image.shape[0];
michael@0:   var width = image.shape[1];
michael@0:   return new ParallelArray([height, width-1], function (y, x) {
michael@0:     if (x < path[y]-1)
michael@0:       return image.get(y, x);
michael@0:     if (x == path[y]-1)
michael@0:       return (image.get(y, x) + image.get(y, x+1)) / 2 | 0;
michael@0:     else
michael@0:       return image.get(y, x+1);
michael@0:   });
michael@0: }
michael@0: 
michael@0: function cutPathVerticallyBWPar(image, path) {
michael@0:   var height = image.shape[0];
michael@0:   var width = image.shape[1];
michael@0:   return new ParallelArray([height-1, width], function (y, x) {
michael@0:     if (y < path[x]-1)
michael@0:       return image.get(y, x);
michael@0:     if (y == path[x]-1)
michael@0:       return (image.get(y, x) + image.get(y+1, x)) / 2 | 0;
michael@0:     else
michael@0:       return image.get(y+1, x);
michael@0:   });
michael@0: }
michael@0: 
michael@0: function cutHorizontalSeamBWPar(image)
michael@0: {
michael@0:   var height = image.shape[0];
michael@0:   var width = image.shape[1];
michael@0:   var edges = detectEdgesPar(image);
michael@0:   var energy = computeEnergy(edges.buffer, width, height);
michael@0:   var path = findPath(energy, width, height);
michael@0:   edges = null; // no longer live
michael@0:   return cutPathHorizontallyBWPar(image, path);
michael@0: }
michael@0: 
michael@0: function cutVerticalSeamBWPar(image) {
michael@0:   var height = image.shape[0];
michael@0:   var width = image.shape[1];
michael@0:   var imageT = transposePar(image);
michael@0:   var edges = detectEdgesPar(imageT);
michael@0:   var energy = computeEnergy(edges.buffer, height, width);
michael@0:   var path = findPath(energy, height, width);
michael@0:   edges = null; // no longer live
michael@0:   return cutPathVerticallyBWPar(image, path);
michael@0: }
michael@0: 
michael@0: function reduceImageBWPar(image,
michael@0:                           newWidth, newHeight,
michael@0:                           intermediateFunc,
michael@0:                           finalFunc) {
michael@0:   var height = image.shape[0];
michael@0:   var width = image.shape[1];
michael@0:   while (width > newWidth || height > newHeight) {
michael@0:     intermediateFunc(image.buffer, width, height);
michael@0: 
michael@0:     if (width > newWidth) {
michael@0:       image = cutHorizontalSeamBWPar(image);
michael@0:       width -= 1;
michael@0:     }
michael@0: 
michael@0:     if (height > newHeight) {
michael@0:       image = cutVerticalSeamBWPar(image);
michael@0:       height -= 1;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   finalFunc(image.buffer, width, height);
michael@0:   return image.buffer;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // Benchmarking via run.sh
michael@0: 
michael@0: var BenchmarkImageWidth = 512;
michael@0: var BenchmarkImageHeight = 256;
michael@0: var BenchmarkImage = stripedImage(BenchmarkImageWidth,
michael@0:                                   BenchmarkImageHeight);
michael@0: var BenchmarkImagePar = parImage(BenchmarkImage,
michael@0:                                  BenchmarkImageWidth,
michael@0:                                  BenchmarkImageHeight);
michael@0: 
michael@0: var benchmarking = (typeof(MODE) != "undefined");
michael@0: if (benchmarking) {
michael@0:   load(libdir + "util.js");
michael@0:   benchmark("LIQUID-RESIZE", 1, DEFAULT_MEASURE,
michael@0:             function() {
michael@0:               return reduceImageBWSeq(
michael@0:                 BenchmarkImage,
michael@0:                 BenchmarkImageWidth, BenchmarkImageHeight,
michael@0:                 BenchmarkImageWidth/2, BenchmarkImageHeight/2,
michael@0:                 function() {},
michael@0:                 function() {});
michael@0:             },
michael@0: 
michael@0:             function() {
michael@0:               return reduceImageBWPar(
michael@0:                 BenchmarkImagePar,
michael@0:                 BenchmarkImageWidth/2, BenchmarkImageHeight/2,
michael@0:                 function() {},
michael@0:                 function() {});
michael@0:             });
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // Running (sanity check)
michael@0: 
michael@0: if (!benchmarking) {
michael@0:   var seqData =
michael@0:     reduceImageBWSeq(SmallImage, SmallImageWidth, SmallImageHeight,
michael@0:                      SmallImageWidth - 15, SmallImageHeight - 10,
michael@0:                      function() {},
michael@0:                      printImage);
michael@0: 
michael@0:   var parData =
michael@0:     reduceImageBWPar(SmallImagePar,
michael@0:                      SmallImageWidth - 15, SmallImageHeight - 10,
michael@0:                      function() {},
michael@0:                      printImage);
michael@0: 
michael@0:   var failed = false;
michael@0:   assertEq(seqData.length, parData.length);
michael@0:   for (var i = 0; i < seqData.length; i++) {
michael@0:     if (seqData[i] !== parData[i]) {
michael@0:       print("At index ", i, " sequential has ", seqData[i], " parallel has ", parData[i]);
michael@0:       failed = true;
michael@0:     }
michael@0:   }
michael@0:   if (failed)
michael@0:     throw new Error();
michael@0: }