As stated by Ruief it is possible to use Photoshop to perform the requested actions. There are really good tutorials on how to quick select with Edge detection. Including how to detect difficult areas. A great example is show in the next video: https://www.youtube.com/watch?v=8XVATypXio0
Otherwise just buy the Recolored tool. For $29 doller it is worth the money.