圖象處理系統的製作方法
2023-10-10 04:09:19
專利名稱:圖象處理系統的製作方法
本發明涉及用來產生一個滿區域或描繪圖象的圖象處理系統，此圖象是用一個圖象再生裝置再生成的，諸如一臺圖象顯示裝置，帶有一個陰極射線管或帶有一個列印頭的圖象印表機。本發明特別涉及一個適合在光柵型陰極射線顯示器中，顯示一個滿區域圖象的圖象處理系統。
用一系列線段或一系列矢量給出組成一幅圖象的輪廓線，並且忽略掉水平線段。除水平線段外的每一線段，通過從起點到終點的坐標地址，並以自頂到底或自底到頂的一個方向來表明。於是在X-Y坐標系統中，將線段變換至近似的象素，並儲存在一隨機存儲器中。按照每一水平線一個象素代表每個線段的這一規則，將每條線段的那些象素存儲在工作存儲器中，並且在工作存儲器中讀出對應坐標地址的象素數值，去掉起點，然後進行象素的異門運算寫入。於是，輪廓線的偶數象素存在於工作存儲器的每一水平線上。因此，區域填滿能夠用掃描存儲器的每一水平線，並且通過從一奇數輪廓線象素，到一偶數輪廓線象素接通象素存儲器單元來實現。這種技術能夠容易地完成區域填滿，甚至可用於任何複雜的圖象上。
區域填滿或描繪是圖象處理系統中的一種基本的處理圖象功能，並且曾提出過各種技術。最基本的技術是用軟體對指定的區域以每一象素逐一填滿於一隨機存取存儲器中，以致在指定的區域填滿所有的象素。然而，用軟體填滿區域存在著處理時間較長的問題。
美國專利NO，4，189，743公開了一種區域填滿技術，其中寫入一隨機存取存儲器的一個封閉輪廓線區中任何一點，可選作種子點，此區域填滿是這樣完成的，首先通過在輪廓線範圍內的種子點填滿象素線，然後通過填滿鄰近於這條象素線的象素線，並且重複這樣的過程，此過程需要非常複雜的程序。
日本審查過的專利公告號NO，40179/79公開了顯示一種滿區域圖象技術，在這種技術中，用有選擇地省去一些輪廓線點來寫出一輪廓線圖形，以致在一刷新存儲器中的每一象素線包括了偶數輪廓線點。當象素線以光柵型陰射線管掃描同步讀出時，加於陰極射線管的視頻信號接通於奇數輪廓線點，並且關掉了偶數輪廓線點。然而，該專利具有這樣的問題，即由於省掉一些明顯的點，填滿圖象出現了畸變、處理圖象受到了限制並且不能在刷新存儲器中處理圖象。此專利未公開方位矢量數據的應用和終點處理以及用本發明的異門進行區域填滿技術。
因此，本發明的目的是提供一圖象處理系統，該系統基於以矢量數據代表一系列線段構成圖象輪廓的方法，能高速和容易地產生一個複雜的滿區域圖象。
本發明按照予定規則產生輪廓線，並把它們儲存在一隨機存取存儲器中。輪廓線以一系列線段或矢量來確定，但是不用水平線段。除水平線段外，每一線段都用從頂部到底部或從底部到頂部一個方向來確定，並轉換成近似的象素。每一線段都表示在每一水平基線的一個象素上，但它的起點沒有寫出。每一象素通過象素數據的異門操作寫入隨機存取存儲器中，而此數據從隨機存取存儲器相應的坐標地址讀出。因此，偶數輪廓線象素存在於隨機存取存儲器內的每一水平線中，以致任何複雜圖象可用奇-偶反轉寫入的方法，很容易地進行區域填滿。
首先，對按照本發明的區域填滿技術的概要和其中所用的處理規則作一說明。
圖2示出了寫在隨機存取存儲器中的閉合輪廓線的象素點，此存儲器儲存對應於二維平面XY的二維圖象的象素數據。假設對每條水平象素線掃描輪廓線象素，並且用奇-偶反轉寫入方法進行區域填滿，其中各點是這樣安排進行的，即從一奇數輪廓線象素到下一個偶數象素。如奇數輪廓線象素存在於一象素線上，於是便產生這樣一個問題，即不待填滿的區域，諸如圖2中的l1，l2，l3和l4將被填滿，而待填滿的區域諸如線l3的虛線部分卻不被填滿。
如圖3(A)所示，本發明以這樣一種方式將輪廓線寫在隨機存取存儲器中，以致每一象素線總是含有偶數輪廓線象素，因此用奇-偶反轉寫入法可以容易地將區域填滿。在圖3中，「X」表示沒有寫入的一個輪廓線象素。
按照本發明，構成一個圖象的輪廓線，是用一系列的線段或矢量表示的。線段可轉換為近似的象素點，根據每條線段所指明起點和終點的坐標數據，將它們儲存在隨機存取存儲器中。本發明利用下列五條規則來寫入圖3所示的輪廓線象素。
規則1不寫水平線段。
規則2把每條線段表示在每條水平基線的一個象素上。
規則3不寫每條線段的起點。
規則4利用象素數據(它貯存在存儲器內該象素想要寫入的地
址中)進行異門邏輯運算來寫輪廓線象素。
規則5以一個方向從頂至底或從底至頂確定每一線段。
規則1用以防止奇數輪廓線象素由於包含在一個水平線區域的輪廓線象素的存在而出現在一條線上，諸如圖2中線l2上的象素P1-P2。因為有很多水平線用於通常的圖象處理中。省掉水平線段，也可提高區域填滿處理的速度。
規則2是表示以每條線上的一個象素輪廓與線段的角度無關。例如在圖4的情形中，相近各點產生的線段具有起點S和終點E，並與水平線構成小於45°的角，而且多數的點產生在一條直線上。在這種情形下，首先產生的點d1和d2用作輪廓線點，但是隨後產生的點d3和d4沒有寫出。
規則3用以消去向上或向下的頂點。如果在一個方向上確定線段，例如按照規則5從頂至底規則3消去輪廓線象素P5和P10，這些點在圖2中是向上的頂點。
規則4和5消去頂點的輪廓線象素，此頂點和用規則3處理點的方向相反(比例見第7頁)。
現在說明寫出圖3(A)中輪廓線象素圖形的程序。在圖3中的輪廓用6條線段確定。假設這些線段指定的方向為從頂到底，它們用P5→P3，P5→P6，P6→P7，P10→P7，P10→P12和P1→P15來表示。象素P1-P2，P13-P14因系水平線段而略去。對於線段P5→P3，由於象素P5為起點而沒有寫出，但是下面的象素寫出了，直到終點象素P3。這種寫入通過待寫的象素數據和從存儲器地址中讀出的象素數據(前面的數據待寫入到該地址中)的異門邏輯寫入來完成的。假設用二進位的1來代表輪廓線象素，而存儲器讀出的數據為二進位的0，則可以這樣來寫出輪廓線象素點數據。
同樣，對於線段P5→P6，其起點P5沒有寫出，但是其餘的象素均置位於二進位的1。對於線段P6→P7，雖然起點P6沒有寫出，但P6已作為線段P5→P6寫出了。在起點P6之後的(包括終點P7)各象素用異門邏輯運算寫入。
對於線段P10→P7沒有寫出起點P10，但是寫出了起點以後的各象素。因為終點P7為二進位的1，作為線段P6→P7寫出的結果，終點P7的異門邏輯運算寫入將它恢復為二進位的0，並且從輪廓線上消去向下的頂點P7。與此類似也寫出線段P10→P12和P1→P15輪廓線的各點。
在輪廓線象素完全寫入後，對存儲器中每條線進行掃描，並且完成填滿工作，這樣對存儲器的點從奇數輪廓線象素到下一個出現的偶數輪廓線象素以二進位的1填滿。在這種情形中，由於下面所討論的原因，最好取偶數輪廓線象素為二進位的0。通過從存儲器中讀出每行象素數據，並取每一象素和同一線上緊挨著前面的象素進行異門邏輯運算，以及寫出其結果，可以令人滿意地完成寫入程序。因此如圖3(B)所示，在奇數輪廓線各象素後面的二進位0象素，均置於二進位的1。雖然象素P10在寫輪廓線時消去，它在填滿工作期間置於二進位的1。在開始時被忽略的象素P13和P14也被填滿了。開始時被消去的象素P1-P2，P5-P7，均從滿區域圖象中除去。這裡要注意的是在P3，P4，P8，P9和P15-P16每條線上的所有偶數輪廓線象素，均通過異門邏輯填滿操作被除去。因此，結果圖象的畸變和上面提到的日本審查過的專利公告號No·40179/79的方法相比，可使它減到最小，在該專利號中各頂點簡單的略去了。而且偶數輪廓線象素的消除提供了一個優點，即容易產生相近的圖象。這將在以下說明。
圖1表示應用在一個光柵掃描型陰極射線管圖象顯示系統的本發明的實施例。一個微處理器10通過一地址線12和一數據線14連接到一個刷新存儲器50上，然後將刷新存儲器接到一光柵掃描型陰極射線管顯示器70。刷新存儲器50是一個隨機存取存儲器，它具有一些儲存單元以對應於顯示器70的各個象素點。這個顯示系統也包括一輪廓線書寫滿區域控制器20，一個線段-象素點變換器30，和一個工作存儲器60，此存儲器用來儲存一滿區域圖象。雖然這種實施例在工作存儲器60中產生了一滿區域圖象，但為了顯示將此存儲器60又寫入刷新記憶器50中，這樣，就可能把一個滿區域圖象直接寫入刷新存儲器50中。然而，最好使用一個分開的工作記憶器60，這是因為如果刷新存儲器具有任何圖象數據時，控制將變得非常複雜。特別是當在刷新存儲器中執行圖象處理時，利用工作存儲器是有其優越性的。當然，刷新存儲器50和工作存儲器60實際上不需要分開，但可以是單個存儲器中分開的區域。
工作存儲器60相似於刷新存儲器，它是一個隨機存取存儲器，此存儲器具有對應於顯示器70上所顯示二維圖象的象素點的儲存單元。按照上面提到的過程，利用在工作存儲器60中寫入輪廓線象素，然後將輪廓線所限定的區域中的儲存單元置於二進位1，於是在工作存儲器60中形成一滿區域圖象。
在運用中，鑑於圖3所說明的那樣，微處理機10對一系列線段的起點和終點順序地提供坐標地址，而這些線段組成待填滿區域圖象的輪廓。一次一個線段地完成該過程。每線段利用線段-象素點變換器30變換至近似的象素點。
在該實施例中，變換器工作於布列遜海姆(Bresenham)的十進位算法下。布列遜海姆算法是眾所周知的，正如公開於「IBM系統雜誌」Vol·4，No·1，1965 PP25-30「數字計算機的計算機控制算法」一文中的那樣。簡單地說，算法產生一些近似點，其方法為以矢量的起點和終點在X坐標間的差和在Y坐標間的差中較大一個差值(△X和△Y)定為長軸，而以差值較小的一個定為短軸，同時要進行選擇，從起點至終點對於短軸坐標值，可否以單位坐標值(+1或-1)每次步進，和對於長軸數值，可否以單位坐標值(+1或-1)每次步進。
微處理機10裝入長軸起點坐標值、長軸終點坐標值和待分別轉換到轉換器30的寄存器31、32和33的線段長軸起點坐標值。同樣，微處理機10在控制器20的寄存器22中，安置一個信號以指明線段的長軸是X還是Y。這取決於線段的角度。再者，微處理機10在寄存器23和24中安置一個信號以指明，當從線段的起點至終點行進時，長軸和短軸的坐標值將是增大還是減小。在圖4所示的例子中，設置長軸＝X、長軸-減量和短軸-增量。一個指示輪廓線寫入模式的信號亦置於寄存器25中。若△X＝△Y，這充分說明X或Y都可作為長軸。
將寄存器31中的長軸起點置於長軸計數器35中，而寄存器33中的短軸起點寄存在計數器36中。長軸計數器35隨來自控制邏輯電路21的長軸步進脈衝逐一地增大或減小。這種增大或減小的方向通過寄存器23所設置的值來控制。短軸計數器36隨來自計算電路34的短軸步進脈衝逐一地增大或減小。其增大或減小的方向取決於寄存器24所設置的數值。根據上述布列遜海姆的算法，計算電路34定出最近似的點，這是通過選擇「短軸＝不變」或「短軸＝步長1」，每個時刻長軸被步進1來實現。如果短軸＝步長1，則產生一短軸步進脈衝。
通過比較器37將長軸計數器35的數值和寄存器32中的長軸終點進行比較，而變換器30連續地工作，直到這些數值相一致。選擇器38響應於寄存器22中長軸的指示，如長軸＝X，則將長軸計數器35接到X輸出，並將短軸計數器36接到Y輸出;若長軸＝Y，則將長軸計數器35和短軸計數器36相應地接到Y和X的輸出。長軸計數器35和短軸計數器36最初包含起點的坐標值，並且每個時刻進行校正，以定出一相近的象素點。
刷新存儲器50和工作存儲器60以定置在X軸方向的8位字節儲存象素數據，並以字節存取。因此，為了將象素地址轉換為字節地址，除掉較低的3位將選擇器38的X輸出的X較高地址字位和從選擇器38Y輸出的Y地址字位組合，加到地址電路44，以對待寫的字節尋址。X輸出的較低的三位加到解碼器39，並轉換為8位圖形，即8-象素點圖形，其圖形以較低三位置於二進位1來表示的象素點(例如，011→00100000)。
每次對工作存儲器存取時，在變換器30中就確定一近似的象素點。在輪廓線書寫/填滿操作中，每個工作存儲器的存取周期常常包括讀和寫二步運算。這用來自控制邏輯電路的讀/寫信號R/W來控制。在輪廓線書寫模式中，首先讀出一個字節，它以X輸出的高位和選擇器38Y輸出的字位尋址。該讀出的1個字節和解碼器39的輸出一起加到一異門(EX-OR)40。異門40的輸出加到一選擇器42，此選擇器根據模式選擇「異-或」邏輯40的輸出，並把它加到門43。
在讀完以後的寫過程中，需要移去起點，並按照以上提到的規則2和3，以每線一個象素寫出輪廓線。控制器20的起點控制電路27響應於來自寄存器25的輪廓線模式信號和寫入來自控制邏輯電路21的開始周期時間信號的輪廓線，並在第一個工作存儲器存取周期中，通過「或」門29封閉門43。輪廓線控制電路28響應於來自寄存器25的輪廓線模式信號，來自寄存器22的長軸＝X的指示和來自計算電路34無短軸步進脈衝的指示，並且當短軸(Y)的值不變時，關閉門43。如圖4所描述的那樣，當長軸＝X時，許多近似點產生在同一X線上。
在這種狀態下，變換器30從起點直到終點在連續的周期內不斷地產生所有近似象素，同時地址電路44在每個周期內對工作存儲器60進行存取，但是不寫出起點和不需要的點。
當對每一線段寫輪廓線象素時，長軸計數器35的值達到寄存器32中長軸終點的數值，比較器37產生一長軸匹配信號，這個信號加到微處理器10，直到一個線段寫完為止。
微處理機10響應於長軸匹配信號，以安置下一線段起點和終點的坐標值於寄存器31，32和33中，並且類似地完成線段對象素點的變換和輪廓線象素的寫入。該運行類似地連續進行著直到完成最後線段的處理。微處理機10將填滿指令信號(沒有表示出)加到以控制器20中的控制邏輯電路21，而控制器響應於在最後線段處理中來自比較器37的長軸匹配信號的產生。控制電路21響應指令信號，以產生一填滿模式信號，並且也響應該填滿模式信號，開關選擇器42接通以產生填滿電路41的輸出，以通過門43。
控制器20的滿地址發生器電路26響應填滿模式信號和長軸步進脈衝，並且對尋址電路44產生地址，在工作存儲器60中對每一X線一次讀出一個字節的數據。圖5表示填滿地址發生器電路26的一個實例。X起點值，X終點值，Y起點值和Y終點值(由這些點定出圍繞已寫入工作存儲器60的輪廓的任何矩形區域，最好使矩形區域稍大於該輪廓線用微處理機10安置在寄存器81，82，83和84中。在X起點寄存器81和Y起點寄存器84中的值都被裝入X計數器86和Y計數器87中。門電路85將長軸步進脈衝加到X計數器86，以響應填滿模式信號。因此，X計數器86連續地步進。將X計數器86中去掉較低3位後的位，和Y計數器87中的位，加到尋址電路44作為字節地址。當X計數器86的值和X終點值相等時，比較器88產生X匹配輸出，並使Y計數器87增加1，使X計數器86復位，然後將X起點再裝入X計數器86。這種運行類似地連續下去，當Y計數器87的值和Y終點值相等時，比較器89產生Y匹配輸出。當完成讀出指定的矩形區域所有字節時，產生了X和Y兩者的匹配輸出，並且「與」電路90對微處理機10提供一填滿結束信號。
圖6表示填滿電路41。它包括一鎖存器和8個「異-或」邏輯電路。鎖存器的輸入連接至異門的0位輸出，而鎖存器的輸出以7位接到異門的輸入。異門的7-2位接到異門6-0位的輸入。讀出的字節加到7-0位的輸入端。例如，假設讀出字節的6位為二進位的1，那麼第一個奇數輪廓線象素點6-0位的每個異門產生二進位的1輸出。因為鎖存器利用復位信號RST(未在圖1中表示出)在開始運用之前被復位，而復位信號來自控制邏輯電路21，則7位輸出為0，因此，在相同的字節地址中儲存了01111111。在寫入之後，來自控制邏輯電路21的一寫完信號(W/C)(未在圖1中表示出)，將來自異門0位輸出的二進位的1鎖入鎖存器中，並對異門7位的輸入提供二進位的1。因此，只要以後讀出二進位0的象素位該電路就連續地產生全為二進位的1輸出。假設在一個字節的5位處產生第一偶數輪廓線象素點，則異門5位產生二進位的0，而且4-0位也成為二進位的0。因此，完成了在第一個奇或偶數點之間的填滿操作，並且將鎖存器置於二進位的0。相似地，當在線上檢出第二個奇數點時，完成了對下一個偶數點的填滿。在對每一X線完成掃描之後，鎖存器也被復位。這個電路使得偶數輪廓線象素被消除了。
在完成填滿操作之後，微處理機10提供一個地址至尋址電路44，在工作存儲器60中一次一個字節地讀出滿區域圖象，並且將它寫在刷新存儲器50中。滿區域圖象可寫在刷新存儲器50中的任何位置上。在黑白顯示情況下，刷新存儲器50將有一單個象素存儲平面，而在對一象素灰色標度或以具有多位彩色顯示的情況下，它將有多個對應於這些位的存儲平面。在這種情形下，滿區域圖象可儲存於刷新存儲器中，以任意所需要的輝度電平或彩色，用通常將存儲地址輸入或數據輸入加到存儲器平面並選擇待寫入的平面。
最後，本發明的優點說明於下
(1)首先，它能容易地進行區域填滿，即使它有許多的向上或向下的頂點，都能以高速度進行區域填滿。
(2)它能使移去頂點所得到的原圖象畸變減至最小，因為它不僅移去了頂點，而且還把偶數輪廓線象素在填滿操作中去掉。
(3)由於略去水平線段，它簡化了線段的確定。
(4)它能區域填滿一個包含交叉線的圖象。例如在圖7的圖象中，能用二條線段P1→P3和P2→P4確定輪廓線。可將象素P5寫入線段P1→P3中，而用異門寫出線段P2→P4，儲存在二進位的0位上。因此，區域填滿可不用交叉處理來完成。
(5)因為消去了偶數輪廓象素，它能產生具有完全與邊界相符的相近的圖象。
例如在這樣的情形下，即將一個滿區域圖象與鄰近於前一個的滿區域圖象相加，或以不同於前一個圖象的彩色來顯示的相近滿區域圖象，這在前一個圖象移至刷新存儲器之後，需要創造一幅和前一個圖象相近的圖象。在這種情形下，本發明能用前一圖象所使用的線段繪出輪廓線。例如在圖3中，若想創造一幅相近的圖象，此圖象的頂、右和底邊和前一圖象的相接近，於是相近圖象的輪廓可用相同的線段P5→P3，P1→P15，P10→P7和P10→P12來確定。因為象素10沒有寫出，那裡沒有發生和前一圖象的相互幹擾。寫出象素P9，P8和P7，同時在填滿操作過程中消去象素P11和P12。因此在圖象之間沒有間隙或重疊。
雖然在這裡已對特殊的實施例作了說明，但是顯然對本領域的技術人員來說，在本發明的範圍內可作種種變更。例如雖然該實施例利用了分離的地址發生器電路26，然而變換器30可用於電路26處，正如線路之間的相似性中所提及的那樣。在這種情形下，變換器30的寄存器31，32和33可用於電路26的寄存器81，82和84處，但需要加入一對應於Y終點寄存器83的短軸終點寄存器，一個對應於比較器89的比較器，和一個對應於「與」門電路90的「與」門電路。另外，在填滿模式中將需要對短軸計數器36根據短軸步進脈衝選通比較器37的輸出。雖然在該實施例中，控制移去起點和每線寫入一個象素是利用封鎖數據門43來完成的，但也可在變換器30的輸出端提供例如一相似的門。
按照本發明，即使是一個複雜的圖象，也可以容易地和很快地進行區域填滿。
附圖的簡要說明
圖1表示本發明的一種實施例。
圖2表示當利用閉合輪廓線時的滿區域。
圖3表示按照本發明的滿區域。
圖4表示近似的象素點。
圖5表示填滿地址發生器電路。
圖6表示一個填滿電路。
圖7表示滿區域圖象的一個實例。
10…微處理機;20…輪廓線/區域填滿控制器;27…起點控制電路;28…輪廓線控制電路;30…線段-象素點變換器;40…異門電路;41…填滿電路;50…刷新存儲器;60…隨機存取工作存儲器;70…陰極射線管顯示(CRT顯示)。
權利要求
1、在一個用圖形表示的圖象處理系統中，包括一個圖象再生裝置和一個隨機存取存儲器，該存儲器有儲存單元用以儲存一個二維圖象的象素數據，該處理系統在上述的存儲器中產生一區域填滿的圖象，圖象通過上述圖象再生裝置再生成，其特徵在於包括
a)用來確定一系列線段中每一條線段的裝置，這些線段除水平線段外在一個方向組成一個圖象的輪廓。
b)用來產生每一確定線段的近似象素的裝置。
c)響應上述產生裝置用來寫入象素的裝置，這些象素不包含每線段的起點，並以每一水平基線上一個象素代表每一線段，在上述存儲器中以象素數據進行異門操作(該數據是從上述存儲器中對應的坐標地址中讀出)，以此建立輪廓線象素。
d)用來逐線對已寫入上述隨機存取存儲器的輪廓線象素進行掃描並且用來在每線的奇數輪廓線象素和緊接著發生的偶數輪廓線象素之間，安置儲存單元的裝置。
2、根據權利要求
1的用圖形表示的圖象處理系統，其特徵在於上述裝置d包括從上述記憶器中每一水平線讀出象素數據的裝置，和一個填滿電路，該電路有一個異門電路，用來對每一象素和在同一水平線上緊靠前的象素的進行異門運算，上述異門操作的結果寫入上述的記憶器中做為填入數據，以便通過填入操作消去偶數輪廓線象素。
專利摘要
本發明公布了一種用圖形表示的圖象區域填滿技術。用一系列除水平線段外的線段來確定構成圖象的輪廓線。這些線段是在一個方向上確定的，即從頂到底或從底到頂；把它們變換為以每條水平基線一個象素的一些近似象素並寫入一個隨機存取存儲器中，除去起始點。(通過每個近似象素和從存儲器中對應地址讀出的象素數據進行異門運算。)結果使每一水平線偶數輪廓象素儲存在存儲器中。因此，通過掃描存儲器中每一水平線，並從一奇數輪廓象素到偶數輪廓象素接通象素存儲單元很容易實現區域填滿。
文檔編號G06T11/40GK86100088SQ86100088
公開日1986年10月22日 申請日期1986年1月14日
發明者松原茂, 森徹, 田煙俊朗 申請人:國際商業機器公司導出引文BiBTeX, EndNote, RefMan