Поиск и чтение больших файлов в приложении C++ Linux

Ниже приведены три подхода к решению этой проблемы (и есть много других).

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

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

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

Соответствие ключевых точек

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

Одним из недостатков сопоставления ключевых точек является время выполнения наивной реализации: O (n ^ 2m), где n - количество ключевых точек в каждом изображении, а m - количество изображений в базе данных. Некоторые умные алгоритмы могут находить ближайшее совпадение быстрее, например, квадродерево или разбиение двоичного пространства.

Альтернативное решение: метод гистограммы

Другим менее надежным, но потенциально более быстрым решением является построение гистограмм признаков для каждого изображения и выбор изображения с гистограммой, ближайшей к входу. гистограмма изображения. Я реализовал это как старшекурсник, и мы использовали 3 цветовые гистограммы (красная, зеленая и синяя) и две текстурные гистограммы, направление и масштаб. Я приведу подробности ниже, но я должен отметить, что это хорошо работает только для сопоставления изображений, ОЧЕНЬ похожих на изображения базы данных. Повторно масштабированные, повернутые или обесцвеченные изображения могут потерпеть неудачу с этим методом, но небольшие изменения, такие как обрезка, не нарушат алгоритм

Вычислить цветовые гистограммы несложно - просто выберите диапазон для гистограммных сегментов и для каждого диапазона подсчитайте количество пикселей с цветом в этом диапазоне. Например, рассмотрим «зеленую» гистограмму и предположим, что мы выбрали 4 сегмента для нашей гистограммы: 0-63, 64-127, 128-191 и 192-255. Затем для каждого пикселя мы смотрим на значение зеленого и добавляем подсчет в соответствующий сегмент. Когда мы закончим подсчет, мы делим каждое общее количество сегментов на количество пикселей во всем изображении, чтобы получить нормализованную гистограмму для зеленого канала.

Для гистограммы направления текстуры мы начали с определения края изображения. Каждая точка ребра имеет нормальный вектор, указывающий в направлении, перпендикулярном ребру. Мы квантовали угол вектора нормали в одно из 6 сегментов между 0 и PI (поскольку ребра имеют 180-градусную симметрию, мы конвертировали углы между -PI и 0, чтобы они были между 0 и PI). После подсчета количества краевых точек в каждом направлении мы имеем ненормализованную гистограмму, представляющую направление текстуры, которую мы нормализовали путем деления каждого сегмента на общее количество краевых точек в изображении.

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

Теперь у вас есть 5 гистограмм для каждого изображения. Чтобы сравнить два изображения, вы берете абсолютное значение разности между каждым сегментом гистограммы, а затем суммируете эти значения. Например, чтобы сравнить изображения A и B, мы вычислили бы

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

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

Третий выбор - ключевые точки + деревья решений

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

Обновление :

Моя ошибка - статья Semantic Texton Forests посвящена не только сопоставлению изображений, но и маркировке регионов. Вот оригинальная статья, которая выполняет сопоставление: Распознавание ключевых точек с использованием рандомизированных деревьев . Кроме того, нижеприведенные статьи продолжают развивать идеи и представляют современное состояние (c. 2010):

• Быстрое распознавание ключевых точек с использованием случайных папоротников - быстрее и более масштабируемо, чем Lepetit 06
• КРАТКОЕ ОПИСАНИЕ: бинарные робастные независимые элементарные функции s> - менее надежные, но очень быстрые - я думаю, что цель здесь - сопоставление в реальном времени на смартфонах и другие портативные устройства