Sequential polygon approximation apparatus for contour and method thereof

• US 5,966,469 A
• Filed: 10/25/1996
• Issued: 10/12/1999
• Est. Priority Date: 10/26/1995
• Status: Expired due to Term

• Current Assignee: Hyundai Curitel ,inc
• Original Assignee: Hyundai Electronics Industries Co. Ltd. (SK Hynix Inc.)
• Inventors: Kim, Jae - Kyoon, Chung, Jae - Won, Moon, Joo - Hee
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Patel, Kanji
• Application Number:
  US08/740,291
• Time in Patent Office: 1,082 Days
• Field of Search: 382/199, 382/241, 382/242, 382/266, 382/203, 382/201
• US Class Current: 382/241
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: H04N 19/20 using video object coding

Abstract

A sequential polygon approximation apparatus for a contour and a method thereof which are capable of sequentially extracting a vertex in the order of a contour pixel when performing a polygon approximation so as to code a shape information, which includes an error computation unit for obtaining a contour pixel between two contour pixels of the vertex extraction unit from the contour pixel memory and computing an error which is a distance between a straight line between two contour pixels and a pixel from the contour pixel memory, a comparison unit for comparing an error obtained by the error computation unit with a threshold value, and a controller for controlling the vertex extraction unit and the error computation unit in accordance with the comparison result of the comparison unit, setting the pixel just before the final pixel of a first region as a first vertex when the error obtained in the first region which is the region of the contour pixel sequentially determined for the vertex extraction from a fixed one vertex is greater than a given threshold value, outputting the final pixel of a second region as a final vertex when all the errors obtained in the second region which is expanded till a predetermined contour pixel from the first region is smaller than the given threshold value, and outputting the first vertex as the final vertex.

Claims

1. A sequential polygon approximation apparatus for a contour, comprising:

a contour extraction unit for extracting a contour from shape information of an input image signal;

a contour pixel memory for storing position information of a contour pixel in the order of a connection of the contour extracted by the contour extracting unit;

a vertex extraction unit for receiving the contour pixel from the contour pixel memory and outputting two contour pixels which are necessary to draw a virtual straight line;

an error computation unit for receiving from the contour pixel memory a contour pixel between the two contour pixels outputted from the vertex extraction unit, and computing a distance between the inputted contour pixel and the virtual straight line between the two contour pixels outputted from the vertex extracting unit;

a comparison unit for comparing the distance obtained by the error computation unit and a threshold value provided by an user;

a controller for controlling the vertex extraction unit and the error computation unit according to a comparison result of the comparison unit, setting a pixel just before a final pixel of a first region as a first vertex when a distance obtained in the first region is greater than the threshold value, setting a corresponding contour pixel as the final vertex when distances obtained in a second region are all smaller than or equal to the threshold value, and setting the first vertex as the final vertex when any of the distances obtained in the second region is not smaller than or equal to the threshold value; and

a vertex memory for storing the vertexes set by the controller.

2. The apparatus of claim 1, wherein said threshold value is determined based on the effective maximum distance between the actual contour and the polygonal straight.

3. The apparatus of claim 1, wherein said threshold value is given as the number of vertexes.

4. A method of a sequential polygon approximation for a contour, comprising the steps of:

a first step for determining a first vertex by carrying out an initialization;

a second step for determining whether a pixel inputted from a contour pixel memory to a vertex extraction unit is a final pixel, after the initialization;

a third step for finishing a polygon approximation when the pixel is the final pixel in the second step, or receiving from the contour pixel memory the contour pixel positioned after two contour pixels from the first vertex which is determined in the first step;

a fourth step for drawing a virtual straight line between the contour pixel inputted in the third step and the first vertex;

a fifth step for receiving a contour pixel between the first vertex determined in the first step and the contour pixel inputted from the contour pixel memory in the third step, and computing a distance between the inputted contour pixel and the virtual straight line drawn in the fourth step;

a sixth step for confirming whether the polygon approximation that has been carried out in respect of a first region or a second region;

a seventh step for comparing the distance computed in the fifth step with the threshold value by the comparison unit when the polygon approximation relates to the first region;

an eight step for receiving a next succeeding contour pixel from the contour pixel memory and repeatedly carrying out the above steps from the fourth step when the distance is smaller than or equal to the threshold value in the seventh step, and determining as the first vertex a contour pixel lust before the pixel connected to the first vertex by the straight line and defining a second region including contour pixels between a pixel position of the first vertex and a predetermined contour pixel from the first vertex, when the distance is greater than the threshold value;

a ninth step for inputting the final pixel of the second region from the contour pixel memory to the vertex extraction unit when the polygon approximation relates to the second region in the sixth or eight step;

a tenth step for drawing a virtual straight line between the final pixel inputted in the ninth step and the first vertex of the first region;

an eleventh step for receiving from the contour pixel memory all contour pixels between the first vertex of the first region and the final contour pixel inputted from the contour pixel memory in the tenth step, and computing a distance between the inputted contour pixels and the virtual straight line drawn in the tenth step by the error computation unit;

a twelfth step for comparing the distance computed by the comparison unit in the ninth step with the threshold value; and

a thirteenth step for receiving from the contour pixel memory a pixel lust before the final pixel of the second region when any of the distances is greater than the threshold value, and repeatedly carrying out the above steps from the tenth step, determining as the final vertex a pixel of the second region connected to the first vertex by a straight line when the distances are all smaller than or equal to the threshold value, and determining the first vertex of the first region as the final vertex and storing it in the vertex memory when any of the distances to the first vertex is not smaller than or equal to the threshold value.

5. The method of claim 4, wherein when the given contour is an open contour, one of both ends of the open contour is determined as a first vertex.

6. The method of claim 4, wherein when the given contour is a closed contour, a predetermined pixel of pixels of the closed contour is determined as a first vertex.

7. The method of claim 4 wherein said threshold value is determined as an effective maximum distance between an actual contour and a polygonal straight line.

8. The method of claim 4, wherein said threshold value is given as the number of vertexes.

9. The method of claim 4, wherein said first region is a region which is sequentially determined so as to extract a vertex, and said second region is a region expanded to a predetermined contour pixel from the first region so as to extract a vertex.