Efficient Column Generation for Cell Detection and Segmentation

We study the problem of instance segmentation in biological images with crowded and compact cells. We formulate this task as an integer program where variables correspond to cells and constraints enforce that cells do not overlap. To solve this integer program, we propose a column generation formulation where the pricing program is solved via exact optimization of very small scale integer programs. Column generation is tightened using odd set inequalities which fit elegantly into pricing problem optimization. Our column generation approach achieves fast stable anytime inference for our instance segmentation problems. We demonstrate on three distinct light microscopy datasets, with several hundred cells each, that our proposed algorithm rapidly achieves or exceeds state of the art accuracy. Keywords: Combinatorial optimization, Column generation, Integer programming, Large scale optimization, Linear programming 1. Introduction Cell detection and instance segmentation are fundamental tasks for the study of bioimages (Meijering, 2012) in the era of big data.