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

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

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

Мы с моим научным руководителем готовим небольшую монографию по обработке изображений. Решил представить на суд хабрасообщества главу, посвящённую алгоритмам сжатия изображений. Так как в рамках одного поста целую главу уместить тяжело, решил разбить её на три поста:
1. Методы сжатия данных;
2. Сжатие изображений без потерь;
3. Сжатие изображений с потерями.
Ниже вы можете ознакомиться с первым постом серии.

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

Думаю, всем читателям хабра хорошо известны алгоритмы энтропийного сжатия с использованием префиксных кодов (алгоритмы Шеннона-Фано, Хаффмана и др.). Особенностью этих алгоритмов является тот факт, что длина кода определённого символа зависит от частоты этого символа в закодированном сообщении. Соответственно при декодировании сообщения необходимо иметь таблицу частот. Данная статья посвящена рассмотрению малоизученной, но важной задачи – передаче частот исходного алфавита.

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

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

Когда я учился в школе, мы изучали логику, но сейчас даже в моём любимом лицее её почему-то не преподают. Более того, я узнал, что большинство моих знакомых (даже успешно закончивших вузы) не знают, ни о логическом квадрате, ни о различных модусах. В этом небольшом топике, я постараюсь вкратце рассказать обо всём. Сразу скажу, что гуру дискретной математики вряд ли узнают что-то новое, но остальным должно быть как минимум интересно, а как максимум полезно.

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

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

Когда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 15 минут в день на её решение тратится. Разумеется, я попробовал автоматизировать этот процесс.

Сразу хочу предупредить, что этот топик не совсем по тематике Хабра, но в комментариях к посту про разработанный в MIT элемент идею вроде бы поддержали, так что ниже я опишу некоторые соображения о биотоливных элементах.
Работа, на основе которой написан данный топик, выполнялась мной в 11 классе, и заняла второе место на международной конференции INTEL ISEF.

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

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

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

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

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

Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:

• Алгоритмы сжатия без потерь;
• Алгоритмы сжатия с потерями.

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

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

• Алгоритм закраски с затравкой
• Алгоритмы со списком рёберных точек
• Алгоритмы XOR

Сегодня на Хабре появилась очень интересная статья, о поиске минимального (максимального) значения на отрезке в массиве. Так как статья оказалось интересной и популярной, я решил с вами поделиться ещё одним алгоритмом поиска в массиве некоторых «специальных» значений.