Installing openCV in anaconda3 - Python.h: No such file or directory

I'm trying to build opencv 3.1.0 for my anaconda3 installation and my build is failing at:

[ 94%] Building CXX object modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o
/home/mikel/Soft/opencv/modules/python/src2/cv2.cpp:6:20: fatal error: Python.h: No such file or directory
compilation terminated.

I have opencv and opencv-contrib cloned with versions 3.1.0 by using git checkout 3.1.0 in both and I am trying to build in ~/Soft/opencv/build where I have opencv-contrib in ~/Soft/opencv-contrib. I'm running Ubuntu GNOME 15.10 with an i7-4960X.

My main goal is to make opencv work in my anaconda3 installation and so my cmake command is the following:

cmake \
 -D  CMAKE_BUILD_TYPE=RELEASE \
 -D  CMAKE_INSTALL_PREFIX=/usr/local \
 -D  INSTALL_C_EXAMPLES=OFF \
 -D  INSTALL_PYTHON_EXAMPLES=ON \
 -D  OPENCV_EXTRA_MODULES_PATH=~/Soft/opencv_contrib/modules \
 -D  PYTHON3_EXECUTABLE=/home/mikel/anaconda3/bin/python3.5 \
 -D  PYTHON3_INCLUDE_DIR=/home/mikel/anaconda3/include/ \
 -D  PYTHON3_LIBRARY=/home/mikel/anaconda3/lib/libpython3.5m.so \
 -D  PYTHON3_PACKAGES_PATH=/home/mikel/anaconda3/lib/python3.5/site-packages/ \
 -D  PYTHON3_NUMPY_INCLUDE_DIRS=/home/mikel/anaconda3/lib/python3.5/site-packages/numpy/core/include \
 -D  PYTHON_DEFAULT_AVAILABLE=/home/mikel/anaconda3/bin/python3.5 \
 -D  BUILD_EXAMPLES=ON ..

The output of my cmake command is here: http://pastebin.com/qtd1wyMb - Everything okay as far as I can see.

I then run make -j12 to install opencv and after a few warnings it runs fine until 94%, where I get the following output:

Scanning dependencies of target opencv_python3
[ 94%] Building CXX object modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o
/home/mikel/Soft/opencv/modules/python/src2/cv2.cpp:6:20: fatal error: Python.h: No such file or directory
compilation terminated.
modules/python3/CMakeFiles/opencv_python3.dir/build.make:278: recipe for target 'modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o' failed
make[2]: *** [modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o] Error 1
CMakeFiles/Makefile2:18929: recipe for target 'modules/python3/CMakeFiles/opencv_python3.dir/all' failed
make[1]: *** [modules/python3/CMakeFiles/opencv_python3.dir/all] Error 2
make[1]: *** Waiting for unfinished jobs....
[ 94%] Building CXX object modules/stitching/CMakeFiles/opencv_perf_stitching.dir/perf/perf_main.cpp.o
[ 94%] Built target opencv_test_optflow
[ 94%] [ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_registration.dir/tutorial_code/calib3d/real_time_pose_estimation/src/CsvWriter.cpp.o
Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/CsvReader.cpp.o
[ 94%] [ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_registration.dir/tutorial_code/calib3d/real_time_pose_estimation/src/ModelRegistration.cpp.o
Building CXX object modules/stitching/CMakeFiles/opencv_test_stitching.dir/test/ocl/test_warpers.cpp.o
[ 94%] Building CXX object modules/stitching/CMakeFiles/opencv_perf_stitching.dir/perf/opencl/perf_stitch.cpp.o
Linking CXX executable ../../bin/cpp-example-bgfg_segm
Linking CXX executable ../../bin/cpp-example-autofocus
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/CsvWriter.cpp.o
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/ModelRegistration.cpp.o
[ 94%] Linking CXX executable ../../bin/opencv_test_tracking
Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_registration.dir/tutorial_code/calib3d/real_time_pose_estimation/src/Mesh.cpp.o
[ 94%] Built target example_bgfg_segm
[ 94%] [ 94%] Built target example_autofocus
Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_registration.dir/tutorial_code/calib3d/real_time_pose_estimation/src/Model.cpp.o
[ 94%] [ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_registration.dir/tutorial_code/calib3d/real_time_pose_estimation/src/Utils.cpp.o
Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_registration.dir/tutorial_code/calib3d/real_time_pose_estimation/src/PnPProblem.cpp.o
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/Mesh.cpp.o
[ 94%] Built target opencv_test_tracking
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/Model.cpp.o
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/PnPProblem.cpp.o
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/Utils.cpp.o
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_registration.dir/tutorial_code/calib3d/real_time_pose_estimation/src/RobustMatcher.cpp.o
[ 94%] Building CXX object samples/cpp/CMakeFiles/cpp-tutorial-pnp_detection.dir/tutorial_code/calib3d/real_time_pose_estimation/src/RobustMatcher.cpp.o
[ 94%] Building CXX object modules/stitching/CMakeFiles/opencv_perf_stitching.dir/perf/opencl/perf_warpers.cpp.o
Linking CXX executable ../../bin/cpp-example-3calibration
[ 94%] Building CXX object modules/stitching/CMakeFiles/opencv_test_stitching.dir/test/test_main.cpp.o
[ 94%] Built target example_3calibration
Linking CXX executable ../../bin/opencv_test_stitching
[ 94%] Built target opencv_test_stitching
Linking CXX executable ../../bin/cpp-tutorial-pnp_registration
[ 94%] Built target cpp-tutorial-pnp_registration
Linking CXX executable ../../bin/cpp-tutorial-pnp_detection
[ 94%] Built target cpp-tutorial-pnp_detection
Linking CXX executable ../../bin/opencv_perf_stitching
[ 94%] Built target opencv_perf_stitching
Makefile:146: recipe for target 'all' failed
make: *** [all] Error 2

The full output from make is here for reference: http://pastebin.com/1zNgsckZ

It looks like my issue is because I'm using the anaconda3 paths instead of the standard python3 paths, it can no longer find Python.h. However, when I install using the system python3 installation, I can't import opencv into anaconda where I need it.

I have python3-dev and python-dev installed, so Python.h should be on my machine. What do I need to change in order to make openCV find Python.h?

EDIT: I found that Anaconda3's Python.h is in anaconda3/include/python3.5m/ so I set PYTHON3_INCLUDE_DIR=anaconda3/include/python3.5m/ and now I get a different error:

Scanning dependencies of target opencv_python3
Linking CXX executable ../../bin/opencv_test_optflow
[ 91%] Building CXX object modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o
In file included from /home/mikel/Soft/opencv/build/modules/python3/pyopencv_generated_include.h:11:0,
                 from /home/mikel/Soft/opencv/modules/python/src2/cv2.cpp:12:
/home/mikel/Soft/opencv_contrib/modules/hdf/include/opencv2/hdf/hdf5.hpp:40:18: fatal error: hdf5.h: No such file or directory
compilation terminated.
modules/python3/CMakeFiles/opencv_python3.dir/build.make:278: recipe for target 'modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o' failed
make[2]: *** [modules/python3/CMakeFiles/opencv_python3.dir/__/src2/cv2.cpp.o] Error 1
CMakeFiles/Makefile2:18929: recipe for target 'modules/python3/CMakeFiles/opencv_python3.dir/all' failed
make[1]: *** [modules/python3/CMakeFiles/opencv_python3.dir/all] Error 2
make[1]: *** Waiting for unfinished jobs....