An image upscaling algorithm jointly optimizes estimating pixel color, classifying it into one of multiple regions, and estimating region boundaries subject to region continuity and edge-configuration constraints. The joint solution of constraints at multiple levels of image abstraction leads to improved image reconstruction quality. The algorithm involves subdividing the image signal into multiple distinct regions, including an upper region and a lower region, and at least one transition zone between the upper and lower regions; constructing a plurality of separate curves, one for each region; smoothing each curve independently of the other curves; and reconstructing the image signal from the smoothed curves such that the reconstructed image signal has no segment in any transition zone.