Probably someone still need it, so I'll try to answer.

I used triangular barycentric approach for image interpolation, and, as I hoped, it's quite nice. All the math is simplified by the fact that pixels may be considered square and one unit in size, I guess this match you problem description. The main point is dividing square onto triangles by either / or \ diagonal depending on local contrast. Probably that's what you need to avoid artifacts you mentined.

It's rather big (full of comments) so I'll put it on gist: Barycentric image interpolation.