# US 2006/0153449 A1 · Block-based parallel image thinning methods, computer program products and systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0153449 A1
- Document ID: US20060153449A1
- Status: Published application
- Kind: A1
- Application number: 11/241,620
- Filed: 2005-09-30
- Published: 2006-07-13
- Earliest claimed: 2005-01-11
- Assignees: Samsung Electronics Co., Ltd.
- Inventors: Deok-soo Park; Dong-jae Lee
- Web page: https://patentgrep.com/patent/US20060153449A1

## CPC

- G06V 30/168: Smoothing or thinning of the pattern; Skeletonisation
- G06V 30/10: Character recognition
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A block-based parallel image thinning method segments an input image into blocks, determines the block flag of each of the segmented blocks, and determines a preservation condition of an object pixel of a corresponding block. Then, the method determines a removal condition of the object pixel for which the preservation condition has been determined, removes the value of the object pixel satisfying the removal condition and sets the block flag. When all the blocks have been thinned, the method thins the processed image into one-pixel thickness using a post processing condition. Related systems and computer program products also are provided.

## Claims

### Claim 1

An image thinning method comprising:
(a) segmenting an input image into blocks;
(b) determining a block flag of each of the segmented blocks;
(c) determining a preservation condition of an object pixel of a corresponding block;
(d) determining a removal condition of the object pixel for which the preservation condition has been determined;
(e) removing the value of the object pixel satisfying the removal condition and setting the block flag;
(f) determining whether all the blocks have been thinned and, when blocks to be thinned are left, iterating from (b) through (e); and
(g) processing the image obtained in (f) into one-pixel thickness using a post processing condition.

### Claim 2 (depends on 1)

The thinning method of claim 1, further comprising determining an image flag of the thinned image,
wherein a next input image is updated in response to the image flag and then (a) through (g) are iterated.

### Claim 3 (depends on 1)

The thinning method of claim 1, wherein the preservation condition includes horizontal, vertical and diagonal directions based on the object pixel.

### Claim 4 (depends on 3)

The thinning method of claim 3, wherein the condition of horizontal direction is set when a 1×4 window pattern including the object pixel P corresponds to 0-P-1-0.

### Claim 5 (depends on 3)

The thinning method of claim 3, wherein the condition of vertical direction is set when a 4×1 window pattern including the object pixel P corresponds to 0-P-1-0.

### Claim 6 (depends on 3)

The thinning method of claim 3, wherein the condition of diagonal direction is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 0-0-0-0-0-0-1-1.

### Claim 7 (depends on 3)

The thinning method of claim 3, wherein the condition of diagonal direction is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 1-0-0-0-0-0-0-1.

### Claim 8 (depends on 1)

The thinning method of claim 1, wherein the preservation condition includes B(p)=1 which is defined based on the number of black pixels, B(p), among eight neighborhood pixels surrounding the object pixel and the number of cases, A(p), where a pixel value 0 is changed to 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 9 (depends on 1)

The thinning method of claim 1, wherein the preservation condition includes B(p)=2 to 6 and A(p)>1 which is defined based on the number of black pixels B(p) among the eight neighborhood pixels surrounding the object pixel P and the number of cases, A(p), where a pixel value 0 is changed to 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 10 (depends on 1)

The thinning method of claim 1, wherein the preservation condition includes B(p)=8 which is defined based on the number of black pixels B(p) among the eight neighborhood pixels surrounding the object pixel P and the number of cases, A(p), where a pixel value 0 is changed to 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 11 (depends on 1)

The thinning method of claim 1, wherein the preservation condition is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 0-1-0-1-0-1-0-1.

### Claim 12 (depends on 1)

The thinning method of claim 1, wherein the removal condition includes B(p)=2 to 6 and A(p)>1 which is defined based on the number of black pixels B(p) among the eight neighborhood pixels surrounding the object pixel P and the number of cases, A(p), where a pixel value 0 is changed in 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 13 (depends on 1)

The thinning method of claim 1, wherein the removal condition is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 0-1-0-1-0-1-0-1.

### Claim 14 (depends on 1)

The thinning method of claim 1, wherein the post processing condition is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to x-0-x-x-1x-1-x (where x is don't care).

### Claim 15 (depends on 1)

The thinning method of claim 1, wherein the post processing condition is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 1-x-x-0-x x-1-x (where x is don't care).

### Claim 16 (depends on 1)

The thinning method of claim 1, wherein a data region for thinning has a size of (N+3)×(N+3) when the image is segmented into blocks each have a size of N×N.

### Claim 17 (depends on 1)

A computer program product for thinning an image, the computer program product comprising computer program code embodied in a computer-readable medium, the computer program code configured to provide the image thinning method of claim 1.

### Claim 18

An image thinning system comprising:
a block segmentation unit that is configured to receive an input image and to segment the image into blocks based on a kind of the image;
a thinning unit that is configured to thin the segmented blocks in parallel; and
a post processing unit that is configured to process an output of the thinning unit into one-pixel thickness.

### Claim 19 (depends on 18)

The thinning system of claim 18, wherein the thinning unit comprises:
a controller that is configured to distribute blocks to be processed in response to block flags of the segmented blocks;
a plurality of thinning blocks that are configured to thin the distributed blocks in parallel; and
an image reconstructing part that is configured to reconstruct an image from the images processed by the thinning blocks to determine whether the image has been thinned.

### Claim 20 (depends on 19)

The thinning system of claim 19, wherein each of the thinning blocks carries out preservation, removal and post-processing of an object pixel for the pixels in a corresponding block.

### Claim 21 (depends on 20)

The thinning system of claim 20, wherein the preservation preserves data of the object pixel in response to whether three conditions of horizontal, vertical and diagonal directions based on the object pixel are satisfied.

### Claim 22 (depends on 21)

The thinning system of claim 21, wherein the horizontal direction of the preservation condition is set when a 1×4 window pattern including the object pixel P corresponds to 0-P-1-0.

### Claim 23 (depends on 21)

The thinning system of claim 21, wherein the vertical direction of the preservation condition is set when a 4×1 window pattern including the object pixel P corresponds to 0-P-1-0.

### Claim 24 (depends on 21)

The thinning system of claim 21, wherein the diagonal direction of the preservation condition is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 0-0-0-0-0-0-1-1.

### Claim 25 (depends on 21)

The thinning system of claim 21, wherein the diagonal direction of the preservation condition is set when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 1-0-0-0-0-0-0-1.

### Claim 26 (depends on 20)

The thinning system of claim 20, wherein the preservation preserves the data of the object pixel when B(p)=1 which is defined based on the number of black pixels, B(p), among eight neighborhood pixels surrounding the object pixel and the number of cases, A(p), where a pixel value 0 is changed to 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 27 (depends on 20)

The thinning system of claim 20, wherein the preservation preserves the data of the object pixel when B(p)=2 to 6 and A(p)>1 which is defined based on the number of black pixels B(p) among the eight neighborhood pixels surrounding the object pixel P and the number of cases, A(p), where a pixel value 0 is changed to 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 28 (depends on 20)

The thinning system of claim 20, wherein the preservation preserves the data of the object pixel when B(p)=8 which is defined based on the number of black pixels B(p) among the eight neighborhood pixels surrounding the object pixel P and the number of cases, A(p), where a pixel value 0 is changed to 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 29 (depends on 20)

The thinning system of claim 20, wherein the preservation preserves the data of the object pixel when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 0-1-0-1-0-1-0-1.

### Claim 30 (depends on 20)

The thinning system of claim 20, wherein the removal removes the data of the object pixel when B(p)=2 to 6 and A(p)>1 which is defined based on the number of black pixels B(p) among the eight neighborhood pixels surrounding the object pixel P and the number of cases, A(p), where a pixel value 0 is changed in 1 when the values of the eight neighborhood pixels are checked clockwise.

### Claim 31 (depends on 20)

The thinning system of claim 20, wherein the removal removes the data of the object pixel when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 0-1-0-1-0-1-0-1.

### Claim 32 (depends on 20)

The thinning system of claim 20, wherein the post processing thins two-pixel thickness of the object pixel into one-pixel thickness when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to x-0-x-x-1x-1-x (where x is don't care).

### Claim 33 (depends on 20)

The thinning system of claim 20, wherein the post processing thins two-pixel thickness of the object pixel into one-pixel thickness when eight neighborhood pixels p2, p3, p4, p5, p6, p7, p8 and p9 of a 3×3 window pattern including the object pixel P at the center thereof, which are arranged clockwise starting from the position above the object pixel, correspond to 1-x-x-0-x x-1-x (where x is don't care).

### Claim 34 (depends on 18)

A computer program product for thinning an image, the computer program product comprising computer program code embodied in a computer-readable medium, the computer program code configured to provide the image thinning system of claim 18.
