Сразу скажу, что оговаривается не трассировка лучей и не графика.
Здравствуйте, мне давно советовали писать на Хабр, но я не хотел. Почему...? Ну, наверное, потому что встречалось всё в большей мере «в пики», ну и во вторых потому, что скорее всего я думал что публикация должна иметь какой-то вес. То есть масштаб тулзы меня не устраивал. Да и времени на споры у меня было мало, как и сейчас у меня на них нет его совсем.
Почему публикаций по промежуточному результату?
Потому что мне настойчиво и чуть-ли не в требовательной форме навязывали применение алгоритма Берзенхема, но я читал и его, и другие - не нашёл ничего подходящего для поставленной задачи. И хоть карты могут использоваться одни и те-же, но мне хотелось чтобы алгоритм был быстрый и надёжный, потому что карты предназначены для алгоритма, который планирую использовать для замены свёрточных нейросетей, и мало-ли когда и как нужна будет та или иная карта с другими параметрами. Собственно сам генератор карт за малым не доделан, так как переменные для того что расчитать пути под углом от 45-90 градусов нужно будет применить указатели на переменные и поменять координату x с координатой y местами, а от 90-180 градусов сделать нечто вроде отзеркаливания карт, но это уже не суть, так как самое сложное что оказалось - формулы.
Немного предыстории и теории
Сама идея того, как сделать альтернативу свёрточным нейросетям мне пришла в голову чуть больше года назад, хотя закодить модуль AI желание испытывал давно, читал книги, но как-то не заходили мне западные идеи и алгоритмы, немного не так всё это описывали в эпоху Союза, когда я читал книги и интересовался всем подряд, и от западной литературы я больше впадал в уныние, чем видел перспективы, там как-то любят сравнить человека то с муравьём, то с мухой, то с программой, потом ещё сами алгоритмы вгоняли в депрессию - ни одного лайф хака и вся идея AI построена на банальщине. Всё это в конце концов сводило все мои желания к одному - сделать всё не так. А как общепринято - AI начинается с машинного зрения.
И у меня получилось. Идея заключатеся в том, что некий алгоритм вместо расчёта свёртков, расслоит результат обработки на количество слоёв, где каждый слой будет соответствовать углу, пробегая по изображению линиями под этим углом, подсчитывает окрашенные пикселы (сначала разумеется MNIST) следующие подряд до того, пока этот непрерывный ряд не обрвётся, как только он оборвётся алгоритм кадому пикселу ряда припишет вес всей линии к которой он принадлежит. И так слой за слоем. И тогда можно будет отследить узлы - это пикселы которые совпадают на слоях разных углов и у которых имеется достаточный вес, чтобы отличить их от "шума", и следовательно можно по весу и расстоянию между слоями отследить дуги или углы относительно прямых линий.
Задача генератора карт трассировок
сводится к тому, что он должен составить карту попиксельного следования для алгоритма подсчёта весов. Для каждой из четырёх групп углов 0-45,45-90,90-135,135-180 будет своя точка входа в карту, это необходимо потому что генератор пока работает так, и вряд-ли он будет работать иначе, так как это если не максимально быстро, то почти максимально быстро. Попадая в начало карты, в каждой её ячейке (она может быть разбита на несколько массивов, но я беру ввиду то, что она таблица - так быстрее описать её предназначение), алгоритм суммирующий веса линий и сохранящий их по их обрыву, должен будет читать состояние пиксела изображения, соответствующего координатам на карте и увеличивать вес линии если пиксел окрашен, и записать в каждый пиксел слоя (от угла) значение суммарного веса когда череда окрашенных пикселов в линии пути прервётся, обнулить по обрыву значение веса, а для следования он должен читать в кадой ячейке карты координаты следующего пиксела и булевое поле, которое будет содержать единицу если линия на изображении закончена, так как окончание линии ещё зависит от позиции на изображении, а не только от окончания череды окрашенных пикселов.
То есть в каждой ячейке карты генератор сохраняет информацию о том куда следовать её читателю и информирует продолжается линия на изображении или нет, ведь алгоритм читающий карту тоже не человек, и он понятия не имеет что существуют вооще даже какие-то линии, как и о том, что имеет место быть вообще факт существования его самого.
Почему алгоритм движка генератора карт быстр...
потому что он вообще заполняет карту автоматом, почти как заливка изображения, и невзирая на то, что информацию он сохраняет достаточно объёмную для всей карты в целом - для неё он считает только правый столбец (в данном случае) и последнюю строку ячеек хранения координат и состояния линии от размера изображения. Изначально я думал что это будет генерация по линиям, но потом я решил что гораздо быстрее генератор будет работать если генерировать построчно даже косые линии, а на местах скоса забивать значения алгоитмом автоматически (ведь скос он всегда один и тот-же). Поэтому я начал ассоциировать свой алгоритм движка генератора карт с неким трактором типа комбайна (хотя если честно мысль о подобии трактору была всегда, но после её воплощения в алгоритме она засела в голове прочно).
Алгоритм читающий эти карты «умом» так же не блеснёт, его задача и предназначение - быстрое выполнение поставленной задачи, что эквивалентно эффективному использованию вычислительных ресурсов.
Минусы и плюсы...и можно-ли назвать это минусами...
Из минусов то, что он не повторяет алгоритм Брезенхема - немного уступает в точности, так как у того через н-ное количество итераций будет учтёно накопительное изменение размера шага чередования, а у моего нет, но это собственно и плюс - представьте себе что на дороге строго и идеально всегда через одно расстояние встречается камень одного и того-же размера размера . Так как мы пишем код - ничего страшного, пусть шаг будет таким - всегда до камня, но представьте себе что этот камень вдруг (случай применения для этой задачи алгоритма Брезенхема) начнёт смещаться да ещё и изменять свой размер - прийдётся менять размер шага на ходу, да ещё и высоту подъёма ноги, чтобы перешагнуть. А это уже серьёзно ударит по быстродействию. Но даже если и не совсем так - то пиксел вдург туда-сюда для нейросети будет как шум исходящий от самой карты даже, не говоря уже о том, что обрабатывается изображение в конечном счёте.
Поэтому такую неточность сложно назвать недостатком, скорее она будет иметь положительный эффект.
Проект генератора карт трассировок пока в разработке, но движок генератора можно потестить
Лежит тут, там немного грязи есть в коде, и кто захочет поюзать программку (для линукс пока только) мануал такой: в первое поле ввода вводится угол 0-45 градусов, второе и третье поле ввода строки - размеры карты по оси X и Y (высота карты не меньше трёх пикселов!!! это последствия применения математической логики - я в двух строках вместо привычного кода применяю математические формулы и модуль Math - использую математику как костыль к языку программирования, в данном случае FPC Lazarus). Первая кнопка запускает генератор, а вторая алгоритм проверяющий карту, который следует маршруту по ней, и в каждой пройденной ячеке оставляет точку или X, если линия обрывается согласно размеру изображения. Почему так долго делал движок - потому что всё после работы, и отнимает времени она столько что на свои дела в сутки очень мало - час, два, исключение выходной день. Но практика показала, что и так можно существовать и решать какие-то свои задачи.
Что дальше
Далее после я переведу на с++, распараллелю вычисления, а пока в одном потоке генератор, если закомментировать строки отвечающие за запись расчитанного в таблицу, считает трассировку карты для 100 000 000 ячеек за 100 миллисекунд (0,1 секунды) на Ryzen 7 (нетбук). Но возможно что перед переходом на c++ я ещё и MNIST обработаю своим методом, дописав некоторый аналог обычных нейросетей. Но это уже не суть.
Конечно есть ещё проекты с лайфхаками, но этот у меня наиболее приоритетный, ну как минимум один из них, второй - безроторный электро генератор на базе ... части двигателя Стирлинга. Впрочем его эффективность под вопросом, но думаю что в ближайшее, относительно моего свободного времени, время - я эти вопросы проверю и разрешу в пользу его профитности или наоборот.
Всем спасибо за внимание, не судите строго - времени на большее и лучшее у меня просто нет.
Код не привожу тут, и он только на гитхабе и пока только на FPC Lazarus, ну потому что у многих мои шедевры вызывают приступы идеализма и им кажется что я оскверняю их веру, я много встречал таких людей. Не подумайте что агитирую кого-то не читать западных школ программирования, просто я пишу код так вот, как считаю нужным сам.