Did you play around with Inpaint and texture synthesis at all? I feel like the natural next step for this is to remove the old fish, fill in the background with texture synthesis and then put the new fish into the picture.
Either way, I'm really excited to work thru and understand your RadialBasisInterpolation function. I've needed this for my own projects and the interpolating function I've made haven't been satisfactory.