Methods of contour compression in time and spectral domains

Abstract

Detailed analysis of the methods for contour data extraction has been given including the comparison between them using the number of operations versus the number of edges of the contour. The results approve that the fastest algorithm is the one which has the smallest size of windows. Six algorithms for contour data approximation in the time domain were proposed (centroid and segment distances ratio algorithms and triangle family which contains four algorithms), and compared with well known Ramer algorithm using mean square error, signal-to-noise ratio, compression ratio and the number of operations. Ali algorithms give CR more than 95% (the triangle family gives more than 97%). Except the first algorithm, their computational time of the approximating procedure is very short (i.e. many times faster than that of Ramer). Three algorithms for contour extraction (using high-pass filter) and image compression (using low-pass filter) using PHL transform were developed and compared with Sobel and Canny detectors. Two algorithms were presented for image reconstruction by contours extraction. The first algorithm using HPF and double transforms (two 1-dimensional and 2-dimensional PHL transform) while the second using two 1-dimensional PHL transform and only the most significant bit of the image.

Została przedstawiona szczegółowa analiza metod ekstrakcji konturu, wraz z kompresją z wykorzystaniem liczby operacji a liczby krawędzi konturu. Rezultaty wykazały, że najszybszym algorytmem jest ten, który posiada najmniejszy rozmiar okna. Zaproponowano sześć algorytmów aproksymacji konturu w dziedzinie czasu (algorytmy obliczające stosunek odległości odcinka, algorytmy centroid oraz cztery algorytmy rodziny trójkątnej). Porównano je z dobrze znanym algorytmem Ramera poprzez wykorzystanie błędu średniokwadratowego, stosunku sygnału do szumu, stosunku kompresji oraz liczby operacji. We wszystkich algorytmach współczynnik kompresji wynosił powyżej 95% (w algorytmach z rodziny trójkątnej- ponad 97%). Poza pierwszym algorytmem, we wszystkich pozostałych czas obliczeniowy procedury aproksymacyjnej jest bardzo krótki (tj. często szybszy niż algorytm Ramera). Udoskonalono trzy algorytmy ekstrakcji konturu (z użyciem filtru górno-przepustowego) oraz algorytmy kompresji obrazu (z użyciem filtru dolno-przepustowego) z wykorzystaniem transformacji PHL. Wszystkie algorytmy porównano z detektorami Sobela i Cannyego. Przedstawiono dwa algorytmy ekstrakcji konturów do rekonstrukcji obrazu. Pierwszy algorytm wykorzystuje HPF oraz podwójną transformację (dwie jedno- oraz dwu-wymiarowe transformacje PHL), podczas gdy drugi algorytm wykorzystuje jedno-wymiarową transformację PHL oraz tylko jeden najbardziej znaczący bit obrazu.