1#!/usr/bin/env python3
2"""
3This "copies" the crop of one image pair to another.
4
5Suppose we have a pair of images, one which has been cropped from
6the other:
7
8    +----------+
9    |x.x.111.x.|                +-----+
10    |.x.x.x.x.x|      --->      |x.111|
11    |x.x.x.x.x.|                +-----+
12    +----------+
13
14This script will identify where the cropped image came from the
15bigger image, then apply that crop to a second image which has the
16same dimensions:
17
18    +----------+
19    |.y.y222.y.|                +-----+
20    |y.y.y.y.y.|      --->      |y222.|
21    |.y.y.y.y.y|                +-----+
22    +----------+
23
24This is a very rudimentary form of "template matching" [1].  It relies
25on the first pair of images being only a crop, and not modified in any
26other way.  This is the case for images I've made (screenshots), but
27it may fail if the image has been processed in other ways.
28
29See the README for a more visual example.
30
31[1]: https://en.wikipedia.org/wiki/Template_matching
32
33"""
34
35import argparse
36import collections
37import itertools
38import os
39
40from PIL import Image
41from PIL import ImageChops
42
43
44def parse_args():
45    parser = argparse.ArgumentParser(
46        prog="copycrop", description="Copy the crop from one image to another"
47    )
48
49    parser.add_argument("ORIGINAL_IMAGE_1")
50    parser.add_argument("CROPPED_IMAGE_1")
51    parser.add_argument("ORIGINAL_IMAGE_2")
52
53    return parser.parse_args()
54
55
56def find_crop_region(original: Image, cropped: Image):
57    """
58    Given the pair of images, work out where the cropped image appears
59    in the original.
60
61    This returns a 4-tuple (left, top, right, bottom) which can be passed
62    into the Image.crop method, e.g. (990, 332, 1864, 677).
63
64    == How it works ==
65
66    We look at the palette of both images, and in particular colours which
67    appear in both.  Then we compare their relative positions, and use them
68    to "guess" some possible candidates for the crop.
69
70    e.g. if there's a single red pixel in both images, which:
71
72    * appears at (10, 10) in the original image
73    * appears at (1, 1) in the cropped image
74
75    then we can guess this is the same red pixel, and try a crop that
76    starts at (10, 10).
77
78    """
79    original_palette = collections.Counter(original.getdata())
80    cropped_palette = collections.Counter(cropped.getdata())
81
82    least_frequent_colour = min(
83        cropped_palette, key=lambda c: original_palette[c] * cropped_palette[c]
84    )
85
86    original_pixels = original.load()
87
88    matching_original_coordinates = {
89        (x, y)
90        for x in range(original.width)
91        for y in range(original.height)
92        if original_pixels[x, y] == least_frequent_colour
93    }
94
95    cropped_pixels = cropped.load()
96
97    matching_crop_coordinates = {
98        (x, y)
99        for x in range(cropped.width)
100        for y in range(cropped.height)
101        if cropped_pixels[x, y] == least_frequent_colour
102    }
103
104    for (original_x, original_y), (cropped_x, cropped_y) in itertools.product(
105        matching_original_coordinates, matching_crop_coordinates
106    ):
107        left = original_x - cropped_x
108        top = original_y - cropped_y
109
110        crop_info = (
111            left,
112            top,
113            left + cropped.width,
114            top + cropped.height,
115        )
116
117        new_crop = original.crop(crop_info)
118
119        diff = ImageChops.difference(cropped, new_crop)
120        if diff.getbbox() is None:
121            return crop_info
122
123    raise RuntimeError("Could not find cropped image inside original image!")
124
125
126if __name__ == "__main__":
127    args = parse_args()
128
129    original_im_1 = Image.open(args.ORIGINAL_IMAGE_1)
130    original_im_2 = Image.open(args.ORIGINAL_IMAGE_2)
131
132    if original_im_1.size != original_im_2.size:
133        raise ValueError("Original images must have the same dimensions!")
134
135    cropped_im_1 = Image.open(args.CROPPED_IMAGE_1)
136
137    crop_region = find_crop_region(original_im_1, cropped_im_1)
138
139    cropped_im_2 = original_im_2.crop(crop_region)
140
141    name, ext = os.path.splitext(args.ORIGINAL_IMAGE_2)
142    out_path = f"{name}.cropped.{ext}"
143    cropped_im_2.save(out_path)
144    print(out_path)