• Изобретаем JPEG

    • Tutorial

    Вы правильно поняли из названия, что это не совсем обычное описание алгоритма JPEG (формат файла я подробно описывал в статье «Декодирование JPEG для чайников»). В первую очередь, выбранный способ подачи материала предполагает, что мы ничего не знаем не только о JPEG, но и о преобразовании Фурье, и кодировании Хаффмана. И вообще, мало что помним из лекций. Просто взяли картинку и стали думать как же ее можно сжать. Поэтому я попытался доступно выразить только суть, но при которой у читателя будет выработано достаточно глубокое и, главное, интуитивное понимание алгоритма. Формулы и математические выкладки — по самому минимуму, только те, которые важны для понимания происходящего.

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

    Если есть желание, то предлагаю пройти те же этапы самостоятельно параллельно со статьей. Проверить, насколько приведенные рассуждения подходят для разных изображений, попытаться внести свои модификации в алгоритм. Это очень интересно. В качестве инструмента могу порекомендовать замечательную связку Python + NumPy + Matplotlib + PIL(Pillow). Почти вся моя работа (в т. ч. графики и анимация), была произведена с помощью них.

    Внимание, трафик! Много иллюстраций, графиков и анимаций (~ 10Мб). По иронии судьбы, в статье про JPEG всего 2 изображения с этим форматом из полусотни.
    Читать дальше →
  • Расшифровка трассировщика лучей размером с открытку

    • Translation

    «Он снова это сделал!», — вот, что первое пришло мне в голову, когда я посмотрел на оборотную сторону флаера Pixar [1], полностью заполненную кодом. Скопление конструкций и выражений была подписана в правом нижнем углу не кем иным, как Эндрю Кенслером. Для тех, кто его не знает, скажу: Эндрю — это программист, придумавший в 2009 году 1337-байтный трассировщик лучей размером с визитку.

    На этот раз Эндрю придумал нечто более объёмное, но с гораздо более интересным визуальным результатом. Так как я закончил писать свои Game Engine Black Books про Wolf3D и DOOM, у меня появилось время на изучение внутренностей его загадочного кода. И почти сразу меня буквально очаровали обнаруженные в нём техники. Они сильно отличались от предыдущей работы Эндрю, основанной на «стандартном» трассировщике лучей. Мне было интересно узнать о ray marching, функциях конструктивной объемной геометрии, рендеринге Монте-Карло/трассировкой пути, а также множестве других трюков, которые он использовал, чтобы ужать код в такой небольшой кусок бумаги.

    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 13: «Сетевые протоколы», часть 3

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
    Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
    Лекция 5: «Откуда берутся ошибки систем безопасности» Часть 1 / Часть 2
    Лекция 6: «Возможности» Часть 1 / Часть 2 / Часть 3
    Лекция 7: «Песочница Native Client» Часть 1 / Часть 2 / Часть 3
    Лекция 8: «Модель сетевой безопасности» Часть 1 / Часть 2 / Часть 3
    Лекция 9: «Безопасность Web-приложений» Часть 1 / Часть 2 / Часть 3
    Лекция 10: «Символьное выполнение» Часть 1 / Часть 2 / Часть 3
    Лекция 11: «Язык программирования Ur/Web» Часть 1 / Часть 2 / Часть 3
    Лекция 12: «Сетевая безопасность» Часть 1 / Часть 2 / Часть 3
    Лекция 13: «Сетевые протоколы» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Итоги развития компьютерного зрения за один год

    • Translation
    Часть первая. Классификация/локализация, обнаружение объектов и слежение за объектом

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

    Введение


    Компьютерным зрением обычно называют научную дисциплину, которая даёт машинам способность видеть, или более красочно, позволяя машинам визуально анализировать своё окружение и стимулы в нём. Этот процесс обычно включает в себя оценку одного или нескольких изображений или видео. Британская ассоциация машинного зрения (BMVA) определяет компьютерное зрение как «автоматическое извлечение, анализ и понимание полезной информации из изображения или их последовательности».

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



      Достоинства, проблемы и ограничения сверточных нейронных сетей (CNN) в настоящее время достаточно неплохо изучены. Прошло уже около 5 лет после признания их сообществом инженеров и первое впечатление «вот теперь решим все задачи», хочется верить, уже прошло. А значит, пришло время искать идеи, которые позволят сделать следующий шаг в области ИИ. Хинтон, например, предложил CapsuleNet.
      Вместе с Алексеем Редозубовым, опираясь на его идеи об устройстве мозга, мы тоже решили отступить от мейнстрима. И сейчас у меня есть что показать: архитектуру (идёт заглавной картинкой для привлечения внимания) и исходники на Tensorflow для MNIST.

      Более формально, результат описан в статье на arxiv.
      Читать дальше →
    • Сверточная сеть на python. Часть 2. Вывод формул для обучения модели


        В прошлой статье мы рассмотрели концептуально все слои и функции, из которых будет состоять будущая модель. Сегодня мы выведем формулы, которые будут отвечать за обучение этой модели. Слои будем разбирать в обратном порядке — начиная с функции потерь и заканчивая сверточным слоем. Если возникнут трудности с пониманием формул, рекомендую ознакомиться с подробным объяснением (на картинках) метода обратного распространения ошибки, и также вспомнить о правиле дифференцирования сложной функции.
        Читать дальше →
      • Готовим данные для анализа правильно



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

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



            Распознавание автомобильных номеров до сих пор является самым продаваемым решением на основе компьютерного зрения. Сотни, если не тысячи продуктов конкурируют на этом рынке уже на протяжении 20-25 лет. Отчасти поэтому сверточные нейронные сети (CNN) не бьют прежние алгоритмические подходы на рынке.

            Но опыт последних лет говорит, что алгоритмы CNN позволяют делать надежные и гибкие для применения решения. Есть и еще одно удобство: при таком подходе всегда можно улучшить надежность решения на порядок после реального внедрения за счет переобучения. Кроме того, такие алгоритмы отлично реализуются на GPU (графических модулях), которые значительно эффективней с точки зрения потребления электроэнергии, чем обычные процессоры. А платформа Jetson TX от NVidia так просто потребляет очень мало по меркам современных вычислителей. Наглядное «энергетическое превосходство»:
            Читать дальше →
          • Глубокое обучение для новичков: распознаем изображения с помощью сверточных сетей

            • Translation
            • Tutorial

            Введение


            Представляем вторую статью в серии, задуманной, чтобы помочь быстро разобраться в технологии глубокого обучения; мы будем двигаться от базовых принципов к нетривиальным особенностям с целью получить достойную производительность на двух наборах данных: MNIST (классификация рукописных цифр) и CIFAR-10 (классификация небольших изображений по десяти классам: самолет, автомобиль, птица, кошка, олень, собака, лягушка, лошадь, корабль и грузовик).


            Читать дальше →
          • Глубокое обучение для новичков: распознаем рукописные цифры

            • Translation
            • Tutorial

            Представляем первую статью в серии, задуманной, чтобы помочь быстро разобраться в технологии глубокого обучения; мы будем двигаться от базовых принципов к нетривиальным особенностям с целью получить достойную производительность на двух наборах данных: MNIST (классификация рукописных цифр) и CIFAR-10 (классификация небольших изображений по десяти классам: самолет, автомобиль, птица, кошка, олень, собака, лягушка, лошадь, корабль и грузовик).



            Читать дальше →
            • +31
            • 78.3k
            • 5
          • Введение в машинное обучение с помощью Python и Scikit-Learn

            Привет, хабр!



            Меня зовут Александр, я занимаюсь машинным обучением и анализом веб-графов (в основном — теоретическим), а также разработкой Big Data продуктов в одном из операторов Большой Тройки. Это мой первый пост — прошу, не судите строго!)

            В последнее время ко мне все чаще стали обращаться люди, которые хотят научиться разрабатывать эффективные алгоритмы и участвовать в соревнованиях по машинному обучению с вопросом: «С чего начать?». Некоторое время назад я руководил разработкой инструментов Big Data для анализа медиа и социальных сетей в одном из учреждений Правительства РФ, и у меня остался некоторый материал, по которому обучалась моя команда и которым можно поделиться. Предполагается, что у читателя есть хорошее знание математики и машинного обучения (в команде были в основном выпускники МФТИ и студенты Школы Анализа Данных).
            Читать дальше →
          • TrustZone: аппаратная реализация в ARMv7A

              Сегодня начинаем исследовать внутреннее устройство TrustZone (это торговая марка компании ARM).

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

              Поэтому я начну с того, что TrustZone — это никакое не «место» в процессоре. Ее нельзя найти на чипе, как кеш или АЛУ. И доверенные программы, на самом деле, не исполняются в какой-то физически выделенной зоне процессора.

              Даже если мы посмотрели бы в исходные коды ядра ARM, то не смогли бы четко выделить TrustZone. Скорее, по аналогии с программами, TrustZone — это несколько модулей и набор патчей для почти всех остальных частей процессора.

              В этой статье мы рассмотрим, как TrustZone реализуется на аппаратном уровне процессоров ARM Cortex-A (ARMv7A).
              Читать дальше →
              • +24
              • 7.1k
              • 2
            • Готовим Physically Based Rendering + Image-based Lighting. Теория+практика. Шаг за шагом

                Хей, привет. 2017 год на дворе. Даже простенькие мобильные и браузерные приложения начинают потихоньку рисовать физически корректное освещение. Интернет пестрит кучей статей и готовых шейдеров. И кажется, что это должно быть так просто тоже обмазаться PBR… Или нет?

                В действительности же честный PBR сделать достаточно сложно, потому что легко достичь похожего результата, но сложно правильного. И в интернете полно статей, которые делают именно похожий результат, вместо правильного. Отделить мух от котлет в этом хаосе становится сложно.
                Поэтому цель статьи не только разобраться, что же такое PBR и как он работает, но и научиться писать его. Как отлаживать, куда смотреть, и какие ошибки типично можно допустить.
                Статья рассчитана на людей, которые в достаточной мере уже знают hlsl и неплохо знакомы с линейной алгеброй, и можете написать свой простейший неPBR Phong свет. В общем я постараюсь как можно проще объяснить, но рассчитываю на то, что некоторый опыт работы с шейдерами вы уже имеете.
                Читать дальше →
              • Попиксельная заливка экрана в Wolfenstein 3D

                • Translation
                В коде id Software порой встречаются бесподобные жемчужины. Самая знаменитая — это, конечно, 0x5f3759df, удостоившаяся даже комикса на xkcd. Здесь же речь пойдёт о заливке экрана: пиксели закрашиваются по одному в случайном порядке, без повторов. Как это сделано?

                Читать дальше →
              • «Магическая константа» 0x5f3759df

                • Translation
                В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

                Вот полная реализация этого алгоритма:

                float FastInvSqrt(float x) {
                  float xhalf = 0.5f * x;
                  int i = *(int*)&x;  // представим биты float в виде целого числа
                  i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
                  x = *(float*)&i;
                  x = x*(1.5f-(xhalf*x*x));
                  return x;
                }

                Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы

                image

                Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
                В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

                Да, понадобится немного математики, но школьного курса будет более, чем достаточно.
                Читать дальше →
              • 37 причин, почему ваша нейросеть не работает

                • Translation
                • Tutorial
                Сеть обучалась последние 12 часов. Всё выглядело хорошо: градиенты стабильные, функция потерь уменьшалась. Но потом пришёл результат: все нули, один фон, ничего не распознано. «Что я сделал не так?», — спросил я у компьютера, который промолчал в ответ.

                Почему нейросеть выдаёт мусор (например, среднее всех результатов или у неё реально слабая точность)? С чего начать проверку?

                Сеть может не обучаться по ряду причин. По итогу многих отладочных сессий я заметил, что часто делаю одни и те же проверки. Здесь я собрал в удобный список свой опыт вместе с лучшими идеями коллег. Надеюсь, этот список будет полезен и вам.
                Читать дальше →
              • Немного о проектировании самосинхронных схем

                • Tutorial
                На форумах по электронике периодически вспоминают о самосинхронных схемах, но очень мало кто понимает, что это вообще такое, какие полезные свойства есть у самосинхронных схем, и какими недостатками они обладают. Краткий текст ниже позволит читателю ознакомиться с азами синтеза простейших самосинхронных схем, и самому попробовать их проектировать.
                Читать дальше →
              • Второе почетное. Заметки участника конкурса Dstl Satellite Imagery Feature Detection



                  Недавно закончилось соревнование по машинному обучению Dstl Satellite Imagery Feature Detection в котором приняло участие аж трое сотрудников Avito. Я хочу поделиться опытом участия от своего лица и рассказать о решении.
                  Читать дальше →
                  • +58
                  • 12.9k
                  • 8
                • Custom floating point format on FPGA

                    Всем привет!

                    В данной статье речь пойдет о числах в формате с плавающей точкой и в частности о реализации специализированного формата FP23 на программируемых логических интегральных схемах (ПЛИС). В рамках конкретного проекта у меня родилась мысль реализовать оптимальный для определенных нужд формат данных с плавающей точкой. В итоге эта мысль переросла в реальный проект, который впоследствии нашел применение в некоторых интересных задачах цифровой обработки сигналов. В статье рассмотрены основные сложности при реализации формата данных floating point на ПЛИС Xilinx, рассмотрены базовые математические операции в формате FP23. Также в конце статьи вы можете найти исходный код проекта, которой можно свободно использовать в своих задачах или на его основе реализовать похожие форматы данных.


                    Читать дальше →
                  • Обзор исходного кода Quake 2

                    • Translation
                    image

                    Около месяца свободного времени я уделил чтению исходного кода Quake II. Это был удивительный и поучительный опыт, потому что в движок idTech3 внесено большое изменение: Quake 1, Quake World и QuakeGL объединены в одну красивую архитектуру кода. Особенно был интересен способ, которым достигли модульности, несмотря на то, что язык программирования C не обеспечивает полиморфизма.

                    Quake II во многих отношениях является блестящим образцом программного обеспечения, потому что это был самый популярный (по количеству лицензий) трёхмерный движок всех времён. На его основе было создано более 30 игр. Кроме того, он ознаменовал переход игровой индустрии от программной/8-битной системы цветов к аппаратной/24-битной. Этот переход произошёл примерно в 1997 году.

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

                    Процесс «подчистки» меня сильно увлёк: в статье теперь более 40 мегабайт видео, скриншотов и иллюстраций. Сейчас я не знаю, стоили ли мои труды того, и нужно ли публиковать в будущем необработанные заметки в ASCII, выскажите своё мнение.
                    Читать дальше →