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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

В настоящее время, способы, используемые для того, чтобы идентифицировать позицию и размер ярко выраженных деталей, основаны на принципе "масштабного пространства", который предусматривает применение последовательности постепенно более интенсивных фильтраций к изображению. Фильтрации, применяемые к изображению, типично представляют собой фильтрации, которые выполняют дифференциальные операции для значений физических параметров (например, яркости) точек изображения. Типично, такие фильтрации основаны на гауссовой функции, интенсивность фильтрации которой управляется посредством параметра Σ фильтрации (среднеквадратического отклонения гауссовой функции): чем выше параметр Σ фильтрации, тем более плоским и более широким является гауссиан и тем более интенсивный эффект сглаживания имеет гауссиан. Масштабное пространство изображения, сформированное посредством матрицы пикселов координат (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, Σ) аппроксимированы посредство