Locate API performance issues

[splondike]

There are a couple of conditions under which the locate API can perform slowly (multiple seconds):

• Searching over large screen resolutions (e.g. retina).
• When the locate API finds a large number of matches.

The following Python code and attached image demonstrate the second case. The code attempts to find the Slack 'hash' icon and also a small white patch. The hash icon search gets 15 hits and takes ~0.5s. The white patch search gets 2 million hits and takes around 15-20s. I ran into this issue while building the talon UI helper package that allows users to lasso select regions and displays matches live on the screen. The user might inadvertently select something like the white patch and lock up the system.

Some mechanisms we discussed for improving performance were: exact matching, image pyramids, and multithreading. Having a maximum number of returned results is another option, but that may not be available from the OpenCV API.

import os
import time
import numpy as np
from talon.skia.image import Image
from talon.experimental import locate

def crop_image(image_np, x1, y1, x2, y2):
    return Image.from_array(
        image_np[y1:y2,x1:x2]
    )

image_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), "one-monitor-screenshot.png")
screenshot_image = Image.from_file(image_path)
screenshot_image_np = np.array(screenshot_image)

hash_icon_image = crop_image(screenshot_image_np, 30, 325, 43, 341)
# hash_icon_image.write_file("/tmp/hash-icon.png")
white_patch_image = crop_image(screenshot_image_np, 241, 334, 250, 344)
# white_patch_image.write_file("/tmp/white_patch.png")

for label, image in [("hash icons", hash_icon_image), ("white patches", white_patch_image)]:
    start = time.time()
    results = locate.locate_in_image(
        screenshot_image,
        image,
        threshold=0.99
    )
    end = time.time()
    # I get 15 in 0.42s and 2047752 in ~16s respectively for this on my i7-2620M @ 2.7GHz CPU running Linux
    print(f"Found {len(results)} {label} in {end-start:.2f}s")

[splondike]

To give a rough idea of the potential performance gains from the image pyramid I tried matching both the hash icon and the white patch on a 4x scaled down image using the existing locate API. I got 0.08s from that for the hash icon and 1.2s for the white patch, and that time includes the time spent resising the template and target images (using Image.reshape).

So that's approximately a 10x improvement. Of course you'd then need to match on the full resolution as well so it wouldn't be that good, but you could use this quick pass to discard API calls that returned too many matches (the white patch still returned 100,000+ matches) as well as doing the normal image pyramid algorithm.

[splondike]

Using similar code to the above with the default Talon threshold value of 0.99 searching for the attached images gives me ~2000 matches with the locate_in_image algorithm in 305-g968a and 1 match for 0.2.3 . If I increase the threshold to 0.999 I get 1 (correct) match in both.

The first match is 'the right one' with the beta's locate API. It just feels like the threshold could be increased so as to better handle the default case of trying to find an exact match for an image on a screenshot. The risk of course would be increasing false negatives.

[splondike]

Found a case with beta -305-g968a where the correct match was not the first nor last result. See the following code when run with screenshot-large.png and needle.png. v0.2.3's implementation returns a single correct result in both cases.

import os
from talon.skia.image import Image
from talon.experimental import locate

screenshot_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), "screenshot-large.png")
needle_path = os.path.join(os.path.dirname(os.path.abspath(__file__)), "needle.png")
screenshot_image = Image.from_file(screenshot_path)
needle_image = Image.from_file(needle_path)

results = locate.locate_in_image(
    screenshot_image,
    needle_image
)
print(results[:3])
# screenshot-large.png: [Rect(1613, 977, 16, 23), ...91 others] . This is down in the black area at the bottom of the window. The correct result is at position 52, neither the start nor the end.
# screenshot-small.png: [Rect(774, 51, 16, 23), ...1 other] . This is the correct first match.

And these three images (needle.png, screenshot-large.png, screenshot-small.png):

[wolfmanstout]

Here is an example (Gmail "expand all" button) where a bunch of spurious findings are within empty black space in the taskbar:
Icon:

Works fine on public Talon (0.2.3).

[lunixbochs]

Times are from locate_in_image() on an M1 Max with the next Talon beta release.

Notes from profiling:

• I've found these times to be overwhelmingly caused by the image load now rather than the match itself
• if you call locate() (which uses a fresh screenshot already stored in memory) I've found performance to be much faster
• on a 75ms locate_in_image():
  • 40ms loading the large image (to be searched)
  • 20ms calculating an integral image for the large image
  • 10ms for the actual image match
  • the rest is overhead / variance

This also means with the current algorithm I can possibly do parallel searches at a cost of under 5ms per additional search image.

#456 (comment)

40ms, one match: [Rect(711, 27, 30, 29)]

#456 (comment)

Large image: 68ms, one match: [Rect(1880, 163, 16, 23)]
Smaller image: 11ms, one match: [Rect(774, 51, 16, 23)]

#456 (comment)

76ms, one match: [Rect(2185, 217, 39, 29)]

Considering this fixed in next beta.