As objects in an image are encoded, stored, and transmitted independently, new functionalities, such as object-based manipulation (scaling or rotation), object-based matching, indexing, and retrieval for quick search in the large amount of multimedia data, are needed. Vertex-based shape coder, which uses polygons to approximate the shape of an object, is more suitable to meet these functionalities than bitmap-based shape coder. Because it has merits in inherent quality control and high-level shape features it carries intrinsically. In this dissertation, curvature-based vertex selection method for reducing contour information is presented.
First, we propose E-PVS (Extended Progressive Vertex Selection), which is based on the conventional PVS and adopts extended search area to select vertices of a polygon. Using extended search area, E-PVS selects minimum number of vertices when a maximum distortion between an original contour and a polygon (D,,,0 ) is given and improves coding efficiency.
Second, we propose C-VS (Curvature-based Vertex Selection), which uses curvature information of a contour for the selection of the vertices of a polygon. Because contour pixels with high curvature, which are called as feature points or dominant points, represent the shape of an object well, several techniques using them to represent the shape of an object have been reported in the pattern recognition and the computer vision. But they have not been used in the shape coding. C-VS is the first method using curvature information to select polygon's vertices. It selects high curvature points as initial vertices using CSS (curvature scale space) which is the most popular method to select dominant points. The selected initial vertices divide original contour into several contour segments. We approximate each contour segment independently by using E-PVS and then refine the position of vertices to minimize the approximation error by using DP (dynamic programming). Because each contour segment is processed independently, we can use the parallel processing in order to reduce the execution time for DP. Simulation results demonstrate that C-VS shows high coding performance in the rate-distortion sense.
Third, we propose A-VA (Adaptive Vertex Adjustment). The conventional vertex adjustment improved coding performance, but had heavy computational complexity. A-VA uses adaptive search range of each vertex, which is determined by the configuration of a contour and a polygon around each vertex. It reduces about 50% of execution time than the conventional VA by using adaptive search area while shows similar coding performance with the conventional one. And, we construct the entire vertex selection method which is the combination of C-VS and A-VA. It shows very high coding performance than the conventional vertex selection methods.
Fourth, we consider post-processing in order to improve the subjective quality of the reconstructed polygon. Because a polygon has sharp edges around each vertex, we smooth them by using Gaussian filter and improve the subjective quality.
Finally, we propose CT-VE (Centroid of a Triangle-based Vertex Encoding). If the number of vertices is given, the number of bits is proportional to the size of dynamic-range of relative address of consecutive two vertices when we use octant-based vertex encoding method, which is a well-known vertex encoding method in the vertex-based shape coding. We reduce the size of dynamic range using the centroid of a triangle and improve coding efficiency.
