Эффективные наборы совместно вычисляемых линейных локальных признаков цифровых сигналов

Мясников В.В.

Аннотация:
В работе рассматривается проблема построения эффективных в вычислительном и качественном плане линейных локальных признаков (ЛЛП) цифровых сигналов и изображений. Под набором совместно вычисляемых ЛЛП понимается пара, состоящая из набора конечных импульсных характеристик (КИХ) и одного алгоритма, который производит одновременное/совместное вычисление нескольких линейных свёрток входного сигнала/изображения с набором этих КИХ. Эффективные наборы совместно вычисляемых ЛЛП обнаруживают оптимальное поведение: алгоритм вычисления признаков имеет заранее заданную вычислительную сложность, а набор КИХ наилучшим образом согласован с критерием качества конкретной прикладной задачи. Предлагается способ построения эффективных наборов совместно вычисляемых ЛЛП, основанный на конструировании набора последовательностей отсчётов КИХ специального вида. Приводятся примеры таких наборов последовательностей, рассматривается пример решения задачи построения эффективного набора ЛЛП для типовой задачи цифровой обработки сигналов.

Abstract:
The paper addresses the problem of constructing efficient computationally and qualitatively linear local features (LLA) of digital signals and images. Under a set of jointly-computed LLP is a pair consisting of a set of finite impulse response (FIR) and an algorithm that produces simultaneous / joint computation of several linear convolution the input signal / image with a set of FIR. Effective set of jointly-computed LLP should detect the optimal behavior: an algorithm for calculating the signs must have a predetermined computational complexity, and a set of FIR must be well coordinated with the quality criteria specific application. Propose a method for constructing efficient sets of co-LLA calculated based on the design of a set of sequences of samples of a special type of FIR. Examples of such sets of sequences, is considered an example of solving the problem of building an effective recruitment LLP for a typical problem of digital processing signals.

Ключевые слова :
цифровые сигналы, линейные локальные признаки.

Key words:
digital signals, linear local features.

Литература:

  1. Computer Image Processing, Part II: Methods and algorithms / edited by Victor A. Soifer. - VDM Verlag, 2009. - 584 p.
  2. Forsyth, D.A. Computer Vision: A Modern Approach / D.A. Forsyth, J. Ponce // Upper Saddle River, NJ: Prentice Hall, 2003. - 693 p.
  3. Fukunaga, K. Introduction to Statistical Pattern Recognition / K. Fukunaga. - 2nd ed. - New York: Academic Press, Inc, - 1991.- 591 p.
  4. Мясников, В.В.О синтезе эффективного алгоритма над множеством алгоритмов вычисления свёртки / В.В. Мясников // Компьютерная оптика. - Вып. 29. - 2006. - C. 78-117.
  5. Мясников, В.В. Эффективные локальные линейные признаки цифровых сигналов и изображений / В.В. Мясников // Компьютерная оптика. - 2007. - Т. 31, - № 4. - C. 58-76.
  6. Мясников, В.В. Построение эффективных линейных локальных признаков в задачах обработки и анализа изображений / В.В. Мясников // Автоматика и Телемеханика. - 2010. - № 3. - C. 162-177.
  7. Hatamian, M. A real-time two-dimensional moment generating algorithm and its single chip implementation / M. Hatamian // IEEE Trans. Acoustic, Speech, and Signal Proc. - 1999. - V.ASSP-34. - №~3. - P. 546-553.
  8. Глумов, Н.И. Применение полиномиальных базисов для обработки изображений в скользящем окне / Н.И. Глумов, В.В. Мясников, В.В. Сергеев // Компьютерная оптика. - 1995. - № 14-15. - Ч.1. - С.55-68.
  9. Agarwal, R.P. Difference Equations and Inequality: Theory, Methods, and Applications / R.P. Agarwal. - New York: Marcel Dekker, 2000. - 998 p.
  10. Lidl, R. Finite Fields, Second edition / R. Lidl, H. Niederreiter // Cambridge University Press, 1997. - 755 p.
  11. Гельфонд, А.О. Исчисление конечных разностей / А.О. Гельфонд. - 3-е изд. испр. - М.: Наука, 1967. - 375 с.
  12. Мясников, В.В. Анализ методов построения эффективных линейных локальных признаков цифровых сигналов и изображений / В.В. Мясников, А.Ю. Баврина, О.А. Титова  // Компьютерная оптика. - 2010. - Т. 34, № 3. - C. 193-201.
  13. Мальцев, А.И. Основы линейной алгебры / А.И. Мальцев. - М.: Наука, 1975. - 400 с.
  14. Bellman, R. Dynamic Programming / R. Bellman. - Dover Publications, Inc, 2003. - 366 p.
  15. Anderson, J.A. Discrete Mathematics with Combinatorics / J.A. Anderson. - Upper Saddle River, New Jersey: Prentice Hall, 2001.
  16. Myasnikov, V.V. Construction of Integer-Value Polynomials for Recursive Calculation of the Convolution with FIR-Filter / V.V. Myasnikov // Theses of 7-th International Conference “International Conference on Pattern Recognition and Image Analysis” - PRIA’2004, St.-Petersburg, Russia, October 18-23, 2004, - P. 331-334.
  17. Гихман, И. И. Введение в теорию случайных процессов / И.И. Гихман, А.В. Скороход - М.: Наука, 1965.
  18. Nussbaumer, H.J. Fast Fourier Transform and Convolution Algorithms / H.J. Nussbaumer. - 2nd ed. - New York: Springer-Verlag, 1982.
  19. Minoux, M. Mathematical programming: theory and algorithms / M. Minoux. - New York: Wiley in Chichester, 1986. - 489 p.

References:

  1. Computer Image Processing, Part II: Methods and algorithms / edited by Victor A. Soifer. - VDM Verlag, 2009. - 584 p.
  2. Forsyth, D.A. Computer Vision: A Modern Approach / D.A. Forsyth, J. Ponce // Upper Saddle River, NJ: Prentice Hall. - 2003. - 693 p.
  3. Fukunaga, K. Introduction to Statistical Pattern Recognition / K. Fukunaga. -  2nd ed., New York: Academic Press, Inc. - 1991.- 591 p.
  4. Myasnikov, V.V.On the synthesis of the efficient algorithm over the set of the convolution algorithms/ V.V. Myasnikov // Computer optics, Issue 29, 2006, P. 78-117. - (in Russian)
  5. Myasnikov, V.V. Efficient linear local features of signals and images / V.V. Myasnikov // Computer optics. - 2007. - Vol.31, № 4. - P. 58-76. - (in Russian)
  6. Myasnikov, V.V. Construction of efficient linear local features for image processing and analysis / V.V. Myasnikov // Automation and Remote Control. - 2010. -№ 3. - P.162-177. - (in Russian)
  7. Hatamian, M. A real-time two-dimensional moment generating algorithm and its single chip implementation / M. Hatamian // IEEE Trans. Acoustic, Speech, and Signal Proc. 1999. V.ASSP-34. №~3. P. 546--553.
  8. Glumov, N.I. Application of polynomial bases for image processing in sliding window / N.I. Glumov, V.V. Myasnikov, V.V. Sergeyev // Computer optics. - 1995. - № 14-15. Part.1. - P.55--68. - (in Russian)
  9. Agarwal, R.P. Difference Equations and Inequality: Theory, Methods, and Applications / R.P. Agarwal. - New York: Marcel Dekker, 2000. - 998 p.
  10. Lidl, R. Finite Fields, Second edition / R. Lidl, H. Niederreiter // Cambridge University Press, 1997, 755 pp.
  11. Gelfond, A.O. Finite Differences Calculus / A.O. Gelfond. - 3-d issue. corrected. - Moscow: «Science» Publisher, 1967. - P. 375. - (in Russian)
  12. Myasnikov, V.V. Analysis of the methods for construction of linear local features / V.V. Myasnikov, A.U. Bavrina, O.A. Titova // Computer optics. - 2010. - Vol. 34, № 3. - P. 193-201. - (in Russian)
  13. Malcev, A.I. Linear algebra basis / A.I. Malcev. - Moskow: «Science» Publisher, 1975. - 400 p. - (in Russian)
  14. Bellman, R. Dynamic Programming / R. Bellman. - Dover Publications, Inc. - 2003. - 366 p.
  15. Anderson, J.A. Discrete Mathematics with Combinatorics / J.A. Anderson, - Upper Saddle River, New Jersey: Prentice Hall, 2001.
  16. Myasnikov, V.V. Construction of Integer-Value Polynomials for Recursive Calculation of the Convolution with FIR-Filter / V.V. Myasnikov // Theses of 7-th International Conference ”International Conference on Pattern Recognition and Image Analysis” - PRIA’2004, St.-Petersburg, Russia, October 18-23, 2004 г., P. 331-334.
  17. Gihman, I. I. Introduction to stochastic process theory / I.I. Gihman, A.V. Skorohodov // Moscow: “Science” Publisher, 1965. - (in Russian)
  18. Nussbaumer, H.J. Fast Fourier Transform and Convolution Algorithms / H.J. Nussbaumer. - 2nd ed. New York: Springer-Verlag, 1982.
  19. Minoux, M. Mathematical programming: theory and algorithms / M. Minoux. - New York: Wiley in Chichester, 1986. - 489 p.
© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20