Image segmentation with complex background is a tedious task. In our study, a convex spline is constructed based on Good Features to Track (GF2T) method's region-based salient feature (i.e., corner) set. For an optimized edge-based segmentation, an ellipse shape prior based on this convex spline is useful in edge regularization procedure with region-based features. This kind of optimization is achieved by Boltzmann machine (BM) to automatically form an elliptical foreground mask of the GrabCut method. We demonstrated our approach's usability through traveling salesman problem (TSP), thus, we consider that the TSP's valid tour's path solved by BM can be taken as an optimized convex spline for edge-based segmentation. In our experiments, proposed BM-based approach has the performance improvement of segmentation to stand-alone GF2T as 29.79% improvement based on bounding boxes evaluation and as 38.67% improvement based on the overlapping pixel regions for a quantitative evaluation via objective metrics.