摘  要: 以圖像與圖像平移的并集作為狀態(tài)集,以探針與探針拷貝的并集作為輸入字母表,用向量加減法構(gòu)造狀態(tài)轉(zhuǎn)換映射和輸出映射,給出了實(shí)現(xiàn)數(shù)學(xué)形態(tài)學(xué)基本運(yùn)算開運(yùn)算的有限自動機(jī)。與通用計(jì)算機(jī)對圖像的串行處理相比，開運(yùn)算自動機(jī)采取了并行結(jié)構(gòu)。開運(yùn)算自動機(jī)將運(yùn)算的時(shí)間復(fù)雜度降低到了探針像素個(gè)數(shù)減1。
關(guān)鍵詞: 圖像處理；分形；形態(tài)學(xué)開運(yùn)算；有限自動機(jī)

     雖然通用計(jì)算機(jī)已被廣泛地應(yīng)用于圖像處理，但是就其體系結(jié)構(gòu)而言是不適合處理圖像數(shù)據(jù)的。通用計(jì)算機(jī)的串行性限制了它在圖像處理中的效率，因此有必要開發(fā)專用的圖像處理器。自20世紀(jì)60年代MATHERON G和 SERRA J創(chuàng)立了用于圖像處理的數(shù)學(xué)形態(tài)學(xué)以來，在過去的50多年里得到了大量基于數(shù)學(xué)形態(tài)學(xué)的圖像處理器,包括Golay邏輯處理器[1]、Diff3[2]、PICAP[3]、Leitz 紋理分析系統(tǒng)[4]、CLIP 陣列處理器[5]、細(xì)胞計(jì)算機(jī)[6]和Delft 圖像處理器[7]。這些處理器對于圖像的局部變換有較好的效果,它們都屬于原胞機(jī)器[8]。
    自20世紀(jì)90年代KARI J將自動機(jī)應(yīng)用于圖像壓縮以來，在過去的近20年里，得到了基于有限自動機(jī)的大量圖像壓縮的有效算法[9]，并且將其中一些算法轉(zhuǎn)化成了實(shí)際的圖像壓縮技術(shù)[10]。
    數(shù)學(xué)形態(tài)學(xué)和自動機(jī)理論之所以能夠被應(yīng)用于數(shù)字圖像處理，是因?yàn)槎鄶?shù)圖像具有分形性。而數(shù)學(xué)形態(tài)學(xué)中的探針體現(xiàn)了這種分形結(jié)構(gòu)[11]，有限自動機(jī)識別的正規(guī)語言的正規(guī)分解也體現(xiàn)了分形結(jié)構(gòu)[12-13]。
     本文將有限自動機(jī)應(yīng)用于數(shù)學(xué)形態(tài)學(xué)基本運(yùn)算開運(yùn)算的實(shí)現(xiàn)，得到了可對圖像進(jìn)行并行處理的有限自動機(jī)，降低了開運(yùn)算的時(shí)間復(fù)雜度。

    設(shè)圖像A含有m個(gè)像素點(diǎn)，探針B含有n個(gè)像素點(diǎn)。關(guān)于開運(yùn)算的算法復(fù)雜度有如下結(jié)論。在通用計(jì)算機(jī)上，完成開運(yùn)算需要串行地進(jìn)行2m×n次加減法和m×n次查找,而在開自動機(jī)上完成僅需要并行地進(jìn)行2n-1次加減法和n-1次查找。因此，利用有限自動機(jī)實(shí)現(xiàn)圖像開運(yùn)算，其時(shí)間復(fù)雜度僅取決于探針的像素個(gè)數(shù)n，而與圖像的像素個(gè)數(shù)m無關(guān)。由于在圖像處理中探針通常要比圖像小得多，因此用有限自動機(jī)實(shí)現(xiàn)開運(yùn)算對降低運(yùn)算的時(shí)間復(fù)雜度是有效的。
    用開運(yùn)算的有限自動機(jī)可以降低運(yùn)算的時(shí)間復(fù)雜度。然而，開運(yùn)算結(jié)果的優(yōu)劣取決于探針的選擇，并將直接影響到數(shù)字圖像處理的效果，只有探針選擇恰當(dāng)，開運(yùn)算才有價(jià)值。因此,利用有限自動機(jī)實(shí)現(xiàn)探針選取是一項(xiàng)有意義的工作。
參考文獻(xiàn)
[1] GOLAY M J E. Hexagonal parallel pattern transformations[J]. IEEE Transactions on Computers, 1969,18(8):733-740.
[2] GRAHAM M D, NORGREN P E, The Diff3 analyzer: a  parallel/serial Golay image processor[C]. Real Time Medical Image Processing, 1980:163-182.
[3] KRUSE B. Design and implementation of a picture processor [D]. Linkoeping: University of Linkoeping, 1977.
[4] KLEIN J C, SERRA J. The texture analyzer [J]. Journal of Microscopy, 1977(95):349-356.
[5] DUFF M J B. Parallel processors for digital image processing [C]. Proceedings of the International Symposium, Bad Neuenahr, 1979:265-279.
[6] LOUGHEED R M, MCCUBBREY D L. The cytocomputer: a practical pipelined image processor[C]. Proceedings of IEEE Annual Symposium on Computer Architecture,France,1980:271-278.
[7] GERRITSEN F A, AARDEMA L G. Design and use of DIP-1: a fast flexible and dynamically microprogrammable  image processor[J]. Pattern Recognition, 1981,14(6):319-330.
[8] NACHTEGAEL M, SUSSNER P, MELANGE T. On the role of complete lattices in mathematical morphology: from tool to uncertainty model[J].Information Sciences,2011(181):1971-1988.
[9] KARI J. Image processing using finite automata[J]. Studies  in Computational Intelligence, 2006(25):171-208.
[10] TISCHIER G.Theory and applications of parametric weighted finite automata[D]. Wurzburg: University of Wurzburg, 2008.
[11] DROSTE M, KUICH J, VOGLER H. Handbook of weigted automata[M]. Berlin: Springer-Verlag, 2009.
[12] LIU Y J.Regular component decomposition of regular languages[J]. Theoretical Computer Science, 2003,299:734-749.
[13] LIU Y J, XU Z B. Semigroup method in combinatorics on words[J]. Chinese Journal of Computer,2005,28: 1138-1145.