I have found some web based background removal software that seem to use a cool algorithm.
These web apps have a green brush and red brush.
If you paint something with a green brush the selection and the adjacent pixels similar to the ones you painted will not be removed.
If you paint an object with the red brush, say the background the pixels adjacent and similar to the selection will be removed.
This is one of those apps, but can handle only small images, prolly due to server limitations.
http://editphotosforfree.com/photoapps/remove-background-from-image-online/
Now, I want a free app that is either cloud based or Windows or Linux or Android based.