Changeset 2190 for www/study/study.py

Timestamp:

01/12/08 13:53:10 (5 years ago)

Author:

sam

Message:

• Direct binary search.

File:

• www/study/study.py (modified) (1 diff)

www/study/study.py

@@ -1752 +1752 @@
             ERROR_SUBFS33[y][x][y][1 + x] = -1
 
+# Output 3.7.1: direct binary search, iteration 0
+# Output 3.7.2: direct binary search, iteration 1
+# Output 3.7.3: direct binary search, iteration 2
+# Output 3.7.4: direct binary search, iteration 5
+def test37x(src):
+    random.seed(0)
+    (w, h) = src.size()
+    dest = Image((w, h))
+    for y in range(h):
+        for x in range(w):
+            c = src.getGray(x, y) + random.random() - 0.5
+            d = c > 0.5
+            dest.setGray(x, y, d)
+    return dest
+
+def test37y(src, dest):
+    threshold = 0.4
+    kernel = Matrix(6, 6, 0.) # have a border of zeroes
+    for j in range(4):
+        for i in range(4):
+             kernel[j][i] = math.pow(math.e, - math.sqrt(i * i + j * j))
+    (w, h) = src.size()
+    # Build fast pixel lookup tables
+    srcmat = Matrix(w, h, 0.)
+    destmat = Matrix(w, h, 0.)
+    for y in range(h):
+        for x in range(w):
+            srcmat[y][x] = src.getGray(x, y)
+            destmat[y][x] = dest.getGray(x, y)
+    # Build human perception model for both source and destination
+    srchvs = Matrix(w, h, 0.)
+    desthvs = Matrix(w, h, 0.)
+    for y in range(h):
+        for x in range(w):
+            srcp = destp = 0.
+            for j in range(-3, 4):
+                if y + j < 0 or y + j >= h:
+                    continue
+                for i in range(-3, 4):
+                    if x + i < 0 or x + i >= w:
+                        continue
+                    m = kernel[abs(j)][abs(i)]
+                    srcp += m * srcmat[y + j][x + i]
+                    destp += m * destmat[y + j][x + i]
+            srchvs[y][x] = srcp
+            desthvs[y][x] = destp
+    swaps = toggles = 0
+    for y in range(h):
+        for x in range(w):
+            d = destmat[y][x]
+            best = 0.
+            # Compute the effect of a toggle
+            e = 0.
+            for j in range(-3, 4):
+                if y + j < 0 or y + j >= h:
+                    continue
+                for i in range(-3, 4):
+                    if x + i < 0 or x + i >= w:
+                        continue
+                    m = kernel[abs(j)][abs(i)]
+                    p = srchvs[y + j][x + i]
+                    q1 = desthvs[y + j][x + i]
+                    q2 = q1 - m * d + m * (1. - d)
+                    e += abs(q1 - p) - abs(q2 - p)
+            if e > best:
+                best = e
+                op = False
+            # Compute the effect of swaps
+            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
+                if y + dy < 0 or y + dy >= h or x + dx < 0 or x + dx >= w:
+                    continue
+                d2 = destmat[y + dy][x + dx]
+                if d2 == d:
+                    continue
+                e = 0.
+                for j in range(-4, 5):
+                    for i in range(-4, 5):
+                        if y + j < 0 or y + j >= h or x + i < 0 or x + i >= w:
+                            continue
+                        ma = kernel[abs(j)][abs(i)]
+                        mb = kernel[abs(j - dy)][abs(i - dx)]
+                        p = srchvs[y + j][x + i]
+                        q1 = desthvs[y + j][x + i]
+                        q2 = q1 - ma * d + ma * d2 - mb * d2 + mb * d
+                        e += abs(q1 - p) - abs(q2 - p)
+                if e > best:
+                    best = e
+                    op = (dx, dy)
+            # Apply the change if interesting
+            if best <= 0.:
+                continue
+            if op:
+                dx, dy = op
+                d2 = destmat[y + dy][x + dx]
+                destmat[y + dy][x + dx] = d
+            else:
+                d2 = 1. - d
+            destmat[y][x] = d2
+            for j in range(-3, 4):
+                for i in range(-3, 4):
+                    m = kernel[abs(j)][abs(i)]
+                    if y + j >= 0 and y + j < h and x + i >= 0 and x + i < w:
+                        desthvs[y + j][x + i] -= m * d
+                        desthvs[y + j][x + i] += m * d2
+                    if op and y + dy + j >= 0 and y + dy + j < h \
+                       and x + dx + i >= 0 and x + dx + i < w:
+                        desthvs[y + dy + j][x + dx + i] -= m * d2
+                        desthvs[y + dy + j][x + dx + i] += m * d
+    for y in range(h):
+        for x in range(w):
+            dest.setGray(x, y, destmat[y][x])
+    return dest
+
+if chapter(3):
+    tmp = test37x(grad256bw)
+    tmp.save("grad3-7-1.png")
+    tmp = test37y(grad256bw, tmp)
+    tmp.save("grad3-7-2.png")
+    tmp = test37y(grad256bw, tmp)
+    tmp.save("grad3-7-3.png")
+    tmp = test37y(grad256bw, tmp)
+    tmp = test37y(grad256bw, tmp)
+    tmp = test37y(grad256bw, tmp)
+    tmp.save("grad3-7-4.png")
+
+if chapter(3):
+    tmp = test37x(lenna256bw)
+    tmp.save("out3-7-1.png")
+    tmp = test37y(lenna256bw, tmp)
+    tmp.save("out3-7-2.png")
+    tmp = test37y(lenna256bw, tmp)
+    tmp.save("out3-7-3.png")
+    tmp = test37y(lenna256bw, tmp)
+    tmp = test37y(lenna256bw, tmp)
+    tmp = test37y(lenna256bw, tmp)
+    tmp.save("out3-7-4.png")
+
 ##############################################################################
 if chapter(4):