#!/bin/bash
#
# overlap [-v] [WxH+X+Y] larger_image  images_to_overlay...
#
# Given some images, (and optionally a specific area of overlap), try to find
# the appropriate composition offset so as to produce a larger merged image of
# each matching overlap found.
#
# This works by croping out areas to do a sub-image search against
# all the other provided images.  This means that given N imgs and
# the default 9 crops, it will do  9*N*(N-1) sub-image searches.
#
# Alternativally you an specify a known areas of overlap to search for.
#
# NOTES:
#   * The program will try to match each image against the other.  Whcih image
#     is on top depends on the image order.
#   * Any transparency is preserved, but this is replaced by 50% gray for
#     sub-image matching to lessen its involvement. As such avoid transparency
#     in the areas being used to find the overlap.
#   * Transparency is preserved in the merged images.
#   * You can add images to the previously found merged images.
#
# This program is raw and highly experimental. It will require tweeking to get
# it to work with images other than the 'game maps' I have been using it for.
#
# Anthony Thyssen    3 October 2012
#
PROGNAME=`type $0 | awk '{print $3}'`  # search for executable on path
PROGDIR=`dirname $PROGNAME`            # extract directory of program
PROGNAME=`basename $PROGNAME`          # base name of program

# Fully qualify directory path (remove relative components and symlinks)
ORIGDIR=`pwd`                                 # original directory (builtin)
PROGDIR=`cd $PROGDIR && pwd || echo $PROGDIR` # program directory

Usage() {                              # Usage line (from above) only
  echo >&2 "$PROGNAME:" "$@"
  sed >&2 -n '/^###/q; /^#/!q; s/^#//; 3s/^  */Usage: /p; 4q' \
          "$PROGDIR/$PROGNAME"
  exit 10;
}

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

# Size of the sub-images to search for
radius="4"
size=`expr $radius \* 2 + 1`

edge_radius=$size  # keep sub-images this far from edges.

while [  $# -gt 0 ]; do
  case "$1" in

  # Standard help option.
  -\?|-help|--help|--doc*) Usage ;;

  -v) VERBOSE=true ;;

# [0-9]*x[0-9]*)
#     size="$1" ;;
# +*) offsets="$1" ;;

  --) shift; break ;;    # forced end of user options
  -*) Usage "Unknown option \"$1\"" ;;
  *)  break ;;           # unforced  end of user options

  esac
  shift   # next option
done

# ----------

# work out next number for the combined (overlapping) imgs
prefix="merged_"
suffix="png"
num=`ls $prefix*.$suffix 2>/dev/null | tail -n1 | sed 's/[^0-9]//g'`
[ ! "$num" ] && num=0     # set to zero if no previous file found


# Create a temporary directory for working images.
# With auto-cleanup
tmpdir=`mktemp -d "${TMPDIR:-/tmp}/$PROGNAME.XXXXXXXXXX"` ||
  { echo >&2 "$PROGNAME: Unable to create temporary directory"; exit 1;}
trap 'rm -rf "$tmpdir"' 0   # remove when finished (on end or exit)
trap 'exit 2' 1 2 3 15      # terminate script on signal (don't just die)


# main loop.

img1="$1"; shift

while [ $# -ne 0 ]; do
  img2="$1"; shift
  [ "$img1" = "$img2" ] && continue
  echo "comparing parts of \"$img2\" against \"$img1\""

  # See discussion on forums...
  #     f=1&t=22526&p=94864
  # To become a tutorial...
  #
  # ASIDE:
  #   map_052_la_duex  goes wrong (ocean in 0,0 offset)
  #

  # Create a mask of points which have acceptable entropy
  # That is points along edges and boundaries of color areas.

  magick $img2  \
          \( -clone 0 -magick segment 1 -median 3 \
             -morphology Edge Diamond \
             -morphology thinning:2 Skeleton \
             -channel RGB -separate +channel \
             -compose screen -flatten -compose over \
             -threshold 10% \
          \) \
          \( -clone 0 -alpha extract -virtual-pixel black \
             -morphology erode Square:$edge_radius \
          \) \
          -delete 0 -compose multiply -composite -compose over \
          $tmpdir/acceptable.miff

  # DEBUG: checking 'entropy' results...
  #flicker_cmp -s 300% $img2 $tmpdir/acceptable.miff &

  # Extract a maximally distributed list of points from this map.
  # The first point is tricky, find a point closest to a corner
  #
  # This generates a distance gradient, from all four corners, masks,
  # and returns the point with a minimal distance.
  #
  read -r x y dist < <(
    magick $tmpdir/acceptable.miff \
            \( +clone -threshold -1 \
               -fill black -draw 'rectangle 0,0 1,1' -roll -1-1 \
               -virtual-pixel white -morphology Distance Euclidean:2 \
            \) -compose multiply -composite -compose over \
            -depth 16 txt:- |
      tr -sc '0-9\012' ' ' |
        awk 'NR==1 { min=1e8; next; }
             $3 > 0 && $3 < min { x=$1; y=$2; min=$3; }
             END { print x,y,min; }'
      )

  # Okay we have the first valid point for a sub-image search.
  # now set up a distribution map for later use.
  magick $tmpdir/acceptable.miff -threshold -1 \
          -fill black -draw "point $x,$y" \
          $tmpdir/distribute.miff

  point=1
  dist=1000000   # first point has no minimum distances to neighbour

  cp $tmpdir/distribute.miff $tmpdir/distance.miff
  magick display ephemeral:$tmpdir/distance.miff &
  while [ -f $tmpdir/distance.miff ]; do
    usleep 100
  done


  # Loop over each sub-image point.
  while [ $dist -ge ${edge_radius}00 ]; do
    echo "Processing sub-image #$point centered at $x,$y (sep=$dist)"

    # .... Process here ....

    # find the next acceptable point for a sub-image search
    # that is at a maximum distance from all other points
    # we have so far found, and saved in the 'distribute map'.

    read -r x y dist < <(
      magick $tmpdir/distribute.miff -morphology Distance Euclidean:2 \
              \( +clone -auto-level -write $tmpdir/distance.miff +delete \) \
              $tmpdir/acceptable.miff -compose multiply -composite \
              -depth 16 txt:- |
      tr -sc '0-9\012' ' ' |
        awk 'NR==1 { next; }
             $3 > max { x=$1; y=$2; max=$3; }
             END { print x,y,max; }'
      )
    magick display -remote ephemeral:$tmpdir/distance.miff
    while [ -f $tmpdir/distance.miff ]; do
     usleep 100
    done

    # Add this new point to the distribution map (for next selection)
    magick $tmpdir/distribute.miff \
            -fill black -draw "point $x,$y" \
            $tmpdir/distribute.miff

    point=$((point+1))

    # loop to process this new acceptable sub-image location
  done
  exit 0

# .....
  for offset in $offsets; do
    read -r ox oy <<< `echo $offset | tr + ' ' `
    # break this pipeline up - unsing temporary image files.
    # Check subimage and ignore if
    #  * if it contains transparency
    #  * if standard deviation is less than 1000/65535
    #
    # Basically ensure the crop areas has a high entropy.
    #
    coords=`
      magick "$img1" "$img2" \
              -background grey -alpha remove -alpha off \
              \( +clone -crop "$size$offset" +repage \) \
              +swap +delete miff:- |\
      magick compare -subimage-search - miff:- | \
      magick - +swap +delete +depth txt:- | \
      tail -n+2 | tr -cs '0-9\n' ' ' | sort -rn -t\  -k3 | tail -n-1 `

    read -r x y match junk <<< "$coords"
    x=$(( $x - $ox ))
    y=$(( $y - $oy ))

    if [ $match -lt 10000 ]; then

      echo "-> offset $offset -> results: +$x+$y ($match) GOOD"

      # merge images and save into next numbered file.
      num=`expr $num + 1`
      num=`printf %03d $num`
      output_image="$prefix$num.$suffix"

      # Check if numbered file exists, touch it, else loop to next number!
      echo "   $img1 -page +$x+$y $img2 -> \"$output_image\""

      # Output a merged img
      magick "$img1" -page "+$x+$y" "$img2" \
              -background none -layers merge +repage "$output_image"
      magick display "$output_image" & # magick display it when found

      # Abort loop to next match if we are no longer getting bad
      # area matching.
    elif [ "$VERBOSE" ]; then
      echo "-> offset $offset -> results: +$x+$y ($match) BAD"
    fi

  done

  # if there is another image.  Switch $img1 to the best merged image
  # then continue with next image

done