manual.ps

a small program by Yuval Fisher that has gone a long way to revealing some of the secrets of fracal

03FE00FFFE1C01FF0007FE3001FF8003FE6000FF8003FEE000FFC003FEC000FFC003FF8000FFC0
03FF8000FFC003FF8000FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF00
00FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC0
03FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF00
00FFC003FF0000FFC003FF0000FFC003FF0000FFC003FF0000FFC0FFFFFC3FFFFFFFFFFC3FFFFF
FFFFFC3FFFFFFFFFFC3FFFFF30267CA537>110 D<00FF01FF8000FFFF0FFFF000FFFF3FFFFC00
FFFFFE03FF00FFFFF000FF8003FFC0007FC003FF80003FE003FF00003FF003FF00001FF803FF00
001FFC03FF00000FFC03FF00000FFE03FF00000FFE03FF000007FE03FF000007FF03FF000007FF
03FF000007FF03FF000007FF03FF000007FF03FF000007FF03FF000007FF03FF000007FF03FF00
0007FF03FF000007FE03FF000007FE03FF00000FFE03FF00000FFC03FF00000FFC03FF00001FF8
03FF00001FF803FF00003FF003FF80003FE003FFC0007FC003FFF001FF8003FFFC07FF0003FF3F
FFFC0003FF0FFFF00003FF01FF000003FF0000000003FF0000000003FF0000000003FF00000000
03FF0000000003FF0000000003FF0000000003FF0000000003FF0000000003FF0000000003FF00
00000003FF0000000003FF00000000FFFFFC000000FFFFFC000000FFFFFC000000FFFFFC000000
30377DA537>112 D<FFFFF007FFFCFFFFF007FFFCFFFFF007FFFCFFFFF007FFFC01FF8000FC00
00FFC000F80000FFE001F000007FF003E000003FF007C000001FF80FC000000FFC1F8000000FFE
1F00000007FF3E00000003FFFC00000001FFF800000000FFF0000000007FE0000000007FF00000
00003FF8000000001FF8000000001FFC000000003FFE000000007FFF00000000FBFF80000001F9
FF80000003F0FFC0000003E07FE0000007C07FF000000F803FF800001F001FFC00003E000FFC00
007C0007FE0000FC0003FF0001FC0003FF80FFFF801FFFFEFFFF801FFFFEFFFF801FFFFEFFFF80
1FFFFE2F267EA534>120 D E end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300
TeXDict begin

%%EndSetup
%%Page: 1 1
bop 450 583 a Fj(App)s(endix)34 b(A)450 791 y Fi(Sample)41
b(Co)s(de)450 1007 y Fh(Y.)14 b(Fisher)450 1057 y(Institudte)h(for)f(Nonline)
n(ar)h(Scienc)n(e)450 1107 y(University)f(of)h(California,)e(San)j(Die)n(go)
450 1157 y(L)n(a)f(Jol)r(la,)f(CA)h(92093-0402)450 1207 y(E-mail:)j
(y\014sher@ucsd.e)n(du)512 1482 y Fg(The)11 b(follo)o(wing)d(pages)i(are)h
(excerpted)i(from)8 b Ff(Fra)o(ct)m(al)k(Compression:)p Fe(Theory)g(and)f
(Ap-)450 1532 y(plication)k(to)j(Digital)e(Images)p Fg(,)g(b)o(y)g(Y)m(uv)n
(al)f(Fisher,)i(published)g(b)o(y)f(Springer)h(V)m(erlag)e(\(Ma)o(y)450
1582 y(1994\).)450 1720 y Fd(A.1)69 b(The)23 b(Enc)f(Man)n(ual)i(P)n(age)450
1811 y Ff(Name)554 1878 y Fg(enc)12 b(-)f(use)h(a)f(quadtree-partition)g
(based)h(fractal)e(metho)q(d)h(to)g(enco)q(de)h(a)f(\014le)g(of)g(consecutiv)
o(e)554 1928 y(b)o(yte)j(data)g(represen)o(ting)h(an)f(image.)450
2012 y Ff(Synopsis)554 2105 y Fe(enc)20 b Fg([-t)28 b Fh(toler)n(anc)n(e)p
Fg(])13 b([-m)27 b Fh(minimum)15 b(r)n(e)n(cursion)f(depth)p
Fg(])645 2154 y([-M)28 b Fh(maximum)15 b(r)n(e)n(cursion)g(depth)p
Fg(])f([-S)28 b Fh(strip)n(chars)p Fg(])12 b([-w)28 b Fh(width)p
Fg(])13 b([-h)28 b Fh(height)p Fg(])645 2204 y([-d)g Fh(domain)16
b(p)n(o)n(ol)f(step)g(size)p Fg(])e([-D)27 b Fh(domain)16 b(p)n(o)n(ol)f(typ)
n(e)g(\(0,)g(1,)f(2\))p Fg(])g([-s)28 b Fh(sc)n(aling)15 b(bits)p
Fg(])645 2254 y([-o)28 b Fh(o\013set)15 b(bits)p Fg(])e([-N)28
b Fh(maximum)16 b(sc)n(ale)p Fg(])d([-HepfF])g([)h Fh(input)i(\014le)e(name)p
Fg(])645 2304 y([)g Fh(output\014lename)p Fg(])450 2396 y Ff(Description)554
2463 y Fh(Enc)f Fg(enco)q(des)i(a)d(\014le)h(of)f(sequen)o(tial)h(b)o(yte)g
(v)n(alues)f(whic)o(h)h(represen)o(t)i(an)e(image)d(in)j(ro)o(w)f(\014rst)554
2513 y(order.)17 b(V)m(arious)9 b(\015ags)h(can)f(alter)h(the)g(time)e(and)i
(\014delit)o(y)f(of)g(the)h(resulting)g(enco)q(ding,)g(whic)o(h)1220
2618 y(1)p eop
%%Page: 2 2
bop 150 138 a Fg(2)1040 b Fc(App)q(endix)14 b(A.)27 b(Sample)13
b(Co)q(de)p 150 163 1560 1 v 254 271 a Fg(can)g(b)q(e)h(deco)q(ded)g(with)f
(the)h(program)d Fh(de)n(c)p Fg(.)18 b(All)13 b(input)f(\015ags)h(are)h
(optional,)d(including)h(the)254 321 y(input)17 b(and)h(output)g(\014le)g
(names.)29 b(Output)19 b(\014les)f(t)o(ypically)e(ha)o(v)o(e)i(an)g
(extension)g(of)f(.trn,)254 371 y(to)f(denote)g(a)g Fh(tr)n(ansform)f
Fg(\014le)h(con)o(taining)f(the)h(co)q(e\016cien)o(ts)i(of)d(the)i
(partitioned)e(iterated)254 421 y(transform)d(whic)o(h)i(enco)q(des)i(the)e
(image.)254 490 y(Ranges)d(are)g(selected)i(in)e(the)h(image)d(using)i(a)g
(recursiv)o(e)i(quadtree)f(partitioning)e(of)g(square)254 539
y(sub-images)16 b(of)g(the)i(input)f(image.)26 b(F)m(or)16
b(eac)o(h)i(range,)g(a)f(domain)d(sub-image)i(is)h(sough)o(t)254
589 y(whic)o(h)i(is)f(t)o(wice)h(the)h(range)f(side)g(length.)33
b(If)19 b(a)f(domain)f(is)h(not)h(found)g(whic)o(h)f(can)h(b)q(e)254
639 y(mapp)q(ed)13 b(on)o(to)h(a)g(range)h(with)f(rms)f(error)i(less)g(than)g
(the)f(tolerance)i(set)f(with)f(the)h(-t)f(\015ag,)254 689
y(then)j(the)h(range)f(is)g(partitioned)g(in)o(to)f(four)h(quadran)o(ts,)g
(and)g(the)h(pro)q(cess)h(is)e(rep)q(eated.)254 739 y(The)d(maxim)n(um)c(and)
j(minim)o(um)c(recursion)15 b(depth)g(are)f(set)h(using)e(the)i(-m)d(and)i
(-M)g(\015ags,)254 788 y(and)e(these)i(refer)g(to)e(the)h(maxima)o(l)c
(square)14 b(sub-image.)i(F)m(or)c(example,)f(a)h(256)7 b Fb(\002)g
Fg(256)k(pixel)254 838 y(image)e(with)i(-m)e(4)i(and)f(-M)h(6)g(will)f(ha)o
(v)o(e)g(ranges)i(of)e(maxim)o(um)c(size)12 b(16)f(and)f(minim)o(um)c(size)
254 888 y(4)13 b(\(note)g(that)h(maxim)n(um)9 b(range)k(size)h(corresp)q
(onds)h(to)e(the)h(minim)n(um)9 b(recursion)15 b(depth\).)254
938 y(A)d(300)6 b Fb(\002)g Fg(400)12 b(image)e(with)i(the)h(same)f(\015ag)g
(v)n(alues)g(will)f(ha)o(v)o(e)h(the)h(same)e(size)i(ranges,)g(since)254
988 y(the)h(largest)g(square)h(sub-image)d(whic)o(h)i(\014ts)g(in)g(a)f(300)c
Fb(\002)g Fg(400)14 b(image)e(is)h(256)c Fb(\002)g Fg(256.)254
1056 y(The)j(-D,)g(-e,)g(and)g(-d)g(a\013ect)i(the)e(selection)h(of)f
(domains)e(that)j(are)f(compared)g(with)g(ranges.)254 1106
y(The)j(-D)f(\015ag)h(can)g(tak)o(e)g(v)n(alues)f(of)g(0,)h(1)f(and)h(2,)f
(whic)o(h)h(select)h(among)d(di\013eren)o(t)i(sc)o(hemes)254
1156 y(\(describ)q(ed)f(b)q(elo)o(w\))e(for)h(de\014ning)f(a)g(p)q(o)q(ol)g
(of)g(domains)e(for)i(comparison)f(with)h(eac)o(h)h(range.)254
1206 y(The)g(n)o(um)o(b)q(er)f(of)h(domains)d(is)j(also)f(a\013ected)j(b)o(y)
d(the)i(-d)f(\015ag,)f(whic)o(h)h(tak)o(es)g(a)f(v)n(alue)h(\(0-15\))254
1256 y(that)i(determines)h(the)g(domain)e(densit)o(y)m(.)22
b(The)16 b(-e)g(\015ag)f(c)o(hanges)h(the)g(meaning)e(of)h(the)h(-d)254
1306 y(v)n(alue)d(from)f(a)i(divisor)g(to)g(a)f(m)o(ultiplier)f(\(see)j(b)q
(elo)o(w\).)k(In)14 b(general,)f(-D)h(and)g(-e)g(are)h(not)f(of)254
1355 y(in)o(terest)f(to)f(the)g(casual)g(user.)18 b(With)12
b(no)f(-D)h(or)g(-e)g(\015ag,)f(higher)h(-d)g(\015ag)f(v)n(alues)h(giv)o(e)f
(b)q(etter)254 1405 y(enco)q(dings)j(that)g(tak)o(e)g(longer)g(to)g(compute.)
254 1474 y(The)d(-f)g(and)g(-F)g(\015ag)g(determine)g(ho)o(w)g(man)o(y)f
(domains)f(are)j(searc)o(hed)g(for)f(eac)o(h)h(range.)18 b(The)254
1524 y(-f)13 b(\015ag)h(searc)o(hes)i(24)e(classes)h(and)f(the)g(-F)g(\015ag)
g(searc)o(hes)i(3.)i(Both)d(cause)g(the)g(program)d(to)254
1574 y(run)e(longer)g(and)g(result)h(in)f(b)q(etter)i(enco)q(dings.)18
b(The)10 b(-p)g(\015ag)g(causes)i(only)d(p)q(ositiv)o(e)h(scalings)254
1623 y(to)f(b)q(e)h(used,)g(whic)o(h)g(means)e(that)h(only)g(one)h(class)f
(\(as)h(opp)q(osed)g(to)f(2)g(normally\))e(is)i(searc)o(hed.)254
1673 y(It)14 b(causes)h(the)g(program)d(to)i(run)g(faster)g(and)g(giv)o(e)f
(somewhat)g(p)q(o)q(orer)i(enco)q(dings.)254 1742 y(The)f(-s)g(and)g(-o)f
(\015ags)h(are)g(not)g(of)f(in)o(terest)j(to)d(the)i(casual)f(user.)150
1830 y Ff(Options)254 1927 y Fe(-t)20 b Fh(toler)n(anc)n(e.)h
Fg(A)15 b(real)g(v)n(alue)f(\(t)o(ypically)g(in)g(the)i(range)f(2)f(-)h(15\))
g(whic)o(h)f(is)h(a)g(lo)q(ose)f(target)345 1977 y(for)h(the)h(\014nal)e(rms)
h(error)h(of)e(the)i(enco)q(ded)h(image.)j(Lo)o(w)o(er)15 b(v)n(alues)g
(result)h(in)e(b)q(etter)345 2027 y(lo)q(oking)c(enco)q(ded)j(images)d(whic)o
(h)i(are)g(larger)f(\(i.e.)17 b(ha)o(v)o(e)11 b(lo)o(w)o(er)h(compression)f
(ratio\).)254 2095 y Fe(-m)20 b Fh(minimum)d(r)n(e)n(cursion)g(depth.)27
b Fg(This)16 b(is)g(the)h(minim)o(um)12 b(n)o(um)o(b)q(er)j(of)h(times)g
(that)g(the)345 2145 y(largest)k(square)g(sub-image)e(will)g(b)q(e)i
(recursiv)o(ely)h(quadtree)f(partitioned.)35 b(Using)345 2195
y(larger)13 b(v)n(alues)g(will)e(result)j(in)e(higher)i(compression)e(ratios)
h(when)g(the)h(\014le)f(is)g(easy)g(to)345 2245 y(enco)q(de.)254
2314 y Fe(-M)21 b Fh(maximum)16 b(r)n(e)n(cursion)f(depth.)23
b Fg(This)15 b(is)g(the)g(maxim)o(um)10 b(n)o(um)o(b)q(er)15
b(of)f(times)g(that)h(the)345 2363 y(largest)20 b(square)h(sub-image)d(will)h
(b)q(e)h(quadtree)h(partitioned)f(recursiv)o(ely)m(.)36 b(Using)345
2413 y(larger)19 b(v)n(alues)g(will)e(help)i(enco)q(de)i(the)e(\014ne)h
(detail)e(in)h(the)g(image)e(at)i(the)h(cost)g(of)345 2463
y(smaller)c(compression)h(ratio.)28 b(Using)17 b(to)q(o)g(large)h(a)f(v)n
(alue)g(will)e(result)k(in)e(w)o(aste)h(of)345 2513 y(memory)m(,)11
b(since)j(ranges)h(of)e(size)i(2x2)e(or)h(less)g(should)g(not)g(b)q(e)g(enco)
q(ded.)p eop
%%Page: 3 3
bop 450 138 a Fc(A.1.)31 b(The)15 b(Enc)f(Man)o(ual)f(P)o(age)1026
b Fg(3)p 450 163 1560 1 v 554 271 a Fe(-S)20 b Fh(strip)n(chars.)h
Fg(The)16 b(n)o(um)o(b)q(er)e(of)h(b)o(ytes)h(skipp)q(ed)g(at)f(the)g(b)q
(eginning)g(of)f(the)i(input)f(data)645 321 y(\014le.)31 b(This)18
b(is)g(useful)g(with)g(some)g(image)e(formats)h(whic)o(h)h(store)h(the)f
(image)f(after)645 371 y(a)g(header)g(that)g(can)g(b)q(e)g(skipp)q(ed.)28
b(Care)17 b(should)f(b)q(e)i(tak)o(en)e(that)h(the)h(image)c(data)645
421 y(corresp)q(ond)19 b(to)e(the)g(actual)g(grey-scale)h(v)n(alues)f(\(and)g
(not)g(a)g(reference)i(through)e(a)645 471 y(color)d(lo)q(okup)f(table\).)554
539 y Fe(-w)21 b Fh(width.)h Fg(The)16 b(width)f(of)g(the)h(input)f(image,)e
(assumed)i(to)g(b)q(e)h(the)g(heigh)o(t)f(if)g(-w)g(is)g(not)645
589 y(used.)554 658 y Fe(-h)20 b Fh(height.)j Fg(The)16 b(heigh)o(t)g(of)f
(the)h(input)f(image,)f(assumed)h(to)h(b)q(e)g(the)g(width)f(if)g(-h)h(is)f
(not)645 708 y(used.)554 777 y Fe(-d)20 b Fh(domain)15 b(p)n(o)n(ol)g(step)g
(size.)j Fg(The)d(domain)c(p)q(o)q(ol)i(step)i(size.)k(See)c(-D.)554
846 y Fe(-D)20 b Fh(domain)e(p)n(o)n(ol)f(typ)n(e)g(\(0,)h(1,)g(2\).)26
b Fg(This)16 b(\015ag)g(selects)i(a)e(metho)q(d)g(for)g(determining)f(the)645
896 y(domain)f(p)q(o)q(ol.)23 b(The)17 b(domain)d(p)q(o)q(ol)h(consists)i(of)
e(sub-images)g(of)g(the)i(image)d(whic)o(h)645 945 y(are)i(equally)f(spaced)h
(v)o(ertically)f(and)g(horizon)o(tally)m(.)21 b(The)16 b(step)g(size)h(is)e
(determined)645 995 y(b)o(y)g(the)g(v)n(alue)f(to)h(this)f(\015ag,)g(the)i(v)
n(alue)e(to)g(the)i(-d)e(\015ag,)g(and)h(the)g(-e)g(\015ag.)20
b(Belo)o(w,)14 b Fa(d)645 1045 y Fg(denotes)g(the)g(domain)c(size,)k(and)e
Fa(s)i Fg(denotes)g(the)f(domain)e(p)q(o)q(ol)h(step)i(size,)f(the)h(v)n
(alue)645 1095 y(in)g(the)g(-d)g(\015ag.)645 1168 y Fe(0.)21
b Fg(Use)13 b(sub-images)e(of)h(the)g(image)f(of)g(size)i Fa(d)6
b Fb(\002)g Fa(d)11 b Fg(cen)o(tered)k(on)d(a)g(grid)f(with)h(v)o(ertical)723
1218 y(and)g(horizon)o(tal)f(spacing)i(of)e Fa(d=s)p Fg(.)18
b(Here,)13 b(the)g(largest)g(domains)d(get)j(the)g(largest)723
1268 y(grid)g(size.)645 1327 y Fe(1.)21 b Fg(Use)13 b(sub-images)e(of)h(the)g
(image)f(of)g(size)i Fa(d)6 b Fb(\002)g Fa(d)11 b Fg(cen)o(tered)k(on)d(a)g
(grid)f(with)h(v)o(ertical)723 1377 y(and)h(horizon)o(tal)g(spacing)h(of)f
Fa(t)p Fg(.)18 b(The)d(v)n(alue)e Fa(t)h Fg(dep)q(ends)h(on)f(the)g(maxim)o
(um)9 b(and)723 1427 y(minim)n(um)g(quadtree)14 b(partitions.)j(The)c(grid)g
(size)h(is)f(essen)o(tially)g(in)o(v)o(erted)g(with)723 1476
y(resp)q(ect)j(to)e(domain)e(size)j(from)d(the)j(0)f(case)h(ab)q(o)o(v)o(e.)j
(The)d(largest)f(domains)f(get)723 1526 y(the)h(smallest)f(grid,)g(and)g(the)
i(vice)f(v)o(ers