hnccorr.segmentation module¶

HNC and segmentation related components in HNCcorr.

class hnccorr.segmentation.HncParametricWrapper(lower_bound, upper_bound)[source]¶

Bases: object

Wrapper for solving the Hochbaum Normalized Cut (HNC) problem on a graph.

Given an undirected graph $G = (V, E)$ with edge weights $w_{ij} \ge 0$ for $[i,j] \in E$, the linearized HNC problem is defined as:

\[\begin{split}\min_{\emptyset \subset S \subset V} \sum_{\substack{[i,j] \in E,\\ i \in S,\\ j \in V \setminus S}} w_{ij} - \lambda \sum_{i \in S} d_i,\end{split}\]

where $d_i$ the degree of node $i \in V$ and $\lambda \ge 0$ provides the trade-off between the two objective terms.

See closure package for solution method.

__init__(lower_bound, upper_bound)[source]¶: Initializes HncParametricWrapper object.

static _construct_segmentations(source_sets, breakpoints)[source]¶

Constructs a list of segmentations from output HNC.

Each source set and corresponding lambda upper bound is replaced with a Segmentation object where the selection matches the source set and the weight parameter matches the upper bound of the lambda range.

Parameters

source_sets (list[set]) – List of source sets for each lambda range.
breakpoints (list[float]) – List of upper bounds on the lambda range for which the corresponding source set is optimal.

Returns

List of segmentations.

Return type

list[Segmentation]

solve(graph, pos_seeds, neg_seeds)[source]¶

Solves an instance of the HNC problem for all values of lambda.

Solves the HNC clustering problem on graph for all values of lambda simultaneously. See class description for a definition of HNC.

Parameters

graph (nx.Graph) – Directed similarity graph with non-negative edge weights. Edge [i,j] is represented by two directed arcs (i,j) and (j,i). Edge weights must be defined via the attribute weight.
pos_seeds (set) – Set of nodes in graph that must be part of the cluster.
neg_seeds (set) – Set of nodes in graph that must be part of the complement.

Returns

List of optimal clusters for each lambda range.

Return type

list[Segmentation]

Caution

Class modifies graph for performance. Pass a copy to prevent any issues.

class hnccorr.segmentation.Segmentation(selection, weight)[source]¶

Bases: object

A set of pixels identified by HNC as a potential cell footprint.

Variables

selection (set) – Pixels in the spatial footprint. Each pixel is represented as a tuple.
weight (float) – Upper bound on the lambda coefficient for which this segmentation is optimal.

__eq__(other)[source]¶: Compares two Segmentation objects.

__init__(selection, weight)[source]¶: Initializes a Segmentation object.

clean(positive_seeds, movie_pixel_shape)[source]¶

Cleans Segmentation by selecting a connected component and filling holes.

The Segmentation is decomposed into connected components by considering horizontal or vertical adjacent pixels as neighbors. The connected component with the most positive seeds is selected. Any holes in the selected component are added to the selection.

Parameters

positive_seeds (set) – Pixels that are contained in the spatial footprint. Each pixel is represented by a tuple.
movie_pixel_shape (tuple) – Pixel resolution of the movie.

Returns

A new Segmentation object with the same weight.

Return type

Segmentation

fill_holes(movie_pixel_shape)[source]¶

Fills holes in the selection.

Parameters: movie_pixel_shape (tuple) – Pixel resolution of the movie.
Returns: A new Segmentation object with the same weight.
Return type: Segmentation

select_max_seed_component(positive_seeds)[source]¶

Selects the connected component of selection that contains the most seeds.

The Segmentation is decomposed into connected components by considering horizontal or vertical adjacent pixels as neighbors. The connected component with the most positive seeds is selected.

Parameters: positive_seeds (set) – Pixels that are contained in the spatial footprint. Each pixel is represented by a tuple.
Returns: A new Segmentation object with the same weight.
Return type: Segmentation