Perceptual Hash Matching Experimentation

[erickolb]

I've done some research into the viability, efficacy, and performance of perceptual hash matching for image covers, which I've talked about with @bpepple over email.

Experimental branch: https://github.com/erickolb/metron/tree/experiment/perceptual-hash-matching
Results and Report: https://erickolb.github.io/metron/Metron-CPH-Experiment/

Scanning 138 different comic covers over a local field of just over 40,000 cover hashes, the perceptual hash matching had a success rate (i.e. the correct comic was matched) 92% of the time, 79% on the first attempt.

This feature would require clients to implement their own cover image capture and hash functions (which is what I would do from my personal client), so the API calls would have negligible impact on bytes-over-the-wire. The concern would primarily be how much work Postgres has to do on the back end. I don't have benchmarks for metron.cloud performance under load, but in my local test environment I observed a mean of 47ms for the DB matching.

I think it's worth adding support for the matching to the API, perhaps with a weight to the API call to compensate for the server side performance.

[bpepple]

Thanks for putting this together, @erickolb. I agree that cover matching by perceptual hash is a good addition to the API and worth the time to implement. I did have some concerns about the complexity and long-term maintainability of the experimental implementation, mainly the raw SQL, the custom response format, and the migration and S3 backfill that variant support needs. So this morning I worked a simpler alternative that builds on your work. The experiment and especially the archived scan data were really helpful, and here's where it landed. The code is on the filter-api-by-phash branch (diff against master).

What I went with

Instead of a separate endpoint, I added the search as a filter on the existing issue list:

GET /api/issue/?cover_hash_near=c585eb18bf1e5423
GET /api/issue/?cover_hash_near=c585eb18bf1e5423&cover_hash_max_distance=12&series_id=123

• Returns every issue whose main cover hash is within cover_hash_max_distance bits of the query (default 16, max 24), sorted closest first.
• It's paginated and can be combined with the other issue filters (series_id, publisher_id, cover_year, etc.), so a client can narrow the search if it already knows something about the comic.
• The response is the normal issue list, which already includes each issue's cover_hash, so clients can compute the exact distance themselves.
• Invalid hashes or distances return a 400, and these searches skip the response cache, since a scanned hash is effectively never repeated.

The main reason for this shape is maintenance. There's no migration, no new response format, and no raw SQL, and it fits the existing filters, pagination, and OpenAPI schema. Like your version, it compares against every stored hash. On a copy of production data (~184k hashes) a request takes about 90 ms at the default distance, including the count query pagination needs. If that ever becomes a problem, we can move to a stored integer column like yours without changing the API.

How your data shaped it

I originally used a default max distance of 10. In your 127 successful scans, though, the correct cover was 2–16 bits off (median 10), so only 57% were within 10. The closest wrong cover was 12–18 bits off. Since the two ranges overlap, a threshold can't really separate right from wrong. I raised the default to 16 and rely on closest-first ordering to put the right comic at the top, which is what your top-8 approach was already doing. On production, with a dataset roughly 4–5× larger than your test set, wrong covers will probably sit even closer, so I think ordering is the right thing to lean on.

If we go with this implementation, I'd want to do more testing to make sure we use a good default distance.

What I left out for now

• Variant covers. Your data showed about 7% of matches came through a variant, so it's not nothing. But it needs a migration, a backfill that downloads every variant image from S3, and an image download on every variant save. I'd rather start with main covers and add variants later. Your Variant.cover_hash field and backfill command would be a good starting point when we do.
• distance / matched_cover in the response. Clients can compute the distance from cover_hash, and keeping the standard list response means one less format to maintain.

Open questions

1. Rate limiting. You suggested giving this search more weight against the rate limit. At ~90 ms it seems affordable, but it is heavier than a typical list query. Do you think a separate, tighter limit is worth it? I'm not sure, but it might be worth thinking about.
2. Max distance. At 24, a search returns thousands of mostly unrelated issues. Would a cap of 20 be enough based on what you saw?

[erickolb]

RE: Rate limiting. I haven't looked at how limiting is enforced, but I don't think it needs a separate limit. Is it possible or reasonable to just say "this is a more expensive op, it has a multiplier applied towards your minute/daily limit"? The process of snapping a picture, tapping the buttons through to kick off a search... that's 10-15 seconds of using the interface. And that's in a tight test loop where I'm not doing anything with the results except checking that there was a match. By a natural reckoning of time use, weighting the API call so that you could do 2-4 such queries per minute is reasonable and probably effective at curtailing abuse.

RE: Max Distance - Bear in mind that I was following what I'll described as expected use. I don't think a user wants to take the time to snap the cover and then scroll through 30, 40 results hunting for a weak match. They'll give up if it's not in the first handful. That's why I went with an arbitrary array size of 8.

That being said, the min / max / mean / median for distance in my array-of-8 was 2 / 16 / 10.20 / 10. So in my testing, I never had a top-8 match that was more distant than 16. I agree 24 would likely be garbage. 20 is probably a good upper bound (and the data suggests that might be stretching).

[bpepple]

Thanks @erickolb! The filter is now merged in #683 and live on metron.cloud. A few things changed since my last comment.

Max distance: I went with your suggestion and capped cover_hash_max_distance at 20. Your top-8 results never went past 16, and at 24 a search matched around 11,000 covers. Values above 20 now return a 400.

Default distance: the default ended up at 10, not 16. I tested 1,271 tagged digital comic files against the full ~184k hashes. For those, 10 found the correct issue 98.6% of the time, and it was usually the only result, while 16 returned unrelated covers on every query. Camera scans are noisier, though, and in your data only 57% of correct covers were within 10 bits. So for a camera client I'd send cover_hash_max_distance=16 (or up to 20) and use the closest-first ordering, the way your top-8 approach did:

GET /api/issue/?cover_hash_near=<hash>&cover_hash_max_distance=16

If you know anything else about the comic, adding a filter like cover_year or series_id cuts the candidate list sharply.

Performance: I ended up adding a stored integer column for the hash, much like yours, with an index on it. A search at the default distance now takes about 20 ms on production data, down from the ~90 ms I mentioned, and about 36 ms at 20. That's also why a stricter rate limit seems less pressing now.

Variant covers still aren't included. That's the next piece I'd like to look at, and your Variant.cover_hash field and backfill command will be a good starting point.

[erickolb]

Great! I will implement a search client in Danger Room middle of next week, probably Thursday, and report back how it works!