Как происходит распознавание образов в мозге человека? Этот вопрос давно волнует ученых, поскольку человеческий мозг обладает потрясающей способностью распознавать образы. Хотя этот вопрос и далек от разрешения, ясно, что мозг использует самые разнообразные признаки предмета, такие как цвет, размер, форма, характер текстуры, сочетая их между собой.
Среди вышеперечисленных признаков форма предмета является, возможно, наиболее существенной для распознавания.Мы способны распознать изображение человека, дома, кошки, дерева, - как в жизни, так и на черно-белой фотографии, на детском рисунке, на схематичном абрисе в виде нескольких проведенных линий и т. п. Цвет, размер, характер текстуры будут при этом меняться практически неограниченно, и именно некоторая инвариантность формы позволяет распознавать предмет во всех этих случаях.
Как найти предметы той или иной формы на изображении? Для этого надо ответить на вопрос, как форма предмета отображается на изображении. Как правило, актуальная граница предмета на фотографии отображается сильным перепадом яркости ( границей на изображении, далее просто границей ) между двумя сравнительно однотонными областями. Здесь могут быть и исключения (фотография черной кошки в черной комнате или ежика в тумане). Обратное верно в еще меньшей степени: сильный перепад яркости может быть вызван также текстурой предмета, тенями, бликами, перепадами освещенности, соответствующими граням предмета.
Несмотря на то, что между актуальными границами предметов и границами на изображении нет строгого соответствия, знание о том, где на изображении находятся границы, несомненно весьма полезно для распознавания образов и прочих задач компьютерного зрения. В этой лекции мы рассматриваем нахождение границ на изображениях.
Рассмотрим поиск границ на однотонном изображении A, с интенсивностями пикселей A(x, y). В каждом пикселе (x, y) рассмотрим вектор градиента $$\nabla(x, y) = \left( {\frac{\partial A}{\partial x}}, {\frac{\partial A}{\partial y}} \right) $$ (производные вычислим при помощи линейной фильтрации, как описано в разделе 8.2). Как видно на рис. 9.1, в точках большого перепада яркости градиент имеет большую длину. Это неудивительно, поскольку (частные) производные по определению соответствуют скоростям изменения функции (яркости) по вертикали и горизонтали. Взяв пиксели с соответствующей длиной градиента, большей порога $$\alpha $$, мы получим некий алгоритм нахождения границ.
Недостаток алгоритма выявляется сразу при взгляде на рис. 9.1: какое бы значение $$\alpha $$ мы ни взяли, мы неминуемо пропустим важные границы (спина бурундука) и/или включим в число границ несущественные (волоски на мордочке). Если же мы имеем дело с зашумленным изображением, то карту граничных точек будут загрязнять не только реально существующие, но несущественные детали, но и просто шум. Так произойдет, поскольку в нашем алгоритме мы не учли, что граничные точки соответствуют не просто перепадам яркости, а перепадам яркости между относительно монотонными областями.
Как отделить подобные перепады яркости от перепадов яркости, вызванных шумами и несущественными деталями? Для этого изображение подвергают сглаживающей гауссовской фильтрации (см. раздел 8.2). Такое решение проблемы, на первый взгляд, парадоксально - для нахождения границ мы их cначала размываем. Данный прием основывается на том, что при сглаживающей фильтрации мелкие несущественные детали будут размываться существенно быстрее перепадов между областями.
(рис 9.1)
(рис 9.2) Нахождение границ, исходя из длины градиента после сглаживающей фильтрации. 2 верхних рисунка - исходное изображение после гауссовской фильтрации и длина градиента в каждой точке. Нижний- пороговая фильтрация длины градиентаКак видно на рис. 9.2, такой подход действительно дает существенно лучшие результаты. В результате, к примеру, выделены граничные точки на спине и не выделены волоски на шкурке. Однако мы видим, что сильнее проявил себя другой недостаток алгоритма: четко выраженные границы проявились как жирные линии в несколько пикселей толщиной. К тому же неопределенность с выбором порога $$\alpha $$ не преодолена: результат на рис. 9.2 получен при помощи подбора значения $$\alpha $$ вручную, и, очевидно, такое значение оптимально не для всех частей изображения.
(рис 9.3) Нахождение границ при помощи подавления немаксимумов. Вверху - карта максимальных пикселей. Внизу - результат после пороговой фильтрации максимальных пикселей.Будучи двухмерным вектором, градиент яркости в каждой точке характеризуется длиной и направлением. До сих пор при поиске граничных точек мы использовали только длину вектора. Проблемы, которые при этом возникли, а именно неопределенность порога $$\alpha $$ и утолщение линий, можно во многом решить, опираясь на направление градиента.
Направление градиента есть направление максимального возрастания функции. На этом основана процедура подавления немаксимумов. При этой процедуре для каждой точки рассматривается отрезок длиной в несколько пикселей, ориентированный по направлению градиента и с центром в рассматриваемом пикселе. Пиксель считается максимальным тогда и только тогда, когда длина градиента в нем максимальна среди всех длин градиентов пикселей отрезка. Граничными можно признать все максимальные пиксели с длинами градиента больше некоего порога (рис. 9.3).
Градиент яркости в каждой точке перпендикулярен границе, поэтому после подавления немаксимумов жирных линий не остается: на каждом перпендикулярном сечении жирной линии останется один пиксель с максимальной длиной градиента.
Перпендикулярность градиента яркости к границе может быть использована для прослеживания границы, начиная с некоторого граничного пикселя. Такое прослеживание используется в гистерезисной фильтрации максимальных пикселей. При проведении гистерезисной фильтрации вводят не одно, а два пороговых значения. Меньшее ($$\alpha $$), как и раньше, соответствует минимальной длине градиента, при которой пиксель может быть признан граничным. Большее ($$\beta $$), соответствует минимальной длине градиента, при которой пиксель может инициализировать
контур. После того как контур инициализируется в максимальном пикселе P с длиной градиента, большей $$\beta $$, рассматриваются каждый соседний с ним максимальный пиксель Q. Если пиксель Q имеет длину градиента, большую $$\alpha $$, и угол между векторами - $$\overrightarrow{PQ}$$ и $$\nabla (P)$$ близок к $$90^{\circ}$$, то Q добавляется к контуру, и процесс рекурсивно переходит к Q. Идея гистерезисной фильтрации заключается в том, что длинный устойчивый граничный контур, скорее всего, содержит в себе пиксели с особенно большим перепадом яркости, и, начиная с такого пикселя, контур можно проследить, переходя по граничным пикселям с меньшим перепадом яркости.
Таким образом, описаный нами алгоритм нахождения границ на основе градиента заключается в последовательном применении следующих операций:
Этот алгоритм носит названия алгоритма Кэнни (Canny) [18]. Его результат показан на рис. 9.4. Алгоритм Кэнни является наиболее часто применяемым на сегодняшний день алгоритмом нахождения границ.
(рис 9.4) Алгоритм Кэнни. Вверху- исходное изображение. Внизу- результат алгоритма.
Одним из ключевых элементов алгоритма Кэнни является подавление немаксимумов, которая основана на том, что граница должна проходить через максимум градиента на данном направлении. Эта идея становится интуитивно ясной при рассмотрении функции одной переменной: точка с экстремальным значением первой производной соответствует максимально быстрому перепаду значений.
Однако, как известно из математического анализа, необходимым и достаточным условием экстремального значения первой производной функции в некой точке является равенство нулю второй производной в этой точке, причем по разные стороны от точки вторая производная должна иметь разные знаки. Про такую точку говорят, что вторая производная в ней пересекает ноль.
В двумерном случае, который нас и интересует, аналогом первой производной является вектор градиента $$\nabla f = \left( {\frac{\partial f}{\partial x}}, {\frac{\partial f}{\partial y}} \right) $$, а аналогом второй производной является скалярный оператор, называемый лапласианом $${\nabla ^2} f =\Delta f = \left( {\frac{{\partial ^2} f}{\partial x^2}} + {\frac{{\partial ^2} f}{\partial y^2}} \right) $$. Приближение лапласиана при помощи линейной фильтрации рассматривалось нами в разделе 8.2. Приведенная аналогия подтверждается и на рис. 8.5 - на нем видно, как лапласиан меняет знак при переходе через границы объектов.
Нахождение границ на изображении может, таким образом, производиться по аналогии с одномерным случаем: граничными признаются точки, в которых лапласиан равен нулю и вокруг которых он имеет разные знаки. Кроме того, оценка лапласиана при помощи линейной фильтрации предваряется гауссовской сглаживающей фильтрацией, чтобы снизить чувствительность алгоритма к шуму (аналогично тому, как это описано в разделе 9.2).
Несложно видеть (см. определение линейных фильтров в разделе 8.2), что композиция линейных фильтров есть линейный фильтр. Поэтому гауссовское сглаживание и поиск лапласиана можно осуществить единовременно при помощи фильтра, который
называется лапласиан гауссиана (рис. 9.5). Поиск пересечений нуля, так же, как и линейная фильтрация, является сравнительно быстрой операцией, поэтому нахождение границ при помощи лапласиана гауссиана производится гораздо быстрее, чем при помощи алгоритма Кэнни. Исходя из этого, описанный выше алгоритм применяется в системах, где принципиально и качество результата (которое обычно уступает алгоритму Кэнни), и быстродействие.
Чтобы еще уменьшить чувствительность алгоритма к несущественным деталям, из числа граничных точек можно исключить те, длина градиента в которых меньше порога (рис. 9.5). Для одномерного случая это будет соответствовать разумному требованию того, чтобы в точке перепада величина первой производной была не слишком маленькой.
(рис 9.5) Нахождение границ при помощи лапласиана гауссиана. Первый рисунок- исходное изображение. Второй - результат фильтрации с фильтром лапласиан гауссиана. Третий - точки пересечения нуля. Четвертый - пороговая фильтрация точек пересечения нуля по длине градиента. Как происходит распознавание образов в мозге человека? Этот вопрос давно волнует ученых, поскольку человеческий мозг обладает потрясающей способностью распознавать образы. Хотя этот вопрос и далек от разрешения, ясно, что мозг использует самые разнообразные признаки предмета, такие как цвет, размер, форма, характер текстуры, сочетая их между собой.
Среди вышеперечисленных признаков форма предмета является, возможно, наиболее существенной для распознавания.Мы способны распознать изображение человека, дома, кошки, дерева, - как в жизни, так и на черно-белой фотографии, на детском рисунке, на схематичном абрисе в виде нескольких проведенных линий и т. п. Цвет, размер, характер текстуры будут при этом меняться практически неограниченно, и именно некоторая инвариантность формы позволяет распознавать предмет во всех этих случаях.
Как найти предметы той или иной формы на изображении? Для этого надо ответить на вопрос, как форма предмета отображается на изображении. Как правило, актуальная граница предмета на фотографии отображается сильным перепадом яркости ( границей на изображении, далее просто границей ) между двумя сравнительно однотонными областями. Здесь могут быть и исключения (фотография черной кошки в черной комнате или ежика в тумане). Обратное верно в еще меньшей степени: сильный перепад яркости может быть вызван также текстурой предмета, тенями, бликами, перепадами освещенности, соответствующими граням предмета.
Несмотря на то, что между актуальными границами предметов и границами на изображении нет строгого соответствия, знание о том, где на изображении находятся границы, несомненно весьма полезно для распознавания образов и прочих задач компьютерного зрения. В этой лекции мы рассматриваем нахождение границ на изображениях.
Рассмотрим поиск границ на однотонном изображении A, с интенсивностями пикселей A(x, y). В каждом пикселе (x, y) рассмотрим вектор градиента $$\nabla(x, y) = \left( {\frac{\partial A}{\partial x}}, {\frac{\partial A}{\partial y}} \right) $$ (производные вычислим при помощи линейной фильтрации, как описано в разделе 8.2). Как видно на рис. 9.1, в точках большого перепада яркости градиент имеет большую длину. Это неудивительно, поскольку (частные) производные по определению соответствуют скоростям изменения функции (яркости) по вертикали и горизонтали. Взяв пиксели с соответствующей длиной градиента, большей порога $$\alpha $$, мы получим некий алгоритм нахождения границ.
Недостаток алгоритма выявляется сразу при взгляде на рис. 9.1: какое бы значение $$\alpha $$ мы ни взяли, мы неминуемо пропустим важные границы (спина бурундука) и/или включим в число границ несущественные (волоски на мордочке). Если же мы имеем дело с зашумленным изображением, то карту граничных точек будут загрязнять не только реально существующие, но несущественные детали, но и просто шум. Так произойдет, поскольку в нашем алгоритме мы не учли, что граничные точки соответствуют не просто перепадам яркости, а перепадам яркости между относительно монотонными областями.
Как отделить подобные перепады яркости от перепадов яркости, вызванных шумами и несущественными деталями? Для этого изображение подвергают сглаживающей гауссовской фильтрации (см. раздел 8.2). Такое решение проблемы, на первый взгляд, парадоксально - для нахождения границ мы их cначала размываем. Данный прием основывается на том, что при сглаживающей фильтрации мелкие несущественные детали будут размываться существенно быстрее перепадов между областями.
(рис 9.1)
(рис 9.2) Нахождение границ, исходя из длины градиента после сглаживающей фильтрации. 2 верхних рисунка - исходное изображение после гауссовской фильтрации и длина градиента в каждой точке. Нижний- пороговая фильтрация длины градиентаКак видно на рис. 9.2, такой подход действительно дает существенно лучшие результаты. В результате, к примеру, выделены граничные точки на спине и не выделены волоски на шкурке. Однако мы видим, что сильнее проявил себя другой недостаток алгоритма: четко выраженные границы проявились как жирные линии в несколько пикселей толщиной. К тому же неопределенность с выбором порога $$\alpha $$ не преодолена: результат на рис. 9.2 получен при помощи подбора значения $$\alpha $$ вручную, и, очевидно, такое значение оптимально не для всех частей изображения.
(рис 9.3) Нахождение границ при помощи подавления немаксимумов. Вверху - карта максимальных пикселей. Внизу - результат после пороговой фильтрации максимальных пикселей.Будучи двухмерным вектором, градиент яркости в каждой точке характеризуется длиной и направлением. До сих пор при поиске граничных точек мы использовали только длину вектора. Проблемы, которые при этом возникли, а именно неопределенность порога $$\alpha $$ и утолщение линий, можно во многом решить, опираясь на направление градиента.
Направление градиента есть направление максимального возрастания функции. На этом основана процедура подавления немаксимумов. При этой процедуре для каждой точки рассматривается отрезок длиной в несколько пикселей, ориентированный по направлению градиента и с центром в рассматриваемом пикселе. Пиксель считается максимальным тогда и только тогда, когда длина градиента в нем максимальна среди всех длин градиентов пикселей отрезка. Граничными можно признать все максимальные пиксели с длинами градиента больше некоего порога (рис. 9.3).
Градиент яркости в каждой точке перпендикулярен границе, поэтому после подавления немаксимумов жирных линий не остается: на каждом перпендикулярном сечении жирной линии останется один пиксель с максимальной длиной градиента.
Перпендикулярность градиента яркости к границе может быть использована для прослеживания границы, начиная с некоторого граничного пикселя. Такое прослеживание используется в гистерезисной фильтрации максимальных пикселей. При проведении гистерезисной фильтрации вводят не одно, а два пороговых значения. Меньшее ($$\alpha $$), как и раньше, соответствует минимальной длине градиента, при которой пиксель может быть признан граничным. Большее ($$\beta $$), соответствует минимальной длине градиента, при которой пиксель может инициализировать
контур. После того как контур инициализируется в максимальном пикселе P с длиной градиента, большей $$\beta $$, рассматриваются каждый соседний с ним максимальный пиксель Q. Если пиксель Q имеет длину градиента, большую $$\alpha $$, и угол между векторами - $$\overrightarrow{PQ}$$ и $$\nabla (P)$$ близок к $$90^{\circ}$$, то Q добавляется к контуру, и процесс рекурсивно переходит к Q. Идея гистерезисной фильтрации заключается в том, что длинный устойчивый граничный контур, скорее всего, содержит в себе пиксели с особенно большим перепадом яркости, и, начиная с такого пикселя, контур можно проследить, переходя по граничным пикселям с меньшим перепадом яркости.
Таким образом, описаный нами алгоритм нахождения границ на основе градиента заключается в последовательном применении следующих операций:
Этот алгоритм носит названия алгоритма Кэнни (Canny) [18]. Его результат показан на рис. 9.4. Алгоритм Кэнни является наиболее часто применяемым на сегодняшний день алгоритмом нахождения границ.
(рис 9.4) Алгоритм Кэнни. Вверху- исходное изображение. Внизу- результат алгоритма.
Одним из ключевых элементов алгоритма Кэнни является подавление немаксимумов, которая основана на том, что граница должна проходить через максимум градиента на данном направлении. Эта идея становится интуитивно ясной при рассмотрении функции одной переменной: точка с экстремальным значением первой производной соответствует максимально быстрому перепаду значений.
Однако, как известно из математического анализа, необходимым и достаточным условием экстремального значения первой производной функции в некой точке является равенство нулю второй производной в этой точке, причем по разные стороны от точки вторая производная должна иметь разные знаки. Про такую точку говорят, что вторая производная в ней пересекает ноль.
В двумерном случае, который нас и интересует, аналогом первой производной является вектор градиента $$\nabla f = \left( {\frac{\partial f}{\partial x}}, {\frac{\partial f}{\partial y}} \right) $$, а аналогом второй производной является скалярный оператор, называемый лапласианом $${\nabla ^2} f =\Delta f = \left( {\frac{{\partial ^2} f}{\partial x^2}} + {\frac{{\partial ^2} f}{\partial y^2}} \right) $$. Приближение лапласиана при помощи линейной фильтрации рассматривалось нами в разделе 8.2. Приведенная аналогия подтверждается и на рис. 8.5 - на нем видно, как лапласиан меняет знак при переходе через границы объектов.
Нахождение границ на изображении может, таким образом, производиться по аналогии с одномерным случаем: граничными признаются точки, в которых лапласиан равен нулю и вокруг которых он имеет разные знаки. Кроме того, оценка лапласиана при помощи линейной фильтрации предваряется гауссовской сглаживающей фильтрацией, чтобы снизить чувствительность алгоритма к шуму (аналогично тому, как это описано в разделе 9.2).
Несложно видеть (см. определение линейных фильтров в разделе 8.2), что композиция линейных фильтров есть линейный фильтр. Поэтому гауссовское сглаживание и поиск лапласиана можно осуществить единовременно при помощи фильтра, который
называется лапласиан гауссиана (рис. 9.5). Поиск пересечений нуля, так же, как и линейная фильтрация, является сравнительно быстрой операцией, поэтому нахождение границ при помощи лапласиана гауссиана производится гораздо быстрее, чем при помощи алгоритма Кэнни. Исходя из этого, описанный выше алгоритм применяется в системах, где принципиально и качество результата (которое обычно уступает алгоритму Кэнни), и быстродействие.
Чтобы еще уменьшить чувствительность алгоритма к несущественным деталям, из числа граничных точек можно исключить те, длина градиента в которых меньше порога (рис. 9.5). Для одномерного случая это будет соответствовать разумному требованию того, чтобы в точке перепада величина первой производной была не слишком маленькой.
(рис 9.5) Нахождение границ при помощи лапласиана гауссиана. Первый рисунок- исходное изображение. Второй - результат фильтрации с фильтром лапласиан гауссиана. Третий - точки пересечения нуля. Четвертый - пороговая фильтрация точек пересечения нуля по длине градиента. 
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.