Pull to refresh

Comments 47

А если масштаб не совпадает, то не будет ведь работать?
А если масштаб не совпадает, то не будет ведь работать?

Отмаштабируйте. Прочитайте другую мою статью habrahabr.ru/post/265781 раздел Алгоритм масштабирования изображения
при этом если написать код для прогнать поиск в разных размерах образца
многократно гонять фурье преобразования для образца нет никакой необходимости
поскольку масштабирование получается в результате добавления нулевых или удаления строк и столбцов соответствующих высоким частотам в матрице фурье-образа
а лишнее нормирование делать нет необходимости
получаем что первый квадрант матрицы фурье-образа образца зафиксирована на одном месте в начале координат
а остальные квадранты матрицы перемещаются по строкам и столбцам для перемножения с фурье-образом полного изображения с последующим вычислением обратного преобразования
то же самое для фурье-образа единичной матрицы кадра
Алгоритм масштабирования изображения

В оптических системах световой поток в фокальной плоскости системы представляет собой Фурье-преобразование исходного изображения. Размер получаемого на выходе оптической системы изображения определяется соотношением фокальных расстояний объектива и окуляра.

Алгоритм:

Пусть X(N1,N2) – массив яркостей пикселей изображения.
  1. Вычислить Px = средняя (среднеквадратичная) яркость пикселей в массиве X
  2. Вычислить массив Z=FT(X) – прямое двухмерное дискретное преобразование Фурье
  3. Вычислить массив Z′=T(Z), где T – либо добавление нулевых строк и столбцов матрицы соответствующих высоким частотам, либо удаление строк и столбцов матрицы соответствующих высоким частотам для получения требуемого размера итогового изображения
  4. Вычислить массив Y=RFT(Z′) – обратное двухмерное дискретное преобразование Фурье
  5. Вычислить Py = средняя (среднеквадратичная) яркость пикселей в массиве Y
  6. Нормировать массив Y(M1,M2) по среднему уровню яркости Px/Py
В оптических системах световой поток в фокальной плоскости системы представляет собой Фурье-преобразование исходного изображения.
— вообще-то не исходного изображения, а входящего в апертуру светового поля
Спасибо, поправлю в тексте.
Хотя в том тексте я нарисовал телескопическую систему из двух линз на самом деле линзы вообще не нужны. оптическую систему предоставляет нам само пространство в котором присутствует свет.
В каком тексте? Что-то я нигде не нашел этой картинки
Я бы еще придрался к фразе:
Преобразование Фурье (ℱ) — операция, сопоставляющая одной функции вещественной переменной другую функцию, также вещественной переменной.
Особенно в оптике. Световое поле в типичных оптических задачах, как правило, описывается скалярным приближением уравнений Максвелла, а именно — комплексной скалярной функцией координат и времени. Соответственно и фурье должно быть комплексным.
нет — согласно общепринятому определению Преобразование Фурье — это функции вещественной переменной. либо времени, либо частоты.
Вы просто перепутали с возможным комплексным значением этой функции.
описывается скалярным приближением уравнений Максвелла, а именно — комплексной скалярной функцией координат и времени — да, я понимаю — Вы говорите о тензорах и сверкомплексных
UFO just landed and posted this here
Наверно.
Я ведь экономист по образованию.
Скорее уж вы перепутали, если пишете под интегралом экспоненту с мнимой единицей в показателе. Собственно, этот интеграл и есть общепринятое определение, и даже если исходная функция вещественна, то ее фурье-образ — комплексный
Да — вы правы. В реальном мире мнимого не существует. В реальном мире существует только реальное.
Нет, не о тензорах. Эта скалярная функция координат и времени описывает, как ведет себя любая из шести компонент векторов электрического или магнитного поля световой волны.
реальные — масса и длина
комплексные — плоскость которую видим
сверхкомплексные — пространство-время данные в ощущение
октарионы — неведомо
… — неведомо
а более чем… не обнаружено
Два алгоритма состыковать в один, для отсутствия лишних действий, ведь несложная задача?
Зачем городить такую колбасину? В чём преимущество перед двумя десятками существующих методов, использующихся для этой же задачки? Многие из таких методов, кстати, значительно стабильнее к искажениям, в том числе к аффинным преобразованиям.
Зачем городить такую колбасину?

Ответ — Количество требуемых вычислительных операций
Подсчитате оценку сложности — будете ли Вы удовлетворены быстродействием имеющейся у Вас техники?
Если надо один раз и на суперсовременном компе — то это статья не для вас.
Я пишу алгоритмы в том числе для DSP-процессоров и для embeded процессоров, где производительность это ограниченный ресурс. Я не понимаю как ваш алгоритм хоть как-то превосходит классические алгоритмы поиска. Вы правда считаете, что кто-то сравнивает так: «классический метод “начального уровня”, заключающийся в переборе всех координат».
Подсчитате оценку сложности Вашей задачи.
Если обрабатываете очень маленькие картинки — то эта вся методика вам вообще не нужна
Для справки — трудоёмкость дискретного преобразования Фурье быстрыми алгоритмами O(N*logN)
В приведённом алгоритме суммарная трудоёмкость будет иметь оценку равную оценке трудоёмкости одного фурье-преобразования, то есть O(N*logN)
Оценим классическую схему с попарным сравнением — это O(N*M^2)
То есть если у Вас образец всегда маленькая картинка — то даже от увеличения общего размера Вы будете наблюдать просто линейный рост трудоёмкости пропорциональный количеству пикселей.
Однако если размер образца тоже возрастает и скорость увеличения больше чем SQRT( LOG ( N ) ) то начиная с некоторого размера изображения этот алгоритм будет работать быстрее, как бы Вы не оптимизировали свой программный код в погоне за белым кроликом.
И смею Вас заверить, что на практике это N наступает довольно быстро — если библиотека быстрых преобразований написана грамотно — то уже на картинках в 100-200 пикселей. Если библиотека быстрых преобразований написана тяп-ляп на скриптовом языке — то на 1000-2000 пикселей
Почему вы так упёрлись в попарное сравнение? Неужели не знаете других алгоритмов? Да ладно, даже оно. Пирамидальный поиск? Разреженный поиск? Сегментация предварительной области для поиска через цветность/яркость? Это ускоряет его в сотни и тысячи раз. А если затачивать под конкретные задачи, то ещё больше.

Более того, почему вы упёрлись в размер картинки? Я на raspberry Pi обрабатывал мегапиксельные кадры для поиска интересных объектов. При этом объектов не имеющих стабильную форму.
Для справки, поиск примитива на интегральном изображении O(N). Не зря Хаар на нём сделан. И большая часть алгоритмов хэширования изображений. Поиск через FFT и любой локальный классификартор значительно стабильнее и тоже ~N (хотя там достаточно большой коэффициент пропорциональности).

Почему вы так упёрлись в попарное сравнение? Неужели не знаете других алгоритмов? Да ладно, даже оно. Пирамидальный поиск? Разреженный поиск? Сегментация предварительной области для поиска через цветность/яркость? Это ускоряет его в сотни и тысячи раз. А если затачивать под конкретные задачи, то ещё больше.

Ответ — в основе всего что Вы перечислили всё равно будет лежать некий базовый алгоритм и чаше всего в разных пакетах это попарное сравнение.
Вам никто не мешает и этот алгоритм модифицировать
Например, методом ветвей и границ или каким умеет способом:
сперва сжать изображение и ограничить зону поиска выбором из полученной матрицы оценок несколько наибольших значений.
затем повторить алгоритм но уже только в более достоверных регионах

и как Вы правильно выразились — это ускоряет его в сотни и тысячи раз. (но не миллионы)

повторю ещё раз — на практике эффективность метода можно наблюдать уже на довольно небольших размерах изображений.
Кстати для предварительной оценки не только формулы из статьи можно использовать — кроме фурье преобразований существует и масса других не менее интересных преобразований — но видимо, сейчас это не входит в программу обучения.
и здесь описан алгоритм для задачи один-к-одному
можете сами модифицировать для задачи многие-ко-многим
оптом — дешевле
Разрешите и Вам задать вопрос по программам и алгоритмам.
Какая из сортировок выполняется на компьютере быстрее?
Варианты:
А. Пузырьковая сортировка
Б. Быстрая сортировка

Совет.
Прежде чем ответить однозначно, подумайте ещё раз.
Угу. И строить фурье-преобразование с маской на изображении, по разреженной выборке и пиромидальное так же просто и быстро, как определённого размера блока. Ну-ну. У вас там доступ в память занимает больше времени чем само сравнение.

К тому же вы так же продолжаете игнорировать методы, пропорциональные N, которые решают задачи поиска даже для огромных изображений при большом количестве шумов и искажений.

Впрочем, видя, как вы нервничаете от моих комментариев, отвечая тремя-пятью на каждый, я предпочту откланяться. Конструктивной беседы нет, ни с одним адекватным методом поиска сравнения не приведено.
Жаль.
Хоть Вы и не смогла дать ответ на вопрос какая из сортировок работает на компьютере быстрее, поскольку не понимаете разницы между терминами алгоритм и программа.
Я хочу посоветовать изучить эту тему на примере другого проекта, посвящённого сравнению времени вычислений на CUDA и MPI некоторых алгоритмов сортировок
github.com/dprotopopov/ParallelSorting

К тому же вы так же продолжаете игнорировать методы, пропорциональные N

А вы опишите их по шагам для той же самой задачи.
Вместе рассчитаем количество элементарных операций.
Я добавлю те же ускорители которые у Вас будут в описании, а может и не буду добавлять.
И мы посчитаем количество элементарных операций.

сравним два этих значения и Вы сами решите — надо ли Вам пользоваться этим алгоритмом или нет.
колхоз — дело добровольное
Есть и метод с оценкой O(1) — называется «пальцем в небо»
Алгоритм:
Пусть даны два изображения X и Y – изображение и образец, размеров (N1,N2) и (M1,M2) соответственно и Ni > Mi
Требуется найти координаты образца Y в полном изображении X и вычислить оценочную величину — меру близости.
1. Тыкаем в случайную точку на изображеении Y и берём первое число пришедшее в голову
Полученный результат будем рассматривать как решение задачи
И ещё замечание по поводу DSP-процессоров и для embeded процессоров
Видимо Вы занимаетесь написанием софта для телескопов.

Всякое уменьшение количества операций при анализе изображений без увеличения суммарной ошибки первой и второго рода невозможно если на анализируемое изображение не наложены предоговоренные ограничения.
Если Вы пишете софт для анализа картинок звёздного неба, и при этом пользуетесь софтом который проводит операции сравнения за число шагов равное размеру картинки, то это однозначно указывает, что у Вас уже существует набор предопределённых условий и Ваш софт просто будет отбрасывать всё что не входит в Ваше представление о вселенной.
Вывод.
На Ваших телескопах никогда не будет совершено ни одного открытия — поскольку они будут показывать только то что и та всем известно.
Видимо Вы занимаетесь написанием софта для телескопов

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

Если же вы производите анализ звёздного неба, то мне вообще непонятно зачем Вам растровые изображения.
Запишите координаты светлых пикселей в таблицу, а дальше просто крутите данными.
Надеюсь, тему расчёт параметров распределений по наблюдаемым данным Вы всё же проходили, теорию вероятностей, статистические критерии и тд?
По любому — если графическое изображение являет собой практически полное чёрное поле, не фиксируемое сенсорами телескопа, то как ни крути — явные вычисления формул по таблицам будет быстрее и надёжнее чем расчёты на каких-то сетках с ячейками поддерживающими точность в пару бит.
Конечно придётся посидеть с карандашом и бумагой, чтобы выписать формулы.
по разреженной выборке

а у Вас по математике вопроса не возникло — не будет в приведённом алгоритме одни деления на ноль на Ваших данных?
ответ — да, на Ваших данных, практически везде будет деление на ноль.
А почему?
Ответ — а потому, что в данном алгоритме в качестве меры близости выбрана формула соответствующая типовой модели фотографии — где снимки квадратов малевича не делают. То есть отброшены маловероятные варианты из рассмотрения.
А можно по-другому?
Да — можно. Надо изменить предполагаемую модель исходных изображений.

Я расстроен уровнем научных степеней.
Я расстроен уровнем научных степеней.

Я делал лабы за студентов МФТИ по расчёту задач с краевыми условиями на решетках.
Преподаватель дал такие краевые условия, что получалось что аналитические функции действительного переменного имеют вычет, что может быть только начиная с функций комплексного переменного. Естественно мой результат не совпал с записанным в ответах поскольку расчёты из-за этого противоречия уходили неизвестно куда. Исправилось только после того как я выкинул часть условий из первоначально заданных краевых ограничений.
А ведь другие студенты сдавали так сказать верные решения со всеми этими несоответствиями и получали отличные оценки.
как это возможно — да очень просто — не важно что как считает, главное как отчитаться.
Посмотрел Ваши публикации — понял Вам практически ничего не рассказывали о теории вероятности — поэтому понятия ошибок первого и второго рода Вы не упоминаете в своих публикациях.
Отсюда у Вас и впечатление. что нет конструктивной беседы, и что метод с оценкой ~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
при этом если написать код для прогона поиска в разных размерах образца
многократно гонять фурье преобразования для образца нет никакой необходимости
поскольку масштабирование получается в результате добавления нулевых или удаления строк и столбцов соответствующих высоким частотам в матрице фурье-образа
а лишнее нормирование делать нет необходимости
получаем что первый квадрант матрицы фурье-образа образца зафиксирован на одном месте в начале координат
а остальные квадранты матрицы перемещаются по строкам и столбцам для перемножения с фурье-образом полного изображения с последующим вычислением обратного преобразования
то же самое для фурье-образа единичной матрицы кадра
Only those users with full accounts are able to leave comments. Log in, please.