splitw.py (8721B)
1 #!/usr/bin/python3 -O 2 3 import imageio 4 import sys 5 import numpy 6 import argparse 7 import os.path 8 from math import ceil, floor 9 10 parser = argparse.ArgumentParser( 11 description="Split a musical system into bits of maximal width") 12 parser.add_argument("filename", 13 help="input PNG file name", type=str) 14 parser.add_argument("output_folder", 15 help="folder to write output files", type=str) 16 parser.add_argument("width", 17 help="maximum width in pixels", type=int) 18 parser.add_argument("--minlength", 19 help="minimum len of a low-height point", 20 type=int, default=5) 21 parser.add_argument("--margin", 22 help="margin for low height computation", 23 type=int, default=10) 24 parser.add_argument("--heightthreshold", 25 help="negligible height difference for low-height points", 26 type=int, default=5) 27 parser.add_argument("--weightthreshold", 28 help="negligible weight difference", 29 type=int, default=10) 30 parser.add_argument("--weightwindow", 31 help="window for weight", 32 type=int, default=5) 33 parser.add_argument("--maxbardistance", 34 help="maximum bar distance", 35 type=int, default=15) 36 parser.add_argument("--minbarweight", 37 help="minimum weight multiplicator for bar", 38 type=int, default=4) 39 parser.add_argument("--outlierquantile", 40 help="eliminate this proportion of outlier weights/heights", 41 type=float, default=0.03) 42 parser.add_argument("--whitethreshold", 43 help="threshold to detect white space", 44 type=float, default=3) 45 parser.add_argument("--minchunk", 46 help="minimal width of a chunk when cutting outside a bar", 47 type=float, default=20) 48 parser.add_argument("--debug", 49 help="write debug image", 50 action='store_true') 51 args = parser.parse_args() 52 53 img = imageio.imread(args.filename) 54 55 # https://stackoverflow.com/a/38549260 56 if hasattr(type(img[0][0]), '__iter__'): 57 print ("converting input image to grayscale") 58 # https://stackoverflow.com/a/51571053 59 img = numpy.dot(img[... , :3] , [0.299 , 0.587, 0.114]) 60 61 in_h = len(img) 62 in_w = len(img[0]) 63 64 # Step 1: find columns of low height 65 66 top = [None] * in_w 67 bottom = [None] * in_w 68 height = [None] * in_w 69 70 for c in range(in_w): 71 c_top = 0 72 while c_top < in_h and 255-img[c_top][c] <= args.whitethreshold: 73 c_top += 1 74 top[c] = c_top 75 76 c_bottom = in_h 77 while c_bottom >= 0 and 255-img[c_bottom-1][c] <= args.whitethreshold: 78 c_bottom -= 1 79 bottom[c] = c_bottom 80 81 height[c] = bottom[c] - top[c] 82 83 heights = sorted(height[args.margin:-args.margin]) 84 mn_height = heights[int(len(heights)*args.outlierquantile)] 85 86 lowheight = [height[c] < mn_height + args.heightthreshold for c in range(in_w)] 87 88 # Step 2: eliminate columns of minimal height that are too isolated 89 90 last = 0 91 for c in range(in_w): 92 if not lowheight[c]: 93 if c-last < args.minlength: 94 # forget about the previous region, it is too small 95 for cc in range(last, c+1): 96 lowheight[cc] = False 97 last = c 98 99 # Step 3: compute the total weights and find columns of low weight 100 101 cumul = [sum(255-img[r][c] for r in range(in_h)) for c in range(in_w)] 102 mn_weights=[] 103 104 for c in range(args.margin, in_w-2*args.margin -args.weightwindow): 105 if lowheight[c]: 106 mn_weights.append(sum(cumul[c:c+args.weightwindow])) 107 108 mn_weights = sorted(mn_weights) 109 mn_weight = mn_weights[int(len(mn_weights)*args.outlierquantile)] 110 111 lowweight = [sum(cumul[max(0, c-ceil(1.*args.weightwindow/2)):min(in_w-1,c+floor(1.*args.weightwindow/2))]) < 112 mn_weight + args.weightthreshold*in_h*args.weightwindow for c in range(in_w)] 113 114 # Step 4: find barlines 115 116 last = -1 117 maxweight = -1 118 maxweightpos = -1 119 120 bars = [0] 121 122 for c in range(in_w): 123 if not lowheight[c]: 124 last = -1 # give up 125 continue 126 if not lowweight[c]: 127 if cumul[c] > maxweight: 128 maxweight = cumul[c] 129 maxweightpos = c 130 if lowweight[c] and last > 0 and maxweight > 0: 131 # could be good 132 if maxweight > args.minbarweight*mn_weight/args.weightwindow: 133 if c-last < args.maxbardistance: 134 bars.append(maxweightpos) 135 if lowweight[c]: 136 maxweight = -1 137 maxweightpos = -1 138 last = c 139 140 if bars[-1] != in_w-1: 141 bars.append(in_w-1) 142 143 # Step 5: ensure we will not get stuck by adding cutting points where necessary 144 145 bars2 = [bars[0]] 146 for b in range(len(bars)-1): 147 cbar = bars[b+1] 148 while cbar-bars2[-1] > args.width: 149 # let's first try to find a reasonable cut point... 150 cc = bars2[-1]+args.width 151 ok = False 152 while cc > bars2[-1]+args.minchunk: 153 if lowweight[cc] and lowheight[cc]: 154 ok = True 155 break 156 cc -= 1 157 if ok: 158 # cut where we found 159 bars2.append(cc) 160 else: 161 # last resort: we cut anywhere 162 if cbar-bars2[-1] < 2*(args.width-1): 163 # try to be a bit more clever here: cut at the middle 164 bars2.append(int((bars2[-1]+cbar)/2)) 165 else: 166 bars2.append(bars2[-1]+args.width) 167 bars2.append(cbar) 168 169 chunks = [] 170 171 for b in range(len(bars2)-1): 172 cbar = bars2[b] 173 nbar = bars2[b+1] 174 chunks.append((cbar, nbar-cbar+1)) 175 176 # Step 6: optimal fit 177 178 # naive bruteforce for word wrapping 179 # TODO: this could be a dynamic algorithm 180 def fit(remaining, current_bucket, current_bucket_weight, previous_buckets, worst_difference): 181 if len(remaining) == 0: 182 return (max(worst_difference, args.width-current_bucket_weight), 183 previous_buckets + [current_bucket]) 184 # solution1: finish current bucket and start a new bucket 185 solution1 = fit(remaining[1:], [remaining[0]], remaining[0][1], 186 previous_buckets + [current_bucket], max(worst_difference, 187 args.width-current_bucket_weight)) 188 if current_bucket_weight+remaining[0][1] > args.width: 189 # it does not fit so there's no choice 190 return solution1 191 # solution2: add next item to current bucket 192 solution2 = fit(remaining[1:], current_bucket + [remaining[0]], 193 current_bucket_weight + remaining[0][1], previous_buckets, 194 worst_difference) 195 if solution1[0] < solution2[0]: 196 return solution1 197 else: 198 return solution2 199 200 sol = fit(chunks[1:], [chunks[0]], chunks[0][1], [], 0) 201 202 final_chunks = [(x[0][0], x[-1][0] + x[-1][1] - x[0][0]) for x in sol[1]] 203 204 if args.debug: 205 matrix = numpy.full((in_h,in_w,3), 255, dtype=numpy.uint8) 206 207 for r in range(in_h): 208 for c in range(in_w): 209 matrix[r][c] = img[r][c] 210 if top[c] <= r <= bottom[c]: 211 if lowheight[c]: 212 matrix[r][c][1] = 128 213 if lowweight[c]: 214 matrix[r][c][0] = 128 215 if c in bars: 216 matrix[r][c][0] = 255 217 matrix[r][c][1] = 0 218 matrix[r][c][2] = 0 219 elif c in bars2: 220 matrix[r][c][0] = 0 221 matrix[r][c][1] = 255 222 matrix[r][c][2] = 0 223 if c in [y[0] for y in final_chunks]: 224 matrix[r][c][0] = 0 225 matrix[r][c][1] = 0 226 matrix[r][c][2] = 255 227 228 outfname = os.path.join(args.output_folder, "debug.png") 229 230 imageio.imwrite(outfname, matrix) 231 sys.exit(0) 232 233 # Step 7: draw chunks 234 235 num = 0 236 237 for (start, width) in final_chunks: 238 # count the stretchable columns 239 stretchable = 0 240 naive_stretch = False 241 for c in range(start, start+width): 242 if lowweight[c] and lowheight[c]: 243 stretchable += 1 244 non_stretchable = width-stretchable 245 target_stretchable = args.width - non_stretchable 246 if stretchable == 0: 247 # if nothing is stretchable, fall back on naive stretching 248 naive_stretch = True 249 factor = 1.*args.width/width 250 else: 251 factor = 1.*target_stretchable/stretchable 252 253 matrix = numpy.full((in_h,args.width), 255, dtype=numpy.uint8) 254 255 for r in range(in_h): 256 outc = 0 257 outpos = 0. 258 for c in range(start, start+width): 259 if naive_stretch: 260 outpos += factor 261 else: 262 if not (lowweight[c] and lowheight[c]): 263 outpos += 1 264 else: 265 outpos += factor 266 while outc <= outpos and outc < args.width: 267 matrix[r][outc] = img[r][c] 268 outc += 1 269 270 outfname = os.path.join(args.output_folder, os.path.basename(args.filename).split('.')[0] + "_" + "{:04d}".format(num) + ".png") 271 272 imageio.imwrite(outfname, matrix) 273 print("wrote %s" % outfname) 274 num += 1 275