在Go中计算形状边框上像素的排序顺序

p1iqtdky  于 2022-12-07  发布在  Go
关注(0)|答案(1)|浏览(111)

我制作了一个小程序，它读取一个PNG文件，并找到图像中任何像素的坐标，这些像素是所描绘形状的 border 的一部分（下面的代码）。
我们在这里定义 “边界的像素部分” 为 “在顶部、底部或其一侧上直接具有白色像素的每个彩色像素”。
这个简单的算法找到一个形状的边界，并忽略任何空（白色）像素和任何非空（彩色）像素构成的形状 * 填充 *。
我得到的是一个Point的切片，上面有所有像素的坐标，打印在屏幕上，但它们自然是由找到它们的扫描过程排序的，从上到下，从左到右。
我想要实现的是边界的点被排序，就好像它们在形状周围画了一条连续的线，从遇到的第一个边界像素开始，并在形状周围按顺时针顺序前进。
因此，对于这样一个正方形（抱歉，这是一个非常小的图像）：

在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片从未达到空状态，因此执行将永远继续...
我怎样才能使它工作呢？还有，怎样才能在代码中使它更清楚呢？

go

1条答案

按热度按时间
y1aodyip

y1aodyip1#

我有同样的问题，因为你的。我有一点在互联网上搜索，并没有找到足够的合适的东西，所以我想解释我自己的解决方案，所有的选项，你想要他们都包括在这里，但请注意，起点是不是在我们的控制以这种方式。
首先开始使用开源计算机视觉库它提供了一个名为“cv2.findContours”的python命令（1，2，3）”这是在我最近的作品中使用了这么多，我会解释关于num选项，把在“cv2.findContours”命令。第二件事，必须注意的是，这个命令给你的像素点坐标的边界上的对象，所以我们找到了他们。
选项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]是第一个轮廓的所有边界点的列表“逆时针方向”。因为在这种情况下，我们只有一个轮廓，只是使用“轮廓[0][：：-1]”来反转它。现在所有像素点按其坐标排序“顺时针方向”，但请记住，我们没有选择自己的起点。要将它们视为列表，请使用命令：

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

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

赞(0）分享  回复(0）举报  2022-12-07
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com