00001
00002
00003
00004
00005
00006 from enhanced_grid import Grid2D
00007 from image import rgb_image_to_grid
00008 from image import grid_to_rgb_image
00009 from image import normalize_grey
00010 from image import greyscale_grid_to_rgb_grid
00011 from image import transpose
00012
00013 from random import random
00014 from random import randint
00015
00016 ENERGY_MAX = 10000
00017 R_COMP_P = .3
00018
00019 def rg(a, b):
00020 if a > b:
00021 return True
00022 elif a < b:
00023 return False
00024 else:
00025 return random() < R_COMP_P
00026
00027 def rl(a, b):
00028 if a < b:
00029 return True
00030 elif a > b:
00031 return False
00032 else:
00033 return random() < R_COMP_P
00034
00035 def is_non_negative(lst):
00036 for item in lst:
00037 if item < 0:
00038 return False
00039 return True
00040
00041
00042 def find_min_seam_debug(grid1, grid2):
00043 w, h = grid1.dims
00044
00045 acc_energy = Grid2D((w, h))
00046 energy = Grid2D((w, h))
00047
00048 seam = []
00049
00050
00051
00052
00053
00054 acc_energy[0, 0] = ENERGY_MAX
00055 energy[0, 0] = ENERGY_MAX
00056
00057
00058 for i in range(1, w):
00059 acc_energy[i, 0] = energy2(grid1[i-1, 0], grid2[i, 0])
00060 energy[i, 0] = energy2(grid1[i-1, 0], grid2[i, 0])
00061
00062
00063
00064 for j in range (1, h):
00065 acc_energy[0, j] = ENERGY_MAX
00066 energy[0, j] = ENERGY_MAX
00067
00068 for i in range(1, w - 1):
00069 if acc_energy[i + 1, j - 1] < acc_energy[i, j - 1] and acc_energy[i + 1, j - 1] < acc_energy[i - 1, j - 1]:
00070 e = energy3(grid2[i, j], grid1[i - 1, j], grid1[i, j - 1])
00071 else:
00072 e = energy3(grid2[i, j], grid1[i - 1, j], grid2[i, j - 1])
00073 acc_energy[i, j] = min(acc_energy[i - 1:i+2, j-1]) + e
00074 energy[i, j] = e
00075
00076
00077 e = energy3(grid2[i, j], grid1[i - 1, j], grid2[i, j - 1])
00078
00079 acc_energy[-1, j] = min(acc_energy[-2:, j-1]) + e
00080 energy[-1, j] = e
00081
00082 last_seam = argmin(acc_energy[:, -1])
00083 seam.append(last_seam)
00084
00085 for j in range(h - 2, -1, -1):
00086 if last_seam == 1:
00087 last_seam + argmin(acc_energy[last_seam: last_seam + 2, j])
00088 elif last_seam == w - 2:
00089 last_seam = last_seam - 1 + argmin(acc_energy[last_seam - 1: last_seam + 1, j])
00090 else:
00091 last_seam = last_seam - 1 + argmin(acc_energy[last_seam - 1: last_seam + 2, j])
00092 seam.append(last_seam)
00093
00094 seam.reverse()
00095
00096 return seam, energy
00097
00098 def quilt_debug(grid1, grid2, w):
00099 seam, energy = find_min_seam_debug(grid1[-w:, :], grid2[:w, :])
00100
00101 res = Grid2D((grid1.width + grid2.width - w, grid1.height))
00102
00103 for i in range(res.width):
00104 for j in range(res.height):
00105 if i < grid1.width - w + seam[j]:
00106 res[i, j] = grid1[i, j]
00107 elif i == grid1.width - w + seam[j]:
00108 res[i, j] = (1, 0, 0, 1)
00109 else:
00110 res[i, j] = grid2[i - grid1.width + w , j]
00111 return res, energy
00112
00113
00114 def energy2_old(col1, col2):
00115 s1 = sum(col1)
00116 s2 = sum(col2)
00117
00118 return abs(s1 - s2)
00119
00120 def energy3(col_centre, col_left, col_top):
00121 s_centre = sum(col_centre)
00122 s_top = sum(col_top)
00123 s_left = sum(col_left)
00124
00125 return abs(s_centre - s_top) + abs(s_centre - s_left)
00126
00127 def energy2(col1, col2):
00128 return abs(col1[0] - col2[0]) + abs(col1[1] - col2[1]) + abs(col1[2] - col2[2])
00129
00130 def energy3(col_centre, col_left, col_top):
00131 return abs(col_centre[0] - col_top[0]) + abs(col_centre[0] - col_left[0]) + \
00132 abs(col_centre[1] - col_top[1]) + abs(col_centre[1] - col_left[1]) + \
00133 abs(col_centre[2] - col_top[2]) + abs(col_centre[2] - col_left[2])
00134
00135 def energy4(col_centre, col_left, col_top, col_top_left):
00136 return abs(col_centre[0] - col_top[0]) + abs(col_centre[0] - col_left[0]) + abs(col_centre[0] - col_top_left[0]) + \
00137 abs(col_centre[1] - col_top[1]) + abs(col_centre[1] - col_left[1]) + abs(col_centre[1] - col_top_left[1]) + \
00138 abs(col_centre[2] - col_top[2]) + abs(col_centre[2] - col_left[2]) + abs(col_centre[2] - col_top_left[2])
00139
00140
00141 def argmin(lst):
00142 min_item = lst[0]
00143 min_i = 0
00144
00145 for i, item in enumerate(lst[1:]):
00146 if rl (item, min_item):
00147 min_item = item
00148 min_i = i + 1
00149 return min_i
00150
00151
00152 def calc_acc_energy(grid1, grid2):
00153 w, h = grid1.dims
00154 acc_energy = Grid2D((w, h))
00155
00156
00157
00158 acc_energy[0, 0] = ENERGY_MAX
00159
00160 for i in range(1, w):
00161 acc_energy[i, 0] = energy2(grid1[i-1, 0], grid2[i, 0])
00162
00163
00164
00165 for j in range (1, h):
00166 acc_energy[0, j] = ENERGY_MAX
00167
00168 for i in range(1, w - 1):
00169 if acc_energy[i + 1, j - 1] < acc_energy[i, j - 1] and acc_energy[i + 1, j - 1] < acc_energy[i - 1, j - 1]:
00170 e = energy3(grid2[i, j], grid1[i - 1, j], grid1[i, j - 1])
00171 else:
00172 e = energy3(grid2[i, j], grid1[i - 1, j], grid2[i, j - 1])
00173 acc_energy[i, j] = min(acc_energy[i - 1:i+2, j-1]) + e
00174
00175
00176 e = energy3(grid2[i, j], grid1[i - 1, j], grid2[i, j - 1])
00177 acc_energy[-1, j] = min(acc_energy[-2:, j-1]) + e
00178
00179 return acc_energy
00180
00181
00182 def calc_acc_energy2(grid1, grid2):
00183 w, h = grid1.dims
00184 acc_energy = Grid2D((w, h))
00185
00186
00187
00188 acc_energy[0, 0] = ENERGY_MAX
00189
00190 for i in range(1, w):
00191 acc_energy[i, 0] = energy2(grid1[i, 0], grid2[i, 0])
00192
00193
00194
00195 for j in range (1, h):
00196 acc_energy[0, j] = ENERGY_MAX
00197
00198 for i in range(1, w - 1):
00199 e = energy2(grid1[i, j], grid2[i, j])
00200 acc_energy[i, j] = min(acc_energy[i - 1:i+2, j-1]) + e
00201
00202
00203 e = energy2(grid1[i, j], grid2[i, j])
00204 acc_energy[-1, j] = min(acc_energy[-2:, j-1]) + e
00205
00206 return acc_energy
00207
00208 def find_min_seam(grid1, grid2):
00209 w, h = grid1.dims
00210 acc_energy = calc_acc_energy2(grid1, grid2)
00211 last_seam = argmin(acc_energy[:, -1])
00212 seam = []
00213 seam.append(last_seam)
00214
00215 for j in range(h - 2, -1, -1):
00216 if last_seam == 1:
00217 last_seam + argmin(acc_energy[last_seam: last_seam + 2, j])
00218 elif last_seam == w - 2:
00219 last_seam = last_seam - 1 + argmin(acc_energy[last_seam - 1: last_seam + 1, j])
00220 else:
00221 last_seam = last_seam - 1 + argmin(acc_energy[last_seam - 1: last_seam + 2, j])
00222 seam.append(last_seam)
00223
00224 seam.reverse()
00225
00226 return seam
00227
00228 def quilt(grid1, grid2, w):
00229 seam = find_min_seam(grid1[grid1.width-w:, :], grid2[:w, :])
00230 assert is_non_negative(seam)
00231
00232 res = Grid2D((grid1.width + grid2.width - w, grid1.height))
00233
00234 for i in range(res.width):
00235 for j in range(res.height):
00236 if i < grid1.width - w + seam[j]:
00237 res[i, j] = grid1[i, j]
00238 else:
00239 res[i, j] = grid2[i - grid1.width + w , j]
00240
00241
00242
00243 return res
00244
00245 def quilt_multi_h(src, w, h, nx, qw):
00246 x0 = randint(0, src.width - w - 1)
00247 y0 = randint(0, src.height - h - 1)
00248 grid = src[x0:x0 + w, y0:y0 + h]
00249
00250 for i in range(nx):
00251 x0 = randint(0, src.width - w - 1)
00252 y0 = randint(0, src.height - h - 1)
00253 new_grid = src[x0:x0 + w, y0:y0 + h]
00254 grid = quilt(grid, new_grid, qw)
00255
00256 return grid
00257
00258 def quilt_multi(src, w, h, nx, ny, qw, qh):
00259 grid = transpose(quilt_multi_h(src, w, h, nx, qw))
00260
00261 for i in range(ny):
00262 new_grid = transpose(quilt_multi_h(src, w, h, nx, qw))
00263 grid = quilt(grid, new_grid, qh)
00264
00265 return transpose(grid)
00266
00267
00268
00269