This repository contains benchmark instances for (s,t)-max-flow/min-cut, which were submitted to the 13th DIMACS Implementation Challenge. The instances are derived from the bicriteria polygon aggregation problem, which is studied in the following publications: Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach. Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, Jan-Henrik Haunert. In: ACM Transactions on Spatial Algorithms and Systems, vol. 11(1), ACM, pages 3:1--3:23, 2025. A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order. Arne Beines, Michael Kaibel, Philip Mayer, Petra Mutzel, Jonas Sauer. In: Proceedings of the 27th Workshop on Algorithm Engineering and Experiments (ALENEX'25), SIAM, pages 29--41, 2025. Bicriteria Polygon Aggregation with Arbitrary Shapes. Lotte Blank, David Eppstein, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, Jonas Sauer. To appear in: Proceedings of the 34th Annual European Symposium on Algorithms (ESA'26), Leibniz International Proceedings in Informatics, 2026. Background These instances are derived from a real-world application: polygon aggregation for map simplification. Given is a set $P$ of building footprints, represented as 2D polygons. The objective is to find a set $S$ of interior-disjoint representative regions, such that each polygon in $P$ is fully contained in a region of $S$. We are interested in a solution that minimizes the objective function $g_\alpha(S) = A(S) + \alpha \cdot P(S)$, where $A(S)$ and $P(S)$ are the total area and perimeter of the regions in $S$, respectively. The parameter $\alpha$ controls the trade-off between faithfulness to the input (represented by the area) and shape simplicity (represented by the perimeter). In a cartographic application, it can be thought of as the "zoom factor" -- the further we zoom out, the simpler we want the shapes to become. We distinguish between two variants of the problem, both for a fixed choice of $\alpha$: Subdivision-based: A subdivision $D$ of the plane (e.g., a constrained Delaunay triangulation) is supplied in advance, such that each polygon in $P$ appears as a cell of $D$. The solution must be constructed by selecting cells from $D$ to add to $P$. The problem is solved via a transformation to (s,t)-min-cut on an augmented geometric dual of $D$ (see any of the papers listed above for details). Unrestricted: No restrictions are made regarding the shape of $S$ -- the only conditions are that $P$ must be covered and that the objective function $g_\alpha(S)$ is minimized. Blank et al. show that in this variant, the polygons are connected by circular arcs of radius $\alpha$ that fulfill several other conditions. The arcs are chosen from a set of $O(n^2)$ candidates. The problem can then be solved optimally via a transformation to the subdivision-based case, where the subdivision $D$ is created by superimposing all $O(n^2)$ arcs. This yields a solution in polynomial time, although the subdivision is much more complex than the constrained Delaunay triangulation. The resulting instances have some similarities with grid-based computer vision max-flow instances, which are built using a similar geometric-dual construction: They are sparse and have short (s,t)-paths. However, unlike typical vision instances, they do not have a regular structure because they are derived from human settlement areas. Consequently, although all nodes (except for s and t) have low degrees, the degrees are not entirely uniform. For the unrestricted variant, the graph is highly detailed because it is derived from a geometric intersection process between many circular arcs. As a side note, a parametric version of the problem, where $\alpha$ is not fixed, has also been studied. Here, the objective is to find an optimal solution for every possible value of $\alpha$. Beines et al. show that, with an equivalent reformulation of the objective function $g_\alpha$, this is a monotone parametric min-cut problem. The instances in this dataset are not parametric, but parametric instances can be found here. Contents The dataset is split into two groups, depending on how the subdivision was built: triangulations: Using a constrained Delaunay triangulation, as proposed by Rottmann et al. The instances are cities of varying sizes (Bonn, Cologne, Berlin, Miami) and the entire German state of Saarland. For each instance, there are five copies, with the different $\alpha$ values 100, 500, 1000, 5000, and 25000. Note that the graph structure is the same for all copies; only the weights are different. arcs: Using the geometric intersection of the candidate arcs, as proposed by Blank et al. for the unrestricted variant. The instances represent the towns of Ahrem, Edendorf, Friesheim and Gerolstein in the German state of North Rhine-Westphalia. For each instance, there are four copies, with the different $\alpha$ values 100, 500, 1000, 5000. Note that for this variant, the graph size increases dramatically with $\alpha$. The arc capacities represent a weighted tradeoff between area and perimeter, measured in square decimeters (dm^2) and rounded to the nearest integer. The $\alpha$ parameter is also measured in decimeters. In the arcs instances, this corresponds to the radii of the circular arcs from which the subdivision is formed, e.g., $\alpha=5000$ represents arcs with radii of 500m. Data Sources Ahrem, Friesheim, Edendorf, Gerolstein, Bonn, Cologne: OpenStreetMap data from Geofabrik Saarland: OpenStreetMap data from Geofabrik Berlin, Miami: GHS-OBAT project Format The files follow the format from the first DIMACS implementation challenge. This is a text format in which each line is prefixed with a character that specifies the type of line. Lines starting with c are comments and should be ignored. The first non-comment line is the problem line: p max NODES ARCS Here, max is the problem type (max-flow/min-cut), NODES is the number of nodes in the network, and ARCS is the number of directed arcs. This is followed by two node descriptor lines:n IDT tn IDS s Here, IDT is the id of the sink node and IDS is the id of the source node. Note that in this format, node ids start at 1. Finally, there is an arc descriptor line for every directed arc in the network: a SRC DST C This specifies an arc from node SRC to DST with capacity C. Capacities with values of int32_max or more should be interpreted as infinite. Note that the format does not require that a reverse arc exists for every directed arc. If reverse arcs are required by your algorithm, you must ensure that missing arcs are added with capacity 0. Credits and Contact This dataset was created by two research groups at the University of Bonn: the geoinformation group headed by Prof. Dr. Jan-Henrik Haunert and the Computational Analytics group headed by Prof. Dr. Petra Mutzel. It is released under the MIT license. When using it, please cite the publications listed above. If you want to report problems or give feedback on the dataset, please contact Jonas Sauer ([email protected]).

Document image dewarping is a crucial step in the digitization of physical documents, as it aims to remove the distortions induced by challenging environment settings and document sheet deformations often encountered when using smartphone cameras for image capture. Recently, deep learning-based methods were combined with knowledge about the expected document structure, also known as a template, at inference time to improve the dewarping results. Our contributions in this work are threefold: (1) we propose a novel document image dewarping approach that leverages the prior knowledge about the document structure effectively by detecting and matching lines from the warped and the template domain, and (2) we introduce a novel evaluation metric called matched normalized character error rate (mnCER) to overcome the limitations of existing metrics in evaluating the dewarping process. (3) Finally, we evaluate our approach on the Inv3DReal dataset and show that our approach outperforms the state-of-the-art methods in terms of visual and text-based metrics. Our approach improves upon the state-of-the-art methods by 32.6% in Local Distortion and 40.2% in mnCER. Our code and models are available at ht tps: // felixhert lein. github.io/doc-matcher.

Due to the steadily rising amount of valuable goods in supply chains, tampering detection for parcels is becoming increasingly important. In this work, we focus on the use-case last-mile delivery, where only a single RGB image is taken and compared against a reference from an existing database to detect potential appearance changes that indicate tampering. We propose a tampering detection pipeline that utilizes keypoint detection to identify the eight corner points of a parcel. This permits applying a perspective transformation to create normalized fronto-parallel views for each visible parcel side surface. These viewpoint-invariant parcel side surface representations facilitate the identification of signs of tampering on parcels within the supply chain, since they reduce the problem to parcel side surface matching with pair-wise appearance change detection. Experiments with multiple classical and deep learning-based change detection approaches are performed on our newly collected TAMpering detection dataset for PARcels, called TAMPAR. We evaluate keypoint and change detection separately, as well as in a unified system for tampering detection. Our evaluation shows promising results for keypoint (Keypoint AP 75.76) and tampering detection (81% accuracy, F1-Score 0.83) on real images. Furthermore, a sensitivity analysis for tampering types, lens distortion and viewing angles is presented. Code and dataset are available at https://a-nau.github.io/tampar.

Abstract Numerous business workflows involve printed forms, such as invoices or receipts, which are often manually digitalized to persistently search or store the data. As hardware scanners are costly and inflexible, smartphones are increasingly used for digitalization. Here, processing algorithms need to deal with prevailing environmental factors, such as shadows or crumples. Current state-of-the-art approaches learn supervised image dewarping models based on pairs of raw images and rectification meshes. The available results show promising predictive accuracies for dewarping, but generated errors still lead to sub-optimal information retrieval. In this paper, we explore the potential of improving dewarping models using additional, structured information in the form of invoice templates. We provide two core contributions: (1) a novel dataset, referred to as Inv3D, comprising synthetic and real-world high-resolution invoice images with structural templates, rectification meshes, and a multiplicity of per-pixel supervision signals and (2) a novel image dewarping algorithm, which extends the state-of-the-art approach GeoTr to leverage structural templates using attention. Our extensive evaluation includes an implementation of DewarpNet and shows that exploiting structured templates can improve the performance for image dewarping. We report superior performance for the proposed algorithm on our new benchmark for all metrics, including an improved local distortion of 26.1 %. We made our new dataset and all code publicly available at https://felixhertlein.github.io/inv3d .

State-of-the-art approaches in computer vision heavily rely on sufficiently large training datasets. For real-world applications, obtaining such a dataset is usually a tedious task. In this paper, we present a fully automated pipeline to generate a synthetic dataset for instance segmentation in four steps. In contrast to existing work, our pipeline covers every step from data acquisition to the final dataset. We first scrape images for the objects of interest from popular image search engines and since we rely only on text-based queries the resulting data comprises a wide variety of images. Hence, image selection is necessary as a second step. This approach of image scraping and selection relaxes the need for a real-world domain-specific dataset that must be either publicly available or created for this purpose. We employ an object-agnostic background removal model and compare three different methods for image selection: Object-agnostic pre-processing, manual image selection and CNN-based image selection. In the third step, we generate random arrangements of the object of interest and distractors on arbitrary backgrounds. Finally, the composition of the images is done by pasting the objects using four different blending methods. We present a case study for our dataset generation approach by considering parcel segmentation. For the evaluation we created a dataset of parcel photos that were annotated automatically. We find that (1) our dataset generation pipeline allows a successful transfer to real test images (Mask AP 86.2), (2) a very accurate image selection process - in contrast to human intuition - is not crucial and a broader category definition can help to bridge the domain gap, (3) the usage of blending methods is beneficial compared to simple copy-and-paste. We made our full code for scraping, image composition and training publicly available at https://anau.github.io/parcel2d.

Within a logistics supply chain, a large variety of transported goods need to be handled, recognized and checked at many different network points. Often, huge manual effort is involved in recognizing or verifying packet identity or packaging structure, for instance to check the delivery for completeness. We propose a method for complete automation of packaging structure recognition: Based on a single image, one or multiple transport units are localized and, for each of these transport units, the characteristics, the total number and the arrangement of its packaging units is recognized. Our algorithm is based on deep learning models, more precisely convolutional neural networks for instance segmentation in images, as well as computer vision methods and heuristic components. We use a custom data set of realistic logistics images for training and evaluation of our method. We show that the solution is capable of correctly recognizing the packaging structure in approximately 85% of our test cases, and even more (91%) when focusing on most common package types.

Recent advances in the area of plane segmentation from single RGB images show strong accuracy improvements and now allow a reliable segmentation of many indoor scenes into planes. Nonetheless, fine-grained details of these segmentation masks are still lacking accuracy, thus restricting the usability of such techniques on a larger scale in numerous applications, such as inpainting for Augmented Reality use cases. We propose to enhance deep learning based methods with classical model-based approaches by aligning the segmented plane masks with edges detected in the image. This allows us to increase the accuracy of state-of-the-art approaches, while limiting ourselves to cuboid-shaped objects. Our approach is motivated by logistics, where this assumption is valid and refined planes can be used to perform robust object detection without the need for supervised learning. Results for two baselines and our approach are reported on our own dataset, which we made publicly available. The results show a consistent improvement over the state-of-the-art. The influence of the prior segmentation and the edge detection is investigated and finally, areas for future research are proposed.