UCLA Library

The Beltrami framework has seen its successful applications in many fields of image processing, so as in the graph partitioning problem. In this report, we present a Beltrami energy based graph partitioning model, which is a composition of two minimization problems. To optimize the energy, we can apply the efficient primal-dual projected gradients method to the inner part; and then given the inner optimizer has been found, the rearrangement algorithm can strictly decrease the outer energy in finite steps to achieve the optimization. Specifically for the inner part, we look into finding appropriate primal and dual time steps to ensure the convergence of the primal-dual projected gradients algorithm. Indeed, if the product of the primal and dual time steps is bounded by the inverse of the squared induced norm of $\nabla_w$, then we can show the convergence by squeezing the partial primal dual gap to zero, thanks to Chambolle and Pock's theorem. Moreover, we are interested in exploring the model's similarities to the state of the art, and we believe this geometric graph partitioning model can seamlessly unify both edge and region-based segmentation methods in a single functional by selecting proper conditions. With the stepsizes' boundedness, and the model's region-based and edge-based constructions for comparison purposes, in the end we present experimental segmentation results to confirm that the Beltrami graph partitioning model with our proposed algorithm has good performance in practice.