- What the converter does?
- Why the converter works so slowly?
- But why the converter works so slow, if it works so fast?
- Why the converter generates different output each time?
- Why the converter is not able to convert even simple pictures from other 8 bit computers?
- But the picture I have can be converted 1 to 1!
- But the picture I have is low-color and trivial. The converter should give a results in seconds!
- Why don't you use some other algorithm like genetic algorithm?
- Can you write a version that will use multiple threads, CUDA, open-CL, OpenMP, LibGlass, Cloud computing etc.?
- Why the converter does not use character mode to get one extra color? Or interlace? Or hires?
- What are the -src , -dst and output pictures?
- If the best solution can’t ever be reached then how long should I wait?
- Why some blue colors get violet during conversion?
- Why the knoll dithering is so slow?
- Why to use more solutions with /s parameter? How many should I use?
- Why the converter produces outputs with banding and visible horizontal lines?
- How many different colors in line can we have?
- How to report bugs?
The converter tries to solve some complex optimization problem: to write a Kernel Program that executed by [6502 CPU] (http://en.wikipedia.org/wiki/MOS_Technology_6502) and ANTIC will show the best picture possible on 8bit Atari computer.
Well... It does not work slowly. It works fast considering the problem complexity. Straight brute-force algorithm to find the optimal solution would require to test about 805^4080 combinations. The code is already quite optimized. The current version works ~1000 times faster than the first version.
Because the problem is not trivial. All proposed and tested simple ideas (like assign the most common colors to playfield colors and the rest to the sprites) give very bad results comparing to what can be achieved. Those simple ideas are already implemented in the converter as initialization and optimization heuristics.
To understand the problem complexity you need to understand how the 8Bit Atari works, how it creates the screen, how many cycles are used by 6502, how many color and general purpose registers are available, how the sprites priority works, how the sprites multiplication works, how many color cycles ANTIC steals etc.
The problem is probably as hard as some NP-complete problems and the size of the problem is big here.
The Late Acceptance Hill Climbing algorithm used in the converter is nondeterministic and does not guarantee to find the optimal solution. Therefore it is better to run it a few times and to choose the output you like best. Why it is not deterministic? Because the search space is huge and in most of the cases it is not possible to tell in reasonable time what is the best solution. Therefore algorithm is able to search only through some part of the search space and each time you run the algorithm it tries a different area.
All 8 bit platforms had different architectures and different graphics capabilities. What is easy to show on one computer can be not possible to show on the Atari.
Are you really, really sure that this is possible? Even simple pictures can have color settings in lines that are not possible to be displayed on the Atari.
Low amount of colors does not mean that it is trivial to set them. The CPU and ANTIC timing is complex and there are only 3 CPU registers the can be used to set sprite and color registers. Are you really sure that conversion is trivial or even possible? If yes, then I have a bad news: RastaConverter works in a nondeterministic way that was explained before. It is not created to brute-force simple pictures, because they rarely happen in reality and "so simple pictures" are usually not that simple. There is however a special case of pictures with less than 5 colors handled and the output should be given instantly.
Why don't you use some other algorithm like genetic algorithm?
I've tested some other optimization techniques (Tabu Search, Genetic Algorithm, Beam Search) and the Late Acceptance Hill Climbing outperformed others.
Can you write a version that will use multiple threads, CUDA, open-CL, OpenMP, LibGlass, Cloud computing etc.?
Yes, I can, but I have probably more interesting things to do ;-) The project is open source, so feel free to contribute.
Because it is not implemented. Feel free to contribute, but you should know in advance that proper implementation will not be easy.
- The –src picture is the input picture resized to 160*height pixels using the chosen resize filter (/filter parameter).
- The –dst picture is the picture in Atari palette with dithering applied. This is the goal for the optimization process and this goal in most of the cases can never be reached! If I it would be known what is the best possible output then the whole optimization would not be needed.
- The output picture is the picture telling how the screen will look like when executed on the 8bit Atari.
As long as you want :-) I usually stop the conversion when I don’t see any visible improvements for a longer time. Sometimes it takes 2 million iterations, sometimes even 500 million – depending on a picture.
Example
| Input | Destination picture |
|
|
This is because of the default color distance metric CIEDE2000. It is chosen to be default, because Atari palette does not have linear spread over color space and with other distance metrics (YUV or Euclidian) too many pictures get converted to gray. If your picture gets violet instead of blue then use a different color distance for the preprocess f.e. /predistance=yuv:
Basically if a picture is high-contrast one or colors are well saturated, then use /predistance=yuv.
Look how the colors get converted to Atari palette with different color distance metrics:
Original file
CIEDE2000:
Euclidian RGB:
YUV:
CIE94:
Why the knoll dithering is so slow?
It is slow, because the algorithm is slow :-) It gets much slower with CIEDE2000 distance metric, which is complex to calculate.
With /s=1 (default) the algorithm used is Hill Climbing, which provides result fast, but the result is usually far from optimal. With /s greater than 1 the Late Acceptance Hill Climbing is used which is less prone to stuck in local maximum. Basically the more solutions you will use, the better possible output you can reach:
Reasonable value for /s is 1000 to 10000.
There are a few reasons for that:
- Amount of available colors to be used at one time is very low on Atari and colors cannot be set everywhere whey they are needed because of CPU and ANTIC timing. The converter sometimes "reserves" a color for further usage or places a sprites in previous line, where it is not really needed. All of this is kept when it may improve global picture quality.
- The sprites width used is quadruple to cover more area. RastaConverter does not support sprites with lower width. Because of sprites priority it is not always possible to cover part of a sprite with the best color.
- Best areas to cover with more details are not the same for a human eye and for a computer. Computer works on the color distance while humans prefer to see more details for example on faces, small but important objects, center of a picture, objects in the first plan etc. Use the /details mask to choose where do you want to have details.
- The algorithm stucked in local optimum and is not able to find a better solution. Rerun it again or try larger number of solutions with /s parameter.
RastaConverter does midline changes of colour/sprite registers. You can have up to 7 changes in line. With initial set of colours (4 playfield, 4 players) you can have up to 15 colours in line. The number is not constant and depends on a picture (colors in previous and next lines, position of colors on the screen). Usually you can have 5 to 13 colours in line. Therefore reducing number of colors in lines f.e. to 8 would work only for some pictures, for others giving much worse output.
Attach all the input and output files to the bug report. Without that your report will be useless.