images2gif.py 38 KB

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