Method and device for detecting connected pixels in image

• US 10,019,807 B1
• Filed: 12/05/2017
• Issued: 07/10/2018
• Est. Priority Date: 03/31/2017
• Status: Active Grant

• Current Assignee: MVTech Co., Ltd.
• Original Assignee: MVTech Co., Ltd.
• Inventors: Kwon, Ki Sun, Song, Jong Hyun
• Primary Examiner(s): Lee, Jonathan S
• Application Number:
  US15/832,738
• Time in Patent Office: 217 Days
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/32 using correlation-based methods

Abstract

A method and device for detecting connected pixels in a two-dimensional (2D) image having a plurality of pixels each having X-Y coordinates may compare an upper-row pixel included in a Yth row with a lower-row pixel included in a Y+1th row depending on a comparison condition, wherein Y is a positive integer, and wherein when a difference in X coordinate between the upper-row pixel and the lower-row pixel is one or less, the upper-row pixel and the lower-row pixel are determined to be positioned adjacent each other, and when the difference in X coordinate is two or more, the upper-row pixel and the lower-row pixel are determined to be spaced apart from each other and update an index map that defines a relationship between index numbers of adjacent pixels depending on the determination to set pixels with the same or associated index number in the same pixel group.

Claims

1. A method for detecting connected pixels in a two-dimensional (2D) image having a plurality of pixels each having X-Y coordinates, the method comprising:

comparing an upper-row pixel included in a Yth row with a lower-row pixel included in a Y+1th row depending on a comparison condition, wherein Y is a positive integer, and wherein when a difference in X coordinate between the upper-row pixel and the lower-row pixel is one or less, the upper-row pixel and the lower-row pixel are determined to be positioned adjacent each other, and when the difference in X coordinate is two or more, the upper-row pixel and the lower-row pixel are determined to be spaced apart from each other; and

updating an index map that defines a relationship between index numbers of adjacent pixels depending on the determination to set pixels with the same or associated index number in the same pixel group, wherein updating the index map includes;

identifying the indexed pixels having the same or associated number by referring to the index map; and

obtaining a maximum value and a minimum value of the X coordinates of the identified indexed pixels and a maximum value and a minimum value of the Y coordinates of the identified indexed pixels to generate a rectangular pixel group.

2. The method of claim 1, further comprising:

defining a plurality of indexed pixels by assigning the same index number to two or more horizontally adjacent ones of the pixels;

storing the indexed pixels in a first array;

generating the index map depending on the index numbers of the indexed pixels;

obtaining memory addresses of leftmost pixels in rows among the plurality of indexed pixels; and

storing the memory addresses in a second array.

3. The method of claim 2, wherein the comparison includes:

setting a U-th indexed pixel and a U+1th indexed pixel of the second array to the upper-row pixel and the lower-row pixel, respectively, wherein U is a positive integer.

4. The method of claim 3, wherein when an X coordinate of the upper-row pixel is smaller than an X coordinate of the lower-row pixel, an indexed pixel next to the upper-row pixel in the first array is set as the upper-row pixel, and when a Y coordinate of the upper-row pixel is identical or larger than a Y coordinate of the lower-row pixel, an indexed pixel next to the lower-row pixel is set as the lower-row pixel, and wherein when the upper-row pixel is set as an indexed pixel of the second array, U is increased by one.

5. The method of claim 4, wherein when a difference in X coordinate between the upper-row pixel and the lower-row pixel is one or less, the index map is updated with the smaller of an index number associated with the upper-row pixel and an index number associated with the lower-row pixel.

6. The method of claim 1, wherein the index map is updated by applying a function represented as below inversely from f(N) to f(1), wherein N is a maximum index number of the indexed pixels:

7. A device for detecting connected pixels in a 2D image including a plurality of pixels each of which has X and Y coordinates, the device comprising:

an indexing processor for assigning an index number to each of the plurality of pixels, generating one or more arrays, and storing information about the plurality of pixels;

a pixel comparator for comparing an upper-row pixel included in a Yth row with a lower-row pixel included in a Y+1th row according to a comparison condition, determining that the upper-row pixel and the lower-row pixel are positioned adjacent each other when a difference in X coordinate between the upper-row pixel and the lower-row pixel is one or less and that the upper-row pixel and the lower-row pixel are spaced apart from each other when the difference in X coordinate is two or more, and updating an index map depending on the determination, the index map defining a relationship in index number between adjacent pixels; and

a detector for setting a pixel group for pixels having the same or associated index number based on the updated index map, identifying a plurality of indexed pixels having the same or associated number by referring to the index map, and extracting the maximum and minimum X coordinates and the maximum and minimum Y coordinates of the identified indexed pixels to create or draw a rectangle forming a pixel group.

8. The device of claim 7, wherein the indexing processor includes:

an array generator for assigning the same index number to two or more pixels that are positioned horizontally adjacent each other, defining a plurality of indexed pixels, storing the plurality of indexed pixels in a first array, extracting memory addresses for pixels having minimum X coordinates in rows among the plurality of indexed pixels, and storing the memory addresses in a second array; and

an index map generator for generating the indexed pixel according to index numbers of the plurality of indexed pixels.

9. The device of claim 8, wherein the pixel comparator includes:

a comparator for setting a Uth indexed pixel of the second array and a U+1th indexed pixel of the second array as the upper-row pixel and the lower-row pixel, respectively, and comparing the upper-row pixel with the lower-row pixel, wherein U is a positive integer; and

an updater for updating the index map with the smaller of the index numbers associated with the upper-row pixel and the lower-row pixel in the index map when the comparator determines that the difference in X coordinate between the upper-row pixel and the lower-row pixel is one or less.

10. The device of claim 9, wherein when the comparator determines that the X coordinate of the upper-row pixel is smaller than the X coordinate of the lower-row pixel, the comparator resets the next indexed pixel in the corresponding row of the first array as the upper-row pixel and compare the reset upper-row pixel with the lower-row pixel, wherein when the comparator determines that the Y coordinate of the upper-row pixel is equal or larger than the Y coordinate of the lower-row pixel, the comparator resets the next indexed pixel in the corresponding row as the lower-row pixel and compare the upper-row pixel with the reset lower-row pixel, and wherein when an indexed pixel in the second array is set as the upper-row pixel, the comparator increases U by one.

11. The device of claim 10, wherein when a difference in X coordinate between the upper-row pixel and the lower-row pixel is one or less, the updater updates the index map with the smaller of an index number associated with the upper-row pixel and an index number associated with the lower-row pixel.