Amirhossein (Amir) Kardoost

Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation

Evgeny Levinkov*, Amirhossein Kardoost*, Bjoern Andres, Margret Keuper

TPAMI · 2022 · (* Contributed equally)

PDF

The minimum cost lifted multicut problem is a generalization of the multicut problem (also known as correlation clustering) and is a means to optimizing a decomposition of a graph w.r.t. both positive and negative edge costs. It has been shown to be useful in a large variety of applications in computer vision thanks to the fact that multicut-based formulations do not require the number of components given a priori; instead, it is deduced from the solution. However, the standard multicut cost function is limited to pairwise relationships between nodes, while several important applications either require or can benefit from a higher-order cost function, i.e. hyper-edges. In this paper, we propose a pseudo-boolean formulation for a multiple model fitting problem. It is based on a formulation of any-order minimum cost lifted multicuts, which allows to partition an undirected graph with pairwise connectivity such as to minimize costs defined over any set of hyper-edges. As the proposed formulation is NP-hard and the branch-and-bound algorithm (as well as obtaining lower bounds) is too slow in practice, we propose an efficient local search algorithm for inference into resulting problems. We demonstrate versatility and effectiveness of our approach in several applications: 1) We define a geometric multiple model fitting, more specifically, a line fitting problem on all triplets of points and group points, that belong to the same line, together. 2) We formulate homography and motion estimation as a geometric model fitting problem where the task is to find groups of points that can be explained by the same geometrical transformation. 3) In motion segmentation our model allows to go from modeling translational motion to Euclidean or affine transformations, which improves the segmentation quality in terms of F-measure.

@article{kardoost_tpami_2022,
  author = {Levinkov, Evgeny and Kardoost, Amirhossein and Andres, Bjoern and Keuper, Margret},
  journal = {Transactions on Pattern Analysis and Machine Intelligence (TPAMI)},
  title = {Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation},
  year = {2022},
  doi = {10.1109/TPAMI.2022.3148795}
}

Convolutional Neural Network Approach for the Automated Identification of in Cellulo Crystals

Amirhossein Kardoost, Robert Schönherr, Carsten Deiter, Lars Redecke, Kristina Lorenzen, Joachim Schulz, Iñaki de Diego

Journal of Applied Crystallography · 2024

PDF Code Data

In cellulo crystallization is a rare event in nature. Recent advances that have made use of heterologous overexpression can promote the intracellular formation of protein crystals, but new tools are required to detect and characterize these targets in the complex cell environment. The present work makes use of Mask R-CNN, a convolutional neural network (CNN)-based instance segmentation method, for the identification of either single or multi-shaped crystals growing in living insect cells, using conventional bright field images. The algorithm can be rapidly adapted to recognize different targets, with the aim of extracting relevant information to support a semi-automated screening pipeline, in order to aid the development of the intracellular protein crystallization approach.

@article {Kardoost_2024,
  author = {Amirhossein Kardoost and Robert Sch{\"o}nherr and Carsten Deiter and Lars Redecke and Kristina Lorenzen and Joachim Schulz and I{\~n}aki de Diego},
  title = {Convolutional neural network approach for the automated identification of in cellulo crystals},
  year = {2024},
  volume = {57},
  doi = {10.1107/S1600576724000682},
  publisher = {IUCR/Wiley},
  journal = {Journal of Applied Crystallography}
}

Paper thumbnail: Uncertainty in multicuts

Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation

Amirhossein Kardoost, Margret Keuper

UAI · 2021

PDF

The minimum cost lifted multicut approach has proven practically good performance in a wide range of applications such as image decomposition, mesh segmentation, multiple object tracking, and motion segmentation. It addresses such problems in a graph-based model, where real-valued costs are assigned to the edges between entities such that the minimum cut decomposes the graph into an optimal number of segments. Driven by a probabilistic formulation of minimum cost multicuts, we provide a measure for the uncertainties of the decisions made during the optimization. We argue that access to such uncertainties is crucial for many practical applications and conduct an evaluation by means of sparsifications on three different, widely used datasets in the context of image decomposition (BSDS-500) and motion segmentation (DAVIS2016 and FBMS59) in terms of variation of information (VI) and Rand index (RI).

@inproceedings{kardoost_uai_2021,
  author = {Kardoost, Amirhossein and Keuper, Margret},
  title = {Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation},
  booktitle = {Uncertainty in Artificial Intelligence (UAI)},
  year = {2021}
}

Paper thumbnail: Sparse to dense motion segmentation

Self-supervised Sparse to Dense Motion Segmentation

Amirhossein Kardoost, Kalun Ho, Peter Ochs, Margret Keuper

ACCV · 2020

PDF Video Code

Observable motion in videos can give rise to the definition of objects moving with respect to the scene. The task of segmenting such moving objects is referred to as motion segmentation and is usually tackled either by aggregating motion information in long, sparse point trajectories, or by directly producing per frame dense segmentations relying on large amounts of training data. In this paper, we propose a self supervised method to learn the densification of sparse motion segmentations from single video frames. While previous approaches towards motion segmentation build upon pre-training on large surrogate datasets and use dense motion information as an essential cue for the pixelwise segmentation, our model does not require pre-training and operates at test time on single frames. It can be trained in a sequence specific way to produce high quality dense segmentations from sparse and noisy input. We evaluate our method on the well-known motion segmentation datasets FBMS59 and DAVIS2016.

@inproceedings{kardoost_accv_2020_a,
  author = {Kardoost, Amirhossein and Ho, Kalun and Ochs, Peter and Keuper, Margret},
  title = {Self-supervised Sparse to Dense Motion Segmentation},
  booktitle = {Proceedings of the Asian Conference on Computer Vision (ACCV)},
  month = {November},
  year = {2020}
}

A Two-Stage Minimum Cost Multicut Approach to Self-Supervised Multiple Person Tracking

Kalun Ho, Amirhossein Kardoost, Franz-Josef Pfreundt, Janis Keuper, Margret Keuper

ACCV · 2020

PDF

Multiple Object Tracking (MOT) is a long-standing task in computer vision. Current approaches based on the tracking by detection paradigm either require some sort of domain knowledge or supervision to associate data correctly into tracks. In this work, we present a self-supervised multiple object tracking approach based on visual features and minimum cost lifted multicuts. Our method is based on straight-forward spatio-temporal cues that can be extracted from neighboring frames in an image sequences without supervision. Clustering based on these cues enables us to learn the required appearance invariances for the tracking task at hand and train an AutoEncoder to generate suitable latent representations. Thus, the resulting latent representations can serve as robust appearance cues for tracking even over large temporal distances where no reliable spatio-temporal features can be extracted. We show that, despite being trained without using the provided annotations, our model provides competitive results on the challenging MOT Benchmark for pedestrian tracking.

@inproceedings{kardoost_accv_2020_b,
  author = {Ho, Kalun and Kardoost, Amirhossein and Pfreundt, Franz-Josef and Keuper, Janis and Keuper, Margret},
  title = {A Two-Stage Minimum Cost Multicut Approach to Self-Supervised Multiple Person Tracking},
  booktitle = {Proceedings of the Asian Conference on Computer Vision (ACCV)},
  month = {November},
  year = {2020}
}

Paper thumbnail: Object Segmentation Tracking

Object Segmentation Tracking from Generic Video Cues

Amirhossein Kardoost, Sabine Müller, Joachim Weickert, Margret Keuper

ICPR · 2021

PDF Video

We propose a light-weight variational framework for online tracking of object segmentations in videos based on optical flow and image boundaries. While high-end computer vision methods on this task rely on sequence specific training of dedicated CNN architectures, we show the potential of a variational model, based on generic video information from motion and color. Such cues are usually required for tasks such as robot navigation or grasp estimation. We leverage them directly for video object segmentation and thus provide accurate segmentations at potentially very low extra cost. Our simple method can provide competitive results compared to the costly CNN-based methods with parameter tuning. Furthermore, we show that our approach can be combined with state-of-the-art CNN-based segmentations in order to improve over their respective results. We evaluate our method on the datasets DAVIS16,17 and SegTrack v2.

@inproceedings{kardoost_icpr_2021,
  author = {Kardoost, Amirhossein and Müller, Sabine and Weickert, Joachim and Keuper, Margret},
  booktitle = {2020 25th International Conference on Pattern Recognition (ICPR)},
  title = {Object Segmentation Tracking from Generic Video Cues},
  year = {2021},
  doi = {10.1109/ICPR48806.2021.9413089}
}

Solving Minimum Cost Lifted Multicut Problems by Node Agglomeration

Amirhossein Kardoost, Margret Keuper

ACCV · 2018

PDF Code

Despite its complexity, the minimum cost lifted multicut problem has found a wide range of applications in recent years, such as image and mesh decomposition or multiple object tracking. Its solutions are decompositions of a graph into an optimal number of segments which are optimized w.r.t. a cost function defined on a superset of the edge set. While the currently available solvers for this problem provide high quality solutions in terms of the task to be solved, they can have long computation times for more difficult problem instances. Here, we propose two variants of a heuristic solver (primal feasible heuristic), which greedily generate solutions within a bounded amount of time. Evaluations on image and mesh segmentation benchmarks show the high quality of these solutions.

@inproceedings{kardoost_accv_2018,
  TITLE = {Solving Minimum Cost Lifted Multicut Problems by Node Agglomeration},
  AUTHOR = {Kardoost, Amirhossein and Keuper, Margret},
  YEAR = {2018},
  BOOKTITLE = {ACCV 2018, 14th Asian Conference on Computer Vision}
}

Paper thumbnail: Edge detection for multicut

Optimizing Edge Detection for Image Segmentation with Multicut Penalties

Steffen Jung, Sebastian Ziegler, Amirhossein Kardoost, Margret Keuper

GCPR · 2022

PDF

The Minimum Cost Multicut Problem (MP) is a popular way for obtaining a graph decomposition by optimizing binary edge labels over edge costs. While the formulation of a MP from independently estimated costs per edge is highly flexible and intuitive, solving the MP is NP-hard and time-expensive. As a remedy, recent work proposed to predict edge probabilities with awareness to potential conflicts by incorporating cycle constraints in the prediction process. We argue that such formulation, while providing a first step towards end-to-end learnable edge weights, is suboptimal, since it is built upon a loose relaxation of the MP. We therefore propose an adaptive CRF that allows to progressively consider more violated constraints and, in consequence, to issue solutions with higher validity. Experiments on the BSDS500 benchmark for natural image segmentation as well as on electron microscopic recordings show that our approach yields more precise edge detection and image segmentation.

@inproceedings{gcpr_2022,
  TITLE = {Optimizing Edge Detection for Image Segmentation with Multicut Penalties},
  AUTHOR = {Jung, Steffen and Ziegler, Sebastian and Kardoost, Amirhossein and Keuper, Margret},
  YEAR = {2022},
  BOOKTITLE = {GCPR, German Conference on Pattern Recognition}
}

Publications

Journal Articles