3D-поиск по шаблону в поплавке [] [] - PullRequest
Новая
       25

3D-поиск по шаблону в поплавке [] []

0 голосов
/ 30 декабря 2011

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

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 4 0 9 0 0 0 0 0
0 0 0 0 0 0 0 0 3 0
0 8 0 0 0 0 0 0 0 0
0 0 0 6 0 2 8 7 0 0
0 0 0 0 0 3 5 5 0 0
0 0 0 0 0 6 2 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Я ищу библиотеку Java (или эффективный алгоритм) для обнаружения наличия и местоположения одного (или более) шаблона, похожего на ссылкуНапример, я хочу получить местоположение (5,5) в результате, независимо от того, что я искал: 

2 8 7
3 5 5
6 2 1

или: 

3 8 6
3 6 5
5 2 3

Есть идеи?

Ответы [ 3 ]

1 голос
/ 31 декабря 2011

Я не знаю ни о каких библиотеках Java, но я бы подумал, что это не будет слишком сложно для программирования.Эта проблема может рассматриваться как производная от задачи подстроки, за исключением того, что у вас нет линейной строки.Вот некоторый псевдокод Java-ish, который, вероятно, довольно близок. 

for(int x = 0; x < heightmap.width(); ++x)
    for(int y = 0; y < heightmap.height(); ++y)
        if(find_pattern(x, y))
            // YAY! pattern starts at (x, y)

// start at (x, y) and find an exact match
boolean find_pattern(int x, int y)
{
      for(int xx = 0; xx < pattern.width(); ++x)
          for(int yy = 0; yy < pattern.width(); ++x)
              if(heightmap[x + xx][y + yy] != pattern[xx][yy])
                  return false;
      return true; 
}

Это найдет точное совпадение.Если вы хотите что-то, скажем, плюс или минус 2, вам понадобится немного больше логики в find_pattern () вместо сравнения! =.

Могут быть и другие алгоритмы, которые работают лучше.Это, наверное, самое простое в программировании.В отношении сложности это происходит в O (n ^ 2 * m ^ 2): задано n - ширина и высота карты высот, а m - ширина и высота шаблона.

ПРИМЕЧАНИЕ: это не делает проверку границ!

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

.
0 голосов
/ 31 декабря 2011

Это проблема фильтрации изображений. Наиболее простой подход можно выразить так: 

for i in 0..image.height
  for j in 0..image.width
    result = 0
    for k in 0..pattern.height
      for l in 0..pattern.width
        if  i + k < image.height && j + l < image.width
          result += image[i + k][j + l] * pattern[k][l]
    if result > threshold
      /* Found a solution */

Число threshold - это то, что вы должны найти методом проб и ошибок для данной проблемы. Может быть, это хорошая идея, чтобы нормализовать числа в первую очередь в интервале [0,1]. Тогда, например, result / (pattern.width * pattern.height) > 0.75 означает что-то вроде «75% как шаблон».

В зависимости от размеров изображения и рисунка это может быть медленным - в этом случае вы можете посмотреть Фильтрация изображений в частотной области

0 голосов
/ 30 декабря 2011

Если вы можете представить данные как одномерные массив у вас по сути есть строка (содержащая только числовые значения) в котором можно искать шаблоны с регулярными выражениями. В случае это невозможно с Java (т.е. вместо этого создается строка с плавающей точкой персонажей) не должно быть слишком сложно свернуть свой собственный (простой) реализация для сопоставления регулярных выражений [1].

[1] http://matt.might.net/articles/implementation-of-nfas-and-regular-expressions-in-java/

...