摘 要: 以圖像與圖像平移的并集作為狀態集,以探針與探針拷貝的并集作為輸入字母表,用向量加減法構造狀態轉換映射和輸出映射,給出了實現數學形態學基本運算開運算的有限自動機。與通用計算機對圖像的串行處理相比，開運算自動機采取了并行結構。開運算自動機將運算的時間復雜度降低到了探針像素個數減1。
關鍵詞: 圖像處理；分形；形態學開運算；有限自動機
雖然通用計算機已被廣泛地應用于圖像處理，但是就其體系結構而言是不適合處理圖像數據的。通用計算機的串行性限制了它在圖像處理中的效率，因此有必要開發專用的圖像處理器。自20世紀60年代MATHERON G和 SERRA J創立了用于圖像處理的數學形態學以來，在過去的50多年里得到了大量基于數學形態學的圖像處理器,包括Golay邏輯處理器[1]、Diff3[2]、PICAP[3]、Leitz 紋理分析系統[4]、CLIP 陣列處理器[5]、細胞計算機[6]和Delft 圖像處理器[7]。這些處理器對于圖像的局部變換有較好的效果,它們都屬于原胞機器[8]。
自20世紀90年代KARI J將自動機應用于圖像壓縮以來，在過去的近20年里，得到了基于有限自動機的大量圖像壓縮的有效算法[9]，并且將其中一些算法轉化成了實際的圖像壓縮技術[10]。
數學形態學和自動機理論之所以能夠被應用于數字圖像處理，是因為多數圖像具有分形性。而數學形態學中的探針體現了這種分形結構[11]，有限自動機識別的正規語言的正規分解也體現了分形結構[12-13]。
本文將有限自動機應用于數學形態學基本運算開運算的實現，得到了可對圖像進行并行處理的有限自動機，降低了開運算的時間復雜度。
設圖像A含有m個像素點，探針B含有n個像素點。關于開運算的算法復雜度有如下結論。在通用計算機上，完成開運算需要串行地進行2m×n次加減法和m×n次查找,而在開自動機上完成僅需要并行地進行2n-1次加減法和n-1次查找。因此，利用有限自動機實現圖像開運算，其時間復雜度僅取決于探針的像素個數n，而與圖像的像素個數m無關。由于在圖像處理中探針通常要比圖像小得多，因此用有限自動機實現開運算對降低運算的時間復雜度是有效的。
用開運算的有限自動機可以降低運算的時間復雜度。然而，開運算結果的優劣取決于探針的選擇，并將直接影響到數字圖像處理的效果，只有探針選擇恰當，開運算才有價值。因此,利用有限自動機實現探針選取是一項有意義的工作。
參考文獻
[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.