「様式３」
課題番号P-9

Space and Time Efficient Image
Information Processing: from Theoretical Models to
Practical Implementation[1] Organization
Leader: Reneta P. Barneva (Department ofComputer Science, SUNY Fredonia, USA)
Representative at RIE: Kamen Kanev (ResearchInstitute of Electronics, Shizuoka University)
Participants:
Valentin E. Brimkov (Mathematics Department,Buffalo State College, State University of New
York, USA)
José Ramón Dorronsoro (Telecommunications
andComputing
Department,
EscuelaPolitécnica Superior, Universidad Autónoma
of Madrid (UAM) and Instituto de Ingenieríadel Conocimiento (IIC), UAM, Spain)
Kostadin Koroutchev (Universidad Autónoma ofMadrid, Spain)
Alberto Suarez (Universidad Autónoma of Madrid,Spain)
Antoine Deza (Department of Computing andSoftware, Faculty of Engineering, McMasterUniversity, Canada)
Daniel D. Cunningham (Mathematics Department,Buffalo State College, State University of New
York, USA)
Michael Vynnycky (Department of Mathematicsand Statistics, University of Limerick, Ireland)
Francois de Vieilleville (Department ofMathematics, University of Savoie, France)
Rosen Kostadinov (Universidad Autónoma ofMadrid, Spain)
Akira Takahashi (Faculty of Informatics,Shizuoka University)[2] Progress of the Research
In the nine month project period (May 2010 –March 2011) the team worked on the researchtasks outlined in project description. The work
was continuation of the successful previous
project conducted from June 15, 2009 to March16, 2010. Part of the work was coordinated anddone through electronic communications on
Skype and through e-mail. Another part wasaccomplished in face-to-face meetings. Some ofthe project members gave talks at seminars andconferences. A detailed description of themeetings and visits is given at the end of thereport.

Project members were also involved in organizing
the International Symposium on Modeling ofObjects Represented in Images, which was held in
May 2010 in Buffalo, NY. Its Program
Committee members are renowned experts
coming from 25 different countries. Submissions
to the symposium came from 22 countries fromAfrica, Asia, Europe, North and South America.
Overall, representatives of 32 countries
contributed to the symposium in different
capacities. Profs. Barneva and Brimkov weregeneral chairs, Prof. Kanev was a member of theProgram Committee, and Prof. Cunningham was amember of the Organizing Committee. A special
guest of the symposium was Dr. Herbert
Hauptman, Nobel Laureate. He also served as an
editor of the proceedings published in Lecture
Notes in Computer Science, Springer [1]. Anothervolume devoted to papers from the Special Trackon Object Modeling, Algorithms and Applications
was published by Research Publishing Services(Singapore) [2].
A special issue of IJIST Entitled “Combinatorial
Problems and Algorithms in Image Analysis”
edited by Profs. Barneva and Brimkov wasdevoted to the latest theoretical findings incombinatorial image analysis and practicalapplications appeared in March 2011 [3]. Eightpapers presenting new structural results andalgorithms in digital geometry and topology andaddressing various applications of image analysis
and processing were included in the volume.
In the course of the research, both theoretical andexperimental studies have been carried out. Thiseffort resulted in obtaining a series of results on
space and time efficient computation regarding
the theoretical foundations of this research area aswell as related applications. Overall, most of theproject tasks have been accomplished, and some
unexpected new results have been obtained.
[3] Results(3.1) Research results
We worked in two main directions:A. Time- and space-efficiency of embedded
software of intelligent peripherals. We are
currently working on improvement of theefficiency of CLUSPI technology using methods
intrinsic to the applied coding. In particular, weare constructing algorithms that would reconstruct
missing information due to noise or surface wear
and defects. [4]Another research task was dedicated to visual
encoding of surfaces for absolute positioning andglobal navigation by optical means. Special
attention was paid to seamless coded patterns
suitable for interior decoration. Single figure typepatterns over equally and non-equally spacedgrids were constructed and figure directional
vector calculation tests were implemented.
Experiments were carried out for integrating theCluster Pattern Interface (CLUSPI) for blocklessencoding and the Seamless Coded Pattern (SCP)
methods in a more flexible, unified surface
marking and localization system. [7]
B. Computation of topological image invariants
We introduced a special type of digital objects
called digital stars with special points from which
all other points can be “seen.” The continuous
counterparts were studied since the early 20thcentury, but there was no research in the field ofdigital stars. Problems on stars are closely related
to convexity issues. We initiated a study on digitalstars particularly motivated by possible
applications in computer vision. We defined thenotion of digital star, derived several basic
properties, and consider relations between digitalstarshapedness, continuous starshapedness, anddigital convexity. In particular, we showed that
Krasnosel'skii’s theorem does not hold for digitalstars, in general. We also conjectured thatcomputing the surveillance/star decomposition
number is NP-hard. Future work is aimed atconstructing a time and space-efficient algorithm
for finding a center of a digital star. Extending theconsiderations to higher dimensions is seen as
another important task. [6]Another trend of our work was the investigationof the properties of a digital object obtained bytaking the integer points within an offset of acertain radius of the object. Our considerations
apply to digitizations of arbitrary path-connected
sets in an arbitrary dimension n. Interestingcorollaries were derived for the important special
case of surfaces, as well as for offsets ofdisconnected sets. [5](3.2) Future work
Some of the results, already reported atinternational conferences will be extended andsubmitted for consideration and publication in
special issues of reputable scientific journals. (See,e.g. [4].)The obtained results are groundwork fordeveloping various implementations and solving
practical problems. They can also be used as aseed results for future projects for which the teamwill apply for external funding and support.
In the framework of the research meetings andvisit exchange, ways to deepen the collaboration
were outlined. In particular, formal exchange
agreements between RIE-Shizuoka University andthe partner universities were discussed. There isalready a former undergraduate student from
SUNY Fredonia, Ms. Kaori Sagawa, who iscurrently pursuing her master’s degree at
Shizuoka University as a result of the visit andpresentation of Prof. Kanev. We are looking
towards more opportunities.
[4] Publications(1) Barneva, R.P., Brimkov, V.E., Hauptman,
H.A., Natal, R.J., Tavares, J.M.R. (Eds.)
Computational
ModelingofObjects
Represented in Images, Springer Verlag,
LNCS 6026, Berlin-Heidelberg, 2010.
(2) Barneva, R.P., Brimkov, V.E., Natal, R.J.,
Tavares, J.M.R. (Eds.) Object Modeling,Algorithms, and Applications, Research
Publishing Services, Singapore-Chennai,
2010.
(3) Barneva, R.P., Brimkov, V.E., Wiederhold, P.,
Combinatorial Problems and Algorithms inImage Analysis, International Journal ofImaging Systems and Technology (Wiley) 21(2) March 2011.
(4) Barneva, R.P., Brimkov, V.E., Kanev, K.,
Theoretical Developments for Direct-Access
Pattern Interfaces, (in preparation).
(5) Brimkov, V.E., Connectedness of Offset
Digitizations in Higher Dimensions, In:Computational
ModelingofObjects
Represented in Images, Lecture Notes in
Computer Science (Springer Verlag), 6026,
Berlin-Heidelberg, 2010, pp. 36-46.
(6) Brimkov, V.E., Barneva, R.P., Digital starsand visibility of digital objects, In:
Computational
ModelingofObjects
Represented in Images, Lecture Notes in
Computer Science (Springer Verlag), 6026,
Berlin-Heidelberg, 2010, pp. 11-23.
(7) Kanev, K., Kato, H., Koroutchev, K.,
Encoding of Surfaces for Global Positioningand Navigation, The Journal of Three
Dimensional Images, Vol. 24, No. 3, 2010, pp.
51-57.

Travelling report
Name:
Affiliation:
Period of time:
Destination:
Purpose:Name of receiver:Name:
Affiliation:
Period of time:
Destination:
Purpose:Name of receiver:Name:
Affiliation:
Period of time:
Destination:
Purpose:Name of receiver:Name:
Affiliation:
Period of time:
Destination:
Purpose:Name of receiver:

Kostadin Koroutchev
Universidad Autónoma of Madrid, Spain
June 8, 2010 – August 10, 2010
Shizuoka University, Japan
To participate in cooperative research and the preparation of joint publications and togive a talk on “Figures Design for Coding with Orientation” at the 190th Monday
Moring Forum (MMF) organized at RIE.
Prof. Kamen Kanev
Alberto Suarez
Universidad Autónoma of Madrid, Spain
January 23, 2011 – January 30, 2011
Shizuoka University, JapanTo discuss the cooperative project organization and research, to participate inresearch meetings, and to give a talk entitled “The Arrow of Time in Time Series”.
Prof. Kamen Kanev and Prof. Akira Takahashi
Michael Vynnycky
University of Limerick, Ireland
November 15, 2010 – November 18, 2010
Shizuoka University, JapanTo discuss the cooperative project organization and research and to give a talkentitled “A New Look at the P3P Problem”.
Prof. Kamen Kanev
Reneta Barneva
Department of Computer Science, SUNY Fredonia, USA
February 25, 2011 – March 6, 2011
Shizuoka University, JapanTo plan the future collaboration, coordinate the ongoing research, and participate in acollaborative research seminar organized at RIE with a presentation entitled “Spaceand Time Efficient Image Information Processing: Computation of TopologicalImage Invariants”
Prof. Kamen Kanev