CN102411788B - Area Filling Algorithm Based on Four-direction Scanning - Google Patents
Area Filling Algorithm Based on Four-direction Scanning Download PDFInfo
- Publication number
- CN102411788B CN102411788B CN201110243706.7A CN201110243706A CN102411788B CN 102411788 B CN102411788 B CN 102411788B CN 201110243706 A CN201110243706 A CN 201110243706A CN 102411788 B CN102411788 B CN 102411788B
- Authority
- CN
- China
- Prior art keywords
- scanning
- color
- scan
- edge
- area
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Image Analysis (AREA)
- Image Generation (AREA)
- Image Processing (AREA)
Abstract
The invention belongs to the digital image processing technology field, concretely relating to an area filling algorithm based on a four-way scan mode. Through setting a specific edge point in a binary edge image as a starting point, the edge image is subjected to scan in four directions, a closed area enclosed by closed edge lines is screened, and other noises in an unclosed area and the edge image are effectively eliminated. A realization mode of the invention is simple, no complex operation is needed, and the closed area can be accurately screened from the complex edge image. The whole algorithm is operated automatically with no need of human intervention and without recursion operation, and is very suitable for parallel realization. Extraction of the closed area in the complex changeable edge image can not be realized in other area filling algorithms, but according to the invention, the extraction of the closed area in the complex changeable edge image is realized. Simultaneously, compared with the other algorithms, the algorithm in the invention has much higher execution efficiency in hardware with parallel operation as main operation.
Description
Technical field
The invention belongs to the digital image processing techniques field, be specifically related to the region-filling algorithm based on the four-way scan mode.
Background technology
The enclosed region of edge image is all often significant part in image, and extract these enclosed region, gets rid of non-enclosed region simultaneously and just can realize the complete image Segmentation Technology based on edge image.This partitioning scheme, except its parallel characteristics and less this advantage of operand, is also a kind of based on geological information but not the image Segmentation Technology that colouring information is realized simultaneously.And often more can reflect on the whole the meaningful object in image compared with the colouring information geological information, therefore rapidly and accurately the enclosed region of complex edge image being filled to extract has boundless application prospect.
Existing enclosed region filling mode mainly contains se ed filling algorithm, edge filling method, orderly Bian Biaofa, limit notation
[1-4].Se ed filling algorithm specifies a pixel to fill by the recursive fashion feasible region as Seed Points by artificial in enclosed region, because it needs the man-machine interactively operation, so the algorithm versatility is less.The edge filling method is based on each limit of polygon and fills to the right in an orderly manner, and by the filling to enclosed region to the final realization of the continuous negate of filling part, this method only is suitable for the few polygon of limit number and fills.Orderly Bian Biaofa, by obtaining the intersection point of horizontal scan line and enclosed region, the line ordering of going forward side by side, judge again the sweep trace of present intra-zone according to parity, thereby feasible region is filled, the fine while algorithm of this algorithm versatility can automatically be realized without manual intervention, thereby but shortcoming is to need cap and sort operation to reduce the execution efficiency of algorithm.The limit notation is the improvement to orderly Bian Biaofa, thereby has removed cap from and sort operation has promoted efficiency.
Yet these algorithms have a common deficiency, and they can't process the edge image that comprises noise and non-enclosed region simultaneously, though these algorithms can correctly be filled enclosed region and also can be filled out non-enclosed region by mistake.And the present invention can address this problem fully, not only can fill simultaneously but also avoid the mistake of non-enclosed region is filled the enclosed region in the complex edge image.Thereby although there will be in algorithm, same pixel repeatedly being accessed on efficiency to some extent and descended, because its splendid parallel characteristics can make up this defect fully, is that main hardware is carried out in as GPU and still high efficiency can be arranged take parallel processing.
list of references:
［1］Pavlidis?T.?Filling?Algorithms?for?Raster?Graphics[J].?Computer?Graphics?Image?Process,?1979,?10(2):?126—141．
［ 2 ］ Zhang Yinghui, Zhang Yulian.A kind of improved edge filling algorithm ［ J ］.University On The Mountain Of Swallows's journal, 2000,24 (1): 47-49.
［ 3 ］ Liu Chun.Fast area filling algorithm ［ J ］ based on boundary scan.Computer programming skill and maintenance, 2010,7:66-68.
［4］ACKLAND?B.D,?WESTE?N.H,?The?edge?flag?algorithm-A?fill?method?for?raster?scan?displays[J].?IEEE?Trans.?Comput.?C-30,?1981,?1:?762-791.。
Summary of the invention
The object of the invention is to propose a kind of simple, fast, accurately, but the padding of executed in parallel feasible region is given in the region-filling algorithm of getting rid of non-enclosed region and picture noise.
The present invention can be used in the edge image of any complexity, rely on simple scanning can't fill these characteristics of breach of non-enclosed region, inheritance by detecting look and fill color by this breach information after scanning in constantly amplify the formation positive feedback, finally make whole non-enclosed region be excluded, and enclosed region is unaffected, therefore can realize both having kept algorithm to be carried out by independent parallel between each marginal point, the while can extract enclosed region on the whole again and get rid of non-enclosed region and noise from edge image.Whole algorithm all operations occurs over just between the marginal point in outline map, pixel between putting by edge carries out that four direction scanning detects and repeat number time, finally retains the color of last scanning filling and removes all the other fill colors and realize the extraction to the enclosed region in the complex edge image.
The region-filling algorithm that the present invention proposes, be based on based on the four-way scan mode, and concrete steps are as follows:
Step 1, scanned from top to bottom from start edge point;
Step 2, scanned from left to right from start edge point;
Step 3, scanned from bottom to top from start edge point;
Step 4, scanned from right-to-left from start edge point;
Step 5, repeat 1 ~ 4 step N time;
Step 6, retain the last Fill Color scanned, and all the other fill colors is set to the background colour of two-value outline map.
Below each step is further described in detail.
In step 1, first by the user, specify initial edge to detect look, because edge image is bianry image, so initial edge detects the background colour (black or white) that look is edge image.The initial direction of scanning can be any direction of four direction, but has determined that 3 direction of scanning after initial direction must form clockwise or counterclockwise order with initial direction.It is example as initial direction of scanning from top to bottom that the present invention be take, first search for a pixel compartments under all marginal points of binary edge map and current marginal point, if under marginal point, its color of lattice pixel is that initial edge detects look, this marginal point is sweep starting point.But Parallel Implementation scan operation between each starting point.
The user also needs to specify a sweep length parameter L, and the user can specify common sweep length parameter for the scanning of four direction, and different sweep length parameters is specified in the scanning that also can be respectively four direction, is determined on a case-by-case basis.
From starting point start along under the pointwise picture element scan, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm from current initial scanning success of lighting, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For scanning successful situation, (scanning that this color value also will become next direction detects colour to detect the same another kind of color value filled coloring for pixel compartments of form and aspect with scanning during all scanning is detected, this numerical value can be arbitrary constant, if can with edge image in other value distinguishing in order to accurately detected while once scanning upper).For scanning failed situation, be left intact, keep intact.
In step 2, carry out scanning direction from left to right, it be the last fill color scanned that the scanning of this scanning detects look, and sweep length L value can scan and identically also can specify in addition with the last time.
A pixel compartments of all marginal points of search edge image and current marginal point the right, if marginal point the right one its color of lattice pixel detects look for scanning, this marginal point is sweep starting point.
From starting point, start along the right pointwise picture element scan of X axis, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm from current initial scanning success of lighting, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For the successful situation of scanning, during all scanning is detected with scanning detect form and aspect with pixel compartments be different from another kind of the color value filled coloring that step 1, step 2 scanning detect look, for scanning failed situation, be left intact, keep intact.
In step 3, scan from the bottom to top, it be the last fill color scanned that the scanning of this scanning detects look, and sweep length L value can scan and identically also can specify in addition with the last time.
A pixel compartments directly over all marginal points of search edge image and current marginal point, if directly over marginal point, its color of lattice pixel detects look for scanning, this marginal point is sweep starting point.
From starting point start along directly over the pointwise picture element scan, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm from current initial scanning success of lighting, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For scanning successful situation, during all scanning is detected with scanning detect form and aspect with the another kind of color value filled coloring that is different from step 1, step 2, step 3 scanning detection look for pixel compartments, for scanning failed situation, be left intact, keep intact.
In step 4, scanned from right to left, it be the last fill color scanned that the scanning of this scanning detects look, and sweep length L value can scan and identically also can specify in addition with the last time.
All marginal points and one, the current marginal point left side pixel compartments of search edge image, if the marginal point left side one its color of lattice pixel detects look for scanning, this marginal point is sweep starting point.
From starting point, start along the left pointwise picture element scan of X axis, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm the scanning success from current starting point, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For scanning successful situation, during all scanning is detected with scanning detect form and aspect with the another kind of color value filled coloring that is different from step 1, step 2, step 3, step 4 scanning detection look for pixel compartments, for scanning failed situation, be left intact, keep intact.
In step 5, repeat 1 ~ 4 step N time.For complicated edge image, some non-enclosed region can't only be got rid of by 1 four-way scanning fully, need to repeatedly carry out could fully non-enclosed region eliminating only being retained to enclosed region after several, this multiplicity N will be specified by the user, can be any positive integer, can establish greatly for complicated image N value, simple image N value can be established little, generally speaking, N can get rid of in the complex edge image non-enclosed region arbitrarily at 3 o'clock substantially fully.
The preliminary sweep that circulation starts detects the background colour that look is binary edge map, and the last scanning circulated before finishing will be retained the unique tag as the enclosed region to extracting because of filled color value, so the requirement of last fill color not only can not be with the used Fill Color while also requires it to have the processing that definite meaning is convenient to the later stage before.These color values finally can be removed the background colour that namely again is set to edge image as for all the other fill colors of using because of it in cyclic process, so can replace as long as guarantee different with simple continuous integral number.
Step 6, in this step, by the fill color of a preserving edge color and last scanning, remaining fill color is as all be set to the background colour of original binary edge map without special circumstances (carrying out the color value that other algorithms retain).The fill color finally stayed is the enclosed region surrounded by the closure edge line in edge image.
Whole algorithm has two large advantages, and the one, only have comparison operation without any arithmetic operator fully, simultaneously also without any recurrence or cap, so algorithm extremely simply all can be realized easily in any hardware.The secondth, whole algorithm is all to take marginal point to be carried out as unit, between marginal point without any message exchange or wait for the execution result of other marginal points, therefore algorithm has very strong parallel characteristics, although the repeatedly access to same pixel may occur, but the advantage of its parallel characteristics still can make up the increase that algorithm repeats the operand brought, so the present invention is very suitable on main hardware, realizing take concurrent operation.
The accompanying drawing explanation
Fig. 1 is that a four-way scanning area filling realizes procedure chart.
Fig. 2 is whole algorithm flow chart.
Embodiment
Below in conjunction with accompanying drawing, the specific embodiment of the present invention is further described.
Figure 2 shows that the particular flow sheet of whole algorithm in the present invention.
Step 1, first specify initial edge to detect look (background colour of binary edge map) by the user.Start from top to bottom to scan, first search for a pixel compartments under all marginal points of binary edge map and current marginal point, if under marginal point, its color of lattice pixel is that initial edge detects look, this marginal point is sweep starting point, and the user also needs to specify a sweep length parameter L.
From starting point start along under the pointwise picture element scan, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm from current initial scanning success of lighting, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For scanning successful situation, will in all scanning detections, with scanning, detect the same another kind of color value filled coloring for pixel compartments of form and aspect.For scanning failed situation, be left intact and keep intact.
Next be step 2, scanned from left to right.It is the last fill color scanned that the scanning of this scanning detects look, and sweep length L value can scan and identically also can specify in addition with the last time.
A pixel compartments of all marginal points of search edge image and current marginal point the right, if marginal point the right one its color of lattice pixel detects look for scanning, this marginal point is sweep starting point.
From starting point, start along the right pointwise picture element scan of X axis, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm from current initial scanning success of lighting, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For the successful situation of scanning, during all scanning is detected with scanning detect form and aspect with pixel compartments be different from another kind of the color value filled coloring that step 1, step 2 scanning detect look, for scanning failed situation, be left intact and keep intact.
Step 3 is served as reasons down to enterprising line scanning.It is the last fill color scanned that the scanning of this scanning detects look, and sweep length L value can scan and identically also can specify in addition with the last time.
A pixel compartments directly over all marginal points of search edge image and current marginal point, if directly over marginal point, its color of lattice pixel detects look for scanning, this marginal point is sweep starting point.
From starting point start along directly over the pointwise picture element scan, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm from current initial scanning success of lighting, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For scanning successful situation, during all scanning is detected with scanning detect form and aspect with the another kind of color value filled coloring that is different from step 1, step 2, step 3 scanning detection look for pixel compartments, for scanning failed situation, be left intact and keep intact.
Step 4 is scanned from right-to-left.It is the last fill color scanned that the scanning of this scanning detects look, and sweep length L value can scan and identically also can specify in addition with the last time.
All marginal points and one, the current marginal point left side pixel compartments of search edge image, if the marginal point left side one its color of lattice pixel detects look for scanning, this marginal point is sweep starting point.
From starting point, start along the left pointwise picture element scan of X axis, if the pixel color value of scanning detects form and aspect with continuing scanning with scanning, if find other marginal points in scanning process or scan the image boundary position, confirm from current initial scanning success of lighting, and finish from current initial scanning of lighting.If before running into other marginal points or arriving the image boundary position, occurred that scanning element point color and scanning detect the sweep length parameter L that look different or length scanning has been greater than user's appointment, announce from current initial scanning failure of lighting, and finish from current initial scanning of lighting.
For scanning successful situation, during all scanning is detected with scanning detect form and aspect with the another kind of color value filled coloring that is different from step 1, step 2, step 3, step 4 scanning detection look for pixel compartments, for scanning failed situation, be left intact and keep intact.
Step 5 is for repeating 1 ~ 4 step N time, and this multiplicity N will be specified by the user, for complicated image N value, can establish greatly, and simple image N value can be established little.
Should be noted that it is that the preliminary sweep that circulation starts detects the background colour that look is binary edge map, and last fill color requires to have the processing that definite meaning is convenient to the later stage.As for all the other fill colors of using in cyclic process, can replace as long as guarantee different with simple continuous integral number.
Last be the Fill Color that retains last scanning, all the other fill colors are set to the background colour of two-value outline map.The fill color finally stayed is the enclosed region surrounded by the closure edge line in edge image.
Fig. 1 is that a four-way scanning area filling realizes that procedure chart, the redness finally retained are exactly the enclosed region in image.
Claims (1)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110243706.7A CN102411788B (en) | 2011-08-24 | 2011-08-24 | Area Filling Algorithm Based on Four-direction Scanning |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110243706.7A CN102411788B (en) | 2011-08-24 | 2011-08-24 | Area Filling Algorithm Based on Four-direction Scanning |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102411788A CN102411788A (en) | 2012-04-11 |
| CN102411788B true CN102411788B (en) | 2014-01-08 |
Family
ID=45913852
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201110243706.7A Expired - Fee Related CN102411788B (en) | 2011-08-24 | 2011-08-24 | Area Filling Algorithm Based on Four-direction Scanning |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102411788B (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110246173B (en) * | 2018-08-14 | 2023-11-03 | 浙江大华技术股份有限公司 | Method and device for judging shape area |
| CN113284154B (en) * | 2021-05-25 | 2022-04-26 | 武汉钢铁有限公司 | Steel coil end face image segmentation method and device and electronic equipment |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1380543A (en) * | 2001-04-12 | 2002-11-20 | 清华大学 | Image segmentation and identification method in industrial radiation imaging system |
| CN101398894A (en) * | 2008-06-17 | 2009-04-01 | 浙江师范大学 | Automobile license plate automatic recognition method and implementing device thereof |
-
2011
- 2011-08-24 CN CN201110243706.7A patent/CN102411788B/en not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1380543A (en) * | 2001-04-12 | 2002-11-20 | 清华大学 | Image segmentation and identification method in industrial radiation imaging system |
| CN101398894A (en) * | 2008-06-17 | 2009-04-01 | 浙江师范大学 | Automobile license plate automatic recognition method and implementing device thereof |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102411788A (en) | 2012-04-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10489970B2 (en) | 2D image processing for extrusion into 3D objects | |
| JP7242165B2 (en) | Program, Information Processing Apparatus, and Method | |
| CN109376659A (en) | Training method, face critical point detection method, apparatus for face key spot net detection model | |
| JP2018520428A (en) | Image processing method and apparatus | |
| CN106952271A (en) | An Image Segmentation Method Based on Superpixel Segmentation and EM/MPM Processing | |
| CN105513105B (en) | Image background weakening method based on notable figure | |
| JP6261301B2 (en) | Medical image display device and control method thereof | |
| CN109767479B (en) | Dynamic boundary group sequence-based primitive filling method and system | |
| CN105261049B (en) | A kind of image connectivity region quick determination method | |
| US20170132837A1 (en) | 2d image processing for extrusion into 3d objects | |
| CN113469929B (en) | Training data generation method and device, electronic equipment and computer readable storage medium | |
| Dai et al. | Example-based facade texture synthesis | |
| CN104809694A (en) | Digital image processing method and digital image processing device | |
| EP4075373A1 (en) | Image processing method and apparatus | |
| CN109389607A (en) | Ship Target dividing method, system and medium based on full convolutional neural networks | |
| CN108470185A (en) | The atural object annotation equipment and method of satellite image | |
| CN104008547A (en) | Method for visible serial segmentation of human body slice images based on skeleton angular points | |
| CN110070548A (en) | A kind of deep learning training sample optimization method | |
| CN102411788B (en) | Area Filling Algorithm Based on Four-direction Scanning | |
| CN104166958A (en) | Area-of-interest displaying and operating method | |
| CN108805022A (en) | A kind of remote sensing scene classification method based on multiple dimensioned CENTRIST features | |
| CN102768763A (en) | Method and device for outlining characters | |
| CN103164843B (en) | A kind of medical image colorize method | |
| CN113706645A (en) | Information processing method for landscape painting | |
| CN105354833B (en) | A kind of method and apparatus of shadow Detection |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20140108 |