Learning discontinuous piecewise affine fitting functions using mixed integer programming over lattice

Piecewise affine functions are widely used to approximate nonlinear and discontinuous functions. However, most, if not all existing models, only deal with fitting a continuous function. In this paper, we investigate the problem of fitting a discontinuous piecewise affine function to a given function defined on an arbitrary subset of an integer lattice, where no restriction on the partition of the domain is enforced (i.e., its geometric shape can be nonconvex). This is useful for segmentation and denoising when the given function corresponds to a mapping from pixels of a bitmap image to their color depth values. We propose a novel Mixed Integer Program (MIP) formulation for the piecewise affine fitting problem, where binary edge variables determine the boundary between two partitions of the function domain. To obtain a consistent partitioning (e.g., image segmentation), we include multicut constraints in the formulation. The resulting problem is $$\mathcal {NP}$$ -hard, and two techniques are introduced to improve the computation. One is to adopt a cutting plane method to add the exponentially many multicut inequalities on-the-fly. The other is to provide initial feasible solutions using a tailored heuristic algorithm. We show that the MIP formulation on grid graphs is approximate, while on king’s graph, it is exact under certain circumstances. We conduct initial experiments on synthetic images as well as real depth images, and discuss the advantages and drawbacks of the two models.