· 9 years ago · Jan 10, 2017, 04:22 PM
1# -*- coding: utf-8 -*-
2# Copyright (C) 2012, Almar Klein, Ant1, Marius van Voorden
3#
4# This code is subject to the (new) BSD license:
5#
6# Redistribution and use in source and binary forms, with or without
7# modification, are permitted provided that the following conditions are met:
8# * Redistributions of source code must retain the above copyright
9# notice, this list of conditions and the following disclaimer.
10# * Redistributions in binary form must reproduce the above copyright
11# notice, this list of conditions and the following disclaimer in the
12# documentation and/or other materials provided with the distribution.
13# * Neither the name of the <organization> nor the
14# names of its contributors may be used to endorse or promote products
15# derived from this software without specific prior written permission.
16#
17# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20# ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
21# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28""" Module images2gif
29
30Provides functionality for reading and writing animated GIF images.
31Use writeGif to write a series of numpy arrays or PIL images as an
32animated GIF. Use readGif to read an animated gif as a series of numpy
33arrays.
34
35Note that since July 2004, all patents on the LZW compression patent have
36expired. Therefore the GIF format may now be used freely.
37
38Acknowledgements
39----------------
40
41Many thanks to Ant1 for:
42
43* noting the use of "palette=PIL.Image.ADAPTIVE", which significantly
44 improves the results.
45* the modifications to save each image with its own palette, or optionally
46 the global palette (if its the same).
47
48Many thanks to Marius van Voorden for porting the NeuQuant quantization
49algorithm of Anthony Dekker to Python (See the NeuQuant class for its
50license).
51
52Many thanks to Alex Robinson for implementing the concept of subrectangles,
53which (depening on image content) can give a very significant reduction in
54file size.
55
56This code is based on gifmaker (in the scripts folder of the source
57distribution of PIL)
58
59
60Useful links
61-------------
62 * http://tronche.com/computer-graphics/gif/
63 * http://en.wikipedia.org/wiki/Graphics_Interchange_Format
64 * http://www.w3.org/Graphics/GIF/spec-gif89a.txt
65
66"""
67# todo: This module should be part of imageio (or at least based on)
68
69import os
70import time
71
72try:
73 import PIL
74 from PIL import Image
75 from PIL.GifImagePlugin import getheader, getdata
76except ImportError:
77 PIL = None
78
79try:
80 import numpy as np
81except ImportError:
82 np = None
83
84
85def get_cKDTree():
86 try:
87 from scipy.spatial import cKDTree
88 except ImportError:
89 cKDTree = None
90 return cKDTree
91
92
93# getheader gives a 87a header and a color palette (two elements in a list).
94# getdata()[0] gives the Image Descriptor up to (including) "LZW min code size".
95# getdatas()[1:] is the image data itself in chuncks of 256 bytes (well
96# technically the first byte says how many bytes follow, after which that
97# amount (max 255) follows).
98
99def checkImages(images):
100 """ checkImages(images)
101 Check numpy images and correct intensity range etc.
102 The same for all movie formats.
103 """
104 # Init results
105 images2 = []
106
107 for im in images:
108 if PIL and isinstance(im, PIL.Image.Image):
109 # We assume PIL images are allright
110 images2.append(im)
111
112 elif np and isinstance(im, np.ndarray):
113 # Check and convert dtype
114 if im.dtype == np.uint8:
115 images2.append(im) # Ok
116 elif im.dtype in [np.float32, np.float64]:
117 im = im.copy()
118 im[im < 0] = 0
119 im[im > 1] = 1
120 im *= 255
121 images2.append(im.astype(np.uint8))
122 else:
123 im = im.astype(np.uint8)
124 images2.append(im)
125 # Check size
126 if im.ndim == 2:
127 pass # ok
128 elif im.ndim == 3:
129 if im.shape[2] not in [3, 4]:
130 raise ValueError('This array can not represent an image.')
131 else:
132 raise ValueError('This array can not represent an image.')
133 else:
134 raise ValueError('Invalid image type: ' + str(type(im)))
135
136 # Done
137 return images2
138
139
140def intToBin(i):
141 """Integer to two bytes"""
142 # devide in two parts (bytes)
143 i1 = i % 256
144 i2 = int(i / 256)
145 # make string (little endian)
146 return chr(i1) + chr(i2)
147
148
149class GifWriter:
150 """ GifWriter()
151
152 Class that contains methods for helping write the animated GIF file.
153
154 """
155
156 def getheaderAnim(self, im):
157 """ getheaderAnim(im)
158
159 Get animation header. To replace PILs getheader()[0]
160
161 """
162 bb = "GIF89a"
163 bb += intToBin(im.size[0])
164 bb += intToBin(im.size[1])
165 bb += "\x87\x00\x00"
166 return bb
167
168 def getImageDescriptor(self, im, xy=None):
169 """ getImageDescriptor(im, xy=None)
170
171 Used for the local color table properties per image.
172 Otherwise global color table applies to all frames irrespective of
173 whether additional colors comes in play that require a redefined
174 palette. Still a maximum of 256 color per frame, obviously.
175
176 Written by Ant1 on 2010-08-22
177 Modified by Alex Robinson in Janurari 2011 to implement subrectangles.
178
179 """
180
181 # Defaule use full image and place at upper left
182 if xy is None:
183 xy = (0, 0)
184
185 # Image separator,
186 bb = '\x2C'
187
188 # Image position and size
189 bb += intToBin(xy[0]) # Left position
190 bb += intToBin(xy[1]) # Top position
191 bb += intToBin(im.size[0]) # image width
192 bb += intToBin(im.size[1]) # image height
193
194 # packed field: local color table flag1, interlace0, sorted table0,
195 # reserved00, lct size111=7=2^(7 + 1)=256.
196 bb += '\x87'
197
198 # LZW minimum size code now comes later, begining of [image data] blocks
199 return bb
200
201 def getAppExt(self, loops=float('inf')):
202 """ getAppExt(loops=float('inf'))
203
204 Application extention. This part specifies the amount of loops.
205 If loops is 0 or inf, it goes on infinitely.
206
207 """
208
209 if loops == 0 or loops == float('inf'):
210 loops = 2 ** 16 - 1
211 #bb = "" # application extension should not be used
212 # (the extension interprets zero loops
213 # to mean an infinite number of loops)
214 # Mmm, does not seem to work
215 if True:
216 bb = "\x21\xFF\x0B" # application extension
217 bb += "NETSCAPE2.0"
218 bb += "\x03\x01"
219 bb += intToBin(loops)
220 bb += '\x00' # end
221 return bb
222
223 def getGraphicsControlExt(self, duration=0.1, dispose=2):
224 """ getGraphicsControlExt(duration=0.1, dispose=2)
225
226 Graphics Control Extension. A sort of header at the start of
227 each image. Specifies duration and transparancy.
228
229 Dispose
230 -------
231 * 0 - No disposal specified.
232 * 1 - Do not dispose. The graphic is to be left in place.
233 * 2 - Restore to background color. The area used by the graphic
234 must be restored to the background color.
235 * 3 - Restore to previous. The decoder is required to restore the
236 area overwritten by the graphic with what was there prior to
237 rendering the graphic.
238 * 4-7 -To be defined.
239
240 """
241
242 bb = '\x21\xF9\x04'
243 bb += chr((dispose & 3) << 2) # low bit 1 == transparency,
244 # 2nd bit 1 == user input , next 3 bits, the low two of which are used,
245 # are dispose.
246 bb += intToBin(int(duration * 100)) # in 100th of seconds
247 bb += '\x00' # no transparant color
248 bb += '\x00' # end
249 return bb
250
251 def handleSubRectangles(self, images, subRectangles):
252 """ handleSubRectangles(images)
253
254 Handle the sub-rectangle stuff. If the rectangles are given by the
255 user, the values are checked. Otherwise the subrectangles are
256 calculated automatically.
257
258 """
259
260 if isinstance(subRectangles, (tuple, list)):
261 # xy given directly
262
263 # Check xy
264 xy = subRectangles
265 if xy is None:
266 xy = (0, 0)
267 if hasattr(xy, '__len__'):
268 if len(xy) == len(images):
269 xy = [xxyy for xxyy in xy]
270 else:
271 raise ValueError("len(xy) doesn't match amount of images.")
272 else:
273 xy = [xy for im in images]
274 xy[0] = (0, 0)
275
276 else:
277 # Calculate xy using some basic image processing
278
279 # Check Numpy
280 if np is None:
281 raise RuntimeError("Need Numpy to use auto-subRectangles.")
282
283 # First make numpy arrays if required
284 for i in range(len(images)):
285 im = images[i]
286 if isinstance(im, Image.Image):
287 tmp = im.convert() # Make without palette
288 a = np.asarray(tmp)
289 if len(a.shape) == 0:
290 raise MemoryError("Too little memory to convert PIL image to array")
291 images[i] = a
292
293 # Determine the sub rectangles
294 images, xy = self.getSubRectangles(images)
295
296 # Done
297 return images, xy
298
299 def getSubRectangles(self, ims):
300 """ getSubRectangles(ims)
301
302 Calculate the minimal rectangles that need updating each frame.
303 Returns a two-element tuple containing the cropped images and a
304 list of x-y positions.
305
306 Calculating the subrectangles takes extra time, obviously. However,
307 if the image sizes were reduced, the actual writing of the GIF
308 goes faster. In some cases applying this method produces a GIF faster.
309
310 """
311
312 # Check image count
313 if len(ims) < 2:
314 return ims, [(0, 0) for i in ims]
315
316 # We need numpy
317 if np is None:
318 raise RuntimeError("Need Numpy to calculate sub-rectangles. ")
319
320 # Prepare
321 ims2 = [ims[0]]
322 xy = [(0, 0)]
323 t0 = time.time()
324
325 # Iterate over images
326 prev = ims[0]
327 for im in ims[1:]:
328
329 # Get difference, sum over colors
330 diff = np.abs(im-prev)
331 if diff.ndim == 3:
332 diff = diff.sum(2)
333 # Get begin and end for both dimensions
334 X = np.argwhere(diff.sum(0))
335 Y = np.argwhere(diff.sum(1))
336 # Get rect coordinates
337 if X.size and Y.size:
338 x0, x1 = X[0], X[-1] + 1
339 y0, y1 = Y[0], Y[-1] + 1
340 else: # No change ... make it minimal
341 x0, x1 = 0, 2
342 y0, y1 = 0, 2
343
344 # Cut out and store
345 im2 = im[y0:y1, x0:x1]
346 prev = im
347 ims2.append(im2)
348 xy.append((x0, y0))
349
350 # Done
351 # print('%1.2f seconds to determine subrectangles of %i images' %
352 # (time.time()-t0, len(ims2)))
353 return ims2, xy
354
355 def convertImagesToPIL(self, images, dither, nq=0):
356 """ convertImagesToPIL(images, nq=0)
357
358 Convert images to Paletted PIL images, which can then be
359 written to a single animaged GIF.
360
361 """
362
363 # Convert to PIL images
364 images2 = []
365 for im in images:
366 if isinstance(im, Image.Image):
367 images2.append(im)
368 elif np and isinstance(im, np.ndarray):
369 if im.ndim == 3 and im.shape[2] == 3:
370 im = Image.fromarray(im, 'RGB')
371 elif im.ndim == 3 and im.shape[2] == 4:
372 im = Image.fromarray(im[:, :, :3], 'RGB')
373 elif im.ndim == 2:
374 im = Image.fromarray(im, 'L')
375 images2.append(im)
376
377 # Convert to paletted PIL images
378 images, images2 = images2, []
379 if nq >= 1:
380 # NeuQuant algorithm
381 for im in images:
382 im = im.convert("RGBA") # NQ assumes RGBA
383 nqInstance = NeuQuant(im, int(nq)) # Learn colors from image
384 if dither:
385 im = im.convert("RGB").quantize(palette=nqInstance.paletteImage())
386 else:
387 # Use to quantize the image itself
388 im = nqInstance.quantize(im)
389 images2.append(im)
390 else:
391 # Adaptive PIL algorithm
392 AD = Image.ADAPTIVE
393 for im in images:
394 im = im.convert('P', palette=AD, dither=dither)
395 images2.append(im)
396
397 # Done
398 return images2
399
400 def writeGifToFile(self, fp, images, durations, loops, xys, disposes):
401 """ writeGifToFile(fp, images, durations, loops, xys, disposes)
402
403 Given a set of images writes the bytes to the specified stream.
404
405 """
406
407 # Obtain palette for all images and count each occurance
408 palettes, occur = [], []
409 for im in images:
410 #palette = getheader(im)[1]
411 palette = im.palette.getdata()[1]
412 if not palette:
413 palette = PIL.ImagePalette.ImageColor
414 if isinstance(palette, type(os)):
415 # Older or newer? version of Pil(low)
416 #data = im.palette.getdata()
417 #palette = data[0].encode('utf-8') + data[1]
418 # Arg this does not work. Go use imageio
419 raise RuntimeError('Cannot get palette. '
420 'Maybe you should try imageio instead.')
421 palettes.append(palette)
422 for palette in palettes:
423 occur.append(palettes.count(palette))
424
425 # Select most-used palette as the global one (or first in case no max)
426 globalPalette = palettes[ occur.index(max(occur)) ]
427
428 # Init
429 frames = 0
430 firstFrame = True
431
432 for im, palette in zip(images, palettes):
433
434 if firstFrame:
435 # Write header
436
437 # Gather info
438 header = self.getheaderAnim(im)
439 appext = self.getAppExt(loops)
440
441 # Write
442 fp.write(header.encode('utf-8'))
443 fp.write(globalPalette)
444 fp.write(appext.encode('utf-8'))
445
446 # Next frame is not the first
447 firstFrame = False
448
449 if True:
450 # Write palette and image data
451
452 # Gather info
453 data = getdata(im)
454 imdes, data = data[0], data[1:]
455 graphext = self.getGraphicsControlExt(durations[frames],
456 disposes[frames])
457 # Make image descriptor suitable for using 256 local color palette
458 lid = self.getImageDescriptor(im, xys[frames])
459
460 # Write local header
461 if (palette != globalPalette) or (disposes[frames] != 2):
462 # Use local color palette
463 fp.write(graphext.encode('utf-8'))
464 fp.write(lid.encode('utf-8')) # write suitable image descriptor
465 fp.write(palette) # write local color table
466 fp.write('\x08'.encode('utf-8')) # LZW minimum size code
467 else:
468 # Use global color palette
469 fp.write(graphext.encode('utf-8'))
470 fp.write(imdes) # write suitable image descriptor
471
472 # Write image data
473 for d in data:
474 fp.write(d)
475
476 # Prepare for next round
477 frames = frames + 1
478
479 fp.write(";".encode('utf-8')) # end gif
480 return frames
481
482
483## Exposed functions
484
485def writeGif(filename, images, duration=0.1, repeat=True, dither=False,
486 nq=0, subRectangles=True, dispose=None):
487 """ writeGif(filename, images, duration=0.1, repeat=True, dither=False,
488 nq=0, subRectangles=True, dispose=None)
489
490 Write an animated gif from the specified images.
491
492 Parameters
493 ----------
494 filename : string
495 The name of the file to write the image to.
496 images : list
497 Should be a list consisting of PIL images or numpy arrays.
498 The latter should be between 0 and 255 for integer types, and
499 between 0 and 1 for float types.
500 duration : scalar or list of scalars
501 The duration for all frames, or (if a list) for each frame.
502 repeat : bool or integer
503 The amount of loops. If True, loops infinitetely.
504 dither : bool
505 Whether to apply dithering
506 nq : integer
507 If nonzero, applies the NeuQuant quantization algorithm to create
508 the color palette. This algorithm is superior, but slower than
509 the standard PIL algorithm. The value of nq is the quality
510 parameter. 1 represents the best quality. 10 is in general a
511 good tradeoff between quality and speed. When using this option,
512 better results are usually obtained when subRectangles is False.
513 subRectangles : False, True, or a list of 2-element tuples
514 Whether to use sub-rectangles. If True, the minimal rectangle that
515 is required to update each frame is automatically detected. This
516 can give significant reductions in file size, particularly if only
517 a part of the image changes. One can also give a list of x-y
518 coordinates if you want to do the cropping yourself. The default
519 is True.
520 dispose : int
521 How to dispose each frame. 1 means that each frame is to be left
522 in place. 2 means the background color should be restored after
523 each frame. 3 means the decoder should restore the previous frame.
524 If subRectangles==False, the default is 2, otherwise it is 1.
525
526 """
527
528 # Check PIL
529 if PIL is None:
530 raise RuntimeError("Need PIL to write animated gif files.")
531
532 # Check images
533 images = checkImages(images)
534
535 # Instantiate writer object
536 gifWriter = GifWriter()
537
538 # Check loops
539 if repeat is False:
540 loops = 1
541 elif repeat is True:
542 loops = 0 # zero means infinite
543 else:
544 loops = int(repeat)
545
546 # Check duration
547 if hasattr(duration, '__len__'):
548 if len(duration) == len(images):
549 duration = [d for d in duration]
550 else:
551 raise ValueError("len(duration) doesn't match amount of images.")
552 else:
553 duration = [duration for im in images]
554
555 # Check subrectangles
556 if subRectangles:
557 images, xy = gifWriter.handleSubRectangles(images, subRectangles)
558 defaultDispose = 1 # Leave image in place
559 else:
560 # Normal mode
561 xy = [(0, 0) for im in images]
562 defaultDispose = 2 # Restore to background color.
563
564 # Check dispose
565 if dispose is None:
566 dispose = defaultDispose
567 if hasattr(dispose, '__len__'):
568 if len(dispose) != len(images):
569 raise ValueError("len(xy) doesn't match amount of images.")
570 else:
571 dispose = [dispose for im in images]
572
573 # Make images in a format that we can write easy
574 images = gifWriter.convertImagesToPIL(images, dither, nq)
575
576 # Write
577 fp = open(filename, 'wb')
578 try:
579 gifWriter.writeGifToFile(fp, images, duration, loops, xy, dispose)
580 finally:
581 fp.close()
582
583
584def readGif(filename, asNumpy=True):
585 """ readGif(filename, asNumpy=True)
586
587 Read images from an animated GIF file. Returns a list of numpy
588 arrays, or, if asNumpy is false, a list if PIL images.
589
590 """
591
592 # Check PIL
593 if PIL is None:
594 raise RuntimeError("Need PIL to read animated gif files.")
595
596 # Check Numpy
597 if np is None:
598 raise RuntimeError("Need Numpy to read animated gif files.")
599
600 # Check whether it exists
601 if not os.path.isfile(filename):
602 raise IOError('File not found: ' + str(filename))
603
604 # Load file using PIL
605 pilIm = PIL.Image.open(filename)
606 pilIm.seek(0)
607
608 # Read all images inside
609 images = []
610 try:
611 while True:
612 # Get image as numpy array
613 tmp = pilIm.convert() # Make without palette
614 a = np.asarray(tmp)
615 if len(a.shape) == 0:
616 raise MemoryError("Too little memory to convert PIL image to array")
617 # Store, and next
618 images.append(a)
619 pilIm.seek(pilIm.tell() + 1)
620 except EOFError:
621 pass
622
623 # Convert to normal PIL images if needed
624 if not asNumpy:
625 images2 = images
626 images = []
627 for im in images2:
628 images.append(PIL.Image.fromarray(im))
629
630 # Done
631 return images
632
633
634class NeuQuant:
635 """ NeuQuant(image, samplefac=10, colors=256)
636
637 samplefac should be an integer number of 1 or higher, 1
638 being the highest quality, but the slowest performance.
639 With avalue of 10, one tenth of all pixels are used during
640 training. This value seems a nice tradeof between speed
641 and quality.
642
643 colors is the amount of colors to reduce the image to. This
644 should best be a power of two.
645
646 See also:
647 http://members.ozemail.com.au/~dekker/NEUQUANT.HTML
648
649 License of the NeuQuant Neural-Net Quantization Algorithm
650 ---------------------------------------------------------
651
652 Copyright (c) 1994 Anthony Dekker
653 Ported to python by Marius van Voorden in 2010
654
655 NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994.
656 See "Kohonen neural networks for optimal colour quantization"
657 in "network: Computation in Neural Systems" Vol. 5 (1994) pp 351-367.
658 for a discussion of the algorithm.
659 See also http://members.ozemail.com.au/~dekker/NEUQUANT.HTML
660
661 Any party obtaining a copy of these files from the author, directly or
662 indirectly, is granted, free of charge, a full and unrestricted
663 irrevocable, world-wide, paid up, royalty-free, nonexclusive right and
664 license to deal in this software and documentation files (the "Software"),
665 including without limitation the rights to use, copy, modify, merge,
666 publish, distribute, sublicense, and/or sell copies of the Software, and
667 to permit persons who receive copies from any such party to do so, with
668 the only requirement being that this copyright notice remain intact.
669
670 """
671
672 NCYCLES = None # Number of learning cycles
673 NETSIZE = None # Number of colours used
674 SPECIALS = None # Number of reserved colours used
675 BGCOLOR = None # Reserved background colour
676 CUTNETSIZE = None
677 MAXNETPOS = None
678
679 INITRAD = None # For 256 colours, radius starts at 32
680 RADIUSBIASSHIFT = None
681 RADIUSBIAS = None
682 INITBIASRADIUS = None
683 RADIUSDEC = None # Factor of 1/30 each cycle
684
685 ALPHABIASSHIFT = None
686 INITALPHA = None # biased by 10 bits
687
688 GAMMA = None
689 BETA = None
690 BETAGAMMA = None
691
692 network = None # The network itself
693 colormap = None # The network itself
694
695 netindex = None # For network lookup - really 256
696
697 bias = None # Bias and freq arrays for learning
698 freq = None
699
700 pimage = None
701
702 # Four primes near 500 - assume no image has a length so large
703 # that it is divisible by all four primes
704 PRIME1 = 499
705 PRIME2 = 491
706 PRIME3 = 487
707 PRIME4 = 503
708 MAXPRIME = PRIME4
709
710 pixels = None
711 samplefac = None
712
713 a_s = None
714
715 def setconstants(self, samplefac, colors):
716 self.NCYCLES = 100 # Number of learning cycles
717 self.NETSIZE = colors # Number of colours used
718 self.SPECIALS = 3 # Number of reserved colours used
719 self.BGCOLOR = self.SPECIALS-1 # Reserved background colour
720 self.CUTNETSIZE = self.NETSIZE - self.SPECIALS
721 self.MAXNETPOS = self.NETSIZE - 1
722
723 self.INITRAD = self.NETSIZE/8 # For 256 colours, radius starts at 32
724 self.RADIUSBIASSHIFT = 6
725 self.RADIUSBIAS = 1 << self.RADIUSBIASSHIFT
726 self.INITBIASRADIUS = self.INITRAD * self.RADIUSBIAS
727 self.RADIUSDEC = 30 # Factor of 1/30 each cycle
728
729 self.ALPHABIASSHIFT = 10 # Alpha starts at 1
730 self.INITALPHA = 1 << self.ALPHABIASSHIFT # biased by 10 bits
731
732 self.GAMMA = 1024.0
733 self.BETA = 1.0/1024.0
734 self.BETAGAMMA = self.BETA * self.GAMMA
735
736 self.network = np.empty((self.NETSIZE, 3), dtype='float64') # The network itself
737 self.colormap = np.empty((self.NETSIZE, 4), dtype='int32') # The network itself
738
739 self.netindex = np.empty(256, dtype='int32') # For network lookup - really 256
740
741 self.bias = np.empty(self.NETSIZE, dtype='float64') # Bias and freq arrays for learning
742 self.freq = np.empty(self.NETSIZE, dtype='float64')
743
744 self.pixels = None
745 self.samplefac = samplefac
746
747 self.a_s = {}
748
749 def __init__(self, image, samplefac=10, colors=256):
750
751 # Check Numpy
752 if np is None:
753 raise RuntimeError("Need Numpy for the NeuQuant algorithm.")
754
755 # Check image
756 if image.size[0] * image.size[1] < NeuQuant.MAXPRIME:
757 raise IOError("Image is too small")
758 if image.mode != "RGBA":
759 raise IOError("Image mode should be RGBA.")
760
761 # Initialize
762 self.setconstants(samplefac, colors)
763 self.pixels = np.fromstring(image.tostring(), np.uint32)
764 self.setUpArrays()
765
766 self.learn()
767 self.fix()
768 self.inxbuild()
769
770 def writeColourMap(self, rgb, outstream):
771 for i in range(self.NETSIZE):
772 bb = self.colormap[i, 0]
773 gg = self.colormap[i, 1]
774 rr = self.colormap[i, 2]
775 outstream.write(rr if rgb else bb)
776 outstream.write(gg)
777 outstream.write(bb if rgb else rr)
778 return self.NETSIZE
779
780 def setUpArrays(self):
781 self.network[0, 0] = 0.0 # Black
782 self.network[0, 1] = 0.0
783 self.network[0, 2] = 0.0
784
785 self.network[1, 0] = 255.0 # White
786 self.network[1, 1] = 255.0
787 self.network[1, 2] = 255.0
788
789 # RESERVED self.BGCOLOR # Background
790
791 for i in range(self.SPECIALS):
792 self.freq[i] = 1.0 / self.NETSIZE
793 self.bias[i] = 0.0
794
795 for i in range(self.SPECIALS, self.NETSIZE):
796 p = self.network[i]
797 p[:] = (255.0 * (i-self.SPECIALS)) / self.CUTNETSIZE
798
799 self.freq[i] = 1.0 / self.NETSIZE
800 self.bias[i] = 0.0
801
802 # Omitted: setPixels
803
804 def altersingle(self, alpha, i, b, g, r):
805 """Move neuron i towards biased (b, g, r) by factor alpha"""
806 n = self.network[i] # Alter hit neuron
807 n[0] -= (alpha * (n[0] - b))
808 n[1] -= (alpha * (n[1] - g))
809 n[2] -= (alpha * (n[2] - r))
810
811 def geta(self, alpha, rad):
812 try:
813 return self.a_s[(alpha, rad)]
814 except KeyError:
815 length = rad * 2-1
816 mid = int(length//2)
817 q = np.array(list(range(mid-1, -1, -1)) + list(range(-1, mid)))
818 a = alpha * (rad * rad - q * q)/(rad * rad)
819 a[mid] = 0
820 self.a_s[(alpha, rad)] = a
821 return a
822
823 def alterneigh(self, alpha, rad, i, b, g, r):
824 if i-rad >= self.SPECIALS-1:
825 lo = i-rad
826 start = 0
827 else:
828 lo = self.SPECIALS-1
829 start = (self.SPECIALS-1 - (i-rad))
830
831 if i + rad <= self.NETSIZE:
832 hi = i + rad
833 end = rad * 2-1
834 else:
835 hi = self.NETSIZE
836 end = (self.NETSIZE - (i + rad))
837
838 a = self.geta(alpha, rad)[start:end]
839
840 p = self.network[lo + 1:hi]
841 p -= np.transpose(np.transpose(p - np.array([b, g, r])) * a)
842
843 #def contest(self, b, g, r):
844 # """ Search for biased BGR values
845 # Finds closest neuron (min dist) and updates self.freq
846 # finds best neuron (min dist-self.bias) and returns position
847 # for frequently chosen neurons, self.freq[i] is high and self.bias[i] is negative
848 # self.bias[i] = self.GAMMA * ((1/self.NETSIZE)-self.freq[i])"""
849 #
850 # i, j = self.SPECIALS, self.NETSIZE
851 # dists = abs(self.network[i:j] - np.array([b, g, r])).sum(1)
852 # bestpos = i + np.argmin(dists)
853 # biasdists = dists - self.bias[i:j]
854 # bestbiaspos = i + np.argmin(biasdists)
855 # self.freq[i:j] -= self.BETA * self.freq[i:j]
856 # self.bias[i:j] += self.BETAGAMMA * self.freq[i:j]
857 # self.freq[bestpos] += self.BETA
858 # self.bias[bestpos] -= self.BETAGAMMA
859 # return bestbiaspos
860 def contest(self, b, g, r):
861 """Search for biased BGR values
862 Finds closest neuron (min dist) and updates self.freq
863 finds best neuron (min dist-self.bias) and returns position
864 for frequently chosen neurons, self.freq[i] is high and self.bias[i]
865 is negative self.bias[i] = self.GAMMA * ((1/self.NETSIZE)-self.freq[i])
866 """
867 i, j = self.SPECIALS, self.NETSIZE
868 dists = abs(self.network[i:j] - np.array([b, g, r])).sum(1)
869 bestpos = i + np.argmin(dists)
870 biasdists = dists - self.bias[i:j]
871 bestbiaspos = i + np.argmin(biasdists)
872 self.freq[i:j] *= (1-self.BETA)
873 self.bias[i:j] += self.BETAGAMMA * self.freq[i:j]
874 self.freq[bestpos] += self.BETA
875 self.bias[bestpos] -= self.BETAGAMMA
876 return bestbiaspos
877
878 def specialFind(self, b, g, r):
879 for i in range(self.SPECIALS):
880 n = self.network[i]
881 if n[0] == b and n[1] == g and n[2] == r:
882 return i
883 return -1
884
885 def learn(self):
886 biasRadius = self.INITBIASRADIUS
887 alphadec = 30 + ((self.samplefac-1)/3)
888 lengthcount = self.pixels.size
889 samplepixels = lengthcount / self.samplefac
890 delta = samplepixels / self.NCYCLES
891 alpha = self.INITALPHA
892
893 i = 0
894 rad = biasRadius * 2**self.RADIUSBIASSHIFT
895 if rad <= 1:
896 rad = 0
897
898 print("Beginning 1D learning: samplepixels = %1.2f rad = %i" %
899 (samplepixels, rad))
900 step = 0
901 pos = 0
902 if lengthcount % NeuQuant.PRIME1 != 0:
903 step = NeuQuant.PRIME1
904 elif lengthcount % NeuQuant.PRIME2 != 0:
905 step = NeuQuant.PRIME2
906 elif lengthcount % NeuQuant.PRIME3 != 0:
907 step = NeuQuant.PRIME3
908 else:
909 step = NeuQuant.PRIME4
910
911 i = 0
912 printed_string = ''
913 while i < samplepixels:
914 if i % 100 == 99:
915 tmp = '\b' * len(printed_string)
916 printed_string = str((i + 1) * 100/samplepixels) + "%\n"
917 print(tmp + printed_string)
918 p = self.pixels[pos]
919 r = (p >> 16) & 0xff
920 g = (p >> 8) & 0xff
921 b = (p) & 0xff
922
923 if i == 0: # Remember background colour
924 self.network[self.BGCOLOR] = [b, g, r]
925
926 j = self.specialFind(b, g, r)
927 if j < 0:
928 j = self.contest(b, g, r)
929
930 if j >= self.SPECIALS: # Don't learn for specials
931 a = (1.0 * alpha) / self.INITALPHA
932 self.altersingle(a, j, b, g, r)
933 if rad > 0:
934 self.alterneigh(a, rad, j, b, g, r)
935
936 pos = (pos + step) % lengthcount
937
938 i += 1
939 if i % delta == 0:
940 alpha -= alpha / alphadec
941 biasRadius -= biasRadius / self.RADIUSDEC
942 rad = biasRadius * 2**self.RADIUSBIASSHIFT
943 if rad <= 1:
944 rad = 0
945
946 finalAlpha = (1.0 * alpha)/self.INITALPHA
947 print("Finished 1D learning: final alpha = %1.2f!" % finalAlpha)
948
949 def fix(self):
950 for i in range(self.NETSIZE):
951 for j in range(3):
952 x = int(0.5 + self.network[i, j])
953 x = max(0, x)
954 x = min(255, x)
955 self.colormap[i, j] = x
956 self.colormap[i, 3] = i
957
958 def inxbuild(self):
959 previouscol = 0
960 startpos = 0
961 for i in range(self.NETSIZE):
962 p = self.colormap[i]
963 q = None
964 smallpos = i
965 smallval = p[1] # Index on g
966 # Find smallest in i..self.NETSIZE-1
967 for j in range(i + 1, self.NETSIZE):
968 q = self.colormap[j]
969 if q[1] < smallval: # Index on g
970 smallpos = j
971 smallval = q[1] # Index on g
972
973 q = self.colormap[smallpos]
974 # Swap p (i) and q (smallpos) entries
975 if i != smallpos:
976 p[:], q[:] = q, p.copy()
977
978 # smallval entry is now in position i
979 if smallval != previouscol:
980 self.netindex[previouscol] = (startpos + i) >> 1
981 for j in range(previouscol + 1, smallval):
982 self.netindex[j] = i
983 previouscol = smallval
984 startpos = i
985 self.netindex[previouscol] = (startpos + self.MAXNETPOS) >> 1
986 for j in range(previouscol + 1, 256): # Really 256
987 self.netindex[j] = self.MAXNETPOS
988
989 def paletteImage(self):
990 """PIL weird interface for making a paletted image: create an image
991 which already has the palette, and use that in Image.quantize. This
992 function returns this palette image."""
993 if self.pimage is None:
994 palette = []
995 for i in range(self.NETSIZE):
996 palette.extend(self.colormap[i][:3])
997
998 palette.extend([0] * (256-self.NETSIZE) * 3)
999
1000 # a palette image to use for quant
1001 self.pimage = Image.new("P", (1, 1), 0)
1002 self.pimage.putpalette(palette)
1003 return self.pimage
1004
1005 def quantize(self, image):
1006 """ Use a kdtree to quickly find the closest palette colors for the pixels """
1007 if get_cKDTree():
1008 return self.quantize_with_scipy(image)
1009 else:
1010 print('Scipy not available, falling back to slower version.')
1011 return self.quantize_without_scipy(image)
1012
1013 def quantize_with_scipy(self, image):
1014 w, h = image.size
1015 px = np.asarray(image).copy()
1016 px2 = px[:, :, :3].reshape((w * h, 3))
1017
1018 cKDTree = get_cKDTree()
1019 kdtree = cKDTree(self.colormap[:, :3], leafsize=10)
1020 result = kdtree.query(px2)
1021 colorindex = result[1]
1022 print("Distance: %1.2f" % (result[0].sum()/(w * h)))
1023 px2[:] = self.colormap[colorindex, :3]
1024
1025 return Image.fromarray(px).convert("RGB").quantize(palette=self.paletteImage())
1026
1027 def quantize_without_scipy(self, image):
1028 """" This function can be used if no scipy is availabe.
1029 It's 7 times slower though.
1030 """
1031 w, h = image.size
1032 px = np.asarray(image).copy()
1033 memo = {}
1034 for j in range(w):
1035 for i in range(h):
1036 key = (px[i, j, 0], px[i, j, 1], px[i, j, 2])
1037 try:
1038 val = memo[key]
1039 except KeyError:
1040 val = self.convert(*key)
1041 memo[key] = val
1042 px[i, j, 0], px[i, j, 1], px[i, j, 2] = val
1043 return Image.fromarray(px).convert("RGB").quantize(palette=self.paletteImage())
1044
1045 def convert(self, *color):
1046 i = self.inxsearch(*color)
1047 return self.colormap[i, :3]
1048
1049 def inxsearch(self, r, g, b):
1050 """Search for BGR values 0..255 and return colour index"""
1051 dists = (self.colormap[:, :3] - np.array([r, g, b]))
1052 a = np.argmin((dists * dists).sum(1))
1053 return a
1054
1055if __name__ == '__main__':
1056 im = np.zeros((200, 200, 3), dtype=np.uint8)
1057 im[10: 30, :, 0] = 100
1058 im[:, 80: 120, 0] = 255
1059 im[-50: -40, :, 0] = 50
1060
1061 images = [im * 1.0, im * 0.8, im * 0.6, im * 0.4, im * 0]
1062 images = [im.astype(np.uint8) for im in images]
1063 writeGif('lala3.gif', images, duration=0.5, dither=0)