When decreasing minScale, generating crop size takes astronomically longer

[abagshaw]

I am generating a square crop (500x500) for a large image (about 3000x3000px). When minScale is at 1 this process is done in a second or two (max) on my machine - when decreasing minScale to 0.7 it takes a good few seconds longer and when decreasing minScale to 0.5 it takes almost a minute (similar results when running on Heroku)!

Is there something I am doing wrong or some way around this?

[abagshaw]

I've been doing a little more tinkering and it appears that the two main ways to speed things up are changing scoreDownSample to a larger value and step to a larger value. Just wondering, is there a reason why these values are not relative to the size of the image? Just an idea - but I think it would make much more sense to make them relative (or at least have an option to make them relative) to the size of the image so a small image will take around the same time to process as a massive image.

[jwagner]

Is there something I am doing wrong or some way around this?

No, this sounds roughly right. The reason for this is in short, that I haven't used smartcrop that way and therefore haven't optimized it for this. There are some fairly obvious examples to speed this up one is using a summed area table for calculating the the integrals & using stochastic gradient descent for finding the optimal crop. That should easily make your slow cases 100x faster.

Just an idea - but I think it would make much more sense to make them relative (or at least have an option to make them relative) to the size of the image so a small image will take around the same time to process as a massive image.

This is already the case. The image is prescaled depending on the size of the output crop. If I recall correctly the idea was that the size of the features to consider depend on the size of the thumbnail. But thinking about it again you are likely right and I should have just picked one 'right' size for the analysis.

I won't work on this right now, but I'll leave the issue open in case someone else wants to work on it.

[abagshaw]

Thanks for the quick response.

There are some fairly obvious examples to speed this up one is using a summed area table for calculating the the integrals & using stochastic gradient descent for finding the optimal crop. That should easily make your slow cases 100x faster.

Wouldn't it make much more sense to use the method you are describing here in all case scenarios rather than the somewhat brute-force method currently employed (even if we are talking about small square crops of small images)? Just wondering. I may have some time to tinker around with this to see if I can get that working.

Thanks!

[jwagner]

At very least the summed area tables, yes. I'm surprised I didn't use them to begin with. They are such a simple, elegant and obvious solution. And I even had them coded up when I played with face detection & multi scale approaches to this problem.

If you have some time to play I'd say give the summed area tables a shot. They should just transparently make everything much faster with marginal additional complexity. :)

[jwagner]

I now remember why I didn't use summed area tables for the integration step. It's because of the weighting function. So I guess this needs another trick to be made more fast. Damn. :(

[abagshaw]

Sorry for the slow response on this. I spent some time thinking about this problem and ways to improve the current algorithm. I decided to have a shot at implementing a new approach from the ground up.

I built a "smart-cropping" tool around the fast feature detector from tracking.js. Add on some outlier removal, dbscan clustering and a method for scoring/prioritizing certain clusters and I'm getting some pretty cool results. When running in node its achieving about anywhere from 2-6x+ faster processing time than smartcrop on all image sizes - haven't really done any benchmarking in the browser so I don't know if the performance improvement would persist there. Going for a clustered feature detection based system opens up some neat possibilities too (like intelligently switching between objects when a crop isn't big enough to comfortably fit both).

Probably will open source this some time in the future when I get the code cleaned up. It's not exactly the smallest library when everything is compiled down so for client side, small image cropping I have a feeling smartcrop would still have the edge (assuming minScale is at 1).

[jwagner]

I investigated this a bit more and tried out both prescaling to a fixed size and the summed area tables approach in this branch. The prescaling seems to work nicely, it might even give more consistent results. The unoptimized summed area table/integral image approach I used made things slower in addition to being less flexible. I'm sure it could be tweaked but I'm no longer convinced it would be worth it.

Cheers,
Jonas

[greghuc]

Hi @abagshaw. Did you ever open-source the "smart-cropping" tool built around the fast feature detector from tracking.js? (you mentioned it here). I'm looking for a fast browser-side smart-cropping solution, so wondered if you'd made progress. Thanks :-)

[abagshaw]

@greghuc No, I didn't end up open-sourcing that. I worked on that for a bit and while it did show some promising signs (quite a bit faster than smartcrop.js - it didn't employ a sliding box brute-force approach to finding smaller crops so it didn't take any longer to generate a zoomed crop than a larger crop) it's level of accuracy was not much better than smartcrop.js (and in some cases worse) and that wasn't good enough for me. Now it's just a jumbled mess of code lying around my computer.

Both that new algorithm and smartcrop.js are "dumb" per se - i.e. they don't recognize objects for what they are (they can't recognize relationships between objects - what can be cut off and what can't) and accuracy when generating crops that aren't full height or full width is pretty hit and miss. I've actually been working on an entirely new solution (an API) that's based on AI object detection https://www.salieo.com/ which is pretty cool and is a heck of a lot more accurate than the "dumb" solutions. Hoping to bring that to market soon.

[greghuc]

@abagshaw thanks for the reply. Good luck with the venture!