如何找到矩形的角點像素？

給定一個簡單的單色位圖，其中包含一個隨機旋轉的矩形。如何在位圖內找到矩形的左/上，左/右，右/下和右/上角位置？如何找到矩形的角點像素？

例如，這是位圖可看怎麼樣，這裏的X標記所涉及的像素：

......... ......... ......... ......... 
.X11111X. ....X.... ..X11.... ....11X.. 
.1111111. ...111... ..11111X. X111111.. 
.1111111. ..X111X.. ..111111. .111111.. 
.X11111X. ...111... .1111111. .1111111. 
......... ....X.... .111111.. ..111111. 
......... ......... .X11111.. ..11111X. 
......... ......... ....11X.. ..X11.... 
......... ......... ......... .........

請原諒壞的ASCII藝術。對於第二個示例，頂部的角落像素可以是左/頂部或右上角的矩形。兩者都很好。

上述例子中需要哪些步驟來確定角點像素/位置？

來源

2015-12-17 SePröbläm

當形狀不對稱或傾斜時，沒有確切的解決方案。你想要一個確切的矩形或者你會接受一個四邊形？ –

我正試圖在圖像中找到一個四邊形。 –

然後你應該重新發帖。 –

角落像素是最遠的像素。找到最上面一行和最下面一行。這些中總會有一個角落像素。

轉角像素只能是這個最上面的行行中的第一個或最後一個像素（或者兩者都存在，如果只有一個）。

因此，比較最頂行第一個像素和最底行最後一個像素之間的距離。最後一個像素位於最下方，最下方的像素位於最下方。那裏的角落是那些距離最遠的角落。

由於它們在Y中的距離都是相同的，所以需要像素的x位置差異最大。拐角是abs（x0-x1）最大的像素，其中x0位於最上面一行，x1位於最下面。

對最右邊和最左邊的行重複此操作。

如果最上角位於左側，則最左側角位於底部，最下角位於右側，最右側角位於頂部。一旦你有了頂部，底部，左邊和右邊的行，真正的兩個可能性就可以在if語句中解決。但是，由於最上面的一行上有一個像素，最右面兩行上有一個像素的邊緣條件，您最好再次使用顛倒的x和y來運行算法，以解決其他兩個角落問題，而不是試圖讓自己一個if語句。

來源

2015-12-17 13:14:19 Tatarize

查找頂部，底部，右側和左側行可以在log（n）時間完成。但是，我不會推薦它。這個問題並不是你需要玩Battleship™的東西。你來我的長方形！ – Tatarize

「查找頂部，底部，左側和右側的行可以在log（n）時間完成」：怎麼樣？ –

發揮戰艦尋找矩形blob。然後執行二進制搜索來查找邊緣。形狀的右側，左側或上方必須有一個黑色像素，直到它位於最上面一行。 – Tatarize

從矩形的邊界框開始。

對於每個角落，順時針移動它直到出現黑色方塊。

public class Test { 

    String[][] squares = { 
     { 
      ".........", 
      ".X11111X.", 
      ".1111111.", 
      ".1111111.", 
      ".X11111X.", 
      ".........", 
      ".........", 
      ".........", 
      ".........",}, 
     { 
      ".........", 
      "....X....", 
      "...111...", 
      "..X111X..", 
      "...111...", 
      "....X....", 
      ".........", 
      ".........", 
      ".........",}, 
     { 
      ".........", 
      "..X11....", 
      "..11111X.", 
      "..111111.", 
      ".1111111.", 
      ".111111..", 
      ".X11111..", 
      "....11X..", 
      ".........",}, 
     { 
      ".........", 
      "....11X..", 
      "X111111..", 
      ".111111..", 
      ".1111111.", 
      "..111111.", 
      "..11111X.", 
      "..X11....", 
      ".........",}}; 

    private static final int WHITE = 0; 
    private static final int BLACK = 1; 

    class Point { 

     private final int x; 
     private final int y; 

     public Point(Point p) { 
      this.x = p.x; 
      this.y = p.y; 
     } 

     public Point(int x, int y) { 
      this.x = x; 
      this.y = y; 
     } 

     @Override 
     public String toString() { 
      return "{" + x + "," + y + '}'; 
     } 

     // What colour is there? 
     public int colour(int[][] bmp) { 
      // Make everything off-bmp black. 
      if (x < 0 || y < 0 || y >= bmp.length || x >= bmp[y].length) { 
       return BLACK; 
      } 
      return bmp[y][x]; 
     } 

     private Point step(Point d) { 
      return new Point(x + d.x, y + d.y); 
     } 

    } 

    class Rectangle { 

     private final Point[] corners = new Point[4]; 

     public Rectangle(Point[] corners) { 
      // Points are immutable but corners are not. 
      System.arraycopy(corners, 0, this.corners, 0, corners.length); 
     } 

     public Rectangle(Rectangle r) { 
      this(r.corners()); 
     } 

     public Rectangle(Point a, Point b, Point c, Point d) { 
      corners[0] = a; 
      corners[1] = b; 
      corners[2] = c; 
      corners[3] = d; 
     } 

     private Rectangle(Point tl, Point br) { 
      this(tl, new Point(br.x, tl.y), br, new Point(tl.x, br.y)); 
     } 

     public Point[] corners() { 
      return Arrays.copyOf(corners, corners.length); 
     } 

     @Override 
     public String toString() { 
      return Arrays.toString(corners); 
     } 

    } 

    private Rectangle getBoundingBox(int[][] bmp) { 
     int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE, maxX = 0, maxY = 0; 
     for (int r = 0; r < bmp.length; r++) { 
      for (int c = 0; c < bmp[r].length; c++) { 
       if (bmp[r][c] != WHITE) { 
        if (minX > c) { 
         minX = c; 
        } 
        if (minY > r) { 
         minY = r; 
        } 
        if (maxX < c) { 
         maxX = c; 
        } 
        if (maxY < r) { 
         maxY = r; 
        } 
       } 
      } 
     } 
     return new Rectangle(new Point(minX, minY), new Point(maxX, maxY)); 
    } 

    Point[] clockwise = new Point[]{ 
     new Point(1, 0), 
     new Point(0, 1), 
     new Point(-1, 0), 
     new Point(0, -1)}; 

    private void test(int[][] bmp) { 
     // Find the bounding box. 
     Rectangle bBox = getBoundingBox(bmp); 
     System.out.println("bbox = " + bBox); 
     Point[] corners = bBox.corners(); 
     // Move each corner clockwise until it is black. 
     for (int p = 0; p < corners.length; p++) { 
      while (corners[p].colour(bmp) == WHITE) { 
       corners[p] = corners[p].step(clockwise[p]); 
      } 
     } 
     System.out.println("rect = " + new Rectangle(corners)); 
    } 

    private void test(String[] square) { 
     // Build the int[][]. 
     // . -> White 
     // X/1 -> Black 
     int[][] bmp = new int[square.length][]; 
     for (int r = 0; r < square.length; r++) { 
      bmp[r] = new int[square[r].length()]; 
      for (int c = 0; c < bmp[r].length; c++) { 
       switch (square[r].charAt(c)) { 
        case '.': 
         bmp[r][c] = WHITE; 
         break; 
        case 'X': 
        case '1': 
         bmp[r][c] = BLACK; 
         break; 
       } 
      } 
     } 
     test(bmp); 
    } 

    public void test() { 
     for (String[] square : squares) { 
      test(square); 
     } 
    } 

    public static void main(String args[]) { 
     try { 
      new Test().test(); 
     } catch (Throwable t) { 
      t.printStackTrace(System.err); 
     } 
    } 

}

打印

bbox = [{1,1}, {7,1}, {7,4}, {1,4}] 
    rect = [{1,1}, {7,1}, {7,4}, {1,4}] 
    bbox = [{2,1}, {6,1}, {6,5}, {2,5}] 
    rect = [{4,1}, {6,3}, {4,5}, {2,3}] 
    bbox = [{1,1}, {7,1}, {7,7}, {1,7}] 
    rect = [{2,1}, {7,2}, {6,7}, {1,6}] 
    bbox = [{0,1}, {7,1}, {7,7}, {0,7}] 
    rect = [{4,1}, {7,4}, {4,7}, {0,2}]

可以通過尋找黑色的運行，並選擇運行的中間得到改善。

來源

2015-12-17 15:03:29 OldCurmudgeon

從頂部逐行掃描圖像，直到找到黑色運行。

重複四種方式，從下往上，左，右，給你八個角落的候選人。

使運行終點在最上面和最下面的行中距離最遠。這告訴你垂直採取哪些端點。

來源

2015-12-18 17:17:26

一旦您發現黑色像素從頂部開始運行，如果您發現一行像素沒有低於該標記的黑色像素，則必須是最底部行在該行之上的情況。至少，我們最好是從頂端開始，直到我們連續擊球，然後繼續下去，直到我們擊出純白色的一排。然後我們有最後一行。假設矩形不超過位圖的一半。 – Tatarize

正確地，你應該循環瀏覽頂部的位圖，直到你點擊第一個黑色像素爲止，直到你點擊一行所有白色像素，然後將它們與最右邊，最左邊，最頂端最底部在一系列快速的if語句中。 o（n * m/2） – Tatarize

@Tatarize：我的解法是O（N-M）其中N是圖像的面積，M是矩形邊界框的面積。 –

不是每個單色位圖都會給你一個答案。一個完整的算法需要輸出「獨特的角落不存在」。下面的附圖給出的問題的一個例子：

......... ......... .......... ...XX.... ....X.... ....XX.... ..X11X... ...111... ...1111... ..X11X... ..X111X.. ..X1111X.. ...XX.... ...111... ..X1111X.. ......... ....X.... ...X11X... ......... ......... ....XX.... ......... ......... ..........

的簡併性所示，當矩形的斜率+1和-1和中心的位置是半整反應。它也可以與其他斜坡和位置的組合發生。一般的答案將需要包含像素對作爲頂點的最佳逼近。

來源

2015-12-21 15:42:37 eh9

如何找到矩形的角點像素？

回答

相關問題