Elements of the information technology of cytological specimen analysis: Taxonomy and factor analysis

The automated software system “Black Square,” Version 1.2 is described. The system is intended for the automation of image processing, analysis, and recognition. It is an open system for generating new knowledge: objects, algorithms of image processing, recognition procedures originally not intended for image processing, and methods for solving applied problems. The system combines the features of information retrieval, reference, training, and computing systems. This work was partially supported by the Russian Foundation for Basic Research, project nos. 03-07-90406, 05-04-49846, and 05-07-08000; by the INTAS grant no. 04-77-7067; by the Cooperative grant “Image Analysis and Synthesis: Theoretical Foundations and Prototypical Applications in Medical Imaging” within agreement between Italian National Research Council and Russian Academy of Sciences (RAS); by the grant of the RAS in the framework of the Program “Fundamental Science to Medicine.” An erratum to this article is available at .     

From Kalman—Mesarovic realization to a normal-hyperbolic linear model

The principles of the methodology are formulated, which underlie the procedures of the Kalman—Mesarovic realization for dynamic systems with state equations in the class of autonomous linear differential equations in the normalized Frechet space. In this connection, the key approaches to the solution of classical problems of realization theory regarding linear dissipation models of normal-hyperbolic type are interpreted. The study was sponsored by the Russian Fund for Basic Research (grant No. 05-01-00623), the “Integration” Russian Federal Target Program (grant No. B0077), and the Program for Basic Research of the Presidium of the Russian Academy of Sciences (program No. 19, project 2.5). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 137–157, November–December 2005.     

Functional completeness criteria in Dijkstra algebra

The study was supported by the International Soros Program for basic Research and Education in Exact Sciences of the International Foundation “Renaissance,” grant No. VA0000.     

Classification system in the software of the Earth remote sensing data processing

Questions concerning the problem of choosing adequate recognition algorithms for Earth, multispectral, remote sensing data are considered. A system of supervised classification based on the strategy of maximum likelihood for normally distributed vectors of attributes is presented. A system of cluster analysis, including an algorithm of K-means and the method of modes analysis for a multidimensional histogram, is described. Aleksei Aleksandrivich Buchnev. Born in 1947. Graduated from Krasnoyarsk State University in 1972. Received his candidate’s degree in 1989. He was awarded the State prize of the Soviet Union in the field of science and technology. Buchnev is currently a senior research fellow at the Institute of Computational Mathematics and Mathematical Geophysics SB RAS (Novosibirsk). Scientific interests include remote sensing, digital image processing, and pattern recognition. He is the author of more than 70 publications. Valerii Pavlovich Pyatkin. Born in 1939. Graduated from Moscow Energetic Institute in 1963. Received his candidate’s degree in 1970 and his doctoral degree in 1987. Since 1990, he has been a professor and is currently a head of the Image Processing laboratory at the Institute of Computational Mathematics and Mathematical Geophysics SB RAS (Novosibirsk). Pyatkain has been awarded with a K.E. Tsiolkovskii medal (the highest award of the Federation of Russian Cosmonautics) in 2002 and has received the honorary title “Honored Creator of Space Technique.” Scientific interests include digital image processing, remote sensing, geoinformatics, and GIS- and Web-technologies. He is the author of more than 200 publications, including five monographs. Vasilii Valentinovich Asmus. Born in 1952. Graduated from Moscow Institute of Electronic Engineering in 1976. Postgraduate studies at the Computational Center of the Siberian Branch of the Russian Academy of Sciences. Received his candidate’s degree in 1984 and his doctoral degree in 2002. Since 2007, he has been a professor and is currently a director at the Planeta Space Hydrometeorology Research and Development Center of the Federal Service of Russia on Hydrometeorology and Environmental Monitoring (Moscow). Asmus is also a full member of the Tsiolkovskii Russian Academy of Cosmonautics and has been awarded the prize of the Moscow City Administration. Scientific interests include remote sensing, digital image processing, and pattern recognition. He is the author of more than 140 publications, including four monographs.     

Methods for formation of features of tree-like structures on fundus images

A fundamental problem of computer diagnostics is the detection of a vascular system on an image and the determination of its local and global parameters. Methods for tracing vessels and estimating their diagnostic features based on a mathematical model of a fundus fragment are described. This work was supported by the Ministry of Education of the Russian Federation, Administration of Samara Region, the U.S. Civilian Research and Development Foundation in the framework of the Russian-American program “Basic Research and Higher Education” (CRDF project no. SA-014-02), and by the Russian Foundation for Basic Research, project no. 03-01-00642.     

On the theory of realization of quasilinear systems described by differential equations in a Hilbert space

We consider a system-theoretic methodology of mathematical modeling involved in the structural identification of continuous nonlinear dynamic systems with programmable position control. We present various functional-analytical modifications of a characteristic criterion for exogenous (“input-output”) behavior of these systems that permit, by virtue of this criterion, model realizations in the class of quasilinear nonstationary ordinary differential equations describing states in a separable Hilbert space. The study was sponsored by the Russian Foundation for Basic Research (Grant No. 05-01-00623), Basic Research Program No. 22 of the Presidium of the Russian Academy of Sciences, Grant of the President of the Russian Federation for the Governmental Support of Scientific Schools of the Russian Federation (No. NSh-1676.2008). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 82–95, September–October 2008.     

Application of pattern recognition methods in electropuncture diagnostics for assessment of neuropsychic state

The logical and statistical methods of pattern recognition and data analysis are applied for studying the capability of electropuncture diagnostics for the estimation of the neuropsychic states (stress) of school children during an examination period. This work was supported by the Russian Foundation for Basic Research (the research program “Basic Sciences for Medicine”) and INTAS, project nos. 00-626 and 00-397.     

Electronic corpora of the Albanian,Kalmyk, Lezgian,and Ossetic Languages

Four electronic corpora created in 2011 within the framework of the “Corpus Linguistics: the Albanian, Kalmyk, Lezgian, and Ossetic Languages” Program of Fundamental Research of the RAS are presented. The interface and functionalities of these corpora are described, engineering problems to be solved in their creation are elucidated, and the promises of their development are discussed. A particular emphasis is made on the compilation of dictionaries and automatic grammatical markup of the corpora.     

Comparative analysis of function approximation methods applied to image processing

Application of nonlinear methods of multivariate regression approximation (neural networks, functions linear in fitting parameters, and hierarchical approximation) is considered to problems of image filtering based on a priori information in the form of matched pairs of images (“ideal” and “degraded”). The methods are compared with regard to their efficiency. Vasilii N. Kopenkov. Born 1978. Graduated from the Samara State Aerospace University (SSAU) in 2001. Assistant Professor at the Chair of Geoinformatics, SSAU, and a Junior Researcher at the Institute of Image Processing Systems, Russian Academy of Sciences. Scientific interests: image processing and pattern recognition. Author of four papers. Member of the Russian Federation Association for Pattern Recognition and Image Analysis. Andrei V. Chernov. Born 1975. Graduated from the Samara State Aerospace University (SSAU) in 1998. Received candidate’s degree (Cand. Sc. (Eng.)) in 2004. Assistant Professor at the Chair of Geoinformatics, SSAU, and a Researcher at the Institute of Image Processing Systems, Russian Academy of Sciences. Scientific interests: image processing, pattern recognition, and geoinformation systems. Author of more than 50 publications, including 11 papers in journals, and a co-author of a monograph. Member of the Russian Federation Association for Pattern Recognition and Image Analysis. Vladislav V. Sergeev. Born 1951. Graduated from the Kuibyshev Aviation Institute (now, the Samara State Aerospace University). Received doctoral degree (Dr. Sc. (Eng.)) in 1993. Head of Laboratory of Mathematical Methods of Image Processing, Institute of Image Processing Systems, Russian Academy of Sciences. Scientific interests: digital signal processing, image analysis, pattern recognition, and geoinformatics. Author of more than 150 publications, including about 40 papers in journals, and a co-author of 2 monographs. Chair of the Volga-region Branch of the Russian Federation Association for Pattern Recognition and Image Analysis. Corresponding Member of the Russian Ecological Academy and the Russian Academy of Engineering, member of SPIE (The International Society for Optical Engineering), a winner of the Samara District Award for Science and Engineering.     

Satellite monitoring of ice conditions in polar regions

Data obtained by Russian and foreign polar-orbital satellites for remote sensing (RS) of the Earth is used for monitoring the ice cover of the polar regions. State Research Center of Space Hydrometeorology “Planeta” (SRC “Planeta”) and the Institute of Computational Mathematics and Mathematical Geophysics (CMMGI), have developed methods and technologies for processing the satellite data. Russian and foreign satellites (active and developing) including the satellite Arktika are described in the present paper. Procedures and techniques for monitoring the ice cover and examples of satellite data related to Arctic and Antarctic territories are given below.     

Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to treelike resolution proofs. Therefore, lower bounds for treelike resolution (known since the 1960s) apply to them. However, these lower bounds say nothing about the behavior of such algorithms on satisfiable formulas. Proving exponential lower bounds for them in the most general setting is impossible without proving P ≠ NP; therefore, to prove lower bounds, one has to restrict the power of branching heuristics. In this paper, we give exponential lower bounds for two families of DPLL algorithms: generalized myopic algorithms, which read up to n ^1−ε of clauses at each step and see the remaining part of the formula without negations, and drunk algorithms, which choose a variable using any complicated rule and then pick its value at random. ^★Extended abstract of this paper appeared in Proceedings of ICALP 2004, LNCS 3142, Springer, 2004, pp. 84–96. ^†Supported by CCR grant CCR-0324906. ^‡Supported in part by Russian Science Support Foundation, RAS program of fundamental research “Research in principal areas of contemporary mathematics,” and INTAS grant 04-77-7173. ^§Supported in part by INTAS grant 04-77-7173.     

A posteriori detecting a quasiperiodic fragment in a numerical sequence

Combinatorial approach to solving the problem of detection of an unknown quasi-periodic fragment in a noisy numerical sequence is considered. The problem is analyzed under the following conditions: (1) the number of repeats is known; (2) the number of the sequence term corresponding to the starting instant of the fragment is a deterministic (non-random) value; and (3) the observed sequence is corrupted by additive Gaussian uncorrelated noise. It is demonstarted that the problem under consideration consists in testing the set of composite hypotheses on the mean of a random Gaussian vector. It is shown that the search for a maximum likelihood hypothesis can be reduced to the search for a maximum of an auxiliary objective function. It is proved that the problem of maximization of this function is NP-hard in the general case. An approximate polynomial algorithm for solving the problem is proposed. To improve the approximation, an algorithm of local search is proposed. Numerical simulation showed reasonable results from the applied point of view. Eduard Khairutdinovich Gimadi. Born 1937. Principal Researcher at the Soblev Institute of Mathematics of Siberian Branch of the Russian Academy of Sciences, Professor. Graduated from the Kazan State University in 1959. Received candidate’s degree in 1971 and doctoral degree in 1988. Scientific interests: discrete optimization, operation research. Author of more than 200 publications including 4 monographs. Editorial board member of journals “Discrete analysis and operation research,” “Algorithmic Operations Research,” FACETS Publishing, USA. Awarded the medal of the Federal Agency of Education (Russia). E-mail: gimadi@math.nsc.ru Maria Aleksandrovna Kel’manova. Born 1983. Junior Researcher at the Soblev Institute of Mathematics of Siberian Branch of the Russian Academy of Sciences. Graduated from the Novosibirsk State University in 2005. Scientific interests: mathematical methods for pattern recognition, problems of discrete optimization, efficient algorithms for analysis and recognition of random sequences. Author of 1 publication. E-mail: mashulka@ngs.ru Aleksandr Vasil’evich Kel’manov. Born 1952. Principal Researcher at the Soblev Institute of Mathematics of Siberian Branch of the Russian Academy of Sciences. Graduated from the Izhevsk State Technical University in 1974. Received candidate’s degree in 1980 and doctoral degree in 1994. Scientific interests: mathematical methods for pattern recognition, problems of discrete optimization, efficient algorithms for analysis and recognition of random sequences, study of algorithms for solving applied problems, methods and algorithms for processing, recognition, and synthesis of speech signals. Author of about 150 publications. Member of the Russian Association for Pattern Recognition, Russian Acoustic Society, Russian Scientific Center of Expertise, Expert Council of the Russian Foundation for Basic Research. Awards: golden medal of International exhibition “Siborobot-93” (1993), main prize in the competition of research papers on speech recognition of Hewlett-Packard company (1991), second-degree diploma in the competition of application studies of the Siberian Branch of the Russian Academy of Science (1989), the award of Military-Industrial Complex, USSR (1982). Homepage: http://math.nsc.ru/:∼kelmanov/index_ENG.htm E-mail: kelm@math.nsc.ru Sergei Asgadullovich Khamidullin. Born 1952. Senior Researcher at the Soblev Institute for Mathematics of Siberian Branch of the Russian Academy of Sciences. Graduated from the Novosibirsk State University in 1974. Received candidate’s degree in 1997. Scientific interests: mathematical methods for pattern recognition, problems of discrete optimization, efficient algorithms for analysis and recognition of random sequences, methods and algorithms for processing, recognition, and synthesis of speech signals. Author of about 90 publications. Awards: golden medal of International exhibition “Siborobot-93” (1993), main prize in the competition of research papers on speech recognition of Hewlett-Packard company (1991), second-degree diploma in the competition of application studies of Siberian Branch of the Russian Academy of Science (1989), the award of Military-Industrial Complex, USSR (1982). Homepage: http://math.nsc.ru/:∼serge/index_ENG.htm E-mail: kelm@math.nsc.ru     

Neural network based biometric personal identification with fast iris segmentation

This paper presents the iris recognition system for biometric personal identification using neural network. Personal identification consists of localization of the iris region and generation of a data set of iris images followed by iris pattern recognition. In this paper, a fast algorithm is proposed for the localization of the inner and outer boundaries of the iris region. Located iris is extracted from an eye image, and, after normalization and enhancement, it is represented by a data set. Using this data set a Neural Network (NN) is used for the classification of iris patterns. The adaptive learning strategy is applied for training of the NN. The results of simulations illustrate the effectiveness of the neural system in personal identification. Recommended by Guest Editor Phill Kyu Rhee. This work was supported by the Near East University. The authors would like to thank Institute of Automation, Chinese Academy of Sciences for providing CASIA iris database. Rahib Hidayat Abiyev was born in Azerbaijan, in 1966. He received the Ph.D. degree in Electrical and Electronic Engineering from Azerbaijan State Oil Academy (old USSR) in 1997. He worked as a Research Assistant at the research laboratory “Industrial intellectual control systems” of Computer-aided control system department. From 1999-present he is working as an Associate Professor at the department of Computer Engineering of Near East University. He is the Chairman of Computer Engineering Department. His research interests are softcomputing, pattern recognition, control systems, signal processing, optimization. Koray Altunkaya was born in Turkey, in 1982. He received the MSc. degree in Computer Engineering from Near East University, North Cyprus in 2007. He is working as an Research Assistant at the research laboratory “Applied Computational Intelligence” of Computer Engineering Department. His research interests are image processing, neural networks, pattern recognition, digital signal processing.     

Facial expression recognition of a speaker using front-view face judgment, vowel judgment, and thermal image processing

For facial expression recognition, we selected three images: (i) just before speaking, (ii) speaking the first vowel, and (iii) speaking the last vowel in an utterance. In this study, as a pre-processing module, we added a judgment function to distinguish a front-view face for facial expression recognition. A frame of the front-view face in a dynamic image is selected by estimating the face direction. The judgment function measures four feature parameters using thermal image processing, and selects the thermal images that have all the values of the feature parameters within limited ranges which were decided on the basis of training thermal images of front-view faces. As an initial investigation, we adopted the utterance of the Japanese name “Taro,” which is semantically neutral. The mean judgment accuracy of the front-view face was 99.5% for six subjects who changed their face direction freely. Using the proposed method, the facial expressions of six subjects were distinguishable with 84.0% accuracy when they exhibited one of the intentional facial expressions of “angry,” “happy,” “neutral,” “sad,” and “surprised.” We expect the proposed method to be applicable for recognizing facial expressions in daily conversation.     

Handwritten signature verification based on code representation

A method to obtain a code representation of handwritten signatures is described and an algorithm for signature verification based on such representations is proposed. Results of tests to determine efficient methods of image compression for the purpose of signature verification are presented. Konstantin Alekseev. Born 1979. Received Master’s degree in engineering and technology (Radioengineering) in 2002. Currently post-graduate student at St. Petersburg State Electrotechnical University “LETI”, chair of television and video. Scientific interests: digital image processing and pattern recognition. Author of three papers. Svetlana Egorova. Born 1931. Graduated from St. Petersburg State Electrotechnical University “LETI” in 1955, received Candidates degree (Eng.) in 1965; since 1968 a senior lecturer at the chair of television and video, St. Petersburg State Electrotechnical University “LETI”. Scientific interests: optical and digital image processing and compression methods in signal processing. Author of 141 papers.     

2nd Russian conference with international participation “hardware and software of control,surveillance, and measurement systems” (CSM-10) (Moscow,ICS RAS,October 18–20, 2010)

Information

2nd Russian conference with international participation “hardware and software of control, surveillance, and measurement systems” (CSM-10) (Moscow, ICS RAS, October 18–20, 2010)     

Optimal External Memory Planar Point Enclosure

In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surprisingly, despite the fact that the problem can be solved optimally in internal memory with linear space and O(log N+K) query time, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(log  _B N+K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B ^1−ε ) disk blocks are needed for some constant ε>0. With linear space, the best obtainable query bound is O(log ₂ N+K/B) if a linear output term O(K/B) is desired. To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds. An extended abstract of this paper appeared in Proceedings of the 12th European Symposium on Algorithms (ESA’04), Bergen, Norway, September 2004, pp. 40–52. L. Arge’s research was supported in part by the National Science Foundation through RI grant EIA–9972879, CAREER grant CCR–9984099, ITR grant EIA–0112849, and U.S.-Germany Cooperative Research Program grant INT–0129182, as well as by the US Army Research Office through grant W911NF-04-01-0278, by an Ole Roemer Scholarship from the Danish National Science Research Council, a NABIIT grant from the Danish Strategic Research Council and by the Danish National Research Foundation. V. Samoladas’ research was supported in part by a grant co-funded by the European Social Fund and National Resources-EPEAEK II-PYTHAGORAS. K. Yi’s research was supported in part by the National Science Foundation through ITR grant EIA–0112849, U.S.-Germany Cooperative Research Program grant INT–0129182, and Hong Kong Direct Allocation Grant (DAG07/08).     

Water resource quality monitoring using heterogeneous data and high-performance computations

This article presents the architecture of a system that is used for regional water resource quality monitoring of environmental parameters using heterogeneous data sources such as remote sensing data, model data, and data of in-situ observations. The system’s architecture and components are developed that are reusable and can be applied to solving various monitoring problems. The monitoring of the aquatic environment of the Dnieper estuary is selected as an example of such a problem. The distinctive features of this system consist of using a Grid approach to the distribution of complex computations and also the realization of computationally complicated computations on supercomputers of the SKIT family. Typical components of the monitoring system are presented, namely, those of data acquisition, data processing, modeling, and result representation. The development of the described monitoring system is partially supported by the UNTTs-NANU grant “Development of efficient Grid technologies of ecological monitoring on the basis of satellite data” (project No. 3872) and also joint INTAS-CNES-NSAU grant No. 06-1000024-9154 “Data Fusion Grid Infrastructure.” __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 179–188, July–August 2008.