Идентификация ключевых точек

Изобретение относится к технологиям анализа изображений. Техническим результатом является повышение точности идентификации ключевых точек в цифровом изображении, содержащем набор пикселов. Предложен способ идентификации ключевых точек в цифровом изображении, содержащем набор пикселов, причем каждый пиксел имеет ассоциированное соответствующее значение характерного параметра изображения. Способ содержит этап, на котором аппроксимируют фильтрованное изображение, причем упомянутое фильтрованное изображение зависит от параметра фильтрации и содержит, для каждого пиксела изображения, функцию фильтрации, которая зависит от параметра фильтрации для того, чтобы вычислять фильтрованное значение значения характерного параметра пиксела. При этом аппроксимация содержит этап, на котором формируют набор базовых фильтрованных изображений, причем каждое базовое фильтрованное изображение представляет собой изображение, фильтрованное с помощью соответствующего значения параметра фильтрации. 21 з.п. ф-лы, 20 ил.

 

Уровень техники

Область техники

Настоящее изобретение относится к области техники анализа изображений.

Описание предшествующего уровня техники

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

Еще несколько лет назад, можно было идентифицировать позицию ярко выраженных деталей изображения, но не их размер. Более подробно, идентификация местоположения ярко выраженной детали изображения выполняется через идентификацию ассоциированной ярко выраженной точки изображения (на жаргоне, ключевой точки), которая практически соответствует центру ярко выраженной детали. В случае детали, имеющей круглую форму, ключевая точка совпадает с центром детали, тогда как в случае деталей, имеющих различные формы, позиция ключевой точки может отличаться от фактического центра детали.

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

В настоящее время, способы, используемые для того, чтобы идентифицировать позицию и размер ярко выраженных деталей, основаны на принципе "масштабного пространства", который предусматривает применение последовательности постепенно более интенсивных фильтраций к изображению. Фильтрации, применяемые к изображению, типично представляют собой фильтрации, которые выполняют дифференциальные операции для значений физических параметров (например, яркости) точек изображения. Типично, такие фильтрации основаны на гауссовой функции, интенсивность фильтрации которой управляется посредством параметра Σ фильтрации (среднеквадратического отклонения гауссовой функции): чем выше параметр Σ фильтрации, тем более плоским и более широким является гауссиан и тем более интенсивный эффект сглаживания имеет гауссиан. Масштабное пространство изображения, сформированное посредством матрицы пикселов координат (X, Y), представляет собой пространство, сформированное посредством набора фильтрованных изображений (с точки зрения яркости), полученных из применения с начального изображения постепенно более интенсивных фильтров (т.е. с постепенно большими значениями Σ), и в силу этого представляет собой трехмерное (x, y, Σ) пространство.

Теория (см., например, работу автора T. Lindeberg (1992) "Scale-space behavior of local extrema and blobs", J. of Mathematical Imaging and Vision, 1 (1), страницы 65-99) утверждает, что если имеется экстремальное значение (относительно Σ) фильтрованного изображения для точки (x_p, y_p, Σ_p), принадлежащей пространству (x, y, Σ), т.е. максимум или минимум (относительно Σ) в части пространства (x, y, Σ), окружающего точку (x_p, y_p, Σ_p), то эта точка ассоциирована с ярко выраженной деталью, центральные координаты которой составляют (x_p, y_p), и размер является пропорциональным Σ_p. Размер (диаметр) детали (в единицах или пикселах) равен 2*sqrt(2)*Σ_p.

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

Чтобы находить экстремальные точки в масштабном пространстве, известные способы (к примеру, способ, который использует дескриптор "преобразования масштабно-инвариантных признаков", SIFT, описанный в 1999 году в статье "Object recognition from local scale-invariant features" авторов Lowe, David G., Proceedings of the International Conference on Computer Vision 2, страницы 1150-1157, и предмет патента (США) 6711293) рассматривают последовательность фильтрованных изображений с возрастающими значениями Σ, и для каждой точки изображения, фильтрованного с помощью Σ, сравнивают их значения со значениями восьми смежных точек идентичного изображения и значениями 18 (9+9) смежных точек, присутствующих в фильтрованных изображениях, соответствующих предыдущим и следующим значениям Σ в последовательности. Если эта точка меньше или больше всех смежных точек, то точка является экстремальным значением пространства x, y, Σ и является возможным вариантом в качестве ключевой точки.

Эта точка является только возможным вариантом, поскольку известен способ (см., например, работу Lowe, DG "Distinctive Image Features from Scale-Invariant Keypoints", International Journal of Computer Vision, 60, 2, страницы 91-110, 2004) исключать точки, соответствующие частям изображения, имеющим низкую контрастность, и точки, которые находятся в структурах, аналогичных краям, поскольку местоположение детали вдоль края может легко варьироваться в различных изображениях, которые изображают идентичную сцену. Таким образом, точка является ненадежной и в силу этого отбрасывается.

Сущность изобретения

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

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

Аспект настоящего изобретения ссылается на способ идентификации ключевых точек в цифровом изображении, содержащем набор пикселов. Каждый пиксел имеет ассоциированное соответствующее значение характерного параметра изображения. Упомянутый способ содержит аппроксимацию фильтрованного изображения. Упомянутое фильтрованное изображение зависит от параметра фильтрации и содержит, для каждого пиксела изображения, функцию фильтрации, которая зависит от параметра фильтрации для того, чтобы вычислять фильтрованное значение значения характерного параметра пиксела. Упомянутая аппроксимация содержит:

- a) формирование набора базовых фильтрованных изображений, причем каждое базовое фильтрованное изображение представляет собой изображение, фильтрованное с помощью соответствующего значения параметра фильтрации;

- b) для каждого пиксела, по меньшей мере, поднабора упомянутого набора пикселов, аппроксимацию функции фильтрации посредством соответствующей аппроксимирующей функции на основе базовых фильтрованных изображений, причем упомянутая аппроксимирующая функция представляет собой функцию параметра фильтрации в пределах предварительно заданного диапазона параметра фильтрации;

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

Для каждого пиксела, идентифицированного в качестве возможного варианта ключевой точки, способ дополнительно содержит:

- c) сравнение значения, предполагаемого посредством аппроксимирующей функции равным значению параметра фильтрации, соответствующего глобальному экстремальному значению пиксела, со значениями, предполагаемыми посредством аппроксимирующих функций смежных пикселов в изображении равными значениям параметров фильтрации соответствующих глобальных экстремальных значений таких смежных пикселов, и

- d) выбор такого пиксела на основе этого сравнения.

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

Согласно варианту осуществления настоящего изобретения, упомянутая аппроксимирующая функция основана на дополнительной аппроксимации упомянутой линейной комбинации упомянутых базовых фильтрованных изображений.

Согласно варианту осуществления настоящего изобретения, упомянутая аппроксимирующая функция представляет собой полином, имеющий параметр фильтрации в качестве переменной.

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

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

Согласно варианту осуществления настоящего изобретения, способ дополнительно содержит:

- для каждого выбранного пиксела, вычисление главной кривизны и вторичной кривизны поверхности, сформированной посредством функций фильтрации в пикселах изображения, содержащегося в заплате, центрированной на таком выбранном пикселе;

- отбрасывание/поддержание такого пиксела из/в выбранных пикселах на основе отношения между главной кривизной и вторичной кривизной.

Согласно варианту осуществления настоящего изобретения, способ дополнительно содержит:

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

- отбрасывание/поддержание такого пиксела из/в выбранных пикселах на основе такого значения, предполагаемого посредством второй производной.

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

Согласно варианту осуществления настоящего изобретения:

- по меньшей мере, одно из значений параметра фильтрации базовых фильтрованных изображений в два раза превышает наименьшее из значений параметра фильтрации других базовых фильтрованных изображений;

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

Согласно варианту осуществления настоящего изобретения, упомянутое фильтрованное изображение основано на применении фильтров на основе вычисления лапласиана над гауссианами или фильтров на основе разностей гауссианов, и упомянутый параметр фильтрации представляет собой среднеквадратическое отклонение гауссовой функции.

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

Согласно варианту осуществления настоящего изобретения, каждый пиксел изображения имеет, по меньшей мере, одну соответствующую координату, которая идентифицирует местоположение пикселов в изображении, причем упомянутый способ дополнительно содержит, для каждого выбранного пиксела, модификацию упомянутой, по меньшей мере, одной координаты такого пиксела посредством вычисления соответствующего изменения координат на основе дополнительной аппроксимирующей функции, которая аппроксимирует функцию фильтрации в пикселе относительно такого изменения координат, причем упомянутая дополнительная аппроксимирующая функция основана:

1) на функции фильтрации такого выбранного пиксела, равной значению параметра фильтрации, соответствующего глобальному экстремальному значению выбранного пиксела, и 2) на функциях фильтрации пикселов, смежных с выбранным пикселом в изображении, равных значению параметра фильтрации, соответствующего глобальному экстремальному значению выбранного пиксела.

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

Краткое описание чертежей

Эти и дополнительные признаки и преимущества настоящего изобретения должны становиться очевидными из нижеприведенного описания некоторых вариантов осуществления в качестве примера, а не ограничения, которые должны рассматриваться в сочетании с прилагаемыми чертежами, на которых:

Фиг. 1A является графиком, показывающим сигнал яркости в качестве функции координаты;

Фиг. 1B показывает, для различных возрастающих значений Σ, соответствующий LoG-фильтр и сигнал по фиг. 1A, фильтрованный через этот LoG-фильтр;

Фиг. 2A показывает двумерное изображение, каждая точка которого имеет соответствующее значение яркости;

Фиг. 2B показывает, для возрастающих значений Σ, соответствующий LoG-фильтр и изображение по фиг. 2A, фильтрованное через LoG-фильтр;

Фиг. 3A иллюстрирует четыре базовых фильтра LoGB;

Фиг. 3B показывает, как LoG-фильтр, аппроксимированный посредством линейной комбинации в соответствии с одним вариантом осуществления настоящего изобретения, является аналогичным фильтру, который явно вычислен;

Фиг. 3C иллюстрирует схему, показывающую то, как весовые коэффициенты линейной комбинации четырех базовых фильтров LoG варьируются в функции Σ, чтобы получать общий LoG-фильтр;

Фиг. 4A показывает изображение по фиг. 2A, фильтрованное через свертку с помощью фильтра LoG, имеющего Σ, равное 2,5;

Фиг. 4B показывает изображение по фиг. 2A, фильтрованное через аппроксимацию LoG-фильтра для Σ, равного 2,5, посредством аппроксимирующей функции в соответствии с вариантом осуществления настоящего изобретения;

Фиг. 4C является изображением, получающимся в результате разности между изображением по фиг. 4A и изображением по фиг. 4B;

Фиг. 5A-5B показывают блок-схему последовательности операций способа, который иллюстрирует с точки зрения функциональных блоков процесс идентификации ключевой точки изображения в соответствии с вариантом осуществления настоящего изобретения;

Фиг. 6A показывает, посредством шкалы полутонов, пример максимального значения, предполагаемого посредством аппроксимирующей функции в соответствии с вариантом осуществления настоящего изобретения для каждой точки примерного изображения по фиг. 2A;

Фиг. 6B показывает, посредством шкалы полутонов, пример минимального значения, предполагаемого посредством аппроксимирующей функции в соответствии с вариантом осуществления настоящего изобретения для каждой точки изображения по фиг. 2A;

Фиг. 6C и 6D показывают пример того, какие из точек изображения по фиг. 2A представляют собой точки максимума и минимума, соответственно, которые являются возможными вариантами в качестве потенциальных ключевых точек;

Фиг. 7A и 7B показывают, надлежащим образом, соответствующие точки максимума и минимума, которые по-прежнему считаются потенциальными ключевыми точками после того, как процедура сравнения со смежными точками выполнена в соответствии с вариантом осуществления настоящего изобретения;

Фиг. 8A показывает точки, идентифицированные в качестве ключевой точки в первой октаве изображения на фиг. 2A, а фиг. 8B показывает точки, идентифицированные в качестве ключевой точки в пяти рассматриваемых октавах изображения по фиг. 2A.

Подробное описание примерных вариантов осуществления изобретения

Типично, фильтр на основе гауссовой функции, который применяется к изображениям, может представлять собой вычисление лапласиана над гауссианами ("вычисление лапласиана над гауссианами", LoG) или разность гауссианов ("разность гауссианов", DoG). Разность гауссианов аппроксимирует вычисление лапласиана над гауссианами, но ее может быть удобным приспосабливать по вычислительным причинам.

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

Чтобы показывать механизм, который находится в основе идентификации ярко выраженных деталей посредством применения LoG-фильтрации, далее представлены два примера: в первом примере, проиллюстрированном на фиг. 1A и 1B, для простоты, вместо двумерного изображения рассматривается одномерный сигнал яркости, тогда как второй пример, показанный на фиг. 2A и 2B, ссылается на двумерное изображение.

Что касается первого примера, фиг. 1A является графиком, показывающим, в качестве функции одной координаты X, значение яркости; если смотреть на график по фиг. 1A, можно уже отметить присутствие двух ярко выраженных деталей, соответствующих двум пикам сигнала. Чтобы видеть, как эти две ярко выраженных детали могут идентифицироваться посредством процедуры LoG-фильтрации, которая дает возможность идентифицировать не только центральную координату, но также и размер, следует обратиться к фиг. 1B, который показывает, для различных возрастающих значений Σ (Σ=2, Σ=6, Σ=10, Σ=14, Σ=18, Σ=22), соответствующий LoG-фильтр (слева на чертеже) и сигнал по фиг. 1A, фильтрованный через этот LoG-фильтр (справа на чертеже). В рассматриваемом примере, могут идентифицироваться два экстремальных значения, а именно, первое экстремальное значение, равное x=210, когда Σ=6, и второе экстремальное значение, равное x=110, когда Σ=14. Эти экстремальные значения указывают присутствие двух ярко выраженных деталей, центры которых находятся в точках 210 и 110 (или в пикселах, если это изображение), и ширина которых составляет приблизительно 16,87 и 39,59 точек, с использованием отношения: диаметр ярко выраженной точки =2*sqrt(2)*Σ.

Что касается второго примера, фиг. 2A показывает двумерное изображение, каждая точка которого имеет соответствующее значение яркости, тогда как фиг. 2B показывает, для возрастающих значений Σ (Σ=2, Σ=9, Σ=16, Σ=23), соответствующий LoG-фильтр (справа на чертеже) и изображение по фиг. 2A, фильтрованное через такой LoG-фильтр (слева на чертеже). Серповидное окно рядом со словом "SCUOLA" представляет собой ярко выраженную деталь с легко обнаруживаемой отличающейся формой, имеющую высоту в центре приблизительно в 19 пикселов. Это означает то, что в середине окна, результат применения LoG-фильтра к изображению имеет максимальное значение при Σ, равном 19/(2*sqrt(2))=6,46. Фактически, можно отметить, что в центре окна, наибольшее значение (самое светлое), полученное в качестве результата фильтрации, является значением, которое соответствует LoG-фильтру, имеющему Σ=9, т.е. LoG-фильтру из четырех используемых LoG-фильтров, имеющих значение Σ, более близкое к 6,46.

Поскольку LoG-фильтр имеет тенденцию значительно увеличиваться по размеру по мере того, как возрастает Σ (при Σ=50, фильтр является представимым с помощью матрицей почти из 500x500 точек), обработка, описанная выше, может выполняться преимущественно посредством использования подхода на основе "октав", чтобы сокращать число вычислений. Обработка по октавам основана на таком наблюдении, что результат фильтра при Σ=Σ* в исходном изображении может воспроизводиться с помощью фильтра при Σ=Σ*/2 в изображении, масштабированном до 50%. В обработке по октавам, интервал является фиксированным для Σ, фильтрованные изображения изучаются для некоторых Σ, которые попадают в диапазон, и затем изображение масштабируется до 50% посредством повторения идентичного типа анализа для уменьшенного изображения (выполнения идентичных фильтраций). Процесс итеративно проходится до тех пор, пока масштабированное изображение не будет иметь размер ниже предварительно определенного порогового значения. Например, при начале с VGA-изображения (640x480) и прекращении процесса, когда более короткая сторона изображения меньше 20 пикселов, получаются пять октав (640x480, 320x240, 160x120, 80x60, 40x30).

Один из базовых принципов решения в соответствии с вариантами осуществления настоящего изобретения возникает из такого наблюдения, что можно аппроксимировать LoG-фильтр (x, y, Σ) (где x, y являются пространственными координатами изображения (т.е. точками или пикселами, которые формируют изображение), и Σ является среднеквадратическим отклонением гауссиана, причем x, y, Σ задают масштабное пространство) в качестве линейной комбинации n фильтров LoGB(x, y, Σ_i), ранее вычисленных для n различных Σ=Σ_i (i=1, 2,..., n), далее называемых "базовыми фильтрами":

(1): LoG(x, y, Σ)≈p₁(Σ)LoGB(x, y, Σ₁)+p₂(Σ)LoGB(x, y, Σ₂)+p₃(Σ)LoGB(x, y, Σ₃)+...+p_n(Σ)LoGB(x, y, Σ_n),

где p₁(Σ), p₂(Σ),..., p_n(Σ) являются весовыми коэффициентами, значение которых представляет собой функцию Σ, как показано ниже в этом описании. Пространственная зависимость от x и y опущена для простоты.

Ссылаясь на пример, показанный на фиг. 3A, предположительно вычислено четыре базовых фильтра LoGB(Σ₁), LoGB(Σ₂), LoGB(Σ₃), LoGB(Σ₄), причем Σ₁=1,8, Σ₂=2,846, Σ₃=3,6 и Σ₄=4,2214. При формировании линейной комбинации этих четырех базовых фильтров LoGB, можно аппроксимировать LoG-фильтр следующим образом:

(2): LoG(x, y, Σ) ≈ p₁(Σ)LoGB(x, y, 1,8)+p₂(Σ)LoGB(x, y, 2846)+p₃(Σ)LoGB(x, y, 3,6)+p₄(Σ)LoGB(x, y, 4,2214).

С использованием отношения (2), можно получать хорошую аппроксимацию LoG-фильтра для Σ, равного, например, 2,5:

(3): LoG (x, y, 2,5)≈0,0161 LoGB(x, y, 1,8)+0,2501 LoGB(x, y, 2,846)-0,187 LoGB(x, y, 3,6)+0,0836 LoGB(x, y, 4,2214)

На фиг. 3B можно наблюдать то, как LoG-фильтр, аппроксимированный посредством линейной комбинации (справа на чертеже), является аналогичным LoG-фильтру, вычисленному явно (слева на чертеже).

Весовые коэффициенты p₁(Σ), p₂(Σ),..., p_n(Σ) вычисляются посредством решения системы линейных уравнений:

(4): Ap=b,

где:

- A является матрицей, имеющей число столбцов, равное числу n базовых фильтров LoGB (в рассматриваемом примере, четырем), при этом каждый столбец представляет соответствующий базовый фильтр LoGB. При условии, что общий LoG-фильтр является представимым посредством квадратной матрицы mxm (в которой каждый элемент соответствует одному пикселу), каждый столбец A компонуется посредством выстраивания в столбцах столбцов матрицы каждого базового фильтра LoGB, получая соответствующий вектор-столбец m2 элементов.

- b является вектором-столбцом из m2 элементов, который представляет LoG-фильтр, который должен быть аппроксимирован.

- p является вектором из n элементов, содержащим весовые коэффициенты p₁(Σ), p₂(Σ),..., p_n(Σ) (в рассматриваемом примере, p₁, p₂, p₃, p₄), которые определяются посредством решения системы.

Чтобы решать систему, в соответствии с вариантом осуществления настоящего изобретения, можно использовать известный метод наименьших квадратов либо любой другой метод, который дает возможность уменьшать норму разности между наблюдаемыми и аппроксимированными значениями, как, например, в способе известном как "метод моделирования отжига" (в этом отношении, см., например, работу авторов Kirkpatrick, S., Gelatt, CD, Vecchi, MP (1983) "Optimization by Simulated Annealing", Science 220 (4598): 671-680).

Посредством выбора набора q LoG-фильтров, которые должны быть аппроксимированы, имеющих соответствующие Σ=Σ'₁, Σ'₂,..., Σ'_q, и на основе отношения (4), можно вычислять матрицу W весовых коэффициентов, имеющую строку для каждого из n базовых фильтров LoGB и столбец для каждого из q LoG-фильтров для аппроксимации и содержащую для каждого столбца весовые коэффициенты p₁(Σ), p₂(Σ),..., p_n(Σ), чтобы аппроксимировать LoG-фильтр, соответствующий такому столбцу, согласно следующему отношению:

(5) AW=D,

где D является матрицей, которая содержит q LoG-фильтров (Σ'_j) (j=1, 2,..., q).

В таком случае возможна интерполяция, для каждого из n базовых фильтров LoGB, соответствующих элементов матрицы W весовых коэффициентов с тем, чтобы определять то, как весовые коэффициенты p₁(Σ), p₂(Σ),..., p_n(Σ) варьируются относительно Σ. Точность, с которой тренд весовых коэффициентов p₁(Σ), p₂(Σ),..., p_n(Σ) аппроксимирован относительно Σ, зависит от числа q LoG-фильтров, рассматриваемых в отношении (5) (чем выше q, тем лучше аппроксимация).

Фиг. 3C иллюстрирует схему, показывающую то, как варьировать весовые коэффициенты p₁(Σ), p₂(Σ), p₃(Σ), p₄(Σ) примера, рассматриваемого выше, в функции Σ. В этом случае, кривые сформированы посредством интерполяции для каждого весового коэффициента 13 точек, соответствующих 13 различным Σ=Σ'₁, Σ'₂,..., Σ'_q (т.е. q=13).

Чтобы фильтровать изображение с помощью фильтра LoG(Σ), свертка LoG-фильтра выполняется с помощью этого изображения I:

(6): L(Σ)=LoG(Σ)*I,

где L(Σ) является результатом LoG-фильтра, применяемого к изображению (далее называемому "фильтрованным изображением"), а "*" является символом свертки.

Поскольку свертка является линейным оператором, посредством использования такого свойства преимущественно можно получать аппроксимацию любого фильтрованного изображения L(Σ) (т.е. для фильтрации, соответствующей любому Σ) без необходимости явно вычислять его. Фактически, посредством использования такого свойства и подстановки отношения (1) в отношение (6), получается следующее отношение:

(7):

L(x, y, Σ)≈p₁(Σ) L(x, y, Σ₁)+p₂(Σ) L(x, y, Σ2)+p₃(Σ) L(x, y, Σ₃)+…+p_n(Σ) L(x, y, Σ_n)

Другими словами, благодаря решению в соответствии с вариантом осуществления настоящего изобретения, достаточно явно вычислять фильтрацию уменьшенное число раз (т.е. n), чтобы получать n фильтрованных изображений L(Σ_i) (i=1, 2,..., n) с использованием n базовых фильтров LoGB(Σ_i), и использовать отношение (7), чтобы аппроксимировать общее фильтрованное изображение L(Σ) начиная с этих фильтрованных изображений L(Σ_i).

Чтобы получать аппроксимацию для фильтрованного изображения L(Σ), в силу этого достаточно однократно вычислять матрицу W весовых коэффициентов, которая задает значение n весовых коэффициентов p_i(Σ) для определенного набора Σ достаточно большим (т.е. посредством рассмотрения матрицы D, содержащей достаточное число q LoG-фильтров), чтобы удовлетворять обязательным требованиям по точности.

Второй базовый принцип решения в соответствии с вариантами осуществления настоящего изобретения предусматривает аппроксимацию общего фильтрованного изображения L(Σ) посредством аппроксимирующей функции фильтрации, которая зависит от непрерывного набора значений Σ.

В соответствии с вариантом осуществления настоящего изобретения, аппроксимирующая функция представляет собой полином степени r, хотя эквивалентные соображения применяются в случае, если эта аппроксимирующая функция представляет собой другую функцию, например, функцию alog(Σ)+bΣ²+cΣ+d. Тем не менее, выбор полинома является преимущественным в том, что полиномы просто обрабатывать, поскольку они являются быстрыми в вычислении, легко извлекаются и не содержат сингулярностей.

Чтобы вычислять аппроксимирующую функцию в качестве полинома степени r в соответствии с одним вариантом осуществления настоящего изобретения, матрица W весовых коэффициентов, в свою очередь, аппроксимируется следующим образом:

(8): SF=W^T,

где S является матрицей размера q x (r+1):

(9):

где обозначение (Σ'₁)^r означает "Σ'₁, возведенный в r", и F является матрицей, содержащей значения аппроксимации, которые служат для того, чтобы аппроксимировать, посредством полиномов степени r в Σ'₁, Σ'₂,..., Σ'_q, весовые коэффициенты матрицы W весовых коэффициентов, которые должны использоваться для того, чтобы аппроксимировать LoG-фильтры, имеющие Σ=Σ'₁, Σ'₂,..., Σ'_q, соответственно. Более подробно, аппроксимирующая матрица F представляет собой матрицу размерности (r+1) x n, в которой каждый столбец F используется для того, чтобы составлять линейную комбинацию столбцов S.

Матрица S, умноженная на i-ый столбец F, является вектором, который аппроксимирует весовые коэффициенты, содержащиеся в i-ом столбце WT. Общий элемент k-ого столбца и i-ая строка F являются значением, которое используется в линейной комбинации k-ого столбца S, который соответствует (Σ'_i)^(r-k+1). Чтобы решать систему (8), в соответствии с вариантом осуществления настоящего изобретения можно использовать известный метод наименьших квадратов или любой другой метод, который дает возможность уменьшать норму разности между наблюдаемыми и аппроксимированными значениями.

При подстановке отношения (8) в (5), получается:

(10): AF^T S^T≈D.

Таким образом, на основе отношения (10), в соответствии с вариантом осуществления настоящего изобретения можно аппроксимировать фильтр LoG(Σ), имеющий любое Σ, создающее линейную комбинацию значений базовых фильтров LoGB(Σ_i), содержащихся в матрице A, посредством умножения на матрицу FT и использования результата в качестве коэффициентов полинома степени r в Σ, как указано ниже:

(11):

где (:) является обозначением, указывающим то, что матрица, предшествующая обозначению, преобразована в вектор, полученный посредством выстраивания в столбцах различных столбцов матрицы.

Следует отметить, что с учетом основания, сформированного посредством базовых фильтров LoGB(Σ_i), содержащихся в матрице A, матрица F вычисляется только один раз и используется для того, чтобы аппроксимировать любой фильтр LoG(Σ).

Согласно вышеуказанному, с использованием свойства линейности свертки и подстановки отношения (11) в отношение (6), получается:

(12):

где L(Σ) представляет общее изображение, фильтрованное с помощью фильтра LoG(Σ), а L(Σ_i) (i=1, 2,..., n) представляют изображения, фильтрованные посредством n базовых фильтров LoGB(Σ_i).

Другими словами, при раскрытии отношения (12), в соответствии с одним вариантом осуществления настоящего изобретения, общее фильтрованное изображение L(x, y, Σ) может быть аппроксимировано с помощью следующей аппроксимирующей функции:

(13): L(x, y, Σ)≈c_r(x, y)Σ^r+c_(r-1)(x, y)Σ(r-1)+…+c₁(x, y)Σ+c₀(x, y),

где (r+1) коэффициентов cr,..., c0 полинома аппроксимирующей функции являются функциями от фильтрованных изображений L(Σ_i) (i=1, 2,..., n) с использованием n базовых фильтров LoGB(Σ_i) и от матрицы F и варьируются между пикселами в качестве функции координат X и Y. Эта аппроксимация является допустимой в интервале (концы которого являются параметрами, которые могут задаваться), в котором Σ варьируется в пределах одной октавы.

В соответствии с одним вариантом осуществления, степень r полинома аппроксимирующей функции преимущественно равна 3, поскольку обнаружено, что это хороший компромисс между сложностью вычислений и точностью аппроксимации.

В частности, для r=3, общее фильтрованное изображение L(x, y, Σ) может быть аппроксимировано с помощью следующей аппроксимирующей функции:

(14): L(x, y, Σ)≈c₃(x, y)Σ³+c₂(x, y)Σ²+c₁(x, y)Σ+c₀(x, y)

Чтобы осознавать хорошее качество аппроксимации, полученной посредством аппроксимирующей функции в качестве полинома третьей степени, следует сравнить фиг. 4A, который отображает фильтрованное изображение, полученное из изображения по фиг. 2A через свертку с помощью LoG-фильтра, имеющего Σ, равное 2,5, с фиг. 4B, который представляет фильтрованное изображение, полученное из идентичного изображения по фиг. 2A посредством аппроксимации LoG-фильтра для Σ, равного 2,5, посредством аппроксимирующей функции (14) с использованием четырех базовых фильтров LoGB(Σi), причем Σi=1,8, 2,846, 3,6 и 4,2214. Фиг. 4C является изображением, получающимся в результате разности между изображением по фиг. 4A и изображением по фиг. 4B. Как можно видеть посредством наблюдения фиг. 4C, разность между изображением, фильтрованным посредством явной свертки с LoG (фиг. 4A), и изображением, фильтрованным посредством аппроксимирующей функции (14) (фиг. 4B), является близкой к нулю.

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

Процесс идентификации ключевой точки цифрового изображения I в соответствии с одним вариантом осуществления настоящего изобретения проиллюстрирован с точки зрения функциональных блоков на блок-схеме 100 последовательности операций способа, показанной на фиг. 5A-5B.

Перед переходом к подробному описанию функциональных блоков этого процесса, следует отметить, что составление аппроксимирующей функции требует использования аппроксимирующей матрицы F (см. отношение (12)), которая преимущественно вычислена один раз, например, в ходе предыдущей фазы обучения и затем используется для того, чтобы аппроксимировать любой фильтр LoG(Σ), применяемый к любому изображению I. В ходе этой фазы обучения, выбор набора n базовых фильтров LoGB(Σ_i) (i=1, 2,..., n), где Σ_i<Σ_i+1, и набора LoG q фильтров (Σ'_j) (j=1, 2,..., q) и вычисление аппроксимирующей матрицы F, как описано выше (см. отношение (10)).

Обращаясь теперь к фиг. 5A-5B, первая фаза процесса предоставляет то, что начиная с общего изображения I, вычисляются n соответствующих изображений, затем фильтрованных посредством базовых фильтров LoGB(Σ_i), а именно, вычисляются L(Σ_i) (i=1, 2,..., n) (этап 102).

В этот момент (этап 104), выбирается рабочий диапазон в Σ, в котором выполняются следующие операции. Как должно становиться очевидным в нижеприведенном описании, при выборе в качестве нижнего конца рабочего диапазона Σ_i=1 и в качестве верхнего конца рабочего диапазона Σ_i=n, можно исключать проведение некоторых вычислений на последующих стадиях процесса.

После этого выбирается точка (x_t, y_t) изображения I (этап 106), к примеру, координирующая точка (x_t=0, y_t=0), чтобы выполнять для нее операции, связанные с этапами 108-124.

Фильтрованное изображение L(x_t, y_t, Σ) в выбранной точке (x_t, y_t) затем аппроксимировано посредством вычисления аппроксимирующей функции (например, полинома степени r) с использованием отношения (12) при x=x_t и y=y_t (этап 108). Например, в случае r=3, фильтрованное изображение L(x_t, y_t, Σ) аппроксимировано посредством следующей полиномиальной функции третьей степени Σ (с коэффициентами, которые зависят от(x_t, y_t)): c₃(x_t, y_t)Σ₃+c₂(x_t, y_t)Σ₂+c₁(x_t, y_t)Σ+c₀(x_t, y_t).

Необходимое условие для того, чтобы точка в изображении представляла собой ключевую точку, состоит в том, что эта точка имеет экстремальное значение в части масштабного пространства (x, y, Σ), окружающей эту точку. В соответствии с вариантом осуществления настоящего изобретения, благодаря тому факту, что фильтрованные изображения L(x, y, Σ) аппроксимированы посредством аппроксимирующей функции, которая зависит от Σ, определение того, имеет или точка экстремальное значение, может быть преимущественно выполнено посредством сравнения тренда в Σ аппроксимирующей функции этой точки с трендом в Σ аппроксимирующих функций смежных точек.

По этой причине, на следующем этапе (этапе 110), первая производная аппроксимирующей функции вычисляется относительно Σ, и выполняется проверка в отношении того, допускает или нет (и, в положительном случае, где) эта производная значение, равное нулю, в рассматриваемом диапазоне Σ (за исключением концов), чтобы идентифицировать возможные точки локального максимума или минимума. С использованием полинома в качестве аппроксимирующей функции, можно легко вычислять производную очень быстро. Ссылаясь на рассматриваемый пример, первая производная фильтрованного изображения в точке (x_t, y_t) L(x_t, y_t, Σ) равна: 3c₃(x_t, y_t)Σ₂+2c2(x_t, y_t)Σ+c1(x_t, y_t).

Если эта первая производная допускает значение в нуль, по меньшей мере, в одной точке Σ_m диапазона Σ, за исключением концов этого диапазона (выходная ветвь Y этапа 112), процесс предусматривает вычисление значения, предполагаемого посредством аппроксимирующей функции равным упомянутому, по меньшей мере, одному Σ_m (этап 114), и сравнение этого значения аппроксимирующей функции со значениями, предполагаемыми посредством идентичной аппроксимирующей функции в соответствии с концами рассматриваемого диапазона Σ (этап 116). Если диапазон Σ, определенный на этапе 104, имеет в качестве нижнего конца Σ_i=1 и в качестве верхнего конца Σ_i=n, даже не обязательно вычислять значения аппроксимирующей функции на концах диапазона, поскольку эти значения уже вычислены (без аппроксимации) на этапе 102 в качестве фильтрованных изображений L(Σ₁), L(Σ_n) через базовый фильтр LoGB(Σ₁), LoGB(Σ_n).

Через сравнение, выполняемое на этапе 116, можно определять то, представляет собой или нет Σ_m также точку глобального максимума (или минимума) аппроксимирующей функции в рассматриваемом диапазоне Σ, либо она представляет собой только точку локального максимума (или минимума).

Если определено то, что Σ_m представляет собой точку глобального максимума (или минимума) аппроксимирующей функции относительно Σ (выходная ветвь Y этапа 118), то соответствующая выбранная точка (x_t, y_t), которая определяет значения текущих коэффициентов c_r,..., c₀ аппроксимирующей функции, представляет собой потенциальную ключевую точку. В этом случае (этап 120), координаты (x_t, y_t) точки, значение Σm и значение аппроксимирующей функции, вычисленное для Σm, вставляются в элемент первой таблицы, идентифицированной в качестве таблицы "потенциальных ключевых точек".

Следует отметить, что для каждой из точек, принадлежащих первой таблице, также получается оценка диаметра ярко выраженной детали, ассоциированной с этой точкой, равная 2*sqrt(2)*Σ_m.

Если вместо этого определяется то, что Σ_m не представляет собой точку глобального максимума (или минимума) аппроксимирующей функции относительно Σ (выходная ветвь N этапа 118), или в случае, если производная аппроксимирующей функции не допускает нулевое значение, по меньшей мере, в одной точке Σm в диапазоне Σ, за исключением концов этого диапазона (выходная ветвь N этапа 112), то соответствующая выбранная точка (x_t, y_t), которая определяет значения текущих коэффициентов c_r,..., c₀ аппроксимирующей функции, не может представлять собой потенциальную ключевую точку. В этом случае (этап 122), координаты (x_t, y_t) точки и значение аппроксимирующей функции, вычисленное для Σ_m, вставляются в элемент второй таблицы, идентифицированной в качестве таблицы "отброшенных точек".

В соответствии с другим вариантом осуществления настоящего изобретения, чтобы точка считалась потенциальной ключевой точкой, и затем она вставлялась в первую таблицу, соответствующая точка Σ_m глобального максимума (или минимума) должна дополнительно удовлетворять условию включения в поднабор рабочего диапазона, выбранного на этапе 104, причем такой поднабор имеет нижний конец выше Σ_i=1, и верхний конец ниже Σ_i=n. Таким образом, только точки максимума или минимума, которые возникают в Σ_m, для которых поведение аппроксимирующих функций известно в окружении Σ_m, которое является достаточно большим, к примеру, в окружении, имеющем минимальный размер приблизительно в 0,1 (относительно Σ).

Кроме того, чтобы предотвращать возникновение артефактов, которые могут нарушать корректную идентификацию ключевых точек, точки изображения, принадлежащие границе изображения, непосредственно отбрасываются (и в силу этого вставляются во вторую таблицу) независимо от присутствия возможных точек глобального максимума (или минимума).

Следует отметить, что для каждой точки координат (x_t, y_t) возможно то, что существует большее число точек максимума и/или минимума. В этом случае, в случае точки максимума, может рассматриваться только точка, имеющая более высокое значение L(x_t, y_t, Σ), тогда как в случае точки минимума, может рассматриваться только точка, имеющая более низкое значение L(x_t, y_t, Σ).

В соответствии с дополнительным вариантом осуществления настоящего изобретения, вместо использования для каждой точки идентичного рабочего диапазона в Σ, можно использовать соответствующий различный рабочий диапазон. Например, точка локального максимума (или минимума) аппроксимирующей функции может рассматриваться как глобальный максимум (или минимум) относительно диапазона Σ, который является подыинтервалом рабочего диапазона, содержащего Σ_m, и имеющего концы, зависящие от Σm. В этот момент, выполняется проверка для того, чтобы определять то, представляет собой или нет выбранная точка (x_t, y_t) последнюю точку изображения I (этап 124).

В отрицательном случае (выходная ветвь N этапа 124), выбирается новая точка (x_t, y_t) изображения (этап 126), и операции, описанные выше, повторяются для новой точки (возврат к этапу 108).

В положительном случае (выходная ветвь Y этапа 124), все точки изображения классифицированы в первой или во второй таблице.

Фиг. 6A показывает, посредством шкалы полутонов, пример максимального значения, предполагаемого посредством аппроксимирующей функции для каждой точки изображения примерного фиг. 2A, причем более светлый цвет соответствует более высокому значению. Фиг. 6B показывает, посредством шкалы полутонов, пример минимального значения, предполагаемого посредством аппроксимирующей функции для каждой точки изображения по фиг. 2A, причем также в этом случае более светлый цвет соответствует более высокому значению. Фиг. 6C и 6D показывают в черном цвете пример того, какие из точек изображения по фиг. 2A представляют собой точки максимума и минимума, соответственно, которые являются возможными вариантами в качестве потенциальных ключевых точек (т.е. точки, которые включены в первую таблицу).

В соответствии с вариантом осуществления настоящего изобретения, последующие операции процесса идентификации ключевых точек по фиг. 5A-5B предоставляют верификацию для каждой точки (x_t, y_t) изображения, принадлежащей первой таблице, имеющей максимум в аппроксимирующей функции, если значение аппроксимирующей функции упомянутой точки, равное значению Σ_m идентифицированного максимума, также превышает максимальные значения, предполагаемые посредством аппроксимирующих функций восьми точек, смежных с этой точкой в изображении. Аналогичным образом, для каждой точки (x_t, y_t) изображения, принадлежащего первой таблице, имеющей минимум в аппроксимирующей функции, верифицируется то, также ниже или нет значение аппроксимирующей функции этой точки, равное значению Σm идентифицированного минимума, минимальных значений, предполагаемых посредством аппроксимирующих функций восьми точек, смежных с этой точкой в изображении.

При рассмотрении точек максимума (аналогичные соображения также могут применяться к точкам минимума), в соответствии с одним вариантом осуществления настоящего изобретения точка (x_t, y_t) выбирается из первой таблицы (этап 128), и максимальное значение аппроксимирующей функции точки, получаемое из соответствующего элемента в первой таблице, сравнивается (этап 130) с максимальными значениями аппроксимирующих функций восьми смежных точек в изображении, получаемых посредством элементов, соответствующих этим смежным точкам в первой и/или во второй таблице. Следует подчеркнуть, что каждая из восьми смежных точек, в свою очередь, может представлять собой потенциальную ключевую точку (в этом случае, точка перечислена в первой таблице) или точку, которая уже отброшена (в этом случае, точка перечислена во второй таблице). Если очевидно, что максимальное значение аппроксимирующей функции в выбранной точке превышает все максимальные значения аппроксимирующих функций смежных точек (выходная ветвь Y этапа 132), то эта точка по-прежнему считается потенциальной ключевой точкой, и в силу этого она остается в первой таблице (этап 134). Если максимальное значение аппроксимирующей функции в выбранной точке не превышает все максимальные значения аппроксимирующей функции смежных точек (выходная ветвь N этапа 132), то эта точка больше не должна считаться потенциальной ключевой точкой, и в силу этого она удаляется из первой таблицы и вставляется во вторую таблицу (этап 136). После этого выполняется проверка, чтобы определять то, сравнены или нет все точки, перечисленные в первой таблице. В отрицательном случае (выходная ветвь N этапа 138), новая точка выбирается из первой таблицы (этап 140), и операции этапов 132-136 выполняются снова для этой новой точки. В положительном случае (выходная ветвь Y этапа 138), начальный отбор потенциальных ключевых точек завершается.

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

Возвращаясь к примеру, проиллюстрированному на фиг. 6C и 6D, фиг. 7A и 7B показывают в черном цвете соответствующие точки максимума и минимума, соответственно, которые остаются в первой таблице (т.е. которые по-прежнему представляют собой потенциальную ключевую точку) после того, как выполнена процедура этапов 130-140.

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

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

Первый тест на стабильность в соответствии с одним вариантом осуществления настоящего изобретения (этап 142) предусматривает отбрасывание из первой таблицы точек с абсолютным значением аппроксимирующей функции, вычисленной в соответствующем Σ_m, ниже определенного порогового значения. Эти точки принадлежат областям изображения с контрастностью ниже минимальной контрастности (определенной посредством порогового значения). Эта верификация также дает возможность исключать возможные точки, которые идентифицированы в качестве ключевой точки только вследствие аппроксимации, выполняемой посредством аппроксимирующей функции. На практике, в соответствии с областью, имеющей однородный цвет (в силу этого областью с очень низкой контрастностью), результат фильтрации в точке, принадлежащей упомянутой области по мере того, как варьируется Σ, должен иметь значения, почти постоянные и близкие к нулю, и в силу этого должен иметь плоский тренд, но аппроксимация с использованием аппроксимирующей функции имеет тенденцию формировать (в частности, если аппроксимирующая функция представляет собой полином) только локальный максимум или минимум, близкий к нулю, введенный посредством аппроксимации, что может обеспечивать возможность классификации точки в качестве ключевой точки вместо отбрасывания.

Второй тест на стабильность в соответствии с одним вариантом осуществления настоящего изобретения (этап 144) предусматривает вычисление каждой точки первой таблицы и, в заплате из 3x3 пикселов изображения, центрированной в этой точке, главной кривизны и вторичной кривизны (ортогональной к первой главной кривизне) поверхности, сформированной посредством функции L(x, y, Σ) в точках, принадлежащих этой заплате, и для сравнения этих двух заплат, вычисление отношения. Если очевидно, что две кривые являются аналогичными, то это означает то, что точка попадает в область изображения, в которой ее позиция является четко определенной, и точка остается в первой таблице, тогда как если две кривые значительно отличаются, то это означает то, что точка попадает в область изображения, аналогичную доске, и в силу этого является не очень надежной, поскольку ее местоположение или наличие значительно варьируется в зависимости от того, как наблюдается сцена. В этом последнем случае, точка удаляется из первой таблицы. Этот тест также используется в известных процедурах идентификации ключевых точек, но в отличие от них, когда заплата точек, используемых для того, чтобы вычислять заплаты, принадлежит уже фильтрованному изображению, в соответствии с вариантами осуществления настоящего изобретения, заплата компонуется в данный момент посредством вычисления фильтрованного изображения в точках, равных Σ_m рассматриваемой точки, с тем чтобы иметь более точное изображение поверхности в масштабе, которому фактически принадлежит деталь.

Третий тест на стабильность, в соответствии с одним вариантом осуществления настоящего изобретения (этап 146), предусматривает вычисление значения заплаты (в Σ) функции L(x, y, Σ), заданной посредством второй производной аппроксимирующей функции, вычисленной в соответствии с Σm точки. Ссылаясь на ранее рассматриваемый пример аппроксимирующей функции, соответствующей полиному третьей степени, заплата функции L(x_t, y_t, Σ) в точке Σ_m равна: L''(x_t, y_t, Σ_m)=6c₃(x_t, y_t)Σ_m+2c₂(x_t, y_t). Если абсолютное значение заплаты превышает пороговое значение, то точка считается стабильной и в силу этого остается в первой таблице. Если оказывается, что абсолютное значение заплаты меньше порогового значения, то точка считается нестабильной и в силу этого удаляется из первой таблицы.

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

По этой причине, в соответствии с одним вариантом осуществления настоящего изобретения, после выполнения операций, описанных выше, выполняется детализация координат точек, перечисленных в первой таблице (этап 148). К этому моменту, фактически координаты (x_t, y_t) каждой точки, перечисленной в первой таблице, соответствуют реальным и целочисленным координатам пикселов исходного изображения I. Если упомянутая детализация не выполнена, координаты точек, идентифицированных в более высоких октавах, в которых изображение масштабируется наполовину, на четверть, на одну восьмую и т.д. от исходного размера изображения, возвращаемого при полном разрешении, должны приводить к идентификации ключевых точек, которые не центрируются с соответствующими ярко выраженными деталями. Фаза детализации координат направлена на более точное определение центра ярко выраженных деталей.

Чтобы выполнять эту детализацию, в соответствии с вариантом осуществления настоящего изобретения подход, аналогичный, какой представлен в вышеприведенном, чтобы аппроксимировать с аппроксимирующей функцией фильтрованное изображение в точке по мере того, как варьируется Σ. В этом случае, вместо этого аппроксимируется фильтрованное изображение, поскольку пространственные координаты x_t-u и y_t-v варьируются в окружении общей точки (x_t, y_t), перечисленной в первой таблице, с заданием Σ фиксированно равным соответствующему значению Σ_m.

Например, в соответствии с одним вариантом осуществления настоящего изобретения, изображение, фильтрованное по мере того, как варьируются x и y, может быть аппроксимировано посредством аппроксимирующей функции, например, полинома второй степени в двух переменных u и v:

(15): L(x_t-u, y_t-v, Σ)≈l5(x_t, y_t, Σ)u²+l₄(x_t, y_t, Σ)v²+l₃(x_t, y_t, Σ)uv+l₂(x_t, y_t, Σ)u+l₁(x_t, y_t, Σ)v+l₀(x_t, y_t, Σ)

Аналогично уже описанному способу, коэффициенты аппроксимирующей функции вычисляются как линейная комбинация некоторых фильтрованных изображений, полученных посредством LoG-фильтрации. Например, в соответствии с вариантом осуществления настоящего изобретения, коэффициенты являются комбинацией фильтрованного изображения в 3x3 точках, центрированных в точке (x_t, y_t), причем Σ равно значению Σm (т.е. равно значениям заплаты, используемым для вычисления отношения главной кривизны и вторичной кривизны). Если обобщить, для получения коэффициентов, аппроксимирующая матрица G скомпонована аналогично аппроксимирующей матрице F, описанной выше, и упомянутая матрица умножается на LoG-фильтры заплаты. Аппроксимирующая функция затем подвергнута операциям идентификации максимума или минимума (в зависимости от того, идентифицирована точка (x_t, y_t) в качестве максимума или минимума), соответствующего точке, в которой первая производная относительно u и первая производная относительно v равны нулю. Если заплата центрирована в точке (x_t, y_t), u и v, которые решают систему, заданную, посредством наложения первой производной относительно u и первой производной относительно v, равной нулю, предоставляют сдвиг, который должен применяться к координатам (x_t, y_t). В соответствии с вариантом осуществления настоящего изобретения, если сдвиг вычисляется как больший по абсолютному значению пиксела изображения, по меньшей мере, вдоль u или вдоль v, то точка отбрасывается из первой таблицы. Это последнее событие является редким, но по-прежнему может иметь место, поскольку весь процесс идентификации экстремальных значений в масштабном пространстве (x, y, Σ) выполнен сначала посредством выполнения операций вдоль Σ, а затем вдоль x и y.

В соответствии с вариантом осуществления настоящего изобретения, предоставленном для того, чтобы увеличивать требуемые вычисления и сложность процедуры, должно быть возможным аппроксимировать фильтрованное изображение с одной функцией x, y и Σ.

В этот момент, все точки, которые остаются в первой таблице, идентифицируются в качестве ключевых точек изображения I в рассматриваемой октаве (этап 150). Для каждой ключевой точки, известна как ее позиция в изображении (координаты (x_t, y_t), возможно модифицированные в соответствии с фазой детализации этапа 148), так и размер ассоциированной ярко выраженной детали (равный 2*sqrt(2)*Σ_m).

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

Возвращаясь к фиг. 5A-5B, в этот момент верифицируется то, является или нет октава, рассматриваемая выше, последней из набора выбранных октав (например, пяти октав). В положительном случае (выходная ветвь Y этапа 151), процесс завершается, в противном случае (выходная ветвь N этапа 151), масштабированная версия изображения вычисляется (этап 152) для перехода к следующей октаве, и затем процесс идентификации ключевых точек повторно итеративно проходится в новой октаве (возврат к этапу 102). После повторного итеративного прохождения через процесс для достаточного числа октав (например, пяти), процесс идентификации ключевых точек завершается.

Фиг. 8B показывает точки, идентифицированные в качестве ключевой точки во всех рассматриваемых октавах (в рассматриваемом примере, в пяти) дискретизированного изображения, показанного на фиг. 2A.

В соответствии с вариантом осуществления настоящего изобретения, вместо прямого вычисления масштабированного изображения, соответствующего следующей октаве, масштабированная версия изображения может быть аппроксимирована посредством выбора Σ_i для базовых фильтров LoGB(Σ_i) таким образом, что один из таких Σ_i в два раза превышает первый Σ_i=1 (который является наименьшим из рассматриваемых Σ_i), и фильтрованное изображение может недостаточно дискретизироваться с таким Σ_i, который в два раза превышает Σ₁ (с учетом пиксела каждые два раза как по горизонтали, так и по вертикали). Таким образом, получается хорошая аппроксимация того, как изображение, масштабированное до 50%, должно получаться в результате при фильтрации с помощью базового фильтра LoGB(Σ₁). При недостаточной дискретизации, следовательно, получается изображение следующей октавы, фильтрованное с помощью первого базового фильтра LoGB(Σ₁). Фильтрация изображения, масштабированного до 50% согласно общему базовому фильтру LoGB(Σ_i), получается посредством фильтрации изображения, масштабированного до 50%, фильтрованного с помощью предыдущего базового фильтра LoGB(Σ_i-1). Координаты X, Y и масштабы Σ ключевых точек, извлеченных в различных октавах, затем сообщаются для размера исходного изображения I.

Вышеприведенное описание показывает и подробно описывает различные варианты осуществления настоящего изобретения; тем не менее, предусмотрено несколько возможных модификаций описанных вариантов осуществления, а также других вариантов осуществления изобретения, без отступления от объема, заданного посредством прилагаемой формулы изобретения.

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

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

1. Способ идентификации ключевых точек в цифровом изображении, содержащем набор пикселов, причем каждый пиксел имеет ассоциированное соответствующее значение характерного параметра изображения, причем упомянутый способ содержит этапы, на которых:

аппроксимируют фильтрованное изображение, причем упомянутое фильтрованное изображение зависит от параметра фильтрации и содержит, для каждого пиксела изображения, функцию фильтрации, которая зависит от параметра фильтрации для того, чтобы вычислять фильтрованное значение значения характерного параметра пиксела, причем упомянутая аппроксимация содержит этапы, на которых:

a) формируют набор базовых фильтрованных изображений, причем каждое базовое фильтрованное изображение представляет собой изображение, фильтрованное с помощью соответствующего значения параметра фильтрации;

b) для каждого пиксела, по меньшей мере, поднабора упомянутого набора пикселов, аппроксимируют функцию фильтрации посредством соответствующей аппроксимирующей функции на основе базовых фильтрованных изображений, причем упомянутая аппроксимирующая функция представляет собой функцию параметра фильтрации в пределах предварительно заданного диапазона параметра фильтрации;

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

для каждого пиксела, идентифицированного в качестве возможного варианта ключевой точки:

c) сравнивают значение, предполагаемое посредством аппроксимирующей функции равным значению параметра фильтрации, соответствующего глобальному экстремальному значению пиксела, со значениями, предполагаемыми посредством аппроксимирующих функций смежных пикселов в изображении равными значениям параметров фильтрации соответствующих глобальных экстремальных значений таких смежных пикселов, и

d) выбирают такой пиксел на основе этого сравнения.

2. Способ по п. 1, в котором упомянутая аппроксимация функции фильтрации посредством соответствующей аппроксимирующей функции на основе базовых фильтрованных изображений содержит этап, на котором вычисляют упомянутую аппроксимирующую функцию на основе линейной комбинации упомянутых базовых фильтрованных изображений.

3. Способ по п. 2, в котором упомянутая аппроксимирующая функция основана на дополнительной аппроксимации упомянутой линейной комбинации упомянутых базовых фильтрованных изображений.

4. Способ по п. 3, в котором упомянутая аппроксимирующая функция представляет собой полином, имеющий параметр фильтрации в качестве переменной.

5. Способ по п. 4, в котором коэффициенты упомянутого полинома вычисляются на основе базовых фильтрованных изображений и на основе аппроксимации весовых коэффициентов упомянутой линейной комбинации.

6. Способ по любому из пп. 1-3, 5, дополнительно содержащий этап, на котором отбрасывают, из выбранных пикселов, пикселы, в которых значение, предполагаемое посредством аппроксимирующей функции равным параметру фильтрации, соответствующему глобальному экстремальному значению пиксела, имеет абсолютное значение, меньшее первого порогового значения.

7. Способ по любому из пп. 1-3, 5, дополнительно содержащий этапы, на которых:

для каждого выбранного пиксела, вычисляют главную кривизну и вторичную кривизну поверхности, сформированной посредством функций фильтрации в пикселах изображения, содержащегося в заплате, центрированной на таком выбранном пикселе;

отбрасывают/поддерживают такой пиксел из/в выбранных пикселах на основе отношения между главной кривизной и вторичной кривизной.

8. Способ по любому из пп. 1-3, 5, дополнительно содержащий этапы, на которых:

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

отбрасывают/поддерживают такой пиксел из/в выбранных пикселах на основе такого значения, предполагаемого посредством второй производной.

9. Способ по любому из пп. 1-3, 5, в котором упомянутая идентификация ключевой точки дополнительно повторяется, по меньшей мере, для масштабированной версии изображения, с использованием идентичного предварительно заданного диапазона параметра фильтрации.

10. Способ по п. 9, в котором:

по меньшей мере, одно из значений параметра фильтрации базовых фильтрованных изображений в два раза превышает наименьшее из значений параметра фильтрации других базовых фильтрованных изображений;

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

11. Способ по любому из пп. 1-3, 5, в котором упомянутое фильтрованное изображение основано на применении фильтров на основе вычисления лапласиана над гауссианами или фильтров на основе разностей гауссианов, и упомянутый параметр фильтрации представляет собой среднеквадратическое отклонение гауссовой функции.

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

13. Способ по п. 4, дополнительно содержащий этапы, на которых:

для каждого выбранного пиксела, вычисляют главную кривизну и вторичную кривизну поверхности, сформированной посредством функций фильтрации в пикселах изображения, содержащегося в заплате, центрированной на таком выбранном пикселе;

отбрасывают/поддерживают такой пиксел из/в выбранных пикселах на основе отношения между главной кривизной и вторичной кривизной.

14. Способ по п. 4, дополнительно содержащий этапы, на которых:

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

отбрасывают/поддерживают такой пиксел из/в выбранных пикселах на основе такого значения, предполагаемого посредством второй производной.

15. Способ по п. 4, в котором упомянутая идентификация ключевой точки дополнительно повторяется, по меньшей мере, для масштабированной версии изображения, с использованием идентичного предварительно заданного диапазона параметра фильтрации.

16. Способ по п. 15, в котором:

по меньшей мере, одно из значений параметра фильтрации базовых фильтрованных изображений в два раза превышает наименьшее из значений параметра фильтрации других базовых фильтрованных изображений;

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

17. Способ по п. 4, в котором упомянутое фильтрованное изображение основано на применении фильтров на основе вычисления лапласиана над гауссианами или фильтров на основе разностей гауссианов, и упомянутый параметр фильтрации представляет собой среднеквадратическое отклонение гауссовой функции.

18. Способ по одному из пп. 4 и 5 и любому из пп. 12-17, в котором упомянутый полином представляет собой полином третьей степени относительно параметра фильтрации.

19. Способ по любому из пп. 1-5, 12-17, в котором каждый пиксел изображения имеет, по меньшей мере, одну соответствующую координату, которая идентифицирует местоположение пикселов в изображении, причем упомянутый способ дополнительно содержит этап, на котором, для каждого выбранного пиксела, модифицируют упомянутую, по меньшей мере, одну координату такого пиксела посредством вычисления соответствующего изменения координат на основе дополнительной аппроксимирующей функции, которая аппроксимирует функцию фильтрации в пикселе относительно такого изменения координат, причем упомянутая дополнительная аппроксимирующая функция основана:

1) на функции фильтрации такого выбранного пиксела, равной значению параметра фильтрации, соответствующего глобальному экстремальному значению выбранного пиксела, и

2) на функциях фильтрации пикселов, смежных с выбранным пикселом в изображении, равных значению параметра фильтрации, соответствующего глобальному экстремальному значению выбранного пиксела.

20. Способ по п. 19, в котором упомянутое вычисление изменения координат содержит этап, на котором идентифицируют точки максимума или минимума в дополнительной аппроксимирующей функции относительно изменения координат и задают такое изменение координат на основе идентифицированных точек максимума или минимума.

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

1) на функции фильтрации такого выбранного пиксела, равной значению параметра фильтрации, соответствующего глобальному экстремальному значению выбранного пиксела, и

2) на функциях фильтрации пикселов, смежных с выбранным пикселом в изображении, равных значению параметра фильтрации, соответствующего глобальному экстремальному значению выбранного пиксела.

22. Способ по п. 21, в котором упомянутое вычисление изменения координат содержит этап, на котором идентифицируют точки максимума или минимума в дополнительной аппроксимирующей функции относительно изменения координат и задают такое изменение координат на основе идентифицированных точек максимума или минимума.