What you just mentioned is actually really easy (if it worked): factoring n where n is up to 10 megapixels.
Factoring up to a few megapixels (e.g. 3648 x 2736) isn't hard at all! At most there are 3159 guesses (square root of number of pixels) before you hit one of the factors - and that's starting at 1, rather than starting at sane minimum aspect ratio.
(It's only when you start trying to factor really large numbers that the problem becomes intractable. For example, the same trick just doesn't apply to a composite number that's 600 digits long. We're talking 6-9 digits, which a tight loop can crunch through faster than a disk read.)
The harder issue is after you do factor it into primes, you still have to combine those primes into a width and height.
For example, 640 x 480 is 307200. Factor that and you get
2^12 * 3 * 5^2.
There's obviously quite a few ways to combine those into two groups (two factors)...
so you're really not done. Probably the best heuristic is to simply count pixels and then compare with common formats.
I suppose you could do your factorization trick, and then try combining the factors in every possible way into two groups, and for any combinations that result in a "sane" aspect ratio, run some kind of vision algorithm to see if there are connected color blobs or something.
it does seem to me that for truly arbitrary pixel counts, the factors help but don't determine a unique choice.
What you just mentioned is actually really easy (if it worked): factoring n where n is up to 10 megapixels.
Factoring up to a few megapixels (e.g. 3648 x 2736) isn't hard at all! At most there are 3159 guesses (square root of number of pixels) before you hit one of the factors - and that's starting at 1, rather than starting at sane minimum aspect ratio.
(It's only when you start trying to factor really large numbers that the problem becomes intractable. For example, the same trick just doesn't apply to a composite number that's 600 digits long. We're talking 6-9 digits, which a tight loop can crunch through faster than a disk read.)
The harder issue is after you do factor it into primes, you still have to combine those primes into a width and height.
For example, 640 x 480 is 307200. Factor that and you get 2^12 * 3 * 5^2.
There's obviously quite a few ways to combine those into two groups (two factors)...
so you're really not done. Probably the best heuristic is to simply count pixels and then compare with common formats.
I suppose you could do your factorization trick, and then try combining the factors in every possible way into two groups, and for any combinations that result in a "sane" aspect ratio, run some kind of vision algorithm to see if there are connected color blobs or something.
it does seem to me that for truly arbitrary pixel counts, the factors help but don't determine a unique choice.