ccl

README

Connected Component Labeling

Documentation

Overview

Package ccl provides implementations of Connected Component Labeling algorithms.

Example

package main

import (
	"fmt"
)

func main() {
	data := [][]int{
		{0, 1, 0, 0, 0, 0, 0, 1, 1},
		{1, 1, 1, 0, 1, 0, 0, 1, 0},
		{0, 1, 0, 0, 1, 0, 0, 1, 0},
		{0, 1, 1, 1, 1, 0, 0, 1, 0},
		{0, 0, 0, 1, 0, 0, 0, 1, 0},
		{0, 1, 0, 1, 1, 1, 1, 1, 0},
		{1, 1, 1, 0, 0, 0, 0, 0, 1},
		{1, 0, 1, 1, 1, 0, 0, 0, 1},
		{1, 1, 1, 0, 0, 0, 0, 1, 1},
		{1, 0, 1, 0, 1, 0, 1, 1, 1},
	}
	bmp := newBitmap(data)

	labelSizes := HoshenKopelman(bmp)

	for y := 0; y < len(bmp.labels); y++ {
		for x := 0; x < len(bmp.labels[y]); x++ {
			fmt.Printf(" % d", bmp.labels[y][x])
		}
		fmt.Printf("\n")
	}

	fmt.Println("label sizes:", labelSizes)

}

type bitmap struct {
	data   [][]int
	labels [][]int
	x, y   int
}

func newBitmap(data [][]int) *bitmap {
	bmp := &bitmap{}
	bmp.data = data

	bmp.labels = make([][]int, len(data))
	for y := 0; y < len(data); y++ {
		bmp.labels[y] = make([]int, len(data[y]))
		for x := range bmp.labels[y] {
			bmp.labels[y][x] = NullLabel
		}
	}

	return bmp
}

func (bmp *bitmap) Reset() {
	bmp.x, bmp.y = 0, 0
}

func (bmp *bitmap) Next() bool {
	if !bmp.next() {
		return false
	}
	for bmp.data[bmp.y][bmp.x] == 0 {
		if !bmp.next() {
			return false
		}
	}
	return true
}

func (bmp *bitmap) next() bool {
	bmp.x++
	if bmp.x >= len(bmp.data[bmp.y]) {
		bmp.y++
		bmp.x = 0
	}
	if bmp.y >= len(bmp.data) {
		return false
	}
	return true
}

func (bmp *bitmap) Neighbors() []int {
	x, y := bmp.x, bmp.y
	neighbors := make([]int, 0)
	if y > 0 && bmp.data[y-1][x] != 0 {
		neighbors = append(neighbors, bmp.labels[y-1][x])
	}
	if x > 0 && bmp.data[y][x-1] != 0 {
		neighbors = append(neighbors, bmp.labels[y][x-1])
	}
	return neighbors
}

func (bmp *bitmap) GetLabel() int {
	return bmp.labels[bmp.y][bmp.x]
}

func (bmp *bitmap) SetLabel(label int) {
	bmp.labels[bmp.y][bmp.x] = label
}

func (bmp *bitmap) Size() int {
	return 1
}

Output:

 -1  0 -1 -1 -1 -1 -1  0  0
  0  0  0 -1  0 -1 -1  0 -1
 -1  0 -1 -1  0 -1 -1  0 -1
 -1  0  0  0  0 -1 -1  0 -1
 -1 -1 -1  0 -1 -1 -1  0 -1
 -1  1 -1  0  0  0  0  0 -1
  1  1  1 -1 -1 -1 -1 -1  2
  1 -1  1  1  1 -1 -1 -1  2
  1  1  1 -1 -1 -1 -1  2  2
  1 -1  1 -1  3 -1  2  2  2
label sizes: [23 13 7 1]

Index

• Constants
• func BlobFromColor(r, g, b, a byte) int
• func ColorFromBlob(v int) color.NRGBA
• func HoshenKopelman(labeler CCLabeler) []int
• func Visualize(src *image.NRGBA)
• type Blob
  • func CCLImage(img *image.NRGBA) []Blob
  • func CollectBlobs(img *image.NRGBA) []Blob
• type CCLabeler

Examples

• Package

Constants

const (
	// EmptyBlob refers to points not belonging to an input image.
	EmptyBlob = -1
)

const (
	// NullLabel is the label that should be initially given to all nodes.
	NullLabel = -1
)

Functions

func BlobFromColor

func BlobFromColor(r, g, b, a byte) int

BlobFromColor returns a blob identifier from its color representation.

func ColorFromBlob

func ColorFromBlob(v int) color.NRGBA

ColorFromBlob returns the color representation of a blob.

func HoshenKopelman

func HoshenKopelman(labeler CCLabeler) []int

HoshenKopelman labels all nodes in the container using the Hoshen-Kopelman algorithm. It returns the sizes of all labels in descending order.

func Visualize

func Visualize(src *image.NRGBA)

Visualize visualizes the largest blobs in an image.

Types

type Blob

type Blob struct {
	// ID is the identifier of this blob
	ID int

	// Size is the size of this blob.
	Size int
}

Blob is a blob in connected components labeling

func CCLImage

func CCLImage(img *image.NRGBA) []Blob

CCLImage performs connected components labeling on an image.NRGBA. The image is modified in-place, and the blob each pixel belongs to can be inferred from BlobFromColor.

func CollectBlobs

func CollectBlobs(img *image.NRGBA) []Blob

CollectBlobs collects the blobs from an image returned by CCLImage.

type CCLabeler

type CCLabeler interface {
	// Reset resets the iterator of the container.
	Reset()

	// Next moves the iterator forward to the next node to be labeled.
	// If there are no more nodes available, Next returns false.
	Next() bool

	// Neighbors returns the labels of the neighbors of the current node.
	Neighbors() []int

	// GetLabel returns the label of the current node.
	GetLabel() int

	// SetLabel sets the label of the current node.
	SetLabel(int)

	// Size returns the size of the current node.
	// The sum of the sizes of all nodes sharing a same label is the size of that label.
	// Labels are assigned in descending order of their sizes.
	Size() int
}

A CCLabeler is a container of nodes that can be labeled.