Algorithm to find an image in an array using minimum size constraint

Question

Hello,

I have an array containing image objects. I am looking for an image nearest my size constraint. For exemple I want an image equal to 400x600 or nearest.

By nearest I mean nearest by size, a little bit bigger or smaller.

I am not looking for an implementation just for an algorithm.

Do you have an idea how to achieve this ?

Thanks

Thierry

Answer 1

Unless your array is huge, have you tried a simple linear search of the array while keeping track of the "best-match-so-far"? The best-match can be determined using a scoring/weighing/rating function that you apply to each item in the array in sequence. The item with the highest "score" wins. Initialize two variables called say bestMatchIndex and bestMatchScore. Use a for-loop to go through the array. For each item, call the scoring function to get its score. Compare that to the bestMatchScore so far. If the current item's score is higher, set the bestMatch variables to the current item. At the end of the loop, the bestMatch variables point you to the "best match".

The scoring function can be as simple or complicated as you want.

Here's an example of a scoring function (I know you said you're not looking for an implementation but sometimes some code is worth a thousand words). In the example, I am looking for items that deviate the least from both the width and height and ratio. Your requirements might be different.

-(double)itemScoreForWidth:(double)itemWidth height:(double)itemHeight
{
    const double targetWidth = 400.0;
    const double targetHeight = 600.0;
    const double targetScore = 7.0;

    double widthDiff = (itemWidth / targetWidth);
    double heightDiff = (itemHeight / targetHeight);
    double ratioDiff = ((itemWidth/itemHeight) / (targetWidth/targetHeight));

    double product = (4 * ratioDiff) +  (2 * widthDiff) + heightDiff;

    return fabs(targetScore - product);
}

(The implementation might be more complicated than necessary.)

Running this with some sample dimensions, we get:

score for 400x600 : 0.000000
score for 401x600 : 0.015000
score for 401x601 : 0.009994
score for 401x598 : 0.025078
score for 500x700 : 0.952381
score for 602x400 : 5.706667
score for 200x300 : 1.500000
score for 800x1200: 3.000000
score for 410x610 : 0.099454
score for 600x400 : 5.666667

So in this example, the item with the lowest score should "win". The "winner" depends on the scoring function. Above, if it was a choice between only the 500x700 and the 600x400, the 500x700 would win.

Answer 2

Here my algorithm.

For each image in the array I calculate a score for its ratio and its width. The score with the smallest value wins.

function getBestMatchingImage(array,width,height)

BEGIN

float bestScoreFound = 100 // arbitrary big value
Image bestImageFound
float currentImgScore = 0
float rationToMatch = width / height

for each image in array

    currentImgScore = scoreIt(image, rationToMatch, width)

    if (currentImgScore < bestScoreFound) then
        bestScoreFound = currentImgScore
        bestImageFound = image
    end if

end for

return bestImageFound

END


float function scoreIt(image, ratioToMatch, widthToMatch)

BEGIN

float imageRation = image.width / image.height
    float ratioScore = fabs((imageRation/ratioToMatch)-1)
    float widthScore = fabs((image.width/widthToMatch)-1)

    return ratioScore + widthScore

END

Answer 3

If you treat image size as vector in two dimensions, then you can use any one of a number of distance metrics:

For example, you could use Euclidean distance:

sqrt((itemWidth-targetWidth)^2 + (itemHeight-targetHeight)^2)

Minkowski distance of order 1 (City-Block distance):

(itemWidth-targetWidth) + (itemHeight-targetHeight)

Chebyshev distance, also quick to calculate:

max( (itemWidth-targetWidth), (itemHeight-targetHeight) )

Or a combination of Minkowski and Chebyshev distances:

max( (2/3 * minkowski), chebyshev )

You could also use difference in image areas:

abs( (itemWidth*itemHeight) - (targetWidth*targetHeight) ) 

Or one of the more sophisticated solutions that take aspect ratio into account, as proposed above