Сотрудник ФАС, задремавший над спамом, в представлении художника эпохи романтизма

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

Случай 1: Компания «Яндекс» прислала на электронную почту рекламу своей «Метрики», имитирующую ответ службы поддержки

Спустя несколько месяцев после реального запроса в поддержку «Яндекса» и получения на него исчерпываюшего ответа, компания решила послать вдогонку ни разу не рекламу, а просто дополнительно проинформировать на тему, никак не связанную с запросом. Ом-ном-ном, – прочавкал Московский УФАС, – какой вкусный удон, это не спам!

В соответствии с документами и сведениями, представленными ООО «Яндекс» по запросу Московского УФАС России, установлено, что поступившее на Вашу электронную почту письмо было направлено в ответ на ранее поданное Вами обращение в службу поддержки сервиса Яндекс с вопросом, касающимся индексирования сайта и верификационного кода Вебмастера. В связи с поступившим обращением ООО «Яндекс» дополнительно Вас проинформировало по соответствующей категории вопросов о возможности дополнительной настройки индексирования, о чем также свидетельствует указанный в теме письма заголовок «[Ticket#20093010511401740]».

Случай 2: Правительство Москвы прислало на электронную почту рекламу «цифрового туристического сервиса RUSSPASS», на котором в свою очередь, рекламировались в т.ч. платные услуги третьих лиц по проведению досуга (не в дурном смысле)

Московское УФАС России приходит к выводу, что заявителю на адрес электронной почты пришло информационное сообщение относительно возможности использования туристического сервиса, реализуемого в соответствии с нормативным актом органа исполнительной власти города Москвы, и который непосредственно связан с деятельностью сайта Мэра Москвы, в связи с чем и было направлено с электронной почты с доменным именем mos.ru.
<…>
Об обратном не свидетельствует и довод заявителя относительно платности предлагаемых услуг, поскольку в указанном случае данное обстоятельство касается не самой платформы RUSSPASS, которая функционирует и доступна пользователю на безвозмездной основе, а именно услуги иных лиц, которые пользователь может получить, выбрав тот или иной маршрут путешествия.

Перевожу на понятный русский:
— Почему это информационное сообщение, а не реклама?
— Потому, что это реклама – кого надо реклама гладиолус.
— Вот даже платные услуги на том портале…
— Но в спаме письме рекламируются не они, а сам портал, и даже не рекламируется – а информируется, что он есть.
— Позвольте, но это и называется «реклама»…
— Кого надо реклама!

Случай 3: Правительство Москвы прислало на электронную почту рекламу «Запустите рекламную кампанию с Рекламной подпиской Яндекс.Бизнеса на 2 месяца за 10% от ее стоимости»

Вы уже догадались, что в таком комбо – вдвое больше неуиноуности?

Московское УФАС России приходит к выводу, что заявителю на адрес электронной почты пришло информационное сообщение о возможности воспользоваться программой по предоставлению субсидии из бюджета города Москвы, реализуемой в соответствии с нормативными актами органа исполнительной власти города Москвы, и которая непосредственно связана с деятельностью сайта Мэра Москвы, в связи с чем и было направлено с электронной почты с доменным именем develop.mos.ru.

Таким образом поступившее заявителю e-mail-сообщение не является рекламным, в поступившем Вам e-mail-сообщении отсутствует информация об объекте рекламирования. Целью данного сообщения не является привлечение внимания потребителей к объекту рекламирования, формирование или поддержание интереса к нему и его продвижение на рынке. Данное e-mail-сообщение направлено в целях информирования пользователя сайта mos.ru, которым является заявитель, о возможности участия в программе Правительства Москвы.

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

Увы, остался непроясненным один момент: партнерам Правительства Москвы можно спамить только совместно с ним, или один раз запартнерился – и пожизненная лицензия на убийство индульгенция на спам в кармане?

Кстати, обратите внимание на адрес, куда Правительство Москвы со своим партнером «Яндексом» рассылали спам – contactifap.ru Это общий корпоративный адрес, который никогда и никем не использовался для регистрации на сайте mos.ru, но… вы же понимаете: джентльмены верят друг другу на слово, сказано послали пользователю – значит пользователю.

Случай 4 (не совсем спам, но интересно): некто (предположительно, админ) разместил на сайте Российской библиотечной ассоциации рекламный скрипт, который демонстрировал в т.ч. рекламу интернет-казино. Письмо в РБА было проигнорировано, и тогда я передал им привет через ФАС…

На запрос управления от Российской библиотечной ассоциации поступили объяснения (вх. № 38729-ЭП/21 от 09.12.2021) по существу рассматриваемого вопроса. <…> Из-за установленного на сайте РБА устаревшего программного оборудования, и как следствие, из-за его уязвимости для сторонних действий, был произведён несанкционированный доступ с целью размещения на сайте РБА сторонних ссылок, включая ссылку на онлайн-казино. <…> Статья 13 Федерального закона от 12 августа 1995 года № 144-ФЗ «Об оперативно-розыскной деятельности» содержит перечень органов, которые имеют право на территории России осуществлять оперативно-розыскную деятельность. ФАС России и его территориальные органы не поименованы в указанном перечне. С учётом изложенного, управление в рамках предоставленных ему на основании Федерального закона от 13 марта 2006 № 38-ФЗ «О рекламе» полномочий не может установить лиц, допустивших размещение на сайте www.rba.ru ненадлежащей рекламы.

Родненькие, что ж они сразу-то не сказали: у нас лапки, джентльмены верят друг другу на слово, все российские спамеры пьют за здравие ФАСа и разучивают фразу I didn’t do it! «это не я!» Не стыдно же было подписывать такой бред врио главы питерского УФАС Никитиной…

Случай 5: некто с российским IP, с существующим российским адресом электропочты разместил на российском форуме рекламу криптообменника с доменом в ссTLD .RU

Казалось бы, что может пойти не так при привлечении спамера? (Спойлер: у ФАСа лапки все!)

Материал созданный творческим трудом и содержащий в себе какую-либо информацию аналитического, обзорного характера, статистические, количественные и качественные показатели, имеющий в качестве своей цели не привлечение внимания потенциального потребителя к какому-либо товару или группу товаров, а донесение сведений до широкого круга читателей, справочный материал и т. п. не признается рекламой в контексте Закона о рекламе.
<…>
На сайте-форуме пользователи в сообщениях сообщают личные впечатления, опыт использования товара, субъективные выводы и взгляды лица, опубликовавшего конкретную запись, относительно свойств такого товара, в том числе его достоинств и отрицательных характеристик.

Обратного из материалов заявления не следует. Более того, в заявлении представлены скриншоты сайта-форума, из которого следует, что размещенная информация является сообщением конкретного пользователя — участника форума, какие-либо отметки о том, что данная информация является рекламой также отсутствуют.

Там дальше еще шла ссылка на ст.29 Конституции, но мне кажется, уровень бреда уже и так зашкаливает. Почему не спам? Потому, что гладиолус не помечен как реклама! Держите еще одну картинку с того же форума – это тоже, по мнению ФАС, не реклама, а творческий труд, аналитика, мнение пользователя, нет пометки, лапки, ко-ко-ко…

Случай 6: АО РСИЦ позвонило на сотовый и прокрутило запись: уважаемый клиент, в личном кабинете на сайте nic.ru для вас размещено важное сообщение…

Тут важно отметить 2 момента. Первый: я, действительно, на тот момент был их клиентом, но моего телефона у них не было (во всяком случае, легально), так что это просто «холодный звонок». Второе: в личном кабинете на сайте nic.ru не существовало и не существует системы обмена сообщениями между клиентами и компанией, все коммуникации идут по электронной или обычной почте (возможно, и по телефону – не знаю по вышеуказанной причине). Разумеется, никакого важного сообщения в ЛК не было, как и неважного, но вдоволь подолбившись в глаза уши, ФАС посчитала, что:

Посредством телефонного звонка Общество проинформировало заявителя о необходимости мониторинга состояния доменных имен, администратором которых он является, в личном кабинете заявителя в целях недопущения прекращения прав их администрирования. По мнению антимонопольного органа, спорный телефонный звонок был направлен заявителю в целях его информирования, в связи с чем, в рассматриваемом телефонном звонке отсутствует информация об объекте рекламирования.

Случай 7: какие-то ряженные патриотами блаженные клянчили через электронную почту подписку на их «военно-патриотические каналы»

Они же дети суворовцы!, – ответила ФАС на жалобу, – А это вот на скриншоте – не реклама, нет объекта рекламирования, творческий труд, аналитика, мнение пользователя, лапки, глазки, ушки, хвостики, общественная организация – это лицо, ведущее блог, война – это мир, свобода – это рабство, незнание – сила…

Исходя из содержания Вашего заявления, в поступившем Вам email-сообщении отсутствует информация об объекте рекламирования. В рассматриваемом письме и указанных в нем ссылках размещаются различные статьи, изложены личные впечатления автора, субъективные выводы и взгляды лица, ведущего интернет-блог. Его целью не является привлечение внимания потребителей к объекту рекламирования, формирование или поддержание интереса к нему и его продвижение на рынке.

Если серьезно, в какой-то момент у меня возникло подозрение, что фасовцам выдают героин дезоморфин за вредность, который они употребляют прямо на рабочем месте, а отмена обезболивающего вызывает у гражданских служащих неописанные в медицинской литературе побочные эффекты, типа избирательной слепоты и delirium transitorium, т.е., по определению Блейхера, расстройства содержания мышления с возникновением не соответствующих реальности болезненных представлений, рассуждений и выводов (и в этом состоянии они пребывают уже лет 20 как).

Но по статистике, которую я приводил в предыдущей статье, ФАС все-таки больше половины жалоб рассмотрел без использования дезоморфина изменяющих сознание веществ. Если вы не хотите, чтобы вся радость от огорчения спамеров досталась мне, присоединяйтесь! Специально для вас выпустили брошюру «Борьба со спамерами правовыми средствами. Руководство по дезинсекции». А я как-нибудь еще расскажу, почему ФАС решила, что может рассматривать дела против спамеров без привлечения к делу сторон, что по этому поводу думают суды и где в России заканчивается обычный лес электронное правосудие.

Работать всегда желательно с первоисточником. В обратном случае мы сталкиваемся с невежеством, Копенгагенскими интерпретациями, Пирамидами Маслоу и Сигарами Фрейда. 

Будет справедливо называть «Оговорки по Фрейду», «Оговорками по Бриллу». Именно этот человек предложил сравнение табачной продукции с предметом олицетворения мужской сексуальности. 

Авраам Арден Брилл,  доктор философии и медицины Колумбийский университет, 1903 г.  Первый психоаналитик, практикующий в Соединенных Штатах и первый переводчик работа Фрейда на английский.

Авторство Брилла нам известны из интервью Эдварда Бернейса, отца-основателя Public Relations, главного проектировщика культуры потребления и по совместительству племянника Фрейд (вот неожиданность).

С окончанием 19-го века Америка стала обществом массового промышленного производства с миллионами людей, собранными в городах. Бернейс искал новый способ менять и управлять мыслями и чувствами толпы. Для этого он обратился к работам своего дяди Зигмунда Фрейда. Когда Бернейс был в Париже, он подарил своему дяде гаванские сигары. В ответ Фрейд подарил копию «общего видения психоанализа». Бернейса заворожила идея потаённых, иррациональных сил внутри человека. Он задумался над тем, как можно заработать, манипулируя подсознанием.

Эдвард обратился к Бриллу по просьбе одного из своих ранних клиентов. В то время существовало табу на курящих на публике женщин. И Джордж Хилл, президент американской табачной корпорации, человек который сделал марку Camel — самой продаваемой на территории США, не мог побороть социальный барьер и попросил Бернейса найти способ разрушить это табу.

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

Факел свободы

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

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

На следующий день это событие было освещено не только во всех нью-йоркских газетах, оно разошлось по всем Соединенным Штатам и по всему миру. И прямо с этого момента продажи сигарет женщинам начали расти. Он сделал их социально приемлемыми с помощью единственного символического события. Бернейс создал идею — если женщина курит, это делает её более сильной и независимой.

Это событие продемонстрировало, что можно заставить людей вести себя иррационально, если связать товары с рациональными желаниями и чувствами людей. Идея о том, что курение делает женщин свободными была полностью иррациональна, но это давало им чувство большей независимости.

Восемь разработчиков YDB собрались, чтобы поделиться тем, что они сделали для последнего релиза YDB v23.1. Рассмотренные новые возможности можно разделить на две категории: функциональные улучшения и улучшения производительности. Давайте начнем с первой.

Начальное сканирование для механизма Change Data Capture (CDC)

Change Data Capture — это механизм, который позволяет создавать поток изменений данных в таблицах и использовать его в других системах. В YDB он реализован поверх YDB topics, надёжных персистентных очередей, похожих по возможностям на Apache Kafka®. Обычно CDC отправляет только те изменения, которые происходят после его включения и настройки. Но бывают и сценарии, когда в целевой системе нужны все существующие данные, включая записанные ранее. Именно в этом случае пригодится появившаяся в версии v23.1 опция начального сканирования для CDC. С этой опцией CDC передаёт текущее состояние на момент создания в том же формате, что и последующие изменения. Гарантируется, что текущее состояние будет отправлено до начала изменений. Ранее для получения того же результата приходилось вручную разбираться какие данные были в таблице до начала подписки и копировать их отдельно другими средствами.

Улучшения в аудитном логе

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

Улучшения производительности

Автоматическая конфигурация пулов акторной системы

Акторная система YDB — среда для параллельных вычислиений на C++, на основе которой построена YDB. Акторы — это легковесные вычислительные единицы, которые общаются друг с другом посредством передачи сообщений (message passing), как локально, так и через сеть. Узлы YDB выполняют код акторов в нескольких пулах потоков. Конфигурация пулов потоков ранее была довольно сложной, но теперь она имеет автоматический режим с динамическим распределением размера пулов на основе текущей загрузки системы и количества доступных ядер процессора.

Улучшение форматов передачи данных между этапами выполнения запросов

Выполнение запроса YDB состоит из нескольких этапов и каждый из них передаёт текущие данные следующему. Мы заменили часть форматов передачи таким образом, чтобы не перекладывать одни и те же данные из одного формата в другой, если это возможно. Кроме того, мы избавились от избыточных таймеров. Эти изменения позволили сэкономить до 30% вычислительных ресурсов при релизе на наши высоконагруженные кластера.

Кэш шаблонов вычислительного графа

Если мы более детально рассмотрим сам процесс вычисления результата запроса, то можно выделить три основных шага:

1. Компиляция запроса

2. Построение шаблона вычислительного графа

3. Выполнение вычислительного графа

В сценарии транзакционной нагрузки (OLTP) первые два этапа могут быть гораздо более затратными, чем третий. Очевидным решением является кэширование их результатов. В YDB уже давно был кэш компиляции запросов, а в версии 23.1 появился новый кэш для второго этапа — шаблонов вычислительного графа. При обнаружении подходящего шаблона в кэше он клонируется, обогащается временными значениями и в результате становится готовым к выполнению вычислений.

Улучшение вторичных индексов

Вторичные индексы являются ещё одной важной функцией для производительности системы управления базами данных. В этом выпуске YDB мы внесли улучшения для двух сценариев, связанных с вторичными индексами.

В YDB вторичные индексы имеют имена и, на момент написания, имя индекса необходимо явно указывать при написании SQL запросов. Таким образом, в производственном окружении может быть полезной замена индекса под определенным именем, например, для добавления столбцов, покрытых индексом. Чтобы учесть такой сценарий, YDB теперь поддерживает атомарную замену вторичных индексов.

YDB позволяет выполнять два типа запросов: запросы данных (data query) для транзакционных (OLTP) нагрузок и сканирующие запросы (scan query) для аналитических (OLAP) нагрузок. Изначально только запросы данных могли использовать вторичные индексы, а теперь сканирующие запросы тоже могут. Однако эта функция ещё не готова для использования в производственных окружениях и не включена по умолчанию в версии 23.1, но вы все равно можете поэкспериментировать с ней, если включите указанную на слайде настройку EnableKqpScanQueryStreamLookup.

Улучшение оптимизации предикатов для чтения таблиц

На уровне ввода-вывода базы данных как правило стараются считывать с дисков лишь минимальный объём данных, необходимый для получения запрошенного результата. В этом релизе YDB мы устранили ещё один случай, когда выполнялось избыточное полное сканирование таблицы при использовании запроса с оператором OR в условии для чтения нескольких диапазонов таблицы по первичному ключу.

Что дальше?

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

Если у вас установлена более старая версия YDB, мы рекомендуем обновиться в ближайшее удобное время, скачав последний релиз и следуя инструкциям по обновлению.

В этом дайджесте разбираем Swift Runtime на детали и экономим гигабайты с SPM, боремся с фризами и ANR, проектируем функционал сторис, исследуем отказы на собеседовании, определяем маркетинг подписных приложений и многое другое!

В нашем Telegram-канале Mobile Insights, еще больше материалов для мобильных разработчиков, а в IT Insights — об интересном коде и технологиях. Подключайтесь!

Хотим в очередной раз пригласить вас в опрос Developer Nation. Расскажите, что вам нравится или не нравится в популярных инструментах и платформах. Опрос охватывает 13 направлений: мобильные, десктопные, облачные и веб-приложения, промышленный Интернет вещей, игры, машинное обучение, искусственный интеллект и т.п. Опрос доступен на 10 языках, в том числе и на русском. Можно начать и сохранить для продолжения. Можно выиграть призы. Главное — внести свой вклад в развитие сообщества разработчиков.

iOS

• Разбираю Swift Runtime на детали
• Как в Swift Package Manager сэкономить гигабайты трафика и места на диске
• Библиотека криптования ChaCha20
• OptionSet в деталях
• Distributed actors и где они обитают
• Apple определила API, использование которых надо будет объяснять
• Эксперты App Store: онлайн-сессии в августе
• Apple принимает заявки на Vision Pro Developer Kit
• Любовное письмо к Objective-C
•  Creating and modifying UIKit components like in SwiftUI
•  Mobile Automation Stories — XCUITest
•  Mastering ObjectIdentifier in Swift
•  State Management using Protocol-Oriented Programming + Generics
•  The Ultimate Guide to Building SwiftData Applications
•  Creating an Animated Background using SwiftUI
•  [Swift] Property wrappers to the rescue!
•  Adopting Efficient Networking Practices in iOS Apps
•  Refactoring our Swift SDK
•  Chloe’s Opinionated and Biased Law of SwiftUI
•  Integrating the Swift EstimoteUWB SDK into your SwiftUI project
•  Embracing the Future with Swift Concurrency: A Comprehensive Overview
•  Why you should use OSLog in 2023
•  iOS Development with Factory: The Power of Dependency Injection
•  How to Create and Publish Your Own Swift Package Manager (SPM) Library
•  How to deal with custom fonts in Swift and SwiftUI
•  Access Control in Swift
•  TipKit — iOS 17 — SwiftUI
•  OSLog and Logger
•  Radial Layout With Gestures — SwiftUI
•  Inout Parameters and Mutating Functions
•  How to master Combine like a Pro – The Basics
•  SwiftUI NavigationStack Hero Animation Effect — Custom Matched Geometry Effect
•  Design Patterns In Swift: паттерны проектирования на Swift
•  NearDrop: Nearby Share для macOS

Android

• Фризы и ANR? Проверьте утечки памяти!
• Настраиваем интерфейс Android-приложения с помощью тем
• 7 книг по Android-разработке, на которые стоит обратить внимание в 2023 году
• Переиспользование модулей в многомодульных Android приложениях
• Секретная фича в Android Studio: логируем, пока дебажим, не меняя сам код
• Google Play начнет пессимизировать приложения, не поддерживающие планшеты
• Вышла стабильная версия Android Studio Giraffe
• 5 советов Kotlin-разработчикам для повышения чистоты кодовой базы
•  Using Version Catalogs from Gradle Precompiled Scripts with Kotlin DSL
•  How to Inject Navigation Argument Directly into View Model with Jetpack Compose and Hilt
•  Android Adaptive Icons
•  Screen Transition Animations with Jetpack Navigation
•  Migrate your Multi-Module App to AGP and Gradle 8.0 with Android Studio Flamingo
•  Threads Invitation Card with Jetpack Compose
•  Jetpack Compose: Unveiling the Hottest Projects and Libraries on GitHub in 2023
•  Rich UI Models in Android using MVVM and Jetpack Compose
•  Android Security: Securing your Gradle builds from baddies
•  A Step-by-Step Guide to Building a Timeline Component with Jetpack Compose
•  Jetpack Compose — The order of modifiers does matter
•  Nibel: A Navigation Library for Adopting Jetpack Compose in Fragment-Based Apps
•  Coroutines Masterclass: Chapter-1: Foundation of Coroutines
•  Exploring Differences Between lateinit and lazy in Kotlin
•  Error Handling in Clean Architecture using Flow and Jetpack Compose
•  Kotlin Enum Class
•  Simplify Dependency Management for Android Projects with Gradle Version Catalog and Dependabot
•  Navigating the Complexities: Building a Scalable Multi-Module Navigation Architecture in Android
•  Now in Android: 87 — Android 14 Beta 4, Google Play policy update, and Compose Performance
•  What’s new in Android Studio — Giraffe
•  Text Fields — UX With Material3
•  Buttons — UX With Material3
•  SQLDelight: типобезопасные Kotlin API из SQL
•  Molecule: создание потоков StateFlow в помощью Jetpack Compose

Кроссплатформа

• Cocos Creator: Это самый мощный игровой движок, о котором вы не знали
• Под капотом анимаций в React Native. Часть 1/2: Animated and Bridge
• Зачем нужны PWA-приложения: примеры успешного использования
• Кодогенерация для Flutter: что, как и зачем
•  Beginner’s guide on Flutter for iOS developers
•  Server-Driven UI Implementation from Scratch in Flutter
•  Unifying Video Players: Compose Multiplatform for iOS, Android & Desktop
•  The Top 5 Flutter State Management Solutions: A Deep Dive
•  FlutterCon 23 Resources
•  Integrate Apple Sign-In on Android using Flutter
•  KMM in a simple language learning app: was it worth it?
•  Improve your Flutter app performance with this small trick
•  Build an iOS & Android app in 100% Kotlin with Compose Multiplatform
•  Full Guide on Building your first Kotlin Multiplatform Project with Kobweb
•  NativePHP: десктопные приложения на PHP

Разработка

• Работа в Европе для мобильных разработчиков
• Неизменная ценность ручных тестировщиков: важность и преимущества в эпоху автоматизации
• Проектируем функционал сторис
• Алгоритмическое собеседование в Яндекс в прямом эфире
• Постоянные отказы на собеседованиях: что мне делать
• На шаг ближе к метавселенной, или Как мы оживили аватары пользователей в VK Звонках
• Как сделать аналог Firebase App Distribution
• Ozon Tech Intro Meetup: как работают системы поиска, рекомендаций и рекламы
• Значение совещаний и некоторые альтернативы
• 43% программистов снится работа
•  Game On: UI Design Meets Gamification
•  On Becoming a VP of Engineering, Part 1: The Path to VP + Part 2: Doing the Job
•  Platform engineering is just DevOps with a product mindset
•  Building Startups as a Developer: Learning from My Mistakes
•  Iosevka: шрифт для кода

Аналитика, маркетинг и монетизация

• $18.2 млн в Серии B: Airvet — телемедицина для домашних животных
• Маркетинг подписных приложений 2023 — отчет AppsFlyer и Liftoff
• Новая AR-платформа Mirrorscape улучшает Dungeons & Dragons
• Reddit после закрытия API: загрузки выросли, но доходы упали
•  The ultimate guide to A/B testing

AI, Устройства, IoT

• Как создавать качественные ML-системы. Часть 2: приручаем хаос + Часть  1
• Подключаем Zigbee-устройства к контроллеру Wiren Board и пишем сценарии на wb-rules
• Высокоточное измерение ЭКГ
• Stability AI выпускает Stable Diffusion XL 1.0
• Умные колонки Assistant не перейдут на Fuchsia
• У Flipper Zero появился магазин приложений
•  Chat with your databases using LangChain
•  The Ultimate Tech Stack for Building AI Products
•  A comprehensive guide to running Llama 2 locally
•  Automating Web Scraping with ChatGPT Code Interpreter

← Предыдущий дайджест. Если у вас есть другие интересные материалы или вы нашли ошибку — пришлите, пожалуйста, в почту.

Привет, Хабр! Хочу рассказать о том, как я решал задачу связанную с обработкой и визуализацией томографических изображений, а именно — измерение и поиск кратчайшей траектории на поверхности 3D изображения. Одна из областей применения — измерение антропометрических данных на КТ/МРТ исследованиях.

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

Содержание

• Воксельный объем

• Классические алгоритмы поиска пути

• Проблема Евклидова кратчайшего пути

• Планирование пути под любым углом

• Проблема ориентации воксельной поверхности

• Полигонализация

• Поиск пути на полигональной сетке

• Заключение

Воксельный объем

Воксельный объем представляет собой трехмерный куб – структура моделирующая собой объемный объект, где каждый элемент такой структуры называется вокселем. Воксели не содержат информацию о своих координатах в пространстве, поэтому координаты вычисляются из их позиции в объеме.

Воксели хорошо подходят для описания моделей имеющие внутреннюю структуру, например для моделирования сплошных сред или трехмерной реконструкции томографических исследований. А каждый воксель может характеризоваться определенными значениями, такими как скорость частицы или рентгеновская плотность вещества.

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

Для простоты изложения и понимания материала, в данной статье будут рассматриваться 2D изображения, но используемы алгоритмы с легкостью расширяются и на объемное пространство.

Классические алгоритмы поиска пути

Тем, кто хоть немного знаком с теорией графов, наверняка слышали про обход графа в ширину (BFS) и в глубину (DFS), или же про алгоритм Дейкстры. Эти методы являются базовыми для решения задачи поиска пути. Только вот алгоритм Дейкстры, в отличии от двух других позволяет найти не только наличие траектории, но и выдать кратчайший из возможных. Могу порекомендовать онлайн-книгу, в которой достаточно обширно рассказывается на тему поиска пути.

Большинство алгоритмов поиска имеют одну общую идею, которая заключается в обходе графа, и порядок обхода является ключевым моментом, определяющий название алгоритма. Если же посещение вершин будет организовано в виде очереди, то получится поиск в ширину, а если в качестве структуры данных будет стек – поиск в глубину. Также можно представить обход над очередью с приоритетом, то в таком случае получится алгоритм Дейкстры. Одним из самых известных алгоритмов поиска кратчайших путей является A*, который представляет собой модификацию Дейкстры.

Может показаться, что решение поставленной задачи очевидно, ведь узлы графа – это видимые воксели, связь между двумя соседними векселями образуют ребра, а вес ребра – это расстояние между вокселями, нужно всего лишь реализовать поиск пути методом A*. Но есть один нюанс. Данный алгоритм действительно является эффективным и оптимальным, но он прежде всего ориентирован на дискретные области. И первая проблема — это применение алгоритма к воксельному объему, представленный в виде дискретного набора элементов, которые в свою очередь описывают непрерывное (в данном случае Евклидово) пространство.

Проблема Евклидова кратчайшего пути

Классические алгоритмы распространяются на дискретном наборе траекторий, и в случае двухмерной регулярной сетки количество направлений будет равно 8, с шагом в 45 градусов.

Планирование пути под любым углом

Алгоритмы планирования пути под любым углом направлены на получение оптимальных или почти оптимальных траекторий с учетом непрерывности пространства, и естественно это приводит к росту стоимости вычислений.

Post-smoothing

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

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

Алгоритм Lazy Theta*

Более эффективным подходом будет применение алгоритмов, основанных на трассировке траектории между точками, с целью определения видимости между узлами. Одним из таких алгоритмов является Theta* [1], который является модификацией A*. В свою очередь у данного метода есть оптимизация в виде Lazy Theta* [2], которая приводит к меньшим вычислительным затратам.

Вкратце алгоритм Theta* заключается в том, что при распространении волны поиска, следующая точка проверяет видимость до родительской точки текущего узла, и в случае успеха родитель текущего узла становится также родителем следующей точки, в противном случае родителем становится текущая вершина. Таким образом, при обнаружении препятствия на пути к цели, алгоритм ищет наилучшую точку в направлении цели на линии между текущей точкой и предыдущей наилучшей точкой, а не пересчитывает путь до каждой точки, это похоже на формирование некого графа видимости.

Проблема ориентации воксельной поверхности

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

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

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

Полигонализация

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

Алгоритм марширующих кубов является трехмерным алгоритмом, который используется для создания поверхностей в трехмерном пространстве. Однако, алгоритм также может быть адаптирован для работы в двумерном пространстве.

Идея алгоритма марширующих кубов в 2D состоит в том, чтобы разбить изображение на набор прямоугольников (пиксели 2×2). Затем, используя информацию о значениях пикселя в углах каждого прямоугольника, алгоритм создает линии, которые проходят через грани прямоугольника. Таким образом, создается набор линий, которые соединяются, чтобы создать границу объекта.

Алгоритм марширующих кубов в 3D основан на той же идее, что и в 2D. Но вместо того, чтобы использовать прямоугольники, он разделяет объемное изображение на набор кубов, каждый из которых состоит из 8 вокселей (вершин). Затем, используя информацию о значениях вокселя внутри каждого куба, алгоритм создает поверхности, которые проходят через грани куба. Таким образом, создается набор треугольников, которые соединяются, чтобы создать границу объекта.

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

Поиск пути на полигональной сетке

В результате полигонализации изображения, мы возвращаемся к дискретному представлению поверхности в виде графа. Здесь проблему сглаживания можно решить с помощью вычисления геодезических расстояний [3],[4]. Геодезические расстояния являются наиболее точным способом измерения расстояний на поверхности. Они учитывают не только геометрическую длину пути, но и особенности самой поверхности. Эти различия можно увидеться на рисунке ниже.

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

Заключение

Построение геодезического пути было достаточно для решения данной задачи, но все же не дает покоя мысль о том, что данную задачу, можно было бы решить без перехода к полигональной поверхности. В процессе, я наткнулся на книгу по функционально-воксельному моделированию [5], и работу по применению функционально-воксельного метода в решении задач поиска пути [6]. Но уже не было желания читать и разбирать эти работы, таким образом изучение данного вопроса представляется читателю.

Литература

1. Daniel, Kenny & Nash, Alex & Koenig, Sven & Felner, Ariel. (2014). Theta*: Any-Angle Path Planning on Grids. J. Artif. Intell. Res. (JAIR). 39. 10.1613/jair.2994.

2. Nash, Alex & Koenig, Sven & Tovey, Craig. (2010). Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D.. Proceedings of the 3rd Annual Symposium on Combinatorial Search, SoCS 2010. 1.

3. Crane, Keenan & Livesu, Marco & Puppo, Enrico & Qin, Yipeng. (2020). A Survey of Algorithms for Geodesic Paths and Distances.

4. Crane, Keenan & Weischedel, Clarisse & Wardetzky, Max. (2017). The heat method for distance computation. Communications of the ACM. 60. 90-99. 10.1145/3131280.

5. Толок А.В. Функционально-воксельный метод в компьютерном моделировании
   / Под ред. акад. РАН С.Н. Васильева. – М.: ФИЗМАТЛИТ, 2016. 112 с. ISBN: 978-5-9221-1680-0.

6. Локтев М.А. Особенности применения функционально-воксельного моделирования в задачах поиска пути с препятствиями // Информационные технологии в проектировании и производстве. 2016. № 1. С. 45–49.