Джентльмены, возник небольшой вопрос.
Имеется условно прямоугольная сетка кадров, снятых с перекрытием, далее они попарно совмещаются. Для совмещения кадры нужно загрузить. Кадров может быть до нескольких тысяч, в памяти их всех разместить невозможно, поэтому приходится делать вытесняющий кэш заданного объема. Необходимо составить алгоритм обхода пар так, чтобы минимизировать количество загрузок.
Наверняка есть похожие стандартные задачи, но я о них ничего не знаю.
Подскажите, куда копать.

miksoft,
Сейчас так и делается, но при большом числе кадров уже не получается.

Dima TИМХУ просто построчно обходить меняя направление обхода.
Т.е. в таком порядке
1 2 3 4
8 7 6 5
9 ...
Тут если кэша хватит на одну строку, то повторного считывания в кэш не потребуется. В худшем случае надо будет пересчитать крайние элементы последней законченной строки.

Сейчас делается именно так - обход построчно по меандру. На больших размерах предыдущую строчку приходится перегружать.
Число лишних загрузок получается порядка (Y-1)*P, где P - (0..X-1) в зависимости от размера кэша.
Я думал, возможно существуют алгоритмы с меньшей накладкой.

Dima TЕще вопрос по одработке: Сейчас пока 8-связный алгоритм (все соседи, в т.ч. диагональные).

miksoftСоколинский БорисЯ думал, возможно существуют алгоритмы с меньшей накладкой.Пару более выгодных вариантов я уже предложил. Я прочитал, спасибо. Идея с полосками, наверное, лучше всего.

softwarer,
miksoft, насколько я понял, именно такой вариант предложил.
С результатами - отдельная история, не для этой темы.

maytonЭтот вопрос не такой простой как кажется. Я вот из топика не понимаю каким образом Борис делает выравнивание границ и проверки на то что мозаика складывается верно. Если я это пойму - то посоветую order или файловый формат при котором взаимодействие с источниками будет минимально. В некотором вырожденном варианте можно вообще решать задачу "поточно" без привлечения кешей и буферов. Но я должен понять как Борис делает сшивание фоток. Мне казалось, это к теме не относится, но могу рассказать, большого секрета тут нет.
1. "Грубая" сетка кадров получается при создании карты просто по координатам "сканера" (запись кадров идет в "нахлест"). По этой сетке вычисляются перекрывающиеся пары и для каждой пары - предполагаемая область перекрытия.
2. Делается совмещение всех выбранных пар, процедура выдернута из OpenCV. Собственно здесь возникает задача оптимизации порядка совмещения.
3. В результате получается система линейных уравнений, большая, разреженная и переопределенная. Решается методом наименьших квадратов, есть достаточно эффективный и качественный алгоритм.

miksoftНет, не такой. Тут разница только в порядке обхода строк/столбцов - не по меандру, а от меньшего к большему. Принципиальной разницы не вижу.