課題番号 ：P-8

Space and Time Efficient Image Information
Processing: Paradigms and Prototypes[1] Organization
Leader: Reneta P. Barneva (Department ofComputer Science, SUNY Fredonia,USA)
Representative at RIE: Kamen Kanev(Research Institute of Electronics,
Shizuoka University)
Participants:

JoséRamón

Dorronsoro(Telecommunications and Computing
Department,
EscuelaPolitécnica
Superior, Universidad Autónoma ofMadrid (UAM) andInstituto deIngeniería del Conocimiento (IIC), UAM,Spain)
ValentinE.
Brimkov(Mathematics
Department, Buffalo State College, State
University of New York, USA)
Rémy Malgouyres (IUT Department ofInformatics,
Université
d'Auvergne(Clermont 1), France)
Antoine Deza (Department of Computingand Software, Faculty of Engineering,
McMaster University, Canada)
Kostadin
Koroutchev(UniversidadAutónoma of Madrid, Spain)
Alberto Suarez (Universidad Autónoma ofMadrid, Spain)
Daniel D. Cunningham (Mathematics
Department, Buffalo State College, State
University of New York, USA)Elka Korutcheva (Universidad Nacional deEducación a Distancia, Spain)
Volodymyr Gnatyuk (V.E. Lashkaryov
Institute of Semiconductor Physics,
National Academy of Sciences ofUkraine)
Sergey Gagarsky (Quantum Electronics andBiomedical Optics Department, StateUniversity of Information Technologies,Russia)
MichaelVynnycky(DepartmentofMathematics and Statistics, Universityof Limerick, Ireland)
Francois de Vieilleville (Department ofMathematics, University of Savoie,France)
Robert Olson (Department of ComputerScience, SUNY Fredonia, USA)

Andrew David Speers (Department ofComputer Science and Engineering,
Faculty of Engineering, York University,Canada)
Akira Takahashi (Faculty of Informatics,Shizuoka University)[2] Progress of the ResearchThis project is a continuation of theprevious successful project conducted fromMay 2011 to March 2012. In the period ofthe current project 2012/05/23 - 2013/03/08
the team worked on several research tasks
as outlined in project description. Apartfrom the electronic communication throughe-mail, Skype, and phone, we exchanged
research visits, had face-to-face meetings,and attended together conferences andworkshops. In addition to the meetings andvisits funded by the grant and listed at theend of the report, Prof. Kamen Kanev
visited SUNY Fredonia hosted by Prof.
Reneta Barneva and delivered two talks
and Prof. Valentin E. Brimkov visited
Université d'Auvergne hosted by Prof.
Rémy Malgouyres and delivered a talk.
Several project members were also involvedintheorganizationofthe15thInternational Workshop on Combinatorial
Image Analysis, held in November 2012 inAustin, TX, USA. General Chair of theconference was Prof. Valentin Brimkov. Prof.
Reneta P. Barneva was a Program andPublication
Chair.
Profs.
Kostadin
Koroutchev and Valentin Brimkov weremembers of the Steering Committee, Prof.
Rémy Malgouyres was a member of theProgram Committee, and Prof. Reneta
Barneva served as Chair of the Organizing
Committee. The proceedings of theworkshop were published in Lecture Notes
in Computer Science, Springer [1].
Another conference that gathered many
project
participants
wasthe15th
International Conference on Humans andComputers held in Shizuoka, Japan,February 11-12, 2013. Prof. Kanev wasProgram Chair and member of theInternational Advisory Committee; Prof.
Barneva was invited speaker [2]. They aswell as Drs. Michael Vynnycky andVolodymyr Gnatyuk participated withpresentations [3,4,5].
A special issue of International Journal ofComputer
Mathematics(TaylorandFrancis), edited by Profs. Brimkov andBarneva, is prepared for publication [6].
The issue contains eight papers devoted tovarious theoretical and practical issues
such as topology preserving hexagonal
thinning; combinatorial algorithm toconstruct
3D
isotheticcovers;
isoperimetrically optimal polygons in thetriangulargridwith
Jordan-type
neighborhood on the boundary; ischemic
heart disease detection using support vector
machines;
Jordan curve theorem withrespect to a pretopology on Z2; singularity
analysis in digital signals through theevaluation of their unpredictable point
manifold;
approximability
issuesofguarding a set of segments; and recognitionof concurrency relations between inaccuratelines.
The work on the project resulted in
obtaining a series of results on space andtime efficient computation based on
different models. Details are given in thenext section.
[3] Results(3.1) Research results
Results in the following four directions wereachieved:
A. Mathematical foundations of image
information processing. The models andparadigms used for image representation
arecriticalfor
thetimeandspace-efficiencyof
theinformationprocessing. In many cases, the models
should also allow deriving some geometricalproperties such as area, distances, angles,
and derivatives of the geometrical objects.
The work [7] deals with estimation ofdifferentials of discrete signals which isalmost mandatory in digital segmentation.
A new fast method was presented based onconvolutions by a mask with a logarithmic
number of constant layers. It was comparedto other multigrid convergent methods inthe field such as the Binomial Convolution,
the Digital Straight Segment Tangent
Estimator, and the Taylor PolynomialFitting. Our convolution method’s main
advantage is its complexity of O(2n.log2(m)),
which makes it competitive to theconvolution by Fast Fourier Transform(FFT) latest implementation. The precisionof the first order derivative estimation, its
resistance to noise, and its convergence rate
were tested.
Another work [8] introduces a new method
to compute conformal parameterizations
using a recent definition of discrete
conformity, and establishes a discrete
version of Riemann mapping theorem. The
algorithm can parameterize triangular,quadrangular, and digital meshes. It canalso be adapted to preserve metricproperties. The efficiency of the method isdemonstrated
throughextensiveexperiments.
B. Space and time-efficient algorithms for
PDEmodels.
Analgorithm
forone-dimensional time-dependent Stefan
problems was extended for the purpose ofsolving one-phase ablation-type moving
boundary problems; in tandem with theKeller box finite-difference scheme, theso-called boundary immobilization method
was used. An important component of thework
wastheuseofvariabletransformations that must be built into thenumerical algorithm in order to preserve
second-order accuracy in both time andspace. The analysis also determined thatthe ablation front initially moves as thetime raised to the power 3/2; hence, it
evolves considerably more slowly than thephase-change front in the classical Stefan
problem with isothermal cooling [9].
Another work deals with the accuracy of afinite-difference method for parabolic PDEs
with discontinuous boundary conditions.
Although the numerical solution ofparabolic partial differential equations(PDEs) is widely documented, the effect of
discontinuous boundary conditions onnumerical accuracy is not. This work
employs the Keller box finite-difference
method to study the effect of suchdiscontinuities when solving the linear 1D

transient heat equation. It demonstrates
that, without due care, this formallysecond-orderaccurate
schemeloses
accuracy,butthatananalyticalunderstanding of the behaviour of thesolution helps to reformulate the problem ina way that restores accuracy [10].
Yet another work considers scientific andtechnical applications that require thesolution of the steady 3D Navier Stokes
equations in slender channels or ducts;
often, this is carried out using commerciallyavailable software which is unable to makeuse of the fact that the equations can beparabolized to give a formulation that, interms of RAM and CPU time and random
access memory (RAM) usage, is orders ofmagnitude cheaper to compute. Here, avelocity-vorticity formulation in commercial
finite-element solver is implemented totackle the weakly compressible parabolized
steady 3D Navier Stokes equations in achannel with a permeable wall - a situationthat occurs in polymer electrolyte fuel cells.
Benchmarks results indicate at least a
30-fold saving in CPU time and a 70-foldsaving in RAM usage, as compared to full3D computations, without any discernible
loss in accuracy [11].
C. Time- and space-efficiency of embedded
software of intelligent peripherals.
Specialized pervasive encoding is well
suited for localization and automatednavigation in various robotic and assistive
applications where it is applied mostly toconfined interiors. Such encoding could beembedded in manufacturing, storage, andotherfacilities
whererobot-assisteddelivery and product handling is in place aswell as in smart homes for elderly anddisabled where automated transportationand specialized services are provided.
Extending the scope of such pervasive
encoding to natural human habitats
requires development of methods andtechnologies for i) seamless and unobtrusive
integration of pervasive encoding patterns
in human environments and ii) efficient andreliable
extraction,recognition,andanalysis of such codes. The study [5] is acontinuation of our previous research on
Environmental Codes for Autonomous
Position Determination based on interior

design patterns mainly for mobile robots
and reported elsewhere. In this work wehave shifted the focus to human users andexplore possibilities for environmental code
processing with widely used mobile devices
such as smart phones. We discussed theorganization and development of a novel
server-client
environment
integrating
Windows, Mac, and iOS systems andspecificallydesignedtofacilitateexperimental work with mobile devices.
Environmental
encoding
patternrecognition and localization experiments
are currently conducted on iPhones andother iOS based devices with plans to
expand to other platforms in the nearfuture.
Another aspect is the creation of encoding
areas inside different objects by laser
volumetricmarking[3,12].
Uniquecapacities of focused, short laser pulses, tocreate different kinds of marks (localstructure damages, micro-cracks, voids,
pores, optically active nanoparticles,
light-emitting centers, and other opticalinhomogeneities) in the volume of materials,
which are transparent for the selected laser
wavelength are studied. Laser-induced
marks with varying appearance (or datapixels) can serve as multi-bit information
carriers that open a wide range of new
possibilities for volumetric parameterizedmarking, encoding, and recording of digitalinformation.
Results
obtained
inexperiments with different approaches andlaser techniques for creation, monitoring,and measurement of such marks arereported.
D. Study on efficiency of brain computations
The
hypothesis
ofacommon
information-processing principle exploitedby the brains evolved through naturalevolution has been explored. A model
combining recent advances in cognitive
psychology and evolutionary neurosciencehas been proposed and analyzed. The
macroscopic effects associated with theintelligence-like structures postulated by
the model has been investigated anddiscussed from a statistical mechanics pointof view. As a result of this analysis, someplausible explanations have been presented
concerning the disparities and similarities

in cognitive capacities which are observedin nature across species. An interpretationon the efficiency of brain’s computations, aswell as the behavioral differences between
different species, including humans andchimpanzees has been largely discussed[13].
E. Computational and geometric approachto colorful simplicial depth
In statistics, there are several measures ofthe depth of a point p in dimension drelative to a fixed set S of sample points.
One key depth measure, introduced by Liu
in 1990, is the simplicial depth, which is thenumber of simplices generated by points in
S that contain p. A point of maximum
simplicial depth can be viewed as a type ofd-dimensional
median.
Acolourful
generalization of the simplicial depth wasintroduced and a new parity property wasproved. The work exhibited extremal
d-dimensional configurations with points oflow colorful simplicial depth, and provided
the first upper bound for the minimalcolorful depth µ(d) of a core point p for any
generic
configuration
S. The first
improvement since Bárány’s 1982 result of
the lower bound for µ(d) was obtained. Thelower bound has since been improved by
Bárány and Matoušek who verified thatµ(3)=10, and Deza et al. which includes thecurrent strongest bound of µ(d) ≥ d(d+7)/2-8for d≥5 and verified that µ(4)=17. The
colorful feasibility problem is the equivalent
generalization of the linear programming
feasibility problem; i.e., to express p as acolorful convex combination of points in S.
While the monochrome version is the
traditional linear programming feasibility
problem, and therefore efficiently solvable,
it is still not known if a polynomial timealgorithm for the colorful feasibility
problem exists. The recent publications
relevant to this line of research include[14,15,16](3.2) Future work
The obtained theoretical results laid out abasis for solving various practical problems.
The team is considering extending the workfor 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., Aggarwal,J.K.,(Eds.) Computational Image
Analysis, Springer Verlag, LNCS 7655,
Heidelberg-Berlin, 2012.
2. Barneva, R.P., Space and time efficientalgorithms in imaging sciences, The 15thInternational Conference on Humans
and Computers (HC-2012), ElectronicAbstracts
Collection(Hamamatsusessions), Paper No ID18, pp. 33. [11-12February 2013, Aizu-Wakamatsu &Hamamatsu,Japan;
Düsseldorf,Germany].
3. Gnatyuk, V.A., Kanev, K., Mizeikis, V.,
Aoki, T., Gagarsky, S.V., Poperenko,
L.V.,
Volumetric marking withlaser-induced parameterized centers,
The 15th International Conference on
Humans and Computers (HC-2012),
Electronic
Abstracts
Collection(Hamamatsu sessions), Paper No ID12,
pp. 20-21. [11-12 February 2013,
Aizu-Wakamatsu & Hamamatsu, Japan;
Düsseldorf, Germany].
4. Vynnycky, M., Kanev, K., The P3P
Problemrevisited,
The
15th
International Conference on Humans
and Computers (HC-2012), Electronic
Abstracts
Collection(Hamamatsusessions), Paper No ID08, pp. 13. [11-12February 2013, Aizu-Wakamatsu &Hamamatsu,
Japan;
Düsseldorf,Germany].
5. Inoue, T., Mochiduki, S., Kanev, K.,
Barneva, R.P., Environmental Encoding
Pattern Recognition and Localization
with Mobile Devices, The
15thInternational Conference on Humans
and Computers (HC-2012), Electronic
Abstracts
Collection(Hamamatsusessions), Paper No ID17, pp. 31. [11-12February 2013, Aizu-Wakamatsu &Hamamatsu,Japan;
Düsseldorf,
Germany].
6. Brimkov, V.E., Barneva, R.P. (Eds.),

International
Mathematics

Journalon

Computer(Taylor and Francis),
http://www.tandfonline.com/action/show
AxaArticles?journalCode=gcom20,
toappear in printed version in 2013.
7. Gonzalez, D., Malgouyres, R., Esbelin,
H.-A.,Samir,C.,
Fastlevel-wise
convolution,
Combinatorial
ImageAnalysis, Barneva, R.P., Brimkov, V.E.,
Aggarwal, J.K., (Eds.), Springer Verlag,
LNCS 7655, Heidelberg-Berlin, 2012, pp.
223-233.
8. Cartade, C., Mercat, C., Malgouyres, R.,
Samir, C., Mesh parameterization withgeneralized discrete conformal maps,
Journal of Mathematical Imaging andVision,Springer,
2013,
DOI
10.1007/s10851-012-0362-y
9. Mitchell, S. L., Vynnycky, M., An
accurate finite difference method for
ablation-type Stefan problems, J. Comp.
Appl. Math. 236 (2012) 4181-4192.
10.
Vynnycky, M., Mitchell, S. L., On
the accuracy of a finite-difference
method for parabolic PDEs withdiscontinuous boundary conditions, Num.
Heat Trans. B (2012) submitted.
11.
Vynnycky, M., Sharma, A. K.,
Birgersson, E., A finite-element method
for the weakly compressible parabolized
3D Navier Stokes equations in a channel
with a permeable wall, Comput. Fluids(2012) submitted
12.
Gnatyuk, V.A., Kanev, K., Mizeikis,
V., Aoki, T., Gagarsky, S.V., Poperenko,
L.V., Laser marking and recording ofdigital information, Proceedings of The
11th International Conference on Global
Research and Education in Engineers
and Better Life: Inter-Academia-2012,(August, 2012) pp.189-200.
13.
Chinea,A.,
Korutcheva,
E.,Intelligence
andembodiment:A
statistical mechanics approach, Journal
onNeuralNetworks,DOI:
10.1016/j.neunet.2013.01.007, Reference:
NN 3127.
14.
Deza,A.,
Meunier,F.,
Sarrabezolles, P., A Combinatorial
approach to colourful simplicial depth.
AdvOL-Report
2012/4,
McMasterUniversity (2012) submitted.
15.
Deza, A., Stephen, T., Xie, F., A
note on lower bounds for colourfulsimplicial depth, Symmetry 5 (2013) 47
- 53.
16.
Meunier, F., Deza, A., A further
generalizationofthecolourfulCarathéodory
theorem.
Discrete
Geometry and Optimization, Fields
Institute Communications Series 69 (toappear).

Travelling report
Name:
Affiliation:

Reneta Barneva
State University of New York at
Fredonia, USA
Period of time:
February 9, 2013 – February 18,
2013
Destination:
Research Institute of Electronics,
Shizuoka University, Japan
Purpose:Participation in the 15thInternational
Conference
Human and Computers. Giving
a talk “Space and Time Efficient
Algorithms in Imaging Sciences.”
Discussing various tasks of thecollaborative project research.
Name of receiver: Prof. Kamen Kanev
Name:
Affiliation:

Michael Vynnicky
Department of Mathematics
and Statistics, University ofLimerick, Ireland
Period of time:
February 9, 2013 – February 19,
2013
Destination:
Research Institute of Electronics,
Shizuoka University, Japan
Purpose:Participation in the 15thInternational
Conference
Human and Computers. Giving
a talk “The P3P Problem
Revisited.” Discussing various
tasks of the collaborative project
research.
Name of receiver: Prof. Kamen Kanev