Здравствуйте, 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, написанный языком для непродвинутых, кинь ссылочки плз...
Потому что оказалось в математике я почти полный профан