ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2014. Vol. 9

Analyse of Sketch Images with Metrics

M. D. Katashevtsev

The article considers to the problem of analysis of sketch images within the logical-heuristic paradigm. A model representation of raster contour image as a system of arcs and links arcs. Each arc is connected to another arc through the linked arcs relation. Arcs and arcs relations represent as primitives with a given set of properties. In the basic model the arc has two properties - degree measure of the arc and the direction of traversal (clockwise or counterclockwise). This paper introduces a new extended model of representation of raster contour image. The new model extends the concept of the arc by adding a relative arc length (relative to other arcs forming the system of arcs of the image). We are considering an algorithm for constructing a new model based on skeletizated image. We present procedure of the reduction of the samples tree for the extended model to the samples tree of the base model. Reviewed estimates of the complexity of new algorithms. Provides estimates of the complexity of the basic recognition algorithms. The results showing that the introduction of the extended model does not affect the complexity of the basic recognition algorithms. It is suggested that the addition of any finite number of features to arc concept design wont affect the complexity of recognition. Offered the new method of the reducing the number of samples in the samples tree as implementation of the detailing procedure, comprising removing from a sample the arcs whose relative size is less than some userdefined threshold.

computer graphics, image recognition, logic-heuristic, raster, algebraic system, relative metrics

1. Martyanov V.I., Katashevtsev M.D. Combinatorial problems of high complexity and analyse of sketch images [Kombinatornye zadachi vysokoj slozhnosti i analiz ploskih konturnyh izobrazhenij], Izvestija Irkutskogo GosudarstvennogoUniversiteta Ser. "Matematika 2013, no. 4, pp. 31-47.

2. Katashevtsev M.D. Wave Skeletization [Volnovaja skeletizacija], Vestnik Irkutskogo Gosudarstvennogo Tehnicheskogo Universiteta, 2013, no. 7, pp. 89-92.

3. Martyanov V.I., Arkhipov V.V., Katashevtsev M.D., Pakhomov D.V. Logical heuristic methods for solving combinatorial problems of high complexity. Applications review [Obzor prilozhenij logiko-jevristicheskih metodov reshenijakombinatornyh zadach vysokoj slozhnosti], Sovremennye tehnologii. Sistemnyj analiz. Modelirovanie. [Modern technologies. System analysis. Modeling.] IRGUPS., 2010, no. 4(28), pp. 61-67.

4. Garey M., Johnson D. Computers and Intractability [Vychislitel’nye mashiny i trudnoreshaemye zadachi]. Moscow, Mir, 1982.

5. Malcev A.I. Algebraic Systems [Algebraicheskie Sistemi]. Moscow, Nauka, 1967.

6. Bellman R. Dynamic programming [Dinamicheskoe programmirovanie]. Moscow foreign papers publishing, 1960.

Full text (russian)