СРАВНЕНИЕ ИЗОБРАЖЕНИЙ ПОСРЕДСТВОМ ВСТРАИВАНИЯ МЕТРИК

1. Способ, содержащий:
представление первого изображения в виде первого графа и второго изображения в виде второго графа, причем каждая вершина в первом и втором графах соответствует пикселу в соответствующих изображениях;
назначение веса каждому ребру между вершинами в каждом неориентированном графе, причем вес соответствует разнице между значениями смежных пикселов;
получение первого семейства деревьев из первого графа и второго семейства деревьев из второго графа, причем в эти семейства деревьев внедряются метрики графа; и
определение меры разницы для первого и второго изображений на основе меры разницы между первым и вторым семействами деревьев.
2. Способ по п.1, в котором представление первого и второго изображений в виде первого и второго графов включает в себя обработку каждого изображения при помощи вейвлетного преобразования.
3. Способ по п.2, в котором вейвлетное преобразование предусматривает трехуровневое вейвлетное преобразование Хаара.
4. Способ по п.2, дополнительно предусматривающий уменьшение размерности каждого изображения для снижения шума, что дает в результате предварительно обработанное изображение.
5. Способ по п.2, дополнительно предусматривающий уменьшение размерности каждого изображения до приблизительно 70 пикселов в ширину для формирования предварительно обработанного изображения.
6. Способ по п.1, в котором получение семейства деревьев предусматривает получение семейства иерархических хорошо разделенных деревьев посредством рекурсивной иерархической кластеризующей декомпозиции изображения.
7. Способ по п.6, в котором рекурсивная иерархическая кластеризующая декомпозиция включает в себя:
выбор кластера пикселов из предварительно обработанного изображения, случайного местоположения x пиксела в этом кластере пикселов, размера r кластера и радиуса d кластера, равного - r(log N)(log x), где N - количество пикселов в предварительно обработанном изображении, и
генерирование дочерних кластеров упомянутого кластера пикселов до тех пор, пока кластер пикселов не окажется разделенным, при этом данное генерирование включает в себя рекурсивное построение дочерних кластеров с последовательными радиусами из точки x, причем каждый дочерний кластер задается на основе отношения ранее полученного кластера, деленного на кластер с текущим радиусом.
8. Способ по п.1, в котором определение разницы между первым семейством деревьев и вторым семейством деревьев включает в себя сравнение топологии первого семейства деревьев и второго семейства деревьев и сравнение топологии кластеров, связанных с узлами деревьев первого и второго семейств.
9. Способ по п.1, в котором определение разницы между первым семейством деревьев и вторым семейством деревьев включает в себя вычисление выпуклой оболочки кластера, связанного с каждым узлом первого семейства деревьев и второго семейства деревьев, для получения параметров формы для этого узла, назначение вектора форм каждому узлу посредством конкатенации местоположения кластера, связанного с этим узлом, с параметрами формы и нахождение меры разницы, которая минимизирует разницу между векторами форм для соответствующих множеств дочерних узлов первого и второго семейств деревьев.
10. Способ по п.9, дополнительно предусматривающий агрегирование разниц по узлам деревьев посредством формирования вектора минимизированных разниц векторов форм и нормирования компонентов этого вектора.
11. Способ по п.1, дополнительно предусматривающий последовательное повторение этого способа для первого изображения и членов набора изображений для нахождения члена этого набора с наибольшим сходством с первым изображением.
12. Запоминающий носитель, содержащий множество исполняемых команд, которые при их исполнении вычислительным устройством реализуют способ по п.1.
13. Машина сравнения изображений, содержащая:
средство формирования графа изображения для получения неориентированных графов из соответствующих изображений, причем вершины этих неориентированных графов соответствуют пикселам в изображениях;
средство создания дерева для получения семейства деревьев из каждого неориентированного графа;
средство дифференциации деревьев для определения минимальной разницы между соответствующими узлами семейств деревьев;
средство агрегирования для составления матрицы разниц между семействами деревьев; и
средство формирования вектора для получения меры сходства для двух изображений из матрицы разниц.
14. Машина сравнения изображений по п.13, в которой средство формирования графа изображения включает в себя средство приведения к шкале уровней серого для предварительной обработки цветных изображений, средство вейвлетного преобразования для определения значений вектора коэффициентов пиксела и средство уменьшения размерности для уменьшения размерности изображения и снижения шума.
15. Машина сравнения изображений по п.13, в которой средство создания дерева дополнительно включает в себя средство рекурсии кластеров для разделения изображения, представляемого неориентированным графом, на хорошо разделенные кластеры.
16. Машина сравнения изображений по п.13, в которой средство создания дерева дополнительно включает в себя средство усечения дерева для удаления узлов дерева, связанных с соответствующими кластерами, количество узлов в которых меньше некоторого порога.
17. Машина сравнения изображений по п.13, в которой средство создания дерева дополнительно включает в себя фильтр перезапуска для перезапуска обработки изображения в средстве формирования графа изображения, если дерево имеет количество узлов ниже некоторого порога.
18. Машина сравнения изображений по п.13, в которой средство дифференциации деревьев дополнительно включает в себя средство минимальной разницы, включающее в себя средство сравнения топологии деревьев и средство сравнения топологии кластеров.
19. Система, содержащая:
средство для получения графов из соответствующих изображений;
средство для получения семейства деревьев из каждого графа; и
средство для определения минимальной разницы между семействами деревьев двух различных изображений.
20. Система по п.19, дополнительно содержащая средство для выбора изображения и средство для нахождения наиболее схожего изображения для выбранного изображения из набора изображений на основе минимальных разниц между семействами деревьев.