Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Warp wrote:
Maybe it's just my monitor, but it looks pretty darn close to me:[..]
If the color picking algorithms are that bad, then perhaps the colors should be picked manually. After all, there aren't that many to choose from.
Side by side comparison of the two colors (MP: #00F8F8, SMB: #9CFBF0):
Again, what's obvious to the human eye is not obvious to the mathematic formula. Also, a global change of color temperature / brightness is often completely ignored by a human, whereas a local change of colors is noticed more easier. A good algorithm could tweak the global color temperature or the global brightness to invoke better color matches, but I know of no such algorithm.* All of these color difference algorithms are extremely local: They work on two individual colors at a time.
As for the "manual" option, I don't see how picking the colors manually is reasonably doable when the input image contains 10303 colors (due to filtered rescaling).
*) Hmm, maybe I should work on that a bit.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Warp wrote:
I can see cyan right there in the Mario Paint palette. I think the algorithm that decides the gray is closer to cyan than cyan itself is not very well done.
The algorithm that chooses nearest palette colors used an euclidean RGB distance to determine the nearest color, and came up with what you saw. The theory of measuring color differences is currently an open area of science with a number of different formulas devised during decades. You can read about it at http://en.wikipedia.org/wiki/Color_difference .
For the same price, I rendered that animation with a number of different color difference formulae. These are:
RGB, CIE-76, CIE-94, CIEDE-2000, BFD, CMC
The CIE-based formula (all but RGB) were based on the CIE L*a*b* colorspace (or LCh), which are created from RGB using a conversion matrix called "white point". IIRC my program uses the Adobe D65 whitepoint matrix.
The cyan of Mario Paint is considerably darker and of different hue & saturation than the cyan background in that SMB3 level. Different enough to cause all of these algorithms to choose another color as the nearest one.
As can be deduced from the dithering patterns in http://bisqwit.iki.fi/kala/snap/mp/mar.gif, it only becomes a close representation of the video's color by the addition of great amount of white, a token amount of yellow and a token amount of gray.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Warp wrote:
As I commented, district heating is (AFAIK) currently the most energy-efficient and least-polluting solution to heat large amounts of homes and other buildings in cities (as well as having a virtually endless supply of hot shower water), so it is indeed a bit strange that so many so-called first-world countries have not adopted this technology. Heating water with electricity is a huge waste of energy.
In Finland I have noticed that many houses (not apartments) have a water heater. It is especially common at areas of lower population density, such as the other 90% of Finland.
Wow, do you really have to wait 6 months to see a dentist in Finland?
Though Finland has a tax-supported public health care, often the queues to treatment are many months long, sometimes longer than a year. Private dentists and doctors usually grant appointments if not within the same day, within a few days at most, but they do also cost significantly more, to the degree that is not affordable for most pensioners or for the unemployed.
Re: TV fee, see prior discussion.
Dacicus wrote:
What's the reasoning behind requiring TV permits? Do you need a permit to listen to the radio and access the Internet, too? With just that information, it sounds like a massive set-up for widespread censorship.
The Finnish Broadcasting Company (YLE) offers several TV channels that are completely devoid of advertisements. Instead, they are funded with the money collected from the TV permits. They have a legal role in Finland, possibly originating from the times when they were the channels for official information such as war-time alarms. Anyone who possesses a device that is capable of receiving their transmissions, regardless of whether you actually watch them, must pay the fee.
Anyone who is not a TV fee payer will receive periodically mailing from the Communications Office containing the TV fee form and a warning that it's a punishable offense to not pay it, if you have a TV. TV inspectors also visit houses that do not pay the TV fee, and ask if they can inspect the house for a TV. One is not legally obliged to let them in, but failure to cooperate with them has sometimes resulted in the person being ordered to pay the fee anyway, even if they really do not have a TV. Winning the battle in such cases has proven to be very tough, because they do demand that you prove a negative, even though such conduct is illegal.
As the fee has become more and more expensive lately, more and more people are getting rid of their TV so they also don't need to pay the fee. This has spawned a lobbyist motion that the TV fee should be made mandatory, like a tax, on everyone, regardless of whether they have a TV or not. It would be somewhat cheaper than the current fee (which gains it some support from people who already pay it), while still quite expensive (obviously, present non-subscribers vehemently object to it). They also want to extend it to cover Internet connection ownership (because of Internet TV, so that if you possess Internet connection, you must also pay the TV fee), cellphones and whatnot.
Radio is free, even the radio channels of YLE (which have no advertisements).
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Hello and congratulations on your first TAS experiment.
However, I don't think this video is a submission material for TASVideos. As you yourself admit, it's full of various kind of errors.
The TASVideos submission queue is meant for videos that should eventually become publications, and there's a quality bar on those publications. More information at: http://tasvideos.org/Rules.html
You're welcome to continue refining your skills, and perhaps one day you'll create something truly outstanding. This submission is not it, though.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
What is happening in the next few years is going to be so interesting that I wouldn't like to miss it. Then again, what's happening 200 years from now may be even more mind-blowing, but at least now I know the context. :-)
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Ver Greeneyes wrote:
Should be 2^15 - if I'm not mistaken, the SNES uses BGR555 internally. There are several ways to convert that to RGB888, the most mathematically correct is probably
... where the + 15 is the integer version of rounding (that is, (int)(31/2)).
Yes, you're mistaken. & 5 is quite wrong. That is probably just a thinking error though. You want a & 31. Or, & ((1 << 5)-1).
Converting a 0..31 value into 0..255 range: n*8 + n/4.
(Rationale: 256/32 = 8 (the multiply value); 255 - 8*31 = 7 (missing value); 32/X = 7+1, solve X gets 4 (the divider).)
I.e.
unsigned r = (input >> 10) & 31; r = r*8 + r/4;
unsigned g = (input >> 5) & 31; g = g*8 + g/4;
unsigned b = (input >> 0) & 31; b = b*8 + b/4;
// Note: almost all compilers produce shifts here. If that is not the case, write (r << 3) + (r >> 2) instead.
output = (r << 16) + (g << 8) + b;
Observing this code shows that the bits of the original value will end up as follows:
ONMLKjihgfEDCBA
->
ONMLKONMjihgfjihEDCBAEDC
Which means that the code can be translated to this:
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
nitsuja wrote:
Another way that appears to work fine is to put in a hack like this:
Sadly, it did not seem to change the situation in any manner. It gives me the exact same message...
My main code:
Language: lua
while(movie.framecount() < 152) do next() end
getcur()
if(movie.framecount() < 530)then
if(cury ~= 244) then clickat(208,84) end
for y = 90,146,8 do
-- for x=214,230,8 do
for x=198,230,8 do
if(movie.framecount() > 286)or(cury == 244) then break end
if(y == 146)and(x >= 230) then break end
print('trying click at('..x..','..y..')')
clickat(x,y)
end
end
while(cury ~= 108) do next() end
for n=1,50 do click=not click;next() end
repeat click = not click; next() until(cury < 244)
end
if(movie.framecount() < 1009)then
clickat(233,207) --; next()
clickat(60,207) --; next()
-- continues here with stuff.
end
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
There is one problem with TASBlend. It increases jerkiness.
Simple frame dropping from 60Hz to 30Hz works like this:
drop TAKE drop TAKE drop TAKE drop TAKE drop TAKE drop TAKE ...
where drop=0% blend and TAKE=100% blend.
TASblend works like this:
low HIGH HIGH low low HIGH HIGH low low HIGH HIGH low low HIGH ...
where low=33% blend and HIGH=67% blend.
The low-blends are mostly unnoticeable at most situations. Which means, instead of the jerkiness being caused by one frame dropped, now two frames are dropped. It's an inchworm effect. Fast,slow,fast,slow,fast,slow...
I don't think I am expressing clearly here, but the concern is that this just substitutes one kind of jerkiness for another kind of jerkiness, and that it might still look bad.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
nitsuja wrote:
The only way I can reproduce those results is by first clicking on the T to switch to the pen tool on the title screen, but isn't 194 an invalid Y coordinate in that case? I can't get it to go below 190.
I see. It was a consequence of the clicks being faster now. Sorry about that.
However, when attempting to access the bottom-screen tools in the drawing screen, I get:
mousegoto(233,207) failed. it could only get to 223,145. rolled back.
mousegoto(60,207) failed. it could only get to 60,145. rolled back.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
On startup screen:
mousegoto(214,194) failed. it could only get to 214,186. rolled back.
mousegoto(222,194) failed. it could only get to 222,186. rolled back.
mousegoto(230,194) failed. it could only get to 230,186. rolled back.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
For the record. For the original picture (resized and sharpened):
Conversions with Nitsuja's version of Scolorq (filter=3, presumably gamma=1.0).
From left to right: Dithering level = 1.25, 1.0, 0.75, 0.6 and 0.5 respectively.
Conversions using Yliluoma-2 dithering @ 32-color mix (no precombines), with gamma=1.0 (NOTE: gamma 1 should not be used, it is wrong):
From left to right: original; RGB; CIE 76; CIE 94; CIEDE 2000.
The same, with gamma=2.0:
The same, with 4 colors (pointless, except to illustrate the different ΔE formulae):
The same, with 2 colors:
A selection of error diffusion filters, gamma 1.0:
From left to right: Original, Floyd-Steinberg, Jarvis-Judice-Ninke, Sierra-3 and Sierra-2-4A
The same, with gamma 2.0:
Finally, Yliluoma-2 dithering with gamma=2, with 16 colors, from 16 precombined maximum-16-color unique color mixes, at 16x16 matrix, with different delta-E formulae:
From left to right, RGB; CIE 76; CIE 94; CIEDE 2000; CMC; BFD. Each of these small images took something from 10―30 minutes to render (on a 4-core), but the result is definitely worth it. Lifting the unique-color restriction would possibly yield even better results. (Note that as of this posting they're still rendering, but will come up.)
(Do you now see why I prefer ordered-dithering over floyd-steinberg?)
(Disclaimer: It's possible though, that my implementation of error-diffusion dithers is buggy.)
Appendix:
16 colors; RGB and CIE76 side-by-side. Gamma=2.0
Floyd-Steinberg:
Scolorq (gamma=1.0, RGB, default options; original shown at side to show how the dithered version is lighter due to wrong gamma):
4 colors (gamma=2.0, RGB and CIE76):
2 colors
4 colors, with less choices and more duplicates
2 colors, with less choices and more duplicates
Mega Man at 64 colors (minimal precombines to make it fast) at RGB,CIE76,CIEDE2000,CMC,BFD, gamma 2.2:
Same, but 4 colors:
Same, but 2 colors:
Fewer colors are preferred if you want to increase the chances of Mario Paint's predefined dithering brushes being used.
Note: When I say "64 colors" in this context, it means that for each pixel, a selection of 64 colors is formed from the 15-color palette. From that selection, the color is selected according to the dithering matrix. It does not mean that the image has 64 colors.
It would also be possible to create custom dithering brushes according to whichever dithering patterns are the most common ones in the source picture (assuming you still have enough one-pixel brushes to complete the image). I considered this option, but could not figure out how to achieve it optimally. This possibility, however, exists only when using ordered dithering.
EDIT: Oh, one more thing. I forgot. It is possible to mix ordered dithering and error diffusioning! It works by diffusing the error that remains after ordered-dithering, as opposed to diffusing the error that remains after nearest-color quantization.
From left to right: Yliluoma-2 dithering, Yliluoma-2 + Floyd-Steinberg, Floyd-Steinberg. Gamma = 2.2, colors=15, precombine=minimal.
The fourth image is of Nitsuja's version of Scolorq (where gamma=presumably 1.0) and the fifth is the original (resized+sharpened).
Same, with 4 colors:
Same, with 2 colors & minimum premixes:
-----------
Conclusions:
― Any proper dithering algorithm should operate on gamma-corrected RGB values rather than on linear RGB values. Failure to do this will produce an image that is obviously lighter in tone than the original. This error is most pronounced when the dithered colors differ significantly from each others.
― With static images, for certain images, ordered dithering can produce at least as good pictures as error-diffusion dithering, but for many images, it is vice versa.
― All error diffusion dithers, except for scolorq, seem to suffer from a bias towards gray values. Gray is apparently a good approximation for most colors. Therefore, where error diffusion is deemed appropriate over ordered dithering, I recommend using scolorq except where its lack of gamma correction is too obvious.
― Especially at low color candidate counts, ordered dithering produces distinguished repetive patterns, which may be very beneficial in optimizing the production of the picture when patterned brushes are available (such as in Mario Paint).
― From the six color difference formulae (ΔE), an euclidean distance in the RGB space appeared to be sufficient for most purposes. In a few cases, an euclidean distance in the LAB C*i*e* space (aka. CIE 76) produced better results. The more expensive formulae (CIE 94, CIEDE 2000, CMC, BFD) produced no advantage to justify their significantly more expensive calculation. (And indeed, BFD often seemed even to produce inferior results).
― For customized needs, it often is warranted to do extensive testing with different values for gamma, and color collection/mixing, in order to produce the image that is best for the particular need. Remember, that the eye is more sensitive to local differences in color/tone than to global differences of color/tone. Therefore, it is forgivable to tweak the colorscape of the entire image at once (such as by darkening, brightening, or colorizing it), if it helps bringing out a more accurate local contrast. Such testing was not done here.
― For animation, ordering dithering should always be used rather than error diffusion dithering. To prove the point, study these three examples (from DemonStrate's Portal Done Pro speedrun... rendered in Mario Paint palette.):
―― http://bisqwit.iki.fi/kala/snap/mp/pdp_fs.gif (1.3 MB, Floyd-Steinberg @gamma=2)
―― http://bisqwit.iki.fi/kala/snap/mp/pdp_sc.gif (1.5 MB, Scolorq @gamma=1)
―― http://bisqwit.iki.fi/kala/snap/mp/pdp_y2.gif (913 kB, Yliluoma-2 @gamma=2).
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Here is my Lua function for producing a mouse click at a given coordinate in Mario Paint. It usually achieves the movement in a few frames, but sometimes it gets stuck in an infinite loop, circling the intended coordinates in an everlasting attempt to compensate for the perceived error. Does anyone have will to try to improve it?
This is at the core of my Mariopaint TAS.
Language: lua
local sendx,sendy = 128,127
local click = false
local curx,cury = "?","?"
local function getcur()
curx,cury = memory.readbyte(0x7E0226), memory.readbyte(0x7E0227)
end
local function next()
joypad.set(1, { x = sendx, y = sendy, left=click } )
emu.frameadvance()
getcur()
local valid_location = AND(memory.readbyte(0x7E0426),1)
gui.text(10,160, "cur="..curx..","..cury..";send="..sendx..","..sendy..",valid="..valid_location)
end
local function ismousedown()
return memory.readbyte(0x7E00DE) >= 0x40
end
local function mousegoto(x,y)
local s = savestate.create(1)
local prompt = "curx="..curx..","..cury..";goal="..x..","..y..";send="..sendx..","..sendy
maxadjust = 97
while(true) do
-- Go forward a few frames to get a stable reading
getcur()
local origx,origy = curx,cury
gui.text(40,140, prompt)
savestate.save(s)
local n
for n = 1,3 do
next()
gui.text(40,140, prompt)
end
if cury == 244 then break end
local valid_location = AND(memory.readbyte(0x7E0426),1) == 0
savestate.load(s)
--if((origx ~= curx) or (origy ~= cury)) then
prompt = "cur="..curx..","..cury..";orig="..origx..","..origy..";goal="..x..","..y..";send="..sendx..","..sendy
-- Find out how much the current address must be corrected
-- to reach at the desired endpoint
local errx = x - curx
local erry = y - cury
if (errx == 0) and (erry == 0) then
if(valid_location) then break end
errx = 128
end
--if(errx > 128) then errx = errx - 256 end
--if(errx < -128) then errx = errx + 256 end
--if(erry > 128) then erry = erry - 256 end
--if(erry < -128) then erry = erry + 256 end
if(errx > maxadjust) then errx = maxadjust end
if(errx < -maxadjust) then errx = -maxadjust end
if(erry > maxadjust) then erry = maxadjust end
if(erry < -maxadjust) then erry = -maxadjust end
next()
sendx = AND(sendx + errx, 255)
sendy = AND(sendy + erry, 255)
--end
if((origx ~= curx) or (origy ~= cury)) then
maxadjust = maxadjust*math.random(6,9)/10 + math.random(1,2)
end
end
end
function clickat(x,y)
click = false; while(ismousedown())do next()end
while(true)do
mousegoto(x,y)
local s = savestate.create(1)
savestate.save(s)
click = true ; while(not ismousedown())do next()end
if((cury == 244)or((curx == x)and(cury == y)))then break end
savestate.load(s)
click = false; next()
end
click = false; while(ismousedown())do next()end
end
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Warp wrote:
Why use ordered dithering when scolorq or even Floyd–Steinberg would create a visually much better result?
In order to give Mario Paint's predefined dithering brush patterns a chance. Also, I like the ordered-dithered appearance.
Also, Scolorq cannot do predefined palettes.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
I've been secretly working on a Mario Paint drawing TAS this year.
My TAS uses the mouse instead of the keypad for maximum performance, but it is still rather lacking in, well, performance. The mouse ends up being rather unpredictable. So instead of drawing one pixel per frame, it takes many more frames per pixel, lifting and depressing the pen individually each time.
The TAS is entirely generated with a Lua script, which in turn is generated with a PHP script, by reading from a plan generated by a C++ program, which in turn reads images generated with Animmerger.
The script has understanding about the painting program's tools, and can use different types of pens, and it can use the colour patterns that include pre-defined dithering masks. It also knows about the bucket fill tool, but it only uses it in the beginning of the render of each image at most.
The set of images it attempts to render is like this:
In sequence: Naruto; a car; Megaman; a manga drawing; Mario paint cover crisp and neat; Mario paint cover with more accurate colors.
Once it finishes an image, it immediately starts painting the next one over the previous one.
Here's my latest WIP. I don't remember what it exactly contains. IIRC the script got stuck somewhere.
http://dev.w3.fi/%7Ebisqwit/mariopaint-wip-unknown.smv
Oh, and about dithering: All these images are converted with Animmerger using Yliluoma-2 dithering at matrix size 16x16 with maximum 4 color combinations per pixel, maximum precombined colors, assumed gamma 2.0. The original was resized with lanczos filtering and sharpened minimally prior conversion. The dithering was rigged to produce patterns aligned to Mario Paint's brushes where possible.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
You should wrap your code in the [cоde][/cоde] tags; otherwise indents get removed and end results becomes very difficult to parse.
So I went and read the actual ppu.cpp instead.
sphitx is an x coordinate that is used for checking whether this scanline was the one on which sprite 0 gets rendered (sprite 0 hit). The PPU can be queried for this condition. The variable records the value 0x100 if the hit no longer needs to be checked, or otherwise, the x coordinate that was last checked.
It's something like this. I'm not the author of that code, so I am only deducing from reading it.
I do not find a "flow" in your pasted code, so I cannot answer that question. However, if you want to understand how that function works, it might help for you to study first how the NES PPU works. Suggest this article: http://www.nesdev.com/2C02%20technical%20reference.TXT
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
I agree that the rule that forbids fan translations has been biting me most. I know why I set that rule, but it still annoys me most.
Now that I'm no longer in charge, I have no objection to if the rule is removed or changed.
For instance, I would be glad to see the DeJap translation of Star Ocean TASed, possibly even obsoleting the current Japanese version thereof, thereby potentially significantly increasing the entertainment ratings of the TAS of that relatively unknown game. (And I would like to see it being done in an emulator that does not distort the speech of the intro, such as (probably) BSNES.)
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
By post length / number of words?
It is with great sadness that I regrettably must inform everyone that I vote "no" on this submission.
By number of sentences?
Hi. No vote. Thanks. Better luck next time.
By number of verbs?
I hope nobody gets disappointed by it being said that my vote is going to be "no".
Again, what's obvious to the human eye is not obvious to the mathematic formula. Also, a global change of color temperature / brightness is often completely ignored by a human, whereas a local change of colors is noticed more easier. A good algorithm could tweak the global color temperature or the global brightness to invoke better color matches, but I know of no such algorithm.* All of these color difference algorithms are extremely local: They work on two individual colors at a time.
As for the "manual" option, I don't see how picking the colors manually is reasonably doable when the input image contains 10303 colors (due to filtered rescaling).
*) Hmm, maybe I should work on that a bit.
Conversions with Nitsuja's version of Scolorq (filter=3, presumably gamma=1.0).
From left to right: Dithering level = 1.25, 1.0, 0.75, 0.6 and 0.5 respectively.
Conversions using Yliluoma-2 dithering @ 32-color mix (no precombines), with gamma=1.0 (NOTE: gamma 1 should not be used, it is wrong):
From left to right: original; RGB; CIE 76; CIE 94; CIEDE 2000.
The same, with gamma=2.0:
The same, with 4 colors (pointless, except to illustrate the different ΔE formulae):
The same, with 2 colors:
A selection of error diffusion filters, gamma 1.0:
From left to right: Original, Floyd-Steinberg, Jarvis-Judice-Ninke, Sierra-3 and Sierra-2-4A
The same, with gamma 2.0:
Finally, Yliluoma-2 dithering with gamma=2, with 16 colors, from 16 precombined maximum-16-color unique color mixes, at 16x16 matrix, with different delta-E formulae:
From left to right, RGB; CIE 76; CIE 94; CIEDE 2000; CMC; BFD. Each of these small images took something from 10―30 minutes to render (on a 4-core), but the result is definitely worth it. Lifting the unique-color restriction would possibly yield even better results. (Note that as of this posting they're still rendering, but will come up.)
(Do you now see why I prefer ordered-dithering over floyd-steinberg?)
(Disclaimer: It's possible though, that my implementation of error-diffusion dithers is buggy.)
Appendix:
16 colors; RGB and CIE76 side-by-side. Gamma=2.0
Floyd-Steinberg:
Scolorq (gamma=1.0, RGB, default options; original shown at side to show how the dithered version is lighter due to wrong gamma):
4 colors (gamma=2.0, RGB and CIE76):
2 colors
4 colors, with less choices and more duplicates
2 colors, with less choices and more duplicates
Mega Man at 64 colors (minimal precombines to make it fast) at RGB,CIE76,CIEDE2000,CMC,BFD, gamma 2.2:
Same, but 4 colors:
Same, but 2 colors:
Fewer colors are preferred if you want to increase the chances of Mario Paint's predefined dithering brushes being used.
Note: When I say "64 colors" in this context, it means that for each pixel, a selection of 64 colors is formed from the 15-color palette. From that selection, the color is selected according to the dithering matrix. It does not mean that the image has 64 colors.
It would also be possible to create custom dithering brushes according to whichever dithering patterns are the most common ones in the source picture (assuming you still have enough one-pixel brushes to complete the image). I considered this option, but could not figure out how to achieve it optimally. This possibility, however, exists only when using ordered dithering.
EDIT: Oh, one more thing. I forgot. It is possible to mix ordered dithering and error diffusioning! It works by diffusing the error that remains after ordered-dithering, as opposed to diffusing the error that remains after nearest-color quantization.
From left to right: Yliluoma-2 dithering, Yliluoma-2 + Floyd-Steinberg, Floyd-Steinberg. Gamma = 2.2, colors=15, precombine=minimal.
The fourth image is of Nitsuja's version of Scolorq (where gamma=presumably 1.0) and the fifth is the original (resized+sharpened).
Same, with 4 colors:
Same, with 2 colors & minimum premixes:
-----------
Conclusions:
― Any proper dithering algorithm should operate on gamma-corrected RGB values rather than on linear RGB values. Failure to do this will produce an image that is obviously lighter in tone than the original. This error is most pronounced when the dithered colors differ significantly from each others.
― With static images, for certain images, ordered dithering can produce at least as good pictures as error-diffusion dithering, but for many images, it is vice versa.
― All error diffusion dithers, except for scolorq, seem to suffer from a bias towards gray values. Gray is apparently a good approximation for most colors. Therefore, where error diffusion is deemed appropriate over ordered dithering, I recommend using scolorq except where its lack of gamma correction is too obvious.
― Especially at low color candidate counts, ordered dithering produces distinguished repetive patterns, which may be very beneficial in optimizing the production of the picture when patterned brushes are available (such as in Mario Paint).
― From the six color difference formulae (ΔE), an euclidean distance in the RGB space appeared to be sufficient for most purposes. In a few cases, an euclidean distance in the LAB C*i*e* space (aka. CIE 76) produced better results. The more expensive formulae (CIE 94, CIEDE 2000, CMC, BFD) produced no advantage to justify their significantly more expensive calculation. (And indeed, BFD often seemed even to produce inferior results).
― For customized needs, it often is warranted to do extensive testing with different values for gamma, and color collection/mixing, in order to produce the image that is best for the particular need. Remember, that the eye is more sensitive to local differences in color/tone than to global differences of color/tone. Therefore, it is forgivable to tweak the colorscape of the entire image at once (such as by darkening, brightening, or colorizing it), if it helps bringing out a more accurate local contrast. Such testing was not done here.
― For animation, ordering dithering should always be used rather than error diffusion dithering. To prove the point, study these three examples (from DemonStrate's Portal Done Pro speedrun... rendered in Mario Paint palette.):
―― http://bisqwit.iki.fi/kala/snap/mp/pdp_fs.gif (1.3 MB, Floyd-Steinberg @gamma=2)
―― http://bisqwit.iki.fi/kala/snap/mp/pdp_sc.gif (1.5 MB, Scolorq @gamma=1)
―― http://bisqwit.iki.fi/kala/snap/mp/pdp_y2.gif (913 kB, Yliluoma-2 @gamma=2).
In sequence: Naruto; a car; Megaman; a manga drawing; Mario paint cover crisp and neat; Mario paint cover with more accurate colors.
Once it finishes an image, it immediately starts painting the next one over the previous one.
Here's my latest WIP. I don't remember what it exactly contains. IIRC the script got stuck somewhere.
http://dev.w3.fi/%7Ebisqwit/mariopaint-wip-unknown.smv
Oh, and about dithering: All these images are converted with Animmerger using Yliluoma-2 dithering at matrix size 16x16 with maximum 4 color combinations per pixel, maximum precombined colors, assumed gamma 2.0. The original was resized with lanczos filtering and sharpened minimally prior conversion. The dithering was rigged to produce patterns aligned to Mario Paint's brushes where possible.
