Данная статья рассказывает не только о наиболее распространённых фильтрах обработки изображений, но в понятной форме описывает алгоритмы их работы. Статья ориентирована, прежде всего, на программистов, занимающихся обработкой изображений.
Рубрика «Алгоритмы» - 310
Матричные фильтры обработки изображений
2012-04-25 в 17:53, admin, рубрики: image processing, Алгоритмы, Песочница, метки: image processingСловомания — отгадываем слова. Часть 1, Ruby
2012-04-25 в 15:27, admin, рубрики: ruby, Алгоритмы, Программирование, словомания, метки: ruby, словомания 
Впервые увидев Словоманию, я запал на нее очень крепко, проводя бесконечные часы отгадывая слова. Суть игры: есть сетка 4х4, в каждой ячейке расположена буква. Задача игрока — составлять слова, последовательно соединяя буквы между собой.
После энного количества времени появилась идея: а что если автоматизировать процесс разгадывания слов? Ведь зачастую я и сам занимаюсь простым перебором комбинаций в попытках сложить слово. Очевидно, что компьютер справится с такой задачей гораздо продуктивнее любого человека. Конечно, за исключением тех случаев, когда слово сразу «видно» на поле, но эта задача уже решена нашим мозгом, так что было решено заняться разделением труда между мозгом и компьютером, чтобы каждый занимался тем, что ему проще дается.
Читать полностью »
Персистентные деревья отрезков
2012-04-24 в 17:51, admin, рубрики: Алгоритмы, персистентные структуры данных, Программирование, структуры данных, метки: персистентные структуры данных, структуры данныхВведение
Структуры данных можно разделить на две группы: эфемерные (ephemeral) и персистентные (persistent).
Эфемерными называются структуры данных, хранящие только последнюю свою версию.
Персистентные структуры, то есть те, которые сохраняют все свои предыдущие версии, в свою очередь можно разделить еще на две подгруппы: если структура данных, позволяет изменять только последнюю версию, она называется частично персистентной (partially persistent), если же позволяется изменять любую версию, такая структура считается полностью персистентной (fully persistent).
Далее будет рассмотрено дерево отрезков и его полностью персистентная версия.
Весь код доступен на GitHub.
Читать полностью »
О подходах к сравнению версий файлов
2012-04-24 в 4:45, admin, рубрики: алгоритм, Алгоритмы, контроль версий, оптимизация, Программирование, разработка, расстояние Левенштейна, сравнение, сравнение файлов, хэширование, метки: алгоритм, Алгоритмы, контроль версий, оптимизация, расстояние Левенштейна, сравнение, сравнение файлов, хэширование Люди, использующие системы контроля версий исходного кода (SVN, Mercurial, Git и т.п.), наверняка часто пользуются возможностью сравнения версий файлов для просмотра внесенных пользователями изменений. Существует множество независимых программ сравнения версий (WinMerge, BeyondCompare и др.). При сравнении версий, как правило, две версии файла показываются рядом друг с другом таким образом, чтобы одинаковые (неизменившиеся) части документов были расположены напротив друг друга, а изменившиеся (добавленные и удаленные) выделяются соответствующим цветом.
Уверен, многим было бы интересно узнать, какие алгоритмы могут использоваться для реализации такого сравнения.
Читать полностью »
Полиномиальные хеши и их применение
2012-04-23 в 19:37, admin, рубрики: Алгоритмы, олимпиадные задачи, поиск подстроки в строке, сравнение строк, строки, хеширование, метки: Алгоритмы, олимпиадные задачи, поиск подстроки в строке, сравнение строк, строки, хешированиеЗдравствуй. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.
Введение
Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).
Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Читать полностью »
Сжатие информации без потерь. Часть вторая
2012-04-23 в 11:55, admin, рубрики: Алгоритмы, сжатие без потерь, сжатие данных, теория информации, метки: сжатие без потерь, сжатие данных, теория информацииВо второй части будут рассмотрены арифметическое кодирование и преобразование Барроуза-Уилера (последнее часто незаслуженно забывают во многих статьях). Я не буду рассматривать семейство алгоритмов LZ, так как про них на хабре уже были неплохие статьи.
Итак, начнем с арифметического кодирования — на мой взгляд, одного из самых изящных (с точки зрения идеи) методов сжатия.
Читать полностью »
Шум Перлина (Perlin Noise)
2012-04-23 в 7:41, admin, рубрики: game development, Gamedev, gamedevelopment, Алгоритмы, переводы, метки: Gamedev, gamedevelopment, АлгоритмыДоброго времени суток. Предлагаю Вашему вниманию перевод статьи про шум Перлина (вот этой). Ссылки на эту статью уже мелькали на хабре (тут), но перевод статьи мне не попался. Так что надеюсь кому либо он может оказаться полезен.
Многим людям приходилось использовать генератор случайных чисел в программах для создания непредсказуемости, чтобы сделать движение и поведение объектов более натуральными или генерировать текстуры. Генераторы случайных чисел, конечно, имеют свои области применения, но иногда их выход может быть слишком «жесткий», чтобы казаться естественным. В этой статье мы представляем функцию, которая имеет очень широкий спектр применения, больше, чем я мог бы думать, но в основном везде, где вам нужно чтобы что-то выглядело естественного происхождения. К тому же вывод может быть легко настроен под ваши нужды.
Если посмотреть на многие вещи в природе, вы заметите, что они являются фрактальными. Они имеют различные уровни детализации. Типичным примером является очертание горного хребта. Оно содержит значительные различия в высоте (горы), средние изменения (холмы), небольшие вариации (валуны), крошечные изменения (камни) и так далее. Посмотрите на что угодно: распространение пятен травы на поле, волн в море, движение муравьев, движение ветвей дерева, узоры из мрамора, ветра. Все эти явления поддаются той же схеме, в больших и малых вариациях. Функция шума Перлина воссоздает это, просто складывая функции шума в различных масштабах.
Для создания функции шума Перлина, вам нужны две вещи, функции шума и функция интерполяции.
Читать полностью »
Сжатие информации без потерь. Часть первая
2012-04-18 в 12:31, admin, рубрики: Алгоритмы, сжатие без потерь, сжатие данных, теория информации, метки: сжатие без потерь, сжатие данных, теория информации Доброго времени суток.
Сегодня я хочу коснуться темы сжатия данных без потерь. Несмотря на то, что на хабре уже были статьи, посвященные некоторым алгоритмам, мне захотелось рассказать об этом чуть более подробно.
Я постараюсь давать как математическое описание, так и описание в обычном виде, для того, чтобы каждый мог найти для себя что-то интересное.
В этой статье я коснусь фундаментальных моментов сжатия и основных типов алгоритмов.
Читать полностью »
Рандомизированые Алгоритмы
2012-04-18 в 9:53, admin, рубрики: Алгоритмы, обзор, рандомизация, теория вероятностей, метки: обзор, рандомизация, теория вероятностей Надеюсь что тема будет интересна людям которые знакомы с обычными алгоритмами и хотят узнать об упомянутых выше в общих чертах, что бы иметь представление о чем речь. Постараюсь избегать вычеслений и излагать на интуитивном уровне. И хотя интуиция в теории вероятностей часто подводит, давайте все же попробуем.
Читать полностью »
Unbiased rendering (рендеринг без допущений)
2012-04-16 в 14:47, admin, рубрики: 3d графика, path tracing, ray tracing, unbiased rendering, Алгоритмы, Анимация и 3D графика, рендеринг, рендеринг без допущений, трассировка лучей, трассировка пути, метки: 3d графика, path tracing, ray tracing, unbiased rendering, Алгоритмы, рендеринг, рендеринг без допущений, трассировка лучей, трассировка путиВ компьютерной графике, рендеринг без допущений относится к технике рендеринга, которая не вносит в расчет систематических ошибок, предположений или погрешностей. Изображение получается таким, каким должно быть в природе, а рендер не имеет настроек качества поверхностей либо источников света.
.png "Unbiased rendering (рендеринг без допущений)")
Изображение отрендерено с помощью Maxwell Render.