• Обзор алгоритмов сегментации


      Этим летом мне посчастливилось попасть на летнюю стажировку в компанию Itseez. Мне было предложено исследовать современные методы, которые позволили бы выделить местоположения объектов на изображении. В основном такие методы опираются на сегментацию, поэтому я начала свою работу со знакомства с этой областью компьютерного зрения.
      Сегментация изображения — это разбиение изображения на множество покрывающих его областей. Сегментация применяется во многих областях, например, в производстве для индикации дефектов при сборке деталей, в медицине для первичной обработки снимков, также для составления карт местности по снимкам со спутников. Для тех, кому интересно разобраться, как работают такие алгоритмы, добро пожаловать под кат. Мы рассмотрим несколько методов из библиотеки компьютерного зрения OpenCV.
      Читать дальше →
    • Кто жмёт лучше, или Уолш против Фурье

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

      Для начала хочу поблагодарить автора статей «Декодирование JPEG для чайников» и «Изобретаем JPEG», которые очень помогли мне в работе по написанию данной публикации. Когда я занялся вопросами изучения алгоритмов сжатия изображений с потерями, то в части алгоритма JPEG меня всё время мучил вопрос: «Почему роль базисного преобразования в алгоритме JPEG отведена именно частному случаю преобразования Фурье?». Здесь автор даёт ответ на этот вопрос, но я решил подойти к нему не с точки зрения теории, математических моделей или программной реализации, а с точки зрения схемотехники.

      Алгоритм сжатия изображений JPEG является алгоритмом цифровой обработки сигналов, которые, аппаратно, как правило, реализуются либо на цифровых сигнальных процессорах, либо на программируемых логических интегральных схемах. В моём случае, выбор для работы цифрового сигнального процессора означал бы приход к тому, от чего я пытался уйти — к программной реализации, поэтому решено было остановиться на программируемой логике.
      Читать дальше →
      • +48
      • 20.6k
      • 1
    • «Выглядит похоже». Как работает перцептивный хэш

      • Translation
      За последние несколько месяцев несколько человек спросили меня, как работает TinEye и как в принципе работает поиск похожих картинок.

      По правде говоря, я не знаю, как работает поисковик TinEye. Он не раскрывает деталей используемого алгоритма(-ов). Но глядя на поисковую выдачу, я могу сделать вывод о работе какой-то формы перцептивного хэш-алгоритма.
      Читать дальше →
    • Эквализация гистограмм для повышения качества изображений

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

          Привет всем. Я уже однажды писал про Distance Field и приводил реализацию «эвристическим» кодом, дающую неплохую скорость: «Честный glow и скорость».

          Зачем он нужен?


          DField можно применять:
          • Для значительного повышения качества шрифтов
          • Для эффектов например горения контура. Один из эффектов я приводил в своей предыдущей статье
          • Для эффекта «metaballs» но в 2д и для любых сложных шейпов. (возможно я когда-нибудь приведу пример реализации этого эффекта)
          • А в данный момент DField мне нужен для качественного сглаживания углов и удаления мелких деталей.

          И если в первых двух случаях мы можем заранее вычислить DField, то для других эффектов нам нужно просчитывать его в реальном времени.
          В статье будет рассмотрен наиболее популярный, я бы сказал классический Chamfer distance (CDA) с кучей картинок, объясняющих принцип его работы, а так же рассмотрен двухпроходный алгоритм на GPU.
          Оба алгоритма реализованы в демонстрационных программах на FPC.
          Читать дальше →
        • Бездисковая загрузка по технологии iSCSI на базе ОС Windows

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

          Предпосылкой к изучению данного вопроса стало наличие в сети компьютера, с вышедшем из строя дисковым накопителем. Необходимо было запустить на данном ПК «полноценную» 64-битную операционную систему Windows 7 без использования Linux-сервера, ограничившись только имеющимися в локальной сети Windows системами. Приводимые в данном посте программные продукты распространяются бесплатно и могут работать как на серверных, так и на пользовательских версиях Windows.

          Разговор пойдет о замечательной технологии iSCSI, и как мы её можем использовать для загрузки по локальной сети, чтобы сэкономить на стоимости покупки нового дискового оборудования. Постараюсь описать весь процесс конфигурирования наиболее доступным языком как для начинающих администраторов, так и для непросвещенных пользователей.
          Читать дальше →
        • Ликбез: методы ресайза изображений

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

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


            Этот человек сидит среди ромашек, чтобы привлечь ваше внимание к статье.
            Читать дальше →
          • GifCam — анимированный скриншот в два клика

            Не знаю как у вас, а у меня необходимость сделать анимированный скриншот иногда появляется. Например, чтобы передать как выглядит анимированное изображение на странице сайта. Или, чтобы доказать, что добавить анимацию в принципе возможно, например, в ленту новостей группы на mail.ru (считается, что анимация там не добавляется).
            Читать дальше →
          • Мгновенный поиск файлов в Windows. Ловкость рук и никакого мошенничества

              Если в Windows XP поиск файлов был хоть и медленным, но все-таки работоспособным, то в Windows 7 он превратился во что-то совсем непонятное. Многие успешно пользуются поиском в Far'е или Total Commander'е вместо стандартных средств Windows. Когда на дисках очень много файлов, такой поиск также выполняется медленно. Я бы вряд ли поверил, если бы не попробовал сам, что файлы можно находить мгновенно (!), прямо во время ввода имени файла в строку поиска. Заинтересовались?

              Читать дальше →
            • Повышение визуального качества для фотографий документов

                В последнее время пользователи все чаще получают изображения документов при помощи фотокамер или мобильных устройств, прибегая к помощи сканера изредка, в особых случаях. В то же время, для изображений, получаемых фотокамерами, характерны следующие недостатки: геометрические искажения (о них мы говорили в статье про автоматическое выделение документа), неравномерность освещения (часто можно видеть тени или засветки при использовании вспышки), падение контраста, расфокусировка, смаз, цифровой шум при недостаточном освещении. Постараемся избавиться от этих недостатков, применяя некоторые преобразования к исходному изображению, чтобы приблизить его вид к отсканированному.
                Читать дальше →
              • Signed Distance Field или как сделать из растра вектор

                  Речь сегодня пойдёт о генерации изображений с картой расстояний (Signed Distance Field). Данный вид изображений примечателен тем, что фактически позволяет получить «векторную» графику на видеоускорителе, причём даром. Одной из первых данный метод растеризации предложила компания Valve в игре Team Fortress 2 для масштабируемых декалей в 2007 году, но до сих пор он не пользуется особой популярностью, хотя позволяет рендерить прекрасного качества шрифты, используя текстуру всего 256х256 точек. Данный метод прекрасно подходит для современных экранов высокой чёткости и позволяет серьёзно сэкономить на текстурах в играх, он не требователен к железу и прекрасно работает на смартфонах.



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

                  Как же создавать такие изображения? Очень просто, ImageMagick позволяет сделать это одной командой:

                  convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png
                  

                  На этом можно было бы поставить точку, но так полноценного топика не получится. Что ж, под катом — описание быстрого алгоритма расчёта SDF, пример на C++ и немного шейдеров для OpenGL.
                  Читать дальше →
                • Об особенностях реализации префиксного энтропийного кодирования для больших алфавитов

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

                      В этой статье хочу поделиться интересной историей, о необычном решении одной интересной задачи, которая попалась мне год назад. Всё описанное в статье делалось, прежде всего, «just for fun» и из чистого академического интереса…
                      Дело было год назад, как раз было свободное время и желание сделать что-нибудь полезное. Явно был некоторый интеллектуальный голод и острая нехватка чего-нибудь нового, какой-нибудь интересной задачи… Отсюда и попытки прилепить велосипед даже туда, куда он вообще не требовался… Собственно, таковым велосипедом и является всё нижеописанное…

                      1. Задача


                      На одном торгово-закупочном предприятии, достаточно остро стоял вопрос оптимизации закупок. У предприятия было несколько десятков основных поставщиков, но при этом у многих поставщиков пересечение товаров достигало 20-30%, а цены у всех разные. К сожалению, большинство товаров закупалось «по старой памяти», например привыкли, что товары группы A поставляет поставщик X, а товары группы Б поставщик Y, хотя если отбирать товары не группами, а штучно, то можно не слабо экономить. Для наглядности, покажу на примере:
                      Читать дальше →
                    • Изобретаем JPEG

                      • Tutorial

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

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

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

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

                        image

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



                        Я обнаружил этот фрактал, когда разглядывал интерференцию волн на поверхности речки. Волна движется к берегу, отражается и накладывается сама на себя. Есть ли порядок в тех узорах, которые создаются волнами? Попробуем найти его. Рассмотрим не всю волну, а только вектор ее движения. «Берега» сделаем гладкими, для простоты эксперимента.

                        Эксперимент можно провести на обычном листке в клеточку из школьной тетради.
                        Читать дальше →
                      • Сглаживание цифровых сигналов

                        Введение


                        Данную статью меня заставил написать пост habrahabr.ru/post/183986, где не совсем правильно используется некоторый алгоритм сглаживания изображения.

                        Сразу перейдём к сути дела.

                        Математические модели цифровых сигналов — вектора и матрицы, элементами которых являются числа. Числа могут быть двоичными (бинарный сигнал), десятичными («обычный» сигнал) и так далее. Любой звук, любое изображение и видео могут быть преобразованы в цифровой сигнал1: звук — в вектор, изображение — в матрицу, а видео — в последовательный набор матриц. Поэтому цифровой сигнал — это, можно сказать, универсальный объект для представления информации.

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

                        Задача сглаживания может использоваться при прореживании сигналов, то есть когда, например, необходимо отобразить большую картинку на небольшой экран. Или когда частота дискретизации звука снижается, например, с 48000 Гц до 44100 Гц. Понижение частоты выборок — коварная операция, требующая предварительной обработки сигнала (низкочастотной фильтрации), но это — тема отдельного разговора…

                        Приведём пример «плохого» сглаживания


                        Казалось бы, обычное усреднение и сигнал на выходе должен быть «гладким». Но как определить, насколько он стал «глаже»? Не переборщили ли мы? А может быть некоторые коэффициенты выбрать не по 1/3? А может быть усреднить по пяти точкам? Как определить насколько ослабляются частотные составляющие в сигнале? Как найти свой (то есть для конкретной задачи) оптимум?
                        На эти и некоторые другие вопросы я постараюсь ответить так, чтобы «обычный» программист смог обосновать свой алгоритм, — надеюсь, не только алгоритм на тему «Сглаживание», так как идеи будут излагаться весьма общие, заставляющие думать самому
                        Читать дальше →