使用 Go 在形状边界上对像素进行排序

一分耕耘，一分收获！既然打开了这篇文章《使用 Go 在形状边界上对像素进行排序》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

我编写了这个小程序，它读取 png 文件，并查找图像中属于所描绘形状的边框一部分的任何像素的坐标（代码如下）。

我们在这里定义“边框的像素部分”为“每个在顶部、底部或一侧有一个白色像素的彩色像素”.

这个简单的算法找到形状的边界，并忽略构成形状填充的任何空（白色）像素和任何非空（彩色）像素。

我得到的是 point 的切片，其中包含所有这些像素的坐标，打印在屏幕上，但它们是根据找到它们的扫描过程自然排序的，从上到下，从左到右。

我想要实现的是对边界点进行排序，就像它们围绕形状绘制一条连续线一样，从遇到的第一个边界像素开始，并围绕形状按顺时针顺序前进。

对于像这样的正方形（抱歉，图像很小）：

8x8 像素，在 10x10 像素的网格中，我得到这个坐标：

2,2
3,2
4,2
5,2
6,2
7,2
2,3
7,3
2,4
7,4
2,5
7,5
2,6
7,6
2,7
3,7
4,7
5,7
6,7
7,7

或者，以图形方式

但我真正想要的是这个（我已经手动排序了这些点）：

2,2
3,2
4,2
5,2
6,2
7,2
7,3
7,4
7,5
7,6
7,7
6,7
5,7
4,7
3,7
2,7
2,6
2,5
2,4
2,3

或者，对于这个小 h 形状

我明白了：

2,2
3,2
6,2
7,2
2,3
3,3
6,3
7,3
2,4
4,4
5,4
7,4
2,5
4,5
5,5
7,5
2,6
3,6
6,6
7,6
2,7
3,7
6,7
7,7

但我想要这个（也是手动排序的）：

2,2
3,2
3,3
4,4
5,4
6,3
6,2
7,2
7,3
7,4
7,5
7,6
7,7
6,7
6,6
5,5
4,5
3,6
3,7
2,7
2,6
2,5
2,4
2,3

我希望能够很好地说明我的情况。我试图自己思考解决方案，但我不知道如何解决这样的问题。如果您有直接的解决方案或想为我指出正确的方向，或者一些有关此类问题及其解决方案的阅读材料，我将非常感激。

抱歉我的英语不好。

这是我的代码：

package main

import (
    "fmt"
    "image"
    "image/png"
    "io"
    "os"
)

var (
    println = fmt.println
    printf  = fmt.printf
)

type pixel struct {
    r int
    g int
    b int
}

type point struct {
    x int
    y int
}

func main() {
    imagefilename := "square1.png"

    image.registerformat("png", "png", png.decode, png.decodeconfig)

    file, err := os.open(imagefilename)
    if err != nil {
        println("error: file could not be opened")
        os.exit(1)
    }
    defer file.close()

    pixels, err := getpixels(file)
    if err != nil {
        println("error: image could not be decoded")
        os.exit(1)
    }

    borders := findborders(pixels)

    // sorting the borders points in clockwise order starting from the first encountered point (but how?)
    // borders = sortborders(borders)

    // print borders points
    for _, point := range borders {
        printf("%d,%d\n", point.x, point.y)
    }
}

func findborders(pixels [][]pixel) []point {
    var borders []point
    for y := 0; y < len(pixels); y++ {
         for x := 0; x < len(pixels[y]); x++ {
              pixel := pixels[y][x]
              if !whitepixel(pixel) {
                  if whitepixel(pixels[y-1][x]) ||
                     whitepixel(pixels[y][x-1]) ||
                     whitepixel(pixels[y+1][x]) ||
                     whitepixel(pixels[y][x+1]) {
                         borders = append(borders, point{x, y})
                  }
              }
         }
    }
    return borders
}

// return true if a pixel is white
func whitepixel(pixel pixel) bool {
     return pixel.r == 255 && pixel.g == 255 && pixel.b == 255
}

// get the bi-dimensional pixel array
func getpixels(file io.reader) ([][]pixel, error) {
    img, _, err := image.decode(file)

    if err != nil {
        return nil, err
    }

    bounds := img.bounds()
    width, height := bounds.max.x, bounds.max.y

    var pixels [][]pixel
    for y := 0; y < height; y++ {
        var row []pixel
        for x := 0; x < width; x++ {
            row = append(row, rgbatopixel(img.at(x, y).rgba()))
        }
        pixels = append(pixels, row)
    }

    return pixels, nil
}

// img.at(x, y).rgba() returns four uint32 values, we need something a little more comfortable
func rgbatopixel(r uint32, g uint32, b uint32, a uint32) pixel {
    return pixel{int(r / 257), int(g / 257), int(b / 257)}
}

编辑

我几乎找到了解决方案。对于正方形示例，如果在角点 {7, 7} 和 {2, 7} 处失败，因为在我看来，当它在垂直或水平邻居之前找到对角邻居时，如果它在unsorted 切片此算法认为它足够好，并且跳过最接近的切片，而该切片仍然被忽略。请看一下：

func sortborders(unsorted []point) []point {
    original := make([]point, len(unsorted))
    copy(original, unsorted)
    expected := []point{{2, 2}, {3, 2}, {4, 2}, {5, 2}, {6, 2}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, {6, 7}, {5, 7}, {4, 7}, {3, 7}, {2, 7}, {2, 6}, {2, 5}, {2, 4}, {2, 3}}

    // finding the first one is easy
    sorted := []point{unsorted[0]}
    unsorted = unsorted[1:]

    stillunsorted := func() bool {
        return len(unsorted) > 0
    }

    lastsorted := func() point {
        return sorted[len(sorted)-1]
    }

    neighbor := func(s, u point) bool {
        if (s.x == u.x || s.x == u.x+1 || s.x == u.x-1) && (s.y == u.y || s.y == u.y+1 || s.y == u.y-1) {
            return true
        }
        return false
    }

    removefromunsorted := func(index int) {
        fresh := unsorted[:index]
        unsorted = append(fresh, unsorted[index+1:]...)
    }

    addtosorted := func(point point) {
        sorted = append(sorted, point)
    }

    for stillunsorted() {
        for i, point := range unsorted {
            if neighbor(lastsorted(), point) {
                removefromunsorted(i)
                addtosorted(point)

                println("---------")
                println("original:", original)
                println("unsorted:", unsorted)
                println("sorted  :", sorted)
                println("expected:", expected)
                break
            }
        }
    }

    return sorted
}

对于上面的方形示例，会产生以下输出：

original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {2 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {2 6} {2 7} {3 7} {4 7} {5 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {2 6} {2 7} {3 7} {4 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7} {5 7}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {2 6} {2 7} {3 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7} {5 7} {4 7}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {2 6} {2 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7} {5 7} {4 7} {3 7}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 5} {2 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7} {5 7} {4 7} {3 7} {2 6}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 4} {2 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7} {5 7} {4 7} {3 7} {2 6} {2 5}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 3} {2 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7} {5 7} {4 7} {3 7} {2 6} {2 5} {2 4}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
---------
original: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {2 3} {7 3} {2 4} {7 4} {2 5} {7 5} {2 6} {7 6} {2 7} {3 7} {4 7} {5 7} {6 7} {7 7}]
unsorted: [{2 7} {7 7}]
sorted  : [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {6 7} {5 7} {4 7} {3 7} {2 6} {2 5} {2 4} {2 3}]
expected: [{2 2} {3 2} {4 2} {5 2} {6 2} {7 2} {7 3} {7 4} {7 5} {7 6} {7 7} {6 7} {5 7} {4 7} {3 7} {2 7} {2 6} {2 5} {2 4} {2 3}]
^Csignal: interrupt

由于 unsorted 切片永远不会达到空状态，因此执行将永远继续...

我怎样才能做到这一点？另外，如何在代码中使其更清晰？

正确答案

我也有和你一样的问题。我在互联网上进行了一些搜索，发现没有足够合适的东西，所以我想解释一下我自己的解决方案，您想要的所有选项都包含在这里，但请注意，这样的起点不受我们控制。

首先开始使用开源计算机视觉库（称为 cv2），它有非常好的选项。它提供了一个名为“cv2.findcontours(1, 2, 3)”的python命令，它在我最近的作品中使用得很多，我将解释“cv2.findcontours”命令中的num个选项。第二件必须注意的事情是这个命令为您提供了对象边界上的像素点坐标，因此我们找到了它们。

选项 1 是您的图像，接下来是层次结构选项，当您处理沙子等多组件形状时使用，因此对于单个选项，我建议放置“cv2.retr_list”以消除额外的计算并避免复杂性。有关更多信息，我提到了下面的链接以了解我为什么使用它。

链接：https://docs.opencv.org/4.x/d9/d8b/tutorial_py_contours_hierarchy.html

第三个选项非常好，它大大减少了计算量，我喜欢它。你的问题的解释是你想要“所有”像素点坐标按顺时针顺序排列，而不是它们的“近似值”。因此，在第三位使用“cv2.chain_approx_none”选项。要知道为什么我在谈论“近似值”，请关注下面的链接。

链接：https://docs.opencv.org/3.4/d4/d73/tutorial_py_contours_begin.html

现在你肯定知道如何编写代码了。 python 代码类似于以下代码：

import cv2
contour, hierarchy = cv2.findcontours(input_image, cv2.retr_list, cv2.chain_approx_none)

鉴于我们仅处理一个对象，要顺时针排序或“排序”所有点，请使用以下命令：

contour[0][::-1]

轮廓[0]是第一个轮廓“逆时针”的所有边界点的列表。因为在这种情况下我们只有一个轮廓，只需使用“contour[0][::-1]”来反转它。现在所有像素点都按其坐标“顺时针”排序，但请记住，我们没有自己选择起点。要将它们视为列表，请使用命令：

for c in Contour[0]:
   print(c[0])

我们实现了边界点坐标的排序，就像它们围绕形状绘制一条连续的线一样，从遇到的第一个边界像素开始，并围绕形状按顺时针顺序前进。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于Golang的相关知识，也可关注golang学习网公众号。