[Week 2]Princeton Algorithm PartII SeamCarving

回顧

第二周主要內(nèi)容仍然是關(guān)于圖的算法，主要內(nèi)容為：

編程作業(yè)是SeamCarver：原題地址

題目

SeamCarving是一種調(diào)整圖像尺寸的算法：從一幅圖像中選出最不重要的像素并刪去，在盡可能保留圖像內(nèi)容的情況下改變圖像的尺寸。

original image
resized image

上圖就是SeamCarving算法的應(yīng)用，原圖尺寸為505-by-287，變換后的圖片尺寸為355-by-287。雖然尺寸變了，但是沒(méi)有發(fā)生拉伸扭曲，保留了原圖的特征。

算法步驟：

  1. 計(jì)算每個(gè)像素點(diǎn)的權(quán)重
  2. 找到水平（垂直）方向上的權(quán)重最小的像素序列，稱(chēng)為seam
  3. 移除seam
vertical seam

備注：

  • 像素點(diǎn)的權(quán)重計(jì)算使用dual-gradient energy function,具體計(jì)算方法在原題中有。
  • 從像素點(diǎn)(i,j)出發(fā)(假設(shè)垂直方向)只能連接到下一行的相鄰三個(gè)像素(i-1,j+1),(i,j+1),(i+1,j+1)
  • 坐標(biāo)系與默認(rèn)的不同：(i,j)表示第j行，第i列
a 3-by-4 image
  (0, 0)      (1, 0)      (2, 0)  
  (0, 1)      (1, 1)      (2, 1)  
  (0, 2)      (1, 2)      (2, 2)  
  (0, 3)      (1, 3)      (2, 3)

API:

public class SeamCarver {
   public SeamCarver(Picture picture)                // create a seam carver object based on the given picture
   public Picture picture()                          // current picture
   public     int width()                            // width of current picture
   public     int height()                           // height of current picture
   public  double energy(int x, int y)               // energy of pixel at column x and row y
   public   int[] findHorizontalSeam()               // sequence of indices for horizontal seam
   public   int[] findVerticalSeam()                 // sequence of indices for vertical seam
   public    void removeHorizontalSeam(int[] seam)   // remove horizontal seam from current picture
   public    void removeVerticalSeam(int[] seam)     // remove vertical seam from current picture
}

解析

  • 圖像的表示使用alg4.jar中的Picture類(lèi)。但是構(gòu)造這個(gè)類(lèi)的開(kāi)銷(xiāo)很大，在內(nèi)部用一個(gè)二維數(shù)組作為類(lèi)成員變量來(lái)表示圖像中每個(gè)點(diǎn)，數(shù)組中存的值為此像素點(diǎn)int類(lèi)型的rbg值。在實(shí)現(xiàn)算法的時(shí)候使用此二維數(shù)組，只在public Picture picture()方法中生成Picture對(duì)象并返回。

  • 核心算法是找到某一方向上的seam，下面一步步思考：

    1. 首先可以把圖像抽象成一個(gè)有向圖，頂點(diǎn)是每一個(gè)像素點(diǎn)，每個(gè)頂點(diǎn)有三條邊指向下一行（列）的相鄰頂點(diǎn)。
    2. seam即是一條最短路徑，權(quán)值就是最短路徑上所有像素點(diǎn)的權(quán)重。
    3. 這是一個(gè)無(wú)環(huán)有向圖（DAG），從時(shí)間復(fù)雜度考慮應(yīng)該使用無(wú)環(huán)有向圖的最短路徑算法，而不是Dijkstra算法。
    4. 因此需要得到拓?fù)漤樞颍谶@里不需要使用深度優(yōu)先搜索來(lái)計(jì)算。以垂直方向?yàn)槔?，自上而下，每一行的拓?fù)漤樞蛳扔谙乱恍?，而每一行中各個(gè)頂點(diǎn)的順序無(wú)關(guān)緊要。
    5. 因此在最短路徑算法中，可以直接for循環(huán)自上而下遍歷所有頂點(diǎn)，進(jìn)行松弛（relax）操作。

  • 水平和垂直方向：兩個(gè)不同方向的算法實(shí)質(zhì)是一樣的，只要先對(duì)表示圖像的二維數(shù)組進(jìn)行轉(zhuǎn)置，就能夠復(fù)用代碼。
    java中二維數(shù)組實(shí)際是由一維數(shù)組的每個(gè)元素表示其他各個(gè)一維數(shù)組，根據(jù)題意，垂直方向的像素作為第二層數(shù)組，方便用System.arraycopy()來(lái)整體移動(dòng)，因此我們實(shí)現(xiàn)removeHorizontalSeam(int[] seam)方法：即水平方向上每行移除一個(gè)像素點(diǎn)，再整體移動(dòng)剩余像素點(diǎn)；而對(duì)于removeVerticalSeam(int[] seam)方法，只要轉(zhuǎn)置二維數(shù)組、調(diào)用removeHorizontalSeam(int[] seam)、再轉(zhuǎn)置二維數(shù)組。

代碼

成員變量：

private int[][] colors;

構(gòu)造方法：

public Picture picture() {
        Picture picture = new Picture(colors.length, colors[0].length);
        for (int i = 0; i < colors.length; i++) {
            for (int j = 0; j < colors[0].length; j++) {
                Color color = new Color(this.colors[i][j]);
                picture.set(i, j, color);
            }
        }
        return picture;
    }

width()和height()：

public int width() {
    return this.colors.length;
}

public int height() {
    return this.colors[0].length;
}

energy()：使用dual-gradient energy function來(lái)計(jì)算

public double energy(int x, int y) {
        if (x < 0 || x > this.width() - 1 || y < 0 || y > this.height() - 1) {
            throw new IndexOutOfBoundsException();
        }
        if (x == 0 || x == this.width() - 1 || y == 0 || y == this.height() - 1) {
            return 1000.0;
        } else {
            int deltaXRed = red(colors[x - 1][y]) -
                    red(colors[x + 1][y]);
            int deltaXGreen = green(colors[x - 1][y]) -
                    green(colors[x + 1][y]);
            int deltaXBlue = blue(colors[x - 1][y]) -
                    blue(colors[x + 1][y]);

            int deltaYRed = red(colors[x][y - 1]) - red(colors[x][y + 1]);
            int deltaYGreen = green(colors[x][y - 1]) - green(colors[x][y + 1]);
            int deltaYBlue = blue(colors[x][y - 1]) - blue(colors[x][y + 1]);

            return Math.sqrt(Math.pow(deltaXRed, 2) + Math.pow(deltaXBlue, 2) + Math.pow(deltaXGreen, 2) + Math.pow(deltaYRed, 2) + Math.pow(deltaYBlue, 2) + Math.pow(deltaYGreen, 2));
        }

    }

findVerticalSeam()

  1. 先計(jì)算所有頂點(diǎn)的distTo值，即從第一行到此頂點(diǎn)的最短路徑上所有頂點(diǎn)權(quán)值之和
  2. 找出最后一行中distTo值最小的頂點(diǎn)，此頂點(diǎn)屬于seam
  3. 根據(jù)nodeTo，逐行逆向找到每個(gè)屬于seam的頂點(diǎn)
public int[] findVerticalSeam() {
        int n = this.width() * this.height();
        int[] seam = new int[this.height()];
        int[] nodeTo = new int[n];
        double[] distTo = new double[n];
        for (int i = 0; i < n; i++) {
            if (i < width())
                distTo[i] = 0;
            else
                distTo[i] = Double.POSITIVE_INFINITY;
        }
        for (int i = 0; i < height(); i++) {
            for (int j = 0; j < width(); j++) {
                for (int k = -1; k <= 1; k++) {
                    if (j + k < 0 || j + k > this.width() - 1 || i + 1 < 0 || i + 1 > this.height() - 1) {
                        continue;
                    } else {
                        if (distTo[index(j + k, i + 1)] > distTo[index(j, i)] + energy(j, i)) {
                            distTo[index(j + k, i + 1)] = distTo[index(j, i)] + energy(j, i);
                            nodeTo[index(j + k, i + 1)] = index(j, i);
                        }
                    }
                }
            }
        }

        // find min dist in the last row
        double min = Double.POSITIVE_INFINITY;
        int index = -1;
        for (int j = 0; j < width(); j++) {
            if (distTo[j + width() * (height() - 1)] < min) {
                index = j + width() * (height() - 1);
                min = distTo[j + width() * (height() - 1)];
            }
        }

        // find seam one by one
        for (int j = 0; j < height(); j++) {
            int y = height() - j - 1;
            int x = index - y * width();
            seam[height() - 1 - j] = x;
            index = nodeTo[index];
        }

        return seam;
    }
    
    private int index(int x, int y) {
        return width() * y + x;
    }

findHorizontalSeam()

public int[] findHorizontalSeam() {
        this.colors = transpose(this.colors);
        int[] seam = findVerticalSeam();
        this.colors = transpose(this.colors);
        return seam;
    }

removeHorizontalSeam

public void removeHorizontalSeam(int[] seam) {
        if (height() <= 1) throw new IllegalArgumentException();
        if (seam == null) throw new NullPointerException();
        if (seam.length != width()) throw new IllegalArgumentException();

        for (int i = 0; i < seam.length; i++) {
            if (seam[i] < 0 || seam[i] > height() - 1)
                throw new IllegalArgumentException();
            if (i < width() - 1 && Math.pow(seam[i] - seam[i + 1], 2) > 1)
                throw new IllegalArgumentException();
        }

        int[][] updatedColor = new int[width()][height() - 1];
        for (int i = 0; i < seam.length; i++) {
            if (seam[i] == 0) {
                System.arraycopy(this.colors[i], seam[i] + 1, updatedColor[i], 0, height() - 1);
            } else if (seam[i] == height() - 1) {
                System.arraycopy(this.colors[i], 0, updatedColor[i], 0, height() - 1);
            } else {
                System.arraycopy(this.colors[i], 0, updatedColor[i], 0, seam[i]);
                System.arraycopy(this.colors[i], seam[i] + 1, updatedColor[i], seam[i], height() - seam[i] - 1);
            }

        }
        this.colors = updatedColor;
    }

removeVerticalSeam:轉(zhuǎn)置后復(fù)用removeHorizontalSeam(int[] seam)

public void removeVerticalSeam(int[] seam) {
        this.colors = transpose(this.colors);
        removeHorizontalSeam(seam);
        this.colors = transpose(this.colors);
    }

最后是轉(zhuǎn)置方法：

private int[][] transpose(int[][] origin) {
        if (origin == null) throw new NullPointerException();
        if (origin.length < 1) throw new IllegalArgumentException();
        int[][] result = new int[origin[0].length][origin.length];
        for (int i = 0; i < origin[0].length; i++) {
            for (int j = 0; j < origin.length; j++) {
                result[i][j] = origin[j][i];
            }
        }
        return result;
    }

成績(jī)

ASSESSMENT SUMMARY

Compilation:  PASSED
API:          PASSED

Findbugs:     PASSED
Checkstyle:   FAILED (3 warnings)

Correctness:  31/31 tests passed
Memory:       7/7 tests passed
Timing:       6/6 tests passed

Aggregate score: 100.00%
[Compilation: 5%, API: 5%, Findbugs: 0%, Checkstyle: 0%, Correctness: 60%, Memory: 10%, Timing: 20%]

完整代碼和測(cè)試用例在GitHub上，歡迎討論
https://github.com/michael0905/SeamCarver

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀(guān)點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 第一章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)？ 數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 第二章...
    SeanCheney閱讀 5,986評(píng)論 0贊 19
  • 不同圖像灰度不同，邊界處一般會(huì)有明顯的邊緣，利用此特征可以分割圖像。需要說(shuō)明的是：邊緣和物體間的邊界并不等同，邊緣...
    大川無(wú)敵閱讀 14,114評(píng)論 0贊 29
  • https://zh.visualgo.net/graphds 淺談圖形結(jié)構(gòu)https://zh.visualgo...
    狼之獨(dú)步閱讀 4,412評(píng)論 0贊 0
  • 自由書(shū)寫(xiě)第十七篇 人生最大的痛苦是你抗拒無(wú)常，生老病死，乃人之常情 忘了讀那一本書(shū)上說(shuō)的，研究癌癥病人有一個(gè)共同的...
    Wendy3閱讀 256評(píng)論 0贊 0
  • 由于歷史的原因，我們的國(guó)家貧困落后，而且被西方社會(huì)孤立了，我們不懂葡萄酒，不是因?yàn)槲覀冇廾翢o(wú)知，而是因?yàn)槲覀儧](méi)有機(jī)...
    武破九荒閱讀 860評(píng)論 3贊 1

友情鏈接更多精彩內(nèi)容