Меня попросили — я сделал. Может быть где-то и есть готовое решение именно для метода суперсемплинга, но ни я, ни мои коллеги его не нашли. Готовые методы, которые можно сравнительно легко найти с открытым кодом, ориентированы на человеческое зрение и вносят в изображение специфические искажения, которых заказчик хотел избежать. Здесь же постобработка (векторизация) проводилась машиной, поэтому некоторая размытость изображения после трансформации (а это, в сущности, единственное искажение, вносимое алгоритмом) не критична.
Аэрофотосъёмку я показать не могу, у меня к ней нет даже доступа, моя задача была только в написании функций. Здесь представлены просто картинки из интернета, в качестве примера.
На досуге переработал и упростил структуру программы. Время расчётов при этом увеличилось примерно в 1,7 раз но память теперь расходуется только на хранение битмапов, что позволяет работать с изображениями любых размеров.
Скачать программу и исходники можно здесь: prosolver.kiev.ua/PreciseRotation2.zip
За 9 часов с перерывами решил задачу в общем виде. Программу и исходники для Delphi Object Pascal можно скачать здесь: prosolver.kiev.ua/SamsungTaskSolver.zip
Благодарю всех за отзывы! Они были действительно ценными и нтересными.
С вашего позволения, отвечу в одном сообщении на ключевое. Материал статьи я готовил месяц, потому и с комментарием задержался.
1. На практике редко возникает потребность в том, чтобы вращать одно и то же изображение много раз. В таких условиях применение любого алгоритма приведёт к накоплению ошибок и усилению искажений. На практике возникает задача повернуть одно изображение один раз. И здесь вполне уместно поставить вопрос, что ценнее: контрастные детали или информация о цвете? Фотошоп даёт ответ — контрастные детали важнее, цветом можно пожертвовать. Предложенный мной алгоритм отвечает на вопрос иначе — цвет важнее, контрастом можно пожертвовать. Я отнюдь не настаиваю на том, что мой алгоритм лучше всех алгоритмов. Он просто предоставляет выбор метода под конкретную задачу.
Вместе с тем, я всё же провёл эксперимент, подобный тому, который предложили Krovosos и archim. В итоге изображение, повёрнутое прецизионным алгоритмом, действительно, получилось более размытым, чем у фотошопа, но и ошибка в цвете у фотошопа получилась большей. Например, по каналу G для изображения тюльпана из теста №2 ошибка после 32 последовательных поворотов на 5° у Фотошопа достигла 0,4%, а у моего алгоритма оказалась на уровне 0,005% т.е. на 2 порядка лучше.
Тут же следует заметить, что размытость изображения — это не приговор. Можно подумать над эффективным алгоритмом шарпизации, специфичными для данного алгоритма поворота. Вопрос не так прост и очевиден, тут действительно есть над чем подумать.
2. Касательно гамма-коррекции я предлагаю провести такой мысленный эксперимент. Представим, что тестовое изображение получено непосредственно с идеальной фотоматрицы. Теперь представим, что мы повернули фотоматрицу на небольшой угол и снова сделали снимок таким образом, чтобы элемент изображения, который снимался одним фотоэлементом фотоматрицы оказался разделённым между двумя фотоэлементами. Совершенно понятно, что в таком случае каждый фотоэлемент получит в 2 раза меньше света, поэтому и в прецизионном алгоритме яркость этого пикселя должна разделиться. С другой стороны, если RGB шкала действительно нелинейная (что для меня новость), коррекцию итогового цвета произвести надо обязательно. Над этим нюансом я тоже обещаю подумать.
Благодарю за ссылку. Сходство между алгоритмами, судя по статье, только в том, что используется рекурсия. В остальном отличия:
— в статье задача коммивояжёра на нижнем рекурсивном уровне решается подоптимальными методы / у меня полным перебором;
— в статье использован другой (нерекурсивный) алгоритм для разбиения на группы. А способ разбиения на группы — это самый принципиальный момент в рекурсивном подходе к решению задачи;
— у меня группы соединяются через один узел просто по ближайшему расстоянию между группами. У Сигала применена специальная процедура.
В качестве меры близости используется евклидово расстояние, поэтому в принципе ничто не мешает его перевести в N-мерное пространство с метрикой евклида. В программе приведён вариант для 2-х измерений.
Да, конечно ) Но эвристики тут минимум. Если Вы видите способ, как полностью уйти от эвристики и основываться исключительно на каких-то соображениях, имманентно присущих данной задаче — было бы интересно узнать.
Связи между узлами устанавливаются только полным перебором на данном уровне рекурсии. Конечно, перебор получается не полностью полный. Просто другого метода для соединения узлов здесь не используется.
Я исследовал применимость тривиального полного перебора как основного метода решения, в симбиозе с рекурсией. Любые другие методы, конечно, имеют право на существование.
Скачать программу и исходники можно здесь: prosolver.kiev.ua/PreciseRotation2.zip
С вашего позволения, отвечу в одном сообщении на ключевое. Материал статьи я готовил месяц, потому и с комментарием задержался.
1. На практике редко возникает потребность в том, чтобы вращать одно и то же изображение много раз. В таких условиях применение любого алгоритма приведёт к накоплению ошибок и усилению искажений. На практике возникает задача повернуть одно изображение один раз. И здесь вполне уместно поставить вопрос, что ценнее: контрастные детали или информация о цвете? Фотошоп даёт ответ — контрастные детали важнее, цветом можно пожертвовать. Предложенный мной алгоритм отвечает на вопрос иначе — цвет важнее, контрастом можно пожертвовать. Я отнюдь не настаиваю на том, что мой алгоритм лучше всех алгоритмов. Он просто предоставляет выбор метода под конкретную задачу.
Вместе с тем, я всё же провёл эксперимент, подобный тому, который предложили Krovosos и archim. В итоге изображение, повёрнутое прецизионным алгоритмом, действительно, получилось более размытым, чем у фотошопа, но и ошибка в цвете у фотошопа получилась большей. Например, по каналу G для изображения тюльпана из теста №2 ошибка после 32 последовательных поворотов на 5° у Фотошопа достигла 0,4%, а у моего алгоритма оказалась на уровне 0,005% т.е. на 2 порядка лучше.
Тут же следует заметить, что размытость изображения — это не приговор. Можно подумать над эффективным алгоритмом шарпизации, специфичными для данного алгоритма поворота. Вопрос не так прост и очевиден, тут действительно есть над чем подумать.
2. Касательно гамма-коррекции я предлагаю провести такой мысленный эксперимент. Представим, что тестовое изображение получено непосредственно с идеальной фотоматрицы. Теперь представим, что мы повернули фотоматрицу на небольшой угол и снова сделали снимок таким образом, чтобы элемент изображения, который снимался одним фотоэлементом фотоматрицы оказался разделённым между двумя фотоэлементами. Совершенно понятно, что в таком случае каждый фотоэлемент получит в 2 раза меньше света, поэтому и в прецизионном алгоритме яркость этого пикселя должна разделиться. С другой стороны, если RGB шкала действительно нелинейная (что для меня новость), коррекцию итогового цвета произвести надо обязательно. Над этим нюансом я тоже обещаю подумать.
Ещё раз всем спасибо за комментарии.
— в статье задача коммивояжёра на нижнем рекурсивном уровне решается подоптимальными методы / у меня полным перебором;
— в статье использован другой (нерекурсивный) алгоритм для разбиения на группы. А способ разбиения на группы — это самый принципиальный момент в рекурсивном подходе к решению задачи;
— у меня группы соединяются через один узел просто по ближайшему расстоянию между группами. У Сигала применена специальная процедура.