Алгоритм поиска изображения в массиве с использованием ограничения минимального размера

Question

У меня есть массив, содержащий объекты изображения.Я ищу изображение, ближайшее к моему ограничению размера.Например, я хочу, чтобы изображение было равным 400x600 или ближайшему.

Под ближайшим я имею в виду ближайшее по размеру, немного больше или меньше.

Я не ищу реализацию только для алгоритма.

У вас есть идея, как этого добиться?

Спасибо

Тьерри

Answer 1

Вот мой алгоритм.

Для каждого изображения в массиве я вычисляю оценку для его соотношения и ширины.Победит счет с наименьшим значением.

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 2

Если вы рассматриваете размер изображения как вектор в двух измерениях, то вы можете использовать любой из нескольких показателей расстояния:

Например, вы можете использовать евклидово расстояние:

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

расстояние Минковского порядка 1 (расстояние Сити-Блок):

(itemWidth-targetWidth) + (itemHeight-targetHeight)

Чебышевское расстояние, также быстро рассчитать:

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

Или комбинация расстояний Минковского и Чебышева:

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

Вы также можете использовать разницу в областях изображения:

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

Или одно из более сложных решений, учитывающих соотношение сторон, как было предложено выше

Answer 3

Если ваш массив не огромен, пробовали ли вы выполнить простой линейный поиск в массиве, отслеживая при этом «лучшее совпадение на данный момент»?Наилучшее совпадение можно определить с помощью функции оценки / взвешивания / оценки, которую вы применяете к каждому элементу в массиве последовательно.Предмет с наибольшим количеством очков выигрывает.Инициализируйте две переменные с именами скажем bestMatchIndex и bestMatchScore.Используйте цикл for, чтобы пройти через массив.Для каждого элемента вызовите функцию оценки, чтобы получить его оценку.Сравните это с лучшим MatchScore.Если оценка текущего элемента выше, установите переменные bestMatch для текущего элемента.В конце цикла переменные bestMatch указывают на «лучшее совпадение».

Функция оценки может быть настолько простой или сложной, насколько вы хотите.

Вот пример оценкифункция (я знаю, вы сказали, что вы не ищете реализацию, но иногда некоторый код стоит тысячи слов).В этом примере я ищу элементы, которые меньше всего отличаются как по ширине, так и по высоте и соотношению.Ваши требования могут быть другими.

-(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);
}

(Реализация может быть более сложной, чем необходимо.)

Запустив это с некоторыми примерами измерений, мы получим:

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

Таким образом, в этом примере, предмет с наименьшим счетом должен «выиграть».«Победитель» зависит от функции подсчета очков.Выше, если бы был выбор между 500x700 и 600x400, 500x700 выиграл бы.