gocv. connected structures size algo

structures.go

package app

import (
	"gocv.io/x/gocv"
	"image"
	"sort"
)

type RefMat struct {
	cols    int
	rows    int
	mat     [][]*uint8
	counter uint8
	Refs    map[uint8]*uint8
}

func NewRefMat(r int, c int) *RefMat {
	zero := uint8(0)

	matrix := make([][]*uint8, r)
	rows := make([]*uint8, r*c)
	for i := 0; i < r; i++ {
		matrix[i] = rows[i*c : (i+1)*c]
	}

	refs := make(map[uint8]*uint8)
	refs[0] = &zero

	return &RefMat{
		mat:     matrix,
		rows:    r,
		cols:    c,
		counter: 0,
		Refs:    refs,
	}
}

func (m *RefMat) Zero() *uint8 {
	return m.Refs[0]
}

func (m *RefMat) Rows() int {
	return m.rows
}

func (m *RefMat) Cols() int {
	return m.cols
}

func (m *RefMat) Incr() *uint8 {
	m.counter++

	v := m.counter
	m.Refs[v] = &v

	return m.Refs[v]
}

func (m *RefMat) Set(r int, c int, v *uint8) {
	m.mat[r][c] = v
}

func (m *RefMat) Get(r int, c int) *uint8 {
	return m.mat[r][c]
}

type Structure struct {
	connected map[uint8]bool
	Size      int
	Area      image.Rectangle
}

func ConnectedStructures(mat gocv.Mat) []int {

	ss := make(map[uint8]*Structure)

	rows := mat.Rows()
	cols := mat.Cols()
	imgb := mat.ToBytes()
	img := make([][]byte, rows)
	for i := 0; i < rows; i++ {
		img[i] = imgb[i*cols : (i+1)*cols]
	}

	cimg := NewRefMat(rows, cols)
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			v := img[r][c]
			if v == 0 {
				cimg.Set(r, c, cimg.Zero())

				continue
			}

			// in the middle
			if c != 0 && r != 0 {
				pv := cimg.Get(r, c - 1)
				if *pv != 0 {
					ss[*pv].Size += 1

					cimg.Set(r, c, pv)

					// connect
					rpv := cimg.Get(r - 1, c)
					if *rpv != 0 && *rpv != *pv {
						for ri := range cimg.Refs {
							if ri == *pv {
								continue
							}

							if *rpv == *cimg.Refs[ri] {
								ss[*pv].Size += ss[ri].Size

								// delete ???
								ss[ri].Size = 0

								*cimg.Refs[ri] = *pv
							}
						}
					}
				} else {
					pv := cimg.Get(r - 1, c)
					if *pv != 0 {
						ss[*pv].Size += 1

						cimg.Set(r, c, pv)

					} else {
						v := cimg.Incr()

						ss[*v] = &Structure{Size: 1}
						//ss[*v].Area = image.Rect(c, r, c, r)
						cimg.Set(r, c, v)
					}
				}

				continue
			}

			// first row
			if c != 0 && r == 0 {
				pv := cimg.Get(r, c - 1)
				if *pv != 0 {
					ss[*pv].Size += 1

					cimg.Set(r, c, pv)
				} else {
					v := cimg.Incr()
					ss[*v] = &Structure{Size: 1}
					//ss[cntr].Area = image.Rect(c, r, c, r)
					cimg.Set(r, c, v)
				}

				continue
			}

			// first column
			if c == 0 && r != 0 {
				pv := cimg.Get(r - 1, c)
				if *pv != 0 {
					ss[*pv].Size += 1

					cimg.Set(r, c, pv)
				} else {
					v := cimg.Incr()
					cimg.Set(r, c, v)

					ss[*v] = &Structure{Size: 1}
				}

				continue
			}

			// corner
			if c == 0 && r == 0 {
				if v != 0 {
					v := cimg.Incr()
					cimg.Set(r, c, v)

					ss[*v] = &Structure{Size: 1}
				} else {
					cimg.Set(r, c, cimg.Zero())
				}

				continue
			}
		}
	}

	//log.Printf("\n")
	//for r := 0; r < cimg.Rows(); r++ {
	//	row := []uint8{}
	//	for c := 0; c < cimg.Cols(); c++ {
	//		row = append(row, *cimg.Get(r, c))
	//	}
	//
	//	log.Printf("%v\n", row)
	//}

	var areas []int
	for i := range ss {
		if ss[i].Size > 0 {
			areas = append(areas, ss[i].Size)
		}
	}

	sort.Sort(sort.Reverse(sort.IntSlice(areas)))

	return areas
}

structures_test.go

package app

import (
	"gocv.io/x/gocv"
	"testing"
)

func TestOneToOneZero(t *testing.T) {
	img, err := gocv.NewMatFromBytes(1, 1, gocv.MatTypeCV8U, []byte{0})
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 0 {
		t.Errorf("Expected 0 areas, got %d", len(areas))
	}
}

func TestOneToOneNotZero(t *testing.T) {
	img, err := gocv.NewMatFromBytes(1, 1, gocv.MatTypeCV8U, []byte{1})
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 1 {
		t.Errorf("Expected 1 area, got %d", len(areas))

		t.FailNow()
	}

	size := areas[0]
	if size != 1 {
		t.Errorf("Expected area size 1, got %d", size)

		t.FailNow()
	}
}

func TestOneToFive(t *testing.T) {
	b := []byte{
		1, 0, 1, 1, 1,
	}

	img, err := gocv.NewMatFromBytes(1, 5, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)
	if len(areas) != 2 {
		t.Errorf("Expected 2 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 3 {
		t.Errorf("Expected area size 3, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 1 {
		t.Errorf("Expected area size 1, got %d", s2)

		t.FailNow()
	}
}

func TestFiveToOne(t *testing.T) {
	b := []byte{
		1, 0, 1, 1, 1,
	}

	img, err := gocv.NewMatFromBytes(5, 1, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)
	if len(areas) != 2 {
		t.Errorf("Expected 2 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 3 {
		t.Errorf("Expected area size 3, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 1 {
		t.Errorf("Expected area size 1, got %d", s2)

		t.FailNow()
	}
}

func TestTwoToTwoV1(t *testing.T) {
	b := []byte{1, 0, 0, 1}

	img, err := gocv.NewMatFromBytes(2, 2, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 2 {
		t.Errorf("Expected 2 structures, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 1 {
		t.Errorf("Expected area size 1, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 1 {
		t.Errorf("Expected area size 2, got %d", s2)

		t.FailNow()
	}
}


func TestTwoToTwoV2(t *testing.T) {
	b := []byte{0, 1, 1, 0}

	img, err := gocv.NewMatFromBytes(2, 2, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 2 {
		t.Errorf("Expected 2 structures, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 1 {
		t.Errorf("Expected area size 1, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 1 {
		t.Errorf("Expected area size 2, got %d", s2)

		t.FailNow()
	}
}

func TestTwoToTwoV3(t *testing.T) {
	b := []byte{1, 1, 0, 0}

	img, err := gocv.NewMatFromBytes(2, 2, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 1 {
		t.Errorf("Expected 2 structures, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 2 {
		t.Errorf("Expected area size 1, got %d", s1)

		t.FailNow()
	}
}

func TestTwoToTwoV4(t *testing.T) {
	b := []byte{1, 0, 1, 0}

	img, err := gocv.NewMatFromBytes(2, 2, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 1 {
		t.Errorf("Expected 2 structures, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 2 {
		t.Errorf("Expected area size 1, got %d", s1)

		t.FailNow()
	}
}

func TestTwoToTwoV5(t *testing.T) {
	b := []byte{0, 1, 0, 1}

	img, err := gocv.NewMatFromBytes(2, 2, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 1 {
		t.Errorf("Expected 2 structures, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 2 {
		t.Errorf("Expected area size 1, got %d", s1)

		t.FailNow()
	}
}

func TestThreeToThreeV2(t *testing.T) {
	b := []byte{0, 1, 0, 1, 0, 0, 1, 1, 1}

	img, err := gocv.NewMatFromBytes(3, 3, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 2 {
		t.Errorf("Expected 2 structures, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 4 {
		t.Errorf("Expected area size 4, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 1 {
		t.Errorf("Expected area size 1, got %d", s2)

		t.FailNow()
	}
}

func TestThreeToThreeWithConnectionV1(t *testing.T) {
	b := []byte{1, 0, 1, 1, 1, 1, 0, 0, 0}

	img, err := gocv.NewMatFromBytes(3, 3, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 1 {
		t.Errorf("Expected 1 area, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 5 {
		t.Errorf("Expected area size 5, got %d", s1)

		t.FailNow()
	}
}

func TestThreeToThreeWithConnectionV2(t *testing.T) {
	b := []byte{
		1, 0, 0,
		1, 0, 0,
		1, 1, 1,
	}

	img, err := gocv.NewMatFromBytes(3, 3, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 1 {
		t.Errorf("Expected 1 area, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 5 {
		t.Errorf("Expected area size 5, got %d", s1)

		t.FailNow()
	}
}

func TestFourToFourWithConnectionV1(t *testing.T) {
	b := []byte{
		1, 0, 0, 1,
		1, 0, 0, 1,
		1, 0, 1, 1,
		1, 1, 1, 1,
	}

	img, err := gocv.NewMatFromBytes(4, 4, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)

	if len(areas) != 1 {
		t.Errorf("Expected 1 area, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 11 {
		t.Errorf("Expected area size 11, got %d", s1)

		t.FailNow()
	}
}

func TestFiveToFiveWithConnectionV1(t *testing.T) {
	b := []byte{
		1, 0, 1, 0, 0,
		0, 1, 1, 0, 0,
		1, 1, 1, 0, 0,
		0, 0, 0, 1, 1,
		0, 0, 0, 1, 1,
	}

	img, err := gocv.NewMatFromBytes(5, 5, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)
	if len(areas) != 3 {
		t.Errorf("Expected 3 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 6 {
		t.Errorf("Expected area size 6, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 4 {
		t.Errorf("Expected area size 4, got %d", s2)

		t.FailNow()
	}

	s3 := areas[2]
	if s3 != 1 {
		t.Errorf("Expected area size 1, got %d", s3)

		t.FailNow()
	}
}

func TestFiveToFiveWithConnectionV2(t *testing.T) {
	b := []byte{
		0, 0, 1, 0, 0,
		0, 1, 1, 0, 1,
		1, 1, 0, 1, 1,
		1, 0, 1, 1, 0,
		0, 1, 1, 0, 0,
	}

	img, err := gocv.NewMatFromBytes(5, 5, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)
	if len(areas) != 2 {
		t.Errorf("Expected 2 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 7 {
		t.Errorf("Expected area size 7, got %d", s1)

		t.FailNow()
	}


	s2 := areas[1]
	if s2 != 6 {
		t.Errorf("Expected area size 6, got %d", s2)

		t.FailNow()
	}
}

func TestFiveToFiveWithConnectionV3(t *testing.T) {
	b := []byte{
		1, 0, 1, 1, 1,
		1, 0, 0, 0, 1,
		1, 0, 0, 0, 1,
		1, 0, 0, 0, 1,
		1, 1, 1, 1, 1,
	}

	img, err := gocv.NewMatFromBytes(5, 5, gocv.MatTypeCV8UC1, b)
	if err != nil {
		t.Errorf(err.Error())

		t.FailNow()
	}
	defer img.Close()

	areas := ConnectedStructures(img)
	if len(areas) != 1 {
		t.Errorf("Expected 1 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 15 {
		t.Errorf("Expected area size 15, got %d", s1)

		t.FailNow()
	}
}

func TestRealImgOne(t *testing.T) {
	img := gocv.IMRead("./../fixtures/1.jpg", gocv.IMReadGrayScale)
	defer img.Close()

	gocv.Threshold(img, &img, 127, 255, gocv.ThresholdBinary)

	areas := ConnectedStructures(img)
	if len(areas) < 4 {
		t.Errorf("Expected more than 4 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 < 5000 {
		t.Errorf("Expected area size more 5000, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 > 200 {
		t.Errorf("Expected area size less 200, got %d", s2)

		t.FailNow()
	}
}

func TestRealImgTwo(t *testing.T) {
	img := gocv.IMRead("./../fixtures/2.jpg", gocv.IMReadGrayScale)
	defer img.Close()

	gocv.Threshold(img, &img, 127, 255, gocv.ThresholdBinary)

	areas := ConnectedStructures(img)
	if len(areas) != 5 {
		t.Errorf("Expected 5 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 198 {
		t.Errorf("Expected area size 198, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 110 {
		t.Errorf("Expected area 110, got %d", s2)

		t.FailNow()
	}
}

func TestRealImgThree(t *testing.T) {
	img := gocv.IMRead("./../fixtures/3.jpg", gocv.IMReadGrayScale)
	defer img.Close()

	gocv.Threshold(img, &img, 127, 255, gocv.ThresholdBinary)

	areas := ConnectedStructures(img)
	if len(areas) < 4 {
		t.Errorf("Expected more than 4 areas, got %d", len(areas))

		t.FailNow()

	}

	s1 := areas[0]
	if s1 != 6458 {
		t.Errorf("Expected area size 6458, got %d", s1)

		t.FailNow()
	}

	s2 := areas[1]
	if s2 != 12 {
		t.Errorf("Expected area 12, got %d", s2)

		t.FailNow()
	}
}