「様式３」課題番号 ：P-15

Space and Time Extremely High Performance Algorithms
and Models for Image Information Processing[1] Organization
Project Leader: Reneta P. Barneva (Departmentof Computer Science, SUNY Fredonia, USA)
Representative at RIE: Vygantas Mizeikis(Research Institute of Electronics, Shizuoka
University)
Participants:
Valentin E. Brimkov (Mathematics Department,
Buffalo State College, State University of New
York, USA)
Daniel D. Cunningham (Mathematics Department,
Buffalo State College, State University of New
York, USA)
Antoine Deza (Department of Computing and
Software, Faculty of Engineering, McMaster
University, Canada)
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)
Rémy Malgouyres (IUT Department ofInformatics, Université d'Auvergne (Clermont1), France)
Vygantas Mizeikis (Research Institute ofElectronics, Shizuoka University, Japan)
Volodymyr Gnatyuk (V.E. Lashkaryov Institute of
Semiconductor Physics, National Academy of
Sciences of Ukraine)
Kostadin Koroutchev (Universidad Autónoma of
Madrid, Spain)
Alberto Suarez (Universidad Autónoma of Madrid,
Spain)
Akira Takahashi (Faculty of Informatics,
Shizuoka University)
Sergey Gagarsky (Quantum Electronics andBiomedical
OpticsDepartment,
State
University of Information Technologies,
Russia)Michael Vynnycky (Department of Mathematics
and Statistics, University of Limerick, Ireland)
Robert Olson (Department of Computer Science,
SUNY Fredonia, USA)
Rossen Kostadinov (Faculty of Arts andPhilosophy, Universidad Autonoma de Madrid,
Spain)

Boris Brimkov (Department of Computational andApplied Mathematics, Rice University, USA)
Andrew David Speers (Department of Computer
Science and Engineering, Faculty ofEngineering, York University, Canada)
Carlos Asencio Pizarro (Departamento deIngenieria Informatica, Escuela Politecnica
Superior, Universidad Autonoma de Madrid,
Spain)
Kamen Kanev (Graduate School of Informatics,
Shizuoka University)[2] Progress of the Research
The participants had active scientificcollaboration through electronic media and a faceto-face Workshop January 27-31, 2014 at whichsome of them met. They reported the achieved
results, exchanged ideas about future join work,and discussed possibilities for further cooperation
between the institutions.
Apart from the specific results described in
the next section, the team members were involvedin the organization of several major international
forums and in the publishing of a special issue ofa reputable journal, both of them devoted to topicsof the project.
• Several project members are also involved in
the organization of the 16th International
Workshop on Combinatorial Image Analysis,
to be held in May 2014 in Brno Czech
Republic. Prof. Reneta P. Barneva is a
Program and Publication Chair. Profs.
Valentin Brimkov and Kostadin Koroutchev
are members of the Steering Committee as
the former is also an invited speaker. The
proceedings of the workshop are submitted
and will be published in Lecture Notes in
Computer Science, Springer [1].
• Prof. Antoine Deza was the organizer of theRetrospective
WorkshoponDiscrete
Geometry, Optimization, and Symmetry, heldat the Fields Institute, Toronto, Ontario,
November 25-29, 2013. The workshop
attracted participants from such prestigious
universities as MIT, Stanford, Vanderbuilt,
Tokyo University of Technology, University

「様式３」
College London, Universidad Nacional
Autónoma de México, and others. The
abstracts of the talks are available at [2].
• Prof. Antoine Deza was the organizer of theSecond Industry-Academic Workshop on
OptimizationinFinanceand
RiskManagement,
attracting
experts fromdifferent areas. It was also held at the Fields
Institute, Toronto, Ontario, in September 2324, 2013. Some of the industrial participants
were from top institutions as IBM, Goldman
Sachs Asset Management, Bank of Montreal,
Royal Bank of Canada, Scotiabank, andothers [3].
• Prof. Kamen Kanev was a PC Chair of the
16th International Conference on Humans andComputers held at Shizuoka University andjointly organized with the iCAST2013 and
UMEDIA2013
conferences
andtheInternational Symposium on Spatial Media(ISSM’13-’14).
• Dr. Volodymyr Gnatyuk was a member of theInternational Committee of The 14th
International Young Scientists Conference“Optics and High Technology Material
Science” (SPO 2014), held at the Faculty ofPhysics of Taras Shevchenko National
University of Kyiv, Ukraine, October 24-27,
2013.
• Dr. Volodymyr Gnatyuk presented the
project-related
results
at
The
12th
International Conference on Global Researchand Education: Inter-Academia-2013, held at
the University of Sofia, Bulgaria, September
23-27, 2013.
• Dr. Volodymyr Gnatyuk reported the reviewof the laser marking and encoding results attheCooperative
ResearchWorkshop“Imaging Devices and Digital Imaging of
Semantic Surfaces in Active Knowledge
Management”, held at RIE, Shizuoka
University, Hamamatsu, Japan, November 15,
2013.
• A special issue of Annals of Mathematics andArtificial Intelligence (Springer), edited byProfs. Barneva and Brimkov, is being
prepared for publication [4]. The issue is stilla work in progress, but is expected to appear
soon. All accepted papers are of very highquality and some of them are directly related
to the theme of the Cooperative Research
Project (for example, the papers “Efficient
Segmentation with the Convex Local-Global
Fuzzy Gaussian Distribution Active ContourforMedicalApplications,”“Cellular
Topology and Topological Coordinate
Systems on the Hexagonal and on the
Triangular Grids,” “Convenient Adjacencies
for Structuring the Digital Plane,” “On 2D
Constrained Discrete Rigid Transformations,”
and “Contextual Array Grammars and Array
P Systems.”[3] Results(3.1) Research results
The twelve significant results obtained in theframework of the Cooperative Research Project
can be grouped into the following six major
themes:Time- and space-efficiency of embedded
software of graphical intelligent peripherals.
1) In [5] the authors discuss the design anddevelopment of an improved CLUSPI method foraugmented computer vision and positioning ofautonomous agents in indoor settings. The method
employs environmental patterns posted on walls,
ceilings, floors, and other surrounding surfacesthat are accessible for digital imaging. Suchpatterns are blended into the environment as
decorative elements where the encoding anddecoding is based on orientation and clustering ofartistic figures. As part of this work a specializedclient-server
systemfor
multi-platform
experiments with various environmental codes
and imaging devices have been implemented.
Conducted experiments indicate robust andreliable code extraction with extremely highrecognition rates in most practical setups.
2) and 3) Works [6, 7] present the design andimplementation of time- and space- efficientalgorithms for the purposes of CLUSPI
application on large surfaces. Various laserassisted technological approaches and methods
suitable for optical recording of digital
information by creation of micromarks (data bits,
pixels, and other information carriers) in the bulkof materials, transparent for a selected laser
wavelength are evaluated and discussed. A
marking center refers to a local area with opticalproperties different from the ones of the bulk
obtained in result of actions of short laser pulses
tightly focused in the volume of a transparent
dielectric. Depending on the characteristics oflaser pulses (wavelength and duration), selectedmaterials (such as glass, plastic, organic medium,etc.) and irradiation conditions, a resulting laserinduced mark can be a point microcrack or void
(pore), parameterized centers with different sizes「様式３」and orientations, colored or light emitting centers,
as well as any other local inhomogeneity causedby thermal breakdown, optical excitation,
chemical reaction or burning of material. Laserinduced marks with varying appearance (or data
pixels) can serve as multi-bit information carriers
that open a wide range of new possibilities formarking, encoding, and recording of digital
information and creation of images.
Mathematical models of high performancetime and space algorithms for image
information processing.
4) Differentials estimation of discrete signals
is almost mandatory in digital segmentation. A
previous work by team members, introduced fastlevel-wise convolution (LWC) with timecomplexity O(n log m). The research wascontinued, as convergence proofs were devisedfor two LWC compatible kernel families [8]. The
first one is the pseudo-binomial family, and thesecond one is the pseudo-Gaussian family. The
proposed method was experimentally compared to
the Digital Straight Segment tangent estimator.
Tests are done on different digitized objects at
different discretization step using the DGtal
library.
5) A major problem in computer graphics,
image processing, numerical analysis and otherapplied areas is constructing a relevant object
discretization. In a recent work, a project teammember investigated an approach for constructing
a connected discretization of a subset A of the ndimensional Euclidean space by taking the integer
points within an offset of A of a certain radius.
The minimal value of the offset radius whichguarantees connectedness of the discretization
was determined, provided that set A is pathconnected. In [9] these results have been
essentially strengthened by proving that the same
results hold when A is connected, but notnecessarily path-connected. Moreover, it isdemonstrated that similar facts hold about
Hausdorff discretization, thus generalizing known
results of other researchers.
Efficient algorithms for solving problems on
maps.
Given a finite set of straight-line segments S
in the plane, one considers the problem of findinga minimum in size set V of points on the segments,
such that each segment of S contains at least one
point in V. This problem was called guarding a setof segments (GSS). GSS is a special case of theset cover problem where the given family ofsubsets can be taken as a set of intersections of
the straight line segments in S. Requiring that thegiven subsets can be interpreted geometricallythis way is a major restriction on the input, yet it
has been shown that the problem is still strongly
NP-complete. GSS is relevant to any physicalstructure that can be modelled by a finite set ofstraight-line segments. Examples could be a
network of streets in a city, tunnels in a mine,
corridors in a building or pipes in a factory. One
looks for a minimum number of locations at
which to place ‘guards’ in a way that any point of
the structure can be ‘seen’ by at least one guard(assuming guards have infinite visibility range inall directions, but cannot see around corners). An
equivalent problem is to find a minimum numberof locations to place ‘terminals’ so that any pointof the network has a direct access to at least one‘terminal’ at all times.
6) In previous work by a project teammember the GSS approximability was studied
both theoretically and experimentally. These
investigations were continued as part of the
project. In [10] further results were obtained thatshed more light on GSS approximability. In
particular, conditions were found under which
GSS defined on drawings of arbitrary (notnecessarily planar) graphs admits good
approximation. As a consequence, other moregeneral results about GSS approximability wereobtained. Thus it was shown that GSS on asegment set with almost tree (1) structure is (2 −ε)-approximable for 0 < ε ≤ 1, and that GSS on arandom graph drawing is almost surely 2approximable.
Computational and geometric approach tocolorful simplicial depth – a problem without aknown polynomial time algorithm.
7) The research activities around the colorful
simplicial depth and the colorful linear
programming feasibility problem resulted in aseries of recent advances. A significant lower
bound improvement by team was made in [11] by
employing a purely combinatorial approach.
More specifically, the colorful simplicial
depth conjecture states that any point in theconvex hull of each of d + 1 sets, or colours, of d+1 points in general position in Rd is contained in
at least d2 +1 simplices with one vertex from eachset. In [11] the conjecture was verified indimension 4 and the known lower bounds were
strengthened in higher dimensions. These results
are obtained using a combinatorial generalizationof colorful point configurations called octahedral

「様式３」
systems. New properties of octahedral systems
were obtained, generalizing earlier results oncolorful point configurations and exhibiting anoctahedral system which cannot arise from acolorful point configuration. The number ofoctahedral systems is also given.
Space-efficient algorithms for graph problems
related to image processing8) The shortest path problem is fundamental
to many areas of image processing. In [12],approaches were presented that allow solving the
problem in environments where computation
space is scarce. Two constant-work-spacealgorithms are proposed for solving the shortest
path problem for cactus graphs and clique-cactus
graphs of arbitrary size. Both algorithms perform
in polynomial time. Moreover, an in-placealgorithm for finding the shortest path in cactus
graphs is presented, which performs inpolynomial time of lower degree.
As an image can easily be modeled by its
adjacency graph, graph theory and algorithms ongraphs are widely used in imaging sciences. In[13] and [14] we study the problem of finding the
maximal cliques of the intersection graphs ofcertain polygons. Intersection graphs appear
applicable to numerous research domains, inparticular computer imagery. A major application
is found in representation and visualization ofrelations among objects in a scene. This includes
data visualization for the purposes of software
engineering,drawing
Euler
diagrams,
visualization of overlapping clusters on graphs,
video database queries; in graph-based
recognition and visualization of grid patterns instreet networks, solid intersection, andcontingency tables. Moreover, intersection graphbased discrete models of continuous ndimensional spaces have been developed to solve
problems of surface graphics. Algorithms for
maximal clique computation are applicable tocomputer graphics and image analysis. Thus,
maximal clique computation has been applied toimage segmentation and to deformable object
model learning in image analysis. Maximal cliquecomputation on certain intersection graphs is also
relevant to problems of computer vision andcomputer graphics, as well as to visualization innatural sciences. For samples of the abovementioned applications see [14] and thereferences therein.
9) We presented results which extended andgeneralize ones related to studies on maxtolerance, semi-square, and convex polygon

intersection graphs. We considered the maximal
clique problem defined on intersection graphs ofconvex polygons, quasi-homothetic trapezoids,
and homothetic triangles, the latter being
equivalent to the max clique problem defined on
max-tolerance graphs. For the case of quasihomothetic trapezoid graph studied in [13], we
showed that the number of maximal cliques insuch graphs is Θ(n3) which improved thepreviously known Θ(n4) bound. We alsopresented a space-efficient in-place algorithm forfinding the maximum clique on such graphs. We
reported experimental results of a computer
implementation of our algorithm on randomly
generated sets of polygons of the considered type.
The experiments confirmed the expected cubic
regression for the number of maximal cliques insemi-square graphs, which has been proved only
for an artificially constructed class of instances.
Other experiments showed that the well-known
Lovasz theta function approximates very well theclique number for the considered classes ofgraphs.
10) In [14] we studied the maximal clique
problem on intersection graphs of convex
polygons. We presented results which refine or
improve some of the results recently proposed byothers. Thus, it was shown therein that anintersection graph of n convex polygons whosesides are parallel to k different directions has no
more than n2k maximal cliques. We proved thatthe number of maximal cliques does not exceed nk.
Moreover, we showed that this bound is tight for
any fixed k. We also discussed algorithmic
aspects.
Other research problems and results
In addition to the basic project tasks
considered above, team members carried out
research on other important problems related to
the general project theme.
Combinatorics on words with applications topattern matching problems
The characterization and detection ofrepetitive structures arises in a variety of
applications in imaging sciences. In fact, studying
repetitions, periodicities, and other similar
regularities play a central role in various facets ofcomputer science and subtend properties that areeither interesting and deep from the standpoint of
combinatorics, or susceptible to exploitation intasks of automated inference and datacompression, or both. In strings, the notions of arepetition or square (i.e., two consecutive

「様式３」
occurrences of a same primitive word), isintermingled with the dawn of language theory
and combinatorics on strings.
In the framework of the Cooperative
Research Project, the following two problems
have been considered.
11) Fraenkel and Simpson conjectured in1998 that the number of distinct squares in astring is at most its length. Kolpakov andKucherov conjectured in 1999 that the number ofruns in a string is also at most its length. Since
then, both conjectures attracted the attention ofmany researchers and many results have beenpresented, including asymptotic lower bounds forboth, asymptotic upper bounds for runs, anduniversal upper bounds for distinct squares interms of the length. In [15], a project teammember proposed a parametrized approach forestimating the maximal number of squares andruns in a string. The approach provides acomputationally efficient framework allowing toconfirm and extend earlier experimental results byother researchers.
12) Recently, efforts have been made at
generalizing clever string searching techniques,notions and results to structures of higher
dimensions, particularly two-dimensional arrays,
where texts and patterns can be considered as“bit-map” images, represented by matrices ofpixels and stored in a database. This is naturally
driven by various applications to patternrecognition, low level image processing,computer vision and, more recently, multimedia.
Combinatorial pattern matching problems
have been studied in the framework of diverse
computation models and settings. Numerous
algorithms exist (mostly for problems on strings),
including optimal sequential algorithms, online
algorithms, algorithms that solve a problem inreal time, or ones that use only constant auxiliary
space in addition to the input. In [16] weintroduce the reader to parallel computation
approach for pattern matching problems. We
discuss the basic steps of a parallel algorithm
design, illustrating them by author's results on the
problem of detecting all two-dimensional
repetitions in a two-dimensional array.
(3.2) Future work
The obtained theoretical results laid out a basis
for solving various practical problems. The teamis considering extending the work for new models
and algorithms. Of special interest are the results
for mobile devices.

In the framework of the research meetingsand visit exchange, ways to deepen thecollaboration were outlined.
[4] Publications(1) Barneva, R.P., Brimkov, V.E., Slapal, J,(Eds.) Computational Image Analysis,
Springer Verlag, LNCS, Vol. 8466,
Heidelberg-Berlin, 2014.
(2) http://www.fields.utoronto.ca/programs/scient
ific/13-14/discretegeom/Abstracts.html(3) http://www.fields.utoronto.ca/videoarchive/event/192/2013.
(4) Brimkov, V.E., Barneva, R.P. (Eds.), Annalsof Mathematics and Artificial Intelligence(Springer), to appear in 2014.
(5) Barneva, R., Kanev, K., Mochiduki, Sh.,
Position Encoding and Localization withEnvironmental Patterns, Western New York
Image Processing Workshop, Rochester
Institute of Technology, November 2013, pp.
43-46.
(6) Zelenska, K.S., Zelensky, S.E., Poperenko,
L.V., Rozouvan, S.G., Kanev, K., Mizeikis,
V., Gnatyuk, V.A., Thermal mechanisms oflaser marking in transparent polymers withlight-absorbing microparticles, Journal of
Physics: Conference Series, to appear.
(7) Gnatyuk, V.A., Vlasenko, O.I., Levytskyi,
S.N., Kanev, K., Mizeikis, V., Aoki, T.,
Gagarsky, S.V., Poperenko, L.V., Zelenska,
K.S., Statsenko, A.O., Features of laserinduced damage and creation of marking
centers in digital material processing, Journalof Physics: Conference Series, to appear.
(8) Gonzalez, D., Malgouyres, R., Esbelin, H.-A.,
Samir, Ch., Convergence of Level-Wise
Convolution Differential Estimators, Proc.
Discrete Geometry for Computer Imagery,2013, pp. 335-346.
(9) Brimkov, V., On Connectedness ofDiscretized Objects, G. Bebis et al. (Eds.):
ISVC 2013, Part I, LNCS (Springer) 8033, pp.
246–254, 2013.
(10) Brimkov, V.E., Approximability issues ofguarding a set of segments, International
Journal of Computer Mathematics, Taylor &Francis, pp. 1653-1667 (2013).
(11) Deza, A., Meunier, F., Sarrabezolles, P., A
combinatorial
approachtocolourful
simplicial depth. SIAM Journal on Discrete
Mathematics 28 (2014) 306 - 322.
(12) Brimkov, B., Memory Efficient Shortest Path
Algorithms for Cactus Graphs, G. Bebis et al.
(Eds.): ISVC 2013, Part I, LNCS (Springer)
8033, pp. 476–485, 2013.
(13) Brimkov, V.E., S. Kafer, M. Szczepankiewicz,
J. Terhaar, Maximal cliques in intersection

「様式３」
graphs of quasi-homothetic trapezoids,
Proc.MCURCSM'13, Ohio, paper No 10, 10
pp. (2013).
(14) Brimkov, V.E., S. Kafer, M. Szczepankiewicz,
J. Terhaar, On Intersection Graphs of Convex
Polygons, Proc. 16th International Workshop
on Combinatorial Image Analysis, Lecture
Notes in Computer Science, to appear.

(15) Deza, A., Franek, F, A d-step approach to the
maximum number of distinct squares andruns in strings. Discrete Applied Mathematics
163 (2014) 268–274.
(16) Brimkov, V.E., Parallel algorithms for
combinatorial
patternmatching,
16th
International Workshop on Combinatorial
Image Analysis, Lecture Notes in Computer
Science, to appear.

「様式３」
Travelling report
Name:
Affiliation:
Period of time:
Destination:
Purpose:Name of receiver:Name:
Affiliation:
Period of time:
Destination:
Purpose:Name of receiver:

Reneta Barneva
State University of New York at Fredonia, USA
January 23, 2014 – February 1, 2014
Research Institute of Electronics, Shizuoka University, Japan
Participation in the Planning and Coordination Meeting of the 2013-14 Cooperative
Research Project and the related workshop, Research Institute of Electronics,
Shizuoka University, Hamamatsu. Giving a talk “Digital Geometry Algorithms andModels for Advanced Imaging Devices” and moderating a round table discussion
about the possibilities of institutional cooperation.
Prof. Kamen Kanev
Valentin Brimkov
State University of New York at Fredonia, USA
January 23, 2014 – February 1, 2014
Research Institute of Electronics, Shizuoka University, Japan
Participation in the Planning and Coordination Meeting of the 2013-14 Cooperative
Research Project and the related workshop, Research Institute of Electronics,
Shizuoka University, Hamamatsu. Giving a talk entitled “Complexity andApproximability Issues in Image Analysis.”
Prof. Kamen Kanev