Lossy ASCII art compression
Java → CJam, score ≈4417.89
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import net.aditsu.cjam.CJam;
public class Compress {
protected static final char[] DIGITS = "0123456789ABCDEFGHIJK".toCharArray();
protected static final String CHARS = "@#+';:,.` ";
protected static final char[] CHR = CHARS.toCharArray();
private static class Img {
public final int rows;
public final int cols;
public final int[][] a;
public Img(final int rows, final int cols) {
this.rows = rows;
this.cols = cols;
a = new int[rows][cols];
}
public Img(final List<String> l) {
rows = l.size();
cols = l.get(0).length();
a = new int[rows][cols];
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
a[i][j] = CHARS.indexOf(l.get(i).charAt(j));
}
}
}
public static Img read(final Reader r) {
try {
final BufferedReader br = new BufferedReader(r);
final List<String> l = new ArrayList<>();
while (true) {
final String s = br.readLine();
if (s == null || s.isEmpty()) {
break;
}
l.add(s);
}
br.close();
return new Img(l);
}
catch (IOException e) {
throw new RuntimeException(e);
}
}
public static Img read(final File f) {
try {
return read(new FileReader(f));
}
catch (IOException e) {
throw new RuntimeException(e);
}
}
public Img scaleDown(final int fr, final int fc) {
final int r1 = (rows + fr - 1) / fr;
final int c1 = (cols + fc - 1) / fc;
final Img x = new Img(r1, c1);
final int[][] q = new int[r1][c1];
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
x.a[i / fr][j / fc] += a[i][j];
q[i / fr][j / fc]++;
}
}
for (int i = 0; i < r1; ++i) {
for (int j = 0; j < c1; ++j) {
x.a[i][j] /= q[i][j];
}
}
return x;
}
public Img scaleUp(final int fr, final int fc) {
final int r1 = rows * fr;
final int c1 = cols * fc;
final Img x = new Img(r1, c1);
for (int i = 0; i < r1; ++i) {
for (int j = 0; j < c1; ++j) {
x.a[i][j] = a[i / fr][j / fc];
}
}
return x;
}
public Img crop(final int r, final int c) {
if (r == rows && c == cols) {
return this;
}
final Img x = new Img(r, c);
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
x.a[i][j] = a[i][j];
}
}
return x;
}
public Img rescale(final int fr, final int fc) {
return scaleDown(fr, fc).scaleUp(fr, fc).crop(rows, cols);
}
public double quality(final Img x) {
if (x.rows != rows || x.cols != cols) {
throw new IllegalArgumentException();
}
double t = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
final int y = a[i][j] - x.a[i][j];
t += y * y;
}
}
t /= 81 * rows * cols;
t = 1 - Math.sqrt(t);
return Math.pow(t, 8);
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
sb.append(CHR[a[i][j]]);
}
sb.append('\n');
}
return sb.toString();
}
public Array toArray() {
final Array x = new Array(rows * cols);
int k = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
x.a[k++] = a[i][j];
}
}
return x;
}
public String compress(final double quality) {
int bi = 1;
int bj = 1;
int bs = rows * cols;
Img bx = this;
for (int i = 1; i < 3; ++i) {
for (int j = 1; j < 3; ++j) {
Img x = rescale(i, j);
if (quality(x) >= quality) {
x = scaleDown(i, j);
if (x.rows * x.cols < bs) {
bi = i;
bj = j;
bs = x.rows * x.cols;
bx = x;
}
}
}
}
Array a = bx.toArray();
int bf = 0;
for (int i = 1; i <= 20; ++i) {
final int t = a.rle11(i).n;
if (t < bs) {
bs = t;
bf = i;
}
}
int b = 10;
if (bf > 0) {
b = 11;
a = a.rle11(bf);
}
String s = null;
for (int i = 92; i < 97; ++i) {
for (char c = ' '; c < '$'; ++c) {
final String t = a.cjamBase(b, i, c);
boolean ok = true;
for (int j = 0; j < t.length(); ++j) {
if (t.charAt(j) > '~') {
ok = false;
break;
}
}
if (!ok) {
continue;
}
if (s == null || t.length() < s.length()) {
s = t;
}
}
}
if (bf > 0) {
s += "{(_A={;()";
if (bf > 1) {
s += DIGITS[bf] + "*";
}
s += "\\(a@*}&\\}h]e_";
}
if (bi * bj == 1) {
return s + '"' + CHARS + "\"f=" + cols + "/N*";
}
s += bx.cols + "/";
if (bi > 1) {
s += bi + "e*";
if (rows % 2 == 1) {
s += "W<";
}
}
if (bj > 1) {
s += bj + "fe*";
if (cols % 2 == 1) {
s += "Wf<";
}
}
return s + '"' + CHARS + "\"ff=N*";
}
public void verify(final String s, final double quality) {
final String t = CJam.run(s, "");
final Img x = read(new StringReader(t));
final double q = quality(x);
if (q < quality) {
throw new RuntimeException(q + " < " + quality);
}
// System.out.println(q + " >= " + quality);
}
}
private static class Array {
public final int[] a;
public final int n;
public Array(final int n) {
this.n = n;
a = new int[n];
}
public Array(final int[] a) {
this.a = a;
n = a.length;
}
public String join() {
final StringBuilder sb = new StringBuilder();
for (int x : a) {
sb.append(x).append(' ');
}
sb.setLength(sb.length() - 1);
return sb.toString();
}
// public String cjamStr() {
// final StringBuilder sb = new StringBuilder("\"");
// for (int x : a) {
// sb.append(DIGITS[x]);
// }
// sb.append("\":~");
// return sb.toString();
// }
public String cjamBase(final int m, final int b, final char c) {
final boolean zero = a[0] == 0;
String s = join();
if (zero) {
s = "1 " + s;
}
s = CJam.run("q~]" + m + "b" + b + "b'" + c + "f+`", s);
s += "'" + c + "fm" + b + "b" + DIGITS[m] + "b";
if (zero) {
s += "1>";
}
return s;
}
public Array rle11(final int f) {
final int[] b = new int[n];
int m = 0;
int x = -1;
int k = 0;
for (int i = 0; i <= n; ++i) {
final int t = i == n ? -2 : a[i];
if (t == x && m < 11 * f) {
m++;
}
else {
if (m >= f && m > 3) {
b[k++] = 10;
b[k++] = m / f - 1;
b[k++] = x;
for (int j = 0; j < m % f; ++j) {
b[k++] = x;
}
}
else {
for (int j = 0; j < m; ++j) {
b[k++] = x;
}
}
m = 1;
x = t;
}
}
return new Array(Arrays.copyOf(b, k));
}
}
private static void score() {
double p = 1;
for (int i = 1; i < 6; ++i) {
final File f = new File("image" + i + ".txt");
final Img img = Img.read(f);
final int n = (int) f.length();
for (int j = 5; j < 10; ++j) {
final double q = j / 10.0;
final String s = img.compress(q);
System.out.println(f.getName() + ", " + q + ": " + n + " -> " + s.length());
img.verify(s, q);
p *= s.length();
}
}
System.out.println(Math.pow(p, 1 / 25.0));
}
public static void main(final String... args) {
if (args.length != 2) {
score();
return;
}
final String fname = args[0];
final double quality = Double.parseDouble(args[1]);
try {
final Img img = Img.read(new File(fname));
final String s = img.compress(quality);
img.verify(s, quality);
final FileWriter fw = new FileWriter(fname + ".cjam");
fw.write(s);
fw.close();
}
catch (IOException e) {
throw new RuntimeException();
}
}
}
Requires the CJam jar in the classpath. If you give it 2 command line arguments (file name and quality), it appends ".cjam" to the file name and writes the compressed image there. Otherwise it calculates its score on the 5 test images, which are assumed to be in the current directory. The program also verifies every compressed image automatically. You may want to double-check the score calculation in case there's any discrepancy.
The techniques used (so far) are: scaling to half (horizontally, vertically or both) if it doesn't reduce the quality too much, a custom-coded RLE, and base conversion to pack more data into each character while remaining in the printable ASCII range.
Python 3.5 (main and output) (currently noncompeting)
Happy Birthday, Challenge! Here's your present: an answer!
EDIT: Converted output to python code, improved compression rate (slightly)
EDIT2: Made it print raw when size is 1. Improved score, but score needs to be calculated again.
EDIT3: @Dennis pointed out that I still haev bugs to fix, so I marked the answer as noncompeting
Code:
import sys
LIST = [' ','`','.',',',':',';',"'",'+','#','@']
def charxel_to_brightness(charxel):
return LIST.index(charxel)
def brightness_to_charxel(bright):
return LIST[bright]
def image_to_brightness(imagetext):
return [list(map(charxel_to_brightness,line)) for line in imagetext.split("\n")]
def brightness_to_image(brightarray):
return '\n'.join([''.join(map(brightness_to_charxel,line)) for line in brightarray])
def split_into_parts(lst,size):
return [lst[x:x+size] for x in range(0, len(lst), size)]
def gen_updown(startxel,endxel,size):
return [[int((size-r)*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]
def gen_leftright(startxel,endxel,size):
return [[int((size-c)*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]
def gen_tlbr(startxel,endxel,size):
return [[int((2*size-r-c)/2*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]
def gen_bltr(startxel,endxel,size):
return [[int((size-r+c)/2*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]
def gen_block(code,startxel,endxel,size):
if code==0:return gen_updown(startxel,endxel,size)
if code==1:return gen_leftright(startxel,endxel,size)
if code==2:return gen_bltr(startxel,endxel,size)
if code==3:return gen_tlbr(startxel,endxel,size)
def vars_to_data(code,startxel,endxel):
acc=endxel
acc+=startxel<<4
acc+=code<<8
return acc
def data_to_vars(data):
code=data>>8
startxel=(data>>4)&15
endxel=data&15
return code,startxel,endxel
def split_into_squares(imgarray,size):
rows = split_into_parts(imgarray,size)
allsquares = []
for rowblock in rows:
splitrows = []
for row in rowblock:
row = split_into_parts(row,size)
splitrows.append(row)
rowdict = []
for row in splitrows:
for x in range(len(row)):
if len(rowdict)<=x:
rowdict.append([])
rowdict[x].append(row[x])
allsquares.append(rowdict)
return allsquares
def calc_quality(imgarray,comparray):
acc=0
for row in range(len(imgarray)):
for col in range(len(imgarray[row])):
acc+=pow(imgarray[row][col]-comparray[row][col],2)
return (1-(acc/81.0/sum([len(row) for row in imgarray]))**.5)**8
def fuse_squares(squarray):
output=[]
counter=0
scounter=0
sqrow=0
while sqrow<len(squarray):
if scounter<len(squarray[sqrow][0]):
output.append([])
for square in squarray[sqrow]:
output[counter].extend(square[scounter])
scounter+=1
counter+=1
else:
scounter=0
sqrow+=1
return output
def main_calc(imgarray,threshold):
imgarray = image_to_brightness(imgarray)
size = 9
quality = 0
compimg=[]
datarray=[]
testdata = [vars_to_data(c,s,e) for c in range(4) for s in range(10) for e in range(10)]
while quality<threshold:
squares = split_into_squares(imgarray,size)
compimg = []
datarray = []
testblock = [gen_block(c,s,e,size) for c in range(4) for s in range(10) for e in range(10)]
for row in squares:
comprow = []
datrow=[]
for square in row:
quality_values = [calc_quality(square,block) for block in testblock]
best_quality = quality_values.index(max(quality_values))
comprow.append(testblock[best_quality])
datrow.append(testdata[best_quality])
compimg.append(comprow)
datarray.append(datrow)
compimg = fuse_squares(compimg)
quality = calc_quality(imgarray,compimg)
print("Size:{} Quality:{}".format(size,quality))
size-=1
return brightness_to_image(compimg),datarray,size+1
template = '''def s(d,s,e,z):
x=range(z)
return d<1 and[[int((z-r)*(e-s)/z+s)for c in x]for r in x]or d==1 and[[int((z-c)*(e-s)/z+s)for c in x]for r in x]or d==2 and[[int((2*z-r-c)/2*(e-s)/z+s)for c in x]for r in x]or d>2 and[[int((z-r+c)/2*(e-s)/z+s)for c in x] for r in x]
i=lambda a:'\\n'.join([''.join(map(lambda r:" `.,:;'+#@"[r],l))for l in a])
def f(a):
o=[];c=0;s=0;r=0
while r<len(a):
if s<len(a[r][0]):
o.append([])
for q in a[r]:
o[c].extend(q[s])
s+=1;c+=1
else:
s=0;r+=1
return o
t={};z={}
print(i(f([[s(D>>8,(D>>4)&15,D&15,z)for D in R]for R in t])))'''
template_size_1 = '''print("""{}""")'''
def main(filename,threshold):
print(filename+" "+str(threshold))
file = open(filename,'r')
compimg,datarray,size = main_calc(file.read(),threshold)
file.close()
textoutput = open(filename.split(".")[0]+"-"+str(threshold*100)+".txt",'w')
textoutput.write(compimg)
textoutput.close()
compoutput = open(filename.split(".")[0]+"-"+str(threshold*100)+".py",'w')
datarray = str(datarray).replace(" ","")
code = ""
if size==1:
code = template_size_1.format(compimg)
else:
code= template.format(datarray,str(size))
compoutput.write(code)
compoutput.close()
print("done")
if __name__ == "__main__":
main(sys.argv[1],float(sys.argv[2]))
This answer could use a lot of improvements, so I'll probably be working on it more over the weekend.
How this works:
- Divide image into blocks of size
size. - Find best matching block
- Blocks can have gradient now!
- Calculate quality (according to formula) for entire image.
- If correct, write zipped image to file.
- Otherwise, decrement
sizeand try again.
This algorithm works well for low quality (0.5, 0.6) but doesn't work too well on the higher quality images (actually inflates). It is also really slow.
Here I have all the generated files, so you won't have to re-generate them again.