Changeset 2031Tweet

Timestamp:

11/20/07 00:04:32 (6 years ago)

Author:

sam

Message:

• More about photomosaics.

Location:

www/study

Files:

• out6-1-1.png (added)
• out6-1-2.png (moved) (moved from www/study/out6-0-2.png)
• out6-1-3.png (added)
• out6-1-4.png (added)
• out6-1-5.png (moved) (moved from www/study/out6-0-3.png)
• part6.html (modified) (2 diffs)
• study.py (modified) (3 diffs)

www/study/part6.html

@@ -40 +40 @@
 of a bigger image. </p>
 
-<p> Since we don’t have many images at our disposition, we will simply
-cut Lenna into small chunks and use these parts to create mosaics. This is
-our <b>image database</b>: </p>
+<p> Since we don’t have many images at our disposal, we will simply cut Lenna
+into small chunks (called <b>tiles</b>) and use these parts to create mosaics.
+This is our <b>tile database</b>: </p>
 
 <p style="text-align: center;">
@@ -49 +49 @@
 </p>
 
-<p> Here is an example of a simple photographic mosaic method where the
-original picture is cut into smaller chunks and each chunk is matched to
-the most resembling item in the image database: </p>
+<p> Generating a photomosaic consists in subdividing the original picture
+into <i>x</i> rectangular cells and find <i>x</i> tiles in the database
+(with or without duplicates, depending on the set of rules that is decided)
+so that when recombined the resulting image resembles the original picture.
+By the way, this technique is covered by Runaway Technology Inc’s
+<a href="http://www.freepatentsonline.com/6137498.html">U.S. patent
+6137498</a>. </p>
+
+<p> Picking the right tile for the right cell in the grid is a very
+expensive and complicated operation. One of the biggest problems is the
+cost of a database lookup: comparing each tile area pixel-by-pixel
+is an O(N) operation where N is the size of the database. We can resort
+to <b>image classification</b> in order to speed up database lookups. </p>
+
+<h3> 6.1. Image classification </h3>
+
+<p> One of the simplest image classification technique is the storage of
+each tile’s <b>average colour</b> into a separate database that is used for
+best match lookups: </p>
 
 <p style="text-align: center;">
-  <img src="out6-0-2.png" width="80" height="80"
+  <img src="out6-1-1.png" width="168" height="120"
+       class="inline" alt="1 feature extracted from Lenna patterns" />
+</p>
+
+<p> When creating the mosaic, we then only need to check the average colour
+instead of comparing each pixel one by one. Below is the result of the
+technique applied on a portion of the Lenna picture: </p>
+
+<p style="text-align: center;">
+  <img src="out6-1-2.png" width="80" height="80"
        class="inlinetop" alt="Lenna (detail)" />
-  <img src="out6-0-3.png" width="416" height="416"
+  <img src="out6-1-3.png" width="416" height="416"
+       class="inline" alt="Mosaic created from Lenna’s detail" />
+</p>
+
+<p> Better results can be achieved by storing <b>four colour values</b>, one
+for each corner of the tile: </p>
+
+<p style="text-align: center;">
+  <img src="out6-1-4.png" width="248" height="176"
+       class="inline" alt="4 features extracted from Lenna patterns" />
+</p>
+
+<p> Having 12 values (4 RGB triplets) is still a lot less than the original
+value of 3072 (for 32×32 tiles), and the results show clear improvement,
+for instance the feather-hair frontier is now a lot smoother: </p>
+
+<p style="text-align: center;">
+  <img src="out6-1-2.png" width="80" height="80"
+       class="inlinetop" alt="Lenna (detail)" />
+  <img src="out6-1-5.png" width="416" height="416"
        class="inline" alt="Mosaic created from Lenna’s detail" />
 </p>

www/study/study.py

@@ -39 +39 @@
         c = self.colorResolve((r, g, b))
         self.setPixel((x, y), c)
+    def getCrop(self, x, y, w, h):
+        dest = Image((w, h), True)
+        self.copyTo(dest, (-x, -y))
+        return dest
 
 # Manipulate gamma values
@@ -838 +842 @@
     return coeffs
 
-def test603(src, sqw, sqh, tnlist, coeffs, dx, dy):
-    (w, h) = src.size()
+def test601(tnlist, cols):
     (tnw, tnh) = tnlist[0].size()
+    dw = cols
+    dh = (len(tnlist) + cols - 1) / cols
+    dest = Image((dw * tnw + 8 * (dw + 1), dh * tnh + 8 * (dh + 1)), True)
+    for (n, img) in enumerate(tnlist):
+        di = 8 + (n % dw) * (tnw + 8)
+        dj = 8 + (n / dw) * (tnh + 8)
+        for y in range(tnh):
+            for x in range(tnw):
+                (r, g, b) = img.getRgb(x, y)
+                dest.setRgb(di + x, dj + y, r, g, b)
+    return dest
+
+if chapter(6):
+    tnlist = mosaic_split(lenna256, 32, 32)
+    test601(tnlist, 10).save("out6-0-1.png")
+
+# Output 6.1.1: extract 1 colour feature from mosaic tiles
+# Output 6.1.2: crop Lenna
+# Output 6.1.3: generate a mosaic from the 1-feature database
+# Output 6.1.4: extract 4 colour features from mosaic tiles
+# Output 6.1.5: generate a mosaic from the 4-feature database
+def test61x(coeffs, cols, tnw, tnh):
+    dx = len(coeffs[0][0])
+    dy = len(coeffs[0])
+    dw = cols
+    dh = (len(coeffs) + cols - 1) / cols
+    dest = Image((dw * tnw + 8 * (dw + 1), dh * tnh + 8 * (dh + 1)), True)
+    for (n, tab) in enumerate(coeffs):
+        di = 8 + (n % dw) * (tnw + 8)
+        dj = 8 + (n / dw) * (tnh + 8)
+        for y in range(tnh):
+            for x in range(tnw):
+                (r, g, b) = tab[y * dy / tnh][x * dx / tnw]
+                dest.setRgb(di + x, dj + y, Gamma.ItoC(r), Gamma.ItoC(g), Gamma.ItoC(b))
+    return dest
+
+def test61y(src, sqw, sqh, tnlist, coeffs):
+    (w, h) = src.size()
+    (tnw, tnh) = tnlist[0].size()
+    dx = len(coeffs[0][0])
+    dy = len(coeffs[0])
     nx = w / sqw
     ny = h / sqh
@@ -873 +917 @@
     return dest
 
-def test602(src, x, y, w, h):
-    dest = Image((w, h), True)
-    src.copyTo(dest, (-x, -y))
-    return dest
-
-def test601(tnlist, cols):
-    (tnw, tnh) = tnlist[0].size()
-    dw = cols
-    dh = (len(tnlist) + cols - 1) / cols
-    dest = Image((dw * tnw + 8 * (dw + 1), dh * tnh + 8 * (dh + 1)), True)
-    for (n, img) in enumerate(tnlist):
-        di = 8 + (n % dw) * (tnw + 8)
-        dj = 8 + (n / dw) * (tnh + 8)
-        for y in range(tnh):
-            for x in range(tnw):
-                (r, g, b) = img.getRgb(x, y)
-                dest.setRgb(di + x, dj + y, r, g, b)
-    return dest
-
 if chapter(6):
-    tnlist = mosaic_split(lenna256, 32, 32)
-    coeffs = mosaic_analyse(tnlist, 2, 2)
-    test601(tnlist, 10).save("out6-0-1.png")
-    out602 = test602(lenna256, 100, 90, 80, 80)
-    out602.save("out6-0-2.png")
-    test603(out602, 6, 6, tnlist, coeffs, 2, 2).save("out6-0-3.png")
+    coeffs1x1 = mosaic_analyse(tnlist, 1, 1)
+    test61x(coeffs1x1, 10, 8, 8).save("out6-1-1.png")
+    out612 = lenna256.getCrop(100, 90, 80, 80)
+    out612.save("out6-1-2.png")
+    test61y(out612, 6, 6, tnlist, coeffs1x1).save("out6-1-3.png")
+
+    coeffs2x2 = mosaic_analyse(tnlist, 2, 2)
+    test61x(coeffs2x2, 10, 16, 16).save("out6-1-4.png")
+    test61y(out612, 6, 6, tnlist, coeffs2x2).save("out6-1-5.png")
 
 ##############################################################################