Two delay-and-sum beamformers for 3-D synthetic aperture imaging with row-column addressed arrays are presented. Both beamformers are software implementations for graphics processing unit (GPU) execution with dynamic apodizations and third-order polynomial subsample interpolation. The first beamformer was written in the MATLAB programming language and the second was written in C/C++ with the compute unified device architecture (CUDA) extensions by NVIDIA. Performance was measured as volume rate and sample throughput on three different GPUs: a 1050 Ti, a 1080 Ti, and a TITAN V. The beamformers were evaluated across 112 combinations of output geometry, depth range, transducer array size, number of virtual sources, floating-point precision, and Nyquist rate or in-phase/quadrature beamforming using analytic signals. Real-time imaging defined as more than 30 volumes per second was attained by the CUDA beamformer on the three GPUs for 13, 27, and 43 setups, respectively. The MATLAB beamformer did not attain real-time imaging for any setup. The median, single-precision sample throughput of the CUDA beamformer was 4.9, 20.8, and 33.5 Gsamples/s on the three GPUs, respectively. The throughput of CUDA beamformer was an order of magnitude higher than that of the MATLAB beamformer.

Minimum cut/maximum flow (min-cut/max-flow) algorithms solve a variety of problems in computer vision and thus significant effort has been put into developing fast min-cut/max-flow algorithms. As a result, it is difficult to choose an ideal algorithm for a given problem. Furthermore, parallel algorithms have not been thoroughly compared. In this paper, we evaluate the state-of-the-art serial and parallel min-cut/max-flow algorithms on the largest set of computer vision problems yet. We focus on generic algorithms, i.e., for unstructured graphs, but also compare with the specialized GridCut implementation. When applicable, GridCut performs best. Otherwise, the two pseudoflow algorithms, Hochbaum pseudoflow and excesses incremental breadth first search, achieves the overall best performance. The most memory efficient implementation tested is the Boykov-Kolmogorov algorithm. Amongst generic parallel algorithms, we find the bottom-up merging approach by Liu and Sun to be best, but no method is dominant. Of the generic parallel methods, only the parallel preflow push-relabel algorithm is able to efficiently scale with many processors across problem sizes, and no generic parallel method consistently outperforms serial algorithms. Finally, we provide and evaluate strategies for algorithm selection to obtain good expected performance. We make our dataset and implementations publicly available for further research.

Head and neck squamous cell carcinoma (HNSCC) is often diagnosed at advanced stages. Due to pronounced intratumoral heterogeneity (ITH), reliable risk stratification and prediction of treatment response remain challenging. This study aimed to identify peptide signatures in HNSCC tissue that are associated with treatment outcomes in HPV-negative, advanced-stage HNSCC patients undergoing 5-fluorouracil/platinum-based chemoradiotherapy (CDDP-CRT). We integrated matrix-assisted laser desorption/ionization mass spectrometry imaging (MALDI-MSI) of tryptic peptides with univariate statistics and machine learning approaches to uncover potential prognostic patterns. Formalin-fixed, paraffin-embedded whole tumor sections from 31 treatment-naive, HPV-negative HNSCC patients were digested in situ with trypsin, and the generated peptides were analyzed using MALDI-MSI. Clinical follow-up revealed recurrence or progression (RecPro) in 20 patients, while 11 patients showed no evidence of disease (NED). Classification models were developed based on the recorded peptide profiles using both unrestricted and feature-restricted approaches, employing either the full set of m/z features or a subset of the most discriminatory m/z features, respectively. The unrestricted model achieved a balanced accuracy of 71% at the patient level (75% sensitivity, 66% specificity), whereas the feature-restricted model reached a balanced accuracy of 72%, showing increased specificity (92%) but reduced sensitivity (52%) in the CDDP-CRT cohort. In order to assess treatment specificity, models trained on the CDDP-CRT cohort were tested on an independent patient cohort treated with mitomycin C-based CRT (MMC-CRT). Neither model demonstrated prognostic performance in the MMC-CRT patient cohort, suggesting specificity for platinum-based therapy. Presented findings highlight the potential of MALDI-MSI–based proteomic profiling to identify patients at elevated risk of recurrence following CDDP-CRT. This approach may support more personalized risk assessment and treatment planning, ultimately contributing to improved therapeutic outcomes in HPV-negative HNSCC.

This is a collection of min-cut/max-flow problem instances that can be used for benchmarking min-cut/max-flow algorithms. The collection is released in companionship with the paper: Jensen et al., "Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision", 2021 (Under review). The problem instances are collected from a wide selection of sources to be as representative as possible. Specifically, this collection contains: Most of the problem instances (some are unavailable due to dead links) published by the University of Waterloo: https://vision.cs.uwaterloo.ca/data/maxflow Super-resolution, texture restoration, deconvolution, decision tree field (DTF) and automatic labeling environment from Verma & Batra, "MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems", 2012, BMVC Sparse Layered Graph instances from Jeppesen et al., "Sparse Layered Graphs for Multi-Object Segmentation", 2020, CVPR Multi-object surface fitting from Jensen et al., "Multi-Object Graph-Based Segmentation With Non-Overlapping Surfaces", 2020, CVPRW The reason for releasing this collection is to provide a single place to download all datasets used in our paper (and various previous paper) instead of having to scavenge from multiple sources. Furthermore, several of the problem instances typically used for benchmarking min-cut/max-flow algorithms are no longer available at their original locations and may be difficult to find. By storing the data on Zenodo with a dedicated DOI we hope to avoid this. For license information, see below. Files and formats We provide all problem instances in two file formats: DIMACS and a custom binary format. Both are described below. Each file has been zipped, and similar files have then been grouped into their own zip file (i.e. it is a zip of zips). DIMACS files have been prefixed with `dimacs_` and binary files have been prefixed with `bin_`. DIMACS All problem instances are available in DIMACS format (explained here: http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm). For the larger problem instances, we have also published a partition of the graph nodes into blocks for block-based parallel min-cut/max-flow. The partition matches the one used in the companion review paper (Jensen et al., 2021). For a problem instance with filename `.max` the blocks are in the text file `.blk.txt`. The first line gives the number of blocks. The second gives the block index (zero-indexed) for every node; each entry is separated by a space. Example for a sixteen node graph with four blocks: 4 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 Binary files While DIMACS has the advantage of being human-readable, storing everything as text requires a lot of space. This makes the files unnecessarily large and slow to parse. To overcome this, we also release all problem instances in a simple binary storage format. We have two formats: one for graphs and one for quadratic pseudo-boolean optimization (QPBO) problems. Code to convert to/from DIMACS is also available at: https://www.doi.org/10.5281/zenodo.4903946 or https://github.com/patmjen/maxflow_algorithms. Binary BK (`.bbk`) files are for storing normal graphs for min-cut/max-flow. They closely follow the internal storage format used in the original implementation of the Boykov-Kolmogorov algorithm, meaning that terminal arcs are stored in a separate list from normal neighbor arcs. The format is: Uncompressed: Header: (3 x uint8) 'BBQ' Types codes: (2 x uint8) captype, tcaptype Sizes: (3 x uint64) num_nodes, num_terminal_arcs, num_neighbor_arcs Terminal arcs: (num_terminal_arcs x BkTermArc) Neighbor arcs: (num_neighbor_arcs x BkNborArc) Compressed (using Google's snappy: https://github.com/google/snappy): Header: (3 x uint8) 'bbq' Types codes: (2 x uint8) captype, tcaptype Sizes: (3 x uint64) num_nodes, num_terminal_arcs, num_neighbor_arcs Terminal arcs: (1 x uint64) compressed_bytes_1 (compressed_bytes_1 x uint8) compressed num_terminal_arcs x BkTermArc Neighbor arcs: (1 x uint64) compressed_bytes_2 (compressed_bytes_2 x uint8) compressed num_neighbor_arcs x BkNborArc Where: /** Enum for switching over POD types. */ enum TypeCode : uint8_t { TYPE_UINT8, TYPE_INT8, TYPE_UINT16, TYPE_INT16, TYPE_UINT32, TYPE_INT32, TYPE_UINT64, TYPE_INT64, TYPE_FLOAT, TYPE_DOUBLE, TYPE_INVALID = 0xFF }; /** Terminal arc with source and sink capacity for given node. */ template struct BkTermArc { uint64_t node; Ty source_cap; Ty sink_cap; }; /** Neighbor arc with forward and reverse capacity. */ template struct BkNborArc { uint64_t i; uint64_t j; Ty cap; Ty rev_cap; }; Binary QPBO (`.bq`) files are for storing QPBO problems. Unary and binary terms are stored in separate lists. The format is: Uncompressed: Header: (5 x uint8) 'BQPBO' Types codes: (1 x uint8) captype Sizes: (3 x uint64) num_nodes, num_unary_terms, num_binary_terms Unary arcs: (num_unary_terms x BkUnaryTerm) Binary arcs: (num_binary_terms x BkBinaryTerm) Compressed (using Google's snappy: https://github.com/google/snappy): Header: (5 x uint8) 'bqpbo' Types codes: (1 x uint8) captype Sizes: (3 x uint64) num_nodes, num_unary_terms, num_binary_terms Unary terms: (1 x uint64) compressed_bytes_1 (compressed_bytes_1 x uint8) compressed num_unary_terms x BkUnaryTerm Binary terms: (1 x uint64) compressed_bytes_2 (compressed_bytes_2 x uint8) compressed num_binary_terms x BkBinaryTerm Where: /** Enum for switching over POD types. */ enum TypeCode : uint8_t { TYPE_UINT8, TYPE_INT8, TYPE_UINT16, TYPE_INT16, TYPE_UINT32, TYPE_INT32, TYPE_UINT64, TYPE_INT64, TYPE_FLOAT, TYPE_DOUBLE, TYPE_INVALID = 0xFF }; /** Unary term */ template struct BkUnaryTerm { uint64_t node; Ty e0; Ty e1; }; /** Binary term */ template struct BkBinaryTerm { uint64_t i; uint64_t j; Ty e00; Ty e01; Ty e10; Ty e11; }; Block (`.blk`) files are for storing a partition of the graph nodes into disjoint blocks. The format is: Nodes: uint64_t num_nodes Blocks: uint16_t num_blocks...