- Сообщения
- 7,981
- Реакции
- 6,756
Цифровая обработка изображений — весьма интересная область, но она таит в себе множество подводных камней, на которые постоянно натыкаются новички. Мы активно привлекаем студентов к участию в грантах и проектах, но когда мы пытались давать студентам реальные задания, которые требуют реализации новых алгоритмов обработки изображений, мы были в ужасе от совершаемых ими детских ошибок.
Поэтому перед постановкой полноценных задач мы стали давать студентам ряд практических заданий по реализации стандартных алгоритмов обработки изображений: базовые операции над изображениями (поворот, размытие), свёртка, интерполяция с помощью простых фильтров (билинейная, бикубическая), направленная интерполяция, выделение границ с помощью алгоритма Канни, детектирование ключевых точек и т.д. Язык программирования мог быть любым, однако при выполнении заданий не допускается использование сторонних библиотек, за исключением чтения и записи изображений. Это связано с тем, что задания носят обучающий характер, самостоятельная реализация алгоритмов является хорошей практикой в программировании и позволяет понять, как работают методы изнутри.
Данная статья описывает наиболее частые ошибки, совершаемые студентами при выполнении практических заданий по обработке изображений. Изображения обычные, никакой экзотики типа 16-битной глубины цвета, панхроматичности и 3D-изображений нет.
Ошибка 1. Работа с пикселями, используя системные объекты Bitmap, HBITMAP и им подобные для хранения изображений
Данные объекты предназначены для взаимодействия с графической подсистемой (рисование примитивов и текста, вывод на экран) и не предоставляют возможности прямого доступа к участку памяти, в котором хранятся пиксели изображения. Доступ к пикселям осуществляется с помощью функций GetPixel и SetPixel. Вызов этих функций очень дорогой — на два-три порядка медленнее, чем прямой доступ к пикселям. Особенно велик соблазн так делать в C#, где тип Bitmap доступен «из коробки».
Решение: использовать данные классы только для чтения из файла, записи в файл и вывод на экран, в остальных случаях работать с классами, имеющими эффективный доступ к пикселям.
Замечание: в некоторых случаях в Windows удобно работать с DIB (device independent bitmap): есть и прямой доступ к пикселям, и возможность вывода на экран, минус — ограничение на тип пикселя.
Ошибка 2. Использование библиотек для работы с изображениями при отсутствии опыта обработки изображений
Использование библиотек чревато непониманием работы алгоритмов и дальнейшими трудностями при решении практических задач, требующих разработки собственных алгоритмов, которых нет в библиотеках. Я сталкивался с хорошо программирующими студентами, которые не могли реализовать даже элементарные операции типа свёртки: то не получалось подключить библиотеку, то работало не так, но на написание функции из 10 строчек ума уже не хватало.
Решение: не использовать сторонние библиотеки, а писать свои классы для работы с изображениями и самостоятельно реализовывать основные алгоритмы. Особенно полезно это для тех, кто не имеет достаточного опыта программирования. Лучше несколько раз сломать велосипед, чем завалить целый проект из-за глупых ошибок.
Ошибка 3. Потеря в точности при округлении
В результате применения различных алгоритмов обработки изображений возникают промежуточные результаты, имеющие вещественный тип. Пример: практически любой усредняющий фильтр, например, фильтр Гаусса. Приведение результатов к типу byte приводит к внесению дополнительной ошибки и менее точной работе алгоритмов.
Ниже приведён пример работы алгоритма детектировании контуров Канни, одним из составных частей которого является вычисление модуля градиента. Слева — модуль градиента после вычисления хранится в типе float, справа — округляется до byte.
Несложно заметить, что при округлении контуры становятся рваными.
Решение: используйте тип float вместо byte для хранения значений пикселей, не занимайтесь преждевременной оптимизацией — сначала добейтесь нормальной работы алгоритма на float, а затем уже думайте, где можно использовать byte так, чтобы не снизилось качество.
Замечание: скорость работы современных процессоров с вещественными числами сопоставима с целыми. В некоторых случаях компилятор может применить автоматическую векторизацию, что приведёт к более быстрому коду с float. Также код с float может получиться более быстрым при большом количестве преобразований byte-float, округлений и отсечений. А вот использование double редко бывает оправдано, а мешанина из float и double так вообще является следствием непонимания типов и принципов работы с ними.
Использование целочисленных типов (byte, int16, uint16) особенно эффективно при использовании векторных операций, когда скорость доступа к памяти становится узким местом.
Ошибка 4. Выход значений пикселей за пределы диапазона [0, 255]
У вас нет проблем с точностью и вы всё ещё хотите для хранения значений пикселей использовать тип byte? Тогда возникает ещё одна проблема: многие операции, например бикубическая интерполяция или повышение резкости, приводят к появлению значений, выходящих за пределы указанного диапазона. Если не учитывать этот факт, то возникает эффект, называемый wrapping: значение 260 превращается в 4, а –3 — в 253. Появляются яркие точки и линии на тёмном фоне и тёмные — на светлом (слева — правильная реализация, справа — с ошибкой).
Решение: при выполнении промежуточных операций проверяйте на каждом шаге диапазон возможных значений, а при преобразовании в байтовый тип обязательна проверка на выход за границы диапазона, например, так:
Ошибка 5. Потеря значений в результате приведения к диапазону [0, 255]
Вы упираетесь и по-прежнему отказываетесь от использования типа float и вызываете функцию clamp? А вы уверены, что ничего не теряете, как в случае с округлением?
Видел на практике, как студенты при вычислении производной или при применении фильтра Собеля таким образом теряли отрицательные значения.
Решение: используйте float для хранения промежуточных результатов, а функцию clamp только для сохранения в файл или вывода на экран. Для визуализации производной добавляйте 128 к значению пикселя, либо берите модуль.
Ошибка 6. Неправильный порядок обхода по пикселям изображения, приводящий к замедлению работы программы
Память в компьютере одномерна. Двумерные изображения хранятся в памяти в виде одномерных массивов. Обычно они записываются построчно: сначала идёт 0-я строка, затем 1-я и т.д.
Последовательный доступ к памяти осуществляется быстрее, чем произвольный. Это связано с работой кэша процессора, который помещает данные из памяти в кэш большими блоками, например, по 64 байта для современных процессоров. В этот блок попадают сразу несколько соседних по горизонтали пикселей. Значит, при обращении к последующим пикселям в той же строке скорость доступа будет выше, чем к последующим пикселям в столбце.
Решение: Обход по изображению нужно делать так, чтобы доступ к памяти был последовательный: во внешнем цикле производится обход по вертикали, а во внутреннем — по горизонтали:
Примечание: В разных языках способ представления многомерных массивов в памяти может быть различным. Имейте это в виду.
Ошибка 7. Путаница с шириной и высотой
Классическая проблема: тестирование либо отсутствует, либо осуществляется только на квадратных изображениях, в полевых условиях при работе с прямоугольными изображениями происходит выход за границу массива.
Решение: не забывайте про тестирование! Спор о TDD предлагаю не разводить: его использование — это личное дело каждого.
Ошибка 8. Отказ от абстракций
Боязнь плодить сущности — типичная ошибка новичков, она приводит к проблемам с читаемостью и восприятием кода. Здесь можно привести много примеров.
1. Обращение к пикселям через непосредственное вычисление индексов в массиве вместо использования методов getPixel(x, y) и setPixel(x, y). Помимо удобства, в этих методах можно проверять и корректно обрабатывать выход за границы изображения. Например, не выдавать ошибку, а эктраполировать значения изображения.
2. Дублирование кода при работе с цветными изображениями, приводящее к ошибкам (см. пример выше). Вместо copy-paste кода и замены r на g и на b достаточно было бы использовать перегрузку операторов. В три раза меньше кода, в три раза понятнее.
3. Использование двумерных массивов вместо создания отдельного класса для изображения.
Проблема заключается в том, что индексация получается неестественной — (y, x) вместо (x, y), а размерности массива не очевидны: непонятно, что из GetLength(0) и GetLength(1) есть ширина, а что — высота. Высок риск просто перепутать индексы.
4. Использование трёхмерных массивов для хранения цветных изображений вместо создания отдельного класса для изображения. В дополнение к предыдущему пункту, приходится помнить, какой из индексов соответствует какой цветовой компоненте. Также видел, как трёхмерные массивы используются для хранения векторов, как в виде (vx, vy), так и в виде (v, angle). Запутаться легко.
5. Использование массива вместо класса. Угадайте, что возвращает следующая функция?
Ответ: массив из 11 элементов, каждый из элементов имеет свой сакральный смысл, непонятный без длительного анализа кода. Не делайте так! Заведите класс и назовите каждое из полей по-человечески.
6. Переиспользование переменных с изменением семантики. Видите в коде gradx и grady и думаете, что это призводные по x и по y? А вот и нет, это модуль и угол:
Решение: никаких магических констант и индексов быть не должно. Оформляйте изображения как отдельные классы, сами пиксели тоже должны быть типизированы, а доступ к пикселям должен осуществляться только через специальные методы.
Ошибка 9. Применение некоторых математических функций неправильно или не к месту
Здесь виной всему слабое понимание архитектуры процессора, набора инструкций и времени их выполнения. Простительно, приходит с опытом, но некоторые моменты я отмечу:
1. Возведение в квадрат в виде Math.Pow(x, 2) или pow(x, 2) вместо x * x.
Компиляторы не оптимизируют эти конструкции, вместо однотактового умножения они генерируют довольно сложный код, включающий в себя вычисление экспоненты и логарифма, что приводит к снижению скорости на порядок-два.
2. Взятие целой части как (int)Math.Floor((float)(j) / k), причём k — вещественное и не меняется внутри цикла.
Здесь достаточно было бы написать (int)(j / k), а ещё лучше (int)(j * inv_k), где float inv_k = 1.0f / k.
Дело в том, что floor возвращает вещественное число, которое затем нужно дополнительно преобразовывать в целое. Получается лишняя довольно дорогая операция. Ну а замена деления на умножение — просто оптимизация, операция деления до сих пор дорогая.
3. Вычисление обратного значения.
Зачем так делать, когда можно написать _sum = 1.0 / sum?
Решение: применяйте математические функции только там, где они нужны.
Ошибка 10. Незнание языка
И опять проблемы с математикой:
1. Путаница с типами. Использование long long для индексов пикселей вместо int, постоянные преобразования между float, double и int. Например, зачем писать (float)(1.0 / 16), когда можно написать 1.0f / 16.0f?
2. Вычисление полярного угла через возню с atan и проблемой с делением на ноль вместо использования atan2, которая делает именно то, что надо.
3. Необычная экспонента и магические константы:
Здесь студент просто забыл про существование функции exp и константы pi. А вместо (float)1 можно просто написать 1.0f.
Решение: программируйте больше, только так вы наберётесь опыта.
Ошибка 11. Обфускация кода
Начинающие программисты любят показать своё мастерство, предпочитая писать короткий код, а не понятный.
1. Сложные циклы
Здесь правильно было бы сделать цикл от -1 до 1, а x1 и x2 вычислять уже внутри цикла, ну и порядок поменять:
Получилось бы даже быстрее за счёт того, что компиляторы легко оптимизируют простые циклы.
2. Крутые функции
А нормальные люди просто напишут
А это вообще за гранью добра и зла:
Для тех, кто не понял: ldexp(x, -1) — это просто деление на 2.
Решение: просто помните, что рано или поздно вам отобьют пальцы молотком за такой код.
Ошибка 12. Порча значений обрабатываемых изображений
Вот кусок кода из подавления немаксимумов, являющегося частью алгоритма Канни:
Здесь некоторые значения зануляются grad[x, y] = 0, а на последующих итерациях циклах к ним происходит обращение. Ошибка бы не произошла, если бы для вычисления промежуточного результата создавалось новое изображение, а не перезаписывалось текущее.
Решение: не стремитесь экономить память раньше времени, подумайте о функциональной парадигме.
Остальные ошибки
Остальные ошибки уже имеют непрограммистский характер. Это ошибки в реализации алгоритмов вследствие их непонимания, они индивидуальны. Например, неверный выбор размера ядра для фильтра Гаусса.
Фильтр Гаусса — один из основных фильтров в обработке изображений. Он лежит в основе огромного числа алгоритмов: детектирование контуров (edges) и хребтов (ridges), поиск ключевых точек, повышение резкости и т.д. Фильтр Гаусса имеет параметр «сигма», определяющий уровень размытия, его ядро описывается формулой:
а график имеет вид:
Данная функция нигде не обращается в ноль, а свёртка с ядром бесконечного размера не имеет смысла. Поэтому размер ядра выбирается таким, чтобы ошибка была ничтожно мала. Для практических задач достаточно взять ядро с радиусом (int)(3 * sigma) — ошибка будет меньше 1/1000. Выбор слишком маленького ядра (красная функция на графике выше) приведёт к искажению фильтра Гаусса. Использование ядра фиксированного размера, например, 5х5 и приводит к некорректным результатам уже при sigma = 1.5.
Итог: общие рекомендации для начинающих работать с изображениями
→ Visual Studio 2015, C++
→ Visual Studio 2015, C#
Версий под Linux нет — студенты, использующие Linux, обычно не испытывают проблем с такими вещами.
Ну и на закуску — просто картинки.
Выделение контуров с помощью алгоритма Канни. Слева вверху — входное изображение, второе слева — правильный результат, остальное — ошибочные результаты.
Увеличение с помощью бикубической интерполяции.
Источник
Поэтому перед постановкой полноценных задач мы стали давать студентам ряд практических заданий по реализации стандартных алгоритмов обработки изображений: базовые операции над изображениями (поворот, размытие), свёртка, интерполяция с помощью простых фильтров (билинейная, бикубическая), направленная интерполяция, выделение границ с помощью алгоритма Канни, детектирование ключевых точек и т.д. Язык программирования мог быть любым, однако при выполнении заданий не допускается использование сторонних библиотек, за исключением чтения и записи изображений. Это связано с тем, что задания носят обучающий характер, самостоятельная реализация алгоритмов является хорошей практикой в программировании и позволяет понять, как работают методы изнутри.
Данная статья описывает наиболее частые ошибки, совершаемые студентами при выполнении практических заданий по обработке изображений. Изображения обычные, никакой экзотики типа 16-битной глубины цвета, панхроматичности и 3D-изображений нет.
Ошибка 1. Работа с пикселями, используя системные объекты Bitmap, HBITMAP и им подобные для хранения изображений
Данные объекты предназначены для взаимодействия с графической подсистемой (рисование примитивов и текста, вывод на экран) и не предоставляют возможности прямого доступа к участку памяти, в котором хранятся пиксели изображения. Доступ к пикселям осуществляется с помощью функций GetPixel и SetPixel. Вызов этих функций очень дорогой — на два-три порядка медленнее, чем прямой доступ к пикселям. Особенно велик соблазн так делать в C#, где тип Bitmap доступен «из коробки».
Решение: использовать данные классы только для чтения из файла, записи в файл и вывод на экран, в остальных случаях работать с классами, имеющими эффективный доступ к пикселям.
Замечание: в некоторых случаях в Windows удобно работать с DIB (device independent bitmap): есть и прямой доступ к пикселям, и возможность вывода на экран, минус — ограничение на тип пикселя.
Ошибка 2. Использование библиотек для работы с изображениями при отсутствии опыта обработки изображений
Использование библиотек чревато непониманием работы алгоритмов и дальнейшими трудностями при решении практических задач, требующих разработки собственных алгоритмов, которых нет в библиотеках. Я сталкивался с хорошо программирующими студентами, которые не могли реализовать даже элементарные операции типа свёртки: то не получалось подключить библиотеку, то работало не так, но на написание функции из 10 строчек ума уже не хватало.
Решение: не использовать сторонние библиотеки, а писать свои классы для работы с изображениями и самостоятельно реализовывать основные алгоритмы. Особенно полезно это для тех, кто не имеет достаточного опыта программирования. Лучше несколько раз сломать велосипед, чем завалить целый проект из-за глупых ошибок.
Ошибка 3. Потеря в точности при округлении
В результате применения различных алгоритмов обработки изображений возникают промежуточные результаты, имеющие вещественный тип. Пример: практически любой усредняющий фильтр, например, фильтр Гаусса. Приведение результатов к типу byte приводит к внесению дополнительной ошибки и менее точной работе алгоритмов.
Ниже приведён пример работы алгоритма детектировании контуров Канни, одним из составных частей которого является вычисление модуля градиента. Слева — модуль градиента после вычисления хранится в типе float, справа — округляется до byte.
![86849e11eb134295af071890ffce8929.webp 86849e11eb134295af071890ffce8929.webp](https://www.safezone.cc/data/attachments/69/69763-10f4cc9a061fb012d65eb5f089af2a76.jpg?hash=DeuXImP_-6)
![d8bcaaa1fe974af6af33a3085745ba7d.webp d8bcaaa1fe974af6af33a3085745ba7d.webp](https://www.safezone.cc/data/attachments/69/69764-024a3f36501a2f309decda4768e1036f.jpg?hash=8DT_MMoO9V)
Несложно заметить, что при округлении контуры становятся рваными.
Решение: используйте тип float вместо byte для хранения значений пикселей, не занимайтесь преждевременной оптимизацией — сначала добейтесь нормальной работы алгоритма на float, а затем уже думайте, где можно использовать byte так, чтобы не снизилось качество.
Замечание: скорость работы современных процессоров с вещественными числами сопоставима с целыми. В некоторых случаях компилятор может применить автоматическую векторизацию, что приведёт к более быстрому коду с float. Также код с float может получиться более быстрым при большом количестве преобразований byte-float, округлений и отсечений. А вот использование double редко бывает оправдано, а мешанина из float и double так вообще является следствием непонимания типов и принципов работы с ними.
Использование целочисленных типов (byte, int16, uint16) особенно эффективно при использовании векторных операций, когда скорость доступа к памяти становится узким местом.
Ошибка 4. Выход значений пикселей за пределы диапазона [0, 255]
У вас нет проблем с точностью и вы всё ещё хотите для хранения значений пикселей использовать тип byte? Тогда возникает ещё одна проблема: многие операции, например бикубическая интерполяция или повышение резкости, приводят к появлению значений, выходящих за пределы указанного диапазона. Если не учитывать этот факт, то возникает эффект, называемый wrapping: значение 260 превращается в 4, а –3 — в 253. Появляются яркие точки и линии на тёмном фоне и тёмные — на светлом (слева — правильная реализация, справа — с ошибкой).
![20f3d60c3a394970a44fc40c3f246010.webp 20f3d60c3a394970a44fc40c3f246010.webp](https://www.safezone.cc/data/attachments/69/69765-23389f57cd242168c8382ba5464eb665.jpg?hash=LOeaBhhfPk)
![088e3ee2f0e34bb29708e3e2cc436f0d.webp 088e3ee2f0e34bb29708e3e2cc436f0d.webp](https://www.safezone.cc/data/attachments/69/69766-4ec3274444f8dd07282ef4279a1a9a6c.jpg?hash=lgcK0GkqPv)
Решение: при выполнении промежуточных операций проверяйте на каждом шаге диапазон возможных значений, а при преобразовании в байтовый тип обязательна проверка на выход за границы диапазона, например, так:
C++:
unsigned char clamp(float x)
{
return x < 0.0f ? 0 : (x > 255.0f ? 255 : (unsigned char)x);
}
Ошибка 5. Потеря значений в результате приведения к диапазону [0, 255]
Вы упираетесь и по-прежнему отказываетесь от использования типа float и вызываете функцию clamp? А вы уверены, что ничего не теряете, как в случае с округлением?
Видел на практике, как студенты при вычислении производной или при применении фильтра Собеля таким образом теряли отрицательные значения.
Решение: используйте float для хранения промежуточных результатов, а функцию clamp только для сохранения в файл или вывода на экран. Для визуализации производной добавляйте 128 к значению пикселя, либо берите модуль.
Ошибка 6. Неправильный порядок обхода по пикселям изображения, приводящий к замедлению работы программы
Память в компьютере одномерна. Двумерные изображения хранятся в памяти в виде одномерных массивов. Обычно они записываются построчно: сначала идёт 0-я строка, затем 1-я и т.д.
Последовательный доступ к памяти осуществляется быстрее, чем произвольный. Это связано с работой кэша процессора, который помещает данные из памяти в кэш большими блоками, например, по 64 байта для современных процессоров. В этот блок попадают сразу несколько соседних по горизонтали пикселей. Значит, при обращении к последующим пикселям в той же строке скорость доступа будет выше, чем к последующим пикселям в столбце.
Решение: Обход по изображению нужно делать так, чтобы доступ к памяти был последовательный: во внешнем цикле производится обход по вертикали, а во внутреннем — по горизонтали:
C++:
for (int y = 0; y < image.Height(); y++)
for (int x = 0; x < image.Width(); x++)
...
Ошибка 7. Путаница с шириной и высотой
Классическая проблема: тестирование либо отсутствует, либо осуществляется только на квадратных изображениях, в полевых условиях при работе с прямоугольными изображениями происходит выход за границу массива.
Решение: не забывайте про тестирование! Спор о TDD предлагаю не разводить: его использование — это личное дело каждого.
Ошибка 8. Отказ от абстракций
Боязнь плодить сущности — типичная ошибка новичков, она приводит к проблемам с читаемостью и восприятием кода. Здесь можно привести много примеров.
1. Обращение к пикселям через непосредственное вычисление индексов в массиве вместо использования методов getPixel(x, y) и setPixel(x, y). Помимо удобства, в этих методах можно проверять и корректно обрабатывать выход за границы изображения. Например, не выдавать ошибку, а эктраполировать значения изображения.
C++:
b1 = (float)0.25 * ( w1 - 1) * (w1 - 2) * (w1 + 1) * (h1 - 1) * (h1 - 2) * (h1 + 1);
b2 = -(float)0.25 * w1 * (w1 + 1) * (w1 - 2) * (h1 - 1) * (h1 - 2) * (h1 + 1);
b3 = -(float)0.25 * (w1 - 1) * (w1 - 2) * (w1 + 1) * (h1 + 1) * (h1 - 2);
b4 = (float)0.25 * w1 * h1 * (w1 + 1) * (w1 - 2) * (h1 + 1) * (h1 - 2);
b5 = -(1 / 12) * w1 * (w1 - 1) * (w1 - 2) * (h1 - 1) * (h1 - 2) * (h1 + 1);
b6 = -(1 / 12) * h1 * (w1- 1) * (w1 - 2) * (w1 + 1) * (h1 - 1) * (h1 - 2);
b7 = (1 / 12) * w1 * h1 * (w1 + 1) * (w1 - 2) * (h1 + 1) * (h1 - 2);
b8 = (1 / 12) * w1 * h1 * (w1- 1) * (w1 - 2) * (h1 - 1) *( h1 - 2);
b9 = (1 / 12) * w1 * (w1 - 1) * (w1 + 1) * (h1 - 1) * (h1 - 2) * (h1 + 1);
b10 = (1 / 12) * w1 * (w1 - 1) * (w1 - 2) * (w1 + 1) * (h1 - 1) * (h1+ 1);
b11 = (1 / 36) * w1 * h1 * (w1 - 1) * (w1 - 2) * (w1 - 1) * (h1 - 2) * (h1- 2);
b12 = -(1 / 12) * w1 * h1 * (w1 - 1) * (w1 + 1) * (h1 + 1) * (h1 - 2);
b13 = -(1 / 12) * w1 * h1 * (w1 + 1) * (w1 - 2) * (h1 - 1) * (h1 + 1);
b14 = -(1 / 36) * w1 * (w1 - 1) * (w1 + 1) * (h1 - 1) * (h1 - 2);
b15 = -(1 / 36) * w1 * h1 * (w1 - 1) * (w1 - 2) * (h1 - 1) * (h1 + 1);
b16 = (1 / 36) * w1 * h1 * (w1 - 1) * (w1 + 1) * (h1 - 1) * (h1 + 1);
image2.rawdata[y1 * image2.Width + x1].b =
image1.rawdata[h * image1.Width + w].b * b1
+ image1.rawdata[h * image1.Width + w + 1].b * b2
+ image1.rawdata[(h + 1) * image1.Width + w].b * b3
+ image1.rawdata[(h + 1) * image1.Width + w + 1].b * b4
+ image1.rawdata[h * image1.Width + w - 1].b * b5
+ image1.rawdata[(h - 1) * image1.Width + w].b * b6
+ image1.rawdata[(h + 1) * image1.Width + w - 1].b * b7
+ image1.rawdata[(h - 1) * image1.Width + w + 1].b * b8
+ image1.rawdata[h * image.Width + w + 2].b * b9
+ image1.rawdata[(h + 2) * image1.Width + w].b * b10
+ image1.rawdata[(h - 1) * image1.Width + w - 1].b * b11
+ image1.rawdata[(h + 1) * image1.Width + w + 2].b * b12
+ image1.rawdata[(h + 2) * image1.Width + w + 1].b * b13
+ image1.rawdata[(h - 1) * image1.Width + w + 2].b * b14
+ image1.rawdata[(h + 2) * image1.Width + w - 1].b * b15
+ image1.rawdata[(h + 2) * image1.Width + w + 2].b * b16;
image2.rawdata[y1 * image2.Width + x1].g =
image1.rawdata[h * image1.Width + w].g * b1
+ image1.rawdata[h * image1.Width + w + 1].g * b2
+ image1.rawdata[(h + 1) * image1.Width + w].g * b3
+ image1.rawdata[(h + 1) * image1.Width + w + 1].g * b4
+ image1.rawdata[h * image1.Width + w - 1].g * b5
+ image1.rawdata[(h - 1) * image1.Width + w].g * b6
+ image1.rawdata[(h + 1) * image1.Width + w - 1].g * b7
+ image1.rawdata[(h - 1) * image1.Width + w + 1].g * b8
+ image1.rawdata[h * image1.Width + w + 2].g * b9
+ image1.rawdata[(h + 2) * image1.Width + w].g * b10
+ image1.rawdata[(h - 1) * image1.Width + w - 1].g * b11
+ image1.rawdata[(h + 1) * image1.Width + w + 2].g * b12
+ image1.rawdata[(h + 2) * image1.Width + w + 1].g * b13
+ image1.rawdata[(h - 1) * image1.Width + w + 2].g * b14
+ image1.rawdata[(h + 2) * image1.Width + w - 1].g * b15
+ image1.rawdata[(h + 2) * image1.Width + w + 2].g * b16;
image2.rawdata[y1 * image2.Width + x1].r =
image1.rawdata[h * image1.Width + w].r * b1
+ image1.rawdata[h * image1.Width + w + 1].r * b2
+ image1.rawdata[(h + 1) * image1.Width + w].r * b3
+ image1.rawdata[(h + 1) * image1.Width + w + 1].r * b4
+ image1.rawdata[h * image1.Width + w - 1].r * b5
+ image1.rawdata[(h - 1) * image1.Width + w].r * b6
+ image1.rawdata[(h + 1) * image1.Width + w - 1].r * b7
+ image1.rawdata[(h - 1) * image1.Width + w + 1].r * b8
+ image1.rawdata[h * image1.Width + w + 2].r * b9
+ image1.rawdata[(h + 2) * image1.Width + w].r * b10
+ image1.rawdata[(h - 1) * image1.Width + w - 1].r * b11
+ image1.rawdata[(h + 1) * image1.Width + w + 2].r * b12
+ image1.rawdata[(h + 2) * image1.Width + w + 1].r * b13
+ image1.rawdata[(h - 1) * image1.Width + w + 2].r * b14
+ image1.rawdata[(h + 2) * image1.Width + w - 1].r * b15
+ image1.rawdata[(h + 2) * image1.Width + w + 2].r * b16;
2. Дублирование кода при работе с цветными изображениями, приводящее к ошибкам (см. пример выше). Вместо copy-paste кода и замены r на g и на b достаточно было бы использовать перегрузку операторов. В три раза меньше кода, в три раза понятнее.
3. Использование двумерных массивов вместо создания отдельного класса для изображения.
Проблема заключается в том, что индексация получается неестественной — (y, x) вместо (x, y), а размерности массива не очевидны: непонятно, что из GetLength(0) и GetLength(1) есть ширина, а что — высота. Высок риск просто перепутать индексы.
4. Использование трёхмерных массивов для хранения цветных изображений вместо создания отдельного класса для изображения. В дополнение к предыдущему пункту, приходится помнить, какой из индексов соответствует какой цветовой компоненте. Также видел, как трёхмерные массивы используются для хранения векторов, как в виде (vx, vy), так и в виде (v, angle). Запутаться легко.
5. Использование массива вместо класса. Угадайте, что возвращает следующая функция?
C++:
public static double[] HoughTransform2(GrayscaleFloatImage image, ref float[][] direction, ColorFloatImage cimage)
6. Переиспользование переменных с изменением семантики. Видите в коде gradx и grady и думаете, что это призводные по x и по y? А вот и нет, это модуль и угол:
C++:
gradx[x, y] = (float)Math.Sqrt(temp1 * temp1 + temp2 * temp2);
grady[x, y] = (float)(Math.Abs(Math.Atan2(temp2, temp1)) * 180 / Math.PI);
Ошибка 9. Применение некоторых математических функций неправильно или не к месту
Здесь виной всему слабое понимание архитектуры процессора, набора инструкций и времени их выполнения. Простительно, приходит с опытом, но некоторые моменты я отмечу:
1. Возведение в квадрат в виде Math.Pow(x, 2) или pow(x, 2) вместо x * x.
Компиляторы не оптимизируют эти конструкции, вместо однотактового умножения они генерируют довольно сложный код, включающий в себя вычисление экспоненты и логарифма, что приводит к снижению скорости на порядок-два.
Вызов pow(x, y) разворачивается в exp(log(x) * y). Это занимает около 300 тактов при использовании команд x87. В SSE же экспоненты и логарифма до сих пор нет, существует множество реализаций exp и log с различной производительностью, например, вот. В лучшем случае возведение в степень займёт 30-50 тактов. На умножение же уйдёт всего один такт.
2. Взятие целой части как (int)Math.Floor((float)(j) / k), причём k — вещественное и не меняется внутри цикла.
Здесь достаточно было бы написать (int)(j / k), а ещё лучше (int)(j * inv_k), где float inv_k = 1.0f / k.
Дело в том, что floor возвращает вещественное число, которое затем нужно дополнительно преобразовывать в целое. Получается лишняя довольно дорогая операция. Ну а замена деления на умножение — просто оптимизация, операция деления до сих пор дорогая.
(int)floor(x) и (int)x зквивалентны только при неотрицательных x. Функция floor всегда округляет вниз, тогда как (int)x — в сторону нуля.
3. Вычисление обратного значения.
C++:
double _sum = pow(sum, -1);
Решение: применяйте математические функции только там, где они нужны.
Ошибка 10. Незнание языка
И опять проблемы с математикой:
1. Путаница с типами. Использование long long для индексов пикселей вместо int, постоянные преобразования между float, double и int. Например, зачем писать (float)(1.0 / 16), когда можно написать 1.0f / 16.0f?
2. Вычисление полярного угла через возню с atan и проблемой с делением на ноль вместо использования atan2, которая делает именно то, что надо.
3. Необычная экспонента и магические константы:
C++:
g=(float)Math.pow(2.71,-(d*d)/(2*sigma*sigma));
t=((float)1/((float)Math.sqrt(6.28)*sigma));
Решение: программируйте больше, только так вы наберётесь опыта.
Ошибка 11. Обфускация кода
Начинающие программисты любят показать своё мастерство, предпочитая писать короткий код, а не понятный.
1. Сложные циклы
C++:
for (int x1 = x - 1, x2 = 0; x1 <= x + 1; x1++, x2++)
{
for (int y1 = y - 1, y2 = 0; y1 <= y + 1; y1++, y2++)
{
C++:
for (int j = -1; j <= 1; j++)
{
int y1 = y + j, y2 = j + 1;
for (int i = -1; i <= 1; i++)
{
int x1 = x + i, x2 = i + 1;
2. Крутые функции
C++:
long long ksize = llround(fma(ceil(3 * sigma), 2, 1)), rad = ksize >> 1;
C++:
int rad = (int)(3.0f * sigma);
int ksize = 2 * rad + 1;
C++:
kernel[idx] = exp(ldexp(-pow(_sigma * (rad - idx), 2), -1));
Решение: просто помните, что рано или поздно вам отобьют пальцы молотком за такой код.
Ошибка 12. Порча значений обрабатываемых изображений
Вот кусок кода из подавления немаксимумов, являющегося частью алгоритма Канни:
C++:
for x in xrange(grad.shape[0]):
for y in xrange(grad.shape[1]):
if ((angle[x, y] == 0) and ((grad[x, y] <= grad[getinds(grad, x + 1, y)])
or (grad[x, y] <= grad[getinds(grad, x - 1, y)]))) or\
((angle[x, y] == 0.25) and ((grad[x, y] <= grad[getinds(grad, x + 1, y + 1)])
or (grad[x, y] <= grad[getinds(grad, x - 1, y - 1)]))) or\
((angle[x, y] == 0.5) and ((grad[x, y] <= grad[getinds(grad, x, y + 1)])
or (grad[x, y] <= grad[getinds(grad, x, y - 1)]))) or\
((angle[x, y] == 0.75) and ((grad[x, y] <= grad[getinds(grad, x + 1, y - 1)])
or (grad[x, y] <= grad[getinds(grad, x - 1, y + 1)]))):
grad[x, y] = 0
Решение: не стремитесь экономить память раньше времени, подумайте о функциональной парадигме.
Остальные ошибки
Остальные ошибки уже имеют непрограммистский характер. Это ошибки в реализации алгоритмов вследствие их непонимания, они индивидуальны. Например, неверный выбор размера ядра для фильтра Гаусса.
Фильтр Гаусса — один из основных фильтров в обработке изображений. Он лежит в основе огромного числа алгоритмов: детектирование контуров (edges) и хребтов (ridges), поиск ключевых точек, повышение резкости и т.д. Фильтр Гаусса имеет параметр «сигма», определяющий уровень размытия, его ядро описывается формулой:
![37a50647cecb44639ac624f406ff77f1.webp 37a50647cecb44639ac624f406ff77f1.webp](https://www.safezone.cc/data/attachments/69/69767-2d20079899929dd6ba562ce75c01706f.jpg?hash=VKXkFkjAdk)
а график имеет вид:
![a63550268b2f432eac608dc44a66e72c.webp a63550268b2f432eac608dc44a66e72c.webp](https://www.safezone.cc/data/attachments/69/69768-689b3fe9cac9d5c2064f5bb658e2de57.jpg?hash=49GJ-TdkHH)
Данная функция нигде не обращается в ноль, а свёртка с ядром бесконечного размера не имеет смысла. Поэтому размер ядра выбирается таким, чтобы ошибка была ничтожно мала. Для практических задач достаточно взять ядро с радиусом (int)(3 * sigma) — ошибка будет меньше 1/1000. Выбор слишком маленького ядра (красная функция на графике выше) приведёт к искажению фильтра Гаусса. Использование ядра фиксированного размера, например, 5х5 и приводит к некорректным результатам уже при sigma = 1.5.
Итог: общие рекомендации для начинающих работать с изображениями
- Не используйте системные объекты Bitmap, HBITMAP и им подобные.
- Прежде, чем использовать библиотеки для работы с изображениями, начните с написания велосипедов, а уже затем бросайтесь в бой.
- Используйте тип float для хранения значений пикселей. Не занимайтесь преждевременной оптимизацией по скорости и памяти, заменяя float на byte.
- При преобразовании из float в byte помните об ошибках округления и выход за границы типа.
- Помните об отрицательных значениях.
- Совершайте обход по пикселям изображения в правильном порядке.
- Тщательно тестируйте код.
- Не бойтесь плодить сущности. Код должен быть понятным.
- Используйте математические операции с умом.
- Учите язык.
- Не пытайтесь показать мастерство.
- Читайте учебники по обработке изображений — там много всего полезного пишут.
→ Visual Studio 2015, C++
→ Visual Studio 2015, C#
Версий под Linux нет — студенты, использующие Linux, обычно не испытывают проблем с такими вещами.
Ну и на закуску — просто картинки.
Выделение контуров с помощью алгоритма Канни. Слева вверху — входное изображение, второе слева — правильный результат, остальное — ошибочные результаты.
![4dda6a1fa65347c58da707e4f1c97fed.webp 4dda6a1fa65347c58da707e4f1c97fed.webp](https://www.safezone.cc/data/attachments/69/69769-4d52a02719a72ddd62b4cfa899275b83.jpg?hash=q5Gh-wMv2m)
![7d993420e9f84cefb4f6d63143f5505c.webp 7d993420e9f84cefb4f6d63143f5505c.webp](https://www.safezone.cc/data/attachments/69/69770-50ff2a832898ff0a936b61ad05b43f2e.jpg?hash=iYH065c_tA)
![84191ce8dcb54cfeb024ec8b8f98a34a.webp 84191ce8dcb54cfeb024ec8b8f98a34a.webp](https://www.safezone.cc/data/attachments/69/69771-7641450fb82f76801ef90ef3f169ced3.jpg?hash=510eomXYrR)
![bbe83050c4d84833b531d109a931f1b2.webp bbe83050c4d84833b531d109a931f1b2.webp](https://www.safezone.cc/data/attachments/69/69772-9e60aec16eb820a8da29695ce0491a8d.jpg?hash=0vF9aUbJp8)
![d24485205a394d54a021fad73d3aba71.webp d24485205a394d54a021fad73d3aba71.webp](https://www.safezone.cc/data/attachments/69/69773-94d3372d2fcca8b714d38bbcb508edf5.jpg?hash=SF-egNenNx)
![a434395522284b3f92666bcc18dfb893.webp a434395522284b3f92666bcc18dfb893.webp](https://www.safezone.cc/data/attachments/69/69774-80df5a1d40f6a876618d9f4db62529f9.jpg?hash=A8HagPoUR8)
![5649819545914187803a6a0540f9dff2.webp 5649819545914187803a6a0540f9dff2.webp](https://www.safezone.cc/data/attachments/69/69775-4058a78c999ed5dd99f1a2d2a34dd745.jpg?hash=aiUmDbAxs6)
![7b58f31caa6641c5ab8de667dee8359d.webp 7b58f31caa6641c5ab8de667dee8359d.webp](https://www.safezone.cc/data/attachments/69/69776-dfd5018629aab2e6264246917acde378.jpg?hash=dvdXUS7F1n)
![bd0814a2782c4c43be7dc1b86f0f3806.webp bd0814a2782c4c43be7dc1b86f0f3806.webp](https://www.safezone.cc/data/attachments/69/69777-d495eb1c7486a0508b334f4130d8dc74.jpg?hash=UZI53M0NCM)
![53b0a6e175724723b13cdc0bf0f5acc9.webp 53b0a6e175724723b13cdc0bf0f5acc9.webp](https://www.safezone.cc/data/attachments/69/69778-910e48d09fae12d5ce6bdbcb707ce99c.jpg?hash=qyGSq-giRY)
Увеличение с помощью бикубической интерполяции.
![0f82d72f2dc44b19bddc7792f4737993.webp 0f82d72f2dc44b19bddc7792f4737993.webp](https://www.safezone.cc/data/attachments/69/69779-90e95f3ed76667e70f621feb56b645ae.jpg?hash=5h65lZQCHC)
![1bdc3a23763a4feabe388c8fd680aec7.webp 1bdc3a23763a4feabe388c8fd680aec7.webp](https://www.safezone.cc/data/attachments/69/69780-b4c2f33de82cf21f90893b3668e92441.jpg?hash=q4bVKU4VBi)
![9eabaa29c4ff4b2bb46dff8f5bec3144.webp 9eabaa29c4ff4b2bb46dff8f5bec3144.webp](https://www.safezone.cc/data/attachments/69/69781-d2dcbc25316bb6d36e6bbba7ebbc2dcc.jpg?hash=HEk_Iyhzpf)
![c2165b91016a446bac73d0e747a9c5bb.webp c2165b91016a446bac73d0e747a9c5bb.webp](https://www.safezone.cc/data/attachments/69/69782-fa1f7d6b67f14b8470001d5c118125e0.jpg?hash=iw2dFaLA_o)
![5a99db0f9b2a4abca607a08a26b8f4b4.webp 5a99db0f9b2a4abca607a08a26b8f4b4.webp](https://www.safezone.cc/data/attachments/69/69783-ab8d85b263cfb0256f6bac766f99e4b4.jpg?hash=r82PmVIOvl)
Источник