It is currently Tue Jul 17, 2018 5:06 am

 All times are UTC - 7 hours

 Page 1 of 2 [ 20 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 4:35 pm

Joined: Wed May 19, 2010 6:12 pm
Posts: 2712
Start with a random color palette. Convert the picture to all 4 palettes. Then chose the closest pallette for each attribute block. Then for each color, calculate the average color and round it to the nearest NES color. Then repeat the process again until it's as accurate as possible.

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 4:48 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2143
Location: DIGDUG
Sounds good except for the "start with a random palette". You would have 2.2 x 10^21 possible palettes to choose from. Unless I'm misunderstanding you.

Edit, or maybe 4 x 10^21. I'm counting 52 unique colors and 13 possible palette colors.

_________________
nesdoug.com -- blog/tutorial on programming for the NES

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 5:15 pm

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7307
Location: Seattle
I haven't gotten around to writing this, but I've been contemplating something like
1- Quantize original image to 54 available colors
2- Quantize that image down to 13 colors
3- Requantize original directly to target 13 colors, to reduce loss
Then:
4- Histogram of entire color-reduced picture from step #3. Use most prevalent ("plurality") color is shared background color
5- For each attribute zone (of whatever dimensions; 16x16 down to 8x1), build a histogram of the colors in that zone; ignoring the background color
6- Take the four most prevalent palettes per the histograms
7- If fewer than 13 colors are present, restart at step #3 with the newer shorter palette

Using most frequent colors here will lose regional detail, a different selector could be chosen for that, too...

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 5:26 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20255
Location: NE Indiana, USA (NTSC)
psycopathicteen wrote:
Start with a random color palette. Convert the picture to all 4 palettes. Then chose the closest pallette for each attribute block. Then for each color, calculate the average color and round it to the nearest NES color. Then repeat the process again until it's as accurate as possible.

This is similar to the Linde-Buzo-Gray algorithm or k-means clustering.

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 5:26 pm

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10591
Location: Rio de Janeiro - Brazil
Didn't we just have this conversation?

Anyway, it's hard to judge the effectiveness of an algorithm without images showing the result. Also, I don't think your description is detailed enough. Here are the things I don't understand:

1- "start with a random color palette": Why a random palette? How many colors does this palette have and where do they come from?

2- "convert the picture to all 4 palettes": Convert the same image to 4 different palettes? Which palettes are these?

3- "Then chose the closest pallette for each attribute block": from the 4 palettes you mentioned before? Do you mean picking the most accurate 16x16-pixel blocks from the 4 different images?

4- "Then for each color, calculate the average color": I don't understand what I'm supposed to average, because you seem to have mentioned 1 input and 1 output.

5- "Then repeat the process": Didn't the previous steps already result in a complete NES image? I don't see how applying this recursively could make things better.

Please explain what you mean in greater detail, and provide a sample picture if possible.

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 5:26 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2143
Location: DIGDUG
How about this approach...

1.Narrow the original to the 8 most common hues, ignoring their brightness.
2.construct a pallette, each has black, white, and 2 unique colors.
3.divide the picture into 16x16 chunks, decide which palette it fits best.
4.index each 16x16 chunk, dithering with black, white, and those 2 colors.
5.reconstruct the image, and attribute table.

_________________
nesdoug.com -- blog/tutorial on programming for the NES

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 5:52 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2143
Location: DIGDUG
Quote:
Didn't we just have this conversation?

The old conversation was restricted to 1 pallette (4 color)... The new one seems to be about using all 4 palettes (13 colors).

_________________
nesdoug.com -- blog/tutorial on programming for the NES

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 6:02 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20255
Location: NE Indiana, USA (NTSC)
If anyone decides to implement this, as an alternative to a random palette, I wonder whether the following might converge to something reasonable faster or more reliably.

0f001020 0f112120 0f172720 0f1a2a20
Gray ramp, teals (for sky), oranges (for skin), and greens (for plants)

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 6:55 pm

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10591
Location: Rio de Janeiro - Brazil
dougeff wrote:
The old conversation was restricted to 1 pallette (4 color)

Oh, I hadn't realized that. My contributions to that thread certainly didn't take this into consideration. Sorry for that!

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Sun Aug 23, 2015 7:09 pm

Joined: Wed May 19, 2010 6:12 pm
Posts: 2712
tokumaru wrote:
Didn't we just have this conversation?

Anyway, it's hard to judge the effectiveness of an algorithm without images showing the result. Also, I don't think your description is detailed enough. Here are the things I don't understand:

1- "start with a random color palette": Why a random palette? How many colors does this palette have and where do they come from?

2- "convert the picture to all 4 palettes": Convert the same image to 4 different palettes? Which palettes are these?

3- "Then chose the closest pallette for each attribute block": from the 4 palettes you mentioned before? Do you mean picking the most accurate 16x16-pixel blocks from the 4 different images?

4- "Then for each color, calculate the average color": I don't understand what I'm supposed to average, because you seem to have mentioned 1 input and 1 output.

5- "Then repeat the process": Didn't the previous steps already result in a complete NES image? I don't see how applying this recursively could make things better.

Please explain what you mean in greater detail, and provide a sample picture if possible.

In other words, it will keep adjusting both the image and palette until the image no longer changes with each iteration.

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Wed Aug 26, 2015 7:00 pm

Joined: Sat Jul 25, 2015 11:53 am
Posts: 12
rgb121 is the way to go.
MODS: Please lock this thread.

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Thu Aug 27, 2015 7:02 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20255
Location: NE Indiana, USA (NTSC)
The RGB121 technique works fine for stills but not so well if you need more than 256 unique tiles without a huge CHR ROM or you want to use CPU time for something other than the raster effect that powers it. If I weren't working on a paid project right now, I might try implementing this LBG method.

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Thu Aug 27, 2015 7:45 am

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10591
Location: Rio de Janeiro - Brazil
The thing is, NES graphics are very primitive, and completely unsuitable for photographic images. No matter how much you try to optimize patterns and palettes, you're still stuck with a certain number of tiles (depending on the mapper), 16x16 or 8x8 (also depending on the mapper) attribute areas using 4 palettes of 3 colors + 1 shared color out of a very limited master palette.

RGB121 looks good because it bends the rules. It tricks the system into displaying a picture that deviates from the normal specs, causing colors to blend in a different way. If you're not bending the rules, I don't see how an algorithm would do better than an artist doing the conversion manually using Photoshop/GIMP. Algorithms will certainly give results faster, but hardly better than a good artist, so I don't think we're gonna see any groundbreaking images coming out any algorithm that doesn't bend the rules of the display. Yes, raster effects often steal 100% of the CPU time, but you hardly need that time anyway when you're showing a full screen still image.

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Thu Aug 27, 2015 9:51 am

Joined: Fri May 08, 2015 7:17 pm
Posts: 2143
Location: DIGDUG
I don't expect to see full color pictures, but anime style flat images and reduced color images could be a possibility. There's a printing concept called 'duotone' that might work and produce nice images.

https://en.m.wikipedia.org/wiki/Duotone

Edit: and when people tell me something can't be done, it just encourages me to think of a way to do it. Maybe that's a character flaw in me, I don't know.

_________________
nesdoug.com -- blog/tutorial on programming for the NES

Top

 Post subject: Re: Possible algorithm for converting photos to NESPosted: Thu Aug 27, 2015 10:03 am

Joined: Fri May 08, 2015 7:17 pm
Posts: 2143
Location: DIGDUG
Maybe I should explain how to do a duotone, since the Wikipedia page doesn't...

First you turn the image into a black and white. Then instead of shades of gray in the palette, you use shades of pink (faces) or shades of blue (other things).

_________________
nesdoug.com -- blog/tutorial on programming for the NES

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 20 posts ] Go to page 1, 2  Next

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki
Powered by phpBB® Forum Software © phpBB Group