[Tmmrn]

kolourpaint from KDE. It's basically a clone with more features.

https://vidd.me/kAU

I did a quick check: It also does resizing with several choosable smoothing algorithms and the "perfect shape" thingy too..

[hjek]

It's kind of a Debian/Ubuntu issue, but it is kind of heavy having to install 150 MBs of desktop environment (with database server, wtf?!) to use a paint program. Kind of difficult to compile from scratch too ( the ./configure file seems to be missing in their SVN repo). But looks really cool on the video :-)