superdsm.minsetcover

class superdsm.minsetcover.MinSetCover(atoms, beta, adjacencies, **solve_minsetcover_kwargs)

Bases: object

Objects of this class represent solved instances of the min-weight set-cover problem.

The objective of the problem is to determine a sparse minimal-energy family \(\mathscr X\) of sets, where \(\nu(X)\) is the energy of a set \(X\), and \(\beta \geq 0\) is the sparsity parameter,

\[\operatorname{MSC}(\mathscr S) = \min_{\mathscr X \subseteq \mathscr S} \sum_{X \in \mathscr X} \beta + \nu(X) \enspace\text{s.t. } \bigcup \mathscr S = \bigcup \mathscr X,\]

where the sparse minimal-energy family \(\mathscr X\) is a min-weight set-cover. See Joint segmentation and cluster splitting and Section 2.3.2 in Kostrykin and Rohr (TPAMI 2023) for details.

The family of candidate sets \(\mathscr S\) initially contains sets of cardinality \(\# X = 1\). Further object prototypes (i.e. sets of atomic image regions) are added to \(\mathscr S\) by the update() method. The approximative solution is then updated automatically using the solve_minsetcover() function.

Parameters:

  • atoms – List of objects corresponding to the atomic image regions (instances of the Object class).

  • beta – The sparsity parameter \(\beta \geq 0\).

  • adjacencies – Adjacency graph \(\mathcal G\).

  • solve_minsetcover_kwargs – Passed to the solve_minsetcover() function.

property costs

The value of the min-weight set-cover (the optimal value of the objective function).

get_atom(atom_label)

Returns the object corresponding to an atomic image region.

get_cluster_costs(cluster_label)

Returns the value of the min-weight set-cover for the subset of candidate sets which correspond to a single region of possibly clustered objects.

property solution

The optimal set of objects.

This is the family \(\mathscr X \subseteq \mathscr S\) of sets of atomic image regions, which is optimal with respect to the objective function

\[\sum_{X \in \mathscr X} \beta + \nu(X)\]

subject to the constraint that \(\bigcup \mathscr S = \bigcup \mathscr X\).

update(new_objects, out=None)

Adds new objects to the family of candidate sets \(\mathscr S\) and updates the solution.

Parameters:

new_objects – An iterable of Object instances, each representing a set of atomic image regions.

The solution of the min-weight set-cover is updated automatically.

superdsm.minsetcover.solve_minsetcover(objects, beta, merge=True, max_iter=5, gamma=0.8, out=None)

Computs an approximative min-weight set-cover.

This function implements Algorithm 2 of Kostrykin and Rohr (TPAMI 2023).

Parameters:

  • objects – Corresponds to the family of the candidate sets \(\mathscr S\). Any set \(X \in \mathscr S\) is either included in \(\mathscr X\) or not. Must be a list of objects, so that c.energy correspsonds to the value of the set energy function \(c(X)\) and c is of the class Object.

  • beta – The sparsity parameter \(\beta \geq 0\).

  • merge – The merge step of Algorithm 2 will be used only if True is passed.

  • max_iter – The number of iterations using an increasingly conservative merging strategy (i.e. the sparsity parameter \(\beta\) is reduced).

  • gamma – The factor used to reduce the sparsity parameter \(\beta\) after the first iteration (this is the parameter \(\gamma\) of Algorithm 2, where \(0 < \gamma < 1\)).

  • out – An instance of an Output sub-class, 'muted' if no output should be produced, or None if the default output should be used.

Returns:

The min-weight set-cover \(\mathscr X \subseteq \mathscr S\).