labels

package
v0.8.14 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 20, 2017 License: BSD-3-Clause Imports: 10 Imported by: 0

Documentation

Overview

Package labels supports label-based data types like labelblk, labelvol, labelsurf, labelsz, etc. Basic 64-bit label data and deltas are kept here so all label-based data types can use them without cyclic package dependencies, especially when writing code to synchronize across data instances.

Index

Constants

View Source 
const (
	IngestBlockEvent    = imageblk.IngestBlockEvent
	MutateBlockEvent    = imageblk.MutateBlockEvent
	DeleteBlockEvent    = imageblk.DeleteBlockEvent
	SparsevolStartEvent = "SPARSEVOL_START"
	SparsevolModEvent   = "SPARSEVOL_MOD"
	SparsevolEndEvent   = "SPARSEVOL_END"
	ChangeSizeEvent     = "LABEL_SIZE_CHANGE"
	MergeStartEvent     = "MERGE_START"
	MergeBlockEvent     = "MERGE_BLOCK"
	MergeEndEvent       = "MERGE_END"
	SplitStartEvent     = "SPLIT_START"
	SplitLabelEvent     = "SPLIT_LABEL"
	SplitEndEvent       = "SPLIT_END"
)

Label change event identifiers

View Source 
const DefaultBlockSize = DefaultSubBlocksPerBlock * SubBlockSize
View Source 
const DefaultSubBlocksPerBlock = 8
View Source 
const (
	// MaxAllowedLabel is the largest label that should be allowed by DVID if we want
	// to take into account the maximum integer size within Javascript (due to its
	// underlying use of a double float for numbers, leading to max int = 2^53 - 1).
	// This would circumvent the need to use strings within JSON (e.g., the Google
	// solution) to represent integer labels that could exceed the max javascript
	// number.  It would require adding a value check on each label voxel of a
	// mutation request, which might be too much of a hit to handle an edge case.
	MaxAllowedLabel = 9007199254740991
)
View Source 
const MaxBlockSize = 1024 // N^3 < max uint32, so N <= 2^10
View Source 
const MaxSubBlockSize = MaxBlockSize / SubBlockSize
View Source 
const SubBlockSize = 8

Variables

This section is empty.

Functions

func LogMerge added in v0.8.13 

func LogMerge(d dvid.Data, v dvid.VersionID, mutID uint64, op MergeOp) error

func LogSplit added in v0.8.13 

func LogSplit(d dvid.Data, v dvid.VersionID, mutID uint64, op SplitOp) error

func MergeStart added in v0.8.0 

func MergeStart(iv dvid.InstanceVersion, op MergeOp) error

MergeStart handles label map caches during an active merge operation. Note that if there are multiple synced label instances, the InstanceVersion will always be the labelblk instance. Multiple merges into a single label are allowed, but chained merges are not. For example, you can merge label 1, 2, and 3 into 4, then later merge 6 into 4. However, you cannot concurrently merge label 4 into some other label because there can be a race condition between 3 -> 4 and 4 -> X.

func MergeStop added in v0.8.0 

func MergeStop(iv dvid.InstanceVersion, op MergeOp)

MergeStop marks the end of a merge operation.

func SplitStart added in v0.8.0 

func SplitStart(iv dvid.InstanceVersion, op DeltaSplitStart) error

SplitStart checks current label map to see if the split conflicts.

func SplitStop added in v0.8.0 

func SplitStop(iv dvid.InstanceVersion, op DeltaSplitEnd)

SplitStop marks the end of a split operation.

func WriteBinaryBlocks added in v0.8.13 

func WriteBinaryBlocks(mainLabel uint64, lbls Set, op *OutputOp, bounds dvid.Bounds)

WriteBinaryBlocks writes a compact serialization of a binarized Block to the supplied Writer. The serialization is a header + stream of blocks. The header is the following: 

 3 * uint32      values of gx, gy, and gz
 uint64          foreground label

The format of each binary block in the stream is detailed by the WriteBinaryBlock() function.

func WriteRLEs added in v0.8.7 

func WriteRLEs(lbls Set, op *OutputOp, bounds dvid.Bounds)

WriteRLEs, like WriteBinaryBlocks, writes a compact serialization of a binarized Block to the supplied Writer. In this case, the serialization uses little-endian encoded integers and RLEs with the repeating units of the following format: 

int32   Coordinate of run start (dimension 0)
int32   Coordinate of run start (dimension 1)
int32   Coordinate of run start (dimension 2)
int32   Length of run in X direction

The offset is the DVID space offset to the first voxel in the Block. After the RLEs have been written to the io.Writer, an error message is sent down the given errCh.

Types

type BinaryBlock added in v0.8.13 

type BinaryBlock struct {
	Offset dvid.Point3d // voxel offset for the first voxels in this block
	Size   dvid.Point3d
	Label  uint64
	Voxels []bool
}

func ReceiveBinaryBlocks added in v0.8.13 

func ReceiveBinaryBlocks(r io.Reader) ([]BinaryBlock, error)

ReceiveBinaryBlocks returns a slice of BinaryBlock, easily parseable but not necessarily optimally compressed format.

func (*BinaryBlock) Read added in v0.8.13 

func (b *BinaryBlock) Read(r io.Reader, gx, gy, gz int32, label uint64) error

func (BinaryBlock) String added in v0.8.14 

func (b BinaryBlock) String() string

type Block added in v0.8.7 

type Block struct {
	Labels []uint64     // labels in Block.
	Size   dvid.Point3d // # voxels in each dimension for this block

	NumSBLabels []uint16 // # of labels for each sub-block
	SBIndices   []uint32 // indices into Labels array
	SBValues    []byte   // compressed voxel values giving index into SBIndices.
	// contains filtered or unexported fields
}

Block is the unit of storage for compressed DVID labels. It is inspired by the Neuroglancer compression scheme and makes the following changes: (1) a block-level label list with sub-block indices into the list (minimal required bits vs 64 bits in original Neuroglancer scheme), (2) the number of bits for encoding values is not required to be a power of two. A block-level label list allows easy sharing of labels between sub-blocks, and sub-block storage can be more efficient due to the smaller index (at the cost of an indirection) and better encoded value packing (at the cost of byte alignment). In both cases memory is gained for increased computation.

Blocks cover nx * ny * nz voxels. This implementation allows any choice of nx, ny, and nz with two restrictions: (1) nx, ny, and nz must be a multiple of 8 greater than 16, and (2) the total number of labels cannot exceed the capacity of a uint32.

Internally, labels are stored in 8x8x8 sub-blocks. There are gx * gy * gz sub-blocks where gx = nx / 8; gy = ny / 8; gz = nz / 8.

The byte layout will be the following if there are N labels in the Block: 

3 * uint32      values of gx, gy, and gz
uint32          # of labels (N), cannot exceed uint32.
N * uint64      packed labels in little-endian format.  Label 0 can be used to represent
                    deleted labels, e.g., after a merge operation to avoid changing all
                    sub-block indices.

----- Data below is only included if N > 1, otherwise it is a solid block.
      Nsb = # sub-blocks = gx * gy * gz

Nsb * uint16        # of labels for sub-blocks (Ns[i]).
                        Each uint16 Ns[i] = # labels for sub-block i.
                        If Ns[i] == 0, the sub-block has no data (uninitialized), which
                        is useful for constructing Blocks with sparse data.

Nsb * Ns * uint32   label indices for sub-blocks where Ns = sum of Ns[i] over all sub-blocks.
                        For each sub-block i, we have Ns[i] label indices of lBits.

Nsb * values        sub-block indices for each voxel.
                        Data encompasses 512 * ceil(log2(Ns[i])) bits, padded so no two
                        sub-blocks have indices in the same byte.
                        At most we use 9 bits per voxel for up to the 512 labels in sub-block.
                        A value gives the sub-block index which points to the index into
                        the N labels.  If Ns[i] <= 1, there are no values.  If Ns[i] = 0,
                        the 8x8x8 voxels are set to label 0.  If Ns[i] = 1, all voxels
                        are the given label index.

func MakeBlock added in v0.8.7 

func MakeBlock(uint64array []byte, bsize dvid.Point3d) (*Block, error)

MakeBlock returns a compressed label Block given a packed little-endian uint64 label array. It is the inverse of MakeLabelVolume(). There is no sharing of underlying memory between the returned Block and the given byte slice.

func MakeSolidBlock added in v0.8.7 

func MakeSolidBlock(label uint64, blockSize dvid.Point3d) *Block

MakeSolidBlock returns a Block that represents a single label of the given block size.

func SubvolumeToBlock added in v0.8.7 

func SubvolumeToBlock(sv *dvid.Subvolume, lbls []byte, idx dvid.IndexZYX, bsize dvid.Point3d) (*Block, error)

SubvolumeToBlock converts a portion of the given label array into a compressed Block. It accepts a packed little-endian uint64 label array and a description of its subvolume, i.e., its extents in dvid space, and returns a compressed Block for the given chunk when tiling dvid space with the given chunk size.

func (Block) CalcNumLabels added in v0.8.13 

func (b Block) CalcNumLabels(prev *Block) map[uint64]int32

CalcNumLabels calculates the change in the number of voxels under each label. If a previous Block is given, the change is calculated from the previous numbers.

func (*Block) Downres added in v0.8.13 

func (b *Block) Downres(octants [8]*Block) error

Downres takes eight Blocks that represent higher-resolution octants (by 2x) of the receiving block, and modifies the receiving Block to be a half-resolution representation. If a given octant is a nil Block, the receiving Block is not modified for that portion of the higher-resolution octant.

func (*Block) DownresSlow added in v0.8.13 

func (b *Block) DownresSlow(octants [8]*Block) error

DownresSlow is same as Downres() but uses simpler and more memory/compute-intensive approach to computing down-res block.

func (Block) MakeLabelVolume added in v0.8.7 

func (b Block) MakeLabelVolume() (uint64array []byte, size dvid.Point3d)

MakeLabelVolume returns a byte slice with packed little-endian uint64 labels in ZYX order, i.e., a uint64 for each voxel where consecutive values are in the (x,y,z) order: (0,0,0), (1,0,0), (2,0,0) ... (0,1,0) There is no sharing of memory between the returned byte slice and the Block data.

func (Block) MarshalBinary added in v0.8.7 

func (b Block) MarshalBinary() ([]byte, error)

MarshalBinary implements the encoding.BinaryMarshaler interface. Note that for efficiency, the returned byte slice will share memory with the receiver Block.

func (*Block) MergeLabels added in v0.8.13 

func (b *Block) MergeLabels(op MergeOp) (merged *Block, err error)

MergeLabels returns a new block that has computed the given MergeOp.

func (*Block) ReplaceLabel added in v0.8.13 

func (b *Block) ReplaceLabel(target, newLabel uint64) (replace *Block, replaceSize uint64, err error)

ReplaceLabel replaces references to the target label with newLabel.

func (*Block) UnmarshalBinary added in v0.8.7 

func (b *Block) UnmarshalBinary(data []byte) error

UnmarshalBinary implements the encoding.BinaryUnmarshaler interface. The source byte slice is copied into a new 8-byte aligned slice so the receiver block does not depend on the passed slice.

func (*Block) Value added in v0.8.13 

func (b *Block) Value(pos dvid.Point3d) uint64

Value returns the label for a voxel using its 3d location within block. If the given location is outside the block extent, label 0 is returned. Note that this function is inefficient for multi-voxel value retrieval.

func (Block) WriteGoogleCompression added in v0.8.7 

func (b Block) WriteGoogleCompression(w io.Writer) error

GoogleCompression writes label compression compliant with the Google Neuroglancer specification: https://goo.gl/IyQbzL

type Counts 

type Counts struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Counts is a thread-safe type for counting label references.

func (*Counts) Decr 

func (c *Counts) Decr(label uint64)

Decr decrements the count for a label.

func (*Counts) Empty 

func (c *Counts) Empty() bool

Empty returns true if there are no counts.

func (*Counts) Incr 

func (c *Counts) Incr(label uint64)

Incr increments the count for a label.

func (*Counts) Value 

func (c *Counts) Value(label uint64) int

Value returns the count for a label.

type DeltaDeleteSize 

type DeltaDeleteSize struct {
	Label    uint64
	OldSize  uint64
	OldKnown bool // true if OldSize is valid, otherwise delete all size k/v for this label.
}

DeltaDeleteSize gives info to delete a label's size.

type DeltaMerge 

type DeltaMerge struct {
	MergeOp
	Blocks       dvid.IZYXSlice               // not nil if labelarray used.
	BlockMap     map[dvid.IZYXString]struct{} // not nil if labelblk used, to be deprecated.
	TargetVoxels uint64
	MergedVoxels uint64
}

DeltaMerge describes the labels and blocks affected by a merge operation. It is sent during a MergeBlockEvent.

type DeltaMergeEnd 

type DeltaMergeEnd struct {
	MergeOp
}

DeltaMergeEnd is the data sent during a MergeEndEvent.

type DeltaMergeStart 

type DeltaMergeStart struct {
	MergeOp
}

DeltaMergeStart is the data sent during a MergeStartEvent.

type DeltaModSize 

type DeltaModSize struct {
	Label      uint64
	SizeChange int64 // Adds to old label size
}

DeltaModSize gives info to modify an existing label size without knowing the old size.

type DeltaNewSize 

type DeltaNewSize struct {
	Label uint64
	Size  uint64
}

DeltaNewSize is a new label being introduced.

type DeltaReplaceSize 

type DeltaReplaceSize struct {
	Label   uint64
	OldSize uint64
	NewSize uint64
}

DeltaReplaceSize gives info to precisely remove an old label size and add the updated size.

type DeltaSparsevol 

type DeltaSparsevol struct {
	Label uint64
	Mods  dvid.BlockRLEs
}

DeltaSparsevol describes a change to an existing label.

type DeltaSplit 

type DeltaSplit struct {
	OldLabel     uint64
	NewLabel     uint64
	Split        dvid.BlockRLEs
	SortedBlocks dvid.IZYXSlice
	SplitVoxels  uint64
}

DeltaSplit describes the voxels modified during a split operation. The Split field may be null if this is a coarse split only defined by block indices.

type DeltaSplitEnd 

type DeltaSplitEnd struct {
	OldLabel uint64
	NewLabel uint64
}

DeltaSplitEnd is the data sent during a SplitEndEvent.

type DeltaSplitStart 

type DeltaSplitStart struct {
	OldLabel uint64
	NewLabel uint64
}

DeltaSplitStart is the data sent during a SplitStartEvent.

type Mapping 

type Mapping struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Mapping is a thread-safe, mapping of labels to labels in both forward and backward direction. Mutation of a Mapping instance can only be done through labels.MergeCache.

func LabelMap added in v0.8.0 

func LabelMap(iv dvid.InstanceVersion) *Mapping

LabelMap returns a label mapping for a version of a data instance. If no label mapping is available, a nil is returned.

func (*Mapping) ConstituentLabels added in v0.8.0 

func (m *Mapping) ConstituentLabels(final uint64) Set

ConstituentLabels returns a set of labels that will be mapped to the given label. The set will always include the given label.

func (*Mapping) FinalLabel 

func (m *Mapping) FinalLabel(start uint64) (uint64, bool)

FinalLabel follows mappings from a start label until a final mapped label is reached.

func (*Mapping) Get 

func (m *Mapping) Get(label uint64) (uint64, bool)

Get returns the mapping or false if no mapping exists.

type MergeOp 

type MergeOp struct {
	Target uint64
	Merged Set
}

MergeOp represents the merging of a set of labels into a target label.

func (MergeOp) String added in v0.8.5 

func (op MergeOp) String() string

type MergeTuple 

type MergeTuple []uint64

MergeTuple represents a merge of labels. Its first element is the destination label and all later elements in the slice are labels to be merged. It's an easy JSON representation as a list of labels.

func (MergeTuple) Op 

func (t MergeTuple) Op() (MergeOp, error)

Op converts a MergeTuple into a MergeOp.

type OutputOp added in v0.8.13 

type OutputOp struct {
	sync.Mutex // lock on writing
	// contains filtered or unexported fields
}

OutputOp provides a way to communicate with writing goroutines, TODO: concurrency support on the given io.Writer.

func NewOutputOp added in v0.8.13 

func NewOutputOp(w io.Writer) *OutputOp

func (OutputOp) Finish added in v0.8.13 

func (op OutputOp) Finish() error

Finish signals all input to an OutputOp is done and waits for completion. Any error from the OutputOp is returned.

func (OutputOp) Process added in v0.8.13 

func (op OutputOp) Process(pb *PositionedBlock)

type PositionedBlock added in v0.8.7 

type PositionedBlock struct {
	Block
	BCoord dvid.IZYXString
}

PositionedBlock is a Block that also knows its position in DVID space via a chunk coordinate.

func (PositionedBlock) OffsetDVID added in v0.8.7 

func (pb PositionedBlock) OffsetDVID() (dvid.Point3d, error)

OffsetDVID returns the DVID voxel coordinate corresponding to the first voxel of the Block, i.e., the lowest (x,y,z).

func (PositionedBlock) Split added in v0.8.13 

func (pb PositionedBlock) Split(op SplitOp) (split *Block, keptSize, splitSize uint64, err error)

Split a target label using RLEs within a block. Only the target label is split. A nil split block is returned if target label is not within block. TODO: If RLEs continue to be used for splits, refactor / split up to make this more readable.

func (PositionedBlock) SplitSlow added in v0.8.13 

func (pb PositionedBlock) SplitSlow(op SplitOp) (split *Block, keptSize, splitSize uint64, err error)

Split a target label using RLEs within a block by doing full expansion of block into uint64 array. Only the target label is split. A nil split block is returned if target label is not within block.

func (PositionedBlock) String added in v0.8.13 

func (pb PositionedBlock) String() string

func (*PositionedBlock) WriteBinaryBlock added in v0.8.7 

func (pb *PositionedBlock) WriteBinaryBlock(indices map[uint32]struct{}, hasBackground bool, op *OutputOp, bounds dvid.Bounds) error

WriteBinaryBlock writes the binary version of a Block to the supplied Writer, where the serialized data represents just the label voxels. By definition, a binary block has at most two labels (0 = background, 1 = given label) and encoding is a bit per voxel. The binary format is related to the Google and internal DVID label block compression but is simplified, the DVID space offset of the block is included, and the sub-block data are arranged to allow streaming.

Internally, the mask is stored in 8x8x8 sub-blocks. There are gx * gy * gz sub-blocks where gx = nx / 8; gy = ny / 8; gz = nz / 8, and (gx, gy, gz) is relayed in a header outside of the data returned by this function. For example, for a full sparse volume response, there would be a header followed by some number of these binary blocks.

The byte layout will be the following: 

3 * int32       offset of first voxel of Block in DVID space (x, y, z)
byte            content flag:
                0 = background ONLY  (no more data for this block)
                1 = foreground ONLY  (no more data for this block)
                2 = both background and foreground so stream of sub-blocks required.

Stream of gx * gy * gz sub-blocks with the following data:

byte            content flag:
                0 = background ONLY  (no more data for this sub-block)
                1 = foreground ONLY  (no more data for this sub-block)
                2 = both background and foreground so mask data required.
mask            64 byte bitmask where each voxel is 0 (background) or 1 (foreground)

type Set 

type Set map[uint64]struct{}

Set is a set of labels.

func NewSet added in v0.8.7 

func NewSet(lbls ...uint64) Set

Merge returns a set made of the given labels.

func (Set) Copy added in v0.8.5 

func (s Set) Copy() Set

Copy returns a duplicate of the Set.

func (Set) Exists added in v0.8.5 

func (s Set) Exists(i uint64) bool

Exists returns true if the given uint64 is present in the Set.

func (Set) Merge added in v0.8.7 

func (s Set) Merge(s2 Set)

Merge adds the elements in the given set to the receiver.

func (Set) String 

func (s Set) String() string

type SplitOp added in v0.8.13 

type SplitOp struct {
	Target   uint64
	NewLabel uint64
	RLEs     dvid.RLEs
	Coarse   bool // true if the RLEs are block coords (coarse split), not voxels.
}

SplitOp represents a split with the sparse volume of the new label.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.