Best method to segment a given image
For such a segmentation, you might want to use graphcuts:
http://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision

However lately there have been better algorithms proposed, such as Branch and Mincut:
http://research.microsoft.com/en-us/downloads/994e80f7-007b-4fed-a6e9-db5f4f32ccd1/

For most of the methods, source codes are available and you could try them out of the box. Also check out:
http://vision.csd.uwo.ca/code/