Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 47
А если масштаб не совпадает, то не будет ведь работать?
А если масштаб не совпадает, то не будет ведь работать?
Отмаштабируйте. Прочитайте другую мою статью habrahabr.ru/post/265781 раздел Алгоритм масштабирования изображения
при этом если написать код для прогнать поиск в разных размерах образца
многократно гонять фурье преобразования для образца нет никакой необходимости
поскольку масштабирование получается в результате добавления нулевых или удаления строк и столбцов соответствующих высоким частотам в матрице фурье-образа
а лишнее нормирование делать нет необходимости
получаем что первый квадрант матрицы фурье-образа образца зафиксирована на одном месте в начале координат
а остальные квадранты матрицы перемещаются по строкам и столбцам для перемножения с фурье-образом полного изображения с последующим вычислением обратного преобразования
то же самое для фурье-образа единичной матрицы кадра
многократно гонять фурье преобразования для образца нет никакой необходимости
поскольку масштабирование получается в результате добавления нулевых или удаления строк и столбцов соответствующих высоким частотам в матрице фурье-образа
а лишнее нормирование делать нет необходимости
получаем что первый квадрант матрицы фурье-образа образца зафиксирована на одном месте в начале координат
а остальные квадранты матрицы перемещаются по строкам и столбцам для перемножения с фурье-образом полного изображения с последующим вычислением обратного преобразования
то же самое для фурье-образа единичной матрицы кадра
Алгоритм масштабирования изображения
В оптических системах световой поток в фокальной плоскости системы представляет собой Фурье-преобразование исходного изображения. Размер получаемого на выходе оптической системы изображения определяется соотношением фокальных расстояний объектива и окуляра.
Алгоритм:
Пусть X(N1,N2) – массив яркостей пикселей изображения.
В оптических системах световой поток в фокальной плоскости системы представляет собой Фурье-преобразование исходного изображения. Размер получаемого на выходе оптической системы изображения определяется соотношением фокальных расстояний объектива и окуляра.
Алгоритм:
Пусть X(N1,N2) – массив яркостей пикселей изображения.
- Вычислить Px = средняя (среднеквадратичная) яркость пикселей в массиве X
- Вычислить массив Z=FT(X) – прямое двухмерное дискретное преобразование Фурье
- Вычислить массив Z′=T(Z), где T – либо добавление нулевых строк и столбцов матрицы соответствующих высоким частотам, либо удаление строк и столбцов матрицы соответствующих высоким частотам для получения требуемого размера итогового изображения
- Вычислить массив Y=RFT(Z′) – обратное двухмерное дискретное преобразование Фурье
- Вычислить Py = средняя (среднеквадратичная) яркость пикселей в массиве Y
- Нормировать массив Y(M1,M2) по среднему уровню яркости Px/Py
В оптических системах световой поток в фокальной плоскости системы представляет собой Фурье-преобразование исходного изображения.— вообще-то не исходного изображения, а входящего в апертуру светового поля
Спасибо, поправлю в тексте.
Хотя в том тексте я нарисовал телескопическую систему из двух линз на самом деле линзы вообще не нужны. оптическую систему предоставляет нам само пространство в котором присутствует свет.
Хотя в том тексте я нарисовал телескопическую систему из двух линз на самом деле линзы вообще не нужны. оптическую систему предоставляет нам само пространство в котором присутствует свет.
В каком тексте? Что-то я нигде не нашел этой картинки
Я бы еще придрался к фразе:
Преобразование Фурье (ℱ) — операция, сопоставляющая одной функции вещественной переменной другую функцию, также вещественной переменной.Особенно в оптике. Световое поле в типичных оптических задачах, как правило, описывается скалярным приближением уравнений Максвелла, а именно — комплексной скалярной функцией координат и времени. Соответственно и фурье должно быть комплексным.
нет — согласно общепринятому определению Преобразование Фурье — это функции вещественной переменной. либо времени, либо частоты.
Вы просто перепутали с возможным комплексным значением этой функции.
описывается скалярным приближением уравнений Максвелла, а именно — комплексной скалярной функцией координат и времени — да, я понимаю — Вы говорите о тензорах и сверкомплексных
Вы просто перепутали с возможным комплексным значением этой функции.
описывается скалярным приближением уравнений Максвелла, а именно — комплексной скалярной функцией координат и времени — да, я понимаю — Вы говорите о тензорах и сверкомплексных
Скорее уж вы перепутали, если пишете под интегралом экспоненту с мнимой единицей в показателе. Собственно, этот интеграл и есть общепринятое определение, и даже если исходная функция вещественна, то ее фурье-образ — комплексный
Нет, не о тензорах. Эта скалярная функция координат и времени описывает, как ведет себя любая из шести компонент векторов электрического или магнитного поля световой волны.
Два алгоритма состыковать в один, для отсутствия лишних действий, ведь несложная задача?
Зачем городить такую колбасину? В чём преимущество перед двумя десятками существующих методов, использующихся для этой же задачки? Многие из таких методов, кстати, значительно стабильнее к искажениям, в том числе к аффинным преобразованиям.
Зачем городить такую колбасину?
Ответ — Количество требуемых вычислительных операций
Подсчитате оценку сложности — будете ли Вы удовлетворены быстродействием имеющейся у Вас техники?
Если надо один раз и на суперсовременном компе — то это статья не для вас.
Я пишу алгоритмы в том числе для DSP-процессоров и для embeded процессоров, где производительность это ограниченный ресурс. Я не понимаю как ваш алгоритм хоть как-то превосходит классические алгоритмы поиска. Вы правда считаете, что кто-то сравнивает так: «классический метод “начального уровня”, заключающийся в переборе всех координат».
Подсчитате оценку сложности Вашей задачи.
Если обрабатываете очень маленькие картинки — то эта вся методика вам вообще не нужна
Для справки — трудоёмкость дискретного преобразования Фурье быстрыми алгоритмами O(N*logN)
Если обрабатываете очень маленькие картинки — то эта вся методика вам вообще не нужна
Для справки — трудоёмкость дискретного преобразования Фурье быстрыми алгоритмами O(N*logN)
В приведённом алгоритме суммарная трудоёмкость будет иметь оценку равную оценке трудоёмкости одного фурье-преобразования, то есть O(N*logN)
Оценим классическую схему с попарным сравнением — это O(N*M^2)
То есть если у Вас образец всегда маленькая картинка — то даже от увеличения общего размера Вы будете наблюдать просто линейный рост трудоёмкости пропорциональный количеству пикселей.
Однако если размер образца тоже возрастает и скорость увеличения больше чем SQRT( LOG ( N ) ) то начиная с некоторого размера изображения этот алгоритм будет работать быстрее, как бы Вы не оптимизировали свой программный код в погоне за белым кроликом.
Оценим классическую схему с попарным сравнением — это O(N*M^2)
То есть если у Вас образец всегда маленькая картинка — то даже от увеличения общего размера Вы будете наблюдать просто линейный рост трудоёмкости пропорциональный количеству пикселей.
Однако если размер образца тоже возрастает и скорость увеличения больше чем SQRT( LOG ( N ) ) то начиная с некоторого размера изображения этот алгоритм будет работать быстрее, как бы Вы не оптимизировали свой программный код в погоне за белым кроликом.
И смею Вас заверить, что на практике это N наступает довольно быстро — если библиотека быстрых преобразований написана грамотно — то уже на картинках в 100-200 пикселей. Если библиотека быстрых преобразований написана тяп-ляп на скриптовом языке — то на 1000-2000 пикселей
Почему вы так упёрлись в попарное сравнение? Неужели не знаете других алгоритмов? Да ладно, даже оно. Пирамидальный поиск? Разреженный поиск? Сегментация предварительной области для поиска через цветность/яркость? Это ускоряет его в сотни и тысячи раз. А если затачивать под конкретные задачи, то ещё больше.
Более того, почему вы упёрлись в размер картинки? Я на raspberry Pi обрабатывал мегапиксельные кадры для поиска интересных объектов. При этом объектов не имеющих стабильную форму.
Для справки, поиск примитива на интегральном изображении O(N). Не зря Хаар на нём сделан. И большая часть алгоритмов хэширования изображений. Поиск через FFT и любой локальный классификартор значительно стабильнее и тоже ~N (хотя там достаточно большой коэффициент пропорциональности).
Более того, почему вы упёрлись в размер картинки? Я на raspberry Pi обрабатывал мегапиксельные кадры для поиска интересных объектов. При этом объектов не имеющих стабильную форму.
Для справки, поиск примитива на интегральном изображении O(N). Не зря Хаар на нём сделан. И большая часть алгоритмов хэширования изображений. Поиск через FFT и любой локальный классификартор значительно стабильнее и тоже ~N (хотя там достаточно большой коэффициент пропорциональности).
Почему вы так упёрлись в попарное сравнение? Неужели не знаете других алгоритмов? Да ладно, даже оно. Пирамидальный поиск? Разреженный поиск? Сегментация предварительной области для поиска через цветность/яркость? Это ускоряет его в сотни и тысячи раз. А если затачивать под конкретные задачи, то ещё больше.
Ответ — в основе всего что Вы перечислили всё равно будет лежать некий базовый алгоритм и чаше всего в разных пакетах это попарное сравнение.
Вам никто не мешает и этот алгоритм модифицировать
Например, методом ветвей и границ или каким умеет способом:
сперва сжать изображение и ограничить зону поиска выбором из полученной матрицы оценок несколько наибольших значений.
затем повторить алгоритм но уже только в более достоверных регионах
и как Вы правильно выразились — это ускоряет его в сотни и тысячи раз. (но не миллионы)
повторю ещё раз — на практике эффективность метода можно наблюдать уже на довольно небольших размерах изображений.
Кстати для предварительной оценки не только формулы из статьи можно использовать — кроме фурье преобразований существует и масса других не менее интересных преобразований — но видимо, сейчас это не входит в программу обучения.
Разрешите и Вам задать вопрос по программам и алгоритмам.
Какая из сортировок выполняется на компьютере быстрее?
Варианты:
А. Пузырьковая сортировка
Б. Быстрая сортировка
Совет.
Прежде чем ответить однозначно, подумайте ещё раз.
Какая из сортировок выполняется на компьютере быстрее?
Варианты:
А. Пузырьковая сортировка
Б. Быстрая сортировка
Совет.
Прежде чем ответить однозначно, подумайте ещё раз.
Угу. И строить фурье-преобразование с маской на изображении, по разреженной выборке и пиромидальное так же просто и быстро, как определённого размера блока. Ну-ну. У вас там доступ в память занимает больше времени чем само сравнение.
К тому же вы так же продолжаете игнорировать методы, пропорциональные N, которые решают задачи поиска даже для огромных изображений при большом количестве шумов и искажений.
Впрочем, видя, как вы нервничаете от моих комментариев, отвечая тремя-пятью на каждый, я предпочту откланяться. Конструктивной беседы нет, ни с одним адекватным методом поиска сравнения не приведено.
К тому же вы так же продолжаете игнорировать методы, пропорциональные N, которые решают задачи поиска даже для огромных изображений при большом количестве шумов и искажений.
Впрочем, видя, как вы нервничаете от моих комментариев, отвечая тремя-пятью на каждый, я предпочту откланяться. Конструктивной беседы нет, ни с одним адекватным методом поиска сравнения не приведено.
Жаль.
Хоть Вы и не смогла дать ответ на вопрос какая из сортировок работает на компьютере быстрее, поскольку не понимаете разницы между терминами алгоритм и программа.
Я хочу посоветовать изучить эту тему на примере другого проекта, посвящённого сравнению времени вычислений на CUDA и MPI некоторых алгоритмов сортировок
github.com/dprotopopov/ParallelSorting
А вы опишите их по шагам для той же самой задачи.
Вместе рассчитаем количество элементарных операций.
Я добавлю те же ускорители которые у Вас будут в описании, а может и не буду добавлять.
И мы посчитаем количество элементарных операций.
сравним два этих значения и Вы сами решите — надо ли Вам пользоваться этим алгоритмом или нет.
колхоз — дело добровольное
Хоть Вы и не смогла дать ответ на вопрос какая из сортировок работает на компьютере быстрее, поскольку не понимаете разницы между терминами алгоритм и программа.
Я хочу посоветовать изучить эту тему на примере другого проекта, посвящённого сравнению времени вычислений на CUDA и MPI некоторых алгоритмов сортировок
github.com/dprotopopov/ParallelSorting
К тому же вы так же продолжаете игнорировать методы, пропорциональные N
А вы опишите их по шагам для той же самой задачи.
Вместе рассчитаем количество элементарных операций.
Я добавлю те же ускорители которые у Вас будут в описании, а может и не буду добавлять.
И мы посчитаем количество элементарных операций.
сравним два этих значения и Вы сами решите — надо ли Вам пользоваться этим алгоритмом или нет.
колхоз — дело добровольное
Есть и метод с оценкой O(1) — называется «пальцем в небо»
Алгоритм:
Пусть даны два изображения X и Y – изображение и образец, размеров (N1,N2) и (M1,M2) соответственно и Ni > Mi
Требуется найти координаты образца Y в полном изображении X и вычислить оценочную величину — меру близости.
1. Тыкаем в случайную точку на изображеении Y и берём первое число пришедшее в голову
Полученный результат будем рассматривать как решение задачи
Алгоритм:
Пусть даны два изображения X и Y – изображение и образец, размеров (N1,N2) и (M1,M2) соответственно и Ni > Mi
Требуется найти координаты образца Y в полном изображении X и вычислить оценочную величину — меру близости.
1. Тыкаем в случайную точку на изображеении Y и берём первое число пришедшее в голову
Полученный результат будем рассматривать как решение задачи
И ещё замечание по поводу DSP-процессоров и для embeded процессоров
Видимо Вы занимаетесь написанием софта для телескопов.
Всякое уменьшение количества операций при анализе изображений без увеличения суммарной ошибки первой и второго рода невозможно если на анализируемое изображение не наложены предоговоренные ограничения.
Если Вы пишете софт для анализа картинок звёздного неба, и при этом пользуетесь софтом который проводит операции сравнения за число шагов равное размеру картинки, то это однозначно указывает, что у Вас уже существует набор предопределённых условий и Ваш софт просто будет отбрасывать всё что не входит в Ваше представление о вселенной.
Вывод.
На Ваших телескопах никогда не будет совершено ни одного открытия — поскольку они будут показывать только то что и та всем известно.
Видимо Вы занимаетесь написанием софта для телескопов.
Всякое уменьшение количества операций при анализе изображений без увеличения суммарной ошибки первой и второго рода невозможно если на анализируемое изображение не наложены предоговоренные ограничения.
Если Вы пишете софт для анализа картинок звёздного неба, и при этом пользуетесь софтом который проводит операции сравнения за число шагов равное размеру картинки, то это однозначно указывает, что у Вас уже существует набор предопределённых условий и Ваш софт просто будет отбрасывать всё что не входит в Ваше представление о вселенной.
Вывод.
На Ваших телескопах никогда не будет совершено ни одного открытия — поскольку они будут показывать только то что и та всем известно.
Видимо Вы занимаетесь написанием софта для телескопов
если Ваш софт отвечает только за ориентацию телескопа — то можно обсуждать.
если Вас софт предназначен для исследования вселенной — я бы Вам рекомендовал вообще забыть что существуют какие-либо программные пакеты компьютерного зрения, а так же описанная мною методика.
по разреженной выборке
Если же вы производите анализ звёздного неба, то мне вообще непонятно зачем Вам растровые изображения.
Запишите координаты светлых пикселей в таблицу, а дальше просто крутите данными.
Надеюсь, тему расчёт параметров распределений по наблюдаемым данным Вы всё же проходили, теорию вероятностей, статистические критерии и тд?
По любому — если графическое изображение являет собой практически полное чёрное поле, не фиксируемое сенсорами телескопа, то как ни крути — явные вычисления формул по таблицам будет быстрее и надёжнее чем расчёты на каких-то сетках с ячейками поддерживающими точность в пару бит.
Конечно придётся посидеть с карандашом и бумагой, чтобы выписать формулы.
по разреженной выборке
а у Вас по математике вопроса не возникло — не будет в приведённом алгоритме одни деления на ноль на Ваших данных?
ответ — да, на Ваших данных, практически везде будет деление на ноль.
А почему?
Ответ — а потому, что в данном алгоритме в качестве меры близости выбрана формула соответствующая типовой модели фотографии — где снимки квадратов малевича не делают. То есть отброшены маловероятные варианты из рассмотрения.
А можно по-другому?
Да — можно. Надо изменить предполагаемую модель исходных изображений.
Я расстроен уровнем научных степеней.
Я расстроен уровнем научных степеней.
Я делал лабы за студентов МФТИ по расчёту задач с краевыми условиями на решетках.
Преподаватель дал такие краевые условия, что получалось что аналитические функции действительного переменного имеют вычет, что может быть только начиная с функций комплексного переменного. Естественно мой результат не совпал с записанным в ответах поскольку расчёты из-за этого противоречия уходили неизвестно куда. Исправилось только после того как я выкинул часть условий из первоначально заданных краевых ограничений.
А ведь другие студенты сдавали так сказать верные решения со всеми этими несоответствиями и получали отличные оценки.
как это возможно — да очень просто — не важно что как считает, главное как отчитаться.
Посмотрел Ваши публикации — понял Вам практически ничего не рассказывали о теории вероятности — поэтому понятия ошибок первого и второго рода Вы не упоминаете в своих публикациях.
Отсюда у Вас и впечатление. что нет конструктивной беседы, и что метод с оценкой ~N всегда лучше метода с оценкой O(NlogN)
Отсюда у Вас и впечатление. что нет конструктивной беседы, и что метод с оценкой ~N всегда лучше метода с оценкой O(NlogN)
примитива на интегральном изображении O(N)
так и здесь перемножение элементов двух матриц O(N)
но как говорил кот Матроскин псу Шарику — ты ещё полдня за ним будешь гонятся чтобы фотографию отдать
типовыми являются случаи
- M = SQRT ( N )
- M = N/2^(2*k)
в том числе к аффинным преобразованиям
Так здесь этот вопрос не рассматривается.
Никто не спрашивает — никто и не отвечает
а правильно заданный вопрос — это половина ответа
Требуется найти координаты образца Y в полном изображении X и вычислить оценочную величину — меру близости.
То есть в прицнипе кусочек изображения может быть слегка изменен (шум например), и не обязан полностью соотвествовать оригиналу (за исключением масштаба). Я правильно понимаю?
быть слегка изменен (шум например)
и не только слегка
Вспомните курс математической статистики и теории вероятности
Зная параметры зашумления Вы можете легко рассчитать вероятности ошибок первого и второго рода.
Используется статистический критерий X^2(M) где М-длина образца.
Даже если вы будете точно знать распределение шумов — то всё равно критерий для оценки значительно лучше чем X^2(M) не станет — причина в том что M как правило > 100, а при таком большом числе слагаемых там все с практической точки равносильно сумме нормальных распределений.
Естественно в этой формуле каждое отдельное распределение шума в пикселях образца надо отнормировать на дисперсию.
А можете и не нормировать — тогда просто получите оценку ошибок
я даже более хочу вам заметить — не существует вещей и явлений известных человеку с характеристикой 100% вероятности.
Кроме Бога
Кроме Бога
А X^2(M) при больших M практически совпадает с нормальным распределением.
Естественно надо решить вопросы нормирования.
То есть надо иметь только справочник нормального распределения, чтобы ответить на все вопросы.
Естественно надо решить вопросы нормирования.
То есть надо иметь только справочник нормального распределения, чтобы ответить на все вопросы.
Я правильно понимаю?
Абсолютно верно.
Вспомните операции сравнения векторов в линейном пространстве из школьного курса — там вводится мера на пространстве равная скалярному произведению.
Благодаря нормированию мы тем самым фактически будем искать к заданному вектору-образцу ближайший нормированный вектор из всех возможных таких векторов сформированных из картинки.
Естественно при совпадении направлений двух векторов скалярное произведение будет максимальным.
Почему нормировать лучше на квадрат и не на сумму — просто это из-за цветовосприятия человеческого глаза, под который затачивается и фототехника. Это конечно не закон — это просто обычная практика. Просто Вы должны знать характеристики данных которые намерены обрабатывать для более эффективной их обработки.
То есть — можете делить на корень, а можете вообще не делить, если уверены что в среднем все участки имеют одинаковую интенсивность, например если это не фото, а просто случайные равновероятны данные.
Приведённые программные коды производят поиск без учёта цветности, то есть в монохромном режиме
Чтобы при поиске учитывать и цвет надо использовать трёхмерный массив для образцов и изображения и делать трёхмерные преобразования Фурье
трёхмерные преобразования тоже содержатся практически во всех библиотеках
Считывать значение меры естественно только из нулевой цветовой плоскости полученной матрицы M
Чтобы при поиске учитывать и цвет надо использовать трёхмерный массив для образцов и изображения и делать трёхмерные преобразования Фурье
трёхмерные преобразования тоже содержатся практически во всех библиотеках
Считывать значение меры естественно только из нулевой цветовой плоскости полученной матрицы M
при этом если написать код для прогона поиска в разных размерах образца
многократно гонять фурье преобразования для образца нет никакой необходимости
поскольку масштабирование получается в результате добавления нулевых или удаления строк и столбцов соответствующих высоким частотам в матрице фурье-образа
а лишнее нормирование делать нет необходимости
получаем что первый квадрант матрицы фурье-образа образца зафиксирован на одном месте в начале координат
а остальные квадранты матрицы перемещаются по строкам и столбцам для перемножения с фурье-образом полного изображения с последующим вычислением обратного преобразования
то же самое для фурье-образа единичной матрицы кадра
многократно гонять фурье преобразования для образца нет никакой необходимости
поскольку масштабирование получается в результате добавления нулевых или удаления строк и столбцов соответствующих высоким частотам в матрице фурье-образа
а лишнее нормирование делать нет необходимости
получаем что первый квадрант матрицы фурье-образа образца зафиксирован на одном месте в начале координат
а остальные квадранты матрицы перемещаются по строкам и столбцам для перемножения с фурье-образом полного изображения с последующим вычислением обратного преобразования
то же самое для фурье-образа единичной матрицы кадра
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Фурье-вычисления для сравнения изображений