Дескрипторы формы Фурье

Question

Я смотрю на статью под названием "Извлечение изображения на основе формы с использованием общих дескрипторов Фурье", но имею только элементарные знания о дескрипторах Фурье. Я пытаюсь реализовать алгоритм на странице 12 статьи, и у меня есть некоторые результаты, из которых я не могу получить слишком много смысла.

Если я создаю маленькое изображение, беру вычисление FD для изображения и сравниваю FD с тем же изображением, которое было переведено одним пикселем в направлениях x и y, дескриптор полностью отличается, за исключением первой записи - что точно так же. Во-первых, вопрос в том, должны ли эти дескрипторы быть одинаковыми (поскольку дескриптор, по-видимому, инвариантен относительно масштаба, поворота и перевода) между двумя изображениями?

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

Я быстро собрал код Javascript для проверки алгоритма, который приведен ниже.

У кого-нибудь есть вклад, идеи, способы продвижения вперед?

Спасибо пол

    var iShape = [
     0,   0,   0,   0,   0,
     0,   0, 255,   0,   0,
     0, 255, 255, 255,   0,
     0,   0, 255,   0,   0,
     0,   0,   0,   0,   0
    ];
    
    var ImageWidth = 5, ImageHeight = 5, MaxRFreq = 5, MaxAFreq = 5;
    
    // Calculate centroid
    var cX = 0, cY = 0, pCount = 0;
    for (x = 0; x < ImageWidth; x++) {
     for (y = 0; y < ImageHeight; y++) {
      if (iShape[y * ImageWidth + x]) {
       cX += x;
       cY += y;
       pCount++;
      }
     }
    }
    
    cX = cX / pCount;
    cY = cY / pCount;
    
    console.log("cX = " + cX + ", cY = " + cY);
    
    // Calculate the maximum radius
    var maxR = 0;
    for (x = 0; x < ImageWidth; x++) {
     for (y = 0; y < ImageHeight; y++) {
      if (iShape[y * ImageWidth + x]) {
       var r = Math.sqrt(Math.pow(x - cX, 2) + Math.pow(y - cY, 2));
       if (r > maxR) {
        maxR = r;
       }
      }
     }
    }
    
    // Initialise real / imaginary table
    var i;
    var FR = [ ];
    var FI = [ ];
    for (r = 0; r < (MaxRFreq); r++) {
     var rRow = [ ];
     FR.push(rRow);
     var aRow = [ ];
     FI.push(aRow);
     for (a = 0; a < (MaxAFreq); a++) {
      rRow.push(0.0);
      aRow.push(0.0);
     }
    }
    
    var rFreq, aFreq, x, y;    
    for (rFreq = 0; rFreq < MaxRFreq; rFreq++) {
     for (aFreq = 0; aFreq < MaxAFreq; aFreq++) {
      for (x = 0; x < ImageWidth; x++) {
       for (y = 0; y < ImageHeight; y++) {
        var radius = Math.sqrt(Math.pow(x - maxR, 2) +
         Math.pow(y - maxR, 2));
        var theta = Math.atan2(y - maxR, x - maxR);
        if (theta < 0.0) {
         theta += (2 * Math.PI);
        }
        
        var iPixel = iShape[y * ImageWidth + x];
        FR[rFreq][aFreq] += iPixel * Math.cos(2 * Math.PI * rFreq *
         (radius / maxR) + aFreq * theta);
        FI[rFreq][aFreq] -= iPixel * Math.sin(2 * Math.PI * rFreq *
         (radius / maxR) + aFreq * theta);
         
       }
      }
     }
    }
    
    // Initialise fourier descriptor table
    var FD = [ ];
    for (i = 0; i < (MaxRFreq * MaxAFreq); i++) {
     FD.push(0.0);
    }
    
    // Calculate the fourier descriptor
    for (rFreq = 0; rFreq < MaxRFreq; rFreq++) {
     for (aFreq = 0; aFreq < MaxAFreq; aFreq++) {
      if (rFreq == 0 && aFreq == 0) {
       FD[0] = Math.sqrt(Math.pow(FR[0][0], 2) + Math.pow(FR[0][0], 2) /
        (Math.PI * maxR * maxR));
      } else {
       FD[rFreq * MaxAFreq + aFreq] = Math.sqrt(Math.pow(FR[rFreq][aFreq], 2) +
        Math.pow(FI[rFreq][aFreq], 2) / FD[0]);
      }
     }
    }
    
    for (i = 0; i < (MaxRFreq * MaxAFreq); i++) {
     console.log(FD[i]);
    }

Answer 1

Здесь применяются три отдельных метода нормализации, чтобы сделать окончательный дескриптор инвариантным к 1) переводу и 2) масштабированию 3) вращению.

Для части трансляционной инвариантности вам нужно найти центроид формы и вычислить вектор каждой точки контура, имеющей центр тяжести в качестве источника. Это делается путем вычитания координат x и y центроида из координат каждой точки, соответственно. Таким образом, в вашем коде радиус и тета каждой точки должны быть вычислены следующим образом:

var radius = Math.sqrt(Math.pow(x - cX, 2) + Math.pow(y - cY, 2));
var theta = Math.atan2(y - cY, x - cX);

Для части инвариантности масштаба вам нужно найти максимальную величину (или, как вы говорите, радиус) каждого вектора (уже нормализованного для инвариантности сдвига) и разделить величину каждой точки на значение максимальной величины. Альтернативный способ достижения этого состоит в том, чтобы разделить каждый коэффициент Фурье на коэффициент нулевой частоты (первый коэффициент), поскольку там представлена ​​информация о масштабе. Как я вижу в вашем коде и в статье, это реализовано в соответствии со вторым способом, который я описал.

Наконец, инвариантность к вращению достигается только сохранением величины коэффициентов Фурье, как вы можете видеть на шаге 6 псевдокода статьи.

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

Надеюсь, я помог, Лазарос