search

hbldh / pyefd

Python implementation of "Elliptic Fourier Features of a Closed Contour"
http://pyefd.readthedocs.org/
MIT License
82 stars 15 forks source link

Descriptors not consistent across cycled contour indices #14

Open geloescht opened 3 years ago

geloescht commented 3 years ago

Description

I am trying to create invariant descriptors for the same silhouettes at different rotation angles.

What I Did

Created rotated copies of the same picture. Ran skimage.measure.find_contours() on it to extract a contour and pyefd.elliptic_fourier_descriptors(normalize=True) on the result. Expected output: Equal with some margin of error for differently rotated copies. Actual output: Result is only sometimes equal.

Unfortunately my code is spread over several source files and depends on data, so I cannot easily share an example of what I am actually doing. But here is a function that, when inserted into tests.py will result in a failed test:

def test_normalizing_4():
    contour_2 = np.roll(contour_1[:-1,:], 40, axis=0)
    contour_2 = np.append(contour_2, [contour_2[0]], axis=0)
    c1 = pyefd.elliptic_fourier_descriptors(contour_1, normalize=True)
    c2 = pyefd.elliptic_fourier_descriptors(contour_2, normalize=True)
    np.testing.assert_almost_equal(c1, c2, decimal=12)

The reason for this behaviour is actually mentioned in the original paper in chapter 5.1 and figure 8: For every shape there are two possible classifications, each rotated along one of the two semi-major axes (rotated 180 degrees from each other). It seems like pyefd chooses one of them based on the location of the first point in the contour.

There might be two solutions to this, firstly to return both classifications or to choose one of them (more) consistently by examining higher harmonic content of the descriptor. Note that the (near-)circular case also exists as outlined in the paper in chapter 5.2, so returning multiple descriptors and normalisation parametres might be required anyway for contours with rotational symmetry.

hbldh commented 3 years ago

Thank you for reporting this. I admit, this was something that I missed when reading the paper, and it does hinder the use of pyefd if one expects such identical output.

I guess I never noticed it because I calculated contours for a lot of MNIST images and trained a ML classifier to distinguish between them. Given a large enough dataset, there will be shapes of both solution configurations present for each class in the training set and a ML classifier will be tolerant to this flaw in pyefd in such a case.

But for comparing like this, it does not work.

I am reluctant to change the output of the elliptic_fourier_descriptors to return a tuple of solutions instead, given that it will slow down the method considerably. However, a new method for returning both would be ok given that a consistent and efficient way of finding both can be found.

Personally, I have no time to invest in this package (and very little incentive to do so as well, since I do not use pyefd currently) in the foreseeable future, but I will accept a PR.

geloescht commented 3 years ago

I might give it a go, but my math skills are sometimes hitting a brick wall with this project. The fact that my dataset is essentially split in two halves is not a huge problem, but it does give me potentially less interesting results. In case you are wondering what I am using pyefd for, I am basically using it to find similar images to form an animation in a half-automated fashion. This is my latest test: https://vimeo.com/528553087