Преобразование изображения леса

В практике цифровой обработки изображений Александр X. Фалькао, Хорхе Столфи и Роберто де Аленкар Лотуфо создали и доказали, что преобразование лесного преобразования изображений (IFT) можно использовать для экономии времени при обработке 2-D, 3-D изображений. и движущиеся изображения. ^[1]

История

В 1959 году Дейкстра использовал структуру данных сбалансированной кучи. ^[1]^[2] улучшить алгоритм, представленный Муром в 1957 году. ^[1]^[3] и Беллман в 1958 году ^[1]^[4] который вычислил стоимость путей в общем графе. Техника сортировки Bucket — это то, как Dial усовершенствовал алгоритм десять лет спустя. ^[1]^[5] С тех пор алгоритм был усовершенствован и модифицирован во многих отношениях. Именно в этой версии улучшились Фалькао, Столфи и Лотуфо. ^[1]

Определение

Преобразование представляет собой усовершенствованную версию алгоритма поиска кратчайшего пути Дейкстры, оптимизированную для использования более одного входного сигнала и максимизации операторов цифровой обработки изображений. ^[1]^[2] Преобразование создает график пикселей изображения, а связи между этими точками представляют собой «стоимость» изображаемого пути. Стоимость рассчитывается путем проверки характеристик пути между пикселями, например шкалы серого, цвета, градиента и многих других. Деревья создаются путем соединения пикселей, которые имеют одинаковую или близкую стоимость применения выбранного оператора. Надежность преобразования требует затрат и требует много места для хранения кода и обрабатываемых данных. По завершении преобразования возвращаются предшественник, стоимость и метка. Большинство операторов, занимающихся цифровой обработкой изображений, могут использовать эти три части информации для оптимизации.

Оптимизация

В зависимости от того, какой оператор цифровой обработки изображений был выбран, алгоритм может быть дополнительно настроен для оптимизации в зависимости от того, что использует этот оператор. Алгоритм также можно оптимизировать, исключив пересчет путей. Это достигается за счет использования внешней справочной таблицы для отслеживания рассчитанных путей. «Обратные дуги» можно устранить, сравнив стоимость пути в обоих направлениях и исключив более дорогой путь. Также возможен случай, когда алгоритм возвращает бесконечность для некоторых путей. В этом случае пороговое число может быть установлено вместо бесконечности, либо путь будет исключен и не будет использоваться в дальнейших расчетах.

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Фалькао, А. С. Столфи, Ж. де Аленкар Лотуфо, Р.: « Преобразование леса изображений: теория, алгоритмы и приложения », В IEEE ТРАНЗАКЦИИ ПО АНАЛИЗУ ШАБЛОНОВ И МАШИННОМУ ИНТЕЛЛЕКТУ, VOL. 26, НЕТ. 1 ЯНВАРЯ 2004 ГОДА
^ Перейти обратно: ^а ^б Э. В. Дейкстра, « Заметки о двух проблемах, связанных с графами », Numerische Mathematik, vol. 1, стр. 269-271, 1959 г.
^ Э. Ф. Мур, «Кратчайший путь через лабиринт», Proc. Международный симп. Теория переключения, стр. 285–292, апрель 1959 г.
^ Р. Беллман, « О проблеме маршрутизации », Ежеквартальный журнал прикладной математики, том. 16, стр. 87-90, 1958 г.
^ RB Dial, « Лес кратчайшего пути с топологическим упорядочением », Comm. АКМ, том. 12, нет. 11, стр. 632–633, ноябрь 1969 г.

[Falcao-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Фалькао, А. С. Столфи, Ж. де Аленкар Лотуфо, Р.: « Преобразование леса изображений: теория, алгоритмы и приложения », В IEEE ТРАНЗАКЦИИ ПО АНАЛИЗУ ШАБЛОНОВ И МАШИННОМУ ИНТЕЛЛЕКТУ, VOL. 26, НЕТ. 1 ЯНВАРЯ 2004 ГОДА

[Dij-2] Перейти обратно: ^а ^б Э. В. Дейкстра, « Заметки о двух проблемах, связанных с графами », Numerische Mathematik, vol. 1, стр. 269-271, 1959 г.

[Moo-3] Э. Ф. Мур, «Кратчайший путь через лабиринт», Proc. Международный симп. Теория переключения, стр. 285–292, апрель 1959 г.

[Bell-4] Р. Беллман, « О проблеме маршрутизации », Ежеквартальный журнал прикладной математики, том. 16, стр. 87-90, 1958 г.

[Dial-5] RB Dial, « Лес кратчайшего пути с топологическим упорядочением », Comm. АКМ, том. 12, нет. 11, стр. 632–633, ноябрь 1969 г.

[1]

[2]

[3]

[4]

[5]