IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
UP-0390653
(2006-03-28)
|
등록번호 |
US-7546950
(2009-07-01)
|
발명자
/ 주소 |
|
출원인 / 주소 |
|
인용정보 |
피인용 횟수 :
7 인용 특허 :
9 |
초록
▼
A method of locating and decoding a two-dimensional machine-readable symbol in a digital image, where the symbol has three finder patterns adjacent respective corners of the symbol, takes into account the possibility of skew and pitch when delineating the symbol in the digital image by estimating th
A method of locating and decoding a two-dimensional machine-readable symbol in a digital image, where the symbol has three finder patterns adjacent respective corners of the symbol, takes into account the possibility of skew and pitch when delineating the symbol in the digital image by estimating the unknown fourth corner based on lines passing through known symbol edge points. On the basis of the delineating, a reference grid is mapped to the digital image and a bit stream is extracted based on the mapping.
대표청구항
▼
What is claimed is: 1. A method of extracting a bitstream from a machine-readable symbol in an image, the symbol comprising three finder patterns adjacent respective corners of the symbol and generally defining the corners of a right-angled triangle, the method comprising: using one or more compute
What is claimed is: 1. A method of extracting a bitstream from a machine-readable symbol in an image, the symbol comprising three finder patterns adjacent respective corners of the symbol and generally defining the corners of a right-angled triangle, the method comprising: using one or more computer processing units to perform the following: identifying the finder patterns in the symbol; orienting the symbol using the finder patterns, the orienting comprising determining which of the three finder patterns is positioned at the corner of the triangle opposite its hypotenuse ("top left finder pattern" ), and labeling the remaining two finder patterns based on the relative distance between the remaining two finder patterns that would result if one of the remaining two finder patterns were rotated about the top left finder pattern less than 180 degrees, wherein the labeling comprises: initially labeling the remaining two finder patterns respectfully as top right and bottom left finder patterns; rotating a selected one of the top right and bottom left finder patterns about the top left finder pattern; and after rotation, comparing the relative distance between the top right and bottom left finder patterns before and after rotation to verify the initial labeling; on the basis of the orienting, delineating the symbol, wherein the delineating comprises: determining the top left bottom left, and top right corners of the symbol based on the top left bottom left and top right finder patterns; and using a skew and pitch sensitive technique based on the top right and bottom left finder patterns to determine the bottom right corner of the symbol; mapping a decoding grid to the delineated symbol; and extracting bit values from the mapped symbol. 2. The method of claim 1, wherein during the labeling the top right finder pattern is rotated counterclockwise about the top left finder pattern and its position examined to determine if the top right finder pattern is farther from the bottom left finder pattern; and in the event that the top right finder pattern is farther from the bottom left finder pattern, deeming the remaining two finder patterns correctly labeled. 3. The method of claim 1, wherein during the labeling the bottom left finder pattern is rotated counterclockwise about the top left finder pattern and its position examined to determine if the bottom left finder pattern is closer to the top right finder pattern; and in the event that the bottom left finder pattern is closer to the top right finder pattern, deeming the remaining two finder patterns correctly labeled. 4. The method of claim 1, wherein during the labeling the bottom left finder pattern is rotated clockwise about the top left finder pattern and its position examined to determine if the bottom left finder pattern is farther from the top right finder pattern; and in the event that the bottom left finder pattern is farther from the top right finder pattern, deeming the remaining two finder patterns correctly labeled. 5. The method of claim 1, wherein during the labeling the top right finder pattern is rotated clockwise about the top left finder pattern and its position examined to determine if the top right finder pattern is closer to the bottom left finder pattern; and in the event that the top right finder pattern is closer to the bottom left finder pattern, deeming the remaining two finder patterns correctly labeled. 6. The method of claim 1, further comprising reversing the labeling if the comparing does not verify the initial labeling. 7. The method of claim 1, wherein the determining comprises: establishing a plurality of line segments each extending between corresponding points on each of the finder patterns; and identifying the top left finder pattern as the finder pattern that is common to the corresponding points having line segments extending over only white pixels. 8. The method of claim 7, wherein the image is tokenized into black or white tokens, and wherein the finder pattern common to two of the line segments that pass through only one white token is identified as the top left finder pattern. 9. The method of claim 7, wherein said points are the midpoints of the finder pattern edges. 10. The method of claim 1, wherein the determining comprises: calculating respective lengths of line segments extending between center points of each of the three finder patterns; and identifying the top left finder pattern as the finder pattern common to the two line segments that have a squared length sum that equals the square of the length of the third line segment. 11. The method of claim 10, wherein the skew and pitch sensitive technique comprises: determining a first inside edge line that is collinear with the inside edge of the bottom left finder pattern that faces the top left finder pattern; determining a second inside edge line that is collinear with the inside edge of the top right finder pattern that faces the top left finder pattern; determining a first midpoint of the outside edge of the bottom left finder pattern that is opposite the inside edge of the bottom left finder pattern; determining a second midpoint of the outside edge of the top right finder pattern that is opposite the inside edge of the top right finder pattern; determining a first outside edge point along the first inside edge line that coincides with an outside edge of the symbol; determining a second outside edge point along the second inside edge line that coincides with an outside edge of the symbol; determining a first outside edge line passing through the first midpoint and the second outside edge point; determining a second outside edge line passing through the second midpoint and the first outside edge point; and declaring the intersection of the first outside edge line and the second outside edge line to be the bottom right corner. 12. The method of claim 1, wherein the determining the first outside edge point comprises: defining a first set of test points along the first inside edge line between the intersection point of the first inside edge line and the second inside edge line and an arbitrary point outside of the symbol; beginning with the test point nearest the intersection point, defining a line segment extending from the second midpoint to the test point; examining if the line segment passes through only white pixels; and in the event that the line segment passes through only white pixels, deeming the test point as the first outside edge point; otherwise selecting the next test point and repeating the line segment defining and examining. 13. The method of claim 12, wherein the determining the second outside edge point comprises: defining a second set of test points along the second inside edge line between the intersection point of the first inside edge line and the second inside edge line and an arbitrary point outside of the symbol; beginning with the test point nearest the intersection point, defining a line segment extending from the first midpoint to the test point; examining if the line segment passes through only white pixels; and in the event that the line segment passes through only white pixels, deeming the test point as the second outside edge point, otherwise selecting the next test point and repeating the line segment defining and examining. 14. The method of claim 1, wherein said skew and pitch sensitive technique comprises: determining bottom and right side symbol edge points adjacent the bottom right corner of said symbol; and determining the intersection of a line extending from the bottom left finder pattern through the bottom symbol edge point and a line extending from the top right finder pattern through the right side symbol edge point thereby to determine the bottom right symbol corner. 15. The method of claim 1, wherein the two-dimensional machine-readable symbol is a QR-Code symbol. 16. A computer readable medium embodying a computer program executable by the computer for performing the method of claim 1. 17. An apparatus for extracting a bitstream from a machine-readable symbol in an image, the symbol comprising three square finder patterns adjacent respective corners of the symbol and generally defining the corners of a right-angled triangle, the apparatus comprising: a finder pattern identifier identifying the finder patterns in the symbol; a symbol orientor orienting the symbol using the finder patterns, the orienting comprising determining which of the three finder patterns is positioned at the corner of the triangle opposite its hypotenuse ("top left finder pattern"), and labeling the remaining two finder patterns based on the relative distance between the remaining two finder patterns that would result if one of the remaining two finder patterns were rotated about the top left finder pattern less than 180 degrees, wherein the labeling comprises: initially labeling the remaining two finder patterns respectfully as top right and bottom left finder patterns; rotating a selected one of the top right and bottom left finder patterns about the top left finder pattern; and after rotation, comparing the relative distance between the top right and bottom left finder patterns before and after rotation to verify the initial labeling; a symbol delineator for, on the basis of the orienting, delineating the symbol, wherein the delineating comprises: determining the top left, bottom left, and top right corners of the symbol based on the top left, bottom left and top right finder patterns; and using a skew and pitch sensitive technique based on the ton right and bottom left finder patterns to determine the bottom right corner of the symbol; a reference grid calculator for mapping a reference decoding grid to the delineated symbol; and a bit extractor for extracting bit values from the mapped symbol.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.