On Interpolation for Triangulation-represented Digital Image

Tomáš Janák

(tjanak[at]students.zcu.cz)

Department of Computer Science and Engineering

University of West Bohemia

Pilsen / Czech Republic

(tjanak[at]students.zcu.cz)

Department of Computer Science and Engineering

University of West Bohemia

Pilsen / Czech Republic

Following tables shows exact computing times for four different triangulations (and most important, with differnt count of triangles). Results of individual methods are compared with each other in three resolutions of the outputted image. All implementations were made in C# language and tested on PC with the following configuration: Intel Core2Duo 1,86GHz, 1 GB DDR2 RAM on 800MHz (PC6400), OS: Windows XP SP2.

Image: Fruits, Triangle count: 7829 | ||

Method | Resolution | Consumed time |

Piecewise linear interpolation | 512x512 | 46.875ms |

Zienkiewicz interpolation | 512x512 | 93.750ms |

Interpolation on Bezier patch | 512x512 + | 42s, 750ms |

Interpolation on Coons patch | 512x512 * | 2 min, 18s, 671.875ms |

Piecewise linear interpolation | 1024x1024 | 140.625ms |

Zienkiewicz interpolation | 1024x1024 | 296.875ms |

Interpolation on Bezier patch | 1024x1024 + | 1 min, 58s, 390.625ms |

Interpolation on Coons patch | 1024x1024 * | 2 min, 29s, 781.250ms |

Piecewise linear interpolation | 4096x4096 | 1s, 531.250ms |

Zienkiewicz interpolation | 4096x4096 | 4s, 093.750ms |

Interpolation on Bezier patch | 4096x4096 ++ | 18 min, 5s, 578.125ms |

Interpolation on Coons patch | 4096x4096 ** | 14 min, 40s |

Image: Lena (simple triangulation), Triangle count: 7891 | ||

Method | Resolution | Consumed time |

Piecewise linear interpolation | 512x512 | 46.875ms |

Zienkiewicz interpolation | 512x512 | 93.750ms |

Interpolation on Bezier patch | 512x512 + | 1 min, 56s, 703.1250ms |

Interpolation on Coons patch | 512x512 * | 2 min, 6s, 453.125ms |

Piecewise linear interpolation | 1024x1024 | 156.250ms |

Zienkiewicz interpolation | 1024x1024 | 312.500ms |

Interpolation on Bezier patch | 1024x1024 + | 1 min, 58s, 437.500ms |

Interpolation on Coons patch | 1024x1024 * | 2 min, 32s, 562.500ms |

Piecewise linear interpolation | 4096x4096 | 1s, 546.875ms |

Zienkiewicz interpolation | 4096x4096 | 4s, 78.125ms |

Interpolation on Bezier patch | 4096x4096 ++ | 18 min, 29s, 15.625ms |

Interpolation on Coons patch | 4096x4096 ** | 20 min, 5s, 109.375ms |

Image: Peppers, Triangle count: 24627 | ||

Method | Resolution | Consumed time |

Piecewise linear interpolation | 512x512 | 78.125ms |

Zienkiewicz interpolation | 512x512 | 125.000ms |

Interpolation on Bezier patch | 512x512 + | 6 min, 4s, 375.000ms |

Interpolation on Coons patch | 512x512 * | 7 min, 16s, 609.375ms |

Piecewise linear interpolation | 1024x1024 | 187.500ms |

Zienkiewicz interpolation | 1024x1024 | 343.750ms |

Interpolation on Bezier patch | 1024x1024 + | 6 min, 10s, 843.750ms |

Interpolation on Coons patch | 1024x1024 * | 7 min, 53s, 406.250ms |

Piecewise linear interpolation | 4096x4096 | 1s, 640.625ms |

Zienkiewicz interpolation | 4096x4096 | 4s, 218.750ms |

Interpolation on Bezier patch | 4096x4096 ++ | 57 min, 5s, 375ms |

Interpolation on Coons patch | 4096x4096 ** | 45 min, 30s, 937.500ms |

Image: Lena, Triangle count: 49801 | ||

Method | Resolution | Consumed time |

Piecewise linear interpolation | 512x512 | 109.375ms |

Zienkiewicz interpolation | 512x512 | 187.500ms |

Interpolation on Bezier patch | 512x512 + | 12 min, 37s, 468.750ms |

Interpolation on Coons patch | 512x512 * | 16 min, 18s, 93.750ms |

Piecewise linear interpolation | 1024x1024 | 234.375ms |

Zienkiewicz interpolation | 1024x1024 | 437.500ms |

Interpolation on Bezier patch | 1024x1024 + | 13 min, 4s, 437.500ms |

Interpolation on Coons patch | 1024x1024 * | 20 min, 17s, 437.500ms |

Piecewise linear interpolation | 4096x4096 | 1s, 828.125ms |

Zienkiewicz interpolation | 4096x4096 | 4s, 328.125ms |

Interpolation on Bezier patch | 4096x4096 ++ | 1 h, 53 min, 50s, 203.125ms |

Interpolation on Coons patch | 4096x4096 ** | 1 h, 33 min, 12s, 781.250ms |

For the 4096x4096 resolution, the "step" of patch-based methods had to be increased in order to ensure proper rendering of large triangles, which obviously occur when the triangulation is highly magnified. Therefore the step differs for individual cases - it was chosen to be as big as possible and to ensure perfect rendering at the same time. For further details about what does the "step" represents see the paper, section 4.

** The "step" used for cases marked by "**" was set to 0.002 (that is approximately 500 * 500 = 250 000 iterations per triangle).

* The "step" used for cases marked by "*" was set to0.005 (that is approximately 200 * 200 = 40 000 iterations per triangle).

+ The "step" used for cases marked by "+" was set to0.003 (that is approximately 333 * 333 = 111 111 iterations per triangle).

++ The "step" used for cases marked by "++" was set to0.001 (that is approximately 1000 * 1000 = 1 000 000 iterations per triangle).