Jump to content

    

getch

Участник
  • Content Count

    117
  • Joined

  • Last visited

Everything posted by getch


  1. Спасибо, посмотрел книгу. Срезюмировав: Не совсем понял, что вы хотели сказать своим постом. Если задать норму вектор-столбца, как сумму квадратов разниц соседних элементов, то, вроде, задача сводится к нахождению вектора, индуцирующего матричную норму. Но как приведенные выше свойства индуцированной матричной нормы помогут решить задачу? Я запомнил данный Вами замечательный итерационный алгоритм нахождения собственного вектора, соответствующего максимальному собственному значению матрицы. Поэтому данная ранее перефломулировка задачи через матрицу A = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V) видится наиболее оптимальной на данный момент.
  2. Матрица сдвига, конечно, получается огромной - NxN (N - количество элементов в исходном векторе Vi). Т.е. ее для перемножения использовать совсем нерезонно на практике. Проще алгоритмом сразу. Спасибо, задача теперь решена полностью. В выкладках заинтересовал такой нюанс, что если бы использовалась не матрица-сдвига, а матрица любого преобразования, то все равно не потребовалось бы ее искать. Достаточно лишь знать алгоритм преобразования. Выходит, эксплуатируется какое-то фундаментальное свойство, что любое преобразование можно задать умножением на соответствующую матрицу. Не очевидно совсем.
  3. Если переписать матрицу A следующим образом: A = V'*V - V'*S*V -V'*S'*V + V'*S'*S*V = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V) то S-матрица-сдвига будет присутствовать только в виде (S*V), значит можно не гадать, как выглядит матрица-сдвига, а делать упомянутый выше сдвиг индексов в самом алгоритме. Скажите, нет ли ошибки в таких рассуждениях?
  4. Спасибо за подробный ответ! Подскажите, как выглядит матрица сдвига в данном случае? Вместо нее делал бы сдвиг индексов в самом алгоритме, но в выражении ниже ее надо и транспонировать и другое. Т.е. без явного вида не представляю, как обойтись. Жирным шрифтом подправил неточности. k - собственный вектор матрицы A, соответствующий максимальному собственному значению матрицы A. Правильно ли понимаю, что для такого решения условия равенства нулю суммы элементов каждого исходного вектора Vi, а также единичной длины искомого вектора-стобца k не обязательны?
  5. Да, вектора относительно удобные для мат. аппарата, которым, к сожалению, владею крайне слабо. Поэтому и прошу помощи.
  6. Понимаю, что решение в лоб всегда существует. В лоб - ГА, примененный к любой целевой функции. Естественно, о подходах к решению задачи спрашивал с другой целью - получить какие-то значительно более быстро-считающие варианты решения. Т.е. в идеале что-то близкое к аналитическому решению. Например, переход от огромной размерности векторов к существенно более компактной их ковариационной матрице. И далее работа уже с ней.
  7. Только максимизировать надо не саму сумму векторов, а определенную выше функцию F от этой суммы - F(K1 * V1 + ... + Kn * Vn). F - сумма модулей (или квадратов) разностей соседних элементов вектора.
  8. Это произведение числа на вектор: Ki - вещественные числа. Vi - вектора. V[j] - j-й элемент вектора V.
  9. Приветствую всех! На данном форуме мне очень здорово когда-то помогли в решении некоторых задач. Поэтому решил еще раз обратиться к уважаемому сообществу с просьбой дать дельный совет/рекомендации, как подступиться к решению такой задачи: Определена такая функция для любого вектора: F(V) = Sum(Abs(V[j] - V[j + 1])) , либо F(V) = Sum((V[j] - V[j + 1])^2)) Даны одинаковой размерности вектора V1, V2, ..., Vn, у каждого из которых сумма его элементов равна нулю. Нужно найти вектор NewV = K1 * V1 + K2 * V2 + ... + Kn * Vn, где Sum(Abs(Ki)) = 1, либо Sum(Ki^2) = 1 значение F(NewV) которого было бы максимальным. У меня есть гипотеза, что всегда верно неравенство F(NewV) <= max(F(V1), F(V1), ...., F(Vn)), т.е. решением задачи является вектор коэффициентов, где один элемент равен ±единице, а остальные - нули. Возможно, кому-то известно решение схожей или частного случая этой задачи. Спасибо.
  10. Существует итерационный алгоритм расчета СКО сдвинутого окна через СКО окна до сдвига. Нормировка делается через деление фрагмента на его почти бесплатно полученное СКО. При этом Среднее каждого фрагмента обнулять не требуется при сравнении. Надо лишь один раз отнормировать сам шаблон (что ищется) к СКО = 1 и Ср. = 0.
  11. Алгоритмическая сложность такого метода "лобовая" - O(N^2). Быстрая корреляция через БПФ значительно эффективнее - O(N * log(N)).
  12. Поискал в интернете схожие задачи. Выкладываю ссылки, возможно, кому-то пригодятся: Контурный анализ. Видео создания шаблона. Видео нахождения шаблона(-ов). Обнаружение устойчивых признаков изображения: метод SURF. «Выглядит похоже». Как работает перцептивный хэш. Алгоритм быстрого нахождения похожих изображений. Презентация «Поиск изображений. Методы индексирования изображений. Методы на основе хэш-функций. Обучение метрик. Фильтры объектов для классификации и поиска изображений.» (из курса лекций Введение в компьютерное зрение) Блог Распознавание образов для программистов. Тематические реализации (поисковики): Поиск изображений по исходному изображению. Распознавание шрифта по картинке. Поиск песни по ритму. Поиск песни по аудио-образцу. Поиск песни по напеву.
  13. На другом форуме есть очень схожая по задаче тема: Распознавание звукового сигнала (звука) по образцам. Привожу цитату одного поста оттуда: Т.е. предлагаются альтернативные корреляции варианты, а также упоминается возможность значительного уменьшения признаков сравнения. Кто-нибудь использовал отличные от корреляционного методы или занимался уменьшением признаков сравнения? У меня корреляция через оптимизированный (насколько мог) БПФ считается, к сожалению, не так быстро, как хотелось бы.
  14. Да, с каждым новом шаблоном нужно считать корреляцию во всем множестве точек исходного сигнала. И тут есть две ситуации: 1. Меняется только шаблон, сигнал - нет. Тогда БПФ сигнала делать повторно не требуется при расчете корреляции. Делается только прямое БПФ шаблона и обратное БПФ. 2. Меняется и шаблон и сигнал (добавляется один отсчет). Вот тут и хочу БПФ сигнала с новым отсчетом получить из ранее посчитанного БПФ сигнала без этого отсчета.
  15. Видимо, я плохо пояснил. Дело в том, что при поступлении нового отсчета меняется и шаблон. Поэтому без БПФ не обойтись. Всвязи с этим желательно производить из предыдущего БПФ (сигнала, не шаблона) новый, т.к. вычислять полностью БПФ по приходу каждого нового отсчета - очень дорого.
  16. Герцеля смотрел ранее, но перед тем, как его применить, провел следующий эксперимент: 1. Сделал RealFFT(Signal, SignalLen), в массиве на выходе посмотрел значение элемента с номером SignalLen. 2. Сделал RealFFT(Signal, SignalLen + 1), в массиве на выходе посмотрел значение элемента также с номером SignalLen. Соответствующие элементы оказались не равны. Т.е. в общем случае получается, что нет никаких совпадений между RealFFT(Signal, SignalLen) и RealFFT(Signal, SignalLen + 1). Это так и должно быть (ведь тогда Герцель неприменим)? Или же это особенность вещественной реализации БПФ и надо переходить на комплексную, чтобы получить совпадение?
  17. Подскажите, есть ли возможность из RealFFT(Signal, SignalLen) получить RealFFT(Signal, SignalLen + 1)? Т.е. при приходе нового значения сигнала нужно ли проделывать полностью БПФ или же можно из предыдущего результата БПФ получить текущий?
  18. Врубился, как сделать. Надо лишь перед БПФ привести шаблон к нулевому среднему и СКО единица. А после вычисления через БПФ быстрой корреляции делить полученные элементы массива значений КК на СКО соответствующих выборок в сигнале. При этом вычисление этих СКО дается практически бесплатно - итерационно.
  19. Написал алгоритм быстрой корреляции через БПФ. Как понял, быстрая корреляция, это то, что и ранее предлагалось - сумма попарных произведений. Но такой критерий похожести явно не работает в общем случае (когда у выборок МО != 0 и СКО != 1), т.к. максимум такой корреляции показывает совсем не там, где надо. Подскажите, как от быстрой корреляции перейти к Пирсону с той же эффективностью алгоритма O(N * log(N))?
  20. Так мне же и надо иметь (Len - N) значений КК, чтобы среди них выбрать максимальное абсолютное значение. Т.е. если делать в лоб, то надо вычислить (Len - N) скалярных произведений векторов длины N. Поэтому и интересуюсь быстрой корреляцией через БПФ, БПХ и другие методы. Можете пояснить более подробно для слабо-разбирающегося в ЦОС?
  21. Похоже, вы вычисляете для каждой точки свой КК в лобовую (~O(N^2)). Хотя это не совсем КК. Ведь КК был бы равен сумме попарных произведений, если у каждого варианта средняя была бы равна нулю и СКО - единице. Спорное утверждение. Ведь КК(шаблон; перевернутый по X шаблон) не равен нулю.
  22. Спасибо за ответ! Вроде, задачи разные. Но судя по описанию к видео (ниже), у вас то, что нужно. Могли бы вы более подробно описать решенную Вами задачу и алгоритм-идею? За исходники спасибо. Еще не разбирался в них. По своей задаче поясню на простом примере. Шаблон имеет 1000 точек. Исходный ВР имеет 100 000 точек. Это значит, что шаблон надо "сравнить" (как вариант - через КК) с 99 000 (100 000 - 1000) вариантами. Или же, если шаблон является частью ВР, то с 98 000 вариантами. Надеюсь, понятно объяснил.
  23. Приветствую всех! Я от ЦОС далек, но задача, по-моему, найдет здесь понимание. Постановка задачи: 1. Есть ВР (временной ряд (вещественный), LEN точек), который с определенной частотой дополняется новым членом. 2. Есть Шаблон - N точек. 3. Надо найти в ВР участок, который наиболее сильно "похож" на Шаблон. Соответственно, в этом участке тоже N точек. Критерием похожести я выбрал КК (коэффициент корреляции). Т.е. задача сводится к нахождению максимума абсолютного значения КК. Нашел два оптимизированных алгоритма расчета быстрой корреляции: через БПФ (вещественное) и БПХ (Хартли). Честно говоря, математическую часть алгоритмов слабо понимаю. И у меня возникло несколько вопросов: 1. Имеет ли смысл для моей задачи (с точки зрения скорости выполнения) использовать алгоритм БПФ для длин векторов, не являющихся степенями двойки? Это работы Бейли, Просекова и другие. 2. БПФ Винограда? 3. Возможно, есть другой эффективный критерий похожести, отличный от КК. 4. Задача, очевидно, стандартная и максимально эффективный велосипед уже давно изобретен. Подскажите, как официально она называется? 5. Какие могут быть оптимизации, чтобы не проделывать полностью вычисления БПФ? Поясню ниже на примере двух случаев: 1. Шаблон - это крайние N точек исходного ВР из Len точек. Пришло новое значение ВР, т.е. его длина стала (Len + 1) точек. Шаблон, соответсвенно "сместился" вправо (изменился) тоже на одно значение. БПФ заново пересчитывать? 2. Шаблон - это какой-то участок из N точек исходного ВР. Если я сдвигаю шаблон на одну точку в какую-то сторону, БПФ надо будет полностью пересчитывать? И еще один вопрос, если надо найти похожий участок не только на шаблон, но и на "перевернутый шаблон" - точки в обратном направлениии (Было {1, 2, 5, 7}, стало {7, 5, 2, 1}), то можно ли из "нормального" БПФ перейти эффективно к "перевернутому" БПФ? Уверен, моя косноязычная формулировка задачи вызовет улыбку у форумчан, особенно у гуру. Но это все же хорошие эмоции. Готов учиться и вникать. P.S. Если возможно, разъясните на более понятном языке, что имелось в виду в этом посте (Сообщение #28)?
  24. Поскажите, какие более оптимальные подходы могут быть в решении такой задачи: Текущее решение имеет сложность 2^N: