fastncut package¶

fastncut module¶

This is the implementation of a fast algorithm for estimating the minimal normalized cut of a given feature map. Andrej Lucny, 2025, lucny@fmph.uniba.sk

fastncut.ncut(features: Tensor, num_iters: int = 2, mask: Tensor | None = None, init: None | Tensor | int | List[int] | Tuple[int, int] | List[Tuple[int, int]] | Literal['frame', 'full', 'random', 'chessboard'] = 'frame', data_format: Literal['hwc', 'chw', 'nc', 'bhwc', 'bchw', 'bnc'] = 'chw', patience: int = 1, return_all: bool = False, border_size: int = 2, auto_fix: bool = False, eps: float = 1e-05) → Tensor¶

Estimates normalized cut on feature maps.

This function calculates the bipartition of the given feature map by the fastncut algorithm

Parameters:

features (torch.Tensor (float)) – Input feature tensor. The expected shape depends on the data_format argument: - “hwc”: (Height, Width, Channels) - “chw”: (Channels, Height, Width) - Default - “nc”: (Length, Channels) - no spatial grid - “bhwc”: (Batch, Height, Width, Channels) - “bchw”: (Batch, Channels, Height, Width) - “bnc”: (Batch, Length, Channels) - no spatial grid
num_iters (int, optional) – Number of iterations to perform. Default is 1. The optimal value for intensity features is 2. For hundreds of features, 4 is recommended. For very small resolutions like 28x28, 8 is recommended. For trainable module of neural network, 1 is recommended. When num_iters is zero, the algorithm iterates until the bipartition is stable for patience times. (This mechanism serves for the investigation only; it is not proper for production.)
mask (torch.Tensor (bool), optional) –
An optional tensor specifying a part of the given feature map to be processed by the fastncut algorithm - float tensor: (Height, Width) Note: Unfortunately, the shape (Batch, Height, Width) is not supported.

More calls with the batch size one are preferred in this case. It is the same as we cannot have various resolutions in one batch.
init (torch.Tensor or None, optional) – An optional initial tensor used to initialize the fastncut process or a kind of its generation. It indicates the resulting polarity of the bipartition mask. - float tensor: (Height, Width) - “frame”: ones in interior and zeros on the border of the border_size (Default) - “full”: all ones - “random”: random values [-1,1] - “chessboard”: half -1, half 1, like the chessboard - a tuple of int: (x,y) specifies a point/region, which guides the polarity of the bipartition (prompt) - a list of such tuples, if the prompt differs for each item in the batch
return_all (bool, optional) – Determines the output format: - False: return only the final bipartition - True: return all bipartitions, and further info
auto_fix (bool, optional (default False)) – Apply extendWithFix on features; useful mainly when a mask is specified.

Returns:

The resulting bipartition provided by the fastncut algorithm: (Batch, Height, Width) or (Height, Width) If return_all is true, returns dictionary containing the complete info including: - intermediate results from all iterations (Batch, Height, Width) x num_iters - value of the generated init

Return type:

torch.Tensor (bool)

Notes

This algorithm stems from Shi-Malik’s solution for the estimation of the normalized cut. However, it does not require the materialization of the similarity matrix quadratic to the number of pixels/regions. As a result, it is linear instead of quadratic, working for a specific kind of similarity only (cosine similarity).

class fastncut.Ncut(num_iters: int = 1, init: None | Tensor | Literal['frame', 'full', 'random', 'chessboard'] = 'frame', data_format: Literal['bhwc', 'bchw'] = 'bchw', auto_fix: bool = False)¶

Bases: Module

Building block of NN performing fastncut algorithm, i.e., agnostic bipartition (optionally masked)

forward(features: Tensor, mask: Tensor | None = None) → Tensor¶

Define the computation performed at every call.

Should be overridden by all subclasses.

fastncut.toCosSin(features: Tensor, scale: float = 1.0, data_format: Literal['hwc', 'chw', 'bhwc', 'bchw'] = 'chw', wrap_around: bool = False, eps: float = 1e-05) → Tensor¶: Convert features [0, 1/scale] → [0, π/2-ε] and return [cos, sin] channels.

class fastncut.ToCosSin(scale: float = 1.0, data_format: Literal['bhwc', 'bchw'] = 'bchw', wrap_around: bool = False, eps: float = 1e-05)¶

Bases: Module

Convert features [0, 1/scale] → [0, π/2-ε] and return [cos, sin] channels.

fastncut.extendWithFix(features: Tensor, data_format: Literal['hwc', 'chw', 'nc', 'bhwc', 'bchw', 'bnc'] = 'chw', return_offset: bool = False, eps: float = 1e-05) → Tensor¶: Extend the cosine similarity features by adding a feature that ensures the ncut algorithm is applicable.

class fastncut.ExtendWithFix(data_format: Literal['bhwc', 'bchw'] = 'bchw', eps: float = 1e-05)¶

Bases: Module

Extend the cosine similarity features by adding a feature that ensures the ncut algorithm is applicable.

fastncut.extendWithPositionEncoding(features: Tensor, weight: float = 0.59, data_format: Literal['hwc', 'chw', 'bhwc', 'bchw'] = 'chw', wrap_around_x: bool = False, wrap_around_y: bool = False, eps: float = 1e-05) → Tensor¶: Features extension with the positional encoding

class fastncut.ExtendWithPositionEncoding(weight: float = 0.59, data_format: Literal['bhwc', 'bchw'] = 'bchw', wrap_around_x: bool = False, wrap_around_y: bool = False, eps: float = 1e-05)¶

Bases: Module

Features extension with the positional encoding

fastncut.correlateWithPrompt(features: Tensor, prompt: List[Tuple[int, int]], data_format: Literal['hwc', 'chw', 'bhwc', 'bchw'] = 'chw') → Tensor¶: Turn general features into the features describing similarity to a given list of regions (samples of segmented object)

class fastncut.CorrelateWithPrompt(data_format: Literal['bhwc', 'bchw'] = 'bchw')¶

Bases: Module

Extend the cosine similarity features by adding a feature that ensures the ncut algorithm is applicable.

fastncut.targetFromMask(mask: Tensor, d: Tensor = None, custom_b: Tensor = None, eps: float = 1e-07) → Tuple[Tensor, Tensor]¶: Calculate the eigenvector corresponding to the target mask

fastncut.unpr(u: Tensor, v: Tensor) → Tensor¶

Unnormalized projection of vector of features u onto vector of features v. This function processes a batches, each pair u v in the batch is processed as follows:

unpr(u, v) = v @ (vᵀ @ u)

Parameters:

u (Tensor) – A tensor of shape (B, N, C)
v (Tensor) – A tensor of shape (B, N, C) where: - B is the batch size - N is the length of the vector (the number of regions in the feature map) - C is the number of features

Return type:

A tensor of shape (B, N, C) containing the unnormalized projection of u onto v.

Notes

We aim to compute projection of a vector u by Gram matrix (v @ vᵀ) without its materialization. This way, it is much more efficient, O(BNC) instead of O(BN²C) in space and time.

Examples

>>> B, N, C = 1, 784, 384
>>> u = torch.randn(B, N, K)
>>> v = torch.randn(B, N, M)
>>> out = unpr(u, v)
>>> out.shape
torch.Size([1, 784, 384])