Pix2SVG - Paletted image to (pixelated geometric) SVG converter

#!/usr/bin/python3

"""
; Pix2SVG - A paletted image to SVG converter
; Version: 1.1.0.0
; (c) Copyright 2025, Daniel Neville

; This program is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 3 of the License, or
; (at your option) any later version.
;
; This program is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
; GNU General Public License for more details.
;
; You should have received a copy of the GNU General Public License
; along with this program. If not, see <https://www.gnu.org/licenses/>.
"""

import os
import sys
import traceback
import math
import numpy as np
import itertools
import re
import html
import argparse
from PIL import Image


VERSION = '1.1.0.0'


class Error (Exception):
  pass

class ArgError (Error):
  pass

class FileError(Error):
  pass

class DataError(Error):
  pass

class CmdError(Error):
  pass


#-----------------------------------------------------------------------------
# Number formatting and text handling functions
# (These should really be in a separate file.)
#-----------------------------------------------------------------------------


# Regular expressions

re_std_decimal_number = fp = re.compile(
    r"^[+-]?([0-9]+\.?[0-9]*|[0-9]*\.?[0-9]+)([Ee][-+]?[0-9]+)?")
re_trailing_zeros = re.compile(r".*?\.[0-9]+?(0+)(?:[Ee][^Ee]*)?$")
re_decimal_zeros = re.compile(r".*?(\.0*)(?:[Ee][^Ee]*)?$")
re_neg_zero = re.compile(
    r"^([-\u2212])(0+\.0*|0*\.0+)([Ee][+-\u2212]?[0-9]+)?$")
re_zero_point = re.compile(r"^[-\u2212+]?(0)\.[0-9].*")


#-----------------------------------------------------------------------------


def remove_trailing_zeros(x, keep_dp=False):
  """Return a string representation of a number with trailing zeros stripped.

  The number may already be a string representation, in which case, any
  spurious trailing decimal point will be removed.

  If keep_dp is False (the default), the removal of trailing zeros extends
  to the removal of the decimal point as well.

  Numbers expressed in E notation are handled correctly.

  This function requires any decimal point to be preceded by a digit.
  """
  s = str(x)
  if m := re_trailing_zeros.match(s):
    span = m.span(1)
    s = s[:span[0]] + s[span[1]:]
  if not keep_dp:
    if m := re_decimal_zeros.match(s):
      span = m.span(1)
      s = s[:span[0]] + s[span[1]:]
  return s


#-----------------------------------------------------------------------------


def nnz_str(s):
  """Strip any leading minus sign if the significand is zero.

  The Unicode minus sign U+2212 may be used as well as the usual U+0045.
  """
  s = str(s)
  return s[1 if re_neg_zero.match(s) else 0:]


#-----------------------------------------------------------------------------


def nzbdp_str(s, keep_zbdp=False):
  """Remove the leading zero before a decimal point for a small number.

  Negative numbers and numbers with negative exponents are handled
  correctly, including those which use the Unicode minus sign U+2212
  instead of the usual U+0045.

  If keep_zbdp is True, this function does no more than the usual
  conversion to a string if the first argument was not a string already.
  """
  s = str(s)
  if not keep_zbdp:
    if m := re_zero_point.match(s):
      span = m.span(1)
      s = s[:span[0]] + s[span[1]:]
  return s


#-----------------------------------------------------------------------------


def max_dp_str_fn(max_dp=6, keep_dp=False, keep_zbdp=True):
  """Return a function which rounds to a given number of decimal places.

  The number of decimal places, whether to always keep the decimal
  point and whether to keep the a leading zero before a decimal point
  is given in this function, which returns a single-argument function
  via partial application.
  """
  if max_dp is None: max_dp = 70
  return lambda x: nzbdp_str(
    remove_trailing_zeros(
      nnz_str(f"{x:.{max_dp}f}"), keep_dp
    ),
    keep_zbdp
  )


#-----------------------------------------------------------------------------


def lines_from_frags(
  frags,
  indent_str=None,
  spacer=" ",
  columns=78,
  head=None,
  tail=None
):
  """Format text fragments into lines.

  This generator function allows the frags argument to be a generator.

  If neither the head nor the tail is specified, the first line will
  begin with indent_str rather than head. In any case, head is expected
  to incorporate its own indentation.

  If head is longer than indent_str, a long fragment which cannot fit
  on the same line as head within the limit specified by columns will
  be placed on the next line, indented. A long fragment which cannot
  properly fit on a line on its own will still have the specified
  indentation.

  if the tail is short (up to four characters), an attempt is made to
  keep the final fragment and the tail together. If tail is on a line of
  its own, that line begins with the same indent as the usual lines.
  """
  indent_str = "" if indent_str is None else str(indent_str)
  default_head = indent_str if head is None and tail is None else ""
  head = default_head if head is None else str(head)
  tail = "" if tail is None else str(tail)
  frag = None
  started = False
  spacer = "" if spacer is None else str(spacer)
  L = []
  line_start = head
  num_chars = len(line_start)
  for next_frag in itertools.chain(frags, (None, None)):
    if started:
      thres = columns
      if frag is not None and next_frag is None:
        if len(tail) < 5:
          thres = min(
            columns,
            max(len(indent_str) + 1, columns - len(tail))
          )
      if frag is None:
        line = line_start + spacer.join(L)
        num_chars = len(line)
        if num_chars + len(tail) <= thres:
          yield line + tail
        else:
          yield line
          yield indent_str + tail
        break
      else:
        frag = str(frag)
        s = len(spacer) if L else 0
        if (num_chars + s + len(frag) <= thres
            or (not L and len(line_start) <= len(indent_str))):
          L.append(frag)
          num_chars += s + len(frag)
        else:
          yield line_start + spacer.join(L)
          L = [frag]
          line_start = indent_str
          num_chars = len(line_start) + len(frag)
    started = True
    frag = next_frag


#-----------------------------------------------------------------------------
# Generic SVG functions
#-----------------------------------------------------------------------------


def svg_path_polygon_frags(polygon, spacing_level=3, max_dp=None):
  """Generate SVG code fragments For a closed polygon loop.

  A polygon is defined as a sequence of 2D absolute coordinates,
  which may be supplied by a generator. The output of this generator
  function is a series of path drawing commands, one command
  per coordinate pair pluf a final "z" command to close the loop.

  The first command will be an absolute move-to command ("M").
  Following commands (before the final "z") will be absolute or
  relative 1D or 2D line-to commands, whichever is most compact.

  The Spacing Level determines the insertion of spaces between the
  drawing command and its coordinate(s) and between the x and y
  parts of the coordinates. A Spacing Level of -1 invokes a compact
  coding permitted by the SVG specification: The leading zeros of
  small decimal numbers are omitted and the comma separator is
  omitted when the following number begins with anything but a digit.

           Between
  Spacing  Command and    Between
  Level    Coordinate(s)  Coordinates

  3+:      one space      one space
  2:       one space      no space
  0, 1:    no space       no space
  -1:      Exclude comma separator and leading zero before a decimal point.
  """
  s = spacing_level if spacing_level is not None else 0
  if max_dp is None: max_dp = 6
  mdp = max_dp_str_fn(max_dp, keep_dp=False, keep_zbdp=True)
  s1 = " " if s >= 2 else ""
  if s < 0:
    mdp1 = max_dp_str_fn(max_dp, keep_dp=False, keep_zbdp=False)
    fmt1 = lambda cmd, x: f"{cmd}{mdp1(x)}"
    fmt2 = lambda cmd, x, y: "".join((cmd, A := mdp1(x),
        "," if ('.' not in A if (B := mdp1(y))[0] == '.'
        else '0' <= B[0] <= '9') else "", B))
  else:
    s2fn = lambda y: ", "[:(s>=3)+(s>=0)|('0'<=(A:=mdp(y))[0]<='9')]+A
    fmt1 = lambda cmd, x: f"{cmd}{s1}{mdp(x)}"
    fmt2 = lambda cmd, x, y: f"{cmd}{s1}{mdp(x)}{s2fn(y)}"
  P = None
  for Q in polygon:
    x = Q[0]
    y = Q[1]
    if P:
      dx = x - P[0]
      dy = y - P[1]
      if dx and dy:
        rel_frag = fmt2('l', dx, dy)
        abs_frag = fmt2('L', x, y)
      else:
        rel_frag = fmt1('h', dx) if dx else fmt1('v', dy)
        abs_frag = fmt1('H', x) if dx else fmt1('V', y)
      yield rel_frag if len(rel_frag) < len(abs_frag) else abs_frag
    else:
      yield fmt2('M', x, y)
    P = Q
  yield 'z'


#-----------------------------------------------------------------------------


def svg_path_multipolygon_lines(
  polygons,
  spacing_level=3,
  max_dp=None,
  indent_str=None,
  columns=78,
  head="",
  tail=""
):
  """Generate SVG code lines For a closed polygon loop.

  A polygon is defined as a sequence of 2D absolute coordinates,
  which may be supplied by a generator. The polygons argument may
  also be a generator. The output of this generator function is a
  series of path drawing commands, one command per coordinate pair
  plus a final "z" command for each polygon.

  For each polygon, the first command will be an absolute move-to
  command ("M"). Following commands (before that polygon's final "z")
  will be absolute or relative 1D or 2D line-to commands, whichever
  is most compact.

  The Spacing Level determines the insertion of spaces between the
  drawing command and its coordinate(s), between the x and y parts of
  the coordinates and between each drawing command.

  A Spacing Level of -1 invokes a compact coding permitted by the SVG
  specification: The leading zeros of small decimal numbers are omitted
  and the comma separator is omitted when the following number begins
  with anything but a digit.

                        Between
  Spacing  Between      Command and    Between
  Level    Commands     Coordinate(s)  Coordinates

  4..10    2..8 spaces  one space      one space
  3:       one space    one space      one space
  2:       one space    one space      no  space
  1:       one space    no space       no space
  0:       no space     no space       no space
  -1:      Exclude comma and leading zero before a decimal point.
  """
  spacer = " "*int(max(1, min(10, spacing_level - 2))*(spacing_level > 0))
  frags = itertools.chain.from_iterable(
    svg_path_polygon_frags(
        polygon,
        spacing_level=spacing_level,
        max_dp=max_dp
    )
    for polygon in polygons
  )
  yield from lines_from_frags(
    frags,
    indent_str=indent_str,
    spacer=spacer,
    columns=columns,
    head=head,
    tail=tail
  )


#-----------------------------------------------------------------------------
# Image functions
#-----------------------------------------------------------------------------


def load_image(filename):
  """Load an image as a numpy array, a palette and a transparency key.

  The returned tuple contains:
  * The image body as a numpy colour index array with the shape (h, w);
  * A palette as a numpy array with the shape (n, 3) and
  * The colour index used as the transparency key or None.
  """
  im = Image.open(filename)
  if im.mode != 'P':
    im = im.convert('P')
    #print("Converted to index-colour image.")
  num_colours = im.getextrema()[1] + 1
  P0 = im.getpalette()[:3*num_colours]
  P = np.array(P0, dtype=np.uint8).reshape((-1, 3))
  key = im.info.get("transparency", None)
  #if key: print(f"Transparency key index = {key}")
  M = np.asarray(im)
  return M, P, key


#-----------------------------------------------------------------------------


def find_novel_colour(palette):
  """Return a RGB tuple of a colour not already in an RGB palette.

  The palette may be flat or in n by 3 format.
  This function is useful for marking colours to be protected from the
  effects of remapping a palette to remove redundancies.
  """
  S0 = (7, 6, 2, 5, 4, 3, 1, 0)
  S1 = (2, 5, 4, 6, 1, 7, 3, 0)
  S2 = (4, 5, 6, 2, 7, 3, 1, 0)
  P1 = np.array(palette, dtype=int).reshape(-1, 3) >> 5
  P2 = np.unique(64*P1[:, 0] + 8*P1[:, 1] + P1[:, 0])
  for i in range(512):
    u = 64*S0[(i>>6)&7] + 8*S1[(i>>3)&7] + S2[i&7]
    if u not in P2:
      break
  col = (
    ((u & 0x1C0)>>1) + 15,
    ((u & 0x038)<<2) + 15,
    ((u & 0x007)<<5) + 15)
  return col


#-----------------------------------------------------------------------------


def loops_from_boolimg(M, evenodd):
  """Return polygon loops tracing the edges of a Boolean image.

  Each loop represents the vertices of a polygon with sides that are
  strictly horizontal or vertical. The polygons contain the elements
  set to True. (If False regions are contained within a given loop,
  other loops will generated to cut holes.)

  If evenodd is True, self-intersecting loops are permitted. This allows
  chequered regions to be efficiently coded as two orthogonal overlapping
  striped.

  If evenodd is False, the loops consist of clockwise loops which may
  surround anticlockwise loops for holes.
  """

  A = np.pad(M, 1)
  NotA = np.logical_not(A)
  Ev = np.logical_xor(A[1:, 1:], A[1:, :-1])
  Eh = np.logical_xor(A[1:, 1:], A[:-1, 1:])

  # Edge flags are centred on pixel corners.
  if evenodd:
    Edn = np.logical_xor(A[1:, 1:], A[1:, :-1])
    Eup = np.pad(Ev[:-1, :], [(1, 0), (0, 0)])
    Eri = np.logical_xor(A[1:, 1:], A[:-1, 1:])
    Ele = np.pad(Eh[:, :-1], [(0, 0), (1, 0)])
  else:
    NotA = np.logical_not(A)
    Edn = np.logical_and(Ev, NotA[1:, 1:])
    Eup = np.pad(np.logical_and(Ev[:-1, :], A[1:-1, 1:]), [(1, 0), (0, 0)])
    Eri = np.logical_and(Eh, A[1:, 1:])
    Ele = np.pad(np.logical_and(Eh[:, :-1], NotA[1:, 1:-1]), [(0, 0), (1, 0)])
    del NotA
  E = sum(Ed * d for Ed, d in ((Eri, 1), (Edn, 2), (Ele, 4), (Eup, 8)))
  del Eri, Edn, Ele, Eup, Eh, Ev, A

  if evenodd:
    search_dirs = [[x & 3 for x in (d, d + 1, d - 1)] for d in range(4)]
  else:
    search_dirs = [[(d + 1 - i) & 3 for i in range(3)] for d in range(4)]

  deltas = ((1, 0), (0, 1), (-1, 0), (0, -1))

  # Search for beginnings of rightward paths segments.
  # The extreme bottom and right edges are excluded from
  # the search but wall-following walks to find loops
  # may include segments on those edges.
  h = M.shape[0]
  w = M.shape[1]
  loops = []
  loops_by_y = [list() for i in range(h)]
  for sy in range(h):
    right0 = False
    for sx in range(w):
      right = E[sy, sx] & 1
      if right and not right0:
        (x, y) = (sx, sy)
        d = 0
        loop = [(x, y)]
        while True:
          E[y, x] &= ~(1 << d)
          dxy = deltas[d]
          (x, y) = (x + dxy[0], y + dxy[1])
          E[y, x] &= ~(1 << (d ^ 2))
          d0 = d
          d = None
          if (x, y) != loop[0]:
            dflags_at_xy = E[y,x]
            for d in search_dirs[d0]:
              if dflags_at_xy & (1 << d):
                break
            if d is None:
              raise Error("Dizzy at ({}, {})!".format(x, y))
            if d != d0:
              loop.append((x, y))
          else:
            break
        if evenodd:
          ax, ay = sx, sy
        else:
          # For the fill-rule of 'nonzero', ensure the vertices start at
          # the leftmost part of the top extremity even for anticlockwise
          # (cutting) loops. For the fill-rule of 'evenodd', all loops
          # that are not self-intersecting are clockwise.
          ay = min(p[1] for p in loop)
          ax = min(p[0] for p in loop if p[1] == ay)
          ai = loop.index((ax, ay))
          loop = loop[ai:] + loop[:ai]
        loops_by_y[ay].append(loop)
      right0 = right
    if not evenodd:
      for loops in loops_by_y:
        loops.sort()
    loops = list(itertools.chain.from_iterable(loops_by_y))
  return loops


#-----------------------------------------------------------------------------


def chamfer_polygon_corners(polygon, r=None):
  """Chamfer the corners of one polygon tracing part of a bi-level image.

  The polygon must have strictly horizontal and vertical sides. No
  chamfering is performed where the self-intersects.

  The length-by-length size of each chamfer is given by r, so that the
  width of the chamfer is r*sqrt(2).

  The number of points will be doubled. As this function is a generator
  function which can accept a generator for the polygon, the yielded
  vertices will correspond to the original polygon starting at its
  second vertex.
  """
  if r is None: r = 0.2
  loop = []
  F0 = F1 = None
  V0 = V1 = V2 = None
  for Z in itertools.chain(polygon, (None, None)):
    V0, V1, V2 = V1, V2, Z
    if Z is None:
      V2, F0 = F0, F1
    if V0 is None:
      F0, F1 = F1, Z
    else:
      dx = r * max(-1, min(1, V0[0] - V1[0]))
      dy = r * max(-1, min(1, V0[1] - V1[1]))
      yield (V1[0] + dx, V1[1] + dy)
      dx = r * max(-1, min(1, V2[0] - V1[0]))
      dy = r * max(-1, min(1, V2[1] - V1[1]))
      yield (V1[0] + dx, V1[1] + dy)


#-----------------------------------------------------------------------------


def chamfer_path_loops(loops, r=None):
  """Chamfer the corners of multiple polygons tracing a bi-level image.

  The polygon must have strictly horizontal and vertical sides. No
  chamfering is performed where the self-intersects.

  The length-by-length size of each chamfer is given by r, so that the
  width of the chamfer is r*sqrt(2).

  The number of points will be doubled. As this function is a generator
  function which can accept a generator for the polygons, the yielded
  vertices for each polygon in loops will correspond to the original
  polygon starting at its second vertex.

  The chamfering is a visual aid to allow one to easily see the paths
  taken by the loops generating function.
  """
  yield from (
    chamfer_polygon_corners(polygon, r)
    for polygon in loops
  )


#-----------------------------------------------------------------------------


def loops_complexity(loops, evenodd):
  """Return a measure of the complexity of a bunch of polygon loops.

  This is used to help find the best (and usually the least complex)
  regions of a particular colour to extract from an image in the hope
  that the holes will be filled by remaining regions of ever-reducing
  complexity.
  """
  return sum(1 + len(L) for L in loops)


#-----------------------------------------------------------------------------


def find_best_colour(img_array, indices, key, evenodd):
  """Find the best colour index ro remove from an image array.

  The best colour to remove is one which has low complexity and
  to a lesser extent one with fewer pixels. The removal of that
  colour is likely to reduce the complexity of the remaining
  colour regions when the non-transparent holes are healed.

  Arguments
    img_array:  An array of colour indices
    indices:    The list (or array) of candidate colour indices
    key:        The transparency key or None
    evenodd:    Allow self-intersecting polygon loops
  """
  M = img_array
  Q = indices
  best = None
  result = None
  for i, col_ix in enumerate(Q):
    if key is None or col_ix != key:
      B = np.equal(M, col_ix)
      area = np.count_nonzero(B)
      loops = loops_from_boolimg(B, evenodd)
      complexity = loops_complexity(loops, evenodd) + area//4
      if best is None or complexity < best:
        best = complexity
        result = i
  return result


#-----------------------------------------------------------------------------


def remove_colour(img_array, target_ix, replacement_ix):
  """Remove a selected colour from an image and try to heal the holes left.

  The colour indices to be removed from img_array are indicated with
  target_ix, leaving non-transparent holes. As far as easily possible,
  those holes are filled to match surrounding regions of colour indices.
  As a last resort, remaining holes will be replaced with replacement_ix.

  This procedure, while expensive, hopes to reduce the geometric complexity
  of regions of colour which remain after a colour index is removed and
  converted to an overlapping filled SVG path.
  """
  M0 = np.asanyarray(img_array)
  count = np.count_nonzero(M0 == target_ix)
  prev_count = count + 1
  while count < prev_count:
    for M1 in (M0, M0.T):
      M = M1
      h, w = M.shape
      for y in range(1, h - 1):
        for x in range(w):
          if M[y, x] == target_ix:
            c = M[y-1, x]
            if M[y+1, x] == c: M[y, x] = c
      for M2 in (M1, np.fliplr(M1)):
        for M in (M2, np.flipud(M2)):
          h, w = M.shape
          for y in range(1, h):
            for x in range(1, w):
              if M[y, x] == target_ix:
                c = M[y, x-1]
                if M[y-1, x] == c: M[y, x] = c
    prev_count = count
    count = np.count_nonzero(M0 == target_ix)
  np.copyto(M0, replacement_ix, where=np.equal(M0, target_ix))
  return M0


#-----------------------------------------------------------------------------


def hex_col_str(rgb, allow12b):
  """Return a CSS-compatible hex colour string from an RGB tuple.

  If allow12b is True, the short, 12-bit representation is returned.
  Thus "#E7A" is returned instead of "#EE77AA", given (0xEE, 0x77, 0xAA).
  """
  clamp = lambda x: max(0, min(255, x))
  S24 = "".join(f"{clamp(round(v)):02X}" for v in rgb)
  S12 = S24[0:5:2]
  S = S12 if allow12b and S12 == S24[1:6:2] else S24
  return f"#{S}"


#-----------------------------------------------------------------------------


def length_and_unit_from_str(length_str):
  """Return a (length value, unit string) tuple from a string."""
  S = str(length_str)
  m = re_std_decimal_number.search(S)
  if m:
    x = m.span(0)[1]
    length = float(S[:x])
    unitstr = S[x:].lstrip()
  else:
    length = None
    unitstr = None
  return length, unitstr


#-----------------------------------------------------------------------------


def svg_colour_loops_lines(
  loops,
  evenodd,
  col_str,
  col_ix=None,
  columns=None,
  spacing_level=None
):
  """Yield lines for the SVG code to represent regions of a single colour.

  Arguments
    loops:    List (or generator) of polygons to fill with colouor
    evenodd:  Indicates the "evenodd" fill rule required by loops
    col_str:  CSS colour string for fill property
    col_ix:   Palette colour index or None (to be output as a comment line)
    columns:  The maximum lime length (sometimes exceeded)
    spacing_level: Spacing methods from -1 to 10
  """
  eostr = 'evenodd' if evenodd else 'nonzero'
  cs = html.escape(col_str)
  if col_ix is not None:
    cis = html.escape(str(col_ix))
    yield f'<!-- Index {cis} -->'
  head = f'<path fill="{cs}" d="'
  yield from svg_path_multipolygon_lines(
    loops,
    spacing_level=spacing_level,
    max_dp=6,
    indent_str=" "*max(0, min(2, int(columns//20))),
    columns=columns,
    head=head,
    tail='"/>'
  )

#-----------------------------------------------------------------------------


def svg_header_lines(
  title,
  w,
  h,
  pixel_shape=None,
  widthstr=None,
  heightstr=None,
  background=None,
  apply_bg=False,
  evenodd=False,
  chamfered_turns=False
):
  """Yield lines for the SVG header and code preceding the SVG colour paths.

  Arguments
    title:        SVG title
    w:            Number of pixels wide
    h:            Number of pixels high
    pixel_shape:  (w, h) tuple of pixel aspect
    widthstr:     SVG length and unit for the physical width
    heightstr:    SVG length and unit for the physical height
    apply_bg:     Output an opaque background rectangle
    background:   CSS colour for background rectangle, if applied
    evenodd:      Indicate the fill rule used is "evenodd".
    chamfered_turns:  Show path courses by chamfering turns.
  """

  mdp = max_dp_str_fn(6, keep_dp=False)
  if title is None:
    title = '(Untitled)'
  if background is None or not background:
    background = 'white'
  if w is None: w = h
  if h is None: h = w
  if w is None: w = h = 16
  w = max(1, w)
  h = max(1, h)
  if pixel_shape is None:
    pixel_shape = (1, 1)
  pixw, pixh = pixel_shape
  mw = w*pixw
  mh = h*pixh
  wsv, wus = length_and_unit_from_str(widthstr)
  hsv, hus = length_and_unit_from_str(heightstr)
  if wsv:
    if not hsv:
      hsv = wsv * mh / mw
      hus = wus
  else:
    if hsv:
      wsv = hsv * mw / mh
      wus = hus
    else:
      wsv = w
      hsv = h
      wus = hus = "px"
  if wus and wus == hus:
    wus = hus = html.escape(wus)
  else:
    wus = hus = "px"
  metric_aspect = mh*pixh/(mw*pixw)
  mectric_is_square = abs(metric_aspect - 1.0) < 1e-7
  #print("Metric Aspect =", metric_aspect)

  if evenodd:
    eodescstr = "Pixelated image as self-intersecting path loops"
    eostr = 'evenodd'
  else:
    eodescstr = "Pixelated image as CW fill loops and CCW cut loops"
    eostr = 'nonzero'

  ts = html.escape(title)
  bgs = html.escape(background)

  yield '<?xml version="1.0" standalone="no"?>'
  yield '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"'
  yield '  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">'
  yield (f'<svg width="{mdp(wsv)}{wus}" height="{mdp(hsv)}{hus}"'
      f' viewBox="0 0 {mw} {mh}"')
  yield '    preserveAspectRatio="none"'
  yield '    xmlns="http://www.w3.org/2000/svg" version="1.1"'
  yield '    xmlns:xlink="http://www.w3.org/1999/xlink">'
  yield f'<title>{ts}</title>'
  if pixw == pixh == 1:
    yield f'<g stroke="none" fill-rule="{eostr}">'
  else:
    yield (f'<g transform="scale({pixw}, {pixh}) '
        f'stroke="none" fill-rule="{eostr}">')
  if apply_bg:
    yield '<!-- Background -->'
    yield (f'<rect x="0" y="0" width="{w}" height="{h}" '
        f'stroke="none" fill="{bgs}"/>')
  yield f'<!-- {eodescstr} -->'


#-----------------------------------------------------------------------------


def svg_footer_lines():
  """Yield the footer lines of SVG code."""
  yield '</g>'
  yield '</svg>'


#-----------------------------------------------------------------------------


def get_arguments():
  """Parse the command line arguments.

  If --help or -V/--version is invoked, the program will exit early.
  """

  cmd = os.path.basename(sys.argv[0])

  parser = argparse.ArgumentParser(
    prog=cmd,
    add_help=False,
    description="Converts a low-res indexed colour image to an SVG."
  )

  parser.add_argument(
      "--help",
      dest="help", action="store_true",
      help="Display this message and exit.")
  parser.add_argument(
      "-t", "--title", metavar="TITLE",
      dest="title", type=str, action="store",
      help=("SVG title"))
  parser.add_argument(
      "-w", "--width", metavar="WIDTH",
      dest="widthstr", type=str, action="store",
      help=("Physical SVG width with unit"))
  parser.add_argument(
      "-h", "--height", metavar="HEIGHT",
      dest="heightstr", type=str, action="store",
      help=("Physical SVG height with unit"))
  parser.add_argument(
      "-k", "--key", metavar="INDEX",
      dest="transparency_key", type=int, default=-1, action="store",
      help="Select the colour index to serve as the transparency key.")
  parser.add_argument(
      "-a", "--apply-bg",
      dest="apply_bg", action="store_true",
      help="Include the filled background rectangle.")
  parser.add_argument(
      "-b", "--bgcol", metavar="BG",
      dest="background", action="store",
      help="CSS-style background colour")
  parser.add_argument(
      "-M", "--no-remap",
      dest="no_remap", action="store_true",
      help="Preserve redundant palette entries.")
  parser.add_argument(
      "-p", "--pixel", metavar="H:W",
      dest="pixel_aspect", action="store",
      help="Pixel aspect ratio (default 1:1)")
  parser.add_argument(
      "-Z", "--frnz",
      dest="evenodd", action="store_false",
      help="Use the (less efficient) SVG path fill rule \"nonzero\" "
           "instead of the default \"evenodd\" rule, which gains its "
           "efficiency from self-intersecting path loops.")
  parser.add_argument(
      "-H", "--holes",
      dest="keep_holes", action="store_true",
      help="Skip the laborious healing of holes, minimising overprinting "
           "and compound aliasing in some SVG renderers at the cost of "
           "increased SVG complexity.")
  parser.add_argument(
      "-C", "--chamfer",
      dest="chamfer", action="store_true",
      help="Chamfer corners to show path loops.")
  parser.add_argument(
      "-c", "--columns", metavar="N",
      dest="columns", type=int, default=78, action="store",
      help="Maximum line width for SVG path data")
  parser.add_argument(
      "-s", "--spacing", metavar="S",
      dest="spacing_level", type=int, default=-1, action="store",
      help="Spacing level (-1..10) for SVG path data")
  parser.add_argument(
      "-P", "--progress-images",
      dest="save_progress_images", action="store_true",
      help="Save numbered progress images.")
  parser.add_argument(
      "-V", "--version",
      dest="version", action="store_true",
      help="Display version and exit.")

  parser.add_argument(
      "filename", metavar="PIMAGE",
      type=str,
      help=("Index-colour (paletted) image to read"))
  parser.add_argument(
      "outfilename", metavar="SVGFILE",
      type=str,
      help=("SVG file to create"))

  if "--help" in sys.argv:
    parser.print_help()
    sys.exit(0)

  if "-V" in sys.argv or "--version" in sys.argv:
    print(VERSION)
    sys.exit(0)

  args = parser.parse_args()

  return args


#-----------------------------------------------------------------------------


def get_pix_shape(shape_str):
  """Parse the pixel aspect ratio argument.

  No attempt is to simplify the ratio (by using gcd(), say), since the
  user may have a special use case which requires integer sub-pixel
  addressing in the same transformation frame as the path data.
  """
  if shape_str is None:
    return (1, 1)
  x = 1
  y = 1
  s = shape_str.lower()
  if ':' in s:
    sep = ':'
  elif ',' in s:
    sep = ','
  elif 'X' in s:
    sep = 'X'
  elif 'x' in s:
    sep = 'x'
  else:
    sep = None
  if sep is None:
    try:
      x = float(s)
    except ValueError:
      x = max(1.0/256.0, min(256.0, x))
      y = 1.0
  else:
    if sep == ',' and len(s) >= 3 and s[0] == '(' and s[-1] == ')':
      s = s[1 :  len(s) - 1]
    fields = s.split(sep)
    try:
      x = int(fields[0])
    except ValueError:
      x = 1
    try:
      y = int(fields[1])
    except ValueError:
      y = 1
    x = max(1, min(256, x))
    y = max(1, min(256, y))
  return (x, y)


#-----------------------------------------------------------------------------


def main():

  result = 0
  err_msg = ''

  cmd = os.path.basename(sys.argv[0])

  try:

    args = get_arguments()

    pixel_shape = get_pix_shape(args.pixel_aspect)
    bgstr = bg if (bg := args.background) is not None and bg else None
    apply_bg = args.apply_bg or bgstr is not None

    progress_img_fmt = f"{args.outfilename}_P{{:03}}.png"
    mask_img_fmt = f"{args.outfilename}_M{{:03}}.png"

    M, P, key = load_image(args.filename)
    if args.transparency_key >= 0:
      key = args.transparency_key
      if key >= len(P):
        key = None

    if args.apply_bg and key is not None and not bgstr:
      bgstr = hex_col_str(P[key], allow12b=True)
      bgstr = {'#000': "black", '#FFF': "white"}.get(bgstr, bgstr)

    kcint0 = 0
    kcint1 = 0
    if not args.no_remap:
      # Remap the palette to eliminate redundant palette entries
      # that would lead to needlessly complex paths.
      if key is not None:
        kc0 = P[key]
        kcint0 = kc0[0]*65536 + kc0[1]*256 + kc0[2]
        kc1 = find_novel_colour(P)
        kcint1 = kc1[0]*65536 + kc1[1]*256 + kc1[2]
      P1 = np.array(P, dtype=int)
      P2 = P1[:, 0]*65536 + P1[:, 1]*256 + P1[:, 2]
      if key is not None:
        P2[key] = kcint1
      P3, remap = np.unique(P2, return_inverse=True)
      M = np.take(remap, M)
      if key is not None:
        key = list(P3).index(kcint1)
        P3[key] = kcint0
      P = np.vstack([P3>>16, (P3>>8) & 255, P3 & 255]).T

    Q = sorted(np.unique(M))
    c0 = key
    count = 0
    if args.save_progress_images:
      img1 = Image.fromarray(M, 'P')
      img1.putpalette(P)
      img1.save(progress_img_fmt.format(count))
    count += 1
    Q1 = np.array(Q)
    done = False
    jobs = []
    while len(Q1) and not done:
      c = M[0, 0]
      if np.array_equiv(M, c):
        if key is None and not bgstr:
          h, w = M.shape
          loops = [[(0, 0), (w, 0), (w, h), (0, h)]]
          jobs.append((c, loops))
        if args.save_progress_images:
          img1 = Image.fromarray(M, 'P')
          img1.putpalette(P)
          img1.save(progress_img_fmt.format(count))
        done = True
      else:
        if args.keep_holes:
          ccii = len(Q1) - 1
          c = Q1[ccii]
          if key is None or c != key:
            B = np.logical_not(M - c);
            loops = loops_from_boolimg(B, args.evenodd)
        else:
          ccii = find_best_colour(M, Q1, c0, args.evenodd)
          c = Q1[ccii]
          if c0 is None:
            c0 = c
          B = np.logical_not(M - c);
          loops = loops_from_boolimg(B, args.evenodd)
          if args.save_progress_images and not args.keep_holes:
            Z = np.array(np.equal(M, c), dtype=np.byte)
            maskimg = Image.fromarray(Z, 'P')
            maskimg.putpalette([0,0,0, 255,255,255])
            maskimg.save(mask_img_fmt.format(count - 1))
          M = remove_colour(M, c, c0)
        Q1 = np.delete(Q1, ccii)
        jobs.append((c, loops))
        if args.save_progress_images and not args.keep_holes:
          img1 = Image.fromarray(M, 'P')
          img1.putpalette(P)
          img1.save(progress_img_fmt.format(count))
      count += 1
    jobs.reverse()

    with open(args.outfilename, 'w') as f:
      header_gen = svg_header_lines(
        title = args.title,
        w = M.shape[1],  # Array shapes are in (h, w) format.
        h = M.shape[0],
        pixel_shape = pixel_shape,  # Pixel shape is in (w, h) format.
        widthstr = args.widthstr,
        heightstr = args.heightstr,
        apply_bg = apply_bg,
        background = bgstr,
        evenodd = args.evenodd,
        chamfered_turns = args.chamfer
      )
      for line in header_gen:
        f.write(f"{line}\n")
      for job in jobs:
        col_ix, loops = job
        rgb = P[col_ix] if col_ix < len(P) else (255, 0, 255)
        cs = hex_col_str(rgb, allow12b=True)
        if args.chamfer:
          loops1 = chamfer_path_loops(loops)
          loops1 = [[V for V in L] for L in loops1]
        else:
          loops1 = loops
        lines = svg_colour_loops_lines(
          loops=loops1,
          evenodd=args.evenodd,
          col_str=cs,
          col_ix=None,
          columns=args.columns,
          spacing_level=args.spacing_level
        )
        for line in lines:
          f.write(f"{line}\n")
      for line in svg_footer_lines():
        f.write(f"{line}\n")

  except ArgError as E:
    err_msg = 'Error: ' + str(E)
    result = 2
  except FileError as E:
    err_msg = str(E)
    result = 3
  except CmdError as E:
    err_msg = str(E)
    result = 4
  except DataError as E:
    err_msg = str(E)
    result = 5
  except Exception as E:
    exc_type, exc_value, exc_traceback = sys.exc_info()
    err_lines = traceback.format_exc().splitlines()
    err_msg = 'Unhandled exception:\n' + '\n'.join(err_lines)
    result = 1

  if err_msg != '':
    print(cmd + ': ' + err_msg, file=sys.stderr)

  return result


#-----------------------------------------------------------------------------


if __name__ == '__main__':
  main()


#-----------------------------------------------------------------------------
# End
#-----------------------------------------------------------------------------