Распознавание с учетом характеристик
Вместо применения в качестве характеристик необработанных данных о яркости пикселов можно использовать способы обнаружения и разметки пространственно локализованных характеристик, таких как участки и края (см. раздел 24.3). Применение краев является целесообразным по двум описанным ниже важным причинам. Одной из них является уменьшение объема данных, связанное с тем, что количество краев намного меньше по сравнению с количеством пикселов изображения. Вторая причина обусловлена возможностью добиться инвариантности освещенности, поскольку края (при наличии подходящего диапазона контрастов) обнаруживаются приблизительно в одних и тех же местах, независимо от точной конфигурации ос-вещенностей. Края представляют собой одномерные характеристики; были также предприняты попытки использовать двухмерные характеристики (участки) и нульмерные характеристики (точки). Обратите внимание на то, как отличаются трактовки пространственного расположения в подходах с учетом яркости и с учетом характеристик. В подходах с учетом яркости эти данные кодируются неявно, как индексы компонентов вектора характеристик, а в подходах с учетом характеристик характеристикой является само местонахождение (х,у).
Неотъемлемым свойством любого объекта является инвариантное расположение краев; именно по этой причине люди могут легко интерпретировать контурные рисунки (см. рис. 24.13), даже несмотря на то, что подобные изображения не встречаются в природе! Простейший способ использования этих знаний основан на классификаторе по ближайшим соседним точкам. При этом предварительно вычисляются и сохраняются данные о конфигурациях краев, соответствующие представлениям всех известных объектов. А после получения конфигурации краев, соответствующей неизвестному объекту на изображении, являющимся предметом запроса, можно определить "расстояние" этого объекта от каждого элемента библиотеки хранимых представлений. После этого классификатор по ближайшим соседним точкам выбирает наиболее близкое соответствие.
Для описания понятия расстояния между изображениями было предложено много разных определений. Один из наиболее интересных подходов основан на идее согласования с учетом деформации. В своей классической работе On Growth and Form [1506] Дарси Томпсон заметил, что близкие, но не идентичные формы часто можно деформировать в подобные друг другу формы с использованием простых координатных преобразований4. При таком подходе понятие подобия формы воплощается на практике в виде следующего трехэтапного процесса: во-первых, отыскивается решение задачи соответствия между двумя формами, во-вторых, данные о соответствии используются для определения преобразования, позволяющего сделать эти формы аналогичными, и, в-третьих, вычисляется расстояние между двумя формами как сумма ошибок согласования между соответствующими точками, наряду с термом, в котором измеряется величина выравнивающего преобразования.
Форма представляется с помощью конечного множества точек, полученных в виде выборки, взятой на внутренних или внешних контурах формы. Эти данные могут быть получены как сведения о местонахождениях пикселов краев, обнаруженные детектором краев, и представлены в виде множества {р1;... ,pN) из N точек. Примеры множеств точек, соответствующих двум формам, приведены на рис. 24.20, а, б.
Теперь рассмотрим конкретную точку выборки ри наряду с множеством всех векторов, исходящих из этой точки в направлении всех других точек выборки в форме. Эти векторы представляют конфигурацию всей формы относительно рассматриваемой опорной точки. Такое представление лежит в основе следующей идеи: с каждой точкой выборки можно связать дескриптор, или контекст формы, который приближенно представляет расположение остальной части формы по отношению к данной точке. Точнее, контекст формы точки р± представляет собой приближенную пространственную гистограмму hi относительных координат pk-pi остальных N-1 точек рк. Для определения сегментов используется логарифмическая—полярная система координат, обеспечивающая то, что дескриптор становится более чувствительным к различиям в ближайших друг к другу пикселах. Пример расположения сегментов показан на рис. 24.20, в.
Обратите внимание на то, что неотъемлемым свойством этого определения контекста формы является его инвариантность к операции переноса, поскольку все изменения выполняются по отношению к точкам в объекте. Для достижения инвариантности к операции масштабирования все радиальные расстояния нормализуются путем деления на среднее расстояние между парами точек.
Контексты формы позволяют решить задачу установления соответствия между двумя аналогичными, но не идентичными формами, наподобие тех, которые показаны на рис. 24.20, а, б. Контексты формы являются разными для различных точек на одной и той же форме S, тогда как соответствующие (гомологичные) точки на подобных формах S и 5", как правило, имеют одинаковые контексты формы. Таким образом, задача поиска соответствующих друг другу точек двух форм преобразована в задачу поиска партнеров, имеющих взаимно подобные контексты формы.
Точнее, рассмотрим точку р± на первой форме и точку gj на второй форме. Допустим, что Cij = C(Pi, gj) обозначает стоимость согласования этих двух точек. Поскольку контексты формы представляют собой распределения, выраженные в виде гистограмм, вполне обоснован подход, предусматривающий использование расстояния %2, следующим образом: к
_ IV [hj(k)-hk) ]2 Cij " 22 hi(k)+hj(k) k=l
где hi (к) и hj {к) обозначают k-й сектор нормализованных гистограмм в точках Pi и gj. Если дано множество стоимостей Cij согласования между всеми парами точек i на первой форме и точек j на второй форме, то может быть принято решение минимизировать общую стоимость согласования с учетом ограничения, что это согласование должно выполняться на основе взаимно-однозначного соответствия. Это — пример задачи поиска паросочетаний взвешенного двухдольного графа, которая может быть решена за время О (ЛГ3) с использованием так называемого венгерского алгоритма (Hungarian algorithm).
Если известны соответствия в точках выборки, то данные о соответствии можно распространить на всю форму, оценивая стоимость согласующего преобразования, которое позволяет отобразить одну форму на другой. Особенно эффективным является подход с использованием регуляризованного тонкостенного сплайна (regularized thin plate spline). После того как формы будут согласованы, задача вычисления оценок подобия становится относительно несложной. Расстояние между двумя формами может быть определено как взвешенная сумма расстояний контекстов форм между соответствующими точками и как энергия изгиба, связанная с тонкостенным сплайном. После получения такой меры расстояния для решения задачи распознавания можно использовать простой классификатор по ближайшим соседним точкам. Превосходная иллюстрация, демонстрирующая высокую эффективность применения этого подхода при классификации рукописных цифр, приведена в главе 20.