Народ! Помогите!!!
Задача такая:
Дан набор точек(координаты х и у).Этот набор является эталонным. Назовем его (Е)
Есть еще один набор точек(координаты х и у, назовем его (Х)), повернутый, смещенный и смасштабированный (Е). Причем незначительная часть точек и набора (Е) может отсутствовать и могут присутствовать 'левые' точки, которых не было в исходном наборе.
Необходимо найти такое преобразование(Е) (смещение, масштабирование и поворот) при котором точки (Е) будут преобразовываться в точки (Х) оптимальным образом.
набор (Е)
набор(Х)
Здравствуйте, tinytjan, Вы писали:
T>Народ! Помогите!!! T>Задача такая: T>Дан набор точек(координаты х и у).Этот набор является эталонным. Назовем его (Е) T>Есть еще один набор точек(координаты х и у, назовем его (Х)), повернутый, смещенный и смасштабированный (Е). Причем незначительная часть точек и набора (Е) может отсутствовать и могут присутствовать 'левые' точки, которых не было в исходном наборе. T>Необходимо найти такое преобразование(Е) (смещение, масштабирование и поворот) при котором точки (Е) будут преобразовываться в точки (Х) оптимальным образом. T>набор (Е) T> T>набор(Х) T>
Гы! Уж не номерок-ли автомобильный ты выравнивать собрался? Что-то не пойму, ты же только что писал, что с этим твоя нейросеть справляется на раз-два . А тут вдруг — "помогите"?
Здравствуйте, Gaperton,
Издеваться всякий может.Не до приколов мне сейчас . Мне помощь нужна ,и срочно. Если интересно, то не номера автомобильные мне ворочать не надо. А надо найти контур компонента для печатных плат и положение его ножек на зашумленной картинке.Это надо для того, чтобы скорректировать головку, которая компонент на плату ставит.
А набор (Е) это набор центров пятен, которые 'типа' являются ножками компонента.(т.е. 'типа' ножка на самом деле может быть шумом).
Нейронка здесь не поможет -- просто всунуть некуда.
Здравствуйте, 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 сравнения для определения угла.
Проблема остается. Мы можем взять левые точки.
Здравствуйте, tinytjan, Вы писали:
T>Здравствуйте, Gaperton, Вы писали:
G>>Хе-хе!
G>>!!!!!!
G>>А мы ее уберем до нуля. После совершения всех описанных мной преобразований ты легко выделишь "левые" точки как наиболее удаленные от точек образца, выкинешь их, и повторишь всю процедуру. После чего получишь 100% совпадение. T>Чтобы все было так легко Левые точки необязательно будут самые удаленные.
Ты не понял. Все на самом деле так легко. T>Если бы от них можно было избавиться все было бы тип-топ.Построил внешний прямоугольник и твори че хошь.
Какой внешний прямоугольник, боже упаси?! Метрику я ввел, помнишь? Чтобы ее посчитать, ты каждой точке образца ставишь в соответствие ближайшую к ней точку тестового набора, и считаешь сумму расстояний, так?
Так вот, "левыми" будут те точки тестового набора, которые не сопоставлены ни одной точке образца. Так как соответствие точек получается 1 в 1, то все наиболее удаленные точки уйдут. Понятно?
G>>Есть такой метод. Надо попытаться определить направляющие оси на тестовом наборе точек (пользуясь тем, что точки выравнены по сетке), после чего тебе понадобится всего 4 сравнения для определения угла. T>Проблема остается. Мы можем взять левые точки.
Левые точки выравнены по сетке, или нет? И в конце концов, сколько процентов левых точек от общего числа?
Здравствуйте, Gaperton, Вы писали:
G>Ты не понял. Все на самом деле так легко. T>>Если бы от них можно было избавиться все было бы тип-топ.Построил внешний прямоугольник и твори че хошь. G>Какой внешний прямоугольник, боже упаси?! Метрику я ввел, помнишь? Чтобы ее посчитать, ты каждой точке образца ставишь в соответствие ближайшую к ней точку тестового набора, и считаешь сумму расстояний, так?
G>Так вот, "левыми" будут те точки тестового набора, которые не сопоставлены ни одной точке образца. Так как соответствие точек получается 1 в 1, то все наиболее удаленные точки уйдут. Понятно?
Да в приципе это вариант.
Некоторые Левые точки может и останутся, но в конце концов процедуру можно повторить еще раз или два.
Спасибо
G>>>Есть такой метод. Надо попытаться определить направляющие оси на тестовом наборе точек (пользуясь тем, что точки выравнены по сетке), после чего тебе понадобится всего 4 сравнения для определения угла. T>>Проблема остается. Мы можем взять левые точки. G>Левые точки выравнены по сетке, или нет? И в конце концов, сколько процентов левых точек от общего числа?
Левые точки расположены КАК УГОДНО и соответственно могут попасть в сетку.
А процент может варьироваться в зависимости от количества эталонных точек.
Если точек больше хотя бы 50 то процент можно брать не больше 10-15%
Если больше 200-300 , то 3-5%. И так далее.
Так что на нормальном количестве точек покатит думаю без проблем
Что-то не пойму, ты же только что писал, что с этим твоя нейросеть справляется на раз-два 
Левые точки необязательно будут самые удаленные.
