A number of 3D shape reconstruction algorithms, in particular 3D image segmentation methods, produce their results in the form of binary volumes, where a binary value indicates whether a voxel is associated with the interior or the exterior. For visualization purpose, it is often desirable to convert a binary volume into a surface representation. Straightforward extraction of the median isosurfaces for binary volumes using the marching cubes algorithm, however, produces jaggy, visually unrealistic meshes. Therefore, similarly to some previous works, we suggest to precede the isosurface extraction by replacing the original binary volume with a new continuous-valued embedding function, so that the zero-isosurface of the embedding function is smooth but at the same time consistent with the original binary volume. In contrast to previous work, computing such an embedding function in our case permits imposing a higher-order smoothness on the embedding function and involves solving a convex optimization problem. We demonstrate that the resulting separating surfaces are smoother and of better visual quality than minimal area separating surfaces extracted by previous approaches to the problem. We plan to make the code of our algorithm publicly available for researchers working on 3D image segmentation as well as other 3D shape reconstruction applications.