Thursday 2 June 2011

What should big pixels look like?

There has been some fuss recently about a new algorithm that vectorizes pixel art. And yes, judging from the example pictures, this algorithm by Johannes Kopf and Dani Lischinski indeed seems to produce results superior to the likes of hq*x and scale*x or mainstream vectorization algorithms. Let me duplicate the titular example for reference:
Impressive, yes, but as in case with all such algorithms, the first question that came to my mind was: "But does it manage dithering and antialiasing?". The paper explicitly answers this question: no.

All the depixelization algorithms so far have been succesful only with a specific type of pixel art. Pixel art of a cartoonish style that has clear lines and not too many details. This kind of pixel art may have been mainstream in Japan, but in the Western sphere, especially in Europe, there has been a strong tradition of optimalism: the tendency of maximizing the amount of detail and shading within the limited grid of pixels. An average pixel artwork on the Commodore 64 or the ZX Spectrum has an extensive amount of careful manual dithering. If we wish to find a decent general-purpose pixel art depixelization algorithm, it would definitely need to take care of that.

I once experimented by writing an undithering filter that attempts to smooth out dithering while keeping non-dithering-related pixels intact. The filter works as follows:
  • Flag a pixel as a dithering candidate if it differs enough from its cardinal neighborhood (no more than one of the four neighbors are more similar to the reference pixel than the neighbor average).
  • Extend the area of dither candidates: flag a pixel if at least five of its eight neighbors are flagged. Repeat until no new pixels are flagged.
  • For each flagged pixel, replace its color with the weighed average of all the flagged pixels within the surrounding 3x3 rectangle.
Would it be possible to improve the performance of a depixelization algorithm by first piping the picture thru my undithering filter? Let's try out. Here is an example of how the filter manages with a fullscreen C-64 multicolor-mode artwork (from the demoscene artist Frost of Panda Design) and how the results are scaled by the hq4x algorithm:

The undithering works well enough within the smooth areas, and hq4x is even able to recognize the undithered areas as gradients and smooth them a little bit further. However, when looking at the border between the nose and the background, we'll notice careful manual antialiasing that even adds some lonely dithering pixels to smooth out the staircasing. My algorithm doesn't recognize these lonely pixels as dithering, and neither does it recognize the loneliest pixels in the outskirts of dithered gradients as dithering. It is a difficult task to algorithmically detect whether a pixel is intended to be a dithering pixel or a contour/detail pixel. Detecting antialiasing would be a totally different task, requiring a totally new set of processing stages.

There seems to be still a lot of work to do. But suppose that, some day, we will discover the ultimate depixelization algorithm. An image recognition and rerendering pipeline that succesfully recognizes and interprets contours, gradients, dithering, antialiasing and everything else in all conceivable cases, and rerenders it in a high resolution and color without any distracting artifacts. Would that be the holy grail? I wouldn't say so.

The case is that we already have the ultimate depixelization algorithm -- the one running in the visual subsystem of the human brain. It is able to fill in amazing amounts of detail when coping with low amounts of reliable data. It handles noisiness and blurriness better than any digital system. It can extrapolate very well from low-complexity shapes such as silhouette drawings or groups of blurry dots on a CRT screen.

A fundamental problem with the "unlimited resolution" approach of pixel art upscaling is that it attempts to fill in details that aren't there -- a task in which the human brain is vastly superior. Replacing blurry patterns with crisp ones can even effectively turn off the viewer's visual imagination: a grid of blurry dots in the horizon can be just about anything, but if they get algorithmically substituted by some sort of crisp blobs, the illusion disappears. I think it is outright stupid to waste computing resources and watts for something that kills the imagination.

The reason why pixel art upscaling algorithms exist in the first place is that sharp rectangular pixels (the result of nearest-neighbor upscaling) look bad. And I have to agree with this. Too easily recognizable pixel boundaries distract the viewer from the art. The scaling algorithms designed for video scaling partially solve this problem with their interpolation, but the results are still quite bad for the opposite reason -- because there is no respect for the nature of the individual pixel.

When designing a general-purpose pixel art upscaling algorithm, I think the best route would go somewhere between the "unlimited resolution" approach and the "blurry interpolation" approach. Probably something like CRT emulation with some tasteful improvements. Something that keeps the pixels blurry enough for the visual imagination to work while still keeping them recognizable and crisp enough so that the beauty of the patterns can be appreciated.

Nevertheless, I was very fascinated by the Kopf-Lischinski algorithm, but not because of how it would improve existing art, but for its potential of providing nice, organic and blobby pixels to paint new art with. A super-low-res pixel art painting program that implements this kind of algorithm would make a wonderful toy and perhaps even vitalize the pixel art scene in a new and refreshing way. Such a vitalization would also be a triumph for the idea of Computationally Minimal Art which I have been advocating.

32 comments:

Zet said...

Europe and Japan are both on the Eastern hemisphere, though :)

http://en.wikipedia.org/wiki/Western_Hemisphere

jasa fotocopy murah said...

Great article, thanks for sharing with us, do not forget to also visit my website :)

Gary said...


I'm here to testify about Mr John Blank ATM Cards which can withdraw money from any ATM machines around the world.. firstly I thought it was scam until I saw so many testimony about how Mr John sent them the ATM blank card and how it was used to withdraw money in any ATM machine and become rich so I decided to risk the opportunity I contacted him also and I applied for the Blank Card to my greatest surprise I have used it to get 10,000 dollars. maximum withdrawal daily $1,000, Mr John is giving out the card just to help the poor. Hack and take money directly from any ATM Machine Vault,If your interested kindly contact him directly on his email (johnlopez1945@gmail.com)

Neliso Dlamini said...

Become rich today and take the risk of transforming your own life. Try and get a blank ATM card today from (MR JOHN) and be among the lucky ones who are benefiting from this cards. This PROGRAMMED blank ATM card is capable of hacking into any ATM machine,anywhere in the world. I got to know about this BLANK ATM CARD when I was searching for job online about a month ago..It has really changed my life for good and now I'm rich because am a living testimony. The list money I get in a day with this card is about $50,000. I keeping pumping money into my account.there is no risk of being caught because it has been programmed in such a way that it is not traceable, it also has a technique that makes it impossible for the CCTV to detect you..For details on how to get yours today, email the hackers on
Email: { programmedatmcards@gmail.com}OR Text or Call or WhatsApp: +2348154637647

John said...



فرزاد فرزیندانلود آهنگ جدید
علی یاسینی دانلود آهنگ جدید
شهاب مظفری
احسان خواجه امیری

No Name said...

Selling USA FRESH SSN Leads/Fullz, along with Driving License/ID Number with good connectivity.

**PRICE FOR ONE LEAD/FULLZ 2$**

All SSN's are Tested & Verified. Fresh spammed data.

**DETAILS IN LEADS/FULLZ**

->FULL NAME
->SSN
->DATE OF BIRTH
->DRIVING LICENSE NUMBER
->ADDRESS WITH ZIP
->PHONE NUMBER, EMAIL
->EMPLOYEE DETAILS

->Bulk order negotiable
->Minimum buy 10 to 15 leads/fullz
->Hope for the long term business
->You can asked for specific states too

**Contact 24/7**

Whatsapp > +923172721122

Email > leads.sellers1212@gmail.com

Telegram > @leadsupplier

ICQ > 752822040

No Name said...

Selling USA FRESH SPAMMED SSN Leads/Fullz, along with Driving License/ID Number with EXCELLENT connectivity.

**PRICE**
>>2$ FOR EACH LEAD/FULLZ/PROFILE
>>5$ FOR EACH PREMIUM LEAD/FULLZ/PROFILE

>All Leads are Tested & Verified.
>Invalid info found, will be replaced.
>Serious buyers will be welcome & will give discounts to them.
>Fresh spammed data of USA Credit Bureau
>Good credit Scores, 700 minimum scores.

Email > leads.sellers1212@gmail.com
Telegram > @leadsupplier
ICQ > 752822040

**DETAILS IN EACH LEAD/FULLZ**

->FULL NAME
->SSN
->DATE OF BIRTH
->DRIVING LICENSE NUMBER WITH EXPIRY DATE
->ADDRESS WITH ZIP
->PHONE NUMBER, EMAIL, I.P ADDRESS
->EMPLOYEE DETAILS
->REALTIONSHIP DETAILS
->MORTGAGE INFO
->BANK ACCOUNT DETAILS

->Bulk order will be preferable
->Minimum order 25 to 30 leads/fullz
->Hope for the long term business
->You can asked for specific states & zips
->You can demand for samples if you want to test
->Data will be given with in few mins after payment received
->Payment mode BTC, PAYPAL & PERFECT MONEY

**Contact 24/7**

Email > leads.sellers1212@gmail.com
Telegram > @leadsupplier
ICQ > 752822040

Christina N. said...

I’am Mrs Christina, I and my husband are here to testify about how we use United ATM black card to make money and also have our own business today. Go get your blank ATM card today and be among the lucky ones. This PROGRAMMED blank ATM card is capable of hacking into any ATM machine, anywhere in the world. It has really changed our life for good and now we can say we are rich and we can never be poor again. You can withdraw the maximum of $ 10,000 daily We can proudly say our business is doing fine and we have up to 20,000 000 (20 millions dollars in our account) Is not illegal, there is no risk of being caught because it has been programmed in such a way that it is not traceable, it also has a technique that makes it impossible for the CCTV to detect you.. For details and cost on how to get yours today, email the hackers on: unitedblankatmhackcard@gmail.com or text via WhatsApp: +1 208 425 7799

melanie case said...

i want to testify of a great and powerful spell caster my Lover left me and the kids for 2 weeks when i called him he didn't pick up when he came back home the 3rd week he told me he wanted a divorce i was so sad i cried all night he left again i was so lonely the next day i was searching for something online when i found a spell caster called Dr kuta who have helped so many people with their problems so i contacted him with my problems he told me it will take 24hrs and my Lover will be back to me i did every thing he told me to do and the next day my lover came back kneeling and begging he canceled the divorce we are now happy togethe. drkutaherbalcenter@gmail.com   help you too Email him at dr or whatsApp him ‪+234 7054547814 

No Name said...

**SELLING SSN+DOB FULLZ**

CONTACT
Telegram > @leadsupplier
ICQ > 752822040
Email > leads.sellers1212@gmail.com

>>1$ each without DL/ID number
>>2$ each with DL
>>5$ each for premium (also included relative info)

*Will reduce price if buying in bulk
*Hope for a long term business

FORMAT OF LEADS/FULLZ/PROS

->FULL NAME
->SSN
->DATE OF BIRTH
->DRIVING LICENSE NUMBER WITH EXPIRY DATE
->COMPLETE ADDRESS
->PHONE NUMBER, EMAIL, I.P ADDRESS
->EMPLOYMENT DETAILS
->REALTIONSHIP DETAILS
->MORTGAGE INFO
->BANK ACCOUNT DETAILS

>Fresh Leads for tax returns & w-2 form filling
>Payment mode BTC, ETH, LTC, PayPal, USDT & PERFECT MONEY

''OTHER GADGETS PROVIDING''

>SSN+DOB Fullz
>CC with CVV
>Photo ID's
>Dead Fullz
>Spamming Tutorials
>Carding Tutorials
>Hacking Tutorials
>SMTP Linux Root
>DUMPS with pins track 1 and 2
>Sock Tools
>Server I.P's
>HQ Emails with passwords

Email > leads.sellers1212@gmail.com
Telegram > @leadsupplier
ICQ > 752822040

THANK YOU

Arul Raj said...

Awesome blog post,Thank you.
look here
Best Sofa Repair Services in Bellandur

Unknown said...

샌즈카지노 | 우리카지노계열 | 카지노사이트 - 쿠쿠카지노

Unknown said...

Hello viewer am Albert mike from Kenya 30 years old am here to share my testimony on how i joined the brotherhood of illuminati.. four months back when i wanted to join the brotherhood i was scammed by fake agents and people pretending to be Grand Master use the website.. until i met a friend MR BERRY WARD who gave me the genuine procedures i followed and made me a member of the great brotherhood of illuminati. today i am living a good life and i have enough money to do all i ever wanted .if u are interested and u need the help of my Initiator Berry.send email-grandmasterilluminati29@gmail.com or Whats'App MR Berry ward +1(720) 803-2932 thanks Berry, am living the dream i will forever be grateful

yadongbiz said...

Attractive portion of content. I simply stumbled upon your web site and in accession capital to assert that I get actually enjoyed account your weblog. Feel free to visit my website;

야설

japanyadongcom said...

It’s really a great and useful piece of information. I am glad that you shared this useful information with us. Please keep us up to date like this. Thanks for sharing. Feel free to visit my website;
한국야동

yahanvideonet said...

Plz reply as I'm looking to create my own blog and would like to find out where u got this from. thanks a lot. Feel free to visit my website;

일본야동
일본야동
일본야동
일본야동
일본야동


메이저사이트 said...

Found most people will go along with your views on this web site.

안전놀이터 said...

It looks great. I have bookmarked it in my google bookmarks to come back then.

카지노 said...

It’s in point of fact a nice and helpful piece of information.

사설토토 said...

I am satisfied that you simply shared this helpful information with us.

safetotosite said...

It’s always nice when you can not only be informed, but also entertained!

casinositenet said...

Thank you for sharing this fascinating information. Best of luck.

casinositekim said...

Your creative writing abilities inspired me to get my own blog now Thank you.

casinositeguide said...

I like the helpful information that provide in articles. Keep doing it.

토토사이트 said...

I read a lot of stuff here and I like the way you write. Good job!

안전놀이터 said...

This blog is very informative the stuff you provide I really enjoyed reading

바카라사이트 said...

thank you for sharing this amazing piece of information

에볼루션 바카라사이트 said...

The post was really very good. Thanks for sharing.

안전 토토사이트 said...

Thank for you shared again.

gostopsite.com said...

I hope there's an audience next time. thank you

casinosite.zone said...

Having read this I believed it was really enlightening.

edwardsrailcar.com said...

This is something I actually have to try and do a lot of analysis into, thanks for the post.