Простая геометрия. Объекты на прямой.

Смешно описал :)

Дашь поглядеть?

Рано батенька рано, во первых идея слишком простая что-бы её палить, во вторых и правда не готово. Как в стим скину билд я тебе ключик дам так и быть =) Внесу пометку к твоему нику ::) Хотя если за месяц после выпуска будет 3 продажи то под MIT выложу на гитхаб помойку ибо мусору там и место :D=)

Задача из серии анализа данных и поиска линейной регрессии координат объектов.

Ну за проприетарщину меня конечно говном закидают

На ЛОРе (по крайней мере, вменяемые люди) обычно наезжают не за саму проприетарщину, а за то, что человек, выкладывающий проприетарщину, ещё и быковать начинает. Вот, например, такое (особенно эффектно смотрится в сочетании с последним абзацем ОП).

https://ru.m.wikipedia.org/wiki/RANSAC

HIS ай яй яй по попе! Ринат хороший! А тролит он с юмором обычно. :D

На ЛОРе (по крайней мере, вменяемые люди) обычно наезжают не за саму проприетарщину

Всё равно я готов заранее по умолчанию принять тонну помоев, гнилых помидоров и тухлых яиц тачанку =) Всё что мне останется это просто помалкивать. Ибо ЛОР какой бы он ни был всё же тут про открытость в том или ином виде. И ладно бы я хрень какую крутую делал про которую можно подумать,«Да чувак пыхтел и сделал красоту! Можно и не ругать за то что пытается окупить свои старания» то в моём случае будет «Это говно да ещё за деньги, окстись милок! ТуксКар по сравнении с твоей поделкой это как тетрис и Крузис третий, так вот ты тетрис!» В не зависимости от того что для меня моя поделка тоже старания гыыы ))))) Так что можно надеяться на похвалу конечно, но обольют меня и всё. Ну и ладно, кому то может зайдёт на разок =) Первая игра всётки (публичная первая) будет.

Смешно

Перебором? Не? Берёшь 2 «предмета» и «смотришь» сколько «предметов» на этой же линии.

Ну и ладно, кому то может зайдёт на разок =) Первая игра всётки (публичная первая) будет.

Ждём-с.

какие из элементов находится на прямой.

Ласло М. Вычислительная геометрия и компьютерная графика на C++ ©:
4.4.4. расстояние от точки до прямой линии.
5.4; 5.5 Принадлежность точки (доверительной области).

Препарата и Шаймос, «Вычислительная геометрия: 2.2. Задачи локализации точки» ©.

так чтобы была выявлена «прямая» относительно большинства находящихся на этой «прямой» элементов.

Линейная регрессия ©.

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

Я не ТС, но скажу спасибо!

точные алгоритмы

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

например 6 из 10

10 - это недорого

быстрые

NP-полные задачи все «одинаково» быстрые.

МНК со дополнительным штрафом за отклонение от прямой, если же лежит на прямой размер штрафа увеличивается(дальше можно сопоставляя с результатом МНК немного улучшать). Или можно построить выпуклую оболочку, не включая точки лежащие внутри выпуклой оболочки и перебрав рёбра выбрать ребро наиболее близкое к центру тяжести.

ай яй яй по попе! Ринат хороший! А тролит он с юмором обычно. :D

Да ладно. Хоббит просто вырвал из контекста мою неприязнь к некоторым персонажам на здешнем форуме. Думаю что он не знает всю подоплёку этого всего действа начавшуюся неколько лет назад. Но пусть бегает за мной и выискивает как я выражаю свою неприязнь к всего трём троллям, и то, только когда они сами приползают меня троллить. Может добъётся того, что я и его для себя помечу как не адеквата. Его выбор.

педметы

Это как педобир?

Починил

Но пусть бегает за мной и выискивает

Шиза? Мания преследования?

Есть ли быстрые и точные алгоритмы решающие подобные задачи?

А чем брутфорс не устраивает? Т.е. тупо построить все прямые и выбрать одну с минимальным расстоянием до «лишних» точек?

PS: можно какое-нибудь отсечение прикрутить, чтобы заведомо негодные варианты не перебирать.

Примерно так и собираюсь сделать с некоторыми эвристиками.

В принципе точек максимум 12 нужно будет обрабатывать.

Метод предложенный quickquest не ложится как нужно для этой задачи. Я его ещё в начале писания проги забраковал.

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

Насколько я понял, тебе нужно то, что в Calc называется «линия тренда». Вот пример расчёта: https://bookaa.ru/operatsionnyy-menedzhment/postroenie-linejnogo-trenda.html

тупо построить все прямые

Все не нужны. Они будут выбывать но мере нахождения «предметов» на какой либо прямой. Плюс всегда можно ограничиться неким кол-вом «предметов», например, для 100 «предметов» target > 25.

Можно ещё регрессию считать и от неё перебирать, т.е. брать сначала ближайшие к ней точки. Есть большой шанс, что сразу нужная прямая так найдётся

Они будут выбывать но мере нахождения «предметов» на какой либо прямой

Так я и говорю, что можно какие-то отсечения ветвей перебора прикрутить, в зависимости от конкретных требований.

тупо построить все прямые и выбрать одну с минимальным расстоянием до «лишних» точек?

Это называется «наименее абсолютные отклонения» ©.

можно какое-нибудь отсечение прикрутить, чтобы заведомо негодные варианты не перебирать.

Методы ©.

надёжность считывания всё же получить хочеться особенно на агрессивных фонах с узорами на купюрах.

Глянь «квантиль регрессию» ©, она более устойчива к выбросам.

Numerical Recipes in C, The Art of Scientific Computing Second Edition, 15.7 Robust Estimation

Решал подобную задачу в дипломном проекте именно преобразованием Хафа.
Оно переводит прямые в точки (а точки в прямые).
Вот допустим, есть на изображении N точек. Через них можно провести M = N * (N-1) / 2 прямых. После преобразования Хафа получится M точек. Рядом расположенные точки соответствуют «похожим» прямым. Так что остаётся определить, где эти M точек расположены наиболее кучно.

где эти M точек расположены наиболее кучно.

В топку. Взвешенное среднее. Веса для него из обычного среднего.

Я уже даже сейчас начал предполагать как бы здешние «умельцы» по «Tesseract» и орущие про нейросистемы показали бы что нибудь мне в области распознваняи хотябы серийников банкнот.

какие из элементов находится на прямой.

Элементы это точки или все таки фигуры?

Я упростил задачу и предложил найти некоторые точки фигур.

Ты таки не ответил на мой вопрос. Я правильно понял что элементы это точки?

И я правильно понял, что тебе нужна прямая проходящая через наибольшее число точек и среди одинаковых прямых та, до которой суммарное расстояние до точек наименьшее?

Да.

Самое ужастное то, что я почти все решения уже нашёл. Да. Есть нюансы где, не могу найти быстрые решения, чтобы было всё зашибись с пол оборота. На мощных вычислениях я знаю как сделать. Но здесь и те что орут, что они всёзнающию про нейротехнологии (про которые и лыка не вяжут) про все вариации распознавания обсераются. У меня уже есть вполне готовая программа, которая работает на упрощённых версиях фонов в риалтайме на мобильниках.

Так в чем проблема? Через каждые 2 точки проходит минимум 1 прямая. Гугли уравнение прямой по двум точкам, вот тебе емнип n!/(2(n-2)!) уравнений. Подставляешь в каждое оставшиеся точки и находишь на какой прямой больше точек. Если таких прямых несколько то гугли расстояние от точки до прямой и считай сумму этих расстояний.

Аа, так тебе быстро нужно, что ж сразу не написал.

Почему не PCA (метод главных компонент)?

про нейросистемы показали бы что нибудь мне

Intel® Neural Compute Stick 2 + OpenVINO™ toolkit — > Text Detection C++ Demo

Созерцай до просветления :)

Вот, сделал для примера, на матлабе.
Возьмём 7 точек. Их координаты:

src_xx = [10 20 20 20 20 20 30] + rand(1, 7)
src_xx = 
  10.4514  20.0439  20.0272  20.3127  20.0129  20.3840  30.6831
src_yy = [18 30 25 20 15 10 17] + rand(1, 7)
src_yy =
  18.8744  30.0150  25.7680  20.9708  15.9901  10.7889  17.4387
plot(src_xx, src_yy, 'b*')

https://yadi.sk/i/qrnd32rZ8t_lgQ
Как видно, 5 из 7 точек лежат примерно на одной прямой.
Смотрим результат после преобразования Хафа:

imagesc(enum_all_lines(src_xx, src_yy))

https://yadi.sk/i/0gJY535woLP58g
На этом изображении каждая яркая точка соответствует одной из прямых исходного изображения.
Наиболее яркая точка, как видно - это точка с координатами x=1, y=47, что, после обратного преобразования Хафа, будет соответствовать прямой, проходящей параллельно оси ординат через точку x=20.
Код использованных функций: https://pastebin.com/9cURBECu https://pastebin.com/3VmU3qrL

Не совсем понял, что мне там созерцать?

Хотябы в жипегах какие-то примеры.

Я написал в топике что у меня есть решение. Оно чуть более круче чем раза в 3 потому что не делает полный перебор каждые 2 точки. Патамучта это глупо.

Чтобы не быть голословным я объясню суть моего алгоритма.

Смысл поиска закономерности расположения элементов начинается с количества 4. От этого и отталкивается мой алгоритм поиска.

Но пусть бегает за мной и выискивает

Обожемой, да всё гораздо проще. Бегать особо не понадобилось.

Я заглянул в эту тему. Вижу, как ТС безапелляционно в духе того самого героя Хармса заявляет «Тессеракт — говнище». Мне в таких случаях сразу становится интересно, а сам-то ТС что сделал для опенсорса? (Да-да, «спердобейся», как в таких случаях верещат тролли с лурки. Вот поэтому и верещат, что тролли.) Ну или хотя бы может ли предложить аналог получше?

И тут я вспоминаю. Пятнашки. Проприетарные. Причём сначала автор в ОП почесал своё ЧСВ, а потом сагрился (заочно!) на человека, который, в отличие от него, написал несколько полезных опенсорсных программ.

как я выражаю свою неприязнь к всего трём троллям, и то, только когда они сами приползают меня троллить.

Пфф, я вижу, что в той теме сначала Harald призвал Рината. После этого, ещё до появления человека в теме, из тебя посыпалось сначала «убогий троль», потом «чуваг просто обкакается», потом «упорыш». И только после этого в теме появился сам i-rinat с нейтральной репликой. Как-то это не очень вяжется с твоей версией, не находишь? Это я, что ли, из контекста вырвал? (Я в поисках этого контекста даже удалённые посмотрел, ничего, принципиально меняющего картину, не увидел.) И кто после этого тут тролль?

Думаю что он не знает всю подоплёку этого всего действа начавшуюся неколько лет назад.

Ну попробуй меня переубедить. Есть пруфы на то, что было «несколько лет назад»?

P.S. Как я уже писал, я не считаю проприетарные программы абсолютным злом, особенно игрушки. Я прекрасно понимаю, что людям надо зарабатывать на хлеб и жильё. Но когда автор проприетарной программы начинает вот такое себе позволять в отношении опенсорса и тех, кто его делает — надо таких время от времени слегонца возвращать к реальности.

P.P.S. И да, я ни в коей мере не являюсь экспертом по распознаванию. Но раз дело дошло до заявлений уровня «Тессеракт — говнище», не сопровождённых аргументами, жду хотя бы примера: какой опенсорсный продукт такого же класса НЕ является говнищем?

Не совсем понял, что мне там созерцать?

Примеры применения «Intel® Neural Compute Stick 2» для задач сегментации, интерполяции, распознавания, …

Хотябы в жипегах какие-то примеры
распознаванию купюр по серийным номерам

Example

А я понял. Просто ещё не выложил в общий доступ свою прогу.

Да. У меня прога, а не просто картинки. Скоро будет в маркете.

А у тебя есть что показать?

не всех можно вернуть к реальности )

А у тебя есть что показать?

Есть, пиши запрос «т. майору», но я больше «железячник», чем «погромист», а некоторые мои изделия самоликвидируются при попытках взять их в руки и поизучать :)

Да-да, «спердобейся», как в таких случаях верещат тролли с лурки. Вот поэтому и верещат, что тролли.

Да нет, это просто реакция на троллей с «а чего добился ты?». По мнению которых, называть говно говном может только ассенизатор с 10 годами стажа.

Вспоминается шутка, что прошивка железок в МБР никогда не нарушает GPL, поскольку изделие доставляется пользователю в неработоспособном виде.