from __future__ import division
from __future__ import print_function
# Read PNM file, pick colors that can be represented by Micropal, print
# out GIMP palette with those colors.
import sys
class Image(object):
def __init__(self, w, h, data):
self.width = w
self.height = h
self.data = data
def getpixel(self, x, y):
base = (y * self.width + x) * 3
return (data[base], data[base + 1], data[base + 2])
def read_pnm(f):
line = f.readline().rstrip()
if line != 'P3':
raise Exception('Need P3 file, got %s' % (line,))
def read_non_comment():
while True:
line = f.readline()
if len(line) > 0 and line[0] != '#':
return line
width, height = map(int, read_non_comment().split())
scale = int(read_non_comment())
def get_pieces():
for line in f:
for piece in line.split():
if scale == 255:
yield int(piece)
else:
yield int(float(piece) / scale * 256)
size = width * height * 3
data = [0] * size
inator = get_pieces()
for i in range(size):
data[i] = inator.next()
return Image(width, height, data)
def simple_colormap():
# A simple colormap which does not consider the image data at all.
colormap = []
for b in range(4):
for g in range(8):
for r in range(8):
mr = r & 1
mg = g & 1
mb = b
colormap.append(((mr << 7) | (r << 4),
(mg << 7) | (g << 4),
(mb << 6) | (b << 4)))
return colormap
def colormap_from_image(img):
# Micropal provides red, green, blue (RGB) colors with 4 bits for each
# of the components. However, the bits are not freely assignable.
#
# The bits are divided into major bits and minor bits. The major
# bits are the most significant bit of red, the most significant
# bit of green, and the most significant 2 bits of blue. The minor
# bits are the 3 least significant bits of red and green and the 2
# least significant bits of blue.
#
# Color is then encoded as follows:
#
# rrrgggbb rgbb
# -------- ----
# minor major
#
# where rrrgggbb is the color number, and rgbb is stored in a lookup
# table indexed by color number.
#
# Every combination of minor bits always exists in the palette.
# For every combination of minor bits, exactly one combination of
# major bits exists in the palette.
#
# The task of this function, then, is to assign exactly one major
# color to every minor color. The better a job this function does,
# the closer to the original the image will look after conversion
# to the resulting colormap.
#
# Algorithm
#
# Getting an optimal assignment of minor colors to major colors is an
# Interesting Problem. The algorithm used here is not guaranteed to
# be optimal, but it runs in a reasonable amount of time and produces
# good results on a number of images I have tried it on.
#
# We assign a value to each of the minor colors based on how many pixels
# use that minor color.
#
# We assign a budget to each major color based on how many pixels use that
# major color.
#
# Then we auction off the minor colors, in an order that is deterministic
# but spread out through the color space. For each minor color, all
# major colors that want it place a bid, and the highest bidder wins.
#
# The function that determines the bid is currently relatively simple.
# One way it might be improved is by considering nearby colors and
# whether or not they are still available. For example, we may be willing
# to bid more on a minor color if we wanted a neighboring minor color,
# but lost the bid.
#
# It may also be beneficial to allow trading colors after the initial
# auction.
# First, we create some lookup tables.
#
# Bits are arranged from least significant to most significant.
# rgb is the 12-bit red, green, blue number: rrrrggggbbb.
# maj is the major color number. It consists of bits r...g...bb..
# c is the minor color number. It consists of bits .rrr.ggg..bb
#
# count[maj][c] is the number of occurrences of each color in the image.
# major[maj] is the budget for each major color. Initially, this is the
# number of occurrences of the major color in the image.
count = []
for i in range(16):
count.append([0] * 256)
major = [0] * 16
for color in colors_in_image(img):
rgb = nearest_rrrrggggbbbb(color)
maj = ((rgb & 8) >> 3) | ((rgb & 128) >> 6) | ((rgb & 3072) >> 8)
c = (rgb & 7) | ((rgb & 0x70) >> 1) | ((rgb & 0x300) >> 2)
major[maj] += 1
count[maj][c] += 1
def bid(m, c):
if major[m] < 1 or count[m][c] == 0:
return 0
total = 0
for i in range(256):
total += count[m][i]
return count[m][c] * major[m] / total
# We cycle through the colors so that the next color to be auctioned is never
# next to the previous color that was auctioned.
colormap = [(0, 0, 0)] * 256
c = 54
for i in range(256):
# 61 and 256 are relative primes, which guarantees that we will visit every
# minor color in 256 steps.
c = (c + 61) & 0xff
best = (0, 0)
for m in range(16):
b = bid(m, c)
if b > best[0]:
best = (b, m)
colormap[c] = (((best[1] & 1) << 7) | ((c & 7) << 4),
((best[1] & 2) << 6) | ((c & 0x38) << 1),
((best[1] & 0x0c) << 4) | ((c & 0xc0) >> 2))
return colormap
def colors_in_image(img):
for i in range(0, len(img.data), 3):
yield (img.data[i], img.data[i + 1], img.data[i + 2])
def nearest_rrrrggggbbbb(rgb):
return (to4bit(rgb[0]) |
(to4bit(rgb[1]) << 4) |
(to4bit(rgb[2]) << 8))
def to4bit(c):
c = (c + 7) // 16
if c >= 16:
return 15
else:
return c
def main():
img = read_pnm(sys.stdin)
colormap = colormap_from_image(img)
print('GIMP Palette')
print('Name: test')
print('Columns: 16')
for c in colormap:
print('%s %s %s' % c)
if __name__ == '__main__':
main()