Здравствуйте, tinytjan, Вы писали:

T>Народ! Помогите!!!
T>Задача такая:
T>Дан набор точек(координаты х и у).Этот набор является эталонным. Назовем его (Е)
T>Есть еще один набор точек(координаты х и у, назовем его (Х)), повернутый, смещенный и смасштабированный (Е). Причем незначительная часть точек и набора (Е) может отсутствовать и могут присутствовать 'левые' точки, которых не было в исходном наборе.
T>Необходимо найти такое преобразование(Е) (смещение, масштабирование и поворот) при котором точки (Е) будут преобразовываться в точки (Х) оптимальным образом.
T>набор (Е)
T>
T>набор(Х)
T>

Гы! Уж не номерок-ли автомобильный ты выравнивать собрался? Что-то не пойму, ты же только что писал, что с этим твоя нейросеть справляется на раз-два . А тут вдруг — "помогите"?

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Хе-хе!

G>>!!!!!!

G>>А мы ее уберем до нуля. После совершения всех описанных мной преобразований ты легко выделишь "левые" точки как наиболее удаленные от точек образца, выкинешь их, и повторишь всю процедуру. После чего получишь 100% совпадение.
T>Чтобы все было так легко Левые точки необязательно будут самые удаленные.
Ты не понял. Все на самом деле так легко.
T>Если бы от них можно было избавиться все было бы тип-топ.Построил внешний прямоугольник и твори че хошь.
Какой внешний прямоугольник, боже упаси?! Метрику я ввел, помнишь? Чтобы ее посчитать, ты каждой точке образца ставишь в соответствие ближайшую к ней точку тестового набора, и считаешь сумму расстояний, так?

Так вот, "левыми" будут те точки тестового набора, которые не сопоставлены ни одной точке образца. Так как соответствие точек получается 1 в 1, то все наиболее удаленные точки уйдут. Понятно?

G>>Есть такой метод. Надо попытаться определить направляющие оси на тестовом наборе точек (пользуясь тем, что точки выравнены по сетке), после чего тебе понадобится всего 4 сравнения для определения угла.
T>Проблема остается. Мы можем взять левые точки.
Левые точки выравнены по сетке, или нет? И в конце концов, сколько процентов левых точек от общего числа?

Народ! Помогите!!!
Задача такая:
Дан набор точек(координаты х и у).Этот набор является эталонным. Назовем его (Е)
Есть еще один набор точек(координаты х и у, назовем его (Х)), повернутый, смещенный и смасштабированный (Е). Причем незначительная часть точек и набора (Е) может отсутствовать и могут присутствовать 'левые' точки, которых не было в исходном наборе.
Необходимо найти такое преобразование(Е) (смещение, масштабирование и поворот) при котором точки (Е) будут преобразовываться в точки (Х) оптимальным образом.
набор (Е)

набор(Х)

Здравствуйте, Gaperton,
Издеваться всякий может.Не до приколов мне сейчас . Мне помощь нужна ,и срочно. Если интересно, то не номера автомобильные мне ворочать не надо. А надо найти контур компонента для печатных плат и положение его ножек на зашумленной картинке.Это надо для того, чтобы скорректировать головку, которая компонент на плату ставит.
А набор (Е) это набор центров пятен, которые 'типа' являются ножками компонента.(т.е. 'типа' ножка на самом деле может быть шумом).
Нейронка здесь не поможет -- просто всунуть некуда.

Лучшим методом на сег. день является RANSAC. или очень хорошая реализация метода ветвей и границ.


RANSAC делать быстрее , а МВГ дает лучшею robustness.

А чем именно не подходит SIFT и RANSAC которы еможно чуть подизменить ? Демка для WIN находится тут
http://www.autostitch.net/

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton,
T>Издеваться всякий может.Не до приколов мне сейчас . Мне помощь нужна ,и срочно.
Раз не до приколов, то сформулируй наконец математически, что означает "оптимальным образом".

Здравствуйте, Gaperton, Вы писали:

G>Здравствуйте, tinytjan, Вы писали:
G>Раз не до приколов, то сформулируй наконец математически, что означает "оптимальным образом".
На словах оптимальным образом --> набор точек (Е) должен отображаться в (Х) так, чтобы расстояние от полученной до реальной точки набора (Х) было минимальным (для всех — сумма расстояний).
Пробовал построить решетку (прикол в том что реальные точки лежат на параллельных прямых) методом МНК — нормальных результатов не получилось.

Здравствуйте, minorlogic, Вы писали:

M>Лучшим методом на сег. день является RANSAC. или очень хорошая реализация метода ветвей и границ.


M>RANSAC делать быстрее , а МВГ дает лучшею robustness.

M>А чем именно не подходит SIFT и RANSAC которы еможно чуть подизменить ? Демка для WIN находится тут
M>http://www.autostitch.net/
Я не знаю подходит или нет. Если можешь, поподробнее пожалуйста.
Заранее спасибо.

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Здравствуйте, tinytjan, Вы писали:
G>>Раз не до приколов, то сформулируй наконец математически, что означает "оптимальным образом".
T>На словах оптимальным образом --> набор точек (Е) должен отображаться в (Х) так, чтобы расстояние от полученной до реальной точки набора (Х) было минимальным (для всех — сумма расстояний).
А может, так? "Количество полностью совпавших точек образца с паттерном должно быть максимальным".

T>Пробовал построить решетку (прикол в том что реальные точки лежат на параллельных прямых) методом МНК — нормальных результатов не получилось.
Тот критерий, что ты задал — и есть требование наименьшего отклонения. Точки паттерна по такому критерию могут (и будут) лежать между точек образца. Ты уверен, что это то, что тебе надо?

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Здравствуйте, tinytjan, Вы писали:
G>>Раз не до приколов, то сформулируй наконец математически, что означает "оптимальным образом".
T>На словах оптимальным образом --> набор точек (Е) должен отображаться в (Х) так, чтобы расстояние от полученной до реальной точки набора (Х) было минимальным (для всех — сумма расстояний).
T>Пробовал построить решетку (прикол в том что реальные точки лежат на параллельных прямых) методом МНК — нормальных результатов не получилось.

Оптимальным образом, значит что E как бы должен накладываться на X причем "левые" точки должны не учитываться. Задача достаточно интеллектуальная.

Здравствуйте, Gaperton, Вы писали:

G>А может, так? "Количество полностью совпавших точек образца с паттерном должно быть максимальным".
Похоже, то что нужно

T>>Пробовал построить решетку (прикол в том что реальные точки лежат на параллельных прямых) методом МНК — нормальных результатов не получилось.
G>Тот критерий, что ты задал — и есть требование наименьшего отклонения. Точки паттерна по такому критерию могут (и будут) лежать между точек образца. Ты уверен, что это то, что тебе надо?
Я уже уверен, что мне это не надо. Результаты никакие

Здравствуйте, tinytjan, Вы писали:

T>Пробовал построить решетку (прикол в том что реальные точки лежат на параллельных прямых) методом МНК — нормальных результатов не получилось.
Далее — всегда-ли точки лежат в узлах квадратной сетки с равномерным известным шагом?

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Здравствуйте, tinytjan, Вы писали:
G>>Раз не до приколов, то сформулируй наконец математически, что означает "оптимальным образом".
T>На словах оптимальным образом --> набор точек (Е) должен отображаться в (Х) так, чтобы расстояние от полученной до реальной точки набора (Х) было минимальным (для всех — сумма расстояний).
T>Пробовал построить решетку (прикол в том что реальные точки лежат на параллельных прямых) методом МНК — нормальных результатов не получилось.


Обычный МНК не пойдет, нужно outliers отбрасывать обязательно. Есть вроде метод взвешенных наименьших квадратов. А вообще если все "правильные" точки должны лежать на прямых, то может преобразование Хафа сюда прикрутить, а потом прямые между собой сопоставлять? Вроде как гораздо устойчивее к шуму получается (т.к. преобразование куммулятивное).

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, minorlogic, Вы писали:

M>>Лучшим методом на сег. день является RANSAC. или очень хорошая реализация метода ветвей и границ.


M>>RANSAC делать быстрее , а МВГ дает лучшею robustness.

M>>А чем именно не подходит SIFT и RANSAC которы еможно чуть подизменить ? Демка для WIN находится тут
M>>http://www.autostitch.net/
T>Я не знаю подходит или нет. Если можешь, поподробнее пожалуйста.
T>Заранее спасибо.

А может скачать демку ? Куда еще более подробно чем работающая демка и описания алгоритмов ? ткнуть в исходники ?

Здравствуйте, Gaperton, Вы писали:

G>Далее — всегда-ли точки лежат в узлах квадратной сетки с равномерным известным шагом?

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

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Далее — всегда-ли точки лежат в узлах квадратной сетки с равномерным известным шагом?

T>Нет не всегда. Какая то погрешность по любому присутствует.Точки находятся как центр масс фигуры и могут быть найдены неточно. Разбежка будет несколько пикселов. Левые точки могут располагаться произвольно.

Ну, если так, то нечто близкое к решению мы получим так:
1) Найди центр масс наблюдаемой системы точек, и совмести его с центром масс образца.
2) Посчитай дисперсию наблюдаемой системы точек, и смасштабируй (увеличение/уменьшение) ее так, чтобы дисперсия совпала с дисперсией образца.
3) Теперь определяем оптимальный поворот. Тебе нужет угол поворота такой, при котором метрика между образцом и системой точек минимальна. Метрику можно вводить по разному, можно попробовать так:
Сумма по всем точкам образца расстояний от точки образца до ближайшей точки системы.

Здравствуйте, Gaperton, Вы писали:

G>Здравствуйте, tinytjan, Вы писали:

T>>Здравствуйте, Gaperton, Вы писали:

G>>>Далее — всегда-ли точки лежат в узлах квадратной сетки с равномерным известным шагом?

T>>Нет не всегда. Какая то погрешность по любому присутствует.Точки находятся как центр масс фигуры и могут быть найдены неточно. Разбежка будет несколько пикселов. Левые точки могут располагаться произвольно.

G>Ну, если так, то нечто близкое к решению мы получим так:
G>1) Найди центр масс наблюдаемой системы точек, и совмести его с центром масс образца.
G>2) Посчитай дисперсию наблюдаемой системы точек, и смасштабируй (увеличение/уменьшение) ее так, чтобы дисперсия совпала с дисперсией образца.
Я думаю 'левые' точки будут влиять на центр масс и на дисперсию. То есть мы получим не реальный масштаб и центр масс а с погрешностью. Если центр может искаться и нормально, то масштаб скорее всего будет неточным.
G>3) Теперь определяем оптимальный поворот. Тебе нужет угол поворота такой, при котором метрика между образцом и системой точек минимальна. Метрику можно вводить по разному, можно попробовать так:
G>Сумма по всем точкам образца расстояний от точки образца до ближайшей точки системы.
Попробую, конечно. Но количество операций для количества точек в образце и зашумленном наборе ~N получится
примерно 90*N*N(если мы хотим найти угол с точностью до градуса, чем больше точность тем пропорционально больше вычислений).
Если можешь(и есть желание), предложи че-нить поэффективнее. А пока за это спасибо.

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Здравствуйте, tinytjan, Вы писали:

T>>>Здравствуйте, Gaperton, Вы писали:

G>>>>Далее — всегда-ли точки лежат в узлах квадратной сетки с равномерным известным шагом?

T>>>Нет не всегда. Какая то погрешность по любому присутствует.Точки находятся как центр масс фигуры и могут быть найдены неточно. Разбежка будет несколько пикселов. Левые точки могут располагаться произвольно.

G>>Ну, если так, то нечто близкое к решению мы получим так:
G>>1) Найди центр масс наблюдаемой системы точек, и совмести его с центром масс образца.
G>>2) Посчитай дисперсию наблюдаемой системы точек, и смасштабируй (увеличение/уменьшение) ее так, чтобы дисперсия совпала с дисперсией образца.
T>Я думаю 'левые' точки будут влиять на центр масс и на дисперсию. То есть мы получим не реальный масштаб и центр масс а с погрешностью. Если центр может искаться и нормально, то масштаб скорее всего будет неточным.

Хе-хе!

!!!!!!

А мы ее уберем до нуля. После совершения всех описанных мной преобразований ты легко выделишь "левые" точки как наиболее удаленные от точек образца, выкинешь их, и повторишь всю процедуру. После чего получишь 100% совпадение.

G>>3) Теперь определяем оптимальный поворот. Тебе нужет угол поворота такой, при котором метрика между образцом и системой точек минимальна. Метрику можно вводить по разному, можно попробовать так:
G>>Сумма по всем точкам образца расстояний от точки образца до ближайшей точки системы.
T>Попробую, конечно. Но количество операций для количества точек в образце и зашумленном наборе ~N получится
T>примерно 90*N*N(если мы хотим найти угол с точностью до градуса, чем больше точность тем пропорционально больше вычислений).
T>Если можешь(и есть желание), предложи че-нить поэффективнее. А пока за это спасибо.

Есть такой метод. Надо попытаться определить направляющие оси на тестовом наборе точек (пользуясь тем, что точки выравнены по сетке), после чего тебе понадобится всего 4 сравнения для определения угла.

Здравствуйте, Gaperton, Вы писали:

G>Хе-хе!

G>!!!!!!

G>А мы ее уберем до нуля. После совершения всех описанных мной преобразований ты легко выделишь "левые" точки как наиболее удаленные от точек образца, выкинешь их, и повторишь всю процедуру. После чего получишь 100% совпадение.
Чтобы все было так легко Левые точки необязательно будут самые удаленные.
Если бы от них можно было избавиться все было бы тип-топ.Построил внешний прямоугольник и твори че хошь.

G>>>3) Теперь определяем оптимальный поворот. Тебе нужет угол поворота такой, при котором метрика между образцом и системой точек минимальна. Метрику можно вводить по разному, можно попробовать так:
G>>>Сумма по всем точкам образца расстояний от точки образца до ближайшей точки системы.
T>>Попробую, конечно. Но количество операций для количества точек в образце и зашумленном наборе ~N получится
T>>примерно 90*N*N(если мы хотим найти угол с точностью до градуса, чем больше точность тем пропорционально больше вычислений).
T>>Если можешь(и есть желание), предложи че-нить поэффективнее. А пока за это спасибо.

G>Есть такой метод. Надо попытаться определить направляющие оси на тестовом наборе точек (пользуясь тем, что точки выравнены по сетке), после чего тебе понадобится всего 4 сравнения для определения угла.
Проблема остается. Мы можем взять левые точки.

Здравствуйте, Gaperton, Вы писали:

G>Ты не понял. Все на самом деле так легко.
T>>Если бы от них можно было избавиться все было бы тип-топ.Построил внешний прямоугольник и твори че хошь.
G>Какой внешний прямоугольник, боже упаси?! Метрику я ввел, помнишь? Чтобы ее посчитать, ты каждой точке образца ставишь в соответствие ближайшую к ней точку тестового набора, и считаешь сумму расстояний, так?

G>Так вот, "левыми" будут те точки тестового набора, которые не сопоставлены ни одной точке образца. Так как соответствие точек получается 1 в 1, то все наиболее удаленные точки уйдут. Понятно?

Да в приципе это вариант.
Некоторые Левые точки может и останутся, но в конце концов процедуру можно повторить еще раз или два.
Спасибо

G>>>Есть такой метод. Надо попытаться определить направляющие оси на тестовом наборе точек (пользуясь тем, что точки выравнены по сетке), после чего тебе понадобится всего 4 сравнения для определения угла.
T>>Проблема остается. Мы можем взять левые точки.
G>Левые точки выравнены по сетке, или нет? И в конце концов, сколько процентов левых точек от общего числа?
Левые точки расположены КАК УГОДНО и соответственно могут попасть в сетку.
А процент может варьироваться в зависимости от количества эталонных точек.
Если точек больше хотя бы 50 то процент можно брать не больше 10-15%
Если больше 200-300 , то 3-5%. И так далее.
Так что на нормальном количестве точек покатит думаю без проблем

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Ты не понял. Все на самом деле так легко.
T>>>Если бы от них можно было избавиться все было бы тип-топ.Построил внешний прямоугольник и твори че хошь.
G>>Какой внешний прямоугольник, боже упаси?! Метрику я ввел, помнишь? Чтобы ее посчитать, ты каждой точке образца ставишь в соответствие ближайшую к ней точку тестового набора, и считаешь сумму расстояний, так?

G>>Так вот, "левыми" будут те точки тестового набора, которые не сопоставлены ни одной точке образца. Так как соответствие точек получается 1 в 1, то все наиболее удаленные точки уйдут. Понятно?

T>Да в приципе это вариант.
T>Некоторые Левые точки может и останутся, но в конце концов процедуру можно повторить еще раз или два.
Не останется не одной. За один проход уйдут все — соответствие точек 1 в 1. Процедуру повторять не придется.

T>Спасибо
На здоровье.

Здравствуйте, Gaperton,
Перед тем как реализовывать, решил еще раз все перечитать и обмозговать.
И стопорнулся на таком вопросе:
как можно соместить два этих набора (эталонный и рассматриваемый) (совмещение по углу поворота)
без учета того, что точки расположены по сетке? То есть к сетке привязываться нежелательно.
Подойдет ли простой регрессионный анализ(две перпендикулярные наилучшие прямые)?
Или надо опять изобретать паровоз?

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton,
T>Перед тем как реализовывать, решил еще раз все перечитать и обмозговать.
T>И стопорнулся на таком вопросе:
T>как можно соместить два этих набора (эталонный и рассматриваемый) (совмещение по углу поворота)
T>без учета того, что точки расположены по сетке? То есть к сетке привязываться нежелательно.
Я думаю, их надо плавно крутить друг относительно друга вогруг центров масс (с некоторым шагом, как ты и писал). И искать минимум меры. Это небыстро, но учитывая количество точек, производительность процов и время реакции механики вполне может прокатить. Уж для доказательства работоспособности идеи точно прокатит. Что удобно, при таком подходе совершенно не волнует то, что точки выравнены по сетке.

T>Подойдет ли простой регрессионный анализ(две перпендикулярные наилучшие прямые)?
Это как?

Здравствуйте, Gaperton, Вы писали:

T>>Подойдет ли простой регрессионный анализ(две перпендикулярные наилучшие прямые)?
G>Это как?
Одна прямая — наилучшая по принципу минимума суммы расстояний от этой прямой до всех точек набора (Х).
Вторая прямая будет находиться по такому же принципу, с условием сто она перпендикулярна первой.
Таким же макаром находятся оси для набора (Е)
Так мы находим локальные системы координат для обоих наборов точек, а затем происходит наложение
совмещением этих систем координат. (естественно точки предварительно отмасштабированы)
Подойдет ли такая штука?
Между прочим масштабировать можно также с помощью этих прямых.

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

T>>>Подойдет ли простой регрессионный анализ(две перпендикулярные наилучшие прямые)?
G>>Это как?
T>Одна прямая — наилучшая по принципу минимума суммы расстояний от этой прямой до всех точек набора (Х).
T>Вторая прямая будет находиться по такому же принципу, с условием сто она перпендикулярна первой.
T>Таким же макаром находятся оси для набора (Е)
T>Так мы находим локальные системы координат для обоих наборов точек, а затем происходит наложение
T>совмещением этих систем координат. (естественно точки предварительно отмасштабированы)
T>Подойдет ли такая штука?
T>Между прочим масштабировать можно также с помощью этих прямых.

Мне кажется, это работать не будет. Кстати, вот что мне подумалось. Если ты собираешься ставить роботом микросхему в плату, как ты выберешь правильную ориентацию микросхемы? Насколько я себе их представляю, если основываться только на образе ножек, можно воткнуть ее наоборот. И будет засада. Если паттерн ножек несимметричен, чтобы точно задать положение, то тоже засада. На сколько процентов точек он будет отличаться, если перевернуть микросхему не так? Есть нефиговая вероятность, что мы не сможем отличить это от шума.

Я не хочу привязывать сетку, потому что нашел еще одно применение к этой штуке -- распознавать фигуры на фотке:
крестики там или квадратики.
G>Мне кажется, это работать не будет.
Был бы тебе очень благодарен за рабочий метод.
G>Кстати, вот что мне подумалось. Если ты собираешься ставить роботом микросхему в плату, как ты выберешь правильную ориентацию микросхемы? Насколько я себе их представляю, если основываться только на образе ножек, можно воткнуть ее наоборот. И будет засада. Если паттерн ножек несимметричен, чтобы точно задать положение, то тоже засада. На сколько процентов точек он будет отличаться, если перевернуть микросхему не так? Есть нефиговая вероятность, что мы не сможем отличить это от шума.
С этим вроде проблем нету. Фишка в том что в магазине, где берется компонент, они лежат в одном положении и оно нам известно. А фазовое смещение получается из-за того, что место для компонента в магазине больше компонента.
Так что угол будет варьироваться в пределах 20-25 градусов не больше. Можно просто приводить полученный угол в пределы от -45 до 45 градусов.

Здравствуйте, tinytjan, Вы писали:

T>Я не хочу привязывать сетку, потому что нашел еще одно применение к этой штуке -- распознавать фигуры на фотке:
T>крестики там или квадратики.
G>>Мне кажется, это работать не будет.
T>Был бы тебе очень благодарен за рабочий метод.
Знал-бы — рассказал. Здесь думать надо, то есть даже не думать, а просто расслабиться, и ждать озарения. Если повезет.

T>С этим вроде проблем нету. Фишка в том что в магазине, где берется компонент, они лежат в одном положении и оно нам известно. А фазовое смещение получается из-за того, что место для компонента в магазине больше компонента.
T>Так что угол будет варьироваться в пределах 20-25 градусов не больше. Можно просто приводить полученный угол в пределы от -45 до 45 градусов.

Та-ак, Семен Семеныч. Что же ты сразу не сказал? В изначальном условии этого не было. Это меняет дело — угол в 20-25 градусов означает, что угол имеет смысл определять перебором — это навскидку будет сравнимо с тем, чтобы определить направляющие сетки. Кстати, момент вообще принципиальный, и его надо прояснить.

Объясняю основную фишку прикладной математики и ее отличие от фундаментальной. Задача прикладной математики (как и инженерии) — разработать метод для решения конкретной проблемы, а не сформулировать глобальную теорему. Чем больше подробностей ты дашь о задаче, за которые можно зацепиться, тем луччше. Прикладной математик (и инженер), в отличии от фундаментального, цепляется за детали условия, чтобы схалявить (упростить проблему и решить ее), а "фундаментальный" математик от деталей наоборот — абстрагируется (и бьется над проблемой годами, прет его от этого). Разницу понимаешь?

Что еще об этой задаче ты утаил?

Здравствуйте, Gaperton, Вы писали:

G>Здравствуйте, tinytjan, Вы писали:

G>Знал-бы — рассказал. Здесь думать надо, то есть даже не думать, а просто расслабиться, и ждать озарения. Если повезет.

Неужели все так плохо?

G>Та-ак, Семен Семеныч.

Андрей меня зовут

G>Что же ты сразу не сказал? В изначальном условии этого не было. Это меняет дело — угол в 20-25 градусов означает, что угол имеет смысл определять перебором — это навскидку будет сравнимо с тем, чтобы определить направляющие сетки.

Просто не удовлетворяет меня количество О(n*n) еще с таким бешеным коэффициентом.

G>Кстати, момент вообще принципиальный, и его надо прояснить.

Проясняй, спрашивай, чем смогу помогу в разъяснении

G>Объясняю основную фишку прикладной математики и ее отличие от фундаментальной. Задача прикладной математики (как и инженерии) — разработать метод для решения конкретной проблемы, а не сформулировать глобальную теорему. Чем больше подробностей ты дашь о задаче, за которые можно зацепиться, тем луччше. Прикладной математик (и инженер), в отличии от фундаментального, цепляется за детали условия, чтобы схалявить (упростить проблему и решить ее), а "фундаментальный" математик от деталей наоборот — абстрагируется (и бьется над проблемой годами, прет его от этого). Разницу понимаешь?

Чего ж непонятного? Понятно

G>Что еще об этой задаче ты утаил?

Не знаю...Может, чего-нить еще... такого, мелкого

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Здравствуйте, tinytjan, Вы писали:

G>>Знал-бы — рассказал. Здесь думать надо, то есть даже не думать, а просто расслабиться, и ждать озарения. Если повезет.
T>Неужели все так плохо?
Ну, в общем, да, это не та задача, что легко решается за 15 минут . Если бы я работал с тобой, я бы потратил на нее существенно больше. И так же сидел, и ждал озарения.

G>>Что же ты сразу не сказал? В изначальном условии этого не было. Это меняет дело — угол в 20-25 градусов означает, что угол имеет смысл определять перебором — это навскидку будет сравнимо с тем, чтобы определить направляющие сетки.

T>Просто не удовлетворяет меня количество О(n*n) еще с таким бешеным коэффициентом.
А почему? Тебе не все равно? N у тебя порядка сотни. Смешно. Имеешь порядка 10000 сравнений. Фигня полная — процессор успеет, скорость ограничена механикой — какая тебе разница? Если разницы нет, лучше применять простой и тупой алгоритм — его проще понять и отладить.

G>>Что еще об этой задаче ты утаил?
T>Не знаю...Может, чего-нить еще... такого, мелкого
Дьявол прячется в деталях . Мелких

Здравствуйте, Gaperton, Вы писали:

T>>Неужели все так плохо?
G>Ну, в общем, да, это не та задача, что легко решается за 15 минут . Если бы я работал с тобой, я бы потратил на нее существенно больше. И так же сидел, и ждал озарения.
Ну что ж, если снизойдет на тебя озарение, пиши, кидай идеи .
А я в ожидании озарения с SIFT и RANSAC попробую поразбираться.

G>>>Что же ты сразу не сказал? В изначальном условии этого не было. Это меняет дело — угол в 20-25 градусов означает, что угол имеет смысл определять перебором — это навскидку будет сравнимо с тем, чтобы определить направляющие сетки.
T>>Просто не удовлетворяет меня количество О(n*n) еще с таким бешеным коэффициентом.
G>А почему? Тебе не все равно? N у тебя порядка сотни. Смешно. Имеешь порядка 10000 сравнений. Фигня полная — процессор успеет, скорость ограничена механикой — какая тебе разница? Если разницы нет, лучше применять простой и тупой алгоритм — его проще понять и отладить.

не порядка 10000, а порядка 1.800.000 для точности в полградуса, для точности в десятую градуса — 10.000.000
А это уже разница. А нам чем точнее тем лучше.
Где вы, блин, умные мысли?

Здравствуйте, tinytjan, Вы писали:

T>не порядка 10000, а порядка 1.800.000 для точности в полградуса, для точности в десятую градуса — 10.000.000
T>А это уже разница. А нам чем точнее тем лучше.
T>Где вы, блин, умные мысли?
Умные мысли:
1) Алгоритм двухфазный, на первой фазе мы выкидываем нафиг лишние точки, и точного определения угла поворота нам не нужно. На этой фазе мега-точность не нужна — достаточно того, чтобы шаг угла поворота был достаточно малым, чтобы точки на краях фигуры перемещались не более чем на половину шага сетки.
2) Шаг сетки определяется как минимум расстояния между точками образца, с которым ты сравниваешь.
3) Для определения количества итераций тебе надо с таким шагом разбить угол в 45 градусов.
4) После того, как ты выкинул лишние точки, и у тебя есть пара почти совмещенных образцов (фаза 1), ты добиваешься точного соответствия совместив их по трем крайним точкам (фаза 2) за O(1). Усе.
5) Для современных процов 10.000.000 сравнений — это тьфу. Должно делаться в реальном времени. Кстати, какое у тебя ограничение на время операции и какой проц?

Здравствуйте, Gaperton, Вы писали:

G>Умные мысли:
G>1) Алгоритм двухфазный, на первой фазе мы выкидываем нафиг лишние точки, и точного определения угла поворота нам не нужно. На этой фазе мега-точность не нужна — достаточно того, чтобы шаг угла поворота был достаточно малым, чтобы точки на краях фигуры перемещались не более чем на половину шага сетки.

Мне надо совместить картинки по углу как раз для того, чтобы откинуть левые точки. Замкнутый круг получается однако.
И интересно, как можно с такой (не?)точностью откинуть левые точки, если они могут располагаться где угодно?
Сначала предполагалось что сетка нужна для наложения картинок. Или я что-то не догоняю?

G>2) Шаг сетки определяется как минимум расстояния между точками образца, с которым ты сравниваешь.

Действительно умная мысль.Как я сам не придумал не знаю.


G>3) Для определения количества итераций тебе надо с таким шагом разбить угол в 45 градусов.

Почему 45?. 45 в одну сторону, 45 — в другую, 90 получается (почему 45 — а на всякие разные случаи)

G>5) Для современных процов 10.000.000 сравнений — это тьфу. Должно делаться в реальном времени. Кстати, какое у тебя ограничение на время операции и какой проц?

Да никакого. Чем быстрее тем луче. Никаких требований я не знаю. Я уже писал -- клепаем вслепую.

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Умные мысли:
G>>1) Алгоритм двухфазный, на первой фазе мы выкидываем нафиг лишние точки, и точного определения угла поворота нам не нужно. На этой фазе мега-точность не нужна — достаточно того, чтобы шаг угла поворота был достаточно малым, чтобы точки на краях фигуры перемещались не более чем на половину шага сетки.

T>Мне надо совместить картинки по углу как раз для того, чтобы откинуть левые точки. Замкнутый круг получается однако.
T>И интересно, как можно с такой (не?)точностью откинуть левые точки, если они могут располагаться где угодно?
T>Сначала предполагалось что сетка нужна для наложения картинок. Или я что-то не догоняю?
Здесь я пишу только о том, как можно точно посчитать необходимый шаг угла для перебора, чтобы точности хватило для отсева левых точек.

G>>2) Шаг сетки определяется как минимум расстояния между точками образца, с которым ты сравниваешь.
T>Действительно умная мысль.Как я сам не придумал не знаю.
Слушай, реально умная мысль, ты прав. Я ее недооценил. Давай-ка мы ее попользуем. Вот еще один алгоритм определения коэффициента масштабирования — альтернатива сравнению дисперсий вокруг центров, я думаю, более точный и адекватный:

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

G>>3) Для определения количества итераций тебе надо с таким шагом разбить угол в 45 градусов.
T>Почему 45?. 45 в одну сторону, 45 — в другую, 90 получается (почему 45 — а на всякие разные случаи)
Ок, пусть будет 90. Просто ты сначала говорил об угле разброса +-20..25 градусов.

G>>5) Для современных процов 10.000.000 сравнений — это тьфу. Должно делаться в реальном времени. Кстати, какое у тебя ограничение на время операции и какой проц?
T>Да никакого. Чем быстрее тем луче. Никаких требований я не знаю. Я уже писал -- клепаем вслепую.
Плохо. Выясни требования по скорости механики — можно взять данные с реальных сборочных линий. Померяй скорость работы нашего метода на компе, и вычисли требуемую поризводительность проца, чтобы уложиться в норматив. Если не получится, надо думать об оптимизациях.

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Gaperton, Вы писали:

G>>Умные мысли:
G>>1) Алгоритм двухфазный, на первой фазе мы выкидываем нафиг лишние точки, и точного определения угла поворота нам не нужно. На этой фазе мега-точность не нужна — достаточно того, чтобы шаг угла поворота был достаточно малым, чтобы точки на краях фигуры перемещались не более чем на половину шага сетки.

T>Мне надо совместить картинки по углу как раз для того, чтобы откинуть левые точки. Замкнутый круг получается однако.
T>И интересно, как можно с такой (не?)точностью откинуть левые точки, если они могут располагаться где угодно?
T>Сначала предполагалось что сетка нужна для наложения картинок. Или я что-то не догоняю?
!!!!! Вот еще такая мега-идея. Короче, начало торкать .

Множество углов, которое надо перебирать, считается совсем не так. Вот как надо.
1) Переходим в полярную систему координат с центром в центре масс.
2) Получаем для каждой системы точек график удаленности точки от центра в зависимости от угла. Очевидно, по оси, где отложен угол, у нас количество точек будет равно количеству точек системы.
3) Бьем точки систем на кластеры, в зависимости от их уделенности. Это можно сдалать посчитав статистические моменты.
4) Проводим процедуру поиска углов используя только точки из одинаковых кластеров, чем заметно режем сложность квадратичного алгоритма. Угол ищем перебором, причем вопрос выбора шага перебора не стоит вообще — просто двигаемся по графику от точки к точке в (пределах кластера) вдоль оси "угол".

Здравствуйте, Gaperton, Вы писали:

G>!!!!! Вот еще такая мега-идея. Короче, начало торкать .
По-хорошему завидую, у меня после семи(!)дневной рабочей недели похоже испарились все остатки мозгов.

G>Множество углов, которое надо перебирать, считается совсем не так. Вот как надо.
G>1) Переходим в полярную систему координат с центром в центре масс.

Хокей

G>2) Получаем для каждой системы точек график удаленности точки от центра в зависимости от угла. Очевидно, по оси, где отложен угол, у нас количество точек будет равно количеству точек системы.
G>3) Бьем точки систем на кластеры, в зависимости от их уделенности. Это можно сдалать посчитав статистические моменты.
G>4) Проводим процедуру поиска углов используя только точки из одинаковых кластеров, чем заметно режем сложность квадратичного алгоритма. Угол ищем перебором, причем вопрос выбора шага перебора не стоит вообще — просто двигаемся по графику от точки к точке в (пределах кластера) вдоль оси "угол".

Ниче не понял, может, уже нечем просто?
Если можно поподробней

Здравствуйте, Gaperton, Вы писали:

T>>Мне надо совместить картинки по углу как раз для того, чтобы откинуть левые точки. Замкнутый круг получается однако.
T>>И интересно, как можно с такой (не?)точностью откинуть левые точки, если они могут располагаться где угодно?
T>>Сначала предполагалось что сетка нужна для наложения картинок. Или я что-то не догоняю?
G>Здесь я пишу только о том, как можно точно посчитать необходимый шаг угла для перебора, чтобы точности хватило для отсева левых точек.

Так как этот угол считать все таки? Я наверное окончательно запутался.

G>>>2) Шаг сетки определяется как минимум расстояния между точками образца, с которым ты сравниваешь.
T>>Действительно умная мысль.Как я сам не придумал не знаю.
G>Слушай, реально умная мысль, ты прав. Я ее недооценил. Давай-ка мы ее попользуем. Вот еще один алгоритм определения коэффициента масштабирования — альтернатива сравнению дисперсий вокруг центров, я думаю, более точный и адекватный:

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

Опять же : совместить вначале надо. Если я неправ поправь.

G>Насчет непереборного определения угла поворота. Деталь всегда вписывается в прямоугольный контур? На этом можно попробовать сыграть.

Любая деталь, даже если она сама не прямоугольная, вписывается в прямоугольник. В БД у нас только прямоугольые детали. Неплохое облегчение.

G>>>3) Для определения количества итераций тебе надо с таким шагом разбить угол в 45 градусов.
T>>Почему 45?. 45 в одну сторону, 45 — в другую, 90 получается (почему 45 — а на всякие разные случаи)
G>Ок, пусть будет 90. Просто ты сначала говорил об угле разброса +-20..25 градусов.

Я тут недавно ПДФину почитал -- там вообще угол от -180 до 180 ...

G>>>5) Для современных процов 10.000.000 сравнений — это тьфу. Должно делаться в реальном времени. Кстати, какое у тебя ограничение на время операции и какой проц?
T>>Да никакого. Чем быстрее тем луче. Никаких требований я не знаю. Я уже писал -- клепаем вслепую.
G>Плохо. Выясни требования по скорости механики — можно взять данные с реальных сборочных линий. Померяй скорость работы нашего метода на компе, и вычисли требуемую поризводительность проца, чтобы уложиться в норматив. Если не получится, надо думать об оптимизациях.

На современных сборочных системах стоят 4е пни.
Весь процесс центровки, построения контура и всякме другие процессы (исходя из того что современные системы могут ставить до 60000 элементов в час) дожны занимать по времени не больше 0.1 сек. Вот такой вот примерный критерий.

Кстати, если есть какой нить материал по SIFT и RANSAC, написанный языком для непродвинутых, кинь ссылочки плз...
Потому что оказалось в математике я почти полный профан