Рубрика «Алгоритмы» - 69

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

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

Терпение и труд весь текст извлекут - 1

Источник изображения: Википедия

Читать полностью »

image

В этой статье представлена реализация на Python алгоритма распознавания источников освещения на картах окружения (LDR или HDR) при помощи равнопромежуточной проекции (equirectangular projection). Однако после внесения незначительных изменений её также можно использовать с простыми фоновыми изображениями или кубическими картами. Примеры возможного применения алгоритма: программы трассировки лучей, в которых требуется распознавать первичные источники освещения для испускания из них лучей; в растеризованных рендерерах он может применяться для отбрасывания теней, использующих карту окружения; кроме того, алгоритм также можно применять в программах устранения засветов, например в AR.

Алгоритм состоит из следующих этапов:

  1. Снижение разрешения исходного изображения, например, до 1024.
  2. Преобразование изображения в яркость (luminance), при необходимости с размытием изображения.
  3. Применение метода квази-Монте-Карло.
  4. Преобразование из сферических координат в равнопромежуточные.
  5. Фильтрация сэмплов на основании яркости соседа.
  6. Сортировка сэмплов на основании их яркости.
  7. Фильтрация сэмплов на основании евклидовой метрики.
  8. Слияние сэмплов при помощи алгоритма Брезенхэма.
  9. Вычисление позиции кластера освещения на основании его яркости.

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

  lum = img[:, :, 0] * 0.2126 + img[:, :, 1] * 0.7152 + img[:, :, 2] * 0.0722

Дополнительно можно применить к изображению яркости небольшое размытие, например, в 1-2 пикселя для изображения разрешением 1024, для устранения всех высокочастотных деталей (в частности, вызванных снижением разрешения).
Читать полностью »

Data Science Digest (July 2019) - 1

Приветствую всех!

Лето в полном разгаре, и если вы планируете быть в Одессе 5-го июля, приглашаю вас на ODS митап и дата-бар, который организовывает одесская ODS.ai команда. Напоминаю, что у дайджеста есть свой Telegram-канал и страницы в соцсетях (Facebook, Twitter, LinkedIn, Medium), где я ежедневно публикую ссылки на полезные материалы. Присоединяйтесь!

А пока предлагаю свежую подборку материалов под катом.
Читать полностью »

Ручная сегментация легких занимает около 10 минут и требуется определенная сноровка, чтобы получить такой же качественный результат, как при автоматической сегментации. Автоматическая сегментация занимает около 15 секунд.

Я предполагал, что без нейронной сети удастся получить точность не выше 70%. Также я предполагал, что морфологические операции – это только подготовка изображения к более сложным алгоритмам. Но в результате обработки тех, хоть и немногочисленных 40 образцов томографических данных, что есть на руках, алгоритм выделил легкие без ошибок, причём после теста на первых пяти случаях алгоритм уже не претерпевал значительных изменений и с первого применения правильно отработал на остальных 35 исследованиях без изменения настроек.

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

Автоматическая сегментация дыхательных органов - 1

Читать полностью »

Методы сопряжения электрических соединений при трассировке дифференциальных пар на печатных платах - 1
В публикации приводится описание метода сопряжения электрических соединений при трассировке дифференциальных пар на печатных платах. Основу метода составляет техника генерации и применения шаблонов подключения печатных проводников дифференциальной пары к трассируемым контактам электронных компонентов с минимизацией длины несопряженных участков.
Читать полностью »

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

В статье я покажу интересное реальное применение динамического программирования — задача вырезания швов (seam carving). Задача и методика подробно описаны в работе Авидана и Шамира «Вырезание швов для изменения размеров изображения с учётом контента» (статья в свободном доступе).

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

Процедурная генерация планет - 1

От переводчика:
Представляю вашему вниманию статью авторства Andy Gainey, в прошлом независимого разработчика игровых инструментов, ныне сотрудника Paradox Development Studio. На мой взгляд, автор играючи создал один из лучших процедурных генераторов планет с открытым исходным кодом.

Читать полностью »

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

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

Используем данные на практике - 1
Читать полностью »

Генерируем тайловые уровни и прячем квадраты от игрока - 1

Генерация уровней в Unexplored 2

Мы очень гордимся генератором уровней игры Unexplored 2, это программа, отвечающая всем современным требованиям. В посте я расскажу о том, как создаются уровни игры.

Нам не пришлось заново изобретать велосипед. В Unexplored 1 мы уже создали техники, которые сильно повлияли на успех первой игры. Unexplored 2 просто продолжила начатое. Фундамент нашей технологии состоит из двух частей: мы применяем многоэтапную генерацию, которая почти имитирует процесс, очень похожий на работу живого дизайнера уровней. Поверх него мы используем технику под названием "циклическая генерация подземелий", которая гораздо лучше справляется с генерацией естественно выглядящих уровней, чем большинство стандартных приложений генеративного создания контента. В этом посте я расскажу о первом аспекте. Адаптация циклической генерации подземелий к Unexplored 2 будет темой будущего поста.

Имитация «человеческого» дизайна уровней

Генератор уровней разбивает процесс генерации уровня на целое множество управляемых этапов. Он проходит путь от высокоуровневого планирования до низкоуровневой детальной карты уровня. По сути, он сначала создаёт набросок уровня, а затем начинает добавлять детали, пока уровень не станет завершённым и заполненным.
Читать полностью »

Пользователи ClickHouse знают, что его главное преимущество — высокая скорость обработки аналитических запросов. Но как мы можем выдвигать такие утверждения? Это должно подтверждаться тестами производительности, которым можно доверять. О них мы сегодня и поговорим.

Обфускация данных для тестов производительности - 1

Такие тесты мы начали проводить в 2013 году, задолго до того, как продукт стал доступным в опенсорсе. Как и сейчас, тогда нас больше всего интересовала скорость работы данных сервиса Яндекс.Метрика. Мы уже хранили данные в ClickHouse с января 2009 года. Часть данных записывалась в базу с 2012 года, а часть — была переконвертирована из OLAPServer и Metrage — структур данных, которые использовались в Яндекс.Метрике раньше. Поэтому для тестов мы взяли первое попавшееся подмножество из 1 миллиарда данных о просмотрах страниц. Запросов в Метрике ещё не было, и мы придумали запросы, больше всего интересные нам самим (всевозможные виды фильтрации, агрегации и сортировки).

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

После того, как ClickHouse вышел в опенсорс в 2016 году, к тестам стало больше вопросов.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js