The segmentation of bone surfaces from magnetic resonance imaging (MRI) data has applications in the quanti- tative measurement of knee osteoarthritis, surgery planning for patient specific total knee arthroplasty and its subsequent fabrication of artificial implants. However, due to the problems associated with MRI imaging such as low contrast between bone and surrounding tissues, noise, bias fields, and the partial volume effect, segmentation of bone surfaces continues to be a challenging operation. In this paper, a new framework is presented for the enhancement of knee MRI scans prior to segmentation in order to obtain high contrast bone images. During the first stage, a new contrast enhanced relative total variation (RTV) regularization method is used in order to remove textural noise from the bone structures and surrounding soft tissue interface. This salient bone edge information is further enhanced using a sparse gradient counting method based on L0 gradient minimization, which globally controls how many non-zero gradients are resulted in order to approximate prominent bone structures in a structure-sparsity-management manner. The last stage of the framework involves incorporation of local phase bone boundary information in order to provide an intensity invariant enhancement of contrast between the bone and surrounding soft tissue. The enhanced images are segmented using a fast random walker algorithm. Validation against expert segmentation was performed on 10 clinical knee MRI images, and achieved a mean dice similarity coefficient (DSC) of 0.975.