В статьях подобная задача обсуждается последние лет 20. Рекомендую поискать по ключевым словам «near duplicate detection» and (image or photo). Замечу, что во многих статьях начальные этапы обработки часто совпадают с предлагаемыми в посте. Считаю, что стоит поздравить автора: он свой «велосипед» изобретает в правильном направлении.
Однако, подробно обсуждать предлагаемое решение я не вижу смысла, так как задача не поставлена более-менее чётко. О какого рода изображениях идет речь? Согласен с первым комментарием, что не существует универсальных подходов. Упоминаемые в комментария выше статьи про matching прекрасно работают для обычных бытовых фото, но попробуйте их применить для мэтчинга регулярных текстур или, например, изображений слоёв травления в микроэлектронике. По моему опыту они не работают.
Что значит «похожие»? Согласитесь (или посмотрите в существующих статьях), что формулировка может быть достаточно разной.
Сколько изображений всего уже сейчас или ожидается когда-либо?
Как Вы собираетесь считать точность и какого уровня рассчитываете достичь?
Сколько времени Вы можете себе позволить заниматься разработкой, реализацией и тестированием алгоритма?
Без ответа на хотя бы часть из этих вопросов маловероятно ожидать конструктивного обсуждения предлагаемого подхода. Хотя ссылок «а вот посмотрите еще сюда» «а вот посмотрите еще сюда», накидают, что, конечно, тоже полезно.
Нет, это аддитивная модель, цвета складываются. Модель применяют для экранов. Сложение R, G и B максимальной интенсивности дают на экране белый цвет.
«Правило вычитания» работает в субтрактивных моделях, например, CMY.
Материал интересный. Спасибо за перевод! Давайте его немного улучшим.
Область схемы цветности, ограниченная треугольником, созданным основными цветами заданной системы отображения, называется гаммой.
В оригинале видимо «gamut». На русский язык обычно переводят как «локус» или транслитерируют как «гамут», но не «гамма». На хабре был хороший подробный материал на эту тему.
Хорошо бы также расшифровать ряд аббревиатур, например, SDR (Standard Dynamic Range) и HDR (High Dynamic Range). Неспециалистам может быть непонятно.
CIE — Commission Internationale de l'Éclairage, в русскоязычной литературе МКО — Международная комиссия по освещению.
Поддерживаю предыдущего оратора. Нужен критерий качества сегментации. Как минимум, это картинка с желаемым результатом. Лучше ещё и численный показатель качества сегментации. Несколько таких метрик можно найти, например, в статье.
только один учёный из 1000 может придумать что-то действительно полезное. Но именно ради одного этого учёного и приходится содержать остальных, потому что дело тут даже не в способностях, а в случае.
Ну, я надеюсь, Вы или Ваши коллеги попадут в этот 0.1% и мы увидим пост «Как мы опубликовали статью в Nature» или, хотя бы, в IEEE Transactions on Image Processing.
Ну так как я работаю в университете, курс читается тоже в университете, то и цели преследую научные, а не инженерные.
Пардон, а все Ваши студенты после университета будут учёными. Вы курс для себя или для студентов читаете?
Поэтому разработкой и оптимизацией алгоритмов обычно занимаются разные люди.
В каком-то идеальном мире это так. Но я 15 лет работаю в Research подразделениях известных компаний и знаю буквально единичные примеры успешной оптимизации алгоритмов «другими людьми». Гораздо чаще ситуация такая: или алгоритм идет в корзину, или идет в production без изменений и оптимизации, или разработчик алгоритма сам оптимизирует код.
Прошу прощения за критику, но как-то это мало, чтобы называться исследованием. Замечаний очень много. Вот несколько:
1. Несмотря на то, что эти методы действительно можно считать более-менее известными, хорошо бы привести ссылки на статьи или ресурсы, где указано, о каком алгоритме в действительности идет речь.
2. У этих алгоритмов есть параметры. Какие использовались у Вас?
3. От конкретной реализации зависит работа того или иного метода. Вы сами их рtализовали или использовали готовые библиотеки? Какие? На каком языке?
4. Наконец, в тексте сначала написано «Метод выращивания регионов обеспечивает локализацию сегментов на изображениях объекта». Несколько строк ниже: «Метод выращивания регионов не обеспечивает локализацию сегментов».
обеспечивает локализацию элементов дорожно-транспортной инфраструктуры
Выше я написал: OK — это нормально.
Если дальше развивать мысль «уменьшить время разработки, пусть и ценой более высокого потребления памяти и медленной работы», то имеет смысл переходить на скриптовые языки Python, Matlab, etc…
Вы этого в своем курсе не делаете, т.к. ставите цель научить писать обработку изображений на C++/C#, в том числе «глобальные задачи». Я ставлю цель научить программировать (с элементами оптимизации) на С/С++ отдельные базовые функции обработки изображений. О «глобальных задачах» речь не идет.
Вы всегда рекомендуете использовать float для хранения пикселей. Я не рекомендую этого делать без необходимости, т.е. когда уже нельзя или сложно обойтись целочисленными типами без значительной потери точности.
Из немного разных целей курсов следуют немного разные рекомендации. Ваши, в целом правильные, рекомендации в разделе «Итог» апостулируются как абсолютно истинные для любого студента, изучающего обработку изображений, а это не совсем так.
Спасибо за очень подробные и более чем показательные результаты скорости обработки!
Здесь реализован метод размытия изображения с окном 3х3. В целом byte получается чуть быстрее float.
Возьмем ядро свертки / окно больше, и преимущество byte получится значительнее.
Вы считаете, что следует учить студентов избегать возможных ошибок, связанных с переполнением и потерей точности, путем использования float. При этом больше внимания уделяете чему-то другому. OK, нормальная понятная позиция.
Я считаю, что надо дать студентам в процессе обучения возможность делать такого рода ошибки, чтобы указать на них, чтобы научиться понимать их причину и сознательно устранять. Давайте согласимся, что такая позиция также имеет право на существование.
Спасибо! Важную тему подняли. Более 15 лет преподаю студентам обработку изображений. В принципе, согласен с перечисленными типичными ошибками и почти всеми рекомендациями. Однако, я призываю студентов отказываться от вычислений во float/double везде, где это целесообразно. Иначе у студентов укореняется привычка использовать только float, а до оптимизации дело никогда не доходит. Наоборот, развивается боязнь оптимизации. Преждевременная оптимизация это часто вредно, но и отсутствие умения оптимизировать тоже не хорошо.
скорость работы современных процессоров с вещественными числами такая же быстрая, как и с целыми
студентами хорошо бы понимать, что современные процессоры бывают очень разные. Бывают DSP, бывают для embedded. Для них картина может быть не такой радужной. К тому же справедливо замечено, что узким местом является обращение к памяти, а unsigned char, как не крути, в четыре раза меньше чем float.
Лишь немногие студенты догадались, что бикубическая интерполяция сепарабельна
Строго говоря, не сепарабельна, а реализуется с помощью 5 одномерных интерполяций cubic convolution. Подобный приведенному в посте код я тоже видел много раз. Это потому, что в Википедии в статье про бикубическую интерполяцию написаны такие формулы. Согласен с предложением, написанным выше, может помочь делать посты с «правильным» описанием даже таких простых алгоритмов.
Спасибо за продукт и статью! К сожалению, сейчас мало пишу на С++, но но пару раз использовал trial PVS-Studio, было очень полезно, особенно при переносе с 32 на 64bit.
Еще в постах очень рисунки стильные. Кто автор, если не секрет?
Что касается symbolic execution. У вас свой engine или сторонний? Какие ограничения? Как с path explosion боретесь?
Поскольку это блиц-интервью со мной, то позволю себе ответить на вопросы :-)
1) Закончил МИФИ в 1994 году, защитил диссертацию в 1997. Сейчас считаю, что все университетские курсы, даже бесполезные с практической точки зрения, научили меня учиться. На младших курсах большое впечатление на меня произвели лабораторные работы по физике, на старших — учебно-исследовательская работа и диплом, где решались практические задачи, а часть результатов реально использовалось на производстве.
2) для Win: Far manager, MS Office, Visual C++, Python (Anaconda), IrfanView.
3) Поучиться «впрок» для своего удовольствия не удаётся, нет времени. Кроме того, теория без практики плохо держится в голове. Учусь тому, что важно для текущего проекта.
4) Много раз был на собеседованиях с обеих сторон. Не люблю это мероприятие, видимо, поэтому любимых вопросов нет.
5) Мне нравится то, чем я занимаюсь. Надеюсь, каких-то глобальных изменений в роде деятельности не произойдет, а за это время удастся сделать несколько интересных проектов.
6) a) На ZeroNights вместе с Александром Матросовым представлял проект по системе для автоматического поиска уязвимостей в BIOS https://2016.zeronights.ru/wp-content/uploads/2016/12/1_3_Excite_Project_ZN.pdf
b) На конференции МЭС-2016 рассказывал о части проекта по реализации операций линейной алгебры на DSP: href=«http://www.mes-conference.ru/data/year2016/pdf/D197.pdf
c) В Nokia занимался распознаванием типов физической активности человека по сигналам сенсоров мобильных устройств. Если поискать, то можно найти мои статьи и патенты по этой теме.
Для начинающих работу с OpenMP написано хорошо и доступно. Тем не менее, есть несколько замечаний и пожеланий.
1. Поскольку речь идет о программе повышения квалификации, то участвовать в ней могут люди с разным background. Например, я довольно много использовал OpenMP для задач обработки изображений на PC и немного программировал одноядерные DSP. У меня возникло довольно много вопросов.
a) Мне было бы интересно понять особенности OpenMP на TMS320C66x по сравнению с реализации OpenMP в компиляторах Intel и Microsoft для PC. Есть ли отличия и в чем?
b) Сила DSP в SIMD инструкциях. Видимо в статье предполагается, что SIMD-векторизация появляется в результате работы компилятора. Однако бывают задачи, когда авто-векторизация компилятором работает недостаточно хорошо и приходится писать intrinsics и/или встроенный ассемблер. Как такой подход сочетается с OpenMP, нет ли особенностей и ограничений?
c) При использовании С++ нет необходимости явно указывать private для переменных объявленных внутри параллельной секции. Все остальные переменные автоматически shared, если не указано иное в #pragma. Для TMS320C66x также?
2. Ошибка с sum, которую Вы приводите в статье, является типичным примером ошибки типа «гонки данных» (race conditions). Новички часто делают подобные ошибки, а обнаружить их бывает не просто. Хорошо бы заострить на этом внимание. Когда я показывал студентам такого рода ошибки в их коде, у большинства тутже возникал соблазн все переменные объявлять shared. Почему так не стоит делать лучше показать на замерах времени работы. Вообще, мне кажется, что графики со временем работы для разных примеров сделали бы статью гораздо лучше.
3. В тексте говорится про «версии OpenMP разработанные TI». Не понял, как это соотносится с версиями стандарта OpenMP? Кстати, если я ничего не путаю, сейчас есть 4-я версия стандарта.
4. Совершенно правильно отмечено, что не стоит распаралеливать «короткие» циклы, так как есть накладные расходы на создание потоков. Где и как искать оптимум? Обещана отдельная статья. OK. Буду ждать.
5. Если честно, то я не увидел ориентации примеров на задачи ЦОС. Размер кода линейного КИХ фильтра (свертка) не сильно отличается от скалярного произведения. Вообще, такой процессор очень хорош для обработки изображений и видео.
Отлично написано и про Allstate соревнование, и про разницу в machine learning / data science для индустрии, академической науки и «спорта»!
А область пересечения всех трех областей намеренно оставили такой маленькой или это случайно получилось? Что сейчас, на Ваш взгляд, есть бщее в machine learning для науки, индустрии и соревновательных платформ?
Добавлю, что в индустрии часто есть ограничения на сложность и размер модели. В частности, приходилось делать несколько machine learning проектов для embedded / мобильных платформ c очень жёсткими ограничениями для итоговой модели (вычисления на микроконтроллере без floating point и объемом памяти для модели в несколько десятков kB).
Однако, подробно обсуждать предлагаемое решение я не вижу смысла, так как задача не поставлена более-менее чётко. О какого рода изображениях идет речь? Согласен с первым комментарием, что не существует универсальных подходов. Упоминаемые в комментария выше статьи про matching прекрасно работают для обычных бытовых фото, но попробуйте их применить для мэтчинга регулярных текстур или, например, изображений слоёв травления в микроэлектронике. По моему опыту они не работают.
Что значит «похожие»? Согласитесь (или посмотрите в существующих статьях), что формулировка может быть достаточно разной.
Сколько изображений всего уже сейчас или ожидается когда-либо?
Как Вы собираетесь считать точность и какого уровня рассчитываете достичь?
Сколько времени Вы можете себе позволить заниматься разработкой, реализацией и тестированием алгоритма?
Без ответа на хотя бы часть из этих вопросов маловероятно ожидать конструктивного обсуждения предлагаемого подхода. Хотя ссылок «а вот посмотрите еще сюда» «а вот посмотрите еще сюда», накидают, что, конечно, тоже полезно.
«Правило вычитания» работает в субтрактивных моделях, например, CMY.
В оригинале видимо «gamut». На русский язык обычно переводят как «локус» или транслитерируют как «гамут», но не «гамма». На хабре был хороший подробный материал на эту тему.
Хорошо бы также расшифровать ряд аббревиатур, например, SDR (Standard Dynamic Range) и HDR (High Dynamic Range). Неспециалистам может быть непонятно.
CIE — Commission Internationale de l'Éclairage, в русскоязычной литературе МКО — Международная комиссия по освещению.
Ну, я надеюсь, Вы или Ваши коллеги попадут в этот 0.1% и мы увидим пост «Как мы опубликовали статью в Nature» или, хотя бы, в IEEE Transactions on Image Processing.
В каком-то идеальном мире это так. Но я 15 лет работаю в Research подразделениях известных компаний и знаю буквально единичные примеры успешной оптимизации алгоритмов «другими людьми». Гораздо чаще ситуация такая: или алгоритм идет в корзину, или идет в production без изменений и оптимизации, или разработчик алгоритма сам оптимизирует код.
1. Несмотря на то, что эти методы действительно можно считать более-менее известными, хорошо бы привести ссылки на статьи или ресурсы, где указано, о каком алгоритме в действительности идет речь.
2. У этих алгоритмов есть параметры. Какие использовались у Вас?
3. От конкретной реализации зависит работа того или иного метода. Вы сами их рtализовали или использовали готовые библиотеки? Какие? На каком языке?
4. Наконец, в тексте сначала написано «Метод выращивания регионов обеспечивает локализацию сегментов на изображениях объекта». Несколько строк ниже: «Метод выращивания регионов не обеспечивает локализацию сегментов». А это какое отношение к посту имеет?
Если дальше развивать мысль «уменьшить время разработки, пусть и ценой более высокого потребления памяти и медленной работы», то имеет смысл переходить на скриптовые языки Python, Matlab, etc…
Вы этого в своем курсе не делаете, т.к. ставите цель научить писать обработку изображений на C++/C#, в том числе «глобальные задачи». Я ставлю цель научить программировать (с элементами оптимизации) на С/С++ отдельные базовые функции обработки изображений. О «глобальных задачах» речь не идет.
Вы всегда рекомендуете использовать float для хранения пикселей. Я не рекомендую этого делать без необходимости, т.е. когда уже нельзя или сложно обойтись целочисленными типами без значительной потери точности.
Из немного разных целей курсов следуют немного разные рекомендации. Ваши, в целом правильные, рекомендации в разделе «Итог» апостулируются как абсолютно истинные для любого студента, изучающего обработку изображений, а это не совсем так.
Возьмем ядро свертки / окно больше, и преимущество byte получится значительнее.
Вы считаете, что следует учить студентов избегать возможных ошибок, связанных с переполнением и потерей точности, путем использования float. При этом больше внимания уделяете чему-то другому. OK, нормальная понятная позиция.
Я считаю, что надо дать студентам в процессе обучения возможность делать такого рода ошибки, чтобы указать на них, чтобы научиться понимать их причину и сознательно устранять. Давайте согласимся, что такая позиция также имеет право на существование.
Можете пример показать с замерами времени для release с включенной оптимизацией? Что-то сомневаюсь я в правильности данного утверждения.
студентами хорошо бы понимать, что современные процессоры бывают очень разные. Бывают DSP, бывают для embedded. Для них картина может быть не такой радужной. К тому же справедливо замечено, что узким местом является обращение к памяти, а unsigned char, как не крути, в четыре раза меньше чем float. Строго говоря, не сепарабельна, а реализуется с помощью 5 одномерных интерполяций cubic convolution. Подобный приведенному в посте код я тоже видел много раз. Это потому, что в Википедии в статье про бикубическую интерполяцию написаны такие формулы. Согласен с предложением, написанным выше, может помочь делать посты с «правильным» описанием даже таких простых алгоритмов.
Смотрите, например, здесь
или здесь.
Еще в постах очень рисунки стильные. Кто автор, если не секрет?
Что касается symbolic execution. У вас свой engine или сторонний? Какие ограничения? Как с path explosion боретесь?
1) Закончил МИФИ в 1994 году, защитил диссертацию в 1997. Сейчас считаю, что все университетские курсы, даже бесполезные с практической точки зрения, научили меня учиться. На младших курсах большое впечатление на меня произвели лабораторные работы по физике, на старших — учебно-исследовательская работа и диплом, где решались практические задачи, а часть результатов реально использовалось на производстве.
2) для Win: Far manager, MS Office, Visual C++, Python (Anaconda), IrfanView.
3) Поучиться «впрок» для своего удовольствия не удаётся, нет времени. Кроме того, теория без практики плохо держится в голове. Учусь тому, что важно для текущего проекта.
4) Много раз был на собеседованиях с обеих сторон. Не люблю это мероприятие, видимо, поэтому любимых вопросов нет.
5) Мне нравится то, чем я занимаюсь. Надеюсь, каких-то глобальных изменений в роде деятельности не произойдет, а за это время удастся сделать несколько интересных проектов.
6) a) На ZeroNights вместе с Александром Матросовым представлял проект по системе для автоматического поиска уязвимостей в BIOS https://2016.zeronights.ru/wp-content/uploads/2016/12/1_3_Excite_Project_ZN.pdf
b) На конференции МЭС-2016 рассказывал о части проекта по реализации операций линейной алгебры на DSP: href=«http://www.mes-conference.ru/data/year2016/pdf/D197.pdf
c) В Nokia занимался распознаванием типов физической активности человека по сигналам сенсоров мобильных устройств. Если поискать, то можно найти мои статьи и патенты по этой теме.
1. Поскольку речь идет о программе повышения квалификации, то участвовать в ней могут люди с разным background. Например, я довольно много использовал OpenMP для задач обработки изображений на PC и немного программировал одноядерные DSP. У меня возникло довольно много вопросов.
a) Мне было бы интересно понять особенности OpenMP на TMS320C66x по сравнению с реализации OpenMP в компиляторах Intel и Microsoft для PC. Есть ли отличия и в чем?
b) Сила DSP в SIMD инструкциях. Видимо в статье предполагается, что SIMD-векторизация появляется в результате работы компилятора. Однако бывают задачи, когда авто-векторизация компилятором работает недостаточно хорошо и приходится писать intrinsics и/или встроенный ассемблер. Как такой подход сочетается с OpenMP, нет ли особенностей и ограничений?
c) При использовании С++ нет необходимости явно указывать private для переменных объявленных внутри параллельной секции. Все остальные переменные автоматически shared, если не указано иное в #pragma. Для TMS320C66x также?
2. Ошибка с sum, которую Вы приводите в статье, является типичным примером ошибки типа «гонки данных» (race conditions). Новички часто делают подобные ошибки, а обнаружить их бывает не просто. Хорошо бы заострить на этом внимание. Когда я показывал студентам такого рода ошибки в их коде, у большинства тутже возникал соблазн все переменные объявлять shared. Почему так не стоит делать лучше показать на замерах времени работы. Вообще, мне кажется, что графики со временем работы для разных примеров сделали бы статью гораздо лучше.
3. В тексте говорится про «версии OpenMP разработанные TI». Не понял, как это соотносится с версиями стандарта OpenMP? Кстати, если я ничего не путаю, сейчас есть 4-я версия стандарта.
4. Совершенно правильно отмечено, что не стоит распаралеливать «короткие» циклы, так как есть накладные расходы на создание потоков. Где и как искать оптимум? Обещана отдельная статья. OK. Буду ждать.
5. Если честно, то я не увидел ориентации примеров на задачи ЦОС. Размер кода линейного КИХ фильтра (свертка) не сильно отличается от скалярного произведения. Вообще, такой процессор очень хорош для обработки изображений и видео.
А область пересечения всех трех областей намеренно оставили такой маленькой или это случайно получилось? Что сейчас, на Ваш взгляд, есть бщее в machine learning для науки, индустрии и соревновательных платформ?
Добавлю, что в индустрии часто есть ограничения на сложность и размер модели. В частности, приходилось делать несколько machine learning проектов для embedded / мобильных платформ c очень жёсткими ограничениями для итоговой модели (вычисления на микроконтроллере без floating point и объемом памяти для модели в несколько десятков kB).