Coursera Algorithm Ⅱ week2 Seam

全部代码 https://github.com/Joshmomel/Princeton_Algorithms/tree/seam

背景

本次作业就是resize图片时，删除energy最小的线, 最大程度的保留图片信息, 这里有具体的介绍

具体例子就是通过vertical的裁剪, 虽然两个imagesd的大小是不一样的, 但是保留了最重要的信息, 看上去是没有区别的

步骤就是

1. Energy calculation - 计算image的energy
2. Seam identification - 找出最小的energy路径
3. Seam removal - 删除路径

Implementation

energy

为了performance, 把energy做cache, 如果energy之前计算过, 则读取之前的值, 否则就计算energy

// energy of pixel at column x and row y
  public double energy(int x, int y) {
    validateColumnIndex(x);
    validateRowIndex(y);

    double energy = this.energy[x][y];

    if (energy != 0.0d) {
      return energy;
    }


    if (isBorder(x, y)) {
      this.energy[x][y] = 1000;
      return 1000;
    }

    double energyPixel = Math.sqrt(getDxSquare(x, y) + getDySquare(x, y));
    this.energy[x][y] = energyPixel;

    return energyPixel;
  }

具体energy的计算公式是这样的, 具体可以参考这里的代码

findVerticalSeam

这个是这次assignment的算法重点

这里的核心算法就是 topologial sort algorithm for computing a shortest path in a DAG, 对应需要复习Edge-Weighted DAGs 这个lecture

具体来说需要maintain两个变量
int[] edgeTo = new int[this.size + 1];
double[] distTo = new double[this.size + 1];

然后再起点做BFS, 跟新对应distTo[] 以及 edgeTo[]

for (int y = 0; y < this.height(); y++) {
      for (int x = 0; x < this.width(); x++) {
        ArrayList<Point> nextNodes = getNextNodes(x, y);
        int currentPoint = getNumber(x, y);
        for (Point nextNode : nextNodes) {
          if (distTo[nextNode.number] > distTo[currentPoint] + this.energy(nextNode.x, nextNode.y)) {
            distTo[nextNode.number] = distTo[currentPoint] + this.energy(nextNode.x, nextNode.y);
            edgeTo[nextNode.number] = currentPoint;
          }
        }
      }
    }

有了edgeTo, 反推路径

 double min = distTo[this.size - width() + 1];
    int nodeNumber = this.size - width() + 1;
    for (int i = this.size - width() + 1; i <= this.size; i++) {
      if (distTo[i] < min) {
        min = distTo[i];
        nodeNumber = i;
      }
    }

    int[] minList = new int[this.height()];
    int i = this.height() - 1;
    while (i > -1) {
      minList[i] = toX(nodeNumber);
      nodeNumber = edgeTo[nodeNumber];
      i -= 1;
    }

findVerticalSeam完整代码可以参考这里

findHorizontalSeam

简单来说就是把image做transpose, call findVerticalSeam(), and transpose it back

具体还是比较麻烦的, 需要维护一些变量

1. transposeEnergy 用来保存当前的energy
2. isInTranspose 主要是计算height/width时候用的

public int[] findHorizontalSeam() {
    if (!this.hasSetEnergy) {
      setEnergy();
    }

    int w = this.picture.width();
    int h = this.picture.height();

    double[][] tempEnergy = new double[w][h];
    for (int i = 0; i < w; i++) {
      System.arraycopy(this.energy[i], 0, tempEnergy[i], 0, h);
    }

    this.isInTranspose = true;

    double[][] transposeEnergy = new double[h][w];
    for (int y = 0; y < h; y++) {
      for (int x = 0; x < w; x++) {
        transposeEnergy[y][x] = energy[x][y];
      }
    }
    this.energy = transposeEnergy;

    int[] horizontalSeam = findVerticalSeam();

    this.energy = tempEnergy;
    this.isInTranspose = false;

    return horizontalSeam;
  }

removeVerticalSeam

就是通过移除给定的seam, 重新生成新的图片, 不算太复杂, 只是需要考虑到图片是否在isInTranspose

  public void removeVerticalSeam(int[] seam) {
    if (!isInTranspose) {
      if (seam == null || !isSeamValid(seam)) {
        throw new IllegalArgumentException();
      }
    }

    Picture newPicture = new Picture(this.width() - 1, this.height());
    for (int y = 0; y < this.height(); y++) {
      for (int x = 0; x < this.width(); x++) {
        Color color;
        if (isInTranspose) {
          color = this.picture.get(y, x);
        } else {
          color = this.picture.get(x, y);
        }
        if (x < seam[y]) {
          newPicture.set(x, y, color);
        }
        if (x > seam[y]) {
          newPicture.set(x - 1, y, color);
        }
      }
    }
    this.picture = newPicture;
    this.width = newPicture.width();
    this.height = newPicture.height();
    update();
    this.hasSetEnergy = false;
    this.isInTranspose = false;
  }

removeHorizontalSeam

同理, removeHorizontalSeam就是transpose the image, call removeVerticalSeam(), and transpose it back

  public void removeHorizontalSeam(int[] seam) {
    this.isInTranspose = true;

    if (seam == null || !isSeamValid(seam)) {
      this.isInTranspose = false;
      throw new IllegalArgumentException();
    }

    removeVerticalSeam(seam);
    transformPicture();
  }

其中transformPicture

  
  private void transformPicture() {
    int tw = this.height;
    int th = this.width;
    Picture newPicture = new Picture(tw, th);
    for (int y = 0; y < th; y++) {
      for (int x = 0; x < tw; x++) {
        Color color = this.picture.get(y, x);
        newPicture.set(x, y, color);
      }
    }

    this.picture = newPicture;
    this.width = newPicture.width();
    this.height = newPicture.height();
    update();
    this.isInTranspose = false;
  }

总结

这个作业还是非常有意思的, 算法核心就是找最短路径, 然后比较麻烦的事图片的各种变换顺序, 需要维护一些变量