Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік көру немесе табиғи тілді өңдеуде құжат макетін талдау – мәтіндік құжаттың сканерленген кескініндегі қызығушылық тудыратын аймақтарды анықтау және жіктеу процесі. Оқу жүйесі мәтіндік аймақтарды мәтіндік емес аймақтардан бөліп, оларды дұрыс оқу ретімен орналастыруды қажет етеді. Құжаттағы мәтін блогы, суреттер, математикалық символдар және кестелер сияқты әртүрлі аймақтарды (немесе блоктарды) анықтау және белгілеу – геометриялық макетті талдау деп аталады. Бірақ мәтіндік аймақтар құжат ішінде әртүрлі логикалық рөлдер атқарады (тақырыптар, түсіндірмелер, әйнекшелер және т.б.), ал осы семантикалық белгілеу логикалық макетті талдау саласына жатады. Құжат макетін талдау – геометриялық және логикалық белгілеудің біріктірілген түрі. Ол әдетте құжат кескінін OCR қозғалтқышына жібермес бұрын жасалады, бірақ оны үлкен мұрағаттардағы бірдей құжаттың дубликаттарын анықтау үшін немесе құжаттарды олардың құрылымы немесе кескіндік мазмұны бойынша индекстеу үшін де пайдалануға болады. Құжат макеті ISO 8613:1989 халықаралық стандартында ресми түрде анықталған.
In computer vision or natural language processing, document layout analysis is the process of identifying and categorizing the regions of interest in the scanned image of a text document. A reading system requires the segmentation of text zones from non textual ones and the arrangement in their correct reading order. Detection and labeling of the different zones (or blocks) as text body, illustrations, math symbols, and tables embedded in a document is called geometric layout analysis. But text zones play different logical roles inside the document (titles, captions, footnotes, etc.) and this kind of semantic labeling is the scope of the logical layout analysis. Document layout analysis is the union of geometric and logical labeling. It is typically performed before a document image is sent to an OCR engine, but it can be used also to detect duplicate copies of the same document in large archives, or to index documents by their structure or pictorial content. Document layout is formally defined in the international standard ISO 8613 1:1989.
Әдістердің жалпы сипаттамасы
Құжаттың макетін талдаудың екі негізгі тәсілі бар. Біріншіден, төменнен жоғарыға қарайғы тәсілдер бар, олар шикі пикселдік деректерге сүйене отырып, құжатты қайталап талдайды. Бұл тәсілдер әдетте құжатты қара және ақ түстермен байланысты аймақтарға бөледі, содан кейін бұл аймақтар сөздерге, одан кейін мәтін жолдарына және соңында мәтін блоктарына топтастырылады. Екіншіден, жоғарыдан төменге қарайғы тәсілдер бар, олар ақ кеңістік пен геометриялық ақпарат негізінде құжатты бағандар мен блоктарға қайталап бөлуге тырысады. Құжат макетін талдаудың кез келген тәсіліне ортақ екі мәселе бар: шу және қисықтық. Шу дегеніміз – тұз және бұрыш шуы немесе Гаусс шуы сияқты бейнедегі шу. Қисықтық – құжаттың кескінінің мәтін жолдары толық көлденең болмауы үшін бұрылуы мүмкін екендігі. Құжат макетін талдау алгоритмдері мен оптикалық таңбаларды тану алгоритмдерінде құжат кескініндегі таңбалар мәтін жолдары көлденең бағытта орналасқан деген жалпы болжам бар. Сондықтан, егер қисықтық болса, оны жою үшін құжат кескінін бұру маңызды. Осыдан кейін кез келген құжат макетін талдау кодын бастау үшін бейнедегі шуды жою және құжаттың қисықтық бұрышын бағалау қажет.
There are two main approaches to document layout analysis. Firstly, there are bottom up approaches which iteratively parse a document based on the raw pixel data. These approaches typically first parse a document into connected regions of black and white, then these regions are grouped into words, then into text lines, and finally into text blocks. Secondly, there are top down approaches which attempt to iteratively cut up a document into columns and blocks based on white space and geometric information. There are two issues common to any approach at document layout analysis: noise and skew. Noise refers to image noise, such as salt and pepper noise or Gaussian noise. Skew refers to the fact that a document image may be rotated in a way so that the text lines are not perfectly horizontal. It is a common assumption in both document layout analysis algorithms and optical character recognition algorithms that the characters in the document image are oriented so that text lines are horizontal. Therefore, if there is skew present then it is important to rotate the document image so as to remove it. It follows that the first steps in any document layout analysis code are to remove image noise and to come up with an estimate for the skew angle of the document.
Төменнен жоғарыға қарай әдістің үлгісі
Бұл бөлімде біз 1993 жылы О’Горман әзірлеген төменнен жоғарыға қарай құжат макетін талдау алгоритмінің қадамдарын қарастырамыз. Бұл тәсілдің қадамдары келесідей:
In this section we will walk through the steps of a bottom up document layout analysis algorithm developed in 1993 by O`Gorman. The steps in this approach are as follows:
Суретті Гаусс және «тұз бен бұрыш» шуын жою үшін алдын ала өңдеңіз. Кейбір шуды жою сүзгілері үтірлер мен нүктелерді шу ретінде қарастыруы мүмкін, сондықтан сақтық тану қажет. Суретті екі түсті суретке айналдырыңыз, яғни әрбір пикселдің мәнін толығымен ақ немесе толығымен қараға өзгертіңіз. Суретті қара пикселдердің байланысты компоненттеріне сегменттеңіз. Бұл суреттегі символдар. Әрбір символ үшін оны қоршайтын тіктөртбұрыш пен центроидты есептеңіз. Әрбір символ үшін k жақын көршісін анықтаңыз, мұнда k – төрттен үлкен немесе оған тең бүтін сан. О’Горман өз мақаласында беріктік пен жылдамдық арасындағы жақсы компромисс ретінде k=5 ұсынады. Кемінде k=4 пайдалану себебі – құжаттағы символ үшін ең жақын екі немесе үш символ сол мәтін жолында орналасқан. Төртінші жақын символ әдетте жоғарыда немесе төмендегі жолда болады, және осы символдарды келесі жақын көрші есептеуіне қосу маңызды. Әрбір жақын көрші символдар жұбы бір символдың центроидынан екінші символдың центроидына бағытталған вектормен байланысты. Егер осы векторлар жақын көрші символдардың барлық жұптары үшін салынса, құжат үшін «docstrum» деп аталатын нәрсе пайда болады (төмендегі суретті қараңыз). Сондай-ақ, екі жақын көрші символ арасындағы көлденеңнен Θ бұрышы мен D қашықтығын пайдаланып, жақын көрші бұрыштары мен жақын көрші қашықтықтарының гистограммасын жасауға болады. Жақын көрші бұрыштарының гистограммасын пайдаланып, құжаттың қисықтығын есептеуге болады. Егер қисықтық қанағаттанарлық деңгейде болса, келесі қадамға өтіңіз. Әйтпесе, қисықтықты жою үшін суретті бұрыңыз және 3-қадамға оралыңыз. Жақын көрші қашықтығының гистограммасында бірнеше шыңдар болады, және бұл шыңдар әдетте символдар арасындағы, сөздер арасындағы және жолдар арасындағы аралықты көрсетеді. Гистограммадан осы мәндерді есептеп, жазып қойыңыз. Әрбір символ үшін оның жақын көршілерін қарап, олардың арасында символдар арасындағы немесе сөздер арасындағы аралыққа толеранттылық шегіндегі қашықтықта орналасқандарын белгілеңіз. Белгіленген әрбір жақын көрші символ үшін олардың центроидтарын қосатын сызық сегментін салыңыз. Сызық сегменттері арқылы көршілерімен байланысқан символдар мәтін жолдары құрайды. Мәтін жолындағы барлық центроидтарды пайдаланып, сызықтық регрессия арқылы мәтін жолын көрсететін нақты сызық сегментін есептеуге болады. Бұл маңызды, өйткені мәтін жолындағы символдардың барлық центроидтары бір түзу бойында жатқандығын күту қиын. Әрбір мәтін жолдарының жұбы үшін олардың сәйкес сызық сегменттері арасындағы ең аз қашықтықты есептеңіз. Егер бұл қашықтық 7-қадамда есептелген жолдар арасындағы аралықтың толеранттылық шегінде болса, екі мәтін жолы бір мәтін блогына біріктіріледі. Соңында, әрбір мәтін блогы үшін оны қоршайтын тіктөртбұрышты есептеуге болады, және құжат макетін талдау аяқталады.
Preprocess the image to remove Gaussian and salt and pepper noise. Note that some noise removal filters may consider commas and periods as noise, so some care must be taken. Convert the image into a binary image, i. e. convert each pixel value to completely white or completely black. Segment the image into connected components of black pixels. These are the symbols of the image. For each symbol, compute a bounding box and centroid. For each symbol, determine its k nearest neighbors where k is an integer greater than or equal to four. O`Gorman suggests k=5 in his paper as a good compromise between robustness and speed. The reason to use at least k=4 is that for a symbol in a document, the two or three nearest symbols are the ones right next to it on the same text line. The fourth nearest symbol is typically on a line right above or below, and it is important to include these symbols in the nearest neighbor calculation for the following. Each nearest neighbor pair of symbols is related by a vector pointing from one symbol’s centroid to the other symbol’s centroid. If these vectors are plotted for every pair of nearest neighbor symbols, then one gets what is called the docstrum for the document (See figure below). One can also use the angle Θ from the horizontal and distance D between two nearest neighbor symbols and create a nearest neighbor angle and nearest neighbor distance histogram. Using the nearest neighbor angle histogram, the skew of the document can be calculated. If the skew is acceptably low, continue to the next step. If it is not, rotate the image so as to remove the skew and return to step 3. The nearest neighbor distance histogram has several peaks, and these peaks typically represent between character spacing, between word spacing, and between line spacing. Calculate these values from the histogram and set them aside. For each symbol, look at its nearest neighbors and flag any of them that are a distance away which is within some tolerance of the between character spacing distance or between word spacing distance. For each nearest neighbor symbol which is flagged, draw a line segment connecting their centroids. Symbols connected to their neighbors by line segments form text lines. Using all the centroids in a text line, one can compute an actual line segment representing the text line with linear regression. This is important because it is unlikely that all the centroids of symbols in a text line are actually collinear. For each pair of text lines, one can compute a minimum distance between their corresponding line segments. If this distance is within some tolerance of the between line spacing calculated in step 7, then the two text lines are grouped into the same text block. Finally, one can calculate a bounding box for each text block, and the document layout analysis is complete.
Жасауды талдау бағдарламалық жасақтамасы
OCRopus – C++ және Python тілдерінде және FreeBSD, Linux және Mac OS X жүйелері үшін іске асырылған, құжаттардың макетін талдауға және OCR жүйесіне арналған ақысыз бағдарлама. Бұл бағдарламалық қамтамасыз ету, пайдаланушыға әртүрлі құжат макетін талдау және OCR алгоритмдерін таңдауға мүмкіндік беретін қосымша архитектурасын қолдайды. OCRFeeder – Linux жүйесі үшін, Python тілінде жазылған, құжаттардың макетін талдауды да қолдайтын OCR жиынтығы. Бұл бағдарламалық қамтамасыз ету белсенді түрде дамытылуда, тегін және ашық кодты.
OCRopus – A free document layout analysis and OCR system, implemented in C++ and Python and for FreeBSD, Linux, and Mac OS X. This software supports a plug in architecture which allows the user to select from a variety of different document layout analysis and OCR algorithms. OCRFeeder – An OCR suite for Linux, written in python, which also supports document layout analysis. This software is actively being developed, and is free and open source.